Machine Learning at U of C

This page contains a list of topics, definitions, and results from Machine Learning course at University of Chicago taught by this guy. The proof is very sketchy and given without any intuition mainly because I'm so lazy. I would appreciate all kinds of help to make the note complete.

Week 1: Introduction and OLS

The materials this week are just about the framework. We show that the problem of minimizing squared errors with respect to a distribution is the same as the problem of learning $f_{p}(x)=\mathbb {E} _{p}[y|x]$. If the examples are drawn from discrete domain, this is a classification problem, but in case of continuous domain, it's a regression problem.

After defining all necessary definitions, an example of linear regression is given as a motivation of how regression is done.

Learning problem

Given a distribution $\mathbb {P}$ on $X\times Y$. We want to learn the objective function $f_{p}(x)=\mathbb {E} _{p}[y|x]$ (with respect to the distribution :$\mathbb {P}$).

Learning Algorithms

Let Z be the set of possible samples. The learning algorithm is a function that maps a number of samples to a measurable function (denoted here by F a class of all measurable functions). Sometimes we consider a class of computable functions instead.

$A:\cup _{n=1}^{\infty }Z^{n}\rightarrow F$

Learning errors

Suppose the learning algorithm outputs h. The learning error can be measured by

$\int (y-h(x))^{2}dP$

One can prove that minimizing this quantity could be reduced to the problem of minimizing the following quantity.

$||f_{p}-h||_{l_{2}(\mathbb {P} )}^{2}=\int (f_{p}(x)-h(x))^{2}P_{x}(x)dx$

And that's the reason why we try to learn $\mathbb {E} _{p}[y|x]$

In other word, we claim that

$argmin_{h}\int (y-h(x))^{2}dP=argmin_{h}||f_{p}-h||_{l_{2}(\mathbb {P} )}^{2}$

The proof is easy.

$\int (y-h(x))^{2}dP=\int ((y-f_{p}(x))+(f_{p}(x)-h(x)))^{2})dP$

We get

$\int (y-h(x))^{2}dP=\int (y-f_{p}(x))^{2}dP+\int (f_{p}(x)-h(x))^{2}dP+2\int (y-f_{p}(x))(f_{p}(x)-h(x))dP$

Then observe that,

• The first term only depends on distribution $\mathbb {P}$
• The third term is zero

$\int \int (y-f_{p}(x))(f_{p}(x)-h(x))p(x,y)dydx=\int p(x)(f_{p}(x)-h(x))[\int (y-f_{p}(x))p(y|x)dy]dx$

Observe also that the term $\int (y-f_{p}(x))p(y|x)dy=\mathbb {E} [y-\mathbb {E} [y|x]|x]$ which is zero.

• The second term is equal to

$\int _{X}\int _{Y}(f_{p}(x)-h(x))^{2}p(x,y)dydx=\int _{X}(f_{p}(x)-h(x))^{2}\int _{Y}p(x,y)dydx=||f_{p}-h||_{l_{2}(\mathbb {P} )}^{2}$

Example 1

When the class $Y=\{-1,1\}$, i.e. classification problem, our objective $f_{p}(x)$ reduces to

$f_{p}(x)=\mathbb {E} _{p}[y|x]=Pr[y=1|x]-Pr[y=-1|x]$

One can show that the function

$h_{*}(x)=sgn\mathbb {E} _{p}[y|x]$

minimizes the loss (proof omited)

Example 2

When $Y=\mathbb {R}$, the problem is just like regression where we try to regress :$f_{p}(x)$

Learning lowerbound

Let $\mathbb {M}$ be a class of probability distribution of interest. No algorithm achieve error smaller than

$\mathbf {R} (n,\mathbb {M} )=\inf _{A}\sup _{P\in \mathbb {M} }E_{z}||f_{p}-A(z)||^{2}$

Ordinary Least Square

If the relation is linear,

$y=X\mathbf {\beta } +\mathbf {\epsilon }$

OLS provably gives the minimum squared error.

Consider the error

