エムスリーテックブログ

エムスリー(m3)のエンジニア・開発メンバーによる技術ブログです

分散密ベクトル探索エンジンValdとSentence-BERTを使った類似文書検索を試す

python 機械学習 情報検索

エムスリーエンジニアリンググループ AI・機械学習チームでソフトウェアエンジニアをしている中村(@po3rin) です。 好きな言語はGo。仕事では主に検索周りを担当しています。

Overview

最近、社内で情報検索論文輪読会を立ち上げました。

情報検索論文読み会のスケジュール

そこでNGT-ONNGについての論文*1を紹介したところ1時間の予定のところを盛り上がりすぎて2時間超えてしまいました。

大盛り上がりのついでに、今回は情報検索論文輪読会で紹介した近似最近傍探索ライブラリNGTを内部で利用するValdを使って、類似文書検索がどのように出来るのか、現状の問題を解決できるのかを試したのでその結果を報告します。

弊社が抱える類似文書検索の課題

医師に質問ができるサービスであるAskDoctorsではユーザーが質問を検索できる機能があり、現状、似た質問を出す機能はElaticsearchのMore Like Thisのような単語頻度ベースの類似文書検索を利用しています。クエリとして入力されたドキュメントから頻出単語を抜き出し、それを使って文書検索します。これは「似た文書は同じ単語をもつ可能性が高い」という仮定に基づいた手法です。

しかし医療言語は表現揺れが大きく、単語頻度ベースだと類似文書を出せない可能性があります。例えば

  • 「胸が違和感」と表現する人もいれば「胸がムカムカ」と表現する人もいるので関連度が高いのに単語ベースだとスコアが下がってしまう類似文書が出てくる

  • 「妊娠30日」「生後12日」「39度の熱」など表現では多くの数値表現が出てくる。単語頻度ベースでは数字だけがトークンとして抽出されてしまうので、何とひもづく数値なのかを文脈で理解する必要がある

  • 「熱はないが、頭が痛い」など「熱」と「ない」の関係、または否定形を含んだ類似文書検索をしないとユーザーの意図と違う文書を出してしまう

このような医療自然言語に関する課題の話は医療言語処理という本が面白いので興味のある人は読んでみることをお勧めします。

医療言語処理 (自然言語処理シリーズ)

医療言語処理 (自然言語処理シリーズ)

Amazon

これらの問題を解決するために、文脈を考慮した文書ベクトルを利用した類似度計算が1つの解決策として考えられます。そこで今回はSentence BERTで質問のタイトルから文章ベクトルを生成し、Valdを使ってベクトル検索をすることで、この問題を突破できるかを試します。

また、今年の2月に私が書いた記事ではこれらの問題の別解としてGiNZAと患者表現辞書を使った意味構造検索を試した記事もあるので読んでみてください。

www.m3tech.blog

Sentence-BERT

Sentence BERT*2は文章の組み合わせに対して、それらが似ているか否かのラベルをつけて入力とし、BERT層、pooling層を距離学習でfine-tuneしたモデルです。

論文では評価関数、pooling手法の2つを変えて実験しています。評価関数はSoftmax、Cosine Similarityの2つで実験しています。pooling層はmean pooling、max poolingが提案されています。論文から引用した図がわかりやすいです。

Sentence-BERTのアーキテクチャ

pooling手法については、論文の実験では単語ベクトルの平均を使った手法がBERTのCLSベクトルを利用する手法よりも精度が高かったようです。

今回は検証のため、学習済みモデルは以下の記事で公開されているものを使用しました。

qiita.com

記事内では学習方法について明言がされていないため、埋め込み空間の精度への影響については今回見ていませんが、改善の余地はありそうです。

Valdを使った近似最近傍探索

Sentence-BERTで生成した文書ベクトルを使ってCosine Similarityを計算し、類似文書を決定するのですが、全てのベクトルに対して線形に探索するとパフォーマンス的に問題があります。そのため、ベクトル検索を実践投入するためには近似最近傍探索が選択肢に上がります。

そこで今回は前々から気になっていたNGTとそれをスケーラブルな分散ベクトル検索エンジンとして使えるように実装されたValdを試してみました。

NGT

NGTのロゴ

Valdの中で利用されているNGTという近似最近傍探索ライブラリから紹介します。NGTライブラリでは利用できるアルゴリズムに種類があり、特にツリー構造による探索起点決定、グラフのエッジ調整、パス調整を行うNGT-ONNGはANN Benchmark *3でトップクラスの性能を叩き出しています。

https://github.com/yahoojapan/NGT

github.com

NGT-ONNGの調整ロジックは非常に面白いので論文 *4、もしくは下記のアルゴリズム開発者のNGT日本語解説記事をご覧ください。

techblog.yahoo.co.jp

Vald

Valdのロゴ

