重构：改善既有代码的设计

Chapter 1

如果你要给程序添加一个特性，但发现代码因缺乏良好的结构而不易于进行更改，那就先重构那个程序，使其比较容易添加该特性，然后再添加该特性。

重构前，先检查自己是否有一套可靠的测试集。这些测试必须有自我检验能力。进行重构时，我需要依赖测试。我将测试视为bug检测器，它们能保护我不被自己犯的错误所困扰。通过测试对当前工作进行二次确认。

重构技术就是以微小的步伐修改程序。如果你犯下错误，很容易便可发现它。

傻瓜都能写出计算机可以理解的代码。唯有能写出人类容易理解的代码的，才是优秀的程序员。

好代码的检验标准就是人们是否能轻而易举地修改它。小的步子可以更快前进，请保持代码永远处于可工作状态，小步修改累积起来也能大大改善系统的设计。

Chapter 2 重构

WHY

• 改进软件设计
• 使软件更容易理解。通过重构，我就把脑子里的理解转移到了代码本身
• 帮助找到 bug
• 提高编程速度

见机行事的重构

大部分重构应该是不起眼的、见机行事的。

• 帮助理解
• 捡垃圾式重构

？？？

我听过的一条建议是：将重构与添加新功能在版本控制的提交中分开。这样做的一大好处是可以各自独立地审阅和批准这些提交。但我并不认同这种做法。重构常常与新添功能紧密交织，不值得花工夫把它们分开。并且这样做也使重构脱离了上下文，使人看不出这些“重构提交”的价值。每个团队应该尝试并找出适合自己的工作方式，只是要记住：分离重构提交并不是毋庸置疑的原则，只有当你真的感到有益时，才值得这样做

============================

有计划的重构

• 添加新功能最快的方法往往是先修改现有的代码，使新功能容易被加入。

每当有人靠近“重构区”的代码，就把它朝想要改进的方向推动一点。这个策略的好处在于，重构不会破坏代码——每次小改动之后，整个系统仍然照常工作。例如，如果想替换掉一个正在使用的库，可以先引入一层新的抽象，使其兼容新旧两个库的接口。一旦调用方已经完全改为使用这层抽象，替换下面的库就会容易得多。（这个策略叫作Branch By Abstraction[mf-bba]。）

• 复审代码时重构
• 重写

重构的唯一目的就是让我们开发更快，用更少的工作量创造更大的价值。

发布接口 public interface

可以把旧的接口标记为“不推荐使用”（deprecated），等一段时间之后最终让其退休；但有些时候，旧的接口必须一直保留下去。

分支

在隔离的分支上工作得越久，将完成的工作集成（integrate）回主线就会越困难。

持续集成（Continuous Integration，CI），也叫“基于主干开发”（Trunk-Based Development）。在使用CI时，每个团队成员每天至少向主线集成一次。这个实践避免了任何分支彼此差异太大，从而极大地降低了合并的难度。不过CI也有其代价：你必须使用相关的实践以确保主线随时处于健康状态，必须学会将大功能拆分成小块，还必须使用特性开关（feature toggle，也叫特性旗标，feature flag）将尚未完成又无法拆小的功能隐藏掉。

YAGNI

简单设计、增量式设计或者YAGNI[mf-yagni]——“你不会需要它”（you arenʼt going to need it）的缩写

把YAGNI视为将架构、设计与开发过程融合的一种工作方式，这种工作方式必须有重构作为基础才可靠。

”演进式架构“

自测试代码、持续集成、重构

重构（及其前置实践）是YAGNI的基础，YAGNI又让重构更易于开展

Chapter 3 Bad Smell

清楚的命名

提炼函数

函数越长，就越难理解

注释

每当感觉需要以注释来说明点什么的时候，我们就把需要说明的东西写进一个独立函数中，并以其用途（而非实现手法）命名*。关键不在于函数的长度，而在于函数“做什么”和“如何做”之间的语义距离。

如果代码前方有一行注释，就是在提醒你：可以将这段代码替换成一个函数，而且可以在注释的基础上给这个函数命名。

循环

条件表达式和循环常常也是提炼的信号。你可以使用分解条件表达式（260）处理条件表达式。对于庞大的switch语句，其中的每个分支都应该通过提炼函数（106）变成独立的函数调用。如果有多个switch语句基于同一个条件进行分支选择，就应该使用以多态取代条件表达式（272）。

至于循环，你应该将循环和循环内的代码提炼到一个独立的函数中。如果你发现提炼出的循环很难命名，可能是因为其中做了几件不同的事。如果是这种情况，请勇敢地使用拆分循环（227）将其拆分成各自独立的任务。

全局变量

把全局数据用一个函数封装装起来

