[미완성][논문 리뷰] PSO(Particle Swarm Optimization)를 이용한 SVM parameter 튜닝 관련 논문

Support vector machine parameter tuning based on particle swarm optimization metaheuristic. 

(Korovkinas K., Danėnas P. and Garšva G. (2020) “Support vector machine parameter tuning based on particle swarm optimization metaheuristic”, Nonlinear Analysis: Modelling and Control, 25(2), pp. 266–281. doi: 10.15388/namc.2020.25.16517.)

이 논문을 리뷰하게 된 까닭은, 현재 수강중인 비선형최적화 강의의 과제를 위해서이기도 하지만 좀 더 확장하여 modified SVM based RS를 구현하는 것에 그 목적이 있다. 논문 선정 기준은 우선 비선형최적화에 대한 주제를 담으면서도, RS에 적용가능한 모델에 적용가능하고, Q1, SCI급 논문인 것으로 선택했다. 

기준은 교내 포탈에서 제공하는 JCR 랭킹,
검색엔진은 http://www.webofscience.com 를 이용했다. 

(Abstract) 

본 논문은 Particle swarm optimization metaheuristic을 이용한 linear SVM의 parameter tuning을 소개함. 해당 방법은 SVM을 이용한 텍스트 데이터의 분류 정확도 향상을 위해 최적 코스트의 parameter를 찾아줌. 추가적으로, majority voting based ensembling 방법이 제안된 방법의 효율성을 증가시키기위하여 적용되었음.

1 Introduction

SVM은 감성 분류 문제에 가장 자주 쓰이는 ML 알고리즘이며, 여러 고난도의 도메인에서 그 성능을 증명해왔음. 

그러나, 현재 시류에서 사람이 그 수준을 결정하는 manual hyper-parameter selection을 위한 그 어떤 휴리스틱 규칙이나 SVM을 위한 rules of thumb도 제공되지 못했음.

대부분 이러한 hyper-parameter 튜닝에 있어서는, 대부분이 몇가지 휴리스틱 알고리즘을 이용하는데, 유전 알고리즘 또는 이 리뷰의 주제가 되는 PSO(Particle Swarm Optimization), colony optimization 등이 그러한 알고리즘임.

이 중 PSO는 다른 진화 알고리즘과 결합되었을 때 더 좋은 성능을 내는데, [47]의 경우가 좋은 예시임.

앙상블 분류 모형은 자주 쓰이지만, 단일 모형에 비해 오히려 성능이 떨어지는 경우가 많음. 저자는 [4]의 ensemble voting 알고리즘이 감성 분류 문제에서 좋은 성능을 보였다는 것에 동기를 부여받아 텍스트 데이터 분류 문제에서의 LSVM(Linear SVM) 성능을 단순한 방법을 이용해 개선코자 함.

2 Relevant algorithms

2.1 Support vector machines

SVM에 대해서는 다른 게시물에서 다루는 중이며 지속 업데이트 될 예정이다. 본 게시글에서는 간단히만 다루도록 한다.

본 논문의 linear SVM은 학습데이터가 매우 커다랄 때를 목적으로 최적화된다. 

훈련 벡터집합 \(x_i\in\mathbb{R}^n\), \(i=1, ... , l\)이 2클래스 집합이고, 분류문제 \(y\in\mathbb{R}^l\)이 \(y_i=\{1,-1\}\)라고 했을 때, 결정 함수(결정 경계의 함수)는 다음과 같다: 

\[sgn(w^Tx)\]

이후 논문에서는  L2 정규화된 L1 loss SVC(support vector classifier)가 해결하는 primal problem과 L2 정규화된 L2 loss SVC가 해결하는 primal problem의 dual representation 된 형태가 주어져 있다. 결과적으로는 L1-정규화가 sparse solution \(w\)를 generate한다. SVM은 기본적으로 결정경계를 찾는 것이 목표이므로, 본 논문에서의 linear SVM 또한 동일한 목적을 갖는다.

2.2 PSO(Particle Swarm Optimization) 알고리즘

PSO 자체는, 따로 게시글을 만들어 다뤄보아야 할 것 같다. 직관적인 이해는 어느정도 했으나, 역시나 수식이 문제다. 우선은 논문에서 다룬 수준에서 겉핥기라도 해보는 것이 좋겠다.

우선 PSO는 논문 reference의 [11]에서 소개된 이론이다. 주로 Genetic algorithm과 비교되는 편인데, 그 이유는 조금 더 찾아보아야겠다. 아마도, optimizer로 사용되는 메타휴리스틱 알고리즘 계열이지 않을까 싶다. NP-hard 문제들에도 제법 많이 사용되는 것으로 보았을 때 objective가 같기 때문일것도 같다. 

