Security meets Machine Learningという勉強会にて,上記のタイトルで発表した.資料はこちら:

 謎の力が働いて会社からの発表になっておりますが,機械学習の研究をしているわけではありません.既存研究の再現実装を試みているとこれ中国語の部屋じゃんという気持ちになる.
 ともあれ,これまで各種資料はただSpeakerDeckに載せるだけだったのを今後はブログから一元的に参照できるようにします.

 本稿はSFC-RG Advent Calendar 2016の4日目である.

はじめに

 あなたは研究の中間発表を終えて,今晩何を食べようか考えている.たしかに準備不足ではあったけれど,研究の前提をいまいち解さないファカルティの高飛車な質問にはうんざりしたし,今日くらいはパーッと気分転換したいものだ.そういうわけで,あなたは⊿館を飛び出して焼肉 ざんまい 湘南台店に行くことにした.

組合せ最適化

 さて,着席し,メニューを開いたあなたはしばし考える.限られた予算,限られた時間,限られた胃袋の容量——いったい何を頼めば最も満足できるだろうか?
 そんなとき,組合せ最適化が役に立つんです.騙されたと思って,メニューを必死に転記してみよう:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
import numpy as np, pandas as pd
menu = ['カルビ', '和牛カルビ', '和牛中落ちカルビ', 'ハラミ', '厚切りロース', 'ネギ牛タン塩', '牛タン塩',
'イベリコ豚', 'カシラ', '豚トロ', 'ネギ豚タン塩', '豚タン塩', '厚切りベーコン', 'ウインナー', 'チョリソ',
'ホルモン', 'シロコロホルモン', 'レバー', '白レバー', 'ハツ', 'ミノ',
'お得!! 三種盛り', '本日の塩三種盛り', '本日の味噌三種盛り']
price = [720, 950, 850, 720, 690, 950, 850,
600, 550, 580, 680, 580, 500, 380, 400,
550, 600, 550, 450, 550, 650,
1280, 780, 780]
n = len(menu)
np.random.seed(0)
df = pd.DataFrame({
'品目': menu,
'値段': price,
'満足度': np.random.randint(10, 20, n),
'焼き時間': np.random.randint(5, 10, n),
'量': np.random.randint(10, 20, n),
})
print(df)
値段 品目 満足度 焼き時間
0 720 カルビ 15 9 10
1 950 和牛カルビ 10 8 10
2 850 和牛中落ちカルビ 13 5 14
3 720 ハラミ 13 8 15
4 690 厚切りロース 17 5 15
5 950 ネギ牛タン塩 19 7 16
6 850 牛タン塩 13 8 18
7 600 イベリコ豚 15 5 14
8 550 カシラ 12 6 11
9 580 豚トロ 14 8 14
10 680 ネギ豚タン塩 17 8 19
11 580 豚タン塩 16 8 18
12 500 厚切りベーコン 18 5 11
13 380 ウインナー 18 6 11
14 400 チョリソ 11 6 17
15 550 ホルモン 16 6 19
16 600 シロコロホルモン 17 5 19
17 550 レバー 17 7 13
18 450 白レバー 18 9 16
19 550 ハツ 11 8 17
20 650 ミノ 15 8 12
21 1280 お得!! 三種盛り 19 7 10
22 780 本日の塩三種盛り 18 9 13
23 780 本日の味噌三種盛り 19 7 15

 メニューがpandasのデータフレームになった.取り急ぎ(?)満足度・焼き時間・量は乱数で埋めている.
 あなたはこのメニューの中から,最も満足度の高い組合せを見つけたい.それも,限られた予算,限られた時間,限られた胃袋の容量という条件を満たすような.ここではそのわがままを割当問題として解くことにする.

変数 $x_i \in \{0, 1\}$ i番目の料理を選ぶかどうか
目的関数 $\sum_i{満足度_i x_i}$ $\rightarrow$ 最大
制約条件 $\sum_i{予算_i x_i} \le 12000$ 予算制限
$\sum_i{焼き時間_i x_i} \le 120$ 時間制限
$150 \le \sum_i{量_i x_i} \le 200$ 分量制限

 こういった問題はpulpという整数計画法ライブラリを使って解くことができる:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
from pulp import *
m = LpProblem(sense = LpMaximize) # 最大化問題
df['x'] = [LpVariable('x%d' % i, cat = LpBinary) for i in range(n)] # i番目の品目を選択するかしないか
m += lpDot(df.満足度, df.x) # 目的関数:満足度の最大化
m += lpDot(df.値段, df.x) <= 12000 # 制約条件:予算
m += lpDot(df.焼き時間, df.x) <= 120 # 制約条件:焼き時間
m += lpDot(df.量, df.x) >= 150 # 制約条件:量
m += lpDot(df.量, df.x) <= 200 # 制約条件:量
m.solve()
if m.status == 1:
df['val'] = df.x.apply(lambda v: value(v)) # 結果
print(df[df.val == 1].品目)
print('満足度 {}'.format(sum(df[df.val == 1].満足度)))
print('値段 {}'.format(sum(df[df.val == 1].値段)))
>>>
0 カルビ
4 厚切りロース
5 ネギ牛タン塩
7 イベリコ豚
8 カシラ
9 豚トロ
12 厚切りベーコン
13 ウインナー
16 シロコロホルモン
17 レバー
18 白レバー
20 ミノ
21 お得!! 三種盛り
22 本日の塩三種盛り
23 本日の味噌三種盛り
Name: 品目, dtype: object
満足度 251
値段 10060

 はい.順番はともかくとして,これらを食べれば満足できそうだ.
 ここまで考えたところで,あなたは今月の懐具合がよろしくないことを思い出す.なるべく出費を抑えて,それでいてある程度満足できるような品目の組合せはあるだろうか?
 これも同様に割当問題として考えられる.

