直感的な検索を目指して（『ベクトル検索実践入門』を執筆しました）

こんにちは。LINEヤフー株式会社で検索エンジン開発のマネジメントを行っている真鍋です。検索のなかでも、今回はベクトル検索についてお話しします。ベクトル検索は、LINEヤフーでも検索や広告配信、レコメンドなどの領域で日々活用されています。

わかりやすい説明のために、まず検索の具体例を挙げます。たとえばユーザーが家電量販店の通販サイトを訪れ、「ディスプレイ」について検索したとします。このとき「ディスプレイ」をクエリ、検索の対象とする家電それぞれをドキュメントと呼びます。このとき、ほぼクエリそのままの「液晶ディスプレイ」という名前のドキュメントがあれば、ユーザーに見てもらったほうがよいと言えるでしょう。また、「有機ELテレビ」はクエリと共通の単語を含みませんが、このテレビがディスプレイとしても使えるものであれば、これも表示したほうが良さそうです。

一方、「6ドア冷蔵庫」はクエリと関連がなさそうなので、あまり表示しなくてもよいと言えるでしょう。また、「テレビリモコン」は名前に「テレビ」を含んでいますがテレビそのものではないので、これも表示しなくても良さそうです。

このとき、検索結果の最上位には「液晶ディスプレイ」を、続けて「有機ELテレビ」を並べれば、直感的な検索結果になるといえます。

ベクトル検索の基本的なアイデア

以上の例のように、直感的な検索のためには、実は各種の一般的な知識を処理する必要があります。たとえば多くのテレビはディスプレイとしても使えることや、テレビリモコンはテレビそのものではないことです。ベクトル検索では、クエリやドキュメントをベクトルで扱うことで、直感的な検索を可能にします。

ベクトルとは実数の配列です。ベクトル検索では、まずドキュメントをそれぞれベクトルに変換（ベクトル化）します。ドキュメントは通常、人間が使う言語で書かれているので、それを理解するための「言語モデル」によってベクトル化します。高度な言語モデルを使えば、一般的な知識も処理できます。最近ではコンピューターと人間が自然に対話できるようになっていますが、あれも言語モデルの高度化によるものです。ベクトル検索に応用すれば、たとえば「液晶ディスプレイ」と「有機ELテレビ」を似たベクトルに、「有機ELテレビ」と「テレビリモコン」を大きく異なるベクトルに、それぞれ変換できるということです。

$\begin{matrix*}[r] \text{液晶ディスプレイ} & \mapsto & \mathbf{v}_\text{液晶ディスプレイ} & = & [ & -0.076 & 0.058 & \cdots & 0.027 & 0.034 & ] \\ \text{有機ELテレビ} & \mapsto & \mathbf{v}_\text{有機ELテレビ} & = & [ & -0.030 & 0.033 & \cdots & 0.038 & 0.005 & ] \\ \text{6ドア冷蔵庫} & \mapsto & \mathbf{v}_\text{6ドア冷蔵庫} & = & [ & -0.001 & 0.079 & \cdots & -0.020 & -0.008 & ] \\ \text{テレビリモコン} & \mapsto & \mathbf{v}_\text{テレビリモコン} & = & [ & -0.103 & 0.030 & \cdots & 0.013 & 0.012 & ] \\ \end{matrix*}$

ベクトル検索では、ユーザーからクエリを受け取ったら、それもベクトル化します。そして、各ドキュメントベクトルとクエリベクトルとの間で簡単な計算をして、各ドキュメントにスコアをつけます。たとえば対応する要素の積の総和を計算します。この計算をドット積と呼びます。

$\begin{matrix*}[r] \text{ディスプレイ} & \mapsto & \mathbf{v}_\text{ディスプレイ} & = & [ & -0.086 & 0.069 & \cdots & 0.025 & 0.043 & ] \\ \end{matrix*}$

$\begin{matrix*}[r] \mathbf{v}_\text{液晶ディスプレイ} & \cdot & \mathbf{v}_\text{ディスプレイ} & = & -0.076 & \times & -0.086 & + \\ & & & & 0.058 & \times & 0.069 & + \\ & & & & & \vdots \\ & & & & 0.027 & \times & 0.025 & + \\ & & & & 0.034 & \times & 0.043 \\ & & & \fallingdotseq & 0.933 \\ \end{matrix*}$

