패턴 인식 (12) 혼성 모델
 패턴인식, 오일석 지음/교보문고 |
12. 혼성 모델
특징 추출과 선택, 분류, 군집화 문제를 푸는 알고리즘은 아주 다양하다. 어느 방법이 가장 좋은가? 이 질문은 크게 두 가지 다른 상황에서 생각해 볼 수 있다. 첫째, ‘특정 문제가 주어진’ 상황에서 그 문제를 가장 높은 성능으로 풀 수 있는 알고리즘은 어느 것인가? 이에 대한 답을 자동으로 구하는 방법은 없어 충분히 많은 데이터를 가지고 성능 실험을 거쳐 최선의 방법을 찾아내는 수밖에 없다. 둘째, 다른 모든 방법을 능가하는 ‘보편적으로 우수한’ 알고리즘이 있는가? 이것은 패턴 인식의 근간에 해당하는 질문이고 이에 대한 답을 구하기 위해서는 과학적인 접근을 해야한다. 물론 현재까지 개발된 알고리즘 중에 그런 것이 없는 것은 확실하다. 특정 문제에서 알고리즘 간에 우열이 보이기 때문이다.
여기서는 단일 알고리즘의 한계를 인정하고 여러 알고리즘을 결합하는 혼성 모델(hybrid model)에 대해 공부한다. 대체적으로 공통된 의견은 여러개를 결합하면 가장 좋은 단일 알고리즘보다 좋아진다는 것이다.
12.1 알고리즘의 성능 특성
많은 알고리즘의 특성을 여러 측면에서 바라볼 수 있다. 공학적인 관점에서는 특정 응용 도메인에 만족스러운 성능을 갖는 시스템을 구축하는 것이 목적이고, 과학적인 관점은 알고리즘 성능의 본질적인 면을 통찰하는 것이 목적이다. 공학적인 관점에서는 패턴 인식이 다분히 실험적인 학문임을 강조한다. 과학적인 관점에서는 공짜 점심 없음 정리와 바이어스-분산 딜레마 현상을 살펴 본다.
공학적 관점
필기 숫자 인식 문제를 생각해보자. 어떤 은행의 전표에 나타나는 필기 숫자를 자동으로 인식하는 문제가 주어져 있다고 생각해보자. 어떤 알고리즘은 숫자 뿐 아니라 여러 언어의 문자 그리고 다른 나라 사람의 필기체나 우편물에 나타나는 필기 숫자 등에 두루두루 어느 정도의 일정한 성능을 보이지만, 주어진 문제에서만큼은 더 높은 성능을 보이는 알고리즘이 있다고 생각해보자. 이럴 때 공학적인 판단에서는 후자의 알고리즘을 선택하여야 할 것이다. 후자와 같은 성능을 얻으려면 어떻게 설계해야할까? 가장 신경써야 하는 것은 주어진 문제 영역을 포괄하는 충분히 많은 양의 충분히 높은 품질의 샘플을 수집하는 것이다.
공짜 점심 없음
탐색과 최적화 문제에 대해 ‘모든 문제에 대해 다른 모든 알고리즘을 능가하는 알고리즘이 있나’ 라는 질문에 대하여 공짜 점심 없음(no free lunch, NFL) 정리가 있다.
바이어스-분산 딜레마
선형 모델을 선택하건 보다 정확한 3차 모델을 선택하건 가능한 모든 샘플 집합을 고려한 평균 제곱 오차는 같다. 단 오차의 내용이 서로 다르다. 매개 변수가 적은 단순한 모델은 바이어스 항의 값이 크게 되는 반면 분산 항의 값은 작다. 반대로 3차와 같이 복잡한 모델은 바이어스가 작은 반면 분산이 커지게 된다. 바이어스의 제곱과 분산을 합한 값은 복잡한 모델이나 간단한 모델 모두 같다는 법칙이 성립한다. 이 현상을 바이어스-분산 딜레마(bias-variance dilemma)라 부른다. 또는 법칙으로 간주하여 보존 법칙(conservation law)라 부른다.
회귀이건 분류이건 샘플 집합의 크기 N이 커지면 분산의 값이 따라서 작아진다는 사실이 밝혀져 있다. 이것이 의미하는 바는 평균 제곱 오차를 줄이기 위해서는 N을 크게 하라는 것이다. 따라서 패턴 인식 시스템 설계자는 충분히 큰 데이터 베이스를 확보해야 한다. 바이어스는 보다 정확한 모델을 선택하면 줄일 수 있다.
12.2 재 샘플링에 의한 성능 평가
패턴 인식 시스템을 설계하고 구현할 때 우리가 가진 데이터는 훈련 집합과 테스트 집합뿐이다. 훈련 데이터베이스와 테스트 데이터베이스의 품질이 시스템 성능에 지대한 영향을 미치고, 모델 선택에는 별도의 검증 집합이 필요하다. 또한 바이어스-분산 딜레마를 통해 충분히 큰 N을 확보하는 것 또한 필요하다. 그런데 현실적으로 데이터 수집에 상당한 비용이 든다는 것이 문제다. 따라서 데이터 양이 충분치 않을 경우 재 샘플링(resampling) 방법을 사용하여야 한다. 기본 아이디어는 같은 샘플을 여러 번 사용하는 것이다.
교차 검증
N개의 샘플을 수집해 왔다고 하자. 적절한 비율로 훈련 집합과 테스트 집합으로 나눈 다음 시스템 설계에 들어가면 된다. 하지만 현실적으로 대부분 경우 샘플의 양이 충분치 않다. 이러한 경우 사용할 수 있는 방법이 있다. 샘플을 k개의 부분 집합으로 등분한다. 분류기를 k-1개의 부분 집합으로 학습시키고 나머지 한 개의 부분 집합으로 학습된 분류기의 성능을 측정한다. 이 과정을 서로 다른 부분 집합으로 k번 수행하여 얻은 성능을 평균하여 그것을 분류기의 성능으로 취한다. 이러한 성능 측정 방법을 k-겹 교차 검증(k-fold cross validation)이라 한다. 극단적으로 k=N으로 하면 매번 한 개의 샘플로 테스트를 하는 셈이 된다. 이런 경우를 하나 남기기(leave-one-out) 또는 잭 나이프(jackknife) 기법이라 한다.
교차 검증을 써야하는 상황을 두 가지로 나눌 수 있다. 하나는 샘플 집합이 하나 뿐인데 그것을 훈련과 테스트 집합으로 나누어 써야 하는 경우이다. 두 번째 상황은 훈련 집합과 테스트 집합이 별도로 준비되어 있는데 모델 선택을 위해 검증 집합이 필요할 때이다. 이때는 훈련 집합을 k겹 교차하여 훈련과 검증 목적으로 사용하면 된다. 교차 검증은 가지고 있는 샘플의 대부분을 학습에 쓸 수 있다는 면에서 매력적이다. 특히 k가 N에 가까워질수록 그렇다. 하지만 k가 커짐에 따라 계산 시간이 많아지는 부담이 있다.
붓스트랩
붓스트랩 기법은 중복을 허용한다. N개의 샘플을 가진 샘플 집합 X가 있다고 하자. 집합 X에서 N개의 샘플을 중복이 가능하도록 임의로 뽑는다. 이러한 샘플링 작업을 독립적으로 T번 수행하여 T개의 샘플 집합을 얻어 성능을 각각 측정하고 그 결과를 평균한 값을 최종 성능으로 취한다.
12.3 혼성 모델의 발상
패턴 인식에서 혼성 모델(hybrid model)이란 각자가 가진 서로 다른 능력을 하나로 모아 보다 성공적인 결과를 얻기 위함이다. 혼성 모델 중 가장 활발히 연구되는 주제는 분류기 앙상블(classifier ensemble)이다.
12.3.1 동기
혼성 모델에서 여러 모델이 협동하는 방식이 여럿 있는데 그 중 대표적인 두 가지를 보여준다. 첫 번째는 같은 문제에 대해 서로 다른 여러 알고리즘이 해를 구하고, 결합 알고리즘이 그들을 결합하여 최종 해를 만드는 방식이다. 여러 개의 분류기를 만들고 그들의 출력을 결합하는 다중 분류기 방식이 여기에 속한다. 두 번째는 연산 공유(operation sharing) 방식이다. 해를 구하는데 두 개 이상의 알고리즘이 개입하는 방식이다. 여기서는 결합 방식을 주로 다룰 것인데, 이러한 방식은 여러 이름으로 알려져 있다. 다중 분류기 결합(multiple classifier combination), 다중 분류기 시스템(multiple classifier system), 전문가 위원회(committee of experts), 전문가 혼합(mixture of experts), 분류기 풀(classifier pool), 분류기 앙상블(classifier ensemble) 등이 있다.
분류기 앙상블에서 중요한 개념 중 하나는 다양성(diversity)이다. 앙상블에 참여한 분류기가 모두 같은 분류 결과를 출력한다면 결합에 의해 얻는 이득은 전혀 없게 된다. 어떤 분류기가 틀리는 샘플은 다른 분류기가 맞추는 경향을 내포하고 있어야만 한다.
분류기 앙상블을 구현하기 위해서는 크게 세 가지 문제를 다루어야 한다. 먼저 앙상블이라 부르는 다중 분류기를 생성해야 한다. 다음 이들 중에 특히 효과적인 분류기 부분 집합을 선택하는 앙상블 선택은 선택적으로 수행할 수 있다. 앙상블 결합은 다중 분류기의 출력을 하나로 결합하는 역할을 한다.
12.3.2 이유
- 나쁜 운을 피할 수 있다. 현장에 사용할 시스템을 설계하는데 있어 최적의 분류기 모델과 매개 변수를 찾는 것은 결코 쉬운 일이 아니다.
- 성능 향상을 꾀할 수 있다.
- 데이터 양에 따른 어려움을 극복할 수 있다.
- 데이터 질에 따른 어려움을 극복할 수 있다.
- 다중 센서 시스템에서 효과적이다.
- 결정 경계가 너무 복잡한 경우에 효과적일 수 있다.
- 점진 학습(incremental learning)이 가능하다.
12.4 앙상블 생성
앙상블 생성을 위한 가장 대표적인 방법으로 훈련 집합을 재 샘플링하는 기법이 있다. 재 샘플링에는 배깅과 부스팅이 있다. 앙상블을 구성하는 분류기 각각은 결합 과정에서 하나의 요소로 작용하기 때문에 요소 분류기(component classifier) 또는 기초 분류기(base classifier)라고 부른다.
서로 다른 분류 알고리즘을 사용하는 방식도 있다. 더 나아가 이들 세 가지 알고리즘 각각에 대해 적절한 앙상블 생성 방법으로 분류기를 더 만들 수도 있다. 또 다른 대안으로 특징 벡터의 부분 공간을 사용하는 방법도 있다. 이 방법에서는 서로 다른 특징 부분 집합을 만들고 각각의 부분 집합에 대해 하나의 분류기를 만든다. 이런 기법으로 결정 트리 앙상블을 생성한 것을 결정 숲(decision forest)라 한다.
앙상블을 구성하는 분류기는 다양해야 한다. 그렇지 않다면 성능 향상 효과를 기대하기 힘들다. 하지만 앙상블 생성은 대부분 휴리스틱한 방법을 사용한다. 따라서 다양성 측면에서 최적의 앙상블을 생성한다고 말할 수 없다.
12.4.1 배깅
배깅(bagging)은 붓스트랩을 다중 분류기 생성 기법으로 확장하였다고 보면 된다. 이름도 붓스트랩을 확장한 bootstrap aggregating에서 유래하였다. 붓스트랩으로 T개의 샘플 집합을 얻었다고 하자. 배깅은 그 중 하나를 훈련 집합으로 사용하여 분류기 하나를 만든다. 이러한 분류기 학습을 여러개에 대해 독립적으로 수행하여 T개의 분류기를 만든다. 분류 알고리즘은 어떤 것을 사용해도 좋다. 이렇게 만든 분류기 앙상블을 투표와 같은 방법으로 결합하면 된다.
12.4.2 부스팅
부스팅(boosting)은 배깅에 비해 보다 정교한 재 샘플링 연산을 사용한다. 부스팅에서는 t번째 분류기와 그 다음 t+1번째 분류기가 서로 연관성을 가지고 만들어진다. X의 샘플은 t번째 분류기가 맞추는 것과 틀리는 것으로 나눌 수 있다. 맞춘 샘플은 이제 인식이 가능해졌으므로 가중치를 낮추어도 되나 틀린 샘플은 여전히 까다로운 상대이므로 가중치를 높여준다. 가중치는 t+1번째 샘플 집합을 뽑는데 중요한 역할을 한다. 즉 가중치가 높은 샘플이 뽑힐 가능성을 높게 조절하는 정책을 사용한다. 널리 사용되는 방법은 AdaBoost이다.
12.5 앙상블 결합
앙상블 결합은 다중 분류기의 출력을 결합하여 하나의 분류 결과를 만드는 과정을 일컫는다. 따라서 요소 분류기의 출력 특성에 대해 먼저 살펴보아야 한다. 요소 분류기의 출력은 아래 세 가지 형태 중의 하나를 취한다.
- 부류 표지(class label) : 패턴 x는 부류 i에 속한다.
- 부류 순위(class ranking) : 패턴 x가 i 부류에 속할 가능성의 순위는 $r_i$이다. 이것을 모든 부류에 대해 쓰면 순위 벡터가 된다.
- 부류 확률(class priobability) : 패턴 x가 부류 i에 속할 확률은 $p_i$이다. 이것을 모든 부류에 대해 쓰면 확률 벡터가 된다.
부류 확률은 쉽게 부류 순위와 부류 표지로 바꿀 수 있다. 또한 부류 순위도 부류 표지로 바꿀 수 있다. 하지만 반대의 과정은 불가능하다.
12.5.1 부류 표지
이 방법은 부류 표지 벡터를 사용하여 다중 분류기를 결합한다. 분류기가 T개 있으므로 표지 벡터가 T개 있다.
다수 투표
다수 투표(majority voting)는 사람들이 가장 널리 쓰는 의사 결정 방식을 흉내낸 것이다. 미지의 패턴 x를 T개의 분류기로 분류한 뒤, 가장 많은 부류로 선택된 것을 출력으로 하는 것이다.
가중 다수 투표
가중 다수 투표(weighted majority voting)은 다수 투표에서 각 분류기마다 가중치를 다르게 주어 계산하는 방식이다.
행위 지식 공간
어떤 분류기는 특정 부류에 대해 보다 신뢰도 높은 분류를 해 주는 경우가 잇다. 이러한 상황을 감안하여 분류기의 특성을 감안할 수 있다. 하나의 방법으로 행위 지식 공간(behavior knowledge space, BKS)가 있다. 이 방법은 T개의 분류기 출력 조합을 모두 나열하고 그들에 대해 발생 빈도를 센다. 이렇게 하여 BKS 표를 구성한다. 인식은 T개의 분류기로 분류한 뒤 출력 조합을 만든다. 그리고 이 출력 조합에 해당하는 행을 BKS에서 참조하여 가장 빈도가 높은 분류로 최종 분류한다.
12.5.2 부류 순위
Borda 계수
순위 벡터 R에 따라 각 부류에 점수를 부여한다. 높은 순위에 높은 점수를 부여하는 것이다. 단순한 방법으로 r 순위에 M-r 점을 부여하는 방법과 r 순위에 1/r 범을 부여하는 방법이 있다.
Borda 꼐수에 의한 결합은 아주 단순하다. T개의 분류기로부터 순위 벡터를 얻은 후 이들을 점수 벡터로 변환한다. 이제 T개의 점수 벡터를 모두 더한 후 가장 큰 값을 갖는 분류를 사용한다.
12.5.3 부류 확률
합, 가중 합, 최소, 최대, 메디언, 그리고 곱 규칙
합, 가중합, 최대, 최소, 메디언, 곱의 방법으로 구한 벡터 중 가장 큰 값을 갖는 부류로 분류하면 된다.
12.6 앙상블 선택
앙상블 생성과 앙상블 결합은 반드시 있어야 할 요소이나 앙상블 선택은 선택적으로 사용될 수 있다.
12.6.1 다양성 척도
7가지 정도의 척도를 소개한다.
- Q-통계(Q-statistics)
- 상관 계수(correlation coefficient)
- 불일치(disagreement)
- 이중 과실(double fault)
- 엔트로피(entropy)
- Kohavi-Wolpert 분산
- 평가자 동의(interrater agrrement)
12.6.2 선택 알고리즘
앞에서 공부한 특징 선택 알고리즘을 도입하여 사용할 수 있다.
혼성 유전 알고리즘은 혼성 모델의 일종이다.
혼성 유전 알고리즘
유전 알고리즘은 문제 공간의 넓은 범위를 탐색할 수 잇으나 지역 최적 점 근처에서 미세 조정력이 약하기 때문에 긴 실행시간을 필요로 한다. 따라서 혼성 유전 알고리즘(hybrid genetic algorithm, HGA)를 적용하고 있다. 혼성 유전 알고리즘은 자식 염색체를 해 집단에 넣기 전에 지역 탐색 연산을 통해서 품질을 향상시킨다.
12.7 알고리즘을 바라보는 관점
개성과 통일
사람과 마찬가지로 알고리즘도 개성이 있다. 패턴 인식 설계자들은 알고리즘이 갖는 이러한 개성을 충분히 이해하고 그것을 적절히 활용해야 한다. 동시에 다양한 개성에도 불구하고 이론적 뿌리를 살펴보면 통일성을 발견할 수 있다. 방법론에 대한 깊은 이해와 높은 통찰력을 통해 기술 돌파(breakthrough)를 창발시켜야 한다.
해 봐라.
알고리즘 선택에 마술은 없다. 직접 해 보는 것이 최선이다. 알고리즘의 특성을 제대로 이해하고 적재적소에 활용해야 한다.