はじめに

2024年7月25日まで開催されていた 「USPTO - Explainable AI for Patent Professionals」 で社内チーム(@s_shohei, @sakusaku)で参加し、金メダル(5位/572チーム)を獲得しました。 この記事では金メダル獲得のために行った特許検索クエリの構築について解説します。 Kaggleに投稿したSolutionはこちら。

この記事の構成は以下です。

• コンペ概要
• 評価方法と基本戦略
• チームの解法
• 時系列順の取り組み
• 上位解法の概要
• まとめ

コンペ概要

コンペ目的

このコンペの目的はある特許に対する類似特許を50個取得する検索クエリを作成することです。

通常の Kaggle コンペであれば、ある特許に対する類似特許を50個提出し、それが正解データ50個とどの程度一致しているのかを評価されるものになると思いますが、このコンペでは既に類似特許50件が与えられています。この類似特許50件は Google の機械学習モデルが生成した Embeddings により作成されています。
しかし、この特許の類似特許はこの50件です、とだけ出されても全く説明性がありません。そこで、本コンペでは"類似特許50個を取得することができる検索クエリ"の作成が求められました。これにより、ブラックボックスである機械学習モデルの結果を特許の専門家が解釈可能な結果に変換することができます。これはコンペのタイトルである、“Explainable AI for Patent Professionals"にも表現されています。

検索は Python で実装された全文検索エンジン (Whoosh) を用いて行われます。

訓練データとして以下の nearest_neighbors.csv が与えられています。参加者は neighbor_0~49 を取得することができるクエリを構築することを目指します。

nearest_negihbors.csv

データ概要

クエリを作成するために利用できるデータとして以下のものが提供されていました。

• patent_metadata.parquet
  • 特許のメタデータ。特許公開日、 cpcコード(特許分類コード)などを含む。約1330万件。
• test.csv
  • クエリ提出対象の特許、nearest_neighbors.csv のサブセットになっている。2500行。
• patent_data/[year_month].parquet
  • Google Patents Public Dataからの特許テキスト。特許識別子(publication_number)、タイトル(title)、概要(abstract)、請求項(claims)、全文説明(description)を含む。

また提出においては以下の注意点があります。

• 評価時に利用される Whoosh の検索インデックスは非公開（特許全体はリソース的に無理、運営が設定している）
• test.csv に含まれる特許は最大 2500 * 50 = 12250（実際は neighbor_X での重複があるので少し少なくなる）

Whoosh について

全文検索エンジンである Whoosh で実行できるクエリとして以下の操作がサポートされていました。

• Boolean: OR, AND, NOT, XOR
• Proximity:
  • ADJ: 2つの単語が1-9語以内に順番通りに出現する。例: cheese ADJ3 bread
  • NEAR: 2つの単語が1-9語以内に任意の順序で出現する。
• Wildcards:
  • *: 任意の文字数に一致
  • ?: 単一文字に一致
  • $: 特定の文字数に一致
• Phrase:
  • “cheese bread” などのフレーズ(n-gram)での検索

提出できるクエリの長さは 50 トークンに制限されていました。トークンは Kaggle が用意した関数 count_query_tokens でカウントされます。この関数では文字列を空白で分割し、1分割 = 1トークンとしてカウントしています。 後述しますが、多くの上位チームがトークンカウントについて工夫を行っておりその工夫が今回の上位入賞には不可欠な要素となりました。

提出ファイルと評価について

参加者は目標とする50件の特許を取得するために、メタデータやテキストデータを利用し、各検索フィールド（cpc、title、abstract、claims、description\）に対するクエリを組み合わせて構築されたクエリを提出します。提出ファイルは以下の形式です。

publication_number,query
US-2017082634-A1,text AND search
US-2017180470-A1,text AND search
US-2018029544-A1,text AND search
...

特許検索クエリが取得する特許と正解の関連特許セットとの間の平均適合率（mAP@50）を使用して評価されます。

