Hatena::Grouprekken

murawaki の雑記

2010-11-25

Implementing distributed Perceptron training with GXP make

Distributed Training Strategies for the Structured PerceptronGXP make で実装してみたものの、結局使っていない。ここでさらしてみる。

まず Structured Perceptron の distributed training を手短に。online learning では、訓練データを一つずつ読んで重みを更新する。大量の訓練データを逐次的に読んでいたら時間がかかって仕方がない。そこで、訓練データを分割して、それぞれの断片について並列に重みを学習したい。

素朴には、別々に学習した結果を最後に混ぜればいいんじゃないかと思うところ。それでは駄目な例を著者は示す。ではどうすればいいか。分類器の混ぜあわせを最後に一度行うのではなく、iteration 毎に行えば良い。収束性も証明されている。混ぜあわせる時に、分類器間に混合比を設定して傾斜をかけることも考えられるけど、単純に重みを平均しても問題ない。

実装は簡単。部品として、普通の Perceptron の訓練プログラムをそのまま流用できる。変更は一点。普通は分類器を重み 0 で初期化するが、混ぜ合わされた分類器を受け取って初期値とする。そこで、分類器の初期状態を読み込む起動オプション --init を追加。このプログラムを iteration 1回で呼び出す。

新たに作る部品は二つ。訓練データを並列数に分割するプログラムと、複数の分類器を受け取ってその重みを混ぜ合わせるプログラム

これらの部品を使ってどうやって並列化するか。著者は Google の人なので MapReduce を使っている。部外者は Hadoop を使えということなのだろう。Hadoop 使いではないので GXP make で実装してみる。GXP make は、GNU make 方式の Makefile を与えたら、並列化できる部分を勝手に並列化してくれる。GXP make で実装という言い方は少し変。単に Makefile を書いているだけ。複雑な Makefile を書いたことがなかったので、田浦先生のチュートリアルを見ながら書く。

難しい点。主なパラメータが二つ。並列数 (= 訓練データの断片数) $SHARD と、全体の iteration 回数 $ITER。これらのパラメータの値によって中間ファイルの数が変わる。チュートリアルの分類では、「起動時の状態でパラメータ化された DAG」にあたる。チュートリアルの指南通り、パターンルールを生成する関数を define し、foreach をまわして eval/call で関数を呼び出してパターンルールを生成する。

$ITER 回目の $SHARD 個目の断片からの学習結果は each.$(ITER).$(SHARD).mp。これは $ITER - 1 番の混ぜあわせ結果と、断片 shard.$(SHARD).bz2 に依存する (parallel_train_each)。ただし、iteration の初回は初期値の分類器がない (parallel_train_init)。学習された分類器は merge_mps で混ぜあわせる。

make のターゲットは一つしか記述できない。でも、訓練データの分割は、出力が複数ある。make では記述しにくい。分割ルールは shard.1.bz2 を生成することにし、shard.1.bz2 から shard.2.bz2、shard.2.bz2 から shard.3.bz2 を生成するようにダミールールを書く (shard_dummy)。

特徴。make なので、実行途中に殺しても、中間ファイルの状態から再開できる。ただし、現在の設定では中間ファイルをそのまま残すので、ディスクを食いまくる。訓練結果の混ぜあわせは、依存している分類器がすべて生成されてから開始される。一個が生成された時点で始めた方が時間が節約できるはず。MapReduce ならこれを自動でやってくれるのだろうが、make だと難しい。(今回はそうでもないけど) merge の処理だけメモリを大量に食うので、特定のマシンで処理したいといった要求がよくある。GXP make でこれを実現する方法を知らない。

誰か Makefile の効率的な debug 方法を教えてほしい。

2010/12/03 追記: 比較的新しい gxp だと、recipe (コマンド) に以下のように記述すれば、実行するホストを制限できる様子。

	program arguments # GXPMAKE: on=hostname_regex

GXPMAKE の情報をどうやって書けばいいのかわからなかったけど、コメントとして渡せばよい。こうすれば、xmake は解釈するけど、プログラムには渡らない。

2013/04/06 追記: gxp js 導入後 make の仕様も変わっている。今ならこう書かないといけない。

	program arguments # aff: name=hostname_regex

