前言

这是高级机器学习的课程笔记，推荐读物是:

周志华. 机器学习(西瓜书).
Peter Harrington. Machine Learning in Action (机器学习实战).

绪论

基本术语:

数据集dataset: 一组对象记录，每一条一个称为示例instance/样本sample
属性attribute/特征feature: 对象某方面的性质xi
属性值value: 性质的量化取值xi = vi
属性/样本/输入空间: 属性值的合法取值空间
特征向量featvec: 一个样本的所有特征因此可以组成样本空间空间里的一个向量
维数: 每个对象的特征数量
标记label: 样本的定性/定量判断结果，yi
标记/输出空间: 标记的合法取值空间
*因此每个样本通常形如(X, y)，X是对象的特征向量，y是其标记
分类classification: 预测值是离散值
回归regression: 预测值是连续值
泛化能力generalization: 模型对未训练数据也适用/表现良好
归纳偏置: 机器学习算法在学习过程中对某些假设的偏好/坚持(即合理的选项有很多，却最终不得不选一个、按偏好选择)

No Free Lunch/NFL定理: 所有机器学习算法的期望性能(误差)是一样的，假设所有问题等概率出现(但应用上、真实数据的形态并不是平坦的)

人工智能历程:

推理期: “逻辑理论家”、”通用问题求解”程序
知识期: 知识工程(抽取/表示)
学习期
- 联结主义connectionism: 感知机、神经网络/深度学习
- 符号主义symbolism: 结构学习、归纳学习、概念学习、统计学习/核方法
- 行为主义: 强化学习

模型评估与选择

基本概念:

错误率: E = α/m，其中m个样本中有α个分类错误；准确率/精度即1 - α/m
误差: 预测值与真实值的差异，在训练集上的误差叫训练误差/经验误差、新样本上的误差叫泛化误差
泛化能力: 越强，泛化误差越小
过拟合/欠拟合: 泛化能力因为模型过于精细/粗糙而降低；只要P != NP则过拟合不可避免

评估方法:

留出leave-out: 将数据集D划分为互斥的训练集S和测试集T，在S上训练、在T上评估泛化误差；注意两个集合数据分布要基本一致、分层采样
交叉验证cross-validation: 将数据集D划分为互斥的k个数据分布一致的子集Dk，然后重复k次每次将其中一份作测试集、其余做训练集，最终评估均值
自助法bootstrapping(小数据集): 从数据集D中有放回地抽取m个做训练集D'、余下的做测试集(可计算得数据集D中有占比约1/e的部分不出现在训练集D'中)；但该方法改变了数据分布
调参: 网格化搜索最优结果的模型参数

性能度量:

错误率: E(f;D) = Σi[m](f(xi)!=yi) / m
精度: acc(f;D) = 1 - E(f;D)
查准率precision: P = TP / (TP + FP)，正确正例对正例的占比；查准率低意味着模型误判太多，不可信
查全率recall: R = TP / (TP + FN)，正确正例对正确判断的占比；查全率低意味着正例不足，我们对A是什么仍然一无所知(只知道A不是什么)
平衡点break-even point/BEP: P-R图上P = R的点(曲线越方越好)
F1值: F1 = ((1 + β^2) * P * R / (β^2 * P + R))，平衡因子β>1时查全率重要、β<1时查准率重要
受试者工作特征ROC: 正判正率TPR = TP / (TP + FN), 误判正率FPR = FP / (TN + FP)，画TPR-FPR曲线、图形面积衡量质量
代价敏感错误率: 在混淆矩阵上加权、随后类似地计算查准P/查全R

线性模型

线性模型认为对象的标签是其特征向量各个分量的线性函数: f(X) = Σi[d](wi*xi) + b，或向量写法f(x) = w'*x + b，要训练的参数即w'/wi和b、使得f(xi) ~= yi
最小二乘法/优化均方误差: (w*, b*) = argmax[w,b] Σi[m](f(xi)-yi)^2

