בתשובה להפונז, 02/06/24 20:30
 |
|
 |
||
|
||||
 |
לפעמים יש לך מרחב מדגם עם מבנה מסויים שלא מובן מאליו איך להגדיר עליו התפלגות אחידה, ולפעמים אתה מעוניין בהתפלגות "טיפוסית" ולא אחידה. המקרה השני הוא טכנית פחות אקראי (מבחינת אנטרופיה אל מול התפלגות אחידה על אותה קבוצה), אבל לדעתי יש במסגרתו הרבה דוגמאות שמרגישות יותר כמו משימה של הגדרת התפלגות עם תכונות מסוימות ופחות כמו הכנסת מידע לא אקראי לתהליך דגימה. הנה דוגמה נאיבית למקרה הראשון: דגימת נקודות ממעגל היחידה במישור. אפשר להגריל שני מספרים בהתפלגות אחידה מ-0 עד 1, לקחת את הנקודה שהתקבלה לפי קורדינטות קרטזיות ולנרמל אותה למקבילתה על המעגל ע"י חלוקה באורך הקטע מהראשית אליה. זה מגדיר התפלגות על המעגל, אבל היא לא אחידה1. מצד שני, אפשר להגריל מספר בהתפלגות אחידה מ-0 עד 360° (למי שלא אוהב פאי), להתייחס אליו כזווית בהצגה פולרית של נקודה באורך 1 ולקבל התפלגות אחידה על המעגל. אבני הבניין הן עדיין פונ' רנדום של פייתון, אם רוצים, אבל השימוש בהן הוא האתגר. כדוגמה למקרה השני, ובתקווה שלא הגזמתי כבר בפירוט, אני מתעסק לפעמים באלגוריתמים על גרפים והיפר-גרפים (קודקודים וקשתות2, לא ערכי פונקציה מול קלטים) וכשאני רוצה לבדוק אם משהו עובד טוב אמפירית לגרפים שאתקל בהם "בטבע", אני צריך דרך להגריל גרפים טיפוסיים. נניח שיש לי מדגם של גרפים, אני יכול (מבין הרבה אפשרויות אחרות) 1. להגריל אחיד גרפים מהמדגם. 2. להגריל גרפים עם כמות קודקודים שמתפלגת אמפירית כמו הכמות במדגם, וקשת בין כל זוג קודקודים באופן בלתי תלוי ולפי צפיפות הקשתות בגרפים במדגם. 2. לדגום אחיד גרף מהמדגם, ולערבל לו את הקשתות — לבחור הרבה פעמים זוגות קשתות בדגימה אחידה ולהצליב אותן (קודקוד אחד של קשת אחת מתחבר לקודקוד שני של קשת שניה, והשני בהתאם). 3. להשתמש בשיטה להגרלת scale free netowrks כמו Barabási-Albert model (דמיינו קישור לויקיפדיה, לא הצלחתי לפרמט אותו לפי ההוראות) עם התפלגות קודקודים כמו בדגימה. כל אחת מהדרכים מגדירה התפלגות אחרת ובעלת תכונות אחרות, ועלולה להיות טובה יותר או פחות בהתאם להתפלגות המדגם, החשיבות של דגימת דוגמאות שלא נראו, החשיבות של שימור תכונות (דרגות קודקודים, כמות קודקודים), אילוצי כח החישוב וכח מי שנאלץ לממש את שיטות הדגימה, וכו'. אמנם כולן בסופו של דבר ימומשו כסדרת קריאות לדגימה אחידה על טווחי מספרים או קבוצות סופיות, אבל יש הרבה עבודה בלבנות דברים מאבן הבניין הזאת. --- 1. אינטואיציה — הנקודות לפני נרמול נדגמו אחיד על ריבוע סביב הראשית. קחו קשת מעגל בגודל זוויתי מסויים ותזיז אותה לאורך המעגל. השטח בין הקרניים שמגדירות את הקשת והריבוע הוא הסיכוי לדגום מהקשת אחרי נרמול, אבל השטח הזה גדול יותר ככל שהקרניים מתקרבות לפינת הריבוע. 2. פעם היה אפשר לומר "רשתות" בבטחה, עכשיו המושג הזה יותר מסיח. |
 |
 |
 |
