统计学习

基本概念

联合概率分布

监督学习假设输入X与输出Y 遵循联合概率分布P（X，Y）

训练数据和测试数据被看作依联合概率分布P(X,Y)独立同分布产生的

假设空间

监督学习的目的是找到一个最好的描述输入到输出的映射模型

输入空间到输出空间的映射的集合，hypothesis space

统计学习三要素

模型

策略

算法

要学习的条件概率分布或决策函数

包含模型的所有可能的条件概率分布或决策函数

cost function

0-1 loss function

quadratic loss function

absolute loss function

logarithmic loss function

1 if Y != f(X), else 0

(Y - f(X))^2

|T - f(X)|

-logP(Y|X)

经验风险／损失

f(X)对于训练数据集的平均损失

当样本亮趋于无穷时，经验风险趋于期望风险
但通常样本量有限，所以不应用经验风险估计期望风险

经验风险最小化
empirical risk minimization ERM

结构风险最小化
structural risk minimization

最大似然估计
maximum likelihood estimation

需要大量样本， 否则可能过度拟合

防止过度拟合，等价于正则化

在经验风险上加上表示模型复杂度的正则化项(regularizer)或罚项(penalty term)
惩罚复杂模型，倾向简单模型

对训练数据和未知数据都有较好预测

最大后验概率估计(maximum posterior probability estimation, MAP)

训练误差与测试误差

过度拟合与模型选择

正则化

交叉验证

通过惩罚算法复杂度来倾向于经验损失和算法复杂度同时小的模型

k-fold cross validation

把数据分成k份，每次用k-1份训练，另一份测试，
重复k次取平均测试误差最小的模型

泛化能力

模型对未知数据的预测能力

泛化误差上界

模型类型

生成模型 generative model

从数据学习联合概率分布P(X,Y)，然后求出条件概率分布P(Y|X), P(Y|X) = P(X,Y) / P(X)

判别方法 discriminative model

从数据直接学习决策函数f(X)或条件概率分布P(Y|X)作为预测模型

给定输入X来产生输出Y，典型：朴素贝叶斯，隐马尔可夫模型

关心对给定的X，应该预测什么样的输出Y，典型：决策树，k近邻，感知机，逻辑回归，SVM，最大熵 等

可以还原出联合概率分布P(X,Y)， 收敛速度更快，适用于隐变量

不能还原出联合概率分布P(X,Y)， 准确率更高，
可对数据进行抽象，定义并使用特征，因此简化学习问题

分类模型 classification

precision

recall

TP / (TP + FP)

TP / (TP + FN)

F1

precision和recall的调和均值

2/F1 = 1/Precision + 1/Recall

标注问题 tagging

输出Y是一个标注序列

用于NLP，信息抽取。典型：隐马尔可夫模型，条件随机场

回归问题 regression

常用平方损失函数，如最小二乘法least squares

模型

感知机 perceptron p40

二类分类的线性分类模型
输入：实例的特征向量
输出：实例的类别，1或-1

f(x) = sign(w*x + b)

采用随即梯度下降法(stochastic gradient descent)学习，不断降低cost

当训练数据集线性可分时，感知机学习算法是收敛的
但可能存在多个解，依赖于初值及训练数据的顺序

k近邻 p54

在训练集中找出距离最近的k个数据实例，根据多数表决判断当前数据点的分类。没有学习过程。

k值的选择

距离度量

欧氏距离

Minkowski距离

Manhattan距离

k太小，approximation error小，estimation error大，对噪声点更敏感

k太大，approximation error大，estimation error小，使模型简化

通常采用cross validation选取最优k值

如何高效找出k近邻数据点？

kd tree p57

对k维空间中的实例点进行存储及快速检索的二叉树形数据结构

适用于数据量远大于空间维数的情况
当二者接近时效率骤降如线性扫描

创建：

  1. 构造根结点，选择x(1)为坐标轴，以所有数据在该轴上数值的中位数切分出两个子区域
  2. 根结点包含落在切分面上的数据点
  3. 重复切分步骤，在深度为j的节点选择x(l)为轴，l = (j mod k) + 1
  4. 重复直到切分出的两个子区域都没有节点

