【2026年10月版】

索引と探す技術（第8回）― 手法の選び方と意思決定木

公開日: 2026/10/02
読了時間: 約 22分

第7回では、評価関数の作り方を扱った。第8回は、ここまでの手法の選び方を扱う。

1. 評価データに合わせて調整された設定

論文に載る手法の設定と成績は、評価に使ったデータに向けて調整されている。別のデータに移せば、成績は変わる。ここまでの回でも、分野ごとに同じ構図が出てきた。BEIR で BM25 と密ベクトル検索の勝者が入れ替わる例は第3回で、分布外のクエリとニューラル推薦の再現性は第4回で扱った。ここでは、第2回で導入した学習索引と、ニューラルを使う組合せ最適化を詳しく見る。

学習索引の評価からは、結果がデータの分布で変わることが分かる。SOSD を使った評価では、64ビット整数のキーを各2億件持つ4つのデータを使った。osm のデータでは、ほぼどのサイズでも、基数表で範囲を絞ってから二分探索する RBS が、学習索引と従来の索引に並ぶか上回った。局所的な構造に乏しく、モデルが同程度の誤差に達するにはより大きな記憶が要るためである。face のデータには約100個の巨大な外れ値があり、RBS が使う基数表の先頭16ビットがほぼ機能を失って、性能が大きく落ちた。amzn と wiki のデータでは、学習索引が100MB までパレート最適だった。索引の大きさと検索の速さを並べて比べると、100MB までのどの大きさでも、学習索引がその大きさで最も速いか、同じ速さを最も小さい索引で出していた、という意味である。論文は、合成データは驚くほど学習しやすく学習索引に有利になるので、実データで評価したと明記している。

更新を含む場合については、Wongkham らの評価がある。10の実データで、ALEX と LIPP は単一スレッドではデータとワークロードの組み合わせの80%超で従来の索引を上回ったが、設計によっては並行処理で性能が落ちた。メモリは、更新を含む現実的な設定で最大3.2倍削減できた。論文は、データの難しさを指標にし、その難しさを考慮して使うことを勧めている。

ニューラルを使う組合せ最適化にも同じ構図がある。Kool らの注意機構を使う手法は、100都市の巡回セールスマン問題で、Concorde、LKH3、Gurobi の7.76に対し、貪欲に構成した解が8.12(ギャップ4.53%、6秒)、1時間のサンプリングで7.94(2.26%)だった。数値は巡回路の平均の長さで、ギャップは最良の解より何パーセント長い道順になったかを表す。OR-Tools は7.99(2.90%)である。著者自身が、Concorde のような専用ソルバに勝つことを目的から外していると書き、訓練したサイズから離れるほど品質が落ちると述べている。Xia らの2024年の論文は、訓練なしで使える距離ベースの単純なベースラインが、複雑な機械学習モデルを上回ったと報告している。ニューラルのルーティングソルバのサーベイは、従来の評価が訓練分布に過学習した手法に有利で、弱い古典的なベースラインや不利な時間設定と比べられてきたと指摘する。

分枝限定法で分枝変数の選び方を学習する手法も同様である。Gasse らの手法は、SCIP の既定の規則と比べて、ほぼすべての設定で解く時間が短かった。ただし最大独立集合の問題では、機械学習の手法はどれも既定の規則より解けた数が少ない。Distributional MIPLIB は未使用の3つの分布で評価し、いずれの分布でも SCIP が学習した手法に並ぶか上回った。

調整した範囲の外では成績が変わる。だから学習手法は、自分のデータで学習し直し、必ず測ってから使う。

2. 探索アルゴリズムの選択という探索

手法が多く、データとの相性もあるため、手法を選ぶ作業そのものが探索になる。辞書を引くときに、見出し語がはっきりしていれば索引から引き、うろ覚えなら前後をめくって探すように、問題の性質を見て手の付け方を変えるのは自然なやり方で、これを自動でやるには、問題の特徴を受け取って、使う手法を一つ返す仕組みを作ればよい。研究ではこれがアルゴリズム選択問題として扱われてきた。教科書的には、解きたい問題の集合、手持ちのアルゴリズムの集合、性能を測る尺度を定め、問題ごとに性能の高いアルゴリズムを選ぶ写像を作るという定式化になる。

SATzilla は、SAT の最良のソルバはインスタンスごとに入れ替わるという前提に立つ。インスタンスごとに実行時間を予測してソルバを選び、2007年の SAT Competition で金3つ、銀1つ、銅1つを獲得した。ASlib は、アルゴリズム選択のベンチマークを集めたものである。最良の単一ソルバと、インスタンスごとに最良のソルバを選ぶ理想との差のうち、選択で埋められた割合は SAT11-RAND で0.90、CSP-MZN-2013 で0.91だったが、SAT11-INDU では最良でも0.15にとどまった。ASlib の論文は、収録したシナリオの多くが、選択による性能向上を報告した論文から来ていると断っている。

