Scaling Conditional Random Fields for Natural Language Processing

《Scaling Conditional Random Fields for Natural Language Processing》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、ScalingConditionalRandomFieldsforNaturalLanguageProcessingTrevorA.CohnSubmittedintotalfulfilmentoftherequirementsofthedegreeofDoctorofPhilosophyJanuary,2007DepartmentofComputerScienceandSoftwareEngineeringFacultyofEngineeringUniversityofMelbourneAbstractThisthesisdealswiththeuseofConditionalRandom

2、Fields(CRFs;Laffertyetal.(2001))forNaturalLanguageProcessing(NLP).CRFsareprobabilisticmodelsforsequencelabellingwhichareparticularlywellsuitedtoNLP.Theyhavemanycompellingadvan-tagesoverotherpopularmodelssuchasHiddenMarkovModelsandMaximumEntropyMarkovModels(Rabiner,1990;McCallumetal.,2001),andhaveb

3、eenappliedtoanum-berofNLPtaskswithconsiderablesuccess(e.g.,ShaandPereira(2003)andSmithetal.(2005)).Despitetheirapparentsuccess,CRFssufferfromtwomainfailings.Firstly,theyoftenover-fitthetrainingsample.Thisisaconsequenceoftheirconsiderableexpres-sivepower,andcanbelimitedbyaprioroverthemodelparameters

4、(ShaandPereira,2003;PengandMcCallum,2004).TheirsecondfailingisthatthestandardmethodsforCRFtrainingareoftenveryslow,sometimesrequiringweeksofprocessingtime.Thisefficiencyproblemislargelyignoredincurrentliterature,althoughinpractisethecostoftrainingpreventstheapplicationofCRFstomanynewmorecomplextask

5、s,andalsopreventstheuseofdenselyconnectedgraphs,whichwouldallowformuchricherfeaturesets.Thisthesisaddressestheissueoftrainingefficiency.Firstly,wedemonstratethattheasymptotictimecomplexityofstandardtrainingforalinearchainCRFisquadraticinthesizeofthelabelset,linearinthenumberoffeaturesandalmostquadr

6、aticinthesizeofthetrainingsample.Thecostofinferenceincyclicgraphs,suchaslatticestructuredDynamicCRFs(Suttonetal.,2004),isevengreater.ThecomplexityoftraininglimitstheapplicationofCRFstolargeandcomplextasks.Wecomparetheaccuracyofanumberofpopularapproximatetrainingtechniques,whichcangreatlyreducethe

7、trainingcost.However,formosttasksthissavingiscoupledwithasubstantiallossinaccuracy.Forthisreasonweproposetwonoveltrainingmethods,whichbothreducetheresourcerequirementsandimprovethescalabilityoftraining,suchthatCRFscanb