しまてく

学んだ技術を書きためるブログ

ブロックチェーンについてナレッジコモンズに登壇してきました。

みなさんこんにちは。 ブロックチェーンやってますか?僕はやってます。

昨年末から今年始めのビットコインの高騰からその後の暴落、シビレますね!

そんなこんなでブロックチェーン界隈に身を寄せていたら、 ナレッジコモンズという勉強会を運営している先輩から「ブロックチェーンについて講師やってくれない?」とお願いされて、 それならばとやらせていただくことにしました。

ナレッジコモンズについて

knowledgecommons.net

「誰でも講師になれる勉強会」として、ナレコモは「下町のTED」を目指しています。

というビジョンの通り、さまざまな発表がされていてとてもおもしろい勉強会です。

僕は実は初めての参加でした。

55回目: ブロックチェーンの基礎を学び、未来に活かす。

knowledgecommons.connpass.com

枠としては2時間だったので、プレゼンは1時間想定で作ってたんですが 途中で質問もバンバンでる感じで2時間いっぱい使ってしまいました。

質問たくさんでるとやりやすくていいですね! シーンとすると結構つらいので質問されれればされるほどテンションあがりますw

資料はこんな感じです。

www.slideshare.net

驚いたのは、ナレッジコモンズの定番らしいのですが、「グラフィックレコーディング」という超絶テクをお持ちの 小野 奈津美さんが、僕の発表を聞きながらリアルタイムでサマリーを作ってくれました!

作成風景

f:id:cimadai:20170127165704j:plain

完成後には小野さんから全体の振り返り

f:id:cimadai:20170127165717j:plain

最後にはこのまとめを頂けるという素晴らしい特典もありました!

f:id:cimadai:20170127165729j:plain

とってもかわいくてとっても的を射た素晴らしいまとめです。 リアルタイムにまとめられていく様を見ながら話すのも素敵な体験でした。

ということでナレッジコモンズ運営の皆様ありがとうございます。

今後参加するのはもちろん、また機会があればお話したいと思いました!

ブロックチェーンっていいものですね。それでは。

builderscon tokyo 2016に参加してきました。

buildersconとは、

「知らなかった、を聞く」をテーマとした技術を愛する全てのギーク達のお祭りです。 https://builderscon.io/

ということで、ノンジャンルな技術的な発表をやったり聞いたりする集まりです。

私の会社も第一回目のスポンサーになったということもあり参加してきました。 f:id:cimadai:20161204013802p:plain

以下は参加した発表の感想です。

OSSWindows で動いてこそ楽しい Go言語への誘い

mattn さん

資料) https://mattn.github.io/builderscon2016/#0

  • Windowsに対する愛(?)とgoへの愛とVimへの愛に溢れた非常に面白い発表でした。

  • goに対するコントリビューションの実績もスゴイですが、発表後にあった 「家庭を持つエンジニアが時間を捻出するためには?」という質問に対する mattnさんの回答で「夜中頑張るしか無い」という回答がシビレました。

  • 最近自分もそうなんじゃないかと感じてたので是非見習いたい点です。

  • あと突貫でVim上で動画再生するプラグイン書いちゃうとか変態(賛辞です)。

動け!Golang 〜圧倒的IoTツール開発へようこそ〜

kazuph さん

資料) https://speakerdeck.com/kazuph/dong-ke-golang-ya-dao-de-iotturukai-fa-heyoukoso

  • 実際にakerunを作るのに工場にIoTを導入にしていろいろと改善した話。
  • 工場でハードウェアを生産するときの辛みとか工夫を惜しみなく聞けた発表でした。
  • akerun使ってみたい。

Automatic Smile Camera を作った話 - 親バカハックノススメ

yosuke-furukawa さん

資料) https://speakerdeck.com/yosuke_furukawa/automatic-smile-camera-at-builderscon

  • 最近お子さまが生まれたそうで、IoTハックで子供の笑顔を残していく、という話。
  • Google Cloud Vision APIの無料枠で収める工夫も参考になりました。
  • 次の展望のBaby speech recognitionも楽しみ!

  • 「Hack for your babies」を「Hack your babies」に空目して電脳Baby感あるなーなどと勘違い。

人工知能によってプログラムを有機化する

三宅陽一郎さん

資料1) http://www.slideshare.net/youichiromiyake/builderscon-2016-69784983

資料2) http://www.slideshare.net/youichiromiyake/builderscon-2016-69785059

  • とても1時間の内容ではないレベルの発表で、情報量半端なかった。
  • それにしてもめちゃくちゃ濃い内容で、AIの歴史、さまざまなアプローチ、適用方法など 網羅的かつ体系的に説明していてとてもわかり易かったです。
  • 資料をよく読み込みたいNo1発表。

Highly available and scalable Kubernetes on AWS

mumoshuさん kube-awsのメンテナー

