机器学习第二次作业

预习笔记

第一章

• 主要内容
  • 模式识别和机器学习的基本概念
  • 模型的概念和组成
  • 特征向量的定义与计算
• 模式识别的基本概念与应用
• 机器学习的基本概念
  • 监督式学习，无监督式学习，半监督式学习，强化学习
  • 模型训练中存在的问题
    • 样本稀疏、不均匀、带有噪声
  • 模型泛化问题
    • 选择复杂度合适的模型
    • 正则化
  • 过拟合现象
  • 模型评估方法
    • 留出法、留一法、K折交叉验证
  • 模型性能度量
    • TP/FP/FN/TN
    • 准确度Accuracy、精度Precision、召回率Recall、特异度Specificity、F-Score
    • 混淆矩阵
    • PR曲线
    • ROC曲线

第二章

• • 基于距离的分类器
    • 欧氏距离、加权欧式距离、曼哈顿距离、马氏距离
    • 将样本到每个类的距离作为决策模型，把测式样本判定为与其距离最近的类
  • 特征白化
• MED分类器（最小欧氏距离分类器）
  • 以欧氏距离为度量
  • 以均值为类的原型
  • 只考虑到类原型的距离，不考虑类样本的分布，存在分类不合理的问题
• • 将原始特征映射到新的一个特征空间，使得在新空间中特征的协方差为单位矩阵，从而去除特征变化的不同及特征之间的相关性
  • 特征解耦：先去除特征之间的相关性
  • 特征白化：在解耦的基础上再对特征进行尺度变化
• 马氏距离
  • 表示数据的协方差距离，是一种有效的计算两个未知样本集的相似度的方法
• MICD分类器（最小类内距离分类器）
  • 以马氏距离为度量
  • 会选择方差较大的类

第三章

• • 贝叶斯决策和学习
• MAP分类器（最大后验概率分类器）
  • 将测试样本分类到后验概率最大的类
  • 先验概率：指根据以往经验和分析得到的概率
  • 后验概率：指在得到结果的信息后重新修正的概率，通过Bayes定理，用先验概率和似然函数计算出来
  • 决策产生的误差用概率误差表达，是未选择的类对应的后验概率
• 贝叶斯分类器
  • 在MAP分类器的基础上，加入决策风险因素
• 参数估计方法
  • 极大似然估计
    • 利用已知的样本结果，反推最有可能导致结果的参数值
  • 贝叶斯估计
    • 已知样本满足某种未知参数的概率分布，把待估计参数看作符合先验概率分布的随机变量。对样本进行观测的过程就是把先验概率密度转化为后验概率密度，利用样本信息修正了对参数的初始估计值。
• 无参数估计方法
  • KNN估计
  • 直方图估计
  • 核密度估计
    • 利用平滑的峰值函数来拟合观察到的数据，从而模拟真实的概率分布曲线

第四章

• • 线性判定与回归
• 生成模型
  • 给定训练样本，直接在输入空间内学习其概率密度函数p(x)
  • 优势是可以根据p(x)采样新的样本数据，可以测验出较低概率的数据，实现离群点检测。
  • 劣势是高维的x需要大量训练样本才能准确估计p(x)，否则会出现维度灾难
• 判别模型
  • 给定训练样本，直接在输入空间内估计后验概率，快速直接，省去了耗时的高维观测似然估计
• 线性判据
  • 如果判别模型f(x)是线性函数，则f(x)是线性判据
• 感知机算法
  • 根据标记过的训练样本学习模型参数
  • 并行感知机与串行感知机
• Fisher线性判据
  • 找到最合适的投影轴，使两类样本在该轴上投影的重叠部分最少，从而使分来效果达到最佳
• 支持向量机
  • 给定一组训练样本，使得两个类中与决策边界最近的训练样本到决策边界之间的距离最大
• 拉格朗日对偶问题

复习笔记

• 模式识别的概念

  

  • 模式识别的基本定义是根据已有知识的表达， 针对待识别模式，判别决策其所属的类别或者预测其对应的回归值，本质上是一种推理过程。模式识别在数学解释上可以看作一种函数映射f(x)，是关于已有知识的一种表达方式，也可以称作模型，狭义的模型由特征提取和回归器组成的。
  • 模式识别的任务形式有分类和回归，前者的输出量是输出量是离散的类别表达，后者则是单个或多个维度连续的信号表达（即回归值）。回归是分类的基础，离散的类别值是由回归值做判别决策得到的，所以分类器是由回归器与判别函数构成，其加上特征提取则构成广义的模型。
