MLlib: メインガイド

MLlib: RDDベースのAPIガイド

最適化 - RDDベースのAPI

\[ \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}} \]

数学的記述

勾配降下法

$\min_{\wv \in\R^d} \; f(\wv)$ の形式の最適化問題を解くための最も単純な方法は、勾配降下法です。このような一次最適化手法 (勾配降下法とその確率的変種を含む) は、大規模および分散計算に適しています。

勾配降下法は、最も急な降下方向、つまり現在の点、すなわち現在のパラメータ値における関数の導関数 ( 勾配 と呼ばれる) の負の方向に反復的にステップを進めることによって、関数の局所最小値を見つけることを目的としています。目的関数 $f$ がすべての引数で微分可能ではないが、それでも凸である場合、 *劣勾配* は勾配の自然な一般化であり、ステップ方向の役割を担います。いずれの場合でも、$f$ の勾配または劣勾配を計算することはコストがかかります。すべての損失項からの寄与を計算するために、データセット全体を完全にパススルーする必要があるためです。

確率的勾配降下法 (SGD)

目的関数 $f$ が合計として記述される最適化問題は、*確率的勾配降下法 (SGD)* を使用して解くのに特に適しています。教師あり機械学習で一般的に使用される最適化定式化の場合、 \begin{equation} f(\wv) := \lambda\, R(\wv) + \frac1n \sum_{i=1}^n L(\wv;\x_i,y_i) \label{eq:regPrimal} \ . \end{equation} は特に自然です。損失は各データポイントからの個々の損失の平均として記述されるためです。

確率的劣勾配は、ベクトルのランダムな選択であり、期待値において、元の目的関数の真の劣勾配が得られます。1つのデータポイント $i\in[1..n]$ をランダムに均一に選択すると、$\wv$ に関して、$\eqref{eq:regPrimal}$ の確率的劣勾配が次のように得られます。 \[ f'_{\wv,i} := L'_{\wv,i} + \lambda\, R'_\wv \ , \] ここで、$L'_{\wv,i} \in \R^d$ は、$i$番目のデータポイントによって決定される損失関数部分の劣勾配、つまり $L'_{\wv,i} \in \frac{\partial}{\partial \wv} L(\wv;\x_i,y_i)$ です。さらに、$R'_\wv$ は、正則化項 $R(\wv)$ の劣勾配、つまり $R'_\wv \in \frac{\partial}{\partial \wv} R(\wv)$ です。$R'_\wv$ という項は、どのランダムデータポイントが選択されるかには依存しません。明らかに、$i\in[1..n]$ のランダムな選択に対する期待値において、$f'_{\wv,i}$ は元の目的 $f$ の劣勾配であり、$\E\left[f'_{\wv,i}\right] \in \frac{\partial}{\partial \wv} f(\wv)$ を意味します。

SGDを実行することは、単に負の確率的劣勾配 $f'_{\wv,i}$ の方向に進むことになります。つまり、\begin{equation}\label{eq:SGDupdate} \wv^{(t+1)} := \wv^{(t)} - \gamma \; f'_{\wv,i} \ . \end{equation} です。 **ステップサイズ。** パラメータ $\gamma$ はステップサイズであり、デフォルトの実装では、反復カウンタの平方根で減少するように選択されます。つまり、$t$番目の反復では $\gamma := \frac{s}{\sqrt{t}}$ であり、入力パラメータは $s=$ stepSize です。SGDメソッドの最適なステップサイズを選択することは、実際には難しい場合があり、活発な研究のトピックであることに注意してください。

**勾配。** spark.mllib に実装されている機械学習メソッドの（劣）勾配の表は、分類と回帰セクションにあります。

**近接更新。** ステップ方向で正則化項の劣勾配 $R'(\wv)$ を使用する代わりに、近接作用素を使用することにより、場合によっては更新を改善できます。L1正則化項の場合、近接作用素は、L1Updater に実装されているように、ソフトしきい値化によって与えられます。

分散SGDの更新スキーム

GradientDescent のSGD実装では、データ例を単純に（分散して）サンプリングします。最適化問題 $\eqref{eq:regPrimal}$ の損失部分は $\frac1n \sum_{i=1}^n L(\wv;\x_i,y_i)$ であり、したがって $\frac1n \sum_{i=1}^n L'_{\wv,i}$ は真の（劣）勾配になります。これはデータセット全体へのアクセスが必要になるため、パラメータ miniBatchFraction は、代わりに使用するデータの割合を指定します。このサブセットの勾配の平均、つまり \[ \frac1{|S|} \sum_{i\in S} L'_{\wv,i} \ , \] は確率的勾配です。ここで、$S$ はサイズ $|S|=$ miniBatchFraction $\cdot n$ のサンプリングされたサブセットです。

