3.1 Support Vector Machine

SVM은 커널 매핑 및 최적화 기법을 이용하여 통계적 학습방법과 융합한 패턴 분류 알고리즘으로 다른 패턴 분류 알고리즘에 비해 비교적 간단한 구조를 가지며, 우수한 예측 성능을 보이는 것으로 알려져 있다. SVM은 특징 공간 (Feature Space)에서 초평면(Hyper-Plane)과 가장 인접한 지지벡터(Support Vector)들과의 거리인 마진(Margin)을 최대로 하는 최대 마진 초평면 (Maximum Margin hyper-Plane)을 찾아서 이진 분류를 수행한다[7-11]. 다시 말하면, SVM 패턴 분류기는 입력공간상에서 패턴 분류를 위한 초평면(hyper-plane) $f(x)$의 coefficients $w, b$를 최적화 한다. 일반적으로 SVM에서 사용되는 초평면은 다음과 같다.

여기서, $b in R$는 모든 실수의 집합에 속한 임의의 값을 의미하고, $w cdot x$는 계수 $w in R^n$와 입력 데이터 $x$와의 벡터 내적값을 의미한다.

식 (4)와 같이 정의된 초평면을 이용하여 입력 데이터의 해당 클래스 레이블을 결정하기 위하여 아래 식을 이용한다.

여기서, $haty$는 입력데이터 $x$의 추정된 클래스 레이블을 의미한다.

그리고 식 (4)와 같이 표현된 초평면을 클래스 경계면 (Decision Boundary Surface)라 부른다.

각 클래스에 속한 데이터들 중에서 초평면과 가장 가까운 거리에 있는 데이터 쌍의 거리를 최대 마진 (Maximum Margin)이라 하고, 아래식과 같이 표현한다.

만약 두 개의 클래스 분류 문제에서 주어진 데이터들이 선형 초평면으로 완벽하게 분리되어지지 않을 경우, 식 (5)를 (7)과 같이 변형하여 사용한다.

여기서, $\xi _ { j }$는 j번째 변수에 해당되는 슬랙변수를 나타내며, 항상 0보다 크거나 같아야 한다($xi_j >=0$).

이를 위한 일반적인 SVM의 목적함수는 (8)과 같다.

여기서, C는 오분류와 패턴 분류 성능간의 trade-off를 나타내는 파라미터로 “trade-off 파라미터”로 정의한다.

일반적으로 선형식을 기본으로 하는 Linear SVM으로는 실제 현장에 적용하여 비선형 분류 문제를 해결하기에는 부족함이 있어서 Linear- SVM을 Nonlinear-SVM을 확장하여 사용할 필요가 있다 ^[12]. 이를 위해 표 2에 나열된 것과 같은 Kernel function $K(x _ { i } , x _ { j } )$를 추가하여 사용한다.

3.2 Support Vector Machine 기반 다항식 뉴럴 네트워크

SVM 기반 다항식 뉴럴 네트워크는 네트워크의 기본구조인 뉴런으로 SVM을 적용하는 네트워크이며, 뉴럴 네트워크의 동적생성은 앞에서 설명한 일반적인 다항식 뉴럴 네트워크 생성 방법을 변경없이 이용한다.

일반적인 SVM의 경우 주어진 입력 변수 전체를 입력으로 사용하지만, 다항식 뉴럴 네트워크의 기본 노드로 사용되는 SVM의 경우에는 전체 입력 변수들 중에서 사용자가 미리 정한 개수만큼의 입력 변수만을 입력으로 선택하여 사용한다. 그리하여, 전체 입력 변수의 개수가 $p$이고 $q$개의 입력 변수를 선택하여 입력 변수로 사용할 경우, 만들어질 노드의 경우의 수는 (9)와 같다.

여기서, $K$는 표 2에 보인 커널 함수의 종류의 개수를 나타낸다.

노드를 선택하기 위한 기준으로 학습데이터에 대한 오분류율과 SVM의 목적함수 식 (8)을 결합하여 (10)과 같은 선택함수를 정의하여 사용한다.

여기서, MCR은 오분류율 (Mis-Classification Rate)을 의미하며, $J _ { SVM }$$J _ { SVM } = \frac{ 1 } { 2 } \parallel w \parallel ^ { 2 }$을 의미한다.

SVM 기반 다항식 뉴럴 네트워크의 구조는 그림 2와 같다.