選択そのものにも費用がかかる。SATzilla は、特徴の計算と pre-solver の時間を自身の実行時間に含めて比較した。選択の競技会の報告は、産業系の SAT では特徴の計算が時間予算の半分以上を占めうることを挙げている。訓練にも費用がかかる。Gagliolo と Schmidhuber は、オフラインの選択では訓練インスタンスを各アルゴリズムで解く費用が無視されていると指摘し、事前の訓練をせず、問題を解きながら選び方を学ぶ方法をとった。どの手法がよいかを試しながら、成績のよい手法に時間を多く回し、ほかの手法も時々試して見直す。この、試すことと稼ぐことを両立させる配分の問題を、教科書ではバンディット問題と呼ぶ。手法の実行時間には前もって分かる上限がないので、論文はこれを損失の上界が未知のバンディット問題として扱った。Frugal Algorithm Selection は、訓練用のラベル付けの費用を、能動学習とタイムアウトの予測で減らす。Hyperband は、ハイパーパラメータ最適化で資源を適応的に配分して早期に打ち切り、ベイズ最適化より5倍から30倍速くなったと報告している。選ぶことと解くことを同時に進めて、選択に予算を取られる問題を抑える方法である。

選択の結果が別のデータでも通用するかどうかは、訓練に使ったデータに左右される。Dietrich らの2024年の研究は、BBOB の成分関数だけで訓練した選択器が、生成した11,920問のテストでは成績が悪いことを示した。Cenikj らの2026年の研究は、BBOB と CEC で訓練した選択モデルが、ロボットの軌道最適化や UAV の経路計画のような実問題に汎化しにくく、多くの場合ダミーのベースラインと同等以下にとどまると報告している。選択器そのものを選ぶメタ選択も試されているが、Tornede らの実験では、過半数のインスタンスで、単一の最良の選択器が、どのメタ選択の手法にも並ぶか上回った。こうした研究の成績は、自分のデータで最初に試す候補を選ぶときの手がかりとして使える。

3. 保証を残す設計

手法の成績が分布で変わるなら、予測が外れたときの下限を設計で確保しておく方法がある。予測付きアルゴリズムの枠組みでは、予測器に任意のものを使える。辞書で単語を引くときは、見当をつけたページを開いてそこから前後へ広げながら探す。見当が当たっていれば数ページで済み、外れていても最後は半分ずつ絞る引き方に切り替えれば、手間は普通に引いた場合と同じ程度に収まる。Mitzenmacher と Vassilvitskii の章は、この二つの性質を目標に置き、予測が良いときに最適に近い性能が出ることを consistency、予測が大きく外れても予測なしのアルゴリズム並みの性能を保つことを robustness と呼ぶ。第2回で触れた予測付きの二分探索がこの辞書の引き方にあたる。予測した位置と実際の位置のずれを η とすると、比較回数は高々 2 log η で、ずれは配列の長さ以下なので、予測がどれほど外れても、比較回数は二分探索の2倍以内に収まる。スキーレンタルは、何日滑るか分からないまま、毎日板を借り続けるか、どこかで買うかを決める問題である。結果を全部知っていた場合の最小の費用に対して実際の費用が何倍になったかを競争比と呼び、パラメータ λ によって、競争比を誤差0のとき 1+λ、誤差がどれほど大きくても 1+1/λ に収められる。λ を小さくして予測を信じるほど、当たったときの費用は最小に近づき、外れたときの倍率は大きくなるので、consistency と robustness はトレードオフの関係にある。

学習ブルームフィルタも同じ考え方で作られている。ブルームフィルタは、「なし」の答えは常に正しく、「あり」の答えだけが時々外れる、という片側だけの誤りを許す仕組みである。学習モデルに判定させると、実際にはあるキーを「なし」と答える偽陰性が起こりうるので、モデルが「なし」と答えたキーをもう一度バックアップのブルームフィルタに通して、この偽陰性を防ぐ。SAT の NeuroBack は、各変数をまず真と偽のどちらに置いて試すか(位相)について、解に現れやすい側を GNN で一度だけ事前に予測し、CDCL ソルバの Kissat に渡す。毎回オンラインで推論する重さを避け、探索の骨格は古典的な手法のまま残している。著者は、SATCOMP-2022 で最大5.2%、2023 で最大7.4%多く解けたと報告している(推論に成功した問題だけが対象)。

