SIGNATE StudentCup 2020 1st place solutionの後半部分(multiclassラベルのpostprocess)を読んでみる

# 自分は1st placeの人じゃないです。
誤解されるとあれなので、念の為。

# この記事は何。
SIGNATE StudentCupという学生限定コンペが毎年開催されていまして、その解法LTスライドが一般公開されました。
1位の方の手法がかなり頭良くて(特に後半のpost process)TLなどでも話題になっていたのですが、あのスライドだけだと結構真面目に読まないと理解できなくて辛かったので**後半部分を**読んだ時のメモを書きました。

本家は[こちら](https://signate.jp/competitions/281/summary)です。
他の方の著作物なので本記事ではあまり本体スライドそのままを引用したりしません。
原典を確認しながら並行して読んでいただくことを想定しています。

# スライド5ページ目
このスライドは最終的に謎です。

まず、シミュレーションの部分がどういうシミュレーションなのかわからない方も多いと思います。(自分もどういう設定なのか追証しないとわからなかった。)

このシミュレーションは具体的にはこのようになっています。

・2値分類。
・陽性(Positive)ラベルの確率が0.6
・モデルはある一定の確率でPositiveを出力するだけで、性能という概念がない。
・2値の状態でF1-macroを計算している。

コードで書くとこんな感じです。

```python
label = []
pred = []
positive_rate = 0.6
for i in range(1000):
    pred_rate = #ここに1と予想する確率が入る
    lb = np.random.choice([0,1],p=[1-positive_rate,positive_rate])
    label.append(lb)
    pred.append(np.random.choice([0,1],p=[1-pred_rate,pred_rate]))
    
print(f1_score(label,pred,average="macro"))
```

これを実際に`pred_rate=0~1.0`で各10回ずつシミュレーションしてグラフを書いてみました。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/244678/491bc7e7-9ef7-0581-083e-f3ce08c455e2.png)

縦棒はエラーバーです。おおよそ元のグラフと同じ形状になっているのではないでしょうか。

さて、シミュレーションがどういったものかまで理解できた上でもこのページは謎です。

**真陽性率0.6のものにランダムに6割で陽性を返すモデルが最も性能が良いのは自明**

じゃないですかね。これをもってargmaxが最適ではないというのは無理があると思います。
極端な話、モデルの元々の正答率が100%ならargmaxを取るのが最適戦略になりますからね…  
**argmaxが必ずしも最適でないというのにはわたしも同意します。**が、このシミュレーションはその根拠にはなりえないと思います。ということで謎です。

### 追記
今回のコンペは一位でもF値0.5程度とそもそものタスクが難しい設定でした。(人間でも結構苦しいくらいの設定)だったので、モデルの信頼性が低いとしてこのような設定を考えたのかもしれません。

これに関連して今回の手法はタスク自体が難しい(モデルの出力がランダムに近い)ほどおそらく効いてくる手法になります。F-scoreが0.8とか行くような問題設定では素直にargmaxをとるので良いのではないかな…と思います。

# スライド6ページ目

ここではベースアイディアの説明をしています。まぁなんやかんや難しいことが書いてありますが、順に追うと、まず確率からラベル予測を求める問題を

```
x:Kクラスのone-hot labelがデータ数N個分重なったもの。(例: [[0,0,1,0],[0,1,0,0]...[0,0,0,1])
p:KクラスのラベルへのデータN個に対する予測値(例: [[0.1,0.4,0.3,0.2]....[0.8,0.1,0.1,0.0]])
```

において、pに最も"近い"xを求めることという問題に置き換えます。
この定式化を表しているのが下の方に書いてある条件の1番目と3番目です。

ところで、"近い"をどう判定するのかですが、それは対数確率を使っています。
まぁ要はcross entropyみたいなものですね。
$$
\Sigma_{ik}\  x^k_i\ log p^k_i 
$$
**$a^k_i$はi行k列目の要素を指します。**
xはonehotなので、pが大きいところに1を割り当てるほど値が大きくなるという指標で、これを"近い"の判定基準として最大化します。

これだけで解くと最大値を取るのと変わらなくなってしまうので、ここに更に次の条件を加えます。

**あるクラスkにおいて、そのクラスに属するデータの数$N_k$は決まっている。**
つまり、xを行の方向に足していったら、$[N_0,N_1,...N_k]$になるってことですね。
予測の分布と真ラベルの分布を見て折衷案を取ろうという感じです。
これは式で書くと
$$
\Sigma_i x^i_k = N_k
$$

