《统计学习方法》笔记

  • 统计学习的定义、研究对象与方法
  • 监督学习,这是本书的主要内容
  • 统计学习方法的三要素
    • 模型
    • 策略
    • 算法
  • 模型选择
    • 正则化
    • 交叉验证
    • 学习的泛化能力
  • 生成模型与判别模型
  • 监督学习方法的应用
    • 分类问题
    • 标注问题
    • 回归问题

统计学习

统计学习的特点

统计学习(statistical learning)是关于计算机基于数据构建概率统计模型并运用模型对数据进行预测与分析的一门学科。

统计学习也称为统计机器学习(statistical machine learning)

统计学习的主要特点是

  1. 统计学习以计算机及网络为平台,是建立在计算机及网络之上的
  2. 统计学习以数据为研究对象,是数据驱动的学科
  3. 统计学习的目的是对数据进行预测与分析
  4. 统计学习以方法为中心,统计学习方法构建模型并应用模型进行预测与分析
  5. 统计学习是概率论、统计学、信息论、计算理论、最优化理论及计算机科学等多个领域的交叉学科,并且在发展中逐步形成独自的理论体系与方法论。

赫尔伯特·西蒙(Herbert A. Simon)曾对“学习”给出以下定义

“如果一个系统能够通过执行某个过程改进它的性能,这就是学习。”

按照这一观点,统计学习就是计算机系统通过运用数据及统计方法提高系统性能的机器学习。现在,当人们提及机器学习时,往往是指统计机器学习。

统计学习的对象

统计学习的对象是数据(data)

它从数据出发,提取数据的特征,抽象出数据的模型,发现数据中的知识,又回到对数据的分析与预测中去。作为统计学习的对象,数据是多样的,包括存在于计算机及网络上的各种数字、文字、图像、视频、音频数据以及它们的组合。

统计学习关于数据的基本假设是同类数据具有一定的统计规律性,这是统计学习的前提。这里的同类数据是指具有某种共同性质的数据,例如英文文章、互联网网页、数据库中的数据等。由于它们具有统计规律性,所以可以用概率统计方法来加以处理。比如,可以用随机变量描述数据中的特征,用概率分布描述数据的统计规律。

在统计学习过程中,以变量或变量组表示数据。数据分为由连续变量和离散变量表示的类型。

离散变量的方法为主。另外,本书只涉及利用数据构建模型及利用模型对数据进行 分析与预测,对数据的 观测和收集 等问题 不作讨论

统计学习的目的

统计学习用于对数据进行预测与分析,特别是对未知新数据进行预测与分析。

  • 对数据的预测可以使计算机更加智能化,或者说使计算机的某些性能得到提高
  • 对数据的分析可以让人们获取新的知识,给人们带来新的发现。

统计学习的方法

统计学习的方法是基于数据构建统计模型从而对数据进行预测与分析。

统计学习由

  • 监督学习(supervised learning)
  • 非监督学习(unsupervised learning)
  • 半监督学习(semi-supervised learning)
  • 强化学习(reinforcement learning)

本书主要讨论 监督学习,这种情况下统计学习的方法可以概括如下:

  • 从给定的、有限的、用于学习的训练数据(training data)集合出发,假设数据是独立同分布产生的
  • 并且假设要学习的模型属于某个函数的集合,称为假设空间(hypothesis space)
  • 应用某个评价准则(evaluation criterion),从假设空间中选取一个最优的模型,使它对已知训练数据及未知测试数据(test data)在给定的评价准则下有最优的预测

最优模型的选取由算法实现

统计学习方法的三要素:模型(model)、策略(strategy)和算法(algorithm)

  • 模型: 模型的假设空间
  • 策略: 模型选择的准则
  • 算法: 模型学习的算法

实现统计学习方法的步骤如下:

  1. 得到一个有限的训练数据集合
  2. 确定包含所有可能的模型的假设空间,即学习模型的集合
  3. 确定模型选择的准则,即学习的策略
  4. 实现求解最优模型的算法,即学习的算法
  5. 通过学习方法选择最优模型
  6. 利用学习的最优模型对新数据进行预测或分析

本书以介绍 统计学习方法为主,特别是 监督学习方法,主要包括用于分类、标注与回归问题的方法。这些方法在自然语言处理、信息检索、文本数据挖掘等领域中有着极其广泛的应用。

