อัลกอริทึมแบบเดินหน้า-ถอยหลัง (Forward-Backward Algorithm)เป็นอัลกอริทึมการอนุมาน สำหรับ แบบจำลองมาร์คอฟแบบซ่อน เร้น (Hidden Markov Model)ซึ่งคำนวณค่า มาร์จินัล ภายหลัง (Posterior Marginal Distribution ) ของตัวแปรสถานะซ่อนเร้นทั้งหมด โดยกำหนดลำดับของการสังเกต/การปล่อยสัญญาณ กล่าวคือมันคำนวณการแจกแจงสำหรับตัวแปรสถานะซ่อนเร้นทั้งหมดงานอนุมานนี้มักเรียกว่าการปรับเรียบ (Smoothing ) อัลกอริทึมนี้ใช้หลักการของการเขียนโปรแกรมเชิงพลวัต (Dynamic Programming)เพื่อคำนวณค่าที่จำเป็นในการได้มาซึ่งการแจกแจงมาร์จินัลภายหลังอย่างมีประสิทธิภาพในสองรอบ รอบแรกเดินหน้าไปตามเวลา ในขณะที่รอบที่สองถอยหลังไปตามเวลา ดังนั้นจึงได้ชื่อว่า อัลกอริทึม แบบ เดินหน้า-ถอยหลัง${\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})}$

คำว่าอัลกอริทึมแบบเดินหน้า-ถอยหลังยังใช้เพื่ออ้างถึงอัลกอริทึมใดๆ ที่อยู่ในกลุ่มอัลกอริทึมทั่วไปที่ทำงานกับแบบจำลองลำดับในลักษณะเดินหน้า-ถอยหลัง ในแง่นี้ คำอธิบายในส่วนที่เหลือของบทความนี้จึงอ้างถึงเพียงตัวอย่างเฉพาะเจาะจงหนึ่งตัวอย่างของกลุ่มนี้เท่านั้น

ในขั้นตอนแรก อัลกอริทึมแบบไปข้างหน้า-ย้อนกลับจะคำนวณชุดความน่าจะเป็นไปข้างหน้า ซึ่งให้ความน่าจะเป็นของการไปอยู่ในสถานะใดสถานะหนึ่งโดยเฉพาะ สำหรับทุกค่า t โดยพิจารณาจากการสังเกตครั้งแรกในลำดับนั่น คือ t = 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. คำนวณค่าที่ปรับให้เรียบแล้ว

ขั้นตอนการส่งต่อและย้อนกลับอาจเรียกว่า "การส่งข้อความไปข้างหน้า" และ "การส่งข้อความย้อนกลับ" ก็ได้ คำศัพท์เหล่านี้มาจาก วิธี การส่งข้อความ ที่ใช้ในแนวทาง การแพร่กระจายความเชื่อทั่วไปในแต่ละการสังเกตในลำดับ จะมีการคำนวณความน่าจะเป็นที่จะใช้ในการคำนวณในการสังเกตครั้งถัดไป ขั้นตอนการปรับให้เรียบสามารถคำนวณได้พร้อมกันในระหว่างการส่งผ่านย้อนกลับ ขั้นตอนนี้ช่วยให้อัลกอริธึมสามารถนำการสังเกตผลลัพธ์ในอดีตมาพิจารณาเพื่อคำนวณผลลัพธ์ที่แม่นยำยิ่งขึ้น

อัลกอริทึมแบบเดินหน้า-ถอยหลังสามารถใช้เพื่อค้นหาสถานะที่มีความเป็นไปได้มากที่สุดสำหรับจุดเวลาใดๆ ก็ได้ อย่างไรก็ตาม ไม่สามารถใช้เพื่อค้นหาลำดับของสถานะที่มีความเป็นไปได้มากที่สุดได้ (ดูอัลกอริทึมของ Viterbi )

คำอธิบายต่อไปนี้จะใช้เมทริกซ์ของค่าความน่าจะเป็นแทนการแจกแจงความน่าจะเป็น อย่างไรก็ตาม โดยทั่วไปแล้วอัลกอริทึมแบบเดินหน้า-ถอยหลังสามารถนำไปใช้กับแบบจำลองความน่าจะเป็นทั้งแบบต่อเนื่องและแบบไม่ต่อเนื่องได้