그림 2에 보인 것처럼 $(l-1)$층에서 선택된 노드의 출력이 $l$층의 입력 변수로 사용되어진다. 그림 3은 SVM 기반 다항식 뉴럴 네트워크의 구조 생성과정을 보인다. 각 레이어의 구조를 결정하기 위하여 각 노드의 패턴 분류 성능을 평가하고, 패턴 분류 성능을 기반으로 선택 과정을 거쳐 미리 정해진 개수만큼의 노드들이 선택된다.

4.1 다중 목적 입자 군집 최적화 알고리즘(Multi-Objective Particle Swarm Optimization: MOPSO)

MOPSO의 기본 알고리즘인 입자 군집 최적화 알고리즘(Particle Swarm Optimization: PSO)은 물고기 혹은 새와 같은 무리를 짖는 동물들이 먹이를 찾아 생존하는 행동양식을 모사하여 최적화 문제를 해를 탐색하는 방법이다. Genetic algorithm, Genetic Programming과 같은 알고리즘에 비해 PSO에서 사용되는 연산자들이 매우 간단한 수학적 연산자이기 때문에 최적화 알고리즘의 계산속도 측면에서 매우 유리한 조건을 가지고 있다. 또한 확률적인 방법에 기반을 두고 최적화 문제를 해결하는 다른 알고리즘에 비해 안정적이고 빠른 수렴 특징을 가진다고 알려져 있다 ^[13].

단일 목적 PSO의 장점을 보유 하면서 다중 목적 함수를 처리할 수 있는 MOPSO가 2002년 Coello에 의해 개발 되었다 ^[14]. 다중 목적함수 최적화 문제(Multi-objective Optimization Problem: MOP)는 아래와 같이 정의된다.

Optimize $f _{i} ( \textbf{X}),~for~i=1, \cdots ,M$

subject to $g _{j} ( \textbf{X} )>0,~for~j=1, \cdots ,N$

$h _{k} ( \textbf{X} )=0,~for~k=1, \cdots ,K$

where, $\textbf{X} = ( x _{1} , \cdots ,x _{n} ) ,~x _{l} ^{(L)} \leqq x _{l} \leqq x _{l} ^{(U)} ,~l=1, \cdots ,n.$

여기에서 $f_i$는 개별 목적함수(objective function). $g_j$와 $h_k$는 각각 부등식과 등식 제한조건(constraint)이며, $M$은 목적함수의 개수를 의미하고, $N$은 부등식 제한조건의 개수, $K$는 등식 제한조건의 개수를 나타낸다. 또한 $x^(L)$과 $x^(U)$는 입력 변수 $x$의 최솟값과 최댓값을 나타낸다.

다중 목적 함수 최적화 문제에서 해공간에서 하나의 해 $rm { \textbf { X } } = \left ( x _ { 1 } , \cdots , x _ { n } \right )$는 이에 상응하는 목적함수 공간상의 점 $f( { \textbf { X } } )=$$\left [ f _ { 1 } ( { \textbf { X } } ), \cdots , f _ { M } ( { \textbf { X } } ) \right ]$을 갖는다. 해공간에서 서로 다른 두 점의 우열을 비교하여 우수한 해를 결정한다. 일반적으로 두 점 사이의 우열관계를 비교할 경우 “Dominance”관계를 이용한다.

해공간에서 다른 두 점 사이의 우열 관계를 비교하기 위한 “Dominance” 관계는 다음과 같다.

목적함수 를 최소화 하고자 할 경우, 해공간의 서로 다른 점 과 의 경우 이 보다 우수한 해라고 평가되기 위해서는 아래 두 조건을 모두 만족하여야 한다.

위와 같은 두 조건을 모두 만족 시킬 때, $rm { \textbf { X } } _ { 1 }$은 $rm { \textbf { X } } _ { 2 }$를 “dominate”한다라고 할 수 있다.

만약 해공간상의 두 점 $rm { \textbf { X } } _ { 1 }$과 $rm { \textbf { X } } _ { 2 }$가 서로 dominate하지 않을 경우 두 점은 서로 무엇이 우수하다 할 수 없으므로 최적해들의 집합의 원소가 될 수 있다. 이와 같이 해공간상에서 dominate되지 않은 점들의 집합을 pareto 집합이라고 하며, 이를 pareto optimal이라 부른다.

Pareto 집합을 이용한 MOPSO의 알고리즘은 다음과 같다.

step 1) 미리 정해진 수 만큼의 개체(particle: POP)들을 랜덤하게 생성한다.

(a)FOR i=0 TO MAX /* MAX: predetermined number of particles*/

(b) Initialize POP[i] randomly