資料) http://qiita.com/mumoshu/items/922a36dec039e8d230f9

  • kuberunetesの良いところと、kube-awsでさらに得られる便利さを解説してくれた発表。
  • 後のssig33の発表と併せて聞くと味わい深い。
  • minikube入れてみようと思いました。

そろそろプログラマーFPGAを触ってみよう!

kazunori_279さん

資料) http://qiita.com/kazunori279/items/a9e97a4463cab7dda8b9

  • FPGAの情勢から向き不向き、高位合成、実際のデモまであって個人的に興奮度No1の発表でした。
  • FPGAめっちゃ面白いし、ラズパイとか触って楽しい人だったら絶対にはまりそう。
  • PYNQ買って遊びたいな。

Docker swarm mode などで作る PaaS モドキとその悲しみ

ssig33さん: 小池陸さん

  • Docker swarm modeでいろいろやったりハマったりしたお話。
  • mumoshuさんのkuberunetesの話と併せて聞いて、Docker swarm mode確かに簡単だけどどうなのか? という気持ちになった発表でした。
  • kuberunetesはkuberunetesでいろいろ設定めんどくさそうな印象なので、docker swarmレベルの 簡単さでkuberunetesくらい安定したものがあるといいなぁ。

世の中の困り事はだいたいGoのコード自動生成で解決する

makopy さん

  • Goを使う時の心構えとか、コード自動生成の便利さと自作のgo-sqllaというライブラリの紹介。
  • カヤックはゲームサーバーでgoを使っているということでカッコイイなぁと思いました。

Bluetooth キーボードの作りかた

cho45さん

資料) https://lowreal.net/2016/12/03/1

  • Bluetoothキーボードの作り方というタイトルから、まさかこんなに深い、ガチな感じだとは 思わずとてもいい意味で裏切られて楽しい発表でした。
  • とはいえ回路の削り出しの機械10万くらいと聞いて自分は既製品のキーボードでいいかな、と思ってしまうのでした。

次回のbuildersconはすでに日程が決まっているそうです

次回も絶対に参加したい!と思いました。 来年の夏は熱いですね!

dockerでhyperledger/fabricをセットアップ & Chaincode実行まで。

hyperledger/fabricを使ってchaincodeで遊ぶ

最近良く耳にするhyperledgerを手元の環境(docker)で試したくて セットアップをしたのですがややハマったので記録に残します。 このエントリが誰かの役に少しでも立てば幸いです。

docker-composeのセットアップ

dockerの元イメージとしては以下を利用しました。

https://hub.docker.com/r/yeasy/hyperledger-peer/

最終的なdocker-compose.ymlは以下にあります。

github.com

上記のdocker-compose.ymlとcommon.ymlを配置したディレクトリで

docker-compose up -d

として起動します。

起動はこれだけです。カンタンですね!

chaincodeの登録

次にchaincodeを登録するのですが、 登録するchaincodeは以下のリポジトリのサンプルをお借りしました。

github.com

ただし上記のままだとインターフェースが合わないと怒られるので、 最新のインターフェースに併せて以下のように変更しています。

github.com

これを実際に登録します。

curl -X POST --header "Content-Type: application/json" --header "Accept: application/json" -d "{
  \"jsonrpc\": \"2.0\",
  \"method\": \"deploy\",
  \"params\": {
    \"type\": 1,
    \"chaincodeID\": {
      \"path\": \"https://github.com/cimadai/chaincode_example/example_01\"
    },
    \"ctorMsg\": {
      \"function\": \"init\",
      \"args\": []
    }
  },
  \"id\": 1
}" "192.168.2.230:7050/chaincode"

するとログに以下のようなエラーが出てしまいました。

10:06:13.998 [dockercontroller] deployImage -> ERRO 030 Error building images: Error: image hyperledger/fabric-ccenv:x86_64- not found
vp0_1  | 10:06:13.998 [dockercontroller] deployImage -> ERRO 031 Image Output:
vp0_1  | ********************
vp0_1  | Step 1 : FROM hyperledger/fabric-ccenv:x86_64-
vp0_1  | Pulling repository docker.io/hyperledger/fabric-ccenv

どうやらfabric-ccenvというイメージが無くて起動できないみたいなので 用意してあげる必要がありそうです。

fabric-ccenvのビルド

dockerを動かしている環境で、fabric-ccenvをビルドします。

$ git clone https://github.com/hyperledger/fabric.git
$ cd fabric/
$ go get "github.com/hyperledger/fabric/core/chaincode/shim"
$ sudo make peer-image

少しまつとできました。

