パラメーターフリー遺伝的アルゴリズムでディープラーニングのハイパーパラメータを解く

##ディープラーニングの課題
最近、仕事でディープラーニングやってますが、結局over fitting（過学習）やunder fitting（未学習）との戦いに終始してしまう毎日を過ごしてます。

ネットワークの構成や各層のチャネル数、dropout有無やその率、optimizerの種類やlr（学習率）、weightDecay（L2ノルム）の値、等々調整すべきものはハイパーパラメータと呼ばれるものも含めて数多くあり、それらのベストな組み合わせを見つけるのは至難の業。

##パラメーターフリー遺伝的アルゴリズム
これらのベターな組み合わせ（ベストではない）を遺伝的アルゴリズムで解くという論文は既にいくつか出ているようだけど、PfGA（パラメーターフリー遺伝的アルゴリズム）で実現した記事を発見できなかったので、備忘録としてアップしておきます。

遺伝的アルゴリズムの詳しい説明は省略しますが、ディープラーニングのハイパーパラメータなどを遺伝子と見立てて、一定の長さのゲノム（染色体）を進化させていくことで、ベターな組み合わせを発見させることが目的です。

例えば、lr、weightDecay、optimizerの3つを遺伝子とした場合、長さ3のゲノムを沢山作って、選択、交叉、突然変異、適合度評価を繰り返しながら進化させるのですが、通常の遺伝的アルゴリズムでは、ゲノムの母集団が500とか1000とかになります。

ディープラーニングの場合は、１つのゲノムの適合度評価のために、少なくとも100エポック程度は学習させないとわからないので、かなりの時間がかかります。100エポックに3時間程度かかるテーマの場合、最初の母集団500個のゲノム全ての評価に3×500=1,500時間（２ヶ月程度）かかることになり現実的ではありません。

PfGAは2000年過ぎた頃に発表されたもので、元々は遺伝的アルゴリズムにも存在するハイパーパラメータの調整をしなくても解けるようにとの目的で生み出されています。

PfGAも詳しい説明は省略しますが、通常の遺伝的アルゴリズムとの大きな違いのひとつに、母集団の数があります。PfGAでは、初期母集団＝2でスタートします。この2つが親となり、2つの子供ゲノムを交叉によって生成します。さらにどちらかの子供ゲノムに対して任意の場所で任意の数だけ突然変異を行います。
そして、親ゲノム2個、子供ゲノム2個の4ゲノムの適合度によって、次の世代に残ることができるゲノムが決まります。全体の流れは下記の通り。
　０　初期母集団として、ランダムに2個の親ゲノムを生成する（各遺伝子の値は0~1のfloat値）
　１　母集団からランダムに2個の親ゲノムを選択する
　２　交叉（任意の遺伝子をお互い交換し、2個の子供ゲノムを生成する）
　３　突然変異（どちらかの子供ゲノムの任意の数だけ任意の場所の遺伝子をランダムに変更する）
　４　親と子供、合計４つのゲノムについて適合度を評価し、以下のルールで次世代に残すゲノムを選択する
　　　ルール1：全ての子供ゲノムが全ての親ゲノムより優秀だった場合、
　　　　　　　子供ゲノム2個と親ゲノムの良い方の計3個が次世代に残る
　　　ルール2：全ての親ゲノムが全ての子供ゲノムより優秀だった場合、
　　　　　　　親ゲノムの良い方のみが残る
　　　ルール3：親ゲノムのどちらかが全ての子供ゲノムより優秀だった場合、
　　　　　　　親ゲノムの良い方と子供ゲノムの良い方が残る
　　　ルール4：子供ゲノムのどちらかが全ての親ゲノムより優秀だった場合、
　　　　　　　子供ゲノムの良い方が残り、ランダム固体が1個追加される
　５　次世代のゲノム数が2個未満の場合、ランダム固体を2個になるまで追加する
　６　１に戻る

これがディープラーニングにはぴったりなんです。なぜなら適合度評価の対象ゲノムが通常の遺伝的アルゴリズムに比べて圧倒的に少ないから。

