Kalman Filter की सरल व्याख्या

 (thekalmanfilter.com)
4 पॉइंट द्वारा GN⁺ 2024-02-13 | 1 टिप्पणियां | WhatsApp पर शेयर करें
  • Kalman Filter शोरयुक्त या गलत मापों से रियल टाइम में ज़्यादा सटीक state estimate बनाता है, और सेंसर-आधारित prediction व control में इस्तेमाल होने वाला algorithm है
  • यह सिर्फ मापों को smooth नहीं करता, बल्कि सीधे observe करना मुश्किल position और velocity जैसे state variables तक estimate कर सकता है
  • radar tracking example 2D position measurements और covariance को input के रूप में लेकर object की position और velocity को 4×1 state vector के रूप में estimate करने का flow दिखाता है
  • पहले दो measurements से state initialize करने के बाद, आगे prediction, Kalman Gain calculation, और state तथा error covariance update को repeat किया जाता है
  • filter जो history रखता है वह केवल current state estimate होता है, इसलिए memory-constrained devices पर भी implement करना आसान है

Kalman Filter की बड़ी तस्वीर

  • Kalman Filter को input और output वाले black box की तरह देखा जा सकता है
    • input शोरयुक्त या कभी-कभी गलत measurements होते हैं
    • output ऐसा estimate होता है जिसमें noise कम होता है और accuracy ज़्यादा होती है
  • estimate ऐसे system state parameters भी हो सकते हैं जिन्हें वास्तव में measure या observe नहीं किया गया हो
  • यह observable और unobservable parameters को real time में high accuracy के साथ estimate करने के लिए इस्तेमाल होता है
  • high-accuracy estimates का उपयोग precise prediction और decision-making में किया जाता है
  • इसलिए भरोसेमंद information की जरूरत वाले robotics और real-time systems में इसका अक्सर उपयोग होता है

Kalman Filter कौन-सी समस्या हल करता है

  • inaccurate या noisy measurements के आधार पर किसी variable की state, या सीधे observe करना मुश्किल दूसरे variables को ज़्यादा accuracy से estimate करता है
  • इसके प्रमुख applications ये हैं
    • object tracking: measured position का उपयोग करके object की position और velocity को ज़्यादा accurately estimate करता है
    • digital scale में weight estimation: surface पर लगे pressure से object का weight estimate करता है
    • guidance, navigation, control: IMU sensors से position, velocity, acceleration estimate करता है और अगली movement control में उपयोग करता है
  • Kalman Filter की ताकत measurement smoothing से ज्यादा मापना मुश्किल system parameters को estimate करने की क्षमता में है
  • real-time systems में ज़्यादा accurate estimates बेहतर control और features तक ले जाते हैं

Radar Tracking Example के input और output

  • example airport के आसपास airplanes और objects को track करने वाली radar tracking स्थिति को cover करता है
  • output track state का उपयोग airspace monitor करने वाले air traffic control operators को दिखाने के लिए किया जाता है
  • radar 2D Cartesian coordinate system में x, y position measurements output करता है
    • measurement को 2×1 column vector z के रूप में represent किया जाता है
    • measurement का variance-covariance matrix R से represent किया जाता है
    • measurement timestamp t से represent किया जाता है
    • subscript m measurement parameters को, और k measurement order को दिखाता है
  • Kalman Filter radar measurements के आधार पर object की position और velocity estimate करता है
    • estimate को 4×1 column vector x के रूप में represent किया जाता है
    • estimate का variance-covariance matrix 4×4 matrix P से represent किया जाता है
    • state estimate का timestamp T से दिखाया जाता है

चरण 1: system state initialization

  • Kalman Filter की initialization method application के हिसाब से अलग होती है
  • इस radar tracking example में पहले measurement से system state initialize की जाती है
  • input measurement में केवल position information होती है, लेकिन output system state में object की position और velocity शामिल होती है
  • पहला measurement आने पर पता चलने वाली information सिर्फ उस समय की position होती है
    • पहले estimate के बाद system state estimate को input position पर set किया जाता है
    • system state error covariance को पहले measurement की position accuracy पर set किया जाता है

