本文共 9025 字,大约阅读时间需要 30 分钟。
方法概述:按照一定的策略将待分析的汉字串与一个充分大的词典中的词条进行匹配,若在词典中找到某个字符串,则匹配成功。
典型方法:
1.正向最大匹配法 2.反向最大匹配法 3.最短路径法(最少分词法)eg.
句子:中医治白癜风 词典:中、医、治、中医、医治、白癜风 正向最大匹配法:中医/治/白癜风 反向最大匹配法:中/医治/白癜风 最短路径法: 独立自主/和平/等/互利/的/原则 独立自主/和/平等互利/的/原则正向最大匹配(Forward Maximum Matching, FMM)
1.令i=0,当前指针 P i P_i Pi指向输入字串的初始位置,执行下面的操作: 2.计算当前指针 P i P_i Pi到字串末端的字数(即未被切分字串的长度)n,如果n=1,转第4步,结束算法。否则,令m=字典中最长单词的字数,如果 n < m n<m n<m,令m=n; 3.从当前 P i P_i Pi起取m个汉字作为词 w i w_i wi,判断: (1)如果 w i w_i wi确实是词典中的词,则在 w i w_i wi后添加一个切分标志,转(3); (2)如果 w i w_i wi不是词典中的词且 w i w_i wi的长度大于1,将 w i w_i wi从右端去掉一个字,转(1)步;否则( w i w_i wi的长度等于1),则在 w i w_i wi后添加一个切分标志,将 w i w_i wi作为单字词添加到词典中,执行(3); (3)根据 w i w_i wi的长度修改指针 P i P_i Pi的位置,如果 P i P_i Pi指向字串末端,转第4步,否则, i = i + 1 i = i + 1 i=i+1,返回(2); 4.输出切分结果,结束分词程序最短路径法
1.相邻节点 V k − 1 , V k V_{k-1}, V_k Vk−1,Vk之间建立有向边 < V k − 1 , V k > <V_{k-1}, V_k> <Vk−1,Vk>,边对应的词默认为 C k ( k = 1 , 2 , . . . , n ) C_k (k = 1, 2, ..., n) Ck(k=1,2,...,n)。 2.如果 w = C i C i + 1 . . . C j ( 0 < i < j < = n ) w = C_i C_{i+1}... C_{j} (0<i<j<=n) w=CiCi+1...Cj(0<i<j<=n)是一个词,则节点 V i − 1 , V j V_{i-1},V_j Vi−1,Vj之间建立有向边 < V i − 1 , V j > <V_{i-1}, V_j> <Vi−1,Vj>,边对应的词为w。 3.重复步骤2,直到没有新路径(词序列)产生。 4.从产生的所有路径中,选择路径最短的(词数最少的)作为最终分词结果。基于统计的方法需要标注训练语料训练模型,可分为生成式统计分词和判别式统计分词
原理:首先建立学习样本的生成模型,再利用模型对预测结果进行间接推理。
马尔可夫模型
存在一类重要的随机过程(马尔可夫过程):如果一个系统有N个状态 S 1 , S 2 , . . . , S N S_1, S_2, ..., S_N S1,S2,...,SN,随着时间的推移,该系统从某一个状态转移到另一状态。如果用 q t q_t qt表示系统在时间t的状态变量,那么t时刻的状态取值为 S j ( 1 < = j < = N ) S_j (1<=j<=N) Sj(1<=j<=N)的概率取决于前t-1个时刻的状态,该状态的概率为: P ( q t = S j ∣ q t − 1 = S i , q t − 2 = S k , . . . ) P(q_t = S_j | q_{t-1} = S_i, q_{t-2} = S_k, ...) P(qt=Sj∣qt−1=Si,qt−2=Sk,...)假设1:一阶马尔可夫假设
如果在特定情况下,系统在时间t的状态只与其在时间t-1的状态相关,则该系统构成一个离散的一阶马尔可夫链。 P ( q t = S j ∣ q t − 1 = S i , q t − 2 = S k , . . . ) = P ( q t = S j ∣ q t − 1 = S i ) P(q_t = S_j | q_{t-1} = S_i, q_{t-2} = S_k, ...) = P(q_t = S_j | q_{t-1} = S_i) P(qt=Sj∣qt−1=Si,qt−2=Sk,...)=P(qt=Sj∣qt−1=Si)假设2:不动性假设
如果只考虑上述公式独立于时间t的随机过程,状态与时间无关,那么: P ( q t = S j ∣ q t − 1 = S i ) = a i j , 1 < = i , j < = N P(q_t = S_j | q_{t-1} = S_i) = a_{ij}, \quad\quad 1<=i,j<=N P(qt=Sj∣qt−1=Si)=aij,1<=i,j<=N a i j > = 0 ∑ j = 1 N a i j = 1 a_{ij}>=0 \quad\quad\quad \sum_{j=1}^N a_{ij} = 1 aij>=0j=1∑Naij=1马尔可夫模型状态表示:马尔可夫链可以表示成状态图(转移弧上有概率的非确定的有限状态自动机)
马尔可夫模型状态序列的概率
状态序列 S 1 , . . . , S T S_1, ..., S_T S1,...,ST的概率: P ( S 1 , . . . , S T ) = P ( S 1 ) P ( S 2 ∣ S 1 ) P ( S 3 ∣ S 1 , S 2 ) . . . P ( S T ∣ S 1 , . . . , S T − 1 ) P(S_1, ..., S_T) = P(S_1)P(S_2 | S_1)P(S_3 | S_1, S_2) ... P(S_T | S_1, ..., S_{T-1}) P(S1,...,ST)=P(S1)P(S2∣S1)P(S3∣S1,S2)...P(ST∣S1,...,ST−1) 一 阶 马 尔 可 夫 假 设 = P ( S 1 ) P ( S 2 ∣ S 1 ) P ( S 3 ∣ S 2 ) . . . P ( S T ∣ S T − 1 ) 一阶马尔可夫假设 = P(S_1)P(S_2 | S_1)P(S_3 | S_2) ... P(S_T | S_{T-1}) 一阶马尔可夫假设=P(S1)P(S2∣S1)P(S3∣S2)...P(ST∣ST−1) 不 动 性 假 设 = π S 1 ∏ t = 1 T − 1 a S t S t + 1 不动性假设 = \pi_{S_1}\prod_{t=1}^{T-1} a_{S_t S_{t+1}} 不动性假设=πS1∏t=1T−1aStSt+1其中, π = P ( q 1 = S i ) \pi = P(q_1 = S_i) π=P(q1=Si)为初始状态的概率。 隐马尔可夫模型隐马尔可夫模型是关于时序的概率模型,是一个双重随机过程。其描述由一个隐藏的马尔可夫链随机生成不可观察的状态随机序列,再由各个状态生成一个观察,从而产生随机观察序列的过程,序列的每一个位置又可以看作是一个时刻。
wiki定义:隐马尔可夫模型是统计模型,它用来描述一个含有隐含未知参数的马尔可夫过程。其难点是从可观察的参数中确定该过程的隐含参数。然后利用这些参数来作进一步的分析,例如模式识别。
示例:
房间里有N个盒子,每个盒子中有M种不同颜色的球。一实验员进入房间根据某一概率分布选择一个盒子,然后根据盒子中不同颜色球的概率分布随机取出一个球,并向房间外的人报告该球的颜色。 对房间外的人:可观察的过程是不同颜色球的序列,而盒子的序列是不可观察的。 每只盒子对应HMM中的一个状态;球的颜色对应于HMM中状态的输出。图解
HMM的组成
假设
生成观察序列
三个问题:
1. 概率计算问题
对于给定的状态序列 Q = q 1 q 2 . . . q T Q = q_1 q_2 ... q_T Q=q1q2...qT,求 P ( O ∣ μ ) P(O | \mu) P(O∣μ)? 在公式里,我们需要遍历所有满足条件的Q,即遍历所有路径。 一阶马尔可夫假设: 观察独立假设: 可以看出,如果模型 μ = ( A , B , π ) \mu = (A, B, \pi) μ=(A,B,π)有N个不同的状态,时间长度为T,那么有 N T N^T NT个可能的状态序列,搜索路径成指数级组合爆炸。 可以通过动态规划,利用地推算法提高计算效率概率计算问题——前向算法
前向算法计算过程:
算法的时间复杂性:
递推计算中,每一次计算可以直接饮用前一个时刻的计算结果,避免了重复计算。示例
共有3个盒子,每个盒子里分别有红、白两种球,对应的状态转移概率矩阵、观察概率矩阵和初始状态概率分布如下所示: (1)计算前向向量的初值: (2)递推计算: (3)终止:概率计算问题——后向算法
后向算法——算法描述
2. 隐马尔可夫模型——预测问题
针对第二种解释,可使用Viterbi 算法:动态搜索最优状态序列
Viterbi算法
示例:
3. 隐马尔科夫模型——学习问题
有监督学习的方法:假设训练数据是包括观测序列O和对应的状态序列Q,则可以利用最大似然估计来计算模型的参数。
无监督学习方法
无监督学习方法
Baum-Welch算法(前向后向算法)描述:
生成式方法的优缺点:
转载地址:http://yqobb.baihongyu.com/