本研究では,ノンパラメトリックな確率モデルを用いた遺伝的プログラミング(Genetic Programming,GP)に関する研究について述べる.

GPは,生物進化を模倣した進化計算の一手法であり,木構造データを扱うことでプログラムそのものや関数を生成することが可能な手法である.ロボットの動作生成や複雑な数式など,人間が直接作ることが難しいような問題に対して,機械に自動的に解を獲得させることが可能である.

GPや遺伝的アルゴリズム(Genetic Algorithm,GA)などの進化計算では,交叉,突然変異と呼ばれる有性生殖を模倣した遺伝的オペレータを用いて解の組み換えを行ってきた.近年,確率モデルを用いた進化計算の枠組みが盛んに研究されている.確率モデルを用いた進化計算はGAで初めて提案され,1次元で固定長のパラメータを最適化させる問題で有効であることが示されてきた.特に最適化する対象の変数間に依存関係があるような問題は従来のGAでは,ベイジアンネットワークや変数のグループへと分解するようなモデルを使うことで従来のGAよりも正確に解けることが報告されている.

現在,GPに対しても,確率モデルを使用することで,複雑な問題や騙し問題などを解くアプローチが研究されており,確率モデルGPと呼ばれる.これらの確率モデルを明示的に扱うアプローチでは,PPT(Probabilistic Prototype Tree)表現や確率文法が用いられる.しかし,可変長な木構造を遺伝子として持つGPでは,ノード間の依存関係を表現することが難しい.またGPでは使用するシンボルの数が多く,パラメータ数や十分な推定に必要な個体数が増加し,結果計算量が増大してしまう問題がある.本研究で示す実験では,PPT表現を用いるタイプの確率モデルGPの比較を行い,モデルの複雑性と解くことができる問題の難しさに相関があることを示す.

本論文では,上記の問題に対し,PORTS(Program Optimization by Random Tree Sampling)とPERCE(Program Evolution using Related Clique Extraction)の二つの手法を提案する.これらの手法は,ネットワークの確率テーブルや条件付確率表などの明示的なパラメータを持たない,ノンパラメトリックな確率モデルであると言える.そのため,少ない計算量,少ないメモリで実行できるメリットがある.

PORTSでは,優良個体からの木構造断片と呼ばれる単位の部分構造を組み合わせることで新たな個体を生成する.木構造断片のサイズは幾何分布に従うようにサンプリングされ,適応的なスケジューリングにより,この分布のサイズを変化させることで,効率的に解の探索を行う.この特徴から,GP-Easyな問題やRegression問題対して有効に働くことが示されている.

PERCE(Program Evolution using Related Clique Extraction)は,PPT表現を,互いに重複を許すクリークに分割することで有用な部分構造を保存する手法である.従来の確率モデルGPでは,部分構造の周辺分布を保持する必要があったが,優良個体からデータをサンプリングすることでメモリを節約と,大きなサイズの部分構造を保存可能である.従来のGPでは解きづらかった騙し問題に対して,従来のGPや,確率モデルGPより高速に解けることを示す.

最後に,本研究で得られた結果についてまとめ,GPと確率モデルGPの利用方法について考察する.また確率モデルGPの研究の課題と将来の方向性について述べる.

本論文は「ノンパラメトリックな確率モデルを用いたプログラム進化」と題し,7章からなり,遺伝的プログラミングにノンパラメトリックな確率モデルを用いる手法を提案し,シミュレーション結果に基づく探索性能の比較によってその有効性を明らかにしている.

第1章は序論であり,主題と目的が述べられ,進化計算の枠組みが説明される.関数やプログラムを計算機によって自動生成する遺伝的プログラミングと確率モデルを用いる遺伝的プログラミングの概念が簡潔に説明されている.

第2章においては,本論文の事前知識として進化計算と遺伝的プログラミングについて詳細に述べ,いくつかの現在の研究動向についての調査と,遺伝的プログラミングの理論とこの分野での問題について考察している.

第3章においては,確率モデルを用いる進化計算について議論される.確率モデル進化計算の概念,従来の進化計算との違いが説明される.確率モデル進化計算で使われるモデルについて概観し,確率モデル遺伝的プログラミングの手法から,使われるモデル基に3つのクラスに分類する.シミュレーション実験から,3種類の使われるモデルと,4種類の問題で性能比較を行い,使用するモデルの複雑さと解ける問題の複雑さの相関について考察している.

第4章においては,ノンパラメトリックな確率モデルを用いたプログラム進化手法PORTS(Program Optimization by Random Tree Sampling)を提案している.従来手法である遺伝的プログラミングは関数やプログラムを計算機によって自動生成する強力な手法であるが,遺伝的プログラミングによる効率的な探索が困難な問題もこれまでにいくつか報告されている.提案手法は,交叉や突然変異を用いず,複数の優良解から幾何分布に従う部分構造をランダムにサンプリングし,それらを遷移確率に従って結合することで新たな探索を行う.従来の交叉による探索と提案手法の探索を計算機実験によって比較し,提案手法PORTSがより多くの構造を探索することを示している,遺伝的プログラミングの比較で用いられるGP-Easyな問題を用いて探索性能を比較し,提案手法の有効性を検証している.また小さな部分構造から大きな部分構造が徐々に保存されることを,部分構造のサイズの推移から考察している.

第5章においては,PPT(Probabilistic Prototype Tree)を用いたノンパラメトリックなプログラム進化手法PERCE(ProgramEvolu七ionusingRelated Clique Estimation)を提案している.従来の確率モデルでは,ノードの確率表や,条件付き確率などのパラメータの推定が必要であり,大きな部分構造をあつかうためには大量のメモリが必要であった.提案手法では,サンプリングする際に優良個体から直接データを入力することで明示的にパラメータを計算する必要がない。計算機実験から,従来の遺伝的プログラミングで解き難い問題に対して,高い探索性能が得られることを示している.

第6章では,提案手法を実世界の問題に適用する試みがなされている.車輪型ロボットの壁沿い運動を自動生成する問題では,シミュレーションにより,提案手法PERCEは遺伝的プログラミングよりも多くの壁沿い動作を生成できることが示されている.また,音楽の自動表情付けの応用では,楽譜情報から人間らしい演奏を生成することが目的となる.遺伝的プログラミングによる対話的な演奏ルール生成システムを構築している.WEB上にシステムインタフェースを公開しており,多人数が評価するシステムを構築している.医療データからの診断の問題では,広く使われている肺ガン診断結果を予測する.SVM(Support Vector Machine)や遺伝的プログラミングとほぼ同等程度の予測精度であり,実世界の問題に十分応用可能であると結論づけている.

第7章では,本論文の結論として,提案したノンパラメトリックな確率モデルを用いる遺伝的プログラミングの手法の特徴について再度触れ,問題に応じた使い分けが必要とまとめている.また,今後の研究の可能性について述べられている.

以上これを要するに本論文は,進化計算による遺伝的プログラムの自動生成のための新たな探索手法を提案し,シミュレーション実験の他にロボットや音楽などの実世界問題での実験結果をもとにその有効性を示したものであり,情報工学の発展に貢献するところ少なくない.

よって本論文は博士(工学)の学位請求論文として合格と認められる.