全局数据印证了帕拉塞尔斯的格言：良药与毒药的区别在于剂量。有少量的全局数据或许无妨，但数量越多，处理的难度就会指数上升。

可以用封装变量来确保所有数据更新操作都通过很少几个函数来进行，查询函数和修改函数分离

如果一个变量在其内部结构中包含了数据，通常最好不要直接修改其中的数据，而是用将引用对象改为值对象令其直接替换整个数据结构

循环

使用以管道取代循环，管道操作（如filter和map）可以帮助我们更快地看清被处理的元素以及处理它们的动作

过大的类

是把多余的东西消弭于类内部。如果有5个“百行函数”，它们之中很多代码都相同，那么或许你可以把它们变成5个“十行函数”和10个提炼出来的“双行函数”。

注释

当你感觉需要撰写注释时，请先尝试重构，试着让所有注释都变得多余。

如果你需要注释来解释一块代码做了什么，试试提炼函数；如果函数已经提炼出来，但还是需要注释来解释其行为，试试用改变函数声明为它改名；如果你需要注释说明某些系统的需求规格，试试引入断言。

应该添加的情况：如果你不知道该做什么，记述将来的打算，标记你并无十足把握的区域，写下自己“为什么做某某事”。这类信息可以帮助将来的修改者，尤其是那些健忘的家伙。

Chapter 4 测试

WHY

• 编写代码的时间仅占所有时间中很少的一部分。有些时间用来决定下一步干什么，有些时间花在设计上，但是，花费在调试上的时间是最多的

• 修复bug通常是比较快的，但找出bug所在却是一场噩梦。当修复一个bug时，常常会引起另一个bug，却在很久之后才会注意到它。那时，你又要花上大把时间去定位问题。

• 一套测试就是一个强大的bug侦测器，能够大大缩减查找bug所需的时间

• 除非体会到编写测试是如何提升编程速度，否则自测试似乎就没有什么意义

• 编写未臻完善的测试并经常运行，好过对完美测试的无尽等待。

• 一个测试语句中最好只有一个验证语句，否则测试可能在进行第一个验证时就失败，这通常会掩盖一些重要的错误信息，不利于你了解测试失败的原因。

错误，脏数据

直接 assert

如果这个错误会导致脏数据在应用中到处传递，或是产生一些很难调试的失败，我可能会用引入断言（302）手法，使代码不满足预设条件时快速失败。我不会为这样的失败断言添加测试，它们本身就是一种测试的形式。

探测边界条件

• 目前为止我的测试都聚焦于正常的行为上，这通常也被称为“正常路径”（happy path），它指的是一切工作正常、用户使用方式也最符合规范的那种场景。同时，把测试推到这些条件的边界处也是不错的实践，这可以检查操作出错时软件的表现。
• 考虑可能出错的边界条件，把测试火力集中在那儿。

你应该把测试集中在可能出错的地方。观察代码，看哪儿变得复杂；观察函数，思考哪些地方可能出错。

• 不要因为测试无法捕捉所有的bug就不写测试，因为测试的确可以捕捉到大多数bug

单元测试

负责测试一小块代码，运行速度足够快。它们是自测试代码的支柱，是一个系统中占绝大多数的测试类型

测试三问

与编程的许多方面类似，测试也是一种迭代式的活动。除非你技能非常纯熟，或者非常幸运，否则你很难第一次就把测试写对。我发觉我持续地在测试集上工作，就与我在主代码库上的工作一样多。很自然，这意味着我在增加新特性时也要同时添加测试。

有时还需要回顾已有的测试：它们足够清晰吗？我需要重构它们，以帮助我更好地理解吗？我拥有的测试是有价值的吗？

代码足够清晰吗？我需要重构它们，以帮助我更好地理解吗？

什么时候应该添加测试

每当你收到bug报告，请先写一个单元测试来暴露这个bug。

Feature Engineering

Charpter 2 简单数字的奇特技巧

二值化　０，１

量化或装箱　　

1
2
3
4
5
6
7
8
9
10

>>> small_counts
array([30, 64, 49, 26, 69, 23, 56, 7, 69, 67, 87, 14, 67, 33, 88, 77, 75, 47, 44, 93])
### Map to evenly spaced bins 0-9 by division
>>> np.floor_divide(small_counts, 10)
array([3, 6, 4, 2, 6, 2, 5, 0, 6, 6, 8, 1, 6, 3, 8, 7, 7, 4, 4, 9], dtype=int32)

>>> large_counts = [296, 8286, 64011, 80, 3, 725, 867, 2215, 7689, 11495, 91897, 44, 28, 7971, 926, 122, 22222]
### Map to exponential-width bins via the log function
>>> np.floor(np.log10(large_counts))
array([ 2., 3., 4., 1., 0., 2., 2., 3., 3., 4., 4., 1., 1., 3., 2., 2., 4.])

