y_uti のブログ

統計、機械学習、自然言語処理などに興味を持つエンジニアの技術ブログです

IBM Model 1 を SQL で実装

IBM Model 1 を SQL で実装してみます。RDBMS には PostgreSQL を使いました。

まず、コーパスを格納するテーブルを作成します。position_id は文中での出現位置を表す値のつもりです。これは IBM Model 1 では不要なのですが、気分的に入れておきました。

CREATE TABLE corpus (
  sentence_id INTEGER NOT NULL,
  lang        VARCHAR NOT NULL,
  position_id INTEGER NOT NULL,
  word        VARCHAR NOT NULL
);

このテーブルに読み込ませるように、コーパスを変形します。出来上がりはこんな形になります。各列が上で作成したテーブルの列に対応しています。

$ cat sample.csv
1 E 1 the
1 E 2 house
2 E 1 the
2 E 2 book
3 E 1 a
3 E 2 book
1 F 1 das
1 F 2 Haus
2 F 1 das
2 F 2 Buch
3 F 1 ein
3 F 2 Buch

これをデータベースに読み込みます。

COPY corpus FROM 'sample.csv' USING DELIMITERS ' ';

次に、翻訳確率を保存するテーブルを作成します。EM 法で学習するので、各 iteration での値を保存できるように iteration 列を付けておきました。

CREATE TABLE probability (
  iteration INTEGER NOT NULL,
  e         VARCHAR NOT NULL,
  f         VARCHAR NOT NULL,
  p         DOUBLE PRECISION NOT NULL
);

さて、これで一通りの準備ができたので、学習部分を書いていきます。まずは初期化。共起する単語対を全部拾い、確率を初期化します。iteration は 0 から開始することにしました。

INSERT INTO probability
SELECT DISTINCT
  0,
  c1.word,
  c2.word,
  /* ここで 1.0 / E 側語彙数 に初期化 */
  1.0 / (SELECT count(DISTINCT word) FROM corpus WHERE lang = 'E')
FROM
  corpus c1,
  corpus c2
WHERE
  c1.lang = 'E'
  AND c2.lang = 'F'
  AND c1.sentence_id = c2.sentence_id
;

本体の反復計算はこんな感じでしょうか。これで E step と M step を合わせた一回分です。現在の probability テーブルから iteration 最大の要素を使って計算し、結果を iteration + 1 として probability テーブルに追加します。

INSERT INTO probability
SELECT DISTINCT
  tbl.iteration + 1,
  tbl.e,
  tbl.f,
  /* 次行が count(e|f) / total(f) の計算 */
  (sum(tbl.c) OVER (PARTITION BY tbl.e, tbl.f)) / (sum(tbl.c) OVER (PARTITION BY tbl.f))
FROM (
  SELECT
    prob.iteration,
    prob.e,
    prob.f,
    /* 次行が一組の単語対 (e, f) に関する t(e|f) / s_total(e) の計算 */
    prob.p / sum(prob.p) OVER (PARTITION BY c1.sentence_id, prob.e) AS c
  FROM
    corpus c1,
    corpus c2,
    probability prob
  WHERE
    c1.lang = 'E'
    AND c2.lang = 'F'
    AND c1.sentence_id = c2.sentence_id
    AND prob.iteration = (SELECT max(iteration) FROM probability)
    AND prob.e = c1.word
    AND prob.f = c2.word
) tbl;

上の SQL を何度か実行して、最後に計算結果を見てみます。

SELECT
  e,
  f,
  round(sum(CASE iteration WHEN 0 THEN p ELSE 0 END)::NUMERIC, 4) AS i0,
  round(sum(CASE iteration WHEN 1 THEN p ELSE 0 END)::NUMERIC, 4) AS i1,
  round(sum(CASE iteration WHEN 2 THEN p ELSE 0 END)::NUMERIC, 4) AS i2,
  round(sum(CASE iteration WHEN 3 THEN p ELSE 0 END)::NUMERIC, 4) AS i3,
  round(sum(CASE iteration WHEN 4 THEN p ELSE 0 END)::NUMERIC, 4) AS i4,
  round(sum(CASE iteration WHEN 5 THEN p ELSE 0 END)::NUMERIC, 4) AS i5
FROM probability
GROUP BY e, f
ORDER BY e, f

このように、ちゃんと計算できています。

   e   |  f   |   i0   |   i1   |   i2   |   i3   |   i4   |   i5
-------+------+--------+--------+--------+--------+--------+--------
 a     | Buch | 0.2500 | 0.2500 | 0.1818 | 0.1313 | 0.0904 | 0.0596
 a     | ein  | 0.2500 | 0.5000 | 0.5714 | 0.6534 | 0.7245 | 0.7817
 book  | Buch | 0.2500 | 0.5000 | 0.6364 | 0.7479 | 0.8344 | 0.8961
 book  | das  | 0.2500 | 0.2500 | 0.1818 | 0.1208 | 0.0752 | 0.0444
 book  | ein  | 0.2500 | 0.5000 | 0.4286 | 0.3466 | 0.2755 | 0.2183
 house | das  | 0.2500 | 0.2500 | 0.1818 | 0.1313 | 0.0904 | 0.0596
 house | Haus | 0.2500 | 0.5000 | 0.5714 | 0.6534 | 0.7245 | 0.7817
 the   | Buch | 0.2500 | 0.2500 | 0.1818 | 0.1208 | 0.0752 | 0.0444
 the   | das  | 0.2500 | 0.5000 | 0.6364 | 0.7479 | 0.8344 | 0.8961
 the   | Haus | 0.2500 | 0.5000 | 0.4286 | 0.3466 | 0.2755 | 0.2183