$ sudo docker images
REPOSITORY                     TAG                             IMAGE ID            CREATED             SIZE
hyperledger/fabric-peer        latest                          357747f2a570        45 minutes ago      1.446 GB
hyperledger/fabric-peer        x86_64-0.7.0-snapshot-0e69b6d   357747f2a570        45 minutes ago      1.446 GB
hyperledger/fabric-javaenv     latest                          6a826a63c1ad        45 minutes ago      791 MB
hyperledger/fabric-javaenv     x86_64-0.7.0-snapshot-0e69b6d   6a826a63c1ad        45 minutes ago      791 MB
hyperledger/fabric-ccenv       latest                          e8913f28fbda        47 minutes ago      1.415 GB
hyperledger/fabric-ccenv       x86_64-0.7.0-snapshot-0e69b6d   e8913f28fbda        47 minutes ago      1.415 GB
hyperledger/fabric-src         latest                          b7e7607659fc        47 minutes ago      1.418 GB
hyperledger/fabric-src         x86_64-0.7.0-snapshot-0e69b6d   b7e7607659fc        47 minutes ago      1.418 GB

この状態でもういちどやってみたのですが、同じエラーで怒られてしまい上手く行きません。

FROM hyperledger/fabric-ccenv:x86_64-

エラーのこの部分に注目して、fabricのソースコード見てみると

FROM hyperledger/fabric-ccenv:$(ARCH)-$(PROJECT_VERSION)

という部分がありました。

どうやらこの PROJECT_VERSION が取得できてないっぽいのですが、 docker-compose.ymlに PROJECT_VERSION つけたりもしたけどうまく行かなかったので ワークアラウンドとして、dockerイメージにPROJECT_VERSIONなしのtagをつけたら上手く行きました。 ※この対応、スマートなやり方があれば教えてください。

以下のようにタグを付けました。

docker tag hyperledger/fabric-ccenv:latest hyperledger/fabric-ccenv:x86_64-

こんな感じになります。

$ sudo docker images
REPOSITORY                     TAG                             IMAGE ID            CREATED             SIZE
hyperledger/fabric-peer        latest                          357747f2a570        49 minutes ago      1.446 GB
hyperledger/fabric-peer        x86_64-0.7.0-snapshot-0e69b6d   357747f2a570        49 minutes ago      1.446 GB
hyperledger/fabric-javaenv     latest                          6a826a63c1ad        49 minutes ago      791 MB
hyperledger/fabric-javaenv     x86_64-0.7.0-snapshot-0e69b6d   6a826a63c1ad        49 minutes ago      791 MB
hyperledger/fabric-ccenv       latest                          e8913f28fbda        50 minutes ago      1.415 GB
hyperledger/fabric-ccenv       x86_64-                         e8913f28fbda        50 minutes ago      1.415 GB
hyperledger/fabric-ccenv       x86_64-0.7.0-snapshot-0e69b6d   e8913f28fbda        50 minutes ago      1.415 GB
hyperledger/fabric-src         latest                          b7e7607659fc        50 minutes ago      1.418 GB
hyperledger/fabric-src         x86_64-0.7.0-snapshot-0e69b6d   b7e7607659fc        50 minutes ago      1.418 GB

これで大丈夫なはずです。

codechainの実行

再度deployをしてみる。

curl -X POST --header "Content-Type: application/json" --header "Accept: application/json" -d "{
  \"jsonrpc\": \"2.0\",
  \"method\": \"deploy\",
  \"params\": {
    \"type\": 1,
    \"chaincodeID\": {
      \"path\": \"https://github.com/cimadai/chaincode_example/example_01\"
    },
    \"ctorMsg\": {
      \"function\": \"init\",
      \"args\": []
    }
  },
  \"id\": 1
}" "192.168.2.230:7050/chaincode"

こんどはちゃんと成功しました。

{
  "jsonrpc": "2.0",
  "result": {
    "status": "OK",
    "message": "da35e239025eb78d7b0af31964639ac05f3869f0ad798ef7e89432f47ce63e56e31d761dc225d982f9eea3daba12a1b04a78e817ec81e389defbf126081a76e1"
  },
  "id": 1
}

続いてinvokeしてみます。

curl -X POST --header "Content-Type: application/json" --header "Accept: application/json" -d "{
  \"jsonrpc\": \"2.0\",
  \"method\": \"invoke\",
  \"params\": {
    \"type\": 1,
    \"chaincodeID\": {
      \"name\": \"da35e239025eb78d7b0af31964639ac05f3869f0ad798ef7e89432f47ce63e56e31d761dc225d982f9eea3daba12a1b04a78e817ec81e389defbf126081a76e1\"
    },
    \"ctorMsg\": {
      \"function\": \"invoke\",
      \"args\": [\"test\", \"123\"]
    }
  },
  \"id\": 2
}" "192.168.2.230:7050/chaincode"

実行も良さそうです。

{
  "jsonrpc": "2.0",
  "result": {
    "status": "OK",
    "message": "4ccb6e02-4763-4c42-81f9-b17143b5fc5e"
  },
  "id": 2
}

