In Search of an Understandable Consensus Algorithm<一>

简介

Raft是用于管理复制日志的一致性算法，但由于与paxos结构不同，raft更加容易被理解。

Introduction

共识算法可以使得一组机器作为一个工作组，在某些成员故障时仍然能很好地运行。

raft算法有几点创新点：

• Strong leader：例如所有日志都只能从该leader流向其它服务器；
• Leader election：Raft使用随机的定时器来选举leader；
• Membership changes：raft更改集群中服务器集的机制，使用了一种新的共识算法，两种不同配置的机器允许在转换期间重叠；

Replicated state machines

共识算法通常出现在复制状态机的上下文中，通过复制日志实现，如下图，每个服务器都存储着一些列命令的日志，状态机按顺序执行，由于状态机时确定性的，因此每个都计算出相同的状态和输出序列。

保障复制日志的一致性是一致性算法的工作。服务器的共识模块从客户端接受命令并将其添加到日志中。正确复制命令后，每个服务器的状态机按日志顺序处理它们，并将输出返回给客户端。

生产系统的共识算法具备以下特点：

• safety：永远不返回不正确的结果，包括网络延迟，分区和数据包丢失，重复和重新排序；
• 只要大多数服务器都可以运行并且可以与客户和客户进行通信，它们就可以正常运行（可用）；
• 不依赖于时间来确保日志的一致性；
• 在通常情况下，只要大多数群集响应了RPC，命令就可以完成；

The Raft consensus algorithm

下图简洁地总结了raft算法：

raft通过选举一个leader来实现共识，然后让该leader负责管理复制的日志。leader可能会与服务器断开连接，这时需要选出新的leader。

raft basic

raft集群中包含多个服务器，在任意时间内，每个服务器都处于以下三种状态之一：leader、follower、candidate。一般情况下，只有一个leader，其它都是follower。follower不会自发请求，而是响应leader和candidate的请求，leader处理所有来自client的请求（即便client私自联系了follower，也会被重定向到leader）。以下是状态转换图：

raft将时间划分为任意长度，如下图：

term是一个逻辑时钟，采用连续的整数编号。每个term都以选举开始，如果有candidate成为了leader，那么它将成为在剩下的term时间内成为leader。raft保障在一个term内最多只有一个leader。

不同的服务器可以在不同的时间观察term之间的转换，每个服务器都有一个当前的term编号，并且随着时间单调递增。服务器间通信时交换当前term。如果一个服务器的当前term小于另一个服务器的当前term，则它将其当前term更新为更大的值。 如果候选人或领导者发现其term已过期，则会立即变成到follower的状态。 如果服务器收到带有过期term的请求，它将拒绝该请求。

Raft服务器使用远程过程调用（RPC）进行通信。RequestVote RPCs由candidate在选举期间启动，Append-Entries RPCs由leader发起，用来复制日志条目并提供心跳形式。

Leader election

raft使用心跳机制出发leader选举，leader向所有follower定期发送heartbeat(log entry为空的appendEntries RPC)。如果follower在选举超时的一定时间内没有收到任何联系，则会假定没有leader并开始重新选举。

在开始选举时，follower会增加当前的term，并切换到candidate状态，然后它会给自己投上一票，并向所有其它server发送RequestVote RPC。candidate接下来会遇到以下三种情况：

• 它赢得了选举；
• 有其他服务器成为了leader；
• 一段时间内没有选出leader；

如果candidate在相同的期限内收到来自完整集群中大多数服务器的投票，则candidate将赢得选举。每个服务器将按照first-come-first-served的规则对给定期限内的一个候选人进行投票。一旦赢得选举，它会向所有其它服务器发送heartbeat，以确定自己的身份并阻止后续选举。

在等待投票时，candidate可能会从另外的服务器上收到声称自己的是leader的AppendEntries RPC，这时会比较term，如果当前term小于RPC的term，则会视为合法，并返回follower状态。否则会拒绝RPC并保持candidate状态。

第三种情况是由于出现了许多的candidate，使得投票分割，以便没有candidate获得多数票。这样每个candidate会超时并开始一个新的选举，增加其term。但是，如果不采取额外措施，分割票数可能会无限期重复。

raft使用随机选举超时的机制来避免分割投票，从固定的范围内随机选择时间(150-300ms)选择一个时间作为选举超时，使得在大多数情况下只有一台服务器会超时，它会赢得选举并在其他服务器超时之前发送heartbeat。同理，这样可以解决分割投票的问题，每个candidate在重新选举时重启并选择随机选举超时，这减少了新选举时另一次分割投票的可能性。

Log replication

在leader选举完毕之后，就开始为client请求提供服务，client把这些命令提供给状态机，leader则把命令作为新的条目添加到日志中，并通过AppendEntries RPC并行地发送到每个其它的服务器以复制条目。如果发送失败/包丢失/follower崩溃，leader会无限重试。

日志的组织结构如下，每个条目都有一个term编号：

Raft保证提交的条目是持久的，并最终由所有可用的状态机执行。一旦创建条目的领导者将其复制到大多数服务器上（例如，上图中的条目7），就会提交日志条目。并且还会提交leader日志中的所有前面的日志。

Log Matching属性：

• 如果不同日志中的两个条目具有相同的index和term，则它们存储相同的命令。
• 如果不同日志中的两个条目具有相同的index和term，则所有前面的条目中的日志相同。

第一个属性是基于leader在给定的term中最多创建一个具有给定日志索引的条目，并永远不会更改其在日志中的位置；第二个属性由AppendEntries执行的简单一致性检查保证。发送AppendEntries RPC时，leader在其日志中加入紧接在新条目之前的条目的索引和term。如果follower找不到相同索引和term的条目，则拒绝新日志条目。

正常情况下，leader和follower保持着一致的日志，但也有可能出现日志不一致的情况，比如旧leader可能不提交日志，如下：

为了解决这种情况。raft会让leader通过强制follower的日志复制自己的日志来覆盖处理。

要使得follower的日志与leader保持一致，leader必须找到共同的最新日志条目，在该店之后删除follower日志中的所有条目，然后往follower发送这之后的所有在leader上存在的日志。所有这些操作都是在响应AppendEntries RPC执行的一致性检查时发生的。leader为每个follower维护一个nextIndex，这是leader将发送给follower的下一个日志条目的索引。leader选举出来后，所有的nextIndex会被初始化到其日志中最后一个之后的索引（上图中的11）。如果不一致，RPC将会失败，拒绝后，leader会减少nextIndex，知道RPC成功。

当然也可以做优化，减少AppendEntries RPC，则follower可以发送冲突条目的term和它为该term存储的第一个索引。这样就是一个term一次RPC。

该机制使得leader在选举出来后，无需采取额外的操作恢复日志，而是正常运行，并且由于RPC自动收敛日志。Leader Append-Only，leader永远不会覆盖或者删除自己的日志。

Safety

当leader提交多个日志时，follower可能崩溃了，这时新的leader会用新的日志条目覆盖原来的那些日志，导致不同的状态机可能执行不同的命令序列。

Election restriction

在基于leader的一致性算法中，leader最终会存储所有提交的日志条目，raft通过保证先前term的所有已提交的日志条目从其选举时出现在每个新leader身上，这意味着日志只会从了leader流向follower，leader之间不会覆盖日志。

如果candidate的日志中没有与大多机器的日志保持着最新，raft会使用投票来阻止candidate赢得选举。RequestVote RPC实现了这一限制：RPC包含有关候选人日志的信息，如果其自己的日志比候选者的日志更新，则选民拒绝其投票。

通过比较日志中最后一个条目的索引和术语，Raft确定两个日志中哪一个更新。如果日志包含具有不同term的最后一个条目，则具有较晚term的日志为新的。如果日志以相同的term结束，则索引更大的日志是新的。

Committing entries from previous terms

一个leader不能立马对之前term的log entry是否复制到大多数server来判断其是否已被提交。下图就是这样一个例子：

