प्रोग्रामर्स के लिए Kalman Filter का गैर-गणितीय परिचय

(praveshkoirala.com)

6 पॉइंट द्वारा GN⁺ 2023-08-03 | 1 टिप्पणियां | WhatsApp पर शेयर करें

वास्तविक दुनिया में position और velocity की measurements हमेशा डगमगाती रहती हैं, इसलिए Kalman Filter को कई अपूर्ण सूचना स्रोतों को मिलाकर अधिक भरोसेमंद state estimate बनाने की विधि के रूप में समझा जा सकता है
जहाज की position वाले उदाहरण में engine speed 10m/s वाला model हवा और लहरों के कारण चूक जाता है, और GPS जैसे sensors भी noise या रुकावटों की वजह से हमेशा सटीक नहीं होते
example code में 1000 passengers में से हर कोई velocity-based estimate और sensor measurement बनाता है, और दोनों values को weighted average से मिलाकर Kalman Filter की intuition दिखाता है
सूचना स्रोतों की reliability measurements के variance से निकाली जाती है; जिस तरफ variability ज्यादा हो उसे कम भरोसा दिया जाता है और जो तरफ consistent हो उसे ज्यादा वजन देने के लिए 1/variance इस्तेमाल किया जाता है
sensor सामान्य होने पर sensor values को ज्यादा follow किया जाता है, और t=3·t=6 जैसे unstable intervals में उसका असर अपने-आप घट जाता है, जिससे estimate ज्यादा stable बना रहता है

Kalman Filter की जरूरत कब पड़ती है

Kalman Filter को एक funnel की तरह देखा जा सकता है, जो कई noisy information sources को एक ज्यादा accurate statistical value में compress करता है
गणितीय रूप से इसमें linear algebra, probability theory और calculus जुड़े होते हैं, लेकिन यहाँ पूरा theory नहीं, बल्कि intuition पर focus है
मान लें कि एक जहाज port x=0 से शुरू होकर 1D में चलता है, और engine 10m/s की constant velocity देता है
ideal world में 2 सेकंड बाद position 2 * 10 = 20m होगी, लेकिन real world में engine, हवा और लहरों के कारण velocity और position बिल्कुल accurate नहीं रह पाते
इसलिए सिर्फ position formula से जहाज की actual position को लेकर भरोसा करना मुश्किल है

Sensors भी perfect नहीं होते

GPS जैसे sensors हों तो किसी खास समय की position को सीधे measure किया जा सकता है, लेकिन sensor measurements भी हमेशा accurate नहीं होते
GPS 3 सेकंड पर 29.998m, 30.002m जैसी actual position के करीब values दे सकता है, और बहुत rare cases में 100m जैसी बहुत ज्यादा दूर की value भी दे सकता है
जहाँ satellite coverage नहीं है, वहाँ GPS sensor practically काम नहीं कर सकता
अगर sensor कभी offline न हो और arbitrary precision से मनचाही value measure कर सके, तो Kalman Filter की जरूरत नहीं होगी
Kalman Filter velocity-based position estimate, GPS estimate, radar, sonar जैसे कई information sources को combine करके position को अधिक accurate तरीके से estimate कर सकता है

Code से position estimate देखना

example में माना गया है कि जहाज पर 1000 passengers हैं, और हर passenger के पास अपना GPS device है
हर passenger पहले previous position में velocity और external factors की variability जोड़कर new position estimate करता है

from random import gauss
def new_position(last):
    velocity = 10
    wind = gauss(0, 2)
    wave = gauss(0, 0.1)
    return last + velocity + wind + wave

gauss positive या negative random values बनाता है, और दूसरा parameter variability का size बताता है
हवा और लहरों के effect को सीधे measure नहीं किया जा सकता, इसलिए example में mean 0 और standard deviation 2, 0.1 वाले random numbers से noise model किया गया है
दूसरे step में sensor actual position में sensor noise जोड़कर measurement return करता है

def sensor(t):
    if t == 3:

# oops, passing through a thunderstorm. GPS fluctuating!
        sensor_noise = gauss(5, 10)
    elif t == 6:

# uh-oh, satellite unavailable!
        sensor_noise = gauss(-5, 10)
    else:
        sensor_noise = gauss(0, 1)
    return true_position[t] + sensor_noise

