2018年7月11日水曜日

正态分布的前世今生四

http://www.52nlp.cn/%E6%AD%A3%E6%80%81%E5%88%86%E5%B8%83%E7%9A%84%E5%89%8D%E4%B8%96%E4%BB%8A%E7%94%9F%E5%9B%9B

 

在介分布的后续发展之前,我来多一点数学,也有些人会得枯燥,不高斯曾经说过"数学是上帝的"。所以要想更加深入的理解正分布的美,唯有通上帝的

造物主造物的准往往是简单明了的,只是在芜杂的万物之中,我发现会它并非易事。之前提到17-18科学界流行的做法,是尽可能从某种简单明了的准(first principle)探求的起点,而后来的数学家和物理学家研究发现,屡次从一些定的简单的准,们总是被引到了正分布的家口,这让人感到正分布的美妙。

文的表弟高尔顿是生物学家兼统计学家,他分布非常的推崇与美:"我几乎不曾见过差呈正分布么激想象的宇宙秩序"。当代两位大的概率学家 Levy Kac 都曾经说过 分布是他切入概率的初恋情人,具有无的魅力。如果古希腊人知道正分布,想必奥林匹斯山的神殿里会多出一个正女神,由她来掌管世的混沌。

要拉下正分布的神秘面她的美,需要高深的概率,本人在数学方面知浅薄,不能任。只能在极有限的范尝试掀开她的面的一角。棣莫弗和拉普拉斯以抛钢镚的序列求和点,沿着一条小径把我第一次到了正分布的家口,条路叫作中心极限定理,而条路上景秀多概率学家都倒,条路在20被概率学家越拓越。而后数学家和物理学家们发现:条条曲径通正。著名的物理学家 E.T.Jaynes 在他的名著《Probability Theory, the Logic of Science(中文名翻译为《概率沉思)中,描了四条通往正分布的小径。曲径通幽,禅房花木深,一起来欣一下四条小径上的景吧。

1. 高斯的推(1809)

第一条小径是高斯找到的,高斯以如下准小径的出

差分布出的极大似然估 = 平均

值为 θθx1,,xnx1,,xnn次独立, 每次量的ei=xiθei=xi−θ

设误eiei的密度函数 f(e), 则测合概率n差的合概率,记为

L(θ)=L(θ;x1,,xn)=f(e1)f(en)=f(x1θ)f(xnθ)L(θ)=L(θ;x1,⋯,xn)=f(e1)⋯f(en)=f(x1−θ)⋯f(xn−θ)

求极大似然估,令

dlogL(θ)=0dlog⁡L(θ)dθ=0

整理后可以得到

ni=1f(xiθ)f(xiθ)=0∑i=1nf′(xi−θ)f(xi−θ)=0

 g(x)=f(x)f(x)g(x)=f′(x)f(x),

ni=1g(xiθ)=0∑i=1ng(xi−θ)=0

由于高斯假极大似然估的解就是算平均 x¯,把解入上式,可以得到

i=1ng(xix¯)=0()∑i=1ng(xi−x¯)=0(∗)

(*) 式中取 n=2n=2,

g(x1x¯)+g(x2x¯)=0g(x1−x¯)+g(x2−x¯)=0

由于此 x1x¯=−(x2x¯)x1−x¯=−(x2−x¯), 并且 x1,x2x1,x2 是任意的,有此得到

g(−x)=−g(x)g(−x)=−g(x)

(*) 式中再取 n=m+1n=m+1, 并且要求 x1==xm=−x,xm+1=mxx1==xm=−x,xm+1=mx,  x¯=0x¯=0, 并且

ni=1g(xix¯)=mg(−x)+g(mx)∑i=1ng(xi−x¯)=mg(−x)+g(mx)

所以得到

g(mx)=mg(x)g(mx)=mg(x)

足上式的唯一的连续函数就是 g(x)=cxg(x)=cx, 从而一步可以求解出

f(x)=Mecx2f(x)=Mecx2

由于f(x)f(x)是概率分布函数,把f(x)f(x) 化一下就得到正分布函数。

2. Herschel(1850) Maxwell(1860) 的推

