Implementing distributed Perceptron training with GXP make

Distributed Training Strategies for the Structured Perceptron を GXP 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)

murawaki の雑記

はてなグループから移転してきました

Implementing distributed Perceptron training with GXP make