Analysis of stochastic bias in estimation of distribution genetic programming

Abstract

분포 추정 유전 프로그래밍(Estimation of Distribution Genetic Programming, EDA-GP)는 인공지능의 한 분야인 진화연산 알고리즘 중 하나로 분포 추정 알고리즘(Estimation of Distribution Algorithm, EDA) 의 모델 기반 학습 방법을 유전 프로그래밍(Genetic Programming, GP) 이 다루는 관계형 정보 기반의 문제 영역에 도입하였다. 이 분야에서는 지난 15년간 많은 모델 기법들을 60여개의 논문에서 발표되었으며, 모델 기반의 접근 방법을 통해 다양한 해생성, 다수의 최적해 분포 학습, 사전 지식 사용 및 유전 프로그래밍 행동 분석의 용이성 등 여러 가지 장점을 가지고 있다. 이 알고리즘이 다루는 문제 영역은 귀납적 논리 프로그래 밍(Inductive Logic Programming, ILP)이나 확률적 관계학습(Statistical Relational Learning, SRL)등 관계형 정보를 확률적으로 학습하는 방법 론들과 중첩된다. 많은 장점에도 불구하고 이 분포 추정 유전 프로그래밍은 분포의 편향 성에 의해 확장성에 큰 제약을 받는다. 관계형 정보로부터 확률 모델을 구성하는 과정이 복잡하여, 하나의 표준화된 모델의 표현방식이 사용되 지 않고 다양한 표현방식들이 새롭게 개발되거나, 다른 분야로부터 유입 되어왔다. 이런 과정에서 많은 표현방식들은 진화연산과정 중 특히 모델 의 확률 분포 유지 면에서 충분한 분석이 이루어지지 않고 사용되고 있 다. 일반적인 분포추정알고리즘에서는 보통 모델이 학습한 확률분포가 진화적 선택과정 없이 세대가 흘러가는 경우 분포가 변하지 않는 것이 보편적으로 기대되는 행동이다. 중립성(Neutrality)라고 부르는 이 성향 은 분포추정유전프로그래밍의 경우에는 많은 모델들에서 지켜지지 않고, 확률적 편향을 발생한다. 해결하려고하는 문제와는 독립적으로 발생하는 이런 편향성은 진화적 선택과정이 제공하는 문제 해결을 위한 유용한 정 보들을 왜곡하고, 확장성을 제한하고 분포추정유전프로그래밍의 문제해 결도구로써의 능력에 심각한 제약이 되기도 한다. 이 논문에서는 분포추정유전프로그래밍의 편향성에 대해서 보다 근본 적으로 분석한다. 우선, 분포추정유전알고리즘이 극단적으로 간단한 문제 조차 해결을 못하는 경우를 실험적으로 보여, 편향성의 심각성과 영향력 을 증명한다. 이런 실험적 분석을 넘어서 이어지는 연구에서는 수학적으 로 확률초기트리(Probabilistic Prototype Tree, PPT) 및 확률적문맥자유 문법(Stochastic Context Free Grammar, SCFG)라는 분포추정유전프로 그래밍의 대표적인 두 표현방식을 분석한다. 확률초기트리 방식에서는 편향성이 드리프트효과(drift effect)로 인해 발생하고, 이 효과가 구조적 특성으로 인해 증폭되면서, 큰 모델의 문제 해결력을 제한한다. 이런 제 약은 현실적인 문제들에서는 기본적으로 요구되는 능력으로, 확장성의 문제를 가져온다. 확률적문맥자유문법, 크게는 문법기반의 모델들에서는 이런 드리프트효과뿐만 아니라, 다른 종류의 문제들이 발생하기도 한다. 이 연구에서는 재귀성(recursion)과 깊이제약(depth limit)으로 발생하는 편향을 분석한다. 두 가지 특성은 각각 컴퓨터 언어학과 유전프로그래밍 분야에서 매우 일반적으로 사용되는 특성으로, 두 특성의 상호작용으로 인한 편향효과는 아직 보고된 바가 없다. 이 편향성은 모델을 특정한 형 태의 분포로 수렴하게 하여 위의 편향성이 가져오는 문제들과 같이 관측 된 정보의 이용을 방해한다. 이 연구에서는 이런 편향성을 확인함과 동시에, 정확한 추정을 제공하 고, 이를 이용해 편향성을 제거한다. 확률초기트리의 경우, 우도가중치 (Likelihood Weighting, LW)라는, 베이지안 네트워크에서 사용되는 것과 유사한 방식으로 편향성의 증폭 효과를 제거한다. 문법기반 모델의 경우, 학습된 분포가 만들어내는 편향의 정도가 추정되었으므로, 이의 역치를 다시 적용하는 것으로 문제를 해결한다. 이런 방법들은 수학적인 접근을 통해 편향성을 제거하고 중립성을 보존하는 것을 보장하지만, 이 주장을 뒷받침하기위하여 널리 쓰이는 벤치마크 및 현실적인 문제들에서 검증한 다. 결과적으로 이 논문은 많은 분포추정유전프로그래밍 모델들의 확장성 을 향상시킬 것이다. 중립성 문제의 해결은 해결하려고하는 문제와는 독 립적이므로 분포추정유전프로그래밍을 사용하는 모든 응용연구에서 개선 효과를 나타낸다. 또한 표현방식을 가장 널리, 대표적으로 쓰이는 두 가 지를 선택하여 분석함으로써, 이 표현방식을 기반으로 하는 많은 수의 분포추정유전프로그래밍들이 개선될 것이다. 본 연구의 기대효과는 중립 성의 해결로 인한 일반적인 분포추정유전프로그래밍 분야의 전반적 성능 향상이라고 할 수 있다. 파급 효과로써 중립성 문제의 해결을 넘어서 분포추정유전프로그래밍 의 모델 표현방식에 대한 근본적인 분석 연구 활성화도 기대해본다.