評価指標と基本戦略

評価指標について

評価指標の詳細についてコンペ序盤に Discussion で評価指標である Aerage Precision の計算が定義と異なる可能性があることが指摘されていました。

指摘されていたのは具体的に以下の箇所です。

def ap50(preds, labels):
    precisions = list()
    n_label = len(labels)
    n_found = 0
    for e, i in enumerate(preds):
        if i in labels:
            n_found += 1
        precisions.append(n_found/(e+1))  # <<<< 本来の実装
            precisions.append(n_found/(e+1))  # <<<< 本コンペでの実装はこうなっているのではという指摘
    return sum(precisions)/50

この指摘について検証するために、実際に2つの提出を行い理論値と Public LB の値がほぼ同じになることを確認しました。

• True Positive:TP = 1, False Positive:FP = 0 となるクエリの提出（理論値: 0.089, LB: 0.08）
  • neighbor50個の中から1つ特許を選んで abstract フィールドの先頭20単語を使った phrase クエリを作成して提出（ほぼ必ず TP1, FP0のクエリとなることを想定）
• TP = 2, FP = 0 となるクエリの提出（理論値: 0.159, LB: 0.15）
  • neighbor50個の中から2つ特許を選んで abstract フィールドの先頭20単語を使った phrase クエリをそれぞれ作成、OR 結合して提出（ほぼ必ず TP2, FP0のクエリとなることを想定）

この評価指標では検索結果の上位にTPが並ぶことが非常に重要です。以下の画像は topN までを完全正解した際に得られるスコアを表しています。検索結果の順位が上位のほうがスコアに対する寄与が大きく、下位のほうがスコアに対する寄与が小さいことが確認出来ます。 同じTP10個得られるクエリでも検索順位によって以下のように大きなスコア差が発生します。

• TP10個の後にFP40個が続く -> スコア0.514
• FP40個の後にTP10個が続く -> スコア0.023

基本戦略

• 評価指標において上位の FP によるスコアの損失が大きいこと
• test で与えられる Whoosh の検索インデックスが未知であり FP をクエリで除外（NOT）することは難しいこと

このようなコンペの特徴から以下の基本戦略を設定しました。

基本戦略

• 可能な限りFP=0でトークンが少ない TP>0 のクエリ候補を作成する
• クエリ候補を全体のトークン数上限まで OR 結合しできるだけ多くのTPを集める

トークン数の上限は50なのでもし (TP1, FP0) のクエリ候補を1トークンで作成出来た場合、OR 結合すると最大25候補結合することが出来ます。(TP25, FP0) のスコアは大体0.84 なので最終結果のLB上でも金メダル圏近くのスコアとなります。

この方針に気づけたことが今回のコンペで上位入賞の鍵だったと思います。

チームの解法

解法の概要

前述の基本戦略に従い検証を進め、最終的な解法は以下の内容になりました。

• クエリ候補の作成
  • Global Counter のクエリ候補
  • 50c2 のクエリ候補
• Magic: トークンハック
• 集合被覆問題としてTP最大、FP最小のクエリ候補を選ぶ

クエリ候補の作成

Global Counter のクエリ候補

各フィールドにおける単語もしくは n-gram が今回与えられた全特許(約1330万件)のうち、何件の特許に出現するかを事前に数えます。これを Global Counter と呼びます。

Global Counter を元に与えられた neighbor0~49 に対するクエリ候補のTP, FPを以下のように計算します。

• TP の計算
  • neighbor0~49 に出現する単語もしくは n-gram が neighbor0~49 のどの特許において出現するか算出する
• FP の計算
  • “ある単語もしくは n-gram の Global Counter での出現特許数 - neighbor0~49 のにおける出現特許数” で算出する
  • 例） “ti: device” が Global Counter で5特許に出現、neighbor0~49 のうち3特許で出現している場合FP=2となる

