v1.3-SNAPSHOT
优化
数学公式
FlinkML 中的优化框架是一个面向开发人员的包，这个包可以解决机器学习任务中经常遇到的优化问题。在谈论监督式学习时，这涉及找到一个模型，用一组参数 $w$ 定义，该模型能够在给定一组 $(\x, y)$ 例子的情况下最小化 $f(\wv)$，这里$\x$是一个特征向量，而 $y$ 是一个表征一个回归模型的实数值或分类模型的类别标签的实数。在监督式学习中，需要被最小化的函数通常是以下形式：
\begin{equation} \label{eq:objectiveFunc} f(\wv) := \frac1n \sum_{i=1}^n L(\wv;\x_i,y_i) + \lambda\, R(\wv) \ . \end{equation}
这里 $L$ 是损失函数，而$R(\wv)$是正则化惩罚 (regularization penalty)。我们使用 $L$ 来衡量一个模型对观察数据的拟合有多好，并且我们使用 $R$ 来影响对一个模型的复杂度损失 (complexity cost)，其中 $\lambda > 0$ 是正则化惩罚。
损失函数
在监督式学习中，我们用损失函数来衡量模型的拟合程度，损失函数通过对比模型做出的预测 $p$ 和每个实例的真值 $y$ 来惩罚错误。不同的损失函数可以被回归任务 (比如平方损失) 和分类任务 (比如转折点损失(hinge loss))。
常用的损失函数有：
- 平方损失: $ \frac{1}{2} \left(\wv^T \cdot \x - y\right)^2, \quad y \in \R $
- 转折点损失: $ \max \left(0, 1 - y ~ \wv^T \cdot \x\right), \quad y \in {-1, +1} $
- 逻辑损失: $ \log\left(1+\exp\left( -y ~ \wv^T \cdot \x\right)\right), \quad y \in {-1, +1}$
正则化类型
机器学习中的[正则化] (https://en.wikipedia.org/wiki/Regularization_(mathematics)) 会惩罚需要被评价的模型，为了减少过拟合，最常见的惩罚是 $L_1$ 和 $L_2$ 惩罚，定义如下：
- $L_1$: $R(\wv) = \norm{\wv}_1$
- $L_2$: $R(\wv) = \frac{1}{2}\norm{\wv}_2^2$
$L_2$ 惩罚会惩罚大权重，比起含若干大权重的解决方法，它更倾向含更多小权重的解决方案。 $L_1$ 惩罚能用来归零解决方案中的系数 (solution coefficients)，所以会产生稀疏的解决方案。 $\eqref{eq:objectiveFunc}$ 中的正则化常数 $\lambda$ 决定了用在模型上的正则化数量，该常数经常通过交叉验证模型决定。 关于比较好的正则化类型的对比，可以参阅这篇由 Andrew Ng 发表的论文 至于什么样的正则化类型会被支持，取决于实际使用的优化算法。
随机梯度下降 (Stochastic Gradient Descent)
为了找到一个 (局部) 最小值，梯度下降法会朝着与当前参数 (权重) 相关 $\eqref{eq:objectiveFunc}$ 函数的梯度相反的方向的下降。 为了计算精确的梯度，我们需要对一个数据集里的所有点进行一次传递 (one pass)，让整个过程的计算量增大。 另一个替代的方案是随机梯度下降，在随机梯度下降中我们每一轮迭代都从完整的数据集中采集一个点，并通过在线方式对每个点更新参数。
在小批次的随机梯度下降中，我们则从一个数据集中采样随机数据集，并在每一批次上计算梯度。在算法的每一轮迭代中我们根据从每一个批次中计算得到的梯度，对权重只更新一次。
一个重要的参数是学习率 $\eta$，或者称为步长 (step size)，该参数可由以下列出的五个方法之一决定。 初始步长的设定会对算法的表现有重要的影响。如果想要知道一些实际运用中的指导，清参与 Leon Botou 的 “Stochastic Gradient Descent Tricks“。
目前随机梯度下降的实现使用所有的分区，这样能让一批次的梯度下降变更加有效。只要一个采集操作被引入到 Flink 中，真实的小批次随机梯度下降算法就会被执行。
参数
随机梯度下降的实现可以由以下参数控制：
| 参数 | 描述 |
|---|---|
| 正则化惩罚 |
要应用的正则化方程. (默认值: NoRegularization) |
| 正则化常数 |
使用的正则化量. (默认值: 0.1) |
| 损失函数 |
要被优化的损失函数. (默认值: None) |
| 迭代数 |
最大迭代次数. (默认值: 10) |
| 学习率 |
梯度下降法中的初始学习率. 这个值控制了梯度下降法要沿着梯度的反方向移多远. (默认值: 0.1) |
| 聚合阀值 |
当被设置时，如果目标函数 $\eqref{eq:objectiveFunc}$ 的值的相对变化量小于提供的阀值 $\tau$，则迭代停止 聚合的标准定义如下：$\left| \frac{f(\wv)_{i-1} - f(\wv)_i}{f(\wv)_{i-1}}\right| < \tau$. (默认值: None) |
| 学习率方法 |
(默认值: LearningRateMethod.Default) |
| 衰退值 |
(默认值: 0.0) |
正则化
FlinkML 支持含 L1, L2 和无正则化的随机梯度下降。正则化类型必须实现 RegularizationPenalty 接口，该接口根据梯度和正则化类型计算新的权重。
下表包含了支持的正则化函数。
| 类别名称 | 正则化函数 $R(\wv)$ |
|---|---|
| 无正则化 | $R(\wv) = 0$ |
| L1正则化 | $R(\wv) = \norm{\wv}_1$ |
| L2正则化 | $R(\wv) = \frac{1}{2}\norm{\wv}_2^2$ |
损失函数
需要被最小化的损失函数需要实现 LossFunction 接口，该接口定义了计算损失及其梯度的方法。
任何一个定义了自己 LossFunction 或使用 GenericLossFunction 类会从一个偏损失函数和一个预测函数构造损失函数。
以下是一个实例：
val lossFunction = GenericLossFunction(SquaredLoss, LinearPrediction)支持的偏损失函数请参阅此处. 支持的预测函数请参阅here.
偏随机函数 (Partial Loss Function) 值
| 函数名 | 描述 | 损失 | 损失导数 |
|---|---|---|---|
| 平方损失 |
回归任务中最常用的损失函数. |
$\frac{1}{2} (\wv^T \cdot \x - y)^2$ | $\wv^T \cdot \x - y$ |
| 逻辑损失 |
分类任务中最常用的损失函数. |
$\log\left(1+\exp\left( -y ~ \wv^T \cdot \x\right)\right), \quad y \in \{-1, +1\}$ | $\frac{-y}{1+\exp\left(y ~ \wv^T \cdot \x\right)}$ |
| 转折点损失 |
可用于分类任务的损失函数. |
$\max \left(0, 1 - y ~ \wv^T \cdot \x\right), \quad y \in \{-1, +1\}$ | $\begin{cases} -y&\text{if } y ~ \wv^T <= 1 \\ 0&\text{if } y ~ \wv^T > 1 \end{cases}$ |
预测函数值
| 函数名 | 描述 | 预测 | 预测梯度 |
|---|---|---|---|
| 线性预测 |
线性模型比如线性回归和线性分类最常用的函数. |
$\x^T \cdot \wv$ | $\x$ |
有效学习率
这里:
-
$j$ 是迭代数
-
$\eta_j$ 是每一步 $j$ 的步长
-
$\eta_0$ 是初始学习率
-
$\lambda$ 是正则化常量
-
$\tau$ 是衰退常量, 该常量会使得学习率变成一个递减函数 $j$，也就是说，随着迭代次数的增加，学习率会衰减。衰减的精准率是由函数特定的，请参阅 反缩放 (Inverse Scaling) ** 和 Wei Xu 方法 (Wei Xu’s Method)** (该方法是 反缩放 方法的一个延伸)。
| 函数名 | 描述 | 函数 | 称呼为 |
|---|---|---|---|
| 默认 |
决定步长的默认方法。该方法相当于当 $\tau$ = 0.5 时的 inverse scaling 方法。默认保留该特殊情况来为保持向后兼容性. |
$\eta_j = \eta_0/\sqrt{j}$ | LearningRateMethod.Default |
| 常数 |
步长在整个学习任务中保持不变. |
$\eta_j = \eta_0$ | LearningRateMethod.Constant |
| Leon Bottou 方法 |
这是 sklearn 中 |
$\eta_j = 1 / (\lambda \cdot (t_0 + j -1)) $ | LearningRateMethod.Bottou |
| 反缩放 |
一个决定步长的非常常用的方法. |
$\eta_j = \eta_0 / j^{\tau}$ | LearningRateMethod.InvScaling |
| Wei Xu 方法 |
由 Wei Xu 在 Towards Optimal One Pass Large Scale Learning with Averaged Stochastic Gradient Descent 的方法 |
$\eta_j = \eta_0 \cdot (1+ \lambda \cdot \eta_0 \cdot j)^{-\tau} $ | LearningRateMethod.Xu |
例子
在随机梯度下降的 Flink 实现中，假如在一个 DataSet[LabeledVector] 给定一组实例，并选择性地给定一些初始初始权重，我们可以使用 GradientDescent.optimize() 来找到给定数据的最优权重。
用户能提供一个包含 WeightVector 元素的初始的 DataSet[WeightVector]，或者使用所有集合均为0的默认权重。
一个 WeightVector 就是一个含权重的容器类 (container class)，这个类把截距从权重向量中分离出来。这允许我们避免把正则化运用到截距上。
// 创建一个随机梯度下降实例
val sgd = GradientDescent()
.setLossFunction(SquaredLoss())
.setRegularizationPenalty(L1Regularization)
.setRegularizationConstant(0.2)
.setIterations(100)
.setLearningRate(0.01)
.setLearningRateMethod(LearningRateMethod.Xu(-0.75))
// 获取数据
val trainingDS: DataSet[LabeledVector] = ...
// 根据所提供的数据优化权重
val weightDS = sgd.optimize(trainingDS)