页面树结构

2017-07-25 Apache Spark 2.2.0 官方文档中文版发布 : http://spark.apachecn.org/docs/cn/2.2.0/


MachineLearning 优酷地址 : http://i.youku.com/apachecn

转至元数据结尾
转至元数据起始

Mathematical description(数学描述

Gradient descent(梯度下降)

解决格式为的优化问题的最简单的方法是梯度下降。这种一阶优化方法(包括梯度下降及其随机变量)非常适合于大规模分布式计算。

梯度下降方法旨在通过迭代,沿最陡下降的方向迭代地获得函数的局部最小值,该最陡下降的方向是当前点处的函数的导数(称为梯度)的负值,即当前参数值 。

如果目标函数f在所有参数上都不可微分,但仍然是凸的,则子梯度是梯度的自然泛化,并且承担步骤方向的作用。 在任何情况下,计算f的梯度或子梯度的成本是很高的 - 它需要完整的遍历完整的数据集,以便计算所有损失项的权重。

Stochastic gradient descent (SGD-随机梯度下降)

将目标函数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中实现的。

Update schemes for distributed SGD(分布式SGD更新方案)

GradientDescent 中的SGD实现使用数据示例的简单(分布式)抽样。 我们记得优化问题 (1) 的损失部分是,因此将是真(子)梯度。 由于这将需要访问完整的数据集,参数miniBatchFraction指定要使用的完整数据的哪一部分。 该子集上的梯度的平均值,即:

是随机梯度。 这里SS是大小 | S | = miniBatchFraction⋅n 的采样子集。
在每次迭代中,通过分布式数据集(RDD的采样以及每个工作机器的部分结果的总和的计算由标准火花程序执行。

如果将小分数分数的分数设置为1(默认值),则每次迭代中生成的步骤都是精确(子)梯度下降。 在这种情况下,在使用的步骤方向上没有随机性和无变化。 另一方面,如果选择非常小的miniBatchFraction,使得仅对一个点进行采样,即  | S | = miniBatchFraction⋅n=1,则算法等同于标准SGD。 在这种情况下,步长方向取决于点的均匀随机抽样。

Limited-memory BFGS (L-BFGS)

L-BFGS 是用于解决  形式的优化问题的准牛顿法中的优化算法。 L-BFGS方法将本地目标函数近似为二次,而不用评估目标函数的第二偏导数来构造Hessian矩阵。 Hessian矩阵由先前的梯度评估近似,因此在牛顿方法中明确计算Hessian矩阵时,没有垂直可伸缩性问题(训练特征的数量)。 因此,与其他一阶优化相比,L-BFGS经常实现rapider融合。

Choosing an Optimization Method(选择优化方法)

线性方法在内部使用优化,而spark.mllib中的一些线性方法支持SGD和L-BFGS。 根据目标函数的属性,不同的优化方法可以有不同的收敛保证,我们无法涵盖这里的文献。 一般来说,当L-BFGS可用时,我们建议使用它代替SGD,因为L-BFGS趋向于更快地收敛(以较少的迭代)。

 

在MLlib中的实现

Gradient descent and stochastic gradient descent(梯度下降和随机梯度下降)

包括作为MLlib中的低级原函数的随机子梯度下降(SGD)的梯度下降方法,其中开发各种ML算法,参见线性方法部分。

SGD类GradientDescent可以设置以下参数:

  • Gradient 渐变是计算正在优化的功能的随机梯度的类,即相对于单个训练示例,以当前参数值计算。 MLlib包括常见损失函数的梯度类,例如hinge, logistic, least-squares(最小二乘法)。梯度类将训练样本,其标签和当前参数值作为输入。
  • 更新器是对于给定的损耗部分的梯度,执行实际的梯度下降步骤,即更新每个迭代中的权重。更新者还负责从正规化部分执行更新。 MLlib包括没有正则化的情况的更新程序,以及L1和L2正则化程序。
  • stepSize是一个标量值,表示梯度下降的初始步长。 MLlib中的所有更新者都使用等于  的第t步的步长。
  • numIterations是要运行的迭代次数。
  • regParam是使用L1或L2正则化时的正则化参数。
  • miniBatchFraction是在每次迭代中采样的总数据的一部分,以计算梯度方向。
    • 采样仍然需要遍历整个RDD,因此减少miniBatchFraction可能无法加快优化。当梯度计算成本高时,用户将会看到最大的加速,因为只有选定的样本用于计算梯度。

L-BFGS

L-BFGS目前只是MLlib中的一个低级优化原语。 如果要在各种ML算法(如线性回归和逻辑回归)中使用L-BFGS,则必须将目标函数的渐变和更新器传递给优化器,而不是使用诸如LogisticRegressionWithSGD之类的培训API。 参见下面的例子。 将在下一个版本中解决。

使用L1Updater的L1正则化将不起作用,因为L1Updater中的软阈值逻辑被设计用于梯度下降。 请参阅开发人员的说明。

L-BFGS方法LBFGS.runLBFGS具有以下参数:

  • Gradient是一个类,它以当前参数值计算正在优化的目标函数的梯度,即相对于单个训练示例。 MLlib包括常见损失函数的梯度类,例如铰链,后勤,最小二乘法。梯度类将训练样本,其标签和当前参数值作为输入。
  • 更新器是一种计算L-BFGS正则化部分的目标函数的梯度和损耗的类。 MLlib包括没有正则化的情况的更新程序,以及L2正则化程序。
  • numCorrections是L-BFGS更新中使用的更正次数。建议10。
  • maxNumIterations是L-BFGS可以运行的最大迭代次数。
  • regParam是使用正则化时的正则化参数。
  • converTol控制当L-BFGS被认为收敛时仍然允许多少相对变化。这必须是非负的。较低的值较不容忍,因此通常会导致更多的迭代运行。该值考察了Breeze LBFGS中的平均改善度和梯度范数。

返回是包含两个元素的元组。 第一个元素是包含每个要素权重的列矩阵,第二个元素是包含为每次迭代计算的损失的数组。

这是使用L-BFGS优化器来训练二元逻辑回归与L2正则化的一个例子。

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("Area under ROC = " + auROC)

有关API的详细信息,请参阅  LBFGS Scala docs 和 SquaredL2Updater Scala docs 

在Spark repo中的“examples/src/main/scala/org/apache/spark/examples/mllib/LBFGSExample.scala”中查找完整示例代码。

Developer’s notes(开发者笔记)

由于Hessian近似来自先前的梯度评估,所以在优化过程中不能改变目标函数。 结果,随机L-BFGS不会通过使用miniBatch天真地工作; 因此,直到我们有了更深入的了解,我们才不提供这个。

Updater是一个最初设计用于梯度的类,它计算实际的梯度下降步长。 然而,我们可以忽略L-BFGS正则化的目标函数的梯度和损失,忽略仅适用于梯度的逻辑部分,例如自适应步长的东西。 我们将把它重构为正则化程序,以替换更新程序,以便稍后在正则化和步骤更新之间分离逻辑。

  • 无标签