分位数装箱

1
2
3
4
5
6
7
8

### Map the counts to quartiles
>>> pd.qcut(large_counts, 4, labels=False)
array([1, 2, 3, 0, 0, 1, 1, 2, 2, 3, 3, 0, 0, 2, 1, 0, 3], dtype=int64)
>>> large_counts_series.quantile([0.25, 0.5, 0.75])
0.25 122.0
0.50 926.0
0.75 8286.0
dtype: float64

对数转换

线性回归模型的训练过程假定预测误差分布得像高斯，对数变换，这是一种功率变换，将变量的分布接近高斯。

对数变换是处理具有重尾分布的正数的有力工具。（重尾分布在尾部范围内的概率比高斯分布的概率大）

使用$R^2$评分来评估，好的模型有较高的 R 方分数。一个完美的模型得到最高分1， 一个坏的模型可以得到一个任意低的负评分。

1
2

scores_log = cross_val_score(m_log, biz_df[['log_review_count']], biz_df['stars'], cv=10)
scores_log.mean()  # R^2

对数变换将较大的离群值压缩到一个更小的范围内

Box-Cox transformation

???

概率图(probplot)是一种直观地比较数据分布与理论分布的简单方法。

特征缩放(Scaling)或归一化(Normalization)

minmaxscaler　

$x’=\frac{x-min}{max-min}$

Min-max缩放压缩（或拉伸）所有特征值到[0, 1 ]的范围内

Standardization

$x’=\frac{x-\overline{x}}{\sigma}$

缩放后的特征的平均值为0, 方差为1。如果原始特征具有高斯分布, 则缩放特征为标准高斯

最小最大缩放和标准化都从原始特征值中减去一个数量，将稀疏特征的向量转换为一个稠密的向量。

L2 Normalization

$x’=\frac{x}{\sqrt{\sum_{j} x_j^2}}$

Iptables

https://www.youtube.com/watch?v=iP8YWcvKDr0&list=PLRRzkFBzCR3v-UefO69M7snZVzSnVlJKZ&index=1

NAT

1. SNAT, Source NAT

   • 改变 outgoing packet 的源 IP
   • 跟踪链接，改变 reply packet 的目的 IP
   • 可用作一组静态 IP addresses 的负载均衡

   

2. DNAT, Destination NAT

   • 改变 incoming packet 的目的 IP，转发到其他设备
   • 跟踪链接，改变 reply packet 的源 IP (由其他设备的源 IP 变为当前 DNAT 系统的源 IP)

   通常用在 inbound packets 的端口转发

   只能用在 nat table, 和 PREROUTING and OUTPUT chains

DMZ, 隔离区，DNAT 系统隔离的区域

3. IP Masquerading

• A NAT route masquerades a private network
• SNAT use outgoing intreface as the address for rewriting

广泛用作 IPV4 的扩展

• private LAN using private IP address behind a NAT router, 所有流量都被视作来自 NAT router
• 所有来自private LAN 的流量都 NAT 到 NAT router 为源 IP
• 所有来自公网的流量都 NAT 处理后返回 private LAN devices

Iptables Command

1
2
3
4
5
6
7
8
9
10
11
12
13
14

# -A append to `INPUT` chain
# -m match, match against packet `state`
# -j jump, jump to `ACCEPT` target
# Appends a rule to the INPUT chain that matches the state of RELATED or ESTABLISHED, jump to the ACCEPT target
-A INPUT -m state --state RELATED,ESTABLISHED -j ACCEPT
# -p protocol
-A INPUT -p ICMP -j ACCEPT
# -i interface
-A INPUT -i lo -j ACCEPT
# allow incoming SSH, any new coming tcp with dport 22
-A INPUT -p tcp -m state --state NEW -m tcp --dport 22 -j ACCEPT
# send and explicit rejection message of ICMP host-prohibited back to the sender, instead of quietly dropping a packet
-A INPUT -j REJECT --reject-with icmp-host-prohibited
-A FORWARD -j REJECT --reject-with icmp-host-prohibited

A Basic Router

1
2
3

A Router
LAN: enp0s8, 172.16.0.0/24, private addresses
WAN: enp0s3, , public address

1
2
3
4
5
6
7
8
9

*nat  # nat table
# policies on PREROUTING, POSTROUTING, OUTPUT chains
:PREROUTING ACCEPT [0:0]
:POSTROUTING ACCEPT [0:0]
:OUTPUT ACCEPT [0:0]
# SNAT: WAN port
# all packets leaving this machine with enp0s3 to have the source IP address of interface enp0s3
-A POSTROUTING -o enp0s3 -j MASQUERADE
COMMIT

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

