《用JAVA语言实现离散数学算法》由会员分享，可在线阅读，更多相关《用JAVA语言实现离散数学算法（10页珍藏版）》请在金锄头文库上搜索。
1、用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,B|C)=P(D1,A,B|C
4、)+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转移出去的次数的期望值，是在状态j下观察到
6、活动为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; / 混淆矩阵 ArrayList
7、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, 2, 2, 1,
8、 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 doubleM; PI0
9、= 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 t = 0; t T
10、; 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 T; t+) fo
11、r (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-) for (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 =