# -*- mode: Makefile -*-
#
# usage: make -f THIS_FILE INPUT=x OUTPUT=y ...
#

# default configurations
SHARD:=10
ITER:=10
TYPE:=mp
INPUT:=train.bz2
OUTPUT:=output.$(TYPE)
TMPDIR:=/tmp

BASEDIR:=/some/where
SPLIT_PROGRAM:=$(BASEDIR)/split-train --shard=$(SHARD) --compressed --compress
TRAIN_PROGRAM:= $(BASEDIR)/train-mp --type=$(TYPE) --iter=1 --debug --compressed
MERGE_PROGRAM:=$(BASEDIR)/merge-mp --type=$(TYPE) --debug

define shard_dummy
$(TMPDIR)/shard.$(1).bz2: $(TMPDIR)/shard.$(shell expr $(1) - 1).bz2
endef

define parallel_train_init
$(TMPDIR)/each.1.$(1).$(TYPE): $(TMPDIR)/shard.$(1).bz2
	$(TRAIN_PROGRAM) --input=$(TMPDIR)/shard.$(1).bz2 --output=$(TMPDIR)/each.1.$(1).$(TYPE)
endef

define parallel_train_each
$(TMPDIR)/each.$(1).$(2).$(TYPE): $(TMPDIR)/merged.$(shell expr $(1) - 1) $(TMPDIR)/shard.$(2).bz2
	$(TRAIN_PROGRAM) --input=$(TMPDIR)/shard.$(2).bz2 --init=$(TMPDIR)/merged.$(shell expr $(1) - 1) --output=$(TMPDIR)/each.$(1).$(2).$(TYPE)
endef

define merge_mps
$(TMPDIR)/merged.$(1): $(foreach y,$(shell seq 1 $(SHARD)),$(TMPDIR)/each.$(1).$(y).$(TYPE))
	$(MERGE_PROGRAM) --dir=$(TMPDIR) --prefix=each.$(1). --output=$(TMPDIR)/merged.$(1)
endef

$(foreach x,$(shell seq 2 $(SHARD)), \
  $(eval $(call shard_dummy,$(x))))
$(foreach x,$(shell seq 1 $(ITER)), \
  $(eval $(call merge_mps,$(x))))
$(foreach x,$(shell seq 1 $(SHARD)), \
  $(eval $(call parallel_train_init,$(x))))
$(foreach x,$(shell seq 2 $(ITER)), \
  $(foreach y,$(shell seq 1 $(SHARD)), \
    $(eval $(call parallel_train_each,$(x),$(y)))))

.PHONY : all clean
all : $(OUTPUT)
$(OUTPUT) : $(TMPDIR)/merged.$(ITER)
	mv $< $@
$(TMPDIR)/shard.1.bz2 : $(INPUT)
	mkdir -p $(TMPDIR)
	$(SPLIT_PROGRAM) --input=$< --prefix=$(TMPDIR)/shard

clean:
	rm -rf $(TMPDIR)

2010-11-15

Unsupervised phonemic Chinese word segmentation using Adaptor Grammars

Mark Johnson; Katherine Demuth: Unsupervised phonemic Chinese word segmentation using Adaptor Grammars (COLING 2010) (PDF).

単体の論文としては微妙。既存の手法を少し手直しして新しいデータに適用しましたという話。結果は微妙で考察も浅い。しかし問題設定問題について個人的に思うところがいろいろ。ただし考えがまとまらない。書き出して整理を試みる。

作っているのは単語分割を学習するモデル。食わせるデータは赤ちゃんに向けられた大人の発話。目的は人間の言語獲得を計算モデルを作って解明すること。壮大で役に立たない話。こういう研究ができるのはすばらしい。とはいえ意味の領域には踏み込めないし、それどころか構文の獲得もまだまだ大変。とりあえず単語分割から始めようというのが現状。中で Pitman-Yor Process が使われているとか、そういう瑣末な話はこの際置いておく。

