ハイパーパラメータ最適化のハイパーパラメータ最適化のハイパーパラメータ最適化

2022/12/11 0:10追記:スマホ環境下で全ての数式およびテキストの一部が表示されていない現象を確認したため修正しました.

この記事は, Acompany Advent Calendar 2022 10日目 の記事です.

昨年度はOPTIMINDさんとのコラボでしたが,今年度はAcompany単体でのAdvent Calendarとなりました.弊社単体で全日程を埋められるだけ会社が成長したのは嬉しい限りですが,私の所属が一意に定まってしまうようになったのは悲しいです.

はじめに

最適化は非常に便利なものです.ヒトは生きていく中で「〇〇を良くしたい」という願望を頻繁に抱くと思います.こういった抽象的な欲望を解決する1つの手段が最適化です.
コンピュータ上で最適化をする手段として様々なアルゴリズムが提案されていますが,それらの多くにはハイパーパラメータと呼ばれるパラメータが存在します.しかし,ハイパーパラメータは最適化アルゴリズムの性能を左右する重大なパラメータでありながら,通常最適なハイパーパラメータを人力で導出するのは困難です.そこで一般に行われるのがハイパーパラメータ最適化です.
最適化アルゴリズムのハイパーパラメータを最適化するということですが,ハイパーパラメータを最適化するアルゴリズムのハイパーパラメータはどのように決定するのでしょうか?これも最適化したくなりませんか?更に最適化アルゴリズムのハイパーパラメータを最適化するアルゴリズムのハイパーパラメータを最適化するアルゴリズムのハイパーパラメータも最適化してみたいですね.
ということで本記事では,実際に再帰的にハイパーパラメータを最適化してみて最適化の性能がどのように変化するのかを調査してみようと思います.

実験

本記事では最適化として2次元で実数値の単目的最適化による最小化を考えます.つまり,関数$f: \mathbb{R}^2 \rightarrow \mathbb{R}$を与えて,$\underset{\textbf{x} \in \mathbb{R}^2}{\min} f(\textbf{x})$を求めます.具体的な関数は実験設定に記します.
最適化アルゴリズムにはDE(Differential Evolution, 差分進化)を採用します.DEは進化計算の1種で,シンプルなアルゴリズムでありながらそれなりの性能を持つ優秀なアルゴリズムです.通常ハイパーパラメータ最適化にはベイズ最適化をはじめとする,ハイパーパラメータへの依存が少ない手法やハイパーパラメータが存在しない手法を用いるのが主流かと思われます.ただ,今回はハイパーパラメータが及ぼす影響について調査したいこともあり,私見でハイパーパラメータへの依存も高い印象があるDEを採用しました.
検証に先立ち,まずは次節でDEのアルゴリズムについて概説します.

DE

DEは次の5つStepから成るアルゴリズムです.

  • Step1: Initialize
  • Step2: Mutation
  • Step3: Crossover
  • Step4: Selection
  • Step5: termination condition

各Stepについて説明します.ただし,なぜこのアルゴリズムで効率化な最適化が実現できるのかといった点は本記事の本筋ではないため省略します.

Step1: Initialize

$\textrm{NP}\in \mathbb{N}$ をハイパーパラメータとし,$\textrm{NP}$個の初期解集合$(\textbf{X} = \{\textbf{x}_1, \cdots, \textbf{x}_{\textrm{NP}}\})$を生成します.また,この初期解集合を現在の解集合とします.DEは多点探索アルゴリズムで,この初期解集合を後のStepで互いに作用させあいながら徐々に最適解に近づけていくことになります.
初期解生成アルゴリズムは様々ありますが,本記事ではシンプルに一様乱数で生成することとします.

Step2: Mutation

変異ベクトルと呼ばれる特殊なベクトルを生成します.生成手順は以下の通りです.
各 $i = 1,\cdots,NP$ について,$\textrm{F}\in [0,1]$ をハイパーパラメータとし$i$番目の変異ベクトル $v_i$ を次で求める.

  1. $r_1,r_2,r_3 \in \{1,\cdots,NP\}\setminus i$となる乱数$r_1,r_2,r_3$を定める
  2. $v_i = x_{r_1} + \textrm{F}(x_{r_2} - x_{r_3})$ とする

Step3: Crossover