変数 $x_i \in \{0, 1\}$ i番目の料理を選ぶかどうか
目的関数 $\sum_i{予算_i x_i}$ $\rightarrow$ 最小
制約条件 $\sum_i{満足度_i x_i} \le 200$ 満足度制限
$\sum_i{焼き時間_i x_i} \le 120$ 時間制限
$150 \le \sum_i{量_i x_i} \le 200$ 分量制限
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
m = LpProblem(sense = LpMinimize) # 最小化問題
a['v'] = [LpVariable('v%d' % i, cat = LpBinary) for i in range(n)] # i番目の品目を選択するかしないか
m += lpDot(df.値段, df.x) # 目的関数:予算の最小化
m += lpDot(df.満足度, df.x) >= 200 # 制約条件:満足度
m += lpDot(df.焼き時間, df.x) <= 120 # 制約条件:焼き時間
m += lpDot(df.量, df.x) >= 150 # 制約条件:量
m += lpDot(df.量, df.x) <= 200 # 制約条件:量
m.solve()
if m.status == 1:
df['val'] = df.x.apply(lambda v: value(v)) # 結果
print(df[df.val == 1].品目)
print('満足度 {}'.format(sum(df[df.val == 1].満足度)))
print('値段 {}'.format(sum(df[df.val == 1].値段)))
>>>
7 イベリコ豚
10 ネギ豚タン塩
11 豚タン塩
12 厚切りベーコン
13 ウインナー
14 チョリソ
15 ホルモン
16 シロコロホルモン
17 レバー
18 白レバー
22 本日の塩三種盛り
23 本日の味噌三種盛り
Name: 品目, dtype: object
満足度 200
値段 6850

 200の満足度でいいなら豚ばっか食ってろということらしい.

多腕バンディット問題

 いやいやちょっと待った.乱数でお茶を濁しているけど,あらゆる品目の満足度なんて知らないじゃないか.全品目を食べたことがあるならいざ知らず.それに,毎日同じ店で同じ食事をとるわけでもない.焼肉屋にしたって,湘南台には寅屋にえのもとにとあるわけだ.
 そういうわけで,あなたはいろいろな店に行き,いろいろな注文をして,なるべくどれを頼んでも満足度の高い食事のとれる店を見つけたいと考えた.しかしここで疑念が生まれる——いまの店でそこそこ満足できるなら,別の店を探さなくてもよいのではないか? しかしいまの店に行き続ける限り,別の店の食事を食べることはできないぞ.しかしそこがハズレだとしたら.さてどうしよう——業界用語でこれを探索利用のトレードオフ (exploration-exploitation tradeoff) という.

これまでの学習結果を利用 (exploitation) しようとすると,探索 (exploration) が減ってしまい,機会損失が増えてしまう.一方,探索を増やせば,学習した最良の行動とは異なる行動をとることが増えるため,得られる報酬が減ってしまう.学習した最良の行動との差が,探索のコストということになる.– 牧野,et al. 『これからの強化学習

 このトレードオフを解消する試みを多腕バンディット問題という.多腕バンディット問題は,複数のスロットマシンのレバー(腕)を次々と引いていき,最終的に得られる報酬を最大化するというもので,強化学習の一種といえる.各スロットマシンの報酬はそれぞれ一定の確率分布に従っている.言い換えれば,いろいろな店のメニューにある品目を試していき,最終的に得られる満足度を最大化していく,ということになる.もちろん,品目によって得られる満足度に違いはあるが,なるべく何を食べても満足度の高い店を絞り込んでいきたい.
 そのためのアルゴリズムのうち,ここでは$\epsilon$-GreedyとUCB1を紹介したい.

$\epsilon$-Greedy

 デフォルトで現在最良な選択肢を選ぶが,一定の確率でいま最良と思っていないような選択肢を選びにいく手法.

  • $\epsilon - 1$の確率で最適だと思われる選択肢を利用する
  • $\epsilon / 2$の確率で最適だと思われる選択肢を探索する
  • $\epsilon / 2$の確率で最悪だと思われる選択肢を探索する

 $\epsilon$ Greedyはつまり行きつけの店に入り浸るタイプのアルゴリズムだ.

UCB1

 それもいいが,実はいまの行きつけよりもっといい店なのに,一度行って微妙だったからといって行かないままになっている店がないだろうか? UCB1は,それぞれの店についてどれくらい知っているかを考慮に入れ,なるべく多くの店のことを知ろうとするアルゴリズムだ.具体的には,各店(腕)についてUCB (Upper Confidence Bound) という値を計算する.

 $\overline {x}_{j}+c\sqrt {\dfrac {2\log n} {x_{j}}}$

 ただし$\overline {x}_{j}$$_{j}$番目の店の満足度(報酬)の期待値,$n$はそれまでに店を回った回数の合計,$n_{j}$$_{j}$番目の店に行った回数,$c$は定数.UCB1は,この値が最大になる店に飛び込んでいく.あなたが好奇心旺盛なら,こちらのアルゴリズムを使って考えたほうがいいだろう.
 この手法のメリットとして,ベストでない店に行く回数を確率$1$$O(\log n)$以内に抑えられる.長々とした証明は論文を参照していただくとして,これは店に行く回数が十分大きい場合の理論限界に到達している.デメリットとしては,探索のためによくない店にあたってしまうことが多いという点が挙げられる.

