Robust Optimization

背景

稳健优化:利用凸理论、对偶理论中概念,使得凸优化问题中的解 对参数的bounded uncertainty有限不确定性(波动)不敏感

  • 稳健优化在机器学习涉及方面:不确定优化、过拟合

    • Connecting Consistency
    • Generalization Ability
    • Sparsity
    • Stability
  • 不确定性来源

    • 模型选择错误
    • 假设不成立
    • 忽略必要因素
    • 经验分布、函数无法正确估计整体分布
  • 过拟合判断依据

    • metric entropy
    • VC-dimension

对比

优化问题对问题参数的扰动非常敏感,以至于解经常不可行、次优

  • Stochastic Programming:使用概率描述参数不确定性,

  • 稳健优化则假设问题参数在某个给定的先验范围内随意变动

    • 不考虑参数的分布

    • 利用概率论的理论,而不用付出计算上的代价

策略(最优化问题)

  • $\mathcal{U}_i $:uncertainty set,不确定集

Computational Tractablity

稳健优化易解性:在满足标准或一点违反 Slater-like regularity conditions情况下,求解稳健优化问题 等同于求解对以下凸集$\mathcal{X(U)}$的划分(求出凸集)

  • 若存在高效算法能确定$x \in \mathcal{X(U)}$、或者能够提供 分离超平面,那么问题可以在多项式时间中求解

  • 即使所有的约束函数$f_i$都是凸函数,此时$\mathcal{X(U)}$ 也是凸集,也有可能没有高效算法能够划分出$\mathcal{X(U)}$

  • 然而在大部分情况下,稳健化后的问题都能高效求解下,和原 问题复杂度相当

复杂度说明

  • LP + Polyhedra Uncertainty:LP
  • LP + Ellipsoidal Uncertainty:SOCP
  • CQP + Ellipsoidal Uncertainty:SDP
  • SDP + Ellipsoodal Uncertainty:NP-hard
  • LP:Linear Program,线性规划
  • SOCP:Second-Order Cone Program,二阶锥规划
  • CQP:Convex Quadratic Program,凸二次规划
  • SDP:Semidefinite Program,半定规划
  • Polyhedra Uncertainty:多项式类型不确定
  • Ellipsodial Uncertainty:椭圆类型不确定
  • NP-hard:NP难问题,至少和NPC问题一样困难得问题

Example

Linear Programs with Polyhedral Uncertainty

概率解释、结果

  • 稳健优化的计算优势很大程度上来源于,其形式是固定的,不再 需要考虑概率分布,只需要考虑不确定集

  • 计算优势使得,即使不确定性是随机、且分布已知,稳健优化 仍然具有吸引力

  • 在一些概率假定下,稳健优化可以给出稳健化问题解的某些 概率保证,如:可行性保证(在给定约束下,解能以多大概率 不超过约束)

Uncertainty Set

Atomic Uncertainty Set

原子不确定集

Robust Optimization and Adversary Resistant Learning

即稳健优化在机器学习中处理不确定性(随机的、对抗性的)

  • 稳健优化中在机器学习中应用

  • 稳健学习在很多学习任务中都有提出

    • 学习和规划
    • Fisher线性判别分析
    • PCA

这里考虑经典的二分类软阈值SVM

Corrupted Location

  • 椭圆不确定集:随机导致的

  • 正则化项使用

    • 传统的二范数,一范数同样使用的稀疏的解
  • 概率解释:风险控制

Missing Data

  • 多项式不确定:对抗删除数据(alpha go)

  • 使用无效特征消去偏置

  • 对max损失取对偶得到min带入得到SOCP

Robust Optimization and Regularization

  • 统一从稳健优化的角度解释学习算法中的优秀性质

    • 正则化
    • 稀疏
    • 一致性
  • 指导寻找新的算法

    • 大数定理、中心极限定理表明即使各个特征上随机不确定项 是独立的,其本身也会有强烈的耦合倾向,表现出相同特征 、像会相互影响一样

    • 这促使寻找新的稳健算法,其中随机不确定项是耦合的

SVM

Kernel Function

Kernel Function

  • 对输入空间 $X$ (欧式空间 $R^n$ 的子集或离散集合)、特征空间 $H$ ,若存在从映射 $$
      \phi(x): X \rightarrow H
    
      K(x,z) = \phi(x) \phi(z)
    
    $$ 则称 $K(x,z)$ 为核函数、 $\phi(x)$ 为映射函数,其中 $\phi(x) \phi(z)$ 表示内积
  • 特征空间 $H$ 一般为无穷维
    • 特征空间必须为希尔伯特空间(内积完备空间)

映射函数 $\phi$

  • 映射函数 $\phi$:输入空间 $R^n$ 到特征空间的映射 $H$ 的映射

  • 对于给定的核 $K(x,z)$ ,映射函数取法不唯一,映射目标的特征空间可以不同,同一特征空间也可以取不同映射,如:

    • 对核函数 $K(x, y) = (x y)^2$ ,输入空间为 $R^2$ ,有

    • 若特征空间为$R^3$,取映射

      或取映射

    • 若特征空间为$R^4$,取映射

核函数 $K(x,z)$

  • Kernel Trick 核技巧:利用核函数简化映射函数 $\phi(x)$ 映射、内积的计算技巧

    • 避免实际计算映射函数
    • 避免高维向量空间向量的存储
  • 核函数即在核技巧中应用的函数

    • 实务中往往寻找到的合适的核函数即可,不关心对应的映射函数
    • 单个核函数可以对应多个映射、特征空间
  • 核技巧常被用于分类器中

    • 根据 Cover’s 定理,核技巧可用于非线性分类问题,如在 SVM 中常用
    • 核函数的作用范围:梯度变化较大的区域
      • 梯度变化小的区域,核函数值变化不大,所以没有区分能力
  • Cover’s 定理可以简单表述为:非线性分类问题映射到高维空间后更有可能线性可分

正定核函数

  • 设 $X \subset R^n$,$K(x,z)$ 是定义在 $X X$的对称函数,若 $\forall x_i \in \mathcal{X}, i=1,2,…,m$,$K(x,z)$ 对应的 Gram* 矩阵 $$
      G = [K(x_i, x_j)]_{m*m}
    
    $$ 是半正定矩阵,则称 $K(x,z)$ 为正定核
  • 可用于指导构造核函数
    • 检验具体函数是否为正定核函数不容易
    • 正定核具有优秀性质
      • SVM 中正定核能保证优化问题为凸二次规划,即二次规划中矩阵 $G$ 为正定矩阵

欧式空间核函数

Linear Kernel

线性核:最简单的核函数

  • 特点
    • 适用线性核的核算法通常同普通算法结果相同
      • KPCA 使用线性核等同于普通 PCA

Polynomial Kernel

多项式核:non-stational kernel

  • 特点

    • 适合正交归一化后的数据
    • 参数较多,稳定

      todo

  • 应用场合

    • SVM:p 次多项式分类器

Gaussian Kernel

高斯核:radial basis kernel,经典的稳健径向基核

  • $\sigma$:带通,取值关于核函数效果,影响高斯分布形状
    • 高估:分布过于集中,靠近边缘非常平缓,表现类似像线性一样,非线性能力失效
    • 低估:分布过于平缓,失去正则化能力,决策边界对噪声高度敏感
  • 特点

    • 对数据中噪声有较好的抗干扰能力
  • 对应映射:省略分母

    即高斯核能够把数据映射至无穷维

  • 应用场合

    • SVM:高斯radial basis function分类器

Exponential Kernel

指数核:高斯核变种,仅去掉范数的平方,也是径向基核

  • 降低了对参数的依赖性
  • 适用范围相对狭窄

Laplacian Kernel

拉普拉斯核:完全等同于的指数核,只是对参数$\sigma$改变敏感 性稍低,也是径向基核