現在の解集合と変異ベクトルを交差させ,新たな解候補の集合を生成します.生成手順は以下の通りです.
各 $i = 1,\cdots,NP$ について,$\textrm{CR} \in [0,1]$ をハイパーパラメータとし$i$番目の次世代の解候補$y_i$ を次で求める.

  1. 次元数個の乱数$r_j \in [0,1], j = \{1,\cdots\,D\}$を定める
  2. $u_i$の各次元の値$y_{ij}$について,$y_{ij} = \left\{\begin{array}{ll}v_{ij} & (r_j \leq \textrm{CR}) \\ x_{ij} & (otherwise)\end{array}\right.$ とする

Step4: Selection

現在の解集合と新たな解候補集合を比較し,より優れている解を次の世代(Step)の解集合とします.手順を以下の通りです.
各 $i = 1,\cdots,NP$ について,次世代の解 $z_i$ を次で求める.
$z_{i} = \left\{\begin{array}{ll}y_i & (f(y_i) < f(x_i)) \\ x_i & (otherwise)\end{array}\right.$

Step5: Termination Condition

事前に定めた終了条件を満たすかどうか判定し,満たしていればアルゴリズムを終了,満たしていなければStep2に戻ります.本記事では,「探索における総評価回数(関数$f$が呼ばれた回数)が規定回数以上」という条件で終了判定を行います.

実験設定

次の3つのDEで後述する関数を最適化し,探索推移を比較します.

  • f0:0再帰DE(ハイパーパラメータを適当に設定したDE)
  • f1:1再帰DE(ハイパーパラメータをハイパーパラメータを適当に設定したDEで最適化したDE)
  • f2:2再帰DE(ハイパーパラメータをハイパーパラメータをハイパーパラメータを適当に設定したDEで最適化したDEで最適化したDE)

なお,DEには$\textrm{NP},\textrm{F},\textrm{CR}$という3つのハイパーパラメータがありますが,今回は$\textrm{NP}$を固定し,$\textrm{F},\textrm{CR}$のみハイパーパラメータと捉えることにします.

共通設定

共通の設定を以下に示します.

試行回数100
次元数2
評価回数1000
NP20

関数

最適化する関数は次の3つを採用しました.次元数は前述したように全て2です.

Rosenbrock function

滑らかな形状の関数です.私が好きなので採用しました.
\begin{align}
f(x_1,x_2) = 100(x_2 - x_1^2)^2 + (x_1 - 1)^2 \\\
{-} 5 \leq x_i \leq 5 \; (i = 1,2)
\end{align}
最適解:$f_{\textrm{min}} = f(1, 1) = 0$

Rastrigin function

大域的には単峰でありながら大量の局所解が存在する関数です.私がとても好きなので採用しました.
\begin{align}
f(x_1,x_2) = 20 + \sum_{i=1}^2\left(x_i^2 - 10\cos (2\pi x_i)\right)\\\
{-} 5.12 \leq x_i \leq 5.12 \; (i = 1,2)
\end{align}
最適解:$f_{\textrm{min}} = f(0, 0) = 0$

Schwefel function

複数の峰が存在する多峰性の関数です.私のイチオシ関数なので採用しました.
\begin{align}
f(x_1,x_2) = -\sum_{i=1}^{2} \sin\left(\sqrt{|x_i|}\right) \\\
{-} 500 \leq x_i \leq 500 \; (i = 1,2)
\end{align}
最適解:$f_{\textrm{min}} = f(420.9687..., 420.9687...) = -837.9658..$

実験結果

実際に探索を行って得られた各関数における評価値推移の比較グラフです.左から,Rosenbrock function,Rastrigin function,Schwefel functionの結果で,縦軸が評価値,横軸が世代数です.今回は最小化を扱っているため,下に推移すればするほど性能が良いと言えます.
また,評価値は100試行の平均値を取ったもので,中央値などの他の情報については(面倒なので)触れません.





一番左のRosenbrock Functionは,ハイパーパラメータ最適化をしない場合が最も良い性能を発揮し,再帰的に最適化した2つの手法は同等程度の性能でした.真ん中のRastrigin Functionは,それぞれの手法で異なる傾向が得られ,2回再帰させた手法だけが他の手法に劣っています.一番右のSchwefel Functionは,ハイパーパラメータ最適化をしない場合が最も悪い性能を発揮し,再帰的に最適化した2つの手法は同等程度に良い性能でした.

考察

見て分かるように,見ても何も分かりませんでした.いかがでしたか?

.直感的には再帰させるほど良い結果が得られることが想定されます.今回このように手法や問題によって性能がバラバラになってしまったのはおそらく問題設定の不備が原因だと考えられます.実験では2次元の問題のみを扱いましたが,2次元では問題が簡単で,乱数によってはそれほど良いハイパーパラメータでなくても最適解に到達できてしまいます.さらにハイパーパラメータの最適化は探索後の最小値だけを見て行っていたため,これらが噛み合って最適でないハイパーパラメータが導出されてしまった可能性が高いです.
この仮説の検証及びさらなる調査として,より難しい問題を扱う,ハイパーパラメータ最適化を定式化し直すなどがあります.しかし,それらをし始めるとさらに考察->再実験のループに入ってしまい生活が崩壊しかねないのでここで打ち止めとします.

おわりに

本記事では再帰的なハイパーパラメータ最適化が探索に及ぼす影響について調査しました.当初は再帰すればするほど性能が良くなることを想定していたのですが,実際は全く異なる結果が得られました.
このように,最適化の分野は想定通りいかないことが多々あります.しかしだからこそ,どうすれば上手くいくのか,どうすればより良い解が得られるかを試行錯誤する時間が生まれ,この時間の楽しさは計り知れないです.
最適化は非常に便利なものです.日常生活でもコンピュータ上に限らず最適化ができる場面は多く存在します.そこで最適化がうまくいかなくてもそれを試行錯誤する時間はとても有意義で,それで良い解を発見した時はとても嬉しいものです.皆様もぜひ,日々の生活から最適化の精神 †OPTIMIND† を持って過ごして行きましょう.