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. :)
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 RU-vid
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!
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 RU-vidrs 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!
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.
@@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
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.
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 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,
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.
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.
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.
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 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!
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
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.
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.
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.
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"
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.
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.
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!
I’m only now realizing why learning eigenvectors in school felt like pulling teeth - the curriculum never mentioned any practical applications. Great Video
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.
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)
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 RU-vid, I noticed them. Pretty strange, RU-vid 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 RU-vid recompression. Thanks for the great content though!
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).
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 :)
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.
@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.
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
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 RU-vid.
@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.
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