第二条小径是天文学家 Hershcel 和物理学家麦克斯(Maxwell) 发现的。1850年,天文学家 John Herschel 星星的位置量的候,需要考差分布,了推导这差的概率密度分布 f(x,y)f(x,y),Herschel 置了两个准

  •  x y 差是相互独立的,即差的概率在正交的方向上相互独立
  • 差的概率分布在空上具有旋转对称性,即差的概率分布和角度没有关系

两个准则对 Herschel 实际测问题看起来都很合理。由准1,可以得到 f(x,y)f(x,y)应该具有如下形式

f(x,y)=f(x)f(y)f(x,y)=f(x)f(y)

个函数转换为极坐,在极坐下的概率密度函数设为 g(r,θ)g(r,θ),

f(x,y)=f(rcosθ,rsinθ)=g(r,θ)f(x,y)=f(rcosθ,rsinθ)=g(r,θ)

由准2, g(r,θ)g(r,θ) 具有旋转对称性,也就是应该 θθ 无关, 所以 g(r,θ)=g(r)g(r,θ)=g(r),
合以上,我可以得到

f(x)f(y)=g(r)=g(x2+y2−−−−−−)f(x)f(y)=g(r)=g(x2+y2)

 y=0y=0, 得到 g(x)=f(x)f(0)g(x)=f(x)f(0), 所以上式变为

log[f(x)f(0)]+log[f(y)f(0)]=log[f(x2+y2)f(0)]log⁡[f(x)f(0)]+log⁡[f(y)f(0)]=log⁡[f(x2+y2)f(0)]

 log[f(x)f(0)]=h(x)log⁡[f(x)f(0)]=h(x),

h(x)+h(y)=h(x2+y2−−−−−−)h(x)+h(y)=h(x2+y2)

个函数方程中容易求解出 h(x)=ax2h(x)=ax2, 从而可以得到 f(x)f(x) 的一般形式如下

f(x)=απ−−eαx2f(x)=απe−αx2

 f(x)f(x) 就是正分布 N(0,1/2α)−−−N(0,1/2α)  f(x,y)f(x,y) 就是准二分布函数。

f(x,y)=απeα(x2+y2)f(x,y)=απe−α(x2+y2)

1860 年,我们伟大的物理学家麦克斯在考气体分子的运速度分布的候,在三中基于似的准出了气体分子运的分布是正分布ρ(vx,vy,vz)exp{−α(v2x+v2y+v2z)}ρ(vx,vy,vz)exp{−α(vx2+vy2+vz2)}就是著名的麦克斯分子速率分布定律。大家还记得我在普通物理中学的麦克斯-尔兹曼气体速率分布定律

F(v)==(m2πkT)3/2emv22kT(m2πkT)1/2emv2x2kT×(m2πkT)1/2emv2y2kT×(m2πkT)1/2emv2z2kTF(v)=(m2πkT)3/2e−mv22kT=(m2πkT)1/2e−mvx22kT×(m2πkT)1/2e−mvy22kT×(m2πkT)1/2e−mvz22kT

所以个分布其是三个正分布的乘,你的物理老是否告诉过你其实这个分布就是三分布?反正我是一直不知道,直到今年才明白 

Herschel-Maxwell 的神妙之在于,没有利用任何概率的知,只是基于空几何的不性,就推出了正分布。

3. Landon 的推(1941)

第三条道是一位气工程Vernon D. Landon 出的。1941 年,Landon 研究通信路中的噪声电压,通分析经验数据他发现噪声电压的分布模式很相似,不同的是分布的层级,而层级可以使用方差 σ2σ2 来刻画。因此他推理认为噪声电压的分布函数形式是 p(x;σ2)p(x;σ2)在假有一个相 σσ而言很微小的扰动 eeee 的分布函数是 q(e)q(e), 那么新的噪声电压 x=x+ex′=x+eLandon 提出了如下的准

  •  随机噪声具有定的分布模式
  • 累加一个微小的随机噪声,不改定的分布模式,只改分布的层级(用方差度量)

用数学的言描述: 如果 xp(x;σ2),eq(e),x=x+exp(x;σ2),eq(e),x′=x+e xp(x;σ2+var(e))x′p(x;σ2+var(e))

在我来推导满足以上两个准的函数p(x;σ2)p(x;σ2) 应该长啥样。按照两个随机量和的分布的算方式, xx′ 的分布函数将是 xx 的分布函数和 ee的分布函数的卷,即有

