Rest Term

Blog

JavaScriptで機械学習の実装 3 AROW

今回はオンライン機械学習アルゴリズムとして知られている AROW (Adaptive Regularization of Weight Vectors) を試してみました。内容的には以下のエントリーの続きになりますが、今回からタイトル文言を少し変えようと思います。TypeScript入門という段階はそろそろ脱したかなと思うのと、TypeScriptよりも直接JavaScriptで書く量の方が増えてきたためです。

前回のエントリー内で、次はブースティング系アルゴリズムを実装してみたいと書いたのですが、オンライン機械学習 (機械学習プロフェッショナルシリーズ)を読んでいたらこの分野への興味が強くなってしまったので、ちょっと寄り道。

AROW (Adaptive Regularization of Weight Vectors)

AROWのアルゴリズムは以下のようになっています(元論文から引用)。

arow_algorithm
AROWは Confidence Weighted Learning (CW) というアルゴリズムを改善したものです。CWでは"現在の訓練データを常に正しく分類する"という条件で最適化するので、訓練データにノイズの入っていると上手く学習できないという欠点がありますが、AROWではこれまでの分布(パラメータ)に近い分布を探しつつ、各特徴の確信度(Confidence)を更新毎に上げるという条件(正則化項として加える)も併せて考慮して最適化するため、ノイズが多いデータでもCWと比較して分類精度が高くなるという特徴があります。パラメータも一つだけというのも嬉しいです。実装上は計算量の削減の為に共分散行列の非対角項を0にして対角項だけ計算することが多いそうですが、これでも精度はほとんど落ちないようです。

Node.js Stream APIで学習データの読み込み

今回からはWebブラウザではなくNode.js上で実行します。理由はデータセットの効率的な読み込み処理の為にStream APIを使いたかった為です。LIBSVMフォーマットのデータファイルをStream APIで読み込むには例えば以下のように書くことができます。

これで一つのサンプルが取り出される度にコールバック関数が呼ばれます。これを応用して入力をファイルではなくHTTPのストリームを指定して、例えばJSON形式で一つのサンプルを渡してもらうインタフェースにすると、WebAPIで学習データをストリームで受け取り続けることができるのでオンライン学習と相性が良さそうです。ただ、上記のように単一のファイルを読み込む場合はオーバーヘッドが大きいので、通常の非同期読み込みの手順を使う方が良いと思います。

検証

AROW本体やデータ読み込み用モジュール、動作確認用のテストコード一式はこれまで通りGitHubに置いておきます。今回からはTypeScriptとJavaScriptの両方のコードを上げておきます。

今回はLIBSVM Data: Classificationの news20.binary データセットで分類精度や収束速度などを確認してみます。

事前にデータをシャッフルして15000例の訓練データと4996例のテストデータに分けています。今回作ったLIBSVMデータファイル読み込みモジュールは、非同期によるストリーム読み込みだけでなく同期読み込みもできるようにしてあります。動作確認には後者を使った方が楽です。

パラメータは適当に決めたのですが、分類精度(正答率)は約97.2%となりました。注目すべきは収束速度で、データを一巡しただけでほぼ収束しているように見えます。速いですね。

線形SVMとも比較してみます。まだJavaScriptでSVMの実装はしていないので、ここではscikit-learnの実装(sklearn.svm.LinearSVC)を使いました。

* 実行結果

パラメータはグリッドサーチで決定、分類精度は約96.5%で、AROWと同等あるいは少し悪いくらい。妥当な結果と言えるでしょうか。

おわりに

今回はオンライン機械学習アルゴリズムのひとつであるAROWを試してみました。最近はディープラーニング系のニューラルネットワークのプログラムを趣味でも書くことが増えてきたのですけど、それらに比べてオンライン機械学習のアルゴリズムは実装が楽で収束も速いので嬉しいです。それに加えてデータを蓄積しておかなくて良いので、近年のWebサービスで扱われるような断続的なストリームデータとも相性が良いと思います。この後はAROWより後発のアルゴリズムであるSCWなども試しつつ、Node.js上でのより効率的な処理の書き方なども併せて調べていくつもりです。

参考