t=3 पर thunderstorm के कारण GPS में fluctuation, और t=6 पर satellite unavailable होने की स्थिति को model किया गया है
एक ही समय पर भी हर passenger के sensor measurements अलग-अलग आते हैं

Actual route और simple average

जहाज की actual position नीचे दी गई list से दी जाती है

true_position = [0, 9, 19.2, 28, 38.1, 48.5, 57.2, 66.2, 77.5, 85, 95.2]

जहाज port x=0 से शुरू होकर 1 सेकंड बाद 9m, 2 सेकंड बाद 19.2m, और उसके बाद list की values की तरह चलता है
passenger का लक्ष्य noisy और unreliable measurements से हर second की position को जितना संभव हो उतना accurately predict करना है
t=1 पर किसी passenger का velocity-based estimate 9.37 और sensor measurement 8.98 हो, तो simple average 9.17 है
actual position 9m होने पर यह simple average velocity estimate से कम error देता है, लेकिन इस example के sensor measurement से खराब है

Weighted average और reliability

simple average से बेहतर method के रूप में weighted average इस्तेमाल किया जाता है

def combine(A, B, trustA, trustB):
    total_trust = trustA + trustB
    return (A * trustA + B * trustB) / total_trust

combine(9.37, 8.98, 10, 1) velocity estimate पर ज्यादा भरोसा करता है, इसलिए result 9.37 के करीब 9.33 होता है
combine(9.37, 8.98, 1, 10) sensor measurement पर ज्यादा भरोसा करता है, इसलिए result 8.98 के करीब 9.01 है
यह reliability-based weighted average Kalman Filter की core intuition है, और data combine करने का center of gravity है
किस information source पर ज्यादा भरोसा करना है, यह variance से तय होता है
- जिन information sources के conclusions बहुत fluctuate करते हैं, उन पर कम भरोसा किया जाता है
- जिन information sources के conclusions consistent होते हैं, उन्हें ज्यादा भरोसा दिया जाता है
- अगर 10 radio stations में से 4 बारिश और 6 साफ मौसम बता रहे हों, और 10 websites में से 9 बारिश बता रही हों, तो websites वाली तरफ variance कम होने के कारण उस पर ज्यादा भरोसा किया जा सकता है

Update step

पूरा update passenger-wise velocity-based estimates और sensor measurements बनाने के बाद, measurement के दोनों groups के variance से reliability calculate करता है

from statistics import variance

def update(t, last):
    velocity_updates = []
    sensor_updates = []

    for p in range(1000):
        velocity_updates.append(new_position(last[p]))
        sensor_updates.append(sensor(t))

    fluctuation_velocity = variance(velocity_updates)
    fluctuation_sensor = variance(sensor_updates)

    trust_velocity = 1 / fluctuation_velocity
    trust_sensor = 1 / fluctuation_sensor

    combined = []
    for p in range(1000):
        combined.append(combine(
            A=velocity_updates[p],
            B=sensor_updates[p],
            trustA=trust_velocity,
            trustB=trust_sensor
        ))

    return sensor_updates, velocity_updates, combined

variance जितना बढ़ता है, reliability उतनी घटती है, इसलिए 1/variance इस्तेमाल किया जाता है
हर passenger अपनी position को individually update करता है
सभी passengers की position updates पूरी होने के बाद, जहाज की actual position estimate passengers की positions के average से निकाली जा सकती है

Results कैसे पढ़ें

update_plot function plot बनाने के लिए हर time point की actual position, sensor estimate, velocity estimate और combined estimate store करता है
main loop passengers के पास मौजूद current best estimate का इस्तेमाल करके हर time point पर position estimate को update करता रहता है
plot में line के आसपास का envelope uncertainty दर्शाता है; width जितनी ज्यादा हो, उस value को लेकर uncertainty उतनी ज्यादा होती है
जब sensor t=0.75 से t=1 interval में सामान्य रूप से काम करता है, तब combined position estimate सिर्फ velocity estimate इस्तेमाल करने से बेहतर होता है, लेकिन सिर्फ sensor measurement इस्तेमाल करने से खराब हो सकता है
जब sensor t=2 से t=4 interval में fail होता है, तब combined estimate failed sensor measurement अकेले इस्तेमाल करने से बेहतर result दिखाता है
sensor के recover होने वाले t=4 से t=5 interval में Kalman Filter फिर से sensor को ज्यादा prefer करना शुरू करता है