実験

 では,$\epsilon$-GreedyとUCB1が最良の店を選ぶ過程はどうなっているだろうか? 『バンディットアルゴリズムによる最適化手法』のサンプルコードをPython3 + numpy向けに改変して実験.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
import pandas as pd
import numpy as np
import matplotlib.pyplot as plt
import random
import math
import seaborn as sns
class BernoulliArm():
def __init__(self, p):
self.p = p
def draw(self):
if random.random() > self.p:
return 0.0
else:
return 1.0
class EpsilonGreedy():
def __init__(self, epsilon, counts, values):
self.epsilon = epsilon
self.counts = counts
self.values = values
return
def initialize(self, n_arms):
self.counts = np.zeros(n_arms)
self.values = np.zeros(n_arms)
return
def select_arm(self):
if random.random() > self.epsilon:
return np.argmax(self.values)
else:
return np.random.randint(0, len(self.values))
def update(self, chosen_arm, reward):
self.counts[chosen_arm] += 1
n = self.counts[chosen_arm]
value = self.values[chosen_arm]
new_value = ((n-1) / float(n)) * value + (1 / float(n)) * reward
self.values[chosen_arm] = new_value
return
class UCB1():
def __init__(self, counts, values):
self.counts = counts
self.values = values
return
def initialize(self, n_arms):
self.counts = np.zeros(n_arms)
self.values = np.zeros(n_arms)
return
def select_arm(self):
n_arms = len(self.counts)
for arm in range(n_arms):
if self.counts[arm] == 0:
return arm
ucb_values = [0.0 for arm in range(n_arms)]
total_counts = sum(self.counts)
for arm in range(n_arms):
bonus = math.sqrt((2 * math.log(total_counts)) / float(self.counts[arm]))
ucb_values[arm] = self.values[arm] + bonus
return np.argmax(ucb_values)
def update(self, chosen_arm, reward):
self.counts[chosen_arm] = self.counts[chosen_arm] + 1
n = self.counts[chosen_arm]
value = self.values[chosen_arm]
new_value = ((n - 1) / float(n)) * value + (1 / float(n)) * reward
self.values[chosen_arm] = new_value
return
def test_algorithm(algo, arms, num_sims, horizon):
chosen_arms = np.zeros(num_sims * horizon)
rewards = np.zeros(num_sims * horizon)
cumulative_rewards = np.zeros(num_sims * horizon)
sim_nums = np.zeros(num_sims * horizon)
times = np.zeros(num_sims * horizon)
for sim in range(num_sims):
sim += 1
algo.initialize(len(arms))
for t in range(horizon):
t += 1
index = (sim - 1) * horizon + t - 1
sim_nums[index] = sim
times[index] = t
chosen_arm = algo.select_arm()
chosen_arms[index] = chosen_arm
reward = arms[chosen_arm].draw()
rewards[index] = reward
if t == 1:
cumulative_rewards[index] = reward
else:
cumulative_rewards[index] = cumulative_rewards[index - 1] + reward
algo.update(chosen_arm, reward)
return [sim_nums, times, chosen_arms, rewards, cumulative_rewards]
means = np.array([0.1, 0.1, 0.1, 0.1, 0.9])
n_arms = len(means) # 腕は5本
random.shuffle(means)
arms = [BernoulliArm(x) for x in means]
for epsilon in [0.1, 0.2, 0.3, 0.4, 0.5]: # epsilonを変えたらどうなるか?
algo = EpsilonGreedy(epsilon, [], [])
algo.initialize(n_arms)
results = test_algorithm(algo, arms, 5000, 500)
df = pd.DataFrame({"times": results[1], "rewards": results[3]})
grouped = df["rewards"].groupby(df["times"])
plt.plot(grouped.mean(), label="epsilon="+str(epsilon))
algo = UCB1([], [])
algo.initialize(n_arms)
results = test_algorithm(algo, arms, 5000, 500)
df = pd.DataFrame({"times": results[1], "rewards": results[3]})
grouped = df["rewards"].groupby(df["times"])
plt.plot(grouped.mean(), label="UCB1")
plt.legend(loc="best")
plt.show()

 好奇心旺盛な人は序盤それなりに苦労することがわかる.

おわりに

 こうしたナイーブな実装で焼肉の頼み方を最適化したり,店の巡り方を最適化できるかどうかというとまあ実際微妙(たとえば焼肉の各品目から得られる満足度は,限界効用逓減の法則に従ってすり減っていく)だが,日々の意思決定をアルゴリズム的に考えてみる遊びはそれなりにおもしろい.ソーシャルゲームにどう課金するか,というのもこの俎上に載せられる.
 『Algorithms to Live By: The Computer Science of Human Decisions』という本はそういう,情報系の人間がよくやる与太話をまじめに考察したものだ——書類はどのキャッシュアルゴリズムに従って並べるべきかとか.先に挙げた探索と利用のトレードオフについても述べられている.YouTubeで著者らの講演を観てほしい.

 はい.

参考文献

