机器学习笔记

感谢毕秋宇同学!!

Chapter 2

空间

  • 假设空间

    • 假设满足XX条件的是好瓜
  • 版本空间

    • 有限训练集,已知XX是好瓜
  • 归纳偏好

    • 假设空间和训练集一致的假设
    • 学习过程中对某种类型假设的偏好称为归纳偏好
  • No Free Lunch
    • 奥卡姆剃刀:两个模型效果同样好,选择较为简单的

模型评估与选择

  • 经验误差与过拟合
    • 错误率率&误差
      • 错误率:错份样本的占$E=a/m$
      • 误差:样本真实输出与预测输出之间的差异
        • 训练(经验)误差:训练集上
        • 测试误差:测试集
        • 泛化误差:初训练集外所有样本
  • 过拟合
    • 学习器把训练样本学习的“太好”,将训练样本本身的特点当作所有样本的一般性质,导致泛化性能下降
    • 优化目标加正则项
    • Early stop
  • 欠拟合
    • 对训练样本的一般性质尚未学好
    • 决策树:扩展分支
    • 神经网络:增加训练层数
  • 评估方法
    • 留出法
      • 直接将数据集划分为两个互斥集合
      • 训练/测试集划分要尽可能保持数据分布的一致性
      • 一般若干次随机划分,重复实验取平均值
      • 训练/测试样本比例通常为2:1~4:1
    • 交叉验证法
      • 将数据集分层采样划分为$k$个大小相似的互斥子集
    • 自助法
      • 以自助采样法为基础,对数据集$D$有放回采样$m$次得到训练集$D^{\prime}$,$D\backslash D^{\prime}$用作测试集
  • 性能度量
    • 性能度量是衡量模型泛化能力的评价标准,反映任务的需求
      • 回归任务最常用的是“均方误差”:
        • $E(f:D)=\frac{1}{m}\sum_{i=1}^{m}(f(x_i)-y_i)^{2}$
    • 查准率 $P=\frac{TP}{TP+FP}$
    • 查全率 $R=\frac{TP}{TP+FN}$
    • $P-R$曲线
    • $F1$ measure:$\frac{2\times TP}{N+TP-TN}$
    • $AUC=\frac{1}{2}\sum_{i=1}^{m-1}(x_{i+1}-x_{i})\cdot(y_{i}+y_{i+1})$,预测了排序质量
    • 代价敏感错误率
  • 性能评估
    • 关于性能比较
      • 测试性能并不等于泛化性能
      • 测试性能随着测试集的变化而变化
      • 很多机器学习算法本身有一定的随机性
      • 直接选取相应评估方式在相应条件下评估并不可靠
    • 二项检验
      • 泛化错误率为$\epsilon$,测试错误率为$\hat{\epsilon}$,嘉定测试样本从样本总体分布中独立采样而来,我们可以使用“二项检验”,对于$\epsilon<epsilon_{0}$进行假设检验。
      • 假设$\epsilon\leq\epsilon_{0}$,若测试错误率小于
    • $t$检验
    • 交叉验证$t$检验
  • 偏差和方差
    • 对于测试样本$x$,令$y_{D}$为$x$在数据集中的标记,$y$为$x$的真实标记,$f(x;D)$为训练集$D$上学的模型$f$在$x$上的预测输出。
    • 以回归任务为例:
      • 期望预期为:$\bar{f}(x)=\mathbb{E}_{D}[f(x;D)]$;
      • 使用样本数目相同的不同训练集产生的方差为$var(x)=\mathbb{E}_{D}[(f(x:D)-\bar{f}(x))^{2}]$;
      • 噪声为$\varepsilon^{2}=\mathbb{E}_{D}[(y_{D}-y)^{2}]$
    • $E(f;D)=bias^{2}(x)+var(x)+\varepsilon^2$

Chapter 3

