机器学习中的数学基础

一、 线性回归与逻辑回归：

机器学习中的监督部分大多从样本数据开始，首先构建满足一定假设且逻辑合理、理论完备的“带参”假设函数，定义该假设函数下评价模型好坏的损失函数，然后代入样本使用迭代更新（牛顿或梯度下降法）或代数法（直接求解最优参数表达式），求解最小化损失函数下的参数取值，最终使用该假设函数预测新样本数值或类别。线性回归是最简单的机器学习算法，它最重要的假设是定义自变量x无误差（噪声），同时因变量y的误差e满足均值为0的正态分布，方差齐性，且与自变量无关，在此假设下构建线性假设函数，求解最小化时的参数向量a，最终利用对新输入特征作预测。但线性回归预测的结果是连续的，并不能解决监督学习中最普遍的分类问题。那有没有办法利用回归的思想来构建分类模型呢？答案是逻辑回归：使用logit变换的回归算法。其实算法本身很简单，无非是将样本数据代入后，再，最后根据g(z)的大小来决定类别归属，阈值通常取0.5。

仔细思考整个学习过程，有4个显而易见的问题：

1、为什么它是一个回归问题；

2、为什么要构建回归方程后才代入g(z)，即sigmoid函数；

3、为什么要使用g(z)而不使用别的；

4、为什么使用最大似然而不是最小二乘求解系数。

首先介绍广义线性模型对其概率函数的3个假设：（3）指数分布集中的参数，即满足回归条件。前3个问题，从理论上讲，线性回归模型认为误差项e服从均值为0的正态分布，因此，在给定x和时，因变量y也服从均值为的正态分布。逻辑回归模型假定y服从伯努利分布，两者均满足广义线性模型第一条假设。于是，将两者的概率密度函数写成指数分布集的形式并对应各部分，同时利用正态分布和伯努利分布的特点，前3个问题迎刃而解，具体可参考吴恩达广义线性模型部分的笔记。

直观上，逻辑回归建立的初衷是如何使用回归方法求解二分类问题，如何将无穷定义域上的x映射为y=1的概率，如何使得y属于正类时p(y|x)尽可能趋近于1，属于负类时趋近于0才是问题的关键。正巧sigmoid函数满足上述一切条件，仅此而已。

第4个问题，线性回归模型可以从最大似然的角度解释，只是它从误差项e服从0均值正态分布的假定出发，构建误差项的最大似然函数，同样可以得到与最小二乘法一模一样的最优解。而逻辑回归的目的是确定y的类别归属，属于二分类问题，因此就无法使用经典回归连续y的最小二乘法，改用最大似然或重新构建损失函数的方法了，最终发现又是殊途同归，求解同一个最优化问题。

需要注意的是，在逻辑回归中，由于sigmoid函数的特殊性，平方误差非凸，因此只能考虑其他的损失函数类型，即log误差，来构建损失函数。特别的，任何一个样本数据都可以通过添加其他特征或提升特征的幂次等提升特征维度的方式完美拟合，但这极易产生过拟合，模型范化能力丢失，俗称“维度诅咒”。因此，任何优雅的最优化问题都不应该仅仅是使误差最小化，还要考虑模型的范化能力，避免过拟合，所以损失函数通常会在基本误差函数的基础上添加一个正则化项。其中，L1正则化lasso，它有棱有角的凸集可以稀疏模型特征系数，即在参数估计的同时完成模型选择，但缺点在于无法直接得到解析解，只能通过数值迭代求解。L2正则化ridge则是刚好相反，它可以快速得到参数的解析解，但参数估计完成后还需要额外处理模型选择。

最后就是如何从逻辑回归的二分类问题扩展到多分类。通常可以使用one vs. one和one vs. rest方式来扩展。前者关注将多类别中的任意2类分开，而不管其他，再重复迭代；后者关心将1类从其他类别中分开，再反复处理。

二、 深入理解SVM：

机器学习理论中首先要明确一个方法的Big Ideas，正如在编程领域中先将算法思想可以用伪代码的方式描述出来一样，Big Ideas表示整个学习方法的Intuition，而数学仅仅是描述这种Intuition的工具而已。因此，机器学习中数学的作用在于，先要知道什么问题可以用数学解决并大致了解如何解决。

