Rest Term

Blog

JavaScriptで機械学習の実装 3 AROW

8月 14th, 2016 in tech/study tags: algorithm, javascript, ml, typescript

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

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

AROW (Adaptive Regularization of Weight Vectors)

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

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

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

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

var fs = require('fs');
var readline = require('readline');

var loadLIBSVM = function (filePath, callback) {
    var options = { encoding: 'utf8', highWaterMark: 256 };
    var stream = fs.createReadStream(filePath, options);
    var rl = readline.createInterface(stream, null);

    rl.on('line', function (line) {
        var fields = line.split(/[\s:]/);
        var label = fields[0].charAt(0) == '+' ? +1 : -1;
        var x = [];
        var len = fields.length;
        for (var i = 1; i < len; i += 2) {
            var index = parseInt(fields[i]) - 1;
            var value = parseFloat(fields[i + 1]);
            var element = { index: index, value: value };
            x.push(element);
        }
        callback(x, label);
    });

    rl.on('close', function () {
        console.log('load complete');
    });
};

var fs = require('fs');

var readline = require('readline');

var loadLIBSVM = function (filePath, callback) {

var options = { encoding: 'utf8', highWaterMark: 256 };

var stream = fs.createReadStream(filePath, options);

var rl = readline.createInterface(stream, null);

rl.on('line', function (line) {

var fields = line.split(/[\s:]/);

var label = fields[0].charAt(0) == '+' ? +1 : -1;

var x = [];

var len = fields.length;

for (var i = 1; i < len; i += 2) {

var index = parseInt(fields[i]) - 1;

var value = parseFloat(fields[i + 1]);

var element = { index: index, value: value };

x.push(element);

}

callback(x, label);

});

rl.on('close', function () {

console.log('load complete');

});

};

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

検証

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

imageprocessing-labs/ml/arow/ - GitHub

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

news20.binary
Preprocessing: Each instance has unit length.
# of classes: 2
# of data: 19,996
# of features: 1,355,191

news20.binary

Preprocessing: Each instance has unit length.

# of classes: 2

# of data: 19,996

# of features: 1,355,191

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

var featureSize = 1355191;
var r = 0.1;  // ハイパーパラメータ
var clf = new AROW(featureSize, r);

// 非同期ストリーム読み込みによる学習は以下のように書く
DataLoader.read('news20_train', function(x, label) {
    clf.update(x, label);
});

// 同期読み込みによる学習とテスト
var trainData = new DataLoader('news20_train');
var testData = new DataLoader('news20_test');
console.log('load complete.');
console.log(trainData.size, testData.size);
var maxIter = 5;
for (var i = 0; i < maxIter; i++) {
    trainData.data.forEach(function (e) {
        clf.update(e.x, e.label);
    });
    var error = 0;
    testData.data.forEach(function (e) {
        var predLabel = clf.predict(e.x);
        if (predLabel != e.label) {
            error++;
        }
    });
    console.log('iteration: ' + (i + 1) + ', error rate = ' + (error / testData.size));
}

var featureSize = 1355191;

var r = 0.1; // ハイパーパラメータ

var clf = new AROW(featureSize, r);

// 非同期ストリーム読み込みによる学習は以下のように書く

DataLoader.read('news20_train', function(x, label) {

clf.update(x, label);

});

// 同期読み込みによる学習とテスト

var trainData = new DataLoader('news20_train');

var testData = new DataLoader('news20_test');

console.log('load complete.');

console.log(trainData.size, testData.size);

var maxIter = 5;

for (var i = 0; i < maxIter; i++) {

trainData.data.forEach(function (e) {

clf.update(e.x, e.label);

});

var error = 0;

testData.data.forEach(function (e) {

var predLabel = clf.predict(e.x);

if (predLabel != e.label) {

error++;

}

});

console.log('iteration: ' + (i + 1) + ', error rate = ' + (error / testData.size));

}

load complete.
15000 4996
iteration: 1, error rate = 0.02822257806244996
iteration: 2, error rate = 0.027622097678142513
iteration: 3, error rate = 0.027822257806244997
iteration: 4, error rate = 0.027822257806244997
iteration: 5, error rate = 0.027822257806244997

load complete.

15000 4996

iteration: 1, error rate = 0.02822257806244996

iteration: 2, error rate = 0.027622097678142513

iteration: 3, error rate = 0.027822257806244997

iteration: 4, error rate = 0.027822257806244997

iteration: 5, error rate = 0.027822257806244997

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

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

import numpy as np
from sklearn.datasets import load_svmlight_file
from sklearn.svm import LinearSVC
from sklearn.grid_search import GridSearchCV
from sklearn.metrics import accuracy_score, classification_report

X_train, y_train = load_svmlight_file('news20_train')  ## 学習データ
X_test, y_test = load_svmlight_file('news20_test')  ## テストデータ
estimator = LinearSVC()
param_grid = [{'C':np.logspace(-3, 1, 20),},]
clf = GridSearchCV(estimator, param_grid, cv=5, scoring='accuracy', n_jobs=3)
clf.fit(X_train, y_train)
print(clf.best_estimator_)
pred = clf.predict(X_test)
print('## accuracy: %s' % (accuracy_score(y_test, pred),))
cr = classification_report(y_test, pred)
print(cr)

import numpy as np

from sklearn.datasets import load_svmlight_file

from sklearn.svm import LinearSVC

from sklearn.grid_search import GridSearchCV

from sklearn.metrics import accuracy_score, classification_report

X_train, y_train = load_svmlight_file('news20_train') ## 学習データ

X_test, y_test = load_svmlight_file('news20_test') ## テストデータ

estimator = LinearSVC()

param_grid = [{'C':np.logspace(-3, 1, 20),},]

clf = GridSearchCV(estimator, param_grid, cv=5, scoring='accuracy', n_jobs=3)

clf.fit(X_train, y_train)

print(clf.best_estimator_)

pred = clf.predict(X_test)

print('## accuracy: %s' % (accuracy_score(y_test, pred),))

cr = classification_report(y_test, pred)

print(cr)

* 実行結果

LinearSVC(C=3.7926901907322459, class_weight=None, dual=True,
     fit_intercept=True, intercept_scaling=1, loss='squared_hinge',
     max_iter=1000, multi_class='ovr', penalty='l2', random_state=None,
     tol=0.0001, verbose=0)
## accuracy: 0.964792958592
             precision    recall  f1-score   support

       -1.0       0.97      0.96      0.96      2474
        1.0       0.96      0.97      0.97      2522

avg / total       0.96      0.96      0.96      4996

LinearSVC(C=3.7926901907322459, class_weight=None, dual=True,

fit_intercept=True, intercept_scaling=1, loss='squared_hinge',

max_iter=1000, multi_class='ovr', penalty='l2', random_state=None,

tol=0.0001, verbose=0)

