Kaggle LLM 20 Questionsの解説と上位ソリューションまとめ

はじめに

この記事では、先日Kaggleで行われた『LLM 20 Questions』の上位ソリューションについてまとめます。LLMとゲームAIが合わさったコンペティションでした。

私はソロで参加し、832チーム中9位（上位1.1%）の成績となり、金メダルを獲得しました。また、このたびの成績によって、Kaggle Competitions Masterに昇格しました！

最終順位発表後におけるリーダーボード

上位50チームのスコア分布

ボットのペア、キーワードなどのランダム要素があり、不確実性が高いコンペでしたが、２週間の評価期間のおかげで、最終的にはMaster、GMをはじめとする実力者が金メダル圏内に残りました。ただし、実力者であっても不運に見舞われて順位を落としているケースも多いです。
ちなみに、金メダル圏内の11枠の内で5チームがJapaneseチームです！

コンペティションの概要

期間について

May 15, 2024 - コンペの開始日
August 13, 2024 - 最終提出日
August 13, 2024- August 29, 2024 - AIエージェントの評価期間

当初はAugust 27, 2024が最終日でしたが、２日間の延長が発表されました。

タスクについて

概要

このコンペティションでは、20 Questionsというゲーム（いわゆるアキネーターゲーム）をプレイできるLLMを作成することが目標です。チームは2対2で対戦し、どちらが早く秘密のキーワードを見つけ出すかを競います。

詳細

20 Questionsは、YesまたはNoで答えられる質問を使って、秘密のキーワードを20ラウンド以内に当てるゲームです。各チームはランダムに「質問者」と「回答者」の2つの役割を持ちます。質問者は質問をして単語を推論し、回答者はYesまたはNoで答えます。戦略的な質問を通じて、質問者ができるだけ少ないラウンドで正解にたどり着くことが目標です。

ルール

ゲームは20ラウンド行われ、各ラウンドで質問者は質問をし、推論します。正解を当てたらそのチームが勝利します。両方の質問者が同じラウンドで正解を当てた場合は引き分けです。どちらも正解できなかった場合は、次のラウンドに進みます。20ラウンド終了時に正解が出なければゲームは引き分けです。

質問は750文字以内、推論は100文字以内でなければなりません。各ラウンドでLLMが回答するための時間は60秒で、さらに300秒の追加時間もあります。時間切れや、YesまたはNo以外の回答をした場合、そのLLMは負けとなります。

評価方法

提出と評価の仕組み

提出されたボットは、リーダーボード上で似たスキルレベルのボットと対戦します。スキルレーティングは勝利で上がり、敗北で下がります。引き分けの場合は、平均に回帰します。

このコンペティションは2対2の協力形式で行われます。提出されたボットはランダムにペアを組んで他のペアと対戦し、質問者と回答者の役割がランダムに割り当てられます。

ランキングシステム

エピソードが終了すると、全てのボットのレーティング推定値が更新されます。勝利したペアのμ（スキル推定値）が上がり、敗北したペアのμが下がります。引き分けの場合は、μが平均に近づくように更新されます。レーティングの更新は、期待値からの偏差と各ボットの不確実性σに基づいて行われます。

最終評価

2024年8月13日の提出期限で全ての提出がロックされ、リーダーボードはリセットされます。その後、8月13日から29日までの期間に、新しい未公開のキーワードセットを使ってエピソードが実行されます。この期間中、リーダーボードに表示されるのは、2つのアクティブな提出のみです。この期間の終了時点でリーダーボードが確定します。

データ

毎試合ごとに、秘密のキーワードが設定されます。
キーワードは、コンペ開始当初は、『人』『場所』もありましたが、最終的には『物』カテゴリーのみに限定されました。
Publicリーダーボードは、公開されている約1500件のキーワードからランダムに設定されます。
Privateリーダーボードは、重複なしの完全に新規のキーワードセットに置き換えられます。
そのため、どのようなキーワードセットになるかを推定し、参加者自身で作成する必要がありました。

評価期間開始直後に、一部のキーワードが重複しているという事件がありました。

ゲームの例

