统计语言模型 假设一个句子S可以表示为一个序列S=w1w2…wn,语言模型就是要求句子S的概率P(S): 这个概率的计算量太大,解决问题的方法是将所有历史w1w2…wi-1按照某个规则映射到等价类S(w1w2…wi-1),等价类的数目远远小于不同历史的数目,即假定: N-Gram模型 当两个历史的最近的N-1个词(或字)相同时,映射两个历史到同一个等价类,在此情况下的模型称之为N-Gram模型。 N-Gram模型被称为一阶马尔科夫链。 N的值不能太大,否则计算仍然太大。 根据最大似然估计,语言模型的参数: 其中,C(w1w2…wi)表示w1w2…wi在训练数据中出现的次数 平滑技术的引入 传统的估计方法对于随机变量£的N次独立观察的样本容量N有如下要求: N>>K 其中K为随机变量能够取到的值的个数。 实际语言模型中往往无法满足这个要求。 例如:词性标注问题,共有140个可能的标记,考虑当前词前后两个词的影响的三阶模型。 K=140*140*140=2,744,000 给定一个10万词左右的人工标注训练集,即 N=100,00,可见训练数据显得非常不足。 假设k泛指某一事件,N(k)表示事件k观察到的频数,极大似然法使用相对频数作为对事件k的概率估计: p(k)=N(k)/N 在语言模型中,训练语料中大量的事件N(k)=0,这显然没有反映真实情况。我们把这个问题称为数据稀疏问题。 这种零值的概率估计会导致语言模型算法的失败,例如:概率值作为乘数会使结果为0,而且不能做log运算。 计数等价类 根据对称性原理,事件除了出现次数之外不应具有细节特征,即所有具有相同计数r=N(k)的事件k(事件出现的次数称为事件的计数)应当具有相同的概率估计值,这些计数相同的事件称为计数等价,将它们组成的一个等价类记为计数等价类Gr。 对于计数为r的计数等价类,定义nr为等价类中成员的个数,pr为等价类中事件的概率,R是最大可能出现的计数次数,则 交叉检验 交叉检验就是把训练样本分为m份,其中一份作为保留部分,其余m-1份作为训练部分。训练部分作为训练集估计概率pr,保留部分作为测试集进行测试。 我们使用Cr表示保留部分中计数为r的计数等价类的观察个数。对于保留部分使用最大似然法对进行概率pr进行估计,即使对数似然函数最大化: 使用拉格朗日乘子解决约束条件下的最大值问题,即: 对pr求偏导,得到交叉检验估计: 如果测试部分也作为保留部分的话,就是典型的极大似然估计: 留一估计 留一方法是交叉检验方法的扩展,基本思想是将给定N个样本分为N-1个样本作为训练部分,另外一个样本作为保留部分。这个过程持续N次,使每个样本都被用作过保留样本。 优点:充分利用了给定样本,对于N中的每个观察,留一法都模拟了一遍没有被观察到的情形。 对于留一方法,pr的极大似然估计为: Turing-Good公式 因为nRpR与1相比一般可以忽略,留一估计公式可以近似为: 留一估计可以利用计数r=1的事件来模拟未现事件,对于未现事件有如下估计: 这个公式就是著名的Turing-Good公式。 空等价类 留一估计中要求么个nr均不为0,在实际问题中当r=5时,这个要求通常都不能满足,即计数等价类G1,…,GR中存在空的等价类。这时按照出现次数进行排序: 对应的出现r(l)次的事件的个数记为nr(l),在进行留一估计时,使用下一个非空的等价类Gr(l+1)代替可能为空的等价类Gr(l)+1,留一估计公式变为: 式中对空的等价类没有估计概率,因为空等价类并没有对应任何有效事件。 Turing-Good估计的优缺点和适用范围 缺点:( 1 )无法保证概率估计的“有序性”,即出现次数多的事件的概率大于出现次数少的事件的概率。(2)pr与r/N不能很好地近似,好的估计应当保证pr<=r/N。 优点:其它平滑技术的基础。 适用范围:对0<r<6的小计数事件进行估计。 约束留一估计 单调性约束:pr-1<=pr;折扣约束:p<=r/N。 约束留一估计:让计数估计r*=pr•N处于距其最近的绝对频数之间: 在这个约束下,单调性约束自然满足。 计算方法:计算m时检查每个pr是否满足约束,不然就用约束的上下界进行裁剪,然后重新计算m,一直迭代下去直到所有pr满足约束。 折扣模型 [...]
AMQP协议介绍
AMQP,即Advanced Message Queuing Protocol,高级消息队列协议,是应用层协议的一个开放标准,为面向消息的中间件设计。 AMQP的主要特征是面向消息、队列、路由(包括点对点和发布/订阅)、可靠性、安全。 AMQP在消息提供者和客户端的行为进行了强制规定,使得不同卖商之间真正实现了互操作能力。 JMS是早期消息中间件进行标准化的一个尝试,它仅仅是在API级进行了规范,离创建互操作能力还差很远。 与JMS不同,AMQP是一个Wire级的协议,它描述了在网络上传输的数据的格式,以字节为流。因此任何遵守此数据格式的工具,其创建和解释消息,都能与其他兼容工具进行互操作。 AMQP规范的版本: 0-8 是2006年6月发布 0-9 于2006年12月发布 0-9-1 于2008年11月发布 0-10 于2009年下半年发布 1.0 draft (文档还是草案) AMQP的实现有: 1)OpenAMQ AMQP的开源实现,用C语言编写,运行于Linux、AIX、Solaris、Windows、OpenVMS。 2)Apache Qpid Apache的开源项目,支持C++、Ruby、Java、JMS、Python和.NET。 3)Redhat Enterprise MRG 实现了AMQP的最新版本0-10,提供了丰富的特征集,比如完全管理、联合、Active-Active集群,有Web控制台,还有许多企业级特征,客户端支持C++、Ruby、Java、JMS、Python和.NET。 4)RabbitMQ 一个独立的开源实现,服务器端用Erlang语言编写,支持多种客户端,如:Python、Ruby、.NET、Java、JMS、C、PHP、ActionScript、XMPP、STOMP等,支持AJAX。RabbitMQ发布在Ubuntu、FreeBSD平台。 5)AMQP Infrastructure Linux下,包括Broker、管理工具、Agent和客户端。 6)ØMQ 一个高性能的消息平台,在分布式消息网络可作为兼容AMQP的Broker节点,绑定了多种语言,包括Python、C、C++、Lisp、Ruby等。 7)Zyre 是一个Broker,实现了RestMS协议和AMQP协议,提供了RESTful HTTP访问网络AMQP的能力。