简介

从以往的实验中可以知道，神经网络中的深度是非常重要的，但是深度越深，网络就越难进行训练。存在Degradetion Problem：随着网络深度增加，训练集上的准确度可能会下降：

这说明并不是所有的网络结构都是好进行优化的。于是这篇论文提出了一种可以构建深层神经网络的结构：将原本的输入与一个浅层网络的输出相加作为最终的输出，然后将这样的结构进行堆叠。

和直接尝试让神经网络去拟合最终期望的函数不同，这里尝试让他去拟合一个残差映射。就好比本来希望得到的函数是$\mathcal{H}(x)$，这里我们让它去拟合一个$\mathcal{F}(x) = \mathcal{H}(x)-x$的映射，这样最终仍然可以得到原本的映射。我们假设这样可以得到相同的最终结果，并且这种结构更容易进行训练。

在极限情况下，可能identity是更优的，那么回是残差趋近于0，整个块就等同于一个非线性函数。在这里可以看做原本的堆叠之上添加了一些短路连接，但是短路连接并不会增加额外的参数和计算复杂度。所以可以认为ResNet最坏的结果只是增加了无用的层数，理论上不会使结果变得更差

论文作者在ImageNet的实验中得到了两个结论：

1. 利用残差连接的深度网络可以很好地进行优化，而直接进行堆叠的普通网络随着层数加深可能会难以收敛
2. 残差网络可以从额外的深度中获得提升，更深的网络可以得到更好地结果。

具体结构

对每一个基本块可以看成这样一个结构：

$\mathbf{y}=\mathcal{F}\left(\mathbf{x},\left\{W_{i}\right\}\right)+\mathbf{x}$

其中$\mathcal{F}\left(\mathbf{x},\left\{W_{i}\right\}\right)$代表的是要被学习的残差映射，后面是一个自映射，期中需要保证残差映射的结果和原本输入的维度是相同的，如果不相同的话，可以考虑通过一个线性的投影$W_{s}$使得维度可以match：

$\mathbf{y}=\mathcal{F}\left(\mathbf{x},\left\{W_{i}\right\}\right)+W_{s} \mathbf{x}$

$\mathcal{F}$的形式是很多样的，但是如果只采用一层Linear，那么实际上用不用这个结构是没区别的，一般的时候是使用一个多层的卷积层来作为残差连接。

代码实现

以下是基于pytorch做的复现，其中对应的网络结构如下所示：

两层的为BasicBlock，三层的为Bottleneck：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108

import torch
import torch.nn as nn

class BasicBlock(nn.Module):
    expansion = 1
    
    def __init__(self, input_channel, channel, stride):
        super(BasicBlock, self).__init__()
        
        self.downsample = lambda x: x
        if(input_channel != channel):
            self.downsample = nn.Sequential(
                nn.Conv2d(in_channels = input_channel, out_channels = channel, kernel_size = 1, stride = stride, bias = False),
                nn.BatchNorm2d(channel)
            )
        
        self.relu = nn.ReLU(inplace = True)
        
        self.convlayers = nn.Sequential(
            nn.Conv2d(in_channels = input_channel, out_channels = channel, kernel_size = 3, stride = stride, padding = 1, bias = False),
            nn.BatchNorm2d(channel),
            nn.ReLU(inplace = True),
            nn.Conv2d(in_channels = channel, out_channels = channel, kernel_size = 3, stride = 1, padding = 1, bias = False),
            nn.BatchNorm2d(channel)
        )
    def forward(self, x):
        out = self.downsample(x) + self.convlayers(x)
        out = self.relu(out)
        return out

class Bottleneck(nn.Module):
    expansion = 4
    
    def __init__(self, input_channel, channel, stride, expansion = 4):
        super(Bottleneck, self).__init__()
        self.expansion = expansion
        output_channel = channel * expansion
        
        self.downsample = lambda x: x
        if(input_channel != output_channel):
            self.downsample = nn.Sequential(
                nn.Conv2d(in_channels = input_channel, out_channels = output_channel, kernel_size = 1, stride = stride, bias = False),
                nn.BatchNorm2d(output_channel)
            )
        
        self.relu = nn.ReLU(inplace = True)
        
        self.convlayers = nn.Sequential(
            nn.Conv2d(in_channels = input_channel, out_channels = channel, kernel_size = 1, stride = 1, bias = False),
            nn.BatchNorm2d(channel),
            nn.ReLU(inplace = True),
            nn.Conv2d(in_channels = channel, out_channels = channel, kernel_size = 3, stride = stride, padding = 1, bias = False),
            nn.BatchNorm2d(channel),
            nn.ReLU(inplace = True),
            nn.Conv2d(in_channels = channel, out_channels = output_channel, kernel_size = 1, stride = 1, bias = False),
            nn.BatchNorm2d(output_channel)
        )
    def forward(self, x):
        out = self.downsample(x) + self.convlayers(x)
        out = self.relu(out)
        return out
    
    