在c中，term2的日志已经在大多数server中了，但如果此时leader S1 crash的话，在d这种情况下，term2的日志会被新leader S5给重写。

为了消除这种情况，raft不会通过副本数来commit之前的log entries。只有当前term的log entries才会通过计算副本数被commit。

Safety argument

现在来证明Leader Completeness Property。

假设leader在term T 提交了一个当前term的log entry，但是这个log entry在随后的term没有被leader保存。term U是大于term T的最小的term，并且term U的leader没有包含这个log entry。

1. 在选举时leader U的日志中一定没有提交该条目（leader永远不会删除或覆盖条目）
2. leaderT复制了大多数机器的条目，leaderU从集群的大多数群体中获得了投票。因此，至少一个服务器（“voter”）接受了来自leaderT的条目并投票给了leaderU；这个voter就是矛盾的关键；
3. voter必须在给leader U投票之前收到了被leader T提交的entry。否则它会拒绝来自leader T的AppendEntries请求，因为它当前的term比T的高；
4. 当voter投票给leader U的时候，它仍然保存着这个entry，这中间的所有leader都会包含了这个条目；
5. voter将票投给了leader U，所以leader U的log必须和voter至少是一样新的。这就导致了两个矛盾；

Follower and candidate crashes

相对leader失败，follower和candidate的crash更容易被处理，而且都是通过重试来完成，这是因为raft的RPC都是幂等的。

Timing and availability

我们对raft的一个要求是安全性不能取决于时间安排，而可用性(系统及时对客户端作出响应的能力)则必然取决于时间。选举leader就体现了时间的重要性，只要系统满足以下的时间要求，就能保持稳定的leader： \[ broadcastTime << electionTimeout << MTBF \]

• broadcastTime：每个服务器发送RPC并接受响应的平均时间；
• electionTimeout：选举超时；
• MTBF：单个服务器的平均故障间隔时间；

broadcastTime和MTBF都是底层系统的属性，而选举超时则是我们设计的。broadcastTime可能在0.5ms到20ms之间，选举超时可能介于10毫秒到500毫秒之间。

The Design of a Practical System for Practical System for Fault-Tolerant Virtual Machines

ABSTRACT

一个容错虚拟机分布式系统的设计

INTRODUCTION

对于分布式系统而言，有很多通用的容错方法：

• 主备服务器：在主服务器挂掉了，由备份服务器接管工作。需要大量带宽在主备间传输状态；
• 状态机方法：让两台机器初始化为相同状态，然后接受相同的输入，使得两台机器保持同步。保持两台机器同步的额外信息数量远少于改变主服务器的状态量；然而可能存在一些不确定的操作（如读取时钟），因此必须同步这些不确定操作的结果；

primary和backup之间传递deterministic operation + non-deterministic operation's result；

BASIC FT DESIGN

上图展示了容错虚拟机的基本配置。primary VM和backup VM运行在不同的物理机上，并保持同步（backup会稍有迟延），并且它们使用共享磁盘空间。primary VM将接收到的输入通过Logging channel传送到backup VM。虽然两者都执行相同的输入，但只有primary VM会输出返回给client，因为backup VM会被hypervisor终止掉。backup会通过ack应答来保证没有数据丢失。primary VM和backup VM之间会通过 heartbeat 进行 fail 检测。

Deterministic Replay Implementation

正如上文提到过的，让两台机器处于相同的初始状态，然后以相同的顺序提供相同的输入，这样两台机器就能经历相同的状态序列并产生相同的输出。

但由于存在非确定性的事件(虚拟中断)或者操作(读取处理器时钟技术器)，这样会影响VM的状态。

这里的挑战在于：

• 需要捕捉全部的输入和非确定性操作，以此保证backup是确定性；
• 需要将所有的输入和非确定性操作应用到backup中；
• 需要保证系统高效；

设计方案：将所有的输入和非确定性操作记录到日志文件，并且对于非确定性操作，还必须要把相关的状态信息记录到日志文件中。

FT Protocol

FT协议是用于logging channel的协议

• 输出要求：

如果primary宕机了，backup会接管它的工作，并且backup会执行与primary一致的输出

• 输出规则：

在backup VM收到并应答所有的日志之前，primary都不会把输出发送给外部

并且，基于这个输出规则来说，primary VM不会停止执行，它只是延迟发送输出。

FT协议的流程如下图：

但这里存在一个小问题，如果 primary 宕机了，backup 不能判断它是在发送了 output 之前还是之后宕机的，因此 backup 会再发送一次 output，但可以通过以下方式解决：

• 诸如TCP等网络协议能够检查丢失或者重复的数据包；

Detecting and Responding to Failure

如果是backup宕机，primary会停止发送日志。如果primary宕机，情况复杂一点，backup会接替它的工作，在执行完接收到的日志记录之后，成为primary真正对外输出。

存在一些方法检测宕机，比如通过UDP heartbeat来检测primary与backup之间是否正常通信。另外，还会监控logging channel的日志流量。

但这些方法仍然无法解决split-brain问题，即primary和backup同时宕机。为了解决这个问题，该设计使用了共享存储，提供了一个原子操作test-and-set，primary和backup无法同时在该区域操作。

PRACTICAL IMPLEMENTATION OF FT

Starting and Restarting FT VMs

在设计系统时，需要考虑如何启动/重启一个与primary状态一致的backup？

VMware VMotion能够使得一个运行中的VM从一个server迁移到另一个server，并且只需要很短的中断。这里做了一些改动，并不是进行迁移，而是在远程主机上克隆一个，并使得源VM进去logging mode，目标VM进入replay mode。

除此之外，由于VM都运行在同一个集群，访问同一个存储区域，因此在选择哪个server作为backup时，是由primary同志集群服务实现的。

Managing the Logging Channel

存在几种实现方法，管理logging channel的流量。

如下图所示，hypervisor维持了一个很大的log buffer，存着primary和backup的日志。primary往buffer写入日志，而backup则从中读取日志。这两者的操作类似于一个队列，backup遇到的空buffer，影响不大。但如果primary遇到满的buffer，会停止写入并停止对外输出。

因此我们需要一种机制来降低primary的速度，在logging channel增加额外的信息来通知primary，降低server上CPU的使用限制。

Operation on FT VMs

另一个需要关注的实际问题是如何应对primary的多种控制操作。一般来说，大多VM操作只会在primary初始化，然后将必要的信息发送给backup。唯一一个在primary和backup独立的操作是VMotion，请注意，VMware FT确保两个VM都不会移动到另一个VM所在的服务器，因为这种情况不再提供容错功能。

对于primary来说，VMotion会导致backup与primary断开连接，然后重连。

对于backup来说，由于backup同时还在重放primary的操作和完成IO（VMotion需要停顿IO），所以VMotion会比较复杂。VMware的方法是当backup VM位于VMotion的最终切换点时，它通过日志记录通道请求primary VM暂时停顿其所有IO。 然后，backup VM的IO将在单个执行点自然停顿，因为它重放primary VM执行静止操作。

Implementation Issues for Disk IOs

• 磁盘操作是非阻塞的、可以并行操作，这样会导致non-determinism；

解决方法：检测IO races，并强制这些操作串行

• 磁盘操作很可能与其它应用或者OS在访问同一块内存时产生竞争，因为磁盘操作是通过DMA实现的，会导致non-determinism；

解决方法；设置页保护，但修改MMU的页保护代价太高了。因此这里是用了bounce buffer的设计，这是一块与访问内存等大的buffer。读操作将内存读入buffer，待IO完成了再写回内存；写操作则是将内容写入buffer，稍后写入磁盘。

• 当backup接管失效的primary，成为新的primary后，无法确定磁盘IO是否已经完成；

解决方法：发送一个error，表明所有IO都失败了，然后重新执行磁盘IO操作，无论是否已经成功

Implementation Issues for Network IO

系统设计了关于网络的性能优化。

