Dynamic Routing Between Capsules

Part 1, Intution

CNN 是如何工作的?

  • 浅层的卷积层会检测一些简单的特征,例如边缘和颜色渐变。
  • 更高层的 layer 使用卷积操作将简单的特征加权合并到更复杂的特征中。
  • 最后,网络顶部的网络层会结合这些非常高级的特征去做分类预测。

在第二步中,需要理解的是,CNN 是通过加权求和的方式将低层次的特征组合到高层次的特征的(weighted, added, nonlinear)。在这个过程中,简单的特征在组合成更复杂的特征之前,他们之间是存在位置关系的(pose translation and ratational)。

对于这个位置关系的问题,CNN 是通过 max pooling/successive convolution layer 来解决这个问题的。通过减小图像的尺寸,增加高层神经元的感受野(field of view),这使得他们能在更大的区域内检测出更高阶的特征。

CNN 存在的问题

但是不要被 CNN 的表现好所迷惑,尽管 CNN 的表现优于其他模型。Hinton认为:max pooling工作得这么好其实是一个大灾难。

Hinton: “The pooling operation used in convolutional neural networks is a big mistake and the fact that it works so well is a disaster.”

就算你不使用max pooling,传统CNN依然存在这样的关键问题,学习不到简单与复杂对象之间的重要的空间层次特征。

Internal data representation of a convolutional neural network does not take into account important spatial hierarchies between simple and complex objects.

  • CNN只关注要检测的目标是否存在,而不关注这些组件之间的位置和相对的空间关系。如下例,CNN判断人脸只需要检测出它是否存在两个眼睛,两个眉毛,一个鼻子和一个嘴唇,现在我们把右眼和嘴巴换个位置,CNN依然认为这是个人。

个人理解:神经网络能否具备模糊识别的能力?比如仅仅是鼻子和眼睛调换了位置,但是大致看起来依然是一张人脸。神经网络能否像我们人类一样,知道这张图片想去表达一张人脸,只不过有些地方除了问题,那么它是否知道问题出在哪儿了呢?而不仅仅是识别的问题对吧?
再比如在文本领域,一两个字颠倒顺序并不影响我们人类阅读,神经网络也能理解它的意思,但是能否准确的知道这两个字顺序是颠倒的呢?
这能否作为一个课题。。神经网络纠错。。当然,如果给出了错误的数据集,那也就是监督学习以及分类的问题,能不能在没有给出这个有部分错误的数据情况下,依旧识别出来呢?

  • CNN 对旋转不具备不变性,学不到 3D 空间信息。例如下面的自由女神,我们只看自由女神的一张照片,我们可能没有看过其它角度的照片,还是能分辨出这些旋转后的照片都是自由女神,也就是说,图像的内部表征不取决于我们的视角。但是CNN做这个事情很困难,因为它无法理解3D空间。
  • 另外,神经网络一般需要学习成千上万个例子。人类学习数字,可能只需要看几十个个例子,最多几百个,就能区别数字。但是CNN需要成千上万个例子才能达到比较好的效果,强制去学习。并且关于前面的旋转不变性,CNN可以通过增强数据的手段去改善,但是这也就需要用到大量的数据集。

Hardcoding 3D World into a Neural Net: Inverse Graphics Approach

Capsules 就是为了解决这些问题。其灵感来源于计算机图形学中的渲染技术。

Computer graphics deals with constructing a visual image from some internal hierarchical representation of geometric data.
在计算机图形领域,是通过几何数据的内部层次表示来重构一个视觉图像的。这项技术叫 "渲染 (rendering)".

Inspired by this idea, Hinton argues that brains, in fact, do the opposite of rendering. He calls it inverse graphics: from visual information received by eyes, they deconstruct a hierarchical representation of the world around us and try to match it with already learned patterns and relationships stored in the brain. This is how recognition happens. And the key idea is that representation of objects in the brain does not depend on view angle.
Hiton 认为大脑是反向渲染的一个过程。接受视觉信息,然后对这样一个具有层次的信息表示进行解构,并与我们已知的模式进行匹配。这里的关键是对象信息的表示在大脑中是不依赖于某一个视角的。

So at this point the question is: how do we model these hierarchical relationships inside of a neural network?
那么我们如何通过神经网络对一个层次信息进行建模呢?

Capsules

