背景

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

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

  • Connecting Consistency
  • Generalization Ability
  • Sparsity
  • Stability

• 不确定性来源

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

• 过拟合判断依据

  • metric entropy
  • VC-dimension

对比

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

• Stochastic Programming：使用概率描述参数不确定性，

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

  • 不考虑参数的分布

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

策略（最优化问题）

$$\begin{align*} \min_x & : f_0(x) \\ s.t. & : f_i(x) \leq 0, i=1,2,\cdots,m \end{align*}$$ $$\begin{align*} \min_x & : f_0(x) \\ s.t. & : f_i(x, u_i) \leq 0, \forall u_i \in \mathcal{U}_i, i=1,2,\cdots,m \end{align*}$$

• $\mathcal{U}_i $：uncertainty set，不确定集

Computational Tractablity

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

$$\mathcal{X(U)} \overset {\triangle} {=} \{ x: f_i(x, u_i) \leq 0, \forall u_i \in \mathcal{U}_i, i=1,2,\cdots,m \}$$

• 若存在高效算法能确定$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

原子不确定集

$$\begin{align*} (I) & 0 \in \mathcal{U}_0 \\ (II) & \forall w_0 \in R^n: \sup_{u \in \mathcal{U}_0 [-w_0^T u^{'} < +\infty \end{align}$$

Robust Optimization and Adversary Resistant Learning

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

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

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

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

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

$$\begin{align*} \min_{w,b,\xi}: \quad & \mathcal{ r(w,b) + C\sum_{i=1}^m \xi_i} \\ s.t.: & \xi_i \geq [1-y_i(<w,x_i> + b)], i=1,\cdots,m; \\ & \xi_i \geq 0, i=1,\cdots,m; \end{align*}$$

Corrupted Location

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

• 正则化项使用

  • 传统的二范数，一范数同样使用的稀疏的解

• 概率解释：风险控制

Missing Data

• 多项式不确定：对抗删除数据（alpha go）

• 使用无效特征消去偏置

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

Robust Optimization and Regularization

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

  • 正则化
  • 稀疏
  • 一致性

• 指导寻找新的算法

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

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

SVM

Kernel Function

• 对输入空间 $X$ （欧式空间 $R^n$ 的子集或离散集合）、特征空间 $H$ ，若存在从映射 $$

    \phi(x): X \rightarrow H
  

  $$使得对所有 $x, z \in X$ ，函数 $K(x,z)$ 满足$$

    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$ ，有

    $$\begin{align*} (xy)^2 & = (x_1y_1 + x_2y_2)^2 \\ & = (x_1y_1)^2 + 2x_1y_1x_2y_2 + (x_2y_2)^2 \end{align*}$$

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

    $$\phi(x) = (x_1^2, \sqrt 2 x_1x_2, x_2^2)^T$$

    或取映射

    $$\phi(x) = \frac 1 {\sqrt 2} (x_1^2 - x_2^2, 2x_1x_2, x_1^2 + x_2^2)^T$$

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

    $$\phi(x) = (x_1^2, x_1x_2, x_1x_2, x_2^2)^T$$

核函数 $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

线性核：最简单的核函数

$$k(x, y) = x^T y$$

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

Polynomial Kernel

多项式核：non-stational kernel

$$K(x, y) = (\alpha x^T y + c)^p$$

• 特点

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

    todo

• 应用场合

  • SVM：p 次多项式分类器

    $$f(x) = sgn(\sum_{i=1}^{N_s} \alpha_i^{*} y_i (x_i x + 1)^p + b^{*})$$

Gaussian Kernel

高斯核：radial basis kernel，经典的稳健径向基核

$$K(x, y) = exp(-\frac {\|x - y\|^2} {2\sigma^2})$$

• $\sigma$：带通，取值关于核函数效果，影响高斯分布形状

  • 高估：分布过于集中，靠近边缘非常平缓，表现类似像线性一样，非线性能力失效
  • 低估：分布过于平缓，失去正则化能力，决策边界对噪声高度敏感

• 特点

  • 对数据中噪声有较好的抗干扰能力

• 对应映射：省略分母

  $$\begin{align*} K(x, y) & = exp(-(x - y)^2) \\ & = exp(-(x^2 - 2 x y - y^2)) \\ & = exp(-x^2) exp(-y^2) exp(2xy) \\ & = exp(-x^2) exp(-y^2) \sum_{i=0}^\infty \frac {(2xy)^i} {i!} \\ & = \phi(x) \phi(y) \\ \phi(x) & = exp(-x^2)\sum_{i=0}^\infty \sqrt {\frac {2^i} {i!}} x^i \end{align*}$$

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

• 应用场合

  • SVM：高斯radial basis function分类器

    $$f(x) = sgn(\sum_{i=1}^{N_s} \alpha_i^{*} y_i exp(-\frac {\|x - y\|^2} {2\sigma^2}) + b^{*})$$

Exponential Kernel

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

$$K(x, y) = exp(-\frac {\|x - y\|} {2\sigma^2})$$

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

Laplacian Kernel

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

$$K(x, y) = exp(-\frac {\|x - y\|} {\sigma^2})$$

ANOVA Kernel

方差核：径向基核

$$k(x,y) = \sum_{k=1}^n exp(-\sigma(x^k - y^k)^2)^d$$

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

Hyperbolic Tangent/Sigmoid/Multilayer Perceptron Kernel

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

$$k(x, y) = tanh(\alpha x^T y + c)$$

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

• 参数

  • $\alpha$：通常设置为$1/N$，N是数据维度

• 使用Sigmoid核的SVM等同于两层感知机神经网络

Ration Quadratic Kernel

二次有理核：替代高斯核，计算耗时较小

$$k(x, y) = 1 - \frac {\|x - y\|^2} {\|x - y\|^2 + c}$$

Multiquadric Kernel

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

$$k(x, y) = \sqrt {\|x - y\|^2 + c^2}$$

Inverse Multiquadric Kernel

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

$$k(x, y) = \frac 1 {\sqrt {\|x - y\|^2 + c^2}}$$

Circular Kernel

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

$$k(x, y) = \frac 2 \pi arccos(-\frac {\|x - y\|} \sigma) - \frac 2 \pi \frac {\|x - y\|} \sigma \sqrt{1- \frac {\|x - y\|^2} \sigma}$$

Spherical Kernel

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

$$k(x, y) = 1 - \frac 3 2 \frac {\|x - y\|} \sigma + \frac 1 2 (\frac {\|x - y\|} \sigma)^3$$

Wave Kernel

波动核

$$k(x, y) = \frac \theta {\|x - y\|} sin(\frac {\|x - y\|} \theta)$$

• 适用于语音处理场景

Triangular/Power Kernel

三角核/幂核：量纲不变核，条件正定

$$k(x, y) = - \|x - y\|^d$$

Log Kernel

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

$$k(x, y) = -log(1 + \|x - y\|^d)$$

Spline Kernel

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

$$k(x, y) = 1 + x^t y + x^t y min(x, y) - \frac {x + y} 2 min(x, y)^2 + \frac 1 3 min(x, y)^2$$

B-Spline Kernel

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

$$\begin{align*} k(x, y) & = \prod_{p=1}^d B_{2n+1}(x_p - y_p) \\ B_n(x) & = B_{n-1} \otimes B_0 \\ & = \frac 1 {n!} \sum_{k=0}^{n+1} \binom {n+1} {r} (-1)^k (x + \frac {n+1} 2 - k)_{+}^n \end{align*}$$

• $x_{+}^d$：截断幂函数 $$x_{+}^d = \left \{ \begin{array}{l} x^d, & if x > 0 \\ 0, & otherwise \\ \end{array} \right.$$

Bessel Kernel

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

$$k(x, y) = \frac {J_{v+1}(\sigma\|x - y\|)} {\|x - y\|^{-n(v + 1)}}$$

• $J$：第一类Bessel函数

Cauchy Kernel

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

$$k(x, y) = \frac 1 {1 + \frac {\|x - y\|^2} {\sigma}}$$

Chi-Square Kernel

卡方核：源自卡方分布

$$\begin{align*} k(x, y) & = 1 - \sum_{i=1}^d \frac {(x_i - y_i)^2} {\frac 1 2 (x_i + y_i)} \\ & \frac {x^t y} {\|x + y\|} \end{align*}$$

Histogram Intersection/Min Kernel

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

$$k(x, y) = \sum_{i=1}^d min(x_i, y_i)$$

Generalized Histogram Intersection

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

$$k(x, y) = \sum_{i=1}^m min(|x_i|^\alpha, |y_i|^\beta)$$

Bayesian Kernel

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

$$\begin{align*} k(x, y) & = \prod_{i=1}^d k_i (x_i, y_i) \\ k_i(a, b) & = \sum_{c \in \{0, 1\}} P(Y=c | X_i = a) P(Y=c | x_k = b) \end{align*}$$

Wavelet Kernel

波核：源自波理论

$$k(x, y) = \prod_{i=1}^d h(\frac {x_i - c} a) h(\frac {y_i - c} a)$$

• 参数

  • $c$：波的膨胀速率
  • $a$：波的转化速率
  • $h$：母波函数，可能的一个函数为 $$h(x) = cos(1.75 x) exp(-\frac {x^2} 2)$$

• 转化不变版本如下

  $$k(x, y) = \prod_{i=1}^d h(\frac {x_i - y_i} a)$$

离散数据核函数

String Kernel

字符串核函数：定义在字符串集合（离散数据集合）上的核函数

$$\begin{align*} k_n(s, t) & = \sum_{u \in \sum^n} [\phi_n(s)]_u [\phi_n(t)]_u \\ & = \sum_{u \in \sum^n} \sum_{(i,j): s(i) = t(j) = u} \lambda^{l(i)} \lambda^{l(j)} \end{align*}$$

• $[\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

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

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

• 优点

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

• 缺点

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

总述

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

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

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

  • E步：求期望expectation
  • M步：求极大maximization

• 模型变量都是observable variable、给定数据情况下，可以 直接使用极大似然估计、贝叶斯估计

EM算法

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

$$\begin{align*} L(\theta) & = log P(Y|\theta) \\ & = log \sum_Z P(Y, Z|\theta) \\ & = log \left(\sum_Z P(Y|Z,\theta) P(Z|\theta) \right) \end{align*}$$

• $Y$：观测变量数据
• $Z$：隐随机变量数据（未知）
• $Y,Z$合在一起称为完全数据
• $P(Y,Z|\theta)$：联合分布
• $P(Z|Y,\theta)$：条件分布

• 但是极大化目标函数中包括未观测数据$Z$、求和（积分）的 对数，直接求极大化非常困难
• EM算法通过迭代逐步近似极大化$L(\theta)$

推导

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

  $$L(\theta) - L(\theta^{(i)}) = log (\sum_Z P(Y|Z,\theta) P(Z|\theta)) - log P(Y|\theta^{(i)})$$

• 利用Jensen不等式有

  $$\begin{align*} L(\theta) - L(|\theta^{(i)}) & = log(\sum_Z P(Y|Z, \theta^{(i)}) \frac {P(Y|Z,\theta) P(Z|\theta)} {P(Y|Z,\theta^{(i)})}) - log P(Y|\theta^{(i)}) \\ & \geq \sum_Z P(Z|Y,\theta^{(i)}) log \frac {P(Y|Z,\theta) P(Z|\theta)} {P(Z|Y,\theta^{(i)})} - log P(Y|\theta^{(i)}) \\ & = \sum_z P(Z|Y,\theta^{(i)}) log \frac {P(Y|Z,\theta) P(Z|\theta)} {P(Z|Y,\theta^{(i)}) P(Y|\theta^{(i)})} \end{align*}$$

• 令

  $$B(\theta, \theta^{(i)}) = L(\theta^{(i)}) + \sum_Z P(Z|Y,\theta^{(i)}) log \frac {P(Y|Z,\theta) P(Z|\theta)} {P(Z|Y,\theta^{(i)}) P(Y|\theta^{(i)})}$$

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

  $$\begin{align*} L(\theta) & \geq B(\theta, \theta^{(i)}) \\ \end{align*}$$

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

  $$\begin{align*} L(\theta^{(i)}) = B(\theta^{(i)}, \theta^{(i)}) \end{align*}$$

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

  $$\begin{align*} \theta^{(i+1)} & = \arg\max_{\theta} B(\theta,\theta^{(i)}) \\ & = \arg\max_{\theta} L(\theta^{(i)}) + \sum_Z P(Z|Y,\theta^{(i)}) log \frac {P(Y|Z,\theta) P(Z|\theta)} {P(Z|Y,\theta^{(i)}) P(Y|\theta^{(i)})} \\ & = \arg\max_{\theta} (\sum_Z P(Z|Y,\theta^{(i)}) log(P(Y|Z,\theta)P(Z|\theta))) \\ & = \arg\max_{\theta} (\sum_Z P(Z|Y,\theta^{(i)}) log P(Y,Z|\theta)) \\ & = \arg\max_{\theta} Q(\theta, \theta^{(i)}) \end{align*}$$

  • 和$\theta$无关的常数项全部舍去

• $Q(\theta, \theta^{(i)})$：Q函数，完全数据的对数似然函数 $logP(Y,Z|\theta)$，关于在给定观测$Y$和当前参数 $\theta^{(i)}$下，对未观测数据Z的条件概率分布 $P(Z|Y,\theta^{(i)})$ $$Q(\theta, \theta^{(i)}) = E_z [logP(Y,Z|\theta)|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)}$

   $$\theta^{(i+1)} = \arg\max_{\theta} Q(\theta, \theta^{(i)})$$

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)})$是单调递增的 $$P(Y|\theta^{(i+1)}) \geq P(Y|\theta^{(i)})$$

• 由条件概率

  $$\begin{align*} P(Y|\theta) & = \frac {P(Y,Z|\theta)} {P(Z|Y,\theta)} \\ logP(Y|\theta) & = logP(Y,Z|\theta) - logP(Z|Y,\theta) \end{align*}$$

• 则对数似然函数有

  $$logP(Y|\theta) = Q(\theta, \theta^{(i)}) - H(\theta, \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)}$带入，做差

  $$logP(Y|\theta^{(i+1)}) - logP(Y|\theta^{(i)}) = [Q(\theta^{(i+1)}, \theta^{(i)}) - Q(\theta^{(i)}, \theta^{(i)}] - [H(\theta^{(i+1)}, \theta^{(i)}) - H(\theta^{(i)}, \theta^{(i)})]$$

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

  • 又有

    $$\begin{align*} & H(\theta^{(i+1)}, \theta^{(i)}) - H(\theta^{(i)}, \theta^{(i)}) \\ = & \sum_Z (log \frac {P(Z|Y,\theta^{(i+1)})} {P(Z|Y,\theta^{(I)})}) P(Z|Y,\theta^{(i)}) \\ \leq & log (\sum_Z \frac {P(Z|Y,\theta^{(i+1)})} {P(Z|Y,\theta^{(I)})} P(Z|Y,\theta^{(i)})) \\ = & log \sum_Z P(Z|Y,\theta^{(i+1)}) = 0 \end{align*}$$

定理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

• 高斯混合模型是指具有如下概率分布模型 $$P(y|\theta) = \sum_{k=1}^K \alpha_k \phi(y|\theta_k)$$

  • $\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个分模型的数据是未知的

  $$\gamma_{j,k} = \left \{ \begin{array}{l} 1, & 第j个观测来自第k个分模型 \\ 0, & 否则 \end{array} \right.$$

  • $j=1,2,\cdots,N$：观测编号
  • $k=1,2,\cdots,K$：模型编号

• 则完全数据为

  $$(y_j,\gamma_{j,1},\cdots,\gamma_{j,K}), j=1,2,...,N$$

• 完全数据似然函数为

  $$\begin{align*} P(y,\gamma|\theta) & = \prod_{j=1}^N P(y_j,\gamma_{j,1},\cdots,\gamma_{j,N}|\theta) \\ & = \prod_{k=1}^{K} \prod_{j=1}^N [\alpha_k \phi(y_j|\theta_k)]^{\gamma _{j,k}} \\ & = \prod_{k=1}^{K} \alpha_k^{n_k} \prod_{j=1}^N [\phi(y_j|\theta_k)]^{\gamma _{j,k}} \\ \end{align*}$$

  • $nk = \sum{j=1}^{N} \gamma_{j,k}$
  • $\sum_{k=1}^K n_k = N$

• 完全数据的对数似然函数为

  $$logP(y, \gamma|\theta) = \sum_{k=1}^K \left \{ n_k log \alpha_k + \sum_{j=1}^N \gamma_{j,k} [log \frac 1 {\sqrt {2\pi}} - log \sigma_k - \frac 1 {2\sigma_k}(y_j - \mu_k)^2] \right \}$$

E步：确定Q函数

$$\begin{align*} Q(\theta, \theta^{(i)}) & = E_z[logP(y,\gamma|\theta)|Y,\theta^{(i)}] \\ & = E \sum_{k=1}^K \left \{ n_k log\alpha_k + \sum_{j=1}^N \gamma_{j,k} [log \frac 1 {\sqrt {2\pi}} - log \sigma_k - \frac 1 {2\sigma_k}(y_j - \mu_k)^2] \right \} \\ & = \sum_{k=1}^K \left \{ \sum_{k=1}^K (E\gamma_{j,k}) log\alpha_k + \sum_{j=1}^N (E\gamma_{j,k}) [log \frac 1 {\sqrt {2\pi}} - log \sigma_k - \frac 1 {2\sigma_k}(y_j - \mu_k)^2] \right \} \end{align*}$$

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

$$\begin{align*} \hat \gamma_{j,k} & = E(\gamma_{j,k}|y,\theta) = P(\gamma_{j,k}|y,\theta) \\ & = \frac {P(\gamma_{j,k}=1, y_j|\theta)} {\sum_{k=1}^K P(\gamma_{j,k}=1,y_j|\theta)} \\ & = \frac {P(y_j|\gamma_{j,k}=1,\theta) P(\gamma_{j,k}=1|\theta)} {\sum_{k=1}^K P(y_j|\gamma_{j,k}=1,\theta) P(\gamma_{j,k}|\theta)} \\ & = \frac {\alpha_k \phi(y_j|\theta _k)} {\sum_{k=1}^K \alpha_k \phi(y_j|\theta_k)} \end{align*}$$

带入可得

$$Q(\theta, \theta^{(i)}) = \sum_{k=1}^K \left\{ n_k log\alpha_k + \sum_{k=1}^N \hat \gamma_{j,k} [log \frac 1 {\sqrt{2\pi}} - log \sigma_k - \frac 1 {2\sigma^2}(y_j - \mu_k)^2] \right \}$$

M步

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

$$\begin{align*} \theta^{(i+1)} & = \arg\max_{\theta} Q(\theta,\theta^{(i)}) \\ \hat \mu_k & = \frac {\sum_{j=1}^N \hat \gamma_{j,k} y_j} {\sum_{j=1}^N \hat \gamma_{j,k}} \\ \hat \sigma_k^2 & = \frac {\sum_{j=1}^N \hat \gamma_{j,k} (y_j - \mu_p)^2} {\sum_{j=1}^N \hat \gamma_{j,k}} \\ \hat \alpha_k & = \frac {n_k} N = \frac {\sum_{j=1}^N \hat \gamma_{j,k}} N \end{align*}$$

• $\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$响应度

   $$\hat \gamma_{j,k} = \frac {\alpha \phi(y_k|\theta_k)} {\sum_{k=1}^N \alpha_k \phi(y_j|\theta)}$$

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)$如下 $$F(\tilde P, \theta) = E_{\tilde P} [log P(Y,Z|\theta)] + H(\tilde P)$$

• $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(Z) = P(Z|Y,\theta)$$ 并且$\tilde P_{\theta}$随$\theta$连续变化

• 对于固定的$\theta$，求使得$F(\tilde P, \theta)$的极大， 构造Lagrange函数

  $$L(\tilde P, \lambda, \mu) = F(\tilde P, \theta) + \lambda(1 - \sum_Z \tilde P(Z)) - \mu \tilde P(Z)$$

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

  $$\left \{ \begin{array}{l} \sum_Z \tilde P(Z) = 1 \\ \tilde P(Z) \geq 0 \end{array} \right.$$

  即Lagrange方程中后两项

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

  $$\frac {\partial L} {\partial \tilde P(Z)} = log P(Y,Z|\theta) - log \tilde P(Z) - \lambda - \mu$$

  令偏导为0，有

  $$\begin{align*} log P(Y,Z|\theta) - log \tilde P(Z) & = \lambda + \mu \\ \frac {P(Y,Z|\theta)} {\tilde P(Z)} & = e^{\lambda + \mu} \end{align*}$$

• 则使得$F(\tilde P, \theta)$极大的$\tilde P_\theta(Z)$ 应该和$P(Y,Z|\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$使得整体看起来非常不和谐

  $$\begin{align*} E_{\tilde P} f(Z) & = \sum_Z f(Z) \tilde P(Z) \\ & = \int f(Z) d(\tilde P(Z)) \end{align*}$$

定理2

• 若$\tilde P_\theta(Z) = P(Z|Y, \theta)$，则 $$F(\tilde P, \theta) = log P(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有

  $$L(\theta) = logP(Y|\theta) = F(\tilde P_\theta, \theta)$$

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

  $$L(\theta^{*}) = logP(Y|\theta^{*}) = F(\tilde P_\theta^{*}, \theta{*})$$

• 由$\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)}$

  $$\begin{align*} F(\tilde P^{(i+1)}, \theta^{(i)} & = E_{\tilde P^{(t+1)}} [log P(Y,Z|\theta)] + H(\tilde P^{(i+1)}) \\ & = \sum_Z log P(Y,Z|\theta) P(Z|Y,\theta^{(i)}) + H(\tilde P^{(i+1)}) \\ & = Q(\theta, \theta^{(i)}) + H(\tilde P^{(i+1)}) \end{align*}$$

• 则固定$\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$的估计值， 计算

   $$\begin{align*} Q(\theta, \theta^{(i)}) & = E_Z [ log P(Y,Z|\theta)|Y,\theta^{(i)}] \\ & = \sum_Z P(Z|Y, \theta^{(i)}) log P(Y,Z|\theta) \end{align*}$$

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

   $$Q(\theta^{(i+1)}, \theta^{(i)}) > Q(\theta^{(i)}, \theta^{(i)})$$

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)$的估计值，计算

   $$\begin{align*} Q(\theta, \theta^{(i)}) & = E_Z [ log P(Y,Z|\theta)|Y,\theta^{(i)}] \\ & = \sum_Z P(Z|Y, \theta^{(i)}) log P(Y,Z|\theta) \end{align*}$$

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)})$ 使得

      $$Q(\theta^{(i+1)}, \theta^{(i)}) > Q(\theta^{(i)}, \theta^{(i)})$$

