[人工智能]神经网络基础+Leetcode(118119121)

神经网络与BP算法

1. 神经网络的基础

1.1 神经元模型

一般神经网络都会非常大，所以神经元定义要尽量的简单。一般用一个线性组合+激活函数来表示，如下图所示。

(1)线性组合部分为：
偏置项隐含表示在x0里，即偏置项=1*w0
(2)激活函数部分在这里是一个阶跃函数（实际上激活函数类型有很多在1.1.2介绍）：
所以综上根据神经元模型：f(x)=f(g(x))的原则得到神经元模型如下：
那么我们可以理解成线性组合表示刺激的大小，而激活函数定义了多大刺激可以激活神经元，最终神经元就表示了这样。
其实这就是个感知机（感知器）：一般指单层感知器，它是指只含有输入层和输出层的神经网络。

1.1.1 偏置项b

1、什么是bias？
偏置单元（bias unit），在有些资料里也称为偏置项（bias term）或者截距项（intercept term），它其实就是函数的截距，与线性方程 y=wx+b 中的 b 的意义是一致的。在 y=wx+b中，b表示函数在y轴上的截距，控制着函数偏离原点的距离，其实在神经网络中的偏置单元也是类似的作用。
因此，神经网络的参数也可以表示为：(W, b)，其中W表示参数矩阵，b表示偏置项或截距项。

2、bias的计算方式或者说表现形式？

神经网络结构中对偏置单元的计算处理方式有两种，
　（1）设置偏置单元=1，并在参数矩阵 W 中设置第 0 列对应偏置单元的参数，对应的神经网络如下：
　
激活值a1计算公式：

相当于bias本身值为1，但它连接各个神经元的权重不为1，即—整个神经网络只有1个bias，对应有多个不同的权重（权重个数等于hide层和out层神经元的个数）

（2）设置偏置单元，不在参数矩阵中设置对应偏置单元的参数，对应的神经网络如下：

激活值计算公式：
相当于bias连接各个神经元的所有权重都为1，但bias本身不为1，即—有多个bias，但所有的bias对应的权重都为1（bias的个数等于hide层和out层神经元的个数）

3.每个神经元为什么要加上偏置项？
先不说为什么一定要加入偏置 b, 就还是上面的分类问题，假如我现在的样本点是如下这种：

此时希望得到的线性方程分割线是能够正确的将俩类进行分开，如下图所示：
如分割线如果没有偏置的话，所有的分割线都是经过原点的，但是上图样本点不是能够是经过原点线性可分的，所以一定要加上偏置。要是把偏置项给漏掉了，那么神经网络很有可能变得很差，收敛很慢而且精度差，甚至可能陷入“僵死”状态无法收敛。

1.1.2激活函数介绍g(x)

注意激活函数需要处处可导

1.什么是激活函数以及为什么需要激活函数？
激活函数是用来加入非线性因素的，解决线性模型所不能解决的问题。
下面举一个简单的例子来解释为什么需要激活函数，以及激活函数的作用：
如我要将下面的三角形和圆形点进行正确的分类
很容易能够看出，这些给出的样本点根本不是线性可分的，一个感知器得到的一条直线怎么动，都不可能完全正确的将三角形与圆形区分出来

那么首先再不提出激活函数的情况下，我们首先会想到用多个感知器（如下图）来进行组合，以便获得更大的分类问题如下所示：
从上图我们可以得到一个多感知器分类器，那么这个分类器可以解决我们的样本点分类问题吗？
很简单我们先把这个分类器公式如下

转换一下得到：
显而易见，其实这得到的分类器本质还是一个线性方程也就是一条直线，该处理不了的非线性问题，它还是处理不了

那么我们接下来引入激活函数的概念，首先确定一点，激活函数一定是非线性的！！！
然后我们把激活函数加入到感知器模型中：
可以分析通过这个激活函数映射之后，输出很明显就是一个非线性函数！能不能解决一开始的非线性分类问题不清楚，但是至少说明已经有解决的可能性了。
当我们把激活函数加入到多感知器分类器（即扩展到多个神经元组合的情况时候）的时候，这个结果就会更明显：
假设σ(.)是阶跃函数，我们可能会得到如下结果：
假设激活函数是sigmoid函数时，我们可能会得到如下结果：
可以看到都可以对样本点进行很好的分类了，这就是激活函数的作用。