class ResNet(nn.Module):
    def __init__(self, block, block_nums, input_channel, class_num):
        super(ResNet, self).__init__()
        
        self.stacklayers = nn.Sequential(
            nn.Conv2d(in_channels = input_channel, out_channels = 64, kernel_size = 7, stride = 2, padding = 3, bias = False),
            nn.BatchNorm2d(64),
            nn.ReLU(inplace = True),
            nn.MaxPool2d(kernel_size = 3, stride = 2),
            self.make_layers(block = block, input_channel = 64, channel = 64, stride = 1, block_num = block_nums[0]),
            self.make_layers(block = block, input_channel = 64 * block.expansion, channel = 128, stride = 2, block_num = block_nums[1]),
            self.make_layers(block = block, input_channel = 128 * block.expansion, channel = 256, stride = 2, block_num = block_nums[2]),
            self.make_layers(block = block, input_channel = 256 * block.expansion, channel = 512, stride = 2, block_num = block_nums[3]),
            nn.AdaptiveAvgPool2d(1),
            nn.Flatten(),
            nn.Linear(512*block.expansion, class_num)
        )
    
    def make_layers(self, block, input_channel, channel, stride, block_num, expansion = 4, reduction = 16):
        layers = []
        layers.append(block(input_channel, channel, stride))
        input_channel = channel * block.expansion
        for _ in range(1, block_num):
            layers.append(block(input_channel, channel, 1))
        return nn.Sequential(*layers)
    
    def forward(self, x):
        out = self.stacklayers(x)
        return out
    
def ResNet_18(input_channel, class_num = 1000):
    return ResNet(BasicBlock, [2,2,2,2], input_channel, class_num)

def ResNet_34(input_channel, class_num = 1000):
    return ResNet(BasicBlock, [3,4,6,3], input_channel, class_num)

def ResNet_50(input_channel, class_num = 1000):
    return ResNet(Bottleneck, [3,4,6,3], input_channel, class_num)

def ResNet_101(input_channel, class_num = 1000):
    return ResNet(Bottleneck, [3,4,23,3], input_channel, class_num)

def ResNet_152(input_channel, class_num = 1000):
    return ResNet(Bottleneck, [3,8,36,3], input_channel, class_num)
   

Gumbel-Softmax Distribution

考虑$z$是一个定类型的变量，对于每个类型有着概率$\pi_1,\pi_2,\ldots,\pi_k$。考虑到从这个概率分布中的采样可以用一个onehot向量来表示，当数据量很大的时候满足：

$\mathbb{E}_p[z]=[\pi_1,\ldots,\pi_k]$

Gumbel-Max trick 提供了一个简单且高效的来对符合$\pi$这样概率分布的$z$进行采样的方法：

$z = \text{onehot} \left(\arg \max_i [g_i+\log \pi_i]\right)$

其中$g_i$是从Gumbel(0,1)中独立采出的，它可以利用Uniform(0,1)中的采样来计算得到：

$\begin{aligned} u &\sim \text{Uniform}(0,1) \\ g &= -\log(-\log(u)). \end{aligned}$

之后利用softmax来获得一个连续可导对argmax的估计

$\begin{aligned} y_{i}=\frac {\exp \left(\left(\log \left(\pi_{i}\right)+g_{i}\right) / \tau\right)} {\sum_{j=1}^{k} \exp \left(\left(\log \left(\pi_{j}\right)+g_{j}\right) / \tau\right)}\quad \text{for} \ i=1, \ldots, k \end{aligned}$

Gumbel-Softmax分布的概率密度如下表是：

$p_{\pi, \tau}\left(y_{1}, \ldots, y_{k}\right)=\Gamma(k) \tau^{k-1}\left(\sum_{i=1}^{k} \pi_{i} / y_{i}^{\tau}\right)^{-k} \prod_{i=1}^{k}\left(\pi_{i} / y_{i}^{\tau+1}\right)$

可以知道对于温度$\tau$而言，越接近于零，那么从Gumbel-Softmax分布中的采样就越接近onehot并且Gumbel-Softmax分布同原始的分布$p(z)$也更加的相似。

Gumbel-Softmax Estimator

可以发现对于任意的$\tau>0$，Gumbel-Softmax分布都是光滑的，可以求出偏导数$\partial y / \partial \pi$对参数$\pi$。于是用Gumbel-Softmax采样来代替原有的分类采样，就可以利用反向传播来计算梯度了。

对于学习过程中来说，实际上存在一个tradeoff。当$\tau$较小的时候，得到的sample比较接近onehot但是梯度的方差很大，当$\tau$较大的时候，梯度的方差比较小但是得到的sample更平滑。在实际的操作中，我们通常从一个较高的$\tau$开始，然后逐渐退火到一个很小的$\tau$。事实上，对于很多种的退火方法，结果都表现的不错。

Straight-Through Gumbel-Softmax Estimator

对于有些任务需要严格的将其限制为得到的就是离散的值，那么这个时候可以考虑对于$y$来做一个arg max得到$z$，在反向传播的时候利用$\nabla_\theta z \approx \nabla_\theta y$来进行梯度的估计。

即通过离散的方式进行采样，但是从连续的路径进行求导。这个叫做ST Gumbel-Softmax estimator，可以知道，当温度$\tau$较高的时候，这依然可以采样得到离散的采样值。

Related Work

