DeepIndeed's Blog!

• C++ Object Model

  2020-04-07

  blog

  C++

  前言

  面向对象的三大特征是抽象、继承、多态。《深度探索C++对象模型》一书中从数据的排布，C++对象函数的调用设计等等。 我尝试以一个编译器的设计者的角度去理解C++对象，该书中也提到了多种编译器，有的时候也会涉及一些不同编译器厂商在设计过程中的不同，虽然没有深入探究不同的原因以及优劣对比， 但对于我这个新手来说已经开了很大的窗户。

  整个书籍通过横向切割方式，分别从构造、数据成员、成员函数、运行时C++对象的特点来介绍，从缔造者的视角来理解C++对象的设计，有利于我们写出更加高效、简洁的程序。

  关于对象

  C++对象比C struct对象在空间与时间的有额外负担吗？

  封装的后布局成本与C struct是一样的。member functions虽然旱灾class的声明之内，却不出现在的object中。每一个non-inline memberfunction 只会诞生一个函数实例。 C++在布局以及存取时间上的主要的额外负担是由virtual引起的，包括：

  • virtual function机制，引入vptr以及vtbl，支持一个有效率的”执行期绑定”
  • virtual base class，用以实现”多次出现在继承体系中的base class，有一个单一而被共享的实例”
  • 多重继承下，派生类跟第二个以及后续基类之间的转换

  C++对象模型

  在C++中，有两种数据成员（class data members）：static 和nonstatic,以及三种类成员函数（class member functions）:static、nonstatic和virtual:

  class Base {
  public:
      Base(int i) :baseI(i){};    
      int getI(){ return baseI; } 
      static void countI(){};   //static
      virtual void print(void){ cout << "Base::print()"; } // virtual
      virtual ~Base(){}         // virtual
  private:
      int baseI;  // no static 
      static int baseS;  // static
  };
  

  在此模型下，nonstatic 数据成员被置于每一个类对象中，而static数据成员被置于类对象之外。static与nonstatic函数也都放在类对象之外，而对于virtual 函数，则通过虚函数表+虚指针来支持，具体如下：

  • 每个类生成一个表格，称为虚表（virtual table，简称vtbl）。虚表中存放着一堆指针，这些指针指向该类每一个虚函数。虚表中的函数地址将按声明时的顺序排列，不过当子类有多个重载函数时例外，后面会讨论。
  • 每个类对象都拥有一个虚表指针(vptr)，由编译器为其生成。虚表指针的设定与重置皆由类的复制控制（也即是构造函数、析构函数、赋值操作符）来完成。vptr的位置为编译器决定，传统上它被放在所有显示声明的成员之后，不过现在许多编译器把vptr放在一个类对象的最前端。关于数据成员布局的内容，在后面会详细分析。
  • 另外，虚函数表的前面设置了一个指向type_info的指针，用以支持RTTI（Run Time Type Identification，运行时类型识别）。RTTI是为多态而生成的信息，包括对象继承关系，对象本身的描述等，只有具有虚函数的对象在会生成。

  

  这个模型的优点在于它的空间和存取时间的效率；缺点如下：如果应用程序本身未改变，但当所使用的类的non static数据成员添加删除或修改时，需要重新编译。

  Note: 针对析构函数，g++中的实现有一些令人疑惑的地方，~Base在虚表中出现了两次，我表示不能理解，网上也没有找到相关说明。

  Vtable for Base
  Base::_ZTV4Base: 6u entries
  0     (int (*)(...))0
  4     (int (*)(...))(& _ZTI4Base)
  8     (int (*)(...))Base::print
  12    (int (*)(...))Base::~Base
  16    (int (*)(...))Base::~Base
  

  我猜测可能是我们使用g++编译中合成根据我添加的~Base()合成了一个用于动态内存分配释放的析构函数和静态释放的析构函数。当然如果有大佬知道这个是为什么，请务必指导一番，不胜感激。

  多重继承

  #include<iostream>
  using namespace std;
  class Base1
  {
  public:
  	virtual ~Base1() {};
  	virtual void speakClearly() {cout<<"Base1::speakClearly()"<<endl;}
  	virtual Base1 *clone() const {cout<<"Base1::clone()"<<endl; return new Base1;}
  protected:
  	float data_Base1;
  };
  class Base2
  {
  public:
  	virtual ~Base2() {};
  	virtual void mumble() {cout<<"Base2::mumble()"<<endl;}
  	virtual Base2 *clone() const {cout<<"Base2::clone()"<<endl; return new Base2;}
  protected:
  	float data_Base2;
  };
  class Derived : public Base1,public Base2
  {
  public:
  	virtual ~Derived()  {cout<<"Derived::~Derived()"<<endl;}
  	virtual Derived *clone() const {cout<<"Derived::clone()"<<endl; return new Derived;}
  protected:
  	float data_Derived;
  }
  

  

  类似问题在vs2010中也有，主要是多重继承的时，将派生类赋值给第二个基类时

  1>  Derived::$vftable@Base1@:
  1>   | &Derived_meta
  1>   |  0
  1>   0 | &Derived::{dtor}
  1>   1 | &Base1::speakClearly
  1>   2 | &Derived::clone
  1>  
  1>  Derived::$vftable@Base2@:
  1>   | -8
  1>   0 | &thunk: this-=8; goto Derived::{dtor}
  1>   1 | &Base2::mumble
  1>   2 | &thunk: this-=8; goto Base2* Derived::clone
  1>   3 | &thunk: this-=8; goto Derived* Derived::clone
  

  • 派生类的虚函数表数目是它所有基类的虚函数数目之和，基类的虚函数表被复制到派生类的对应的虚函数表中。

  • 派生类中重写基类的虚拟函数时，该被重写的函数在派生类的虚函数列表中得到更新，派生类的虚析构函数覆盖基类的虚析构函数。

  • 派生类中新增加的虚函数被添加到与第一个基类相对应的虚函数表中。

  • virtual table[1]中的clone分别为：Base2* Derived::clone 和 Derived* Derived::clone 。这里为什么会比table[0]多一个Base2* Derived::clone呢？ 因为：如果将一个Derived对象地址指定给一个Base1指针或者Derived指针是，虚拟机制使用的是virtual table[0] ；如果将一个Derived对象地址指定给一个Base2指针时，虚拟机制使用的是virtual table[1]。 （«C++对象模型» P164)

  构造函数

  

  参考链接

  MSVC应对多重继承中的thunk技术 C++对象模型详解 图说C++对象模型：对象内存布局详解 RTTI实现详解

  Read All

  ---