## accuracy: 0.964792958592

precision recall f1-score support

-1.0 0.97 0.96 0.96 2474

1.0 0.96 0.97 0.97 2522

avg / total 0.96 0.96 0.96 4996

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

おわりに

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

imageprocessing-labs/ml/arow/ - GitHub (ソースコード)

参考

オンライン機械学習 (機械学習プロフェッショナルシリーズ)
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: algorithm, javascript, ml, typescript

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

5月 18th, 2016 in tech/study tags: c/c++, unix/linux

Comments →

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

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

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といったわかりやすい名前のサブディレクトリが見えます。

# CentOSの場合
$ ls -l /sys/fs/cgroup
drwxr-xr-x 2 root root  0  2月  6 16:07 blkio/
lrwxrwxrwx 1 root root 11  2月  6 16:07 cpu -> cpu,cpuacct/
drwxr-xr-x 2 root root  0  2月  6 16:07 cpu,cpuacct/
lrwxrwxrwx 1 root root 11  2月  6 16:07 cpuacct -> cpu,cpuacct/
drwxr-xr-x 2 root root  0  2月  6 16:07 cpuset/
drwxr-xr-x 2 root root  0  2月  6 16:07 devices/
drwxr-xr-x 2 root root  0  2月  6 16:07 freezer/
drwxr-xr-x 2 root root  0  2月  6 16:07 hugetlb/
drwxr-xr-x 2 root root  0  2月  6 16:07 memory/
drwxr-xr-x 2 root root  0  2月  6 16:07 net_cls/
drwxr-xr-x 2 root root  0  2月  6 16:07 perf_event/
drwxr-xr-x 4 root root  0  2月  6 16:07 systemd/

# Ubuntuの場合
$ ls -l /sys/fs/cgroup
drwxr-xr-x 3 root root 0  4月 28 11:02 blkio/
drwxr-xr-x 3 root root 0  4月 28 11:02 cpu/
drwxr-xr-x 3 root root 0  4月 28 11:02 cpuacct/
drwxr-xr-x 3 root root 0  4月 28 11:02 cpuset/
drwxr-xr-x 3 root root 0  4月 28 11:02 devices/
drwxr-xr-x 3 root root 0  4月 28 11:02 freezer/
drwxr-xr-x 3 root root 0  4月 28 11:02 hugetlb/
drwxr-xr-x 3 root root 0  4月 28 11:02 memory/
drwxr-xr-x 3 root root 0  4月 28 11:02 perf_event/
drwxr-xr-x 3 root root 0  4月 28 11:02 systemd/

# CentOSの場合

$ ls -l /sys/fs/cgroup

drwxr-xr-x 2 root root 0 2月 6 16:07 blkio/

lrwxrwxrwx 1 root root 11 2月 6 16:07 cpu -> cpu,cpuacct/

drwxr-xr-x 2 root root 0 2月 6 16:07 cpu,cpuacct/

lrwxrwxrwx 1 root root 11 2月 6 16:07 cpuacct -> cpu,cpuacct/

drwxr-xr-x 2 root root 0 2月 6 16:07 cpuset/

drwxr-xr-x 2 root root 0 2月 6 16:07 devices/

drwxr-xr-x 2 root root 0 2月 6 16:07 freezer/

drwxr-xr-x 2 root root 0 2月 6 16:07 hugetlb/

drwxr-xr-x 2 root root 0 2月 6 16:07 memory/

drwxr-xr-x 2 root root 0 2月 6 16:07 net_cls/

drwxr-xr-x 2 root root 0 2月 6 16:07 perf_event/

drwxr-xr-x 4 root root 0 2月 6 16:07 systemd/

# Ubuntuの場合

$ ls -l /sys/fs/cgroup

drwxr-xr-x 3 root root 0 4月 28 11:02 blkio/

drwxr-xr-x 3 root root 0 4月 28 11:02 cpu/

drwxr-xr-x 3 root root 0 4月 28 11:02 cpuacct/

drwxr-xr-x 3 root root 0 4月 28 11:02 cpuset/

drwxr-xr-x 3 root root 0 4月 28 11:02 devices/

drwxr-xr-x 3 root root 0 4月 28 11:02 freezer/

drwxr-xr-x 3 root root 0 4月 28 11:02 hugetlb/

drwxr-xr-x 3 root root 0 4月 28 11:02 memory/

drwxr-xr-x 3 root root 0 4月 28 11:02 perf_event/

drwxr-xr-x 3 root root 0 4月 28 11:02 systemd/

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

## 使用可能なサブシステムは/proc/cgroupsで確認できる
$ cat /proc/cgroups                                                                                                                                           
#subsys_name    hierarchy       num_cgroups     enabled
cpuset  2       10      1
cpu     3       10      1
cpuacct 4       10      1
memory  5       10      1
devices 6       10      1
freezer 7       10      1
blkio   8       10      1
perf_event      9       10      1
hugetlb 10      10      1

## OSブート時にcgroupが初期化されていることを確認
$ dmesg | grep cgroup
[    0.000000] Initializing cgroup subsys cpuset
[    0.000000] Initializing cgroup subsys cpu
[    0.000000] Initializing cgroup subsys cpuacct
[    0.000000] allocated 33554432 bytes of page_cgroup
[    0.000000] please try 'cgroup_disable=memory' option if you don't want memory cgroups
[    0.002301] Initializing cgroup subsys memory
[    0.002305] Initializing cgroup subsys devices
[    0.002306] Initializing cgroup subsys freezer
[    0.002307] Initializing cgroup subsys blkio
[    0.002308] Initializing cgroup subsys perf_event
[    0.002310] Initializing cgroup subsys hugetlb

## include/linux/cgroup_subsys.h 内にマクロで列挙されている
$ cat include/linux/cgroup_subsys.h | grep 'SUBSYS('
SUBSYS(cpuset)
SUBSYS(debug)
SUBSYS(cpu_cgroup)
SUBSYS(cpuacct)
SUBSYS(mem_cgroup)
SUBSYS(devices)
SUBSYS(freezer)
SUBSYS(net_cls)
SUBSYS(blkio)
SUBSYS(perf)
SUBSYS(net_prio)
SUBSYS(hugetlb)

## 使用可能なサブシステムは/proc/cgroupsで確認できる

$ cat /proc/cgroups

#subsys_name hierarchy num_cgroups enabled

cpuset 2 10 1

cpu 3 10 1

cpuacct 4 10 1

memory 5 10 1

devices 6 10 1

freezer 7 10 1

blkio 8 10 1

perf_event 9 10 1

hugetlb 10 10 1

## OSブート時にcgroupが初期化されていることを確認

$ dmesg | grep cgroup

[ 0.000000] Initializing cgroup subsys cpuset

[ 0.000000] Initializing cgroup subsys cpu

