아마도 MLDL에서 제일 어렵고 제일 중요한.. 알고리즘이 아닐까 싶음
당연히 면접준비용이기에 러프하게 다루는 점 양해부탁..
Perceptron의 가장 큰 단점은, 항상 linear decision boundary를 찾을 수는 있지만 가능한 해가 여러 개이고 따라서 initialization에 영향을 받는다는 것임. SVM은 이러한 단점을 극복하기 위해, decision boundary와 각 클래스의 데이터 포인트 사이의 margin을 최대화해주는 알고리즘을 제안합니다.
기본적인 식은 아래와 같아요:
\begin{equation}\label{svm}\tag{*}\max_{\gamma,\mathbf{w},b}\gamma\\\text{such that }\forall_i\: \gamma^i = \dfrac{y^i(\mathbf{w}\cdot\mathbf{x}^i+b)}{\Vert\mathbf{w}\Vert}\end{equation}
규정된 건 아니지만 사용하는 트릭에 따라 세 가지 정도로 나누어 설명할 수 있을 것 같은데요,
- Hard SVM: mistake를 허용하지 않는 경우입니다.
- Soft SVM: mistake를 허용해주는 경우인데, "얼만큼 이동시켜줘야 제대로 분류되는지"를 의미하는 slack variable과 이에 적용되는 하이퍼파라미터 slack penalty (결과적으로 margin의 크기가 조정됨)를 이용해 decision boundary를 찾습니다. 이때 slack variable은 hinge loss로 계산되는데, 그래서 우리가 hyperparameter처럼 설정해줄 필요가 없는 아이들이이에요.
- Kernel SVM: 데이터가 linearly separable하지 않은 경우에 대해서도 linear separator인 SVM을 활용할 수 있게끔 해줍니다. kernel trick은 고차원 feature space내에서의 계산을 간단하게 해주는 kernel function을 이용하는 건데, 기존에는
(1) input space와 feature space간의 매핑 $\phi$를 각 데이터포인트에 적용해 $\phi(x)$ 계산
(2) $\phi(x)$를 이용해 inner product 계산
이렇게 두 단계의 복잡한 계산을 거쳤다면, kernel function은 input space에서의 inner product 값으로 $\phi$를 직접 계산하지 않아도 feature space 내에서의 계산 결과를 유도할 수 있다는 편리함이 있어요. 아무튼 이렇게 non-linear한 feature space로의 매핑을 통해 SVM을 구현할 수 있습니다.
SVM은 KKT 조건을 만족하는 constrained QP여서, dual problem으로 전환해 최적화 문제를 풉니다. 그렇게 dual problem으로 바꾸면, w를 직접 계산하는 대신 margin의 canonical line(경계)에 놓인 데이터 포인터들, 즉 서포트 벡터들을 찾는 문제로 바뀌어요.
ㅋㅋ 이렇게 대답해도 되나
728x90