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!
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.
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!
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.
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?
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.
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.
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
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.
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
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.
![Lp. Сердце Вселенной #60 РОЖДЕНИЕ ЛОЛОЛОШКИ [Финал] • Майнкрафт](http://i.ytimg.com/vi/YoR0pAV9FVQ/mqdefault.jpg)
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!
This is a very clear, well-detailed and informative explanation. Thank you!
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.
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 UA-cam. 🙂
You should make more videos! This was an excellent explanation. Thanks.
Best explanation of this algorithm I have seen so far.
One picture is worth 1000 words. One well made video is worth 4 years of studying on a university.
Found the best explanation and the most intuitive illustration of Viterbi algorithm! Love it!
This was helpful. Thank you.
This is so well explained!! better than only given an equation, thanks a ton!
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
This is so pretty and also perfect for visual learners, thank you!
Your example gave a very good perspective other than the ordinary one. Thanks a lot.
Great explanation, very clear and concise. Thanks Keith!
Helpful and interesting. Moreover, attractive voice!
Really useful and intuitive explanation. Thank you!
Thanks for the beautiful explanation.
Thanks! I *finally* have the intuition for Viterbi, phew! Great down-to-earth, enjoyable video! you're doing wonders for algo-tourism!
Best Viterbi video!!! super simple!!
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.
looking for more videos❤
I finally understand what the algorithm is about. Thank you
Perfect example. Thank you, you saved me a lot of time :D
Wow Viterbi explaining Viterbi! Impressive
Thank you so much
Thanks Chugg
Excellent video!
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?
That Albuquerque just distracts me and reminds me breaking bad :)))))
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.
Thanks a lot!
It will be great if you mention the algorithm is running in topological order
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.
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.
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.
"irregardles?" 3:30-4:30?
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
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.
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
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.
Tiger on a car.
It’s pronounced “Peer”. - former South Dakotan.
you spelled Pittsburgh wrong
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...