One-Class SVM & SVDD
03_6 : Anomaly Detection : Auto-Encoder, 1-SVM, SVDD
MoG와 같은 밀도기반 방법론들은 특정 객체가 정상범주에 속할 확률을 구했다. 반면 Support vector 기반 방법론들은 normal과 abnormal을 구분하는 분류경계면을 찾는다. 이번 글에서는 Support vector 기반의 Anomaly detection 방법 중 one-class SVM과 SVDD를 알아보자.
One-class Support Vector Machine (1-SVM, OCSVM)
1-SVM의 목표는 Data를 feature space로 mapping 한 뒤, 분류경계면을 통해 mapping된 Data 중 normal data들이 원점으로부터 최대한 멀어지게 만드는 것이다.
위 그림에서 파란색 분류경계면이 (+1) normal data들을 구분하는 것을 확인할 수 있다. 이 목표를 수식화 한 Optimization problem부터 살펴보자.
- Optimization Problem
$$\min_{\textbf{w}}\;\;\;\frac{1}{2}||\textbf{w}||^2 + \frac{1}{\nu l} \sum_{i=1}^l \xi_i - \rho$$
$$s.t.\;\;\;\textbf{w}\cdot \Phi (x_i) \geq \rho - \xi_i\;\;\;\;(i=1,2,\cdots,l),\;\;\xi_i\geq 0$$
$\frac{1}{2}||\textbf{w}||^2$ term은 SVR과 같이 $x$의 변화에 따른 변동이 크지 않도록 Regularization을 하는 term이다.
$\rho$는 위 그림에서 주황 직선을 나타내는데, 원점과 분류경계면 Hyperplane과의 거리를 나타낸다. 이 값을 뺌으로써 최소화 문제를 만족하는 최적해일때 $\rho$가 최대가 되도록 한다. (원점에서 Hyperplane이 최대한 멀어지게 만든다)
$\frac{1}{\nu l} \sum_{i=1}^l \xi_i$ term은 제약식에 따라 Hyperplane보다 안쪽의 normal 객체들에게 부여되는 페널티 $x_i$의 합이다. 이 term에서 주목할 점은 $\frac{1}{\nu l}$이다. 이 부분은 이전에 보았던 C-SVM에서 $C\sum_{i=1}^l \xi_i$ term의 $C$와 동일하게, 페널티의 정도를 조절한다.
우선 $l$은 normal data의 개수이고, $\nu$는 $0\leq \nu \leq 1$값을 가지는 Hyperparameter이다. C-SVM과 다르게, $\nu$의 값에 따라서 1-SVM이 어떻게 동작할지 정량적인 예상이 가능하다. 이 부분은 뒤에서 자세히 설명하겠다.
제약식을 살펴보면 $\Phi$가 있는데 이는 original data를 feature space로 mapping하는 함수이다 이후에 Kernel trick을 사용하여 더 쉽게 계산한다.
- Decision function
$$f(x_i) = sign(\textbf{w}\cdot \Phi (x_i)-\rho )$$
최적화 문제를 풀어서 분류경계면을 찾았다면, 위 식을 통해 분류경계면 보다 위쪽이면 normal(+1) 아래쪽이라면 abnormal(-1)로 분류한다.
이제 라그랑주 승수법을 사용해 최적화 문제를 풀어보자.
- Primal Lagrangian problem (Minimize)
$$L = \frac{1}{2}||\textbf{w}||^2 + \frac{1}{\nu l} \sum_{i=1}^l \xi_i - \rho - \sum_{i=1}^l \alpha_i (\textbf{w}\cdot \Phi (x_i) - \rho + \xi_i) - \sum_{i=1}^l \beta_i \xi_i$$
이전까지 했었던 방법과 크게 다르지 않다. 이제 KKT condition에 따라 미지수 $\textbf{w},\xi_i,\rho$로 미분한 값이 0임을 이용하자.
$$\frac{\partial L}{\partial \textbf{w}} = \textbf{w} - \sum_{i=1}^l \alpha_i \Phi(x_i) = 0\;\;\;\;\Rightarrow\;\;\;\; \textbf{w} = \sum_{i=1}^l \alpha_i \Phi(x_i)$$
$$\frac{\partial L}{\partial \xi_i} = \frac{1}{\nu l} - \alpha_i-\beta_i = 0\;\;\;\;\Rightarrow\;\;\;\; \alpha_i = \frac{1}{\nu l} - \beta_i $$
$$\frac{\partial L}{\partial \rho} = -1 + \sum_{i=1}^l \alpha_i = 0\;\;\;\;\Rightarrow\;\;\;\; \sum_{i=1}^l \alpha_i = 1$$
이제 $\textbf{w} = \sum_{i=1}^l \alpha_i \Phi(x_i)$를 대입하여 Dual 문제로 바꾸자.
- Dual Lagrangian problem (Maximize)
$$\begin{align*}L = &\frac{1}{2} \sum_{i=1}^l\sum_{j=1}^l \alpha_i \alpha_j \Phi(x_i)\Phi(x_j) + \frac{1}{\nu l} \sum_{i=1}^l \xi_i - \rho\\&- \sum_{i=1}^l\sum_{j=1}^l \alpha_i \alpha_j \Phi(x_i)\Phi(x_j) + \rho \sum_{i=1}^l \alpha_i - \sum_{i=1}^l \alpha_i \xi_i - \sum_{i=1}^l \beta_i \xi_i \end{align*}$$
식을 정리해보면,
$$L =-\frac{1}{2} \sum_{i=1}^l\sum_{j=1}^l \alpha_i \alpha_j \Phi(x_i)\Phi(x_j) + \bigg( \rho \sum_{i=1}^l \alpha_i -\rho \bigg) + \sum_{i=1}^l\big(\frac{1}{\nu l} - \alpha_i-\beta_i\big) \xi_i $$
위에서 구한 조건 $(\sum_{i=1}^l \alpha_i = 1)$과 $(\frac{1}{\nu l} - \alpha_i-\beta_i = 0)$를 사용하여 식을 항을 제거하면,
$$L =-\frac{1}{2} \sum_{i=1}^l\sum_{j=1}^l \alpha_i \alpha_j \Phi(x_i)\Phi(x_j)$$
이 된다. $L$에 대한 최대화 문제는 $L^\prime = -L$ 일때 $L^\prime$의 최소화 문제로 바꿀 수 있다.
정리하면, ($L^\prime$을 그냥 $L$이라 썼다)
$$min\;\;L =\frac{1}{2} \sum_{i=1}^l\sum_{j=1}^l \alpha_i \alpha_j \Phi(x_i)\Phi(x_j)$$
$$s.t.\;\;\;\;\sum_{i=1}^l \alpha_i = 1,\;\;\;0\leq \alpha_i \leq \frac{1}{\nu l}$$
제약조건 중 $\alpha_i \leq \frac{1}{\nu l}$ 부분은 $(\frac{1}{\nu l} - \alpha_i-\beta_i = 0)$ 조건에 따라 $\beta_i =0$인 경우 $\alpha_i = \frac{1}{\nu l}$이 최대값이다.
이제 Kernel trick을 사용하여 mapping 함수 $\Phi$ 부분인 $\Phi(x_i)\Phi(x_j)$는 $K(x_i,x_j)$로 치환된다.
$$min\;\;L =\frac{1}{2} \sum_{i=1}^l\sum_{j=1}^l \alpha_i \alpha_j K(x_i,x_j)$$
$$s.t.\;\;\;\;\sum_{i=1}^l \alpha_i = 1,\;\;\;0\leq \alpha_i \leq \frac{1}{\nu l}$$
One-class Support Vector Machine (1-SVM, OCSVM) (Cont.)
우리는 제약조건 $(\sum_{i=1}^l \alpha_i = 1)$, $(0\leq \alpha_i \leq \frac{1}{\nu l})$과 라그랑주 승수법에 따른 조건 $(\beta_i\xi_i = 0)$ 그리고 KKT condition에 따른 관계식 $(\alpha_i + \beta_i = \frac{1}{\nu l})$을 알고있다.
이를 이용하여 $\alpha_i$ 값에 따라서 각 객체가 어떤 의미를 가지는지 분석해보자.
- Case 1 : $\alpha_i = 0$ $\Rightarrow$ Non-support vector
$\alpha_i = 0$인 경우 조건 $(\alpha_i + \beta_i = \frac{1}{\nu l})$에 따라 $\beta_i = \frac{1}{\nu l} \neq 0$이다. 따라서 $\xi_i = 0$이어야 한다. $\alpha_i = 0$이고 $\xi_i = 0$으로 $L$에 아무런 영향을 주지 않는다. 이 경우 non-support vector로써 위 그림에서 하얀색 점들이다.
- Case 2 : $\alpha_i = \frac{1}{\nu l}$ $\Rightarrow$ Support vector (outside the Hyperplane)
$\alpha_i = \frac{1}{\nu l}$인 경우, $(\alpha_i + \beta_i = \frac{1}{\nu l})$에 따라 $\beta_i = 0$이다. $(\beta_i\xi_i = 0)$에서 라그랑주 승수와 제약식 둘다 0이면 안되기 때문에 $\xi_i > 0$이어야 한다. 이 경우 페널티를 받는 경계분류면 밖에 있는 support vector이다. 위 그림에서 검은색 점들이다.
- Case 3 : $0<\alpha_i<\frac{1}{\nu l}$ $\Rightarrow$ Support vector (on the Hyperplane)
$0<\alpha_i<\frac{1}{\nu l}$인 경우, $(\alpha_i + \beta_i = \frac{1}{\nu l})$에 따라 $\beta_i > 0$이다. $(\beta_i\xi_i = 0)$ 조건에 의해 $\xi_i = 0$이어야 한다. 이 경우 페널티를 받지 않으면서 $L$에 영향을 주는 분류경계면 위의 support vector이다. 위 그림에서 파란색 분류경계면 위 회색 점들이다.
The role of $\nu$
이제 아까 위에서 나중에 설명하겠다고 했던 $\nu$의 역할에 대하여 알아보자.
주어진 제약조건 $(\sum_{i=1}^l \alpha_i = 1)$, $(0\leq \alpha_i \leq \frac{1}{\nu l})$을 보면, $\alpha_i$의 최대값이 $\frac{1}{\nu l}$임으로 제야조건 $(\sum_{i=1}^l \alpha_i = 1)$를 만족하기 위해서 최소한 $\nu l$ 개의 $\alpha_i$가 최대값인 원소가 있어야 한다.
원소의 개수 $l=1000$이고 $\nu = 0.1$인 경우에 예시로 들어보자.
이때 $\alpha_i$의 최대값은 $\frac{1}{\nu l} = \frac{1}{100}$이다. 따라서 $(\sum_{i=1}^l \alpha_i = 1)$을 만족하기 위해, 최소한 100개의 $\alpha_i$가 최대값인 원소가 있어야 한다는 뜻이다. (만약 $\alpha_i$가 최대값이 아니라면 더 많이 필요할 것이다)
이러한 이해를 통해 2개의 정리를 도출할 수 있다.
- At least $\nu l$ support vectors exist
Support vector는 $\alpha_i > 0$인 원소들이다. 따라서 최소한 $\nu l$개의 support vector를 가진다는 것을 보장할 수 있다.
- At most $\nu l$ support vectors can be located outside the hyperplane
$\alpha_i = \frac{1}{\nu l}$인 경우, $\xi_i > 0$인 Hyperplane 밖에 위치하는 support vector들이다. 모든 $\alpha_i$가 최대값($\frac{1}{\nu l}$)인 경우 많아야 $\nu l$개의 support vector만이 분류경계면 밖에 존재할 수 있다.
요약하면,
$\nu$ is the lower bound for the fraction of support vectors and the upper bound for the fraction of errors
다시말해, support vector의 개수의 lower bound와 페널티를 받는 support vector의 개수의 upper bound를 $\nu$통해 조절할 수 있다.
Example 1 : $\nu = 0.1$
전체 데이터 중 10% 이상은 support vector이고, 페널티가 부여되는 support vector의 최대 비율은 10%이다.
Example 2 : $\nu = 0.9$
전체 데이터 중 90% 이상은 support vector이고, 페널티가 부여되는 support vector의 최대 비율은 90%이다.
의미상으로 $\nu$가 작을수록 Generalization이 되고, $\nu$가 클수록 Specialization이 된다.
C-SVM의 $C$와 다르게 $\nu$를 사용하면 결과를 직관적으로 예측 가능하다는 장점이 있다.
Support Vector Data Description (SVDD)
SVDD의 목표는 Data를 feature space로 mapping 한 뒤, normal data들의 영역을 포함할 수 있는 가장 작은 초구(Hypersphere)를 찾는 것이다.
- Optimization problem
$$\min_{R,\textbf{a},\xi_i}\;\;\; R^2 + C \sum_{i=1}^l \xi_i $$
$$s.t.\;\;\;||\Phi(x_i) - \textbf{a}||^2 \leq R^2 + \xi_i,\;\;\;\xi_i \geq 0,\;\;\;\forall i$$
$R^2$은 Hypersphere의 크기를 최소화 하려는 term이다. 그리고 $C \sum_{i=1}^l \xi_i$ term을 통해 Hyperplane 밖으로 벗어나는 객체들에게 페널티를 부여한다.
여기서도 제약식에 $\Phi$가 있는데 original data를 feature space로 mapping하는 함수이다 이후 Kernel trick을 사용하여 더 쉽게 계산한다.
- Decision function
$$f(x) = sign(R^2 - ||\Phi(x) - \textbf{a}||^2)$$
객체 $x$에 대하여 $sign$함수 안의 계산식이 양수라면 초구의 안에 있다는 뜻으로 normal(+1)로 판별할 것이고, 계산식이 음수라면 초구의 밖에 있다는 뜻으로 abnormal(-1)로 판별할 것이다.
이제 라그랑주 승수법을 사용해 최적화 문제를 풀어보자.
- Primal Lagrangian problem (Minimize)
$$\begin{align*}L &= R^2 + C \sum_{i=1}^l \xi_i - \sum_{i=1}^l \alpha_i \big(R^2 + \xi_i - ||\Phi(x_i) - \textbf{a}||^2 \big) - \sum_{i=1}^l \beta_i \xi_i \\ &= R^2 + C \sum_{i=1}^l \xi_i - \sum_{i=1}^l \alpha_i \big(R^2 + \xi_i - (\Phi(x_i)\cdot \Phi(x_i) - 2\textbf{a}\cdot \Phi(x_i) + \textbf{a} \cdot \textbf{a}) \big) - \sum_{i=1}^l \beta_i \xi_i\end{align*}$$
$$\alpha_i \geq 0,\;\;\;\beta_i \geq 0$$
이제 KKT condition에 따라 미지수 $R,\textbf{a},\xi_i$로 미분한 값이 0임을 이용하자.
$$\frac{\partial L}{\partial R} = 2R - 2R\sum_{i=1}^l \alpha_i = 0\;\;\;\;\Rightarrow\;\;\;\; \sum_{i=1}^l \alpha_i = 1$$
$$\frac{\partial L}{\partial \textbf{a}} = 2\sum_{i=1}^l \alpha_i \cdot \Phi(x_i) - 2\textbf{a} \sum_{i=1}^l \alpha_i= 0\;\;\;\;\Rightarrow\;\;\;\; \textbf{a} = \sum_{i=1}^l \alpha_i \cdot \Phi(x_i)$$
$$\frac{\partial L}{\partial \xi_i} = C-\alpha_i - \beta_i = 0\;\;\;\;\forall i$$이제 $\textbf{a} = \sum_{i=1}^l \alpha_i \cdot \Phi(x_i)$를 대입하여 Dual 문제로 바꾸자.
- Dual Lagrangian problem (Maximize)
$$\begin{align*}L = & R^2(1 - \sum_{i=1}^l \alpha_i) + \sum_{i=1}^l \xi_i (C-\alpha_i - \beta_i)\\ &\;+ \sum_{i=1}^l \alpha_i \Phi(x_i)\cdot \Phi(x_i) - 2\sum_{i=1}^l \sum_{j=1}^l \alpha_i\alpha_j \Phi(x_i) \Phi(x_j) + \sum_{i=1}^l \sum_{j=1}^l \alpha_i\alpha_j \Phi(x_i) \Phi(x_j)\end{align*}$$
$1 - \sum_{i=1}^l \alpha_i = 0$ 조건과 $C-\alpha_i - \beta_i = 0$ 조건을 사용해 식을 정리하면,
$$L = \sum_{i=1}^l \alpha_i \Phi(x_i)\cdot \Phi(x_i) - \sum_{i=1}^l \sum_{j=1}^l \alpha_i\alpha_j \Phi(x_i)\Phi(x_j)$$
$$s.t.\;\;\; 0\leq \alpha_i \leq C$$
$L$에 대한 최대화 문제는 $L^\prime = -L$ 일때 $L^\prime$의 최소화 문제로 바꿀 수 있다.
정리하면, ($L^\prime$을 그냥 $L$이라 썼다)
$$min\;\;\; L = \sum_{i=1}^l \sum_{j=1}^l \alpha_i\alpha_j \Phi(x_i)\Phi(x_j) - \sum_{i=1}^l \alpha_i \Phi(x_i)\cdot \Phi(x_i)$$
$$s.t.\;\;\; 0\leq \alpha_i \leq C$$
(Kernel trick 부분은 생략,,, $\Phi(x_i)\cdot \Phi(x_i)$에 대한 처리...?)
Support Vector Data Description (SVDD) (Cont.)
우리는 제약조건 $(C-\alpha_i - \beta_i = 0)$과 라그랑주 승수법에 따른 조건 $(\beta_i\xi_i = 0)$를 알고있다.
이를 이용하여 $\alpha_i$ 값에 따라서 각 객체가 어떤 의미를 가지는지 분석할 수 있다.
- Case 1 : $\alpha_i = 0$ $\Rightarrow$ Non-support vector
$\alpha_i = 0$인 경우 조건 $(C-\alpha_i - \beta_i = 0)$에 따라 $\beta_i = C$이다. 따라서 $\xi_i = 0$이어야 한다. $\alpha_i = 0$이고 $\xi_i = 0$으로 $L$에 아무런 영향을 주지 않는다. 이 경우 non-support vector로써 위 그림에서 하얀색 점들이다.
- Case 2 : $\alpha_i = C$ $\Rightarrow$ Support vector (outside the Hypersphere)
$\alpha_i = C$인 경우, $(C-\alpha_i - \beta_i = 0)$에 따라 $\beta_i = 0$이다. $(\beta_i\xi_i = 0)$에서 라그랑주 승수와 제약식 둘다 0이면 안되기 때문에 $\xi_i > 0$이어야 한다. 이 경우 페널티를 받는 Hypersphere 밖에 있는 support vector이다. 위 그림에서 검은색 점들이다.
- Case 3 : $0<\alpha_i<C$ $\Rightarrow$ Support vector (on the Hypersphere)
$0<\alpha_i<C$인 경우, $(C-\alpha_i - \beta_i = 0)$에 따라 $\beta_i > 0$이다. $(\beta_i\xi_i = 0)$ 조건에 의해 $\xi_i = 0$이어야 한다. 이 경우 페널티를 받지 않으면서 $L$에 영향을 주는 Hypersphere 위의 support vector이다. 위 그림에서 파란색 Hypersphere 위 회색 점들이다.
Example : SVDD with Gaussian(RBF) kernels
$$K(x_i,x_j) = exp \bigg(\frac{-||x_i - x_j||^2}{s^2} \bigg)$$
앞의 글에서 RBF Kernel을 사용하는 경우 $s$값이 크다면 더 Generalize된 분류경계면을 만들고, $s$값이 작다면 더 Specialize된 분류경계면을 만든다고 공부했었다. 아래 예시를 보면 확인할 수 있다.
1-SVM vs. SVDD
Tax (2001) pp.39 ~ 41.
※ 이 글은 고려대학교 산업경영공학과 강필성 교수님의 IME654 강의를 정리하고, 공부한 내용을 추가하여 작성되었습니다.
댓글
댓글 쓰기