$\begin{matrix*}[r] \mathbf{v}_\text{有機ELテレビ} & \cdot & \mathbf{v}_\text{ディスプレイ} & \fallingdotseq & 0.602 \\ \mathbf{v}_\text{6ドア冷蔵庫} & \cdot & \mathbf{v}_\text{ディスプレイ} & \fallingdotseq & 0.430 \\ \mathbf{v}_\text{テレビリモコン} & \cdot & \mathbf{v}_\text{ディスプレイ} & \fallingdotseq & 0.571 \\ \end{matrix*}$

あとはスコアが高いドキュメントを優先してユーザーに返せば、直感的な検索結果になります。言い換えればベクトル検索とは、そうなるようにドキュメントやクエリをベクトル化する技術です。

LSH: ベクトル検索の改善の例

ベクトル検索の基本的なアイデアは以上のようにシンプルですが、実装のために考慮すべき事柄は多くあります。たとえば言語モデルの選択と微調整が必要ですし、大きなベクトルの入出力にはコストがかかります。この記事ではベクトルの圧縮について、LSHという面白い手法を簡単に紹介します。

まず線形変換について説明します。ベクトル検索の流れ全体を通して非常によく使う、基本的な変換です。線形変換は、ベクトルを入力にとり、別の複数のベクトルとのドット積を書き並べた新たなベクトルを出力します。線形変換によってベクトルの長さも変換でき、より短いベクトルに変換すればベクトルの圧縮になります。まず面白いポイントとしては、このとき「別の複数のベクトル」を乱数に基づいて生成しても、スコアの大小関係がいくらか保存される場合があります。要はランダムな計算に基づいてベクトルを圧縮できる場合があるということです。

$\begin{matrix*}[r] \mathbf{v}_\text{液晶ディスプレイ} & \mapsto & \mathbf{w}_\text{液晶ディスプレイ} & = & [ & -0.010 & 0.006 & 0.070 & -0.011 & ] \\ \mathbf{v}_\text{有機ELテレビ} & \mapsto & \mathbf{w}_\text{有機ELテレビ} & = & [ & 0.018 & 0.045 & 0.029 & -0.082 & ] \\ \mathbf{v}_\text{6ドア冷蔵庫} & \mapsto & \mathbf{w}_\text{6ドア冷蔵庫} & = & [ & 0.046 & 0.006 & 0.025 & 0.012 & ] \\ \mathbf{v}_\text{テレビリモコン} & \mapsto & \mathbf{w}_\text{テレビリモコン} & = & [ & 0.056 & -0.057 & 0.001 & -0.057 & ] \\ \end{matrix*}$

$\begin{matrix*}[r] \mathbf{v}_\text{ディスプレイ} & \mapsto & \mathbf{w}_\text{ディスプレイ} & = & [ & -0.021 & 0.036 & 0.062 & -0.022 & ] \\ \end{matrix*}$

$\begin{matrix*}[r] \mathbf{w}_\text{液晶ディスプレイ} & \cdot & \mathbf{w}_\text{ディスプレイ} & \fallingdotseq & 0.0050 \\ \mathbf{w}_\text{有機ELテレビ} & \cdot & \mathbf{w}_\text{ディスプレイ} & \fallingdotseq & 0.0048 \\ \mathbf{w}_\text{6ドア冷蔵庫} & \cdot & \mathbf{w}_\text{ディスプレイ} & \fallingdotseq & 0.0005 \\ \mathbf{w}_\text{テレビリモコン} & \cdot & \mathbf{w}_\text{ディスプレイ} & \fallingdotseq & -0.0019 \\ \end{matrix*}$

さらに面白いポイントとして、線形変換のあとベクトルの各要素の符号だけを取り出しても、まだスコアの大小関係が確率的に保存されます。たとえば負数なら $-1$、非負数なら $1$ に丸めてしまうということです。これはLSH（Locality Sensitive Hashing、局所性鋭敏型ハッシュ）の一手法です。もとのベクトルの要素が32ビットだとすると、符号は1ビットなので、32分の1という大幅なベクトルの圧縮になります。

