分散機械学習用パラメータサーバー

導入

多くの機械学習の問題は、トレーニングと推論に大量のデータに依存しています。インターネット規模の大規模企業は、テラバイトまたはペタバイトのデータを使用してトレーニングを行い、そこからモデルを作成します。これらのモデルは、ほとんどの場合に推論誤差を最適化する重みで構成されています。重み/パラメータの数は数十億から数兆のオーダーです。このような大規模なモデルでは、単一のマシンで学習と推論の両方を実行することは不可能です。分散学習と推論に使用できるフレームワークがあると便利です。パラメータは複数のノード間で共有され、それらのノードを使用して更新され、計算が実行され、調整される必要があるため、共有に関しては大量のデータがボトルネックになる可能性があります。共有には、帯域幅、シーケンシャル機械学習 (ML) アルゴリズムの同期、マシンのフォールト トレランスの面でコストがかかり、障害率は 10% にも達します。パラメータ サーバー (https://www.cs.cmu.edu/~muli/file/parameter_server_osdi14.pdf) は、これらの問題を解決し、分散機械学習アルゴリズムを構築するための新しいフレームワークを提案しました。

[[248745]]

主なデザインコンセプト

パラメータ サーバーは、次の設計要件を提案します。

• 効率的な通信: 機械学習 (ML) アルゴリズムの全体的なネットワーク帯域幅を削減する非同期タスク モデルと API
• 柔軟な一貫性モデル: 緩和された一貫性により、同期コストが削減されます。また、開発者はアルゴリズムの収束とシステム パフォーマンスのどちらかを選択することもできます。
• リソースを追加するための弾力性: コンピューティング全体を再起動せずに容量を追加できます。
• 効率的なフォールト トレランス: 障害率が高く、データ量が多い状況では、マシンの障害が壊滅的でない場合は、タスクを 1 秒程度で迅速に回復できます。
• 使いやすさ: API は、スパース ベクトル、行列、テンソルなどの ML 構造をサポートするように構造化されています。

分散機械学習アルゴリズムの例

従来の教師あり機械学習 (ML) の問題は、ラベル付きデータのトレーニング セットが与えられた場合にコスト関数を最適化することです。コスト関数は、予測誤差を削減または最小限に抑えるために、多数のサンプルにわたって変更および調整されます。モデルを調整したり、エラーを減らしたりするために、偏微分/勾配が計算されます。これらの勾配は、重みを正しい方向に移動してエラーを最小限に抑えるのに役立ちます。

「d」次元の特徴ベクトルの場合、モデルは次の式を使用して、これまでに見たことのない x の結果を予測しようとします: i=1 から d までのすべての場合、∑xi * wi。モデルが比較的よく一般化されるようにするため（つまり、トレーニング データだけではうまく機能しない）、予測関数に正規化コンポーネントが追加されます。したがって、上記の関数はΣxi*wi +ƛ*Norm(w)になります。ここで、ƛ はトレーニング データで見つかった重みにペナルティを課すために使用されます。これにより、学習した重みが弱まり、過剰適合が回避され、これまで見たことのないデータへの一般化が容易になります。この記事では、フレームワークのシステム面に重点を置いています。

上記の予測アルゴリズムを解決するために、分散確率的勾配降下法がどのように使用されるかを見てみましょう。次の図は、反復アルゴリズムの作業を並列化する高レベルのプロセスを示しています。

分散トレーニングアルゴリズム

システムはいくつかのサーバー ノードとワーカー ノードで構成されます。各ワーカーはデータのサブセットをロードし、異なるワーカーは異なるサンプルをロードします。各ワーカーはローカル データの勾配を計算して損失関数を最適化します。次に、各ワーカーはこれらの部分勾配をサーバー ノードに送信します。サーバー ノードは、多数のワーカー ノードから受信した勾配を集約します。サーバー ノードが終了すると、ワーカー ノードはサーバー ノードから新しい重みセットを取得し、勾配計算を再度実行できます。ほとんどの時間は、g1、g2、...、gm の勾配の計算に費やされます。これらはtranspose(X)*wを使用して計算されます。 w が数十億から数兆のオーダーである場合、この計算は単一のノードでは実行不可能です。ただし、各ノードがデータのサブセットのみを処理することの良い副作用は、データに対応する重みのみが必要になることです。ユーザーが広告をクリックする可能性があるかどうかを予測しようとする場合、「regularizers」などの単語はあまり興味深くなく、ほとんどのワーカーは重みを更新しません。上の図からわかるように、特定のノードでは、ドット積に存在する/ドット積に関連付けられている特徴 x の重み (w) のみをワーカー ノードに送信する必要があります (各ワーカー ノードの x とスパース重みベクトル w の対応する列を参照)。

大まかに言えば、各ワーカーのアルゴリズムは次のようになります。

• 各ワーカーで、データのサブセットの勾配（偏微分）を計算する
• この部分的なグラデーションをサーバーにプッシュする
• 準備ができたらサーバーから新しい重みセットを取得します

各サーバー上:

• すべての「m」人のワーカーの勾配を集計します。 g = Σgi
• 新しい重み = 古い重み - 学習率 *(g +ƛ* Norm(古い重み))

建築

高レベルアーキテクチャ

ParameterServer は、システム内で複数のアルゴリズムを実行できるようにするためのサーバー グループで構成されています。サーバー グループ内の各サーバー ノードは、キースペース/データのパーティションを担当します。サーバーは相互に通信してデータを移行/複製し、スケーラビリティと可用性を高めることができます。サーバー マネージャーは、サーバー グループの一貫したビューを維持する責任があります。活性チェックを実行し、キースペースの所有権を各サーバー ノードに割り当てます。

アプリケーションには通常、ワークグループが割り当てられます。複数のワーカー ノードがワーク グループを形成し、前のセクションで説明したように、サーバー グループと通信してパラメーターを抽出し、勾配をプッシュします。ワークグループは相互に通信する必要はありません。スケジューラはワークグループを確認し、それらにタスクを割り当てます。通常、同じワーカーノードは、同じデータセットに対して反復アルゴリズムを実行して、ローカルに保存されたデータを活用します。パラメータ名前空間を使用すると、複数の作業グループ間で作業をさらに並列化できます。さらに、同じパラメータ名前空間を複数のグループ間で共有できます。典型的な例としては、1 つのグループがリアルタイム推論をサポートし、他のワークグループがモデルの開発と共有パラメータの更新をサポートすることが挙げられます。

このアーキテクチャを構築するために必要なプリミティブのいくつかを見てみましょう。

キーバリューAPI

執筆時点では、既存のシステムではキーと値のペアを使用して共有パラメータを渡しています。例としては、feature-id とその重みがあります。従来、これは memcached またはその他のキー値ストアを使用して実装されていました。重要な洞察は、値が主にベクトルや行列などの線形代数プリミティブであり、これらの構造に対する操作を最適化できることが有用であるということです。一般的な演算は、ドット積、行列乗算、L-2 ノルムなどです。したがって、キーと値のセマンティクスを維持し、値をベクトルとして割り当てる行列は、最も一般的な機械学習 (ML) 演算を最適化するのに非常に役立ちます。

範囲ベースのプッシュとプル

前のアルゴリズムで説明したように、サーバー ノードから抽出された重みと勾配がサーバー ノードにプッシュされます。範囲ベースのプッシュとプルをサポートすることで、ネットワーク帯域幅の使用が最適化されます。したがって、システムはデータを抽出するために w.push(R, destination) と w.pull(R, destination) をサポートします。どちらの場合も、範囲 R 内のキーに対応する値が宛先ノードからプッシュおよびプルされます。 R を単一のキーに設定すると、単純なキー値の読み取りおよび書き込みセマンティクスが提供されます。勾配 g は w と同じキーを持つため、w.push(R, g, destination) を使用してローカル勾配を宛先にプッシュできます。

非同期タスクと依存関係

タスクは RPC と考えることができます。プッシュまたはプル リクエストは、実行中のタスクまたはリモート関数になります。タスクは通常非同期であり、プログラム/アプリケーションはタスクを発行した後も実行を継続できます。 (キー、値) ペアの応答を受信すると、タスクを完了としてマークできます。特定のタスクが依存するすべてのサブタスクが返された場合にのみ、タスクを完了としてマークできます。タスクの依存関係は、アプリケーションの全体的な制御フローを実装するのに役立ちます。

柔軟な一貫性モデル

上記のモデルからわかるように、タスクは多くの場合リモート ノード上で並列に実行されます。したがって、さまざまなタスク間にデータ依存関係がある場合、古いバージョンのデータを取得することになる可能性があります。機械学習では、最近の重みの代わりに古い重みやそれほど古くない重みを使用することはそれほど有害ではない場合があります。 Parameterserver を使用すると、実装者は追求する一貫性モデルを選択できます。次の図に示すように、3 種類の一貫性モデルがサポートされています。順次一貫性では、すべてのタスクが次々に実行されます。結果整合性では、すべてのタスクが並行して開始され、最終的に収束します。制限付きレイテンシでは、開始されたタスクが 't' 回以上完了するとすぐにタスクが開始されます。下の図 c は制限付きレイテンシが 1 であることを示しています。

一貫性モデル

実装の詳細

ベクトル クロック: フォールト トレランスとリカバリのために、システムにはいくつかのタイムスタンプが必要です。 Parameterserver はベクトル クロックを使用して、システム内のイベントの特定の順序を確立します。ベクトル クロックは、ノード数 (m) とパラメーター数 (p)、つまり O(m * p) に基づいてコストが高くなる可能性があります。システム内のパラメータの数が多いため、これはかなり大きくなる可能性があります。ほとんどの操作は範囲を使用して実行できるため、各範囲にベクター クロックを割り当てるのではなく、各範囲にベクター クロックを割り当てることができます。システム内に一意の範囲がある場合、このメカニズムを通じて複雑さはさらに O(m * r) まで削減できます。システムは最初は m 個のクロックのみで開始されるため、このノードに属するキー空間全体には 1 つのベクトル クロックがあります。これにより回復プロセスが遅くなる可能性があります。したがって、システム内にさらに多くの範囲が作成されると、更新されたベクター クロックがこれらの範囲パーティションに配布されます。

メッセージ: システム内のメッセージは、(VectorClock(R)、すべてのキーと値はR) として表されます。データ集約型の機械学習 (ML) アプリケーションでは通信量が多いため、キャッシュによって帯域幅を削減できます。反復アルゴリズムでは同じキーが複数回渡されるため、ノードはキーをキャッシュできます。これらには反復中に変更されない値が多く含まれる可能性もあるため、効率的に圧縮できます。 ParameterServer は snappy 圧縮を使用して大量のゼロを効率的に圧縮します。

一貫性のあるハッシュ: 一貫性のあるハッシュは、システムに新しいノードを簡単に追加および削除するために使用されます。ハッシュ リング上の各サーバー ノードは、いくつかのキー スペースを担当します。キースペースのパーティション分割と所有権は、サーバー マネージャーによって管理されます。

レプリケーション: レプリケーションは隣接ノードによって実行されます。各ノードは、k 個の隣接ノードのキー空間を複製します。キースペースを担当するマスター サーバーは、同期通信を通じて近隣のサーバーと調整し、レプリカを維持します。マスターがキー範囲をプルするたびに、それが近隣に複製されます。ワーカーがデータをサーバーにプッシュすると、データがスレーブに複製されるまでタスクは完了として認識されません。当然、押したり引いたりするたびにこれを実行しなければならないとしたら面倒な作業になります。したがって、システムでは、一定量のデータが集約された後にレプリケーションも許可されます。この集約は下の図に示されています。 s1 と s2 の間では、レプリケーション メッセージが 1 つだけ交換されます。 x と y の両方が S1 にプッシュされ、その後 S1 で関数計算タスクが実行され、最後のメッセージが複製され、確認 (4、5a、5b) がワーカー 1 とワーカー 2 に返されてタスクが完了します。

集約後のレプリケーション

• サーバー ノード管理: システムに新しいサーバー ノードを追加して拡張できると便利です。このような場合、サーバー マネージャーは新しいノードにキースペースを割り当てます。このキーは、以前に終了したノードから取得することも、負荷の高いサーバー ノードのキースペースを分割することによって取得することもできます。この新しいノードは、担当するキー空間を取り出し、k 個の隣接ノードからレプリカをスレーブとして取得します。通常、この新しいノードによって抽出されたときに上書きされたデータを抽出するには、2 フェーズの抽出が必要になる場合があります。次に、サーバー マネージャーはこの所有権割り当てメッセージをリング上の他のノードにブロードキャストし、他のサーバー ノードはこの新しい所有権割り当てに基づいてキー スペースの使用量を削減できます。離脱するノードの場合、サーバー マネージャーはキースペースを新しい着信ノードに割り当てます。サーバー マネージャーはハートビートを介してノードの健全性を維持します。
• ワーカー ノード: 新しいワーカー ノードの追加は比較的簡単です。タスク スケジューラは、データ範囲をワーカー ノードに割り当てます。この新しいノードは、NFS または他のワーカーからデータをプルします。次に、スケジューラはこのメッセージを他のワーカーにブロードキャストし、他のワーカーがトレーニング データを放棄してスペースを取り戻せるようにします。ワーカーノードが離脱すると、データのサイズに応じて、アルゴリズムの所有者がデータを復元するかどうかを決定します。

結論は

この記事では、分散機械学習のいくつかの重要な概念について説明します。システムの観点から見ると、この記事には一貫性ハッシュなどの優れたテクニックがいくつか組み込まれています。範囲ベースの通信とメッセージ パッシングをサポートするネイティブ ML 構造は、効率的な ML フレームワークを構築するための優れた洞察であると思われます。