机器学习（二十一）——Optimizer, 单分类SVM&多分类SVM, 时间序列分析

antkillerfarm

17537人浏览 · 2017-06-19 10:01:46

antkillerfarm · 2017-06-19 10:01:46 发布

http://antkillerfarm.github.io/

Optimizer

在《机器学习（一）》中，我们已经指出梯度下降是解决凸优化问题的一般方法。而如何更有效率的梯度下降，就是本节中Optimizer的责任了。

Momentum

Momentum是梯度下降法中一种常用的加速技术。其公式为：

v t = γ v t - 1 + η \nabla θ J (θ)

$v_t = \gamma v_{t-1} + \eta \nabla_\theta J( \theta)$

θ = θ - v t

$\theta = \theta - v_t$

从上式可以看出，参数的更新值 $v_t$ ，不仅取决于当前梯度 $\nabla_\theta J( \theta)$ ，还取决于上一刻的速度 $v_{t-1}$ 。

Nesterov accelerated gradient

该方法是Momentum的一个变种。其公式为：

v t = γ v t - 1 + η \nabla θ J (θ - γ v t - 1)

$v_t = \gamma v_{t-1} + \eta \nabla_\theta J( \theta - \gamma v_{t-1})$

θ = θ - v t

$\theta = \theta - v_t$

Adagrad

Momentum算法中所有的参数 $\theta$ 都使用同一个学习率，而Adagrad采用了另一种方法进行优化：为每个参数确定不同的学习率。

Adagrad的基本思想：给经常更新的参数一个较小的学习率，而给很少更新的参数一个较大的学习率。

其公式为：

g t, i = \nabla θ J (θ i)

$g_{t, i} = \nabla_\theta J( \theta_i )$

θ t + 1, i = θ t, i - η G t , i i + ϵ - - - - - - - \sqrt \cdot g t, i

$\theta_{t+1, i} = \theta_{t, i} - \dfrac{\eta}{\sqrt{G_{t, ii} + \epsilon}} \cdot g_{t, i}$

其中， $G_{t, ii}$ 表示参数 $\theta_i$ 梯度平方和的历史累积值， $\epsilon$ 是为了防止分母为0，而加入的平滑项，数量级一般为 $10^{-8}$ 。

有趣的是，如果去掉上式中的根号，则其效果会变糟。

Adagrad的优点在于：它是一个自适应算法，初值选择显得不太重要了。

Adagrad的缺点在于：训练越往后，G越大，从而学习率越小。如果在训练完成之前，学习率变为0，就会导致提前结束训练。

Adadelta

为了克服Adagrad的缺点，Matthew D. Zeiler于2012年提出了Adadelta算法。

该算法不再使用历史累积值，而是只取最近的w个状态，这样就不会让梯度被惩罚至0。

为了避免保存前w个状态的梯度平方和，可做如下变换：

E [g 2] t = γ E [g 2] t - 1 + (1 - γ) g 2 t

$E[g^2]_t = \gamma E[g^2]_{t-1} + (1 - \gamma) g^2_t$

θ t + 1 = θ t - η E [ g 2 ] t + ϵ - - - - - - - - \sqrt g t

$\theta_{t+1} = \theta_{t} - \dfrac{\eta}{\sqrt{E[g^2]_t + \epsilon}} g_{t}$

上边的公式，就是Hinton在同一年提出的RMSprop算法。其中的 $\gamma E[g^2]_{t-1}$ 即可看作是前w个状态的滤波值，也可看作是Momentum算法中动量值。

Adadelta在RMSprop的基础上更进一步：

R M S [g] t = E [g 2] t + ϵ - - - - - - - - \sqrt

$RMS[g]_{t}=\sqrt{E[g^{2}]_{t}+\epsilon }$

Δ θ t = - R M S [ Δ θ ] t - 1 R M S [ g ] t g t

$\Delta \theta_t = - \dfrac{RMS[\Delta \theta]_{t-1}}{RMS[g]_{t}} g_{t}$