Appendix: `gauss` और variance

normal distribution function gauss(0, 0.1) और gauss(0, 2) ज्यादातर 0 के आसपास random values generate करते हैं
दूसरा parameter, यानी standard deviation, control करता है कि measurements कितनी fluctuate करेंगी
- gauss(0, 0.1) से 0.06, -0.07, 0.02 जैसी 0 के आसपास की छोटी values आने की संभावना ज्यादा होती है
- gauss(0, 2) से 1.05, -1.06, 1.29, -1.72 जैसी ज्यादा widely spread values आने की संभावना ज्यादा होती है
example code में माना गया है कि wind ज्यादा vary करती है, और waves कम vary करती हैं
variance consistency का measure है; consistency ज्यादा हो तो variance low होता है, और consistency कम हो तो variance high होता है
standard deviation 2 वाली distribution का variance 4 होता है, और standard deviation 0.1 वाली distribution का variance 0.01 होता है

1 टिप्पणियां

GN⁺ 2023-08-03

Hacker News की टिप्पणियां

लेख पढ़ने में मज़ेदार था, लेकिन implementation गलत है। सबसे बड़ी गलती यह है कि यह uncertainty को time axis पर propagate नहीं करता, जिससे error को कम करके आंका जाता है
ग्राफ़ में भी यह दिखता है: error range को ज़्यादातर समय actual state को include करना चाहिए, लेकिन result में ऐसा नहीं है
यात्री estimates में noise नहीं जोड़ते; बल्कि passenger के नज़रिए से, k समय पर state दिए जाने पर k+1 समय की state का expected value बस position_k+1 = position_k + velocity * Delta_t है। actual dynamics में noise होता है, और filter में इसे estimated covariance में जोड़कर reflect किया जाता है
code तुरंत टूटता नहीं है क्योंकि 1000 यात्रियों से dynamics के बहुत सारे samples लिए जाते हैं और उनके result का variance numerically calculate किया जाता है, लेकिन यह practice में आम तौर पर किए जाने वाले तरीके से काफी अलग है
साथ ही, GPS पर मौसम का असर पड़ता है—यह एक आम गलतफहमी है, असल में ऐसा नहीं है। और लेख में इस्तेमाल की गई consistency की definition भी standard नहीं है। estimation theory में किसी estimator को consistent कहने का मतलब है कि data बढ़ने पर estimate true value की ओर converge करता है
आम पाठकों के लिए इसे आसान बनाकर समझाना अच्छा है, लेकिन लगता है कुछ गलतफहमियां problem पैदा कर रही हैं। मैं estimation theory का graduate student हूं, और अगर और बात करनी हो तो मदद कर सकता हूं
- “actual dynamics में noise होता है, और filter में इसे estimated covariance में जोड़कर reflect किया जाता है” वाले हिस्से को थोड़ा और खोलकर समझा सकते हैं? खासकर estimated covariance क्या है, और उसमें क्या जोड़ा जाता है?
university के signal processing lecture में Kalman Filter को इतना सरल तरीके से क्यों नहीं पढ़ाया जाता, यह सोचने पर मजबूर कर दिया। math concepts को mathematically पढ़ाना सही है, लेकिन जिन लोगों के पास background knowledge कम है उनके लिए information loss हो जाता है
पहले मैंने discrete cosine transform और wavelet transform को image-centric तरीके से पढ़ाया था, और rigor से पहले intuition देने का तरीका उलटे क्रम से हमेशा बेहतर काम करता था
- signal processing सीखने वाले university students के पास ज़रूरी background knowledge होना चाहिए। फिर भी basics भूल जाना आसान है
  professors intuition पहले क्यों नहीं देते, इसके कई कारण हो सकते हैं। कभी professor की अपनी expertise intuition से ज़्यादा numbers और equations manipulate करने में गहरी होती है; कभी teaching ability को reward नहीं मिलता, इसलिए intuitively समझाने में लगने वाला समय research funding proposals या PhD students manage करने में जाता है; और कभी math समझ लेने के बाद intuitive explanation उल्टा “मुश्किल रास्ता” जैसा लगने लगता है और दिमाग वापस जाने से इनकार कर देता है
  खासकर तीसरा कारण मुझे सबसे बड़ा लगता है। यह math education से आगे expertise और teaching ability के फर्क की बात भी है। golf drive सीखनी हो तो सबसे दूर मारने वाले व्यक्ति से ज़्यादा, उस व्यक्ति से सीखना बेहतर हो सकता है जिसने 100 yards से शुरू करके लगातार 300 yards मारना सीखा हो
