前几天微软提出了一个xDeepFM算法:

介绍

传统交叉特征工程主要有三个缺点,以下部分来自paper:

  • 1.获取高质量特征代价高昂
  • 2.大规模预测系统(比如:推荐系统),存在大量原始特征(raw features),很难人工抽取所有交叉特征
  • 3.人工交叉特征不能泛化到在训练数据中未见过的交叉上

FM会将每个特征i嵌入到一个隐因子向量 上,pairwise型特征交叉可以被建模成隐向量的内积:。在本paper中,我们使用术语bit来表示在隐向量中的一个元素(比如:)。经典的FM可以被扩展到专门的高阶特征交叉上,但一个主要缺点是:会建模所有的特征交叉,包括有用组合和无用组合。无用组合会引入噪声、以及效果的下降。最近几年,DNNs越来越流行。利用DNNs可以学习复杂和可选择的特征交叉。[46]提出来FNN用于学习高阶特征交叉。它会使用对于field embedding的预训练FM,然后应用于DNN。[31]提出了PNN,它不依赖预训练的FM,而是在embedding layer和DNN layer之间引入了一个product layer。FNN和PNN的主要缺点是,它们主要更多关注高阶特征交叉,而非低阶交叉。Wide&Deep模型和DeepFM模型通过引入混合结构克服了上面的缺点,它包含了一个shallow组件以及一个deep组件,可以学到memorization和generalization。因而可以联合学习低阶和高阶特征交叉。

上面的所有模型都使用DNN来学习高阶特征交叉。然而,DNN可以以一个隐式的方式建模高阶特征交叉。由DNN学到的最终函数可以是任意形式,关于特征交叉的最大阶数(maximum degree)没有理论上的结论。另外,DNNs在bit-wise级别建模征交叉,这与FM框架不同(它会在vector-wise级别建模)。这样,在推荐系统的领域,其中DNN是否是用于表示高阶特征交叉的最有效模型,仍然是一个开放问题。在本paper中,我们提供了一个基于NN的模型,以显式、vector-wise的方式来学习特征交叉。我们的方法基于DCN(Deep&Cross Network)之上,该方法能有效捕获有限阶数(bounded degree)的特征交叉。然而,我们会在第2.3节讨论,DCN将带来一种特殊形式的交叉。我们设计了一种新的压缩交叉网络CIN(compressed interaction network)来替换在DCN中的cross network。CIN可以显式地学到特征交叉,交叉的阶数会随着网络depth增长。根据Wide&Deep模型和DeepFM模型的精神,我们会结合显式高阶交叉模块和隐式交叉模型,以及传统的FM模块,并将该联合模型命名为“eXtreme Deep Factorization Machine (xDeepFM)”。这种新模型无需人工特征工程,可以让数据科学家们从无聊的特征搜索中解放出来。总结一下,主要有三个贡献:

  • 提出了一种新模型xDeepFM,可以联合训练显式和隐式高阶特征交叉,无需人工特征工程
  • 设计了CIN来显式学习高阶特征交叉。我们展示了特征交叉的阶(degree)会在每一层增加,特征会在vector-wise级别进行交叉。
  • 我们在三个数据集中进行了实验,结果展示xDeepFM效果好于其它state-of-art模型

2.PRELIMINARIES

2.1 Embedding Layer

在CV或NLP领域,输入数据通常是图片或文本信号,它们空间相关(spatially correlated)或时序相关(temporally correlated),因而DNN可以被直接应用到dense结构的原始特征上。然而,在推荐系统中,输入特征是sparse、高维、没有明显地空间相关或时序相关。因此,multi-field类别形式被广泛使用。例如,一个输入实例为: [user_id=s02,gender=male,organization=msra,interests=comedy&rock]

通过field-aware one-hot进行编码成高维稀疏特征:

在原始特征输入上使用一个embedding layer,可以将它压缩到一个低维、dense、real-value vector上。如果field是一阶的(univalent),feature embedding被当成field embedding使用。以上述实例为例,特征(male)的embedding被当成field gender的embedding。如果field是多阶的(multivalent),feature embedding的求和被用于field embedding。embedding layer如图1所示。embedding layer的结果是一个wide concatenated vector:

其中,m表示fields的数目,表示一个field的embedding。尽管实例的feature长度可以是多变的,它们的embedding具有相同的长度 m x D, 其中D是field embedding的维数。

图1: field embedding layer。本例中embedding的维度是4

2.2 隐式高阶交叉

FNN, Deep&Cross,以及Wide&Deep的deep part会使用一个在field embedding vector e上的feed-forward神经网络来学习高阶特征交叉。forward process是:

…(1)

…(2)

其中,k是layer depth,是激活函数,是第k层的output。可视化结构与图2展示的非常像,但不包括FM layer或Product layer。该结构会以bit-wise的方式建模交叉。也就是说,相同field embedding vector中的元素也会相互影响。

PNN和DeepFM在上述结构上做了小修改。除了在embedding vector e上应用了DNNs外,它们在网络中添加了一个2-way interaction layer。因而,bit-wise和vector-wise的交叉都能在模型中包含。PNN和DeepFM中主要不同是,PNN会将product layer的输出连接到DNNs中,而DeepFM会直接将FM layer连接给output unit。

图2: DeepFM和PNN的架构。我们复用了符号,其中红色边表示weight-1 connections(没有参数),灰色边表示normal connections(网络参数)

2.3 显式高阶交叉

[40]提出的Cross Network(CrossNet)它的结构如图3所示:

图3:

它可以显式建模高阶特征交叉。不同于经典的fully-connected feed-forward network,它的hidden layers通过以下的cross操作进行计算:

…(3)

其中,是第k层的weights,bias以及output。对于CrossNet能学到一个特殊类型的高阶交叉这一点我们有争论,其中,CrossNet中的每个hidden layer是一个关于的标量乘积。

theorem 2.1: 考虑到一个k层cross network,第i+1层的定义为:。接着,cross network的output 是一个关于的标量乘积。

证明如下:

k=1时,根据矩阵乘法的结合律和分配律,我们具有:

…(4)

其中,标量实际上是关于的线性回归。其中,是关于的一个标量乘。假设标量乘适用于k=i。对于k=i+1, 我们可以有:

…(5)

其中,是一个标量。其中,仍是一个关于的标量乘。通过引入hypothesis,cross network的output 是一个关于的标量乘。

注意,并不意味着是与是线性关系的。系数是与敏感的。CrossNet可以非常有效地学到特征交叉(复杂度与一个DNN模型对比是微不足道的),然而,缺点是:

  • (1) CrossNet的输出受限于一个特定的形式,每个hidden layer是关于的一个标量乘
  • (2) 交叉是以bit-wise的方式进行

3.新模型

3.1 CIN

我们设计了一个新的cross network,命名为CIN(Compressed Interaction Network),具有如下注意事项:

  • (1) 交叉是在vector-wise级别上进行,而非bit-wise级别
  • (2) 高阶特征的交叉显式衡量
  • (3) 网络的复杂度不会随着交叉阶数进行指数增长

由于一个embedding vector被看成是一个关于vector-wise 交叉的unit,后续我们会将field embedding公式化为一个矩阵:,其中,假设表示在第k层的(embedding)feature vectors的数量。对于每一层,通过以下方式计算:

…(6)

其中是第h个feature vector的参数矩阵,表示Hadamard product,例如:。注意,通过在间的交叉产生,其中,特征交叉会被显式衡量,交叉的阶数会随着layer depth增长。CIN的结构与RNN非常相似,其中下一个hidden layer的outputs取决于最近一个(the last)的hidden layer和一个额外的input。我们在所有layers上都持有embedding vectors的结构,这样,即可在vector-wise级别上使用交叉。

有意思的是,等式(6)与CNN具有很强的关联。如图4a所示,我们引入了一个内部张量(intermediate tensor) ,其中,它是hidden layer和原始特征矩阵的外积(outer products:沿着每个embedding维度)。被看成是一个特殊类型的图片,看成是一个filter。我们如图4b所示跨沿着该embedding dimension(D)滑动该filter,获得一个hidden vector ,这在CV中通常被称为一个feature map。在CIN命名中所使用的术语”compressed”表示了第k个hidden layer会将 向量的隐空间压缩到向量中。

图4c提供了CIN的一个总览。假设T表示网络的深度。每个hidden layer 具有一个与output units的连接。我们首先在hidden layer的每个feature map上使用sum pooling:

…(7)

其中,。这样,我们就得到一个pooling vector:,对于第k个hidden layer相应的长度为。hidden layers的所有polling vectors在连接到output units之前会被concatenated:。如果我们直接使用CIN进行分类,output unit是在上的一个sigmoid节点:

…(8)

其中,是回归参数。

3.2 CIN详解

我们对CIN进行分析,研究了模型复杂度以及潜在的效果。

3.2.1 空间复杂度

在第k层的第h个feature map,包含了个参数,它与具有相同的size。因而,在第k层上具有个参数。考虑到对于output unit的当前最近(the last)的regression layer,它具有个参数,CIN的参数总数是 。注意,CIN与embedding dimension D相互独立。相反的,一个普通的T-layers DNN包含了个参数,参数的数目会随着embedding dimension D而增长。

通常,m和不会非常大,因而,的规模是可接受的。当有必要时,我们可以利用一个L阶的分解,使用两个小的矩阵以及来替换

…(9)

其中以及。出于简洁性,我们假设每个hidden layer都具有相同数目(为H)的feature maps。尽管L阶分解,CIN的空间复杂度从下降到。相反的,普通DNN的空间复杂度是,它对于field embedding的维度D是敏感的。

3.2.2 时间复杂度

计算tensor 的开销是O(mHD)。由于我们在第一个hidden layer上具有H个feature maps,计算一个T-layers CIN会花费时间。相反的,一个T-layer plain DNN,会花费时间。因此,CIN的主要缺点是在时间复杂度上。

3.2.3 多项式近似(Polynomial Approximation)

接下来,我们检查了CIN的高阶交叉属性。出于简洁性,我们假设,在hidden layers上的feature maps数目,等于fields m的数目。假设[m]表示小于或等于m的正整数集。在第1层上的第h个feature map,表示为,通过下式计算:

…(10)

因此,在第1层的每个feature map会使用个系数来建模pair-wise特征交叉。相似的,在第2层的第h个feature map为:

…(11)

注意,l和k相关的所有计算在前一个hidden layer已经完成。我们在等式(11)扩展的因子是为了清晰。我们可以观察到,在第二层的每个feature map会使用新参数来建模3-way交叉。

一个经典的k阶多项式具有系数。我们展示了CIN会逼近这类型多项式,根据一个feature maps链,只需要个参数。通过引入hypothesis,我们可以证明,在第k层的第h个feature map为:

…(12)

为了更好地演示,我们参考了[40]的注解。假设表示一个multi-index,其中。我们会从中忽略原始的上标,使用来表示它,因为对于最终展开的表达式,我们只关心来自第0层(等同于field embedding)的feature maps。现在,使用一个上标来表示向量操作,比如。假设表示一个multi-vector 多项式的阶数k:

…(13)

在该类中的每个向量多项式都具有个系数。接着,我们的CIN接似系数

…(14)

其中, 是一个multi-index,是索引()的所有排列。

3.3 与隐式网络的组合

在第2.2节,plain DNNs可以学到隐式高阶特征交叉。由于CIN和plain DNNs可以互补,一个直观的做法是,将这两种结构进行组合使模型更强。产生的模型与Wide&Deep和DeepFM非常像。结构如图5所示,我们将新模型命名为eXtreme Deep Factorization Machine(xDeepFM),一方面,它同时包含了低阶和高阶特征交叉;另一方面,它包含了隐式特征交叉和显式特征交叉。它产生的output unit如下:

…(15)

其中,\sigma为sigmoid函数,a是原始特征。分别是是plain DNN和CIN的outputs。和b是可学习的参数。对于二分类,loss函数为log loss:

…(16)

其中,N是训练实例的总数。Optimization过程是最小化下面的目标函数:

…(17)

其中表示正则项,表示参数集,包含linear part,CIN part,DNN part。

图5: xDeepFM的结构

3.3.1 与FM和DeepFM的关系

假设所有field是一阶的(univalent)。如图5所示,当depth和CIN part的feature maps同时设为1时,xDeepFM就是DeepFM的一个泛化,通过为FM layer学习线性回归权重实现(注意,在DeepFM中,FM layer的units直接与output unit相连,没有任何系数)。当我们进一步移去DNN part,并同时为该feature map使用一个constant sum filter(它简单采用输入求和,无需任何参数学习),接着xDeepFM就变成了传统的FM模型。

4.实验

实验主要回答下述问题:

  • (Q1) CIN在高阶特征交叉学习上是如何进行的?
  • (Q2) 对于推荐系统来说,将显式和隐式高阶特征交叉相组合是否是必要的?
  • (Q3) xDeepFM的网络设置如何影响效果?

4.1 实验设置

4.1.1 数据集

1. Criteo Dataset:ctr预测的benchmarking dataset,对外开放。给定一个用户和他访问的页面,目标是预测它点击一个给定广告的概率。

2. Dianping Dataset:收集了6个月的关于大众点评的用户check-in活动用于餐厅推荐实验。给定一个用户的profile,一个餐厅的相应属性,该用户最近三次访问POIs(point of interest),我们希望预测它访问该餐厅的概率。对于在一个用户的check-in样本中的每个餐厅,我们会通过POI流行度抽样出在3公里内的4个餐厅作为负样本。

3.Bing News Dataset.:Bing News是微软Bing搜索引擎的一部分。我们收集了在新闻阅读服务上连续5天的曝光日志。使用前3天数据用于训练和验证,后两天数据用于测试。

对于Criteo dataset和Dianping dataset,随机将样本划分为8:1:1进行训练、验证、测试。三个数据集的特性如表1所示。

表1:评估数据计的统计。

4.1.2 评估metrics

我们使用两种metrics:AUC和LogLoss。有时更依赖logloss,因为我们需要使用预测概率来估计一个排序系统带来的收益(比如常见的CTR x bid)

4.1.3 Baselines

我们比较了xDeepFM, LR, FM, DNN, PNN, Wide&Deep, DCN, DeepFM.

4.1.4 Reproducibility

使用tensorflow来实现模型。每个模型的超参数通过在validation set上进行grid-searching调参,然后选择最好的settings。

  • learning rate设置为0.001.
  • optimization方法使用Adam。
  • mini-batch size=4096.
  • 对于DNN, DCN, Wide&Deep, DeepFM和xDeepFM,使用L2正则,对应的
  • 对于PNN,使用dropout=0.5
  • 每层neurons数目的缺省setting为:
    • (1) DNN layers为400
    • (2) 对于Criteo dataset,CIN layers为200; 对于DIanping和Bing News datasets,CIN layers=100
  • 由于本文主要关注网络结构,所有field embedding的维度统一设为固定值=10.
  • 本试验在并行化在5块tesla K80 GPUs上跑.
  • 源码为: https://github.com/ Leavingseason/ xDeepFM

效果展示部分:

表3: depth列表示单模型中的最佳深度,分别表示(cross layers, DNN layers)

4.2 Q1: 单一Neural组件间的效果比较

我们想知道CIN单独是如何执行的。注意FM会显式衡量2阶特征交叉,DNN模型可以隐式衡量高阶特征交叉,CrossNet尝试使用较少参数来建模高阶特征交叉,CIN则会显式建模高阶特征交叉。由于它实际依赖于数据集,单一模型(individual model)间的比较优势没有理论保证。例如,如果实际数据集不需要高阶特征交叉,FM可能是最好的单一模型。对于该实验,我们并不期望哪个模型表现最好。

表2展示了单一模型在三个实际数据集上的效果。令人惊讶的是,CIN的表现都要好些。另一方面,结果表明,对于实际数据集,稀疏特征上的高阶交叉是必要的,可以证实:DNN,CrossNet, CIN的效果要远好于FM。另一方面,CIN是最好的单一模型,图中展示了CIN在建模高阶特征交叉上的效果。注意,一个k-layer的CIN可以建模k阶的特征交叉。有趣的是,在Bing News dataset上,它会采用5 layers的CIN来达到最佳结果。

表2: 不同数据集下的模型表现。Depth列表示每个模型最好的网络深度

4.3 Q2: 集成模型的效果

xDeepFM会将CIN和DNN集成一个end-to-end模型。而CIN和DNN能cover在特征交叉学习上两种不同的属性,我们感兴趣的是,是否确实有必要将两者组合在一起进行explicit和implicit的joint learning。这里,我们比较了一些比较强的baselines,如表3所示。另一个有意思的观察是,所有基于neural的模型并不需要非常深的网络结构来达到最佳效果。常见的depth超参数设置为2或3, xDeepFM的最佳深度是3,可以表示最多学习4阶的交叉。

4.4 Q3: 超参数学习

  • 1.hidden layers的数目
  • 2.每层的neurons数目
  • 3.激活函数

参考

CRNN( Convolutional Recurrent Neural Network)由华科白翔等人提出。

介绍

