Viterbi Algorithm
ฝัง
- เผยแพร่เมื่อ 29 ก.ย. 2024
- Short description of the Viterbi Algorithm without equations using a trip planning example.
Correction: Viterbi first published this in 1967, not 1968 as stated in the video. Here is the original reference:
Andrew J. Viterbi, "Error Bounds for Convolutional Codes and an Asymptotically Optimum Decoding Algorithm," IEEE Trans. Information Theory, vol. 13, pp. 259-260, April 1967.
Also see the seminal paper by David Forney showing several applications of the Viterbi Algorithm:
G. D. Forney, Jr., "The Viterbi Algorithm," Proc. IEEE, Mar. 1973, pp. 268-278.
I watched all the Viterbi videos on youtube and this was by FAR the best. This is ultimately an intuitive algorithm and describing using the language of math masks that. Thank you and please make more videos!
Best explanation of this algorithm I have seen so far.
Thanks Chugg
This looks like Djikstra's algorithm rather than Viterbi.
Although Dijkstra's has only one starting point and one endpoint, not multiple on each side.
Using some kind of Dijkstra-equivalent algorithm, the final hop from Pittsburg to MIT would never be calculated: the route via Tallahassee would be calculated first, since it's the shortest route at the penultimate iteration. Having calculated the total for USC to Daytona Beach, the final hop on the USC to MIT route (i.e. Pittsburg to MIT) would then not be calculated as the ENTIRE route USC-Daytona Beach is shorter than the total for USC-Pittsburg.
This hints at a simple efficiency saving which could be used to speed-up the Viterbi Algorithm as described in the video. I'm sure there are way better ways of doing it though, I'm not a mathematician or computer scientist and the idea I could improve a 53 year-old algorithm having watched one video on it would be nuts.
Still, this being an internet comment section, yor all loosers, what do we even pay for these a'hole's educayionun, I made it better in just two minutes.....TRUMP 2020!
@Sanchit Singh LOL
You should make more videos! This was an excellent explanation. Thanks.
This was helpful. Thank you.
This algorithm doesnt seem to be as efficient as Dijkstra's. Is this true? In practise, if you have a bunch of nodes, how would you find all the nodes on the west coast and all the nodes on the east coast programmatically? Is it manual selection and input it to the algorithm as a parameter? This is where I see this as more efficient than Dijkstra. Where you hsve a bunch of origins and destinations, and you just want any shortest paths from any of the origins to the destinations. Where dijkstra, you have to do a shortest path compute between all of the origins and destinations, and then get the shortest. In the above example it would be 16 searches, seatle to MIT, settle to Washington, settle to Wilmington, settle to Daytona, new Port to MIT and so on... is this correct?
you're better than professor Thad in Georgia Tech uni who taught me AI course! in MS in CS! tell me your bank account number...
This is so pretty and also perfect for visual learners, thank you!
One picture is worth 1000 words. One well made video is worth 4 years of studying on a university.
That Albuquerque just distracts me and reminds me breaking bad :)))))
Found the best explanation and the most intuitive illustration of Viterbi algorithm! Love it!
Great video. I've spent half this day deriving all the equations, still having no idea what I'm actually doing. This is the sort of content that really complements the calculations.
Great video, truly brilliant explanation pitched perfectly for an introduction.
I'd really love it if you could go from this to a more complex example though, like decoding convolutional codes.
Can you suggest a book I can read for this? Thanks.
The paper by Forney in the video description is a good reference. Most textbooks on digital communications or coding will cover this and many follow Forney’s survey paper.
This is so well explained!! better than only given an equation, thanks a ton!
Perfect example. Thank you, you saved me a lot of time :D
Great explanation, very clear and concise. Thanks Keith!
Vegas is a MUST so gotta start from San Fransisco or USC, lets say USC cuz its closer. Then Albuquerque, take pics of breaking bad sets, may be smoke a little. After that, its Amarillo, cuz frankly, who the hell wants to drive 700 miles just to see San Antonio. Then Kansas City(just to see mahomes), Nashville (for hot chicken and biscuits), and Roanoke(visti the greatest college in the world, VT!!). Then head over to Daytona beack and Partyyyy.
Your example gave a very good perspective other than the ordinary one. Thanks a lot.
It’s pronounced “Peer”. - former South Dakotan.
"irregardles?" 3:30-4:30?
Wow Viterbi explaining Viterbi! Impressive
Helpful and interesting. Moreover, attractive voice!
Wow this kind of real world example makes it much easier to understand the underlying concept. Thanks a lot for making this a free video on TH-cam. 🙂
you spelled Pittsburgh wrong
Excellent video!
Thanks for the beautiful explanation.
the explanation is cool but you need a map with the states names to understand better :].
thanks alot for this short course
ps I just noticed that the names are already there
Best Viterbi video!!! super simple!!
Thanks a lot!
I finally understand what the algorithm is about. Thank you
But what if I am in Newport?
UvuvwevwevweOnyetenyevweUgwemuhwemOssasVEVO do the same thing, but eliminate Seattle, San Fran, and USC. It's simply one step less to do than before
It will be great if you mention the algorithm is running in topological order
Really useful and intuitive explanation. Thank you!
Thanks! I *finally* have the intuition for Viterbi, phew! Great down-to-earth, enjoyable video! you're doing wonders for algo-tourism!
looking for more videos❤
Very nice video, I only wonder a bit of the Viterbi properties? Is it always guaranteed to work? Is it the best possible algorithm? What are the alternatives? Other applications, actually Wiki talks about Markov chains, which looks a bit disconnected to traveling.
The VA is the best detector (classifier) for the sequence of states in a discrete time Markov chain observed with independent additive noise. See my reply to nowhereman. It is optimal in that it minimizes the probability of selecting the wrong sequence. An alternative is to minimize the probability of state error (ie, choosing the wrong city on a given day). The forward-backward algorithm solves that problem and is analogous to running two Viterbi algorithms - one left to right and the other right to left. The key step for the VA to be optimal is that the cost is any path to the east of a city does not depend on what path you took to the city. When this does not hold, the VA can be viewed as a heuristic tree search algorithm. Search tree search algorithms for more alternatives in that case.
Thank you so much
Thank you, But what if I'm in Seattle and just want to go to Washington?
only start a path in Seattle and you will have several survivors when you reach the east coast. The one that ends in Washington is the shortest path from Seattle to Washington.
How this example maps formally to general formulas of the algorithm, what would be observations?
Usually, you have a set-up like:
z[n] = y(n; s[n], a[n]) + w[n]
where w[n] is an iid noise sequence and y[n] is the output of a finite state machine with state s[n] and input a[n] being an independent digital sequence. In the video example, s[n] can be any city for day n and a[n] is a digital variable that determines which edge you follow from the current city. The FSM means that given your state s[n] and the input a[n], you can determine the next state s[n+1] and the output y[n].
With that, the "mileage between cities" is the state transition metrics which is
M[s[n], a[n]] = - log( p(z[n] | y(n; s[n], a[n]) p(a[n]).
This is abstracted out in the video to make the core part of the VA clear. If a[n] is binary and equally likely to be 0 or 1, and w[n] is Gaussian, then the transition metric can be simplified to the euclidean squared metric
M[s[n], a[n]] = | z[n] - y(n; s[n], a[n]) |^2
Label each edge in the trellis with this metric and you're ready to run the VA as in the video
@@keithchugg5604 Thank you.
Tiger on a car.
Do you have code for the example?
This is paper and pencil example! I am sure there are many implementations of teh VA on GitHub.