解决格式为
的优化问题的最简单的方法是梯度下降。这种一阶优化方法(包括梯度下降及其随机变量)非常适合于大规模分布式计算。梯度下降方法旨在通过迭代,沿最陡下降的方向迭代地获得函数的局部最小值,该最陡下降的方向是当前点处的函数的导数(称为梯度)的负值,即当前参数值 。
如果目标函数f在所有参数上都不可微分,但仍然是凸的,则子梯度是梯度的自然泛化,并且承担步骤方向的作用。 在任何情况下,计算f的梯度或子梯度的成本是很高的 - 它需要完整的遍历完整的数据集,以便计算所有损失项的权重。
将目标函数f写为和的优化问题特别适合于使用随机梯度下降(SGD)求解。 在我们的例子中,是在监督机器学习中常用的优化方案。
(1)
这是很正常的,因为损失是作为每个数据点的个人损失的平均值得出的。
随机子梯度是一个向量的随机选择,使得在预期中,我们获得了原始目标函数的真实子梯度。 随机抽取一个数据点
,我们得到关于w的(1)的随机子梯度,如下:
其中
是由第i个数据点确定的损失函数的一部分的子梯度,即 。 此外, 是正则化器 的子梯度。不依赖于选择哪个随机数据点。 显然,期望 的随机选择。 我们有 是原始目标f的子梯度,即是 。
运行SGD现在只是走向负随机子梯度f'w的方向 ,即
Step-size(步长): 参数 是步长,在默认实现中,选择与迭代计数器的平方根相减,即 在第t次迭代中,输入参数 s= stepSize。
请注意,选择SGD方法的最佳步长通常在实践中是微妙的,并且是积极研究的主题。
Gradients(梯度):在spark.mllib中实现的机器学习方法的(子)梯度表在分类和回归部分可用。
Proximal Updates(更新近端):作为在步进方向上仅使用正则化器的子梯度R'(w)的替代方案,可以通过使用近端算子来获得一些改进的更新。 对于L1正则化器,近端运算符由软阈值给出,如L1Updater中实现的。
GradientDescent 中的SGD实现使用数据示例的简单(分布式)抽样。 我们记得优化问题 (1)
的损失部分是 ,因此 将是真(子)梯度。 由于这将需要访问完整的数据集,参数miniBatchFraction指定要使用的完整数据的哪一部分。 该子集上的梯度的平均值,即:
是随机梯度。 这里SS是大小 | S | = miniBatchFraction⋅n 的采样子集。
在每次迭代中,通过分布式数据集(RDD) 的采样以及每个工作机器的部分结果的总和的计算由标准火花程序执行。
如果将小分数分数的分数设置为1(默认值),则每次迭代中生成的步骤都是精确(子)梯度下降。 在这种情况下,在使用的步骤方向上没有随机性和无变化。 另一方面,如果选择非常小的miniBatchFraction,使得仅对一个点进行采样,即 | S | = miniBatchFraction⋅n=1,则算法等同于标准SGD。 在这种情况下,步长方向取决于点的均匀随机抽样。
L-BFGS 是用于解决 形式的优化问题的准牛顿法中的优化算法。 L-BFGS方法将本地目标函数近似为二次,而不用评估目标函数的第二偏导数来构造Hessian矩阵。 Hessian矩阵由先前的梯度评估近似,因此在牛顿方法中明确计算Hessian矩阵时,没有垂直可伸缩性问题(训练特征的数量)。 因此,与其他一阶优化相比,L-BFGS经常实现rapider融合。
线性方法在内部使用优化,而spark.mllib中的一些线性方法支持SGD和L-BFGS。 根据目标函数的属性,不同的优化方法可以有不同的收敛保证,我们无法涵盖这里的文献。 一般来说,当L-BFGS可用时,我们建议使用它代替SGD,因为L-BFGS趋向于更快地收敛(以较少的迭代)。
包括作为MLlib中的低级原函数的随机子梯度下降(SGD)的梯度下降方法,其中开发各种ML算法,参见线性方法部分。
SGD类GradientDescent可以设置以下参数:
L-BFGS目前只是MLlib中的一个低级优化原语。 如果要在各种ML算法(如线性回归和逻辑回归)中使用L-BFGS,则必须将目标函数的渐变和更新器传递给优化器,而不是使用诸如LogisticRegressionWithSGD之类的培训API。 参见下面的例子。 将在下一个版本中解决。
使用L1Updater的L1正则化将不起作用,因为L1Updater中的软阈值逻辑被设计用于梯度下降。 请参阅开发人员的说明。
L-BFGS方法LBFGS.runLBFGS具有以下参数:
返回是包含两个元素的元组。 第一个元素是包含每个要素权重的列矩阵,第二个元素是包含为每次迭代计算的损失的数组。
这是使用L-BFGS优化器来训练二元逻辑回归与L2正则化的一个例子。
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("Area under ROC = " + auROC)
有关API的详细信息,请参阅 LBFGS
Scala docs 和 SquaredL2Updater
Scala docs 。
由于Hessian近似来自先前的梯度评估,所以在优化过程中不能改变目标函数。 结果,随机L-BFGS不会通过使用miniBatch天真地工作; 因此,直到我们有了更深入的了解,我们才不提供这个。
Updater是一个最初设计用于梯度的类,它计算实际的梯度下降步长。 然而,我们可以忽略L-BFGS正则化的目标函数的梯度和损失,忽略仅适用于梯度的逻辑部分,例如自适应步长的东西。 我们将把它重构为正则化程序,以替换更新程序,以便稍后在正则化和步骤更新之间分离逻辑。