基本形式

  • 线性模型一般形式$f(x)=w_1x_1+w_2x_2+\cdots+w_dx_d+b$
  • 向量形式$f(x)=w^{T}x+b$

  • 区分猫狗的例子

    • 按照像素行堆叠或列堆叠,成为一个向量
    • 乘以单位,对于二分类问题,单位就是一个向量
  • Perceptron感知机
    • 对于线性分类器,误分类则$-y_{1}(w\cdot x_i)+b>0$
    • 定义损失函数$L(w,b)=-\sum_{x_{i}\in M}y_{i}(w\cdot x_{i}+b)$
    • 梯度$\bigtriangledown_{w}L(w,b)=-\sum_{x_{i}\in M}y_{i}x_{i}$
    • $\bigtriangledown_{b}L(w,b)=-\sum_{x_{i}\in M}y_{i}$
  • 梯度下降法
    • 一阶方法
    • 考虑无约束优化$min_{x}f(x)$,$f(x+\Delta x)\approx f(x)+\Delta x^{T}\bigtriangledown f(x)$
    • $\Delta x^{T}\bigtriangledown f(x)<0$
    • $\Delta x=-\gamma \bigtriangledown f(x)$
    • $\gamma$使用二分查找法进行查找
  • 优点
    • 形式简单,易于建模
    • 可解释性
    • 非线性模型的基础
      • 引入层级结构或高维映射
  • 缺陷
    • 解决不了$x^{2}$问题

线性回归

  • 目的:学得一个线性模型以尽可能准确地预测实值输出标记

  • 离散属性处理

    • 有“序”关系
      • 连续化为连续值
    • 无“序”关系
  • 单一属性的线性回归目标
    • $f(x)=wx_{i}+b$使得$f(x_{i})\simeq y_{i}$
  • 参数/模型估计:最小二乘法(Least square method)

    • $(w^{},b^{})=arg\ min_{(w,b)}\sum_{i=1}^{m}(f(x_{i})-y_i)^2$
    • 最小化均方误差$E_{(w,b)}$
  • 多元线性回归

    • $f(\hat{x_{i}})=\hat{x_{i}}^{T}(X^{T}X)^{-1}$
    • $X^{T}X$不满秩,进行正则化
  • 广义线性模型
    • 一般形式:$y=g^{-1}(w^{T}x+b)$
      • $g$为联系函数(link function)

二分类问题

  • 预测值与输出标记$z=w^{T}x+b$
  • 寻找函数将分类标记与线性回归模型输出联系起来
  • 最理想的模型——单位阶跃函数
  • 替代函数——对数几率函数(logistic function)

    • $y=\frac{1}{1+e^{-z}}$
    • 运行对数几率函数$y=\frac{1}{1+e^{-z}}=\frac{1}{1+e^{-(w^{T}x+b)}}$
    • 对数几率
  • 样本作为正例的相对可能性的对数$\ln\frac{y}{1-y}=\ln\frac{p(y=1|x)}{p(y=0|x)}=w^{T}x+b$

  • 极大似然法

  • 给定数据集$\{(x_{i}, y_{i})\}^{m}_{i=1}$

  • 最大化样本属于其真实标记的概率

  • 线性判别分析(Linear Discriminant Analysis)

    • 最大化目标$J=\frac{|w^{T}\mu_{0}-w^{T}\mu_{1}|^{2}_{2}}{w^{T}\sum_{0}w+w^{T}\sum_{1}w}=\frac{w^{T}(\mu_{0}-\mu_{1})(\mu_{0}-\mu_{1})^{T}w}{w^{T}(\sum_{0}+\sum_{1})w}$
    • 类间散度矩阵,类内散度矩阵
    • 广义瑞丽商$J=\frac{w^{T}S_{b}w}{w^{T}S_{w}w}$
    • 拉格朗日乘子法
      • $\bigtriangledown f(x^{})+\lambda \Delta g(x^{})=0$
      • $L(x,\lambda)=f(x)+\lambda g(x)$.

