דיון מקרי על אלגוריתמים הסתברותיים

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

אלגוריתם, כפי שתיארתי כאן בעבר, הוא שם כללי לתהליך חישובי “מוגדר היטב”, שבנוי מסדרת צעדים שכל אחד מהם הוא פשוט דיו כדי שיהיה ברור כיצד ניתן לבצע אותו (“הגדל את המספר הזה ב-1”; “אם שני המספרים הללו שווים, כתוב ‘כן’” וכו’). באופן כללי מטרתו של אלגוריתם היא לקחת קלט ולייצר ממנו פלט; לפוסט הזה אצטמצמם לבעיות פשוטות עוד יותר - בעיות שבהן מתקבל קלט, והפלט צריך להיות או “כן” או “לא”. אם נמשיך עם אלגוריתם מילר-רבין מהפוסט הקודם, דוגמה לכך היא אלגוריתם שמקבל מספר וצריך לומר אם הוא ראשוני או לא.

אלגוריתם הסתברותי הוא אלגוריתם שמבצע הגרלות במהלך ריצתו (יש דרך אחרת לחשוב על כך, שלפעמים היא מועילה יותר - אלגוריתם שמקבל עם תחילת ריצתו אוסף של מספרים אקראיים - אבל לא אכנס לכך כאן). אפשר לחשוב על כך בצורה מאוד פשוטה, כאלגוריתם שלפעמים מטיל מטבע ולפי התוצאה בוחר באחת משתי דרכי פעולה אפשריות. בתכנות “אמיתי” אפשר להשתמש בפונקציה rand (או משהו דומה - לרוב השפות יש פונקציה כזו כחלק מהספריה הסטנדרטית) כדי לקבל מספר אקראי ולהמשיך את החישוב על פיו (איך המספרים האקראיים הללו נוצרים כבר תיארתי בפוסט קודם). דוגמה אמיתית נתתי בפוסט הקודם - מילר-רבין מגריל מספר \( a \) שקטן מה-\( n \) שאת ראשוניותו הוא בודק, ואז משתעשע עם אותו \( a \) קצת ובסוף פולט תשובה, שתלויה ב-\( a \) שהוגרל. זו דוגמה לאלגוריתם טוב, ואני רוצה גם דוגמה לאלגוריתם גרוע, אז הנה אלגוריתם אקראי גרוע לבדיקת ראשוניות - אלגוריתם שבהינתן מספר \( n \) מטיל מטבע. אם יצא “עץ”, האלגוריתם פולט “\( n \) ראשוני”, ואחרת הוא פולט “\( n \) פריק”. זה נשמע מגוחך ואווילי, כמובן (האלגוריתם לא בדק את \( n \) בשום צורה!) אבל נשאלת השאלה - מדוע מילר-רבין הוא אלגוריתם טוב בעוד שהאלגוריתם שהצעתי גרוע? איך מודדים איכות של אלגוריתמים הסתברותיים?

