With fully labelled data

Goals and formulations are presented elsewhere.

Binary classification

See the many hypothesis classes/ parametrized model families in the colt ref, boolean functions ref.

Non parametric methods

k nearest neighbors

A discriminative, non parametric approach. Number of examples: N. Samples: $S = (x_{1}, . . x_{N})$ . There are $k$ classes. To classify $x$ , find $k$ nearest neighbors in S; take their majority vote.

So, can’t ever throw away data points.

Linear models for discrete classification

Linear separability of data sets or feature space: Decision surfaces are (p-1) dim hyperplanes in feature space.

$h (x, w) = f (w^{T} x + w_{0}) = f (v^{T} x^{'})$ with $x^{'} = (x, 1)$ : $f$ is activation function or link function; $w$ is the weight vector; $w_{0}$ is the bias. So without loss of generality, we can restrict ourselves to considering only hyperplanes passing through the origin.

Decision surfaces are h(x, v) = constant or $v^{T} x^{'}$ = constant, so linear in $x$ ; Not linear in terms of $w$ due to possible non linearity of $f$ : so called generalized linear model.

For binary classification, this becomes a halfspace: see boolean function ref and colt ref.

For geometric properties of separating hyperplane, see boolean function ref.

Arbitrary separator from fully separable training set

When the training set is fully separable, one can pick one of the many separating hyperplane easily, for example, using linear programming. For other such algorithms, see computational learning theory ref.

To select the best among the candidate hyperplanes, one can use some sort of regularization, as in maximum margin classifiers.

Winnow: multiplicative update

Let weight of $c$ be $W$ . Set weights $a_{i} = 1$ . Multiplicative update rule: if $x_{i}$ agrees with c(x), set $a_{i} = a_{i} (1 + δ)$ ; set $a_{i} = a_{i} / (1 + δ)$ for others. $m b = O (W^{2} \log n)$ . \why Sometimes better than additive update rule used in the perceptron algorithm.

This is very similar to the ‘panel of experts’ algorithm. Also see note in the section on perceptron algorithm comparing this with the ‘panel of experts’ algorithm.

Perceptron learning alg for halfspaces

The problem

The classifier: A hyperplane c through origin perfectly classifies labeled data; unit vector $u ⊥ c$ defines c; $c (x_{i}) = s g n (⟨ u, x_{i} ⟩)$ .

The data: $x \in R^{n}$ ; $∥ x_{i} ∥ = 1$ ; $S = {x_{i}}$ . Geometric margin of X wrt u: $g = min_{x \in S} | ⟨ u, x ⟩ |$ ; or $s g n (⟨ u, x_{i} ⟩) ⟨ u, x_{i} ⟩ \geq g$ . Note: g = function(S).

Want to find $c$ .

The algorithm

$u_{0} = 0$ . Additive update rule: If mistake on $x_{i}$ : $u_{i + 1} = u_{i} + s g n (⟨ u, x_{i} ⟩) x_{i}$ : hyperplane orientation tilted towards correcting the mistake.

Convergence to u

$m b = O (g^{- 2})$ . In general, if $∥ x_{i} ∥ \leq R$ ; $m b = O ((\frac{R}{g})^{2})$ .

By induction, using update rule expression for $u_{t}$ : $∥ u_{t} ∥ = ∥ u_{t} ∥ ∥ u ∥ \geq ⟨ u, u_{t} ⟩ \geq t g$ . So, if the length of $u_{t}$ is not increasing too much, may be perceptron is getting closer to u as more mistakes made.

Also, by induction, the update rule and the fact that $u_{t - 1}$ misclassified $x_{t - 1}$ , causing the update: ${∥ u_{t} ∥}^{2} \leq t$ .

So, $(t g)^{2} \leq t$ ; and $t \leq g^{- 2}$ .

Comparison

Perceptron Algorithm is usually faster than than LP. Is exponential when $g \leq 2^{- c}$ : this is rare.

For a given $g$ , we can find good enough halfspace with mb $O ((\frac{R + D}{g})^{2})$ . \chk Perhaps the winnow algorithm, which uses multiplicative update is more efficient.

Has connection to halfspace learning with noise. \why

Assumes that the data is perfectly separable. So, often less preferable than soft margin SVM’s. But, a soft margin variant of perceptron algorithm is known.

With panel of experts algorithm

Compare the perceptron algorithm $B$ with the algorithm $A$ described in the learning theory survey, which for any given sequence of inputs, using a panel of experts achieves a mistake bound comparable with the mistake bound achieved by the best expert. In the case of halfspaces, every input bit $x_{i}$ can be viewed as an ’expert’.

Upon making a mistake, $A$ updates the weight of only the experts which made a mistake, whereas $B$ updates weight assigned to every expert.

The weights used in $A$ were all positive, whereas weights used in $B$ can be negative: but this distinction is minor, as it can perhaps be accounted for in the ’experts algorithm’ by introducing experts corresponding to $- x_{i}$ .

Maximum margin classifier

The problem

A discriminative, parametric approach. Number of examples: N. Samples: $(x_{1}, . . x_{N})$ , label function $c : X \to {\pm 1}$ .

Suppose $y (x) = w^{T} ϕ (x) + w_{0}$ with $y (x) c (x) > 0 \forall x$ , for some $w, w_{0}, ϕ$ . So finding a separating hyperplane (see halfspaces in boolean function ref) in some feature space.

Hard margin

Primal

To maximize margin, solve: $max_{w, w_{0}} [\frac{min_{n} [y (x_{n}) c (x_{n})]}{∥ w ∥}]$ . Scale w, $w_{0}$ so that $min_{n} [y (x_{n}) c (x_{n})] = 1$ ; thence get $\equiv$ problem $min_{w, w_{0}} \frac{{∥ w ∥}^{2}}{2}$ : $y (x_{n}) c (x_{n}) \geq 1$ . Prediction: sgn(y(x)).

Can solve using Quadratic programming (QP).

Dual

Get Lagrangian $L (w, w_{0}, a) = \frac{{∥ w ∥}^{2}}{2} + \sum a_{n} [1 - (w^{T} ϕ (x_{n}) + w_{0}) c (x_{n})]$ ; $a_{n} \geq 0$ . Get dual: $g (a) = inf_{w, w_{0}} L (w, w_{0}, a)$ ; Set $\nabla_{w, w_{0}} L (w, w_{0}, a) = 0$ : $w = \sum_{n} a_{n} c (x_{n}) ϕ (x_{n}); 0 = \sum a_{n} c (x_{n})$ . So, dual problem: $max_{a} g (a) = max \sum a_{n} - 2^{- 1} \sum_{n} \sum_{m} a_{n} a_{m} c (x_{n}) c (x_{m}) k (x_{n}, x_{m})$ : $a_{n} \geq 0; \sum a_{n} c (x_{n}) = 0$ .

Can solve using QP too. This form is useful where $d i m (ϕ (x)) » N$ .

KKT conditions

Primal feasible: $y (x_{n}) c (x_{n}) \geq 1$ . Dual feasible: $a_{n} \geq 0; \sum a_{n} c (x_{n}) = 0$ . Complementary slackness: $a_{n} [1 - c (x_{n}) y (x_{n})] = 0$ .

So, $\forall n : a_{n} = 0 \lor c (x_{n}) y (x_{n}) = 1$ : in latter case, you have support vectors. So, aka Support Vector Machine (SVM). Take S: number of support vectors.

Predictor

Substituting for w, get: $y (x) = \sum_{n} a_{n} c (x_{n}) k (x_{n}, x) + w_{0}$ : only S terms actually appear with $a_{n} \neq 0$ : so SVM is fast to evaluate. So, $w_{0} = \frac{\sum_{m} [c (x_{m}) y (x_{m}) - \sum_{n} a_{n} k (x_{n}, x_{m})]}{N}$ .

Soft margins

Allow some points to be misclassified or to be below the margin, but linearly penalize such outliers.

Primal

So, use slack variables: $ξ_{n} \geq 0$ ; Instead of $y (x_{n}) c (x_{n}) \geq 1$ , use constraint $y (x_{n}) c (x_{n}) + ξ_{n} \geq 1$ .

$min C \sum_{n = 1}^{N} ξ_{n} + \frac{{∥ w ∥}^{2}}{2}$ : $C$ is tradeoff between penalty on $ξ$ and margin; saying $\sum ξ_{i} \leq G$ ; so controls model complexity. As $C \to \infty$ , get hard margin SVM.

Dual

Lagrangian: $L (w, w_{0}, ξ, a, m) = \frac{{∥ w ∥}^{2}}{2} + C \sum_{n = 1}^{N} ξ_{n} + \sum a_{n} (1 - c (x_{n}) y (x_{n}) - ξ_{n}) + \sum μ_{n} ξ_{n}$ : $a \geq 0, μ \geq 0$ . Set $\nabla_{w, w_{0}, ξ}$ L $= 0$ : $w = \sum a_{n} c (x_{n}) ϕ (x_{n}), \sum a_{n} c (x_{n}) = 0, a_{n} =$ C $- μ_{n}$ . Thence get dual g(a), with objective function same as hard-margin case with constraints: $0 \leq a_{n} \leq C$ : as $μ_{n} \geq 0; \sum a_{n} c (x_{n}) = 0$ .

KKT conditions

Primal feasible: $1 - c (x_{n}) y (x_{n}) - ξ_{n} \leq 0$ . Dual feasible: $a_{n} \geq 0, μ_{n} \geq 0$ . Complimentary slackness: $a_{n} (1 - c (x_{n}) y (x_{n}) - ξ_{n}) = 0, μ_{n} ξ_{n} = 0$ .

So, support vectors now are points on or within certain margin from hyperplane. Predictor same as hard margin case.