Нативная нейронная сеть, часть IV: градиентный спуск и обратное распространение

оригинал:Deep Learning From Scratch IV: Gradient Descent and Backpropagation

Перевод: Сунь Имэн

Глава 1: Вычислительные графики
Глава 2: Персептроны
Глава 3: Стандарты обучения
Глава 4: Градиентный спуск и обратное распространение
Глава 5: Многослойные персептроны
Глава 6: TensorFlow

градиентный спуск

В общем, чтобы найти минимум функции, мы можем установить ее производную равной 0 и найти параметры. Однако на самом деле найтииЗамкнутое решение невозможно, поэтому переходимградиентный спускметод, который итеративно находит минимальное значение.

Представьте, что вы стоите на высокой горе, и если вы хотите спуститься на землю в кратчайшее время, вам нужно выбрать самое крутое направление горы.

Градиентный спуск такой же, он сначала берёт случайное число в диапазоне значений параметров, а потом итеративно находит проигрышминимальный случай. На каждом шаге итерацииЗначение уменьшается в самом крутом направлении, а затем продолжает итерацию на один шаг в этом направлении.

Одномерный случай этого процесса таков:

В определенной точке направление наискорейшего спуска определяется градиентом функции в этой точке:梯度的相反数(Потому что это падение) — это направление, в котором потери падают быстрее всего.

Как в этом случае минимизироватьУ нас есть несколько идей:

дай первымислучайное значение
рассчитатьоиградиент
Возьмите противоположный градиент в качестве направления и выполните итерацию на один шаг вперед.
вернуться к шагу 2

Давайте напишем операцию, которая вычисляет минимальное значение узла с помощью градиентного спуска. по параметруlearning_rateРазмер шага для каждого шага может быть установлен.

import numpy as np

class Operation:
    """Represents a graph node that performs a computation.

    An `Operation` is a node in a `Graph` that takes zero or
    more objects as input, and produces zero or more objects
    as output.
    """

    def __init__(self, input_nodes=[]):
        """Construct Operation
        """
        self.input_nodes = input_nodes

        # Initialize list of consumers (i.e. nodes that receive this operation's output as input)
        self.consumers = []

        # Append this operation to the list of consumers of all input nodes
        for input_node in input_nodes:
            input_node.consumers.append(self)

        # Append this operation to the list of operations in the currently active default graph
        _default_graph.operations.append(self)

    def compute(self):
        """Computes the output of this operation.
        "" Must be implemented by the particular operation.
        """
        pass

class Graph:
    """Represents a computational graph
    """

    def __init__(self):
        """Construct Graph"""
        self.operations = []
        self.placeholders = []
        self.variables = []

    def as_default(self):
        global _default_graph
        _default_graph = self

class placeholder:
    """Represents a placeholder node that has to be provided with a value
       when computing the output of a computational graph
    """

    def __init__(self):
        """Construct placeholder
        """
        self.consumers = []

        # Append this placeholder to the list of placeholders in the currently active default graph
        _default_graph.placeholders.append(self)

class Variable:
    """Represents a variable (i.e. an intrinsic, changeable parameter of a computational graph).
    """

    def __init__(self, initial_value=None):
        """Construct Variable

        Args:
          initial_value: The initial value of this variable
        """
        self.value = initial_value
        self.consumers = []

        # Append this variable to the list of variables in the currently active default graph
        _default_graph.variables.append(self)

class add(Operation):
    """Returns x + y element-wise.
    """

    def __init__(self, x, y):
        """Construct add

        Args:
          x: First summand node
          y: Second summand node
        """
        super().__init__([x, y])

    def compute(self, x_value, y_value):
        """Compute the output of the add operation

        Args:
          x_value: First summand value
          y_value: Second summand value
        """
        return x_value + y_value

class matmul(Operation):
    """Multiplies matrix a by matrix b, producing a * b.
    """

    def __init__(self, a, b):
        """Construct matmul

        Args:
          a: First matrix
          b: Second matrix
        """
        super().__init__([a, b])

    def compute(self, a_value, b_value):
        """Compute the output of the matmul operation

        Args:
          a_value: First matrix value
          b_value: Second matrix value
        """
        return a_value.dot(b_value)
