CNN，BN,过拟合
1.卷积神经网络（CNN）
1.1 基础结构
主要由三个基本组件组成：
卷积层（Convolutional layer）
池化层（Pooling layer）
全连接层（Fully-Connected layer）—就是正常神经网络层，不做过多介绍
（1）以下以一个经典的LeNet-5卷积神经网络来介绍：第一层：输入层，输入的是 batchsize∗32∗32的黑白分辨率图像
第二层：C1，卷积层，有6个特征图，卷积核大小为 5 ∗ 5 ，深度为 6，没有使用全0填充且步长为1，所以共有 28 ∗ 28 ∗ 6 个神经元（32-5+1=28），参数数量为156（ 5 ∗ 5 ∗ 6 + 6 = 156 ，6为偏置项参数）,每一个单元与输入层的25个单元连接。
第三层：S2，池化下采样层，有6个特征图，每个特征图大小为 14 ∗ 14 ，池化核大小为2*2，长和宽步长都为2。
第四层：C3，卷积层，卷积核大小为 5 ∗ 5，有16个特征图，每个特征图大小为 10 ∗ 10 ( 14 − 5 + 1 = 10 ) ，与第三层有着固定的连接。
第五层：S4，池化下采样层，有16个特征图，每个特征图大小为 5 ∗ 5 ( 10 / 2 ) ，池化核大小为 2 ∗ 2 ，长和宽步长都为2。
第六层：F5，全连接层，有 batchsize∗400个特征图。
第七层：F6，全连接层，有 batchsize ∗ 120个特征图。
第八层：F7，全连接层，有 batchsize ∗ 84个特征图。
第九层：输出层，有 batchsize ∗ 10个特征图。
1.2 卷积层
实际上和图像处理的卷积滤波是类似的，就是用卷积核对图像进行特征提取。一般用一个正方形卷积核，遍历图片上的每一个像素点。图片与卷积核重合区域内相对应的每一个像素值，乘卷积核内相对应点的权重，然后求和， 再加上偏置后，最后得到输出图片中的一个像素值。
卷积层的功能是对输入数据进行局部特征提取，其内部包含多个卷积核，组成卷积核的每个元素都对应一个权重系数和一个偏差量（bias vector），然后每一个卷积核对应一个输出通道，其中的权重参数是需要学习，而不是直接得出的。
1.2.1 什么是感受野？
感受野用来表示网络内部的不同神经元对原图像的感受范围的大小，或者说，convNets(cnn)每一层输出的特征图(feature map)上的像素点在原始图像上映射的区域大小。
简单的说，就是卷积后的图像上一个像素点回推到原图像上的区域大小
计算公式是：
n代表卷积层；rn代表第n个卷积层的感受野大小；Kn代表第n个卷积层的卷积核大小；Sn代表第n个卷积层的步长。
1.2.2 卷积层超参数
卷积神经网络的超参数 ：
(1)滤波器/卷积核数量（output number）
D=卷积核的数量=输出通道
(2) 核尺寸（kernel size）
由卷积核的交叉相关计算可知，随着卷积层的堆叠，特征图的尺寸会逐步减小，例如16×16的输入图像在经过单位步长、无填充的5×5的卷积核后，会输出12×12的特征图。
具体计算方式如下所示：实例如下所示，注意卷积核图层和原图层是一致的，如下图输入图片是3层，卷积核也得是3层：
(3) 步长（stride）
卷积步长定义了卷积核相邻两次扫过特征图时位置的距离，卷积步长为1时，卷积核会逐个扫过特征图的元素，步长为n时会在下一次扫描跳过n-1个像素 。
卷积步长大于1的情况可以起到降维的作用
（4）填充（padding）
填充是在特征图通过卷积核之前人为增大其尺寸以抵消计算中尺寸收缩影响的方法。
常见的填充方法为
–1--全零填充（zero padding）:
–2--重复边界值填充（replication padding）
1.2.3 激励函数
常用的还是ReLU激活函数
(1)分段线性函数
(2)无饱和问题，明显减轻梯度消失问题
(3)深度网络能够进行优化的关键
1.2.4 卷积层误差反向传播
1.2.4.1 卷积运算实例
在图像上显示这个过程就是一个连接层的过程，每个像素点是一个变量，相当于9个输入变成了4个输出，然后卷积核里面包含了权重，偏置，如下图所示：
1.2.4.2 卷积层误差反向传播
回顾一下在基础神经网络得到的误差反向传播的公式：
有关卷积层误差反向传播的推导帖子
根据卷积层可以看作一个连接层的概念：
实例：在实际计算中还需要乘上激励函数去计算
1.3 池化层
在卷积层中，可以通过调节步长实现特征图的高宽成倍缩小，从而降低了网络的参数量。实际上，除了通过设置步长，还有一种专门的网络层可以实现尺寸缩减功能，它就是池化层(Pooling layer)。
池化层同样基于局部相关性的思想，通过从局部相关的一组元素中进行采样或信息聚合，从而得到新的元素值。作用是特征融合和降维。
在池化层中没有需要学习的参数
1.3.1 池化层超参数和池化方法
尺寸（size）
步长（step）
常见的池化方法有
1.3.1.1平均池化（mean pooling）
计算图像区域的平均值作为该区域池化后的值。
优缺点：能很好的保留背景，但容易使得图片变模糊
1.3.1.2 最大池化（max pooling）
选图像区域的最大值作为该区域池化后的值，记住最大值的索引位置，以方便反向传播。
优缺点：能很好的保留纹理特征，一般现在都用max-pooling而很少用mean-pooling
1.3.2 池化层误差反向传播
回顾一下在基础神经网络得到的误差反向传播的公式：当现在利用到池化层的误差反向传播时
1.3.2.1 平均池化（mean pooling）反向传播
1.3.2.2最大池化（max pooling）反向传播
当然这里两种反向传播实例都只是讲了上采样的过程，在实际计算中还需要乘上激励函数去计算
2. 批标准化 (Batch Normalization)
就像激活函数层、卷积层、全连接层、池化层一样，BN(Batch Normalization)也属于网络的一层。Batch normalization 也可以被看做一个层面. 在一层层的添加神经网络的时候, 我们先有数据 X, 再添加全连接层, 全连接层的计算结果会经过 激励函数 成为下一层的输入, 接着重复之前的操作. Batch Normalization (BN) 就被添加在每一个全连接和激励函数之间.
2.1 为什么需要Batch Normalization
在神经网络中, 数据分布对训练会产生影响.
比如在某个神经元中：
当x 的值为1, 某个 Weights 的初始值为 0.1, 这样后一层神经元计算结果就是 Wx = 0.1;
当x = 20, 这样 Wx 的结果就为 2.
如果我们把Wx值加入一层激励函数, 激活这个 Wx 值的时候, 问题就来了. 如果使用 像 tanh 的激励函数, Wx 的激活值就变成了 ~0.1 和 ~1, 接近于 1 的部分已经处在了 激励函数的饱和阶段, 也就是如果 x 无论再怎么扩大, tanh激励函数输出值也还是接近1. 如下图所示：
换句话说, 神经网络在初始阶段已经不对那些比较大的 x 特征范围 敏感了. 这样很糟糕, 想象我轻轻拍自己的感觉和重重打自己的感觉居然没什么差别, 这就证明我的感官系统失效了. 而且这类问题不仅仅发生在神经网络的输入层, 而且在隐藏层中也经常会发生.
所以各层在训练的过程中就需要不断的改变以适应这种新的数据分布，从而造成网络训练困难，难以拟合的问题。这就需要用到Batch Normalization了。
2.2 Batch Normalization是什么
Batch normalization 的 mini-batch 是批数据, 把数据分成小批小批进行SGD(梯度下降). 而且在每批数据进行前向传递 forward propagation 的时候, 对每一层都进行 normalization 的处理（即规范化操作），使得结果（输出信号各个维度）的均值为0，方差为1。
具体公式如下所示：
最后的“scale andshift”操作则是为了让因训练所需而“刻意”加入的BN能够有可能还原最初的输入。
最后会得到这样的结果：
3.避免过适应（过拟合）
3.1 什么是过适应（过拟合）
模型在训练集上的表现很好，但在测试集和新数据上的表现很差。
过适应的根本原因：权重参数太多，而训练数据集太小，过拟合出现的原因：
1.模型复杂度过高，参数过多
2.数量数据比较小
3.训练集和测试集分布不一致
3.1 样本里面的噪声数据干扰过大，导致模型过分记住了噪声特征，反而忽略了真实的输入输出特征
3.2训练集和测试集特征分布不一样(如果训练集和测试集使用了不同类型的数据集会出现这种情况)
3.2 method 1-早期停止训练
当目标函数在“测试集”上不再减小时，训练就应该停止了。不能一味追求“训练集”的误差减小，如下图所示
3.3 method 2-权重衰减
一般来说权重越低，过拟合的可能性就越低，权重衰减的含义就是把一些“无用”的权重逐步减小。实现方法如下：最后可能会使得某些权重趋向于0。
3.4 method 3-Dropout
本质上，Dropout就是用一小块数据来训练一系列“子网络”；Dropout是“集成学习”的一种。
3.4.1 Dropout 实现方法
在训练阶段：以概率p主动临时性地忽略掉部分隐藏节点，具体步骤如下
1.首先随机（临时）删掉网络中的一些隐藏神经元（备份被删除神经元的参数），一般情况下输入输出神经元保持不变
2.把输入x通过修改后的网络前向传播，删除的神经元不进行前向传播，传给下一层的值是0，然后把得到的损失结果通过修改后的网络反向传播。一小批训练样本执行完这个过程后就按照随机梯度下降法更新没有被删除的神经元对应的参数（w，b）
3.然后再恢复被删掉的神经元，此时在当前层中被删除的神经元保持原样，而没有被删除的神经元已经有所更新
4.不断重复上述过程1，2，3：
在测试阶段：将参与学习的节点和那些被隐藏的节点以一定的概率p加权求和，综合计算得到网络的输出。预测的时候，每一个单元的参数要预乘以p。
3.4.2 Dropout如何防止过拟合
主要是以下两个作用：
（1）起到取平均的作用
首先确定为什么取平均可以起到防止过拟合：
先回到正常的模型（没有dropout），我们用相同的训练数据去训练5个不同的神经网络，一般会得到5个不同的结果，此时我们可以采用 “5个结果取均值”或者“多数取胜的投票策略”去决定最终结果。（例如 3个网络判断结果为数字9,那么很有可能真正的结果就是数字9，其它两个网络给出了错误结果）。这种“综合起来取平均”的策略通常可以有效防止过拟合问题。因为不同的网络可能产生不同的过拟合，取平均则有可能让一些“相反的”拟合互相抵消。
而每次训练随机dropout掉不同的隐藏神经元，网络结构已经不同，这就类似在训练不同的网络，整个dropout过程就相当于对很多个不同的神经网络取平均。所以Dropout可以起到防止过拟合的作用
（2）减少神经元之间共适应关系
Leetcode(125,136,141)
学习python常用字符串方法
学习一下 Python 中常用处理字符串的相关函数
string.capitalize() 把字符串的第一个字符大写
string.count(str, beg=0, end=len(string)) 返回 str 在 string 里面出现的次数，如果 beg 或者 end 指定则返回指定范围内 str 出现的次数
string.endswith(obj, beg=0, end=len(string)) 检查字符串是否以 obj 结束，如果beg 或者 end 指定则检查指定的范围内是否以 obj 结束，如果是，返回 True,否则返回 False.
string.find(str, beg=0, end=len(string)) 检测 str 是否包含在 string 中，如果 beg 和 end 指定范围，则检查是否包含在指定范围内，如果是返回开始的索引值，否则返回-1
string.index(str, beg=0, end=len(string)) 跟find()方法一样，只不过如果str不在 string中会报一个异常.
string.isalnum() 如果 string 至少有一个字符并且所有字符都是字母或数字则返回 True,否则返回 False
string.isalpha() 如果 string 至少有一个字符并且所有字符都是字母则返回 True,否则返回 False
string.isdecimal() 如果 string 只包含十进制数字则返回 True 否则返回 False.
string.isdigit() 如果 string 只包含数字则返回 True 否则返回 False.
string.islower() 如果 string 中包含至少一个区分大小写的字符，并且所有这些(区分大小写的)字符都是小写，则返回 True，否则返回 False
string.isnumeric() 如果 string 中只包含数字字符，则返回 True，否则返回 False
string.isspace() 如果 string 中只包含空格，则返回 True，否则返回 False.
string.istitle() 如果 string 是标题化的(见 title())则返回 True，否则返回 False
string.isupper() 如果 string 中包含至少一个区分大小写的字符，并且所有这些(区分大小写的)字符都是大写，则返回 True，否则返回 False
string.join(seq) 以 string 作为分隔符，将 seq 中所有的元素(的字符串表示)合并为一个新的字符串
string.lower() 转换 string 中所有大写字符为小写.
string.lstrip() 截掉 string 左边的空格
max(str) 返回字符串 str 中最大的字母。
min(str) 返回字符串 str 中最小的字母。
string.replace(str1, str2, num=string.count(str1)) 把 string 中的 str1 替换成 str2,如果 num 指定，则替换不超过 num 次.
string.split(str="", num=string.count(str)) 以 str 为分隔符切片 string，如果 num 有指定值，则仅分隔 num+ 个子字符串
string.startswith(obj, beg=0,end=len(string)) 检查字符串是否是以 obj 开头，是则返回 True，否则返回 False。如果beg 和 end 指定值，则在指定范围内检查.
string.strip([obj]) 在 string 上执行 lstrip()和 rstrip()
string.swapcase() 翻转 string 中的大小写
string.title() 返回"标题化"的 string,就是说所有单词都是以大写开始，其余字母均为小写(见 istitle())
string.translate(str, del="") 根据 str 给出的表(包含 256 个字符)转换 string 的字符,要过滤掉的字符放到 del 参数中
string.upper() 转换 string 中的小写字母为大写
125 回文字符串
方法1 比较简单粗暴，判断一下是不是字母或者数字，且字母转小写，然后双指针；
class Solution:
def isPalindrome(self, s: str) -> bool:
def isornot(lab):
if lab.lower()<='z' and lab.lower()>='a':
return True
if lab<='9'and lab>='0':
return True
return False
low=0
high=len(s)-1
while low<=high:
while low<=high and (not isornot(s[low])):
low+=1
while low<=high and (not isornot(s[high])):
high-=1
#print("low=",s[low].lower(),"high=",s[high].lower())
if low>high:
return True
if s[low].lower() != s[high].lower():
return False
else:
low+=1
high-=1
return True
方法2 利用了s.lower()和正则表达模块 re.findall()
re.findall():返回string中所有与pattern匹配的全部字符串,返回形式为数组。
class Solution:
def isPalindrome(self, s: str) -> bool:
s = s.lower()
s1 = re.findall(r'[a-z0-9]', s)
s2 = "".join(s1) #list转字符串
# 使用字符串切片反转
return s2[::-1] == s2
136. 只出现一次的数字
利用了^异或计算
异或的规律是：
所以不断异或，最终剩余数就是只出现一次的数
class Solution:
def singleNumber(self, nums: List[int]) -> int:
n = len(nums)
for i in range(1, n):
nums[i] ^= nums[i-1]
return nums[-1]
141. 环形链表
这种就是快慢指针，只要有环，慢指针就可以追上快指针！！！
class Solution:
def hasCycle(self, head: Optional[ListNode]) -> bool:
slow=head
fast=head
while fast!=None:
fast=fast.next
if not fast:
return False
fast=fast.next
slow=slow.next
if slow==fast:
return True
return False