Information Extraction Note (SLP Ch18)

Recently, I wanted to build an information extraction system, so I searched for Google. However there were little Chinese articles, the quality was not so good as well. Fortunately, I found several English ones seemed well, and then the summary is here. The whole structure is based on my favorite NLP book Speech and Language Processing (use SLP instead below), also with some other materials in the reference.

Information extraction (IE), turns the unstructured information extraction information embedded in texts into structured data, for example for populating a relational database to enable further processing. Here is a figure of: Simple Pipeline Architecture for an Information Extraction System.

From: https://www.nltk.org/book/ch07.html

By the way, this book provides actionable steps, focusing on specific actions.

architecture

More

自然语言计算机形式分析的理论与方法笔记(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