f(x)=p(xe;σ2)q(e)def(x′)=∫p(x′−e;σ2)q(e)de

 p(xe;σ2)p(x′−e;σ2) xx′做泰勒数展开(了方便,展开后把自量由 xx′ 换为 xx) 上式可以展开

f(x)=p(x;σ2)−∂p(x;σ2)∂xeq(e)de+12∂2p(x;σ2)∂2xe2q(e)de+f(x)=p(x;σ2)−∂p(x;σ2)∂x∫eq(e)de+12∂2p(x;σ2)∂2x∫e2q(e)de+

 p=p(x;σ2)p=p(x;σ2),

f(x)=p−∂pxe¯+12∂2p2xe2¯+o(e2¯)f(x)=p−∂p∂xe¯+12∂2p∂2xe2¯+o(e2¯)

于微小的随机扰动 ee, 们认为他取正或者负值称的,所以e¯=0e¯=0。所以有

f(x)=p+12∂2p2xe2¯+o(e2¯)f(x)=p+12∂2p∂2xe2¯+o(e2¯)

于新的噪声电压 x=x+ex′=x+e 方差由σ2σ2 增加 σ2+var(e)=σ2+e2¯σ2+var(e)=σ2+e2¯,所以按照 Landon 的分布函数模式不的假 新的噪声电压的分布函数应该为 f(x)=p(x;σ2+e2¯)f(x)=p(x;σ2+e2¯)p(x;σ2+e2¯)p(x;σ2+e2¯)  σ2σ2 做泰勒数展开,得到

f(x)=p+∂pσ2e2¯+o(e2¯)f(x)=p+∂p∂σ2e2¯+o(e2¯)

以上 f(x)f(x) 的两个展开式,可以得到如下偏微分方程

12∂2p2x=∂pσ212∂2p∂2x=∂p∂σ2

个方程就是物理上著名的散方程(diffusion equation),求解方程就得到

p(x;σ2)=12πσex22σ2p(x;σ2)=12πσe−x22σ2

又一次,我出了正分布!

E.T. Jaynes个推价很高,认为Landon 的推出了自然界的噪音形成的程。他指出个推导这基本上就是中心极限定理的增量式版本,相比于中心极限定理是一次性累加所有的因素,Landon 的推是每次在原有的分布上去累加一个微小的扰动
而在个推中,我看到,正分布具有相当好的定性;只要数据中正的模式已形成,他就容易继续保持正分布,无外部累加的随机噪声 q(e)q(e) 是什么分布,正分布就像一个黑洞一个累加噪声吃掉。

4. 最大和正分布

有一条神妙的小径是基于最大原理的, 物理学家 E.T.Jaynes 在最大原理上有非常重要的献,他在《概率沉思》里面对这个方法有描述和明,没有提到发现者,我不确认这条道的发现者是否是 E.T.Jaynes 本人。

在物理学中由来已久,信息始人香(Claude Elwood Shannon)个概念引入了信息,学机器学的同学都知道目前机器学中有一个非常好用的分算法叫最大器。要想把和最大的来去脉清楚可不容易,希望我后能有时间整理一下。条道的景是相当独特的,E.T.Jaynes 对这条道也是偏有加。

于一个概率分布 p(x)p(x), 他的熵为

H(p)=−p(x)logp(x)dxH(p)=−∫p(x)log⁡p(x)dx

如果定一个分布函数 p(x)p(x) 的均 μμ 和方差σ2σ2(定均和方差个条件,也可以描述为给定一原点矩和二原点矩,两个条件是等价的)在所有两个限制的概率分布中,最大的概率分布 p(x|μ,σ2)p(x|μ,σ2) 就是正分布 N(μ,σ2)N(μ,σ2)

结论的推数学上稍微有点复,不如果已猜到了定限制条件下最大的分布是正分布,要个猜却是很简单的,明的思路如下出。

两个概率分布 p(x),q(x)p(x),q(x)。使用不等式 logx≤(x−1)log⁡x≤(x−1),

p(x)logq(x)p(x)dxp(x)(q(x)p(x)−1)dx=q(x)dxp(x)dx=0∫p(x)log⁡q(x)p(x)dx≤∫p(x)(q(x)p(x)−1)dx=∫q(x)dx−∫p(x)dx=0

于是

