אינדוקציה לאחור הוא תהליך של הסקה, אחורה בזמן, מסופם של בעיה או מצב, על-מנת לבחור רצף פעולות אופטימלי. התהליך מתחיל בנקודת ההחלטה האחרונה, בה מסתכל השחקן מה הפעולה שהכי משתלם לו לשחק. בהינתן המידע הזה, ניתן להחליט בצעד הלפני אחרון מה הצעד המשתלם ביותר (בהנחה שבצעד האחרון בחר השחקן המחליט את הפעולה המשתלמת ביותר עבורו), וכך הלאה. את התהליך הזה ניתן לבצע עד לתחילת המשחק, וכך להסיק מה הפעולה האופטימלית, לכל שחקן, בכל נקודת זמן במשחק.
בתכנון דינמי, אינדוקציה לאחור היא אחת השיטות המרכזיות לפתירת משוואת בלמן. בתורת המשחקים, אינדוקציה לאחור משמשת לחישוב שיווי משקל תת-משחקי משוכלל במשחקים סדרתיים. ההבדל היחיד הוא שהאופטימיזציה מערבת מקבל החלטות יחיד, שבוחר מה לעשות בכל נקודה בזמן, בעוד שבתורת המשחקים, ניתן לנתח קבלת החלטות של מספר שחקנים, כפי שתואר לעיל.
בתורת המשחקים, אינדוקציה לאחור הוצגה לראשונה על ידי ג'ון פון נוימן ואוסקר מורגנשטרן בספרם "תורת המשחקים והתנהגות כלכלית" (1944).
פסאודו-קוד.
eval(node):
if node is a leaf
return value(node)
if node is a min-node
current-min = +infinity
for all children u of node do
x = eval(u)
current-min = minimum(x, current-min)
return current-min
else // node is a max-node
current-max = -infinity
for all children u of node do
x = eval(u)
current-max = maximum(x, current-max)
return current-max
לאלגוריתם זה ניתן לעשות אופטימיזציה בעזרת שיטה שנקראת גיזום אלפא-ביתא, מבלי לשנות את התוצאה שהיה מחזיר האלגוריתם המקורי.
קבלת החלטות בעזרת אינדוקציה לאחור: דוגמה.
ניקח, לדוגמה, אדם מובטל שיהיה מסוגל לעבוד רק בעשר השנים הקרובות: formula_1. נניח כי בכל שנה שבה הוא נשאר מובטל, מציעים לו עבודה 'טובה' בה יקבל 100 ש"ח, או עבודה 'גרועה' שבה יקבל 44 ש"ח, בהסתברות 50/50 בכל פעם. ברגע שהוא מסכים לעבודה, הוא יעבוד בה עד לסוף עשר השנים.
(נניח, לשם פשטות, שכל שמעניין את אותו אדם הוא הרווחים הכספיים שלו, ושהוא מעריך כסף בצורה זהה בזמנים שונים. כלומר, לריבית אין משמעות במשחק זה).
האם עליו לקבל עבודה גרועה שהוצעה לו? כדי לענות על השאלה נשתמש באינדוקציה לאחור מהזמן t=10 אחורה.
ניתן להמשיך ולראות שכדאי לאדם המובטל לקבל הצעות גרועות רק בזמנים 9 או 10. בכל שאר הזמנים עליו לסרב. אינטואיטיבית, אם הוא רוצה לעבוד זמן רב, יותר משתלם לו להיות בררן לגבי העבודה בה הוא בוחר.
בעיית אופטימיזציה דינמית מהצורה הזו נקראת בעיית עצירה אופטימלית, כיוון שהנושא המרכזי כאן הוא האם לעצור או לחכות להצעה טובה יותר. תורת החיפוש היא הענף במיקרו-כלכלה שמתייחס לבעיות מסוג זה בהקשרים כמו קניות, חיפוש עבודה ונישואין.
אינדוקציה לאחור בתורת המשחקים: דוגמאות.
משחק הפיראטים.
נניח כי ישנם חמישה פיראטים שרוצים להתחלק באוצר של 100 מטבעות זהב. שמות הפיראטים הם A, B, C, D, E ומעמדם בהתאם. בהיותנו על ספינת פיראטים דמוקרטית, חלוקת השלל תתבצע באופן הבא: כל פיראט בתורו (לפי סדר החשיבות) יציע דרך לחלוקת השלל, ואם יהיה רוב בעד ההצעה, היא תתקבל. אחרת, ייזרק הפיראט אל הכרישים. נשאלת השאלה: כיצד יחולק השלל?
אינדוקציה לאחור עוזרת לנו למצוא את הפתרון. נתחיל מהסוף. בנקודת ההחלטה האחרונה נשארו הפיראטים D ו-E. הפיראט D יודע כי כל הצעה שיציע, מלבד 0 עבורו ו-100 עבור הפיראט E, לא תקבל רוב, והוא ישחה עם הכרישים (כיוון שעדיף ל-E לסרב ולקחת את כל השלל). לכן, הוא מציע ל-E את כל השלל. כעת, בנקודת ההחלטה הקודמת, נשארו C, D ו-E. הפיראט C צריך למשוך אליו רק עוד פיראט אחד על מנת שהצעתו תתקבל, ולכן הוא יציע לפיראט D מטבע בודד, וייקח 99 לעצמו. נחזור עוד אחורה, אל B, C, D ו-E. הפיראט B צריך איתו עוד שני פיראטים, ולכן יציע ל-D שני מטבעות, ול-E מטבע אחד. נזכיר, שבהינתן שכל הפיראטים פועלים על פי אותו ההיגיון, זהו באמת תשלום טוב יותר מכל מצב אחר, אם יסרבו. לבסוף, אם נחזור להתחלה, A יודע שכל שעליו לעשות הוא לשכנע שני פיראטים. לכן, הוא ייתן לפיראט C מטבע אחד, ולפיראט E שני מטבעות. הוא עצמו יישאר עם 97 מטבעות.
משחק מרבה-הרגליים.
איש עשיר מת והוריש לשני בניו, יוסי ודני, הון בשווי מיליון ועשרת אלפים ש"ח (1,010,000). יחד עם הירושה, השאיר האב הוראות: יוסי, האח הבכור, יכול לקחת לעצמו 100 ש"ח, להשאיר לאחיו שקל אחד, ואת כל שאר הסכום לתרום לצדקה. יוסי אינו חייב לקבל את החלוקה הזו. הוא יכול להעביר את ההחלטה לאחיו, אך הפעם החלוקה תהיה שונה לגמרי: דני יקבל 1,000 ש"ח, בעוד יוסי, שקיבל קודם 100 ש"ח, יקבל רק 10 ש"ח. השאר ייתרם לצדקה. גם דני לא חייב לקבל את החלוקה הזו. הוא יכול להעביר את ההחלטה שוב לידיו של יוסי שיוכל לקחת לעצמו 10,000 ש"ח, ולתת לדני 100 ש"ח. היתר ייתרם לצדקה. יוסי יכול להעביר את ההחלטה לידיו של דני שוב, והתשלומים יהיו 100,000 ש"ח לדני ו-1,000 ש"ח ליוסי. ולבסוף, יכול דני להעביר את ההחלטה ליוסי שיקבל 1,000,000 ש"ח בעוד דני יקבל 10,000 ש"ח ואף שקל לא ייתרם לצדקה.
מה יקרה במצב כזה? דני יבין שאם הוא לא ייקח לעצמו 100,000 ש"ח. יוסי ייקח לעצמו 1,000,000, וישאיר אותו, דני, עם 10,000 בלבד. לכן הוא ייקח לעצמו 100,000 ש"ח. יוסי יבין זאת, ולכן כבר בשלב הקודם יחליט לקחת לעצמו 10,000 ש"ח, ולתת לדני 100. כך, יגיעו שני האחים למצב העגום בו יוסי יקבל 100 ש"ח, דני יקבל שקל אחד, וכל שאר הסכום ייתרם לצדקה.
פרדוקס בוחן הפתע.
נניח כי המורה מחליטה להודיע לכיתה ביום ראשון כי השבוע ייערך בוחן פתע במתמטיקה.
אם ישתמשו התלמידים באינדוקציה לאחור, יבינו מיד כי אם עד ליום חמישי לא נערך הבוחן, הוא יהיה חייב להיות בשישי, ולכן לא יפתיע אף אחד. לכן, חייבת המורה לערוך אותו בחמישי. אך, אם יפסלו את יום שישי, בהגיעם ליום רביעי יסיקו כי הבוחן ייערך בחמישי. התלמידים ימשיכו כך, עד לתחילת השבוע ויסיקו, לשמחתם, כי המורה לא יכולה לקיים בוחן פתע באף יום בשבוע. המורה, מצדה, תקיים את בוחן הפתע ביום רביעי, למשל, ותפתיע את כולם.
כאן, התלמידים משתמשים באינדוקציה לאחור, ומגיעים למסקנה שגויה. אך, שימו לב כי תיאור הבעיה מניח כי ניתן להפתיע שחקן שמשתמש באינדוקציה לאחור. התאוריה המתמטית שמאחורי השיטה אינה מניחה הנחה זו, ולכן הפרדוקס אינו סותר את התאוריה. אף על פי כן, פרדוקס זה ידוע מאוד ונדון רבות בהקשרים פילוסופיים.
Google AdSense
Google AdSense (קריא בעברית: גּוּגֶל אֵדְסֶנְס) היא רשת פרסום בבעלות חברת גוגל המאפשרת לבעלי אתרי אינטרנט למכור שטחי פרסום ומאפשרת בנוסף למכור שטחי פרסום בסרטונים ואפליקציות.
הרשת משלמת כ-10 מיליארד דולר בשנה (נכון לשנת 2012) לחברים ברשת. רשת הפרסום של גוגל תומכת במודעות בצורה של טקסט, תמונות או וידאו. האלגוריתם של גוגל יודע להתאים מודעה רלוונטית לעמוד ולאתר בו היא מפורסמת ומכאן השם AdSense.
היסטוריה.
השירות הושק במרץ 2003 ופומבית ביוני 2003.
באפריל 2003 רכשה גוגל את חברת אפלייד סמנטיקס (לשעבר אוינגו) תמורת 102 מיליון דולר. אוינגו הוקמה בשנת 1998 על ידי גלעד אלבז ואדם ויצמן ופיתחה אלגוריתם חיפוש על בסיס המשמעות של המילים. האלגוריתם עשה שימוש ב-WorldNet, פרויקט שהחל באוניברסיטת פרינסטון ב-1980. לאחר רכישת אפלייד סמנטיקס, כ-40 מעובדיה עברו לגוגל והמשיכו בפיתוח האלגוריתם ובפיתוח ה-AdSense.
ברבעון השלישי של 2012, הכנסות Google AdSense היו 3.13 מיליארד דולר. שהן כ-27% מהכנסות גוגל ברבעון הנ"ל.
בחירת הפרסומת.
בחירת סוג הפרסומת שתוצג לגולש מסוים נעשית על ידי אלגוריתמים. מטרת האלגוריתמים היא למקסם את הרווח משטח הפרסום על ידי בחירת מודעה שהופעתה עשויה להכניס לרשת הפרסום ולבעל האתר את הסכום הגבוה ביותר בסיכוי הגבוה ביותר.
בחישוב הסיכוי של המודעה להכניס כסף לרשת הפרסום נלקחים בחשבון:
בעל אתר, המוכר שטחי פרסום דרך רשת הפרסום יכול לחסום מפרסמים מסוימים מלפרסם אצלו באתר.
הרווחים מהתוכנית.
גוגל מתחלקת עם בעלי שטח הפרסום בתמורה שהיא מקבלת מהמפרסם. החלוקה היא ע"פ סוג שטח הפרסום.
במקרה של אתרי תוכן – 68% מהמחיר אותו משלם המפרסם מועבר לבעל האתר.
שלבי התהליך הם כדלקמן:1. אחד מחברי רשת הפרסום "גוגל אָדְסֶנס"- מעלה סרטון פרסומי לאתר יוטיוב.2. מעלה הסרטון משלם לגוגל, עבור הזכות לפרסם באתר יוטיוב.3. לאחר זמן מה, מפיקה הפרסומת רווחים.4. סך כל הרווחים שהופקו מהפרסומת- מתחלקים בין גוגל ובין המשתמש מעלה הסרטון, החבר, כאמור, ברשת הפרסום "גוגל אָדְסֶנס".
הגבלות ואיסורים.
השימוש ב-AdSense מותנה בעמידה במספר כללים. בעלי האתרים אינם רשאים:
הרארה
הצהרת הרארה
הצהרת הררה
דולר אמריקאני
גרנד קולי
הגרנד קוּלי (באנגלית Grand Coulee) הוא ערוץ נהר עתיק במדינת וושינגטון שבארצות הברית. אתר טבע לאומי בולט זה משתרע לאורך 100 קילומטרים דרומית מערבית מסכר גרנד קולי עד אגם סוֹאפּ (Soap Lake "אגם הסבון" בשל הקצף המיוחד שנוצר על פניו), כשהוא מחולק על ידי המפלים היבשים לגרנד קולי העליון ולגרנד קולי התחתון.
היסטוריה גאולוגית.
הגרנד קולי הוא חלק מרמת קולומביה. סלע האם של אזור זה הוא מסלע גרניט שנוצר עמוק בקרום כדור הארץ לפני 40 עד 60 מיליון שנים. הקרקע התרוממה ושקעה במהלך מיליוני שנים ועקב כך נוצרו הרים נמוכים, ובסופו של דבר ים פנימי.