crnn主要关注CV中的一个经典难题:基于图片的序列识别。现实世界中,一大群视频对象,比如场景文字(scene text)、手写、音阶符,以序列方式出现。不同于通用目标识别,识别这样的序列对象通常需要系统去预测一串对象labels,而非单个label。因而,识别这样的目标很自然地转化成一个序列识别问题。序列化目标的另一个独特属性是,它们的长度变化很大。例如,英文词汇可以包含2个字符“OK”,也可以包含15个符如“congratulations”。因而,大多数流行的deep模型(比如DCNN)不能直接应用于序列预测,因为DCNN模型经常在固定维度的inputs和outputs上操作,不能产生变长的label sequence

对于一个特定的序列对象(比如:场景文字),已经有一些方法来解决该问题。例如,在[35,8]中的算法首先对单个字符进行检测,接着对这些被检测的字符使用DCNN进行识别,可以使用带标注的字符图片进行训练。这样的方法通常需要训练一个很强的字符检测器,来从原始图片中精准地检测和裁减每个字符。一些其它方法[22]会将场景文字识别看成是一个分类问题,为每个英文词汇(总共90K words)分配一个class label。将它看成是一个带有大量分类的训练模型,它很难泛化到其它类型的目标上,比如:中文文字、音阶等,因为这种类型序列的基本组合远超100w。总之,当前基于DCNN的系统不能直接用于基于图片的序列识别。

RNN模型是Deep模型的另一分支,主要用于处理序列。RNN的一个好处是,它不需要知道在训练和测试时一个序列目标图片中每个元素的位置。然而,需要有一个预处理step来将一个输入目标图片转化成一个图片特征序列。例如,Graves et al.[16]从手写文本中抽取一个几何集合 或者 图片特征,而paper[33]将word images转化成顺序化的HOG特征。这些预处理step与pipeline中的子任何组件相互独立,因而,基于RNN的系统不能以一种end-to-end的方法地直接被训练和优化

一些传统的场景文字识别方法,它们不基于神经网络,也能在该领域带来重大启发和新颖的表示。paper[5]和paper[30]提出来将word images和text strings嵌入到一个公共的向量子空间中,将文字识别转换成一个检索问题(retrieval problem)。paper[36]和paper[14]使用中间级别的特征来进行场景文字识别。尽管在标准的benchmarks上取得了效果提升,这些方法总体上好于之前的神经网络方法,本文方法也能做到。

该paper的主要贡献是一个新的NN模型,它的网络架构是专门为识别图片中的序列化对象而设计的。提出的NN模型被命名为“CRNN ( Convolutional Recurrent Neural Network)”,因为它是一个DCNN和RNN的组合。对于序列化对象,比起CNN模型,CRNN具有着一些明显的优点:

  • 1) 它可以直接从sequence labels(例如:words)中学习,无需详细注解(例如:characters)
  • 2) 在从图片数据中直接学习有信息表示时,它具有DCNN的相同特性,即不用手工特征,也不用预处理steps(包括:二值化/分割,成分定位等)
  • 3) 它具有RNN的相同属性,可以产生一个labels序列
  • 4) 它不限制序列化对象的长度,在训练和测试阶段只需要高度归一化
  • 5) 它在场景文字识别上,比之前的方法要好
  • 6) 比起标准的DCNN,它包含了更少的参数,消耗更少的存储空间

2.网络结构

CRNN的网络结构如图1所示,自底向上,包含了三个组成部分:

  • 卷积层(conv layers)
  • 递归层(recurrent layers)
  • 一个合成层(transcription layer)

图1

在CRNN的底部,conv layers从每一张输入图片中自动抽取一个特征序列。在卷积网络的顶部,构建一个recurrent网络来对通过conv layers输出的每一帧的特征序列做预测。transcription layer将每一帧的预测翻译成一个label sequence。尽管CRNN由不同的网络结构组成,它可以使用一个loss function进行jointly training。

2.1 特征序列抽取

在CRNN模型中,conv layers的组件通过从一个标准的CNN模型所使用的conv layers和max-pooling layers进行构建(移除FC layers)。这样的组件被用于从一个输入图片中抽取一个序列化特征表示。在feed给网络之前,所有的图片需要被归一化成相同的高度。接着,一个特征向量的序列会从feature maps中被抽取出来。特别的,一个特征序列的每个feature vector通过在feature maps上按列从左到右来生成。这意味着,第i个feature vector是所有maps中的第i列的拼接(concatenation)。在我们的设置中,每一列的宽度寄存定为单个pixel。

由于有conv layers、max-pooling layers、以及element-wise激活函数在局部区域上操作。它们是平移不变的(translation invariant)。因而,feature maps的每列对应于原始图片的一个矩形区域(术语称为“receptive field”),这样的矩形区域与在feature maps中相应的从左到右的相对应的列具有相同的顺序。如图2所示,在特征序列中的每个vector与一个receptive field相关联,可以被看成是该区域的图片描述符

图2: receptive field. 在被抽取的特征序列中,每个向量都与输入图片上的一个receptive field相关,可以被认为是该区域的特征向量

对于不同类型的视觉识别任务,健壮的、丰富的、可训练的卷积特征被广泛使用。一些之前的方法采用CNN来学习一个关于序列目标(比如:场景文字)的健壮表示。然而,这些方法通常会通过CNN来抽取整个图片的全局表示,接着收集局部深度特征来识别该序列目标。由于CNN需要输入图片缩放到一个固定size,以满足固定的输入维度,不适合变长的序列化目标识别。在CRNN中,我们将deep features转成顺序表示,以便能表示不同长度的序列化目标。

2.2 Sequence Labeling

在conv layers之上,构建了一个deep bi-RNN网络。该recurrent layers可以为在特征序列中的每一帧预测一个label分布。该recurrent layer的优点有三个。

  • 首先,RNN具有很强的能力来捕获在序列中的上下文信息。对于基于图片的序列识别使用上下文信息,比将每个符号单独对待的方式更稳定更有用。将场景文本识别看成一个示例,宽字符可能需要许多个连续帧才能完整描述(如图2所示)。另外,当观察它们的上下文时,一些模糊的字符很容易区分;例如,很容易识别“il”,通过区别该字符高度而非单个字符单独识别。
  • 第二,RNN可以对error微分进行反向传播至它的输入(例如:conv layer),从而允许我们在同一网络中对recurrent layers和conv layers进行jointly training。
  • 第三,RNN能在特有长度的序列上操作,从头到尾进行遍历。

一个典型的RNN unit在它的input layers和output layers间具有自连接的hidden layer。每次它接受序列中的一帧时,它会使用一个带有当前输入和过去状态作为输入的非线性函数()来更新它的内部状态。接着,基于做出预测。在这种方式下,过去的上下文 可以被捕获并用来进行预测。然而,传统的RNN unit,存在着梯度消失问题,这限制了它可存储的上下文范围,增加了训练过程的负担。LSTM是一种特殊的RNN unit,可以用来解决该问题。一个LSTM(如图3所示)包含了一个memory cell和三个乘法门,称为:input gates, output gates和forget gates。概念上,memory cell会存储过去的上下文,input gates和output gates允许cell存储一段时间的上下文。同时,在cell中的memory可以被forget gate清除。LSTM的这种特殊设计允许它捕获长范围依赖,这通常发生在基于图片的序列上。

LSTM是有向的,它只使用过去的上下文。然而,在基于图片的序列中,两个方向的上下文都是有用的。因而,我们使用了两个LSTMs来组成双向LSTM:一个向前,一个向后。另外,多个bi-LSTMs可以进行stack,产生一个如图3.b所示的deep bi-LSTM。deep结构比shallow结构允许更高级的抽象,在语音识别上可以达到极大的效果提升[17]。

图3: LSTM. (a) 单个LSTM unit (b)paper中所使用的bi-LSTM结构。它会将一个forward LSTMs和一个backward LSTMs组合产生一个bi-LSTM。将多个bi-LSTM进行Stacking可以产生一个deep bi-LSTM。

在recurrent layers上,error微分(differentials)沿如图3.b所示的箭头反向传播,例如:Back-Propagation Through Time(BPTT)。在recurrent layers的底部,传播的微分序列被级联成maps,将feature maps转换成feature sequences的操作进行反向,fed back到conv layers。实际上,我们创建了一个定制的network layer,称为“Map-to-Sequence”,来作为在conv layers和recurrent layers间的桥梁

2.3.1 label序列的概率

我们采用了由Graves et al.[15]提出的Conectionist Temporal Classifcation(CTC) layer中所定义的条件概率。该概率被定义成,对于label sequence (l) ,在每帧预测上的条件概率,它会忽略在l中每个label所处的位置。因此,当我们使用该概率的负log-likelihood作为目标来训练该网络时,我们只需要图片和它们相应的label序列,从而避免为单独的字符标注位置。