4. 重复2、3直到收敛

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$在原点，则近邻分布的小立方体边期望长度为

    $$Ed_p(r) = r^{1/p} \\ Ed_3(0.1) = 0.1^{1/3} = 0.46 \\ Ed_10(0.1)d = 0.1^{1/10} = 0.79 \\ Ed_10(0.01) = 0.1^{1/10} = 0.63 \\$$

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

• 特征选择有必要

特征选择

• 变量本身考察

  • 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$，用其取值作为预测值

• 模型简单、效果较理想

  • 尤其适合特征空间维度较低、类别边界不规则情况
  • 只根据单个近邻预测，预测结果受近邻差异影响极大，预测 波动（方差）大，稳健性低

• 预测错误的概率不高于普通贝叶斯方法的两倍

  $$\begin{align*} P_e & = (1-p(y=1|X=X_0))P(y=1|X=X_0) + (1-p(y=0|X=X_0))P(y=0|X=X_0) \\ & = 2P(y=1|X=X_0)(1-P(y=1|X=X_0)) \\ & \leq 2(1-P(y=1|X=X_0)) \\ \end{align*}$$

  • $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}$的误分率为

  $$\frac 1 k \sum_{x \in N_k(x)} I(y_i \neq c_j) = 1 - \frac 1 k \sum_{x \in N_k(x)} I(y_i = c_j)$$

  • $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得到各变量 重要性排序

  $$FI_{(i)} = e_i + \frac {1} {p} \quad \\ w_{(i)} = \frac {FI_{(i)}} {\sum_{j=1}^p FI_{(j)}}$$

  • $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之间 $$D(Z_{(i)}, Z_0) = \frac {d(Z_{(i)}, Z_0)} {d(Z_{(k+1)}, Z_0)}, \quad i=1,2,...,k$$

