图谱分解的拉普拉斯矩阵中特征值与特征向量的含义

图的谱分解是人们研究图的一个重要方向，对于图卷积神经网络有着非常重要的作用。然而在阅读相关文献[1]时，发现其中图的谱分解涉及到图的拉普拉斯矩阵的特征值与特征向量非常难以理解，因此我花了一段时间研究了网上的资料，最终写下了这篇文章。

拉普拉斯矩阵的含义

说道拉普拉斯矩阵，不得不先提一下与之相关的另一个我们比较熟悉的数学概念：拉普拉斯算子。

\Delta f = \nabla^2 f = \sum_{i=1}^{n} \frac{\partial^2 f}{\partial x_i^2}

在图像处理中，拉普拉斯算子可以用于边缘检测，比如下面这张图，就是对x坐标使用了拉普拉斯算子的结果——

See the source image

当然，上面的图片也可以看做以\left( \begin{matrix} -1 & 2 & -1 \\ -1 & 2 & -1 \\ -1 & 2 & -1 \end{matrix} \right)作为卷积核的图卷积操作，这样的卷积适用于抓取横向的边缘信息。当然我们也可以设计卷积核同时抓取横向和纵向的信息\left( \begin{matrix} 0 & -1 & 0 \\ -1 & 4 & -1 \\ 0 & -1 & 0 \end{matrix} \right)。这个卷积核就是上面列到的拉普拉斯算子的离散版本了。

从直观上来说，拉普拉斯反映了图像的边界信息，实际上，我们也可以理解为某一个像素点变为其向量的元素点产生的期望影响大小。（可以很容易看出，边缘拉普拉斯算子计算出来的值较大，而均匀色块计算出来的值则为零，表示一个像素变为相邻元素的期望影响为零）。从某种意义上来说，拉普拉斯算子非常成功刻画了一个像素的邻域信息。

对于图像来说，拉普拉斯矩阵就是将卷积的操作修改为矩阵，如一个3\times 3的图像，有

L = \left( \begin{matrix} 4 & -1 & 0 & -1 & 0 & 0 & 0 & 0 & 0 & \\ -1 & 4 & -1 & 0 & -1 & 0 & 0 & 0 & 0 & \\ 0 & -1 & 4 & 0 & 0 & -1 & 0 & 0 & 0 & \\ -1 & 0 & 0 & 4 & -1 & 0 & -1 & 0 & 0 & \\ 0 & -1 & 0 & -1 & 4 & -1 & 0 & -1 & 0 & \\ 0 & 0 & -1 & 0 & -1 & 4 & 0 & 0 & -1 & \\ 0 & 0 & 0 & -1 & 0 & 0 & 4 & -1 & 0 & \\ 0 & 0 & 0 & 0 & -1 & 0 & -1 & 4 & -1 & \\ 0 & 0 & 0 & 0 & 0 & -1 & 0 & -1 & 4 \end{matrix} \right)

而图的拉普拉斯算子，也可以理解为将一个节点权值变成其相邻节点权值的期望影响，对应的矩阵是L = D-W，其中D是图的度数矩阵，W是图的边权矩阵。有没有发现，不管是图，还是图像，拉普拉斯矩阵都是对角线为正数，其他地方为负数。

图的拉普萨斯矩阵

当然，图的拉普拉斯矩阵有若干不同的变种，分别为：

  • 非标准化的拉普拉斯矩阵：L = D-W
  • 标准化的拉普拉斯矩阵：L_{sym} = D^{-1/2} L D^{-1/2} = I - D^{-1/2} W D^{-1/2}
  • 标准化的拉普拉斯矩阵：L_{rw} = D^{-1}L = I - D^{-1}W

拉普拉斯矩阵特征

我们令L = D-W，则L满足如下特征：

  • 对于任意f \in \mathbb{R}^n，有f' L f = \frac{1}{2} \sum_{i,j=1}^{n} w_{i,j} (f_i-f_j)^2
  • L是对称的半正定矩阵
  • 矩阵L的最小特征值为1，其对应的特征向量为1
  • L的特征值是非负实数0 = \lambda_1 \leq \lambda_2 \leq \lambda_3 \leq \dots \lambda_n
  • L的特征值中0的个数等同于原图的连通块数量。

对于上述特性的证明如下——

特性1：

(1)   \begin{align*} f' W f &= f' D f - f' W f \\&= \sum_{i=1}^n d_i f^2_i - \sum_{i=1}^n f_i f_j w_{ij} \\&= \frac{1}{2} \left( \sum_{i=1}^n d_i f^2_i - 2 \sum_{i,j=1}^n f_i f_j w_{ij} + \sum_{i=1}^n d_i f^2_i \right) \\&= \frac{1}{2} \sum_{i,j=1}^{n} w_{i,j} (f_i-f_j)^2\end{align*}

特性2：

由于度数矩阵D和权值矩阵W都是对称的，所以L=D-W也是对称矩阵。同时，由于特性1，我们发现f'Wf \geq 0对于所有f \in \mathbb{R}成立，所以矩阵是半正定的。

特性3：

将1带入即可验证

特性4：

可以通过特性2保证特征值非负实数，通过特性3保证存在0特征值。

特性5：

倘若希望f' L f = \frac{1}{2} \sum_{i,j=1}^{n} w_{i,j} (f_i-f_j)^2 = 0，那么我们需要保证在w_{i,j} \neq 0时，f_i = f_j，因此，f_i = 1一定是一个可能的解，但是，当图存在多个连通块时，相等关系只需要在块内满足即可，因此，可能有等同于连通块个数个正交基满足特征值为0.

上述内容可以在参考文献[2]中查看详细信息。

基于拉普拉斯矩阵的图的谱分解

在文献[1]中，定义了||\nabla x||_W^2 = \sum_i \sum_j W_{ij} [x(i)-x(j)]^2，其实这只是上一小节里面f' L f的另一种表现形式而已。

不过一个比较混乱的地方在于文章[1]借用||\nabla x||_W^2生成了一系列基f_0, f_1, \dots, f_m，满足——

(2)   \begin{align*}f_0 = \arg min _{x \in \mathbb{R}^m, ||x||=1} ||\nabla x||_W^2 = (1/\sqrt{m}) 1_m \\f_i = \arg min _{x \in \mathbb{R}^m, ||x||=1, x \perp \{v_0, v_1, \dots, v_{i-1}\}} ||\nabla x||_W^2 \end{align*}

实际上，这些f_i恰好是L的特征值从小到大对应的特征向量！

证明可以这样想，若f为L的\lambda特征值对应的特征向量，且\|x\| = 1，那么f' W f = \lambda f' f = \lambda。现在假设f_0, f_1, \dots, f_{i-1}是L的前i-1个特征向量，我们希望证明下一个能够最小化||\nabla x||_W^2的向量f_t恰好是f_i。如果存在f' W f < \lambda_i，那么f一定与f_0, f_1, \dots, f_{i-1}中的某一个向量不正交。如果保证了f_t与f_0, f_1, \dots, f_{i-1}正交，那么任意一个非f_t的向量，一定包含了一个特征值大于等于\lambda_i的基，则最终一定没有f_i优。因此，我们发现将L的特征向量作为解是最优的。

谱分解的作用

我们可以使用傅里叶对于卷积的优化来类比图的谱分解对于图卷积的意义。原来图上面做卷积是将一个邻域内的点与一个“卷积核”做卷积，这个“卷积核”的权值个数会相对比较多一些，而谱分解就是考虑到了“时域的卷积等于频域的点积”。将图的权值矩阵映射为“不同频率的分量强度为多少”，而对这个“强度”做点积完全等效于原来的卷积。这样一方面减少运算量，另一方面还减少了（如神经网络的）待训练权值个数。

引用

[1] Bruna J, Zaremba W, Szlam A, et al. Spectral networks and locally connected networks on graphs[J]. arXiv preprint arXiv:1312.6203, 2013.

[2] Von Luxburg, Ulrike. “A tutorial on spectral clustering.” Statistics and computing 17.4 (2007): 395-416.

[3] 图卷积神经网络(GCN)详解:包括了数学基础(傅里叶，拉普拉斯)

SelectorGAN汉字风格迁移模型（Chinese Charactor Style Transfer)

这个项目是在 CVPR论文 Separating Style and Content for Generalized Style Transfer的基础上改进而来的，是我和LJSthu在学校人工神经网络课程上面的课程作业。我们提出的模型叫做SelectorGAN，从模型效果上面来看，大幅度超越了上文中提出的state of art算法EMD，但模型本身并没有对应的paper，因此，如果希望研究汉字迁移问题，并且引用本文的模型，可以直接引用本博客。

我们的模型尝试处理这样一个问题：给定风格A的16个字体图片，以及字B的不同风格16个图片，尝试合成同时拥有字体A与风格B的图片。如下图所示，一个是ground truth，一个是模型输出，你能猜出谁是谁吗？

首先，我们找到了原文模型EMD的代码，并使用自己的数据集进行复现，得到下图的效果，其中右图是ground true，左图是模型生成结果。可以发现，在我们自己的数据集（规模和原文差不多）上面，模型完全没有paper里面配图的讲的那么好。

与之对比的，是我们提出的SelectorGAN输出如下图所示，其中，左边是ground truth ，右边是模型的输出结果。最明显的区别是我们的模型不容易生成全黑或者全白的无意义图片，几乎所有文字都是清晰可辨的。

在介绍我们的模型之前，我们先分析了当前state of art模型的缺陷。EMD模型的图例如下图所示，将16张候选图片，输入到CNN的16个channel中。这里，由于16张图片是无序不可分的，而CNN的不同Channel是有序可分的，这里就会导致交换输入图片的顺序会产生不同的结果。这其实是一个不正确的做法，倘若我们将16*1的CNN作用于16张图片修改16个为1*1的CNN分别作用于16张图片，可以将模型的参数个数降低16倍，有效降低过拟合的出现。用时，原文的欧几里得距离损失函数，也是的模型在对于生成图片没有信心时，直接输出全部空白，或者全部黑色，而正常图片也存在模糊边界的问题。这一系列问题到这了EMD模型实际跑的并没有文章中说的那么厉害。

我们的模型SelectorGAN为了解决上述的问题，引入了若干个特殊的机制。首先，为了解决生成图像模糊的问题，我们不在使用回归模型训练，而是使用生成模型进行创造。具体来说，我们使用了GAN。

基于回归的模型，非常容易出现全黑/全白的情况

我们使用的GAN实际上是魔改版的 CycleGAN and pix2pix，使用了GAN后，我们发现生成模型可以很好的理解诸如字体宽度，字体边界曲率等信息，并加以模仿。

不同字体迁移到同一风格，基本不存在风格上的区别

接下来，我们发现，将原文中16个风格和16个字体结合生成的效果，与1个风格1个字体结合生成效果无区别。上图就是用1对1的方式生成的16张候选图片。

1对1的生成还会出现另一个比较麻烦的东西，就是生成器容易通过增删笔画的方式欺骗判别器。

通常，当原字体与目标字体长款比差距较大时，Generator认为增添笔画可以糊弄Discriminator，而且实际上它成功了。

对于上述的问题，我们发现，我们现在有整整16张候选图片。我们希望能够设计出一个评分模型Selector实现字体的选择。这个Selector应该怎么设计呢？

使用Selector的评分，可以从16张后选中选出最好的结果

一个直观的想法是直接使用Discriminator的输出当做Selector，因为Discriminator觉得“真的”的图片往往真的很像答案。但是这样做并不好，因为Discriminator输入的是一堆“真的或者假的”图片，但是实际上，即使是假的图片，不考虑原来输入的话，在风格上都是无懈可击的。这时Discriminator并不能很好的判断出输出的好坏。

基于上面的考虑，我们额外设计了一个Selector模型，作为一个评分模型，通过预测Discriminator的评分进行训练，与Discriminator不同的是，Selector同时使用原始输入图片与Generator的生成图片作为输入，且可以理解为Discriminator的滑动平均。降低了Discriminator的抖动。（当然，实验证明，将Selector评分和Discriminator评分加权平均能够获得更好的效果）

上面两个图片介绍了我们的SelectorGAN的基本原理。同时，我们也在模型上进行了若干试验，比如对于style vector进行插值，可以得到两种风格间的渐变矩阵。

以上就是对于我们模型的简要介绍，有兴趣也可以阅读我们的展示ppt与课程论文。

SelectorGAN

汉字风格迁移-2.0

ubuntu安装ss-server

相比于普通的ssserver， ss-server命令支持更多的加密方式，也更加安全。安装它，需要首先在终端执行下列命令

apt update
apt install shadowsocks-libev

接着在用户目录新建配置文件config.json——

{
	"server":"0.0.0.0",
	"server_port":8388,
	"local_address": "127.0.0.1",
	"local_port":1880,
	"password":"<password>",
	"timeout":300,
	"method":"aes-256-gcm",
	"fast_open": false
}

表示ss-server将监听0.0.0.0的8388端口，链接密码为<password>，加密方式为aes-256-gcm（现在已知比较安全的一种加密方式）。最后使用

ss-server -c config.json

运行服务端，即可实现ss-server的shadowsocks翻墙。

对于客户端，需要下载支持aes-256-gcm的客户端，如github的shadowsocksX-NG

Segmented LRU替换算法

在LRU(Least Recently Used)算法中，我们将缓存行按照最近使用时间进行排序。每次替换其中最长时间没有访问过的缓存行。

在实际的cache替换场景中，有一个很重要的现象，即如果一个缓存行被短时间访问了超过两次，那么他极有可能在近期再次被访问。LRU算法并没有基于该现象进行优化，而常常由于某一个常用缓存行在短时间内恰好没有使用而被替换出去。

Segmented LRU算法就是用来解决上述问题的，他通过在缓存行上面新加一个位，将缓存分为两个段(segment)，分别称作试用段(probationary segment)和保护段(protected segment)。保护段里面存放了那些近期被多次访问，极有可能再次被访问的缓存行。而试用段则存放最近被导入缓存，但是并没有被多次访问的段。

上图非常清楚的解释了两个段的关系——

  • 任何段的访问都会导致该行被移到保护段的顶端
  • 保护段中最近未被使用的行会被退回到试用段的顶端，在替换他之前，为它提供额外的机会

当然，如果我们仔细对比了LRU和SLRU的代码，可以发现区别并不像之前我们说的这么多。如果我们将保护段和试用段连到一起，你就会发现，SLRU和LRU唯一的区别就是当一个不在缓存中的行进入缓存时，LRU算法将它放在了第0号位置，即Most Recently Used的位置，而SLRU算法将它放在了不那么高的一个位置，即保护段和试用段连接处的位置。这样SLRU算法就不会担心某一些特定代码段（比如短时间塞入了大量无用缓存行）会完全破坏缓存的有效性了。

参考文献：R. Karedla et al, “Caching Strategies to Improve Disk System Performance”, Computer, vol. 27, no. 3, pp. 38-46, Mar. 1994.

使用mac对含FDisk_partition_scheme的U盘重新分区

我有一个4G的U盘，由于用来装机后，U盘被分层两个区。使用mac系统自带的Disk Utility只能够对于两个分区分别格式化，却不能够进行“分区”以及“删除分区”操作。

使用百度上建议的diskutil mergePartitions命令报如下错误——

Merging partitions encountered error "MediaKit reports partition (map) too small; if you recently grew your whole-disk, you should run whole-disk repair (-5341)".

使用终端命令diskutil list，可以看出U盘有如下结构——

/dev/disk5 (external, physical):

   #:                       TYPE NAME                    SIZE       IDENTIFIER

   0:     FDisk_partition_scheme                        *4.0 GB     disk5

   1:                  Apple_HFS                         2.9 GB     disk5s1

   2:                  Apple_HFS                         314.6 MB   disk5s2

第0项指示了U盘总空间大小，我猜测是类似于分区表的结构，而1号2号项则加起来大约4G，是我们需要合并的两个分区。

我的其他U盘的第0项的TYPE是“GUID_partition_scheme”。猜测可能我们的MAC系统不支持“FDisk_partition_scheme”的磁盘分区操作。而接下来，我们这试图将磁盘抹掉，重置为“GUID_partition_scheme”。

diskutil list
diskutil unmountDisk force disk5
sudo dd if=/dev/zero of=/dev/disk5 bs=1024 count=1024
diskutil list

此时，输出为

/dev/disk5 (external, physical):

   #:                       TYPE NAME                    SIZE       IDENTIFIER

   0:                                                   *4.0 GB     disk5

接着，我们使用diskutil重新对这个空白磁盘格式化

diskutil partitionDisk disk5 GPT JHFS+ "My External HD" 0g

现在，我们的磁盘就和普通u盘一样了，有3.7G的可用空间。

/dev/disk5 (external, physical):

   #:                       TYPE NAME                    SIZE       IDENTIFIER

   0:      GUID_partition_scheme                        *4.0 GB     disk5

   1:                        EFI EFI                     209.7 MB   disk5s1

   2:                  Apple_HFS My External HD          3.7 GB     disk5s2

参考链接：https://superuser.com/questions/233531/how-can-i-resolve-the-error-mediakit-reports-partition-map-too-small

浅析trapframe与context的原理与区别

TRAPFRAME与CONTEXT的区别

在ucore操作系统中，trapframe和context是很容易混淆的两个结构，他们都会出现在线程的调度中。实际上，结构体trapframe用于切换优先级、页表目录等，而context则是用于轻量级的上下文切换。从技术上来看，两者的区别在于context仅仅能够切换普通寄存器，而trapframe可以切换包括普通寄存器、段寄存器以及少量的控制寄存器。

*在看后续内容之前，你需要提前了解汇编语言、栈、C函数调用的实现。

TRAPFRAME结构体

trapframe定义如下——

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
struct trapframe {
    struct pushregs tf_regs;
    uint16_t tf_gs;
    uint16_t tf_padding0;
    uint16_t tf_fs;
    uint16_t tf_padding1;
    uint16_t tf_es;
    uint16_t tf_padding2;
    uint16_t tf_ds;
    uint16_t tf_padding3;
    uint32_t tf_trapno;
    /* below here defined by x86 hardware */
    uint32_t tf_err;
    uintptr_t tf_eip;
    uint16_t tf_cs;
    uint16_t tf_padding4;
    uint32_t tf_eflags;
    /* below here only when crossing rings, such as from user to kernel */
    uintptr_t tf_esp;
    uint16_t tf_ss;
    uint16_t tf_padding5;
} __attribute__((packed));

这个结构体中，依次储存了——

  • 目标寄存器
  • gs, fs, es, ds 段寄存器
  • trap_no, err 用于储存中断信息
  • eip, cs, eflags 用于储存陷阱(trap)返回后的目的地址
  • esp, ss 在权限发生变化时，用于指示新的栈的位置

有两个地方使用了trapframe，一个是中断调用，另一个是进程切换。两者对于trapframe的使用有相似之处，但也并不完全相同。

中断调用中使用TRAPFRAME

trapframe在中断中，在前期负责中断信息的储存，后期负责中断的恢复。同时，trapframe结构体是位于栈中的，其生成和使用都是通过栈的push、pop命令实现的，这将在后面详细解释。

中断发生时，下面代码，将一系列信息压到栈中。这些信息在后续的，trap(struct trapframe *tf)函数中，被对齐到了tf结构体中。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
.globl __alltraps                                                                                                                  
__alltraps:                                                                                                                        
    # push registers to build a trap frame                                                                                        
    # therefore make the stack look like a struct trapframe                                                                        
    pushl %ds                                                                                                                      
    pushl %es                                                                                                                      
    pushl %fs                                                                                                                      
    pushl %gs                                                                                                                      
    pushal                                                                                                                        
                                                                                                                                  
    # load GD_KDATA into %ds and %es to set up data segments for kernel
    movl $GD_KDATA, %eax
    movw %ax, %ds
    movw %ax, %es
 
    # push %esp to pass a pointer to the trapframe as an argument to trap()
    pushl %esp
 
    # call trap(tf), where tf=%esp
    call trap

中断处理完成后，需要恢复原来的运行状态，此时，按顺序将之前push的所有信息pop出来即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
    # call trap(tf), where tf=%esp
    call trap
 
    # pop the pushed stack pointer
    popl %esp
 
    # return falls through to trapret...
.globl __trapret
__trapret:
    # restore registers from stack
    popal
 
    # restore %ds, %es, %fs and %gs
    popl %gs
    popl %fs
    popl %es
    popl %ds
 
    # get rid of the trap number and error code
    addl $0x8, %esp
    iret

当然，倘若读者认为trapframe仅仅像这样中规中矩的实现信息的保存，那就太小看他了。我们发现，在调用call trap之后，有一句popl %esp，而后续恢复的信息完全是基于该%esp进行定位的，那么在中断处理内存中，如果我们强行修改%esp成为我们希望接下来运行的代码段的trap描述，那么经过__trapret代码恢复trapframe后，你就可以让程序跳转到任何你希望的地方。

比如下面代码就实现了内核态到用户态的切换。

1
2
3
4
5
6
7
8
9
10
11
12
    if (tf->tf_cs == KERNEL_CS) {                                                                                              
        cprintf("T_SWITH_TOU\n");                                                                                              
        userframe =  *tf;                                                                                                      
        userframe.tf_cs = USER_CS;                                                                                            
        userframe.tf_ds = USER_DS;                                                                                            
        userframe.tf_es = USER_DS;                                                                                            
        userframe.tf_ss = USER_DS;                                                                                            
        //userframe.tf_fs = USER_DS;                                                                                          
        userframe.tf_eflags |= FL_IOPL_MASK;                                                                                  
        userframe.tf_esp = (uint32_t)tf + sizeof(struct trapframe) - 8;                                                        
        *((uint32_t *)tf - 1) = (uint32_t)&userframe;                                                                    
    }

其中*((uint32_t *)tf - 1)这个位置的值就是之后popl %esp恢复的%esp的值。

进程切换中CONTEXT的作用

context的结构体定义如下，可以看到，其中储存了所有的用户寄存器的值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// Saved registers for kernel context switches.                                                                                    
// Don't need to save all the %fs etc. segment registers,                                                                          
// because they are constant across kernel contexts.                                                                              
// Save all the regular registers so we don't need to care                                                                        
// which are caller save, but not the return register %eax.                                                                        
// (Not saving %eax just simplifies the switching code.)                                                                          
// The layout of context must match code in switch.S.                                                                              
struct context {                                                                                                                  
    uint32_t eip;                                                                                                                  
    uint32_t esp;                                                                                                                  
    uint32_t ebx;                                                                                                                  
    uint32_t ecx;                                                                                                                  
    uint32_t edx;                                                                                                                  
    uint32_t esi;                                                                                                                  
    uint32_t edi;                                                                                                                  
    uint32_t ebp;                                                                                                                  
};                    

context结构体干的事情也很简单，可以用switch_to函数囊括，即保存一系列寄存器，并恢复一系列寄存器。在C++中，switch_to是拥有两个context结构体为参数的函数switch_to(&(prev->context), &(next->context)); ，其实现如下——

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
switch_to:                      # switch_to(from, to)
 
    # save from's registers
    movl 4(%esp), %eax          # eax points to from
    popl 0(%eax)                # save eip !popl
    movl %esp, 4(%eax)          # save esp::context of from
    movl %ebx, 8(%eax)          # save ebx::context of from
    movl %ecx, 12(%eax)         # save ecx::context of from
    movl %edx, 16(%eax)         # save edx::context of from
    movl %esi, 20(%eax)         # save esi::context of from
    movl %edi, 24(%eax)         # save edi::context of from
    movl %ebp, 28(%eax)         # save ebp::context of from
 
    # restore to's registers
    movl 4(%esp), %eax          # not 8(%esp): popped return address already
                                # eax now points to to
    movl 28(%eax), %ebp         # restore ebp::context of to
    movl 24(%eax), %edi         # restore edi::context of to
    movl 20(%eax), %esi         # restore esi::context of to
    movl 16(%eax), %edx         # restore edx::context of to
    movl 12(%eax), %ecx         # restore ecx::context of to
    movl 8(%eax), %ebx          # restore ebx::context of to
    movl 4(%eax), %esp          # restore esp::context of to
 
    pushl 0(%eax)               # push eip
 
    ret

进程切换中TRAPFRAME的作用

那是不是进程的切换就可以直接用switch_to函数呢？答案是否定的，因为switch_to仅仅保存、恢复了普通寄存器，无法实现优先级跳转、段寄存器修改等等。这时，就要借助trapframe了。

由于switch_to函数跳转后，将调到context.eip位置。而这个跳转我们没法完全实现进程切换，所以我们可以将其设置为一个触发二级跳转的函数，forkret。

1
2
proc->context.eip = (uintptr_t)forkret;
proc->context.esp = (uintptr_t)(proc->tf);

其中，forkret定义如下（current是当前进程，也就是进程切换的目标进程），forkret不同于switch_to，它尝试使用trapframe作为进程切换的手段，而相比于context，trapframe的功能就强大多了。

1
2
3
4
static void
forkret(void) {
    forkrets(current->tf);
}

而forkrets定义如下——

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
.globl __trapret
__trapret:
    # restore registers from stack
    popal
 
    # restore %ds, %es, %fs and %gs
    popl %gs
    popl %fs
    popl %es
    popl %ds
 
    # get rid of the trap number and error code
    addl $0x8, %esp
    iret
 
.globl forkrets
forkrets:
    # set stack to this new process's trapframe
    movl 4(%esp), %esp
    jmp __trapret

现在，又回到了中断恢复的那一段代码，而其中的逻辑也完全相同。最终，进程跳转目标进程的入口，而该入口的地址，被存放在proc->tf中。下面是kernel_thread的trapframe初始化代码，也能佐证最终调用函数入口fn被储存在了eip中。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// kernel_thread - create a kernel thread using "fn" function                                                                      
// NOTE: the contents of temp trapframe tf will be copied to                                                                      
//       proc->tf in do_fork-->copy_thread function                                                                                
int                                                                                                                                
kernel_thread(int (*fn)(void *), void *arg, uint32_t clone_flags) {                                                                
     struct trapframe tf;                                                                                                          
     memset(&amp;tf, 0, sizeof(struct trapframe));                                                                                      
     tf.tf_cs = KERNEL_CS;                                                                                                          
     tf.tf_ds = tf.tf_es = tf.tf_ss = KERNEL_DS;                                                                                    
     tf.tf_regs.reg_ebx = (uint32_t)fn;                                                                                            
     tf.tf_regs.reg_edx = (uint32_t)arg;                                                                                            
     tf.tf_eip = (uint32_t)kernel_thread_entry;                                                                                    
     return do_fork(clone_flags | CLONE_VM, 0, &amp;tf);                                                                                
}                                                                                                                                  

浅析文本摘要算法（Document Summarization）

概述

文本摘要算法，指的是在一篇文章中，摘要出核心观点的算法。主流的文本摘要算法生成一篇文章的摘要，摘要长度在3~4句话左右。

历史

在深度学习算法出现之前，人们使用了贪心算法、图算法来研究文本摘要。同时，为了衡量一段生成的摘要是否和标准摘要（gold summary）相似，学术界提出了一系列标准，这些标准现在广泛用于文本摘要算法的模型评价，其中最为常用的就是ROUGE – A Package for Automatic Evaluation of Summarieszz中提到的ROUGE-x系列算法。

深度学习提出后，LSTM/GRU作为摘要生成的强有力工具，一举打破传统算法的效果。最为主流的摘要生成模型是基于抽取式和生成式的，这两种模型将在后面详述。

随着深度学习的发展，很多其他算法也被引入。如一些文章使用强化学习，直接尝试训练一个能够获得最高ROUGE得分的模型。一些文章借助机器视觉方向的研究，优化模型结构。也有文章训练模型，判断句子相对于文章的重要性，进而间接实现摘要提取。

抽取式和生成式文本摘要

不过既然是摘要，那么显然，摘要中很大一部分都应该是原文中出现过的词语。同时，基于语法的考虑，也需要引入一些没有在原文中出现的词。

这时，就引出了文本摘要算法的两大学派—— 抽取式(extractive)和生成式(abstractive)。

  • extractive算法希望直接从文本中，抽出若干词语，连成一句话。词汇的抽取通常使用循环神经网络，配合注意力机制。得到“下一个词”可能是谁的概率分布。
  • abstractive算法希望从词汇表中，直接选出“下一个词”。

不论是abstractive的文本摘要，还是extractive的文本摘要，模型都由两个部分构成的，即一个编码器(encoder)和一个解码器(decoder)。

  • 对于编码器来说，通常都是将输入文本导入一个循环神经网络，生成出一个上下文特征向量c。
  • 对于解码器来说，通常也是使用一个循环神经网络。以编码器生成的表征原文的上下文特征向量c，和之前生成的词汇{y_1, y_2, \dots, y_t}，生成出摘要的下一个词y_t。

数据集

当前研究人员多使用CNN/DailyMail作为数据集，在该数据集中，每一组数据是一个新闻稿，平均每篇文章39句话。同时还有一个“多句”的摘要。

著名论文

Get To The Point: Summarization with Pointer-Generator Networks

这篇文章提出了一个Pointer-Generator模型，既可以通过Pointer拷贝原文的文字，也可以通过Generator生成不存在原文中的文本。这两个模型通过一个开关p_{gen}进行选择——

P(w) = p_{gen} P_{vocab}(w) + (1-p_{gen})\sum_{i:w_i=w} a_i^t

其中P_{vocab}表示从词汇表中选择一个单词的概率分布，而a_i则是从原文选择第i个词汇的概率分布。

在此基础上，本文还提出了一种称之为覆盖率机制(coverage mechanism)的方式，用以解决抽取式摘要中最容易出现的内容重复的问题。

SummaRuNNer: A Recurrent Neural Network based Sequence Model for Extractive Summarization of Documents

这篇文章核心目标是仅仅是在“句子级别”进行摘要，即从原文中选择若干适合作为摘要的句子。该文章使用两层GRU，依次在“词语”级别和“句子”级别总结信息，最终获得一个可以表征全局性质的向量d。接着，再参考句子级别的特征向量s_i、全局特征向量d、以及RNN的隐状态h_i，生成对于句子的评分。

Ranking Sentences for Extractive Summarization with Reinforcement Learning

这篇文章的核心目标是给一篇文章的句子按照与主题的相关度进行排序，文章指出，在之前的方法中，通常是训练模型，使得对于每一个句子的估价尽量靠近一个指定的ground-true。但提升对于ground-true的近似并不一定能够提高模型的ROUGE评分。因此，文章提出使用强化学习的方式，直接学习句子的label，进一步最大化ROUGE评分（注意，这里ROUGE评价指标是不可导的，因此才需要用到强化学习）。

Neural Document Summarization by Jointly Learning to Score and Select Sentences

这篇文章仍然是句子级别摘要的算法，其思想借鉴了MMR算法，在MMR算法中，借助一个建立在语句集合中的评分函数r(S)，迭代选择能够最大化加入后r(S')值的句子。即

g(S_i) = r(S_{t-1} \cap {S_i}) - r(S_{t-1})

而g(S_i)可以看做在选择了S_{t-1}后，第i篇文章S_i的评分。使用神经网络结构去学习g(S_i)即可实现——能够参考之前选取句子集合信息的语句选择算法。

BanditSum: Extractive Summarization as a Contextual Bandit

这篇文章也是借助强化学习尝试拟合文本的ROUGE得分，并且提出了新的结构用于防止摘要倾向于前面的句子。

Bottom-Up Abstractive Summarization

这篇文章与Pointer-Generator相似，不过为了解决前文中文本拷贝倾向于拷贝整句话的bug。在输入给Pointer-Generator模型之前，先给输入的文本加了一个mask，过滤掉其中一部分，这样就导致文本不再倾向于拷贝连续的内容。

DeepChannel: Salience Estimation by Contrastive Learning for Extractive Document Summarization

这篇文章训练模型，拟合P(D|S)，即给定摘要S，能够恢复原文D的概率。而函数P(D|S)的训练，可以借助文章D，摘要S，一句不重要的话S_2这三部分进行训练。生成P(D|S)后，再使用贪心算法构造摘要集合。

一句话解析最大边缘相关性算法(MMR, Maximal Marginal Relevance)

随着网络资源的丰富，找到和询问(query)最相关的一系列文本成为了学者们研究的问题。

之前的做法通常是直接计算逐个候选文本与询问的相关度。将前K大值对应的文档作为“最相关文档”输出出来。但是这种做法适用于那些候选文本集合较小，且只有少量文本与询问存在关联的情况。

但实际上，我们还有另一种场景，以搜索引擎为首的这类环境中，潜在的相关文档非常多，我们需要非常高的召回率(recall)，并且尽量降低结果的冗余性(redundance)。在这种情况下，MMR就有用武之地了。

实际上MMR的算法核心思想可以用一句话解释——

A document has high mariginal relevance if it is both relevant to the query and contains minimal similarity to previously selected documents.

一个文章拥有高边缘相关性(MMR)当且仅当它与询问相关性高，而且与之前已经选出来的文章集合相关性低。

而使用公式化的表达如下——

MMR \overset{def}{=} \underset{D_i \in R \backslash S}{Arg max} \left[ \lambda (Sim_1(D_i, Q) - (1-\lambda) \underset{D_j \in S}{max} Sim(D_i, D_j) \right]

其中，Q表示询问,D_i表示文档，S表示选择出来的相关文档集合，Sim表示任意一种文档相关性计算函数。

以上就是MMR的解释，MMR在文档摘要方面有很多应用。想要更细了解，可以参考文献 The Use of MMR, Diversity-Based Reranking for Reordering Documents and Producing Summaries

Learning Convolutional Neural Networks for Graphs

图卷积网络(Graph Convolutional Network)，顾名思义，就是把图像处理中的卷积层运用到图上，图卷积网络能够处理如下两类问题[1]——

  • 给定一系列图作为训练集，可以训练出一个函数，该函数能够对未知的图进行分类或回归。
  • 给一张很大的图，学习图的表示函数(representation)，并对于未知的图，推导出一些性质，诸如判断一个节点的类型，或是消失的边权等等。

回顾卷积神经网络，一个像素的特征值，来自于该层输入中，这个像素空间上临近点的像素特征。卷积神经网络的成功，从某种意义上来说，正式借助了这种隐含的空间特征。对于NLP也是同理

但是，对于大部分图而言，并没有这么好的特征可以利用，要将CNN迁移到图上面，需要解决这两个问题——

  • 找到一部分中间点，这些中间点将各自总结其邻域节点的特征。
  • 计算每个中间点临近图的正则化表示，即向量空间中的一个可以编码这个图的表示

定义术语

首先，需要定义图的节点的标号(labeling)和排名(ranking)。标号是一个给图上每个节点赋予一个权值的映射l(u)。而排序是将图上每一个节点权值从小到大排名后的排名映射r(u)。即满足对于任意u, v \in V，r(u)<r(v)当且仅当l(u)>l(v)。

倘若r(u)函数和l(u)函数都是单射的，那么使用r(u)对于图中的节点编号进行置换，可以得到A^l(G)。

上述定义其实是有道理的，假设l(u)是一个能够描述节点位置的函数，那么使用r(u)映射后的图G'可以用来当做一个图的标准化(Canonicalization)结构，这个结构能够用来比较两个图是否同构(Isomorphism)。

l(u)的最优化是NP的，但是可以构造出相对有效的l(u)——用距离“中心节点”的距离函数作为l(u)，这里的“中心节点”是Node Sequence Selection函数的结果。

算法流程

Node Sequence Selection

为了对图进行卷积操作，我们需要定义卷积的stride和width。实际的算法非常简单，既然我们假设了r(u)函数能够有效刻画节点空间位置，那么在按照r(u)排序后的节点序列中，使用一个width大小stride步长的滑动窗口就可以完成节点的选择了。

Neighborhood Assembly

这一个步骤，试图对于上一步得到的若干个节点，分别找到一个大小为k的领域，这里用了简单的广度优先搜索算法。

Graph Normalization

图的规范化操作使用上一步得到的中心节点及其领域，重新对于领域中的节点进行标号，进而通过标号的排名进行置换，此时的图就相对规范了。由于距离不是单射函数，所以文中引用了NAUTY的方法，对于同样距离的节点进行区分。

Convolutional Architecture

文中的模型能够同时处理点权和边权，仅需要改变CNN的stride参数即可，具体实现略

评价

  • 没有公开代码，可复现性存疑
  • 适合作为GCN的入门论文，但和现在主流的GCN不一样。

引用

  1. Niepert M, Ahmed M, Kutzkov K. Learning convolutional neural networks for graphs[C]//International conference on machine learning. 2016: 2014-2023.

云计算平台故障事件与相关研究

今年来，云计算平台发生了多起故障事件，而其原因的分析以及损失估计被很多学者所研究，本文将分别列举规模较大的云计算故障事件，并加以分析，同时对于学界对云计算研究成果做综述性摘要。

经典事件

阿里云停机事件

2019年3月3日，阿里巴巴旗下阿里云发布通报称，华北2地域可用区C部分ECS服务器(云服务器)等实例出现IO HANG(IO不响应)，经紧急排查处理后已全部恢复。在这一次事件中，华北相当多的互联网公司的App、网站全部瘫痪，大量程序员、运维晚上从被窝里面被拉回公司修复错误。

Amazon AWS宕机事件

2017年2月28号，一名亚马逊程序员在调试系统的时候，试图运行了一条脚本，以删除少量用于支持支付操作的服务器。但是他输错了命令，导致大量服务器被删。而被误删除的服务器集群中中，有两个非常重要的系统，一个是存放了该区域所有托管服务器的配置信息，用于处理所有GET, LIST, PUT 和 DELETE 请求的。另一个系统用于负责新服务器的分配。

为了修复这个错误，亚马逊不得不重启整个系统。对于数年没有重启过得系统，而重启系统后的完整性和安全检查耗费了非常多的时间。最终导致了震惊全球的Amazon S3宕机4个小时事件。

事后，亚马逊官方网站通告总结事件时，称整个事件的触发程序，是一个支持快速移除大量负载的命令，而我们已经将该命令进行修改，使得负载的移除更加缓慢，并且增加了足够的安全保障，当某个节点移除后，其对应的子系统剩余节点没有能力负载所有的访问，则该移除指令不会被执行。另一方面，亚马逊也修改了恢复系统，保障在将来错误发生时，恢复不再会花费那么多时间。

Azure服务器中断事件

在2012年2月28日，微软旗下的Azure云服务器发生中断，事件长达7小时，据微软官方网站通告，该中断是由于服务中一处关于闰年的计算失误导致的。问题发生后，工程师快速部署了修复代码，并在7小时候恢复了服务器的访问。

其他安全事件

对于云服务商来说，设备故障并不是唯一的灾难，安全性漏洞更为致命，在7 Most Infamous Cloud Security Breaches文章中写道，微软、Dropbox、LinkedIn、Apple iCloud、Yahoo都曾经经历过安全漏洞攻击。并产生了很大的损失。

相关研究

硬件故障是云计算平台故障中，一个非常古老的错误，有非常非常多的研究者对他进行过研究。随着云计算的发展和商业化，硬件故障所扮演的角色也在随之改变，在Wang et al. (2017)的研究中指出，这些变化有积极和消极的方面。
从积极的方面来讲，云服务商的硬件设备的质量越来越可靠，更完备的故障检测系统也被部署到了云计算平台上，从而使得故障的恢复更加高效。而且由于云计算已经是一门非常成熟的技术，面对故障，运维也有足够的经验。这一系列变化都会倾向于降低对故障事件的损失。
但是从消极的方面来讲，由于市场扩大，更多的服务商进驻云计算行业，使得运营商们更加注重成本。自然而然的，他们就会倾向于使用那些不那么可靠，但是便宜的设备。

在Lloyds ́ and AIR (2018)的研究中，对于云服务商的故障损失进行了估计，发现美国的云服务商停机3-6天对应损失可达69亿美元。其中，制造业和零售批发业首当其冲，而其中损失最严重的是财富1000强的企业。

为了控制由于云服务商故障导致的损失，催生出一个全新的保险行业，叫做网络保险(cyber-insurance)，这种保险以投保者的网站的可用性作为保险项目。不同于传统的保险，网络保险作为一个新兴的品种，仍没有被大众以及保险公司所接受，一方面是人们并没有正确的认识到服务商故障的损失，另一方面是网络保险有极大的系统性风险。一个云服务商的故障可能同时美国导致124万企业的经营遭受影响，此时大规模的赔偿可能会对保险公司带来巨大的流动性风险。

对于云服务的故障原因，文章Calvesbert (2018列举了四类原因：
1)环境原因，包括自然灾害在内的，无法认为控制的故障。
2)敌对攻击，主要包括竞争对手或黑客，尝试利用网络的漏洞进行攻击。
3)意外原因，指的是日常操作维护的误操作。
4)结构性故障，由于结构缺陷、资源耗尽而产生无法预知的错误。