class Session:
    """Represents a particular execution of a computational graph.
    """

    def run(self, operation, feed_dict={}):
        """Computes the output of an operation

        Args:
          operation: The operation whose output we'd like to compute.
          feed_dict: A dictionary that maps placeholders to values for this session
        """

        # Perform a post-order traversal of the graph to bring the nodes into the right order
        nodes_postorder = traverse_postorder(operation)

        # Iterate all nodes to determine their value
        for node in nodes_postorder:

            if type(node) == placeholder:
                # Set the node value to the placeholder value from feed_dict
                node.output = feed_dict[node]
            elif type(node) == Variable:
                # Set the node value to the variable's value attribute
                node.output = node.value
            else:  # Operation
                # Get the input values for this operation from node_values
                node.inputs = [input_node.output for input_node in node.input_nodes]

                # Compute the output of this operation
                node.output = node.compute(*node.inputs)

            # Convert lists to numpy arrays
            if type(node.output) == list:
                node.output = np.array(node.output)

        # Return the requested node value
        return operation.output


def traverse_postorder(operation):
    """Performs a post-order traversal, returning a list of nodes
    in the order in which they have to be computed

    Args:
       operation: The operation to start traversal at
    """

    nodes_postorder = []

    def recurse(node):
        if isinstance(node, Operation):
            for input_node in node.input_nodes:
                recurse(input_node)
        nodes_postorder.append(node)

    recurse(operation)
    return nodes_postorder


red_points = np.random.randn(50, 2) - 2*np.ones((50, 2))
blue_points = np.random.randn(50, 2) + 2*np.ones((50, 2))

class negative(Operation):
    """ 逐元素计算负数
    """

    def __init__(self, x):
        """ 构造负运算

        参数列表:
          x: 输入节点
        """
        super().__init__([x])

    def compute(self, x_value):
        """ 计算负运算 operation 的输出

        参数列表:
          x_value: 输入值
        """
        return -x_value

class log(Operation):
    """ 对每一个元素进行对数运算
    """

    def __init__(self, x):
        """ 构造 log

        参数列表:
          x: 输入节点
        """
        super().__init__([x])

    def compute(self, x_value):
        """ 计算对数 operation 的输出

        参数列表:
          x_value: 输入值
        """
        return np.log(x_value)

class multiply(Operation):
    """ 对每一个元素，返回 x * y 的值
    """

    def __init__(self, x, y):
        """ 构造乘法

        参数列表:
          x: 第一个乘数的输入节点
          y: 第二个乘数的输入节点
        """
        super().__init__([x, y])

    def compute(self, x_value, y_value):
        """ 计算乘法 operation 的输出

        Args:
          x_value: 第一个乘数的值
          y_value: 第二个乘数的值
        """
        return x_value * y_value

class negative(Operation):
    """ 逐元素计算负数
    """

    def __init__(self, x):
        """ 构造负运算

        参数列表:
          x: 输入节点
        """
        super().__init__([x])

    def compute(self, x_value):
        """ 计算负运算 operation 的输出

        参数列表:
          x_value: 输入值
        """
        return -x_value

class reduce_sum(Operation):
    """ 计算张量中元素延某一或某些维度的总和
    """

    def __init__(self, A, axis=None):
        """ 构造 reduce_sum

        参数列表:
          A: 要进行 reduce 运算的张量
          axis: 需要 reduce 的维度，如果 `None`（即缺省值），则延所有维度 reduce
        """
        super().__init__([A])
        self.axis = axis

    def compute(self, A_value):
        """ 计算 reduce_sum operation 的输出值

        参数列表:
          A_value: 输入的张量值
        """
        return np.sum(A_value, self.axis)

class softmax(Operation):
    """返回 a 的 softmax 函数结果.
    """

    def __init__(self, a):
        """构造 softmax

        参数列表:
          a: 输入节点
        """
        super().__init__([a])

    def compute(self, a_value):
        """计算 softmax operation 的输出值

        参数列表:
          a_value: 输入值
        """
        return np.exp(a_value) / np.sum(np.exp(a_value), axis=1)[:, None]

from queue import Queue

class GradientDescentOptimizer:
    def __init__(self, learning_rate):
        self.learning_rate = learning_rate

    def minimize(self, loss):
        learning_rate = self.learning_rate

        class MinimizationOperation(Operation):
            def compute(self):
                # 计算梯度
                grad_table = compute_gradients(loss)

                # 遍历所有节点
                for node in grad_table:
                    if type(node) == Variable:
                        # 找到节点对应的梯度
                        grad = grad_table[node]

                        # 沿着负梯度的方向进行一步迭代
                        node.value -= learning_rate * grad

        return MinimizationOperation()

На рисунке ниже изображен итеративный процесс градиентного спуска. Сначала мы случайным образом находим разделительную линию (обозначенную цифрой 1), продвигаемся вперед на один шаг и находим чуть лучшую линию (обозначенную цифрой 2). Продолжайте шаг за шагом, пока не найдете хорошую разделительную линию.