イメージをつかみ易くするために、ゲームの例を紹介します。
秘密のキーワードは猫とします。
ラウンド1
質問（質問者）：『それは生き物ですか？』
回答（回答者）：『yes』
推論（質問者）：『ライオン』
--不正解なのでゲーム続行。--

ラウンド2
質問（質問者）：『それは家にいますか？』
回答（回答者）：『yes』
推論（質問者）：『猫』
--正解。相手チームと同時の場合は引き分け、相手チームが未正解の場合は勝利。勝利チームの質問者と回答者にそれぞれプラスの得点が与えられます。--

上記のように、質問者（質問、推論）と回答者の二種類の開発が必要になります。
質問フェイズでは、キーワード候補を上手く減らす質問を選択することを目指します。
回答者は、適切なyes/noを返答することを目指します（回答者にも得点が与えられるので、協力するインセンティブがあります）。
推論フェイズでは、過去のラウンドの質問と回答から、最も確率の高いキーワードを推論することを目指します。

最小限のソースコードとしては下記のようになります。ソースコードの最後の関数（引数はobs, cfgに固定）が自動的にエントリーポイントとなります。

def agent_fn(obs, cfg):
    if obs.turnType == "ask":
        response = "Is it an animal?"  # 質問
    elif obs.turnType == "guess":
        response = "cat"  # 推論
    elif obs.turnType == "answer":
        response = "yes"  # 回答
    return response

上位陣のソリューション

前提知識

上位陣の個別のソリューションを紹介する前に、このコンペの前提知識を共有します。

質問者の主流戦略

辞書順二分探索（Agent Alpha）

下記のように、秘密のキーワードを辞書順二分探索により発見する手法がPrivateキーワードセットではトップメタでした（一方で、Publicキーワードセットではそこまで流行っていなかったと記憶しています）。

この手法の弱点として、LLMは正しく回答することができません。回答者が一度でも間違えると、永遠に正答できなくなります。
そこで、正規表現を回答者のパイプラインの前段に組み込ませることが提案されていました。
しかしながら、質問者の立場では、回答者がその正規表現を採用しているかわかりません。
そこで、ラウンド1で合言葉を質問（ハンドシェイク質問）し、yesと答えた場合のみ辞書順二分探索に進む手法が提案されていました。通常は意味がわからない質問なので、回答者が正規表現を採用していない場合は、noと答えるので弾くことができます（偽陽性でyesと答えることもあり、その場合は負けを意味します）。

ちなみに、このノートブックの著者のloh-maaさん(本コンペ3位)は、銅メダルや銀メダルを経由せず、金メダル3枚でKaggle Competition Master に昇格しました（何者？！）。

このAgent Alphaプロトコルの採用に関する、質問者および回答者それぞれの詳細な統計はGMのChris Deotteさんが下記のコメントで共有しています。

最終的には、Privateキーワードセットに切り替わるタイミングで、Agent Alphaをソリューションに組み込んだ上位チームが多かったようです。835チームの内で33チームがAgent Alphaを組み込んでいます。上位50チームに限ると、18チームがAgent Alphaを組み込んでいます。（Aug 29thにおける情報）

Offline-Policy

上位陣はAgent Alphaに対する応答を用意している方が多いですが、用意していない参加者も多いです。具体的には、835チーム中、約300チームが応答を用意していますが、約500チームは応答を用意していません。
そこで、非Agent Alphaが回答者ペアになった場合の対策を考える必要があります。
最初に思いつくのは、LLMによってその場で（Onlineで）質問と推論を行なうことです。
実際にコンペの中盤には、LLMのみで質問と推論と回答を行なうノートブックが公開されており、シルバーメダル圏内のスコアを達成していました。

このLLMベースでの推論を拡張する手法として、Offline-Policyがセカンドティアに君臨しました。
Offline-Policyは、キーワードと質問の行列（値は回答）を基にしており、LLMが直接質問を行うのではなく、あらかじめ準備されたデータを活用して質問を行うアプローチです。これにより、効率的にゲームを進めることが可能になります。

