אלגוריתם ויטרבי

{{#invoke:ParamValidator|validateparams|module_options=יחידה:PV-options}} {{#invoke:תבנית מידע|מידע| | טבלה-עיצוב = width: 22em; font-size: 95%; | כותרת תבנית-עיצוב =background: #B2C6FF; border:1px solid #aaaaaa; border-bottom:0px; | כותרת-עיצוב = background: #B2C6FF; | תמונה = | כיתוב= | תווית-מידע10=מחלקה | תווית-מידע20=סוג | תווית-מידע30=מבנה נתונים | תווית-מידע40=סיבוכיות זמן |סיבוכיות זמן-ויקינתונים=P3752 | תווית-מידע50=סיבוכיות מקום |סיבוכיות מקום-ויקינתונים=P3755 | תווית-מידע60=ממציא |ממציא-ויקינתונים-מרובה=P61 |ממציא-ויקינתונים-פרטים=P577 | תווית-מידע70=נקרא על שם |נקרא על שם-ויקינתונים-מרובה=P138 | תווית-מידע80=הומצא |הומצא-ויקינתונים=P575

}}

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

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

היסטוריה

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

פסאודו-קוד

אלגוריתם ויטרבי מקבל כקלט רצף תצפיות $Y=(y_1,y_2,\dots ,y_T)\in \{1,2,\dots ,N{\}}^T$, ומטרתו להוציא את רצף המצבים $X=(x_1,x_2,\dots ,x_T)\in S=\{s_1,s_2,\dots ,s_K{\}}^T$ הסביר ביותר בהינתן התצפיות $Y$. בהקשר זה, $T$ הוא אורך הרצף (תצפיות ומצבים), $N$ הוא גודל מרחב התצפיות ו-$K$ הוא גודל מרחב המצבים.

במהלך פעולתו, האלגוריתם משתמש בשתי טבלאות בגודל $K\times T$:

• טבלה $T_1$, שבה האיבר $T_1[i,j]$ מכיל את ההסתברות של הנתיב (רצף) הכי סביר עד כה: $\hat{X}=({\hat{x}}_1,{\hat{x}}_2,\dots ,{\hat{x}}_j)$.
• טבלה $T_2$ שבה האיבר $T_2[i,j]$ מכיל את ${\hat{x}}_{j-1}$ של המסלול הסביר ביותר עד כה.

האלגוריתם ממלא את הטבלאות לפי סדר עולה של $K\cdot j+i$, ולפי הנוסחאות הרקורסיביות:

$T_1[i,j]=\underset{k}{\max }(T_1[k,j-1]\cdot A_{ki})\cdot B_{i{y}_j}$

$T_2[i,j]={\mathrm{argmax}}_k(T_1[k,j-1]\cdot A_{ki})$

כאשר $A_{ki}$ ו-$B_{i{y}_j}$ מוגדרים מטה.

קלט

• מרחב התצפיות $O=\{o_1,o_2,\dots ,o_N\}$
• מרחב המצבים $S=\{s_1,s_2,\dots ,s_K\}$
• ההסתברויות ההתחלתיות $\mathrm{\Pi }=({\pi }_1,{\pi }_2,\dots ,{\pi }_K)$, כך ש-${\pi }_i$ היא ההסתברות ש-$x_1==s_i$
• רצף תצפיות $Y=(y_1,y_2,\dots ,y_T)$ כך ש-$y_t==i$ אם התצפית בזמן $t$ היא $o_i$
• מטריצת המעברים $A$ ממימד $K\cdot K$ כך ש-$A_{ij}$ היא הסתברות המעבר ממצב $s_i$ למצב $s_j$
• מטריצת הפלטים $B$ ממימד $K\cdot N$ כך ש-$B_{ij}$ הוא ההסתברות לתצפית $o_j$ בהינתן שהמצב הוא $s_i$

פלט

• רצף המצבים הסביר ביותר $X=(x_1,x_2,\dots ,x_N)$

 function VITERBI$(O,S,\mathrm{\Pi },Y,A,B):X$
     for each state $i\in \{1,2,\dots ,K\}$ do
         $T_1[i,1]\leftarrow {\pi }_i\cdot B_{i{y}_1}$
         $T_2[i,1]\leftarrow 0$
     end for
     for each observation $i=2,3,\dots ,T$ do
         for each state $j\in \{1,2,\dots ,K\}$ do
             $T_1[j,i]\leftarrow B_{j{y}_1}\cdot \underset{k}{\max }(T_1[k,i-1]\cdot A_{kj})$
             $T_2[j,i]\leftarrow \arg \underset{k}{\max }(T_1[k,i-1]\cdot A_{kj})$
         end for
     end for
     $z_T\leftarrow \arg \underset{k}{\max }(T_1[k,T])$
     $x_T\leftarrow s_{z_T}$
     for $i\leftarrow T,T-1,\dots ,2$  do
         $z_{i-1}\leftarrow T_2[z_i,i]$
         $x_{i-1}\leftarrow s_{z_{i-1}}$
     end for
     return $X$
 end function

סיבוכיות האלגוריתם היא $O(T\times {\left|S\right|}^2)$.

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

• מימושים ב-Java, C#, ועוד באתר wikibooks.
• הסבר מפורטתבנית:קישור שבור על האלגוריתם בהקשרי קודי קונבולוציה
• ההיסטוריה של האלגוריתם - מאת David Forney