$||y-X\mathbf {\beta } ||^{2}=(y-X\beta )^{T}(y-X\beta )$

Differentiating the error and make it zero, we get

$(X^{T}X)\mathbf {\beta } =X^{T}\mathbf {y}$

If $(\mathbf {X} ^{T}\mathbf {X} )$ has no nullspace (or is full rank), then it has an inverse. We get

$\mathbf {\beta } =(X^{T}X)^{-1}X^{T}y$

But if the matrix $\mathbf {X} ^{T}\mathbf {X}$ is not full rank, we can still show that

$\mathbf {\beta } =(X^{T}X)^{\dagger }X^{T}y$

minimizes the error, where $(X^{T}X)^{\dagger }$ is the Moore-Penrose pseudoinverse of the matrix.

First, let $\mathbf {\lambda } _{1},\mathbf {\lambda } _{2},\ldots ,\mathbf {\lambda } _{d}$ be eigenvalues of $\mathbf {X} ^{T}\mathbf {X}$ and let $\mathbf {v} _{1},\ldots ,\mathbf {v} _{d}$ be corresponding eigenvectors.

Note that:

• Since $\mathbf {X} ^{T}\mathbf {X}$ is positive semidefinite, all eigenvalues are non-negative
• We can decompose $\mathbf {X} ^{T}\mathbf {X}$ to

$\mathbf {X} ^{T}\mathbf {X} =\sum _{i}\lambda _{i}v_{i}v_{i}^{T}$ (because $\mathbf {X} ^{T}\mathbf {X}$ is symmetric so that every eigenvector is orthogonal to others.)

Denote the column space of $\mathbf {X} ^{T}\mathbf {X}$ by ${\mathcal {W}}$. Assume WLOG that ${\mathcal {W}}=span\{v_{1},\ldots ,v_{m}\}$ and ${\mathcal {W}}^{\bot }=ker\mathbf {X} ^{T}\mathbf {X} =span\{v_{m+1},\ldots ,v_{d}\}$.

We will first show that $X^{T}\mathbf {y}$ in fact, lives in the subspace ${\mathcal {W}}$. Observe that since the set of eigenvectors span $\mathbb {R} ^{d}$, it suffices to show that it is orthogonal to every vector in ${\mathcal {W}}^{\bot }$

$\forall z\in {\mathcal {W}}^{\bot }$, $<\mathbf {X} ^{T}y,z>=0$.

Let $z\in {\mathcal {W}}^{\bot }$, that is $\mathbf {X} ^{T}\mathbf {X} z=0$. We get

$z^{T}\mathbf {X} ^{T}\mathbf {X} z=||Xz||^{2}=0$

This implies that $\mathbf {X} z=0$ and thus, $<\mathbf {X} ^{T}y,z>=0$.

From the fact that $\mathbf {X} ^{T}y$ lives in ${\mathcal {W}}$, we can verify that the following $\mathbf {\beta }$ is what we need.

$\beta =(\sum _{i=1}^{m}{\frac {1}{\lambda _{i}}}v_{i}v_{i}^{T})\mathbf {X} ^{T}y$

And it's straightforward to see that the solution for $\mathbf {\beta }$ is not unique since any $\mathbf {\beta } +e$ for $e\in ker(\mathbf {X} ^{T}\mathbf {X} )$ would also satisfy the equation.

Note that the term $\sum _{i=1}^{m}{\frac {1}{\lambda _{i}}}v_{i}v_{i}^{T}$ is a Moore-Penrose pseudoinverse of a singular matrix.

Tikhonov Regularization

Instead of solving

$\beta ^{*}=argmin_{\beta \in \mathbb {R} ^{d}}||y-\mathbf {X} ^{T}\beta ||^{2}$

we look at

$\beta ^{*}=argmin_{\beta \in \mathbb {R} ^{d}}||y-\mathbf {X} ^{T}\beta ||^{2}+\alpha ||\beta ||^{2}$

