KaggleのAbstraction and Reasoning Challenge（ARCコンペ）で金メダルを獲得しました

あいさつ

こんにちは、Deep Percept開発チームの久保です。

以前、雲コンペに参加したときの記事を書いた続きとなります。

この記事では、Kaggleのコンペティション"Abstraction and Reasoning Challenge"に参加した経験を紹介します。

最終結果は914チーム中9位で金メダルを獲得し、また、個人的に1つの目標だったKaggle Masterになることができました。

コンペティション紹介

このコンペは他のKaggleコンペティションとは少し毛色が違っていて、簡単に言うと「パズル形式のIQテストを解けるAIを作れるか？」という深遠な問いを題材にしたものです。

以下、このコンペティションの概要について、具体例を交えながら紹介していきます。

まず、以下の画像のように何かしらの規則性を持つtrain inputとtrain outputのペアがいくつか（この場合は5組）提示されます。

この例の規則性は簡単な方で、人間だったらすぐに「train inputの緑で囲われた部分を黄色に塗りつぶすとtrain outputになりそう」と推論できると思います。

次に、我々が推論した規則性が正しいかどうかがテストされます。

具体的には、以下のように新しく別の画像(test input)が提示されるのでこれに対応するtest outputを我々が回答します。

この例の場合は黄色に塗るだけなので、これも人間だったら簡単にできると思います。

もし我々が回答したtest outputと出題者の意図するtest outputが一致していれば正解とみなされます。

 

 

ちなみに正解の画像は以下のようになります。簡単ですね。

実際にはこの問題を解くのは人ではなくプログラムなのですが、とはいえ、この1問だけ解けるようなプログラムであればすぐに書けるものと思います。

 

 

では、以下の問題はどうでしょうか。

どうでしょうか。人間でも多少考慮を必要とする問題もあったのではないでしょうか。

(他の問題に興味がある方はこちらのnotebookを参照してください。ちなみに↑で挙げた例のIDは05f2a901、08ed6ac7、0dfd9992、0520fde7です)

問題の多様性がかなり高く、これらをできるだけ汎用的に解けるようなプログラムを作成するのはかなり難易度が高いことが実感いただけたでしょうか。

また、上記のnotebookで図示されている問題は全て例題として800個だけ提供されているものであって、実際のコンペの順位付けは未知問題100個に対する正答率でスコアリングされます^*。

よって、事前に提供されている問題例800個を指針にしながら、未知の問題を解けるようにコードを書いていく必要があります。

ちなみにこのコンペティションの主催者はあのKeras開発者であるFrançois Cholletであり、知性を測定・比較・評価するための手法の研究の一環として開催されています。

*補足：このコンペはsynchronous kernel形式です。この形式のコンペでは、我々がアクセスできない環境でコードが実行され、未公開問題に対するスコアが計算されます。我々が知ることができるのは最終的なスコアだけでログなども確認できません。よって、未公開問題の内容を我々が知ることはできないとされています。

私の解法、方針

ここからは私の解法を紹介していきます。

大きな方針としては以下のような流れです。

• タスクを解けるように十分な範囲のDSL(Domain Specific Language、ドメイン固有言語)を実装する
• train input画像に適用するとtrain output画像が適切に生成されるようなDSL表現を探索する
• test input画像に探索されたDSL表現を適用して、test output画像を出力する

以下、それぞれ簡単に紹介します。

DSL実装

DSL(Domain Specific Language)とは、ある特定のタスクを解くためだけに設計・実装された言語(?)です。言語と言っても、実際このコンペにおいては新しいコンピュータ言語を1から作るという雰囲気ではなく、ほとんどの人はPython上に各々が扱いやすいように定義した画像処理関数群のことをDSLと呼んでいました。

ここでは複雑な処理を大量に記述するので割愛するのですが、一例を上げると以下のようになります。

A. ピクセル非依存の関数群

• 画像のピクセルの値に依存せず、画像全体を操作する関数群
  例：Padding, Resize, Flip, Rotate

B. ピクセル選択ベースの関数群

• 操作1. ピクセルの色が特定の条件を満たすピクセルの位置を抜き出し、マスクとする
  例：FixedSingleColorSelection, SingleColorSelection, MultiColorSelection
• 操作2. 様々な条件でマスクを変換する
  例：SquareObjectsSelection, HolesSelection, ContourSelection
• 操作3. マスクの位置情報を使って、元画像を変換する
  例：FixedColorMaskFill, SingleColorMaskFill, MaskCoordsCrop

