F1期待値最大化

複数選択可の予測問題(Multi Label Classification¹)で，どれを選ぶのが一番F1の期待値が高いのかという話です．

図: 浴衣を着た動物のキャラクター²

「この画像に何が写っていますか？」と問われたときに

いぬ	ねこ	うさぎ	ねずみ	くま	たぬき
○	○	○	-	○	-

といった具合に複数のラベルを出力したい場合がある．その場合にラベルとして上げる項目が少なすぎても多すぎてもダメなので，ちょうどいいラベルの出力数をなんとか数学的に求められないかという要望があったりします．

問題

$n$個の商品があるとする．ユーザーは複数商品を選択可(選ばなくても良い)場合に，ユーザーが商品を選ぶ確率$p$が既知であるとする．
ユーザーがどの商品を選ぶと予測すればF1の期待値を最大化できるか？

例

A, B, Cという商品があって，ユーザーが選ぶ確率が$p = (0.45, 0.40, 0.35)^\mathrm{T}$とすると，
一個一個は5割未満だけど全部選ばないよりはどれか選んどいたほうが確率が高そうという話になります．

考え方

$2^n$の全てのパターンを試せば，F1の期待値が高い組み合わせがわかる．
ただProbability Ranking Principle³より，確率の高い方から順に$k$個選べば良いという話になって
動的計画法を用いることで，$O(n^2)$で解けることが知られている．⁴

実装

その論文⁴の実装をFaron氏⁵がやってくれてて，さらにCPMP氏⁶がnumba⁷で高速化してくれています．

References

1. Jain, Solving Multi-Label Classification problems (Case studies included), 2017. ↩

2. みふねたかし, いらすとや ↩

3. Suhara, Notes on Probabilistic Information Retrieval—Probability Ranking Principle から BM25 まで—, 2012.(Probability Ranking Principalについて記載) ↩

4. Nan et al., Optimizing F-measure: A Tale of Two Approaches, 2012. ↩ ↩²

5. Faron, Get Expected F1-Score in O(n²), (Faron氏の実装) ↩

6. CPMP, F1-Score Expectation Maximization in O(n²), (CPMP氏の実装, numbaで高速化) ↩

7. ANACONDA, Numba, ↩