オンライン機械学習 (機械学習プロフェッショナルシリーズ)
AROW (Adaptive Regularization of Weight Vectors) (論文PDF)
SCW (Soft Confidence Weighted Learning) (論文PDF)
CW, AROW, and SCW
[機械学習] AROWのコードを書いてみた
Node.js v6.3.1 Documentation
Node.js の Stream API で「データの流れ」を扱う方法

 

Tags: , , ,

Linuxカーネル Docker関連 cgroupsのメモ

Linux_Containers_logo_150

前回はLinuxの namespace(名前空間) についてCプログラムやツールを使っていろいろと確認できましたので、今回は cgroups についても調べます。

namespaceは生成したプロセスに対してリソース体系を割り当てる(隔離空間を作る)のに対して、cgroupsは指定したプロセスのグループに対してリソース制限をかけます。似ているようで全然別の機能ですね。

環境

* CentOS 7.2 (kernel-3.10.0-327.4.5.el7.x86_64)
* Ubuntu 14.04 (3.13.0-77-generic)
* Docker 1.9.1

cgroups

Control Groups provide a mechanism for aggregating/partitioning sets of
tasks, and all their future children, into hierarchical groups with
specialized behaviour.

cgroupsは control groups の略でタスクをグループ化したり、そのグループ内のタスクに対して様々なリソース制御を行うための仕組みです。namespaceではホスト名やPID空間などのカーネル/OSが扱うリソースを制御(隔離)しますが、cgroupsで制御するのはCPUやメモリといった物理的なリソースです。

/sys/fs/cgroup 以下に仮想的なファイルシステムとしてのインタフェースが提供されています。今回の作業環境も上述の通りCentOSとUbuntuの両方で確認していますが、CentOSの場合はsystemd経由でcgroupsを操作するのに対して、Ubuntuの場合は直接 /sys/fs/cgroup を書き換えています。Ubuntu 15.04からはUpstartからsystemdに置き換わるらしいですが、ディレクトリ以下の構造は基本的には変わりません。

実際に /sys/fs/cgroup の中身を見てみるとcpuやmemoryといったわかりやすい名前のサブディレクトリが見えます。

仮想的なファイルシステムと前述した通り、ここでファイル/ディレクトリ操作をすることで様々なリソース制御を行います。これらはサブシステムと呼ばれています。

サブシステム 概要
blkio ブロックデバイスの入出力
cpu CPUリソースの割り当て・制限
cpuacct タスクが消費するCPU時間をレポート
cpuset グループへのCPU,メモリノードの割り当て
devices デバイスへのアクセス制限
freezer グループに属するプロセスの一時停止/再開
hugetlb cgroupからのhugetlbの使用
memory タスクが消費するメモリリソースのレポートと制限
perf_event cgroup単位でのperfツールの使用

cgroupsによってタスクをグループ化しますが、そのグループは各々ヒエラルキー(hierarchy:階層)構造を持ち、上記のサブシステムによるリソース制限を受けます。そのヒエラルキー構造は仮想ファイルシステム上で表現されます。

ここではいくつかのサブシステムをピックアップしていろいろ調べてみます。

cpuset/cpu/memoryサブシステム

まずは挙動がわかりやすいcpuset/cpu/memoryサブシステムについて。dockerコンテナを作成する際の以下のオプションに関係してきます。オプション名はDockerのバージョンによって変わることがあるので注意してください(その際はdeprecatedメッセージが出力されます)。

--cpuset-cpus 使用するCPUコアを指定 (cpusetサブシステム)
--cpu-shares CPU時間の割り当てを相対比率で指定、デフォルト 1024 (cpuサブシステム)
-m | --memory 使用メモリの上限 (memoryサブシステム)

上記dockerオプションはcpuset,cpu,memoryサブシステムの以下のファイルを操作してリソース制限を行います。ここではUbuntu上で動作確認していますが、/sys/fs/cgourps/cpuset,cpu,memoryディレクトリに以下のファイルがあります。

  • cpuset.cpus
  • cpu.shares
  • memory.limit_in_bytes

まずはcpusetサブシステムの動作確認のために適当なdockerコンテナを作って起動し、CPU1のみを利用するように --cpuset-cpus オプションで指定してddコマンドを実行し続けます。

dockerではコンテナを起動すると各サブシステムに docker/{コンテナID} 名のディレクトリを作成します。上記のコンテナで指定した --cpuset-cpus の値を確認してみます。

