集合分割問題のためのヒューリスティック統計推論の提案と情報検索システムへの適用

点击翻译按钮获取中文摘要

本研究は,Walsh関数によるだまし問題の解析やEpistasis Varianceと呼ばれる情報基準による問題の容易性/困難性の判定など,遺伝的アルゴリズム(Genetic Algorithm,以下GA)における理論研究の流れを組むものであり,GAに代表される多点探索法を,探索空間の確率的なサンプリングによる超並列な統計推論として位置付けたことが特徴となっている.本研究の1年間の研究活動による成果は以下のとおりである.まず,探索空間の特徴づけに関する理論的な考察では,L個の2値変量によって定義される実数値関数を対象として,大きさ2^Lの探索空間をk個の変数の値により2^k個の部分空間に分割した場合のばらつき(分散)に注目した.そして,この統計量とWalsh係数の間の関係を明らかにすることにより,分割により得られる部分集合の平均値の分散が,選ばれたk個の変数の依存関係の強さを表すマクロな特徴量であることを示した.次に,高並列な統計推論に関する理論的な展開では,上記の特徴量が,Epistasis Varianceや相関度分析(Correlation Analysis)など,従来より提案されてきたGAの理論分析手法の一般化となっていることを示した.これに基づきGAの交叉オペレータの数学的な意味を解析し、解空間の中に潜む依存関係を統計的かつ高並列に推測して,依存関係のある部分空間に対してランダム探索を,独立な部分空間に対しては重畳効果を期待した組合せ操作を適用する手法としてGAを再定義した.さらに実験による評価では,特徴的な複数のテスト問題を用いて上記の特徴量を計算し,実際にGAを適用して最適化を行った場合の性能との一致性を検証した.本研究は,探索空間のマクロ的な特徴(分割された部分空間の間のばらつき)とミクロ的な特徴(Walsh係数)を対応づけ,既存の代表的な分析法であるWalsh関数分析,Epistasis Variance,および相関度分析の間の関係を明らかにした点で新しいものである.また本研究では,従来生物学とのアナロジーで論じられてきたGAを,依存関係仮説のランダムな選択に基づく確率的なサンプリングとして捉えており,これより情報検索システムのクラスタリングなど,従来の枠組を超えた問題への適用が期待される.