Task 7
  1. Express the distance of the image of a point \(\mathbf{x}\) from the centre of mass of a set of examples
    \[
    S = \{\mathbf{x}_1, \ldots, \mathbf{x}_m\}
    \]
    in a feature space defined by kernel \(\kappa(\mathbf{x}, \mathbf{z}) = \langle \phi(\mathbf{x}), \phi(\mathbf{z})\rangle\) in terms of kernel evaluations.

[2 Marks]

  1. Using the result from item 1. give pseudocode for the novelty detection algorithm that labels a test point novel if it lies outside the smallest sphere centred at the centre of mass that contains all of the training data.

[3 Marks]

  1. Show that if we remove one point \(\mathbf{x}_j\) from \(S\), the centre of mass moves away from \(\phi(\mathbf{x}_j)\) on the line from \(\phi(\mathbf{x}_j)\) through the centre of mass by \(\frac{1}{m-1}\) times the distance between them.

[3 Marks]

  1. Hence or otherwise show that the novelty detection method  using the same centre as in item 2. above but increasing the radius of the sphere by \(\frac{m}{m-2}\) ensures that the leave one out error (an error occurs if the left out point is not inside the sphere) on the training set is at most 1.

[5 Marks]

[Total 13 marks]