インターン講座２：離散最適化(GA) / 連続最適化(scipy optimize / torch optim) / ベイズ最適化(optuna)

Yuichiro Minato

2022/08/30 12:01

今回はインターン講座2回目です。前回は軽く機械学習とニューラルネットワークモデルを見ました。今回は最適化について確認をします。

最適化は、大きく分けて二種類に分かれます。値が連続していない「離散最適化」と値が連続している「連続最適化」です。

「離散最適化」は値がとびとびの離散値を取るため、微分を取ることができません。用途は「組合せ最適化問題」と呼ばれる多数の選択肢から一番いいものを選ぶような計算に利用されます。

「連続最適化（数理最適化）」は値が連続になっているため微分を取ることができます。微分を取らないで解く方法もありますが、主に機械学習や量子計算のモデルを最適化するために使われます。

また、それに加え機械学習のパラメータ探索で利用されるベイズ最適化を含めたざっくり3種類を学びます。

「離散最適化」
こちらは遺伝的アルゴリズム（GA）・タブーサーチ・シミュレーテッドアニーリングなどが有名です。メタヒューリスティクスという方法を使って計算をすることが多く、量子に対応するのは量子アニーリングやQAOAといったアルゴリズムです。コスト関数を設定し、それを最小化するなどの方向に計算をします。最小化するのは、例えば自動車の走行する最短距離だったり、一番効率的なスケジュールなどを組むなどを行うことができます。今回はGAを学びます。

「遺伝的アルゴリズム」
wikipediaの説明を見てみます。

遺伝的アルゴリズム（いでんてきアルゴリズム、英語：genetic algorithm、略称：GA）とは、1975年にミシガン大学のジョン・H・ホランド（John Henry Holland）によって提案された近似解を探索するメタヒューリスティックアルゴリズムである。人工生命同様、偶然の要素でコンピューターの制御を左右する。4つの主要な進化的アルゴリズムの一つであり、その中でも最も一般的に使用されている。 https://ja.wikipedia.org/wiki/%E9%81%BA%E4%BC%9D%E7%9A%84%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0

「遺伝的アルゴリズム」の流れ

遺伝的アルゴリズムは一般に以下の流れで実装される。なお、下記では個体数をN, 最大世代数をGと置く。

1.あらかじめN個の個体が入る集合を二つ用意する。以下、この二つの集合を「現世代」、「次世代」と呼ぶことにする。
2. 現世代にN個の個体をランダムに生成する。評価関数により、現世代の各個体の適応度をそれぞれ計算し、ある確率で次の3つの動作のどれかを行いその結果を次世代に保存する。

A. 個体を二つ選択して交叉を行う。
B. 個体を一つ選択して突然変異を行う。
C. 個体を一つ選択してそのままコピーする。

次世代の個体数がN個になるまで上記の動作を繰り返す。次世代の個体数がN個になったら次世代の内容を全て現世代に移す。

3.以降の動作を最大世代数G回まで繰り返し、最終的に「現世代」の中で最も適応度の高い個体を「解」として出力する。

早速遺伝的アルゴリズムのpythonパッケージのvcoptを利用して実装をしてみます。


!pip install vcopt

Requirement already satisfied: vcopt in /opt/conda/lib/python3.10/site-packages (1.6.3)

Requirement already satisfied: matplotlib in /opt/conda/lib/python3.10/site-packages (from vcopt) (3.5.2)

Requirement already satisfied: joblib in /opt/conda/lib/python3.10/site-packages (from vcopt) (1.1.0)

Requirement already satisfied: numpy in /opt/conda/lib/python3.10/site-packages (from vcopt) (1.21.0)

Requirement already satisfied: python-dateutil>=2.7 in /opt/conda/lib/python3.10/site-packages (from matplotlib->vcopt) (2.8.2)

Requirement already satisfied: kiwisolver>=1.0.1 in /opt/conda/lib/python3.10/site-packages (from matplotlib->vcopt) (1.4.4)

Requirement already satisfied: cycler>=0.10 in /opt/conda/lib/python3.10/site-packages (from matplotlib->vcopt) (0.11.0)