次はcpuサブシステムが関係する --cpu-shares の挙動を確認してみます。2つめのコンテナを以下のオプションで起動します。--cpu-shares 2048 と指定していますが、これは同じCPUコアで複数のコンテナのプロセスが実行される場合に、どちらのコンテナを優先的に実行するかを相対的な重みで指定するオプションです。デフォルト値が1024なので、ここではその2倍の値を指定しています。その結果、2つめのコンテナは2倍の優先度でCPU時間が割り当てられることになります。

2つのコンテナでのddコマンドのCPU使用率が綺麗に1対2に分かれています。確認のため cpu.shares ファイルの中身も見てみます。

次はmemoryサブシステムが関係する --memory オプションの挙動を確認します。コンテナから使用できるメモリの上限値を指定するオプションで、数値の後ろにmを付ければMB(メガバイト)指定ができます。

--memory オプションを指定しない場合(デフォルト)だと、memory.limit_in_bytesファイルには 18446744073709551615 (bytes)と書かれていました。スワップ領域の容量も同じサイズに制限されるため、128mと指定した場合はプロセスは物理メモリ128MB + スワップ128MBまで使用できます。そのサイズを超えるとOOM Killerが発動してコンテナ内のプロセスが強制終了させられます。

また、以下のファイルの中身を見るとコンテナ内でのメモリ使用状況を確認することができます。

ここまで紹介した各ファイル内の値を直接書き換えることでもコンテナ内のリソースを任意に制限をすることができます。まぁdockerを使っているなら素直にdockerのコマンドから指定した方が良いですね。

devicesサブシステム

次にdevicesサブシステムについていろいろ確認してみます。devicesはグループに所属するプロセスがアクセス可能なデバイスを制限するサブシステムです。例えばコンテナ内から直接ネットワークやディスクのデバイスにアクセスさせないように設定できます。

cgroupから始まっているファイルは他のサブシステムと共通のファイル、devicesから始まっているファイルはdevicesサブシステム専用のファイルとなっています。それ以外の tasks、notify_on_release、release_agent の3つはどうやら歴史的な理由でプレフィックスが付いていないようです。これらに頼るのなら焼かれる覚悟をしておけって書いてありますけど、怖すぎるんですが。

前述のdevicesプレフィックスが付いた3つのファイルを使って各種アクセス制御を行います。

devices.allow アクセスを許可するデバイスを追加
devices.deny アクセスを禁止するデバイスを追加
devices.list 現在のアクセス許可されているデバイスの状態を表示

Linux Kernel Updates Vol 2014.08の内容に沿ってこちらの環境でも動作確認してみます。まずはdevices.listの中身を見て現在のデバイスの状態を確認しておきます。

dockerコンテナの内部ではどうなっているでしょう。

なにやらいろいろと制限されているようです。以下に読み方を整理します。

  • 先頭のアルファベット a: 全てのデバイス、b: ブロックデバイス、c: キャラクタデバイス
  • n:m (n:mはメジャー番号:マイナー番号 or ワイルドカード)は/devのノード番号
  • 末尾のアルファベット3つ r: 読み込み可能、w: 書き込み可能、m: 新規作成可能

となっています。つまり a *:* rwm は全てのデバイスへの操作が可能であることを示しています。そして上記の内容を読み解くと、まずは全てのキャラクタデバイスとブロックデバイスへの読み書きを禁止した後に、個々のキャラクタデバイスに必要に応じて権限を与えていることが読み取れます。/devのノード番号だけみてもわかりにくいですが、例えば 1:3 は /dev/null 、1:8 は /dev/random を差しています。このように各デバイスへの操作を制限することによってdockerコンテナ内のセキュリティを担保しているのですが、ここでは試しにその制限を解除してみます。

また、devices.allowに明示的に/dev/kmsgへの読み書きを許可することもできます。

devicesサブシステムの動作確認ができました。他にもサブシステムはありますが動作確認はこれくらいにして、カーネルのソースコードも少しだけ見ておきたいと思います。

カーネルの実装

task_struct 構造体(Linuxプロセスを表現するデータ構造)のメンバに css_set というcgroupを管理するための構造体があります。