条件概率的公式可以如下简短描述:

输入是一个序列,其中T是序列长度。接着,每个是一个在集合上的概率分布。其中L包含了任务中的所有labels(例如:所有英文字符),以及空白(blank)label。一个seq-to-seq的映射函数B被定义在序列上,其中T为长度。B将映射到l上,通过首先移除重复的labels,接着移除空白。例如,B将“–hh-e-l-ll-oo–”(其中’-‘表示空白)映射到”hello”。接着,条件概率被定义成通过B将所有映射到l上概率求和:

…(1)

其中的概率被定义成,其中是在时间t时具有label 的概率。直接计算等式(1)在计算上是不可行的,因为求和项是指数级别的。然而,等式(1)可以通过paper[15]中提到forward-backward算法进行有效计算。

2.3.2 Lexicon-free transcription

在该模式下,序列 表示等式(1)的最高概率。由于不存在可训练的算法来精准求解,我们使用paper[15]的策略进行。序列可以通过进行近似。例如,在每一时刻t上采用最可能的label ,将产生的序列映射到上。

2.3.3 Lexicon-based transcription

在lexicon-based模式下,每个测试样本会与一个词典D相关系。通常,label序列通过选择在词典中具有等式(1)的最高条件概率的序列被识别。例如,。然而,对于大词典,例如,50k-words的Hunspell spell-checking dictionary,在词典上执行搜索是一个非常耗时的开销。例如,为在词典中的所有的sequence计算等式(1)的概率,并选择最高的概率。为了解决该问题,我们观察到,label sequences通过lexicon-free transcription方式进行预测,通常会在编辑距离(edit distance metric)上更接近ground truth。这意味着,我们可以将我们的搜索限制在最近邻候选上,其中是最大编辑距离,I’是在lexicon-free模式下从y转录得到的序列:

…(2)

候选可以通过BK-tree结构有效发现,它是一种metric tree用来离散化metric空间。BK-tree的搜索时间复杂度为,其中是lexicon size。因此,该scheme可以扩展到非常大的词典上。在我们的方法中,为一个词典离线构建了一个BK-tree。接着,我们使用该tree执行了最快的在线搜索,通过小于或等于到query sequence的编辑距离来发现序列。

2.4 网络训练

训练数据集通过的定义,其中是训练图片,是ground truth的label sequence。目标函数是最小化ground truth的条件概率的-log-likelihood:

…(3)

其中,是由经过recurrent layers和conv layers所产生的序列。该目标函数会从一张图片和它的ground truth的label序列间计算一个cost value。因此,该网络可以在(images, sequences) pairs上进行端到端训练,消除训练图片中由人工标注所有独立components的过程。

该网络使用SGD进行训练。Gradients的计算通过BP算法进行。特别的,在transcription layer,error微分通过back-propagated结合forward-backward算法计算。在recurrent layers,会使用Back-Propagation Through Time (BPTT) 来计算error微分。

对于optimization,我们使用AdaDelta来自动计算每个维度的learning rates。对比常用的momentum方法,AdaDelta无需人工设置一个learning rate。更重要的,我们发现,使用AdaDelta的optimization比momentum方法收敛更快。

3.试验

为了评估CRNN模型的有效性,我们在场景文识别和音阶识别的标准benchmarks上进行试验。

3.1 Datasets

对于场景文本识别的所有试验,我们使用Jaderberg【20】的synthetic dataset (Synth)作为试验。该dataset包含了800w的训练图片,以及相应的ground truth的words。这样的图片通过一个人造文本引擎(synthetic text engine)生成,高度与现实相近。我们的网络在synthetic data上训练一次,并在其实真实世界的测试数据集上进行测试,无需在其它训练数据上做任何的fine-tuning。即使用CRNN模型是纯粹使用synthetic text data训练的,它也能在标准的文本识别becnmarks上工作良好。

目前在效果评测方面,使用了4种流行的场景文本识别benchmarks:

  • ICDAR 2003(IC03):该测试数据集包含了带标注文本边框的251张场景图片。根据paper[34],我们忽略了那些包含非字母数字字符、以及那些小于三个字符的图片,获得的测试集包含了860个裁减过的文本图片。每张测试图片与一个50-words的词典相关联(由paper[34]定义)。一个完整的词典可以通过组合所有单张图片的词典来构成。另外,我们使用了一个50k个词的词典,它包含了在Hunspell spell-checking dictionary字典中的所有词。
  • ICDAR 2013 (IC13):测试数据集继承了IC03上的大多数数据,它包含了1015张ground truth的裁减word images。
  • IIIT 5k-word (IIIT5k):包含了3000张来自互联网上的word test images。每张图都与一个50词的词典和1k-words词典相关。
  • Street View Text (SVT):该测试数据集包含了来自Google Street View的249张街景门牌图片。从它们中裁减出647张word images。每张word images具有一个由paper[34]定义的50 words的词典。

3.2 实现细节

在我们的实验中,所使用的配置如表1所示:

表1:

conv layers基于一个VGG-VeryDeep架构(paper[32])。为了让它更适合识别英文字符,会做一定调整。在第3和第4个max-pooling layers中,我们采用了1x2 的rectangular pooling window来替代常见的squared方法。该tweak yields的feature maps具有更大的宽度,更长的feature序列。例如,一张包含了10字符的图片,通常size=100x32, 其中一个feature sequence可以生成25帧。该长度超过了最大英文词汇的长度。在那之上,rectangluar pooling windows会生成rectangular receptive fields(如图2),它有益于识别具有narrow shapes的一些字符,比如’i’和’l’。

该网络不只具有deep conv layers,但也具有recurrent layers。两者很难训练。我们发现使用batch-normalization技术来训练这样深度的网络很有用。两个batch-normalization layers,训练过程可以极大加速。

我们使用torch7来实现该网络框架,定制实现了LSTM units(Torch7/CUDA),transcription layer(c++)和BK-tree数据结构(c++)。实验在工作站(2.50 GHz Intel(R) Xeon(R) E5- 2609 CPU, 64GB RAM 以及NVIDIA(R) Tesla(TM) K40 GPU)上进行训练。该网络的训练使用AdaDelta进行训练,相应的为0.9. 在训练期间,所有图片被归一化到100 x 32,以加速训练过程。训练过程大概达到50个小时后收敛。测试图片的高度被归一化到32. 宽度按高度的比例进行缩放,但至少是100个像素。平均测试时间是0.16s/sample,在IC03上进行评测,没有词典。合适的词典搜索被应用于IC03的50k词典上,参数设置为3.每个测试样本平均花费0.53s。

评测

略,详见paper.

参考

CTPN(Connectionist Text Proposal Network)由Zhi Tian等人提出。

总览

CTPN可以在卷积特征图(convolutional feature maps)中直接检测在精密尺度(fine-scale)的text proposals序列中的文本行(text line)。它开发了一个垂直锚点机制(vertical anchor mechanism),可以联合预测关于每个固定宽度proposal的位置(location)和文本/非文本分值(text/none-text score)。序列化的proposals被连接到一个RNN上,无缝地与卷积网络相接,产生一个end-to-end的训练模型。这使得CTPN可以探索丰富的图像文本信息,可以检测相当模糊的文本。CTPN可以在多尺度(multi-scale)和多语言文本(multi-language text)环境下可靠工作,无需进一步后序处理(post-processing):这与自底向上的方法不同(它们通常需要多步后置过滤(post filtering))。在ICDAR 2013和2015 becnmarks上分别取得0.88和0.61的F-measure值,比最近的较好结果有很大的提升。CTPN的计算效率是0.14s/image,它使用了very deep VGG16 model.

一、介绍

在自然图片中读取文本最近在CV界获得广泛关注。这是由于许多实际应用,比如:图片OCR,多语言翻译,图片检索,等等。它包含了两个子任务:文本检测、文本识别。CTPN主要工作集中在文本检测任务上,它比识别更具挑战。文本模式的大量变种,以及高度混杂的背景对于精准文本定位构成巨大挑战。