ANOVA Kernel

方差核:径向基核

  • 在多维回归问题中效果很好

Hyperbolic Tangent/Sigmoid/Multilayer Perceptron Kernel

Sigmoid核:来自神经网络领域,被用作人工神经元的激活函数

  • 条件正定,但是实际应用中效果不错

  • 参数

    • $\alpha$:通常设置为$1/N$,N是数据维度
  • 使用Sigmoid核的SVM等同于两层感知机神经网络

Ration Quadratic Kernel

二次有理核:替代高斯核,计算耗时较小

Multiquadric Kernel

多元二次核:适用范围同二次有理核,是非正定核

Inverse Multiquadric Kernel

逆多元二次核:和高斯核一样,产生满秩核矩阵,产生无穷维的 特征空间

Circular Kernel

环形核:从统计角度考虑的核,各向同性稳定核,在$R^2$上正定

Spherical Kernel

类似环形核,在$R^3$上正定

Wave Kernel

波动核

  • 适用于语音处理场景

Triangular/Power Kernel

三角核/幂核:量纲不变核,条件正定

Log Kernel

对数核:在图像分隔上经常被使用,条件正定

Spline Kernel

样条核:以分段三次多项式形式给出

B-Spline Kernel

B-样条核:径向基核,通过递归形式给出

  • $x_{+}^d$:截断幂函数

Bessel Kernel

Bessel核:在theory of function spaces of fractional smoothness 中非常有名

  • $J$:第一类Bessel函数

Cauchy Kernel

柯西核:源自柯西分布,是长尾核,定义域广泛,可以用于原始维度 很高的数据

Chi-Square Kernel

卡方核:源自卡方分布

Histogram Intersection/Min Kernel

直方图交叉核:在图像分类中经常用到,适用于图像的直方图特征

Generalized Histogram Intersection

广义直方图交叉核:直方图交叉核的扩展,可以应用于更多领域

Bayesian Kernel

贝叶斯核:取决于建模的问题

Wavelet Kernel

波核:源自波理论

  • 参数

    • $c$:波的膨胀速率
    • $a$:波的转化速率
    • $h$:母波函数,可能的一个函数为
  • 转化不变版本如下

离散数据核函数

String Kernel

字符串核函数:定义在字符串集合(离散数据集合)上的核函数

  • $[\phin(s)]_n = \sum{i:s(i)=u} \lambda^{l(i)}$:长度 大于等于n的字符串集合$S$到特征空间 $\mathcal{H} = R^{\sum^n}$的映射,目标特征空间每维对应 一个字符串$u \in \sum^n$

  • $\sum$:有限字符表

  • $\sum^n$:$\sum$中元素构成,长度为n的字符串集合

  • $u = s(i) = s(i1)s(i_2)\cdots s(i{|u|})$:字符串s的 子串u(其自身也可以用此方式表示)

  • $i =(i1, i_2, \cdots, i{|u|}), 1 \leq i1 < i_2 < … < i{|u|} \leq |s|$:序列指标

  • $l(i) = i_{|u|} - i_1 + 1 \geq |u|$:字符串长度,仅在 序列指标$i$连续时取等号($j$同)

  • $0 < \lambda \leq 1$:衰减参数

  • 两个字符串s、t上的字符串核函数,是基于映射$\phi_n$的 特征空间中的内积

    • 给出了字符串中长度为n的所有子串组成的特征向量的余弦 相似度
    • 直观上,两字符串相同子串越多,其越相似,核函数值越大
    • 核函数值可由动态规划快速计算(只需要计算两字符串公共 子序列即可)
  • 应用场合

    • 文本分类
    • 信息检索
    • 信物信息学

函数说明

约定

  • I:示性/指示函数

    • 满足条件时取1,否则取0
  • sign:符号函数

    • >0:取1
    • <0:取-1

Auto-Encoders

自编码机/稀疏编码/堆栈自编码器

  • 起源:编码理论可以应用于视觉皮层感受野,大脑主要视觉皮层 使用稀疏原理创建可以用于重建输入图像的最小基函数子集

  • 优点

    • 简单技术:重建输入
    • 可堆栈多层
    • 直觉型,基于神经科学研究
  • 缺点

    • 贪婪训练每层
    • 没有全局优化
    • 表现较监督学习差
    • 多层容易失效
    • 输入的重建可能不是学习通用表征的理想metric

EM算法

总述

expectation maximization algorithm:含有隐变量的概率模型 参数的极大似然估计法、极大后验概率估计法

  • 模型含有latent variable(潜在变量)、hidden variable (隐变量)似然函数将没有解析解

  • 所以EM算法需要迭代求解,每次迭代由两步组成

    • E步:求期望expectation
    • M步:求极大maximization
  • 模型变量都是observable variable、给定数据情况下,可以 直接使用极大似然估计、贝叶斯估计

EM算法

对含有隐变量的概率模型,目标是极大化观测数据(不完全数据) $Y$关于参数$\theta$的对数似然函数,即极大化

  • $Y$:观测变量数据
  • $Z$:隐随机变量数据(未知)
  • $Y,Z$合在一起称为完全数据
  • $P(Y,Z|\theta)$:联合分布
  • $P(Z|Y,\theta)$:条件分布
  • 但是极大化目标函数中包括未观测数据$Z$、求和(积分)的 对数,直接求极大化非常困难
  • EM算法通过迭代逐步近似极大化$L(\theta)$

推导

  • 假设第i次迭代后$\theta$的估计值是$\theta^{(i)}$,希望 新估计值$\theta$能使$L(\theta)$增加,并逐步增加到极大值 ,考虑两者之差

  • 利用Jensen不等式有

  • 则$B(\theta, \theta^{(i)})$是$L(\theta)$的一个下界,即

    并根据$B(\theta, \theta^{(i)})$定义有

  • 则任意$\theta$满足 $B(\theta,\theta^{(i)}) > B(\theta^{(i)},\theta^{(i)})$ ,将满足$L(\theta) > L(\theta^{(i)})$,应选择 $\theta^{(i+1)}$使得$B(\theta,\theta^{(i)})$达到极大

    • 和$\theta$无关的常数项全部舍去
  • $Q(\theta, \theta^{(i)})$:Q函数,完全数据的对数似然函数 $logP(Y,Z|\theta)$,关于在给定观测$Y$和当前参数 $\theta^{(i)}$下,对未观测数据Z的条件概率分布 $P(Z|Y,\theta^{(i)})$

算法

  1. 选择参数初值$\theta^{0}$,开始迭代

  2. E步:记$\theta^{(i)}$为第$i$迭代时,参数$\theta$的估计值 ,在第$i+1$步迭代的E步时,计算Q函数 $Q(\theta, \theta^{(i)})$

  3. M步:求使得Q函数极大化$\theta$作为第$i+1$次估计值 $\theta^{(i+1)}$

  4. 重复E步、M步直到待估参数收敛

  • 算法初值可以任意选择,但EM算法对初值敏感

  • E步:参数值估计缺失值分布,计算Q函数(似然函数)

  • M步:Q函数取极大得新参数估计值

  • 收敛条件一般是对较小正数$\epsilon$,满足 $|\theta^{(i+1)} - \theta^{(i)}| < \epsilon$或 $|Q(\theta^{(i+1)},\theta^{(i)}) - Q(\theta^{(i)},\theta^{(i)})| < \epsilon$

EM算法特点

EM算法优点

  • EM算法可以用于估计含有隐变量的模型参数
  • 非常简单,稳定上升的步骤能非常可靠的找到最优估计值
  • 应用广泛,能应用在多个领域中
    • 生成模型的非监督学习

EM算法缺点

  • EM算法计算复杂、受外较慢,不适合高维数据、大规模数据集
  • 参数估计结果依赖初值,不够稳定,不能保证找到全局最优解