• The history of C++

  2020-04-01

  blog

  C++

  前言

  在阅读C++相关的技术书籍或博客时，常常会提到一些日常开发中不常接触的名词，如cfront 2.0或者TR1等，这些名词在C++的历史发展中属于里程碑式的的名词。从C++不同时期的发展中可以看出对于程序员的开发需求逐渐满足，伴随着C++的标准的变化，编译器对语言的支持也逐渐完善。

  C++ 历史大事件

  

  关键事件总结

  date	feature	details	sample
  1979	首次实现引入类的C	C with Classes first implemented 1. 新特性：类、成员函数、继承类、独立编译、公共和私有访问控制、友元、函数参数类型检查、默认参数、内联函数、赋值符号重载、构造函数、析构函数、f()相当于f(void)、调用函数和返回函数（同步机制，不是在C++中）</br> 2. 库：并发任务程序库（不是在C++中）
  1985	编译器cfront 1.0	1. 新特性：虚函数、函数和操作符重载、引用、new和delete操作符、const关键词、范围解析运算符:: 2. 新加入的库：复数（complex）、字符串（string）、输入输出流（iostream）
  1985	《C++编程语言第一版》	The C++ Programming Language, 1st edition
  1989	编译器cfront 2.0	1.新特性：多重继承、成员指针、保护访问控制、类型安全联接、抽象类、静态和常量成员函数、特定类的new和delete 2. 新库：I/O 操作器
  1990	ANSI C++委员会成立（ANSI C++ Committee founded）
  1990	《C++参考手册注解》	The Annotated C++ Reference Manual was released.
  1991	ISO C++委员会成立（ISO C++ Committee founded）
  1998	C++98	1. 新特性：运行时类型信息［RTTI（dynamic_cast, typeid）］、协变返回类型（covariant return types）、cast 操作符、可变型、布尔型、声明情况、模板例示、成员模板、导出 2. 新库：容器、算法、迭代器、函数对象（STL中）、区域设置、位集合、值向量、自动指针（auto_ptr）、模块化字符串、输入输出流和复数 the C++ standards committee published the first international standard for C++ ISO/IEC 14882:1998, which would be informally known as C++98. The Annotated C++ Reference Manual was said to be a large influence in the development of the standard. The Standard Template Library, which began its conceptual development in 1979, was also included.	*****
  1999	Boost由委员会成员成立，旨在开发新的高质量库以作为标准库的候选库	Boost founded by the committee members to produce new high-quality candidate libraries for the standard
  2003	C++03 (ISO/IEC 14882:2003)	The committee responded to multiple problems that were reported with their 1998 standard, and revised it accordingly. The changed language was dubbed C++03. 这是一个次要修订版本，修正了一些错误。
  2006	Performance TR (ISO/IEC TR 18015:2006) (ISO Store ) (2006 draft )	性能技术报告
  2007	2007 Library extension TR1 (ISO/IEC TR 19768:2007) (ISO store ) (2005 draft )	1. 源自Boost：引用包装器（Reference wrapper）、智能指针（Smart pointers）、成员函数（Member function）、Result of 、绑定（Binding）、函数（Function）、类型特征（type traits）、随机（Random）、数学特殊函数（Mathematical Special Functions）、元组（Tuple）、数组（Array）、无序容器［Unordered Containers包括哈希（Hash）］还有正则表达式（Regular Expressions） 2. 源自C99：math.h中同时也是新加入C99的数学函数、空白字符类、浮点环境（Floating-point environment）、十六进制浮点I/O操作符（hexfloat I/O Manipulator）、固定大小整数类型（fixed-size integral types）、长整型（the long long type）、va_copy、snprintf() 和vscanf()函数族，还有C99 的printf()与scanf()函数族的指定转换。 TR1除了一些特殊函数，大部分都被囊括进C++11。	*****
  2010	数学特殊函数技术报告［2010 Mathematical special functions TR (ISO/IEC 29124:2010)(ISO Store)］	此TR是一个C++标准库扩展，加入了TR1中的部分特殊函数，但那些函数之前没有被包括进C++11：椭圆积分、指数积分、拉盖尔多项式（Laguerre polynomials）、勒让徳多项式（Legendre polynomials）、艾尔米特多项式（Hermite polynomials）、贝塞尔（Bessel）函数、纽曼（Newmann）函数、$\beta$函数和黎曼（Riemann）$\zeta$函数
  2011	C++11 (ISO/IEC 14882:2011) (ISO Store) (ANSI Store )	1. 新语言特性：自动（auto）和类型获取（decltype）、默认和已删除函数（defaulted and deleted functions）、不可更改（final）和重载（override）、拖尾返回类型（trailing return type）、右值引用（rvalue references）、移动构造函数（move constructors）/移动赋值（move assignment）、作用域枚举（scoped enums）、常量表达式（constexpr）和文字类型（literal types）、列表初始化（list initialization）、授权（delegating）和继承构造器（inherited constructors）、大括号或等号（brace-or-equal）初始化器、空指针（nullptr）、长整型（long long）、char16_t和char32_t、类型别名（type aliases）、可变参数模板（variadic templates）、广义联合体（generalized unions）、广义POD、Unicode字符串文字（Unicode string literals）、自定义文字（user-defined literals）、属性（attributes）、$\lambda$表达式（lambda expressions）、无异常（noexcept）、对齐查询（alignof）和对齐指定（alignas）、多线程内存模型（multithreaded memory model）、线程本地存储（thread-local storage）、GC接口（GC interface）、range for(based on a Boost library)、静态断言［static assertions（based on a Boost library）］ 2.新库特性：原子操作库（atomic operations library）、emplace()和贯穿整个现有库的右值引用的使用、std::initializer_list、状态性的和作用域内的分配器（stateful and scoped allocators）、前向列表（forward_list）、计时库（chrono library）、分数库（ratio library）、新算法（new algorithms）、Unicode conversion facets 3.源自TR1：除了特殊的函数，TR1中全部都被囊括进来 4.源自Boost：线程库（The thread library）、异常指针（exception_ptr）、错误码（error_code）和错误情况（error_condition）、迭代器改进［iterator improvements（std::begin, std::end, std::next, std::prev）］ 5.源自C：C风格的Unicode转换函数 6.搜集错误报告修复：363个错误在2008草案中被解决，另外有322个错误接着被修复。其中的错误包括530号，它使得std::basic_string对象相连。	*****
  2011	十进制浮点技术报告［Decimal floating-point TR (ISO/IEC TR 24733:2011) (ISO Store ) (2009 draft )］	这个TR根据IEEE 754-2008浮点算数标准（Floating Point Arithmetic）：std::decimal::decimal32、std::decimal::decimal64、std::decimal::decimal128
  2012	标准C++基金会成立	The Standard C++ Foundation founded
  2013	《C++编程语言第四版》	The C++ Programming Language, 4th edition
  2014	C++14 (2014 final draft )	1. 新语言特性：变量模板（variable templates）、多态lambda（polymorphic lambdas）、λ动捕获（move capture for lambdas）、new/delete elision、常量表达式函数放宽限制（relax restrictions on constexpr functions）、二值文本（binary literals）、数字分隔符（digit separators）、函数返回类型推演（return type deduction for functions）、用大括号或等号初始符集合初始化类 2. 新库特性：std::make_unique、std::shared_mutex和std::shared_lock、std::index_sequence、std::exchange、std::quoted，还有许多针对现有库的小改进，比如一些算法的双距离重载（two-range overloads for some algorithms）、类型特征的类型别名版本（type alias versions of type traits）、用户定义字符串（user-defined string）、持续期（duration）和复杂数字文本（complex number literals）等等 3.搜集错误报告修复：149号库（149 library issues） 基础库技术规范（Library fundamentals TS）, 文件系统技术规范（Filesystem TS）和其他专业技术规范（ experimental technical specifications）

  不同编译器对c++标准的支持

  cfront x.x就是Bjarne Stroustrup的第一个C++编译器，将C++转换成C语言。在1993年，cfront 4.0因为尝试支持异常机制失败而被取消。我们开发者最长打交道的工具就是编译器了。我们只要通过编写程序语言，编译器会翻译成具体的更底层命令来控制计算机去实现我们的需要的功能。但C++语言标准是一个庞大的特性集合，而不同编译器厂商在根据这个统一标准做编译器的过程中，由于各种原因，不可能支持全部的标准中列举出来的特性。 例如，C++11已经流行多年，很多特性是随着编译器版本release才逐渐支持的，如下图：

  

  • 关于不同编译器对C++不同时期的语言特性的支持程度

  • gnu gcc对C++语言特定的支持情况以及最低支持版本等信息

  参考资料

  • gnu gcc常见问题
  • C++官方的history页面
  • 中文博客C++的历史与现状
  • Feature-Test Macros and Policies
  • 各编译器下载地址，包括vs2017社区版
  Read All

  ---