Requirement already satisfied: pyparsing>=2.2.1 in /opt/conda/lib/python3.10/site-packages (from matplotlib->vcopt) (3.0.9)

Requirement already satisfied: fonttools>=4.22.0 in /opt/conda/lib/python3.10/site-packages (from matplotlib->vcopt) (4.34.4)

Requirement already satisfied: packaging>=20.0 in /opt/conda/lib/python3.10/site-packages (from matplotlib->vcopt) (21.3)

まずはツールを読み込みます。


from vcopt import vcopt

次に最適化をするための評価関数を設定します。この値が最小になる方向に基本的には向かいます。今回は単純な二次関数を見ました。


#評価関数
def f(x):
    return x**2

次に探索するパラメータの範囲を設定します。


#パラメータ範囲
x_range = [-5, 5]
print(x_range)

[-5, 5]

そして早速実行します。引数は、パラメータ探索範囲、評価関数、ターゲットの順番で設定をします。ターゲットは今回は小さくしたいので-9999としました。


#最適化を実行
para, score = vcopt().rcGA(x_range, f, -9999)

________________________________________ info ________________________________________

para_range     : n=1

score_func     : <class 'function'>

aim            : ==-9999.0

show_pool_func : 'bar'

seed           : None

pool_num       : 10

max_gen        : None

core_num       : 1 (*vcopt, vc-grendel)

_______________________________________ start ________________________________________


#結果の表示
print(para)
print(score)

[-0.06034547]

0.0036415763068664156

x=0のときに、y=0になるように最小化が進んである程度の値が出ました。このように評価関数や値の範囲を設定し、遺伝的アルゴリズムの手順に沿ってpython内で処理が進み解が出力されます。

「連続最適化」
こちらは機械学習などのモデルを最適化しますが、関数の傾きを計算し、低い方に進むようにして計算する勾配法が有名です。その他勾配を利用ない方法も使いやすいので使われることもあります。量子計算でも量子古典ハイブリッドと呼ばれる手法で使われます。今回はscipyというライブラリに掲載されているscipy.optimize.minimizeをみてみます。また、pytorchに搭載されているSGDを含む複数の最適化アルゴリズムが掲載されたoptimライブラリを見てみます。後者は勾配ベースのアルゴリズムとなっています。

「scipy.optimize.minimize」 scipyというライブラリに搭載されている最適化アルゴリズムです。早速使い方を見てみます。
https://docs.scipy.org/doc/scipy/reference/generated/scipy.optimize.minimize.html

最適化アルゴリズムには、1次2次の導関数が必要なものや不要のものもあります。今回は不要なものとして、Powell/Nelder-Mead/COBYLAなどを簡単に使ってみます。関数は先ほどのGAと同じものを使います。こちらでは初期状態のxの値を指定して投げます。


import scipy.optimize
import numpy as np

x0 = np.array([1.0])
scipy.optimize.minimize(f, x0, method='Powell')

   direc: array([[1.]])

     fun: array(0.)

 message: 'Optimization terminated successfully.'

    nfev: 19

     nit: 2

  status: 0

 success: True

       x: array([0.])


x0 = np.array([1.0])
scipy.optimize.minimize(f, x0, method='Nelder-Mead')

 final_simplex: (array([[-8.8817842e-16],

       [ 9.7656250e-05]]), array([7.88860905e-31, 9.53674316e-09]))

           fun: 7.888609052210118e-31

       message: 'Optimization terminated successfully.'

          nfev: 34

           nit: 17

        status: 0

       success: True

             x: array([-8.8817842e-16])


x0 = np.array([1.0])
scipy.optimize.minimize(f, x0, method='COBYLA')

     fun: 1e-08

   maxcv: 0.0

 message: 'Optimization terminated successfully.'

    nfev: 18

  status: 1

 success: True

       x: array([0.0001])

大体どれを使っても変わりませんが、似た解がでるようになっています。次に今度はPyTorchのoptimをみてみます。