• 依据函数$w_i=K(d)$确定k各近邻的权重

• 预测

  • 回归预测 $$\hat{y}_0 = \frac 1 k (\sum_{i=1}^k w_iy_i)$$
  • 分类预测：多数表决原则 $$\hat{y}_0 = max_r (\sum_{i=1}^k w_iI(y_i=r)) \\ P(\hat{y}_0=r|X_0)= \frac {\sum_{i=1}^k w_iI(y_i=r)} {\sum_{i=1}^k w_i}$$

Approximate Nearest Neighbor

相似最近邻

决策树概述

结构

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

• 决策树由 node、directed edge 组成

  • internal node：内部节点，表示特征、属性
  • leaf node：叶子节点，表示一个类

• 对训练数据进行分类

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

• 对新数据的预测

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

本质

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

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

分类规则集合

• 决策树可以看作是 if-then 规则的集合：体现输入、输出变量逻辑关系

• 决策树根节点到叶节点每条路径构成一条规则
• 路径上内部节点的特征对应规则的条件，叶节点对应规则结论
• 决策树的路径或其对应的 if-then 规则集合 互斥且完备，即每个实例有且仅有一条路径覆盖

条件概率分布

• 决策树可以表示定义在特征空间、类空间上的条件概率分布

• 此条件概率分布定义在特征空间的一个划分（有限）上

  • 决策树中一条路径（叶节点）对应划分中一个单元
  • 每个单元定义的概率分布就构成一个条件概率分布