- पूरी तरह सहमत। university में मेरे पसंदीदा professors में से एक theorem introduce करने के बाद तुरंत proof पर नहीं जाते थे; पहले दिखाते थे कि theorem कहां useful है, फिर proof करते थे
- मुझे याद है कि पहले MIT के online lectures में एक lecture ऐसा था जो formulae के बिना intuition को refine करने के तरीके पर था
Kalman Filter implement करने वालों के लिए एक general warning: numerical instability को handle करने के तरीकों के लिए https://www.stat.berkeley.edu/~brill/Stat248/kalmanfiltering... के शुरुआती कुछ पन्ने पढ़ लेना अच्छा रहेगा
- उस paper में flat initial conditions के लिए Kalman Filter की exact generalization का दिलचस्प reference दिया गया है। मैंने पहली बार देखा; यह arbitrarily large initial covariance चुनने की common practice से पैदा होने वाली numerical problems को solve करता है
  practice में ऐसा करने पर मैंने बहुत कम noticeable numerical artifacts देखे हैं, लेकिन यह काफी आकर्षक solution है
इस लेख के complement के रूप में, अगर Kalman Filter family में ज़्यादा thorough और mathematical introduction चाहिए, तो मैं इस किताब की strongly recommend करता हूं: https://github.com/rlabbe/Kalman-and-Bayesian-Filters-in-Pyt...
यह किताब एक software engineer ने लिखी है जिसे काम के लिए Kalman Filter implement करना पड़ा था, इसलिए concepts को motivate और convey करने का तरीका इस readership के लिए अच्छा fit हो सकता है। यह interactive Jupyter notebooks के रूप में लिखी गई है, इसलिए repository clone करके सीधे run करते हुए follow किया जा सकता है
यह simple filters से शुरू करके Bayes rule जोड़ती है और probability distributions तक extend करती है, इस तरह step by step improve करती है, इसलिए Kalman Filter तक पहुंचने के लिए एक gentle on-ramp देती है
एक aspect छूट गया है। prediction और measurement का weighted average लेते समय, Kalman Filter के weights समय के साथ बदल सकते हैं। वरना शायद इसे किसी और नाम से पुकारा जाता
slow-changing value को single sensor से measure करने का example अच्छा है। जैसे fuel gauge में, seconds के scale पर no change assume करना बेहतर है, लेकिन measurements में tank के अंदर fuel sloshing जैसा noise हो सकता है
इस case में Kalman Filter exponentially decaying gain वाले first-order low-pass filter जैसा दिखता है। cutoff frequency बदलती है, जिससे starting level कुछ seconds में जल्दी मिल जाता है, और उसके बाद 0.01Hz जैसी बहुत low cutoff frequency के साथ noise को ignore किया जा सकता है
एक महत्वपूर्ण टूल पर अच्छा लेख है
मेरी समझ में linear Kalman Filter linear समस्याओं के लिए optimal solution है, और इसे समझना व implement करना अपेक्षाकृत आसान है। लेकिन मैंने जिन ज्यादातर applications को देखा, वे nonlinear थीं
Extended Kalman Filter और Unscented Kalman Filter को समझना और implement करना कहीं ज्यादा कठिन है, और इनके resources व libraries भी कम और कम उपयोगी लगे
उदाहरण के लिए, छोटे UAV के लिए AHRS/GNSS CAN device पर काम करते हुए, PX4 या Ardupilot में देखा गया Extended Kalman Filter बहुत जटिल था और उसमें बहुत सारे parameters थे। इसलिए quaternion के मूल सिद्धांतों से शुरू करके gyro solution को accelerometer के “ऊपर” और magnetometer के inclination vector की ओर थोड़ा-थोड़ा correct करना ज्यादा सरल लगा
अगर acceleration magnitude 1G से बहुत अलग हो या magnetic field vector स्थानीय पृथ्वी के magnetic field strength से काफी अलग हो, तो उस sensor update का weight घटा देना या उसे skip कर देना, और gyro को वैसे ही आगे बढ़ने देना। शायद EKF के सही जवाब होने की संभावना ज्यादा है, लेकिन उसे ऐसी form में fit करने में मैंने हार मान ली जिसे समझना, बनाना या tune/diagnose करना आसान हो
- संदर्भ के लिए, EKF सामान्य Kalman Filter से बहुत ज्यादा जटिल नहीं है। मूलतः dynamics या sensor model को linearize करने के बाद, उसी linear model से Kalman Filter update किया जाता है
  हालांकि quadrotor में बड़ी मुश्किल rotation है। Kalman Filter का linear model मानता है कि सब कुछ Euclidean space में है, लेकिन rotation manifold पर होता है। quaternion के मामले में यह manifold unit quaternions का set है
  quaternion estimate करने के लिए अगर EKF को सीधे-सादे तरीके से लागू करें, तो वह अब unit quaternion नहीं रह जाता और estimates खराब हो जाते हैं। इस manifold constraint को संभालने के well-known तरीके हैं, लेकिन जिन equations को मैंने code में उतारा है, वे सबसे बदसूरत equations में से थीं
  एक सरल उदाहरण के तौर पर ऐसी state (x, y) के बारे में सोच सकते हैं, जिसे physics के laws के कारण हमेशा unit circle पर होना चाहिए। वास्तविक dynamics f(x, y) circle पर एक नया point देता है, लेकिन इसका linearized approximate dynamics unit circle पर बने रहने की guarantee नहीं देता, जिससे non-physical state या EKF state estimate मिल सकता है
