KerasでLSTMを使ってテスト駆動開発してみた

tl;dr

Kerasという機械学習のフレームワークのサンプルにあるLSTMを使い、テストコードを生成して、それをもとにテスト駆動開発してみた。

Kerasを試してみる

以前、紹介記事を書いたのでそちらを参照していただけると幸いです。

sharply.hatenablog.com

また、MLPを使った文の分類については以下の記事をご参照ください。

sharply.hatenablog.com

ソースコードを生成してみる

Kerasのexamplesに含まれているlstm_text_generation.pyを使って、文を生成してみることにチャレンジしてみたいと思います。ここではLSTMという構造が使われていますが、LSTMについては別の記事で少し紹介したので、そちらとその参考ページを参照いただけたら幸いです。

sharply.hatenablog.com

さて、元のコードではニーチェの文書をそのLSTMに学習させています。CPUマシンで計算させるとそれなりにまともな文章が出力されるまでとんでもなく時間がかかるのですが、例えば17イテレータでこんな文章が出力されました。

----- diversity: 1.0 ----- Generating with seed: "on as religion, art and ethics are so un" on as religion, art and ethics are so untorjuse of the nationar is the greater and repalsife man who law, it was supposed at the inplanatine, sole--of the whole poom befole this chacal we have sight of the are the divine patter. of the bits in the end, and the good and despriating the otherse, consequem and gratprouble autional enemat.--and a thing world agaits this difficeetis: the must is the greater of to the morality. one who are in

何のこっちゃといった感じですが、これは"on as religion, art and ethics are so un"をシード、つまりこの文字列から始まる文として、その続きをLSTMに予測させたものです。ご覧の通りそんなに精度よく文が生成されるわけではないのですが、今回はここにRuby on Rails5のソースコードのうち、テストコードだけを読ませてみたいと思います。

$ git clone https://github.com/rails/rails.git
$ cd rails
$ more `find . | grep _test.rb` > all_test.rb

これだけ抽出するだけでも5MBぐらいになり、5MB程度でも非力なCPUマシンでは1イテレータに10時間ほどかかってしまう見込みが出たので、splitコマンドを使って1MBずつに切り分けて、そのなかで最初のファイルを入力として指定してみます。さて、ちゃんとテストコードらしいコードを出力してくれるのでしょうか。結果はこのようなものがみてとれました。

