خوارزمية أمامية

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

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

بالنسبة لنموذج ماركوف المخفي (HMM) مثل هذا:

يُكتب هذا الاحتمال على النحو التالي:${\displaystyle p(x_{t}|y_{1:t})}$. هنا${\displaystyle x(t)}$هي الحالة الخفية التي تُختصر إلى${\displaystyle x_{t}}$و${\displaystyle y_{1:t}}$هي الملاحظات${\displaystyle 1}$ل${\displaystyle t}$.

تُكمّل الخوارزمية العكسية الخوارزمية الأمامية من خلال مراعاة التاريخ المستقبلي إذا رغبنا في تحسين التقدير للأوقات الماضية. يُشار إلى هذا باسم التنعيم، وتقوم الخوارزمية الأمامية/العكسية بحساب...${\displaystyle p(x_{t}|y_{1:T})}$ل${\displaystyle 1<t<T}$وبالتالي، تأخذ خوارزمية التقديم/التراجع الكاملة جميع الأدلة في الحسبان. تجدر الإشارة إلى أنه يمكن حساب حالة الاعتقاد في كل خطوة زمنية، ولكن هذا لا يُنتج، بالمعنى الدقيق، تسلسل الحالات الأكثر احتمالاً ، بل يُنتج الحالة الأكثر احتمالاً في كل خطوة زمنية، بالنظر إلى التاريخ السابق. ولتحقيق التسلسل الأكثر احتمالاً، يلزم استخدام خوارزمية فيتربي . فهي تحسب تسلسل الحالات الأكثر احتمالاً بالنظر إلى تاريخ الملاحظات، أي تسلسل الحالات الذي يُعظّم قيمة .${\displaystyle p(x_{0:t}|y_{0:t})}$.

الهدف من الخوارزمية الأمامية هو حساب الاحتمال المشترك${\displaystyle p(x_{t},y_{1:t})}$، حيث قمنا باختصارها تسهيلاً للرموز${\displaystyle x(t)}$مثل${\displaystyle x_{t}}$و${\displaystyle (y(1),y(2),...,y(t))}$مثل${\displaystyle y_{1:t}}$بمجرد تحديد الاحتمال المشترك${\displaystyle p(x_{t},y_{1:t})}$يتم حساب الاحتمالات الأخرى${\displaystyle p(x_{t}|y_{1:t})}$و${\displaystyle p(y_{1:t})}$يمكن الحصول عليها بسهولة.

كلا الولايتين${\displaystyle x_{t}}$والملاحظة${\displaystyle y_{t}}$يُفترض أن تكون متغيرات عشوائية منفصلة ومحدودة. احتمالات انتقال الحالة لنموذج ماركوف المخفي${\displaystyle p(x_{t}|x_{t-1})}$احتمالات الرصد/الانبعاث${\displaystyle p(y_{t}|x_{t})}$، والاحتمالية الأولية المسبقة${\displaystyle p(x_{0})}$يُفترض أن تكون هذه المعلومات معروفة. علاوة على ذلك، فإن تسلسل الملاحظات${\displaystyle y_{1:t}}$يفترض أن تكون هذه المعلومات معطاة.

الحوسبة${\displaystyle p(x_{t},y_{1:t})}$يتطلب الأمر ببساطة إجراء عملية تهميش على جميع تسلسلات الحالة الممكنة${\displaystyle \{x_{1:t-1}\}}$، والتي يزداد عددها بشكل كبير مع${\displaystyle t}$بدلاً من ذلك، تستفيد الخوارزمية الأمامية من قواعد الاستقلال الشرطي لنموذج ماركوف المخفي (HMM) لإجراء الحساب بشكل متكرر.

لتوضيح التكرار، دع

${\displaystyle \alpha (x_{t})=p(x_{t},y_{1:t})=\sum _{x_{t-1}}p(x_{t},x_{t-1},y_{1:t})}$.

استخدام قاعدة السلسلة للتوسيع${\displaystyle p(x_{t},x_{t-1},y_{1:t})}$ثم يمكننا أن نكتب