由于这些优化很多都基于异步的执行，而这些操作可能回导致non-determinism，因此一个重要的问题是如何禁止这些异步的网络优化。

我们采取两个办法来提高VM的网络性能：

• 实现集群优化，减少VM的traps和中断；
• 降低发送packets的延迟，减少发送日志消息和等待ack的时间，方法是避免线程切换；

DESIGN ALTERNATIVES

Shared vs Non-shared Disk

存在一个可替代的设计方法，那就是primary和backup拥有独立的虚拟磁盘(non-shared)，保证磁盘内容的同步，这样disk就变成了VM内部的状态。如下图：

这种设计的一大缺点就是为了保证容错，必须要确保虚拟磁盘以某些方法同步。在面对split-brain问题时，需要使用一个第三方服务器（primary和backup都能访问的）

Executing Disk Reads on the Backup VM

在我们的设计中，磁盘的读入不是直接输入backup的，而是通过logging channel获取相关读取信息的。

这种设计方案可以减少logging channel的流量，但面临更多的小问题：

• 因为backup要执行读取，这样会降低backup VM的执行速度；
• 要处理好失败的磁盘读取操作，如果backup失败，primary成功，需要重试；如果反过来，primary需要通过logging channel告知backup不需要做备份；
• 在shared disk的情况下，如果primary在读完磁盘之后想马上执行写入到相同位置，则必须要等待backup也读取完毕；

集成学习

个体与集成

集成学习通过构建并结合多个学习器来完成学习任务，以下图为例，集成学习时先产生一组个体学习器，然后通过某种策略将其结合起来。如果其中的个体学习器是同种类型的，则是同质集成，否则叫异质的，

集成学习的结果是通过投票法产生的，为了使得集成学习的效果比单一学习器更好，应该要保证个体学习器具备一定的准确性，同时要有多样性，则学习器之间具有差异。

假设存在二分类问题和真实函数f，如果基分类器的错误率为\(\epsilon\)，则对于每个分类器hi有： \[ P(h_i(x) \ne f(x)) = \epsilon \] 如果基分类器的错误率相互独立，那么集成学习的错误率有： \[ P(h_i(x) \ne f(x)) = \sum_{k=0}^{[T/2]} C_T^k (1-\epsilon)^k \epsilon^{T-k} \\ \leq exp(-1/2T(1-2\epsilon)^2) \] 可以看到随着个体学习器数目的增加，集成的错误率降指数下降。

但往往基学习器的误差不是相互独立的，而且一般准确性很高的话，要增加多样性就必须牺牲准确性，

目前集成学习中，个体学习强依赖的代表是Boosting，而非强依赖的代表是Bagging和Random Forest。

Boosting

Boosting是将弱学习器提升为强学习器的算法：先从初始训练集中训练出一个基学习器，然后根据该学习器的表现对训练样本的分布进行调整，根据调整后的样本分布来训练下一个基学习器。

Boost的代表是AdaBoost。

AdaBoost有多种推导方式，我们这里采用基学习器的线性组合： \[ H(x) = \sum_{t=1}^T\alpha_th_t(x) \] AdaBoost的算法如下：

给定一个训练数据集D={(x1,y1), (x2,y2)…(xN,yN)}，yi属于标记集合{-1,+1}。

1. \(D_1(x) = 1/m\)，每一个训练样本最开始时都被赋予相同的权值：1/N；
2. 进行多轮迭代，假设迭代T次。for t = 1, 2, .. ,T

• \(h_t = \xi(D, D_t);\)基于分布\(D_t\)从数据集中训练出分类器\(h_t\)；
• \(\epsilon_{t} = P_{x-D_t}(h_t(x)\ne f(x));\)计算分类器的错误率；
• 如果错误率比随机猜测还要差，那么意味着当前的基学习器不满足基本条件，放弃该学习器；
• \(\alpha_t = 1/2 ln(\frac{1-\epsilon_t}{\epsilon_t})\)；确定该分类器的权重；
• \(D_{t+1}(x) = \frac{D_t(x) exp(-\alpha_tf(x)h_t(x))}{Z_t}\)；更新样本的权重，其中Z是一个规范化因子，以确保\(D_{t+1}\)是一个分布；每个样本的新权值是变大还是变小，取决于它是被分错还是被分正确；

3. 输出\(H(x)=sign(\sum_{t=1}^T \alpha_th_t(x))\)；

若H(x)能令指数损失函数最小化，可以求偏导： \[ \frac {\alpha l_{exp}(H|D)} {\alpha H(x)} = -e^{-H(x)} P(f(x)=1|x) + e^{H(x)}P(f(x)=-1|x) \] 令上式为0，可求解： \[ H(x) = 1/2 ln \frac{P(f(x)=1|x)}{P(f(x)=-1|x)} \] 依赖这个式子，我们可以求得分类器权重的更新公式。

对于无法重新赋权的训练样本，可以通过重新采样的方法来处理。如上所述，如果初始设置的学习轮数还没到T，可能导致只包含少量基学习器而性能不佳的情况。重采样可以在抛弃不满足基本条件的基学习器之后，根据当前分布重新对样本进行采样，再基于采样结果训练出基学习器，使得学习过程可以在T轮完成。

Boosting主要关注降低偏差，可以基于泛化能力较弱的学习器构建出强的集成。

Bagging与随机森林

为了得到泛化能力强的集成，集成中的个体学习器应该尽可能独立，一种可能的做法是进行随机取样，根据不同的样本训练得到相对独立的基学习器。但这种做法又可能因为数据量不够而导致学习器的准确性不够高。

Bagging

bagging是一种并行式的集成学习方法。给定m个样本的数据集，我们每次随机从中抽出一个样本放入采样集中，抽出的样本需要重新放回去。经过m次抽取，我们得到一个m个样本的数据集。其中采样集中有可能存在重复的数据。

采样了T个含有m个训练样本的数据集，然后基于每个数据集训练出一个基学习器，然后将这些基学习器进行组合，对于分类任务使用简单投票法，而对于回归任务则是使用简单平均法。

优点：

• Bagging可以应用于多分类、回归等任务；
• 由于每个基学习器只用了六成的数据，因此可以用剩下的数据坐泛化能力的"包外预计"；

随机森林

随机森林是Bagging的一个扩展变形，在以决策树为基学习器构建Bagging集成的基础上，进一步在决策树的训练过程中引入了随机属性的选择。

传统决策树在当前节点从d个属性中选择一个最优属性，而在RF中，则是先从该节点的属性集合中随机选择一个包含k个属性的子集，然后再从中选择一个最优属性。

一般情况下，推荐\(k=log_2d\)。

随机森林的泛化误差比Bagging更小。

结合策略

学习器结合的优点：

• 减小因为单学习器可能带来的误选而导致泛化能力不佳的风险；
• 多次运行进行结合，避免陷入局部最小点；
• 某些学习任务的真实假设可能并不在单学习器当前学习算法所考虑的假设空间中；

平均法

加权平均法： \[ H(x) = \sum_{i=1}^Tw_ih_i(w) \] 其中，\(w_i \ge 0, \sum_{i=1}^Tw_i=1\)；简单平均法，则是令\(w_i=1/T\)的特例。

一般而言，在个体学习器性能相差较大时宜使用加权平均法，而在个体学习器性能相近时则使用简单平均法。

投票法

投票法有几种，假设\(h_i^j(x)\)是分类器\(h_i\)在类别标记\(c_j\)上的输出。

• 绝对多数投票法