PSO는 간단히 말해 개별 입자가 서로 다른 속도(방향의 개념이 포함)로 움직이면서, 개별 입자의 best fit을 찾아나가는 알고리즘이다. 

\(t\)를 discrete time step이라고 할 때, \(a_i(t)\)는 i번째 입자의 위치이고, 이 때 i의 속도는 \(v_i(t)\)이다. 수식으로 나타내면 다음과 같다. : 

\[a_i(t+1)=a_i(t)+v_i(t+1)\]

이때, \(a_i(0)\sim\mathrm{U}(a_{min}, a_{max})\)인데, 어떤 논문 중에서는 이 초기값의 위치를 K-means 등을 이용해 설정하기도 하는 듯하다. 그렇다면 아마도 GMM을 이용한 방법론을 소개한 논문도 있을 것이라 생각된다.

아무튼 이때 속도 \(v_i(t)\)는 개별 입자에 대한 경험적 지식과 그 입자 주변의 이웃 입자의 정보 변화에 모두 영향을 받는다는 가정을 한다. 때문에 Global Best PSO에서 입자 i의 속도는 다음과 같이 계산되고, 앞선 가정은 \(c_1\), \(c_2\)를 통해 수식에서 구현된다. :

\[v_{ij}(t+1)=v_{ij}(t)+c_1r_{1j}(t)[b_{ij}(t)-a_{ij}(t)]+c_2r_{2j}(t)[\widehat{b}_{j}(t)-a_{ij}(t)]\]

수식에서 확인할 수 있듯이, 이때의 i번째 입자가 j번째 차원(\(j=1, ... , n_a\))에서 t-step에서 갖는 속도는 \(v_{ij}(t)\)로 나타낼 수 있다. 

언급했듯이, \(c_1\), \(c_2\)는 속도에 영향을 주는 경험적 + 근접이웃에 의해 결정되는 상수이다. 이 부분도 사실 자세한 조사가 필요하다. 결국은 처음 PSO를 제안한 논문을 확인해야 할 것 같다. 당장에 드는 의문은 이러한 상수 또한 일종의 parameter로 보인다는 것이다. 

\(r_{1j}(t), r_{2j}(t)\sim\mathrm{U}(0,1)\)는 stochastic element를 해당 수식에 부여하는 역할이다.

그리고, \(b_i\)는 personal best position이라 명명된 것으로, 최초의 t-step으로부터 마지막 t-step까지 i번째 입자가 방문했던 모든 position 중 가장 best 인 position을 일컫는다. \(t+1\) 단계에서의 personal best position은 다음과 같이 계산된다. : 

\[\begin{cases}b_i(t) & \text{if  } f(a_i(t+1)) \geq f(b_i(t)) \\ a_i(t+1) &\text{if  } f(a_i(t+1)) < f(b_i(t))\end{cases}\]

이때의 함수 \(f : \mathbb{R}^n_{a} \to \mathbb{R}\)는 fitness function으로, 진화 알고리즘과 같이 사용되는 경우에는 이 함수가 현재의 해가 최적해에 얼마나 근접했는지를 나타낸다. 그러니까, 이 함수가 particle의 퍼포먼스 또는 품질을 measure한다. 관련 reference가 논문의 [12]이다.

결과적으로 global best position인 \(\widehat{b}(t)\)는 t-step에서 다음과 같이 정의된다 : 

\[\widehat{b}(t)\in\{b_0(t), ... , b_{n_s}(t)\}, f(\widehat{b}(t))=\min\{f(b_0(t)), ... , f(b_{n_x}(t))\}\]

이때, \(n_s\)는 swarm에 속한 particle의 총 갯수이다. 

이상으로, 간단한 수준에서 PSO를 살펴보았다. 이론의 사상은 마치 새 떼나 정어리 떼에 비유할 수 있지 않을까 싶고, 수식화 되었다는 것이 흥미롭다. 특히 관심갖게 되는 속성으로는 개별 입자의 속도가 아닐까 싶은데, 매 시점마다 그 속도가 달라진다는 점에서 일반적으로의 속도에 빗대기는 어려워보인다. 허무맹랑한 상상일지 모르겠으나, 속도 외에 다른 물리적인 속성을 부여하면 또 완전히 다른 알고리즘이 탄생할 수 있지 않을까 싶기도 하다.

3 Proposed Method

(내용 추가 예정)