Offline-Policyを採用した（と推察される）ボットがPublicリーダーボード上位を席巻していました。本コンペ1位のc-numberさんは、Agent AlphaなしのOffline-Policyを採用したボットで1ヶ月ほどPublic1位の順位をキープしていました。（しかも、USPTOコンペでも同時期にPublic2位をキープされていました！）

私自身もAgent Alphaの勝利を含まないOffline-Policyの勝利のみで、Public最高3位の順位をはじめ金メダル圏内に複数回到達しました。

なお、本コンペは直近の数件の提出ボットのみがリーダーボードスコアを保持し、新しいボットを提出すると古いアクティブなボットが停止されます。そのため、実験サイクルを重視してガンガン提出するか、ボットの性能を正確に測定するために時間を置くか悩ましいコンペでした。

Privateリーダーボードでは、Agent AlphaとOffline-Policyを組み合わせたチームが上位となりました。評価期間開始直後はレートが全員600に初期化されるため、Agent AlphaとOffline-Policyの勝利によってレートを上昇させ、高レート帯ではAgent Alphaのミラーマッチが徐々に増えていくという流れでした。

回答者の主流戦略

LLM

Llama-3-8Bを用いている公開ノートブックが共有されていたので、使用していた参加者の方が多いです。上位陣は、Llama-3.1-8Bを用いている方が多かったように見えます。

ルールベースのプロトコル

Aで始まりますか？のような特定のプロトコルに則った質問には、LLMで対応することが難しいので、正規表現が有効でした。

c-numberさんが、下記のディスカッションで、有名な5つのプロトコルに対する正規表現を共有していました。

上位陣の個別のソリューションを紹介

現在公開されている上位ソリューションのみを紹介しています。新しく上位ソリューションが公開され次第、この記事に追記します。本記事をストックしていただければ通知が飛びますので、しばしお待ち下さいませ。

元のソリューションを一箇所にまとめたディスカッションは下記です。

11th Place Solution by NIWATORIさん、akmrさん、oksさん

このソリューションは、Offline PolicyとAgent Alphaを組み合わせ、LLMの性能を最大限に活用しつつ、リソースを効率的に使うことに焦点を当てたものでした。また、3 つの 4 ビット量子化 LLM (gemma-9B、llama3.1-8B、mistral-7B) の多数決による回答を採用しています。

このソリューションの日本語解説が、リクルート様のテックブログで共有されています。

質問者の工夫

• Offline Policy: 質問者は、Offline-Policyに基づいています。キーワードリスト、質問リスト、(キーワード, 質問)ペアの確率表、およびキーワードの事前確率を事前に準備し、質問時には条件付きエントロピーを最小化する質問を選び、最大尤度でキーワードを推論しました。これにより、20問の質問と回答のペアに基づく推論が難しいLLMでも、単一のキーワードと質問のペアに対する回答には高い精度を発揮しました。
• Agent Alpha: 両方のボットにAgent Alphaの機能を統合しました。ボキャブラリーはWordNetの単語と推論に使用したキーワードリストを組み合わせて作成され、ボキャブラリーサイズは約173,000となりました。
• キーワードリスト生成: LLMを使用してキーワードリストを生成しました。また、LLMからの頻度に基づいて事前確率を計算し、最適な質問と推論の計算に含めることで、精度を向上させました。
• 質問リスト生成: 公開エピソードからの質問とLLMによって生成された質問を活用し、最終的に約1,000の質問リストを作成しました。

回答者の工夫

• ルールベースと多数決: 回答者（Answerer）は、いくつかのルールベースのロジックと、3つの4ビット量子化LLM（gemma-9B、llama3.1-8B、mistral-7B）による多数決で構成されました。特定の正規表現にマッチする質問に対しては、ルールベースで回答し、それ以外の場合は多数決による回答を採用しました。

データセットの作成の工夫

• キーワードリスト: LLMを使用してキーワードリストを約32,000件生成しました。リストに含まれるキーワードの頻度に基づいて事前確率を定義しました。これにより、バランスの取れたリストを作成し、推論の精度を向上させました。