[ 0.000000] Initializing cgroup subsys cpuacct

[ 0.000000] allocated 33554432 bytes of page_cgroup

[ 0.000000] please try 'cgroup_disable=memory' option if you don't want memory cgroups

[ 0.002301] Initializing cgroup subsys memory

[ 0.002305] Initializing cgroup subsys devices

[ 0.002306] Initializing cgroup subsys freezer

[ 0.002307] Initializing cgroup subsys blkio

[ 0.002308] Initializing cgroup subsys perf_event

[ 0.002310] Initializing cgroup subsys hugetlb

## include/linux/cgroup_subsys.h 内にマクロで列挙されている

$ cat include/linux/cgroup_subsys.h | grep 'SUBSYS('

SUBSYS(cpuset)

SUBSYS(debug)

SUBSYS(cpu_cgroup)

SUBSYS(cpuacct)

SUBSYS(mem_cgroup)

SUBSYS(devices)

SUBSYS(freezer)

SUBSYS(net_cls)

SUBSYS(blkio)

SUBSYS(perf)

SUBSYS(net_prio)

SUBSYS(hugetlb)

サブシステム	概要
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コマンドを実行し続けます。

$ sudo docker run -itd --cpuset-cpus 1 centos dd if=/dev/zero of=/dev/null
46532188bbd17503d9ceca0d57d72c5783d25e2f5648af4c89c5111e3a847a10

## topコマンドでCPU使用率を確認
$ top
top - 23:11:40 up  9:56,  1 user,  load average: 0.99, 0.58, 0.27
Tasks: 158 total,   2 running, 156 sleeping,   0 stopped,   0 zombie
%Cpu0  :  0.0 us,  0.0 sy,  0.0 ni,100.0 id,  0.0 wa,  0.0 hi,  0.0 si,  0.0 st
%Cpu1  : 26.3 us, 73.7 sy,  0.0 ni,  0.0 id,  0.0 wa,  0.0 hi,  0.0 si,  0.0 st  ## 1コアのみ利用されている
%Cpu2  :  0.0 us,  0.0 sy,  0.0 ni,100.0 id,  0.0 wa,  0.0 hi,  0.0 si,  0.0 st
%Cpu3  :  0.3 us,  0.0 sy,  0.0 ni, 99.7 id,  0.0 wa,  0.0 hi,  0.0 si,  0.0 st
KiB Mem:   8071336 total,  1041000 used,  7030336 free,   124388 buffers
KiB Swap: 16670716 total,        0 used, 16670716 free.   599068 cached Mem

  PID USER      PR  NI    VIRT    RES    SHR S  %CPU %MEM     TIME+ COMMAND
 7146 root      20   0    4356    360    284 R  99.8  0.0   4:13.35 dd
... 省略

$ sudo docker run -itd --cpuset-cpus 1 centos dd if=/dev/zero of=/dev/null

46532188bbd17503d9ceca0d57d72c5783d25e2f5648af4c89c5111e3a847a10

## topコマンドでCPU使用率を確認

$ top

top - 23:11:40 up 9:56, 1 user, load average: 0.99, 0.58, 0.27

Tasks: 158 total, 2 running, 156 sleeping, 0 stopped, 0 zombie

%Cpu0 : 0.0 us, 0.0 sy, 0.0 ni,100.0 id, 0.0 wa, 0.0 hi, 0.0 si, 0.0 st

%Cpu1 : 26.3 us, 73.7 sy, 0.0 ni, 0.0 id, 0.0 wa, 0.0 hi, 0.0 si, 0.0 st ## 1コアのみ利用されている

%Cpu2 : 0.0 us, 0.0 sy, 0.0 ni,100.0 id, 0.0 wa, 0.0 hi, 0.0 si, 0.0 st

%Cpu3 : 0.3 us, 0.0 sy, 0.0 ni, 99.7 id, 0.0 wa, 0.0 hi, 0.0 si, 0.0 st

KiB Mem: 8071336 total, 1041000 used, 7030336 free, 124388 buffers

KiB Swap: 16670716 total, 0 used, 16670716 free. 599068 cached Mem

PID USER PR NI VIRT RES SHR S %CPU %MEM TIME+ COMMAND

7146 root 20 0 4356 360 284 R 99.8 0.0 4:13.35 dd

... 省略

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

## cpuset.cpusファイルに1が書き込まれている
$ cat /sys/fs/cgroup/cpuset/docker/46532188bbd17503d9ceca0d57d72c5783d25e2f5648af4c89c5111e3a847a10/cpuset.cpus
1

## cpuset.cpusファイルに1が書き込まれている

$ cat /sys/fs/cgroup/cpuset/docker/46532188bbd17503d9ceca0d57d72c5783d25e2f5648af4c89c5111e3a847a10/cpuset.cpus

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

$ sudo docker run -itd --cpuset-cpus 1 --cpu-shares 2048 centos dd if=/dev/zero of=/dev/null
2b8096a07c04892d9882615a70f5cf58882de3af1434e45a931bf587ba9f2015

## 同様にtopコマンドでCPU使用率を確認
top - 23:38:30 up 10:23,  1 user,  load average: 1.99, 1.32, 0.79
Tasks: 159 total,   3 running, 156 sleeping,   0 stopped,   0 zombie
%Cpu0  :  0.0 us,  0.0 sy,  0.0 ni,100.0 id,  0.0 wa,  0.0 hi,  0.0 si,  0.0 st
%Cpu1  : 25.0 us, 75.0 sy,  0.0 ni,  0.0 id,  0.0 wa,  0.0 hi,  0.0 si,  0.0 st  ## 1コアのみ利用
%Cpu2  :  0.0 us,  0.3 sy,  0.0 ni, 99.7 id,  0.0 wa,  0.0 hi,  0.0 si,  0.0 st
%Cpu3  :  0.0 us,  0.0 sy,  0.0 ni,100.0 id,  0.0 wa,  0.0 hi,  0.0 si,  0.0 st
KiB Mem:   8071336 total,  1050296 used,  7021040 free,   125476 buffers
KiB Swap: 16670716 total,        0 used, 16670716 free.   600564 cached Mem

  PID USER      PR  NI    VIRT    RES    SHR S  %CPU %MEM     TIME+ COMMAND
 7794 root      20   0    4356    356    284 R  66.6  0.0   2:02.05 dd  ## 2つめのコンテナでのdd
 7670 root      20   0    4356    360    284 R  33.6  0.0   2:05.72 dd  ## 1つめのコンテナでのdd
... 省略

$ sudo docker run -itd --cpuset-cpus 1 --cpu-shares 2048 centos dd if=/dev/zero of=/dev/null

2b8096a07c04892d9882615a70f5cf58882de3af1434e45a931bf587ba9f2015

