6.867 Machine Learning (Fall 2003)





Problem sets




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.