خوارزمية فيتربي

خوارزمية فيتربي هي خوارزمية برمجة ديناميكية تُستخدم لإيجاد التسلسل الأكثر احتمالاً للأحداث الخفية التي تُفسر سلسلة من الأحداث المرصودة. تُسمى نتيجة هذه الخوارزمية عادةً مسار فيتربي . وتُستخدم هذه الخوارزمية بشكل شائع مع نماذج ماركوف المخفية (HMMs). على سبيل المثال، إذا لاحظ طبيب أعراض مريض على مدى عدة أيام (الأحداث المرصودة)، يُمكن لخوارزمية فيتربي تحديد التسلسل الأكثر احتمالاً للحالات الصحية الكامنة (الأحداث الخفية) التي تسببت في تلك الأعراض.

وجدت هذه الخوارزمية استخدامًا واسع النطاق في فك تشفير الرموز الالتفافية المستخدمة في كلٍ من شبكات CDMA و GSM الخلوية الرقمية، وأجهزة المودم ذات الاتصال الهاتفي ، والاتصالات عبر الأقمار الصناعية، والاتصالات الفضائية، وشبكات LAN اللاسلكية 802.11 . كما تُستخدم على نطاق واسع في التعرف على الكلام ، وتوليف الكلام ، وتحديد هوية المتحدثين ، ^{[ 1 ]} واكتشاف الكلمات المفتاحية ، واللغويات الحاسوبية ، والمعلوماتية الحيوية . على سبيل المثال، في تحويل الكلام إلى نص (التعرف على الكلام)، تُمثل الإشارة الصوتية التسلسل المرصود، بينما يُمثل النص الناتج "السبب الخفي" لتلك الإشارة. وتجد خوارزمية فيتربي النص الأكثر احتمالًا بناءً على الإشارة الصوتية .

سُميت خوارزمية فيتربي نسبةً إلى أندرو فيتربي ، الذي اقترحها عام 1967 كخوارزمية لفك تشفير الرموز الالتفافية عبر روابط الاتصالات الرقمية المشوشة. ^{[ 2 ]} ومع ذلك، فقد شهدت هذه الخوارزمية تاريخًا حافلًا بالاختراعات المتعددة ، مع سبعة اكتشافات مستقلة على الأقل، بما في ذلك اكتشافات فيتربي، ونييدلمان وونش ، وواغنر وفيشر . ^{[ 3 ]} وقد تم إدخالها إلى معالجة اللغة الطبيعية كطريقة لتصنيف أجزاء الكلام في وقت مبكر من عام 1987.

أصبح مسار فيتربي وخوارزمية فيتربي مصطلحين شائعين لتطبيق خوارزميات البرمجة الديناميكية على مسائل التعظيم التي تتضمن الاحتمالات. ^{[ 3 ]} على سبيل المثال، في التحليل الإحصائي، يمكن استخدام خوارزمية البرمجة الديناميكية لاكتشاف الاشتقاق الأكثر احتمالاً (التحليل) الخالي من السياق لسلسلة نصية، والذي يُعرف عادةً باسم "تحليل فيتربي". ^{[ 4 ] [ 5 ] [ 6 ]} ومن التطبيقات الأخرى تتبع الأهداف ، حيث يتم حساب المسار الذي يُحدد أعلى احتمال لتسلسل من الملاحظات. ^{[ 7 ]}

بافتراض وجود نموذج ماركوف مخفي مع مجموعة من الحالات المخفية${\displaystyle S}$، ومجموعة من الانبعاثات (الملاحظات) المحتملة M، وتسلسل من${\displaystyle T}$الملاحظات${\displaystyle o_{0},o_{1},\dots ,o_{T-1}}$تجد خوارزمية فيتربي التسلسل الأكثر احتمالاً للحالات الخفية التي كان من الممكن أن تنتج تلك الملاحظات. في كل خطوة زمنية${\displaystyle t}$، تحل الخوارزمية المشكلة الفرعية حيث يتم فقط عرض الملاحظات حتى${\displaystyle o_{t}}$يتم أخذها في الاعتبار.