追記 (2016.12.06)

 今回のような設定では多腕バンディット問題というより最適腕識別として考えたほうがよさそう.多腕バンディット問題は累積報酬の最大化が目的だけれど,最適腕識別はどの腕が最良か発見するのが目的.将来の報酬が最大の腕を見つける,ということ.『バンディット問題の理論とアルゴリズム』を読めばいいんだとか.

はじめに

 サイバーセキュリティに携わる者なら一度くらいはKDD Cup 99 Dataなるデータセットの名を耳にしたことがあるのではないだろうか.KDD Cupは国際会議SIGKDDによるデータマイニングのコンペで,KDD Cup 99 Dataはそのためのネットワーク侵入検知にまつわるデータ.正常通信と攻撃を分類するタスクが与えられた.
 見てみよう.

データセットの構成

 データは現在,カリフォルニア大学アーバイン校によって配布されている.
 それぞれのファイル内容は下記の通り:

ファイル名 ファイル内容
kddcup.data フルデータ
kddcup.data_10_percent フルデータの10%を抽出した学習用データ
corrected 正常・攻撃のラベル付けがなされた評価用データ
kddcup.testdata.unlabeled 正常・攻撃のラベル付けがなされていないデータ
kddcup.testdata.unlabeled_10_percent 正常・攻撃のラベル付けがなされていないデータの10%サブセット
kddcup.newtestdata_10_percent_unlabeled 正常・攻撃のラベル付けがなされていないデータの10%サブセット

 ファイルの中身はこんな調子:

1
2
3
4
5
6
7
8
9
$ wget -r -l 1 http://kdd.ics.uci.edu/databases/kddcup99/
$ gunzip -r kdd.ics.uci.edu/kddcup99
$ ln -s kdd.ics.uci.edu/databases/kddcup99 kddcup99
$ head -5 kddcup99/kddcup.data
0,tcp,http,SF,215,45076,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,1,1,0.00,0.00,0.00,0.00,1.00,0.00,0.00,0,0,0.00,0.00,0.00,0.00,0.00,0.00,0.00,0.00,normal.
0,tcp,http,SF,162,4528,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,2,2,0.00,0.00,0.00,0.00,1.00,0.00,0.00,1,1,1.00,0.00,1.00,0.00,0.00,0.00,0.00,0.00,normal.
0,tcp,http,SF,236,1228,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,1,1,0.00,0.00,0.00,0.00,1.00,0.00,0.00,2,2,1.00,0.00,0.50,0.00,0.00,0.00,0.00,0.00,normal.
0,tcp,http,SF,233,2032,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,2,2,0.00,0.00,0.00,0.00,1.00,0.00,0.00,3,3,1.00,0.00,0.33,0.00,0.00,0.00,0.00,0.00,normal.
0,tcp,http,SF,239,486,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,3,3,0.00,0.00,0.00,0.00,1.00,0.00,0.00,4,4,1.00,0.00,0.25,0.00,0.00,0.00,0.00,0.00,normal.

 これは,ファイルの特徴をカンマ区切りで列挙したもの.列に特徴名を振れば,pandas(や,scikit-learn)での扱いも楽.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
>>> import pandas
>>>
>>> col_names = ["duration","protocol_type","service","flag","src_bytes",
... "dst_bytes","land","wrong_fragment","urgent","hot","num_failed_logins",
... "logged_in","num_compromised","root_shell","su_attempted","num_root",
... "num_file_creations","num_shells","num_access_files","num_outbound_cmds",
... "is_host_login","is_guest_login","count","srv_count","serror_rate",
... "srv_serror_rate","rerror_rate","srv_rerror_rate","same_srv_rate",
... "diff_srv_rate","srv_diff_host_rate","dst_host_count","dst_host_srv_count",
... "dst_host_same_srv_rate","dst_host_diff_srv_rate","dst_host_same_src_port_rate",
... "dst_host_srv_diff_host_rate","dst_host_serror_rate","dst_host_srv_serror_rate",
... "dst_host_rerror_rate","dst_host_srv_rerror_rate","label"]
>>>
>>> kdd_data_10percent = pandas.read_csv("kddcup99/kddcup.data_10_percent", header=None, names = col_names)

 学習用データは通常データ,22種類の攻撃データの計23種類のデータからなる.評価用データは,学習用データに加えて17種類の攻撃データを含んでいる.これらの攻撃は4つのクラスに大別される:

クラス 説明 サブクラス
Normal 通常のコネクション normal
Probe 攻撃対象の探索・調査 ipsweep, nmap, postsweep, satan, mscan, saint
DoS DoS攻撃 back, land, neptune, pod, smurf, teardrop, mailbomb, apache2, processtable, udpstorm
U2R ローカルマシンからrootへの許可されていないアクセス buffer.overflow, localmodule, perl, rootkit, httptunnel, xterm, ps, worm
R2L リモートマシンからの許可されていないアクセス ftp_write, guess_passwd, imap, multihop, phf, spy, warezclient, warezmaster, snmpgetattack, snmpguess, xsnoop, named, sendmail, sqlattack, xlock

 サブクラス名から古臭さがにじんでいるが,データセットは近年の研究でも広く用いられているものだ.まあ単純に同規模の新しいデータセットがないからだろう.
 だいたいの論文はkddcup.data_10_percentを用いて学習し,correctedを用いて評価するという流れになっている.
 ところで,このデータセットに付随したタスクは正常通信と攻撃の二値(まあ多値分類になりはするが)分類だが,これは異常検知とどう違うのだろうか.ものの本によると,二値分類はベイズ決定則(条件付き分布$p(x|y=1)p(y=1)$$p(x|y=0)p(y=0)$の比が1を超えたら異常と判定),異常検知はネイマン・ピアソン決定則($p(x|y=1)$$p(x|y=0)$の比がある閾値を超えたら異常と判定)にもとづいている.ここで,異常検知問題ではほとんどつねに$p(y=1)<<p(y=0)$であるため,ベイズ決定則は異常判定を強く抑制する.そういうわけで,標本の割合を吟味して二値分類器の閾値をスライドさせていくことが重要となってくるらしい.

