《信息抽取2.ppt》由会员分享,可在线阅读,更多相关《信息抽取2.ppt(53页珍藏版)》请在三一文库上搜索。
1、1,信息抽取(2),Information Extraction (IE),2,IE,什么是信息抽取 IR和IE 面对的工作和IE模型 IE体系结构,3,Wrapper Induction,4,Wrapper,分装器 ,包装器 是一个程序,用于从特定的信息源中抽取相关内容,并以特定形式加以表示。 由一系列的抽取规则以及应用这些规则的计算机程序代码组成。,5,基于Wrapper方法的信息抽取,6,wrapper的构造方式,手工生成 半自动生成 自动生成,7,Wrapper Induction,归纳学习算法 是一种通过分析一个未知的集合中的某些遵循某种规律的实例集合,归纳出一般性的规则,并利用这些
2、规则来推知该集合的其他部分的方法。,8,Wrapper Induction,a technique for automatically constructing wrappers from labeled examples of a resources content.,9,Wrapper induction: Delimiter-based extraction,Some Country Codes Congo 242 Egypt 20 Belize 501 Spain 34 ,Use , , , for extraction,10,Learning LR wrappers,l1, r1,
3、, lK, rK,wrapper,Example: Find 4 strings , , , l1 , r1 , l2 , r2 ,labeled pages,11,: datai-1与datai 之间字符串的后缀 : datai与datai+1之间字符串的前缀,12,LR: Finding r1,Some Country Codes Congo 242 Egypt 20 Belize 501 Spain 34 ,r1 can be any prefix eg ,13,LR: Finding l1, l2 and r2,Some Country Codes Congo 242 Egypt 20
4、 Belize 501 Spain 34 ,r2 can be any prefix eg ,l2 can be any suffix eg ,l1 can be any suffix eg ,14,A problem with LR wrappers,Distracting text in head and tail Some Country Codes Some Country Codes Congo 242 Egypt 20 Belize 501 Spain 34 End,15,One (of many) solutions: HLRT,Ignore pages head and tai
5、l Some Country Codes Some Country Codes Congo 242 Egypt 20 Belize 501 Spain 34 End,head,body,tail,start of tail,end of head,16,Extraction,HLRT wrapper as a vector Web pages as Example, output tuples as Label, ExecHLRT() as a Hypothesis function,17,Induction,18,Induction as search,Search the hypothes
6、is space,19,Induction as search,Generate-andtest Depth-first search, 2K+2 levels for wrapper vector,20,隐马尔可夫模型 Hidden Markov model (HMM),21,Generating Patterns,生成模型是指在数据预处理基础上通过神经元网络、回归分析等数据建模算法从训练样本集中提炼出数据模型.,22,Generating Patterns,确定性的生成模型,23,Generating Patterns,非确定性的生成模型,24,Markov过程与Markov链,Marko
7、v过程:具有无后效性的随机过程。即t时刻所处状态的概率只和t-1时刻的状态有关,而与t-1时刻之前的状态无关。 Markov链:时间离散,状态离散的马尔可夫(Markov)过程。,25,Markov链的参数,转移概率:A=akl=P(i=l|i-1=k) 初始概率:,26,Markov链的例子,Sun(状态1),Rain(状态3),Cloudy(状态2),State transition matrix,Initial Distribution,States,Sun Cloud Rain ( 0.0 0.0 1.0 ),27,Markov链的例子,设第一天(t=1)是雨,问题:根据这个模型,在以
8、后的7天里天气是“雨-雨-晴-晴-雨-多云-雨” 的概率是多少? 说得更抽象些,令对应t=1,2,8观察序列为O= ,28,29,Hidden Markov Models-HMM,HMM是一个双重随机过程,两个组成部分: 马尔可夫链:描述状态的转移,用转移概率描述。 一般随机过程:描述状态与观察序列间的关系, 用观察值概率描述。,30,HMM组成,Markov链 (, A),随机过程 (B),状态序列,观察值序列,q1, q2, ., qT,o1, o2, ., oT,HMM的组成示意图,31,HMM,Graphical Model Representation: Variables by t
9、ime Circles indicate states Arrows indicate probabilistic dependencies between states,32,HMM,Green circles are hidden states Dependent only on the previous state: Markov process “The past is independent of the future given the present.”,33,HMM,Purple nodes are observed states Dependent only on their
10、 corresponding hidden state,34,HMM的基本要素,N,M, , A, B N : s1sN are the values for the hidden states M : k1kM are the values for the observations,S,S,S,K,K,K,S,K,S,K,35,HMM的基本要素,N, M, , A, B = pi are the initial state probabilities A = aij are the state transition probabilities B = bik are the observat
11、ion state probabilities,A,B,A,A,A,B,B,S,S,S,K,K,K,S,K,S,K,36,HMM的应用,(1) 评估 根据已知的HMM找出一个观察序列的概率 (2) 解码 根据观察序列找到最有可能出现的隐状态序列 (3) 学习 从观察序列中得出HMM,37,HMM应用(1),给定观察序列O=O1,O2,OT,以及模型 , 计算P(O|),o1,ot,ot-1,ot+1,38,HMM应用(1),39,Forward Procedure,定义前向变量 初始化: 递归: 终结:,40,Forward Procedure,41,Forward Procedure,42,
12、Backward Procedure,定义后向变量 初始化: 递归: 终结:,43,Backward Procedure,oT,o1,ot,ot-1,ot+1,x1,xt+1,xT,xt,xt-1,44,HMM的应用,(1) 评估 根据已知的HMM找出一个观察序列的概率 (2) 解码 根据观察序列找到最有可能出现的隐状态序列 (3) 学习 从观察序列中得出HMM,45,HMM的应用(2) Viterbi Algorithm,目的:给定观察序列O以及模型, 选择一个对应的状态序列S ,使得S能够最为合理的解释观察序列O 我们所要找的,就是T时刻最大的 所代表的那个状态序列,46,Viterbi
13、Algorithm,x1,xt-1,xt,xt+1,47,Viterbi Algorithm,x1,xt-1,xt,xt+1,xT,48,HMM的应用,(1) 评估 根据已知的HMM找出一个观察序列的概率 (2) 解码 根据观察序列找到最有可能出现的隐状态序列 (3) 学习 从观察序列中得出HMM,49,HMM的应用(3) Baum-Welch算法(模型训练算法),目的:给定观察值序列O,通过计算确定一个模型 l , 使得P(O| l)最大。 算法步骤: 1. 初始模型(待训练模型) l0, 2. 基于l0 以及观察值序列O,训练新模型 l; 3. 如果 log P(X|l) - log(P(X|l0) Delta,说明训练已经达到预期效果, 算法结束。 4. 否则,令l0 l ,继续第2步工作,50,Baum-Welch算法,定义:,51,Baum-Welch算法,参数估计:,52,HMM的应用领域,语音识别 机器视觉 人脸检测 机器人足球 图像处理 图像去噪 图像识别 生物医学分析 DNA/蛋白质序列分析,53,The End! Thank you!,
链接地址:https://www.31doc.com/p-2844189.html