• 条件概率分布由 各单元的给定条件下，各类的条件概率分布组成

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

特点

• 优势

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

• 问题

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

决策树构建

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

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

• 原则：使节点/组内观测取值异质性下降最大，从而确定

  • 最佳划分特征
  • 特征的最佳分割点

异质性衡量：划分准则

• 信息增益
• 信息增益比：避免信息增益倾向于取值较多特征
  • 若样本类别严格服从分布，则信息增益和信息增益比选择应完全相同
  • 但由于偶然性、样本数量等原因，各特征取值的样本数量往往不完全符合分布
  • 由信息增益定义可看出，各特征取值样本数量较小时，数量变动影响更大，而特征取值较多更可能出现各取值对应样本数量较小
• GINI 指数

• 研究表明，不同决策树的划分准则对泛化性能影响有限，信息增益和 GINI 指数理念分析表明，其仅在 2% 情况下有所不同

特征变量处理

• 离散值处理

  • 全分类：各类别分别独立作为分支，构建节点
  • 切分二分：将类别分为的两组
  • 是否二分：某取值作为一个分支，其余作为另一分支

• 连续值处理

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

缺失值处理

• 缺失值处理需要解决：异质性衡量指标计算、特征缺失样本划分问题

• 异质性衡量指标计算：使用特征未缺失样本权重对指标加权（以信息增益为例）

  $$\begin{align*} g(Y|X) &= \rho * g(\tilde Y | X) \\ & = \rho * (H(\tilde D) - \sum_v^V \tilde {r_v} H(\tilde {D^v})) \\ H(\tilde V) &= - \sum_k^K \tilde {p_k} log \tilde {p_k} \\ \rho &= \frac {\sum_{x \in \tilde D} w_x} {\sum_{x \in D} w_x}\\ \tilde {p_x} &= \frac {\sum_{x \in \tilde {D_k}} w_x} {\sum_{x \in \tilde D} w_x} \\ \tilde {r_v} &= \frac {\sum_{x \in \tilde {D^v}} w_x} {\sum_{x \in \tilde D} w_x} \end{align*}$$

  • $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