## Обратное распространение

В приведенной выше реализации градиентного спуска мы использовалиcompute_gradient(loss)функция для расчета计算图середина,loss operationО других узлахn 的输出из梯度(То есть направление, в котором потери увеличиваются быстрее всего, а направление, противоположное градиенту, — это направление, в котором потери уменьшаются быстрее всего).

Рассмотрим следующий вычислительный граф:

По цепному правилу производных можно получить:

`[math] \frac{\partial e}{\partial a} = \frac{\partial e}{\partial b} \cdot \frac{\partial b}{\partial a} = \frac{\partial e}{\partial c} \cdot \frac{\partial c}{\partial b} \cdot \frac{\partial b}{\partial a} = \frac{\partial e}{\partial d} \cdot \frac{\partial d}{\partial c} \cdot \frac{\partial c}{\partial b} \cdot \frac{\partial b}{\partial a} [/math] `

Отсюда видно, что для расчетаоГрадиент , мы хотим начать сначать, работать в обратном порядке, для каждого узла на этом пути вычисляйте градиент его выхода по отношению к входу, один за другим, пока. Затем умножьте все градиенты.

Рассмотрим этот сценарий еще раз:

В этом случае изприбытьЕсть два пути: a, b, d, e и a, c, d, e . следовательно,оизполный дифференциалМетод заключается в следующем:

`[math] \frac{\partial e}{\partial a} = \frac{\partial e}{\partial d} \cdot \frac{\partial d}{\partial a} = \frac{\partial e}{\partial d} \cdot (\frac{\partial d}{\partial b} \cdot \frac{\partial b}{\partial a} + \frac{\partial d}{\partial c} \cdot \frac{\partial c}{\partial a}) = \frac{\partial e}{\partial d} \cdot \frac{\partial d}{\partial b} \cdot \frac{\partial b}{\partial a} + \frac{\partial e}{\partial d} \cdot \frac{\partial d}{\partial c} \cdot \frac{\partial c}{\partial a} [/math] `

Отсюда мы можем вывести общий алгоритм вычисления градиента потерь по отношению к узлу: начиная с узла, представляющего потери, и выполняя поиск в ширину в обратном порядке. Каждый раз при посещении узлаn, даже если потеря составляет околоn 的输出Градиент , где градиент проходит через пару узловnКаждый потребительский узелc(Потребительский узел — это узелcк узлуnвывод в качестве ввода) выполните следующие действия:

получить потерю оcвыходной градиентG
будетGездить наcВыход примерноnГрадиент выхода

Затем мы складываем эти градиенты.

Существует предварительное условие для реализации обратного распространения, нам нужно указать функцию для каждой операции, которая вычисляет градиент по отношению к каждому входу операции, беря градиент по отношению к выходу операции.

Для этого мы сначала определяем декоратор@RegisterGradient(operation_name):

# operation 到对应梯度计算函数的映射
_gradient_registry = {}


class RegisterGradient:
    """装饰器，用来给 op type 注册梯度计算函数
    """

    def __init__(self, op_type):
        """创建一个装饰器实例，以 op_type 作为 Operation type
        参数列表:
          op_type: operation 的名字
        """
        self._op_type = eval(op_type)

    def __call__(self, f):
        """把函数 `f` 注册为 `op_type`的梯度计算函数"""
        _gradient_registry[self._op_type] = f
        return f

Теперь предположим, что содержимое словаря _gradient_registry заполнено, поэтому давайте реализуем обратное распространение:

from queue import Queue


def compute_gradients(loss):
    # 可以通过 grad_table[node] 取出损失关于节点输出的梯度
    grad_table = {}

    # 损失关于损失的梯度是 1
    grad_table[loss] = 1

    # 从损失节点开始，反向进行广度优先搜索
    visited = set()
    queue = Queue()
    visited.add(loss)
    queue.put(loss)

    while not queue.empty():
        node = queue.get()

        # 如果节点不是损失节点
        if node != loss:
            #
            # 计算损失关于节点输出的梯度
            #
            grad_table[node] = 0

            # 遍历所有消费节点
            for consumer in node.consumers:

                # 取出损失关于消费节点的输出的梯度
                lossgrad_wrt_consumer_output = grad_table[consumer]

                # 取出根据关于消费者节点的输出的梯度，计算关于消费者节点的输入的梯度的函数
                consumer_op_type = consumer.__class__
                bprop = _gradient_registry[consumer_op_type]

                # 得到损失关于消费节点所有的输入的梯度
                lossgrads_wrt_consumer_inputs = bprop(consumer, lossgrad_wrt_consumer_output)

                if len(consumer.input_nodes) == 1:
                    # 如果消费节点只有一个输入节点，lossgrads_wrt_consumer_inputs 就是标量
                    grad_table[node] += lossgrads_wrt_consumer_inputs

                else:
                    # 否则，lossgrads_wrt_consumer_inputs 是对各个输入节点的梯度的数组

                    # 取得该节点在消费节点的输入节点中的序列
                    node_index_in_consumer_inputs = consumer.input_nodes.index(node)

                    # 得到损失关于节点的梯度
                    lossgrad_wrt_node = lossgrads_wrt_consumer_inputs[node_index_in_consumer_inputs]

                    # 加到关于这个节点的总梯度中
                    grad_table[node] += lossgrad_wrt_node

        #
        # 把每个输入节点加入队列
        #
        if hasattr(node, "input_nodes"):
            for input_node in node.input_nodes:
                if not input_node in visited:
                    visited.add(input_node)
                    queue.put(input_node)

    # 返回所有关于已访问过节点的梯度
    return grad_table

