Zyzzyva Paper 链接：http://www.cs.cornell.edu/lorenzo/papers/kotla07Zyzzyva.pdf Journal Version (Extended): https://www.cs.cornell.edu/lorenzo/papers/a7-kotla.pdf 回顾：PBFT 讲解链接：https://gyrojeff.top/index.php/archives/dive-into-pbft/ 动机 PBFT 的 $O(n^2)$ 开销太大，而且观察到大多数时候并会经历 Primary Fault 甚至大多数时候不会有 Fault。Zyzzyva 旨在提高没有 Fault 或者没有 Primary Fault 的情况下的协议效率。 Zyzzyva 流程 一些记号的说明 Checkpoint, CC, Speculative History 见上图 Order-Req 以及 Spec-Response阶段 $d = H(m)$，即消息 $m$ 的 Digest $h_n = H(h_{n-1}, d)$，描述截止到 $n$ 的历史记录，即 $$ h_n = H(H(H(\cdots (H(d_1), d_2)\cdots), d_{n-2}), d_{n-1}) $$ 注意到光靠 $h_n$ 就能判断历史记录了。正常的 Client 可以靠这个鉴别是否 Diverge。 Normal Case Operation 当有 Fault 存在 View Change View Change 的大体过程和 PBFT 相同： PBFT: Last Stable Checkpoint + Preprepare Messages Zyzzyva: Last Stable Checkpoint / Committed Certificate + Speculative History 区别在于对待 Speculative History 的处理上。 Zyzzyva 这里要分两种情况处理： 如果没有 Speculative History，那么就是普通的 PBFT View Change，没什么好讨论的 如果有 Speculative History，我们需要判断这个 History Diverge 了还是是属于 Fast Path 的正常 History。判断方法如下：如果在 View Change 的 $2f+1$ 个 Replica 当中，有 $\geq f+1$ 个 Replica 有 CC 之后的这样一条匹配消息，那么就认为这个消息是真实消息，即属于 Fast Path。我们会在之后的章节给予证明。 一些 Intuition 对于 Zyzzyva，简要而言可以理解如下 如果没有 Fault，那就非常快，Client 知道搞定就行了。这样的记录就是 Speculative 的 如果存在 Fault，那也要至少要求 $2f+1$ 个 Reply，这个时候 Client 会给所有 Replica Multicast Committed Certificate。注意：有了 Committed Certificate，之前的所有 Speculative 记录就自动转正了 Zyzzyva 的 View Change 和 PBFT 相比也有少许不同。最大的特点就是：如果 Suspect Primary Faulty，不会暂停消息的处理！ Replica 会继续处理消息，但是同时广播 I-Hate-The-Primary。只有当 I-Hate-The-Primary 的数量达到 $f+1$ 的时候，才会进入真正的 View Change。相比之下，PBFT 只要 trigger timeout 就立刻罢工，这就是 PBFT 的 In-Dark 问题。 Safety 是如何保证的？ View 内部的 Safety？ 注意到 Zyzzyva 没有 Pre-Prepare - Prepare - Commit 三个节点，没有 View 内的 Consensus，完全靠的是 CC 和 Speculative History。所以我们只需要分析这两个部分。 Committed Certificate 的 Safety Committed Certificate 的 $2f+1$ 个 Replica 和 View Change 时的 $2f+1$ 个 Replica 构成了 $f+1$ 个 Quorum，保证了 View Change 的时候至少有一个 non-faulty Replica。这个和 PBFT 的过程相同，原理也相同。 Speculative History 的 Safety 以及 View Change 时的 $f+1$ 的 Design Choice 我们要论证的大问题是，有没有可能在前一个 View Commit 了一个消息，客户端接受了，但是在新的 View 中不见了？ 首先我们可以证明：如果一个 Commit 属于 Fast Path ($3f+1$)，那么在 View Change 时，我们一定能在那个 $2f+1$ 的 Quorum 内找到 $f+1$ 个 Matching。 证明：反证法。如果一个 Commit 属于 Fast Path，同时找不到 $f+1$ 个 Matching，那么和至多有 $f$ 个节点是 Fault 矛盾。 接下来我们想要说明：如果一个 Commit 能够在 $2f+1$ 的 Quorum 中找到 $f+1$ Matching，那么他不可能属于 Slow Path（客户端成功执行）. 证明：反证法。如果一个 Commit 属于 Slow Path 且客户端成功执行，那么他必定存在于某个 CC 当中，与 Speculative History 矛盾。 给出了上面两种情形，我们接下来说明：如果一个 Commit 能够在 $2f+1$ 的 Quorum 中找到 $f+1$ Matching，那么把他包含进 New View 中时不会 Violate Safety Condition。 证明：根据前面几个结论，我们可以得到这个 Commit 无非只有两种情形： Commit 属于 Fast Track，成功执行：不会违反 Safety Condition Commit 属于 Slow Track，Commit Certificate 只有部分（或者没有）传回，而且根据前面的论证，$2f+1$ 的 View Change 节点内不可能有 CC。在这种情况下 View Change 会促成 Commit，即在 New View 继续处理这个消息。如果客户端请求失败了进行重传，那么 Cache 会继续这个过程。 Commit 尚未执行完毕，即 Client 收到 $< 2f+1$ 个 Speculative Response：回顾本章开头的大问题，全然问题无。 如果 Diverge 了怎么办？ 注意到 CC 前的内容不可能 Diverge，只有可能 Speculative History 有 Diverge。文章中没有讲解，但是如果有 Diverge 就听从 New View 安排，不对的东西直接 Rollback (Discard)，然后处理新的 Order-Request. Two-Phase Protocol 的 View Change Liveness 问题 问题构造 与 PBFT 的对比 为什么 PBFT 没有这个问题？注意到 PBFT 的 View Change 原则是如果 Timeout 就自动发起 View Change，不会卡住。 解决方案——I Hate The Primary 解决方案就是 Intuition 章节提到的 I-Hate-The-Primary 消息。这里的主要思想是：只有我知道了足够多的人都怀疑 Primary Fault 的情况下，我才会进入 View Change，以防卡住的问题。这里我们可以证明为什么有 $f+1$ 个 I-Hate-The-Primary 就不会再有 liveness 问题。 注意到保证 liveness 的条件是没有 Network Partition。这就意味着 $f+1$ 个 I-Hate-The-Primary 一定可以被这 $f+1$ 个节点互相收到，也就是说会有 $f+1$ 个节点进入 View Change 节点并广播 View Change 消息。因为 Zyzzyva 和 PBFT 相同，在收到 $f+1$ 个其他节点的 View Change 之后，Replica 会立刻进入 View Change。而因为这里没有 Network Partition，所以上述操作必然可以完成，也就是说必然会有 $\geq 2f+1$ 的节点进入 View Change，完成整个操作。 有没有可能进行 View Change Attack？ 参考最后一章 Design Choice 的 $f+1$ 设计问题。 Design Choice 问题汇总与 Edge Case 分析 Q: 为什么 Client 需要至少 $2f+1$ Matching？ Q: 为什么 View Change 至少需要 $2f+1$ Matching？ A: 这两个问题 Commited Certificate 的 Safety 章节已证明。 Q: 为什么 View Change 时 New Primary 计算，需要 $f+1$ 个 Ordered Request 存在才能将该记录加入 New View，而不像 PBFT 只需要 $1$ 个？ A: Speculative History 的 Safety 章节已证明。 Q: 为什么 I-Hate-The-Primary 需要 $f+1$ 个？ A: 我们在前面的章节已经证明了 $f+1$ 是足够的。这里我们再论证为什么 $f$ 是不行的。原因非常简单，如果需要 $f$ 个就可以进入 View Change 状态的话，假设有 $f$ 个 faulty Replica，全部不停地发 I-Hate-The-Primary，就会不断 trigger view change，liveness 便不能再保证了。
PBFT - Practical Byzantine Fault Tolerance BFT PBFT 的重要概念 PBFT 的大致流程 Normal Case Operation 即 Primary 不出问题的情况下 Checkpoint Protocol View Change Protocol Fault 的分类 为什么达成 Prepared 状态需要 $2f+1$ 个 Matching Prepared 保证了什么？ 反例构造 证明 Commit Phase 的必要性 Commit Phase 能够保证什么？ 反例构造 理解 为什么达成 Committed 状态需要 $2f+1$ 个 Prepared 估算 反例构造 为什么 New Primary 需要 $2f$ 个 View Change 为什么 Reply 需要 $f+1$ 个 Matching Checkpoint (Garbage Collection) 的必要性 Checkpoint 为什么在数字签名模式下只需要 $f+1$？ View Change 和 Liveness 之间的关系 Primary 作恶带来的 In-Dark 问题 Network Recovery 的流程 Misc PBFT - Practical Byzantine Fault Tolerance 论文链接：https://pmg.csail.mit.edu/papers/osdi99.pdf BFT BFT (Byzantine Fault Tolerant) 拜占庭容错，指的是在一个分布式系统当中，在有节点可能出现任意行为（包括但不限于崩溃、发送错误数据、出现恶意行为等）的情况下，仍可以正常运行即达成共识。 Wikipedia Link. PBFT 的重要概念 PBFT 可以保证在一个大小为 $3f+1$ 的分布式网络下，容忍至多 $f$ 个节点的拜占庭错误。 Primary (Leader): PBFT 是一个 leader-based 的协议，即在任意时刻，都有一个 leader 主导协议的走向。 视图 View: 在 Primary 不发生改变的一段时间我们称之为 View。注意到：View 的编号是单调递增的。给定一个视图编号 $v$，我们就可以唯一确定这个视图的 Primary 编号 $p = v \bmod |\mathcal R|$，其中 $\mathcal R$ 是所有节点的集合，即所有 Replica 的集合。 Replica: 可以理解为服务器节点。 目标: 达成 Consensus。即在每一个 Replica 上，所有的 transaction 内容和顺序都保证一致。 View Change: 视图改变。正因为协议由一个 Leader 主导，那在 leader 出现 malicious behaviour 的时候，协议可以保证触发 View Change，即更换 leader，来保证 liveness。具体内容后文会详细说明。 PBFT 的大致流程 Normal Case Operation 即 Primary 不出问题的情况下 [REQUEST] 客户端向 Primary 发送 $\langle Request, o, t, c \rangle _{\sigma_c}$ 请求 $o$: Operation $c$: Client $t$: Timestamp - 这是用来保证执行的 exactly-once semantics [PREPREPARE] Primary 将请求 Multicast 给所有 Replica: $\langle \langle Preprepare, v, n, d \rangle _{\sigma_p}, m \rangle$ $v$: view $n$: Primary 给这个请求分配的 Sequence Number 【关于 Sequence Number: 一个正常的 Replica 只会按顺序 (Sequence Number) 处理消息。即若其收到了 127 号消息但始终没有收到 125、126 号消息，127 号消息便一直不会处理。】 $d$: $d = D(m)$ 消息 $m$ 的 digest (摘要) [PREPARE] 每个 Replica $i$ 收到请求之后，如果选择接受请求（原文有更详细的描述），就会向所有 Replica 广播 Prepare: $\langle Prepare, v, n, d, i \rangle _ {\sigma_i}$ [COMMIT] 接下来，如果每个 Replica $i$ 收到了其他 Replica (包括自己在内) 一共 $2f+1$ 个 Prepare 请求，这个时候认为其进入了 Prepared 状态，并广播 Commit 消息: $\langle Commit, v, n, d, i \rangle _ {\sigma_i}$ Checkpoint Protocol 见原文，不赘述。 View Change Protocol 在怀疑 Primary 作恶的情况下，Replica 会广播 View Change 消息: $\langle ViewChange, v+1, n, \mathcal C, \mathcal P, i \rangle _{\sigma_i}$ $\mathcal C$ 是用来证明上一个 Checkpoint 的有效性的 $\mathcal P$ : 对于所有编号在 $n$ 之前，上一个 Checkpoint 之后的消息 $m$，$\mathcal P_m \in \mathcal P$，其中 $\mathcal P_m$ 包含了 $m$ 的 Preprepare 消息和 $2f+1$ Matching。 注意到之所以包含了这么多消息，主要就是为了防止消息伪造，全部演算一遍数字签名，出现纰漏就直接忽略，拒不执行。 如果一个 Replica 收到了 $f+1$ 个 View Change 请求，那他也会广播 View Change 请求，加速 View Change 进程。 New Primary 收到 $2f$ 个 View Change 请求之后（不包括自己），广播 $\langle NewView, v+1, \mathcal V, \mathcal O \rangle _{\sigma_i}$，具体的计算细节原文写的很详细了。 Fault 的分类 见：https://dinhtta.github.io/pbft/ Network Failure Model Byzantine fault tolerant protocols tolerate at most $f$ Byzantine failures. In a distributed system, however, there are two types of failures: node and network. It is important to distinguish them, especially since they determine guarantees about the protocol’s safety and liveness. Node failure means a node (or server, peer, entity, etc.) behaves arbitrarily. This captures the strongest adversary model. A network failure refers to network partitions which can last for an unbounded amount of time. It can be quantified as the number of nodes being isolated from the rest of the network, although they can still communicate with each other. Given this distinction, what are being counted toward $f$? In PBFT $f$ refers to node failures. The protocol guarantees safety upto $f$ node failures. Safety is independent of network failure. That is, even if the network is severely partition, namely more than $f$ nodes are isolated (but across all partitions there are still fewer than $f$ node failures), the protocol is still safe. However, liveness is only guaranteed with fewer than $f$ total failures, i.e. counting both node and network failures. This means at least $2f+1$ nodes must be reachable. Note that safety being independent of network failures is a strong guarantee, and it is common in most variants of PBFT. Not until Liu et al. recent work, namely XFT, is it relaxed in a way that separates out node and network failures. 为什么达成 Prepared 状态需要 $2f+1$ 个 Matching Prepared 保证了什么？ 要回答上面的大问题首先要理解我们想要 Preprepare + Prepare Phase 保证什么。论文 Section 4.2 已经回答了这个问题，即 $$ prepared(m, v, n, i) \Rightarrow \lnot prepared(m', v, n, j), \forall i,j,m,m', s.t. D(m') \neq D(m) $$ 即我们要保证在同一个 view 内，每一个 sequence number 只对应唯一一个 prepared message。 反例构造 首先我们可以构造一个如果只有 $2f$ 个 matching 就能打破上述原则的反例。 证明 接下来我们尝试用 Quorum 的思想来证明。使用反证法：如果每个节点都有 $2f+1$ 个 matching，但是最后仍然出现了两个 Replica $a \neq b$，使得 $$ prepared(m, v, n, a) \land prepared(m', v, n, b) \land D(m) \neq D(m') $$ 根据题设，有 $2f+1$ 个节点向 $a$ 发送了 $\langle Prepare, v, n, d, i \rangle _{\sigma_i}$，有 $2f+1$ 个节点向 $b$ 发送了 $\langle Prepare, v, n, d', i \rangle _{\sigma_i}$。根据容斥原理，至少有 $$ 2 \times (2f + 1) - (3f+1) = f + 1 $$ 个节点向 $a, b$ 分别发送了不同的消息。这样的行为毫无疑问是 malicious 的，所以至少存在 $f+1$ 个恶意节点，与至多有 $f$ 个恶意节点的协议假设矛盾。证毕。 Commit Phase 的必要性 Commit Phase 能够保证什么？ 首先，Commit Phase 是 View Change 的副产物。后面的章节会详细解释 View Change，在这个阶段我们只需要知道 View Change 用来解决 Primary 作恶时的 Liveness 问题。而 Commit Phase 就是用来解决 View Change 过程中 Safety 的问题，即在 View 切换的前后： 一个 Sequence Number 对应的 Message 必定在所有正常节点之间达成 Consensus 不会出现一部分节点 Commit 了，但是另一部分节点完全不知道这件事，并继续执行下一个 Commit 或者重复使用 Sequence Number 的情况。 更加明确一点就是原文中的表达： $$ Committed(n, m, v, i) \Rightarrow \lnot Committed(n, m', v', j), \forall D(m) \neq D(m'), v' > v $$ 反例构造 现在我们假设 Commit Phase 不存在，即在节点达成 Prepared 的时候就直接给 Client 发送 Reply。考虑下图的情况： 可以发现反例非常容易构造，我们甚至构造出了 $f$ 个节点使用了 $n+1$ 的 Sequence Number，但是剩余节点以及 New Primary 没有的情况。 理解 从上面这个例子已经可以看出，Commit Phase 主要就是需要保障一个 Sequence Number 在跨 View 的时候不能被 Malicious Primary 或者 Network Partition 影响，使得被重复使用，破坏 Safety。 增加一个 Commit Phase 的主要功能，就是 只有在知道有一定数量的其他 Replica 已经处于 Prepared 状态之后再进行 Commit，这个数量一定要保证能够在 View Change 的时候至少有一个节点能够证明这个请求已经 Prepared。 因为注意到上图：在节点 Commit 的时候，很多节点没有达到 Prepared 状态，无法在 Network Partition 的时候提供证据向新的 Primary 证明这个请求已经被 Commit。综上所述，这就是 Commit Phase 存在的意义。 为什么达成 Committed 状态需要 $2f+1$ 个 Prepared 估算 上一节提到，在 Commit 前，我们至少要保证有足够多的 Replica 已经处于 Prepared 阶段，使得在 Network Partition 出现的时候仍然能够向 Primary 提供信息，告诉 Primary 一个请求已经被 Commit。那这个数量到底应该是多少呢？通过简单的估算其实就可以得到。 已知 New Primary 需要 $2f$ 个除了自己以外的 View Change 请求。最悲观地考虑，出现了最大限度的 Network Partition，即有 $f$ 个节点无法通信。在这个极限情况下的极限情况是这 $f$ 个 Replica 都处于 Prepared 状态却无法与 Primary 通信。而其余 $2f+1$ 个节点中又有 $f$ 个 malicious node，可以假装不知道自己 Prepared 了。 所以，在那 $2f+1$ 个节点中至少需要 $f+1$ 个节点处于 Prepared 状态才能保证 New Primary 收到 Commit 记录，再算上 Network Partition 的 $f$ 个 Replica，一共得有 $2f+1$ 个节点处于 Prepared 状态才能保证信息能够在 Network Partition 和 View Change 的情况下送达 New Primary。 反例构造 上述文字选取的是极端情况，有一条不成立即为反例。所以 $2f$ 个 Prepared 却仍然失败的反例和没有 Commit Phase 一样非常好构造，这里不再赘述。 为什么 New Primary 需要 $2f$ 个 View Change 理解了 Commit Phase 的 $2f+1$ 便不难发现，这里 $2f$ 这个数目的选取是和 Committed 数目的选取是相关的。 两个 $2f+1$ (实际上 View Change 算上 New Primary 也是 $2f+1$) 在总共 $3f+1$ 的池子里，Intersection (Quorum) 的大小总是不小于 $f+1$ 个 Replica 的。这样就保证了总有一个 Non-faulty Replica 位于最终的 Quorum 当中（faulty replica 可以隐瞒不报，装作不知道，所以一定需要 non-faulty replica），即既是 Prepared，又没有被 Network Partition 和 Malicious Replica 影响到。 为什么 Reply 需要 $f+1$ 个 Matching 这个就非常 Intuitive 了，因为这样必定能有一个 Non-faulty Replica 回复。 Checkpoint (Garbage Collection) 的必要性 注意到 View Change 的时候需要附上所有的记录来证明自己是正常节点，这所带来的开销随着时间的推移显然是不可接受的，所以我们需要想办法回收一部分 log。 Checkpoint 为什么在数字签名模式下只需要 $f+1$？ 因为 $f+1$ 保证了至少有一个 Non-faulty Node 进行了 Checkpoint，也就是在没有 Network Partition 的情况下必定可以从网络中访问到这个 Checkpoint。 但是这里其实有一个问题：如果 Network Partition 了呢？注意到 PBFT 只在没有 Network Fault 的情况下 Guarantee Liveness，所以在那种情况下，需要请求 Checkpoint 的节点就 In-dark 了。如果这样的情况足够多，Liveness 也就无法保证了。 View Change 和 Liveness 之间的关系 View Change 主要是为了解决没有 Network Fault 的情况下的 Liveness 问题。当一个 Replica 的请求迟迟无法完成的时候就会 Trigger View Change。因为请求无法完成无非几种情况： Primary 作恶，比方说只发给一部分 Replica Preprepare 消息 Network Partition View Change 在第二种情况下其实并不能解决问题，但是可以解决第一种情况的问题。这就是 View Change 的 Intuition。 Primary 作恶带来的 In-Dark 问题 注意到 Primary 可以故意不给某些节点发请求，即 Primary 作恶。在这种情况下，这些节点既不会触发 View Change，也不会做任何事情，也就是字面意义上的 In-Dark。 由于前面的论证，PBFT 已经保证了 Safety，同时在没有 Network fault 的情况下也保证了 Liveness，所以这样的 In-Dark 并不会有什么特别大的影响。 只有当 In-Dark Replica 的数量多到使得 Consensus 无法达成了，才会 trigger View Change，使得协议能够推进下去。 Network Recovery 的流程 首先向网络请求 Checkpoint 如果能顺利 Catch Up，那就无缝衔接 反之，迎来的结果必然是请求积压无法处理，timeout 之后便会 Request View Change，然后在 View Change 的过程中完成 Catch Up Misc Q: 如果 Primary 无中生有虚构信息或者篡改 Client 信息怎么办？ A: 注意到 $\langle Request, o, t, c \rangle _{\sigma_c}$ 的角标 $\sigma_c$，客户端签名保证了 Primary 不能篡改消息也不能伪造消息。 Q: 如果 Client 不知道当前的 Primary 怎么办？ A: 如果客户端一段时间内没有收到 Reply，触发 Timeout，重新 Multicast 请求。 Q: 如果因为 Network Partition 正常节点没有把回复送达到 Client，Client 认为请求失败，重传怎么办？这不就等于会执行两次了吗？ A: 注意到 $\langle Request, o, t, c \rangle _{\sigma_c}$ 中的 timestamp 可以解决这个问题 其他小的点： View Change 后面 New View 这里应该也是有 Time out 机制的，否则 New Primary 迟迟不发 New View 的话 Liveness 就寄了 Client 发请求之后应该也有 Timeout 机制然后 Multicast，用来规避：（1）Primary 作恶，故意不发 Preprocess（2）发送的 Replica 不是 Primary
注：本文为《机器学习》（周志华）第一章的作业笔记。 1.1 表 1.1 的编号为 1, 4 的两个样例： 色泽 根蒂 敲声 好瓜 青绿 蜷缩 浊响 是 乌黑 稍蜷 沉闷 否 因为只有两个样本，我们只要能够保证： $$ s_好 \in S, s_坏 \notin S $$ 1.2 首先我们可以将决策看作一棵树，而每一个取式其实就是一棵子树或者叶子节点。会过来看合取式的析合范式，其实就是在一整棵树中取 $k$ 个互相不包含的子树或者叶子节点。 这里不能直接确定答案，因为题目并没有说决策树能不能给出形如下面的节点： $$ (色泽\in\{青绿，乌黑\}; 根蒂=*; 敲声=*) $$ 我们先假设题目不允许上述的情况出现，那我们可以断言，包含 $n$ 个并列条件的决策，整棵树的深度为 $n + 1$，因为每一个父子关系其实就是析构 $*$ 和具体内容。 这个问题其实不能简单估算，但是我们可以用树形动态规划来解决。设状态 $f[u][p]$ 代表以节点 $u$ 为根的子决策树有 $p$ 个合取式的析合范式情况数。同时我们注意到书上的旁注：会有冗余的等价情况，那么我们还需要去除这样的等价情况，即在本题中我们需要去除 $$ \bigcup_{v \in u.sons} v = u $$ 的情况。 下面是递推方程： $$ f[u][p] = \sum_{\sum_{1 \leq i \leq |u.sons|} p_i = p, p_i \geq 0} f[v_i][p_i] $$ 减去冗余情况： $$ f[u][|u.sons|] := f[u][|u.sons|] - 1 $$ 1.3 举例：线性回归。 1.4 $$ E_{ote} (\mathfrak L_a | X, f) = \sum_h \sum_{\boldsymbol x \in \mathcal X - X} P(\boldsymbol x) \ell (h(\boldsymbol x), f(\boldsymbol x)) P(h | X, \mathfrak L_a) $$ $$ \begin{aligned} \sum_f E_{ote} &= \sum_f \sum_h \sum_{\boldsymbol x \in \mathcal X - X} P(\boldsymbol x) \ell (h(\boldsymbol x), f(\boldsymbol x)) P(h | X, \mathfrak L_a) \\ &=\sum_{\boldsymbol x \in \mathcal X - X}P(\boldsymbol x)\sum_h P(h | X, \mathfrak L_a) \sum_f \ell (h(\boldsymbol x), f(\boldsymbol x)) \end{aligned} $$ 注意到最后一部分为与 $\mathfrak L$ 无关的常数。不妨设 $$ L = \sum_f \ell (h(\boldsymbol x), f(\boldsymbol x)) $$ 故原式等于 $$ L\sum_{\boldsymbol x \in \mathcal X - X}P(\boldsymbol x)\sum_h P(h | X, \mathfrak L_a) = L\sum_{\boldsymbol x \in \mathcal X - X}P(\boldsymbol x) \cdot 1 $$ Q.E.D. 1.5 略。
Data Augmentation 这个词其实很容易误导人，因为 Augmentation 是增广的意思。数据增广，自然而然就会让人理解为：“增加了新的数据”。然而在实现的过程中，不一定是这样。 我们会给定一些随机化的参数，在每个 epoch 内生成随机增广后的图片。 比方说，每个 epoch 都按照一定的 random rule 来 crop 图片、调整色调，便是图像增广。 PyTorch 实现 这里拿 Fashion-MNIST 举例，同样我们会给出例子来证明我们的做法是行之有效的。 首先引入包： %matplotlib inline %config InlineBackend.figure_formats = ['svg'] from matplotlib import pyplot as plt import torch import torchvision from torch.utils import data 加载 FashionMNIST 数据集，并且禁用 shuffle，这样保证我们每个 epoch 图片顺序都是相同的，方便我们验证： def load_data_fashion_mnist(batch_size, dataloader_worker_count, resize=None): trans = [torchvision.transforms.ToTensor()] if resize: trans.insert(0, torchvision.transforms.Resize(resize)) trans.append(torchvision.transforms.RandomCrop((28, 28))) trans = torchvision.transforms.Compose(trans) mnist_train = torchvision.datasets.FashionMNIST( root="../data", train=True, transform=trans, download=True) mnist_test = torchvision.datasets.FashionMNIST( root="../data", train=False, transform=trans, download=True) return (data.DataLoader(mnist_train, batch_size, shuffle=False, num_workers=dataloader_worker_count), data.DataLoader(mnist_test, batch_size, shuffle=False, num_workers=dataloader_worker_count)) 辅助渲染的函数： def get_fashion_mnist_labels(labels): ''' 返回Fashion-MNIST数据集的文本标签 ''' text_labels = ['t-shirt', 'trouser', 'pullover', 'dress', 'coat', 'sandal', 'shirt', 'sneaker', 'bag', 'ankle boot'] return [text_labels[int(i)] for i in labels] def show_images(imgs, num_rows, num_cols, titles=None, scale=1.2): ''' 绘制图像列表 ''' figsize = (num_cols * scale, num_rows * scale) _, axes = plt.subplots(num_rows, num_cols, figsize=figsize) axes = axes.flatten() for i, (ax, img) in enumerate(zip(axes, imgs)): if torch.is_tensor(img): # 图片张量 ax.imshow(img.numpy()) else: # PIL图片 ax.imshow(img) ax.axes.get_xaxis().set_visible(False) ax.axes.get_yaxis().set_visible(False) if titles: ax.set_title(titles[i]) return axes 测试三个 epoch，看每次 epoch 第一个 batch 的数据： train_iter, test_iter = load_data_fashion_mnist(18, 4, resize=40) for _ in range(3): for i, (X, y) in enumerate(train_iter): if i == 0: show_images(X.reshape(18, 28, 28), 2, 9, titles=get_fashion_mnist_labels(y)) 输出： 可以看出有明显的不同。 本文中的 notebook：https://github.com/JeffersonQin/deep-learning/blob/master/tests/pytorch-data-augmentation.ipynb
论文链接：https://arxiv.org/abs/1506.02640 Abstract 以前都是用 Classifiers 来做 detection 现在：we frame object detection as a regression problem to spatially separated bounding boxes and associated class probabilities end-to-end FAST! Fast YOLO: 155 fps, double mAP of other real-time detectors YOLO: 45 fps Introduction Related works Deformable Parts Models (DPM): sliding window approach where the classifier is run at evenly spaced locations over the entire image R-CNN: first generate potential bounding boxes in an image then run a classifier on these proposed boxes post-processing: refine the bounding boxes, eliminate duplicate detections, and rescore the boxes based on other objects in the scene YOLO Fast, realtime simple architecture see the entire image => less background error learn generalizable representations of objects accuracy 不行, 虽然识别率高，但是定位精准度相对低 Architecture Unified Detection 描述大致的识别思路。 先划分成 $S\times S$ 方格，每个方格需要检测是否有物体的中心在这个方格内，产生 $B$ 个 bounding box 每个 bounding box 会产生五个预测量 $x, y, w, h, \text{confidence}$。注意：$x,y$ 是相对于 cell 的，$w, h$ 是相对于整个图像的。 confidence 描述这个区域有物体的置信度。confidence 的定义： $$ P(\text{Object}) \times \text{IoU}_{\text{pred}}^{\text{truth}} $$ 每个方格产生一个还会对 $C$ 个类别判断的概率，判断这个方格内是否含有类别 $C_i$ $$ P(\text{Class}_i \mid \text{Object}) $$ 测试的时候每个 bounding box 的置信概率就是 $$ P(\text{Class}_i \mid \text{Object}) \times P(\text{Object}) \times \text{IoU}_{\text{pred}}^{\text{truth}} = P(\text{Class}_i) \times \text{IoU}_{\text{pred}}^{\text{truth}} $$ Network Design 我们取 $B=2$，每个区域生成两个 bounding box，区域数量（边） $S=7$，然后分类的类别是 $C=10$。所以最后的输出 $$ S \times S \times (5B + C) = 7 \times 7 \times 30 $$ Training Pretrain ImageNet 数据集 前 20 个卷积层（去掉最后四个卷积层和两个全连接层）再加上一个平均池化层和一个全连接层 Activation 出最后一个层外，使用 Leaky ReLU $$ \phi(x) = \begin{cases} x & x > 0 \\ 0.1x & \text{otherwise} \end{cases} $$ 最后一层文章中说用的是 linear activation function 除此之外，因为最后的结果应该在 $[0,1]$ 范围之内，查到一个 stackoverflow 的问题说最后可能对 output 逐元素做了 sigmoid. https://stackoverflow.com/questions/49707542/yolo-v1-bounding-boxes-during-training-step Hyper Parameters $\text{batch size} = 64$ $\text{weight decay} = 0.0005$ $\text{momentum} = 0.9$ learning rate $10^{-3} \rightarrow 10^{-2}$ for some epochs $10^{-2}$ for $75$ epochs $10^{-3}$ for $30$ epochs $10^{-4}$ for $30$ epochs Regularization Dropout (0.5) after the first connected layers Loss Function 问题一：均方差损失函数对所有东西的权重都相同 如果一个区域不含东西，那么根据定义 confidence 直接降到 0，但是这就会造成梯度的急剧抖动。同时，现在不管是对位置的预测还是对概率的置信，所有权重都是相同的，这显然不符合目标，所有作者提出了下面两个 param: $$ \lambda_{\text{coord}} = 5, \lambda_{\text{noobj}} = .5 $$ 在算坐标预测的 loss 的时候提高权重，然后对于不含目标的划分区间降低权重。 问题二：不管 bounding box 的大小，权重都一样 解决方案：计算 $w, h$ 方根的均方损失 问题三 YOLO 对于每个区域都会产生若干个 bounding box，但是训练的时候我们只希望每个目标对应一个 bounding box。所以最后计算 loss 的时候，我们就会 assign 一个 bounding box predictor 给每个目标。这个 assign 的依据是取 $$ \operatorname{argmax}_{i, B_i \in B} \text{IoU}_{\text{truth}}^{B_i} $$ Loss 原文好像 sigma 的下标有点问题，这里做一下修正 $$ \begin{aligned} &\lambda_{\textbf{coord}} \sum_{i=1} ^ {S^2} \sum_{j=1}^{B} 1 _{ij}^{\text{obj}} \left[(x_i - \hat{x_i})^2 + (y_i - \hat{y_i})^2\right] \\ +&\lambda_{\textbf{coord}} \sum_{i=1} ^ {S^2} \sum_{j=1}^{B} 1 _{ij}^{\text{obj}} \left[ \left(\sqrt{w_i} - \sqrt{\hat{w_i}}\right)^2 + \left(\sqrt{h_i} - \sqrt{\hat{h_i}}\right)^2 \right] \\ +&\sum_{i=1} ^ {S^2} \sum_{j=1}^{B} 1 _{ij}^{\text{obj}}\left(C_i - \hat{C_i}\right)^2 \\ +&\lambda_{\textbf{noobj}}\sum_{i=1} ^ {S^2} \sum_{j=1}^{B} 1 _{ij}^{\text{noobj}}\left(C_i - \hat{C_i}\right)^2 \\ +&\sum_{i=1}^{S^2} 1_{i}^{\text{obj}} \sum_{c\in\text{classes}} (p_i(c) - \hat{p_i}(c))^2 \end{aligned} $$ where $1^{\text{obj}} _i$ denotes if object appears in cell $i$, and $1^{\text{obj}}_{ij}$ denotes that the $j$th bounding box predictor in cell $i$ is “responsible” for that prediction. 从上到下看还挺好理解的。 实践中的问题 对于每一个 cell，如果有多个东西就无解了，因为 loss 中没有说明这种情况。 一些想法 总的来说，Yolo v1 apply 了大量的 tricks... 太难训了。我自己训比原文低了 15 个点左右 ... 虽然用的是 resnet18/50。
题面 https://www.luogu.com.cn/problem/P1363 题解 先说正解。 怎么样才能判断可以无限延伸呢？那就是如果存在一条路径 $$ P \rightsquigarrow P' $$ 其中 $P'$ 为任意一个虚幻棋盘中 $P$ 的对应点。 证明十分容易。 充分性证明：记坐标 $P$ 为 $P(x, y), 0 \leq x < n, 0 \leq y < m$。那么： $$ P'(x + na, y + mb), a, b \in \mathbb Z, a,b 不同时为0 $$ 所以根据假设存在下面的路径： $$ P(x, y) \rightsquigarrow P(x + na, y + mb) $$ 则亦存在： $$ P(x + na, y + mb) \rightsquigarrow P(x + 2na, y + 2mb) $$ 我们将路径记作下面这种映射： $$ f(x, y) = (x + na, y + mb) $$ 故我们可以不断应用： $$ f^{(t)}(x, y) = \underbrace{f(f(\cdots f}_{t}(x, y) \cdots)) = (x + tna, y + tmb) $$ 故 $$ \lim_{t \rightarrow \infty} f^{(t)}(x, y) = \begin{cases} (\infty, \infty) & ab \neq 0 \\ (0, \infty) & a = 0 \\ (\infty, 0) & b = 0 \end{cases} $$ 必要性证明可以通过反证法证得： 向无穷远处延伸代表存在长度为无穷的路径。接下来应用反正：若存在长度为无穷的路径，且不存在形如题设的 $P \rightsquigarrow P'$ 的路径。 若不存在形如 $P \rightsquigarrow P'$ 的路径，那么路径长度必然是有限的，因为我们能够构造出来的路径都形如下式： $$ S \rightsquigarrow T = S \rightsquigarrow A_1 \rightsquigarrow A_2 \rightsquigarrow \cdots \rightsquigarrow A_p \rightsquigarrow T $$ 其中等式右侧的每条路径都不存在中间点。我们不难发现集合 $A$ 是有限的，因为原棋盘是有限的，故 $|A \cup \{S, T\}| \leq nm$。故长度必然为有限，与长度为无限矛盾。证毕。 下面是一些错误结论： 错误结论 1：向上下左右各拓展一个棋盘，如果一个点被等价走到了两次，那么就可以到达无穷。 反例： 代码 #include <iostream> #include <cstring> using namespace std; const int maxn = 1505; const int dx[4] = {-1, 0, 0, 1}; const int dy[4] = {0, -1, 1, 0}; int n, m, sx, sy, vx[maxn][maxn], vy[maxn][maxn]; bool map[maxn][maxn], vis[maxn][maxn], ans; void dfs(int x, int y, int lx, int ly) { if (ans) return; if (vis[x][y]) { if (vx[x][y] != lx || vy[x][y] != ly) ans = 1; return; } vis[x][y] = 1; vx[x][y] = lx; vy[x][y] = ly; for (int i = 0; i < 4; i ++) { int xx = (x + n + dx[i]) % n; int yy = (y + m + dy[i]) % m; int lxx = lx + dx[i], lyy = ly + dy[i]; if (map[xx][yy]) dfs(xx, yy, lxx, lyy); } } int main() { char in; while (cin >> n >> m) { for (int i = 0; i < n; i ++) for (int j = 0; j < m; j ++) { cin >> in; map[i][j] = (in != '#'); if (in == 'S') sx = i, sy = j; } memset(vis, 0, sizeof(vis)); memset(vx, 0, sizeof(vx)); memset(vy, 0, sizeof(vy)); ans = 0; dfs(sx, sy, sx, sy); if (ans) cout << "Yes" << endl; else cout << "No" << endl; } return 0; }
P3572 [POI2014] PTA-Little Bird - DP 单调队列
题面 https://www.luogu.com.cn/problem/P3572 题解 首先，不难列出方程：$f[i]$ 代表跳到 $i$ 的最小疲劳值 $$ f[i] = \min_{i - k \leq j < i} \{f[j] + (a[i] \geq a[j])\} $$ 时间复杂度为 $O(qn^2)$，不理想。但是不难发现，这道题可以用单调队列进行优化。为什么？ 如下状态一定是更优的：随着 index 递增 $f$ 不下降（第一维比较） $f$ 若相同，同时有 $a$ 不上升（第二维比较） 所以我们就可以用单调队列来维护 index，时间复杂度为 $O(qn)$ 注意： 初值的设定，详见代码 写的顺序和单调队列的模板稍微有一点不同，因为 $i - k \leq j < i$，右边的小于号不是小于等于号，即 $f[i]$ 不能被自己更新，所以调整了一下逻辑块的顺序。 代码 #include <iostream> using namespace std; const int maxn = 1e6+5; int qq, n, k, head, tail, a[maxn], f[maxn], q[maxn]; int main() { cin >> n; for (int i = 1; i <= n; i ++) cin >> a[i]; cin >> qq; while (qq --> 0) { cin >> k; head = 1; tail = 1; q[1] = 1; for (int i = 2; i <= n; i ++) { while (head <= tail && q[head] < i - k) head ++; f[i] = f[q[head]] + (a[i] >= a[q[head]]); while (head <= tail && ( f[i] < f[q[tail]] || ( f[i] == f[q[tail]] && a[i] >= a[q[tail]] ) )) tail --; q[++ tail] = i; } cout << f[n] << endl; } return 0; }
Preface 三年前的四月，第一次接触 OI。初三下，小教室里听着 fcx 讲着滑动窗口单调队列，放学后去本部蹭了第一节斜率优化的课，随即拉开了我长达两年的竞赛摆烂之旅。 记忆犹新。第一个注册的 OJ 账户就是 POJ，第一道 AC 的题便是 POJ 2823 滑动窗口。 多年过去，今天再看这个基础中的基础，茫然。只能说这是究极摆烂的下场罢。总之就好好写一下题解。 题面 https://www.luogu.com.cn/problem/P1886 题解 接下来只讨论求最小值的情况。设 $f[i]$ 代表终止于位置 $i$ 的滑动窗口的最小值： $$ f[i] = \min_{i - k < j \leq i} a[j] $$ 如果暴力做的话时间复杂度为 $O(n^2)$。这里我们需要使用单调队列来优化。 对于最小值：单调队列内的元素值递增，同时 index 也是递增的。为什么这样做？思考一个情况：index 递增的情况下，如果一个 $a[i] > a[j], i < j$，那么在 $i,j$ 都有效的范围内，$a[i]$ 永远不可能作为答案。 这里有一句经典的话：如果一个选手年龄比你小，但却比你强，那你就可以退役了。我们把 index 比作出生年份，$a[]$ 比作能力，那么这句话就维护了一个求最大值的单调队列。 接下来是代码中需要注意的一些问题： head, tail 不是左闭右开，而是 $[head, tail]$。这样做的原因是访问 head 和 tail 的元素就可以简单的：q[head], q[tail] 队列里存的是 index （pos） 注意：第二个 while 可以修改为 if，因为每次 i ++ 且 q 内的 pos 递增，写成 while 是习惯。 代码 #include <iostream> using namespace std; const int maxn = 1e6+5; int n, k, a[maxn], q[maxn], head, tail; int main() { cin >> n >> k; for (int i = 1; i <= n; i ++) cin >> a[i]; // min head = 1, tail = 0; for (int i = 1; i <= n; i ++) { while (head <= tail && a[i] <= a[q[tail]]) tail --; q[++ tail] = i; while (head < tail && q[head] <= i - k) head ++; if (i >= k) cout << a[q[head]] << " "; } cout << endl; // max head = 1, tail = 0; for (int i = 1; i <= n; i ++) { while (head <= tail && a[i] >= a[q[tail]]) tail --; q[++ tail] = i; while (head < tail && q[head] <= i - k) head ++; if (i >= k) cout << a[q[head]] << " "; } cout << endl; return 0; }
leetcode 1787 使所有区间的异或结果为零 - DP - 随机跳题计划
Preface 好耶，少见的难题。 题面 https://leetcode-cn.com/problems/make-the-xor-of-all-segments-equal-to-zero/ 题解 大部分题解已经提到了：就是下面这个结论。 结论：最终构造出来的数列以 $k$ 为一个周期 证明： 由题设： $$ a[1] \oplus a[2] \oplus \cdots \oplus a[k] = a[2] \oplus a[3] \oplus \cdots \oplus a[k + 1] $$ 所以我们有： $$ (a[1] \oplus a[2] \oplus \cdots \oplus a[k]) \oplus (a[2] \oplus a[3] \oplus \cdots \oplus a[k + 1]) = 0 $$ 根据异或的交换律与结合律： $$ a[1] \oplus a[k + 1] = 0 $$ 故 $a[1] = a[k + 1]$。易证，此结论可以将 $1$ 替换为任意定义域内的数。 接下来思考一下最终构造出来的数列满足什么特征： 以 $k$ 为一个周期 第一个周期异或和为 0 接下来看图说话: 在上图中 $n = 13, k = 3$，我们就是需要让 $$ a[1] = a[4] = a[7] = a[10] = a[13] $$ $$ a[2] = a[5] = a[8] = a[11] $$ $$ a[3] = a[6] = a[9] = a[12] $$ $$ a[1] \oplus a[2] \oplus a[3] = 0 $$ 那么我们不妨一组一组按列处理，接下来是状态的设法：$f[i][j]$ 代表处理完第 $i$ 列，使得前 $i$ 列的异或和为 $j$ 的最少修改次数。 思考转移方程：都是从上一列转移，但是有两种转移方式： 第 $i$ 列全部修改 第 $i$ 列部分修改，部分保留 设 $cnt$ 为第 $i$ 列的个数，$t[j]$ 代表第 $i$ 列 $j$ 出现的次数，那么： $$ f[i][j] = \min (f[i][j], cnt + \min_{k} f[i - 1][k]) $$ $$ f[i][j] = \min_{k \in \text{column }i} \{f[i][j], f[i - 1][j \oplus k] + cnt - t[k]\} $$ 注意：全部修改仍然有可能比部分修改更优，这是因为本题不是简单的贪心。具体可以见下一小节，我们可以构造出反例，证明贪心是错误的。 此外，我们还需要注意初值的设定。 构造贪心的反例 贪心？怎么贪心？那当然是每一列选择相同数量最多的，再把这个数量排序，相同数量最少的一列全部改变，使得最后异或值为 0。 但是这个反例是非常容易构造的。 第一列： $$ a, a, b, b, b, c, c $$ 第二列： $$ d, d, d, d, e, e, e $$ 第三列： $$ f,f,g,g,h,h,i $$ 按照之前说的贪心，我们会选保留 $b, d$，然后第三列适应答案使得异或为 $0$。但是如果很不巧，我们的构造在这样的情况下其他元素全部需要改变，那么此时的改动数量为 $4 + 5 + 7 = 16$。然而如果 $a \oplus e \oplus f = 0$，那么如果我们选择 $a, e, f$，改动的数量就是 $5 + 4 + 5 = 14 < 16$，更优。构造完毕。 代码 const int maxn = 2e3+5; const int maxl = 10; class Solution { int f[maxn][1 << maxl]; int g[maxn], a[maxn], t[1 << maxl]; public: int minChanges(vector<int>& nums, int k) { int n = nums.size(); for (int i = 0; i < n; i ++) a[i + 1] = nums[i]; memset(f, 0x7f, sizeof(f)); memset(g, 0x7f, sizeof(g)); memset(t, 0, sizeof(t)); int cnt = 0; for (int j = 1; j <= n; j += k) t[a[j]] ++, cnt ++; for (int j = 0; j < 1024; j ++) { f[1][j] = min(f[1][j], cnt - t[j]); g[1] = min(g[1], f[1][j]); } for (int i = 2; i <= k; i ++) { memset(t, 0, sizeof(t)); cnt = 0; for (int j = i; j <= n; j += k) t[a[j]] ++, cnt ++; for (int j = 0; j < 1024; j ++) { f[i][j] = g[i - 1] + cnt; for (int m = 0; m < cnt; m ++) { f[i][j] = min(f[i][j], f[i - 1][j ^ a[m * k + i]] + cnt - t[a[m * k + i]]); } g[i] = min(g[i], f[i][j]); } } return f[k][0]; } };
题面 https://www.luogu.com.cn/problem/P2210 题解 一开始没反应出来是状压，看了少数题解才知道可以状压。今天姑且 A 掉状压的写法，明天写写看模拟退火。 首先，我们来设状压的状态方程： $$ f[i] $$ $i$ 代表 $i$ 表示成二进制的时候有 $1$ 那些位所代表的牛组成的集合 比方说 $i = 6 = (110)_2$ 代表有 $2, 3$ 号牛组成的集合 $f[i]$ 代表牛的集合为 $i$ 时对答案产生的贡献。 什么是贡献？这个说法很模棱两可。其实是这样的：两个朋友都在集合里面，那答案必然要包括这对朋友连线的贡献。但是如果只有一头牛在集合里呢？很简单，贡献就是：按照某种最佳排列时，这头牛所处的位置到集合队尾的距离。这么说很抽象，我们举个例子： $$ ~ * ~ * ~ * ~ \triangle ~ * ~ * $$ 上图中，$*$ 代表无所谓的某头牛，$\triangle$ 代表我们现在考察的单个朋友，在这个状态下，$\triangle$ 对答案的贡献就是 $2$，因为 $\triangle$ 之后还有两头牛. 而如果在这个队列之后紧跟就是 $\triangle$ 的朋友：另一个 $\triangle$，那么在增加前 $\triangle$ 给出的贡献 $2$ 就是这对朋友对答案的贡献了： $$ ~ * ~ * ~ * ~ \triangle ~ * ~ * ~ \triangle $$ 好。赘述完关于状态的定义，我们来思考状态怎么转移。对于集合 $i$，我们可以枚举位于队列尾端的到底是哪头牛。每次转移我们只需要加上原来的集合中孤立朋友的数量即可。最终给出的代码是做了一些小的优化，稍微难以理解，所以下面给出一个等价的形式，但是时间复杂度多一个 $n$，为 $O(n^22^n)$： for (int i = 1; i < (1 << n); i ++) { for (int j = 0; j < n; j ++) { if ((1 << j) & i) { int pending_links = 0; int ii = i & ~(1 << j); for (int k = 0; k < n; k ++) if ((1 << k) & ii) pending_links += 3 - (((ii >> nbr[k][0]) & 1) + ((ii >> nbr[k][1]) & 1) + ((ii >> nbr[k][2]) & 1)); f[i] = min(f[i], f[ii] + pending_links); } } } 代码 最终给出的代码时间复杂度为 $O(n2^n)$： #include <iostream> #include <cstring> using namespace std; const int maxn = 12; int f[1 << maxn], nbr[maxn + 5][3]; int main() { int n; cin >> n; for (int i = 0; i < n; i ++) { cin >> nbr[i][0] >> nbr[i][1] >> nbr[i][2]; nbr[i][0] --; nbr[i][1] --; nbr[i][2] --; } memset(f, 0x7f, sizeof(f)); f[0] = 0; for (int i = 1; i < (1 << n); i ++) { int pending_links = 0; for (int j = 0; j < n; j ++) if ((1 << j) & i) pending_links += 3 - (((i >> nbr[j][0]) & 1) + ((i >> nbr[j][1]) & 1) + ((i >> nbr[j][2]) & 1)); for (int j = 0; j < n; j ++) { if ((1 << j) & i) { f[i] = min(f[i], f[i & ~(1 << j)] + pending_links - (3 - (((i >> nbr[j][0]) & 1) + ((i >> nbr[j][1]) & 1) + ((i >> nbr[j][2]) & 1))) + ((i >> nbr[j][0]) & 1) + ((i >> nbr[j][1]) & 1) + ((i >> nbr[j][2]) & 1)); } } } cout << f[(1 << n) - 1] << endl; return 0; }