近似最近傍探索（ANN）アルゴリズムを理解する

近似最近傍探索（ANN）とは、指定のクエリポイントに非常に近いものの、必ずしも一番近いとは限らないポイントをデータセットから見つけるアルゴリズムです。NNアルゴリズムは完全に一致するポイントを見つけるために全データを徹底的に検索しますが、ANNアルゴリズムでは十分に近い一致で良しとしています。

これはソリューションとしては悪手のように聞こえますが、実際に高速類似検索を成功させる鍵となっています。ANNはインテリジェントショートカットとデータ構造を活用し、効率的に検索空間をナビゲートします。膨大な時間とリソースを消費する代わりに、ANNではるかに少ない労力で、ほとんどの実際の状況で有用な、十分に近いデータポイントを特定します。

実のところ、これはトレードオフです。完全にマッチするものを見つける必要が絶対にあるなら、速度とパフォーマンスを犠牲にしてNNを使用すればいいのです。しかしほんのわずかの不正確さが許容できるなら、ほぼどんなときでもANNがより良いソリューションです。

ANNの仕組みの最初の段階は次元の削減で、その目的は高次元のデータセットを低次元に変換することです。全データを解析するより、複雑さを抑えたより効率的な予想に基づくモデルタスクの構築を目指します。

アルゴリズムはメトリック空間の数学的概念に立脚したもので、空間内のデータポイントとその間の距離が定義されています。こういった距離は特定の規則（非負性、恒等式、対称性、三角不等式）に従う必要があり、ユークリッド距離やコサイン類似度のような一般的な関数を使用して計算します。

このことをより良く理解するために、借りた別荘を休日になって探していると仮定してみましょう。建物をひとつひとつチェックする（高次元）代わりに地図を使うと、問題を2次元（低次元）に減らすことができます。（ここではわざと例を単純化しています。次元の削減は、効率を改善するためにANNアルゴリズムが採用している唯一の方法ではありません。）

ANNアルゴリズムはまた、効率性の改善にインデックスというデータ構造も活用しています。データをこういったインデックスに前処理するため、ANNは検索空間をはるかに迅速にナビゲートできるのです。これらを道路標識と考えれば、自分が地図のどの地点にいるのかを把握するのに役立ち、休日の別荘により早く到達できます。

急速に進化するデータサイエンスの世界では、効率性が最も重要です。本当に一番近いデータを見つけること（厳密な最近傍探索）には価値がありますが、すでに見てきたように、それには多くの場合計算コストがかかります。そこでANN検索の出番です。超高速と、完璧ではないにせよ高度な正確性という、競争力の高いトレードオフを提供します。

しかし他の検索方法よりもANNを選ぶのは一体どういう場合でしょうか？

厳密な最近傍は低速でしょうが、正確さを最優先する場合や、小さなデータセットを使用する場合には最良の選択となります。k近傍法（kNN）はNNとANNの中間で、高速に結果を出しながらも高い正確性を保ちます。しかしkの値を正しく決定するのは難しく、高次元のデータの扱いはやはりやっかいです。

ANNの速度と効率は、完全ではないもののその高い正確性と合わせて、次のような多くの状況にはまさにぴったりです。

• 大規模なデータセット：数百万、さらに数十億ものデータポイントを扱う場合、厳密なNNではその徹底した性質により応答が遅くなります。ANNは広大なデータ世界のナビゲートに秀でており、迅速に結果を出します。

• 高次元のデータ：次元が上がるほど、厳密なNNの計算量は爆発的に増えます。ANNの次元削減技法は効果的に検索空間を狭め、画像やテキストのような複雑なデータにおいて効率性を高めます。

• リアルタイム用途：すぐに結果が必要ですか？レコメンデーションシステム、不正検知、異常検知は、リアルタイムでのインサイトに依存しています。ANNの高速性は、そういった用途に理想的です。

• 許容できる概算：結果におけるわずかな不正確さを許容できる用途であれば、ANNの高速性は極めて有益です。たとえば画像検索において見た目がよく似た画像を見つけるとき、正確に一番似ているものを見つけるのではないなら、ANNで十分です。

ベクトル検索は密ベクトルとしてエンコードされたデータを扱い、複雑な関連性と埋め込まれた意味を取り出します。ベクトル検索は、従来のキーワードベースの検索ではしばしば水準に達しない、画像、テキスト、ユーザー設定などのコンテンツの検索に最適です。しかしここでもやはり「次元の呪い」が問題となります。つまり次元の次数が上がるとベクトルが増加するため、従来の検索手法では困難で、低速で非効率となります。

ANNは厳密な一致を見つけるよりも、「十分近い」一致の検出に注力するように切り替えて、この問題を解決しています。こうして高速の結果取得が可能になります。ベクトル検索で膨大なデータセットから似たベクトルを瞬時に探し出せるのです。またスケーラビリティ機能も組み込まれているので、速度を犠牲にすることなく、必要なだけデータセットを拡大できます。

リアルタイムでの応答と、関連性と効率性の改善とを組み合わせるとは、多くの場合、ANNがベクトル検索の真の潜在能力を解き放つ際に重要な役割を演じるということを意味します。

ANNのコンセプトは検索速度において圧倒的な利点を持っていますが、ANNという用語は実際には多様なアルゴリズムのツールボックスを含んでいます。そのどれにも長所とトレードオフがあり、具体的なデータと検索のニーズに合った正しいツールを選ぶには、その微妙な差異の理解が重要となります。