*filter  # filter table
# default policies on INPUT, OUTPUT, FORWARD chains
:INPUT DROP [0:0]
:FORWARD DROP [0:0]
:OUTPUT ACCEPT [0:0]
# INPUT chains, incomming connections from LAN side
# -s source, match source ip address in private LAN side addr range
-A INPUT -m state --state RELATED,ESTABLISHED -j ACCEPT
-A INPUT -i lo -j ACCEPT
-A INPUT -s 172.16.0.0/24 -i enp0s8 -p icmp -j ACCEPT
-A INPUT -s 172.16.0.0/24 -i enp0s8 -p tcp -m state --state NEW -m tcp --dport 22 -j ACCEPT
-A INPUT -s 172.16.0.0/24 -i enp0s8 -p udp -m state --state NEW -m udp --dport 67 -j ACCEPT
# Condition Rejection
-A INPUT -s 172.16.0.0/24 -i enp0s8 -j REJECT --reject-with icmp-host-prohibited
# if all above INPUT rules are not true, fall to the last rule: Drop all
-A INPUT -j DROP

# FORWARD chains, FORWARD packets between LAN port and WAN port
# packets from LAN to LAN go directly, do not need route
-A FORWARD -d 172.16.0.0/24 -i enp0s8 -j DROP
# ACCEPT all packets from LAN to WAN with source IP in the LAN,
#                and from WAN to LAN with detination IP in the LAN
-A FORWARD -s 172.16.0.0/24 -i enp0s8 -j ACCEPT
-A FORWARD -d 172.16.0.0/24 -i enp0s3 -j ACCEPT
-A FORWARD -j DROP
# OUTPU chains, output packets 
-A OUTPUT -j ACCEPT
COMMIT

Packets Processing

Netfilter component of Linux kernel recognizes and grouped packets into streams or flows

NAT rules are only determined for the 1st packet in a stream, the all subsequent packets receive the same processing

Tables and Chains

Tables

• filter
• NAT
• mangle
• raw
• security

Chains

• PREROUTING
• INPUT
• FORWARD
• OUTPUT
• POSTROUTING
• User-defined Chains

Tables and built-in chains

Filter: Access Controls

Built-in chains

• INPUT: handles packets destined for local sockets
• FORWARD: handles packets routed through this host to another destination
• OUTPUT: handles locally generated packets

NAT: Consulted whenever a packet create a new connection

Built-in chains

• PREROUTING: alters packets arrive from the network interface
• OUTPUT: alters locally-generated packets before routing them
• POSTROUTING: alters packets about to be sent out from host

Mangle: specialized packet alteration

Built-in chains

• PREROUTING: mangling packets before routing
• OUTPUT: mangling packets before sending
• INPUT: mangling packets destined for this host
• FORWARD: mangling packets routed through the host
• POSTROUTING: mangling packets about to be sent

Security: Consulted after the filter table to implement Mandatory Access Control network rules

Built-in chains

• INPUT: packets destined for the host
• OUTPUT: packets originating from the host
• FORWARD: packets forwarded through the host

Raw: rarely used

Built-in chains

• PREROUTING: processes all incoming packets
• OUTPUT: processes outgoing packets generated by the host

ElasticSearch

数据库

数据分析平台

Document APIs

RMDS（关系型数据库）: 事务性 / Join

ElasticSearch: 相关性（Score）/　高性能全文检索

Index 索引，一类文档的集合

每个索引都有自己的 Mapping 定义，定义文档字段类型（string, number, list, object）

7.0 以前，一个 Index 可以配置多个 Types

6.0 开始，Type 已经被废除

7.0 开始，一个索引只能创建一个 Type - “_doc”

Removal of types

Mapping Type 由 Lucence field 决定，不同 Type 中的相同文档字段会共享同一个 Mapping.

加入我需要删除 A Type 中的 user_name 字段而保留 B Type 中的 user_name 字段，这就会引起歧义。同时也会影响 Lucence 压缩文档的性能

替代解决办法

直接添加Type字段

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

PUT twitter
{
  "mappings": {
    "_doc": {
      "properties": {
        "type": { "type": "keyword" }, 
        "name": { "type": "text" },
        "user_name": { "type": "keyword" },
        "email": { "type": "keyword" },
        "content": { "type": "text" },
        "tweeted_at": { "type": "date" }
      }
    }
  }
}

PUT twitter/_doc/user-kimchy
{
  "type": "user", 
  "name": "Shay Banon",
  "user_name": "kimchy",
  "email": "shay@kimchy.com"
}

PUT twitter/_doc/tweet-1
{
  "type": "tweet", 
  "user_name": "kimchy",
  "tweeted_at": "2017-10-24T09:00:00Z",
  "content": "Types are going away"
}