搜索：

  1. 从根出发找出包含目标点的叶结点
  2. 以此叶结点为当前最近点
  3. 递归地向上回退，在每个节点：
    3.a 若该点保存的数据点离目标更近，重置该节点为当前最近点
    3.b 当前最近点一定存在于该节点一个子节点对应点区域，检查另一个子节点的区域是否覆盖更近的区域，若覆盖则搜索该子节点

朴素贝叶斯 p62

假设全部特征相互独立，由训练数据推测X和Y的联合概率分布P(X,Y)，然后基于此分布对给定输入x计算后验概率最大的输出y

实现简单，学习和预测效率都很高，但特征互相独立的假设可能不准确

贝叶斯估计 p66

引入一个常量以保证不会出现0概率，否则会影响后验概率的计算

决策树 decision tree p70

需要与训练数据矛盾较小，且很好的泛化能力的决策树

常见算法

ID3 p78

C4.5

Classification And Regression Tree

特征选择

information gain，通过熵entropy衡量

相当于极大似然法进行概率的选择

用最大info gain选择特征

用最大info gain ratio选择特征

information gain ratio = info gain／训练数据的经验熵H(D)

info gain ratio可以避免训练数据经验熵的差异带来的误差

剪枝以防过度拟合

将决策树的节点数加入cost function以惩罚过长的树

正则化的极大似然

只考虑父子节点之间cost的差值，因此可以用动态规划的算分实现

给定输入随机变量X的条件下输出随机变量Y的条件概率分布的学习方法

  1. 基于训练数据生成决策树，要尽量大，特征选择：回归用least squares，分类用gini index最小化
  2. 用验证数据集给树剪枝并依据最小cost选择最优子树

CART生成

❓回归树 机器学习实战p162


遍历每个特征j的每个可能取值s（训练数据集中出现过的值）将数据二元切分，
对左右两份数据分别求误差（方差之和var(Y)*X.size，引入数据集size来惩罚切出的大数据集）然后相加，
找到最优的j和s使得切分后两份数据的误差之和最小，但如果一下情况则不切分并返回数据集的Y的均值为叶结点：

  1. 进行切分前所有数据的y值都相等
  2. 即使最优切分的误差减小也不明显
  3. 切出的数据集太小

分类树

用gini index选择特征，同时决定该特征的最优切分点的值

Screen Shot 2018-06-23 at 15.25.11
Screen Shot 2018-06-23 at 15.26.04
Screen Shot 2018-06-23 at 15.26.08

❓CART剪枝 p88 机器学习实战p170

Logistic Regression p92 https://www.coursera.org/learn/machine-learning/resources/Zi29t

Logistic Distribution

Screen Shot 2018-06-23 at 15.55.15

Screen Shot 2018-06-23 at 15.56.54

binomial logistic regression

Screen Shot 2018-06-23 at 15.58.04

❓最大熵 maximum entropy model p96
https://blog.csdn.net/qianwenhong/article/details/41479671
https://blog.csdn.net/pipisorry/article/details/51695283

满足约束的条件下，在所有可能的概率模型中，熵最大的是最好的模型
熵最大表示等概率，即已知的信息最少

Screen Shot 2018-06-23 at 16.22.50

极大似然估计

假设训练数据与真实数据是独立同分布的，
在给定的训练数据下，估计出最有可能符合训练数据概率分布的模型参数

互信息

模型学习的最优化算法

improved iterative scaling p104

拟牛顿法 BFGS p106

设当前参数向量为w = (w0,w1,w2,...wn)
重复寻找w+d = (w0+d0,w1+d1,...wn+dn)使模型的对数似然函数值增大，直到找到最大值

click to edit

支持向量机 SVM p110

线性可分SVM p111

二类分类问题，且所有数据点线性可分（存在一条直线可以分割不同类别的数据）

找到正确划分数据的，使分割带最宽的w*x + b = 0
（凸二次规划问题 convex quadratic programming）
Screen Shot 2018-06-24 at 11.39.34

函数间隔／几何间隔（正则化的函数间隔） Screen Shot 2018-06-24 at 11.35.46

只依赖于最靠近分离超平面的数据点，称之为support vector，不需要海量数据训练，但必须提供关键的数据点

凸优化 convex optimization p114

对偶算法 dual algorithm p118

应用拉格朗日对偶性，求解对偶问题来得到原始问题的最优解

