今やってる研究で、トーナメント問題を調べる機会がありました。
トーナメントは私も知らなかったのですが、勝者や順位を決める方式のことを指し、いわゆる二人ずつ戦って生き残っていく方式はノックアウトトーナメントといわれるそうです(wikipedia)。
＃10000人戦う時にノックアウトトーナメントでは何回試合が行われるかというのはよくある質問ですね。
で、このトーナメント方式というのは調べてみると非常に様々なものがあります
例えばスイス式トーナメントは、最初はランダムな組み合わせで対戦、次は勝者同士と敗者同士、その次は全勝・１勝１敗・２戦全敗のそれぞれが・・というふうに同じ成績の人同士で戦う方式です。レーティングを計算して、レーティングが近いもの同士を戦わせるような拡張もあります。近いのは将棋でやってるようなものですね。
利点は全ての人が同じ試合数で戦い、また厳密な順位が決めやすいことがあります。
パラマストーナメントは、一組試合を行い、その勝者とまた新たな人が戦い、その勝者と新たな人・・というふうにやっていく方式です。ハンター試験のトーナメントみたいですね。こんなのあるかというと、ボウリングとか将棋とか囲碁の一部でつかわれているそう
その他にもページシステム・ダブルエリミネーション（ダブルノックアウト）とかいろいろあります。敗者復活が複雑に絡んでくるとさらにややこしい
なんでこんなのを調べたかというと、多値分類問題の二値分類問題への還元でまさにこの問題がでてくるからです（順位学習でも出てくるが今回は割愛）
多値分類問題は、与えられた入力（例：文書）に対し1,2..,kのラベル（例：カテゴリ）をひとつ予測するうな問題です。これらの問題では昔から多値分類を二値分類問題（の組み合わせ）に還元する方式が多く用いられていました。二値分類は多値分類に比べて昔から研究され、理論も実装も揃ってますので、みんな二値分類に還元したいかです。
たとえば、one vs restと呼ばれる方法では (1 vs その他) (2 vs その他) ... (k vs その他）というk個の二値分類器を作り、一番確信度orスコアが大きかったものを予測ラベルとします。この他に有名な方法では総当り戦、つまり(1 vs 2) (1 vs 3) ... (k-1 vs k)のように、二値分類器をk*(k-1)/2個作り、一番勝ったものを採用する方法です。これ以外に誤り訂正符号(ECOC)の手法を使う方法も知られています。
直接多値分類問題を扱える多値SVMや多値ロジスティック回帰（最大エントロピーモデル）といったものも今となっては簡単に使えるようになりましたが、それでも計算量はラベル種類数に比例してしまうという問題があります。ラベル種類数が非常に大きくなりうる場合（数千、多い場合は数百万）、これら全てのクラスのスコアを調べスコアが最大となるのを求めるのは非常に計算量を必要とします。
実は私もこの問題は１年前からいろいろ、特に言語モデル周りでやっていたのですが、モタモタしている間に今年の間に一気にいろいろとでてきてしまいました。
"Multiclass Classification with Filter Trees", A. Beygelzimer, J. Langford, P. Ravikumar pdf
これは、まさにノックダウントーナメント方式を利用する方法です。各ラベルがトーナメントのプレイヤーであり、勝ち残ったものを予測ラベルとして採用します。実際にテストの時は決勝から逆に葉へむかって勝つ方向に調べていきます。
"Error-Correcting Tournaments", A. Beygelzimer, J. Langford, P. Ravikumar, ALT 2009 pdf
この方法は先ほどのよりもロバストな場合で各二値分類のエラーが大きくなっても、それに耐えうるように、ノックダウントーナメントを複数回繰り返し行い、優勝者を複数決め、それら優勝者の間でグランドチャンピオンをクライマックスシリーズのように決勝に近づくにつれ１、２、３勝したほうが勝ち残るというようにして予測ラベルを決定する方式です。
"Conditional Probability Tree Estimation Analysis and Algoritms", A. Beygelzimer, J. Langford, Y. Lifshits, G. Sorkin, A. Strehl. UAI 2009 pdf
最後の方法は確率も出力できるように根から[0, 1]の区間を分割していく方式です（これはまさに私が去年IBISで発表した方法と同じ） ラベル集合が前もってわかっていなくてもオンラインでラベル追加できたりするところなんかはよくできてるなとおもいます。
どの論文も解析（二値分類の問題に還元したときにどの程度達成可能な精度より悪くなるか）がたくさんされていて、このへんの技はもっていないので勉強になります。
これらは実際に実装は簡単で、すでにいろいろと使わせてもらってます。
しかし、研究はよっぽど思いつかない問題でやるかチームでやらないとなかなか先取りできないなぁ・・
Recent Comments