算法收敛性

定理1

  • 设$P(Y|\theta)$为观测数据的似然函数,$\theta^{(i)}$为 EM算法得到的参数估计序列,$P(Y|\theta^{(i)}),i=1,2,…$ 为对应的似然函数序列,则$P(Y|\theta^{(i)})$是单调递增的
  • 由条件概率

  • 则对数似然函数有

    • $H(\theta, \theta^{(i)}) = \sum_Z log P(Z|Y,\theta) P(Z|Y,\theta)$
    • $Q(\theta, \theta^{(i)})$:前述Q函数
    • $logP(Y|\theta)$和$Z$无关,可以直接提出
  • 分别取$\theta^{(i+1)}, \theta^{(i)}$带入,做差

    • $\theta^{(i+1)}$使得$Q(\theta, \theta^{(i)})$取极大

    • 又有

定理2

  • 设$L(\theta)=log P(Y|\theta)$为观测数据的对数似然函数, $\theta^{(i)},i=1,2,…$为EM算法得到的参数估计序列, $L(\theta^{(i)}),i=1,2,…$为对应的对数似然函数序列
    • 若$P(Y|\theta)$有上界,则$L(\theta^{(i)})$收敛到某 定值$L^{*}$
    • Q函数$Q(\theta, \theta^{‘})$与$L(\theta)$满足一定 条件的情况下,由EM算法得到的参数估计序列 $\theta^{(i)}$的收敛值$\theta^{*}$是$L(\theta)$的 稳定点
  • 结论1由序列单调、有界显然
  • Q函数$Q(\theta, \theta^{‘})$与$L(\theta)$的条件在大多数 情况下是满足的
  • EM算法收敛性包含对数似然序列$L(\theta^{(i)})$、参数估计 序列$\theta^{(i)}$的收敛性,前者不蕴含后者
  • 此定理只能保证参数估计序列收敛到对数似然序列的稳定点, 不能保证收敛到极大点,可选取多个不同初值迭代,从多个结果 中选择最好的

Gaussion Mixture Model

  • 高斯混合模型是指具有如下概率分布模型
    • $\alphak \geq 0, \sum{k=1}^K \alpha_k=1$:系数
    • $\phi(y|\theta_k)$:高斯分布密度函数
    • $\theta_k=(\mu_k, \sigma_k)$:第k个分模型参数
  • 用EM算法估计高斯混合模型参数 $\theta=(\alpha_1,…,\alpha_2,\theta_1,…,\theta_K)$

推导

明确隐变量

明确隐变量,写出完全数据对数似然函数

  • 反映观测数据$y_j$来自第k个分模型的数据是未知的

    • $j=1,2,\cdots,N$:观测编号
    • $k=1,2,\cdots,K$:模型编号
  • 则完全数据为

  • 完全数据似然函数为

    • $nk = \sum{j=1}^{N} \gamma_{j,k}$
    • $\sum_{k=1}^K n_k = N$
  • 完全数据的对数似然函数为

E步:确定Q函数

  • $E\gamma{j,k} = E(\gamma{j,k}|y,\theta)$:记为 $\hat \gamma_{j,k}$

带入可得

M步

求新一轮模型参数 $\theta^{(i+1)}=(\hat \alpha_1,…,\hat \alpha_2,\hat \theta_1,…,\hat \theta_K)$

  • $\hat \theta_k = (\hat \mu_k, \hat \sigma_k^2)$:直接求 偏导置0即可得
  • $\hat \alphak$:在$\sum{k=1}^K \alpha_k = 1$条件下求 偏导置0求得

算法

  • 输入:观测数据$y_1, y_2,\cdots, y_N$,N个高斯混合模型
  • 输出:高斯混合模型参数
  1. 取参数初始值开始迭代

  2. E步:依据当前模型参数,计算分模型k对观测数据$y_j$响应度

  3. M步:计算新一轮迭代的模型参数 $\hat mu_k, \hat \sigma_k^2, \hat \alpha_k$

  4. 重复2、3直到收敛

  • GMM模型的参数估计的EM算法非常类似K-Means算法
    • E步类似于K-Means中计算各点和各聚类中心之间距离,不过 K-Means将点归类为离其最近类,而EM算法则是算期望
    • M步根据聚类结果更新聚类中心

GEM

Maximization-Maximization Algorithm

Free Energy函数

  • 假设隐变量数据Z的概率分布为$\tilde P(Z)$,定义分布 $\tilde P$与参数$\theta$的函数$F(\tilde P, \theta)$如下
  • $H(\tilde P)=-E_{\tilde P} log \tilde P(Z)$:分布 $\tilde P(Z)$的熵
  • 通常假设$P(Y,Z|\theta)$是$\theta$的连续函数,则函数 $F(\tilde P,\theta)$是$\tilde P, \theta$的连续函数

定理1

  • 对于固定$\theta$,存在唯一分布$\tilde P\theta$,极大化 $F(\tilde P, \theta)$,这时$\tilde P\theta$由下式给出 并且$\tilde P_{\theta}$随$\theta$连续变化
  • 对于固定的$\theta$,求使得$F(\tilde P, \theta)$的极大, 构造Lagrange函数

    因为$\tilde P(Z)$是概率密度,自然包含两个约束

    即Lagrange方程中后两项

  • 对$\tilde P(Z)$求偏导,得

    令偏导为0,有

  • 则使得$F(\tilde P, \theta)$极大的$\tilde P_\theta(Z)$ 应该和$P(Y,Z|\theta)$成比例,由概率密度自然约束有

    而由假设条件,$P(Y,Z|\theta)$是$\theta$的连续函数

  • 这里概率密度函数$\tilde P(Z)$是作为自变量出现

  • 理论上对$\tilde P(Z)$和一般的复合函数求导没有区别, 但$E_{\tilde P}, \sum_Z$使得整体看起来非常不和谐

定理2

  • 若$\tilde P_\theta(Z) = P(Z|Y, \theta)$,则

定理3

  • 设$L(\theta)=log P(Y|\theta)$为观测数据的对数似然函数, $\theta^{(i)}, i=1,2,\cdots$为EM算法得到的参数估计序列, 函数$F(\tilde P,\theta)$如上定义
    • 若$F(\tilde P,\theta)$在$\tilde P^{}, \theta^{}$ 上有局部极大值,则$L(\theta)$在$\theta^{*}$也有局部 最大值
    • 若$F(\tilde P,\theta)$在$\tilde P^{}, \theta^{}$ 达到全局最大,则$L(\theta)$在$\theta^{*}$也达到全局 最大
  • 由定理1、定理2有

    特别的,对于使$F(\tilde P,\theta)$极大$\theta^{8}$有

  • 由$\tilde P_\theta$关于$\theta$连续,局部点域内不存在点 $\theta^{}$使得$L(\theta^{}) > L(\theta^{})$,否则 与$F(\tilde P, \theta^{})$矛盾

定理4

  • EM算法的依次迭代可由F函数的极大-极大算法实现
  • 设$\theta^{(i)}$为第i次迭代参数$\theta$的估计, $\tilde P^{(i)}$为第i次迭代参数$\tilde P$的估计,在第 i+1次迭代的两步为
    • 对固定的$\theta^{(i)}$,求$\tilde P^{(i)}$使得 $F(\tilde P, \theta^{(i)})$极大
    • 对固定的$\tilde P^{(i+1)}$,求$\theta^{(i+1)}$使 $F(\tilde P^{(t+1)}, \theta)$极大化
  • 固定$\theta^{(i)}$

  • 则固定$\tilde P^{(i+1)}$求极大同EM算法M步