בואו נבהיר קודם כל על מה אני מדבר. כשמנתחים אלגוריתמים הסתברותיים, לא מדברים על התנהגות האלגוריתם על קלט אקראי. לא אומרים דברים בסגנון “האלגוריתם ירוץ טוב על רוב הקלטים” ולא שום דבר דומה לזה. זה ההבדל שבין ניתוח של “המקרה הממוצע”, ובין ניתוח של אלגוריתם הסתברותי. הדרישה מאלגוריתם הסתברותי היא שעל כל קלט האלגוריתם ירוץ טוב, בהסתברות גבוהה. שוב, אמחיש זאת עם דוגמה רעה ודוגמה טובה. הדוגמה הרעה היא האלגוריתם הבא לבדיקת האם מספר הוא ראשוני: “בהינתן מספר \( n \), פלוט ‘המספר פריק’”. האלגוריתם הזה נשמע מטומטם לגמרי - הוא תמיד יגיד שהמספר פריק, בלי לבדוק אותו בכלל! אבל בואו נניח שהקלטים לאלגוריתם מתפלגים בצורה אחידה בין כל המספרים הטבעיים שניתנים לייצוג עם 32 סיביכות (אני מדקדק כאן בקטנות כי אין כזה דבר, “התפלגות אחידה” על כל הטבעיים) - מה ההסתברות שהאלגוריתם יענה תשובה נכונה? ובכן, גבוהה למדי; בין המספרים הטבעיים עד \( n \) יש בערך \( \frac{n}{\ln n} \) מספרים ראשוניים, ולכן ההסתברות ליפול על ראשוני היא \( \frac{1}{\ln n} \), שעבור ערכים גדולים של \( n \) הוא מספר לא גבוה כל כך - נניח, עבור מספרים בני 32 סיביות נקבל \( \ln n\approx22 \) ולכן האלגוריתם שלנו יטעה רק בפחות מ-5 אחוז מהמקרים - לא רע, נכון? אבל הבעיה היא שכשהאלגוריתם טועה, הוא טועה תמיד. ומכיוון שדווקא חמשת האחוזים של המספרים הראשוניים הם המקרים שמעניינים אותנו ביותר, אסור לנו להרשות לו לטעות תמיד עליהם. אז נחזור שוב על הנקודה - אלגוריתם הסתברותי חייב לעבוד טוב (כלומר, בהסתברות גבוהה) על כל הקלטים.

הדוגמה השנייה, ה”טובה” שלי היא של אלגוריתם המיון Quicksort (“מיון מהיר”). זמן הריצה של האלגוריתם במקרה הגרוע הוא \( O\left(n^{2}\right) \), וזהו חסם לא טוב לאלגוריתמי מיון; האלגוריתמים הנאיביים ביותר הם בעלי החסם הזה. עם זאת, ניתוח הסתברותי מראה שבמקרה הממוצע, האלגוריתם רץ בזמן \( O\left(n\log n\right) \) (שהוא זמן “כן טוב”) ובפועל הביצועים של האלגוריתם מעולים. למרבה האירוניה, הקלטים שעבורם האלגוריתם (במימוש נאיבי שלו) רץ לאט הם דווקא כאלו שבהם האיברים שאותם רוצים למיין כבר ממויינים (או קרובים מאוד לכך). אמנם, במקרה שבו כל האיברים ממויינים אפשר לגלות זאת בקלות רבה יחסית ולהמנע מהרצת אלגוריתם המיון מלכתחילה; אבל זה עדיין לא מבטיח התנהגות טובה של האלגוריתם על כל קלט.

אז מה עושים? הופכים את האלגוריתם להסתברותי בצורה פשוטה מאוד - לפני שהאלגוריתם רץ על האיברים שאותם הוא רוצה למיין, הוא מערבב אותם באופן אקראי (אני קצת משקר כאן מסיבות “פדגוגיות”). לאחר העירבוב, יש הסתברות טובה לקבל קבוצה שעליה האלגוריתם המקורי רץ מהר; ותוצאת הערבוב לא תלויה בכלל בסדר שהיה קיים בקבוצת האיברים לפני הערבוב. כלומר, לכל קבוצת איברים שהאלגוריתם רוצה למיין, יש הסתברות טובה שהערבוב שלו “יצליח” ויאפשר לו למיין את הקבוצה המעורבבת במהירות. זוהי דוגמה קלאסית לאלגוריתם הסתברותי.

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