この方法で作成されるクエリ候補は以下のようなものになります。

提出では検索インデックスに含まれる特許は全特許のうちの一部サブセットとなっているため、FPの数は評価時の実際の値と異なります。ですが、FP=0 の場合を保証できることがこのクエリ候補のメリットで、FP=0の候補を OR でつなぐことで TP=25, FP=0 のクエリを構築出来、PublicLB 0.85 を達成出来ました。

idf + 50c2 のクエリ候補

Global Counter での候補で成果を得られた後、次に検討したのがTPを2以上取れてFP=0となるクエリ候補の検討です。

このようなクエリ候補を idf(inverse document frequency) と neighbor0~49 内の 50c2 の特許の組み合わせを見ることで作成しました。

• neighbor0~49 の中で 50c2(=1225) の組み合わせをみる
• 組み合わせの中で共通に出現している単語を idf の上位から取得する
• 取得した単語の idf の合計が閾値（実験的に設定した）を超えた場合、単語を AND でつないでクエリ候補とする
  • IDFは特許出現確率の逆数の対数である、IDF値を合計するとAND条件のクエリ候補の特許出現確率が得られると想定
  • 実験的にIDFの合計が大体80を超えると、FP=0（見ている2つの特許の組み合わせでしか出現しないクエリ候補）となることがわかった

この方法で作成されるクエリ候補は以下のようなものになります。

この手法は TP2,FP0 のクエリ候補を作成することが出来ますが、2つの特許に共通する単語を AND で繋いでいく必要がありトークンを大量に消費してしまうクエリ候補が出来てしまいます。この問題は次の “Magic: Token Hack” で解決出来ました。

Magic: トークンハック

def count_query_tokens(query: str):
    return len([i for i in re.split('[\s+()]', query) if i])

トークン数は提出されたクエリに対して上記のコードで Kaggle 側が算出し、50トークン以上のクエリが含まれていた場合は Submission Scoring Error として扱われるようになっていました。

しかし、このトークンのカウント方法と実際に Whoosh ライブラリでクエリがパースされるときの扱いが異なり AND や Phrase 検索が実質1トークンで行える方法がありました。

具体例

実際多くの上位チームがこの Magic を見つけ採用していため、上位入賞には必要な気づきでした。

集合被覆問題

前述の方法で neighbor0~49 に対して大量のクエリ候補を作成した後、50トークン以下でTP数最大化、FP数最小化ができるクエリ候補の部分集合を選びます。

これは集合被覆問題として知られていて、線形計画問題としてソルバ(ortools)で解を作成しました。

ソルバで選ばれたクエリ候補を OR で繋いだ結果の最終的なクエリの例を示します。前述の Magic によって49トークンのクエリとなっています。