\[ H(x)=\left\{ \begin{array}{rcl} c_j & & {if \sum_{i=1}^T h_i^j(x) \ge 0.5\sum_{k=1}^T \sum_{i=1}^T h_i^k(x)}\\ reject & & {otherwise} \end{array} \right. \]

对于可靠性的学习任务中，这个机制提供了拒绝预测的选项

• 相对多数投票法

\[ H(x) = c_{arg max _j } \sum_{i=1}^Th_i^j(x) \]

若同时有多个类别获得了最高票，则随机选一个。

• 加权投票法

\[ H(x) = c_{arg max _j } \sum_{i=1}^T w_ih_i^j(x) \]

一般情况下，对于不同的学习器可能会产生不同类型的值，比如类标记和类概率。在这种情况下，类概率输出转化为类标记输出（例如将类概率最大的设置为1，其它为0），然后再投票。

学习法

当训练数据很多时，我们可以使用另一种更为强大的结合策略——通过另一个学习器进行结合。

Stacking是这类策略的代表，其先从初始数据集训练出初级学习器，然后"生成"一个新的数据集用于训练次级学习器。

为了避免过拟合，一般是采用交叉验证的方式，即用训练初级学习器未使用的样本来产生次级学习器的训练样本。以k折交叉验证为例，初始训练集D被随机划分为k个大小相似的集合\(D_1,..,D_k\)。令\(D_j\)和\(\overline D_j = D-D_j\)分别表示在第j折的测试集和训练集。

算法的具体过程如下：

• 给定T个初级学习算法，初级学习器\(h_t^{(j)}\)通过在\(\overline D_j\)上使用第t个学习算法而得；
• 对\(D_j\)中每个样本\(x_i\)，计算\(z_{it}=h_t^{(j)}(x_i)\)，则由样本产生的次级训练样例为\(z_i=(z_{i1},…,z_{iT})\)，标记部分为\(y_i\)；
• 交叉验证结束之后，由初级学习器产生的次级训练集\(D' = \{(z_i,y_i)\}^m_{i=1}\)，并由此训练次级学习器；

次级学习器的输入属性表示和次级学习算法对stacking集成的泛化性能由很大的影响。

多样性

误差——分歧分解

为了使得泛化能力提高，个体学习器应该"好而不同"。因此我们来做一点理论分析：

假设对于数据x，定义学习器h得分歧为： \[ A(h_i|x) = (h_i(x)-H(x))^2\\ 则集成的分歧为：\overline A(h_i|x) = \sum_{i=1}^Tw_i(h_i(x)-H(x))^2 \] 而个体学习器和集成学习器的平方误差为： \[ E(h_i|x) = (f(x)-h_i(x))^2 \\ \overline E(h|x) = \sum_{i=1}^T w_i E(h_i|x) \\ E(H|x) = (f(x)-H(x))^2 \] 则可以根据上式求得： \[ \overline A(h|x) = \overline E(h|x) -E(H|x) \] 因此可以求得\(E = \overline E - \overline A\)，即个体学习器准确性越高，多样性越好，则集成效果越好。

多样性度量

多样性度量其实就是度量集成个体分类器的多样性，比较典型的做法是考虑个体分类器的两两相似/不相似性，以两分类为例：

其中，a表示两个分类器都预测为正类的样本数目，a+b+c+d=m。以下是一些常见的多样性度量：

• 不合度量

\[ dis_{ij} = \frac{b+c}{m} \]

• 相关系数

\[ p_{ij} = \frac{ad-bc}{\sqrt{(a+b)(a+c)(c+d)(b+d)}} \]

该系数的值域为[-1,1]，若两分类器无关，则值为0.若为正相关，则值为正，否则为负；

• Q-统计量

\[ Q_{ij} = \frac{ad-bc}{ad+bc} \]

其与上面相关系数符号相同；

• k-统计量

\[ k = \frac{p1-p2}{1-p2} \]

其中，p1是两个分类器取得一致的概率；p2是两个分类器偶然达成一致的概率： \[ p1 = \frac{a+d}{m} \\ p2 = \frac{(a+b)(a+c)+(c+d)(b+d)}{m^2} \] 若分类器在数据集上完全一致，则k=1；若它们仅仅是偶然性达成一致，则k=0；k通常为非负值，仅仅在分类器达成一致的概率比偶然性的情况下还低时取负值。

多样性增强

要生成多样性大的个体学习器，比较直接的方法是在学习过程引入随机性。

• 数据样本扰动

基于采样法，对训练样本稍加变化。但有些稳定学习器对数据样本的扰动并不敏感。

• 输入属性扰动

该方法一般是从初始属性集中抽出若干个属性子集，这样做不但能增加多样性，还能减少训练时间。但对于属性较少的样本不适宜。

• 输出表示扰动

此类做法的基本思路是对输出表示进行操纵以增强多样性，可以对训练样本的类标记做少许改动，也可以对输出表示进行转化，还可以将原任务拆解成多个子任务。

• 算法参数扰动

对基学习算法的一些参数进行设置，比较常见的是神经网络的参数设置。

The Google File System

论文《The Google File System》

INTRODUCTION

Google File System (GFS)是谷歌提出的一种快速处理数据的文件系统，与传统的分布式文件系统一样，对于性能，可扩展性，可靠性和可用性都有一定的需求。但通过与传统的分布式文件系统相比较，Google认为：

• 组件故障是常态的而非例外；
• 传统标准意义的文件很大；
• 大多数文件在发生变更时，是通过添加新的数据，而不是覆盖原有数据；
• 通过提高我们的灵活性，共同设计应用程序和文件系统API有益于整个系统；

DESIGN OVERVIEW

Assumptions

为了设计符合需求的文件系统，有一些细节需要明确的。

• 该系统的组成部分容易出故障；
• 系统需存储大量的文件；
• 在读取时产生workload，主要出现在大型的流式读取和小的随机读取；
• 在写入时产生workload，主要出现在顺序的追加写入；
• 系统必须为同时附加到同一文件的多个客户端有效地实现明确定义的语义，需要使用原子写入；
• 高带宽比低延迟更重要；

Interface

GFS提供了熟悉的文件系统接口，但它没有实现POSIX等标准API。

此外，GFS还实现了快照和记录追加操作，Record append允许多个客户端同时将数据追加到同一文件，同时保证每个客户端追加的原子性。

Architecture

一个GFS集群包含了一个master服务器和多个被client访问的chunk服务器，每个chunk服务器都是跑着用户级进程的Linux主机。文件被分成固定大小的块存储在chunkserver上，拥有一个唯一的、由master分配的64位ID。为了可靠性，每个chunkserver都做了多重备份，如三备份。

master存储着所有的文件元数据信息，并且与chunkserver通过心跳机制进行沟通。

client和chunkserver都不对文件进行缓存，而是有Linux本身的文件、内存机制进行管理，因为文件太大了。

Single Master

单个master对于我们的设计非常有帮助，为了不使master成为系统的瓶颈，我们需要减少master的IO。因此client不会直接通过master会读写数据，而是向master发送(file name, chunk index)请求，master返回(chunk handle, chunk locations)，这样client就可以通过这个handle和byte range向最近的chunk server获取数据。

对于相同的chunk的读取，client不会再向master做请求，而是到了cache的信息过期了，或者相关文件重新被打开了，才会去与master交互。

Chunk Size

chunk size是关键的设计参数，在这里选定了64MB大小，比一般的文件系统的block略大。

优点：

• 减少了与master交互，因为只需要一次初始的请求得知chunk的位置即可；
• client能对chunk做尽可能多的操作，减少了通过TCP连接时的网络负载；
• 减少了存在master的元数据信息大小，使得其可以存放在内存；

缺点：

• 对于一个小文件，可能只有一个chunk，这很可能因为client都访问同一个文件，造成hot spot的问题；

Metedata

master会保存三种元数据类型：文件和块的命名空间，文件到块的映射，块的位置，所有这些元数据都在master的内存中。

In-Memory Data Structures

把元数据存储在内存中，提高了master的操作速度，并使得master定期扫描元数据状态变得更加方便。另外，虽然这种方式受制于机器内存，但由于每个文件都会有少数的块是部分满的，对于64MB大小的chunk size，我们会采用64个字节去存储元信息。因此可以用来存储这些小于64个字节的元数据信息。除此之外，必要地增加内存也不是很麻烦的事情。

Chunk Locations

master不会拥有chunkserver中关于某个块位置的持久化记录，而是在启动后定期轮询chunkserver（或者有新的GFS chunkserver加入时），获取该信息。因为GFS chunkserver很容易出现宕机，重启等行为，这样GFS master在每次发生这些事件的时候，都要修改持久化存储里面的位置信息的数据。

Operation Log

操作日志包含关键元数据更改的历史记录。 它是GFS的核心。它不仅是元数据的唯一持久记录，而且还充当定义并发操作顺序的逻辑时间线。

在存储时，只有当操作日志被写入到本地master和远程时，master才会对client返回成功。并且，为了提高IO吞吐，master会对日志记录进行批处理。

关于操作日志，master只有在操作日志达到一定大小时才会进行checkpoint，并且checkpoint以B树的结构在内存中存在，之后则可以通过加载最新的checkpoint来重放这之后的操作日志。因为build checkpoint需要一定的时间，所以master会新开一个线程做checkpoint，从而避免影响到来的请求。

Consistency Model

Guarantees by GFS

文件命名空间的修改，比如创建文件，都是由master进行的院子操作，master的操作日志定义了一个全局的执行顺序。

数据修改后，文件区域的状态取决于修改类型，如下图：

• consistent: 所有的client都能看到相同的数据；
• defined: 在文件被修改后，该区域时consistent的并且client能够看到其修改了什么；

Implications for Applications

事实上，应用在修改文件时往往是追加而不是覆盖，典型的，一个writer创建文件后从头到尾追加。追加文件的操作相对于随机写，其效率更高，并且更容易应对应用失败，只需要使用checkpoint重启增量写即可，还可以避免reader读到不完整的数据。

除此之外，还会经常出现的场景是，多个writers并发地追加到一个文件，以作归并输出。readers通过辨识writer留下的检验信息，可以认出并去除额外的对齐和记录碎片，还可以用唯一的ID去除重复的记录。

SYSTEM INTERACTIONS

所有的操作都应该尽量减少与master的交互

Leases and Mutation Order

由于master对于后续的数据流操作是不作控制的，因此需要一种机制保证，多副本以相同的操作顺序写入。GFS会从chunk选定一个chunk server，发送lease，称作primary。由这个primary chunkServer控制写入的顺序。

lease的初始超时为60秒，这些lease是搭载在HeartBeat信息上的，当master与primary失去连接，也可以在旧lease过期重新选择primary。

下图为该控制流程：

1. client向master请求当前lease是哪个chunk，和所有的相关副本。如果还没有lease，master则分配一个；
2. master返回primary的id和其副本的所在位置给client。client会缓存这些信息，只有当无法连上primary或者其不再持有lease，才会重新联系master；
3. client将这些数据信息推送到所有副本，每个chunkserver都会将数据存放在内部的LRU缓存中；
4. 一旦所有副本都确认收到数据，client会向primary发送写请求，包含之前写的数据的信息。primary会给此次的请求分配一个序列号，保证多客户端并发时能得到唯一的操作顺序；
5. primary向所有副本转发写请求，副本以primary的序列号去修改数据；
6. 副本写成功后向primary确认；
7. Primary返回给client。任何副本发生任何错误都会返回给client

Data Flow

为了尽可能避免网络瓶颈和链路延迟，每台机器都将数据转发到尚未接收到它的网络拓扑中的“最近”的机器，可以通过IP地址估算距离。

在没有网络拥塞的情况下，将B字节传输到R副本的理想经过时间是B / T + RL，其中T是网络吞吐量，L是在两台机器之间传输字节的延迟。

Atomic Record Appends

GFS提供了一个名为record append的原子追加操作，客户端仅指定数据，GFS选择偏移量，然后以原子方式将其附加到文件至少一次，并将该偏移量返回给客户端。

记录追加与上面的流程有一个额外的逻辑：客户端将数据推送到文件最后一个块的所有副本之后，将其请求发送给primary。primary检查是否将记录附加到当前块将会导致块的大小超过限制（64 MB）。如果是，会把当前的chunk的剩余空间pad起来，然后告诉其他的副本也这么干，最后告诉client这个chunk满了，写入下个chunk。

如果任何副本上的记录追加失败，则客户端将重试该操作。因此，同一块的副本可能包含不同的数据，但副本必须要与primary对齐，使得下次再追加时，无论哪个副本成为了primary，都能保证所有的操作都从同样的偏移开始追加。

Snapshot

我们采用写时拷贝的方法来完成快照操作：

1. client向master请求snapshot操作；
2. master取消该snapshot涉及到的chunk的所有lease；
3. master将该操作持久化到磁盘；
4. 复制相关chunk的元数据信息到内存中；

当client要写入相关snapshot的chunk C时：

1. client向master请求当前的primary；
2. master注意到该chunk的引用计数大于1，然后推迟回复客户端请求，选择一个新的块句柄C'。然后它要求每个具有C的当前副本的块服务器创建一个名为C'的新块；
3. master授予其中一个副本在新块C'上的lease并回复客户端；

MASTER OPERATION

The master executes all namespace operations.

Namespace Management and Locking

由于很多master操作会花费很多时间，为了避免master阻塞，允许多种master操作同时running，我们使用锁保证序列化。

GFS逻辑上将namespace表示为完整路径名映射到元数据的查找表，并且通过前缀压缩保证了其在内存中的使用，namespace树中的每个节点都有一个读写锁。

每个master操作前都会获取一组锁，如果设计了路径/d1/d2/.../dn/leaf，那么就会获得一组关于/d1, /d1/d2, ..., /d1/d2/…/dn， /d1/d2/.../dn/leaf的锁。

举个例子，当/home/user被快照到/save/user的时候，/home/user/foo的创建是被禁止的。因为快照操作获取/home和/save上的读锁，以及/home/user和/save/user上的写锁。文件创建需要/home和/home/user上的读锁，以及/home/user /foo上的写锁。其中，/home/user的锁产生冲突。

这种方案的一个好处是保障其可以在同一个文件目录并发执行多个文件创建。

Replica Placement

在GFS集群中，通常有数百个chunk server分布在许多rack上。副本的放置策略有两个目的：最大化数据可靠行和可用性，并最大化网络带宽的利用率。我们必须把chunk的副本分发到不同的rack，这样即使整个rack故障了，这些副本仍然可以存活可用。而且这样在读取的时候也可以利用多个rack的聚合带宽。

Creation, Re-replication, Rebalancing

Chunk replicas are created for three reasons: chunk creation, re-replication, and rebalancing.

1. 创建chunk

当chunk server要创建一个chunk时，会考虑以下几种因素：

• 希望chunk server低于平均磁盘空间利用率；
• 限制每个chunk server最近创建的数量，因为创建chunk往往意味着后续会有大量写入；
• 希望在rack上分散chunk的副本；

2. 重复复制

一旦可用副本的数量低于用户指定的目标，主服务器就会重新复制一个数据块。需要重新复制的每个块根据几个因素进行优先级排序，一个是它与复制目标的距离（比如优先复制丢失了更多副本的块），另外就是优先重新复制活动文件的块，而不是属于最近删除的文件的块。最后，为了最大限度地减少故障对运行应用程序的影响，我们提高了阻止客户端进度的任何块的优先级。

3. 重新平衡

master会定期重新平衡副本，通过检查当前的副本分发并移动副本来获得更好的磁盘空间和负载平衡。同样，对于新加入的的chunk server，master会逐渐填满，而不是用大量的写入流量将其打挂。

Garbage Collection

文件会删除后，GFS不会立即GC，而且在常规GC时，也只是做了lazy delete。

Mechanism

当应用程序删除文件时，master会立即记录删除，并将文件重命名为包含删除时间戳的隐藏名称。在master定期扫描文件系统的期间，如果发现其存在已经超过一定间隔（三天），它将删除此类隐藏文件。在此之前，我们可以通过重命名的方式取消删除。从命名空间中删除隐藏文件时，将删除其内存中的元数据。在与master定期交换的HeartBeat消息中，每个chunkserver报告它具有的块的子集，并且主服务器回复主服务器元数据中不再存在的所有块的标识。这样chunkserver就可以自由删除了。

Discussion

这种回收方法有许多优势：

• 不用担心副本删除信息的丢失，因为heartbeat消息携带了相关信息，可以重试；
• GC被放在master的后台活动中，和定期命名空间扫描等活动一起，使得cost均摊，master可以更加迅速回应其它紧急请求；
• GC的延迟提供了防止意外、不可逆删除的保障；

Stale Replica Detection

当chunkserver失败并且此时错过了chunk的写入变化时，chunk副本很可能会变得过时。

每当master给chunk授予lease时，它会增加chunk的版本号并作持久化，然后其他副本也会做对应更新，这些操作会在返回给客户端之前完成。当失败的chunkserver重启后，其版本号还是落后的，它会向master汇报版本号和chunk。

master在其常规垃圾回收中会删除过时的副本，并且当有客户端作请求时，它会认为落后副本不存在。

FAULT TOLERANCE AND DIAGNOSIS

One of our greatest challenges in designing the system is dealing with frequent component failures.

High Availability

我们通过两种简单而有效的策略保持整个系统的高可用性：快速恢复和复制。

Fast Recovery

无论是正常终止还是异常终止，master和chunkserver都被设计为可以在几秒内快速恢复。

Chunk Replication

每个chunk都被复制在不同rack的多个chunkserver上，client可以指定其复制级别（默认为3），master则根据需要克隆现有的副本。

Master Replication

master的操作日志和checkpoint会在多台计算机上进行复制，只有在其日志记录在本地和所有主副本上刷新到磁盘后，才会认为状态变化已提交。其中，一个master进程仍然在复制所有的修改变化和后台活动。

当master失败时可以立即重启，而当master所在机器故障时，则在其他位置使用复制的操作日志启动新的主进程。

新启动的“shadow” masters只提供读服务，因为可能在挂掉的一瞬间，有些日志记录到primary master上，而没有记录到secondary master上。

Data Integrity

每个chunkserver都使用校验和来检测存储数据是否损坏。

一个chunk被分成64kb大小的块，每个块都有32位的校验和被存在内存和持久化到日志。

对于读取的请求，chunkserver会检查数据块的校验和是否正确，如果checksum不正确，chunkserver会报告给client和master，返回错误，让client从其它副本读取数据。而master会clone一个新副本，当新副本clone好后，master会删除掉这个checksum出错的副本。

Diagnostic Tools

GFS服务器生成诊断日志，记录许多重要事件，比如上下游的chunkservers，RPC的请求和回复。

MapReduce

论文《MapReduce: Simplified Data Processing on Large Clusters》

Introduction

MapReduce是谷歌提出的一种编程模型，主要目的是为了处理和生成大数据。通过定义map函数来处理key/value对，生成中间键值对，而reduce函数则是用来归并这些中间键值对。

以这种编程模式来实现的程序会自动在大的集群上并行执行。

Programming Model

运算时键值对输入，产生另外的一系列键值对。Map函数是用户编写，输入键值对，产生键值对，将具有相同的中间key的值传到reduce函数。

reduce函数则是接收上面的中间键值对，将那些value合并起来。

Example

考虑计算文档单词数目的伪代码：

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

map(String key, String value):
    // key: document name
    // value: document contents
    for each word w in value:
    	EmitIntermediate(w, "1");

reduce(String key, Iterator values):
    // key: a word
    // values: a list of counts
    int result = 0;
    for each v in values:
    	result += ParseInt(v);
    Emit(AsString(result));

Types

map和reduce函数都是有类型的：

1
2

map 	(k1, v1) 		--> list(k2, v2)
reduce	(k2, list(v2))	--> list(v2)

More Examples

一些应用了mapReduce的例子：

• Distributed Grep
• Count of URL Access Frequency
• Reverse Web-Link Graph
• Term-Vector per Host
• Inverted Index
• Distributed Sort

Implementation

论文介绍了谷歌内部的使用。

Execution Overview

1. MapReduce库先将input分成M份(16MB-64MB)，然后启动集群上多个机器上的进程；
2. 其中一个进程是master，其它都是worker；
3. 分配了map任务的worker会读取那M份输入的一份，解析键值对，将其传到自定义的Map函数中，产生的中间键值对将会缓存起来；
4. 缓存的内容会被周期性写入到磁盘上，这里磁盘被分成R个区域。写入后的位置信息将会反馈到maser，master再将位置信息传给reduce的worker；
5. reduce的worker将会调用RPC去读取缓存，并根据中间结果的key进行排序，使得相同key的键值对分到一个组；
6. reduce worker将会遍历键值对，然后将key和相关联的values传到自定义的reduce函数里；
7. 当所有任务完成后，master将会从MapReduce中返回；

Master Data Structures

master保存着多种数据结构，比如worker的状态。

另外master还是map任务和reduce任务关于文件位置的沟通渠道。

Fault Tolerance

Worker Failure

master周期性地pingworker，如果没有响应，就认为worker失败了。在失败worker上完成的map任务会设置为idle状态，而还在失败worker上运行的map或者reduce任务都会被设置为idle状态。

完成的map任务此时还需要重新执行，因为中间结果被存在失败机器的磁盘上；而reduce任务不需要重新运行，因为它的输出存储在全局文件系统。另外，所有的reduce任务都应该知晓任务在重新执行，以便读取到正确磁盘上的中间结果。

Master Failure

一般情况下，是将master的数据结构持久化。一旦master任务挂了，就从上次的checkpoint点重新起来。

Semantics in the Presence of Failures

当用户的map和reduce函数是确定性的，那么MapReduce产生的结果也是唯一确定的，这是依赖于Map和Reduce任务的原子性提交实现的。

而对于非确定性的Map或者Reduce操作，单个reduce操作的输出对应于整个程序某次序列化输出的结果。

Locality

由于在计算环境中，网络带宽是很重要的资源，所以谷歌文件系统将输入数据平分，存储到本地磁盘上，而且一般会进行3备份。在运行过程中，MapReduce操作会从本地读取。

Task Granularity

M和R的任务数量应该要比worker机器要多，这样使得worker可以执行多种任务，从而提高负载均衡，也可以在某个worker挂掉的时候快速恢复，因为它已经完成的大量map任务都可以重新分配给其它worker机器上执行。

因为master进行任务分配决策的复杂度是O(M+R)，并且需要在内存中使用O(M*R)大小的空间来保存之前所说的状态。

Backup Tasks

因为某些机器磁盘的故障等原因，MapReduce任务会变得特别慢。这时MapReduce采用的机制就是：

• 在整个计算快要结束时，将一些还在进行的任务进行backup，当backup任务或者源任务其中一个完成时，我们就任务整个计算完成了

Refinements

Partitioning Function

该函数的作用是将中间key结构划分为R部分，默认使用hash(key) mod R，但也可以根据需求自定义

Ordering Guarantees

这个函数主要是对中间结果根据key进行排序

Combiner Funct

该函数是在执行map任务的机器上操作的，将一些数据合并起来，然后写到中间结果去。

Input and Output Types

Mapreduce支持三种文件格式：第一种是逐行读入，key是文件偏移，value是行内容；第二种是key/value读入；第三种是用户自定义reader，可以从文件、数据库或者内存中的数据结构读取。

Side-effects

MapReduce允许用户生成额外的输出，但其原子性应该由应用本身来实现

Skipping Bad Records

对于一些不好修复的bug，或者确定性的错误。worker通过一个信号处理器来捕获错误，然后在执行Map或者Reduce操作前，MapReduce会存储一个全局序列号，一旦发现了用户代码的错误，信号处理器就会发一个内含序列号的UDP包给master，如果master发现了特定记录有了多次的失败，就会指示该记录应该跳过，不再重试。

Local Execution

因为分布式环境调试不方便，MapReduce提供在本机串行化执行MapReduce的接口，方便用户调试。

Status Information

master把内部的状态通过网页的方式展示出来

Counters

MapReduce提供一个计数器来计算各种时间的发生频率。例如这样：

1
2
3
4
5
6
7
8

Counter* uppercase;
uppercase = GetCounter("uppercase");

map(String name, String contents):
	for each word w in contents:
		if (IsCapitalized(w)):
			uppercase->Increment();
		EmitIntermediate(w, "1");

计数器的值会周期性传达给master。当MapReduce操作完成时，count值会返回给用户程序，需要注意的是，重复执行的任务的count只会统计一次。

列表优先于数组

不同点

1. 数组和泛型的不同首先体现在数组是covariant的，所以如果Sub是Super的一个子类型，那么数组类型Sub[]也是数组类型Super[]的子类型。相反，泛型列表对此则有限制。这意味着：

1
2

Object[] objectArray = new Long[1];
objectArray[0] = "I don't fit in"; //在运行时会报错

但如果使用列表：

1
2

List<Object> ol = new ArrayList<Long>(); // Incompatible types
ol.add("I don't fit in");

2. 数组是具化的，数组只有在运行时才能直到并检查元素类型，而泛型是通过擦除来实现的，这意味着泛型只在编译时进行类型约束的检查，而运行时是忽略元素类型的。因此无法混合使用数组和泛型，以下的操作都是不合法的：

1

new List<E>[], new List<String>[], new E[]

优先使用列表

当你强转成数组类型时，若得到一个泛型数组创建错误或者未检查强转警告，最好的解决办法是，总是优先采用集合类型List<E>，而不是数组类型E[]。

考虑这样一个类，构造器接受一个集合：

1
2
3
4
5
6
7
8
9
10

public class Chooser {
    private final Object[] choiceArray;
    public Chooser(Collection choices) {
        choiceArray = choices.toArray();
    } 
    public Object choose() {
        Random rnd = ThreadLocalRandom.current();
        return choiceArray[rnd.nextInt(choiceArray.length)];
    }
}

那么在使用时，我们每次都要在调用choose方法之后，将Object类型转换为需要的类型，有可能强转失败，如果我们使用泛型：

1
2
3
4
5
6

public class Chooser<T> {
    private final T[] choiceArray;
    public Chooser(Collection<T> choices) {
        choiceArray = choices.toArray();
    }// choose method unchanged
}

这样会编译报错，除非我们强制换位Object数组：

1

choiceArray = (T[]) choices.toArray();

这样只会产生一个警告，因为编译器无法保证运行时强转的安全性。当然，我们可以消除warning，但最佳的做法还是使用泛型列表：

1
2
3
4
5
6
7
8
9
10

public class Chooser<T> {
    private final List<T> choiceList;
    public Chooser(Collection<T> choices) { 
        choiceList = new ArrayList<>(choices);
    }
    public T choose() {
        Random rnd = ThreadLocalRandom.current();
        return choiceList.get(rnd.nextInt(choiceList.size()));
    } 
}

深度学习中的正则化<一>

概述

深度学习的一个核心问题就是提高模型的泛化性，即不仅仅要在训练数据上表现好，还能在新输入上有更好的泛化，这些策略就是正则化。

首先来理解偏差和方差的含义：

• 方差度量了同样大小的训练集的变动所导致的学习性能的变化，即刻画了数据扰动所造成的影响。
• 偏差度量了学习算法的期望预测与真实结果的偏离程度，即刻画了学习算法本身的拟合能力

在一些过拟合的场景下，正则化会以偏差的增加来换取方差的减少。

参数范数惩罚

许多正则化方法会对目标函数J增加一个参数范数惩罚\(\Omega(\theta)\)，限制模型的学习能力，目标函数变为： \[ J'(\theta, X, y) = J(\theta, X, y) + \alpha \Omega(\theta) \] \(\alpha\)越大，对应的正则化惩罚就越大。当我们的训练算法最小化正则化后的目标函数J时，它会降低原始目标J关于 训练数据的误差并同时减小在某些衡量标准下参数θ(或参数子集)的规模。

一般情况下，在神经网络中我们只对权重做惩罚而不对偏置做惩罚。精确拟合偏置所需要的数据比拟合权重少，我们不对其进行正则化也不会导致太大的方差，而且正则化偏置参数可能会导致明显的欠拟合。

L2参数正则化

\(L^2\)参数范数惩罚是最简单最常见的正则化方式，这个策略添加了一个正则项（权值向量w中各个元素的平方和），使得权重更加接近原点。这个目标函数就变成了： \[ J'(w, X, y)=\frac{\alpha}{2}w^Tw+J(w, X, y) \] 与之对应的梯度为： \[ \nabla_wJ'(w, X, y) = \alpha w+\nabla_wJ(w, X, y) \] 那么更新权重的方式也会发生变化： \[ w = w-\epsilon(\alpha w+\nabla_wJ(w, X, y)) = (1-\epsilon \alpha)w-\epsilon \nabla_wJ(w, X, y) \] 我们可以看到每步更新执行时都会先收缩权重向量。

我们进一步分析整个训练过程中会发生什么，令w为未正则化的目标函数取得最小训练误差时的权重向量，那么近似的误差函数就是： \[ J'(\theta) = J(w^*) + \frac{1}{2}(w-w^*)^TH(w-w^*) \] 其中H是J在w处计算的Hessian矩阵，当\(J'\)取得最小时，其梯度为： \[ \nabla_wJ'(w) = H(w-w^*) = 0 \] 然后我们添加上权重衰减的梯度，其中w是此时的最优点： \[ \alpha w+H(w-w^*) = 0 \]

\[ w = (H+\alpha I)^{-1}Hw^* \]

可以看到当\(\alpha\)趋向于0的时候，正则化的解w会趋向\(w^*\)。那么当\(\alpha\)增加时，在显著减小目标函数方向上的参数会保留得相对完好，而在无助于目标函数减小的方向(对应 Hessian 矩阵较小的特征值)上改变参数不会显著增加梯度，这种不重要方向对应的分量会在训练过程中因正则化而衰减掉。

简单来说，L2正则化能让学习算法对与具有较高方差的输入x更加敏感，使得与输出目标的协方差较小的特征的权重收缩，

L1参数正则化

L1正则化则是添加一个另外的正则化项（权值向量w中各个元素的绝对值之和）： \[ J'(w, X, y)=\alpha||w||_1+J(w, X, y) \] 对应的梯度为： \[ \nabla_wJ'(w, X, y) = \alpha sign(w)+\nabla_wJ(w, X, y) \] 其中sign(w)只是简单地取w各个元素的正负号，其中若w>0，则sign(w)=1；若w<0，则sign(w)=−1；若w=0，则sign(w)=0。

相比L2正则化，L1正则化会产生更加稀疏的解，这里的稀疏指的是最优值中的一些参数为0。由L1正则化导出的稀疏性质被广泛用于特征选择机制，从可用的特征子集中选择出有意义的特征。

在编译过程中出现warning的时候，我们应该根据编译器的指示来进行修正，让警告消失。

对于不能消除的警告，如果能够引起这个警告的代码是类型安全的话，那么就可以使用注解@SuppressWarnings("unchecked")来禁止这个警告。该注解可以在任意声明上使用，从单独的局部变量到整个类都可以，但我们应该在尽可能小的作用域上使用该注解。永远不要在整个类上使用SuppressWarnings注解。

对于以下的方法，编译的时候会生成warning：

1
2
3
4
5
6
7
8

public <T> T[] toArray(T[] a) { 
    if (a.length < size)
        return (T[]) Arrays.copyOf(elements, size, a.getClass()); 
    System.arraycopy(elements, 0, a, 0, size);
    if (a.length > size)
        a[size] = null; 
    return a;
}

1
2
3
4

ArrayList.java:305: warning: [unchecked] unchecked cast return (T[]) Arrays.copyOf(elements, size, a.getClass());
                                                                     ^ 
required: T[]
found: Object[]

对于这种情况，我们不能将注解放在返回语句上，因为其不是一个声明。因此我们可以声明一个局部变量来保存返回值，并注解这个局部变量的声明，并且需要在注释里记录禁止warning的原因：

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

// Adding local variable to reduce scope of @SuppressWarnings
public <T> T[] toArray(T[] a) {
    if (a.length < size) {
        // This cast is correct because the array we're creating
        // is of the same type as the one passed in, which is T[].
        @SuppressWarnings("unchecked") 
        T[] result = (T[]) Arrays.copyOf(elements, size, a.getClass());
        return result;
    }
    System.arraycopy(elements, 0, a, 0, size); 
    if (a.length > size)
        a[size] = null; 
    return a;
}

反向传播和其他的微分算法

概述

在训练过程中，前向传播可以向前直到它产生一个标量代价函数\(J(\theta)\)，而反向传播会计算代价函数关于参数的梯度，即\(\nabla_\theta J(\theta)\)。

计算图

我们将计算形式转化为图形，形成计算图。那么我们每一个结点代表一个变量，操作则是一个或者多个变量的简单函数，我们定义一个操作仅仅返回单个输出变量。

如果变量 y 是变量 x 通过一个操作计算得到的,那么我们画一条从 x 到 y 的有向边。

微积分中的链式法则

微积分中的链式法则用于计算符合函数的导数。

假设x是实数，f和g是从实数映射到实数的函数。假设y=g(x)并且z=f(g(x))=f(y)。那么就有： \[ \frac{dz}{dx} = \frac{dz}{dy} \frac{dy}{dx} \] 如果向向量的情况扩展： \[ \frac{\alpha z}{\alpha x_i} = \sum_j \frac{\alpha z}{\alpha y_i} \frac{\alpha y_i}{\alpha x} \\ \nabla_x{^z} = (\frac {\alpha y} {\alpha x})^T \nabla_y{^z} \] 这个$ {x}$是g的Jacobian矩阵。

当然，也可以将反向传播应用到任意维度的张量，在我们运行反向传播之前,将每个张量变平为一个向量，计算一个向量值梯度,然后将该梯度重新构造成一个张量。

递归地使用链式法则来实现反向传播

使用链式法则，我们可以直接写出某个标量关于计算图中任何产生该标量的梯度的代数表达式，但一般计算机在计算时会引入一些额外的考虑。 \[ \frac{\alpha u^{(n)} }{\alpha x^{(j)} } = \sum_{i:j \in Pa(u^{(i)})} \frac{\alpha u^{(n)} }{\alpha u^{(i)} } \frac{\alpha u^{(i)} }{\alpha u^{(j)} } \] 考虑这种计算图，在计算梯度时导致子表达式重复计算：

为了计算z对w的梯度： \[ \frac{\alpha z}{\alpha w} \\ =\frac{\alpha z}{\alpha y} \frac{\alpha y}{\alpha x} \frac{\alpha x}{\alpha w} \\ =f'(y)f'(x)f'(w) .............1\\ =f'(f(fw)) f'(f(w)) f'(w) .............2 \] 对于1式，我们采用的实现方式是仅仅计算f(w)一次，并存储起来，这种方式减少了运行时间；

而对于2式，每次只在需要时重新计算f(w)，在存储受限时它是有用的。

符号到符号的导数

代数表达式和计算图都对符号或不具有特定值的变量进行操作，这些代数或者基于图的表达式就是符号表示。一些反向传播的方法采用计算图和一组用于图的输入的数值，然后返回在这些输入值处梯度的一组数值。我们将这种方法称为 符号到数值的微分。这是Torch和Caffe使用的方法；

另一种方法则是采用计算图以及添加额外的结点到计算图中，其提供了我们需要导数的符号描述，这是Theano和TensorFlow采用的方法。

一般化的反向传播

反向传播算法比较容易理解，其实就是为了计算某个标量z关于图中它的一个祖先x的梯度，我们首先观察到它关于z的梯度由1给出，然后，我们对图中z的每个父节点的梯度进行计算，通过现有的梯度乘以产生z的操作的Jacobian。如果从z触发经过多条路径到达父结点，我们应该对不同路径上的梯度进行求和。

求解这种表达式\(\frac{\alpha u^{(i)} }{\alpha u^{(j)} }\)的时候，相同的计算可能会重复多次，为了避免重复计算，我们利用存储的中间结果\(\frac{\alpha u^{(n)} }{\alpha u^{(i)} }\)来进行补充计算。

Java通配符的使用

基本介绍

泛型是一种表示类或者方法行为对于未知类型的类型约束的方法，通配符在类型系统中有重要的作用，它们为一个泛型类所指定的类型集合提供了一个有用的类型范围。

协变

数组是协变的，因为Integer是Number的子类型，数组类型Integer[]是Number[]的子类型，因此在任何需要 Number[]值的地方都可以提供一个Integer[]值。泛型不是协变的，List<Integer>不是List<Number>的子类型。

因此这种代码无法通过编译：

1

ArrayList<Fruit> flist = new ArrayList<Apple>();

使用通配符

我们知道上面那种语句是无法通过编译，通过它们之间存在父子类型的关系，如果我们需要建立这种向上转型的关系，就需要使用通配符了。

上边界限定通配符

利用 <? extends Fruit> 形式的通配符，可以实现泛型的向上转型：

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

public class GenericsAndCovariance {
    public static void main(String[] args) {
        // Wildcards allow covariance:
        List<? extends Fruit> flist = new ArrayList<Apple>();
        // Compile Error: can’t add any type of object:
        // flist.add(new Apple());
        // flist.add(new Fruit());
        // flist.add(new Object());
        flist.add(null); // Legal but uninteresting
        // We know that it returns at least Fruit:
        Fruit f = flist.get(0);
    }
}

在这种情况下，我们不知道这个 List 到底持有什么类型，因此也不可能安全的添加一个对象，唯一可以添加的是null。编译器会为这个问号类型起一个临时的代号，比如CAP#1。但是调用某个返回Fruit的方法就是安全的，因此不管实际类型是什么，肯定能够转型为Fruit。

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

public class CompilerIntelligence {
    public static void main(String[] args) {
        List<? extends Fruit> flist =
        Arrays.asList(new Apple());
        Apple a = (Apple)flist.get(0); // No warning
        flist.contains(new Apple()); // Argument is ‘Object’
        flist.indexOf(new Apple()); // Argument is ‘Object’
        
        //flist.add(new Apple());   无法编译

    }
}

下边界限定通配符

这是通配符的另一个方向，超类型的通配符：? super T，T是类型参数的下界。在这种情况下，写入是有效的，因为对象都可以被向上转型成合法的类型：

1
2
3
4
5
6
7

public class SuperTypeWildcards {
    static void writeTo(List<? super Apple> apples) {
        apples.add(new Apple());
        apples.add(new Jonathan());
        // apples.add(new Fruit()); // Error
    }
}

无边界通配符

还有一种通配符是无边界通配符，它的使用形式是一个单独的问号：List<?>，也就是没有任何限定。因为不知道是具体哪种类型，我们也无法向其中添加对象。

类型参数与无边界通配符

List<T>是泛型方法，List<?>是限制通配符。一般来说，List<T>一般有两种用：定义一个通用的泛型方法和限制方法的参数之间或参数和返回结果之间的关系。

比如这种情况就可以限制返回结果的类型与参数类型一致：

1

List<T> getList<T param1,T param2>

而List<?>一般就是在泛型起一个限制作用。

当对已经存在的泛型，我们不想给她一个具体的类型做为类型参数，我们可以给其一个不确定的类型作为参数。这个就是通配符的意义。

Reference

https://segmentfault.com/a/1190000005337789

https://www.zhihu.com/question/31429113