当前文本检测的主要方法大多数使用了自底向上的pipeline。它们通常从低级字符(low-level character)或笔画(stroke)的检测开始,通常按照一定数量的子阶段:非文本组件过滤(non-text component filtering)、文本行构造(text line construction)和文本行验证(text line verification)。这种多步的自底向上的方法很复杂,并且健壮性和可靠性差。它们的性能很严重地依赖字符检测的结果、以及连接组件的方法、或者滑动窗口的方法。这些方法通常会探索低级特征(基于SWT,MSER,或者HoG)来将候选文本从背景中区分出来。然而,它们并不健壮,需要通过独立标识私有的笔画或字符,没有文本信息。例如,人们标识一个字符序列比标识单个字符更自信,特别是当一个字符很模糊时。这种限制通常会在字符检测上产生大量非文本组件,从而在下一步中处理它们造成主要难题。再者,这些错误的检测很容易在自底向上的pipeline上按顺序累积。为了解决这些难题,CTPN采用强的deep features来在卷积图中直接检测文本信息。另外还开发了文本锚点机制,可以精准预测在精准尺度上的文本位置。接着,提出了一个in-network recurrent架构来将这些fine-scale text proposals按顺序相连接,并将它们编码成富文本信息。

近几年,CNN在通用目标检测上有优势。state-of-art的方法是Faster Region-CNN(R-CNN)系统,其中RPN( Region Proposal Network)可以直接从卷积特征图中生成高质量的未知类别目标proposals。接着RPN proposals可以被feed到一个Fast R-CNN模型上以进一步分类(classification)和提炼(refinement),从而在通用目标检测上产生state-of-art的效果。然而,很难将这些通用目标检测系统直接应用到文本场景检测中,这种情况下通常需要一个更高的位置准确率。在通用目标检测中,每个object都具有一个定义良好的边界,而在文本中也存在这样的边界,因为一个文本行或词由一定数目的独立字符或笔画构成。对于目标检测,一个典型的正确检测的定义是松散的,比如:在检测表面的边界框和ground truth重叠(overlap)> 0.5(PASCAL standard),因为人们可以很容易地从主要部件上识别一个object。相反地,读取完整文本是一个细粒度的识别任务,它的一个正确检测必须覆盖文本行或词的完整区域。因此,文本检测通常需要一个更精准的定位,来产生一个不同的评估标准,比如:text benchmarks中常用的Wolf’s standard。

在CTPN中,会通过扩展RPN结构来进行精准文本行定位。并提出了许多技术开发手段来将generic object detection模型优雅地移植来解决文本上的难题。另外进一步提出了一个in-network recurrent机制,可以在卷积图中直接检测文本序列,避免通过一个额外的CNN检测模型来进行后置处理。

1.1

CTPN的主要架构见图1.

图1: (a) CTPN的结构. 我们通过VGG16模型的最后一层的卷积图(conv5)紧密地滑动一个3x3的空间窗口。在每行中的序列窗口通过一个Bi-LSTM进行递归连接,其中每个窗口的卷积特征(3x3xC)被用于BLSTM的256D输入(包含两个128D的LSTMs)。RNN layer被连接到一个512D的FC-layer上,后面跟着output layer,它会联合预测text/non-text scores,y坐标以及k个锚点的side-refinement offsets。 (b) CTPN输出预列化的固定宽度的fine-scale text proposals。每个box的颜色表示了text/non-text score。只有正分值的boxes才会被展示。

2.相关工作

  • 文本检测:
  • 目标检测:

略,详见paper

3.Connectionist Text Proposal Network

CTPN包括了三个主要部分:

  • 在fine-scale proposals中检测文本
  • 对text proposals进行recurrent连接(recurrent connectionist text proposals)
  • 边缘细化(side-refinement)

3.1 Detecting Text in Fine-scale Proposals

与RPN相类似,CTPN本质上是一个完全卷积网络(fully convolutional network):它允许一个任意size的输入图片。它会通过密集地在卷积特征图(convolutional feature maps)上滑动一个小窗口,并输出一串fine-scale(例如:16-pixel的宽度)的text proposals,如图1(b)所示。

这里采用了一个非常深的16-layer vggNet (VGG16)作为示例来描述 CTPN,它很容易应用于其它的deep模型。CTPN的结构如图1(a)所示。我们使用了一个小的空间窗口(spatial window),3x3,来滑动最后的卷积层中的feature maps(例如:VGG16中的conv5)。conv5的feature maps的size由输入图片的size决定,其中总的stride和receptive field由网络结构来确定。在卷积层中使用一个共享卷积计算的滑动窗口,可以减少基于该方法的计算量。

总之,滑动窗口法采用了多尺度窗口(multi-scale windows)来检测不同size的目标,其中一个固定size的window scale对应于相同size的目标。在faster R-CNN中,提出了一个高效的锚点回归机制,它允许RPN来使用单尺度窗口来检测多尺度目标。单尺度窗口的核心是:通过使用一定数量的锚点(anchors),能预测在一个宽范围尺度和尺度比例(aspect ratios)上的目标。我们希望将这种有效的锚点机制扩展到文本任务上。然而,文本与通用目标十分不同,它必须有一个定义良好的闭合边界和中心,可以从一部分来推测整个目标。它可能包含了多级别的组件:比如笔画,字符,词,文本行和文本区域,它们相互间很容易区分。文本检测是在词或文本行级别定义的,因而,通过将它定义成单个目标,它可以很容易地做出不正确的检测,例如:检测一个词的某部分。因此,直接预测一个文本行或词的位置很难或者不可靠,使得它很难达到一个满意的准确率。图2展示了一个示例,其中RPN直接训练来定位图片中的文本行。

我们寻找文本的唯一特性是,能够很好地泛化成在所有级别上的文本组件。我们观察到,RPN的词检测(word detection)很难精准预测词的水平边缘(horizontal sides),因为一个词中的每个字符是孤立或者分离的,这使得发现一个词的起点和终点容易混淆。很明显,一个文本行是一个序列,它是文本与通用目标之间的主要区别。很自然地将一个文本行考虑成一个fine-scale text proposals的序列,其中每个proposal通常表示成一个文本行的一小部分,例如,一个16-pixel宽的文本片段(text piece)。每个proposal可以包含单个或多个笔画,一个字符的一部分,单个或多个字符,等。我们相信,通过将它的水平位置固定(很难进行预测),可以更精准地预测每个proposal的垂直位置。对比RPN(它只要预测一个目标的4个坐标),这减少了搜索空间。我们开发了一个垂直锚点机制,它可以同时预测一个文本/非文本分值,以及每个fine-scale proposal的y轴位置。对比识别一个独立的字符(很容易混淆),检测一个通用固定宽度的text proposal更可靠。再者,检测在固定宽度的text proposals序列中的一个文本行,可以在多尺度和多尺度比例下可靠运行。

最后,我们按以下方式设计了fine-scale text proposal。我们的检测器(detector)会密集地(densely)检测在conv5中的每个空间位置(spatial location)。一个text proposal被定义成:具有一个16 pixels的固定宽度(在输入图片上)。这等同于将该detector密集地通过conv5 maps,其中,总的stride是完整的16 pixels。接着,我们设计了k个垂直锚点来为每个proposal预测y坐标。k个锚点具有相同的水平位置,它们都有16 pixels的宽度,但它们的水平位置以k个不同的高度进行区分。在我们的实验中,我们为每个proposal使用了10个锚点,k=10, 它们的高度从11到273个pixels不等(每次除以0.7)。显式的水平坐标通过高度和一个proposal边界框的y轴中心来进行衡量。我们根据每个锚点的边界位置,各自计算了相对预测的水平坐标(v):

…(1)

…(2)

其中,

  • 分别是相对预测坐标与ground true坐标。
  • 是中心(y轴)和锚点的高度,它们可以从一个输入图片中被预计算好。
  • 和h是预测的y轴坐标,是ground truth坐标。因此,每个预测的text proposal具有一个size=hx16的边界,如图1(b)和图2(右)所示。通常,一个text proposal会大大小于有效可接受field(228x228)。

检测过程如下。给定一个输入图片,我们具有的conv5 features maps(通过使用VGG16模型得到),其中C是feature maps或channels的数目,是空间位置(spatial arrangement)。当我们的检测器通过一个3x3的窗口通过conv5进行密集滑动时,每个滑动窗口会采用一个的卷积特征,来产生预测。对于每个预测,水平位置(x坐标)和k-anchor位置是固定的,它们可以通过将conv5上的空间窗口位置映射到输入图片上来预先计算好。我们的detector会为k个anchors在每个窗口位置输出text/non-text score和预测的y坐标(v)。检测到的text proposals从那些具有text/non-text score > 0.7的锚点上生成(没有最大限制)。通过设计垂直锚点和fine-scale检测策略,我们的检测器可以通过使用单个尺度的图片来处理多个尺度和比例范围的文本行。这进一步减小了计算量,同时还能精准预测文本行的位置。对比RPN或Faster R-CNN系统,我们的fine-scale检测提供了更详细的监督式信息,可以很自然地产生一个更精准的检测。