### Расчет градиента, соответствующий каждой операции

Для каждой операции нам нужно определить функцию, которая преобразует градиент потерь по отношению к выходу операции в градиент потерь по отношению к каждому входному узлу операции, и сохранить их в списке. Вычисление градиента по матрице скучно, поэтому давайте проигнорируем процесс и просто приведу результат. Пропуск этого раздела не повлияет на ваше общее понимание.

Если вы хотите знать, как получить этот результат, общий процесс таков:

Найдите частные производные каждого выходного значения по каждому входному значению (вероятно, тензор порядка больше 2, то есть ни скаляр, ни вектор, ни матрица, предполагающая много суммирования)
Используя цепное правило, градиент по отношению к входу узла вычисляется из градиента по отношению к выходу узла. Результатом будет тензор той же формы, что и входной тензор, то есть, если вход является матрицей, результатом также будет матрица.
Запишите результат в виде ряда матричных операций, чтобы повысить эффективность вычислений. Этот шаг немного сложен.

Расчет градиента, соответствующий отрицательной операции

известно оградиент, тогда оГрадиент.

@RegisterGradient("negative")
def _negative_gradient(op, grad):
    """计算 `negative` 的梯度

    参数列表:
      op: 我们要单独处理的 `negative` Operation
      grad: 关于这个 `negative` operation 的梯度

    返回值:
      关于 `negative` 的输入的梯度
    """
    return -grad

вычисление логарифмического градиента

известно о log(x) градиент, тогда оГрадиент $\frac{G}{x}$ .

@RegisterGradient("log")
def _log_gradient(op, grad):
    """计算 `log` 的梯度。

    参数列表:
      op: 要处理的 `log` Operation
      grad: 关于 `log` operationa 的输出的梯度

    返回值:
      关于 `log` 的输入的梯度
    """
    x = op.inputs[0]
    return grad/x

Расчет градиента, соответствующий умножению

известно о $A \odot B$ градиент, тогда оГрадиент $G \odot B$ ,оГрадиент $G \odot A$ .

@RegisterGradient("multiply")
def _multiply_gradient(op, grad):
    """计算 `multiply` 的梯度。

   参数列表:
      op: 要处理的 `multiply` Operation
      grad: 关于 `multiply` operationa 的输出的梯度

    返回值:
      关于 `multiply` 的输入的梯度
    """

    A = op.inputs[0]
    B = op.inputs[1]

    return [grad * B, grad * A]

Градиентная операция, соответствующая matmul

известно оградиент, тогда оГрадиент GB^T ,оГрадиент A^TG .

@RegisterGradient("matmul")
def _matmul_gradient(op, grad):
    """计算 `matmul` 的梯度。

    参数列表:
      op: 要处理的 `matmul` Operation
      grad: 关于 `matmul` operationa 的输出的梯度

    返回值:
      关于 `matmul` 的输入的梯度
    """

    A = op.inputs[0]
    B = op.inputs[1]

    return [grad.dot(B.T), A.T.dot(grad)]

Операция градиента, соответствующая добавлению

известно о a + b Градиент, тогда оГрадиент,оГрадиент также. следовательноиформа такая же.

еслииразличные формы, такие как матрицыКоличество строк 100, векторКоличество строк равно 1, тогда a + b что будетдобавить вна каждой строке. В этом случае расчет градиента будет немного сложнее, и мы не будем здесь его подробно раскрывать.

