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

用JAVA语言实现离散数学算法 * 显示离散数学算法的真值表 * 提供将一个中缀合适公式的真值表输出到某一PrintStream流中的功能 * 以单个大写字母表示变量（支持26个变量） * 以字符0或者1表示值 * 以 ~ ^ - 分别表示 非 析取 合取 条件 双条件 连接词 * 支持 ( )（括号） * 如果公式中有错误将不会输入真值表（将会输出错误信息） 说明：以 ~ ^ - 分别表示 非 析取 合取 条件 双条件 连接词 以单个大写字母表示变量（支持26个变量） 以字符0或者1表示值，式子中的T与F 支持 ( )（括号） 如果公式中有错误将不会输入真值表（将会输出错误信息） 注意：输出的结果会同时显示到屏幕与该程序的同目录下的“真值表结果.txt”文件中 直接按回车键（输入为空）则会退出程序 例如：输入 A^B-(1C)则会显示 该合适公式是 A^B-(1C) A B C Key 0 0 0 0 1 0 0 0 0 1 0 0 1 1 0 1 0 0 1 0 1 0 1 0 0 1 1 0 1 1 1 1收起 在HMM模型中，已知隐藏状态的集合S，观察值的集合O，以及一个观察序列（o1,o2,...,on），求使得该观察序列出现的可能性最大的模型参数（包括初始状态概率矩阵π，状态转移矩阵A，发射矩阵B）。这正好就是离散数学算法要求解的问题：已知一系列的观察值X，在隐含变量Y未知的情况下求最佳参数θ*，使得： 在中文词性标注里，根据为训练语料，我们观察到了一系列的词（对应离散数学中的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)+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的概率，为了求此概率，需要用到向前变量和向后变量。 向前变量 向前变量?是假定的参数 它表示t时刻满足状态，且t时刻之前（包括t时刻）满足给定的观测序列的概率。 令初始值 归纳法计算 最后计算 复杂度 向后变量 向后变量? ? ? ? ? ? ? ? 它表示在时刻t出现状态，且t时刻以后的观察序列满足的概率。 初始值 归纳计算 E-Step 定义变量为t时刻处于状态i，t+1时刻处于状态j的概率。 ? ? ? ?? 定义变量表示t时刻呈现状态i的概率。 实际上? ?? ?? ? ?? ? 是从其他所有状态转移到状态i的次数的期望值。 是从状态i转移出去的次数的期望值。 是从状态i转移到状态j的次数的期望值。 M-Step 是在初始时刻出现状态i的频率的期望值， 是从状态i转移到状态j的次数的期望值 ???从状态i转移出去的次数的期望值， 是在状态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; // 混淆矩阵 ArrayListInteger observation = new Arra