统计学习及监督学习概述

《统计学习方法》笔记 第1章

Posted by Cheereus on January 15, 2020

第1章 统计学习及监督学习概论

1.1 统计学习

  1. 统计学习的特点

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

    统计学习的主要特点是:

    (1) 统计学习以计算机及网络为平台,是建立在计算机及网络上的;

    (2) 统计学习以数据为研究对象,是数据驱动的学科;

    (3) 统计学习的目的是对数据进行预测与分析;

    (4) 统计学习以方法为中心,统计学习方法构建模型并应用模型进行预测与分析;

    (5) 统计学习是概率论、统计学、信息论、计算理论、最优化理论及计算机科学等多个领域的交叉学科,并且在发展中逐步形成独自的理论体系与方法论。

  2. 统计学习的对象

    统计学习研究的对象是数据(data)。它从数据出发,提取数据的特征,抽象出数据的模型,发现数据中的知识,又回到对数据的分析与预测中去。

    统计学习关于数据的基本假设是同类数据具有一定的统计规律性,这是统计学习的前提。由于数据具有统计规律性,所以可以用概率统计方法处理它们。

  3. 统计学习的目的

    统计学习用于对数据的预测和分析,特别是对未知新数据的预测与分析。对数据的预测与分析是通过构建概率统计模型实现的。统计学习总的目标就是考虑学习什么样的模型和如何学习模型,以使模型能对数据进行准确的预测与分析,同时也要考虑尽可能地提高学习效率。

  4. 统计学习的方法

    统计学习的方法是基于数据构建概率统计模型从而对数据进行预测与分析。统计学习由监督学习(supervised learning)、无监督学习(unsupervised learning)和强化学习(reinforcement learning)等组成。

    统计学习方法可以概括如下:

    从给定的、有限的、用于学习的训练数据(training data)集合出发,假设数据是独立同分布产生的;并且假设要学习的模型属于某个函数的集合,称为假设空间(hypothesis space);

    应用某个评价准则(evaluation criterion),从假设空间中选取一个最优模型,使它对已知的训练数据及未知的测试数据(test data)在给定的评价准则下有最优的预测;

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

    这样,统计学习方法包括模型的假设空间、模型选择的准则以及模型学习的算法。称其为统计学习方法的三要素,简称为:

    模型(model)、策略(strategy)和算法(algorithm)。

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

    (1) 得到一个有限的训练数据集合;

    (2) 确定包含所有可能的模型的假设空间,即学习模型和集合;

    (3) 确定模型选择的准则,即学习的策略;

    (4) 实现求解最优模型的算法,即学习的算法;

    (5) 通过学习方法选择最优模型;

    (6) 利用学习的最优模型对新数据进行预测或分析。

  5. 统计学习的研究及重要性

1.2 统计学习的分类

1.2.1 基本分类

1. 监督学习

监督学习(unsupervised learning)是指从标注数据中学习预测模型的机器学习问题。标注数据表示输入输出的对应关系,预测模型对给定的输入产生相应的输出。监督学习的本质是学习输入到输出的映射的统计规律。

(1) 输入空间、特征空间和输出空间

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

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

输入实例的特征向量记作:

$x^{(i)}$ 表示 $x$ 的第 $i$ 个特征。注意 $x^{(i)}$ 与 $x_i$ 不同,通常用 $x_i$ 表示多个输入变量中的第 $i$ 个变量,即:

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

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

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

输入变量与输出变量均为连续变量的预测问题称为回归问题;

输出变量为有限个离散变量的预测问题称为分类问题;

输入与输出变量均为变量序列的预测问题称为标注问题。

(2) 联合概率分布

监督学习假设输入与输出的随机变量 $X$ 和 $Y$ 遵循联合概率分布 $P(X,Y)$ 。 $P(X,Y)$ 表示分布函数,或分布密度函数。

学习过程中,假定这一联合概率分布存在,但对学习系统来说,联合概率分布的具体定义是未知的。训练数据与测试数据被看作是依联合概率分布 $P(X,Y)$ 独立同分布产生的。

统计学习假设数据存在一定的统计规律,$X$ 和 $Y$ 具有联合概率分布就是监督学习关于数据的基本假设。

(3) 假设空间

模型属于由输入空间到输出空间的映射的集合,这个集合就是假设空间(hypothesis space)。假设空间的确定意味着学习范围的确定。

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