เราแปลงการแจกแจงความน่าจะเป็นที่เกี่ยวข้องกับแบบจำลองมาร์คอฟที่ซ่อนอยู่ให้เป็นสัญกรณ์เมทริกซ์ดังต่อไปนี้ ความน่าจะเป็นของการเปลี่ยนสถานะของตัวแปรสุ่มที่กำหนดซึ่งแสดงถึงสถานะที่เป็นไปได้ทั้งหมดในแบบจำลองมาร์คอฟที่ซ่อนอยู่จะถูกแทนด้วยเมทริกซ์โดยที่ดัชนีคอลัมน์จะแสดงถึงสถานะเป้าหมาย และดัชนีแถวจะแสดงถึงสถานะเริ่มต้น การเปลี่ยนสถานะจากสถานะเวกเตอร์แถวไปยังสถานะเวกเตอร์แถวที่เพิ่มขึ้นจะเขียนเป็นตัวอย่างด้านล่างแสดงถึงระบบที่ความน่าจะเป็นของการคงอยู่ในสถานะเดิมหลังจากแต่ละขั้นตอนคือ 70% และความน่าจะเป็นของการเปลี่ยนไปยังสถานะอื่นคือ 30% ดังนั้นเมทริกซ์การเปลี่ยนสถานะคือ: ${\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} }$

${\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% เมื่อกำหนดเวกเตอร์แถวใดๆ ที่อธิบายสถานะของระบบ ( ) ความน่าจะเป็นของการสังเกตเหตุการณ์ j คือ: ${\displaystyle \mathbf {\pi } }$

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

ความน่าจะเป็นของสถานะที่กำหนดซึ่งนำไปสู่เหตุการณ์ที่สังเกตได้ j สามารถแสดงในรูปแบบเมทริกซ์ได้โดยการคูณเวกเตอร์แถวของสถานะ ( ) กับเมทริกซ์การสังเกต ( ) ที่มีเฉพาะค่าในแนวทแยงมุมเท่านั้น จากตัวอย่างข้างต้น เมทริกซ์การสังเกตสำหรับเหตุการณ์ที่ 1 จะเป็นดังนี้: ${\displaystyle \mathbf {\pi } }$${\displaystyle \mathbf {O_{j}} =\mathrm {diag} (B_{*,o_{j}})}$

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

วิธีนี้ช่วยให้เราสามารถคำนวณเวกเตอร์สถานะความน่าจะเป็นที่ไม่ได้รับการปรับมาตรฐานใหม่โดยใช้กฎของเบย์ส โดยถ่วงน้ำหนักด้วยความน่าจะเป็นที่แต่ละองค์ประกอบของเหตุการณ์ที่สร้างขึ้น 1 ดังนี้: ${\displaystyle \mathbf {\pi '} }$${\displaystyle \mathbf {\pi } }$

${\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}}} }$

โดยที่แทนเวกเตอร์ที่ปรับขนาดแล้วจากขั้นตอนก่อนหน้า และแทนตัวประกอบการปรับขนาดที่ทำให้ผลรวมของค่าในเวกเตอร์ที่ได้เท่ากับ 1 ผลคูณของตัวประกอบการปรับขนาดคือความน่าจะเป็นทั้งหมดสำหรับการสังเกตเหตุการณ์ที่กำหนดโดยไม่คำนึงถึงสถานะสุดท้าย: ${\displaystyle \mathbf {{\hat {f}}_{0:t-1}} }$${\displaystyle c_{t}}$

${\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})}$

กล่าวคือ ตอนนี้เราต้องการสมมติว่าเราเริ่มต้นในสถานะเฉพาะ ( ) และตอนนี้เราสนใจความน่าจะเป็นของการสังเกตเหตุการณ์ในอนาคตทั้งหมดจากสถานะนี้ เนื่องจากสถานะเริ่มต้นถือว่ากำหนดไว้แล้ว (นั่นคือ ความน่าจะเป็นก่อนหน้าของสถานะนี้ = 100%) เราจึงเริ่มต้นด้วย: ${\displaystyle X_{t}=x_{i}}$

${\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)}$

