Seminar on Probability and Statistics

Seminar information archive ~05/22Next seminarFuture seminars 05/23~

Organizer(s) Nakahiro Yoshida, Teppei Ogihara, Yuta Koike

2008/04/24

16:20-17:30   Room #126 (Graduate School of Math. Sci. Bldg.)
白石 友一 (統計数理研究所)
二値判別機の組合せによる多値判別問題へのゲーム理論的アプローチ
[ Abstract ]
多値判別という学習理論の問題に対して、ゲーム理論的なアプローチを試みた結果についてお話したいと思います。多値判別問題を解くために実用的に広く用いられている方法に、2値判別機を組み合わせる方法があります。その際に2値判別機の出力結果に誤り訂正符号のモデルを仮定し、MAP推定により出力を決める方法が一般的です。本発表では2値判別機の組合せによる多値判別の問題を、「決定者」と「自然」のゲームとして捉え、既存の手法の解析や新しい手法の提案を行います。まず、多値判別問題における、誤り訂正符号による方法がミニマックスとなるための条件をネットワークフローにより表します。そして、one-vs-oneやone-vs-allなどの方法が自然な条件下でミニマックス戦略となることを検証します。次に、誤り訂正符号による方法に拡張を加え、「自然」の範囲をデータからある程度特定したときのミニマックス戦略を求める方法を提案し、これを2次錐計画法により定式化します。またミニマックス定理やエントロピーなどとの関連についての考察を行います。キーワードとしては
・判別問題(特にクラス数が3以上の多値判別問題)
・誤り訂正符号
・ゲーム理論
・最適化理論(線形計画法、2次錐計画法)
・ネットワークフロー理論
・フォン=ノイマンのミニマックス定理
などが挙げられると思います。
[ Reference URL ]
https://www.ms.u-tokyo.ac.jp/~kengok/statseminar/2008/01.html