GEM算法

  • 输入:观测数据,F函数
  • 输出:模型参数
  1. 初始化$\theta^{(0)}$,开始迭代

  2. 第i+1次迭代:记$\theta^{(i)}$为参数$\theta$的估计值, $\tilde P^{(i)}$为函数$\tilde P$的估计,求 $\tilde P^{(t+1)}$使$\tilde P$极大化$F(\tilde P,\theta)$

  3. 求$\theta^{(t+1)}$使$F(\tilde P^{(t+1)l}, \theta)$极大化

  4. 重复2、3直到收敛

次优解代替最优解

  • 输入:观测数据,Q函数
  • 输出:模型参数
  1. 初始化参数$\theta^{(0)}$,开始迭代

  2. 第i+1次迭代,记$\theta^{(i)}$为参数$\theta$的估计值, 计算

  3. 求$\theta^{(i+1)}$使

  4. 重复2、3直到收敛

  • 有时候极大化$Q(\theta, \theta^{(i)})$非常困难,此算法 仅寻找使目标函数值上升方向

ADMM求次优解

  • 输入:观测数据,Q函数
  • 输出:函数模型
  1. 初始化参数 $\theta^{(0)} = (\theta_1^{(0)},…,\theta_d^{(0)})$, 开始迭代

  2. 第i次迭代,记 $\theta^{(i)} = (\theta_1^{(i)},…,\theta_d^{(i)})$, 为参数$\theta = (\theta_1,…,\theta_d)$的估计值,计算

  3. 进行d次条件极大化

    1. 在$\theta1^{(i)},…,\theta{j-1}^{(i)},\theta_{j+1}^{(i)},…,\theta_d^{(i)}$ 保持不变条件下 ,求使$Q(\theta, \theta^{(i)})$达到极大的 $\theta_j^{(i+1)}$

    2. j从1到d,进行d次条件极大化的,得到 $\theta^{(i+1)} = (\theta_1^{(i+1)},…,\theta_d^{(i+1)})$ 使得

  4. 重复2、3直到收敛

K-Nearest Neighor

K-NN

  • 输入:p维实例特征向量

    • 将样本点视为p维特征空间的中点
  • 输出:实例类别,可以取多类别

  • 基本思想

    • 在已有数据中找到与$X_0$相似的若干个观测 $(X_1, X_2, …, X_k)$,称为$X_0$的近邻
    • 对近邻$(X_1, X_2, …, X_k)$的输出变量 $(y_1, y_2, …, y_k)$,计算诸如算术平均值 (加权平均值、中位数、众数),作为新观测$X_0$输出 变量取值$y_0$的预测值
  • 特点

    • k近邻不具有显式学习过程、简单、直观
    • 不需要假设$y=f(X)$函数体形式,实际上是利用训练数据集 对特征空间进行划分

局部方法

k-NN是一种“局部”方法,仅适合特征空间维度较低的情况

  • 给定k的情况下,在高维空间中,需要到更远的区域寻找近邻, 局部性逐渐丧失,近似误差变大

  • 如:n个观测均匀分布在超立方体中,确定k后即确定$X_0$需要 寻找的近邻个数占总观测的比率r,即近邻覆盖的体积

    • 考虑$X_0$在原点,则近邻分布的小立方体边期望长度为

    • 可以看出:减少近邻比例(数量)没有帮助,还会使得近似 误差变大,只能通过增大样本量解决

  • 特征选择有必要

特征选择

  • 变量本身考察

    • low variance filter:剔除标准差小于阈值数值型变量
    • missing values ratio:剔除缺失值大于阈值的变量
    • 剔除众数比率大于阈值的分类型变量
  • 变量与输出变量相关性角度考察

    • high correlation filter
  • 对预测误差影响角度考察

    • Wrapper方法:逐个选择使错误率、均方误差下降最快变量 ,可使用Forward Feature Elimination

k-NN模型

K-NN是使用模型:实际上对应于特征空间的划分

  • 模型包括3个基本要素,据此划分特征空间,确定特征空间中 每个点所属类
    • k值选择
    • 距离度量:参见data_science/ref/functions
    • 分类决策规则

k值选择

k值选择对k-NN方法有重大影响

  • 较小k值:相当于使用较小邻域中训练实例进行预测

    • 复杂模型,容易发生过拟合
    • approximation error较小:只有于输入实例近、相似的 训练实例才会对预测结果有影响
    • estimation error较大:预测结果对近邻实例点非常敏感
  • 较大k值:相当于使用较大邻域中训练实例进行预测

    • 简单模型
    • 估计误差较小
    • 近似误差较大:同输如实例远、相似程度差的训练实例也会 对预测结果有影响

k=1

只使用一个近邻做预测

  • 找到距离$X_0$最近的近邻$X_i$,用其取值作为预测值

  • 模型简单、效果较理想

    • 尤其适合特征空间维度较低、类别边界不规则情况
    • 只根据单个近邻预测,预测结果受近邻差异影响极大,预测 波动(方差)大,稳健性低
  • 预测错误的概率不高于普通贝叶斯方法的两倍

    • $P(y=1|X=X_0)$:普通贝叶斯方法做分类预测,预测结果 为1的概率
    • 1-NN方法犯错的概率就是$X_0$、$X_i$二者实际值不同的 概率????

k=N

使用训练样本整体做预测

  • 无论输入实例,预测结果完全相同

    • 对分类预测,预测结果为“众数”
    • 对回归预测,预测结果为“平均数”
  • 模型过于简单、效果不好

    • 忽略训练实例中大量信息
    • “稳健性”极好:预测值基本不受近邻影响,无波动

决策规则

分类决策规则

Majority Voting Rule

多数表决规则:等价于经验风险最小化

  • 分类损失函数为0-1损失函数,分类函数为 $f: \mathcal{R^n} \rightarrow {c_1, c_2, \cdots}$

  • 误分类概率$P(Y \neq f(X)) = 1 - P(Y=f(X))$

  • 给定实例$x \in \mathcal{X}$的误分率为

    • $N_k(x)$:最近邻k个实例构成集合
    • $c_j$:涵盖$N_k(x)$区域的类别
    • $I$:指示函数
  • 为使误分率(经验风险)最小,应选择众数

  • 经验风险的构造中,前提是近邻被认为属于相同类别$c_j$,
  • 当然这个假设是合理的,因为k-NN方法就是认为近邻类别相同, 并使用近邻信息预测
  • $c_j$的选择、选择方法是模型选择的一部分,不同的$c_j$会 有不同的经验风险

数值决策规则

算法

  • 实现k近邻法时,主要问题是对训练数据进行快速k近邻搜索, 尤在特征空间维数大、训练数据量大

  • 考虑使用特殊的结构存储训练数据,减少计算距离次数,提高 k近邻搜索效率

linear scan

线性扫描:最简单的实现方法

  • 需要计算输入实例与每个训练实例的距离,训练集较大时计算 非常耗时

kd树最近邻搜索

  • 输入:已构造kd树
  • 输出:x的最近邻
  • 在kd树种找出包含目标点x的叶节点的

    • 从根节点出发,比较对应坐标,递归进行访问,直到叶节点 为止

    • 目标点在训练样本中不存在,必然能够访问到叶节点

  • 以此叶节点为“当前最近点”

    • 目标点在此叶节点中点所在的区域内,且区域内只有该 叶节点中点
  • 回溯,并在每个节点上检查

    • 如果当前节点保存实例点比当前最近点距离目标的更近, 更新该实例点为“当前最近点”

    • 检查该节点另一子区域是否可能具有更近距离的点

      • 即其是否同以目标点为圆心、当前最短距离为半径圆 相交
      • 只需要比较目标点和相应坐标轴距离和最短距离即可
    • 若二者相交,则将目标节点视为属于该子区域中点, 进行最近邻搜索,递归向下查找到相应叶节点,重新 开始回退

    • 若二者不相交,则继续回退

  • 退回到根节点时,搜索结束,最后“当前最近点”即为最近邻点

  • 这里涉及到回溯过程中,另一侧子域是否访问过问题,可以通过 标记、比较相应轴坐标等方式判断
  • k>1的情况类似,不过检测时使用最远近邻,新近邻需要和所有 原近邻依次比较

