유전 알고리즘 기반 귀납적 학습 환경에서 다중 분류기 시스템의 구축을 위한 메타 학습법

A Meta-learning Approach for Building Multi-classifier Systems in a GA-based Inductive Learning Environment

  • cc icon
  • ABSTRACT

    본 논문은 유전 알고리즘 기반 귀납적 학습 환경 하에서 메타 학습법을 이용한 다중 분류기 시스템의 구축에 관한 것이다. 메타 학습법을 이용한 다중 분류기 시스템의 구축에서 분류기는 일반 분류기와 메타 분류기로 구성된다. 메타 분류기는 사례에 대한 일반 분류기의 분류 결과에 학습 알고리즘을 적용하여 얻어진다. 분류시스템의 의사 결정 과정에서 메타 분류기의 역할은 일반 분류기의 분류 결과를 평가하여 최종 의사 결정 과정에의 참여 여부를 결정하는 것이다. 분류 시스템은 분류기의 분류 결과가 옳은 것으로 평가된 결과들만 취합하여 이를 바탕으로 최종 분류 결과를 도출해 낸다. 메타 학습법이 다중 분류기 시스템의 성능에 미치는 영향을 다수의 사례 집합을 이용하여 평가하였다.


    The paper proposes a meta-learning approach for building multi-classifier systems in a GA-based inductive learning environment. In our meta-learning approach, a classifier consists of a general classifier and a meta-classifier. We obtain a meta-classifier from classification results of its general classifier by applying a learning algorithm to them. The role of the meta-classifier is to evaluate the classification result of its general classifier and decide whether to participate into a final decision-making process or not. The classification system draws a decision by combining classification results that are evaluated as correct ones by meta-classifiers. We present empirical results that evaluate the effect of our meta-learning approach on the performance of multi-classifier systems.

  • KEYWORD

    유전 알고리즘 , 귀납적 학습 , 메타 학습법 , 다중 분류기 시스템

  • Ⅰ. 서 론

    학습 시스템은 시스템의 구현을 위해 이용한 학습 알고리즘의 수에 따라 단일 전략 학습 시스템과 다중 전략 학습 시스템으로 구분된다. 단일 전략 학습 시스템에서는 학습 시스템이 결정 트리나, 신경망, 결정 규칙 등의 여러 계산 메커니즘 중 하나의 계산 메커니즘하에 귀납법, 연역법, 유추 등의 추론 방법 중 하나의 추론 방법에 준하여 구현된 학습 알고리즘을 이용하여 구축된다. 이에 반해 다중 전략 학습 시스템[1,2]에서는 다수의 추론 형태와 계산 메커니즘을 이용하여 학습 시스템이 구축된다.

    각각의 학습 알고리즘은 알고리즘 고유의 표현 방법과 경험적 탐색 방법으로 인해 같은 문제에 대해 다른 학습 능력을 갖게 되는데 Michell[3]은 이를 귀납적인 기울어짐(inductive bias)이라 하였다. 다중 전략 학습 시스템에 대한 연구의 근본적인 목적은 결국 여러 다른 학습 알고리즘이 갖고 있는 고유의 학습 능력 즉, 귀납적인 기울어짐을 적절히 통합하여 서로 보완적인 작용을 하게 함으로써 학습 능력이 보다 향상된 시스템을 구축하고자 하는 것이다.

    다중 전략 학습 시스템에 관한 연구의 일환으로 주어진 사례의 집합에 대해 서로 다른 학습 알고리즘을 이용하여 사례들을 분류할 수 있는 분류기를 습득한 후 이들을 통합하여 보다 성능이 향상된 분류 시스템을 구축하기 위한 연구가 활발히 진행되어 왔다[4]. Lorrentz et. al.[5]과 Nguyen et. al.[6]은 그들의 논문에서 다수의 분류기를 통합하여 최종 분류 결과를 제시하기 위한 기법을 제시하였고, Major and Ragsdale[7]은 특정 영역에 속한 사례를 그 영역에 대해 좋은 성능을 보이는 분류기가 분류하도록 함으로써 분류 시스템의 성능을 향상시키는 기법을 제안하였다. Ishibuchi와 그의 그룹[8]은 주어진 사례의 집합으로부터 퍼지 분류 규칙을 습득하는 유전 알고리즘 기반 학습 시스템을 이용하여 다수의 분류기를 구한 후 이들을 이용하여 분류 시스템을 구축함으로써 분류 시스템의 성능을 향상 시키는 연구를 하였다.

    본 논문은 유전 알고리즘 기반 귀납적 학습 환경 하에서 메타 학습법을 이용한 다중 분류기 시스템의 구축에 관한 것이다. 메타 학습법은 분류기의 분류 결과에 학습 알고리즘을 적용하여 분류기의 편향성을 학습한 메타 분류기를 습득하는 기법이다[9]. 본 논문에서 제시한 메타 학습법을 이용한 다중 분류기 시스템의 구축에서 분류기는 일반 분류기와 메타 분류기로 구성된다. 일반 분류기는 주어진 사례 집합에 대해 학습 알고리즘을 적용하여 습득한다. 메타 분류기는 사례에 대한 일반 분류기의 분류 결과에 학습 알고리즘을 적용하여 얻어진다. 분류시스템의 의사 결정 과정에서 메타 분류기의 역할은 일반 분류기의 분류 결과를 평가하여 최종 의사 결정 과정에의 참여 여부를 결정하는 것이다. 분류 시스템은 일반 분류기의 분류 결과가 옳은 것으로 평가된 결과들만 취합하여 이를 바탕으로 최종 분류 결과를 도출해 낸다.

    본 논문의 구성은 다음과 같다. 2장에서는 일반 분류기와 메타 분류기를 습득하기 위한 유전 알고리즘 기반 귀납적 학습 환경을 간략히 소개하고 3장에서는 분류 시스템의 성능 향상을 위한 메타 학습법에 대해 설명한다. 4장에서는 메타 학습법이 다중 분류기 시스템의 성능 향상에 미치는 영향을 평가하고 5장에서는 결론 및 향후 과제에 대해 설명한다.

    Ⅱ. 분류 규칙 습득을 위한 유전 알고리즘 기반 학습 환경

    본 장에서는 메타 학습법을 구현한 유전 알고리즘 기반 귀납적 학습 환경을 학습 시스템이 습득하고자 하는 분류 규칙의 구문 형태 및 의미, 분류 규칙의 습득을 위한 유전 알고리즘을 중심으로 소개 한다

    분류 규칙의 습득을 위한 유전 알고리즘 기반 학습 환경에서 훈련 사례 집합내의 사례는 속성 A1, A2, …, An에 대한 값 a1, a2, …, an과 사례가 속한 클래스 c로 구성된 리스트, (a1, a2, …, an, c)의 형태로 표현된다. 사례 집합 내의 임의의 사례 e의 속성 Ai에 대한 값 ai는 사례 집합 내에서 속성 Ai에 대해 e가 갖고 있는 속성 값보다 적은 값을 갖는 사례의 수를 e의 속성 값과 다른 값을 가지는 사례의 수로 나누어 0과 1사이의 값을 갖도록 정규화한 값이다.

    학습 시스템은 유전 알고리즘을 이용하여 주어진 사례의 집합으로부터 PROSPECTOR[10]에서 사용한 규칙과 유사한 "If E then C with S = s, N =n" 형태의 규칙들을 습득한다. 이들 습득된 규칙으로 구축된 분류 시스템에서는 주어진 사례가 어떤 특정 클래스 C에 속할 사전 가능성 O(C)를 사례가 C에 속할 확률 P(C)로부터 O(C) = P(C)/(1 - P(C))의 식을 이용하여 구한다. P(C)는 사례 집합 내에서 C에 속하는 사례가 차지하는 비율로 부터 구한다. 주어진 사례에 대해 각각의 규칙들은 규칙의 조건(즉, E)에서 고려하는 속성에 대해 사례가 갖고있는 속성 값에 따라 사례가 규칙의 결론인 C에 속할 가능성에 대한 승수를 N과 S사이의 값으로 제공한다. 규칙은 사례가 규칙의 조건을 완전하게 만족하면(즉, P(E') = 1) S의 값을, 불만족 시에는(즉, P(E') = 0) N의 값을, 0 < P(E') < 1인 경우에는 P(E')의 값에 비례하여 N과 S사이의 값을 제공한다. 분류 시스템은 주어진 사례에 대해 사례가 C에 속할 사전 가능성 O(C)에 C를 결론으로 갖는 규칙들이 제공하는 가능성에 대한 승수를 베이지안 추론법에 준하여 취합하여 C에 속할 사후 가능성 O(C')을 구한다. 분류 시스템은 각각의 클래스에 대해 사례가 속할 사후 가능성을 구한 후 사후 가능성이 가장 큰 클래스를 사례가 속한 클래스로 선택한다.

    분류 시스템이 사례를 분류하는 과정은 다음과 같다:

    image

    학습 시스템이 주어진 사례의 집합으로부터 습득하는 규칙의 형태 중 하나는 "If is-high(A) then C with S = s, N = n"의 형태로 이 타입의 규칙은 고려대상이 되는 속성 A의 값의 상대적인 높고 낮음에 따라 주어진 사례가 클래스 C에 속할 가능성에 대한 승수를 N과 S사이의 값으로 제공한다. 다른 하나는 "If is-close(A, a) then C with S = s, N= n"의 형태로 고려하는 속성 A의 값이 어떤 특정 값 a에 근사한 정도에 따라 클래스 C에 대해 N과 S사이의 값을 제공한다. 학습 시스템은 주어진 사례의 집합에 대해 그 사례들을 분류하기 위한 규칙 집합(즉 주어진 사례들을 분류하기 위해 필요한 속성들을 적절히 고려한 is-high 규칙과 is-close 규칙들)을 각각의 규칙에 필요한 s, n, 상수 a의 값(is-close 규칙에 한 함)과 함께 유전 알고리즘을 이용하여 습득하는 것이다.

    유전 알고리즘을 이용한 학습 시스템의 구현에서 개체 집단은 일정 수의 규칙 집합으로 구성되며 각각의 규칙 집합은 임의의 수의 규칙으로 구성된다. 즉, 개체 집단의 구성원은 임의의 수의 규칙들로 이루어진 규칙의 집합이다. 초기의 개체 집단은 난수 발생기를 이용하여 임의의 수의 규칙들로 이루어진 일정 수의 규칙 집합을 생성함으로써 얻어진다. 계속되는 진화 과정에서는 적합도에 비례하여 선택된 규칙 집합에 대해 유전 연산자를 적용하여 새로운 개체 집단을 생성하는 과정을 반복한다. 각각의 규칙 집합의 적합도는 규칙 집합이 주어진 사례 집합 내의 사례들을 어느 정도 정확하게 분류 할 수 있는가 하는 분류의 정확도를 이용하여 평가한다. 주어진 개체 집단에서 새로운 개체 집단을 생성하는 과정을 원하는 해가 얻어질 때까지 반복한다. 유전 연산자로는 교배 연산자, 돌연변이 연산자가 이용되었다. 교배 연산자는 선택된 2개의 규칙 집합 내의 규칙들의 일부를 교환하여 새로운 규칙 집합을 생성하고 돌연변이 연산자는 규칙 집합 내의 하나의 규칙을 새로운 규칙으로 대체함으로써 새로운 규칙 집합을 생성한다.

    Ⅲ. 메타 학습법

    2장에서 설명한 학습 환경 하에서 습득된 일반 분류기에 대해 메타 분류기를 습득하는 과정은 다음의 두단계로 이루어진다. 첫 단계는 메타 분류기의 습득을 위한 사례 집합을 만드는 단계로 이 단계에서는 우선 주어진 사례 집합을 일반 분류기를 이용하여 분류한 후 사례가 갖고 있는 기존의 속성에 사례에 대한 일반 분류기의 분류 결과와 분류 결과의 옳고 그름을 나타내는 새로운 속성을 추가하여 메타 분류기의 습득을 위한 사례 집합을 만든다. 그림 1은 메타 분류기의 습득을 위한 사례 집합의 예를 보인 것이다.

    그림 1에서 (a)에 기술 된 사례들을 일반 분류기로 분류 하였을 때, 사례 e1, e2, e3, e6는 올바르게 분류하고 사례 e4, e5는 각 각 클래스 0와, 클래스 1에 속한 것으로 잘 못 분류 하였다고 가정하면 주어진 사례 집합 (a)로 부터 메타 분류기의 습득을 위한 사례 집합 (b)를 얻을 수 있다. (b)에서 속성 CR은 일반 분류기의 분류 결과를, CE는 일반 분류기의 분류 결과에 대한 평가 결과를 값으로 갖는 속성이다. 올바르게 분류한 경우 평가 결과에 대한 속성 값은 1을 갖고 잘 못 분류된 경우에는 0을 갖는다. 다음 단계에서는 메타 분류기 습득을 위한 사례 집합과 2장에서 설명한 학습 시스템을 이용하여 메타 분류기를 습득한다. 이러한 과정을 통해 습득된 메타 분류기는 일반 분류기가 어떤 사례를 올바르게 분류하고 어떤 사례를 잘 못 분류하는지를 평가할 수 있게 된다. 그림 2는 메타 분류기를 습득하는 과정을 보인 것이다.

    메타 학습법 하에서 구축된 다중 분류기 시스템에서 분류기는 일반 분류기와 메타 분류기로 구성되며, 메타 분류기의 역할은 일반 분류기의 분류 결과를 평가하여 최종 의사 결정 과정에의 참여 여부를 결정하는 것이다. 분류 시스템은 사례에 대한 분류 과정에서 일반 분류기의 분류 결과 중 메타 분류기가 올바른 것으로 평가한 경우에 해당 하는 결과만 취합 하여 주어진 사례가 속할 클래스를 최종적으로 결정한다.

    Ⅳ. 메타 학습법이 분류 시스템의 성능에 미치는 영향 평가

    메타 학습법이 분류 시스템의 성능 향상에 미치는 영향을 다음의 사례 집합을 이용하여 평가 하였다.

    메타 학습법이 분류 시스템의 성능에 미치는 영향을 평가하려면 일반 분류기의 습득을 위한 사례 집합, 메타 분류기의 습득을 위한 사례 집합, 그리고 분류 시스템의 성능을 평가하기 위한 사례 집합이 필요하다. 이를 위해 우선 각각의 사례 집합을 크기가 같은 두 개의 부분 집합으로 나누어 그 중 하나를 일반 분류기의 습득을 위한 사례 집합으로 사용하고 나머지 하나는 다시 크기가 같은 두 개의 부분 집합으로 나누어 하나는 메타 분류기의 습득에, 다른 하나는 구축된 다중 분류기 시스템의 성능 평가에 사용하였다. 다중 분류기 시스템내에 사용될 분류기의 습득 과정은 다음과 같다. 우선 일반 분류기의 습득을 위한 사례 집합에 대해 2장에서 설명한 학습 시스템을 이용하여 일반 분류기를 구한다. 그런 다음 이를 이용하여 메타 분류기의 습득을 위해 준비해 둔 사례 집합 내의 사례 들을 분류한 후 그 결과를 반영하여 3장에서 기술한 방법에 따라 메타 분류기의 습득을 위한 사례 집합을 만든다. 이 사례 집합에 대해 학습 시스템을 실행하여 메타 분류기를 습득한다. 2장에서 설명한 학습 환경 하에서는 이 과정을 원하는 만큼 반복하여 필요로 하는 수의 분류기를 습득할 수 있다. 일반 분류기의 습득과정에서 학습 시스템의 유전 알고리즘을 위한 매개변수로 개체 집단의 크기는 15, 교배연산자와 돌연변이 연산자를 위한 교차율과 변이율은 각각 98%, 40%를 사용하였다.

    다중 분류기 시스템에서는 시스템이 채택한 의사 결정 기법에 따라 분류기의 분류 결과를 취합하여 최종 분류 결과를 결정한다. 따라서 단순히 일정 수의 분류기를 이용하여 다중 분류기 시스템을 구축하는 대신 시스템이 사용하는 의사 결정 기법에 대해 최적의 분류기 조합을 찾아 다중 분류기 시스템을 구축하면 시스템의 성능을 더욱 향상시킬 수 있다. 본 논문에서는 학습 시스템을 반복 실행하여 얻어진 10개의 분류기의 집합으로부터 유전 알고리즘을 이용하여 최적의 분류기의 조합을 찾아내어 이를 이용하여 분류 시스템을 구축 한후 평가 사례를 이용하여 분류 시스템의 성능을 평가하였다. 이와 같은 실험을 각각의 사례 집합에 대해 5회씩 반복하였다. 다중 분류기 시스템의 의사 결정 기법으로는 단순 보우팅 기법을 사용하였다.

    단일 분류기를 이용하여 구축한 분류 시스템과 메타학습법을 이용한 다중 분류기 시스템의 성능을 표 1에 비교하였다. 표 1에서 '단일'은 하나의 분류기를 이용하여 분류 시스템을 구축한 결과를 '다중'은 다중 분류기 시스템의 성능을 나타낸다. 표 1은 단일 분류기 시스템이 붓꽃 사례 집합에 대한 실험에서 평균적으로 훈련 사례 집합을 98.7%, 평가 사례 집합 내의 사례들의 94.1%를 올바르게 분류한 반면에 다중 분류기 시스템은 훈련 사례 집합을 100.0%, 평가 사례 집합 내의 사례들의 96.2%를 올바르게 분류하였음을 보인다. 콩의 질병과 관련된 사례 집합에 대해서는 메타 학습법을 이용한 다중 분류기 시스템의 성능이 단일 분류기에 비해 12.9% 향상되었음을 보인다. 다른 학습 알고리즘과의 비교를 위하여 신경망의 경우를 고려해 보면 붓꽃 사례 집합에 대해서는 95.9%, 레이더 시그널 사례 집합에 대해서는 86.8%의 정확도를 갖는 시스템을 구축할 수 있는 것으로 알려졌다.

    Ⅴ. 결 론

    유전 알고리즘 기반 학습 환경 하에서 다중 분류기 시스템의 구축 시 분류기의 편향성을 습득한 메타 분류기를 이용하여 분류기의 분류 결과를 평가한 후 평가 결과를 최종 의사 결정 과정에 반영함으로써 분류 시스템의 성능을 향상시키는 메타 학습법에 대해 연구하였다. 다수의 사례 집합을 이용하여 메타 학습법이 다중 분류기 시스템의 성능에 미치는 영향을 평가한 결과 메타 학습법이 분류 시스템의 성능 향상에 크게 기여하는 것으로 나타났다.

    본 연구에서는 메타 학습법을 유전 알고리즘 기반 학습 환경 하에서 구현하였으나 신경망, 결정 트리 등 기존의 학습 알고리즘을 이용한 분류 시스템의 구축 시에도 시스템의 성능 향상을 위한 일반적인 기법으로 활용 가능하리라 사료된다.

  • 1. Doan A., Domingos P., Halevy A. 2003 “Learning to Match the Schemas of Data Sources : A Multistrategy Approach,” [Machine Learning] Vol.50 P.279-301 google doi
  • 2. Esposito F., Semeraro G., Fanizzi N., Ferilli S. 2000 “Multistrategy Theory Revision: Induction and Abduction in INTHELEX,” [Machine Learning] Vol.38 P.133-156 google doi
  • 3. Mitchell T. M. 1980 “The need for biases in learning generalizations,” google
  • 4. Ranawana R., Palade V. 2006 “Multi-classifier systemsreview and a roadmap for developers,” google
  • 5. Lorrentz P., Howells W. G. J., McDonald-Maier K. D. 2010 “A Novel Weightless Artificial Neural Based Multi-Classifier for Complex Classifications,” [Neural processing letters] Vol.31 P.25-44 google doi
  • 6. Nguyen N. T., Lee S. G., Chung T. C. 2008 “A New Boosting Algorithm for Classification on Distributed Databases,” [International Journal of Software Engineering and Its Applications] Vol.2 P.13-20 google
  • 7. Major R. L., Ragsdale C. T. 2000 “An aggregation approach to the classification problem using multiple prediction experts,” [Information Processing and Management] P.683-696 google
  • 8. Ishibuchi H., Nakashima T., Morisawa T. 1999 “Voting in fuzzy rule-based systems for pattern classification problems,” [Fuzzy Sets and Systems] google
  • 9. Giraud-Carrier C., Vilalta R., Brazdil P. 2004 “Introduction to the Special Issue on Meta-Learning,” [Machine Learning] Vol.54 P.187-193 google doi
  • 10. Duda R., Hart P., Nilsson J. 1976 “Subjective Bayesian methods for rule-based inference systems,” [in Proc. National Computer Conference] P.1075-1082 google
  • [] 
  • [그림 1.] 메타 분류기를 위한 훈련 사례 집합의 예
    메타 분류기를 위한 훈련 사례 집합의 예
  • [그림 2.] 유전 알고리즘 기반 학습 환경에서의 메타 학습법
    유전 알고리즘 기반 학습 환경에서의 메타 학습법
  • [표 1.] 메타 학습법을 이용한 다중 분류기 시스템의 성능 평가
    메타 학습법을 이용한 다중 분류기 시스템의 성능 평가