最近做毕业设计其中一部分需要进行中英文词语的切分，所以鄙人采用一下方法进行处理：
同时使用下面两种大方法：
1、基于HMM的中英文分词
2、基于词库的中英文分词

原因：
1、HMM之类的模型有比较高的智能性，但是速度较慢和复杂性较高
2、词库方法实现相对简单，但是对新词汇等的适应能力先天不足

so，整合在一起使用~简单一点说就是主体采用HMM进行分词，然后对其中变成“单字”的部分进行词库分词~

下面对HMM进行简单的描述和论证~


[ 此贴被zc1984在2007-04-22 10:13重新编辑 ]

如何更好的认识世界？找到规律！哪怕这个规律就是“随机”本身！

我们经常需要寻找一个事物一个时间片段中的变化规律，例如“股票”、“海潮”等~

下面我们首先看看如何生成一个概率模型系统来进行预测~

然后我们尝试接触一种系统：我们需要预测的该系统的状态是隐藏在表象之后的，并不能被我们直接观察到。例如“看到动物开始狂躁不安，水井的水暴涨暴跌，就说明地震可能会发生”~~

最后，我们尝试利用已经建立的模型去解决一些实际问题，例如我的毕业设计中的中英文分词，呵呵~


[ 此贴被zc1984在2007-04-22 10:18重新编辑 ]

生成模式

一般来说，有两种模式：
1、确定性的生成模式：变化规律是固定的，可以进行准确的预测。例如“春夏秋冬”的转变，我们知道了一个季节，就可以明确的知道下一个季节是什么（不要说电影《后天》那种情况，只不过是一个例子嘛，不要这么认真嘛~~）。

2、非确定性的生成模式：变化规律存在，但是是以概率的形式进行表述的，我们并不能准确的预测。例如“一个通向大城市和小乡村的十字路口的车辆”，经过长时间的统计，我们知道车开向大城市的概率为90%，开向小乡村的概率为10%，那么当我们预测一台车经过这个十字路口的时候，我们并不能得出准确的预测，只能说开向大城市的可能性比较大~~

我们可以假设某个状态只和它之前的状态有关，这就是马尔科夫假设。虽然这只是一个大概的估计并不精确，但是往往能在本来就不精确的现实中产生巨大的作用。

马尔科夫过程：当前状态只和之前的n个状态有关，这就是n阶马尔科夫模型。
最简单的就是一阶马尔科夫模型了~~哇咔咔（但是希望大家能够注意到即使是1阶模型，也和确定性生成模式有差别，这里是指一个概率模型~~）
对于有T个状态的一阶马尔科夫模型，一共有T*T个状态转移~，每种状态转移都对应着一定的概率（也就是转移概率），我们可以很方便的使用矩阵进行描述~~

我们下面就看看一个实际中的例子——“股票”：
        今天的情况
      涨   平   跌
明天 涨   0.5   0.25   0.25
的   平   0.375 0.125 0.375
情况 跌   0.125 0.625 0.375

（注意每行每列的概率和都是1哈~~）
我们看其中的一种状态：今天涨，明天也涨~~（我最喜欢的股票转移状态了，哇咔咔），根据上面的表，我们得到该状态（今天，涨）-->（明天，涨）概率为0.5。Clear？

p.s.一个系统开始运作的时候，我们需要对其进行初始化，给出初始概率，也就是传说中的π向量~~
例如对应上面的股票的例子，就是今天的股票的情况：
涨   平   跌
(1.0 0.0 0.0)
我最喜欢这样了~~

finally，我们得到一个一阶的马尔科夫模型，包括一下内容：
状态：涨、平、跌
状态转移概率
初始概率~~

（打字累了，喝口水，看看远方~~）


[ 此贴被zc1984在2007-04-22 10:45重新编辑 ]

上面的世界貌似很美好，都这样的话人人炒股都会成为百万富翁来自亿万富翁~~
为什么现实中没这么富翁呢？那就是因为我们并不能直接观察到涨跌之间的关系~~~
也就是说我们得不到上面那个状态转移矩阵~~

但是我们知道一些其他的东西，例如“大庄家或者机构投资者大举买入某只股票的话，那么这只股票很可能会涨~相反，可能会跌~~~”
（另一个例子就是做语音识别的时候，我们输入的语音信号就是观察到的状态，而我们需要识别出来的文字就是隐含在现象后面的——称为隐含状态）

那么，我们就观察这些大机构吧~~（他们很有钱，貌似最近一个基金仓都有n亿的资金~~）

HMM（很有意思的哦~）
我们假设隐含状态是通过一阶马尔科夫过程描述的，并且都是有链接的（也就是对上面一些炒股经验的数学抽象）

            观察到的状态
        大机构抛售     大机构买入
隐含的 涨     0.1         0.9
状态   跌     0.9         0.1

我们现在得到了另一个状态转移矩阵~~~同样的，里面的每行每列的和都是1~~

至此，我们得到了HMM（隐式马尔科夫模型）的所有要素：
1、两类状态：观察状态+隐含状态
2、三组概率：初始概率、状态转移概率、两态对应概率(confusion matrix)

吃饭去了~~回来继续~~


[ 此贴被zc1984在2007-04-22 11:04重新编辑 ]

HMM的数学定义

HMM是一个三元组(大π,A,B)
大π=(π[i])——初始状态概率向量
A=(a[i,j])——状态转移矩阵，Pr(x[i,t]|x[j,t-1])
B=(b[i,j])——两态对应概率矩阵，Pr(y[i]|x[j])——混淆概率矩阵

其中，状态转移概率矩阵和两态对应概率矩阵（以后就把它成为混淆概率矩阵）在整个系统中是保持不变的，这也是HMM中很不爽的一个假设~~~因此我们可能需要经过一段时间就要进行一次调整，也可以使某种条件作为触发进行调整~~~唉，数学是好东西啊，加紧学习了~~~

HMM的应用

主要用来进行模式识别和参数估计~~
典型的例子：
1、评估：根据已知的HMM求出某个观察序列的概率。
这类问题是首先假定我们有了一系列的HMM描述不同的系统（例如“牛市的股票和熊市的股票”），我们想要得到哪个系统的生成观察状态序列的可能性最大。换句话来说就是，把不同的系统运用到一个给定的观察序列中去，得到最大概率的那个系统所对应的情况就是最有可能出现的情况（就是根据观察状态序列得到“是熊市股票还是牛市股票”，哇咔咔）。

我们可以使用forward算法得到观察状态序列对应的一个HMM的概率~~~~

2、学习：非常困难的一个领域，我自己都学不会的东西要让这台机器学会，难于上LT的网~，哇咔咔~~也就是根据观察序列和其代表的隐含状态，生成一个HMM三元组(大π,A,B)，然后使得一个三元组能够很好的解释和描述我们已知的另一个观察序列的情况，也就是让机器总结一个规律~~

我们可以使用forward-backward算法来解决一些现实中的不能直接得到状态转移矩阵和混淆矩阵的情况~~

3、解码：根据观察序列找到最有可能出现的隐含状态序列。回顾我们关于股票的例子，我们可以观察到大机构投资者的操作，从而判断出股票的涨跌平的情况，这就是典型的应用了。

我们可以使用viterbi算法来解决类似的问题。
p.s.该算法也被广泛应用于自然语言的处理上，例如词性的标注，字面上的信息就是我们的观察状态，而要求获得的词性就是隐含状态，通过我们的HMM就可以得到一个符合上下文的最有可能的句法结构分析结果~~~

p.s.说道算法，又想起万恶的朱清新~~~老子的算法大补考成绩怎么还不出来？？？


[ 此贴被zc1984在2007-04-22 12:04重新编辑 ]

查找特定观察序列的概率~~~
也就是传说中的forward算法~~~

我们首先想到的就是穷举法~~~感觉上很龌龊，事实上也证明了的确很龌龊~~
回想我们前面说过的关于股票的例子，如果使用穷举法来计算某个观察状态序列的概率，那么就要求出所有可能的天气状态序列下的概率之和~~，对应股票的（涨平跌）：
假设我们现在观察到大机构投资者进行的操作序列为（买，卖，买），那么有对应（涨，平，跌）共27个可能性：
Pr(买,卖,买|HMM)=Pr(买,卖,买|涨,涨,涨)+Pr(买,卖,买|涨,涨,跌)+..+Pr(买,卖,买|跌,跌,跌)

计算的复杂度是很高的~~
特别是状态空间很大，序列又很长的情况，简直不敢想像~~（例如分析股票的长时间序列~~太可怕了~~）
因此，我们开动脑筋，想到了利用“概率时间不变性”的特点简化计算~~

采用递归的思想解决问题往往能够得到“善终”~
我们采用递归的观点计算观察序列的概率，我们可以定义一个“局部概率”来表示达到状态转换图中某个中间状态的概率。另外，我们把观察序列长度为T的观察序列定义为(Y[k1],Y[k2],Y[k3],...,Y[kT])这种向量形式~~

计算某个中间状态的概率时，可以使用所有达到该状态的路径进行计算。
比如，我们在T=2的时刻，状态为“涨”的概率，就可以通过计算(买,涨)、(买,平)、(买,跌)到状态(卖,涨)而得到。（注意我们开始的假设，庄家的操作序列为（买，卖，买），不要被绕晕了哈~）

定义alpha[T](j)表示在T时刻，状态j的局部概率，计算方式如下：
alpha[T](j)=Pr(观察状态|隐含状态j)*Pr(在T时刻达到状态j的路径)

最后的观察状态的局部概率就等于这些状态所经过的所有可能的路径的概率。这也就是说，最后的局部概率就等于状态转移图中所有路径的概率之和，也就是在HMM下观察序列的概率。

p.s.我们考虑初始状态（这时候没有任何路径可以达到初始状态~~貌似是废话~~）
根据信息论的表述，我们知道初始状态只和自己有关，也就是说：
alpha[1](j)=π(j)*关联观察概率(j,k(1))
也就是说：初始状态的局部概率只和自身的概率和该时刻观察状态的概率有关~~


[ 此贴被zc1984在2007-04-22 14:35重新编辑 ]

接着~~~
前面我们说了一下forward算法的东西，下面继续~~

怎么得到t>1时刻的局部概率呢？这是一个问题~~
回想我们关于局部概率的定义：
alpha[T](j)=Pr(观察状态|隐含状态j)*Pr(在T时刻达到状态j的路径)

我们很容易得到Pr(观察状态|隐含状态j)，那么如何得到Pr(在T时刻达到状态j的路径)呢？
简单的，随着序列的增长，需要计算的路径的数量是指数上升的~但是通过递归的方法，我们已经可以得出所有达到某一个状态的局部概率，因此在计算t+1时刻的状态的局部概率的时候我们就只和t时刻有关了。（大家可以在纸上稍微画一下就明白了，发帖里面夹杂图片貌似很麻烦~~）
alpha[T+1](j)=b[j,k(T+1)]*{Sigma(alpha[T](i)*a[i,j]) From t=1 to n}

这个式子的含义就是恰当的观察概率（状态j下，时刻t+1所真正看到的观察状态的概率）乘以此时所有到达该状态的概率和（前一时刻所有状态的概率与相应的转移概率的积）。因此，我们说在计算t+1时刻的概率时，只用到了t时刻的概率。这样我们就可以计算出整个观察序列的概率。(貌似比较绕~~~大家细心理解~~也可能是我的表述能力比较烂~~)

复杂度的比较结果：
对于观察长度为T的序列，穷举法是指数级别的~~我们的方法（Forward算法）是线性的~~哇咔咔~~~

P.S.貌似有个蝈蝈问我这个计算量会很大，估计你是使用的穷举吧~~来试试Forward算法？


