自然语言处理基础 | 1 词义消歧

1 WSD

WSD (Word sense disambiguation, 词义消歧): 给定上下文, 确定一个词的语境义 (已知所有可能的意思集合 sense inventory).

• 概率视角: 求出 \(p(y\mid x)\), 其中 \(x\) 为上下文, \(y\) 为单词的某条含义, 取映射 \(g(x)=\argmax_y p(y\mid x)\).

• Discriminative: 直接学习 \(p(y\mid x)\).

• Generative: 先学习 \(p(x,y)\), 然后利用 Bayes 公式: \[ \argmax_y p(y\mid x) = \argmax_y \frac{p(x,y)}{\sum_{y'} p(x\mid y')p(y')} = \argmax_y p(x,y), \] 其中 \(p(x\mid y')p(y')=p_X(x)\) 与变量 \(y\) 无关.

不同的方法:

• Supervised learning:

  • a classification task
    • Naïve Bayes, Linear/Logistic Regression, SVM, Neural Networks...
  • sense inventories are known
  • annotated data available for training

• Unsupervised learning:

  • a clustering task (group word usages according to context)
  • we do not know/have the complete sense inventories
  • plain text data available only
  • cluster data instances into groups:
    • similar within a group
    • discriminative between groups

• Semi-Supervised learning:

  1. obtain a small manually annotated corpus as seeds
  2. bootstrap more annotated
     1. samples top \(K\) output from existing classifier
     2. design rules to extract more samples, e.g., from naturally aligned datasets.
  • limited data with annotations
  • indirect supervision: entries or example sentences in WordNet
  • a lot more textual resources

Heuristics:

• 启发一: (长尾效应) 单词的含义可能有很多, 但是大部分都很罕见. Identify the most often used sense and use this sense by default.
• 启发二: A word tends to preserve its meaning across all its occurrences in a given discourse.
• Lesk 算法: choose the sense with most word overlap between gloss (词汇释义 / 例句) and your input context (上下文).

1.1 Naïve Bayes

A generative model.

设单词 \(w\) 的含义集合 (sense inventory) 为 \({\cal S}=\{s_k\}_{k=1}^n\), 上下文为 \(C\), 上下文的词汇表为 \({\cal V}=\{v_j\}_{j=1}^m\). 我们感兴趣的是 \[ \Align{ s^* &= \argmax_{s_k} P(s_k\mid C) \\ &= \argmax_{s_k} \frac{P(C\mid s_k)P(s_k)}{P(C)} \\ &= \argmax_{s_k} P(C\mid s_k)P(s_k), } \] 其中 \(P(C)\) 与变量 \(s_k\) 无关. 为了简单, 我们做出独立性假设 (independent assumption), 即 \[ P(C\mid s_k) = \prod_{v_x\in C} P(v_x\mid s_k). \] 进而有 \[ s^* = \argmax \prod_{v_x\in C} P(v_x\mid s_k)P(s_k). \] 我们可以通过频率估计概率: \[ \Align{ P(v_x\mid s_k) &= \frac {\textsf{$w$ 以含义 $s_k$ 出现, 且句子中含有 $v_x$ 的次数}} {\textsf{$w$ 以含义 $s_k$ 出现次数}}, \\ P(s_k) &= \frac {\textsf{$w$ 以含义 $s_k$ 出现次数}} {\textsf{$w$ 出现次数}}. } \]

1.2 Evaluation

如何评价模型的好坏?

考虑一般的多分类问题 (\(C\) 个类), 构造混淆矩阵 (confusion matrix) \(M\in\R^{C\times C}\), 其中 \(M_{ij}\) 表示实际为 \(i\) 类中预测为 \(j\) 类的个数. 对角线上表示分类正确的实例, 非对角线为错误的实例.

实例个数	预测 1	预测 2	预测 3	预测 4
实际 1	\(M_{11}\)	\(M_{12}\)	\(M_{13}\)	\(M_{14}\)
实际 2	\(M_{21}\)	\(M_{22}\)	\(M_{23}\)	\(M_{24}\)
实际 3	\(M_{31}\)	\(M_{32}\)	\(M_{33}\)	\(M_{34}\)
实际 4	\(M_{41}\)	\(M_{42}\)	\(M_{43}\)	\(M_{44}\)

准确率 (accuracy) 为分类正确的比例: \[ {\sf acc} := \frac{\sum_i M_{ii}}{\sum_{i,j} M_{ij}}. \] 类别 \(k\) 的精确率 (precision) 为在所有预测为类别 \(k\) 的样本中, 有多少实际属于类别 \(k\) (预测得对不对): \[ {\sf pre}_k := \frac{M_{kk}}{\sum_i M_{ik}}. \] 类别 \(k\) 的召回率 (recall) 为所有实际属于类别 \(k\) 的样本中, 有多少被正确预测为 \(k\) (预测得全不全): \[ {\sf rec}_k := \frac{M_{kk}}{\sum_j M_{kj}}. \]

F-beta 指标定义为 precision 和 recall 的加权调和平均: \[ F_\beta := \frac{1+\beta^2}{\frac1{\sf pre} + \frac{\beta^2}{\sf rec}} = \frac{(\beta^2+1){\sf pre} \cdot {\sf rec}}{\beta^2{\sf pre} + {\sf rec}}. \]

• 一般取 \(\beta=1\) (权重相等).

• Macro F-beta 是不同类别 F1 的平均值 (适用于关注各类别性能均衡的问题): \[ \textsf{Macro-}F_\beta := \frac1C \sum_{k} \textsf{$F_\beta$ of class $k$}. \]

• Micro F-beta 是整体样本的平均 F1 (反映整体分类性能, 对大类别更敏感): \[ \Align{ {\sf pre}_{\sf all} &:= \frac{\sum_k M_{kk}}{\sum_k \sum_i M_{ik}} \rightsquigarrow {\sf acc}, \\ {\sf rec}_{\sf all} &:= \frac{\sum_k M_{kk}}{\sum_k \sum_j M_{kj}} \rightsquigarrow {\sf acc}. } \] 对于单分类问题来说, micro f-beta 等于 accuracy.

1.3 Feature-based discriminative models

1.3.1 Features in NLP

Feature templates:

• 前面的词和后面的词分别是什么?
• 该词是否出现在句首? 是否大写?
• ...

根据一条训练数据 (一个包含当前单词的句子), 可以构造一个 feature vector. 这是一个很长的 0/1 向量, 它的每个分量代表某个特征模版为真 / 假, 比如:

句子: I cash a check in that bank and transfer 100 dollars to my mom. 该句中 bank 的释义为 FI (for finance). 一些 feature 的例子: \[ \Align{ f_1(x,y) &= \Cases{ 1, & \textsf{$w_{-1}=$ that 且 $y=$ FI}, \\ 0, & \textsf{otherwise}, } \\ f_2(x,y) &= \Cases{ 1, & \textsf{$w_{2}=$ hello 且 $y=$ FI}, \\ 0, & \textsf{otherwise}, } \\ f_3(x,y) &= \Cases{ 1, & \textsf{大写且 $y=$ FI}, \\ 0, & \textsf{otherwise}, } \\ \dots\;\;\; } \] Feature 的值: \(f_1(x,{\sf FI})=1\), \(f_2(x,{\sf FI})=0\), \(f_3(x,{\sf FI})=0\).

假设 bank 的释义数量为 \(5\), 上下文长度为 \(10\) (前后各 \(5\) 个词), 词汇表大小为 \(1000\), 除了上下文 feature 外还考虑 "是否在句首" 和 "是否大写", 则 feature 的数量为 \[ 5\times(1000\times10 + 2\times 2) = 50020. \]

假设一共有 \(m\) 个 feature. 对于一个实例 \((x,y)\), 它的 feature vectors 为 \[ \Align{ f(x,y_1) &= [f_1(x,y_1),\dots,f_m(x,y_1)], \\ f(x,y_2) &= [f_1(x,y_2),\dots,f_m(x,y_2)], \\ \dots\hspace{0.9em}& } \] 其中 \(y_1,y_2,\dots\) 为所有释义 (label).

在实际训练中, 一般采用稀疏向量来存储这些特征.

TF-IDF: 文章 \(d\) 中词语 \(t\) 的重要程度, 等于词语频次减去该词语出现的文章频次: \[ \Align{ \textsf{TF}_{t,d} &:= \Cases{ 1 + \log_{10}\textsf{($d$ 中 $t$ 出现的次数)}, & \textsf{次数 $>0$}, \\ 0, & \textsf{otherwise}, } \\ \textsf{IDF}_{t,d} &:= \log_{10} \frac{\textsf{文章总数}}{\textsf{含有 $t$ 的文章数量}}, \\ \textsf{TF-IDF}_{t,d} &:= \textsf{TF}_{t,d} \cdot \textsf{IDF}_{td}. } \]

1.3.2 The log-linear model

构建一个线性分类器, 对于一个输入 \(x\), 构造不同释义下的特征向量 \(f(x,y)\), 分别计算其得分 \({\sf score}(x,y)\), 然后取最大得分的释义 \(y^*\) 作为预测值: \[ \Align{ y^* &= \argmax_y \textsf{score}(x,y) \\ &= \argmax_y \sum_i \lambda_{f_i(x,y)} f_i(x,y) \\ &= \argmax_y (\lambda \cdot f(x,y)) } \] 其中 \(i\) 是特征的下标, 参数向量 \(\lambda=(\lambda_{f_i(x,y)})\). 通过 softmax 函数将 score 映到一个 \([0,1]\) 内的值, 进而可以理解为概率 (exponential model): \[ p_\lambda(y\mid x) = \frac{\exp{\sf score}(x,y)}{\sum_{y'} \exp{\sf score}(x,y')} = \frac{\exp(\lambda \cdot f(x,y))}{\sum_{y'}\exp(\lambda \cdot f(x,y'))}. \] 参数估计采用最大似然法 (MLE). 设训练数据 \(\{(x_k,y_k)\}\), 则似然函数为 \[ \Align{ L(\lambda) = \prod_k p_\lambda(y_k\mid x_k). } \] 似然越大越好. 为了方便优化, 考虑对数似然函数: \[ \ell(\lambda) = \log{L(\lambda)} = \sum_k \lambda\cdot f(x_k,y_k) - \sum_k \log\pqty{\sum_{y'} \exp(\lambda\cdot f(x_k,y'))}, \] 令其导数为零, \[ 0 = \pdv{\ell}{\lambda} = \underbrace{\sum_k f(x_k,y_k)}_{\textsf{empirical count}} - \underbrace{\sum_k\sum_{y} p_\lambda(y\mid x_k) f(x_k,y)} _{\textsf{expected count}}. \] 经验计数 (empirical count) 是特征向量在数据集上的总和; 期望计数 (expected count) 是对所有数据, 计算它在当前模型下 \(f(x_k,y)\) 的期望值, 再求和.

可以采用梯度上升法来最大化对数似然函数:

1. 初始化 \(\lambda\leftarrow0\).
2. 迭代直到收敛:
   1. 计算梯度 \(\Delta\leftarrow\partial\ell/\partial\lambda\).
   2. 计算最优学习率 \(\beta^*\leftarrow\argmax_\beta\ell(\lambda+\beta\Delta)\).
   3. 更新参数 \(\lambda\leftarrow\lambda+\beta^*\Delta\).

也可以采用共轭梯度或者随机梯度上升来加速收敛.

由于训练数据存在 bias, 直接进行梯度上升可能导致过拟合. 我们需要进行参数正则化 (regularization), 让参数的模长不要太大: \[ \ell(\lambda) = \sum_k \lambda\cdot f(x_k,y_k) - \sum_k \log\pqty{\sum_{y'} \exp(\lambda\cdot f(x_k,y'))} - \orange{\frac\alpha2 \|\lambda\|_2^2}. \]