備忘録 blog

Docker/Machine Learning/Linux

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となることを待つ。通常、待ち時間はランダマイズされるので、そのうちこのコンフリクトは解決するだろう。

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

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

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に比べて理解はやさしい。

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

f:id:sharply:20160611191544p:plain

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

f:id:sharply:20160611191645p:plain

ビザンチン障害

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

相互に通信しあう何らかのオブジェクト群において、通信および個々のオブジェクトが故障または故意によって偽の情報を伝達する可能性がある場合に、全体として正しい合意を形成できるかを問う問題である。 (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プラスシリーズ)

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

Consensus Protocols: Paxos : Paper Trail

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について

http://i.imgur.com/2dKCQHh.gif

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

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

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

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

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

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.logless +Fして眺めていましたが、このログはそのままでは少しみずらいです。一方でWeb上の管理画面でログを見ることはできますが、そうすると今度は自分で更新しなきゃならないので痛し痒しです。

Hookが効かない

https://doc.owncloud.org/api/classes/OCP.Files.Node.html

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

https://doc.owncloud.org/server/9.0/developer_manual/app/init.html

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

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

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

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

https://github.com/owncloud/core/blob/master/lib/private/Files/Node/HookConnector.php

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

https://doc.owncloud.org/server/9.0/developer_manual/app/hooks.html

というわけで、上のページを参考にして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

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

f:id:sharply:20160514204330p:plain

f:id:sharply:20160514204454p:plain

  • Authorizeします。

f:id:sharply:20160514204907p:plain

f:id:sharply:20160516092632j:plain

これで設定終了です。

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

f:id:sharply:20160516092644j:plain

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

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

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

余談

誰なんだ!

f:id:sharply:20160514205418p:plain

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

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

www.slideshare.net

github.com

IBMのx10チュートリアルをやる

tl;dr

IBMのx10言語という、並列計算に向いた言語がある。言語仕様の詳細は省くが、scalaライクにオブジェクト指向で書ける言語の割に、MPIほど面倒なことを書かなくてもネイティブなC/C++のコードを吐いてくれるので速度が出るというありがたい言語である。

このチュートリアルをやってみた時に戸惑ったことの備忘録。なお、バージョンアップによる記法の変動が割と大きいので注意されたし。以下の環境で動作を確認。

x10c++ version 2.5.4

x10-lang.org

なお、見るとわかるがver2.5のチュートリアルはなく、ver2.4のチュートリアルはAPGASと呼ばれるjava用のライブラリの説明しかないので、ver2.2のものを使うしかないので注意。

Sequential Monti Pi

(-1,-1),(1,1),(-1,1),(1,-1)で囲まれた空間にランダムに点を打ったとき、円周内に入った点の数から円周率を計算できるというもの。モンテカルロ法の亜種。

  • args:Rail[String]

argsの後のRailは引数不要になっているので、()を外そう。

The x10.lang.Rail class also provides a similar, high-performance implementation of a one dimensional array. The expectation should be that a Array_1 and a Rail should have very similar performance characteristics, although the Array_1 has an additional wrapper object and thus may have marginally lower performance in some situations.

Arrayクラスもあるのだが、一次元配列の場合はより高速なRailを使うのがよいかもしれない。

  • Place.MAX_PLACES is duplicated by Place.numPlaces()

MAX_PLACESで検索しても古いドキュメントしか出てこなくて途方に暮れてしまうのだが、Placeクラスのドキュメントを見るとnumPlaces()になっているらしい。

その他のtips

  • Mismatched input 'var' expecting {'--', '|', '-', '!', '!=', '%', '&', '&&', '(', '*', ',', '.', '/', ';', '?', '[', '^', '||', '~', '+', '++', '<', '<<', '>>', '>>>', '<=', '==', '>', '>=', '..', '->', '<:', ':>', '**', '!~', '<-', '-<', '>-', '<>', '><', 'as', 'haszero', 'instanceof', 'isref'}

このエラーを見かけたら;が欠落していることを疑ったほうが良い。CやC++と同様。

  • 配列の添字を()で表す

CやC++に慣れていると[]とついつい書いてしまうがエラーが出る。

  • 型のキャストをas Intのようにする。
val x:Long = 4 as Long;
val x:Long = 4L;

例えばLong型であれば数字リテラルの末尾にLをつけるだけでもよい。Byte型やらShort型やらchar型やら、型はやたらめったら出てくるので場合に応じた適切なものを用いるとよい。

  • staticをつけるとクラスに属するメソッドになる

これはC++JAVAと同じですが、rubyでいうところのシングルトンメソッド・特異メソッドになります。実際にはrubyのシングルトンメソッドは外から呼べるので、public staticに対応しているといえるでしょう。staticにするだけでは、クラスの内部からしか呼べません。

