Go言語にさらに入門するために係り受け解析器を書いた話

今年からGo言語に入門していますが、もう少し複雑なものをものを書いてみたいと思ったので、係り受け解析器を書きました。その過程で工夫したこと、苦労したことをまとめます。作ったものはこちら。

一人で作っているプロジェクトですが、100行以下の細かめの修正毎にPull Requestを作っているので、どのような過程でやっているかが比較的分かりやすいと思います。

easy-first algorithmについて

  • 係り受け解析アルゴリズムの1つです
  • 最も自信のある(つまり簡単な)ところから係り受け関係を付けていくgreedyな方法です
  • コーパスには正解の係り受けは付与されていますが、簡単さの順序は当然分からないので、構造化パーセプトロンでそれを含めて学習します
    • 構造化パーセプロトンについては入門エントリを書いているので、興味がある方はどうぞ

なぜ係り受け解析器を書いてGo言語の入門をするのか

  • 今年の初めからGo言語に入門していた
  • おかげでAPI wrapper的なcliツールは作れるようになった
  • しかし、以下の経験をもっと積みたい
    • もっとCPUやメモリに負荷がかかる計算をやらせたい
      • Go言語でどの辺がボトルネックになりやすいのか知りたい
      • プロファイリングで地道に改善していく経験がしたい
    • もう少し複雑なデータ構造を扱いたい
    • goroutineやchannelについての知識を、本を読むだけではなく、実装しながら掴みたい
  • 係り受け解析器を作るのは(自分にとっては)よい選択
    • ドメイン知識があるので、係り受け解析器のこと自体はそれほど心配しなくてよい
      • clojureでも実装経験済み
      • 初めてのタスクでやるとタスク固有のことではまっているのか言語のことではまっているのかの切り分けが必要
    • 特に学習部分はあまりにナイーブな実装をするとそこそこ時間もかかるし、メモリも食う

学んだこと

Goroutineによる並列処理

Go言語の定石的なところ。sync.WaitGroupを使って並列に処理をする、channelを使ってCPU数に合わせた並列度にするといったところが学べました。元の関数にはほとんど手を入れずに並列化できているので、お手軽感が分かるかと思います。

文字列連結のパフォーマンス

最初は何も考えずにfmt.Sprintfで丁寧に文字列の特徴量を作っていましたが、案の定ボトルネックになりました。読みやすさも考えて妥協できるライン(ハードコーディング)で落ち着きました。

プロファイリングの取り方

文字列連結のパフォーマンス改善をしたほうがよさそうと決めたのも、プロファイリングの結果を見てからでした。Goは標準のツールセットがよくできていますが(gofmtなど)、プロファイリングも標準のpprofで十分でした。pprofの使い方については、以下のサイトを参考にしました。

プロファイラを取りたいコードに以下のコードを仕込みます。

defer profile.Start(profile.CPUProfile).Stop()

仕込んだバイナリを実行すると、cpu.pprofができあがります。

% go build
% ./go-easy-first ...
% go tool pprof go-easy-first /var/folders/pk/zk906vvd7rx7ls8g3sv3vs800000gn/T/profile498633669/cpu.pprof

私の場合はtop 20 -cum main.list main.を実行するとボトルネックになっている箇所が大まかに分かり、そこを修正すると速度が改善できました。最初は7分程度かかっていたものが2分程度まで縮んだので、まあまあのインパクトです。また、実行する関数を文字列で取りたい場所でreflectionを使っていて、パフォーマンスが若干気になったのですが、プロファイリングを取ることでそこはほぼ問題にならない程度の時間であることが分かってよかったです。

mapの辞書引きのパフォーマンス

同じくプロファイリングを取っていて少しずつ改善していった箇所です。文字列連結のパフォーマンスを改善した後も、内積計算(DotProd)で計算時間がかかっていることが分かりました。初期は内積計算をするための重みベクトルをmap[string]float64で保持していましたが、keyが文字列で引いてくるのは明らかに時間がかかります。そこで、keyをid化して辞書引きを高速にするように変更しました。また、Feature Hashingも使い、最大の次元数を決めることで重みベクトルも[]float64となり、使用するメモリも削減&高速になりました(最大の次元数が小さすぎるとhashが頻繁に衝突してしまいますが、100万次元程度確保しておけばこのタスクではほぼ精度は落ちずに済みます)。

外部のciサービスを使う

仕事ではcircleciやtravis-ciにお世話になっていますが(mackerel-agent関係)、個人のプロジェクトでは使ったことがなかったため導入してみました。CircleCIのようなバッチをREADME.mdに付けたかったというミーハー的な動機もあります。いくつか似たようなものがありましたが、今回は以下の3つを導入しました。

ずぼらな性格なので、一人でやっているとどんどん適当になってしまいがちですが、ciを入れると適度に秩序が保てるのでよいですね。

タスクランナーとしてMakefileを使う

これまで小規模なGo言語のアプリしか使っていなかったため、go rungo buildで十分でした。しかし、後述するgo-bindata等をビルドの前に行ないたい等、色々やることが増えてくるとタスクランナーが欲しくなってきます。みんGoでも我等がid:SongmuさんがMakefileでやることをオススメしていたので、Makefileを導入することにしました。

はまったこと/困ったこと

パラメータファイルの読み書き

パラメータファイルはただのベクトル([]float64)なので、human readableなjsonである必要は特にありません。バイナリファイルに書いて、デコードのときに読み込ませるようにしようと思いましたが、イマイチbest practiceがよく分かりませんでした。試行錯誤をした結果、encoding/gobのEncoder/Decoderでやりすごしました。

この程度のことだったら、gopher的にはこの程度だったらencoding/binaryを使うのがよい?

パラメータファイルをバイナリに埋め込む

係り受け解析器を走らせるんだったら、バイナリを一個落としてくるとそれでOKな形になっているとかっこいいです。Goで書かれた形態素解析器のkagomeは実際そのようになっています。

みんGoでこういうときにはgo-bindataを使うべしとあったので、導入してみました。

しかし、ちょっと困りました。学習済みのパラメータファイルがすでにあれば普通にビルドできますが、そもそもビルドしないと学習ができないのでした。ひとまず空ディレクトリを置いとくことでビルドは通るようにしました。普通にgo-bindataを使うだけならそんなに困らないけど、機械学習のモデルもバイナリに組み込んで配布したいといった場合にはちょっと考えることが増えそうです。

副作用

ここは当てはまる人はそんなにいなさそう。前職ではClojure、現在はScalaを書いていることが多く、immutableなデータ構造を扱うことが多いのですが、Goは当然ながらそうではないので、副作用関連ではまりました。思っていなかったところが書き変わっていたり、あるいは変更できたと思っていたところが書き換えられていなかったり。immutableな場合は考えるスコープがかなり局所的ですが、mutableだと広くなりがちなので頭のスイッチに時間がかかりました。

まとめ

係り受け解析器をGo言語で書くことで学んだ様々なことについて紹介しました。慣れない言語は自分が慣れている言語と比べるとどうしても実装速度等は落ちてしまいがちですが、自分がなじんでいるドメインで実験すると新しい言語のこと自体に集中できて、なかなかよかったです。そろそろGo初心者を脱出したい…!

みんなのGo言語【現場で使える実践テクニック】

みんなのGo言語【現場で使える実践テクニック】