3.2 Recurrent Connectionist Text Proposals

为了提升位置精度,我们将一个文本行分割成一个fine-scale text proposals序列,然后各自对它们每一个进行预测。很明显地,如果独立地将它们看成单个孤立的proposal是不健壮的。这会在一些非文本目标上(它们与文本模式具有相类似结构:比如,窗,砖,叶子等)产生许多错误的检测。也可以丢弃一些包含弱文本信息的模糊模式。在图3(top)上的一些示例。文本具有很强的连续字符,其中连续的上下文信息对于做出可靠决策来说很重要。可以通过RNN来编码文本信息进行文字识别进行验证。一些paper的结果展示出,连续上下文信息可以极大地促进在裁减不好的词图片上(cropped word images)的识别任务。

受该工作的启发,我们相信该上下文信息对于我们的检测任务很重要。我们的检测器可以探索这些重要的上下文信息来做出可靠决策。再者,我们的目标是为了在卷积层直接编码该信息,产生一个优雅无缝的关于fine-scale text proposals的in-network连接。RNN可以循环地使用它的hidden layer编码该信息。出于该目的,我们提出设计一个在conv5之上的RNN layer,它采用每个窗口的卷积特征作为连续输入,循环更新在hidden layer中的内部state:

…(3)

其中,是来自第t个滑动窗口的输入的conv5 feature。滑动窗口会从左到右密集地移动,为每个row产生t=1,2,…,W的连续特征。W是conv5的宽度。是recurrent internal state,可以从当前输入()和先前在中编码的state联合计算得到。该recurrence的计算使用一个非线性函数,它定义了recurrent模型的准确形式。对于我们的RNN layer,我们采用LSTM的结构。LSTM的提出是为了解决梯度消失问题,通过引入三个额外的乘法门:input gate, forget gate和output gate。我们进一步扩展RNN layer,通过使用一个bi-directional LSTM,它允许双向编码recurrent上下文,因而, connectionist receipt field可以覆盖整个图片宽度,比如:228 x width。我们为每个LSTM使用了一个128D的hidden layer,来采用一个256D的RNN hidden layer,

的内部state被映射到下一个FC layer,以及output layer上用于计算第t个proposal的预测。因此,我们的与RNN layer集合的方式是优雅的,可以产生一个有效的模型,可以进行end-to-end训练,无需额外开销。RNN连接的高效性如图3所示。很明显,它减小了错误检测,同时,可以恢复许多缺失的text proposals(它们包含了非常弱的文本信息)。

图3: 上面三个:不使用RNN的CTPN。下面三个:使用RNN连接的CTPN

3.3 Side-refinement

fine-scale text proposals可以通过CTPN进行准确检测。文本行构建很简单,通过将那些text/no-text score > 0.7的连续的text proposals相连接即可。文本行的构建如下。首先,为一个proposal 定义一个邻居():,其中:

  • (i) 在水平距离上离最近
  • (ii) 该距离小于50 pixels
  • (iii) 它们的垂直重叠(vertical overlap) > 0.7

另外,如果,会将两个proposals被聚集成一个pair。接着,一个文本行会通过连续将具有相同proposal的pairs来进行连接来构建。

图4: 红色box:使用side-refinement的CTPN;黄色虚色的box:不使用side-refinement的CTPN。fine-scale proposal box的颜色表示一个text/non-text score

fine-scale detection和RNN连接可以预测在垂直方向上的累积位置。在水平方向上,图片被划分成一串16-pixel宽的proposals序列。当在两个水平侧( horizontal sides)的text proposals不能准确被一个ground truth文本行区域覆盖时,或者一些side proposals被丢弃时(例如:具有一个较低的text score),这会导致一个不精准的定位,如图4所示。这种不准确在通用目标检测中不是很严格,但在文本检测中不能忽视,尤其是对于那些小尺度文本行或词。为了解决该问题,我们提供了一个side-refinement方法,可以准确地为每个anchor/proposal估计在水平左侧和水平右侧的offset(被称为side-anchor或side-proposal)。与y轴坐标的预测相似,我们计算了相对offset:

…(4)

其中,是相对于当前锚点最近水平侧(比如:左或右侧)的x预测坐标。是ground truth侧在x轴坐标,通过BT 边界框和锚点位置预先计算好。是在x轴的锚点中心。是锚点宽度,它是固定的,。当将一个检测到的fine-scale text proposals序列连接成一个文本行时,该side-proposals被定义成start proposals和end proposals。在图4中的一些检测样本通过side-refinement进行提升。 side-refinement可以进一步提升位置准确率,在SWT的Multi-Lingual datasets上产生2%的效果提升。注意,side-refinement的offset可以通过我们的模型同时进行预测,如图1所示。它不需要一个额外的后置处理step。

3.4 模型输出和Loss functions

CTPN有三个outputs,它们会一起连接到最后的FC layer上,如图1(a)所示。三个outputs同时预测:text/non-text scores(s)、垂直坐标(等式(2)中的 )、side-refinement offset (o)。我们探索了k个anchors来在conv5中的每个空间位置上预测它们,在各自的output layer上产生2k, 2k和k个参数。

我们采用了多任务学习来联合优化模型参数。我们引入了三个loss functions:,会各自计算text/non-text score、坐标以及side-refinement的error。有了这些,我们会根据faster R-CNN中的多任务loss,最小化一个关于一第图片的总目标函数(L):

……(5)

其中,每个anchor是一个训练样本,i是minimatch中的一个anchor的索引。是anchor i为一个真实文本的预测概率。是ground truth。j是一个关于y坐标回归中合法anchors集合的anchor索引,定义如下。一个合法的anchor是一个已经定义的positive anchor(),或者具有一个与ground truth的text proposal具有Intersection-over-Union(IoU) > 0.5 的重合度。是第j个anchor相关的y坐标的prediction和ground truth。k是关于一个side-anchor的索引,side-anchor被定义成在距离ground truth文本行限定框左侧或右侧的水平距离(例如:32-pixel)内的一个anchors集合。分别是在第k个anchor相关的在x轴上的predicted offsets 和ground truth offsets。是regression loss。我们会根据之前的工作,通过使用L1 function进行平滑来计算它们。是用于平衡不同任务的loss weights,期望设置为1.0和2.0。是归一化参数,分别表示通过的总anchors数。

3.5 训练和实现细节

CTPN通过标准的BP和SGD来进行end-to-end的训练。与RPN相似,训练样本是anchors,它们的位置可以通过在输入图片中的位置进行预计算得到,因而每个anchor的labels可以从相应的BT box计算得到。

Training Labels:对于text/none-text分类,会分配一个二分类label:positive(文本)、negative(非文本)anchor。它们通过计算BT bounding box(通过anchor位置进行划分)的IoU overlap得到。一个positive anchor被定义为:

  • i. 一个具有一个与任意GB box有IoU>0.7的重合度(overlap)的anchor
  • ii. 一个anchor具有一个与GT box的最高IoU重合度的anchor

通过条件(ii)的定义,即使一个非常小的文本模式也可以分配一个positive anchor。这对于检测小尺度的文本模式很重要,这也是CTPN的一个核心优点。这与通用目标检测很不同。negative anchors被定义成与所有GT boxes具有IoU<0.5重合度的anchors。y坐标回归()的training labels以及offset regression ()分别通过等式(2)和(4)定义。

训练数据:在训练过程中,每个minibatch样本都从单个图片中随机收集。每个mini-batch的anchors数目固定在,正负样本的比例在1:1. 如果一个mini-batch的正样本小于64个,会用负样本进行补齐。我们的模型训练了3000张自然图片,包含229张来自ICDAR 2013训练集的图片。我们收集了其它图片并进行人工标注上相应的文本行的bounding boxes。所有这些自收集的训练样本在所有的benchmarks的任意测试图片没有重合。输入图片将它的short side设置为600进行训练,来保持它原始的比例尺。

实现细节:我们根据标准惯例,探索了极深的VGG16模型在ImageNet上的预训练。我们使用高斯分布为(0, 0.01)的随机权重来为new layers(例如:RNN和output layers)进行初始化。模型通过固定前两个convolutional layers的参数来进行end-to-end训练。我们使用0.9的momentum和0.0005的weight decay。learning rate在前16k次迭代设置为0.001, 在之后的4K次迭代使用0.0001的learning rate。我们的模型使用Caffe框架进行实现。

评测

略,详见paper。

参考

在各种类型的DNN漫天飘的时代,周老师等提出了gcForest算法。以下是论文核心部分的介绍:

3. gcForest算法

gcForest算法引入了cascade forest结构,以及multi-grained scanning。