@RegisterGradient("add")
def _add_gradient(op, grad):
    """计算 `add` 对应的梯度

    参数列表:
      op: 要处理的 `add` Operation
      grad: 关于 `add` operationa 的输出的梯度

    返回值:
      关于 `add` 的输入的梯度
    """
    a = op.inputs[0]
    b = op.inputs[1]

    grad_wrt_a = grad
    while np.ndim(grad_wrt_a) > len(a.shape):
        grad_wrt_a = np.sum(grad_wrt_a, axis=0)
    for axis, size in enumerate(a.shape):
        if size == 1:
            grad_wrt_a = np.sum(grad_wrt_a, axis=axis, keepdims=True)

    grad_wrt_b = grad
    while np.ndim(grad_wrt_b) > len(b.shape):
        grad_wrt_b = np.sum(grad_wrt_b, axis=0)
    for axis, size in enumerate(b.shape):
        if size == 1:
            grad_wrt_b = np.sum(grad_wrt_b, axis=axis, keepdims=True)

    return [grad_wrt_a, grad_wrt_b]

Градиентная операция, соответствующая reduce_sum

известно о reduce_sum Градиент выхода, то на входеГрадиент повторяется вдоль указанной оси.

@RegisterGradient("reduce_sum")
def _reduce_sum_gradient(op, grad):
    """计算 `reduce_sum` 对应的梯度

    参数列表:
      op: 要处理的 `reduce_sum` Operation
      grad: 关于 `reduce_sum` operationa 的输出的梯度

    返回值:
      关于 `reduce_sum` 的输入的梯度
    """
    A = op.inputs[0]

    output_shape = np.array(A.shape)
    output_shape[op.axis] = 1
    tile_scaling = A.shape // output_shape
    grad = np.reshape(grad, output_shape)
    return np.tile(grad, tile_scaling)

Градиентная операция, соответствующая softmax

@RegisterGradient("softmax")
def _softmax_gradient(op, grad):
    """计算 `softmax` 对应的梯度

    参数列表:
      op: 要处理的 `softmax` Operation
      grad: 关于 `softmax` operationa 的输出的梯度

    返回值:
      关于 `softmax` 的输入的梯度
    """

    softmax = op.output
    return (grad - np.reshape(
        np.sum(grad * softmax, 1),
        [-1, 1]
    )) * softmax

### Пример

Теперь попробуйте приведенный выше код и посмотрите, какие оптимальные веса для персептрона мы можем получить.

# 创建一个新 Graph
Graph().as_default()

X = placeholder()
c = placeholder()

# 随机初始化权重
W = Variable(np.random.randn(2, 2))
b = Variable(np.random.randn(2))

# 搭建感知机
p = softmax(add(matmul(X, W), b))

# 搭建交叉熵损失
J = negative(reduce_sum(reduce_sum(multiply(c, log(p)), axis=1)))

# 搭建最小化 operation
minimization_op = GradientDescentOptimizer(learning_rate=0.01).minimize(J)

# 搭建占位输入
feed_dict = {
    X: np.concatenate((blue_points, red_points)),
    c:
        [[1, 0]] * len(blue_points)
        + [[0, 1]] * len(red_points)

}

# 创建会话
session = Session()

# 执行 100 步梯度下降迭代
for step in range(100):
    J_value = session.run(J, feed_dict)
    if step % 10 == 0:
        print("Step:", step, " Loss:", J_value)
    session.run(minimization_op, feed_dict)

# 打印最终结果
W_value = session.run(W)
print("Weight matrix:\n", W_value)
b_value = session.run(b)
print("Bias:\n", b_value)

Обратите внимание, что теперь мы начинаем с довольно высокого убытка, а затем позволяем убытку быстро снижаться.

Наконец, давайте нарисуем окончательную разделительную линию:

import matplotlib.pyplot as plt
[/amalthea_pre_exercise_code]
[amalthea_sample_code]
W_value =  np.array([[ 1.27496197 -1.77251219], [ 1.11820232 -2.01586474]])
b_value = np.array([-0.45274057 -0.39071841])

# 画出直线 y = -x
x_axis = np.linspace(-4, 4, 100)
y_axis = -W_value[0][0]/W_value[1][0] * x_axis - b_value[0]/W_value[1][0]
plt.plot(x_axis, y_axis)

# 把红 / 蓝点画上去
plt.scatter(red_points[:,0], red_points[:,1], color='red')
plt.scatter(blue_points[:,0], blue_points[:,1], color='blue')
plt.show()

Если у вас есть какие-либо вопросы, пожалуйста, задавайте в комментариях.

Если вы хотите попробовать, можете ли вы перейти в индустрию искусственного интеллекта, нажмите справа:Класс ИИ Цзижи