Introduction To Conditional Random Fields.ppt

1、Introduction To Conditional Random Fields,Presentation by Yanbing Yu Oct.12, 2006,Outline,Why do we choose crf ?What is crf ?How to apply it ?,Application,HMM,joint probability,Disadvantages,Need to enumerate all possible observation sequencesNot practical to represent multiple interacting features

2、or long-range dependencies of the observationsVery strict independence assumptions on the observations,MEMM,Exponential modelGiven training set X with label sequence Y:Train a model that maximizes P(Y|X, )For a new data sequence x, the predicted label y maximizes P(y|x, )Notice the per-state normali

3、zation,MEMM,Disadvantages,per-state normalization,Global normalizationCRFs,Label bias problem,CRFs,Represent multiple interacting features or long-range dependencies of the observations,Solve the label bias problem,Comparison,HMM MEMM CRF,kuai ji shi,hui,会 计 师,Outline,Why do we choose crf ?What is c

4、rf ？How to apply it ？,Random Fields,Definition of CRFs,Conditional Distribution,If the graph G = (V, E) of Y is a tree, the conditional distribution over the label sequence Y = y, given X = x, by fundamental theorem of random fields is:,Z(x) is a normalization over the data sequence x,Outline,Why do

5、 we choose crf ?What is crf ?How to apply it ?,Experiment,Data sourceA CTP conversion on one years Peoples Daily of 1998 to prepare the corpus used in our experiments. SentencesThis experiment is based on 50,000 sentences with 746,761 couples of Chinese character and pinyin. 40000 of them are used t

6、o train and the left 10000 are used to test.,Format of Corpus,Traintou 投 biao 标 ， ，shen 申 qing 请 。 。Testshi shi 十yi yi 亿， ， ，OR ren ren 人min min 民。 。 。,How to train ?,Expectation: Correct tag sequence,Training Set xi, yi,Optimizing Goal,shi jie bei guan jun gui lai世 界 杯 冠 军 归 来,Example:x,y,Example,T

7、rain sentence:,shi jie bei guan jun gui lai世 界 杯 冠 军 归 来,x,y,Process:,Feature Extraction,LBFGS Optimization,Gradient Calculation,shi jie bei guan jun gui lai世 界 杯 冠 军 归 来,x,y,师 姐 悲 观 军 规 赖 使 节 被 官 军 贵 来 。,Template,U00:%x-2,0,U01:%x-1,0,U02:%x0,0,U03:%x1,0,U04:%x2,0,U05:%x-1,0/%x0,0,U06:%x0,0/%x1,0,U

8、00:shi:,U01:jie:,U02:bei:,U03:guan:,U04:jun:,U05:jie/bei:,U06:bei/guan:,Vertex Features,Weight,Sentence,Feature Extraction,shi jie bei guan jun gui lai世 界 杯 冠 军 归 来,x,y,Template,B00:%x-2,0,B01:%x-1,0,B02:%x0,0,B03:%x1,0,B04:%x2,0,B05:%x-1,0/%x0,0,B06:%x0,0/%x1,0,B00:shi:,B01:jie:,B02:bei guan:,B03:j

9、un:,B04:gui:,B05:jie/bei guan:,B06:bei guan/jun:,Edge Features,Weight,师 姐 悲 观 军 规 赖 使 节 被 官 军 贵 来 。,Sentence,Feature Extraction,B06:bei guan/jun:,Gradient Calculation,Lattice,shi jie bei guan jun gui lai,Gradient Calculation,Forward-Backward The goal is to get Z(x) and calculate the expectationViter

10、biGet the best optimizing path,Three parametresx Current weight vectorg Gradient (expectation)f Optimizing goal,LBFGS Optimization,Maximize,Some training weights,Org: 许多文艺理论家看到前人所建立的理论体系的不足， result: 许多文艺理论家看到前人所建立的理论体系的不足，(对:23,错:0)Org: 今天的会议向委员们印发了关于召开第六届全国人民代表大会第五次会议的决定草案， result: 今天的会议向委员们印发了关于召开

11、第六届全国人民代表大会第五次会议的决定草案，(对:38,错:0)Org: 在年制定的暂行海关法的基础上修改制定海关法是必要的， result: 在年制定的暂行海关法的基础上修改制定海关法是必要的，(对:30,错:0)Org: 本着逐步实现农村基层社会生活的直接民主的指导思想起草的。 result: 本着逐步实现农村基层社会生活的直接民主的指导思想起草的。(对:28,错:0)Org: 技术合同法是适应我国经济体制改革和科学技术体制改革的需要， result: 技术合同法是适应我国经济体制改革和科学技术体制改革的需要，(对:29,错:0)Org: 中央政治局常委、国务院总理赵紫阳今天下午在中南海会

12、见部分科技工作者时强调， result: 中央政治局常委、国务院总理赵紫阳今天下午在中南海会见部分科技工作者时强调，(对:37,错:0)Org: 办一切事情都要发扬艰苦创业、艰苦奋斗的精神， result: 办一切事情都要发扬艰苦创业、艰苦奋斗的精神，(对:22,错:0)Org: 我们国家十分重视发展各类教育事业， result: 我们国家十分重视发展各类教育事业，(对:17,错:0)Org: 我们要大力提倡和鼓励在生产实践中自修成才、自学成才。 result: 我们要大力提倡和鼓励在生产实践中自修成才、自学成才。(对:26,错:0)Org: 我国绝大多数知识分子、科技人员都在思考这样一个问题