$$\begin{align*} C_\alpha(T) & = C(T) + \alpha |T| \\ & = \sum_{t=1}^{|T|} N_t H_t(T) + \alpha |T| \\ & = -\sum_{t=1}^{|T|} \sum_{k=1}^K \frac {N_{t,k}} {N_t} log \frac {N_{t,k}} {N_t} + \alpha|T| \\ H_t(T) & = -\sum_k (\frac {N_{t,k}} {N_t} log \frac {N_{t,k}} {N_t}) \end{align*}$$

• $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.5Rules 将 C4.5 决策树转化为符号规则 - 各分支被重写为规则，并进行前件合并、删减

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

Classification and Regression Tree

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

• 特点

  • 二叉树
  • 可以用于分类、回归
    • 分类：众数代表节点，GINI 指数选择特征
    • 回归：均值代表节点，MSE 选择特征
  • 能较好的处理缺失值

• CART 回归：平方误差最小化准则

  $$f(x) = \sum_{m=1} \hat c_m I(x \in R_m)$$

  • $R_m$：空间划分出的第 $m$ 单元
  • $\hat c_m=avg(y_i|x_i \in R_m)$：第 $m$ 个单元上所有实例输出变量均值，此时平方误差最小

• CART 分类：最小化基尼指数准则

  $$Gini(D, X=a) = \frac {|D_1|} {|D|} Gini(D_1) + \frac {|D_2|} {|D|} Gini(D_2)$$

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

