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）。