備忘録 blog

Docker/Machine Learning/Linux

Rustの覚書

全体的に

postd.cc

https://japaric.github.io/discovery/

インストール

rustを手元の環境に導入する方法として、rustc(rustコンパイラ)を直に入れるほかにrustupと呼ばれるツールチェーン管理用のソフトウェアを介してインストールする方法がある。これはnightlyビルドやstableビルドなどが選べたり、バージョン管理が可能だったりするので、nightlyビルドでなければ通らないライブラリを使うときに個人的には便利であった。

blog.rust-lang.org

Cross Compile

github.com

によれば、

It's hard to find a cross C toolchain (and cross compiled C libraries) between different OSes (except perhaps from Linux to Windows). A much simpler and less error prone way is to build natively for these targets because they are tier 1 platforms. You may not have direct access to all these OSes but that's not a problem because you can use CI services like Travis CI and AppVeyor. Check my rust-everywhere project for instructions on how to do that.

ということだそうだ。

所有権・参照

qiita.com

qiita.com

Box, Rc, Cell, RefCell

agtn.hatenablog.com

qiita.com

ヒープ領域を確保するためのBox、C++のスマートポインタに相当するようなRcなど。

Optional / Result型

qiita.com

Logger

qiita.com

コマンドライン引数

qiita.com

文字列処理

qiita.com

HaskellにおけるHTMLのテンプレートエンジンを調査する

HaskellはWebフレームワークだけでもYesod, Snap, Happstackといった重厚長大型のフレームワークに加え、軽量なもの/API向けのものでもSpock, Scotty, Servantなど乱立しているが、Template Engineとて例外ではない。Blaze-html, shakespeare, mustache, stache, ede, lucid, heistなどこれもまた様々存在し、特にSpockやScottyといったフレームワークではテンプレートエンジン選択の自由度が高いので、どれを使おうかと思い、調べたのでここにメモを残す。

Template Engine

stackoverflow.com

stackoverflowでも何を使えばよいか、議論となっている。

stache

stache: Mustache templates for Haskell

Mustacheという汎用テンプレートエンジンのhaskell実装の1つ。 ただMustache自体の仕様として記法が簡潔でよいのだが、if文の分岐がBooleanのTrue/Falseしかできないなど、少し凝ったことをしづらい面がある。 ただAesonのインスタンスをそのまま渡せるのは心強く、Viewに送りたいデータを新しいデータ型として定義し、deriveJSONを呼んでおけば、あとはテンプレートにそのインスタンスを渡すだけでよいというのは手軽である。

記法は以下のような形。

