八分音符(频率)卷积算子 Octave Convolution

为什么读此系列文章？

优化数学和计算理论帮助机器学习完成问题分类：

1）按照领域划分，比如计算机视觉，自然语言处理，统计分析预测； 

2）按照算法复杂划分，比如是否是NP-Hard问题，是否需要精确解；

3）按照方法分类，监督性学习问题，非监督性学习问题，半监督性学习模型，和有先验信息的交互学习模型；

4）按照研模型分类，比如基于代数线性表出理论、基理论的线性模型，基于决策树的树状非线性模型，基于Kernel理论的非线性模型，基于编码解码器的神经网络；

逐渐形成以数据为主轴，离线训练算法，在线推理的机器学习模型离开刀耕火种，进入春秋百家争鸣时代。这一时期，监督性学习理论高速增长，以逻辑回归，SVM，Convolution Neural Network，RNN迅速在子领域占领重要的一席之地。

这是一个幸福的时代，实际上每个子领域，都已经形成成熟的方法论。

从Tensorflow开始，我意识的这已经从春秋，进入短短战国时代。针对大量数据的存储，ETL，和分布式内存计算比如流计算平台，针对机器学习的软件架构实现比如Tensorflow, 针对业务场景的端设备，针对计算资源虚拟化、计算能力服务化的云平台，会扮演者越来越重要的作用。没有算法工程师和软件架构工程师很有可能是从不同方向，成长起来的同一批人。所以我们需要了解，去研究以工业框架底层目标模型，到底该如何实现，才能实现我们的从输入到输出的价值？（没有中间商赚差价）

本系列文章包含哪些内容？

本系列文章，旨在通过扎实的实现纵向优化，工业级代码框架的横向比较，透视、分析神经网络架构撰写技巧，方法和思路，正确使用神经网络工具，解决实际生成问题：

1. 数据篇：数据集编写，训练、测试数据预处理技术，图像数据正则化技巧，ZCA白化技术；带标注的训练数据增强，其中标注包含以下可能的数据类型：BBounding Box, Mask, Key Points, Feature Descriptor。还包括Anchor size等相关超参数估计技巧。无数据无监督性学习算法。

2. 网络结构篇：组网手段，各个网络的优势，和loss函数的书写技巧：比如CNN网络如何根据业务实时性选择特征提取层，不同尺度大小目标的特征提取，ROI编码等；再比如将回归问题转化为分类问题，给定一个预估值，动态计算上确界，和下确界，并极大化预估值落入区间的概率，极小化双向溢出率，通过分位数回归来计算loss实现任意非标准分布的强拟合；我们将重点关注，全连接网络，卷积网络，网络搜索(NAS)，图网络的实现方法，和撰写技巧。

3. 算子篇：具体的算子的实现。比如IoU, GIoU, 我实现的UIoU；再比如卷积块实现，金字塔特征FP实现，残差块实现；在比如卷积核反向传播算法，空洞卷积反向传播算法

4. 求解器篇：求解器实现策略, 和相关数学原理。实际上神经网络的求解器涉及的技术和理论还是比较局限的，主要通过heuristic以梯度贪心，参数可行域无限制，参数间无约束关系（比如图连接）因此较为简单；比如Wolf-Powell定理及其实现，用于判定搜索是否可收敛；在拟牛顿法理论二次加速原理，及其局限性和相关近似算法；在比如理论上任网络可以使用另外一个非线性模型代替全连接层FC用来学习，比如SVM，GBDT等；BOOSTING技巧，有趣的AdaBoost；整数优化拓展，实际上离散优化和非离散优化的数学技术有很大的不同，是否可以神经网络架构搜索映射到0-1整数规划，一个值得思考的问题！更复杂的优化求解器技术，参数可行域受限，以参数间以图连接为约束，包含时间窗口约束，则需要更为完善的数学理论。这里我推荐Google OR tools来学习LP, MLP, VRPT(C)进行相关问题求解。

5. 计算图：从2015年tensorflow相关文章Dean Jeff等人的文章《Large Scale Deep Learning with Tensorflow》, 计算图不仅仅包含自动微分，还包含分布式思想中的算子算力划分，数据并行，和模型并行的加速思想在里面。自动微分已经被人们完全掌握，比如基于Numpy的AutoGrad, 实现一个自动微分以及不难。但是实现一个能够进行上述在异构设备上进行算力划分， 执行不同并发策略是十分困难的。
   

为什我想写？