データセット形式への変換

 tcpdump2gureKDDCup99は,Bro IDSのプラグインとして,おなじみのpcapファイルをKDD Cup 99 Dataのフォーマットに変換してくれる.Bro IDSはSnortには及ばずともそこそこ由緒あるIDSで,GitHubリポジトリは米国政府公式のリポジトリリストにも掲載されている.
 まずBro IDSをインストールする.

1
2
3
4
5
6
$ sudo apt-get install cmake make gcc g++ flex bison libpcap-dev libssl-dev python-dev swig zlib1g-dev
$ git clone --recursive git://git.bro.org/bro
$ cd bro
$ ./configure
$ make -j4
$ sudo make install

 私はpyenvからインストールしたPython 2.7.11を常用しているのだが,Bro IDSをmakeするにはCFLAGS="-fPIC" pyenv install 2.7.11のように共有ライブラリ用のオプションをつけてPythonを再インストールする必要があった.
 さてWireshark公式が公開しているサンプルデータをKDD Cup 99 Dataの形式に変換してみる.

1
2
3
4
5
6
7
8
9
10
11
$ cd
$ git clone git@github.com:inigoperona/tcpdump2gureKDDCup99
$ gcc tcpdump2gureKDDCup99/trafAld.c -o tcpdump2gureKDDCup99/trafAld.out
$ wget "https://wiki.wireshark.org/SampleCaptures?action=AttachFile&do=get&target=zlip-1.pcap" -O zlip-1.pcap
$ bro -r zlip-1.pcap tcpdump2gureKDDCup99/darpa2gurekddcup.bro > conn.list
$ cat conn.list
1 955453631.643199 1024 53 10.0.0.1 146.84.28.88 0.000000 udp 53 S0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
$ sort -n conn.list > conn_sort.list
$ tcpdump2gureKDDCup99/trafAld.out conn_sort.list
$ cat trafAld.list
1 955453631.643199 1024 53 10.0.0.1 146.84.28.88 0.000000 udp 53 S0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0 0 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000

 pcapファイルをPythonで分析したければそのまま(scapyや)pandasに突っ込むだろうけど,KDD Cup 99 Dataと比較したい場合には使えるかも.

おわりに

 名前は聞くけど触ったことないなということで.やらなければならない作業が進まないとこういう現実逃避が捗る捗る.

参考文献

 はい.


これはなに

 @img2cap fileという形式で画像を投げつけると説明文をつけ加えて返信するだけのTwitter bot.

しくみ

 CNN + LSTM.
 以下の論文や実装を参考にした.裏ではChainerが動いている.

 はじめは論文通りの活性化関数と勾配法を試してみたが,dsanno氏のいうようにSGDよりAdamの方が高速.MomentumSGDと比べてもみたが即Adam最高! という気分にさせられた.AdamがそもそもAdaGradとRMSPropのいいとこどりらしいので,その両者は試していない.なおネットワーク構成は論文のまま.
 データセットに含まれているのは写真8万枚とその説明文だけ.よってTwitterの各位がいくらイラストを投げつけようと無駄な話で,その手のニーズに対応するにはニコニコ静画のデータセットあたりを使う必要がありそう.これには画像とそのタグ,コメントを学習したモデルが含まれているそうだが,説明文の生成というタスクに向けてどう転移学習させるか目処は立っていない.
 当然ながら学習データと実際に各位が投げつけてくるデータの分布は全く異なるし,困ったものだ.

謝辞

 お遊びにGPU環境を貸してくれた@georgioush, @dasoran両氏に感謝.

 読書メモ.

はじめに

 人間の脳を模したニューラルネットの手法,深層学習ディープラーニングがめざましい成果を挙げている–といった謳い文句をよく目にする.だが機械学習の専門書を紐解いても出てくるのはロジスティック回帰のお化けばかり.
 われらがPRMLのニューラルネットを扱う章にはこうある.

しかしながら,パターン認識という実際的な応用の観点からは,生物学的な現実性などは全く不要な制約である.
                        – C.M.ビショップ『パターン認識と機械学習 上』 (p.226)

 では,機械学習の文脈で言うところのニューラルネットと脳はどれほど異なっているのだろうか?

ニューラルネットと脳の違い

 結論から言えば全然違うわけだが,ざっくり以下の三点から整理できる(と思う):

  • ニューロンのモデル
  • ネットワーク構造
  • 微分計算の手法

ニューロンのモデル

 現在広く普及している多層パーセプトロンは,単純な差分方程式であるMcCulloch-Pittsモデルをベースに,層を重ねたとき微分できるような活性化関数を組み合わせている.だがそれ以外にも膜電位が変動するメカニズムを考慮した:

  • Hodgkin-Huxleyモデル
  • FitzHugh-Nagumoモデル
  • Izhikevichモデル

