Having recently taken Linear Algebra, I got so excited at around 15:55 when I realized he was about to talk about eigenvectors! What a cool connection!
Or even earlier ca. 6:50 regarding stationary states -- admittedly it's been years since I took LA myself, but I remember this point fondly from e.g. 3b1b's videos: a stationary point, or angle or vector or what have you, is exactly what the eigenvector&value tells you. :)
Just finished my freshman year at UC Berkeley as a CS student, and while watching this video my “Oski senses” were tingling. having found out 2 of my favorite TH-camrs were Cal alumni, I dug around for a bit and found out you too went to UC Berkeley and even taught CS61A. Keep making great videos and providing intuitive explanations to really complex problems. Go Bears!
I think it's the first time I've seen a video showing the movement of a Markov chain so dynamically. It really helps to get a lot of intuition. thank you!
Yeah, when I was looking at other videos on the topic, I was rather surprised to see that no one had shown that way of thinking about it. For me, it just felt like an absolute necessity to understand it!
Wow excellent idea and video quality. PageRank hits on a lot of hugely important topics.. Monte Carlo.. finding stationary distributions.. creating an internet empire! Seriously top notch. Love seeing the technical details too. Reminds me there is demand for that on TH-cam
@@mastershooter64 plus Im sure if he speaks with his professors they'd be more then happy to go in depth on their subject. People often fail to realize that formal education requires standards and that these are optimized for limited time and relative importance of topics.
@@paulomartins1008 oh yes talking to professors too! like yes i get it there are some bad and unfriendly professors but most professors explicitly encourage you to ask them question and to talk to them, they absolutely love it whenever a student shows genuine interest in something they teach and would love to teach you more about that topic
I’m an incoming freshman at Carnegie Mellon University who is well excited but also somewhat intimidated by the vast field of computer science. I just want to say that this video is beyond amazing. You are doing God’s work. Elegant MANIM visualization, lucid explanations, and the structure of the video all comes together and creates this powerful delivery of clarity. Although your name is Reducible, I don’t want to reduce you down to “The Grant Sanderson of Computer Science.” You’re much more than that. A great explanation is indistinguishable from art and you’re an excellent artist. Your videos inspire me in many ways and fuel my passion and interest in CS. I believe I’m not the only one and there are millions more to be inspired. So please keep it up. We appreciate your work. Thank you.
One of the most heart-warming comments I've received Shawn! Thank you so much! As cheesy as it does sound, I really do try to create something that feels like art to me. It's amazing to hear that others interpret it as such. In some ways, I think of the videos I make as the explanations I wish I had when I was in your position right now, an incoming student that was excited, but also worried about thoughts of whether I would be able to learn and understand the complex ideas in the field. Or the student that had just been completely lost by something in lecture that if given the right perspective, would have clicked. One thing that really helped me get through those worrisome and stressful thoughts was finding joy and beauty in the topics themselves, and the "art" I create hopefully conveys that. Good luck at CMU -- you're at the start of an incredible journey, and no matter where it takes you, it's a time to cherish.
I thought I was ready for this level of math when I clicked on the video, but nope. That went all over my head though. Sounds very interesting, I must watch again someday
19:21 I think the "brute force" method can also be interpreted as the power method for calculating the largest eigenvalue/eigenvector. Since you already mentioned beforehand that the stationary solution is unique for non-periodic irreducible Markov chains, the corresponding matrix would also have only one unique eigenvalue (1) and eigenvector (stationary solution) pair. Overall, great explanation of the algorithm!
Yup, that's indeed a more formal and accurate way to put it, but thinking about it from the perspective of someone who has just started learning Markov chains, I really do feel that it is, in a sense, the first and most simple thought of what you might do to compute the stationary distribution. That thought paired with the fact that it's generally the most computationally practical method to solve for it makes it super satisfying.
@@Reducible Agreed. Monte Carlo simulations also came to mind, though in this case we are guaranteed that just one simulation is required to get the answer.
Awesome explanation! Just a couple of remarks: - Related to the power method (for largest eigenvalue) that some people are commenting: when all entries of P are nonzero it can be proven that the limit P^n where n tends to infinity is a matrix where all rows are exactly equal to the asymptotic distribution vector. This property is a consequence of the Perron-Frobenius theorem applied to "strongly connected" graphs. "Strongly connected" means here that each "website" can always be reached from another in a (finite) number of steps, which I think is related to the aperiodic and irreducible property that you explain (I'm not sure). - Assuming P with nonzero entries, we can prove that the eigenvalue 1 of P^T has multiplicity 1 (both algebraic and geometric). With this, it can be deduced that only one extra equation is needed (sum of probs = 1) to get exactly one solution. I remark this because is not immediately clear that just with the extra equation the solution is unique. Also, this eigenvalue 1 happens to be the largest one, which is related to the fact that P^infinity does converge (again, power method without normalizing).
There actually isn't any computational difference between the "System of Equations" method and the "Eigenvalues/Eigenvectors" method. Given that you already know that the matrix has an eigenvalue of 1, the eigenvector calculation boils down to the exact same system of equations. Eigenvectors are just an interesting way of framing the problem.
I randomly clicked on this out of pure curiosity and was completely stunned to see exactly the same math that I use everyday in matrix population models for modelling wildlife populations! The scalar lambda is considered the population growth rate and >1 the population is growing,
I am so happy that I finally grew enough in my knowledge to watch this video and understand 100% of it! I am so glad! Thakns Reducible and thanks Jesus that I am can learn so much in this ERA! This is now one of my favourite videos!
It is technically correct to call that the brute force method, but it's actually the power method, the simplest iterative eigenvalue/eigenvector finding algorithm. It would have been nice if you stated that the largest eigenvalue of the matrix is 1 which is why it works, and that actually lines up with the physical nature of the process quite well.
@@grekiki At it is a stochastic matrix, each row sums to 1. We can see that if we have the vector v = (1, 1, ..., 1)^T, then the elements of Pv will all be 1, so Pv=1v, and 1 is an eigenvalue with v as it's eigenvector. To show it is the largest eigenvalue possible, suppose there is a larger one, lambda. Because each row sums to 1, each component of Pv is a convex combination of the components of v. If v_k is the largest component of v, then the largest convex combination of components will be v_k by using the coefficients (0,...1,..., 0) where 1 is in the k'th position. This means the largest component of Pv will also be v_k. According to our assumption we had Pv=lambda*v>v component-wise as lambda>1. Therefore, v_k > v_k, which is a contradiction. Considering I have proved this myself before and have final exams around the corner, it's a little worrying I had to get this off stack exchange lol (math.stackexchange.com/questions/40320/proof-that-the-largest-eigenvalue-of-a-stochastic-matrix-is-1)
@@henryginn7490 That's a great summary. One note I'll mention to avoid misunderstanding is that v = (1, 1, ..., 1)^T is a right eigenvector of P (since Pv = v). Whereas for the stationary problem, we need the left eignenvector (pi * P = pi). That's why we can't just use (1, 1, ..., 1)^T as the stationary solution. And I think there's a proof that the left and right eigenvectors share the same set of eigenvalues, but I can't recall it.
@@grekiki Another way to think about it is that every vector can be seen as a weighted combination of the eigenvectors. So when you keep multiplying the probability matrix, the vector will morph towards the eigenvector with the largest eigenvalue, since it's weight will grow fastest and so it will take up more and more of the share of the vector. We want our initial distribution to end at a stationary distribution, which by our definition requires an eigenvalue of 1. So if 1 is not the largest eigenvalue, then over time the vector will shoot off to some other vector that's not the stationary distribution for the problem.
I want you to make more videos, please, especially on graphs and tough topics that students run away from (like Graphs, DP, trie, trees etc). Your one video is actually enough to imprint the logic to do questions and how to think of an approach. Now I can do them myself, this is the power of extraordinary but simple explanation, world-class animation for understanding, and Good voice.
Seriously this is top notch content. As an engineer when I see a big problem I always think how in the world would I ever solve it. But seeing this guys and 3b1b videos I always feel that I should have developed a skill of analysis, observe the properties, solving smaller problems and try to predict generalizations repeat the same process again until you end with a satisfactory solution (Actually that is the process for most education but generally we do not go as far as these guys in understanding some concept). Never in the world would I have thought that I would sit and listen to a class about markov chains for 30 minutes. When I saw the text book there was a big diagram with some matrix multiplications and that's it. But now as I see this beauty unravel before my eyes I feel how better I could have learnt about Maths and CS when I was in college.
Watching these videos with no knowledge of advanced algebra or whatever other math classes is fun because I just get to listen to the guy talk about funny magic with cool drawings to go with it
Absolutely mind blowing. Thank you for your work on explaining things in an easy way. My take from the video: eigenvectors can be seen as the stacionary vectors of a transformation which represents a dynamic system changing over time.
What I thought at 16:11: "Wait, isn't that...?" I never realize why to learn calculating eigenvalues and eigenvectors. It is a great example for it, thx.
Another amazing video! Love how well you explained Markov Chains while still getting into some of the more gritty details- that was beautifully done :)
I used PageRank for social networks in my thesis and found in really interesting how the engineering solution was just "We don't care about the exact solution as long as the power method is deterministic"
If you want to know where the connection to the Eigenvalue decomposition comes from, check out how to compute powers with matrix exponents and why that works. The same connection exists there, related to computing a limit of higher and higher powers of a matrix.
Two easy refinements for the PageRank specific use case of these Markov chains : 1. there are no actual dead ends as the user can hit the back button making all links two-way. (Perhaps back button clicks, instead of counting as a new edge in the graph, could decrease the weight of the edge taken before the backup, or simply undoing the data that that user took the edge and the backup at all? 2. A jump isn't quite random: users don't want to jump to where they already are. So you can eliminate all links from any node to itself from the graph., and force a new node by setting the main diagonal of Random jump matrix R to 0 (R[ j, j ] = 0)
Excellent video and cool idea to present. As a follow-up suggestion, you could explore what happens with the Markov Chain when we have a continuous set of states instead of a discrete one. This ends with the Perron-Frobenius operator, and the Markov Chain is a discrete approximation obtained through the Ulam method. One application example is mapping the flow structure of the ocean's currents.
The assumption in the "simplified real world use case" (!?) that you mention at 2:03 stating that "...these web pages will often reference each other..." does not tally with my experience in the last, say, 20+ years. I would even be initially inclined to believe that, in 2022, it is demonstrably not the case. Has this aspect been the subject of some formal research pointing to that conclusion? Anyone? Thank you so much for uploading the video!
Perfect video. I recently built a web crawler, and I want to use the data to build a search engine. I watched the video through, I don't quite get it all, but I'm just working on creating a list of important information to collect. I'm thinking I'll probably use pagerank first for my page sorting algorithm.
17:15 I'm glad to report that my university (UC Berkeley) intro Linear Algebra class for engineers uses this exact example about the stationary points of transition matrices as one of the first introductions to learning about eigenvalues/eigenvectors. I guess you and that course staff see eye to eye on this example.
Haha, where do you think I went to school? Back when I was in Berkeley, I learned this in EE16A without direct reference to Markov chains. This video has flavors of inspiration from that class and some of the more intense Markov chain theory in EE126.
Fantastic video, thank you so much! I would love to see more videos on search algorithms, I find it endlessly fascinating how all these purely mathematical concepts combine to an algorithm that seems like it understands language and what is relevant to human beings.
I could really use some help with the ergodicity property at 12:40. 1. Is there a practical test for the aperiodic and reducible properties? 2. W.r.t convergent behavior, what alternatives are considered _in principle,_ except for periodic oscillation and convergence (unique or not)? I can think only of chaotic dynamics and divergence to infinity. Since the transition matrix is a linear map in the distribution space, chaos is impossible (it would require both non-linearity and dissipation); since it's both locally and globally non-dilating w.r.t the distribution support, divergence is also impossible. I cannot understand what makes the statement about convergence of the difference equation non-trivial; it seems to be simply the only remaining possibility (uniqueness of the fixpoint _is_ non-obvious tho).
Awesome video! One question: if the solution to periodic/irreducible chains is to use some value alpha to transition to a random state, wouldn't that result in that particular state being seen as ranking higher? Since a user will be "trapped" there for a few steps before breaking out with alpha probability?
Fantastic question! From a super high level perspective, PageRank is fundamentally recursive in nature. When a page is ranked highly, it's because usually, several other highly ranked pages link to it. So in the case of when we have an absorbing state/cycle, if many high ranking pages link to it, the pages should generally have a high rank anyways. So in that case, we are fine. And when the ranks of the web pages pointing to it settle to a lower rank, in general if we think about the user perspective, there won't be many users that actually end up being absorbed in that state, just because the neighboring states have low number of users reaching it. In this case, there might be a bit of artificial increase in density due to the absorbing nature, but as long as the alpha is tuned appropriately, studies have found it doesn't actually end up affecting rankings too much. The nice thing about this too is if you are worried this adversely affecting the ranking, you can crank up the alpha parameter to prevent too much of that absorption from happening. As another side note, I think there was some paper that I read that mentioned that absorbing states/cycles actually end up being a relatively small proportion of the web network topology, so that withstanding, this is unlikely to make a massive impact in the global rankings.
Well, you can also think of Markov chain as water flowing through the pipes. Or light oscillating through space. Or just any sort of particle/finite amount traversing different spatial cells.
Really interesting video! A picture quality note: I see some flashing of grey visual artifacts in the black background on the left side when the diagrams transition up until around minute 3.
Honestly, this was one I couldn't quite figure out. In Final Cut Pro, I did not see these artifacts, but when I uploaded to TH-cam, I noticed them. Pretty strange, TH-cam compression should not result in artifacts like that.
@@Reducible yeah, I wish I could help, but I don't know anything about video authoring software or TH-cam recompression. Thanks for the great content though!
I’m only now realizing why learning eigenvectors in school felt like pulling teeth - the curriculum never mentioned any practical applications. Great Video
Excellent video! I took an information retrieval course last semester and this was kind of a refresher to me, I somehow have forgotten about half the stuff from it ^^ Btw, can I recommend a topic for your next videos? I think posit number system is a good topic, I haven't seen many explanations of it on TH-cam.
I wish mathematicians constructed computationally coherent formal structures/transforms bc what if there is exists a transform that reduces the computation to a couple operations that can beat monte carlo methods
@pyropulse I got that part. Maybe I phrased it weirdly. Like how would a sink-node look (in terms of visitor-percentage) when you add a probabilty to leave that node.
I have almost watched all of your videos, and remarkably all of them are the best. The explanation of the Markov Chain was incredibly awesome. Could you please make a video on Bell-man Equation (Reinforcement learning) from the scratch, No where I have found an awesome video like this to interpret the Bellman Equation.
Thank you! That topic has been on the board for a while! One of the side effects of doing this video is it allows me to approach the general topic of Markov Decision Processes, value iteration, and Q-learning. Lot's of cool stuff there, but also an incredible amount of content for one/several videos. It'll happen at some point, but no guarantees when :)
@Reducible, Great job with the video! you should do a video on the other half of Google's original search algorithm. Page rank is good and all, but isn't that useful if you can't combine it with the text being searched! The original Google paper goes in depth on how this side is implemented. On a related note, I also think a video on Finite State Transducers would be cool. I'd recommend looking at Burntsushi's (Rust's regex library maintainer) excellent blog on FST's.
Absolutely, the index they built was arguably the most important contribution. Without that, scaling this to the level that was necessary wouldn't have been possible. And interesting, I'll definitely put FST's on my radar.
okay this is slightly abstracted because people don't "randomly" pick links to visit. They have intention. Also I can't tell you how many times the number 1 hit wasn't what I was actually looking for. Also your "user" started at state 2 so per the path set by the Markov chain's pathing the Stationary Distribution will always be state 2. If you change the pathing it will change. TL;DR the entire video should be taken with a grain of salt.
14:00 immediately i think: let A = the matrix. let v = the vector. at each step: A = A * A; v = v * A; compare v to the previous v. This exponentially increases the number of matrix steps until it performs so many steps so fast that it MUST converge
re-thinking it: in order to perform A = A * A ONE TIME, you would have to perform as many calculations of a * M for vectors a as the matrix's size, which means simply performing v * M (for example) 1000 times is already 1001 times more efficient than performing M = M * M and then v * M 500 times, which itself is 1001 times more efficient than performing M = M * M again and then v * M 250 times; etc. This method is only good for very small matrices (< 10) that require more than n^2 steps to converge (which they never do, except when n < 4), so this method is excellent for 2x2 matrices, but for n < 5 it's already easy to solve for the eigenvectors in constant time, since explicit formulas exist for all n < 5
Came here just to say that there's some kind of optical illusion going on with the yellow glowy circle in the thumbnail. When I look at it with my peripheral vision, every time I flick my eyes to a new position, the glowyness seems to instantly reduce in size then slowly grow back
Using my ultra instincts I have watched the entirity of this half hour long video and have concluded that it is GOOD.
Lol
I concluded it in the first 15 secs
I concluded that it is magic
@@karanrao116 hello person with the same defalt profile pic as me
Having recently taken Linear Algebra, I got so excited at around 15:55 when I realized he was about to talk about eigenvectors! What a cool connection!
Or even earlier ca. 6:50 regarding stationary states -- admittedly it's been years since I took LA myself, but I remember this point fondly from e.g. 3b1b's videos: a stationary point, or angle or vector or what have you, is exactly what the eigenvector&value tells you. :)
I'd like to learn linear algebra
Just finished my freshman year at UC Berkeley as a CS student, and while watching this video my “Oski senses” were tingling. having found out 2 of my favorite TH-camrs were Cal alumni, I dug around for a bit and found out you too went to UC Berkeley and even taught CS61A.
Keep making great videos and providing intuitive explanations to really complex problems.
Go Bears!
Ha, nice investigation! A lot of the inspiration for the approach to this video was actually from EE126: Probability and Random Processes.
Go bears!!
gob ears
I think it's the first time I've seen a video showing the movement of a Markov chain so dynamically. It really helps to get a lot of intuition. thank you!
Yeah, when I was looking at other videos on the topic, I was rather surprised to see that no one had shown that way of thinking about it. For me, it just felt like an absolute necessity to understand it!
@@Reducible which software do you use to make such wonderful videos?
@@DevKumar-dg2vo I believe he uses manim which is the same animation engine that 3b1b uses for his videos :)
Wow excellent idea and video quality. PageRank hits on a lot of hugely important topics.. Monte Carlo.. finding stationary distributions.. creating an internet empire! Seriously top notch.
Love seeing the technical details too. Reminds me there is demand for that on TH-cam
I did my masters' project on MCMC algorithms and you have beautifully explained everything I learned in 6 months.
As a computer science major in college, this amazing channel goes so much more in depth than my courses could ever hope. Thank you so much! :)
Lol then just get a graduate level book on the topic
@@mastershooter64 plus Im sure if he speaks with his professors they'd be more then happy to go in depth on their subject.
People often fail to realize that formal education requires standards and that these are optimized for limited time and relative importance of topics.
@@paulomartins1008 oh yes talking to professors too! like yes i get it there are some bad and unfriendly professors but most professors explicitly encourage you to ask them question and to talk to them, they absolutely love it whenever a student shows genuine interest in something they teach and would love to teach you more about that topic
I’m an incoming freshman at Carnegie Mellon University who is well excited but also somewhat intimidated by the vast field of computer science. I just want to say that this video is beyond amazing. You are doing God’s work.
Elegant MANIM visualization, lucid explanations, and the structure of the video all comes together and creates this powerful delivery of clarity.
Although your name is Reducible, I don’t want to reduce you down to “The Grant Sanderson of Computer Science.” You’re much more than that. A great explanation is indistinguishable from art and you’re an excellent artist. Your videos inspire me in many ways and fuel my passion and interest in CS. I believe I’m not the only one and there are millions more to be inspired. So please keep it up. We appreciate your work. Thank you.
One of the most heart-warming comments I've received Shawn! Thank you so much! As cheesy as it does sound, I really do try to create something that feels like art to me. It's amazing to hear that others interpret it as such.
In some ways, I think of the videos I make as the explanations I wish I had when I was in your position right now, an incoming student that was excited, but also worried about thoughts of whether I would be able to learn and understand the complex ideas in the field. Or the student that had just been completely lost by something in lecture that if given the right perspective, would have clicked. One thing that really helped me get through those worrisome and stressful thoughts was finding joy and beauty in the topics themselves, and the "art" I create hopefully conveys that.
Good luck at CMU -- you're at the start of an incredible journey, and no matter where it takes you, it's a time to cherish.
@@Reducible You might want to make a video about the "string art algorithm".
I remeber the PageRank being shown in one of my Linear Algebra classes at my University like ~16 years ago. Thanks for the flashback.
I thought I was ready for this level of math when I clicked on the video, but nope. That went all over my head though. Sounds very interesting, I must watch again someday
19:21 I think the "brute force" method can also be interpreted as the power method for calculating the largest eigenvalue/eigenvector. Since you already mentioned beforehand that the stationary solution is unique for non-periodic irreducible Markov chains, the corresponding matrix would also have only one unique eigenvalue (1) and eigenvector (stationary solution) pair.
Overall, great explanation of the algorithm!
Yup, that's indeed a more formal and accurate way to put it, but thinking about it from the perspective of someone who has just started learning Markov chains, I really do feel that it is, in a sense, the first and most simple thought of what you might do to compute the stationary distribution. That thought paired with the fact that it's generally the most computationally practical method to solve for it makes it super satisfying.
@@Reducible Agreed. Monte Carlo simulations also came to mind, though in this case we are guaranteed that just one simulation is required to get the answer.
Clearer than MIT lecture on Markov chain.
Awesome explanation!
Just a couple of remarks:
- Related to the power method (for largest eigenvalue) that some people are commenting: when all entries of P are nonzero it can be proven that the limit P^n where n tends to infinity is a matrix where all rows are exactly equal to the asymptotic distribution vector. This property is a consequence of the Perron-Frobenius theorem applied to "strongly connected" graphs.
"Strongly connected" means here that each "website" can always be reached from another in a (finite) number of steps, which I think is related to the aperiodic and irreducible property that you explain (I'm not sure).
- Assuming P with nonzero entries, we can prove that the eigenvalue 1 of P^T has multiplicity 1 (both algebraic and geometric). With this, it can be deduced that only one extra equation is needed (sum of probs = 1) to get exactly one solution. I remark this because is not immediately clear that just with the extra equation the solution is unique.
Also, this eigenvalue 1 happens to be the largest one, which is related to the fact that P^infinity does converge (again, power method without normalizing).
I studied Linear Algebra last semester and it was wonderful to see how what I learned is actually applied on such a large scale!
This is EASILY one of the best videos I've ever watched on TH-cam
There actually isn't any computational difference between the "System of Equations" method and the "Eigenvalues/Eigenvectors" method.
Given that you already know that the matrix has an eigenvalue of 1, the eigenvector calculation boils down to the exact same system of equations. Eigenvectors are just an interesting way of framing the problem.
I randomly clicked on this out of pure curiosity and was completely stunned to see exactly the same math that I use everyday in matrix population models for modelling wildlife populations! The scalar lambda is considered the population growth rate and >1 the population is growing,
0:48 was a cooooool intro!
I am so happy that I finally grew enough in my knowledge to watch this video and understand 100% of it! I am so glad! Thakns Reducible and thanks Jesus that I am can learn so much in this ERA! This is now one of my favourite videos!
Thank you for making Markov Chains less scary to learn about and making all of us a little bit smarter.
It is technically correct to call that the brute force method, but it's actually the power method, the simplest iterative eigenvalue/eigenvector finding algorithm. It would have been nice if you stated that the largest eigenvalue of the matrix is 1 which is why it works, and that actually lines up with the physical nature of the process quite well.
Wait why is the largest eigen value 1?
@@grekiki At it is a stochastic matrix, each row sums to 1. We can see that if we have the vector v = (1, 1, ..., 1)^T, then the elements of Pv will all be 1, so Pv=1v, and 1 is an eigenvalue with v as it's eigenvector.
To show it is the largest eigenvalue possible, suppose there is a larger one, lambda. Because each row sums to 1, each component of Pv is a convex combination of the components of v. If v_k is the largest component of v, then the largest convex combination of components will be v_k by using the coefficients (0,...1,..., 0) where 1 is in the k'th position. This means the largest component of Pv will also be v_k. According to our assumption we had Pv=lambda*v>v component-wise as lambda>1. Therefore, v_k > v_k, which is a contradiction.
Considering I have proved this myself before and have final exams around the corner, it's a little worrying I had to get this off stack exchange lol (math.stackexchange.com/questions/40320/proof-that-the-largest-eigenvalue-of-a-stochastic-matrix-is-1)
@@henryginn7490 Thanks for summarizing still not extremely comfortable with linear algebra here either
@@henryginn7490 That's a great summary. One note I'll mention to avoid misunderstanding is that v = (1, 1, ..., 1)^T is a right eigenvector of P (since Pv = v). Whereas for the stationary problem, we need the left eignenvector (pi * P = pi). That's why we can't just use (1, 1, ..., 1)^T as the stationary solution. And I think there's a proof that the left and right eigenvectors share the same set of eigenvalues, but I can't recall it.
@@grekiki Another way to think about it is that every vector can be seen as a weighted combination of the eigenvectors. So when you keep multiplying the probability matrix, the vector will morph towards the eigenvector with the largest eigenvalue, since it's weight will grow fastest and so it will take up more and more of the share of the vector.
We want our initial distribution to end at a stationary distribution, which by our definition requires an eigenvalue of 1. So if 1 is not the largest eigenvalue, then over time the vector will shoot off to some other vector that's not the stationary distribution for the problem.
16:36 This connection here.
This is still the "click" moment that I treasure the most during my times at uni.
I want you to make more videos, please, especially on graphs and tough topics that students run away from (like Graphs, DP, trie, trees etc). Your one video is actually enough to imprint the logic to do questions and how to think of an approach. Now I can do them myself, this is the power of extraordinary but simple explanation, world-class animation for understanding, and Good voice.
Seriously this is top notch content. As an engineer when I see a big problem I always think how in the world would I ever solve it. But seeing this guys and 3b1b videos I always feel that I should have developed a skill of analysis, observe the properties, solving smaller problems and try to predict generalizations repeat the same process again until you end with a satisfactory solution (Actually that is the process for most education but generally we do not go as far as these guys in understanding some concept). Never in the world would I have thought that I would sit and listen to a class about markov chains for 30 minutes. When I saw the text book there was a big diagram with some matrix multiplications and that's it. But now as I see this beauty unravel before my eyes I feel how better I could have learnt about Maths and CS when I was in college.
You have nicely concluded Markov chains, I wasn't expecting this much intuition from youTube.
Just in time for my exam tomorrow including Markov chains thanks for the great initiative explaination!
Outstanding video dude. I've been self-studying linear algebra and its very cool to see the concepts applied.
Just discovered you today and binged lots of your work. Super excited to see your library grow! Here's to many more videos (:
I swear you could teach TAX LAW and make it interesting. You are a born teacher. Thanks for another amazing video!
The whole world holds on such individuals like you!
Watching these videos with no knowledge of advanced algebra or whatever other math classes is fun because I just get to listen to the guy talk about funny magic with cool drawings to go with it
Absolutely mind blowing. Thank you for your work on explaining things in an easy way. My take from the video: eigenvectors can be seen as the stacionary vectors of a transformation which represents a dynamic system changing over time.
What I thought at 16:11: "Wait, isn't that...?"
I never realize why to learn calculating eigenvalues and eigenvectors. It is a great example for it, thx.
Another amazing video! Love how well you explained Markov Chains while still getting into some of the more gritty details- that was beautifully done :)
I used PageRank for social networks in my thesis and found in really interesting how the engineering solution was just "We don't care about the exact solution as long as the power method is deterministic"
I love this channel so much! Happy to say I've been here since the dynamic array video :)
I love how the first couple of sentences would just be absolute nonsense to someone 100 years ago.
This was an assignment question for my intro linear algebra class. This video takes it a lot deeper
glad to see you're still alive. As per usual excellent work.
Wow! finally someone explaining those boaring things off my syllabus in a way they should be.👍Hope to see poisson process and queing chains next.
You don‘t only explain „what“ is the mathematic, but also explain „why“ is the mathematic
What the heck. I was just reading Sergey's 1998 paper on PageRank (literally hours ago)
If you want to know where the connection to the Eigenvalue decomposition comes from, check out how to compute powers with matrix exponents and why that works. The same connection exists there, related to computing a limit of higher and higher powers of a matrix.
Read a paper a month back and chad Reducible walks in to better describe it
Two easy refinements for the PageRank specific use case of these Markov chains :
1. there are no actual dead ends as the user can hit the back button making all links two-way. (Perhaps back button clicks, instead of counting as a new edge in the graph, could decrease the weight of the edge taken before the backup, or simply undoing the data that that user took the edge and the backup at all?
2. A jump isn't quite random: users don't want to jump to where they already are. So you can eliminate all links from any node to itself from the graph., and force a new node by setting the main diagonal of Random jump matrix R to 0 (R[ j, j ] = 0)
You keep uploading videos exactly when we have the topics at our uni
Excellent video and cool idea to present. As a follow-up suggestion, you could explore what happens with the Markov Chain when we have a continuous set of states instead of a discrete one. This ends with the Perron-Frobenius operator, and the Markov Chain is a discrete approximation obtained through the Ulam method. One application example is mapping the flow structure of the ocean's currents.
Ooh, that looks super interesting -- I'll definitely have to read up on that, but sounds like a great topic!
Again, my mind was blown
Really well explained and now I want to know more, time to dive in the rabbit hole
The assumption in the "simplified real world use case" (!?) that you mention at 2:03 stating that "...these web pages will often reference each other..." does not tally with my experience in the last, say, 20+ years. I would even be initially inclined to believe that, in 2022, it is demonstrably not the case. Has this aspect been the subject of some formal research pointing to that conclusion? Anyone? Thank you so much for uploading the video!
Perfect video. I recently built a web crawler, and I want to use the data to build a search engine. I watched the video through, I don't quite get it all, but I'm just working on creating a list of important information to collect. I'm thinking I'll probably use pagerank first for my page sorting algorithm.
yo that new intro is sick
Really an excellent video with incredible visuals.
markov chains are such a rich topic for explain videos
I'd love to see more of them around :(
Really great videos loved them wondering if you could increase the frequency of the uploads.
We usually define the so-called markov chain a directed graph, because it is better assumed as a graph for further computations.
Also love the new intro
17:15 I'm glad to report that my university (UC Berkeley) intro Linear Algebra class for engineers uses this exact example about the stationary points of transition matrices as one of the first introductions to learning about eigenvalues/eigenvectors. I guess you and that course staff see eye to eye on this example.
Haha, where do you think I went to school?
Back when I was in Berkeley, I learned this in EE16A without direct reference to Markov chains. This video has flavors of inspiration from that class and some of the more intense Markov chain theory in EE126.
@@Reducible this whole video gave me flashbacks to EE16A homeworks lol
Fantastic video, thank you so much! I would love to see more videos on search algorithms, I find it endlessly fascinating how all these purely mathematical concepts combine to an algorithm that seems like it understands language and what is relevant to human beings.
Your videos always blow me away. What an amazing explanation.
Could've released this video a couple months earlier and saved me a ton of headache brother
I could really use some help with the ergodicity property at 12:40. 1. Is there a practical test for the aperiodic and reducible properties? 2. W.r.t convergent behavior, what alternatives are considered _in principle,_ except for periodic oscillation and convergence (unique or not)? I can think only of chaotic dynamics and divergence to infinity. Since the transition matrix is a linear map in the distribution space, chaos is impossible (it would require both non-linearity and dissipation); since it's both locally and globally non-dilating w.r.t the distribution support, divergence is also impossible. I cannot understand what makes the statement about convergence of the difference equation non-trivial; it seems to be simply the only remaining possibility (uniqueness of the fixpoint _is_ non-obvious tho).
Maybe that way of thinking wasn't that obvious back then, graph theory and markov processes were born in the last century if i'm correct anyway
8:42 "Roll Credits." Eyy!
Awesome video! One question: if the solution to periodic/irreducible chains is to use some value alpha to transition to a random state, wouldn't that result in that particular state being seen as ranking higher? Since a user will be "trapped" there for a few steps before breaking out with alpha probability?
Fantastic question! From a super high level perspective, PageRank is fundamentally recursive in nature. When a page is ranked highly, it's because usually, several other highly ranked pages link to it. So in the case of when we have an absorbing state/cycle, if many high ranking pages link to it, the pages should generally have a high rank anyways. So in that case, we are fine.
And when the ranks of the web pages pointing to it settle to a lower rank, in general if we think about the user perspective, there won't be many users that actually end up being absorbed in that state, just because the neighboring states have low number of users reaching it. In this case, there might be a bit of artificial increase in density due to the absorbing nature, but as long as the alpha is tuned appropriately, studies have found it doesn't actually end up affecting rankings too much.
The nice thing about this too is if you are worried this adversely affecting the ranking, you can crank up the alpha parameter to prevent too much of that absorption from happening. As another side note, I think there was some paper that I read that mentioned that absorbing states/cycles actually end up being a relatively small proportion of the web network topology, so that withstanding, this is unlikely to make a massive impact in the global rankings.
Just so you know, I doooooo have notifications on sir.
Man im doing my thesis. This is an excellent explaination
“Long term behaviour of systems is tied to eigenvalues/eigenvectors“ **war flashbacks to my control systems class in uni**
Well, you can also think of Markov chain as water flowing through the pipes. Or light oscillating through space. Or just any sort of particle/finite amount traversing different spatial cells.
22:00 this kind of reminds me of adding a prior when predicting sports team's true strength
Really interesting video! A picture quality note: I see some flashing of grey visual artifacts in the black background on the left side when the diagrams transition up until around minute 3.
Honestly, this was one I couldn't quite figure out. In Final Cut Pro, I did not see these artifacts, but when I uploaded to TH-cam, I noticed them. Pretty strange, TH-cam compression should not result in artifacts like that.
@@Reducible yeah, I wish I could help, but I don't know anything about video authoring software or TH-cam recompression. Thanks for the great content though!
Most Linear Algebra doesn't mention Probability at all. I think it would be best to have classes showing connections between different math topics
Great video and explaination!!
I love the Video, I love the new intro! keep up the amazing work!
An Eigenvalue decomposition of the transition matrix will tell you everything: reducibility, periodicity and all stationary distributions.
kinda insane that I get this video in my recommended after missing my class lecture about pagerank
I’m only now realizing why learning eigenvectors in school felt like pulling teeth - the curriculum never mentioned any practical applications. Great Video
Ah yes, another video from Reducible, another piece of quality content
Excellent video! I took an information retrieval course last semester and this was kind of a refresher to me, I somehow have forgotten about half the stuff from it ^^
Btw, can I recommend a topic for your next videos? I think posit number system is a good topic, I haven't seen many explanations of it on TH-cam.
I was not expecting my mind to be blow today
I wish mathematicians constructed computationally coherent formal structures/transforms bc what if there is exists a transform that reduces the computation to a couple operations that can beat monte carlo methods
Would have loved a visualization of what happens to the stationary distributions after adding the alpha term/step
@pyropulse I got that part. Maybe I phrased it weirdly. Like how would a sink-node look (in terms of visitor-percentage) when you add a probabilty to leave that node.
I gotta say man, procedurally generated videos always look cool when it's about CS, AI, or math.
So amazing. Thank you for this!
I have almost watched all of your videos, and remarkably all of them are the best. The explanation of the Markov Chain was incredibly awesome. Could you please make a video on Bell-man Equation (Reinforcement learning) from the scratch, No where I have found an awesome video like this to interpret the Bellman Equation.
Thank you! That topic has been on the board for a while! One of the side effects of doing this video is it allows me to approach the general topic of Markov Decision Processes, value iteration, and Q-learning. Lot's of cool stuff there, but also an incredible amount of content for one/several videos. It'll happen at some point, but no guarantees when :)
@Reducible, Great job with the video! you should do a video on the other half of Google's original search algorithm. Page rank is good and all, but isn't that useful if you can't combine it with the text being searched! The original Google paper goes in depth on how this side is implemented. On a related note, I also think a video on Finite State Transducers would be cool. I'd recommend looking at Burntsushi's (Rust's regex library maintainer) excellent blog on FST's.
Absolutely, the index they built was arguably the most important contribution. Without that, scaling this to the level that was necessary wouldn't have been possible. And interesting, I'll definitely put FST's on my radar.
3b1b levels of good... maybe better
Amazing Video
I love how eigenvectors pop up...
Great content and work. Thank you.
okay this is slightly abstracted because people don't "randomly" pick links to visit. They have intention. Also I can't tell you how many times the number 1 hit wasn't what I was actually looking for.
Also your "user" started at state 2 so per the path set by the Markov chain's pathing the Stationary Distribution will always be state 2. If you change the pathing it will change.
TL;DR the entire video should be taken with a grain of salt.
14:00 immediately i think: let A = the matrix. let v = the vector. at each step: A = A * A; v = v * A; compare v to the previous v. This exponentially increases the number of matrix steps until it performs so many steps so fast that it MUST converge
re-thinking it: in order to perform A = A * A ONE TIME, you would have to perform as many calculations of a * M for vectors a as the matrix's size, which means simply performing v * M (for example) 1000 times is already 1001 times more efficient than performing M = M * M and then v * M 500 times, which itself is 1001 times more efficient than performing M = M * M again and then v * M 250 times; etc. This method is only good for very small matrices (< 10) that require more than n^2 steps to converge (which they never do, except when n < 4), so this method is excellent for 2x2 matrices, but for n < 5 it's already easy to solve for the eigenvectors in constant time, since explicit formulas exist for all n < 5
Legendary. Thank you!
Thanks for this video
I appreciate the effort you put in but I got about 5-10 minutes in and was completely lost
Is there any website or links to create the animation in the video? I'm doing an essay on PageRank and I can't find a good markov chains generator
I believe this is actually one of the Google interview questions
Came here just to say that there's some kind of optical illusion going on with the yellow glowy circle in the thumbnail. When I look at it with my peripheral vision, every time I flick my eyes to a new position, the glowyness seems to instantly reduce in size then slowly grow back
Your videos are so good
Excellent video!
I have a basic question. Whats Pie of P? :-|
Excellent video