多分类问题

  • 多分类学习方法
    • 二分类学习方法推广到多类
    • 利用二分类学习器解决多分类问题
      • 对问题进行拆分,为拆出的每个二分类任务训练一个分类器
      • 对于每个分类器的预测结果进行集成以获得最终的多分类结果
    • 拆分策略
      • 一对一(OVO)
        • $N$个类别两两配对,$N(N-1)/2$个二类任务
        • 各个二类任务学习分类器,$N(N-1)/2$个二类分类器
      • 一对其余(OVR)
      • 多对多(MVM)
        • 若干类作为正类,若干类作为反类
        • 输出纠错码(Error Correcting Output Code, ECOC)
    • 类别不平衡问题$(class\ imbalance)$
      • 不同类别训练样例数相差很大情况(正类为小类)
      • 类别平衡正例预测$\frac{y}{1-y}>1\Rightarrow \frac{y}{1-y}>\frac{m^{+}}{m^{-}}$正负类比例
    • 再缩放
      • 欠采样$(undersampling)$
        • 去除一些反例使正反例数目接近
      • 过采样$(oversampling)$
        • 增加一些正例使正反例数目接近
      • 阈值移动$(threshold-moving)$

Chapter4 决策树

4.1 基本流程

决策树基于树结构来进行预测

  • 如果用决策树来进行分来,起码该模型一定意义上是可以理解的

    树结构的return

    (1)当前节点包含的样本全部属于同一类别(没必要分类)
    (2)当前的属性集为空,或所有样本所有属性上取值相同(没法分类)
    (3)当前节点包含的样本集合为空($ \emptyset $)

    4.2划分选择

  • 希望决策树的分支节点包含的样本尽可能属于同一类别,即节点的”纯度”(purity)越来越高

  • 经典的属性划分方法:
    1)信息增益,
    2)增益率,
    3)基尼指数

    划分选择-信息增益
  • “信息熵”是度量样本集合纯度最常用的一种指标

    信息熵
  • 推导:

    • (log2可以表示用二进制表示,$\frac{1}{p_k}$可以显示信息(概率越低越刺激))

    • 计算信息熵的约定:若p=0,则Ent=0

    • Ent(D)的值越小,纯度越大

      信息增益
  • 算出信息增益之后,可以确定树的每一层应该对应哪些划分属性

    存在的问题
  • 信息增益对可取值数目较多的属性有所偏好

    划分选择-增益率
  • 增益率:
    其中

    存在的问题
  • 增益率准则对可取值数目较少的属性有所偏好

    划分选择-基尼指数
  • Gini越小纯度越高

4.3剪枝处理

  • 为了对抗过拟合

  • 基本策略

    • 预剪枝
    • 后剪枝
  • 判断决策树泛化性能是否提升的办法

    • 留出法
      预剪枝
  • 优点

    • 降低过拟合风险
    • 显著减少训练时间和测试时间开销
  • 缺点

    • 欠拟合风险
      后剪枝
  • 优点

    • 比预剪枝保留了更多的分支,欠拟合风险小,泛化性能往往由于预剪枝决策树
  • 缺点

    • 时间开销

      4.4连续与缺失值

      连续与缺失值-连续值处理
  • 连续属性离散化(二分法)

  • 缺失值处理

    • 面临两个问题 如何划分,如何测试

4.5多变量决策树

Chapter 5

5.1 神经网络模型与发展史

  • 第一阶段
    • M-P模型
    • Hebb学习规则:类似于巴普洛夫,if input and output 同时激活或者失活, 那么这两个神经元的链接应该被加强,else 应该减弱
    • 感知机网络
    • 自适应神经元,最小均方学习算法
    • GG 1: 单层的神经网络不能解决非线性问题,多层神经网络算力不足的时候就输了
  • 第二阶段
    • Hopfield 网络
    • 反向传播算法
    • SVM与统计学习理论
  • 第三阶段
    • DBN深度信念网络
  • 神经元模型
    • M-P神经元模型
      • 输入:来自其他n个神经元传递过来的输入信号
      • 处理:输入信号通过带权重的连接进行传递,神经元接收到的总输入值将与神经元的阈值进行比较
      • 输出:通过激活函数的处理以得到输出:$y=f(\sum _{i=1}^{n}w_ix_i-
        \theta)$
      • 扯一点signmoid(x)=$\frac{1}{1+e^{-x}}$
        $y’=\frac{1}{1+e^{-x}}’=\frac{1}{1+e^{-x}}\times \frac{e^{-x}}{1+e^{-x}}=y(1-y)$