• 質問リスト: ルールベースの質問、公開エピソードから収集した質問、LLMで生成した質問を組み合わせて約1,000の質問リストを作成しました。最適な質問は条件付きエントロピーを最小化することで導かれました。

• 確率表のラベル付け: LLMを使用してp(keyword, question)確率をローカルで計算し、これを元に推論を行いました。この過程で、vLLMを活用して計算を高速化しました。

その他の工夫

• モデルのロードとアンロード: 回答時にモデルをロード・アンロードする方法を採用し、モデルロードの順序をABC/CAB/BCAと回転させることで、GPUメモリの制限を超えないよう工夫しました。

10th Place Solution by raconionさん、Rakiさん、Benedikt Drosteさん

このソリューションでは、キーワードリストの網羅性に焦点を当て注力し、Privateキーワードセットの約90%をカバーすることに成功しています。また、質問者としての質問のテンプレートのプロンプトエンジニアリングを行い、回答者が適切に回答できる確率を高める工夫を行っています。

質問者の工夫

• Agent Alphaの質問テンプレートの工夫: 初期は単純なAgent Alphaのアプローチを採用しましたが、LLMがアルファベット順二分探索の質問に正確に答えられないことがわかりました。そのため、プロンプトエンジニアリングを行い、以下のようなステップを含むテンプレートが効果的だと判明しました。

  ステップ1: 小文字で既知のキーワードと比較単語を書き出す。
  ステップ2: 文字を比較し、不一致があれば順序を決定。

keyword Please follow these 2 steps to compare alphabetical order:
Step 1: take the known keyword and the comparison word and write them out with a space between each character, in lowercase.
Step 2: Now iterate through the characters of both words, until you find a mismatch. The first mismatch determines alphabetical order.
If one word ends while the other has more letters, the shorter word comes first alphabetically. 
Finally answer with yes or no.
For your reference, the alphabetical order of characters is: a < b < c < d < e < f < g < h < i < j < k < l < m < n < o < p < q < r < s < t < u < v < w < x < y < z.

Does the keyword (in lowercase) precede {keyword} in alphabetical order?

このプロンプトにより、microsoft/Phi-3-medium-4k-instructモデルは約80〜90%の精度で回答可能でした。

• Tier付きキーワード推論: 各キーワードにGPT-4o miniを使用してTier1〜10（10が最高）を付与し、最も高いTierのキーワードを優先的に推論。これにより、より効率的な推論が可能となりました。

回答者の工夫

• Phi-3-medium-4k-instructの採用: 回答者にはmicrosoft/Phi-3-medium-4k-instructを使用しました。プロンプトには制約を設け、LLMが創造的に誤答しないようにしました。
• プロンプト工夫: 「結論が出たら答えを終了する」など、明確な手順を導入して、CoT（Chain of Thought）を活用し、より正確な回答を促しました。また、時間制限に関する処理も含め、obs.remainingOverageTime < 60の条件を満たすと「no」と答えるように設定しました。

データセットの作成の工夫

• キーワードリスト生成とランク付け: 最大2M件のキーワードリストを作成し、20ラウンドで1M以上のキーワードを網羅するように設計。Wikipediaのn-gramから生成したキーワードを組み込み、最も高い精度を達成しました。キーワード生成タスクを教師あり学習タスクとして定式化しています。
  

その他の工夫

• ハンドシェイクのスキップ: 1つのエージェントはハンドシェイクをスキップしてAgent Alphaに進み、2Mのキーワードリストを使用しました。もう1つは1Mリストを使用し、Agent Alphaのハンドシェイクを保持しました。

9th Place Solution by ISAKA Tsuyoshi（ねぼすけAI）

このソリューションは、複数の要素を統合し、特にルールベースとLLM（Llama3.1-8B-IT）＋Wikipediaコンテキスト応答を組み合わせています。また、データセットをTier1からTier4に分割することで、Offline-Policyにおける高精度なキーワード推論を実現しました。また、Agent Alphaのミラーマッチでの勝率を高める工夫もされています。

質問者の工夫

