多値判別という学習理論の問題に対して、ゲーム理論的なアプローチを試みた結果についてお話したいと思います。 多値判別問題を解くために実用的に広く用いられている方法に、２値判別機を組み合わせる方法があります。その際に２値判別機 の出力結果に誤り訂正符号のモデルを仮定し、MAP推定により出力を決める方法が一般的です。本発表では２値判別機の組合せによる多値判別の問題を、 「決定者」と「自然」のゲームとして捉え、既存の手法の解析や新しい手法の提案を行います。まず、多値判別問題における、誤り訂正符号による方法が ミニマックスとなるための条件をネットワークフローにより表します。そして、one-vs-oneやone-vs-allなどの方法が自然な条件下でミニマックス戦略 となることを検証します。次に、誤り訂正符号による方法に拡張を加え、「自然」の範囲をデータからある程度特定したときのミニマックス戦略を求める 方法を提案し、これを２次錐計画法により定式化します。またミニマックス定理やエントロピーなどとの関連についての考察を行います。キーワードとしては
・判別問題（特にクラス数が３以上の多値判別問題）
・誤り訂正符号
・ゲーム理論
・最適化理論（線形計画法、２次錐計画法）
・ネットワークフロー理論
・フォン=ノイマンのミニマックス定理
などが挙げられると思います。