Capsules introduce a new building block that can be used in deep learning to better model hierarchical relationships inside of internal knowledge representation of a neural network.

  • Capsule可以学习到物体之间的位置关系,例如它可以学习到眉毛下面是眼睛,鼻子下面是嘴唇,可以减轻前面的目标组件乱序问题。
  • Capsule可以对3D空间的关系进行明确建模,capsule可以学习到上面和下面的图片是同一个类别,只是视图的角度不一样。Capsule可以更好地在神经网络的内部知识表达中建立层次关系
  • Capsule只使用CNN数据集的一小部分,就能达到很好的结果,更加接近人脑的思考方式,高效学习,并且能学到更好的物体表征。

小结:这一节引用了capsule的概念,可以用于深度学习,更好地在神经网络的内部知识表达中建立层次关系,并用不同的方法去训练这样一个神经网络。

Part2, How Capsules Work

What is a Capsule?

CNN 在解决视角的不变性时是通过 max pooling 解决的。选择一块区域的最大值,这样我们就能得到激活的不变性(invariance of activities). 不变性意味着,稍微改变输入的一小部分,输出依旧不变。并且,在图像中移动我们识别的目标,我们依然能检测出这个目标来。

但是 max pooling 会丢失很多信息,并且 CNN 不能编码特征之间的相对空间关系。所以采用 capsules.

Capsules encapsulate all important information about the state of the feature they are detecting in vector form.

  • Capsule 是一个神经元向量(activity vector)
  • 这个向量的模长表示某个entity存在的概率,entity可以理解为比如鼻子,眼睛,或者某个类别,因为用vector的模长去表示概率,所以我们要对vector进行压缩,把vector的模长压缩到小于1,并且不改变orientation,保证属性不变化。
  • 这个向量的方向表示entiry的属性(orientation),或者理解为这个vector除了长度以外的不同形态的instantiation parameter,比如位置,大小,角度,形态,速度,反光度,颜色,表面的质感等等。

How does a capsule work?

传统神经元是一个 scaler, 神经元与神经元之间通过加权求和的方式连接。其计算方式:
- 计算输入标量 \(x_i\) 的权重 \(w_i\)
- 对输入标量 \(x_i\) 进行加权求和
- 通过非线性激活函数,进行标量与标量之间的变换,得到新标量 \(h_j\)

