mhy12345 – 只愿面朝大海，春暖花开

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定义如下——

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));

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结构体中。

.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

.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出来即可。

    # 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

# 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后，你就可以让程序跳转到任何你希望的地方。

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

    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;                                                                     
    }

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的结构体定义如下，可以看到，其中储存了所有的用户寄存器的值。

// 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;                                                                                                                  
};

// 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)); ，其实现如下——

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

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。

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

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

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

static void
forkret(void) {
    forkrets(current->tf);
}

static void

forkret(void) {

forkrets(current->tf);

}

而forkrets定义如下——

.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

.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中。

// 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);                                                                                
 }

// 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(&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, &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不一样。

引用

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都曾经经历过安全漏洞攻击。并产生了很大的损失。

总结

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

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

引用

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

FaceNet: A Unified Embedding for Face Recognition and Clustering 阅读笔记

简介

该论文试图去解决人脸识别的课题，人脸识别有三个研究方向，分别为

验证(verification)，用于判断两个图像是否为同一个人
识别(recognition)，用于识别一个图像是哪个人
聚类(clustering)，在一系列图片中，找到一个经常出现的人

通常的人脸识别算法流程是这样的——

先训练一个可以用于在训练集中分类的网络，然后将该网络的中间某一层输出（一般而言是一个作为瓶颈的向量）作为测试集的人脸特征向量。

1	先训练一个可以用于在训练集中分类的网络，然后将该网络的中间某一层输出（一般而言是一个作为瓶颈的向量）作为测试集的人脸特征向量。

与之相反，论文提出的模型，以直接生产特征向量为目标，也就是说，特征向量不再作为一个中间信息，而是一个模型实实在在优化的目标。论文中的这种损失函数称为Triplet Loss。

模型

我们希望构造函数 $f(x)$ ，将图片x映射到特征空间 $\mathbb{R}^d$ ，使得所有相同身份的人脸拥有较小的欧几里得距离，反之不同人脸的距离较大。在Triplet Loss的构造中，为了满足尺度的恒定，还额外规定 $f(x)$ 位于单位球体上，即 $|f(x)| = 1$

模型希望相同人脸特征距离近，不同人脸特征距离远，量化到数学公式上就是

$|f(x_i^a)-f(x_i^p)|^2 + \alpha < |f(x_i^a)-f(x_i^n)|^2$

其中 $x_i^a$ 为基准图片(anchor)， $x_i^p$ 为同一身份的不同图片(positive)， $x_i^n$ 为不同身份的不同图片(negative). 而 $\alpha$ 被称为TripletLoss的边缘距离(margin)

由于算力的原因，不能计算出所有可能的 $x_i^a$ ， $x_i^p$ ， $x_i^n$ 组合，即所有Triplet。因此，选择有代表性的Triplet是非常有必要的。一种非常暴力的做法是，找到上述不等式中前半部分的最大值以及后半部分的最小值，即 $argmax|f(x_i^a)-f(x_i^p)|^2$ 和 $argmin|f(x_i^a)-f(x_i^n)|^2$ ，他们的组合一定是优化的瓶颈部分。我们将他们作为Hard Triplet，单纯优化他们就可以较快收敛。

由于图片画质以及误标记等原因，全局的argmax和argmin表现并不好，不过将其改成mini-batch内部的argmax与argmin就好了。

从零开始编写并托管WordPress插件：NoBaidu抵制百度插件

最近被一篇称为《搜索引擎百度已死》的文章被刷屏了，笔者本身就非常不喜欢百度，趁放寒假没有事情干，琢磨这在自己的网站上写一个插件。当访问者从百度进入网站，则在页面顶部显示一段用户自定义的阻止标语。顺便搞清楚Wordpress插件的原理。

上图就是NoBaidu的一个截图，本文按照我的编写顺序，分为——

如何编写一个Wordpress插件
如何将编好的插件托管到云端

另外，插件的源代码在我的github中开源，读者可以对照理解。

如何编写一个wordpress插件

编写Wordpress插件的教程网上很多，我就不重新造轮子了，我自己是在如何开发一个WordPress如何开发一个WordPress插件这篇文章中学到的，其核心要义就是钩子函数——

在Wordpress渲染一个页面的时候，在很多关键位置设置钩子（比如页面渲染开头，渲染器启动后等位置），而插件可以自定义的在任何钩子上挂载自己的函数，这样当页面渲染到了指定位置时，插件可以做一些自己的事情。