ちなみに今回仕事で試してみたパラメータは、9個の遺伝子で構成されていて、
　・weightDecay　9種類
　・チャネル倍率　6種類
　・CNN層1のdropout率　4種類
　・CNN層2のdropout率　4種類
　・CNN層3のdropout率　4種類
　・CNN層4のdropout率　4種類
　・最後の全結合層のチャネル倍率　6種類
　・訓練データのガウシアンノイズ率　7種類
　・optimizer　4種類
という選択肢を準備。その組み合わせは2,322,432パターンとなり、もし全部試そうとしたら、1パターンの学習を100エポック3時間かけたとして、795年（笑）かかることになります。

PfGAだったら、1世代の適合度評価に最大でも親ゲノム2個＋子供ゲノム2個＝4個×3時間＝12時間なので、1日に2世代（これでも相当遅いけど）進むことになる。まぁ、放置しておけば、勝手にベターな組み合わせを見つけてくれるので、仕事中のストレスは随分解消されるのではと期待してます。

##PfGAのコード
さて肝心のPfGAのコードですが、何せpython初心者のため、きっとひどい書き方になってると思いますが、備忘録として載せておきます。

```python:pfga.py
# Parameter Free GA
import numpy as np
import copy

class PFGA():
    def __init__(self, gene_len, evaluate_func=None, better_high=True, mutate_rate=0.05):
        self.family = []
        self.gene_len = gene_len
        self.evaluate_func = evaluate_func
        self.better_high = better_high
        self.mutate_rate = mutate_rate
        self.generation_num = 0
        
    def add_new_population(self):
        new_gene = []
        new_gene.append(np.random.rand(self.gene_len))
        new_gene.append(None)
        self.family.append(new_gene)
        
    def pop_num(self):
        return len(self.family)
        
    def copy_gene(self, g):
        return copy.deepcopy(g)
        
    def best_gene(self):
        idx = self.family[0]
        for i in self.family:
            if i[1] is not None:
                if idx[1] is not None:
                    if (self.better_high == True and idx[1] < i[1]) or (self.better_high == False and idx[1] > i[1]):
                        idx = i
                else:
                    idx = i
        return idx
        
    def select_and_delete_gene(self):
        return self.copy_gene(self.family.pop(np.random.randint(0, len(self.family))))
        
    def crossover(self, p1, p2):
        c1 = self.copy_gene(p1)
        c2 = self.copy_gene(p2)
        for i in range(len(c1[0])):
            if np.random.rand() < 0.5:
                c1[0][i], c2[0][i] = c2[0][i], c1[0][i]
        c1[1] = None
        c2[1] = None
        return c1, c2
        
    def mutate(self, g):
        for i in range(len(g[0])):
            if np.random.rand() < self.mutate_rate:
                g[0][i] = np.random.rand()
        return g
        
    def next_generation(self):
        while len(self.family) < 2:
            self.add_new_population()
            
        p1 = self.select_and_delete_gene()
        p2 = self.select_and_delete_gene()
        
        c1, c2 = self.crossover(p1, p2)
        
        if np.random.rand() < 0.5:
            c1 = self.mutate(c1)
        else:
            c2 = self.mutate(c2)
            
        self.generation_num += 1
        
        genelist = p1, p2, c1, c2
        for i in genelist:
            if i[1] is None:
                i[1] = self.evaluate_func(i[0])
                
        # rule-1:both child is better than both parant, remain both child and better 1 parant
        if (self.better_high == True and min(c1[1], c2[1]) > max(p1[1], p2[1])) or (self.better_high == False and max(c1[1], c2[1]) < min(p1[1], p2[1])):
            self.family.append(c1)
            self.family.append(c2)
            if (self.better_high == True and p1[1] > p2[1]) or (self.better_high == False and p1[1] < p2[1]):
                self.family.append(p1)
            else:
                self.family.append(p2)
                
        # rule-2:both parant is better than both child, remain better 1 parant
        elif (self.better_high == True and max(c1[1], c2[1]) < min(p1[1], p2[1])) or (self.better_high == False and min(c1[1], c2[1]) > max(p1[1], p2[1])):
            if (self.better_high == True and p1[1] > p2[1]) or (self.better_high == False and p1[1] < p2[1]):
                self.family.append(p1)
            else:
                self.family.append(p2)
        
        # rule-3:better 1 parant is better than both child, remain better 1 parant and better 1 child
        elif (self.better_high == True and max(c1[1], c2[1]) < max(p1[1], p2[1])) or (self.better_high == False and min(c1[1], c2[1]) > min(p1[1], p2[1])):
            if (self.better_high == True and p1[1] > p2[1]) or (self.better_high == False and p1[1] < p2[1]):
                self.family.append(p1)
            else:
                self.family.append(p2)
                
            if (self.better_high == True and c1[1] > c2[1]) or (self.better_high == False and c1[1] < c2[1]):
                self.family.append(c1)
            else:
                self.family.append(c2)
                    
        # rule-4:better 1 child is better than both parant, remain better 1 child and append 1 new gene
        else:
            if (self.better_high == True and c1[1] > c2[1]) or (self.better_high == False and c1[1] < c2[1]):
                self.family.append(c1)
            else:
                self.family.append(c2)
            self.add_new_population()
```