• Offline Policy: 質問は、Yes/Noの安定した回答を得るための明確さ、独立性、および高い情報利得を優先しました。情報利得が高くても明確さが欠ける質問は選択されないよう、質問選定アルゴリズムに「Tie」オプション（YesでもNoでもない回答）を導入し、最も高いE値（キーワード候補削減数の期待値に関連する指標）を持つ質問を選びました。
  

• ミラーマッチ対策付きAgent Alpha: Round 1で「Is it Agent Alpha?」に対してYesが返ってきた場合、バイナリサーチを使用して、2,046件の主要キーワード候補から10ターン以内に検索を行い、それ以降は89,760件の補足的なキーワード候補を使用しました。この手法により、秘密のキーワードが主要キーワード候補内にある場合は、単純なAgent Alphaに勝つことができるので、Agent Alphaのミラーマッチにおける勝率を向上させました。

回答者の工夫

• ルールベースのYes/No応答: 全体の約15%の回答を担います。特定のプロトコルに一致する質問に対してルールベースでYes/Noの応答を行います。23種類のプロトコルが含まれ、実装ミスを最小限に抑えるためにテストケースを複数用意しました。
• 事前定義のキーワード-質問ペア: 全体の約5%の回答を担います。事前定義のマトリックスと一致する場合は、そのペアに対応する適切な回答を返しました。
• LLM（Llama3.1-8B-IT） + Wikipediaコンテキストベースの応答: 全体の約80%の回答を担います。137,468件のWikipediaのタイトルと秘密のキーワードを比較して関連テキストを取得することで、LLM（Llama3.1-8B-IT）の知識ベースを拡張し、精度を向上させました。また、bad_words_idsを設定し、特定のトークンの出現確率を調整しています。
• 例外の応答: 全体の約0%の回答を担います。エラー発生時などは"no"と返答します。一部参加者のエージェントは、ペアのボットにエラーを生じさせるアプローチを採用しているため、有効だった可能性があります。

データセットの作成の工夫

• キーワード収集: LLM（GPT-4o mini）を使用してキーワードリストを生成し、共有されている全てのキーワードデータセットを追加しました。また、英語版Wikipediaのタイトルを「Things」カテゴリーに属するかをLLM（GPT-4o mini）に判断させました。一部、手動でキーワードを追加しました。最終的なデータセットには15,113のキーワードが含まれました。パブリック キーワードと Tier 1 キーワード (生成されたキーワードの中で最も品質の高いデータセット) のllama3.1-8B-ITの埋め込み表現をUMAPで次元削減し可視化しています。
  

• 質問収集と削除: 上位のKagglerのエピソードから質問を収集し、明確さに欠ける質問や他の質問と高い相関を持つ質問を削除しました。最終的に521の質問を選択しました。

• 回答の作成: LLM（GPT-4o mini）を使用してYes/Noの回答を生成し、Tieの応答を含むデータセットを作成しました。

その他の工夫

• スコアリングシステムの導入: キーワード候補をラウンドごとに更新し、Yes/Noの一致でスコアを増減させました。Tieの応答に対してはスコアを更新せず、不要な調整を避けました。
  

• データセットのソート: 質問は初期値のEでソートされ、キーワードデータセットはTier 1から4（1が最高）に分割されました。これにより、特定のデータセットへの依存を避けることができました。

5th Place Solution by yukky_maruさん

このソリューションは、メタゲームへの適切な対応を行い、Agent Alphaを発展させたアプローチです。また、単語頻度に基づく事前確率分布をキーワードに設定することで、勝率を高める工夫を行っています。

質問者の工夫

• Agent Alpha->候補の提示: 質問者はバイナリサーチ型のAgent Alphaを使用しています。キーワードリストから秘密のキーワードを推論する際、まず単語頻度が高いキーワードが秘密のキーワードである可能性が高いと仮定しました。この仮定に基づき、すべてのキーワードに対してこのメトリックを計算し、スコアが最も高いキーワードを推論する戦略を採用しました。また、すべてのキーワードの合計文字数が約 1400 文字以下になった時点で、辞書式順序に基づく二分探索から単語頻度に基づく二分探索に切り替えました。具体的には、質問を次のように変更しました。