(4) 问题的形式化

监督学习分为学习和预测两个过程,由学习系统与预测系统完成。

首先给定一个训练数据集:

其中 $(x_i,y_i), i=1,2,\cdots,N$,称为样本或样本点。$x_i \in X \subseteq R^n$ 是输入的观测值,也称为输入或实例,$y_i \in Y$ 是输出的观测值,也称为输出。

在学习过程中,学习系统利用给定的训练数据集,通过学习(或训练)得到一个模型,表示为条件概率分布 $\hat{P}(Y{\vert}X)$ 或决策函数 $Y=\hat{f}(X)$。

在预测过程中,预测系统对于给定的测试样本集中的输入 $X_{N+1}$,由模型 $y_{N+1}={\arg}\ \underset{y}{\max}\ \hat{P}(y{\vert}x_{N+1})$ 或 $y_{N+1}=\hat{f}(x_{N+1})$ 给出相应的输出 $y_{N+1}$。

学习系统(也就是学习算法)试图通过训练数据集中的样本 $(x_i,y_i)$ 带来的信息学习模型。如果这个模型由很好的预测能力,训练样本输出 $y_i$ 和模型输出 $f(x_i)$ 之间的差就应该足够小。

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

2. 无监督学习

无监督学习(unsupervised learning)是指从无标注数据中学习预测模型的机器学习问题。无监督学习的本质是学习数据中的统计规律或潜在结构。

假设 $X$ 是输入空间,$Z$ 是隐式结构空间。要学习的模型可以表示为函数 $z=g(x)$,条件概率分布 $P(z{\vert}x)$,或者条件概率分布 $P(x{\vert}z)$ 的形式。

无监督学习旨在从假设空间中选出在给定评价标准下的最优模型,和监督学习有类似的流程。

3. 强化学习

强化学习(reinforcement learning)是指智能系统在与环境的连续互动中学习最优行为策略的机器学习问题。假设只能系统与环境的互动基于马尔可夫决策过程(Markov decision process),智能系统能观测到的是与环境互动得到的数据序列。强化学习的本质是学习最优的序贯决策。

强化学习的马尔可夫决策过程是状态、奖励、动作序列上的随机过程,由五元 $<S,A,P,r,\gamma>$ 组成。

  • $S$ 是有限状态(state)的集合
  • $A$ 是有限动作(action)的集合
  • $P$ 是状态转移概率(transition probablity)函数:
  • $r$ 是奖励函数(reward function):$r(s,a)=E(r_{t+1}{\vert}s_t=s,a_t=a)$
  • $\gamma$ 是衰减系数(discount factor):$\gamma \in [0,1]$

马尔可夫决策过程具有马尔可夫性,下一个状态只依赖于前一个状态与动作,由状态转移概率函数 $P(s’{\vert}s,a)$ 表示。下一个奖励依赖于前一个状态与动作,由奖励函数 $r(s,a)$ 表示。

策略 $\pi$ 定义为给定状态下动作函数 $a=f(s)$ 或者条件概率分布 $P(a{\vert}s)$。给定一个策略 $\pi$,只能系统与环境互动的行为就已确定。

价值函数(value function)或状态价值函数(state value function)定义为策略 $\pi$ 从某一个状态 $s$ 开始的长期累积奖励的数学期望:

动作价值函数(action value function)定义为策略 $\pi$ 从某一个状态 $s$ 和动作 $a$ 开始的长期累积奖励的数学期望:

强化学习的目标就是在所有可能的策略中选出价值函数最大的策略 $\pi ^*$,而在实际学习中往往从具体的策略出发,不断优化已有策略。这里 $\gamma$ 表示未来的奖励会有衰减。

强化学习方法中有基于策略的(policy-based)、基于价值的(value-based),这两者属于无模型的(model-free)方法,还有有模型的(model-based)方法。

有模型的方法试图直接学习马尔可夫决策过程的模型,包括转移概率函数和奖励函数。这样可以通过模型对环境的反馈进行预测,求出价值函数最大的策略 $\pi ^*$。

无模型的、基于策略的方法不直接学习模型,而是试图求解最优策略 $\pi ^$,表示为函数 $a=f^(s)$ 或者是条件概率分布 $P^*(a{\vert}s)$,这样也能达到在环境中做出最优决策的目的。学习通常从一个具体策略开始,通过搜索更优的策略进行。