回归模型
- 线性回归: 建模认为y = w'x + b
- 对数回归: 建模认为ln(y) = w'x + b
- 广义线性回归模型: 建模认为g(y) = w'x + b，其中g单调可微
分类模型
- 对数几率回归logistic regression/LR: 建模认为ln(y/(1-y)) = w'x + b，由于二分类标签y取值范围为{0,1}，ln(y/(1-y))解释为该对象是正例相对于它是负例的几率(odds)的对数值，得到的预测值y是其属于正例的几率
- 线性判别法linear discriminant analysis/LDA: 将训练集投影到一条直线上，使得正例负例的投影点相对集中于各自的中心点、而两个中心相对较远
- *多分类: 拆分成若干个二分类，拆分方案有一对一OvO、一对其余OvR、多对多MvM
- *类别不平衡问题: 训练数据中每个类别的记录数不平衡，使用相对值、比较训练集中正负比例，若y/(1-y) > m+/m-则认为是正例

决策树

决策树模型反复考虑每个属性并划分条件，将一个级联的蕴含式作为分类规则(cond1->cond2->cond3->…->res)，因此分类边界必定是折线
划分选择: 希望不断划分后每个子树的叶子尽可能属于同一类别，即纯度越来越高
信息熵: 离散聚集D的熵Ent(D) = -Σi[k]p(i)*log2(p(i))，p(i)表示i号元素的数量占比，熵越小纯度越高
信息增益: 若属性α有V种取值，则Gain(D,α) = Ent(D) - Σv[V](Ent(Dv)*|Dv|/|D|)，增益越大纯度提升越大

优化目标:

ID3: α* = argmax[α](Gain(D,α))，最大增益
C4.5: α* = argmax[α](Gain(D,α)/IV(α)), IV(α) = -Σv[V](|Dv|/|D|)*log2(|Dv|/|D|)，最大增益率(会偏好取值数目少的属性)
Gini指数: Gini(D)反映从D种随机抽取两个样本、其标记不一致的概率，Gini越小越纯

一些处理技巧:

过拟合:
- 预减枝: 用训练集划分子树、随即用测试集考察该划分是否能提高精度
- 后剪枝: 先完全建好树，然后从叶子节点开始考察合并是否能带来测试集上的精度提升
连续值: 离散化、二值均化
缺失值: 对于有缺失值的分叉，每个子树分配一个概率(根节点概率为1)，概率大小反比于某种意义上的数据缺失率

神经网络

神经元模型: 输入是向量X、输出是标称值y、自己拥有一个阈值b；操作是先对X做聚合g、再用f决定是否激活，即y = f(g(xi),b)，通常取g为加权和、取f为阶跃，即有线性模型y = (Σi(wi*xi) - b) > 0，参数为wi和b
线性可分问题: 存在一个(d-1)维超平面可以完美分隔d维空间里的给定数据点
感知机: 两层神经元模型
*隐层神经元个数?: 试错法、调参
神经网络: 更多层神经元模型
多层前馈神经网络: 没有同层连接、没有跨层连接、相邻两层全连接
误差逆传播算法BP: 基于可微函数、符号计算、链式法则、梯度下降

经常会过拟合: 早停止、正则化
局部最优: 多次随机选择初始点、模拟退火

常见神经网络形态:

径向基函数网络RBF
自适应谐振理论网络ART
自组织映射网络SOM
级联相关网络
Elman网络(递归神经网络之一)
Boltzmann机(基于能量的模型)

支持向量机

线性模型中用于分割正负例的超平面可以有一定自由度，选择”中间位置”的超平面做最终模型
边界:

正例边界: w'x + b = +1
负例边界: w'x + b = -1
最终模型超平面: w'x + b = 0
支持向量: 距离超平面最近的几个正负例样本点
间隔margin: 两个异类支持向量到超平面的距离之和，即γ = 2 / |w|
优化目标：min[w,b] |w|^2, st. yi(w'xi+b) ≥ 1

数据集并非完全线性可分的时候:

软间隔: 允许正负例边界存在一定的交叉
核方法: 若原始空间是有限维，则必能映射到一个高维空间使其线性可分
- 线性核: xi' * xj
- 多项式核: (xi' * xj)^d
- 高斯核: exp(-|xi-xj|^2 / (2σ^2))
- 拉普拉斯核: exp(-|xi-xj| / σ)

支持向量回归: 拟合f(x) = w'x + b，然后取上下宽ε的带状区域f(x) ± ε认为都是目标函数，因此仅对落出的点计算loss、优化error；预测时仍然返回f(xi)即可

贝叶斯分类器

贝叶斯决策论：

给定N个类别，令λij代表将第j类样本误分类为第i类所产生的损失，则基于后验概率将样本x分到第i类的条件风险为：R(ci|x) = Σj[N] λij*P(cj|x)
贝叶斯判定准则：h*(x) = argmin[c∈Y] R(c|x)
h*称为贝叶斯最优分类器，其总体风险称为贝叶斯风险
反映了学习性能的理论上限

集成学习

聚类

降维与度量学习

引入: kNN算法简单粗暴，但其分类器泛化错误率不超过贝叶斯最优分类器错误率的两倍
但这基于一个假设，即任意测试样本的任意足够小邻域内都能找到另一个样本，但现实问题中备选特征的维度通常很大，若要满足此密采样则训练数据量根本不够，因此必须特征降维、过滤无用特征
低维嵌入: 原始高维空间坍缩掉一些维度得到低维空间、寻找流形

多维缩放算法MDS:

要求原始空间样本之间得距离得到保持，特别地，新空间中的欧式距离等于原距离||z1-zj||2 = dist[i][j] (原距离定义是任意的)
考察降维后样本的内积矩阵B = Z'Z, 其中b(i,j) = zi'zj
对B进行特征值分解，取特征值最大的d'个组成对角阵λ、对应的特征向量组成V
输出V*λ^(1/2)，每一行是一个样本在d'维的低维空间里的坐标

主成分分析PCA:

最近重构性: 样本点到超平面的距离足够近，最大可分性: 样本点在超平面上的投影尽可能分开
- 优化目标: max[W](tr(W'XX'W)) st. W'W = I
对数据进行中心化: xi = xi - mean(x)
计算样本属性的协方差矩阵XX’，对其特征值分解
取最大的d'个特征值所对应的特征向量w1,w2,..,wd'
得到投影矩阵W* = (w1, w2, .., wd')
每个样例的乘上投影矩阵即得低维空间里的对应向量

非线性降维:

核化线性降维: KPCA, KLDA
流形学习: 测地线距离(保距)
- ISOMAP
  1. 构造近邻图
  2. 基于最短路求/近似任意两点间测地线距离
  3. 基于距离矩阵通过MDS获得低维嵌入
- LLE

距离度量学习: 学出一个半正定对称距离矩阵M

NCA
LMNN

特征选择与稀疏学习

特征选择: 滤去无关特征、顺便降维

子集搜索

前向搜索: 从空集开始逐渐加入特征
后向搜索: 从全集开始逐渐删特征
双向搜索: 混合上述二者

子集评价

特征子集A确定了对数据集D的一个划分
- A上的取值(组合)将数据集D划分成V份，每一份记作Dv
- Ent(Dv)为子集Dv的信息熵
样本标记Y对应了数据集D的真实划分
- Ent(D)表示D上的信息熵
特征子集A的信息增益越大越好
- Gain(A) = Ent(D) - Σv[V](Ent(Dv)*|Dv|/|D|)

选择方式

过滤式: 特征选择与后续训练无关而串联
- Relief方法: 特征加权以度量重要性，对特征j对每个样本xi寻找其同类的猜中近邻和异类的猜错近邻、计算这两个距离dist_h和dist_m(dist_h越小越好、dist_m越大越好)，则特征j的权为δj = Σi(-dist_h(xi)^2 + dist_m(xi)^2)
包裹式: 以训练结果的评估作为特征选择的评估、因此需要多次训练反馈
- LasVegasWrapper/LVW方法: 随机选一个特征子集、训练评估，反复多次后取评估最优的最小特征子集
嵌入式: 融入学习训练过程，在同一个优化过程内自动完成特征选择
- 考虑简单线性模型，以平方误差为损失，引入一个正则化项防止过拟合
  - 岭回归: min[w]Σi[m](yi-w'*xi)^2 + λ*|w|2^2，此处|w|2即w的L2范数(欧几里得距离)
  - LASSO: min[w]Σi[m](yi-w'*xi)^2 + λ*|w|1，替换为L1范数(曼哈顿距离)能获得更多稀疏解(但若误差等值线在与坐标轴相交前就与L1范数等值线相交、则得不到稀疏解)
  - 稀疏化: min[w]Σi[m](yi-w'*xi)^2 + λ*|w|0，但L0范数(向量中非零元素的个数)不连续、非凸、且是NP问题因此不好用
  - *由于w是模型参数，使得w稀疏即可限制模型复杂度、防止过拟合
  - *加入L1范数即在原目标函数中增加约束条件|w|1 ≤ C、C为某常数，岭回归同理
- 工作流程: 选取使L1范数最小化的参数λ -> 调用PGD等训练算法 -> 获取模型稀疏系数w -> 在测试集上预测输出 -> 预测输出 + 输出中非零系数即选择的特征集

稀疏表示与字典学习: 为普通稠密表达的稀疏数据样本找到合适的字典，将样本转化为基于该字典的稀疏表示，从而可以比如提升SVM性能

压缩感知: 能否利用部分数据恢复全部数据？——只要数据内部确实高度相关、直接抓住正确的生成式模型即可。
若A满足k限定等距性，则可近乎完美地从y中恢复出稀疏信号s，进而恢复出x
应用: 矩阵补全(将非缺失项数据作为部分信号，利用压缩感知的思想恢复出完整信号)

计算学习理论

概念(concept): 是从样本空间X到标记空间Y的映射, 它决定示例x的真实标记y

目标概念: 对任何样例(x,y)均有c(x) = y成⽴，则c为目标概念(实际上就是一个可能模型)
概念类: 一组目标概念的集合C(一组可用的可能模型)
假设空间(hypothesis space): 给定学习算法L它所考虑的所有可能概念集合H(通常H != C)
可分性
- 可分/一致的: 若存在目标概念c∈H，称该问题对学习算法L是可分的
- 不可分/不一致的: 若否

概率近似正确(Probably Approximately Correct)

PAC识别Identify: 若对0 < ε,δ < 1, 任意c∈C和分布D，存在学习算法L, 其输出的h∈H，满足P(E(h) ≤ ε) ≥ 1-δ，则称学习算法L能从假设空间H中PAC辨识概念类C
PAC可学习: 若存在学习算法L在多项式时间poly(1/ε,1/δ,size(x),size(c))内PAC识别概念类C，则概念类C是PAC可学习的
- 样本复杂度: 满足PAC学习算法L所需的m ≥ poly(.)的最小m称为样本复杂度
- 假设空间复杂性
  - 有限假设空间
  - ⽆无限假设空间: VC维
  - ⽆无限假设空间: Rademacher复杂度

VC维:

增⻓长函数(growth function): ΠH(m) = max |{h(xi),...|h∈H}|，即假设空间里的所有h对m个样例所能做出最多分类的分类数；反映出假设空间的复杂度
对分(dichotomy): 对二分类问题而言，H中的假设h对D中样例赋予标记的每种可能结果称为对D的一种对分
打散(shattering): 若假设空间H能实现在样例集D上的所有对分，即ΠH(m) = 2^m，则称样例集D能被假设空间H打散
VC维: 假设空间H的VC维是能被H打散的最⼤示例集的⼤小，即VC(H) = max{m | ΠH(m) = 2^m}
- *n维实空间的VC维是n+1
- *任何VC维有限的假设空间H都是不可知PAC可学习的

稳定性: 经验⻛险最小化(Empirical Risk Minimization)原则

半监督学习

主动学习active learning: 先根据少量已标记样本训练一个小模型，随后即可对无标记样本作预测，若拿不准(置信度低)就去问专家得到正解，后加入训练集重新训练得到更新模型；目标是尽可能减少专家查询次数

未标记样本分布假设: 聚类假设、流形假设

半监督学习分类:

纯半监督学习pure: 假定训练数据中未标记样本不一定是待预测数据(基于开放世界假设)
直推学习transductive: 假定未标记样本恰好就是待预测数据(基于封闭世界假设)

生成式方法: 假设数据(无论有没有标记)都是同一个潜在模型生成出来的(这模型是什么得靠采样估计去猜)，从而可以将无标记数据视作模型的参数缺失、从而基于EM算法进行极大似然估计求解参数

半监督SVM/S3VM:

基本假设: 低密度分隔，即穿过低密度数据区域得划分超平面
直推支持向量机TSVM算法
1. 用已标记数据训练一个小模型SVMl
2. 用SVMl预测所有未标记数据，得到伪标记
3. 全部数据当作已标记数据，训练大模型SVM找到超平面
4. 交换两个异类的、可能预测错误的点的伪标记，不断重新训练以调整超平面
5. 重复步骤4直到满足某个给定折中参数条件

图半监督学习: 给定数据集将其映射为一个图，每个样本为一个节点、相关度很高的样本间存在一条边(边权正比于相关性)，随后将有标记样本对应节点染色，于是半监督学习过程即染色在图上的扩散

基于分歧的方法: 数据有多个视图，可以互补兼容协同训练(类似于多语翻译过程)

半监督聚类:

约束k均值: 当已知某些点必须同簇或者不必同簇时
约束种子k均值: 当已知少量有标记样本时，直接作为聚类中心

概率图模型

概率模型:

生成式: 对联合分布P(Y,R,O)进行建模
判别式: 对条件分布P(Y,R|O)进行建模
*符号约定: Y为预测变量集合，O为可观测变量集合，R为其他变量集合

概率图模型:

用图来表达变量相关关系的概率模型
- 节点: 随机变量(集合)，亦即特征集
- 边: 变量间依赖关系
分类
- 有向无环图: 贝叶斯网
- 无向图: 马尔可夫网

隐马尔可夫模型HMM/动态贝叶斯网:

组成
- 隐状态变量序列Y = [y1,y2,...,yn]，状态常量集S = {s1,s2,...}
- 观测变量序列X = [x1,x2,...,xm]，观测常量集O = {o1,o2,...}
一步状态依赖假设: 时刻t的状态yi仅依赖t-1时的状态，即下一时刻状态只依赖当前状态
- 联合概率: P([y1];[xm]) = P(y1)P(x1|y1)*Πi[2,n]P(yi|y[i-1])P(xi|yi)
参数λ = (π,A,B)决定了一个HMM模型
- 初始状态概率π: 向量π=(π1,π2,...,πn), πi=P(y1=si)，若未给出则一般认为是均匀分布
- 状态转移概率A: 矩阵A_nn[i][j] = P(y(t+1)=sj|yt=si)
- 状态输出观测概率B: 矩阵B_nm[i][j] = P(xt=oj|yt=si)
生成观察序列的每步密度: x1=Bπ, x2=BAπ, x3=B(A^2)π, ..., xn=B(A^(n-1))π
HMM的基本问题: 对于给定模型λ和观察序列X
- 评估模型和观测序列之间的匹配程度: 即有效计算P(X|λ)
- 根据观测序列推测隐状态序列Y
- 参数学习: 如何调整λ以使得该序列X出现P(X|λ)的概率最大
- *应用: 预测(根据以往观测值预测下一步最有可能的观测值)、语音识别(根据观测语音信号序列预测最有可能对应的文字序列)

马尔可夫随机场MRF:

使用图模型表示，外加一组定义在变量子集上的非负实函数称势函数(“因子”)、用于定义概率分布函数
使用基于极大团(max-clique)的势函数
- 每个节点/变量至少出现在一个极大团中
- 多个变量之间的连续分布可基于团分解为多个因子的乘积，每个因
  子只与一个团相关
- 对于n个变量x={x1,x2,...,xn}，所有极大团构成的集合为C、每个团q所含变量(即节点)的集合记为xq，则联合概率定义为: P(x) = Πq[C](ψq(xq)) / Z，其中ψq是团q的势函数/因子、Z为很难精确计算的概率规范化因子

[马尔可夫随机场MRF-实例]
图模型: 
  x1 - x3 - x5
    \     / |
       x2 - x6
       |
       x4
则联合概率分布建模为: 
  P(x) = (ψ12 * ψ13 * ψ35 * ψ256 * ψ24) / Z
  *其中ψ12即ψ12(x1,x2)，其他可类比

分离集: 
  若从结点集A(不必是团)中的结点到B中的结点都必须经过结点集C中的结点
  则称结点集A、B被结点集C分离，称C为分离集
全局马尔可夫性(global Markov property): 
  在给定分离集的条件下，两个变量子集条件独立
  若令A,B,C对应的变量集分别为xa,xb,xc, 则xa和xb在xc给定的条件下独立，记为 xa⊥xb | xc
  可验证 P(xa,xb|xc) = P(xa|xc) * P(xb|xc)
则图模型可以简化，每个独立结点集作为一个超节点，重新建模联合概率分布

条件随机场CRF:

判别式无向图模型(可看作给定观测值的MRF)，对多个变量给定相应观测值后的条件概率进行建模
- 令x = [x1,x2,..,xn]为观测序列，y = [y1,y2,..,yn]为对应的标记序列
- 目标是构建条件概率模型P(y|x)
- *标记变量yi也可以是结构型变量，只要它的各个分量之间有某种相关性
链式条件随机场cs-CRF
- 条件概率建模为P(y|x) = exp(ΣjΣi[n-1]λj*tj(y(i+1),yi,x,i) + ΣkΣi[n](μk*sk(yi,x,i))) / Z
  - tj(y(i+1),yi,x,i)定义在观测序列的两个相邻标记位置上的转移特征函数，刻画相邻标记变量之间的
    相关关系、以及观测序列对它们的影响
  - sk(yi,x,i)定义在观测序列标记位置i上状态特征函数，刻画观测序列对标记变量的影响
  - λj和μk为参数、Z为规范化因子

模型推断: 基于概率图模型定义的分布，能对目标变量的边际分布或某些可观测变量为条件的条件分布进行推断

精确推断
- 变量消去(见下例)
近似推断
- 随机化方法: MCMC采样(构造平稳分布为p的马尔可夫链来产生样本)
  - Metropolis-Hastings: 基于”拒绝采样”来逼近平稳分布
  - Gibbs-sampling
- 确定性方法: 变分推断
  - 使用EM算法最大化对数似然……

[精确推断-实例]
贝叶斯网络结构: 
  x1 -> x2 -> x3 -> x4
               \--> x5
计算边缘概率p(x5): 
  p(x5) = Σx4Σx3Σx2Σx1 p(x1,x2,x3,x4,x5)                        // 想办法消去x1,x2,x3,x4
        = Σx4Σx3Σx2Σx1 p(x1)p(x2|x1)p(x3|x2)p(x4|x3)p(x5|x3)    // 根据图模型依赖得到，但这个p(x4|x3)是不是应该是p(x3|x4)啊
        = Σx3 p(x5|x3) Σx4 p(x4|x3) Σx2 p(x3|x2) Σx1 p(x1)p(x2|x1) // 按x1,x2,x4,x3的顺序求和
        = Σx3 p(x5|x3) Σx4 p(x4|x3) Σx2 p(x3|x2) m2(x2)   // 对x1边缘求和消去，剩下关于x2的函数
        = Σx3 p(x5|x3) Σx4 p(x4|x3) m3(x3)
        = Σx3 p(x5|x3) m3(x3) Σx4 p(x4|x3)   // 无关变量移出，为什么？
        = Σx3 p(x5|x3) m3(x3) m3'(x3)        // m3'是另一个关于x3的函数
        = m5(x5)                             // 最终剩下仅关于x5的函数

信念传播: 将变量消去求和过程视作消息传播
消息传播过程: 
  x1 -[m12(x2)]-> x2 -[m23(x3)]-> x3 <-[m43(x3)]- x4    // 注意x4到x3箭头方向
                                    \-[m35(x5)]-> x5
两步即可完成所有变量上的边际分布计算: 
  1. 指定一个根节点，从所有叶节点开始向根节点传递消息、直到根节点收到所有叶节点的消息
  2. 从根节点向叶节点传递回复，直到所有叶节点都收到回复    
  3. *基于每条边上相反的两则信息即可算出节点边际分布、这正比于它所接收消息的乘积(有点像一轮PageRank?)

话题模型:

非监督生成式有向图模型
典型代表: 隐狄里克雷分配模型(Latent Dirichlet Allocation/LDA)
基本单元
- 词word: 待处理数据中基本离散单元(语词/图元/音节/…)
- 文档document: 待处理数据集，能表示为词袋模型BoW即可
- 话题topic: 一些概念，亦即一组相关的词、及它们在该概念下出现的概率(有点像tag/category、组成一个滤波器)

规则学习

规则: if p then q, q <- p

序贯覆盖:

问题: 正负例散点图上，用矩形覆盖所有正例、形成正例规则
策略: 特化(逐步增加约束)、泛化(逐步去除约束)
- 规则评判(增删哪个条件): 准确率、信息增益、Gini系数
- 规避局部最优: 集束搜索(每次保留最优的多个候选规则)

剪枝优化:

预剪枝: 似然率统计量LRS
后剪枝: 减错剪枝REP(穷举所有可能的剪枝操作、用验证集反复剪枝直到准确率无法提高)
二者结合:
- IREP
- IREP*
- RIPPER(将所有规则放在一起优化，通过全局考虑来缓解局部最优)
  1. 用IREP*生成规则集
  2. 选取一条规则，找到其覆盖的样例，特化原规则再泛化、重新生成规则
  3. 把原规则和新规则分别置入规则集进行评价，留下较好的

一阶规则学习: FOIL

归纳逻辑程序设计

目标: 完备地学习一阶规则（Horn子句）
方法: 以序贯覆盖方法学习规则集、一般采用自底向上策略学习单条规则
最小一般泛化(LGG)
- 最小: 变换时对原规则的改动尽可能小
- 一般: 覆盖率尽可能高
- 泛化: 将覆盖率低的规则变换为覆盖率高的规则
- *寻找两条规则LGG的步骤
  1. 找出两条规则中涉及相同谓词的文字，即相同的谓词函数
  2. 考察谓词的参数，取实参的并集抽象出一个变量；递归此过程
  3. 删除没有相同谓词出现的文字，即保留共有的谓词函数项(合一操作)

强化学习

图示: 
         -(动作a)->
  |机器|             |环境|
      <-(状态x/奖赏r)-
要素: <A, X, R, P>
  A   动作空间
  X   状态空间
  R   奖励函数，X × A × X -> R
  P   转移函数，X × A × X -> R
策略: 
  a = π(x)
  P(a|x) = π(x,a), st. Σa[A]π(x,a) = 1, ∀a∈A π(x,a) ≥ 0
  *策略的表格/列表表示: [(state, action, probility), ...]
策略评价: 累积回报
  T-step: 1/T * Σt[T](rt)
  discounted: Σt(γ^t * rt)
学习⽬标: 寻找最⼤回报策略，即在每个状态以多大概率做出每个行为

马尔可夫过程<X,P>
  无记忆性: P(x(t+1)|xt,...,x0) = P(x(t+1)|xt)
  稳态分布: lim(t->∞) P(x(t+1)) = P(xt)
马尔可夫回报过程MRP<X,R,P>
  (这tm是个啥玩意儿)
马尔可夫决策过程MDP<A,X,R,P>
  (这tm又是个啥玩意儿)

Q-function: (Vπ和Qπ是整体符号，π是上标)
  状态值函数: Vπ(x) = E[Σt[T]rt|x]
  状态制作值函数: Qπ(x,a) = E[Σt[T]rt|x,a] = Σx'[X] P(x'|x,a)(R(x,a,x') + Vπ(x'))
  两者关系: Vπ(x) = Σa[A] π(a|x) * Qπ(x,a)

唔，这章基本完全不懂

虚仮威し全てを。

——若し雨が降ったら

高级机器学习-笔记

前言

绪论