Motivation
Details
Example
Implementation
Properties
NBC有坚实的数学基础，稳定的分类效率，超参数少（先验），对缺失数据不敏感，算法简单。
如果属性较多且相关性比较大，决策树优于NBC，否则NBC性能很好。
垃圾邮件分类器
事先做一个vocabulary存放常用的单词，如果邮件中包含vocabulary的第j个单词，特征向量中\(x_j=1\)
朴素贝叶斯假设给定标签前提下各个属性是独立的（条件独立）： \(P(x_1,...,x_d|y)=P(x_1|y)P(x_2|y,x_1)...P(x_d|y,x_1,...,x_{d-1})=P(x_1|y)P(x_2|y)...P(x_d|y)\)
\(P(x_2|y,x_1)\)表示在\((y,x_1)\)的条件下\(x_2\)发生的概率
\(P(junk|D)=\frac{P(junk)P(D|junk)}{P(D)},P(normal|D)=\frac{P(normal)P(D|normal)}{P(D)}\)
P(junk)/P(normal)根据邮件库的比例即可
P(D|junk)=P(word1,word2,...,wordn|junk)，联合概率分布的数据是稀疏的，在垃圾邮件集合中出现与当前邮件相同的邮件概率。
P(word1|junk)P(word2|word1,junk)P(word3|word2,word1,junk)...
如果条件独立假设成立，
P(word1|junk)P(word2|junk)P(word3|junk)...只要统计垃圾邮件中每个单词的频率
拼写纠正
max P(猜测用户希望输入的单词|实际输入单词) \(P(h_1|D),P(h_2|D)\)
\(P(h|D)\propto P(h)P(D|h)\)
对给定的观测数据，一个猜测的好坏正比于先验和这个猜测生成观测数据的可能性大小（似然）
假设实际输入D=thew,h1=the,h2=thaw
\(P(h_1|D)=\)the本身在词典中的出现概率及输入the前提下输thew的可能
ID3（Iterative Dichotomiser 3）迭代二叉树3代，启发式算法
以信息增益做属性选择，选择分裂后信息增益最大的属性进行分裂
- top-down贪心遍历可能的决策树空间
- 核心问题在于如何选择划分属性
- 按照信息增益选择分类能力最好的属性
- 属性的每个值产生一个分支，将训练数据放在合适的分支，不回溯考虑之前的选择
都知道熵用来衡量随机变量的不确定性，在这里就是刻画数据集的不纯度
条件熵是指在某个条件下，随机变量的不确定性
信息增益即熵-条件熵，即某条件下信息不确定性减少的程度
举例来看：明天下雨的熵为2，阴天条件下下雨的熵是0.01（即阴天下雨的可能性很大，所以不确定性很小），信息增益=2-0.01=1.99，获知阴天后，下雨的不确定性减少了很多，信息增益很大，所以阴天对下雨这一推断很重要，意味着这个特征很关键。
IG衡量给定属性区分训练样例的能力
\(Entropy(S)=\sum_{i=1}^{c}-p_ilog_2p_i\)，c表示该属性有c个取值，Pi表示子集中样例占总数的比例。介于[0,1]之间，所有样例属于1类，最纯，熵为0；平分熵最大为1
一个属性的IG意味着用该属性分割样例导致的熵减的期望，
\(IG(S,A)=E(S)-\sum_{i=1}^{c}\frac{|S_i|}{|S|}E(S_i)\)
C4.5用信息增益率作为属性选择的依据，构造过程中会进行剪枝（不考虑只有几个元素的结点，避免过拟合）
率即用相对性衡量（10经过10s到20，1经过1s到2，虽然前者的增益大，但如果用速度增加率即加速度衡量是一样的）
可以处理非离散数据和不完整数据
当前数据集S，当前属性A有c个取值，S需要被分割为c个子集 \(GainRatio(S,A)=\frac{IG(S,A)}{SplitInfo(S,A)}\)
\(SplitInfo(S,A)=-\sum_{i=1}^{c}\frac{|S_i|}{|S|}log_2\frac{|S_i|}{|S|}\)
如果A能完全分割，那么splitinfo=0；如果对半分，那么=1，即splitinfo阻碍选择值均匀分布的属性
如果splitinfo=0，可以先计算每个属性的信息增益，选择增益>平均值的属性再去应用增益比率，因为如果splitinfo=0，即A能完全分割，意味着信息增益=0，不可能>平均值
实际中决策树的过拟合是比较严重的，C4.5克服了ID3用IG选择属性时倾向选择取值多的属性的不足。
马尔可夫随机过程：
s1：名词
s2：动词
s3：形容词
转移矩阵A=0.3 0.5 0.2;0.5 0.3 0.2;0.4 0.2
0.4即A11表示s1后面跟着s1的概率
若某段话第一个词为名词s1，那么该句子是“名动形名”的概率是多少？
\(P(s1,s2,s3,s1|model)=P(s1)P(s2|s1)P(s3|s2)P(s1|s3)=1*A12*A23*A31=0.004\)？？？
马尔科夫链：转移弧上有概率的非确定有限状态自动机，圈代表状态，每个结点的出度加起来是1
隐马尔可夫模型HMM：状态转换是不可观察的
EM（expectation maximization）
假设数据点是围绕k个核心点的k个正态分布源产生，目标是根据已知点推断正态分布的核心及参数，这也是一个贝叶斯问题
矛盾之处在于：蛋与鸡的问题
只有已知哪些点属于同一个圈，才能预测参数
只有参数靠谱，才能知道哪些点属于哪个圈
解这种问题，一般要先随机给蛋或鸡，随便猜一个参数，计算每个点属于哪个圈，接着重新评估参数，直至最后参数基本不变，有点kmeans那味。
