בתשובה להפונז, 03/06/24 12:16
על מה יש להצטער 769204
רק לדקה • בתשובה להפונז יום ב', 3/6/2024, 15:55
אנחנו במרחק תפילין אחד מאחידות! קודם אני רוצה להתחרט על הנחת היחידות של ההתפלגות האחידה בעקבות הפרדוקס לעיל. אני חושב שההתפלגות האלטרנטיבית בדוגמה מגדירה יפה מאוד מידה שהיא אחידה עבורה ולכן אפשר לקרוא לה (ולמעשה לכל התפלגות) התפלגות אחידה. לא צריך תפילין ולא הכשר מהרבנות.

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

אבל זאת דוגמה מאוד חלבית. אם אנחנו מתעסקים בהתפלגות אחידה על כדור היחידה במימדים גבוהים יותר (ורוב הזמן אנחנו מעוניינים, אם מדברים על מדעי עוזרי הסטטיסטיקאים), אז קללת המימדים שהתאפקתי מלהזכיר מקודם רלוונטית (curse_of_dimensionality [Wikipedia]). התהליך שהגדרנו מגדיר התפלגות שמרחקה מההתפלגות "האחידה" הולך וגדל עם המימד. במקרה הזה אנחנו מודעים אבל קל למצוא את עצמך חוזר על דבר כזה במרחב שהוא לא הכדור בלי לשים לב שההתפלגות שהגדרת שונה מאוד ממה שחשבת שהיא תהיה.
על מה יש להצטער 769206
עומר • בתשובה לרק לדקה יום ב', 3/6/2024, 16:45
אני לא ממש עוקב אחרי הדיון ואיבדתי את ההקשר, אבל אני מחזק את המסר: דגימה אקראית (ממרחבי ההסתברות מורכבים או אפילו "מאד פשוטים" אבל בממד גבוה) היא אכן בעיה אלגוריתמית קשה (בלי קשר להיות ההסתברות אחידה או לא). תת-ענפים שלמים במדעי המחשב, למידת מכונה והסתברות מוקדשים לעניין זה בדיוק.

אגב, דגימה אקראית יכולה להיות בעיה אלגוריתמית מעניינת ולא טריוויאלית גם במיקרים מאד פשוטים. למשל, הקורא הסקרן מוזמן לחשוב איך הוא היה כותב פונקציה לדגימה מתוך הסתברות דיסקרטית (בלי לקרוא ל-np.random.choice...). ההנאה מובטחת.
על מה יש להצטער 769222
יובל נוב • בתשובה לעומר יום ג', 4/6/2024, 10:07
>> הקורא הסקרן מוזמן לחשוב איך הוא היה כותב פונקציה לדגימה מתוך הסתברות דיסקרטית (בלי לקרוא ל-np.random.choice...). ההנאה מובטחת.

תוכל לחדד מה בדיוק המטלה? אם היא לכתוב פונקציה שמגרילה, למשל, את המספר 0 בהסתברות 0.5, את המספר 17 בהסתברות 0.4, ואת המספר 18 בהסתברות 0.1, ואם מותר להשתמש במספר אקראי מהתפלגות אחידה (רציפה) בין 0 ל-‏1, אז אני לא רואה מה הקושי.
על מה יש להצטער 769228
עומר • בתשובה ליובל נוב יום ג', 4/6/2024, 15:43
הבנת נכון. בפירוט: בהנתן וקטור סטוכסטי באורך שרירותי, הגרל אינדקס בהתאם להסתברות שהוקטור מייצג. אתה רשאי להניח גישה להתפלגות אחידה על קטע היחידה או להתפלגות ברנולי, כרצונך (כל הנחה כזו מובילה לכיוון קצת שונה ומעניין בפני עצמו).

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

ארשה לעצמי לנחש: נעבור מהוקטור הנתון להתפלגות המצטברת, נגריל מספר בין 0 ל-‏1 (בהסתברות אחידה), ונבצע חיפוש בוקטור? אם כן זה אכן פותר את הבעיה, אבל בסיבוכיות מקום של n, סיבוכיות זמן של n לאתחול וסיבוכיות זמן של o(log(n)) לכל הגרלה. אפשר לשפר זאת משמעותית, ואז זה גם ניהיה מעניין.
על מה יש להצטער 769234
יובל נוב • בתשובה לעומר יום ג', 4/6/2024, 19:28
הניחוש שלך נכון, זה הכיוון שחשבתי עליו. איך אפשר לשפר את הסיבוכיות?
על מה יש להצטער 769262
עומר • בתשובה ליובל נוב יום ד', 5/6/2024, 13:40
אלגוריתם אחד, שהוא בעיני לא פחות מיפהפה, מכונה בד"כ Alias Method והוא מבוסס על התבנית הרעיונית של rejection sampling - רק אלגנטי פי 100 ממה שבד"כ מקבלים מהכיוון הזה. חשוב מה היה קורה אילו היינו מגרילים מהתפלגות אחידה במקום מההתפלגות הנתונה: אז אברים שהסתברותם נמוכה מ-p=1\n היו נדגמים יותר מידי, ואיברים שהסתברותם גבוהה מכך היו נדגמים פחות מידי. אפשר לקוות לתקן זאת: אם הגרלנו איבר שהסתברותו נמוכה, אז נבצע הגרלה נוספת, ובהסתברות כלשהי(?) נחזיר אותו ואחרת... נחזיר איבר אחר כלשהו? כך שהכל יסתדר?