• 模型的组成
  • 特征提取：指从原始输入数据提取出更有效的信息
  • 回归器：将特征映射到回归值
  • 模型（广义）= 特征提取 + 回归器 + 判别函数
  • 模型（狭义）= 特征提取 + 回归器
  • 分类器 = 回归器 + 判别函数
  • 判别器可以是二类分类和多类分类，前者根据回归值的正负来确定分类，后者根据最大值来确定分类
  • 判别函数通常已知固定，所以不能当作模型的一部分

  • 

• 特征的概念
  • 可以用于区分不同类别模式的、可测量的量
  • 具有辨别能力：提升不同类别之间的识别性能
  • 鲁棒性：针对不同的观测条件，仍能够有效表达类别之间的差异性
  • 特征向量：指多个特征构成的（列）向量，长度为向量的模，方向为特征向量除其模长
  • 特征空间：每个坐标轴表示一个特征，空间中和坐标原点相连的向量代表着该模式的特征向量
• 特征向量相似度度量
  • 特征向量投影

    

    向量x到向量y的投影是向量x垂直投射到向量y方向上的长度，是个标量。投影的含义是向量x分解到向量y方向上的长度，投影长度越大，说明两个向量方向上越相似
  • 残差向量

    

  • 欧式距离

    

    • 两个特征向量的欧式距离可以表示两个向量间的相似程度，综合考虑了方向和模长
  • 余弦相似度

    

    只考虑方向，不考虑模长
• • 很显然想要进行模式识别离不开模型，想要确定模型，就需要先设计好模型结构，然后由机器学习通过训练样本得到模型参数

  

• 机器学习的分类
  • 监督式学习
    • 训练样本及其输出真值都给定情况下的机器学习，是最常见的学习方式
    • 监督式学习问题可以进一步被分为回归和分类问题
    • 通常使用最小化训练误差作为目标函数进行优化
  • 无监督式学习
    • 只给定训练样本、没有给输出真值情况下的机器学习算法，难度远高于监督式学习
    • 无监督式学习的目标是对数据中潜在的结构和分布建模，以便对数据作更进一步的学习。
    • 通常根据训练样本之间的相似程度来进行决策，典型应用有聚类和图像分割
  • 半监督式学习
    • 既有标注的训练样本、又有未标注的训练样本情况下的学习算法

    • 半监督式学习问题介于监督式和非监督式学习之间。

      许多现实中的机器学习问题都可以归纳为这一类。因为对数据加上标注耗时耗力，对于非专业人士也有一定的阻碍。而无标注数据的收集存储都是极为方便的

    • 可以看作有约束条件的无监督式学习问题，即标注过的训练样本用作约束条件，典型应用有网络流数据
  • 强化学习
    • 真值滞后反馈的过程，适用于累积多次决策动作才能知道最终结果好坏，很难针对单次决策给出对应的真值的任务，例如棋类游戏。
• 模型的泛化能力
  • 泛化能力是指训练得到的模型不仅要对训练样本要具有决策能力，还要对新的模式具有决策能力。
  • 训练样本存在的一些问题
    • 训练样本稀疏：给定的训练样本数量是有限的，很难完整表达样本的真实分布
    • 训练样本采样过程可能不均匀：有些区域采样密一些，有些区域采样疏一些
    • 一些样本可能带有噪声
• • 模型训练阶段表现很好，但是在测试阶段表现差

    

• 如何提高泛化能力
  • 选择复杂度适合的模型：模型选择
  • 正则化：在目标函数中加入正则项

    

• 评估方法与性能指标
  • 留出法
    • 直接将数据集D划分为两个互斥的部分，其中一部分作为训练集，另一部分用作测试集
    • 通常训练集和测试集的比例为70%：30%。
    • 数据集的划分要注意尽可能保持数据分布的一致性，避免因数据划分过程引入的额外偏差而对最终结果产生影响。在分类任务中，保留类别比例的采样方法称为分层采样
    • 同时要注意采用若干次随机划分避免单次使用留出法的不稳定性。
  • K折交叉验证法
    • 交叉验证法先将数据集划分为K个大小相似的互斥子集，每次采用K−1个子集的并集作为训练集，剩下的那个子集作为测试集。进行K次训练和测试，最终返回K个测试结果的均值

      

  • 留一法
    • 留一法是K折交叉验证K=样本数时候的特殊情况。即每次只用一个样本作测试集，其它所有样本来训练，计算开销较大
• 性能度量
  • 根据预测正确与否，将样例分为以下四种：
    • True positive(TP): 真正例，将正类正确预测为正类数
    • False positive(FP): 假正例，将负类错误预测为正类数
    • False negative(FN):假负例，将正类错误预测为负类数
    • True negative(TN): 真负例，将负类正确预测为负类数。
  • 准确度Accuracy

    

  • 精度Precision

    

  • 召回率Recall

    

  • 特异度Specificity

    

  • F-Score

    

    • F1-Score
      • F-Score设置a=1

        