5.2 感知机与多层网络

  • 感知机
    • 由两层神经元组成,输入层接受外界输入信号传递个输出层,输出层是M-神经元
    • 与或非
    • 多层感知机
    • 多层前馈神经网络
      • 定义:每层神经元与下一层神经元全互联
      • 前馈:输入层接受外界输入,隐含层与输出层神经元对信号进行加工,最终结果由输出层神经元输出

5.3 误差逆传播算法

  • 误差逆传播算法(BP)
    • 前向计算:
      • $b_h=f(\beta _h -y_h ),\beta _h=\sum_{i=1}^{d}v_{ih}x_i$
      • $\hat{y}_i^{k}=f(a_j-\theta _j),\alpha_h=\sum_{i=1}^{d} w_{hj}b_{h}$
      • $E_k=\frac{1}{2}\sum_{j=1}^{l}(\hat{y}_{j}^{k}-\hat{y}_{j}^{k})^{2}$
    • 参数数目
      • 权重:$v_{ih},w_{hj}$, 阈值:$\theta _{j}$,$y_{h}$ (i=1,…,d,h=1,…,q,j=1,…,l)
        因此网络中需要(d+l+1)q+l个参数需要优化
    • 参数优化
      • BP是迭代学习算法,在迭代的每一轮中采用广义的感知机学习规则对参数进行更新估计,任意的参数v的更新估计式为
      • 梯度咋整? 梯度消失咋整?
      • 因为本质上还是函数的复合,因此不能用线性函数做传递函数
  • 一些BP算法
    • 标准BP算法:每来一个样本,就扔到bp网络中,然后前馈得到误差,得到误差之后就逆传递回来更新网络……
    • 累计BP算法:用平均误差更新权值,一定意义上可以减少震荡
    • 实际应用: Mini BP 一块一块更新
  • 多层前馈网络:
    • 局限:
      • 可能遭遇过拟合
      • 到底搞几层?
    • 解决过拟合策略:
      • 正则化
      • 早停

5.4 全局最小与局部极小

  • 策略
    • 使用”模拟退火”
    • 随机梯度下降
    • 遗传算法

5.5 其他常见神经网络

  • RBF网络:单隐层,激活函数与输入向量有关:$\rho(x,c_i)$是径向基函数:
  • ART网络:自适应谐振理论
    竞争性学习网络,输出神经元互相竞争,遵循胜者通吃原则
    比较层,识别层(???)
  • SOM网络:获取数据内在的结构
  • 级联相关,或则隐层节点的构造
  • Elman网络:递归神经网络

Chapter 6: 支持向量机

传奇——一刀999

神经网络(1989-1994)(BP算法)—————->支持向量机 (1995-2005)(核方法,统计学习)(Vapnik)————-> 神经网络(2006-今)(深度学习)

支持向量机 灵活(核方法) 能力很强 数学理论坚实 全局最优解 不需要人工调参
神经网络 更灵活 能力很强 理论不清,来自认知 局部最优解 非常依赖人工调参
支持向量机(SVM) 计算开销大 领域知识嵌入困难(对现象的认识) 服务于科学界
神经网络(NN) 可大可小 领域知识无处不在 服务于工业界

6.1 间隔与支持向量

  • 最大间隔: 寻找参数$w$,b,使得$\nu=\frac{2}{||w||}$ 最大

    • s.t. $y_i(w^{T}x_i+b)\geq 1,i=1,2,…,m$

    • s.t. $y_i(w^{T}x_i+b) \geq 1,i=1,2,…,m$

6.2 对偶问题

  • 拉格朗日乘子法

    • 三步
  • 解的稀疏性

    • 最终模型:$f(x)=w^Tx+b=\sum_{i=1}^{m}a_iy_ix_{i}^{T}x+b$

    • KKT条件:

  • SMO-求解方法,选两个固定搞,因为两个有闭式解;

6.3 核函数

  • 从低维映射到高维可以用线性的方式进行分类,只要维数足够高,高维的空间总可以线性的来分类;

  • 将x映射到$\phi(x)$转换前面的最终模型为:$f(x)=w^Tx+b=\sum_{i=1}^{m}a_iy_i\phi(x)_{i}^{T}\phi(x)+b$

    定义核函数:$k(x_i,x_j)=\phi(x_i)^{T}\phi(x_j)$

    定义核矩阵:

6.4 软间隔与正则化

  • 黑人问号,谜の调参(C)

6.5 支持向量回归

  • 因为听不懂所以自闭了 感觉大概推了一个神奇的二次回归吧

6.6 核方法

  • 表示定理:对于任意单调增函数$\Omega$和任意非负损失函数l,优化问题……

Chapter 7 :贝叶斯

7.1 贝叶斯决策论

概率框架下实施决策的基本理论:

  • 条件风险

    • $R(c_i|x)=\sum_{j=1}^{N}\lambda _{ij}P(c_j|x)$
  • 贝叶斯判定准则

    • $h^{*}(x)=argmin_{c\in \gamma} ~R(c|x)$
    • $h^*(x)$:贝叶斯最优分类器,
    • 反应了机器学习所能产生的模型精度的理论上限
  • P(c|x)在现实中通常难以直接获得

  • 两种基本策略:

    • 判别式模型:直接对P(c|x)建模
      • 决策树
      • BP神经网络
      • SVM
    • 生成式模型:先对联合概率分布P(x,c)建模,再由此获得P(c|x)
      • $P(c|x)=\frac{P(x.c)}{P(x)}$
  • 贝叶斯定理

    • 后验概率与联合概率分布的关系:

      $P(c|x)=\frac{P=(x,c)}{P(x)}$

    • $P(c|x)=\frac{P(c)P(x|c)}{P(x)}=\frac{P(c)P(x|c)}{\int P(c)P(x|c)~dc}$

      P(c):先验概率(人群中得病概率为1/1000000)

      P(x):证据

      P(c|x):后验概率(医院看到了症状之后判断的概率)

      P(x|c): likehood 似然(重点在另外的变量$\theta$上) ,likehood function目的是求$\theta$

      Prob(重点在变量上面)

7.2极大似然估计

fenleiqifenleiqi(不太懂 https://blog.csdn.net/chenjianbo88/article/details/52398181

7.3 朴素贝叶斯分类器(naive Bayes classifier)

假定属性独立地对分类结果发生影响

  • P(c)=$\frac{D_c}{D}$
  • $P(x_i|c)=\frac{D_{c,x_i}}{D_c}$
  • 拉普拉斯修正(为了解决某一个属性值在训练集中没有与某个类同时出现过就凉了 所以要假设出现了一次)
    • $\hat{P(c)}=\frac{|D_c|+1}{|D|+N}$
    • $\hat{P(x_i|c)}=\frac{|D+{c_i,x_i}|+1}{|D_c|+N_i}$
  • hint: 连续的分布用概率密度来代替,(一般用高斯分布)

7.4 半朴素贝叶斯分类器

One - Dependent Esitimator

  • SPODE

    超父带你飞

  • TAN

    • 计算条件互信息

      $I(x_i,x_j|y)=\sum _{x_i,x_j;c\in \gamma}P(x_i,x_j|c)log\frac{P(x_i,x_j|c)}{P(x_i|c)P(x_j|c)}$

    • 建完全图,权重设为上面的I

    • 构建最大带权生成树,挑选根变量,将变置为有向

    • 加入类别节点y,增加从y到每一个属性的有向边

  • AODE

7.5 贝叶斯网

(概率论知识反应不能,To be continued

  • V型例子:各位的智商x1 考试难度x2 最后的考试成绩x4,考完结果出来x1,x2就不独立了
  • 道德图(从marriage的梗里面获得)

Chap 8 集成学习

PS:使用https://runninggump.github.io/2018/12/05/%E6%88%90%E5%8A%9F%E8%A7%A3%E5%86%B3%E5%9C%A8hexo%E4%B8%AD%E6%97%A0%E6%B3%95%E6%98%BE%E7%A4%BA%E6%95%B0%E5%AD%A6%E5%85%AC%E5%BC%8F%E7%9A%84%E9%97%AE%E9%A2%98/ 里面的方法解决了博客的数学公式显示问题