「PyTorch Optimizer」
機械学習向けの最適化アルゴリズムは主に勾配ベースのものが使われています。初期位置から微分を計算し、低いほうに下っていくもので、SGDと呼ばれる確率的勾配法をベースとしたアルゴリズムが実装されています。

最初にツールを読み込みます。


import torch

/opt/conda/lib/python3.10/site-packages/tqdm/auto.py:22: TqdmWarning: IProgress not found. Please update jupyter and ipywidgets. See https://ipywidgets.readthedocs.io/en/stable/user_install.html

  from .autonotebook import tqdm as notebook_tqdm

初期値と最適化アルゴリズムを準備します。
初期値はtorch.tensorの形にしておく必要があります。

最適化アルゴリズムはSGDをベースにいろいろあります。lrは学習率で今回は0.1としました。


x = torch.tensor([10.0],requires_grad=True)
op = torch.optim.SGD([x], lr=0.1)

実行ではループを回します。実際にxの値を関数として代入して計算します。


for _ in range(100):
    y = x**2

    op.zero_grad()
    y.backward()
    op.step()
    
print(x)

tensor([2.0370e-09], requires_grad=True)

このように計算できました。ちょっとほかの最適化アルゴリズムと実装の手順が異なりました。

「ベイズ最適化」
何かしらの最適化をする際に、優先順位をつけて探索をするのがベイズ最適化です。機械学習では様々な設定をしないといけないパラメータが出てきますが、そのような選択肢、離散値、連続値などをまとめて探索したりするときにもベイズ最適化はよく使われます。今回はoptunaと呼ばれるライブラリをみてみます。


!pip install optuna

Requirement already satisfied: optuna in /opt/conda/lib/python3.10/site-packages (3.0.0)

Requirement already satisfied: sqlalchemy>=1.1.0 in /opt/conda/lib/python3.10/site-packages (from optuna) (1.4.39)

Requirement already satisfied: packaging>=20.0 in /opt/conda/lib/python3.10/site-packages (from optuna) (21.3)

Requirement already satisfied: numpy in /opt/conda/lib/python3.10/site-packages (from optuna) (1.21.0)

Requirement already satisfied: scipy<1.9.0,>=1.7.0 in /opt/conda/lib/python3.10/site-packages (from optuna) (1.8.1)

Requirement already satisfied: tqdm in /opt/conda/lib/python3.10/site-packages (from optuna) (4.64.0)

Requirement already satisfied: PyYAML in /opt/conda/lib/python3.10/site-packages (from optuna) (6.0)

Requirement already satisfied: cmaes>=0.8.2 in /opt/conda/lib/python3.10/site-packages (from optuna) (0.8.2)

Requirement already satisfied: typing-extensions>=3.10.0.0 in /opt/conda/lib/python3.10/site-packages (from optuna) (4.3.0)

Requirement already satisfied: alembic in /opt/conda/lib/python3.10/site-packages (from optuna) (1.8.1)

今回は以前行った家賃をあてる問題のパラメータのうち、NNの中間層、最適化アルゴリズム、学習率をそれぞれ変数として最適化をします。最小化するのは、家賃の正解値11.5に一番近いパラメータとします。


import torch
import random
import optuna
import numpy as np
import pandas as pd

#データを準備しました。
data = np.array([[8,3,83.74,18,22],[5,2,75.72,19,19],[7,2,31.47,46,7.8],[18,2,46.62,36,8],[8,3,41.02,49,8],[8,1,70.43,25,15.8],[8,1,70.43,25,15.8],[12,1,48.02,3,12.5],[10,4,58.57,36,11.8]])
df = pd.DataFrame(data,columns=['toho','kaisu','hirosa','chiku','chinryo'])

#賃料だけのデータ
y = df["chinryo"]

#賃料以外のデータ
X = df.drop(columns=["chinryo"], axis=1)

from sklearn.model_selection import train_test_split
X_train, X_val, y_train, y_val = train_test_split(X, y, test_size=0.2, random_state=1)

#シード固定
seed = 1
random.seed(seed)
np.random.seed(seed)
torch.manual_seed(seed)