(x10)

class Node {
  public static def length(){
  }
}

(ruby)

class Node
  def self.length
    
  end
end
  • Pair型 Pair(T first, U second) 例えば関数の返り値をペアにできる。

Gentoo Linuxにxmonadを導入する

動機

Gentoo Linuxではコンパイルに時間がかかるので、大規模なデスクトップ環境を構築しようとするとすごい時間がかかる。 当方はGNOME派だが、恐らくGNOMEKDEを入れるのは骨が折れるだろう。コテコテのデスクトップ環境を構築するのもそれはそれで一興だが、今回は敢えて軽量な環境とするためにタイル型を導入してみたいと思う。

タイル型デスクトップ環境といえばawesomeも有名だが、ここではHaskellで設定ファイルが記述できるxmonadを導入することとした。

Emerge

# emerge xmonad xmonad-contrib xmobar

依存関係を確認すると、その場でコンパイルするのでghcが必要となり、これのコンパイルにものすごい時間がかかるので、先に入れておくとよい。xmonad-contribxmonadの設定ファイルを書く際に便利なアルゴリズムが同梱されているので導入しておきたい。また、ここではステータスバーとしてxmobarを入れることとした。

この他にもHaskellのcabalを使って導入する方法もあるが、せっかくPortageツリーに入っているのでemergeで入れることとした。

xmonadxmobarの相性について

xmonad上でアプリケーションを開きながらその上にxmobarを重ねる場合、設定ファイルにどう記述してもなぜか下に潜ってしまう問題が起きた。 これは0.12を使っていたからということらしい。gentooPortageツリーに入っていた安定版の0.11を使うと解決した。

Usage

modキーをAltに割り当てると他のキーバインドと重複して厄介なので、Windowsボタンに割り当てることとした。基本的な使い方は以下が詳しい。(但し以下ではGNOME共存させているが、今回はxmonad単体で実行している)

blog.blueblack.net

http://blog.drmn.jp/2013/04/haskell-xmonad.html

参考サイト

https://wiki.archlinuxjp.org/index.php/Xmonad

Gentoo Linuxでうどんワールドする

tl;dr

Gentoo LinuxPortageを使う際、

# emerge --uDNva @world

をしたときに大量に循環依存やエラーメッセージが出た場合の対処策。

まずはメッセージを読む

$ man emerge

emergeコマンドの説明(できれば英語版のようがよい)を読みながら、出力の意味を理解する。 USEフラグを立てろと言われた場合は、メッセージの通りに設定してもよいですが、私はflaggieを使って管理しています。 maskしろと言われた場合も同様。

例:app-emulation/dockerでaufsフラグを立てたい場合

$ sudo flaggie app-emulation/docker +aufs

それとnewsを読むと役に立つ情報が手にはいります。

$ eselect news read

循環参照じたいは、メッセージで表示されるパッケージに関わるUSEフラグを適当に-gtkとか-emacsとかしておいてからemergeして片方ずつ入れれば解決することが多いです。

ghcperlのコンフリクトを解決する

ghcperlといったプログラミング言語本体のパッケージの更新が関わってくると、バージョンの違いによって依存するライブラリがエラーを吐くことがあります。このときは関連するライブラリは入れずに、まずはghcperlだけを先に更新し、それからライブラリをツールを使って一括で更新する、ということでエラーメッセージを回避することができます。

@worldからやると関連のライブラリを更新しようとするためにエラーメッセージが出ることがあり、@systemをまず対象とするとエラーメッセージが出ないかもしれません。そうでない場合は個別にghcperlを選択し、更新をかけましょう。

その後しばしば@preserved-rebuildをしろというメッセージが出るので、実行しましょう。これによってパッケージの更新によって壊れた依存関係を解決してリビルドしてくれます。

emerge -1 @preserved-rebuild

ここで-1というフラグをつけることで、--oneshotつまり、ここで指定したパッケージは@worldに含まずに更新することができます。こうすることで、どうでもいいパッケージの更新を追尾せずにすむので、@worldの肥大化を防げます。

その後、perlであればperl-cleaner --all, pythonであればpython-updatorといったコマンドが用意されているので、その言語固有のパッケージの更新をかけることで、バージョンアップに伴う依存関係の再構築を行うことが可能です。

dispatch-confする

/etc/以下のファイルを、emergeによって推奨する設定に書き換えるとき、それらの作業は手動で行われなければなりません。 古い文献ではetc-updateしろと書いてある場合がありますが、dispatch-confのほうが良さそうです。

dispatch-conf の使い方 - WebOS Goodies

あとは最後に、不要となったパッケージを整理するだけです。

$ emerge --depclean

参考ページ

d.hatena.ne.jp

hanepjiv: Gentoo Linux / gentooのアップデート