เพื่อให้เข้าใจเรื่องนี้ เราต้องสังเกตว่าแสดงถึงความน่าจะเป็นในการสังเกตเหตุการณ์ที่กำหนดในลักษณะที่ผ่านสถานะณ เวลา t ความน่าจะเป็นนี้รวมถึงความน่าจะเป็นไปข้างหน้าซึ่งครอบคลุมเหตุการณ์ทั้งหมดจนถึงเวลา t รวมถึงความน่าจะเป็นย้อนหลังซึ่งรวมถึงเหตุการณ์ในอนาคตทั้งหมด นี่คือตัวเศษที่เรากำลังมองหาในสมการของเรา และเราหารด้วยความน่าจะเป็นทั้งหมดของลำดับการสังเกตเพื่อทำให้ค่านี้เป็นค่ามาตรฐานและดึงเฉพาะความน่าจะเป็นที่ค่าเหล่านี้บางครั้งเรียกว่า "ค่าที่ปรับเรียบแล้ว" เนื่องจากเป็นการรวมความน่าจะเป็นไปข้างหน้าและย้อนหลังเข้าด้วยกันเพื่อคำนวณความน่าจะเป็นสุดท้าย ${\displaystyle \mathbf {f_{0:t}} (i)\cdot \mathbf {b_{t:T}} (i)}$${\displaystyle x_{i}}$${\displaystyle X_{t}=x_{i}}$

ค่าเหล่านี้จึงให้ความน่าจะเป็นของการอยู่ในแต่ละสถานะ ณ เวลา t ดังนั้นจึงมีประโยชน์ในการกำหนดสถานะที่มีความน่าจะเป็นสูงสุด ณ เวลาใดๆ คำว่า "สถานะที่มีความน่าจะเป็นสูงสุด" นั้นค่อนข้างกำกวม แม้ว่าสถานะที่มีความน่าจะเป็นสูงสุดจะเป็นสถานะที่มีโอกาสถูกต้องมากที่สุด ณ จุดใดจุดหนึ่ง แต่ลำดับของสถานะที่มีความน่าจะเป็นแต่ละสถานะอาจไม่ใช่ลำดับที่มีความน่าจะเป็นสูงสุด เนื่องจากความน่าจะเป็นสำหรับแต่ละจุดคำนวณอย่างอิสระจากกัน ไม่ได้คำนึงถึงความน่าจะเป็นของการเปลี่ยนสถานะ ดังนั้นจึงเป็นไปได้ที่จะได้สถานะ ณ สองช่วงเวลา (t และ t+1) ที่ทั้งสองสถานะมีความน่าจะเป็นสูงสุด ณ จุดเวลาเหล่านั้น แต่มีความน่าจะเป็นที่จะเกิดขึ้นพร้อมกันน้อยมากลำดับของสถานะที่มีความน่าจะเป็นสูงสุดที่สร้างลำดับการสังเกตสามารถหาได้โดยใช้ อัลกอริ ทึม Viterbi${\displaystyle \mathbf {\gamma _{t}} (i)}$${\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})}$

ตัวอย่างนี้อ้างอิงจากโลกแห่งร่มใน หนังสือของ Russell & Norvig ปี 2010 บทที่ 15 หน้า 567ซึ่งเราต้องการอนุมานสภาพอากาศจากการสังเกตบุคคลอื่นว่าถือร่มหรือไม่ถือร่ม เราสมมติว่าสภาพอากาศมีสองสถานะที่เป็นไปได้ คือ สถานะที่ 1 = ฝนตก สถานะที่ 2 = ไม่ฝนตก เราสมมติว่าสภาพอากาศมีโอกาส 70% ที่จะคงที่ในแต่ละวัน และมีโอกาส 30% ที่จะเปลี่ยนแปลง ความน่าจะเป็นของการเปลี่ยนสถานะจึงเป็นดังนี้:

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

นอกจากนี้ เรายังสมมติว่าแต่ละสถานะจะสร้างเหตุการณ์ที่เป็นไปได้ 1 ใน 2 เหตุการณ์ ได้แก่ เหตุการณ์ที่ 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 เนื่องจากเราไม่ได้ปรับขนาดความน่าจะเป็นย้อนหลังด้วยค่า's ที่พบก่อนหน้านี้ เวกเตอร์ความน่าจะเป็นย้อนหลังข้างต้นจึงแสดงถึงความน่าจะเป็นของแต่ละสถานะ ณ เวลา t โดยพิจารณาจากการสังเกตในอนาคต เนื่องจากเวกเตอร์เหล่านี้เป็นสัดส่วนกับความน่าจะเป็นย้อนหลังที่แท้จริง ผลลัพธ์จึงต้องถูกปรับขนาดอีกครั้งหนึ่ง ${\displaystyle c_{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}}}$

