自然语言处理课程笔记

发表于
| 本文字数： 8.6k

本文为哥伦比亚大学教授Micheal Collins主讲的MOOC自然语言处理（NLP）课程笔记，首发于果壳MOOC学院。

课程涵盖范围：

  • NLP 子问题（NLP sub-problems）：词性标注（part-of-speech tagging）、句法分析（parsing）、词义辨识（word-sense disambiguation）等
  • 机器学习技术（Machine learning techniques）：概率无关上下文语法（probabilistic context-free grammars）、隐马尔可夫模型（hidden markov models）、估值/平滑技术（estimation/smoothing techniques）、EM算法（EM algorithm）、对数线性模型（log-linear models）等
  • 应用（Applications）：信息提取（information extraction）、机器翻译（machine translation）、自然语言界面（natural language interfaces）等

第一周

语言模型（Language Modeling）

  • Trigram 模型：

$$p(x_1 \dots x_n) = \prod_{i=1}^n q(x_i|x_{i-2}, x_{i-1})$$ （马尔可夫链）

  • 评价模型：Perplexity $$\text{Perplexity} = 2^{-l} \quad\text{where}\quad l = \frac{1}{M}\sum_{i=1}^m \log p(s_i)$$

  • 估计 q 值：

    • 最大似然估计（数据不够，需要 smooth）： $$q_{\text{ML}}(w_i|w_{i-2},w_{i-1}) = \frac{\text{Count}(w_{i-2},w_{i-1},w_i)}{\text{Count}(w_{i-2},w_{i-1})}$$
    • 线性插值： $$q(w_i|w_{i-2},w_{i-1}) = \lambda_1 \times q_{\text{ML}}(w_i|w_{i-2},w_{i-1})+ \lambda_2 \times q_{\text{ML}}(w_i|w_{i-1})+ \lambda_3 \times q_{\text{ML}}(w_i)$$
    • Discounting： $$\text{Count}^*(x) = \text{Count}(x) - 0.5$$

  • Katz Back-Off 模型

第二周

标注问题、隐马尔可夫模型（Tagging Problems, Hidden Markov Models）

  • 标注问题：监督式学习（supervised learning）
  • 生成模型（generative model），对联合概率分布建模：$p(x,y)=p(y)p(x|y)$
  • 隐马尔可夫模型（属于生成模型）： $$p(x_1 \dots x_n, y_1 \dots y_{n+1}) = \prod_{i=1}^{n+1} q(y_i|y_{i-2},y_{i-1})\prod_{i=1}^n e(x_i|y_i)$$
  • 标注： $$\arg\max_{y_1\dots y_n} p(x_1\dots x_n,y_1,y_2,\dots,y_n)$$
  • Viterbi 算法：动态规划算法，时间复杂度为 $O(n|S|^3)$

第三周

句法分析、上下文无关语法（Parsing, Context-Free Grammars）

  • 句法分析
  • 上下文无关语法（CFG）：
    • N：非终端符号集（例：N = {S, NP, VP, PP, DT, Vi, Vt, NN, IN}）
    • Σ：终端符号集（例：Σ = {sleeps, saw, man, woman, telescope, the, with, in}）
    • R：$X\rightarrow Y_1Y_2\dots Y_n \quad\text{for}\quad n \geq 0,X \in N, Y_i \in (N \cup \Sigma)$
    • S：开始符

概率上下文无关语法（Probabilistic Context-Free Grammars）

  • 概率上下文无关语法（PCFG，为 CFG 的每一条规则加上概率）
    • 概率： $$p(t)=\prod_{i=1}^n q(\alpha_i\rightarrow \beta_i)$$
    • 计算最高概率的语法树： $$\arg\max_{t\in\mathcal{T}(s)} p(t)$$
    • 最大似然估计： $$q_{\text{ML}}(\alpha\rightarrow \beta) = \frac{\text{Count}(\alpha\rightarrow\beta)}{\text{Count}(\alpha)}$$
    • CKY 算法：动态规划算法

第四周

PCFG 的弱点（Weaknesses of PCFGs）

  • 缺少对词汇信息（lexical information）的敏感度
  • 缺少对结构频率（structural frequencies）的敏感度

