【机器学习】次梯度(subgradient)方法 |
您所在的位置:网站首页 › 可微如何计算 › 【机器学习】次梯度(subgradient)方法 |
次梯度方法(subgradient method)是传统的梯度下降方法的拓展,用来处理不可导的凸函数。它的优势是比传统方法处理问题范围大,劣势是算法收敛速度慢。但是,由于它对不可导函数有很好的处理方法,所以学习它还是很有必要的。 次导数设f:I→R是一个实变量凸函数,定义在实数轴上的开区间内。这种函数不一定是处处可导的,例如最经典的例子就是 凸函数f:I→R在点x0的次导数,是实数c使得: 原导数计算公式为: 对该定义略作解释: 按照上面次导数对定义方式,次导数c应满足条件: 对于函数 很容易就可以得出: 接下来给出正宗的计算定义: 对于所有I内的x。我们可以证明,在点x0的次导数的集合是一个非空闭区间[a, b],其中a和b是单侧极限 它们一定存在,且满足a ≤ b。 所有次导数的集合 例如:考虑凸函数 到这里,我们总算是搞清楚次导数和次微分是什么东西了。 将次导数和次微分的概念推广到多元函数,就可以得到次梯度了。如果f:U→ R是一个实变量凸函数,定义在欧几里得空间 所有次梯度的集合称为次微分,记为 此记法与前面的次导数记法极为相似。我们用更为常见的记法来定义次梯度: 次梯度(Subgradient)与梯度的概念类似,凸函数的First-order characterization(一阶特征描述)是指如果函数f可微,那么当且仅当 其中,函数 很明显,凸函数的次梯度一定存在,如果函数 左一图为 左二图为 同样,绝对值函数 对于最大值函数而言,其在满足 同理,我们还可以给出在高维情形下次微分(subdifferential)的定义,即: 次微分是闭合且为凸集; 如果函数 凸函数的次微分不为空,但非凸函数则不一定。 次梯度的性质Scalingf(数乘不变性): Addition(加法不变性): Affine composition(仿射特性):如果 Finite pointwise maximum(有限最大值):如果 在开头已经粗略的阐述了次梯度方法的使用情景,在这里在详细的复述一遍。 对于光滑的凸函数而言,我们可以直接采用梯度下降算法求解函数的极值,但是当函数不处处光滑、处处可微的时候,梯度下降就不适合应用了。因此,我们需要计算函数的次梯度。对于次梯度而言,其没有要求函数是否光滑,是否是凸函数,限定条件很少,所以适用范围更广。 次梯度具有以下优化条件(subgradient optimality condition):对于任意函数 即,当且仅当0属于函数 这与之前所描述的次导数的性质相符合。 证明: 证明很简单,当次梯度 介绍完前面的基础知识,终于要开始介绍算法了~ 经典梯度下降算法实际上是利用负梯度总是指向最小值点这一性质,然后每次迭代 次梯度算法(Subgradient method)与梯度下降算法类似,仅仅用次梯度代替梯度,即: 其中, 与梯度下降算法不同的地方在于,次梯度算法并不是下降算法,每次对于参数的更新并不能保证代价函数是呈单调递减的趋势,因此,一般情况下我们选择: 另一点与梯度下降算法不同的是:次梯度算法没有明确的步长选择方法,类似Exact line search和Backtracking line search的方法,只有步长选择准则,具体如下: Fixed step sizes:Diminishing step sizes方法主要是保证步长逐渐变小,同时,变化幅度还不会特别快。这里需要注意的是,次梯度算法并不像梯度下降一样,可以在每一次迭代过程中自适应的计算此次步长(adaptively computed),而是事先设定好的(pre-specified)。 但是,很多人会提出这样一个问题,如果你不能保证次梯度是单调的,如何保证最后可以收敛? 定理:如果
lipschitz条件:
在高维情形下: 证明: 对于 因为, 对于任意 因为, 如果令
所以,我们可以得到 同时,因为函数满足Lipschitz continuous with G,所以, 综上所述,我们可以证明下式成立: 其中 当 此时,如果我们想要获得 因此,次梯度的收敛速度为 不妨设 1).步长和不可消时(Non-summable diminishing step size):
2).Constant step size:
A. Regularized Logistic Regression 对于逻辑回归的代价函数可记为: 明显,上式是光滑且凸的,而regularized problem则是指优化目标函数为: 如果 下图是对于同样数据集下分别对逻辑回归选用岭惩罚和Lasso惩罚求解最优解的实验结果图(n=1000,p=20n=1000,p=20): B. 随机次梯度算法 上面讲到的次梯度算法梯度更新定义为: 随机次梯度算法(Stochastic Subgradient Method)与次梯度算法(Subgradient Method)相比,每次更新次梯度是根据某一个样本计算获得,而不是通过所有样本更新次梯度,其定义为: 其中, 所以,根据梯度更新的方式不同,次梯度算法和梯度下降算法一般被称为“batch method”。从计算量来讲, 对于随机更新次梯度,一般随机的方式有两种: Cyclic rule:选择与所有优化算法一样,随机次梯度算法能否收敛? 答案是肯定的,这里就不在做证明,有兴趣的同学可以参考boyd教授的论文,这里仅给出收敛结果,如下: 对于Cyclic rule,随机次梯度算法的收敛速度为 下图给出梯度下降和随机梯度下降算法在同一数据下迭代结果: 随机梯度下降一般有两个特性: 通常下降的速度较batch方法要快。通常在最优点附近会来回震荡,相较于batch方法不够稳定。
参考文章: 凸优化-次梯度算法 优化中的subgradient方法 次导数 次梯度 小结 次梯度(Subgradient) 次梯度 |
CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |