CRF工具包使用简介.doc

CRF工具包使用简介最近我刚开始使用CRF工具包，里边的具体细节也没有研究明白，但论坛上有人询问工具包的使用，我就将它贴出来一下。希望和大家一起讨论讨论。另外需要说明的一点是，下面的内容是从crf工具包网页内容翻译的，可能理解上有偏差，翻译也有问题。所以还请大家指正。英文原文请大家参考网页。CRFs工具包工具包地址：/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工具的用户必须自己确定特征模板。基本模板和宏l模板文件中的每一行代表一个template。每一个template中，专门的宏%xrow,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%x0,0the%x0,1DT%x-1,0rokens%x-2,1PRP%x0,0/%x0,1the/DTABC%x0,1123ABCthe123模板类型l有两种模板类型，它们可由template的第一个字符确定。第一种是Unigram template：第一个字符是U这是用于描述unigram feature的模板。当你给出一个模板U01:%x0,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数。当类别数很大的时候，这种类型会产生许多可区分的特征，这将会导致训练和测试的效率都很低下。使用标识符区分相对位置l如果用户需要区分token的相对位置时，可以使用标识符。比如在下面的例子中，宏%x-2,1和%x1,1都代表“DT”，但是它们又是不同的“DT“。The DT B-NPpen NN I-NPis VB B-VP CURRENT TOKENa DT B-NP为了区分它们，可以在模型中加入一个唯一的标识符(U01: 或 U02:)，即：U01:%x-2,1U02:%x1,1在这样的条件下，两种模型将被认为是不同的，因为他们将被扩展为”U01:DT“和”U02:DT”。只要你喜欢，你可以使用任何标识符，但是使用数字序号区分更很有用，因为它们只需简单的与特征数相对应。例子：下面是用于CoNLL2000中shared task和Base-NP chunking task的模板实例。只使用了bigram template B。这意味着前一个output token和current token将组合成bigram features。每个以#起始的一行或者是空行都会被当作注释去掉。# UnigramU00:%x-2,0U01:%x-1,0U02:%x0,0U03:%x1,0U04:%x2,0U05:%x-1,0/%x0,0U06:%x0,0/%x1,0U10:%x-2,1U11:%x-1,1U12:%x0,1qU13:%x1,1U14:%x2,1U15:%x-2,1/%x-1,1U16:%x-1,1/%x0,1U17:%x0,1/%x1,1U18:%x1,1/%x2,1U20:%x-2,1/%x-1,1/%x0,1U21:%x-1,1/%x0,1/%x1,1U22:%x0,1/%x1,1/%x2,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(sigma2): 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 Is 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.954883s 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.040337s 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 Is POS B B.# 1 0.194335Rockwell NNP B BInternational NNP I I按照manual的解释，Bigram B生成一个当前tag和前一个tag的组合特征，但是，问题在于当前tag还没有得到，如何解释这个组合？如果想采用前一个的输出为特征，该怎么表示？以上面的template为例，俺曾经试过U22:%x-1,2，结果报错。想请问一下，如果要采用前一个或前面若干个的预测结果作为当前对象的特征，该怎么写模板？ 我没有使用过CRF工具，但我同样遇到过Helen提出的问题，即如何使用前一个token的输出结果作为当前token的特征的问题。我记的当时我的解决方法是：一：之前我使用过最大熵，最大熵工具包有这样一个接口可以获得前一个token的输出结果。二：穷举发。比较笨，但还挺好用的。仍以上文的例子为例：/Input: DataRockwell NNP BInternational NNP ICorp. NNP Is POS B 当前的tokenTulsa NNP Iunit NN I词 词性 前一个输出 当前输出/训练语料：你只需最后再加入一列和前一个token的第三列一样的。这样第三列就可以认为是前一个token的输出结果作为了当前token的一个特征。我想你说的U22:%x-1,2报错，是因为CRF默认为最后一列是标准输出，不允许作为输入特征使用，只要加入一列就不会有这样的问题了。输入变为：/Input: DataInput: DataRockwell NNP Null BInternational NNP B ICorp. NNP I Is POS I B 当前的tokenTulsa NNP B Iunit NN I I词 词性 前一个输出 当前输出/测试语料：因为测试时CRF应该是对整个句子的token输出序列有个全局最优算法，所以要使用前一个token的输出比较难。我们可以使用穷举法，假设前一个token的可能输出，算出当前输出概率。这样可能需要等同于输出类别个数的模板/Input: DataRockwell NNP Null Null Null BInternational NNP B I O ICorp. NNP B I O Is POS B I O B 当前的tokenTulsa NNP B I O Iunit NN B I O I词 词性 前一个可能输出（穷举） 当前输出/三个模板分别U22:%x-1,3；U22:%x-1,4；U22:%x-1,5三个测试后的输出分别代表前一个是B是I是O时当前的输出。需要注意的是句首词的前一个输出为NULL，它是无需进行选择的。如此一来，我们依据句首条件概率最大的输出来决定第二个词选择哪个模板（若句首输出为B选择模板一的结果，若为I选择模板二的输出结果，若为O悬在模板三的输出结果）来获得的当前输出作为当前的输出值，依次下推。就可以获得输出序列。此方法较笨，需要自己做一个后处理程序，在没有前一个特征输出接口时，使用此法比较实用，我用过效果还不错 :) 多谢佳佳回复。在构造训练数据时采用此方法添加前一个输出结果，的确是个好办法。但仍有一些问题，讨论如下：1. “三个模板分别U22:%x-1,3；U22:%x-1,4；U22:%x-1,5” 是否应该是：“U22:%x-1,2；U22:%x-1,3；U22:%x-1,4” ？这样是否在训练语料中也列写这三个特征（即增加3列）？2.“依据句首条件概率最大的输出来决定第二个词选择哪个模板”这句话不理解。比如，上一句概率最大的输出结果为I，若下一句要想使用上一句的输出结果作为特征，则下一句应该使用模板U22:%x-1,3（对应上一句的特征I），但由于列举了三个模板（分别对应BIO），模型应该全部使用它们而不具备选择功能吧；如果具备选择功能（比如此例中选择I对应的模板U22:%x-1,3），是如何实现的呢？3.如果在测试语料中列举上一句所有可能的输出（BIO三列），而训练语料中只包含上一句正确的输出（一列），这样训练数据和测试数据的格式是不是不一致？模型是否接受？1.我没有注意列数是从0开始的，三个模板应该是“U22:%x-1,2；U22:%x-1,3；U22:%x-1,4” 。我觉得你说得很对，CRF提供的工具包在测试的时候无需再提供模板文件，这和我使用的最大熵工具有所不同。为了保证训练与测试模板的一致性，不能采用不同模板文件的方式，因此训练与测试文件格式也应该是一致的。我想是否可以让训练语料和测试语料格式一样，训练语料也加入三列，三列都是前一个输出特征？这样我们可以使用三个不同的temp1(U22:%x-1,2)、temp2(U22:%x-1,3)、temp3(U22:%x-1,4)模板文件训练三个其实一样的模型，仅仅是模板文件不同，但特征内容在训练语料中提取出来是一样的，而训练的模型应该相同。但在测试阶段，使用三个模型获得的测试特征有所不同，分别是假设前一个输出是BIO时当前token的输出。例如：train.txt/Input: DataRockwell NNP Null Null Null BInternational NNP B B B ICorp. NNP I I I Is POS I I I B 当前的tokenTulsa NNP B B B Iunit NN I I I词 词性 前一个输出 当前输出/测试语料：test.txt/Input: DataRockwell NNP Null Null Null BInternational NNP B I O ICorp. NNP B I O Is POS B I O B 当前的tokenTulsa NNP B I O Iunit NN B I O I词 词性 前一个可能输出（穷举） 当前输出/训练% crf_learn temp1 train.txt model1% crf_learn temp2 train.txt model2% crf_learn temp3 train.txt model3测试% crf_test -v2 -m model1 test1.txt% crf_test -v2 -m model2 test2.txt% crf_test -v2 -m model3 test3.txt此时，model1model2model3相同，获得的test1,test2,test3分别对应假设前一个特征为BIO获得的输出结果2.“依据句首条件概率最大的输出来决定第二个词选择哪个模板”的意思是指句首的前一个输出都是null，三个模板的句首token输出结果应该都一样，假设句首输出都为B,那么我们第二个token就应该使用test1(对应B)中第二个token的输出结果，假设是I，那么第三个token就应该使用test2(对应I)的输出结果，依次类推。3.格式应该是一致的，因为默认测试与训练模板相同，这个我开始没有注意到.另外，这个方法比较麻烦，不知道有没有比较了解CRF的人，如果有相关接口就容易得多了。最大熵就提供前一个输出结果的接口，很好使用。决策树的计算原理决策树对比神经元网络的优点在于可以生成一些规则。 当我们进行一些决策，同时需要相应的理由的时候，使用神经元网络就不行了。 这里介绍三个算法 CART,CHAID,C4.5。 决策树是如何工作的 决策树一般都是自上而下的来生成的。 选择分割的方法有好几种，但是目的都是一致的：对目标类尝试进行最佳的分割。 从根到叶子节点都有一条路径，这条路径就是一条“规则”。 决策树可以是二叉的，也可以是多叉的。 对每个节点的衡量： 1) 通过该节点的记录数 2) 如果是叶子节点的话，分类的路径 3) 对叶子节点正确分类的比例。 有些规则的效果可以比其他的一些规则要好。 决策树对于常规统计方法的优点。 CART Diversity(整体)-diversity(左节点)-diversity(右节点)，值越大，分割就越好。 三种diversity的指标： 1. min(P(c1),P(c2) 2. 2P(c1)P(c2) 3. P(c1)logP(c1)+P(c2)logP(c2) 这几个参数有相同的性质：当其中的类是均匀分布的时候，值最大；当有一个类的个数为0的时候，值为0。 选择分割的时候，对每个字段都考虑；对每个字段中的值先排序，然后再一一计算。最后选出最佳的分割。 树的生成： 错误率的衡量：最初生成的树中也是有错误率的！因为有些叶子节点并不是“Pure”的。 树的修剪：是不是当所以的叶子都很纯是，这棵树就能工作的很好呢? 修剪的要点是：应该回溯多少、如何从众多的子树总寻找最佳的。 1) 鉴别生成候选子树 ：使用一个调整的错误率。AE(T)=E(T)+aleaf_count(T)。一步步的生成一些候选子树。 2) 对子树的评估：通过test set找到最佳子树 3) 对最佳子树进行评估：使用evaluation set。 4) 考虑代价(cost)的问题。 C4.5 C4.5是从ID3演变而来的。 C4.5和CART的区别: 1) 树的生成方面。 C4.5不一定使用两分法。C4.5处理种类变量的时候，缺省的情况是每个值作为一个分支。 Gain 和gain ratio。 2) 树的修剪 C4.5使用原来的数据进行测试。(学院派) 规则的生成 CHAID 1975年 和CART和C4.5的区别： 1. 在overfitting之前就停止树的生长。 2. 必须都是