2016.08.25
機械学習のためのベイズ最適化入門
応用範囲が広く幅広い視点からの説明になりがちなベイズ最適化について、本記事では機械学習のハイパーパラメータ探索に利用することに限定して説明しどのように利用できるのかを解説します。
1. はじめに
最近、ベイズ最適化という手法が注目を集めています。 ベイズ最適化 (Bayesian Optimization) とは、形状がわからない関数 (ブラックボックス関数) の最大値 (または最小値) を求めるための手法です。 ベイズ最適化についての入門記事は Web 上にすでにいくつかありますが、ベイズ最適化は応用範囲が広く、入門記事は様々な応用に向けた幅広い視点からの説明になりがちです。 本記事では、機械学習ユーザに向けて、ベイズ最適化を機械学習のハイパーパラメータ探索に利用することに限定して説明します。 これにより、機械学習に対して、ベイズ最適化がどのように利用できるのかを分かりやすく解説したいと思います。
2. ハイパーパラメータ探索
機械学習の手法には、必ずと言ってよいほどハイパーパラメータが存在します。 ハイパーパラメータとは、機械学習手法が持つパラメータの中で、データからの学習では決まらないパラメータのことを言います。 例えば、サポートベクターマシン (SVM) における、誤分類に対するペナルティの大きさを制御するパラメータや、ランダムフォレストにおける、個々の決定木に使う特徴量の数などです。 これらのパラメータは、データを学習する前にあらかじめ決めておかなければなりません。
このようなハイパーパラメータは、これぐらいの値が良いなどの知見がある場合にはそれを使うこともありますが、精度の良い機械学習モデルを作成したい場合には、いくつかのハイパーパラメータを使って実際にモデルを学習してみて、一番精度が良くなるものを使うということが行われます。
このように、機械学習で良い精度を出すために、良いハイパーパラメータの値を探すことを、ハイパーパラメータ探索と言います。
3. グリッドサーチ
機械学習のハイパーパラメータ探索の方法として、グリッドサーチという手法がよく使われます。 グリッドサーチとは、ハイパーパラメータの探索空間を格子状 (グリッド) に区切り、交点となるハイパーパラメータの組み合わせについて、すべて調べるという方法です。
具体的な例を見てみましょう。 いま、機械学習手法として、RBF カーネルを用いた SVM を使用するとします。 RBF カーネルを用いた SVM には2つのハイパーパラメータがあります。 誤分類に対するペナルティの大きさを制御する C と、RBF カーネルのバンド幅を制御する gamma です。
これらのハイパーパラメータについて、C の探索範囲を [10-4, 105], gamma の探索範囲を [10-5, 104] とし、10 × 10 の次のような格子を作成します。
C_range <- 10 ^ seq(-4, 5, length.out = 10) gamma_range <- 10 ^ seq(-5, 4, length.out = 10) grid <- expand.grid(C = C_range, gamma = gamma_range) library(ggplot2) ggplot(grid, aes(x = C, y = gamma)) + geom_point() + scale_x_log10() + scale_y_log10()
これら1つひとつの格子点に対して、モデルを学習していきます。 今回は、有名な iris データセットを使って「あやめの品種」を分類するモデルを作ることにします。 SVM のグリッドサーチは、e1071 パッケージの tune.svm() によって簡単に実行できます。 ここでは、モデルの評価方法として 10-fold 交差検証を使っています。
library(e1071)
set.seed(71)
# SVM に対するグリッドサーチの実行
tune_result <- tune.svm(Species ~ ., data = iris, scale = TRUE,
gamma = gamma_range, cost = C_range,
tunecontrol = tune.control(sampling = "cross", cross = 10))
# 結果の表示
ggplot(tune_result$performances, aes(x = cost, y = gamma)) +
geom_point(aes(size = 1-error)) +
scale_x_log10() + scale_y_log10() + xlab("C") +
guides(size = guide_legend(title = "正答率", reverse = TRUE))
上の図では、正答率の高いものほど大きい丸で表しています。 このように、すべての格子点 (ハイパーパラメータの組み合わせ) でモデルを作り、 最も良い評価値となるハイパーパラメータを選択するというのがグリッドサーチです。
# 最適なハイパーパラメータ tune_result$best.parameters # そのときの正答率 1 - tune_result$best.performance
今回のグリッドサーチで求まった最適なハイパーパラメータは C = 10, gamma = 0.1 であり、そのときの正答率は 0.973 でした。
4. ベイズ最適化
ベイズ最適化を使うと、機械学習のハイパーパラメータ探索を効率よく行うことができます。
上記のグリッドサーチの例において、次の図のように4つの点で評価値が分かっているとします。
このとき、最大値を効率よく見つけるためには次にどこを調べたらよいでしょうか？ なんとなく右下あたりを調べた方が良さそうだと感じないでしょうか。 また、真ん中あたりがスカスカなので、このあたりを調べてみないとよく分からないと思うのも自然だと思います。
まずは真ん中あたりを1つ評価し、評価値が小さければ右下を重点的に調べればよく、大きければ探索範囲を広げたほうがいいというふうに、1つ評価を行っては次にどこを調べるかを決めるというような探索を、人間は自然に行うことができます。
これと同じ様に、すでに持っている情報から、次にどの点を調べた方がいいかを判断し、実際に評価を行い、その結果を次の判断に利用するということを自動的に行ってくれるのがベイズ最適化です。 これにより、すべての点を評価しなくても、効率的に最適値にたどり着くことができます。
実際に、上記の例において、グリッドサーチではなく、ベイズ最適化を使ってハイパーパラメータ探索を行ってみます。
このように、ベイズ最適化では、評価値が大きくなりそうなところを重点的に観測し、逆に小さくなりそうなところは観測しません。 また、あまり観測されていないエリアに対して時々観測を行い、局所解におちいるのを防ぐ動きをします。 今回、10 × 10 = 100 のグリッドに対して、50 回しか評価を行っていませんが、見事に最適値にたどり着いています。 グリッドサーチに比べて、ベイズ最適化ではモデルを評価する回数を半分に抑えることができました。
5. 獲得関数
ベイズ最適化では、すでに持っている情報から、次にどの点を調べたらよいかを自動的に判断します。 その判断を決める戦略として、色々なものが考えられます。
いま、すでに評価した中で最も高い評価値を ybest とします。 このとき、すべての未評価点に対して、評価値が ybest を超える確率を計算し、それが最も高い点を次に調べるというのはどうでしょうか？ これは、Probability of Improvement (改善確率; PI) と呼ばれる戦略です。 これにより評価値の低い点を観測することを避け、なるべく高くなりそうな点を選んで観測できます。
PI 戦略では評価値が高くなる確率を考えましたが、ybest がどれくらい改善されるかについては気にしません。 どんなに確率が高くても ybest がほんのちょっとずつしか改善されないとしたら効率的とは言えません。 そこで、すべての未評価点に対して、評価値とベストの差 y - ybest の期待値を予測し、それが最も大きくなる点を次に調べるというのはどうでしょうか？ これは、Expected Improvement (期待改善量; EI) と呼ばれる戦略です。 PI がしばしば局所解におちいるのに比べ、EI は最適解にたどり着きやすいことが経験的に知られています。1
最近注目されているのは、Upper Confidence Bound (上側信頼限界; UCB) という戦略です。 これは、すべての未評価点に対して、評価値の信頼区間の上限を計算し、それが最も高い点を次に調べるというものです。 EI は最適解へとたどり着く理論的保証は無かったのですが、UCB はある条件のもとで最適解へと収束していくことが理論的に保証されています。2
このように、ベイズ最適化では、ある関数を定め、その関数が最大となる点を次に調べることで解の探索を自動化します。
・ PI(x) = 評価値が現在のベストより高くなる確率
・ EI(x) = 評価値と現在のベストの差の期待値
・ UCB(x) = 評価値の信頼区間の上限
このような関数を獲得関数 (Acquisition Function) と言います。 ベイズ最適化の性能は、どの獲得関数を選択するかによって大きく左右されます。 そのため、どの獲得関数を使うかは非常に重要です。 ここに挙げたもの以外にも、様々な獲得関数が提案されています。
6. ガウス過程
「5. 獲得関数」では、未評価点における評価値の確率、期待値、信頼区間などを計算できるという前提で話を進めました。 しかし、実際には、最適化したい関数は形状がよく分からないため、そのような計算はできません。 ベイズ最適化では、未評価点における評価値の確率や信頼区間を計算するために、最適化したい関数がなんらかの確率過程に従うという仮定を置きます。 この確率過程としてよく使われるのが、ガウス過程 (Gaussian Process) です。
関数が確率過程に従うと言われてもあまりイメージがわかないかもしれません。 具体的な例を見てみましょう。 いま、1変数の形の分からない関数 y = f(x) に対して、次の5点の観測値が分かっているとします。
x y 1 0.1 0.08 2 0.4 -0.30 3 0.5 -0.48 4 0.7 0.46 5 0.9 0.37
このとき、関数がガウス過程に従うとすると、関数の形はだいたい次の形に定まります。
ガウス過程は、関数の形状を確率分布によって表現します。 上の図において、黒い点は観測値であり、関数がそこを通ることは確定しています3。 青い線は関数が通る確率が最も高い値を示しています。 そして、赤い点線は、青い線を中心として、95% の確率でこの範囲内を通ることを示しています。 上の図において、入力 x を一つ固定したとき、すなわち、上のグラフに垂直線を引いたとき、その断面は確率分布となっています。 この断面の確率分布がガウス分布 (正規分布) となることが、ガウス過程と呼ばれるゆえんです。
このように、関数がガウス過程に従うと仮定することによって、未観測な点に対して、その点における観測値の分布が決まります。 これにより、未観測な点における観測値の期待値や信頼区間などを計算することができるようになります。 これを利用すれば獲得関数が計算できるというわけです。
ただし、ガウス過程を使用するためには、共分散を決定するためのカーネル関数を選択する必要があります。 ベイズ最適化でよく使われるカーネル関数として、次が挙げられます。
Squared Exponential:
Matern:
ここで、d = x - x' です。詳しくは Usual covariance functions - Gaussian process - Wikipedia を参照してください。
ベイズ最適化の性能は、どのカーネル関数を選ぶかによっても変わります。 カーネル関数の選択は、獲得関数の選択と同じように重要です。
7. R言語による実装
それでは、実際に R言語で実装してみます。 今回は、獲得関数として Upper Confidence Bound を、カーネル関数として Squared Exponential を選択します。 ガウス過程の計算には、GPfit パッケージを使っています。
library(e1071) # SVM のため
library(GPfit) # ガウス過程のため
# グリッドの作成
C_range <- 10 ^ seq(-4, 5, length.out = 10)
gamma_range <- 10 ^ seq(-5, 4, length.out = 10)
grid <- expand.grid(C = C_range, gamma = gamma_range)
scaled_grid <- scale(log10(grid), c(-4, -5), c(9, 9))
# 目的関数(最適化したい関数)の定義
obj_func <- function(C, gamma) {
tune_result <- tune.svm(Species ~ ., data = iris, scale = TRUE,
gamma = gamma, cost = C,
tunecontrol = tune.control(sampling = "cross", cross = 10))
accuracy <- 1 - tune_result$best.performance
accuracy
}
# 獲得関数の定義 (Upper Confidence Bound)
acq_func <- function(mu, var, k) {
acqs <- mu + k * sqrt(var)
which.max(acqs)
}
# 初期値の設定 (四隅がすでに観測されている)
set.seed(2)
inds <- c(1, 10, 91, 100)
ys <- c(0.26, 0.966, 0.226, 0.233)
# 観測点が 30 になるまで繰り返す
for (i in 1:26) {
# ガウス過程により評価値の分布を計算
gp <- GP_fit(scaled_grid[inds, ], ys, corr = list(type = "exponential", power = 2))
pred <- predict.GP(gp, scaled_grid)
# 獲得関数により次の観測点を計算
next_ind <- acq_func(pred$Y_hat, pred$MSE, k = 3)
next_y <- do.call(obj_func, args = as.list(grid[next_ind,]))
# 結果の更新
inds <- c(inds, next_ind)
ys <- c(ys, next_y)
}
# 最適点と評価値の表示
grid[inds[which.max(ys)], ]
max(ys)
最適なパラメータは C = 10, gamma = 0.1, その時の評価値は 0.973 となりました。 グリッドサーチのときと結果が少し異なりますが、これは交差検証におけるデータ分割がランダムに行われるためです。
今回は 30 回の評価で最適値までたどり着いています。 評価回数はグリッドサーチの 1/3 以下となりました。
8. まとめ
本記事では、機械学習ユーザに向けて、ベイズ最適化の基本的な部分を解説しました。
ベイズ最適化は次のような場合に有効な手法です。
・機械学習モデルの評価 (計算) に時間がかかる
・グリッドサーチを行うときのグリッド数が多い
ベイズ最適化では、計算に時間がかかる関数の最適解を効率よく探索するために、計算時間の短い獲得関数の最大化を何度も行います。 したがって、そもそも最適化したい関数の計算時間が短い場合は、ガウス過程の計算などにかかる時間を考えると、適用には不向きです。
ベイズ最適化が有効となるのは、機械学習のハイパーパラメータの数が多い場合です。 ハイパーパラメータの数が多いと、探索空間の次元が大きくなり、グリッドサーチを行うには計算時間がかかりすぎてしまうからです。4
最近流行のディープラーニングでは、ハイパーパラメータの数が多いため、ベイズ最適化の適用が盛んに行われています。 しかし、探索空間が高次元になりすぎると、獲得関数の最大化にも時間がかかりすぎてしまうため、今回紹介したような単純な方法ではうまくいきません。 こうした問題を解決するため、ベイズ最適化の研究は現在も活発に行われています。
1 Roman Garnett. Bayesian Methods in Machine Learning. Lecture Notes 12.
2 Srinivas, N., Krause, A., Kakade, S., and Seeger, M. Information-theoretic regret bounds for Gaussian process optimization in the bandit setting. IEEE Transactions on Information Theory, 58(5):3250-3265, 2012.
3 実際はある点における関数の値は分散 σ2 でばらつくことが許されます。
4 例えば、4つハイパーパラメータがあり、各パラメータに対して10点ずつ調べようとすると、10 × 10 × 10 × 10 = 10,000点の計算が必要になります。