مصفوفتان من الحجم${\displaystyle T\times \left|{S}\right|}$يتم بناؤها:

• ${\displaystyle P_{t,s}}$يحتوي على أقصى احتمال للوصول إلى الحالة${\displaystyle s}$أثناء المراقبة${\displaystyle t}$، من بين جميع التسلسلات الممكنة للحالات التي تؤدي إليها.
• ${\displaystyle Q_{t,s}}$يتتبع الحالة السابقة التي تم استخدامها من قبل${\displaystyle s}$في تسلسل الحالات ذي الاحتمالية القصوى هذا.

يترك${\displaystyle \pi _{s}}$و${\displaystyle a_{r,s}}$ولتكن احتمالات البداية والانتقال على التوالي، ولتكن${\displaystyle b_{s,o}}$ليكن احتمال الملاحظة${\displaystyle o}$في الولاية${\displaystyle s}$ثم قيم${\displaystyle P}$يتم تحديدها بواسطة علاقة التكرار ^{[ 8 ]}$${\displaystyle P_{t,s}={\begin{cases}\pi _{s}\cdot b_{s,o_{t}}&{\text{إذا كان }}t=0,\\\max _{r\in S}\left(P_{t-1,r}\cdot a_{r,s}\cdot b_{s,o_{t}}\right)&{\text{إذا كان }}t>0.\end{cases}}}$$ صيغة لـ${\displaystyle Q_{t,s}}$متطابق لـ${\displaystyle t>0}$باستثناء ذلك${\displaystyle \max }$يتم استبدالها بـ${\displaystyle \arg \max }$، و${\displaystyle Q_{0,s}=0}$يمكن إيجاد مسار فيتربي عن طريق تحديد القيمة القصوى لـ${\displaystyle P}$في الخطوة الزمنية الأخيرة، وبعد ذلك${\displaystyle Q}$بالعكس.

دالة Viterbi(states, init, trans, emit, obs) تأخذ المدخلات التالية : states: S حالة مخفية ، init: الاحتمالات الأولية لكل حالة، trans: مصفوفة الانتقال S × S، emit : مصفوفة الانبعاث S × M، obs: سلسلة من T مشاهدة احتمال ← مصفوفة أصفار T × S السابق ← مصفوفة T × S فارغة لكل ولاية s في الولايات do prob[0][s] = init[s] * emit[s][obs[0]] من أجل t = 1 إلى T - 1 شاملةً، نفّذ ما يلي: // تمّت معالجة t = 0 بالفعل. لكل حالة s في مجموعة الحالات ، نفّذ ما يلي: لكل حالة r في مجموعة الحالات ، نفّذ ما يلي: new_prob ← prob[t - 1][r] * trans[r][s] * emit[s][obs[t]] إذا كانت قيمة new_prob أكبر من قيمة prob[t][s] ، prob[t][s] ← new_prob prev[t][s] ← r المسار ← مصفوفة فارغة بطول T path[T - 1] ← الحالة s ذات الاحتمالية القصوى prob[T - 1][s] من أجل t = T - 2 إلى 0 شاملةً، path[t] ← prev[t + 1][path[t + 1]] نهاية مسار العودة

التعقيد الزمني للخوارزمية هو${\displaystyle O(T\times \left|{S}\right|^{2})}$إذا عُرفت انتقالات الحالة ذات الاحتمالية غير الصفرية، فيمكن إيجاد حد محسّن من خلال التكرار على تلك الانتقالات فقط.${\displaystyle r}$والتي ترتبط بـ${\displaystyle s}$في الحلقة الداخلية. ثم باستخدام التحليل المُستهلك، يمكن إثبات أن التعقيد هو${\displaystyle O(T\times (\left|{S}\right|+\left|{E}\right|))}$، أين${\displaystyle E}$يمثل عدد الحواف في الرسم البياني، أي عدد المدخلات غير الصفرية في مصفوفة الانتقال.

يرغب الطبيب في تحديد ما إذا كان المرضى يتمتعون بصحة جيدة أم يعانون من الحمى. والمعلومات الوحيدة التي يمكن للطبيب الحصول عليها هي سؤال المرضى عن حالتهم الصحية. وقد يجيب المرضى بأنهم يشعرون بأنهم طبيعيون، أو يعانون من الدوار، أو البرد.