主要总结了一些随机神经网络训练的方法，进行了一个对比。

上图中

1. 正常的无随机节点的梯度下降
2. 存在随机节点的时候，梯度在这个地方不能很好地进行反传
3. 采用log trick绕开随机节点传递梯度
4. 估计梯度进行传播，例如前文提到的ST Estimator
5. 采用重参数化方法，就是这里的Gumbel-Softmax Estimator

Semi-Supervised Generative Models

对于重参数化和log trick就不再多说，这里看一个半监督生成模型的推断。

考虑到一个半监督网络，从带标签数据$(x,y)\sim\mathcal{D}_L$和不带标签数据$x\sim \mathcal{D}_U$中进行学习。

有一个分辨网络（D）$q_\phi(y|x)$，一个推断网络（I）$q_\phi(z|x,y)$，和一个生成网络（G）$p_\theta(x|y,z)$，通过最大化生成网络输出的log似然的变分下界来进训练。

对于带标签的数据，y是观测到的结果，所以变分下界如下：

$\begin{aligned} \log p_\theta(x,y) &\ge \mathcal{L}(x,y)\\ &= \mathbb{E}_{z \sim q_\phi(z|x,y)}[\log p_\theta(x|y,z)] - KL[q_\phi(z|x,y)||p_\theta(y)p(z)] \end{aligned}$

对于无标签数据，重点在于对于离散的分布没有办法进行重参数化，所以这里采用的方法是对于margin out所有类别的y，同样是在$q_\phi(z|x,y)$上面进行推断，得到的变分下界如下所示（有一说一我推的和论文不一样，但我觉得论文里面的公式写错了）：

$\begin{aligned}\log p_{\theta}(x) &\geq\mathcal{U}(x) \\&=\mathbb{E}_{z \sim q_{\phi}(y, z | x)}\left[\log p_{\theta}(x | y, z)+\log p_{\theta}(y)+\log p(z)-\log q_{\phi}(y, z | x)\right] \\&=\mathbb{E}_{z \sim q_{\phi}(y, z | x)}\left[\log p_{\theta}(x | y, z)-\log \frac{q_\phi(z|x,y)}{p_{\theta}(y) p(z)} + \log \frac{q_\phi(z|x,y)}{q_\phi(y,z|x)}\right]\\&=\mathbb{E}_{z \sim q_{\phi}(y, z | x)}\left[\log p_{\theta}(x | y, z)-\log \frac{q_\phi(z|x,y)}{p_{\theta}(y) p(z)} + \log \frac{1}{q_\phi(y|x)}\right]\\&=\sum_{y} q_\phi(y|x)\mathbb{E}_{z \sim q_{\phi}(z | x,y)}\left[\log p_{\theta}(x | y, z)-\log \frac{q_\phi(z|x,y)}{p_{\theta}(y) p(z)} + \log \frac{1}{q_\phi(y|x)}\right]\\&=\sum_{y} q_\phi(y|x)\mathbb{E}_{z \sim q_{\phi}(z | x,y)}\left[\log p_{\theta}(x | y, z)-\log \frac{q_\phi(z|x,y)}{p_{\theta}(y) p(z)}\right] + \sum_{y} q_\phi(y|x)\log \frac{1}{q_\phi(y|x)}\\&=\sum_{y} q_{\phi}(y | x)\mathcal{L}(x, y)+\mathcal{H}\left(q_{\phi}(y | x)\right)\end{aligned}$

最终得到的最大化目标为下面这个式子：

$\mathcal{J}=\mathbb{E}_{(x, y) \sim \mathcal{D}_{L}}[\mathcal{L}(x, y)]+\mathbb{E}_{x \sim \mathcal{D}_{U}}[\mathcal{U}(x)]+\alpha \cdot \mathbb{E}_{(x, y) \sim \mathcal{D}_{L}}\left[\log q_{\phi}(y | x)\right]$

容易发现，前两项一个是针对带标签数据的变分下界最大化，一个是针对无标签数据的最大化，最后一项代表分辨网络的对数似然，其中$\alpha$参数越大，说明越看重分辨网络的能力。是一个在分辨网络和生成网络之间进行tradeoff的参数。

对于这种方法，假设要margin out一共k个类别，那么对每个前向/反向步需要$\mathcal{O}(D+k(I+G))$，但是采用Gumbel-Softmax方法进行重参数化，就可以直接进行反向传播而不需要margin out，时间复杂度降低到了$\mathcal{O}(D+I+G)$，在类别很多的情况下可以有效降低训练的时间复杂度！

准备面试的时候找到了两套C++面试题，做了一下，解答直接写在上面了，放在这里分享出来。感觉难度并不是很高，这是第二套~

A. Show me the code

1. Please create a “String” class to process char strings. This string class should satisfy the following requirements:

• It could be used as an original type like “int” to define variables and support assignment and copy.
• It could be used as the parameter type of a function and the return value type of a function.
• It could be used as the element type of the STL container, e.g., vector/list/deque.

In other words, your “String” class could be used in the following code and be complied successfully by a standard C++ compiler.

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

