מודל מרקוב חבוי

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

מודל מרקוב חבוי (Hidden Markov model; ובקיצור HMM) הוא מודל סטוכסטי המאפשר למדל מערכת כתהליך מרקובי עם מצבים חבויים (כאלו שאינם ידועים לצופה).

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

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

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

הגדרה פורמלית

ניתן להגדיר מודל מרקוב חבוי באופן הבא:

• $\{S_{1},S_{2}...S_{N}\}$ - קבוצה של N המצבים במודל.
  • נסמן $\ q_{t}$ המצב המתאים לתצפית בזמן t
• $\{\sigma _{1},\sigma _{2}...\sigma _{M}\}$ - קבוצה של M אותיות אלפבית (אותיות הפלט של המצבים)
• $A=\{a_{ij}\}$ - מטריצת הסתברויות מעבר בין מצבים, כאשר $a_{ij}=P[q_{t+1}=S_{j}|q_{t}=S_{i}]$, כלומר הסתברות מעבר ממצב i למצב j. המטריצה מגדירה הסתברויות ובהתאם צריך להתקיים $0\leq a_{ij}\leq 1$ ולכל i מתקיים: $\sum _{j}a_{ij}=1$
• $B=\{b_{i}(k)\}$ - כאשר $b_{i}(k)$ היא ההסתברות לפלט k כאשר נמצאים במצב $S_{i}$, כלומר $b_{i}(k)=P[v_{k}att|q_{t}=S_{i}]$
• $\Pi =\{\pi _{i}\}$ - כאשר $\pi _{i}$ היא ההסתברות למצב ההתחלתי $S_{i}$

בהינתן מודל עם כל הפרמטרים לעיל, ניתן להשתמש בו כדי ליצור רצף תצפיות: $\ O=o_{1},...,o_{T}$

בעיות

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

הסתברות לרצף תצפיות

בהינתן רצף תצפיות $O=o_{1},\dots ,o_{T}\,$ ובהינתן מודל עם כל הפרמטרים לעיל ניתן לחשב את ההסתברות לרצף התצפיות:

$P(O)=\sum _{X}P(O\mid X)P(X),\,$

כאשר הסכימה נעשית על כל המצבים החבויים האפשריים:

$X=q_{1},\dots ,q_{T}.\,$

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

הסתברויות למצבים חבויים

בהינתן רצף תצפיות $o_{1},\dots ,o_{T}$ ובהינתן מודל עם כל הפרמטרים לעיל אז ניתן לחשב את ההסתברויות למצבים החבויים ולענות על מספר שאלות.

• סינון - המטרה בבעיה זו היא לשערך את ההסתברות של המצב החבוי האחרון, $P(q_{T}\ |\ o_{1},\dots ,o_{T})$. ניתן למצוא פתרון לבעיה באמצעות אלגוריתם Forward.
• החלקה - המטרה בבעיה זו היא לשערך את ההסתברות למצב חבוי באמצע הרצף, כלומר $P(q_{k}\ |\ o_{1},\dots ,o_{T})$, כאשר $k<T$. אלגוריתם המבוסס גם כן על תכנון דינמי הפותר בעיה זו הוא אלגוריתם Forward-backward.
• פענוח רצף המצבים הסביר ביותר - בבעיה זו מנסים למצוא מהו רצף המצבים החבויים המסביר בצורה הטובה ביותר את רצף התצפיות לאורך כל הרצף. בעיה זו נפתרת באמצעות אלגוריתם ויטרבי.

למידה

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

דוגמה

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

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

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

מצבים = ('גשום', 'בהיר')

תצפיות = ('הליכה', 'קניות', 'ניקיון')

הסתברות התחלה = {'גשום': 0.6, 'בהיר': 0.4}

הסתברויות מעבר = {
 'גשום' : {'גשום': 0.7, 'בהיר': 0.3},
 'בהיר' : {'גשום': 0.4, 'בהיר': 0.6},
 }

הסתברויות פלט= {
 'גשום' : {'הליכה': 0.1, 'קניות': 0.4, 'ניקיון': 0.5},
 'בהיר' : {'הליכה': 0.6, 'קניות': 0.3, 'ניקיון': 0.1},
 }

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

הסתברויות מעבר מגדירות את הסתברויות לשינוי מזג האוויר בשרשרת מרקוב. בדוגמה זו, יש סיכוי של 30% בלבד שיום למחרת יום גשום יהיה בהיר. הסתברויות פלט מגדירות את נטייתו של בוב להעדיף פעילות מסוימת בהתאם למצב מזג האוויר. כאשר גשום יש סיכוי של 50% שיעסוק בניקיון; כאשר בהיר, יש סיכוי של 60% שיעשה הליכה בפארק.

תיאור גרפי של מודל מרקוב חבוי בדוגמה

קישורים חיצוניים

מדיה וקבצים בנושא מודל מרקוב חבוי בוויקישיתוף