各反復では、分散データセット (RDD) のサンプリングと、各ワーカーマシンからの部分的な結果の合計の計算は、標準のSparkルーチンによって実行されます。

ポイントの割合 miniBatchFraction が1（デフォルト）に設定されている場合、各反復で得られるステップは正確な（劣）勾配降下になります。この場合、使用されるステップ方向にランダム性と分散はありません。一方、miniBatchFraction が非常に小さく選択され、単一のポイントのみがサンプリングされる場合、つまり $|S|=$ miniBatchFraction $\cdot n = 1$ の場合、アルゴリズムは標準のSGDと同等です。その場合、ステップ方向はポイントの均一なランダムサンプリングに依存します。

メモリ制限付きBFGS (L-BFGS)

L-BFGS は、$\min_{\wv \in\R^d} \; f(\wv)$ の形式の最適化問題を解くための準ニュートン法ファミリーの最適化アルゴリズムです。L-BFGS法は、ヘッセ行列を構築するために目的関数の二階偏導関数を評価することなく、目的関数を局所的に二次関数として近似します。ヘッセ行列は以前の勾配評価によって近似されるため、ニュートン法でヘッセ行列を明示的に計算する場合、垂直方向のスケーラビリティの問題（トレーニング特徴量のde数）はありません。その結果、L-BFGSは、他の一次最適化と比較して、多くの場合、より高速な収束を実現します。

最適化手法の選択

線形手法 は内部で最適化を使用し、spark.mllib の一部の線形手法はSGDとL-BFGSの両方をサポートしています。最適化手法が異なれば、目的関数のプロパティに応じて異なる収束保証が得られる可能性があり、ここでは文献を網羅することはできません。一般に、L-BFGSが利用可能な場合は、L-BFGSの方がSGDよりも高速に収束する傾向があるため（反復回数が少ない）、SGDの代わりにL-BFGSを使用することをお勧めします。

MLlibでの実装

勾配降下法と確率的勾配降下法

確率的劣勾配降下法 (SGD) を含む勾配降下法は、MLlib に低レベルプリミティブとして含まれており、それを基にさまざまなMLアルゴリズムが開発されています。例については、線形手法セクションを参照してください。

SGDクラス GradientDescent は、次のパラメータを設定します

L-BFGS

L-BFGS は、現在 MLlib では低レベルの最適化プリミティブにすぎません。線形回帰やロジスティック回帰などのさまざまな ML アルゴリズムで L-BFGS を使用するには、LogisticRegressionWithSGD のようなトレーニング API を使用する代わりに、目的関数の勾配と Updater を自分でオプティマイザに渡す必要があります。以下の例を参照してください。これは次のリリースで対処される予定です。

L1Updater を使用した L1 正則化は機能しません。L1Updater のソフトしきい値ロジックは勾配降下用に設計されているためです。開発者のメモを参照してください。

L-BFGS メソッド LBFGS.runLBFGS には、次のパラメータがあります。

return は、2 つの要素を含むタプルです。最初の要素は、各特徴の重みを含む列行列であり、2 番目の要素は、各反復で計算された損失を含む配列です。

L-BFGS オプティマイザを使用して L2 正則化で二項ロジスティック回帰をトレーニングする例を次に示します。

API の詳細については、LBFGS Scala ドキュメント および SquaredL2Updater Scala ドキュメント を参照してください。

import org.apache.spark.mllib.classification.LogisticRegressionModel
import org.apache.spark.mllib.evaluation.BinaryClassificationMetrics
import org.apache.spark.mllib.linalg.Vectors
import org.apache.spark.mllib.optimization.{LBFGS, LogisticGradient, SquaredL2Updater}
import org.apache.spark.mllib.util.MLUtils

val data = MLUtils.loadLibSVMFile(sc, "data/mllib/sample_libsvm_data.txt")
val numFeatures = data.take(1)(0).features.size

// Split data into training (60%) and test (40%).
val splits = data.randomSplit(Array(0.6, 0.4), seed = 11L)

// Append 1 into the training data as intercept.
val training = splits(0).map(x => (x.label, MLUtils.appendBias(x.features))).cache()

val test = splits(1)

// Run training algorithm to build the model
val numCorrections = 10
val convergenceTol = 1e-4
val maxNumIterations = 20
val regParam = 0.1
val initialWeightsWithIntercept = Vectors.dense(new Array[Double](numFeatures + 1))

val (weightsWithIntercept, loss) = LBFGS.runLBFGS(
  training,
  new LogisticGradient(),
  new SquaredL2Updater(),
  numCorrections,
  convergenceTol,
  maxNumIterations,
  regParam,
  initialWeightsWithIntercept)

