跳到主要内容

東京大学 情報理工学系研究科 コンピュータ科学専攻 2019年8月実施 専門科目II 問題2

标签：

Author​

祭音Myyura (co-authored with GPT 5.6 SOL)

Description​

题目描述​

对句子（单词序列）w=(w1,…,wℓ)\mathbf w=(w_1,\ldots,w_\ell)，输出词性序列 t=(t1,…,tℓ)\mathbf t=(t_1,\ldots,t_\ell)。例如 (John, wrote, a, book) 对应 (NOUN, VERB, DET, NOUN)。W,TW,T 分别是有限的单词集、词性集。训练数据为已标注语料

D={(w(k),t(k))∣k=1,…,N},N>0.D=\{(\mathbf w^{(k)},\mathbf t^{(k)})\mid k=1,\ldots,N\},\qquad N>0.

（1）定义

pu(t∣w)=∏i=1∣w∣pu(ti∣wi).p_u(\mathbf t\mid\mathbf w)=\prod_{i=1}^{|\mathbf w|}p_u(t_i\mid w_i).

假设各训练样本独立服从此条件分布，说明如何求 pu(t∣w)p_u(t\mid w) 的最大似然估计。

（2）已知全部 pu(t∣w)p_u(t\mid w)，给出对任意输入句子求最大概率词性序列的算法。

（3）令 vv 为 ww 的前一个单词；句首前词记为特殊符号 〈s〉。定义

pb(t∣w)=pb(t1∣⟨s⟩,w1)∏i=2∣w∣pb(ti∣wi−1,wi).p_b(\mathbf t\mid\mathbf w) =p_b(t_1\mid\langle s\rangle,w_1) \prod_{i=2}^{|\mathbf w|}p_b(t_i\mid w_{i-1},w_i).

说明如何由独立训练数据求 pb(t∣v,w)p_b(t\mid v,w) 的最大似然估计，以及已知这些概率时如何求最优词性序列。

（4）解释使用隐马尔可夫模型（HMM）为什么有望比（1）至（3）更准确。给出 HMM 的定义和词性标注算法，并举例说明局部方法可能错误而 HMM 正确的情形。

Kai​

(1)​

记 C(w,t)C(w,t) 为训练集中单词 ww 标为 tt 的次数，C(w)=∑tC(w,t)C(w)=\sum_tC(w,t)。对数似然为

∑w,tC(w,t)log⁡pu(t∣w).\sum_{w,t}C(w,t)\log p_u(t\mid w).

对每个 ww，在 ∑tpu(t∣w)=1\sum_t p_u(t\mid w)=1 下最大化，得到

p^u(t∣w)=C(w,t)/C(w)(C(w)>0).\boxed{\widehat p_u(t\mid w)=C(w,t)/C(w)\quad(C(w)>0).}

若 C(w)=0C(w)=0，似然不约束该条件分布，任意归一化分布都是最大似然解。

(2)​

各位置相互独立，故逐词取

ti∈arg⁡max⁡t∈Tpu(t∣wi).\boxed{t_i\in\arg\max_{t\in T}p_u(t\mid w_i).}

时间为 O(ℓ∣T∣)O(\ell|T|)；并列时任选。

(3)​

记 C(v,w,t)C(v,w,t) 为前词 vv、当前词 ww、当前词性 tt 的次数，句首也计入。则

p^b(t∣v,w)=C(v,w,t)∑r∈TC(v,w,r)\boxed{\widehat p_b(t\mid v,w)=\frac{C(v,w,t)}{\sum_{r\in T}C(v,w,r)}}

（分母为零时条件分布任意）。给定句子后所有前词已知，各词性仍相互独立，故逐个取

ti∈arg⁡max⁡t∈Tpb(t∣wi−1,wi),w0=⟨s⟩.t_i\in\arg\max_{t\in T}p_b(t\mid w_{i-1},w_i),\qquad w_0=\langle s\rangle.

时间仍为 O(ℓ∣T∣)O(\ell|T|)。

(4)​

HMM 将词性 tit_i 作为隐状态，单词 wiw_i 作为观测。隐状态满足一阶 Markov 性，观测在给定状态后条件独立：

p(w,t)=π(t1)bt1(w1)∏i=2ℓa(ti−1,ti)bti(wi),p(\mathbf w,\mathbf t)=\pi(t_1)b_{t_1}(w_1) \prod_{i=2}^{\ell}a(t_{i-1},t_i)b_{t_i}(w_i),

其中 π\pi 为初始概率，aa 为词性转移概率，bb 为词性给定时的发词概率，可由标注语料的相应频数估计。

用 Viterbi 动态规划：

D1(t)=π(t)bt(w1),Di(t)=bt(wi)max⁡r∈TDi−1(r)a(r,t).D_1(t)=\pi(t)b_t(w_1),\qquad D_i(t)=b_t(w_i)\max_{r\in T}D_{i-1}(r)a(r,t).

记录每次最大化的前驱，在末尾选最大值并回溯，得到最优序列，时间 O(ℓ∣T∣2)O(\ell|T|^2)。

例如在 They can fish 中，fish 可为名词或动词。若局部模型将 fish 及词对 (can, fish) 均偏向名词，就会误标。HMM 能利用 can 的情态动词词性以及“情态动词后接动词”的高概率选择动词。

具体地，若对前缀的最优路径已以 MODAL 结束，且 a(MODAL,VERB)=0.9a(\mathrm{MODAL},\mathrm{VERB})=0.9、a(MODAL,NOUN)=0.1a(\mathrm{MODAL},\mathrm{NOUN})=0.1，又有 bVERB(fish)=0.4b_{\mathrm{VERB}}(\text{fish})=0.4、bNOUN(fish)=0.6b_{\mathrm{NOUN}}(\text{fish})=0.6，则后续得分分别为 0.360.36 与 0.060.06，HMM 选择正确的动词。HMM 利用词性间的联系和全句信息；准确率的提高取决于数据与参数，并非对每个句子都有保证。

本页目录