|
|
|
||
|
||||
|
תיאור יפה, אני מבין ממנו שהבעיה היא איך לגרום להתפלגות מסוימת רצויה על מרחבים שהם מטיבם "מעוותים" ולכן מאד לא ברור מלכתחילה מהי התפלגות אחידה עליהם. (יש לי אגב זכרון מאד עמום של דיון על התובנה הלא-אינטואיטיבית שהמושג "התפלגות אחידה" כשלעצמו הוא לא כל כך פשוט כמו שזה נשמע). אבל לגבי דוגמת המעגל, יש לי שאלה מכיוון אחר: אז קיבלת התפלגות שסוטה בעשרה אחוז פלוס-מינוס מהתפלגות אחידה. אז מה? ממילא בסוף אתה מריץ איזה רשת שתלמד על חמישים אחוז (נניח) מהמידע ותכוונן על חמישים אחוז אחרים. כמה זה כבר ישנה את הביצועים הסופיים שלה, התפלגות שהיא "קרובה לאחידה עד כדי אפסילון גדול-אבל-לא-עצום"? (אנקדוטה - לפני רגע המתקן האוטומטי הציע לי 'תפילין' במקום אפסילון. יש אלוהים!) |
|
|
|
|
|
|
||
|
||||
|
אנחנו במרחק תפילין אחד מאחידות! קודם אני רוצה להתחרט על הנחת היחידות של ההתפלגות האחידה בעקבות הפרדוקס לעיל. אני חושב שההתפלגות האלטרנטיבית בדוגמה מגדירה יפה מאוד מידה שהיא אחידה עבורה ולכן אפשר לקרוא לה (ולמעשה לכל התפלגות) התפלגות אחידה. לא צריך תפילין ולא הכשר מהרבנות. בכל מקרה לגבי המעגל, אולי אין בעיה רצינית, אלא אם כן התחרות קשה והרשת שלך צריכה לנצח אלטרנטיבות טובות. אם התחרות על הביצועים צמודה, האפסילון הזה במה שהגדרת כפונקציית אובדן לרשת עלול להיות משמעותי. אבל זאת דוגמה מאוד חלבית. אם אנחנו מתעסקים בהתפלגות אחידה על כדור היחידה במימדים גבוהים יותר (ורוב הזמן אנחנו מעוניינים, אם מדברים על מדעי עוזרי הסטטיסטיקאים), אז קללת המימדים שהתאפקתי מלהזכיר מקודם רלוונטית (curse_of_dimensionality [Wikipedia]). התהליך שהגדרנו מגדיר התפלגות שמרחקה מההתפלגות "האחידה" הולך וגדל עם המימד. במקרה הזה אנחנו מודעים אבל קל למצוא את עצמך חוזר על דבר כזה במרחב שהוא לא הכדור בלי לשים לב שההתפלגות שהגדרת שונה מאוד ממה שחשבת שהיא תהיה. |
|
|
|
|
|
|
||
|
||||
|
אני לא ממש עוקב אחרי הדיון ואיבדתי את ההקשר, אבל אני מחזק את המסר: דגימה אקראית (ממרחבי ההסתברות מורכבים או אפילו "מאד פשוטים" אבל בממד גבוה) היא אכן בעיה אלגוריתמית קשה (בלי קשר להיות ההסתברות אחידה או לא). תת-ענפים שלמים במדעי המחשב, למידת מכונה והסתברות מוקדשים לעניין זה בדיוק. אגב, דגימה אקראית יכולה להיות בעיה אלגוריתמית מעניינת ולא טריוויאלית גם במיקרים מאד פשוטים. למשל, הקורא הסקרן מוזמן לחשוב איך הוא היה כותב פונקציה לדגימה מתוך הסתברות דיסקרטית (בלי לקרוא ל-np.random.choice...). ההנאה מובטחת. |
|
|
|
|
|
|
||
|
||||
|
>> הקורא הסקרן מוזמן לחשוב איך הוא היה כותב פונקציה לדגימה מתוך הסתברות דיסקרטית (בלי לקרוא ל-np.random.choice...). ההנאה מובטחת. תוכל לחדד מה בדיוק המטלה? אם היא לכתוב פונקציה שמגרילה, למשל, את המספר 0 בהסתברות 0.5, את המספר 17 בהסתברות 0.4, ואת המספר 18 בהסתברות 0.1, ואם מותר להשתמש במספר אקראי מהתפלגות אחידה (רציפה) בין 0 ל-1, אז אני לא רואה מה הקושי. |
|
|
|
|
|
|
||
|
||||
|
הבנת נכון. בפירוט: בהנתן וקטור סטוכסטי באורך שרירותי, הגרל אינדקס בהתאם להסתברות שהוקטור מייצג. אתה רשאי להניח גישה להתפלגות אחידה על קטע היחידה או להתפלגות ברנולי, כרצונך (כל הנחה כזו מובילה לכיוון קצת שונה ומעניין בפני עצמו). כתבתי שזו בעיה "מעניינת ולא טריוויאלית", לא קשה :) אבל האמת היא שהיא גם לא קלה (לפחות עבורי, אני לא יכול להעיד בשמך). על מה חשבת? ארשה לעצמי לנחש: נעבור מהוקטור הנתון להתפלגות המצטברת, נגריל מספר בין 0 ל-1 (בהסתברות אחידה), ונבצע חיפוש בוקטור? אם כן זה אכן פותר את הבעיה, אבל בסיבוכיות מקום של n, סיבוכיות זמן של n לאתחול וסיבוכיות זמן של o(log(n)) לכל הגרלה. אפשר לשפר זאת משמעותית, ואז זה גם ניהיה מעניין. |
|
|
|
|
|
|
||
|
||||
|
הניחוש שלך נכון, זה הכיוון שחשבתי עליו. איך אפשר לשפר את הסיבוכיות? | |
|
|
|
|
|
||
|
||||
|
אלגוריתם אחד, שהוא בעיני לא פחות מיפהפה, מכונה בד"כ 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 משחקים בהם תפקיד מרכזי ולא תמיד צפוי גם האנטרופיה של ההסתברות, גם המימד של המרחב וגם פרטי הייצוג הנומרי של ההסתברויות עצמן. |
|
|
|
|
|
|
||
|
||||
|
אם ההסתברויות הן: 0.1, 0.29 ,0.3, 0.31 אז איך האלגוריתם הראשון עובד? |
|
|
|
|
|
|
||
|
||||
|
ההגרלה תעבוד כך: בחר אינדקס אקראי בין 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), ראה כאן. |
|
|
|
|
|
|
||
|
||||
|
(את האינדקס בחר, כמובן, בין 0 ל-3 - כולל). | |
|
|
|
|
|
||
|
||||
|
(אני מבין שהראש שלך עובד בפייתון / C, ולא ב-R / מטלאב.) ותודה על האלגוריתם, לא הכרתי. |
|
|
|
|
|
|
||
|
||||
|
תודה על ההסבר. בתגובה המקורית דובר על כך שאיברים שקיבלו "יותר מדי" (למשל האיבר הראשון שקיבל 25 במקום 10) צריכים לתרום חלק למישהו אחר. עכשיו אני רואה שלפעמים איברים שקיבלו "מעט מדי" (כמו האיבר השלישי שקיבל 25 במקום 30) צריך לתרום, אבל איכשהו זה מתקזז (האיבר השלישי תרם 4 וקיבל 9 וזה הביא את המאזן שלו ל 30). זה קצת כמו מה שקורה ב splid בשלב ההתחשבנות (רק בכיוון ההפוך). |
|
|
|
|
|
|
||
|
||||
|
זה האיזכור השני של "תפילין" בו אני נתקל היום! סימן משמיים? |
|
|
|
|
|
|
||
|
||||
|
איכשהו עלתה לי מהסיפור הזה אסוציאציה לאגדה האורבנית על הכושי במעלית שאומר "שב!" | |
|
|
|
|
|
||
|
||||
|
נדמה לי ששמעתי את זה לפני כמה עשורים בתור חוויה של ישראלי שפגש את אדי מרפי ושומרי הראש שלו במעלית. | |
|
|
|
|
|
||
|
||||
|
ואצל אחרים זה איטלקי עם מייק טייסון. זה מה שיפה בסיפורים האלה, הגנריות. |
|
|
|
|
|
|
||
|
||||
|
בשולי הדברים: אולי זאת הזדמנות טובה להזכיר שוב את ה"פרדוקס" של ברטרנד שכבר הזכרתי פעם. אם הבנתי נכון מילה או שתיים מהסינית שמעלי, הוא מציף בעיה דומה לאלה שאתם מדברים עליהן | |
|
|
|
|
|
||
|
||||
|
תודה, לא הכרתי. כדי לסדר לעצמי את המחשבות ואת אי הנוחות (עם סיכוי לתיקון ממישהו אם אני טועה): במרחבים סופיים יכול להיות קשה להגדיר תהליך דגימה שנותן התפלגות אחידה, אבל קל להגדיר את ההתפלגות האחידה — לכל איבר סיכוי שווה להדגם. במרחב מעוצמה אינסופית המקבילה היא שלכל תת-קבוצה בעלת מידה, הסיכוי של איבר ממנה להדגם הוא מידתה ביחס למידת הקבוצה המלאה. אבל אפשר להגדיר מידות שונות על אותו מרחב, ומכאן שהתפלגות אחידה תלויה לא רק בקבוצה. | |
|
|
|
|
|
||
|
||||
|
ניטפוק: אני לא חושב שהגדרת כאן "הסתברות אחידה", אלא סתם "הסתברות" (דרך נרמול מידה סופית). אני לא מכיר הגדרה כללית לגמרי ל-"הסתברות אחידה". אינטואטיבית, אולי אפשר לומר שמידת הסתברות היא אחידה אם היא מתקבלת כנרמול מידת Haar של חבורת הסימטריות של המרחב בהנחה שהכל מוגדר היטב (אבל אולי לא). | |
|
|
|
|
|
||
|
||||
|
(ההצעה הסו-קולד אינטואטיבית לעיל לא ממש מתקמפלת, אבל נראה לי שאפשר להוציא ממנה הגדרה הגיונית. לא חשוב.) | |
|
|
|
|
|
||
|
||||
|
זה מה שניסיתי לומר — לפי ההגדרה האינטואיטיבית שלנו להתפלגות אחידה (ההסתברות לדגימה מתת קבוצה פרופורציונלית לגודלה), כל התפלגות על מרחב מעוצמה אינסופית היא אחידה, אז צריך לזרוק לפח את האינטואיציה. | |
|
|
|
|
|
||
|
||||
|
זה לא נשמע לי הגיוני. התפלגות שנראית כמו גאוסיאן סביב 0 מעל הממשיים (שעוצמתם אינסופית הרי), היא לא אחידה לא באינטואיציה ולא במציאות. |
|
|
|
|
|
|
||
|
||||
|
למה לא במציאות? הגדר לכל קטע אורך לפי הפרש פונקציית ההתפלגות המצטברת של הגאוסין על קצותיו, ותשלים למידה על הממשיים. קיבלת מידה שבה הסיכוי לקבלת נקודה בקטע פרופורציונלי (ואפילו זהה) לגודלו. לא אחיד? אני חושב שמה שלא נשמע הגיוני זה מידות על הממשיים שהן לא מידת לבג. זאת באמת מידה אינטואיטיבית ומיוחסת, אז אולי אני צריך לחזור בי לגבי לזרוק את האינטואיציה לפח. ומצד שני, יש הרבה מרחבים (כולל הממשיים עצמם) עליהם אין מידה מיוחסת אינטואיטיבית שעבורה הם ממידה סופית. אז מקבלים את זה שאין כזה דבר התפלגות אחידה עליהם, לא? |
|
|
|
|
|
|
||
|
||||
|
יופי, זו הגדרה עקומה (תרתי משמע) של המידה ומאד לא אינטואיטיבית. אינטואיטיבית - זה אורך כל קטע. ועל מידה כזו ההתפלגות הזו רחוקה (עד אינסוף) מלהיות אחידה. |
|
|
|
|
|
|
||
|
||||
|
ואכן, הייתי צריך לבחור קטע סופי ולא כל הממשיים כדי לא ליפול בפח. | |
|
|
|
|
|
||
|
||||
|
קיבלתי, אתיישר. לא עולות לי בראש שום דוגמאות למרחב מדגם מעניין לצורך מעשי שאי אפשר להחיל עליו (אולי עם טיפת עבודה, כמו מעגל במישור ושיכונים אחרים) את אורכי הקטעים ממידת לבג. | |
|
|
| חזרה לעמוד הראשי |  |
| מערכת האייל הקורא אינה אחראית לתוכן תגובות שנכתבו בידי קוראים | |
 RSS מאמרים |
כתבו למערכת |
אודות האתר |
טרם התעדכנת |
ארכיון |
חיפוש |
עזרה |
תנאי שימוש
|
© כל הזכויות שמורות |