一方で、このPfGAを使う側のコードは下記のような感じです。有名な巡回セールスマン問題で試してみました（このコードはディープラーニングではありません）。

```python:salesman.py
# salesman
import numpy as np
import copy
import pfga
import matplotlib.pyplot as plt
import sys

class Salesman():
    def __init__(self, city_num=100):
        self.x = []
        self.y = []
        self.city_num = city_num
        for i in range(self.city_num):
            self.x.append(np.random.rand())
            self.y.append(np.random.rand())
            
    def draw_city(self, x, y, num):
        plt.clf()
        plt.title("Generation:{}".format(num))
        plt.plot(x, y, label="Salesman")
        plt.pause(.01)
        
    def draw_gene(self, gene, num):
        s = np.argsort(gene[0])
        sx = []
        sy = []
        for i in range(self.city_num):
            sx.append(self.x[s[i]])
            sy.append(self.y[s[i]])
        self.draw_city(sx, sy, num)
        
    def evaluate_salesman(self, gene):
        v = 0.0
        if gene is not None:
            s = np.argsort(gene)
            sx = []
            sy = []
            for i in range(len(gene)):
                sx.append(self.x[s[i]])
                sy.append(self.y[s[i]])
                
            for i in range(self.city_num-1):
                v += (sx[i]-sx[i+1])*(sx[i]-sx[i+1])+(sy[i]-sy[i+1])*(sy[i]-sy[i+1])
            
        return v
        
if __name__ == "__main__":
    city_num = 20
    if len(sys.argv) > 1:
        city_num = int(sys.argv[1])
    s = Salesman(city_num)
    ga = pfga.PFGA(city_num, evaluate_func=s.evaluate_salesman, better_high=False, mutate_rate=0.1)
    while True:
        ga.next_generation()
        best = ga.best_gene()
        if best is not None:
            s.draw_gene(best, ga.generation_num)
            print('gen:{} pop-num:{} best-value:{}'.format(ga.generation_num, ga.pop_num(), best[1]))
```

##ディープラーニング with PfGA
さて、ディープラーニング側でPfGAを使うコードについて簡単に説明します。
まずは、下記のようなクラスを作成します。

```python:
class Evaluate_cnn():
    def __init__(self, max_epoch = 100, batchsize = 16, gpu_id=-1):
        self.g0 = [ 0.05, 0.03, 0.01, 0.005, 0.003, 0.001, 0.0005, 0.0003, 0.0001 ]  #0 weight_decay_gene
        self.g1 = [ 1, 2, 3, 4, 5, 10 ]    #1 k_size_gene
        self.g2 = [ 0.1, 0.3, 0.5, 0.7 ]   #2 drop_rate1_gene
        self.g3 = [ 0.1, 0.3, 0.5, 0.7 ]   #3 drop_rate2_gene
        self.g4 = [ 0.1, 0.3, 0.5, 0.7 ]   #4 drop_rate3_gene
        self.g5 = [ 0.1, 0.3, 0.5, 0.7 ]   #5 drop_rate4_gene
        self.g6 = [ 1, 2, 3, 4, 5, 10 ]    #6 fc_size_gene
        self.g7 = [ 0.1, 0.2, 0.3, 0.5, 1.0, 2.0, 3.0 ]    #7 gauss_rate_gene
        self.g8 = [ optimizers.SGD,optimizers.MomentumSGD, optimizers.Adam, optimizers.AdaGrad, optimizers.AdaDelta ]   #8 optimizer_gene
        
        self.gene_list = [ self.g0, self.g1, self.g2, self.g3, self.g4, self.g5, self.g6, self.g7, self.g8 ]
        self.max_epoch = max_epoch
        self.batchsize = batchsize
        self.gpu_id = gpu_id
        self.past_param = []
        self.past_v = []
        
    def evaluate(self, gene):
        param = []
        for i in range(len(self.gene_list)):
            param.append(self.gene_list[i][int(gene[i] * len(self.gene_list[i]))])
            
        if len(self.past_param) > 0:
            for j in range(len(self.past_param)):
                if self.past_param[j] == param:
                    return self.past_v[j]
        v = train(param, max_epoch = self.max_epoch, batchsize = self.batchsize, gpu_id = self.gpu_id)
        self.past_param.append(param)
        self.past_v.append(v)
        return v
        
    def param_list(self, gene):
        param = []
        for i in range(len(self.gene_list)):
            param.append(self.gene_list[i][int(gene[i] * len(self.gene_list[i]))])
        return param
```