## 同様にtopコマンドでCPU使用率を確認

top - 23:38:30 up 10:23, 1 user, load average: 1.99, 1.32, 0.79

Tasks: 159 total, 3 running, 156 sleeping, 0 stopped, 0 zombie

%Cpu0 : 0.0 us, 0.0 sy, 0.0 ni,100.0 id, 0.0 wa, 0.0 hi, 0.0 si, 0.0 st

%Cpu1 : 25.0 us, 75.0 sy, 0.0 ni, 0.0 id, 0.0 wa, 0.0 hi, 0.0 si, 0.0 st ## 1コアのみ利用

%Cpu2 : 0.0 us, 0.3 sy, 0.0 ni, 99.7 id, 0.0 wa, 0.0 hi, 0.0 si, 0.0 st

%Cpu3 : 0.0 us, 0.0 sy, 0.0 ni,100.0 id, 0.0 wa, 0.0 hi, 0.0 si, 0.0 st

KiB Mem: 8071336 total, 1050296 used, 7021040 free, 125476 buffers

KiB Swap: 16670716 total, 0 used, 16670716 free. 600564 cached Mem

PID USER PR NI VIRT RES SHR S %CPU %MEM TIME+ COMMAND

7794 root 20 0 4356 356 284 R 66.6 0.0 2:02.05 dd ## 2つめのコンテナでのdd

7670 root 20 0 4356 360 284 R 33.6 0.0 2:05.72 dd ## 1つめのコンテナでのdd

... 省略

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

## cpu.sharesファイルに2048が書き込まれている
$ cat /sys/fs/cgroup/cpu/docker/2b8096a07c04892d9882615a70f5cf58882de3af1434e45a931bf587ba9f2015/cpu.shares
2048

## cpu.sharesファイルに2048が書き込まれている

$ cat /sys/fs/cgroup/cpu/docker/2b8096a07c04892d9882615a70f5cf58882de3af1434e45a931bf587ba9f2015/cpu.shares

2048

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

$ sudo docker run -itd --memory 128m centos /bin/bash
6077df1a5a396b729256871482942d033aa9f0897f3bf9753e1e90e23029eb48

## memory.limit_in_bytesファイルに指定した値がバイト単位で書き込まれている
$ cat /sys/fs/cgroup/memory/docker/6077df1a5a396b729256871482942d033aa9f0897f3bf9753e1e90e23029eb48/memory.limit_in_bytes
134217728  ## 128MB

$ sudo docker run -itd --memory 128m centos /bin/bash

6077df1a5a396b729256871482942d033aa9f0897f3bf9753e1e90e23029eb48

## memory.limit_in_bytesファイルに指定した値がバイト単位で書き込まれている

$ cat /sys/fs/cgroup/memory/docker/6077df1a5a396b729256871482942d033aa9f0897f3bf9753e1e90e23029eb48/memory.limit_in_bytes

134217728 ## 128MB

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

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

## コンテナ内のプロセスの現在のメモリ使用量
$ cat /sys/fs/cgroup/memory/docker/6077df1a5a396b729256871482942d033aa9f0897f3bf9753e1e90e23029eb48/memory.usage_in_bytes
2453504

## コンテナ内のプロセスのメモリ使用量の最大値
$ cat /sys/fs/cgroup/memory/docker/6077df1a5a396b729256871482942d033aa9f0897f3bf9753e1e90e23029eb48/memory.max_usage_in_bytes
134217728  ## コンテナ作成時にオプションで指定した値 128MB

## コンテナ内のプロセスのメモリ使用量が上限値に達した回数
$ cat /sys/fs/cgroup/memory/docker/6077df1a5a396b729256871482942d033aa9f0897f3bf9753e1e90e23029eb48/memory.failcnt
84491

## コンテナ内のプロセスの現在のメモリ使用量

$ cat /sys/fs/cgroup/memory/docker/6077df1a5a396b729256871482942d033aa9f0897f3bf9753e1e90e23029eb48/memory.usage_in_bytes

2453504

## コンテナ内のプロセスのメモリ使用量の最大値

$ cat /sys/fs/cgroup/memory/docker/6077df1a5a396b729256871482942d033aa9f0897f3bf9753e1e90e23029eb48/memory.max_usage_in_bytes

134217728 ## コンテナ作成時にオプションで指定した値 128MB

## コンテナ内のプロセスのメモリ使用量が上限値に達した回数

$ cat /sys/fs/cgroup/memory/docker/6077df1a5a396b729256871482942d033aa9f0897f3bf9753e1e90e23029eb48/memory.failcnt

84491

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

devicesサブシステム

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

$ ls -l /sys/fs/cgroup/devices
-rw-r--r-- 1 root root 0  4月 28 11:02 cgroup.clone_children
--w--w--w- 1 root root 0  4月 28 11:02 cgroup.event_control
-rw-r--r-- 1 root root 0  4月 28 11:02 cgroup.procs
-r--r--r-- 1 root root 0  4月 28 11:02 cgroup.sane_behavior
--w------- 1 root root 0  4月 28 11:02 devices.allow
--w------- 1 root root 0  4月 28 11:02 devices.deny
-r--r--r-- 1 root root 0  4月 28 11:02 devices.list
drwxr-xr-x 3 root root 0  4月 28 11:09 docker/
-rw-r--r-- 1 root root 0  4月 28 11:02 notify_on_release
-rw-r--r-- 1 root root 0  4月 28 11:02 release_agent
-rw-r--r-- 1 root root 0  4月 28 11:02 tasks
drwxr-xr-x 4 root root 0  4月 28 11:02 user/

$ ls -l /sys/fs/cgroup/devices

-rw-r--r-- 1 root root 0 4月 28 11:02 cgroup.clone_children

--w--w--w- 1 root root 0 4月 28 11:02 cgroup.event_control

-rw-r--r-- 1 root root 0 4月 28 11:02 cgroup.procs

-r--r--r-- 1 root root 0 4月 28 11:02 cgroup.sane_behavior

--w------- 1 root root 0 4月 28 11:02 devices.allow

--w------- 1 root root 0 4月 28 11:02 devices.deny

-r--r--r-- 1 root root 0 4月 28 11:02 devices.list

drwxr-xr-x 3 root root 0 4月 28 11:09 docker/

-rw-r--r-- 1 root root 0 4月 28 11:02 notify_on_release

-rw-r--r-- 1 root root 0 4月 28 11:02 release_agent

-rw-r--r-- 1 root root 0 4月 28 11:02 tasks