无模型的、基于价值得方法也不直接学习模型,而是试图求解最优价值函数,特别是最优动作价值函数。这样可以间接地学到最优策略,根据该策略在给定的状态下做出相应的动作。

4. 半监督学习与主动学习

1.2.2 按模型分类

1. 概率模型与非概率模型

统计学习的模型可以分为概率模型(probabilistic model)和非概率模型(non-probabilistic model)或者确定性模型(deterministic model)。

决策树、朴素贝叶斯、隐马尔可夫模型、条件随机场、概率潜在语义分析、潜在狄利克雷分配、高斯混合模型是概率模型。

感知机、支持向量机、$k$ 近邻、AdaBoost、$k$ 均值、潜在语义分析,以及神经网络是非概率模型。

逻辑斯蒂回归既可以看作是概率模型,又可看作是非概率模型。

2. 线性模型与非线性模型

统计学习模型,特别是非概率模型,可以分为线性模型(linear model)和非线性模型(non-linear model)。如果函数 $y=f(x)$ 或 $z=g(x)$ 是线性函数。则称模型是线性模型,否则称模型是非线性模型。

感知机、线性支持向量机、$k$ 近邻、$k$ 均值、潜在语义分析是线性模型。

核函数支持向量机、AdaBoost、神经网络是非线性模型。

3. 参数化模型与非参数化模型

参数化模型(parametric model)假设模型参数的维度固定,模型可以由有限维参数完全刻画;非参数化模型(non-parametric model)假设模型参数的维度不固定或者说无穷大,随着训练数据量的增加而不断增大。

感知机、朴素贝叶斯、逻辑斯蒂回归、$k$ 均值、高斯混合模型是参数化模型。

决策树、支持向量机、AdaBoost、$k$ 近邻、潜在语义分析、概率潜在语义分析、潜在狄利克雷分配是非参数化模型。

1.2.3 按算法分类

统计学习根据算法,可以分为在线学习(online learning)与批量学习(batch learning)。

在线学习是指每次接受一个样本,进行预测,之后学习模型,并不断重复该操作的机器学习。

批量学习一次接受所有数据,学习模型,之后进行预测。

利用随机梯度下降的感知机学习算法就是在线学习。

1.2.4 按技巧分类

1. 贝叶斯学习

贝叶斯学习(Bayesian learning),又称为贝叶斯推理(Bayesian inference),其主要想法是,在概率模型的学习和推理中,利用贝叶斯定理,计算在给定数据条件下模型的条件概率,即后验概率,并应用这个原理进行模型的估计,以及对数据的预测。将模型、未观测要素及其参数用变量表示,使用模型的先验分布是贝叶斯学习的特点。

假设随机变量 $D$ 表示数据,随机变量 $\theta$ 表示模型参数。根据贝叶斯定理,可以用以下公式计算后验概率:

其中 $P(\theta)$ 是先验概率,$P(D\vert\theta)$ 是似然函数。

模型估计时,估计整个后验概率分布 $P(\theta\vert D)$。如果需要给出一个模型,通常取后验概率最大的模型。

预测时,计算数据对后验概率分布的期望值:

这里 $x$ 是新样本。

2. 核方法

核方法(kernel method)是使用核函数表示和学习非线性模型的一种机器学习方法,可以用于监督学习和无监督学习。

有一些线性模型的方法基于相似度计算,更具体地,向量内积计算。核方法可以把它们扩展到非线性模型的学习,使其应用范围更广泛。

假设 $x_1$ 和 $x_2$ 是输入空间的任意两个实例(向量),其内积是 $<x_1,x_2>$。假设从输入空间到特征空间的映射是 $\varphi$,于是 $x_1$ 和 $x_2$ 在特征空间的映像是 $\varphi(x_1)$ 和 $\varphi(x_2)$,其内积是 $<\varphi(x_1),\varphi(x_2)>$。核方法直接在输入空间中定义核函数 $K(x_1,x_2)$,使其满足 $K(x_1,x_2)=<\varphi(x_1),\varphi(x_2)>$。

1.3 统计学习方法三要素

1.3.1 模型

假设空间用 $\mathcal F$ 表示。假设空间可以定义为决策函数的集合:

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

参数向量 $\theta$ 取值于 $n$ 维欧式空间 $\mathcal R ^n$,称为参数空间(parameter space)。

