CYK算法
Cocke-Younger-Kasami algorithm 基于非活性线图的、以乔姆斯基范式为描述对象的并行句法分析算法。CYK算法是Cocke-Younger-Kasami算法的缩写
CYK－1表面印刷设备智能控制器
某人名字的缩写
我这是用STC做的，应该很容易移植到MPS430上的给你参考一下。#include<reg52.h>
#include<intrins.h>
#define uchar unsigned char
#define uint unsigned int
sbit scl=P1^3
sbit sda=P1^4
sbit key1=P1^6
sbit key2=P1^7
sbit key3=P2^0
sbit key4=P2^1
sbit lcrs=P3^7//数据/命令
sbit lcwr=P3^5//读/写
sbit lcden=P3^4//使能
sbit DS=P2^2
/*sbit lcrs=P3^4//数据/命令
sbit lcwr=P3^7//读/写
sbit lcden=P3^5//使能
*/
sbit jrk=P2^2
sbit cyk=P2^3
sbit xhk=P2^4
bit flag=0,rsg=0,not=0,he=0,in=0
int acon=0,bcon=0,dcon=0,econ=0,
temp=0,y=0,j=0,l=0,cfj=0,ec=0,dc=0,at
uchar code table[]={48,49,50,51,52,53,54,55,56,57}
uchar code ta1[]={"Temperature UP"}
uchar code ta2[]={"Temperature DN"}
uchar code ta3[]={"Inflator Cycle"}
uchar code ta4[]={"Inflator Time "}
uchar code ta5[]={" Heating UP "}
uchar code ta6[]={"Inflator"}
uchar code table7[]={"Temperature"}
uchar table1[]={0,0,0,'.',0}
uchar table3[]={"AptitudeAquarium"}
uchar table4[]={0,0,0,0,0}
uchar n,c=0
void delay(uchar)
void wen_kong()
void xh()
void rso()
void weno()
void Init_Com(void)
{
TMOD = 0x11
PCON = 0x00
TH1=0x61
TL1=0x99
EA=1
ET1=1
TR1=1
}
void delay(uchar count) //delay
{
uint i
while(count)
{
i=200
while(i>0)
i--
count--
}
}
////初始化18B20/////////
bit init18b20(void)
{
uint i
bit no
DS=0
i=103
while(i>0)i--
DS=1
i=4
while(i>0)i--
no=DS
if(no==0)
{
DS=1
i=100
while(i>0)i--
no=DS
if(no==1)
not=0
else
not=1
}
else
not=1
return (not)
}
bit tmpreadbit(void) //读一位
{
uint i
bit dat
DS=0
i++
DS=1
i++i++
dat=DS
i=8while(i>0)i--
return (dat)
}
uchar tmpread(void) //读一个字节
{
uchar i,j,dat
dat=0
for(i=1i<=8i++)
{
j=tmpreadbit()
dat=(j<<7)|(dat>>1)//读出的数据最低位在最前面，这样刚好一个字节在DAT里
}
return(dat)
}
void tmpwritebyte(uchar dat) //写一个字节到 ds18b20
{
uint i
uchar j
bit testb
for(j=1j<=8j++)
{
testb=dat&0x01
dat=dat>>1
if(testb) //write 1
{
DS=0
i++i++
DS=1
i=8while(i>0)i--
}
else
{
DS=0 //write 0
i=8
while(i>0)i--
DS=1
i++i++
}
}
}
int tmp() //DS18B20温度读取
{
float tt
int a,b
if(init18b20()==0)
{
WDT_CONTR=0x36 /////喂狗
EA=0
delay(1)
tmpwritebyte(0xcc) // 跳过读ROM *** 作
tmpwritebyte(0x44) // 启动温度转换
delay(10)
init18b20()
delay(1)
tmpwritebyte(0xcc)
tmpwritebyte(0xbe)
a=tmpread()
b=tmpread()
temp=b
temp<<=8 //将高字节温度数据与低字节温度数据整合
temp=temp|a
c=b>>4
tt=temp*0.0625
temp=tt*10+0.5//放大10倍输出并四舍五入
EA=1
return temp
}
else
not=1
}
//////1062/////////
void ydelay(uint x)
{
uint a,b
for(a=xa>0a--)
for(b=10b>0b--)
}
void write_com(uchar com)
{
P0=com
lcwr=0
lcrs=0
lcden=0
ydelay(10)
lcden=1
ydelay(10)
lcden=0
lcwr=1
}
void write_date(uchar date)//写数据
{
P0=date
lcwr=0
lcrs=1
lcden=0
ydelay(10)
lcden=1
ydelay(10)
lcden=0
lcwr=1
}
void init1602()//初始化
{
write_com(0x38)//设置显示模式
ydelay(20)
write_com(0x0c)//开显示
ydelay(20)
write_com(0x06)//指针和光标自动加一
ydelay(20)
write_com(0x01)//清屏指令
ydelay(20)
}
///////显示程序//////
void display(int num)
{
uint i,A1,A2
WDT_CONTR=0x35 /////喂狗
if(c!=0)
num=~num+1
A1=num/1000
A2=num%1000/100
if(not==0)
{
if(c!=0)
{
c=0
table1[0]='-'
}
else if(A1==0)
table1[0]=' '
else
table1[0]=table[A1]
if(A1==0)
if(A2==0)
table1[1]=' '
else
table1[1]=table[A2]
table1[2]=table[num%1000%100/10]
table1[4]=table[num%1000%100%10]
}
else
{
table1[0]='?'
table1[1]='?'
table1[2]='?'
table1[4]='?'
}
write_com(0x80)
for(i=0i<11i++)
{write_date(table7[i])
delay(2)}
write_com(0x8b)
for(i=0i<5i++)
{write_date(table1[i])
delay(2)}
write_com(0xc0)
for(i=0i<16i++)
{
if(he==1)
write_date(ta5[i])
else if(in==1)
write_date(ta6[i])
else
write_date(table3[i])
}
c=0
WDT_CONTR=0x35 /////喂狗
}
////显示2////////////////////
display2(uchar bh,int dat)
{
uchar a,A,B
WDT_CONTR=0x35 /////喂狗
//write_com(0x01)//清屏指令
y=dat
y=y&0x8000
if(y!=0)
dat=~dat+1
A=dat/1000
B=dat%1000/100
if((bh!=4)&&(bh!=5))
{
if(A!=0)
table4[0]=table[dat/1000]
else if((c!=0)||(y!=0))
{
c=0y=0
table4[0]='-'
}
else
table4[0]=' '
if(B!=0)
table4[1]=table[B]
else
table4[1]=' '
table4[2]=table[dat%1000%100/10]
table4[3]='.'
table4[4]=table[dat%1000%100%10]
}
else
{
table4[0]=' '
if((c!=0)||(y!=0))
{
c=0y=0
table4[1]='-'
}
else
table4[1]=' '
table4[2]=' '
table4[3]=table[dat%1000%100/10]
table4[4]=table[dat%1000%100%10]
}
write_com(0xc4)
delay(2)
for(a=0a<5a++)
write_date(table4[a])
delay(2)
write_com(0x80)
switch(bh)
{
case 1:for(a=0a<14a++)write_date(ta1[a])break
case 2:for(a=0a<14a++)write_date(ta2[a])break
case 3:for(a=0a<14a++)write_date(ta3[a])break
case 4:for(a=0a<14a++)write_date(ta4[a])break
default:break
}
}
///////////x24c02//////////////////
void delay24()
{ }
void init24c02() //初始化
{
sda=1
delay24()
scl=1
delay24()
}
void start() //开始信号
{
sda=1
delay24()
scl=1
delay24()
sda=0
delay24()
}
void stop() //停止
{
sda=0
delay24()
scl=1
delay24()
sda=1
delay24()
}
void respons() //应答
{
uchar i
scl=1
delay24()
while((sda==1)&&(i<250))i++
scl=0
delay24()
}
void write_byte(uchar date) // 写数据子函数
{
uchar i,temp
temp=date
for(i=0i<8i++)
{
temp=temp<<1
scl=0
delay24()
sda=CY
delay24()
scl=1
delay24()
}
scl=0
delay24()
sda=1
delay24()
}
uchar read_byte() // 读数据子函数
{
uchar i,k
scl=0
delay24()
sda=1
delay24()
for(i=0i<8i++)
{
scl=1
delay24()
k=(k<<1)|sda
scl=0
delay24()
}
return k
}
///////写数据函数///////////////////
void write_add(uchar address,uint date)
{
start()
write_byte(0xa0)
respons()
write_byte(address)
respons()
write_byte(date/256)
respons()
write_byte(date%256)
respons()
stop()
}
uchar read_add(uchar address) //读数据函数
{
uchar date
start()
write_byte(0xa0)
respons()
write_byte(address)
respons()
start()
write_byte(0xa1)
respons()
date=read_byte()
stop()
return date
}
void delay1ms(uchar ms)
{
uchar i
while(ms--)
{
for(i = 0i<250i++)
{
_nop_()
_nop_()
_nop_()
_nop_()
}
}
}
int keyf(int *num,int up,int dn)
{
uint i
uchar z
for(i=0i<600i++)
{
display2(n,*num)
if(key1==0)
{
delay1ms(30)
if(key1==0)
{
i=0
n++
if(n>=9)
n=0
while(!key1)
display2(n,*num)
break
}
}
if(key2==0)
{
delay1ms(10)
if(key2==0)
{
i=0
if(*num>=up)
*num=up
else if(n!=4)
*num=*num+1
else if(*num<100)
*num=*num+5
else
*num=*num+10
for(z=0z<65z++)
{
display2(n,*num)
if(key2!=0)
break
}
while(!key2)
{
for(z=0z<2z++)
display2(n,*num)
if(*num>=up)
*num=up
else if(n!=4)
*num=*num+1
else if(*num<100)
*num=*num+5
else
*num=*num+10
}
}
}
if(key3==0)
{
delay1ms(10)
if(key3==0)
{
i=0
if(*num<=dn)
*num=dn
else if(n!=4)
*num=*num-1
else if(*num<100)
*num=*num-5
else
*num=*num-10
for(z=0z<65z++)
{
display2(n,*num)
if(key3!=0)
break
}
while(!key3)
{
for(z=0z<2z++)
display2(n,*num)
if(*num<=dn)
*num=dn
else if(n!=4)
*num=*num-1
else if(*num<100)
*num=*num-5
else
*num=*num-10
}
}
}
}
return(*num)
}
void keyjc()
{
uchar i=0
if(key1==0)
{
delay1ms(10)
if(key1==0)
{
EA=0
for(i=0i<20i++)
{
display(tmp())
}
if(key1==0)
{
write_com(0x01)//清屏指令
n++
if(n>=5)
n=0
while(!key1)
{
switch(n)
{
case 1:display2(n,acon)break
case 0:break
}
}
if(n==1)
{
keyf(&acon,1250,-530)
if((acon-bcon)<3)
bcon=acon-3
}
if(n==2)
{
keyf(&bcon,1240,-550)
if((acon-bcon)<3)
acon=bcon+3
}
write_add(1,acon)//A
delay1ms(15)
write_add(3,bcon)//B
n=0
write_com(0x01)//清屏指令
}
EA=1
}
}
}
key()
{
uint i
if(key4==0)
delay1ms(50)
if(key4==0)
{
write_com(0x01)//清屏指令
for(i=0i<500i++)
{
if(key4==0)
{
delay1ms(15)
if(key4==0)
{
i=0
n++
if(n>=5)
n=0
while(!key4)
{
switch(n)
{
case 1: display2(1,acon)break
case 2: display2(2,bcon)break
default: break
}
}
}
}
switch(n)
{
case 1: display2(1,acon)break
case 2: display2(2,bcon)break
default: break
}
}
n=0
}
}
///////滤波////////
int filter()
{
int tm,buf[6]
uchar i,j
EA=0
for(i=0i<6i++)
{
buf[i]=tmp()
delay1ms(20)
WDT_CONTR=0x35 /////喂狗
}
for(j=0j<5j++)
for(i=0i<5-ji++)
if(buf[i]>buf[i+1])
{
tm=buf[i]
buf[i]=buf[i+1]
buf[i+1]=tm
}
tm=((buf[2]+buf[3])/2)
EA=1
return (tm)
}
void main()
{
uchar b,c
Init_Com()
init1602()
init24c02()
b=read_add(1)
delay1ms(15)
c=read_add(2)
delay1ms(15)
acon=b*256+c
b=read_add(3)
delay1ms(15)
c=read_add(4)
delay1ms(15)
bcon=b*256+c
AUXR=0x01// 禁止ALE输出
WDT_CONTR=0x35//启动看门狗
write_com(0x01)//清屏指令
while(1)
{
at=filter()
display(at)
keyjc()
key()
wen_kong()
weno()
}
}
//////温度控制//////////////
void wen_kong()
{
if((flag==0)&&(not==0))
{
at=filter()
if(at<=bcon)
{
flag=1
jrk=0
xhk=0
he=1
}
}
}
void weno()
{
if(flag)
{
at=filter()
if(at>=acon)
{
flag=0
jrk=1
if(rsg)
xhk=0
else
xhk=1
he=0
}
}
if(not==1)
{
flag=0
jrk=1
if(rsg)
xhk=0
else
xhk=1
he=0
}
}
句法分析的基本任务是确定句子的 语法结构 或句子中 词汇之间的依存关系 。句法分析不是一个自然语言处理任务的最终目标，但它往往是实现最终目标的关键环节。
句法分析分为 句法结构分析 和 依存关系分析 两种。以获取整个句子的句法结构为目的的称为 完全句法分析 ，而以获得局部成分为目的的语法分析称为 局部分析 ，依存关系分析简称 依存分析 。
一般而言，句法分析的任务有三个：
判断输出的字符串是否属于某种语言
消除输入句子中词法和结构等方面的歧义
分析输入句子的内部结构，如成分构成、上下文关系等。
第二三个任务一般是句法分析的主要任务。
一般来说，构造一个句法分析器需要考虑两部分工作：一部分是语法的形式化表示和词条信息描述问题，形式化的语法规则构成了规则库，词条信息等由词典或同义词表等提供，规则库与词典或同义词表构成了句法分析的知识库；另一部分就是基于知识库的解析算法了。
语法形式化属于句法理论研究的范畴，目前在自然语言处理中广泛使用的是上下文无关文法（CFG）和基于约束的文法，后者又称合一文法。
简单的讲，句法结构分析方法可以分为基于规则的分析方法和基于统计的分析方法两大类。
基于规则的句法结构分析方法的基本思路是，由人工组织语法规则，建立语法知识库，通过条件约束和检查来实现句法结构歧义的消除。
根据句法分析树形成方向的区别，人们通常将这些方法划分为三种类型：自顶向下的分析方法，自底向上的分析方法和两者相结合的分析方法。自顶向下分析算法实现的是规则推导的过程，分析树从根结点开始不断生长，最后形成分析句子的叶结点。而自底向上分析算法的实现过程恰好想法，它是从句子符号串开始，执行不断规约的过程，最后形成根节点。
基于规则的语法结构分析可以利用手工编写的规则分析出输入句子所有可能的句法结构；对于特定领域和目的，利用有针对性的规则能够较好的处理句子中的部分歧义和一些超语法（extra-grammatical）现象。
但对于一个中等长度的输入句子来说，要利用大覆盖度的语法规则分析出所有可能的句子结构是非常困难的，而且就算分析出来了，也难以实现有效的消歧，并选择出最有可能的分析结果；手工编写的规则带有一定的主观性，还需要考虑到泛化，在面对复杂语境时正确率难以保证；手工编写规则本身就是一件大工作量的复杂劳动，而且编写的规则领域有密切的相关性，不利于句法分析系统向其他领域移植。
基于规则的句法分析算法能够成功的处理程序设计语言的编译，而对于自然语言的处理却始终难以摆脱困境，是因为程序设计语言中使用的知识严格限制的上下文无关文法的子类，但自然语言处理系统中所使用的形式化描述方法远远超过了上下文无关文法的表达能力；而且人们在使用程序设计语言的时候，一切表达方式都必须服从机器的要求，是一个人服从机器的过程，这个过程是从语言的无限集到有限集的映射过程，而在自然语言处理中则恰恰相反，自然语言处理实现的是机器追踪和服从人的语言，从语言的有限集到无限集推演的过程。
完全语法分析
基于PCFG的基本分析方法
基于概率上下文无关文法的短语结构分析方法，可以说是目前最成功的语法驱动的统计句法分析方法，可以认为是规则方法与统计方法的结合。
PCFG是CFG的扩展，举个例子：
PCFG
当然，同一个符号不同生成式的概率之和为1。NP是名词短语、VP是动词短语、PP是介词短语。
基于PCFG的句法分析模型，满足以下三个条件：
位置不变性：子树的概率不依赖于该子树所管辖的单词在句子中的位置
上下文无关性：子树的概率不依赖于子树控制范围以外的单词
祖先无关性：子树的概率不依赖于推导出子树的祖先节点
根据上述文法，『He met Jenny with flowers』有两种可能的语法结构：
而且我们可以通过将树中的所有概率相乘，得到两棵子树的整体概率，从中选择概率更大的子树作为最佳结构。
与HMM类似，PCFG也有三个基本问题：
给定一个句子W＝w1w2…wn和文法G，如何快速计算概率P(W|G)
给定一个句子W＝w1w2…wn和文法G，如何选择该句子的最佳结构？即选择句法结构树t使其具有最大概率
给定PCFG G和句子W＝w1w2…wn，如何调节G的概率参数，使句子的概率最大
首先是第一个问题，HMM中我们用的是前向算法和后向算法来计算观察序列O概率，相似的，这里我们用的是内向算法和外向算法来计算P(W|G) 。
首先我们定义内向变量αij(A)，与前向变量相似但又有不同，αij(A)即非终结符A推导出W中字串wiw(i+1)…wj的概率。那P(W|G)自然就等于α1n(S)了，S是起始符号，计算的就是由起始符号S推导出整个句子W=w1w2…wn的概率。
所以只要有αij(A)的递归公式就能计算出P(W|G)，递归公式如下：
根据定义，αii(A)自然就等同于符号A输出wi的概率；而αij(A)的计算思路是，这个子串wiw(i+1)…wj可以被切成两部分处理，前一部分wiw(i+1)…wk由非终结符号B生成，后一部分wkw(k+1)…wj由非终结符号C生成，而BC由A生成。这样将概率依次相乘，即可将一个大问题划分为两个小问题处理，两个小问题又可以进一步划分直到不能划分为止，然后递归回来得到结果。
这里给一张内向变量计算方法示意图：
这个问题也可以用外向算法来解决。
首先定义外向变量，βij(A)是，初始符号S在推导出语句W=w1w2…wn的过程中，产生符号串w1w2…w(i-1)Aw(j+1)…wn的概率（隐含着A会生成wiw(i+1)…wj）。也就是说βij(A)是S推导出除了以A节点为根节点的子树以外的其他部分的概率。
《统计自然语言处理（第二版）》这本书里讲错了，这里我给出我自己的理解，书里给的算法步骤如下：
很明显的错误，初始化都把结果初始化了，那这个算法还算什么，直接等于1就完了呗。
这是作者对外向变量定义理解模糊的问题，上面给了外向变量的定义，里面有一句话『隐含着A会生成wiw(i+1)…wj』，那问题在于，A会生成wiw(i+1)…wj，这到底算是条件还是推论。
看这个算法的初始化的意思，说β1n(A)，在A=S的时候，为1，不等于S为0，意思是什么？意思就是『隐含着A会生成wiw(i+1)…wj』这句话是条件，β1n(S)已经隐含了S生成W＝w1w2…wn了，所谓的w1w2…w(i-1)Aw(j+1)…wn也就不存在了，只剩下一个S->S了，所以概率自然为1。
但是在第三步这个地方，作者理解成什么意思了呢？作者又把『隐含着A会生成wiw(i+1)…wj』这句话当成推论了，认为在β1n(S)，里S会生成W＝w1w2…wn是推论，那真是就正好了，要求的结果就是S生成W＝w1w2…wn，这不就结束了吗，结果就导致了这个算法第一步初始化都把结果初始化了。
那我的理解是什么呢，通过这个公式计算出来的β1n(S)，确实是正确的，意义实际上也是包含了『隐含着A会生成wiw(i+1)…wj』这句话是推论，但是右侧式子里由于不断递归而产生的β1n(S)，是把『隐含着A会生成wiw(i+1)…wj』这句话当条件的，所以计算上没有问题。
我倾向于为第三步中的β1n(S)加一个星号，以表明意义的不同。
书中还给了个外向变量的计算方法示意图，我觉得也是莫名其妙：
他说βij(A)是这两种情况的概率和，这我们知道j比i大，那这图里这个k既比i小又比j大，这不是搞笑吗。只能说图上这俩C就不是一个C，k也不是一个k。
那我为什么会理解成一个呢，除了字母相同，他前面还这么讲『必定运用了形如B->AC或者B->CA的规则』、『运用B->AC或者B->CA两种规则的情况』，这明显就是给人以顺序交换的误解。
另外，还在内向变量的使用上前后不一，可以说这本书里对外向算法的讲解是非常失败的。而且对外向算法的计算仍然需要用到内向算法的递归，那真的直接用内向算法就好了，外向算法还要多定义变量。
然后是第二个问题，选择句子的最佳结构，也即给定一个句子W＝w1w2…wn和文法G，
选定拥有最大概率的语法结构树。这一问题与HMM中类似，仍然采用动态规划的思想去解决。最后利用CYK算法去生成拥有最大概率的语法结构树。
第三个问题是给定PCFG G和句子W＝w1w2…wn，如何调节G的概率参数，使句子的概率最大，与HMM相对的，PCFG这里采用的算法名叫内外向算法。与前后向算法相同，也属于一种EM算法，其基本思想是，首先给G的产生式随机地赋予一个概率值（满足归一化条件），得到文法G0，然后根据G0和训练数据，可以计算出每条规则使用次数的期望值，用期望值进行最大似然估计，得到语法G的新参数值，新的语法记作G1，然后循环执行该过程，G的参数概率将收敛于最大似然估计值。
PCFG只是一种特殊的上下文无关文法模型，根据PCFG的模型和句子，具体去对句子做语法分析，生成语法结构树，靠的是还是CYK算法。CYK算法是一个用来判定任意给定的字符串W是否属于一个上下文无关文法的算法。
基于PCFG的句法分析模型存在有许多问题，比如因为PCFG没有对词汇进行建模，所以存在对词汇信息不敏感的问题。因此人们提出了词汇化的短语结构分析器，有效的提升了基于PCFG的句法分析器的能力。
而且，我们上面也提到了PCFG的三个独立性假设，这也导致了规则之间缺乏结构依赖关系（就像HMM的三个假设也不完全合理一样），而在自然语言中，生成每个非终结符的概率往往是与其上下文结构有关系的，所以有人提出了一种细化非终结符的方法，为每个非终结符标注上其父节点的句法标记信息。
D. Klein提出了带有隐含标记的上下文无关文法（PCFG with latent annotations，PCFG-LA），使得非终结符的细化过程可以自动进行，并且在使用EM算法优化时，为避免到达局部最优，对其进行了改进，提出了一种层次化的『分裂-合并』策略，以期获取一个准确并且紧凑的PCFG-LA模型。基于PCFG-LA的Berkeley Parser作为非词汇化句法分析器的代表，无论是性能表现还是运行速度，都是目前开源的短语结构分析器中最好的。其语法树如下图：
普通句法树与PCFG-LA句法树对照实例
这个x就是隐含标记，xi的取值范围一般是人为设定的，一般取1~16之间的整数。而且PCFG-LA也类似于HMM模型，原始非终结符对应HMM模型中的观察输出，而隐含标记对应HMM模型中的隐含状态。
浅层语法分析（局部语法分析）
由于完全语法分析要确定句子所包含的全部句法信息，并确定句子中各成分之间的关系，这是一项十分苦难的任务。到目前为止，句法分析器的各方面都难以达到令人满意的程度，为了降低问题的复杂度，同时获得一定的句法结构信息，浅层句法分析应运而生。
浅层语法分析只要求识别句子中的某些结构相对简单的独立成为，例如非递归的名词短语、动词短语等，这些被识别出来的结构通常称为语块（chunk）。
浅层句法分析将句法分析分解为两个主要子任务，一个是语块的识别和分析，另一个是语块之间的依附关系分析。其中，语块的识别和分析是主要任务。在某种程度上说，浅层句法分析使句法分析的任务得到了简化，同时也有利于句法分析系统在大规模真实文本处理系统中迅速得到应用。
基本名词短语（base NP）是语块中的一个重要类别，它指的是简单的、非嵌套的名词短语，不含有其他子项短语，并且base NP之间结构上是独立的。示例如下：
base NP识别就是从句子中识别出所有的base NP，根据这种理解，一个句子中的成分和简单的分为baseNP和非base NP两类，那么base NP识别就成了一个分类问题。
base NP的表示方法有两种，一种是括号分隔法，一种是IOB标注法。括号分隔法就是将base NP用方括号界定边界，内部的是base NP，外部的不属于base NP。IOB标注法中，字母B表示base NP的开端，I表示当前词语在base NP内，O表示词语位于base NP之外。
基于SVM的base NP识别方法
由于base NP识别是多值分类问题，而基础SVM算法解决的是二值分类问题，所以一般可以采用配对策略（pairwise method）和一比其余策略（one vs. other method）。
SVM一般要从上下文的词、词性、base NP标志中提取特征来完成判断。一般使用的词语窗口的长度为5（当前词及其前后各两个词）时识别的效果最好。
基于WINNOW的base NP识别方法
WINNOW是解决二分问题的错误驱动的机器学习方法，该方法能从大量不相关的特征中快速学习。
WINNOW的稀疏网络（SNoW）学习结构是一种多类分类器，专门用于处理特征识别领域的大规模学习任务。WINNOW算法具有处理高维度独立特征空间的能力，而在自然语言处理中的特征向量恰好具有这种特点，因此WINNOW算法也常用于词性标注、拼写错误检查和文本分类等等。
简单WINNOW的基本思想是，已知特征向量和参数向量和实数阈值θ，先将参数向量均初始化为1，将训练样本代入，求特征向量和参数向量的内积，将其与θ比较，如果大于θ，则判定为正例，小于θ则判定为反例，将结果与正确答案作比较，依据结果来改变权值。
如果将正例估计成了反例，那么对于原来值为1的x，把它的权值扩大。如果将反例估计成了正例，那么对于原来值为1的x，把它的权值缩小。然后重新估计重新更改权重，直到训练完成。
这其实让我想到了LR算法，因为LR算法也是特征向量与参数向量的内积，最后将其送到Sigmoid函数中去拿到判定结果，然后大于0.5的为正例，小于0.5的为反例，实际上只要反过来，Sigmod函数输出0.5时候的输入就是WINNOW算法里的那个实数阈值θ。但是区别在于WINNOW算法只判定大小，不判定概率，而LR利用Sigmoid函数给出了概率。LR利用这给出的概率，通过使训练集的生成概率最大化来调整参数，而WINNOW则是直接朴素的错误情况来增大或缩小相关参数。目测LR因为使用了梯度下降，它的收敛速度要快于WINNOW，而WINNOW的优势则在于可以处理大量特征。
基于CRF的base NP识别方法
基于CRF的base NP识别方法拥有与SVM方法几乎一样的效果，优于基于WINNOW的识别方法、基于MEMM的识别方法和感知机方法，而且基于CRF的base NP识别方法在运行速度上较其他方法具有明显优势。
依存语法理论
在自然语言处理中，我们有时不需要或者不仅仅需要整个句子的短语结构树，而且要知道句子中 词与词之间的依存关系 。用词与词之间的依存关系来描述语言结构的框架成为依存语法，又称从属关系语法。利用依存语法进行句法分析也是自然语言理解的重要手段之一。
有人认为，一切结构语法现象可以概括为关联、组合和转位这三大核心。句法关联建立起词与词之间的从属关系，这种从属关系由 支配词 和 从属词 联结而成， 谓语中的动词是句子的中心并支配别的成分，它本身不受其他任何成分支配 。
依存语法的本质是一种结构语法，它主要研究以谓词为中心而构句时由深层语义结构映现为表层语法结构的状况及条件，谓词与体词之间的同现关系，并据此划分谓词的词类。
常用的依存于法结构图示有三种：
计算机语言学家J. Robinson提出了依存语法的四条公理：
一个句子只有一个独立的成分
句子的其他成分都从属于某一成分
任何一个成分都不能依存于两个或两个以上的成分
如果成分A直接从属于成分B，而成分C在句子中位于A和B之间，那么，成分C或者属于成分A，或者从属于B，或者从属于A和B之间的某一成分。
这四条公理相当于对依存图和依存树的形式约束：单一父节点、连通、无环和可投射，由此来保证句子的依存分析结果是一棵有根的树结构。
这里提一下可投射，如果单词之间的依存弧画出来没有任何的交叉，就是可投射的（参考上面的两个有向图）。
为了便于理解，我国学者提出了依存结构树应满足的5个条件：
单纯结点条件：只有终结点，没有非终结点
单一父结点条件：除根节点没有父结点外，所有的结点都只有一个父结点
独根结点条件：一个依存树只能有一个根结点，它支配其他结点
非交条件：依存树的树枝不能彼此相交
互斥条件：从上到下的支配关系和从左到右的前于关系之间是相互排斥的，如果两个结点之间存在着支配关系，它们就不能存在于前于关系
这五个条件是有交集的，但它们完全从依存表达的空间结构出发，比四条公理更直观更实用。
Gaifman 1965年给出了依存语法的形式化表示，证明了依存语法与上下文无关文法没有什么不同..
类似于上下文无关文法的语言形式对被分析的语言的投射性进行了限制，很难直接处理包含非投射现象的自由语序的语言。20世纪90年代发展起来了约束语法和相应的基于约束满足的依存分析方法，可以处理此类非投射性语言问题。
基于约束满足的分析方法建立在约束依存语法之上，将依存句法分析看做可以用约束满足问题来描述的有限构造问题。
约束依存语法用一系列形式化、描述性的约束将不符合约束的依存分析去掉，直到留下一棵合法的依存树。
生成式依存分析方法、判别式依存分析方法和确定性依存分析方法是数据驱动的统计依存分析中具有代表性的三种方法。
生成性依存分析方法
生成式依存分析方法采用联合概率模型生成一系列依存语法树并赋予其概率分值，然后采用相关算法找到概率打分最高的分析结果作为最后输出。
生成式依存分析模型使用起来比较方便，它的参数训练时只在训练集中寻找相关成分的计数，计算出先验概率。但是，生成式方法采用联合概率模型，再进行概率乘积分解时做了近似性假设和估计，而且，由于采用全局搜索，算法的复杂度较高，因此效率较低，但此类算法在准确率上有一定优势。但是类似于CYK算法的推理方法使得此类模型不易处理非投射性问题。
判别式依存分析方法
判别式依存分析方法采用条件概率模型，避开了联合概率模型所要求的独立性假设（考虑判别模型CRF舍弃了生成模型HMM的独立性假设），训练过程即寻找使目标函数（训练样本生成概率）最大的参数θ（类似Logistic回归和CRF）。
判别式方法不仅在推理时进行穷尽搜索，而且在训练算法上也具有全局最优性，需要在训练实例上重复句法分析过程来迭代参数，训练过程也是推理过程，训练和分析的时间复杂度一致。
确定性依存方法
确定性依存分析方法以特定的方向逐次取一个待分析的词，为每次输入的词产生一个单一的分析结果，直至序列的最后一个词。
这类算法在每一步的分析中都要根据当前分析状态做出决策（如判断其是否与前一个词发生依存关系），因此，这种方法又称决策式分析方法。
通过一个确定的分析动作序列来得到一个唯一的句法表达，即依存图（有时可能会有回溯和修补），这是确定性句法分析方法的基本思想。
短语结构与依存结构之间的关系
短语结构树可以被一一对应地转换成依存关系树，反之则不然。因为一棵依存关系树可能会对应多棵短语结构树。
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）