面向对象的三大特征是抽象、继承、多态。《深度探索C++对象模型》一书中从数据的排布,C++对象函数的调用设计等等。 我尝试以一个编译器的设计者的角度去理解C++对象,该书中也提到了多种编译器,有的时候也会涉及一些不同编译器厂商在设计过程中的不同,虽然没有深入探究不同的原因以及优劣对比, 但对于我这个新手来说已经开了很大的窗户。
整个书籍通过横向切割方式,分别从构造、数据成员、成员函数、运行时C++对象的特点来介绍,从缔造者的视角来理解C++对象的设计,有利于我们写出更加高效、简洁的程序。
封装的后布局成本与C struct是一样的。member functions虽然旱灾class的声明之内,却不出现在的object中。每一个non-inline memberfunction 只会诞生一个函数实例。 C++在布局以及存取时间上的主要的额外负担是由virtual引起的,包括:
在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 函数,则通过虚函数表+虚指针来支持,具体如下:
这个模型的优点在于它的空间和存取时间的效率;缺点如下:如果应用程序本身未改变,但当所使用的类的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)
在阅读C++相关的技术书籍或博客时,常常会提到一些日常开发中不常接触的名词,如cfront 2.0或者TR1等,这些名词在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) |
cfront x.x就是Bjarne Stroustrup的第一个C++编译器,将C++转换成C语言。在1993年,cfront 4.0因为尝试支持异常机制失败而被取消。我们开发者最长打交道的工具就是编译器了。我们只要通过编写程序语言,编译器会翻译成具体的更底层命令来控制计算机去实现我们的需要的功能。但C++语言标准是一个庞大的特性集合,而不同编译器厂商在根据这个统一标准做编译器的过程中,由于各种原因,不可能支持全部的标准中列举出来的特性。 例如,C++11已经流行多年,很多特性是随着编译器版本release才逐渐支持的,如下图:
以猫狗分类为例, 假如数据集是
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。
我们假设一个数据集$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$, 直观上需要满足的条件:
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}$次。这个方法看上去好像可以,但是存在以下问题:
还有可能遇到的问题就是第一次pass过程中,每个分块的数据并不是相等的,很有可能有那么一两块的大小比$S_{RAM}$大,导致后面不能进行内存内shuffle. 这个问题在how to shuffle a big dataset3这篇文章中有一个解决方案。其实还有简单粗暴的方案就是针对这个特殊的分块进行单独处理,再进行一次类似的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:
Dataset.list_files(...).shuffle(num_shards)
.dataset.interleave(lambda filename: tf.data.TextLineDataset(filename), cycle_length=N)
to mix together records from N
different shards.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.视觉算法经过几年高速发展,大量的算法被提出。为了能真正将算法在实际应用场景中更好地应用,高性能的 inference框架层出不穷。从手机端上的ncnn到tf-lite,NVIDIA在cudnn之后,推出专用于神经网络推理的TensorRT. 经过几轮迭代,支持的操作逐渐丰富,补充的插件已经基本满足落地的需求。笔者觉得,尤其是tensorrt 5.0之后,无论是接口还是使用samples都变得非常方便集成。
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(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
。
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.
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.
这个需要硬件的支持,如果没有类似Volta架构的GPU就不要强求。
基于深度学习算法的的自然场景文本检测,经过几年的研究,针对解决实际问题中的某些问题,涌现出CTC, LSTM等大量的单元。在深度学习之前,已经有大量的优秀工作如SWT,MSER等算法被提出,这里我将先对一些OCR领域的经典作品进行介绍,然后再引入OCR中的深度学习算法。
Paper: Detecting Text in Natural Scenes with Stroke Width Transform
github: https://github.com/aperrau/DetectText
下面根据原文的结构和上述提供的代码详细的解读一下该算法。总的来说该算法分为四步:
canny
算子检测图片的边界SWT
图像得到多个连通域这步不用多说,基础的图像处理知识,利用OpenCV 的Canny函数可以得到图片边缘检测的结果。
这一步输出图像和输入图像大小一样,只是输出图像像素为笔画的宽度,具体如下。
如上图所示,通过边缘检测得到上图a,假设现在从边缘上的点p开始,根据p点梯度的反方向找到边缘另一边的点q,如果p点的梯度与q点梯度的反方向夹角在$\pm\pi/6$之间,那么这两点间的距离为一个笔画宽度,那么p点和q点以及它们之间的像素在SWT输出图像中对应位置的值为p和q点的距离大小。
按照上述的计算方法会有两种情况需要考虑。如下图所示,
下图a表示一个笔画中的像素可能得到两个笔画宽度,这种情况下将红点出的笔画宽度设置为最小的那个值,下图b表示当一个笔画出现更为复杂情况,b图中的红点计算出的两个笔画宽度用两个红线表示,这两红线都无法真正表示笔画的宽度,这时候笔画宽度取这里面所有像素计算得到的笔画宽度的中值作为红点出的笔画宽度。
因为有文字比背景更亮和背景比文字更亮两种情况,这样会导致边缘的梯度方向相反,所以这一个步骤要执行两遍。这个步骤结束后得到一张SWT图像。
在通过上述步骤得到SWT输出图像后,该图像大小与原图像大小一致,图像中的像素值为对应像素所在笔画的宽度(下面称为SWT值)。现将相邻像素SWT值比不超过3.0的归为一个连通域。这样就能得到多个连通域。
上述步骤输出的多个连通域中,并不是所有的连通域都被认为是笔画候选区域,需要过滤一些噪声的影响,过滤的规则有:
文中认为,在自然场景中,一般不会只有单个字母出现,所有将连通域合并为文本有利于进一步将噪声排除。
当两个连通域满足下面条件时,认为这两个连通域是一对:
得到两两连通域组成的多对连通域后,如果有两对连通域有共享的连通域,共享的连通域都在连通域对的一端(即连通域的首端或者尾端),且方向相同(方向用一个连通域中心到另一个连通域中心的方向),就将这两对连通域合并为一个新的连通域组,依次进行,知道没有连通域对需要合并则合并结束。
最后将合并完的结果中滤除小于3的连通域的连通域组得到的最终结果,认为是一行文字。
最大稳定极值区域MSER是一种类似分水岭图像的分割与匹配算法,它具有仿射不变性。极值区域反映的就是集合中的像素灰度值总大于或小于其邻域区域像素的灰度值。对于最大稳定区域,通过局部阈值集操作,区域内的像素数量变化是最小的。
MSER的基本原理是对一幅灰度图像(灰度值为0~255)取阈值进行二值化处理,阈值从0到255依次递增。阈值的递增类似于分水岭算法中的水面的上升,随着水面的上升,有一些较矮的丘陵会被淹没,如果从天空往下看,则大地分为陆地和水域两个部分,这类似于二值图像。在得到的所有二值图像中,图像中的某些连通区域变化很小,甚至没有变化,则该区域就被称为最大稳定极值区域。这类似于当水面持续上升的时候,有些被水淹没的地方的面积没有变化。
上述做法只能检测出灰度图像的黑色区域,不能检测出白色区域,因此还需要对原图进行反转,然后再进行阈值从0~255的二值化处理过程。这两种操作又分别称为MSER+和MSER-。
MSER是当前认为性能最好的仿射不变性区域的检测方法,其使用不同灰度阈值对图像进行二值化来得到最稳定区域,表现特征有以下三点:
MSER最大极值稳定区域的提取步骤:
序列学习任务需要从未分割的输入数据中预测序列的结果。HMM模型与CRF模型是序列标签任务中主要使用的框架,这些方法对于许多问题已经获得了较好的效果,但是它们也有缺点:
RNN网络除了输入与输出的表达方式需要选择之外不需要任何数据的先验。 它可以进行判别训练,它的内部状态为构建时间序列提供了强大的通用机制。 此外,其对时间和空间噪声具有很强的鲁棒性。
但是对于RNN呢,它是不能拿来做序列预测的,这是因为RNN只能去预测一些独立标签的分类,因而就需要进行序列预分割。要解决该问题,那么将RNN与HMM结合起来被称之为hybrid approach。在该方法中使用HMM为长序列结构数据建立模型,神经网络就提供局部分类。加入HMM之后可以使得在训练中自动分割序列,并且将原本的网络分类转换到标签序列。然而,它并没有避免上述内容中HMM使用缺点。
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)。在这里还对其进行了归一化,从而得到了如下的形式:
将网络输出转换成为基于标签序列的条件概率,从而可以使用分类器对输入按照概率大小进行分类。
在CTC网络中拥有一个$softmax$输出层,其输出的个数为$∣L∣+1$,$L$是标签元素的集合,额外的一个那当然就是”BLANK”标签了。这些输出定义了将所有可能的标签序列与输入序列对齐的所有可能路径的概率。任何一个标签序列的总概率可以通过对其不同排列的概率求和得到。 首先对于一条可行的路径$p(\pi|x)$被定义为对应路径上的各个时刻输出预测概率的乘积。其定义如下:
对于预测结果中的一条路径的标签,论文中假设这些不同时刻网络的输出是相互独立的,而这种独立性是通过输出层与自身或网络之间不存在反馈连接来确保实现的。
在此基础上还定义了映射函数$B$,它的职责就是去除”BLANK”与重复的标签。因而给定的一个标签其输出概率就可以描述为几个可行路径相加和的形式:
从上面的内容中已经得到了一个序列标签的输出条件概率,那么怎么才能找到输入数据最匹配的标签呢?最为直观的便是求解
在给定输入情况下找到其最可能的标签序列,这样的过程使用HMM中的术语叫做解码。目前,还没有一种通过易理解的解码算法,但下面的两种方法在实践过程中也取得了不错的效果。
该方法是建立在概率最大的路径与最可能的标签时对应的,因而分类器就被描述为如下形式:
从上面的形式中就可以看出,最佳路径解码的计算式很容易的,因为最佳路径中的元素是各个时刻输出的级联。但是呢,这是不能保证找到最可能的标签的。
前缀解码在足够时间的情况下会找到最可能的标签,但是随着输入序列长度的增强时间也会指数增加。如果输入的概率分布是尖状的,那么可以在合理的时间内找到最可能的路径。
实践中,前缀搜索在这个启发式下工作得很好,通常超过了最佳路径解码,但是在有些情况下,效果不佳。
目标函数是由极大似然原理导出的。也就是说,最小化它可以最大化目标标签的对数可能性。有了损失函数之后就可以使用依靠梯度进行优化的算法进行最优化。
CTC在网络中放置在双向递归网络的后面作为序列预测的损失来源。CTC会在RNN网络中传播梯度,进而使得其学习一条好路径。
需要一种有效的方法来计算单个标签的条件概率$p(l|\mathbf{x})$。对于这样的问题,其实就是对应于给定标签的所有路径的综合。通常有很多这样的路径。这里我们采用动态规划的算法计算所有可能路径的概率和,其思想是,与标签对应的路径和可以分解为与标签前缀对应的路径的迭代和。 然后,可以使用递归向前和向后变量有效地计算迭代。 以下是本文设计到的一些符号定义:
其中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时候的情况:
where $\alpha_t(s) \overset{def}{=} \alpha_{t-1}(s) + \alpha_{t-1}(s-1)$ 最后就可以得到一个序列的输出概率
反向传播的变量$\beta_{t}(s)$被定义为$t$时刻$l_{s:|l|}$的总概率
最大似然训练的目的是同时最大化训练集中所有正确分类的对数概率。因而这里可以将损失函数定义为:
为了使用梯度进行网络训练,因而就需要对网络的输出进行微分,且训练样本是相互独立的,也就是说可以单独考虑了,因而可以将微分写为:
这里可以用前向后向算法计算上式。主要思想是:对于一个标记l,在给定s和t的情况下,前向和后向变量的内积是对应l所有可能路径的概率。表达式为:
且根据上面的公式(2)联合可以得到:
再与前面的公式(3)联合可以得到
整体架构如下,其中需要用到Reverse这种Layer
一般的分组卷积(如ResNeXt的)仅对$3\times3$的层进行了分组操作,然而$1\times1$的pointwise卷积占据了绝大多数的乘加操作,在小模型中为了减少运算量只能减少通道数,然而减少通道数会大幅损害模型精度。作者提出了对$1\times1$也进行分组操作,但是如图1(a)所示,输出只由部分输入通道决定。为了解决这个问题,作者提出了图(c)中的通道混淆(channel shuffle)操作来分享组间的信息,假设一个卷基层有g groups,每个group有n个channel,因此shuffle后会有$g\times n$个通道,首先将输出的通道维度变形为(g, n),然后转置(transpose)、展平(flatten),shuffle操作也是可导的。
图2 (a)是一个将卷积替换为depthwise卷积7的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卷积。
https://www.jianshu.com/p/56f8c714f372 “自然场景文本检测识别技术综述” ↩
https://blog.csdn.net/liuxiaoheng1992/article/details/85305871 “SWT博客” ↩
https://www.cnblogs.com/shangd/p/6164916.html “MSER 博客” ↩
https://zybuluo.com/hanbingtao/note/541458 “循环神经网络” ↩
http://colah.github.io/posts/2015-08-Understanding-LSTMs/ “理解LSTM” ↩
https://www.jianshu.com/p/4b4701beba92 “理解LSTM中文” ↩
https://arxiv.org/pdf/1610.02357.pdf “Xception” ↩
一个基于神经网络模型的视觉模型中,卷积和归一化层是最为耗时的两种layer。卷积数据计算密集类型,今年来大量的优化主要集中在各种设备上的卷积加速。 归一化层通过计算一个批量中的均值与方差来进行特征归一化。众多实践证明,它利于优化且使得深度网络易于收敛。批统计的随机不确定性也作为一个有利于泛化的正则化项。BN 已经成为了许多顶级计算机视觉算法的基础。添加归一化层作为提高算法性能的很好的一种策略,但由于像BN遭受数据同步延时的问题,现在逐渐被一些新的normalization方式所替代。
卷积定义
$f(t)$先不动, $g(-t)$相当于$g(t)$函数的图像沿y轴(t=0)做了一次翻转。$g(x-t)$相当于$g(-t)$的整个图像沿着t轴进行了平移,向右平移了x个单位。他们相乘之后围起来的面积就是$h(x)$。
离散卷积的定义
其实,深度学习中的卷积对应于数学中的cross correlation. 从卷积的定义来看,我们当前在深度学习中训练的卷积核是翻转之后的卷积核。
下面是一些介绍卷积的文章和常见卷积类型统计表:
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. |
计算卷积的方法有很多种,常见的有以下几种方法:
使用Depthwise separable convolution卷积的计算量为:
那么计算量之比为
一般情况下,$k^2 « C_1$, 所以当$k=3$的时候,计算量之比约为原来的$\frac{1}{9}$.
每个子图表示一个feature map张量,以$N$为批处理轴,$C$为通道轴,$(H,W)$作为空间轴。其中蓝色区域内的像素使用相同的均值和方差进行归一化,并通过聚合计算获得这些像素的值。从示意图中可以看出,GN没有在N维度方向上进行拓展,因此batch size之间是独立的,GPU并行化容易得多。
需要比较大的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存在以下缺点:
LN中同层神经元输入拥有相同的均值和方差,不同的输入样本有不同的均值和方差; BN中则针对不同神经元输入计算均值和方差,同一个batch中的输入拥有相同的均值和方差。
所以,LN不依赖于batch的大小和输入sequence的深度,因此可以用于batchsize为1和RNN中对边长的输入sequence的normalize操作。
BN注重对每个batch进行归一化,保证数据分布一致,因为判别模型中结果取决于数据整体分布。
但是图像风格化中,生成结果主要依赖于某个图像实例,所以对整个batch归一化不适合图像风格化中,因而对HW做归一化。可以加速模型收敛,并且保持每个图像实例之间的独立。
GN does not exploit the batch dimension, and its computation is independent of batch sizes.
从实验结果中可以看出在训练集合上GN的valid error低于BN,但是测试结果上逊色一些。这个
可能是因为BN的均值和方差计算的时候,通过随机批量抽样(stochastic batch sampling)引入了不确定性因素,这有助于模型参数正则化。
而这种不确定性在GN方法中是缺失的,这个将来可能通过使用不同的正则化算法进行改进。
动机
在神经深武学有一个概念叫做侧抑制(lateral inhibitio),指的是被激活的神经元抑制相邻的神经元。 归一化的目的就是“抑制”,局部响应归一化就是借鉴侧抑制的思想来实现局部抑制,尤其是当我们使用ReLU 的时候,这种侧抑制很管用。
好处
有利于增加泛化能力,做了平滑处理,识别率提高1~2%
梯度下降法是最早最简单,也是最为常用的最优化方法。梯度下降法实现简单,当目标函数是凸函数时,梯度下降法的解是全局解。 一般情况下,其解不保证是全局最优解,梯度下降法的速度也未必是最快的。梯度下降法的优化思想是用当前位置负梯度方向作为搜索方向, 因为该方向为当前位置的最快下降方向,所以也被称为是”最速下降法”。最速下降法越接近目标值,步长越小,前进越慢。 梯度下降法的搜索迭代示意图如下图所示:
梯度下降法的缺点:
CS231n: Convolutional Neural Networks for Visual Recognition.
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%)。说话人跨越不同的口音,职业和年龄。 可用来对说话者的身份进行识别。 |