用JAVA语言实现离散数学算法.docx

1、用JAVA语言实现离散数学算法用JAVA语言实现离散数学算法* 显示离散数学算法的真值表 * 提供将一个中缀合适公式的真值表输出到某一PrintStream流中的功能 * 以单个大写字母表示变量（支持26个变量） * 以字符0或者1表示值 * 以 & - 分别表示 非 析取 合取 条件 双条件 连接词 * 支持 ( )（括号） * 如果公式中有错误将不会输入真值表（将会输出错误信息）说明：以 & - 分别表示 非 析取 合取 条件 双条件 连接词以单个大写字母表示变量（支持26个变量）以字符0或者1表示值，式子中的T与F支持 ( )（括号）如果公式中有错误将不会输入真值表（将会输出错误信息）注

2、意：输出的结果会同时显示到屏幕与该程序的同目录下的“真值表结果.txt”文件中直接按回车键（输入为空）则会退出程序例如：输入 AB-(1&C)则会显示该合适公式是 AB-(1&C)A B C Key0 0 0 01 0 0 00 1 0 01 1 0 10 0 1 01 0 1 00 1 1 01 1 1 1收起在HMM模型中，已知隐藏状态的集合S，观察值的集合O，以及一个观察序列（o1,o2,.,on），求使得该观察序列出现的可能性最大的模型参数（包括初始状态概率矩阵，状态转移矩阵A，发射矩阵B）。这正好就是离散数学算法要求解的问题：已知一系列的观察值X，在隐含变量Y未知的情况下求最佳参数*

3、，使得：在中文词性标注里，根据为训练语料，我们观察到了一系列的词（对应离散数学中的X），如果每个词的词性（即隐藏状态）也是知道的，那它就不需要用离散数学来求模型参数了，因为Y是已知的，不存在隐含变量了。当没有隐含变量时，直接用maximum likelihood就可以把模型参数求出来。预备知识首先你得对下面的公式表示认同。以下都是针对相互独立的事件，P(A,B)=P(B|A)*P(A)P(A,B,C)=P(C)*P(A,B|C)=P(A,C|B)*P(B)=P(B,C|A)*P(A)P(A,B,C,D)=P(D)*P(A,B|D)*P(C|A)=P(D)*P(A,B|D)*P(C|B)P(A,

4、B|C)=P(D1,A,B|C)+P(D2,A,B|C) D1,D2是事件D的一个全划分理解了上面几个式子，你也就能理解本文中出现的公式是怎么推导出来的了。离散数学算法求解我们已经知道如果隐含变量Y是已知的，那么求解模型参数直接利用Maximum Likelihood就可以了。离散数学算法的基本思路是：随机初始化一组参数(0)，根据后验概率Pr(Y|X;)来更新Y的期望E(Y)，然后用E(Y)代替Y求出新的模型参数(1)。如此迭代直到趋于稳定。在HMM问题中，隐含变量自然就是状态变量，要求状态变量的期望值，其实就是求时刻ti观察到xi时处于状态si的概率，为了求此概率，需要用到向前变量和向后变

5、量。向前变量向前变量是假定的参数它表示t时刻满足状态，且t时刻之前（包括t时刻）满足给定的观测序列的概率。1.令初始值2.归纳法计算3.最后计算复杂度向后变量向后变量 它表示在时刻t出现状态，且t时刻以后的观察序列满足的概率。1.初始值2.归纳计算E-Step定义变量为t时刻处于状态i，t+1时刻处于状态j的概率。 定义变量表示t时刻呈现状态i的概率。实际上 是从其他所有状态转移到状态i的次数的期望值。是从状态i转移出去的次数的期望值。是从状态i转移到状态j的次数的期望值。M-Step是在初始时刻出现状态i的频率的期望值，是从状态i转移到状态j的次数的期望值 除以从状态i转移出去的次数的期望值

6、，是在状态j下观察到活动为k的次数的期望值除以从其他所有状态转移到状态j的次数的期望值,然后用新的参数再来计算向前变量、向后变量、和。如此循环迭代，直到前后两次参数的变化量小于某个值为止。下面给出我的java代码：package nlp;/* * author Orisun * date 2011-10-22 */import java.util.ArrayList;public class BaumWelch int M; / 隐藏状态的种数 int N; / 输出活动的种数 double PI; / 初始状态概率矩阵 double A; / 状态转移矩阵 double B; / 混淆矩阵

7、ArrayList observation = new ArrayList(); / 观察到的集合 ArrayList state = new ArrayList(); / 中间状态集合 int out_seq = 2, 1, 1, 1, 2, 2, 2, 2, 2, 1, 1, 1, 1, 2, 2, 2, 2, 1, 1, 1, 1, 1, 2, 2, 2, 1, 1, 1, 1, 1, 2, 1 ; / 测试用的观察序列 int hidden_seq = 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 2