โปรดสังเกตว่าค่าของเท่ากับและเท่ากับ ซึ่งเป็นไปตามธรรมชาติเพราะทั้งและเริ่มต้นด้วยค่าความน่าจะเป็นล่วงหน้าแบบสม่ำเสมอ (uniform priors) สำหรับเวกเตอร์สถานะเริ่มต้นและสถานะสุดท้าย (ตามลำดับ) และคำนึงถึงการสังเกตทั้งหมด อย่างไรก็ตามจะมีค่าเท่ากับ ก็ต่อเมื่อเวกเตอร์สถานะเริ่มต้นของเราแสดงถึงค่าความน่าจะเป็นล่วงหน้าแบบสม่ำเสมอ (กล่าวคือ ค่าทั้งหมดเท่ากัน) เมื่อไม่ใช่เช่นนั้นจะต้องนำมารวมกับเวกเตอร์สถานะเริ่มต้นเพื่อหาสถานะเริ่มต้นที่มีความเป็นไปได้มากที่สุด ดังนั้นเราจึงพบว่าความน่าจะเป็นไปข้างหน้าเพียงอย่างเดียวก็เพียงพอที่จะคำนวณสถานะสุดท้ายที่มีความเป็นไปได้มากที่สุด ในทำนองเดียวกัน ความน่าจะเป็นย้อนกลับสามารถนำมารวมกับเวกเตอร์สถานะเริ่มต้นเพื่อให้ได้สถานะเริ่มต้นที่มีความเป็นไปได้มากที่สุดเมื่อพิจารณาจากการสังเกต ความน่าจะเป็นไปข้างหน้าและย้อนกลับจำเป็นต้องนำมารวมกันเพื่ออนุมานสถานะที่มีความเป็นไปได้มากที่สุดระหว่างจุดเริ่มต้นและจุดสุดท้าย ${\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}} }$

อัลกอริทึมแบบเดินหน้า-ถอยหลังทำงานด้วยความซับซ้อนของเวลาในพื้นที่โดยที่คือความยาวของลำดับเวลา และคือจำนวนสัญลักษณ์ในตัวอักษรสถานะ^{[ 1 ]} อัลกอริทึมยังสามารถทำงานในพื้นที่คงที่ด้วยความซับซ้อนของเวลาโดยการคำนวณค่าใหม่ในแต่ละขั้นตอน^{[ 2 ]}สำหรับการเปรียบเทียบขั้นตอนวิธีแบบใช้กำลังทั้งหมดจะสร้างลำดับสถานะที่เป็นไปได้ทั้งหมดและคำนวณความน่าจะเป็นร่วมของแต่ละลำดับสถานะกับชุดเหตุการณ์ที่สังเกตได้ ซึ่งจะมีความซับซ้อนของเวลาการใช้กำลังทั้งหมดไม่สามารถทำได้สำหรับปัญหาที่สมจริง เนื่องจากจำนวนลำดับโหนดที่ซ่อนอยู่ที่เป็นไปได้มักจะสูงมาก ${\displaystyle O(S^{2}T)}$${\displaystyle O(ST)}$${\displaystyle T}$${\displaystyle S}$${\displaystyle O(S^{2}T^{2})}$${\displaystyle S^{T}}$${\displaystyle O(T\cdot S^{T})}$

การปรับปรุงอัลกอริทึมแบบเดินหน้า-ถอยหลังทั่วไปที่เรียกว่าอัลกอริทึม Islandแลกเปลี่ยนการใช้หน่วยความจำที่น้อยลงกับเวลาการทำงานที่ยาวนานขึ้น ซึ่งใช้เวลาและหน่วยความจำ นอกจากนี้ ยังสามารถกลับแบบจำลองกระบวนการเพื่อให้ได้ อัลกอริทึม แบบพื้นที่และเวลาได้ แม้ว่ากระบวนการที่กลับด้านอาจไม่มีอยู่จริงหรือมีเงื่อนไขที่ไม่ดีก็ตาม^{[ 3 ]}${\displaystyle O(S^{2}T\log T)}$${\displaystyle O(S\log T)}$${\displaystyle O(S)}$${\displaystyle O(S^{2}T)}$

นอกจากนี้ ยังมีการพัฒนาอัลกอริธึมเพื่อคำนวณอย่างมีประสิทธิภาพผ่านการปรับเรียบแบบออนไลน์ เช่น อัลกอริธึมการปรับเรียบแบบหน่วงเวลาคงที่ (FLS) ^{[ 4 ]}${\displaystyle \mathbf {f_{0:t+1}} }$