capsule 的前向转换的计算方式:

  • matrix multiplication of input vectors(输入向量 \(u_i\) 的矩阵 W 乘法)
  • scalar weighting of input vectors(输入向量 \(\hat u_i\) 的标量加权 \(c_i\)
  • sum of weighted input vectors(输入向量的加权求和)
  • vector-to-vector nonlinearity(向量到向量的非线性变换)

输入向量 \(u_i\) 的矩阵 W 乘法

Affine transform:  \[\hat u_{j|i}=W_{ij}u_i\]

  • 向量的长度表示低维的胶囊能检测出对应实体的概率。向量的方向则编码了检测对象的中间状态表示。我们可以假设低维胶囊 \(u_i\) 分别表示眼睛,嘴巴,鼻子这三个低层次的特征,高维胶囊 \(u_j\) 检测脸部高层次特征。
  • 矩阵 W 编码了低层次特征之间或低层次特征与高层次特征之间的重要的空间或其他关系。
  • \(u_i\) 乘以相应的权重矩阵 W 得到prediction vector(注意这个图里只画了一个 prediction vector,也就是 \(\hat u_i\),因为这里只对应了一个 capsule 输出,如果下一层有 j 个 capusles,\(u_i\) 就会生成 j 个 prediction vectors)

例如,矩阵 \(W_{2j}\) 可以对鼻子和面部的关系进行编码:面部以鼻子为中心,其大小是鼻子的10倍,而在空间上的方向与鼻子的方向一致。矩阵 \(W_{1j}\)\(W_{3j}\) 也是类似的。经过矩阵相乘之后,我们可以得到更高层次特征的预测位置。比如,\(\hat u_1\) 根据眼睛预测人脸位置,\(\hat u_2\) 根据嘴巴预测人脸位置,\(\hat u_3\) 根据鼻子预测人脸位置。最后如果这3个低层次特征的预测指向面部的同一个位置和状态,那么我们判断这是一张脸

输入向量 \(\hat u_i\) 的标量加权 \(c_i\)

weighting: \[s_{j|i} = c_{ij}\hat u_{j|i}\] \[s_{k|i} = c_{ik}\hat u_{k|i}\]

前面提到的传统神经元在这一步对输入进行加权,这些权重是在反向传播过程中得到的,但 Capsule 是通过 dynamic routing 的方式进行交流的。在这一步,低层次 capsule 需要决定怎么把自己的输出分配给高层次capsule。

\(c_{ij}\) 是耦合系数 (coupling coefficients), 通过迭代动态路由过程来决定。比如上图中的,高层次有两个胶囊 capsule J 和 capsule K. 那么对于 capsule i 通过上一步的矩阵 W 就可以得到 \(\hat u_{j|i}, \hat u_{k|i}\), 他们对应的权重分别是 \(c_{ij}, c_{ik}\), 并且有 \(c_{ij} + c_{ik} = 1\).

在动态路由的过程中是如何确定权重的呢,Routing by agreement:
- 在这张图片中,我们现在有一个低层次的已经被激活的capsule,它对下层每个capsule会生成一个prediction vector,所以这个低层次capsule现在有两个prediction vector,对这两个prediction vectors分配权重分别输入到高层次capsule J和K中。
- 现在,更高层次的capsule已经从其他低层次的capsule中获得了许多输入向量,也就是图片中的点,标红的部分是聚集的点,当这些聚集点意味着较低层次的capsule的预测是相互接近的。
- 低层次capsule希望找到高一层中合适的capsule,把自己更多的vector托付给它。低层次capsule通过dynamic routing的方式去调整权重c。

例如,如果低层次capsule的prediction vector远离capsule J中“correct”预测的红色集群,并且接近capsule K 中的“true”预测的红色集群,那么低层次capsule就会调高capsule K对应的权重,降低capsule J对应的权重。最后,如果高层次capsule接收到的这些prediction都agree这个capsule,那么这个capsule就会被激活,处于active状态,这就叫Routing by agreement。

加权输入向量的总和

sum:

\[s_j = \sum_i c_{ij}\hat u_{j|i}\] 高层次capsule根据前面计算的权重c,对所有低层次capsule的prediction vectors进行加权,得到一个向量。

向量到向量的非线性变换

Squashing是一种新的激活函数,我们对前面计算得到的向量施加这个激活函数,把这个向量的模长压缩到1以下,同时不改变向量方向,这样我们就可以利用模长去预测概率,并且保证属性不变化。

这个公式的左边是变换尺度,右边是单位向量。

小结:这一节介绍了capsule的基本概念,capsule把单个神经元扩展到神经元向量,有更强大的特征表征能力,并且引入矩阵权重来对不同layer特性之间的重要层次关系进行编码,结果说明了以下两种性质:

  • Invariance 不变性:物体表示不随变换变化,例如空间的 Invariance,是对物体平移之类不敏感(物体不同的位置不影响它的识别)
  • Equivariance同变性:用变换矩阵进行转换后,物体表示依旧不变,这是对物体内容的一种变换

Part 3, Dynamic Routing Between Capsules

算法的核心思想:
> Lower level capsule will send its input to the higher level capsule that “agrees” with its input. This is the essence of the dynamic routing algorithm.

动态路由算法的设计是为了动态调整 \(c_{ij}\) 的值:
- \(c_{ij}\) 为非负 scalar
- 对于每一个的 low level capsule i,所有的权重之和 \(c_{ij}\) 为 1,j 表示 high-level capsule j.
- 对于每一个 low-level capsule, 对应的权重数量等于 high-level 的数量
- 权重由动态路由算法确定

下面我们逐行解释伪代码:
1. 这个过程的输入是 第 \(l\) 层的 capsule 经过矩阵变换之后的 prediction vector \(\hat u\). 迭代步数 r
2. 初始化 \(b_{ij}\) 为 0, \(b_{ij}\) 是用来计算 \(c_{ij}\)
3. 对接下来4-6行代码迭代r次,计算第 \(l+1\) 层 capsule j 的 output
4. 在第 \(l\) 层,每个 capsule i 对 \(b_{ij}\) 做 softmax 得到 \(c_{ij}\)\(c_{ij}\) 是第 \(l\) 层 capsule i 给第 \(l+1\) 层 capsule j 分配的权重。在第一次迭代的时候,所有的 \(b_{ij}\) 都初始化为 0,所以这里得到的 \(c_{ij}\) 都是相等的概率,当然后面迭代多次后,\(c_{ij}\) 的值会有更新。
5. 在第 \(l+1\) 层,每个 capsule j 利用 \(c_ij\)\(\hat u_j|i\) 进行加权求和,得到输出向量 \(s_j\)
6. 在第 \(l+1\) 层,使用squash激活函数对 \(s_j\) 做尺度的变换,压缩其模长不大于1
7. 我们在这一步更新参数,对所有的 \(l\) 层 capsule i和 \(l+1\) 层 capsule j,迭代更新 \(b_{ij}\),更新 \(b_{ij}\) 为旧 \(b_{ij}\) + capsule j 的输入和输出的点乘,这个点乘是为了衡量这个 capsule 的输入和输出的相似度,低层 capsule 会把自己的输出分给跟它相似的高层 capsule。

经过r次循环,高层capsule可以确定低层分配的权重以及计算其输出,前向传播可以继续连接到下一个网络层。这个r一般推荐设置为3,次数太多了可能会过拟合。

susht 大佬画的图,不过没有把 \(b_{ij}\) 表示出来。 \(b_{ij}\) 的参数量和 \(c_{ij}\) 以及 \(u_{ij}\) 的个数是一致的。

  • 假设有两个高层capsule,紫色向量v1和v2分别是这两个capsule的输出,橙色向量是来自低层中某个capsule的输入,黑色向量是低层其它capsule的输入。
  • 左边的capsule,橙色u_hat跟v1方向相反,也就是这两个向量不相似,它们的点乘就会为负,更新的时候会减小对应的c_11数值。右边的capsule,橙色u_hat跟v2方向相近,更新的时候就会增大对应的c_12数值。
  • 那么经过多次迭代更新,所有的routing权重c都会更新到这样一种程度:对低层capsule的输出与高层capsule的输出都进行了最佳匹配。

小结:这节介绍了 dynamic routing algorithm by agreement 的方式去训练 capsNet,主要 idea 是通过点乘去衡量两个 capsule 输出的相似度,并且更新routing的权重参数。

CapsNet Architecture

论文给出了一个简单的CapsNet模型,第一层是个普通的conv层,第两层也结合了conv操作去构建初始的capsule,再通过routing的方式和第三层的DigitCaps交流,最后利用DigitCaps的capsule去做分类。

  • ReLU Conv1: 这是一个普通的卷积层,参数量是 \(9\times 9\times 256\), 假设输入是 \(28\times 28\times 1\), 得到的输出是 \(20\times 20\times 256\).

  • PrimaryCaps: 这里构建了 32 个 channels 的 capsules, 每个 capsule 的向量维度是 8. 依旧是采用卷积的方法,每一个 channels 使用 8 个卷积核 \(9\times 9\). 所以总的参数量是 \(9\times 9\times 256 \times 32\times 8 + 32 \times 8= 5308672\)。 一个 channels 对应一个 feature map,在这里是 \(6\times 6\) 个 8 维的 capsules. 所以最后是 \(6\times 6\times 32=1152\) 个 capsules。

  • DigitCaps: 对前面1152个capules进行传播与routing更新,输入是1152个capsules,输出是10个capules,每个 capsule 的维度由 8 变成了 16,表示10个数字类别,最后我们用这10个capules去做分类. 总的参数量是 \(1152\times 8\times 16+1152+1152=149760\). 后面两个 1152 分别表示 \(b_{ij}, c_{ij}\).

loss function

在 dynamic routing 过程中我们更新了 \(c_{ij}\) 参数,其余参数是通过反向传播进行更新,这里对于每一个capsule k我们都计算它的 Margin loss损失函数 \(L_k\)

跟 SVM 的 loss function 非常类似。
\[L_i = \sum_{j\neq y_i} \max(0, s_j - s_{y_i} + \Delta)\]

  • 不同的是,这里设定了 正类的概率 越小于 \(m^+=0.9\) 其贡献的 loss 越小,负类的概率越大于 \(m^-=0.1\) 其贡献的 loss 越大。
  • \(\lambda\) 参数设置为0.5,这是为了防止负例减小了所有capsule向量的模长。

Decoder: reconstruction as a regularization method

这里会mask掉一些capsule,用有代表性的capsule去重构图像,通过几层全连接层得到784维的输出,也就是原始图像的像素点个数,以这个输出跟原始像素点的欧几里得距离作为重构损失函数。

CapsNet与CNN的联系

相同之处:CNN可以上下左右平移在图像上进行扫描,也就是它在这个地方学到的东西可以用到下一个地方,可以有效识别图片的内容,所以capsule也采用了convolution的特点,最后一层只用capsule.

不同之处:capsule不采用max pooling的做法,因为Max pooling只保留了区域内最好的特征,而忽视了其它的特征,routing并不会丢失这些信息,它可以高效处理高度层叠的例子。浅层capsule会把位置信息通过place-coded的方式记录在激活的capsule中,高层的capsule会通过rate-coded的方式记录在capsule vector的值当中。

Capsules做分类的优点

适合输出有多个类别的多分类问题,softmax只适合只有一个输出的多分类问题,因为softmax会提高某一类的概率,而压低其余所有类别的概率。
另外,我们也可以用k sigmoid去代替softmax,把多分类任务转换成K个二分类任务.