Hi, {{name}}! You have:
{{#things}}
  * {{.}}
{{/things}}

こうすると、things配列の要素が.のところに順々に出力される。

Mustache

mustache: A mustache template parser library.

これも上と同じMustacheの実装。Data.AesonのValueを渡せるのはよいが、Maybe型の値のデータをみたとき、Nothingの時の値は空白が入っていることを期待したらnullが入っているというのはstacheと異なる点。そういった点で、stacheの時と同じmustacheファイルに対して同じ挙動を示すというわけではなかった。下の記事によれば、

Mustache templates in Haskell - Tutorials

it again makes simple things complex using Aeson's Value (good) and at the same time introducing its own Value type (with conflicting names of constructors and naturally not so numerous instances).

とのことで、Mustacheを使うぐらいであればstacheを使ったほうがよさそう。

ede

ede: Templating language with similar syntax and features to Liquid or Jinja2.

Mustache風味のHTMLベースのテンプレートエンジンだが、こちらのほうが表現力が高い。

qiita.com

こちらもData.AesonのValue型をObject型に変換し、それをテンプレートに代入してrenderしてくれる機構が備わっているので、テンプレートに与えたいデータをデータ型で用意しておけばよいのは変わらない。

--Unwrap a Value to an Object safely.
fromValue :: Value -> Maybe Object

記法はこんな感じ。

<div class="checkbox">
  {% for chara in characters %}
    <label class="checkbox-inline">
      <input name="chara" value="{{chara.value.name}}" type="checkbox">
      {{chara.value.name}}
    </label>
  {% endfor %}
</div>

if文では、比較演算子if-elif-elseと複数の条件で分岐させることもできるので、View側で凝ったことをすることも容易。

lucid

lucid: Clear to write, read and edit DSL for HTML

一方でこちらはhaskellの記法でHTMLを記述するDSL

ただSpockで使う場合、テンプレートを書き換えるごとにコンパイルしなおさなければならない。ede, stacheの場合は別ファイルで呼び出すので、コンパイルをし直す必要はないが、記法が誤っている場合は実行時エラーとなる。そう考えるとCompile時にValidateしてくれるlucidや、特にshakespeareではリンクのバリデーションも施してくれるので、これらのほうが型安全であると考えられる。

HTMLテンプレート?Lucidを使ってみた

Haskellの文法そのままなので、例えばリストの要素を列挙したい場合では

div_ [class_ "container"] do $
  h1_ [] "List"
  ul_ [class_ "list-group"] $
    mapM_ (li_ []) ["a", "b"]

などと書くことで、["a"], ["b"]の中身がliタグに囲まれて列挙される。

blaze-html

blaze-html: A blazingly fast HTML combinator library for Haskell

広く使われるHTMLライブラリではあるのですが、先述のLucidはこちらの改良版と言うか、blaze-htmlの問題点を解決したライブラリである。チュートリアルより、

import Text.Blaze.Html5 as H
import Text.Blaze.Html5.Attributes as A

userInfo :: Maybe User -> Html
userInfo u = H.div ! A.id "user-info" $ case u of
    Nothing ->
        a ! href "/login" $ "Please login."
    Just user -> do
        "Logged in as "
        toHtml $ getUserName user
        ". Your points: "
        toHtml $ getPoints user

記法はこんな感じで、これの何が問題かというと、下記のブログによればいくつかあるのだが、div, id, head, mapといった要素はbaseとconflictしているのでqualifiedして呼ばなければならないし、AttributeとElementの名前がコンフリクトするものがあるので、そうするとAやらHやらを頭に付けなければならない。結果としてコードが見にくくなってしまうのだ。それよりかは、Lucidのようにすべてsuffixに_をつけるほうが統一性があり、見栄えも良さそうだ。

Lucid: templating DSL for HTML

shakespeare

shakespeare: A toolkit for making compile-time interpolated templates

yesodで使われているテンプレートエンジン。hamletはこれにdeprecateされた。拡張子としては.hamletがHTML、.juliusがjs, .luciusCSSに対応している。 記法はこんな感じ。

<div .container>
  <h1> All Posts

  <div .jumbotron>
    <ul>
      $forall Entity id post <- allPosts
        <h4>
          <li>
            <a href=@{PostDetailsR id}>#{blogPostTitle post}

タグは閉じないで、インデントで親子関係を示す。HTMLに近い記法ができる一方でコンパイル時に変数が確実に埋め込まれる。たとえば@{}では型付きのURLが埋め込まれるため、それが有効なURLかどうかコンパイル時にバリデートされる。これがリンク切れを起こさない秘訣だ。変数の代入は#{}を使う。このとき、hamletではXSS attackを防ぐために適切にエスケープしてくれる。

制御構文は$から始まる行に記述し、if, elseif, forall, caseなど場合分けや、Maybe型への対応なども充実している。hamletはQuasiquotesでコード内部に埋め込むこともできるし、外部ファイルに記述することもできる。外部ファイルの場合はTemplateHaskellで参照され、コンパイル時に組み込まれる。

上記はyesodの場合で、これはscreencastから持ってきた例だが、yesodと無関係に使うこともできる。

www.yesodweb.com

sites.google.com

heist

heist: An Haskell template system supporting both HTML5 and XML.

snapというフレームワークで採用されているテンプレートエンジン。これは実際には試していないので、ウェブ上の例を見てみよう。

<bind tag="special">special-id</bind>
<div id="${special}">very special</div>

<bind tag="message">some text</bind>
<p><message/></p>

snapframework.com

heistの特徴となる主なタグはbindapplyで、bindはその名の通り変数を束縛し、 applyは<apply template="nav"/>のようにすると部分テンプレートを代入することができるらしい。Haskellからどう呼び出すかというと、公式サイトの例をみると

factSplice :: Splice Snap
factSplice = do
    input <- getParamNode
    let text = T.unpack $ X.nodeText input
        n = read text :: Int
    return [X.TextNode $ T.pack $ show $ product [1..n]]

というコードに対して、bindSplice "fact" factSplice templateStateとすると、<fact>タグにfactSpliceがbindされるので、<fact>5</fact>120になるとのことだ。

シェルコマンドでよく使う引数を書き留める

TL;DR

シェルコマンドの中で、しばしば自分が使っていて便利な引数、毎回検索するも忘れてしまって前回打ったコマンドをback-i-searchで探そうとするも見つからなくて困るものなどを記す。

diff

diff -y -B -b -i -W 200

  • -y : 結果を2行に表示
  • -W 200: 各行の幅を表示
  • -B : 空行を無視
  • -b : 空白スペースを無視
  • -i : 大文字・小文字の違いを無視

sort

sort -n -r -k 3,3

  • -n : 数値順に評価
  • -r : 逆順にする
  • -k : 並び替えるフィールドを指定する。上記の例だと3フィールド目。

tr

標準入力から標準出力へ、文字を変換・削除するなどして流し込むコマンド。

tr -d '\n'

  • -d : 引数の文字を削除する

less

less -N -S -s +F

  • -N : 行番号を付ける
  • -S : 長い行を折り返さず、1行で表示
  • -s : 空行を1行にまとめる
  • +F : 更新をリアルタイムに見る

qiita.com

qiita.com

time

/usr/bin/time -p -o FILE [cmd]

  • /usr/bin/time : シェル組み込みのtimeではなく、GNU timeを使う
  • -p : 互換性のある出力にする
  • -o FILE : 出力のファイル名を指定する

du

フォルダの容量を表示する

du -h --max-depth=2 [dir]

  • -h : サイズの接尾辞が付く
  • --max-depth : 再帰的に探索するディレクトリの深さの上限を指定する

tar

tar czvf file.tar.gz file tar xzvf file.tar.gz

  • c : 圧縮する
  • x : 解凍する
  • z : gzipにする
  • v : ファイル一覧を出力する
  • f : fの引数のアーカイブファイルを使う
  • j : bzip2にする

curl

curl -H 'Content-Type:application/json' -d "{\"session\": \"test\"}" -u user:pass [url]

  • -H : header
  • -d : パラメータをつける
  • -u : BasicAuthのユーザー情報

qiita.com

ps

プロセスを見る。

ps aux

  • a : 自分以外のプロセスも見る
  • u : ユーザー名が出る
  • x : 端末を持たないプロセスも見る

convert

ImageMagickのコマンド。identifyもそうだが、パッケージ名とコマンド名が一致しないので注意。

タイル状に切り抜く時のコマンド。

convert -crop 64x64 +repage in.png out.png

こうすると、64x64でタイル状に左上から切り取ってくれる。ただし、割り切れずに端数がでる場合は端数サイズのファイルが出力されてしまうし、出力ファイル名はout-1.png,out-2.pngのようになるので、sortするときに文字順で並べるとout-1.png,out-10.png,out-11.png...のように並んで困ることになる場合もある。

Imagemagick - code snippets

xargs

xargs -P 22 -n 2 -t -I {} [cmd]

  • -P : 指定した個数のプロセスを立ち上げて並列実行
  • -n : cmdに渡す引数の個数
  • -t : コマンドの実行内容を表示
  • -I : [cmd]の部分に引数で渡した{}を使うと、その部分にxargsで渡される引数が入る。
    • -i : -iも-Iと同様で、引数を省略すると自動で{}が採用されるが、deplecated.

orebibou.com

d.hatena.ne.jp

ただしxargsからパイプでファイルに書き込みたいと思って、> output.txtなどと書いても、プロセスを並列化していると複数のプロセスから同時に書き込まれるので、1つのプロセスから書き込まれる内容が別々の行にばらけてしまうことがある。そういった諸々の問題が面倒なので、下のコマンドを使うこともある。

parallel

xargsより高性能に並列処理を行ってくれるコマンド。このGNU parallelは、apt-getなどで別途導入する。

bicycle1885.hatenablog.com

GNU Parallel

シェルスクリプト(bash)

bash -x hoge.sh

  • -x : 実行するコマンドも同時に出力する
  • -c : 引数の文字列をシェルコマンドとして実行する

shellscript.sunone.me

モニタリングツール

htop

プロセスをモニタリングするtopコマンドの拡張で、見やすい。 htop 上でキーをたたくと、表示様式を変更することができる。F1キーをたたけばヘルプが見られる。

  • u : ユーザーを限定してプロセスを表示
  • H : ユーザープロセスのスレッドを隠すか表示させるかをトグルする
  • l : lsofで開いているファイルを読む
  • s : straceで読んだシステムコールを読む

iostat

ioの状況を表示するコマンド

bmon

ネットワークアダプタの状況を表示するコマンド

その他

80 Linux Monitoring Tools for SysAdmins - Server Density Blog

入出力制御

qiita.com

Haskellで参考にしたもの

Web Framework

Scotty / Spock

Rubyで言う所のSinatraのような軽量フレームワークhaskell版。ScottyよりSpockの方が、waiに準拠している上に機能も充実していて良いらしい。

Spockの紹介記事は以下。

qiita.com

ScottyをHerokuで動かしてみたサンプルアプリは

github.com

Yesod

Yesodのすごいところは、shakespeareのおかげでビューにまで型付きの制約があるところで、このおかげでリンク切れとか起きないらしい。(もしリンクが切れるようなことがあれば、それはコンパイルが通らない。)

またketerと言うデプロイマネージャーは、ローカルでコンパイルして、実行に必要なファイルをすべてまとめてサーバーにscpし、ダウンタイム0でデプロイしてくれるようにできるらしい。とても便利。

公式のScreecastsには、わずか40分程度!で簡単なブログを組み立てる動画が見られる。

HTMLエスケープやXSSを防ぐ機構についてはライブラリが面倒を見てくれるため、我々はそういったことに気をつかうことなく安心してWebアプリを書くことができる。

www.yesodweb.com

Other

Web/Comparison of Happstack, Snap and Yesod - HaskellWiki

テンプレートエンジンについては記事を書きました。

sharply.hatenablog.com

DB操作をする

YesodのDatabase.Persistentが、sqlite, mongoDB, postgresSQLなどのDBとのアダプターとなって、マイグレーションを自動でやってくれるとか便利。

www.yesodweb.com

qiita.com

rf0444.hatenablog.jp

http://blog.fujimuradaisuke.com/post/26887032662/haskell-de-json-web-api
blog.fujimuradaisuke.com

Libraries

d.hatena.ne.jp

http://haskell-distributed.github.io/

実際にこれを使って分散処理を書くのがやりやすいかというと、やはりもう少しダイナミックに型を扱える言語の方が書きやすいのかもしれない。

チュートリアル

1. Getting Started

  • IntervalMap

区間を保持する構造のhaskellにおける実装。

github.com

Haskell IntervalMap

  • Aeson

Template Haskellを用いて、dataの定義からderiveJSONするのがスマートそうな気がします。

qiita.com

Data.AesonでJSONを扱う | saito's memo

文字列型

bicycle1885.hatenablog.com

qiita.com

Blaze.ByteString.Builder

Other

例えばm [a] => [m a]にする関数が何かを知りたいと思った時、Hoogle で検索するのが便利そうです。初心者なのでコンパイルが通らない時に型の帳尻合わせをしたくなるので、そういった時に重宝しました。

Hoogle

github.com

React-Nativeで便利なUIライブラリ

tl;dr

React-NativeでiOSAndroidのネイティブアプリを作る際、自分が使った中で便利だったUIに関するライブラリをいくつか紹介する。

探し方や導入方法など

github.com

ここにReact-nativeに関連する様々な情報がまとまっており、その中にライブラリも多数収録されている。

依存がjavascriptだけのものはnpm install --saveすればよい。一方でコンパイル時に組み込まなければならないものは、GithubのReadmeなどに説明があると思うが、最近ではrnpmを使う、あるいはreact-native link <packagename>といったコマンドでプロジェクトに自動で組み込んでくれるようになっているので、手動で各ファイルに追記するよりミスを防げるので安全であると言えよう。

react-native-gifted-chat(旧 react-native-gifted-messenger)

github.com

いわゆるL○NE風のチャット画面を誰でも容易に作ることのできるライブラリ。ここにあるようにデザインはもうすでに整っているので、あとはチャットに表示させるメッセージをどこかから引っ張ってくるだけでよい。

React-native-gifted-messenger時代のものだが、簡単なチャットアプリの作り方は以下のQiitaの記事が参考になる。

qiita.com

react-native-vector-icons

github.com

FontAwesomeをはじめとしてFoundation, MaterialIcons, Octionsなど様々なベクターアイコンがバンドルされたライブラリ。

例えばアイコンを表示させたかったら、以下のようなタグを挿入すればよい。

<Icon name="rocket" size={30} color="#900" />

クオリティの高いアイコンが多数揃っているので、必要なアイコンはきっと見つかるはずだ。

react-native-action-button

github.com

Twitterの公式アプリの右下にある感じのボタンと、それを押すと複数のボタン選択肢が開いてくれるような、触っていて楽しいライブラリ。

これとreact-native-vector-iconsを組み合わせると、ボタンのアイコンを自作せずともきれいなベクターアイコンを使えるので便利。

react-native-sglistview

github.com

React NativeにはListViewという実装があり、何らかのデータソースから得られたデータをリスト形式で表示してくれるものであるが、その実装ではスクロールするにつれてメモリ使用量が線形で増え、利用可能なメモリを使い潰すと考えられる。その解決策として、SGListViewを用いることを提案している。スクロールするたびに内部のビューをflushしてくれるので、メモリを節約できるとのこと。

記法はListViewで実装していた部分をそのままSGListViewで置き換えればよく、導入も容易である。ただしアルファ版のため、skepticallyに使うようにとNoticeに書いてあるので注意。

react-native-grid-view

github.com

ListViewに対して、1つの列に複数のアイテムを置くことができるという点が優れている。ライブラリ自体の説明は乏しいが、Exampleを参考に改変しながら実装するとよいと思われる。サムネイルから選択させるような画面を作るときに向いているだろう。

react-native-router-flux

github.com

React NativeではNavigatorでのルーティングがデフォルトとなっており、Sceneと呼ばれる一つ一つの画面をスタックにpop/pushしていくことで、階層的なルーティングをサポートしている。

一方でそもそもAndroidiOSの間では画面遷移の制御や、TabBarやNavBarといったネイティブコンポーネントの違いがあり、その違いをうまく吸収してくれるようなルーターを使いたいと思う。

そこでここで取り上げるのが、fluxの考え方を取り入れたreact-native-router-fluxだ。公式のExampleをみてみると、

    return <Router>
      <Scene key="root">
        <Scene key="login" component={Login} title="Login"/>
        <Scene key="register" component={Register} title="Register"/>
        <Scene key="home" component={Home}/>
      </Scene>
    </Router>

Routerを上記のように定義すると、それぞれのコンポーネントではActions.Key(PARAM)によってpropsにPARAMを代入した状態で、Keyで指定したSceneへの遷移を呼び出せるほか、Actions.pop()と書くとその前のSceneに戻ることができる。

こうすることでまずルーティングを直感的に記述でき、それぞれの遷移も(ライブラリのActionsをそのコンポーネントに依存しない形で呼び出すので少し気持ち悪いように見えるかもしれないが)Keyを指定するだけで手軽に書けるので便利である。

またこのままだとナビゲーションバーが上に出るので、それがうっとうしい場合は<Scene key="root" hideNavBar>とすると、ナビゲーションバーを消すことができる。またそれぞれのSceneで、pop可能なとき、画面の左部中央をスワイプすると勝手にpopされてしまう。この挙動が邪魔な場合は、その挙動が発生してほしくないScene上で例えば<Scene key="home" component={Home} panHandlers={null}/>などとして、panHandlersをnullにすることで、スワイプによる画面遷移を防ぐことができる。

参考:

twins-tech.hatenablog.com

PRML 3.4-3.6 メモ

線形回帰モデルの流れ

3章では、 {y=w^{T}x}に対して、 yと決定変数tの間に加えられるガウスノイズの精度パラメータとしてβ、モデルパラメータwの事前確率分布を期待値0の、分散 {\alpha^{-1} I}の等方的ガウス分布としてαという2つのハイパーパラメータを導入している。ここで、ベイズ線形回帰ではwを周辺化していたが、今度はハイパーパラメータについても同様に事前分布を導入して周辺化したいが、完全に解析的に周辺化することは難しい。そのため、wに関して得られた周辺尤度を最大にするようにハイパーパラメータの値を定めるという近似について議論し、αとβの意味づけについて考える。

3.4 ベイズモデル比較

  • モデルパラメータの値を含んだ同時確率から、それを積分して周辺化することで、パラメータに依存しない確率が手に入れられる。

モデルの事後分布 {p(M_i|D) \propto p(M_i) p(D|M_i)}を計算するにあたって、事前分布 {p(M_i)}が全iに対して等しいとすると、 {p(D|M_i)}の項をモデルエビデンス=データから見たモデルの好みが重要である。それぞれのモデルの事後分布が分かると、全体の予測分布は混合分布で与えられる。

{ \displaystyle
p(t|x, D) = \sum p(t|x, Mi, D)p(M_i|D)
}

これは多峰性の分布となるが、近似するためにここから尤もらしいモデルを1つ選択しよう。

{ \displaystyle
p(D|M_i) = \int p(D|w,M_i)p(w|M_i)
}

この時、モデルエビデンスパラメータの事後確率を選ぶ際の正規化係数そのものになっている。

別の解釈を与える

モデルエビデンスに別の解釈を与える。パラメータの事前分布と事後分布が図3.12の時、事前分布の話は1で幅がΔWpriorだと、その高さは1/ΔWpriorとなるから、このことからp(D)を表現できる。この対数をとると、 {\ln{p(D|w_{MAP})}}が尤もらしいパラメータ wMAPによるフィッティング度で、 Δpos/Δpriを含む項が複雑さに対するペナルティであり、事前分布より事後分布が強くフィットするほど、ペナルティが増える。=これにより、過学習を防ぐことが可能となっていると考えられる。

M個のパラメータに対して、同じ比を持つならばM倍のペナルティがかかる。これが、パラメータ数が増えるにつれてペナルティが増えていることを示している。

カルバックライブラーダイバージェンス

期待ベイズ因子を求める際にKL-Divを用いる。式3.73の情報学的な解釈としては、真の分布 {p(D|M_1)}に対して偽の分布 {p(D|M_2)}を用いた時に必要な追加情報量の平均である。ここで、その2つの分布が一致するならば、必要となる情報量は0になるためにカルバックライブラーダイバージェンスも0になるということも直感的にわかる。

  • 変則事前分布は、先の解釈で言うところの正規化係数が定義できないので、適用できない。
  • 適切な極限をとって近似するほかない。

3.5 エビデンス近似

3.3より線形関数モデルでは、モデルパラメータwの事前確率分布を期待値0の、分散 {\alpha^{-1} I}の等方的ガウス分布を考えることとした。ここでβを決定変数に加えられるガウスノイズの精度パラメータとすると(このβは尤度関数に顕に現れる)、この時にwの事後分布は正規分布 { N (w|M_N,S_N)} で表現される。 これの対数尤度をとると、係数にαとβが現れる形になる。背後に仮定したガウス分布のαとβに対して、対数尤度を最大にするような値を求めるのが本節の目的である。

3.5 エビデンス近似 - 詳細

ハイパーパラメーターα、βに対しても事前分布を導入する。パラメータを周辺化して得られる周辺尤度関数を最大化することを、エビデンス近似と呼ぶ。

周辺尤度関数を最大にするようなα、βを選択すればよい。ではその周辺尤度関数を計算してみよう。重みwを周辺化すれば、αとβの式にできる。

演3.17,演3.18をとくと、演3.19は自明に導けて、エビデンス関数の(対数)表式を求められる。

これを最大化するα、βを求めたい。αは(3.92)から導かれる。βも同様に導かれて、(3.95)から導かれる。αとβはそれぞれに関する陰関数であるため、繰り返しによって計算する。

3.5.3 有効パラメータ数-αの意味づけ

基底関数の変換行列Φの固有値λ,αを用いて、

{ \displaystyle
\gamma = \sum(\frac{\lambda}{\lambda + \alpha})
}

で表される。固有値が正だから、 {\frac{\lambda}{\lambda + \alpha}}は0~1の値をとる。1となるものの和=個数がγであるから、1となるものはどういうものだろうか。

パラメータwiが最尤推定値に近いもの。このパラメータはデータに制約されるから、well-determinedパラメータと呼ばれる。このパラメータは、回帰への相関が高いパラメータに対応している。

一方で0に近い場合、 {y=w^{T} \phi(x)}に対して特徴量空間で値が動きにくくなることから、尤度関数の感度は悪くなっている。

思うに、実際には理想的にw_iの値がくっきり最尤推定値に近いものと0に近いもので別れることはなく、 {\frac{\lambda}{\lambda + \alpha}}が0.5になるようなものも得られるだろうが、その時γはパラメーターの寄与相当数(0.5のものが2つあれば、1相当になるとみなす)という形で捉えればよいのではなかろうか。

ハイパーパラメーターαはそもそも事前分布の分散として与えたものであるから、α=0であれば事前分布を導入してないことになるのでα=0の時は最尤推定に一致するし、α!=0の時はMAP推定の結果で最頻値が与えられると考えられる。

3.5.3 有効パラメータ数-βの意味づけ

βは、回帰関数周りでの目標関数の残差分散だが、ここではデータ数がN-γ、つまりwell-determinedでないパラメータの個数ととなっている。これは分散の最尤推定値と不偏推定量の関係で見たように、自由度が関係している。

ベイズ推定では、γ個のパラメータがデータによって決まっていると考えられるため、総パラメータ数Mに対してM-γ個のパラメータは事前分布に従っている。ここから、γ個のパラメータ=自由度が、最尤推定バイアス補正に用いられていると考えるのが相当である。

データ点に関する陰的な和でΦTΦが表現されることが期待できるようなN>>Mの状況では、すべてのパラメータがwell-determinedとなり、γ=Mとなる。この時αとβは容易に書き下せる。αが正則化項、βがデータ依存の誤差項に対応していることは、事前確率分布を期待値0の、分散 {\alpha^{-1} I}の等方的ガウス分布を考え、βを決定変数に加えられるガウスノイズの精度パラメータとしていたことから直感的にわかる。

固定された基底関数の限界

線形モデルの欠点は、以下である。

  • 基底関数を、観測する前に固定していること。

これに対する対処策は以下である。

  • データベクトルは、本質的な次元数は入力空間よりも小さい非線形多様体上に分布していること。
    • 後述
  • 局所的な基底関数を用いれば良い
  • 目標変数がデータ多様体中のほんの少数の方向にしか依存しないこと

パラメータの隠れ変数, 連続への拡張

周辺化することで、パラメータwはいわば隠れ変数となる。この隠れ変数が離散的であるとしたのがEMアルゴリズムによるE,M過程によるαとβの最適化であり、連続的であるとした時に主成分分析を行うのが12章の流れである。

データベクトルは、本質的な次元数は入力空間よりも小さい非線形多様体上に分布していることの直感的な議論としては、下章で示されている例としては手書き数字において、変化するのは垂直方向と水平方向、回転という3自由度しかないので、実効次元は3次元となる。この時、画素が文字位置の非線形関数であり、平行移動と回転のパラメタが潜在変数である。

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

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

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

stackoverflow.com

  • sysdig

Sysdig | Home

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

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

f:id:sharply:20160622151129p:plain

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

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

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

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

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

sourceware.org

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

  • strace

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

blog.livedoor.jp

straceを使うと、このような形で呼ばれたシステムコールと戻り値をみることができる。それをもとにmmapbrkがどれだけメモリ確保したかを累算することができるが、いかんせん、これが内部で呼んでいるシステムコール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を重み行列として

{ \displaystyle
y=W^{T}x
}

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

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

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

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の枠組みで攻撃しようとするならば、攻撃者はそれだけコインを保有する必要があるが、それだけコインを保有するならば攻撃によって失われるコインの価値もまた多くなるはずであり、従って損得で考えるならば攻撃者は攻撃する意味を失うはずである。