也就是说，Adadelta不仅考虑了梯度的平方和，也考虑了更新量的平方和。

Adam

Adaptive Moment Estimation借用了卡尔曼滤波的思想，对 $g_t,g_t^2$ 进行滤波：

m t = β 1 m t - 1 + (1 - β 1) g t

$m_t = \beta_1 m_{t-1} + (1 - \beta_1) g_t$

v t = β 2 v t - 1 + (1 - β 2) g 2 t

$v_t = \beta_2 v_{t-1} + (1 - \beta_2) g_t^2$

估计：

m^t = m t 1 - β t 1

$\hat{m}_t = \dfrac{m_t}{1 - \beta^t_1}$

v^t = v t 1 - β t 2

$\hat{v}_t = \dfrac{v_t}{1 - \beta^t_2}$

更新：

θ t + 1 = θ t - η v ^ t - - \sqrt + ϵ m^t

$\theta_{t+1} = \theta_{t} - \dfrac{\eta}{\sqrt{\hat{v}_t} + \epsilon} \hat{m}_t$

参考

http://sebastianruder.com/optimizing-gradient-descent/

An overview of gradient descent optimization algorithms

https://morvanzhou.github.io/tutorials/machine-learning/ML-intro/3-06-speed-up-learning/

加速神经网络训练

http://www.cnblogs.com/neopenx/p/4768388.html

自适应学习率调整：AdaDelta

单分类SVM&多分类SVM

原始的SVM主要用于二分类，然而稍加变化，也可用于单分类和多分类。

单分类SVM

单分类任务是一类特殊的分类任务。在该任务中，大多数样本只有positive一类标签，而其他样本则笼统的划为另一类。

单分类SVM（也叫Support Vector Domain Description(SVDD)）是一种单分类算法。和普通SVM相比，它不再使用maximum margin了，因为这里并没有两类的data。

单分类SVM的目标，实际上是确定positive样本的boundary。boundary之外的数据，会被分为另一类。这实际上就是一种异常检测的算法了。它主要适用于negative样本的特征不容易确定的场景。

这里写图片描述

这里可以假设最好的boundary要远离feature space中的原点。左边是在original space中的boundary，可以看到有很多的boundary都符合要求，但是比较靠谱的是找一个比较紧（closeness）的boundary（红色的）。这个目标转换到feature space就是找一个离原点比较远的boundary，同样是红色的直线。

当然这些约束条件都是人为加上去的，你可以按照你自己的需要采取相应的约束条件。比如让data的中心离原点最远。

下面我们讨论一下SVDD的算法实现。

首先定义需要最小化的目标函数：

min s . t . F (R, a, ξ i) = R 2 + C \sum i = 1 N ξ i (x i - a) T (x i - a) \leq R 2 + ξ i, ξ i \geq 0

$\begin{align} &\operatorname{min}& & F(R,a,\xi_i) = R^2 + C \sum_{i=1}^N \xi_i\\ &\operatorname{s.t.}& & (x_i - a)^T (x_i - a) \leq R^2 + \xi_i\text{,} \qquad \xi_i \geq 0 \end{align}$

这里a表示形状的中心，R表示半径，C和 $\xi$ 的含义与普通SVM相同。

Lagrangian算子：

L (R, a, α i, ξ i) = R 2 + C \sum i = 1 N ξ i - \sum i = 1 N γ i ξ i - \sum i = 1 N α i (R 2 + ξ i - (x i - c) T (x i - c))

$L(R,a,\alpha_i,\xi_i) = R^2 + C \sum_{i=1}^N \xi_i - \sum_{i=1}^N \gamma_i \xi_i - \sum_{i=1}^N \alpha_i \left( R^2 + \xi_i - (x_i - c)^T (x_i - c) \right)$

对偶问题：

L = \sum i = 1 N α i (x T i \cdot x i) - \sum i, j = 1 N α i α j (x T i \cdot x i)

$L = \sum_{i=1}^N \alpha_i (x_i^T \cdot x_i) - \sum_{i,j=1}^N \alpha_i \alpha_j (x_i^T \cdot x_i)$

