خوارزمية التقديم والتراجع

خوارزمية التقديم والتراجع هي خوارزمية استدلال لنماذج ماركوف المخفية، تقوم بحساب التوزيعات الهامشية اللاحقة لجميع متغيرات الحالة المخفية بالنظر إلى سلسلة من الملاحظات/الانبعاثات.${\displaystyle o_{1:T}:=o_{1},\dots ,o_{T}}$أي أنه يحسب، لجميع متغيرات الحالة المخفية${\displaystyle X_{t}\in \{X_{1},\dots ,X_{T}\}}$، التوزيع${\displaystyle P(X_{t}\ |\ o_{1:T})}$تُعرف مهمة الاستدلال هذه عادةً باسم التنعيم . تستخدم الخوارزمية مبدأ البرمجة الديناميكية لحساب القيم المطلوبة بكفاءة للحصول على التوزيعات الهامشية اللاحقة في مرحلتين. المرحلة الأولى تتقدم زمنيًا بينما الثانية تتراجع زمنيًا؛ ومن هنا جاء اسم خوارزمية التقدم والتراجع .

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

في المرحلة الأولى، تحسب خوارزمية التمرير الأمامي-الخلفي مجموعة من الاحتمالات الأمامية التي توفر، لجميع${\displaystyle t\in \{1,\dots ,T\}}$، احتمال الوصول إلى أي حالة معينة بالنظر إلى الحالة الأولى${\displaystyle t}$الملاحظات في التسلسل، أي${\displaystyle P(X_{t}\ |\ o_{1:t})}$في المرحلة الثانية، تحسب الخوارزمية مجموعة من الاحتمالات العكسية التي توفر احتمالية رصد المشاهدات المتبقية بالنظر إلى أي نقطة بداية.${\displaystyle t}$، أي${\displaystyle P(o_{t+1:T}\ |\ X_{t})}$ويمكن بعد ذلك دمج مجموعتي التوزيعات الاحتمالية هاتين للحصول على التوزيع على الحالات في أي نقطة زمنية محددة بالنظر إلى سلسلة الملاحظات الكاملة:

${\displaystyle P(X_{t}\ |\ o_{1:T})=P(X_{t}\ |\ o_{1:t},o_{t+1:T})\propto P(o_{t+1:T}\ |\ X_{t})P(X_{t}|o_{1:t})}$

وتنتج الخطوة الأخيرة عن تطبيق قاعدة بايز والاستقلال الشرطي لـ${\displaystyle o_{t+1:T}}$و${\displaystyle o_{1:t}}$منح${\displaystyle X_{t}}$.

كما هو موضح أعلاه، تتضمن الخوارزمية ثلاث خطوات:

1. حساب الاحتمالات الأمامية
2. حساب الاحتمالات العكسية
3. حساب القيم المُعدّلة.

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

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

سيستخدم الوصف التالي مصفوفات قيم الاحتمالات بدلاً من توزيعات الاحتمالات. ومع ذلك، يمكن تطبيق خوارزمية التقديم والتراجع بشكل عام على نماذج الاحتمالات المستمرة والمتقطعة.

نقوم بتحويل التوزيعات الاحتمالية المتعلقة بنموذج ماركوف المخفي المعطى إلى ترميز المصفوفات كما يلي. احتمالات الانتقال${\displaystyle \mathbf {P} (X_{t}\mid X_{t-1})}$لمتغير عشوائي معين${\displaystyle X_{t}}$سيتم تمثيل جميع الحالات الممكنة في نموذج ماركوف المخفي بواسطة المصفوفة${\displaystyle \mathbf {T} }$حيث فهرس العمود${\displaystyle j}$سيمثل الحالة المستهدفة وفهرس الصف${\displaystyle i}$يمثل حالة البداية. انتقال من حالة متجه الصف${\displaystyle \mathbf {\pi _{t}} }$إلى حالة متجه الصف المتزايدة${\displaystyle \mathbf {\pi _{t+1}} }$تُكتب على النحو التالي:${\displaystyle \mathbf {\pi _{t+1}} =\mathbf {\pi _{t}} \mathbf {T} }$يمثل المثال أدناه نظامًا تبلغ فيه احتمالية البقاء في الحالة نفسها بعد كل خطوة 70%، بينما تبلغ احتمالية الانتقال إلى الحالة الأخرى 30%. وبالتالي، تكون مصفوفة الانتقال كما يلي:

${\displaystyle \mathbf {T} ={\begin{pmatrix}0.7&0.3\\0.3&0.7\end{pmatrix}}}$

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

${\displaystyle \mathbf {B} ={\begin{pmatrix}0.9&0.1\\0.2&0.8\end{pmatrix}}}$