「キーワードは次のいずれかですか？{トップ 1 単語頻度の単語}、{トップ 2 単語頻度の単語}、{トップ 3 単語頻度の単語}、…"

これにより、単語の出現頻度が高いキーワードを使用したバイナリ検索が可能になりました。

回答者の工夫

• ハードコーディングと正規表現の活用: 回答者戦略の最も重要な部分は、質問に対して正確な回答を提供することです。しかし、小さなLLMではこれを実現することは困難です。そこで、可能な限りLLMの使用を最小限に抑え、ハードコーディングされた回答を使用することに注力しました。全ての質問に対してハードコーディングすることは不可能であるため、Publicリーダーボードから収集した「", ', ,」などの文字を含む全ての質問をパターンに分割し、正規表現を使用してマッチングを行いました。これらの質問は、キーワードの構造的属性に関連することが多いため、正規表現を用いた手動関数でYes/Noの回答を提供しました。それ以外の質問については、Llama 3.1に基づく8Bモデルを使用しました。

データセットの作成の工夫

• オブジェクトの収集: キーワードリストが主に実際の物体を表していることを確認したため、収集するキーワードもオブジェクトに限定しました。具体的には、Conceptual CaptionsやCoco Captionの画像キャプションデータセット、およびAmazonレビューのデータセットから名詞のみを抽出し、これらの名詞をGemini Flashを使って100語ずつ処理して必要な名詞をフィルタリングしました。加えて、WordNetからも名詞をリストに追加しました。

その他の工夫

• Agent Alphaのハンドシェイクのスキップ: 他の参加者の強力なハードコーディングアプローチを信じ、初期ハンドシェイクなしで全エージェントに対して辞書順に基づくバイナリサーチを実施しました。これにより1ターン節約することができます。

4th Place Solution by Karam Al-Robaieさん、VassiliPhさん、Jasper Butcherさん、Devnirwal01さん

このソリューションでは、LLMと正規表現を組み合わせた回答者戦略と、Agent Alphaを取り入れたアプローチを採用しています。LLMにMistral-7Bを採用している事が特徴的です。

質問者の工夫

• Agent Alpha: 多くの提出されたLLMが質問に適切に答えられないことが明らかになったため、締め切り直前にAgent Alphaのアルファベット順二分探索を採用。これにより、最も可能性の高いキーワードを効率的に推測しました。
• ハンドシェイクの採用: Agent Alphaを起動するかどうかについて議論がありましたが、最終的には1ターンを犠牲にしてでも確実な回答者を得られることを優先しました。

回答者の工夫

• 正規表現による質問対応: 特定のパターンに一致する質問に対しては、22種類の正規表現を用いて対応しました。中でも、アルファベット順二分探索と最初の文字を特定する質問に対応する正規表現が主に機能しました。
• LLMの使用: 最終的にはMistral-7Bを使用しました。このモデルは他のモデルと比べ、noと回答する傾向が強く、この特性を利用してより効率的にキーワードを特定しました。複数のプロンプトを用いて少数の質問に対して投票を行い、最も一般的な回答を選択しました。

データセットの作成の工夫

• キーワードリストの生成: キーワードリストは、12カテゴリー、1700のサブサブカテゴリーに分類され、それぞれに対してLLMを用いて100件のキーワードを生成。これを繰り返し、大規模なキーワードリストを作成しました。また、出現頻度の高い英単語や国・都市リストもバックアップとして低い確率で追加しました。

その他の工夫

• 質問ツリーのアプローチ（未採用）: 当初、質問ツリーを使用してキーワードを特定するアプローチを考案しました。各ノードに質問を配置し、キーワードをそれに基づいて分類するという手法です。しかし、他のボットのLLMの品質が低かったため、このアプローチは最終提出には採用しませんでした。その他のトライについても多く触れています。

3rd Place Solution by loh-maaさん