统计学习的研究

  • 统计学习方法(statistical learning method)
    • 开发新的学习方法
  • 统计学习理论(statistical learning theory)
    • 探求统计学习方法的有效性与效率
    • 统计学习的基本理论问题
  • 统计学习应用(application of statistical learning)
    • 将统计学习方法应用到实际问题中去,解决实际问题

统计学习的重要性

  • 统计学习是处理海量数据的有效方法
  • 统计学习是计算机智能化的有效手段
  • 统计学习是计算机科学发展的一个重要组成部分

监督学习

  • 监督学习
  • 非监督学习
  • 半监督学习
  • 强化学习

本书主要讨论 监督学习 问题。

监督学习(supervised learning)的 任务 是学习一个模型,使模型能够对任意给定的输入,对其相应的输出做出一个好的预测。

基本概念

输入空间特征空间 输出空间

在监督学习中,将输入与输出所有可能取值的集合分别称为 输入空间(input space)与输出空间(output space)

  • 输入与输出空间可以是有限元素的集合,也可以是整个欧氏空间

  • 输入空间与输出空间可以是同一个空间,也可以是不同的空间

  • 但通常输出空间远远小于输入空间

每个具体的输入是一个实例(instance),通常由 特征向量(feature vector) 表示。这时,所有特征向量存在的空间称为 特征空间(feature space)

模型实际上都是定义在特征空间上的

输入、输出变量用大写字母表示,习惯上输入变量写作 \(X\),输出变量写作 \(Y\)

输入、输出变量所取的值用小写字母表示,输入变量的取值写作 \(x\),输出变量的取值写作 \(y\)。变量可以是标量或向量,都用相同类型字母表示。

本书中向量均为 列向量,输入实例 \(x\) 的特征向量记作
\[ x=\left(x^{(1)}, x^{(2)}, \cdots, x^{(i)}, \cdots, x^{(n)}\right)^{\mathrm{T}} \]
\(\mathbf{x}^{(\mathrm{i})}\) 表示 \(x\) 的第 \(i\) 个特征。注意,\(\mathbf{x}^{(\mathrm{i})}\)\(\mathbf{x}_{\mathbf{i}}\) 不同,本书通常用 \(\mathbf{x}_{\mathbf{i}}\) 表示多个输入变量中的第 \(i\) 个,即

\[ x_{i}=\left(x_{i}^{(1)}, x_{i}^{(2)}, \cdots, x_{i}^{(n)}\right)^{\mathrm{T}} \]

监督学习从训练数据(training data)集合中学习模型,对测试数据(test data)进行预测。训练数据由输入(或特征向量)与输出对组成,训练集通常表示为

\[ T=\left\{\left(x_{1}, y_{1}\right),\left(x_{2}, y_{2}\right), \cdots,\left(x_{N}, y_{N}\right)\right\} \]

测试数据也由相应的输入与输出对组成。输入与输出对又称为 样本(sample)样本点

输入变量 X 和输出变量 \(Y\) 有不同的类型,可以是 连续 的,也可以是 离散 的。

人们根据输入、输出变量的不同类型,对预测任务给予不同的名称

  • 回归问题: 输入变量与输出变量均为连续变量的预测问题
  • 分类问题: 输出变量为有限个离散变量的预测问题
  • 标注问题: 输入变量与输出变量均为变量序列的预测问题

联合概率分布

监督学习假设输入与输出的随机变量X和Y遵循联合概率分布 \(\mathrm{P}(\mathrm{X}, \mathrm{Y})\)

\(\mathrm{P}(\mathrm{X}, \mathrm{Y})\) 表示 分布函数,或 分布密度函数。注意,在学习过程中,假定这一联合概率分布存在,但对学习系统来说,联合概率分布的具体定义是未知的。训练数据与测试数据被看作是依联合概率分布 \(\mathrm{P}(\mathrm{X}, \mathrm{Y})\) 独立同分布产生的。统计学习假设数据存在一定的统计规律,\(X\)\(Y\) 具有联合概率分布的假设就是监督学习关于数据的基本假设。

假设空间

监督学习的目的在于学习一个由输入到输出的映射,这一映射由模型来表示。换句话说,学习的目的就在于找到最好的这样的模型。模型属于由输入空间到输出空间的映射的集合,这个集合就是假设空间(hypothesis space)。假设空间的确定意味着学习范围的确定。

