2010年度第2回 SCOPE 講演会

7月10日に 2010 年度第２回の SCOPE 研究会を開催します。つくば合宿の２週間後ですが、こちらの研究会にも是非ご参加下さい。

2010年度 第２回研究会
日　時 ： 2010年07月10日（土）14:00～
会　場 ： 中央大学 後楽園キャンパス 6号館4階 6418号室

講演1
講演者 ： 金森敬文氏　（名古屋大学 大学院情報科学研究科 計算機数理科学専攻）
講演題目 ： 密度比の推定と計算 ―smoothed analysis からのアプローチ
講演概要：
２つの確率密度の比 (密度比) の推定は，機械学習における重要な課題のひと
つである．例えば，共変量シフト下での回帰分析，外れ値検出，ダイバージェ
ンス推定，条件付き確率密度の推定など，さまざまな統計的推論の問題が密度
比推定の枠組で定式化される．本発表では，密度比推定に対してカーネル関数
と最小２乗法を用いた学習アルゴリズムを提案し，その統計的ないし数値的性
質について考察する．計算効率や数値安定性などの性質は，計算対象となる関
数から定義される条件数と関係が深い．統計的推論においては，データがラン
ダムなので条件数もランダムな確率変数となる．ランダムネスのある状況下で，
学習アルゴリズムの計算効率を議論するために，計算量の分野で提案されてい
る "smoothed analysis" の考え方を利用する．この視点から，提案法は他の
方法と比べて，広いクラスの確率分布に対して条件数が小さな値に分布するこ
とを示す．これにより，提案法が大規模データに対して高い計算効率を持つこ
とが，理論的に裏付けられる．また，学習アルゴリズムを設計するための枠組
として，smoothed analysis の考え方を積極的に利用することの有用性につい
て，今後の可能性を探る．

講演2
講演者 ： 安井雄一郎氏　（中央大学 理工学研究科 博士後期課程）
講演題目 ： 大規模最短路問題に対するダイクストラ法の高速化
講演概要：
最短路問題はネットワーク上の経路探索などの多くの応用を持ち, また他の最適化
問題の子問題として用いられることも多く,適用範囲の広い組合せ最適化問題である.
そのため最短路問題を高速に解くことの重要性は非常に大きくなってきている.
最短路問題に対する解法にはダイクストラ法などの安定的かつ効率的な高速アルゴ
リズムが存在するが, 実問題は非常に大規模(約2,400万点, 約5,800万枝)になるため
高速化が不可欠である. そこで本研究では, バイナリ・ヒープを適用したダイクス
トラ法に対し,メモリ階層構造を考慮した汎用的かつ効率的な高速化を適用することで,
実行性能, グラフ特性に対する安定性, メモリ要求量, 並列実行など, 総合的に最も
優れたソルバーを開発することに成功した. 計算機上の律速箇所を解析するための
実験方法を合わせて示し, 本実装の有用性を裏付けていく.