เรียนรู้ Kalman Filter ตั้งแต่พื้นฐาน
(kalmanfilter.net)- Kalman Filter เป็นอัลกอริทึมสำหรับประมาณสถานะปัจจุบันและทำนายอนาคตของระบบที่มี สัญญาณรบกวนในการวัด และปัจจัยภายนอกที่ไม่ทราบค่า โดยใช้ในงานอย่างการติดตาม วงการนำทาง หุ่นยนต์ และการควบคุม
- ตัวอย่างเรดาร์แบบ 1 มิติจะวัดระยะทาง (r) และความเร็ว (v) ของเครื่องบิน โดยใช้เวกเตอร์สถานะ (\boldsymbol{x}=[r, v]^T) และเมทริกซ์โคเวเรียนซ์ (\boldsymbol{P}, \boldsymbol{R}, \boldsymbol{Q}) เพื่อจัดการทั้ง สถานะและความไม่แน่นอน ไปพร้อมกัน
- ค่าการวัดเริ่มต้นคือระยะทาง 10,000m และความเร็ว 200m/s และเมื่อใช้ช่วงเวลาสุ่มตัวอย่าง 5 วินาทีร่วมกับแบบจำลองความเร็วคงที่ จะได้การทำนายตำแหน่งถัดไปเป็น 11,000m
- ขั้นตอนการทำนายจะใช้เมทริกซ์เปลี่ยนผ่านสถานะ (\boldsymbol{F}) เพื่อส่งต่อสถานะ และคำนวณโคเวเรียนซ์ด้วย (\boldsymbol{F}\boldsymbol{P}\boldsymbol{F}^T+\boldsymbol{Q}) เพื่อสะท้อนผลที่ความไม่แน่นอนของความเร็วและ สัญญาณรบกวนของกระบวนการ ทำให้ความไม่แน่นอนของตำแหน่งเพิ่มขึ้น
- ขั้นตอนการอัปเดตจะไม่เชื่อการวัดใหม่ทั้งหมดหรือทิ้งมันไป แต่ใช้ Kalman Gain มาถ่วงน้ำหนักรวมการทำนายกับการวัดเพื่อลดความไม่แน่นอนของการประมาณค่า จากนั้นฟิลเตอร์จะทำซ้ำขั้นตอนทำนายและอัปเดตต่อไป
ปัญหาที่ Kalman Filter จัดการ
- Kalman Filter เป็นอัลกอริทึมที่ทำ การประมาณสถานะ และ การทำนายอนาคต ในระบบที่มีความไม่แน่นอน
- ใช้กับสถานการณ์ที่มีสัญญาณรบกวนในการวัด หรือมีปัจจัยภายนอกที่ไม่ทราบซึ่งส่งผลต่อระบบ
- เป็นเครื่องมือสำคัญในงานติดตามวัตถุ การนำทาง หุ่นยนต์ และการควบคุม
- ในการประมาณเส้นทางของเมาส์คอมพิวเตอร์ สามารถลดอาการมือสั่นและสัญญาณรบกวนเพื่อให้เส้นทางการเคลื่อนที่นิ่งขึ้น
- ในการวิเคราะห์ตลาดการเงิน ใช้ตรวจจับแนวโน้มราคาหุ้นจากข้อมูลตลาดที่มีสัญญาณรบกวน และในด้านอุตุนิยมวิทยาก็นำไปใช้กับการพยากรณ์อากาศ
- บทเรียนนี้เลือกสร้างความเข้าใจจาก ตัวอย่างเชิงตัวเลข แทนการเริ่มจากคณิตศาสตร์ที่ซับซ้อนก่อน
- รวมถึงตัวอย่าง Kalman Filter ที่ออกแบบไม่ดีจนติดตามวัตถุได้ไม่ถูกต้อง
- ตั้งเป้าให้เข้าใจทั้งแนวคิดและคณิตศาสตร์จนสามารถออกแบบและนำไปใช้งานเองได้
เส้นทางการเรียนรู้
- เส้นทางการเรียนรู้ที่มีให้แบ่งเป็น สามขั้นตอน
- ภาพรวมหน้าเดียว: อธิบายแนวคิดหลักและสมการสำคัญโดยไม่ลงรายละเอียดการพิสูจน์ และสมมติว่าผู้อ่านมีพื้นฐานสถิติและพีชคณิตเชิงเส้น
- เว็บทิวทอเรียลฟรีที่อิงตัวอย่าง: tutorial จะค่อย ๆ สร้างความเข้าใจจากตัวอย่างเชิงตัวเลขไปจนถึงการอนุมานสมการ Kalman Filter
- หนังสือ: Kalman Filter from the Ground Up มีตัวอย่างเชิงตัวเลขพร้อมวิธีทำครบ 14 ตัวอย่าง กราฟและตารางประสิทธิภาพ, Extended Kalman Filter และ Unscented Kalman Filter, sensor fusion และแนวทางการนำไปใช้งานจริง
ทำไมการติดตามด้วยเรดาร์จึงต้องมีการทำนาย
- ถ้าเรดาร์ต้องการติดตามเครื่องบิน จะต้องเล็งลำแสงแคบไปยังทิศทางของเป้าหมายซ้ำ ๆ ดังนั้นจึงต้องทำนาย ตำแหน่งในอนาคต ตอนที่จะส่งลำแสงครั้งถัดไป
- หากทำนายพลาด ลำแสงอาจหันไปผิดทิศและสูญเสียการติดตามได้
- จึงจำเป็นต้องมี แบบจำลองพลวัต ที่อธิบายว่าเครื่องบินเคลื่อนที่อย่างไรตามเวลา
- ในตัวอย่างแบบ 1 มิติที่ย่อให้ง่าย จะพิจารณาเฉพาะการเคลื่อนที่เป็นเส้นตรงของเครื่องบินที่เข้าหาเรดาร์หรือถอยห่างออกไป
- สถานะนิยามด้วยระยะทาง (r) จากเรดาร์
- เรดาร์คำนวณระยะทาง (r) จากเวลาส่งรับพัลส์และความเร็วแสง
- และยังวัดความเร็ว (v) ได้จากปรากฏการณ์ Doppler
- สมมติว่า ณ (t_0) วัดระยะทาง 10,000m และความเร็ว 200m/s ได้ด้วยความถูกต้องและความแม่นยำสูงมาก
- ช่วงเวลาสุ่มตัวอย่างคือ (\Delta t=5s)
- ในแบบจำลองความเร็วคงที่ ระยะที่เคลื่อนที่คือ (\Delta r=v\cdot\Delta t)
- ตำแหน่งที่ทำนายได้คือ (10,000+200\cdot5=11,000m)
สัญญาณรบกวนในการวัดและสัญญาณรบกวนของกระบวนการ
- การวัดของเรดาร์จริงไม่ได้สมบูรณ์แบบ แม้เรดาร์หลายตัวจะวัดเครื่องบินลำเดียวกันในเวลาเดียวกัน ก็ยังได้ผลต่างกันเล็กน้อย
- ความแปรผันนี้เกิดจาก สัญญาณรบกวนในการวัด
- จึงต้องคำนวณไม่ใช่แค่ค่าประมาณ แต่รวมถึงความน่าเชื่อถือของค่าประมาณนั้นด้วย
- แบบจำลองพลวัตเองก็อธิบายการเคลื่อนที่จริงได้ไม่ครบถ้วน
- แม้จะสมมติว่าเครื่องบินเคลื่อนที่ด้วยความเร็วคงที่ ปัจจัยภายนอกอย่างลมก็อาจเปลี่ยนการเคลื่อนที่จริงได้
- อิทธิพลที่คาดเดาไม่ได้เหล่านี้จัดการด้วย สัญญาณรบกวนของกระบวนการ
- Kalman Filter ให้ทั้งค่าประมาณสถานะปัจจุบัน การทำนายสถานะในอนาคต และ ความไม่แน่นอน ของแต่ละส่วนไปพร้อมกัน
- ถูกอธิบายว่าเป็นอัลกอริทึมเชิงเหมาะที่สุดที่ลดความไม่แน่นอนของการประมาณสถานะให้ต่ำที่สุด
การแทนสถานะและการกำหนดค่าเริ่มต้นในตัวอย่างเรดาร์
- สถานะของระบบในตัวอย่างเป็นเวกเตอร์ที่มีระยะทาง (r) และความเร็ว (v) ของเครื่องบิน
[ \boldsymbol{x}=\left[\begin{matrix}r\v\\end{matrix}\right] ]
- เวกเตอร์เขียนด้วยตัวหนาพิมพ์เล็ก ส่วนเมทริกซ์เขียนด้วยตัวหนาพิมพ์ใหญ่
- Kalman Filter ถูกกำหนดค่าเริ่มต้นจากการวัดครั้งแรก
- ณ (t_0) ค่าที่วัดได้คือระยะทาง 10,000m และความเร็ว 200m/s
- เวกเตอร์การวัดเป็นดังนี้
[ \boldsymbol{z}_0=\left[\begin{matrix}10{,}000\200\\end{matrix}\right] ]
- ค่าที่วัดได้ไม่ใช่สถานะจริงของระบบ แต่เป็น ตัวแปรสุ่ม ที่มีสัญญาณรบกวนปนอยู่
- ส่วนเบี่ยงเบนมาตรฐานของการวัดระยะทางคือ (4m)
- ส่วนเบี่ยงเบนมาตรฐานของการวัดความเร็วคือ (0.5m/s)
- เนื่องจากความแปรปรวนคือกำลังสองของส่วนเบี่ยงเบนมาตรฐาน เมทริกซ์โคเวเรียนซ์ของการวัด (\boldsymbol{R}_0) จึงเป็นดังนี้
[ \boldsymbol{R}_0=\left[\begin{matrix}16&0\0&0.25\\end{matrix}\right] ]
- ในตัวอย่างนี้สมมติว่าความคลาดเคลื่อนของการวัดระยะทางและความเร็วไม่เกี่ยวข้องกัน จึงให้สมาชิกนอกแนวทแยงของเมทริกซ์โคเวเรียนซ์เป็น 0
- ในช่วงเริ่มต้นมีเพียงการวัดครั้งเดียว จึงใช้ค่าการวัดเป็นค่าประมาณสถานะเริ่มต้นได้
[ \boldsymbol{\hat{x}}_{0,0}=\boldsymbol{z}_0=\left[\begin{matrix}10{,}000\200\\end{matrix}\right] ]
- วิธีนี้ใช้ได้เฉพาะใน ขั้นตอนการกำหนดค่าเริ่มต้น เท่านั้น
ขั้นตอนการทำนาย: ส่งต่อสถานะและโคเวเรียนซ์
- เพื่อทำนายสถานะถัดไป จะใช้แบบจำลองพลวัตแบบความเร็วคงที่
[ v_1=v_0=v ]
[ r_1=r_0+v_0\Delta t ]
- การทำนายสถานะแบบเมทริกซ์เป็นดังนี้
[ {\hat{\boldsymbol{x}}}{1,0}=\boldsymbol{F}{\hat{\boldsymbol{x}}}{0,0} ]
- (\boldsymbol{F}) คือ เมทริกซ์เปลี่ยนผ่านสถานะ และเมื่อ (\Delta t=5s) ผลการทำนายจะเป็นดังนี้
[ {\hat{\boldsymbol{x}}}_{1,0}
\left[\begin{matrix}1&5\0&1\\end{matrix}\right] \left[\begin{matrix}10,000\200\\end{matrix}\right]
\left[\begin{matrix}11,000\200\\end{matrix}\right] ]
- สมการ extrapolation ของสถานะทั่วไป หรือสมการทำนาย คือดังนี้
[ {\hat{\boldsymbol{x}}}{n+1,n}=\boldsymbol{F}{\hat{\boldsymbol{x}}}{n,n}+\boldsymbol{G}\boldsymbol{u}_n ]
- (\boldsymbol{u}_n) คือตัวแปรอินพุต
- (\boldsymbol{G}) คือเมทริกซ์เปลี่ยนผ่านอินพุต
- ในตัวอย่างนี้ไม่มีอินพุต ดังนั้น (\boldsymbol{u}_n=0)
- โคเวเรียนซ์ไม่ได้คำนวณเพียงด้วย (\boldsymbol{F}\boldsymbol{P}) แบบตรง ๆ
- เพราะโคเวเรียนซ์มี พจน์กำลังสอง ของความแปรปรวนและโคเวเรียนซ์รวมอยู่ด้วย
- เมื่อไม่มีสัญญาณรบกวนของกระบวนการ สมการ extrapolation ของโคเวเรียนซ์เป็นดังนี้
[ \boldsymbol{P}{n+1,n}=\boldsymbol{F}\boldsymbol{P}{n,n}\boldsymbol{F}^T ]
- เมื่อนำโคเวเรียนซ์เริ่มต้น (\boldsymbol{P}_{0,0}) ในตัวอย่างมาส่งต่อ จะได้ผลดังนี้
[ \boldsymbol{P}_{1,0}
\left[\begin{matrix}22.25&1.25\1.25&0.25\\end{matrix}\right] ]
- ความแปรปรวนของความเร็วคงอยู่ที่ (0.25m^2/s^2)
- ความแปรปรวนของระยะทางเพิ่มจาก (16m^2) เป็น (22.25m^2)
- ความไม่แน่นอนของความเร็วเมื่อเวลาผ่านไปจะกลายเป็นความไม่แน่นอนของระยะทาง
การสะท้อนสัญญาณรบกวนของกระบวนการ
- การสมมติความเร็วคงที่เพียงอย่างเดียวอธิบายการเคลื่อนที่จริงของเครื่องบินได้ไม่ครบถ้วน
- ปัจจัยภายนอกที่ไม่ทราบ เช่น ลม อาจส่งผลต่อความเร็วได้
- อิทธิพลที่คาดเดาไม่ได้เหล่านี้แทนด้วย สัญญาณรบกวนของกระบวนการ (\boldsymbol{Q})
- สมการทำนายโคเวเรียนซ์เมื่อรวมสัญญาณรบกวนของกระบวนการเป็นดังนี้
[ \boldsymbol{P}{n+1,n}=\boldsymbol{F}\boldsymbol{P}{n,n}\boldsymbol{F}^T+\boldsymbol{Q} ]
- ในตัวอย่างนี้สมมติว่าส่วนเบี่ยงเบนมาตรฐานของความเร่งแบบสุ่มคือ (\sigma_a=0.2m/s^2)
- ความแปรปรวนคือ (\sigma_a^2=0.04m^2/s^4)
- เมื่อ (\Delta t=5s) เมทริกซ์สัญญาณรบกวนของกระบวนการเป็นดังนี้
[ \boldsymbol{Q}
\left[\begin{matrix}6.25&2.5\2.5&1\\end{matrix}\right] ]
- โคเวเรียนซ์ที่ทำนายได้เมื่อรวมสัญญาณรบกวนของกระบวนการแล้วเป็นดังนี้
[ \boldsymbol{P}_{1,0}
\left[\begin{matrix}28.5&3.75\3.75&1.25\\end{matrix}\right] ]
ขั้นตอนการอัปเดต: รวมการวัดเข้ากับการทำนาย
- ณ (t_1) ค่าการวัดครั้งที่สองเป็นดังนี้
[ \boldsymbol{z}_1= \left[\begin{matrix}11{,}020\202\\end{matrix}\right] ]
- การวัดนี้มีความไม่แน่นอนมากกว่าครั้งแรก เพราะมีสไปก์ของสัญญาณรบกวนรุนแรงทำให้อัตราส่วนสัญญาณต่อสัญญาณรบกวนต่ำกว่า
- ส่วนเบี่ยงเบนมาตรฐานของการวัดระยะทางคือ (6m)
- ส่วนเบี่ยงเบนมาตรฐานของการวัดความเร็วคือ (1.5m/s)
- เมทริกซ์โคเวเรียนซ์ของการวัดเป็นดังนี้
[ \boldsymbol{R}_1= \left[\begin{matrix}36&0\0&2.25\\end{matrix}\right] ]
- ณ (t_1) เราสามารถใช้ได้ทั้ง สถานะที่ทำนายไว้ จากขั้นตอนก่อนหน้าและค่าการวัดใหม่
- สมาชิกแนวทแยงของโคเวเรียนซ์ที่ทำนาย (\boldsymbol{P}_{1,0}) คือ (28.5), (1.25)
- สมาชิกแนวทแยงของโคเวเรียนซ์การวัด (\boldsymbol{R}_1) คือ (36), (2.25)
- ในกรณีนี้ความไม่แน่นอนของการทำนายน้อยกว่าความไม่แน่นอนของการวัด
- Kalman Filter จะไม่ใช้การวัดใหม่ตรง ๆ และก็ไม่ยึดเฉพาะการทำนาย
- แต่จะรวมการทำนายและการวัดด้วย ค่าเฉลี่ยถ่วงน้ำหนัก
- ฝั่งที่มีความไม่แน่นอนต่ำกว่าจะได้รับน้ำหนักมากกว่า
- การรวมกันในรูปแบบ 1 มิติเป็นดังนี้
[ \hat{x}{1,1}=K_1z_1+(1-K_1)\hat{x}{1,0} ]
- (K_1) คือ Kalman Gain ซึ่งกำหนดว่าจะให้น้ำหนักกับการวัดและการทำนายมากน้อยเพียงใด
- ตราบใดที่สมมติฐานของแบบจำลองยังถูกต้อง มันจะลดความไม่แน่นอนของค่าประมาณหลังอัปเดตให้ต่ำที่สุด
การอัปเดตสถานะและ innovation
- สมการอัปเดตสถานะแบบเมทริกซ์เป็นดังนี้
[ \hat{\boldsymbol{x}}_{1,1}
\hat{\boldsymbol{x}}_{1,0} + \boldsymbol{K}_1(\boldsymbol{z}1-\hat{\boldsymbol{x}}{1,0}) ]
- โดยทั่วไปค่าการวัดกับสถานะของระบบอาจไม่ได้แทนปริมาณทางกายภาพเดียวกัน
- ตัวอย่างเช่น เทอร์โมมิเตอร์ดิจิทัลอาจวัดสัญญาณไฟฟ้า แต่สถานะของระบบอาจเป็นอุณหภูมิ
- ในกรณีนี้ต้องมี เมทริกซ์สังเกตการณ์ (\boldsymbol{H}) เพื่อแปลงสถานะที่ทำนายไปยังโดเมนของการวัด
- สมการอัปเดตสถานะทั่วไปเป็นดังนี้
[ \hat{\boldsymbol{x}}_{1,1}
\hat{\boldsymbol{x}}_{1,0} + \boldsymbol{K}_1(\boldsymbol{z}1-\boldsymbol{H}\hat{\boldsymbol{x}}{1,0}) ]
- (\boldsymbol{z}1-\boldsymbol{H}\hat{\boldsymbol{x}}{1,0}) คือ innovation หรือ residual ซึ่งแทนข้อมูลใหม่
- ในตัวอย่างนี้ทั้งสถานะและการวัดเป็นระยะทางและความเร็วเหมือนกัน ดังนั้น (\boldsymbol{H}) จึงเป็นเมทริกซ์เอกลักษณ์
การคำนวณ Kalman Gain
- Kalman Gain แบบ 1 มิติเป็นดังนี้
[ K_n=\frac{p_{n,n-1}}{p_{n,n-1}+r_n} ]
- (p_{n,n-1}) คือความแปรปรวนของสถานะที่ทำนาย
- (r_n) คือความแปรปรวนของการวัด
- ใน Kalman Filter แบบหลายตัวแปร Kalman Gain จะเป็นเมทริกซ์และมีรูปดังนี้
[ \boldsymbol{K}n= \boldsymbol{P}{n,n-1}\boldsymbol{H}^T \left( \boldsymbol{H}\boldsymbol{P}_{n,n-1}\boldsymbol{H}^T+\boldsymbol{R}_n \right)^{-1} ]
- Kalman Gain ที่คำนวณได้ในตัวอย่าง ณ (t_1) เป็นดังนี้
[ \boldsymbol{K}_1= \left[\begin{matrix}0.4048&0.6377\0.0399&0.3144\\end{matrix}\right] ]
- เมทริกซ์ผกผันสามารถคำนวณได้ด้วย
inv(A)ใน MATLAB หรือnumpy.linalg.inv(A)ใน Python- แต่ในการนำไปใช้จริง โดยทั่วไปการ แก้ระบบสมการเชิงเส้นโดยตรง เช่น
A\bใน MATLAB หรือnumpy.linalg.solve(A, b)ใน Python มักดีกว่าการคำนวณเมทริกซ์ผกผันแบบชัดแจ้ง
- แต่ในการนำไปใช้จริง โดยทั่วไปการ แก้ระบบสมการเชิงเส้นโดยตรง เช่น
ผลลัพธ์หลังอัปเดตและการลดลงของโคเวเรียนซ์
- ในตัวอย่าง innovation เป็นดังนี้
[ \boldsymbol{z}1-\hat{\boldsymbol{x}}{1,0}
\left[\begin{matrix}20\2\\end{matrix}\right] ]
- ปริมาณการแก้ไขหลังใช้ Kalman Gain เป็นดังนี้
[ \boldsymbol{K}_1 \left[\begin{matrix}20\2\\end{matrix}\right]
\left[\begin{matrix}9.37\1.43\\end{matrix}\right] ]
- ค่าประมาณสถานะหลังอัปเดตเป็นดังนี้
[ \hat{\boldsymbol{x}}_{1,1}
\left[\begin{matrix}11{,}009.37\201.43\\end{matrix}\right] ]
- ในการอัปเดตโคเวเรียนซ์แบบหลายตัวแปร มักใช้ Joseph form
[ \boldsymbol{P}_{n,n}
(\boldsymbol{I}-\boldsymbol{K}n\boldsymbol{H}) \boldsymbol{P}{n,n-1} (\boldsymbol{I}-\boldsymbol{K}_n\boldsymbol{H})^T + \boldsymbol{K}_n\boldsymbol{R}_n\boldsymbol{K}_n^T ]
- ในเอกสารต่าง ๆ ก็มักพบรูปแบบที่ย่อแล้วเช่นกัน
[ \boldsymbol{P}_{n,n}
(\boldsymbol{I}-\boldsymbol{K}n\boldsymbol{H}) \boldsymbol{P}{n,n-1} ]
- หากคำนวณด้วยเลขคณิตที่แม่นยำ ทั้งสองรูปจะให้ผลลัพธ์เดียวกัน
- แต่ในการคำนวณบนคอมพิวเตอร์ Joseph form มักมีเสถียรภาพเชิงตัวเลขดีกว่า
- ในตัวอย่างนี้ใช้การอัปเดตโคเวเรียนซ์แบบย่อ และได้ผลลัพธ์ดังนี้
[ \boldsymbol{P}_{1,1}
\left[\begin{matrix}14.57&1.43\1.43&0.71\\end{matrix}\right] ]
- ความไม่แน่นอนของค่าประมาณหลังอัปเดตต่ำกว่าทั้งความไม่แน่นอนของการทำนายและของการวัด
- สมาชิกแนวทแยงของโคเวเรียนซ์ที่ทำนายคือ (28.5), (1.25)
- สมาชิกแนวทแยงของโคเวเรียนซ์การวัดคือ (36), (2.25)
- สมาชิกแนวทแยงของโคเวเรียนซ์หลังอัปเดตคือ (14.57), (0.71)
- ในทางทฤษฎี ข้อมูลใหม่จะช่วยลดความไม่แน่นอนของการประมาณ แม้ว่าตัวข้อมูลนั้นเองจะมีความไม่แน่นอนสูงก็ตาม
- แต่ในระบบจริง บางครั้งก็จำเป็นต้องปฏิเสธการวัดที่ไม่น่าเชื่อถือ
การทำนายครั้งถัดไปและลูปการทำซ้ำ
- ขั้นตอนทำนายของ Iteration 1 ทำแบบเดียวกับ Iteration 0
- ต่างกันเพียงจุดเริ่มต้นคือ (\hat{\boldsymbol{x}}{1,1}) และ (\boldsymbol{P}{1,1}) ที่อัปเดตแล้ว
- การทำนายสถานะเป็นดังนี้
[ \hat{\boldsymbol{x}}_{2,1}
\boldsymbol{F}\hat{\boldsymbol{x}}_{1,1}
\left[\begin{matrix}12,016.5\201.43\\end{matrix}\right] ]
- การทำนายโคเวเรียนซ์เป็นดังนี้
[ \boldsymbol{P}_{2,1}
\boldsymbol{F}\boldsymbol{P}_{1,1}\boldsymbol{F}^\top+\boldsymbol{Q}
\left[\begin{matrix}52.86&7.47\7.47&1.71\\end{matrix}\right] ]
- เมื่อเวลาผ่านไปโดยไม่มีการวัดใหม่ ความแปรปรวนทั้งสองจะเพิ่มขึ้นอีกครั้ง
- ความไม่แน่นอนของความเร็วจะยิ่งเพิ่มความไม่แน่นอนของระยะทาง ทำให้ความแปรปรวนของระยะทางโตเร็วกว่า
- Kalman Filter ทำงานเป็นโครงสร้างที่ กำหนดค่าเริ่มต้น เพียงครั้งเดียวตอนเริ่ม แล้วจึงทำซ้ำการทำนายและการอัปเดตต่อเนื่องไปเรื่อย ๆ
- การทำนายจะใช้แบบจำลองการเปลี่ยนผ่านสถานะเพื่อส่งต่อค่าประมาณปัจจุบันและโคเวเรียนซ์ไปยังเวลาถัดไป
- การอัปเดตจะรวมการวัดใหม่กับการทำนายด้วย Kalman Gain เพื่อปรับปรุงสถานะปัจจุบันและความไม่แน่นอน
1 ความคิดเห็น
ความคิดเห็นบน Hacker News
ทุกครั้งที่เห็น “บทแนะนำสำหรับผู้เริ่มต้น” ก็จะคาดหวัง แต่ส่วนใหญ่ก็มักผิดหวัง และครั้งนี้ก็ไม่ใช่ข้อยกเว้น
ช่วงต้นดีอยู่ แต่ก็มักจะข้ามแนวคิดหรือคำสำคัญบางอย่างไปโดยไม่อธิบายให้พอ ที่นี่ผมหยุดตรงส่วนที่ว่า “ตัวแปรสุ่มอธิบายด้วยฟังก์ชันความหนาแน่นของความน่าจะเป็น และฟังก์ชันความหนาแน่นของความน่าจะเป็นมีลักษณะเฉพาะด้วยโมเมนต์ โมเมนต์ของค่าความน่าจะเป็นคือค่าคาดหมายของกำลังของตัวแปรสุ่ม”
ผมไม่รู้ว่าหมายถึงค่าคาดหมายของเลขชี้กำลังของค่าความน่าจะเป็น หรือค่าคาดหมายของค่าความน่าจะเป็นที่ถูกยกกำลังอะไรบางอย่าง และก็ไม่รู้ว่าทำไม กำลัง ถึงพิเศษ แทนที่จะเป็นแค่ค่าความน่าจะเป็นเอง รู้สึกหงุดหงิดเหมือนผู้เขียนจู่ ๆ ก็เลิกพยายามอธิบายให้ง่ายกลางทางของกระบวนการคิด หรือไม่ก็ไม่ได้เข้าใจแนวคิดพื้นฐานจริง ๆ ตั้งแต่แรกจนไม่สามารถอธิบายให้คนอื่นเข้าใจได้ ถ้าเป็นแบบ Udemy ที่ถามผู้สอนได้ก็คงดี แต่ผู้เขียนหนังสือไม่มีทางให้ได้รับคำตอบ
แค่ผู้เขียนอธิบายได้ไม่เพียงพอเพียงครั้งเดียว ทั้งหมดก็พังลง และถ้ามี feedback loop ก็จะช่วยได้มาก หากไม่มีก็สุดท้ายต้องรับผิดชอบเอง ค้นหาคำและวลีที่ไม่รู้จักไปเรื่อย ๆ ให้ค้นหาสำนวนที่ยังไม่เข้าใจพอ เช่น “ตัวแปรสุ่ม” หรือ “ฟังก์ชันความหนาแน่นของความน่าจะเป็น” แล้วเติมเต็มด้วย Wikipedia, ChatGPT, ตำรา, วิดีโอ ฯลฯ กระบวนการนี้เป็นแบบ recursive จึงจะมีแนวคิดที่ไม่รู้อีกโผล่มา แต่ก็แค่ไล่ลงไปเรื่อย ๆ คุณค่าของติวเตอร์ก็อยู่ที่การนำทาง depth-first search แบบนี้ให้ดี ในสาขาใหม่ โดยปกติแล้วมักใช้เวลาเติมความรู้พื้นหลังมากกว่าอ่านเนื้อหาหลัก และหัวข้อคล้าย ๆ กันครั้งต่อไปก็อาจเร็วขึ้นได้
น่าแปลกใจด้วยซ้ำที่แนวคิดพื้นฐานขนาดนี้ยังไม่ได้ถูกทำให้เป็นความเข้าใจภายใน แม้ผ่านทั้งระดับปริญญาตรีและบัณฑิตศึกษามาแล้ว
ดังนั้นจึงลืมสิ่งที่ตัวเองถือว่าเป็นเรื่องแน่นอนว่ารู้อยู่แล้ว ผมรู้สึกถึงปัญหาคล้ายกันในวิดีโอของ 3blue1brown วิดีโอสวย แต่ไม่ได้ทำให้เกิดความเข้าใจ คนที่รู้อยู่แล้วจะพยักหน้าเมื่อเห็นแนวคิดที่คุ้นเคยถูกถ่ายทอดอย่างเรียบร้อย แต่สำหรับคนอย่างผม ดูเหมือนว่ามีเงื่อนไขพื้นฐานที่ต้องรู้มากเกินไป
ถ้าจะเข้าใจ Kalman filter ก่อนอื่นต้องรู้พื้นฐานของความน่าจะเป็นและความสำคัญของการแจกแจง Gaussian การพิสูจน์เชิงคณิตศาสตร์สมมติว่าการแจกแจงความน่าจะเป็นที่เกี่ยวข้องทั้งหมดเป็นการแจกแจง Gaussian และการแจกแจง Gaussian จะถูกกำหนดได้อย่างเอกลักษณ์เมื่อรู้โมเมนต์อันดับ 1 และอันดับ 2 สุดท้ายจึงหลีกเลี่ยงการนำเรื่องโมเมนต์เข้ามาไม่ได้ และหลังจากนั้นก็ตามด้วยคณิตศาสตร์ที่ค่อนข้างโหด Kalman filter ไม่ใช่หัวข้อที่ง่าย และ Rudolf Kalman เคยกล่าวในการสัมภาษณ์ครั้งหนึ่งว่า หากไม่มีฟิลเตอร์ของเขา การลงจอดบนดวงจันทร์ของสหรัฐฯ คงเป็นไปไม่ได้
เพราะสามารถเริ่มจากกรณีตัวแปรเดียวแบบง่าย ๆ แล้วปรับแก้และทำให้เป็นกรณีทั่วไปได้ ผมจึงคิดมาเสมอว่านี่เป็นวิธีที่ดีในการสอน Kalman filter
หลายปีก่อนผมเคยฟังชุดบรรยายสั้น ๆ ของ Kalman และเขาเน้นอย่างหนักแน่นมากถึงคุณค่าของการทำงานกับข้อมูลสังเกตโดยตรง
เขามองว่าหากตั้งสมมติฐานโมเดลก่อนแล้วพยายามทำให้เข้ากับข้อมูล จะเกิดอคติ และยก Principia ของ Newton เป็นตัวอย่างที่ดีของหลักการนี้ คำอธิบายคือ Newton ไม่ได้ออกตามหาโมเดลเพื่ออธิบายกฎของ Kepler แต่ใช้การให้เหตุผลเชิงเรขาคณิตเป็นหลัก เพื่ออนุมาน กฎแรงโน้มถ่วงแบบผกผันกำลังสอง จากกฎของ Kepler เขาเป็นนักพูดที่ยอดเยี่ยมและมีความเห็นหนักแน่น แน่นอนว่าเขาอธิบายแนวคิดของ Kalman filter ด้วย แต่เพราะงานของผมไม่ได้ใช้โดยตรง รายละเอียดจึงลืมไปนานแล้ว
ผมเคยทำงานกับนักวิทยาศาสตร์และวิศวกรที่นำระบบซับซ้อนมากและเป็นที่รู้จักดีไปใช้งานจริง คนเหล่านั้นโดยทั่วไปค่อนข้างกังขาต่ออัลกอริทึมตามกระแส และมักเริ่มจาก first principles ใน 90% ของกรณี Kalman filter เชิงเส้นธรรมดา ๆ แบบง่าย หรือแม้ไม่มีโมเดลการเคลื่อนที่ ก็เพียงพอแล้ว
เมื่อไม่นานมานี้ เพื่อนขอให้ช่วย ทำ implementation ของ Kalman filter สำหรับโปรเจกต์ข้างเคียง ผมเลยอ่านเอกสารหลายอย่างรวมถึงเว็บไซต์นี้ แต่ก็ยังไม่รู้ว่าควร implement อย่างไรอยู่ดี
ทุกอย่างดูเหมือนแนว “วาดส่วนที่เหลือของนกฮูก” ไปหมด อยากได้เอกสารที่อธิบายเหมือนโปรแกรมเมอร์อธิบาย เช่น แทนที่จะใช้สัญลักษณ์ซิกมา ก็อธิบายด้วยการวนลูปบนอาร์เรย์ จากที่ผมเข้าใจ Kalman filter ดูเหมือนค่าเฉลี่ยเคลื่อนที่ของตำแหน่ง ความเร็ว และอาจรวมถึงความเร่ง และเหมือนใช้ค่าทั้งสามนี้เพื่อประมาณ “ค่าจริง” แทนค่าที่เซนเซอร์บอกมา
เพียงแต่ก่อนอื่นต้องเขียนคณิตศาสตร์ที่อธิบายพลวัตของระบบออกมาก่อน Kalman filter ค่อนข้างคล้ายกับการนำ ทฤษฎีบทของ Bayes ไปใช้กับพลวัตของระบบเฉพาะ โดยนำมาใช้ซ้ำ ๆ เพื่อดูว่าเมื่อได้รับค่าการวัดแล้วควรอัปเดตค่าประมาณสถานะปัจจุบันอย่างไร และหลังการวัดนั้นจนกว่าจะถึงการวัดครั้งถัดไป พลวัตของระบบจะส่งผลต่อความไม่แน่นอนอย่างไร ก่อนอื่นต้องมีโมเดลพลวัตที่บอกว่าสิ่งที่ติดตามเปลี่ยนไปตามเวลาอย่างไร ถ้าไม่มีสิ่งนี้ implementation ก็ย่อมสับสน ลองอ่าน Bayes filter หรือ particle filter ก่อน อาจช่วยให้จับแนวคิดได้โดยไม่ต้องมีเมทริกซ์ ผมมักรู้สึกหงุดหงิดกับคำพูดที่ว่าเป็นนักพัฒนาซอฟต์แวร์ได้โดยไม่ต้องรู้คณิตศาสตร์—ถ้าทำเว็บเพจอาจเป็นอย่างนั้นได้ แต่ยิ่งรู้คณิตศาสตร์มากเท่าไร ขอบเขตของปัญหาที่เราสามารถสร้างโมเดลและแก้ได้ก็ยิ่งกว้างขึ้นมากเท่านั้น
สิ่งสำคัญคือการประมาณจาก สถานะ นั้น และหลังได้รับการวัดแล้วใช้ข้อมูลทั้งสองส่วนเพื่อปรับสถานะถัดไปซ้ำ ๆ ถ้าเข้าใจสูตรแล้ว การเขียนโค้ดเองก็ค่อนข้างง่าย เอกสารนี้อาจช่วยได้: http://bilgin.esme.org/BitsAndBytes/KalmanFilterforDummies
อาจมีการควบคุมภายนอกและสัญญาณรบกวนของกระบวนการเพิ่มเติมได้ และสถานะภายในจะแทนด้วยเวกเตอร์ของค่าต่าง ๆ นอกจากนี้ยังต้องมีโมเดลเชิงเส้นที่บอกว่าสถานะภายในถูกแปลงเป็นการสังเกตอย่างไร รวมถึงสัญญาณรบกวนของการสังเกตด้วย
x คือสถานะของโมเดล, F คือโมเดลการเปลี่ยนสถานะเชิงเส้น
x(t+1) = F x(t), Q คือเมทริกซ์ความแปรปรวนร่วมของสัญญาณรบกวนกระบวนการ ดังนั้นในความเป็นจริงคือx(t+1) = F x(t) + N(0,Q), H คือโมเดลการสังเกตเชิงเส้น, R คือเมทริกซ์ความแปรปรวนร่วมของสัญญาณรบกวนการสังเกต, ส่วน u และ B คือเวกเตอร์ควบคุมภายนอกที่เลือกใช้ได้และวิธีที่มันออกฤทธิ์N(0,Q)คือการแจกแจงปกติที่มีค่าเฉลี่ย 0 และความแปรปรวนร่วม Qเช่น ถ้าเป็นวัตถุที่กำลังเคลื่อนที่ สถานะของโมเดลอาจเป็นตำแหน่ง x และความเร็ว v โดยทั่วไปเรดาร์หรืออุปกรณ์ลักษณะนี้มักสังเกตได้เพียงตำแหน่ง และไม่สามารถสังเกตความเร็วปัจจุบันได้ ดังนั้นโมเดลการสังเกตจึงอยู่ในรูปที่ดึงออกมาเฉพาะตำแหน่ง ก่อนจะทำ Kalman filter ต้องมี “นกฮูก” แบบนี้เสียก่อน และต้องกำหนดเองตามว่าเป็นกระบวนการแบบใด Kalman filter บอกวิธีประมาณเวกเตอร์สถานะจริงในแต่ละช่วงเวลาอย่างเหมาะที่สุด เมื่อทั้งโมเดลการเปลี่ยนสถานะและการสังเกตต่างมีสัญญาณรบกวน บทเรียนจำนวนมากอธิบายโดยผสมส่วนของโมเดลกระบวนการที่เลือกกับส่วนของ Kalman filter เข้าด้วยกัน จึงทำให้สับสน และในตัวอย่างที่เล็กเกินไปอย่างโมเดลค่าคงที่หนึ่งมิติ โมเดลพลวัตก็หายไปจากสมการ ทำให้ยิ่งสับสนกว่าเดิม
ช่วงต้น ๆ หลายบทอธิบาย Kalman filter และ information filter ได้ดี
เมื่อรู้ว่าค่าที่เซนเซอร์วัดมีสัญญาณรบกวน วิธีนี้คือการหาค่าเฉลี่ยของหลายตัวอย่างเพื่อให้ได้ค่าประมาณที่ใกล้ค่าจริงขึ้น และถ้ารู้ระดับสัญญาณรบกวนของเซนเซอร์ ก็พอจะเดาได้ว่าควรเฉลี่ยกี่ตัวอย่าง ในที่นี้ให้มองว่าค่าที่ตรวจจับหรืออนุมานทั้งหมดถูกประมาณเป็น การแจกแจงแบบเกาส์เซียน ที่กำหนดด้วยค่าเฉลี่ยและความแปรปรวน
ในระบบฟิสิกส์ที่มีความเร่ง ความเร็ว และตำแหน่ง ถ้าที่เวลา t มีตำแหน่ง p และความเร็ว v ตำแหน่งที่ t+dt ก็จะประมาณได้เป็น
p+(v*dt)นอกจากนี้ยังอัปเดตความเร็วได้ด้วยค่าประมาณความเร่ง และถ้าเป็นระบบที่เราควบคุมอยู่ ก็อัปเดตโมเดลความเร่งได้จากแรงที่สั่งให้กระทำ แต่เพราะค่าประมาณเริ่มต้นมีความไม่แน่นอน หากเดินหน้าเฉพาะโมเดลกระบวนการนี้ไปเรื่อย ๆ ความไม่แน่นอนก็จะเพิ่มขึ้นเรื่อย ๆ จนสุดท้ายใช้การไม่ได้Kalman filter เป็นเทคนิคที่ผสานข้อมูลจากเซนเซอร์กับโมเดลกระบวนการ เพื่อประมาณปริมาณที่สนใจให้ดีกว่าการใช้เพียงอย่างใดอย่างหนึ่ง ในแต่ละช่วงเวลา จะใช้โมเดลกระบวนการทำนายสถานะจากค่าประมาณสถานะก่อนหน้า แล้วใช้งานวัดจากเซนเซอร์ปัจจุบันเพื่ออัปเดตค่าเฉลี่ยและความไม่แน่นอน ใน Kalman filter พื้นฐาน จะสมมติว่าโมเดลกระบวนการเป็นเชิงเส้นและค่าประมาณทั้งหมดเป็นการแจกแจงเกาส์เซียนอย่างง่าย จากนั้นกำหนดว่าจะเชื่อโมเดลหรือเซนเซอร์มากแค่ไหนด้วยตัวคูณที่เรียกว่า Kalman gain
เพลย์ลิสต์วิดีโอสอนแบบทีละขั้นอีกชุดเกี่ยวกับ Kalman filter: https://www.youtube.com/watch?v=CaCcOwJPytQ&list=PLX2gX-ftPV...
เมื่อจับสัญชาตญาณได้แล้ว Kalman filter น่าสนใจมากจริง ๆ และ particle filter ก็สนุกทั้งในการใช้งานและการทำ visualization
ผมมีหนังสือเล่มนี้ และเคยนำไปใช้กับปัญหาจริงได้ค่อนข้างสำเร็จ
แม้อ่านซ้ำหลายครั้งแล้วก็ยังมีบางส่วนที่ตามได้ไม่ค่อยลื่น แต่โดยรวมถือว่าค่อนข้างดี
อีกบทความที่ดีในเรื่องที่เกี่ยวข้อง: Is the Kalman filter a low-pass filter? Sometimes!
https://jbconsulting.substack.com/p/is-the-kalman-filter-jus...
ผมเคยใช้เพื่อลดการสั่นของการเคลื่อนที่กล้องเสมือนในวิดีโอที่ครอปรอบใบหน้าแบบเรียลไทม์ วิธีคือส่งสตรีมตำแหน่งใบหน้าที่ตรวจพบไปให้ตัวทำงาน Kalman filter แล้วรับสตรีมตำแหน่งกล้องที่นิ่งขึ้นกลับมา
เมื่อทรัพยากรการคำนวณมีจำกัด Kalman filter เป็นตัวเลือกที่ยอดเยี่ยม แต่โดยส่วนตัวแล้วผมชอบโมเดลที่ใหม่กว่าและขั้นสูงกว่าอย่าง particle filter มากกว่า
ข้อดีของ particle filter คือสามารถรับมือกับสถานการณ์ซับซ้อนที่มีฟิสิกส์ไม่เชิงเส้นและการแจกแจงแบบไม่ใช่ Gaussian ได้ เช่น GPS ของรถยนต์สามารถใช้แผนที่ถนนโดยอิงจากประวัติการเลี้ยวล่าสุดเพื่อตัดตำแหน่งที่เป็นไปไม่ได้ออกไปได้ ส่วน Gaussian filter ทำแบบนี้ไม่ได้ และจะได้แค่ก้อนเบลอ ๆ ที่ครอบคลุมไปหลายบล็อก
และยังสงสัยด้วยว่า สำหรับการประมวลผลแบบออฟไลน์ มีโมเดลที่ใหม่กว่าหรือขั้นสูงกว่านอกจาก particle filter ที่น่าแนะนำหรือไม่
ปี 2007 ผมอยู่ที่บริษัทเทคโนโลยีโฆษณาแห่งหนึ่ง ตอนนั้น CEO กับทีมวิจัยหมกมุ่นกับ Kalman filter เพื่อเพิ่มประสิทธิภาพแคมเปญโฆษณาบนเครือข่าย Google และ MSN
เท่าที่จำได้มันได้ผลอยู่บ้าง แต่ตอนนี้หาคำขอสิทธิบัตรไม่เจอแล้ว และ Zeta กับ Walmart ก็ซื้อเทคโนโลยีนั้นไป
บทความอธิบาย Kalman filter แทบทุกชิ้นมักเริ่มประมาณว่า “ลองนึกถึงเทอร์โมสตัทเป็นตัวอย่างเชิงสัญชาตญาณ เข้าใจไหม? ดี! ทีนี้เพื่อให้มันเป็นเชิงสัญชาตญาณยิ่งขึ้น มาดูพีชคณิตเชิงเส้นขั้นสูงกัน”
เลยอยากรู้ว่าเคยเห็น คำอธิบาย Kalman filter ที่ไม่กระโดดเข้าสู่คณิตศาสตร์ทันทีบ้างไหม
ถ้าหลับตาแล้วเดินไปหากำแพง ยิ่งเวลาผ่านไปความมั่นใจในตำแหน่งของตัวเองก็ยิ่งลดลง และทันทีที่นิ้วแตะกำแพง ความมั่นใจในตำแหน่งก็เพิ่มขึ้นอย่างฉับพลัน ช่วงแรกคือขั้นตอนการทำนาย ส่วนช่วงหลังคือการอัปเดตจากการวัด พีชคณิตเชิงเส้นเป็นเพียงวิธีคำนวณน้ำหนักเหล่านั้นในระบบพลวัตเชิงเส้นที่มีสัญญาณรบกวนแบบ Gaussian เท่านั้น
Kalman filter มีสมมติฐานทางสถิติ เช่น การแจกแจงปกติ ดังนั้นอย่างน้อยต้องรู้สถิติและเมทริกซ์ค่าเฉลี่ย·ความแปรปรวนร่วม ถ้าระดับนั้นก็อาจตามเนื้อหาได้ถึงก่อนส่วนที่ 4 ของ https://sites.ualberta.ca/~dwiens/stat679/meinhold&singpurwa... หลังส่วนที่ 4 เป็นส่วนที่ผลักดันการคำนวณทางคณิตศาสตร์ที่จำเป็นสำหรับการทำ implementation จริง จึงไม่ได้เพิ่มความเข้าใจมากนัก
วิธีที่เริ่มจากทุกอย่างใน 1 มิติก่อน แล้วค่อยขยายไปสู่ปัญหาหลายมิติ ช่วยให้จับแนวคิดได้จริง ๆ เพลย์ลิสต์คอร์สดูเหมือนจะอยู่ที่นี่: https://youtube.com/playlist?list=PLAwxTw4SYaPkCSYXw6-a_aAoX...
ส่วน Kalman filter เริ่มจากวิดีโอ “Tracking Intro - Artificial Intelligence for Robotics” คอร์สฟรีก็ดูเหมือนจะอยู่ที่นี่ด้วย แต่ต้องล็อกอินจึงจะเข้าถึงได้: https://www.udacity.com/course/intro-to-artificial-intellige...
ผมไม่ค่อยรู้จัก Kalman จึงลองอ่านบทความเบื้องต้นในเว็บไซต์นี้ แต่ยังไม่ค่อยเข้าถึง
พอลองคิดถึงกราฟตัวอย่าง มันดูเหมือน exponential moving average ที่เข้าใจง่ายกว่ามาก เมื่อค้นหาใน Google เพื่อดูการเปรียบเทียบ พบว่าใน Stats Stack Exchange บอกว่าสำหรับ “random walk + noise” นั้น EMA ดีพอ ๆ กับ Kalman และบทความปี 2003 ของ Joseph J. LaViola จาก Brown University แสดงให้เห็นว่าอัลกอริทึม double exponential smoothing มีคุณภาพเท่ากับ Kalman และ extended Kalman แต่เร็วกว่า 135 เท่าและเรียบง่ายกว่า
เนื่องจาก double exponential smoothing เข้าใจง่ายกว่า Kalman มาก ถ้าสมมติว่าบทความของ LaViola ถูกต้อง ผมก็จะไม่ทุ่มความพยายามเพิ่มเติมเพื่อทำความเข้าใจ Kalman แล้ว