• • 行为真值，列为预测值，元素为计数统计值
  • 对角线的值越大，表示模型性能越好
• • 横轴为召回率，纵轴为精度
  • 对各类别样本分布敏感
  • 越往右上凸突性能越好
• • 横轴为假阳性比例（FPR），纵轴为召回率
  • FPR = 1 - Specificity
  • 对各类别样本分布不敏感
  • 越往左上凸突性能越好
  • 对角线为随机识别算法的性能
  • 可使用曲线下面积（AUC）度量，其中AUC = 0.5时为随机识别算法

• • 把样本到每个类的距离作为决策模型，将测试样本判定为与其距离最近的类
• 常见的几种距离度量
  • 欧氏距离

    

  • 曼哈顿距离(Manhattan Distance)

    

  • 加权欧式距离
    • 对每维特征设置不同的权重

  • 

• • 二类MED分类器决策边界

    

    • 在高维空间中，该决策边界是一个超平面，垂直平分两个类原型的线

  • 存在的问题

    C1 = {(5, 4), (7, 0), (3.5, 1), (4.5, 3)}

    C2 = {(4, 4), (8, 5), (8, 3), (12, 4)}

    判断y = (4,5)所属类别

    

    根据MED决策方程，y属于C1类，但直观上y更接近于C2类。因为MED分类器没有考虑特征变化的不同以及特征之间的相关性。
• • 目标
    • 特征之间存在相关性和尺度不同的问题
  • 解耦
    • 通过W1实现协方差矩阵对角化，去除特征之间的相关性
    • 解耦后欧式距离不变
  • 白化
    • 通过W2对上一步变换后的特征再进行尺度变换实现所有特征具有相同方差
  • 过程

    

    

    

    

• MICD分类器（最小马氏距离分类器）
  • 二类MICD分类器决策边界

    

    

  • • 夸大了变化微小的变量的作用
    • 受协方差矩阵不稳定的影响，马氏距离并不总是能顺利计算出
    • 在均值相同时，MICD分类器会选择方差较大的类

      

  • 马氏距离的优点
    • 不受量纲的影响，两点之间的马氏距离与原始数据的测量单位无关
    • 由标准化数据和中心化数据（即原始数据与均值之差）计算出的二点之间的马氏距离相同
    • 马氏距离可以排除变量之间的相关性的干扰，综合考虑了类的不同特征之间的相关性和尺度差异

      

• 贝叶斯规则
  • 

• • 二分类决策边界
  • 平均概率误差
  • 决策目标
    • 最小环概率误差
• • 决策风险和损失

    

    

  • • 选择决策风险最小的类。即对于所有测试样本，选择损失最小的类，以达到期望损失最小
    • 期望损失，即所有样本的决策损失之和
  • 朴素贝叶斯分类器
    • 如果特征是多维，学习特征之间的相关性会很困难

      

• • 最大似然估计

    • 

  • 先验概率估计

    

    先验概率的最大似然估计就是该类训练样本出现的频率
  • 观测概率估计：高斯分布

    

    

  • 均值估计
    • 无偏估计

      

    • 高斯分布均值的最大似然估计等于样本的均值

      

  • 协方差估计
    • 有偏估计

      

    • 高斯分布协方差的最大似然估计等于所有训练模式的协方差

      

    • 协方差估计的修正

      

  • • 已知样本满足某种未知参数的概率分布，把待估计参数看作符合先验概率分布的随机变量。对样本进行观测的过程就是把先验概率密度转化为后验概率密度，利用样本信息修正了对参数的初始估计值
    • 参数的后验概率

      

    • 贝叶斯估计：高斯观测似然

      

      • 参数（高斯均值）先验概率

        

      • 参数（高斯均值）后验概率

        

        

        

      • 分析
        • 当𝑁𝑖足够大时， 样本均值m就是参数θ的无偏估计

        

        • 参数先验对后验的影响

          

    • 贝叶斯估计：不断学习能力
      • 允许最初的、基于少量训练样本的、不太准的估计
      • 随着训练样本的不断增加，可以串行的不断修正参数的估计值，从而达到该参数的期望真值
    • 流程

      

    • 贝叶斯估计一般比最大似然估计复杂，但能力也更强

