机器学习算法-第8章 万能分类器-支持向量机.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**本章主要内容：**\n",
    "* 支持向量机的理论基础  \n",
    "* SVM的数学推导  \n",
    "* SMO算法  \n",
    "* SVM中文文本分类  \n",
    "\n",
    "## 8.1 支持向量机的理论基础\n",
    "### 8.1.1 经验风险最优  \n",
    "在第6章，从第二代神经网络理论的视角看，线性不可分：就是为$n$维空间中的样本集找到一个分类曲面，让这个曲面能够根据标记的类别把样本点划分开。\n",
    "\n",
    "**总体**：研究对象的全体总和。（在统计学中，可以理解成一个概率分布）。   \n",
    "**总体样本**：从总体中，随机抽取若干有代表性的对象。（主观认为这些样本分布一定程度上与总体的分布是相同或相似的）。  \n",
    "**风险**：仍然需要衡量经验模型与真实模型之间的误差。  \n",
    "**经验风险**：当从训练集得到一个分类器之后，这个分类器是以经验模型的分布作为总体分布的，那么这个分类器的误差。 因为机器学习的算法较多，为了总和评估的方便，给这些误差函数起名叫**损失函数（Loss Function）**。 \n",
    "\n",
    "假设样本：$(x_1,y_1),\\dots,(x_n,y_n)\\in{R^n}\\times{R}$对于离散样本的经验函数可以写为： \n",
    "\n",
    "$$\n",
    "R_{emp}(\\alpha)=\\frac{1}{n}\\sum_{i=1}^n{L(y_i,{f(x_i,\\alpha)})}\n",
    "$$\n",
    "\n",
    "其中$R_{emp}(\\alpha)$就是所谓的经验风险。$f(x_i,\\alpha)$是用来最小化风险$R_{emp}(\\alpha)$的目标函数，$L(y_i,{f(x_i,\\alpha)})$就是损失函数，它表示对每个$x_i$，其标签$y_i$与目标函数$f(x_i,\\alpha)$之间的偏差。在$BP$神经网络中就是全局误差函数，在梯度下降法就是斜率和截距的变化等。\n",
    "\n",
    "**经验风险最小原则（Empirical Risk Minimizing,ERM）**：在第二代神经网络算法中，我们用最小化经验风险$R_{emp}(\\alpha)$来表示真实风险$R(\\alpha)$，即$min[R_{emp}[\\alpha]]$。   \n",
    "\n",
    "神经网络的主要思想在于把经验风险最小化作为衡量算法准确性的主要依据。  \n",
    "从梯度下降法开始一直到$RBF$网络，我们千方百计地要找到一个误差，通过迭代将这个误差函数收敛在尽可能小的范围内，或者说达到平稳的状态，一次使算法收敛到最优。\n",
    "\n",
    "但是一味追求损失函数的最小化并不总能达到全局最优的分类效果。很多在训练集上轻易达到百分之百的分类器，一旦遇到真实数据，计算结果却一塌糊涂。而且，过小的训练误差还会导致分类推广能力的下降，也就是常遇到的过拟合现象，导致过拟合的原因来自两个方面：   \n",
    "\n",
    "* 一是说明训练样本对总体的代表性不强，也就是说最小的经验风险并不一定意味着最小的真实（总体）风险。最小经验风险原则要求经验风险必须确实能够逼近真实风险才行，但实际上，根据概率论中的大数定理“当实验次数足够多时，事件出现的频率无穷接近于该事件发生的概率。”这里强调样本足够多，但是现实情况是，这一切取决于问题的特征和设计者的技巧，所以第二代神经网络左后成了建模技巧的比拼。这么做的一个恶果是，所建立的模型失去泛化能力。  \n",
    "* 二是说明学习算法理论还不完备。如果考虑真实（总体）风险，那么评估风险的方法不能只从样本入手，显而易见，现有的、单一的经验风险最小（ERM）理论存在很大的不足。\n",
    "\n",
    "认识到这个问题，人们很自然地将目光转向统计学习方法。人们希望利用统计学习找到一种方法衡量样本所表达的规律（分类器）与总体规律之间的差距，这也就是所谓学习一致性的问题。于是统计学习理论发展起来了。  \n",
    "\n",
    "### 8.1.2 关键定理与VC维  \n",
    "\n",
    "统计学习理论诞生于20世纪60年代，那时代表人物有Vladimir N.Vapnik，…………\n",
    "直到机器学习（特别是神经网络）遇到上述的困难，统计学习理论才脱颖而出。\n",
    "\n",
    "统计学习的第一个定义就是解决经验风险和真实风险的衡量问题，在此称为学习一致性的定义。  \n",
    "\n",
    "设$Q(x,\\alpha)$是对给定的独立同分布观测$x_1,\\dots,x_n$（样本），是经验风险$R_{emp}=\\frac{1}{n}\\sum_{i=1}^{n}Q(x_i,\\alpha)$最小化函数。如果下面两个序列依概率$P$收敛于同一个极限，即$R(\\alpha_{n})\\to^{n\\to{\\infty}}inf_{\\alpha\\in\\land}R(\\alpha),R_{emp}(\\alpha_{n})\\to^{n\\to{\\infty}}inf_{\\alpha\\in\\land}R(\\alpha)$   \n",
    "\n",
    "则ERM原则对函数集$Q(x,\\alpha),\\alpha\\in\\land$,概率分布函数$F(x)$是一致的。其中inf表示函数的下确界，$R(\\alpha_n)$表示真实（期望）风险。上面定义是说，对于一个基于ERM原则的算法，如果它提供一个函数序列$Q(x,\\alpha_n),n=1,2,\\cdots$,这个序列能使真实风险和经验风险都收敛于$R(\\alpha)$的下确界，那么就说此ERM算法符合学习一致性。我们可以近似地认为$R_{emp}(\\alpha)$的极限就是$R(\\alpha)$的下确界。\n",
    "\n",
    "从学习一致性的角度看，当样本数目趋近于无穷大时（大数定理），最小的经验风险一定能够收敛于最小的真实风险。只有满足这一条件，才能够保证在经验风险最小下取得最优结果能够代表真实风险的最有结果，如图所示\n",
    "\n",
    "<img src=\"https://pic4.zhimg.com/80/v2-eee1acdca79cdc1364be8a5a1224c057_hd.jpg\",width=400,height=400>\n",
    "\n",
    "\n",
    "进一步，Vapnik还给出学习理论的关键定理。 \n",
    "\n",
    "设函数集$Q(z,\\alpha),\\alpha\\in\\land$,满足条件$A\\leq|Q(z,\\alpha)dF(z)\\leq{B},A\\leq{R(\\alpha)}\\leq{B}$,那么，ERM原则一致性的充要条件是：经验风险$R_{emp}(\\alpha)$在如下意义上一直收敛于实际风险$R(\\alpha)$:  \n",
    "$$\\lim_{n\\to\\infty}P\\{sup_{\\alpha}(R(\\alpha)-R_{emp}(\\alpha))>\\varepsilon\\}=0,\\forall\\varepsilon>0$$\n",
    "\n",
    "其中$P$表示概率，$sup$表示函数的上确界。   \n",
    "\n",
    "由于这个定理在统计学习中的重要性，因而它被称为学习理论的关键定理。关键定理把学习的一致性问题转化为一个收敛问题。它没有用经验风险去逼近真实（期望）风险，而是通过经验风险最小化函数来逼近真实（期望）风险最小化函数。这就是关键定理的绝妙之处。这样，我们在经验风险和真实风险之间建立了一座桥梁，即经验风险最小化原则符合学习过程一致性的条件是，$Q(z,\\alpha)$函数集中最差的那个函数。   \n",
    "\n",
    "如何找到这个最差的函数呢？关键定理没有给出方法，但是提供了对$Q(z,\\alpha)$的一个度量方法，这就是VC维。  \n",
    "\n",
    "VC维是20世纪60年代由Vapnik和Chervonenkis共同提出的，现在已经成为统计学习理论中的核心概念。  \n",
    "\n",
    ">**VC维定义**：假设存在一个有$h$个样本集能被一个函数集中的函数按照所有可能的$2^h$种形式分为两类，则此函数集能够把样本数为$h$的样本集打散。也就是说，如果存在$h$个样本的样本集能够把函数集打散，而不存在$h+1$个样本能被打散，则函数集的VC维就是$h$。   \n",
    "\n",
    "为了理解这个例子，举例如下：假设二维空间中一个指示函数集$I$（只有两类输出$y=\\{0,1\\}$），空间中有$n$个点（不共线），我们想用这个指示函数集分隔这$n$个点，问最大能分开的点数是多少？很显然，1和2能完全被分开。再来看3个点（不共线）的情况，共会出现8种分法，如图\n",
    "\n",
    "<img src=\"https://pic3.zhimg.com/80/v2-e69e2005457ef36e8a213c1a321b761b_hd.jpg\",width=400,height=400>\n",
    "\n",
    "$I$可以将3个点完全分开，这种完全分开被称为打散。我们继续让它打散4个点。如图：\n",
    "\n",
    "<img src=\"https://pic4.zhimg.com/80/v2-98baf69d3df007fba2f7b951b3472f9c_hd.jpg\",width=260,height=260>\n",
    "\n",
    "\n",
    "图中遇到问题了，因为出现了异或的情况，$I$无法打散空间4个点。那么二维空间的指示函数集$I$的VC维就是3.\n",
    "\n",
    "\n",
    "VC维的一个重要意义在于使人们重新判定线性可分与线性不可分的问题，并提供了衡量的依据。一个数据集如果是线性可分的，它的维度就是样本空间的维度$d$；如果不是线性可分的，对于线性分类器（含指示函数），它的维度至少等于其VC维$h=d+1$。因此不难理解函数集的VC维越大，其非线性的程度越高，学习机器就越复杂。但是，除了一些特殊的函数，现在还咩有一个通用的方法来确定所有的学习机器的VC维，例如，非线性神经网络的VC维都很难确定。\n",
    "\n",
    "\n",
    "\n",
    "#### VC的理解\n",
    "\n",
    "在机器学习里我们常常看到这样的说法：一般而言, VC 维 越大, 学习能力就越强,学习也越复杂；可以通过 VC 维 计算学习风险的上界。但进一步对VC维的介绍却不多，例如，VC维是什么？如何计算VC维？\n",
    "我们认为2维线性分类器的VC维为3，而不是4。即，2维线性分类器可以打散集合大小为3的样本集合，不能打散有4个样本的集合。\n",
    "\n",
    "#### 1.集合大小为3的样本集合。  \n",
    "\n",
    "1. 当3个点不在一条直线上时。3个点任意点被标为任意类别（o或X）都存在一条直线可以将两类打散（分开），如下图。此时满足VC维的定义，即有$2^3=8$种标记方式都能被打散。\n",
    "\n",
    "<img src=\"https://img-blog.csdn.net/20161019213132110?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQv/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/Center\">\n",
    "\n",
    "2. 3点一线时，有两种情况不能被打散。如下图：\n",
    "<img src=\"https://img-blog.csdn.net/20161019213540428?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQv/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/Center\">\n",
    "\n",
    "\n",
    "#### 2.集合大小为4的样本集合\n",
    "\n",
    "无论4个点在一天直线上还是不在一条直线上（任意位置），都找不到一种情况能对$2^4=16$种标注进行打散。因为总存在类似如下的一种标注存在这16种标注中，此种标注方式是不能被2维线性分类器所打散的。所以他不能满足VC维的要求。\n",
    "\n",
    "<img src=\"https://img-blog.csdn.net/20161019213755845?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQv/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/Center\",width=250,height=250>\n",
    "\n",
    "总结，所以从上面可以看出，集合大小为3的样本集合是存在满足VC维条件的样本（只要存在就行，不要求所有的样本集合都要满足条件，例如3点一线就不满足）。而不存在大小为4的样本集合（注意：任意4个点就是一个大小为4的样本集合。同理于大小H个样本的集合）满足条件。所以说对于2D线性分类器的VC维为3。另外，$N$维 实数空间中线性分类器和线性实函数的VC维是n+1。对一些特殊的函数我们也明确知道其VC维，但并不是所有的。对于任意函数目前还没有很好的指导性方法来计算其VC维。\n",
    "\n",
    "如果某函数的VC维无穷大，也就意味着，任意多个点无论怎样标注都能将其打散。例如$sin(ax)$。它可以将任意多样本的任意标注情况精确分开，即在训练集上达到100%的分类正确率。\n",
    "\n",
    "\n",
    "\n",
    "### 8.1.3 结构风险最优\n",
    "\n",
    "有了VC维，就可以衡量经验风险和实际风险的构成。统计学习理论系统地研究了各类函数集的泛化边界，得出如下定理:\n",
    "\n",
    "**定理**：对于指示函数集$f(x,\\alpha)$，如果损失函数$Q(z,\\alpha)=L(y,f(z,\\alpha))$的取值为0或1，对所有函数，则经验风险和实际风险之间至少以概率$1-\\eta$满足如下关系：   \n",
    "\n",
    "$$\n",
    "R(\\alpha)\\leq{R_{emp}(\\alpha)}+\\sqrt{\\Big(\\frac{h(ln(2n/h)+1)-ln(\\eta/4)}{n}\\Big)}\n",
    "$$   \n",
    "\n",
    "\n",
    "其中$n$是样本数，$h$是机器学习的VC维，$0\\leq\\eta\\leq1$。   \n",
    "\n",
    "很明显，该定理说明在经验风险最小化的原则下，总体的真实风险由两部分组成：  \n",
    "\n",
    "$$\n",
    "R(\\alpha)\\leq{R_{emp}{(\\alpha)}+\\Phi(n/h)}\n",
    "$$\n",
    "\n",
    "第一部分$R_{emp}(\\alpha)$使我们已经熟悉的经验风险，而第二部分$\\Phi(n/h)$被称作置信区间。首先，置信区间受$1-\\eta$的影响（置信水平），同时还是函数集的VC维$h$和训练样本数$n$的函数，函数曲线受$h$、$n$的影响而单调递减。其中给出$\\leq$表示真实风险与经验风险差距的上界，它们反映了根据经验风险最小化原则得到的学习机器的推广能力，也被称为推广能力的界。   \n",
    "\n",
    "长期的研究告诉我们，根据这个函数，如果VC维与样本数的比值$n/h<20$，则这样的样本集被称为小样本。进一步的分析发现，当$n/h$较小时，置信区间较大，用经验风险近似真实风险时就有较大的误差，因此，使用经验风险最小化得到的最优解具有较差的推广能力；如果样本数目较多，当$n/h$较大时，则置信区间就会缩小，经验风险最小化的最优解就更可能接近实际的最优解。  \n",
    "\n",
    "另一方面，对于某类特定问题，我们固定样本数$n$，如果VC维越高，即说明学习机器的复杂性越高，置信区间就越大，导致真实风险与经验风险之间的差距也越大。因此，在设计学习机器时，不但要使经验风险最小化，还要使VC维尽量小，从而缩小置信区间，使实际风险最小。本质上，对于神经网络，我们选择学习模型和设计网络的过程就是优化置信区间的过程。   \n",
    "\n",
    "有了推广能力界的概念，我们就可以凭此寻找策略，如图：\n",
    "\n",
    "\n",
    "\n",
    "<img src=\"https://pic3.zhimg.com/v2-381c782c967f243981460902a9853fbc_b.jpg\",width=300,height=300>\n",
    "\n",
    "定义函数$Q(z,\\alpha),\\alpha\\in\\land$的集合$S$具有一定的结构，这一结构是由一系列嵌套的函数子集$S_k=\\{Q(z,\\alpha),\\alpha\\in\\land_{k}\\}$组成的。它们满足$S_1\\subset{S_2}\\subset\\dots{S_k}$，其中结构中的元素满足下面两个性质。   \n",
    "\n",
    "（1） 每个函数集$S_k$的VC维$h_k$是有限的，因此，$h_1\\leq{h_2}\\leq\\dots{h_3}$。   \n",
    "（2） 结构的任何元素$S_k$包含一个完全有界函数的集合$0\\leq{Q(z,\\alpha)\\leq{B_k}},\\alpha\\in\\land_k$。\n",
    "\n",
    "这样在同一个子集中置信区间相同，可以在每一个子集中寻找最小经验风险。选择最小化经验风险与置信区间之和最小的子集，就可以达到期望风险的最小。这个子集中使经验风险最小的函数就是说要求的最优函数。这种思想称作结构风险最小化原则（Structure Risk Minimization），简称SRM原则。  \n",
    "\n",
    "\n",
    "对于一个给定的观测集$z_1,\\dots,z_n$，SRM原则在保证风险最小化的子集$S_k$中选择使经验风险最小的函数$Q(z,\\alpha_n)$。SRM原则定义了给定样本的经验风险逼近实际风险的精度和逼近函数集的复杂性之间的一种折中。随着子集序号的增加，经验风险的最小值减少，但决定置信范围的项却增加。SRM原则通过选择子集$S_k$将这两者都考虑在内，最小化经验风险得到了实际的最好的界。  \n",
    "\n",
    "在函数子集$S^*$中，数据逼近的精度和逼近函数的复杂性之间取得了一种最佳折中，如图所示。这时模型有最好的推广能力。结构风险最小化原则为我们提供了一种不同于经验风险最小化的更科学的学习机器设计原则。但是，由于这个原则的实现并不容易，这里的关键是如何构造函数的子集结构。然而，构造函数子集结构的方法到目前无一般性理论。  \n",
    "\n",
    "\n",
    "<img src=\"https://pic3.zhimg.com/80/v2-09429b3343a61c9e5687f153a4eaea76_hd.jpg\",width=300,height=300>    \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "## SVM的数学推导\n",
    "\n",
    "支持向量机是在统计学习理论的VC维理论和结构风险最小化原理基础上发展起来的一种新的机器学习方法。它具有理论严密、适应性强、全局优化、训练效率高和泛化性能好的优点，可非常成功地处理机器学习分类问题。本节主要介绍支持向量机的数学推导。  \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}