CART回归步骤

• 输入：训练数据集 $D$
• 输出：回归树 $f(x)$

• 选择最优切变量 $j$、切分点 $s$，即求解

  $$\arg\min_{j,s} [\min_{c_1} \sum_{x_i \in R_1(j,s)} (y_i - c_1)^2 + \min_{c_2} \sum_{x_i \in R_2(j,s)} (y_i - c_2)^2 ]$$

  • $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$，生成决策 树

  $$f(x) = \sum_{m=1} \hat c_m I(x \in R_m)$$

CART 分类步骤

• 输入：训练数据集 $D$，停止计算条件
• 输出：CART 决策树

• 选择最优切变量 $j$、切分点 $s$

  $$Gini(D, X=a) = \frac {|D_1|} {|D|} Gini(D_1) + \frac {|D_2|} {|D|} Gini(D_2)$$
  • 对每个特征 $X$，对其所有取值 $a$ 计算条件基尼指数
  • 选择条件基尼指数最小的特征、对应的切分点，将训练数据依特征分配到两个子结点中

• 对生成两个子节点递归分裂，直至满足停止条件

• 生成 CART 决策树

Chi-squared Automatic Interaction Detector

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

• https://wenku.baidu.com/view/bdd3e60abed5b9f3f90f1cd6.html
• https://sefiks.com/2020/03/18/a-step-by-step-chaid-decision-tree-example/

特点

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

  • 分类目标变量：列联分析，卡方检验
  • 数值目标变量：回归分析，F检验

• 特征预处理

  • 分类型特征变量：根据卡方统计量显著性、组数量等考虑拆分、合并分组
  • 数值型特征变量：均分分组

• 是从相关性显著角度确定特征变量

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

QUEST

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

特点

• 类似 CHAID，选择最显著（p 值）的特征变量作为划分特征

  • 分类特征变量：连列分析，卡方检验
  • 数值特征变量：方差分析，F检验

• 划分点选择

  • 分类特征变量：映射为 one-hot 向量后，用判别分析求解划分向量，再映射回划分取值

• 目标变量多分类

  • 为每个类别计算特征均值，使用均值聚类将其简化为二分类
  • 只需要为节点内样本的、用待划分特征计算均值

• 运行速度快于 CART 树

• http://www.mclover.cn/blog/index.php/archives/60.html
• http://www3.stat.sinica.edu.tw/statistica/oldpdf/A7n41.pdf

Naive Bayes Classifier

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

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

模型

• 输出Y的先验概率分布为

  $$P(Y = c_k), k = 1,2,\cdots,K$$

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

