機械学習がシステム設計に与える影響: 学習したインデックス構造の簡単な分析

顔認識からチェックイン、さまざまなアプリケーションの「あなたの好きなものを推測」まで、現在の機械学習（特にディープラーニング技術）は私たちの日常生活のあらゆる側面で広く利用されています。ディープラーニングフレームワーク（TensorFlow、PyTorchなど）やAI専用チップ（TPU、NPUなど）などのハードウェアおよびソフトウェアシステムの設計により、機械学習のパフォーマンスが大幅に向上し、その応用シナリオが拡大しました。同時に、機械学習手法自体を使用して、コンピュータ システムの設計を最適化したり、従来の設計パターンを置き換えたりすることはできるでしょうか? Googleの技術の第一人者であるジェフ・ディーン氏が率いる研究チームは、2018年のSIGMOD学術会議で「学習したインデックス構造の事例」[1]という興味深い論文を発表しました。この記事では、学習済みインデックス構造の実装、利点、欠点について簡単に紹介し、システム設計のヒントやアイデアを提供したいと思います。

1. 学習されたインデックス構造とは何ですか?

インデックスは、データベースやファイルシステムなどの分野で一般的なデータ構造であり、最も古典的なものは B ツリーです。 B ツリーは範囲インデックス データ構造です。クエリ中にキー (または特定の範囲のいくつかのキー) が指定されると、B ツリーはキーを含む対応する範囲のリーフ ノードをインデックスし、リーフ ノード内でキーを検索します。キーがインデックス内に存在する場合、対応する位置が取得されます。通常、論理ページ内のレコードはキーによってインデックス付けされます。図 1 (a) に示すように、入力はキーであり、出力は照会するレコードに対応する位置間隔です。範囲インデックスの他に、ハッシュマップなどのポイントインデックスやブルームフィルターなどの存在インデックスもあり、これらもよく使われるインデックスデータ構造です。学習されたインデックス構造の主なアイデアは、B ツリーやブルーム フィルターなどのデータ構造を機械学習モデルに置き換えることです。図 1 (b) に示すように、検索操作はキーに基づいてインデックス データの場所を予測するようになります。範囲インデックスを例に、学習済みインデックス構造の設計と実装の考え方を詳しく紹介します。

図1 Bツリーと学習インデックスの概略図

図 1 は、従来の B ツリーと学習済みインデックスの比較です。ご覧のとおり、Learned Index の入力は Key であり、出力はこの Key に対応する検索結果の場所です (エラーがある場合があります)。エラーの上限は、リーフ ノードのデータ ページ内の結果エントリです (つまり、必要な検索結果はデー​​タ ページの最後にあります)。

では、範囲インデックスの機械学習モデルをどのように設計すればよいのでしょうか?ここでは、1 次元のクラスター化インデックスの場合のみを検討します (つまり、データは検索に使用されるキーに従ってソートされ、クラスター化インデックスを介して実際のデータ配置へのポインターのレイヤーを追加することで、非クラスター化インデックスを実装できます)。学習されたインデックス構造は、図 2 に示すように、インデックスの位置は実際にはキーの増加とともに増加する単調増加関数であるという洞察を巧みに提供します。特定のインデックスは離散的である可能性がありますが、全体的なインデックスは関数で記述できます。

p = F(キー) * N

ここで、p は推定位置、N はインデックス キーの数、F(key) はインデックス データの累積分布関数 (CDF) です。 F(key) の意味は、キー以下のインデックス データ エントリの合計 (つまり、キーの位置推定値) です。本質的には、データ セットの分布特性を反映します。 B-Tree の一般的な設計と比較して、学習されたインデックス構造は、データ セットの固有の分散特性を考慮し、それを使用してインデックスの構造を最適化します。学習インデックスの誤差の上限は制御可能であり、誤差範囲内で予測位置に応じて左または右にバイナリ検索を実行するだけで、検索対象を正確に見つけることができます。

図2 インデックスポジションの累積確率分布（CDF）

では、 F(Key)を取得するにはどうすればよいでしょうか? Learn Index Structures の著者は、まず TensorFlow を使用して、各層に 32 個のニューロンを持つ 2 層完全接続ニューラル ネットワークを構築しようとしました。Web サーバー ログのデータ セットを使用してトレーニングしたところ、その効果は B-Tree よりもはるかに悪いことがわかりました。問題は次の通りです:

1) TensorFlow は大規模なニューラル ネットワークのトレーニングに使用され、小規模なシナリオでの呼び出しオーバーヘッドは無視できなくなります。

2) アンダーフィッティングの問題。図 2 に示すように、機械学習モデルは CDF の全体的な傾向を非常に正確に推定できますが、単一のデータ項目を正確に表現することは困難です。 B-Tree は、if ステートメントをシンプルかつ効率的に使用して、範囲を正確に分割できます。「ラスト マイル」を最適化するために、機械学習モデルは大量のストレージ スペースとコンピューティング リソースを消費する必要があります。