2.激活函数有哪些？
常用的激活函数有如下几种：
（1）sigmoid函数
（2）tanh函数
（3）ReLU函数(原始的Relu和改进型的PReLU以及ELU)
下面一一介绍
（1）sigmoid函数
该函数是将取值为 (?∞,+∞) 的数映射到 (0,1) 之间。sigmoid函数的公式以及图形如下：
sigmoid函数作为非线性激活函数，但是其并不被经常使用，它具有以下几个缺点：
第一点：当 z 值非常大或者非常小时，通过上图我们可以看到，sigmoid函数的导数 g′(z) 将接近 0 。这会导致权重 W 的梯度将接近 0 ，使得梯度更新十分缓慢，即梯度消失。
第二点：函数的输出不是以0为均值，将不便于下层的计算

sigmoid函数可用在网络最后一层，作为输出层进行二分类，尽量不要使用在隐藏层。

（2）tanh函数
tanh函数相较于sigmoid函数要常见一些，该函数是将取值为 (?∞,+∞) 的数映射到 (?1,1) 之间，其公式与图形为：
tanh函数在 0 附近很短一段区域内可看做线性的。
tanh函数的缺点同sigmoid函数的第一个缺点一样，当 z 很大或很小时，g′(z) 接近于 0 ，会导致梯度很小，权重更新非常缓慢，即梯度消失问题。
但是由于tanh函数均值为 0 ，因此弥补了sigmoid函数均值为 0.5 的缺点。

（3）Relu函数
ReLU函数又称为修正线性单元（Rectified Linear Unit），是一种分段线性函数，其弥补了sigmoid函数以及tanh函数的梯度消失问题。ReLU函数的公式以及图形如下：
ReLU函数的优点：
第一点：在输入为正数的时候（对于大多数输入 z 空间来说），不存在梯度消失问题。
第二点：计算速度要快很多。ReLU函数只有线性关系，不管是前向传播还是反向传播，都比sigmod和tanh要快很多。（sigmod和tanh要计算指数，计算速度会比较慢）

ReLU函数的缺点：
当输入为负时，梯度为0，会产生梯度消失问题。

（4）Leaky ReLU函数（PReLU）
是一种对ReLU函数改进的函数，又称为PReLU函数，但其并不常用。其公式与图形如下：
相比ReLU，Leaky-ReLU在输入为负数时引入了一个很小的常数，如0.01，这个小的常数修正了数据分布，保留了一些负轴的值，在Leaky-ReLU中，这个常数通常需要通过先验知识手动赋值。Leaky ReLU函数解决了ReLU函数在输入为负的情况下产生的梯度消失问题。

（5）ELU (Exponential Linear Units) 函数Leaky ReLU函数解决了ReLU函数在输入为负的情况下产生的梯度消失问题，而且均值更接近于0。
它的一个小问题在于计算量稍大。类似于Leaky ReLU，理论上虽然好于ReLU，但在实际使用中目前并没有好的证据ELU总是优于ReLU。

1.2 神经网络基础结构

神经网络是由大量神经元节点按一定体系架构连接成的网状结构，一般都有输入层，隐含层和输出层三部分组成，如下图所示。
传统的浅层网络，一般都是3~5层
对于神经网络有以下一些概念：
（1）如上图中的每个圆圈，都代表一个神经元，也叫节点(Node)。
（2）输出层可以是单个节点也可以是多个节点，多节点输出常常用于分类问题。
（3）任何多层网络可以用三层网络（输入层，隐含层和输出层）近似地表示。
（4）一般凭经验来确定隐含层到底应该有多少个节点，在测试的过程中也可以不断调整节点数以取得最佳效果。

1.3 单向前馈神经网络

1.3.1 前馈神经网络的定义

所谓的前馈神经网络（全连接神经网络或者多层感知机（MLP））就是每层神经元与下层神经元相互连接，神经元之间不存在同层连接，也不存在跨层连接。
就是各神经元从输入层开始，接收前一级输入，并输出到下一级，直至输出层。整个网络中无反馈，可用一个有向无环图表示。前馈神经网络采用一种单向多层结构。其中每一层包含若干个神经元，同一层的神经元之间没有互相连接，层间信息的传送只沿一个方向进行。
其中第一层称为输入层。最后一层为输出层．中间为隐含层。隐含层可以是一层，也可以是多层。

