ARISE analytics kaggle部の越智です。
今年の7月25日まで開催されていた「USPTO – Explainable AI for Patent Professionals」にソロで参加し銀メダル(44位/571チーム)を獲得できました。
そこで今回はコンペの概要と私が取り組んだアプローチ、上位陣のアプローチを紹介したいと思います。
コンペ概要
コンペの内容
本コンペは、ある特許に対して類似した50件の特許を取得する検索クエリを生成することを目的としています。
類似した50件の特許の取得方法としては、Googleの機械学習によるベクトル検索を用いており、具体的には特許の内容をベクトルに変換し類似度を計算するといった処理で決定されています。
しかし、類似した50件は上記のようにベクトルで計算したものであり、どのフィールド(タイトル、概要、説明文 etc.)、どのキーワードが起因して類似と判断されたのかわかりません。
そこで特許の類似性を解釈可能な形にするために、本コンペでは類似した50件の特許をヒットさせるための検索クエリを探索するというタスクが課されていました。
データセット
次は与えられたデータセットについて説明します。
訓練データとして、ある特許のIDに対して類似した特許50件のIDが紐づいているデータが与えられました。また、各特許のメタ情報のデータセットも存在し、これには、特許のタイトル、特許のcpcコード(特許の技術分野を分類するコード)、特許の概要、特許の主張、特許の説明、発行日、申請日などが含まれています。メタ情報の単語を用いてクエリを作成するのが良さそうです。
本番用のテストデータも上記と同じ形式のデータが与えられていますが見ることはできません。クエリを作成するnotebookを提出し、kaggleプラットフォームの裏側で実行した結果である予測を評価するnotebookコンペとなっています。
評価方法
作成したクエリを実際に検索し、上位50件にどれだけ正解の特許50件が含まれているかどうかで評価されます。
検索にはwhooshという特許検索データベースエミュレーターを利用します。手元でも検証可能なようにwhooshのライブラリが提供されています。クエリが、タイトル、cpcコード、概要、主張、説明の文章のいずれかにヒットした特許のうち上位50件が検索結果として返されます。ただし、手元で実行できるエミュレーターの検索対象の特許は与えられたデータセットの中にある特許のみであり、本番の検索対象とは異なります。
評価関数はmAP@50が使われています。式は以下です。
\(\text{mAP@50} = \frac{1}{Q} \sum_{q=1}^{Q} \left( \sum_{k=1}^{\min(50, R_q)} \frac{1}{k} \text{Precision}_q(k) \cdot \text{Rel}_q(k) \right) \)
\(Q\): 特許の総数
\(R_q\)クエリ\(q\) に対して評価される検索結果の特許の数
\(\text{Precision}_q(k)\)クエリ\(q\) に対して位置\(k\)までの特許の精度
\(\text{Rel}_q(k)\): クエリ\(q\) に対して位置\(k\)の特許が類似特許の場合は 1、そうではない場合は 0
\(\min(50, R_q)\): クエリ\(q\)の検索結果の特許の数と 50 のいずれか小さい方
mAP＠50の式の特性上、同じ正解特許のヒット数でもその特許が上位にあればあるほどスコアは高くなります。
具体例 : 全2500特許を検索し、関連特許50件のうち1件しか正解の特許をヒットしなかった場合
・1番目にヒットした場合 1/2500(1/1 + … + 0 ) / 50 = 1/ (2500*50)
・30番目にヒットした場合 1/2500(0 + … + 1/30 + 0 + … +0) / 50 = 1/ (2500*1500)
そのため、正解の特許のヒット数だけでなく、どれだけ上位にヒットさせるかどうかも重要になってきます。
※ ただし、本コンペではmAP@50の計算式が一部間違っているという指摘がありました。それでも上記の考え方で問題はありません。
解法
本解法ではクエリ探索に貪欲法を使いました。
具体的には、以下のステップで探索していきます。
- 訓練データにあるすべての特許のタイトル、cpcコードそれぞれに対して、単語のTF-IDFの重みを計算
- 以下のように、クエリのトークン数制限 (後述) まで単語を1つずつクエリに追加
- 類似特許50件に出現する単語のうち、まだクエリ候補の単語群にないTF-IDFが最も高い単語を抽出
- クエリ候補の単語群と抽出した単語にあるすべての単語を”OR”で繋いでクエリを作成する
- 作成したクエリをwhooshで検索し、ヒットした上位50件の特許と正解の上位50件の特許とのmAP@50を計算する
- 単語を追加する前のmAP@50より高い場合は、その単語をクエリ候補の単語群に追加する。
クエリは単語と演算子を合計して最大50トークンと定められています。 (例: 「”A” OR “B” OR “C“」の場合、5トークン) また計算時間にも制限があったため、トークン数制限を23単語とOR演算子の合計45トークンとしました。
最初にTF-IDFを計算しているのは、各特許に出現する単語について、その特許を特徴づける単語を見つけるためです。単語抽出元のフィールドが「タイトル」と「cpcコード」だけなのは、その他の「概要」や「主張」を含めると検索時間が膨大で制限時間に収まらないためです。
またwhooshでは、OR条件のクエリでヒットした特許が複数ある場合、その特許におけるクエリの単語のTF-IDF値の合計がより高い特許が上位に来るようになっているそうです。よって、ヒットさせたい50件の特許に出現する特徴的な単語をより多くクエリに含めるために、TF-IDFの高い単語から探索する解法としました。
その他にも、焼きなまし法、決定木によるクエリを特徴とした特徴選択、集合被覆問題、混合整数計画法などを試してみたものの、この単純な解法がCV、LBともに最もスコアが良い結果となりました。(最適化問題は実装が上手くできていなかったかもしれません。)
一方、クエリに使える演算子はORだけではなく、AND、NOT、EXOR、ADJ、NEARなどもありました。ANDの利用も試したものの単語数が増えてしまうため断念しました。また、*、?、$のようなワイルドカードも使用可能でしたが、検索に時間がかかり提出エラーとなってしまい上手く活用できませんでした。
上位者の解法
上位者の解法
本解法とは異なるいくつかの上位者の解法を説明します。基本的には、いかに制限内に収まるようにトークン数を減らすかがキーとなっていました。
特に、magicによって同じ単語数でもトークン数を大幅に減らせることができるため、ここに気づくことができなかったのが残念です。
magicについて以下のようにすることでwhooshにおいてクエリのトークン数を減らすことができます。
・「AND」を「-」に置き換える。例えば、「”A” AND “B”」はトークン数3だが、「”A”-”B”」でトークン数1に削減できる。
・「AND」とホワイトスペースを省略する。例えば、「”A” AND “B”」はトークン数3だが、「”A”“B”」でトークン数1に削減できる。
magicによって1トークンとしてANDで単語を繋いたクエリを複数作成し、焼きなまし法、BEAM Search、混合整数計画法などを用いてORで繋ぐトークンの部分集合を選択していました。
終わりに
今回は、銀メダルを獲得したUSPTOコンペの解法について紹介しました。
普段参加するデータを分類するようなコンペとは異なり、探索や最適化の手法を考えるコンペだったためとても勉強になりました。特に、直近参加したいくつかkaggleコンペでは手元の検証データとpublic、privateのデータ分布の違いによるスコア差に悩まされたので、今回は手元の検証データとLBに相関があり安心して取り組むことができました。
ARISE analyticsでは、kaggle等の分析コンペティションで上位成績を残すと、インセンティブとして報奨がもらえるARISE Tech Master制度があるので引き続き金メダルを目指し、努力していきたいです。
分析はチームワークが大事です。役割を決めお互いの強みを持ち合うことで、一人で行うより何倍も効率的に分析課題に取り組めます。我々と一緒にKaggle部を盛り上げてくださる方、ARISE analyticsに興味を持っていただいた方はこちらの採用ページをご覧ください。
※過去のKaggle部活動記はこちら
※ARISE analytics 公式noteはこちら