線形回帰とその回復方法

出所： xkcd

線形回帰は、データ分析に関連する多くの分野の基本アルゴリズムの XNUMX つです。 その理由は明らかです。 これは非常にシンプルで理解しやすいアルゴリズムであり、数百年とは言わないまでも、何十年にもわたって広く使用されてきました。 その考え方は、XNUMX つの変数が他の変数のセットに対して線形依存していると仮定し、この依存関係を復元しようとするというものです。

ただし、この記事は線形回帰を使用して実際的な問題を解決することについては説明しません。 ここでは、機械学習モジュールを作成するときに遭遇した、回復のための分散アルゴリズムの実装の興味深い機能を検討します。 アパッチ・イグナイト。 少し基本的な数学、機械学習、分散コンピューティングは、データが数千のノードに分散している場合でも線形回帰を実行する方法を理解するのに役立ちます。

何それ？

私たちは線形依存性を回復するという課題に直面しています。 入力データとして、おそらく独立した変数のベクトルのセットが与えられ、それぞれが従属変数の特定の値に関連付けられます。 このデータは XNUMX つの行列の形式で表すことができます。

ここで、依存性が仮定され、さらに線形であるため、仮定を行列の積の形式で書きます (記録を簡略化するために、ここと以下では、方程式の自由項が背後に隠されていると仮定します) 、行列の最後の列 単位が含まれます):

連立一次方程式によく似ていますね。 と思われますが、おそらくそのような方程式系の解は存在しません。 その理由は、ほとんどすべての実データに存在するノイズです。 もう XNUMX つの理由は、線形依存性自体が欠如していることである可能性があります。これは、元の変数に非線形に依存する追加の変数を導入することで対処できます。 次の例を考えてみましょう。

出所： Wikipedia

これは、XNUMX つの変数の関係を (軸に沿って) 示す線形回帰の簡単な例です。 ) 別の変数から (軸に沿って) ）。 この例に対応する線形方程式系が解を得るには、すべての点が同じ直線上に正確に存在する必要があります。 しかし、そうではありません。 しかし、正確にはノイズのため (または線形関係の仮定が間違っていたため)、これらは同じ直線上にありません。 したがって、実際のデータから線形関係を復元するには、通常、もう XNUMX つの仮定を導入する必要があります。入力データにはノイズが含まれており、このノイズには 正規分布。 他のタイプのノイズ分布についても仮定することができますが、ほとんどの場合、考慮されるのは正規分布です。これについては後で説明します。

最尤法

そこで、ランダムな正規分布ノイズが存在すると仮定しました。 このような状況ではどうすればよいでしょうか? 数学におけるこの場合には、広く使用されています。 最尤法。 要するに、その本質は選択にあります 尤度関数 そしてその後の最大化。

通常のノイズを含むデータから線形関係を復元することに戻ります。 仮定された線形関係は数学的な期待値であることに注意してください。 既存の正規分布。 同時に、その確率は、 観測可能なものの存在に応じて、何らかの値を取る このようになります：

代わりに置き換えてみましょう и 必要な変数は次のとおりです。

残っているのはベクトルを見つけることだけです 、この確率が最大になるとき。 このような関数を最大化するには、最初にその対数を取ると便利です (関数の対数は関数自体と同じ点で最大値に達します)。

つまり、次の関数を最小化することになります。

ちなみにこれをメソッドといいます 最小二乗。 多くの場合、上記の考慮事項はすべて省略され、この方法が単純に使用されます。

QR分解

上記の関数の最小値は、この関数の勾配がゼロになる点を見つけることによって見つけることができます。 そして、勾配は次のように記述されます。

QR分解 最小二乗法で使用される最小化問題を解くための行列法です。 この点に関して、方程式を行列形式で書き直します。

そこで行列を分解します 行列に и そして、一連の変換を実行します (QR 分解アルゴリズム自体はここでは考慮されません。当面のタスクに関連してその使用のみが考慮されます)。

行列 直交している。 これにより、仕事を取り除くことができます :

そして、置き換えると、 на 、それなら何とかなるだろう 。 それを考えると は上三角行列で、次のようになります。

これは代入法を使えば解決できます。 要素 として位置しています 、前の要素 として位置しています などなど。

ここで、QR 分解の使用によって得られるアルゴリズムの複雑さは次のとおりであることに注目してください。 。 さらに、行列乗算演算は十分に並列化されているにもかかわらず、このアルゴリズムの効果的な分散バージョンを作成することは不可能です。

勾配降下法

関数の最小化について話すときは、(確率的) 勾配降下法を常に覚えておく価値があります。 これは、ある点における関数の勾配を繰り返し計算し、それを勾配と反対の方向にシフトすることに基づいた、シンプルで効果的な最小化方法です。 このような各ステップは、解決策を最小値に近づけます。 グラデーションはまだ同じように見えます。

このメソッドは、勾配演算子の線形特性により、適切に並列化および分散されます。 上の式では、和記号の下に独立した項があることに注意してください。 言い換えれば、すべてのインデックスに対して独立して勾配を計算できます。 最初から 、これと並行して、インデックスの勾配を計算します。 до 。 次に、結果のグラデーションを追加します。 加算の結果は、最初から XNUMX 番目までのインデックスの勾配を即座に計算した場合と同じになります。 。 したがって、データが複数のデータに分散されている場合、勾配を各データに対して個別に計算し、これらの計算の結果を合計して最終結果を得ることができます。

実装の観点から見ると、これはパラダイムに適合します MapReduce。 勾配降下法の各ステップで、勾配を計算するタスクが各データ ノードに送信され、計算された勾配がまとめて収集され、それらの合計の結果が結果を改善するために使用されます。

MapReduce パラダイムは実装が簡単で実行機能があるにもかかわらず、勾配降下法には欠点もあります。 特に、収束を達成するために必要なステップ数は、他のより特殊な方法と比較して大幅に多くなります。

LSQR

LSQR これは問題を解決するためのもう XNUMX つの方法であり、線形回帰の復元と連立一次方程式の解法の両方に適しています。 その主な特徴は、マトリックス手法と反復アプローチの利点を組み合わせていることです。 このメソッドの実装は両方のライブラリにあります。 SciPy、および マトラブ。 この方法の説明はここでは行いません (記事で見つけることができます) LSQR: スパース線形方程式およびスパース最小二乗法のアルゴリズム）。 代わりに、分散環境での実行に LSQR を適応させるアプローチが示されます。

LSQR メソッドは以下に基づいています。 XNUMX 重対角化手順。 これは反復的な手順であり、各反復は次のステップで構成されます。


しかし、行列だと仮定すると、 が水平方向に分割されている場合、各反復は XNUMX つの MapReduce ステップとして表すことができます。 このようにして、各反復中のデータ転送を最小限に抑えることができます (未知数の数に等しい長さのベクトルのみ)。

線形回帰を実装するときに使用されるのはこのアプローチです。 Apache Ignite ML.

まとめ

線形回帰回復アルゴリズムは数多くありますが、そのすべてがすべての状況に適用できるわけではありません。 したがって、QR 分解は、小さなデータセットを正確に解決するのに最適です。 勾配降下法は実装が簡単で、近似解をすぐに見つけることができます。 また、LSQR は、分散可能であり、勾配降下法と比較してより速く収束するため、前の XNUMX つのアルゴリズムの最良の特性を組み合わせたものであり、QR 分解とは異なり、近似解を見つけるためにアルゴリズムを早期に停止することもできます。

出所： habr.com