----- diversity: 0.5 (9イテレータ目)
  def test_create_with_conditions_should_be_shared_with_conditions_on_conditions_on_many_and_limit_with_logs_target_with_propore_the_save
    comment = comment.projects.first
    assert_equal 1, post.all.merge!(:includes => :posts.id).post
    assert_equal 2, post.tags.belongs.size
  end

  def test_attribute_mattring_table_name_uniqueness_with_can_be_should_return_name
    column = companies(:f

----- diversity: 1.0 (9イテレータ目)
equal startup, sponsor.sponsorable
  end

  test 'string withdenv = write ci nect('restraction is instance_destroying peoples- ta/se body face
  def test_precision_sql_from_select_view(*arging using attributet") do
      connection.project_id = forkal
      assert_equal 'w, sole
      assert posts(@connection.insert_line_it(with_serialize, default_end) 
    assert_equal 0, parent.id

    \wifhoun data s iv� ssopeltriv"
      end

----- diversity: 0.5 (16イテレータ目)
    car = car.create!(bulbs: [first_name])
    assert_equal 0, account.where("name = ?', ['author'], :interest.first_name: 'sting'
    end
  end

  def test_bould_name_prefixed_association_loading_with_belongs_to_and_on_association
    assert_equal 1, account.where("credit_limit = 10").to_a
    assert_equal 1, companies(:first_firm).clients_of_firm.reload.size
  end

  def test_no_collection_using_primary_key
        with_example_t

中には駄目そうなのもあり、diversityが高いほど駄目になっていますが、diversity=0.5で見た目では実行できそうなコードをピックアップすることができました。関数名がスネークケースで単語マシマシみたいになっていて英語的には破綻していますが、それでもちゃんとRubyで実行できそうなコードになっているのがわかります。

それではテスト駆動開発ということで、このテストに通りそうなコードを書いてみたいと思います。上のコードで、小文字と大文字を今回同一視しているのでその部分だけを修正してテストコードを作り、それをパスできるコードを書きます。

require 'test/unit'
require "active_record"

ActiveRecord::Base.establish_connection(
  adapter:   'sqlite3',
  database:  ':memory:'
)

class InitialSchema < ActiveRecord::Migration
  def self.up
    create_table :comments do |t|
      t.string :name
      t.integer :project_id
    end
    create_table :projects do |t|
      t.string :name
      t.integer :comment_id
    end
    create_table :posts do |t|
      t.string :name
    end
  end
end

InitialSchema.migrate(:up)

class ActiveRecord::Relation
  def post
    1
  end
end

class Symbol
  def id
    self.__id__
  end
end

class Comment < ActiveRecord::Base
  has_many :projects
end

class Project < ActiveRecord::Base
  belongs_to :comment
end

class Post < ActiveRecord::Base
  def self.tags
    Tag.all
  end
end

class Tag < ActiveRecord::Base
  def self.belongs
    [0,1]
  end
end

class TestSample < Test::Unit::TestCase
  def setup
    @comment = Comment.new
  end

  def test_create_with_conditions_should_be_shared_with_conditions_on_conditions_on_many_and_limit_with_logs_target_with_propore_the_save
    comment = @comment.projects.first
    assert_equal 1, Post.all.merge!(:includes => :posts.id).post
    assert_equal 2, Post.tags.belongs.size
  end
end

では、これを実行してみます。

$ ruby test_spec.rb 

Loaded suite test_spec
Started
.

Finished in 0.009579296 seconds.
--------------------------------------------------------------------------------------------------------------------------------------------------------------------------
1 tests, 2 assertions, 0 failures, 0 errors, 0 pendings, 0 omissions, 0 notifications
100% passed
--------------------------------------------------------------------------------------------------------------------------------------------------------------------------
104.39 tests/s, 208.78 assertions/s

テストに通ったので、うまくいったといえそうです。

近い将来、人工知能がまだプログラムは組めないけれど、仕様書からテストコードぐらいは生成できるようになった過渡期が訪れたとき、我々人類はこのようにして、機械によって生成されたテストコードをパスするためのプログラムを書くだけの存在になってしまうかもしれませんね。

プロセスあたりのメモリ使用量を知りたい

tl;dr

それぞれのプロセスがどのぐらいのメモリを使用しているかを知りたい。

コマンドで確認する

システム全体のメモリ使用量を確認する

• cat /proc/meminfo

linuxではデバイスもプロセスもファイルとして扱えるので、catできる。

MemTotal:        8073996 kB
MemFree:          333772 kB
MemAvailable:    4262036 kB
Buffers:          600280 kB
Cached:          3386552 kB
SwapCached:            0 kB
Active:          4668596 kB
Inactive:        2382920 kB
Active(anon):    3061940 kB
Inactive(anon):   286724 kB
Active(file):    1606656 kB
Inactive(file):  2096196 kB
Unevictable:           0 kB
Mlocked:               0 kB

enakai00.hatenablog.com

• free -tm

             total       used       free     shared    buffers     cached
Mem:          7884       6293       1591        260        470       3368
-/+ buffers/cache:       2454       5430
Swap:         2054          0       2054
Total:        9939       6293       3646

上のを高級な表示にした感じ。linuxではbuffersとcachedは、メモリが足りない時は開放するようになるので、buffers/cacheの値を見るとよい。

• vmstat

仮想メモリの統計を得る。メモリに関してはfreeと同じような感じだが、cpuやswap, ioの状況も見ることができる。

procs -----------memory---------- ---swap-- -----io---- -system-- ------cpu-----
 r  b   swpd   free   buff  cache   si   so    bi    bo   in   cs us sy id wa st
 2  0      0 2911928 490096 2719356    0    0    48    44  356   16  8  2 87  3  0

またvmstat [sec]として秒数を引数に渡すと、その秒数ごとの出力を得ることができる。

プロセスごとのメモリ使用量を確認する。

用語を以下のように置くことにする。

• VSS: 仮想メモリの使用量
• RSS: 物理メモリの使用量（共有メモリの使用量を含める）
• PSS: 物理メモリの使用量（共有メモリの使用量をプロセス間で等分する）
• USS: 物理メモリの使用量（共有メモリの使用量を除く）

使用量というのは実際にはページ単位で使われているかであって、Linuxでは4KBを1ページとしているため最小単位は4KBとなる。HugePagesを使えば、より粒度の大きいページを使うことができて、そうすることでページ表へのアクセスを減らすことができ、場合によっては高速化できる。

ここで検知したいのはvirtual memoryで確保した領域ではなく、実際に使われている領域がどのぐらいかということにある。そのため最低でもRSS、欲を言えばそれより細かい粒度での情報が欲しい。

• ps aux

USER       PID %CPU %MEM    VSZ   RSS TTY      STAT START   TIME COMMAND
root         1  0.0  0.0  35840  5612 ?        Ss   12:43   0:02 /usr/lib/systemd/systemd

これによってRSSは分かるが、結局それは正しい実使用量ではない。

Virtual Threads: Understanding memory usage on Linux

それは先述のように共有ライブラリの使用量が含まれており、reservedなメモリ使用量を全て表示しているからだ。C,C++のソフトウェアに関してはgdb, valgrindなどのデバッガを使えばよいとしている。

• top/htop

  PID USER      PR  NI    VIRT    RES    SHR S  %CPU  %MEM     TIME+ COMMAND
 3296 root      20   0 2330052 981008 162780 S 35.43 12.15 102:10.74 firefox                                 
 1959 root      20   0 3283584 575640  43724 S 6.954 7.130   6:17.59 dropbox    

topコマンドよりhtopコマンドの方が視覚的にわかりやすいプロセス毎のメモリ/cpu使用率などを表示してくれる。RESがタスクが使用しているスワップされていない物理メモリ、SHRにタスクが利用している共有メモリの総量が載っているので、USS=RES-SHRでとりあえず計算することは可能。

• pmap -x {procid}

3296: firefox
START               SIZE     RSS     PSS   DIRTY    SWAP PERM MAPPING
00007f4d21e00000  11264K   9320K   9320K   9320K      0K rw-p [anon]
00007f4d23400000  10240K   8120K   8120K   8120K      0K rw-p [anon]
00007f4d23e50000      4K      0K      0K      0K      0K ---p [anon]
00007f4d23e51000   8192K     20K     20K     20K      0K rw-p [anon]
00007f4d24651000      4K      0K      0K      0K      0K ---p [anon]
00007f4d24652000   8192K     12K     12K     12K      0K rw-p [stack:22843]
00007f4d24e52000      4K      0K      0K      0K      0K ---p [anon]
00007f4d24e53000   8192K     12K     12K     12K      0K rw-p [stack:22673]
00007f4d25653000   7860K    428K    428K      0K      0K r--p /usr/share/fonts/truetype/ipamp.ttf
00007f4d25e00000   5120K      0K      0K      0K      0K rw-p [anon]
00007f4d26700000  22528K   9512K   9512K   9512K      0K rw-p [anon]
00007f4d27e00000   5120K   2252K   2252K   2252K      0K rw-p [anon]
00007f4d28c00000   1024K    816K    816K    816K      0K rw-p [anon]
00007f4d28df7000   6092K   2572K    335K      0K      0K r--p /usr/share/fonts/truetype/ipagp.ttf

pmapを使うことでRSSに加え、PSSもわかった。

• smem

 PID User     Command                         Swap      USS      PSS      RSS 
 1093 hoge     /usr/lib32/skype/skype             0   172280   175262   182704 
 1050 hoge     /usr/bin/dropbox                   0   193672   195052   207152 

それぞれのプロセスのUSS, PSS, RSSを表示してくれる。python2製。

stackoverflow.com

上のStackOverflowによれば、smemでは下の計算式で求められている。

USS = sum of /proc/<pid>/smaps Private_clean + Private_dirty
PSS = sum of /proc/<pid>/smaps Pss
RSS = sum of /proc/<pid>/smaps Rss

smapsで得られる共有メモリの部分には、共有ライブラリだけでなく例えばforkした子プロセスでは、物理メモリのデータをCopy On Write（実際にメモリが書き換えられた時点で複製する）ようにしているので、そのときに共有されている物理メモリについても含まれている。そのためUSSだけがそのプロセスが実際に使うメモリ量とはならないし、RSSであっても共有ライブラリの分のメモリを含んでいる以上、同様となる。

dtrace

さてSolarisやMac OS X、FreeBSDにはdtraceというコマンドがある。これは動的にシステムをトレースするソフトウェアであるが、残念ながらlinuxには搭載されていない。

以下のツールは、dtraceの代替として紹介されている。それぞれを紹介したい。これを用いて、メモリを確保するようなシステムコールがいつどれだけ発行されたかをたどることができる。

stackoverflow.com

• sysdig

Sysdig | Home

csysdigでncurseによるインタラクティブなモニタリングをすることが可能となっている。そう、sysdigで表示される謎の出力をいちいちgrepしたり、引数をつけて呼び出す必要はないのだ。

最初に開いた画面でできることはたとえば以下がある。

F2を押すと、Viewを変更できる。例えば何らかのプロセスによってopenしているファイルのリスト(lsof)であったり、Systemcallのリストであったり。

Enterキーで選択されている行に限定して詳しく見ることができる。BackSpaceキーで戻れる。例えばSystemCallのリストで、Systemcallを選んでEnterを押すと、そのSystemcallを読んだプロセスが表示される。

F5を押すと、readとwriteイベントを見ることができる。F6を押すと、本家sysdigの出力を垣間見ることができる。

なお、実行するにはsuperuser権限で実行しなければならない。

• systemtap

stap とかいうどこかで聞いたことの有るような細胞名のコマンドで呼び出すこのツールは、Systemtap Scriptと呼ばれるスクリプトファイルに従ってカーネルに対する探索を行うことが可能である。

sourceware.org

がまだ詳しくわかっていない...

• strace

実際にシステムコールがどのタイミングで走っているかについてはstraceで検知することが可能である。プロセスにアタッチして、そのプロセスにおけるシステムコールを確認することもできる。

blog.livedoor.jp

straceを使うと、このような形で呼ばれたシステムコールと戻り値をみることができる。それをもとにmmapやbrkがどれだけメモリ確保したかを累算することができるが、いかんせん、これが内部で呼んでいるシステムコールのptraceは遅いので、実用性という面では厳しい。

brk(NULL)                               = 0x2156000
brk(0x2188000)                          = 0x2188000
mmap(NULL, 1000000000004096, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0) = -1 ENOMEM (Cannot allocate memory)
brk(0x38d7ea6df0000)                    = 0x2188000
mmap(NULL, 1000000000135168, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0) = -1 ENOMEM (Cannot allocate memory)
mmap(NULL, 134217728, PROT_NONE, MAP_PRIVATE|MAP_ANONYMOUS|MAP_NORESERVE, -1, 0) = 0x7f73a4490000
munmap(0x7f73a4490000, 62324736)        = 0
munmap(0x7f73ac000000, 4784128)         = 0
mprotect(0x7f73a8000000, 135168, PROT_READ|PROT_WRITE) = 0
mmap(NULL, 1000000000004096, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0) = -1 ENOMEM (Cannot allocate memory)
exit_group(0)                           = ?

さいごに

今回の記事については、素人同然の立場でまとめた備忘録ですので、Linuxにおけるメモリの使用方法について不正確な記述が多いおそれがあります。ご注意下さい。

References

sisidovski.hatenablog.com

gntm-mdk.hatenadiary.com

Memory Flame Graphs

qiita.com

qiita.com

Linuxトラブルシューティング探偵団 番外編（3）：SystemTapで真犯人を捕まえろ！ (1/4) - ＠IT

d.hatena.ne.jp

th0x4c.github.io

KerasのサンプルでMLPを使って文の分類を試してみる

tl;dr

Kerasに付属しているサンプルを使って、MLPで簡単な文書解析を試してみた。

Kerasを試してみる

前回、紹介記事を書いたのでそちらを参照していただけると幸いです。

sharply.hatenablog.com

MLPで文を分類してみる

単純なパーセプトロンはニューラルネットワークの中でも初歩的なもので、入力層と出力層が全結合しているものです。これは入力をx,出力をyとすると、Wを重み行列として

といった形の単純な数式で表現できる、n次元それぞれの成分と重みの積の和で表されるようなものですが、これでは表現力が乏しく、非線形な問題について解くことが出来ません。そこで多層パーセプトロン(MLP)では、入力層と出力層の間に、それぞれと全結合するような隠れ層が存在し、それが何レイヤーにも積み重なるようになっていることで、それぞれの重みの組み合わせによってモデルがより高い表現力を持つことができると考えられます。

さてKerasのexamplesフォルダにあるreuters_mlp.pyをみてみると、MLPによってロイターの記事をトピックに分類する実装が非常に簡単にできているのがわかります。モデルを見てみると、

model = Sequential()
model.add(Dense(512, input_shape=(max_words,)))
model.add(Activation('relu'))
model.add(Dropout(0.5))
model.add(Dense(nb_classes))
model.add(Activation('softmax'))

最初のDense(512)が上の説明での隠れ層に対応し、後のDense(nb_classes)が出力の種類に対応する層＝出力層です。それぞれの間にActivation層とDropout層が入っています。Activation層では活性化関数を噛ませることで、前のレイヤーの各成分に重みを掛けた値を足し合わせるだけではなく、それに対して効果を加えることで計算を簡略化したり、性能を上げたりすることができます。

活性化関数としてよく用いられるのがReLUと呼ばれるmax(0,x)で表される関数で、元の値がx<0の場合は常に0になるようなものです。こうやって敢えてデータを捨てることで、より値の特徴を強めたり、また行列を疎にすることで計算を早くすることができます。

その次のDropout層は確率的にノードからのデータを捨てることで、データに対するモデルの頑健性を高めている部分です。0.5ということは50%のデータはランダムに捨てられますが、逆に言うと残りの50%で正しく分類できるように誤差を逆伝播させて学習していると考えることができます。

従って、これだけ短いモデルであっても十分にディープラーニングで必要な要素が盛り込まれていることがわかります。ここではそれを用いて、任意の文データを分類できるように改造してみたいと思います。

(X_train, y_train), (X_test, y_test) = reuters.load_data(nb_words=max_words, test_split=0.2)

の行を、以下に置き換えます。

print('Loading data...')

m = map(int, raw_input().split())

max_words = m[1]

X_train = []
y_train = []

for i in range(m[0]):
  l = map(int, raw_input().split())

  X_train.append(l[1:])
  y_train.append(l[0])

そして次に、文データをこの分類器が読み込めるようなフォーマットに変換しなければなりません。文データはこのような形のtsvで保存されていることを想定しています。

1577 2334
0 1115 422 58 23 151 58 5 179 257 497 0 11 190 23 31 191 1116 99 19 38 20 208 86 91 27 145 80 18 23 745 0 36 498 58 0 48 42 423 21 10
0 36 17 92 17 58 499 367 13 29 68
0 36 36 124 19 1117 0 1118 3 102 171 1 293 368 5 746 4 5 40 29 21 87 12 247 16
0 18 32 59 53 24 369 258
0 179 35 27 1119 1120 8 24
0 36 27 370 600 17 747 21 8
0 500 500 36 320 5 16

文じゃなくて数字じゃないか！と思われるかもしれませんが、ディープラーニングの内部では巨大な行列計算が行われており、入力は数字が成分となっているベクトルが想定されます。だから画像を入力としたい時、従来までの統計的な機械学習手法であれば特徴量抽出をし、その特徴量をベクトルとしてSVMなどにかけていましたし、ディープラーニングで特徴量抽出が要らなくなる！といっても、実際にはn☓mサイズの画像をRGBの3次元で0-255の255段階にデジタル化された値が入力となっているのです。従って1つの画像はn☓m☓3個の要素に分解でき、そしてそれぞれは0-255の間の整数値を取ると言えるのです。

そこで、日本語の文であってもそれを何らかの数字に置換する必要がありますが、方針としては1文字を1つの数字とする、1単語を1つの数字とするの2つがあります。ここでは1単語を1数字にしてみましょう。その時、日本語を形態素解析して単語に分解する必要があります。ライブラリとしてはMeCabなどが有名で、それを使って文を単語に分割し、その単語に対してそれぞれ数字を割り当てることで、文を単語ベクトル（含まれている単語に割り当てられた数字を並べた配列）で表すことができるのです。

例: 「すもももももももものうち」 => すもも/も/もも/も/もも/の/うち => [1, 2, 3, 2, 3, 4 ,5] = uniq => [1, 2, 3, 4, 5]

ここで先のtsvのフォーマットを確認します。

1行目    : <文の総数> <単語の種類数>
2行目以降: <分類されるクラス> [単語ベクトル]

ここでは、このようなフォーマットを選択しました。分類されるクラスというのは、例えばある記述がAに関するものか、Bに関するものかというような分類を施したいときに、Aのとき0、Bのとき1というように数字を割り振ります。nb_classesという変数がソースコード中にありますが、その分類されるクラスの種類数をその変数に代入しておきましょう。

また、ここでは単語ベクトルは可変長にみえますが、MLPでは可変長入力を学習することはできません。ではどうなっているかというと、学習データに含まれる単語の種類数(ここではmax_wordsとします)が決まっていることを利用して、max_words次元のベクトルとして0-1のバイナリエンコーディングしているのです。

max_words = 5のとき
[0, 3, 4] => [1, 0, 0, 1, 1]  
[1, 2, 3] => [0, 1, 1, 1, 0]
[0]       => [1, 0, 0, 0, 0]

こうすれば全ての文が固定長のベクトルになることが言えます。これが、ソースコードの以下の部分です。

tokenizer = Tokenizer(nb_words=max_words)
X_train = tokenizer.sequences_to_matrix(X_train, mode='binary')
X_test = tokenizer.sequences_to_matrix(X_test, mode='binary')

tsvファイルを生成するコードは、pythonで書こうと思ったのですがpython2のunicodeとstr型の闇に飲み込まれてしまったので、Rubyで書きました。日本語処理で手間取ることなく、柔軟に配列やハッシュを操作できるので、こういったちょっとしたコードを書く時はRubyを愛用しています。さっとコードなので汚いですし、私が使うために作ったものなので実際のユースケースに合わせて改変してください。

require 'natto'

nm = Natto::MeCab.new

wordhash = Hash.new{|h,k|h[k]=0}
data = {}

Dir::glob("./*.txt").each do |filename|
  open(filename) do |file|
    sentences = []
    file.each_line.with_index do |line, i|
      word = []
      line = line.chomp
      nm.parse(line) do |w|
        word << w.surface
      end
      word.pop
      word.each{|t| wordhash[t]+=1}
      sentences << word
    end
    data[filename] = sentences
  end
end

word2index = {}

wordhash.to_a.sort!{|a,b| b[1]<=>a[1]}.each_with_index do |word,i|
  word2index[word[0]] = i
end

print "#{[data.map{|t| t[1].size}.inject(:+), word2index.keys.size].join(" ")}\n" 

data.to_a.each_with_index do |file, i|
  file[1].each do |row|
    print "#{[i, row.map{|t| word2index[t]}].join(" ")}\n"
  end
end

また実際に使う際には、句読点などは省いた方がよいので、もとの文じたいがデータとして適しているかについても検討する必要があります。

さて、準備が整いました。標準入力に上記で定めたフォーマットのテキストファイルを流し込むことで実行できます。

$ python reuters_mlp.py < input_data.txt

こうすることで、独自データ用のモデルを作ることができます。予測したいときは、このモデルに対して別の文ベクトルを用意し、predictすることで、どのクラスに分類されるか、またその確率について計算することができます。

今回は1単語に対して1つのスカラー値を割り振るという方法をとりましたが、このモデルでは、もともとのモデル構築時に含まれなかった単語に対して、数字が割り当てられないので何も予想することができません。しばしばこういった問題はゼロ頻度問題と呼ばれ、データがないものにたいしては予測できないという至極当然の問題に、自然言語処理では特に頻繁に出くわすことになるのです。これに対して今回のモデルで対処する方法はないので、できるだけ学習データを増やすか、そうでなければ別のやり方を考えるしかないと思います。これについては、以前の記事でWord2Vecを用いる方法について少し検討を加えました（まだうまくいっていません）。

sharply.hatenablog.com

Paxos, Raftなど分散合意プロトコルを概観する(2)

前回の記事

sharply.hatenablog.com

本稿ではRaft, Bitcoinの Proof of Work, Proof of Stakeそれぞれのアルゴリズムについて説明する。

分散合意プロトコル

Raft

難解であったPaxosより簡単であることを標榜しているアルゴリズムで、そこまで多くないノード数で、密結合なネットワークにおける分散合意が想定されており、Paxosではあまり触れられなかったリーダー選出手法についてはこちらの説明のほうが腑に落ちやすいと思う。実際にetcdなどで実装されており、ログレプリケーションなどで用いられる。

ここでは明確にプロセスは状態機械として扱われる。各リソース上のそれぞれのプロセスは本質的に平等であり、プロセスはLeader, Follower, Candidateの3stateのどれかを持つ。Leaderは交代する場合があり、それをtermとよばれる世代番号で管理する。1termにLeaderは1人であり、選出フェーズと稼働フェーズによって構成される。

• Leader: Clientからのログエントリの受領、Followerへのログエントリのブロードキャストを行う。
• Candidate: 他のプロセスへ候補者になったことをブロードキャストし、過半数から承認を得た場合次のtermのLeaderとなる。
• Follower: 手持ちのノードへデータを追加し、Leaderからのブロードキャストに応答する。

Leaderはハートビートと呼ばれる、一定時間毎に生存していることを報告するRPCを流す。これをAppendEntriesRPCと呼ぶ。RPCには以下の2種類がある。

• AppendEntriesRPC: LeaderがFollowerに追加するログエントリを送る。これは内容がなくとも一定時間毎に送られる。
• RequestVoteRPC: Leaderが不在の時、Candidateが自分に投票するように依頼する。レスポンスが投票である。

リーダー選出

Leaderが不在となった場合に、新たなLeader選出に入る。 Leader不在の状況は、AppendEntriesRPCの未受信によって判明する。それぞれのFollowerはランダマイズされた待ち時間があり、その待ち時間を過ぎてもLeaderからのRPCがなかった場合にCandidateに変化し、termの値が1つ増加する。CandidateはRequestVoteRPCと呼ばれるRPCをブロードキャストし、Candidateが自分に投票するように依頼する。過半数の投票があったことを以って、そのCandidateが新たなLeaderとなる。

もし仮に同時に複数のFollowerが時間切れとなって、複数のCandidateによるRequestVoteRPCが同時にブロードキャストされるような事態を想定してみよう。その場合、どのCandidateも過半数の支持を得られないことから、再びFollowerとなり、他のFollowerが次の時間切れとなってCandidateとなることを待つ。通常、待ち時間はランダマイズされるので、そのうちこのコンフリクトは解決するだろう。

ログレプリケーション、スナップショット

このあたりは調査不足なのだが、以下のスライドがわかりやすい。

Raft from Preferred Infrastructure & Preferred Networks

www.slideshare.net

Proof of Work

さて、Bitcoinで用いられるコンセンサスアルゴリズムについて考えてみよう。その前に、Bitcoinの仕組みについて予めさらっておきたい。

bitcoinのブロックにはその前のブロックへのポインタ、トランザクションと呼ばれる取引の一覧、そしてnonceと呼ばれる特定の数字が入っている。このブロックが次々につながった単一の鎖をブロックチェーンと呼び、これを1ブロックずつ延長していくことがマイニングという操作で、nonceと呼ばれる特定の数値をうまく調整することで、ブロックに含まれる情報から計算される一方向ハッシュの値が、定められた値(この値はdifficultyにより定められる)より小さくなるようにする(左端から十分長く000000が続く値になるようにする)作業のことである。

SHA-256やScryptといったこれらのハッシュ関数は、入力の値を少し変えると出力の値は大きく変わる上に、それは予測できない性質を持っている。したがってブルートフォースな全探索に頼るしかなく、CPUやGPU, ASICとよばれる専用の外付けハードを用いてひたすら高速計算する必要がある。こうして新しいブロックを得るということは、それだけ計算＝workをしたという証明になっているためproof of workと呼ばれるのではないかと思う。

逆に、nonce値が正しいかを計算するのは容易である。検証者は示されたnonceの値でhash値を計算し、difficultyの条件に合っているかを確かめればよいからである。このようにマイニングはハッシュ関数の計算困難性に依拠していて、bitcoinにおけるdifficultyは10分に1回新しいブロックが発見されるような難易度となるように調整されている。 取引が発生した場合、そのトランザクションはUTXOとよばれる場所に一時的にプールされ、次のブロックの採掘が始まったときにそこから手数料に応じて抽出されブロックに組み込まれてハッシュ値の計算が始まり、そしてブロックチェーンに組み込まれる。マイニングでは、マイナーはブロックの発見報酬とそのブロックの取引手数料の和を得ることができるのだ。

では仮に、異なる2箇所で同時にブロックA,Bが発見されたらどうなるだろうか。ブロックの発見と同時にそのブロックはブロードキャストされるが、疎結合なネットワークのためあるノードはA,あるノードはBを最新のブロックとして受け取ってしまうだろう。そして既にAを受領しているところでは、同じブロック番号であるBを受領することはできないし、その逆もまた真である。そのため、一時的にチェーンが分裂することがある。半分のマイニングノードではAの次にくるべきブロックを探し、残りの半分はBの次にくるべきブロックを探すようになってしまうからだ。

この場合どうするかというと、その次のつながるブロックA'あるいはB'のうち、A'が先に発見されたとしよう。するともともと先頭がAだったチェーンは次にA'が続くのはよいとして、先頭がBだったチェーンではそのチェーンは放棄され、A, A'の鎖が採用される。このとき比較するのは累積difficultyであり、今回であればA'がブロードキャストされた際に比較され、より累積difficultyの多いA'のほうを選択する。こうして、鎖は元通り1本になった。

difficultyが10分毎に発見されるように調節されていることで、次のブロックの発見には十分な時間差がついていると期待されるのだ。

51%攻撃

しかし、累積difficultyが高いチェーンをプライマリ・チェーンとして選択していくことには罠がある。それはあくまで相対的な規準であるため、51%以上の計算速度を持つノードが(実際にはそれより少ないノード数でも、確率的には引き起こすことが可能である)、プライマリ・チェーンから分岐させたセカンダリ・チェーンを延長させて元の鎖よりPoWの大きい鎖ができてしまった場合、元の鎖は破棄されてしまうのだ。 従って、ソフトウェアにハードコードされているGenesis Block以外のブロックが改変される可能性は0%ではない*1。厳密な意味では分散合意できていない！

現在は6世代まで遡って改変されることはないという前提のもと、それより6ブロック以上発見されているブロックにおけるトランザクションは成立したと見做される。またマイニングへのインセンティブのため、ブロックの発見報酬は100ブロック後が発見されるまでお預けとなる。これらの工夫によりコンスタントに良心的な計算力がマイニングに投下されているという状態が続く限り、そうそう簡単にトランザクションの取り消し、ブロックの改変が起こることはないが、起きた際のビットコインに対する信用の低下は免れない。

そして実際にマイニングは個人で行えるレベルではないため、複数人でマイニングを分担し、発見した分け前を分配するマイニングプールとよばれる集団による集権化が進んでおり、その中にはシェアの2割以上を占めるプールも出現していることから、それがウィークポイントとなるという指摘もされている。

Proof of Stake

さてAltcoinとよばれるBitcoinのオルタネイティブな実装のなかでは、Proof of Workとは異なるメカニズムでの合意を提供しているものがある。その一例がProof of Stakeであり、Stakeの名の通りブロックチェーンはそれを承認するコインの量によって定まるという仕組みである。これはProof of Workにおけるマイニングの電力消費、上記の51%攻撃への対処法として提案されたもので、Peercoin, Etheriumなどで実装されている。

考え方としては、コインを長期間持っている人はコインを鋳造することができるというような認識でよいだろう。コインを有する人がブロックを承認することができ、その承認の多いチェーンが選択されるという理解をしている。この場合、コインを多く持っている人はブロックチェーンのわかれたブランチに対して全承認をしてしまうことも考えられる(Nothing at stake)が、実際にそのようなことをするとブランチが乱立してコインの価値が下がってしまう。またPoS上で51%攻撃をしたとして、51%する主体はすでにコインの51%を取得しているため、そのような攻撃はそのコインの経済的価値を下げることになり、実質的には損である。

結局これはコインを有している人が選択権を握るということは、そのコインの価値を高める方向の選択（チェーンを1本に絞るような安定性を向上させる方向への選択）をするだろうという経済的インセンティブに依拠しているため、悪意を喪失させる*2という点では確かに効力を発揮するかもしれないが、かえってビザンチン故障に対しては弱い。

故障モデルをもとにしたプロトコルの概観

それでは最後に、今までのプロトコルをまとめたい。以下の分類法は「分散プログラミングモデルおよびデザインパターンの考察」に依っている。

マシンは死なない前提

マシンは死なないとする。この状況下で最も簡単な合意プロトコルは2 Phase Commitであり、このプロトコルではマシンが死んでしまうとブロックしてしまうので、死なないことが前提となっている。

Fail-Stop障害

マシンは死んだら死にっぱなしになっている障害のことをFail-Stop障害と呼ぶ。この状況下での合意プロトコルは3 Phase Commitであり、マシンの死に対してノンブロッキングである。

Fail-Recover障害

マシンが死んでいるか単に通信が遅延していうのか分からないような障害のことをFail-Recover障害と呼んでいる。

この状況に対して、初めて回復力を持つプロトコルとして提案されたのがPaxosであったが、元論文である"The Part-Time Parliament"は古代ギリシャの議会をモチーフにした難解なものであった。後に"Paxos made simple"と題されたそれより読みやすい論文や、Googleの開発者らによって実装上における手法を記した"Paxos made live"という論文が出回り理解は容易になったが、実装するにあたっては触れられていない部分も多く難しいことに変わりない。それに対して分かりやすく構成することを試みたRaftアルゴリズムというものが提案されており、そちらは明瞭な記述によって多くの実装が生み出されており、Paxosに比べて理解はやさしい。

論文間のつながりを敢えて図示するならば、以下である。

だが読むならば、以下の順に読むとわかりやすいだろう。

ビザンチン障害

ビザンチン将軍問題とは以下の問題である。

相互に通信しあう何らかのオブジェクト群において、通信および個々のオブジェクトが故障または故意によって偽の情報を伝達する可能性がある場合に、全体として正しい合意を形成できるかを問う問題である。 (Wikipediaによる)

このことから、偽のデータを流しうるノードが存在する状況をビザンチン故障と呼ぶ。数学的には3分の2以上は信頼できるノードである場合は、Lamport(1982)によると全プロセスに対して自分の情報をブロードキャストし、次に受け取った情報をベクトル化し再びブロードキャストすることで、過半数が同じ値のものを正しいと認識すれば、ビザンチン故障したノードがあっても正しい合意に至ることが可能となる。実際にPaxosの亜種として、3分の2以上のプロセスが正常の際にビザンチン障害に耐えうるプロトコルは提案されている。

しかし、さきのメカニズムでは巨大な疎結合ネットワークでは全対全通信が必要となるため、現実的な解決策ではない。これに対して解法を与えたとするのがBitcoinのProof of Workの主張であり、よく考えると厳密には合意に至っていないのだが確率的な制約条件によってほぼ覆ることのない状況にすることは可能であり、その制約条件は現時点では満たされている。

前回の記事

sharply.hatenablog.com

Reference

分散合意

http://www-higashi.ist.osaka-u.ac.jp/~nakata/mobile-cp/chap-07j.pdf

kumagi.hatenablog.com

postd.cc

Paxos

Googleを支える技術 ?巨大システムの内側の世界 (WEB+DB PRESSプラスシリーズ)

Consensus Protocols: Paxos : Paper Trail

Paxos from Preferred Infrastructure & Preferred Networks

www.slideshare.net

Raft

Raft(分散合意アルゴリズム)について · GitHub

Raft Consensus Algorithm

Bitcoin

github.com

d.hatena.ne.jp

qiita.com

アルトコイン | Bitcoin日本語情報サイト

*1:ただしその可能性は限りなく低い

*2:仮にこのネットワークをProof of Stakeの枠組みで攻撃しようとするならば、攻撃者はそれだけコインを保有する必要があるが、それだけコインを保有するならば攻撃によって失われるコインの価値もまた多くなるはずであり、従って損得で考えるならば攻撃者は攻撃する意味を失うはずである。

Paxos, Raftなど分散合意プロトコルを概観する(1)

tl;dr

分散合意プロトコルについてサーベイしたので、メモを残す。

• 2PC
• 3PC
• Paxos
• Raft(次回)
• Proof of Work(次回)
• Proof of Stake(次回)

分散システムについては素人の筆者が書いたため誤りが多いと思うので、できれば確認のため元論文を参照してもらいたいです。

introduction

基本的な定理, 用語

• CAP定理: 分散システムは、一貫性 (Consistency)、可用性 (Availability)、分断耐性 (Partition-tolerance)のうち最大でもいずれか2つしか満たすことはできない。
• レプリケーション: 一貫性を保ちながら、リソース間で情報を共有すること。
• RPC: プログラムであるノードから別のノード上の関数を呼び出すこと。ここでは、ノードから別のノードにメッセージを送ることという理解でもたぶん大丈夫だと思う。
• 冪等性: ある操作を何度行っても結果が同一になることが保障されていること。
• トランザクション: 一連の情報処理の単位。例えば口座A=>口座Bに1万円を移すとき、「口座Aから1万円引く」と「口座Bへ1万円足す」という処理は不可分に実施されなければならない。

FLP impossible

非同期システムでは、メッセージの損失がなかろうと1プロセスでも停止しうる限り、100%合意できるプロトコルはない。

ただしこのステートメントには様々な留保がついているが、以上の不可能性が根底にある中で*1、分散システムの合意に関する諸問題について緩和的なプロトコルが与えられている。

なぜ分散合意が必要となるか

通例あるサーバーに負荷が増大した場合、サーバーじたいの性能を上げる（スケールアップ）ことはもちろんであるが、サーバー自体の台数を増やす（スケールアウト）ことで対応するパターンが考えられる。 そのときデータはサーバーを構成するノード間でデータがレプリケーションされる必要があるが、一般にその通信には時間がかかると想定されるためデータが更新されてレプリケーションをしている途中では、クライアントが呼ぶサーバーによって入っているデータが異なる可能性がある。その可能性を許容し、時間が立てばいつかはどのサーバーに問い合わせても同じになるだろうと期待するのが結果整合性(eventually consistency)である。

では、ここでそれより制約の厳しい問題について取り組むことにする。すなわち、どのタイミングでもサーバーが常に一貫した値を返すようになっている仕組みをどうやって提供するかである。これは例えば銀行口座などを想起すればわかりやすいが、銀行口座でお金を全額引き出すという命令をサーバーに投げたとき、その伝達が遅延しておりあるサーバーのノードではその命令が実行されていないときに、問い合わせクエリを投げるとあたかも預金がまだ入っているかのように偽装できてしまう。問い合わせクエリだけならよいが、再びお金を全額引き出すというクエリが罷り通ってしまえば、二重引き落としが可能になってしまう。そのため、何らかの防御策が必要となる。

抽象化すると、あるデータベースに書き込まれたデータAをBに書き換えるクエリを発行したとき、それをそのデータベースを構成する複数のノードでいかに正しく共有できるか、という問題となる。そこで、以下の思考実験を与える。

Two general's Problem

2人の将軍A,Bが都市をはさんで反対側に陣取っているとして、一斉攻撃を仕掛ければ都市は陥落するが、片方で攻めると各個撃破されてしまう状況を想定する。このとき将軍間で連絡を取り、一斉攻撃する時刻を定めておけばよいが、ここでその連絡は途絶する可能性があるとしよう。

このとき、合意に至ることは不可能であることが言える。なぜならば、「翌朝7時に攻撃する」という通信がA=>Bへ送られたとして、B=>Aに通信が戻らなかった場合、AはそれがA=>Bで途絶えたかB=>Aで途絶えたか分からないので、通信が正しく伝わっているかを知るすべはないからだ。*2

分散合意再考

したがってデータベースのデータAを全ノードで一気にBに書き換えようとしても、その間の通信が途絶する可能性がある限り、その安全性は担保されない。

実際にデータベースではマスター/スレーブ型のサーバー構成を取り、書き込みクエリはマスターが一括して対応し、読み取りクエリはスレーブがそれぞれ対応することで対処することは多い。書き込みより読み取りが十分に多く、水平分割/垂直分割によってマスターの負荷が1台のサーバーでさばける量であればうまく動くだろう。

speakerdeck.com

ところがマスターで処理したクエリをスレーブにただ流すだけのような単純な例を想定すると、マスターが落ちた際に誰も対処できないし、通信が途絶する可能性もあるのでスレーブとの一貫性も保てない。実際にはもっと複雑な通信が行われてはいるのだが、データのconsistencyを保つためには、何らかのルール/プロトコルによってサーバーの各ノードの動きが制限されていなければならないということがいえる。 ここでは以下のように、必要となる制限の強さに応じてプロトコルを提示し、その動作の概略を説明したい。

各々のプロトコルの説明

2 Phase Commit

分散システムで、あるトランザクションがあるときに、それを全ノードがコミットするか、それとも全ノードがコミットしないかのどちらかの状態になることを保障するプロトコルである。 調整者（Coordinator）と呼ばれるノードと残りの参加者(Cohort)ノードに分かれて以下の2フェーズで行われるため、2PCと呼ばれる。

• コミット要求フェーズ: 調整者（Coordinator）が参加者にトランザクションを伝え、コミットの準備ができているかを問い合わせる。参加者はトランザクションが成功するならば成功、失敗すれば失敗を連絡する。
• コミットフェーズ: すべての参加者が成功した場合、コミットを実施するように通告し、失敗した参加者が少なくとも1つあった場合はロールバックを指示する。参加者は指示を実行し、完了応答を行う。

完了応答が調停者にすべて到達した時点で、トランザクションは終了したとみなされる。

この仕組みは少し考えればわかるが、通信路故障やノード故障に対して頑健でない。調整者はすべてのノードからの応答があって次のフェーズに移行することができるため、1つのノードから応答がこなかっただけでブロックされてしまい、以後何も進まなくなるからだ。これはまた調整者のFailにも頑健でない。そこで次にノンブロッキングな仕組みについて考える。

3 Phase Commit

ここでは時間制限を設け、タイムアウトによって時間切れを起こした場合、強制的に別のステップに移行するようにすることで、ブロックを防ぐような仕組みがとられている。

3-Phase Commit Protocol

上の状態機械の図を参考にすると良い。

• CoordはCommit_Requestメッセージを全Cohortにわたし、wait状態となる。CohortはCommit_Requestが成立するならば、AgreedメッセージをCoordに返し、wait状態となる。CohortがCommit_Requestにトランザクションの不整合などで失敗したならば、AbortメッセージをCoordに返しabort状態となる。CoordはAbortメッセージを受け取るか、Agreedメッセージを全Cohortから受け取る前にタイムアウトした場合はAbortし、CohortにAbortメッセージを送る。
• CoordがAgreedメッセージを全Cohortから受け取った場合、Prepareメッセージを全Cohortに送る。待機していた全Cohortは、Abortメッセージを受け取ったならばAbortし、Prepairメッセージを受け取ったらAckメッセージをCoordに返す。
• CoordはすべてのCohortからAckメッセージを受け取ったら、CommitメッセージをすべてのCohortに送り、Cohortはコミットする。一方でCoordがCommitメッセージを送る前にFailしてしまっていたならば、Cohortはタイムアウトしてトランザクションをロールバックする。CoordがすべてのCohortからAckメッセージを受け取る前にタイムアウトしたら、トランザクションをAbortし、Abortメッセージを全Cohort送る。

3PCの3相は、コミットリクエスト、コミット準備、コミットの3段階でメッセージをやり取りすることに依っている。今回の場合、故障したノードが存在してもタイムアウトによって最終的にAbort段階にたどり着くため終了することは保障されている。果たしてこれで分散合意は十分なのだろうか？

いや、決してそうではない。3PCではノードのクラッシュを許容するFail-Stop障害モデルに対応できることを示した。では仮にクラッシュしたノードが何食わぬ顔をして復帰してしまうような、Fail-Recover障害モデルではどうか？　そしてそれは現実のコンピューターでは極めてよくある現象である。なぜならば非同期通信において遅延した通信路によって、あたかも死んでいるかのように見えるノードがあったとして、それが突然速度を取り戻すこともあるし、ノードが単に再起動する可能性だってある。そのとき、3PCでは生き返ったノードを他のノードと同期させることができないのだ。

問題は他にもある。Coordinatorが落ち、別のノードがCoordinatorを代行したとしよう。その後再びCoordinatorが復活したとして、どちらもCoordinatorとしての職務を全うしようとしてしまうとき、Cohortにとってそれは不幸以外の何物でもない！

結局、単なるタイムアウトをとっただけでは、そのノードが死んでいるかそうでないかを判断することは不可能である。仮にFailから復活したノードがあったとして、そのノードにも適切に現状を伝え、そして役割を割り振ることのできるプロトコルが必要不可欠である。それが、以下で説明するPaxos、及び次回説明するRaftである。

Paxos

さてここで仮に多数決で物事を決めるとすると、過半数の参加者が正しい情報を持っていればよいと考えられる。この基本的な考えを敷衍して、メッセージは届かなかったり遅延はあってもよいが壊れないことを前提に置いた、非同期ネットワークのFail-Recover障害に対して回復力を持つプロトコルがPaxosである。

その中で全ての提案に順序番号を定め(Serialize)、どのプロセスにも同様の順序で到達することを約束している。これによってログのレプリケーションや命令の実行順序をシーケンシャルに定めることができる。ただし必ずしもその命令の発行された時間的順序とは一致しないが、このアルゴリズムは複数の提案を受理した際に単一の結果を得ることを保障する。 それぞれプロセスにはProposer, Acceptor, Learnerという役割を与えられており、2回のmessageのやり取りで合意を得る。

カジュアルなそれぞれのプロセスの役割は以下である。

• Proposer: 次に来る提案をAcceptorに問い合わせ(propose)、過半数の承認を得た場合にCommitメッセージを及び提案の承認とともに戻ってきた提案値のうち最大のものをAcceptorに伝える。
• Acceptor: Proposerの提案が自分の持っているログの中にある最大値の提案より小さければ提案を承認する(premise)。承認する場合は、ログ内の最大の提案値と共に返す。
  • Commitメッセージと共に受け取った提案値が、さきAcceptした提案値と一致すれば、そのCommitを承認する。
• Learner: Accpetorの過半数Commitした提案を記憶する。

"Paxos made simple"によれば、ProposerとAcceptorが1つずつの場合、Acceptorが複数の場合、Proposerが複数の場合、というように増やしていくことが各プロセスのルールを理解する助けになるという。

http://research.microsoft.com/en-us/um/people/lamport/pubs/paxos-simple.pdf

この場合であっても発生しうる障害は、Proposerが複数存在した場合に一方のProposerによる提案のProposeとCommitの間に他方のProposeが入ることで、Commitが棄却されてしまうことだ。これによってこのアルゴリズムは停止保証がないが、安全性は保障されている。 これを防ぐにはProposerのLeaderを定める必要がある。Paxosでは乱数を使うなりタイムアウトを使うなりすればよいと書いてあるだけで、リーダー選出の問題はRaftにより詳しく書かれている。またLearnerは複数ある場合、Acceptorとの多対多通信が発生するので、AcceptorとLearnerを媒介するLeader的な(Distributed) Learnerがあると望ましい*3。このLeader Proposer, Learnerを1つのマスターとする実装は1つ考えられる。

Paxos made live

一方でGoogleの実装は"Paxos made live"という論文にあるが、そこで平等なノード間で単一のCoordinator=Proposerを選出し、残りのノードがAcceptorsになるようにしている。さきの説明ではProposer=>Acceptor=>Learnerがシーケンシャルにつながっているように記述したが、この実装ではその役割は可変的である。この仕組みを基礎としているjavascriptでの実装が以下にあり、わかりやすい。

Neat Algorithms - Paxos - Will You Harry Me

またこの論文ではMulti-paxosやmaster leasesといった仕組みを新たに導入している。

Multi-Paxosでは一旦選出されたProposer(=Coordinatior)をある程度の期間変えないことで、2回目以降のpropose/promiseの手続きをしなくてもすむため、処理速度の向上が図れる。*4 Multi-PaxosでのCoordinatorはMaster相当のもので、master leasesとよばれる仕組みは、そのMasterが定期的に単調増加なsequence numberを更新していくことで、古いマスターが一時的に切れて新しいマスターが誕生し、その後古いマスターが戻ってきたときにsequence numberが小さい方を無視することで競合を防いでいる。*5

次回に続く。Referenceについても最後にまとめて記す。

*1:一方で故障検出機構をつけたり、原子時計を用いたりする(Google Spanner)ことで解決しているらしい

*2:A=>Bで途絶えたとき、Bはその通信の内容を知らないが、B=>Aで途絶えたときはBはその通信の内容を知っていることになる。しかしそれはAには分からない。

*3:そこが障害点にもなりかねないが..

*4:なぜならば単一のProposerがいる限りは、他の誰もProposeすることがないと確約されるため。

*5:このあたりはRaftでも同じようなことをやっているので、Raftの説明のほうがわかりやすいかもしれない。

word2vecによる文章表現 / ディープラーニング所感

tl;dr

Kerasを用いてDeepLearningをした上で得られた知見や、感じたことについて適当に列挙する。

Kerasについて

sharply.hatenablog.com

以前に書いた。依然としてKerasはオススメである。

Optimizerについて

ExampleではしばしばSGDを使っているが、上の図のようにSGDでは局所解に陥って動かなくなることがある。逆にAdadeltaやRMSPropのほうが早く収束するので、Optimizerの選択は意外に重要であった。

文章のベクトル表現を考える

台詞があったとき、分かち書きして学習させることで、ある台詞が誰の発話であるかを推定するモデルを作るとする。この場合のワークフローとしては単語をスカラーとして扱い、その単語が文中に出てくれば1,出てこなければ0としてバイナリ化し、単語の種類数の長さをもつベクトルで表現する。

このときに問題となるのは、その単語が学習データにあればよいけれど、基本的には学習データにない単語に対しては判定ができないということにある。これに対処する方法としては、事前学習で台詞一般、文章一般を学習させておき、次に分類したいキャラの台詞を学習させて重みをつけるという方法が１つ考えられる。

次に、キャラクターは単語空間上で近い言葉をしゃべる可能性が高いだろうという推定を置いて、単語のベクトル表現を利用することが考えられる。以後、その方法について考えたい。

Word2vec考

Google Code Archive - Long-term storage for Google Code Project Hosting.

Word2vecは単語のベクトルを表現を得る際に使われる。このベクトル表現で、類似した単語は近傍で得られるという過程を置く。これもさんざん各所で説明されているが、Word2Vecは主にCBoWとSkip-Gramと呼ばれる2つのアルゴリズムで構成されている。

• CBoW: 周囲の文脈から出現する単語を推定するNN
• Skip-gram: 単語から周囲の文脈を推定するNN

このWord2Vecを使うことで、単語のベクトル表現を抽出することができる。日本語コーパスとしてここで、Wikipediaを用いることとする。

saiyu.cocolog-nifty.com

上記の手順を使えば、Mecab-ipadicで単語分割を施したWikipedia産の単語の200次元ベクトル表現を得ることができる。pythonバインディングを使うことで、生のベクトル表現を手に入れることも可能である。

from gensim.models import Word2Vec

w2v = Word2Vec.load_word2vec_format('./jawiki.bin', binary=True)  # C binary format

words = raw_input().split()
vector = []
for word in words:
  try:
    vector.append(w2v[word.decode('utf-8')])

ワークフロー考

これを用いて、以下のワークフローを考える。

• 台詞をMecabで分かち書きし、単語それぞれword2vecを用いてベクトル表現を受け取る。
• そのベクトル表現から"文のベクトル表現"なるものを抽出し、それをNNで学習させ、分類問題を解く。

次に文のベクトル表現をどうやって生成するかだが、そのまま単語を200次元のベクトルに変換すると、台詞は200x単語数の可変長ベクトルになってしまい、そのままではMLPの入力にはできない。そこで以下の2選択肢があるように思う。

1. 固定長の文ベクトルを計算し、それを入力とする。
2. 可変長入力を学習できるレイヤーを用意する。

このうち1.について考えると、単語ベクトルを平均するなり和をとるなりすれば、確かに200次元のベクトル表現を作ることは可能だ。しかし和をとるとすると台詞の長短によって結果が左右されてしまうし、平均をとったところでそもそもその単語ベクトルには多分に文脈情報が含まれているはずであり、その平均をとるというのはいったい何を意味するのかという疑念が残る。

そこで、2.について考えたい。

可変長入力を受け付けられるニューラルネットモデル

RNN(Reccurent Neural Network)が可変長入力を受け付けられるモデルとして考えられる。RNNでは一般に、内部に再帰的なループを持つことで、それ以前に受けとった入力を"記憶"しておくことが可能であり、LSTMやGRUといったユニットが提案されている。このユニットがあることで、時刻tの入力に対して、時刻t-1までの入力によって得られた重みも同時に入力として次の重みを計算することが可能となる。一般には時系列データに対して適用される。

LSTMの詳細については下の記事が詳しい。

qiita.com

時系列データのように、過去から未来への一方向なデータに対しては順方向なRNNが用いられるが、未来から過去に対する因果関係が存在するような場合は、双方向RNNが用いられることがある。

さて、ここではLSTMを使って可変長入力を受取り、分類するようなモデルをkerasで記述した。モデルとしては以下のような形になった。

model = Sequential()
model.add(LSTM(output_dim=256, batch_input_shape=(batch_size, 58, 200), return_sequences=False))
model.add(Dense(nb_classes))
model.add(Activation("softmax"))

model.summary()

このモデルが本当に動いているか自信がない。というのも学習は進んだものの、汎化性能を獲得するには至らなかったからだ。それにpredict時に毎回word2vecをロードするので時間がかかっている。そういうこともありいささか筋悪な手法だとは思うのだが、誰か詳しい方の解説を乞いたい。

外挿性の問題

「データをつなげて論理的に実現方法がわかるものしか機械学習できない」というのはその通りで、基本的に機械学習であってもデータの補間はできても外挿は難しい。つまり学習させたものと同じようなテストケースに対しては正答できても、違う類の問題に対しては答えられない。しかしもしディープラーニングによって解きたい問題よりメタな概念を学習させることができるならば、その下位概念（＝いま解きたい問題）に対してもある程度正答率の高いモデルを得ることができるのではないかと思う。実際に実現可能かは分からない。

ownCloudのアプリを作る

tl;dr

ownCloudはphp製のオープンソースオンラインストレージであり、社内Dropboxのようなものとして使えるが、プラグインのような形でAppを自作・追加することができます。このAppはHookやCronジョブのほか、ownCloud内にアプリ用のページを実装することもできます。しかし日本語の資料が乏しく、マニュアルも十分に整備されていないので自分でソースコードを読みながら適宜、実装を書いていく必要があります。

App Development — ownCloud Developer Manual 9.0 documentation

以下ではownCloud9.0を対象に、アプリを作る上で気になったことや引っかかったことをメモしておきます。

アプリの作り方とデバッグ方法

アプリは、\apps内にフォルダを作って置けば良い。予めocdevというコマンドラインツールをダウンロードしておいて、\appsフォルダ内で

ocdev startapp OwnNotes

というコマンドを叩くことでディレクトリが自動で生成されます。ここで注意しなければならないのは、イニシャルキャピタルのキャメルケースでアプリ名を定めなければならないということです。実際に生成されるフォルダはすべて小文字になっているので注意。ここで決めるアプリ名が、そのまま名前空間になります。モジュール名は例えば\OCA\MyApp\Controller\PageController が /apps/myapp/controller/pagecontroller.php に対応しているように、ファイル名のスラッシュの向きが入れ替わってキャメルケースになります。

デバッグですが、php初心者の私はひたすらownCloudのログに出力するという方法をとっていました。\data\ownCloud.logをless +Fして眺めていましたが、このログはそのままでは少しみずらいです。一方でWeb上の管理画面でログを見ることはできますが、そうすると今度は自分で更新しなきゃならないので痛し痒しです。

Hookが効かない

Fileが書き込まれたときにHookして、callback関数で書き込まれたファイルのNodeを取得して、中身をあれこれするコードを書こうと思った時のための備忘録。

\OCP\Util::connectHook('OC_Filesystem', 'post_write', 'OCA\OwnNotes\Hooks\UserHooks', 'postWrite');

こうすると、ownnotes/hooks/userhooks.phpのclass UserHooksのシングルトンメソッドとしてstatic public def postWrite($args)を定義すればよいのですが、この戻り値が曲者で、返ってくる値は

{
"run" => 1,
"path" => "\aaa.txt",
}

みたいな形になります。(実際にはphpのデータ構造です。var_export($node, true)みたいなコードを書くと、文字列型として出力されます。)

このコードを読む限り、このpathをNodeにするにはHookConnectorのgetNodeForPathを呼ばなければならないのですが、private methodなのでクラスのインスタンスを作らなければなりません。しかしコンストラクタには$rootと$viewが必要となって、厄介なのでやはり引数として[$node]自体が返ってくるようにしたいです。

というわけで、上のページを参考にしてhookを定めます。registerメソッド内でHookをlistenしておいてapp起動時にregisterを呼ぶようにしておけば、この時呼ばれるcallbackメソッドの引数はNodeになります。

ファイルの作成/更新ができない

Filesystem — ownCloud Developer Manual 9.0 documentation

    public function writeTxt($content) {
        // check if file exists and write to it if possible
        try {
            try {
                $file = $this->storage->get('/myfile.txt');
            } catch(\OCP\Files\NotFoundException $e) {
                $this->storage->touch('/myfile.txt');
                $file = $this->storage->get('/myfile.txt');
            }

            // the id can be accessed by $file->getId();
            $file->putContent($content);

        } catch(\OCP\Files\NotPermittedException $e) {
            // you have to create this exception by yourself ;)
            throw new StorageException('Cant write to file');
        }
   }

ドキュメントにあるコードそのままですが、\OCP\Files\NotPermittedExceptionが出てしまってファイルを書き込めません。

若者の生態を青春小説の系譜から探る

若者 は常に、良くも悪くも時代を象徴する存在であった。太陽族、竹の子族、ヒッピー、アッシー君……といった時代を象徴する文化や言葉には、背後に若者の大きな力があった。しかしながら、一億総中流と呼ばれた日本人が多様化をする中で、人口に対する若者の占める割合が低下するだけでなく若者間での共通性が失われてきたのが現代の若者である。そう、もはや彼らを若者としてひとくくりに扱えるほどの共通性をもつ集団が存在しているわけではないのだ。

古市憲寿(2011)「絶望の国の幸福な若者たち」は、まさにそういった現代の若者をデータとインタビューの両面から切り取る資料集として非常に興味深い。

絶望の国の幸福な若者たち (講談社+α文庫)

一方でかつての若者、特に学生はいったいどのように生きていたのだろうか。

しばしば語られることであるが、「大きな物語」の瓦解がもたらした影響は大きい。現代の若者は共通の文脈を失っている。かつてはほとんどの家庭が視ていたテレビ、そこで流される野球中継といったものは少なからず話題を生み出す役割を果たしていたはずだ。しかし今はそういった共通の中心軸となる話題もなく、個々人はより細分化された人間関係の中で過ごすようになっている。そういった現代の視点から過去を見渡したとき、いったいどのような変化がみられるのだろうか。

ここでは私が独断と偏見で選んだ学生を主人公とする小説を追いながら、それぞれの時代の学生事情を詳らかにしたい。また大澤真幸(2008)「不可能性の時代」に倣った時代区分を採用した。時代の先端をゆく若者であるからこそ、時代の空気に大きく影響を受けた生き方をしているのではないかと思う。昔に読んだ本ばかりなので記憶が曖昧であるし、そこまで深く掘り下げて考えたわけでもないし、かなり適当なことを言っている部分もあるが、それはそれとして最後まで読んでいただけたら幸いである。

不可能性の時代 (岩波新書)

ポスト学生紛争（理想の時代～虚構の時代Ⅰ）

赤頭巾ちゃん気をつけて (新潮文庫)

ぼくらの七日間戦争 (角川文庫)

この時代の有名な本は、学生運動という一時代が終わった虚脱感としらけの中で発生してきたといってもよい。ちょうど学生紛争以後に大学に入学した世代を「しらけ世代」と呼ぶように。

学生運動は、腐敗した大学上層部の粉砕を目論んだものが始まりではあったが、それが労使対立や新左翼運動と結びつき大規模なムーブメントとなった。しかしそれは過激化を招き、一般大衆の離反と先鋭化したメンバーによる浅間山荘事件を引き起こした。このように日本の革命はなしえなかったものの、而して大学解体じたいは成功した。大学全入時代の到来により大学生は量産されるようになったが、一方で彼らの全員が高い学習意欲を持っていたわけではない。その帰結として大学は以後、レジャーランド化の一途をたどるようになったのだ。

その中で、庄司薫(1969)「赤頭巾ちゃん気をつけて」は学生運動のあおりを受けて東大入試がなくなった年の浪人生が、人間との関わりを通して学問や人生について思索をめぐらし、その中で主人公が成長を遂げる成長譚である。

学生運動というある意味で悩める若者を吸収して有り余るエネルギーを議論と破壊に向けたはけ口がなくなったことで、若者は自律的に悩むことが求められるようになった混乱期の若者のあり方を等身大に描いているように感じる。そしてその悩みが若者で共有されたからこそ、多くの若者が当時この本を手に取り、芥川賞を受賞したのではないかと思う。身近なちっぽけなことからもっと規模の大きなことまでひっくるめて若者は悩んでいたのではないか、と感じさせる。少なくとも、人間関係や目先の就職だけに悩みが収斂していたとは思えない。

宗田理(1985)「ぼくらの七日間戦争」も同様のポスト学生運動期を描いた作品であったが、こちらはどちらかというと学生運動に対する回顧的、懐古的心情が強く、全共闘の亡霊を中学生の悪戯に仮託しているところが逆に、若い瑞々しい感性からの乖離を感じさせる。もちろん、読み物としては面白く、中学生が知恵を駆使して大人達の裏をかいていく姿はまさに痛快である。

ノルウェイの森 上 (講談社文庫)

ノルウェイの森 下 (講談社文庫)

一方で全く学生運動に関心を抱かない層もある。それが村上春樹(1987)「ノルウェイの森」だ。ここでの主人公（ワタナベ君）は学生運動を横目に見ながら、而して学生運動や学問というものにはまったく興味を持たず恋愛ゲームに興じ、過去の因縁にとらわれている。

村上春樹の場合、多くの作品で過去が重要なモチーフになっている。過去に囚われた主人公、過去の束縛から逃れられないヒロインなど、そういった登場人物を描く限り、将来を考えるためにはまず過去を解決しなければならないし、それが主題となってしまうのだから、彼らから前向きな悩みを見いだすのは難しいのかも知れない。だが一方で、過去の悩みはその時々の世相に左右される現在や将来の生活に比べて普遍的/時代に囚われないことが多く、それが彼の作品が長く人々を楽しませていることにつながっているのだろう。

バブル期（虚構の時代Ⅱ）

なんとなく、クリスタル (新潮文庫)

学生運動というある意味での理想を追い求める運動が破綻し、人々が虚構に溺れるようになったのが1970年代以後の「虚構の時代」とするならば、その頂点がバブル期であろう。 その中で田中康夫(1980)「なんとなく、クリスタル」はブランドという虚構に溺れながら、自律的な生活を送る恋人どうしの生活を端的な文章で表現する、バブル期を象徴する文学なのではないかと思う。

膨大な脚注は、それをシニカルな視点からメタ的に捉えている。そこではブランドが過剰なまでに記述される一方で、大学名については適度にぼやかされているところが、かえって学歴としての大学名が飾り立てたブランドよりも価値を有していると考えていることが暗黙裡に示唆される。彼らの生活の主体はもはや大学ではなく仕事であるにも関わらず、大学名にはやはり価値があるのだ。

田中康夫の小説は、どのような人生を送るかや将来を悩むということよりも「なんとなく」や「気分」で今を生きることを当然のようにとらえている。しかしそれは残念ながらバブル崩壊以後の現代には通用しない観念となってしまった。これが村上春樹と好対照を為している。彼らはどちらも若者を主人公に据えた小説を書き、時代の寵児となったわけだが、村上春樹の作品群はそれ以降の時代でも受容され、毎年ノーベル文学賞を取るのではないかと騒がれているが、作品自体が特定の年代/時代を扱うものが多いといえども、翻訳文体ともいわれるその文体じたいは時代に依存していないために、原典は日本語そのものが変革するまで読み続けられるだろう。一方、とうの田中康夫はそれ以降、批評家、そして政治家へ転向し、なんクリ自体はそれが古典小説と同様の扱いを受けるようになったことがそのことの何よりの証左だろう。

だがもう一作バブル期には面白い作品がある。それが杉元伶一(1991)の「就職戦線異状なし」だ。これは織田裕二主演の映画の方でしか観たことがないのだが、空前の（そして恐らく絶後の）売り手市場であったバブル期であって、就活はできるだけ良い会社に入るレースゲームのように捉えられていた中で、就活をしていくうちに段々、「本当に自分のやりたいこと」を見いだしていくというストーリーである。その中の一節で、「なりたいものではなく、なれるものを探し始めたら大人だ」という登場人物の台詞がある。それは正鵠を射ている。だがやりたいことをやる、なりたいものになろうとするのは若者の特権でもあるはずだ。それこそ当時よりも更に就活のあり方が画一化され、インターネットの普及により容易に大量に企業にエントリーできるようになった現代は企業とのマッチングはますます難しいものになっている一方で、経団連指針により就活期間は短くなっているという厳しい現実だが、その中でどう就活していくかということに対して作品の持つメッセージは色褪せていないはずだ。

失われた20年（不可能性の時代）

大澤は1995年以降を「不可能性の時代」と呼んだ。この時代を「現実への逃避」という言葉で象徴したが、それは大澤の言葉を借りるならば「第三者の審級」の衰退と軌を一にしていたといえよう。世俗化による信仰の衰退に加え、ソ連崩壊による共産主義への幻滅が進み、日本ではバブル崩壊で成長神話も崩れた。それはつまり「大きな物語」の崩壊であった。それ以後人々は多様性の名のもとにお互いを許容し、尊重しあうことが求められた。

それと同時にセキュリティ化が進んだ。これの意味するところはジジェクの言うところのカフェインレス・コーヒーやノンアルコールビールのような無害な危険であり、主張なきデモであり、その究極系が美少女ゲームのような、恋愛や生身の身体性といった現実の面倒な手続きなしにセックスを体験することのできるバーチャル・リアリティである。科学の発展は、様々な危険から危険を取り除くことに成功した。しかしその手法はときに、現実と精神を仲立ちする中間媒体を設けることがしばしばあり、結果として久しく我々は、身体性を欠いたアンバランスな生活を送っている。

一方で変化する現実を受け入れられない人々が「大きな物語」を求めたが、その手法は極めて肉体的、身体的なものであった。その行き着く先がテロルや暴力であり、そういった破壊的な行為による原理への回帰を求めた。その帰結が9.11であり、その後の一連のテロとの戦いであり、例えば秋葉原連続通り魔事件もその発露ではないかと考えられる。

まさに現実が消毒されるのと対照的に失われた身体の感覚を取り戻さんとして暴力、自傷行為に走る人々が増えているのは、高度なセキュリティ化が生み出した矛盾といって差し支えないだろう。

将来が不安であるがゆえに若者は今が幸福だと考える。これは古市の見方だが、私は実際に今の日本の若者は「なんとなく」生きることはできず、そのかりそめの幸福を刹那的に享受するか、さもなくばその不安に押しつぶされながらひたすらにペシミスティックに（あるいは絶望して）生きるか、そのどちらかに収斂しているのではないかとみている。

参考ページ

なんとなく、クリスタル

http://d.hatena.ne.jp/SuzuTamaki/20080522/1211421607d.hatena.ne.jp

Wantedly SyncのGithub連携を試してみる

Wantedlyがリリースしている社内向けグループチャットツールSyncに、github連携できる機能がついたので早速試してみました。 github連携を有効にすると、プルリクなどを通知してくれるようになります。

方法

• Syncにアクセスします。

Sync

• 左下の歯車のマークをクリックし、外部サービス連携を押します。

• Githubを選びます。

• Authorizeします。

• リポジトリを設定します。

これで設定終了です。

• 試しにプルリクを立ててみる

プルリクの通知が届いていますね。確かに連携は成功です。

今回はWeb版で試してみましたが、普段はLinux環境で過ごしているので、SyncのクライアントアプリもLinuxのバイナリで提供してくれると嬉しいですね。（需要はなさそうですが...）

サイボウズ、ChatWork、Skype、Slack、チャットワークと様々なチャットツールを今まで使ってきましたが、Sync自体はslackとか違って非エンジニアの方でも便利に使えるし、他のチャットツールと違ってエンジニアに近い方も便利に使える多機能なチャットツールだと思います。

余談

誰なんだ！

ディープラーニングをKerasというフレームワーク上で行う

はじめに

機械学習、特にディープラーニングが近頃（といってもだいぶ前の話になりますが）盛んになっています。CaffeやChainerといったフレームワークもありますが、特にGoogleがTensorflowでtensorboardと呼ばれる簡単に使える可視化基盤を提供して有名になったのを機に、Tensorflowで機械学習を始めてみたという方も少なくないと思います。

しかしTensorflowは低レイヤーな行列演算、ベクトル演算を記述するには適していますが、機械学習モデルの記述という面では書きにくいことも確かで、何かが動いていることは確かめられたけれど自分で何かをするには敷居が高かったです。例えば、Tensorflowでsoftmax層を定義するには、以下のコードを書く必要があります。

 # softmax, i.e. softmax(WX + b)
  with tf.variable_scope('softmax_linear') as scope:
    weights = _variable_with_weight_decay('weights', [192, NUM_CLASSES],
                                          stddev=1/192.0, wd=0.0)
    biases = _variable_on_cpu('biases', [NUM_CLASSES],
                              tf.constant_initializer(0.0))
    softmax_linear = tf.add(tf.matmul(local4, weights), biases, name=scope.name)
_activation_summary(softmax_linear)

（https://github.com/tensorflow/tensorflow/blob/r0.7/tensorflow/models/image/cifar10/cifar10.pyから引用）

もちろん機械学習の研究をする場合や、細かくモデルを定義してチューニングをゴリゴリしたい場合には、これぐらい表現力が高い方がよいかもしれません。しかし数学が苦手だったり、趣味レベルで少し触ってみたいだけだったり、短い時間である程度の成果を上げたかったりする人にとっては、下のようにモデルに追加する層を列挙する形で書けると便利ですよね。

model.add(Activation('softmax'))

ここでKeras(Keras Documentation)というフレームワークを導入します。これは簡単な記法で（短いコードで）機械学習のモデルを書き下せる上、すぐに類似した問題に応用可能なsampleがついています。またバックエンドにTheanoの他Tensorflowを適用できるため、Tensorflowとほとんど変わらない速度で、しかも簡易な記法で記述したモデルを試すことが可能です。ここではKerasを用いてCNNで簡単なカラー画像の分類モデルを組み立て、学習させ、実際に予測をするサービスを作ろうとする上のtipsをメモしておきます。先に断っておきますが、私は機械学習の専門家でも、またそれを専門に学んでいるわけでもないため、ディープラーニングに対する記述には正しくない点も多く含まれていることをご了承下さい。

モデルをどう構築するか

従来の機械学習や統計、例えばSVMや回帰分析では、特徴量は自分で抽出しなければなりませんでした。しかしディープラーニングでは、その特徴量抽出は隠れ層の重みの学習に置き換えられるので、適切な学習データを用意することで特徴量自体の検出を機械に委ねることが可能になりました。従って必要となるのはどういったモデルを作るかということと、どう入力画像を扱うか、さらに言えば解きたい問題をどのように機械学習の枠組みに落とし込むかという３つになるでしょう。

Tensorflowよりモデルの構築は容易になったとはいえ、私のような初学者はいったいどのようにモデルを構築すればいいのか検討もつきませんが、画像を扱うにはいくつかの方法があって、MNISTとよばれるグレースケールの手書き数字認識では(MNIST handwritten digit database, Yann LeCun, Corinna Cortes and Chris Burges)多層パーセプトロンと畳み込みニューラルネットワークのサンプルがありました。kerasのexamplesフォルダにあるmnist_cnn.pyとmnist_mlp.pyを比べると分かりますが、CNNではモデルの中に

model.add(Convolution2D(nb_filters, nb_conv, nb_conv,
                        border_mode='valid',
                        input_shape=(1, img_rows, img_cols)))
model.add(Activation('relu'))
model.add(Convolution2D(nb_filters, nb_conv, nb_conv))
model.add(Activation('relu'))
model.add(MaxPooling2D(pool_size=(nb_pool, nb_pool)))
model.add(Dropout(0.25))

このような畳み込み層（CNNのCは畳み込み:Convolutionalのcです）が入力と多層パーセプトロンの間に組み込まれています。それぞれの意味としてはConvolution2Dでが画像にフィルタを掛けて特徴量を抽出し、Max Pooling層が最大の値をサンプリングすることで、その値の位置感度を下げます。そして最後のDropout層によって出力をここでは4分の1にして過学習を防いでいるといった感じでしょうか。またノードからの出力の総和を計算する際、reluと呼ばれる活性化関数が用いられていますが、これはmax(0, x)で定義される関数で、負の入力に対しては0を返しますが、正の入力に対しては線形の出力が返されます。これによってある程度疎な行列が得られるので行列演算にも都合がよく隠れ層でよく使われる一方で、最終的な出力を得る際には表現力が貧弱だということもあり、softmax関数が使っているようです。

実際にサンプルのコメントにもあるように精度はCNNの方が高いですし、Cifar10(CIFAR-10 and CIFAR-100 datasets)とよばれるカラー画像6万枚の10分類のサンプルコードはCNN版しかありません。TensorflowでもCNNによる実装がチュートリアルにあったはずです。恐らくこのようなフルカラーの画像を扱う上では、計算コストはかかりますが畳み込み層を入れたほうがよいのでしょう。更にCNNのよいところは、全層結合のモデルで画像認識させる際に必要となる初期化処理（自己符号化器などを用いて、前もって適当な重みをそれぞれのノードにかけておかなければならない）をせずに学習させることができるところにもあります。

Kerasではこういった一直線のSequentialなモデルは、層を列挙していくだけで簡単に記述することができます。CNNを用いることとした上で、サンプルのモデルを使って数字をいろいろ変えてみてチューニングするといったことをしました。より高度なモデルを作るとしたら、論文を読むとか、強い人のものを参考にするという方法もあります。

github.com

例えばこのように公開されているKaggleで用いられたNeural Network Configurationsを参考にして層を増やすといったことは考えられます。ただ一方で、モデルを複雑にしたところでそもそも学習させる画像データが少ない場合、計算時間ばかりかかって満足できる結果を得ることにはつながりませんでした。

入力の扱い

機械学習に食わせるためには、入力を区間[0,1]のn次元配列（テンソル？）にする必要があります。例えば文章であれば文を単語に分けて、同じ単語に対して一意の数字を割り振ったベクトルとして表現できます。デジタル画像では、BMP形式だとわかりやすいですが1ピクセルに対してグレースケールであれば1つの値、カラー画像であればRGBの3つの値で表現することがすでにできているので、それをそのまま入力とすることを考えます。（ただし0〜1の範囲に落とし込むため、255で割る必要があります。逆に255で2回割ってしまうと全く予測結果がおかしなことになるので注意）

Kerasの例をみると、MNISTのようなグレースケールのものは1枚の画像は縦☓横の2次元配列で表されて、それ自体が1つの配列にすべて格納されている形で学習データを構成するので実質は3次元配列が入力全体となります。cifar10ではカラー画像なので1枚の画像は縦x横xRGBの3次元配列で表されて、それを1つの配列に全部格納するので実質4次元配列が入力の形となります。

分類結果は5値分類であれば0,1,2,3,4のように表現されますが、ここではバイナリ配列として扱う([1,0,0,0,0],[0,1,0,0,0],...のように)必要があります。これは関数が用意されているのでそのまま使います。

Y_train = np_utils.to_categorical(y_train, nb_classes)
Y_test = np_utils.to_categorical(y_test, nb_classes)

ではcifar10の場合に入力配列をどう生成するかということですが、Tensorflowではバイナリファイルから読み込むスタイルでした。このバイナリファイルの構造は簡単で1行に1画像であり、最初の1バイトが分類値で、次にRGB値が1024バイトごと入っているものでしたが、KerasではPythonのcPickle化されたものを入力として使っていました。サンプルコードをそのまま流用するためには画像をcPickleに落とし込まなければならないのですが、好きな画像群からダンプする場合は下の記事のコードのインスタンス変数名を少し変更することでカラー画像の読み込みを作ることができました。

qiita.com

私はこの時に、上下位置を少しずつずらした画像を作って学習効率の増強に努めました。KerasにもImageDataGeneratorというのがあって画像を適切に加工してくれるようなのですが、私が試した時はデータ数が少ないためもあったのか、うまくいきませんでした。（何度学習させてもlossが減らない、学習中に明らかにおかしいlossの変動がみられるなど）

また入力画像として、あまり関連性のない画像を分類問題として与えるとうまくいかないことが多かったです。例えば画像がアニメキャラのものか実在する人間のものかを二値分類するのはそれなりに精度がよかったのですが、あるアニメの登場人物と別のアニメの登場人物をそれぞれ集合として与えた時、登場人物1人につき1枚ずつの写真が大量にあったとしても、うまくいきませんでした。

予測するには

Tensorflowではセッションに対してrunを呼ぶとき、学習データと分類値を入れれば学習になるし、feed_dict=にテストデータを与えれば分類が受け取れるということのようだったのですが、Kerasではpredictという専用の関数があります。これに学習データを投げると、配列で受け取ることができます。またpredict_classesを呼ぶと、分類結果のラベルだけを表示してくれます。

学習させた後のモデルを最後にこんな感じのコードを追加すると、architecture.jsonにはモデル構造がJSON形式で、weights.h5にはそれぞれのノードの重みが保存されます。

model_json = model.to_json()
open('architecture.json', 'w').write(model_json)
model.save_weights('weights.h5', overwrite=True)

予測させたいときには

def load_model(model_def_fname, model_weight_fname):
   model = model_from_json(open(model_def_fname).read())
   model.load_weights(model_weight_fname)

こんな感じで呼べるので、これを再びコンパイルしたものを使ってpredictすると、1回の学習データをもとにさまざまなデータに対して予測をすることが簡単にできます。

ところでこれはpythonというかnumpyのtipsなのですが、多値分類は結果の値が指数表現になることがあります。こうなってしまったとき小数点以下の値が見にくいときは、

import numpy as np

np.set_printoptions(suppress=True) # 小数表現にする
np.set_printoptions(precision=3) # 小数点以下3桁まで表示させるようにする

と書くとprintしたときにわかりやすくなるでしょう。

サービス化する

Kerasを使った予測サービスをWeb上で展開しようというとき、金があればいくらでも方法はあるのですが、個人レベルで且つ無料で済ませたい（且つアクセスを期待しない）場合はどうするかという問題があって、検討した結果を記述します。

ここでやりたいのは学習済みのarchitecture.json、weights.h5を置き、解析用のコードとwebサーバーを立てておいて、そこに入力のベクトルをPOSTすると予測結果を返すものを作るということです。TensorflowはPythonなので、Webサーバーは同じくPythonのFlaskとかで記述すると書きやすいです。

heroku

herokuは18時間までならタダで動かせるのでこれを使うのが一番王道だと思いますが、dockerコンテナを立てるにはクレジットカードが必要です。そうしない場合はKerasのバックエンドとなるTensorflow、Theanoをどちらもheroku上にインストールすることができませんでした。Theanoをrequirements.txtに記述してpush時にpipでインストールさせようとしても、まず最新バージョンが落とせない。それにビルドの途中で

 Problem occurred during compilation with the command line below:
 /usr/bin/g++ -shared -g -march=core-avx-i -mcx16 -msahf -mno-movbe -maes -mpclmul -mpopcnt -mno-abm -mno-lwp -mno-fma -mno-fma4 -mno-xop -mno-bmi -mno-bmi2 -mno-tbm -mavx -mno-avx2 -msse4.2 -msse4.1 -mno-lzcnt -mno-rtm -mno-hle -mrdrnd -mf16c -mfsgsbase -mno-rdseed -mno-prfchw -mno-adx -mfxsr -mxsave -mxsaveopt --param l1-cache-size=32 --param l1-cache-line-size=64 --param l2-cache-size=25600 -mtune=core-avx-i -DNPY_NO_DEPRECATED_API=NPY_1_7_API_VERSION -m64 -fPIC -I/app/.heroku/python/lib/python2.7/site-packages/numpy/core/include -I/app/.heroku/python/include/python2.7 -I/app/.heroku/python/lib/python2.7/site-packages/theano/gof -fvisibility=hidden -o /app/.theano/compiledir_Linux-3.13--generic-x86_64-with-debian-jessie-sid-x86_64-2.7.7-64/lazylinker_ext/lazylinker_ext.so /app/.theano/compiledir_Linux-3.13--generic-x86_64-with-debian-jessie-sid-x86_64-2.7.7-64/lazylinker_ext/mod.cpp -L/app/.heroku/python/lib -lpython2.7
 /usr/bin/ld: /app/.heroku/python/lib/libpython2.7.a(abstract.o): relocation R_X86_64_32S against `_Py_NotImplementedStruct' can not be used when making a shared object; recompile with -fPIC
 /app/.heroku/python/lib/libpython2.7.a: error adding symbols: Bad value
 collect2: error: ld returned 1 exit status

というエラーメッセージが出て駄目でした。Tensorflowは下のページを見る限り動かなさそうでしたし、herokuを予測サーバーに使うのは断念しました。

d.hatena.ne.jp

Openshift Online

これもしばしば無料でWebサーバー立てる際に使うのですが、今回は試していないです。

Arukas.io

arukas.io

さくらインターネットが出しているDockerホスティングサービス。つい最近公開されましたが、Dockerイメージを今の所制約なしにホスティングしてくれるのはかなりありがたいです。TheanoやTensoflowのインストールでこけるぐらいなら、全部入りのDockerイメージをアップロードしてしまうほうがはるかに楽で、Dockerfileにkeras + tensorflow + flaskを入れる設定を書いてDocker hubにアップロードし、それをArukas.ioにデプロイするというフローで拍子抜けするほど簡単に予測サーバーを立てることができました。メモリは512MBに設定していますが予測する分ならほとんど手元のマシンと変わらない速度で動いている感があります。

続き

Kerasを用いて様々な処理を施した所感は以下になります。

sharply.hatenablog.com

Refernces

Neural Networks using Keras on Rescale | Rescale

Deep Learningと画像認識　～歴史・理論・実践～ from nlab_utokyo

www.slideshare.net

github.com