אם יזדמן לכם להיכנס לפקולטה לחשמל בטכניון, תוכלו להבחין בשלט: "הפקולטה להנדסת חשמל ע"ש ויטרבי". אנדרו ויטרבי הוא יהודי אמריקאי ממוצא איטלקי, פרופסור להנדסת חשמל ואיש עסקים שתרם 50 מיליון דולר לפקולטה. הוא ידוע גם כמייסד חברת קוואלקום, חלוצה בתחום תקשורת סלולרית. אבל אנדרו ידוע בעיקר כמפתח "אלגוריתם ויטרבי" המסייע לתיקון רעש דיגיטלי ונמצא בשימוש בתחומים מגוונים: תקשורת סלולרית, WIFI, זיהוי דיבור, ניתוח תחבירי, ביואינפורמטיקה כמו ניתוח רצפי-DNA ובשלל נושאים אחרים. אז מה הקסם שהופך אותו לכל כך שימושי? 

נתאר את האלגוריתם באמצעות אנלוגיה, וכדי להישאר נאמנים להיסטוריה, נשתמש בבעיה המקורית אותה פתר ויטרבי. סיפורנו מתחיל עם ארבעה פאבים, שנקרא להם א, ב, ג, ו-ד אליהם מגיעים סטודנטים בשעה תשע בערב. הסטודנטים חסרי מנוח, וכל שעה עגולה מחליטים אם להישאר או ללכת לפאבים סמוכים. אולם אין חיבור בין כל הפאבים. למשל, מפאב א יש שביל רק לפאב ג , והסטודנטים עוברים אליו בהסתברות 50%. מפאב ב יש שתי יציאות, ל-א ול-ג , וכולי  (המסלולים בדוגמה של ויטרבי מופיעים בציור באתר).

אנו רוצים לעקוב אחרי סטודנט, שנקרא לו למשל יומירן, ולבדוק היכן בילה כל שעה. לשם כך נבקש מסטודנטים שמזהים אותו להודיע על מיקומו באמצעות שדר אלחוטי. אולם, מכיוון שהסטודנטים שיכורים, חלק מהדיווחים מתבלבלים ולכן נוכל לדעת את מיקומו של יומירן בכל שעה, רק בסבירות מסוימת. נניח למשל שהסבירות המשוערכת שיומירן היה בשעה תשע בפאב א, ב, ג או ד, היא: 40%, 10%, 20%, ו- 30% בהתאמה, ובשעה עשר: 20%, 50%, 40% ו- 30%, וכולי. האם נוכל להעריך מה היה המסלול הסביר ביותר שעשה יומירן בלילה בכל שעה?

ממבט חטוף בנתונים, האפשרות שנראית הכי סבירה היא שיומירן עבר בשעה עשר מפאב א ל-ב, אולם, מסלול זה לא קיים. אכן, לא מספיק להסתכל על כל אירוע בנפרד, צריך להתחשב גם בהסתברויות למעברים בין הפאבים. למשל, לחישוב הסבירות שיומירן עבר בשעה עשר מ-א ל-ג, נכפיל את הסבירות שהיה בתשע ב-א בהסתברות למעבר מ-א ל-ג (50%) ואת התוצאה נכפול בסבירות שיומירן היה בעשר בפאב ג.

כדי למצוא את סדרת המעברים הסבירה ביותר במשך עשר שעות, נוכל לנסות את כל הסדרות האפשריות (למשל סדרה "אאגדדבגבגד"), להכפיל ולמצוא  את הסדרה עם מכפלת ההסתברויות המקסימלית. הבעיה היא שיש הרבה סדרות אפשריות. האם יש דרך למצוא זאת בלי לבדוק את כולם?