http://www.hanlongfei.com/%E5%87%B8%E4%BC%98%E5%8C%96/2015/09/25/cmu-10725-optimization/

Screen Shot 2018-06-24 at 12.48.06

对偶问题更容易求解，而且自然引入核函数，进而推广到非线性分类问题

  1. 构建拉格朗日函数 - 对每一个不等式约束引进拉格朗日乘子
    Screen Shot 2018-06-24 at 12.52.37
    先求L(w,b,a)对w，b的极小，再求对a的极大
  1. 对偶形式：分类决策函数只依赖于输入x和训练样本输入的内积
    Screen Shot 2018-06-24 at 13.17.49
    a必须大于0. 最优w和b只依赖于训练数据中ai大于0的数据点xi，称为support vector

线性支持向量机 p124

对每个样本点引入一个松弛变量，使得 Screen Shot 2018-06-24 at 13.27.32
同时支付一个代价，使目标函数变为 Screen Shot 2018-06-24 at 13.28.13
即如下凸二次规划
Screen Shot 2018-06-24 at 13.29.34

对偶形式

Screen Shot 2018-06-24 at 13.32.06

Screen Shot 2018-06-24 at 13.37.52

合页损失函数 hinge loss function

线性SVM学习的另一种解释：最小化 Screen Shot 2018-06-24 at 13.47.16
第一项是经验损失 Screen Shot 2018-06-24 at 13.49.37
分类正确时为0，否则为1-yi(w*xi + b)

不仅要求分类正确，确信度也要足够高时损失才为0，对学习有更高的要求

非线性SVM p130

❓kernel trick

基本思想

分类决策函数

将非线性问题变换为线性问题求解。例如定义N个核（landmark），将原数据X转换成到各个核的远近程度的线性组合

将欧式空间的输入X映射到高维甚至无穷维的特征空间（希尔伯特空间）
以线性问题方式在特征空间求解
在学习与预测中，只定义核函数，不显示定义映射函数

❓如何选择合适的核函数？

Screen Shot 2018-06-24 at 14.54.34

正定核 p134

常用核函数

多项式核函数 polynomial kernel function Screen Shot 2018-06-24 at 14.39.22

高斯核函数 Gaussian kernel function Screen Shot 2018-06-24 at 14.39.43

字符串核函数 string kernel function
（定义在离散数据集合上，如字符串集合。用于文本分类、信息检索、生物信息学等方面）
相同子串越多越相似，核函数值就越大，可由动态规划快速计算

凸二次规划实现 统计学习p140

❓Sequential Minimal Optimization 机器学习实战p94

提升方法 boosting p153 机器学习实战p118

AdaBoost

优缺点

要解决的问题

如何在每一轮训练中改变训练数据的概率分布或权值？

  • 提高那些被上一轮弱分类器错判的样本的权值，降低被正确分类的样本的权值

如何将弱分类器组合成强分类器？

  • 加权多数表决，加大分类误差率低的分类器的权值，减小错误率高的分类器的权值
  • 最流行的弱分类器：单层决策树 decision stump

算法 p153

  1. 初始化训练数据权值分布 D1 = (w11, w12, w13, ..., w1N)
  2. 对m = 1,2,...,M ❓如何决定M的值？
    2.1. 使用具有权值分布Dm的训练数据学习得到分类器Gm(x): X -> {-1,+1}
    2.2. 计算Gm(x)在训练数据上的分类误差率Em
    2.3. 计算Gm(x)的权值 Screen Shot 2018-06-24 at 17.58.44 （这里是自然对数）
    2.4. 更新训练数据的权值分布 Screen Shot 2018-06-24 at 18.00.05
    若正确分类更新为 Screen Shot 2018-07-03 at 14.01.43 若错误分类更新为 Screen Shot 2018-07-03 at 14.01.50
    （被错误分类的样本的权值将会放大，在下一轮学习中起到更大的作用）
  3. 构建基本分类器的线性组合 Screen Shot 2018-06-24 at 18.02.20

训练误差界 p158

最终分类器的训练误差 Screen Shot 2018-06-24 at 18.11.39
说明可以在每一轮学习中选取适当的Gm使得Zm最小，从而使训练误差下降最快

二类分类问题的训练误差界 Screen Shot 2018-06-24 at 18.15.14
说明AdaBoost的训练误差是以指数速度下降的

