SVDD

8次阅读

共计 5068 个字符，预计需要花费 13 分钟才能阅读完成。

支持向量数据描述（Support Vector Data Description，SVDD）是一种单分类算法，该算法不是为了将不同的类别的数据区分开来，而是对某一个类别生成一个描述 description。可以理解为，在特征空间中为某一个类别划分一个区域，在区域内的样本属于该类别，在区域外的数据不属于该类别。SVDD 常用于异常检测任务或者是类别极度不平衡的分类任务。

以异常检测任务为例，假设有一组正常的样本数据集 $T=\{x^{(i)},x^{(2)},\cdots,x^{(N)}\}$，其中 N 为样本个数，$x^{(i)}\in \mathcal{x}=\mathbb{R}^d$，d 为维度。首先通过一个非线性变换将输入空间（欧式空间 $\mathbb{R}^d$ 的子集）$\mathcal{X}$ 对应到一个特征空间（希尔伯特空间）$\mathcal{H}$，即存在一个从 $\mathcal{X}$ 到 $\mathcal{H}$ 的映射 $\phi(x):\mathcal{X} \rightarrow \mathcal{H}$，然后在特征空间找到一个体积最小的超球体，为映射到特征空间中的样本划定一个区域。$\phi(x)$ 可以理解为 SVM 中的核函数，使用核函数一是因为输入空间中的数据并不会呈现球状分布，二是可以提高模型的表达能力。
写为如下带约束的最优化问题（类似于使用核函数的软间隔支持向量机），
$$\begin{equation}\begin{aligned}&\min_{a,R,\xi}R^2+C\sum_{i=1}^{N}\xi_i\\ & \begin{aligned}s.t.\quad &||\phi(x^{(i)})-a||^2\leq R^2+\xi_i,i=1,\cdots,N \\& \xi_i\geq 0,i=1,\cdots,N\end{aligned}\end{aligned}\tag{1}\end{equation}$$
其中，a 为超球体的球心，R 为超球体的半径，$\xi$ 为松弛因子，$C\geq 0$ 为惩罚参数，式 (1) 希望超球体体积小的同时，误分类的样本个数也尽量少。
式 (1) 是带约束的最优化问题，引入拉格朗日函数，
$$\begin{equation}L(a,R,\xi,\alpha,\mu)=R^2+C\sum_{i=1}^N\xi_i+\sum_{i=1}^N\alpha_i (||\phi(x^{(i)})-a||^2- R^2-\xi_i)-\sum_{i=1}^{N}\mu_i\xi_i\tag{2}\end{equation}$$
其中，$\alpha\geq 0,\mu$ 为拉格朗日乘子。考虑 $R,a,\xi$ 的函数，$\theta_p(a,R,\xi)=\max_{\alpha,\mu}L(a,R,\xi,\alpha,\mu)$，原问题式 (1) 可以写为广义拉格朗日的极小极大问题的形式，
$$\begin{equation}\min_{a,R,\xi}\theta_P(a,R,\xi)=\min_{a,R,\xi}\max_{\alpha,\mu}L(a,R,\xi,\alpha,\mu)\tag{3}\end{equation}$$

