自然语言计算机形式分析的理论与方法笔记(Ch14)

第十四章:隐 Markov 模型

HMM 概述

Markov 链也就是加权自动机。HMM 增加了要求:

  • HMM 有一个观察符号的集合 O,这个集合中的符号不是从状态集合 Q 中的字母抽取的
  • HMM 中观察似然度函数 B 的值不只限于 1 或 0,概率 bi(ot) 可以取 0-1 之间的任何值

HMM 要求的参数如下:

  • 状态序列:Q = (q1, q2, …, qn)
  • 观察序列:O = (o1, o2, …, on)
  • 转换概率:A = (a01, a02, …, ann)
  • 观察似然度:B = bi(ot),表示从状态 i 生成观察值 ot 的概率
  • 初始状态概率分布:π,πi 是 HMM 在状态 i 开始时的概率
  • 接收状态:合法的接收状态集合

需要求解的是 A B π,因此一般使用 λ = {A, B, π} 来定义一个 HMM 模型,模型对外表现出来的是观察序列,状态序列不能直接观察到,被称为 “隐变量”。

三个基本问题:

  • 评估问题:给定观察序列 O 和模型 λ,如何计算由该模型产生该观察序列的概率 P(O|λ)
  • 解码问题:给定观察序列 O 和模型 λ,如何获取在某种意义下最优的状态序列 Q,一般使用 Viterbi 算法
  • 训练问题:如何选择或调整模型参数 λ,使得在该模型下产生观察序列 O 的概率 P(O|λ) 最大

More

自然语言计算机形式分析的理论与方法笔记(Ch13)

第十三章:N 元语法和数据平滑

N 元语法

N 元语法模型利用前面 N-1 个单词来预测下一个词。一些特殊情况:标点、大小写、屈折变化等。

一个单词的概率只依赖于它前面一个单词的这种假设叫作 Markov 假设,这样的模型叫 Bi-gram,即二元语法模型,也叫一阶 Markov 模型。

N 元语法模型可以使用训练语料库 “归一化” 得到。

开头的二元语法计数必定等于 这个单词的计数,于是:

一般化 N 元语法的参数估计:

两个重要事实:

  • N 增加时,精确度相应增加,同时生成句子的局限性增加(可选的下个词减少)
  • 严重依赖于语料库

More

自然语言计算机形式分析的理论与方法笔记(Ch12)

第十二章:Bayes 公式与动态规划算法

拼写错误的检查与更正

1992 年,Kukich 把这个领域分解为三大问题:

  • 非词错误检查
  • 孤立词错误更正
  • 依赖于上下文的错误检查和更正
    • 打字操作时的错误:插入、脱落、改变位置等
    • 书写错误地拼写同音词和准同音词

1964 年 Damerau 发现 80% 的错误由 “单个错误” 引起的:

  • 插入:the→ther
  • 脱落:the→th
  • 替代:the→thw
  • 换位:the→hte

Kukich 把打字错误分为两类:

  • 打字操作错误:一般与键盘有关
  • 认知错误:不知道如何拼写

OCR 错误一般分为五类:替代、多重替代、空白脱落、空白插入和识别失败。

More

自然语言计算机形式分析的理论与方法笔记(Ch11)

第十一章:概率语法

基于规则的句法剖析主要使用 Chomsky 的上下文无关语法。之前的自顶向下、自底向上、左角、CYK、Earley、线图分析法等都对歧义无能为力,于是有了新的改进:一方面是给上下文无关语法的规则加上概率,另一方面是除了加上概率外,还考虑规则的中心词对于规则概率的影响。这些称为 “概率语法”。

More