يُعتقد أن الحالة الصحية للمرضى تتصرف كسلسلة ماركوف منفصلة . هناك حالتان: "صحي" و"حمى"، لكن الطبيب لا يستطيع ملاحظتهما مباشرةً؛ فهما خفيتان عنه. في كل يوم، يعتمد احتمال أن يقول المريض للطبيب "أشعر أنني بخير"، أو "أشعر بالبرد"، أو "أشعر بالدوار"، على حالته الصحية في ذلك اليوم فقط.

تشكل الملاحظات (طبيعي، برد، دوار) بالإضافة إلى الحالات الخفية (صحي ، حمى) نموذج ماركوف المخفي (HMM). وبناءً على الخبرة السابقة، تم تقدير احتمالات هذا النموذج على النحو التالي:

init = {"صحي": 0.6, "حمى": 0.4} trans = { "صحي": {"صحي": 0.7، "حمى": 0.3}، "حمى": {"صحي": 0.4، "حمى": 0.6}, } انبعاث = { "صحي": {"عادي": 0.5، "زكام": 0.4، "دوار": 0.1}، "حمى": {"طبيعي": 0.1، "زكام": 0.3، "دوار": 0.6}، } 

في هذا الكود، initيُمثل اعتقاد الطبيب بشأن احتمالية تمتع المريض بصحة جيدة في البداية. تجدر الإشارة إلى أن توزيع الاحتمالات المستخدم هنا ليس توزيع التوازن، والذي يكون {'Healthy': 0.57, 'Fever': 0.43}وفقًا لاحتمالات الانتقال. transتُمثل احتمالات الانتقال تغير الحالة الصحية في سلسلة ماركوف الأساسية. في هذا المثال، تبلغ احتمالية إصابة مريض يتمتع بصحة جيدة اليوم بالحمى غدًا 30% فقط. emitتُمثل احتمالات الانبعاث مدى احتمالية كل حالة مُحتملة (طبيعية، أو نزلة برد، أو دوار) بالنظر إلى الحالة الأساسية (صحة جيدة أو حمى). تبلغ احتمالية شعور المريض السليم بصحة جيدة 50%، بينما تبلغ احتمالية شعور المريض المصاب بالحمى بالدوار 60%.

يزور مريض معين العيادة لثلاثة أيام متتالية، ويذكر أنه يشعر بأنه طبيعي في اليوم الأول، وبرد في اليوم الثاني، ودوار في اليوم الثالث.

أولاً، يتم حساب احتمالات أن يكون المريض بصحة جيدة أو مصابًا بالحمى في اليوم الأول. احتمال أن يكون المريض بصحة جيدة في اليوم الأول وأن يشعر بأنه طبيعي هو${\displaystyle 0.6\times 0.5=0.3}$وبالمثل، فإن احتمال إصابة المريض بالحمى في اليوم الأول وإبلاغه بأنه يشعر بأنه طبيعي هو${\displaystyle 0.4\times 0.1=0.04}$.

يمكن حساب احتمالات كل يوم من الأيام التالية مباشرةً من اليوم السابق. على سبيل المثال، أعلى احتمال للشعور بالصحة في اليوم الثاني والإبلاغ عن الشعور بالبرد، بعد الإبلاغ عن الشعور بالحالة الطبيعية في اليوم الأول، هو الحد الأقصى لـ${\displaystyle 0.3\times 0.7\times 0.4=0.084}$و${\displaystyle 0.04\times 0.4\times 0.4=0.0064}$وهذا يشير إلى أنه من المرجح أن المريض كان يتمتع بصحة جيدة خلال هذين اليومين، بدلاً من أن يكون مصابًا بالحمى ويتعافى.

أما باقي الاحتمالات فملخصة في الجدول التالي:

يتضح من الجدول أن المريض على الأرجح كان يعاني من الحمى في اليوم الثالث. علاوة على ذلك، توجد سلسلة من الحالات تنتهي بـ "حمى"، واحتمالية حدوث هذه الملاحظات هي 0.01512. هذه السلسلة هي تحديدًا (صحي، صحي، حمى)، ويمكن إيجادها بتتبع الحالات المستخدمة في حساب القيم القصوى (والتي تُعدّ أفضل تقدير لكل يوم، ولكنها ليست كذلك دائمًا). بعبارة أخرى، بالنظر إلى الأنشطة المرصودة، كان المريض على الأرجح بصحة جيدة في اليوم الأول، وكذلك في اليوم الثاني (على الرغم من شعوره بالبرد في ذلك اليوم)، ولم يُصب بالحمى إلا في اليوم الثالث.

يمكن تصور آلية عمل خوارزمية فيتربي باستخدام مخطط شبكي . مسار فيتربي هو في الأساس أقصر مسار عبر هذا المخطط الشبكي.

يمكن استخدام تعميم لخوارزمية فيتربي، يُسمى خوارزمية المجموع الأقصى (أو خوارزمية الضرب الأقصى )، لإيجاد التوزيع الأكثر ترجيحًا لجميع أو بعض مجموعات المتغيرات الكامنة في عدد كبير من النماذج البيانية ، مثل الشبكات البايزية ، وحقول ماركوف العشوائية ، والحقول العشوائية الشرطية . يجب أن تكون المتغيرات الكامنة، بشكل عام، متصلة بطريقة مشابهة لنموذج ماركوف المخفي ، مع عدد محدود من الروابط بين المتغيرات ونوع من البنية الخطية بينها. تتضمن الخوارزمية العامة تمرير الرسائل ، وهي مشابهة إلى حد كبير لخوارزمية نشر الاعتقاد (وهي تعميم لخوارزمية التمرير الأمامي-الخلفي ).

باستخدام خوارزمية تُسمى فك تشفير فيتربي التكراري ، يُمكن إيجاد التسلسل الفرعي للملاحظة الذي يُطابق (في المتوسط) نموذج ماركوف المخفي المُعطى على أفضل وجه. وقد اقترح هذه الخوارزمية تشي وانغ وآخرون للتعامل مع رمز التوربو . ^{[ 9 ]} يعمل فك تشفير فيتربي التكراري من خلال استدعاء خوارزمية فيتربي مُعدّلة بشكل تكراري، وإعادة تقدير درجة الحشو حتى الوصول إلى التقارب.

تم اقتراح خوارزمية بديلة، وهي خوارزمية فيتربي الكسولة. ^{[ 10 ]} في العديد من التطبيقات العملية، وفي ظل ظروف ضوضاء معقولة، يكون المُفكِّك الكسول (باستخدام خوارزمية فيتربي الكسولة) أسرع بكثير من مُفكِّك فيتربي الأصلي (باستخدام خوارزمية فيتربي). فبينما تحسب خوارزمية فيتربي الأصلية كل عقدة في شبكة النتائج المحتملة، تحتفظ خوارزمية فيتربي الكسولة بقائمة مُرتبة حسب الأولوية للعقد لتقييمها بالتسلسل، ويكون عدد العمليات الحسابية المطلوبة عادةً أقل (ولا يزيد أبدًا) من خوارزمية فيتربي العادية للحصول على النتيجة نفسها. مع ذلك، ليس من السهل موازاتها في الأجهزة.

خوارزمية فيتربي ذات المخرجات الناعمة ( SOVA ) هي نوع مختلف من خوارزمية فيتربي الكلاسيكية.

يختلف SOVA عن خوارزمية Viterbi الكلاسيكية في أنه يستخدم مقياس مسار معدل يأخذ في الاعتبار الاحتمالات المسبقة لرموز الإدخال، وينتج مخرجًا مرنًا يشير إلى موثوقية القرار.

تتمثل الخطوة الأولى في خوارزمية SOVA في اختيار مسار البقاء، الذي يمر عبر عقدة فريدة واحدة في كل لحظة زمنية t . وبما أن لكل عقدة فرعين يتقاربان عندها (حيث يتم اختيار أحد الفرعين لتشكيل مسار البقاء ، ويتم تجاهل الآخر)، فإن الفرق في مقاييس الفروع (أو التكلفة ) بين الفروع المختارة والمتجاهلة يشير إلى مقدار الخطأ في الاختيار.

