この記事は 株式会社うるる（ULURU）Advent Calendar 2023 の23日目の記事です。
一日遅れてしまいました・・・
私の担当するNJSSというシステムでは、入札情報の検索サービスを提供しています。
このような検索サービスでは、特定の情報と類似した情報を検索したいケースがあります。
例えば、NJSSでは入札情報の詳細画面において、その入札案件と似たような案件を表示し、お薦めしています。そうすることでNJSSの利用者は、類似案件から自社に必要とする案件情報を得ることができます。
その他にもそのユーザーの過去の閲覧履歴等の情報から、それらに類似する情報をおすすめするなど、リコメンデーションに利用することもできます。
上記のようなニーズに対応するため、NJSSの利用しているAmazon OpenSearch Serviceという検索サービスでは以下の２通りの方法が提供されています。
More like this query
現在のNJSSでも利用されている方式です。
tf-idf(Term Frequency-Inverse Document Frequency)と呼ばれる文章中の単語の重要度を評価する仕組みを用いて検索されているようです。
OpenSearchでは、検索対象の文章を形態素解析した結果をインデックスに登録し、全文検索を実現していますが、More like this queryでは文章から分割された単語を出現頻度から重要度などを推定して検索に用いているということのようです。
（私も詳しいところはよくわかってませんが、こちらの記事が参考になりそうです）
実際の利用方法については、Elasticsearchのこちらのドキュメントをご覧ください。
K 最近傍 (k-NN) 検索
More like this queryは、SolrやElascitcsearchを含め比較的昔から存在する手法だと思われますが、近年はk-NN検索と呼ばれるベクトル検索の仕組みが実装されています。
文章や画像などの情報をベクトル表現に変換し、複数のベクトル間の類似度をユーグリッド距離やコサイン類似度を使って計測することで、類似検索を実現しているようです。
https://pages.awscloud.com/rs/112-TZM-766/images/20231005-Analytics-03-AWS.pdf
大量データにおいて、上記のような類似度の計測と検索を高速に行うためにOpenSearchやElasticSearchではApproximate k-NN検索(近似最近傍探索)と呼ばれる手法が用いられています。
k-NN検索の利点
More like this queryではなく、k-NN検索を利用するとどのようなメリットがあるのでしょうか？
実際にNJSSに登録されている入札情報で両者の検索を行ってみた結果を比較してみます。
類似検索の比較元の入札情報
比較元となる入札案件はこちらです。
| 案件名称 | 機関名 | 都道府県 |
|---|---|---|
| トラック等借り上げ | 森林研究・整備機構 | 茨城県 |
今回の検索では、入札案件の名称とそれを発注する機関名と都道府県の情報を対象として、類似した入札情報を検索することとします。
More like this queryでの検索結果
More like this queryでの実行結果（上位１０件のみ）は以下の通りです
比較元の案件名に含まれる"トラック"という単語に関連した案件が選ばれているようです。
一部、陸上競技のトラックに関連した案件も含まれています。
また、トラックという単語は含まれているもの、業務としては"借り上げ"関連ではないものも検索されています。
| 案件名 | 機関名 | 都道府県 |
|---|---|---|
| トラックの修理等 | 防衛省(MOD) 防衛装備庁 航空装備研究所 | 東京都 |
| 器材等の診断整備(ハンドパレットトラック等) | 防衛省(MOD) 陸上自衛隊 富士学校 | 静岡県 |
| 北海道上川合同庁舎構内等除排雪業務(ダンプトラック) | 北海道庁 上川総合振興局 | 北海道 |
| 水門等水位観測員講習会会場借り上げ | 国土交通省(MLIT) 東北地方整備局 酒田河川国道事務所 | 山形県 |
| 競技施設等整備工事(上尾運動公園陸上競技場トラック等修繕工) | 埼玉県庁 | 埼玉県 |
| 揚塔作業にかかるトラッククレーン等による荷役作業(後期) | 防衛省(MOD) 海上自衛隊 厚木航空基地隊 | 神奈川県 |
| 【特活】野球部用消耗品購入(トラックマット等)【054001970028101】 | 茨城県庁 | 茨城県 |
| 管理備品)ブックトラック | 加賀市役所 | 石川県 |
| 除雪トラックの売払 | 山形県庁 | 山形県 |
k-NN検索での検索結果
k-nn検索での結果は以下の通りです。
"トラック"という単語が含まれていなくても、車関連全般の案件が選ばれています。
また、業務としては"借り上げ"とほぼ同じ意味の"賃貸借"の案件も多く選ばれているようです。
| 案件名 | 機関名 | 都道府県 |
|---|---|---|
| 車両借上 | 防衛省(MOD) 防衛装備庁 航空装備研究所 | 国外 |
| 公用車の賃貸借 | 防災科学技術研究所(NIED) | 茨城県 |
| バス借上 | 防衛省(MOD) 防衛大学校 | 神奈川県 |
| バス借上 | 防衛省(MOD) 防衛大学校 | 神奈川県 |
| 車両借上 | 防衛省(MOD) 防衛装備庁 次世代装備研究所 | 東京都 |
| 公用車の賃貸借 | 新エネルギー・産業技術総合開発機構(NEDO) | 神奈川県 |
| 公用車の賃貸借 | 新エネルギー・産業技術総合開発機構(NEDO) | 神奈川県 |
| レンタカーの借上 | 防衛省(MOD) 情報本部 | 東京都 |
| 家畜防疫業務に係るトラックの借上げ | 千葉県庁 | 千葉県 |
両者の比較
More like this queryはその仕組みからも推察されるとおり、文章に含まれる特徴的な単語が含まれる案件を検索しています。
しかしながら、トラックの借り上げとトラックの購入や修理の案件のは、単語としては近くても業務としての意味合いが異なるため、入札業務を担当される方からすると類似しているとは言えないかもしれません。
一方でk-NN検索では同じ単語が含まれていなくても、意味合いが近いものを検索します。
"トラックの借り上げ"を担当する会社は、乗用車のその他の種類の車のリースなどを行うケースもありそうです。
ケースバイケースではありますが、文章の意味合いまで考慮されることで、検索の正確性や利便性があがることが期待できそうです。
k-NN検索における検討ポイント
k-NN検索を検証するにあたり、検討が必要となったポイントをいくつか紹介します。
ベクトル化のやり方
k-NN検索を行うには、文章のベクトル表現を取得する必要があります。
OpenSearchでは、機械学習のモデルをアップロードする仕組みを提供しており、それを使ってインデックスを登録することができるようです。
参考: Using ML models within OpenSearch
また、OpenAI社が提供するAPIを利用することもできます。Embeddingsと呼ばれるAPIに文章を送ると、そのベクトル表現が取得できます。
今回はこちらのやり方を採用しています。
その他にもWord2VecやfastTextなど、いろいろ手法があるようです。
参考: OpenAI の Embeddings API はイケてるのか、定量的に調べてみる
k-NN検索のエンジンの選択
k-NN検索のエンジンの実装が複数あり、OpenSearchでは以下３つから選択できます
- faiss
- nmslib
- Lucene
検索性能や他の項目と組み合わせた検索における制約などいくつかの違いがあるようです。
今回は、他の項目と組み合わせた検索が必要であり、"Efficient k-NN filtering"をサポートしているfaissを選択しています。
参考: k-NN search with filters
メモリ消費
k-NN検索は非常に多くのメモリを消費するようです。
実際に試してみたところ、100万件程度の入札情報でも数十GBのJVMのヒープが必要となりました。
より多くのデータを検索できるようにするには、メモリ消費を抑えるための工夫が必要となりそうです。
こちらのページでいくつかの手法が紹介されており、これから我々も試してみる予定です。
OpenSearch における 10 億規模のユースケースに適した k-NN アルゴリズムの選定
おわりに
k-NN検索やベクトル検索と呼ばれるような領域は、比較的新しい分野ですが、様々なDBや検索エンジンでも類似の機能がサポートされ始めており、今後広まっていきそうな予感があります。
この機能を使うことで、類似検索やリコメンデーションなどいろいろな用途で比較的大きな改善効果が期待できるように感じています。