DP方法简介

• 由于其大量的计算损耗，已经不实用，但理论上非常重要。
• 本书后续的所有方法可以看做想要取得和DP类似的效果；只不过是减少了计算或者假设没有完美的环境模型。
• 假设解决的问题是有限的MDP，即给定动作a，状态s，和奖励r，可以通过\(p(s',r|s,a)\)描述动态变化。

笔记摘要

• 在PAC（概率近似正确(PAC, Probably approximately correct)）学习框架下，一个概念是强可学习的充分必要条件是这个概念是弱可学习的。
• 提升方法的两个问题

1. 在每一轮如何改变训练数据的权值或概率分布
2. 如何将弱分类器组合成一个强分类器

• Adaboost的解决方案：

3. 提高那些被前一轮弱分类器错误分类样本的权值，降低那些被正确分类的样本的权值
4. 加权多数表决的方法，加大分类误差率小的弱分类器的权值，减小分类误差率大的弱分类器的权值

笔记摘要

• SVM的基本模型是定义在特征空间上的间隔最大的线性分类器
• 线性可分支持向量机和线性支持向量机假设输入空间和特征空间的元素一一对应，并将输入空间中的输入映射为特征空间的特征向量；非线性支持向量机利用一个从输入空间到特征空间的非线性映射将输入映射为特征向量
• 支持向量机的学习策略就是间隔最大化，可形式化为一个求解凸二次规划的问题，也等价于正则化的合页损失函数最小化问题
• 仿射变换是保凸变换
• 通过使用核函数可以学习非线性支持向量机，等价于隐式地在高维的特征空间中学习线性支持向量机

• logistic regression是统计学习中的经典分类方法。最大熵是概率模型学习的一个准则，推广到分类问题得到最大熵模型(maxium entropy model)
• 这两种模型都属于对数线性模型

笔记摘要

• 决策树可以认为是if-then规则的集合，也可以认为是定义在特征空间上的条件概率分布
• 根据损失函数最小化的原则建立决策树模型
• 决策树的路径或其对应的if-then规则集合具有一个重要性质：互斥且完备
• 决策树的学习算法包含特征选择、决策树的生成与决策树的剪枝
• 决策树的生成对应于模型的局部选择，决策树的剪枝对应于模型的全局选择

Agent和Environment的交互

• 学习者和决策者称为agent。
• agent交互的对象，外部环境，称为Environment。
• 在时刻t，agent的所处的环境用状态：\(S_t \in S\)表示，\(S\)是可能的状态集。假设agent采用了动作\(A_t\in A(S_t)\)，\(A(S_t)\)代表在状态\(S_t\)下可能的动作集。
• 到了下一个时刻t+1，agent收到了一个奖励：\(R_{t+1} \in R\)，并且发现自己处在一个新的state中：\(S_{t+1}\)。

k-armed Bandit Problem，K臂老虎机

问题描述：重复面临有k种选择的情况，每一次选择之后，都会收到一个reward。这个reward服从一个跟你的选择相关的分布。你的目标是，在选择t次后，找到最大的期望reward。

为什么叫K臂老虎机：有K个单臂老虎机，每个时间节点，你可以选择K个中任意一个老虎机选择按下它的臂，然后获得一个奖励。目标自然是多次选择之后的累计奖励最大。

笔记摘要

• 条件概率分布\(P(X=x|Y=c_k)\)有指数级数量的参数，其实际估计是不可行的

• 指数级数量的参数 \(K\prod_{j=1}^nS_j\)，实际估计不可行是实际上没有那么多样本

• 朴素贝叶斯法是基于贝叶斯定理与特征条件独立假设的分类方法

学习笔记

• k值的选择、距离度量及分类决策规则是k近邻法的三要素
• 三要素在算法之中完整体现出来：

在CRF系列的前两篇，我们总结了CRF的模型基础与第一个问题的求解方法，本文我们关注于linear-CRF的第二个问题与第三个问题的求解。第二个问题是模型参数学习的问题，第三个问题是维特比算法解码的问题。