(cpc:"B60P1/165"cpc:"E02F3/3483"cpc:"B60P1/165"cpc:"E02F3/3486") OR (cpc:"B60D1/26"cpc:"B62D49/04"cpc:"B60D1/26"cpc:"E02F3/6472"cpc:"B60D1/26"cpc:"E02F3/655"cpc:"B62D49/04"cpc:"E02F3/64"cpc:"B62D49/04"cpc:"E02F3/6472"cpc:"B62D49/04"cpc:"E02F3/655"cpc:"B62D49/04"cpc:"E02F9/2016"cpc:"E02F3/6472"cpc:"E02F9/2016"cpc:"E02F3/655"cpc:"E02F9/2016"detd:"courli"detd:"lgayea") OR (cpc:"B65F2003/0283"cpc:"E02F3/3486"cpc:"B65F3/046"cpc:"E02F3/3486"ti:"end@loader@actuating"ti:"loader@actuating"ti:"loader@actuating@mechanism"ti:"actuating@mechanism@dump"cpc:"B65F2003/0283"cpc:"B65F3/046"detd:"horbe") OR (detd:"wharfpthe"ti:"dumping@scoop"ti:"side@dumping@scoop"detd:"hatchof") OR (detd:"powerswung") OR (detd:"shlppee") OR (detd:"0rneypearce"detd:"schaepcrklaus"ti:"as@asphalt@or"ti:"improvement@therein@laying"ti:"laying@surfacing"ti:"laying@surfacing@material"ti:"machine@and@improvement"ti:"surfacing@material@as"ti:"therein@laying"ti:"therein@laying@surfacing"detd:"comprlsesr") OR (detd:"disswingable"detd:"rdlyonto"detd:"sitionedsymmetrically"detd:"understandingflof"detd:"opjusting") OR (ti:"mechanical@shoveling@machine"ti:"mechanical@shoveling") OR ((detd:"tractors"detd:"ravity"detd:"scrapers"detd:"kick"cpc:"E02F3/6472"ti:"scraper"cpc:"E02F3/656"detd:"apron"detd:"scraper"detd:"hingedly"detd:"tractor"detd:"sheave"detd:"sheaves"detd:"cooperates"detd:"dead"detd:"axle")) OR ((detd:"oor"detd:"exible"detd:"retracting"detd:"trough"detd:"retracted"detd:"turntable"detd:"underground"detd:"jacks"detd:"therealong"detd:"rectilinear"detd:"propelling"detd:"conveyor"detd:"extensible"detd:"slip"detd:"clutch"detd:"mines"detd:"adjustably"detd:"engageable"detd:"elevating"detd:"hydraulic")) OR ((detd:"shovelling"detd:"tom"detd:"cushioned"detd:"compel"detd:"swiveled"detd:"abruptly"detd:"swivelly"detd:"wardly"detd:"hose"detd:"guideway"detd:"swivelled"detd:"undesired"detd:"sup"detd:"ported"detd:"swivel"detd:"osgood"detd:"pile"detd:"muck"detd:"guideways"detd:"dig")) OR ((detd:"planetaries"detd:"payed"detd:"planetary"detd:"mosier"detd:"fiexible"detd:"2li"detd:"conveyer"detd:"tractive"detd:"lil"detd:"ior"detd:"exible"detd:"2s"detd:"yieldable"detd:"tunnels"detd:"compensating"detd:"excepting"detd:"lll"detd:"chute"detd:"illinois"detd:"geared")) OR ((detd:"fioor"detd:"simmons"detd:"overlie"detd:"hydraulically"detd:"attachable"detd:"swivelly"detd:"coal"detd:"jacks"detd:"swivel"detd:"anchor"detd:"joy"detd:"guideways"detd:"unison"detd:"propelling"detd:"pennsylvania"detd:"mining"detd:"extensible"detd:"transporting"detd:"tilted"detd:"elevating")) OR ((detd:"vfiled"detd:"communicable"detd:"eiect"detd:"hydraulically"detd:"sullivan"ti:"material"detd:"propulsion"detd:"machinery"detd:"claremont"detd:"bores"detd:"uid"detd:"pile"detd:"muck"detd:"lin"detd:"dig"detd:"trackway"detd:"conduits"detd:"5i"detd:"massachusetts"detd:"hydraulic")) OR ((detd:"i23"detd:"movementof"detd:"i26"detd:"insides"detd:"encircles"detd:"compactness"detd:"h2"detd:"cushioning"detd:"yieldably"detd:"reversely"detd:"pivoting"detd:"cams"detd:"mucking"detd:"abuts"detd:"lug"detd:"therealong"detd:"teeth"detd:"axles"detd:"scoop"detd:"nuts")) OR ((detd:"foolproof"detd:"selfcentering"detd:"impetus"detd:"i85"detd:"coaction"detd:"rockers"detd:"pinned"detd:"maxson"detd:"i00"detd:"pivotable"detd:"i05"detd:"fork"detd:"inadequate"detd:"dipper"detd:"compelling"detd:"plungers"detd:"incapable"detd:"h5"detd:"abrupt"detd:"tang")) OR ((detd:"evidently"detd:"shank"detd:"receivable"detd:"hoses"detd:"venting"detd:"urges"detd:"interrupting"detd:"vented"detd:"hose"detd:"rolls"detd:"inactive"detd:"claremont"detd:"interrupted"detd:"3i"detd:"joy"detd:"guideways"detd:"trackway"detd:"pennsylvania"detd:"embodies"detd:"assumes")) OR ((detd:"seam"detd:"bevel"detd:"brake"detd:"rocked"detd:"wheeled"detd:"propulsion"detd:"spur"detd:"rst"detd:"coal"detd:"pinion"detd:"withdrawal"detd:"gearing"detd:"shafts"detd:"extensible"detd:"clutch"detd:"keyed"detd:"elevating"detd:"hydraulic")) OR ((detd:"draulic"detd:"hy"detd:"4s"detd:"vfor"detd:"oor"detd:"zontal"detd:"withdrawing"detd:"ie"detd:"andv"detd:"progresses"detd:"mw"detd:"lo"detd:"anchor"detd:"teeth"detd:"conveyor"detd:"extremity"detd:"3l"detd:"hydraulic")) OR ((detd:"isv"detd:"isprovided"detd:"sion"detd:"ropes"detd:"rope"detd:"suddenly"detd:"vof"detd:"relied"detd:"thel"detd:"urge"detd:"anda"detd:"4l"detd:"0f"detd:"gearing"detd:"anchored"detd:"transportation"detd:"mining"detd:"lthe"detd:"transporting")) OR ((detd:"posltion"detd:"motive"detd:"unwind"detd:"drifts"detd:"rearmost"detd:"tunnels"detd:"cated"detd:"segmental"detd:"injury"detd:"imparting"detd:"pile"detd:"ward"detd:"ap"detd:"scoop"detd:"swings"detd:"mines"detd:"reversible")) OR ((detd:"adaptedv"detd:"grooved"detd:"ore"detd:"chine"detd:"vhen"detd:"t0"detd:"opera"detd:"vand"detd:"sidewise"detd:"wheeled"detd:"thev"detd:"meshes"detd:"andv"cpc:"E02F9/022"detd:"movably"detd:"idler"detd:"coal"detd:"pinion"detd:"casting"detd:"bears")) OR ((detd:"compel"detd:"abruptly"detd:"tensioned"detd:"swivelled"detd:"coincident"detd:"assured"detd:"turntable"detd:"claremont"detd:"swivel"detd:"osgood"detd:"fulcrum"detd:"loader"detd:"guideways"cpc:"E02F3/3486"detd:"trackway"detd:"propelling"detd:"rolling"detd:"assumes"detd:"alinement"detd:"swings")) OR ((detd:"hoists"cpc:"E02F3/657"detd:"hoist"cpc:"E02F3/656"detd:"medial"detd:"bumper"detd:"trunnions"detd:"trunnion"detd:"grading"detd:"brake"detd:"steering"detd:"spreading"detd:"tractor"detd:"propulsion"detd:"coacting"detd:"extremities"detd:"gearing"detd:"rail"detd:"dump"detd:"clutch"))

