Coding The Matrix 406aa
This document was ed by and they confirmed that they have the permission to share it. If you are author or own the copyright of this book, please report to us by using this report form. Report 3i3n4
Overview 26281t
& View Coding The Matrix as PDF for free.
More details 6y5l6z
- Words: 3,086
- Pages: 61
Coding the Matrix! Divya Panabhan Intelligent Systems Lab, Dept. of CSA, Indian Institute of Science, Bangalore
June 28, 2013
Divya Panabhan
Coding the Matrix!
June 28, 2013
1
How does the most popular search engine work?
Google it! Search more than 8 billion pages .. Results in less than a second.. How is it possible??? What is Google doing in that 1 second?
Divya Panabhan
Coding the Matrix!
June 28, 2013
2
How does Facebook manage information about you?
Friend network matrix U · · · Un 1 U1 ··· U2 ··· .. . Un ··· Divya Panabhan
Coding the Matrix!
June 28, 2013
3
How does Flipkart recommend products for you?
How does Flipkart know what you require? How does Flipkart keep track of so many s and find their interests?
Divya Panabhan
Coding the Matrix!
June 28, 2013
4
Some BASICS!!!
Divya Panabhan
Coding the Matrix!
June 28, 2013
5
Preliminaries
Vectors eg. How well can you sing? paint? play? .. Professional singer : 1 · · · . Amateur : 0.1 · · ·
Divya Panabhan
Coding the Matrix!
June 28, 2013
6
Preliminaries
Vectors eg. How well can you sing? paint? play? .. Professional singer : 1 · · · . Amateur : 0.1 · · · q Norm |~x | = x12 + x22 + · · · + xn2
Dot product ~x .~y = |~x ||~y | cos θ = x1 y1 + x2 y2 + · · · + xn yn Divya Panabhan
Coding the Matrix!
June 28, 2013
6
Orthogonality and Projections Figure: Orthogonal vectors ~x T ~y = ||x||||y || cos θ = 0
~x θ ~y
Divya Panabhan
Coding the Matrix!
June 28, 2013
7
Orthogonality and Projections Figure: Orthogonal vectors ~x T ~y = ||x||||y || cos θ = 0
~x θ ~y
Figure: Projection of ~x on ~y =
~ x .~ y ||~ y ||
~x
Z O Divya Panabhan
~y
~x.~y ||y||
Coding the Matrix!
June 28, 2013
7
Linear Combination and Independence
Linear Combination c1~x + c2~y , c1 ∈ R, c2 ∈ R
Linear Independence of vectors ~x and ~y c1~x + c2~y = 0 ⇒ c1 = 0, c2 = 0
Divya Panabhan
Coding the Matrix!
June 28, 2013
8
Linear Combination and Independence
Linear Combination c1~x + c2~y , c1 ∈ R, c2 ∈ R
Linear Independence of vectors ~x and ~y c1~x + c2~y = 0 ⇒ c1 = 0, c2 = 0 Can’t express ~x in of ~y .
Divya Panabhan
Coding the Matrix!
June 28, 2013
8
Linear Combination and Independence
Linear Combination c1~x + c2~y , c1 ∈ R, c2 ∈ R
Linear Independence of vectors ~x and ~y c1~x + c2~y = 0 ⇒ c1 = 0, c2 = 0 Can’t express ~x in of ~y . 1 2 , , c1 = 0, c2 = 0 Eg. 0 3 Linearly dependent : 1 2 , , c1 = 2, c2 = −1 2 4
Divya Panabhan
Coding the Matrix!
June 28, 2013
8
Matrix Multiplication
Divya Panabhan
Coding the Matrix!
June 28, 2013
9
Matrix Multiplication
A
B
C
z }| { z}|{ z }| { 2 3 1 8 = 4 5 2 14 2 3 8 +2 = 1 4 5 14
Divya Panabhan
Coding the Matrix!
June 28, 2013
9
Row and column vectors
2 1 0 A= 3 −1 4
Divya Panabhan
Coding the Matrix!
June 28, 2013
10
Row and column vectors
2 1 0 A= 3 −1 4 2 3 Row vectors = r 1 = 1 , r 2 = −1 0 4
Divya Panabhan
Coding the Matrix!
June 28, 2013
10
Row and column vectors
2 1 0 A= 3 −1 4 2 3 Row vectors = r 1 = 1 , r 2 = −1 0 4 2 1 0 Column vectors = c1 = , c2 = , c3 = 3 −1 4
Divya Panabhan
Coding the Matrix!
June 28, 2013
10
Fundamental spaces
Row space and column space of A Row Space: Linear combination of r 1, r 2. Column space : Linear combination of c1, c2, c3 Null space: Vectors orthogonal to row space of A. Row Space (A) = Col space (AT )
Divya Panabhan
Coding the Matrix!
June 28, 2013
11
Representatives of a space Basis and dimensions of a space Basis : Smallest no. of linearly independent vectors whose linear combination gives the entire space.
−2 1 0 = −2 +1 1 0 1 Dimension : No. of vectors in the basis. Divya Panabhan
Coding the Matrix!
June 28, 2013
12
Redundancy elimination
Rank and nullity of matrix A Rank(A)= no. of linearly independent column vectors of A. Nullity(A) = dimension of nullspace of A. Rank measures redundancy in the matrix.
Divya Panabhan
Coding the Matrix!
June 28, 2013
13
Redundancy elimination
Rank and nullity of matrix A Rank(A)= no. of linearly independent column vectors of A. Nullity(A) = dimension of nullspace of A. Rank measures redundancy in the matrix. 1 0 −4 −28 −15 0 1 −1 −2 −6
Divya Panabhan
Coding the Matrix!
June 28, 2013
13
Redundancy elimination
Rank and nullity of matrix A Rank(A)= no. of linearly independent column vectors of A. Nullity(A) = dimension of nullspace of A. Rank measures redundancy in the matrix. 1 0 −4 −28 −15 0 1 −1 −2 −6 Rank-Nullity Theorem: Rank(A) + Nullity(A) = n
Divya Panabhan
Coding the Matrix!
June 28, 2013
13
Eigen values and eigen vectors Publi Speaking
0.8
x
1 Resear h
Divya Panabhan
Coding the Matrix!
June 28, 2013
14
Eigen values and eigen vectors Publi Speaking
A2×2
0.8
−−−→
x
1 Resear h
Divya Panabhan
Coding the Matrix!
June 28, 2013
14
Eigen values and eigen vectors Publi
Publi
Speaking
Speaking
Ax = λx A2×2
0.8
−−−→
x
1.6
0.8
1
x
1
Divya Panabhan
2 Resear h
Resear h
Coding the Matrix!
June 28, 2013
14
Eigen values and eigen vectors Publi
Publi
Speaking
Speaking
Ax = λx A2×2
0.8
−−−→
x
1.6
0.8
1
x
1
2 Resear h
Resear h
How do you determine the x and λ given a matrix A? Ax = λx, x 6= ~0 ( or x T AT = λx T , x 6= ~0 )
Divya Panabhan
Coding the Matrix!
June 28, 2013
14
Eigen values and eigen vectors Publi
Publi
Speaking
Speaking
Ax = λx A2×2
0.8
−−−→
x
1.6
0.8
1
x
1
2 Resear h
Resear h
How do you determine the x and λ given a matrix A? Ax = λx, x 6= ~0 ( or x T AT = λx T , x 6= ~0 ) (A − λI )x = 0
Divya Panabhan
Coding the Matrix!
June 28, 2013
14
Eigen values and eigen vectors Publi
Publi
Speaking
Speaking
Ax = λx A2×2
0.8
−−−→
x
1.6
0.8
1
x
1
2 Resear h
Resear h
How do you determine the x and λ given a matrix A? Ax = λx, x 6= ~0 ( or x T AT = λx T , x 6= ~0 ) (A − λI )x = 0 det(A − λI ) = 0 Divya Panabhan
Coding the Matrix!
June 28, 2013
14
Eigen values and eigen vectors Publi
Publi
Speaking
Speaking
Ax = λx A2×2
0.8
−−−→
x
1.6
0.8
1
x
1
2 Resear h
Resear h
How do you determine the x and λ given a matrix A? Ax = λx, x 6= ~0 ( or x T AT = λx T , x 6= ~0 ) (A − λI )x = 0 det(A − λI ) = 0 Divya Panabhan
Coding the Matrix!
June 28, 2013
14
Now for the FUN stuff!!!
Divya Panabhan
Coding the Matrix!
June 28, 2013
15
A Typical Search Activity : Random surfer
Divya Panabhan
Coding the Matrix!
June 28, 2013
16
A Typical Search Activity : Random surfer
Jump −−−→
Divya Panabhan
Coding the Matrix!
June 28, 2013
16
Importance of pages
Divya Panabhan
Coding the Matrix!
June 28, 2013
17
Importance of pages
Divya Panabhan
Coding the Matrix!
June 28, 2013
17
Page Rank Algorithm
Divya Panabhan
Coding the Matrix!
June 28, 2013
18
Page Rank Algorithm Transition A B A 0 13 1 B 2 0 C 1 0 D 0 12
Divya Panabhan
Coding the Matrix!
Matrix H C D 1 1 3
0 0 1 2
3 1 2
0 0
June 28, 2013
18
Page Rank Algorithm Transition A B A 0 13 1 B 2 0 C 1 0 D 0 12
Matrix H C D 1 1 3
0 0 1 2
3 1 2
0 0
Anything particular about H?
Divya Panabhan
Coding the Matrix!
June 28, 2013
18
Page Rank Algorithm Transition A B A 0 13 1 B 2 0 C 1 0 D 0 12
Matrix H C D 1 1 3
0 0 1 2
3 1 2
0 0
Anything particular about H? H : row stochastic
Divya Panabhan
Coding the Matrix!
June 28, 2013
18
Page Rank Algorithm Transition A B A 0 13 1 B 2 0 C 1 0 D 0 12
Matrix H C D 1 1 3
0 0 1 2
3 1 2
0 0
Anything particular about H? H : row stochastic Vt (A) : Probability of being t at page A at time Vt : row vector. eg. 0.1 0.3 · · ·
Divya Panabhan
Coding the Matrix!
June 28, 2013
18
Page Rank Algorithm Transition A B A 0 13 1 B 2 0 C 1 0 D 0 12
Matrix H C D 1 1 3
0 0 1 2
3 1 2
0 0
Anything particular about H? H : row stochastic Vt (A) : Probability of being t at page A at time Vt : row vector. eg. 0.1 0.3 · · · Vt (A) = Vt−1 (A)HAA + Vt−1 (B)HBA + . . .
Divya Panabhan
Coding the Matrix!
June 28, 2013
18
Page Rank Algorithm Transition A B A 0 13 1 B 2 0 C 1 0 D 0 12
Matrix H C D 1 1 3
0 0 1 2
3 1 2
0 0
Anything particular about H? H : row stochastic Vt (A) : Probability of being t at page A at time Vt : row vector. eg. 0.1 0.3 · · · Vt (A) = Vt−1 (A)HAA + Vt−1 (B)HBA + . . .
Vt = Vt−1 H Divya Panabhan
Coding the Matrix!
June 28, 2013
18
Page Rank Algorithm Transition A B A 0 13 1 B 2 0 C 1 0 D 0 12
Matrix H C D 1 1 3
0 0 1 2
3 1 2
0 0
H : row stochastic, guaranteed to have eigen value 1, under some conditions. 1/4 1/4 V0 = 1/4, 1/4
Divya Panabhan
Coding the Matrix!
June 28, 2013
19
Page Rank Algorithm Transition A B A 0 13 1 B 2 0 C 1 0 D 0 12
Matrix H C D 1 1 3
0 0 1 2
3 1 2
0 0
H : row stochastic, guaranteed to have eigen value 1, under some conditions. 1/4 9/24 1/4 5/24 V0 = 1/4, V1 = V0 H = 5/24 , 1/4 5/24
Divya Panabhan
Coding the Matrix!
June 28, 2013
19
Page Rank Algorithm Transition A B A 0 13 1 B 2 0 C 1 0 D 0 12
Matrix H C D 1 1 3
0 0 1 2
3 1 2
0 0
H : row stochastic, guaranteed to have eigen value 1, under some conditions. 1/4 9/24 15/48 1/4 5/24 11/48 V0 = 1/4, V1 = V0 H = 5/24 , V2 = V1 H = 11/48 1/4 5/24 11/48
Divya Panabhan
Coding the Matrix!
June 28, 2013
19
Page Rank Algorithm Transition A B A 0 13 1 B 2 0 C1 0 D 0 12
Matrix H C D 1 1 3
0 0 1 2
3 1 2
0 0
H : row stochastic, guaranteed to have eigen value 1, under some conditions. .. . Vn = Vn−1 H
Divya Panabhan
Coding the Matrix!
June 28, 2013
20
Page Rank Algorithm Transition A B A 0 13 1 B 2 0 C1 0 D 0 12
Matrix H C D 1 1 3
0 0 1 2
3 1 2
0 0
H : row stochastic, guaranteed to have eigen value 1, under some conditions. .. . Vn = Vn−1 H
Divya Panabhan
Coding the Matrix!
June 28, 2013
20
Page Rank Algorithm Transition A B A 0 13 1 B 2 0 C1 0 D 0 12
Matrix H C D 1 1 3
0 0 1 2
3 1 2
0 0
H : row stochastic, guaranteed to have eigen value 1, under some conditions. .. . Vn = Vn−1 H .. . vH = 1v
Divya Panabhan
Coding the Matrix!
June 28, 2013
20
Page Rank Algorithm Transition A B A 0 13 1 B 2 0 C1 0 D 0 12
Matrix H C D 1 1 3
0 0 1 2
3 1 2
0 0
H : row stochastic, guaranteed to have eigen value 1, under some conditions. .. . Vn = Vn−1 H .. . vH = 1v v is the eigen vector of H corresponding to eigen value 1 !!! Divya Panabhan
Coding the Matrix!
June 28, 2013
20
Page Rank Algorithm - conditions on H Transition A B A 0 13 1 B 2 0 C 1 0 D 0 12
Divya Panabhan
Coding the Matrix!
Matrix H C D 1 1 3
0 0 1 2
3 1 2
0 0
June 28, 2013
21
Page Rank Algorithm - conditions on H Transition A B A 0 13 1 B 2 0 C 1 0 D 0 12
Matrix H C D 1 1 3
0 0 1 2
3 1 2
0 0
Row stochastic
Divya Panabhan
Coding the Matrix!
June 28, 2013
21
Page Rank Algorithm - conditions on H Transition A B A 0 13 1 B 2 0 C 1 0 D 0 12
Matrix H C D 1 1 3
0 0 1 2
3 1 2
0 0
Row stochastic Irreducible :Possible to reach a page from any other page.
Divya Panabhan
Coding the Matrix!
June 28, 2013
21
Page Rank Algorithm - conditions on H Transition A B A 0 13 1 B 2 0 C 1 0 D 0 12
Matrix H C D 1 1 3
0 0 1 2
3 1 2
0 0
Row stochastic Irreducible :Possible to reach a page from any other page. Aperiodic : Not periodic
Divya Panabhan
Coding the Matrix!
June 28, 2013
21
Page Rank Algorithm - Dangling nodes Transition A B A 0 13 1 B 21 0 C2 0 D 0 0
Divya Panabhan
Coding the Matrix!
Matrix H C D 1 1 3
0 0 0
3 1 2 1 2
0
June 28, 2013
22
Page Rank Algorithm - Dangling nodes Transition A B A 0 13 1 B 21 0 C2 0 D 0 0
Matrix H C D 1 1 3
0 0 0
3 1 2 1 2
0
S =H +Y A
B = C D
Divya Panabhan
A
B
C
D
0
1 3
1 3
1 2 1 2 1 4
0
0
0
0
1 4
1 4
1 3 1 2 1 2 1 4
Coding the Matrix!
June 28, 2013
22
Page Rank Algorithm - Entering a new destination
A B S= C D
A 0
B
C
D
1 2 1 2 1 4
1 3
1 3
0 0
0 0
1 4
1 4
1 3 1 2 1 2 1 4
1/n · · · ··· B: 1/n · · ·
1/n
1/n
n×n
Google matrix! Surfer follows the link structure 60 % of time Otherwise to a random page! G = αS + (1 − α)B
Divya Panabhan
Coding the Matrix!
June 28, 2013
23
Page Rank Algorithm
Search Engines Get pages containing query words. Use page rank to determine the order of pages to be displayed.
Divya Panabhan
Coding the Matrix!
June 28, 2013
24
Page Rank Algorithm
Search Engines Get pages containing query words. Use page rank to determine the order of pages to be displayed. Ford 0.1 0.7 Maruti Volkswagen 0.05 Hyundai 0.15
Divya Panabhan
Coding the Matrix!
June 28, 2013
24
Recommender Systems
Divya Panabhan
Coding the Matrix!
June 28, 2013
25
Recommender Systems
Matrix Factorization Original matrix Xd×n (d s, n movies) ˆ = Md×k × Hk×n X ≈X Find M, H.
Divya Panabhan
Coding the Matrix!
June 28, 2013
26
References
1
Gilbert Strang, “Linear Algebra and its Applications”, Fourth Edition.
2
Langville and Meyer,“Google’s PageRank and Beyond”.
3
Gene H. Golub, Charles F. Van Loan, “Matrix Computations”.
4
Howard Anton, Chris Rorres, “Elementary Linear Algebra”.
Divya Panabhan
Coding the Matrix!
June 28, 2013
27
THANK YOU!
Divya Panabhan
Coding the Matrix!
June 28, 2013
28
June 28, 2013
Divya Panabhan
Coding the Matrix!
June 28, 2013
1
How does the most popular search engine work?
Google it! Search more than 8 billion pages .. Results in less than a second.. How is it possible??? What is Google doing in that 1 second?
Divya Panabhan
Coding the Matrix!
June 28, 2013
2
How does Facebook manage information about you?
Friend network matrix U · · · Un 1 U1 ··· U2 ··· .. . Un ··· Divya Panabhan
Coding the Matrix!
June 28, 2013
3
How does Flipkart recommend products for you?
How does Flipkart know what you require? How does Flipkart keep track of so many s and find their interests?
Divya Panabhan
Coding the Matrix!
June 28, 2013
4
Some BASICS!!!
Divya Panabhan
Coding the Matrix!
June 28, 2013
5
Preliminaries
Vectors eg. How well can you sing? paint? play? .. Professional singer : 1 · · · . Amateur : 0.1 · · ·
Divya Panabhan
Coding the Matrix!
June 28, 2013
6
Preliminaries
Vectors eg. How well can you sing? paint? play? .. Professional singer : 1 · · · . Amateur : 0.1 · · · q Norm |~x | = x12 + x22 + · · · + xn2
Dot product ~x .~y = |~x ||~y | cos θ = x1 y1 + x2 y2 + · · · + xn yn Divya Panabhan
Coding the Matrix!
June 28, 2013
6
Orthogonality and Projections Figure: Orthogonal vectors ~x T ~y = ||x||||y || cos θ = 0
~x θ ~y
Divya Panabhan
Coding the Matrix!
June 28, 2013
7
Orthogonality and Projections Figure: Orthogonal vectors ~x T ~y = ||x||||y || cos θ = 0
~x θ ~y
Figure: Projection of ~x on ~y =
~ x .~ y ||~ y ||
~x
Z O Divya Panabhan
~y
~x.~y ||y||
Coding the Matrix!
June 28, 2013
7
Linear Combination and Independence
Linear Combination c1~x + c2~y , c1 ∈ R, c2 ∈ R
Linear Independence of vectors ~x and ~y c1~x + c2~y = 0 ⇒ c1 = 0, c2 = 0
Divya Panabhan
Coding the Matrix!
June 28, 2013
8
Linear Combination and Independence
Linear Combination c1~x + c2~y , c1 ∈ R, c2 ∈ R
Linear Independence of vectors ~x and ~y c1~x + c2~y = 0 ⇒ c1 = 0, c2 = 0 Can’t express ~x in of ~y .
Divya Panabhan
Coding the Matrix!
June 28, 2013
8
Linear Combination and Independence
Linear Combination c1~x + c2~y , c1 ∈ R, c2 ∈ R
Linear Independence of vectors ~x and ~y c1~x + c2~y = 0 ⇒ c1 = 0, c2 = 0 Can’t express ~x in of ~y . 1 2 , , c1 = 0, c2 = 0 Eg. 0 3 Linearly dependent : 1 2 , , c1 = 2, c2 = −1 2 4
Divya Panabhan
Coding the Matrix!
June 28, 2013
8
Matrix Multiplication
Divya Panabhan
Coding the Matrix!
June 28, 2013
9
Matrix Multiplication
A
B
C
z }| { z}|{ z }| { 2 3 1 8 = 4 5 2 14 2 3 8 +2 = 1 4 5 14
Divya Panabhan
Coding the Matrix!
June 28, 2013
9
Row and column vectors
2 1 0 A= 3 −1 4
Divya Panabhan
Coding the Matrix!
June 28, 2013
10
Row and column vectors
2 1 0 A= 3 −1 4 2 3 Row vectors = r 1 = 1 , r 2 = −1 0 4
Divya Panabhan
Coding the Matrix!
June 28, 2013
10
Row and column vectors
2 1 0 A= 3 −1 4 2 3 Row vectors = r 1 = 1 , r 2 = −1 0 4 2 1 0 Column vectors = c1 = , c2 = , c3 = 3 −1 4
Divya Panabhan
Coding the Matrix!
June 28, 2013
10
Fundamental spaces
Row space and column space of A Row Space: Linear combination of r 1, r 2. Column space : Linear combination of c1, c2, c3 Null space: Vectors orthogonal to row space of A. Row Space (A) = Col space (AT )
Divya Panabhan
Coding the Matrix!
June 28, 2013
11
Representatives of a space Basis and dimensions of a space Basis : Smallest no. of linearly independent vectors whose linear combination gives the entire space.
−2 1 0 = −2 +1 1 0 1 Dimension : No. of vectors in the basis. Divya Panabhan
Coding the Matrix!
June 28, 2013
12
Redundancy elimination
Rank and nullity of matrix A Rank(A)= no. of linearly independent column vectors of A. Nullity(A) = dimension of nullspace of A. Rank measures redundancy in the matrix.
Divya Panabhan
Coding the Matrix!
June 28, 2013
13
Redundancy elimination
Rank and nullity of matrix A Rank(A)= no. of linearly independent column vectors of A. Nullity(A) = dimension of nullspace of A. Rank measures redundancy in the matrix. 1 0 −4 −28 −15 0 1 −1 −2 −6
Divya Panabhan
Coding the Matrix!
June 28, 2013
13
Redundancy elimination
Rank and nullity of matrix A Rank(A)= no. of linearly independent column vectors of A. Nullity(A) = dimension of nullspace of A. Rank measures redundancy in the matrix. 1 0 −4 −28 −15 0 1 −1 −2 −6 Rank-Nullity Theorem: Rank(A) + Nullity(A) = n
Divya Panabhan
Coding the Matrix!
June 28, 2013
13
Eigen values and eigen vectors Publi Speaking
0.8
x
1 Resear h
Divya Panabhan
Coding the Matrix!
June 28, 2013
14
Eigen values and eigen vectors Publi Speaking
A2×2
0.8
−−−→
x
1 Resear h
Divya Panabhan
Coding the Matrix!
June 28, 2013
14
Eigen values and eigen vectors Publi
Publi
Speaking
Speaking
Ax = λx A2×2
0.8
−−−→
x
1.6
0.8
1
x
1
Divya Panabhan
2 Resear h
Resear h
Coding the Matrix!
June 28, 2013
14
Eigen values and eigen vectors Publi
Publi
Speaking
Speaking
Ax = λx A2×2
0.8
−−−→
x
1.6
0.8
1
x
1
2 Resear h
Resear h
How do you determine the x and λ given a matrix A? Ax = λx, x 6= ~0 ( or x T AT = λx T , x 6= ~0 )
Divya Panabhan
Coding the Matrix!
June 28, 2013
14
Eigen values and eigen vectors Publi
Publi
Speaking
Speaking
Ax = λx A2×2
0.8
−−−→
x
1.6
0.8
1
x
1
2 Resear h
Resear h
How do you determine the x and λ given a matrix A? Ax = λx, x 6= ~0 ( or x T AT = λx T , x 6= ~0 ) (A − λI )x = 0
Divya Panabhan
Coding the Matrix!
June 28, 2013
14
Eigen values and eigen vectors Publi
Publi
Speaking
Speaking
Ax = λx A2×2
0.8
−−−→
x
1.6
0.8
1
x
1
2 Resear h
Resear h
How do you determine the x and λ given a matrix A? Ax = λx, x 6= ~0 ( or x T AT = λx T , x 6= ~0 ) (A − λI )x = 0 det(A − λI ) = 0 Divya Panabhan
Coding the Matrix!
June 28, 2013
14
Eigen values and eigen vectors Publi
Publi
Speaking
Speaking
Ax = λx A2×2
0.8
−−−→
x
1.6
0.8
1
x
1
2 Resear h
Resear h
How do you determine the x and λ given a matrix A? Ax = λx, x 6= ~0 ( or x T AT = λx T , x 6= ~0 ) (A − λI )x = 0 det(A − λI ) = 0 Divya Panabhan
Coding the Matrix!
June 28, 2013
14
Now for the FUN stuff!!!
Divya Panabhan
Coding the Matrix!
June 28, 2013
15
A Typical Search Activity : Random surfer
Divya Panabhan
Coding the Matrix!
June 28, 2013
16
A Typical Search Activity : Random surfer
Jump −−−→
Divya Panabhan
Coding the Matrix!
June 28, 2013
16
Importance of pages
Divya Panabhan
Coding the Matrix!
June 28, 2013
17
Importance of pages
Divya Panabhan
Coding the Matrix!
June 28, 2013
17
Page Rank Algorithm
Divya Panabhan
Coding the Matrix!
June 28, 2013
18
Page Rank Algorithm Transition A B A 0 13 1 B 2 0 C 1 0 D 0 12
Divya Panabhan
Coding the Matrix!
Matrix H C D 1 1 3
0 0 1 2
3 1 2
0 0
June 28, 2013
18
Page Rank Algorithm Transition A B A 0 13 1 B 2 0 C 1 0 D 0 12
Matrix H C D 1 1 3
0 0 1 2
3 1 2
0 0
Anything particular about H?
Divya Panabhan
Coding the Matrix!
June 28, 2013
18
Page Rank Algorithm Transition A B A 0 13 1 B 2 0 C 1 0 D 0 12
Matrix H C D 1 1 3
0 0 1 2
3 1 2
0 0
Anything particular about H? H : row stochastic
Divya Panabhan
Coding the Matrix!
June 28, 2013
18
Page Rank Algorithm Transition A B A 0 13 1 B 2 0 C 1 0 D 0 12
Matrix H C D 1 1 3
0 0 1 2
3 1 2
0 0
Anything particular about H? H : row stochastic Vt (A) : Probability of being t at page A at time Vt : row vector. eg. 0.1 0.3 · · ·
Divya Panabhan
Coding the Matrix!
June 28, 2013
18
Page Rank Algorithm Transition A B A 0 13 1 B 2 0 C 1 0 D 0 12
Matrix H C D 1 1 3
0 0 1 2
3 1 2
0 0
Anything particular about H? H : row stochastic Vt (A) : Probability of being t at page A at time Vt : row vector. eg. 0.1 0.3 · · · Vt (A) = Vt−1 (A)HAA + Vt−1 (B)HBA + . . .
Divya Panabhan
Coding the Matrix!
June 28, 2013
18
Page Rank Algorithm Transition A B A 0 13 1 B 2 0 C 1 0 D 0 12
Matrix H C D 1 1 3
0 0 1 2
3 1 2
0 0
Anything particular about H? H : row stochastic Vt (A) : Probability of being t at page A at time Vt : row vector. eg. 0.1 0.3 · · · Vt (A) = Vt−1 (A)HAA + Vt−1 (B)HBA + . . .
Vt = Vt−1 H Divya Panabhan
Coding the Matrix!
June 28, 2013
18
Page Rank Algorithm Transition A B A 0 13 1 B 2 0 C 1 0 D 0 12
Matrix H C D 1 1 3
0 0 1 2
3 1 2
0 0
H : row stochastic, guaranteed to have eigen value 1, under some conditions. 1/4 1/4 V0 = 1/4, 1/4
Divya Panabhan
Coding the Matrix!
June 28, 2013
19
Page Rank Algorithm Transition A B A 0 13 1 B 2 0 C 1 0 D 0 12
Matrix H C D 1 1 3
0 0 1 2
3 1 2
0 0
H : row stochastic, guaranteed to have eigen value 1, under some conditions. 1/4 9/24 1/4 5/24 V0 = 1/4, V1 = V0 H = 5/24 , 1/4 5/24
Divya Panabhan
Coding the Matrix!
June 28, 2013
19
Page Rank Algorithm Transition A B A 0 13 1 B 2 0 C 1 0 D 0 12
Matrix H C D 1 1 3
0 0 1 2
3 1 2
0 0
H : row stochastic, guaranteed to have eigen value 1, under some conditions. 1/4 9/24 15/48 1/4 5/24 11/48 V0 = 1/4, V1 = V0 H = 5/24 , V2 = V1 H = 11/48 1/4 5/24 11/48
Divya Panabhan
Coding the Matrix!
June 28, 2013
19
Page Rank Algorithm Transition A B A 0 13 1 B 2 0 C1 0 D 0 12
Matrix H C D 1 1 3
0 0 1 2
3 1 2
0 0
H : row stochastic, guaranteed to have eigen value 1, under some conditions. .. . Vn = Vn−1 H
Divya Panabhan
Coding the Matrix!
June 28, 2013
20
Page Rank Algorithm Transition A B A 0 13 1 B 2 0 C1 0 D 0 12
Matrix H C D 1 1 3
0 0 1 2
3 1 2
0 0
H : row stochastic, guaranteed to have eigen value 1, under some conditions. .. . Vn = Vn−1 H
Divya Panabhan
Coding the Matrix!
June 28, 2013
20
Page Rank Algorithm Transition A B A 0 13 1 B 2 0 C1 0 D 0 12
Matrix H C D 1 1 3
0 0 1 2
3 1 2
0 0
H : row stochastic, guaranteed to have eigen value 1, under some conditions. .. . Vn = Vn−1 H .. . vH = 1v
Divya Panabhan
Coding the Matrix!
June 28, 2013
20
Page Rank Algorithm Transition A B A 0 13 1 B 2 0 C1 0 D 0 12
Matrix H C D 1 1 3
0 0 1 2
3 1 2
0 0
H : row stochastic, guaranteed to have eigen value 1, under some conditions. .. . Vn = Vn−1 H .. . vH = 1v v is the eigen vector of H corresponding to eigen value 1 !!! Divya Panabhan
Coding the Matrix!
June 28, 2013
20
Page Rank Algorithm - conditions on H Transition A B A 0 13 1 B 2 0 C 1 0 D 0 12
Divya Panabhan
Coding the Matrix!
Matrix H C D 1 1 3
0 0 1 2
3 1 2
0 0
June 28, 2013
21
Page Rank Algorithm - conditions on H Transition A B A 0 13 1 B 2 0 C 1 0 D 0 12
Matrix H C D 1 1 3
0 0 1 2
3 1 2
0 0
Row stochastic
Divya Panabhan
Coding the Matrix!
June 28, 2013
21
Page Rank Algorithm - conditions on H Transition A B A 0 13 1 B 2 0 C 1 0 D 0 12
Matrix H C D 1 1 3
0 0 1 2
3 1 2
0 0
Row stochastic Irreducible :Possible to reach a page from any other page.
Divya Panabhan
Coding the Matrix!
June 28, 2013
21
Page Rank Algorithm - conditions on H Transition A B A 0 13 1 B 2 0 C 1 0 D 0 12
Matrix H C D 1 1 3
0 0 1 2
3 1 2
0 0
Row stochastic Irreducible :Possible to reach a page from any other page. Aperiodic : Not periodic
Divya Panabhan
Coding the Matrix!
June 28, 2013
21
Page Rank Algorithm - Dangling nodes Transition A B A 0 13 1 B 21 0 C2 0 D 0 0
Divya Panabhan
Coding the Matrix!
Matrix H C D 1 1 3
0 0 0
3 1 2 1 2
0
June 28, 2013
22
Page Rank Algorithm - Dangling nodes Transition A B A 0 13 1 B 21 0 C2 0 D 0 0
Matrix H C D 1 1 3
0 0 0
3 1 2 1 2
0
S =H +Y A
B = C D
Divya Panabhan
A
B
C
D
0
1 3
1 3
1 2 1 2 1 4
0
0
0
0
1 4
1 4
1 3 1 2 1 2 1 4
Coding the Matrix!
June 28, 2013
22
Page Rank Algorithm - Entering a new destination
A B S= C D
A 0
B
C
D
1 2 1 2 1 4
1 3
1 3
0 0
0 0
1 4
1 4
1 3 1 2 1 2 1 4
1/n · · · ··· B: 1/n · · ·
1/n
1/n
n×n
Google matrix! Surfer follows the link structure 60 % of time Otherwise to a random page! G = αS + (1 − α)B
Divya Panabhan
Coding the Matrix!
June 28, 2013
23
Page Rank Algorithm
Search Engines Get pages containing query words. Use page rank to determine the order of pages to be displayed.
Divya Panabhan
Coding the Matrix!
June 28, 2013
24
Page Rank Algorithm
Search Engines Get pages containing query words. Use page rank to determine the order of pages to be displayed. Ford 0.1 0.7 Maruti Volkswagen 0.05 Hyundai 0.15
Divya Panabhan
Coding the Matrix!
June 28, 2013
24
Recommender Systems
Divya Panabhan
Coding the Matrix!
June 28, 2013
25
Recommender Systems
Matrix Factorization Original matrix Xd×n (d s, n movies) ˆ = Md×k × Hk×n X ≈X Find M, H.
Divya Panabhan
Coding the Matrix!
June 28, 2013
26
References
1
Gilbert Strang, “Linear Algebra and its Applications”, Fourth Edition.
2
Langville and Meyer,“Google’s PageRank and Beyond”.
3
Gene H. Golub, Charles F. Van Loan, “Matrix Computations”.
4
Howard Anton, Chris Rorres, “Elementary Linear Algebra”.
Divya Panabhan
Coding the Matrix!
June 28, 2013
27
THANK YOU!
Divya Panabhan
Coding the Matrix!
June 28, 2013
28
Related Documents 3h463d
Coding The Matrix 406aa
December 2019 36
Scirocco Coding Matrix 443sy
October 2021 0
The Matrix 1u5z3v
August 2021 0
The Matrix 1u5z3v
December 2020 0
The Maverick Matrix c1l6q
December 2021 0