drwxr-xr-x 4 root root 0 4月 28 11:02 user/

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

  /*
   * Historical crazy stuff.  These don't have "cgroup."  prefix and
   * don't exist if sane_behavior.  If you're depending on these, be
   * prepared to be burned.
   */
  {
    .name = "tasks",
    .flags = CFTYPE_INSANE,   /* use "procs" instead */
    .seq_start = cgroup_pidlist_start,
    .seq_next = cgroup_pidlist_next,
    .seq_stop = cgroup_pidlist_stop,
    .seq_show = cgroup_pidlist_show,
    .private = CGROUP_FILE_TASKS,
    .write_u64 = cgroup_tasks_write,
    .mode = S_IRUGO | S_IWUSR,
  },
  {
    .name = "notify_on_release",
    .flags = CFTYPE_INSANE,
    .read_u64 = cgroup_read_notify_on_release,
    .write_u64 = cgroup_write_notify_on_release,
  },
  {
    .name = "release_agent",
    .flags = CFTYPE_INSANE | CFTYPE_ONLY_ON_ROOT,
    .seq_show = cgroup_release_agent_show,
    .write_string = cgroup_release_agent_write,
    .max_write_len = PATH_MAX,
  },
  { } /* terminate */
};

* Historical crazy stuff. These don't have "cgroup." prefix and

* don't exist if sane_behavior. If you're depending on these, be

* prepared to be burned.