❓前向分步算法 p160

因为学习的是加法模型，如果能够从前向后，每一步只学习一个基函数及其系数，逐步逼近优化目标函数，就可以简化复杂度

提升树 boosting tree p162

以decision tree为基函数的boosting Screen Shot 2018-06-24 at 18.29.36

树的线性组合可以很好的拟合训练数据，即使输入输出的关系很复杂也如此，因此boosting tree是很有效的学习算法

梯度提升 gradient boosting p166

利用损失函数的负梯度在当前模型的值作为回归提升树中的残差值，拟合一个回归树 Screen Shot 2018-06-24 at 18.38.23

期望极大算法 Expectation Maximization p170

当概率模型包含隐变量或潜在变量等未观测到的变量，就不能用极大似然或贝叶斯估计法
EM就是考虑到这些隐含变量的极大似然估计法，或极大后验概率估计法
https://www.jianshu.com/p/1121509ac1dc

算法

设观测数据为Y=(Y1,Y2,...,YN), 未观测数据为Z=(Z1,Z2,...,ZN)
则观测数据的似然函数为 Screen Shot 2018-06-25 at 18.26.04

  1. 选择参数的初值theta0，开始迭代
  2. E步骤：计算 Screen Shot 2018-06-25 at 18.27.45
    Screen Shot 2018-06-25 at 18.28.24 是在给定观测数据Y和当前参数估计thetai时，隐变量Z的条件概率分布
  3. M步骤：求使Q(theta,theta_i)极大化的theta，确定下一次迭代的参数的估计址theta_i+1 Screen Shot 2018-06-25 at 18.30.36
  4. 重复2，3步直到收敛

EM和高斯混合模型学习 p178

高斯混合模型 Screen Shot 2018-06-25 at 18.33.11 其中 Screen Shot 2018-06-25 at 18.33.42

隐马尔可夫模型 p186

关于时序的概率模型，由一个隐藏的马尔可夫链随机生成不可观测的状态随机序列（state sequence），
再由各个状态生成一个观测而产生观测随机序列（observation sequence）的过程

构成

初始状态概率向量π

状态转移概率矩阵A Screen Shot 2018-06-25 at 19.57.34

观测概率矩阵B Screen Shot 2018-06-25 at 19.58.08

假设

任意时刻的状态只依赖于上一时刻

任意时刻的观测只依赖于该时刻的马尔可夫链的状态

算法

前向算法 p190

后向算法 p193

学习算法 p196

监督学习

已知观测序列及对应的状态序列，直接用极大似然法估计隐马尔可夫模型的参数

状态序列通常很难获得

非监督学习

Baum-Welch算法

将观测序列作为观测数据，状态序列作为不可观测的隐变量，
可以用EM算法估计隐马尔可夫模型的参数

参数估计 p198

Screen Shot 2018-06-26 at 18.17.35
所有T之前时刻的任一时刻从状态i转到状态j的概率之和，比上任一时刻处于状态i的概率之和

Screen Shot 2018-06-26 at 18.17.51
在T及其之前所有时刻，处于状态j的概率之和（观测O在该时刻的值ot必须是k），比上在T及之前所有时刻处于状态j的概率之和

Screen Shot 2018-06-26 at 18.17.56
初始概率分布就是该状态在第一时刻出现的概率

给定模型lambda和观测O，在时刻t处于状态qi的概率记为 Screen Shot 2018-06-26 at 18.20.06

给定模型lambda和观测O，在时刻t处于状态qi且在时刻t+1处于状态qj的概率记为 Screen Shot 2018-06-26 at 18.21.37

预测算法 p200

近似算法

维特比算法

在每一时刻t选择最可能出现的状态，从而得到一个状态序列

计算简单，但不能保证预测序列整体是最有可能但状态序列

用动态规划求解概率最大路径

从时刻1开始，递推地计算在时刻t状态为i的各条部分路径的最大概率，即为最佳路径。从终结点倒推逐步求得前一结点，组成最优状态序列

很多太小的概率相乘会导致下溢出，结果近似成0。可以通过对乘积取自然对数避免下溢出或浮点数舍入导致对误差

单调性相同所以可以替换 Screen Shot 2018-06-30 at 11.46.08

随机梯度下降

