Stanford Machine Learning 学习笔记、个人整理
课程相关链接
说明
该课程能学到什么？
基于统计模型，概率公式的不同学习方法，不涉及神经网络。
本文档不按照课的分化记录，而按照内容的分化记录。
省去具体实现，毕竟已经有足够的他人整理的资料，以及我也在pad上手写过了，没有这个重复工作的必要了。不过我会尽量把知识点依赖写清，如果心情不错的话，再提供一个相关的优秀的讲解链接。这里还是以框架和思想为主。其中部分公式省略了取值限制，具体原公式请参照讲义
依赖知识
高等数学
- 积分
- 微分
- 偏导数，梯度
- 拉格朗日乘子法、KKT条件(拉格朗日对偶)
- 牛顿切线
线性代数
- 矩阵 乘法 转置 逆 秩 迹
- SVD
概率统计
- 贝叶斯
- 高斯分布 多纬高斯分布
- 0-1分布 泊松分布 等等常见分布
- 极大似然估计
算法
- 动态规划
内容
监督学习
- 提供样例(输入，输出(类别))数据进行训练，从而学习出一个分类器/学成一个带有功能的程序。
方法
| 名称 | 功能 | 对应的期望 | 实现 | 理解 | 知识依赖 | 课程集数 |
|---|---|---|---|---|---|---|
| 线性回归 | 拟合出一条自变量与因变量的关系直线 | 平方和最小 | 梯度下降 | 局部极值 | 高数梯度 | 2 |
| Normal equations | 极值点梯度=0 | 矩阵运算 对矩阵求梯度 | 2 | |||
| 线性回归(数据量大) | 随机梯度下降 | 2 | ||||
| logistics分类 | 对一侧全0，另一侧全1的训练数据集建立分类器 | 计算对应最优参数的logistics function | 梯度上升 | 概率期望最大 | 极大似然 | 3 |
| softmax回归(logistics 可以看做k=2时的特例) | 分为k类 | 找到对应的拟合函数 并且拟合出参数 | 找拟合函数带入GLM 拟合参数老方法了 | 满足GLM的假设所以可以带入GLM | GLM 和 极大似然 | 4 |
| 高斯判别分析GDA | 在n维多项高斯分布中找一条线分割训练集合 |
计算假设分布中对应参数 | 假设伯努利以及高斯分布运用极大似然算参数值 | 根据测试集带入模型得出的可能性的值来判断所属于的分类 | n维高斯的分布矩阵形式的协方差 极大似然 贝叶斯 生成学习方法 | 5 |
| 朴素贝叶斯 | 直接概率公式计算可能性，如垃圾邮件根据词的出现进行分类 | 能够对含有大量特征与非特征的整体进行分类 | 直接算概率 | 通过可能性来判断是否是 | 贝叶斯 极大似然 生成学习方法 | 5 |
| 神经网络(只是提到没有深入讲) | 非线性分类器 | 对非线性进行分类 | 极大似然，反向传播，梯度下降 | 6 | ||
| 最优边界分类器 | 也就是要找到最大几何间隔的分类器 | 期望在满足约束的情况下，表达式最大 | 在限定条件下的线性规划用对偶的方式求极值 | 期望在满足约束的情况下，使所有点到超平面距离的最小值最大 | 拉格朗日乘子法、KKT条件、拉格朗日对偶性 | 7 |
| 支持向量机SVM | 对非线性可分割的分布进行分割 | 非线性分类器 | 说实话SVM以及SVM所依赖的知识的细节理解得还不够清晰 已经放入下面的TODO | 把训练集转换到高维去，在高纬度中进行线性分割 | 核函数+最优边界分类器+对偶问题 | 6 7 8 |
| L1 norm soft margin SVM | 对于有错误分类 | 让带有惩罚项的表达式期望最小 | 数学推导 | 个别的错误项可以破坏支撑点 但仅仅算做惩罚 | svm 极大似然 | 8 |
| 特征选择 | 例如文本分类 | 选取真正对文本类别有影响的特征 | 通过交叉验证 逐个插入检测对预测值的影响 | 运用实验获得模糊的相关性 | 贝叶斯 | 10 |
辅助方法/定义
| 方法 | 功能 | 章节 |
|---|---|---|
| 牛顿切线法 | 加快求极值点的收敛速度、二次收敛 | 4 |
| GLM广义线性模型 | 对满足广义线性模型下的回归问题进行分析 直接得到所需要的拟合模型 | 4 |
| 拉普拉斯平滑 | 对于 处理例如朴素贝叶斯中可能出现的0/0的概率 分子+1 分母+可分的类别数k | 5 |
| 函数间隔 | 定义，当超平面的参数等比例缩放时超平面不会变但函数间隔会变化 | 6 7 |
| 几何间隔 | 同上，区别是 几何间隔=函数间隔/超平面法向量w的模,也就是当(w,b)等比例变化时，几何间隔不变 表示到超平面的距离 | 6 7 |
| 核函数 | 在最右边界分类器中出现了<X,X> 核函数能够降低计算代价,转换特征，同时选取高纬映射的核函数就够转化为SVM问题 |
7 8 |
| SMO | 每次修正一个参数逐步逼近，如果有等式约束每次修正两个 | 8 |
| VC维 | 配合训练集 概率 错误率建立 误差上下界关系 | 10 |
| 交叉验证等多种验证 | 整体思想是把训练集的部分数据不用于训练而用于检验 进行模型筛选 | 10 |
| 规范化 正则化 | 防止过拟合 | 11 |
| 在线学习 | 边学习边预测 能收敛到分界线 | 11 |
| 检测机器学习算法的问题 | 通过 误差 方差 偏差 收敛性 值函数在更优秀的数据下的表现 综合判断问题所在 | 11 |
证明
| 证明 | 方法 | 课程集数 |
|---|---|---|
| 线性回归中用最小二乘法最好 | 概率分布假设+极大似然 | 3 |
| 线性回归 和 logistics分类对应的 拟合函数 | 按照GLM的方式对应带入 | 4 |
| 过拟合 欠拟合 经验风险的上下界 | hoeffding不等式 同时能够提供定量分析误差 | 9 10 |
无监督学习
- 无样例(输入，输出)样本进行学习，直接根据未分类数据的分布特征，对数据进行分类/建立带有功能的程序。
方法
| 名称 | 功能 | 对应的期望 | 实现 | 理解 | 知识依赖 | 课程集数 |
|---|---|---|---|---|---|---|
| k-means | 对无标记的点进行分类 | 找到分类的中心，使(按照每个分类的中心所得到的分类)的中心都是分类的中心 | 平面随机选中心，以这些点进行分类，对每个分好的类进行重新计算中心，重复直到收敛 | 分类的中心=分类的中心 在概率上可能最大 | 不等式递推 | 12 |
| 最大期望算法EM | 对无标记训练数据根据所假设的模型进行分类 | 在所对应假设的模型下找到最好的参数 | 通过假设隐藏已知中间变量计算中间变量的 | E假设 概率可以看做优化Q，M步在这种情况下的分布带回去看作优化参数，再E再M直到收敛，可以说k-means也有点思路类似，也可以通过图形理解 坐标上升 | 贝叶斯 极大似然 | 12 13 |
| 因子分析模型 | 因子多 分类少，直接对角矩阵会丢失其它维度，用来进行分类 | 对无标示样本分类 | 加入低维隐含变量Z 猜测分布 进行升高维度加上高斯噪声再用EM | 高维数据被分到低纬度的类中 可以反过来进行 映射+噪声的假设 | EM 高斯 矩阵乘法 | 13 14 |
| PCA主成分分析 | 降维投影提取真正关键的维度信息 例如LSI潜在语义索引 | 找多组让数据尽量分散的正交投影法向量 | 线性代数 matlab的SVD进行奇异值分解 | 找低前k个最大的向量 | SVD 线性代数 | 14 15 |
| ICA独立成分分析 | 提取分离独立成分 如音频分离 | 需要分布本身独立 且非高斯 | 数学推导 | 高位的平行四边形 找到轴 并把轴转换到正交轴 | 独立概率+sigmoid+极大似然 | 15 |
辅助方法/定义
| 方法 | 功能 | 课程集数 |
|---|---|---|
| 混合高斯分布GMM | 无标记的空间上有多组服从独立的高斯分布的数据，用于作为EM算法的试例 | 12 |
| Jensen不等式 | 如果f是凸函数 E[f(x)]>=f(EX) | 12 |
强化学习RL/马尔科夫模型MDP
上面的都是分类模型，强化学习要强行分类也可以说是无监督分类，或者半监督分类。
解释
| 名称 | 功能 | 对应的期望 | 实现 | 理解 | 知识依赖 | 课程集数 |
|---|---|---|---|---|---|---|
马尔科夫决策过程MDP(状态S，动作A，{概率P(S,A)},折扣因子r,{奖励函数R(S)}) |
对于给定的模型 能够根据当前状态做出模型下最优决策 如讲师所做的自动驾驶倒飞直升机XD | E(R(S0)+rR(S1)+r^2 *R(S2)+...) |
值迭代/策略迭代 | 值迭代是计算每个S下的期望最大值，再根据得到的期望得到决策；决策迭代是在过程中 决策和值共同更新，计算代价更大 小数据相对快 | 动态规划 期望 | 16 |
马尔科夫决策过程 变形/问题
| ? | ! | 课程集数 |
|---|---|---|
| 未知概率函数P | 用实验所得尽心均值估计 | 16 |
| 对于维度高数量级大的 离散化难解决(数量级大 需要非均匀离散) 状态>=动作 | 通过建造模拟器S(t+1)=S(t)+S'(t)*dt和实验数据进行线性拟合 从而取代P的作用，同时 需要多次多步骤实验 |
17 |
| R(S)变为R(S,A) | 依然用期望就好 | 18 |
| 从无限边界变为有限边界T，去掉折扣因子r，R和决策都还需要依赖时间 | 线性二次调节控制LQR 通过强假设 结束的S(T) A(T),进行反向递推(动规)，根据矩阵运算可以省去 噪音项 | 18 19 |
| 非线性函数 | 采用局部的 值点 | 19 |
| 模拟器不够好+非线性函数 | 局部切线值的点+LRQ ->变为 微分动态规划DDP | 19 |
| 无法获得真实值，只能获得观测值 | Kalman滤波，非指数级别增长 通过概率估计推得可能的真实值/极大似然 | 19 |
| 无法真实值的线性二次调节控制 | LQG=LQR+kalman滤波 | 19 |
| LQG虽然能用但效果不是最佳，目标策略非线性策略 | 策略搜索:随机序列+带参数策略如logistics函数+梯度上升，找所假设的策略函数的最优参数 | 20 |
| 随机的序列 同样输入可能不同的值 拟合较难 | Pegasus 序列依然随机生成，但生成后固定反复使用于训练 | 20 |
Debug 19
| 症状 | 方案 |
|---|---|
| 模拟器可以 真实不行 | 改模拟器 |
| 人比RL好 但值函数人的低 | 改值函数 |
| 没有上述问题 | 改奖励函数 |
一句话能回答的知识点 TODO
梯度下降和梯度上升有什么区别？3
画三维图形，求它的梯度，从图像上看，梯度是指向上方的。所以梯度下降用减法，实际是逼近极小值，而梯度上升用加法，逼近极大值。
欠拟合与过拟合分别是什么？4
欠拟合：模型复杂度不够 训练数据少，未能真正获取主要内在关系，训练数据和测试数据得分都低。过拟合，模型过于复杂，训练数据方差小得分高，但是测试数据偏差大 方差大
判别学习法 和 生成学习方法 的区别？5
判别学习法直接对P(y|x)进行建模；生成学习方法对P(x|y) 和 p(y)进行建模 然后，y = 贝叶斯公式转换后最大的y 例如 隐马尔可夫模型HMM、朴素贝叶斯模型、高斯混合模型GMM、LDA。
GDA与Logistics模型比较？5
GDA按照概率转化的曲线和sigmoid,很相似。GDA更强的假设，对于正确的训练集，GDA效率更高 更好，但对于不正确的模型，logistic的健壮性robust更好
其它知识点 细节 TODO
LGM
对偶问题
核函数定义 证明 应用 具体核(高斯核)
SVM
EM:Do, C. B., & Batzoglou, S. (2008). What is the expectation maximization algorithm?. Nature biotechnology, 26(8), 897.
其它TODO
添加配图
李航的《统计学习方法》刚翻了个开头，这本书先讲的泛的再具体的顺序不同，不过瞄了目录，似乎有新内容还是换了个名字？不懂2333，目前计划是先不看它，去看CSP，之后再看_(:з」∠)_。
老师建议把 证明过程盖住 自己再证明
2讲矩阵梯度公式