使用核函数：

L = \sum i = 1 N α i K (x i, x i) - \sum i, j = 1 N α i α j K (x i, x j)

$L = \sum_{i=1}^N \alpha_i K(x_i,x_i) - \sum_{i,j=1}^N \alpha_i \alpha_j K(x_i,x_j)$

预测函数：

y (x) = \sum i = 1 N α i K (x, x n) + b

$y(x) = \sum_{i=1}^N \alpha_i K(x,x_n) + b$

根据计算结果的符号，来判定是正常样本，还是异常样本。

参考：

https://www.projectrhea.org/rhea/index.php/One_class_svm

One-Class Support Vector Machines for Anomaly Detection

https://www.zhihu.com/question/22365729

什么是一类支持向量机（one class SVM）

多分类SVM

多分类任务除了使用多分类算法之外，也可以通过对两分类算法的组合来实施多分类。常用的方法有两种：one-against-rest和DAG SVM。

one-against-rest

比如我们有5个类别，第一次就把类别1的样本定为正样本，其余2，3，4，5的样本合起来定为负样本，这样得到一个两类分类器，它能够指出一篇文章是还是不是第1类的；第二次我们把类别2的样本定为正样本，把1，3，4，5的样本合起来定为负样本，得到一个分类器，如此下去，我们可以得到5个这样的两类分类器（总是和类别的数目一致）。

但有时也会出现两种很尴尬的情况，例如拿一篇文章问了一圈，每一个分类器都说它是属于它那一类的，或者每一个分类器都说它不是它那一类的，前者叫分类重叠现象，后者叫不可分类现象。

分类重叠倒还好办，随便选一个结果都不至于太离谱，或者看看这篇文章到各个超平面的距离，哪个远就判给哪个。不可分类现象就着实难办了，只能把它分给第6个类别了……

更要命的是，本来各个类别的样本数目是差不多的，但“其余”的那一类样本数总是要数倍于正类（因为它是除正类以外其他类别的样本之和嘛），这就人为的造成了“数据集偏斜”问题。

DAG SVM

这里写图片描述

DAG SVM（也称one-against-one）的分类思路如上图所示。

粗看起来DAG SVM的分类次数远超one-against-rest，然而由于每次分类都只使用了部分数据，因此，DAG SVM的计算量反而更小。

其次，DAG SVM的误差上限有理论保障，而one-against-rest则不然（准确率可能降为0）。

显然，上面提到的两种方法，不仅可用于SVM，也适用于其他二分类算法。

参考：

http://www.blogjava.net/zhenandaci/archive/2009/03/26/262113.html

将SVM用于多类分类

时间序列分析

书籍和教程

http://www.stat.berkeley.edu/~bartlett/courses/153-fall2010/

berkeley的时间序列分析课程

http://people.duke.edu/%7Ernau/411home.htm

回归和时间序列分析

《应用时间序列分析》，王燕著。

概述

时间序列，就是按时间顺序排列的，随时间变化的数据序列。

生活中各领域各行业太多时间序列的数据了，销售额，顾客数，访问量，股价，油价，GDP，气温…

随机过程的特征有均值、方差、协方差等。

如果随机过程的特征随着时间变化，则此过程是非平稳的；相反，如果随机过程的特征不随时间而变化，就称此过程是平稳的。

下图所示，左边非稳定，右边稳定。

这里写图片描述

非平稳时间序列分析时，若导致非平稳的原因是确定的，可以用的方法主要有趋势拟合模型、季节调整模型、移动平均、指数平滑等方法。

若导致非平稳的原因是随机的，方法主要有ARIMA及自回归条件异方差模型等。

ARIMA

ARIMA模型全称为差分自回归移动平均模型(Autoregressive Integrated Moving Average Model,简记ARIMA)，也叫求和自回归移动平均模型，是由George Edward Pelham Box和Gwilym Meirion Jenkins于70年代初提出的一著名时间序列预测方法，所以又称为box-jenkins模型、博克思-詹金斯法。