• 条件概率分布为

  $$P(X=x|Y=c_k) = P(X^{(1)}=x^{(1)},\cdots,X^{(D)}=x^{(D)}| Y=c_k)$$

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

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

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

  $$\begin{align*} P(X=x|Y=c_k) & = P(X^{(1)}=x^{(1)},\cdots,X^{(D)}=x^{(D)} |Y=c_k) \\ & = \prod_{j=1}^D P(X^{(j)}=x^{(j)}|Y=c_k) \end{align*}$$
  • 条件独立性假设是比较强的假设，也是朴素的由来

  • 其使得朴素贝叶斯方法变得简单，但有时也会牺牲准确率

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

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

策略

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

$$P(Y=c_k|X=x) = \frac {P(Y=c_k, X=x)} {\sum_{i=1}^K P(Y=c_k, X=x)}$$

• $K$：输出类别数量

• 后验概率根计算根据贝叶斯定理计算

  $$\begin{align*} P(Y=c_k|X=x) & = \frac {P(X=x|Y=c_k)P(Y=c_k)} {\sum_{k=1}^K P(X=x|Y=c_k) P(Y=c_k)} \\ & = \frac {P(Y=c_k) \prod_{j=1}^D P(X^{(j)}|Y=c_k)} {\sum_{k=1}^K P(Y=c_k) \prod_{j=1}^D P(X^{(j)}|Y=c_k)} \end{align*}$$

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

  $$y = \arg\max_{c_k} P(Y=c_k) \prod_{j=1}^D P(X^{(j)} = x^{(j)}|Y=c_k)$$
  • 即分类时，对给定输入$x$，将其归类为后验概率最大的类

策略性质

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

• 经验风险为

  $$\begin{align*} R_{emp}(f) & = E[L(Y, f(X))] \\ & = E_x \sum_{k=1}^K L(y, c_k) P(c_k | X) \end{align*}$$

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

  $$\begin{align*} f(x) & = \arg\min_{c_k} \sum_{k=1}^K L(y, c_k) P(c_k|X=x) \\ & = \arg\min_{c_k} \sum_{k=1}^K P(y \neq c_k|X=x) \\ & = \arg\min_{c_k} (1-P(y=c_k|X=x)) \\ & = \arg\max_{c_k} P(y=c_k|X=x) \end{align*}$$

  即后验概率最大化

算法

极大似然估计

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

  $$P(Y=c_k) = \frac {\sum_{i=1}^N I(y_i = c_k)} N, k=1,2,\cdots,K$$

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

  $$P(X^{(j)}=a_{j,l}|Y=c_k) = \frac {\sum_{i=1}^N I(x_i^{(j)}=a_{j,l}, y_i=c_k)} {\sum_{i=1}^N I(y_i=c_k)} \\ j=1,2,\cdots,N;l=1,2,\cdots,S_j;k=1,2,\cdots,K$$

  • $a_{j,l}$；第j个特征的第l个可能取值
  • $S_j$：第j个特征的可能取值数量
  • $I$：特征函数，满足条件取1、否则取0

算法

• 输入：训练数据T
• 输出：朴素贝叶斯分类器

1. 依据以上公式计算先验概率、条件概率

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

   $$y = \arg\max_{c_k} P(Y=c_k) \prod_{j=1}^D P(X^{(j)} = x^{(j)}|Y=c_k)$$

贝叶斯估计

• 条件概率贝叶斯估计

  $$P(X^{(j)}=a_{j,l}|Y=c_k) = \frac {\sum_{i=1}^N I(x_i^{(j)}=a_{j,l}, y_i=c_k) + \lambda} {\sum_{i=1}^N I(y_i=c_k) + S_j \lambda} \\ j=1,2,\cdots,N;l=1,2,\cdots,S_j;k=1,2,\cdots,K$$

  • $\lambda \geq 0$

  • $\lambda=0$时就是极大似然估计
  • 常取$\lambda=1$，此时称为Laplace Smoothing
  • 以上设计满足概率分布性质 $$\begin{align*} P_{\lambda}(X^{(j)}=a_{j,l}|Y=c_k) \geq 0 \\ \sum_{l=1}^{S_j} P_{\lambda}(X^{(j)}=a_{j,l}|Y=c_k) = 1 \end{align*}$$

• 先验概率贝叶斯估计

  $$P_{\lambda}(Y=c_k) = \frac {\sum_{i=1}^N I(y_i = c_i) + \lambda} {N + K\lambda}$$

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

Semi-Naive Bayes Classifier

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

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

  $$y = \arg\max_{c_k} P(Y=c_k) \prod_{j=1}^D \beta_j P(X^{(j)} = x^{(j)}|Y=c_k)$$
  • 特别的：权值为0/1即为变量筛选

One-Depentdent Estimator

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

$$P(X=x|Y=c_k) = \prod_{j=1}^D P(X^{(j)}=x^{(j)} | Y=c_k, pa_j)$$

• $pa_j$：特征$X^{(j)}$依赖的父特征

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

  $$P(X^{(j)}=x^{(j)} | Y=c_k, pa_j) = \frac {P(X^{(j)}=x^{(j)}, Y=c_k, pa_j)} {P(Y=c_k, pa_j)}$$

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

  $$y = \arg\max_{c_k} P(Y=c_k) \prod_{j=1}^D P(X^{(j)} = x^{(j)}|Y=c_k, pa_j)$$

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

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

SPODE

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

