高度なトピック
\[ \newcommand{\R}{\mathbb{R}} \newcommand{\E}{\mathbb{E}} \newcommand{\x}{\mathbf{x}} \newcommand{\y}{\mathbf{y}} \newcommand{\wv}{\mathbf{w}} \newcommand{\av}{\mathbf{\alpha}} \newcommand{\bv}{\mathbf{b}} \newcommand{\N}{\mathbb{N}} \newcommand{\id}{\mathbf{I}} \newcommand{\ind}{\mathbf{1}} \newcommand{\0}{\mathbf{0}} \newcommand{\unit}{\mathbf{e}} \newcommand{\one}{\mathbf{1}} \newcommand{\zero}{\mathbf{0}} \]
線形メソッドの最適化（開発者向け）
Limited-memory BFGS (L-BFGS)
L-BFGS は、準ニュートン法の一種である最適化アルゴリズムで、$\min_{\wv \in\R^d} \; f(\wv)$ の形の最適化問題を解きます。L-BFGS メソッドは、ヘッセ行列を構築するために目的関数の二次偏導関数を評価することなく、目的関数を局所的に二次関数として近似します。ヘッセ行列は過去の勾配評価によって近似されるため、ニュートン法で明示的にヘッセ行列を計算する場合とは異なり、垂直方向のスケーラビリティの問題（学習特徴量の数）はありません。その結果、L-BFGS は他の一次元最適化手法と比較して、より高速な収束を達成することがよくあります。
Orthant-Wise Limited-memory Quasi-Newton (OWL-QN) は L-BFGS の拡張であり、L1 および弾性ネット正則化を効果的に処理できます。
L-BFGS は、LinearRegression、LogisticRegression、AFTSurvivalRegression、および MultilayerPerceptronClassifier のソルバーとして使用されます。
MLlib の L-BFGS ソルバーは、breeze の対応する実装を呼び出します。
重み付き最小二乗法のための正規方程式ソルバー
MLlib は、重み付き最小二乗法のための正規方程式ソルバーを、WeightedLeastSquares によって実装しています。
$n$ 個の重み付き観測値 $(w_i, a_i, b_i)$ を与えると
- $w_i$ は i 番目の観測値の重み
- $a_i$ は i 番目の観測値の特徴量ベクトル
- $b_i$ は i 番目の観測値のラベル
各観測値の特徴量の数は $m$ です。以下の重み付き最小二乗法定式化を使用します。\[ \min_{\mathbf{x}}\frac{1}{2} \sum_{i=1}^n \frac{w_i(\mathbf{a}_i^T \mathbf{x} -b_i)^2}{\sum_{k=1}^n w_k} + \frac{\lambda}{\delta}\left[\frac{1}{2}(1 - \alpha)\sum_{j=1}^m(\sigma_j x_j)^2 + \alpha\sum_{j=1}^m |\sigma_j x_j|\right] \]ここで、$\lambda$ は正則化パラメータ、$\alpha$ は弾性ネット混合パラメータ、$\delta$ はラベルの母標準偏差、$\sigma_j$ は j 番目の特徴量列の母標準偏差です。
この目的関数は、それを解くために必要な統計情報を収集するために、データに対する 1 回のパスのみを必要とします。 $n \times m$ のデータ行列の場合、これらの統計情報は $O(m^2)$ のストレージしか必要としないため、$m$（特徴量の数）が比較的小さい場合は、単一のマシンに保存できます。その後、直接コレスキー分解や反復最適化プログラムなどのローカルメソッドを使用して、単一のマシンで正規方程式を解くことができます。
Spark MLlib は現在、正規方程式に対して 2 種類のソルバーをサポートしています。コレスキー分解と準ニュートン法（L-BFGS/OWL-QN）です。コレスキー分解は正定値共分散行列（つまり、データ行列の列が線形独立であること）に依存しており、この条件が満たされない場合は失敗します。準ニュートン法は、共分散行列が正定値でない場合でも、合理的な解を提供できます。そのため、この場合、正規方程式ソルバーは準ニュートン法にフォールバックすることもできます。このフォールバックは現在、LinearRegression および GeneralizedLinearRegression 推定器で常に有効になっています。
WeightedLeastSquares は、L1、L2、および弾性ネット正則化をサポートし、正則化と標準化を有効または無効にするオプションを提供します。L1 正則化が適用されない場合（つまり、$\alpha = 0$ の場合）、解析解が存在し、コレスキーまたは準ニュートンソルバーのいずれかを使用できます。 $\alpha > 0$ の場合、解析解は存在せず、代わりに準ニュートンソルバーを使用して係数を反復的に見つけます。
正規方程式アプローチを効率的にするため、WeightedLeastSquares は特徴量の数が 4096 以下であることを要求します。より大きな問題の場合は、代わりに L-BFGS を使用してください。
反復重み付き最小二乗法 (IRLS)
MLlib は、反復重み付き最小二乗法 (IRLS) を IterativelyReweightedLeastSquares によって実装しています。これは、一般化線形モデル (GLM) の最尤推定値を見つけたり、ロバスト回帰の M 推定値やその他の最適化問題を解くのに使用できます。詳細については、Iteratively Reweighted Least Squares for Maximum Likelihood Estimation, and some Robust and Resistant Alternatives を参照してください。
以下の手順で特定の最適化問題を反復的に解きます。
- 現在の解で目的関数を線形化し、対応する重みを更新します。
- WeightedLeastSquares によって重み付き最小二乗法 (WLS) 問題を解きます。
- 収束するまで上記の手順を繰り返します。
各反復で WeightedLeastSquares によって重み付き最小二乗法 (WLS) 問題を解くため、特徴量の数が 4096 以下である必要もあります。現在、IRLS は GeneralizedLinearRegression のデフォルトソルバーとして使用されています。