אלגוריתם הדירוג של גוגל
20/11/2019
גוגל התחילה את דרכה עם אלגוריתם בשם PageRank, המשתמש באלגברה לינארית לצורך דירוג דפים ברשת. האלגוריתם פותח בשנת 1998 ב-MIT (המכון הטכנולוגי של מסצ'וסטס) על ידי סטודנט בשם לארי פייג', יחד עם שותפו סרגיי ברין, ונקרא על שמו של פייג' (ולא בגלל ש-Page הוא דף באנגלית). כזכור, לארי הוא זה שהקים עם סרגיי את גוגל והיה המנכ"ל שלה.
גוגל התחילה את דרכה עם אלגוריתם בשם PageRank, המשתמש באלגברה לינארית לצורך דירוג דפים ברשת. האלגוריתם פותח בשנת 1998 ב-MIT (המכון הטכנולוגי של מסצ'וסטס) על ידי סטודנט בשם לארי פייג', יחד עם שותפו סרגיי ברין, ונקרא על שמו של פייג' (ולא בגלל ש-Page הוא דף באנגלית). כזכור, לארי הוא זה שהקים עם סרגיי את גוגל והיה המנכ"ל שלה.
כאשר אנו מקלידים דבר מה במנוע החיפוש של גוגל, תוך חלקיק שניה מתקבלת על המסך רשימה ארוכה של דפי אינטרנט רלוונטיים. כיצד מנוע החיפוש של גוגל מדרג את כל הדפים האלו? נספר על השיטה, כהרגלנו, באמצעות סיפור דמיוני. הפעם נספר על סטודנטים חסרי מנוח שיוצאים לבלות בפאבים. בהמשך, נסביר לקוראינו שצלחו בשלום פסקה המכילה גם משוואות, את הקשר בין הסיפור לאלגוריתם הדירוג של גוגל.
סיפורנו מתחיל עם שלושה פאבים אליהם מגיעים סטודנטים בערבו של יום. נקרא לפאבים אריה (A), ברבית (B), וסליקי (C). נתון ש-70% מהסטודנטים הם חסרי מנוח, ובכל שעה עגולה מחליטים לצאת ולעבור לפאבים סמוכים. מפאב A ניתן להגיע ישירות ל-B וגם ל-C ולכן הסטודנטים שיצאו מ- A יתפצלו חצי וחצי. מפאב B ניתן להגיע רק ל-C ,ומ-C ניתן להגיע רק ל-A. מה הסיכוי שבבדיקה מדגמית שנבצע לאחר מספר שעות, נגלה שסטודנט כלשהו (נניח ששמו יומירן) נמצא בפאב A, בפאב B, או בפאב C, וכיצד נוכל להשתמש בתוצאה לדרג את מידת הפופולריות של הפאבים?
מי שלא מתעניין במתמטיקה, מוזמן לדלג כמה פסקאות קדימה. לאחרים, נספר שניתן למדל מתמטית את הבעייה באופן פשטני ומקורב באמצעות נוסחת נסיגה (נוסחה המאפשרות חישוב אברי סידרה בתלות באברים הקודמים שלה). למשל: כדי לחשב את הסיכוי שיומירן ימצא בפאב B בשעה n, נתחשב בשני אירועים ונסכם את ההסתברויות שלהם: עבור המקרה שהוא סטודנט עייף נקבל סיכוי של 10% (בהנחה פשטנית ש-30% הסטודנטים העייפים מתחלקים תמיד באופן שווה בין שלושת הפאבים). במקרה שהוא בקבוצת הנמרצים נקבל סיכוי 70% שמוכפל בהסתברות שבשעה n-1 הוא היה דווקא בפאב A ומוכפל גם בהסתברות חצי, כי רק חצי מהיוצאים מ-A מגיעים ל-B. לפיכך, משוואות הנסיגה עבור B, ובאופן דומה עבור-A ו-C יהיו:
PB(n) = 0.1 + 0.7* PA(n-1)/2; PC(n)= 0.1+0.7*(PA(n-1)/2+PB(n-1)); PA(n)= 0.1 + 0.7 * PC(n-1);
מערכת משוואות כזאת, המערבת משוואות נסיגה עם הסתברות נקראת "שרשרת מרקובית". מה לדעתכם תהייה התפלגות הסטודנטים בין הפאבים השונים בשעות הקטנות של הלילה? או במילים אחרות: מה ההסתברות שנפגוש את יומירן בכל אחד מהפאבים בשעות אלו? ניתן למצוא נוסחה כללית לפתרון הבעייה באמצעות כלים מתמטיים (למי שלמד פעם אלגברה לינארית אולי ייזכר שחישוב כזה נעשה באמצעות מציאת "ערכים עצמיים" של מטריצה [1]). אולם, אנו נעשה קיצור דרך, ופשוט נבנה משוואות באקסל.
באמצעות הצבה נגלה שאחרי 8 שעות, ההסתברות שיומירן יהיה בפאב C היא 39%, בפאב A היא 38%, ובפאב B רק 23%. מהצבות נוספות נוכל לראות שהגענו קרוב למצב יציב שממנו ההסתברויות לא ישתנו לאורך זמן.
דירוג הפופולריות של הפאבים נקבע בהתאם להסתברות שיומירן ימצא בהם במצב יציב. נוכל לראות מהחישוב שפאב C הוא הכי פופולרי. הסיבה היא שישנם שני פאבים שמובילים אליו. אולם מדוע פאב A פופולרי יותר מ-B? הסיבה היא שפאב A מקושר לפאב C הפופולרי. מסקנה לחיים: כדי להיות פופולריים, תתחברו לאנשים פופולריים...
סיפור זה הוא אנלוגיה לאלגוריתם PageRank, האלגוריתם הבסיסי של גוגל. אם נחליף "פאב" ל"אתר", ושביל שמוביל לפאב עם קישור לאתר, נקבל סיפור דומה. מטרת האלגוריתם היא לחשב עבור כל דף אינטרנט את "אינדקס הפופולריות" שלו, כדי שמנוע החיפוש יוכל להשתמש בו להצגת תוצאות חיפוש ממוינות לפי מידת הפופולריות של האתרים.
האלגוריתם סורק את הדפים ברשת ומוצא את הקישורים ביניהם (באנלוגיה: "יוצר את מפת השבילים בין הפאבים"). לאחר מכן, הוא עושה סימולציה להתנהגות גולשים כדי לשערך באילו אתרים הם מבקרים יותר פעמים. PageRank מניח שבכל ביקור באתר כלשהו, חלק מהגולשים מתיאש ומפסיק לגלוש, אולם חלק אחר מתמיד (באנלוגיה שלנו: 70%). בסיום החישובים שדומים לאנלוגיה, הציון של אתר נקבע בהתאם להערכת הסיכוי שגולש כלשהו יבקר בו.
PageRank הוא לא רק שעשוע מתמטי נחמד. לעיתים, הוא חורץ את גורלם של חברות ועסקים הנאבקים להופיע גבוה בחלון החיפוש של גוגל. באופן כללי, ניתן ללמוד שדירוג הפופולריות של אתר נקבע לפי מספר הקישורים שמובילים אליו, אבל גם לפי פופולריות האתרים שמצביעים עליו. למשל, אם אלילת הנוער נועה קירל תוסיף באתר הפופולרי שלה קישור לאתר העמותה "מדע גדול בקטנה" תהיה לכך תרומה גדולה יותר לאינדקס הפופולריות, לעומת אם אחד מחברי העמותה יוסיף לינק מאתר הבית שלו לאתר העמותה. אולם, מסתבר שהתמונה לא כל כך פשוטה: תחקיר שפרסם השבוע וול סטריט ג'ורנל חשף כי לעיתים גוגל מטה את תוצאות החיפוש! זה לא רק "מתמטיקה בקטנה" [2].
בינתיים, אנו מתפעלים כיצד אלגוריתם מתמטי מתחום אלגברה לינארית משפיע כל כך על העולם האינטרנטי. למי שמעוניין להבין את המתמטיקה, נשמח להפנות אותו לבלוג המצוין של גדי אלכסנדרוביץ, חבר העמותה [1]: הוספנו לינק מהאתר שלנו לבלוג של גדי, תרומתנו הצנועה להגדלת אינדקס הפופולריות שלו.
מהנדס מחשבים, חוקר ויזם בתחום החינוך המתמטי.
