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

ממציא	אנדרו ויטרבי
נקרא על שם	אנדרו ויטרבי

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

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

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

אלגוריתם ויטרבי מקבל כקלט רצף תצפיות ${\displaystyle Y=(y_{1},y_{2},\ldots ,y_{T})\in \{1,2,\dots ,N\}^{T}}$, ומטרתו להוציא את רצף המצבים ${\displaystyle X=(x_{1},x_{2},\ldots ,x_{T})\in S=\{s_{1},s_{2},\dots ,s_{K}\}^{T}}$ הסביר ביותר בהינתן התצפיות ${\displaystyle Y}$. בהקשר זה, ${\displaystyle T}$ הוא אורך הרצף (תצפיות ומצבים), ${\displaystyle N}$ הוא גודל מרחב התצפיות ו-${\displaystyle K}$ הוא גודל מרחב המצבים.

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

• טבלה ${\displaystyle T_{1}}$, שבה האיבר ${\displaystyle T_{1}[i,j]}$ מכיל את ההסתברות של הנתיב (רצף) הכי סביר עד כה: ${\displaystyle {\hat {X}}=({\hat {x}}_{1},{\hat {x}}_{2},\ldots ,{\hat {x}}_{j})}$.
• טבלה ${\displaystyle T_{2}}$ שבה האיבר ${\displaystyle T_{2}[i,j]}$ מכיל את ${\displaystyle {\hat {x}}_{j-1}}$ של המסלול הסביר ביותר עד כה.

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

${\displaystyle T_{1}[i,j]=\max _{k}{(T_{1}[k,j-1]\cdot A_{ki})\cdot B_{iy_{j}}}}$

${\displaystyle T_{2}[i,j]=\operatorname {argmax} _{k}{(T_{1}[k,j-1]\cdot A_{ki})}}$

כאשר ${\displaystyle A_{ki}}$ ו-${\displaystyle B_{iy_{j}}}$ מוגדרים מטה.

קלט

• מרחב התצפיות ${\displaystyle O=\{o_{1},o_{2},\dots ,o_{N}\}}$
• מרחב המצבים ${\displaystyle S=\{s_{1},s_{2},\dots ,s_{K}\}}$
• ההסתברויות ההתחלתיות ${\displaystyle \Pi =(\pi _{1},\pi _{2},\dots ,\pi _{K})}$, כך ש-${\displaystyle \pi _{i}}$ היא ההסתברות ש-${\displaystyle x_{1}==s_{i}}$
• רצף תצפיות ${\displaystyle Y=(y_{1},y_{2},\ldots ,y_{T})}$ כך ש-${\displaystyle y_{t}==i}$ אם התצפית בזמן ${\displaystyle t}$ היא ${\displaystyle o_{i}}$
• מטריצת המעברים ${\displaystyle A}$ ממימד ${\displaystyle K\cdot K}$ כך ש-${\displaystyle A_{ij}}$ היא הסתברות המעבר ממצב ${\displaystyle s_{i}}$ למצב ${\displaystyle s_{j}}$
• מטריצת הפלטים ${\displaystyle B}$ ממימד ${\displaystyle K\cdot N}$ כך ש-${\displaystyle B_{ij}}$ הוא ההסתברות לתצפית ${\displaystyle o_{j}}$ בהינתן שהמצב הוא ${\displaystyle s_{i}}$

פלט

• רצף המצבים הסביר ביותר ${\displaystyle X=(x_{1},x_{2},\ldots ,x_{N})}$

 function VITERBI${\displaystyle (O,S,\Pi ,Y,A,B):X}$
     for each state ${\displaystyle i\in \{1,2,\ldots ,K\}}$ do
         ${\displaystyle T_{1}[i,1]\leftarrow \pi _{i}\cdot B_{iy_{1}}}$
         ${\displaystyle T_{2}[i,1]\leftarrow 0}$
     end for
     for each observation ${\displaystyle i=2,3,\ldots ,T}$ do
         for each state ${\displaystyle j\in \{1,2,\ldots ,K\}}$ do
             ${\displaystyle T_{1}[j,i]\leftarrow B_{jy_{1}}\cdot \max _{k}{(T_{1}[k,i-1]\cdot A_{kj})}}$
             ${\displaystyle T_{2}[j,i]\leftarrow \arg \max _{k}{(T_{1}[k,i-1]\cdot A_{kj}})}$
         end for
     end for
     ${\displaystyle z_{T}\leftarrow \arg \max _{k}{(T_{1}[k,T])}}$
     ${\displaystyle x_{T}\leftarrow s_{z_{T}}}$
     for ${\displaystyle i\leftarrow T,T-1,\dots ,2}$  do
         ${\displaystyle z_{i-1}\leftarrow T_{2}[z_{i},i]}$
         ${\displaystyle x_{i-1}\leftarrow s_{z_{i-1}}}$
     end for
     return ${\displaystyle X}$
 end function

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

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

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