约束最优化:lagrange 对偶函数

学SVM的时候你会经常听到拉格朗日对偶。拉格朗日对偶是凸优化问题中比较常见的一个手段,关于凸优化,强烈建议Boyd的《凸优化》这本书,总结的很好

lagrange 对偶的基本思想,是将原目标函数,通过对其约束条件的加权求和,变成一个广义的目标函数。从而将一个M个变量N个约束的目标函数转换成一个M+N个变量的目标函数,再得到这个函数的对偶函数

这个对偶函数非常有用,因为他有几个重要性质:

  1. 无论原始问题是不是凸的,对偶问题一定是凸的,可以证明
  2. 对偶问题给出了原始问题的一个下界,可以证明
  3. 当满足一定条件时,对偶问题的解和原问题的解是等价的,可以证明

SVM 支持向量机

参考 mit 课程:https://web.mit.edu/6.034/wwwbob/svm.pdf

SVM 是机器学习领域非常流行的一个分类算法。他的前身其实就是感知机,想了解感知机原理的可以简单看我之前写的文章

传统感知机是有很多局限性的问题的,比如解决不了线性不可分的问题,比如泛化能力不强因为你可以找到N个解,但是不知道哪一个是最好的。SVM 就能很好的解决这些问题。

1. 支持向量

搞清楚什么是支持向量是了解SVM的前提。但是这里只能抽象的讲解,了解后面的内容,会加深你对支持向量的理解

在一个分类问题里,我们可能会有多个解,比如:

但是取哪个是最好的呢?直觉告诉我们,选能让样本分割的最远的超平面,这个就是 SVM 的做法,最大间隔化(后面会讲形式化的定义和推导)。SVM使用两个间隔最大的超平面,将所有数据完美分割在两边。

所以数学上,只需要一个超平面 + 间隔,就能形成一个决策边界,那些依附在决策边界上的点,就叫支持向量。为什么要给这些点起一个专有的名词?因为定义这个超平面只需要用到这些点,而其他远距离的点都是多余的。所以通常在一个2维空间上,最少只需要3个点,就能定义这个超平面


理解感知机模型

感知机是一种很传统和经典的分类算法了,现在机器学习的书基本上也很少详细讲了,大多还会简单介绍一下。看 ng 的机器学习课程,在讲 SVM 支持向量机的时候,从逻辑回归的代价函数直接修改到SVM的代价函数,实在难以理解,逻辑回归和SVM之间的关系和区别,还得好好想想

感知机模型有自身的局限性,它只能做线性分类。如果数据不是线性可分的,那还真没办法。但是了解感知机模型,对后面学习SVM很有帮助的

1. 感知机模型

感知机只能用来做线性分类,所谓线性分类是说,假设我们有一堆样本数据,我们必须找到一条线或者一个超平面,能把这堆样本划分到线的两边

preview

用数学的语言来说,如果我们有m个样本,每个样本对应于n维特征和一个二元类别输出,如下:


用 ReLU 整流单元逼近非线性神经网络

刚学习深度学习的时候,在网上曾经看过很多资料,始终搞不懂,为什么大家都说神经网络为什么能够无限逼近任意连续函数。大家普遍认为,理论上只要神经元足够多,神经网络足够大,就可以实现

后来知乎有个人写了偏文章解释了一下,有兴趣的可以移步这里:https://zhuanlan.zhihu.com/p/25590725

我困惑的根源在于:

  1. 神经网络说白了就是一个矩阵,神经元之间的链接就是各种矩阵运算
  2. 有很多激活函数是“线性”的,比如ReLU及其各种变种

当然,有些人认为ReLU是非线性激活函数,其实也没有错。但是我个人理解,叫分段线性函数,更合适一些。

那么问题来了,如果一个神经网络中,全部使用线性单元,无论经过多少次矩阵运算,最终训练出来的网络,不还是一个线性函数吗?