[ 此贴被zc1984在2007-04-22 14:42重新编辑 ]

关于Viterbi算法的内容可以看18楼哈，那位蝈蝈贴出了具体的算法~~~

下面我在补充一点点东西就是了~

Viterbi算法的目的在于找到一个对应观察状态序列的最可能的隐含状态序列~~
穷举不是办法~~
因此也是考虑使用递归~~这一点和Forward算法一致~~

同样是求解局部概率，只不过这里的局部概率的定义发生了一点点改变：
不是到达该状态的所有路径之和，而是其中概率最大的那一条路径！

对于初始状态的值，和Forward的处理方法一样~~

Viterbi算法的优点：
1、降低计算的复杂性~~
2、viterbi会根据输入的观察序列，“自左向右”的根据上下文给出最优的理解。由于viterbi会在给出最终选择前考虑所有的观察序列因素，这样就避免了由于突然的噪声使得决策原理正确答案。这种情况在真实的数据中经常出现。


[ 此贴被zc1984在2007-04-22 20:26重新编辑 ]

关于Learning的东西实在是学习坡度徒增~~~这部分的内容我觉得应该好好的写出来贡献给大家~~~延迟发布~
它让我们可以进行很大的状态空间、观察序列很长的情况下得到合适的HMM参数：初始状态、转移概率和混淆矩阵。

目前我们考虑的都是一阶的马尔科夫过程（貌似这个马尔科夫蝈蝈很刚健~~），我们之后也许会扩展到n维和变维上面去~~

p.s.对于Viterbi算法来说，我们只是得到了一个路径，如果我们需要N-Best呢？配合Stack解码算法进行（A*也是可以的哈~~）~~这样就可以得到多个候选~~

今天就到此为止吧，喝口水，看书去了~~


[ 此贴被zc1984在2007-04-22 20:30重新编辑 ]

占楼~

占楼~

Quote:

引用第6楼zc1984于04-22-2007 13:49发表的:
接着~~~
前面我们说了一下forward算法的东西，下面继续~~

怎么得到t>1时刻的局部概率呢？这是一个问题~~
回想我们关于局部概率的定义：


P.S.貌似有个蝈蝈问我这个计算量会很大，估计你是使用的穷举吧~~来试试Forward算法？
.......

这些都是很简单的............

也没有啥穷举，只不过是解析解.......

而且只是概率的推导而已............

I just say so easy.............

Quote:

引用第11楼jiju84于2007-04-22 18:12发表的:



这些都是很简单的............

.......

那么蝈蝈说的很消耗时间的问题是什么？
使用具体的代码跑过测试了么？
我这里根据HMM做出来的分词速度还是可以的哈~~
2.2GB的纯文本，耗时3个多小时~~
每秒大约200K~250K~~
Athlon64 3200+~~~

这种问题最好是实际的代码进行测试~~
人类认为很大计算量的事情其实对于计算机来说很小case~~~

Quote:

引用第12楼zc1984于04-22-2007 18:22发表的:


那么蝈蝈说的很消耗时间的问题是什么？
使用具体的代码跑过测试了么？
我这里根据HMM做出来的分词速度还是可以的哈~~
.......

HMM理论上比较成功了........

实现是另外一个问题

向刚开始用MLE来初始化观测概率就比较费时间

我现在的想法是可不可以先建一个这个的库，然后在读入

forward只是用来检验HMM训练的，根据设定阀值的大小不知要计算多少次

另外数据平滑中Katz也比较费时间........这里也有2个参数需要估计

//-------------------------------------------------------------
目前这些还没有搞定
..................估计还需要很长时间


网上所谓的分词，即使说是基于HMM的，那也是伪的，包括
AdvancedChineseAnalyze 的Lucene.Net.Analysis.China.dll
这里面的MLE估计是事先整好的
..........................

还有一个问题就是

最终用Viterbi算法分出来的，可能不是全局最优解

尽管有些书上说是全局最有的，但是他大大简化了HMM

A*算法似乎效果要好点，这都要时间！