يُحدد هذا الاحتمال احتمالات رصد الأحداث في حالة معينة. في المثال أعلاه، سيتم رصد الحدث 1 بنسبة 90% إذا كنا في الحالة 1، بينما تبلغ احتمالية وقوع الحدث 2 في هذه الحالة 10%. في المقابل، سيتم رصد الحدث 1 بنسبة 20% فقط إذا كنا في الحالة 2، وتبلغ احتمالية وقوع الحدث 2 في هذه الحالة 80%. بافتراض وجود متجه صفّي عشوائي يصف حالة النظام (${\displaystyle \mathbf {\pi } }$)، وبالتالي فإن احتمال رصد الحدث j هو:

${\displaystyle \mathbf {P} (O=j)=\sum _{i}\pi _{i}B_{i,j}}$

يمكن تمثيل احتمالية أن تؤدي حالة معينة إلى الحدث المرصود j في شكل مصفوفة عن طريق ضرب متجه صف الحالة (${\displaystyle \mathbf {\pi } }$) مع مصفوفة الملاحظة (${\displaystyle \mathbf {O_{j}} =\mathrm {diag} (B_{*,o_{j}})}$) تحتوي على عناصر قطرية فقط. وبالاستمرار في المثال السابق، ستكون مصفوفة الملاحظات للحدث 1 كما يلي:

${\displaystyle \mathbf {O_{1}} ={\begin{pmatrix}0.9&0.0\\0.0&0.2\end{pmatrix}}}$