נזכיר שאני מגביל את עצמי לדיון על אלגוריתמים שעונים “כן/לא” (מיון מהיר היה דוגמה חשובה מכדי להתעלם ממנה, אבל זה היוצא מן הכלל). מה ההסתברות לטעות שאני יכול “להרשות” לאלגוריתם? האבחנה הראשונה היא שאלגוריתמים שההסתברות שלהם לטעות גדולה מחצי ניתנים מיידית להמרה לאלגוריתמים שההסתברות שלהם לטעות היא קטנה מחצי - זהו פשוט אותו אלגוריתם, אבל שעונה תשובה הפוכה. לכן הסתברות טעות של \( \frac{1}{2} \) היא החסם התחתון בכל הנוגע לטעויות של אלגוריתמים הסתברותיים, והיא גם ההסתברות שאומרת שהאלגוריתם לא מוסיף לנו מידע - אלגוריתם “הטל מטבע, אם יצא עץ אמור כן ואחרת לא” שהזכרתי קודם הוא בעל הסתברות הצלחה כזו (לכל בעיית “כן/לא”), וזה אלגוריתם שכלל אינו מתחשב בקלט.

אם כן, אנחנו רוצים שהסתברות ההצלחה של האלגוריתם תהיה גדולה מ-\( \frac{1}{2} \). כמה גדולה? מסתבר שלא הרבה. בתורת הסיבוכיות יש הפרדה בין שתי מחלקות סיבוכיות עיקריות. הראשונה, PP (מלשון Probablistic Polynomial-time), היא אוסף הבעיות שקיים להן אלגוריתם הסתברותי יעיל (כלומר, בעל זמן ריצה פולינומי) שעל כל קלט שעבורו התשובה המתאימה היא “לא” מחזיר את התשובה הנכונה בהסתברות חצי לפחות, ועל כל קלט שהתשובה עליו היא “כן” מחזיר את התשובה הנכונה בהסתברות גדולה מחצי. כמה גדולה? אין שום דרישה על הגודל. רק שיהיה גדול מחצי. אפילו אם ככל שהקלטים הולכים וגדלים, ההסתברות לתשובה נכונה הולכת וקטנה, אבל עדיין נותרת גבוהה מחצי, אין עם זה בעיה.

הנה דוגמה לאלגוריתם PP לבדיקת פריקות של מספר: בהינתן \( n \), הגרל מספר הקטן מ-\( n \) וגדול מ-1. אם הוא מחלק את \( n \), פלוט “כן” (המספר פריק), ואחרת הטל מטבע וענה בהתאם (אם יצא “עץ”, אז פלוט “כן” ואחרת פלוט “לא”). די ברור שאם \( n \) ראשוני, ההסתברות שהאלגוריתם יפלוט “לא” היא \( \frac{1}{2} \), בגלל הטלת המטבע; ואם \( n \) פריק, אז יש לנו את ההסתברות \( \frac{1}{2} \) להגיד “כן” שמבטיחה הטלת המטבע, ועוד תוספת קטנה ואומללה להסתברות שנובעת מכך שאולי, במזל, איכשהו, נצליח להגריל מחלק של \( n \) בשלב הראשון של האלגוריתם. כלומר, PP מתארת מקרים שבהם יש לנו ולו סיכוי אפסי ואזוטרי לשפר את האמינות שלנו בעזרת הגרלה.

בפועל, אלגוריתמים כאלו אינם טובים מספיק. אנחנו לא רוצים ודאות של כמעט \( \frac{1}{2} \). לכן ל-PP יש חשיבות תיאורטית, אבל היא לא באמת נתפסת כמייצגת חישובים הסתברותיים “אמיתיים”. בשביל זה ישנה מחלקה אחרת - BPP (ה-B שנתווסף הוא בא לציין Bounded). ההגדרה המקובלת דורשת מאלגוריתם BPP לטעות בהסתברות לכל היותר \( \frac{1}{3} \) על כל קלט, אבל \( \frac{1}{3} \) הוא מספר שרירותי יחסית; כל מספר \( p<\frac{1}{2} \) היה מספיק טוב לצרכנו. אם אתם תוהים מה ההבדל בין זה ובין PP, הוא נעוץ בכך ש-\( p \) הוא קבוע ואינו תלוי בקלט; בעוד שאלגוריתם PP עשוי לטעות בהסתברויות שהולכות ומתקרבות עוד ועוד לחצי, אלגוריתם BPP אף פעם לא יעבור את החסם של \( p \). ועם זאת, על פניו גם זה לא מועיל לכלום - מה אני צריך אלגוריתם שצודק בהסתברות \( \frac{51}{100} \) בלבד? התשובה לכך היא לב-לבה של הסיבה מדוע אלגוריתמי מונטה-קרלו הם אחלה של דבר: ניפוח.