最後にqueryを発行して結果を取得してみます。

curl -X POST --header "Content-Type: application/json" --header "Accept: application/json" -d "{
  \"jsonrpc\": \"2.0\",
  \"method\": \"query\",
  \"params\": {
    \"type\": 1,
    \"chaincodeID\": {
      \"name\": \"da35e239025eb78d7b0af31964639ac05f3869f0ad798ef7e89432f47ce63e56e31d761dc225d982f9eea3daba12a1b04a78e817ec81e389defbf126081a76e1\"
    },
    \"ctorMsg\": {
      \"function\": \"query\",
      \"args\": [\"test\"]
    }
  },
  \"id\": 3
}" "192.168.2.230:7050/chaincode"

結果もバッチリ帰ってきました。

{
    "jsonrpc": "2.0",
    "result": {
        "status": "OK",
        "message": "123"
    },
    "id":3
}

これでhyperledgerで遊べますね。

まとめ

hyperledgerはコードベースがどんどん更新されていくので動いたり動かなかったりが ハマりポイントなのかなーと思いました。

実際にhyperledgerを触ってみると、手元環境 + PBFTということもあってEthereumを 触っていたときよりも圧倒的にサクサク感あって快適なblockchain環境です。

  • 秋の夜長にBlockchain -

おわり。

LINE DEVELOPER DAY 2016に行ってきた

LINE DEVELOPER DAY 2016とは

当イベントでは、弊社エンジニアチームの様々な経験や国内外での技術的なチャレンジ、 最新の製品について発表させていただきます。 各セッションでは、セキュリティ関連やBOTなどLINEが現在どのような課題を持ちどのように 解決しようとしているのかも共有できればと考えております。 cf: http://linedevday.linecorp.com/jp/2016/

資料は以下から見れます

http://www.slideshare.net/linecorp/presentations

私が聞いたセッションは以下。

  • A-1 Opening & Introduction
  • A-2 KeyNote New world by the LINE BOT
  • A-3 LINEが乗り越えてきた困難な問題
  • A-4 LINE Login - LINE Platform
  • A-5 Security x LINE Platform
  • B-4 Gravty "A scalable graph database to traverse large-scale relationship fast"
  • A-7 LINE LIVEを支えるアーキテクチャ
  • B-8 New stream processing platform with Apache Flink
  • A-9 LINE Shop powered by Armeria
  • A-10 LINEのエンジニアが働く環境と文化

以下まとめ

A-1 Opening & Introduction

全体的な紹介と方向性の提示。 - LINEの目指すSmart Portal - Messaging Platform - Line - Life Infra Platform - Line pay, Line card, Line pointなど - Content Platform - Line LIVE(日本)、Line TV(タイ) - 今後の注力分野 - AR/MR - Line cameraとの連携 - Data Processing & Mechine Learning - Data Lakeに集約されるLineの全情報を利用。 - スパム探知や攻撃検知など多様な解析を行う。

A-2 KeyNote New world by the LINE BOT

新サービスの紹介 - LINE Notify (当日リリースの新機能) - ChatOptに使う感じの開発者向けツール。 - IFTTTみたい、と思ったらIFTTTとも連携してた。 - かなり柔軟に利用できる。 - Line Messaging APIの最新情報 - 当日正式リリース。 - 新機能 - グループに入れられるようになった。 - 新しいメッセージタイプに対応。(カルーセル、YES/NO、複数ボタン) - 利用者から発信されたメッセージに対するリプライは無料に。 - リッチメニューで利用者がbotを使う時に迷わない導線を提示可能。

A-3 LINEが乗り越えてきた困難な問題

胃の痛くなるような障害を振り返って原因と一次対策と恒久対策について紹介。 - Lineのメッセージと音声通話が止まった。 - 原因は着せ替えデータの更新通知が意図せず大量に発行された事で、それに付随する認証リクエストがバースト。 - モノリシック的な作りになっていたサービスが災いしていろいろ連鎖的に死んだ。 - 2000件未満と2000件以上の時で処理が違っていて、2000件以上になった時に不具合があった。

  • 最終的な対応

    • 2000件以上の場合の処理もちゃんと分散処理する。
    • 異常を検知して止めるサーキットブレイカーを実装する。
    • 本来影響されるべきでない機能を分離。
    • など
  • 教訓

    • 各機能の問題が複合して発生した障害。
    • マイクロサービスを進めて、各サービス側にて自衛的処理をする。
    • 非同期RPCによってブロッキングしないようにする。

A-4 LINE Login - LINE Platform

LINE Loginについて紹介。

  • Lineのユーザー情報を利用したログイン機能
  • Auto Loginが便利。
  • 今後の展開
    • 他の機能との連携をより強化していく。

A-5 Security x LINE Platform

