统计自然语言处理基本概念.ppt

统计自然语言处理基本概念,模型,真实世界中的系统,模型1,Input,Output,模型2,Output1,Output2,如果Output1总是和Ouput接近，Output2总是和Output偏离，我们就认为模型1比模型2好,真实系统,模型1,模型2,Input,Output,模型由体系结构和参数两部分构成举例：住宅楼多层板楼高层板楼高层塔楼参数层数：户型：三室一厅，两室一厅，举架高度：供热方式：地热？暖气片？,目录,样本空间(SampleSpace)估计器(Estimator)和随机过程(StochasticProcess)信息论(InformationTheory)数据集分类(DataSetClassification)性能评价(PerformanceMeasure),样本空间(SampleSpace),试验(Experiment),试验一个可观察结果的人工或自然的过程，其产生的结果可能不止一个，且不能事先确定会产生什么结果例如连掷两次硬币样本空间是一个试验的全部可能出现的结果的集合举例连掷两次硬币=HH,HT,TH,TT,H:面朝上;T:面朝下,事件(Event),事件一个试验的一些可能结果的集合，是样本空间的一个子集举例：连掷两次硬币A:至少一次面朝上B:第二次面朝下A=HT,TH,HH,B=HT,TT,事件的概率,事件的概率重复m试验，如果事件A出现的次数为n，则事件A的概率为P(A)=n/m，这称为概率的频率解释，或称统计解释频率的稳定性又称为经验大数定理举例：连掷两次硬币A:至少一次面朝上B:第二次面朝下P(A)=3/4,P(B)=1/2当试验不能重复时，概率失去其频率解释的含义，此时概率还有其他解释：贝叶斯学派和信念学派一个人出生时的体重，一个人只能出生一次,举例,举例：连续三次掷硬币样本空间=HHH,HHT,HTH,HTT,THH,THT,TTH,TTT事件A：恰好两次面朝下A=HTT,THT,TTH做1000次试验，计数得386次为两次面朝下估计：P(A)=386/1000=0.386继续做7组试验，得：373，399，382，355，372，406，359，共8组试验计算平均值：P(A)=(0.386+0.373+)/8=0.379，或累计：P(A)=(386+373+)/8000=3032/8000=0.379统一的分布假设为：3/8=0.375,概率空间,概率空间的三个公理P(A)0P()=1P(AB)=P(A)+P(B)ifAB=这三条公理也是概率的原始定义推论：P()=0;ABP(A)0正相关，0：x和y关联强度大I(x,y)=0：x和y无关I(x,y)0：x和y具有互补的分布,熵(Entropy),熵(Entropy)Chaos（混沌），无序物理学：除非施加能量，否则熵不会降低举例：把房间弄乱很容易，整理干净不容易是不确定性(Uncertainty)的衡量不确定性越高，熵越高，我们从一次实验中得到的信息量越大,熵的公式,熵H(X)=-xp(x)logxp(x)假设PX(x)是随机变量X的分布基本输出字母表是单位：bits熵是X的平均信息量，是自信息量的期望E(X)=xp(x)xI(X)=-logp(x)，取2为底，I(X)=-log2p(x)E(I(X)=E(-log2p(x)=xp(x)(-log2p(x)=H(X)H(X)=H(p)=Hp(X)=HX(p)=H(pX),熵的例子,掷均匀硬币，=H,Tp(H)=.5,p(T)=.5H(p)=-0.5log20.5+(-0.5log20.5)=132面的均匀骰子，掷骰子H(p)=-32(1/32)log2(1/32)=5事实上，21=2,25=32(perplexity)掷不均匀硬币p(H)=0.2,p(T)=0.8,H(p)=0.722p(H)=0.01,p(T)=0.99,H(p)=0.081,好书店，差书店,什么时候H(p)=0?试验结果事先已经知道即：x,p(x)=1;y,p(y)=0ifyx熵有没有上限？没有一般的上限对于|=n，H(p)log2n均衡分布的熵是最大的,等概率分布2个输出的等概率分布，H(p)=1bit32个输出的等概率分布，H(p)=5bits43亿输出的等概率分布，H(p)=32bits非等概率分布32个输出，2个0.5，其余为0，H(p)=1bit怎样比较具有不同数量输出的“熵”,混乱度Perplexity,混乱度G(p)=2H(p)平均每次试验有多少种可能的结果在NLP中，如果词表中的词具有统一的分布概率，则最难预测，熵最大，混乱度最高反之，分布越不均衡，熵越小，混乱度越小,联合熵和条件熵,两个随机变量：X(空间是)，Y()联合熵(JointEntropy)(X,Y)被视为一个事件H(X,Y)=-xyp(x,y)log2p(x,y)条件熵(ConditionalEntropy)H(Y|X)=-xyp(x,y)log2p(y|x)p(x,y)是加权，权值是没有条件的,条件熵,H(Y|X)=xp(x)H(Y|X=x)=xp(x)(-yp(y|x)log2p(y|x)=-xyp(y|x)p(x)log2p(y|x)=-xyp(x,y)log2p(y|x),熵的性质,熵的非负的H(X)0ChainRuleH(X,Y)=H(Y|X)+H(X)H(X,Y)=H(X|Y)+H(Y)H(X,Y)H(X)+H(Y)，X和Y独立时相等H(Y|X)H(Y)，条件熵比熵小,熵的编码意义,如果一个符号序列是满足概率分布p的随机过程产生的，那么对这个序列进行编码至少需要的bit数是H(p)压缩问题如果数据中有很多重复的模式，则易于压缩，因为熵小否则，熵大，不容易压缩,编码实例,怎样给ISOLatin1编码？通常用8位经验表明：有的字符经常出现，有的字符很少出现我们可以给经常出现的字用较少的bit来表示，给很少出现的字符用较多的bit来表示假设：p(a)=0.3,p(b)=0.3,p(c)=0.3,其余p(x)=0.0004编码：a:00,b:01,c:10,其余：11b1b2b8对于符号串：acbbcbaac，编码为：acbbcbaac0010010111000011111001000010如果每个符号用8位编码，需要80位，现在需要28位,语言的熵,p(cn+1|c1cn)ci是语言中的一个字符c1cn是历史h举例：汉语，n=3p(赵|围魏救)：高p(去|我曾经)：低计算语言的条件熵-hHcp(c,h)log2p(c|h),各种语言的熵,按字母计算的零阶熵法文：3.98bits意大利文：4.00bits西班牙文：4.01bits英文：4.03bits德文：4.10bits俄问：4.35bits中文（按汉字计算）：9.65bits中文（按笔画计算）：3.43bits按词汇计算的零阶熵英语：10.0bits汉语：11.46bits说明汉语的词汇丰富语言的冗余度英语：73%；俄语：70%；汉语：63%；古文更低,Kullback-Leibler距离,假设通过一组试验估计得到的概率分布为p，样本空间，随机变量X真实的分布为q，相同的和X现在的问题是：p和q相比，误差多大？Kullback-Leibler距离给出的答案是：D(q|p)=xq(x)log2q(x)/p(x)=Eplog(q(x)/p(x),KL距离（相对熵）,习惯上0log0=0plog(p/0)=DistanceorDivergence（分歧）不对称D(q|p)D(p|q)也不满足三角不等式事实上，D(q|p)不是距离，而是分歧H(q)+D(q|p)：根据q分布，对p进行编码需要的bit数（交叉熵）,平均互信息,随机变量：X;Y;pXY(X,Y);pX(x);pY(y)两个离散集之间的平均互信息I(X,Y)=D(p(x,y)|p(x)p(y)=xyp(x,y)log2(p(x,y)/p(x)p(y)这里说的是两个离散集的平均互信息互信息衡量已知Y的分布时，对X的预测有多大的帮助，或者说Y的知识降低了H(X)或者说p(x,y)和p(x)p(y)之间的距离,互信息的性质,I(X,Y)=H(X)-H(X|Y)=H(Y)-H(Y|X)I(X,Y)=H(X)+H(Y)-H(X,Y)因为：H(X,Y)=H(X|Y)+H(Y)I(X,X)=H(X)(因为H(X,X)=0)I(X,Y)=I(Y,X)I(X,Y)0,交叉熵Cross-Entropy,典型情况：我们得到一个观察序列T=t1,t2,tn,ti估计：y:p(y)=c(y)/|T|,定义：c(y)=|tT,t=y|但是，真实的q不知道，再大的数据也不够问题：用p对q进行估计是否准确？方法：用一个不同的观察序列T估计实际的q,交叉熵,Hp(p)=H(p)+D(p|p)Hp(p)=-xp(x)log2p(x)p当然也不是真实的分布，但是我们视为真实世界的分布，以便测试p交叉混乱度：Gp(p)=2Hp(p),条件交叉熵,实践中计算的往往是条件交叉熵两个样本空间样本空间：，随机变量Y，yY上下文样本空间：，随机变量X，xX实验得到的分布p(y|x)，“真实”分布p(y|x)Hp(p)=-y,xp(y,x)log2p(y|x)条件交叉熵中的权值是p(y,x)，不是p(y|x),在实际应用中，在全部两个样本空间上做累加通常不是很方便，因此常常简化使用如下公式：Hp(p)=-y,xp(y,x)log2p(y|x)=-1/|T|i=1|T|log2p(yi|xi)事实上，就是在T上进行累加，然后归一化=-1/|T|log2i=1|T|p(yi|xi),举例,=a,b,z，概率分布（估计值）p(a)=0.25,p(b)=0.5,p()=1/64,c,r,p()=0,s,z测试数据为：barb，p(a)=p(r)=0.25,p(b)=0.5在上做累加abcdqrsz-p()log2p()0.50.50001.500=2.5也可以在测试数据上进行累加，然后归一化sibarb-log2p(si)1261=10(1/4)10=2.5,H(p)和Hp(p)之间可能有各种关系包括,举例（参照上例）H(P)=2.5测试数据：barbHp(p)=1/4(1+2+6+1)=2.5测试数据：probableHp(p)=1/8(6+6+6+1+2+1+6+6)=4.25测试数据：abbaHp(p)=1/4(2+1+1+2)=1.5,交叉熵的使用,不是比较数据，而是比较分布如果我们有两个分布p和q，哪一个更好呢？面对“真实数据”S，p和q谁的交叉熵低，谁就更好HT(p)=-1/|S|log2i=1|S|p(yi|xi)HT(q)=-1/|S|log2i=1|S|q(yi|xi),数据集分类,训练集TrainingSet用来获得模型参数测试集TestingSet从训练集以外独立采样反映系统面对真实世界的处理能力测试集经常被无意识地“做了手脚”交叉确认集Cross-ValidationSet从训练集和测试集以外独立采样主要用来帮助做设计决策,测试集,测试集从训练集去评价系统的性能，结果往往过于乐观如果模型的参数比需要的多很多时，获得100%的准确率也是可能的过拟和(Over-fitting)常常出现在训练数据的数量不足以支持模型的复杂程度之时为此，我们需要另一个数据集来模拟用户的真实需要,在设计阶段，不允许偷看测试数据的细节，以保证测试数据不被污染你不能参照测试数据来决定模型的复杂度，特征空间的维数，以及什么时候决定停止训练过程等设计决策可以参照交叉确认数据进行每一个阶段采用一个不同测试集当你试图选择一个最好的方法使测试效果达到最佳时，实际上已经在无意识地使你的系统偏向测试集问题的关键在于测试集并不是真实数据本身，如果面向测试集调整参数，可能造成系统对于从未见过的真实数据效果下降,交叉确认集如果在训练集合上获得了比较差的结果，我们必须重新设计如果在训练集合上获得了比较好的结果，那可能是因为：模型确实好（在测试数据上性能一样会好）模型过拟和（在测试数据上性能会下降）由于不允许使用测试集来改进系统设计，因此需要另一个数据集,性能评价,使用有限的样本进行性能测试有估计误差性能评价的结果和测试数据的大小有关不同数据集的测试结果往往不同性能上限PerformanceUpperBound人与人取得一致的指标就是系统性能的上限,联立表(Contingencytable),准确率P(Precision)N11/(N11+N21)召回率R(Recall)N11/(N11+N12)错误率E(ErrorRate)(N12+N21)/(N11+N12+N21+N22)F-measure2PR/(P+R),谢谢！,