因为Garbage In, Garbage Out的古话，机器学习关注最多的一个问题就是如何预处理原始数据，将样本特征有效提取出来喂给模型。比如，神经网络模型就是利用卷积的方法优化了原始数据的特征表示。若某一种机器学习算法能比其他方法在某一类现实问题上有更强的表现，即Killer App，通常就会大受欢迎。在神经网络最热的时间里，能更有效解决手写识别问题的SVM横空出世。

监督学习和决策边界：不同的机器学习算法有各自不同的决策边界，即在特征空间中区分样本的方式不同。比如，决策树算法中通常选取与特征空间坐标轴平行的线面为决策边界，而KNN通常会以一个大致单调的线面区分。决策边界也大致奠定了学习模型背后的数学思路，所以SVM就新提出了一种决策边界的区分方式— 最大间隔！

假设在线性可分的样本空间中，如何定义模型对样本区分的优劣呢？以二维特征空间的二分类问题为例，SVM提出在分割线两侧，最接近的样本要离该分割线最远。即，分割线两侧存在这样一个阈值，阈值内无任何其他样本，同时该阈值越大越好。数学上表示为为正样本，为负样本。w表示与分割线垂直的法向量，u为特征空间中的坐标，b代表分割线上任意点在w方向上的投影，1为增强模型鲁棒性的归一化指标，算法目标就是求解w与b。

决策公式：上述两个最大间隔表示为，其中（y=1：正样本； y=-1：负样本）。所以，当 时，表示样本正好落在最大间隔上，即为最大间隔上的样本点。（请注意，这里并不一定是支持向量！）

目标函数：目标是最大间隔上样本点的投影差最大，即距离最远。投影差= ，其中w为与分割线垂直的法向量，u和u’分别为y=1和-1的最大间隔点。将决策公式代入投影差化简= 。因此，要使投影差最大，即|w|最小，考虑到凸函数与优化的方便性，最终的目标函数= 。

优化理论：最优化拉格朗日L=，分别求出w和b偏导=0的极值条件得： ，将其反代入L求得L’，因此原问题就转换为求解各自样本点所对应 的对偶问题，原问题的定义域是样本空间内的所有点，而可行域是最大间隔样本点。机器学习的意义之一就是拿着最优化的结论代入机器学习的目标中，有时会窥见某些专属于机器学习新世界里的东西。

比如这里：
1，L’中，表示在SVM里并不关心样本点x本身，而是关注不同样本点间的内积。2，将其代入到决策公式中，我们又发现，当新样本到来时，只需要将其与最大间隔上的样本点做内积再附上各自的权重系数求和，即可判断样本的类别，其中的权重系数为对应的，Duang！原来只要寥寥几个的支撑向量就能分类！此处的内积又被称作核函数，当我们拍脑袋将内积变换为新的核函数时，就变换成另外一种形式的决策边界，它或许可以有效解决其他问题，这就是核函数在SVM中大行其道的原因。SMO算法：由于原始求w和b的问题经L->L’，转变为的问题，它可以使用SMO算法求解。SMO本质上是一种“变化了的”梯度上升算法。传统梯度上升假设固定其他所有的，将且仅将当作变量，求解问题最优值，反复迭代直至所有的被解出。但由于L’限制条件为的特殊性，必须要保持两个和变化才能迭代求解！但需要特别注意的是，有时对于同一组支撑向量，会求出不唯一的，这是因为支撑向量样本的冗余，此时数据矩阵的秩小于样本个数，核矩阵也半正定，SMO算法输出的是第一个被找到的点，但好消息是，对SVM这类凸优化问题来说，由不同的反推出的w和b是唯一的，专门有一篇NIPS论文讨论了这个问题。与逻辑回归的关系：当SVM相对成熟以后，人们发现SVM与前文介绍的逻辑回归有一定关联。逻辑回归通常设定为阈值，但SVM认为，这还不够，必须在p=0.5对应的左右两侧再设置一个margin，使得当且仅当特别大时为正样本，特别小时为负样本。因此，从逻辑回归出发，又能推得SVM损失函数的另一种形式，俗称Hinge Loss。但本质上，它与上文所介绍的方法完全等价。总结：在大数据横行的今天，时间复杂度的SVM或许已不太重要，当数据量在3万以上时普通PC无法完成，但为何SVM仍然是研究机器学习的初学者都应该掌握的算法呢？

因为SVM仅仅根据“最大间隔”就将如此美妙的数学推导与机器学习理论完美的糅合在一起，实在让人叹为观止。