セキュリティについて。個人的にはここが一番おもしろかった。

  • LEGY(Line Event GatewaY)のEncryption

    • pinned RSA keysでMITM攻撃を防ぐ。
    • no X.509 certificates
    • 0-RTT handshake
    • ECDH-Key exchange
  • Messaging E2EE (End-To-End Encryption)

    • グループチャットでのLetter Sealing
  • VoIP E2EE

    • SRTPを使った通信で音声を暗号化。
  • データの完全削除

    • メッセージを消した時に完全消去するようにしている。
  • アンチスパム、ゲーム不正対策

    • GameHakerやGameGuardianでの値ハック
    • SpeedHack
      • サーバーサイドで時間を集計するなどで対策は可能。
      • しかしプレイ時間等、ユーザーの操作技術によって有り得そうなギリギリは難しい。
    • MITM Attack
      • SSL pinningが有効。
      • さらにSSLでやり取りするデータも自分で暗号化しておく。
    • 耐タンパー性について
      • Unity C#のdllはilspy等でかなり元に戻る。
      • il2cppオプションを使うと結構わかりにくい。
    • Server側の対策
      • 出来る限り自動化を進めている。
      • 誤検知(False Positive)には特に厳しい。
        • 正しいユーザーがBANされてしまうと悲しみは深い。

B-4 Gravty "A scalable graph database to traverse large-scale relationship fast"

LINEが開発しているグラフデータベースの紹介。今回聞いた中でこれだけ英語だった。同通レシーバーつけたり外したり。

  • FacebookのSocial GraphやGoogleのPageLankで使われているようなあれ。
  • Lineのタイムラインは7億件のデータがある。
  • これを上手く扱うために、HBaseをストレージとして、Tall Narrow Table Modelで実装されている。
  • Tall Narrowだと、HBaseはRowでスプリット可能で、並行スキャンもできるのでいい。
  • ただしインデックスをサポートしていないので、Phoenixで補完。
  • 非同期にインデックスプロセッシングをするためにKafkaを使っている。

A-7 LINE LIVEを支えるアーキテクチャ

LineLIVEの紹介。

  • 他のサービス同様にマイクロコンポーネントの組み合わせでできている。
  • HLSを使ってやっているのでCDNを使いやすい。
  • 動画ファイルをアップロードしておいて、リアルタイム風再生も可能。
  • CPUでやっていた配信処理をGPUに変えて効率化するなど進めている。
  • チャット機能はWebSocketで実現。
    • チャットサーバーは110台以上!
  • 複数のチャットサーバーをまたいでチャットを実現していて、redisのpub-subを使っている。
  • サーバーサイドはAkka actorを使ってる。
  • ライブ中のメッセージはredisに入ってるが、終了したらMySQLアーカイブする。
  • 後にアーカイブされた動画がバズったら、コメントをjsonにまとめてHLS的な感じでCDNに置いて負荷対策。
  • 人は連打できるところがあれば連打するので、連打が気持ちいいUIにする。

B-8 New stream processing platform with Apache Flink

データラボの紹介とLiveLIVEのデータの扱いについての説明。

  • Line LIVEの裏側の処理はいまはver2。
  • ver1時点の課題として見えていたものは以下の3点。
    1. リアルタイム集計
    2. 番組毎のユニークユーザー数
    3. 耐障害性
  • ver1は上記課題に対して、以下のように解決していた。
    1. リアルタイム集計
      • Norikraによるリアルタイム集計
    2. 番組毎のユニークユーザー数
      • 120GBのメモリを搭載して力技で解決
    3. 耐障害性
      • 待機系を用意して冗長化(待機系はもっとメモリが多い)
  • ver1での障害

    • アイドルグループの生放送でメモリ120GB使い切った。
    • OOMは出ていないものの、ほぼ動いていない状態。
    • この時は待機系に切り替えて乗り切った。
  • その後個人からの配信も可能にする計画があった。

    • もうNorikraの構成じゃ耐えられない。。
  • ver2を開発。

  • ver2はver1の課題に加え、スケーラビリティが求められていて、以下のように解決した。

    1. リアルタイム集計
      • Flink
    2. 番組毎のユニークユーザー数
      • HyperLogLog
    3. 耐障害性
      • Flink
    4. スケーラビリティ
      • Flink
  • 結論

    • Apache Flinkを使うことで多くの問題が解決できた。
    • ユニークユーザー数の集計はHyperLogLogを使うことで大量のメモリが不要になった。
  • FlinkのProsCons

    • Pros:
    • Cons:
      • ジョブを変えたりクラスタを変えた時に内部状態を引き継げない。
      • 稼働中のジョブの並列度を後からあげることができない。
        • 覚えている状態をすべて消さないとだめ。
        • 今後改修予定。
      • ジョブ間の独立性が弱い。タスクマネージャの中のスレッドで実行しているので、 一つ間違ったジョブがあって死ぬとプロセス毎死ぬ。 →Hadoopのyarnを使うと対応可能。

