Announcements¶

• Homework:
  • Homework 9 out, due today
• Final exam: Monday, May 8 from 12-2pm
  • Practice exam will be out today
• Wednesday's class is review
• Upcoming office hours:
  • Tomorrow: Peer tutor Rohan Anand from 1:30-3pm in CCDS 16th floor
  • Tomorrow: Abhishek Tiwari from 3:30-4:30pm on CCDS 13th floor

Lecture 38: Faster PageRank¶

[This lecture is based on Prof. Crovella's CS 132 lecture notes.]

The PageRank Insight¶

Links are endorsements. When a first page contains a link to a second page, that is an indication that the author of the first page thinks the second page is worth looking at. If the first and second pages both contain the same query terms, it is likely that the second page is an important page with respect to that query term.

What they are implying is that a random surfer should visit important pages more often and unimportant pages less often.

The way to interpret this precisely is:

1. Form the graph that encodes the connections between Web pages that are retrieved for a particular query.

2. Construct a Markov chain that corresponds to a random walk on this graph.

3. Rank-order the pages according to their probability in the Markov chain's steady state.

So let's try to make this work and see what happens.

Example. Assume a set of Web pages have been selected based on a text query, e.g., pages related to "personal 737 jets."

These pages have various links between them, as represented by this graph:

Construct the unique steady-state distribution for a random walk on this graph, if it exists. That is, construct the PageRank for this set of Web pages.

Solution.

The key question we must ask is whether a unique steady state exists.

Step 1.¶

Assume there are $n$ pages to be ranked. Construct an $n\times n$ transition matrix for the Markov chain.

Set the Markov chain transitions so that each outgoing link from a node has equal probability of being taken.

We have already seen the transition matrix for this graph:

We have observed that this transition matrix is not regular, because for any $A^k,k>0,$ the second column will be zero.

To address this, let's ask why it happens.

The reason that column 2 of $P$ is zero is that the Web page corresponding to node 2 has no links embedded in it, so there is nowhere to go from this page. Of course this will happen a lot in an arbitrary collection of Web pages.

Note that Page and Brin say that the random surfer will occasionally "start on another random page." In other words, it seems reasonable that when reaching a page with no embedded links, the surfer chooses another page at random.

So this motivates the first adjustment to $P$:

Step 2.¶

Form the matrix $P^{\prime }$ as follows: for each column in $P$ that is entirely zeros, replace it with a column in which each entry is $1/n$.

In our example:

Nonetheless, even after this change, $P^{\prime }$ can fail to be regular.

In other words, for an arbitrary set of web pages, there is no guarantee that their transition matrix will be regular.

Once again, let's read the words of Page and Brin closely: the surfer "eventually gets bored and starts on another random page."

Step 3.¶

In practice this means that there a small probability that the surfer will jump from any page to any other page at random.

Let's call this small probability $\alpha .$

We can't just add $\alpha$ to every entry in $P^{\prime }$, because then the columns of the new matrix would not sum to 1.

Instead we decrease each entry in $P^{\prime }$ by a factor of $(1-\alpha )$, and then add $\alpha /n$ to it.

So we compute the final transition matrix $P^{\prime \prime }$ as:

We can write this as a matrix equation:

where $1$ is an $n\times n$ matrix of 1's.

In our example, let's say that $\alpha =1/10$ (in reality it would be smaller). So $\alpha /n=1/60.$

Then:

Obviously, $P^{\prime \prime }$ is regular, because all its entries are positive (they are at least $\alpha /n.$)

$P^{\prime \prime }$ is the Markov Chain that Brin and Page defined, and which is used by PageRank to rank pages in response to a Google search.

Step 4.¶

Compute the steady-state of $P^{\prime \prime }$, and rank pages according to their magnitude in the resulting vector.

We can do this by solving $P^{\prime \prime }x=x$, or we can compute the eigenvectors of $P^{\prime \prime }$ and use the eigenvector that corresponds to $\lambda =1.$

For the example $P^{\prime \prime }$, we find that the steady-state vector is:

$x=\left[\begin{array}{c}0.037\\ 0.054\\ 0.041\\ 0.375\\ 0.206\\ 0.286\end{array}\right]$

So the final ranking of pages is: 4, 6, 5, 2, 3, 1.

This is the order that PageRank would display its results, with page 4 at the top of the list.

Let's see how to do Step 4 in Python:

38.1 Computing PageRank: the Power Method¶

From a mathematical standpoint, we are done!

However, from a Computing & Data Sciences standpoint, there are still some issues.

The most significant issue is simply this: PageRank results must be provided very quickly. Search engines are in competition and speed is a competitive advantage.

Here is an example Google search:

Notice that the search returned about 400,000 results!

Recall that using Gaussian elimination to solve $Ax=b$ takes about $\frac{2}{3}{n}^3$ operations.

In this case, apparently $n=400,000.$

So computing the PageRank in the straightforward way we've described would take about 42,667,000,000,000,000 operations.

Assuming a 2GHz CPU, that's on the order of eight months.

We need a faster way to compute the PageRank!

Here is an important point: we only need the principal eigenvector. (The one corresponding to $\lambda =1$).

Let's review how a Markov chain gets to steady state. As we discussed at the beginning of the lecture, the state of the chain at any step $k$ is given by

Let's assume that ${\lambda }_1$ is the eigenvalue 1. If the chain converges to steady sate, then we know that all eigenvalues other than ${\lambda }_1$ are less than 1 in magnitude.

Of course, if $|{\lambda }_i|<1,$

So:

Note that $c_1$ is just a constant that doesn't affect the relative sizes of the components of $x_k$ in the limit of large $k.$

This is another way of stating that the Markov chain goes to steady state no matter what the starting state is.

This observation suggests another way to compute the steady state of the chain:

1. Start from a random state $x_0$.
2. Compute $x_{k+1}=A{x}_k$ for $k=0,1,2,3,\dots$

How do we know when to stop in Step 2?

Since we are looking for steady-state, we can stop when the difference between $x_{k+1}$ and $x_k$ is small.

This is called the power method.

Why is this a better method?

Keep in mind that the number of flops in matrix-vector multiplication is about $2n^2$.

This is compared to $\frac{2}{3}{n}^3$ for solving a system (finding the eigenvector directly).

Let's say that after computing

we find that $x_{10}$ is sufficiently close to $x_9.$

How much work did we do?

We did 10 matrix-vector multiplications, or $20n^2$ flops.

So the power method is

times faster than the direct method.

For our example, $n/30=13,333$. So this trick reduces the running time from 8 months down to 27 minutes.

This is an example of an iterative method. Iterative methods are often the preferred approach for solving linear algebra problems in the real world.

One final thing: how exactly do we decide when to stop iterating in the power method?

One simple way is to add up the differences of the components of $x_{k+1}-x_k$:

and compare it to the sum of the components of $x_k$:

If $s/d$ is small (say, less than 0.001) then we can conclude that $x_{k+1}$ is close enough to $x_k$ for us to stop iterating.

So the power method is fast, making it the algorithm of choice for a company like Google. It is also easy to implement, and easy to parallelize across multiple machines.

38.2 Course Evaluation¶

BU requires that we devote some class time to course evaluations. Your input helps CDS grow!

https://bu.campuslabs.com/courseeval/

Exam review¶

Linear independence¶

A set of vectors $\left\{v_1,...,v_p\right\}$ all of which are in $R^n$ is said to be linearly dependent if there exist weights $\{c_1,...,c_p\},$ not all zero, such that

A set $S=\left\{v_1,...,v_p\right\}$ of two or more vectors is linearly dependent if and only if at least one of the vectors in $S$ is a linear combination of the others.

Gaussian Elimination¶

Definition. A matrix is in echelon form (or row echelon form) if it has the following three properties:

1. All nonzero rows are above any rows of all zeros.
2. Each leading entry of a row is in a column to the right of the leading entry of the row above it.
3. All entries in a column below a leading entry are zeros.

For example:

In this diagram, the leading entries $■$ are nonzero, and the $\ast$ symbols can be any value.

This definition is a special case of an upper triangular matrix.

The goal of the first step of Gaussian elimination is to convert the augmented matrix into echelon form.

Definition: A matrix is in reduced echelon form (or reduced row echelon form) if it is in echelon form, and additionally:

4. The leading entry in each nonzero row is 1.
5. Each leading 1 is the only nonzero entry in its column.

For example:

The goal of the second step of Gaussian elimination is to convert the matrix into reduced echelon form.

Example 1¶

In our first example, let the input matrix $A$ be

Stage 1 (Elimination)

Start with the first row ($i=1$). The leftmost nonzero in row 1 and below is in column 1. But since it's not in row 1, we need to swap. We'll swap rows 1 and 3 (we could have swapped 1 and 2).

The pivot is shown in a box. Use row reduction operations to create zeros below the pivot. In this case, that means subtracting row 1 from row 2.

Now $i=2$. The pivot is boxed (no need to do any swaps). Use row reduction to create zeros below the pivot. To do so we subtract $3/2$ times row 2 from row 3.

Now $i=3$. Since it is the last row, we are done with Stage 1. The pivots are marked:

Stage 2 (Backsubstitution)

Starting again with the first row ($i=1$). Divide row 1 by its pivot.

Moving to the next row ($i=2$). Divide row 2 by its pivot.

And use row reduction operations to create zeros in all elements above the pivot. In this case, that means adding 3 times row 2 to row 1.

Moving to the next row ($i=3$). The pivot is already 1. So we subtract row 3 from row 2, and subtract 5 times row 3 from row 1.

This matrix is in reduced row echelon form, so we are done with GE. The solution is:

Example 2¶

Let's assume that the augmented matrix of a system has been transformed into the equivalent reduced echelon form:

This system is consistent. Is the solution unique?

The associated system of equations is

Variables $x_1$ and $x_2$ correspond to pivot columns. They are called basic variables. The other variable $x_3$ is a free variable.

Whenever a system is consistent, the solution set can be described explicitly by solving the reduced system of equations for the basic variables in terms of the free variables.

This operation is possible because the reduced echelon form places each basic variable in one and only one equation.

In the example, solve the first and second equations for $x_1$ and $x_2$. Ignore the third equation; it offers no restriction on the variables.

So the solution set is:

"$x_3$ is free" means you can choose any value for $x_3$.

In other words, there are an inifinite set of solutions to this linear system. Each solution corresponds to one particular value of $x_3$.

For instance,

• when $x_3=0$, the solution is $(1,4,0)$;
• when $x_3=1,$ the solution is $(6,3,1)$.

How many solutions will a system have?¶

Given a system of $m$ equations in $n$ unknowns, let $A$ be the $m\times (n+1)$ augmented matrix. Let $r$ be the number of pivot positions in the REF of $A$.

• If $r=n$, there is a unique solution (no parameters in the solution).
• If $r>n$ (so $r=n+1$) the system is inconsistent (no solution).
• If $r<n$, either the system is inconsistent (no solution) or has a solution with $n-r$ parameters.

Vector geometry¶

Length is such a fundamental concept that we introduce a special notation and name for it.

Definition. The norm of $v$ is the nonnegative scalar $\parallel v\parallel$ defined by

Definition. For $u$ and $v$ in $R^n,$ the distance between $u$ and $v$, written as $\text{dist}(u,v),$ is the length of the vector $u-v$. That is,

This definition agrees with the usual formulas for the Euclidean distance between two points. The usual formula is

Which you can see is equal to

Definition. Two vectors $u$ and $v$ in $R^n$ are orthogonal to each other if $u^{T}v=0.$

Clustering¶

Clustering is a very important way of discovering structure in data. It represents an example of unsupervised learning.

• Supervised methods: Data items have labels, and we want to learn a function that correctly assigns labels to new data items.

• Unsupervised methods: Data items do not have labels, and we want to learn a function that extracts important patterns from the data.

The high-level goal of our clustering algorithm is to:

• minimize intra-cluster distances
• maximize inter-cluster distances

Centroid and Variance¶

To measure how close or different many vectors are in space, let's define the idea of a dataset centroid.

Given a $n$ different vectors $x_1,\dots ,x_n$ each with the same dimension $d$, the centroid is the average of the vectors taken componentwise.

In other words: the centroid is the "center of mass" of the dataset.

Next, we define the sample variance of a dataset $\{x_1,\dots ,x_n\}$ as:

In other words, the sample variance of the set of points is the average squared distance from each point to the centroid.

$k$-means Problem:¶

Find $k$ points $c_1,\dots ,c_k$ (called centers, centroids, or means), so that the cost

is minimized.

Equivalently: we can think in terms of the partition itself.

Consider the set $X=\{x_1,\dots ,x_n\}$ where $x_i\in R^d$.

Find $k$ points $c_1,\dots ,c_k$

and partition the set $X$ into $k$ different subsets $\{X_1,\dots ,X_k\}$ by assigning each point $x_i$ to its nearst cluster center,

so that the cost

is minimized.

The (approximate) $k$-means algorithm:

1. Pick $k$ cluster centers $\{c_1,\dots ,c_k\}$. These can be chosen randomly, or by some other method.
2. For each $j$, define the cluster $X_j$ as the set of points in $X$ that are closest to center $c_k$.

(Nearer to $c_k$ than to any other center.) 3. For each $j$, redefine $c_j$ to be the center of mass of cluster $X_j$.
(In other words, $c_j$ is the mean of the vectors in $X_j$.) 4. Repeat (i.e., go to Step 2) until convergence.

Limitations of $k$-means¶

As you can see, $k$-means can work very well.

However, we don't have any guarantees on the performance of $k$-means.

In particular, there are various settings in which $k$-means can fail to do a good job.

1. $k$-means tries to find spherical clusters.

   Because each point is assigned to its closest center, the points in a cluster are implicitly assumed to be arranged in a sphere around the center.

2. $k$-means tries to find equal-sized clusters.

   For the same reason, the sizes of clusters are implicitly assumed to be approximately equal.

3. $k$-means is sensitive to the starting cluster centers.

   If the initial guess (Step 1) is a bad one, $k$-means may get "stuck" in a bad solution.

Evaluating $k$-means¶

We discussed two metrics to test how well $k$-means clustering has done... and as a result, to find the best $k$.

• If ground truth is known, we can use the Rand Index: a similarity measure that allows us to compare the ground truth $T$ versus the result of $k$-means clustering $C$.

  If $a$ denotes the number of pairs of points that have the same label in both $T$ and $C$, and $b$ denotes the number of pairs that have different labels in both $T$ and $C$, then the Rand Index is:

• If ground truth is not known, we can use the Silhouette Coefficient: an attempt to measure when a model produces "better defined" clusters, in the sense that points in the same cluster are close to each other and far from the other clusters.

  If $a$ equals the mean distance between a data point and all other points in the same cluster, and $b$ equals the mean distance between a data point and all other points in the next nearest cluster, then the

Silhouette Coefficient for a clustering is: $$s=\frac{b-a}{max(a,b)}$$

Hierarchical Clustering¶

A hierarchical clustering produces a set of nested clusters organized into a tree.

A hierarchical clustering is visualized using a dendrogram

• A tree-like diagram that records the containment relations among clusters.

Strengths of Hierarchical Clustering¶

Hierarchical clustering has a number of advantages:

First, a hierarchical clustering encodes many different clusterings. That is, it does not itself decide on the correct number of clusters.

A clustering is obtained by "cutting" the dendrogram at some level.

This means that you can make this crucial decision yourself, by inspecting the dendrogram.

Put another way, you can obtain any desired number of clusters.

The second advantage is that the dendrogram may itself correspond to a meaningful structure, for example, a taxonomy.

Building a dendrogram¶

Agglomerative Clustering ("bottom-up"):

• Start by defining each point as its own cluster
• At each successive step, merge the two clusters that are closest to each other (according to some rule to be determined)
• Repeat until only one cluster is left.

Divisive Clustering ("top-down"):

• Start with one, all-inclusive cluster
• At each step, find the cluster split that creates the largest distance between resulting clusters
• Repeat until each point is in its own cluster.

• Single-Linkage: the distance between two clusters is the distance between the closest two points that are in different clusters.

• Complete-Linkage: the distance between two clusters is the distance between the farthest two points that are in different clusters.

• Average-Linkage: the distance between two clusters is the average distance between all pairs of points from different clusters.

Supervised Learning¶

The supervised learning problem in general is:

• You are given some example data, which we'll think of abstractly as tuples $\left\{\right(x_i,y_i)|i=1,\dots ,N\}$.

• Your goal is to learn a rule that allows you to predict $y_j$ for some $x_j$ that is not in the example data you were given.

When our data is continuous, we call this a regression.

The class of models we looked at are polynomials. They are of the form:

where $k$ is the order of the polynomial.

Choosing $k$ is called model selection and $w_0,w_1,\dots ,w_k$ are called the parameters of the model.

If we overfit our model to our training data, this leads to poor generalizability. To avoid overfitting, we might:

1. Increase the amount of training data.

2. Limit the complexity of the model.

We can hold out data to test our model selection. For example, we might do the following:

• For each possible value of the hyperparameter $k$:
  • randomly split the data 5 times
  • compute the mean testing and training error over the 5 random splits

In cross-validation, the data is partitioned once, and then each partition is used as the test data once.

This ensures that all the data gets equal weight in the training and in the testing.

We divide the data into $k$ "folds".