また、list_head 構造体はわかりやすいのでカーネルを読むときはこの辺りから慣れていくとと良いかもしれません。Doubly linked listの実装でカーネル内のあちこちに登場してきますので。css_set の中身は以下のようになっており、全てのタスクはこの css_set に対する参照カウント(のポインタ)を保持しています。

css_setcgroup_subsys_stateという構造体の集合を保持していることがわかります。cssというのはcgroup_subysys_stateを略なんでしょう。tasks は前述の task_struct 構造体メンバの cg_list と(連結リストとして)繋がっており、これを辿ればcgroupsに属する全てタスクにアクセスできるようになっています。

cgroup_subsys_state 単体だけを見てもよくわかりませんが、css_set からコメント文も読みつつ cgroups 構造体まで辿ってくるとなんとなく構造が見えてきます。ここまでに前述した list_head がたくさん登場していますが、これを使ってcgroupsのヒエラルキー構造を表現していることが読めます。ちなみにRCUというのは排他制御機構 Read-Copy-Update の実装ですが、cgroupsでも多くの場所で活用されているようです。詳細はWikipediaが詳しいです。

ここまではcgroups自体の実装に関する部分で、サブシステムの実装はどうなっているのかわかりません。ここでは例としてdevicesサブシステムを少し覗いてみます。

現在のタスク(プロセス)が所属するcgroupを取得(task_devcgroup関数)、前述したデバイスタイプと番号(c 5:1 とか)を指定してパーミッションのチェックを行っています(may_access関数)。

cgroup.h/cにはサブシステム自体の実装は含まれておらず、cpuサブシステムならkernel/sched/ 、memoryサブシステムならmm/以下にあり、タスクスケジューラやメモリ管理などカーネルの主機能の中にサブシステムの実装も含まれている形です。

サブシステムの実装詳細については今後も興味のあるものから少しずつ読み進めていくつもりです。今回は前回調べたnamespaceに続いて、Dockerコンテナを作成するために必要な技術要素であるcgroupsについて概要を整理しました。

参考

おまけ: Cscopeについて

効率良くLinuxカーネルのコードリーディングするためにCscopeというツールを利用しています。

Cscope is a developer's tool for browsing source code. It has an impeccable Unix pedigree, having been originally developed at Bell Labs back in the days of the PDP-11. Cscope was part of the official AT&T Unix distribution for many years, and has been used to manage projects involving 20 million lines of code!

使い方は以下のエントリーを参考にさせてもらいました。Linuxカーネルのソースコードは規模が大きいので、cscopeのデータベースは必ず転置インデックス付きで作成しておきましょう。また、Emacs使いであればhelmインタフェースからも利用できます。

 

Tags: ,

TypeScript入門 – 機械学習の実装 2 Logistic Regression

TypeScript_Logo
前回はTypeScript入門ということで、TypeScriptで Denoising Autoencoders という種類のニューラルネットワークを作ったのと、AngularJSやAngular Materialの使い方を少し学ぶことができました。

このDenoising Autoencoderを構成要素として何層も積み重ねるとStacked Denoising Autoencoderとなり、Deep Learning(深層学習)とも呼ばれます。Denoising Autoencoderを実装してあれば、残りは出力層での教師有り学習で用いるロジスティック回帰やソフトマックス関数など小さな部品を作るだけです。実はそれとは別に、前回の記事の後に小規模なConvolutional Neural Network(CNN)もTypeScriptで書いてみたのですが、MNISTの学習すら一向に終わらないので少し実装を見直しているところです。漢なら手書きasm.jsに挑むべきって言われたんですけど、なかなかロマンを感じますね。

とりあえず今回は追加部品として作ったロジスティック回帰(Logistic Regression)を動かして正しく学習できているか見てみます。

ソースコードは今回もGitHubにアップしていますので興味があれば。

ロジスティック回帰なので分類タスクとなります。まずは簡単な二値分類から。

* 出力結果

データ作成時にランダム要素が入っているので実行の度に結果は多少変わりますが、予測結果を見るにきちんと分類できていますし、クロスエントロピー損失も徐々に減っているのを確認できました。次は多クラス分類、iris(アヤメ)とdigits(手書き数字)データセットを使います。どちらもscikit-learn(sklearn.datasets)に実装されているので、TypeScriptから読み込めるオブジェクトに変換しておきました。