def objective(trial):
    #中間レイヤー数x
    x = trial.suggest_int('x', 4, 20)
    
    model2 = torch.nn.Sequential()
    model2.add_module('fc1', torch.nn.Linear(4, x))
    model2.add_module('relu', torch.nn.ReLU())
    model2.add_module('fc2', torch.nn.Linear(x, 1))

    optimizer_name = trial.suggest_categorical('optimizer_name', ['SGD', 'Adam'])
    learning_rate = trial.suggest_float('learning_rate', 0.01, 1.)
    if optimizer_name == "SGD":
        optimizer = torch.optim.SGD(model2.parameters(), lr = learning_rate)
    else:
        optimizer = torch.optim.Adam(model2.parameters(), lr = learning_rate)

    #損失関数選ぶ
    lossf = torch.nn.MSELoss()

    #入力値とターゲット
    input = torch.Tensor(X_train.values)
    target = torch.Tensor([[i] for i in y_train.values])

    #トレーニング
    for _ in range(100):
      loss = lossf(model2(input), target)
      optimizer.zero_grad()
      loss.backward()
      optimizer.step()
    
    X_test = np.array([[9,5,58.3,34]])
    pred = model2(torch.Tensor(X_test))
    
    return (pred - 11.5)**2

study = optuna.create_study()
study.optimize(objective, n_trials=20)

[32m[I 2022-08-30 12:00:04,059][0m A new study created in memory with name: no-name-1f08f809-d9e0-4a77-90dc-787d52f43b03[0m

[32m[I 2022-08-30 12:00:04,155][0m Trial 0 finished with value: 5.479587078094482 and parameters: {'x': 6, 'optimizer_name': 'SGD', 'learning_rate': 0.044333181067415524}. Best is trial 0 with value: 5.479587078094482.[0m

[32m[I 2022-08-30 12:00:04,307][0m Trial 1 finished with value: 8.065937042236328 and parameters: {'x': 5, 'optimizer_name': 'Adam', 'learning_rate': 0.6226217508662838}. Best is trial 0 with value: 5.479587078094482.[0m

[32m[I 2022-08-30 12:00:04,389][0m Trial 2 finished with value: 8.660406112670898 and parameters: {'x': 7, 'optimizer_name': 'SGD', 'learning_rate': 0.5020381290904798}. Best is trial 0 with value: 5.479587078094482.[0m

[32m[I 2022-08-30 12:00:04,467][0m Trial 3 finished with value: 8.660411834716797 and parameters: {'x': 13, 'optimizer_name': 'SGD', 'learning_rate': 0.46807361305790574}. Best is trial 0 with value: 5.479587078094482.[0m

[32m[I 2022-08-30 12:00:04,542][0m Trial 4 finished with value: 8.660406112670898 and parameters: {'x': 8, 'optimizer_name': 'SGD', 'learning_rate': 0.8074981983899306}. Best is trial 0 with value: 5.479587078094482.[0m

[32m[I 2022-08-30 12:00:04,662][0m Trial 5 finished with value: 3.2180960178375244 and parameters: {'x': 9, 'optimizer_name': 'Adam', 'learning_rate': 0.46194632516596684}. Best is trial 5 with value: 3.2180960178375244.[0m

[32m[I 2022-08-30 12:00:04,737][0m Trial 6 finished with value: 8.660406112670898 and parameters: {'x': 18, 'optimizer_name': 'SGD', 'learning_rate': 0.691990889952687}. Best is trial 5 with value: 3.2180960178375244.[0m

[32m[I 2022-08-30 12:00:04,797][0m Trial 7 finished with value: 8.660406112670898 and parameters: {'x': 7, 'optimizer_name': 'SGD', 'learning_rate': 0.5674500614264276}. Best is trial 5 with value: 3.2180960178375244.[0m

[32m[I 2022-08-30 12:00:04,947][0m Trial 8 finished with value: 0.00038580328691750765 and parameters: {'x': 9, 'optimizer_name': 'Adam', 'learning_rate': 0.7956685276125515}. Best is trial 8 with value: 0.00038580328691750765.[0m

このように、パラメータが探索されました。