وهذا يسمح لنا بحساب متجه الحالة الجديد للاحتمالات غير المعيارية${\displaystyle \mathbf {\pi '} }$من خلال قاعدة بايز، يتم ترجيح كل عنصر من عناصر${\displaystyle \mathbf {\pi } }$الحدث المُنشأ رقم 1 كالتالي:

${\displaystyle \mathbf {\pi '} =\mathbf {\pi } \mathbf {O_{1}} }$

يمكننا الآن جعل هذا الإجراء العام خاصًا بسلسلة ملاحظاتنا. بافتراض متجه حالة ابتدائي${\displaystyle \mathbf {\pi } _{0}}$، (والتي يمكن تحسينها كمعامل من خلال تكرار إجراء التقديم والتراجع)، نبدأ بـ${\displaystyle \mathbf {f_{0:0}} =\mathbf {\pi } _{0}}$ثم تحديث توزيع الحالة وترجيحها بناءً على احتمالية الملاحظة الأولى:

${\displaystyle \mathbf {f_{0:1}} =\mathbf {\pi } _{0}\mathbf {T} \mathbf {O_{o_{1}}} }$

يمكن مواصلة هذه العملية بإجراء ملاحظات إضافية باستخدام:

${\displaystyle \mathbf {f_{0:t}} =\mathbf {f_{0:t-1}} \mathbf {T} \mathbf {O_{o_{t}}} }$

هذه القيمة هي متجه الاحتمالية غير المعياري الأمامي . العنصر رقم i من هذا المتجه يُعطي ما يلي:

${\displaystyle \mathbf {f_{0:t}} (i)=\mathbf {P} (o_{1},o_{2},\dots ,o_{t},X_{t}=x_{i}|\mathbf {\pi } _{0})}$

عادةً، نقوم بتطبيع متجه الاحتمالية في كل خطوة بحيث يكون مجموع عناصره مساوياً لـ 1. وبالتالي، يتم إدخال عامل قياس في كل خطوة بحيث:

${\displaystyle \mathbf {{\hat {f}}_{0:t}} =c_{t}^{-1}\ \mathbf {{\hat {f}}_{0:t-1}} \mathbf {T} \mathbf {O_{o_{t}}} }$

أين${\displaystyle \mathbf {{\hat {f}}_{0:t-1}} }$يمثل المتجه المُقاس من الخطوة السابقة و${\displaystyle c_{t}}$يمثل عامل القياس الذي يجعل مجموع عناصر المتجه الناتج يساوي 1. حاصل ضرب عوامل القياس هو الاحتمال الكلي لملاحظة الأحداث المعطاة بغض النظر عن الحالات النهائية:

${\displaystyle \mathbf {P} (o_{1},o_{2},\dots ,o_{t}|\mathbf {\pi } _{0})=\prod _{s=1}^{t}c_{s}}$

وهذا يسمح لنا بتفسير متجه الاحتمالية المُقاس على النحو التالي:

${\displaystyle \mathbf {{\hat {f}}_{0:t}} (i)={\frac {\mathbf {f_{0:t}} (i)}{\prod _{s=1}^{t}c_{s}}}={\frac {\mathbf {P} (o_{1},o_{2},\dots ,o_{t},X_{t}=x_{i}|\mathbf {\pi } _{0})}{\mathbf {P} (o_{1},o_{2},\dots ,o_{t}|\mathbf {\pi } _{0})}}=\mathbf {P} (X_{t}=x_{i}|o_{1},o_{2},\dots ,o_{t},\mathbf {\pi } _{0})}$

وبالتالي نجد أن حاصل ضرب عوامل القياس يوفر لنا الاحتمال الكلي لملاحظة التسلسل المعطى حتى الوقت t وأن متجه الاحتمال المقاس يوفر لنا احتمال التواجد في كل حالة في هذا الوقت.

يمكن اتباع إجراء مماثل لإيجاد الاحتمالات العكسية. وتهدف هذه الإجراءات إلى توفير الاحتمالات التالية:

${\displaystyle \mathbf {b_{t:T}} (i)=\mathbf {P} (o_{t+1},o_{t+2},\dots ,o_{T}|X_{t}=x_{i})}$

أي أننا نريد الآن أن نفترض أننا نبدأ في حالة معينة (${\displaystyle X_{t}=x_{i}}$ونحن الآن مهتمون باحتمالية رصد جميع الأحداث المستقبلية من هذه الحالة. وبما أن الحالة الابتدائية مفترضة كمعطى (أي أن الاحتمالية المسبقة لهذه الحالة = 100%)، فإننا نبدأ بما يلي:

${\displaystyle \mathbf {b_{T:T}} =[1\ 1\ 1\ \dots ]^{T}}$

لاحظ أننا نستخدم الآن متجه عمودي بينما كانت الاحتمالات الأمامية تستخدم متجهات صفية. يمكننا بعد ذلك العمل عكسيًا باستخدام:

${\displaystyle \mathbf {b_{t-1:T}} =\mathbf {T} \mathbf {O_{t}} \mathbf {b_{t:T}} }$

على الرغم من إمكانية تطبيع هذا المتجه بحيث يكون مجموع عناصره واحدًا، إلا أن هذا لا يُفعل عادةً. مع ملاحظة أن كل عنصر يحتوي على احتمالية تسلسل الأحداث المستقبلية بالنظر إلى حالة ابتدائية معينة، فإن تطبيع هذا المتجه يُعادل تطبيق نظرية بايز لإيجاد احتمالية كل حالة ابتدائية بالنظر إلى الأحداث المستقبلية (بافتراض توزيعات احتمالية أولية منتظمة لمتجه الحالة النهائية). ومع ذلك، من الشائع أكثر قياس هذا المتجه باستخدام نفس${\displaystyle c_{t}}$الثوابت المستخدمة في حسابات الاحتمالية الأمامية. ${\displaystyle \mathbf {b_{T:T}} }$لا يتم توسيع نطاقها، ولكن العمليات اللاحقة تستخدم:

${\displaystyle \mathbf {{\hat {b}}_{t-1:T}} =c_{t}^{-1}\mathbf {T} \mathbf {O_{t}} \mathbf {{\hat {b}}_{t:T}} }$

أين${\displaystyle \mathbf {{\hat {b}}_{t:T}} }$يمثل المتجه السابق بعد تعديله. ونتيجة لذلك، يرتبط متجه الاحتمالية المعدل بالاحتمالات العكسية بالعلاقة التالية:

${\displaystyle \mathbf {{\hat {b}}_{t:T}} (i)={\frac {\mathbf {b_{t:T}} (i)}{\prod _{s=t+1}^{T}c_{s}}}}$

هذا مفيد لأنه يسمح لنا بإيجاد الاحتمالية الإجمالية للتواجد في كل حالة في وقت معين، t، عن طريق ضرب هذه القيم:

${\displaystyle \mathbf {\gamma _{t}} (i)=\mathbf {P} (X_{t}=x_{i}|o_{1},o_{2},\dots ,o_{T},\mathbf {\pi } _{0})={\frac {\mathbf {P} (o_{1},o_{2},\dots ,o_{T},X_{t}=x_{i}|\mathbf {\pi } _{0})}{\mathbf {P} (o_{1},o_{2},\dots ,o_{T}|\mathbf {\pi } _{0})}}={\frac {\mathbf {f_{0:t}} (i)\cdot \mathbf {b_{t:T}} (i)}{\prod _{s=1}^{T}c_{s}}}=\mathbf {{\hat {f}}_{0:t}} (i)\cdot \mathbf {{\hat {b}}_{t:T}} (i)}$

ولفهم ذلك، نلاحظ أن${\displaystyle \mathbf {f_{0:t}} (i)\cdot \mathbf {b_{t:T}} (i)}$يُحدد هذا الاحتمال احتمالية رصد الأحداث المعطاة بطريقة تمر عبر الحالة${\displaystyle x_{i}}$عند الزمن t. يشمل هذا الاحتمال الاحتمالات الأمامية التي تغطي جميع الأحداث حتى الزمن t، بالإضافة إلى الاحتمالات الخلفية التي تشمل جميع الأحداث المستقبلية. هذا هو البسط الذي نبحث عنه في معادلتنا، ونقسمه على الاحتمال الكلي لتسلسل الملاحظات لتطبيع هذه القيمة واستخراج الاحتمال فقط.${\displaystyle X_{t}=x_{i}}$تُسمى هذه القيم أحيانًا "القيم المُنعّمة" لأنها تجمع بين الاحتمالات الأمامية والخلفية لحساب الاحتمال النهائي.

القيم${\displaystyle \mathbf {\gamma _{t}} (i)}$وبالتالي، توفر هذه الاحتمالات احتمالية التواجد في كل حالة عند الزمن t. ولذلك، فهي مفيدة لتحديد الحالة الأكثر احتمالاً في أي وقت. مصطلح "الحالة الأكثر احتمالاً" غامض إلى حد ما. فبينما تكون الحالة الأكثر احتمالاً هي الحالة التي يُرجح أن تكون صحيحة عند نقطة معينة، فإن تسلسل الحالات المحتملة بشكل فردي ليس بالضرورة أن يكون التسلسل الأكثر احتمالاً. هذا لأن احتمالات كل نقطة تُحسب بشكل مستقل عن بعضها البعض. فهي لا تأخذ في الاعتبار احتمالات الانتقال بين الحالات، وبالتالي من الممكن الحصول على حالات عند لحظتين (t و t+1) تكون كلتاهما الأكثر احتمالاً عند هاتين النقطتين الزمنيتين، ولكن احتمالية حدوثهما معًا ضئيلة للغاية.${\displaystyle \mathbf {P} (X_{t}=x_{i},X_{t+1}=x_{j})\neq \mathbf {P} (X_{t}=x_{i})\mathbf {P} (X_{t+1}=x_{j})}$يمكن إيجاد التسلسل الأكثر احتمالاً للحالات التي أنتجت تسلسل الملاحظات باستخدام خوارزمية فيتربي .

يستند هذا المثال إلى مفهوم "عالم المظلات" الوارد في كتاب راسل ونورفيج (2010)، الفصل 15، صفحة 567، حيث نرغب في استنتاج حالة الطقس من خلال ملاحظة شخص آخر يحمل مظلة أو لا يحملها. نفترض حالتين محتملتين للطقس: الحالة 1 = مطر، الحالة 2 = لا مطر. نفترض أن احتمالية بقاء حالة الطقس على حالها يوميًا هي 70%، واحتمالية تغيرها هي 30%. وبالتالي، تكون احتمالات الانتقال كما يلي:

${\displaystyle \mathbf {T} ={\begin{pmatrix}0.7&0.3\\0.3&0.7\end{pmatrix}}}$

نفترض أيضاً أن كل حالة تُنتج أحد حدثين محتملين: الحدث 1 = مظلة، الحدث 2 = لا مظلة. وتُعطى الاحتمالات الشرطية لحدوث هذين الحدثين في كل حالة بواسطة مصفوفة الاحتمالات التالية:

${\displaystyle \mathbf {B} ={\begin{pmatrix}0.9&0.1\\0.2&0.8\end{pmatrix}}}$

ثم نلاحظ التسلسل التالي للأحداث: {مظلة، مظلة، لا مظلة، مظلة، مظلة} والذي سنمثله في حساباتنا على النحو التالي:

${\displaystyle \mathbf {O_{1}} ={\begin{pmatrix}0.9&0.0\\0.0&0.2\end{pmatrix}}~~\mathbf {O_{2}} ={\begin{pmatrix}0.9&0.0\\0.0&0.2\end{pmatrix}}~~\mathbf {O_{3}} ={\begin{pmatrix}0.1&0.0\\0.0&0.8\end{pmatrix}}~~\mathbf {O_{4}} ={\begin{pmatrix}0.9&0.0\\0.0&0.2\end{pmatrix}}~~\mathbf {O_{5}} ={\begin{pmatrix}0.9&0.0\\0.0&0.2\end{pmatrix}}}$

لاحظ أن${\displaystyle \mathbf {O_{3}} }$يختلف عن الآخرين بسبب ملاحظة "عدم وجود مظلة".

في حساب الاحتمالات المستقبلية، نبدأ بما يلي:

${\displaystyle \mathbf {f_{0:0}} ={\begin{pmatrix}0.5&0.5\end{pmatrix}}}$

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

${\displaystyle (\mathbf {{\hat {f}}_{0:t}} )^{T}=c_{t}^{-1}\mathbf {O_{t}} (\mathbf {T} )^{T}(\mathbf {{\hat {f}}_{0:t-1}} )^{T}}$

بدلاً من:

${\displaystyle \mathbf {{\hat {f}}_{0:t}} =c_{t}^{-1}\mathbf {{\hat {f}}_{0:t-1}} \mathbf {T} \mathbf {O_{t}} }$

لاحظ أن مصفوفة التحويل تُنقل أيضًا، ولكن في مثالنا، تكون المصفوفة المنقولة مساوية للمصفوفة الأصلية. بإجراء هذه الحسابات وتطبيع النتائج، نحصل على:

${\displaystyle (\mathbf {{\hat {f}}_{0:1}} )^{T}=c_{1}^{-1}{\begin{pmatrix}0.9&0.0\\0.0&0.2\end{pmatrix}}{\begin{pmatrix}0.7&0.3\\0.3&0.7\end{pmatrix}}{\begin{pmatrix}0.5000\\0.5000\end{pmatrix}}=c_{1}^{-1}{\begin{pmatrix}0.4500\\0.1000\end{pmatrix}}={\begin{pmatrix}0.8182\\0.1818\end{pmatrix}}}$

${\displaystyle (\mathbf {{\hat {f}}_{0:2}} )^{T}=c_{2}^{-1}{\begin{pmatrix}0.9&0.0\\0.0&0.2\end{pmatrix}}{\begin{pmatrix}0.7&0.3\\0.3&0.7\end{pmatrix}}{\begin{pmatrix}0.8182\\0.1818\end{pmatrix}}=c_{2}^{-1}{\begin{pmatrix}0.5645\\0.0745\end{pmatrix}}={\begin{pmatrix}0.8834\\0.1166\end{pmatrix}}}$

${\displaystyle (\mathbf {{\hat {f}}_{0:3}} )^{T}=c_{3}^{-1}{\begin{pmatrix}0.1&0.0\\0.0&0.8\end{pmatrix}}{\begin{pmatrix}0.7&0.3\\0.3&0.7\end{pmatrix}}{\begin{pmatrix}0.8834\\0.1166\end{pmatrix}}=c_{3}^{-1}{\begin{pmatrix}0.0653\\0.2772\end{pmatrix}}={\begin{pmatrix}0.1907\\0.8093\end{pmatrix}}}$

${\displaystyle (\mathbf {{\hat {f}}_{0:4}} )^{T}=c_{4}^{-1}{\begin{pmatrix}0.9&0.0\\0.0&0.2\end{pmatrix}}{\begin{pmatrix}0.7&0.3\\0.3&0.7\end{pmatrix}}{\begin{pmatrix}0.1907\\0.8093\end{pmatrix}}=c_{4}^{-1}{\begin{pmatrix}0.3386\\0.1247\end{pmatrix}}={\begin{pmatrix}0.7308\\0.2692\end{pmatrix}}}$

${\displaystyle (\mathbf {{\hat {f}}_{0:5}} )^{T}=c_{5}^{-1}{\begin{pmatrix}0.9&0.0\\0.0&0.2\end{pmatrix}}{\begin{pmatrix}0.7&0.3\\0.3&0.7\end{pmatrix}}{\begin{pmatrix}0.7308\\0.2692\end{pmatrix}}=c_{5}^{-1}{\begin{pmatrix}0.5331\\0.0815\end{pmatrix}}={\begin{pmatrix}0.8673\\0.1327\end{pmatrix}}}$

بالنسبة للاحتمالات العكسية، نبدأ بما يلي:

${\displaystyle \mathbf {b_{5:5}} ={\begin{pmatrix}1.0\\1.0\end{pmatrix}}}$

وبذلك نتمكن من الحساب (باستخدام الملاحظات بترتيب عكسي وتطبيعها بثوابت مختلفة):

${\displaystyle \mathbf {{\hat {b}}_{4:5}} =\alpha {\begin{pmatrix}0.7&0.3\\0.3&0.7\end{pmatrix}}{\begin{pmatrix}0.9&0.0\\0.0&0.2\end{pmatrix}}{\begin{pmatrix}1.0000\\1.0000\end{pmatrix}}=\alpha {\begin{pmatrix}0.6900\\0.4100\end{pmatrix}}={\begin{pmatrix}0.6273\\0.3727\end{pmatrix}}}$

${\displaystyle \mathbf {{\hat {b}}_{3:5}} =\alpha {\begin{pmatrix}0.7&0.3\\0.3&0.7\end{pmatrix}}{\begin{pmatrix}0.9&0.0\\0.0&0.2\end{pmatrix}}{\begin{pmatrix}0.6273\\0.3727\end{pmatrix}}=\alpha {\begin{pmatrix}0.4175\\0.2215\end{pmatrix}}={\begin{pmatrix}0.6533\\0.3467\end{pmatrix}}}$

${\displaystyle \mathbf {{\hat {b}}_{2:5}} =\alpha {\begin{pmatrix}0.7&0.3\\0.3&0.7\end{pmatrix}}{\begin{pmatrix}0.1&0.0\\0.0&0.8\end{pmatrix}}{\begin{pmatrix}0.6533\\0.3467\end{pmatrix}}=\alpha {\begin{pmatrix}0.1289\\0.2138\end{pmatrix}}={\begin{pmatrix}0.3763\\0.6237\end{pmatrix}}}$

${\displaystyle \mathbf {{\hat {b}}_{1:5}} =\alpha {\begin{pmatrix}0.7&0.3\\0.3&0.7\end{pmatrix}}{\begin{pmatrix}0.9&0.0\\0.0&0.2\end{pmatrix}}{\begin{pmatrix}0.3763\\0.6237\end{pmatrix}}=\alpha {\begin{pmatrix}0.2745\\0.1889\end{pmatrix}}={\begin{pmatrix}0.5923\\0.4077\end{pmatrix}}}$

${\displaystyle \mathbf {{\hat {b}}_{0:5}} =\alpha {\begin{pmatrix}0.7&0.3\\0.3&0.7\end{pmatrix}}{\begin{pmatrix}0.9&0.0\\0.0&0.2\end{pmatrix}}{\begin{pmatrix}0.5923\\0.4077\end{pmatrix}}=\alpha {\begin{pmatrix}0.3976\\0.2170\end{pmatrix}}={\begin{pmatrix}0.6469\\0.3531\end{pmatrix}}}$

وأخيرًا، سنحسب قيم الاحتمالية المُعدّلة. يجب أيضًا تعديل هذه النتائج بحيث يكون مجموع عناصرها مساويًا لـ 1، لأننا لم نقم بتعديل احتمالات التراجع باستخدام${\displaystyle c_{t}}$تم العثور على ذلك سابقًا. وبالتالي، فإن متجهات الاحتمال العكسي المذكورة أعلاه تمثل في الواقع احتمالية كل حالة عند الزمن t بالنظر إلى الملاحظات المستقبلية. ولأن هذه المتجهات تتناسب مع الاحتمالات العكسية الفعلية، يجب تعديل النتيجة مرة إضافية.

${\displaystyle (\mathbf {\gamma _{0}} )^{T}=\alpha {\begin{pmatrix}0.5000\\0.5000\end{pmatrix}}\circ {\begin{pmatrix}0.6469\\0.3531\end{pmatrix}}=\alpha {\begin{pmatrix}0.3235\\0.1765\end{pmatrix}}={\begin{pmatrix}0.6469\\0.3531\end{pmatrix}}}$

${\displaystyle (\mathbf {\gamma _{1}} )^{T}=\alpha {\begin{pmatrix}0.8182\\0.1818\end{pmatrix}}\circ {\begin{pmatrix}0.5923\\0.4077\end{pmatrix}}=\alpha {\begin{pmatrix}0.4846\\0.0741\end{pmatrix}}={\begin{pmatrix}0.8673\\0.1327\end{pmatrix}}}$

${\displaystyle (\mathbf {\gamma _{2}} )^{T}=\alpha {\begin{pmatrix}0.8834\\0.1166\end{pmatrix}}\circ {\begin{pmatrix}0.3763\\0.6237\end{pmatrix}}=\alpha {\begin{pmatrix}0.3324\\0.0728\end{pmatrix}}={\begin{pmatrix}0.8204\\0.1796\end{pmatrix}}}$

${\displaystyle (\mathbf {\gamma _{3}} )^{T}=\alpha {\begin{pmatrix}0.1907\\0.8093\end{pmatrix}}\circ {\begin{pmatrix}0.6533\\0.3467\end{pmatrix}}=\alpha {\begin{pmatrix}0.1246\\0.2806\end{pmatrix}}={\begin{pmatrix}0.3075\\0.6925\end{pmatrix}}}$

${\displaystyle (\mathbf {\gamma _{4}} )^{T}=\alpha {\begin{pmatrix}0.7308\\0.2692\end{pmatrix}}\circ {\begin{pmatrix}0.6273\\0.3727\end{pmatrix}}=\alpha {\begin{pmatrix}0.4584\\0.1003\end{pmatrix}}={\begin{pmatrix}0.8204\\0.1796\end{pmatrix}}}$

${\displaystyle (\mathbf {\gamma _{5}} )^{T}=\alpha {\begin{pmatrix}0.8673\\0.1327\end{pmatrix}}\circ {\begin{pmatrix}1.0000\\1.0000\end{pmatrix}}=\alpha {\begin{pmatrix}0.8673\\0.1327\end{pmatrix}}={\begin{pmatrix}0.8673\\0.1327\end{pmatrix}}}$

لاحظ أن قيمة${\displaystyle \mathbf {\gamma _{0}} }$يساوي${\displaystyle \mathbf {{\hat {b}}_{0:5}} }$وذلك${\displaystyle \mathbf {\gamma _{5}} }$يساوي${\displaystyle \mathbf {{\hat {f}}_{0:5}} }$وهذا أمر طبيعي لأن كليهما${\displaystyle \mathbf {{\hat {f}}_{0:5}} }$و${\displaystyle \mathbf {{\hat {b}}_{0:5}} }$ابدأ بتوزيعات احتمالية أولية منتظمة على متجهات الحالة الابتدائية والنهائية (على التوالي) وخذ في الاعتبار جميع الملاحظات. ومع ذلك،${\displaystyle \mathbf {\gamma _{0}} }$لن يكون مساوياً إلا لـ${\displaystyle \mathbf {{\hat {b}}_{0:5}} }$عندما يمثل متجه الحالة الأولية لدينا توزيعًا احتماليًا منتظمًا (أي أن جميع المدخلات متساوية). عندما لا يكون الأمر كذلك${\displaystyle \mathbf {{\hat {b}}_{0:5}} }$يجب دمج هذه البيانات مع متجه الحالة الابتدائية لإيجاد الحالة الابتدائية الأكثر احتمالاً. وبذلك، نجد أن احتمالات التقدم وحدها كافية لحساب الحالة النهائية الأكثر احتمالاً. وبالمثل، يمكن دمج احتمالات التراجع مع متجه الحالة الابتدائية لتوفير الحالة الابتدائية الأكثر احتمالاً بالنظر إلى الملاحظات. يكفي دمج احتمالات التقدم والتراجع لاستنتاج الحالات الأكثر احتمالاً بين النقطتين الابتدائية والنهائية.

تُظهر الحسابات أعلاه أن حالة الطقس الأكثر احتمالاً في كل يوم باستثناء اليوم الثالث كانت "المطر". لكنها تُخبرنا بأكثر من ذلك، إذ تُتيح لنا الآن طريقةً لتحديد احتمالات كل حالة في أوقات مختلفة. ولعل الأهم من ذلك، هو قيمتنا عند${\displaystyle \mathbf {\gamma _{5}} }$يُحدد هذا المقياس معرفتنا بمتجه الحالة في نهاية سلسلة الملاحظات. ويمكننا بعد ذلك استخدام هذه المعرفة للتنبؤ باحتمالية حدوث مختلف حالات الطقس غدًا، بالإضافة إلى احتمالية رؤية مظلة.

تعمل خوارزمية التقديم والترجيع بتعقيد زمني${\displaystyle O(S^{2}T)}$في الفضاء${\displaystyle O(ST)}$، أين${\displaystyle T}$يمثل طول التسلسل الزمني و${\displaystyle S}$يمثل عدد الرموز في أبجدية الحالة. ^{[ 1 ]} يمكن أيضًا تشغيل الخوارزمية في مساحة ثابتة مع تعقيد زمني${\displaystyle O(S^{2}T^{2})}$عن طريق إعادة حساب القيم في كل خطوة. ^{[ 2 ]} للمقارنة، فإن إجراء البحث الشامل سيولد جميع القيم الممكنة${\displaystyle S^{T}}$تسلسل الحالات وحساب الاحتمالية المشتركة لكل تسلسل حالة مع سلسلة الأحداث المرصودة، وهو ما سيكون له تعقيد زمني${\displaystyle O(T\cdot S^{T})}$. إن استخدام القوة الغاشمة أمر غير قابل للتطبيق في المشاكل الواقعية، حيث أن عدد تسلسلات العقد المخفية المحتملة عادة ما يكون مرتفعًا للغاية.

يُعدّ تحسين خوارزمية التقديم والتراجع العامة، والتي تُسمى خوارزمية الجزيرة ، بديلاً عن تقليل استخدام الذاكرة وزيادة وقت التشغيل، حيث تأخذ${\displaystyle O(S^{2}T\log T)}$الوقت و${\displaystyle O(S\log T)}$الذاكرة. علاوة على ذلك، من الممكن عكس نموذج العملية للحصول على${\displaystyle O(S)}$فضاء،${\displaystyle O(S^{2}T)}$خوارزمية الوقت، على الرغم من أن العملية المعكوسة قد لا تكون موجودة أو قد تكون سيئة التكييف . ^{[ 3 ]}

بالإضافة إلى ذلك، تم تطوير خوارزميات لحساب${\displaystyle \mathbf {f_{0:t+1}} }$بكفاءة من خلال التنعيم عبر الإنترنت مثل خوارزمية التنعيم ذات التأخير الثابت (FLS). ^{[ 4 ]}

خوارزمية التقديم والترجيع هي المدخل: guessState int sequenceIndex output: resultإذا تجاوز مؤشر التسلسل نهاية التسلسل ، فأرجع 1. إذا سبق رؤية ( guessState ، sequenceIndex ) ، فأرجع النتيجة المحفوظة .النتيجة := 0 لكل حالة مجاورة n: النتيجة := النتيجة + (احتمالية الانتقال من حالة التخمين إلى (n عنصر الملاحظة المعطاة في فهرس التسلسل ) × Backward(n, sequenceIndex + 1) حفظ النتيجة لـ ( guessState ، sequenceIndex ) إرجاع النتيجة

بافتراض وجود نموذج ماركوف المخفي (كما هو الحال في خوارزمية فيتربي ) ممثلاً بلغة برمجة بايثون :

states = ( "صحي" , "حمى" ) end_state = "E"الملاحظات = ( "طبيعي" ، "بارد" ، "دوار" )احتمالية_البداية = { "صحي" : 0.6 , "حمى" : 0.4 }احتمالية_الانتقال = { "صحي" : { "صحي" : 0.69 , "حمى" : 0.3 , "E" : 0.01 }, "حمى" : { "صحي" : 0.4 , "حمى" : 0.59 , "E" : 0.01 }, }احتمالية_الانبعاث = { "صحي" : { "طبيعي" : 0.5 , "زكام" : 0.4 , "دوار" : 0.1 }, "حمى" : { "طبيعي" : 0.1 , "زكام" : 0.3 , "دوار" : 0.6 }, }

يمكننا كتابة تطبيق خوارزمية التقديم والترجيع على النحو التالي:

دالة fwd_bkw ( الملاحظات ، الحالات ، احتمال_البداية ، احتمال_التحول ، احتمال_الانحراف_المتوسط ، حالة_النهاية ): """خوارزمية التقديم والتراجع.""" # الجزء الأمامي من الخوارزمية fwd = [] for i , observation_i in enumerate ( الملاحظات ): f_curr = {} for st in الحالات : if i == 0 : # الحالة الأساسية للجزء الأمامي prev_f_sum = احتمال_البداية [ st ] else : prev_f_sum = مجموع ( f_prev [ k ] * احتمال_التحول [ k ][ st ] for k in الحالات )f_curr [ st ] = emm_prob [ st ][ observation_i ] * prev_f_sumfwd.append ( f_curr ) f_prev = f_curr​​p_fwd = sum ( f_curr [ k ] * trans_prob [ k ][ end_st ] for k in states )# الجزء العكسي من الخوارزمية bkw = [] for i , observation_i_plus in enumerate ( reversed ( observations [ 1 :] + ( None ,))): b_curr = {} for st in states : if i == 0 : # الحالة الأساسية للجزء العكسي b_curr [ st ] = trans_prob [ st ][ end_st ] else : b_curr [ st ] = sum ( trans_prob [ st ][ l ] * emm_prob [ l ][ observation_i_plus ] * b_prev [ l ] for l in states )bkw.insert ( 0 , b_curr ) b_prev = b_curr​​p_bkw = sum ( start_prob [ l ] * emm_prob [ l ][ observations [ 0 ]] * b_curr [ l ] for l in states )# دمج الجزأين posterior = [] for i in range ( len ( observations )): posterior . append ({ st : fwd [ i ][ st ] * bkw [ i ][ st ] / p_fwd for st in states })تحقق من أن p_fwd يساوي p_bkw ، ثم أرجع fwd و bkw و posterior

تأخذ الدالة fwd_bkwالوسائط التالية: xهي سلسلة الملاحظات، على سبيل المثال ['normal', 'cold', 'dizzy']؛ statesهي مجموعة الحالات المخفية ؛ a_0هي احتمالية البداية ؛ aهي احتمالات الانتقال ؛ و eهي احتمالات الانبعاث.

لتبسيط الكود، نفترض أن سلسلة الملاحظات xغير فارغة وأن a[i][j]و e[i][j]معرفة لجميع الحالات i و j.

في المثال العملي، يتم استخدام خوارزمية التقديم والترجيع على النحو التالي:

def example (): return fwd_bkw ( observations , states , start_probability , transition_probability , emission_probability , end_state , )

>>> for line in example (): ... print ( * line ) ... {'Healthy': 0.3, 'Fever': 0.04000000000000001} {'Healthy': 0.0892, 'Fever': 0.03408} {'Healthy': 0.007518, 'Fever': 0.028120319999999997} {'Healthy': 0.0010418399999999998, 'Fever': 0.00109578} {'Healthy': 0.00249, 'Fever': 0.00394} {'Healthy': 0.01, 'Fever': 0.01} {'Healthy': {'صحي': 0.8770110375573259، 'حمى': 0.1229889624426741} {'صحي': 0.623228030950954، 'حمى': 0.3767719690490461} {'صحي': 0.2109527048413057، 'حمى': 0.7890472951586943}

• خوارزمية باوم-ويلش
• خوارزمية فيتربي
• خوارزمية BCJR

• لورانس ر. رابينر ، دليل تعليمي حول نماذج ماركوف المخفية وتطبيقات مختارة في التعرف على الكلام. وقائع معهد مهندسي الكهرباء والإلكترونيات ، 77 (2)، ص  257-286، فبراير 1989. 10.1109/5.18626
• لورانس ر. رابينر، بي إتش جوانج (يناير 1986). “مقدمة لنماذج ماركوف المخفية”. مجلة IEEE ASSP : 4-15 .
• يوجين شارنياك (1993). التعلم الإحصائي للغة . كامبريدج، ماساتشوستس: مطبعة معهد ماساتشوستس للتكنولوجيا. ISBN 978-0-262-53141-2.
• ستيوارت راسل وبيتر نورفيج (2010). الذكاء الاصطناعي: منهج حديث، الطبعة الثالثة . أبر سادل ريفر، نيو جيرسي: بيرسون إديوكيشن/برنتيس هول. ISBN 978-0-13-604259-4.

• جدول بيانات تفاعلي لتعليم خوارزمية التقديم والترجيع (جدول بيانات ومقال مع شرح تفصيلي خطوة بخطوة)
• شرح نماذج ماركوف المخفية بما في ذلك خوارزمية التقديم والتراجع
• مجموعة من خوارزميات الذكاء الاصطناعي المطبقة بلغة جافا (بما في ذلك نموذج ماركوف المخفي وخوارزمية التقديم والتراجع).