サルでもわかる顔検出２

これは「サルでもわかる顔検出の原理」の続きです。

群盲象を撫でる。

Kidney International - Figure 1 for article: The elephant in uremia: Oxidant stress as a unifying concept of cardiovascular disease in uremia

前回、顔検出を実用レベルに引き上げたViola＆Jonesの論文を簡単に解説したけど、Violaらが論文にあげた三つの貢献のうちadaBoostについては、ややこしいということであいまいにしか書いてなかった。
なので今日はそのadaBoostアルゴリズムについて解説してみたいと思う。

コンピュータに画像から顔を検出させるという課題はとても難しい。
人間がどうやって視野の中から顔を検出してるのか、その機構自体が全然判ってないんだから、真似ることも出来ない。*1
人は目に映るものをとっさに判断して「あ、顔」だとか「あ、花だ」、「あ、自動車だ」と認識してるわけだけど、
そのそも網膜に映る画像の中で「花」とは「自動車」とはなんだろう？　どうやって区別できるだろう？
コンピュータが計算できるように、画像データとして数値化してしまったとき、その数値データから「花」や「自動車」をとりだすアルゴリズムってありえるだろうか？

たとえば、ユリの花は「白い」。この程度の判定ならコンピュータの計算でもわりと簡単にできる。
では、画像データの中から「白い」ものをやみくもに抽出すれば、それで「ユリ」を見つける事ができるだろうか？
これって、上のイラストの目隠しをした人達の「象って壁みたいだ」という判断とさしてかわらないんじゃないだろうか？
つまり、求める画像を判定するのにはたいして役に立たない…。

群盲象を評す［＝撫（な）ず・模す］　多くの盲人が象をなでてみて、その手にふれた部分だけで象のことを云々（うんぬん）するように、凡人は大人物や大事業の一部分しかつかめず、大局からの見方はできないということのたとえ。

――小学館『国語大辞典』

ただ、画像から切り出した矩形領域（前回参照）を、でたらめに「これはユリの花」、「これはユリの花ではない」と振り分けるよりは、「白い画素が占める領域が多いからユリの花」という基準で判定するほうが、多少マシな結果が得られるだろう。

象でいえば、触ったときに「木の幹みたいだから象」と判定するほうが、ヤマカンで判定するよりマシな結果が得られる。

そこで、こんな課題を出した人がいた。

Random guess （ヤマカン）よりほんの少し良い“weak learner” (弱い学習アルゴリズム) を組み合わせて、任意の精度を達成する“strong learner”(強い学習アルゴリズム) を作る事は出来ないか？

要するにこういうことだ：
６人の盲人（“weak learner”）が集まって、それぞれが「団扇みたいだ」「木の幹みたいだ」「壁みたいだ」「槍みたいだ」「蛇みたいだ」「縄みたいだ」と証言する対象があったら、それはつまり「象」なんではないの？

「白いものはユリ」と判定する程度の分類アルゴリズムでも、たくさん組み合わせれば、役に立つ分類プログラムを作れるんではないか、という発想。
ここで重要なのは「木の幹みたいだ」という分類器と「太い柱みたいだ」という分類器を組み合わせてもさほどの向上は見られないだろうという事。
「団扇みたいだ」という分類器を組み合わせる事で「太い柱みたいだ」という分類器が「象」と誤認してしまう対象を排除できる。
要するにできるだけ「異なった視点」から対象を選択する分類器*2を組み合わせたい。
その基準を提供するのがadaBoostアルゴリズムというわけ。

そして個々の分類器として顔検出のためにViola＆Jonesが選んだのが、前回説明した「Haar-like」分類器だ。
Haar-like分類器は単純だけど、目のあたりの判定をする分類器とか口の辺りの分類器とか、数え上げると何十万個も分類器の候補が作れる。この中から良いものを選んで組み合わせようというわけ。

一個の分類器が「木の幹みたいだ」と判定した対象をどんどん集めると、当然「象」でないものも混じってくる。
その間違えた対象から「象」をより分けるのに、よりマシな分類器を選べば、より「異なった視点」の分類器を選べるだろう。

具体的にどうするかというと、それぞれの対象に点数をつける。
まず、「象」（――の画像だよな、この場合）を1000頭分、「象」でない画像も1000個用意する。
そして、それぞれに1点ずつを割り振る。
で、それとは別にたくさん用意してある分類器候補に片っ端から分類させる。
そして、それぞれの分類器の成績を比べる。
あってたら１点獲得。間違えてたら０点。全部正解したら2000点だ。
で、一番成績が良いものをひとつ選び出し、最初の分類器にする。
でたらめに分類する役立たずの分類器でも半分は正解する事に注意。
役立たずの分類器は確率二分の一で正解するから、おおむね1000点前後を獲得する。
それより点数が低い分類器は、だから、逆に判定していたという事になるね。
判定を逆にすれば良い分類器に変身。*3

最初の分類器が「木の幹みたいだ」と判定した対象のうち、間違えて「象」でなかったものは２点にする。「木の幹みたいじゃない」と判定した対象のうち、実は「象」だったものは２点にする。要するに間違えた対象の点数を高くつけなおす。*4
そのうえで、残りの分類器の成績をつけなおして、そのなかで一番点数が良かった分類器を二番目の分類器にすれば、最初の分類器が苦手とした対象の分類に役立つ（すなわち「できるだけ視点が異なる」）分類器が選べる。

次は、この二番目の分類器が間違えた対象の点数をさらに２倍にして（両方間違えてた対象なら2点の2倍になるから4点ね）分類させ、一番たくさん点数をとった分類器を選び出して、三番目の分類器にする。

これを繰り返して行けば適切な分類器の組み合わせ（上の喩えで言えば、６人の盲人）が選べる。

で、それぞれの分類器の出した答え（「象」と判定したら１、「象」にあらずと判定したら−１とする）を足し合わせてゼロ以上なら、それは「象」と判定する。
要するに多数決だね。*5

大体こんなかんじかなあ。

正確なアルゴリズムが知りたい人は論文を読んでくださいね。ネットにいっぱい上がってるよ♡

*1:網膜や一次視覚野での画像処理は詳しく判ってるけどね。問題はその先。一次視覚野とは別のバイパスの存在すらあるかもしれないらしいし。

*2:特徴空間で互いに直交する分類器。それを見つけるために下の註で書いたようなオッズによる点数を割り振る

*3:実際は、いちいち判定を反転させずとも、下の註にある組み合わせる際の信頼性係数が負値になる事で目的が達成される。だから、上記の計算方法なら、ヤマカン分類器の獲得点数1000点から最も遠い点数を獲得した分類器が一番良い分類器になる。

*4:実際は、間違いが少なければ少ないほど、間違った対象の点数を高くつけなおす。点数はギャンブルのオッズみたいなもので決める。具体的には、正解だった対象の点数の合計を間違えた対象の点数の合計で割った比率を間違えた対象の点数に掛ける。正解が多ければ多いほど、間違った対象に対する「オッズ」は高くなる。4回に1回しか間違わない分類器なら間違いの「オッズ」は3倍。ヤマカン分類器なら間違いの「オッズ」は1倍のままね

*5:正確には、それぞれの分類器の信頼性が異なるので、分類器毎の信頼性を数値化しておいて、それぞれの答えに掛けてから足し合わせる。信頼性は、上の註で書いた「オッズ」の対数を使う。これは間違いによる損失関数を最小にするように選ばれたもので…この辺は同じDiscrete Adaboostを説明してても、論文によって微妙に数式が違うけど本質的には同じ。損失関数の設定の仕方でAdaBoostにもいくつか種類がある