${\displaystyle \alpha (x_{t})=\sum _{x_{t-1}}p(y_{t}|x_{t},x_{t-1},y_{1:t-1})p(x_{t}|x_{t-1},y_{1:t-1})p(x_{t-1},y_{1:t-1})}$.

لأن${\displaystyle y_{t}}$مستقل شرطيًا عن كل شيء، لكن${\displaystyle x_{t}}$، و${\displaystyle x_{t}}$مستقل شرطيًا عن كل شيء، لكن${\displaystyle x_{t-1}}$، وهذا يتبسط إلى

${\displaystyle \alpha (x_{t})=p(y_{t}|x_{t})\sum _{x_{t-1}}p(x_{t}|x_{t-1})\alpha (x_{t-1})}$.

وبالتالي، بما أن${\displaystyle p(y_{t}|x_{t})}$و${\displaystyle p(x_{t}|x_{t-1})}$إذا تم تحديدها بواسطة توزيعات انبعاثات النموذج واحتمالات الانتقال ، والتي يُفترض أنها معروفة، فيمكن حسابها بسرعة.${\displaystyle \alpha (x_{t})}$من${\displaystyle \alpha (x_{t-1})}$وتجنب تكبد وقت حسابي هائل.

يمكن كتابة صيغة الاستدعاء الذاتي المذكورة أعلاه بشكل أكثر اختصارًا. لنفترض${\displaystyle a_{ij}=p(x_{t}=i|x_{t-1}=j)}$لتكن احتمالات الانتقال و${\displaystyle b_{ij}=p(y_{t}=i|x_{t}=j)}$إذا كانت احتمالات الانبعاث هي ،

${\displaystyle \mathbf {\alpha } _{t}=\mathbf {b} _{t}^{T}\odot \mathbf {A} \mathbf {\alpha } _{t-1}}$

أين${\displaystyle \mathbf {A} =[a_{ij}]}$هي مصفوفة احتمالية الانتقال،${\displaystyle \mathbf {b} _{t}}$يمثل الصف i من مصفوفة احتمالية الانبعاث${\displaystyle \mathbf {B} =[b_{ij}]}$وهو ما يتوافق مع الملاحظة الفعلية${\displaystyle y_{t}=i}$في ذلك الوقت${\displaystyle t}$، و${\displaystyle \mathbf {\alpha } _{t}=[\alpha (x_{t}=1),\ldots ,\alpha (x_{t}=n)]^{T}}$هو متجه ألفا.${\displaystyle \odot }$هو حاصل ضرب هادامارد بين منقولة${\displaystyle \mathbf {b} _{t}}$و${\displaystyle \mathbf {A} \mathbf {\alpha } _{t-1}}$.

يتم تحديد الشرط الأولي وفقًا للاحتمال المسبق على${\displaystyle x_{0}}$مثل

${\displaystyle \alpha (x_{0})=p(y_{0}|x_{0})p(x_{0})}$.

بمجرد الاحتمال المشترك${\displaystyle \alpha (x_{t})=p(x_{t},y_{1:t})}$بعد حسابها باستخدام خوارزمية التقديم الأمامي، يمكننا بسهولة الحصول على الاحتمال المشترك ذي الصلة${\displaystyle p(y_{1:t})}$مثل

${\displaystyle p(y_{1:t})=\sum _{x_{t}}p(x_{t},y_{1:t})=\sum _{x_{t}}\alpha (x_{t})}$

والاحتمال الشرطي المطلوب${\displaystyle p(x_{t}|y_{1:t})}$مثل

${\displaystyle p(x_{t}|y_{1:t})={\frac {p(x_{t},y_{1:t})}{p(y_{1:t})}}={\frac {\alpha (x_{t})}{\sum _{x_{t}}\alpha (x_{t})}}.}$

بمجرد حساب الاحتمال الشرطي ، يمكننا أيضًا إيجاد التقدير النقطي لـ${\displaystyle x_{t}}$على سبيل المثال، تقدير MAP لـ${\displaystyle x_{t}}$يُعطى بواسطة

${\displaystyle {\widehat {x}}_{t}^{MAP}=\arg \max _{x_{t}}\;p(x_{t}|y_{1:t})=\arg \max _{x_{t}}\;\alpha (x_{t}),}$