8、, 2, 2, 1, 1, 1, 1, 1, 1, 1 ; / 测试用的隐藏状态序列 int T = 32; / 序列长度为32 double alpha = new doubleT; / 向前变量 double PO; double beta = new doubleT; / 向后变量 double gamma = new doubleT; double xi = new doubleT - 1; / 初始化参数。Baum-Welch得到的是局部最优解，所以初始参数直接影响解的好坏 public void initParameters() M = 2; N = 2; PI = new dou

9、bleM; PI0 = 0.5; PI1 = 0.5; A = new doubleM; B = new doubleM; for (int i = 0; i M; i+) Ai = new doubleM; Bi = new doubleN; A00 = 0.8125; A01 = 0.1875; A10 = 0.2; A11 = 0.8; B00 = 0.875; B01 = 0.125; B10 = 0.25; B11 = 0.75; observation.add(1); observation.add(2); state.add(1); state.add(2); for (int

10、t = 0; t T; t+) alphat = new doubleM; betat = new doubleM; gammat = new doubleM; for (int t = 0; t T - 1; t+) xit = new doubleM; for (int i = 0; i M; i+) xiti = new doubleM; / 更新向前变量 public void updateAlpha() for (int i = 0; i M; i+) alpha0i = PIi * Biobservation.indexOf(out_seq0); for (int t = 1; t

11、 T; t+) for (int i = 0; i M; i+) alphati = 0; for (int j = 0; j M; j+) alphati += alphat - 1j * Aji; alphati *= Biobservation.indexOf(out_seqt); / 更新观察序列出现的概率，它在一些公式中当分母 public void updatePO() for (int i = 0; i M; i+) PO += alphaT - 1i; / 更新向后变量 public void updateBeta() for (int i = 0; i = 0; t-) fo

12、r (int i = 0; i M; i+) for (int j = 0; j M; j+) betati += Aij * Bjobservation.indexOf(out_seqt + 1) * betat + 1j; / 更新xi public void updateXi() for (int t = 0; t T - 1; t+) double frac = 0.0; for (int i = 0; i M; i+) for (int j = 0; j M; j+) frac += alphati * Aij * Bjobservation.indexOf(out_seqt + 1

13、) * betat + 1j; for (int i = 0; i M; i+) for (int j = 0; j M; j+) xitij = alphati * Aij * Bjobservation.indexOf(out_seqt + 1) * betat + 1j / frac; / 更新gamma public void updateGamma() for (int t = 0; t T - 1; t+) double frac = 0.0; for (int i = 0; i M; i+) frac += alphati * betati; / double frac = PO

14、; for (int i = 0; i M; i+) gammati = alphati * betati / frac; / for(int i=0;iM;i+) / gammati=0; / for(int j=0;jM;j+) / gammati+=xitij; / / 更新状态概率矩阵 public void updatePI() for (int i = 0; i M; i+) PIi = gamma0i; / 更新状态转移矩阵 public void updateA() for (int i = 0; i M; i+) double frac = 0.0; for (int t =

15、 0; t T - 1; t+) frac += gammati; for (int j = 0; j M; j+) double d离散数学 = 0.0; / for (int t = 0; t T - 1; t+) / d离散数学 += xitij; / for (int k = 0; k M; k+) / frac += xitik; / for (int t = 0; t T - 1; t+) d离散数学 += xitij; Aij = d离散数学 / frac; / 更新混淆矩阵 public void updateB() for (int i = 0; i M; i+) doubl

16、e frac = 0.0; for (int t = 0; t T; t+) frac += gammati; for (int j = 0; j N; j+) double d离散数学 = 0.0; for (int t = 0; t 0) / E-Step updateAlpha(); / updatePO(); updateBeta(); updateGamma(); updatePI(); updateXi(); / M-Step updateA(); updateB(); public static void main(String args) BaumWelch bw = new

17、BaumWelch(); bw.run(); Syst离散数学.out.println(训练后的初始状态概率矩阵：); for (int i = 0; i bw.M; i+) Syst离散数学.out.print(bw.PIi + t); Syst离散数学.out.println(); Syst离散数学.out.println(训练后的状态转移矩阵：); for (int i = 0; i bw.M; i+) for (int j = 0; j bw.M; j+) Syst离散数学.out.print(bw.Aij + t); Syst离散数学.out.println(); Syst离散数学.

18、out.println(训练后的混淆矩阵：); for (int i = 0; i bw.M; i+) for (int j = 0; j bw.N; j+) Syst离散数学.out.print(bw.Bij + t); Syst离散数学.out.println(); 迭代22次后得到的参数：训练后的初始状态概率矩阵：6.72801479161809E-301.0训练后的状态转移矩阵：0.76720211710795320.232821659287658270.357061195165864760.6429096688758965训练后的混淆矩阵：0.99589658628791480.0041034137120853992.135*1061E-60.9999978649801687