נדגים זאת על אלגוריתם מילר-רבין תחילה. אם הקלט של מילר-רבין הוא מספר ראשוני, ההסתברות שהאלגוריתם יטעה היא 0. הוא תמיד יענה את התשובה הנכונה. אם לעומת זאת הקלט הוא מספר פריק, אז יש הסתברות של \( \frac{1}{4} \) שהאלגוריתם יטעה. לאלגוריתם כמו זה, שיש לו טעות רק על סוג אחד של קלטים (במקרה הזה, אלו שצריך להחזיר עליהם תשובת “לא”), קוראים “אלגוריתם הסתברותי עם טעות חד צדדית” וגם להם יש מחלקות משל עצמם (RP ו-coRP) אבל לא ניכנס לזה - לצורך העניין, מספיק לראות שהאלגוריתם עונה לתנאים של BPP.

כעת, מה קורה אם בהינתן מספר \( n \), אני פועל באופן הבא: במקום להריץ עליו את מילר-רבין וזהו, אני מריץ עליו את מילר-רבין פעמיים. אם בשתי הפעמים מילר-רבין אמר שהמספר ראשוני, אני מקבל זאת ומתייחס למספר כאל ראשוני, אבל אם הוא אמר ולו באחת מהפעמים שהמספר פריק, אני מתייחס למספר כאל פריק. מה ההסתברות שאני טועה?

ובכן, אם המספר ראשוני, אז מילר-רבין תמיד יחזיר “ראשוני”, לא משנה כמה פעמים נריץ אותו; ולכן ההסתברות שלי לטעות היא 0. אם לעומת זאת המספר פריק, אז ההסתברות של מילר רבין להחזיר “ראשוני” בהרצה הראשונה היא \( \frac{1}{4} \); וההסתברות שלו להחזיר “ראשוני” בהרצה השנייה היא גם כן \( \frac{1}{4} \); ושתי ההרצות הללו בלתי תלויות זו בזו; וכדי שאטעה ואחשוב שהמספר ראשוני, שתי ההרצות צריכות להחזיר “ראשוני”. לכן ההסתברות שלי לטעות היא מכפלת ההסתברויות הללו - \( \frac{1}{4}\cdot\frac{1}{4}=\frac{1}{16} \). על ידי הפעלה חוזרת של האלגוריתם הצלחתי לצמצם את הסיכוי לטעות. ולא סתם לצמצם - לצמצם באופן משמעותי. אחרי \( k \) הרצות של האלגוריתם, הסיכוי שלי לטעות יהיה \( \frac{1}{4^{k}} \) - ובג’יבריש מתמטי: די בהגדלה פולינומית של מספר ההפעלות של האלגוריתם, כדי שההסתברות לטעות תדעך אקספוננציאלית. ובמילים פשוטות: בעזרת מעט הפעלות חוזרות של האלגוריתם, אני יכול לגרום לצמצום אדיר של הטעות. במקרה של מילר-רבין, אחרי ארבע הפעלות שלו ההסתברות לטעות תהיה \( \frac{1}{256} \) - פחות מאחוז אחד. עם זאת, זו עדיין לא טעות שאפשר לחיות איתה, כי היא אומרת שבערך פעם ב-256 בדיקות שאבצע, תהיה לי טעות. לכן עדיף להריץ את האלגוריתם עוד כמה וכמה פעמים - אחרי עשרים הרצות ההסתברות לטעות כבר תהיה אפסית באמת ובתמים: \( (1099511627776)^{-1} \). זה יבטיח לי שגם אם אריץ את האלגוריתם שוב ושוב כל ימי חיי, לא אצפה ממנו לבצע יותר מטעות אחת בכל אותן הרצות. זה גם האופן שבו מילר-רבין ממומש בעולם האמיתי: הוא מורץ מספר פעמים על הקלט, כשהפרנואידים יכולים להגדיל את מספר ההרצות כרצונם.