1.3.2 前馈神经网络的目标函数

对一一个前馈神经网络我们希望达到的目的就是期望值和目标值越接近越好，那么需要用一个目标函数来确定这个接近的概念。
如对于一系列训练样本x，我们的期望输出是t=(t1,…, tc)，网络实际输出是z=(z1,…, zc)
那么我们可以确定这个前馈神经网络的目标函数（各输出误差的平方的累加）是：

如公式可见变量是权重w！！！
我们希望达到的目的是J（w）越接近0越好！！！

1.3.3 关于Delta学习规则

由上所知，其实目标函数的大小实际上可以看作是实际值和期望值的误差大小
所以接下来学习的过程就是减小这个误差到最小值，即期望J(w)越接近0越好。
这里引入一个Detla学习规则简单来讲就是：若神经元实际输出比期望输出大，则减少输入为正的连接的权重，增大所有输入为负的连接的权重。反之，则增大所有输入为正的连接权的权重，减少所有输入为负的连接权的权重。

Delta学习规则是一种有监督学习算法，该算法根据神经元的实际输出与期望输出差别来调整连接权，其数学表示如下：

1.3.4 梯度下降算法

获得目标函数和delta学习规则以后，delta规则是如何找到最小化误差的最佳权向量的呢？这里就涉及到梯度下降的算法：
总结来说就是：delta法则是使用梯度下降法来找到最佳权向量。 而梯度下降法就是沿梯度下降的方向求解目标函数（误差）极小值。

什么是梯度下降的概念？：
寻找损失函数的最低点，就像我们在山谷里行走，希望找到山谷里最低的地方。那么如何寻找损失函数的最低点呢？在这里，我们使用了微积分里导数，通过求出函数导数的值，从而找到函数下降的方向或者是最低点（极值点）。