void foo(String x)
{
}
void bar(const String& x)
{
}
String baz()
{
  String ret("world");
  return ret;
}
int main()
{
  String s0;
  String s1("hello");
  String s2(s0);
  String s3 = s1;
  s2 = s1;
  foo(s1);
  bar(s1);
  foo("temporary");
  bar("temporary");
  String s4 = baz();
  std::vector<String> svec;
  svec.push_back(s0);
  svec.push_back(s1);
  svec.push_back(baz());
  svec.push_back("good job");
}

略，感觉以前写过。

2. Imagine we have a single linked list, please write a function which could remove a specified node in the list.

• Please define the data structure for the list as you need.
• Pass the head pointer to the function.
• Pass the pointer to the node to be removed to the function. Remove the node in the list if it has the same pointer value.

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

struct ListNode{
  int val;
  ListNode* next;
  ListNode(int _val): val(_val){}
};

ListNode* deleteNode(ListNode* head, int val)
{
  if(!head)
    return NULL;
  while(head->val == val)
  {
    head = head->next;
  }
  if(!head)
    return NULL;
  ListNode* pnode = head->next;
  ListNode* prev = head;
  while(pnode)
  {
    if(pnode->val == val)
    {
      prev->next = pnode->next;
      pnode = pnode->next;
    }
    else
    {
      prev = pnode;
      pnode = pnode->next;
    }
  }
  return head;
}

B. Basic Part

1. What are wrong in the following code? Please point out.

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

void main()
{
  char a = 'a';
  int b = 0;
  int *pInt1 = &b;
  int c = *pInt1;
  pInt1 = (int*)(&a);
  int *pInt2 = pInt1 + 1;
  int d = *pInt2;
  void *pV = &a;
  // char * pV = &a;
  pV++;	// 对空指针不能最算术运算
  char e = *pV;
}

2. What are wrong in the following code? Please provide your FIX.

Common.h

1
2
3
4
5

int var1;
void foo(int input)
{
  // some code
}

TestA.h

1
2
3
4
5
6
7
8

#include "Common.h"
#include "TestB.h"

class CTestA
{
  private:
    CTestB m_b;
};

TestB.h

1
2
3
4
5
6
7
8

#include "Common.h"
#include "TestA.h"

class CTestB
{
  private:
    CTestA m_a;
};

TestA.cpp

1
2

#include "TestA.h"
// some code

TestB.cpp

1
2

#include "TestB.h"
// some code

提前声明，结构体内部都采用指针而不是实体。

C. STL

1. Errors, inefficiency and potential bugs exsit in the following code, please point them out.

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

int foo(std::map<int, int>& mapIn, std::set<int>& setIn)
{
  std::vector<int> va(10);
  std::vector<int> vb;
  std::copy(va.begin(), va.end(), vb.begin());
  
  //std::vector<int> vb(va);
  
  std::vector<int> vc(100);
  auto iter = va.begin() + 5;
  int varInt = *iter;
  va.push_back(vc.begin(), vc.end());
  varInt = *(++iter);
  if (mapIn[4] == 0)
  {
    // do something 
  }
  auto itVec = std::find(vc.begin(), vc.end(), 100);
  if (itVec != vc.end())
  {
    // do something
  }
  
  //auto itSet = setIn.find(10);
  //Set本来就是有序的结构，利用可以进行二分查找，效率更高
  
  auto itSet = std::find(setIn.begin(), setIn.end(), 10);
  if (itSet == setIn.end())
  {
    // do something
  }
}

2. Please see the following code, TypeA could be either a function pointer or a functor, please try to provide the definition for TypeA in both function pointer way and functor way.

1
2
3
4
5
6

void foo(TypeA processor)
{
  int paraInt = 0;
  const char* pParaStr = "Test";
  int rtn = processor(paraInt, pParaStr);
}

函数指针:

1
2
3
4
5

int function_pointer(int pInt, const char* pStr)
{
		//do something
  	return 0;
} 

函数对象：

1
2
3
4
5
6
7

class functor{
public:
    int operator ()(int pInt, const char * pStr){
				// do something
        return 0;
    }  
};

准备面试的时候找到了两套C++面试题，做了一下，解答直接写在上面了，放在这里分享出来。感觉难度并不是很高，这是第一套~

For your answers, either Chinese or English are OK.

A. Coding

1. Please create a class to represent Int. Only declaration is required. Please give the declaration of all member functions, friend functions, and member variables.

略

2. Imagine we have a single linked list, please write a function which could move a specified node to the tail of the list.

• Please define the data structure for the list as you need.
• Pass the head pointer to the function.
• Pass the pointer of the node to be moved to the function. Move the node to the tail of the list if it has the same pointer value.

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

struct ListNode{
  int val;
  ListNode* next;
  ListNode(int _val): val(_val){}
};

ListNode* deleteNode(ListNode* head, int val)
{
  if(!head)
    return NULL;
  while(head->val == val)
  {
    head = head->next;
  }
  if(!head)
    return NULL;
  ListNode* pnode = head->next;
  ListNode* prev = head;
  while(pnode)
  {
    if(pnode->val == val)
    {
      prev->next = pnode->next;
      pnode = pnode->next;
    }
    else
    {
      prev = pnode;
      pnode = pnode->next;
    }
  }
  return head;
}

