備忘録 blog

Docker/Machine Learning/Linux

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

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

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をロードするので時間がかかっている。そういうこともありいささか筋悪な手法だとは思うのだが、誰か詳しい方の解説を乞いたい。

外挿性の問題

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