2019年通过姜老师的推荐，和华为ModelArts团队有接触，认识了陈亮老师等人。陈老师希望我来提高社区氛围，随后我就写了Vgg16, YoloV4(YoloV3)变种的实现，以及对ImageNet预训练网络的参数的利用方法。期间大家努力拼搏的精神，让我大受感动。我和清华大学出版社的编辑讨论，也觉得围绕机器学习的架构是个很重要的点。

以往的书目，如华章教育从剑桥出版社引入的以色列科学家著的《深入理解机器学习，从算法到原理》（Understanding Machine Learning from Theory to Algorithms）作为研究生教程，有非常浓厚的数学理论的描述，过于艰涩：首先定义了机器学习的理论框架，以及所有理论服务于将模型编码到计算机上的根本目标；然后样本和总体的关系，定义一些评价由采样样本通过经验误差获得机器学习模型好坏的指标（Valiant提出PAC范式理论，于2010年获得图灵奖，诞生批处理算法并广泛运用于生产算法中，供业模型框架），进而通过找出尽量避免出现坏指标的规则，来设计可充分学习机器学习模型，并将机器学习的学习过程描述为一致收敛过程。接着该书分析了具体线性模型技术算法和一些高级技术。整个过程都是以伪代码和数学表达式来描述，没有明确的研究目标。在现在这种算法越来越专业，研究对象高度相关，算法质量要求越来越高的情况下，这种数学很难帮助学习者掌握1到2两个专业领域的核心技术，跟别说研究目标泛化机器学习体系了。

随后2015-2017年博视，电子工业出版社围绕着Tensorflow，Caffe， Scipy推出了一大批《XX实践》图书。它们具有以下特点：

1）紧密围绕工具，讲解如何通过工具实现一个数据分析手段，从其行文可以看出主要面向非计算机专业方向的学生，从业人员。这导致他们容易受制于工具成为被一些高水平，尤其有计算机专业背景戏称为“调参侠”；

2）有代码的实现和讲解，但是仅限于实现比较简单的，大约1000行以内的模型；或者借助框架提供的优化器，算子建模求解，相对上面的著作缺乏批判性分析和相关实验过程及实验结论；或者过于简化问题，和Github已经开源实现、或者二次开源复现所提供的完整的问题框架相差太远；把一个完整的问题的不同步骤，分散到不同章节的不同问题里面，这是不利于学习和掌握的；

3）绝大多数图书包括《XX实践》，中关于神经网络，尤其是卷积网络都是浅尝辄止，和目前的高水平模型相差甚远，没有实用性：比如没有对预训练模型的利用，缺乏对数据源的分析，没有区分特征器提取问了包括VGG, ResNet, Inception, DarkNet，MobileNet速度，精确度，大小，架构的区别，没有对多目标检测诸多模块的分析，没有带标注数据数据增强相关的分析和思考。

2018年以问题为导向，面向面试的机器学习图书《百面机器学习》在京东售卖。这本书的书写作非常有趣，是先抛出一个问题，然后再寻求解决，类似美国大学课程Warm Up环节，其实和我的一些思考、过去的备课的内容不谋而合：

2018年我想改善机器学习面试体验。当时我通过我自己的渠道，已经收到了几十封简历，其中一些已经有相当资深的经验。受限HeadCount要求，我只能挑选一些刚毕业的学生，包括哥伦比亚大学毕业的，美国东北大学毕业，浙大毕业的，厦门大学毕业，华科大毕业的，北京邮电大大学毕业的朋友等。我结合自己的经验，我决定以问题为导向：我利用下班时间对简历进行coach后，面试中我给候选人准备了8道精心选择题目供他(她)3分钟内的选择，同时我又准备了20到题目根据前一步的选择，动态决定第二道题目选择，并和她沟通是否感兴趣。如果答得不是十分好，我会给一份课后作业，如果感兴趣，可以3天内完成的一个小Project。我同时我想HR，面试候选人做了些回访，无论结果如何，满意度还是非常高的。

在我之前面试要么是纯Code，主要考察计算机基础理论和算法，要么就是现场做数学推理并回答一些比较经典的问题，而我自己恰又是一个平时只有兴趣做最基本的训练，大块时间放在专业领域上，临场全靠即兴发挥的人，觉得这个面试流程还有很大的改进空间。事实上例如2009年MSRA出版的《编程之美》和上述《百面机器学习》都一个不足，就是看似十分机智的问题，其实都有专门的研究领域。在这个研究领域，只能算是浅尝辄止的问题和实践。比如最基本的Qick-Sort，你没有读过专门的学术著作，比如算法导论了解其不断改进的过程，一个新问题放在面前你是很难优化的(比如，如何对不均匀分布数据块，甚至数据链表，加速Quick-Sort，笔者在Github有相关解答)，因为你根本就是外行。所以我希望面试应该在应试者的专业范围内循序渐进，这对于涵盖，统计学、运筹学、控制学、计算机工程的、计算图形学的交叉学科尤为重要，因为不可能有人全部掌握这些的。