英語コーパスに適用したのが2008年の報告で、今回は中国語。わざわざタイトルで phonemic と断っているように、入力は漢字列ではない。元のコーパスは拼音。それで何が重要かといえば、声調が入っているところ。同時につっこみどころでもある。

その前に英語コーパスでの設定を確認しておく。英語コーパスの設定は以前紹介した Goldwater+ の論文と同じ。具体例を見ると、what is it という発話に対応する入力データは WAtIzIt。音素列を普通のアルファベットで表記したもの。

そもそも赤ちゃんに向けられた発話というのは音声、つまりはアナログの波。一方ここで扱う入力はシンボル列。暗黙に了解されている仮定は次の通り。人間の音声認識信号処理とシンボル処理という2段階のパイプライン処理になっている。そして、信号処理を完璧にやった結果をシンボル処理の入力と仮定してもとりあえずはいいだろうと。この二つのモジュールの組み合わせは通常の音声認識でもやっていることで、とりあえずはよしとする。問題は両者の役割分担。

では、改めて英語コーパスの場合、信号処理が何をしているのか。出力は音素列。異音 (例えば peak の p は有気音で、speak の p は無気音) を区別しない。この仮定は多分妥当。耳が聞いているのは音素であって、シンボルとして異音が認識されることはないのだろう。もっとも実際のところは知らない。脳をやっている人にでも聞いてみたい。

もう一つの特徴は、ストレスの情報がないこと。どう考えても人間は英語を聞き取りにストレスの情報を使っている。この問題は Goldwater+ が少し議論している。曰く、Gambell and Yang (2006) はストレスの情報を使えばルールベースで簡単に単語分割できると言うけど、a とか the にまでストレスを振っててインチキだよと。ストレス情報の利用は今後の課題として流しているけど、もし使うならどう表現すべきなのだろうか。

で、本題の中国語。元のコーパスは拼音。これをそのまま入力データとはしない。変換する。その変換がつっこみどころ。まず拼音を IPA に変換。えっ、とここで絶句する。音素じゃなかったのかと。しかし例を見る限り、異音を頑張って書き分けるような本格的な表記ではなく、なんちゃって IPA みたい。とりあえず音素列とみなしてよいのだろう。

次に音節をばらす。さあ声調をどうするのかと思ったら、声調パターンを母音の直後に置いて直列化する。zen3 が ts ə 214 n になる。ここで再び絶句。声調というのは超分節音素じゃなかったのかと。ちゃんとモデル化するのは今後の課題ということで流しているけど、ここが論文の要のはず。

とりあえず声調は置いておく。論文の設定では、音素列をモデルに食わせて単語を認識させる。評価は単語分割だけ。果たして音節境界がどの程度復元できているのか知りたいところだが、論文は何も言わない。

より根本的な疑問が残る。そもそも中国語信号処理の出力、つまりシンボル処理の入力は、果たして音素列でいいのだろうか。私の予想では、中国人の耳は、音素列ではなく音節列を聞き取っている。シンボル処理が音素列から一気に単語までを復元するのは、頑張るレイヤーを間違えているのではないか。だいたい、声母の n と韻尾の n が同じ音素と認識されているとは思えない。

英語の場合、WA-tI-zIt という音節列に対して、単語列は WAt-Iz-It とずれる。信号処理は音素列を出力していると考えてもよさそうだ。ただし、音素列だとすると、ストレスの情報をどこに付けたらいいのか分からない。音節に付いているのかなあとも思うけど。しかし、中国語は基本的に単語境界が音節境界をまたがない。信号処理の時点で音節単位なのではないか。音節単位なら声調が問題なく扱える。ただし、音節を完全に atomic な単位にしているのではなく、音節の内部構成についても保持していそうな気がする。

とにかく、この仮定が正しいなら、やるべき事が変わってくる。音素列から音節 (そして単語) を教師なしのシンボル処理で獲得させるのではなく、アナログ信号から音節を教師なしの信号処理で獲得させるべき。シンボル処理は音節を引っ付けるか引っ付けないか考えればいいのである。

しかし、この設定も微妙といえば微妙。音節を分断するような意味のまとまりが中国語にないことは、言語獲得のある段階以降は知っているだろうが、最初の段階でこれを仮定するのは良くない。