चरण 2: system state reinitialization

  • velocity estimate करने के लिए दूसरे position measurement की जरूरत होती है, इसलिए system state estimate को reinitialize किया जाता है
  • velocity linear approximation से calculate की जाती है
    • velocity = travelled distance / time taken to travel
  • updated system state estimate दूसरे measurement की position और calculated velocity से बनता है
  • updated system state error covariance में दूसरे measurement की position accuracy और approximate velocity accuracy शामिल होती है
  • velocity accuracy approximation को filter से data pass कराने के बाद tuning करके adjust किया जा सकता है
    • example में velocity variance term को 10⁴ set किया गया है
    • यह value velocity state value के लिए बड़ी uncertainty दिखाती है
    • example में velocity unit m/s है

Initialization के बाद iterative processing

  • पहले दो चरण कुछ measurements से system estimate को initialize और reinitialize करने की process हैं
  • applications के हिसाब से initialization method अलग हो सकती है
  • लक्ष्य ऐसा system state estimate रखना है जिसे आगे के measurements के साथ Kalman Filter equations से update किया जा सके
  • आगे के steps में नए measurement को filter में शामिल किया जाता है और state estimate update किया जाता है

चरण 3: system state estimate prediction

  • तीसरा measurement आने पर system state estimate को आगे propagate करके measurement के साथ time-align किया जाता है
  • measurement और state estimate को combine करने के लिए यह alignment जरूरी है
  • prediction में system model का उपयोग होता है
  • example में constant-velocity linear motion model से time interval के दौरान object की position change को approximate किया जाता है
    • constant-velocity model मानता है कि acceleration 0 है
  • state transition matrix इन motion equations को represent करता है
    • यह matrix state estimate और state error covariance matrix को सही तरीके से propagate करने के लिए इस्तेमाल होता है
  • state estimate को future time point तक propagate करने पर उस समय की state uncertainty पैदा होती है, इसलिए error covariance बढ़ता है

Q matrix और H matrix

  • Q matrix system model के process noise को represent करता है
    • system model एक approximation है
    • system state के lifetime के दौरान model की accuracy बदलती रहती है
    • Q matrix इस uncertainty को दिखाता है और existing state noise में जोड़ा जाता है
    • example में actual acceleration और deceleration इस error में contribute करते हैं
  • H matrix state-measurement matrix है, जो system state estimate को state space से measurement space में transform करता है
    • कुछ applications में यह 0 और 1 से बनी matrix होती है
    • Extended Kalman Filter इस्तेमाल करने वाले applications में यह differential equations से भरी होती है
    • संबंधित explanation Extended Kalman Filters article में आगे जारी है
  • इस example की H matrix एक simple matrix है जो state estimate और error covariance की तुलना पूरी position और velocity से नहीं, बल्कि केवल position values से करने के लिए reduce करती है

चरण 4: Kalman Gain calculation

  • Kalman Filter हर नए measurement के लिए Kalman Gain calculate करता है
  • Kalman Gain तय करता है कि input measurement system state estimate को कितना प्रभावित करेगा
  • अगर measurement का noise बहुत बड़ा हो, तो Kalman Gain नए लेकिन inaccurate information की तुलना में current state estimate पर ज्यादा भरोसा करवाता है
  • current estimate और नई measurement information को सही weight देकर optimal estimate बनाना Kalman Filter algorithm का core है

चरण 5: state और error covariance update

  • Kalman Filter Kalman Gain का उपयोग करके input measurement के समय की system state और error covariance matrix estimate करता है
  • Kalman Gain दोनों calculations में measurement को सही weight देने के लिए इस्तेमाल होता है
    • नया system state estimate calculate करना
    • system state error covariance calculate करना
  • calculated state estimate ही Kalman Filter द्वारा रखी जाने वाली एकमात्र state history है
  • इसी characteristic की वजह से Kalman Filter low memory constraints वाले devices पर भी implement किया जा सकता है

सारांश

  • Kalman Filter optimal state estimation के लिए एक general-purpose process है
  • इसे accurate estimation की जरूरत वाले कई तरह के applications में इस्तेमाल किया जाता है
  • छोटे steps में बांटने पर Kalman Filter के काम करने का तरीका कम भारी और समझने में आसान structure के रूप में दिखता है

