6.867 Machine Learning (Fall 2003)
Home
Syllabus
Lectures
Projects
Problem sets
Exams
References
Matlab
Fall 2002
Fall 2001
Problem set 3: errata
Wednesday 10/22 2pm, edited for clarity (new versions available).
For (1-1), (1-2), and (1-3) note that a valid kernel function is always symmetric. So for any finite number of points, the resulting kernel matrix with elements K_{ij} is also symmetric: K_{ij}= K_{ji}. You were not asked to show this, but it is fine to use it.
Problems with training SVMs: for numerical reasons the kernel matrix may have very small negative eigenvalues (all should be non-negative in principle). This causes problems with MATLAB's quadprog. There are two possible solutions (also indicated in the email):
Add the line 'K = K + (1e-10)*eye(n);' to svm_build.m after the evaluation of the kernel matrix. This makes sure that the eigenvalues are positive. The current version of 'svm_build.m' sceleton has this fix.
Impose an upper bound value on the alpha's. This can be done with inequality constraints of the same type as described in the problem set or using a special option for such constraints (see 'help quadprog' for details).
You might find it helpful to use a looser criterion for selecting support vectors in 'svm_build.m'. The current selection 'S = find(alpha > eps);' relies on MATLAB's very small constant 'eps' and may therefore select too many support vectors. Setting 'eps = (1e-4)*max(alpha);', for example, is likely to result in a more reasonable (smaller) set of support vectors.
There was a bug in 'Kr.m'. While it generated a valid kernel, it wasn't the radial basis kernel. The new version is available. If you have not already completed the problem set, please use the new version.