분포 추정 알고리즘의 모델 구조 학습 연구

국문 초록 (Abstract)

2.2.1 최소 메세지 길이 (Minimum Message Length,MML) 학습과 Dirichlet Priors 사용한 구조 학습
MML 원리는 이미 기존의 구조 학습 방법에서 사용되어 왔다. 문법 기반의 학습의 경우 문법들의 선호도를 결정하는 용도로 사용되었다. 대칭적인 Dirichlet Prior에 기반으로 하는 이런 공식은 각 문법을 평가하는데 사용되어 선택 가능한 문법들 가운데 선택을 하는 용도로 쓰여진다. 하나의 예로 가장 작은 MML 값을 가지는 문법이 선택하는 방식이 있다. 이 Dirichlet Prior의 사용은 유용한 결과를 보여주기도 했지만, 당연하게 학습할 수 있을 것 같은 데이터로부터 학습을 실패하는 여러 이례적인 상황들을 보여주기도 한다. 자세한 조사를 위해 구성한 작은 규모의 데이터 셋에서는 직관적인 예상과는 반대되는 기대되지 않는 문법의 선호도를 만드는데 이는 Dirichlet Prior의 파라메터 를 조절하는 것만으로는 바꿀 수 없는 특성이다. 이런 이유로, 확률 모델 구조를 학습하는 EDA-GP 시스템들의 전체적인 구성요소에 보다 적합한 prior를 선택하기 위한 연구를 진행한다.
2.2.2 추정 방법
현재 EDA-GP 시스템들은 모델의 파라메터를 변화시키는데 증감 검색을 사용하거나 혹은 최대우도추정 방법의 변형된다. 본 연구에서는 이런 EDA-GP의 추정 방식이 보다 원칙에 입각하여 연구되어 앞으로의 EDA-GP연구에 보다 좋은 가이드를 제공하는 것이 필요한 시기라고 판단하고 있다. 이 일은 앞서 설명된 적절한 구조학습을 위한 prior를 찾는 연구와 같이 본질적인 이해와 분석을 기반으로 하기 때문에, 서로 밀접하게 연관되며, 두 연구는 상호 작용을 하며 진행된다.
2.2.3 적합도 가중치 설정
EDA-GP에서 어떤 확률 모델 구조를 쓸 것인지를 결정하는 것은 굉장히 민감한 주제이다. 잘못된 구조의 선택은 검색의 효율을 떨어뜨리기도 하고 최악의 경우 완전히 잘못된 해를 찾기도 한다. 해집단 내에서 적합도 분포는 문제해결을 위한 핵심적인 정보를 제공하지만, 실제 EDA에서는 각 개체마다 하나의 비트로 한정되어있다. 최근 연구에서는모델을 구성하는데 보다 구체적인 적합도 정보를 이용하는 알고리즘이 제안되었지만, 이런 알고리즘들은 필요한 정보를 추출하기위한 복잡한 메커니즘과 데이터 구조를 필요로 하게 된다. 이에 반해 EDA-GP는 이런 정보를 이용하기 위해 기본적으로 많은 비용을 소모한다. 따라서 EDAs가 구조적 복잡성을 증가시키는 것으로 겪게 되는 시간적 소모비용이 증가하는 현상은 EDA-GP에서는 이미 고려되는 사항이다. 이 연구에서는 볼츠만 선택이나 다른 메커니즘을 통한 가중치를 구현해보고, 이에 따른 시공간 복잡도를 증가시키는 방향으로 알고리즘을 확장해본다.
2.2.4 부정적 개체
기계학습에서는, 부정적인 개체를 모델의 구체화를 돕는데 사용해 왔다. 반면 EDA에서는 거의 사용되어 오지 않았고, 이는 일반화와 구체화가 EDA에서는 비교적 작은 이슈였기 때문이라고 추정된다. 하지만 EDA-GP에서는 GP에서의 Bloat 문제와 같이 적절한 일반화 수준을 찾는 것이 매우 중요한 이슈이다. 그럼에도 불구하고 부정적 개체들은 EDA-GP에서는 쓰여지고 있지 않다. 이런 이유로, 이런 개체들의 이용은 검색을 도울 수 있는 잠재성을 가지고 있다. 부정적인 개체의 이용은 특히 EDA-GP에서 일어나는 분리 학습의 문제점들을 극복하는데 중요하다. 예로 심볼릭 회귀 문제의 학습 단계에서는 긍정적 개체들을 이용한 모델의 일반화 과정에서 부정적 개체를 이용하지 않는 경우, 원하지 않는 개체들까지 포함하는 모델을 생성하고 만다.
2.2.5 대칭성
단순성과 대칭성은 조합 최적화 기술에서 중요한 이슈지만, EDA에서는 거의 이용된 적이 없다. 대칭성은 EDA-GP의 모델 학습 단계에서 특히 유용하게 이용될 수 있다. 예를 들어 대칭성에 관한 기본적인 배경 지식이 있는 경우 일반화를 위한 학습을 할 필요 없이 간단하게 자동적으로 계산하는 것이 가능하다. 이를 구분하기위한 대칭성 파괴를 사용하는 경우 학습이 지연되는 현상이 보고된 적이 있으며, 이런 불필요한 학습 단계의 제거는 보편적인 GP 시스템보다 속도를 향상 시킬 수 있고, 또한 일반화된 해들을 생성할 수 있다. 이 연구는 매우 높은 단계의 대칭성을 가지고 있는 많은 조합성 최적화 문제들에 사용되는 일반적인 EDA의 학습 방법에 적용될 수 있을것으로 기대된다.
2.2.6 EDA-GP의 전송학습을 위한 네트워크 측도
이 연구에서는 EDA-GP에서 사용되는 적절한 네트워크 측도를 확인하는 것을 목표로 한다. EDA에서 발견된 것과 같이 여러 가지 측도들이 EDA-GP에서도 같은 유용성을 보이는지를 조사한다. 우선 문맥 자유 문법을기반으로 하는 EDA-GP에서의 전송 학습에서 유용한지를 살펴보고 전송 방식을 구현 후 영향력을 분석해본다.