我仔细阅读了诸葛越女士做得序，发现这本书起于公众号的“机器学习问答”，因此我发现诸葛越女士似乎对“通用人工智能更感兴趣”，比如此书仍然更关注方法论，有非常强的数学属性在里面；数目同时涵盖了优化论，图模型，采样理论，全连接神经网络，深度卷积网络，深度残差网络，循环神经网络，树模型，强化学习，生成模型GAN。我们已经知道，Hulu是一个自制作剧目，并且售卖限时流媒体广告的公司，如果这本书能够从Hulu广告业务所对应的计算广告问题出发，视频网站相关的运营策略比如推荐，曝光，排序出发，你会发现数据（有业务意义的埋点数据），所对应的处理方法（特征工程，采样，非均衡数据处理，离散特征编码），以及所选用的模型（可解释性）立刻有了明确的指向。我立刻得出这本书是如何组织架构的。

我希望系列文章以问题为导向，同时问题是一脉相承的，主线明确。系列文章的每一部分，是为了主线问题，进一步细化每一个步骤的处理方法，和相关研究，在力所能及的范围内完整的解决一个目标，掌握一两个技术，产生实际价值。

==== 我是分割线 ====

Warmup

原始的卷积核及其BP算法，在2019年4月30公开的这篇名为"Drop an Octave: Reducing Spatial Redundancy in Convolutional Neural Networks with Octave Convolution"[1]的文章里，原始卷积成为“平凡的实现”（Vanilla implementation）。在考虑新提出的八分音符(频率)[5]卷积前，我们需要回顾下上一篇文章提到的卷积网络的卷积核理论，以及JPEG算法。

1. 卷积核理论回顾，如[文章](https://mp.weixin.qq.com/s/GKZeTrfTgRXmj29c_XouOQ)介绍：

filtersxkxk卷积，作用在输入特征BxHxWxC，涉及: B*(k^2*C*h_nm_out*w_nm_out + (k^2-1)*C*h_nm_out*w_nm_out-1)次浮点计算。我们已经说明，卷积对应多项式乘法的系数表达式。由于n维多项式，根据代数基本定理，由n采样点唯一确定，得知多项式，由范德蒙矩阵决定。因此将多项式乘法，改由采样的点值乘积表示后，就可以通过范德蒙矩阵的逆推算，多项式乘积的系数，即傅里叶变换的取值。

利用复根采样“重数折半”性质，根据主定理，FFT可以nlog(n)完成n阶多项式到采样值表示法:

0) img2col可用于加速dot算子，但FFT使用img2col是错误的，因为理论上k*k的卷积核，最多只需要k维傅里叶基就可以表示，利用傅里叶变换的可分离性（Separable）可以用两个一维傅里叶变换计算二维傅里叶变换。

1) 应用FFT到卷积核：H*W* (log(H) + log(W)) 

2) 应用FFT到输入：H*W* (log(H) + log(W))

3) 上面两个结果执行点乘计算: H*W

4) 应用逆FFT到上一步计算结果：H*W*(log(H) + log(W))

因此总计算量为：B*(log(H) + log(W))*C*H*W

对于256*256的图像log(H) + log(W) ~ 16，当卷积核为5, 8时分别节省1.5, 4倍算力。

2. JPEG算法

在JPEG理论，图像的像素在空间域（Spatial Domain）是有关联性的。因此先算出每个channel的图像的均值，并平移该通道的图像，然后启用二维离散傅里叶变换将图像从空间域（Spatial Domain）转换到 频域 (Frequency Domain) -- 每个像素点，由不同频率的余弦波值叠加而成，得到的逆变换。我们将得到下图，此时图像像素间毫无相关性：即任意丢弃高频波信息，逆变换后不改变原图像纹理。这是以二维傅里叶变换作为基础的JPEG技术专利的核心概念之一。这里的傅里叶变换，就是我们通过卷积核(8x8)点乘输入特征。

 图1：空间频率 Spatial Frequency (SF)[https://sites.uclouvain.be/goffauxlab/project_sf.html]

空间频谱图是对应频域低频傅里叶波函数。具体做法如下:

1) 将图像通过img2col展成一维图像

2) 用快速傅里叶变换，求得频域值

