分类 三、机器学习 下的文章

决策树学习的算法通常是一个递归地选择最优特征，并根据该特征对训练数据进行分割，使得对各个子数据集有一个最好的分类的过程。

一、决策树

单树作为所有集成树的基数，主要有三种：
1.ID3 (分类树)
2.C4.5（分类树）
3.CART（回归树）




- 阅读剩余部分 -

一、基本概念

1.分类原理

通过某对象的先验概率，利用贝叶斯公式，计算出其后验概率。即该对象属于某一类的概率，选择具有最大后验概率的类作为该对象所属的类。

2.贝叶斯公式

$$P(A|B) = \frac{P(B|A)*P(A)}{P(B)}$$

  • (1).其中P(A)为先验概率：先验概率（prior probability）是指根据以往经验和分析得到的概率，如全概率公式，它往往作为"由因求果"问题中的"因"出现的概率。；
  • (2).其中P(B|A)为似然概率(likelihood)，条件概率：是先前统计的事件中，A事件发生情况下B事件发生的概率
  • (3).其中P(B)为边界似然概率；
  • (4).其中P(A|B)为后验概率；
3.相关概念
  • (1).先验概率：是指根据以往经验和分析得到的概率

  • (2).----

    • ①后验概率：后验概率是指通过调查或其它方式获取新的附加信息,利用贝叶斯公式对先验概率进行修正,而后得到的概率
    • ②.最大后验概率：

  • (3).---

    • ①.条件概率：指事件A在另外一个事件B已经发生条件下的发生概率。条件概率表示为：P(A|B)。若只有两个事件A，B，那么$P(A|B) = \frac{P(AB)}{P(B)}$
    • ②.联合概率：表示两个事件共同发生的概率。A与B的联合概率表示为 P(AB) 或者P(A,B),或者P（A∩B）
    • ③.全概率
  • (4).似然概率

联合概率的乘法公式为：P(AB) = P(A|B)*P(B),变形后可得到$P(A|B) = \frac{P(AB)}{P(B)}$

二、朴素贝叶斯分类器

1.朴素贝叶斯分类的定义

朴素贝叶斯分类的正式定义如下：
(1).设 $x = \left\{ f_{1},f_{2},f_{3},...,f_{m} \right\}$为一个待分类项，而每个f为x的一个特征。
(2).有类别集合$C = \left\{ y_{1},y_{2},y_{3},...,y_{n} \right\}$
(3).计算$P(y_{1}|x),P(y_{2}|x),....,P(y_{n}|x)$
(4).如果$P(y_{k}|x) = max \left\{ P(y_{1}|x),P(y_{2}|x),....,P(y_{n}|x) \right\}，则x∈y_{k}$。
那么现在的关键就是如何计算第3步中的各个条件概率。我们可以这么做：
(1)、找到一个已知分类的待分类项集合，这个集合叫做训练样本集。
(2)、统计得到在各类别下各个特征属性的条件概率估计。即
$P(x_{1}|y_{1}),P(x_{2}|y_{1}),...,P(x_{3}|y_{1})$;
$P(x_{1}|y_{2}),P(x_{2}|y_{2}),...,P(x_{3}|y_{2})$;
......
$P(x_{1}|y_{3}),P(x_{2}|y_{3}),...,P(x_{3}|y_{3})$;
(3)、如果各个特征属性是条件独立的，则根据贝叶斯定理有如下推导：
$P(y_{i}|x) = \frac {P(x|y_{i})P(y_{i})}{P(x)}$
因为分母对于所有类别为常数，因为我们只要将分子最大化皆可。又因为各特征属性是条件独立的，所以有：
$P(x|y_{i})P(y_{i}) = P(a_{1}|y_{i})P(a_{2}|y_{i})...P(a_{m}|y_{i})P(y_{i})=P(y_(i))\prod\limits_{j=1}^mP(a_j|yi)$

2.朴素贝叶斯分类的举例

我们知道朴素贝叶斯的公式为：
$P(C|f) = \frac{P(f|C)*P(C)}{P(f)}$
如果换个表达式就会明朗很多，如下：
$P(类别|特征) = \frac{P(特征|分类)*P(分类)}{P(特征)}$
其中P(分类)和P(特征)都是已知的，我们只需求P(特征|分类)即可。