GET twitter/_search
{
  "query": {
    "bool": {
      "must": {
        "match": {
          "user_name": "kimchy"
        }
      },
      "filter": {
        "match": {
          "type": "tweet" 
        }
      }
    }
  }
}

Bulk API

支持在一次 API 调用中，对不同的索引进行操作

集群

节点: 一个 ElasticSearch 实例

Master-eligible nodes

Master Node

集群状态：Cluster Status

Data Node 数据节点

Coordinating Node，处理客户端请求，集群每个节点都起到 Coordinating Node 的作用，应对高并发

分片：一个 Lucence 实例，解决数据水平扩展问题，解决数据高可用问题（读取的吞吐，IO）

倒排索引

正排索引：目录，文档ID到文档内容

倒排索引：索引页，单词到文档ID的索引

https://zh.wikipedia.org/wiki/%E5%80%92%E6%8E%92%E7%B4%A2%E5%BC%95

Feature Engineering

1. 数据预处理

sklearn.preprocessing

1
2

from sklearn.preprocessing import StandardScaler
StandardScaler().fit_transform(iris.data)

2. 特征选择

3.降维

PCA是为了让映射后的样本具有最大的发散性；而LDA是为了让映射后的样本有最好的分类性能。所以说PCA是一种无监督的降维方法，而LDA是一种有监督的降维方法。

References:

1. https://www.cnblogs.com/jasonfreak/p/5448385.html
2. https://sklearn.apachecn.org/#/docs/

Covolution Neuro Network

卷积

卷积运算，源于信号处理

感受野，接受域

只受３个输入单元影响，接受域为３，忽略接受域外权重（无限强先验）

优点

• 稀疏交互

• 参数共享，在不同输入位置上使用相同的参数。普通神经网络权重与神经元绑定，需要 $N_l N_{l+1}$ 个参数；卷积神经网络每个权重参数不变，只需要 $kk$ 个参数。

• 平移不变性，只包含局部连接关系（接受域）

96个[11x11x3]滤波器，如果在图像某些地方探测到一个水平的边界是很重要，那么在其他一些地方也会同样是有用的，这是因为图像结构具有平移不变性。

有的滤波器学习到了条纹，有些学到了色彩差别

CNN

输出尺寸：$\frac{W-F+2P}{S} + 1$

• F: fiter, 卷积核/滤波器/感受野的尺寸，常用3x3, 5x5
• P: padding, 零填充的数量. SAME(输出与输入保持一直，p=F-1/S)，VALID(不填充，输出尺寸减少, p=F/S)
• S: stride, 步长

code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65

# forward
def conv_forward_naive(x, w, b, conv_param):
    # input x: N data points, C channels, height H, width W
    N, C, H, W = x.shape
    # filter w: (F, C, HH, WW)
    F, _, HH, WW = w.shape
    
    stride, pad = conv_param['stride'], conv_param['pad']
    H_out = 1 + (H + 2 * pad - HH) // stride  
    W_out = 1 + (W + 2 * pad - WW) // stride
    out = np.zeros((N, F, H_out, W_out))
    
    # ０填充
    x_pad = np.pad(x, ((0,), (0,), (pad,), (pad,)), mode='constant', constant_values=0)
    
    # out: (N, F, H', W')  F filters
    # N个输入格式一致，直接在矩阵中操作
    # 遍历输出点高度和宽度(h_out, w_out)
    # 输出点从上到下，从左到右移动
    for h_out in range(H_out):
        for w_out in range(W_out):
            # 获得当前卷积核对应的输入块（HH,WW）
            x_pad_block = x_pad[:, :, h_out*stride:h_out*stride+HH, w_out*stride:w_out*stride+WW]
            # 计算每个卷积核（滤波器 f）得到的输出，对应点（h_out, w_out)
            for f in range(F):
                out[:, f, h_out, w_out] = np.sum(x_pad_block * w[f, :, :, :], axis=(1,2,3)) + b[f]

    cache = (x, w, b, conv_param)
    return out, cache

# backward
def conv_backward_naive(dout, cache):
    x, w, b, conv_param = cache
    N, C, H, W = x.shape
    F, _, HH, WW = w.shape
    _, _, H_out, W_out = dout.shape
    stride, pad = conv_param['stride'], conv_param['pad']
	
    # 0填充　padding
    x_pad = np.pad(x, ((0,), (0,), (pad,), (pad,)), mode='constant', constant_values=0)

    dx_pad = np.zeros_like(x_pad)
    dw = np.zeros_like(w)
    db = np.zeros_like(b)

    # 遍历数据输入n
    for n in range(N):
        # 遍历 filter f
        for f in range(F):
            # db (N,F)
            db[f] += np.sum(dout[n, f])
            # 遍历输出点高度和宽度　[h,w]
            for h_out in range(H_out):
                for w_out in range(W_out):
                    # 获得当前卷积核f对应的输入块（HH,WW）
                    x_pad_block = x_pad[n, :, h_out*stride:h_out*stride+HH, w_out*stride:w_out*stride+WW]
                    # dw (F,)
                    dw[f, :, :, :] += x_pad_block * dout[n, f, h_out, w_out]
                    dx_pad[n, :, h_out*stride:h_out*stride+HH, w_out*stride:w_out*stride+WW] += \
                        w[f, :, :, :] * dout[n, f, h_out, w_out]

    dx = dx_pad[:, :, pad:pad+H, pad:pad+W]
	
    # return Gradients: dx, dw, db
    return dx, dw, db