加权k-NN

变量重要性

计算变量的加权距离,重要变量赋予较高权重

  • 变量重要性:Backward Feature Elimination得到各变量 重要性排序

    • $e_i$:剔除变量i之后的均方误差(错误率)
  • 加权距离:$dw(x,y)=\sqrt {\sum{i=1}^{p} w^{(i)}(x_i - y_i)^2}$

观测相似性

目标点的k个近邻对预测结果不应有“同等力度”的影响,与$X_0$越 相似的观测,预测时重要性(权重)越大

  • 权重:用函数$K(d)$将距离d转换相似性,$K(d)$应该有特性

    • 非负:$K(d) \geqslant 0, d \in R^n$
    • 0处取极大:$max K(d) = K(0)$
    • 单调减函数,距离越远,相似性越小
    • 核函数符合上述特征
    • 且研究表明除均匀核外,其他核函数预测误差差异均不明显

步骤

  • 依据函数距离函数$d(Z_{(i)}, Z_0)$找到$X_0$的k+1个近邻

    • 使用第k+1个近邻距离作为最大值,调整距离在0-1之间
  • 依据函数$w_i=K(d)$确定k各近邻的权重

  • 预测

    • 回归预测
    • 分类预测:多数表决原则

Approximate Nearest Neighbor

相似最近邻

Decision Tree

决策树概述

结构

  • 决策树分析结论、展示方式类似一棵倒置的树
  • 决策树由 nodedirected edge 组成

    • internal node:内部节点,表示特征、属性
    • leaf node:叶子节点,表示一个类
  • 对训练数据进行分类

    • 从根节点开始,对实例某特征进行测试,根据测试结果将实例分配到其子节点,对应该特征一个取值
    • 递归地对实例进行分配,直至到达叶子节点,将实例分到叶节点地类中
  • 对新数据的预测

    • 从决策树的树根到树叶搜索,确定数所的叶子节点
    • 利用叶子节点中训练数据集预测
      • 分类型:众数
      • 数值型:均值

本质

决策树:本质上是从训练数据中归纳出一组分类规则

  • 与训练数据不矛盾的分类规则(即能对训练数据正确分类)可能有多个、没有,需要找到矛盾较小、泛化能力较好的
  • 决策树学习也是由训练数据集估计条件概率模型,需要寻找对训练数据有很好拟合、对未知数据有很好预测的模型

分类规则集合

  • 决策树可以看作是 if-then 规则的集合:体现输入、输出变量逻辑关系
  • 决策树根节点到叶节点每条路径构成一条规则
  • 路径上内部节点的特征对应规则的条件,叶节点对应规则结论
  • 决策树的路径或其对应的 if-then 规则集合 互斥且完备,即每个实例有且仅有一条路径覆盖

条件概率分布

  • 决策树可以表示定义在特征空间、类空间上的条件概率分布
  • 此条件概率分布定义在特征空间的一个划分(有限)上

    • 决策树中一条路径(叶节点)对应划分中一个单元
    • 每个单元定义的概率分布就构成一个条件概率分布
  • 条件概率分布由 各单元的给定条件下,各类的条件概率分布组成

    • $P(Y|X)$:$X$ 为表示特征的随机变量(取值各个单元),$Y$ 表示类的随机变量
    • 各叶节点上的条件概率往往偏向于某类,决策树分类时将属于该节点实例分为该类

特点

  • 优势

    • 能有效处理分类型输入变量
    • 能够实现非线性分割
    • 模型具有可读性,分类速度块
  • 问题

    • 充分生长的决策有高方差,预测不稳定
    • 剪枝可以提高预测稳健性,但是预测精度可能会下降

决策树构建

  • 从所有可能决策树中选取最优决策树是NP完全问题

    • 所以实际决策树算法通常采用 启发式 算法、贪心算法,近似求解最优化问题,得到 sub-optimal 决策树
    • 从包含所有数据的根节点开始,递归的选择 当前 最优特征、分割点对训练数据进行分割,使得各子数据集有当前最好分类
    • 此样本不断分组过程对应特征空间的划分、决策树的构建
  • 原则:使节点/组内观测取值异质性下降最大,从而确定

    • 最佳划分特征
    • 特征的最佳分割点
算法 ID3 C4.5 CART CHAID
特征 分类 分类、连续 同左 同左
输出 分类 分类 分类、回归 分类
连续值处理 - 二分法 同左 等距分组
分叉 多叉 多叉 二叉 多叉
分裂指标 信息增益 信息增益比 GINI 不纯度 相关性
前剪枝 - 叶节点数量 树深度、节点样本数量 -
后剪枝 - 置信度、减少-误差法 MCCP -

异质性衡量:划分准则

  • 信息增益
  • 信息增益比:避免信息增益倾向于取值较多特征
    • 若样本类别严格服从分布,则信息增益和信息增益比选择应完全相同
    • 但由于偶然性、样本数量等原因,各特征取值的样本数量往往不完全符合分布
    • 由信息增益定义可看出,各特征取值样本数量较小时,数量变动影响更大,而特征取值较多更可能出现各取值对应样本数量较小
  • GINI 指数
  • 研究表明,不同决策树的划分准则对泛化性能影响有限,信息增益和 GINI 指数理念分析表明,其仅在 2% 情况下有所不同

特征变量处理

  • 离散值处理

    • 全分类:各类别分别独立作为分支,构建节点
    • 切分二分:将类别分为的两组
    • 是否二分:某取值作为一个分支,其余作为另一分支
  • 连续值处理

    • 二分法:选择阈值,按照阈值将连续值分为两部分
      • 精确阈值选取:检查所有可能阈值点,即所有不同取值点的中间点
      • 近似阈值选取
    • 近似分裂算法:选取一组阈值,将特征划分至不同桶内,类似分类值处理
      • 等频阈值:分位数
      • 等距阈值:linespace

缺失值处理

  • 缺失值处理需要解决:异质性衡量指标计算、特征缺失样本划分问题
  • 异质性衡量指标计算:使用特征未缺失样本权重对指标加权(以信息增益为例)

    • $Y, X, w_x$:样本类别,特征,样本权重
    • $D, \tilde D, \tilde {D_k}, \tilde {D^v}$:样本全集,在特征 $X$ 上无缺失样本子集,属于 $k$ 类样本子集,在特征 $X$ 上取 $v$ 样本子集
  • 特征缺失样本划分

    • 划分至所有节点,其权重设置为 $\tilde {r_v} * w_x$
      • $\tilde {r_v}$ 为节点 $v$ 的权重
      • 即将特征缺失样本节点权重比例划分至各节点

剪枝

树剪枝:在决策树的学习过程中,将已生成的树进行简化的过程

  • 最小化 RSS、最大化置信目标下,会导致庞大的树

    • 对训练数据拟合好
    • 模型复杂度越高
    • 推广能力差
    • 比较难理解、解释
  • 通过剪枝得到恰当的树,具备一定的预测精度、复杂程度恰当,代价(误差)和复杂度之间的权衡是必要的

  • Pre-pruning 预剪枝:在决策树分裂过程中,不分裂不满足分裂条件的节点,限制决策树充分生长

    • 分裂条件
      • 最大深度
      • 叶节点数量
      • 样本量最小值
      • 异质性下降阈值
    • 预剪枝基于“贪心”的禁止划分,可能降低过拟合、减少时间开销,但也可能导致欠拟合
  • Post-pruning 后剪枝:决策分裂完成后,根据一定规则剪去不具备普遍性的子树

    • 比预剪枝决策保留更多分支,欠拟合风险小、泛化性能好
    • 决策树生成局部模型,决策树剪枝学习整体模型
  • 剪枝方法、程度对泛化性能影响显著,尤其是数据带有噪声