Estimation of Distribution Genetic Programming(EDA-GP) combines Estimation of Distribution Algorithms(EDA) and Genetic Programming(GP), obtaining benefits of model-based approach in applications dealing with relational information. It has been studied for the last 15 years and more than 20 different models are introduced in about 60 papers. This algorithm has advantages in generating more diverse individuals and learning distribution of multiple solutions. Also it can easily be incorporated with prior knowledge and helps understand GP behavior. Its problem domain is shared by Inductive Logic Programming, handling relational information statistically. EDA-GPs have, however, strong limitation of scalability caused by stochastic bias. Due to the difficulty of building stochastic model with relational information, many model representations are newly proposed or introduced from other areas. Their main problem is lack of analysis of retaining distribution in evolutionary search. If we exclude selection from general EDA process, remaining sampling and update steps are not supposed to change distribution in general, called neutrality, since no problem-related information is used. In EDA-GPs, it changes and generates stochastic bias. This problem-independent bias distorts useful information observed from selection or stops EDA-GPs search, seriously restricting scalability. In this thesis, we provide a fundamental analysis of the bias in EDA-GPs. We prove that the bias has strong impact, unfunctioning EDA-GPs even in solving near-trivial problems. Then, the bias of two major representations, Probabilistic Prototype Tree(PPT) and Stochastic Context Free Grammar(SCFG), are mathematically analysed. In PPT, bias is in a form of amplified drift effect increasing exponentially, preventing systems scaling to complex models for real world problems. Bias of grammar based models is caused by recursion of SCFG and depth limitation of GP, each of which is studied in Computational Linguistics and GP respectively, but their interaction has not been studied yet. This bias prefers specific form of distribution consistently, disturbing guide of search through selection. Beyond confirming the bias, we esitmate it accurately and introduce solutions eliminating it in the update step. For PPT, Likelihood Weighting conceptually similar to that of Bayesian networks is proposed to remove the amplification. In SCFG, we cancel its bias by modification of learnt distribution as estimated amount. These solutions mathematically guarantee to solve the problem caused by bias, maintaining neutrality of systems. Additionally, we verify it empirically by with benchmark and practical problems. This thesis will improve scalability of many EDA-GPs, because systems are improved in an aspect irrelevant to problems. Furthermore, our analysis of model representation rather than a specific model is more generally applicable to EDA-GPs. Beyond direct results of scalability improvement, we expect analysis of neutrality to shed light on fundamental analysis of representations of EDA-GPs.