A-9 LINE Shop powered by Armeria

LINEが開発している非同期RPCのOSSの紹介。

  • 着せ替えショップとかスタンプショップとかで使われている。
  • 非同期RPC、API Client/Serverライブラリ
  • Java 8, Netty 4.1, HTTP/2, Thrift
  • 毎秒数十万のリクエストをさばける。
  • 各種メトリクスの取得も可能。

  • 注意する点

    • HTTP/2にすることで、ロードバランサーTCPコネクション単位でバランシングしていると偏りがち。
    • →クライアントサイドロードバランシングで解決する。

A-10 LINEのエンジニアが働く環境と文化

LINEの文化的なところ。 - 働きやすそう(こなみ)

まとめ

お食事券2000円分に驚き、会場の豪華さに驚き、カフェスペースの無料開放に驚き、 LINE LIVEでのリアルタイム配信、LINE BOTをつかった情報配信、Beaconを使った体験の提供、 さらにBeaconの無料配布、などなどLINEの札束感というか勢いに圧倒されまくりでした。

LINEの印象が大分変わった一日でした。

おまけ

ホールAの豪華さ f:id:cimadai:20160929100219j:plain 無料でもらえるおかし f:id:cimadai:20160929125102j:plain

Dcokerことはじめ

会社で開催した勉強会でDockerの超初歩について発表しました。

dockerがdcokerになってるのはご愛嬌(ゝω・)テヘペロ

ITエンジニアのための機械学習理論入門8.1ベイズ推定

8.1の発表を担当したのでスライドを上げておきます。

ITエンジニアのための機械学習理論入門 7

第7章 EMアルゴリズム: 最尤推定法による教師なし学習

この章では2つのことを学ぶ。

  1. 特定の文字だけからなる手書き文字サンプル群から、それらを代表する「代表文字」を生成する方法。
    • ベルヌーイ分布と呼ばれる確率分布を用い、最尤推定法を実施する。
  2. 複数の文字が混在した手書き文字サンプル群を分類する方法。

7.1 ベルヌーイ分布を用いた最尤推定

  • 代表文字 = 複数の顔写真を合成した「平均的な顔」のイメージ
  • 複数の画像データを合成する方法
    • 平均を取る。
      1. 画像に含まれるピクセルを横一列に並べる
      2. ピクセルの色(黒or白)を1or0として表したベクトルにする。
      3. n番目の画像に対応するベクトルを${\bf x}_n$とする。
      4. その第i成分$[{\bf x}_n]_i$を見ると、i番目のピクセルの色がわかる。
      5. 画像データがN個あるとして、これらの平均をとったベクトル$\mu$を用意する。 $$ \mu = \dfrac{1}{N} \sum_{n=1}^{N} {\bf x}_n \tag{7.1} $$
      6. $\mu$の各成分は0から1の範囲の実数値となる。これがピクセルの色の濃淡。
    • ただし、これは直感的すぎるので、以下で理論的な根拠を見る。

「画像生成器」による最尤推定法の適用

  • 最尤推定法を適用するには、何らかの方法で「トレーニングセットが得られる確率」を計算する必要がある。
  • そこで、ランダムに手書き文字を生成する「画像生成器」を用意する。
  • (7.1)の$\mu$の各成分の値を「対応するピクセルが黒になる確率」と考える。
  • これにより、「確率$\mu_i$でi番目のピクセルを黒にする」というルールで画像を生成できる。
  • いま、トレーニングセットにN個のデータがあり、画像生成器からもN個のデータを生成するとする。
  • これらのデータ群が全て同一になる確率を考える。
  • この確率が最大になるような画像生成器を見つけ出せば、トレーニングセットを代表する画像になっているものと期待できる。

ベクトル$\mu$で表される画像生成器からトレーニングセットのデータと同じものが生成される確率を計算する。

  • トレーニングセットに含まれる特定の画像データを$\bf x$とする。
  • $\bf x$は、第$i$成分の値${\bf x}_i$が$i$番目のピクセルの色(1=黒、0=白)を表すベクトル。
  • ピクセル数は全部で$D$個あるとする。
  • この中で、特に$i$番目のピクセルに注目した場合、そのピクセルの色が得られる確率$p_i$は以下になる。

$$ x_i = 1の場合 : p_i = \mu_i \tag{7.2} $$

$$ x_i = 0の場合 : p_i = 1 - \mu_i \tag{7.3} $$

  • これらをまとめて記述すると以下になる。

$$ p_i = \mu_i^{x_i}(1 - \mu_i)^{1-x_i} \tag{7.4} $$

したがって、ある特定の画像のすべてのピクセルが同じ色になる確率は次の式で表せる。 ($D$個すべてのピクセルが同じなので掛け算する)

