הצגת המקור של הדף "מודל מרקוב חבוי"

[[קובץ:HiddenMarkovModel.svg|260px|ממוזער|מודל מרקוב חבוי: העיגולים בשורה העליונה (x) מציינים מצבים נסתרים מעיני הצופה, הריבועים בשורה התחתונה מציינים אותיות הפלט (y), החצים המסומנים ב-a מציינים הסתברויות מעבר בין מצבים וכאלו המסומנים ב-b מייצגים הסתברות לפלט]]
'''מודל מרקוב חבוי''' (Hidden Markov model; ובקיצור '''HMM''') הוא מודל [[תהליך סטוכסטי|סטוכסטי]] המאפשר למדל מערכת כ[[תהליך מרקובי]] עם מצבים חבויים (כאלו שאינם ידועים לצופה).

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

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

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

==הגדרה פורמלית==
ניתן להגדיר מודל מרקוב חבוי באופן הבא:{{הערה|{{cite journal |author=[[Lawrence Rabiner|Lawrence R. Rabiner]] |title=A tutorial on Hidden Markov Models and selected applications in speech recognition |journal=Proceedings of the [[IEEE]] |volume=77 |issue=2 |pages=257–286 |date=February 1989 |url=http://www.ece.ucsb.edu/Faculty/Rabiner/ece259/Reprints/tutorial%20on%20hmm%20and%20applications.pdf |doi=10.1109/5.18626}} [http://www.cs.cornell.edu/courses/cs481/2004fa/rabiner.pdf]}}
* <math>\{ S_1, S_2... S_N \}</math> - קבוצה של N המצבים במודל.
**נסמן <math>\ q_t</math> המצב המתאים לתצפית בזמן t
*<math>\{ \sigma_1, \sigma_2... \sigma_M \}</math> - קבוצה של M אותיות אלפבית (אותיות הפלט של המצבים)
*<math>A =\{ a_{ij} \}</math> - מטריצת הסתברויות מעבר בין מצבים, כאשר <math>a_{ij}=P[q_{t+1}=S_j|q_t=S_i]</math>, כלומר [[הסתברות]] מעבר ממצב i למצב j. המטריצה מגדירה הסתברויות ובהתאם צריך להתקיים <math>0 \leq a_{ij} \leq 1</math> ולכל i מתקיים: <math>\sum_j a_{ij}=1</math>
* <math>B =\{ b_i(k) \}</math> - כאשר <math>b_i(k)</math> היא ההסתברות לפלט k כאשר נמצאים במצב <math>S_i</math>, כלומר <math>b_i(k)=P[v_k at t|q_t=S_i]</math>
* <math>\Pi = \{ \pi_i \}</math> - כאשר <math> \pi_i</math> היא ההסתברות למצב ההתחלתי <math>S_i</math>

בהינתן מודל עם כל הפרמטרים לעיל, ניתן להשתמש בו כדי ליצור רצף תצפיות:
<math>\ O = o_1 ,..., o_T </math>

==בעיות==
באמצעות מודל מרקוב חבוי ניתן לענות על מספר שאלות בנוגע לרצף תצפיות, וכאשר נעשה שימוש ב[[תכנון דינמי]] ניתן לחשב להן ביעילות פתרון.
===הסתברות לרצף תצפיות===
בהינתן רצף תצפיות <math>O=o_1,\dots,o_T\,</math> ובהינתן מודל עם כל הפרמטרים לעיל ניתן לחשב את ההסתברות לרצף התצפיות:
:<math>P(O)=\sum_{X}P(O\mid X)P(X),\,</math>
כאשר הסכימה נעשית על כל המצבים החבויים האפשריים:
: <math>X=q_1, \dots, q_T.\,</math>
אלגוריתם Forward הוא אלגוריתם מבוסס תכנון דינמי הפותר בעיה זו.

===הסתברויות למצבים חבויים===
בהינתן רצף תצפיות <math>o_1,\dots,o_T</math> ובהינתן מודל עם כל הפרמטרים לעיל אז ניתן לחשב את ההסתברויות למצבים החבויים ולענות על מספר שאלות.
*סינון - המטרה בבעיה זו היא לשערך את ההסתברות של המצב החבוי האחרון, <math>P(q_T\ |\ o_1,\dots,o_T)</math>. ניתן למצוא פתרון לבעיה באמצעות אלגוריתם Forward.
*החלקה - המטרה בבעיה זו היא לשערך את ההסתברות למצב חבוי באמצע הרצף, כלומר <math>P(q_k\ |\ o_1,\dots,o_T)</math>, כאשר <math>k < T</math>. אלגוריתם המבוסס גם כן על תכנון דינמי הפותר בעיה זו הוא אלגוריתם Forward-backward.
*פענוח רצף המצבים הסביר ביותר - בבעיה זו מנסים למצוא מהו רצף המצבים החבויים המסביר בצורה הטובה ביותר את רצף התצפיות לאורך כל הרצף. בעיה זו נפתרת באמצעות [[אלגוריתם ויטרבי]].

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

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

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

לאליס יש מושג כללי על מזג האוויר והיא יודעת פחות או יותר מה בוב נוהג לעשות, ועל פי המידע הנ"ל ניתן להגדיר את הפרמטרים של מודל מרקוב חבוי כדלקמן (מתואר בתחביר [[Python]]):
<syntaxhighlight dir="rtl" lang="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},
 }
</syntaxhighlight>
בדוגמה לעיל <code>הסתברויות התחלה</code> (או <math>\Pi </math>) מייצגים את אמונה של אליס באשר למצב מזג האוויר ביום הראשון שבוב מתקשר אליה (מזג האוויר נוטה יותר לגשום).

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

[[קובץ:HMMGraph.svg|border|מרכז|400px|תיאור גרפי של מודל מרקוב חבוי בדוגמה]]

==קישורים חיצוניים==
{{ויקישיתוף בשורה}}

==הערות שוליים==
{{הערות שוליים|יישור=שמאל}}

{{בקרת זהויות}}

[[קטגוריה:מודלים מרקוביים]]