KD木は階層的な木構造でデータポイントを整理し、特定の次元に基づいて空間を分割します。こうして低次元空間での高速で効率的な検索と、ユークリッド距離に基づくクエリが可能になります。

KD木は低次元での最近傍の検出に優れていますが、「次元の呪い」も受けています。 これは高次元になるにつれて、ポイント間の空間も爆発的に増加するという現象です。高次元では、単一の軸に基づいて分割するというKD木の戦略は、非効率的になります。検索ではほとんどのデータをチェックするようになり、効率的という長所を失い、全ポイントを通じた単なるリニアスキャンに近づき、速度の低下を招きます。

LSHは強力なANN技法で、データポイントを「ハッシュ化」して、類似の関係性をうまく保ったまま低次元空間に落とし込みます。このクラスタリングにより検出が容易になり、画像やテキストのような膨大で高次元のデータセットの検索を、速度とスケーラビリティを保ったまま行うという点で、LSHが抜きんでた性能を示します。それでいて、しかも程よく正確な「十分近い」一致を返すのです。しかしLSHは時には誤検出（類似していないポイントを類似と検出）する場合があること、その効率性は距離のメトリック（基準）とデータのタイプによって変わることに注意してください。異なるメトリック（ユークリッド距離、Jaccard係数など）で作動するように設計されたさまざまなLSHファミリーがあります。つまりLSHは多用途に使えるということです。

Annoy（Approximate Nearest Neighbors Oh Yeah）は単一のアルゴリズムではなく、オープンソースのC++ライブラリで、LSHやKD木を直接実装せず、木を構築しクエリする独自のアルゴリズムを使用します。高次元空間でメモリー効率を高め高速検索ができるように設計されていて、リアルタイムのクエリに適しています。基本的に使いやすいインターフェースを備えていて、さまざまなデータタイプや検索状況に柔軟に対応できます。Annoyの強みは複数のANNアプローチをひとつにまとめて活用でき、ニーズに最も合ったものを選択できる点にあります。これで処理を簡素化できますが、Annoyで正しい内部アルゴリズムを選択することは性能の最適化にとって極めて重要であり、その効率性はやはりデータや正確性の要件といった要因に依存することに注意してください。

通常はANN技法に分類されないものの、リニアスキャンについても言及する価値があります。これは総当たりアプローチですが、他のANNアルゴリズムと同様の結果を出すからです。これは各データポイントについて、レコード間の距離の計算と最良の一致の記録を連続的に繰り返します。アルゴリズムが実に単純であるという特性により、実装が簡単で、小規模なデータセットには優れています。より初歩的なアプローチとしての欠点は大規模なデータセットには非効率で、高次元のデータに使用すると処理が遅くなり、リアルタイム用途には向きません。

どのANNを選ぶかを決める前に、考慮すべきことがいくつかあります。以下に挙げます。

• データセットのサイズと次元：大規模で高次元なデータには局所性鋭敏型ハッシュの、小規模で低次元なデータにはKD木の使用を考慮します。

• 必要な正確性のレベル：絶対的な正確さが必須なのであれば、リニアスキャンが最良の選択でしょうが、そうでなければ高速で十分正確なLSHやAnnoyを検討します。

• 計算のリソース：Annoyは柔軟性に富んでいますが、その中でアルゴリズムを選択する前にメモリーと処理の制限を考慮してください。

万能のソリューションはないことに注意してください。ご使用の固有データを使って、さまざまなANNアルゴリズムで実験し、その性能を評価して、ご自分のベクトル検索のニーズに完全にマッチするものを選びます。こういった選択肢以外にも、ANNアルゴリズムの世界は常に進化しているので、最新の情報にも注意を払う価値があります。検索を改善できる新しい方法を見逃してはなりません。

膨大で複雑なデータの世界には、その迷路をナビゲートする効率的なツールが求められています。このためANNが、類似検索を「良い」ものから「凄い」ものに変える、秘密のソースになり得るのです。正確性の点でほんの少しの妥協が必要ですが、高速性とスケーラビリティが得られます。現在もその研究は続いていて、毎週開発が進められており、すべてがANN空間のダイナミックな特性に貢献しています。たとえば量子コンピューターや機械学習の発達により、一層高速で効率的な新しいタイプのANNアルゴリズムが生まれるかもしれません。

いろいろなANNアルゴリズムを探求しましたが、それぞれに固有の長所と短所があります。しかし最終的には、最適な選択は具体的なニーズに依存します。データサイズ、次元、正確さの要件、リソースといった要因を考慮してください。正しいアルゴリズムを実験、探求、選択してANNを最大限に活用してください。画像検索から不正検知まで、アルゴリズムが劇的な差異をもたらし、隠れていた接続をあらわにして、データに基づくインサイトを迅速に強化します。

次に曲や映画、ビデオゲームなどを検索する際には、表に出ない物静かなヒーロー、点を繋げて関連性を見出すANNアルゴリズムのことを思い出してください。

準備ができたら、ビジネスのデータから得られるインサイトを活用するための次の4つのステップに進みましょう。

1. 無料トライアルを開始して、Elasticがビジネスにどのように役立つのかを実感してください。

2. ソリューションのツアーで、Elasticsearchプラットフォームの仕組みと、ソリューションがニーズにフィットする仕組みを確認してください。

3. 生成AIを企業に導入する方法を確認してください。

4. 興味を持ってくれそうな人とこの記事を共有してください。メール、LinkedIn、X（旧Twitter）、Facebookで共有しましょう。