כשיש לנו אלגוריתם עם הסתברות “דו צדדית” לשגיאה, הניתוח נהיה מסובך בהרבה - במקרה זה צריך להריץ את האלגוריתם מספר רב של פעמים ולהחליט איך לענות על פי “הכרעת הרוב”. עם זאת, כדי להוכיח שההסתברות לשגיאה עדיין קטנה בקצב מהיר, כך שניתן לצמצם את השגיאה “ככל שנרצה” מבלי לפגום משמעותית בזמן הריצה של האלגוריתם - כדי לעשות זאת צריך להשתמש בעוד כלים מתמטיים (אי שוויון צ’רנוף) שלא אכנס אליהם כאן. די בכך שאגיד שזה עובד. זו הסיבה שבגללה ה-\( \frac{1}{3} \) בהגדרת BPP הוא שרירותי; אם יש לנו \( p \) אחר, הגדול מ-\( \frac{1}{3} \), די יהיה במספר לא גדול של הרצות כדי להוריד את הסתברות השגיאה של האלגוריתם אל מתחת ל-\( \frac{1}{3} \) הדרוש. זה לב ההבדל שבין BPP ובין PP; עבור אלגוריתם PP, ניפוח לא תמיד אפשרי - כלומר, הרצות חוזרות ונשנות יקטינו את ההסתברות לשגיאה, אך ייתכן שיהיה צורך ביותר מדי הרצות כדי להקטין את השגיאה אל מתחת לחסם שאנחנו מעוניינים בו, כך שהאלגוריתם ה”מנופח” כבר לא יהיה יעיל.

רק הערה לסיום. השאלה המהותית שמדעני מחשב שואלים את עצמם בכל הנוגע לאלגוריתמים הסתברותיים היא האם אלגוריתמים שכאלו באמת מוסיפים לנו כוח. כלומר, האם לא ניתן לוותר על האקראיות מבלי לפגוע באופן מהותי בזמן הריצה. בעבר, בדיקת ראשוניות היוותה אבן בוחן מעניינת לשאלה הזו, מכיוון שהיו ידועים לה אלגוריתמים הסתברותיים טובים (מילר-רבין הוא רק דוגמה אחת), אך לא היה ידוע אף אלגוריתם לא הסתברותי בעל זמן ריצה סביר שעובד בכל המקרים. בשנת 2002 פרסמו שלושה מדעני מחשב הודים את אלגוריתם AKS (על שם ראשי התיבות של שמם) שענה בדיוק להגדרות הללו והוציא את בדיקת הראשוניות מהמשחק. יתר על כן, הצורה שבה הוא עשה זאת נראית מבטיחה - האלגוריתם במקורו היה הסתברותי, אך החוקרים הצליחו לבצע לו דה-רנדומיזציה - ביטול של הצורך באקראיות על ידי הוכחה שמספיק לבצע “חיפוש ממצה” על חלק מסויים ממרחב האיברים האקראיים האפשריים. אחת מהשאלות המעניינות במדעי המחשב כיום היא האם ניתן לעשות דה-רנדומיזציה דומה לכל האלגוריתמים ה-BPP-ים, והאם קיימות בעיות שניתנות לפתרון יעיל באמצעות אלגוריתם BPP, אך לא קיים להן פתרון דטרמיניסטי יעיל. בדומה לשאלת \( \mbox{P=NP} \), הכל עדיין פתוח.