0%
写在前面
- 昨天, 我们结束了对贝叶斯分类器章节的学习; 今天, 我们将继续学习集成学习中的个体与集成.
个体与集成
- 集成学习(Ensemble Learning)通过构建并结合多个学习器来完成学习任务, 有时也会被称为多分类器系统(Multi-Classifier System), 基于委员会的学习(Committee-Based Learning)等.
- 如下图, 显示出集成学习的一般结构: 先产生一组'个体学习器'(Individual Learner), 再用策略将它们结合起来. 个体学习器通常由一个现有的学习算法从训练数据产生, 例如C4.5决策树算法, BP神经网络算法等, 此时集成中值包含同种类型的个体学习器, 例如'决策树集成'中全是决策树, '神经网络集成'中全是神经网络, 这样的集成是'同质'的(Homogeneous). 同质集成中的个体学习器亦称'基学习器'(Base Learner), 相应的学习算法称为'基学习算法'(Base Learning Algorithm). 集成也可包含不同类型的个体学习器, 例如同事包含决策树和神经网络, 这样的集成是'异质'的(Heterogenous). 异质集成中的个体学习器由不同的学习算法生成, 这是就不在有基学习算法; 相应地, 个体学习器一般不称为基学习器, 常称为'组件学习器'(Component Learner)或直接称为个体学习器.
- 集成学习通过将多个学习器进行结合, 长可获得比单一学习器显著优越的泛化性能. 这对'弱学习器'(Weak Learner)尤为明显, 因此集成学习的很多理论研究都是针对若学习器进行的, 而基学习器有时也被直接成为弱学习器. 但需注意的是, 虽然从理论上来说使用弱学习器集成足以获得好的性能, 但在实践中出于种种考虑, 例如希望使用较少的个体学习器, 或是重用关于常见学习器的一些经验等, 人们往往会使用比较强的学习器. 在一般经验中, 如果把好坏不等的东西掺到一起, 那么通常结果会是比最坏的要好一些, 比最好的要坏一些. 集成学习把多个学习器结合起来, 如何能获得比最好的单一学习器更好的性能呢?
- 考虑一个简单的例子: 在二分类任务中, 假定三个分类器在三个测试样本上的表现如下图, 其中 \(\surd\) 表示分类正确, \(\times\) 表示分类错误, 集成学习的结果通过投票法(Voting)产生, 即'少数服从多数'. a图中每个分类器都只有 \(66.6%\) 的精度, 但集成学习却高达了 \(100%\) ; 在b图中, 三个分类器没有差别, 集成之后性能没有提高; 在c图中, 每个分类器的精度都只有 \(33.3\) , 集成学习的结果变得更糟. 这个简单的例子显示出: 要获得好的集成, 个体学习器应'好而不同', 即个体学习器要有一定的'准确性', 即学习器不能太坏, 并且要有'多样性'(Diversity), 即学习器间具有差异.
- 我们来做个简单的分析. 考虑二分类问题 \(y \in \lbrace -1, +1 \rbrace\) 和真实函数 \(f\) , 假定基分类器的错误率为 \(\epsilon\) , 即对每个基分类器 \(h_{i}\) 有:
- 假设集成通过简单投票法结合 \(T\) 个基分类器, 若有超过半数的基分类器正确, 则集成分类就正确:
- 假设基分类器的错误率相互独立, 则由Hoeffding不等式可知, 集成的错误率为:
- 上式显示出, 随着集成中个体分类器数目 \(T\) 的增大, 集成的错误率将指数级下降, 最终趋向于零. 然而我们必须注意到, 上面的分析有一个关键假设: 及学习期的误差相互独立. 在现实任务中, 个体学习器是为解决同一个问题训练出来的, 他们显然不可能互相独立! 事实上, 个体学习器的'准确性'和'多样性'本身就存在冲突. 一般的, 准确性很高之后, 要增加多样性就需要牺牲准确性. 事实上, 如何产生并结合'好而不同'的个体学习器, 恰是集成学习研究的核心. 更具个体学习器的生成方式, 目前的集成学习方法大致可分为两大类, 即个体学习器间存在强依赖关系, 必须串行生成的序列化方法, 以及个体学习器间不存在强依赖关系, 可同时生成的并行化方法; 前者代表是Boosting, 后者的代表是Bagging和'随机森林'(Random Forest).
写在后面
- 今天, 我们学习了集成学习中的个体与集成; 明天, 我们将继续学习集成学习中的Boosting.
写在前面
- 昨天, 我们学习了贝叶斯分类器中的贝叶斯网; 今天, 我们将继续学习贝叶斯分类器中的EM算法.
EM算法
- 在前面的讨论中, 我们一直假设训练样本所有属性变量的值都已被观测到, 即训练样本是'完整'的. 但在现实应用中往往会遇到'不完整'的训练样本. 未观测变量的学名是'隐变量'(Latent Variable). 令 \(X\) 表示已观测变量集, \(Z\) 表示隐变量集, \(\theta\) 表示模型参数. 若欲对 \(\theta\) 做极大似然估计, 则应最大化对数似然:
- 然而由于 \(Z\) 是隐变量, 上式无法直接求解. 此时我们可以通过对 \(Z\) 计算期望, 来最大化已观测数据的对数'边际似然'(Marginal Likelihood):
- EM(Expectation-Maximization)算法是常用的估计参数隐变量的利器, 他是一种迭代式的方法, 其基本想法是: 若参数 \(\theta\) 已知, 则可更具训练数据推断出最优隐变量 \(Z\) 的值(E步); 反之, 若 \(Z\) 的值已知, 则可方便地对参数 \(\theta\) 做极大似然估计(M步). 于是, 以 \(\theta^{0}\) 为起点, 可迭代执行以下步骤直至收敛
这就是EM算法的原型.
- 进一步, 若我们不是取 \(Z\) 的期望, 而是基于 \(\theta^{t}\) 计算隐变量 (Z) 的概率分布 \(P(Z|X, \theta^{t})\) , 则EM算法的两个步骤是:
- 简单来说, EM算法使用两个步骤交替计算: 第一步是期望(E)步, 利用当前估计的参数值来计算对数似然的期望值; 第二部是最大化(M)步, 寻找能使E步产生的似然期望最大化的参数值. 然后得到的参数值重新被用于E步, ......直至收敛到局部最优解.
- 事实上, 隐变量估计问题也可以通过梯度下降等优化算法求解, 但由于求和的项数将随着隐变量的数目以指数级上升, 会给梯度计算带来麻烦; 而EM算法则可看做一种非梯度优化方法.
写在后面
- 今天, 我们学习了贝叶斯分类器中的EM算法; 明天, 我们将学习下一个章节, 集成学习中的个体与集成.
写在前面
- 昨天, 我们系统的学习了贝叶斯分类器中的半朴素贝叶斯分类器; 今天, 我们继续学习贝叶斯分类器中的贝叶斯网.
贝叶斯网
- 贝叶斯网(Bayesian Network)亦称'信念网'(Belief Network), 它借助有向无环图(Directed Acyclic Graph, 简称DAG)来刻画属性之间的依赖关系, 并使用条件概率表(Conditional Probability Table, 简称CPT)来描述属性的联合概率分布.
- 具体来说, 一个贝叶斯网 \(B\) 由结构 \(G\) 和参数 \(\theta\) 两部分构成, 即 \(B = < G, \theta >\) . 网络结构 \(G\) 是一个有向无环图, 其每个节点对应一个属性, 若两个属性有直接依赖关系, 则他们由一条边连接起来; 参数 \(\theta\) 定量描述这种依赖关系, 假设属性 \(x_{i}\) 在 \(G\) 中的父结点集为 \(\pi_{i}\) , 则 \(\theta\) 包含了每个属性的条件概率表 \(\theta_{x_{i}|\pi_{i}} = P_{B} (x_{i} | \pi_{i})\) .
结构
- 贝叶斯网结构有效地表达了属性建的条件独立性. 给定父节点集, 贝叶斯网假设每个属性与它的非后裔属性独立, 于是 \(B = < G, \theta>\) 将属性 \(x_{1}, x_{2}, ..., x_{d}\) 的联合概率分布定义为:
- 显然, \(x_{3}\) 和 \(x_{4}\) 在给定 \(x_{1}\) 的取值时独立, \(x_{4}\) 和 \(x_{5}\) 在给定的 \(x_{2}\) 取值时独立, 分别简记为 \(x_{3} \perp x_{4} \perp x_{1}\) 和 \(x_{4} \perp x_{5} \perp x_{2}\) . 下图显示出贝叶斯网中三个变量之间的典型依赖关系:
- 在'同父'(Common Parent)结构中, 给定父节点 \(x_{1}\) 的取值, 则 \(x_{3}\) 与 \(x_{4}\) 条件独立. 在'顺序'结构中, 给定 \(x\) 的值, 则 \(y\) 与 \(z\) 条件独立. V型结构(V-Structure)亦称'冲撞'结构, 给定子结点 \(x_{4}\) 的取值, \(x_{1}\) 与 \(x_{2}\) 必不独立; 奇妙的是, 若 \(x_{4}\) 的取值完全未知, 则V型结构下 \(x_{1}\) 与 \(x_{2}\) 却是相互独立的.
- 事实上, 一个变量取值的确定与否, 能对另两个变量间的独立性发生影响, 这个现象并非V型结构所特有.
学习
- 若网络结构已知, 即属性间的依赖关系已知, 则贝叶斯网的学习过程相对简单, 只需通过对训练样本'计数', 估计出每个节点的条件概率表即可. 但在现实应用中我们往往并不知晓网络结构, 于是, 贝叶斯网学习的首要任务就是根据训练数据集来找出结构最'恰当'的贝叶斯网. '评分搜索'是求解这一问题的常用办法. 具体来说, 我们先定义一个评分函数(Score Function), 以此来评估贝叶斯网与训练数据的契合程度, 然后基于这个评分函数来寻找结构最优的贝叶斯网. 显然, 评分函数引入了关于我们希望获得什么样的贝叶斯网的归纳偏好.
- 常用评分函数通常基于信息论准则, 此类准则将学习问题看做一个数据压缩任务, 学习的目标是找到一个能以最短编码长度和使用该模型描述数据所需的字节长度. 对贝叶斯网学习而言, 模型就是一个贝叶斯网, 同事, 每个贝叶斯网描述了一个在训练数据上的概率分布, 自由一套编码机制能使那些经常出现的样本有更短的编码. 于是, 我们应选择那个综合编码长度(包括描述网络和编码数据)最短的贝叶斯网, 这就是'最小描述长度'(Minimal Description Length, 简称MDL)准则.
推断
- 贝叶斯网训练好之后就能用来回答'查询'(Query), 即通过一些属性变量的观测值来推测其他属性变量的取值. 通过已知变量观测值来推测待查询变量的过程称为'推断'(Inference), 已知变量观测值为'证据'(Evidence).
- 最理想的是直接根据贝叶斯网定义的联合概率分布来精确计算后验概率, 不幸的是, 这样的'精确推断'已被证明是NP难的; 换言之, 当网络结点较多, 链接稠密时, 难以进行精确推断, 此时需借助'近似推断', 通过降低精度要求, 在有限时间内求得近似解. 在现实应用中, 贝叶斯网的近似推断常使用吉布斯采样(Gibbs Sampling)来完成, 这事一种随机采样方法
写在后面
- 今天, 我们学习了贝叶斯分类器中的贝叶斯网; 明天, 我们将继续学习贝叶斯分类器中的EM算法.
写在前面
- 昨天, 我们学习了贝叶斯分类器中的朴素贝叶斯分类器; 今天, 我们继续学习贝叶斯分类器中的半朴素贝叶斯分类器.
半朴素贝叶斯分类器
- 为了降低贝叶斯公式中估计后延概率 \(P(c|x)\) 的困难, 朴素贝叶斯分类器采用了属性条件独立性假设, 但在现实任务中这个假设旺旺很难成立. 于是, 人们尝试对属性条件独立性假设进行一定程度的放松, 由此产生了一类称为'半朴素贝叶斯分类器'(Semi-Naive Bayes Classifiers)的学习方法. 半朴素贝叶斯分类器的基本想法是适当考虑一部分属性间的相互依赖信息, 从而不需进行完全联合概率计算, 又不至于彻底忽略了比较强的属性依赖关系. '独依赖估计'(One-Dependent Estimator, 简称ODE)是半朴素贝叶斯分类器最常用的一种策略. 顾名思义, 所谓'独依赖'就是假设每个属性在类别之外最多仅依赖于一个其他属性, 即:
- 其中 \(pa_{i}\) 为属性 \(x_{i}\) 的父属性. 此时, 对每个属性 \(x_{i}\) , 若其父属性 \(pa_{i}\) 已知, 则可采用类似的方法来估计概率值 \(P(x_{i}|c, pa_{i})\) . 于是, 问题的关键就转化为如何确定每个属性的父属性, 不同的做法产生不同的独依赖分类器. 最直接的做法是假设所有属性都依赖于同一个属性, 称为'超父'(Super Parent), 然后通过交叉验证等模型选择方法来确定超父属性, 由此形成了SPODE(Super-Parent ODE)方法. 如下图, \(x_{1}\) 是超父属性:
- TAN(Tree Augmented Naive Bayes)则是在最大带权生成树(Maximum Weighted Spanning Tree)算法的基础上, 通过以下步骤将属性建依赖关系约简为上图的树状结构:
- 容易看出, 条件互信息 \(I(x_{i}, x_{j} | y)\) 刻画了属性 \(x_{i}\) 和 \(x_{j}\) 在已知类别的情况下的相关性, 因此, 通过最大生成树算法. TAN实际上仅保留了强相关属性之间的依赖性. AODE(Averaged One-Dependent Estimator)是一种基于集成学习机制, 更为强大的独依赖分类器. 与SPODE通过模型选择确定超父属性不同, AODE尝试将每个属性作为超父来构建SPODE, 然后将那些具有足够训练数据支撑的SPODE集成起来作为最终结果, 即:
- 其中 \(D_{x_{i}}\) 是在第 \(i\) 个属性上取值为 \(x_{i}\) 的样本的集合, \(m'\) 为阈值常数. 显然, AODE需估计 \(P(c, x_{i})\) 和 \(P(x_{j}|c, x_{i})\) . 则有:
- 其中 \(N_{i}\) 是第 \(i\) 个属性可能的取值数, \(D_{c, x_{i}}\) 是类别为 \(c\) 且在第 \(i\) 个属性上取值为 \(x_{i}\) 的样本集合, \(D_{c, x_{i}, x_{j}}\) 是类别为 \(c\) 且在第 \(i\) 和第 \(j\) 个属性上取值分别为 \(x_{i}\) 和 \(x_{j}\) 的样本集合.
- 不难看出, 与朴素贝叶斯分类器想死, AODE的训练过程也是'计数', 即在训练数据集上对符合条件的样本进行计数的过程. 与朴素贝叶斯分类器相似, AODE无需模型选择, 既能通过预计算节省预测时间, 也能采取懒惰学习方式在与测试再进行计数, 并且易于实现增强学习. 若训练数据非常充分, 泛化性能有可能提升; 但在有限样本条件下, 则有陷入估计高阶联合概率的泥沼.
写在后面
- 今天, 我们学习了贝叶斯分类器中的半朴素贝叶斯分类器; 明天, 我们将继续学习贝叶斯分类器中的贝叶斯网.
写在前面
- 昨天, 我们学习了贝叶斯分类器中的极大似然估计; 今天, 我们将继续学习朴素贝叶斯分类器中的朴素贝叶斯分类器.
朴素贝叶斯分类器
- 不难发现, 基于贝叶斯公式来估计后验概率 \(P(c|x)\) 的主要困难在于: 类似条件概率 \(P(x|c)\) 是所有属性上的联合概率, 难以从有限的训练样本直接估计而得. 为避开这个障碍, 朴素贝叶斯分类器(Naive Bayes Classifier)采用了'属性条件独立假设'(Attribute Conditional Independence Assumption): 对已知类别, 假设所有属性互相独立. 换言之, 假设每个属性独立地对分类结果发生影响. 基于属性条件假设, 得到:
- 其中 \(d\) 为属性数目, \(x_{i}\) 为 \(x\) 在第 \(i\) 个属性上的取值. 由于对所有类别来说 \(P(x)\) 相同, 因此有朴素贝叶斯分类器表达式:
- 显然, 朴素贝叶斯分类器的训练过程就是基于训练集 \(D\) 来估计类先验概率 \(P(c)\) , 并为每个属性估计条件概率 \(P(x_{i}|c)\) . 令 \(D_{c}\) 表示训练集 \(D\) 中第 \(c\) 类样本组成的集合, 若有充足的独立同分布样本, 则可容易地估计出类先验概率:
- 对离散属性而言, 令 \(D_{c, x_{i}}\) 表示 \(D_{c}\) 中在第 \(i\) 个属性上取值为 \(x_{i}\) 的样本组成的集合, 则条件概率 \(P(x_{i}|c)\) 可估计为:
- 对连续属性可考虑概率密度函数, 假定 \(p(x_{i}|c) \sim N(\mu_{c, i} , \sigma^{2}_{c, i})\) , 其中 \(\mu_{c, i}\) 和 \(\sigma^{2}_{c, i}\) 分别是第 \(c\) 类样本在第 \(i\) 个属性上取值的均值和方差, 则有:
- 为了避免其他属性携带的信息被训练集中未出现的属性值'抹去', 在估计概率值时通常要进行'平滑'(Smoothing), 常用'拉普拉斯修正'(Laplacian Correction). 具体来说, 令 \(N\) 表示训练集 \(D\) 中可能的类别数, \(N_{i}\) 表示第 \(i\) 个属性可能的取值数, 则有:
- 拉普拉斯修正避免了因训练集样本不充分而导致概率估值为零的问题, 并且在训练集变大时, 修正过程所引入的先验(Prior)的影响也会逐渐变得可忽略, 使得估值逐渐趋向于实际概率值. 在现实任务中朴素贝叶斯分类器有多种使用方式. 例如, 若任务对预测速度要求较高, 则对给定训练集, 可将朴素贝叶斯分类器涉及的所有概率估值事先计算好存储起来, 这样在进行预测时只需'查表'即可进行判别; 若任务数据更替频繁, 则可采用'懒惰学习'(Lazy Learning)方式, 先不进行任何训练, 待收到预测请求时再根据当前数据集进行概率估值; 若数据不断增加, 则可在现有估值基础上, 仅对新增样本的属性值所涉及的概率估值进行计数修正即可实现增量学习.
写在后面
- 今天, 我们学习了贝叶斯分类器中的朴素贝叶斯分类器; 明天, 我们将继续学习贝叶斯分类器中的半朴素贝叶斯分类器.
写在前面
- 昨天, 我们学习了贝叶斯分类器中的贝叶斯决策论; 今天, 我们接着学习贝叶斯分类器中的极大似然估计.
极大似然估计
- 估计类条件概率的一种常用策略是先假定其具有某种确定的概率分布形式, 再基于训练样本对概率分布的参数进行估计. 具体地, 记关于类别 \(c\) 的类条件概率为 \(P(x|c)\) , 假设 \(P(x|c)\) 具有确定的形式并且被参数向量 \(\theta_{c}\) 唯一确定, 则我们的任务就是利用训练集 \(D\) 估计参数 \(\theta_{c}\) . 为明确期间, 我们将 \(P(x|c)\) 记为 \(P(x|\theta_{c})\) .
- 事实上, 概率模型的训练过程就是参数估计(Parameter Estimation)过程. 对于参数估计, 统计学界的两个学派分别提供了不同的解决方案: 频率主义学派(Frequentist)人为参数虽然未知, 但却是客观存在的固定值, 因此, 可通过优化似然函数等准则来确定参数值; 贝叶斯学派(Bayesian)则认为参数是未观察到的随机变量, 其本身也可有分布, 因此, 可假定参数服从一个先验分布, 然后基于观测到的数据来计算参数的后验分布. 本节介绍源自频率主义学派的极大似然估计(Maximum Likelihood Estimation, 简称MLE), 这是根据数据采样来估计概率分布参数的经典方法.
- 令 \(D_{c}\) 表示训练集 \(D\) 中第 \(c\) 类样本组合的集合, 假设这些样本是独立同分布的, 则参数 \(\theta_{c}\) 对于数据集 \(D_{c}\) 的似然是:
- 对 \(\theta_{c}\) 进行极大似然估计, 就是去寻找最大化似然 \(P(D_{c}|\theta_{c})\) 的参数值 \(\hat{\theta}_{c}\) . 直观上看, 极大似然估计是在试图在 \(\theta_{c}\) 所有可能的取值中, 找到一个能使数据出现的'可能性'最大值. 上式中的连乘操作易造成下溢, 通常使用对数似然(Log-Likelihood):
- 此时参数 \(\theta_{c}\) 的极大似然估计 \(\theta_{c}\) 为:
- 例如, 在连续属性情形下, 假设概率密度函数 \(p(x|c) \sim N(\mu_{c}, \sigma^{2}_{c})\) , 则参数 \(\mu_{c}\) 和 \(\sigma^{2}_{c}\) 的极大似然估计为:
- 也就是说, 通过极大似然法得到的正太分布均值就是样本均值, 方差就是 \((x - \hat{\mu}_{c})(x - \hat{\mu}_{c})^{T}\) 的均值, 这显然是一个符合直觉的结果. 在离散属性情形下, 也可通过类似的方法估计类条件概率.
- 需注意的是, 这种参数化的方法虽能使类条件概率估计变得相对简单, 但估计结果的准确性严重依赖于所假设的概率分布形式是否符合潜在的真实数据分布. 在现实应用中, 欲做出能较好地接近潜在真实分布的假设, 往往需在一定程度上利用关于应用任务本身的经验知识, 否则若仅凭'猜测'来假设概率分布形式, 很可能产生误导性的结果.
写在后面
- 今天, 我们学习了贝叶斯分类器中的极大似然估计; 明天, 我们将继续学习贝叶斯分类器中的朴素贝叶斯分类器.
写在前面
- 前几天, 我们系统的学习了SVM相关的一些知识, 今天我们将开启一个新的章节贝叶斯分类器, 我们先来看看第一个小节中的内容, 贝叶斯决策论.
贝叶斯决策论
- 贝叶斯决策轮(Bayesian Decision Theory)是概率框架下实施决策的基本方法. 对分类任务来说, 在所有行管概率都已知的理想情形下, 贝叶斯决策轮考虑如何基于这些概率和误判损失来选择最优的类别标记. 我们以多分类任务为例来解释其基本原理.
- 假设有 \(N\) 种可能的类别标记, 即 \(Y = \lbrace c_{1}, c_{2}, ..., c_{N} \rbrace\) , \(\lambda_{ij}\) 是一个将真实标记为 \(c_{j}\) 的样本误分类为 \(c_{i}\) 所产生的损失. 基于后验概率 \(P(c_{i}|x)\) 可获得将样本 \(x\) 分类为 \(c_{i}\) 所产生的期望损失(Expected Loss), 即在样本 \(x\) 上的'条件风险'(Conditional Risk):
- 我们的任务是寻找一个判定准则 \(h : X \mapsto Y\) 以最小化总体风险:
- 显然, 对每个样本 \(x\) , 若 \(h\) 能最小化条件风险 \(R(h(x)|x)\) , 则总体风险 \(R(x)\) 也将被最小化. 这就产生了贝叶斯判定准则(Bayes Decision Rule): 为最小化总体风险, 只需在每个样本上选择那个能使条件风险 \(R(c|x)\) 最小的类别标记, 即:
- 此时, \(h^{*}\) 称为贝叶斯最优分类器(Bayes Optimal Classifier), 与之对应的总体风险 \(R(h^{*})\) 称为贝叶斯风险(Bayes Risk). \(1 - R(h^{*})\) 反映了分类器所能达到的最好性能, 即通过机器学习所能产生的模型精度的理论上线. 具体来说, 若目标是最小化分类错误率, 则误判损失 \(\lambda_{ij}\) 可写为:
- 即对每个样本 \(x\) ,选择能使后延概率 \(P(c|x)\) 最大的类别标记. 不难看出, 欲使用贝叶斯判定准则来最小化决策风险, 首先要获得后验概率 \(P(c|x)\) . 然而, 在现实任务中这通常难以直接获得. 从这个角度来看, 机器学习所要实现的是基于有限的训练样本集尽可能准确地估计出后验概率 \(P(c|x)\) . 大体来说, 主要有两种策略: 给定 \(x\) , 可通过直接建模 \(P(c|x)\) 来预测 \(c\) , 这样得到的是'判别式模型'(Discriminative Models); 也可先对联合概率分布 \(P(x, c)\) 建模, 然后再由此获得 \(P(c|x)\) , 这样得到的是'生成式模型'(Generative Models). 显然, 前面介绍的决策树, BP神经网络, 支持向量机等, 都可归入判别式模型的范畴. 对生成式模型来说, 必然考虑:
- 其中, \(P(c)\) 是类'先验'(Prior)概率; \(P(x|c)\) 是样本 \(x\) 相对于类标记 \(c\) 的类条件概率(Class-Conditional Probability), 或称为'似然'(Likelihood); \(P(x)\) 是用于归一化的'证据'(Evidence)因子. 对给定样本 \(x\) , 证据因子 \(P(x)\) 与类标记无关, 因此估计 \(P(c|x)\) 的问题就转化为如何基于训练数据 \(D\) 来估计先验 \(P(c)\) 和似然 \(P(x|c)\) . 类先验概率 \(P(c)\) 表达了样本空间中各类样本所占的比例, 根据大数定律, 当训练集包含充足的独立同分布样本时, \(P(c)\) 可通过各类样本出现的频率来进行估计.
- 对类条件概率 \(P(x c)\) 来说, 由于它涉及关于 \(x\) 所有属性的联合概率, 直接根据样本出现的频率来估计将会遇到严重的困难. 例如, 假设样本的 \(d\) 个属性都是二值的, 则样本空间将有 \(2^{d}\) 种可能的取值, 在现实应用中, 这个值往往远大于训练样本数 \(m\) , 也就是说, 很多样本取值在训练集中根本没有出现, 直接使用频率来估计 \(P(x|c)\) 显然不可行, 因为'未被观测到'与'出现频率为零'通常是不同的.
写在后面
- 今天, 我们学习了贝叶斯分类器中的贝叶斯决策论; 明天, 我们将继续学习贝叶斯分类器中的极大似然估计.
写在前面
- 昨天, 我们学习了SVM中的软间隔与正则化; 今天, 我们继续学习SVM中的支持向量回归.
支持向量回归
- 现在我们来考虑回归问题. 给定训练样本 \(D = \lbrace (x_{1}, y_{1}), (x_{2}, y_{2}), ..., (x_{m}, y_{m}) \rbrace\) , \(y_{i} \in \mathbb{R}\) , 希望学得一个回归模型, 使得 \(f(x)\) 与 \(y\) 尽可能接近, \(w\) 和 \(b\) 是待确定的模型参数.
- 对样本 \((x, y)\) , 传统回归模型通常直接基于模型输出 \(f(x)\) 与真实输出 \(y\) 之间的差别来计算损失, 当且仅当 \(f(x)\) 与 \(y\) 完全相同时, 损失才为零. 与此不同, 支持向量回归(Support Vector Regression, 简称SVR)假设我们能容忍 \(f(x)\) 与 \(y\) 之间最多有 \(\varepsilon\) 的偏差, 即仅当 \(f(x)\) 与 \(y\) 之间的差别绝对值大于 \(\varepsilon\) 时才计算损失. 如下图, 这相当于以 \(f(x)\) 为中心, 构建了一个宽度为 \(2\varepsilon\) 的间隔带, 若训练样本落入此间隔带, 则认为是被预测正确的.
- 于是, SVR问题可形式化为:
- 其中 \(C\) 为正则化常数, \(l_{\varepsilon}\) 是 \(\varepsilon\) - 不敏感损失 ( \(\varepsilon\) - insensitive loss )函数:
- 引入松弛变量 \(\varepsilon _{i}\) 和 \(\hat{\varepsilon}_{i}\) , 可重写为:
- 通过引入拉格朗日乘子 \(\mu_{i} \geq 0 , \hat{\mu_{i}} \geq 0 , \alpha_{i} \geq 0 , \hat{\alpha_{i}} \geq 0\) , 由拉格朗日乘子法可得到拉格朗日函数:
- 再令 \(L(w, b, \alpha , \hat{\alpha} , \varepsilon , \hat{\varepsilon} , \mu , \hat{\mu})\) , 对 \(w , b, \varepsilon _{i}\) 和 \(\hat{\varepsilon}_{i}\) 的偏导为零可得:
- 将式带入, 即可得到SVR的对偶问题:
- 上述过程中满足KKT条件, 即要求:
- 可以看出, 当且仅当 \(f(x) - y_{i} - \varepsilon - \varepsilon _{i} = 0\) 时 \(\alpha_{i}\) 能取非零值, 当且仅当 \(y_{i} - f(x_{i}) - \varepsilon - \hat{\varepsilon}_{i} = 0\) 时 \(\hat{\alpha}_{i}\) 能取非零值. 换言之, 仅当样本 \((x_{i}, y_{i})\) 不落入 \(\varepsilon\) - 间隔带中, 相应的 \(\alpha_{i}\) 和 \(\hat{\alpha}_{i}\) 才能取非零值. 此外, 约束 \(f(x_{i}) - y_{i} - \varepsilon - \varepsilon_{i} = 0\) 和 \(y_{i} - f(x_{i}) - \varepsilon - \hat{\varepsilon}_{i} = 0\) 不能同时成立, 因此 \(\alpha_{i}\) 和 \(\hat{\alpha}_{i}\) 中至少有一个为零. 则SVR的解形如:
- 能使 \((\hat{\alpha}_{i} - \alpha_{i}) \neq 0\) 的样本即为SVR的支持向量, 他们必须落在 \(\varepsilon\) - 间隔带之外. 显然, SVR的支持向量仅是训练样本的一部分, 即其解仍具有稀疏性. 由KKT条件可看出, 对每个样本 \((x_{i}, y_{i})\) 都有 \((C - \alpha_{i})\varepsilon_{i} = 0\) 且 \(\alpha_{i} (f(x_{i}) - y_{i} - \varepsilon - \varepsilon_{i}) = 0\) . 于是, 在得到 \(\alpha_{i}\) 后, 若 \(0 < \alpha_{i} < C\) , 则必有 \(\varepsilon_{i} = 0\) 进而有:
- 因此, 在求解得到 \(\alpha_{i}\) 后, 理论上来说, 可任意选取满足 \(0 < \alpha_{i} < C\) 的样本求得 \(b\) . 实践中长采用一种更鲁棒的办法: 选取多个(或所有)满足条件 \(0 < \alpha_{i} < C\) 的样本求解 \(b\) 后取平均值. 若考虑特征映射形式, 相应的, 得到:
- 则SVR可表示为:
其中 \(k(x_{i}, x_{j}) = \phi (x_{i})^{T} \phi (x_{j})\) 为核函数.
写在后面
- 今天, 我们学习了SVM中的支持向量回归; 明天, 我们将继续学习SVM中的核方法.
写在前面
- 昨天, 我们学习了SVM中的支持向量回归. 今天, 我们继续学习SVM中的核方法.
核方法
- 回顾前面两天的内容, 可以发现, 给定训练样本 \(\lbrace (x_{1}, y_{1}), (x_{2}, y_{2}), ..., (x_{m}, y_{m}) \rbrace\) , 若不考虑偏移项 \(b\) , 则无论SVM还是SVR, 学得的模型总能表示成核函数 \(k(x, x_{i})\) 的线性组合. 不仅如此, 事实上我们有下面这个称为'表示定理'(Representer Theorem)的更一般的结论:
- [定理]: 令 \(H\) 为核函数 \(k\) 对应的再生核希尔伯特空间, \(||h||_{H}\) 表示 \(H\) 空间中关于 \(h\) 的函数, 对于任意单调递增函数 \(\Omega : [0, \infty ]\) , 优化问题:
\[\min_{h \in H} F(h) = \Omega (||h||_{H}) + (h(x_{1}), h(x_{2}), ..., h(x_{m}))\]
- 上式的解总可写为:
\[h^{*}(x) = \sum^{m}_{i = 1} \alpha _{i} k(x, x_{i})\]
- 表示定理对损失函数没有限制, 对正则化项 \(\Omega\) 仅要求单调递增, 甚至不要求 \(\Omega\) 是凸函数, 意味着对于一般的损失函数和正则化项, 优化问题的最优解 \(h^{*}(x)\) 都可表示为核函数 \(k(x, x_{i})\) 的线性组合; 这显示出核函数的巨大威力.
- 人们发展出一些列基于核函数的学习方法, 统称为'核方法'(Kernel Methods). 最常见的, 是通过'核化'(即引入核函数)来讲线性学习器拓展为非线性学习器, 从而得到'核线性判别分析'(Kernelized Linear Discriminant Analysis, 简称KLDA).
- 我们先假设可通过某种映射 \(\varphi : X \mapsto F\) 将样本映射到一个特征空间 \(F\) , 然后在 \(F\) 中执行线性判别分析, 以求得:
\[h(x) = w^{T} \varphi (x)\]
- 则KLDA的学习目标是:
\[\max_{w} J(w) = \frac{w^{T}S^{\varphi}_{b}w}{w^{T}S^{\varphi}_{w}w}\]
- 其中 \(S^{\varphi}_{b}\) 和 \(S^{\varphi}_{w}\) 分别为训练样本在特征空间 \(F\) 中的类间散度矩阵和类内散度矩阵. 令 \(X_{i}\) 表示第 \(i \in \lbrace 0, 1 \rbrace\) 类样本的集合, 其样本数为 \(m_{i}\) ; 总样本数 \(m = m_{0} + m_{1}\) . 第 \(i\) 类样本在特征空间 \(F\) 中的均值为:
\[\mu ^{\varphi}_{i} = \frac{1}{m_{i}} \sum_{x \in X_{i}} \varphi (x)\]
- 两个三度矩阵分别为:\(S^{\varphi}_{b} = (\mu ^{\varphi}_{1} - \mu ^{\varphi}_{0})(\mu ^{\varphi}_{1} - \mu ^{\varphi}_{0})^{T}\)
\(S^{\varphi}_{w} = \sum^{1}_{i = 1} \sum_{x \in X_{i}} (\varphi (x) - \mu ^{\varphi}_{i})(\varphi (x) - \mu ^{\varphi}_{i})^{T}\)
- 通常我们难以知道映射 \(\varphi\) 的具体形式, 因此使用核函数 \(k(x, x_{i}) = \varphi (x_{i})^{T} \varphi (x)\) 来隐式地表达这个映射和特征空间 \(F\) . 把 \(J(w)\) 作为损失函数 \(l\) , 再令 \(\Omega \equiv 0\) , 由表示定理, 函数 \(h(x)\) 可写为:
\[h(x) = \sum^{m}_{i = 1} \alpha _{i} k(x, x_{i})\]
- 于是有:
\[w = \sum^{m}_{i = 1} \alpha _{i} \varphi (x_{i} \cdot \cdot)\]
- 令 \(K \in R^{m \times m}\) 为核函数 \(k\) 所对应的核矩阵, \((K)_{ij} = k(x_{i}, x_{j})\) . 令 \(l_{i} \in \lbrace 1, 0 \rbrace ^{m \times 1}\) 为第 \(i\) 类样本的指示向量, 即 \(l_{i}\) 的第 \(j\) 个分量为0. 再令:\(\hat{\mu}_{0} = \frac{1}{m_{0}} K l_{0}\)
\(\hat{\mu}_{1} = \frac{1}{m_{0}} K l_{1}\)
\(M = (\hat{\mu}_{0} - \hat{\mu}_{1})(\hat{\mu}_{0} - \hat{\mu}_{1})^{T}\)
\(N = KK^{T} - \sum^{l}_{i = 0} m_{i} \hat{\mu}_{i} \hat{\mu}^{T}_{i}\)
- 于是等价为:
\[\max_{\alpha} J (\alpha) = \frac{\alpha ^{T} M \alpha}{\alpha ^{T} N \alpha}\]
- 显然, 使用线性判别分析求解方法可得到 \(\alpha\) , 进而可得到投影函数 \(f(x)\) .
写在后面
- 今天, 我们学习了SVM中的核方法. 明天, 我们将学习下一章, 贝叶斯分类器中的贝叶斯决策论.
写在前面
- 昨天, 我们学习了, SVM中的核函数; 今天, 我们将接下去学习SVM中的软间隔与正则化.
软间隔与正则化
- 在前面的讨论中, 我们一直假定训练样本在样本空间或特征空间中是线性可分的, 即存在一个超平面能将不同类的样本完全划分开. 然而, 在现实任务中往往很难确定合适的核函数使得训练样本在特征空间中线性可分; 退一步说, 即便恰好找到了某个核函数使训练集在特征空间中线性可分, 也很难断定这个貌似线性可分的结果不是由于过拟合所造成的.
- 缓解该问题的一个办法是允许支持向量机在一些样本上出错. 为此, 要引入'软间隔'(Soft Margin)的概念, 如下图:
- 具体来说, 前面介绍的支持向量机形式是要求所有样本均满足约束, 即所有样本都必须划分正确, 这称为'硬间隔'(Hard Margin), 而软间隔则是允许某些样本不满足约束:
\[y_{i}(w^{T}x_{i} + b) \geq 1\]
- 当然, 在最大化间隔的同事, 不满足约束的样本应尽可能少. 于是优化目标可写为:
\[\min_{w, b} \frac{1}{2} ||w||^2 + C \sum^{m}_{i = 1} l_{0 / 1} (y_{i} (w^{T} x_{i} + b) - 1)\]
- 其中 \(C > 0\) 是一个常数, \(l_{0 / 1}\) 是 ' \(0 / 1\) 损失函数':
\[l_{0 / 1} (z) = \begin{cases} 1, & if z < 0 ; \\ 0, & otherwise. \end{cases}\]
- 然而, \(l_{0 / 1}\) 非凸, 非连续, 数学性质不太好, 不易直接求解. 于是, 人们通常用其他一些函数来代替 \(l_{0 / 1}\) , 称为'替代损失'(Surrogate Loss). 替代损失函数一般具有较好的数学性质, 如他们通常是凸的连续函数且是 \(l_{0 / 1}\) 的上界, 三种常用的替代函数:1.hinge损失: \(l_{hinge}(z) = \max(0, 1 - z)\)
2.指数损失(Exponential Loss): \(l(exp)(z) = \exp(- z)\)
3.对率损失(Logistic Loss): \(l_{log}(z) = \log(1 + \exp(- z))\)
- 若采用hinge损失, 则有:
\[\min_{w, b} \frac{1}{2} ||w||^2 + C \sum^{m}_{i = 1} \max(0, 1 - y_{i} (w^{T}x_{i} + b))\]
- 引入'松弛变量'(Slack Variables) \(\varepsilon_{i} \geq 0\) , 则有:
\[\min_{w, b, \varepsilon_{i}} \frac{1}{2} ||w||^2 + C \sum^{m}_{i = 1} \varepsilon_{i}\]
s.t. \(y_{i}(w^{T}x_{i} + b) \geq 1 - \varepsilon_{i}\)
\(\varepsilon_{i} \geq 0 , i = 1, 2, ..., m.\)
- 如上图, 这就是常用的'软间隔支持向量机'.
- 显然, 每个样本都有一个对应的松弛变量, 用以表征改样本不满足约束的程度. 这仍是一个二次规划问题. 于是, 通过拉格朗日乘子发可得到上式的拉格朗日函数:\(L(w, b, \alpha , \varepsilon , \mu ) = \frac{1}{2} ||w||^2 + C \sum^{m}_{i = 1} \varepsilon_{i} + \sum^{m}_{i = 1} \alpha _{i} (1 - \varepsilon_{i} - y_{i} (w^{T}x_{i} + b)) - \sum^{m}_{i = 1} \mu _{i} \varepsilon_{i}\)
- 其中 \(\alpha _{i} \geq 0 , \mu _{i} \geq 0\) 是拉格朗日乘子. 令 \(L(w, b, \alpha , \varepsilon , \mu )\) 对 \(w, b, \varepsilon _{i}\) 的偏导为零可得:\(w = \sum^{m}_{i = 1} \alpha _{i} y_{i} x_{i}\)
\(0 = \sum^{m}_{i = 1} \alpha _{i} y_{i}\)
\(C = \alpha _{i} + \mu _{i}\)
- 即可得到对偶问题:\(\max_{\alpha} \sum^{m}_{i = 1} \alpha _{i} - \frac{1}{2} \sum^{m}_{i = 1} \sum^{m}_{j = 1} \alpha _{i} \alpha _{j} y_{i} y_{j} x^{T}_{i} x_{j}\)
s.t. \(\sum^{m}_{i = 1} \alpha _{i} y_{i} = 0\)
\(0 \leq \alpha _{i} \leq C , i = 1, 2, ..., m\)
- 对比两者可看出, 两者的唯一差别就在于对偶变量的约束不同: 前者是 \(0 \leq \alpha _{i} \leq C\) , 后者是 \(0 \leq \alpha _{i}\) . 于是在引入核函数后能得到同样的支持向量式. 对软间隔支持向量机, KKT条件要求:
\[\begin{cases} \alpha _{i} \geq 0 , & \mu _{i} \geq 0 , \\ y_{i}f(x_{i}) - 1 + \varepsilon _{i} \geq 0, \\ a_{i}(y_{i}f(x_{i}) - 1 + \varepsilon _{i}) = 0 , \\ \varepsilon _{i} \geq 0 , & \mu _{i} \varepsilon _{i} = 0 . \end{cases}\]
- 于是, 对任意训练样本 \((x_{i}, y_{i})\) , 总有 \(\alpha _{i} = 0\) 或 \(y_{i}f(x_{i}) = 1 - \varepsilon _{i}\) . 若 \(\alpha _{i} = 0\) , 则该样本不会对 \(f(x)\) 有任何影响; 若 \(\alpha _{i} > 0\) , 则必有 \(y_{i}f(x_{i}) = 1 - \varepsilon _{i}\) , 即改样本是支持向量: 若 \(\alpha _{i} < C\) , 则 \(\mu _{i} > 0\) , 进而有 \(\varepsilon _{i} = 0\) , 即该样本落在恰在最大间隔边界上; 若 \(\alpha _{i} = C\) , 则有 \(\mu _{i} = 0\) , 此时若 \(\varepsilon _{i} \leq 1\) 则该样本落在最大间隔内部, 若 \(\varepsilon _{i} > 1\) 则该样本被错误分类. 由此可看出, 软间隔支持向量机的最总模型仅与支持向量有关, 即通过采用hinge损失函数仍保持了洗属性.
- 那么能否使用其他的替代损失函数呢? 可以发现, 如果使用对率损失函数 \(l_{log}\) 来替代上面的 \(0 / 1\) 损失函数, 则几乎就得到了对率回归模型. 实际上, 支持向量机与对率回归的优化目标镶金, 通常情形下它们的性能也相当. 对率回归的优势主要在于其输出具有自然的概率意义, 即在给出预测标记的同时也给出了概率, 而支持向量机的输出不具有概率意义, 欲得到概率输出需进行特殊处理, 此外, 对率回归能直接用于对分类任务, 支持向量机为此则需进行推广. 另一方面, 可以看出hinge损失有一块'平坦'的零区域, 这使得支持向量机的解具有洗属性, 而对率损失是光滑的单调递减函数, 不能导出类似支持向量的概念, 因此对率回归的解依赖于更多的训练样本, 其预测开销更大.
- 我们还可以把 \(0 / 1\) 损失函数替换成别的替代损失函数以得到其他学习模型, 这些模型的性质与所用的替代函数直接相关, 但他们具有一个共性: 优化目标中的第一项用来描述划分超平面的'间隔'大小, 另一项 \(\sum^{m}_{i = 1} l(f(x_{i}), y_{i})\) 用来表述训练集上的误差, 可写为更一般的形式:
\[\min_{f} \Omega (f) + C \sum^{m}_{i = 1} l(f(x_{i}), y_{i})\]
- 其中 \(\Omega (f)\) 称为'结构风险'(Structural Risk), 用于描述模型 \(f\) 的某些性质; 第二项 \(\sum^{m}_{i = 1} l(f(x_{i}), y_{i})\) 称为'经验风险'(Empirical Risk), 用于描述模型与训练数据的契合程度; \(C\) 用于对二者进行折中. 从经验风险最小化的角度来看, \(\Omega (f)\) 表述了我们希望获得具有何种性质的模型(例如希望获得复杂度较小的模型), 这位引入领域知识和用于意图提供了途径; 另一方面, 该信息有助于削减假设空间, 从而降低了最小化训练误差的过拟合风险. 从这个角度来说, 上式被称为'正则化'(Regularization)问题, \(\Omega (f)\) 称为正则化项, \(C\) 则称为正则化常数. \(L_{p}\) 范数(Norm)是常用的正则化项, 其中 \(L_{2}\) 范数 \(||w||_{2}\) 倾向于 \(w\) 的分量取值尽量均衡, 即非零分量个数尽量稠密, 而 \(L_{0}\) 范数 \(||w||_{0}\) 和 \(L_{1}\) 范数 \(||w||_{1}\) 则倾向于 \(w\) 的分量尽量稀疏, 即非零分量个数尽量少.
写在后面
- 今天, 我们学习了SVM中的软间隔与正则化; 明天, 我们将继续学习SVM中的支持向量回归.