이번 장에서는 SVM 관련해서 저번에 보았던 Classification 말고 이 후에 개발된 방법에 대해 알아본다.
우선 SVC에서 약간 변형된 버전을 설명해본다.
$\nu$-SVM 은 기존 컨셉과 동일하다. 역시 decision boundary를 찾기 위한 목적함수가 설정이 되어있다.
기존의 dual form으로 나타낸 목적함수는 아래와 같다.
$\nu$_SVM 같은 경우는 기존의 form에서 $C$ 부분이 사라지고, 새로운 term인 $\nu \rho$가 추가된 것을 볼 수 있다. 먼저 $n$이라는 것은 데이터 전체 개수이기 때문에 우리가 조절하는 parameter는 아니다. 대신에 $\nu$ (nu라고 읽는다. 누.) 라는 것은 parameter로써 우리가 조절할 수 있다. 그리고 $\rho$ 의 경우는 조절하는 것은 아니고, slack variable 처럼 모델 구성하면서 찾게 되는 parameter이다. 거의 기존의 SVC(c-SVM)과 동일하다. 원래 사용하던 $C$는 마진의 범위와 오차의 허용 비율을 조절하는 hyperparameter였다. 여기서 $\nu$는 0 과 1사이의 값으로 넣어주게 되는데 이 때 역할은 margin을 설정하게 되면 margin안에 error가 발생하게 될텐데 이에 margin error에 대한 upper bound를 설정하게 해줌과 동시에 support vector의 lower bound를 설정한다.
위의 수식 역시 Lagrange multiplier로 정리하면 아래와 같은 수식으로 변형할 수 있다. $C$대신 들어간 $\frac{1}{n}$ 은 boundary가 $ 0 \leq \alpha_{i} \leq \frac{1}{n}$ 이 된다.
추가된 constraint 는 수식 맨아래에 보이는 것처럼 $\sum_{i=1}^{n} \alpha_{i} \geq \nu$ 이다. 여기의 $\alpha_{i}$도 역시 기존의 SVC처럼 support vector가 아니면 0이라는 값을 가지게 된다. 즉 $\nu$를 증가시키면 support vector의 수도 증가하게 된다.
위의 수식을 보면 알겠지만 $\nu$가 커지게 되면 양쪽 term을 minimize하는데 도움을 주게 되는데, 그렇게 되면 margin도 커지다 보니 $\xi$ 와 같이 오차가 발생하게 되는 샘플의 수도 같이 증가하게 된다. 즉, $\nu$ 값을 증가시켜서 전체적으로 감소시킬 수는 없다. 왜냐하면 그 오른쪽의 term에 대해서 증가하는 꼴이 되어 전체적으로 감소시키기는
무리이기 때문이다. 곧 trade-off 문제에 맞닥뜨리게 된다.
아래의 그림은 [1]논문의 실험 결과를 나타낸다. 아래의 Table을 토대로 바로 위처럼 시각화를 시킨 것이다. Table은 $\nu$값을 증가시켜 가면서 $\nu$값에 따라서 error의 비율, Support Vectors의 비율과 $\rho / ||w||$ 마진의 크기를 보여주고 있다. $\rho / ||w||$ 의 경우는 $\nu$ 값을 풀었을 때 $\rho$값이 결정되고, margin이 결정된다. 원래 수식에서는 1이 고정이였는데, 이를 바꾸기 때문에 margin의 넓이가 달라지게 된다.
$\nu$가 0.8인 경우를 보면 error비율도 증가하고, support vector 비율도 증가했고, $\rho / ||w||$도 증가한 걸 알 수 있다. 반대로 $\nu$를 줄이면 error 샘플 수가 감소하고 support vector가 마찬가지로 감소하고, 마진도 줄어드는 것을 알 수 있다.
기본적으로 SVC에서는 두 class에 대한 classifier 였다. binary classification 문제에서만 사용이 가능했다는 말이고, 이는 애초에 decision boundary라는 직선을 찾는 것이기 때문이다.
이를 해결할 수 있는 방법으로는 먼저 binary 문제를 푸는 classifier를 결합하여 multiclass 문제를 푸는 것이 있다. 일종의 앙상블 모델이라고 볼 수 있다.
이렇게 결합을 하는데는 one-versus-the rest방식과 one-versus-one 방식이 존재한다.
one-versus-the rest방식의 경우는 학습을 하나의 class를 1로 두고 나머지 class를 모두 0으로 둔다. 아래의 그림을 예로 든다면 A와 B,C를 가르는 직선을 찾고, B와 A,C를 가르는 직선을 찾고 마지막으로 C와 A,B를 가르는 직선을 찾는 것이다. 그리고 이 직선들을 가지고 새로운 데이터가 들어왔을 때 예측을 하게 된다.
총 k개의 classifier를 구성해서 문제를 풀게 되는데 이 때, class가 많아지게 되면 첫번째! 하나의 class와 나머지를 대상으로 이진 분류를 하다보니 imbalance 문제가 발생한다.
그리고 두번째로는 아래의 그림에서 처럼 A, B, C 어디에도 속하지 않는 경우가 발생한다. 세번째! scale의 문제인데 각기 다른 scale을 갖다보니 정확하게 값이 안나올 가능성도 존재한다.
one-versus-one approach의 방법은 아래와 같다. 전체 class 중에서 두 개만 따로 뽑아서 그 두 class 만 구분하는 classifier를 학습하게 된다. 그렇게 되면 k 개의 class가 있을 때 k(k-1)/2 횟수 만큼의 classifier를 학습시키게 된다.
기존의 one-versus-the rest approach 보다는 정확도가 높은 것으로 알려져 있는데, 문제점을 살펴보면 이전의 one-versus-the rest 방법의 경우는 k-1 번의 학습 횟수를 보이지만(계산량이 선형적임.) one-versus-one 방법은 제곱으로 늘어나게 되어 학습시간이 더 많이 소요된다.
이번에는 regression 문제를 푸는 방법에 대해 알아본다.
기존의 regression 문제에 대한 error function 을 설명함으로써 regression 문제를 푸는 방법을 설명해볼 수 있다. 기존에 linear regression 같은 경우는 아래와 같이 sum of squares를 줄이고, variance를 줄이기 위해 regularization term 또한 줄이는 방식의 목적함수를 구성할 수 있었다.
이에 sum of squares term 대신에 아래와 같은 error function 을 사용하게 된다. 이를 $\epsilon$-insensitive error function 이라고 한다. $\epsilon$ 는 일종의 margin과 비슷한 역할을 한다. 만약에 실제값과 예측값 차이의 절댓값이 $\epsilon$보다 작으면 오차가 없는 0을 주고, $\epsilon$ 보다 커지게 되면 오차 절댓값에 $\epsilon$을 뺀 값을 사용하게 된다. 즉, 0과 $|y_{i} - \hat{y}_{i}| - \epsilon$ 사이의 maximum 값을 사용하게 된다.
SVR에서는 결과적으로 아래와 같은 목적함수를 사용하게 된다. $\lambda$ 대신에 $C$를 사용하고, sse 부분을 $\epsilon$-insensitive error function 을 사용하게 된 차이를 볼 수 있다.
아래의 그래프에서 녹색선의 경우는 sum of square error를 나타내며 빨간선의 경우는 $\epsilon$-insensitive error를 나타낸다. $\epsilon$ 보다 큰 경우에 대해서 error 값이 선형적으로 죽 증가하는 것을 볼 수 있다.
아래의 그래프를 보면, 붉은색 범위가 나타내는 것이 $\epsilon$에 해당하는 범위라서 error가 사이에 존재하면 0으로 표현하게 되고 그렇지 않은 경우에 error를 주게 된다. 예측을 하는 과정을 간단히 설명해보면 예를 들어 아래의 그림에서 예측 범위(tube)보다 위에 위치한 파란색 관측값 하나를 본다면, 범위로 다시 넣어 주기 위해서 slack variable만큼 빼주거나 반대로 예측하는 값을 위로 좀 더 올려주게 된다.
SVR에서도 마찬가지로 slack variable을 도입함으로써 간단하게 표현이 가능하다.
그리고 나서 4 개의 constraint를 $i$ x $n$만큼해서 Lagrange multiplier를 도입하면 아래와 같은 수식을 얻을 수 있다.
추정식은 다음과 같이 설정하게 된다.
이제 우리가 추정해야할 parameter들($\xi_{i}, \hat{\xi_{i}}, b, w$)에 대해서 0으로 놓아 편미분을 하게 된다. 그리고 그 값들을 다시 Lagrane 수식에 대입을 해서 정리를 한다. 그렇게 정리를 하게 되면 아래와 같은 수식을 얻게 된다.
SVC와 마찬가지로 이 아래의 constraint에 대해서 Lagrange multiplier에 대한 수식으로 바뀌게 된 것이다.
아래의 term 중에서 $k(x_{i}, x_{j})$ 라는 dot product term은 전에 배운 kernel을 도입한 것이다. 그리고 $a$에 대해서 2차 quadratic form으로 된 것이고, 이것을 이용해서 문제를 풀 수 있게 된다.
SVC 와 마찬가지로 $a$에 대한 constraint가 있는데, Lagrangian multiplier이기 때문에 0보다 커야하며, upper bound $C$가 오차항에 대한 가중치의 값을 가지게 된다.
실제로 SVC, SVR에서 각각의 slack variable과 parameter들을 미분했을 때 나오는 수식을 보면 유사한 것을 볼 수 있다. SVC에서 $w$ 같은 경우에는 $a, y$에 대한 liner combination 으로 정리된다고 하면 SVR에서는 $(a - \hat{a})$로 liner combination으로 정의된 것을 볼 수 있다. SVR의 두번째에서도 $(a - \hat{a})$ 을 모두 더하고 나면 0으로 되는 것을 알 수 있고, $C$ 값같은 경우도 slack variable인 $a - \mu$와의 관계를 보면 0보다 크거나 같은데, 이 수식에 의해서 upper bound가 결정이 되게 된다.
$a$ 가 0이냐 아니냐에 따라서 support vector냐 아니냐로 나뉘게 되는데, regression 의 경우에는 lagrange multiplier $a$또는 $\hat{a}$가 $C$인 경우에는 둘 중에 하나는 적어도 0을 가지게 된다.
아래의 수식중 위에 것은 튜브보다 위에 위치할 때, 아래의 것은 튜브보다 아래의 위치한 값을 의미하고, 이는 primal form에서 3,4 번째 constraint의 slack variable(오차)을 0으로 두게 되고, $\hat{y}$을 구해 이 후의 $\hat{y}$ 식에 대입하여 아래와 같은 관계식을 얻게 된다.
$a$와 $\hat{a}$가 0과 $C$ 사이에 있을 때 = b 로 놓고 b를 계산하고 이들을 일반적으로 평균을 구하면 b를 구할 수 있게 된다.
최종적으로 $a$와 $b$ 값을 구하고 나면 $f(x)$를 계산할 수 있게 되고, feature space상에서 dot product이니까 kernel function으로 대체한 것을 알 수 있다.
regression 에서 $\nu$-SVR 은 아래의 수식과 같다.
여기서 $\nu$라고 하는 것은 tube 바깥에 존재하는(오차가 존재하는) 샘플의 개수를 조절하는 역할을 한다. 조절해주는 것은 많아야 $\nu n$ fraction 만큼의 샘플만 tube 바깥에 존재할 수 있다는 것을 조절해주는 것을 의미한다.
Support Vector의 Domain Description이 의미하는 것이 뭔지를 알아보도록 하자. Domail Description은 sample들에 대한 설명을 해주는 건데, 관찰한 데이터들이 어떤 영역안에 있다라는 것을 설명해주는 것이다. 그래서 unsupervised에 해당한다. 뒤에 설명할 클러스터링을 위한 베이스로 생각하면 된다. 일반적으로 training 데이터에 대해서 대부분의 데이터에게 영역을 제시해주게 된다. 반경을 잡고 영역내 있냐 없냐를 판단할 수 있기 때문에 outlier detection, novelty detection 같은 곳에 사용이 된다.
support vector machine 은 원이라는 영역으로 제시를 해주게 된다. 즉 중심점과 radius를 제시해줌으로써 이안에 대부분의 데이터가 포함되는지를 제시해준다. 찾고자 하는 값은 데이터가 몰려있는 중심 그리고 반경이다.
아래와 같이 좌표가 주어지면 중심점 $a$와 반지름(반경) $R$을 구해야하는데, 반경을 키워 모든 점을 다 커버하려면 위 그림처럼 noise들도 다 포함되게 된다. 이는 좋은 선택이 아니다.
원 안에 있는 값들은 0 값을, 바깥에 위치한 데이터는 0이 아닌 오차값을 갖게 된다.
그래서 $R^{2}$과 오차들의 합을 더한 것을 minimize하는 방향으로 목적함수를 설정한다. 그리고 오차항 앞에는 패널티를 주기위해 $C$를 도입한다는 사실은 전에 배웠다. 아래의 수식은 primal form이고, 전처럼 lagrane multiplier를 거친다.
lagrane multiplier를 거치면 아래와 같은 form을 구할 수 있게 된다.
미분해서 = 0 으로 풀면 아래의 3개의 수식을 얻게 된다. 여기서는 중심 $a$는 $x_{i}$의 선형결합으로 이뤄지게 되고, $\alpha_{i}$가 여기서는 다 더하면 1이 되고, lagrange multiplier는 0보다 크거나 같아야하니까 upper bound 가 $C$로 생기게 된다.
L에 대해서 Dual form 으로 변형된 것이 아래의 수식과 constraint이다. 아래의 수식처럼 2차식이 되고, quadratic progarmming으로 해를 구할 수 있게 된다. $\alpha_{i}$를 구하게 되면 중심 $a$를 구할 수 있게 된다. 그러면 반지름은 어떻게 구할까?
위의 그림을 보게 되면 원안에 들어와있는 데이터들에 대해서는 $\alpha$값이 0을 갖게 되고, boundary에 걸리거나 바깥에 위치한 데이터는 0이 아닌 값이 되고 support vector가 된다. unbounded support vector는 0 보다 크고 $C$보다 작은 값을 가지고, 바깥에 위치한 데이터는 $C$의 값을 가진다. 즉, $\alpha$값을 보면 boundary 를 기준으로 어디에 위치한 데이터인지 알 수 있게 된다. numerical한 오류때문에 boundary에 걸리는 애들의 평균을 사용해서 거리(반경)를 구한다.
반경을 구한다면 새로운 좌표들이 들어오면 아래의 수식 값을 계산해서 반경안에 들어오는지 확인할 수 있다. 반경안에 들어온다면 training set 안에 들어오는 데이터라는 것을 판단할 수 있다. 만약 반경보다 크게 되면 outlier로 판단하게 된다.
아래의 수식을 보면 vector들의 dot product만을 가지고 연산을 하게 된다. 여기서도 동일하게 kernel trick을 통해서 input space에서 feature space로 보내게 되고, SVDD를 적용해서 반경을 정해서 구나 원으로써만 표현했던 것을 데이터를 더 잘 표현해줄 모양으로 description을 할 수 있게 된다.
목적함수 term도 dot product니까 kernel을 씌우는 것을 볼 수 있다.
$\alpha$들에 대한 값을 구하게 되면, 그걸 통해서 다시 kernel함수로 변경을 해서 최종적으로 반경보다 작은지 큰지를 판단할 수 있게 된다.
가장 널리 쓰이는 kernel은 Gaussian, RBF function 이다. 아래의 그림은 RBF fuction에서 $C$ 값을 달리하면서 어떤 특징을 보이는지를 나타낸다. $\sigma$는 기존의 감마 값의 역수로 생각하면 된다.
sigma를 키울 수록 원에 가까워지는 모양인 것을 알 수 있다. 그리고 $C$가 커질 수록 바깥으로 벗어나가는 데이터가 많아지게 된다.
방금 SVDD같은 경우는 도메인의 설명을 하기 위해 구체 안에 들어오는 것을 보고 판단했었다. 최종적으로 실제 데이터가 위치하고 있는 지점을 찾고, decision function 을 계산해 양수값을 가지면 도메인 안에 있다고 판단을 하고 음수의 값을 가지면 outlier라고 판단한다고 했다.
이 방식말고 One-Class SVM 은 unsupervised에 해당하며, 데이터를 애초에 고차원으로 매핑을 시킨다음에 거기서 어떤 방식으로 domain description을 하냐하면, hyperplane을 가정을 한다. 어떤 평면으로 선을 그었더니 원점으로 부터 싹 분리가 되는데, 최대한 타이트하게 잡아주는 것을 의미한다. 또 다른 차이점은 $C$라고 하는 parameter (오차합에 주는 가중치) 대신에 $\nu$-SVM 방식처럼 0과 1사이의 비율(벗어나는 데이터들에 대한)들을 조절하는 것으로 구성되어 있다.
이 그림을 보면서 이해해보자. 이것이 잘 작동하려면 고차원의 feature로 보내야한다.. 아래의 그림처럼 한 선을 그었을 때, 원점으로 부터 싹 분리가 된다. 그리고 법선벡터 $w$를 구하게 되면 $\rho$ 라는 절편 같은 역할을 하는 값을 구할 수 있게 된다. 이 계산을 하게 되면 아래의 빨간선 아래의 값들은 양의 값을 가지게 된다. 반대로 위쪽에 존재한다면 음의 값을 가지게 된다.
이렇게 데이터를 tight하게 분류하는 hyperplane을 찾아주는 방식으로 domain description하는게 feature space상에서 one-class svm 이다.
svm은 다양한 application이 존재한다는 것을 알 수 있었다. supervised에 해당하는 classification, regression이 가능하다는 것 그리고 unsupervised에 해당하는 domain description과 clustering까지 가능한 알고리즘이다.
클러스터링은 비지도학습중 하나인데, 분포가 다른 여러개의 샘플들로 이뤄진 도메인이 있다고 해보면, 그룹핑하는게 목표가 되는데, 아래의 그림과 같다. 아래의 그림처럼 그룹핑을 하는 것이다.
이 그룹들은 그룹내에서는 샘플끼리 서로 가깝고, 그룹간에는 거리가 최대한 멀도록 묶어주는게 목표이다.
기본적으로 domian description을 가지고 clustering을 진행하게 된다. 각 영역에 대해서 내부에 있는지 아닌지를 판단할 수 있게 된다. 아래의 그림의 선은 영역 안과 밖에 위치한 값들의 거리를 가지고 계산해서 생긴 경계이다.
양인지 음인지를 가지고는 클러스터간의 포함에 대한 것을 설명해줄 수는 없다. 그래서 SVClustering은 서로 떨어져 있는 것들을 구분하는 작업만 추가해주게 된다. 이 작업을 labeling이라고 한다.
아래의 그림을 보게 되면, 실제로 영역이 있다면(왼쪽 태극문양 같은 분포 그래프) 특정 영역을 그려볼 수 있다고 직관적으로 볼 수 있지만, 실제로 feature space 상에서는 다 구(가운데그림) 안에 위치한 데이터가 된다.
영역안에 있으면 양의 값을 갖고, 그렇지 않으면 음의 값을 가지기 때문에 서로 다른 클러스터 사이의 값을 활용해서 클러스터 label을 붙여줄 수 있게 된다.
아래의 수식은 즉 샘플과 샘플 사이에 값을 보고, 전부다 양의 값을 가지면 1을 주고, 영역밖으로 나갔다가 들어오는(중간에 음의 값을 가지면) 데이터가 있으면 0을 줌으로써 서로 다른 클러스터로 명시할 수 있게 된다.
$A$: adjacent matrix(인접행렬: 그래프에서 어느 꼭짓점들이 변으로 연결되었는지 나타내는 정사각 행렬.)
위와 같은 그래프를 통해 본 방법을 complete graph(CG)라고 한다. 위의 수식에서 우리는 결국 i, j를 구해야한다. 샘플의 모든 i, j pair에 대해서 계산한다. 하지만 계산량 때문에 특정 하이퍼 매개값을 정해주고, pairwise 하게 0보다 큰지 작은지 확인을 하게 된다. CG의 단점은 시간이 오래 걸린다는 것이다. 그리고 위 그림과 같이 곡률이 심한 클러스터 모양인 경우에는 완벽한 클러스터링이 안될 수 있다.
그래서 사용하는 다른 labeling 방법이 SVG 이다. 특정 i 를 고르면, 그 i 와 support vector 사이의 adjacent matrix를 구하게 된다. 모든 좌표에 대한 pair가 아닌 support vector 끼리만 고려하는 것이다.
그리고 MST(Minimum spanning tree) 라고 하는 또다른 labeling 방법이 있다. tree 구조(부모, 자식 노드 구조)를 만드는 것이다. tree의 weight를 두 노드 사이의 거리로 놓는다. 그리고 tree의 edge에서 weight들의 합이 최소가 되게끔 tree를 만드는 것이다. 먼저 training 데이터로 MST를 구성하고, 그 tree에서 서로 연결된 노드끼리 pair하게 $A$값을 계산하게 됨.
CG이후에 나온 방법은 최대한 정확하게 클러스터링을 하면서 최대한 시간을 줄이는 방식이다.
이러한 방법들로 connected components(서로 뭉쳐 연결된 노드들의 집합)를 얻게 된다. 이러한 component들로 clustering이 된다.
아래의 그림처럼 SVDD가 있다하면 영역 밖에 있는 것은 고려하지 않는다. 내부에 있는 것 끼리 계산해서 영역을 정의하게 된다.
support vector끼리의 거리만을 가지고 연결되있다고 판단되는 것끼리 모아놓아 component를 구성하게 되고 아래 그림처럼 총 4개의 클러스터를 찾아주는 것을 알 수 있다.
SVM 알고리즘은 다양한 응용으로써 지도, 비지도학습을 수행이 가능하다. 다만 수학적으로 접근할 때 수식의 전개, lagrange multiplier 나 quadratic programming 등의 방법으로 전개가 되기 때문에 이러한 것들을 모두 숙지하고 있어야 그 전개에 대한 이해가 된다. 이런 trick을 몰라도 각 term과 계수나 parameter, hyperparameter가 의미하는 것이 무언인지만 알고 있어도 튜닝이나 모델학습 때 유용하게 적용할 수 있다. 이번 장에서는 support vector machine이 비지도 학습 clustering도 하는 방법이 있고, 또 어떤식으로 하는지를 알아보았다.
[1] A tutorial on 𝜈𝜈-support vector machines, Appl. Stochastic Models Bus. Ind., 2005; 21:111–136
'머신러닝' 카테고리의 다른 글
| Expectation Maximization (1) | 2020.11.24 |
|---|---|
| Dimensionality Reduction (0) | 2020.11.16 |
| Nearest Neighbor Method (0) | 2020.10.18 |
| Support Vector Machine(1) (0) | 2020.10.18 |
| Graphical Model (0) | 2020.10.18 |
댓글