B. Read and Answer

1. What are wrong in the following code?

1
2
3
4
5
6
7
8

void foo(short startIndex)
{  
  short buffer[50000] = { 0 };
  for (auto i = startIndex; i < 40000; ++i) 
  {  
    buffer[i] = (char)i;  
  }
}

Because i is short, i < 40000 is always True, the loop NEVER ends.

2. Mark all lines which are wrong and provide the FIX.

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

class CBase
{
public:
    CBase() 
      : m_pVar1(NULL)
    {
        m_pVar2 = new int(4);
    }
    ~CBase()
    {
        delete m_pVar2;
        delete m_pVar1;	// Can't delete NULL pointer
      /*
      *if(! m_pVar1)
      *  delete m_pVal1;
      */
    }
    void Init(int* pVar)
    {
        m_pVar1 = pVar;
    }
private:
    int* m_pVar1;
    int* m_pVar2;
}
class CDerive : public CBase
{
public:
    CDerive(int var) : m_var(var) {};
  //CDerive(){}
    ~CDerive() {};
private:
    int m_var;
}
int main()
{
    CDerive* pDerives = new CDerive[10]; // can't init
    int *pVar = new int(10);
    for (int i = 0; i < 10; ++i)
    {
        pDerive[i].Init(pVar);
    }
    delete pDerives;	// pDerives is an array
  //delete[] pDerives;
    delete pVar;
}

3. The following code could not be compiled, give TWO ways to fix it.

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

class CFoo
{
public:
    CFoo() : m_var(0) {};
    ~CFoo() {};
    bool AddAndCheck() const
    {
        m_var += 5;
        return m_var < 10;
    }
private:
    int m_var;
};

第一种：丢掉const

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

class CFoo
{
public:
    CFoo() : m_var(0) {};
    ~CFoo() {};
    bool AddAndCheck()// drop the const
    {
        m_var += 5;
        return m_var < 10;
    }
private:
    int m_var;
};

第二种：加上mutable

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

class CFoo
{
public:
    CFoo() : m_var(0) {};
    ~CFoo() {};
    bool AddAndCheck() const
    {
        m_var += 5;
        return m_var < 10;
    }
private:
    mutable int m_var;
};

4. What are wrong in the following code? Provide your fix.

1
2
3
4
5
6
7
8

#define INCREASE(a) ++a 
// #define INCREASE(a) a+1
void foo()
{
    int a = 3;
    int b = 7;
    cout<<INCREASE(a * b)<<endl; // 等价于(++a) * b
}

5. What are wrong in the following code? Why?

1
2
3
4
5

char* GetStaticBuffer()
{
    char buffer[100] = { 0 };
    return buffer;
}

buffer在栈上分配的，返回之后释放了。

6. With default configuration, in the following code, function fooA is OK but fooB has issues, why?

1
2
3
4
5
6
7
8
9

const int TEN_MEGA_BYTES = 10 * 1024 * 1024;
void fooA()
{
    char *pBuffer = new char[TEN_MEGA_BYTES];
}
void fooB()
{
    char buffer[TEN_MEGA_BYTES] = { 0 };
}

fooA()在堆上进行分配，fooB()在栈上进行分配，栈小，会爆。

7. In the following code, line 32, I want to give “student_teacher” as the input parameter, but by mistake, I typed “student”. The compiling succeeded anyway. Why? If I want the compiling be failed in this condition, how to do?

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

class CStudent
{
public:
    CStudent() {};
    ~CStudent() {};
};

class CTeacher
{
public:
    CTeacher() {};
  // delete this part------------
    CTeacher(CStudent student)
        : m_student(student)
    {
    }
    ~CTeacher() {};
  // end here -------------------
    void Teach() {};
private:
    CStudent m_student;
};

void foo(CTeacher teacher)
{
    teacher.Teach();
}
int main()
{
    CStudent student;
    CTeacher student_teacher;
    foo(student);
}

8. What is the output of the following code?

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

int fooVar = 10;
void foo(int *pVar, int& var)
{
    pVar = &fooVar;
    var = fooVar;
}
int main()
{
    int var1 = 1;
    int var2 = 2;
    foo(&var1, var2);
    cout<<var1<<":"<<var2<<endl;
}

1:10

9. How to run some code before main function is called?

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

int code_before_main()
{
    cout<<"code before main()"<<endl;
    return 0;
}

int useless = code_before_main();

int main()
{
    cout<<"main() start"<<endl;
}

10. What the difference are between

std::vector::resize() and std::vector::reserve()

std::vector::size() and std::vector::capacity()

size()对应的是有效空间，而capacity()对应的是实际空间。

resize()调整的是有效空间的大小，reserve()调整的是实际空间大小。

11. Template greater<> is often used when operating the STL containers. Please give an implementation of greater<>.

Hints: Two template parameters. One is a number to be compared as base, another is the element to be compared.

1
2
3
4
5

template <class T> 
struct greater{
  bool operator() (const T& x, const T& y) const 
  	{return x>y;}
};