संबंधित पढ़ाई

1 टिप्पणियां

 
GN⁺ 2024-02-13
Hacker News की रायें

  • Kalman filter की बात हो और इस शानदार learning resource का लिंक न आए, ऐसा नहीं हो सकता। यह Jupyter notebooks के संग्रह के रूप में लिखी गई किताब है: https://github.com/rlabbe/Kalman-and-Bayesian-Filters-in-Pyt...
    यह किताब alpha-beta filter को एक तरह से पूरे Kalman filter का छोटा भाई मानकर चलती है। हाल ही में काम में कुछ मिलता-जुलता चाहिए था, इसलिए काफी पढ़ते-पढ़ते मुझे समझ आया कि alpha-beta filter और Kalman परिवार का ध्यान निकट भविष्य की भविष्यवाणी पर ज्यादा होता है, जबकि मुझे असल में पिछले data की smoothing चाहिए थी।
    इसलिए मैंने double exponential smoothing पढ़ना शुरू किया। यह use case के लिए बिल्कुल सही लगा, और जितना गहराई में गया, उतना पता चला कि यह आखिरकार वही alpha-beta filter है, बस variable names अलग हैं।
    इस पूरे math क्षेत्र के नीचे कुछ साझा basic theories हैं, लेकिन अलग-अलग fields अलग approaches से उसी system तक पहुंचती हैं, जिससे names और notation अलग हो जाते हैं और समानता छिप जाती है। लगता है कि power series, natural constant, gradient descent, filters, feedback systems, general systems theory जैसी चीजों के केंद्र में intuition का कोई अपेक्षाकृत छोटा core होगा; अगर वह पकड़ में आ जाए तो बहुत-सा math खूबसूरती से जुड़ जाएगा।

    • mathematicians के एक-अक्षर variable names इस्तेमाल करने पर नाराज़ होना अक्सर असली मुद्दे को चूकना है। छोटे नाम equations और relations की structure पर ध्यान दिलाते हैं, और pattern match करना आसान बनाते हैं: “रुको, यह तो बस नाम अलग है, structure वही है जो मुझे X में पता है।”
      यह कागज़ बचाने या लिखना आसान बनाने के लिए नहीं है। English keyboard से LaTeX में superscript/subscript वाले Greek letters लिखना शब्द लिखने से आसान नहीं होता। मकसद reader तक ऐसी खास जानकारी पहुंचाना है जिसे किसी और तरीके से बताना मुश्किल है।
      math notation अक्षरों जैसी दिखती है, लेकिन मूल रूप से काफी चित्रात्मक notation है, और लंबे शब्द उस चित्र को ढक देते हैं।
    • आप जिसे खोज रहे हैं, वह linear या nonlinear dynamical systems theory के करीब है। अफसोस की बात है कि consistent notation से supported intuition का कोई एक core नहीं है; इसके बजाय कई perspectives हैं जो आपस में consistent नहीं हैं।
      control और signals/systems की अच्छी classes लेने पर वैसी intuition स्वाभाविक हो जाती है, और आप किसी खास notation convention से चिपके बिना math और terminology सीखते हैं। असली intuition यह है कि “सब कुछ filter है”, बाकी सब उस idea का analysis और synthesis है।
    • Dieter Fox, Sebastian Thrun, Wolfram Burgard की Probabilistic Robotics देखना अच्छा रहेगा। यह Kalman से जुड़े कई topics को consistent notation के साथ Bayesian तरीके से व्यवस्थित करती है।
      AI/ML के बढ़ने के साथ classical control theory के ideas भी reinforcement learning के साथ मिल रहे हैं।
    • अगर Q और R constants हैं, तो जैसा आम तौर पर होता है, gain तेजी से converge हो जाता है, और Kalman filter prediction step वाला exponential filter बन जाता है। कई लोगों के लिए यह तरीका कहीं ज्यादा समझने में आसान है और real-world usage से भी अच्छी तरह मेल खाता है।
      क्योंकि आमतौर पर Q और R को “जब तक अच्छा न दिखे” हाथ से tune किया जाता है, फिर बदला नहीं जाता। ऊपर से Q और R जैसे कई values tune करने के बजाय सिर्फ एक gain हाथ से adjust करना पड़ता है।
    • पहले मेरे मन में भी बहुत मिलता-जुलता विचार आया था। trick यह है कि कई filters आखिरकार alpha/beta पर आकर टिकते हैं, और Kalman filter को उस तरीके की तरह देखा जा सकता है जो linear model और measurement noise variance अच्छी तरह मालूम होने पर वे constants निकालता है।
      अगर measurements का noise हमेशा समान हो, तो समय के साथ यह constants पर converge हो जाता है; और जब measurement accuracy अच्छी तरह पता हो लेकिन बहुत बदलती हो, तभी यह खास तौर पर उपयोगी बनता है।

  • हाल ही में मुझे Kalman filter implementation करनी पड़ी, और developer के तौर पर मेरी समझ में आने वाली भाषा में अच्छा material ढूंढना सचमुच बहुत मुश्किल था। करीब एक महीने सीखने के बाद मैंने दो posts लिखीं, शायद किसी के काम आएं: https://www.splinter.com.au/2023/12/14/the-kalman-filter-for..., https://www.splinter.com.au/2023/12/15/the-kalman-filter-wit...
    developer के नज़रिए से विडंबना यह थी कि खुद implement करने के बाद ही मुझे math समझ आया। लगता है सीखने का तरीका यही है कि जो पहले से पता है, उसके ऊपर layer बनाते जाओ; पता नहीं इसके लिए कोई term है या नहीं।

  • मेरा हमेशा मानना रहा है कि अगर गणित में वर्णनात्मक variable names इस्तेमाल किए जाएं, तो उसे सीखना कहीं आसान होगा। कम से कम web जैसे interactive medium में तो tooltips ही डाले जा सकते हैं। गणित पढ़ते समय मेरा 90% समय symbols खोजने में चला जाता है
    और यहां जब subscript के बारे में कहा जाता है कि वह “measurement का क्रम दिखाता है”, तो यह स्पष्ट नहीं होता कि किस क्रम की बात है। शायद मतलब index से है। हालांकि Kalman filter को हाथ लगाए मुझे काफी समय हो गया है

    • लोग अक्सर यह भूल जाते हैं कि mathematical notation को algebraic manipulations को follow करना आसान बनाने के लिए design किया गया है। यह इरादा नहीं होता कि notation को देखकर ही उसका अर्थ साफ हो जाए; E=mc^2 जैसी equation अपने-आप meaningful होनी चाहिए, ऐसा सोचने वाले ज्यादातर physicists होते हैं
      गणित जितना ज्यादा pure होता जाता है, ज्यादातर variables का scope उतना ही छोटा होता जाता है। आम तौर पर variable इस्तेमाल से ठीक पहले define होता है, और उसका scope भी उस proof या derivation से आगे नहीं जाता
      हालांकि इस लेख की कुछ choices बस अजीब हैं। जैसे P को variable और index दोनों की तरह इस्तेमाल करना, और precision matrix covariance matrix का exact inverse होने के बावजूद P को covariance matrix के लिए इस्तेमाल करना
    • papers पढ़ते समय मुझे यही चीज सबसे ज्यादा नापसंद है। लेखक abstract और academic सुनाई देने की कोशिश में बस परेशान करने लायक vague हो जाते हैं। sentence को समझ में आने लायक बनाने के लिए subject और object डालने पड़ते हैं
      research papers में सबसे झुंझलाने वाली बात यही ambiguity है। इसे बिल्कुल clear करना चाहिए। relative expressions नहीं, absolute descriptions इस्तेमाल करनी चाहिए। “दाईं ओर देखें” नहीं कहना चाहिए। मैं बाईं ओर भी देख सकता हूं
      अगर आप लिखते हैं “prism को rotate करने के बाद light cone...”, तो यह छूट जाता है कि rotation किस दिशा में है। left या right, horizontal या up-down, fast या slow। लिखने वाले के दिमाग में ये सारे key elements बने होते हैं, लेकिन reader उसका मन नहीं पढ़ सकता
    • पूरी तरह सहमत। मुझे ऐसा ही लगा कि अभी तक किसी ने जो सबसे अच्छी math book नहीं लिखी है, वह ऐसी होगी जो notation और variables के अर्थ को अच्छी तरह व्यवस्थित करे और कई fields के theorems को साफ तरीके से curate करे
    • यहां जिस क्रम की बात है, वह वह time-based index है जिससे values map होती हैं। उदाहरण के लिए x_3 तीसरे time step की state है
      subscript “p” शायद prediction, यानी पूर्वानुमान, को दर्शाता है। time 3 पर x_p वह state है जिसकी time 4 पर उम्मीद है। लेकिन जब सचमुच time 4 आता है, तो नए measurement को शामिल करके x_4 calculate किया जाता है
      साफ कहें तो यह x_4, time 3 पर calculate किए गए x_p से अलग है। क्योंकि predictions हमेशा थोड़ी-बहुत गलत होती हैं
    • मुझे लगता है variable names पहले से ही descriptive रखने के लिए चुने गए हैं। कोई जानबूझकर उन्हें ज्यादा opaque या track करना मुश्किल बनाने के लिए नहीं चुनता
      समस्या यह है कि जो व्यक्ति अभी शुरुआत कर रहा है, उसने अभी concepts या हर problem domain की standard notation नहीं सीखी होती, इसलिए किसी नए topic में उतरने की तकलीफ बनी रहती है

  • Kalman filter शायद उन अजीब मामलों में से एक है जहां गणित में simplified version इतना simplify कर दिया गया है कि असली रूप लगभग दिखता ही नहीं
    असल में यह करता क्या है: एक measurement लेना, संभावित future states को simulate करना, फिर इस information को अगले measurement के साथ combine करना, और इसे repeat करना
    उदाहरण के लिए tennis ball की कई photos लेना, पहली photo से position और velocity estimate करना, फिर simulate करना कि वह कहां जाएगी, और अगली photo से compare करके देखना कि कौन-सा estimate सच के ज्यादा करीब है। एक और पुराना तरीका यह सोच सकते हैं कि सूरज की ऊंचाई measure करके map पर संभावित locations की एक line बनाई जाए, और उसकी तुलना उस point से की जाए जहां आप पहले खुद को मान रहे थे
    बेशक exact calculation practically लगभग impossible है। इसलिए sampling से simplify किया जाता है। फिर भी यह कठिन है, इसलिए assume किया जाता है कि distribution कुछ हद तक Gaussian distribution के करीब है। वहां से और simplify करके अगर मान लें कि system में बदलाव linear transformation है, तो वही Kalman filter बनता है जिसकी यहां चर्चा है
    अगर कोई सिर्फ linear algebra देखकर समझ सके कि असल में क्या हो रहा है, तो यह हैरान करने वाली बात होगी

    • Kalman filter की explanations अक्सर अजीब तरह से “यह बहुत simple है!” से शुरू होती हैं। original post भी इसी format में है
      इस explanation ने पहली बार मुझे असल में क्या हो रहा है, इसकी intuition दी। computer-side का व्यक्ति होने के नाते, मेरे लिए इसका नाम भी काफी misleading है। क्योंकि यह stream processing या SQL में कहे जाने वाले filter जैसा नहीं है
    • इसे और simple ढंग से कहा जा सकता है। linear algebra तो उल्टा आसान है
      Kalman filter उन hidden inputs का estimate करना चाहता है जिनसे measurements बने। इसके लिए वह x के लिए [actual_measurement - expected_measurement(x)]^2/s^2 को minimize करने की problem बनाता है। यहां s noise का sigma है
      यह x के लिए actual_measurement देखने की likelihood को maximize करने वाली state estimation problem से आता है। क्योंकि likelihood function में important term सिर्फ -([x-expected(x)]/s)^2 होती है। normal distribution या सच कहें तो किसी भी exponential distribution के exponent part को देख लें
      actual_measurement constant है, इसलिए अगर expected_measurement function linear है, तो convex optimization से सीधे solve हो जाता है। differentiate करके 0 के बराबर रखकर solve करें, तो Kalman filter का update step निकल आता है
      अगर function nonlinear है, तो आप equation को linearize करके minimize करते हैं, और उस “fake linearization” का solution return करने वाला Newton-Raphson का एक step कर रहे होते हैं। यह undergraduate-level calculus और linear algebra है, बस किसी ने इसे इस तरह बताया नहीं
      लेकिन यह पूरी तरह गलत भी है। यह 1960s का एक hack है, जिसमें ऐसे recursive single-step linearization से likelihood function को maximize करने की कोशिश की गई थी। Cramér-Rao bound को गलत पढ़ने के कारण कई पीढ़ियों के engineers मानते रहे कि यह optimal है, लेकिन असल में ऐसा नहीं है
      आज हमारे पास 10,000 गुना ज्यादा compute resources हैं, और nonlinear equations को कई Newton-Raphson steps में formulate करके solve करना, या लंबी measurement history बनाए रखना और उस पूरे bundle को कई Newton-Raphson steps में solve करना, या multimodal measurement functions को support करने के लिए Gaussian mixture representations इस्तेमाल करना बेहतर performance देता है
      ये चीजें 1980s से अब तक की state estimation research में अच्छी तरह cover की गई हैं, लेकिन textbooks अब भी जैसे 1972 में पत्थर पर खुदी हुई हों
      Cramér-Rao bound तभी defined होता है जब सभी measurement likelihood functions true state पर linearize किए जाते हैं; यह सभी measurements को preserve करने वाले bundle में सिर्फ asymptotically possible है, अनंत समय पहले possible नहीं है और recursive filter से भी possible नहीं है

  • पुरानी व्याख्याओं में मुझे यह लेख अच्छा लगा था: https://www.bzarg.com/p/how-a-kalman-filter-works-in-picture..., https://news.ycombinator.com/item?id=13449229

  • अगर सच में Kalman filter की ज़रूरत हो, तो लगता है कि इस लेख या Wikipedia डॉक्यूमेंट, या implementation source (https://github.com/LdDl/kalman-rs/blob/master/src/kalman/kal...) को पढ़कर समझा जा सकता है
    लेकिन मेरे अनुभव में, दुनिया के लगभग सभी लोग उदाहरणों से सबसे अच्छा सीखने वाले visual learners होते हैं। इसलिए पेज के बीच में मौजूद tutorial में formulas में example numbers न डालना हैरान करता है। हो सकता है मैंने miss कर दिया हो, लेकिन diagrams भी “Kalman filter क्या है” वाले text का एक पेज आने के बाद ही शुरू होते हैं, और वे diagrams भी बस और ज़्यादा formulas हैं

    • दूसरी तरफ़ किसी ने कहा था कि variable-name conventions, math topics को सीखने और समझने में बाधा बनते हैं, और उस नजरिए से भी मैं सहमत हूँ। लेकिन यहाँ बताई गई समस्या से मैं और ज़्यादा सहमत हूँ
      यह इतना आम है कि हैरानी होती है। इसके हल्के रूप में यही समस्या उन software libraries में भी दिखती है जिनमें code examples शामिल नहीं होते

  • जो बात मुझे समझ में आई, वह यह थी कि दो uncertain measurement distributions, यानी ज़्यादा variance वाली distributions को मिलाने पर एक ज़्यादा निश्चित measurement, यानी ज़्यादा narrow distribution बनती है
    इस ज़्यादा निश्चित measurement को अगले measurement के साथ फिर से combine करके दोहराते रहें, तो वही Kalman filter बन जाता है

  • KF समझाने वाले videos के समूह में यह वाला सच में अच्छा था। मूल लेख की सामग्री से ज़्यादा अच्छी तरह समझ आया: https://www.youtube.com/watch?v=CaCcOwJPytQ

  • मेरे दिवंगत पिता ने अपने पूरे career में इस filter का अक्सर इस्तेमाल किया, उस समय से जब यह filter अभी-अभी invent हुआ था। वे radar और missile guidance systems पर काम करते थे

  • आंखें बंद करके कुछ देर चलकर देखिए। कल्पना कीजिए कि आप कहाँ हैं, फिर आंखें खोलें—क्या आपकी असली position आपके सोचे हुए स्थान से अलग है?
    वह अंतिम step, यानी observations का इस्तेमाल करके state variables के बारे में belief को update करना, यही Kalman filter करता है