時系列順の取り組み

取り組みやその時の考察について時系列で紹介します。

5/20

題材が面白そうだったこととからMCDでチームを組み参加しました。初期は提出時の Kaggle 上での評価にバグがあったりしたことで参加者が少なかったです。

6/12 評価指標がわかる

“評価指標について” で解説したように Leader Board でのスコアの詳細についてこの段階でわかりました。 TP>0, FP=0 が達成できるようなクエリ候補を見つけ出し、集合被覆問題として解く基本戦略を立てたのもこの段階でした。

6/18 Global Counter の初期サブミット

Leader Board スコア 0.56

最初は、title や abstract などのデータ量が小さい検索フィールドを対象に Global Counter でのクエリ候補作成を行いました。当時の金メダル圏内に近いスコアを出すことができ、基本戦略の正しさをある程度確認出来ました。

~7/10 Global Counter のフィールドを追加する

Leader Board スコア 0.56 -> 0.85

基本戦略の手応えを感じた後は、claims や description の検索フィールドに対して Global Counter でクエリ候補を追加していく作業を進めました。

前述の通りすべてのクエリ候補で TP=1, FP=0 達成出来た場合、 (TP25, FP0) のスコアは大体0.84と事前に計算できていたので、理論値に達成することができたことに満足すると同時に今後の改善方法に頭を悩ませました。

