HMM实现中文分词

马尔可夫模型

如果系统中有N个状态S1,S2,…,Sn,随着时间的推移,该系统从某一状态转移到另一状态。如果用qt表示系统在时间t的状态,那么,t时刻的状态取值为Sj (i≤j≤N)的概率取决于前t-1个时刻的状态,该概率为:


  • 假设1:
  • 如果在特定情况下,系统在时间t的状态只与其在t-1时刻的状态有关,则该系统构成一个离散的一阶马尔科夫链:


  • 假设2:
  • 如果只考虑上面公式独立于时间t的随机过程,即所谓的不动性假设,状态与时间无关,那么:


该随机过程称为马尔可夫模型。

在马尔可夫模型中,状态转移概率a_ij必须满足下列条件:



状态序列S1,S2,…,ST的概率:



其中πi=p(q1=Si),为初始状态的概率。

隐马尔科夫模型

隐马尔科夫模型是一个双重随机过程,我们不知道具体的状态序列,只知道状态转移概率,即模型的状态转换过程是不可观察的,而可观察事件的随机过程是隐蔽状态转换过程的随机函数。

HMM的组成:

  1. 模型中的状态数为N
  2. 从每一个状态可能输出不同的符号数M
  3. 状态转移概率矩阵A=a_ij(a_ij为从状态S_i转向另一状态S_j的概率),其中

  4. 从状态S_j观察到某一特定符号v_k的概率分布矩阵为:B=bj(k)
  5. 其中,b_j (k)为状态j观察到符号k的概率。那么


  6. 初始状态概率分布为:π=π_i,其中,

为了方便,一般将HMM记为:μ=(A,B,π)或者μ=(S,O,A,B,π)用以指出模型的参数集合。

Viterbi 算法

Viterbi算法实质是动态搜索最优状态序列。定义Viterbi变量δ_t (i)是在时间t时,模型通过某条路径到达S_i并输出观察序列O=O_1 O_2,…O_T的最大概率:



递归计算:

算法

  1. 初始化:


  2. 概率最大的路径变量:ψ1(i)=0

  3. 递归计算
  4. 终结条件
  5. 通过回溯得到路径(状态序列)

算法的时间复杂度为:O(N^2 T)。

系统模块介绍

如下图所示,是系统实现的项目包结构:



HMM.java 是隐马尔科夫模型的实现类;MyUtil.java 是辅助工具类,例如将状态序列转换为分词结果;Segment.java 是分词函数的入口类;Demo.java 是测试样例类;下面会介绍它们的具体实现;lib文件夹里面是汉字字库文件以及训练测试文件。

HMM.java

成员变量:

private int N;				// 模型中状态的数目
private int M;				// 每个状态可能输出的观察符号数目
private double[][] A;		// 状态转移概率矩阵
private double[][] B;		// 观察符号概率矩阵
private double[] pi;		// 初始状态概率分布

成员方法:

/* 从文件中读入HMM数据,即N,M,A,B,pi
* HMM 文件格式:
* ---------------------------------------------
* N= <number of states>
* M= <number of symbols>
* A:
* a11 a12 ... a1N
* a21 a22 ... a2N
* aN1 aN2 ... aNN
* B:
* b11 b12 ... b1M
* b21 b22 ... b2M
* .   .   .   .
* bN1 bN2 ... bNM
* Pi:
* pi1 pi2 ... piN
*
* @param file: HMM数据文件
* @param charSet: 文件编码格式
*/
public void readHMM(String file, String charSet) {}
	
/* 写HMM数据到文件
* @param file: HMM输出文件
* @param charSet: 编码格式
*/
public void printHMM(String file, String charSet) {}
	
/* 从训练文件构建状态转移矩阵A和初始概率分布pi
* @param file: 训练文件
* @param charSet: 编码格式
*/
public void buildPiAndMatrixA(String file, String charSet) {}
	
/* 从训练文件构建观察符号矩阵B
* @param file: 训练文件
* @param charSet: 训练文件编码格式
* @param charMapFile: 汉字字库文件
* @param charMapCharset: 汉字字库文件编码格式
*/
public void buildMatrixB(String file, String charSet, String charMapFile, String charMapCharset) {}
	
/* 前向算法求解观察序列的概率
* @param T: 时间
* @param O:观察序列
* @return pprob:观察序列概率
*/
public void forward(int T, int[] O, double pprob) {}
	
/* 后向算法求解观察序列的概率
* @param T: 时间
* @param O:观察序列
* @return pprob:观察序列概率
*/
public void backward(int T, int[] O, double pprob) {}
	
/* Viterbi算法求解最优状态序列
* @param T: 时间
* @param O:观察序列
* @return q: 状态序列
* @return pprob:观察序列概率
*/
public void viterbi(int T, int[] O, int[] q, double pprob) {}

MyUtil.java

成员方法:

/* 根据测试语句得到观察序列
* @param sentence:测试语句,不包括空格
* @param dict:汉字字典(包括标点符号)
* @return O:观察序列
*/
public static void genSequence(String sentence, HashMap<Character, Integer> dict, int[] O) {}
   
/* 删除测试语句中的空格
* @param sentence: 测试语句
* @return :删除空格后的语句
*/
public static String delSpace(String sentence) {}
	
/* 根据状态序列切分测试语句
* @param sentence: 测试语句,不包括空格
* @param q:状态序列
* @param dict: 汉字哈希表
* @return line: 分词结果
*/
public static String printSegment(String sentence, int[] q, HashMap<Character, Integer> dict) {}
   