3.1 cascade forest结构

DNN中的表征学习几乎全依赖于对原始特征(raw features)进行layer-by-layer的处理。受该点的启发,gcForest使用了一个层叠(cascade)结构,如图2所示,每一级(level)cascade会接受由先前级(preceding level)处理后的信息,然后输出它的结果到下一级(next level)中。

图2:cascade forest结构。假设,cascade的每一级(level)只包含两个random forest(黑色)以及两个completely-random tree forests(蓝色)。假设要预测三个类;这样,每个forest将输出一个三维的分类向量,接着将他们串联起来对原始特征进行重新表征( re-representation)。

每一级是一个决策树森林的ensemble(比如:一个ensemble of ensembles)。此处,我们引入了不同类型的forests来增强diversity,因为对于ensemble的构造来说diversity至关重要。出于简洁性,这里我们使用完全随林树森林(completely-random tree forests)以及两个随林森林(random forest)。每个completely-random tree forests只包含500个完全随机的树,通过对该树的每个节点上做split来随机选择一个feature、完全生长直到纯叶子(pure leaf:每个叶子节点只包含相同类的样本)来生成。相似的,每个随机森林包含了500棵树,通过随机选择个特征作为候选(candidate),并选择对于split后满足最好gini系数的候选(d为输入特征数)。每个forest上的树数目是一个超参数,会在后面1.3描述。

给定一个样本,每个forest为它将生成一个类分布的估计:通过统计不同分类训练样本在叶子节点上的百分比,接着在同一forest上对所有树做平均,如图3所示,其中红色会高亮出样本落到叶子节点的path。

图3: 类向量生成的展示。在叶子节点上不同的标记表示了不同的分类

估计得到的类分布(class distribution)形成了一个类向量(class vector),接着将它们与原始的特征向量进行串联作为cascade下一级的输入。例如,假设有三个类,接着,4个forests的每个都会产生一个三维的类向量;接着,下一级cascade会多接收12个(3x4)扩张特征。

注意,这里我们采用了类向量的最简形式,例如:样本落到的叶子节点上的类分布。结果表明,少量扩展的特征可以传达非常有限的扩张信息,当原始特征向量很高维时很可能被淹没。我们将在实验中展示,这样简单的特征扩展其实是有好处的。预期上如果有更多的扩展特征会收到更大的收益。实际上,显然更多特征可以被合并进去,强如:父节点的类分布表示着先验分布(prior distribution),兄弟节点(sibling nodes)表示着互补分布(complementary distribution)。

为了减小overfitting的发生,由每一个forest生成的类向量通过k-fold交叉验证产生。实际上,每个样本被用于K-1次训练,产生k-1个类向量,接着求平均产生最终的类向量作为下一级的扩展特征。在新一级后,整体cascade的效果会通过验证集被评估,如果没有大的效果增益,训练过程会终止;cascade levels的数目会被自动决定。注意,当考虑训练成本、或者有限计算资源时,使用训练误差(training error)而非交叉验证误差(cross-validation error)可以被用于控制cascade的生长。通过对比DNN(它的模型复杂度确定),gcFroest会自适应地决定它的模型复杂度。这允许它能应用于不同规模的训练数据,而非只限于大规模数据。

3.2 Multi-Grained Scanning

DNN在处理特征关系上很强大,例如,CNN在图片数据上很有效(其中原始像素间的空间关系是很重要的);RNN对于序列型数据很有效(其中序列关系很重要)。受它们的启发,gcForest使用滑动窗口(sliding windows)来扫描原始特征。假设有400个原始特征,我们使用100个特征的window size。对于序列数据,可以通过对每隔一个特征进行窗口滑动来生成一个100维的特征向量;总共可以生成301个特征向量。如果原始特征具有空间关系,比如:在400个图片像素上的20x20的panel,接着一个10x10的window可以产生121个特征向量(比如:121 10x10 panels)。所有的特征向量从正负训练样本上被抽取(忽略正负),接着被用于生成像3.1所述的类向量:从相同size的window中抽取的样本会被用于训练一个completely-random tree forest和一个 random forest,接着生成的类向量被串联作为转换后的特征。如图4所示,假设存在3个类和使用100维的window,对应于一个400维的原始特征向量,会产生一个1806维的转换特征向量。

图4: 使用滑动窗口扫描进行feature re-representation。假设存在三个类,原始特征是400维,滑动窗口是100维。

对于从窗口中抽取的样本,我们会简单地为他们分配原始训练样本带有的label。这样,一些label分配本质上是不正确的。例如,假设原始训练样本是一个关于“car”的正样本图像;很明显许多被抽取的样本(extracted instances)不包含一个car,因而它们相当于会被不正确地标记成正样本。该方法实际上是与Flipping Output方法有关:这是一种用于ensemble中增强diversity的典型的输入特征操作法。

图4展示了滑动窗口的一个size。通过使用多个size的滑动窗口,会生成不同粒度的特征向量,如图5所示。

图5: gcForest的整体过程。假设要预测三个类,原始特征400维,使用三个不同size的滑动窗口。

图5归纳了gcForest的整体流程。对于m个训练样本,一个100个特征size的窗口会生成一个 (301 x m) 的100维训练样本的数据集。这些数据会被用于训练一个completely-random tree forest和一个random forest,每一个包含了500 trees。如果要预测三个类,会获得3.1节中描述的一个1806维的特征向量。转换的训练集接着被用于训练第一阶段(1st-grade)的cascade forest。

相类似的,对于每个原始的训练样本,size为200和300个特征的滑动窗口会分别生成1206维和606维的特征向量。转换后的特征向量,会与由前一级生成的类向量一起扩展,接着被用于训练第二阶段(2nd-grade)、第三阶段(3nd-grade)的cascade forests。该过程会重复,直到验证集效果收敛。换句话说,最终模型实际上是一个cascade of cascades,其中每个cascade包含了许多级(level),每个level对应于一个粒度的scaning,例如:第一个cascade包含了从Level $ 1_A $到Level $ 1_C $ (A、B、C)三个level,如图5所示。注意,对于不同的任务,如果计算资源允许的话,用户可以尝试更多粒度。

给定一个测试样本,它会经过multi-grained scanning过程来得到相应的转换后的特征表示,接着经过cascade直到最后一个level。最终的预测会通过对最后一个level聚合4个3维类向量,使用聚合的最大值来得到最终分类。

表1总结了DNN和gcForest的超参数,其中,实验中使用了缺省值。

表1: 超参数和缺省值。粗体高亮超参数具有相当大的影响;“?”表示缺省值未知,或者对于不同的任务需要不同的设置

4.实验

4.6 Multi-Grained Scanning的影响

为了研究cascade forest structure和multi-grained scanning的贡献,表9对比了更可怕额cascade forest的gcForest在不同的数据集上的表现。结果表明当存在空间特征关系、或者序列特征关系时,multi-grained scanning可以明显提升效果。

4.7 Cascade Structure的影响

gcForest的最终模型结构是cascade of cascades,其中每个cascade包含了多个level,每个level对应于一个粒度的scanning,如图5所示。有许多其它可能的方式来利用多粒度(multi grain)的特征,比如:将所有特征连接起来,如图6所示。

图5: $gcForest_{conc}$变种,它会将多个grain的特征连接起来。假设有三个类要预测,原始特征是400维,使用三个size的滑动窗口。

表10比较了gcForest和$gcForest_{conc}$。

4.8 更大模型

结果表明,更大的模型趋向于提供更好的效果,由于计算资源因素,我们没有尝试更多的grains,forests,trees。

注意,计算设备对于更大的模型训练是很重要的,比如:GPUs 之于DNN。另一方面,一些新的计算设备,比如: Intel KNL of the MIC (Many Integrated Core),可以为gcForest提供类似于GPU对DNN那般的潜在加速。另一方面,gcForest的一些组件,比如:multi-grained scanning,可以通过利用GPU来加速。另外,使用分布式计算还有大量优化空间。

参考

https://arxiv.org/pdf/1702.08835.pdf

google在2017年提出了一个Deep&Cross Network的模型:

1.介绍

在该paper中,提出了Deep&Cross Network(DCN)模型,它能对sparse和dense的输入进行自动特征学习。DCN可以有效地捕获关于有限阶(bounded degrees)上的有效特征交叉,学到高度非线性交叉,无需人工特征工程或暴力搜索(exhaustive searching)。并且计算代价低。

  • 我们提出了一个新的cross network,它显式地在每个layer上进行特征交叉(feature crossing),可有效学习有限阶(bouned degrees)的特征交叉预测,无需人工特征工程和暴力搜索。
  • 该cross network简单有效。通过设计,最高的多项式阶在每一layer递增,由layer depth决定。该网络包含了所有阶的交叉项(直到最高阶),它们的系数都不同。
  • 该cross network内存高效,很容易实现。
  • 我们的实验结果表明,比起接近相同阶的DNN,DCN具有更低的logloss,更少的参数。