例题分析

给定数据如下：

高否富否帅否嫁否
高富帅嫁
高不富帅嫁
不高富不帅嫁
高富不帅不嫁
不高不富帅不嫁
高不富不帅不嫁
不高不富不帅不嫁

那我们现在的问题是，一个男生向一个女生求婚，这个男生具有以下三个特点：不高、富、帅，请你判断以下该女孩是否会嫁？

这是一个典型的分类问题，转化为概率论问题就是$P(嫁|不高、富、帅)$ 与 $P(不嫁|不高、富、帅)那个概率更大？

这里我们就使用朴素贝叶斯公式来分别求以下两种情况下的概率：

  • ①$P(嫁|不高、富、帅) = \frac {P(不高、富、帅|嫁)*P(嫁)}{P(不高、富、帅)}$
  • ②$P(不嫁|不高、富、帅) = \frac {P(不高、富、帅|不嫁)*P(不嫁)}{P(不高、富、帅)}$
对①求解

我们先对要求①进行求解。要求$P(嫁|不高、富、帅)$的概率只需求$P(不高、富、帅|嫁)、P(嫁)、P(不高、富、帅)$即可。根据“朴素”一词也就是各个特征之间是独立的，可以得到如下<1>公式和<2>公式(只需求如下公式即可)：
<1>$P(不高、富、帅|嫁) = P(不高|嫁)*P(富|嫁)*P(帅|嫁)$
<2>$P(不高、富、帅) = P(不高)*P(富)*P(帅)$
同时只需要再求出公式<3>问题就得到解决
<3>$P(嫁)$

我们从表格中统计所有嫁的样本共有3条，其中不高的样本有1条，所以$P(不高|嫁) = 1/3$，同理可以得到$P(富|嫁) = 2/3$， $P(帅|嫁) = 2/3$。

我们从表格中统计所有样本共有7条，其中嫁的样本有3条，所以 $P(嫁) = 3/7$。

我们从表格中统计所有样本共有7条，其中不高的样本有3条，所以 $P(不高) = 3/7$，其中富的样本有3条所以$P(富) = 3/7$，其中帅的样本有3条所以$P(帅) = 3/7$。

综上①$P(嫁|不高、富、帅) = \frac {P(不高、富、帅|嫁)*P(嫁)}{ \; P(不高、富、帅) \; } $
此公式 $= \frac {(\frac {1}{3} *\frac {2}{3}*\frac {2}{3})*\frac {3}{7}} {\frac {3}{7} *\frac {3}{7}*\frac {3}{7}} =\frac {196}{243}$

d对②求解

$P(不嫁|不高、富、帅) = \frac {P(不高、富、帅|不嫁)*P(不嫁)}{P(不高、富、帅)}$
此公式 $= \frac {(\frac {1}{2} *\frac {1}{4}*\frac {1}{4})*\frac {4}{7}} {\frac {3}{7} *\frac {3}{7}*\frac {3}{7}} =\frac {49}{216}$

所以最终的答案是“嫁”
参考：
1.https://blog.csdn.net/xueyingxue001/article/details/52396170
2.https://blog.csdn.net/amds123/article/details/70173402

一、CRF模型的基本元素

1、 CRF的五个基本元素

HMM中，有5个基本元素：{I,O,A,B,π}，我结合序列标志任务对这5个基本元素做一个介绍：

(1)I:状态序列。在这里，是指每一个词语背后的标注。
(2)O:观测序列。在这里，是指每一个词语本身。
(3)A:转移特征函数(状态转移概率矩阵)：$m_kt_k(y_{i-1},y_i,x,i)$,k为特征个数
(4)B:状态特征函数(观测概率矩阵)：$u_ls_l(y_i,x,i)$,$l$为特征个数

2、CRF模型

20201010203039807.png

建模函数：
$P(y|x)=\frac{1}{Z(x)} exp(\sum λ_kt_k(y_{i-1},y_i,x,i)+\sum u_ls_l(y_i,x,i))$

20201009172828707.png

20201009172848167.png

20201009172913704.png

3、CRF模型的一个假设