12. Say we have a class named Printer which has a member function as Print(). Now there’s a container as vector. Please give a lambda expression which could be used in for_each() to call Print() function for every instance in vector.

1

for_each(v.begin(), v.end(), [](const T& n) { Printer().Print(n); });

2019

无所得

有所失

先回顾一下全贝叶斯推断：

训练阶段：

$p(\theta|X_{tr},Y_{tr}) =\frac{p(Y_{tr}|X_{tr},\theta)p(\theta)}{\color{red}{\int p(Y_{tr}|X_{tr},\theta)p(\theta) d\theta}}$

测试阶段：

$p(y|x,X_{tr},Y_{tr}) =\color{red}{\int p(y|x,\theta) p(\theta|X_{tr},Y_{tr})d\theta }$

红色分布难以计算，使得后验分布只有在面对简单的共轭模型才能被精确求解

Approximate inference

概率模型：$p(x,\theta)=p(x|\theta)p(\theta)$

变分推断（Variational Inference）：

采用一个简单的分布来近似后验：$p(\theta|x)\approx q(\theta)\in \mathcal{Q}$

• 有偏的
• 高效并且可拓展

蒙特卡洛方法（MCMC）：

从没有标准化的$p(\theta|x)$里面进行采样（因为下面归一化的部分难以计算）：

• 无偏的
• 需要很多的采样才能近似

Variational inference

$\begin{aligned} \log p(x) &= \int q(\theta)\log p(x) d\theta =\int q(\theta)\log \frac{p(x,\theta)}{p(\theta|x)}d\theta\\ &=\int q(\theta)\log \frac{p(x,\theta)q(\theta)}{p(\theta|x)q(\theta)}d\theta\\ &=\int q(\theta)\log \frac{p(x,\theta)}{q(\theta)}d\theta + \int q(\theta)\log\frac{q(\theta)}{p(\theta|x)}d\theta\\ &=\color{green}{\mathcal{L}(q(\theta))}+ \color{red}{KL(q(\theta)||p(\theta|x))} \end{aligned}$

前面的绿色部分是ELBO(Evidence lower bound)

后面的红色部分是用于变分推断的KL散度，KL散度越小，说明我们的估计与后验分布越接近

但是后验分布是未知的，否则就不需要求解了，再看一遍上面这个公式：

$\log p(x) = \mathcal{L}(q(\theta)) + KL(q(\theta)||p(\theta|x))$

可以发现前面$\log p(x)$与$q(\theta)$是没有关系的，那么要最小化KL散度，实际上就相当于最大化ELBO：

$KL(q(\theta)||p(\theta|x))\rightarrow\min_{q(\theta)\in \mathcal{Q}} \quad \Leftrightarrow \quad \mathcal{L}(q(\theta))\rightarrow\max_{q(\theta)\in\mathcal{Q}}$

改写一遍变分下界：

$\begin{aligned}\mathcal{L}(q(\theta))&=\int q(\theta)\log\frac{p(x,\theta)}{q(\theta)}d\theta\\ &=\int q(\theta)\log\frac{p(x|\theta)p(\theta)}{q(\theta)}d\theta\\ &= \color{green}{\mathbb{E}_{q(\theta)}\log p(x|\theta) } - \color{red}{KL(q(\theta)||p(\theta))} \end{aligned}$

前面绿色的为数据项，后面红色的为正则项

最终的优化问题就在于：

$\mathcal{L}(q(\theta)) = \int q(\theta) \log \frac{p(x,\theta)}{q(\theta)}d\theta \quad \rightarrow \quad \max_{q(\theta)\in \mathcal{Q}}$

问题的关键是，怎么对于一个概率分布进行最优化

Mean Field Variational Inference

Mean Field Approximation

$\mathcal{L}(q(\theta)) = \int q(\theta)\log \frac{p(x,\theta)}{q(\theta)}d\theta \quad \rightarrow \quad \max_{q(\theta)=q_1(\theta_1)\cdot \ldots \cdot q_m(\theta_m)}$

块坐标上升法（Block coordinate assent）:

每次都固定除了一个维度分布其他的部分$\{q_i(\theta_i)\}_{i\ne j}$，然后对一个维度上的分布进行优化

$\mathcal{L}(q(\theta)) \quad \rightarrow \quad \max_{q_j(\theta_j)}$

由于除了$q_j(\theta_j)$其他维度都是固定的，可以得到如下的数学推导：

$\begin{aligned} \mathcal{L}(q(\theta)) &=\int q(\theta)\log \frac{p(x,\theta)}{q(\theta)}\\ &=\mathbb{E}_{q(\theta)}\log p(x,\theta) - \mathbb{E}_{q(\theta)}\log q(\theta)\\ &=\mathbb{E}_{q(\theta)}\log p(x,\theta) - \sum_{k=1}^m \mathbb{E}_{q_k(\theta_k)}\log q_k(\theta_k)\\ &=\mathbb{E}_{q_j(\theta_j)}\left[\mathbb{E}_{q_{i\ne j}}\log p(x,\theta)\right] - \mathbb{E}_{q_j(\theta_j)}\log q_j(\theta_j)+Const\\ &\left\{r_j(\theta_j) = \frac{1}{Z_j} \exp\left(\mathbb{E}_{q_{i\ne j}}\log p(x,\theta)\right)\right\}\\ &=\mathbb{E}_{q_j(\theta_j)} \log \frac{r_j(\theta_j)}{q_j(\theta_j)}+Const\\ &=-KL\left(q_j(\theta_j)||r_j(\theta_j)\right)+Const \end{aligned}$

在块坐标下降中的每一步优化问题转化为了：

$\mathcal{L}(q(\theta)) = -KL(q_j(\theta_j)||r_j(\theta_j)) + Const \quad \rightarrow \quad \max_{q_j(\theta_j)}$

实际上就是要最小化KL散度，容易发现解为：

$q_j(\theta_j) = r_j(\theta_j) =\frac{1}{Z_j} \exp\left(\mathbb{E}_{q_{i\ne j}}\log p(x,\theta)\right)$

Parametric variational inference

考虑对于变分分布的参数族：

$q(\theta) = q(\theta|\lambda)$

限制在于，我们选择了一族固定的分布形式：

• 如果选择的形式过于简单，我们可能不能有效地建模数据
• 如果选择的形式足够复杂，我们不能保证把它训得很好来拟合数据

但这样就把变分推断就转变成了一个参数优化问题：

$\mathcal{L}(q(\theta|\lambda)) = \int q(\theta|\lambda) \log\frac{p(x,\theta)}{q(\theta|\lambda)}d\theta \quad \rightarrow \quad \max_{\lambda}$

只要我们能够计算变分下界(ELBO)对于$\theta$的导数，那么就可以使用数值优化方法来对这个优化问题进行求解

Summary

$\text{Conditional} = \frac{\text{Joint}}{\text{Marginal}},\quad p(x|y)=\frac{p(x,y)}{p(y)}$

Product Rule

联合分布可以被表示为一维的条件分布的乘积

$p(x,y,z)=p(x|y,z)p(y|z)p(z)$

Sum Rule

任何边缘分布可以利用联合分布通过积分得到

$p(y) = \int p(x,y)dx$

Bayes理论

$p(y|x) = \frac{p(x,y)}{p(x)} = \frac{p(x|y)p(y)}{p(x)}=\frac{p(x|y)p(y)}{\int p(x|y)p(y)dy}$

Bayes理论定义了当新的信息到来的时候，可能性的改变：

$\text{Posterior} = \frac{\text{Likelihood} \times \text{Prior}}{\text{Evidence}}$

统计推断（Statistical inference）

问题描述：

给定从分布$p(x|\theta)$中得到的独立同分布变量$X = (x_1,\ldots,x_n)$，来估计$\theta$

常规方法：

采用极大似然估计（maximum likelihood estimation）

$\theta_{ML} = \arg \max p(X|\theta) = \arg \max \prod_{i=1}^{n}p(x_i|\theta) = \arg \max \sum_{i=1}^{n} = \log p(x_i|\theta)$

贝叶斯方法：

用先验$p(\theta)$来编码$\theta$的不确定性，然后采用贝叶斯推断

$p(\theta|X) = \frac{\prod_{i=1}^{n}p(x_i|\theta)p(\theta)} {\int \prod_{i=1}^{n}p(x_i|\theta)p(\theta)d\theta}$

频率学派vs. 贝叶斯学派

• 现代机器学习模型中可训练的参数数量已经接近训练数据的大小了

• 频率学派得到的结果实际上是一种受限制的Bayesian方法：

  $\lim_{n/d \rightarrow \infty}p(\theta|x_1,\ldots,x_n)=\delta(\theta-\theta_{ML})$

  注：此处的$\delta$函数指的是狄拉克函数

贝叶斯方法的优点

• 可以用先验分布来编码我们的先验知识或者是希望的做种结果
• 先验是一种正则化的方式
• 相对于$\theta$的点估计方法，后验还包含有关于估计的不确定性关系的信息

概率机器学习模型

数据：

• $x$ – 观察到变量的集合（features）
• $y$ – 隐变量的集合（class label / hidden representation, etc.)

模型：

• $\theta$ – 模型的参数（weights）

Discriminative probabilistic ML model

通常假设$\theta$的先验与$x$没有关系

$p(y,\theta|x) = p(y|x,\theta)p(\theta)$

Examples:

• 分类或者回归任务（隐层表示比观测空间简单得多）
• 机器翻译（隐层表示和观测的空间有着相同的复杂度）

Generative probabilistic ML model

可能会很难训练，因为通常而言观测到的$x$会比隐层复杂很多。

Examples：

• 文本，图片的生成

贝叶斯机器学习模型的训练与预测

Training阶段：$\theta$上的贝叶斯推断

$p(\theta|X_{tr},Y_{tr}) = \frac{p(Y_{tr}|X_{tr},\theta)p(\theta)} {\int p(Y_{tr}|X_{tr},\theta)p(\theta) d\theta}$

结果：采用$p(\theta)$分布比仅仅采用一个$\theta_{ML}$有着更好地效果

• 模型融合总是比一个最优模型的效果更好
• 后验分布里面含有所有从训练数据中学到的相关内容，并且可以模型提取用于计算新的后验分布

