ผลต่างระหว่างรุ่นของ "Machine Learning at U of C"
Parinya (คุย | มีส่วนร่วม) (→Week 3) |
Jittat (คุย | มีส่วนร่วม) (revert to parinya) |
||
(ไม่แสดง 26 รุ่นระหว่างกลางโดยผู้ใช้ 16 คน) | |||
แถว 147: | แถว 147: | ||
Observe that all eigenvalues are positive, so nullspace is zero. And thus, matrix on the left-hand side is invertible. The solution is '''unique'''. | 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 == | + | == 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. | 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. | ||
แถว 232: | แถว 232: | ||
So, we can maximize the objective by choosing the vector <math>v_k</math> corresponding to largest eigenvalue. | So, we can maximize the objective by choosing the vector <math>v_k</math> corresponding to largest eigenvalue. | ||
− | == Week 3 == | + | == 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. | 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 [[Week 3 (Machine_Learning) | this]]. | See [[Week 3 (Machine_Learning) | this]]. | ||
− | == Week 4 == | + | 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. | ||
+ | |||
+ | [[Week4_Machine Learning | here]] | ||
+ | |||
+ | Please see the reference for more detail. | ||
+ | |||
+ | == Week 5: More on kernels == | ||
+ | The plan for this week is to talk about [http://people.cs.uchicago.edu/~niyogi/papersps/MinNiyYao06.pdf this paper] | ||
==Useful Links== | ==Useful Links== | ||
แถว 247: | แถว 256: | ||
* [http://en.wikipedia.org/wiki/Principal_component_analysis Wikipedia article on principal component analysis] | * [http://en.wikipedia.org/wiki/Principal_component_analysis Wikipedia article on principal component analysis] | ||
* [http://en.wikipedia.org/wiki/Tikhonov_regularization Wikipedia article on Tikhonov regularization] | * [http://en.wikipedia.org/wiki/Tikhonov_regularization Wikipedia article on Tikhonov regularization] | ||
+ | * [http://www.jstor.org/view/00029947/di963001/96p0042z/0 Reproducing kernels Hilbert spaces] | ||
+ | |||
=== Famous Applications of PCA in machine learning === | === Famous Applications of PCA in machine learning === | ||
* Eigenface for '''face recognition''' | * Eigenface for '''face recognition''' | ||
** [http://en.wikipedia.org/wiki/Eigenface Wikipedia article on eigenface] | ** [http://en.wikipedia.org/wiki/Eigenface Wikipedia article on eigenface] | ||
** [http://vismod.media.mit.edu/vismod/demos/facerec/basic.html MIT introduction to eigenface] | ** [http://vismod.media.mit.edu/vismod/demos/facerec/basic.html MIT introduction to eigenface] |
รุ่นแก้ไขปัจจุบันเมื่อ 09:00, 9 กันยายน 2550
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 . 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 on . We want to learn the objective function (with respect to the distribution :).
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.
Learning errors
Suppose the learning algorithm outputs h. The learning error can be measured by
One can prove that minimizing this quantity could be reduced to the problem of minimizing the following quantity.
And that's the reason why we try to learn
In other word, we claim that
The proof is easy.
We get
Then observe that,
- The first term only depends on distribution
- The third term is zero
Observe also that the term which is zero.
- The second term is equal to
Example 1
When the class , i.e. classification problem, our objective reduces to
One can show that the function
minimizes the loss (proof omited)
Example 2
When , the problem is just like regression where we try to regress :
Learning lowerbound
Let be a class of probability distribution of interest. No algorithm achieve error smaller than
Ordinary Least Square
If the relation is linear,
OLS provably gives the minimum squared error.
Consider the error
Differentiating the error and make it zero, we get
If has no nullspace (or is full rank), then it has an inverse. We get
But if the matrix is not full rank, we can still show that
minimizes the error, where is the Moore-Penrose pseudoinverse of the matrix.
First, let be eigenvalues of and let be corresponding eigenvectors.
Note that:
- Since is positive semidefinite, all eigenvalues are non-negative
- We can decompose to
- (because is symmetric so that every eigenvector is orthogonal to others.)
Denote the column space of by . Assume WLOG that and .
We will first show that in fact, lives in the subspace . Observe that since the set of eigenvectors span , it suffices to show that it is orthogonal to every vector in
- , .
Let , that is . We get
This implies that and thus, .
From the fact that lives in , we can verify that the following is what we need.
And it's straightforward to see that the solution for is not unique since any for would also satisfy the equation.
Note that the term is a Moore-Penrose pseudoinverse of a singular matrix.
Tikhonov Regularization
Instead of solving
we look at
If tends to zero, it problem becomes just like OLS. If is a certain positive number, differentiating both sides give (and equate to zero)
are eigenvalues of , where are eigenvalues of .
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 is said to be positive semidefinite if
- for all w
Observation: Matrix in the form is positive semidefinite.
Proof. for any w,
property 1: Positive semidefinite matrix has eigenvalue
Proof.
(This is because can be thought as a generalized dot product so that it will always have non-negative value).
PCA
Given n points of data in , we want to find a projection 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 . That is, we want to maximize where.
- where is positive semidefinite.
The problem is given as follows.
-
- s.t.
Using Lagrange's,
Differentiating the above,
This tells us that the solution must be among eigenvectors of .
The solution becomes clear now, i.e. choose to be the eigenvectors corresponding to the largest eigenvalue of .
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)
where
The numerator could be written as which we denote the middle term by . Also, the denominator reduces to
which we denote the middle term by . The problem becomes
This is equivalent to
- s.t.
Again, consider Lagrange and differentiate the formula. we get
This would have been done if is symmetric and positive semidefinite. We can use the eigenvector solutions like before. We can work it out as follows:
- Observe that is a rank-one symmetric, positive semidefinite matrix (rank-one is not important, though). So, the notation makes sense because we can consider changing to eigen basis, . So .
Replacing with v, we get
And one can check that the linear map on the lefthand is symmetric, positive semidefinite. Thus, we can find eigenvector solution corresponding to and compute .
One can also verify that, plugging this solution back to the original equation, we get
So, we can maximize the objective by choosing the vector 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.
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