このクラスの\_\_init\_\_で遺伝子となるパラメータの種類と、それぞれが取る値のリストを定義します。
また、PfGAから適合度評価時に呼ばれる関数も準備します（ここではevaluate）。そのevaluate関数の冒頭で

```python:
        for i in range(len(self.gene_list)):
            param.append(self.gene_list[i][int(gene[i] * len(self.gene_list[i]))])
```

とあるように、遺伝子の値は0～1のfloat値なので、それぞれの遺伝子の取り得る値に変換してます。更に、

```python:
        if len(self.past_param) > 0:
            for j in range(len(self.past_param)):
                if self.past_param[j] == param:
                    return self.past_v[j]
```

と、過去のパラメータセットを記憶しておいて、同じセットの場合は学習させずに値を返してます。これが本当に良いのかどうか迷います。ディープラーニングでは、同じパラメータセットでも、重みの初期値がランダムであることから、100エポック後の結果が異なるケースも多いからです。とはいえ、早めの決着を考慮すると、できるだけ学習を避けたい気持ちもあって･･･。

```python:
def train(param, max_epoch = 50, batchsize = 8, gpu_id=0):   
    net = L.Classifier(CNN(5, int(param[1]), int(param[6]), param[2:6]))

    optimizer = param[8]()
    optimizer.setup(net)
    optimizer.add_hook(chainer.optimizer.WeightDecay(param[0]))
```

適合度評価時に呼ばれるtrain関数ではネットワークの初期化やoptimizer、weightDecayに遺伝子の値をセットしています。

```python:
class CNN(chainer.ChainList):
    def __init__(self, n_output, k=1, lk=1, droprate=[0.3, 0.5, 0.5, 0.7]):
        super(CNN, self).__init__(
            ConvBlock(1, 8*k, pool=True),
            ConvBlock(8*k, 16*k, pool=True,drop=droprate[0]),
            ConvBlock(16*k, 16*k),
            ConvBlock(16*k, 32*k, pool=True,drop=droprate[1]),
            ConvBlock(32*k, 32*k),
            ConvBlock(32*k, 64*k, pool=True,drop=droprate[2]),
            ConvBlock(64*k, 64*k),
            LinearBlock(100*lk, drop=droprate[3]),
            LinearBlock(n_output)
        )
```

ネットワークの初期化では渡された遺伝子の値を、CNNのチャネル倍率、全結合層のチャネル倍率、dropout率にそれぞれセットしています。

```python:
if __name__ == '__main__':
    ev = Evaluate_cnn(max_epoch = 100, batchsize = 512, gpu_id=0)
    ga = pfga.PFGA(9, evaluate_func=ev.evaluate, better_high=True, mutate_rate=0.1)
    
    while True:
        ga.next_generation()
        best = ga.best_gene()
        if best is not None:
            print('gen:{} best-value:{} best-gene:{}'.format(ga.generation_num, best[1], ev.param_list(best[0])))
```

最後に、このようなループを組むことで、PfGAによるディープラーニングの学習がスタートします。
機密情報がふくまれるため、全てのソースを公開できず心苦しいのですが、雰囲気が伝わればと思います。
質問などございましたらお気軽にどうぞ。