Viterbi algorithm
The conceptHow a map app snaps your wobbly GPS trace onto the right road
GPS points drift by metres, so a point can sit between two roads. The Viterbi algorithm finds the single most likely sequence of hidden things (here, the roads you really drove on) behind a series of noisy observations (the GPS points).
Two probabilities drive it. Transition: how likely you are to move from one road to another between readings. Emission: how well a GPS point fits a road. The best route has the largest product of these.
Instead of testing every possible route, it works forward one reading at a time. For each road it keeps only the best route that ends there so far, and remembers which road that route came from.
What it’s forFinds the best score for a route that ends on road s at reading t.
Vₜ(s) = maxᵣ [ Vₜ₋₁(r) · P(s | r) ] · P(oₜ | s)
- Vₜ(s)
- probability of the best route ending on road s at reading t
- r
- the road at the previous reading, tried one by one
- P(s | r)
- transition: chance of moving from road r to road s, e.g. 0.8 to stay on the same road
- P(oₜ | s)
- emission: how well GPS point oₜ fits road s
What it givesOne best score per road at each reading, plus a pointer to the road it came from.
- V₁(A)=0.6, V₁(B)=0.4; staying on a road 0.8, switching 0.2; new point fits A 0.3, B 0.7
- V₂(A) = max(0.6·0.8, 0.4·0.2)·0.3 = 0.48·0.3 = 0.144
- V₂(B) = max(0.6·0.2, 0.4·0.8)·0.7 = 0.32·0.7 = 0.224