3) 将低频移到中心方便矩形滤波器，过滤

可以通过下面代码进行查看频谱图：

通过，剪裁，我们可以提取不同尺度的频谱特征。下面我提供了实验代码和结果(Colab: https://colab.research.google.com/drive/1Qy5hRRXUz_czN_PXofhZ60ivA9PnA_T7#scrollTo=fLmYabj7XbQP)：

图2：频谱空间低频特征提取

图3：频谱空间高频特征提取

图4：频谱空间带特征提取

3. 频谱和方向作为不变特征

根据认知科学实验，视觉特征被分为，空间频谱（Spatial Frequency）和 朝向（Orientiation）[2]。大脑视觉皮层小的感受野被空间频谱和朝向分解激活，大的感受野被复杂的图形激活[2][3][4].

实验发现[空间频谱和朝向激活量可以被朝向特征和频谱特征的线性加权逼近[2], 且不同的皮质位置响应不同的频谱频率[2]。其中局部8梯度方向直方图检测，已经成为了SIFT特征用于图像处理多年。

高斯差分金字塔（DoG Pyramid）方法因此无论在仿生学上，还是实际计算中首先应用了多尺度特征提取的思想，已经接近日后的卷积块塔思想方法。尺度不变特征方法（SIFT）又进一步从朝向角度来寻找关键特征点，从而去定义图像特征。我们已经知道SIFT[6]的算法原理是有意义的，但是通过特征点来定义图像特征，已经不是我们现在的做法了。我们现在是通过神经网络编码器来输出图像的特征向量，精确度在包括ImageNet, Coco, VOC等数据集的比赛上已经超过了以往的所有方法。

本偏文章介绍的算子，从频谱角度出发，我猜想还可以从朝向进一步发掘，而这有历史过往图像特征提取方法，电子信号学数学物理方法，认知科学实验的坚实支撑。

OctConv

半分音符卷积，将训练过程中已经接近卷积核算子，分为高频，和低频部分。这是已经实证的概念。通过将他们分解成两个存储部分，并执行Butter-Fly计算：

图5：图像频谱分解[1]

图6：Octave Convolution计算过程[1]

其中原文中低频由0.5Hx0.5Wxalpha*Channel存贮卷积参数，高频由HxW*(1-alpha)*Channel存贮卷积参数。因此我们根据这个，可以在进行计算量复杂度估计，约为

图7：卷积核分解[1]

图8：输入特征频谱分解图[1]

官方Facebook通过TVM给出了实现，https://github.com/facebookresearch/OctConv/blob/master/utils/symbol/symbol_resnetv2.py定义了实验Resnet组网；https://github.com/facebookresearch/OctConv/blob/master/utils/symbol/symbol_resblock.py定义了ResnetBlock组件，通过OctaveConvolution实现的ResnetBlock被记做BottleNeckV{1,2}。实现方法是将标准残差连接块中的每个卷积块，由OctaveConvolution实现的卷积块代替。

https://github.com/facebookresearch/OctConv/blob/master/utils/gluon/train_imagenet.py定义了训练入口，其中get_data_loader定义了数据预处理，和增强模块。

实验分析

笔者任务思想上，如前面铺垫，这是非常有价值的思考方向和方法。另一方面，笔者发现，卷积是作用在整个训练周期中，同时理论计算没有考虑到Upsampling和Downsampling的计算。笔者还在做进一步研究工作, 因此目前不能给出非常强的结论，感兴趣的可以联系我（yiak.wy@gmail.com）

[1] Retrieve on 10th Aug 2019, "Drop an Octave: Reducing Spatial Redundancy in Convolutional Neural Networks with Octave Convolution", https://arxiv.org/pdf/1904.05049.pdf, Yunpeng Chen, Haoqi Fan, Bing Xu, Zhicheng Yan, Yannis Kalantidis, Marcus Rohrbach, Shuicheng Yan, Jiashi Feng

[2] Everson RM, Prashanth AK, Gabbay M, Knight BW, Sirovich L, Kaplan E. Representation of spatial frequency and orientation in the visual cortex. Proc Natl Acad Sci U S A. 1998;95(14):8334–8338. doi:10.1073/pnas.95.14.8334

[3]Retrived on 15th Aug 2019, https://zh.wikipedia.org/wiki/Octave_(%E9%9B%BB%E5%AD%90%E5%AD%B8)

[4] Distinctive Images Features from Scale-Invariant Keypoints, David G. Lowe, https://www.cs.ubc.ca/~lowe/papers/ijcv04.pdf, January 5, 2004

转自：Yiakwy