זה בדיוק מה שהאלגוריתם של ויטרבי עושה [1], והרעיון שמאחוריו פשוט להפליא. כיוון שאנו מעוניינים למצוא רק את המסלול עם מכפלת ההסתברויות המקסימלית,  נבדוק את האפשרויות בכל מעבר בשעה עגולה החל משעה עשר, ונזרוק כבר בשלבים מוקדמים אפשרויות שלא מתאימות. למשל, כיוון שהסבירות להגיע לפאב ג מפאב ב בשעה 10 נמוכה יותר מאשר הסבירות להגיע לשם מפאב א, נזרוק את האפשרות הזאת. בצורה דומה, נזרוק בכל מעבר עוד אפשרויות, ובכל שעה עגולה נשמור עבור כל אחד מהפאבים רק אפשרות אחת, שהיא הסבירה ביותר להגיע אליו. באופן כללי, עבור בעיה עם ארבעה פאבים, נוכל למצוא את המסלול הסביר עבור עשר שעות באמצעות 160 בדיקות במקום ארבע בחזקת עשר בדיקות.

אלגוריתם זה הוא די פשוט, אז מה הייחוד שבו? התשובה היא היישומיות שלו. בשנת 1967 התחבט אנדרו ויטרבי במשך מספר חודשים בבעיה הבאה: כיצד ניתן לשלוח מידע דיגיטלי בסביבה רועשת (למשל בתקשורת אלחוטית) ולשחזר אותו במקלט? הפתרון שמצא היה לבנות משדר עם ארבעה מצבי שידור (באנלוגיה:"פאבים"), שבו שידור אינפורמציה נעשה באמצעות מעבר בין המצבים ("שוטטות בין הפאבים"). בכל מעבר, המשדר שולח אותות והמקלט מנסה לקלוט ולשער באיזה מצב המשדר נמצא. יש רעשים בקליטה ("הסטודנטים המשדרים קצת שתויים"), אולם מה שעוזר להתגבר הוא שהמקלט נותן אינדיקציה סטטיסטית על איכות האותות שנקלטו [2], ממנה ניתן להעריך את הסבירות להמצאות בכל מצב שידור. מה שעוד עוזר הוא שיש מעברי מצבים בלתי אפשריים (כמו באנלוגיה: המעבר מפאב א ל- ב) שמעניקים עמידות בפני שגיאות מסוימות. באמצעות האלגוריתם שפיתח ויטרבי ניתן למצוא את סדרת המעברים בין המצבים ("המסלול הלילי של יומירן") הסבירה ביותר, ולשחזר את האינפורמציה ששודרה.

המקלטים בטלפונים שלנו ממשים את אלגוריתם ויטרבי או דומים לו. ניתן להשתמש באלגוריתמים כאלו גם בתחומים רבים אחרים. בהינתן בעיה הכוללת מספר מצבים אפשריים והסתברות המעברים ביניהם (מה שקרוי: "רשת מרקובית"), כאשר המצבים הללו חבויים, וכל מה שאנחנו מקבלים היא אינפורמציה סטטיסטית עקיפה, ניתן להשתמש באלגוריתם ויטרבי או הרחבותיו כדי למצוא את רצף המעברים הסביר. למשל, בעייה יותר מעניינת מלדעת את רצף הפאבים שבהם ביקר יומירן בלילה היא לזהות רצפים של ארבעת הבסיסים המרכיבים את הדנ"א (A,G,T,C).

החוכמה בפתרון בעיה הנדסית ומדעית היא למצוא את המודל המתמטי המתאים לה, וזה מה שפרופסור אנדרו ויטרבי עשה.

לאנדרו ויטרבי יש קשר קרוב לטכניון, ומשפחתו תרמה רבות למוסד זה. עם תרומותיהם נמנים קתדרת אנדרו וארנה פינצ'י ויטרבי למערכות מידע ומדעי המחשב, מרכז אנדרו וארנה פינצ'י ויטרבי ללימודים מתקדמים בטכנולוגיות מחשב בפקולטה להנדסת חשמל, ותכנית המלגות ע"ש אנדרו וארנה פינצ'י ויטרבי. בנוסף, בשנת 2015 תרם אנדרו ויטרבי 50 מיליון דולר לפקולטה להנדסת חשמל בטכניון, שכיום נקראת על שמו.

[1] אלגוריתם ויטרבי

[2] מקודד ויטרבי