机器学习课程总结（个人向）

前言

通过看课件PPT整理的笔记，没有截图

由于大部分内容已经耳熟能详了，故记录比较简略，只记录了一些概念和需要记忆的地方。

里面有较多的个人观点，未必正确。如有错误，还请各位大佬指正

正文

绪论

机器学习的定义：程序在任务T上通过经验E对目标P进行优化
TPE
任务 性能指标 训练经验

目标函数：状态->评价/行动
模型复杂度（函数描述能力）<--权衡-->数据量

##########LMS算法：均方误差+梯度下降
delta = Σ(y'-y)^2
w <- w+ n*(y'-y)*X
n:学习率

执行系统、鉴定器、泛化器、实验生成器？？
执行系统：输入问题、输出解决方案
鉴定器：输入解决方案、输出训练样例
泛化器：输入训练样例、输出假设（也就是拟合的结果分布）
实验生成器：输入假设、输出问题

概念是什么、假设是什么
概念：对象或事件集合的子集，用布尔函数表示
假设：我们对这个概念的拟合，可以用布尔函数表示，也可以用对属性约束的合取范式来表示。
例如<A1,B2,C1,?>，表示满足A1、B2、C1的任意实例都属于该假设

---------------------------------------------

概念学习

X、H、c、D
X实例集：样本空间
H假设集：在该样本空间上的任意一个布尔函数，概念空间
c目标概念（布尔函数）：X->{0,1}
D训练样例集：{<xi，c(xi)>}，其中xi∈X
学习目标：找到h∈H，使得任意x∈X有h(x)=c(x)

归纳学习假设：
由于样本空间X过大，我们假设：
任意<x,c(x)>∈D都有h(x)=c(x)，且D足够大时，
那么我们就认为，h可以使得大部分x∈X有h(x)=c(x)

搜索空间：搜索概念空间中的元素，样本空间中的概念边界
##########偏序关系：more_general_than_or_queal_to
hk(x)=1 -> hj(x)=1
记作hj > hk

##########Find-S算法
从最特殊假设开始，枚举D中正例，哪个属性不满足就取哪个并集加入当前假设，不管负例

##########候选消除算法
Find-S的升级版，输出所有满足条件的假设集合，给出偏序集合的上下界
一致：同时满足D中正例和负例的h
变型空间：所有与D一致的h的集合，记为VS(H,D)
列表后消除算法：暴力枚举出H中的所有假设，一一验证
求出极大一般成员G集合和极小特殊成员S集合，作为上下界，VS(H,D)中所有元素必定位于该上下界之间
步骤：
若为正例，去除G中的不一致假设，泛化S中不一致的假设
若为反例，去除S中的不一致假设，泛化G中不一致的假设
若包含错误的概念数据，最终会收敛到一个空集

无偏学习的无用性，有偏性更强，归纳能力更强

---------------------------------------------

决策树

合取、析取、异或的决策树画法
ID3和C4.5，Splitinfo：划分后每个类别的占比的-plogp之和
错误率降低剪枝（后剪枝，修剪后在训练集上的性能不能低于原树）
规则剪枝（把每条路径的错误率算出来，单独剪枝，而不是统计子树中的总错误率）

还可以引入属性划分代价,把Gain^2/Cost作为划分依据

---------------------------------------------

ANN

感知器训练法则
w=w+Δw
Δw=n*(y'-y)*x
这里的输出是被二值化之后的y‘和y

delta法则=LMS法则（规则）
和感知器训练法则类似，但输出是没有加二值化的（阈值单元）
感知器训练法则是加入了阈值单元的输出，直接进行梯度下降

梯度下降：对整个训练数据进行计算（真实梯度）
随机梯度下降：一个一个数据的计算梯度（引入了扰动，避免梯度下降被局部极小值干扰）

输出单元δ值计算：y'*(1-y')*(y-y')（本质上是一层传递，最初δ为(y-y')即残差）
（这里的y'*(1-y')其实是链式法则求导到sigmoid的特征）
隐藏单元δ值计算：o*(1-o)*Σwi*δi
Δwi->j = n * δj * xi->j（其实大部分神经网络的xi->j都是xi吧？）
链式求导法则

增加冲量（叠加上次的梯度）
sigmoid、relu、tanh、leaky relu
在误差函数中添加L2正则化项，增加对目标函数的偏导（斜率）
交叉熵损失函数

---------------------------------------------

贝叶斯推理

（从观测到预测，从看得见的现象到内在本质的推理）

后验=似然*先验/全概率
先验P(h)：在对概念进行观测之前，各个假设成立的概率，具有主观色彩
先验P(D)：观测结果D的先验概率（一般认为是等概率吧）
似然P(D|h)：在假设h成立的条件下，观测到数据D的概率
后验P(h|D)：在已知观测D的情况下，假设h成立的概率
极大后验假设hMAP、极大似然假设hML：就是使得后验、似然概率最大的假设

Brute-Force贝叶斯概念学习（求hMAP）
枚举每个h，P(h)=1/|H|，似然：一致=1，不一致=0
计算出来的全概率先验为|VS(H,D)|/|H|

一致学习器：在训练集上正确率100%

（证明题）使用误差平方的损失函数会使得输出为极大似然假设
（主要思路：似然概率为每个样本的似然概率乘积累积，因为di服从正态分布，里面具有误差平方项，取argmax操作后，可以化简为最小误差平方和的形式）
贝叶斯学习器：L(X,H,D),D中标签具有噪声
选用正态分布来描述噪声

把预测离散的标签{0,1}，改为预测概率[0,1]
暴力法：收集每种x值的概率，直接输出
梯度搜索，用损失函数G(h,D)，计算预测结果的交叉熵，然后反向传播
但预测分类时并不能直接用极大似然假设h进行分类，需要通过后验概率加权合并所有假设ΣP(cls|hi)*P(hi|D)
由于合并过程代价过大，提出了Gibbs算法
Gibbs算法
按照P(h|D)的分布对H进行采样，用采集的h来预测h(x)
最差错误率为全部合并的两倍

朴素贝叶斯分类器
目标函数为离散
设x=(a1,a2,a3...,an)，ai为样本x的第i个属性
求P(y|x)最大的y
使用贝叶斯公式转换后：求P(x|y)*P(y)
此时若x各个属性相互独立，则P(x|y)=ΠP(ai|y)
也就是说，我们只需要拟合P(ai|y)这n个函数，极大的削减了搜索空间
直接使用频率估计概率，拟合这些函数即可
m-估计（应该是马尔可夫估计？）
在样本数据少时，P(ai|y)=(n(ai)+mp)/(n(y)+m)，p为先验估计，m为等效样本大小（呃，本质上就是直接加上m个分布为p的样本来补足）
文本分类问题：
预处理计算P(wi|tagj)，空间复杂度O(vocabulary*tag_nums)，扫描一遍数据集即可得出

---------------------------------------------

遗传算法

GA(fit,fit_thresh,p,r,m)：
p：种群规模，r：产生杂交后代占比，m：突变概率
维护假设全集H的子集P（population）
使用fit函数计算每个h∈P的适应度（fit值），
当最大的fit值都无法满足fit_thresh时，进行遗传算法
1、根据适应度加权概率抽取样本p*(1-r)个，保留到下一代
2、选取r*p/2对样本，杂交得到后代，添加进来
3、再对下一代的m*p个样本进行突变
4、更新，计算每个样本的适应度
主要算法设计：适应度评估、选择算法、杂交操作、变异操作
目的是保留更多样性的群体，削弱局部极小值的影响
无需使用梯度计算，但需要大量适应度计算，编码定义较为困难

---------------------------------------------

无监督学习

聚类Kmeans，每个点找离他最近的中心点，然后中心点迭代为他所管辖点的中心，劣势：异常值、k值敏感、初始种子敏感、非线性边界聚类
SSE指标计算，每个中心到它所管辖的所有节点的距离
聚类结果的表示：聚类中心、每个点的分类、使用众数来表示聚类、使用聚类树表示
层次聚类：自上而下（分裂）、自下而上（合并）
合并法：类似并查集，需要计算两个聚类之间的距离（最近（单连接）、最远（全连接）、平均链接（多个点对距离和的均值）、聚类中心法）
样本距离计算：欧几里得、曼哈顿、闵可夫斯基、切比雪夫

混合矩阵：两个样本a、b（一般只有布尔属性）中，枚举所有属性，统计a=0/1且b=0/1的个数，写成矩阵形式
样本匹配距离：
(n01+n10)/(n00+n01+n10+n11)（简单匹配距离）（对称布尔属性，两类别概念对称）
(n01+n10)/(n01+n10+n11) （Jaccard距离）（当状态1出现较少时，非对称布尔属性）
推广：不匹配数/总数
相似度衡量：
向量夹角余弦相似度a·b/(|a||b|)
数据标准化：
范围标准化：把数据限制到[0,1]
Z-score：(x-μ)/s，这里s是所有样本到均值的绝对值的平均数，不是标准差σ

各类数据的通用处理方式：
比例度量属性，将非线性的数据进行线性化后，再进行处理
符号属性（标签）->转换为独热编码
顺序属性->连续化，作为连续属性处理
混合属性->找一个主导全部转换过去 || 所有一起做加权平均

聚类评估：
使用一组有标签的数据，利用训练好的聚类模型对其进行分类，评判各个类下的信息熵、纯度、SSE、中心间差异、混淆矩阵（就是多分类评价的那一套AUC、 Acc、 Precision、 Recall、 F1）

---------------------------------------------

基于实例的学习

KNN找最邻近的k个点，KD树实现
优化：对距离进行加权，使用全部样本进行查询
维度灾难：降维，(x,y)->x+ky或者y+kx，然后选取最佳的k（把分类问题维度转换为优化维度），剔除无关属性（留一法，去除一个观察效果），坐标轴伸展
KNN分类与回归
局部加权线性回归
（取局部进行拟合、取全局进行加权、取局部进行加权拟合）
径向基函数RBF
把加权的函数换成高斯函数
每个邻域中的参考值x，都需要对应一个核函数
消极学习：KNN和局部加权线性回归
积极学习：RBF（需要训练，损失函数为训练集中的每个数据预测的平方误差） 

关于积极学习和消极学习还可以参考以下博客：
https://blog.csdn.net/m0_38103546/article/details/81229290

---------------------------------------------

回归学习

线性回归
最小二乘法h(x) = w0+w1x1+...+wnxn=W·X
W = (Xt*X)^(-1)*Xt*y
（作业）使用梯度下降推导线性回归、逻辑回归、softmax回归
逻辑回归就是在线性回归的输出加入一个sigmoid，采用交叉熵
sofmax回归就是多个线性回归的基础上，把所有输出加一个softmax操作，采用交叉熵
正则化
应该主要考梯度计算

---------------------------------------------

线性分类器

线性判别函数（分类时计算量小，比朴素贝叶斯快，但错误率可能更高）
线性可分与线性不可分
SVM证明（略）

线性多分类器的建立
一对其余：wi/wi'法
一条边界划分某一个类和其余类
时间复杂度O(cls_num)
存在不确定区域
一对一：wi/wj法
任意两个类之间都有边界划分
时间复杂度O(cls_num^2)
存在不确定区域
但比wi/wi'更容易线性可分
多对多：
同时求解cls_num个线性函数，将他们的最大值作为分类结果
不存在不确定区
一般采用这种方案

最小距离准则
分完类之后，查询x与各类均值点的距离，最小的就是最近的
可证明也是一种线性分类器（在采用欧氏距离时）
但分类效果不理想

感知器准则
样本规范化：
x->增广（1，x1,x2,x3）->把负类进行取相反向量
这样目的就转换为，找一个平面，使得所有点都在一侧
解区：能正确分割两类数据的w向量（分割面的法向量）取值范围，越大说明解越可靠
有了解区，我们就可以进一步限制线性分类器的精度，使用余量来控制法向量的范围
感知器准则函数
求和所有错误分类的计算结果 Σ-wTx，记为Jp(w)，最小化该值
假设所有样本都正确分类（或在边界上），则Jp(w)=0，否则该值会大于0
然后我们就可以愉快地求dJp(w)/dw的偏导，进行梯度下降，直到错误分类集合为空，停止。
而这个偏导恰好等于Σ-x，也就是所有错误分类的向量之和
我们把它乘以学习率，然后叠加到w上，就可以使用梯度下降训练线性分类器了
*但是，这个方法只适用于线性可分的情况，不可分的话则永远不会停止

最小平方误差准则（SVM使用的准则）
X增广且规范化之后
Xw=b
根据一系列推导，最优MSE的w解为(Xt*X)^(-1)*Xt*b（Xt表示X的转置）
但由于计算量较大，Xt*X可能不可逆，因此实践中并不采用
Widrow-Hoff算法：
发现，如果将梯度下降的步骤增量改为：w_{k+1}=w_{k}-ρk*Xt*(X*w_{k}-b)
并且取ρk=ρ1/k，无论Xt*X是否可逆，w均能收敛到一个很好的解

---------------------------------------------

特征选择与稀疏学习

贪心选择特征子集：
前向搜索，一轮一轮的选，看当前加入哪个特征最优就选哪个
后向搜索，看当前哪个特征拿走后变得更优就删除哪个特征
双向搜索，结合上述两种，直到找到一个公共元素

选出来的特征子集的评价手段：
信息增益等指标

三类特征选择方法
过滤式
relief算法，调整每个特征的权重
每次随机一个样本x，找到最近的同类样本a和最近的不同类样本b，调大(a-x)中小于(b-x)的特征权重，调小(a-x)中大于(b-x)的特征权重。
relief-F，推广到多分类问题，假设类别有k类，每次找1个同类邻近和k-1个不同类邻近样本（每个类都找一个最近的），最后根据每个类别的样本占比加权进行权重调整
包裹式
LVW算法
直接随机特征子集，然后训练，交叉验证，评估
多次取最优的。（怪不得叫Las Vegas Wrapper）
嵌入式选择
把特征选择和学习器训练融为一体，学习器自动选择特征

稀疏表示（行表示样本、列表示属性）？？？
字典学习
对一个数据集X
学习字典B和表示α
最小化 Σ|x-Bα|^2+λΣ|α|
有点意思，就是纯将数据集的特征进行变换，并且使得变换后的属性比较稀疏