7 ms·

This brings to mind the Viterbi algorithm that calculates the most likely sequence of events in a hidden Markov model (Markov model itself is just a state machi

This brings to mind the Viterbi algorithm that calculates the most likely sequence of events in a hidden Markov model (Markov model itself is just a state machine on a graph with weighed edges, where each weight on a state transition is represented as a probability of that transition). It's essentially bases to the same algorithm: you can eliminate sequences if they lead to the same event that is already part of a solution, but with lesser probability. The amount of paths would be exponential, but the ability to eliminate them keeps it polynomial. That really brings forth the beauty of dynamic programming.

akdas 7y ago
I just literally published an article on that yesterday :) https://avikdas.com/2019/06/24/dynamic-programming-for-machine-learning-hidden-markov-models.html https://avikdas.com/2019/06/24/dynamic-programming-for-machi... Agreed, it's basically the same algorithm.
shaki-dora 7y ago
A lot of problems on sequences are amendable to dynamic programming. Two other famous ones are Smith-Waterman and Needleman-Wunsch for finding optimal global and local alignments of sequences–a typical problem in genetics.
- marton78 7y ago
  The Levenshtein distance, which finds the fewest edits to transform one string to another is also a classical example.
n4r9 7y ago
One really nice application of the Viterbi algorithm is map-matching, i.e. taking a GPS trail and "snapping" it to the road network to determine the actual route taken. It's difficult because GPS trails are often sparse and noisy, so you can't do something simple like "project onto the closest road segment". If you take the "states" of the model to be road segments and derive the transition probabilities from the shortest route between segments, you can apply Viterbi and get a very accurate result most of the time. Of course, calculating shortest routes involves Dijkstra, another famous dynamic algorithm.
- benrbray 7y ago
  Cool! Has anyone written this up and made cool visualizations? It's one of those many things I'd like to do but don't have time for :)
  - cechner 7y ago
    yep - look up 'Hidden Markov Map Matching through Noise and Sparseness' by Krumm and Newson it calculates the final probability by combining 'emission' probabilities (the probability that a GPS observation was on a particular road) by the 'transition' probability that if an observation was on a particular road at one point, what is the probability that it is now on this other road segment. By combining these two the final probability incorporates both the nearness of the GPS signals to the roads and the connectivity of the road network itself. I've found the formulas applied in this paper are good in practice only if the GPS updates are relatively frequent
    - n4r9 7y ago
      I've also found that it can be tricky to map "convoluted" routes that don't necessary go simply from point A to pointB. If you don't mind me asking, roughly what frequency threshold have you found the algorithm to perform badly above, and are you aware of any algorithms or formulae which perform better in these situations?
      - cechner 7y ago
        it should be in seconds - the problem is that the paper assumes that the 'great circle' (straight line) distance between two points should be almost the same as the 'route' distance between those points, with an exponential probability distribution. This means that if the path between two points is not simple (around a corner) the probability drops off very quickly. If the time between measurements is in minutes, this heuristic is pretty useless (and you should really use log-scale for your numbers!) edit: this is actually shown in figure 8 of the paper where they explore different 'sampling periods' edit 2: I have not explored other methods yet, but it would probably make sense to start by deriving the formula the way they do, by exploring ground-truth data. edit 3: I just noticed that my comments are largely repeating what you're saying - sorry!

akdas 7y ago

I just literally published an article on that yesterday :) https://avikdas.com/2019/06/24/dynamic-programming-for-machine-learning-hidden-markov-models.html https://avikdas.com/2019/06/24/dynamic-programming-for-machi... Agreed, it's basically the same algorithm.

shaki-dora 7y ago

A lot of problems on sequences are amendable to dynamic programming. Two other famous ones are Smith-Waterman and Needleman-Wunsch for finding optimal global and local alignments of sequences–a typical problem in genetics.

marton78 7y ago
The Levenshtein distance, which finds the fewest edits to transform one string to another is also a classical example.

n4r9 7y ago

One really nice application of the Viterbi algorithm is map-matching, i.e. taking a GPS trail and "snapping" it to the road network to determine the actual route taken. It's difficult because GPS trails are often sparse and noisy, so you can't do something simple like "project onto the closest road segment". If you take the "states" of the model to be road segments and derive the transition probabilities from the shortest route between segments, you can apply Viterbi and get a very accurate result most of the time. Of course, calculating shortest routes involves Dijkstra, another famous dynamic algorithm.

benrbray 7y ago
Cool! Has anyone written this up and made cool visualizations? It's one of those many things I'd like to do but don't have time for :)
- cechner 7y ago
  yep - look up 'Hidden Markov Map Matching through Noise and Sparseness' by Krumm and Newson it calculates the final probability by combining 'emission' probabilities (the probability that a GPS observation was on a particular road) by the 'transition' probability that if an observation was on a particular road at one point, what is the probability that it is now on this other road segment. By combining these two the final probability incorporates both the nearness of the GPS signals to the roads and the connectivity of the road network itself. I've found the formulas applied in this paper are good in practice only if the GPS updates are relatively frequent
  - n4r9 7y ago
    I've also found that it can be tricky to map "convoluted" routes that don't necessary go simply from point A to pointB. If you don't mind me asking, roughly what frequency threshold have you found the algorithm to perform badly above, and are you aware of any algorithms or formulae which perform better in these situations?
    - cechner 7y ago
      it should be in seconds - the problem is that the paper assumes that the 'great circle' (straight line) distance between two points should be almost the same as the 'route' distance between those points, with an exponential probability distribution. This means that if the path between two points is not simple (around a corner) the probability drops off very quickly. If the time between measurements is in minutes, this heuristic is pretty useless (and you should really use log-scale for your numbers!) edit: this is actually shown in figure 8 of the paper where they explore different 'sampling periods' edit 2: I have not explored other methods yet, but it would probably make sense to start by deriving the formula the way they do, by exploring ground-truth data. edit 3: I just noticed that my comments are largely repeating what you're saying - sorry!