{

.name = "tasks",

.flags = CFTYPE_INSANE, /* use "procs" instead */

.seq_start = cgroup_pidlist_start,

.seq_next = cgroup_pidlist_next,

.seq_stop = cgroup_pidlist_stop,

.seq_show = cgroup_pidlist_show,

.private = CGROUP_FILE_TASKS,

.write_u64 = cgroup_tasks_write,

.mode = S_IRUGO | S_IWUSR,

{

.name = "notify_on_release",

.flags = CFTYPE_INSANE,

.read_u64 = cgroup_read_notify_on_release,

.write_u64 = cgroup_write_notify_on_release,

{

.name = "release_agent",

.flags = CFTYPE_INSANE | CFTYPE_ONLY_ON_ROOT,

.seq_show = cgroup_release_agent_show,

.write_string = cgroup_release_agent_write,

.max_write_len = PATH_MAX,

{ } /* terminate */

};

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

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

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

$ cat /sys/fs/cgroup/devices/devices.list
a *:* rwm  ## 全てのデバイスにアクセス可能であることを示している、具体的な読み方は後述

1 2	$ cat /sys/fs/cgroup/devices/devices.list a : rwm ## 全てのデバイスにアクセス可能であることを示している、具体的な読み方は後述

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

## dockerコンテナ起動前
$ ls /sys/fs/cgroup/devices/docker/
cgroup.clone_children  cgroup.event_control  cgroup.procs  devices.allow  devices.deny  devices.list  notify_on_release  tasks
## コンテナ起動
$ sudo docker ps -a
CONTAINER ID        IMAGE               COMMAND             CREATED             STATUS                       PORTS               NAMES
a4557c514ddc        centos              "/bin/bash"         9 weeks ago         Exited (137) 4 seconds ago                       clever_hawking
$ sudo docker start clever_hawking
clever_hawking
## dockerコンテナ起動時に /sys/fs/cgroup/{サブシステム}/docker/{コンテナID} ディレクトリが作成される
$ ls /sys/fs/cgroup/devices/docker/
a4557c514ddc3c3668030fe9b1aac13b7ba8c5ea3fdaed70e345eb7991df364c/  cgroup.clone_children  cgroup.event_control  cgroup.procs  devices.allow  devices.deny  devices.list  notify_on_release  tasks
## 同様にdevices.listの中身を見る
$ cat /sys/fs/cgroup/devices/docker/a4557c514ddc3c3668030fe9b1aac13b7ba8c5ea3fdaed70e345eb7991df364c/devices.list
c *:* m
b *:* m
c 5:1 rwm
c 4:0 rwm
c 4:1 rwm
c 136:* rwm
c 5:2 rwm
c 10:200 rwm
c 1:3 rwm
c 1:5 rwm
c 1:7 rwm
c 5:0 rwm
c 1:9 rwm
c 1:8 rwm

## dockerコンテナ起動前

$ ls /sys/fs/cgroup/devices/docker/

cgroup.clone_children cgroup.event_control cgroup.procs devices.allow devices.deny devices.list notify_on_release tasks

## コンテナ起動

$ sudo docker ps -a

CONTAINER ID IMAGE COMMAND CREATED STATUS PORTS NAMES

a4557c514ddc centos "/bin/bash" 9 weeks ago Exited (137) 4 seconds ago clever_hawking

$ sudo docker start clever_hawking

clever_hawking

## dockerコンテナ起動時に /sys/fs/cgroup/{サブシステム}/docker/{コンテナID} ディレクトリが作成される

$ ls /sys/fs/cgroup/devices/docker/

a4557c514ddc3c3668030fe9b1aac13b7ba8c5ea3fdaed70e345eb7991df364c/ cgroup.clone_children cgroup.event_control cgroup.procs devices.allow devices.deny devices.list notify_on_release tasks

## 同様にdevices.listの中身を見る

$ cat /sys/fs/cgroup/devices/docker/a4557c514ddc3c3668030fe9b1aac13b7ba8c5ea3fdaed70e345eb7991df364c/devices.list

c *:* m

b *:* m

c 5:1 rwm

c 4:0 rwm

c 4:1 rwm

c 136:* rwm

c 5:2 rwm

c 10:200 rwm

c 1:3 rwm

c 1:5 rwm

c 1:7 rwm

c 5:0 rwm

c 1:9 rwm

c 1:8 rwm

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

先頭のアルファベット 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コンテナ内のセキュリティを担保しているのですが、ここでは試しにその制限を解除してみます。

## 適当なdockerコンテナを作る
$ sudo docker run -it centos /bin/bash
## dockerコンテナ内のcgroupsの設定を確認
$ cat /sys/fs/cgroup/devices/docker/a3cdbc51ba62665e056fc438390dcf7e0ee3deae6e39312dfa41071d9cde2946/cgroup.procs
7811  ## 起動しているプロセスIDが表示される
$ ps 7811
  PID TTY      STAT   TIME COMMAND
 7811 pts/20   Ss+    0:00 /bin/bash  ## PID 7811はbashプロセス
## コンテナ内のbashプロセスから/dev/kmsgへの書き込みが制限されていることを確認
# mknod /dev/kmsg c 1 11
# echo aiueo > /dev/kmsg
bash: /dev/kmsg: Operation not permitted  ## この時点では書き込みできない
## 制限を解除するには、ホストから別のcgroupにコンテナ内のプロセスを移す
$ cd /sys/fs/cgroup/devices
$ echo 7811 | sudo tee cgroup.procs
7811
## もう一度コンテナ内から/dev/kmsgに書き込みを試すと
# echo aiueo > /dev/kmsg  ## 今度は成功
## ホストからカーネルバッファを確認
$ dmesg | tail -n 1
[ 6563.293512] aiueo  ## コンテナ側から書き込んだ文字列が記録されている

## 適当なdockerコンテナを作る

$ sudo docker run -it centos /bin/bash

## dockerコンテナ内のcgroupsの設定を確認

$ cat /sys/fs/cgroup/devices/docker/a3cdbc51ba62665e056fc438390dcf7e0ee3deae6e39312dfa41071d9cde2946/cgroup.procs

7811 ## 起動しているプロセスIDが表示される

$ ps 7811

PID TTY STAT TIME COMMAND

7811 pts/20 Ss+ 0:00 /bin/bash ## PID 7811はbashプロセス

## コンテナ内のbashプロセスから/dev/kmsgへの書き込みが制限されていることを確認

# mknod /dev/kmsg c 1 11

# echo aiueo > /dev/kmsg

bash: /dev/kmsg: Operation not permitted ## この時点では書き込みできない

## 制限を解除するには、ホストから別のcgroupにコンテナ内のプロセスを移す

$ cd /sys/fs/cgroup/devices

$ echo 7811 | sudo tee cgroup.procs

7811

## もう一度コンテナ内から/dev/kmsgに書き込みを試すと

# echo aiueo > /dev/kmsg ## 今度は成功

## ホストからカーネルバッファを確認

$ dmesg | tail -n 1

[ 6563.293512] aiueo ## コンテナ側から書き込んだ文字列が記録されている

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

$ echo 'c 1:11 rwm' | sudo tee /sys/fs/cgroup/devices/docker/a3cdbc51ba62665e056fc438390dcf7e0ee3deae6e39312dfa41071d9cde2946/devices.allow
c 1:11 rwm

1 2	$ echo 'c 1:11 rwm' \| sudo tee /sys/fs/cgroup/devices/docker/a3cdbc51ba62665e056fc438390dcf7e0ee3deae6e39312dfa41071d9cde2946/devices.allow c 1:11 rwm

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

カーネルの実装

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

## include/linux/sched.h
#ifdef CONFIG_CGROUPS
  /* Control Group info protected by css_set_lock */
  struct css_set __rcu *cgroups;
  /* cg_list protected by css_set_lock and tsk->alloc_lock */
  struct list_head cg_list;
#endif

## include/linux/sched.h

#ifdef CONFIG_CGROUPS

/* Control Group info protected by css_set_lock */

struct css_set __rcu *cgroups;

/* cg_list protected by css_set_lock and tsk->alloc_lock */

struct list_head cg_list;

#endif

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

struct css_set {

  /* Reference count */
  atomic_t refcount;

  /*
   * List running through all cgroup groups in the same hash
   * slot. Protected by css_set_lock
   */
  struct hlist_node hlist;

  /*
   * List running through all tasks using this cgroup
   * group. Protected by css_set_lock
   */
  struct list_head tasks;

  /*
   * List of cg_cgroup_link objects on link chains from
   * cgroups referenced from this css_set. Protected by
   * css_set_lock
   */
  struct list_head cg_links;

  /*
   * Set of subsystem states, one for each subsystem. This array
   * is immutable after creation apart from the init_css_set
   * during subsystem registration (at boot time) and modular subsystem
   * loading/unloading.
   */
  struct cgroup_subsys_state *subsys[CGROUP_SUBSYS_COUNT];

  /* For RCU-protected deletion */
  struct rcu_head rcu_head;
};

struct css_set {

/* Reference count */

atomic_t refcount;

* List running through all cgroup groups in the same hash

* slot. Protected by css_set_lock

struct hlist_node hlist;

* List running through all tasks using this cgroup

* group. Protected by css_set_lock

struct list_head tasks;

* List of cg_cgroup_link objects on link chains from

* cgroups referenced from this css_set. Protected by

* css_set_lock

struct list_head cg_links;

* Set of subsystem states, one for each subsystem. This array

* is immutable after creation apart from the init_css_set

* during subsystem registration (at boot time) and modular subsystem

* loading/unloading.

struct cgroup_subsys_state *subsys[CGROUP_SUBSYS_COUNT];

/* For RCU-protected deletion */

struct rcu_head rcu_head;

};

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

/* Per-subsystem/per-cgroup state maintained by the system. */
struct cgroup_subsys_state {
  /* the cgroup that this css is attached to */
  struct cgroup *cgroup;

  /* the cgroup subsystem that this css is attached to */
  struct cgroup_subsys *ss;

  /* reference count - access via css_[try]get() and css_put() */
  struct percpu_ref refcnt;

  /* the parent css */
  struct cgroup_subsys_state *parent;

  unsigned long flags;

  /* percpu_ref killing and RCU release */
  struct rcu_head rcu_head;
  struct work_struct destroy_work;
};

// cgroup 構造体の一部
struct cgroup {
  unsigned long flags;    /* "unsigned long" so bitops work */

  /*
   * count users of this cgroup. >0 means busy, but doesn't
   * necessarily indicate the number of tasks in the cgroup
   */
  atomic_t count;

  int id;       /* ida allocated in-hierarchy ID */

  /*
   * We link our 'sibling' struct into our parent's 'children'.
   * Our children link their 'sibling' into our 'children'.
   */
  struct list_head sibling; /* my parent's children */
  struct list_head children;  /* my children */
  struct list_head files;   /* my files */

  struct cgroup *parent;    /* my parent */
  struct dentry *dentry;    /* cgroup fs entry, RCU protected */
... 長いので省略

/* Per-subsystem/per-cgroup state maintained by the system. */

struct cgroup_subsys_state {

/* the cgroup that this css is attached to */

struct cgroup *cgroup;

/* the cgroup subsystem that this css is attached to */

struct cgroup_subsys *ss;

/* reference count - access via css_[try]get() and css_put() */

struct percpu_ref refcnt;

/* the parent css */

struct cgroup_subsys_state *parent;

unsigned long flags;

/* percpu_ref killing and RCU release */

struct rcu_head rcu_head;

struct work_struct destroy_work;

};

// cgroup 構造体の一部

struct cgroup {

unsigned long flags; /* "unsigned long" so bitops work */

* count users of this cgroup. >0 means busy, but doesn't

* necessarily indicate the number of tasks in the cgroup

atomic_t count;

int id; /* ida allocated in-hierarchy ID */

* We link our 'sibling' struct into our parent's 'children'.

* Our children link their 'sibling' into our 'children'.

struct list_head sibling; /* my parent's children */

struct list_head children; /* my children */

struct list_head files; /* my files */

struct cgroup *parent; /* my parent */

struct dentry *dentry; /* cgroup fs entry, RCU protected */

... 長いので省略

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

リード・コピー・アップデート - Wikipedia

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

/* security/device_cgroup.c */

// デバイスへのアクセス可否(ファイルパーミッション)をチェックする関数
static int __devcgroup_check_permission(short type, u32 major, u32 minor,
                short access)
{
  struct dev_cgroup *dev_cgroup;
  struct dev_exception_item ex; 
  int rc; 

  memset(&ex, 0, sizeof(ex));
  ex.type = type;
  ex.major = major;
  ex.minor = minor;
  ex.access = access;

  rcu_read_lock();
  dev_cgroup = task_devcgroup(current);
  rc = may_access(dev_cgroup, &ex, dev_cgroup->behavior);
  rcu_read_unlock();

  if (!rc)
    return -EPERM;

  return 0;
}

// dev_cgroup 構造体
struct dev_cgroup {
  struct cgroup_subsys_state css;
  struct list_head exceptions;
  enum devcg_behavior behavior;
  /* temporary list for pending propagation operations */
  struct list_head propagate_pending;
};

// dev_exception_item 構造体
struct dev_exception_item {
  u32 major, minor;
  short type;
  short access;
  struct list_head list;
  struct rcu_head rcu;
};

/* security/device_cgroup.c */

// デバイスへのアクセス可否(ファイルパーミッション)をチェックする関数

static int __devcgroup_check_permission(short type, u32 major, u32 minor,

short access)

{

struct dev_cgroup *dev_cgroup;

struct dev_exception_item ex;

int rc;

memset(&ex, 0, sizeof(ex));

ex.type = type;

ex.major = major;

ex.minor = minor;

ex.access = access;

rcu_read_lock();

dev_cgroup = task_devcgroup(current);

rc = may_access(dev_cgroup, &ex, dev_cgroup->behavior);

rcu_read_unlock();

if (!rc)

return -EPERM;

return 0;

}

// dev_cgroup 構造体

struct dev_cgroup {

struct cgroup_subsys_state css;

struct list_head exceptions;

enum devcg_behavior behavior;

/* temporary list for pending propagation operations */

struct list_head propagate_pending;

};

// dev_exception_item 構造体

struct dev_exception_item {

u32 major, minor;

short type;

short access;

struct list_head list;

struct rcu_head rcu;

};

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

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

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

参考

cgroups documentation - The Linux Kernel Archives
第1章コントロールグループについて (cgroup)
Linux Containers Basic Concepts (PDF)
Linux Kernel Updates Vol 2014.08 (Kindle)

おまけ: 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!

## installation
## CentOS
$ sudo yum install cscope
## Ubuntu
$ sudo apt-get install cscope

## installation

## CentOS

$ sudo yum install cscope

## Ubuntu

$ sudo apt-get install cscope

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

Tags: c/c++, unix/linux

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

3月 15th, 2016 in tech/study tags: algorithm, javascript, ml, typescript

Comments →

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

TypeScript入門 - 機械学習の実装 1 Denoising Autoencoder

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

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

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

imageprocessing-labs/ml at master

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

// 2クラスのデータを作成
var d: number = 2, N: number = 100,
    x1: number[][] = createSample(d, N),
    x2: number[][] = createSample(d, N),
    x3: number[][] = createSample(d, N),
    x4: number[][] = createSample(d, N),
    y1: number[][] = createLabel(d, 1, N),
    y2: number[][] = createLabel(d, 2, N),
    y3: number[][] = createLabel(d, 1, N),
    y4: number[][] = createLabel(d, 2, N);

for(var i=0; i<N; i++) {
    x2[i][0] += 20; // 半分のデータ点を移動
    x2[i][1] += 10;
    x4[i][0] += 30;
    x4[i][1] += 20;
}

var x: ml.Matrix = new ml.Matrix(x1.concat(x2)); // 行列のインスタンス作成
var y: ml.Matrix = new ml.Matrix(y1.concat(y2));

// ロジスティック回帰クラスのインスタンス作成
var clf: ml.LogisticRegression = new ml.LogisticRegression(x, y);
var lr: number = 0.1,  // 初期学習率
var l2Reg: number = 0.00,  // L2正則化項係数
var iter: number = 100,  // イテレーション回数
var verbose: boolean = true;  // クロスエントロピー損失の値をコンソール出力

// 学習を実行
clf.fit(lr, iter, l2Reg, verbose);

// テストデータ
var tx: ml.Matrix = new ml.Matrix(x3.concat(x4));
var ty: ml.Matrix = new ml.Matrix(y3.concat(y4));

console.log(x.shape, y.shape, tx.shape, ty.shape);

// テストデータで予測
var pred: ml.Matrix = clf.predict(tx);
// 正答率の集計
var accuracy: number = ml.Metrics.accuracy(ty, pred);

console.log("accuracy: " + accuracy.toString());


// データ作成用の関数
function createSample(d: number, n: number): number[][] {
    var data: number[][] = [];
    for (var i = 0; i < n; i++) {
        data[i] = [];
        for (var j = 0; j < d; j++) {
            data[i][j] = Math.floor(randn());
        }
    }
    return data;
}

function createLabel(d: number, c: number, n: number): number[][] {
    var data: number[][] = [];
    for (var i = 0; i < n; i++) {
        data[i] = [];
        for (var j = 0; j < d; j++) {
            data[i][j] = 0;
            if (j == (c - 1)) {
                data[i][j] = 1;
            }
        }
    }
    return data;
}
// Box-Muller法
function randn(m = 0.0, v = 1.0): number {
    var a = 1 - Math.random(),
        b = 1 - Math.random(),
        c = Math.sqrt(-2 * Math.log(a));
    if (0.5 - Math.random() > 0) {
        return c * Math.sin(Math.PI * 2 * b) * v + m;
    } else {
        return c * Math.cos(Math.PI * 2 * b) * v + m;
    }
}

// 2クラスのデータを作成

var d: number = 2, N: number = 100,

x1: number[][] = createSample(d, N),

x2: number[][] = createSample(d, N),

x3: number[][] = createSample(d, N),

x4: number[][] = createSample(d, N),

y1: number[][] = createLabel(d, 1, N),

y2: number[][] = createLabel(d, 2, N),

y3: number[][] = createLabel(d, 1, N),

y4: number[][] = createLabel(d, 2, N);

for(var i=0; i<N; i++) {

x2[i][0] += 20; // 半分のデータ点を移動

x2[i][1] += 10;

x4[i][0] += 30;

x4[i][1] += 20;

}

var x: ml.Matrix = new ml.Matrix(x1.concat(x2)); // 行列のインスタンス作成

var y: ml.Matrix = new ml.Matrix(y1.concat(y2));

// ロジスティック回帰クラスのインスタンス作成

var clf: ml.LogisticRegression = new ml.LogisticRegression(x, y);

var lr: number = 0.1, // 初期学習率

var l2Reg: number = 0.00, // L2正則化項係数

var iter: number = 100, // イテレーション回数

var verbose: boolean = true; // クロスエントロピー損失の値をコンソール出力

// 学習を実行

clf.fit(lr, iter, l2Reg, verbose);

// テストデータ

var tx: ml.Matrix = new ml.Matrix(x3.concat(x4));

var ty: ml.Matrix = new ml.Matrix(y3.concat(y4));

console.log(x.shape, y.shape, tx.shape, ty.shape);

// テストデータで予測

var pred: ml.Matrix = clf.predict(tx);

// 正答率の集計

var accuracy: number = ml.Metrics.accuracy(ty, pred);

console.log("accuracy: " + accuracy.toString());

// データ作成用の関数

function createSample(d: number, n: number): number[][] {

var data: number[][] = [];

for (var i = 0; i < n; i++) {

data[i] = [];

for (var j = 0; j < d; j++) {

data[i][j] = Math.floor(randn());

}

return data;

}

function createLabel(d: number, c: number, n: number): number[][] {

var data: number[][] = [];

for (var i = 0; i < n; i++) {

data[i] = [];

for (var j = 0; j < d; j++) {

data[i][j] = 0;

if (j == (c - 1)) {

data[i][j] = 1;

}

return data;

}

// Box-Muller法

function randn(m = 0.0, v = 1.0): number {

var a = 1 - Math.random(),

b = 1 - Math.random(),

c = Math.sqrt(-2 * Math.log(a));

if (0.5 - Math.random() > 0) {

return c * Math.sin(Math.PI * 2 * b) * v + m;

} else {

return c * Math.cos(Math.PI * 2 * b) * v + m;

}

* 出力結果

Loss: 7.484437784160068
Loss: 7.4823515706712955
Loss: 7.480910710736696
Loss: 7.47957441184471
Loss: 7.478276584000806
... 省略
Loss: 0.11801311268755298
Loss: 0.11730614586557697
Loss: 0.11661028260673367
Loss: 0.11592528080159488
Loss: 0.11525090507107187
[ 200, 2 ] [ 200, 2 ] [ 200, 2 ] [ 200, 2 ]  ## 2次元 2クラス 学習データ数 200, テストデータ数 200
accuracy: 0.995  ## 99.5%の正答率

Loss: 7.484437784160068

Loss: 7.4823515706712955

Loss: 7.480910710736696

Loss: 7.47957441184471

Loss: 7.478276584000806

... 省略

Loss: 0.11801311268755298

Loss: 0.11730614586557697

Loss: 0.11661028260673367

Loss: 0.11592528080159488

Loss: 0.11525090507107187

[ 200, 2 ] [ 200, 2 ] [ 200, 2 ] [ 200, 2 ] ## 2次元 2クラス学習データ数 200, テストデータ数 200

accuracy: 0.995 ## 99.5%の正答率

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

Iris Data Set (3クラス, 4次元特徴量)
Handwritten Digits Data Set (10クラス, 64次元特徴量)

// irisデータ (学習:テスト 4:1 で分割)
var x1 = iris.data,
    y1 = iris.target;
    trainSize: number = Math.ceil(x1.length*0.8);
    testSize: number = x1.length - trainSize;
    trainData: number[][] = x1.slice(0, trainSize);
    trainLabel: number[] = y1.slice(0, trainSize);
    testData: number[][] = x1.slice(trainSize, trainSize + testSize);
    testLabel: number[] = y1.slice(trainSize, trainSize + testSize);

var x: ml.Matrix = new ml.Matrix(trainData);
var y: ml.Matrix = new ml.Matrix(ml.Preprocessing.binalizeLabel(trainLabel));

var clf: ml.LogisticRegression = new ml.LogisticRegression(x, y);

clf.fit(0.1, 100, 0.00, false);

var tx: ml.Matrix = new ml.Matrix(testData);
var ty: ml.Matrix = new ml.Matrix(ml.Preprocessing.binalizeLabel(testLabel));

console.log(x.shape, y.shape, tx.shape, ty.shape);

var pred: ml.Matrix = clf.predict(tx);
var accuracy: number = ml.Metrics.accuracy(ty, pred);

console.log("accuracy: " + accuracy.toString());

// irisデータ (学習:テスト 4:1 で分割)

var x1 = iris.data,

y1 = iris.target;

trainSize: number = Math.ceil(x1.length*0.8);

testSize: number = x1.length - trainSize;

trainData: number[][] = x1.slice(0, trainSize);

trainLabel: number[] = y1.slice(0, trainSize);

testData: number[][] = x1.slice(trainSize, trainSize + testSize);

testLabel: number[] = y1.slice(trainSize, trainSize + testSize);

var x: ml.Matrix = new ml.Matrix(trainData);

var y: ml.Matrix = new ml.Matrix(ml.Preprocessing.binalizeLabel(trainLabel));

var clf: ml.LogisticRegression = new ml.LogisticRegression(x, y);

clf.fit(0.1, 100, 0.00, false);

var tx: ml.Matrix = new ml.Matrix(testData);

var ty: ml.Matrix = new ml.Matrix(ml.Preprocessing.binalizeLabel(testLabel));

console.log(x.shape, y.shape, tx.shape, ty.shape);

var pred: ml.Matrix = clf.predict(tx);

var accuracy: number = ml.Metrics.accuracy(ty, pred);

console.log("accuracy: " + accuracy.toString());

* 実行結果

[ 120, 4 ] [ 120, 3 ] [ 30, 4 ] [ 30, 3 ]  ## 4次元 3クラス 学習データ数 120, テストデータ数 30
accuracy: 1  ## 正答率100%

1 2	[ 120, 4 ] [ 120, 3 ] [ 30, 4 ] [ 30, 3 ] ## 4次元 3クラス学習データ数 120, テストデータ数 30 accuracy: 1 ## 正答率100%

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

/*
var digits: {
  data: number[][];
  target: number[];
}
*/
var x1 = digits.data,
    y1 = digits.target;

// 以下、同様に学習、テスト

var digits: {

data: number[][];

target: number[];

}

var x1 = digits.data,

y1 = digits.target;

// 以下、同様に学習、テスト

* 実行結果

[ 1438, 64 ] [ 1438, 10 ] [ 359, 64 ] [ 359, 10 ]  ## 64次元 10クラス 学習データ数 1438, テストデータ数 359
accuracy: 0.9217877094972067  ## 正答率約92%

1 2	[ 1438, 64 ] [ 1438, 10 ] [ 359, 64 ] [ 359, 10 ] ## 64次元 10クラス学習データ数 1438, テストデータ数 359 accuracy: 0.9217877094972067 ## 正答率約92%

約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のエディタは軽快だし、インテリセンスの反応も良くサクサクと実装を進めることができます。

言語仕様面での課題

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

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

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

おわりに

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

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

JavaScriptで決定木

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

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

Tags: algorithm, javascript, ml, typescript

次ページへ »