このソリューションは、特にAgent Alphaの戦略を駆使し、質問者と回答者の両方で高いパフォーマンスを発揮しました。また、6-shotプロンプトを用いた回答や、エントロピー最小化を用いたOffline Policyなど、多岐にわたる工夫が施されています。

質問者の工夫

• Agent Alpha: 60,008件のキーワードを用いて二分探索を行い、キーワードのランクに基づく探索を行いました。この手法は、既知のキーワードが均等に出現する場合に最適です。また、推測時には、Llamaによる補完的な候補生成を用いて、範囲を絞り込みました。

• Offline Policy: エントロピー最小化とベイズ更新に基づく質問選定を行い、可能性の高いキーワードを絞り込みました。このアプローチにより、特定の質問順序に依存せず、効果的な情報引き出しが可能になりました。

回答者の工夫

• 正規表現: 「最初の文字」や「末尾が何か」といった一般的な質問に対して正規表現を用いて対応しました。これにより、さまざまな質問者エージェントと効果的に協力することが可能になりました。

• Alpha Answerer: Agent Alphaクラスに統合された正規表現に基づき、特定の質問に迅速に対応しました。

• Llama 3 Answerer: Llama 3（HuggingFace 8b-instructモデル）を用いて、正規表現で処理できない質問に対応。6-shotプロンプトを与えることで、安定した「yes」または「no」の回答を得られるようにしました。

データセットの作成の工夫

• キーワードリストの生成: Llamaを使用して、各公開キーワードに類似するキーワードリストを生成。これにより、60,008件のキーワードが作成され、そのうち1,468件が正解キーワードとしてヒットしました。キーワードのランクは、複数のソースの「品質」に基づいて決定されました。

• 複数ソースからのデータ統合: 複数の公開された単語リストや過去の研究からの単語リストを統合し、キーワードの収集を行いました。名詞リストに限定し、正規表現を用いて適切な形態に正規化しました。

その他の工夫

• Llamaバックアップ: Llama 3を使用して、Offline Policyが持つ知識を基に新しい推論を行いました。これによって、事前に用意したキーワードリストに、シークレットキーワードが含まれないケースに対応しました。質問者エージェントの16ラウンド後に使用され、セルフプレイでは約10%の成功率を達成しました。

2nd Place Solution by Andrew Tratzさん

このソリューションは、事前に質問を用意するOffline-PolicyではなくOnline-onlyのLLMベースの質問者を使用し、ユニグラム（単語）に焦点を当てています。主要なアイデアとしては、Agent Alphaによるユニグラム中心のサーチ、文脈の自動要約、複数のモダリティ（カテゴリ、位置、サイズ、デフォルト）を用いた質問システムが挙げられます。

質問者の工夫

• ユニグラム中心のAgent Alpha: 質問者は「Is it Agent Alpha?」の質問でAgent Alphaの有無を確認し、確認後はユニグラム（単語）に基づくサーチを行いました。初期の検索段階では、使用されていない最も頻度の高い単語を使用し、最初の単語が特定されるか、すべての単語が除外されるまで検索を続けます。その後、LLMを使用して名詞句を提案し、特定の名詞句が正解キーワードであるかを推測しました。
• オンラインLLM質問者: オンラインでリアルタイムに質問を生成し、事前に準備された質問を使用しない質問者エージェントを作成しました。カテゴリ、位置、サイズ、デフォルトの4つのモダリティを持ち、各モダリティに応じた質問を行うことで、キーワードを絞り込みます。例えば、カテゴリモダリティでは、現在のカテゴリを2つの非重複のサブカテゴリに分割する質問を行います。そして、LLMを用いてキーワードを列挙および推論します。

回答者の工夫

• 段階的な回答システム: 回答者は、2つのステージで動作します。第1ステージでは、アルファベット順、リストチェック、または文字を含むタイプの質問に対応し、ルールベースで比較を行います。第2ステージでは、LLMを使用して質問に答え、キーワードを文に置き換えて回答の精度を向上させました。

データセットの作成の工夫

• ユニグラムデータセット: 英語の単語頻度データセットから始め、LLMを用いて120,000のユニグラム（単語）を選定しました。このデータセットには、無駄な単語が含まれている可能性がありますが、ユニグラム中心のAgent Alphaサーチに最適化されています。