NGTを内部で利用するスケーラブルな分散型ベクトル検索エンジンとして登場したのがValdです。Valdの利点としてKubernetes friendlyな点があげられます。Helmが公式から提供されており、簡単にKubernetesにデプロイしてスケーラブルな分散型ベクトル検索エンジンがセットアップできます。個人的にGoで書かれているのも好みです。

一方で先ほど紹介したNGT-ONNGなどのグラフ再構築する系のアルゴリズムでは動的な更新、削除ができないので、ValdではNGT-ANNG*5が利用されています。

github.com

Vald×Sententce-BERTで類似文書検索

今回のアーキテクチャ

今回の検証では、Askdoctorsの直近の質問データ約3万件で、タイトルだけの埋め込みを利用してValdで検索した結果を定性的にみてみます。

検証環境は下記になります。

Vald = "v1.1.0"
Python = "v3.9"

# 主な Python modules
torch = "^1.8.1"
vald-client-python = "^1.0.4"
transformers = "^4.5.1"

Valdのセットアップ

Valdのセットアップに関してはドキュメントがあるのでそちらを参考にセットアップすると良いでしょう。

github.com

ベクトルサイズだけ設定し直す必要があります。example/helm/values-scylla.yamlもしくはexample/helm/values-standalone-agent-ngt.yamlのagent.ngt.dimensionを修正します。

また、今回は文書類似検索の定番のCosine Similarityを指定します。ドキュメントのQuick StartではデフォルトでL2なので注意してください。

agent:
  # ...
  ngt:
    # The number of dimensions for feature vector of fashion-mnist dataset.
    dimension: 768
    distance_type: cosine
    # ...

どんな結果になるかだけ試したい場合はVald全体ではなくNGT AgentだけをDockerで立ち上げるのも良いでしょう。

k8sへ接続できることを確認したら、早速Helmでデプロイします。

$ helm install vald vald/vald --values example/helm/values-scylla.yaml

これでValdの準備ができました。

データ準備

データはlistで用意します。

titles = ["新型コロナワクチン予防接種について", "胃ガンの手術", ...]

Sentence-BERTで文書ベクトル生成

学習済みSentence-BERTのモデルを読み込んで。

実装は下記の本を大いに参考にしておりますのでBERTモデルのセットアップなど詳しい解説は下記の本をご覧ください。私のようなソフトウェアエンジニアでもPython×PyTorchで自然言語処理の基本が学べる素晴らしい本なのでお勧めです。

PyTorch自然言語処理プログラミング word2vec/LSTM/seq2seq/BERTで日本語テキスト解析! (impress top gearシリーズ)

PyTorch自然言語処理プログラミング word2vec/LSTM/seq2seq/BERTで日本語テキスト解析! (impress top gearシリーズ)

Amazon

文書ベクトルを得るためのコードを書きます。

from transformers import BertJapaneseTokenizer
from transformers.models.bert_japanese import tokenization_bert_japanese
from transformers import BertModel, BertConfig
import torch
from torch.nn.utils.rnn import pad_sequence

tknz = BertJapaneseTokenizer(vocab_file="resources/sentence-bert/vocab.txt", do_lower_case=False, do_basic_tokenize=False)
tknz.word_tokenizer = tokenization_bert_japanese.MecabTokenizer()

config = BertConfig.from_json_file("resources/sentence-bert/config.json")
net = BertModel.from_pretrained("resources/sentence-bert/pytorch_model.bin", config=config)


def mean_pooling(model_output, attention_mask):
    token_embeddings = model_output[0]
    input_mask_expanded = attention_mask.unsqueeze(-1).expand(token_embeddings.size()).float()
    sum_embeddings = torch.sum(token_embeddings * input_mask_expanded, 1)
    sum_mask = torch.clamp(input_mask_expanded.sum(1), min=1e-9)
    return sum_embeddings / sum_mask


def embeddings(titles):
    xs1, xmsk = [], []
    for i in range(len(titles)):
        tid = tknz.encode(titles[i])
        xs1.append(torch.LongTensor(tid))
        xmsk.append(torch.LongTensor([1] * len(tid)))
    xs1 = pad_sequence(xs1, batch_first=True)
    xmsk = pad_sequence(xmsk, batch_first=True)

    out = net(xs1,xmsk)
    return mean_pooling(out, xmsk)

Valdでベクトルをインデックス&検索する

続いてValdにベクトルをInsertしていきます。ValdのインターフェースはgRPCで提供されています。Pythonでは公式クライアントライブラリであるvald-client-pythonが提供されているのでそれを使います。この他にもGoやJavaなどのクライアントも公式から提供されています。

pypi.org

import grpc
from vald.v1.vald import insert_pb2_grpc, search_pb2_grpc, update_pb2_grpc, remove_pb2_grpc
from vald.v1.payload import payload_pb2

