Tayzwi
Should be reading more and writing less, but well...Thursday, November 30, 2006
Eigen
The inimitable quip-fuckin'-master forced a comment which is worth expanding a little more.
Ever since I found that the PageRank vector of the web-graph is the dominant eigenvector of its matrix representation, I have been meaning to get to the bottom of this eigenvector-eigenvalue concept. I am still snorkeling; long time to scuba dive.
Most of us studied concepts like simultaneous equations in our high school algebra classes, but never really wondered about them deeply, or even more so, felt that they were difficult. Problems like - 3 oranges and 4 apples cost 17 rupees; 2 oranges and 3 apples cost 12 rupees; how much does each apple cost? - never seemed that difficult. We knew that the equations that represented these statements were 'fluid,' and need not apply to just these statements, and an overall tool was being mastered.
Somehow, the same never happened to tools like primal-dual, or eigenvalues-eigenvectors, or other tools from linear algebra, statistics, calculus, etc. Somewhere, the learning process got fucked because of an emphasis on just the concept, and a palpable lack of intuitive visualization. When people talk about a matrix, I never think in terms of transformations. If I did, I could see that some transformations would leave some 'victims' unchanged. And these victims were the eigenvectors of that transformation. Maybe they could change in terms of scale, but not in terms of what they fundamentally are. Here is an example from the Wikipedia entry on Eigenvalue:
As the Earth rotates, every arrow pointing outward from the center of the Earth also rotates, except those arrows that lie on the axis of rotation. Consider the transformation of the Earth after one hour of rotation: An arrow from the center of the Earth to the Geographic South Pole would be an eigenvector of this transformation, but an arrow from the center of the Earth to anywhere on the equator would not be an eigenvector. Since the arrow pointing at the pole is not stretched by the rotation of the Earth, its eigenvalue is 1.
So, was Neo an Eigenvector of The Matrix? I wonder...
As for what it means when they say that PageRank is the dominant eigenvector of the web-graph, we have to visualize the web-graph's matrix representation as a transformation. The matrix representation has all web-pages in rows and columns, and if a web-page in row i has a hyperlink to a web-page in column j, the [i, j] entry is 1, else 0. What does it mean to say that this matrix is a transformation? And what does it mean to say that it can act on 'victims' to change them? And if the 'victim' happens to be a vector which has the pages' pagerank values, the transformation doesn't affect it. What does that say about PageRank, and how is that related to our intuitive perception of pagerank as the importance of each page on a global scale?
We will get to primal-dual some other time. My head hurts. It hurts.
ps: And these are all just tools; albeit mental in nature. If we don't master them, well, it's ok I guess. We can always go back to intellectual stone age, or whatever was there before that. I mean, I always fancied myself as a Cro-Magnon.
Ever since I found that the PageRank vector of the web-graph is the dominant eigenvector of its matrix representation, I have been meaning to get to the bottom of this eigenvector-eigenvalue concept. I am still snorkeling; long time to scuba dive.
Most of us studied concepts like simultaneous equations in our high school algebra classes, but never really wondered about them deeply, or even more so, felt that they were difficult. Problems like - 3 oranges and 4 apples cost 17 rupees; 2 oranges and 3 apples cost 12 rupees; how much does each apple cost? - never seemed that difficult. We knew that the equations that represented these statements were 'fluid,' and need not apply to just these statements, and an overall tool was being mastered.
Somehow, the same never happened to tools like primal-dual, or eigenvalues-eigenvectors, or other tools from linear algebra, statistics, calculus, etc. Somewhere, the learning process got fucked because of an emphasis on just the concept, and a palpable lack of intuitive visualization. When people talk about a matrix, I never think in terms of transformations. If I did, I could see that some transformations would leave some 'victims' unchanged. And these victims were the eigenvectors of that transformation. Maybe they could change in terms of scale, but not in terms of what they fundamentally are. Here is an example from the Wikipedia entry on Eigenvalue:
As the Earth rotates, every arrow pointing outward from the center of the Earth also rotates, except those arrows that lie on the axis of rotation. Consider the transformation of the Earth after one hour of rotation: An arrow from the center of the Earth to the Geographic South Pole would be an eigenvector of this transformation, but an arrow from the center of the Earth to anywhere on the equator would not be an eigenvector. Since the arrow pointing at the pole is not stretched by the rotation of the Earth, its eigenvalue is 1.
So, was Neo an Eigenvector of The Matrix? I wonder...
As for what it means when they say that PageRank is the dominant eigenvector of the web-graph, we have to visualize the web-graph's matrix representation as a transformation. The matrix representation has all web-pages in rows and columns, and if a web-page in row i has a hyperlink to a web-page in column j, the [i, j] entry is 1, else 0. What does it mean to say that this matrix is a transformation? And what does it mean to say that it can act on 'victims' to change them? And if the 'victim' happens to be a vector which has the pages' pagerank values, the transformation doesn't affect it. What does that say about PageRank, and how is that related to our intuitive perception of pagerank as the importance of each page on a global scale?
We will get to primal-dual some other time. My head hurts. It hurts.
ps: And these are all just tools; albeit mental in nature. If we don't master them, well, it's ok I guess. We can always go back to intellectual stone age, or whatever was there before that. I mean, I always fancied myself as a Cro-Magnon.
Labels: computer science
posted by Tejaswi # 10:27 AM 
Comments:
<< Home
Long have I wondered whether mathematics has any real world meaning. I'm convinced it has solved too many technical problems and the solutions to these problems have made human life better. But I'm not sure if a matrix means something. We might use matrices in searching, ranking, image processing et al. But do those transformations have a real meaning? For instance, rotation of an image is a matrix transformation involving the pixels of the image. But is the image really rotated after we transform it? Or is it just the illusion of our eyes? Is digital music really music or is it just a sequence of meaningless bits and bytes arranged so as to make us feel like it is music? Does inverse square law for gravitational and electromagnetic forces tell us something or is the mathematical operation of squaring rigged to make forces obey the inverse square law?
I, as a theist believe that the creation (including inanimate matter) was divinely inspired. But I'm not sure what the content of the inspiration was. I'm not sure whether God custom made each of us or we are the result of our previous karma or God just wanted the whole creation random. I don't see a conflict between divinely inspired creation and Darwin's theory of evolution.
As far as astractness of concepts is concerned, you can make anything abstract. The simultaneous equation involving oranges and apples can be made complicated enough by throwing in exchange rates, shelf life, supply, demand, principle of diminishing marginal utility and so on. Your readers would hate me for this. But please redirect the hate toward me. Lemme illustrate the principle of diminishing marginal utility. You buy 4 oranges, presumably for consumption. If you are eating them all today, is the last orange you eat gonna make you as satisfied as your first? Probably not. Then why would you pay the same price to both of them? In your mind you will have paid a higher price for the first and a lower prices for the last. The simultaneous equation doesn't capture this. What it gives is the average price per orange. Evidently, half the oranges are cheaper than this and half are pricier.
Was Neo the 'Eigen Vector' of 'the matrix'? I can bet Keanu Reeves didn't know what it meant. So he probably wasn't. Like "I think therefore I am", "I can't think. Therefore I'm not". What was invariant about Neo in the Matrix -dressing? character? mission? intelligence? physical abilities? soul? Whether Neo was the Eigen Vector depends on the kind of invariance that's relevant. If mission was what made him an Eigen Vector, the James Bond is an Eigen Vector too.
Perhaps Eigen Vectors don't have a meaning in the human society. Chances are that invariance doesn't exist. Even if it does, since we, the observers, keep changing, the invariance goes unnoticed. The axis of Earth's rotation could be the Eigen Vector if we assume that the earth is rotating while everything else in the universe is stationary? It will cease to be one when we look at the composite motion in the entire universe.
Aside from all this, I have this question. Why gravitational or electrostatic force of attraction should make objects revolve around one another? Why can't they move straight towards one another and collide/merge? You might say the centripetal and the centrifugal forces should cancel each other. But who initiated the centrifugal force? (The tendency of the earth to escape the influence of the sun)
I guess these were the ways God wanted things.
Satyam Shivam Sundaram.
I, as a theist believe that the creation (including inanimate matter) was divinely inspired. But I'm not sure what the content of the inspiration was. I'm not sure whether God custom made each of us or we are the result of our previous karma or God just wanted the whole creation random. I don't see a conflict between divinely inspired creation and Darwin's theory of evolution.
As far as astractness of concepts is concerned, you can make anything abstract. The simultaneous equation involving oranges and apples can be made complicated enough by throwing in exchange rates, shelf life, supply, demand, principle of diminishing marginal utility and so on. Your readers would hate me for this. But please redirect the hate toward me. Lemme illustrate the principle of diminishing marginal utility. You buy 4 oranges, presumably for consumption. If you are eating them all today, is the last orange you eat gonna make you as satisfied as your first? Probably not. Then why would you pay the same price to both of them? In your mind you will have paid a higher price for the first and a lower prices for the last. The simultaneous equation doesn't capture this. What it gives is the average price per orange. Evidently, half the oranges are cheaper than this and half are pricier.
Was Neo the 'Eigen Vector' of 'the matrix'? I can bet Keanu Reeves didn't know what it meant. So he probably wasn't. Like "I think therefore I am", "I can't think. Therefore I'm not". What was invariant about Neo in the Matrix -dressing? character? mission? intelligence? physical abilities? soul? Whether Neo was the Eigen Vector depends on the kind of invariance that's relevant. If mission was what made him an Eigen Vector, the James Bond is an Eigen Vector too.
Perhaps Eigen Vectors don't have a meaning in the human society. Chances are that invariance doesn't exist. Even if it does, since we, the observers, keep changing, the invariance goes unnoticed. The axis of Earth's rotation could be the Eigen Vector if we assume that the earth is rotating while everything else in the universe is stationary? It will cease to be one when we look at the composite motion in the entire universe.
Aside from all this, I have this question. Why gravitational or electrostatic force of attraction should make objects revolve around one another? Why can't they move straight towards one another and collide/merge? You might say the centripetal and the centrifugal forces should cancel each other. But who initiated the centrifugal force? (The tendency of the earth to escape the influence of the sun)
I guess these were the ways God wanted things.
Satyam Shivam Sundaram.
Can I confess that I liked Samba's comment more than the post ?? And if the blog-writer hates me for it, he can redirect that hate towards Samba as well :D
In other thoughts, saying that the axis of rotation is not an eigen vector when thinking from the point of view of a non-stationary universe is like saying that we changed the matrix, and shockingly, the eigen vector is not the same !
In yet further thoughts, the inability to visualize in n dimensions hurts.
In other thoughts, saying that the axis of rotation is not an eigen vector when thinking from the point of view of a non-stationary universe is like saying that we changed the matrix, and shockingly, the eigen vector is not the same !
In yet further thoughts, the inability to visualize in n dimensions hurts.
I remember the exuberance that I got when I first understood the physical meaning of eigenvectors/values. Unfortunately, I have long forgotten the interpretation, and all that remains is the exuberance.
I personally find the primal-dual framework easier to fathom than the mysteriously magical eigensystem. To me, the Primal is like the rogue son of the family and the dual is the well-behaved twin, a mama's boy (always concave). I wish I had studied it more closely when I had the time.
What does that say about PageRank, and how is that related to our intuitive perception of pagerank as the importance of each page on a global scale?
There are possible answers to this question, though not at the level of abstraction that you desire. This was a question that I too had an year back.
I personally find the primal-dual framework easier to fathom than the mysteriously magical eigensystem. To me, the Primal is like the rogue son of the family and the dual is the well-behaved twin, a mama's boy (always concave). I wish I had studied it more closely when I had the time.
What does that say about PageRank, and how is that related to our intuitive perception of pagerank as the importance of each page on a global scale?
There are possible answers to this question, though not at the level of abstraction that you desire. This was a question that I too had an year back.
# posted by 
: 11:08 PM
: 11:08 PM
Pagerank the way i understand it:
1. Vector of numbers: one assigned to a page. Represents how important(connected) a page is.
2. Matrix Transformation: Succint way of saying that If page A is connected to page B, propogate a bit of A's ranking to B and vice versa.
3. Eigen vector: Special assignment of numbers to each page as in [1]. Applying [2] on this vector(propagate the rank) does not change the assignment. So we can say that propagation is complete and all the numbers are in some kind of equilibrium. So now each number represents the true importance value of each page.
Whats so confusing in this?
1. Vector of numbers: one assigned to a page. Represents how important(connected) a page is.
2. Matrix Transformation: Succint way of saying that If page A is connected to page B, propogate a bit of A's ranking to B and vice versa.
3. Eigen vector: Special assignment of numbers to each page as in [1]. Applying [2] on this vector(propagate the rank) does not change the assignment. So we can say that propagation is complete and all the numbers are in some kind of equilibrium. So now each number represents the true importance value of each page.
Whats so confusing in this?
# posted by : 10:13 AM
: 10:13 AM
Concur completely! Books and articles prescribed as a part of coursework or otherwise leave you wanting for much more. Dont even start talking about papers. As a result of their poor authoring, we end up searching about them for a much longer time than should really take. And finally, when you've collected enough literature to state that you understand the concept at hand satisfactorily, you start wondering why the authors didn't collect and present things that you and most around you feel comfortable with. Its a conspiracy to make more money. See
bbc.co.uk/radio4/science/rams/publish.ram
Post a Comment
bbc.co.uk/radio4/science/rams/publish.ram
<< Home
Archives
February 2004 July 2004 August 2004 September 2004 October 2004 November 2004 December 2004 January 2005 February 2005 March 2005 April 2005 May 2005 June 2005 July 2005 August 2005 September 2005 October 2005 November 2005 December 2005 January 2006 February 2006 March 2006 April 2006 May 2006 June 2006 July 2006 August 2006 September 2006 October 2006 November 2006 January 2007 April 2007 May 2007 June 2007 November 2007 December 2007 January 2008 March 2008 June 2008 February 2009 June 2009 February 2010 November 2010
Quick index to blog-posts I like (from my personal website)