每次仅用一个样本点来更新回归参数，可以在新样本到来时在线增量式地更新模型，因此是一种在线学习算法

将大优化问题分解为多个小优化问题求解，求解时间短很多

目标：求出一系列的alpha和b，再计算权重向量w并得到分隔超平面

原理：每次循环中选择两个alpha进行优化（为了保证约束 Screen Shot 2018-06-30 at 15.24.00 不被打破）。一旦找到一对合适的alpha就增大其中一个并减小另一个。
合适条件为：1）两个alpha都必须在间隔边界之外，2）两个alpha还没有进行过区间化处理或者不在边界上

径向基核函数 机器学习实战p110

Screen Shot 2018-07-02 at 19.48.15

SVM多类分类

A Comparison of Methods for Multiclass Support Vector Machine

最小的训练错误率并不对应最小的支持向量数目

可以牺牲线性核函数的错误率来换取分类速度的提高

每次只优化两个alpha值来加快SVM训练速度，优化参考 Improvements to Platt's SMO Algorithm for SVM Classifier Design

综合多个模型的输出，将弱学习方法提升成强学习方法，选举出的结果准确性更高，
泛化错误率低，易编码，广泛适用于大部分分类器，无需参数调整

对outlier数据敏感

bagging

基于数据随机重抽样

弱分类器数量过多时可能在不好的数据集上出现过度拟合，使错误率升高，在好的数据集上会达到一个稳定值

cost-sensitive learning 机器学习实战p134

通过对TP, TN, FP, FN定义cost，使训练算法倾向于代价较小的模型

线性回归 机器学习实战p140

普通最小二乘法 Ordinary Least Squares 机器学习实战p142

平方误差为 Screen Shot 2018-07-03 at 19.55.41 矩阵写法为 Screen Shot 2018-07-03 at 19.56.03 对w求导得到 Screen Shot 2018-07-03 at 19.56.10 使其等于0解出w为 Screen Shot 2018-07-03 at 19.55.50

只有X存在逆矩阵时才能用，通过det(X.T * X) == 0判断是否存在逆矩阵

局部加权线性回归 机器学习实战p144

给待预测点附近每个点赋予一定的权重 Screen Shot 2018-07-03 at 20.03.11

使用核函数来对附近的点赋予更高的权重 Screen Shot 2018-07-03 at 20.03.34
k过小会overfitting，k过大会underfitting

会增加计算量，对每个点做预测时都必须使用整个数据集

缩减系数来“理解”数据 机器学习实战p150

ridge regression

用于处理特征多于数据样本数的情况，也用于在估计中加入偏差以得到更好的估计

通过lambda来限制所有w之和，能够减少不重要的参数，称该技术为shrinkage

岭回归就是在矩阵 Screen Shot 2018-07-04 at 18.52.14 上加一个lambda*x使矩阵非奇异从而可以对矩阵 Screen Shot 2018-07-04 at 18.53.14 求逆，x为一个mxm的单位矩阵。回归系数的计算变为 Screen Shot 2018-07-04 at 18.54.44

lasso 机器学习实战p152

普通的最小二乘法在约束 Screen Shot 2018-07-04 at 19.14.44下会得到与岭回归一样的公式

lasso的约束变为 Screen Shot 2018-07-04 at 19.15.42

前向逐步回归 机器学习实战p152

贪心算法：每一步都尽可能减少误差（选择对某个权重增加或减少一个很小的值）

算法

对数据高斯分布标准化，在每次迭代中：

  1. 遍历所有特征
  2. 对每个特征增大或减小相应权重（很小的改变量）得到新权重矩阵
  3. 用新的权重矩阵计算预测误差，记录使误差最小的权重矩阵
  4. 收集每次迭代中最优的权重矩阵并返回

降低决策树复杂度来防止过拟合

后剪枝

递归地，如果合并两个叶结点后误差会下降，则合并之

预剪枝

回归树算法中提前停止切分的判断条件即为预剪枝

模型树 机器学习实战p174

把叶结点设置为分段线性函数来代替取均值

预测准确度更高，可解释性强于回归树

R2值比较模型好坏

NumPy.corrcoef(yHat, y, rowvar=0)

越接近1越好

K-means 机器学习实战p188

结果受k的大小及质心初始值影响，很难预先给出最优k和最优质心