על פניו בכלל לא ברור ששטיק כזה יכול לעבוד, אבל מסתבר שהוא עובד מושלם: אפשר תמיד להתאים לכל איבר i שהסתברותו נמוכה (ולכן סובל מדגימת-יתר) "הסתברות דחייה" p_i ואיבר אלטרנטיבי קבוע j_i שהסתברותו גבוהה (ולכן סובל מדגימת-חסר) באופן כזה שבסופו של דבר כולם נדגמים בדיוק בהסתברות המתאימה להם. את הבנייה הזו אפשר לעשות באופן מחוכם למדי ב-o(n), ואח"כ כל דגימה מבוצעת טריוויאלית בסיבוכיות זמן של o(1). האלגוריתמיקה עצמה אלגנטית‏1, אבל החיבה הגדולה שלי לאלגוריתם הזה נובעת מכך שזה בכלל עובד. ולמרות שלא נורא קשה לראות (לפחות בדיעבד) למה הוא נכון, אישית אני עדיין לא משתחרר מהתחושה שמדובר בקסם‏2.

אלגוריתם אחר, עם סיבוכיות דומה אך trade-offs שונים, שגם לו מעלות אסתטיות רבות, מבוסס על בניית סדרה של lookup-tables בהתאם לבסיס-ספירה ודיוק-עשרוני שנבחרו מראש כמתאימים לייצוג ההסתברויות הנתונות והגרלה מתוכם. יהיה קשה לתאר את הפרטים בפורמט של האייל, אבל אני מתאר לעצמי שלא תתקשה למצוא רפרנס אם תתעניין.

הפינה הזו היא האחת האטרקציות החביבות עלי בג'ונגל הגדול של האלגוריתמיקה. בין השאר בגלל שמצד אחד הבעיה עצמה כל כך פשוטה וטבעית, מצד שני הפתרונות מעניינים ויפים גם מבחינה אלגוריתמית וגם מבחינה מתמטית‏3, ומצד שלישי הם לא קשים עד כדי כך שאין להם שום שימוש (הם מאד פרקטים) או שנדרשים שנים של מאמץ כדי להתחיל להבין אותם (הם אפילו פשוטים, יחסית).

‏1 ונמצאת על סיפה של מחילת ארנב מעניינת בפני עצמה, כי הבניה אינה יחידה, ומסתבר (אני מקווה שאני זוכר נכון...) שמציאת בנייה אופטימלית היא בעיית NP קשה.
‏2 יש להודות שחלק ניכר מהאהבה שלי למתמטיקה כנראה מוסבר ע"י טפשות שמפריעה לי להבין דברים עד הסוף, כך שאני נותר תמיד עם תחושה של עיסוק באיזושהי תורת סוד מיסטית במקום בדיסציפלינה האנליטית והמכניסטית מכולן.
‏3 משחקים בהם תפקיד מרכזי ולא תמיד צפוי גם האנטרופיה של ההסתברות, גם המימד של המרחב וגם פרטי הייצוג הנומרי של ההסתברויות עצמן.
על מה יש להצטער 769265
אח של אייל • בתשובה לעומר יום ד', 5/6/2024, 15:03
אם ההסתברויות הן: 0.1, 0.29 ,0.3, 0.31
אז איך האלגוריתם הראשון עובד?
על מה יש להצטער 769269
עומר • בתשובה לאח של אייל יום ד', 5/6/2024, 16:12
ההגרלה תעבוד כך: בחר אינדקס אקראי בין 0 ל-‏1.
* אם קיבלת 0: בהסתברות 0.4 החזר 0, ואחרת החזר 3.
* אם קיבלת 1: תמיד החזר 1.
* אם קיבלת 2: בהסתברות 0.84 החזר 2, אחרת החזר 1.
* אם קיבלת 3: בהתסברות 0.64 החזר 3, אחרת החזר 2.

נבדוק:
* ההסתברות לקבל 0: 0.4*0.25 = 0.1.
* ההסתברות לקבל 1: (1-0.84)*0.25+0.25 = 0.29
* ההסתברות לקבל 2: 0.84*0.25 + (1-0.64)*0.25 = 0.3
* ההסתברות לקבל 3: 0.64*0.25 + (1-0.4)*0.25 = 0.31

אם אתה רוצה לדעת איך קיבלתי את ההסתברויות והבחירות האלטרנטיביות האלה בסיבוכיות של o(n), ראה כאן.
על מה יש להצטער 769270
עומר • בתשובה לעומר יום ד', 5/6/2024, 16:14
(את האינדקס בחר, כמובן, בין 0 ל-‏3 - כולל).
על מה יש להצטער 769271
יובל נוב • בתשובה לעומר יום ד', 5/6/2024, 17:32
(אני מבין שהראש שלך עובד בפייתון / C, ולא ב-R / מטלאב.)

ותודה על האלגוריתם, לא הכרתי.
על מה יש להצטער 769272
אח של אייל • בתשובה לעומר יום ד', 5/6/2024, 17:45
תודה על ההסבר.

בתגובה המקורית דובר על כך שאיברים שקיבלו "יותר מדי" (למשל האיבר הראשון שקיבל 25 במקום 10) צריכים לתרום חלק למישהו אחר.

עכשיו אני רואה שלפעמים איברים שקיבלו "מעט מדי" (כמו האיבר השלישי שקיבל 25 במקום 30) צריך לתרום, אבל איכשהו זה מתקזז (האיבר השלישי תרם 4 וקיבל 9 וזה הביא את המאזן שלו ל 30).

זה קצת כמו מה שקורה ב splid בשלב ההתחשבנות (רק בכיוון ההפוך).
חזרה לעמוד הראשי המאמר המלא
מערכת האייל הקורא אינה אחראית לתוכן תגובות שנכתבו בידי קוראים
האייל הקורא RSS מאמרים | כתבו למערכת | אודות האתר | טרם התעדכנת | ארכיון | חיפוש | עזרה | תנאי שימוש © כל הזכויות שמורות