بينما تقدير MMSE لـ${\displaystyle x_{t}}$يُعطى بواسطة

${\displaystyle {\widehat {x}}_{t}^{MMSE}=\mathbb {E} [x_{t}|y_{1:t}]=\sum _{x_{t}}x_{t}p(x_{t}|y_{1:t})={\frac {\sum _{x_{t}}x_{t}\alpha (x_{t})}{\sum _{x_{t}}\alpha (x_{t})}}.}$

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

هذا مثال على رصد حالات الطقس المحتملة من خلال رصد حالة الأعشاب البحرية. لدينا ملاحظات عن حالة الأعشاب البحرية لثلاثة أيام متتالية، حيث كانت جافة، رطبة، ومغمورة بالماء على التوالي. يمكن أن تكون حالات الطقس المحتملة مشمسة، غائمة، أو ممطرة. إجمالاً، يمكن أن يكون هناك${\displaystyle 3^{3}=27}$مثل هذه التسلسلات الجوية. يُعد استكشاف جميع تسلسلات الحالة المحتملة هذه مكلفًا حسابيًا للغاية. ولتقليل هذا التعقيد، تُصبح خوارزمية التقدّم الأمامي مفيدة، حيث تكمن الحيلة في استخدام الاستقلال الشرطي لخطوات التسلسل لحساب الاحتمالات الجزئية.${\displaystyle \alpha (x_{t})=p(x_{t},y_{1:t})=p(y_{t}|x_{t})\sum _{x_{t-1}}p(x_{t}|x_{t-1})\alpha (x_{t-1})}$كما هو موضح في الاشتقاق أعلاه. وبالتالي، يمكننا حساب الاحتمالات كحاصل ضرب احتمال الملاحظة/الانبعاث المناسب.${\displaystyle p(y_{t}|x_{t})}$(احتمالية الحالة)${\displaystyle y_{t}}$(كما هو موضح في الوقت t من الملاحظة السابقة) مع مجموع احتمالات الوصول إلى تلك الحالة في الوقت t، المحسوبة باستخدام احتمالات الانتقال. هذا يقلل من تعقيد المشكلة من البحث في فضاء البحث بأكمله إلى استخدام القيم المحسوبة مسبقًا فقط.${\displaystyle \alpha }$احتمالات الانتقال.

تعقيد الخوارزمية الأمامية هو${\displaystyle \Theta (nm^{2})}$، أين${\displaystyle m}$يمثل عدد الحالات الممكنة لمتغير كامن (مثل عدد الظروف الجوية في المثال أعلاه)، و${\displaystyle n}$ يمثل طول التسلسل المرصود. وهذا يُعدّ اختزالاً واضحاً عن الطريقة المخصصة لاستكشاف جميع الحالات الممكنة، والتي تتسم بتعقيد قدره${\displaystyle \Theta (nm^{n})}$.

• الخوارزمية الأمامية الهجينة : ^{[ 1 ]} تُستخدم خوارزمية أمامية هجينة (HFA)، وهي نوع مُعدّل من الخوارزمية الأمامية، لبناء شبكات عصبية ذات دوال أساسية شعاعية (RBF) بعُقد قابلة للضبط. تُبنى شبكة RBF العصبية باستخدام خوارزميات اختيار المجموعات الفرعية التقليدية. ويُحدد هيكل الشبكة من خلال الجمع بين تكوين الشبكة الأمامي التدريجي والتحسين المستمر لمعاملات RBF. تُستخدم هذه الخوارزمية لإنتاج شبكة RBF عصبية مُقتصدة ذات قدرة عالية على التعميم بكفاءة وفعالية. ويتحقق ذلك من خلال التحديد المتزامن لهيكل الشبكة وتحسين المعاملات في فضاء المعاملات المستمر . تعالج خوارزمية HFA مشكلة الأعداد الصحيحة المختلطة الصعبة باستخدام إطار تحليلي متكامل، مما يؤدي إلى تحسين أداء الشبكة وتقليل استخدام الذاكرة اللازمة لبنائها.

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

