איך תסביר לדיוט הדיג את שרשרת מרקוב מונטה קרלו (MCMC)?

Question

view on stackexchange narkive permalink

אולי המושג, מדוע משתמשים בו ודוגמא.

Answer 1

view on stackexchange narkive permalink

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

$ P (\ text {למחרת הוא שמש} \, \ vert \, \ text {ניתן היום גשום)} = 0.50 $

מכיוון שמזג האוויר שלמחרת הוא שטוף שמש או גשום, נובע מכך:

$ P (\ text {למחרת הוא גשום} \, \ vert \, \ text {ניתן היום הוא גשום) } = 0.50 $

באופן דומה, בואו:

$ P (\ text {למחרת גשום} \, \ vert \, \ text {ניתן היום הוא שטוף שמש)} = 0.10 $

לפיכך, נובע מכך:

$ P (\ text {למחרת הוא שמש} \, \ vert \, \ text {ניתן היום הוא שמש)} = 0.90 $

ניתן לייצג באופן קומפקטי את ארבעת המספרים הנ"ל כמטריצת מעבר המייצגת את ההסתברויות למזג האוויר העובר ממצב אחד למצב אחר באופן הבא: } & S & R \\ S& 0.9 & 0.1 \\ R& 0.5 & 0.5 \ end {bmatrix} $

אנו עשויים לשאול מספר שאלות שתשובותיהן עוקבות:

---

ש 1: אם מזג האוויר שטוף שמש היום אז מה מזג האוויר עשוי להיות מחר?

A1: מכיוון שאיננו יודעים מה יקרה בוודאות, הכי טוב שאנו יכולים לומר הוא שיש סיכוי של 90 $ \% $ שהוא צפוי להיות שטוף שמש ו -10 $ \% $ שיהיה גשום.

---

ש 2: מה עם יומיים מהיום?

A2: חיזוי של יום אחד: $ 90 \% $ שטוף שמש, 10 $ \% $ גשום. לכן, יומיים מעכשיו:

יום ראשון יכול להיות שמש ולמחרת גם שמש. הסיכויים שזה קורה הם: $ 0.9 \ פעמים 0.9 $.

או

ביום הראשון יכול להיות גשום וביום השני יכול להיות שמש. הסיכויים שזה קורה הם: $ 0.1 \ פעמים 0.5 $.

לכן, ההסתברות שמזג האוויר יהיה שטוף שמש בעוד יומיים היא:

$ P (\ text {Sunny יומיים מעכשיו} = 0.9 \ פעמים 0.9 + 0.1 \ פעמים 0.5 = 0.81 + 0.05 = 0.86 $

באופן דומה, ההסתברות שתהיה גשם היא:

$ P (\ text {גשום בעוד יומיים} = 0.1 \ פעמים 0.5 + 0.9 \ פעמים 0.1 = 0.05 + 0.09 = 0.14 $

---

באלגברה לינארית (מטריצות מעבר) חישובים אלה תואמים את כל התמורות במעברים משלב אחד למשנהו (שטוף שמש לשמש ($ S_2S $), שטוף שמש לגשם ( $ S_2R $), גשום עד שטוף שמש ($ R_2S $) או גשום עד גשום ($ R_2R $)) עם ההסתברויות המחושבות שלהם:

בחלק התחתון של התמונה אנו רואים כיצד לחשב את ההסתברות למדינה עתידית ($ t + 1 $ או $ t + 2 $) בהתחשב בהסתברויות (פונקציית מסת הסתברות, $ PMF $) עבור כל מדינה (שטופת שמש או גשום) בזמן אפס (עכשיו או $ t_0 $) ככפל מטריצה ​​פשוט.

אם תמשיך לחזות מזג אוויר כזה תבחין שבסופו של דבר תחזית היום n $ $ יום, כאשר $ n $ גדול מאוד (נניח $ 30 $), מסתפק בהסתברויות 'שיווי משקל' הבאות:

$ P (\ text {Sunny}) = 0.833 $

ו-

$ P (\ text {Rainy}) = 0.167 $

ב- ot לדבריה, התחזית שלך ליום ה- $ n $ והיום ה- $ n + 1 $- להישאר זהה. בנוסף, תוכלו גם לבדוק שההסתברויות 'שיווי משקל' אינן תלויות במזג האוויר כיום. היית מקבל את אותה התחזית למזג האוויר אם תתחיל בהנחה שמזג האוויר היום הוא שטוף שמש או גשום.

הדוגמה שלעיל תפעל רק אם סבירות המעבר של המדינה עומדת בכמה תנאים שלא אדון בהם. פה. אך שימו לב לתכונות הבאות בשרשרת מרקוב 'נחמדה' זו (נחמד = הסתברויות מעבר מספקות תנאים):

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

שרשרת מרקוב מונטה קרלו מנצלת את התכונה הנ"ל באופן הבא:

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

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

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

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

Answer 2

view on stackexchange narkive permalink

אני חושב שיש אינטואיציה נחמדה ופשוטה להשיג מאלגוריתם מטרופוליס-הייסטינגס (שרשרת העצמאות).

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

באופן אינטואיטיבי, מה שאנחנו רוצים לעשות זה ללכת מסביב על משטח כלשהו (גושי) באופן שכמות הזמן שאנו מבלים (או # דגימות שנמשכו) בכל מיקום הוא פרופורציונלי לגובה המשטח באותו מקום. לכן, למשל, נרצה לבלות כפול זמן על ראש גבעה שנמצא בגובה 100 מטר כמו על גבעה סמוכה שנמצאת בגובה 50 מטר. הדבר הנחמד הוא שנוכל לעשות זאת גם אם איננו יודעים את הגבהים המוחלטים של הנקודות על פני השטח: כל שעלינו לדעת הם ה יחסית גבהים. למשל, אם גבעה אחת A גבוהה פי שניים מגבעה B, נרצה לבלות כפול בכמות A ממה שאנחנו מבלים ב- B.

הגרסה הפשוטה ביותר של אלגוריתם מטרופוליס-הייסטינגס (דגימת שרשרת עצמאות) משיגה זאת באופן הבא: נניח שבכל שלב זמן (דיסקרטי) אנו בוחרים מיקום אקראי חדש "מוצע" (שנבחר באופן אחיד על פני השטח כולו) . אם המיקום המוצע גבוה מהמקום בו אנו עומדים כעת, עבור אליו. אם המיקום המוצע נמוך יותר, עבור למיקום החדש עם הסתברות p, כאשר p הוא היחס בין גובה הנקודה לגובה המיקום הנוכחי. (כלומר, הפוך מטבע עם הסתברות p לקבלת ראשים; אם הוא עולה בראש, עבור למיקום החדש; אם הוא עולה בזנבות, הישאר איפה שאנחנו). ערוך רשימה של המיקומים שבהם ביקרת בכל שלב אחר זמן, ולרשימה זו יהיה (באופן אספטי) את הפרופורציה הנכונה של זמן ההשקעה בכל חלקי המשטח. (ולגבעות A ו- B שתוארו לעיל, תהיה לך סיכוי כפול לעבור מ- B ל- A כפי שיש לך לעבור מ- A ל- B).

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

לשם מה זה שימושי? נניח שיש לנו מודל הסתברותי של מזג האוויר המאפשר לנו להעריך A * P (מזג אוויר), כאשר A הוא קבוע לא ידוע. (זה קורה לעיתים קרובות - מודלים רבים נוחים לניסוח באופן שלא תוכלו לקבוע מהו A). אז אנחנו לא יכולים בדיוק להעריך את P ("גשם מחר"). עם זאת, אנו יכולים להריץ את הדגימה של MCMC לזמן מה ואז לשאול: איזה חלק מהדגימות (או "המיקומים") הגיע למצב "גשם מחר". שבר זה יהיה תחזית מזג האוויר ההסתברותית (המבוססת על מודל).

Answer 3

view on stackexchange narkive permalink

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

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

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

"אז למשל, אם אני רוצה לאמוד את ההסתברות שנורמלי תקני משתנה אקראי היה פחות מ 0.5, יכולתי לייצר עשרת אלפים מימושים עצמאיים מהתפלגות נורמלית רגילה ולספור את המספר פחות מ 0.5; נניח שקיבלתי 6905 שהיו פחות מ 0.5 מתוך 10000 דגימות סה"כ; ההערכה שלי ל- P (Z<0. 5) יהיה 0.6905, וזה לא כל כך רחוק מהערך בפועל. זו תהיה אומדן של מונטה קרלו.

"עכשיו דמיין שלא אוכל לצייר משתנים אקראיים עצמאיים נורמליים, במקום זאת הייתי מתחיל ב 0, ואז בכל שלב אוסיף מספר אקראי אחיד בין -0.5 ל 0.5 לערך הנוכחי שלי, ואז החלט על סמך בדיקה מסוימת אם אהבתי את הערך החדש הזה או לא; אם אהבתי אותו, הייתי משתמש בערך החדש כערך הנוכחי שלי, ואם לא, הייתי דוחה אותו ודבוק בערך הישן שלי. כי אני מסתכל רק על ערכים חדשים ועדכניים, זוהי שרשרת מרקוב. ​​אם אני מגדיר את הבדיקה כדי להחליט אם אני שומר את הערך החדש כראוי או לא (זה יהיה הליכה אקראית מטרופולין-הייסטינגס, והפרטים קצת מורכבים), אז למרות שאני אף פעם לא מייצר משתנה אקראי נורמלי אחד, אם אני עושה את ההליך הזה מספיק זמן, רשימת המספרים שאקבל מהנוהל תופץ כמו מספר גדול של ציורים ממשהו שיוצר משתנים אקראיים נורמליים. זה ייתן לי סימולציית שרשרת מרקוב מונטה קרלו למשתנה אקראי רגיל רגיל. אם השתמשתי בזה כדי לאמוד את עמ ' יכולות שוד, זו תהיה אומדן MCMC. "

Answer 4

view on stackexchange narkive permalink

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

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

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

Answer 5

view on stackexchange narkive permalink

בסדר הנה הניסיון הטוב ביותר שלי להסבר בלתי פורמלי וגס.

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

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

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

Answer 6

view on stackexchange narkive permalink

קטע מ שיטות Bayesian להאקרים

הנוף Bayesian

כאשר אנו קובעים בעיית היסק Bayesian עם $ N $ לא ידוע, אנו יוצרים באופן מרומז שטח ממדי $ N $ עבור ההתפלגויות הקודמות להתקיים בו. משויך למרחב הוא מימד נוסף, אותו אנו יכולים לתאר כ משטח , או עקומה שטח, המשקף את ה הסתברות קודמת של נקודה מסוימת. פני השטח מוגדרים על ידי הפצות קודמות שלנו. לדוגמא, אם יש לנו שני לא ידועים $ p_1 $ ו- $ p_2 $, ושניהם אחידים ב- [0,5], החלל שנוצר הוא הריבוע באורך 5 והמשטח הוא מישור שטוח שיושב על גבי הריבוע ( המייצג כי כל נקודה סבירה באותה מידה).

לחלופין, אם שני הקדימים הם $ \ text {Exp} (3) $ ו- $ \ text {Exp} (10) $, הרי שהחלל הוא הכל מספרים פוסטיים במישור הדו-ממדי, והמשטח המושרה על ידי הקדימים נראה כמו נפילת מים שמתחילה בנקודה (0,0) וזורמת על המספרים החיוביים.

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

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

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

העלילה משמאל היא הנוף המעוות עם $ \ text {Uniform} (0,5) $ פריור, והעלילה מימין היא הנוף המעוות עם הפריוריסטים האקספוננציאליים. הנופים האחוריים נראים שונים זה מזה. הנוף האקספוננציאלי-הקודם שם מעט מאוד משקל אחורי על הערכים בפינה הימנית העליונה: זאת מכיוון ש הקדם לא שם שם הרבה משקל ואילו הנוף הקודם האחיד שמח לשים שם משקל אחורי . כמו כן, הנקודה הגבוהה ביותר, המקבילה לאדום הכהה ביותר, מוטה כלפי (0,0) במקרה האקספוננציאלי, שהיא התוצאה מהאקספוננציאלי לפני שהכניס עוד וויג 'קודם בפינה (0,0).

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

חקר הנוף באמצעות MCMC

עלינו לחקור את המרחב האחורי המעוות שנוצר על ידי פני השטח הקודמים שלנו ונתונים נצפו כדי למצוא את רכסי ההרים האחוריים. עם זאת, איננו יכולים לחפש בחלל בתמימות: כל מדעני מחשבים יגיד לך שחציית שטח ממדי $ N $ קשה אקספוננציאלית ב- $ N $: גודל החלל מתפוצץ במהירות כאשר אנו מגדילים $ N $ (ראה קללת המימדיות). איזו תקווה יש לנו למצוא את ההרים הנסתרים האלה? הרעיון שעומד מאחורי MCMC הוא לבצע חיפוש מושכל בחלל. לומר "חיפוש" מרמז שאנחנו מחפשים אובייקט מסוים, שאולי לא תיאור מדויק של מה שעושה MCMC. כזכור: MCMC מחזיר דגימות מההפצה האחורית, ולא מההפצה עצמה. כאשר MCMC מותח את האנלוגיה ההררית שלנו, מבצע MCMC משימה הדומה לשאלה חוזרת ונשנית "עד כמה חלוק נחל זה מצאתי מההר אותו אני מחפש?", ומשלים את משימתו על ידי החזרת אלפי חלוקי נחל מקובלים בתקווה לשחזר. ההר המקורי. ב- MCMC וב- PyMC lingo, הרצף המוחזר של "חלוקי נחל" הם הדגימות, המכונות לעתים קרובות יותר עקבות .

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

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

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

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

אלגוריתמים לביצוע MCMC

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

  1. התחל במיקום הנוכחי .2. הציע לעבור לתפקיד חדש (חקור חלוק נחל בקרבתך) .3. קבל את המיקום בהתבסס על עמידת המיקום בנתונים והפצות קודמות (שאל אם חלוקי נחל הגיעו מן ההר) .4. אם אתה מקבל: עבור לתפקיד החדש. חזור לשלב 1.5. לאחר מספר גדול של חזרות, החזירו את המיקומים.  

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

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

Answer 7

view on stackexchange narkive permalink

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

הרעיון כאן הוא לנסות לקודד אלגוריתם שאוכל ללמד לאיית - לא על ידי לימוד כל מאות (אלפים? ) של כללים כמו כאשר אתה מוסיף סוף למילה שמסתיימת ב- e שקט, זרוק את e הסופי אם הסיום מתחיל בתנועה . סיבה אחת שלא תעבוד היא שאני לא מכיר את הכללים האלה (אני אפילו לא בטוח שהרגע שקראתי נכון). במקום זאת אני אלמד את זה לאיית על ידי הצגתו חבורה של מילים מאויתות כראוי ונותן לה לחלץ את הכללים מאותן מילים, וזה פחות או יותר המהות של למידת מכונה, ללא קשר לאלגוריתם - חילוץ תבניות וזיהוי תבניות .

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

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

אז קידדתי את האלגוריתם שלמטה שסרק את הרומן הזה, שלוש אותיות בכל פעם (לכל מילה יש תו אחד נוסף בסוף, שהוא 'מרחב לבן', או סוף המילה). רצפי שלוש אותיות יכולים לומר לך הרבה - למשל, את האות 'q' כמעט תמיד ואחריה 'u'; הרצף 'ty' מתרחש בדרך כלל בסוף מילה; z לעתים רחוקות עושה, וכן הלאה. (הערה: באותה מידה יכולתי להאכיל אותו במילים שלמות על מנת לאמן אותו לדבר במשפטים שלמים - בדיוק אותו רעיון, רק כמה שינויים בקוד.)

כל זה לא כרוך. אם כי MCMC, זה קורה לאחר אימון, כאשר אנו נותנים לאלגוריתם כמה אותיות אקראיות (כזרע) והוא מתחיל ליצור 'מילים'. כיצד האלגוריתם בונה מילים? תאר לעצמך שיש בו את החסימה 'קווא'; איזה מכתב זה מוסיף הבא? במהלך האימון, האלגוריתם בנה מטריצת תדרים רצפתית * * לאחר רצף * מכל אלפי המילים ברומן. איפשהו במטריצה ​​זו נמצאת גוש 'קווא' בן שלוש האותיות והתדרים עבור הדמויות שיכולות לעקוב אחר הרצף. האלגוריתם בוחר אות בהתבסס על התדרים שעלולים לעקוב אחריה. אז האות שהאלגוריתם בוחר בהמשך תלויה - ובלעדית - בשלושת האחרונים בתור בניית המלים שלו.

אז זה אלגוריתם מונטה קרלו של מרקוב שרשרת.

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

---

מעבר יחיד ברומן, Siddhartha :

then whoicks ger wiff all mothany stand ar you livid theartim mudded sullintionprehribe his sible his

(מיד, זה למד לדבר וולשית כמעט מושלמת; לא ציפיתי לזה.)

---

אחרי שניים עוברים ברומן:

The ack wor prenskinith show was a twor seened the notheady land rhatingle was the ov there

---

After 10 עובר:

למרות אבל צריך להתפלל עם ack עכשיו יש מים הכלב שלה מנוף כאב ברגליים כל אחד לא הזיכרון החלש

---

והנה הקוד (בפייתון, אני כמעט בטוח שאפשר לעשות זאת ב- R באמצעות חבילת MCMC, שיש לה כמה, תוך 3-4 שורות בלבד)

  def create_words_string (raw_string): "" "למקרה שרציתי להשתמש בנתוני אימון בצורה משפט / פיסקה; פונקציה זו תנתח מחרוזת טקסט גולמית לרשימה יפה של מילים; סינון: שמור רק על מילים שיש יותר משלוש אותיות והסר פיסוק וכו '"" "תבנית = r' \ b [A-Za-z] {3,} \ b 'pat_obj = re.compile (patt ern) מילים = [word.lower () למילה ב pat_obj.findall (raw_string)] דפוס = r '\ b [vixlm] + \ b' pat_obj = re.compile (דפוס) החזר "" .join ([מילה עבור מילה במילים אם לא pat_obj.search (word)]) def create_markov_dict (words_string): # אתחול משתנים wb1, wb2, wb3 = "", "", "" l1, l2, l3 = wb1, wb2, wb3 dx = { } עבור ch במילים_מחרוזת: dx.setdefault ((l1, l2, l3), []) .append (ch) l1, l2, l3 = l2, l3, ch return dxdef generate_newtext (markov_dict): simulated_text = "" l1, l2, l3 = "", "", "" עבור c בטווח (100): next_letter = sample (markov_dict [(l1, l2, l3)], 1) [0] simulated_text + = next_letter l1, l2, l3 = l2, l3, next_letter return simulated_textif __name __ == "__ main__": # n = מספר המעברים בטקסט האימון n = 1 q1 = create_words_string (n * raw_str) q2 = create_markov_dict (q1) q3 = generate_newtext (q2) הדפס (q3 )  

Answer 8

view on stackexchange narkive permalink

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

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

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

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

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

הטריק ל- MCMC, אם כן, הוא בחירת הליכה אקראית אשר "תבקר" בכל תוצאה עם הארוך הרצוי תדרים רצים.

דוגמה פשוטה יכולה להיות הדמיה ממודל שאומר שההסתברות לתוצאה "A" היא 0.5 ולתוצאה "B" היא 0.5. במקרה זה, אם התחלתי את ההליכה האקראית במיקום "A" וקבעתי שבכל שלב הוא עובר למצב השני עם הסתברות 0.2 (או כל הסתברות אחרת שגדולה מ- 0), הייתי יכול להיות בטוח שאחרי זמן גדול מספר הצעדים שההליכה האקראית הייתה מבקרת בכל אחד מ- "A" ו- "B" בכ- 50% מהצעדים - תואם את ההסתברויות שנקבעו על ידי המודל שלנו.

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

ניתן למצוא מאמר המכסה את היסודות של מה זה ולמה זה עובד. כאן:

http://wellredd.uk/basics-markov-chain-monte-carlo/

Answer 9

view on stackexchange narkive permalink

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

רקע: התוכנה משתמשת במטרופולין הייסטינגס MCMC ובמודל ביולוגי המדמה את ההתנהגות הידועה של פרופילי DNA (המודל בנוי על סמך נתוני אימות שנוצרו על ידי מעבדה המנתחת פרופילי DNA רבים ממצבים ידועים המייצגים את הטווח בו נתקלת בתיק הידוע הלא ידוע) . ישנן 8 שרשראות עצמאיות ואנו מעריכים את ההתכנסות כדי לקבוע אם לרוץ מחדש ולהגדיל את הצריבה והפוסט מקבל (ברירת מחדל burnin 100k מקבל ופוסט 400k מקבל)

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

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

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

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

Answer 10

view on stackexchange narkive permalink

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

סקירה אמינה ניתנת כאן

אמצא יותר זמן לפרט את תוכנו בפורמט stackexchange.

Answer 11

view on stackexchange narkive permalink

ראשית, עלינו להסביר לדיוט את דגימת מונטה-קרלו. תאר לעצמך כשאין לך את הצורה המדויקת של פונקציה (לדוגמה, $ f (x, y) = z = x ^ 2 + 2 * x * y $ span >) אבל יש מכונה באירופה (ולוס אלמוס) שמשכפלת פונקציה זו (מספרית). אנו יכולים להכניס לתוכו כמה שיותר $ (x, y) $ וזה ייתן לנו את הערך z. חזרה מספרית זו הינה דגימה ותהליך זה הוא הדמיה של מונטה-קרלו של $ f (x, y) $ . לאחר 1,0000 איטרציות, אנחנו כמעט יודעים מה הפונקציה $ f (x, y) $ .

בהנחה שהשכיבה מכירה את מונטה-קרלו, ב- MCMC אינך רוצה לבזבז את מאמצי / זמן המעבד שלך כאשר אתה מדגם ממרחב רב מימדי $ f (x , y, z, t, s, ..., zzz) $ , כפי שעושה הדגימה הרגילה של מונטה-קרלו. ההבדל העיקרי הוא שב- MCMC אתה צריך שרשרת Markov כמפה שתנחה את המאמצים שלך.

הסרטון הזה (החל מהשעה 5:50) מצהיר על אינטואיציה טובה מאוד.

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

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