RNN原理介绍以及二进制加法器

前言：神经网络拓扑学&convJS

两个博客的动图形象的展示了神经网络内部的工作过程。

https://colah.github.io/posts/2014-03-NN-Manifolds-Topology/
https://cs.stanford.edu/people/karpathy/convnetjs/

RNN（Recurrent Neural Network）

为了简易教学过程，我会从“简易”的RNN模型逐渐过渡到“真实”的RNN模型

为什么会有RNN？

类比人类的思考过程。人们对新事物的思考总是包含着先验知识（记忆）的
尝试从后向前背字母表的十分困难的，因为人类总是以序列为单位记忆。（就像链表）

RNN长成什么样？

由上图可见，RNN的信息流是：

RNN中的记忆代表prev_hidden（之前的隐层“记忆”）也被当做了输入用来训练神经网络！

注意区分上图：一个RNN可以看作数多个相同神经网络的复制版本！

假设我们有一个时间步长为4的RNN，那么它的信息流就是

让我们形象的看看“记忆”是如何影响RNN的

RNN可以解决什么问题？

时间序列和列表模型：语音识别，语言模型，翻译，图像捕捉等

RNN有什么缺点吗？

the clouds are in the sky
I grew up in France… I speak fluent French.

长期依赖：当gap越来越大，RNN就不太可能学习有用的信息了

如何解决长期依赖？

看看我们大脑是如何工作的：我们的大脑有遗忘的功能，即只记住记忆中关键的信息点，而不去存储完整的记忆。这种功能让我们大脑的计算负荷大大减少。—-于是LSTM诞生了

LSTM （Long Short Term Memory）

LSTM与RNN的结构差异

LSTM将RNN的单层神经网络变成了四层神经网络

wtf?赶快讲讲细节

我们在图中有以下约定：

图中的线条代表一个完整的向量
粉色圆圈代表一个向量操作

LSTM的核心思想

上图表示LSTM有能力给Cell state添加或者删除信息（这些能力被一种叫做gates的结构控制）
gates:一条信息经过的路径由运算函数和sigmoid函数构成

补充：重新认识sigmoid函数：

$$S(x)= \frac{1}{1+e^{-x}}$$

$$S^{‘}{(x)}=\frac{e^{-x}}{(1+e^{-x})^2}=S(x)(1-S(x))$$

　很明显，其作用是把x映射到$[0,1]$：0表示忘记，1表示记住

LSTM的具体工作流程

LSTM第一步便是决定从cell state中丢弃的信息(由sigmoid函数完成)

$$f_t=\sigma(Wf·[h{t-1},x_t] + b_f)$$

LSTM第二步是决定将那些新信息保存至cell state
- sigmoid层决定更新哪些值
- tanh层则负责创建一个新的候选值
  
  $$i_t = \sigma(Wi·[h{t-1},x_t]+b_i)$$
  
  $$\hat{C_t}=tanh(WC·[h{t-1},x_t]+b_C)$$

更新$C_{t-1}$为新的$C_t$

$$C_t=ft * C{t-1}+i_t * \hat{C_t}$$

LSTM决定输出值
- 使用sigmoid层决定那一部分用作输出
- 通过tanh和部分输出决定总输出

$$o_t=\sigma(Wo[h{t-1},x_t]+b_o)$$

$$h_t = o_t *tanh(C_t)$$

回归RNN，我们来简单的描述下RNN梯度下降的过程

简单介绍传统神经网络的反向传播算法

再来看看真实的RNN到底是什么样子的

我们约定图中符号为：

t时刻的输入：$x^t\in R^{xdim}$
隐层节点的输出：$h^t\in R^{hdim}$
输出层的预测值:$y^t\in R^{ydim}$
从输入到隐层的权重矩阵：$V\in R^{xdim·ydim}$
隐层的自循环矩阵:$U\in R^{hdim·hdim}$
隐层到输出层的权重矩阵:$W\in R^{hdim·ydim}$
各层对应的偏置向量: $b_h\in R^{hdim},b_y\in R^{ydim}$
输入层、隐层、输出层的节点为标识为$i、j、k$
真实的输出：$d^t\in R^{ydim}$