Testing阶段：

• 从training中我们得到了后验分布$p(\theta|X_{tr},Y_{tr})$
• 获得了新的的数据点$x$
• 需要计算对于$y$的预测

$p(y|x,X_{tr},Y_{tr}) = \int p(y|x,\theta) p(\theta|X_{tr},Y_{tr})d\theta$

重新看一遍

训练阶段：

$p(\theta|X_{tr},Y_{tr}) =\frac{p(Y_{tr}|X_{tr},\theta)p(\theta)}{\color{red}{\int p(Y_{tr}|X_{tr},\theta)p(\theta) d\theta}}$

测试阶段：

$p(y|x,X_{tr},Y_{tr}) =\color{red}{\int p(y|x,\theta) p(\theta|X_{tr},Y_{tr})d\theta }$

红色部分的内容通常是难以计算的！

共轭分布

我们说分布$p(y)$和$p(x|y)$是共轭的当且仅当$p(y|x)$和$p(y)$是同类的，即后验分布和先验分布同类。

$p(y)\in \mathcal A(\alpha),\quad p(x|y)\in \mathcal B(\beta)\quad \Rightarrow \quad p(y|x)\in \mathcal A(\alpha^{\prime})$

Intuition:

$p(y|x) = \frac{p(x|y)p(y)}{\int p(x|y)p(y)dy}\propto p(x|y)p(y)$

• 由于任何$\mathcal A$中的分布是归一化的，分母是可计算的
• 我们需要做的就是计算$\alpha^{\prime}$

这种情况下贝叶斯推断可以得到闭式解！

常见的共轭分布如下表：

举个例子：丢硬币

• 我们有一枚可能是不知道是否均匀的硬币
• 任务是预测正面朝上的概率$\theta$
• 数据：$X=(x_1,\ldots,x_n)$，$x\in\{0,1\}$

概率模型如下：

$p(x,\theta) = p(x|\theta)p(\theta)$

其中对于$p(x|\theta)$的似然为：

$Bern(x|\theta) = \theta^x(1-\theta)^{1-x}$

但是不知道$p(\theta)$的先验是多少

怎样选择先验概率分布？

• 正确的定义域：$\theta \in [0,1]$
• 包含先验知识：一枚硬币是均匀的可能性非常大
• 推断复杂度的考虑：使用共轭先验

Beta分布是满足所有条件的！

$Beta(\theta|a,b) = \frac{1}{\mathrm{B}(a,b)}\theta^{a-1}(1-\theta)^{b-1}$

同样也适用于大部分不均匀硬币的情况

让我们来检验似然和先验是不是共轭分布：

$p(x|\theta)=\theta^x(1-\theta)^{1-x}\qquad p(\theta) = \frac{1}{\mathrm{B}(a,b)}\theta^{a-1}(1-\theta)^{b-1}$

方法——检验先验和后验是不是在同样的参数族里面

$\begin{aligned} p(\theta)&=C\theta^{\alpha}(1-\theta)^{\beta}\\ p(\theta|x)&=C^{\prime}p(x|\theta)p(\theta)\\ &=C^{\prime}\theta^x(1-\theta)^{1-x}\frac{1}{\mathrm{B}(a,b)}\theta^{a-1}(1-\theta)^{b-1}\\ &=\frac{C^{\prime}}{\mathrm{B}(a,b)}\theta^{x+a-1}(1-\theta)^{b-x}\\ &=C^{\prime\prime}\theta^{\alpha^{\prime}}(1-\theta)^{\beta^{\prime}} \end{aligned}$

由于先验和后验形式相同，所以确实是共轭的！

现在考虑接收到数据之后的贝叶斯推断：

$\begin{aligned} p(\theta|X) &= \frac{1}{Z}p(X|\theta)p(\theta)\\ &= \frac{1}{Z}p(\theta)\prod_{i=1}^{n} p(x_i|\theta) \\ &=\frac{1}{Z} \frac{1}{\mathrm{B}(a,b)}\theta^{a-1}(1-\theta)^{b-1} \prod_{i=1}^{n} \theta^{x_i}(1-\theta)^{1-x_i}\\ &=\frac{1}{Z^{\prime}}\theta^{a+\sum_{i=1}^n x_i -1}(1-\theta)^{b+n-\sum_{i=1}^n-1}\\ &=\frac{1}{Z^{\prime}}\theta^{a^\prime -1}(1-\theta)^{b^\prime -1} \end{aligned}$

新的参数为：

$a^\prime = a+\sum_{i=1}^nx_i \qquad b^{\prime}=b+n-\sum_{i=1}^nx_i$

那么问题来了，当没有共轭分布的时候我们应该怎么做？

最简单的方法：选择可能性最高的参数

训练阶段：

$\theta_{MP}=\arg \max p(\theta|X_{tr},Y_{tr}) = \arg \max p(Y_{tr}|X_{tr},\theta)p(\theta)$

测试阶段：

$p(y|x,X_{tr},Y_{tr}) = \int p(y|x,\theta)p(\theta,X_{tr},Y_{tr})d\theta \approx p(y|x,\theta_{MP})$