- Probabilistic programming languages का उपयोग करने से nonlinear filters implement करना कहीं आसान हो सकता है। आप generative model implement करते हैं और inference compile होकर निकलता है
  देखने लायक विकल्पों में ForneyLab.jl, Infer.net, Gen.jl, Pyro हैं
- अगर public lecture material ठीक हो तो मैं यह material recommend करूंगा: http://mocha-java.uccs.edu/ECE5550/index.html
- अगर आप जानते हैं कि क्या model करना है, तो traditional linear Kalman Filter को व्यक्त करने वाला model इस्तेमाल करना बहुत आसान है
  लेकिन Kalman Filter इस्तेमाल करने के कई तरीके हैं, और आप कहां से शुरू करते हैं, इस पर निर्भर करते हुए nonlinear transformations को सही ढंग से handle करना बेहद झंझट भरा हो सकता है
मुझे myopia और astigmatism है, और जब एक आंख बंद करके दीवार घड़ी जैसी चीज देखता हूं, तो पता चलता है कि हर आंख अलग तरह से distorted image बनाती है। दोनों आंखें थोड़ी-थोड़ी अलग हैं
लेकिन दोनों आंखों से घड़ी देखने पर image काफी ज्यादा sharp होती है, और किसी एक आंख से देखने से बेहतर होती है। लेख में 1000 जहाज यात्रियों के अपने-अपने GPS coordinates report करने वाला scenario इस phenomenon की याद दिलाता है
लगता है कि brain भी Kalman Filter जैसे smart algorithms का व्यापक रूप से उपयोग करता होगा
- अगर उस visual phenomenon में रुचि है, तो इसे hyperacuity का उदाहरण कहा जा सकता है। संयोग से, मैंने भी अपनी आंखों से वही observation करते हुए यह term जाना था
क्या Kalman Filter को यह समझना सही है कि यह noisy observations से simple average की तुलना में बेहतर value estimate देता है?
उदाहरण के लिए, अगर किसी चीज को 3 बार measure किया और 7, 8, 9 मिले, तो हम guess करेंगे कि actual value 8 है; क्या Kalman Filter कोई अलग estimate देगा?
- हां, लेकिन एक बड़ा caveat है। observations किसी transition mechanism जैसी चीज से आपस में जुड़े होने चाहिए। किसी भी problem पर Kalman Filter लगाकर बेहतर result की उम्मीद नहीं की जा सकती
  Kalman Filter पारंपरिक रूप से समय के साथ move होने वाली चीजों का estimate करने के लिए इस्तेमाल होता है। video में किसी व्यक्ति या किसी तरह की random walk के बारे में सोचें
  अगर आप मानते हैं कि दो consecutive time points या measurements के बीच velocity और current direction जैसा relation है, तो motion model की information और noisy measurement model की information को मिलाकर position या value, या पूरी movement history का बेहतर estimate किया जा सकता है
  अगर motion model meaningful तरीके से गलत है, तो estimate improve नहीं होगा। बाद में आई कई extended methods का focus robotics में wheel slip जैसे ज्यादा sophisticated motion models को शामिल करने पर है