Large53digits_data

* 実行結果

irisデータセットは綺麗なデータなので良い分類結果が出ていますが、データ数が少ないので動作確認結果として妥当かどうか心配です。次にdigitsデータセットも同様に学習、テストを行ってみます。こちらはわかりやすい手書き数字認識のタスクとなります。

* 実行結果

約92%の正答率です。学習率のスケジューリングを丁寧にすればもっと精度は上がると思います。このくらいのデータ規模になると、学習には100イテレーションでも数秒かかりました。MNISTやCIFAR-10だとどれくらいの時間がかかるのでしょうか。

また、ユーティリティ系モジュールとして scikit-learn でいうところの LabelBinalier や metrics モジュールの機能を一部TypeScriptでも作りました。機械学習のアルゴリズムだけでなく、データ整形で必須となる機能が揃っているのも scikit-learn の便利なところ。ただ、重要な機能ではあるんですが移植作業をしていても全然楽しくないのが辛いです。

TypeScript 所感

このエントリーの主題はTypeScriptの勉強なので、この言語を使っていての個人的な所感を。

型のある安心感

機械学習で中心となる行列演算周りのコードを書いていると、メソッドの引数や戻り値がベクトルなのか行列なのかをきちんと検査してくれるのは安心感があります。Typed Arrayを使うプログラムだとありがたみがより大きいかもしれません。また、型推論のおかげで型指定をある程度省略できるのも助かります。

今回 interface は活用できていませんが、もし他の機械学習用のモジュールを追加する場合は使ってみようと思います。scikit-learnでも学習は fit、予測は predict のようにメソッド名が統一されているので真似するのが良さそうです。

コンパイルはそんなに遅くない

昔はTypeScriptのコンパイル(JavaScriptへのトランスパイル)がとても遅かったらしいですが、現在の僕の開発環境だと遅いという感覚はありません。また、Visual Studio Codeのエディタは軽快だし、インテリセンスの反応も良くサクサクと実装を進めることができます。
vscode_cap1

言語仕様面での課題

課題と書いてしまうと語弊がありますが、例えば機械学習だと行列の要素積などのelement-wiseな計算を頻繁に行うのですが、演算子をオーバーロードできる言語だと綺麗に(数式に近い感じで)実装しやすいです。現在のTypeScriptの仕様だと演算子のオーバーロードはできないので、メソッドチェーン方式でそれっぽい感じで書くしかないのでしょうか。醜いですけど、。Pythonでライブラリを使わずに一から実装しました系のエントリーはたくさん見かけますけど、思いっきりNumPy使ってるじゃないですか。羨ましい。

同じような感想を持っている方もいるようです。

アプリケーション開発者側ではオーバーロードは避けるべきなケースが多いかもしれませんが、アプリケーション開発者が使うライブラリの作成者側にとっては必要な機能だったりすることが多いのではないでしょうか。

おわりに

機械学習のアルゴリズムを実際に書いてみると、例えば損失の値がNaNになったり、ソフトマックス関数の計算中にexpの結果がオーバーフローしてInfに落ちたり、コンピュータで数値計算する際のハマり所にたくさん出会えるのでなかなか楽しいです。これは書籍やWebサイト上で数式を眺めているだけだと経験できないこと。数式と実装のギャップを埋めるための数値計算上のテクニックをいろいろ学ぶことが出来ます。

TypeScriptでの実装はPythonやC++で実装するより何倍も面倒なんですけど、結果としてたくさんコードが書けるので良い暇つぶしになるかなと思いました。あと、2011年にJavaScriptで決定木というアルゴリズムを書いたのですが、

これを発展させて勾配ブースティング(Gradient Boosting Decision Tree)を今度はTypeScriptで書いてみたいなと思っています。いきなり書くのは難しそうなので、Boostingに必要な部品から作ったらいいかなと考えています。

体系的な知識だけが増えて技術力が伴わない頭でっかちなエンジニアにはなりたくないので、ひたすら手を動かしてコードを書く習慣を付けたいと思います。さすがに2,3年ほど技術的なことから離れていたのでリハビリはもうしばらく続きそうです。

 

Tags: , , ,