第1章-统计学习方法概论.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 第1章 统计学习方法概论"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 1.1 统计学习"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 一. 统计学习的特点"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__统计学习__: 是关于计算机基于数据构建概率统计模型并运用模型对数据进行预测与分析的一门学科。\n",
    "\n",
    "* 基于数据: data；\n",
    "* 构建概率模型: model；\n",
    "* 预测: prediction；\n",
    "\n",
    "__学习__：如果一个系统能够通过执行某个过程改进它的性能，这就是学习。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 二. 统计学习的对象"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "数据。\n",
    "\n",
    "统计学习对于数据的__重要假设__: 同类数据具有一定的统计规律性。\n",
    "* pattern；\n",
    "* 没有pattern，学习没有意义。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 三. 统计学习的目的"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "预测与分析。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 四. 统计学习的方法"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "监督学习的方法：\n",
    "\n",
    "* 从给定的、有限的、用于学习的训练数据集合出发，且假设数据是独立同分布产生的；\n",
    "* 假设要学习的模型属于某个函数的集合——假设空间；\n",
    "* 选定某个评价准则；\n",
    "* 选择或设计某个算法；\n",
    "* 运用该算法从假设空间中选取一个最优的模型——使它对已知训练数据和未知测试数据在给定的评价准则下有最优的预测。\n",
    "\n",
    "由此，有统计学习方法的三要素：\n",
    "* 模型(model): 假设空间就是模型的集合；\n",
    "* 策略(strategy): 模型选择的准则(具体而言，两层error measurement: 单个数据的损失函数and整个训练集的损失函数，后者可能包括添加项，如正则项)；\n",
    "* 算法(algorithm): 求解最优模型的算法。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 五. 统计学习的研究"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "三个维度的研究：\n",
    "\n",
    "* 统计学习方法：方法的开发；\n",
    "* 统计学习理论：探究方法的有效性；\n",
    "* 统计学习应用：应用于实际问题。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 1.2 监督学习"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> __监督学习__：学习一个模型，使得该模型能够对任意给定的输入，对其相应的输出做一个好的预测。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 一. 基本概念"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__输入__: X，看做随机变量；具体取某个值用小写x。\n",
    "\n",
    "__输出__: Y，看做随机变量；具体取某个值用小写y。\n",
    "\n",
    "__输入空间__: “输入”所有可能的取值的集合。\n",
    "\n",
    "__输出空间__: “输出”所有可能的取值的集合。\n",
    "\n",
    "__实例__: 每个具体的“输入”，通常用__特征向量__表示(所有的__特征向量__的集合被称为__特征空间__)。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "注意，有时输入空间和特征空间是一个空间，但是有时不是——如原始数据需要进行特征转换，那么输入空间就是原始数据的空间，所有的经过转换后的数据则构成的是特征空间。模型都是定义在特征空间上的。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "对于一个数据集，我们将其样本容量记做$N$，将特征数量记做$n$。\n",
    "\n",
    "第$i$个实例记做：$x_i=(x_i^{(1)},x_i^{(2)},\\cdots,x_i^{(n)})^T$\n",
    "\n",
    "训练集：$T=\\{(x_1,y_1),(x_2,y_2),\\cdots,(x_N,y_N)\\}$\n",
    "\n",
    "__样本点__: 输入输出对。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "监督学习：\n",
    "\n",
    "* 回归问题：输入输出变量都为连续变量；\n",
    "* 分类问题：输入变量为连续变量，输出变量为离散变量。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "==============联合概率分布================"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__输入X和输出Y遵循联合概率分布$P(X,Y)$__。这里，我们仅假定该分布存在，但未知。\n",
    "\n",
    "训练数据和测试数据，都是依照这个概率分布，独立同分布产生的。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "==============假设空间================"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "监督学习的模型的实质：输入到输出的映射。\n",
    "\n",
    "__假设空间__: 一些表示输入到输出映射的函数的集合，表明了学习的范围(在哪里挑模型)。\n",
    "\n",
    "监督学习的模型：\n",
    "\n",
    "* 概率模型：由条件概率分布$P(Y|X)$表示；\n",
    "* 非概率模型：由决策函数$Y=f(X)$表示。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 二. 问题形式化"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "监督学习 = 学习+预测。\n",
    "\n",
    "* 学得的模型，我们记做$\\hat{P}(Y|X)$或$Y=\\hat{f}(X)$；\n",
    "* 预测的过程：对于给定的测试样本$x_{N+1}$，模型输出$y_{N+1}$：\n",
    "    * 概率模型：$y_{N+1}=\\hat{f}(x_{N+1})$\n",
    "    * 非概率模型：$y_{N+1}=\\mathop{argmax}\\limits_{y_{N+1}}\\hat{P}(y_{N+1}|x_{N+1})$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 1.3 统计学习三要素"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> 统计学习方法 = 模型+策略+算法"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 一. 模型"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "学习时的所有模型被包含在我们选择的__假设空间__中，一般有__无穷多个__。例如：__线性模型__，所有线性函数的集合。我们可以用如下的方法表示假设空间：\n",
    "\n",
    "* $\\mathcal{F}=\\{f\\ |\\ Y=f_\\theta(X), \\theta \\in \\textbf{R}^n\\}$\n",
    "* $\\mathcal{F}=\\{P\\ |\\ P_\\theta(Y|X), \\theta \\in \\textbf{R}^n\\}$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 二. 策略"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 1. 损失函数, 风险函数, 经验风险"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "即__评价准则__。模型一次预测的好坏用__损失函数__度量，模型平均意义下的预测好坏用__风险函数__度量。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__损失函数__：是预测值$f(X)$和真实值$Y$的非负实函数，度量一次预测的好坏，记做$L(Y,f(X))$。常用的损失函数有：\n",
    "\n",
    "* 0-1损失函数：$L(Y,f(X))=I(Y\\ne f(X))$\n",
    "* 平方损失函数：$L(Y,f(X))=(Y-f(X))^2$\n",
    "* 绝对损失函数：$L(Y,f(X))=|Y-f(X)|$\n",
    "* 对数损失函数：$L(Y,P(X|Y))=-log(P(Y|X))$\n",
    "\n",
    "风险函数是损失函数的期望值，度量的模型平均意义上的好坏(泛化能力)：\n",
    "\n",
    "$$R(f) = E[L] = \\int_{\\mathcal{X}×\\mathcal{Y}}L(y,f(x))P(x,y)dxdy$$\n",
    "\n",
    "所以，我们的终极目标是，从假设空间中选出风险函数最小的模型来。但是，我们并不知道分布$P$，所以这个问题暂时看似无解。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "现在我们来关注某一个模型在训练集上的表现。给定训练集$T$，模型$f(X)$在其上的平均表现(平均损失)为__经验风险__：\n",
    "\n",
    "$$\\hat{R}_{emp}(f)=\\frac{1}{N}\\sum_{i=1}^NL(y_i,f(x_i))$$\n",
    "\n",
    "容易证明，__经验风险的期望就是风险函数__。当样本数量趋于无限大的时候，经验风险无限趋近于风险函数。但是现实中，我们手头的样本的容量是有限的，甚至是很少的。\n",
    "\n",
    "因此，直接使用经验风险代替风险函数进行估测，有一定的危险性。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 2. 经验风险最小化, 结构风险最小化"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "在假设空间$\\mathcal{F}$、损失函数$L$、训练集$T$确定的情况下，经验风险$\\hat{R}$便可以确定。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__经验风险最小化策略(ERM)__认为，经验风险最小的模型就是最佳的模型。依照这一策略，最佳模型为求解：\n",
    "\n",
    "$$\\mathop{min}\\limits_{f\\in \\mathcal{F}}\\frac{1}{N}\\sum_{i=1}^N L(y_i,f(x_i))$$\n",
    "\n",
    "该策略在样本容量足够大的时候，能够保证有不错的学习效果——当模型是__条件概率分布__，损失函数是__对数损失函数__的时候，ERM等价于__极大似然估计__。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "但样本容量不足的时候，ERM的效果不是很好，会出现__过拟合(overfitting)__。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "另一种思考方式：\n",
    "\n",
    "* 当目标函数(target function, 或target distribution, 概念) $c \\in \\mathcal{F}$的时候，如果$\\mathcal{F}$中有唯一一个经验风险为0的hypothesis，那么这个hypothesis一定就是$c$——__然而，在有限样本下，我们往往会得到许多个经验风险为0的hypothesis，此时无法进一步分辨__；\n",
    "* $c \\notin \\mathcal{F}$的时候，我们必须意识到，我们拿不到完美的hypothesis，我们只能拿到足够好的，也就是风险函数最小的；但在样本量不够大的情况下，经验风险不一定趋近于风险函数，因此经验风险为0的hypothesis不一定风险函数也趋近于0——__目标函数是线性模型，但是由于噪声，我们拿到了一个类似二次曲线生成的数据集，我们用复杂的假设空间，可能会得到一个二次函数模型，这个模型的经验风险是0，但是可想而知风险函数是很大的__；\n",
    "* 综上，由于不确定性，经验风险最小化不是100%靠谱的。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "因此，出现了另一种策略——__结构风险最小化测策略(SRM)__：这种策略就是为了防止过拟合而发明的。\n",
    "\n",
    "SRM等价于__正则化(regularization)__，将最小化__结构风险__。\n",
    "\n",
    "__结构风险__在经验风险后加上了一个__正则项(regularizer，又称为惩罚项，penalty)__：\n",
    "\n",
    "$$\\hat{R}_{srm}(f)=\\frac{1}{N}\\sum_{i=1}^NL(y_i,f(x_i))+\\lambda J(f)$$\n",
    "\n",
    "结构风险小的模型往往对训练集和未知数据都有较好的预测，即泛化能力更好。\n",
    "\n",
    "因此，SRM就是最小化结构风险：\n",
    "\n",
    "$$\\mathop{min}\\limits_{f\\in \\mathcal{F}}\\frac{1}{N}\\sum_{i=1}^N L(y_i,f(x_i))+\\lambda J(f)$$\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 三. 算法"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "上面，我们将统计学习问题转化为了最优化问题，__算法就是求解最优化问题的方法__。\n",
    "\n",
    "如果原最优化问题有解析解(Analytic Solution)，如线性回归，则最优化问题很简单。\n",
    "\n",
    "但往往没有解析解，需要运用__数值计算__的方法求解——如何__有效率地快速找到全局最优解__是关键。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 1.4 模型评估与模型选择"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 一. 训练误差与测试误差"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__训练误差__，即training error，就是模型在训练集上的经验风险：\n",
    "\n",
    "$$E_{train} = \\frac{1}{N}\\sum_{i=1}^NL(y_i,f(x_i))$$\n",
    "\n",
    "$N$为训练集容量。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__测试误差__，即test error，就是模型在测试集上的平均损失：\n",
    "\n",
    "$$E_{test} = \\frac{1}{N'}\\sum_{i=1}^{N'}L(y_i,f(x_i))$$\n",
    "\n",
    "$N'$为测试集容量。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "后者体现了模型的__泛化能力__，是真正的重要。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 二. 过拟合与模型选择"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "如果一味地提高对训练集的拟合程度，所选的模型的复杂度往往会比真的模型更高，导致$E_{in}$很小，但$E_{out}$很大，模型的泛化能力很差，这样的现象就是过拟合。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "图：x轴为模型复杂度，y轴为$E$，即error——随着模型复杂度的上升，$E_{in}$在不断减小接近于0，$E_{out}$先减小后增大。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 1.5 正则化与交叉验证"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 一. 正则化"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "正则化项可以是参数向量的：\n",
    "\n",
    "* $L_2$范数：$\\Vert w \\Vert_2$，向量各元素平方和的平方根——每个元素都很小，都接近于0；\n",
    "* $L_1$范数：$\\Vert w \\Vert_1$，向量各元素的绝对值之和————稀疏向量。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "正则项的添加，可以在最小化经验误差的同时，使得模型不是那么的复杂，防止过拟合。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 二. 交叉验证"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "原始想法：将训练集划分为：\n",
    "\n",
    "* 训练集，training set——训练模型；\n",
    "* 验证集，validation set——选择模型；\n",
    "* 测试集，test set——评估模型。\n",
    "\n",
    "但这样存在的问题：一次验证，波动可能比较大——能不能多次验证取平均？——交叉验证。\n",
    "\n",
    "__K-fold交叉验证__：将训练集分成K个互不相交的大小相同的子集，每次取其中1个作为验证集，其他K-1个作为训练集，用训练出的模型在测试集上验证得到$E_{val}$；就这样重复K次，得到K个$E_{val}$，最后求其平均值，作为该模型的验证误差。\n",
    "\n",
    "其中，$N-fold$交叉验证是一种极端情况，也就是每次只留一个样本数据作为验证数据，所以又叫做__Leave-one-out cross validation(留一交叉验证)__；适用于数据缺乏的情况。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 1.6 泛化能力"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 一. 泛化误差"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__泛化误差__其实就是上面所提到的__风险函数__，也就是$E_{out}$——但是是一个学习方法学习到的某个模型的风险函数，即$E_{out}(g)$。因此，泛化误差反映的是一个学习方法的泛化能力。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 二. 泛化误差上界"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__学习方法__的泛化能力，是指由该方法学习到的模型($g$)对未知数据的预测能力，往往是通过研究泛化误差的__概率上界__进行的——__泛化误差上界__，性质如下：\n",
    "\n",
    "* 是样本容量N的函数：N越大，泛化上界越趋于0；\n",
    "* 是假设空间容量的函数：假设空间容量越大，泛化误差上界越大。\n",
    "\n",
    "更具体一些，对于一个学习方法，它选出的$g$，其$E_{out}$能被$E_{in}$加某个__上界__bound住——这个上界就是上面所说的泛化误差上界。泛化误差上界越紧，该学习方法越好。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "考虑一个__二元分类__问题。假设现在的假设空间由有限个函数构成，即：$\\mathcal{F}=\\{f_1,f_2,\\cdots,f_d\\}$。$f$的期望风险和经验风险分别为：\n",
    "\n",
    "$$R(f)=E[L(Y,f(X))]$$\n",
    "\n",
    "$$\\hat{R}(f)=\\frac{1}{N}\\sum_{i=1}^N L(y_i,f(x_i))$$\n",
    "\n",
    "经验风险最小化函数是：\n",
    "\n",
    "$$g = \\underset{f \\in \\mathcal{F}}{argmin}\\ \\hat{R}(f)$$\n",
    "\n",
    "我们现在关注的是$g$的泛化能力，即$E_{out}$，也就是泛化误差，也就是风险函数：\n",
    "\n",
    "$$R(g) = E[L(Y,h(X)]$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__定理__：对于二元分类问题，当假设空间是有限个函数的集合$\\mathcal{F}=\\{f_1,f_2,\\cdots,f_d\\}$时，对__任意__一个函数$f \\in \\mathcal{F}$，至少以$1-\\delta$，以下不等式成立：\n",
    "\n",
    "$$R(f) \\leq \\hat{R}(f)+\\varepsilon(d,N,\\delta)$$\n",
    "\n",
    "其中，\n",
    "\n",
    "$$\\varepsilon(d,N,\\delta) = \\sqrt{\\frac{1}{2N}\\Big(log\\ d + log\\ \\frac{1}{\\delta}\\Big)}$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__证明__：\n",
    "\n",
    "__Hoeffding不等式__——设$S_n=\\sum_{i=1}^nX_i$是独立随机变量$X_1,X_2,\\cdots,X_n$之和，$X_i\\in[a_i,b_i]$，则对任意$t>0$，以下不等式成立：\n",
    "\n",
    "$$P(S_n-ES_n \\geq t) \\leq exp\\Big(\\frac{-2t^2}{\\sum^n_{i=1}(b_i-a_i)^2}\\Big)$$\n",
    "\n",
    "$$P(ES_n-S_n \\geq t) \\leq exp\\Big(\\frac{-2t^2}{\\sum^n_{i=1}(b_i-a_i)^2}\\Big)$$\n",
    "\n",
    "也可以写成：\n",
    "\n",
    "$$P(|S_n-ES_n| \\geq t) \\leq 2exp\\Big(\\frac{-2t^2}{\\sum^n_{i=1}(b_i-a_i)^2}\\Big)$$\n",
    "\n",
    "但由于经验误差往往比期望误差要小，所以我们重点关注第2个不等式。可以将$\\hat{R}(f)$看做$S_n$，是由$N$个随机变量$\\frac{1}{N}L$求和得到，且$E[\\hat{R}(f)]=R(f)$。故有：\n",
    "\n",
    "$$P\\Big(R(f)-\\hat{R}(f) \\geq \\varepsilon \\Big) \\leq exp(-2N\\varepsilon^2)$$\n",
    "\n",
    "由于$\\mathcal{F}$是有限集合，有：\n",
    "\n",
    "$$P\\Big(\\exists f \\in \\mathcal{F}: R(f)-\\hat{R}(f) \\geq \\varepsilon \\Big) \\underset{union\\ bound}{\\leq} \\sum_{f\\in \\mathcal{F}} P\\Big(R(f)-\\hat{R}(f) \\geq \\varepsilon \\Big) \\leq d·exp(-2N\\varepsilon^2)$$\n",
    "\n",
    "等价的，对__任意__$f \\in \\mathcal{F}$，有：\n",
    "\n",
    "$$P\\Big(R(f)-\\hat{R}(f) \\leq \\varepsilon \\Big) \\geq 1-d·exp(-2N\\varepsilon^2)$$\n",
    "\n",
    "令$\\delta = d·exp(-2N\\varepsilon^2)$，有：\n",
    "\n",
    "$$P\\Big(R(f)-\\hat{R}(f) \\leq \\varepsilon \\Big) \\geq 1-\\delta$$\n",
    "\n",
    "其中$\\varepsilon=\\sqrt{\\frac{1}{2N}\\Big(log\\ d + log\\ \\frac{1}{\\delta}\\Big)}$，即：至少有$1-\\delta$的概率，使得$R(f) \\leq \\hat{R}(f)+\\varepsilon$成立。\n",
    "\n",
    "证毕。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__上述定理将经验误差$E_{in}$与期望误差$E_{out}$联系在了一起！__一个学习方法的泛化误差也有了概率上界。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "当$\\delta$和$N$固定时，泛化边界又可以写成：\n",
    "\n",
    "$$R(f) \\leq \\hat{R}(f)+\\Omega(\\mathcal{F})$$\n",
    "\n",
    "其中，$\\Omega(\\mathcal{F})$代表假设空间的复杂度。由此可见，当假设空间越复杂的时候，泛化上界越大，学习方法的结果越差。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "========补充：关于正则化的泛化误差上界========\n",
    "\n",
    "上面我们已经证明了$R(f) \\leq \\hat{R}(f)+\\Omega(\\mathcal{F})$。\n",
    "\n",
    "如果模型很简单，那么如果我们把$\\hat{R}$做的很小，那么泛化误差上界也会很小，$R$也十分可能很小，没有问题。然而，如果模型很复杂，即使我们把$\\hat{R}$做的很小，但后一项会很大，导致泛化误差上界也会很大，$R$也不一定很小，即没有了保证。\n",
    "\n",
    "\n",
    "加入正则项后，我们不仅仅是最小化$\\hat{R}(f)$，而是最小化$\\hat{R}(f)+\\Omega(\\theta)$，其中$\\Omega(\\theta)$代表single hypothesis的复杂度。那么，我们可以近似想成，结构风险最小化就是在__直接__最小化泛化误差上界——如果结构风险很小，一定是保证泛化误差上界也会很小。因此，最小化结构风险往往要比最小化经验风险更有保障，泛化误差上界会被bound更紧，不容易过拟合。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 1.7 生成模型与判别模型"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "监督学习的方法，又可以分为__生成方法__和__判别方法__，学到的模型分别称为__生成模型__和__判别模型__。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__生成方法__：由数据学习联合概率分布$P(X,Y)$，然后求出条件概率分布$P(Y|X)$作为预测的模型，即生成模型：\n",
    "\n",
    "$$P(Y|X) = \\frac{P(X,Y)}{P(X)}$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__判别方法__：由数据直接学习$P(Y|X)$或$Y=f(X)$作为预测的模型，即判别模型。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 1.8 分类问题"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "分类问题中，输出空间的元素是一个个有限的离散值：有两个离散值，就是__二元分类问题__；有多个离散值，就是__多元分类问题__。这时候，我们也把模型称为__分类器(classifier)__。\n",
    "\n",
    "模型：可以是概率模型，也可以是非概率模型。\n",
    "\n",
    "性能指标：一般用__准确率(accuracy)__——对于给定测试集，分类正确的样本数占总样本数之比。\n",
    "\n",
    "当问题是二元分类问题时，常用的评价指标有：\n",
    "\n",
    "* __精确率(precision)__：预测为正类的里面，多少预测正确了。\n",
    "\n",
    "$$P=\\frac{TP}{TP+FP}$$\n",
    "\n",
    "* __召回率(recall)__：所有的正类里面，预测出来了多少。\n",
    "\n",
    "$$R=\\frac{TP}{TP+FN}$$\n",
    "\n",
    "* __F1分数(F1-score)__：综合指数。\n",
    "\n",
    "$$F_1=\\frac{2TP}{2TP+FN+FP}$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 1.9 回归问题"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "回归问题的输出是连续值，且模型为非概率模型：$Y=f(X)$。\n",
    "\n",
    "按照输入变量的个数，可分为：\n",
    "\n",
    "* 一元回归；\n",
    "* 多元回归；\n",
    "\n",
    "按照模型的类型，可分为：\n",
    "\n",
    "* 线性模型；\n",
    "* 非线性模型；\n",
    "\n",
    "回归问题最常用的损失函数是__平方损失函数__，此时可以用__最小二乘法OLS__求解"
   ]
  }
 ],
 "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.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}