• خوارزمية التمرير الأمامي المستمر : ^{[ 3 ]} يمكن استخدام خوارزمية التمرير الأمامي المستمر (CFA) للنمذجة غير الخطية وتحديدها باستخدام الشبكات العصبية ذات الدوال الأساسية الشعاعية (RBF). تُنفذ الخوارزمية المقترحة مهمتي بناء الشبكة وتحسين المعلمات ضمن إطار تحليلي متكامل، وتوفر ميزتين هامتين. أولاً، يمكن تحسين أداء النموذج بشكل ملحوظ من خلال التحسين المستمر للمعلمات. ثانياً، يمكن بناء التمثيل العصبي دون توليد وتخزين جميع المتغيرات المرشحة، مما يؤدي إلى تقليل استخدام الذاكرة والتعقيد الحسابي بشكل كبير.

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

تُستخدم خوارزمية التنبؤ الأمامي في الغالب في التطبيقات التي تتطلب تحديد احتمالية التواجد في حالة معينة عند معرفة تسلسل الملاحظات. يمكن تطبيق هذه الخوارزمية في أي مكان يُمكن فيه تدريب نموذج عند تلقي البيانات باستخدام خوارزمية باوم-ويلش ^{[ 5 ]} أو أي خوارزمية EM عامة . ستُخبرنا خوارزمية التنبؤ الأمامي باحتمالية البيانات بالنسبة لما هو متوقع من نموذجنا. أحد تطبيقاتها هو المجال المالي ، حيث تُساعد في اتخاذ قرارات شراء أو بيع الأصول الملموسة.

يمكن تطبيقها في جميع المجالات التي تُستخدم فيها نماذج ماركوف المخفية (HMMs). ومن أبرز تطبيقاتها مجالات معالجة اللغة الطبيعية ، مثل تحديد أجزاء الكلام والتعرف على الكلام . ^{[ 4 ]} كما تُستخدم مؤخرًا في مجال المعلوماتية الحيوية .

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

• خوارزمية فيتربي
• خوارزمية التقديم والترجيع
• خوارزمية باوم-ويلش

• يقدم كتاب راسل ونورفيج " الذكاء الاصطناعي: منهج حديث" ، بدءًا من الصفحة 570 من طبعة 2010، عرضًا موجزًا ​​لهذا الموضوع والمواضيع ذات الصلة.
• سميث، بادريك، ديفيد هيكرمان، ومايكل آي. جوردان. "شبكات الاستقلال الاحتمالي لنماذج ماركوف الاحتمالية المخفية." الحوسبة العصبية 9.2 (1997): 227-269.
• ريد، جوناثان. "نماذج ماركوف المخفية والبرمجة الديناميكية". جامعة أوسلو (2011).
• كولشاين، كريستيان، مقدمة في نماذج ماركوف المخفية
• مانغانييلو، فابيو، وميركو ماركيتي، وميشيل كولاجاني. الكشف عن الهجمات متعددة المراحل وربط التنبيهات في أنظمة كشف التسلل. أمن المعلومات وضمانها. سبرينغر برلين هايدلبرغ، 2011. 101-110.
• تشانغ، بينغ، وكريستوس جي. كاساندراس. "خوارزمية أمامية محسنة للتحكم الأمثل في فئة من الأنظمة الهجينة." معاملات التحكم الآلي، IEEE 47.10 (2002): 1735-1739.
• ستراتونوفيتش، آر إل "عمليات ماركوف الشرطية". نظرية الاحتمالات وتطبيقاتها 5، العدد 2 (1960): 156178.

• تحتوي حزمة R الخاصة بنموذج ماركوف المخفي على وظائف لحساب واسترجاع الإجراء الأمامي
• توفر حزمة momentuHMM R أدوات لاستخدام واستنتاج نماذج ماركوف المخفية (HMMs).
• مكتبة GHMM للغة بايثون
• تقوم مكتبة Haskell الخاصة بحزمة hmm بتنفيذ خوارزمية Forward.
• تحتوي مكتبة جافا على تطبيقات خوارزميات التعلم الآلي والذكاء الاصطناعي.