13、：珍惜来之不易的大好局面， result: 我国绝大多数知识分子、科技人员都在思考这样一个问题：珍惜来之不易的大好局面，(对:38,错:0)Org: 旗帜鲜明地反对资产阶级自由化。 result: 旗帜鲜明地反对资产阶级自由化。(对:15,错:0)Org: 努力把自己培养锻炼成有理想、有道德、有文化、有纪律的人才， result: 努力把自己培养锻炼成有理想、有道德、有文化、有纪律的人才，(对:29,错:0),Some result,Org: 坚决支持阿拉伯国家和人民反对以色列侵略扩张、恢复合法民族权利的正义斗争。 result: 坚决支持阿拉伯国家和人民反对以色列侵略扩张、恢复合法民族权利的

14、正义斗争。(对:36,错:0)Org: 顺利完成减少军队员额一百万的战略计划， result: 顺利完成减少军队员额一百万的战略计划，(对:19,错:0)Org: 必须尽一切努力通过政治途径和谈判解决柬埔寨问题。 result: 必须尽一切努力通过政治途径和谈判解决柬埔寨问题。(对:24,错:0)Org: 让柬埔寨人民在没有任何外来干涉的情况下自行解决自己的内部问题。 result: 让柬埔寨人民在没有任何外来干涉的情况下自行解决自己的内部问题。(对:31,错:0)Org: 这里呼吁国际社会更加有效地援助南非人民反对种族隔离的斗争。 result: 这里呼吁国际社会更加有效地援助南非人民反对种

15、族隔离的斗争。(对:29,错:0)Org: 以便结束在黎巴嫩的巴勒斯坦难民营地区发生的冲突。 result: 以便结束在黎巴嫩的巴勒斯坦难民营地区发生的冲突。(对:24,错:0)Org: 自去年月底黎巴嫩什叶派“阿迈勒运动”民兵和巴勒斯坦民兵发生难民营冲突以来， result: 自去年月底黎巴嫩什叶派“阿迈勒运动”民兵和巴勒斯坦民兵发生难民营冲突以来，(对:38,错:0)Org: 伊拉克军方发言人日否认了伊朗方面所说的大批伊拉克飞机被击落的说法。 result: 伊拉克军方发言人日否认了伊朗方面所说的大批伊拉克飞机被击落的说法。(对:35,错:0),Some result,Org: 把当代世界

16、各国包括资本主义发达国家的先进的科学技术、具有普遍适用性的经济行政管理 result: 把当代世界各国包括资本主义发达国家的先进的科学技术、具有普遍适用性的经济行政管理(对:40,错:0)Org: 我国电力工业在电力生产和建设上进行了许多改革， result: 我国电力工业在电力生产和建设上进行了许多改革，(对:23,错:0)Org: 电力工业的发展仍然满足不了国民经济和人民生活的需要。 result: 电力工业的发展仍然满足不了国民经济和人民生活的需要。(对:26,错:0)Org: “七五”期间全国新增装机容量达三千五百万至四千万千瓦， result: “七五”期间全国新增装机容量达三千五百

17、万至四千万千瓦，(对:27,错:0)Org: 比“六五”期间增长八十一点六亿元；投产容量达五百万千瓦以上， result: 比“六五”期间增长八十一点六亿元；投产容量达五百万千瓦以上，(对:30,错:0)Org: 电力基本建设全面实行工程项目投产包干、招标、承包等办法。 result: 电力基本建设全面实行工程项目投产包干、招标、承包等办法。(对:30,错:0)Org: 他们通过各种渠道引进技术、优良品种， result: 他们通过各种渠道引进技术、优良品种，(对:18,错:0)Org: 建立了一批以热带、亚热带作物为主的商品生产基地。 result: 建立了一批以热带、亚热带作物为主的商品生

18、产基地。(对:24,错:0)Org: 宣传西瓜价格开放政策和市场需求量， result: 宣传西瓜价格开放政策和市场需求量，(对:17,错:0)Org: 亩产由原来的四百多公斤上升到五百五十多公斤， result: 亩产由原来的四百多公斤上升到五百五十多公斤，(对:22,错:0),Some result,Result.txt,Feature space,Relations between feature space size and corpus size,Fig. 1. Relation between the number of features and sentences. The to

19、p line describes the case of building feature spaces with an extern dictionary, and the bottom dashed line without the extern dictionary.,Feature space,Distribution of feature occurrence,Fig. 2. Distribution of feature occurrence. From the top down, lines represent feature spaces built from 100, 60,

20、 30 and 10 thousand sentences with dictionary for both of the two figures. Picture (a) illustrates the number of features which occur no more than some certain times, while picture (b) exactly some certain times.,(a),(b),Feature space,Distribution of feature weights,Fig. 3. Distribution of feature w

21、eight. The model is trained on 40,000 sentences.,Result,Relation between testing accuracy and removing boundary,Fig. 4. Relation between testing accuracy and removing boundary. The original model is trained on 40,000 sentences. The straight line indicates removing features that has a weight value less than boundary, while the dashed line greater than boundary.,Fig. 5. Training and Testing result with different corpuses.,Result,Thank you for your attention !,