อัลกอริทึม forward_backward รับอินพุตเป็น guessState ผลลัพธ์ของ int sequenceIndex : ผลลัพธ์ถ้าsequenceIndexเกินกว่าจุดสิ้นสุดของลำดับให้คืนค่า 1 ถ้า ( guessState , sequenceIndex ) เคยเห็นมาก่อนแล้วให้คืนค่าผลลัพธ์ที่บันทึกไว้ ผลลัพธ์  := 0 สำหรับแต่ละสถานะข้างเคียง n: ผลลัพธ์  := ผลลัพธ์ + (ความน่าจะเป็นของการเปลี่ยนสถานะจากguessStateไปยัง n องค์ประกอบการสังเกตที่กำหนดที่sequenceIndex ) × ย้อนกลับ(n, ดัชนีลำดับ + 1) บันทึกผลลัพธ์สำหรับ ( guessState , sequenceIndex ) ส่งคืนผลลัพธ์

เมื่อกำหนด HMM (เช่นเดียวกับในอัลกอริธึม Viterbi ) ที่แสดงในภาษาการเขียนโปรแกรม Python แล้ว :

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 }, }

เราสามารถเขียนการใช้งานอัลกอริธึมไปข้างหน้าและย้อนกลับได้ดังนี้:

def fwd_bkw ( observations , states , start_prob , trans_prob , emm_prob , end_st ): """อัลกอริทึมแบบเดินหน้า-ถอยหลัง""" # ส่วนเดินหน้าของอัลกอริทึมfwd = [] for i , observation_i in enumerate ( observations ): f_curr = {} for st in states : if i == 0 : # กรณีพื้นฐานสำหรับส่วนเดินหน้าprev_f_sum = start_prob [ st ] else : prev_f_sum = sum ( f_prev [ k ] * trans_prob [ k ][ st ] for k in states )f_curr [ st ] = emm_prob [ st ][ observation_i ] * prev_f_sumfwd.append ( f_curr ) f_prev = f_curr​​p_fwd = ผลรวม( f_curr [ k ] * trans_prob [ k ][ end_st ] สำหรับk ในstates )# ส่วนย้อนกลับของอัลกอริทึมbkw = [] สำหรับi , observation_i_plus ในenumerate ( reversed ( observations [ 1 :] + ( None ,))): b_curr = {} สำหรับst ในstates : ถ้าi == 0 : # กรณีพื้นฐานสำหรับส่วนย้อนกลับb_curr [ st ] = trans_prob [ st ][ end_st ] มิฉะนั้น: b_curr [ st ] = sum ( trans_prob [ st ][ l ] * emm_prob [ l ][ observation_i_plus ] * b_prev [ l ] สำหรับl ในstates )bkw.insert ( 0 , b_curr ) b_prev = b_curr​​p_bkw = ผลรวม( start_prob [ l ] * emm_prob [ l ][ observations [ 0 ]] * b_curr [ l ] สำหรับl ใน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 , )

>>> สำหรับแต่ละบรรทัดในตัวอย่าง(): ... พิมพ์( * บรรทัด) ... {'สุขภาพดี': 0.3, 'ไข้': 0.04000000000000001} {'สุขภาพดี': 0.0892, 'ไข้': 0.03408} {'สุขภาพดี': 0.007518, 'ไข้': 0.028120319999999997} {'สุขภาพดี': 0.0010418399999999998, 'ไข้': 0.00109578} {'สุขภาพดี': 0.00249, 'ไข้': 0.00394} {'สุขภาพดี': 0.01, 'ไข้': 0.01} {'สุขภาพดี': 0.8770110375573259, 'ไข้': 0.1229889624426741} {'สุขภาพดี': 0.623228030950954, 'ไข้': 0.3767719690490461} {'สุขภาพดี': 0.2109527048413057, 'ไข้': 0.7890472951586943}

• อัลกอริทึม Baum–Welch
• อัลกอริทึมวิเทอร์บี
• อัลกอริทึม BCJR

• สเปรดชีตแบบโต้ตอบสำหรับการสอนอัลกอริทึมแบบเดินหน้า-ถอยหลัง (สเปรดชีตและบทความพร้อมคำแนะนำทีละขั้นตอน)
• บทแนะนำเกี่ยวกับแบบจำลองมาร์คอฟที่ซ่อนอยู่ รวมถึงอัลกอริธึมแบบเดินหน้า-ถอยหลัง
• รวมชุดอัลกอริธึม AI ที่เขียนด้วยภาษา Java (รวมถึง HMM และอัลกอริธึมเดินหน้า-ถอยหลัง)