词汇化的 PCFG（Lexicalized PCFGs）

  • 中心词（head）：加入中心词的语法树，克服PCFG的弱点
  • PCFG的参数（例：$q(\text{S(saw)}\rightarrow_2\text{NP(man) VP(saw)})$
  • 参数估计（smooth）：
    • 第一步： $$q(\text{S(saw)}\rightarrow_2\text{NP(man) VP(saw)}) = q(\text{S}\rightarrow_2\text{NP VP}|\text{S, saw})\times q(\text{man}|\text{S}\rightarrow_2 \text{NP VP, saw})$$
    • 第二步： $$q(\text{S}\rightarrow_2\text{NP VP}|\text{S, saw})=\lambda_1 \times q_{\text{ML}}(\text{S}\rightarrow_2\text{NP VP}|\text{S, saw}) + \lambda_2 \times q_{\text{ML}}(\text{S}\rightarrow_2\text{NP VP}|\text{S})$$

$$q(\text{man}|\text{S}\rightarrow_2 \text{NP VP, saw}) =\lambda_3 \times q_{\text{ML}}(\text{man}|\text{S}\rightarrow_2 \text{NP VP, saw}) + \lambda_4 \times q(\text{man}|\text{S}\rightarrow_2 \text{NP VP})+ \lambda_5 \times q_{\text{ML}} (\text{man}|\text{NP})$$

  • 评价：准确率（precision）、召回率（recall）

第五周

机器翻译（Machine Translation）

  • 挑战：词汇歧义、不同语序、句法结构……

  • 经典机器翻译：

    • 直接翻译
    • 基于转换（transfer-based）的机器翻译：分析→转换语法树→生成（例：Systran 系统）
    • 跨语言（interlingua-based）的机器翻译：分析（独立于语言的表示）→生成

  • 统计机器翻译（statistical MT）：噪声信道模型（noisy channel model），以法翻英为例

    • 语言模型：$p(e)$，可以为 Trigram 模型
    • 翻译模型：$p(f|e)$
    • $p(e|f) = \frac{p(e,f)}{p(f)} = \frac{p(e)p(f|e)}{\sum_e p(e)p(f|e)}$
    • $\arg\max_e p(e|f) = \arg\max_e p(e)p(f|e)$

IBM 翻译模型（The IBM Translation Models）

  • IBM 模型 1

    • 定义英文句 e 有 l 个词汇，法文句 f 有 m 个词汇
    • 对齐（alignment）a 为${a_i\dots a_m}$
    • 模型： $$p(f,a|e,m)=p(a|e,m)p(f|a,e,m)$$ $$p(f|e,m)=\sum_{a\in \mathcal{A}} p(a|e,m)p(f|a,e,m)$$ 其中， $$p(a|e,m)=\frac{1}{(l+1)^m}$$ $$p(f|a,e,m)=\prod_{j=1}^m t(f_j|e_{a_j})$$
    • 副产品：复原 alignment（现在最初的 IBM 模型已很少用于翻译，但仍用于复原 alignment） $$p(a|f,e,m) = \frac{p(f,a|e,m)}{\sum_{a\in \mathcal{A}} p(f,a|e,m)}$$ $$a^*= \arg\max_a p(a|f,e,m)$$

  • IBM 模型 2

    • 与 IBM 模型 1 的区别： $$p(a|e,m) = \prod_{j=1}^m \mathbf{q}(a_j|j,l,m)$$
    • 复原 alignment： $$a_j = \arg\max_{a\in {0\dots l}} q(a|j,l,m)\times t(f_j|e_a)$$

  • 参数估计（t、q）：EM算法（该算法会收敛到 log 似然函数的局部最优解）

第六周

基于短语的翻译（Phrase-Based Translation）

  • 从 alignment 中学习短语

    • 通过 IBM 模型 2（$p(e|f)$）得到 alignment矩阵
    • 从矩阵提取短语对 $$t(f|e)=\frac{\text{Count}(f,e)}{\text{Count}(e)}$$

  • 基于短语的翻译模型 $$\text{Score} = \underbrace{\log q(\text{we}|\text{*, Today}) + \log q(\text{shall}|\text{Today, we}) + \log q(\text{be}|\text{we, shall})}_{\text{Language model}}$$

