Coursera NLP specialization Course 2

Week 1

auto correct

元ネタはこれらしい。 Peter NorvigというGoogleの研究部門を率いた人の記事。

単語に分割するのに、re.split(r"\s+", seltence)を使うか、re.findall(r"\w+", sentence)を使うか。 結論から言うと、findall, r"\w+"を使った方が良い。r"\s+"でsplitすると、”print,”みたいな単語も含まれてしまう。

minimum edit distance

文字列$x$を$y$に変更するのに必要な最小手順を求めたい。 ただし、加えられる変更と、その変更のコストは以下の通りとする

• 1文字削除 コスト1
• 1文字挿入 コスト1
• 1文字置換 コスト2

$x,y$の長さを$m,n$としたとき、

$$D_{00} = 0 \\ D_{ij} = \mathrm{min}(D_{i-1,j} + 1, D_{i,j-1} + 1, D_{i-1,j-1} + R_{ij}) \\ i = 0, 1, \ldots, m \\ j = 0, 1, \ldots, n$$

という漸化式を計算すれば良い。ただし、$R_{ij}$は、$x_i == y_j$なら0、そうでないなら$2$である。

ここで、$D_{ij}$は、$x[:i]$を$y[:j]$に変更する最小コストを表している。

• $D_{00}$は空文字を空文字に変更するコストなので0
• $x[:i]$を$y[:j]$に変換するには、
  • $x[:i]$の末尾を削除して、$x[:i-1]$を$y[:j]$に変更する
  • $x[:i]$を$y[:j-1]$に変更して、$y[j]$を最後に挿入する
  • $x[:i-1]$を$y[:j-1]$に変更して、必要なら1文字入れ替える

  のどれかで得られる。

ということ

Week 2

programming assignment

Viterviアルゴリズムを実装する。

用意するもの

• トレーニング用データ
  • 文章の各単語にPOSを付与したもの
  • 生のコーパスから未知語の処理を行う。生コーパスに1回しか現れなかったものは未知語とみなされる
  • 未知語も、単に未知語とラベルを付けるだけではなくて、「動詞っぽい」「形容詞っぽい」などカテゴリに分けてラベルを付ける（語尾で判断する）
  • これにより、2回以上現れる単語とラベル付与された未知語の集合が語彙となる
• テストデータ
  • 文章の各単語にPOSを付与したもの
• transition matrix: あるタグが与えられた時のタグの確率分布 タグの数 x タグの数の確率行列（要素が非負で行和が1）
• emission matrix: あるタグが与えられた時の単語の確率分布 タグの数 x 語彙サイズの確率行列

確率の計算の際には、ラプラススムージングを行う。 分子に$\mathrm{カウント数} + \alpha$を使い、その分、分母を補正する方法。$\alpha$は適当に小さな値に決める。

viterbi アルゴリズムの一般的な説明

まず、隠れマルコフモデルを以下で定義する。

• 隠れ状態 $s_i, i = 1, \ldots, T, s_i\in \{1, .., S\}$
• 観測変数 $y_i, i = 1, \ldots, T, y_i\in \{1, .., Y\}$
• 初期状態の確率分布 $p_i, i \in \{1, .., S \}$
• 状態遷移行列 $A_{ij}, i, j \in \{1, .., Y\}$
• 観測行列 $B_{ij}, i \in \{1, .., S\}, j \in \{1, .., Y\}$

viterbiアルゴリズムは、$y_1, .., y_T$が与えられた元での$s_1, .., s_T$を最尤推定するアルゴリズムである。

$y_1$を観測した時、$s_1$の尤度は、

$$f(s_1) = p[s_1] B[s_1, y_1]$$

で与えられる。

次に、$y_1, y_2$を観測した時の$s_1, s_2$の尤度を考えると

$$f(s_1, s_2) = p[s_1] B[s_1, y_1] A[s_1, s_2] B[s_2, y_2]$$

で与えられることが分かる。以下、同様に考えれば$y_1, .., y_T$を観測した時の $s_1, .., s_T$の尤度は

$$f(s_1, s_2, .., s_T) = p[s_1] B[s_1, y_1] A[s_1, s_2] B[s_2, y_2] .. A[s_{T-1}, s_T] B[s_T, y_T]$$

これが最大化したい値である。ここで、上の式において次の2つがポイントになる

• 最後の$A[s_{T-1}, s_T] B[s_T, y_T]$以外は$s_T, y_T$に依存しない
• そこに出てくる$A[s_{T-1}, s_T] B[s_T, y_T]$で、他に出てくる変数は$s_{T-1}$だけ

したがって、$s_{T-1}=1, .., S$の場合の最大尤度だけを覚えておけば、そこから全体の最大尤度が計算できる。

以上を念頭に置いてアルゴリズムを設計すれば、自然にviterbiアルゴリズムになるはず。

week 3

nltk

natural language tool kit.

開始単語と終了単語

n-gramモデルを作る時に、最初のn-1単語は、十分な文脈を持たない。そこで、n-1個の特別な開始単語を文章に付ける。

任意の長さの文章を生成したり確率を評価するためには、文がどこで終わるかを識別する必要がある。そのために、1個の特別な終了単語を文末に付ける。

perplexity

文章$W$に対して、$\mathrm{Pr}(W)^{-\frac{1}{m}}$をperplexityと呼ぶ。ただし、$m$は文章の長さである。 対数を取ると

$$- \frac{1}{m} \log_2 \mathrm{Pr}(W)$$

となる。言葉で意味を言うと、一単語あたりの平均情報量、ということになる。この値が低いほど良いモデルとみなされる。

モデルの評価は、テスト用コーパスの全文章を連結した文章のperplexityを見る。 目安としてperplexityが20〜60くらいなら、良いモデルと思えるらしい。log perplexistyでいうと、4.3 ~ 5.9くらい perplexityが20ということは、直前までを知ると次の単語の候補が大体20個くらい、ということに対応する。 まぁ大体そんなもんか、という気持ちになる。

backoff

n-gramモデルにおいて、特定のn-tupleがコーパスの中になかった場合に(n-1)-gramの確率を使う場合がある。 これをbackoffと呼ぶ。backoffは確率分布を歪ませるので調整が必要。コーパスが大きい場合には、あまり深く考えずに 単純に定数を掛けるだけで済ませる場合がある。これをstupid backoffと呼ぶ。定数は0.4が良いらしい（magic number）。