val model = new LogisticRegressionModel(
  Vectors.dense(weightsWithIntercept.toArray.slice(0, weightsWithIntercept.size - 1)),
  weightsWithIntercept(weightsWithIntercept.size - 1))

// Clear the default threshold.
model.clearThreshold()

// Compute raw scores on the test set.
val scoreAndLabels = test.map { point =>
  val score = model.predict(point.features)
  (score, point.label)
}

// Get evaluation metrics.
val metrics = new BinaryClassificationMetrics(scoreAndLabels)
val auROC = metrics.areaUnderROC()

println("Loss of each step in training process")
loss.foreach(println)
println(s"Area under ROC = $auROC")
Spark リポジトリの "examples/src/main/scala/org/apache/spark/examples/mllib/LBFGSExample.scala" に完全なサンプルコードがあります。

API の詳細については、LBFGS Java ドキュメント および SquaredL2Updater Java ドキュメント を参照してください。

import java.util.Arrays;

import scala.Tuple2;

import org.apache.spark.api.java.*;
import org.apache.spark.mllib.classification.LogisticRegressionModel;
import org.apache.spark.mllib.evaluation.BinaryClassificationMetrics;
import org.apache.spark.mllib.linalg.Vector;
import org.apache.spark.mllib.linalg.Vectors;
import org.apache.spark.mllib.optimization.*;
import org.apache.spark.mllib.regression.LabeledPoint;
import org.apache.spark.mllib.util.MLUtils;
import org.apache.spark.SparkConf;
import org.apache.spark.SparkContext;

String path = "data/mllib/sample_libsvm_data.txt";
JavaRDD<LabeledPoint> data = MLUtils.loadLibSVMFile(sc, path).toJavaRDD();
int numFeatures = data.take(1).get(0).features().size();

// Split initial RDD into two... [60% training data, 40% testing data].
JavaRDD<LabeledPoint> trainingInit = data.sample(false, 0.6, 11L);
JavaRDD<LabeledPoint> test = data.subtract(trainingInit);

// Append 1 into the training data as intercept.
JavaPairRDD<Object, Vector> training = data.mapToPair(p ->
  new Tuple2<>(p.label(), MLUtils.appendBias(p.features())));
training.cache();

// Run training algorithm to build the model.
int numCorrections = 10;
double convergenceTol = 1e-4;
int maxNumIterations = 20;
double regParam = 0.1;
Vector initialWeightsWithIntercept = Vectors.dense(new double[numFeatures + 1]);

Tuple2<Vector, double[]> result = LBFGS.runLBFGS(
  training.rdd(),
  new LogisticGradient(),
  new SquaredL2Updater(),
  numCorrections,
  convergenceTol,
  maxNumIterations,
  regParam,
  initialWeightsWithIntercept);
Vector weightsWithIntercept = result._1();
double[] loss = result._2();

LogisticRegressionModel model = new LogisticRegressionModel(
  Vectors.dense(Arrays.copyOf(weightsWithIntercept.toArray(), weightsWithIntercept.size() - 1)),
  (weightsWithIntercept.toArray())[weightsWithIntercept.size() - 1]);

// Clear the default threshold.
model.clearThreshold();

// Compute raw scores on the test set.
JavaPairRDD<Object, Object> scoreAndLabels = test.mapToPair(p ->
  new Tuple2<>(model.predict(p.features()), p.label()));

// Get evaluation metrics.
BinaryClassificationMetrics metrics =
  new BinaryClassificationMetrics(scoreAndLabels.rdd());
double auROC = metrics.areaUnderROC();

System.out.println("Loss of each step in training process");
for (double l : loss) {
  System.out.println(l);
}
System.out.println("Area under ROC = " + auROC);
Spark リポジトリの "examples/src/main/java/org/apache/spark/examples/mllib/JavaLBFGSExample.java" に完全なサンプルコードがあります。

開発者向けメモ

ヘッセ行列は以前の勾配評価から近似的に構築されるため、最適化プロセス中に目的関数を変更することはできません。そのため、Stochastic L-BFGS は miniBatch を使用するだけではうまく機能しません。そのため、より良い理解が得られるまでは、これを提供しません。

Updater クラスは、もともと勾配降下用に設計されたクラスであり、実際の勾配降下ステップを計算します。ただし、適応ステップサイズなどの勾配降下専用のロジック部分を無視することで、L-BFGS の正則化の目的関数の勾配と損失を取得できます。後で正則化とステップ更新のロジックを分離するために、これをリファクタリングして Updater を正則化子に置き換えます。