add_filter('robots_txt', array($this, 'robots_txt_edit'), 10, 2);

1	add_filter('robots_txt', array($this, 'robots_txt_edit'), 10, 2);

比如下面代码就可以在robots.txt渲染时，运行 $this->robots_txt_edit 指定的插件处理模块。

而以NoBaidu插件为例，我们需要支持如下逻辑——

当普通用户访问时，检查用户的请求头的REFERER域是不是baidu域名下的URL
当用户来自百度时，注册一个钩子函数，在页面渲染开始时，加入一个固定在页面顶部的，包含了自定义文字的HTML元素。
当请求robots.txt时，返回禁止Baidu爬虫的robots文字

除此之外，还需要一些额外的代码，来保证我们的插件可以正常使用

在用户是管理员的时候，生成插件设置页面，在其中可以设置显示的自定义抵制文字，用户选择是否组织百度爬虫，以及抵制文字是显示在顶端还是页面中部等等…
编写插件安装、卸载时的逻辑，保证安装时初始化配置信息，卸载时删除配置信息，做到无残留

上述的逻辑，都集中到了下面的代码中，该代码使用一个类包裹了所有的函数（其作用类似于C++中的Namespace，用于最小化命名冲突）

&lt;?php  
/*
 * Plugin Name: No-baidu plugin
 * Plugin URI: http://mhy12345.xyz/no-baidu/
 * Description: 当访问者通过百度访问网站时，此插件将在页面的顶端，显示一段抵制信息.
 * Version: 1.1
 * Author: mhy12345
 * Author URI: http://mhy12345.xyz/no-baidu/
 * License: GPL
 * */
include 'no-baidu-options.php';
class NoBaiduPlugin
{
	protected static $instance;
	private $options;
	private function __construct() { //挂载钩子函数
		add_filter('robots_txt', array($this, 'robots_txt_edit'), 10, 2);
		add_action("wp_head", array($this, "no_baidu_main"));
		register_activation_hook( __FILE__, array($this, 'no_baidu_install'));
		register_deactivation_hook( __FILE__, array($this, 'no_baidu_remove'));
		$this->options = get_option('no_baidu_option', false);
	}
	public static function get_instance() { //单例模式
		if (null === self::$instance) {
			self::$instance = new self();
		}
		return self::$instance;
	}
	public function no_baidu_main(){ //判断是否显示抵制文字，并调用对应的文本生成代码
		if(stristr($_SERVER["HTTP_REFERER"],"www.baidu.com"))
		{
			if ($this->options['method'] == 0) {
				wp_enqueue_style( 'no_baidu_style', plugins_url( 'css/no-baidu-view-header.css', __FILE__ ));
				include "views/header.php";
			}
			else {
				wp_enqueue_style( 'no_baidu_style', plugins_url( 'css/no-baidu-view-page.css', __FILE__ ));
				include "views/page.php";
			}
		}
	}
	public function no_baidu_install() {  //插件安装时，进行默认设置
		$no_baidu_options = Array();
		$no_baidu_options['method'] = 0;
		$no_baidu_options['change_robots'] = 0;
		$no_baidu_options['warn_text'] = '我们发现您是通过百度找到这个页面的，不过我们并不推荐这么做，不妨考虑用其他搜索引擎。';
		add_option("no_baidu_option", $no_baidu_options);
	}
	public function no_baidu_remove() {  //插件卸载时，取消设置
		delete_option("no_baidu_option");
	}
	public function robots_txt_edit($output, $public) //修改robots.txt
	{
		if ($this->options['change_robots'] == 1) {
			$output .= "User-agent: baiduspider\nDisallow: /\n";
			$output .=  apply_filters('robots_txt_rewrite_footer', "\n\n\n\n# This robots.txt file was modified by No-baidu: https://wordpress.org/plugins/robotstxt-rewrite/\n");
		}
		return $output;
	}
}
$no_baidu_plugin = NoBaiduPlugin::get_instance();
if (is_admin()) include_once ('no-baidu-options.php'); //如果是管理员页面，生成Setting界面
?>

<?php

* Plugin Name: No-baidu plugin

* Plugin URI: http://mhy12345.xyz/no-baidu/

* Description: 当访问者通过百度访问网站时，此插件将在页面的顶端，显示一段抵制信息.

* Version: 1.1

* Author: mhy12345

* Author URI: http://mhy12345.xyz/no-baidu/

* License: GPL