step 2) 각 개체의 갱신에 필요한 속도를 초기화 한다.

(a) FOR i=0 TO MAX

(b) VEL[i]=0

step 3) 각 개체를 목적함수에 적용하여 적합도 (fitness)를 계산한다.

step 4) 평가된 각 개체의 적합도 벡터를 이용하여 dominated 되지 않은 개체들을 저장소 REP에 저장한다.

step 5) 현재까지 탐색한 탐색공간에 hypercube를 생성하고 각 개체들을 생성된 hypercube를 좌표 시스템으로 이용하여 위치시킨다. 여기서, 각 개체의 좌표는 각각의 목적함수의 값에 따라 결정된다.

step 6) 각 개체가 가지고 있는 메모리를 초기화 한다. 각 개체들이 보유하고 있는 메모리는 탐색공간에서 각 개체들이 탐색하기 위한 가이드 정보로 사용되어진다.

(a) FOR j=0 TO MAX

(b) PBESTS[j]=POP[j]

step 7) 식 (12)을 이용하여 각 개체의 이동 속도를 결정한다.

여기서, $W$는 하중계수로 $0.4 \sim 0.9$ 사이의 값을 가지며 (본 논문에서는 $W=0.4$를 사용하였다.) $R _ { 1 }$과 $R _ { 2 }$는 가속상수로 $[0,1]$사이의 값으로 랜덤하게 결정된다. + $PBESTS[j]$$는 j번째 개체의 가장 우수한 위치를 나타낸다.

$REP[h]$는 저장소에 있는 개체들 중에서 얻어지는 값을 나타내며, $h$는 아래와 같이 결정한다.

하나 이상의 개체를 포함하고 있는 hypercube에 미리 정하여진 값 ($x>1$)을 해당 hypercube에 속한 개체들의 수로 나누어서 얻어진 값을 적합도로 할당한다(본 논문에서 $x=10$을 사용함). 이와 같이 각 hypercube에 할당된 적합도를 이용하여 roulette-wheel 선택 방법으로 hypercube를 선택한다. 선택된 hypercube에 속한 개체들 중에서 랜덤하게 하나의 개체를 선택하여 $REP[h]$라 한다.

step 8) 각 개체의 위치를 식 (13)를 이용하여 갱신한다.

step 9) 갱신된 개체들이 초기 탐색 범위($P_{min}[i] \leqq POP[i] \leqq P _{max} [i]$) 안에 존재하는지 확인하다. 만약 초기 탐색 범위 밖에 존재할 경우, 즉 $POP[i] < P _{min} [i]$일 경우에는 $POP[i]=P _{min} [i]$와 같이 설정하고, $POP[i]>P _{max} [i]$일 경우에는 $POP[i]=P _{max} [i]$로 설정한 후 이동 속도에 을 곱하여 식 (13)를 반복한다.

step 10) 각 개체의 위치 정보를 이용하여 목적함수의 값을 구한다.

step 11) 새롭게 얻어진 각 개체의 목적함수 값들을 이용하여 저장소 에 존재하는 개체들의 목적함수 값들과 비교하여 를 갱신한다.

step 12) 각 개체의 과거 $PBESTS[i]$와 현재 $POP[i]$의 적합도를 비교하여 현재 $POP[i]$의 적합도가 우수하면 $PBESTS[i]$를 아래와 같이 갱신한다.

$PBESTS[i]$와 $POP[i]$의 적합도를 비교할 때 앞에서 설명한 Pareto Dominance를 기준으로 판단하게 된다.

step 13) 종료조건을 검사하여, 종료조건을 만족하면 최적화 알고리즘을 종료하고, 만족하지 않았다면 step 7)로 이동하여 알고리즘 과정을 반복한다.

4.2 다중 목적 입자 군집 최적화 알고리즘을 이용한 SVM 기반 다항식 뉴럴 네트워크 최적화

제안된 SVM 기반 다항식 뉴럴 네트워크의 각 층의 구조를 최적화하기 위하여 앞에서 설명한 다중 목적 입자 군집 최적화 알고리즘을 이용한다. MOPSO를 이용하여 SVM기반 다항식 뉴럴 네트워크의 각 레이어 구조를 최적화하기 위한 Particle의 구조는 그림 4와 같다.

