What is gradient in Gradient Descent? / [勾配降下法]関数の勾配の定義を振り返る

勾配とは?

そもそもの勾配の定義から振り返ろう。以下のような関数fについて考える。

[mathjax]

$$f(x) = 3x_1^2 – 2x_1x_2 + 3x_2^2 -4x_1 -4x_2$$

このときベクトル$latex \nabla f(x)$を点xにおける関数fの勾配(gradient)という。

$$ \nabla f(x) = \left( \frac{\partial f(x)}{\partial x_1}, \frac{\partial f(x)}{\partial x_2}, \cdots, \frac{\partial f(x)}{\partial x_n} \right) \in \mathbb R^n $$

※ただし以下が成り立つ場合(これは2点を結ぶ線分の傾きから求められますよね?)

$$ f(x+d) = f(x) + \nabla f(x)^Td + o(\Vert{d}\Vert), d \in \mathbb R^n$$

この定義に基づくと上式の勾配は以下で表すことができる。

$$\nabla f(x) = \begin{pmatrix}
6x_1-2x_2-4 \\
-2x_1 + 6×2 -4 \\
\end{pmatrix}
$$

ここで勾配の定義をより直感的にするために以下の2点における勾配を考えてみる。

$$a = (0, 0)^T, \nabla f(a) = (-4, -4)^T$$
$$b = (2, 0)^T, \nabla f(b) = (8, -8)^T$$

このようにfにおける各点の勾配は接線に対して垂直なベクトルとして表される。
そして上図の各点において傾きが最大となる方向を表し、勾配と反対になる方向が降下方向となる。

つまり探索方向を勾配$latex \nabla f(x)$の逆(降下)方向に定めて探索することから「勾配降下法」と言われる所以である(と思う。)

勾配降下法の探索イメージ

初期点を(0, 0)とするとたとえばこんな感じ?

How to implement Genetic Algorithm with python / 遺伝的アルゴリズムをPythonで実装する

モチベーション

以前子供たちと一緒にめんぼうで遺伝的アルゴリズムを実装しました。その内容をPythonプログラムとして実装することでより一層理解を深めたいと思い始めました。

https://loochs.org/session36-asobi-workshop/

そもそも遺伝的アルゴリズムとは?

以下の書籍が非常に参考となります。今回の実装もこちらに基づいております。

ソースコード

実際の実装は以下リンク先から参照してください。

https://github.com/kichinosukey/GA-Question

サンプルコード

3つの3択問題についての解答を試行するGAになります。

import numpy as np

from lib import crossover, evaluate, gen_population, select, mutation

if __name__ == '__main__':

    answer = [1, 2, 3]
    num_question = len(answer)
    num_survive = 3
    num_population = 5

    population = gen_population(num_population, num_question, (min(answer), max(answer)))
    score_dict = {idx:sum(evaluate(answer, result)) for idx, result in population.items()}
    score_list_sorted = sorted(score_dict.items(), reverse=True, key=lambda x: x[1])
    
    print(score_list_sorted[0])
    cnt = 0
    while score_list_sorted[0][1] != 3:
        

        score_list_selected = select(score_list_sorted, num_survive)
        idx_selected = [t[0] for t in score_list_selected]
        population_selected = [population[idx] for idx in idx_selected]

        pop01 = population[score_list_sorted[0][0]]
        pop02 = population[score_list_sorted[1][0]]
        crv_point = np.random.randint(1, num_question-1)
        new01, new02 = crossover(pop01, pop02, crv_point)
        new01 = mutation(new01, (1, 4))
        new02 = mutation(new02, (1, 4))

        population_selected.append(new01)
        population_selected.append(new02)

        population = population_selected[:]
        population = {i:pop for i, pop in enumerate(population)}
        score_dict = {idx:sum(evaluate(answer, result)) for idx, result in population.items()}
        score_list_sorted = sorted(score_dict.items(), reverse=True, key=lambda x: x[1])       

        print(score_list_sorted[0])

        cnt += 1

        if cnt > 100:
            print(population)
            break

設計コンセプト

遺伝的アルゴリズムは大まかに以下の4つの処理を繰り返していきます。

  • 解候補の生成
  • 各解候補の評価
  • 優秀な解候補の選別
  • 新規解候補の生成(交叉・変異)

以下に各処理に関連するメソッドを載せておきます。

解候補の生成

generateでは単一の候補が決められた範囲内(range_ans)からint型の解を生成します。次にgen_populationでは解候補を指定数生成して各候補ごとにgenerateで解を生成します。

def generate(number_question, range_ans):
    """Generate answer array for questions
    
    Args:
        number_question(int):
        range_ans(tuple):
    
    Returns:
        (np.array):
    """
    return np.random.randint(range_ans[0], range_ans[1], number_question)

def gen_population(num_population, num_question, range_ans):
    """Generate population
    
    Args:
        num_population(int): number of population
        num_question(int): number of question
        range_ans(tuple): range of answers, only supported int
    
    Returns:
        (dict):{index: answer_array}
    """
    return {i:list(generate(num_question, range_ans)) for i in range(num_population)}

各解候補の評価

各候補の解と生成した解を比較して候補ごとの評価を下します。

def evaluate(answer, generated):
    """Evaluate answer array
    
    Args:
        answer(list): answer array
        generated(list): generated array
    """
    result = []
    for a, b in zip(answer, generated):
        if a == b:
            match = 1
        else:
            match = 0
        result.append(match)
    return result

優秀な解候補の選別

evaluateを使って候補ごとにスコアが出たので次の世代に残したい候補数(num_survive)を上位から順に確保しておきます。

def select(score_list, num_survive):
    """Selection method
    
    Args:
        score_list(list):
        num_survive(int): number of survival candidate
    
    Returns:
        (list)
    """
    return score_list[:num_survive]

新規解候補の生成(交叉・変異)

交叉と変異の実装です。簡易的なものなのでここは工夫のしがいがあります。今後の伸び代としてとっておきます。

def mutation(arr, range_mut):
    """Mutation
    Args:
        arr(list): array for mutation
        range_mut(tuple/list): range value for mutation
    """
    idx_max_mut = len(arr)
    idx_mut = np.random.randint(0, idx_max_mut)
    arr[idx_mut] = np.random.randint(range_mut[0], range_mut[1])
    return arr

def crossover(arr_01, arr_02, crv_point):
    """Cross over
    Args:
        arr(list):
        crv_point(int): cross over point
    Returns:
        (tuple)
    
    """
    arr_01_left = arr_01[:crv_point]
    arr_01_right = arr_01[crv_point:]
    arr_02_left = arr_02[:crv_point]
    arr_02_right = arr_02[crv_point:]

    arr_01_new = arr_01_left + arr_02_right
    arr_02_new = arr_02_left + arr_01_right

    return arr_01_new, arr_02_new

最後に

実は以前にの簡単なGAの実装に試みたことがあったのですがうまくいきませんでした。前回との違いはアソビワークショップで綿棒実装したことでかなり理解が深まっていたものと思います。今後の課題としては適用可能な問題が整数型の選択問題に限ったものなのでその適用範囲を広げるといった試みは必要かと思います。

そういえば変異を実装せずに一度サンプルスクリプトを動かしてみるとなかなか解が収束しない状況に陥りました。やはり候補の多様性というのが遺伝子の生き残りにおいては重要な要素なのだと改めて実感した次第です。