דגימת גיבס

דוגם גיבס

דגימת גיבס או דוגם גיבס (באנגלית: Gibbs sampling או Gibbs sampler) היא אלגוריתם מבוסס שרשראות מרקוב מונטה קרלו (Markov Chain Monte Carlo-MCMC) המפיק סדרת תצפיות משוערכות מתוך פונקציית הסתברות רב משתנית $p(\theta _{1},\theta _{2},...,\theta _{K})$. הפקת סדרת התצפיות מבוססת פונקציות ההסתברויות המותנות המלאות.

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

שיטה זו שימושית בעיקר כאשר:

1. קיים קושי לדגום תצפיות רב משתניות באופן סימולטני, כלומר לדגום מתוך פונקציית ההסתברות המשותפת
2. אין קושי רב לדגום מתוך פונקציות ההסתברות המותנות המלאות, כלומר מתוך קבוצת פונקציות ההסתברות של כל משתנה לחוד בהינתן ערכי שאר המשתנים $p(\theta _{k}|\theta _{1},...,\theta _{k-1},\theta _{k+1},...,\theta _{K})=p(\theta _{k},|\theta _{-k})$.

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

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

בנוסף, הדגימות הראשונות בסדרה המופקות באמצעות דגימת גיבס לרוב אינן מייצגות נכונה את ההתפלגות המשוערכת. לכן, נהוג למחוק דגימות ראשונות אלו בטרם השימוש בסדרת המספרים. הליך המחיקה קרוי בעגה המקצועית "שריפה" (Burn-in), ולמרווח הזמן מתחילת הפקת המספרים על ידי האלגוריתם עד להפקת המספר הראשון המשמש לחישוב שאינו 'נשרף' נהוג לקרוא בעגה המקצועית 'פרק זמן השריפה' (Burn in period).

האלגוריתם

נניח $\theta =(\theta _{1},\theta _{2},...,\theta _{K})$ וערך התחלתי כלשהו ${\Bigl (}\theta _{1}^{(0)},\theta _{2}^{(0)},...,\theta _{k}^{(0)}{\Bigl )}$.

דגימת גיבס מספר j היא דגימה של המשתנה הראשון מתוך פונקציית ההסתברות המותנית על כל שאר המשתנים 2 עד K שערכם הושג מהדגימה הקודמת (מספר j-1). בכתיב מתמטי זהו הביטוי:

$\theta _{1}^{(j)}\sim p{\Bigl (}\theta _{1}|\theta _{2}^{(j-1)},...,\theta _{K}^{(j-1)}{\Bigl )}$.

לאחר שהושגה דגימה j של המשתנה הראשון, יידגם המשתנה השני מתוך פונקציית ההסתברות המותנית על כל שאר המשתנים למעט 2, שערכם הושג מהדגימה הנוכחית (המשתנה הראשון) או הקודמת. בכתיב מתמטי זהו הביטוי: $\theta _{2}^{(j)}\sim p{\Bigl (}\theta _{2}|\theta _{1}^{(j)},\theta _{3}^{(j-1)},...,\theta _{K}^{(j-1)}{\Bigl )}$.

באופן דומה יידגם משתנה k כלשהו, כאשר הביטוי התואם לו הוא כדלהלן: $\theta _{k}^{(j)}\sim p{\Bigl (}\theta _{k}|\theta _{1}^{(j)},...,\theta _{k-1}^{(j)},\theta _{k+1}^{(j-1)},...,\theta _{K}^{(j-1)})$

דגימת המשתנה האחרון K עונה לביטוי:

$\theta _{k}^{(j)}\sim p{\Bigl (}\theta _{k}|\theta _{1}^{(j)},...,\theta _{K-1}^{(j)}{\Bigl )}$.

בכך הסתיימה דגימה j.

בהנחה ורצויה שרשרת דגימות באורך n, אזי יש לחזור על אופן הדגימה הגנרי שתואר לעיל עבור דגימה j, מ-j=1 עד ל-j=n.

היסטוריה

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