作者归档:admin

反向传播算法—从四个基本公式说起

enter image description here
enter image description here

反向传播四公式:

enter image description here
enter image description here

  反向传播的最终目的是求得使代价C最小时w、b的最佳值,为了方便计算引入了神经单元误差δ_j^l,其定义为误差C关于某个神经单元z的关系;
enter image description here
  其定义如上所示,某神经元误差为代价C(总误差)关于z的偏导数,其中l为神经网络的层数,j为第几个神经元;
  这里的代价函数(损失函数)使用的是平方误差,因此C等于:
enter image description here

BP1

  此公式用于求神经网络最后一层神经元的误差,下面通过BP1公式用于求最后一层神经元(输出层)中第一个神经元的误差;
enter image description here

根据链式法则由此可得到上诉四个公式中得前面BP1

enter image description here
BP1中得L为神经网络得最后一层,而在我们此网络中最后一层为3,所以此处L=3;

BP2

  BP2与BP1类似,不同得是BP1用于求最后一层神经元误差,而BP2则是用于求L层前面某一层得神经元误差,下面通过BP2公式用于求第二层神经元中的第一个神经元的误差;
同样我们也可通过链式法则得出:
enter image description here
有:
enter image description here
因此可以得:
enter image description here
将公式转换为矩阵模式,第2层神经元得误差为:
enter image description here
我们将BP1与BP2带入即可得到BP3与BP4;
通过BP1与BP2公式即可通过BP3、BP4轻松得到w与B;

BP3

此公式用于求误差C关于某个权重的偏导数,在求得BP2后此处只需吧BP2带入到公式即可求得BP3;
enter image description here

BP4

  求误差C关于偏置b的偏导数,BP4与BP3一样得到BP2即可带入得出BP4;
enter image description here
  反向传播算法给出了一种用于计算代价函数(损失函数)梯度得方法,具体步骤如下:
enter image description here

数据计算

enter image description here

一、前向传播

1、计算第二层
  矩阵形式:
enter image description here
enter image description here
2、计算第三层
  矩阵形式:
enter image description here

二、计算误差

当前使用的为平方损失函数(代价函数);
enter image description here

三、计算输出层神经元误差

矩阵形式:
enter image description here
  输出层第一个神经元误差δ_1^3:
enter image description here
  输出层第一个神经元误差δ_2^3:
enter image description here

四、计算其余层神经元误差

矩阵形式:
enter image description here

五、计算误差C关于w、b的梯度

  此处用的是BP3与BP4公式,在计算出BP1与BP2后将其带入到公式中即可计算出C关于w、b的梯度;
矩阵形式:
enter image description here
矩阵形式:
enter image description here
更新w、b公式:
enter image description here
  在计算出误差C关于每个权重每个偏置的偏导数后再使用得到的值带入上述公式更新每一个w、b即可,在更新完成w、b后如误差达到指定精度或epochs则继续执行上述的2-5步骤直到误差满意或指定epochs为止;

再回首数据结构—红黑树(一)

  红黑树与AVL树一样同为二分搜索树,红黑树又称为是保持“黑平衡”的二叉树,红黑树最大高度为:2logn,红黑树由这么几个独特的特征:
  1、每个节点或黑或红
  2、根节点为黑色
  3、每个叶子节点(最后的空节点)都为黑色
  4、如果一个节点为红色,则他孩子节点全为黑色
  5、从任意节点到叶子节点,经过的黑色节点为一样多的
  6、所有红色节点都向左倾斜

enter image description here

  在之前的二叉搜索树中我们在实现的节点结构中定义了用于存储元素的e、用于存放左子树的left、用于存放右子树的right等对象,而在AVL树中比二叉搜索树有所不同由于AVL需要维护左右子树的节点高度所以多了一个元素height用于存放节点的高度;
  红黑树也是基于之前二叉搜索树变体而来的,在红黑树中节点也只比二叉搜索树多一个元素,二叉搜索树的节点由以下元素组成:

  e :用于存储节点元素
  left: 用于存储左子树
  right:用于存储右子树
  color:用于标志节点颜色,节点是红色或黑色

红黑树的代码定义:

 type RBT struct {
    root    *RBTNode
    size    int
    compare Comparable
 }

 type RBTNode struct {
    e     interface{}
    left  *RBTNode
    right *RBTNode
    color bool
 }

根据红黑树的特性、定义可知:
  1、大小为N的红黑树其高度不超过2logN
  2、最坏情况下插入、查找元素的时间复杂度为:2logN
  3、平均情况下插入、查找元素的平均复杂度为:logN

  这里只简单介绍了红黑树的相关概念,下面将从代码实现的角度具体分析红黑树的实现;