Scala で実装する機械学習入門
Let’s try machine learning algorithms with Scala
無線部開発班
2014 年 12 月 17 日
1
はじめに
本稿では、K 近傍法、ニューラルネットワーク、サポートベクターマシンといった代表的な機械学習の
アルゴリズムを Scala で実装する。機械学習はこれが全てではないが、感覚を掴む上では有用となろう。
2
K 近傍法
K 近傍法は、あるデータの近傍にある他の k 個のデータに多数決を取ってもらい分類する手法である。
最も単純な機械学習アルゴリズムのひとつであるが、事前の学習作業が不要で、遅延学習とも呼ばれる。
✞
☎
case class Data ( point : Seq [ Double ] , label : Any = 0)
class KNN ( k : Int , trains : Seq [ Data ] , distance : ( Data , Data ) = > Double ) {
def predict ( target : Data ): Any = {
val knears = trains . sortWith (( t1 , t2 ) = > {
val d1 = distance ( t1 , target )
val d2 = distance ( t2 , target )
d1 > d2
}). take ( k ). map ( _ . label )
val labels = knears . toSet
val counts = labels . map ( label = > label -> knears . count ( _ == label ))
counts . maxBy ( tuple = > tuple . _2 ). _1
}
}
✝
✆
k の値は利用者が適切に設定する。また、データ間の距離を定義する関数 distance も忘れず設定する。
その上で、訓練データ trains を分類器に渡す。predict メソッドを呼び出すと、全ての訓練データを
スキャンして距離を求め、最も近い k 個の訓練データを取り出して多数決を取る。なお、実際は距離に
応じた発言権の重み付けが必要である。また、分類するたびに全ての訓練データとの距離を求めるのは
計算量の点で不利である。少なくとも、使いどころには注意を要するクラス分類手法と言えよう。
3
ニューラルネットワーク
ニューラルネットワークは脳神経の仕組みをエミュレートした数学モデルで、最も歴史の長い機械学習
アルゴリズムのひとつである。今回はその中でも、入力から出力へと一方向に信号が伝搬し、途中で
ループしないフィードフォワード型のニューラルネットワークを実装する。形式的に説明すると難しく
思われるが、非常に単純なアルゴリズムである。分厚い教科書を購入する前に、まずは感覚を掴もう。
3.1
単純パーセプトロン
単純パーセプトロンは最も単純なニューラルネットワークである。何のことはない。n 個の入力 xk の
それぞれに重み wk を付けて合計した値に活性化関数 f を適用するだけである (式 (1))。Fig. 1 を見よ。
(
y = f (w · x) = f
w0 +
n
∑
k=1
2
)
wk xk
(1)
1
x1
x2
w0
w1
w2
xn
wn
Σ
activator
function
Fig. 1 single layer perceptron.
活性化関数とは、実数値の入力を受け取って、閾値以上なら ON、閾値未満なら OFF に分類する関数の
ことだと理解すれば今のところは差し支えない。パーセプトロンの入力は実数値であり、その重み付け
線型和を使ってクラス分類をしたいなら、真偽値に変換しなければならない。そのために活性化関数が
必要になる。これで本当に分類できるのか気になるところだが、先に学習の仕組みを見ておこう。
w′ = w − η||youtput − yanswer ||
(2)
パーセプトロンの学習の基本的な考え方は、パーセプトロンが分類した結果 youtput と正解 yanswer の
乖離が少なくなるように重み w を修正していくことである。では、さっそく実装してみよう。
✞
class Perceptron ( trains : Seq [( Seq [ Double ] , Boolean )] , dim : Int ) {
val weights = new Array [ Double ]( dim + 1)
val ratio = 0.1
for ( step <- 1 to 1024) trains . foreach { case ( in , out ) = > {
predict ( in ) match {
case true if ! out = >
for ( k <- 0 until dim ) weights ( k + 1) -= ratio * in ( k )
weights (0) -= ratio * 1
case false if out = >
for ( k <- 0 until dim ) weights ( k + 1) += ratio * in ( k )
weights (0) += ratio * 1
case _ = >
}
}}
def predict ( in : Seq [ Double ]) = ((1.0 +: in ) zip weights ). map {
case (i , w ) = > i * w
}. sum >= 0
}
✝
☎
✆
weights は入力データの次元数 dim よりも 1 次元大きい。これは、定数項を扱うための工夫で、
weights(0) が定数項に該当する。ratio は学習率 η で、適当に設定する。論理和を学習させてみよう。
✞
☎
val trainingData = Seq (
( Seq (0.0 , 0.0) , false ) ,
( Seq (0.0 , 1.0) , true ) ,
( Seq (1.0 , 0.0) , true ) ,
( Seq (1.0 , 1.0) , true ))
val p = new Perceptron ( trainingData , 2);
✝
predict メソッドに適当なベクトルを入力すれば、true か false かを判断してくれるはずだ。
3
✆
✞
☎
println ( p . predict ( Seq (0.0 , 1.0))) // true
println ( p . predict ( Seq (1.0 , 0.0))) // true
✝
✆
実のところ、パーセプトロンとは、true か false かを判定するための決定境界を学習する機械である。
例えば、論理和の場合は、Fig. 2 のような直線を決定境界として学習する。直線よりも上側は真になる。
Fig. 2 decision boundary of OR operation.
本当にこのような直線を学習しているか確かめるには、weights を出力してみればよい。
✞
☎
println ( p . weights . mkString ( " ," )) // -0.1 ,0.1 ,0.1
✝
✆
論理和と同じ要領で論理積を学習させることも可能だ。しかし、排他的論理和の学習は必ず失敗する。
✞
☎
val trainingData = Seq (
( Seq (0.0 , 0.0) , false ) ,
( Seq (0.0 , 1.0) , true ) ,
( Seq (1.0 , 0.0) , true ) ,
( Seq (1.0 , 1.0) , false ))
val p = new Perceptron ( trainingData , 2)
✝
✆
考えてみれば当たり前の話で、排他的論理和の真の領域と偽の領域は直線で分離することができない。
単純パーセプトロンは決定境界が直線 (超平面) になる問題でしか役に立たない。決定境界が超平面な
問題を線型分離可能と呼ぶ。論理和や論理積は線型分離可能だが、排他的論理和は線型分離不能である。
3.2
多層パーセプトロン
input
x1
y0
hidden layer
x2
y1
x3
y2
output
x4
y3
Fig. 3 multi layer perceptron.
4
x5
y4
Fig. 3 に示す多層パーセプトロンはパーセプトロンを何層にも重ねたニューラルネットワークである。
線型分離不能な問題にも対応しており、汎用的に使うことができる。今回は入力層、中間層、出力層の
3 層パーセプトロンを実装しよう。入力層から中間層へ信号を伝達する hidden メソッドと中間層から
出力層へ伝達する output メソッドを定義する。I は入力層、H は中間層、O は出力層の次元数である。
✞
☎
import scala . collection . mutable . Map
class
val
val
val
BP ( trains : Seq [( Seq [ Double ] , Seq [ Double ])] , I : Int , H : Int , O : Int ) {
w1 = Map [( Int , Int ) , Double ]()
w2 = Map [( Int , Int ) , Double ]()
ratio = 0.1
def hidden ( args : Seq [ Double ]): Seq [ Double ] = {
val hid = new Array [ Double ]( H )
for ( i <- 0 until I ; h <- 0 until H ) hid ( h ) += w1 (( i , h )) * args ( i )
for ( h <- 0 until H ) hid ( h ) = sigmoid ( hid ( h ))
hid
}
✝
def output ( args : Seq [ Double ]): Seq [ Double ] = {
val out = new Array [ Double ]( O )
for ( h <- 0 until H ; o <- 0 until O ) out ( o ) += w2 (( h , o )) * args ( h )
for ( o <- 0 until O ) out ( o ) = sigmoid ( out ( o ))
out
}
✆
入力層から中間層への伝達では IH 個の重みが必要だ。中間層から出力層への伝達では HO 個の重みが
必要である。今回は Map で重みを表現する。なお、sigmoid というメソッドを呼び出しているが、
sigmoid(x) =
1
1 + e−x
(3)
となるように定義する。実はこのシグモイド関数は Fig. 1 の活性化関数に相当する関数で、階段関数を
連続関数で近似したようなグラフを描く。Fig. 4 に示すように、0 と 1 の間の緩やかな階段になる。
Fig. 4 sigmoid function.
✞
✝
☎
def sigmoid ( x : Double ) = 1.0 / (1.0 + Math . exp ( - x ))
5
✆
ついでに、入力ベクトルを受け取って出力ベクトルを計算する predict メソッドを定義しておこう。
✞
✝
☎
def predict ( input : Seq [ Double ]) = output ( hidden ( input ))
✆
以上で多層パーセプトロンはクラス分類できるようになった。問題は、どうやって重みを学習させるか
である。ここで、誤差逆伝搬法を導入する。最終段の出力 youtput と正解 yanswer との二乗誤差 E を
E = ||yanswer − youtput ||2
(4)
ij
で定義する。第 n 番目の層で、ノード i からノード j への経路 (i → j) の重み wn
を最適化することを
ij
考える。二乗誤差 E が最小になる重み wn
を見つければ良いので、勾配法、特に最急降下法を用いる。
wn′ij = wnij − η
∂E
(5)
∂wnij
合成関数の微分の公式を用いて式 (5) を展開すると、
∂E
∂wnij
∂E ∂nij
n
=
∂nij
n
∂wnij
=
∂E
∂nij
n
xin
(6)
ij i
ただし、xjn は第 n 層の入力 xn の i 次元目で、nij
n は経路 (i → j) の寄与 wn xn である。
∂E
∂nij
n
=
∂E ∂ynj
∂ynj
∂nij
n
=
∂E
∂
∂ynj
∂nij
n
sigmoid(nij
n)
(7)
シグモイド関数の定義式 (3) を思い出そう。
sigmoid(nij
n) =
1
ij
1 + e−nn
(8)
第 n 層の出力 yn の j 次元目を ynj と定義すると、
e−nn
ij
∂
sigmoid(nij
n)
∂nij
n
=
ij
(1 + e−nn )2
= ynj (1 − ynj )
(9)
ここから、第 n + 1 層から第 n 層への誤差逆伝搬の漸化式を導出することができる。
∂E
∂ynj
=
K
jk
∑
∂E ∂nn+1
jk
∂ynj
k=1 ∂nn+1
=
K
∑
∂E k
jk
k
yn+1 (1 − yn+1
)wn+1
k
∂y
n+1
k=1
(10)
漸化式 (10) の境界条件として、最終段での二乗誤差を用いる。
∂E
j
∂youtput
j
j
= 2(youtput
− yanswer
)
(11)
この最終段の二乗誤差の勾配が出力側から入力側へと漸化式 (10) に従って伝搬していく様子が朧げに
想像できるだろうか。数式を並べた解説は以上で終わりということにして、さっそく実装してみよう。
✞
✝
☎
for ( i <- 0 until I ; h <- 0 until H ) w1 (( i , h )) = 2 * Math . random - 1
for ( h <- 0 until H ; o <- 0 until O ) w2 (( h , o )) = 2 * Math . random - 1
重みを乱数で初期化する作業を忘れずに入れておこう。全ての重みが 0 だと誤差が逆伝搬できない。
6
✆
✞
☎
for ( step <- 1 to 1024) trains . foreach { case ( input , ans ) = > {
val hid = hidden ( input )
val out = output ( hid )
for ( h <- 0 until H ) {
// from output layer to hidden layer
val e2 = for ( o <- 0 until O ) yield ans ( o ) - out ( o )
val g2 = for ( o <- 0 until O ) yield out ( o ) * (1 - out ( o )) * e2 ( o )
for ( o <- 0 until O ) w2 (( h , o )) += ratio * g2 ( o ) * hid ( h )
// from hidden layer to input layer
val e1 = for ( o <- 0 until O ) yield g2 ( o ) * w2 (( h , o ))
val g1 = for ( i <- 0 until I ) yield hid ( h ) * (1 - hid ( h )) * e1 . sum
for ( i <- 0 until I ) w1 (( i , h )) += ratio * g1 ( i ) * input ( i )
}
}}
}
✝
✆
以上で多層パーセプトロンが完成した。三角関数など直線でない関数を境界に持つ訓練データを試すと
面白い。ニューラルネットワークは近年再び脚光を浴びている分野である。実装しても損はなかろう。
4
サポートベクターマシン
サポートベクターマシンは、正集団と負集団を分離する識別直線を学習する機械である。Fig. 5 を見よ。
Fig. 5 support vector machine.
サポートベクターマシンが学習するのは単なる決定境界ではない。正集団と負集団からの最短距離 d が
最大になる直線を学習するのである。仮に現在知られている訓練データよりも境界に近い部分に未知の
データが出現した場合でも、他方の集団に誤って分類される危険性は低くなる、という期待ができる。
既にお気付きの方もいるかもしれないが、これは制約付き最大値問題である。点 (xi , yi ) の制約条件は、
|axi + byi + c| ≥ 1
(12)
ただし、a, b, c は識別直線の係数で、任意の実数値である。集団と識別直線との最短距離は
min d(xi , yi ) = min
|axi + byi + c|
1
√
=√
2
2
2
a +b
a + b2
7
(13)
あとはラグランジュの未定乗数法を利用して a2 + b2 を最小化するだけである。正解を ti = ±1 として
F (a, b, c, λ) =
N
∑
1 2
(a + b2 ) −
λi {ti (axi + byi + c) − 1}
2
i=1
(14)
a, b, c で偏微分することにより、最短距離 d が最大になる条件が求まる。
a=
N
∑
λi ti xi , b =
i=1
N
∑
λi ti yi , 0 =
i=1
N
∑
λi ti
(15)
i=1
以上より、
F (a, b, c, λ) =
N
∑
i=1
λi
1−
N
1∑
2
j=1
λj ti tj (xi xj + yi yj )
(16)
あとは式 (16) の極値を求めるわけだが、ここで学習率 η の最急降下法を用いる。
λ′i = λi − η
∂F (λi )
∂λi
(17)
式 (16) を λi で偏微分すると、
N
∑
∂F (λi )
=1−
λi ti tj (xi xj + yi yj )
∂λi
i=1
(18)
サポートベクターマシンの数式による導出は以上である。さっそく実装してみよう。
✞
☎
case class Data ( x : Double , y : Double , t : Int ) // t is +1 or -1
class SVM ( trains : Seq [ Data ] , kernel : ( Data , Data ) = > Double ) {
val L = new Array [ Double ]( trains . size )
var (a , b , c ) = (0.0 , 0.0 , 0.0)
for ( step <- 1 to 1024; i <- 0 until trains . size ) {
var dL = 1.0
for ( j <- 0 until trains . size ) {
if ( trains ( i ). t == trains ( j ). t ) {
dL -= L ( j ) * kernel ( trains ( i ) , trains ( j ))
} else {
dL += L ( j ) * kernel ( trains ( i ) , trains ( j ))
}
}
L ( i ) = Math . max (0 , L ( i ) + 0.05 * dL )
}
for ( i <- 0 until trains . size ) if ( L ( i ) > 0.00001) {
a += L ( i ) * trains ( i ). t * trains ( i ). x
b += L ( i ) * trains ( i ). t * trains ( i ). y
c += L ( i ) * trains ( i ). t
}
}
✝
✆
8
© Copyright 2024 ExpyDoc