$$ p(x) = \prod_{i=1}^{D}p_i = \prod_{i=1}^{D}{\mu_i^{x_i}(1 - \mu_i)^{1-x_i}} \tag{7.5} $$

さらに、トレーニングセットに含まれるすべての画像のすべてのピクセルが一致する確率は次のようになる。 ($N$個の画像の$D$個のピクセルすべてが同じなので二重の掛け算する)

$$ \begin{eqnarray} P &=& \prod_{n=1}^{N}p({\bf x}_n) \nonumber \\ &=& \prod_{n=1}^{N}\prod_{i=1}^{D}[p_n]_i \nonumber \\ &=& \prod_{n=1}^{N}\prod_{i=1}^{D}{\mu_i^{[x_n]_i}(1 - \mu_i)^{1-[x_n]_i}} \tag{7.6} \end{eqnarray} $$

  • これが、このモデルにおける尤度関数となる。
  • これを最大にする$\mu$を計算すると、(7.1)が得られる。
  • つまり、(7.1)は尤度関数(7.6)を最大化する画像生成器といえる。

(7.6)を最大化する$\mu$を求めてみる。

  • まず計算を簡単にするため対数尤度関数$lnP$を計算し、これを最大化する$\mu$を求める。

$$ \begin{eqnarray} P &=& \prod_{n=1}^{N}\prod_{i=1}^{D}{\mu_i^{[x_n]_i}(1 - \mu_i)^{1-[x_n]_i}} \nonumber \\ lnP &=& \sum_{n=1}^N\sum_{i=1}^D{ln\mu_i^{[x_n]_i}(1 - \mu_i)^{1-[x_n]_i}} \nonumber \\ lnP &=& \sum_{n=1}^N\sum_{i=1}^D{ln\mu_i^{[x_n]_i} + ln(1 - \mu_i)^{1-[x_n]_i}} \nonumber \\ lnP &=& \sum_{n=1}^N\sum_{i=1}^D\{[{\bf x}_n]_i ln\mu_i + (1 - [{\bf x}_n]_i)ln(1-\mu_i)\} \tag{7.7} \end{eqnarray} $$

  • これを$\mu_i$で偏微分すると以下のようになる。

$$ \begin{eqnarray} \dfrac{\partial(lnP)}{\partial \mu_i} &=& \sum_{n=1}^N\left(\dfrac{[{\bf x}_n]_i}{\mu_i} - \dfrac{1 - [{\bf x}_n]_i}{1-\mu_i}\right) \tag{7.8} \end{eqnarray} $$

$$ \begin{eqnarray} x &=& lnA \nonumber \\ x' &=& \dfrac{A'}{A} \end{eqnarray} $$

  • これが0になるという条件から、以下のように変形できる。

$$ \begin{eqnarray} \sum_{n=1}^N\left(\dfrac{[{\bf x}_n]_i}{\mu_i} - \dfrac{1 - [{\bf x}_n]_i}{1-\mu_i}\right) &=& 0 \nonumber \\ \sum_{n=1}^N\dfrac{[{\bf x}_n]_i}{\mu_i} - \sum_{n=1}^N\dfrac{1 - [{\bf x}_n]_i}{1-\mu_i} &=& 0 \nonumber \\ (1-\mu_i)\sum_{n=1}^N[{\bf x}_n]_i - \mu_i\sum_{n=1}^N(1 - [{\bf x}_n]_i) &=& 0 \nonumber \\ \sum_{n=1}^N[{\bf x}_n]_i - \mu_i\sum_{n=1}^N[{\bf x}_n]_i - \mu_i\sum_{n=1}^N + \mu_i\sum_{n=1}^N[{\bf x}_n]_i &=& 0 \nonumber \\ \sum_{n=1}^N[{\bf x}_n]_i - \mu_iN &=& 0 \nonumber \\ \mu_iN &=& \sum_{n=1}^N[{\bf x}_n]_i \nonumber \\ \mu_i &=& \dfrac{1}{N}\sum_{n=1}^N[{\bf x}_n]_i \nonumber \tag{7.9} \end{eqnarray} $$

  • これは、(7.1)を成分表記したものである。

$$ \mu = \dfrac{1}{N}\sum_{n=1}{N}{\bf x}_n \tag{7.1} $$

  • (7.4)や(5.6)はベルヌーイ分布と呼ばれる確率分布。
  • 上記のモデルは「ベルヌーイ分布を用いた最尤推定法」と呼ぶ。

7.2 混合分布を用いた最尤推定

  • 7.1ではある一種類の数字からなる、手書き文字画像のトレーニングセットを利用した。
  • ここでは、全部で$K$種類の数字を含む、手書き文字画像のトレーニングセットを利用する。
  • 全部で$K$種類なので、画像生成器は $\{\mu_k\}_{k=1}^{K}$ とする。
  • この時、特定の画像生成器$\mu_k$から画像$\bf x$が得られる確率は(7.5)同様に以下式になる。

