Kalman Filter ट्यूटोरियल
(kalmanfilter.net)- Kalman Filter एक ऐसा algorithm है जो noise वाले sensor measurements और अपूर्ण dynamic model को साथ इस्तेमाल करके मौजूदा state और अगली state की uncertainty तक estimate करता है
- यह tutorial aircraft radar tracking के उदाहरण में distance (r) और velocity (v) को state vector मानकर, predicted value और measured value को combine करने की प्रक्रिया को numbers के साथ follow करता है
- शुरुआती measurements (10,000m), (200m/s) और sampling interval (5s) इस्तेमाल करने पर constant velocity model में अगली position (11,000m) predict होती है, और measurement noise (R) तथा process noise (Q) covariance में reflect होते हैं
- दूसरा measurement (11,020m), (202m/s) अधिक uncertain है, लेकिन Kalman gain (K) prediction और measurement को weighted तरीके से combine करके updated state (11,009.37m), (201.43m/s) calculate करता है
- initialization के बाद prediction-update loop दोहराया जाता है, और real implementation में Joseph form जैसी stable covariance update equation और anomalous measurements की handling तक consider करनी चाहिए
Kalman Filter जिस estimation problem को हल करता है
- Kalman Filter uncertainty वाले environment में system की state estimate और predict करने वाला algorithm है
- measurement noise वाला sensor data
- अज्ञात external factors
- dynamic model और actual movement के बीच का अंतर
- इसका उपयोग object tracking, navigation, robotics, control, financial market analysis, weather prediction आदि में होता है
- computer mouse trajectory estimation में apply करने पर यह noise घटाकर hand tremor को compensate कर सकता है और ज्यादा stable movement path बना सकता है
- tutorial को जटिल mathematical explanation के बजाय numerical examples और intuitive explanation के जरिए Kalman Filter समझाने के लिए बनाया गया है
- इसमें गलत तरीके से design की गई situations में Kalman Filter के object को सही से track न कर पाने के उदाहरण और उन्हें correct करने के तरीके भी शामिल हैं
Learning path
- यह project Kalman Filter को तीन levels की depth में सीखने लायक बनाया गया है
- single-page overview: core ideas और जरूरी equations को derivation के बिना समझाता है, और basic statistics तथा linear algebra की जानकारी मानता है
- free example-based web tutorial: numerical examples से intuition बनाता है और Kalman Filter equations की derivation तक step-by-step cover करता है; बताया गया है कि prior knowledge की जरूरत नहीं है
- Kalman Filter from the Ground Up: 14 fully solved numerical examples, performance plots और tables, Extended Kalman Filter, Unscented Kalman Filter, sensor fusion, implementation guidelines शामिल करता है
Radar tracking example से prediction की जरूरत समझना
- aircraft को track करने वाले radar में aircraft system है, और estimate की जाने वाली position system state है
- radar narrow beam को aircraft की direction में steer करता है, इसलिए अगली beam कहाँ भेजनी है यह तय करने के लिए future position predict करनी होती है
- prediction fail होने पर beam गलत direction में जा सकती है और tracking खो सकती है
- time के साथ system movement दिखाने वाला dynamic model जरूरी है
- simplified 1D example में माना जाता है कि aircraft radar की ओर या उससे दूर एक straight line में move कर रहा है
- radar pulse transmit/receive time से distance (r) calculate करता है
- Doppler effect से velocity (v) भी measure की जा सकती है
- अगर (t_0) पर distance (10,000m), velocity (200m/s) बहुत accurately measure की गई हो, sampling interval (\Delta t=5s) हो और velocity constant मानी जाए, तो अगली position (11,000m) है
- (\Delta r = v \cdot \Delta t)
- (r_{t_1}=10,000+200\cdot5=11,000m)
Measurement noise और process noise
- actual radar measurements पूरी तरह precise नहीं होते, इसलिए एक ही moment पर कई radars measure करें तो भी values थोड़ी-थोड़ी अलग हो सकती हैं
- यह variation measurement noise के रूप में express किया जाता है
- सिर्फ state estimate ही नहीं, बल्कि यह estimate कितना reliable है यह भी calculate करना होता है
- dynamic model भी perfect नहीं होता
- aircraft को constant velocity से move करता मानने पर भी wind जैसे external factors के कारण actual movement बदल सकता है
- ऐसे unpredictable effects process noise होते हैं
- Kalman Filter current state estimate, future state prediction और हर एक की uncertainty साथ में provide करता है
- system और noise model की assumptions follow करते हों, तो यह state estimation uncertainty को minimize करने वाला optimal algorithm है
State vector और initialization
- example की system state aircraft की distance (r) और velocity (v) से बनी है
[ \boldsymbol{x}= \begin{bmatrix} r\ v \end{bmatrix} ]
- पहला measurement (t_0) पर इस प्रकार है
[ \boldsymbol{z}_0= \begin{bmatrix} 10{,}000\ 200 \end{bmatrix} ]
- measurements में uncertainty होती है, इसलिए हर measurement के साथ variance के रूप में measurement uncertainty जुड़ी होती है
- distance measurement standard deviation: (4m)
- velocity measurement standard deviation: (0.5m/s)
- variance standard deviation का square होता है
[ \boldsymbol{R}_0= \begin{bmatrix} 16 & 0\ 0 & 0.25 \end{bmatrix} ]
- इस example में माना गया है कि distance और velocity measurement errors एक-दूसरे से related नहीं हैं, इसलिए covariance matrix के off-diagonal elements 0 रखे गए हैं
- initialization step में measurement और system state वही physical quantities (r), (v) represent करते हैं, इसलिए first measurement को initial state estimate के रूप में इस्तेमाल किया जा सकता है
[ \hat{\boldsymbol{x}}_{0,0}= \boldsymbol{z}_0= \begin{bmatrix} 10{,}000\ 200 \end{bmatrix} ]
- यह तरीका सिर्फ initialization step में इस्तेमाल किया जा सकता है
Prediction step: state और covariance propagation
- prediction current state और state transition matrix (\boldsymbol{F}) का उपयोग करके अगले time point की state calculate करता है
- constant velocity model में नीचे वाली equations इस्तेमाल होती हैं
[ v_1=v_0=v ]
[ r_1=r_0+v_0\Delta t ]
- matrix form में state prediction equation इस प्रकार है
[ \hat{\boldsymbol{x}}_{n+1,n}
\boldsymbol{F} \hat{\boldsymbol{x}}_{n,n} + \boldsymbol{G}\boldsymbol{u}_n ]
- (\boldsymbol{u}_n): input variable
- (\boldsymbol{G}): input transition matrix
- इस simple example में input नहीं है, इसलिए (\boldsymbol{u}_n=0)
- (\Delta t=5s) होने पर state transition matrix नीचे जैसा है, और prediction result (11,000m), (200m/s) है
[ \boldsymbol{F}= \begin{bmatrix} 1 & 5\ 0 & 1 \end{bmatrix} ]
[ \hat{\boldsymbol{x}}_{1,0}
\begin{bmatrix} 11{,}000\ 200 \end{bmatrix} ]
- covariance prediction में simply (\boldsymbol{F}\boldsymbol{P}) नहीं, बल्कि (\boldsymbol{F}\boldsymbol{P}\boldsymbol{F}^T) इस्तेमाल होता है
[ \boldsymbol{P}_{n+1,n}
\boldsymbol{F} \boldsymbol{P}_{n,n} \boldsymbol{F}^T + \boldsymbol{Q} ]
- process noise को छोड़ दें तो predicted covariance यह है
[ \boldsymbol{P}_{1,0}
\begin{bmatrix} 22.25 & 1.25\ 1.25 & 0.25 \end{bmatrix} ]
- velocity variance constant velocity model के कारण (0.25) पर बनी रहती है
- distance variance (16) से बढ़कर (22.25) हो जाता है, क्योंकि velocity uncertainty समय के साथ distance uncertainty बढ़ाती है
Process noise को reflect करना
- actual aircraft velocity wind जैसे unpredictable external factors से प्रभावित हो सकती है, इसलिए covariance prediction में process noise (\boldsymbol{Q}) जोड़ा जाता है
- example में random acceleration का standard deviation (\sigma_a=0.2m/s^2) माना गया है
- variance (\sigma_a^2=0.04m^2/s^4) है
- (\Delta t=5s) होने पर process noise matrix इस प्रकार है
[ \boldsymbol{Q}
\begin{bmatrix} 6.25 & 2.5\ 2.5 & 1 \end{bmatrix} ]
- process noise जोड़ने के बाद predicted covariance यह है
[ \boldsymbol{P}_{1,0}
\begin{bmatrix} 28.5 & 3.75\ 3.75 & 1.25 \end{bmatrix} ]
Update step: prediction और measurement का weighted combination
- (t_1) पर दूसरा measurement इस प्रकार है
[ \boldsymbol{z}_1= \begin{bmatrix} 11{,}020\ 202 \end{bmatrix} ]
- इस measurement में strong noise spike की वजह से signal-to-noise ratio कम है, इसलिए इसे first measurement से ज्यादा uncertain माना गया है
- distance standard deviation: (6m)
- velocity standard deviation: (1.5m/s)
[ \boldsymbol{R}_1= \begin{bmatrix} 36 & 0\ 0 & 2.25 \end{bmatrix} ]
- predicted covariance (\boldsymbol{P}_{1,0}) के diagonal elements measurement covariance (\boldsymbol{R}_1) से छोटे हैं, इसलिए prediction side की uncertainty कम है
- Kalman Filter सिर्फ prediction या सिर्फ measurement इस्तेमाल नहीं करता, बल्कि कम uncertainty वाली side को ज्यादा weight देकर combine करता है
- 1D form का weighted average इस प्रकार है
[ \hat{x}_{1,1}
K_1 z_1 + (1-K_1)\hat{x}_{1,0} ]
- (\boldsymbol{K}) Kalman gain है, जो updated estimate की uncertainty minimize करने के लिए measurement और prediction के weights तय करता है
Innovation, observation matrix, Kalman gain
- state update equation को prediction value में correction term जोड़ने के form में लिखा जा सकता है
[ \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 है, और new measurement द्वारा दी गई information को represent करता है
- (\boldsymbol{H}) observation matrix या measurement matrix है, जो state variables को actual measured physical quantities में map करता है
- इस example में state और measurement दोनों distance और velocity हैं, इसलिए (\boldsymbol{H}=\boldsymbol{I})
- आम तौर पर digital thermometer की तरह measurement और state अलग physical domains में हो सकते हैं
- multivariate Kalman gain इस प्रकार है
[ \boldsymbol{K}_n
\boldsymbol{P}{n,n-1} \boldsymbol{H}^T ( \boldsymbol{H} \boldsymbol{P}{n,n-1} \boldsymbol{H}^T + \boldsymbol{R}_n )^{-1} ]
- example में calculated Kalman gain इस प्रकार है
[ \boldsymbol{K}_1= \begin{bmatrix} 0.4048 & 0.6377\ 0.0399 & 0.3144 \end{bmatrix} ]
- matrix inverse calculation MATLAB के
inv(A)या Python केnumpy.linalg.inv(A)से possible है, लेकिन real implementation में explicit inverse के बजायA\bयाnumpy.linalg.solve(A, b)की तरह linear system को directly solve करना आम तौर पर बेहतर होता है
Update result और covariance reduction
- इस example की innovation यह है
[ \boldsymbol{z}1-\hat{\boldsymbol{x}}{1,0}
\begin{bmatrix} 20\ 2 \end{bmatrix} ]
- Kalman gain से correction term calculate करने पर यह मिलता है
[ \boldsymbol{K}_1 \begin{bmatrix} 20\ 2 \end{bmatrix}
\begin{bmatrix} 9.37\ 1.43 \end{bmatrix} ]
- updated state estimate इस प्रकार है
[ \hat{\boldsymbol{x}}_{1,1}
\begin{bmatrix} 11{,}009.37\ 201.43 \end{bmatrix} ]
- multivariate covariance update के लिए numerically stable 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 ]
- simplified covariance update equation भी literature में अक्सर दिखती है
[ \boldsymbol{P}_{n,n}
(\boldsymbol{I}-\boldsymbol{K}n\boldsymbol{H}) \boldsymbol{P}{n,n-1} ]
- exact arithmetic में दोनों forms same result देते हैं, लेकिन computer implementation में Joseph form आम तौर पर ज्यादा numerically stable है
- example में simplified equation से calculate की गई updated covariance इस प्रकार है
[ \boldsymbol{P}_{1,1}
\begin{bmatrix} 14.57 & 1.43\ 1.43 & 0.71 \end{bmatrix} ]
- updated covariance के diagonal elements predicted covariance ((28.5, 1.25)) और measurement covariance ((36, 2.25)) से कम हैं
- नई information, uncertainty अधिक होने पर भी, estimation uncertainty घटाती है, और theory के अनुसार new measurement को ignore नहीं करना चाहिए
- real implementation में अविश्वसनीय measurements को reject करना पड़ सकता है, और outliers handle करने का तरीका book के Outlier Treatment chapter में cover किया गया है
अगली prediction और repeating loop
- Iteration 1 का prediction step Iteration 0 जैसा ही है, लेकिन starting point updated (\hat{\boldsymbol{x}}{1,1}) और (\boldsymbol{P}{1,1}) में बदल जाता है
- state prediction result यह है
[ \hat{\boldsymbol{x}}_{2,1}
\boldsymbol{F} \hat{\boldsymbol{x}}_{1,1}
\begin{bmatrix} 12{,}016.5\ 201.43 \end{bmatrix} ]
- covariance prediction result यह है
[ \boldsymbol{P}_{2,1}
\begin{bmatrix} 52.86 & 7.47\ 7.47 & 1.71 \end{bmatrix} ]
- new measurement के बिना time गुजरने पर uncertainty naturally बढ़ती है, इसलिए prediction step में variance फिर बढ़ जाता है
- velocity uncertainty distance uncertainty को और बढ़ाती है
- इसलिए distance variance velocity variance से ज्यादा तेजी से बढ़ता है
- example Kalman Filter के तीन steps दिखाता है
- Initialization: शुरुआत में एक बार perform किया जाता है
- Prediction: dynamic model से next state और uncertainty propagate करना
- Update: new measurement और prediction को Kalman gain से combine करना
- initialization के बाद Kalman Filter लगातार prediction-update loop के रूप में operate करता है
1 टिप्पणियां
Hacker News की राय
मैं हमेशा कहता हूँ कि Kalman filter को अलग से सीखना क्रम को उल्टा कर देता है, इसलिए उसके आसपास के सिद्धांत जो बड़ी समझ देते हैं, वे अक्सर छूट जाते हैं
इसे ठीक से समझने के लिए least squares (linear regression), recursive least squares, और information filter (KF का एक दूसरा formulation) को क्रम से देखना बेहतर है
तब समझ आता है कि KF बस recursive least squares का ऐसा reformulation है जिसमें update step की efficiency को प्राथमिकता दी गई है
यह PDF एक संक्षिप्त overview देता है: http://ais.informatik.uni-freiburg.de/teaching/ws13/mapping/...
फिर भी जिज्ञासा तो है, इसलिए ऐसा रास्ता चाहिए जो जिज्ञासा बनाए रखे और धीरे-धीरे समझ तक पहुँचाए
The Six (Not So) Easy Pieces को दोबारा पढ़ने पर भी पूरी समझ नहीं बनती, फिर भी वह मूल्यवान है; और Arnold’s cat के साथ खेलते हुए बिना किसी सख्त वैज्ञानिक प्रक्रिया के भी आदिम जिज्ञासा के सहारे उन अवधारणाओं का अनुभव किया जा सकता है जो पहले सिर्फ संदर्भ के पीछे छिपी लगती थीं
http://gerdbreitenbach.de/arnold_cat/cat.html
1D में linear prediction X'1 = X0*a + b से prior distribution मिलता है, और mean(X'1) = mean(X0)*a + b, var(X'1) = var(X0)*a^2 होता है; यहाँ a और b मानी गई dynamics को दर्शाते हैं
Gaussian posterior, prior और observation की precision-weighted average होता है, इसलिए X1 = (1 - K)X'1 + YK और K = (1/var(X'1))/(1/var(X'1) + 1/var(Y)) होता है, जहाँ Y Gaussian observation है
इसे दोहराते जाइए और Kalman filter मिल जाता है; और multi-dimensional Gaussian की linearity समझ में आ जाए तो इसे multi-dimensional case में generalize करना भी सहज लगता है
हालाँकि multi-dimensional Gaussian की linearity और Gaussian posterior खुद आसान विषय नहीं भी हो सकते हैं
जब भी यह विषय आता है, यह resource भी साथ आता है, और उल्टा भी यही सच है: https://github.com/rlabbe/Kalman-and-Bayesian-Filters-in-Pyt...
Jupyter notebook का इस्तेमाल भी बहुत अच्छा है
लगता है कि probability distributions के लिए कोई symbolic computation tool अभी तक नहीं है
मेरा मतलब ऐसे tool से है जो, उदाहरण के लिए, दो multivariate Gaussian probability density functions को गुणा करके covariance matrix दे सके, या Kalman filter के सभी components (prediction model और observation process) को define करने पर sympy के lambdify की तरह ज़रूरी formulas निकाल दे
हालाँकि मुझे नहीं पता कि Sympy Kalman filter के लिए ज़रूरी conditional distributions, यानी Bayesian posterior, तक भी संभाल सकता है या नहीं
वैसे भी, अगर Sympy के साथ Kalman filter पर प्रयोग करना हो तो mean और variance, या covariance matrix, को सीधे handle करना बेहतर है
संदर्भ: https://reference.wolfram.com/language/howto/WorkWithStatist...
और: https://reference.wolfram.com/language/ref/MultinormalDistri...
https://www.squiggle-language.com/docs
अगर Q और R constant हों, जैसा कि अक्सर होता है, तो gain जल्दी converge कर जाता है और Kalman filter prediction step लगे हुए exponential filter जैसा बन जाता है
बहुत से लोगों के लिए यह व्याख्या कहीं ज़्यादा आसान है, और व्यवहार में इसके उपयोग से भी अच्छी तरह मेल खाती है
आम तौर पर Q और R को हाथ से tune किया जाता है जब तक कि नतीजे “ठीक-ठाक” न लगें, और उसके बाद उन्हें फिर बदला नहीं जाता
ऊपर से, Q और R जैसी कई values tune करने के बजाय सिर्फ एक gain को manually tune करना पड़ता है
क्या बस उन्हें तब तक adjust करते रहना है जब तक नतीजे plausible न लगें? अगर ऐसा है, तो फिर यह कैसे भरोसेमंद तरीके से काम करता है जबकि स्थिति पूरी तरह overfit भी नहीं हुई होती?
मान लीजिए आप वीडियो में किसी पक्षी को track कर रहे हैं; किसी Q का चुनाव तो कर सकते हैं, लेकिन दिन के समय के हिसाब से noise statistics बदल सकती हैं। तब क्या किया जाता है?
संबंधित पोस्ट: Kalman filter from the ground up - https://news.ycombinator.com/item?id=37879715 - अक्टूबर 2023, 150 टिप्पणियाँ
यह भी जिज्ञासा है कि ऊपर दिए शीर्षक में शामिल करने के लिए कौन-सा साल सबसे उचित होगा
Kalman filter, David G. Luenberger की अधिक सामान्य विषय वाली किताब Optimization by Vector Space Methods, John Wiley and Sons, Inc., New York, 1969 में भी शामिल है
अचानक एक विचार आया। जिन मामलों में सिर्फ eye-witness testimony हो, क्या उन्हें किसी तरह vector के रूप में encode करके Kalman filter से संभाला जा सकता है ताकि observations के evidentiary value को बढ़ाया जा सके?
यानी झूठ और अशुद्धता—दोनों को “error” की तरह treat किया जाए
मेरे दिमाग में Phoenix lights, सामान्य रूप से UFO, भूत, near-death experiences, और थोड़ा अधिक रोज़मर्रा के उदाहरण के तौर पर rape allegations जैसी चीज़ें हैं
सबसे अच्छा resource लगभग हमेशा यही है: https://github.com/rlabbe/Kalman-and-Bayesian-Filters-in-Pyt...
जो लोग Python इस्तेमाल नहीं करते उनके लिए भी यह शानदार है, और पूरे विषय का बहुत अच्छा coverage देता है
जब मैं यह विषय सीख रहा था, तब क्या किसी और ने bow tie पहने Michael van Biezem के Kalman filter lectures देखे थे?
https://www.youtube.com/watch?v=CaCcOwJPytQ&list=PLX2gX-ftPV...
वह एक पंक्ति जिसे सच में जानना चाहिए, यह है: “इस filter का नाम Rudolf E. Kálmán (19 मई 1930–2 जुलाई 2016) के नाम पर रखा गया है। 1960 में Kálmán ने discrete-data linear filtering problem के recursive solution का वर्णन करने वाला प्रसिद्ध paper प्रकाशित किया।”