自底向上剪枝

  • 自底向上剪去所有无法改善评价准则的非叶节点分支(转为叶节点)

    • 最简单后剪枝策略
    • 若已使用一定预剪策略,则该策略价值不大
  • 特点

    • 须在生成完全决策树之后自底向上逐个考察非叶节点,时间开销大

Minimal Cost Complexity Pruning

  • $N_t$:树 $T$ 的第 $t$ 个叶子节点中样本点数量
  • $N_{t,k}$:树 $T$ 的第 $t$ 个叶子节点第 $k$ 类样本点数量
  • $H_t(T)$:树 $T$ 的第 $t$ 个叶子节点熵
  • $C(T)$:模型对训练数据的预测误差
  • $|T|$:用叶节点数量衡量的模型复杂度
  • $\alpha \geq 0$:控制模型复杂度对模型总损失影响,每个叶节点带来的复杂度
  • 极小化损失复杂度剪枝
    • 损失函数:正则化的极大似然函数
    • 此策略即在给定 $\alpha$ 的情况下,选择损失函数最小树

剪枝步骤

  • 输入:生成算法产生的整个树 $T$,参数 $\alpha$
  • 输出:修剪后的子数 $T_\alpha$
  • 计算每个节点的经验熵
  • 递归的从树的叶节点向上回缩
    • 若 $C\alpha(T{before}) \geq C\alpha(T{after})$,则剪枝
    • 不断回缩直到根节点,选取损失函数最小的子树 $T_\alpha$
  • 算法只需要比较节点、节点子树之间损失函数之差即可,计算可以在局部进行
  • 算法可以由动态规划算法实现

超参选择

  • 对给定超参 $\alpha$,存在使损失函数 $C\alpha(T)$ 最小子树 $T\alpha$,且此最优子树唯一

    • $\alpha$ 偏大时,最优子树 $T_\alpha$ 偏小
    • $\alpha=0$ 时完整树最优,$\alpha \rightarrow \infty$ 时单节点树最优
  • 对决策树种每个节点 $t$,通过以下策略生成 $g(t)$

    • $C_{\alpha}(T^t) = C(T^t) + \alpha|T^t|$:以 $t$ 为根节点的子树 $T^t$ 损失
    • $C_{\alpha}(t) = C(t) + \alpha$:对 $t$ 剪枝之后,仅包含单个节点 $t$ 的正则损失
    • 则 $\alpha=g(t) = \frac {C(t)-C(T^t)} {|T^t|-1}$ 时,单节点 $t$ 和子树 $T^t$ 损失相同
  • 考虑以上 $g(t)$ 序列

    • $\alpha^t=g(t)$ 表示对 $T^{(0)}$ 中每个内部节点 $t$ 剪枝后,整体损失函数值减少程度
    • 可以证明,对以上 $\alpha > 0$ 序列排序,按 $0, \alpha^{(1)}, \cdots, \alpha^{(N)}$ 依次进行剪枝,对应最优子树序列 $T^{(0)}, T^{(1)},\cdots, T^{(N)}$ 嵌套
    • 通过交叉验证法在独立的验证数据集上对子树进行测试,选择最优决策树

完整剪枝+超参选择

  • 输入:CART 算法生成决策树 $T^{(0)}$
  • 输出:最优决策树 $T_\alpha$
  • 自下而上地计算各内部节点 $t$ 对应 $C(T^t), |T^t|, g(t)$,对 $g(t)$ 升序排列得到 $\alpha^{(1)},\cdots,\alpha^{(N)}$

  • 置:$k=1, \alpha=\alpha^{(k)}, T=T^{(0)}$

  • 自上而下访问内部节点,若有 $g(t)=\alpha$,剪枝并计算新叶节点 $t$ 取值,得到对应最优树 $T^{(k)}$

    • 对于节点 $t$,其子树 $T^t$ 最大有效 $\alpha$ 也只是根节点对应 $g(t)$,更大没有价值
    • 自上而下剪枝避免无效剪枝
  • 置:$k+=1, \alpha=\alpha^{(k)}, T=T^{(k)}$

  • 若 $T$ 不是单节点树,则重复以上

  • 采用交叉验证法在子树序列中选取最优子树 $T_\alpha$

  • 也可从 $\alpha \leftarrow \infty$ 开始,逐渐减少,添枝 得到子树序列

决策树构建算法

  • 以下是一些经典的决策树(算法),但实际实现中往往不会严格按其构建决策树

  • 决策树算法常用递归描述、构建,完全决策树中止条件如下 (往往不会应用,而是以预剪枝条件作为中止条件)

    • 节点中样本属于同一类
    • 所有特征利用完毕
    • 无法找到满足划分阈值的特征、划分点

Iterative Dichotomiser 3

步骤

  • 输入:训练数据集 $D$,特征集 $A$,阈值 $\epsilon$
  • 输出:决策树 $T$
  • 以下情况下 $T$ 为单节点树,以 $D$ 中实例数最大的类(众数) $C_k$ 作为该节点的类标记,返回 $T$

    • $D$ 中所有实例属于同一类 $C_k$
    • $A = \varnothing$
  • 计算 $A$ 中各特征对 $D$ 的信息增益,选择信息增益最大的特征 $A_g$

    • 若 $A_g$ 的信息增益小于阈值 $\epsilon$,则置 $T$ 为单节点树,并将 $D$ 中实例数最大的类 $C_k$ 作为节点类标记,返回 $T$
    • 否则,对 $A_g$ 每个可能值 $a_m$,将 $D$ 分割为若干非空子集 $D_i$
      • 将 $D_i$ 中实例数最多的类作为标记,构建子节点
      • 对第 $i$ 个子节点,以 $D_i$ 为训练集,以 $A-{A_g}$ 为特征集,递归的构造子树 $T_i$ 并返回

特点

  • 只允许分类型特征,且每个特征只会被用于划分一次

    • 每次所有取值都会被用于建立子节点
    • ID3 树是多叉树,各个节点的分叉个数取决于使用特征
  • 只有树的生成,容易产生过拟合

  • 以信息增益作为划分训练数据集的特征,倾向于选择取值较多的特征进行划分

    • 理论上若特征取值严格符合分布,取值数量多寡,对信息增益没有影响
    • 由于各种误差的存在,样本不可能严格符合总体分布,取值数量较多特征,各取值对应样本数量较少,误差会使得条件经验熵倾向于偏小 (假设误差随机,可以大概证明)
  • 相当于用 极大似然法 进行概率模型的选择

C4.5

C4.5算法:ID3 算法继承者

  • ID3 差别

    • 用信息增益比代替信息增益用于选择特征,并且也被用于 前剪枝
      • 修正 ID3 倾向于使用取值较多的特征值分裂结点
    • 兼容数值型特征,使用二分法处理
  • C4.5 算法还包含 C4.5RulesC4.5 决策树转化为符号规则 - 各分支被重写为规则,并进行前件合并、删减

    • 最终规则集泛化性能可能优于原决策树

Classification and Regression Tree

CART 树:可用于分类和回归的二叉树

  • 特点

    • 二叉树
    • 可以用于分类、回归
      • 分类:众数代表节点,GINI 指数选择特征
      • 回归:均值代表节点,MSE 选择特征
    • 能较好的处理缺失值
  • CART 回归:平方误差最小化准则

    • $R_m$:空间划分出的第 $m$ 单元
    • $\hat c_m=avg(y_i|x_i \in R_m)$:第 $m$ 个单元上所有实例输出变量均值,此时平方误差最小
  • CART 分类:最小化基尼指数准则

    • $D_1 = {(x,y) \in D, X = a}$
    • $D_2 = D - D_1$
    • CART 树是二叉树,对分类变量只选择是否