$\begin{matrix*}[r] \mathbf{w}_\text{液晶ディスプレイ} & \mapsto & \mathbf{x}_\text{液晶ディスプレイ} & = & [ & -1 & 1 & {\color{transparent}-}1 & -1 & ] \\ \mathbf{w}_\text{有機ELテレビ} & \mapsto & \mathbf{x}_\text{有機ELテレビ} & = & [ & 1 & 1 & 1 & -1 & ] \\ \mathbf{w}_\text{6ドア冷蔵庫} & \mapsto & \mathbf{x}_\text{6ドア冷蔵庫} & = & [ & 1 & 1 & 1 & 1 & ] \\ \mathbf{w}_\text{テレビリモコン} & \mapsto & \mathbf{x}_\text{テレビリモコン} & = & [ & 1 & -1 & 1 & -1 & ] \\ \end{matrix*}$

$\begin{matrix*}[r] \mathbf{w}_\text{ディスプレイ} & \mapsto & \mathbf{x}_\text{ディスプレイ} & = & [ & -1 & {\color{transparent}-}1 & {\color{transparent}-}1 & -1 & ] \\ \end{matrix*}$

$\begin{matrix*}[r] \mathbf{x}_\text{液晶ディスプレイ} & \cdot & \mathbf{x}_\text{ディスプレイ} & = & 4 \\ \mathbf{x}_\text{有機ELテレビ} & \cdot & \mathbf{x}_\text{ディスプレイ} & = & 2 \\ \mathbf{x}_\text{6ドア冷蔵庫} & \cdot & \mathbf{x}_\text{ディスプレイ} & = & 0 \\ \mathbf{x}_\text{テレビリモコン} & \cdot & \mathbf{x}_\text{ディスプレイ} & = & 0 \\ \end{matrix*}$

このようにベクトル検索には、実装上もいくらか直感的に扱える面白さもあります。日常生活では「おおざっぱでいいから急いでやる」戦略が有効なこともありますが、ベクトル検索でも似た戦略がとれるということです。

ベクトル検索の応用

以上、家電量販店の通販サイトにおける検索を例として説明しました。しかしベクトル検索の応用先は本来もっと広く、いわゆる検索にとどまりません。

たとえばベクトル検索は、広告のリアルタイムなCTR（Click-Through Rate、クリック率）予測に応用できます。このためには、クエリとして「ユーザーが使っているデバイス」や「広告を出すページのURL」を使うことが考えられます。またドキュメントは広告、そしてスコアがCTRそのものとなるようにシステムを構成します。他にもベクトル検索は、ユーザーに対するニュース記事の推薦（レコメンド）にも応用できます。この場合は、ユーザーが過去に読んだ記事のベクトルそのものをクエリ、現在ある記事（複数）をドキュメントとして検索することが考えられます。

実際のサービスでは、これらのアイデアをベースとして、より高度な取り組みを行っていきます。

書籍の紹介

さて本題です。ベクトル検索に関する入門的な内容を、書籍として出版していただく機会に恵まれました。もっと詳しく知りたくなった方は、ぜひこちらもご覧いただけるとうれしいです。

真鍋 知博 著

『ベクトル検索実践入門』

（技術評論社発行、ISBN 978-4-297-15337-3）

ベクトル検索実践入門 | 技術評論社

ベクトル検索の実装のために考慮すべき事柄について、広く浅く解説した書籍です。まずベクトル検索の流れを一通り説明し、そのあと各ステップの高度化・高速化について説明しました。また既存の検索システムにベクトル検索を統合したいことも多いと思われるので、そのためのアイデアも紹介しました。そして、ベクトル検索はたとえば画像を扱える点でも優れた技術なので、付録には画像検索について簡単にまとめました。

タイトルに実践とある通り、サンプルコードも多く収録しました。ベクトル検索ライブラリの例としてFaissを、ベクトル検索機能を備えるキーワード検索エンジンの例としてOpenSearchを、それぞれ使用しました。一方、最近流行りの「ベクトルデータベース」として設計されたソフトウェア（たとえばMilvus）は使用しませんでしたが、本書とベクトルデータベースの間でも基本的なアイデアは共通しています。

おわりに

まだベクトル検索に関する和書は少ないので、今回このような書籍を執筆できて、とても光栄でした。本書が直感的な検索を実現する一助となれば幸いです。