$$+ \underbrace{\log t(\text{werden wir}|\text{we shall be})}_{\text{Phrase model}}$$

$$+ \underbrace{\eta\times 0}_{\text{Distortion model}}$$

  • p：短语 tuple (s, t, e)，表示源语言的 $x_s\dots x_t$ 译为目标语言的 e（例：(1, 3, we must also)）
  • y：短语的有限序列 $p_1,p_2,\dots p_L$
  • $\mathcal{Y}(x)$：满足一定条件的 y 的集合
  • 最优翻译： $$\arg\max_{y\in\mathcal{Y}(x)}f(y)$$
  • 任一 y 的得分： $$h(e(y))+\sum_{k=1}^L g(p_k) + \sum_{k=1}^{L-1}\eta\times|t(p_k)+1-s(p_{k+1})|$$ 其中，h 为 Trigram 模型得分，g 为基于短语的得分
  • 解码算法（decoding algorithm）

第七周

对数线性模型（Log-Linear Models）

  • 对数线性模型：

    • 条件概率：$p(y|x)$
    • 特征：$f(x,y)\in\mathbb{R}^m$
    • 参数向量：$v\in\mathbb{R}^m$
    • 得分： $$v\cdot f(x,y) = \sum_k v_k f_k(x,y)$$
    • 模型： $$p(y|x;v)=\frac{e^{v\cdot f(x,y)}}{\sum_{y'\in \mathcal{Y}}e^{v\cdot f(x,y')}}$$

    $$\log p(y|x;v)= \underbrace{v\cdot f(x,y)}_{\text{Linear term}}$$

    $$- \underbrace{\log\sum_{y'\in\mathcal{Y}}e^{v\cdot f(x,y')}}_{\text{Normalization term}}$$

  • 参数估计：

    • 最大似然估计： $$v_{\text{ML}} = \arg\max_{v\in\mathbb{R}^m}L(v)$$

$$L(v) = \sum_{i=1}^n\log p(y^{(i)} | x^{(i)};v)= \sum_{i=1}^n v\cdot f(x^{(i)}, y^{(i)}) - \sum_{i=1}^n \log\sum_{y' \in \mathcal{Y}} e^{v \cdot f(x^{(i)}, y')}$$

  • 梯度上升法（gradient ascent method）
  • 规则化（regularization）： $$L(v) = \sum_{i=1}^n v \cdot f(x^{(i)}, y^{(i)}) - \sum_{i=1}^n \log\sum_{y' \in \mathcal{Y}}e^{v \cdot f(x^{(i)} ,y')} -\frac{\lambda}{2} \sum_{k=1}^m v_k^2$$

第八周

用于标注的对数线性模型（Log-linear Models for Tagging）

  • 标注序列： $$t_{[1:n]}^* = \arg\max_{t_{[1:n]}}p(t_{[1:n]}|w_{[1:n]})$$

  • Trigram 对数线性 tagger $$p(t_{[1:n]}|w_{[1:n]})= \underbrace{\prod_{j=1}^n p(t_j|w_1\dots w_n,t_1\dots t_{j-1})}_{\text{Chain rule}}$$

$$= \underbrace{\prod_{j=1}^n p(t_j|w_1\dots w_n,t_{j-2},t_{j-1})}_{\text{Independence assumption}}$$

  • 训练模型：
  • 4-tuple 历史：$\langle t_{-2},t_{-1},w_{[1:n]},i \rangle$

$$v^*=\arg\max_v\big(\underbrace{\sum_i \log p(y_i|x_i;v)}_{\text{Log-likelihood}}$$

$$- \underbrace{\frac{\lambda}{2} \sum_k v_k^2}_{\text{Regularizer}}\big)$$

  • Viterbi 算法