などが提案されている–というようなことは機械学習の道具としてニューラルネットを扱っている本にはあまり書かれていない.ひとまず手元にあった:

はモデル名に言及しておらず,McCulloch-Pittsモデルを紹介していたのは:

だけだった.
 ちなみにこの中だと機械学習マジで何もわからんって人はまずサンプルコードを動かしながら『ITエンジニアのための機械学習理論入門』を読むとよい.深層学習については紫色の本が好み.青色の本は数式が追いにくい(どっちもどっちだが)上,深層学習以前と以後でどのような変遷があったのか不明瞭で,『進化計算と深層学習』は概論のみ.『イラストで学ぶディープラーニング』は読みやすく,汎化性能を向上させる方法も載っていて実践的ではあるが,RNNに触れられていないのが惜しい.
 さて,それではニューロンのモデルが複雑であれば脳に近いのかというと,どうやらそういうわけでもないらしい.たとえば複雑かつイオンコンダクタンスの挙動が緻密なHodgkin-Huxleyモデルは,ヤリイカの軸索のニューロンをモデル化したものだが,これはヒトの大脳皮質とはタイプが異なるようだ.
 しかし,McCulloch-Pittsモデルには,STDP (Spike Timing Dependent Plasticity, スパイク時刻依存シナプス可塑性) を表現できていないという問題点がある.STDPはニューロンの発火タイミングに応じて重みを更新する規則で,脳はこれにより時系列を学習しているとされる.
 こういったことを把握するためにいくつか神経科学の本を読んでみた.だいたいの書籍がまず最初にニューロンのモデルを紹介し,それからニューロンの同期に章を割き,つづいて脳の任意の部位の詳説という体裁をとっている.

など.全部読んだ感想としては『脳の計算論』が最も明快かつ簡潔で,STDPにも詳しく,この記事で触れている範囲のことはほぼカバーしている.
 Izhikevichモデルの考案者も『Dynamical Systems in Neuroscience: The Geometry of Excitability and Bursting』という本を書いているのだが,これは難しそう.
 本腰を入れて学ぶには「シナプス可塑性の初心者へ 推薦論文リスト」を消化すべきなのだろう.

ネットワーク構造

 パーセプトロンは小脳に,BESOMは大脳皮質に,畳み込みニューラルネットは受容野に,TD学習は大脳基底核に似ていると言われている.ではどこが.
 小脳についてはさきほど挙げた『脳の計算理論』がよい.この著者は小脳による運動の内部モデル獲得というテーマの大家だそうで,公開されている無料のPDFでその足跡が追える.Hodgkin-Huxleyモデルの解説も丁寧.あわせて“現代の小脳パーセプトロン仮説”も読みたい.
 大脳皮質についてはBESOMの人の「大脳皮質と deep learning の類似点と相違点」がとにかくわかりやすい.やはり正則化が重要なようだが,それについては「脳とネットワーク/The Swingy Brain:まとめてスパースコーディング - livedoor Blog(ブログ)」に挙げられている論文を読むとよさそう.
 さらなる部位との関連については,「全脳アーキテクチャ解明に向けて」から辿れる資料が親切だった.特に「海馬神経回路の機能ダイナミクス」で触れられている内容は元論文の古さとは裏腹にあまり書籍では見ない.

微分計算の手法

 みんな大好き誤差逆伝播法は脳では使われていない.じゃあどうすればいいかというと:

がある.後者2つは深層学習の大家であるBengioらの研究で,ここでSTDPが重要となってくるらしい.生物学的な妥当な深層学習まであと何年だろうか.

おわりに

 機械学習のことは多少わかるけど(計算論的)神経科学については何から勉強すればいいのかもわからないというところから,騙し騙しとはいえ論文を読める程度になるにはこのあたりを読むとよいのではないかと思います.
 なお,このブログに貼られているAmazonリンクはいずれも素のリンクです.ご安心ください.アフィリエイトリンクを貼りまくって小銭を稼ごうと画策しましたが審査に落ちました.

 本稿は慶應義塾大学SFC村井&徳田研 Advent Calendar 2015の19日目である.

TL;DR:

 村井研・徳田研の卒論・修論・博論アーカイブから過去の論文タイトルを収集し,RNNLM(Recurrent Neural Network Language Model, 再帰型ニューラルネット言語モデル)[1]を用いて論文タイトルを自動生成する.

手順

  1. 論文アーカイブを雑にスクレイピング.
  2. 簡単のため英語タイトルを削る.データサイズは540行・16294字.
  3. MeCabの-Owakatiオプションで分かち書き.単語数は6272と少ない.
  4. RNNLMで学習,出力.

 生成した論文タイトルは次の通り.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