그림 4에서 보인 바와 같이 각 particle은 ($m+1$)차원의 해 공간에서 탐색을 진행한다. 여기서 $m$은 입력 변수의 개수를 의미한다. MOPSO의 particle의 구조를 살펴보면, 앞 $m$개의 부분은 기본노드인 SVM의 입력 변수를 선택하기 위하여 사용되며, 마지막 하나는 SVM에 사용될 커널 함수의 종류를 결정하기 위하여 사용된다. 앞 $m$개의 부분은 $[0, 1]$ 사이의 임의의 랜덤 값을 가지도록 초기화 되며, 마지막 부분은 $\left \{ 1, 2, 3 \right \}$ 중에서 하나의 값을 임의로 선택한다.

MOPSO의 particle을 이용한 변수 선태과정은 그림 4와 같다. 그림 5에서는 5개의 입력 변수 $m=3$들 중에서 SVM 기반 다항식 뉴럴 네트워크의 기본 노드인 SVM의 입력으로 사용될 3개의 변수 ($l=1$)를 선택하고자 한다. 그림 4에서 빨간색으로 표시된 부분이 선택된 입력변수와 커널함수의 종류를 나타낸다.

MOPSO를 이용하여 제안된 SVM 기반 다항식 뉴럴 네트워크의 구조 최적화를 위한 과정은 그림 6과 같다. 그림 6에서 보인 바와 같이 SVM 기반 다항식 뉴럴 네트워크의 각 레이어의 구조는 MOPSO에 의해 결정된다. 단일 목적함수를 가지고 최적화 과정을 진행하는 Single-Objective PSO와 달리 MOPSO는 2개 이상의 목적함수의 값에 따라 우수한 particle을 평가하여 최적화를 진행한다.

최종적으로 모든 particle에 대해 2개 이상의 목적함수 측면에서 우수한 앞에서 설명한 pareto optimal set을 결정하게 된다. 이와 같은 과정을 거쳐 얻은 Pareto optimal set의 원소를 네트워크의 레이어를 구성하기 위한 노드로 사용하게 된다. MOPSO를 이용하여 제안된 SVM 기반 다항식 뉴럴 네트워크의 구조를 최적화하는 과정에서 Pareto Set을 정의하고 Repository에 저장한다. Repository에 저장된 Pareto set은 최적화를 위한 반복과정에서 갱신된다.

본 연구에서 사용된 2가지의 목적함수는 $J _ { SVM }$과 오분류율이며 이 두 가지 목적함수를 이용하여 정의한 Pareto Set은 그림 7과 같다.

5.1 SVM 기반 다항식 뉴럴 네트워크

제안된 SVM 기반 다항식 뉴럴 네트워크는 그림 3에 보인바와 같이 각 노드의 패턴 분류 성능 평가와 패턴 분류 성능을 기반으로 하는 선택 과정을 거쳐 네트워크의 구조가 결정되어진다.

표 4는 5-fold cross validation을 이용하여 실험한 결과를 보인다. 패턴 분류 성능을 평가하기 위하여 패턴 분류기의 분류율을 평가 지수로 사용한다.

여기서, PCR은 Pattern Classification Ratio를 의미한다. 또한 $g(a,b)$는 식 (16)와 같다.

SVM 기반 다항식 뉴럴 네트워크를 이용한 머신러닝 데이터에 대한 패턴 분류 성능은 표 4에 보인다.

Australian 데이터의 경우, 학습과정을 통해 동적으로 생성된 SVM 기반 다항식 뉴럴 네트워크의 구조는 그림 8과 같다.

5.2 MOPSO를 이용한 SVM 기반 다항식 뉴럴 네트워크 최적화

SVM기반 다항식 뉴럴 네트워크의 구조를 최적화하기 위하여 MOPSO 사용한다. 이를 위하여 사용된 다중 목적 입자 군집 최적화 알고리즘의 초기 설계 파라미터와 최적화 할 해공간의 탐색 범위를 표 5에 나타낸다.

학습 데이터의 패턴 분류 결과는 층을 증가시킬수록 개선이 되지만, 테스트 데이터의 경우 층의 개수가 증가 할수록 패턴 분류기의 복잡도가 증가되고, 패턴 분류기의 증가된 복잡도가 과적합 현상을 발생시켜 테스트 데이터에 대한 일반화 성능이 나빠짐을 알 수 있다. MOPSO에 의해 최적화된 SVM 기반 다항식 뉴럴 트워크의 패턴 분류 성능과 Generic SVM 기반 다항식 뉴럴 네트워크의 성능을 다른 패턴 분류기와 비교한 결과를 표 6에 나열하였다.

제안된 패턴 분류기의 성능과 기존 연구된 패턴 분류기의 성능을 비교할 경우 기존 패턴 분류기에 비해 우수한 성능을 보임을 알 수 있다.