后处理：计算误差平方和SSE来度量各点到质心的密集程度，
分割SSE过大的簇，合并距离最近的簇

二分kmeans算法 机器学习实战p194

初始化所有点为同一个簇，将其一分为二（k=2的kmeans分类），
然后选择能更大程度降低SSE的一半继续切分，直到满足给定的k个簇

Apriori物品关联度分析 机器学习实战p204

support

包含该物品的数据占所有数据的百分比

confidence

关联规则A -> B在所有包含A的数据中占的百分比

Apriori

一个频繁物品集合的所有子集都必须是频繁的，因此一旦一个集合被认为不频繁就可以不用计算以该集合为子集的频繁度，从而减少计算量

数据量保持一致，但因为随机抽样可能存在重复或未包含的数据点

一个频繁物品集合有多个可能的关联因果规则A->B，如果一个物品B为结果的confidence太低，任何包含B为结果的规则都confidence太低

FP-growth 机器学习实战p226

只需要扫描两次数据集，1）构建FP树，2）从FP树中挖掘频繁项集

FP树

通过node link链接来连接相似元素
Screen Shot 2018-07-07 at 13.49.14

FP树存储item集的出现频率，子集会共享树的部分路径，当集合间完全不同时才分叉

结点上存储单个item及其在序列中的出现次数

构建过程 机器学习实战p230

第一遍扫描数据集统计各item出现频率，去掉不满足最小support的item

第二遍只扫描频繁item集

  1. 构建一个头指针表来指向每个item类型的第一个元素及存储出现总数
  2. 逐条读取item集，按以下规则将所有item加入FP树中
    2.1 将items按照出现频率从高到低排序，然后逐个如下加入FP树
    2.2 从FP树的根结点（代表空集）开始，如果当前结点的子结点中已经存在该item，对其结点的计数加一
    2.3 否则新建一个子结点并连接到头指针表中该元素对应链表的尾端

查找频繁item集 机器学习实战p234

  1. 抽取条件模式基
  1. 创建条件FP树 ❓
    https://blog.csdn.net/Bone_ACE/article/details/46669699
    https://www.cnblogs.com/pinard/p/6307064.html
    https://www.cnblogs.com/ybjourney/p/4851540.html

对头指针表中的每一个item找到对应的条件模式基conditional pattern base - 以该元素项为结尾的路径集合，即所有可能的前缀路径及其出现数量。
遍历该item在头指针表中的链表，每个链表结点在FP树中的前缀路径即为要找的前缀路径
Screen Shot 2018-07-07 at 14.50.39 Screen Shot 2018-07-07 at 14.42.04

对每一个频繁item创建一个条件FP树

工具

数据降维

Principle Component Analysis 机器学习实战p246

Factor Analysis

Independent Component Analysis

把数据映射到使数据点方差最大的方向，然后找到方差次大的方向，以此类推。各方向之间必须正交
然后只保留方差最大的前几个方向，从而降维

Singular Value Decomposition 机器学习实战p256

从噪声数据中抽取相关特征，将高维数据映射到低维空间

Latent Semantic Analysis

Screen Shot 2018-07-07 at 18.25.05 中间的矩阵只有对角元素有非零值，为奇异值Singular Value，惯例是从大到小排列，在某个数量过后的奇异值都为0，表示对应的数据是噪声或冗余

一般保留奇异值平方和达到90%总和的奇异值

Collaborative Filtering 机器学习实战p260

相似度

欧氏距离

Pearson Correlation

cosine similarity

一般选择基于item的相似度计算，因为user数量可能远大于item数量

用最小均方根误差Root Mean Squared Error衡量推荐算法的误差

cold start问题

缺乏数据时如何给出正确推荐？

proximal SVM ❓

canopy ❓

分布式聚类算法，可以取得初始的k个簇再运行kmeans算法

Pegasos 机器学习实战p290

原始估计梯度求解器 Primal Estimated sub-Gradient Solver

使用随机梯度下降方法来解决SVM所定义的优化问题，迭代次数之取决于用户要求的精度，和数据集大小无关

从训练数据集随机挑选一些样本点加入待处理列表，按序判断分类是否正确。
忽略正确分类的点，将错误分类的样本点加入待更新集合。处理完毕后按照错分样本更新权重向量