PageRank: A Trillion Dollar Algorithm
Vložit
- čas přidán 12. 06. 2024
- Visit brilliant.org/Reducible/ to get started learning STEM for free, and the first 200 people will get 20% off their annual premium subscription.
Chapters:
0:00 Intro
1:00 Defining Markov Chains
2:00 Introducing the Problem
4:08 Modeling Markov Chains
6:26 Stationary Distributions
7:20 Uniqueness of Stationary Distributions (Irreducibility)
9:11 Convergence of Stationary Distributions (Periodicity)
12:15 Ergodic Theorem
13:32 Computing Stationary Distributions
17:43 Practically Computing Stationary Distributions
19:29 PageRank Algorithm
23:12 Sponsored Message (Brilliant)
24:25 Recap/Conclusion
In the late 1990's two PhD Students Larry Page and Sergey Brin came up with an algorithm that revolutionized search called PageRank. In this video we discuss some of the beautiful mathematical ideas and complexities of PageRank. Fundamentally, PageRank is all about calculating stationary distributions of Markov chains. We talk about some of the challenges of computing these distributions as well as the adjustments that PageRank made to these ideas to make it dominate the search landscape.
Animations created jointly by Nipun Ramakrishnan and Jesús Rascón.
References:
Original PageRank Paper: ilpubs.stanford.edu:8090/422/1...
Proof of the Ergodic Theorem: math.uchicago.edu/~may/VIGRE/...
General inspiration/further reading for Markov chains: Ch 1 of Probability in Electrical Engineering and Computer Science by Jean Walrand
Good discussion on stationary distributions of Markov chains: brilliant.org/wiki/stationary...
Markov chains and PageRank: www2.math.upenn.edu/~kazdan/3...
This video wouldn't be possible without the open source library manim created by 3blue1brown and maintained by Manim Community.
The Manim Community Developers. (2022). Manim - Mathematical Animation Framework (Version v0.11.0) [Computer software]. www.manim.community/
Here is link to the repository that contains the code used to generate the animations in this video: github.com/nipunramk/Reducible
Music in this video comes from Jesús Rascón and Aaskash Gandhi
Socials:
Patreon: / reducible
Twitter: / reducible20
Big thanks to the community of Patreons that support this channel. Special thanks to the following Patreons:
Andreas
Adam Dřínek
Burt Humburg
Eugene Tulushev
Matt Q
Winston Durand
Andjela Arsic
Mutual Information
Richard Wells
Sebastian Gamboa
Zac Landis
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
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 CZcams
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 CZcamsrs 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 :)
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.
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.
Couldn't you calculate the eigenvector via power method? In that case it would be equivalent to the first "brute force" method.
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 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
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 did my masters' project on MCMC algorithms and you have beautifully explained everything I learned in 6 months.
Just discovered you today and binged lots of your work. Super excited to see your library grow! Here's to many more 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.
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.
Another amazing video! Love how well you explained Markov Chains while still getting into some of the more gritty details- that was beautifully done :)
Outstanding video dude. I've been self-studying linear algebra and its very cool to see the concepts applied.
I studied Linear Algebra last semester and it was wonderful to see how what I learned is actually applied on such a large scale!
I love this channel so much! Happy to say I've been here since the dynamic array video :)
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!
16:36 This connection here.
This is still the "click" moment that I treasure the most during my times at uni.
Clearer than MIT lecture on Markov chain.
This is EASILY one of the best videos I've ever watched on CZcams
You have nicely concluded Markov chains, I wasn't expecting this much intuition from youTube.
Your videos always blow me away. What an amazing explanation.
Really an excellent video with incredible visuals.
Just in time for my exam tomorrow including Markov chains thanks for the great initiative explaination!
glad to see you're still alive. As per usual excellent work.
The whole world holds on such individuals like you!
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,
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.
I love how the first couple of sentences would just be absolute nonsense to someone 100 years ago.
Thank you for making Markov Chains less scary to learn about and making all of us a little bit smarter.
Again, my mind was blown
Really well explained and now I want to know more, time to dive in the rabbit hole
This was an assignment question for my intro linear algebra class. This video takes it a lot deeper
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.
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.
Great video and explaination!!
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.
I love the Video, I love the new intro! keep up the amazing work!
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
yo that new intro is sick
Really great videos loved them wondering if you could increase the frequency of the uploads.
Also love the new intro
I swear you could teach TAX LAW and make it interesting. You are a born teacher. Thanks for another amazing video!
So amazing. Thank you for this!
Excellent video!
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.
Legendary. Thank you!
Great content and work. Thank you.
Read a paper a month back and chad Reducible walks in to better describe it
Man im doing my thesis. This is an excellent explaination
Your videos are so good
Thanks for this video
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!
Excellent video
You keep uploading videos exactly when we have the topics at our uni
markov chains are such a rich topic for explain videos
I'd love to see more of them around :(
Just so you know, I doooooo have notifications on sir.
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.
Great 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.
Could've released this video a couple months earlier and saved me a ton of headache brother
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.
8:42 "Roll Credits." Eyy!
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"
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 CZcams.
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!
Nice. Thanks.
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.
Brilliant!
22:00 this kind of reminds me of adding a prior when predicting sports team's true strength
Thanks!
做的很棒，我理解了
Ah yes, another video from Reducible, another piece of quality content
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.
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)
3b1b levels of good... maybe better
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 :)
I was not expecting my mind to be blow today
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
Could you make a video on Markov Decision Processes?
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
“Long term behaviour of systems is tied to eigenvalues/eigenvectors“ **war flashbacks to my control systems class in uni**
@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.
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 CZcams, I noticed them. Pretty strange, CZcams 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 CZcams recompression. Thanks for the great content though!
Here before this goes viral lol
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
Reducible, do make a video on reducibility of polynomials and it's applications
nice video
what are you using for animation
Hi @Reducible, thanks for the video, I'm already 3 minutes in... I want to share a feedback on sound processing. Looks like the volume of the background music is reduced automatically when the voice-over track activated (it's called "ducking"). The music loudness sways are excessive, and when the narrator pauses, music blows through perceivably as louder as the voice was, only to be subdued in half a second, time and time again. I noticed that even my muscles are involuntary tightening up as soon as the narration pauses, as if I'm expecting a blow from the next music blast. If you guys aren't mixing manually, maybe you could consider increasing the timeout in the effect processor, and also match background music loudness ceiling to ~6dB below voice, so it really stays in the background?
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.
kinda insane that I get this video in my recommended after missing my class lecture about pagerank
You don‘t only explain „what“ is the mathematic, but also explain „why“ is the mathematic
We usually define the so-called markov chain a directed graph, because it is better assumed as a graph for further computations.
I’m only now realizing why learning eigenvectors in school felt like pulling teeth - the curriculum never mentioned any practical applications. Great Video
I love how eigenvectors pop up...
I gotta say man, procedurally generated videos always look cool when it's about CS, AI, or math.