$$ p_{\mu_k}({\bf x}) = \prod_{i=1}^{D}{[\mu_k]_i^{x_i}(1 - [\mu_k]_i)^{1-x_i}} \tag{7.10} $$

  • どの画像生成器を使うか、ということも確率に入れて考える。
  • どれか1つの画像生成器をランダムに選択し、新しい画像を生成する。
  • ここで、$k$番目の画像生成器を選ぶ確率を$\pi_k$とする。
  • $\{\pi_k\}_{k=1}^K$は、以下の条件を満たす。

$$ \sum_{k=1}^K\pi_k = 1 \tag{7.11} $$

このような操作で、特定の画像$\bf x$が得られる確率は以下になる。

  1. ある画像生成器が選択される確率( = $\pi_k$)
  2. 特定の画像生成器からある画像$\bf x$が得られる確率( = $p_{\mu_k}({\bf x})$)
  3. 数字は全部で$K$種類あるので、すべての場合を足し合わせる。

$$ p({\bf x}) = \sum_{k=1}^K\pi_kp_{\mu_k}({\bf x}) \tag{7.12} $$

  • さらに、トレーニングセット内のデータ数が$N$個とすると、トレーニングセットのデータ群と一致する確率は以下になる。

$$ P = \prod_{n=1}^{N}p({\bf x}_n) = \prod_{n=1}^{N}\sum_{k=1}^K\pi_kp_{\mu_k}({\bf x}_n) \tag{7.13} $$

  • (7.13)が、このモデルの尤度関数になる。
  • このように、複数のベルヌーイ分布を混ぜたものを混合ベルヌーイ分布と呼ぶ。

EMアルゴリズムの手続き

  • ここで、尤度関数(7.13)を最大化するパラメーターを決定するのだが、簡単にはできない。
  • 積の計算$\Pi$と和の計算$Σ$が混在しているので、対数尤度関数にしてもうまく進められない。
  • このような場合に、EMアルゴリズムを適用することができる。
  • EMアルゴリズムは、k平均法に類似した方になる。

手順

  1. $K$個の画像生成器 $\{\mu_k\}_{k=1}^{K}$ を用意する。
  2. それぞれの画像生成器を選択する確率($\{\pi_k\}_{k=1}^K$)は条件(7.11)を満たす。
  3. どれが一つの画像生成器を選択して、画像${\bf x}_n$が得られる確率は、 $$ p({\bf x}_n) = \sum_{k=1}^K\pi_kp_{\mu_k}({\bf x}_n) \tag{7.14} $$
  4. 特定の$k$番目の画像生成器から、画像${\bf x}_n$が得られる可能性について、その割合を以下で取り出す。 $$ \gamma_{nk} = \dfrac{\pi_kp_{\mu_k}({\bf x}_n)}{\sum_{k'=1}^K\pi_{k'}p_{\mu_{k'}}({\bf x}_n)} \tag{7.15} $$
  5. これはk平均法において、トレーニングセットに含まれるデータ${\bf x}_n$が所属する代表点を決める操作に相当する。
  6. k平均法の場合は最も距離が近い代表点に所属するという条件で設定した。
  7. 上記の$\gamma_{nk}$はこれに相当する。
  8. 今の場合、${\bf x}_n$はどれか一つの画像生成器に所属するのではなく、それぞれの画像生成器に対して、$\gamma_{nk}$の割合で所属する。
  9. 各画像生成器に所属する割合が決まったら、この割合に基づいて、新たに画像生成器$\{\mu_k\}_{k=1}^{K}$を作りなおす。 $$ \mu_k = \dfrac{\sum_{n=1}^N\gamma_{nk}{\bf x}_n}{\sum_{n=1}^N\gamma_{nk}} \tag{7.16} $$
  10. これはk平均法において、各クラスターの重心として新たな代表点をとる操作にあたる。
  11. 特に、(7.16)は(6.3)と同じ形の計算式になっていることがわかる。
  12. あるいは、(7.16)は1種類の文字についての代表文字を作成する(7.1)を$K$種類の文字の混合版に拡張したと考えることができる。
  13. さらに、それぞれの画像生成器を選択する確率 $\{\pi_k\}_{k=1}^K$も作りなおす。 $$ \pi_k = \dfrac{\sum_{n=1}^N\gamma_{nk}}{N} \tag{7.17} $$
  14. (7.17)は、それぞれの画像生成器を使用する割合を「それぞれの画像生成器に所属する画像の量」に比例するようにしている。

以上でEMアルゴリズムの手続きは完成で、(7.16)・(7.17)で決まった値を用いて再度(7.15)を計算、 そしてまた(7.16)・(7.17)というように繰り返す。

繰り返すごとに(7.13)の尤度関数の値が大きくなり、最終的に極大値に達する。

とりあえずここまで。