p(x)logq(x)p(x)dx=p(x)log1p(x)dx+p(x)logq(x)dx≤0∫p(x)log⁡q(x)p(x)dx=∫p(x)log⁡1p(x)dx+∫p(x)log⁡q(x)dx≤0

所以

H(p)≤−p(x)logq(x)dxH(p)≤−∫p(x)log⁡q(x)dx

熟悉信息的同学都知道,个式子是信息中的很著名的结论:一个概率分布的熵总是小于相对熵。上式要取等号只有取q(x)=p(x)q(x)=p(x)

 p(x)p(x), 定的均 μμ 和方差 σ2σ2, q(x)=N(μ,σ2)q(x)=N(μ,σ2), 可以得到

H(p)≤−p(x)log{12π−−√σe(xμ)22σ2}dxH(p)≤−∫p(x)log⁡{12πσe−(x−μ)22σ2}dx
=p(x){(xμ)22σ2+log2π−−√σ}dx=∫p(x){(x−μ)22σ2+log⁡2πσ}dx
=12σ2p(x)(xμ)2dx+log2π−−√σ=12σ2∫p(x)(x−μ)2dx+log⁡2πσ

由于 p(x)p(x) 的均方差有如下限制

p(x)(xμ)2dx=σ2∫p(x)(x−μ)2dx=σ2

于是

H(p)≤12σ2σ2+log2π−−√σ=12+log2π−−√σH(p)≤12σ2σ2+log⁡2πσ=12+log⁡2πσ

而当p(x)=N(μ,σ2)p(x)=N(μ,σ2)候,上式可以取到等号,明了结论

E.T.Jaynes 分布具有这样的性为赞赏,因为这从信息的角度明了正分布的良性。而我可以看到,的大小,取决于方差的大小。 也容易理解, 分布的均和密度函数的形状无关,而的大小反概率分布中的信息量,然和密度函数的形状相关,而正分布的形状是由其方差决定的。

好的,景欣赏暂时告一段落。所横看成岭成峰,近高低各不同,正分布提供了多种欣角度和想象空。法国菩萨级别的大数学家加莱分布说过一段有意思的,引用来作为这个小束:

Physicists believe that the Gaussian law has been proved in mathematics while mathematicians think that it was experimentally established in physics.

— Henri Poincaré

相关文章:

  1. 分布的前世今生()
  2. 分布的前世今生()
  3. 分布的前世今生()
  4. 分布的前世今生()
  5. 分布的前世今生()
  6. LDA-math-认识Beta/Dirichlet分布(3)
  7. 分布的前世今生()
  8. LDA-math-认识Beta/Dirichlet分布(2)
  9. LDA-math-神奇的Gamma函数(3)
  10. LDA-math-认识Beta/Dirichlet分布(1)

 

2018年7月10日火曜日

PAPER EXPLANATION – DEEP RESIDUAL LEARNING FOR IMAGE RECOGNITION (RESNET)

This paper is the outcome when Microsoft finally released the beast! The ResNet "slayed" everything, and won not one, not two, but five competitions; ILSVRC 2015 Image Classification, Detection and Localization, and COCO 2015 detection and segmentation.

PROBLEMS THE PAPER ADDRESSED

The paper analysed what was causing the accuracy of deeper networks to drop as compared to their shallower counterparts and provide a possible solution to it. As a result it became to successfully train a very deep network (152 layers).

Before we dive into the architecture, let's look at the problem a little more closely.

THE PROBLEM

The problem is the degradation problem; as we increase the depth of the network, instead of the accuracy increasing, it drops. This drop isn't just on the validation set data but also on the training data. As a result of this, overfitting can be ruled out as the cause of the problem because if the model was overfitting, the training accuracy, instead of dropping, would be high which is different from the observation.

Degradation Problem
Training error (left) and test error (right)on CIFAR-10 with 20-layer and 56-layer "plain" networks.

In the paper it is mention that the vanishing gradient has been taken care of by "normalised initialisation" and "intermediate normalisation layers" and the problem is due to because "current solvers are unable to find a proper solution in feasible time". In other words, it's an optimisation problem. Somehow, it is becoming very difficult for a deep "plain" network to create a good mapping (a function) from the input images to the output labels.

