RightSignal
1 of 4

Your RightSignal

Concept of the day1 / 3

Viterbi algorithm

The concept

How 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.

  1. 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
  2. V₂(A) = max(0.6·0.8, 0.4·0.2)·0.3 = 0.48·0.3 = 0.144
  3. V₂(B) = max(0.6·0.2, 0.4·0.8)·0.7 = 0.32·0.7 = 0.224