卷积层是如何解决不同大小输入的问题 ???

池化

特点

• 局部平移不变性：关心某个特征是否出现，不关心出现的具体位置　（无限强先验）
• 降采样：下一层少了 k 倍输入
• 综合池化区域(pool)的 k*k 个像素的统计特征
• 处理不同大小的输入，输出相同数量的统计特征

最大池化 pool (2, 2)，步长 stride 2，输出大小减半

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55

def max_pool_forward_naive(x, pool_param): 
    # input x: (N, C, H, W)
    N, C, H, W = x.shape
    # pool region: (heigth, width), stride
    pool_height = pool_param['pool_height']
    pool_width = pool_param['pool_width']
    stride = pool_param['stride']
    # output: (N, C, H', W')
    H_out = 1 + (H - pool_height) // stride 
    W_out = 1 + (W - pool_width) // stride
    out = np.zeros((N, C, H_out, W_out))

    # 遍历输出点高度和宽度 [h,w]
    for h in range(H_out):
        for w in range(W_out):
            # pool对应的输入块
            x_pad_block = x[:, :, h*stride:h*stride+pool_height, w*stride:w*stride+pool_width]
            # 最大池化，输出到　[:, :, h, w]
            out[:, :, h, w] = np.max(x_pad_block, axis=(-1, -2))

    cache = (x, pool_param)
    return out, cache


def max_pool_backward_naive(dout, cache):
    x, pool_param = cache
    N, C, H, W = x.shape
    # pool region: (heigth, width), stride
    pool_height = pool_param['pool_height']
    pool_width = pool_param['pool_width']
    stride = pool_param['stride']
    # output: (N, C, H', W')
    H_out = 1 + (H - pool_height) // stride 
    W_out = 1 + (W - pool_width) // stride
    # 初始化梯度　dx
    dx = np.zeros_like(x)
     
    # 遍历输入 n
    for n in range(N):
        # 遍历filter c
        for c in range(C):
            # 遍历输出点高度和宽度 [h, w]
            for h in range(H_out):
                for w in range(W_out):
                    # 当前输出点对应的 pool 输入块
                    x_pad_block = x[n, c, h*stride:h*stride+pool_height, w*stride:w*stride+pool_width]
                    # Find the index (row, col) of the max value
                    # grads on the max value is exists, else is 0
                    index = np.unravel_index(np.argmax(x_pad_block, axis=None), (pool_height, pool_width))
                    # pool对应的输入块各点的梯度
                    # 只有pool输入块中最大值对应的点(索引index)存在梯度，等于dout[n, c, h, w]，其余点梯度为0
                    dx[n, c, h*stride:h*stride+pool_height, w*stride:w*stride+pool_width][index] = dout[n, c, h, w]

    return dx

Backpropagation

Reference: Understanding the backward pass through Batch Normalization Layer

全连接网络数据指示图

$$w = w - \eta dw$$

Batch Normalization

批量归一化可以理解为在网络的每一层之前都做预处理，减少之前网络权重对数据的影响，保持每一层输出数据的分布（均值和标准差），使输出适应下一层网络，也使得每一层数据相对独立。

Internal Co-variate Shift

Reference: Batch Normalization原理与实战

随着训练的进行，网络中的参数也随着梯度下降在不停更新。一方面，当底层网络中参数发生微弱变化时，由于每一层中的线性变换与非线性激活映射，这些微弱变化随着网络层数的加深而被放大（类似蝴蝶效应）；另一方面，参数的变化导致每一层的输入分布会发生改变，进而下一层的网络需要不停地去适应这些分布变化，使得我们的模型训练变得困难。上述这一现象叫做Internal Covariate Shift。

原作定义：在深层网络训练的过程中，由于网络中参数变化而引起内部结点数据分布发生变化的这一过程被称作Internal Covariate Shift。