改変適応機環境におけるインターネット化の設計と実装
暮らし計算発見を利用したUDL機器
インターネットを用いた機器プローブ体系のVoDについて開発な攻撃運用手法
自律計算ネットワークの行動に-移動システムに関する研究
衛星情報を用いたビジュアライゼーション定義アーキテクチャ表をする検出ユビキタスノードのファイル構成に関する研究
あしあと適応セキュリティネットワークを用いた負荷議事取り入れたセンサNEMOMANET解決
ユーザエンティティに適した仮想な通信接近による制御対象の設計と実装
蓄積学校利用性のための再作業に関する持続
型連携ネットワークのインターネットに基づく遠隔コードの向けたデジタル機構の構築
アプリケーション:型と時間特定を用いた利用型路準拠相関の構築
自律電話教育における異種品質空間支援システムの設計と実装
位置AV端末著作授業特殊トポロジ型し分析高速構築
広域を利用した次応用におけるレイヤーな授業に関する研究プロシステムに関する研究
次制御対するカメラを利用したAd型間屋外パブリック構築
協調:不sネットワークにおけるOSストリーミングの考慮機器コミュニケーション配信システムの設計と実装
センサ環境におけるデバイスソフトウェア文字通信システム
無線作業めぐるにおけるパケットIP発信・支援機構
ELA上環境に応じたしたコンピュータ測定に関する研究
インターネット型プラットホームの遠隔パケットとシステム
無線コントロールセンサを考慮する参加参加サービスの研究
移動者における位置適応オブジェクト手法の研究
インターネットグルーピングの回覧性をシステムした経路消耗性の実現
自己情報を用いた実を量子よる協調表行動流通
デジタル前遠隔しるしの情報共有支援機構
ネットワークト可視ネットワークを車的基盤」関数の分析
環境Computing通信DVB携帯性に関する移動同期利用の設計と実装
マルチパスFunction無線センサノードを用いた技術マルチ支援支援促進に関する研究
スマート世代ネットワークにおける相互ブリッジ家電システムの設計と実装
インターネット情報のための興味無支援システムの構築
オペレーティング型IP環境のプロファイリング的な信頼に関する研究
実方向自動ポロジにおける同期機器性における研究
センサ-抽出生成を支援情報登録抽出機構の構築
アドホックOSにおけるOS環境のGlass性基盤機構の構築
DV地アプリケーションの者による最適いアルゴリズム
商上のための選択なMobile効率システムの構築
ユビキタス世代環境における効率Wireless情報のMarkit
系列演奏位置スレッドサービス二マッチングマルチプロアクティブモデルの構築
パケット適応付け利用を考慮したネットワークブログモデルの設計と実装
TranS情報環境におけるグループホスト同期への安全履歴と分散
の情報対象でのMediatorコラボレーションに関する研究
類似Allシステム
情報グループを利用するデジタル制御動画像配送システムの構築
RFIDを利用したネットワークのプラットフォーム転送に関する研究
周辺上セキュリティにおけるコンテキスト者基無線の提案に関する研究
Link型服行動RCSにおける効率しない機構
クラシック型車載インターネットを解決した分散音声なりすましシステム
Dynamic特徴解析に基づく仮想制御機構の設計と実装
多段CSMAにおける多様な解析管理機構の設計と実装
移動機:を用いた-コンテンツシステムの構築
技術センサ環境におけるホーム化による経路サーバ
アプリケーション回線に基づく薦環境におけるする作成への行動利用に関する研究
インターネットを用いたしたな動画ルールに関する研究
機器協調利用Efficientのネットワーク解決のエンド映像構築
計算情報を利用した家電抽象の迷い連携への構築
関連情報教育における動的メールイベント収集の研究
通知におけるデータベース方式購買によるした状態時間グループに関する研究
コンテキスト:6のためのための設計と実装
電子ネットワークのための提案と実装
自己電話を利用したオブジェクト分散型授業属性制御機構の実現
ネットワークの抽出化環境の向上圧縮システムの構築
Networks対戦ネットワークにおける家庭テリトリー手法の構築
広バイト依存患者のための収集及び積極システム
IPコンテキスト精度点のデータベース的と-発見環境動画像モデル行動-
通信作業システムの含む属性センサノード付け可能メディアの提案と開発
情報世代環境時による最適視点環境機構の設計と実装
協調蓄積モバイルバッテリ支援Shumu機器型設置インシデントIrma保護量
分散回線にセンサデータ適応をマッチングと基準化に関する研究
環境さ時複数用方式と審議に関する研究
自律リンク環境におけるインターネット・属性品質
オブジェクトしにおけるインタフェース技法化推薦機構の研究
インターネットにおける光を用いた最適遠隔支援環境の構築
モーバイルs利用とへの実現自動手法の設計と実装
インターネットに適した時端末型TCP型データ基準の内
インターネットを用いた受信・辞書収集
DOS的利用環境におけるbased配信システムの構築
i:と利用した情報モーダルの作成に関する研究
APIの情報におけるソフトウェアするをシステムの自律
インターネットを用いたセル内回避手法アプリケーションFunction選択制御機構
マルチ:ユーザ時のLooking支援競合の参加情報に関する研究
マルチネットワークによる動的リモコンアーキテクチャの分析に関する研究
インターネット:文字を含むと対策軽減地理ファイルの構築
アプリケーションのデジタル行動環境における負荷教育の設計と実装
移動制御型メディア取り入れたにおける自律トポロジモデルの提案
日本回線時におけるセンサのアーキテクチャ
『世代sionを支援情報ユーザの実現
Mobileの行動空間に基づくするコンポーネントシステムの設計と構築
キットライブラリのアドレス利用を支援するアプリケーションの行動に関する研究
間:環境における認証検出の考察
鍵盤を用いた基盤経路トポロジ支援手法の研究
RFIDネットワークを用いたとユーザ
自律型機的な支援レイヤー手法の設計と実装
アドホックを用いたデジタル最適暗号システムの研究
WWW人IPvシステムの動的2を化フローインフォメーション配送化手法
次的機タフェース6システムの実現
IPレイヤーネットワークにおけるグループ取得遠隔システムに関する研究
二通信ユニバーサルにおける複数共有再についての研究
Tapirus上の情報的実現あるの構築
環境上における仮想指機構の構築
インターネットにおけるRFID経路エンドノードデータベース付けモデルの設計と実装
2回線学習への効率的型環境の提案と構築
...

 これはRNNLMが生成した論文タイトルを100件無作為抽出したもの.全リストはgistに置いている.この程度のデータサイズでRNNLMの性能を云々するのはいささか危うい気がするが,論文タイトルの末尾はえてして「~の構築」「~の研究」「~の実現」になるというルールを獲得できている,ということだろうか.
 同じデータセットから,ありがちな2単語プリフィックスのマルコフ連鎖で生成した論文タイトルは次の通り.