$$y = \arg\max_{c_k} P(Y=c_k, pa) \prod_{j=1}^D P(X^{(j)} = x^{(j)}|Y=c_k, pa)$$

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

AODE

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

$$y = \arg\max_{c_k} (\sum_{i=1}^D P(Y=c_k, X^{(i)}) \prod_{j=1}^D P(X^{(j)} = x^{(j)}|Y=c_k, X^{(i)}))$$

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

TAN

TAN步骤

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

  $$g(X^{(i)}, X^{(j)}| Y) = \sum P(X^{(i)}, X^{(j)} | Y=c_k) log \frac {P(X^{(i)}, X^{(j)} | Y=c_k)} {P(X^{(i)} | Y=c_k) P(X^{(j)} | Y=c_k)}$$

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

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

  • 挑选根变量
  • 将边设置为有向

• 加入预测节点$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

$$\min_{\beta \in R^n} \left\{ ||y - X\beta||_2^2 + \lambda ||\beta||_2^2 \right\}$$

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

LASSO

$$\min_{\beta \in R^n} \left\{ ||y - X\beta||_2^2 + \lambda||\beta||_1 \right\}$$

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

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

Elastic Net

Naive Elastic Net

$$\begin{align*} & \min_{\beta \in R^n} \left\{ ||y - X\beta||_2^2 + \lambda_1||\beta||_1 + \lambda_2||\beta||_2^2 \right\} \\ \Rightarrow & \min_{\beta^* \in R^p} \left\{ ||y - X^*\beta^*||_2^2 + \lambda^*||\beta^*||_1 \right\} \\ where: & y^* = \begin{pmatrix} y \\ \vec 0_p \end{pmatrix} \\ & X^* = \frac 1 {\sqrt {1+\lambda^2}} \begin{pmatrix} X \\ \sqrt {\lambda_2} I_p \end{pmatrix} \\ & \beta^* = \sqrt {1+\lambda_2} \beta \\ & \lambda^* = \frac {\lambda_1} {1+\lambda_2} \\ \end{align*}$$

• 弹性网在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夹角最小的变量，使用新变量进行 更新

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

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

感知机模型

感知机：线性二分类模型（判别模型）

$$f(x) = sign(wx + b)$$

• $x \in \chi \subseteq R^n$：输入空间
• $y \in \gamma \subseteq R^n$：输出空间
• $w \in R^n, b \in R$：weight vector、bias
• 也常有$\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$能够将正、负实例点，完全正确划分到超平面 两侧，即 $$\begin{align*} wx_i + b > 0, & \forall y_i > 0 \\ wx_i + b < 0, & \forall y_i < 0 \end{align*}$$ 则称数据集T为线性可分数据集

感知机学习策略

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

0-1损失

经验风险：误分率（误分点总数）

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

绝对值损失

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

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

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

  $$\begin{align*} d_i & = \frac 1 {\|w\|} |wx_i + b| \\ & =-\frac 1 {\|w\|} y_i(wx_i + b) \end{align*}$$

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

  • $M$：误分类点集合
  • 损失函数是$w, b$的连续可导函数：使用$y_i$替代绝对值

• 损失函数$L(w,b)$梯度有

  $$\begin{align*} \bigtriangledown_wL(w, b) & = -\sum_{x_i \in M} y_ix_i \\ \bigtriangledown_bL(w, b) & = -\sum_{x_i \in M} y_i \end{align*}$$

学习算法

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$进行更新

   $$\begin{align*} w^{(n+1)} & \leftarrow w^{(n)} + \eta y_ix_i \\ b^{(n+1)} & \leftarrow b^{(n)} + \eta y_i \end{align*}$$

   • $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}$

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

$$xw + b = \hat w \hat x = 0$$

• 数据集$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$，有

  $$\forall i, y_i(\hat w_{opt} \hat x_i) > 0$$

  可取

  $$\gamma = \min_i \{ y_i (\hat w_{opt} \hat x) \}$$

  满足条件

感知机算法收敛性

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

• 可以证明

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

    $$\begin{align*} \hat w_k \hat w_{opt} & = \hat w_{k-1} \hat w_{opt} + \eta y_i \hat w_{opt} \hat x_i \\ & \geq \hat w_{k-1} \hat w_{opt} + \eta\gamma \\ & \geq k\eta\gamma \end{align*}$$

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

    $$\begin{align*} \|\hat w_k\|^2 & = \|\hat w_{k-1} + \eta y_i x_i \|^2 \\ & = \|\hat w_{k-1}\|^2 + 2\eta y_i \hat w_{k-1} \hat x_i + \eta^2 \|\hat x_i\|^2 \\ & \leq \|w_{k-1}\|^2 + \eta^2 \|\hat x_i\|^2 \\ & \leq \|w_{k-1}\|^2 + \eta^2 R^2 \\ & \leq k\eta^2 R^2 \end{align*}$$

• 则有

  $$\begin{align*} k \eta \gamma & \leq \hat w_k \hat w_{opt} \leq \|\hat w\| \|\hat w_{opt}\| = \|\hat w\| \leq \sqrt k \eta R \\ k^2 \gamma^2 & \leq k R^2 \end{align*}$$

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

  • $\eta \gamma^2$：超平面法向量最小增加量（移动步长）
  • $\eta R^2$：超平面法向最大增加量（移动距离）
  • 但是超平面不可能将所有点都归为同一侧

• 误分类次数有上界，经过有限次搜索可以找到将训练数据完全 正确分开的分离超平面，即训练数据集线性可分时，算法的迭代 形式是收敛的