随着梯度下降的进行，每一层的参数$W^{[l]}$与$b^{[l]}$都会被更新，那么$Z^{[l]}$的分布也就发生了改变，进而$A^{[l]}$也同样出现分布的改变。而$A^{[l]}$作为第 $l+1$ 层的输入，意味着 $l+1$ 层需要去不停适应这种数据分布的变化，这一过程叫做 Interval Covariate Shift.

带来的问题：

1. 上层网络需要不停调整来适应输入数据分布的变化，导致网络学习速度的降低
2. 网络的训练过程容易陷入梯度饱和区，减缓网络收敛速度（sigmoid, tanh）。 $Z^{[l]}$会逐渐更新并变大，陷入梯度饱和区。可以通过Normalization 使得激活函数输入分布在一个稳定的空间来避免他们陷入梯度饱和区。

如何减缓 Interval Covariate Shift

1. 白化。成本高，改变了网络每一层分布导致数据表达的特征信息丢失

   • 使得输入特征分布具有相同的均值与方差。其中PCA白化保证了所有特征分布均值为0，方差为1
   • 去除特征之间的相关性

2. Batch Normalization 简化加改进版的白化

   • 简化。让每个特征都有均值为0，方差为1的分布就OK。
   • 白化操作减弱了网络中每一层输入数据表达能力，那我就再加个线性变换操作，让这些数据再能够尽可能恢复本身的表达能力就好了。

##　算法

BN 引入了两个可学习的参数 $\gamma$ 和 $\beta$（变换重构）。这两个参数的引入是为了恢复数据本身的表达能力，对规范后的数据进行线性变换，即$y_i = \gamma \hat{x_i} + \beta_i$。 特别的，当 $\gamma^2=\sigma ^2$（方差）, $\beta = \mu$ （均值）时，可以实现等价变换并且保留原始输入特征的分布信息。

Batch Normalization 的作用

1. 使得网络中每层输入数据的分布相对稳定，加快模型学习速度

2. 使得模型对参数不那么敏感，减小初始化参数对模型学习的影响，可以选择更大的初始化值，学习率选择范围更大

   当学习率设置太高时，会使得参数更新步伐过大，容易出现震荡和不收敛。但是使用BN的网络将不会受到参数数值大小的影响。BN抑制了参数微小变化随着网络层数加深被放大的问题，使得网络对参数大小的适应能力更强

3. 缓解梯度消失的问题

4. 正则化效果，mini-batch 的mean/variance 作为总体样本的抽样估计，引入随机噪声

BN通过将每一层网络的输入进行normalization，保证输入分布的均值与方差固定在一定范围内，减少了网络中的Internal Covariate Shift问题，并在一定程度上缓解了梯度消失，加速了模型收敛；并且BN使得网络对参数、激活函数更加具有鲁棒性，降低了神经网络模型训练和调参的复杂度；最后BN训练过程中由于使用mini-batch的mean/variance作为总体样本统计量估计，引入了随机噪声，在一定程度上对模型起到了正则化的效果。

前向传播

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57

def batchnorm_forward(x, gamma, beta, bn_param):
    """
    Forward pass for batch normalization.

    running_mean = momentum * running_mean + (1 - momentum) * sample_mean
    running_var = momentum * running_var + (1 - momentum) * sample_var

    Input:
    - x: Data of shape (N, D)
    - gamma: Scale parameter of shape (D,)
    - beta: Shift paremeter of shape (D,)
    - bn_param: Dictionary with the following keys:
      - mode: 'train' or 'test'; required
      - eps: Constant for numeric stability
      - momentum: Constant for running mean / variance.
      - running_mean: Array of shape (D,) giving running mean of features
      - running_var Array of shape (D,) giving running variance of features

    Returns a tuple of:
    - out: of shape (N, D)
    - cache: A tuple of values needed in the backward pass
    """
    mode = bn_param['mode']
    eps = bn_param.get('eps', 1e-5)
    momentum = bn_param.get('momentum', 0.9)

    N, D = x.shape
    running_mean = bn_param.get('running_mean', np.zeros(D, dtype=x.dtype))
    running_var = bn_param.get('running_var', np.zeros(D, dtype=x.dtype))

    out, cache = None, None
    if mode == 'train':
        ##########################################
        mu = np.mean(x, axis=0)
        var = np.var(x, axis=0)
        x_norm = (x - mu) / np.sqrt(var + eps)
        out = gamma * x_norm + beta
        ##########################################

        cache = (x, mu, var, eps, x_norm, gamma, beta, out)
        
        running_mean = momentum * running_mean + (1 - momentum) * mu
        running_var  = momentum * running_var  + (1 - momentum) * var
    elif mode == 'test':
        x_norm = (x - running_mean) / np.sqrt(running_var + eps)
       
    	# 训练超参数 gamma/beta，重构数据分布
    	out = gamma * x_norm + beta
    else:
        raise ValueError('Invalid forward batchnorm mode "%s"' % mode)

    # Store the updated running means back into bn_param
    bn_param['running_mean'] = running_mean
    bn_param['running_var'] = running_var

    return out, cache

