この記事は TSG Advent Calendar 2021 の 24 日目のエントリです。11か月の遅刻！！
11月21日に、駒場祭企画としてTSG LIVE! 7が開催され、その中で行われたlive-AI早押しバトルなるものにプレイヤーとして参加したので、競技内容の説明とそこで取り組んだことについて説明しようと思います。
動画はこちら
https://youtu.be/XrsfmpdkxwA?t=3790
Overview
画像の解像度をだんだん上げていき、何が映っているかを早押しで答えます。ただし回答者は人間ではなくbotであり、参加者は早押しをするbotを作成し提出することになります。
大会のルールをざっくりまとめると次のようになります。
- 画像はCIFAR-100のサブクラス(動物40種)から出題され、回答botは画像のラベルを答える
- 参加者は訓練データセットを使って事前にモデルを学習することができ、本番ではテストデータセットから出題される
- 1問につき5ターンで構成され、ターンごとに画像の解像度が上がっていく
- 各ターンでは得点の低いbotから順に解答権が与えられ、botは「パス」か「解答」を選択できる
- 「解答」を選択し間違えた場合、「おてつき」となりその問題の解答権を失う
- 各botの解答内容は全員に共有される（誤答すると相手にヒントを与えてしまう！）
- 1ターンにつき5秒の実行時間が与えられる
- 大会中同じラベルの画像は二度出題されない（大会が進行するにつれbotの押しがアグレッシブになります）
- 予選では全botが同時に対戦し、成績の良い順にシードを与え決勝トーナメントをおこなう
- 予選は10問出題、決勝は3点先取
今回プレイヤーとして私含め3名が参加し、以下のbot達が対戦しました。
- 早押しくん（筆者のbot）
- 伏兵
- KombuNet
結果は我が「早押しくん」は予選2位、決勝3位という残念な結果になってしまいました...
以降の章では各botの戦略の概要を紹介します。
解答戦略
早押しくん
予選2位・決勝3位
利用モデル
出題される解像度は2x2から32x32までの5種類で、高い解像度についてはニューラルネットワークベースでそこそこ良い精度を出せていたのですが、低い解像度についてはサッパリなので別の方針を採ることにしました。結果的に解像度によって以下のようにモデルを使い分けました。
- 32x32, 16x16: Efficientnet-B0
- data augmentationを適用
- 出題解像度によらず224x224に拡大してからEfficientnetに入力
- Stratified 5-Foldでバリデーションセットを作成
- 8x8, 4x4: 様々な色空間を追加してPCA + SVM
- RGB, Luv, HSV, YUV空間を結合し10次元にPCA
- SVMはlinear kernel, one-vs-restに設定
- 2x2: 常にパス
これにより各モデルのバリデーションセットでのAccuracyは以下のようになりました。
| 32x32 | 16x16 | 8x8 | 4x4 | 2x2 |
|---|---|---|---|---|
| 80.6% | 61.3% | 11.2% | 9.2% | - |
低解像度は頑張ってもどうせ当たらないだろうと思いこの精度で切り上げました（結果的にこの判断が負けにつながった気がする...）
そして早押し戦略をちゃんと機能させるために、Probability calibrationというものを適用しました。これはモデルの出力する自信度が実際の正解率に一致するように自信度を調整する手法です。これによって16x16のモデルが若干over confident(正解率が低いのに自信高めに答えてしまう)であることが分かったので自信度をスケーリングしました。
早押し戦略
予測の自信度が8割を超えていたら押すようにしました。もちろん他のbotの誤答は選択肢から除くという操作も行います。得点リード時は解答権が遅くなるので自信度低めでも押させる戦略についても考えましたが、自己対戦の結果余り効いてなさそうだったので不採用としました。
KombuNet
予選3位・決勝2位
利用モデル
早押しくんと同じように解像度ごとに異なるモデルを使っています。32x32の場合は以下のようなCNNを使っており、解像度が低くなるにつれ小さなモデルを使用しています。Efficientnetも試したようですがあまり性能が出なかったそうです（解像度を224に上げなかったことが原因かも？）。
________________________________________________________________________________
Layer (type) Output Shape Param #
================================================================================
rescaling_41 (Rescaling) (None, 32, 32, 3) 0
conv2d_40 (Conv2D) (None, 30, 30, 32) 896
max_pooling2d_27 (MaxPooling2D) (None, 15, 15, 32) 0
conv2d_41 (Conv2D) (None, 13, 13, 64) 18496
max_pooling2d_28 (MaxPooling2D) (None, 6, 6, 64) 0
conv2d_42 (Conv2D) (None, 4, 4, 64) 36928
flatten_25 (Flatten) (None, 1024) 0
dense_76 (Dense) (None, 64) 65600
dense_77 (Dense) (None, 40) 2600
================================================================================
Total params: 124,520
Trainable params: 124,520
Non-trainable params: 0
________________________________________________________________________________
data augmentationを適用した結果、32x32と16x16のモデルのみ性能が向上しました。
結果として解像度ごとの性能は次のようになっています。
| 32x32 | 16x16 | 8x8 | 4x4 | 2x2 |
|---|---|---|---|---|
| 36.3% | 31.6% | 27.9% | 21.5% | 14.3% |
早押し戦略
バリデーションセットに対して、自信度$q$以上の予測のみを取り出してその正解率が5割になる点$q$を、早押しの際の自信度閾値に採用しました。これを作者は「累積的な正解率」と表現していますが、累積的でない正解率、すなわち「自信度がちょうど$q$となる予測のみを取り出したときの正解率」がちょうどCalibration curve の点を表していることになると思います。
伏兵
予選1位・決勝1位
利用モデル
2x2と4x4については、入力ベクトル（解像度$s$に対して$3s^2$次元）が各カテゴリに対応した多次元正規分布に従うものと仮定しているそうです。パラメータ推定は単にカテゴリごとに共分散行列をとることで行っているのだと思います。
8x8, 16x16については解答を諦め、32x32でEfficientnet-B0を採用しています。学習データの3割をバリデーションセットとして転移学習を行った結果、val accuracyは75%ほどになったそうです。
性能をまとめると以下のようになります。
| 32x32 | 16x16 | 8x8 | 4x4 | 2x2 |
|---|---|---|---|---|
| 75% | - | - | 20% | 15% |
早押し戦略
基本4x4で押し、自信があったら2x2で押すという戦略を採用しています。ただ、相手が誤答したときのために32x32のモデルを作成しているようです。
結果
結果は上で述べた通り、1位伏兵、2位KombuNet、3位早押しくんとなりました。
対戦風景はYoutubeで配信されたのですが、そこで印象に残ったことや考えたことを書きます。
低解像度の性能
全員のモデルの性能を比べた感じでは2x2で15%, 4x4で20%ほどの正解率を出せるようです。伏兵やKombuNetはこの性能をちゃんと出せているので早く押す戦略が効いたのだと思います。
伏兵の活躍
優勝した伏兵は低解像度でもかなり積極的に押しているのが印象的でした。正答率も高く、一気にリードして勝敗を決めており、とにかく低解像度で攻めるという戦略がかなり刺さっているようでした。
どれくらい自信があったら押すべきか
早押しくんの早押し戦略は適当に80%と決めてしまいましたが、実際のところ何割くらいで押すべきなのでしょうか？同じ推論モデルを使い1vs1で戦った場合のことを考えてみます。
各ターンのラウンドは十分多く分割されるものとして、解像度は時刻(ラウンド) $r=0 \rightarrow T$ に沿って少しずつ上がっていくものとします。このとき各時点での推論モデルの正答率を $P(r)$ として、 $P(0)=p_0, P(T)=p_T$ とおきます。つまり自分がお手付きをしてしまった場合、相手は時刻 $T$ までめいっぱい待つことができるので、相手は確率 $p_t$ でその問題に正解することができます。
では問題の得点を $1$ として、時刻 $t$ で押すことができたときの自分の得点期待値 $E_1$ と相手の得点期待値 $E_2$ を見てみます。
$$
E_1 = P(t), \ E_2 = (1 - P(t))p_T
$$
つまり自分のリードが伸びていく $E_1 > E_2$ 条件は
$$
P(t) > \frac{p_T}{1+p_T}
$$
これはつまり、待てば必ず答えられる問題 $p_T=1$ ならば自信度50%以上で、今回のCIFAR-100のように8割のAccuracyを持っている $p_T=0.8$ ならば自信度44%以上で押すのが良いということが分かりました。8割押しは慎重すぎるということですね。
では相手が「正解率$q$以上で押す」という戦略をとっている場合はどうなるでしょうか。
その場合こちらは次の二択のどちらかを採用することになります。
- 正解率 $q-\epsilon$ 以上で押す（相手が押すぎりぎりまで待って解答権を先取する。自分が先手なら $\epsilon=0$）
- 得点期待値は $q-\epsilon$
- 押さない（相手の誤答を狙う）
- 得点期待値は $(1-q)p_T$
自分が「押さない」を選択した場合はもうお互いの戦略が変化しないので、「相手より早く押す」を選択するべき条件を考えます。
$$
q - \epsilon > (1-q)p_T \Leftrightarrow q-\epsilon > \frac{p_T}{1+p_T}
$$
これはつまり先ほど挙げた最適値 $\frac{p_T}{1+p_T}$ よりも相手が慎重なら先に押すべきということになり、結局のところ正解率 $\frac{p_T}{1+p_T}$ で双方押すという戦略がナッシュ均衡となりそうです。
もちろんこれは理想化された話で、ターンあたりのラウンド数やリード状況、あと何問で終了するかといった要素も戦略に含めるべきですが、考察が難しいのでこの記事では省略します。
まとめ
以上より反省点をまとめると
- 32x32モデルを強くするのも大事だが、基本早めに押すべき
- 早押しするなら自信度5割時点で押すべき、そうでないなら誤答を待った方が良い
- 低解像度の予測を強くすることが肝心。解像度が低すぎるケースでは浅いCNN、GMM、k-meansのような軽いモデルが効く
といったところでしょうか。低解像度の予測を早々に諦めてしまったのが敗着になった気がします...
謝辞
大会の企画・進行やシステムの実装などをされた運営の方々に深く感謝します。面白い企画をありがとう
プレイヤーの皆さんもありがとうございました。楽しかったです。