TL;DR

機械学習において、近似最近傍探索（Approximate Nearest Neighbor, ANN）やTransformerを使用すると、膨大な候補の中から効率的に適切な結果を取得する必要があります。一方で、すべての候補を愚直に計算すると計算量が膨大になり、リアルタイムでの処理が難しくなります。そこで、本記事は全文検索やANN, Transformerを用いて、大規模な候補から効率的に最適解を選ぶ方法について解説します。

1. 全文検索

1.1. 全文検索とは

全文検索は、テキストデータの中から特定のキーワードやフレーズを検索する手法です。一般的に、データベースや検索エンジンなどで利用され、大量のテキストデータから効率的に情報を取得することができます。全文検索は、以下のような特徴を持ちます：

部分一致検索: キーワードやフレーズの一部を含むデータも検索対象となる
スコアリング: 検索結果にスコアを付与し、関連度の高い順に表示する
形態素解析: 日本語などの多言語に対応し、単語の分かち書きや品詞の解析を行う

有名なフレームワークとしては、ElasticSearchやMeiliSearch、Apache Solr, Apache Luceneなどがあります。

1.2. 全文検索の計算量

検索対象の集合を$A$,検索クエリのトークンの長さを$n$とします。

転置インデックスを使用した場合、検索クエリの計算量は$O(n)$です。

これは、$|A|$個の個数に依存しないため、検索対象が増えても計算量が増加しません。
- ただ、この後にスコアリングを行う場合は、スコアリングの計算量が追加されるため、計算量が増加します。
詳細な資料：

スコアリングの方法については、TF-IDFやBM25などが一般的に使用されます。

詳細な資料：
- 実践で学ぶBM25 - パート2：BM25のアルゴリズムと変数 | Elastic Blog
- Similarity module | Elasticsearch Guide [8.17] | Elastic

2. 近似最近傍探索（ANN）

2.1. 近似最近傍探索とは

近似最近傍探索（Approximate Nearest Neighbor, ANN）は、高次元データ空間において、最も近いデータ点を効率的に見つける手法です。ANNは、高次元データにおいて、全てのデータ点との距離を計算することが困難な場合に有用です。ANNは、以下のような特徴を持ちます：

高次元データ: 高次元データにおいて、最も近いデータ点を効率的に見つける
近似解: 最適解ではなく、近似解を返す
計算量の削減: 全てのデータ点との距離を計算する代わりに、近似的な距離を計算する

有名なフレームワークとしては、AnnoyやFAISSなどがあります。

(最近CassandraなどもANNをサポートするようになってきています。currentslab/awesome-vector-search: Collections of vector search related libraries, service and research papersで様々なライブラリが紹介されています。)

2.2. ANNの計算量

いくつかのデータ構造が提案されています。

局所性鋭敏型ハッシュ - Wikipedia
kd木 - Wikipedia
Hierarchical navigable small world - Wikipedia
ボロノイ図 - Wikipedia

内積の計算を簡略化するために量子化を行ったり、事前にデータをクラスタリングしておくことで、計算量を削減することがされているようです。

現在も絶賛研究中の分野のため完全に理解しきれませんでしたが、結局内積計算を行う必要があるため、何らかのクラスタにおける点の数を$m\leq n$としてベクトルの次元数を$d$とすると、計算量は$O(md)$以上になると考えられます(特に木構造を用いる場合は階層的に計算を行うため、kd-treeの場合は $O(d\log n)$ となる)。

より詳細な資料：
- Yusuke Matsui 近似最近傍探索の最前線 - Speaker Deck
- Arya, Sunil, et al. "An optimal algorithm for approximate nearest neighbor searching fixed dimensions." Journal of the ACM (JACM) 45.6 (1998): 891-923.
- Microsoft PowerPoint - 12-kdtrees.ppt

3. Transformer

3.1. Transformerとは

Transformerは、Vaswani, A. "Attention is all you need." Advances in Neural Information Processing Systems (2017)で提案されたニューラルネットワークモデルです。Transformerは、RNNやLSTMなどの従来のモデルよりも高速に学習が可能であり、長距離の依存関係を学習することができます。Transformerは、以下のような特徴を持ちます：

Self-Attention: 入力系列の各要素間の関係を学習する
Positional Encoding: 入力系列の位置情報を考慮する
Multi-Head Attention: 複数のAttentionヘッドを使用して、異なる表現を学習する
Feed-Forward Network: Attention層の後に位置ごとの全結合層を追加する

PyTorchやTensorFlow, JAXなどのフレームワークで実装されており、自然言語処理や画像処理などの様々なタスクに使用されています。

3.2. Transformerの計算量

TransformerはRadford, Alec. "Improving language understanding by generative pre-training." (2018)などのGPTシリーズにも使われています。

その際に、Chat-GPTなどは次の言葉の予測を行いますがその候補は語彙の数だけあるため、非常に膨大な候補から最適解を選ぶ必要があります。ただ、私達がChatGPTなどの生成AIを利用する際に裏でその計算量が行われているとは考えづらいです。

実際に論文にもある通り、サブワードを使用することで語彙数を削減し、計算量を削減しています。

また、英語以外の言語に対してはSentencePieceなどのトークナイザを使用することで、語彙数を削減する工夫がされています（SetencePieceがChatGPTなどで使われているかは不明ですが）。

より詳細な資料：
- Sennrich, Rico. "Neural machine translation of rare words with subword units." arXiv preprint arXiv:1508.07909 (2015)
- Kudo, T. "Sentencepiece: A simple and language independent subword tokenizer and detokenizer for neural text processing." arXiv preprint arXiv:1808.06226 (2018)

4. まとめ

膨大な候補から最適解を選ぶ方法について、全文検索、近似最近傍探索（ANN）、Transformerについて解説しました。

5. 感想

どれも深堀すればするほど、面白いアルゴリズムであると感じました。今回は一つ一つについて詳細な解説はできませんでしたが、どのような工夫がなされてきたかの大枠を知ることができました。今後も機会があれば、より深く理解していきたいと思います。