监督学习的模型可以是概率模型或非概率模型,由 条件概率分布 \(\mathrm{P}(\mathrm{Y} | \mathrm{X})\) 或 决策函数(decision function)\(Y=f(X)\) 表示,随具体学习方法而定。对具体的输入进行相应的输出预测时,写作 \(\mathrm{P}(\mathrm{y} | \mathrm{x})\)\(Y=f(x)\)

问题的形式化

监督学习利用训练数据集学习一个模型,再用模型对测试样本集进行预测(prediction)。

由于在这个过程中需要训练数据集,而训练数据集往往是人工给出的,所以称为 监督学习

监督学习分为学习和预测两个过程

  • 学习系统
  • 预测系统

图 1.1 监督学习问题

首先给定一个训练数据集

\[ T=\left\{\left(x_{1}, y_{1}\right),\left(x_{2}, y_{2}\right), \cdots,\left(x_{N}, y_{N}\right)\right\} \]

其中 \(\left(\mathrm{x}_{\mathrm{i}}, \mathrm{y}_{\mathrm{i}}\right), \quad \mathrm{i}=1,2, \ldots, \mathrm{N}\),称为样本或样本点。\(\mathbf{x}_{\mathbf{i}} \in \mathbf{X} \subseteq \mathbf{R}_{\mathbf{n}}\) 输入的观测值,也称为输入或实例,\(\mathrm{y}_{\mathrm{i}} \in \mathcal{Y}\) 是输出的观测值,也称为输出。

监督学习中,假设训练数据与测试数据是依联合概率分布 \(\mathrm{P}(\mathrm{X}, \mathrm{Y})\) 独立同分布产生的。

在学习过程中,学习系统利用给定的训练数据集,通过学习(或训练)得到一个模型,表示为条件概率分布 \(\hat{P}(\mathrm{Y} | \mathrm{X})\) 或决策函数 \(\mathrm{Y}=\hat{f}(\mathrm{X})\)。条件概率分布 \(\hat{P}(\mathrm{Y} | \mathrm{X})\) 或决策函数 \(\mathrm{Y}=\hat{f}(\mathrm{X})\) 描述输入与输出随机变量之间的映射关系。

在预测过程中,预测系统对于给定的测试样本集中的输入 \(\mathbf{X}_{\mathbf{N}+1}\),由模型 \(y_{N+1}=\arg \max _{y_{N+1}} \hat{P}\left(y_{N+1} | x_{N+1}\right)\)\(\mathrm{y}_{\mathrm{N}+1}=\hat{\jmath}\left(\mathrm{x}_{\mathrm{N}+1}\right)\) 给出相应的输出 \(\mathbf{y}_{\mathrm{N}+1}\)

在学习过程中,学习系统(也就是 学习算法)试图通过训练数据集中的样本 \(\left(\mathbf{x}_{i}, \quad \mathbf{y}_{i}\right)\) 带来的信息学习模型。

具体地说,

  • 对输入 \(\mathbf{X}_{\mathbf{i}}\),一个具体的模型 \(y=f(x)\) 可以产生一个输出 \(\mathrm{f}\left(\mathrm{x}_{\mathrm{i}}\right)\)
  • 训练数据集中对应的输出是 \(\mathbf{y}_{\mathrm{i}}\)
  • 如果这个模型有很好的预测能力,训练样本输出 \(\mathbf{y}_{\mathrm{i}}\) 和模型输出 \(\mathrm{f}\left(\mathrm{x}_{\mathrm{i}}\right)\) 之间的差就应该足够小

学习系统通过不断的尝试,选取最好的模型,以便对训练数据集有足够好的预测,同时对未知的测试数据集的预测也有尽可能好的推广。

统计学习三要素

统计学习方法都是由模型、策略和算法构成的,即统计学习方法由 三要素 构成,可以简单地表示为

方法=模型+策略+算法

下面论述监督学习中的统计学习三要素。非监督学习、强化学习也同样拥有这三要素。可以说构建一种统计学习方法就是确定具体的统计学习三要素。

模型

统计学习首要考虑的问题是学习什么样的模型。在监督学习过程中,模型就是所要学习的 条件概率分布决策函数。模型的假设空间(hypothesis space)包含所有可能的条件概率分布或决策函数。