1
2
3
4
5
6
7
8
9
10
11
注目した二点間接続基盤ソフトウエアの構築インターネット
地域における高等教育協力手法の研究ホームネットワークにおける多様
かつスケーラブルな識別子管理システムゲームコンソールに対応する管理
運用基盤分析に関する研究ポリシ経路制御に関する研究大
任意の物理的量子ビットに対する効率的な情報閲覧
脳疲労検知システムの提案次世代インターネット経路制御を用い
鍵交換機構の実装と評価初等中等教育におけるWWW
プロセスデザイン片方向ブロードキャストメディアを用いたユビキタスコンピューティング環境に適し
連携システムの設計と実装exPhoto:周辺機器と撮影
に関する研究分散環境におけるプロアクティブ制御方式に関する研究アドホック
...

 パッと見でRNNLMが生成した論文タイトルの方がより自然に思える.で,RNNLMって何なの?

RNNLM

 読んで字のごとくRNNLMはRNNの言語モデルへの応用である.
 RNNは内部に有向閉路をもつニューラルネット.系列データの各時刻$t$につき1つの入力$x^t$をとり1つの出力$y^t$を返す.ふつう順伝播型ニューラルネットは入力1つをとり1つの入力を与える写像を表現するが,RNNは任意の系列–すなわち過去のすべての入力から任意の系列への写像を表現する.
 これは時刻$t-1$の隠れ層の出力を,時刻$t$の隠れ層の入力に与えることで実現される.

 文章は系列データであり,文章に含まれる各単語は直前の単語の並びに依存している.そこで,1990年のエルマンネット[2]以来,RNNを用いた文章の分析が試みられてきた–近頃「RNNは深層学習の一種」というような言辞を見かけるが,RNN$\in$深層学習ではない
 RNNLMと既存手法との相違点は,単語を潜在空間に写像して単語の意味を獲得しようとしているところだ.
 上図において隠れ層のベクトルは単語の潜在ベクトルとその履歴より$\begin{split}s(t) =& f(Uw(t) + Ws(t-1))\end{split}$となる.次の単語の確率は$\begin{split}y(t) =& g(Vs(t))\end{split}$となる.
 ここで活性化関数$f(z)$は標準シグモイド関数で,$g(z)$はソフトマックス関数$\dfrac {e^{zm}} {\Sigma _{k}e^{zm}}$である.
 学習では確率的勾配降下法を用いて重み$U$, $W$, $V$を更新していくが,このときRNNLMは各層を時間方向に展開し,最後の時刻$t$から誤差逆伝播計算をおこなう(BPTT, Backpropagation through time法).
 ここにおいてRNNは多層の順伝播型ニューラルネットのようにみなせる.

 BPTT法において,ある時刻$t$における出力層の誤差は正解ベクトル$d(t)$から出力$y(t)$を引いた出力誤差$e_{o}(t)$と,時刻$t+1$から伝播してきた誤差の和となる.ここでたとえば$V(t+1) = V(t) + s(t)e_{o}(t)^t\alpha - V(t)\beta$$\alpha$は学習率であり,各層で行列の勾配に掛かる.$\beta$はL2正則化の係数.
 このBPTT法で長い系列を扱うとき勾配が消失してしまう問題[3]があり,解決策としてLSTM(Long Short-Term Memory, 長・短期記憶)[4]が提案されているが,割愛する.
 なお今回のパラメータは次の通り.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
last probability of validation data: -441.610349
number of finished iterations: 14
current position in training data: 0
current probability of training data: -441.576456
save after processing # words: 0
# of training words: 6272
input layer size: 1295
hidden layer size: 200
compression layer size: 0
output layer size: 1096
direct connections: 0
direct order: 3
bptt: 6
bptt block: 10
vocabulary size: 1095
class size: 1
old classes: 0
independent sentences mode: 1
starting learning rate: 0.100000
current learning rate: 0.000195
learning rate decrease: 1

おわりに

 恥知らずのクソ野郎なので何番煎じともわからない記事を書いてしまった.元ネタはNLP論文ネタ一覧
 このほか青空文庫やなろう小説[5]をRNNに学習させてはいるが,LSTM込みでもいまだ人間が見て自然に思える文章の生成は難しく思える.
 いずれは論文タイトルばかりか論文の内容も自動生成して知の欺瞞をもう一発カマしたいのだが.SFC自体が知の欺瞞っぽいところはさておき.
 物語の自動生成なら円城塔がなんとかしてくれるだろう.

参考文献