If $\mathbf {\alpha }$ tends to zero, it problem becomes just like OLS. If $\mathbf {\alpha }$ is a certain positive number, differentiating both sides give (and equate to zero)

$(\mathbf {X} ^{T}\mathbf {X} +\alpha I)\beta =\mathbf {X} ^{T}y$

$\{\mathbf {\lambda } _{i}+\alpha \}$ are eigenvalues of $\mathbf {X} ^{T}\mathbf {X} +\alpha I$, where $\{\mathbf {\lambda } _{i}\}$ are eigenvalues of $\mathbf {X} ^{T}\mathbf {X}$.

Observe that all eigenvalues are positive, so nullspace is zero. And thus, matrix on the left-hand side is invertible. The solution is unique.

Week 2: PCA, LDA, and Introduction to SVM

In this week, we cover another theme of techniques, i.e. Principle Component Analysis (PCA) and Fisher Linear discriminant analysis. As compared to last week topics which involve solving linear systems, this week topics involve solving eigenvalues & eigenvectors of matrix.

Since the theory of positive semidefinite will be crucial throughout the course, we give a quick introduction.

A quick introduction to theory of positive matrix

A matrix $\mathbf {A}$ is said to be positive semidefinite if

$w^{T}\mathbf {A} w\geq 0$ for all w

Observation: Matrix in the form $\mathbf {X} ^{T}\mathbf {X}$ is positive semidefinite.

Proof. for any w, $w^{T}X^{T}Xw=||Xw||^{2}\geq 0$

property 1: Positive semidefinite matrix has eigenvalue $\geq 0$

Proof. $\mathbf {A} \mathbf {v} =\lambda \mathbf {v} \Rightarrow v^{T}Av=\lambda v^{T}v.$

$\lambda ={\frac {v^{T}Av}{v^{T}v}}\geq 0$

(This is because $v^{T}Av$ can be thought as a generalized dot product so that it will always have non-negative value).

PCA

Given n points of data in $\mathbb {R} ^{d}$, we want to find a projection $w\in \mathbb {R} ^{d}$ which best splits these n points. The notion of 'best' is measured by variance of the projected data. Note that we can assume WLOG that $\sum _{i=1}^{n}\mathbf {x} _{i}=0$. That is, we want to maximize$\sum z_{i}^{2}$ where$z_{i}=w\cdot x_{i}=w^{T}x_{i}$.

$\sum z_{i}^{2}=\sum w^{T}x_{i}x_{i}^{T}w=w^{T}(\sum x_{i}x_{i}^{T})w,$ where $\sum x_{i}x_{i}^{T}$ is positive semidefinite.

The problem is given as follows.

$\max _{w\in \mathbb {R} ^{d}}w^{T}(\sum \mathbf {x} _{i}\mathbf {x} _{i}^{T})w$

s.t. $||\mathbf {w} ||^{2}=1$

Using Lagrange's,

$\max w^{T}\mathbf {A} w-\lambda w^{T}w$

Differentiating the above,

$2\mathbf {A} w-2\lambda w=0$

$\mathbf {A} w=\lambda w$

This tells us that the solution must be among eigenvectors $v_{i}$ of $A$.

$v_{i}^{T}Av_{i}=v_{i}^{T}\lambda _{i}v_{i}=\lambda _{i}v_{i}^{T}v_{i}=\lambda _{i}$

The solution becomes clear now, i.e. choose $\mathbf {w}$ to be the eigenvectors corresponding to the largest eigenvalue of $\mathbf {A}$.

Fischer LDA

Another method along the same line was proposed by Fischer. The idea is to find the direction which best seperates the mean of different classes, as contrasted to PCA which finds the direction in which the projected data have highest variance. Fisher's criterion is as follows: (note that we consider the task of classifications with two labels, 1 and -1)

$\max _{w\in \mathbb {R} ^{d}}{\frac {||w^{T}m_{1}-w^{T}m_{-1}||^{2}}{\sum _{i\in I_{1}}||w^{T}x_{i}-w^{T}m_{1}||^{2}+\sum _{i\in I_{-1}}||w^{T}x_{i}-w^{T}m_{-1}||^{2}}}$