Now, a plausible argument to the above statement could be that a better solution for these deep nets just don't exist! Well, this possibility is also ruled out. Consider a shallower architecture and its deeper counterpart. There exists a solution where all the layers from the shallow net are copied to the deep net and the extra layers are just identity mapping (these identity mappings do not extract any new features and are just redundant). This proves that the solution space for a shallow net is a subset of that of a deeper net and hence a deeper model should produce no higher training error than its shallower counterpart.

Now that we have understood the problem, let's look at innovations done in the architecture to fix it.

THE ARCHITECTURE

Instead of learning a desired mapping from the input space to the output space, ResNets learn a Residual Mapping, called residual learning.

RESIDUAL LEARNING

Residual learning is based on the hypothesis (without proof) that "multiple nonlinear layers can asymptotically approximate complicated functions however all functions don't have the same ease of learning, some are harder while some are easier to learn". In other words, it is theoretically possible to map any function using multiple non-linear layers, however, practically not all mappings are easy and feasible to obtain.

Denoting the underlying (required)mapping as H(x), the stacked non-linear layers fit another mapping, called residual mapping, of F(x) := H(x) – x. It is hypothesised the it is easier to fit the residual mapping, F(x), than to optimise the original mapping, H(x) := F(x) + x. An example to see this is, say the ideal optimal mapping for H(x) is the identity function i.e. H(x) = x, then it will be easier to push the residual to zero, F(x) = 0, than to fit an identity mapping by a stack of non-linear layers.

The above is achieved by using skip connections!

RESNET ARCHITECTURE
Residual Block
Residual learning: a building block.

The figure shows the smallest building block of a ResNet. It is basically a couple of stacked layers (minimum two) with a skip connection. Skip connections are mainly just identity mappings and hence contribute no additional parameters. Residual learning is applied to these stacked layers. The block can be represented as:

y = F(x, {Wi}) + x

F is the residual function learned by the stacked layers. F + x is element-wise addition. The dimensions of x and F must be equal to perform the addition. If this is not the case (e.g., when changing the input/output channels), the following can be done:

  1. The shortcut still performs identity mapping, with extra zero entries padded for increasing dimensions. This introduces no additional parameters.
  2. Perform a linear projection Ws by the shortcut connections, using 1 × 1 convs. to match the dimensions, y = F(x, {Wi}) + Wsx. This introduces extra parameters and computation. In other words we are just adding a 1 × 1 conv. layer in the shortcut connection with the number of filters equal to the required output dimensions.

The final non-linearity is applied only after the element-wise addition.

One point to note is that, if the number of stacked layers was only one, there would be no advantages as the block would just behave like a normal conv. layer:

y = F(x, {Wi}) + x 

 y = (W1x + b) + x

 y = (W1 + I)x + b

 y = W2x + b …………… where W2 = W1+ I and I is an identity matrix.

The actual ResNet model is basically just the residual blocks repeated multiple times. Batch Normalization is used after each convolution but before applying the activation function. All the convolutional layers do not affect the spatial dimensions. Max pooling layers are responsible for halving the spatial dimensions. The output feature map of the last convolutional layer is passed through a global average pooling layer and then finally to a fully connected layer with the number of neurons equal to the number of classes.

ResNet34
A residual network with 34 parameter layers. The dotted shortcuts increase dimensions.
BOTTLENECK LAYER

In deeper variants of ResNet, bottleneck layers are used similar to that in GoogLeNet. The input is first fed through a 1 × 1 conv. layer to reduce the number of channels. After that, a 3 × 3 convolutions are performed followed by another 1 × 1conv. layer to increase/restore the number of channels.

bottleneck layer resnet
Left: Simple residual block. Right: Residual block with bottleneck layer.

TRAINING

224 × 224 crops are randomly sampled from an image resized such that its shorter side is randomly chosen form [256, 480], with the per-pixel mean subtracted. Stochastic gradient descent with mini-batch size of 256, momentum of 0.9 and a weight decay of 0.0001 is used. The learning rate is initialized at 0.1 and is divided by 10 when the error plateaus. The models are trained for 60 × 10e4 iterations. Dropout is not used.

CONCLUSION

From the 22 layer GoogLeNet to the monstrous 152 layer ResNet was a huge leap in just one year! ResNets achieved a 3.57% top-5 error on the ImageNet competition.

 

Original Paper: Deep Residual Learning for Image Recognition

Implementation of ResNet: https://github.com/Natsu6767/ResNet-Tensorflow