- हां। simple average के विपरीत, क्योंकि measuring target और measurement itself के बारे में एक model होता है
  उदाहरण के लिए, मान लें कि आप कोई constant measure कर रहे हैं। basic model में initial uncertainty वाला constant, जैसे standard deviation वाली Gaussian distribution, और measurement values जिनमें Gaussian noise और standard deviation है, रखे जा सकते हैं। आप estimate किए जा रहे constant के आसपास की initial uncertainty और measurements की uncertainty adjust कर सकते हैं
  इस example में Kalman Filter average की तरह behave नहीं करता। अगर measurements अच्छे हैं, यानी uncertainty कम है, तो यह जल्दी converge करता है; अगर measurements खराब हैं, तो estimate हिलता-डुलता है और convergence में ज्यादा समय लगता है
  और यह कहना सही नहीं है कि Kalman Filter केवल moving चीजों के लिए इस्तेमाल होता है। constant estimation में भी इसका हमेशा उपयोग होता है, बस moving objects में यह ज्यादा famous है
- Kalman Filter simple average से बेहतर तब होता है जब samples independent and identically distributed नहीं होते। अगर वे independent and identically distributed हों, तो law of large numbers के अनुसार average निकालना काफी है
  Kalman Filter उन cases को handle करता है जहां किसी linear dynamics की वजह से samples correlated होते हैं। measurements को necessarily target itself होना जरूरी नहीं है; वे target के linear function में Gaussian noise जुड़ा हुआ रूप भी हो सकते हैं
  इसलिए first measurement में 7 देखने की knowledge second measurement में 8 देखने की probability बदल देती है। ऊपर की तरह सिर्फ sample average लेने से आम तौर पर actual mean value पर convergence नहीं होगी
- Kalman Filter multivariate Gaussian model के लिए maximum likelihood दृष्टिकोण से optimal estimate देता है
  आपके example में यह क्या output देगा, यह exact model पर निर्भर है। imaginable simplest scenario में भी Bayes की तरह यह specify करना होगा कि किस expected value से शुरुआत करनी है
- अगर past history हो, तो चीजें अलग हो सकती हैं। मान लें कि आपने पहले भी same target को measure किया था और उस prior information को principle में reflect करना चाहते हैं, लेकिन अगर नए measurements बहुत अलग हों तो new value को ज्यादा dominant होने देना चाहते हैं
  उस expression को linear Gaussian model में encode करें तो वही Kalman Filter बनता है
Kalman Filter को समझने में एक और insight देने वाला छोटा लेख John D. Cook का नोट था: https://www.johndcook.com/blog/applied-kalman-filtering/
पारंपरिक calculus और differential equations आधारित system modeling यह मानती है कि data में कोई uncertainty नहीं है और सब कुछ system model में समाहित है, जबकि data-driven estimator मानता है कि “सब कुछ data में है” और data generate करने वाली physical process के model को पूरी तरह अनदेखा कर देता है
Kalman Filter की खूबसूरती इसी में है कि यह इन दोनों approaches को जोड़ता है
अच्छी visualization वाला एक और लेख भी है: https://www.bzarg.com/p/how-a-kalman-filter-works-in-picture...
यह लेख HN पर पहले ही तीन बार आ चुका है

प्रोग्रामर्स के लिए Kalman Filter का गैर-गणितीय परिचय

Kalman Filter की जरूरत कब पड़ती है

Sensors भी perfect नहीं होते

Code से position estimate देखना

Actual route और simple average

Weighted average और reliability

Update step

Results कैसे पढ़ें

Appendix: gauss और variance

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

1 टिप्पणियां

Hacker News की टिप्पणियां

Appendix: `gauss` और variance