where $m_{c}={\frac {1}{|I_{c}|}}\sum _{i\in I_{c}}x_{i}$

The numerator could be written as $w^{T}(m_{1}-m_{-1})(m_{1}-m_{-1})^{T}w$ which we denote the middle term by $\mathbb {S} _{B}$. Also, the denominator reduces to

$w^{T}(\sum (x_{i}-m_{1})(x_{i}-m_{1})^{T}+\sum (x_{i}-m_{2})(x_{i}-m_{2})^{T})w$

which we denote the middle term by $\Sigma$. The problem becomes

$\max _{w\in \mathbb {R} ^{d}}{\frac {w^{T}\mathbb {S} _{B}w}{w^{T}\Sigma w}}$

This is equivalent to

$\max _{w\in \mathbb {R} ^{d}}w^{T}\mathbb {S} _{B}w$

s.t. $\mathbf {w} ^{T}\Sigma \mathbf {w} =1$

Again, consider Lagrange and differentiate the formula. we get

$2\mathbb {S} _{B}w=2\lambda \Sigma w$

$\Sigma ^{-1}\mathbb {S} _{B}w=\lambda w$

This would have been done if$\Sigma ^{-1}\mathbb {S} _{B}$ is symmetric and positive semidefinite. We can use the eigenvector solutions like before. We can work it out as follows:

• Observe that $\mathbb {S} _{B}$ is a rank-one symmetric, positive semidefinite matrix (rank-one is not important, though). So, the notation $\mathbb {S} _{B}^{1/2}$ makes sense because we can consider changing to eigen basis, $\mathbb {S} _{B}=UDU^{T}$. So $\mathbb {S} _{B}^{1/2}=UD^{1/2}U^{T}$.

Replacing $\mathbb {S} _{B}^{1/2}w$ with v, we get

$\mathbb {S} _{B}^{1/2}\Sigma ^{-1}\mathbb {S} _{B}^{1/2}v=\lambda v$

And one can check that the linear map on the lefthand is symmetric, positive semidefinite. Thus, we can find eigenvector solution $v_{k}$ corresponding to $\lambda _{k}$ and compute $w_{k}=\mathbb {S} _{B}^{-1/2}v_{k}$ .

One can also verify that, plugging this solution back to the original equation, we get

${\frac {w_{k}^{T}\mathbb {S} _{B}w_{k}}{w_{k}^{T}\Sigma w_{k}}}={\frac {\lambda _{k}w_{k}^{T}\Sigma w_{k}}{w_{k}^{T}\Sigma w_{k}}}=\lambda _{k}$

So, we can maximize the objective by choosing the vector $v_{k}$ corresponding to largest eigenvalue.

Week 3: Finishing up SVM

This week, we will talk about support vector machines which involve solving quadratic programs. At the same time, we start the theory of VC dimension.

See this.

Please see chapter 10 in Vapnik's book Statistical Learning Theory for reference.

Week 4: A theory of reproducing kernels

This week, we start looking at kernel methods which will be a main focus for this quarter. The first class gives several definitions and concepts relating to reproducing kernel hilbert spaces. We talk about two constructions of r.k. Hilbert space (i.e. via a completion of linear combinations and via measure-theoretic view). These two methods (and some others in the liturature) are equivalent. Examples of the construction are given in the finite-domain case.

here

Please see the reference for more detail.

Week 5: More on kernels

The plan for this week is to talk about this paper

Useful Links

General Theory

• Wikipedia article on eigenvalue, eigenvector and eigenspace
• Wikipedia article on ordinary least square
• Wikipedia article on singular value decomposition
• Wikipedia article on principal component analysis
• Wikipedia article on Tikhonov regularization
• Reproducing kernels Hilbert spaces

Famous Applications of PCA in machine learning

• Eigenface for face recognition
  • Wikipedia article on eigenface
  • MIT introduction to eigenface