整理人：郑琦鸿，厦门大学信息学院 计算机技术专业
weChat: zqh821493671
主要内容
2. 支持向量机(下)
2.3 软间隔最大化
2.3.1 线性支持向量机
2.3.2 学习的对偶算法
2.4 序列最小最优化算法
2.4.1 SMO算法及求解
2.5 SVM的损失函数解释
2.6 核函数的简要介绍
2.6.1 核技巧与常见核函数
3. 逻辑斯蒂回归(上)
3.1 模型
3.2 决策边界
3.3 MLE和代价函数
3.4 参数求解
2.支持向量机（下）
2.3 软间隔最大化
上一讲我们给大家介绍了支持向量机应对线性可分数据时的算法，很显然它对于线性不可分数据不在适用了，那么这一讲将会为大家介绍如何通过硬间隔过渡到软间隔来应对线性不可分问题。怎么才能将它扩展到线性不可分问题呢？这就需要修改硬间隔最大化中的一些约束条件了。
2.3.1 线性支持向量机
回顾上一讲中的内容，我们知道对于线性可分的情况（上图的左侧），硬间隔最大化的结果是我们可以找到这样一个最大间隔，它将正负样本完美的区分开来，且这个间隔为
这样的样本都比较“乖巧”,但现实情况下总有一些比较“淘气”的样本它跨越了这条“红线”（线性不可分），我们用
✓ 当
✓ 当
✓ 当
✓ 当
✓ 当
通过以上的分析，我们知道线性不可分意味着某些样本点(xi,yi)不在满足函数间隔大于等于1的约束条件。为了解决这个问题，可以对每个样本点(xi,yi)引进一个松弛变量ξi≥0，使函数间隔加上松弛变量大于等于1。这样约束条件变为
通过上面的约束，我们依然能够找到最大间隔，只不过我们也允许SVM犯错，使得一部分样本进入到间隔内部，同时保证这样的样本最少，而对于绝大多数样本来说被这个最大间隔完美的区分开了。
因此，可以和训练数据集线性可分时一样来考虑训练数据集线性不可分的线性支持向量机学习问题。相应于硬间隔最大化，它称为软间隔最大化。
线性不可分的线性支持向量机的学习问题变成如下凸二次规划问题：
其中最小化项比起硬间隔最大化多了
以及相应的分类决策函数
称为线性支持向量机。
2.3.2 学习的对偶算法
同硬间隔最大化一样，软间隔最大化也有相应的对偶算法，原始最优化问题的拉格朗日函数是
对偶问题是拉格朗日函数的极大极小问题。首先求该L函数对w,b,ξ 的极小，由
得
将上式带入拉格朗日函数，得
再对
求α的极大，即得对偶问题：
通过对约束条件进行变换，最终对偶问题是：
设
原始问题是凸二次规划问题，解满足KKT条件，即得
由
得
再由
若存在α*的一个分量α*j,0<α*j<c，则：
那么可求得
最终分类决策函数可写为：
2.4 序列最小最优化算法
好了，当目前为止，我们已经能够很从容的面对数据了，无论它是线性可分还是不可分的情况。当来了一批数据之后，你按照上面的给出的算法，首先列出它的最小化式，然后是各种需要满足的条件，当数据量很小的时候，还不算麻烦，当数据量增大到一定量级之后，你发现情况开始不受控制，不等式越写越多，就算是写起程序来也相当繁琐，这个时候就轮到序列最小最优化算法（sequential minimal optimization，SMO）出场了。
支持向量机的学习问题可以形式化为求解凸二次规划问题。这样的凸二次规划问题具有全局最优解，并且有许多最优化算法可以用于这一问题的求解。当训练样本容量很大时，我们需要一些快速实现算法来提高支持向量机的效率。
2.4.1 SMO算法及求解
SMO算法要解如下凸二次规划的对偶问题：
SMO算法是一种启发式算法，其基本思路是：如果所有变量的解都满足此最优化问题的KKT条件，那么这个最优化问题的解就得到了。整个SMO算法包括两个部分：求解两个变量二次规划的解析方法和选择变量的启发式方法。下面给出SMO算法的具体步骤：
（1）取初值
（2）选取优化变量
（3）若在精度
其中，
则转（3）；否则令k=k+1，转（2）；
（4）取
2.5 SVM的损失函数解释
经过之前的介绍，相信大家已经对SVM有所体会了，但了解的还是比较表面，通过感官直觉我们知道要想取得比较好的分类效果，只需要间隔最大化就好了，但作为一种算法，若是能够从损失函数的角度来描述这种间隔最大化的优化策略，那么理解的也许会更加深入。
那么SVM的损失函数长什么样呢？大概就是下面这样：
然而，线性支持向量机原始最优化问题是：
你可能会有疑问，这两者等价吗？事实上它是等价的。
首先我们令：
其中下标“+”表示以下取正值的函数。例如：
也就是说，当样本点被正确分类且函数间隔
因为形似“合页”，因此也称为合页损失（或铰链损失，hinge loss）。之前我们在介绍感知机的时候，有这样一个对比：
这有什么区别吗？我们把它俩的损失函数都画出来：
其中绿线表示SVM的损失函数，紫线表示感知机的损失函数，当
ok，介绍完合页损失，我们接着从上面的SVM损失来说：
接着变形：
当
2.6 核函数的简要介绍
设
使得对所有的x,z
则称K(x,z)为核函数，
下面通过一个简单的例子来说明核函数和映射函数的关系。
图示如下：
2.6.1 核技巧与常见核函数
其中
常见的核函数有：
当然，核函数也不是万能钥匙，并不是说你用了核函数之后，数据就一定线性可分了，这就要看看哪个更符合自己的数据分布特性。
1.多项式核函数（polynomial kernel function）
对应的支持向量机是一个p次多项式分类器。在此情形下，分类决策函数成为
2.高斯核函数（Gaussian kernel function）
对应的支持向量机是高斯径向基函数分类器。在此情形下，分类决策函数成为
3.字符串核函数
核函数不仅可以定义在欧式空间上，还可以定义在离散数据的集合上。比如，字符串核是定义在字符串集合上的核函数。字符串核函数在文本分类，信息检索，生物信息学等方面都有应用。
3.逻辑斯蒂回归（上）
3.1 模型
逻辑斯蒂回归是统计学习中的经典分类方法。最大熵是概率模型学习的一个准则，将其推广到分类问题得到最大熵模型。逻辑斯蒂回归模式与最大熵模型都属于对数线性模型。
逻辑斯蒂分布的定义：设X是连续随机变量，X服从逻辑斯蒂分布是指X具有下列分布函数和密度函数：
式中，
逻辑斯蒂分布的密度函数f(x)和分布函数F(x)的图形如下图。
分布函数属于逻辑斯蒂函数，其图形是一条S形曲线。该曲线以点
曲线在中心附近增长速度较快，在两端增长速度较慢。形状参数
二项逻辑斯蒂回归模型是一种分类模型，由条件概率分布
P(Y|X)表示，形式为参数化的逻辑斯蒂分布。这里的随机变量X取值为实数，随机变量Y取值为1或0。通过监督学习的方法来估计模型参数。条件概率分布：
将线性函数w*x转换为概率：
这时，线性函数的值越接近正无穷，概率值就越接近1；线性函数的值越接近负无穷，概率值就越接近0。
3.2 决策边界
模型：
决策规则：
决策边界：
3.3 MLE和代价函数
策略：
3.4 参数求解
算法：