当然，云平台的故障并不局限于大规模停机，频次更高的是局部性错误。在Chen et al. (2014)的研究中，将这类错误分类为应用错误、配置错误与云错误。配置错误是开发者认为错误配置、重复提交任务导致的，由于开发者在发现任务失败后倾向于重复提交，因此配置错误是所有故障中最多的。其次就是应用错误，其原因为云平台本身的资源限制、以及硬件错误。最后是云错误，其来源于运节点的添加、删除与维护。

总结

经过大规模的资源不可访问的问题的四种成因，意外原因和结构性故障居多，因为这两种成因比较难以估计，与之相反，敌对攻击和环境原因都会有非常完善的防范措施。因而在近现代的宕机事件中，并不常发生。同时可以发现，不同公司在事件后的翻译也不尽相同，这可以通过修复时间，以及事后事件成因分析看出。其中，亚马逊事件后，官方公布了详细的故障原因，以及改进措施，不仅给用户一个交代，也对我们的研究有很大帮助。反之另一些宕机事件，则官方没有公布调查结果，或是寥寥几句，给用户和研究者都带来 极大的困惑。

现有的研究从各个方面为降低云计算错误做了非常重要的贡献，包括损失估计，频率分析，原因总结等等。为云计算厂商优化平台算法，增加可靠性有非常积极的作用。

引用

  • AWSCloud. 2017. Summary of the Amazon S3 Service Disruption in the Northern Virginia (US-EAST-1) Region. (2017). https://aws.amazon.com/message/41926/.
  • Contel Bradford. 2018.7 Most Infamous Cloud Security Breaches.(2018).https://blog.storagecraft.com/7-infamous-cloud-security-breaches/.
  • Gian Calvesbert. 2018. Cloud Service Failure: 3 Things to Know. (2018). https://www.air-worldwide.com/Blog/Cloud-Service-Failure–3-Things-to-Know/.
  • Xin Chen, Charng-Da Lu, and Karthik Pattabiraman. 2014. Failure analysis of jobs in computeclouds: A google cluster case study. In2014 IEEE 25th International Symposium on SoftwareReliability Engineering. IEEE, 167–177.
  • Bill Laing. 2012. Windows Azure Service Disruption Update. (2012). https://azure.microsoft.com/en-us/blog/windows-azure-service-disruption-update/.
  • Lloyd ́s and AIR. 2018.Cloud Down: Impacts on the US economy. Technical Report.
  • G. Wang, L. Zhang, and W. Xu. 2017. What Can We Learn from Four Years of Data Center Hardware Failures?. In 2017 47th Annual IEEE/IFIP International Conference on Dependable Systems and Networks (DSN). 25–36. https://doi.org/10.1109/DSN.2017.26