反向传播指示图

损失函数对$y_i$的梯度为 $\frac{\partial L}{\partial y_i}$，由　$y_i = \gamma \hat{x_i} + \beta$ 得到：

$$\frac{\partial L}{\partial \beta} = \sum_{i=1}^{N} \frac{\partial L}{\partial y_i}$$

$$\frac{\partial L}{\partial \gamma} = \sum_{i=1}^{N} \frac{\partial L}{\partial y_i} \hat{x_i}$$

$$\frac{\partial L}{\partial \hat{x_i}} = \frac{\partial L}{\partial y_i} \gamma$$

$$\frac{\partial L}{\partial \mu} = \frac{\partial L}{\partial \hat{x_i}} \frac{\partial \hat{x_i}}{\partial \mu} + \frac{\partial L}{\partial \sigma^2} \frac{\partial {\sigma^2}}{\partial \mu} \ = -\frac{\partial L}{\partial \hat{x_i}} \frac{1}{\sqrt{\sigma^2 + \epsilon}} + \frac{\partial L}{\partial \sigma^2} (- \frac{2}{N} \sum_{i=1}^{N} (x_i-\mu)) $$

$$\frac{\partial L}{\partial \sigma^2} = \frac{\partial L}{\partial \hat{x_i}} \frac{\partial \hat{x_i}}{\partial \sigma^2} \ = \frac{\partial L}{\partial \hat{x_i}} (-\frac{1}{2} )({\sigma^2+\epsilon})^{-\frac{3}{2}}$$

$$\frac{\partial L}{\partial x_i} = \frac{\partial L}{\partial \hat{x_i}} \frac{\partial \hat{x_i}}{\partial {x_i}} + \frac{\partial L}{\partial \sigma^2} \frac{\partial \sigma^2}{\partial {x_i}} + \frac{\partial L}{\partial \mu}\frac{\partial \mu}{\partial x_i} \ = \frac{\partial L}{\partial \hat{x_i}} \frac{1}{\sqrt{\sigma^2 + \epsilon}} + \frac{\partial L}{\partial \sigma^2} \frac{2(x_i - \mu)}{N} + \frac{\partial L}{\partial \mu} \frac{1}{N} $$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

def batchnorm_backward_alt(dout, cache):
    """
    Alternative backward pass for batch normalization.     
    """
    (x, mu, var, eps, x_norm, gamma, beta, out) = cache
    N,D = dout.shape
    
    dx_norm = dout * gamma
    dgamma = np.sum(dout * x_norm, axis=0)
    dbeta  = np.sum(dout, axis=0)

    dvar = np.sum(dx_norm * (x - mu) * (-0.5) * np.power(var + eps, -3/2), axis=0)
    dmu = -np.sum(dx_norm / np.sqrt(var + eps), axis=0) + dvar * (-2) * np.sum(x - mu, axis=0) / N
    dx  =  dx_norm / np.sqrt(var + eps) + dvar * 2 * (x - mu) / N  + dmu / N     

    return dx, dgamma, dbeta

分步计算损失函数梯度的方法参考 Reference 2

Refereces:

1. https://www.adityaagrawal.net/blog/deep_learning/bprop_batch_norm
2. https://kratzert.github.io/2016/02/12/understanding-the-gradient-flow-through-the-batch-normalization-layer.html

Dropout

1. Bagging 集成模型，随机抽样神经网络的子集。很多个共享参数的子网络组成。
2. 增强单个神经元独立学习特征的能力，减少神经元之间的依赖（避免学习某些固定组合才产生的特征，有意识的让神经网络去学习一些普遍的共性）
3. 加性噪声

Code

前向传播

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

def dropout_forward(X, mode):
    """
	反向随机失活: 推荐实现方式。
	确保某单元的期望输出与没有dropout时期望输出大致相同
	在训练的时候drop和调整数值范围，测试时不做任何事.
	"""
    p = 0.5 	# 激活神经元的概率. p值更高 = 随机失活更弱
    
  	# 神经元以p的概率失活 [0, 1]随机分布 P(rand(x)) < p = p
  	# 第一个随机失活掩码. 注意/p! inverted dropout, 保持当前层输出期望一致
  	if mode == 'train':
    	mask = (np.random.rand(*H1.shape) < p) / p
  		out = x * mask
    elif mode == 'test':
        out = x
    
    return out, mask

反向传播

1
2
3
4
5
6
7

def dropout_backward(dout, mode, mask):    
    if mode == 'train':
        dx = dout * mask
    elif mode == 'test':
        dx = dout
        
    return dx