その他の工夫

• 自動要約と文脈保持: 推論者は、キーワードに関する理解を段落形式で保持し、各質問と回答の後に要約を更新しました。これにより、LLMが自然言語での説明に基づいて推論する能力を向上させ、回答者の誤答に対しても対応できるようになりました。

1st Place Solution by c-numberさん

このソリューションは、Agent Alphaの導入やデュアルLLMアプローチ、そして自然な質問生成のためのGPT-4o miniの活用により、他のソリューションと差別化されています。計算リソースを最大限に活用し、最終的な勝利を収めた戦略が非常に印象的です。

質問者の工夫

• Offline Policy: PythonのNLTKライブラリを使用して、名詞に絞った116,937件のキーワードリストを作成しました。キーワードは「もの」であると定義されているため、名詞のみを選択しました。エントロピーに基づく質問の選択方法は、11位ソリューションと同様のアプローチです。

• Agent Alphaの導入: 質問者の戦略として、トップパフォーマンスを示す回答者がAgent Alphaモードを実装する可能性が高いと判断し、自身の質問者戦略にAgent Alphaモードを取り入れました。これにより、競争力を確保しました。

• キーワード確率推定: Agent Alphaの報酬期待値を最適化するために、各キーワードがテストデータに含まれる確率を推定しました。この確率推定には、以下の要素を考慮しました：

  • キーワードの単語数
  • 英単語頻度データセットを用いた英単語頻度
  • GPT-4o miniを用いた「ものらしさ」確率

  「ものらしさ」は、GPT-4o miniに「この単語'{keyword}'は一般的にものと見なされますか？」という質問をし、その次のトークンが「Yes」か「No」になる確率を取得して計算しました。

• バイアスされたキーワード確率を用いた効率的なバイナリサーチ: 各キーワードの確率が確立された後、バイナリサーチを行い、効率的に確率を半分に絞り込む戦略を採用しました。これにより、単にキーワード数を減らすのではなく、より効率的な検索が可能となりました。

回答者の工夫

• デュアルLLMアプローチ: 回答者には、異なる種類の質問に対応するために2つの異なるモデルを組み合わせました。

  • 汎用LLM: Meta-Llama-3-8B-Instructを使用し、キーワードに関する幅広い一般的な質問に対応しました。
  • 数学特化型LLM: DeepSeek-Mathを使用し、複雑な数学的な質問やパターン認識が必要な質問に対応しました。このモデルは、AI Mathematical Olympiadコンペティションで人気を博し、数学問題を解くためのPythonプログラムを生成する能力を持っています。

• モデル選択ロジック: 質問の中に「letter」などの特定のキーワードが含まれている場合に、ルールベースのシステムでどのモデルを使用するかを決定しました。

データセットの作成の工夫

• 自然な質問の生成: GPT-4o miniを用いて、ゲームの各段階でキーワードを効果的に絞り込む質問を生成しました。これにより、各ステージで候補となるキーワードを半分に絞る質問ができるようになりました。

• 確率表の作成: LLMを使用して各キーワード-質問ペアに対するp(keyword, question)を推定しました。Meta-Llama-3-8B-Instruct、Phi-3-small-8k-instruct、gemma-7b-itの3つのモデルを使用し、その結果を平均しました。

その他の工夫

• 大規模な計算処理: 確率テーブルの作成には膨大な計算が必要であったため、vllmを活用し処理を高速化しました。最終週には、Runpodで8x RTX 4090構成を使用し、計算リソースに約500ドルを投じて最終的な結果を得ました。

おわりに

LLM 20 Questionsに参加された方も、参加されていない方にもこの記事が参考になれば幸いです。

余談ですが、1年前に『Kaggleのハードルを下げたい！』という記事を執筆し、大きな反響を頂きました。

Kaggle Master昇格までに取り組んだことを整理し、続編の記事を執筆予定です。
-> 記事を公開しました！（2024.09.01追記）

本記事は以上です。皆様の良いKaggleライフを応援しております。