正向传播

$h^t=activate_1(x^tV+h^{t-1}U+b_h)$，其中令$net_h^t=x^tV+h^{t-1}U+b_h$
$y^t=activate_2(h^tW+b_y)$,其中令$net_y^t=h^tW+b_y$
定义单个时间节点$p$的误差为
$$E^t=\sum_p\frac{1}{2}||d^t-y^t||^2$$
则有总误差为

$$E=\sum_tE^t=\frac{1}{2}\sump{\sum^T{t=1}||y^t-d^t||^2}$$

反向传播：Backpropation Through Time(BPTT)

计算RNN内参数的梯度
$$\delta^t{yk}=\frac{\partial{E}}{\partial{net^t{yk}}}，\delta^t{hj}=\frac{\partial{E}}{\partial^t{hj}}$$

这两个偏导数是为：总误差分别对第t个时间节点的输出层的第k个节点&隐藏层的第j个节点的偏导数

展开则有：

$$\delta^t_{yk}={\frac{\partial{E}}{\partial{y^t_k}}}{\frac{\partial{y^tk}}{\partial{net^t{yk}}}}=(y^t_k-d^tk){g^{‘}(net^t{yk})}$$

将上式向量化表示有：
$$\delta_y^t=(y^t-d^t)\circ{g^{‘}(net^t_y)}, \circ表示对应元素相乘而非矩阵乘法$$
$$\delta_h^t=(W(\delta_y^t)^T+U(\delta^{t+1}_h)^T)^T\circ{f^{‘}(net^t_h)}$$
由此可得各个参数的梯度为：
$$\Delta{W}=\sum_t{(h^{t})^T\delta^t_y}$$

$$\Delta{U}=\sum_t{(h^{t-1})^T\delta^t_h}$$

$$\Delta{V}=\sum_t{(x^t)^T\delta^t_h}$$

$$\Delta{by}=\sum_t{\delta^t_y}$$

$$\Delta{bh}=\sum_t{\delta^t_h}$$

注意：从上图中可以很明显的观察到计算t时刻的梯度时，需要用到$t-1，t-2,…$时刻计算得到的梯度。

来用python写一个小demo（二进制加法器）试试？

我们的目标：

我们想要完成一个八位二进制加法器：进位从第三位开始！这个加法器可以直接预测两个八位二进制数的结果，并且我们想要RNN学会是否进位这个“记忆”。

#!/usr/bin/env python
# -*- coding: utf-8 -*-
# @Author  : zzy824
# @File    : traskRNNTutorial.py

import numpy as np
np.random.seed(0)

# compute sigmoid nonlinearity
def sigmoid(x):
    output = 1 / (1 + np.exp(-x))
    return output

# convert output of sigmoid function to its derivative
def sigmoid_output_to_derivative(output):
    return output * (1 - output)
#!/usr/bin/env python
# -*- coding: utf-8 -*-
# @Time    : 2018/4/24 下午2:43
# @Author  : zzy824
# @File    : traskRNNTutorial.py

import numpy as np
np.random.seed(0)

# compute sigmoid nonlinearity
def sigmoid(x):
    output = 1 / (1 + np.exp(-x))
    return output

# convert output of sigmoid function to its derivative
def sigmoid_output_to_derivative(output):
    return output * (1 - output)

# training dataset generation
int2binary = {}
binary_dim = 8

largest_number = pow(2, binary_dim)
binary = np.unpackbits(np.array([range(largest_number)], dtype=np.uint8).T, axis=1)
for i in range(largest_number):
    int2binary[i] = binary[i]

# input variables
alpha = 0.1
input_dim = 2 # because we add two number 
hidden_dim = 16 
output_dim = 1