假设：满足马尔科夫性：
$P(Y_i|X,Y_1,....,Y_{i-1},Y_{i+1},...y_n)=P(Y_i|X,Y_{i-1},Y_{i+1})$

二、CRF模型有三种应用场景

我们做命名实体识别只用到其中的一种——求观察序列的背后最可能的标注序列。CRF解决的三个问题：

1、Evaluation(概率计算问题)

已知模型参数 λ= (A, B, π),计算某个观测序列发生的概率，即求P(O|λ)

2、Learning(学习问题)

给定观测序列$O=(o_1,o_2,...,o_n)$，如何调整模型参数 λ=(π, A, B), 使得P(O|λ)最大？，这个就是求模型的算法

3、Decoding(预测问题或者叫解码问题) 最常用

给定观测序列O和模型 λ，求最有可能的状态序列S(s1,s2,...st+1)。
例如：通过实体标注和训练，我们可以得到模型λ，现在给定了一个观测序列=我在凤凰金融工作，求最有可能的命名实体有哪些，想找到对应的状态序列S=(我，在，凤凰金融，工作)。

三、模型由来

1.HMM假设缺点
  • (1)齐次马尔科夫假设（又叫一阶马尔科夫假设）
    隐藏的马尔科夫链在任意时刻t的状态只依赖于前一时刻的状态，与其他时刻状态及观测状态无关。

$P(i_t|i_{t-1},o_{t-1},...,i_1) = P(i_t|i_{t-1})$

  • (2)观测独立假设
    任意时刻的观测状态只依赖于该时刻的马尔科夫链的状态，与其他时刻的观测状态无关。
2.CRF优点

因为HMM有两个前提假设，所以HMM注定是局部最优解，无法达到全局最优解，也就无法达到最好的效果。

3.CRF算法

CRF解决了HMM两个假设的缺点，使用概率无向图，提出了两个特征函数
1.定义在边上的转移特征函数：$m_kt_k(y_{i-1},y_i,x,i)$
2.定义在节点上的状态特征函数：$u_ls_l(y_i,x,i)$
每个特征函数前面有系数
注意：

  • 1.每个时刻t=i有多个特征函数，每个特征函数取值为1或者0，然后每个序列有多个时刻，所以模型上有两个加。
  • 2.每个特征函数其实是个局部特征，可以对局部特征求和，将局部特征转化为全局特征。那么为啥求和是全局特征？其实求和的本意是求乘积，因为e为底的指数和就是乘积的形式，这就需要概率无向图求联合概率分布的算法。
  • 3.CRF本质上是求概率无向图的联合概率分布，就是去各个时刻标注同时标注正确的联合概率，那么如何求概率无向图的联合概率分布呢？一般是将联合概率写成若干个子联合概率相乘的形式。也就是将联合概率因子分解。
  • 4.联合概率因子分解：概率无向图的联合概率分布表示为其最大团上的随机变量函数的乘积，我们平时所说的CRF指的是线性连CRF，所以说每个时刻的i,o构成了一个最大团，所以证明了全局最优解就是局部最优解的和的形式。

参考：
1.https://spaces.ac.cn/archives/5542/comment-page-1
2.https://www.zhihu.com/question/35866596/answer/236886066
3.https://www.cnblogs.com/pinking/p/9194865.html

一、HMM模型的基本元素

1、 HMM的五个基本元素

HMM中，有5个基本元素：{I,O,A,B,π}，我结合序列标志任务对这5个基本元素做一个介绍：

(1)I:状态序列。在这里，是指每一个词语背后的标注。
(2)O:观测序列。在这里，是指每一个词语本身。
(3)A:状态转移概率矩阵。在这里，是指某一个标注转移到下一个标注的概率。
(4)B:观测概率矩阵，也就是发射概率矩阵。在这里，是指在某个标注下，生成某个词的概率。
(5)π:初始概率矩阵。在这里，是指每一个标注的初始化概率。
其中：
$I = ({i_1,i_2,i_3...i_N})$ 状态序列
$O = ({o_1,o_2,o_3...o_N})$ 观测序列
$A = [a_{ij}]_{N*N}$ 状态转移概率矩阵
$B = [b_j(k)]_{N*N}$ 观测概率矩阵
π 初始状态概率向量