例如,假设决策函数是输入变量的线性函数,那么模型的假设空间就是所有这些线性函数构成的函数集合。假设空间中的模型一般有无穷多个。

假设空间用 \(\mathcal{F}\) 表示。假设空间可以定义为决策函数的集合

\[ \mathcal{F}=\{f | Y=f(X)\} \]

其中,\(X\)\(Y\) 是定义在输入空间 \(x\) 和输出空间 \(\mathcal{Y}\) 上的变量。这时 \(\mathcal{F}\) 通常是由一个参数向量决定的函数族:

\[ \mathcal{F}=\left\{f | Y=f_{\theta}(X), \theta \in \mathbf{R}^{n}\right\} \]

参数向量 \(\theta\) 取值于 \(n\) 维欧氏空间 \(\mathbf{R}_{\mathrm{n}}\),称为参数空间(parameter space)。假设空间也可以定义为条件概率的集合

\[ \mathcal{F}=\{P|P(Y | X)\} \]

其中,\(X\)\(Y\) 是定义在输入空间 \(x\) 和输出空间上的随 \(\mathcal{Y}\) 机变量。这时 \(\mathcal{Y}\) 通常是由一个参数向量决定的条件概率分布族:

\[ \mathcal{F}=\left\{P\left|P_{\theta}(Y | X), \theta \in \mathbf{R}^{n}\right\}\right. \]

参数向量 \(\theta\) 取值于 \(n\) 维欧氏空间 \(\mathbf{R}_{\mathrm{n}}\),也称为参数空间。

本书中称由决策函数表示的模型为 非概率模型,由条件概率表示的模型为 概率模型

策略

有了模型的假设空间,统计学习接着需要考虑的是按照什么样的准则学习或选择最优的模型。

统计学习的目标: 从假设空间中选取最优模型

首先引入损失函数与风险函数的概念。

  • 损失函数度量模型一次预测的好坏
  • 风险函数度量平均意义下模型预测的好坏

损失函数和风险函数

监督学习问题是在假设空间 \(\mathcal{F}\)m中选取模型 \(f\) 作为决策函数,对于给定的输入 \(X\),由 \(f(X)\) 给出相应的输出 \(Y\),这个输出的预测值 \(f(X)\) 与真实值 \(Y\) 可能一致也可能不一致,用一个 损失函数(loss function) 代价函数(cost function) 来度量预测错误的程度。损失函数是 \(f(X)\)\(Y\) 的非负实值函数,记作 \(\mathbf{L}(\mathbf{Y}, \mathrm{f}(\mathbf{X}))\)

统计学习常用的损失函数有以下几种:

  • 0-1 损失函数(0-1 loss function)