目标函数里变量是权重(Weight, 简称 w）。所以我们所要做的工作，就是通过梯度下降方法，不断地调整权重w ，使得目标函数的值变得越来越小。

假设某个目标函数里，目标函数值 J(w) 与权重 w 有下图这样的关系。实际模型里，可能会有多个权重 w ，这里为了简单起见，举只有一个权重 w的例子。权重 w 目前的位置是在A点。此时如果求出A点的梯度dJ/dw是小于零, 便可以知道如果我们向右移动，可以使损失函数的值变得更小。
通过计算梯度，我们就可以知道w的移动方向，应该让 w 向右走而不是向左走，也可以知道什么时候会到达最低点（梯度为0的地方）。
现在知道了 w需要前进的方向，接下来需要知道应该前进多少。这里我们用到学习率(Learning Rate)这个概念（即detla学习规则里的α）。通过学习率，可以计算前进的距离（步长）。
我们用w_i表示权重的初始值， w_i+1表示更新后的权重值，用α 表示学习率，则有：
在梯度下降中，我们会重复式子该多次，直至目标函数值收敛不变（趋近于固定值）。

如果学习率α 设置得过大，有可能我们会错过损失函数的最小值；如果设置得过小，可能我们要迭代式子非常多次才能找到最小值，会耗费较多的时间。因此，在实际应用中，我们需要为学习率α 设置一个合适的值。

当然从这个公式我们结合Detla规则来看，不难发现，其实：

在多样本数据的时候我们如何去使用梯度下降？：

在多样本数据中，对于每一个样本数据，我们都可以求出一个权重的梯度。这个时候，我们需要把各个样本数据的权重梯度加起来，并求出它们的平均值，用这个平均值来作为样本整体的权重梯度。

更为具象的对梯度下降算法的介绍：
先确定一个初始点，将w按照梯度下降的方向进行调整，就会使得J(w)往更低的方向进行变化，如图所示，算法的结束将是在w下降到无法继续下降为止。
step1:想象一下，你如何能在被蒙住眼睛的情况下，从山上走下来？

step2:先用你灵巧的脚，探一探脚下的山地，哪个方向坡度最陡？（计算梯度方向）

step3:朝着这个方向迈一步；（沿梯度方向下降）

step4:一大步，还是一小步？（学习速率）

step5:持续这个过程直到平地（迭代）o可不能有悬崖哦……（目标函数处处可导）

1.3.4 输出层和隐含层的的权重改变量

以下介绍在一个三层模型中，如何确定输出层和隐含层的权重改变量！！！

1.3.4.1 输出层权重改变量

首先我们对于输出层权重改变量，仅考虑隐含层和输出层的关系如下所示：

对于计算输出层权重改变量，首先要确定输出量J和隐含层的输出量的权重W_kj的梯度，关系如下所示：
然后分别计算上式中两个部分（绿色和灰色）的偏导

（1）灰色部分：
**其中net_k实际上就是输出层的总输入。**所以灰色部分的结果显而易见就是y_j

(2)绿色部分：
所以最后得到输出层权重改变量：
其中f’(net_k)是激活函数的导数。

1.3.4.2隐藏层权重改变量

首先我们对于隐含层权重改变量，仅考虑输入层和隐含层的权重关系如下所示：
对于计算隐含层权重改变量，一样的首先要确定输出量J和输入层的输出量的权重W_ji的梯度,如下所示：
然后分别计算三个部分（橘，绿，黄）
绿色部分很熟悉，就是：
然后黄色部分也很熟悉，就是：
然后橘色部分，展开J(w)进行计算：
最后得到隐含层的权重改变量是：

1.3.5 误差反向传播（BP(error BackPropagation)法）

1.3.5.1 误差传播迭代公式归纳

总结1.3.4我们得到输出层权重改变梯度和隐含层权重改变梯度为：

总结两者我们可以推导出一个一致性
（1）权重增量=-1 * 学习步长 * 目标函数对权重的偏导数，即：

（2）目标函数对权重的偏导数=-1 * 残差 * 当前层的输入：

（3）残差=当前层激励函数的导数*上层反传过来的误差
（4）上层反传过来的误差=上层残差的加权和：

1.3.5.2 误差反向传播（即BP(error BackPropagation)法）

所谓的误差反向传播，就是把残差回传去更新隐含层和输出层的权重，从而实现收敛的一个过程
这里有一个计算例子实现误差反向传播
综上整个BP算法的思路是：
1）正向传播：输入样本－>输入层－>各隐层（处理）－>输出层
注1：若输出层实际输出与期望输出不符，则转入误差反向传播过程。
2）误差反向传播：输出误差（某种形式）－>隐层（逐层）－>输入层 其主要目的是通过将输出误差反传，将误差分摊给各层所有单元，从而获得各层单元的误差信号，进而修正各单元的权值（其过程，是一个权值调整的过程）。
其中权值调整的过程，也就是网络的学习训练过程分为以下部分：
1）初始化
2）输入训练样本对，计算各层输出
3）计算网络输出误差
4）计算各层误差信号
5）调整各层权值
6）检查网络总误差是否达到精度要求
满足，则训练结束；不满足，则返回步骤2。

1.3.5.3 BP算法的例子

Leetcode

今天做的三个都和动态规划有点关系，深入一下动态规划算法：
动态规划算法(Dynamic Programming)，也叫dp算法，该算法的核心思想是：将大问题划分为小问题进行解决，从而一步步获取最优解；动态规划算法与分治算法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。
dp与分治法不同的是，适合于用动态规划求解的问题，经分解得到子问题往往不是互相独立的。 ( 即下一个子阶段的求解是建立在上一个子阶段的解的基础上，进行进一步的求解 ),依次解决各子问题，最后一个子问题就是初始问题的解，而分治法各个子问题是相互独立的。
动态规划算法的典型解题套路就是创建一个二维数组，然后通过填表的方式逐步推导出解决问题的递推公式。

118. 杨辉三角

class Solution:
    def generate(self, numRows: int) -> List[List[int]]:
        dp=[]
        dp.append([1])

        for i in range(1,numRows):
            remain=[0]+dp[i-1]+[0]
            print(remain)
            array=[]
            for j in range(i+1):
                array.append(remain[j]+remain[j+1])
            dp.append(array)
        
        return dp

119. 杨辉三角 II

class Solution:
    def getRow(self, rowIndex: int) -> List[int]:
        dp=[1]

        for i in range(1,rowIndex+1):
            remain=[0]+dp+[0]
            dp=[]
            for j in range(i+1):
                dp.append(remain[j]+remain[j+1])
        return dp

121. 买卖股票的最佳时机

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        profit=0
        cost=-prices[0]

        for i in prices:
            if (i+cost)>profit:
                profit=i+cost
            if cost < -i:
                cost=-i
        
        return profit