.. _chap_algorithm:

アルゴリズム
=====================
ここでは、ベイズ最適化に関する説明を行います。技術的な詳細については、`こちらの文献 <https://github.com/tsudalab/combo/blob/master/docs/combo_document.pdf>`_ を参照してください。

ベイズ最適化
---------------------
ベイズ最適化は、複雑なシミュレーションや、実世界における実験タスクなど、目的関数（特性値など）の評価に大きなコストがかかるような場合に利用できる手法です。つまり、「できるだけ少ない実験・シミュレーション回数でより良い目的関数（材料特性など）を持つ説明変数（材料の組成、構造、プロセスやシミュレーションパラメータなど）を見つけ出す」ことが、ベイズ最適化によって解かれる問題です。ベイズ最適化では、探索する説明変数（ベクトルxで表す）の候補をあらかじめリストアップした状況からスタートします。そして、候補の中から目的関数yが良くなると考えられる候補を、機械学習（ガウス過程回帰を利用）による予測をうまく利用することで選定します。その候補に対して実験・シミュレーションを行い目的関数の値を評価します。機械学習による選定・実験シミュレーションによる評価を繰り返すことにより、できるだけ少ない回数で最適化が可能となります。

ベイズ最適化のアルゴリズムの詳細を以下に示します。

- ステップ１：初期化

探索したい空間をあらかじめ用意します。つまり、候補となる材料の組成・構造・プロセスやシミュレーションパラメータ等を、ベクトル :math:`{\bf x}` で表現しリストアップします。この段階では、目的関数の値はわかっていません。このうち初期状態としていくつかの候補を選び、実験またはシミュレーションによって目的関数の値 :math:`{\bf y}` を見積もります。これにより、説明変数 :math:`{\bf x}` と目的関数 :math:`{\bf y}` が揃った学習データ :math:`D = \{ {\bf x}_i, {\bf y}_i \}_{(i=1, \cdots, N)}` が得られます。

- ステップ２：候補選定

学習データを用いて、ガウス過程を学習します。ガウス過程によれば、任意の :math:`{\bf x}` における予測値の平均を :math:`\mu_c ({\bf x})` 、分散を :math:`\sigma_c ({\bf x})` とすると、

.. math::
   
   \mu_c ({\bf x}) &= {\bf k}({\bf x})^T (K+\lambda I)^{-1}{\bf y},

   \sigma_c({\bf x}) &= k({\bf x}, {\bf x}) + \lambda - {\bf k}({\bf x})^T  (K+\lambda I)^{-1}{\bf k}({\bf x}),

となります。ただし、 :math:`k({\bf x}, {\bf x}')` はカーネルと呼ばれる関数であり、2つのベクトルの類似度を表します。一般に、以下のガウスカーネルが使われます。

.. math::

   k({\bf x}, {\bf x}') = \exp \left[ -\frac{1}{2\gamma^2}||{\bf x} - {\bf x}'||^2 \right]

また、このカーネル関数を利用し、 :math:`{\bf k}({\bf x})` および :math:`K` は以下のように計算されます。

.. math::
   
   {\bf k}({\bf x}) = \left( k({\bf x}_1, {\bf x}), k({\bf x}_2, {\bf x}), \cdots, k({\bf x}_N, {\bf x}) \right)^T

.. math::
   :nowrap:

    \[
    K = \left(
    \begin{array}{cccc}
       k({\bf x}_1, {\bf x}_1) & k({\bf x}_1, {\bf x}_2) & \ldots &  k({\bf x}_1, {\bf x}_N) \\
       k({\bf x}_2, {\bf x}_1) & k({\bf x}_2, {\bf x}_2) & \ldots &  k({\bf x}_2, {\bf x}_N) \\
      \vdots & \vdots & \ddots & \vdots \\
       k({\bf x}_N, {\bf x}_1) & k({\bf x}_N, {\bf x}_2) & \ldots &  k({\bf x}_N, {\bf x}_N)
    \end{array}
    \right)
    \]

まだ実験やシミュレーションを行っていない候補全てに対して、予測値 :math:`\mu_c ({\bf x})` および予測の不確かさに関連する分散 :math:`\sigma_c ({\bf x})` を見積もります。これを用いて獲得関数を計算し、目的関数の値がまだわかっていない候補の中から、獲得関数を最大化する候補 :math:`{\bf x}^*` を選定します。このとき、 :math:`\lambda` および :math:`\gamma` はハイパーパラメタと呼ばれ、PHYSBOでは最適な値が自動で設定されます。

- ステップ３：実験

ステップ２で選定された獲得関数が最大となる候補 :math:`{\bf x}^*` に対して実験またはシミュレーションを行い、目的関数値 :math:`{\bf y}` を見積もります。これにより学習データが一つ追加されます。このステップ２、３を繰り返すことで、スコアのよい候補を探索します。