CART回归步骤

  • 输入:训练数据集 $D$
  • 输出:回归树 $f(x)$
  • 选择最优切变量 $j$、切分点 $s$,即求解

    • $R_1(j,s) = {x|x^{(j)} \leq s}$
    • $R_2(j,s) = {x|x^{(j)} \geq s}$
    • $c_m = avg(y_i|x_i \in R_m)$:使得区域 $R_m$ 中平方误差最小,即其中样本点 $y_i$ 均值
    • 这里通过 遍历 得到
  • 对两个子区域 $R_1(j,s), R_2(j,s)$ 继续重复以上步骤,直至满足停止条件

  • 将输入空间划分为 $M$ 个区域 $R_1, R_2, \cdots, R_M$,生成决策 树

CART 分类步骤

  • 输入:训练数据集 $D$,停止计算条件
  • 输出:CART 决策树
  • 选择最优切变量 $j$、切分点 $s$

    • 对每个特征 $X$,对其所有取值 $a$ 计算条件基尼指数
    • 选择条件基尼指数最小的特征、对应的切分点,将训练数据依特征分配到两个子结点中
  • 对生成两个子节点递归分裂,直至满足停止条件

  • 生成 CART 决策树

Chi-squared Automatic Interaction Detector

CHAID 卡方自动交叉检验法:类似 ID3 算法,但利用卡方统计确定特征变量

特点

  • 通过卡方统计量选择最显著特征变量作为划分特征

    • 分类目标变量:列联分析,卡方检验
    • 数值目标变量:回归分析,F检验
  • 特征预处理

    • 分类型特征变量:根据卡方统计量显著性、组数量等考虑拆分、合并分组
    • 数值型特征变量:均分分组
  • 是从相关性显著角度确定特征变量

    • 对决策树分支优化明显
    • 可用特征变量与目标相关性显著显著性作为停止分裂的标准

QUEST

Quick Unbiased Efficient Statical Tree:类似 CHAID 算法,但对选择特征、划分点依据不同,仅能处理分类目标变量

特点

  • 类似 CHAID,选择最显著(p 值)的特征变量作为划分特征

    • 分类特征变量:连列分析,卡方检验
    • 数值特征变量:方差分析,F检验
  • 划分点选择

    • 分类特征变量:映射为 one-hot 向量后,用判别分析求解划分向量,再映射回划分取值
  • 目标变量多分类

    • 为每个类别计算特征均值,使用均值聚类将其简化为二分类
    • 只需要为节点内样本的、用待划分特征计算均值
  • 运行速度快于 CART

Naive Bayes

Naive Bayes Classifier

朴素贝叶斯:在训练数据集上学习联合概率分布$P(X,Y)$,利用后验 分布作为结果

  • 朴素:条件概率分布有条件独立性假设,即特征在类别确定 下条件独立

模型

  • 输出Y的先验概率分布

    • 先验概率是指输出变量,即待预测变量的先验概率分布, 反映其在无条件下的各取值可能性
    • 同理所有的条件概率中也是以输出变量取值作为条件
  • 条件概率分布为

    • $D$:用于分类特征数量

    其中有指数数量级的参数(每个参数的每个取值都需要参数)

  • 因此对条件概率分布做条件独立性假设,即分类特征在类别 确定条件下是独立的

    • 条件独立性假设是比较强的假设,也是朴素的由来
    • 其使得朴素贝叶斯方法变得简单,但有时也会牺牲准确率

    • 以上即可得到联合概率分布$P(X,Y)$

    • 朴素贝叶斯学习到的联合概率分布$P(X,Y)$是数据生成的 机制,即其为生成模型

策略

策略:选择使得后验概率最大化的类$c_k$作为最终分类结果

  • $K$:输出类别数量
  • 后验概率根计算根据贝叶斯定理计算

  • 考虑上式中分母对所有$c_k$取值均相等,则最终分类器为

    • 即分类时,对给定输入$x$,将其归类为后验概率最大的类

策略性质

后验概率最大化等价于0-1损失的经验风险最小化

  • 经验风险为

  • 为使经验风险最小化,对训练集中每个$X=x$取极小化,对每个 个体$(x,y)$有

    即后验概率最大化

算法

极大似然估计

  • 先验概率的极大似然估计为

  • 条件概率的极大似然估计为

    • $a_{j,l}$;第j个特征的第l个可能取值
    • $S_j$:第j个特征的可能取值数量
    • $I$:特征函数,满足条件取1、否则取0
算法
  • 输入:训练数据T
  • 输出:朴素贝叶斯分类器
  1. 依据以上公式计算先验概率、条件概率

  2. 将先验概率、条件概率带入,得到朴素贝叶斯分类器

贝叶斯估计

  • 条件概率贝叶斯估计

    • $\lambda \geq 0$
    • $\lambda=0$时就是极大似然估计
    • 常取$\lambda=1$,此时称为Laplace Smoothing
    • 以上设计满足概率分布性质
  • 先验概率贝叶斯估计

  • 极大似然估计可能出现所需估计概率值为0,影响后验概率计算 结果,贝叶斯估计能够避免这点

Semi-Naive Bayes Classifier

半朴素贝叶斯分类器:适当考虑部分特征之间的相互依赖信息

  • Semi-Naive Bayes可以视为是利用规则对变量加权,以 此来体现相关变量的协同影响

    • 特别的:权值为0/1即为变量筛选

One-Depentdent Estimator

独依赖估计:假设特征在类别之外最多依赖一个其他特征,这是半 朴素贝叶斯分类器中最常用的一种策略

  • $pa_j$:特征$X^{(j)}$依赖的父特征
  • 若父特征已知,同样可以使用条件概率计算 $P(X^{(j)}=x^{(j)} | Y=c_k, pa_j)$

  • ODE形式半朴素贝叶斯分类器相应的策略为

  • 根据确定各特征父特征的不同做法,可以分为不同类型的独依赖 分类器

    • Super-Parent ODE:假设所有特征都依赖同一父特征
    • Averaged ODE:类似随机森林方法,尝试将每个属性作为 超父特征构建SPODE
    • Tree Augmented Naive Bayes:基于最大带权生成树发展

SPODE

SPODE:每个特征只与其他唯一一个特征有依赖关系

  • $pa$:所有特征共有的依赖父特征

AODE

AODE:以所有特征依次作为超父特征构建SPODE,以具有足够训练 数据支撑的SPODE集群起来作为最终结果

  • 这里只选取训练数据足够,即取特征$X^{(i)}$某个取值的样本 数量大于某阈值的SPODE加入结果

TAN

TAN步骤
  • 计算任意特征之间的互信息

  • 以特征为节点构建完全图,节点边权重设为相应互信息

  • 构建此完全图的最大带权生成树

    • 挑选根变量
    • 将边设置为有向
  • 加入预测节点$Y$,增加从$Y$到每个属性的有向边

特点
  • 条件互信息$g(X^{(i)}, X^{(j)}| Y)$刻画了特征在已知类别 情况下的相关性

  • 通过最大生成树算法,TAN仅保留了强相关属性之间的依赖性

回归变量选择

子集回归

  • 特征子集选择独立于回归模型拟合,属于封装器特征选择

最优子集

  • 特点
    • 可以得到稀疏的模型
    • 但搜索空间离散,可变性大,稳定性差

Forward Feature Elimination

前向变量选择

步骤

  • 初始变量集合$S_0 = \varnothing$
  • 选择具有某种最优特性的变量进入变量集合,得到$S_1$
  • 第j步时,从剩余变量中选择最优变量进入集合,得到$S_{j+1}$
  • 若满足终止条件,则结束,否则重复上步添加变量
    • j达到上限
    • 添加剩余变量均无法满足要求

