Margin

Definition

The signed distance of a labeled point $(x,y)$ to the hyperplane $H_w=\{⟨w,x⟩=0\}$ is $y⟨w,x⟩/\Vert w\Vert$ (positive iff classified correctly). The margin of $w$ on the data is the smallest of these distances. Data is linearly separable if some $w$ has a positive margin.

Formula

$$\rho =\underset{i=1,\dots ,n}{\min }\frac{y_i⟨w,x_i⟩}{\Vert w\Vert }$$

Derivation: $x=h+rw/\Vert w\Vert$ with $h\in H_w$, and $⟨h,w⟩=0$ gives $r=⟨x,w⟩/\Vert w\Vert$. The margin is invariant to rescaling $w$. It controls the perceptron mistake bound $R^2/{\rho }^2$ and its $1/n$ generalization bound; margins also appear for SVMs and boosting.

Appears in

• Lecture 2, distance to a hyperplane
• Lecture 2, definition
• Lecture 2, exam-style task
• Lecture 2, non-separable case
• ρ², d+1)

Related concepts

• Perceptron