• • 

    • 优点
      • 可以自适应的确定𝒙相关的区域𝑅的范围
    • 缺点
      • KNN概率密度估计不是连续函数
      • 不是真正的概率密度表达，概率密度函数积分是 ∞ 而不是1。例如，在k=1时

  • 

    

    • • 固定区域𝑅：减少由于噪声污染造成的估计误差
      • 不需要存储训练样本
    • • 固定区域𝑅的位置：如果模式𝒙落在相邻格子的交界区域，意味着当前格子不是以模式𝒙为中心，导致统计和概率估计不准确
      • 固定区域𝑅的大小：缺乏概率估计的自适应能力，导致过于尖锐或平滑
    • 双线性插值

      

    • 带宽选择

      

  • • 以任意待估计模式𝒙为中心、固定带宽ℎ，以此确定一个区域𝑅
    • 原理

      

    • 概率密度估计

      

    • 核函数

      

    • • 以待估计模式𝒙为中心、自适应确定区域𝑅的位置（类似KNN）
      • 使用所有训练样本，而不是基于第 𝑘 个近邻点来估计概率密度，从而克服KNN估计存在的噪声影响
      • 如果核函数是连续，则估计的概率密度函数也是连续的
    • • 与直方图估计相比， 核密度估计不提前根据训练样本估计每个格子的统计值，所以它必须要存储所有训练样本
    • • 带宽ℎ决定了估计概率的平滑程度
      • 因为给定的训练样本数量是有限的，所以要求根据这些训练样本估计出来的概率分布既能够符合这些训练样本，同时也要有一定预测能力，即也能估计未看见的模式

• • 优势
    • 可以根据p(x)采样新的样本数据，可以测验出较低概率的数据，实现离群点检测。
  • 劣势
    • 高维的x需要大量训练样本才能准确估计p(x)，否则会出现维度灾难
• • 给定训练样本，直接在输入空间内估计后验概率
  • • 快速直接，省去了耗时的高维观测似然估计
• • 可以用于二类分类，决策边界是线性的
  • 也可以用于多类分类，相邻两类之间的决策边界也是线性的
  • • 计算量少：在学习和分类过程中，线性判据方法都比基于学习概率分布的方法计算量少
    • 适用于训练样本较少的情况
  • 数学表达

    

  • w的方向

    

  • w0的作用
  • 任意样本到决策边界的距离r r的绝对值可以作为confidence score：值越大，这个点属于正类或者负类的程度越大，𝑓(𝒙)是样本𝒙到决策面𝐻的代数距离度量
  • 学习方法

    

    

    

• • 预处理

    

  • 目标函数

    

  • 并行感知机
    • 训练样本并行给出
    • • 对所有被错误分类的训练样本，其输出值取反求和

        

        

      • 偏导不含有a，不能通过令偏导为0来求a
  • 梯度下降算法

    

    步长用来调整更新的幅度，每次迭代可以用不同的步长

    参数更新

  • 参数a的更新公式（梯度下降算法）

    

    带入并行感知机的梯度公式：

    

  • 串行感知机算法
    • 训练样本是串行给出的

    • 

      

      

    • 算法流程

      

  • 收敛性
    • 如果训练样本是线性可分的，感知机算法理论上收敛于一个解
    • 这只是保证算法会停止，但是最终结果不一定是全局最优

    • 

• • 投影后，使得不同类别的样本分布的类间差异尽可能大，同时使得各自类内样本分布的离散程度尽可能小
  • 类间样本的差异程度
    • 用两类样本分布的均值之差度量
  • 类内样本的离散程度
    • 用每类样本分布的协方差矩阵表征
• • 最大化总间隔
• • 在数学最优问题中，是一种寻找变量受一个或多个条件所限制的多元函数的极值的方法
  • KKT条件
    • 是解决最优化问题的时用到的一种方法。这里提到的最优化问题通常是指对于给定的某一函数，求其在指定作用域上的全局最小值
  • 设d∗是拉格朗日对偶问题的最优解，则不管原问题是不是凸优化问题，都一定有d∗=f∗则强对偶成立。这时对偶函数是原问题的紧致下界

  • 

    则弱对偶成立
  • 能不能取到强对偶条件取决于目标函数和约束条件的性质。如果满足原问题是凸优化问题，并且至少存在一个绝对可行点，那么就具有强对偶性

学习心得与总结

• 机器学习是计算机及其应用领域的一门重要学科。通过这学期的课程学习，大概了解了机器学习的一些基本方法，特别是监督式学习方法，如感知机、K近邻法、贝叶斯法、支持向量机等。
• 总体来说这门课虽然是介绍性的入门课程，但还是由浅入深的。通过阐明思路以及给出必要数学推导的方法，结合部分具体问题和实例，为进一步学习机器学习知识打下基础。
• 当然，这门课因为对于数学、特别是线性代数和概率论的高要求，需要对之前学习过的内容做一些概念性的整合。其实课程中介绍的很多方法还是缺少例子的，难以有整体性的理解，如果概念还不清晰就更致命了。确实需要实践环节来加深印象，可是从理论到实践跳的有点太快了，这方面的引导可能由于不可抗力比较缺乏吧。