HMM主要解决预测问题：也称为解码（decoding）问题。已知模型
λ＝(A，B, π) 和观测序列$O = ({o_1,o_2,o_3...o_N})$ ，，求对给定观测序列条件概率P(I|O)最大的状态序列 $I = ({i_1,i_2,i_3...i_N})$ 。即给定观测序列，求最有可能的对应的状态序列。

2、HMM模型

aHR0cHM6Ly9yYXcuZ2l0aHVidXNlcmNvbnRlbnQuY29tL2xpc3R3ZWJpdC9JbWdEYXRlL21hc3Rlci9obW0uanBn.jpg
模型：λ = (A,B,π)
A,B,π为隐马尔可夫模型的三个要素
这三个元素都是通过统计得到的，这三个值就是模型的参数，得到这三个值的过程就是模型训练的过程，所以说HMM算法是比较简单的算法。模型已经知道了，可以认为各个状态的全连接路径已经知道了，给个观测序列，通过veterbi算法求解所有路径中的最优路径。

3、HMM模型的两个假设
  • (1)齐次马尔科夫假设（又叫一阶马尔科夫假设）
    隐藏的马尔科夫链在任意时刻t的状态只依赖于前一时刻的状态，与其他时刻状态及观测状态无关。

$P(i_t|i_{t-1},o_{t-1},...,i_1) = P(i_t|i_{t-1})$

  • (2)观测独立假设
    任意时刻的观测状态只依赖于该时刻的马尔科夫链的状态，与其他时刻的观测状态无关。

而以上的这些元素，都是可以从训练语料集中统计出来的。最后，我们根据这些统计值，应用维特比（viterbi）算法，就可以算出词语序列背后的标注序列了。

二、隐马尔可夫模型有三种应用场景

我们做命名实体识别只用到其中的一种——求观察序列的背后最可能的标注序列。
最后，来说下HMM解决的三个问题：

1、Evaluation(概率计算问题)

已知模型参数 λ= (A, B, π),计算某个观测序列发生的概率，即求P(O|λ)

2、Learning(学习问题)

给定观测序列$O=(o_1,o_2,...,o_n)$，如何调整模型参数 λ=(π, A, B), 使得P(O|λ)最大？，这个就是求模型的算法

3、Decoding(预测问题或者叫解码问题) 最常用

给定观测序列O和模型 λ，求最有可能的状态序列S(s1,s2,...st+1)。
例如：通过实体标注和训练，我们可以得到模型λ，现在给定了一个观测序列=我在凤凰金融工作，求最有可能的命名实体有哪些，想找到对应的状态序列S=(我，在，凤凰金融，工作)。

三、求模型λ：解决第二个问题

HMM是一种生成模型，所以求的是联合概率

注意：我们平时所说的，求模型指的是求目标函数，例如在线性回归中我们的目标函数为$h(λ)=λ_1X+λ_2$，求目标函数只需要求得参数λ，所以平时我们说求模型就是求参数。

$P(X,Y)$

四、维特比算法(Viterbi):解决第三个问题

维特比算法主要用动态规划来求解HMM的预测问题：一直模型和观测序列，求最可能的状态序列

假如状态序列为：$x_1,x_2,x_3 ... x_N$
对应观测序列为：$y_1,y_3,y_3 ... y_N$
那么我们的问题就转化为：在盲打时候已知输入序列$y_1,y_3,y_3 ... y_N$，对应的最可能汉字$x_1,x_2,x_3 ... x_N$。求最可能的汉字序列是什么？
公式：
$x_1,x_2,x_3 ... x_N = ArgMaxP(x_1,x_2,x_3 ... x_N|y_1,y_3,y_3 ... y_N)$
$= ArgMax \prod_{i=1}^N P(y_i|x_i)*P(x_i|x_{i-1})$

其中公式$ArgMax \prod_{i=1}^N P(y_i|x_i)*P(x_i|x_{i-1})$主要通过贝叶斯公式变换得来

我们知道贝叶斯公式为：$P(A|B) = \frac {P(B|A)*P(A)}{P(B)}$
那么$P(x|y) = \frac {P(y|x)*P(x)}{P(y)}$,其中P(y)为已知常数，其中P(x)实际为$P(x_t|x_{t-1})$,根据马尔科夫假设当前时刻假设之和前一时刻相关。