Backward Feature Elimination

后向变量选择

步骤

  • 初始变量集合$S_0$包含全部变量
  • 从变量集合中剔除具有某种最差特性变量,得到$S_1$
  • 第j步时,从剩余变量中剔除最差变量,得到$S_{j+1}$
  • 若满足终止条件,则结束,否则重复上步添加变量
    • j达到上限
    • 剔除剩余变量均无法满足要求

范数正则化约束

  • 回归过程中自动选择特征,属于集成特征选择

Ridge Regression

  • 在L2范数约束下最小化残差平方
  • 作为连续收缩方法
    • 通过bias-variance trade-off,岭回归较普通最小二乘 预测表现更好
    • 倾向于保留所有特征,无法产生疏系数模型

LASSO

能够选择部分特征,产生疏系数模型

  • p > n时,即使所有特征都有用,LASSO也只能从中挑选n个
  • 如果存在相关性非常高的特征,LASSO倾向于只从该组中选择 一个特征,而且是随便挑选的
    • 极端条件下,两个完全相同的特征函数,严格凸的罚函数 (如Ridge)可以保证最优解在两个特征的系数相等,而 LASSO的最优解甚至不唯一

Elastic Net

Naive Elastic Net

  • 弹性网在Lasso的基础上添加系数的二阶范数

    • 能同时做变量选择和连续收缩
    • 并且可以选择一组变量
  • 传统的估计方法通过二阶段估计找到参数

    • 首先设置ridge系数$\lambda_2$求出待估参数$\beta$, 然后做lasso的收缩
    • 这种方法有两次收缩,会导致估计偏差过大,估计不准
  • 弹性网可以变换为LASSO,因而lasso的求解方法都可以用于 elastic net

elastic_net

Least Angle Regression

  • 线性回归即找的一组系数能够用自变量的线性组合表示 因变量

Forward Selection/Forward Stepwise Regression

  • 从所有给定predictors中选择和y相关系数绝对值最大的变量 $x_{j1}$,做线性回归

    • 对于标准化后的变量,相关系数即为变量之间的内积
    • 变量之间相关性越大,变量的之间的夹角越小,单个变量 能解释得效果越好
    • 此时残差同解释变量正交
  • 将上一步剩余的残差作为reponse,将剩余变量投影到残差上 重复选择步骤

    • k步之后即可选出一组变量,然后用于建立普通线性模型
  • 前向选择算法非常贪心,可能会漏掉一些有效的解释变量,只是 因为同之前选出向量相关

Forward Stagewise

前向选择的catious版本

  • 和前向选择一样选择和y夹角最小的变量,但是每次只更新较小 步长,每次更新完确认和y夹角最小的变量,使用新变量进行 更新

    • 同一个变量可能会被多次更新,即系数会逐渐增加
    • 每次更新一小步,避免了前向选择的可能会忽略关键变量

Perceptron

  • 输入:实例的特征向量
  • 输出:实例类别+1、-1

感知机模型

感知机:线性二分类模型(判别模型)

  • $x \in \chi \subseteq R^n$:输入空间
  • $y \in \gamma \subseteq R^n$:输出空间
  • $w \in R^n, b \in R$:weight vectorbias
  • 也常有$\hat w = (w^T, b^T)^T, \hat x = (x^T + 1)^T$, 则有$\hat w \hat x = wx + b$
  • 感知机模型的假设空间是定义在特征空间的所有 linear classification model/linear classifier,即函数 集合${f|f(x)=wx+b}$

  • 线性方程$wx+b=0$:对应特征空间$R^n$中一个hyperplane

    • $w$:超平面法向量
    • $b$:超平面截距
    • 超平面将特征空间划分为两个部分,其中分别被分为正、负 两类

    • 也被称为separating hyperplane

Linearly Separable Data Set

  • 对数据集$T={(x_1,y_1),\cdots,(x_N,y_N)}$,若存在超平面 $S: wx + b=0$能够将正、负实例点,完全正确划分到超平面 两侧,即 则称数据集T为线性可分数据集

感知机学习策略

感知机学习策略:定义适当损失函数,并将经验风险极小化,确定 参数$w, b$

0-1损失

经验风险:误分率(误分点总数)

  • 不是参数$w, b$的连续可导函数,不易优化

绝对值损失

经验风险:误分类点到超平面距离

  • 对误分类数据$(x_i, y_i)$,有$-y_i(wx_i + b) > 0$

  • 则误分类点$(x_i, y_i)$到超平面S距离

  • 则感知机损失函数可定义为 $L(w,b) = -\sum_{x_i \in M} y_i(wx_i + b)$

    • $M$:误分类点集合
    • 损失函数是$w, b$的连续可导函数:使用$y_i$替代绝对值
  • 损失函数$L(w,b)$梯度有

学习算法

Stochastic Gradient Descent

随机梯度下降法

  • 输入:数据集$T$、学习率$\eta, 0 \leq \eta \leq 1$
  • 输出:$w,b$、感知模型$f(x)=sgn(wx+b)$
  1. 选取初值$w_0, b_0$

  2. 随机选取一个误分类点$(x_i, y_i)$,即$y_i(wx_i+b) \leq 0$ ,对$w, b$进行更新

    • $0 < \eta \leq 1$:learning rate,学习率,步长
  3. 转2,直至训练集中无误分类点

  • 不同初值、随机取点顺序可能得到不同的解
  • 训练数据线性可分时,算法迭代是收敛的
  • 训练数据不线性可分时,学习算法不收敛,迭代结果发生震荡
  • 直观解释:当实例点被误分类,应该调整$w, b$值,使得分离 超平面向误分类点方向移动,减少误分类点与超平面距离, 直至被正确分类

学习算法对偶形式

todo

算法收敛性

为方便做如下记号

  • $\hat w = (w^T, b^T)^T, \hat w \in R^{n+1}$
  • $\hat x = (x^T, 1)^T, \hat x \in R^{n+1}$

此时,感知模型可以表示为

  • 数据集$T={(x_1, y_1), (x_2, y_2),…}$线性可分,其中: $x_i \in \mathcal{X = R^n}$, $y_i \in \mathcal{Y = {-1, +1}}$,则
  • 存在满足条件$|\hat w{opt}|=1$超平面 $\hat w{opt} \hat x = 0$将训练数据完全正确分开,且 $\exists \gamma > 0, yi(\hat w{opt} x_i) \geq \gamma$

  • 令$R = \arg\max_{1\leq i \leq N} |\hat x_i|$,则 随机梯度感知机误分类次数$k \leq (\frac R \gamma)^2$

超平面存在性

  • 训练集线性可分,存在超平面将训练数据集完全正确分开,可以 取超平面为$\hat w_{opt} \hat x = 0$

  • 令$|\hat w_{opt}| = 1$,有

    可取

    满足条件

感知机算法收敛性

  • 给定学习率$\eta$,随机梯度下降法第k步更新为 $\hat wk = \hat w{k-1} + \eta y_i \hat x_i$

  • 可以证明

    • $\hat wk \hat w{opt} \geq k\eta\gamma$

    • $|\hat w_k|^2 \leq k \eta^2 R^2$

  • 则有

  • 直观理解就是超平面最大移动次数不大于最大移动距离 除以最小移动步长

    • $\eta \gamma^2$:超平面法向量最小增加量(移动步长)
    • $\eta R^2$:超平面法向最大增加量(移动距离)
    • 但是超平面不可能将所有点都归为同一侧
  • 误分类次数有上界,经过有限次搜索可以找到将训练数据完全 正确分开的分离超平面,即训练数据集线性可分时,算法的迭代 形式是收敛的