定义 $\theta_D(\alpha,\mu)=\min\limits_{a,R,\xi}L(a,R,\xi,\alpha,\mu)$，考虑广义拉格朗日的极大较小问题，
$$\begin{equation}\max_{\alpha,\mu}\min_{a,R,\xi}L(a,R,\xi,\alpha,\mu)\tag{4}\end{equation}$$
式 (4) 为原始问题（式 (1)）的对偶问题。
因为 $||\phi(x_i)-a||^2\leq R+\xi_i$ 严格可行（李航《统计学习方法》附录 C 定理 C.2），存在 $a^*,R^*,\xi^*,\alpha^*,\mu^*$，使 $a^*,R^*,\xi^*$ 使原始问题的解，$\alpha^*,\mu^*$ 使对偶问题的解，因此可以求解对偶问题来求解原始问题。
由 KKT 条件得，
$$\begin{equation}\nabla_{a}L(a^*,R^*,\xi^*,\alpha^*,\mu^*)=\sum_{i=1}^{N}\alpha_i(a^*-\phi(x^{(i)}))=0\tag{5}\end{equation}$$
$$\begin{equation}\nabla_R L=2R(1-\sum_{i=1}^{N}\alpha_i)=0\tag{6}\end{equation}$$
$$\begin{equation}\nabla_{\xi}L=C-\alpha-\mu=0\tag{7}\end{equation}$$
$$\begin{equation}\alpha_i^* (||\phi(x^{(i)})-a^*||^2- R^2-\xi_i^*)=0\tag{8}\end{equation}$$
$$\begin{equation}||\phi(x^{(i)})-a^*||^2- R^2-\xi_i^*\leq0\tag{9}\end{equation}$$
$$\begin{equation}\alpha_i^* \geq0\tag{10}\end{equation}$$
$$\begin{equation}\mu_i^*\xi_i^*=0\tag{11}\end{equation}$$
$$\begin{equation}\mu_i^*\geq0\tag{12}\end{equation}$$
$$\begin{equation}\xi_i^*\geq0\tag{13}\end{equation}$$
代入式 (4),
$$\begin{equation}\begin{aligned}&\min_{\alpha}\sum_{i=1}^{N}\sum_{j=1}^{N}\alpha_i\alpha_jK(x^{(i)},x^{(j)})-\sum_{i=1}^N\alpha_iK(x^{(i)},x^{(i)})\\&s.t.\quad 0\leq\alpha_i\leq C,\sum_{i=1}^{N}\alpha_i=1\end{aligned}\tag{14}\end{equation}$$
其中 K 为核函数，$K(x^{(i)},x^{(j)})=\phi(x^{(i)})\cdot\phi(x^{(j)})$。使用 SMO 算法或者梯度下降，得到 $\alpha^*$，则由式 (5) 得到超球体的球心 $a^*$ 为，
$$\begin{equation}a^*=\sum_{i=1}^N\alpha_i\phi(x^{(i)})\tag{15}\end{equation}$$
对于超球体的半径 $R^*$，选择 $0<\alpha_v^*<C$，由式 (7) 和(11)推出 $\xi_v=0$，由式 (8) 和(9)可推出 $R^*$。对应 $0<\alpha_v^*<C$ 的样本为支持向量。
$$\begin{equation}\begin{aligned}R^*&=\sqrt{||\phi(x^{(v)})-a^*||^2}\\&=\sqrt{K(x^{(v)},x^{(v)})-2\sum_{i=1}^N\alpha_iK(x^{(v)},x^{(i)})+\sum_{i=1}^{N}\sum_{j=1}^N\alpha_i\alpha_jK(x^{(i)},x^{(j)})}\end{aligned}\tag{16}\end{equation}$$
对于测试样本 $x^{(test}$，衡量其在特征空间中到超球体球心的距离 $d=\sqrt{||\phi(x^{(test)})-a*||^2}$，若 $d\leq R^*$，则属于正常样本，否则属于异常样本。

SVDD 还可以用于类别不平衡的分类任务，假设有数据集 $T=\{(x^{(1)},y^{(1)}),\cdots,(x^{(N)},y^{(N)})\}$，其中 $x^{(i)}\in\mathcal{X}=\mathbb{R}^n,y^{(i)}\in\mathcal{Y}=\{-1,1\}$，- 1 表示样本属于异常类别，1 表示样本属于正常类别，且正常类别的样本数远大于异常类别的样本数。对于正常样本 $x^{(i)}$，希望 $||\phi(x^{(i)})-a||^2\leq R^2+\xi_i$，对于异常类别的样本 $x^{(j)}$，希望 $||\phi(x^{(j)})-a||^2\geq R^2-\xi_j$，则式 (1) 的原始问题改写为，
$$\begin{equation}\begin{aligned}&\min_{a,R,\xi}R^2+C_1\sum_{i\in\{i|y^{(i)}=1\}}\xi_i+C_2\sum_{j\in\{j|y^{(j)}=-1\}}\xi_j\\ & \begin{aligned}s.t.\quad &||\phi(x^{(i)})-a||^2\leq R^2+\xi_i,i\in\{i|y^{(i)}=1\}\\& ||\phi(x^{(j)})-a||^2\leq R^2+\xi_j,j\in\{j|y^{(j)}=1\}\\& \xi_i\geq 0,i\in\{i|y^{(i)}=1\}\\&\xi_j\geq 0,j\in\{j|y^{(j)}=1\}\end{aligned}\end{aligned}\tag{17}\end{equation}$$
写为拉格朗日极小极大问题，
$$\begin{equation}\begin{aligned}L(a,R,\xi,\alpha,\mu)=&R^2+C_1\sum_{i=1}^NI(y^{(i)}=1)\xi_i+C_2\sum_{i=1}^NI(y^{(i)}=-1)\xi_i\\&+\sum_{i=1}^N\alpha_iy^{(i)} (||\phi(x^{(i)})-a||^2- R^2-y^{(i)}\xi_i)-\sum_{i=1}^{N}\mu_i\xi_i\end{aligned}\tag{18}\end{equation}$$
转换为对偶问题为，
$$\begin{equation}\begin{aligned}&\min_{\alpha}\sum_{i=1}^{N}\sum_{j=1}^{N}y^{(i)}y^{(j)}\alpha_i\alpha_jK(x^{(x)},x^{(j)})-\sum_{i=1}^Ny^{(i)}\alpha_iK(x^{(i)},x^{(i)})\\&\begin{aligned}s.t.\quad &0\leq\alpha_i\leq C_1,if\quad y^{(i)}=1\\&0\leq\alpha_i\leq C_2,if\quad y^{(i)}=-1\\&\sum_{i=1}^{N}y^{(i)}\alpha_i=1\end{aligned}\end{aligned}\tag{19}\end{equation}$$
使用 SMO 算法或者梯度下降，得到 $\alpha^*$
$$\begin{equation}a^*=\sum_{i=1}^Ny^{(i)}\alpha_i\phi(x^{(i)})\tag{20}\end{equation}$$
选择 $0<\alpha_v^*<C_1$ 或者 $0<\alpha_v^*<C_2$（可以令 $C_1=C_2=C$），得到 $R^*$
$$\begin{equation}\begin{aligned}R^*&=\sqrt{||\phi(x^{(v)})-a^*||^2}\\&=\sqrt{K(x^{(v)},x^{(v)})-2\sum_{i=1}^Ny^{(i)}\alpha_iK(x^{(v)},x^{(i)})+\sum_{i=1}^{N}\sum_{j=1}^Ny^{(i)}y^{(j)}\alpha_i\alpha_jK(x^{(i)},x^{(j)})}\end{aligned}\tag{21}\end{equation}$$

scikit-learn 中 sklearn.svm.OneClassSVM 不是 SVDD。

正文完