• 大规模训练数据的shuffle

  2019-12-23

  blog

  机器学习
  • 大规模训练数据的shuffle
    • 重要性
    • 2-pass-shuffle算法
    • 2-pass-shuffle的其他问题处理
    • 如何训练过程中，随机从一个超大数据集合中获取训练数据
    • 参考地址

  大规模训练数据的shuffle

  重要性¹²

  以猫狗分类为例， 假如数据集是

  Dog，Dog，Dog，… ，Dog，Dog，Dog，Cat，Cat，Cat，Cat，… ，Cat，Cat

  所有的狗都在猫前面，如果不shuffle，模型训练一段时间内只看到了Dog，必然会过拟合于Dog，一段时间内又只能看到Cat，必然又过拟合于Cat，这样的模型泛化能力必然很差。 那如果Dog和Cat一直交替，会不会就不过拟合了呢？

  Dog，Cat，Dog，Cat，Dog ，Cat，Dog，…

  依然会过拟合，模型是会记住训练数据路线的，为什么呢？

  当用随机梯度下降法训练神经网络时，通常的做法是洗牌数据。在纠结细节的情况下，让我们用一个极端的例子来解释为什么shuffle是有用的。假设你正在训练一个分类器来区分猫和狗，你的训练集是50,000只猫后面跟着50,000只狗。如果你不洗牌，你的训练成绩就会很差。 严格地说，这个问题是由梯度噪声中的序列相关性和参数更新的不可交换性引起的。首先我们需要明白固定的数据集顺序，意味着给定迭代步，对应此迭代步的训练数据是固定的。 假如目标函数是$J=f(w, b)$，使用梯度下降优化$J$。给定权重取值$w、b$和迭代步step的情况下，固定的数据集顺序意味着固定的训练样本，也就意味着权值更新的方向是固定的，而无顺序的数据集，意味着更新方向是随机的。所以固定的数据集顺序，严重限制了梯度优化方向的可选择性，导致收敛点选择空间严重变少，容易导致过拟合。所以模型是会记住数据路线的，所以shuffle很重要，一定shuffle。

  2-pass-shuffle算法

  我们假设一个数据集$X^m$包含样本数目为$m$, 大小为$S_{X^m}$, 计算内存RAM大小为$S_{RAM}$. 当$S_X \lt S_{RAM}$的时，我们完全可以使用训练框架中的Dataset shuffle函数进行处理,如Fisher Yates Shuffle。但我们实际应用场景中，$S_X \ggg S_{RAM}$. 本节将针对这种业务场景进行讨论。

  # https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle
  def fisher_yates_shuffle(dataset=list()):
  	size = len(dataset)
  	for i in range(size-1):
  		j = random.randint(i, size-1)
  		dataset[i], dataset[j] = dataset[j], dataset[i]
  

  分块是一种很普遍的想法，但是如何分块，以及分块后如何随机地写回到文件中才是最终目标。而且要注意的是，数据集$X^m$的每一次访问都存在大量的IO，将非常耗时。因此，设计随机算法的过程中，IO也要考虑在内。

  2-pass-shuffle算法过程中包括块id的shuffle和块内部的shuffle. Fisher Yates算法和 twice pass shuffle算法如下。

  需要自己设置一个超参数$M$, 直观上需要满足的条件： $M \ge \frac{S_{X^m}}{S_{RAM}}$

  python代码模拟实现如下：

  import os
  import random
  
  # https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle
  def fisher_yates_shuffle(dataset=list()):
  	size = len(dataset)
  	for i in range(size-1):
  		j = random.randint(i, size-1)
  		dataset[i], dataset[j] = dataset[j], dataset[i]
  
  def twice_pass_shuffle(dataset, total_size, M):
  	# first pass
  	p = [[] for _ in range(M)]
  	for i in range(total_size):
  		j = random.randint(0, M-1)
  		p[j].append(dataset[i])
  	# second pass
  	result = []
  	for j in range(M):
  		fisher_yates_shuffle(p[j])
  		result.extend(p[j])
  	return result
  
  if __name__ == '__main__':
  	l = [i for i in range(1,101)]
  	print("befor shuffle:\n", l)
  	result = twice_pass_shuffle(l, total_size=100, M=10)
  	print("\nshuffle result:\n", result)
  

  当我面对这个问题的时候，第一次并没有给出这个答案，第二次才给出接近这个算法的答案。 之前的算法分M块，然后M块之间两两洗牌，进行$\frac{M(M-1)}{2}$次。这个方法看上去好像可以，但是存在以下问题：

  • IO次数太多，性能应该不好
  • 两块之间怎么洗牌的算法决定这shuffle的结果是否随机，而且当时我并没有给出比较好的洗牌策略。

  2-pass-shuffle的其他问题处理

  还有可能遇到的问题就是第一次pass过程中，每个分块的数据并不是相等的，很有可能有那么一两块的大小比$S_{RAM}$大，导致后面不能进行内存内shuffle. 这个问题在how to shuffle a big dataset³这篇文章中有一个解决方案。其实还有简单粗暴的方案就是针对这个特殊的分块进行单独处理，再进行一次类似的2-pass-shuffle就是了。

  如何训练过程中，随机从一个超大数据集合中获取训练数据⁴

  The Dataset.shuffle() implementation is designed for data that could be shuffled in memory; we’re considering whether to add support for external-memory shuffles, but this is in the early stages. In case it works for you, here’s the usual approach we use when the data are too large to fit in memory:

  1. Randomly shuffle the entire data once using a MapReduce/Spark/Beam/etc. job to create a set of roughly equal-sized files (“shards”).
  2. In each epoch:
     • Randomly shuffle the list of shard filenames, using Dataset.list_files(...).shuffle(num_shards).
     • Use dataset.interleave(lambda filename: tf.data.TextLineDataset(filename), cycle_length=N) to mix together records from N different shards.
     • Use dataset.shuffle(B) to shuffle the resulting dataset. Setting B might require some experimentation, but you will probably want to set it to some value larger than the number of records in a single shard.

  参考地址

  1. https://juejin.im/post/5c6b989bf265da2ddd4a5261 “数据集shuffle的重要性” ↩

  2. https://blog.janestreet.com/how-to-shuffle-a-big-dataset/#whyshuffle “why shuffle” ↩

  3. https://blog.janestreet.com/how-to-shuffle-a-big-dataset “how to shuffle a big dataset” ↩

  4. https://github.com/tensorflow/tensorflow/issues/14857 ↩

  Read All

  ---

• Inference Framework based TensorRT

  2019-11-20

  blog

  inference  优化
  • 引言
  • 版本选型与基本概念
    • FP16 INT8
    • PTX
  • TensorRT特性助力高性能算法
    • 优化原理
    • 网络模型的裁剪与重构
    • 低精度计算的支持
    • 硬件方面Tensor Core的支持，优化卷积运算
  • Framework TODO SCHEDULE

  引言

  视觉算法经过几年高速发展，大量的算法被提出。为了能真正将算法在实际应用场景中更好地应用，高性能的 inference框架层出不穷。从手机端上的ncnn到tf-lite，NVIDIA在cudnn之后，推出专用于神经网络推理的TensorRT. 经过几轮迭代，支持的操作逐渐丰富，补充的插件已经基本满足落地的需求。笔者觉得，尤其是tensorrt 5.0之后，无论是接口还是使用samples都变得非常方便集成。

  版本选型与基本概念

  FP16 INT8

  The easiest way to benefit from mixed precision in your application is to take advantage of the support for FP16 and INT8 computation in NVIDIA GPU libraries. Key libraries from the NVIDIA SDK now support a variety of precisions for both computation and storage.

  Table shows the current support for FP16 and INT8 in key CUDA libraries as well as in PTX assembly and CUDA C/C++ intrinsics.

  Feature	FP16x2	INT8/16 DP4A/DP2A
  PTX instructions	CUDA 7.5	CUDA 8
  CUDA C/C++ intrinsics	CUDA 7.5	CUDA 8
  cuBLAS GEMM	CUDA 7.5	CUDA 8
  cuFFT	CUDA 7.5	I/O via cuFFT callbacks
  cuDNN	5.1	6
  TensorRT	v1	v2 Tech Preview

  PTX

  PTX(parallel-thread-execution，并行线程执行) 预编译后GPU代码的一种形式，开发者可以通过编译选项 “-keep”选择输出PTX代码，当然开发人员也可以直接编写PTX级代码。另外，PTX是独立于GPU架构的，因此可以重用相同的代码适用于不同的GPU架构。 具体可参考CUDA-PDF之《PTX ISA reference document》

  建议我们的CUDA 版本为CUDA 8.0以上, 显卡至少为GeForce 1060, 如果想支持Int8/DP4A等feature，还是需要RTX 1080或者P40。

  TensorRT特性助力高性能算法

  优化原理

  

  网络模型的裁剪与重构

  

  

  The above figures explain the vertical fusion optimization that TRT does. The Convolution (C), Bias(B) and Activation(R, ReLU in this case) are all collapsed into one single node (implementation wise this would mean a single CUDA kernel launch for C, B and R).

  

  There is also a horizontal fusion where if multiple nodes with same operation are feeding to multiple nodes then it is converted to one single node feeding multiple nodes. The three 1x1 CBRs are fused to one and their output is directed to appropriate nodes. Other optimizations Apart from the graph optimizations, TRT, through experiments and based on parameters like batch size, convolution kernel(filter) sizes, chooses efficient algorithms and kernels(CUDA kernels) for operations in network.

  低精度计算的支持

  • FP16 & Int8指令的支持
  • DP4A(Dot Product of 4 8-bits Accumulated to a 32-bit)

  TensorRT 进行优化的方式是 DP4A (Dot Product of 4 8-bits Accumulated to a 32-bit)，如下图：

  这是PASCAL 系列GPU的硬件指令，INT8卷积就是使用这种方式进行的卷积计算。更多关于DP4A的信息可以参考Mixed-Precision Programming with CUDA 8

  INT8 vector dot products (DP4A) improve the efficiency of radio astronomy cross-correlation by a large factor compared to FP32 computation.

  

  硬件方面Tensor Core的支持，优化卷积运算

  这个需要硬件的支持，如果没有类似Volta架构的GPU就不要强求。

  Framework TODO SCHEDULE

  • model load sample 模型初始化当前包括通过parser初始化和通过模型流初始化的方式。通过parser初始化过程相比较来说比较慢，因为包含parser过程
    • caffe model
    • gie model
  • plugin & extend layers
    • 设计plugin的管理机制,更新初始化流程
    • interp
    • ROIPooling
    • RPNProposal
    • PriorBox
    • ChannelShuffle
    • CTC
    • SLLSTM
  • int8 quantity inference
    • 矫正算法的设计
    • 量化数据集合的管理，这个可以和NNIE的量化数据统一起来管理
    • 与研究侧共同确定各个层量化的范围
    • 最后更新inference模式
  Read All

  ---

