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

集合划分问题的启发式统计推断的提出及其在信息检索系统中的应用

基本信息

批准号：
07750468
负责人：
相澤彰子
金额：
$ 0.7万
依托单位：
National Institute of Informatics
依托单位国家：
日本
项目类别：
Grant-in-Aid for Encouragement of Young Scientists (A)
财政年份：
1995
资助国家：
日本
起止时间：
1995 至无数据
项目状态：
已结题

项目摘要

本研究は,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を,依存関係仮説のランダムな選択に基づく確率的なサンプリングとして捉えており,これより情報検索システムのクラスタリングなど,従来の枠組を超えた問題への適用が期待される.

本研究使用遗传算法（Genetic它结合了算法（GA）中的理论研究流程，其特点是将以GA为代表的多点搜索方法定位为利用搜索空间的概率采样的大规模并行统计推断。本研究历时一年的研究活动结果如下。首先，在搜索空间表征的理论考虑中，我们关注由 L 个二元变量 Sa2^ 定义的实值函数。我们重点关注了当L的搜索空间根据k个变量的值被划分为2^k个子空间时的离散度（分散度）。然后我们阐明了这个统计量与沃尔什系数之间的关系，我们证明了方差。划分得到的子集的均值是一个宏观特征，代表了k个选定变量之间的依赖程度。接下来，我们将讨论高度并行统计推断的理论，在一个典型的发展中，上述特征被称为。上位性方差和相关性分析在此基础上，我们分析了遗传算法中交叉算子的数学意义，并分析了隐藏在解空间中的依赖关系，我们将遗传算法重新设计为一种以高度并行的方式统计推断关系并将随机搜索应用于依赖子空间的方法。以及预计会对独立子空间产生叠加效应的组合运算。此外，在实验评估中，我们使用多个特征测试问题计算了上述特征值，并验证了与应用GA实际进行优化时性能的一致性。本研究将宏观特征（划分的子空间之间的变化）关联起来。和搜索空间的微观特征（沃尔什系数），并使用现有的代表性分析方法，沃尔什函数分析和上位性。这项研究的新颖之处在于它阐明了方差和相关分析之间的关系。此外，在这项研究中，传统上通过与生物学类比来讨论的遗传算法与基于随机选择依赖性假设的概率分析进行了比较。有望应用于超越传统框架的问题，例如信息检索系统中的聚类。