例如，输入观测序列：
我 爱 中 国
O O O B
O B O I
O O B I
B O I B
也就是求的第三行是最优路径：

四、维特比算法(Viterbi)

注意：viberbi算法计算过程中计算的是两个点之间的最短路径，不是计算的两个层之间的最短路径
1.性质

如果概率最大的路径p(或者说最短路径)经过某个点，比如途中的a，那么这条路径上的起始点S到a的这段子路径Q，一定是S到X22之间的最短路径。否则，用S到a的最短路径R替代Q，便构成一条比P更短的路径，这显然是矛盾的。证明了满足最优性原理。

2.算法

假如你从S和E之间找一条最短的路径，除了遍历完所有路径，还有什么更好的方法？
Dingtalk_20240529175903.jpg
实际上在所有路径中肯定有一条最短路径：

我们开始从头一步一步求解：
(1)首先起点是S，从S到A列的路径有三种可能：S-A1、S-A2、S-A3，如下图：

Dingtalk_20240529180048.jpg

我们不能武断地说S-A1、S-A2、S-A3中的哪一段必定是全局最短路径中的一部分，目前为止任何一段都有可能是全局最短路径的备选项。
(2).然后开始第二层
<1>我们先从第二层的第一个节点开始：
Dingtalk_20240529180140.jpg

如上图，经过B1的所有路径只有3条：

S-A1-B1

S-A2-B1

S-A3-B1
如果说最终的第二层的节点是从B1经过的话，肯定要从这三条路径中选择一条最短的路径，那么其他的两条可以删除了。
<2>然后我们开始了第二层的第二个节点：

Dingtalk_20240529180255.jpg

同理，如上图，经过B2的路径有3条：

S-A1-B2

S-A2-B2

S-A3-B2
如果说最终的第二层的节点是从B2经过的话，肯定要从这三条路径中选择一条最短的路径，那么其他的两条可以删除了。

<3>然后我们开始了第二层的第三个个节点：
Dingtalk_20240529180407.jpg
同理，如上图，经过B3的路径也有3条：

S-A1-B3

S-A2-B3

S-A3-B3
如果说最终的第二层的节点是从B3经过的话，肯定要从这三条路径中选择一条最短的路径，那么其他的两条可以删除了。
<4>所有第二层的阶段遍历完了之后，剩下三条路径了。

我们还没有足够的信息判断哪一条一定是全局最短路径的子路径。
(3)然后我们在第三层继续这个算法:
下来讲到C列了，类似上面说的B列，我们从C1、C2、C3一个个节点分析。
经过C1节点的路径有：

S-A3-B1-C1、

S-A1-B2-C1、

S-A2-B3-C1
WX20220514-151839@2x.png
和B列的做法一样，从这三条路径中找到最短的那条（假定是S-A3-B1-C1），其它两条路径同样道理可以删掉了。那么经过C1的所有路径只剩一条，如下图：
WX20220514-152010@2x.png

同理，我们可以找到经过C2和C3节点的最短路径，汇总一下：

2020101019434976.png
我们还没有足够的信息判断哪一条一定是全局最短路径的子路径。
(4)然后我们在最后一层继续这个算法:
202010101944436.png

E点已经是终点了，我们稍微对比一下这三条路径的总长度就能知道哪条是最短路径了。

参考文章
https://clyyuanzi.gitbooks.io/julymlnotes/content/hmm.html
http://www.52nlp.cn/category/hidden-markov-model
https://www.lookfor404.com/%E7%94%A8%E9%9A%90%E9%A9%AC%E5%B0%94%E5%8F%AF%E5%A4%AB%E6%A8%A1%E5%9E%8Bhmm%E5%81%9A%E5%91%BD%E5%90%8D%E5%AE%9E%E4%BD%93%E8%AF%86%E5%88%AB-ner%E7%B3%BB%E5%88%97%E4%BA%8C/
https://www.zhihu.com/question/35866596/answer/236886066
http://www.hankcs.com/ml/conditional-random-field.html

https://www.zhihu.com/question/20136144/answer/763021768

  1. 1
  2. 2
  3. 3
  4. 4
  5. 5