# initialize neural network weights
synapse_0 = 2 * np.random.random((input_dim, hidden_dim)) - 1 # input&hidden
synapse_1 = 2 * np.random.random((hidden_dim, output_dim)) - 1 # hidden&output
synapse_h = 2 * np.random.random((hidden_dim, hidden_dim)) - 1 # hidden&hidden

synapse_0_update = np.zeros_like(synapse_0)
synapse_1_update = np.zeros_like(synapse_1)
synapse_h_update = np.zeros_like(synapse_h)

# training logic
for j in range(10000):

    # generate a simple addition problem (a + b = c)
    a_int = np.random.randint(largest_number / 2)  # int version
    a = int2binary[a_int]  # binary encoding
    b_int = np.random.randint(largest_number / 2)  # int version
    b = int2binary[b_int]  # binary encoding

    # true answer
    c_int = a_int + b_int
    c = int2binary[c_int]

    # where we'll store our best guess (binary encoded)
    d = np.zeros_like(c)

    overallError = 0

    layer_2_deltas = list()
    layer_1_values = list()
    layer_1_values.append(np.zeros(hidden_dim))

    # moving along the positions in the binary encoding
    for position in range(binary_dim):

        # generate input and output
        X = np.array([[a[binary_dim - position - 1], b[binary_dim - position - 1]]])
        y = np.array([[c[binary_dim - position - 1]]]).T

        # hidden layer (input ~+ prev_hidden)
        layer_1 = sigmoid(np.dot(X, synapse_0) + np.dot(layer_1_values[-1], synapse_h))

        # output layer (new binary representation)
        layer_2 = sigmoid(np.dot(layer_1, synapse_1))

        # did we miss?... if so, by how much?
        layer_2_error = y - layer_2
        layer_2_deltas.append(layer_2_error * sigmoid_output_to_derivative(layer_2))
        overallError += np.abs(layer_2_error[0])

        # decode estimate so we can print it out
        d[binary_dim - position - 1] = np.round(layer_2[0][0])
        # store hidden layer so we can use it in the next timestep
        layer_1_values.append(copy.deepcopy(layer_1))

    future_layer_1_delta = np.zeros(hidden_dim)

    for position in range(binary_dim):
        X = np.array([[a[position], b[position]]])
        layer_1 = layer_1_values[-position - 1]
        prev_layer_1 = layer_1_values[-position - 2]

        # error at output layer
        layer_2_delta = layer_2_deltas[-position - 1]
        # error at hidden layer
        layer_1_delta = (future_layer_1_delta.dot(synapse_h.T) + layer_2_delta.dot(synapse_1.T)) * sigmoid_output_to_derivative(
            layer_1)

        # let's update all our weights so we can try again
        synapse_1_update += np.atleast_2d(layer_1).T.dot(layer_2_delta)
        synapse_h_update += np.atleast_2d(prev_layer_1).T.dot(layer_1_delta)
        synapse_0_update += X.T.dot(layer_1_delta)

        future_layer_1_delta = layer_1_delta

        synapse_0 += synapse_0_update * alpha
        synapse_1 += synapse_1_update * alpha
        synapse_h += synapse_h_update * alpha

        synapse_0_update *= 0
        synapse_1_update *= 0
        synapse_h_update *= 0
        # print out progress
        if j % 1000 == 0:
            print "Error:" + str(overallError)
            print "Pred:" + str(d)
            print "True:" + str(c)
            out = 0
            for index, x in enumerate(reversed(d)):
                out += x * pow(2, index)
            print str(a_int) + " + " + str(b_int) + " = " + str(out)
            print "------------"

引用与参考资料

pytorch官方文档：http://pytorch.org/tutorials/

pytorch官方项目样例：https://github.com/pytorch/examples

colah博客：https://colah.github.io/posts/2015-08-Understanding-LSTMs/

RNN求解过程：https://www.cnblogs.com/YiXiaoZhou/p/6058890.html

i am trask博客: https://iamtrask.github.io/2015/11/15/anyone-can-code-lstm/

反向传播算法图来源：https://zhuanlan.zhihu.com/p/31623305