\[ L(Y, f(X))=\left\{\begin{array}{ll}{1,} & {Y \neq f(X)} \\ {0,} & {Y=f(X)}\end{array}\right. \]

  • 平方损失函数(quadratic loss function)

\[ L(Y, f(X))=(Y-f(X))^{2} \]

  • 绝对损失函数(absolute loss function)

\[ L(Y, f(X))=|Y-f(X)| \]

  • 对数损失函数(logarithmic loss function)对数似然损失函数(loglikelihood loss function)

\[ L(Y, P(Y | X))=-\log P(Y | X) \]

损失函数值越小,模型就越好。由于模型的输入、输出 \((\mathrm{X}, \mathrm{Y})\) 是随机变量,遵循联合分布 \(\mathrm{P}(\mathrm{X}, \mathrm{Y})\),所以损失函数的期望是
\[ R_{\mathrm{exp}}(f)=E_{p}[L(Y, f(X))]=\int_{X \times y} L(y, f(x)) P(x, y) \mathrm{d} x \mathrm{d} y \]

这是理论上模型 \(\mathrm{f}(\mathrm{X})\) 关于联合分布 \(\mathrm{P}(\mathrm{X}, \mathrm{Y})\) 的平均意义下的损失,称为 风险函数(risk function)期望损失(expected loss)

学习的目标就是选择期望风险最小的模型。由于联合分布 \(\mathrm{P}(\mathrm{X}, \mathrm{Y})\) 是未知的,\(\mathrm{R}_{\mathrm{exp}}(\mathrm{f})\) 不能直接计算。实际上,如果知道联合分布 \(\mathrm{P}(\mathrm{X}, \mathrm{Y})\),可以从联合分布直接求出条件概率分布 \(\mathrm{P}(\mathrm{Y} | \mathrm{X})\),也就不需要学习了。正因为不知道联合概率分布,所以才需要进行学习。

这样一来,一方面根据期望风险最小学习模型要用到联合分布,另一方面联合分布又是未知的,所以监督学习就成为一个 病态问题(ill-formed problem)

给定一个训练数据集

\[ T=\left\{\left(x_{1}, y_{1}\right),\left(x_{2}, y_{2}\right), \cdots,\left(x_{N}, y_{N}\right)\right\} \]

模型 \(\mathrm{f}(\mathrm{X})\) 关于训练数据集的平均损失称为 经验风险(empirical risk)经验损失(empirical loss),记作 \(\mathbf{R}_{\mathrm{emp}}\)

\[ R_{\mathrm{emp}}(f)=\frac{1}{N} \sum_{i=1}^{N} L\left(y_{i}, f\left(x_{i}\right)\right) \]

期望风险 \(\mathrm{R}_{\mathrm{exp}}(\mathrm{f})\) 是模型关于联合分布的期望损失,经验风险 \(\mathrm{R}_{\mathrm{emp}}(\mathrm{f})\) 是模型关于训练样本集的平均损失。根据大数定律,当样本容量N趋于无穷时,经验风险 \(\mathrm{R}_{\mathrm{emp}}(\mathrm{f})\) 趋于期望风险 \(\mathrm{R}_{\mathrm{exp}}(\mathrm{f})\)

这就关系到监督学习的两个基本策略:

  • 经验风险最小化
  • 结构风险最小化

经验风险最小化与结构风险最小化

经验风险最小化(empirical risk minimization,ERM)的策略认为:经验风险最小的模型是最优的模型

根据这一策略,按照经验风险最小化求最优模型就是求解最优化问题:
\[ \min _{f \in \mathcal{F}} \frac{1}{N} \sum_{i=1}^{N} L\left(y_{i}, f\left(x_{i}\right)\right) \]
其中,\(\mathcal{F}\) 是假设空间。

当样本容量足够大时,经验风险最小化能保证有很好的学习效果,在现实中被广泛采用。比如,极大似然估计(maximum likelihood estimation)就是经验风险最小化的一个例子。

当模型是 条件概率 分布,损失函数是 对数损失函数 时,经验风险最小化就等价于 极大似然估计

但是,当样本容量很小时,经验风险最小化学习的效果就未必很好,会产生后面将要叙述的 “过拟合(over-fitting)” 现象。

结构风险最小化(structural risk minimization,SRM)是为了防止过拟合而提出来的策略。

结构风险最小化 等价于 正则化(regularization)

结构风险在经验风险上加上表示模型复杂度的正则化项(regularizer)或罚项(penalty term)。在假设空间、损失函数以及训练数据集确定的情况下,结构风险的定义是
\[ R_{\mathrm{smn}}(f)=\frac{1}{N} \sum_{i=1}^{N} L\left(y_{i}, f\left(x_{i}\right)\right)+\lambda J(f) \]
结构风险最小化的策略认为结构风险最小的模型是最优的模型。所以求最优模型,就是求解最优化问题:

\[ \min _{f \in \mathcal{F}} \frac{1}{N} \sum_{i=1}^{N} L\left(y_{i}, f\left(x_{i}\right)\right)+\lambda J(f) \]
这样,监督学习问题就变成了 经验风险结构风险函数 的最优化问题。

经验或结构风险函数是 最优化的目标函数

算法

算法是指学习模型的具体计算方法。统计学习基于训练数据集,根据学习策略,从假设空间中选择最优模型,最后需要考虑用什么样的计算方法求解最优模型。

这时,统计学习问题归结为最优化问题,统计学习的算法成为求解最优化问题的算法。如果最优化问题有显式的解析解,这个最优化问题就比较简单。但通常解析解不存在,这就需要用数值计算的方法求解。如何保证找到全局最优解,并使求解的过程非常高效,就成为一个重要问题。统计学习可以利用已有的最优化算法,有时也需要开发独自的最优化算法。

统计学习方法之间的不同,主要来自其模型、策略、算法的不同。确定了模型、策略、算法,统计学习的方法也就确定了。这也就是将其称为统计学习三要素的原因。

统计学习方法总结