يتم تجميع هذه التكلفة على كامل نافذة الانزلاق (عادة ما تساوي خمسة أطوال قيود على الأقل )، للإشارة إلى مقياس الإخراج الناعم لموثوقية قرار البت الصلب لخوارزمية فيتربي.

• خوارزمية التوقع والتعظيم
• خوارزمية باوم-ويلش
• خوارزمية التقديم والتراجع
• خوارزمية أمامية
• رمز تصحيح الأخطاء
• جهاز فك التشفير فيتربي
• تحديد أجزاء الكلام
• خوارزمية البحث A*

• فيتربي، أ. ج. (أبريل 1967). "حدود الخطأ للرموز الالتفافية وخوارزمية فك تشفير مثالية تقاربياً". معاملات IEEE في نظرية المعلومات . 13 (2): 260-269 . doi : 10.1109/TIT.1967.1054010 .(ملاحظة: تم وصف خوارزمية فك التشفير فيتربي في القسم الرابع.) الاشتراك مطلوب.
• فيلدمان ج، أبو فيصل إ، فريجو م (2002). "مفكك تشفير سريع ذو احتمالية قصوى للرموز الالتفافية". وقائع المؤتمر السادس والخمسين لتقنيات المركبات التابع لمعهد مهندسي الكهرباء والإلكترونيات . المجلد  1. الصفحات 371-375 . CiteSeerX 10.1.1.114.1314 . doi : 10.1109/VETECF.2002.1040367 . ISBN   978-0-7803-7467-6. S2CID 9783963 . 
• فورني، جي دي (مارس 1973). "خوارزمية فيتربي". وقائع معهد مهندسي الكهرباء والإلكترونيات . 61 (3): 268-278 . doi : 10.1109/PROC.1973.9030 .الاشتراك مطلوب.
• بريس، دبليو إتش؛ تيوكولسكي، إس إيه؛ فيترلينغ، دبليو تي؛ فلانيري، بي بي (2007). "القسم 16.2. فك تشفير فيتربي" . وصفات عددية: فن الحوسبة العلمية (  الطبعة الثالثة). نيويورك: مطبعة جامعة كامبريدج. ISBN 978-0-521-88068-8أُرشف من المصدر الأصلي بتاريخ 11 أغسطس 2011. تم الاطلاع عليه بتاريخ 17 أغسطس 2011 .
• رابينر، ل. ر. (فبراير 1989). "دليل تعليمي حول نماذج ماركوف المخفية وتطبيقات مختارة في التعرف على الكلام". وقائع معهد مهندسي الكهرباء والإلكترونيات . 77 (2): 257-286 . CiteSeerX 10.1.1.381.3454 . doi : 10.1109/5.18626 . S2CID 13618539 .  (يصف خوارزمية التقديم الأمامي وخوارزمية فيتربي لنماذج ماركوف المخفية).
• Shinghal, R. and Godfried T. Toussaint , “Experiments in text recognition with the modified Viterbi algorithm,” IEEE Transactions on Pattern Analysis and Machine Intelligence , Vol. PAMI-l, April 1979, pp.  184–193.
• شينغال، ر. وغودفريد ت. توسان ، "حساسية خوارزمية فيتربي المعدلة لإحصائيات المصدر"، معاملات IEEE في تحليل الأنماط والذكاء الآلي ، المجلد PAMI-2، مارس 1980، ص  181-185.

• التطبيقات في Java وF# وClojure وC# على Wikibooks
• شرحٌ مبسطٌ للترميز التلافيفي مع فك ترميز فيتربي، بقلم تشيب فليمنج
• دليل تعليمي لمجموعة أدوات نموذج ماركوف المخفي (مُنفذة بلغة C) يتضمن وصفًا لخوارزمية فيتربي
• خوارزمية فيتربي للدكتور أندرو جيه فيتربي (scholarpedia.org).