מודל תערובת התהליך Dirichlet

• יוני 23, 2014
• וסיליס ווריניוטיס
• . 2 תגובות

פוסט בלוג זה הוא החלק הרביעי של הסדרה ב אשכולות עם דגמי תערובת של Dirichlet. במאמרים קודמים דנו במודלים של תמצית Dirichlet Finite ולקחנו את גבול המודל שלהם לאשכולות אינסופיים k שהובילו אותנו להכנס לתהליכי Dirichlet. כפי שראינו, המטרה שלנו היא לבנות מודל תערובת שלא מחייב אותנו לציין את מספר אשכולות / הרכיבים k מההתחלה. לאחר הצגת ייצוגים שונים של תהליכי Dirichlet, הגיע הזמן להשתמש בפועל ב- DP כדי לבנות מודל תערובת אינסופי המאפשר לנו לבצע אשכולות. מטרת מאמר זה היא להגדיר את דגמי התערובת של Dirichlet תהליכים ולדון בשימוש בתהליך המסעדה הסינית ובדגימה של ג'יבס. אם לא קראתם את הפוסטים הקודמים, מומלץ מאוד לעשות זאת מכיוון שהנושא מעט תיאורטי ודורש הבנה טובה בבניית המודל.

עדכון: מסגרת הלמידה על מכונה של Datumbox היא כעת קוד פתוח וחינמית ל- להורדה. עיין בחבילה com.datumbox.framework.machinelearning.clustering כדי לראות את היישום של דגמי תערובת Dirichlet בתבנית Java.

1. הגדרת מודל תערובת Dirichlet Process

שימוש בתהליכי Dirichlet מאפשר לנו לקבל מודל תערובת עם רכיבים אינסופיים שניתן לחשוב שהוא לוקח את גבול המודל הסופי עבור k עד אינסוף. נניח שיש לנו את המודל הבא:

משוואה 1: מודל תערובת Dirichlet Process

כאשר G מוגדר כ ו משמש כציון קצר עבור שהיא פונקציית דלתא שלוקחת 1 אם ו 0 במקום אחר. ה θ_i הם פרמטרי האשכול שנדגמו מ- G. ההפצה הגנרטיבית F מוגדרת על ידי פרמטרי האשכול θ_i ומשמש לייצור x_i תצפיות. לבסוף נוכל להגדיר חלוקת צפיפות שהיא חלוקת התערובת שלנו (תערובת אינסופית לספירה) עם פרופורציות ערבוב וערבוב רכיבים .

איור 1: מודל גרפי של מודל תערובת Dirichlet

מעל אנו יכולים לראות את הדגם הגרפי המקביל של ה- DPMM. הג '₀ היא חלוקת הבסיס של DP ולרוב היא נבחרת להיות מצומדת לפני ההפצה הגנרטיבית שלנו F על מנת להקל על החישובים ולעשות שימוש בתכונות המתמטיות המושכות. ה- α הוא ההיפרפרמטר הסקלרי של תהליך Dirichlet ומשפיע על מספר האשכולות שנקבל. ככל שהערך של α גדול יותר, כך האשכולות גדולים יותר; ככל ש α קטן יותר כך פחות אשכולות. נציין כי הערך של α מבטא כוח האמונה ב- G₀. ערך גדול מצביע על כך שרוב הדגימות יהיו מובחנות ובעלות ערכים מרוכזים ב- G₀. ה- G הוא חלוקה אקראית על שטח פרמטרים Θ שנדגם מה- DP שמקצה הסתברויות לפרמטרים. ה θ_i הוא וקטור פרמטרים שנמשך מהפצת G ומכיל את הפרמטרים של האשכול, חלוקת F מוגדרת על ידי θ_i ו- x_i היא נקודת הנתונים שנוצרה על ידי הפצה Generative F.

חשוב לציין כי ה- θ_i הם אלמנטים של מרחב הפרמטרים and והם "מגדירים" את האשכולות שלנו. ניתן לראות בהם גם משתנים סמויים ב- x_i שאומרים לנו מאיזה רכיב / אשכול ה- x_i מגיע ומה הפרמטרים של רכיב זה. כך עבור כל x_i שאנו מתבוננים, אנו מציירים θ_i החלוקה G. עם כל תיקו השינויים בהתפלגות בהתאם לבחירות הקודמות. כפי שראינו בתכנית הכדיים Blackwell-MacQueen, ניתן לשלב את חלוקת ה- G ואת הבחירות העתידיות שלנו ב- θ_i תלויים רק ב- G₀: . הערכת הפרמטרים θi מהנוסחה הקודמת לא תמיד אפשרית מכיוון שהטמעות רבות (כמו תהליך המסעדה הסינית) כרוכות בספירה דרך הגדלת אקספוננציאלית של רכיבי k. כך משתמשים בשיטות חישוביות משוערות כמו דוגמת גיבס. לבסוף נציין כי אף כי אשכולות k הם אינסופיים, מספר האשכולות הפעילים הוא . כך ה- θ_i תחזור ותציג אפקט מקבץ.

2. שימוש בתהליך המסעדה הסיני כדי להגדיר מודל תערובת אינסופי

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

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

משוואה 2: מודל תערובת עם CRP

האמור לעיל הוא מודל גנראטיבי המתאר כיצד הנתונים x_i והאשכולות נוצרים. כדי לבצע את ניתוח האשכול עלינו להשתמש בתצפיות x_i ולהעריך את משימות האשכול z_i.

3. תערובת מודל תערובת ודגימה של ג'יבס

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

דגימה של ג'יבס מכווץ הוא אלגוריתם פשוט מונטה קרלו מונטה קרלו (MCMC). זה מהיר ומאפשר לנו לשלב כמה משתנים תוך דגימת משתנה אחר. עם זאת האלגוריתמים הללו מחייבים אותנו לבחור G₀ שהוא צמד לפני ההפצה הגנראטיבית F על מנת להיות מסוגל לפתור אנליטית את המשוואות ולהיות מסוגל לדגום ישירות מ .

השלבים של דגימת הגיבס מכווץ בהם אנו נשתמש בכדי להעריך את הקצאות האשכול הם:

• לאתחל את ה- z_i מטלות אשכול באופן אקראי
• חזור על הפעולה עד להתכנסות
• בחר גרזן באופן אקראי_i
  
• שמור על הז 'האחר_j קבוע לכל j ≠ i:
• הקצה ערך חדש על z_i על ידי חישוב "הסתברות CRP" התלוי ב- z_j ו- x_j מכל j ≠ i:

במאמר הבא נתמקד כיצד לבצע ניתוח אשכול באמצעות מודלים של תערובת Dirichlet Process. נגדיר שני דגמי תמהיל תהליכי Dirichlet שונים המשתמשים בתהליך המסעדה הסינית ובדגימה של הגיבס מכווץ כדי לבצע אשכולות על מערכי נתונים ומסמכים רציפים.