3) B-Tree の CPU とキャッシュの動作は高度に最適化されており、検索ごとに必要なインデックスの数はわずかです。機械学習モデルでは、予測を行うためにすべてのパラメータの重みを使用する必要があります。

最後に、図 3 に示す段階的モデルを使用して、インデックス構造の学習モデルが実装されました。各モデルは、最も単純な線形回帰 (LR) からディープ ニューラル ネットワーク (DNN) まで、あらゆる機械学習モデルにすることができます。実際には、より単純なモデルのほうが適しています (検索時にモデルに時間をかけすぎないようにするため)。ルックアップが実行されると、最上位モデル (モデルは 1 つだけ) が 2 番目レベルのモデルを選択してキーを処理します。次に、2 番目のレイヤーのモデルは、このキーを処理するために次のレイヤーのモデルを選択し、最下層のモデルはこのキーに対応する予測位置を提供します。しかし実際には、上位層の各モデルは予測位置を出力し、この予測を使用して下位層のモデルが選択されます (モデル ID = (予測位置/レコードの総数) * この層のモデル数)。

ステージング モデル全体はレイヤーごとにトレーニングされ、最初に最上位レイヤーをトレーニングしてからデータを配布します。データ分布とは、上位モデルがキーを予測する下位モデルを指し、モデルはこのトレーニング データをトレーニング セットとして持ちます。したがって、レイヤーの数が増え、各レイヤーのモデルの数が増えると、下位レベルの各モデルのトレーニング データは少なくなります。この利点は、基礎となるモデルがデータのこの部分の分布に簡単に適合できることです (欠点は、データ量が少ないためモデルの選択に制限が生じ、複雑なモデルが収束できないことです)。 [1]で採用されている構造は、ニューラルネットワークモデルは最上層でのみ使用され、残りの層では線形回帰モデルが使用されるというものです。

図3 学習したインデックス構造の段階的モデル

ポイントインデックスと存在インデックスの学習済みインデックス構造についてはここでは詳しく述べませんが、興味のある方は論文[1]とそれを基にしたRMI(Recursive Model Indexes)コード[2]を読んでみてください。

2. 学習したインデックス構造を評価するにはどうすればよいでしょうか?

一般的に、学習したインデックス構造は、システム分野における機械学習の大きな可能性を示していますが、解決すべき問題はまだ多く残っています（過剰適合、インデックスの追加、削除、変更など）。オーバーフィッティングの場合、新しいインデックスのキーが依然として CDF を満たしている場合は、再トレーニングする必要はなく、予測された位置に直接挿入できます。データの分布が変化する場合は、オンライン学習方法を試す必要があります。データが頻繁に更新されるシステムでは、デルタインデックス技術を使用して、学習したインデックスを段階的に更新できます。

実際、学習済みインデックス構造に代表される機械学習の最適化手法は、システム設計の最適化のすべてではありません。例えば、スプラインBツリー[6]は、各リーフノードに1つのスプライン（つまり、キーとその位置）のみを格納するBツリーを使用し、2つのスプライン間のデータは、2つの点間の直線を使用して予測されます。このような単純なデータ構造は、多くの場合、複雑な Learn Index と同等か、それ以上です。ポイントインデックスの分野では、学習インデックスによって競合を減らすことで達成される最適化は、各キーを同時に2つのバケットにハッシュするだけのバケット化カッコウハッシュ[7]によって簡単に破られる可能性があります。

しかし、これはシステム設計における機械学習の価値を否定するものではありません。機械学習は、システム設計の最適化と思考を刺激し、これまで発見されたことのないシステム設計のアイデアを探求することができます。最適化の原則が明確でシナリオが固定されている場合、人間による解釈と再実装は機械学習の方法よりも効率的で安定していることは明らかです。データの分布やその他の特性が動的に変化するシナリオでは、機械学習の手法はデータ特性をターゲットに合わせて最適化および適応できるため、理論的には一般的なアルゴリズムやデータ構造よりも優れている可能性があります。

3. 機械学習 + システム設計 = ?

学習済みインデックス構造にはまだ多くの欠点があるかもしれませんが、機械学習をコンピュータシステムの設計に適用するトレンドが到来したことは無視できません。 「Learn Index Structures」が機械学習をコンピュータシステム設計の分野に参入させるための最初のきっかけとなったとすれば、2019年に発表された機械学習システムホワイトペーパー[5]は、機械学習とコンピュータシステム設計の学際的な研究方向の誕生を正式に確立したことになります。 SysML18 カンファレンスの基調講演で Jeff Dean 氏は次のように述べました。「コンパイラ、ネットワーク、オペレーティング システム、チップ設計など、ヒューリスティックを使用するあらゆるシステム ドメインは、機械学習を適用するのに適した場所です。」成功の鍵は2つあります。

1) 数値で正確に表現できる最適化指標を見つける。

2) 統合機械学習（モデルの入出力定義、トレーニングおよびテストデータセットの取得など）のための明確なインターフェースがあります。

コンピュータ システムの分野における最適化の場合、これら 2 つの要件は比較的簡単に達成できるようです。