/* 从文件中读入汉字构建汉字哈希表
* @param file: 汉字字典,包括标点符号
* @param charSet: 文件编码
* @return dict:汉字哈希表
*/
public static void readDict(String file, String charSet, HashMap<Character, Integer> dict) {}

Segment.java
成员变量:

private String trainFile;		// 训练文件
private String trainCharset;	// 训练文件编码格式
private String cwLib;			// 汉字字库文件
private String cwLibCharset;	// 汉字字库文件编码格式

成员方法:

/* HMM对一个句子做切分
* @param sentence: 待切分句子
* @return : 切分结果
*/
public String hMMSegment(String sentence) {}

/* HMM对测试文件进行分词
* @param testFile: 测试文件路径
* @param testCharset: 测试文件编码格式
* @param resultFile: 分词结果保存路径
*/
public void hMMSegment(String testFile, String testCharset, String resultFile) {}

/* 反向最大匹配分词
* @param testFile: 测试文件
* @param testCharset: 测试文件编码格式
* @param resultFile: 分词结果保存路径
*/
public void backwardMaximumMatchSegment(String testFile, String testCharset, String resultFile) {}

/* 正向最大匹配分词
* @param testFile: 测试文件
* @param testCharset: 测试文件编码格式
* @param resultFile: 分词结果保存路径
*/
public void forwardMaximumMatchSegment(String testFile, String testCharset, String resultFile) {}	

Demo.java

public class Demo {
	public static void main(String[] args) {
		// HMM语句测试
		/*String test = "这是  一个训练文本,训练分词的效果";
		Segment seg = new Segment();
		System.out.println(seg.hMMSegment(test));*/
		
		// HMM文件测试
		Segment seg = new Segment("lib/pku_training.utf8", "UTF-8");
		seg.hMMSegment("lib/pku_test.utf8", "UTF-8", "hmm_4state_result.txt");
		
		// 反向最大匹配文件测试
		/*Segment seg = new Segment("lib/pku_training_words.utf8", "UTF-8");
		seg.backwardMaximumMatchSegment("lib/pku_test.utf8", "UTF-8", "bw_result.txt");
		System.out.println("Finished");*/
		
		// 正向最大匹配文件测试
		/*Segment seg = new Segment("lib/pku_training_words.utf8", "UTF-8");
		seg.forwardMaximumMatchSegment("lib/pku_test.utf8", "UTF-8", "fw_result.txt");
		System.out.println("Finished");*/
	}
}

实验结果

由于没有下载到北大人民日报的词性标注语料库,这里使用 backoff2005 中的语料进行训练,但是由于没有词性标注,这里采用了基于字的切分方式,即把B(Begin), M(Middle), E(End), S(Single) 作为状态,而每个汉字(包括标点符号)作为观察符号。

下面是使用HMM模型,正向最大匹配,反向最大匹配在 backoff2005 中as、 cityu、 msr 和 pku 数据集上的测试结果:其中,每个单元格内的三个数字分别表示召回率、准确率和 F值。

正向最大匹配 反向最大匹配 隐马尔科夫
as 0.284
0.269
0.276
0.285
0.270
0.277
0.064
0.071
0.067
ciytu 0.908
0.838
0.872
0.910
0.840
0.874
0.554
0.406
0.467
msr 0.957
0.917
0.937
0.955
0.915
0.935
0.775
0.740
0.757
pku 0.907
0.843
0.874
0.909
0.845
0.876
0.591
0.731
0.654

从上表中可以看出,正向最大匹配和反向最大匹配对于词典有很严重的依赖,词典的好坏直接决定了分词的效果;用隐马尔科夫模型在 as 数据集上测试时,由于汉字字库文件中不包含繁体字,即存在很多的未登录词,所以分词结果效果很差。由于正向最大匹配和反向最大匹配使用的词典都是 backoff2005 各个数据集对应的训练文件,故分词效果比HMM高出许多。而由于采用了基于字的方法,而不是基于词性,将词性作为状态,词作为观察符号,HMM模型并没有达到通常的分词效果。

另外,在性能上,数据集比较小时正向和反向最大匹配比HMM稍快,但数据集大时HMM开始超过正向和反向最大匹配,这些测试中最长用时为3.5秒。

由于HMM分词效果较差,通过阅读文献了解到基于字的条件随机场(CRFs)模型分词效果比HMM要好,我还用开源工具 CRF++ 实现了基于条件随机场的分词模型,在backoff2005 msr数据集上的分词结果显示,召回率、准确率和F值分别为 0.965,0.964,0.965,显然高于HMM的分词效果,但是CRF模型的训练时间比HMM要多很多,在我的实验中训练msr数据集用了将近3个小时。关于CRF++实现中文分词的具体介绍可以查看我的博文:基于CRF++实现中文分词。

隐马尔科夫模型实现分词就介绍到这里,详细代码可以访问我的Github项目:cwsegment


Reference:
《统计自然语言处理》 宗成庆著,第二版

Tagged on: ,

5 thoughts on “HMM实现中文分词

      1. 音之

        sorry, 我没说清楚。不是“算法”部分的“递归计算”。是 Viterbi算法下面第一段,“算法”部分前面的“递归计算”:delta_t+1(i) = max_j [delta_t(j)*a_ij]*b_i(O_t+1)感觉这里的i和j如果是j->i的话,应该就是a_ji了。

发表评论

电子邮件地址不会被公开。