例えばこの記事の一番最初の例（緑色で囲われた部分を黄色で塗りつぶすタスク）の解答になるようなDSLは、私のDSLでは以下のように表現することができます。

 

    OperationSequence(operations=[ColorOperation(
        # 緑色のピクセル位置を抽出し、マスクとする
        color_selection=FixedSingleColorSelection(color=Color.GREEN),
        # マスクの内側の部分だけを抽出して新たなマスクとする
        mask_conversions=[HolesSelection(connectivity=PixelConnectivity.FOUR_DIRECTION)],
        # マスク部分を黄色で塗りつぶす
        mask_operation=FixedColorMaskFill(color=Color.YELLOW))
    ])

 

この例では1回の操作で解答が得られますが、中には複数の関数を順番に作用させる場合もあります(例えば、Padding → Resize → ColorOperationのような順列表現)。

例題として提供されている800の問題を指針に、より多くの問題を解けるようにDSLを設計・実装することが要求されます。

ただし実際には未公開の100問を対象にスコア付けされるので、例題の800問だけ解ければいいというわけではなく、できるだけ未知問題にも対応可能なよう、汎用的に設計・実装する必要があります。

探索アルゴリズム

仮に全ての問題を解けるぐらい汎用的で大きなDSLを実装できたとしても、それだけでは正解のDSL表現を得ることはできません。

問われている問題を解答できるようなDSLの順列表現、つまり与えられたtrain input、train outputの画像ペア全てに対してinput → (DSLの順列表現) → outputを満たすようなDSLの順列を探索する必要があります。

ここで私は、プログラムの実行時間制限(CPU9時間かGPU2時間)に対して探索空間が大きすぎること、DSL表現が正解に近いかどうかを数値化する評価関数を(一応)作れそう、という2つの理由でヒューリスティック探索を用いました。

ここでの評価関数は、

1. train output画像(train input画像に対する正解となる画像)
2. train input画像にDSLを適用した結果の画像(もし正しいDSLを適用したら1.と同じ画像になるはず)

の2つの画像間の差分となる特徴量(例えば次元数の差、過不足のある色の数、異なるピクセルの数など)の重み付け総和としました。

(もし1.と2.が同一の画像なら評価関数の戻り値は0となり、1.と2.の画像が離れているほど戻り値は大きな数字になります)

探索手法は大まかに以下のように、ビームサーチ状に探索する流れにしました。

1. 初期状態として、1つ1つの単一な操作をするDSLを候補DSLとする
2. 候補DSLを全て評価する
3. 2で結果が良かった候補DSLをn個選択する
4. 3の候補DSLそれぞれに対して、順列の後ろに新たなDSLを1つ付けた全てのパターンを新たな候補DSLとする
5. 正解に辿り着くまで、2から4を繰り返す

また、DSLの複雑度にペナルティを課したりペナルティの重さをスケジュールしたりして局所解に陥らないような探索方法を試す、並列処理して探索時間を増やす、などの工夫を入れていました。

チームマージ

今回、初めて海外の方とチームマージしてみました。

結果的に私の役割は上記の自分のモデルの改善で、最終結果のスコアにもいくらか貢献しました。

他の人の役割としては、機械学習ベースの手法で直接input imageからoutput imageへの変換を学習したり、公開されているnotebookを改善してスコアを稼いだり、パフォーマンス改善をしたり、モデルのマージを管理したりなどやることはたくさんあって、(当然ですが)1人でやるよりも試行錯誤の幅や速度が全然違いました。また、考えていることや目指すモデルの姿も全然違ったりして、新鮮な気持ちで取り組めたと思います。

結果・感想

結果は914チーム中9位でした。

また、今回金メダルをゲットしてkaggle masterになることができました。今まで挑戦してきたコンペは全て銀メダル止まりだったので、ここで1つ区切りになるような成果を出せてよかったと思います。

このコンペはそもそも興味深いテーマを扱っていて最後までモチベーション高く取り組むことができましたし、機械学習というよりもむしろ画像処理や探索、最適化周りの手法を要求されていて、個人的にも技術の幅を広げられました。

実際この経験は、私が業務で開発しているAI-OCRに必要な画像処理や最適化で役に立っています。

AI-OCRの紹介はこちら → https://www.deep-percept.co.jp/solution/ai-ocr/

今回の記事はここまでですが、現在Deep Perceptでは一緒に働く人を募集中です。
興味を持たれた方はこちら → https://www.deep-percept.co.jp/recruit/
最後まで読んでいただき、ありがとうございました。