Conditional Random Field：条件随机场，一种机器学习技术（模型）
CRF由John Lafferty最早用于NLP技术领域，其在NLP技术领域中主要用于文本标注，并有多种应用场景，例如：
分词（标注字的词位信息，由字构词） 词性标注（标注分词的词性，例如：名词，动词，助词） 命名实体识别（识别人名，地名，机构名，商品名等具有一定内在规律的实体名词）本文主要描述如何使用CRF技术来进行中文分词。
1. CRF把分词当做字的词位分类问题，通常定义字的词位信息如下：
词首，常用B表示 词中，常用M表示 词尾，常用E表示 单子词，常用S表示2. CRF分词的过程就是对词位标注后，将B和E之间的字，以及S单字构成分词
3. CRF分词实例：
原始例句：我爱北京天安门CRF标注后：我/S 爱/S 北/B 京/E 天/B 安/M 门/E 分词结果：我/爱/北京/天安门上面介绍了CRF技术思想以及如何用于分词，下面将介绍如何在实际开发中使用CRF进行分词工作。目前常见的CRF工具包有pocket crf, flexcrf 车crf++，目前网上也有一些它们3者之间的对比报告，个人感觉crf++在易用性，稳定性和准确性等综合方面的表现最好，同时在公司的项目开发中也一直在使用，因此下面将概述一下crf++的使用方法(具体细节可以到crf++官方主页去查阅，http://crfpp.sourceforge.net/)1.安装编译器要求：C++编译器(gcc 3.0或更高)命令：% ./configure% make% su# make install注：只有拥有root帐号的用户才能成功安装。2.使用2.1训练和测试文件的格式训练和测试文件必须包含多个tokens，每个token包含多个列。token的定义可根据具体的任务，如词、词性等。每个token必须写在一行，且各列之间用空格或制表格间隔。一个token的序列可构成一个sentence，sentence之间用一个空行间隔。最后一列是CRF用于训练的正确的标注形式。例如：iphone ASCII S是 CN S一 CN S >> 当前token款 CN S不 CN B错 CN E的 CN S手 CN B机 CN E, PUNC S还 CN S能 CN S听 CN B歌 CN E。PUCN S我上面的例子每个token包含3列，分别为字本身、字类型（英文数字，汉字，标点等）和词位标记。注意：如果每一个token的列数不一致，系统将不能正确运行。2.2准备特征模板使用CRF++的用户必须自己确定特征模板。1)基本模板和宏模板文件中的每一行代表一个template。每一个template中，专门的宏%x[row,col]用于确定输入数据中的一个token。row用于确定与当前的token的相对行数。col用于确定绝对行数。如已知下面的输入数据：iphone ASCII S是 CN S一 CN S >> 当前token款 CN S不 CN B错 CN E的 CN S手 CN B机 CN E特征模板形式为：# UnigramU00:%x[-2,0]U01:%x[-1,0]U02:%x[0,0]U03:%x[1,0]U04:%x[2,0]U05:%x[-1,0]/%x[0,0]U06:%x[0,0]/%x[1,0]U07:%x[-1,0]/%x[1,0]U08:%x[0,1]U09:%x[-1,1]/%x[0,1]# BigramB2)模板类型有两种模板类型，它们可由template的第一个字符确定。第一种是Unigram template：第一个字符是U这是用于描述unigram feature的模板。当你给出一个模板"U02:%x[0,0]"，CRF会自动的生成一个特征函数集合(func1 ... funcN)，如：func1 = if (output = B and feature="U02:一") return 1 else return 0func2 = if (output = M and feature="U02:一") return 1 else return 0func3 = if (output = E and feature="U02:一") return 1 else return 0func4 = if (output = S and feature="U02:一") return 1 else return 0...funcX = if (output = B and feature="U02:的") return 1 else return 0funcY = if (output = S and feature="U02:的") return 1 else return 0...一个模型生成的特征函数的个数总数为L*N，其中L是输出的类别数，N是根据给定的template扩展出的unique string的数目。第二种类型Bigram template:第一个字符是B这个模板用于描述bigram features。使用这个模板，系统将自动产生当前输出token与前一个输出token(bigram)的组合。产生的可区分的特征的总数是 L*L*N，其中L是输出类别数，N是这个模板产生的unique features数。当类别数很大的时候，这种类型会产生许多可区分的特征，这将会导致训练和测试的效率都很低下。3)使用标识符区分相对位置如果用户需要区分token的相对位置时，可以使用标识符。比如在下面的例子中，宏"%x[-2,0]"和"%x[1,0]"都代表“北”，但是它们又是不同的“北“。北 CN B京 CN E的 CN S >> 当前token北 CN S部 CN S为了区分它们，可以在模型中加入一个唯一的标识符(U00: 或 U03:)，即：U00:%x[-2,0]U03:%x[1,0]在这样的条件下，两种模型将被认为是不同的，因为他们将被扩展为”U00:北“和”U03:北”。只要你喜欢，你可以使用任何标识符，但是使用数字序号区分更很有用，因为它们只需简单的与特征数相对应。3.训练（编码）使用crf_learn 命令：% crf_learn template_file train_file model_file其中，template_file和train_file需由使用者事先准备好。crf_learn将生成训练后的模型并存放在model_file中。一般的，crf_learn将在STDOUT上输出下面的信息。还会输出其他的和LBFGS迭代相关的信息。% crf_learn template_file train_file model_fileCRF++: Yet Another CRF Tool KitCopyright (C) 2005 Taku Kudo, All rights reserved.reading training data:Done! 0.32 sNumber of sentences: 77Number of features: 32856Freq: 1eta: 0.0001C(sigma^2): 10iter=0 terr=0.7494725738 serr=1 obj=2082.968899 diff=1iter=1 terr=0.1671940928 serr=0.8831168831 obj=1406.329356 diff=0.3248438053iter=2 terr=0.1503164557 serr=0.8831168831 obj=626.9159973 diff=0.5542182244其中：iter：迭代次数terr：和tags相关的错误率(错误的tag数/所有的tag数)serr：与sentence相关的错误率（错误的sentence数/所有的sentence数）obj：当前对象的值。当这个值收敛到一个确定的值是，CRF模型将停止迭代diff：与上一个对象值之间的相对差有两个主要的参数用于控制训练条件：-c float：使用这个选项，你可以改变CRF的hyper-parameter。当取一个极大的C值，CRF将可能对训练数据产生过拟合（overfitting）现象。这个参数将会调节overfitting和underfitting之间的平衡。结果将会对参数带来有意义的影响。使用者可以通过使用held-out data或者更多的通用模型的选择方法如十字交叉验证法(cross validation)获得最有的值。-f NUM：这个参数用于设置特征的cut-off阈值。CRF++训练时只使用出现次数不少于NUM次数的特征进行训练。默认值为1。当使用CRF++训练大规模数据时，单一特征的数量将达到数百万，此时选择这个参数很有用。这里有一个使用这两个参数的例子：% crf_learn -f 3 -c 1.5 template_file train_file model_file4.测试（解码）使用crf_test 命令：% crf_test -m model_file test_files ...其中，model_file是crf_learn创建的。在测试过程中，使用者不需要指定template file，因为，mode file已经有了template的信息。test_file是你想要标注序列标记的测试语料。这个文件的书写格式应该与训练文件一致。下面是一个crf_test输出的例子：% crf_test -m model test.dataRockwell NNP B BInternational NNP I ICorp. NNP I I's POS B BTulsa NNP I Iunit NN I I..其中，最后一列是模型估计的tag。如果第三列是标准的tag，则可以通过简单的比较第三列和第四列之间的差别计算出准确率。详细的层次（verbose level）-v选项：将设置verbose level。默认值为0。通过增加层次，你可以从CRF++获得额外的信息。层次1：你可以对每个tag使用边缘概率(marginal probabilities)（这是一种对输出tag的confidence measure），对输出使用条件概率(conditional probably)（针对整个输出的confidence measure）。例如：% crf_test -v1 -m model test.data| head# 0.478113Rockwell NNP B B/0.992465International NNP I I/0.979089Corp. NNP I I/0.954883's POS B B/0.986396Tulsa NNP I I/0.991966...其中，第一行的"# 0.478113"即是输出的条件概率，而且每一个输出tag各自含有一个概率，表示形式如“B/0.992465”。层次2：你可以对所有的其他候选求边缘概率。例如：% crf_test -v2 -m model test.data# 0.478113Rockwell NNP B B/0.992465 B/0.992465 I/0.00144946 O/0.00608594International NNP I I/0.979089 B/0.0105273 I/0.979089 O/0.0103833Corp. NNP I I/0.954883 B/0.00477976 I/0.954883 O/0.040337's POS B B/0.986396 B/0.986396 I/0.00655976 O/0.00704426Tulsa NNP I I/0.991966 B/0.00787494 I/0.991966 O/0.00015949unit NN I I/0.996169 B/0.00283111 I/0.996169 O/0.000999975..N-best outputs-n选项：使用这个选项将获得N-best结果，它根据CRF计算出的条件概率排序得到。当选择了N-best结果，CRF++会自动添加一行，形式为“# N prob”，其中N是排序后的输出结果，从0开始。prob表示output的条件概率。需要注意的是，如果CRF++不能找到足够的N条路径是，它将放弃列举N-best结果。这种情况在所给的句子很短的情况下常出现。CRF++使用前向Viterbi和后向A*搜索相结合的方法。这种结合适应了n-best结果的需求。下面是一个N-best结果的例子：% crf_test -n 20 -m model test.data# 0 0.478113Rockwell NNP B BInternational NNP I ICorp. NNP I I's POS B B...# 1 0.194335Rockwell NNP B BInternational NNP I I
最近我刚开始使用CRF工具包，里边的具体细节也没有研究明白，但论坛上有人询问工具包的使用，我就将它贴出来一下。希望和大家一起讨论讨论。另外需要说明的一点是，下面的内容是从crf工具包网页内容翻译的，可能理解上有偏差，翻译也有问题。所以还请大家指正。英文原文请大家参考网页。－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－CRFs工具包工具包地址：http://chasen.org/~taku/software/CRF++/#features，工具包包括Linux环境下的源代码和Windows下的可执行程序。用C++编写。使用方法：(1)安装编译器要求：C++编译器(gcc 3.0或更高)命令：% ./configure% make% su# make install注：只有拥有root帐号的用户才能成功安装。(2)使用(2.1)训练和测试文件的格式训练和测试文件必须包含多个tokens，每个token包含多个列。token的定义可根据具体的任务，如词、词性等。每个token必须写在一行，且各列之间用空格或制表格间隔。一个token的序列可构成一个sentence，sentence之间用一个空行间隔。最后一列是CRF用于训练的正确的标注形式。例如：He PRP B-NPreckons VBZ B-VPthe DT B-NPcurrent JJ I-NPaccount NN I-NPdeficit NN I-NPwill MD B-VPnarrow VB I-VPto TO B-PPonly RB B-NP# # I-NP1.8 CD I-NPbillion CD I-NPin IN B-PPSeptember NNP B-NP. . OHe PRP B-NPreckons VBZ B-VP..上面的例子每个token包含3列，分别为词本身、词性和Chunk标记。注意：如果每一个token的列数不一致，系统将不能正确运行。(2.2)准备特征模板使用该CRFs工具的用户必须自己确定特征模板。基本模板和宏模板文件中的每一行代表一个template。每一个template中，专门的宏%x[row,col]用于确定输入数据中的一个token。row用于确定与当前的token的相对行数。col用于确定绝对行数。如已知下面的输入数据：Input: DataHe PRP B-NPreckons VBZ B-VPthe DT B-NP << 当前的tokencurrent JJ I-NP account NN I-NP特征模板形式为：templateexpanded feature%x[0,0]the%x[0,1]DT%x[-1,0]rokens%x[-2,1]PRP%x[0,0]/%x[0,1]the/DTABC%x[0,1]123ABCthe123模板类型有两种模板类型，它们可由template的第一个字符确定。第一种是Unigram template：第一个字符是U这是用于描述unigram feature的模板。当你给出一个模板"U01:%x[0,1]"，CRF会自动的生成一个特征函数集合(func1 ... funcN)，如：func1 = if (output = B-NP and feature="U01:DT") return 1 else return 0func2 = if (output = I-NP and feature="U01:DT") return 1 else return 0func3 = if (output = O and feature="U01:DT") return 1 else return 0....funcXX = if (output = B-NP and feature="U01:NN") return 1 else return 0funcXY = if (output = O and feature="U01:NN") return 1 else return 0...一个模型生成的特征函数的个数总数为L*N，其中L是输出的类别数，N是根据给定的template扩展出的unique string的数目。第二种类型Bigram template:第一个字符是B这个模板用于描述bigram features。使用这个模板，系统将自动产生当前输出token与前一个输出token(bigram)的组合。产生的可区分的特征的总数是L*L*N，其中L是输出类别数，N是这个模板产生的unique features数。当类别数很大的时候，这种类型会产生许多可区分的特征，这将会导致训练和测试的效率都很低下。使用标识符区分相对位置如果用户需要区分token的相对位置时，可以使用标识符。比如在下面的例子中，宏"%x[-2,1]"和"%x[1,1]"都代表“DT”，但是它们又是不同的“DT“。The DT B-NPpen NN I-NPis VB B-VP << CURRENT TOKENa DT B-NP为了区分它们，可以在模型中加入一个唯一的标识符(U01: 或 U02:)，即：U01:%x[-2,1]U02:%x[1,1]在这样的条件下，两种模型将被认为是不同的，因为他们将被扩展为”U01:DT“和”U02:DT”。只要你喜欢，你可以使用任何标识符，但是使用数字序号区分更很有用，因为它们只需简单的与特征数相对应。例子：下面是用于CoNLL2000中shared task和Base-NP chunking task的模板实例。只使用了bigram template B。这意味着前一个output token和current token将组合成bigram features。每个以#起始的一行或者是空行都会被当作注释去掉。# UnigramU00:%x[-2,0]U01:%x[-1,0]U02:%x[0,0]U03:%x[1,0]U04:%x[2,0]U05:%x[-1,0]/%x[0,0]U06:%x[0,0]/%x[1,0]U10:%x[-2,1]U11:%x[-1,1]U12:%x[0,1]qU13:%x[1,1]U14:%x[2,1]U15:%x[-2,1]/%x[-1,1]U16:%x[-1,1]/%x[0,1]U17:%x[0,1]/%x[1,1]U18:%x[1,1]/%x[2,1]U20:%x[-2,1]/%x[-1,1]/%x[0,1]U21:%x[-1,1]/%x[0,1]/%x[1,1]U22:%x[0,1]/%x[1,1]/%x[2,1]# BigramB(3)训练（编码）使用crf_learn 命令：% crf_learn template_file train_file model_file其中，template_file和train_file需由使用者事先准备好。crf_learn将生成训练后的模型并存放在model_file中。一般的，crf_learn将在STDOUT上输出下面的信息。还会输出其他的和LBFGS迭代相关的信息。% crf_learn template_file train_file model_fileCRF++: Yet Another CRF Tool KitCopyright (C) 2005 Taku Kudo, All rights reserved.reading training data: Done! 0.32 sNumber of sentences: 77Number of features: 32856Freq: 1eta: 0.0001C(sigma^2): 10iter=0 terr=0.7494725738 serr=1 obj=2082.968899 diff=1iter=1 terr=0.1671940928 serr=0.8831168831 obj=1406.329356 diff=0.3248438053iter=2 terr=0.1503164557 serr=0.8831168831 obj=626.9159973 diff=0.5542182244其中：iter：迭代次数terr：和tags相关的错误率(错误的tag数/所有的tag数)serr：与sentence相关的错误率（错误的sentence数/所有的sentence数）obj：当前对象的值。当这个值收敛到一个确定的值是，CRF模型将停止迭代diff：与上一个对象值之间的相对差有两个主要的参数用于控制训练条件：-c float：使用这个选项，你可以改变CRF的hyper-parameter。当取一个极大的C值，CRF将可能对训练数据产生过拟合（overfitting）现象。这个参数将会调节overfitting和underfitting之间的平衡。结果将会对参数带来有意义的影响。使用者可以通过使用held-out data或者更多的通用模型的选择方法如十字交叉验证法(cross validation)获得最有的值。-f NUM：这个参数用于设置特征的cut-off阈值。CRF++训练时只使用出现次数不少于NUM次数的特征进行训练。默认值为1。当使用CRF++训练大规模数据时，单一特征的数量将达到数百万，此时选择这个参数很有用。这里有一个使用这两个参数的例子：% crf_learn -f 3 -c 1.5 template_file train_file model_file(4)测试（解码）使用crf_test 命令：% crf_test -m model_file test_files ...其中，model_file是crf_learn创建的。在测试过程中，使用者不需要指定template file，因为，mode file已经有了template的信息。test_file是你想要标注序列标记的测试语料。这个文件的书写格式应该与训练文件一致。下面是一个crf_test输出的例子：% crf_test -m model test.dataRockwell NNP B BInternational NNP I ICorp. NNP I I's POS B BTulsa NNP I Iunit NN I I..其中，最后一列是模型估计的tag。如果第三列是标准的tag，则可以通过简单的比较第三列和第四列之间的差别计算出准确率。详细的层次（verbose level）-v选项：将设置verbose level。默认值为0。通过增加层次，你可以从CRF++获得额外的信息。层次1：你可以对每个tag使用边缘概率(marginal probabilities)（这是一种对输出tag的confidence measure），对输出使用条件概率(conditional probably)（针对整个输出的confidence measure）。例如：% crf_test -v1 -m model test.data| head# 0.478113Rockwell NNP B B/0.992465International NNP I I/0.979089Corp. NNP I I/0.954883's POS B B/0.986396Tulsa NNP I I/0.991966...其中，第一行的"# 0.478113"即是输出的条件概率，而且每一个输出tag各自含有一个概率，表示形式如“B/0.992465”。层次2：你可以对所有的其他候选求边缘概率。例如：% crf_test -v2 -m model test.data# 0.478113Rockwell NNP B B/0.992465 B/0.992465 I/0.00144946 O/0.00608594International NNP I I/0.979089 B/0.0105273 I/0.979089 O/0.0103833Corp. NNP I I/0.954883 B/0.00477976 I/0.954883 O/0.040337's POS B B/0.986396 B/0.986396 I/0.00655976 O/0.00704426Tulsa NNP I I/0.991966 B/0.00787494 I/0.991966 O/0.00015949unit NN I I/0.996169 B/0.00283111 I/0.996169 O/0.000999975..N-best outputs-n选项：使用这个选项将获得N-best结果，它根据CRF计算出的条件概率排序得到。当选择了N-best结果，CRF++会自动添加一行，形式为“# N prob”，其中N是排序后的输出结果，从0开始。prob表示output的条件概率。需要注意的是，如果CRF++不能找到足够的N条路径是，它将放弃列举N-best结果。这种情况在所给的句子很短的情况下常出现。CRF++使用前向Viterbi和后向A*搜索相结合的方法。这种结合适应了n-best结果的需求。下面是一个N-best结果的例子：% crf_test -n 20 -m model test.data# 0 0.478113Rockwell NNP B BInternational NNP I ICorp. NNP I I's POS B B...# 1 0.194335Rockwell NNP B BInternational NNP I I