channel = grpc.insecure_channel("127.0.0.1:8081")
istub = insert_pb2_grpc.InsertStub(channel)

icfg = payload_pb2.Insert.Config(skip_strict_exist_check=True)
doc_id = d

ts = embeddings(titles)
for i, t in enumerate(ts):
    vec = payload_pb2.Object.Vector(id=str(i), vector=s)
    istub.Insert(payload_pb2.Insert.Request(vector=vec, config=icfg))
    doc_id+=1

次にクエリを用意します。クエリは単語ベースのMore Like Thisで難しいと思われるクエリを独断と偏見で用意しました。

queries = [
    '三日間の腹痛', #数値表現
    '胃ガンの手術', #胃ガンのシノニムを捉えれるか
    '胸がずっと筋肉痛', #ずっとという期間を表す表現
    '生後6ヶ月の乳児の誤飲', #数値表現と誤飲という少し珍しい表現
    '熱はないが頭が痛い', #否定表現
]

最後にいよいよValdに検索をかけるコードを書いていきます。

qs = embeddings(queries)
scfg = payload_pb2.Search.Config(num=5, radius=-1.0, epsilon=0.3, timeout=3000000000)

for i, s in enumerate(qs):
  res = sstub.Search(payload_pb2.Search.Request(vector=s, config=scfg))
  print("---------")
  print(f"query: { queries[i] }")
  for r in enumerate(res.results):
    print(f"title: { titles[int(r[1].id)] }")

payload_pb2.Search.Configに何やらパラメータを渡しています。NGTは探索範囲となる円の半径を狭めながら検索するアルゴリズムなので、探索半径を決定するパラメータを決めてあげる必要があります。

radiusは初期探索半径であり、-1はこちらのANNGの論文で言及がある通り無限大を指定しているものだと思われます。これにより必ず初期半径内に探索対象が存在することが保証されるので、最近傍探索は1回だけで十分になります。https://github.com/yahoojapan/NGT/wiki#annghttps://github.com/yahoojapan/NGT/wiki#anng

epsilonは範囲内のノードの探索において、最近傍のノードへの経路が範囲外を経由しないと到達できない場合を想定して設定するパラメータです。つまりepsilonを高く設定することで再現率が向上しますが、考慮しなければいけないノードが増えるので計算コストが増えてしまいます。ANNGの論文ではepsilonに対する検索精度を50次元のベクトルで速度を計測したグラフが示されています。

これで実装は終了です。

結果を確認

実行して結果を1つずつ見ていきます。

query: 三日間の腹痛

title: ３時間を超える腹痛
title: 胸痛が三日続いています
title: 3週間以上続く体調不良
title: 3日前から腹痛
title: 『腹痛』4日前から3日ほど強い痛みが続きました

数値表現と数値表現がある程度紐付けられていますが、「3週間」などの表現も入ってしまっています。

query: 胃ガンの手術

title: 胃がんの手術について
title: 胃ろう手術後の痛み
title: 胃癌の原因
title: 胃の粘膜下腫瘍について
title: 胃体部に異常があるとの事

胃ガン/胃がん/胃癌の表記ゆれを捉えています。その中でも注目すべきは「胃の粘膜下腫瘍」などの表現を捉えているのが嬉しいです。胃ろうは全く違うのでこれはノイズです。

query: 胸がずっと筋肉痛

title: 胸骨部がとても痛い。
title: 体を捻ると胸が痛む
title: 胸の痛みと激しい動悸
title: ずっと続いている胸痛
title: 胸が痛みます

筋肉痛が痛みであることを意味として捉えていることが分かります。「ずっと」という時間範囲を伴う表現はあまり理解できていないようです。

query: 生後6ヶ月の乳児の誤飲

title: 6ヶ月赤ちゃん、嘔吐
title: 生後6ヶ月半の嘔吐
title: 6ヶ月の赤ちゃん、顔をぶつけて鼻血？がでました。
title: ８ヶ月の乳児、６時間ほど前に嘔吐し、４時間ほど前に頭をぶつけました。
title: ６歳の子供のひどい虫歯

生後6ヶ月の前後の範囲に合わせて赤ちゃん、乳児などの表現をおさえていますが「誤飲」が上手く捉えられていません。今回用意したデータでは「生後７ヶ月息子の誤飲の可能性」というような関連記事が存在しているので、この結果は良くないですね。

query: 熱はないが頭が痛い

title: 多少の息苦しさ 熱なし 咳なし
title: 体温は平熱だけど、頭が熱っぽい
title: 頭痛がひどく味覚がおかしい熱はない
title: 体が熱っぽく、ちょっとだるい
title: 熱も咳もないですが各所に違和感や鈍痛があります

正しい否定表現が取れています。これはかなり嬉しいです。