予測が使える範囲にも限界がある。Tree Search With Predictions は、ソート済みの配列では予測付きの二分探索が O(log η) で済む一方、木に一般化すると一般には O(log η) を達成できず、パス幅 k の木で O(k log η) になることを示した。配列は一本道の木にあたり、パス幅は枝分かれが入り組むほど大きくなる値なので、枝分かれの多い木ほど予測の効き目が薄れる。配列の外に出たとたん、予測を活かすのは難しくなる。

LLM に探索のコードを書かせる場合にも、同じ考え方が当てはまる。Wang らの2026年の研究は、LLM に最適化を促しても高速化は中央値で1.03倍から1.12倍にとどまり、変数、制約、目的を形式化して検証済みのソルバに渡すほうが正しさで勝ると報告している。

4. 大規模データ向けの意思決定木

ここまでの回の内容を、大規模なデータで手法を選ぶ手順として、私なりに整理してみた。件数やメモリの閾値は環境ごとに違うので、木の末尾の手順に沿って、自分のデータで試しながら決めていく。

答えの形は何か
├─ キー・範囲・順序（第1・2回）
│    ├─ 更新が少ない: ソート+二分探索、B木を基準にする。
│    │                学習索引は、キー分布が滑らかで読み取り中心なら候補に加える
│    ├─ 更新が多い:   B木、LSM-tree、ハッシュ表
│    ├─ 「ない」を先に判定したい: ブルームフィルタ、スキップインデックス
│    └─ 同一性・変更範囲: ハッシュ
├─ パターン・語（第3回）
│    ├─ 文字列: アルファベットとパターン長で測る。多数のパターンは エイホ・コラシック法
│    └─ 文書: 転置索引 + BM25 を基準にし、必要ならリランカーを足す
├─ 類似・関連（第4回）
│    ├─ ANN: 標準的な埋め込みはグラフ型を基準にする。
│    │       分布外のクエリ、フィルタ付き、メモリ制約は、自分のクエリで測る
│    ├─ 語彙と意味の両方が要る: BM25 とベクトルを併用し、順位を統合する
│    └─ 推薦: 候補生成 → ランキング。近傍法や iALS を基準にする
└─ 解を作る（第5〜7回）
     ├─ 保証が要る: 形式化して既存のソルバ（MIP、SAT、CP-SAT）に渡す。
     │              同じグラフに繰り返し問い合わせるなら前処理（CH、HL）
     ├─ 良い解でよい: 局所探索を基準に、焼きなまし、PSO、ACO などを
     │                部品とパラメータで選び、自データで調整する
     └─ 評価関数: 緩和 → 特徴の設計 → 検証器の順に検討し、穴を塞ぐ

全ての枝に共通する手順
 1. 自分のデータ、クエリ、負荷で評価セットを作る（難しいクエリ、分布外、更新を含める）
 2. 単純な基準を先に置く（二分探索、BM25、近傍法、既存のソルバ）
 3. 基準で間に合わない分だけ、費用の低い近似や前処理から順に足していく
 4. 構築、前処理、更新、メモリ、推論、特徴の計算まで、全ての費用を評価に含める
 5. 最悪ケースの保証を持つ側を残し、学習や近似は上乗せにする
 6. 分布、更新、クエリが変わったら 1 に戻る

6番の再評価は、索引を維持し続けるシステムとして捉える第1回の見方につながる。

5. 設計で決める四つの判断

システムの性能は、おおむね四つの判断で決まる。どの問い合わせのために何を事前に並べておくか、何を要約するか、どの単位で変更を検知するか、どこまで正確さを犠牲にできるかである。条件に対して最適な検索や探索のアルゴリズムを選べたかどうかは、この四つが決まった後でようやく効いてくる。B木、ブルームフィルタ、HNSW は四つへの答え方が違うだけで、全件のうち、できる限り少ない部分だけを読んで答えへたどり着くという同じ問題を解いている。

探索でも判断の形は同じである。道路網を前処理する経路探索は、空間と時間をかけて何を事前に要約しておくかを決める例で、最適性の保証を手放して枝を捨てる手法は、どこまで正確さを犠牲にできるかへの別の答えになる。探索で違うのは、候補の全体を見渡せないまま、局所の評価をもとに枝を捨てていくため、どの枝を捨てるかの判断が答えの質に直接響く点である。検索しやすくしておくか、検索するか、探索するかの選択は、これから来る問い合わせにどこまで先回りして備え、その代わりに何を捨てるかを決めることでもある。