* */

include 'no-baidu-options.php';

class NoBaiduPlugin

{

protected static $instance;

private $options;

private function __construct() { //挂载钩子函数

add_filter('robots_txt', array($this, 'robots_txt_edit'), 10, 2);

add_action("wp_head", array($this, "no_baidu_main"));

register_activation_hook( __FILE__, array($this, 'no_baidu_install'));

register_deactivation_hook( __FILE__, array($this, 'no_baidu_remove'));

$this->options = get_option('no_baidu_option', false);

}

public static function get_instance() { //单例模式

if (null === self::$instance) {

self::$instance = new self();

}

return self::$instance;

}

public function no_baidu_main(){ //判断是否显示抵制文字，并调用对应的文本生成代码

if(stristr($_SERVER["HTTP_REFERER"],"www.baidu.com"))

{

if ($this->options['method'] == 0) {

wp_enqueue_style( 'no_baidu_style', plugins_url( 'css/no-baidu-view-header.css', __FILE__ ));

include "views/header.php";

}

else {

wp_enqueue_style( 'no_baidu_style', plugins_url( 'css/no-baidu-view-page.css', __FILE__ ));

include "views/page.php";

}

public function no_baidu_install() { //插件安装时，进行默认设置

$no_baidu_options = Array();

$no_baidu_options['method'] = 0;

$no_baidu_options['change_robots'] = 0;

$no_baidu_options['warn_text'] = '我们发现您是通过百度找到这个页面的，不过我们并不推荐这么做，不妨考虑用其他搜索引擎。';

add_option("no_baidu_option", $no_baidu_options);

}

public function no_baidu_remove() { //插件卸载时，取消设置

delete_option("no_baidu_option");

}

public function robots_txt_edit($output, $public) //修改robots.txt

{

if ($this->options['change_robots'] == 1) {

$output .= "User-agent: baiduspider\nDisallow: /\n";

$output .= apply_filters('robots_txt_rewrite_footer', "\n\n\n\n# This robots.txt file was modified by No-baidu: https://wordpress.org/plugins/robotstxt-rewrite/\n");

}

return $output;

}

$no_baidu_plugin = NoBaiduPlugin::get_instance();

if (is_admin()) include_once ('no-baidu-options.php'); //如果是管理员页面，生成Setting界面

看懂了上面的代码，是不是觉得Wordpress编写插件非常简单? 上述代码中引用的其他php代码，大家可以在我的github中自行查阅。

将自己写好的插件托管到wordpress云端

在WordPress官网的Plugin目录最低端，有一个Add Your Plugin分区，这个分区详细介绍了该如何将你的Wordpress插件托管至wordpress.org，一般来说，读完上述的文章，你就已经能够自主把自己的插件丢到云端了。不过我准备从自己的经历出发，来大致讲一讲流程。

WordPress.org自己维护了一个svn仓库，最终会获得自己插件的专属仓库，你可以使用svn提供的版本控制，自行升级、修订等等。而想要获得自己插件的svn仓库，你就需要把自己的插件的最初版提交给官方审核。提交入口在这里。这里写几个提交的注意事项吧——

最重要的是要知道php没有命名空间之说，所以一切全局变量都应该防止冲突。一个比较取巧的做法就是像上文一样，将你自己的程序包裹在一个class里面，而class以自己的插件名称命名。（我就因为配置的class命名为MySettingClass被官方打回来了）
不要有额外的文件，之前写插件的时候，把网上别人插件的代码拷贝到了自己的目录，本来只是想照着抄一抄，结果忘删了，这个也被审核人发现了。
README.txt按照官方的标准格式写。

网站上面说的是7个工作日，结果我第一天晚上提交了初版的zip包，第二天早上就收到了审核者的邮件。按照要求修改了一些类名，并删除了无关文件后，我直接把zip包附在了回复中，第三天早上就拿到了通过的消息，并且获得了svn仓库的访问权限。开源社区真的非常强大👍

接下来就是上传仓库了，如果读者会使用git的话，就别自己去学svn了，照着官方指南走一遍，就完全学会了。和git的pull, add, commit, push, tag如出一辙。

当你的first commit上传到远程仓库，并且readme.txt没有什么问题的话，你应该是可以立即在插件商店中搜索到自己写的插件的。

到这里我们在wordpress上面第一个插件就做好啦！

如果你觉得本文有用的话，欢迎到我的github仓库Star或Contribute~

让我们一起抵制Baidu吧~

参考文章

【一个前人的代码】：http://ju.outofmemory.cn/entry/222836
【如何开发Wordpress插件】：https://www.wpdaxue.com/writing_a_plugin.html
【官方文档】：https://wordpress.org/plugins/developers/

Identity-Aware Convolutional Neural Network for Facial Expression Recognition 阅读笔记

这篇论文核心目标是提高人脸表情识别的精度。经典的表情识别算法，会将表情图片映射到特征空间(feature space)中的特征向量，而两个特征向量的欧几里得距离来衡量两个表情的相似度。

作者发现常规模型容易将“同一个人(indentity)”的特征向量放在一起而非“同一个表情(expression)”。这个问题表现在模型训练的时候，模型容易“偷偷”记录下训练数据中人物的面貌，并基于此进行判断。倘若随便换一个测试集，模型的准确度就有非常大的下降。（比如模型会记录下某黑人胖子A的吃惊的表情特征，但是之后测试集中，倘若是一个黑人瘦子B吃惊的表情，那么模型就不怎么容易判别出来了）

如下图，现有的模型的特征向量如图(a)所示依赖于人物，而作者的模型能挖掘和人物无关的表情特征，反映到特征空间中如图(b)所示。

文章提出的模型称为identity-aware convolutional neural network (IACNN) ，其核心思想是学习与表情有关(expression-related)的特征，并在同时，故意学习一个和人物有关(identity-related)的特征，后者虽然不利于网络的实际识别，但是却有利于让前者变得与身份无关(identity-invariant).

同时，该文章提出了一种距离的计算法则，能够让相似的表情的特征向量相距较近，而不相似的表情的特征向量相距较远。（不过这个计算法则感觉并不算亮点或是创新）

首先定义欧几里得距离作为接下来的距离公式——

$D(f^E(I_1), f^E(I_2)) = |f^E(I_1), f^E(I_2)|^2$

下面是一个自定义的损失函数公式——

$L^{exp}_{Contrastive} = \frac{z_i^E}{2} * D(f^E(I_{i, 1}), f^E(I_{i,2})) + \frac{1-z_i^E}{2} * max(0, \alpha^E - D(f^E(I_{i, 1}), f^E(I_{i,2})))$

这个公式看着很长，实际上非常简单，当两个图片属于同一个表情(exp)，那么 $z_i=1$ ，优化损失函数倾向于让他们的特征向量靠近；而倘若不属于同一个表情， $z_i=0$ ，优化损失函数倾向于让他们至少有 $\alpha^E$ 的距离。这个损失函数可以用于训练提取表情特征的网络 $f^E(x)$ 。顺便一提 $f^E$ 是一个基于CNN的网络。

与上面相似，我们也可以创造一个 $L^{ID}_{Contrastive}$ 专门用来训练提取身份特征的网络 $F^{ID}$

$L^{ID}_{Contrastive} = \frac{z_i^E}{2} * D(f^{ID}(I_{i, 1}), f^{ID}(I_{i,2})) + \frac{1-z_i^{ID}}{2} * max(0, \alpha^{ID} - D(f^{ID}(I_{i, 1}), f^{ID}(I_{i,2})))$

通过上述的网络 $f^{ID}$ 和 $f^E$ ，我们对于一个图片能够生成表情相关的特征 $FC_{exp}$ 和身份相关特征 $FC_{ID}$ ，令他们的组合特征为 $FC_{feat}$ .

使用 $FC_{feat}$ 进行预测，得到损失函数 $L^1_{softmax}$ 和 $L^2_{softmax}$ （1和2分别是两张图片），使用 $FC_{exp}$ 进行预测，得到 $L^{exp1}_{softmax}$ ， $L^{exp2}_{softmax}$ 。

最终损失函数如下

$L = \lambda_1 L^{ID}_{Contrastive} + \lambda_2 L^{Exp}_{Contrastive} + \lambda_3 L^1_{softmax}+ \lambda_4 L^2_{softmax}+ \lambda_5 L^{exp1}_{softmax}+ \lambda_6 L^{exp2}_{softmax}$

可以发现，优化损失函数 $L$ ，身份特征相关的信息倾向于聚集在 $FC_{ID}$ 中，从而使 $FC_{Exp}$ 的信息是纯粹的面部无关信息。那么最后测试集上，单纯使用 $FC_{Exp}$ 进行预测，就不会存在模型对于训练集人物过于依赖的问题了。