こうなって、これで条件式の2番目が出てきてこのスライドの条件式が揃いました。
この問題は解析的には解けなくて、ソルバを使わないと解けないです。(local maximumにlabelを振るのがglobalに得をするとは限らないのでどうしても試行錯誤が必要になります。)

### 追記
ここらへんしれっと流していますが、この対数尤度の和で近似することはそんなに自明じゃないと思っています。確かに指標としては正しいのですが、以降を考えるとここはもう少ししっかり定義できる尤度(つまり、$p(\theta |x)$のような形としてかけるもの)の方が望ましい気がします。OneHotなものとの間でこういう形でかけないか考えたのですが、自分にはうまく思いつかずやむを得ずこのままにしているという状態です。

# スライド7ページ目

スライド6ページ目で出てきた$N_k$ってどうやって計算するの？という問題があります。
public LBからとってくる手もありますが、そうではなくてまず$N_k$を次のように考えます。

1. $N_k$は二項分布に従う。(~~スライドにはポアソン二項分布と書いてますが以降の手順的にただの二項分布と考えて良い気がします。オッカム。~~よく確認すると微妙なところで、この後の期待値や分散の計算はポアソン二項分布に従っていました。ただ近似後の正規分布にどこまでポアソン二項分布の性質が残っているかと言われると微妙な気がします。また、毎回確率が変わるような試行かと言われると微妙なところで、ポアソン二項分布よりは単なる二項分布もしくは多項分布に従うことを仮定したほうが筋が良いのではないかと個人的には思います)
2. サンプル数が多いので二項分布を正規分布で近似する

式で書くと、

$$
N_k \sim Gaussian(\mu_k,\sigma_k)
$$

正規分布の表記にNを使うとサンプル数と混ざってややこしいのでGaussianを使いました。
ここで、母数$\mu_k,\sigma_k$はそれぞれ標本平均と標本分散から決めます。

$$
\mu_k = \Sigma_i p_i^k \\\
\sigma_k = \Sigma_i \ p_i^k(1-p_i^k)
$$

二項分布の公式と同じですね。行方向に計算します。
このように$N_k$を確率分布として表すと、$N_k$も同時に推定できるようになります。
具体的には、スライド6で定義した最大化問題に、突拍子もない$N_k$を設定することによるペナルティ項を追加します。

$$
\Sigma_{ik}\  x^k_i\ log p^k_i \ \  -  \frac{1}{2} \Sigma_k \frac{(N_k-\mu_k)^2}{\sigma_k^2}
$$

後半のペナルティ項はGaussianの対数をとったものです。(正規化項は$\sigma_k$が定数なので、正規化項も定数であり最大化に関わらないため省略されています。)

この状態で、$N_kとx_i^k$をいっぺんに最大化する(折り合いをつける)というのが最終的なポストプロセスのようです。

# 感想疑問等々

頭いいなぁと思いました。
prediction全体を通してのglobalなラベル最適化を考えたことなかったので新たな視点をもらいました。よほど変な問題じゃない限りは自分でも実装できるので今後のコンペでも使ってみようかなと思いました。(utilityにしても良さそうなくらい。)

**当然ですが、trainとtestの分布がまるっきり違う問題には適用できないのでそこは注意ですけどね**
($N_k$のペナルティ項がうまく働いてくれません)

## 疑問点
はいくつかあって、

1. スライド5の謎。
2. ペナルティ項と尤度項の大きさのバランス。
3. 多項分布ではなくて二項分布を仮定していること。


あたりです。

1に関してはかいたとおりです。

2はどういうことかというと、尤度項$\Sigma_{ik}\  x^k_i\ log p^k_i $はデータ数iに比例して大きくなっていくのに対して、ペナルティ項$\frac{1}{2} \Sigma_k \frac{(N_k-\mu_k)^2}{\sigma_k^2}$はクラス数に比例して大きくなるので、**データ数とクラス数のバランスを見て何らかの係数を導入しないとうまく行かない場合も有るんじゃないか**と思うということです。今回は特に導入してないようですが…

3は、書いたとおりで各クラスごとに二項分布を仮定していて、また二項分布の確率和に関する条件も入っていません。つまり、**$\Sigma N_k \neq N$になっている可能性が有るのではないかということです。**これは実実装には入っていたのかもしれません。ない場合は条件を足すか多項分布化したほうが良いような気がします。