基于历史的语法分析的对数线性模型（Log-Linear Models for History-based Parsing）

  • 第一步：将树表示为 decision 序列（Ratnaparkhi's Parser） $$T=\langle d_1,d_2,\dots d_m \rangle$$

    • 第一层：标注
    • 第二层：chunks
    • 第三层：其他结构

  • 第二步：树的概率为 $$p(T|S)=\prod_{i=1}^m p(d_i|d_1\dots d_{i-1},S)$$

  • 第三步：使用对数线性模型估计 $$p(d_i|d_1\dots d_{i-1},S) = \frac{e^{f(\langle d_1\dots d_{i-1},S\rangle,d_i)\cdot v}}{\sum_{d\in\mathcal{A}}e^{f(\langle d_1\dots d_{i-1},S\rangle,d_i)\cdot v}}$$

    • 定义 f

  • 第四步：搜寻问题 Beam Search 方法（不能用动态规划算法）

第九周

非监督式学习：布朗聚类（Unsupervised Learning: Brown Clustering）

  • 布朗聚类算法：

    • 输入：语料库
    • 输出：词的聚类（或进一步，分级的词聚类）

  • 模型： $$p(w_1,w_2,\dots w_n) = \prod_{i=1}^n e(w_i|C(w_i)) q(C(w_i)|C(w_{i-1}))$$

  • C的质量： $$\text{Quality}( C ) = \sum_{i=1}^n \log e(w_i|C(w_i)) q(C(w_i)|C(w_{i-1}))= \sum_{c=1}^k \sum_{c'=1}^k p(c,c')\log \frac{p(c,c')}{p( c )p(c')} + G$$ 其中， $$p(c,c')=\frac{n(c,c')}{\sum_{c,c'}n(c,c')}\quad p( c )=\frac{n( c )}{\sum_c n( c )}$$

  • 算法一

    • 每一词有其自己的聚类，共$|\mathcal{V}|$类
    • 进行$(|\mathcal{V}|-k)$次合并，每次合并使 Quality( C ) 最大的两个类

  • 算法二：

    • 最常见的 m 个词都有其自己的聚类
    • 之后每一步建立一个新聚类，再合并使 Quality( C ) 最大的两个类

全局线性模型（Global Linear Models）

  • 截至目前为止的所有模型都是基于历史（history-based）的模型（例：PCFG、对数线性 tagger）

  • 全局线性模型：

    • 三个要素： 特征向量$\mathbf{f}(x,y)\in\mathbb{R}^d$ 候选$\mathbf{GEN}(x)$ 参数向量$\mathbf{v}$
    • 函数 $$F(x)=\arg\max_{y\in\mathbf{GEN}(x)}\mathbf{f}(x,y)\cdot\mathbf{v}$$

  • 参数估计：

    • 感知器算法（perception algorithm）
    • Boosting
    • 对数线性模型（最大似然）

第十周

标注的感知器算法（The Perceptron Algorithm for Tagging）

  • 感知器算法 $$\text{For}\quad t=1\dots T,i=1\dots n$$

$$z_i = F(x_i)$$

$$\text{If}\quad (z_i \neq y_i) \quad \mathbf{v} = \mathbf{v} + \mathbf{f}(x_i,y_i) - \mathbf{f}(x_i,z_i)$$

  • 全局特征 通过局部特征定义全局特征：

$$F(w_{[1:n]}) =\arg\max_{t_{[1:n]}\in \mathbf{GEN} (w_{[1:n]})} \mathbf{v}\cdot \mathbf{f}(w_{[1:n]},t_{[1:n]})$$

$$= \arg\max_{t_{[1:n]}\in \mathbf{GEN} (w_{[1:n]})} \mathbf{v}\cdot\sum_{i=1}^n g(h_i,t_i) = \arg\max_{t_{[1:n]}\in \mathbf{GEN} (w_{[1:n]})} \sum_{i=1}^n\mathbf{v}\cdot g(h_i,t_i)$$

  • 使用感知器算法训练 tagger

依存句法分析的感知器算法（The Perception Algorithm for Dependency Parsing）

  • 依存句法分析

    • 依存（dependency）表示为$(h,m)$，分别为首词和修饰词的序号
    • 时间复杂度为 $O(n^5 G^3)$）

  • 全局线性模型 $$\arg\max_{y\in \mathbf{GEN} (x)} \mathbf{w}\cdot \mathbf{f}(x,y) = \arg\max_{y\in \mathbf{GEN} (x)} \sum_{(h,m)\in y}\mathbf{w}\cdot \mathbf{g}(x,h,m)$$