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