まとめると、完璧に症状が一致している類似文書が取れている訳ではありませんが、医療言語処理の課題をある程度突破して、意味の近い文書が取得できています。

誤飲などの珍しい単語の場合は、単語頻度ベースの手法の方がその単語が入っている文書が確実に取得できる可能性のある一方、意味を捉えなければ意味理解が難しい文章構造の場合はこのような文書ベクトルを使った手法の方が向いていると思われます。

自分らのアプリケーションではどのような入力がされるのかを考慮して、使う手法を決めるべきでしょう。

Vald Agentのパラメータを変えて試す。

epsilonを0.1くらいに下げると精度が下がり否定形を取れなくなっている。

query: 熱はないが頭が痛い

title: 咳と微熱
title: 微熱と咳が続く
title: 微熱と倦怠感があります
title: 微熱と倦怠感が続いています。
title: 微熱が続く

これは前の節で述べたように、探索半径外の探索もある程度許容するという選択肢を狭めたゆえに精度が下がった結果と言えます。

また radiusを0.3くらいに下げると、最初の探索範囲が極端に狭くなり、top-kが取得できなくなる場合があることがわかりました。

query: 熱はないが頭が痛い

// 結果なし

よって探索半径のパラメータはベクトルの特性によって調節する必要があります。

おまけ: Elasticsearchの近似最近傍探索の現状

今回Valdを調査した１つの理由として、弊社で利用しているElasticserchにはまだ近似最近傍探索が実装されていないという点もありました。

しかし、AWSなど(この辺バチバチなのであまり言及できませんが...)で利用されているOpen Distro for Elasticsearchでは、Hierarchical Navigable Small world(HNSW)グラフ*6を利用するNMSLIBをベースにした機能が提供されているようです。

arxiv.org

HNSWはNGTが利用するアルゴリズムとはまた違い、マルチレイヤー構造を持つグラフを利用することで速度と精度を両立した手法です。

残念ながら弊社では現在Elastic Cloudを利用しているのでこのHNSWは利用できません。しかし時期メジャーバージョンのLucene v9.0.0ではHNSWが実装されるようです!

[LUCENE-9004] Approximate nearest vector search - ASF JIRA

実装を覗くとまだ1階層しかサポートしていませんが、いつの日かElasticsearchの公式機能として利用できると嬉しいです。日本語のLuceneにHNSW入るよ記事はこちらが詳しいです。

https://mocobeta.medium.com/%E3%83%99%E3%82%AF%E3%83%88%E3%83%AB%E6%A4%9C%E7%B4%A2-%E8%BF%91%E4%BC%BC%E6%9C%80%E8%BF%91%E5%82%8D%E6%8E%A2%E7%B4%A2-%E3%81%A7%E3%81%84%E3%81%84%E6%84%9F%E3%81%98%E3%81%AE-morelikethis-%E3%82%92%E5%AE%9F%E7%8F%BE%E3%81%99%E3%82%8B-7eba63ffb593mocobeta.medium.com

まとめ

今回はSentence-BERT × Valdで類似文書検索を試しました。完璧とは行かないまでもある程度は文章の意味を理解した結果が返せることがわかりました。特に「熱はないが頭が痛い」などの否定形を含む文章でも意味を理解して結果を返せることが確認できました。

ValdはHelmが用意されておりデプロイも簡単に行える且つ、各種言語でクライアントライブラリが提供されているため、すぐに分散密ベクトル検索エンジンが利用できるのがメリットだと感じました。もし類似文書検索以外でも近似最近傍探索をやる際にはValdは十分検討対象になりそうです。その際には想定される本番データサイズと次元でパフォーマンステストを行いたいと思います。

また、今回はValdのアーキテクチャに踏み込めなかったので次回調べる機会があればまたブログで書こうと思います！

We're hiring !!!

エムスリーでは検索&推薦基盤の開発&改善を通して医療を前進させるエンジニアを募集しています！ 社内では情報検索論文輪読会が発足し、日々検索や推薦についての議論が活発に行われています。

「ちょっと話を聞いてみたいかも」という人はこちらから！ jobs.m3.com

*1: Optimization of Indexing Based on k-Nearest Neighbor Graph for Proximity Search in High-dimensional Data (https://arxiv.org/abs/1810.07355)

*2:Sentence-BERT: Sentence Embeddings using Siamese BERT-Networks (https://arxiv.org/abs/1908.10084)

*3: ANN Benchmark (https://github.com/erikbern/ann-benchmarks)

*4: Optimization of Indexing Based on k-Nearest Neighbor Graph for Proximity Search in High-dimensional Data (https://arxiv.org/abs/1810.07355)

*5: NGT-ANNG (https://github.com/yahoojapan/NGT#anng)

*6: Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs (https://arxiv.org/abs/1603.09320)