Support estimation

Estimate support of a distribution D

Find set $S^{\prime }$ such that $Pr(x\notin S^{\prime })<p\in (0,1]$, given sample $S$. Can be solved by probability density estimation techniques, but actually simpler.

Visualization: take the input space; draw solid ovals around sampled points; the algorithm will draw a dotted oval around these, which will represent the support of the distribution.

With soft margin kernel hyperplane

Aka One Class SVM or OSVM.

Given $N$ examples $\left\{x_i\right\}$; project to some feature space associated with kernel $k(x,y)=\varphi (x{)}^T\varphi (y)$; want to find hyperplane $w^T\varphi (x)-\rho$ such that all points in the support fall on one side of the hyperplane, outliers fall on the other side: support identifier $f=sgn(w^{T}x-\rho )$; so, allowing a soft margin, want to solve $\underset{\rho ,w}{max}\frac{\rho }{\parallel w\parallel }+C\sum {\xi }_i$ such that $w^T\varphi (x_i)+{\xi }_i\ge \rho ,{\xi }_i\ge 0$; $\equiv$ obj function: $\underset{w,\xi ,\rho }{min}{\parallel w\parallel }^2/2+\frac{1}{\nu N}\sum {\xi }_i-\rho$, for some coefficient $0\le \nu \le 1$.

Thence get Lagrangian: \ $L(w,\xi ,\rho ,\alpha ,\beta )={\parallel w\parallel }^2/2+\frac{1}{\nu N}\sum {\xi }_i-\rho -\sum {\alpha }_i(w^T\varphi (x_i)+{\xi }_i-\rho )-\sum {\beta }_i{\xi }_i$ with $\alpha ,\beta \ge 0$.

Set derivatives wrt primal vars $w,\xi ,\rho$ to 0 to get: $w=\sum _i{\alpha }_i\varphi (x_i);{\alpha }_i=\frac{1}{\nu N}-{\beta }_i\le \frac{1}{\nu N},\sum _i{\alpha }_i=1$. Thence, the support identifier becomes \ $f=sgn(\sum _i{\alpha }_{i}k(x_i,x)-\rho )$; dual optimization problem becomes \ $ma{x}_{\alpha }-2^{-1}\sum _{i,j}{\alpha }_i{\alpha }_{j}k(x_i,x_j)$ subject to $0\le {\alpha }_i\le (\nu N{)}^{-1},\sum _i{\alpha }_i=1$. Solving this, discover w; then recover $\rho$ using $\rho =w^T\varphi (x_i)$ for $x_i$ with ${\alpha }_i\ne 0;{\beta }_i\ne 0$ (support vector with ${\beta }_i>0$): $\mathrm{\exists }{x}_i$ as $\sum {\alpha }_i=1;{\alpha }_i\ge 0$.

Choosing kernel, tuning parameters

$\nu \propto$ softness of the margin, number of support vectors, thence the runtime, sensitivity to appearence of novelty.

With Gaussian kernel, any data set is seperable as everything is mapped to same quadrant in feature space.

\oprob How to decide width of Gaussian kernel to use? Can you use information about the abnormal class in choosing the kernel?

Comparison with thresholded Kernel Density estimator

If $\nu =1,{\alpha }_i=1/N$, support identifier $f=sgn(\sum _i{\alpha }_{i}k(x_i,x)-\rho )$ same as one using a Kernel (Parzen) Density estimator. What happens when $\nu <1$?

Comparison with using soft margin hyperspheres

For homogenous kernels, $k(x,x)$ is a constant and the dual minimization problem \ $\underset{\alpha }{min}\sum _{i,j}{\alpha }_i{\alpha }_{j}k(x_i,x_j)-\sum _i{\alpha }_{i}k(x_i,x_i)$ and the support identifier \ $f=sgn(R^2-\sum _{i,j}{\alpha }_i{\alpha }_{j}k(x_i,x_j)+2\sum _{i}k(x_i,x)-k(x,x))$ is equivalent to the minimization problem derived from the hyperplane formulation. So, all mapped patterns lie in a sphere in feature space; finding the smallest sphere containing them is equivalent to finding the segment of the sphere containing the data points, which reduces to finding the separating hyperplane.

Connection to binary classification

Hyperplane $(w,\rho =0)$ \ separates $\{(x_i,1)\}$ from $(-x_i,-1)$ with margin $\rho /\parallel w\parallel$ and vice-versa.

Using soft margin hyperspheres

Aka Support vector data description. Here one solves: $\underset{R,\xi ,c}{min}{R}^2+\frac{1}{\nu N}\sum _i{\xi }_i$ subject to ${\parallel \varphi (x_i-c)\parallel }^2-{\xi }_i\le R^2,{\xi }_i\ge 0$.

After using the Lagrangian, finding the critical points and substituting, this leads to the dual $\underset{\alpha }{min}\sum _{i,j}{\alpha }_i{\alpha }_{j}k(x_i,x_j)-\sum _i{\alpha }_{i}k(x_i,x_i)$ subject to $0\le {\alpha }_i\le \frac{1}{\nu N},\sum {\alpha }_i=1$, and the solution $c=\sum {\alpha }_i\varphi (x_i)$ corresponding to support identifier $f=sgn(R^2-\sum _{i,j}{\alpha }_i{\alpha }_{j}k(x_i,x_j)+2\sum _{i}k(x_i,x)-k(x,x))$ \chk.

Using Clustering

Cluster the sample, draw boundaries around the clusters. Eg: Use $k$ means clustering.

Novelty detection

Problem

Aka Outlier detection.

In general, we want to find outliers - unlikely data-points according to the conditional distributions $f_{X_r|X_{\mathrm{\neg }r}}$.

As One class classification

view as a problem where there are multiple classes, but all training examples are from one class only.

Motivation

Outliers are detected either to focus attention on them or to remove them from consideration.

Using density estimation

Do density estimation; call apparently improbable data points novel.

Using support of the distribution

Find distrubution support, call anything outside the support an outlier.

Ransack

One learns a model $M$ (either $f_{X_r|X_{\mathrm{\neg }r}}$ or $E[f_{X_r|X_{\mathrm{\neg }r}}]$) using data set $S$.

Then, one finds $S^{\prime }\subset S$ for which $err(M;x)\ge t\mathrm{\forall }x\in S^{\prime }$.

$S^{\prime }$ is then added to the set of outliers.

Finally, one repeats the entire procedure till the set of outliers is stable.

Boundary methods

K nearest neighbors

Estimate local density of $x$ by taking avg distance to $k$ nearest neighbors; similarly estimate local density of each neighbor; call $x$ novel if its local density is much smaller than that of the neighbors.

Support vector data description

\tbc

PCA

Simplify the data using PCA. \tbc