疎グラフ分割問題の研究:統計力学vs理論計算機科学
【研究分野】情報学基礎
【研究キーワード】
キャビティ法 / グラフ分割問題 / スペクトラル法 / ランダム行列 / レプリカ法 / 評価表現辞書構築 / 自然言語処理
【研究成果の概要】
スピングラス模型など変数間に複雑な依存関係を有する大自由度統計モデルの解析を通じて発展した統計力学の方法が,効率的な近似アルゴリズム,強力な解析手法として情報科学において注目されている.本研究では,統計力学,理論計算機科学の双方において一定の知見が蓄積されている疎なグラフの分割問題に着目し,特に有力な近似解法として知られているスペクトラル法の根拠について,統計力学および理論計算機科学的な方法で分析を行った.また,グラフ分割問題の実問題への応用として単語の語感分類問題を取り上げ,統計力学的な知見にもとづき既存方法の性能改善を行った.
【研究代表者】
【研究分担者】 |
渡辺 治 | 東京工業大学 | 大学院情報理工学研究科 | 教授 | (Kakenデータベース) |
|
【研究種目】基盤研究(B)
【研究期間】2010-04-01 - 2014-03-31
【配分額】18,200千円 (直接経費: 14,000千円、間接経費: 4,200千円)