假设空间也可以定义为条件概率的集合:

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

参数向量 $\theta$ 取值于 $n$ 维欧式空间 $\mathcal R ^n$,也称为参数空间(parameter space)。

1.3.2 策略

1. 损失函数和风险函数

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

损失函数是 $f(X)$ 和 $Y$ 的非负值函数,记作 $L(Y,f(X))$。

常用的损失函数有以下几种:

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

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

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

(4) 对数损失函数(logarithmic loss function)或对数似然损失函数(log-likelihood loss function)

损失函数值越小,模型就越好。损失函数的期望:

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

给定一个训练数据集:

模型 $f(X)$ 关于训练数据集的平均损失称为经验风险(empirical risk)或经验损失(empirical loss),记作 $R_{emp}$:

期望风险 $R_{exp}(f)$ 是模型关于联合分布的期望损失,经验风险 $R_{emp}(f)$ 是模型关于训练样本集的平均损失。根据大数定律,当样本容量 $N$ 趋于无穷时,经验风险 $R_{emp}(f)$ 趋于 $R_{exp}(f)$。所以一个很自然的想法就是用经验风险估计期望风险。

但是,由于现实中训练样本数目有限,甚至很小,所以用经验风险估计期望风险常常并不理想,要对经验风险进行一定的矫正。这就关系到监督学习的两个基本策略:经验风险最小化和结构风险最小化。

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

经验风险最小化(empirical rish minimization, ERM)的策略认为,经验风险最小的模型就是最优的模型。根据这一策略,按照经验风险最小化求最优模型就是求解最优化问题:

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

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

结构风险最小化(structural risk minimization, SRM)是为了防止过拟合而提出来的策略。结构风险最小化等价于正则化(regularization)。结构风险在经验风险上加上表示模型复杂度的正则化项(regularizer)或罚项(penalty term)。在假设空间、损失函数以及训练数据集确定的情况下,结构风险的定义是:

其中 $J(f)$ 为模型的复杂度,是定义在假设空间上的泛函。模型 $f$ 越复杂,复杂度 $J(f)$ 就越大。也就是说,复杂度表示了对复杂模型的惩罚。$\lambda \geq 0$ 是系数,用以权衡经验风险和模型复杂度。结构风险小需要经验风险与模型复杂度同时小。

结构风险最小化的策略认为结构风险最小的模型是最优的模型。所以求解最优模型,就是求解最优化问题:

这样,监督学习的问题就变成了经验风险或结构风险函数的最优化问题。

1.3.3 算法

1.4 模型评估与模型选择

1.4.1 训练误差与测试误差

当损失函数给定时,基于损失函数的模型的训练误差(training error)和模型的测试误差(test error)就自然成为学习方法评估的标准。

注意,统计学习方法具体采用的损失函数未必是评估时使用的损失函数。

假设学习到的模型是 $Y=\hat f(X)$,训练误差是模型 $Y=\hat f(X)$ 关于训练数据集的平均损失:

其中 $N$ 是训练样本容量。

测试误差是模型 $Y=\hat f(X)$ 关于测试数据集的平均损失:

其中 $N’$ 是测试样本容量。

例如,当损失函数是 0-1 损失时,测试误差就变成了常见的测试数据集上的误差率(error rate):

这里 $I$ 是指示函数(indicator function)。

相应地,常见的测试数据集上的准确率(accuracy)为:

显然:

通常将学习方法对位置数据的预测能力称为泛化能力(generalization ability)。

1.4.2 过拟合与模型选择

当模型的复杂度增大时,训练误差会逐渐减小并趋向于0;而测试误差会先减小,达到最小值后又增大。当选择的模型复杂度过大时,过拟合现象就会发生。这样,在学习时就要防止过拟合,进行最优的模型选择,即选择复杂度适当的模型,以达到使测试误差最小得学习目的。

两种常见的模型选择方法:正则化与交叉验证

1.5 正则化与交叉验证

1.5.1 正则化

正则化一般具有如下形式:

其中,第1项是经验风险,第2项是正则化项,$\lambda \geq 0$ 为调整两者之间关系的系数。

第1项的经验风险较小的模型可能较复杂,这时第2项的模型复杂度会较大。正则化的作用是选择经验风险与模型复杂度同时较小的模型。

1.5.2 交叉验证

