패턴 인식 (9) 특징 선택
 패턴인식, 오일석 지음/교보문고 |
9. 특징 선택
외부 세계로부터 센서로 획득한 신호 s를 컴퓨터 메모리에 저장한 후에는 특징 생성이라는 작업을 통하여 특징 벡터 x를 만들어야 한다. 특징 생성은 특징 추출과 특징 선택이라는 두 가지 과정을 거쳐 실현된다.
8장에서 공부한 특징 벡터 x가 생성되고 나서는 인식률과 계산 시간에서 만족할 만한 성능을 보이면 이 특징 벡터를 그대로 사용하면 되나, 차원이 높아 계산시간이 과다하다든지 원하는 인식률을 밑돈다면 특징 선택을 적용해야만 한다.
특징 벡터는 차원이 낮을수록 좋고 분별력(discriminatory power)이 클수록 좋다. 분별력을 유지하거나 향상시키면서 특징 벡터의 차원을 줄이는 것이 중요한 목적이다. 특징 벡터의 차원을 줄엿을 때 얻는 이점 중 하나는 계산량의 감소이다. 또 다른 이점으로는 일반화 능력을 향상시킬 수 있다는 것이다.
9.1 특징의 분별력
9.1.1 직관적 이해
먼저 부류내 분산(within-class variance)과 부류간 분산(between-class variance)이라는 개념을 공부해보도록 하자. 부류내 분산은 같은 부류에 속하는 샘플이 얼마나 퍼져 있는지에 관한 척도이다. 부류간 분산은 서로 다른 부류의 분포가 얼마나 멀리 떨어져 있는지에 관한 척도이다. 특징 벡터는 ‘부류내 분산이 작을수록, 부류간 분산은 클수록’ 좋다.
실제 세계는 매우 높은 차원의 데이터를 다루므로 수학의 힘을 빌려 계산하여야한다.
9.1.2 분별력 측정
특징 벡터 x가 얼마나 좋은 지의 척도를 분별력이라 부른다. 또는 부류 분리(class separation) 능력이라 부른다. 널리 사용되는 척도 세 가지를 제시한다.
다이버전스
서로 다른 두 부류 $w_i, w_j$에 대해 이들이 확률 분포 $p(x|w_i), p(x|w_j)$의 거리가 멀 수록 x는 두 부류를 잘분별해준다고 할 수 있다. 두 확률 분포간 거리는 어떻게 측정할 수 있을까?
KL(Kullback-Leibler) 다이버전스를 활용할 수 있다. LL 다이버전스는 대칭이 아니므로 두 KL 다이버전스의 합을으로 정의하여 대칭성을 확보한다. 다음 식으로 정의되는 $d_{ij} $를 두 부류의 다이버전스(divergence)라 한다.
$$d_{ij} = KL(p(x|w_i), p(x|w_j)) + KL(p(x|w_j), p(x|w_i))$$
이를 M 부류에 관한 다이버전스로 확장하면 다음과 같다.
$$d=\sum_{i=1}^M \sum_{j=1}^M P(w_i)P(w_j) d_{ij}$$
다이버전스는 확률 분포 $p(x|w_i)$를 알고 있을 때만 적용이 가능하다는 단점이 있다.
훈련 샘플의 거리
부류 $w_i$에 속한 샘플 집합을 $X_i$라 하고 $X_i$의 k번째 샘플을 $x_i^k$라 하자. 두 부류간 거리는 다음과 같이 측정할 수 있다.
$$d_{ij} = \frac{1}{N_i N_j} \sum_{k=1}^{N_i} \sum_{m=1}^{N_j} dist(x_i^k, x_j^m)$$
여기서 $N_i$는 i부류의 샘플 개수이며 $dist(x_i, x_j)$는 두 샘플 간의 거리로 어떠한 거리 척도라도 적용이 가능하다. 보통 마할라노비스 거리 또는 유클리디언 거리를 사용한다.
분류기의 성능
더욱 현실적인 척도로 분류기를 이용하여 특징 벡터를 평가할 수 잇다. 이 방법의 장점은 사용하고자 하는 분류기의 딱 맞는 특징 벡터를 찾아낼 수 잇다는 점이다. 예를 들어 다이버전스를 사용한다면 최적의 특징 벡터를 결정하였다 하더라도 그것이 SVM에 최적이라는 보장은 업는 것이다. 단점은 새로운 특징마다 분류기를 훈련해야 하는데 이 때 드는 계산 시간이 과다하다는 점이다.
9.2 특징 선택 문제의 이해
개와 고양이를 분류하는데 특징 벡터에 눈의 개수라는 특징이 있으면 이 특징은 쓸모가 없다. 이러한 특징을 제거하고 차원을 하나 줄여야 한다. 또는 두 특징이 서로 중복성이 강한 경우가 잇다. 이러한 특징은 각각 의미있는 분별력을 가지나 둘 중 하나만 있어도 된다.
특징 선택(feature selection)은 d개의 측징을 갖는 특징 집합 F에서 $\hat{d}$개를 갖는 최적의 특징 부분 집합(feature subset) $\hat{F}$을 선택하는 문제이다. 주어진 집합에서 최적의 부분 집합을 찾는 문제를 부분 집합 선택(subset selectoin) 문제라 부른다. 최적의 기준은 앞의 분별력 중 하나를 사용하면 된다.
계산 시간이 충분하다면 모든 부분 집합을 이용하여 분별력을 기준으로 평가한 후 그 중 가장 높은 점수를 받은 부분 집합을 선택하면 된다. 이제 분별력 측정기가 부분 집합 S를 평가하기 위해 사용하는 함수를 $J(S)$라고 하자.
이러한 문제는 전형적인 조합적 최적화(combinatorial optimization) 문제이다. 조합적 최적화 문제는 문제의 크기가 커짐에 따라 계산량이 기하 급수적으로 증가하는 문제를 안고 있다. 특징 선택에서는 $ 2^d$개의 해로 정의되는 방대한 탐색 공간(search space)를 가진다. 결국 이 탐색 공간을 어떻게 효율적으로 뒤질 것인가라는 문제가 이 문제의 핵심이다.
임의 탐색(random search) 알고리즘은 임의로 특정 부분 집합을 선택하여 가장 좋은 것을 선택하는 알고리즘이다. 개별 특징 평가 알고리즘은 각 특징을 개별적으로 평가하고 그들 중 가장 좋은 것들만을 선택하는 방법이다. 이 방법은 특징들의 상관 관계를 아예 무시해버리는 경우이다.
9.3 전역 탐색 알고리즘
전역 탐색(global search) 알고리즘은 전체 특징 공간에서 가능성 있는 영역을 모두 탐색하는 알고리즘이다. 가능성 여부를 따지지 않고 모든 해를 평가하는 낱낱 탐색(exhaustive search) 알고리즘과 탐색 도중에 가능성이 없다고 판단되는 영역을 배제하는 한정 분기 알고리즘(branch-and-bound)이 잇다. 이 둘은 탐색 공간 전체를 대상으로 하므로 항상 전역 최적 해를 보장한다. 하지만 d가 커지면 현실적인 시간 내에 해를 구하지 못하는 한계가 있다.
한정 분기 알고리즘은 탐색 과정에서 얻은 정보를 이용하여 가능성이 없는 영역을 판단한다. 이러한 아이디어가 실현 가능하려면 단조성(monotonicity)라는 조건이 만족되어야 한다. 이 조건은 부분 집합에 새로운 특징을 추가했을 때 분별력이 저하되어서는 안된다는 것이다. 루트 노드를 원래 특징을 나타내도록 하고, 그 자식 노드로 갈 수록 특징 공간에서 특징을 하나씩 빼도록 하여 트리를 구성한다. 각각의 노드마다 분별력을 평가하여 현재 방문했던 노드보다 분별력이 좋아지지 않는 노드들은 제거하는 방법으로 해당 영역을 배제하도록 한다.
9.4 순차 탐색 알고리즘
특집 집합 $ F $의 두 부분 집합을 정의해보자. 알고리즘이 실행되는 어느 순간의 $F_1$선택되고 이 것의 여집합을 $F_2$라고 하자. 이제 지역 탐색 연산 두 가지를 정의해본다. 연산 add는 $F_1$에 특징 하나를 추가한다. 추가할 특징은 $F_2$에서 고르는데, 추가했을 때 가장 큰 성능 증가를 가져오는 특징 $x_k$가 $F_2$에서 $F_1$으로 이동한다. 연산 rem은 $F_1$에서 특징 하나를 제거한다. 제거했을 때 가장 적은 성능 저하를 가져오는 특징 $x_k$가 $F_1$에서 $F_2$로 이동한다.
이들 연산을 이용하여 순차 탐색(sequential search) 알고리즘 중에서 가장 단순한 SFS (sequential forward search) 알고리즘을 사용할 수 있다.
SFS 알고리즘은 공집합인 $F_1$을 가지고 출발하여 한번에 하나씩 특징을 추가해 나간다.
SBS (sequential backward search) 알고리즘은 SFS와 탐색 방향이 반대이다. SBS 는 $F_1=F$에서 출발하여 한번에 하나씩 특징을 제거해 나간다.
SFS는 한번 추가한 특징은 다시 빼낼 수 없고, SBS는 한번 제거한 특징을 다시 넣을 수 없는 단점을 가진다. PTA (plus-p-take-away-q) 알고리즘은 추가와 제거를 번갈아 가며 수행하여 이러한 단점을 극복한다.
SFFS (sequential forward floating search), SBFS (sequential backward floating search) 알고리즘은 미리 정해놓은 크기만큼 추가, 제거를 하지 않고 상황에 맞게 적응적으로 그 크기를 결정한다.
9.5 통계적 탐색 연산을 가진 알고리즘
순차 탐색 알고리즘이 지역 최적 점에 빠질 위험이 이기 때문에 이것을 극복하기 위한 알고리즘이 고안되엇다. 시뮬레이티드 어닐링(simulated annealing)은 현재 해보다 열등한 지점으로 이동하는 연산도 가지고 있다. 열등한 해로 이동할 확률은 온도라는 매개변수에 따르는데 처음 출발할 때는 온도가 높고 갈수록 낮춘다. 온도가 높을 수록 열등한 해로 이동할 확률은 크다.
유전 알고리즘(genetic algorithm, GA)이 다른 알고리즘과 큰 차이를 가지는 것은 어느 순간 해를 하나만 가지는 것이 아니라 여러 해를 포함한 해 집단(population)을 가진다는 것이다. 시간 t의 해들이 교배(crossover) 연산을 통하여 자식 해를 생성한다. 교배를 하는 해는 난수를 생성하여 선택하는데 좋은 해가 선택될 확률이 높도록 해야한다. 이렇게 하여 세대가 거듭될 수록 해의 품질은 조금씩 개선되는 것이다.
이 외에도 생물의 동작 원래를 모방한 인공 면역 시스템(artificial immune system, AIS), 개미 군ㄺ 최적화(ant colony optimization, ACO), 개체 무리 최적화(swarm optimization, SO) 알고리즘들이 활발히 연구되고 있다.