דגימה מהעתקה הופכית

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה לניווט קפיצה לחיפוש

דגימה מהעתקה הופכית או דגימה מטרנספורמציה הופכית (באנגלית: Inverse transform sampling, או בקיצור: ITS) היא שיטה לדגימה ממוחשבת של מספרים אקראיים מהתפלגות ידועה כלשהי, בהינתן שאנו יודעים את פונקציית ההתפלגות המצטברת שלה, ובהינתן שאנו יודעים לדגום מהתפלגות אחידה רציפה.

טרנספורמציה מדגימה מהתפלגות אחידה לדגימה מהתפלגות נורמלית
8.12589-
0.000001 4.75342-
0.005 2.5758-
0.025 1.95996-
0.5 0
0.975 1.95996
0.995 2.5758
0.999999 4.75342
8.12589
דגימה מהתפלגות הופכית עבור התפלגות נורמלית

תיאור השיטה[עריכת קוד מקור | עריכה]

פונקציה הופכית מוכללת[עריכת קוד מקור | עריכה]

תהי פונקציית ההתפלגות המצטברת (פה"מ) של ההתפלגות ממנה אנו רוצים לדגום. נגדיר את "הפונקציה ההופכית המוכללת" של , אותה נסמן ב , באופן הבא:

או במילים: הערך של עבור p הוא ה-x הקטן ביותר (אינפימום) עבורו גדול-שווה ל-p.


אם היא התפלגות רציפה, אז ההופכית המוכללת היא בדיוק הפונקציה ההופכית של , כלומר:

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

שיטת הדגימה[עריכת קוד מקור | עריכה]

בהינתן משתנה מקרי בעל התפלגות אחידה רציפה בקטע (0,1), אז הוא בעל התפלגות .

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

הקושי העיקרי הקיים בשיטה, הוא שלעיתים קשה למצוא את ההופכית המוכללת , גם כש- ידועה לנו.

דוגמאות[עריכת קוד מקור | עריכה]

התפלגות מעריכית[עריכת קוד מקור | עריכה]

דגימה מהתפלגות מעריכית עם פרמטר , באמצעות שיטת ITS. הנקודות בצבע כחול מייצגות 200 דגימות אקראיות, כשבציר ה-X מופיעים הערכים של הדגימה המקורית מהתפלגות אחידה בקטע (0,1), ובציר ה-Y הערכים ה"מתאימים" בהתפלגות המעריכית. בצבע אדום מצויר קו המייצג את הפונקציה ההופכית התאורטית.

נניח שאנו רוצים לדגום מספר מהתפלגות מעריכית עם פרמטר . הפה"מ הוא:

נמצא את הפונקציה ההופכית:

כלומר, נדגום מספר u מהתפלגות אחידה בקטע (0,1), ואז יהיה מספר אקראי מהתפלגות מעריכית עם פרמטר .

התפלגות אחידה בדידה[עריכת קוד מקור | עריכה]

נניח שאנו רוצים לדגום מספר מהתפלגות אחידה בדידה בין a ל-b. הפה"מ הוא: לכל x בקטע [a,b].

נמצא את הפונקציה ההופכית המוכללת, עבור x בקטע [a,b]:

ה- הקטן ביותר (האינפימום) המקיים אי-שוויון זה, הוא המספר השלם הקטן ביותר שאינו-קטן מ-, כלומר:

כלומר, נדגום מספר u מהתפלגות אחידה בקטע (0,1), ואז יהיה מספר אקראי מהתפלגות אחידה בדידה בין a ל-b.

ניתן לראות שהתוצאה שקיבלנו היא הגיונית, שכן עבור u קרוב מאוד ל-1 נקבל ועבור u קרוב מאוד ל-0 נקבל .

הוכחת נכונות השיטה[עריכת קוד מקור | עריכה]

על מנת להוכיח את נכונות השיטה, יש להוכיח שבהינתן התפלגות בעלת פונקציית התפלגות , ובהינתן משתנה מקרי בעל התפלגות אחידה רציפה בקטע (0,1), מתקיים: הוא משתנה מקרי בעל התפלגות .

הוכחה עבור התפלגות רציפה[עריכת קוד מקור | עריכה]

אם היא התפלגות רציפה, אז ההופכית המוכללת היא בדיוק הפונקציה ההופכית של , כלומר:

ההוכחה במקרה זה היא יחסית פשוטה; פונקציית ההתפלגות של (נסמן אותה ב-) היא:

נפעיל את (שהיא פונקציה מונוטונית-עולה) על שני צידי האי-שוויון בתוך נוסחת ההסתברות, ונקבל:

וכיוון ש- הוא משתנה אחיד סטנדרטי:

משלושת השוויונות נובע:

כלומר אכן הפה"מ של התפלגות של זהה ל-, ולכן התפלגות זהה להתפלגות .

הוכחה עבור המקרה הכללי[עריכת קוד מקור | עריכה]

שלב 1[עריכת קוד מקור | עריכה]

לכל ולכל הפונקציה ההופכית המוכללת מקיימת את 2 אי-השוויונות הבאים:

מכיוון ש- מחזירה בהכרח ערך x המקיים , מתקיים בהכרח:

1.    
שכן אחרת .

מכיוון ש- מחזירה את האינפימום על פני כל ערכי x המקיימים , מתקיים בהכרח:

2.    
שכן אחרת: כלומר היה גדול-ממש מ-x, וזה לא ייתכן כי הוא אינפימום על פני קבוצה המכילה את x.

שלב 2[עריכת קוד מקור | עריכה]

משני האי-שוויונים לעיל נובע שקבוצת ה-x-ים וה-p-ים המקיימים זהה לקבוצת ה-x-ים וה-p-ים המקיימים , כלומר:

הוכחה:

  • אם יש (x,p) השייך לקבוצה הראשונה, כלומר מקיים , אז נפעיל את הפונקציה (שהיא פונקציה מונוטונית-עולה) על שני הצדדים ונקבל: , ולפי מה שהוכחנו למעלה: , כלומר: , כלומר (x,p) שייך גם לקבוצה השנייה.
  • אם יש (x,p) השייך לקבוצה השנייה, כלומר מקיים , אז נפעיל את הפונקציה (שהיא פונקציה מונוטונית-עולה) על שני הצדדים ונקבל: , ולפי מה שהוכחנו למעלה: , כלומר: , כלומר (x,p) שייך גם לקבוצה הראשונה.

שלב 3[עריכת קוד מקור | עריכה]

המטרה שלנו היא להוכיח שפונקציית ההתפלגות של זהה לפונקציית ההתפלגות . פונקציית ההתפלגות של (נסמן אותה ב-) היא:

לפי מה שהוכחנו בשלב הקודם, מתקיים בהכרח (נציב את U במקום p):

וכיוון ש- הוא משתנה אחיד סטנדרטי:

משלושת השוויונות נובע:

כלומר אכן הפה"מ של התפלגות של זהה ל-, ולכן התפלגות זהה להתפלגות .

קישורים חיצוניים[עריכת קוד מקור | עריכה]