2.DCN

本节描述了Deep & Cross Network模型。一个DCN模型会以一个embedding and stacking layer开始,接着并列连一个cross network和一个deep network。接着通过最后一个combination layer将两个network的输出进行组合。完整的DCN模型如图1所示。

图1: Deep & Cross Network

2.1 Embedding and Stacking Layer

输入数据带有sparse和dense feature。在大规模推荐系统的CTR预测中,输入几乎都是类别型特征(categorical features),比如:”country=usa”。这样的feature通常被编码成one-hot vectors,比如:”[0,1,0]”;然而,对于大的vocabularies,这通常会产生超高维度的特征空间。

为了减小该维度,我们使用一个embedding procedure来将这些二元features转换到关于真实值(real values)的dense vectors中(称为embedding vectors)。

…(1)

其中是embedding vector,是第i个category的二元输入,是对应的embedding matrix,会与网络中的其它参数一起进行优化,分别是embedding size和vocabulary size。

最后,我们将embedding vectors,以及归一化稠密特征(normalized dense features)进行stack成一个vector:

…(2)

2.2 Cross Network

新的cross network的核心思想是,将显式特征(explicit feature)以一种有效方式进行交叉。cross network由多个cross layers组成,每一个layer具有以下的公式:

…(3)

其中:

  • 是列向量(column vectors),分别表示来自第l层和第(l+1)层cross layers的输出;
  • 是第l层layer的weight和bias参数。

在完成一个特征交叉f后,每个cross layer会将它的输入加回去,对应的mapping function f:,刚好等于残差。一个cross layer的可视化如图2所示。

图2: 一个cross layer的visualization

特征的高阶交叉(high-degree interaction):cross network的独特结构使得交叉特征的阶(the degress of cross features)随着layer的深度而增长。对于第l层layer,它的最高多项式阶(在输入上)是. 实际上,cross network由这些交叉项组成,对应的阶从1到l+1. 详见第3节。

复杂度分析:假设表示cross layers的数目,d表示输入维度。那么,在该cross network中涉及的参数数目为:

一个cross network的时间和空间复杂度对于输入维度是线性关系。因而,比起它的deep部分,一个cross network引入的复杂度微不足道,DCN的整体复杂度与传统的DNN在同一水平线上。如此高效(efficiency)是受益于的rank-one特性,它可以使我们生成所有的交叉项,无需计算或存储整个matrix。

cross network的参数数目少,从而限制了模型的能力(capacity)。为了捕获高阶非线性交叉,我们平行引入了一个deep network。

2.3 Deep Network

Deep network是一个fully-connected feed-forward神经网络,每个deep layer具有以下的公式:

…(4)

其中:

  • 分别是第l层和第(l+1)层hidden layer;
  • 是第l个deep layer的参数;
  • 是ReLU function。

复杂度分析:出于简洁性,我们假设所有的deep layers具有相同的size。假设表示deep layers的数目,m表示deep layer的size。那么,在该deep network中的参数的数目为:

2.4 Combination Layer

Combination Layer将两个network的输出进行拼接(concatenate),然后将该拼接向量(concatenated vector)feed 进一个标准的logits layer上。

下面是一个二分类问题的公式:

…(5)

其中:

  • 分别是来自cross network和deep network的输出
  • 是combination layer的weight vector,其中

loss function是logloss,带有一个正则项。

…(6)

其中 是等式(5)计算得到的probabilities,是true labels,N是输入的总数,正则项参数。

我们对两个network进行jointly train,在训练期间,每个独立的network会察觉到另一个。

3.Cross Network分析

在这一节,我们分析了DCN的cross network,以便于更有效地理解。我们提供了三个视角:多项式近似,泛化到FM,有效投影。为了简洁,我们假设:

概念:假设在中的第i个元素是。对于多索引(multi-index) ,以及,我们定义了:

术语:交叉项的阶(degree)由定义。一个多项式的阶由它的项的最高阶决定。

3.1 多项式近似

根据维尔斯特拉斯逼近定理(Weierstrass approximation theorem),任意满足特定平滑假设条件下的函数,可以通过一个多项式进行逼近到一个特定的精度上。因而,我们从多项式近似的角度分析了cross network。特别的,cross network会以一种高效的、有表现力的、能更好地对现实世界数据集进行泛化的方式,近似相同阶的多项式类。

我们详细研究了一个cross network,将它近似成相同阶的多项式类(polynomial class)。假定表示n阶的多元多项式类(multivariate polynomial class):

…(7)

在该类中的每个多项式具有个系数。只有个参数,cross network包含了在相同阶的多项式中的所有交叉项,每一项的系数与其它项各不相同。

理论 3.1: 一个l-layer的cross network,具有i+1个layer,定义成:。假设网络的输入是,输出是,参数是。接着,多元多项式会以下面的类进行重现(reproduce):

其中:

  • 其中 , 是一个与独立的常数
  • 是多元索引(multi-indices),
  • 是indice 的所有排列(permutations)的集合。

定理3.1的理论证明详见paper中的附录。举个例子,的系数,其中。直到一些常数,其中;其中

3.2 FM的泛化

cross network共享参数,类似于FM模型的参数共享,并扩展到了一个更深的结构上。

在FM模型中,特征与一个 weight vector 相关联,交叉项的权重通过 计算得到。在DCN中,与标量有关,的权重是集合的参数乘积。两种模型都会为每个特征学到一些与其它特征相互独立的参数,交叉项的权重是相应参数的一种特定组合。

参数共享(parameter sharing)不权使得模型更有效,也使模型可以泛化到未见过的特征交叉上,对噪声更健壮。例如,使用sparse features的数据集。如果两个二元特征很少或者几乎从未在训练集中共现过,假设,,接着,学到关于的权重不会带有对预测有意义的信息。

FM是一个浅层结构(shallow structure),受限于交叉项的阶是2. 而DCN可以构建所有的交叉项,其中阶 由一些常数决定,见理论3.1。因而,cross network扩展了参数共享的思想,将单个layer扩展到多个layer,并且有更高阶的交叉项。注意,与高阶FM不同的是,在cross network中的参数数目,只随着输入维度线性增长。

3.3 有效投影

每个cross layer会以一种有效方式,将在间的所有pairwise交叉进行投影到输入维度上。

考虑到是一个cross layer的输入。cross layer首先隐式构建了个关于的pairwise交叉,接着以一种内存高效的方式,隐式地将它们投影到维度d上。这种直接的方式会带来3次方开销。

我们的cross layer提供了一种有效的解决方式,将开销减小到维度d的线性开销上。考虑。事实上等于:

…(8)

其中,row vectors包含了所有的pairwise交叉,投影矩阵具有一个块对角化结构,其中是一个列向量。

4.实验结果

在本节中,我们评估了CDN在多个数据集上的效果。

4.1 Criteo Display Ads数据集

Criteo Display Ads数据集用于预测点击率。具有13个integer features和26个categorial features。其中,每个category都具有一个很高的维度基数。对于该数据集,在logloss上提升0.001可以看成是巨大的提升。当考虑到在一个很大的用户基数时,在预测准确率(prediction accuracy)的一个小的提升,可以为公司带到来一个大的回报。数据包含了11GB的包含7天的用户日志(~41000,000条记录)。我们使用前6天的数据做为训练,并将第7天的数据随机划分成等size的validation和test set。

4.2 实现细节

DCN在tensorflow上实现,我们会讨论一些关于训练CDN的细节。

数据处理和embedding。实数型特征通过一个log转换进行归一化。对于类别型特征,会将这些特征嵌入到dense vectors中,维度为 。最后将所有的embedding结果拼接(concatenating)成一个维度为1026的向量。

优化(Optimization):我们使用Adam optimizer,mini-batch进行随机优化。batch size=512. Batch normalization被应用于deep网络,gradient clip norm设置为100.

正则化:我们使用early stopping,我们未发现L2正则或dropout很有效。

超参数:我们基于一个grid search来在hidden layers的数目、size、初始learning rate以及cross layers的数目上进行探索。hidden layers的数目范围为2一5, hidden layers的数目从32到1024. 对于DCN,cross layers的数目从1到6.初始learning rate从0.0001依次递增调到0.001. 所有试验都使用early stopping,训练step为150000, 超过它可能会发生overfitting。

参考

https://arxiv.org/pdf/1708.05123.pdf