• 自然场景文本检测与识别

  2019-08-09

  blog

  OCR
  • 引言
  • 经典算法在OCR应用中的问题
  • 开源数据集合
  • SWT算子
    • Step 1：利用canny算子检测图片的边界
    • Step 2：笔画宽度变换（Stroke Width Transform）
    • Step 3：通过SWT图像得到多个连通域
    • Step 4：过滤连通域
    • Step 5：将连通域合并得到文本行
  • 最大极值稳定区域MSER分析
  • HMM & CTC
    • 问题
    • 引入CTC
    • 从网络输出到连续标签
    • 构建分类器
      • 最佳路径解码
      • 前缀解码
  • CTC网络训练
    • CTC前向传播算法
    • 反向传播算法
    • 最大似然训练
  • RLSTM(Reverse LSTM)
    • Reverse LSTM
  • ChannelShuffle

  引言

  基于深度学习算法的的自然场景文本检测，经过几年的研究，针对解决实际问题中的某些问题，涌现出CTC, LSTM等大量的单元。在深度学习之前，已经有大量的优秀工作如SWT，MSER等算法被提出，这里我将先对一些OCR领域的经典作品进行介绍，然后再引入OCR中的深度学习算法。

  经典算法在OCR应用中的问题¹

  • 文本定位，尤其是非水平的文本定位问题，例如SWT算子是比较常用的文本定位算法，但针对非水平文本定位存在一定的局限性。
  • 无法处理序列不定长的问题
  • 文字大小不一的问题

  开源数据集合

  

  

  SWT算子²

  • Paper: Detecting Text in Natural Scenes with Stroke Width Transform
  • github: https://github.com/aperrau/DetectText

  下面根据原文的结构和上述提供的代码详细的解读一下该算法。总的来说该算法分为四步：

  • 利用canny算子检测图片的边界
  • 笔画宽度变换-Stroke Width Transform（这一步输出的图像我们称为SWT图像）
  • 通过SWT图像得到多个连通域
  • 通过自定义的规则过滤一些连通域，得到候选连通域
  • 将连通域合并得到文本行

  Step 1：利用canny算子检测图片的边界

  这步不用多说，基础的图像处理知识，利用OpenCV 的Canny函数可以得到图片边缘检测的结果。

  Step 2：笔画宽度变换（Stroke Width Transform）

  这一步输出图像和输入图像大小一样，只是输出图像像素为笔画的宽度，具体如下。

  如上图所示，通过边缘检测得到上图a，假设现在从边缘上的点p开始，根据p点梯度的反方向找到边缘另一边的点q，如果p点的梯度与q点梯度的反方向夹角在$\pm\pi/6$之间，那么这两点间的距离为一个笔画宽度，那么p点和q点以及它们之间的像素在SWT输出图像中对应位置的值为p和q点的距离大小。

  按照上述的计算方法会有两种情况需要考虑。如下图所示，

  

  下图a表示一个笔画中的像素可能得到两个笔画宽度，这种情况下将红点出的笔画宽度设置为最小的那个值，下图b表示当一个笔画出现更为复杂情况，b图中的红点计算出的两个笔画宽度用两个红线表示，这两红线都无法真正表示笔画的宽度，这时候笔画宽度取这里面所有像素计算得到的笔画宽度的中值作为红点出的笔画宽度。

  因为有文字比背景更亮和背景比文字更亮两种情况，这样会导致边缘的梯度方向相反，所以这一个步骤要执行两遍。这个步骤结束后得到一张SWT图像。

  Step 3：通过SWT图像得到多个连通域

  在通过上述步骤得到SWT输出图像后，该图像大小与原图像大小一致，图像中的像素值为对应像素所在笔画的宽度（下面称为SWT值）。现将相邻像素SWT值比不超过3.0的归为一个连通域。这样就能得到多个连通域。

  Step 4：过滤连通域

  上述步骤输出的多个连通域中，并不是所有的连通域都被认为是笔画候选区域，需要过滤一些噪声的影响，过滤的规则有：

  • 如果某连通域的方差过大（方差大于连通域的一半为方差过大为过大），则认为该连通域不是有效的
  • 如果某连通域过大（宽大于300）或者过小（宽小于10），则认为该连通域不是有效的（代码中只过滤了过大的连通域，连通域的长宽为连通域外接矩形的长宽）
  • 如果某连通域的长宽比不在0.1-10的范围内，则认为该连通域不是有效的（连通域的长宽为连通域外接矩形的长宽）
  • 如果某连通域的外接矩形包含其他两个连通域，则认为该连通域不是有效的（代码中判定，如果某个连通域的外接矩形包含两个或两个以上连通域外接矩形的中心时，认为其包含了两个连通域） 上述条件都满足的连通域，认为是笔画候选区域，用于输入给下一步操作。

  Step 5：将连通域合并得到文本行

  文中认为，在自然场景中，一般不会只有单个字母出现，所有将连通域合并为文本有利于进一步将噪声排除。

  当两个连通域满足下面条件时，认为这两个连通域是一对：

  • 两个连通域中值的比小于2.0（连通域中值，指的是连通域中所有像素值的中值）
  • 两个连通域高的比小于2.0（连通域的高，指其外界矩形的高）
  • 两个连通域之间的距离小于较宽的连通域宽度的3倍（连通域之间的距离为连通域外界矩形中心点之间的距离）
  • 两个连通域的颜色相似（代码用两个连通域对应于原图区域的像素均值代表该连通域的颜色）

  得到两两连通域组成的多对连通域后，如果有两对连通域有共享的连通域，共享的连通域都在连通域对的一端（即连通域的首端或者尾端），且方向相同（方向用一个连通域中心到另一个连通域中心的方向），就将这两对连通域合并为一个新的连通域组，依次进行，知道没有连通域对需要合并则合并结束。

  最后将合并完的结果中滤除小于3的连通域的连通域组得到的最终结果，认为是一行文字。

  最大极值稳定区域MSER分析³

  最大稳定极值区域MSER是一种类似分水岭图像的分割与匹配算法，它具有仿射不变性。极值区域反映的就是集合中的像素灰度值总大于或小于其邻域区域像素的灰度值。对于最大稳定区域，通过局部阈值集操作，区域内的像素数量变化是最小的。

  MSER的基本原理是对一幅灰度图像（灰度值为0～255）取阈值进行二值化处理，阈值从0到255依次递增。阈值的递增类似于分水岭算法中的水面的上升，随着水面的上升，有一些较矮的丘陵会被淹没，如果从天空往下看，则大地分为陆地和水域两个部分，这类似于二值图像。在得到的所有二值图像中，图像中的某些连通区域变化很小，甚至没有变化，则该区域就被称为最大稳定极值区域。这类似于当水面持续上升的时候，有些被水淹没的地方的面积没有变化。

  上述做法只能检测出灰度图像的黑色区域，不能检测出白色区域，因此还需要对原图进行反转，然后再进行阈值从0～255的二值化处理过程。这两种操作又分别称为MSER+和MSER-。

  MSER是当前认为性能最好的仿射不变性区域的检测方法，其使用不同灰度阈值对图像进行二值化来得到最稳定区域，表现特征有以下三点：

  • 对图像灰度仿射变化具有不变性，
  • 对区域支持相对灰度变化具有稳定性，
  • 对区域不同精细程度的大小区域都能进行检测。

  MSER最大极值稳定区域的提取步骤：

  • 像素点排序
  • 极值区域生成
  • 稳定区域判定
  • 区域拟合
  • 区域归一化

  HMM & CTC

  问题

  序列学习任务需要从未分割的输入数据中预测序列的结果。HMM模型与CRF模型是序列标签任务中主要使用的框架，这些方法对于许多问题已经获得了较好的效果，但是它们也有缺点：

  • 需要大量任务相关的知识，例如，HMM中的状态模型，CRF中的输入特征选择
  • 需要有独立性假设作为支撑；
  • 对于标准的HMM模型，它是生成式的，但是序列标签时判别式的。

  RNN网络除了输入与输出的表达方式需要选择之外不需要任何数据的先验。 它可以进行判别训练，它的内部状态为构建时间序列提供了强大的通用机制。 此外，其对时间和空间噪声具有很强的鲁棒性。

  但是对于RNN呢，它是不能拿来做序列预测的，这是因为RNN只能去预测一些独立标签的分类，因而就需要进行序列预分割。要解决该问题，那么将RNN与HMM结合起来被称之为hybrid approach。在该方法中使用HMM为长序列结构数据建立模型，神经网络就提供局部分类。加入HMM之后可以使得在训练中自动分割序列，并且将原本的网络分类转换到标签序列。然而，它并没有避免上述内容中HMM使用缺点。

  引入CTC

  CTC( Connectionist Temporal Classification)，可以解决前面提到的两点局限，直接使用序列进行训练。CTC引入了一个新的损失函数，可以使得RNN网络可以直接使用未切分的序列记性训练。为了使用这个损失函数， 为RNN引入其可以输出的”BLANK”标签, RNN的输出是所有标签的概率。 这里将Temporal Classification定义为$h$，训练数据集合$S$中数据是成对存在的$(\mathbf{x},z)$，其中$\mathbf{x}$是训练的时序数据，$z$是标签数据。目标就是找到一个时序分类器$h$使得$S$中的$x$被分类到$z$。训练这个分类器，就需要一个错误度量，这里就借鉴了编辑（ED）距离度量，而引入了label error rate（LER）。在这里还对其进行了归一化，从而得到了如下的形式：

  $$LER(h, S) = \frac{1}{Z}\sum_{(\mathbf{x},z)\in S} ED(h(\mathbf{x}))$$

  将网络输出转换成为基于标签序列的条件概率，从而可以使用分类器对输入按照概率大小进行分类。

  从网络输出到连续标签

  在CTC网络中拥有一个$softmax$输出层，其输出的个数为$∣L∣+1$，$L$是标签元素的集合，额外的一个那当然就是”BLANK”标签了。这些输出定义了将所有可能的标签序列与输入序列对齐的所有可能路径的概率。任何一个标签序列的总概率可以通过对其不同排列的概率求和得到。 首先对于一条可行的路径$p(\pi|x)$被定义为对应路径上的各个时刻输出预测概率的乘积。其定义如下：

  $$p(\pi|x) = \prod^T_{t=1}y_{\pi_t}^t, \quad \forall \pi \in L'^T$$

  对于预测结果中的一条路径的标签，论文中假设这些不同时刻网络的输出是相互独立的，而这种独立性是通过输出层与自身或网络之间不存在反馈连接来确保实现的。

  在此基础上还定义了映射函数$B$，它的职责就是去除”BLANK”与重复的标签。因而给定的一个标签其输出概率就可以描述为几个可行路径相加和的形式:

  $$p(l|\mathbf{x}) = \sum_{\pi \in B^{-1}(l)} p(\pi|\mathbf{x})$$

  构建分类器

  从上面的内容中已经得到了一个序列标签的输出条件概率，那么怎么才能找到输入数据最匹配的标签呢？最为直观的便是求解

  $$h(X) = \arg\max_{l\in L \le T} p(l|\mathbf{x})$$

  在给定输入情况下找到其最可能的标签序列，这样的过程使用HMM中的术语叫做解码。目前，还没有一种通过易理解的解码算法，但下面的两种方法在实践过程中也取得了不错的效果。

  最佳路径解码

  该方法是建立在概率最大的路径与最可能的标签时对应的，因而分类器就被描述为如下形式：

  $$h(\mathbf{x}) \approx B(\pi^*)$$ $$where\quad \pi^* = \arg\max_{\pi \in N^t}p(\pi|\mathbf{x})$$

  从上面的形式中就可以看出，最佳路径解码的计算式很容易的，因为最佳路径中的元素是各个时刻输出的级联。但是呢，这是不能保证找到最可能的标签的。

  前缀解码

  前缀解码在足够时间的情况下会找到最可能的标签，但是随着输入序列长度的增强时间也会指数增加。如果输入的概率分布是尖状的，那么可以在合理的时间内找到最可能的路径。

  实践中，前缀搜索在这个启发式下工作得很好，通常超过了最佳路径解码，但是在有些情况下，效果不佳。

  CTC网络训练

  目标函数是由极大似然原理导出的。也就是说，最小化它可以最大化目标标签的对数可能性。有了损失函数之后就可以使用依靠梯度进行优化的算法进行最优化。

  CTC在网络中放置在双向递归网络的后面作为序列预测的损失来源。CTC会在RNN网络中传播梯度，进而使得其学习一条好路径。

  CTC前向传播算法

  需要一种有效的方法来计算单个标签的条件概率$p(l|\mathbf{x})$。对于这样的问题，其实就是对应于给定标签的所有路径的综合。通常有很多这样的路径。这里我们采用动态规划的算法计算所有可能路径的概率和，其思想是，与标签对应的路径和可以分解为与标签前缀对应的路径的迭代和。 然后，可以使用递归向前和向后变量有效地计算迭代。 以下是本文设计到的一些符号定义：

  • $y_{k}^{t}$, 时刻t的输出字符$k$
  • $l$, 标签序列对应的损失。
  • $l^{\prime}$，相同的标签序列，但是在字符之间添加了”BLANK”标签

  $$\alpha_t(s) \overset{def}{=} \sum_{\pi \in N^T: \atop B(\pi_{1:t}) = l_{1:s}} \prod^t_{t^{\prime} = 1} y_{\pi_{t^{\prime}}}^{t^{\prime}}.$$

  其中B是溢出所有”BLANK”与重复字符的变换；${\pi \in N^T:B(\pi_{1:t}) = l_{1:s}}$ 是时刻1到t的预测矩阵中，给出经过变换$B$之后与标签有前s个一致的所有可行路径；$y^{t^{\prime}}$ 是指时刻$t^{\prime}$时RNN的输出。而且$\alpha_{t}(s)$可以通过$\alpha_{t-1}(s)$与$\alpha_{t-1}(s-1)$迭代计算出来。

  图3中描述的状态转移图与上面公式的含义是相同的。为了能够在输出路径中出现”BLANK”标签，将标签修改成了$l^{\prime}$，也就是在标签的前后与字符之前插入空白标签，因而生成的标签长度就变成了$2|l|+1$的长度，使其可以再空白标签与非空白标签之间转换，也可以使非空白标签之间发生转换。 上面的公式1中已经给出了其计算的内容，但其计算并不具有可行性。但是可以根据图3中$\alpha_{t}(s)$的递归定义使用动态规划算法去解决该问题，仔细看这幅图，是不是有点像HMM的前向计算过程。

  对于解决该问题使用动态规划的算法进行解决，首先来分析时刻1时候的情况：

  $$\alpha_1(1) = y_b^1$$ $$\alpha_1(2) = y_{l^{\prime}}^1$$ $$\alpha_1(s) = 0, \forall s > 2$$ $$\alpha_t(s) = \begin{cases} a_t(s)y_{l_{s}^{\prime}}^t, \quad if\quad l_s^{\prime} = b\quad or\quad l_{s-2}^{\prime} = l_s^{\prime}\\ (\bar{\alpha_t}(s) +\alpha_{t-1}(s -2))y_{l_{s}^{\prime}}^t, \quad otherwise \end{cases}$$

  where $\alpha_t(s) \overset{def}{=} \alpha_{t-1}(s) + \alpha_{t-1}(s-1)$ 最后就可以得到一个序列的输出概率

  $$p(l|\mathbf{x}) = \alpha_T(|l^{\prime}|) + \alpha_T(|l^{\prime}| -1)$$

  反向传播算法

  反向传播的变量$\beta_{t}(s)$被定义为$t$时刻$l_{s:|l|}$的总概率 $\beta_{t}(s) \stackrel{\mathrm{def}}{=} \sum_{\pi \in N^{T} \atop \mathcal{B}(\pi_{t : T}) = l_{s:|l|}} \prod_{t^{\prime}=t}^{T} y_{\pi_{t^{\prime}}^{\prime}}^{t^{\prime}}$

  $$\beta_{T}\left(\left|\mathbf{l}^{\prime}\right|\right)=y_{b}^{T} \\ \beta_{T}\left(\left|\mathbf{l}^{\prime}\right|-1\right)=y_{l_{|l|}}^{T} \\ \beta_{T}(s)=0, \quad \forall s<\left|\mathbf{l}^{\prime}\right|-1 \\ \beta_{t}(s)=\left\{ \begin{array}{ll}{ \overline{\beta}_{t}(s) y_{1 s}^{t}} & {\text { if } 1_{s}^{\prime}=b \text { or } 1_{s+2}^{\prime}=1_{s}^{\prime}} \\ {\left(\overline{\beta}_{t}(s)+\beta_{t+1}(s+2)\right) y_{1_{s}^{t}}} & {\text { otherwise }} \end{array} \right.$$ $$\begin{array}{l}{ \text {where}} {\quad\overline{\beta}_{t}(s) \stackrel{\mathrm{def}}{=} \beta_{t+1}(s)+\beta_{t+1}(s+1)} \end{array}$$

  最大似然训练

  最大似然训练的目的是同时最大化训练集中所有正确分类的对数概率。因而这里可以将损失函数定义为：

  $$O^{M L}\left(S, \mathcal{N}_{w}\right)=-\sum_{(\mathbf{x}, \mathbf{z}) \in S} \ln (p(\mathbf{z} | \mathbf{x}))$$

  为了使用梯度进行网络训练，因而就需要对网络的输出进行微分，且训练样本是相互独立的，也就是说可以单独考虑了，因而可以将微分写为：

  $$\frac{\partial O^{M L}\left(\{(\mathbf{x}, \mathbf{z})\}, \mathcal{N}_{w}\right)}{\partial y_{k}^{t}}=-\frac{\partial \ln (p(\mathbf{z} | \mathbf{x}))}{\partial y_{k}^{t}}$$

  这里可以用前向后向算法计算上式。主要思想是：对于一个标记l，在给定s和t的情况下，前向和后向变量的内积是对应l所有可能路径的概率。表达式为：

  $$\alpha_{t}(s) \beta_{t}(s)=\sum_{\pi \in \mathcal{B}^{-1}(1) : \atop {\pi_t = l_s^{\prime}}} y_{1_{s}}^{t} \prod_{t=1}^{T} y_{\pi_{t}}^{t}$$

  且根据上面的公式（2）联合可以得到：

  $$\frac{\alpha_{t}(s) \beta_{t}(s)}{y_{1_{s}^{t}}^{t}}=\sum_{\pi \in \mathcal{B}^{-1}(1): \atop {\pi_t = l_s^{\prime}}} p(\pi | \mathbf{x})$$

  再与前面的公式（3）联合可以得到

  $$p(\mathbf{l} | \mathbf{x})=\sum_{s=1}^{\left|\mathbf{l}^{\prime}\right|} \frac{\alpha_{t}(s) \beta_{t}(s)}{y_{1_{s}^{\prime}}^{t}}$$

  RLSTM(Reverse LSTM)

  • RNN⁴
  • LSTM⁵⁶

  Reverse LSTM

  整体架构如下，其中需要用到Reverse这种Layer

  

  ChannelShuffle

  

  一般的分组卷积(如ResNeXt的)仅对$3\times3$的层进行了分组操作，然而$1\times1$的pointwise卷积占据了绝大多数的乘加操作，在小模型中为了减少运算量只能减少通道数，然而减少通道数会大幅损害模型精度。作者提出了对$1\times1$也进行分组操作，但是如图１(a)所示，输出只由部分输入通道决定。为了解决这个问题，作者提出了图(c)中的通道混淆(channel shuffle)操作来分享组间的信息，假设一个卷基层有g groups，每个group有n个channel，因此shuffle后会有$g\times n$个通道，首先将输出的通道维度变形为(g, n)，然后转置(transpose)、展平(flatten)，shuffle操作也是可导的。

  

  图2 (a)是一个将卷积替换为depthwise卷积⁷的residual block，(b)中将两个$1\times1$卷积都换为pointwise group convolution，然后添加了channel shuffle，为了简便，没有在第二个pointwise group convolution后面加channel shuffle。根据Xception的论文，depthwise卷积后面没有使用ReLU。(c)为stride > 1的情况，此时在shotcut path上使用$3\times3$的平均池化，并将加法换做通道concatenation来增加输出通道数(一般的设计中，stride=2的同时输出通道数乘2)。

  对于$c \times h \times w$的输入大小，bottleneck channels为m，则ResNet unit需要$hw(2cm + 9m^2)FLOPs$，ResNeXt需要$hw(2cm + 9m^2/g)FLOPs$，ShuffleNet unit只需要$hw(2cm/g + 9m)FLOPs$，g表示卷积分组数。换句话说，在有限计算资源有限的情况下，ShuffleNet可以使用更宽的特征图，作者发现对于小型网络这很重要。

  即使depthwise卷积理论上只有很少的运算量，但是在移动设备上的实际实现不够高效，和其他密集操作(dense operation)相比，depthwise卷积的computation/memory access ratio很糟糕。因此作者只在bottleneck里实现了depthwise卷积。

  1. https://www.jianshu.com/p/56f8c714f372 “自然场景文本检测识别技术综述” ↩

  2. https://blog.csdn.net/liuxiaoheng1992/article/details/85305871 “SWT博客” ↩

  3. https://www.cnblogs.com/shangd/p/6164916.html “MSER 博客” ↩

  4. https://zybuluo.com/hanbingtao/note/541458 “循环神经网络” ↩

  5. http://colah.github.io/posts/2015-08-Understanding-LSTMs/ “理解LSTM” ↩

  6. https://www.jianshu.com/p/4b4701beba92 “理解LSTM中文” ↩

  7. https://arxiv.org/pdf/1610.02357.pdf “Xception” ↩

  Read All

  ---

• 认识神经网络：卷积，归一化，优化和语料

  2019-07-22

  blog

  深度学习
  • 引言
  • 卷积
    • 认识卷积
    • 卷积的实现
    • 计算复杂度分析
  • Normalization
    • Batch Normalization
    • Layer Normalizaiton
    • Instance Normalization
    • Group Normalization
    • LRN（Local Response Normalization）
    • 参考文献
  • 优化
    • 梯度下降法（Gradient Descent）
    • 参考文献
  • 其他参考文献
    • 深度学习教程
    • 计算平台
  • 常用数据集合
    • 图像类
    • 自然语言处理类
    • 语音类
    • Analytics Vidhya实践问题
    • more dataset

  引言

  一个基于神经网络模型的视觉模型中，卷积和归一化层是最为耗时的两种layer。卷积数据计算密集类型，今年来大量的优化主要集中在各种设备上的卷积加速。 归一化层通过计算一个批量中的均值与方差来进行特征归一化。众多实践证明，它利于优化且使得深度网络易于收敛。批统计的随机不确定性也作为一个有利于泛化的正则化项。BN 已经成为了许多顶级计算机视觉算法的基础。添加归一化层作为提高算法性能的很好的一种策略，但由于像BN遭受数据同步延时的问题，现在逐渐被一些新的normalization方式所替代。

  卷积

  认识卷积

  卷积定义

  $$h(x) = f(x)*g(x) = \int_{ - \infty }^{ + \infty } {f(t)g(x - t)dt}$$

  $f(t)$先不动， $g(-t)$相当于$g(t)$函数的图像沿y轴（t=0）做了一次翻转。$g(x-t)$相当于$g(-t)$的整个图像沿着t轴进行了平移，向右平移了x个单位。他们相乘之后围起来的面积就是$h(x)$。

  离散卷积的定义

  $$h(x) = f(x)*g(x) = \sum_{\tau = -\infty}^{+\infty}f(\tau)g(x-\tau)$$

  其实，深度学习中的卷积对应于数学中的cross correlation. 从卷积的定义来看，我们当前在深度学习中训练的卷积核是翻转之后的卷积核。

  下面是一些介绍卷积的文章和常见卷积类型统计表：

  • A Comprehensive Introduction to Different Types of Convolutions in Deep Learning
  • A Tutorial on Filter Groups (Grouped Convolution)
    • AlexNet
    • MobileNet
  • An Introduction to different Types of Convolutions in Deep Learning
  • Convolution arithmetic
  • Deconvolution and Checkerboard Artifacts

  Convolution Name	参考文献	典型代表	附录
  Convolution		AlexNet, VGG
  1x1	Network in Network	GoogLeNet, Inception	(1). Dimensionality reduction for efficient computations; (2).Efficient low dimensional embedding, or feature pooling; (3). Applying nonlinearity again after convolution
  Dilated convolution	Multi-Scale Context Aggregation by Dilated Convolutions	语义分割	support exponentially expanding receptive fields without losing resolution or coverage. Upsampling/poolinglayer(e.g. bilinear interpolation) is deterministic. (a.k.a. not learnable); 内部数据结构丢失, 空间层级化信息丢失; 小物体信息无法重建 (假设有四个pooling layer则任何小于$2^4=16$pixel的物体信息将理论上无法重建。) 如何理解空洞卷积
  Group Convolution	Deep Roots:Improving CNN Efficiency with Hierarchical Filter Groups	MobileNet, ResNeXt
  Pointwise grouped convolution		ShuffleNet
  Depthwise separable convolution	Xception: Deep Learning with Depthwise Separable Convolutions	Xception	MobileNet是典型的代表，通过该卷积，大大降低了计算复杂度和模型大小。也是现在落地产品中移动端常用的操作。
  Deconvolutions	Deconvolution and Checkerboard Artifacts	DSSD	Deconvolution也是一种常用的上采样方式，在物体分割和多尺度检测都可用到
  Flattened convolutions	Flattened convolutional neural networks for feedforward acceleration		computation costs due to the significant reduction of learning parameters.

  卷积的实现

  计算卷积的方法有很多种，常见的有以下几种方法:

  • 滑窗：这种方法是最直观最简单的方法。但是，该方法不容易实现大规模加速，因此，通常情况下不采用这种方法 (但是也不是绝对不会用，在一些特定的条件下该方法反而是最高效的.)
  • im2col: 目前几乎所有的主流计算框架包括[Caffe]¹, MXNet等都实现了该方法。该方法把整个卷积过程转化成了GEMM过程，而GEMM在各种BLAS库中都是被极致优化的，一般来说，速度较快.
  • FFT: 傅里叶变换和快速傅里叶变化是在经典图像处理里面经常使用的计算方法，但是，在 ConvNet 中通常不采用，主要是因为在 ConvNet 中的卷积模板通常都比较小，例如3×3 等，这种情况下，FFT 的时间开销反而更大.
  • [Winograd]²: Winograd 是存在已久最近被重新发现的方法，在大部分场景中，Winograd 方法都显示和较大的优势，目前cudnn中计算卷积就使用了该方法.

  计算复杂度分析

  • 假设输入$I = R^{C_0H_0W_0}$, 卷积核大小为$k$, 输出$O = R^{C_1H_1W_1}$， 则卷积过程的计算量为：

  $$(k^2C_0*H_1W_1)*C_1$$

  使用Depthwise separable convolution卷积的计算量为:

  $$(k^2*H_1W_1*C_0 + C_0C_1*H_1W_1)$$

  那么计算量之比为

  $$\frac{(k^2*H_1W_1*C_0 + C_0C_1*H_1W_1)}{(k^2C_0*H_1W_1)*C_1} =\frac{1}{C_1} + \frac{1}{k^2} \approx \frac{1}{k^2}$$

  一般情况下，$k^2 « C_1$, 所以当$k=3$的时候，计算量之比约为原来的$\frac{1}{9}$.

  • 假设input的$H_0 = W_0$，用$w$表示，$k$是卷积核的大小，$p$表示填充的大小，$s$表示stride步长

  $$o = \frac{w - k + 2p}{s} + 1$$

  Normalization

  每个子图表示一个feature map张量，以$N$为批处理轴，$C$为通道轴，$(H,W)$作为空间轴。其中蓝色区域内的像素使用相同的均值和方差进行归一化，并通过聚合计算获得这些像素的值。从示意图中可以看出，GN没有在N维度方向上进行拓展，因此batch size之间是独立的，GPU并行化容易得多。

  • batchNorm是在batch上，对NHW做归一化，对小batchsize效果不好；
  • layerNorm在通道方向上，对CHW归一化，主要对RNN作用明显；
  • instanceNorm在图像像素上，对HW做归一化，用在风格化迁移；
  • GroupNorm将channel分组，然后再做归一化；
  • SwitchableNorm是将BN、LN、IN结合，赋予权重，让网络自己去学习归一化层应该使用什么方法。

  Batch Normalization

  需要比较大的Batch Size，需要更强的计算硬件的支持。

  A small batch leads to inaccurate estimation of the batch statistics, and reducing BN’s batch size increases the model error dramatically

  尤其是在某些需要高精度输入的任务中，BN有很大局限性。同时，BN的实现是在Batch size之间进行的，需要大量的数据交换。

  batch normalization存在以下缺点：

  • 对batchsize的大小比较敏感，由于每次计算均值和方差是在一个batch上，所以如果batchsize太小，则计算的均值、方差不足以代表整个数据分布；
  • BN实际使用时需要计算并且保存某一层神经网络batch的均值和方差等统计信息，对于对一个固定深度的前向神经网络（DNN，CNN）使用BN，很方便；但对于RNN来说，sequence的长度是不一致的，换句话说RNN的深度不是固定的，不同的time-step需要保存不同的statics特征，可能存在一个特殊sequence比其他sequence长很多，这样training时，计算很麻烦。（参考于https://blog.csdn.net/lqfarmer/article/details/71439314）

  Layer Normalizaiton

  LN中同层神经元输入拥有相同的均值和方差，不同的输入样本有不同的均值和方差； BN中则针对不同神经元输入计算均值和方差，同一个batch中的输入拥有相同的均值和方差。

  所以，LN不依赖于batch的大小和输入sequence的深度，因此可以用于batchsize为1和RNN中对边长的输入sequence的normalize操作。

  Instance Normalization

  BN注重对每个batch进行归一化，保证数据分布一致，因为判别模型中结果取决于数据整体分布。

  但是图像风格化中，生成结果主要依赖于某个图像实例，所以对整个batch归一化不适合图像风格化中，因而对HW做归一化。可以加速模型收敛，并且保持每个图像实例之间的独立。

  Group Normalization

  GN does not exploit the batch dimension, and its computation is independent of batch sizes.

  从实验结果中可以看出在训练集合上GN的valid error低于BN，但是测试结果上逊色一些。这个 可能是因为BN的均值和方差计算的时候，通过随机批量抽样（stochastic batch sampling）引入了不确定性因素，这有助于模型参数正则化。 而这种不确定性在GN方法中是缺失的，这个将来可能通过使用不同的正则化算法进行改进。

  LRN（Local Response Normalization）

  动机

  在神经深武学有一个概念叫做侧抑制(lateral inhibitio)，指的是被激活的神经元抑制相邻的神经元。 归一化的目的就是“抑制”，局部响应归一化就是借鉴侧抑制的思想来实现局部抑制，尤其是当我们使用ReLU 的时候，这种侧抑制很管用。

  好处

  有利于增加泛化能力，做了平滑处理，识别率提高1~2%

  参考文献

  • Batch Normalization: Accelerating Deep Network Training by Reducing Internal Covariate Shift
  • Jimmy Lei Ba, Jamie Ryan Kiros, Geoffrey E. Hinton. Layer normalization.
  • Group Normalization
  • AlexNet中提出的LRN
  • VGG：Very Deep Convolutional Networks for Large-Scale Image Recognition
  • BatchNormalization、LayerNormalization、InstanceNorm、GroupNorm、SwitchableNorm总结
  • Fast Algorithms for Convolutional Neural Networks

  优化

  梯度下降法（Gradient Descent）

  梯度下降法是最早最简单，也是最为常用的最优化方法。梯度下降法实现简单，当目标函数是凸函数时，梯度下降法的解是全局解。 一般情况下，其解不保证是全局最优解，梯度下降法的速度也未必是最快的。梯度下降法的优化思想是用当前位置负梯度方向作为搜索方向， 因为该方向为当前位置的最快下降方向，所以也被称为是”最速下降法”。最速下降法越接近目标值，步长越小，前进越慢。 梯度下降法的搜索迭代示意图如下图所示：

  

  梯度下降法的缺点：

  • 靠近极小值时收敛速度减慢，如下图所示；
  • 直线搜索时可能会产生一些问题；
  • 可能会“之字形”地下降。

  

  参考文献

  • 梯度下降(gradient descent)
  • 梯度下降优化算法
  • 常见的几种最优化方法

  其他参考文献

  深度学习教程

  CS231n: Convolutional Neural Networks for Visual Recognition.

  计算平台

  1. arm平台
  2. linux上编译arm交叉编译链
  3. How to Build a GCC Cross-Compiler

  常用数据集合

  https://www.analyticsvidhya.com/blog/2018/03/comprehensive-collection-deep-learning-datasets/ 这里我们列出了一组高质量的数据集，研究这些数据集将使你成为一个更好的数据科学家。 我们可以使用这些数据集来学习各种深度学习技术，也可以使用它们来磨练您的技能，理解如何识别和构造每个问题，考虑独特的应用场景!

  图像类

  dataset名称	大小	State-of-Art	描述
  MNIST	50MB	Dynamic Routing Between Capsules	手写数字识别，包含60000个训练数据及10000个测试数据，可分为10类
  MSCOCO	~25G	Mask RCNN	COCO is a large-scale and rich for object detection, segmentation and captioning dataset. 330K images, 1.5 million object instances, 80 object categories, 5 captions per image, 250,000 people with key points
  ImageNet	150GB	ResNeXt	ImageNet is a dataset of images that are organized according to the WordNet hierarchy. WordNet contains approximately 100,000 phrases and ImageNet has provided around 1000 images on average to illustrate each phrase. Number of Records: Total number of images: ~1,500,000; each with multiple bounding boxes and respective class labels
  Open Image Dataset	500GB	ResNet	一个包含近900万个图像URL的数据集。 这些图像拥有数千个类别及边框进行了注释。 该数据集包含9,011219张图像的训练集，41,260张图像的验证集以及125,436张图像的测试集。
  VisualQA	25GB	Tips and Tricks for Visual Question Answering: Learnings from the 2017 Challenge	图像的问答系统数据集 265,016 images, at least 3 questions per image, 10 ground truth answers per question
  The Street View House Numbers(SVHN)	2.5GB	Distributional Smoothing With Virtual Adversarial Training	门牌号数据集，可用来做物体检测与识别
  CIFAR-10	170MB	ShakeDrop regularization	图像识别数据集，包含 50000张训练数据，10000张测试数据，可分为10类
  Fashion-MNIST	30MB	Random Erasing Data Augmentation	包含60000训练样本和10000测试样本的用于服饰识别的数据集，可分为10类。

  自然语言处理类

  dataset名称	大小	State-of-Art	描述
  IMDB 影评数据	80MB	Learning Structured Text Representations	可以实现对情感的分类，除了训练集和测试集示例之外，还有更多未标记的数据。原始文本和预处理的数据也包括在内。25,000 highly polar movie reviews for training, and 25,000 for testing
  Twenty Newsgroups	20MB	Very Deep Convolutional Networks for Text Classification	包含20类新闻的文章信息，内类包含1000条数据
  Sentiment140	80MB	Assessing State-of-the-Art Sentiment Models on State-of-the-Art Sentiment Datasets	1,60,000 tweets,用于情感分析的数据集
  WordNet	10MB	Wordnets: State of the Art and Perspectives	117,000 synsets is linked to other synsets by means of a small number of “conceptual relations.
  Yelp点评数据集	2.66GB JSON文件,2.9GB SQL文件,7.5GB图片数据	Attentive Convolution	包括470万条用户评价，15多万条商户信息，20万张图片，12个大都市。此外，还涵盖110万用户的100万条tips，超过120万条商家属性（如营业时间、是否有停车场、是否可预订和环境等信息），随着时间推移在每家商户签到的总用户数。
  维基百科语料库（英语）	20MB	Breaking The Softmax Bottelneck: A High-Rank RNN language Model	包含4400000篇文章 及19亿单词，可用来做语言建模
  博客作者身份语料库	300MB	Character-level and Multi-channel Convolutional Neural Networks for Large-scale Authorship Attribution	从blogger.com收集到的19,320名博主的博客，其中博主的信息包括博主的ID、性别、年龄、行业及星座
  各种语言的机器翻译数据集	15GB	Attention Is All You Need	包含英-汉、英-法、英-捷克、英语- 爱沙尼亚、英 - 芬兰、英-德、英 - 哈萨克、英 - 俄、英 - 土耳其之间互译的数据集

  语音类

  dataset名称	大小	State-of-Art	描述
  Free Spoken Digit Dataset	10MB	Raw Waveform-based Audio Classification Using Sample-level CNN Architectures	数字语音识别数据集，包含3个人的声音，每个数字说50遍，共1500条数据
  Free Music Archive (FMA)	1000GB	Learning to Recognize Musical Genre from Audio	可以用于对音乐进行分析的数据集，数据集中包含歌曲名称、音乐类型、曲目计数等信息。
  Ballroom	14GB	A Multi-Model Approach To Beat Tracking Considering Heterogeneous Music Styles	舞厅舞曲数据集，可对舞曲风格进行识别。
  Million Song Dataset	280GB	Preliminary Study on a Recommender System for the Million Songs Dataset Challenge	Echo Nest提供的一百万首歌曲的特征数据.该数据集不包含任何音频，但是可以使用他们提供的代码下载音频
  LibriSpeech	60GB	Letter-Based Speech Recognition with Gated ConvNets	包含1000小时采样频率为16Hz的英语语音数据及所对应的文本，可用作语音识别
  VoxCeleb	150MB	VoxCeleb: a large-scale speaker identification dataset]()	大型的说话人识别数据集。 它包含约1,200名来自YouTube视频的约10万个话语。 数据在性别是平衡的（男性占55％）。说话人跨越不同的口音，职业和年龄。 可用来对说话者的身份进行识别。

  Analytics Vidhya实践问题

  • Twitter情绪分析
    • 描述：识别是否包含种族歧视及性别歧视的推文。
    • 大小：3MB
    • 31,962 tweets
  • 印度演员的年龄识别数据集
    • 描述：根据人的面部属性，识别人的年龄的数据集。
    • 大小：48MB
    • 19,906 images in the training set and 6636 in the test set
  • 城市声音分类数据集
    • 描述：该数据集包含来自10个类的城市声音的8732个标记的声音片段，每个片段时间小于4秒。
    • 大小：训练数据集3GB，训练数据集2GB。
    • 8732 labeled sound excerpts (<=4s) of urban sounds from 10 classes

  more dataset

  • 机器之心整理的数据集合
  • DHCD_Dataset

  1. https://github.com/BVLC/caffe/blob/master/src/caffe/util/im2col.cpp ↩

  2. https://arxiv.org/abs/1509.09308v2 ↩

  Read All

  ---