|
内容記述 |
多値判別の問題は科学の多くの分野で頻繁に見られる.二値判別の問題については,<br />Support Vector Machine(SVM)やada-boostなど多くの有効な手法が開発されており,そ<br />れらの性質についての研究も深く進んでいる.しかし,多値判別についてはいまだ決定<br />的な手法の開発がなされておらず,現在においても多くの手法が提案され続けている.<br />多値判別には,大きく分けて二つのアプローチがある.一つ目のアプローチは,三クラ<br />ス以上のラベルを同時に扱う損失関数を考え,その損失関数を何らかの手法により直<br />接最小化することである.このアプローチは理論的な解析が比較的容易であり,ベイズ<br />エラーへの一致性についての研究もいくつかなされている.しかし,サンプル数が多い<br />場合には,このアプローチに立つ多くの手法は計算が困難となってしまう.もう一つの<br />代表的なアプローチは,二値判別機を組み合わせて多値判別を行うという方法である.<br />このアプローチは計算量が比較的抑えられること,実装が容易であることから多くの実<br />用上の問題で用いられている.二値判別機の結果から最終的な多値判別の結論を導出す<br />る方法,すなわち二値判別機の結果を組み合わせる方法には,多数決法や,有効グラフ<br />のモデルを用いた方法,Bradley-Terryモデルを用いた方法,誤り訂正符号による方法<br />がよく用いられる.<br /> 以上の手法においては,二値判別機の組み合わせの方法はトレーニングデータに依存<br />せずに決定的に決まっている.この組み合わせの方法をデータから学習することにより,<br />識別率の向上を目指した研究がいくつかなされてきた.しかし,これらの研究において<br />提案された手法は誤判別率を大きく改善するわけではなく,「組み合わせの方法を学習<br />するべきか,そうでないか?」という問題はこの分野で活発に議論されている.本論文<br />ではこの問題を,ゲーム理論と統計学によるアプローチにより解決することを目指した.<br /> まず、いくつかの二値判別機の組み合わせ法を概観し、full-modelECOCという新し<br />い組み合わせ法の提案を行う.そして,それらの方法を数値実験による比較し,二値判<br />別機の組み合わせ法を学習することについての問題点を議論した.<br /> 本論文の主要部分の前半においては、組み合わせの方法を学習しないことに対するあ<br />る種の理論的な正当性を与えた.まず,判別の問題を,二値判別機の結果から最終的に<br />ラベルの決定を行う「決定者」と,二値判別機の結果の確率分布を定める「自然」によ<br />るゲームとして捉える.そして,組み合わせの方法を学習しないことが一種の最適性を<br />有することを,誤り訂正符号による方法がミニマックスであることを証明することによ<br />り示す.最初に,二値判別機の出力が互いに独立であるという仮定のもとで,one-vs-all<br />の場合に誤り訂正符号による方法がミニマックスであるということを証明した.次に,<br />二値判別機の出力が独立であるという仮定を外した状況での解析を行った.one-vs-one<br />やone-VS-allなどの二値判別機の学習の枠組みにより,「自然」にはどのような制約<br />を入れるべきかが問題となる.まず,「自然」の戦略集合が複数の不等式制約の積集合<br />で表されているとき,その制約集合とミニマックス性の関係をfeasible flowによって<br />特徴付ける定理を証明した.その定理により,誤り訂正符号による方法が自然な制約で<br />ミニマックスとなることを示した.さらに,誤り訂正符号による方法が,one-vs-one<br />よりもone-vs-allの場合の方が少ない制約でミニマックス性を有することを示すこと<br />により,one-vs-allとone-vs-oneのどちらが優れているかという未解決問題に,一定<br />の示唆を与えた.<br /> 後半部においては,二値判別の新しい組み合わせ法の提案を行った.最初にゲーム理<br />論に基づいた新しい二値判別機の組み合わせ法を提案した.具体的には,誤り訂正符号<br />による方法に拡張を加え,「自然」の範囲をデータからある程度特定したときのミニマ<br />ックス戦略を求める方法を提案し,これを二次錐計画問題に定式化した.この方法は今<br />までの多くの方法と違い,条件付確率の推定精度を考慮しつつ,どのクラスを選べば良<br />いかについての最適確率化戦略を直接的に求めるという特徴がある.また,ゲーム理論<br />と対応する点として,最適解の存在がゲーム理論におけるミニマックス定理により証明<br />されること,最適値から得うれる最悪の場合の誤判別率がエントロピーの概念と関係づ<br />けられることが挙げられる.次いで,二値判別機の組み合わせ法を学習する際に,既に<br />学習に用いたデータを組み合わせ時にも用いなければならないために生じる過学習の<br />問題に取り組んだ.この問題を,ブートストラップやクロスバリデーションを用いた<br />stackingという手法で回避する方法を提案した.そして数値実験の結果,stackingに<br />より組み合わせ法を学習する提案手法が,学習しない方法に比べて多くの場合によりよ<br />い識別結果を与えることを示した.<br /> |
要旨・審査要旨 (167.6 kB)