如果给定的样本数据充足,进行模型选择的一种简单方法是随机地将数据集切成三部分,分别为训练集(training set)、验证集(validation set)和测试集(test set)。

但在许多实际应用中数据是不足的。为了选择好的模型,可以采用交叉验证(cross validation)方法:

  1. 简单交叉验证
  2. $S$ 折交叉验证(S-fold cross validation)
  3. 留一交叉验证(leave-one-out cross validation)

1.6 泛化能力

1.6.1 泛化误差

如果学到的模型是 $\hat f$,那么用这个模型对未知数据预测的误差即为泛化误差(generalizetion error):

泛化误差反映了学习方法的泛化能力。

1.6.2 泛化误差上界

学习方法的泛化能力分析往往是通过研究泛化误差的概率上界进行的,简称为泛化误差上界(generalization error bound)。具体来说,就是通过比较两种学习方法的泛化误差上界的大小来比较它们的优劣。

泛化误差上界通常具有以下性质:它是样本容量的函数,当样本容量增加时,泛化上界趋于0;它是假设空间容量(capacity)的函数,假设空间容量越大,模型就越难学,泛化误差上界就越大。

1.7 生成模型与判别模型

监督学习方法又可以分为生成方法(generative approach)和判别方法(discriminative approach)。所学到的模型分别称为生成模型和判别模型。

生成方法由数据学习联合概率分布 $P(X,Y)$,然后求出条件概率分布 $P(Y\vert X)$ 作为预测的模型,即生成模型:

这样的方法之所以称为生成方法,是因为模型表示了给定输入 $X$ 产生输出 $Y$ 的生成关系。典型的生成模型有朴素贝叶斯法和隐马尔可夫模型。

判别方法由数据直接学习决策函数 $f(X)$ 或条件概率分布 $P(Y\vert X)$ 作为预测的模型,即判别模型。判别方法关心的是对给定的输入 $X$,应该预测什么样的输出 $Y$。典型的判别模型包括:$k$ 近邻法、感知机、决策树、逻辑斯蒂回归模型、最大熵模型、支持向量机、提升方法和条件随机场等。

生成方法可以还原出联合概率分布,而判别方法则不能;生成方法的学习收敛速度更快,即当样本容量增加的时候,学到的模型可以更快地收敛于真实模型;当存在隐变量时,仍可以用生成方法学习,此时判别方法就不能用。

判别方法直接学习的是条件概率或决策函数,直接面对预测,往往学习的准确率更高,也可以对数据进行各种程度上的抽象、定义特征并使用特征,因此可以简化学习问题。

1.8 监督学习应用

1.8.1 分类问题

监督学习从数据中学习一个分类模型或分类决策函数,称为分类器(classifier)。分类器对输入进行输出的预测,称为分类饿(classification)。可能的输出称为类(class)。

对于二分类问题常用的评价指标是精确率(precision)与召回率(recall)(周志华《机器学习》一书中将这二者翻译为查准率与查全率,笔记整理者注)。通常以关注的类为正类,其他类为负类,分类器在测试数据集上的预测或正确或不正确,分别有四种情况:

  • $TP$ 将正类预测为正类数
  • $FN$ 将正类预测为负类数
  • $FP$ 将负类预测为正类数
  • $TN$ 将负类预测为负类数

精确率(查准率)定义为:

召回率(查全率)定义为:

此外还有 $F_1$ 值,是精确率和召回率的调和均值,即:

精确率和召回率都高时,$F_1$ 值也会高。

1.8.2 标注问题

标注(tagging)也是一个监督学习问题。可以认为标准问题是分类问题的一个推广,又是更复杂的结构预测(structure prediction)问题的简单形式。

评价标注模型的指标与评价分类模型的指标一样,常用的有标注准确率、精确率和召回率。其定义与分类模型相同。

1.8.3 回归问题

回归(regression)是监督学习的另一个重要问题。回归用于预测输入变量(自变量)和输出变量(因变量)之间的关系,特别是当输入变量的值发生变化时,输出变量的值随之发生的变化。回归问题的学习等价于函数拟合。

回归问题按照输入变量的个数,分为一元回归和多元回归;按照输入变量和输出变量之间关系的类型即模型的类型,分为线性回归和非线性回归。

回归学习最常用的损失函数是平方损失函数,在此情况下,回归问题可以由著名的最小二乘法(least squares)求解。

第1章完结