Charta is on Google Play: practise on the go. Get the app
Charta

Describe the underlying intuition and the working steps of two classification methods, K nearest neighbors and support vector machines.

FRM® Part I · Quantitative Analysis · Machine Learning and Prediction · FRM1.QA.15.g

The idea

K nearest neighbors is a lazy method, because nothing is trained. To classify a new case, compute its distance, usually Euclidean, to every training case, find the K closest and assign the majority class among them. Features should be standardised, because a variable measured in large units dominates the distance. Small K gives a flexible, noisy boundary with high variance, while large K gives a smoother boundary with higher bias. K is chosen by cross-validation. A support vector machine seeks the hyperplane w·x + b = 0 that separates the classes with the largest margin. Only the points on or inside the margin, the support vectors, determine it. Distance = |w·x + b| ÷ ‖w‖. This is the distance from a point to the hyperplane. Margin = 2 ÷ ‖w‖. A soft margin allows some violations at a cost C, where a large C fits the training data closely. A kernel handles non-linear boundaries.

Formulas

Distance from a point to an SVM hyperplane

distance = |w · x + b| ÷ ‖w‖

w
the weight vector of the hyperplane
x
the point
b
the intercept of the hyperplane

Divide by the length of w, not by w's components. The margin width between the two margin lines is 2 ÷ ‖w‖.

A practice question

From the question bank, with the reason each wrong option is wrong.

To classify a new borrower, the K nearest neighbors method:

  1. fits a separating hyperplane and assigns the class on the side where the borrower falls.Why not: Describes a linear classifier such as an SVM, not a neighbour vote.
  2. estimates coefficients by minimising squared error and applies them to the borrower.Why not: Describes regression, which needs a training step that KNN does not have.
  3. passes the borrower through a sequence of threshold questions down to a leaf.Why not: Describes a decision tree.
  4. finds the K training observations closest in feature space and assigns the majority class among them. - correct

KNN stores the data, measures distance, and votes among the K nearest points.

A harder one

For a new borrower, the six nearest training borrowers, in order of increasing distance, are: Default, Non-default, Non-default, Default, Default, Non-default. The KNN classification with K = 3 and with K = 5 is, respectively:

  1. Non-default, then Default. - correct
  2. Default, then Non-default.Why not: Swaps the two votes: K = 3 is Non-default (2 of 3) and K = 5 is Default (3 of 5).
  3. Default, then Default.Why not: Uses only the single nearest neighbour for the K = 3 vote.
  4. Non-default, then Non-default.Why not: Keeps the K = 3 result for K = 5, ignoring the fourth and fifth neighbours.

K = 3: two Non-default out of three gives Non-default. K = 5: three Default out of five gives Default. Results change with K.

The hardest tier

A trained linear SVM has the decision function f(x) = 2 x1 - 1 x2 - 3, with the hyperplane at f(x) = 0 and the margins at f(x) = +1 and -1. The geometric distance from the point (4, 1) to the hyperplane is closest to:

  1. 4.00Why not: Reports the functional value |f(x)| without dividing by the norm of w.
  2. 0.80Why not: Divides by the squared norm of w (5) instead of its square root.
  3. 1.79 - correct
  4. 1.33Why not: Divides by the sum of the absolute weights (3) instead of the Euclidean norm.

f(4, 1) = 8 - 1 - 3 = 4. ||w|| = sqrt(2² + 1²) = 2.236. Distance = 4/2.236 = 1.79.

In the app: 6 practice questions on this outcome, spaced review that brings it back before you forget it.

Start free →

More in Machine Learning and Prediction