7/10 Magic: トークンハックに気づく

Leader Board スコア 0.85 -> 0.89

最終2位のチームの方が当時LBで0.99のスコアを出しました。これまでの検証の結果から当時の我々の手法の延長線上で 0.99 に達成することは不可能であることに確信を持っていたので、どこかに必ず Magic があると考えました。

Kaggle から提供されていた count_query_tokens() のコードを注意深く観察すると、Whoosh ライブラリでのクエリパース結果と大きく異なることがわかりトークン数をハックできることに気が付きました。

きっかけは上位チームのスコアでしたが、注意深く観察し見つけることができ良かったです。

7/14 idf + 50c2 でのクエリ候補作成

Leader Board スコア 0.89 -> 0.94

TP=1, FP=0 のクエリ候補は十分作成出来たと考え、TP>1, FP=0 となるクエリ候補の作成に取り組んでいました。 idf（単語の出現確率）に着目しある特許ペアにしか出現しない単語集合を見つけられるのではという考察からその通りの結果を得ることが出来、クエリ候補を更に強化することが出来ました。

~7/25（最終日）

Leader Board スコア 0.94 -> 0.98

その後は強力なクエリ候補を追加することは出来ず、以下のようなチューニングを行いスコアを絞り出していきました。

• 提出時に test.csv データで検索 index を作成し、実際に作った複数のクエリを実行 -> 一番スコアが良いクエリを採用

スコア履歴

我々のチームの Public Leader Board スコア とコンペ終了時の賞金, 金, 銀, 銅メダルのライン

上位解法の概要

上位チームの皆さんは AtCoder Heuristic Contest などで活躍されている方が多く、探索や最適化が得意な方に向いているコンペだったと思います。

賞金獲得圏の6チーム中5チームが上述した Magic を使っていました。 Magic を使うことでおよそ +0.1 程度のスコア改善が得られるようです。 金メダルのチームの Solution を読むと以下のような共通点がありました。

• 今回の Metric の都合上、 FP に非常に厳しいことに気づく
• FP=0 の subquery を大量に生成し、その部分集合を OR でつないで最終的なクエリにする
• subquery
  • 要素を AND で繋いだクエリ
  • 例: clm:"diodes" AND clm:"charged" AND ab:"conversion" AND ...
  • 各 subquery は Magic によって1トークンになる
• 部分集合の選択
  • 焼きなまし、ビームサーチ、貪欲、ソルバなどで subquery 集合から部分集合を選択
• その他
  • NOT も使っている方はいたが(2nd)、改善幅はそれほど大きくない
  • ADJ, NEAR, XOR, ワイルドカードは使われていなかった

まとめ

この記事では Kaggle の USPTO の解法や取り組みについて解説しました。

特に重要だったのは、評価指標の理解とそれに基づいた FP 数最小化の基本戦略の設定であり、 Global Counter を適切に実装することで金メダルスコアを取ることができました。 最後の一押しとしてトークンハックの発見がありました。クエリ候補は AND で作成しておりトークンハックの発見によって1クエリ候補=1トークンとして扱うことができました。その結果、それまでに積み上げてきたクエリ候補を無駄にすることなく強化してスコアを伸ばして行くことが出来ました。

今回のコンペで学んだ知見を今後業務や次のコンペに活かして行きます。