论文: Deep Representation Learning with Target Coding - AAAI2015
作者: Shuo Yang, Ping Luo, Chen Change Loy, Kenneth W. Shum, and Xiaoou Tang
团队: CUHK, CAS shenzhen

Project HomePage

Supplementary Doc

Code-cuda-convnet

1-of-K code:长度为 K 的向量,第 k 个元素为 1,其它的为 0. [分类任务]

Target code:multi-label 预测问题.

图像分类一般采用单个类别标签作为 label,可以看做是 1-of-K 编码,类别标签所在位置的编码值为 1,其它非标签位置的编码值为 0.

Taget code 的方式,是将一个 class 类别表示为一个 0-1 向量,长度为 2 的乘方(幂)(如 2^3=8, 2^4=16, 2^5=32, 2^6=32, 作者代码给出的范围是 3-14),可能有多个位置的编码值为 1,而不仅仅是类别标签位置的编码值为 1. 假如数据集有 10 类(如 MNIST,Cifar10),则 class 类别的 label 向量长度至少为 2^4=16. 假如数据集有 1000 类(如 ImageNet),其Hadamard 矩阵至少为 2^10 × 2^10=1024,每 class 类别的label向量长度为 2^10=1024.

1. Target Coding 定义

假设 ${ \mathcal{T} }$ 为整数集,记为 字符集(alphabet set); ${ \mathcal{T} }$ 内的一个元素记为 符号(symbol). 如,${ \mathcal{T} = \lbrace 0, 1 \rbrace }$ 是一个二值字符集.

目标编码(target code) ${ \mathcal{S} }$ 是一个矩阵,${ \mathcal{S} \in \mathcal{T} ^{n×l} }$. 目标编码矩阵的每一行记为 码字(codeword). ${ l }$ 为每个码字(codeword)中的符号(symbols)数;n 为码字数(codewords).

对于目标编码 ${ \mathcal{S} }$,记 ${ \mathcal{A} = \lbrace \mathbf{\alpha}_{i}\rbrace_{i=1}^{n} }$ 为目标编码矩阵 ${ \mathcal{S} }$ 行元素的符号(symbols) 的经验分布集,如,当 i=1,2,...,n 时,${ \mathbf{\alpha}_i }$ 是长度为 ${ |\mathcal{T}| }$ 的向量,${ \mathbf{\alpha}_i }$ 的第 t 个元素是第 t 个符号(symbol) 在目标编码矩阵 ${ \mathcal{S} }$ 的第 i 行出现的频数.

同样地,记 ${ \mathcal{B} = \lbrace \mathbf{\beta}_{j}} \rbrace _{j=1}^{l}$ 为目标编码矩阵 ${ \mathcal{S} }$ 列元素的符号(symbols) 的经验分布集.

假设给定两个不同的行索引(row indices) ${ i }$ 和 ${ i^\prime }$,目标编码矩阵 ${ \mathcal{S} }$ 的 ${ i }$ 行和 ${ i^\prime }$ 行的 Hamming distance 为:${ |( j : \mathcal{S}_{ij} \ne \mathcal{S}_{i^\prime j} )| }$,即,Hamming 距离计算了两个向量中对应符号(symbol) 不相等的列索引数(column indices). 简便起见,将之记为 成对 Hamming 距离(pairwise Hamming distance).

Table 1 中给除了一种一对多(1-of-K)的二值目标编码,深度学习中一般用于表示 K 类 classes. K 个符号(symbols) 中的每一个元素是 0 或 1,分别表示特定 class 的概率. 此时,可以看做是目标编码矩阵的一种特殊形式,即 ${ \mathcal{S} = I }$. ${ I \in \mathcal{T}^{K×K} }$ 的单位矩阵.

可以简单直接的的到 1-of-K 编码的某些属性. 如,

记 ${ \mathbf{\alpha}_{it} }$ 为矩阵 ${ \mathcal{S} }$ 第 i 行中第 t 个符号(symbol) 的数目,i = 1,2, ..., K,这里 t=1, symbol=0;t=2, symbol=1. 由于每个码字(codeword) 只有一个符号(symbol),能够得出 ${ \mathbf{\alpha}_{i1} = \frac{K-1}{K} }$,${ \mathcal{\alpha}_{i2} = \frac{1}{K} }$.

相似地,可以得到 ${ \mathbf{\beta}_{j1} = \frac{K-1}{K} }$,${ \mathbf{\beta}_{j2} = \frac{1}{K} }$. 成对 Hamming 距离为 2.

2. 基于 Hadamard Code 构建 Class label

目标编码(target coding) 不仅对于目标预测具有纠错(error-correcting)作用,还有助于学习更好的特征表示.

采用普遍使用的错误纠正编码(error-correcting code) 方法 —— Hadamard Code,其可以由 Hadamard 矩阵生成.

假设矩阵 ${ \mathcal{H} \in (+1,-1)^{m×m} }$,其元素是 +1 或 -1,如果 ${ \mathcal{H} \mathcal{H}^T = mI }$,则记该矩阵为 Hadamard 矩阵. 其中,${ I }$ 为单位矩阵. Hadamard 矩阵要求任意两个不同的行和列分别都是正交的.

Hadamard 矩阵采用 Sylvester(Hedayat and Wallis 1978) 方法生成. 如,

给定 Hadamard 矩阵 ${ \mathcal{H} ^2 = [+ +; + -] }$,采用 Kronecker 乘积,有:${ \mathcal{H}^4 = \mathcal{H}^2 \otimes \mathcal{H}^2 }$;类似地,${ \mathcal{H}^8 = \mathcal{H}^4 \otimes \mathcal{H}^2 }$. 可以看出,Hadamard 矩阵的尺寸是 2 的幂(乘方)关系.

针对 Hadamard 矩阵的任意两个不同的行(或列),其长度为 m,则有 m/2 对元素的符号彼此相同,m/2 对元素的符号相反. 因此,任意两行的距离是常数,值等于 m/2.

现在,基于 Hadamard 矩阵,则可以构建目标编码矩阵 ${ \mathcal{S} }$.

假设 Hadamard 矩阵 ${ \mathcal{H} \in (+1,-1)^{m×m} }$,则去除 ${ \mathcal{H} }$ 的第一行和第一列,并将 +1 变成 0,-1 变成 1,即可的到目标编码矩阵 ${ \mathcal{S} \in \mathcal{T}^{(m-1) × (m-1)} }$. 根据 ${ \mathcal{H} }$ 的定义可知,矩阵 ${ \mathcal{S} }$ 的每一行和每一列都有 m/2 个 1. 由于 Hadamard 矩阵的任意两行都是正交的,则矩阵 ${ \mathcal{S} }$ 的成对 Hamming 距离等于 m/2.

Tabel 1 给出了一个由 ${ \mathcal{H}^8 }$ 得到的 7×7 目标编码矩阵 ${ \mathcal{S} }$.

实际上,由于 Hadamard 矩阵的长度 m 是 2 的幂(乘方),很难精确的到包含 K 个 classes 的 K 个码字(codewords). 故,记矩阵 ${ \mathcal{C} \in \mathcal{T} ^{K×(m-1)} }$ 是 K 个 classes labels 的矩阵,i = 1,2,...,K,第 i 个 class 是由矩阵 ${ \mathcal{C} }$ 的第 i 行标注的(labeled). 因此,矩阵 ${ \mathcal{C} }$ 是从目标编码矩阵 ${ \mathcal{S} \in \mathcal{T}^{(m-1)×(m-1)} }$ 中选取 K 个码字(codewords) 来构建的.

3. Target Coding 的属性

属性1. 目标编码矩阵 ${ \mathcal{S} }$ 每一行具有一致性.

Hadamard 编码的每一行都有 m/2 个符号(symbols) 等于 1.

矩阵行元素的一致性对于目标预测(target prediction) 会引入冗余(redundancy). 矩阵 ${ \mathcal{S} }$ 的每一行表示一个 class 类别标签.

与 1-of-K 编码不同的是,1-of-K 编码仅使用单个符号 ‘1’ 来表示 class 类别;

而 Hadamard 编码的每个码字(codeword) 都有相同数量的等于 ‘1’ 的冗余符号(symbols). 这种属性是错误纠正属性. 如果符号(symbols) 的有限数量的部分被损坏,仍更可能正确识别 object 类别.

符号 ‘1’ 的数量越多,则错误纠正能力越强,使得目标层(target layer)的响应能够直接用于最近邻分类.

属性2. 目标编码矩阵 ${ \mathcal{S} }$ 每一列具有一致性.

类似地,Hadamard 编码的每一列都有 m/2 个符号(symbols) 等于 1.

矩阵列元素的一致性也是特征表示学习需要的.

目标编码矩阵 ${ \mathcal{S} }$ 的每一列可以看做是一个决策函数(decision function),将输入空间分成两个平衡区域,如,近一般的 classes 类别在一个区域,剩下的 classes 类别被分组到另一个区域.

给定多个列,可以得到不同的划分区域,结合不同区域可能在输入空间产生指数个区域交叉(region intersections). 基于这样的属性,目标编码矩阵有助于产生更能区分数据的特征,的到数据的判别性和鲁棒性的特征描述.

属性3. 目标编码矩阵 $\mathcal{S}$ 的成对 Hamming 距离值为常数.

因为 Hadamard 编码的行和列都具有一致性,成对 Hamming 距离也是 $\frac{m}{2}$.

也就是说,任意两个码字(codewords) 间的 Hamming 距离都是码字(codewords) 长度的一半.

这种属性确保了,每一 class 类有其唯一的码字(codeword),并与其它 classes 类有相同的远离距离. 从同一 class 类采样的数据,被强制映射到相同的码字(codeword). 有助于特征不变性表示.

如前面说的,假设,Class 类别标签 ${ \mathcal{C} \in \mathcal{T}^{K×(m-1)} }$ 是通过从目标编码矩阵 ${ \mathcal{S} \in \mathcal{T}^{(m-1)×(m-1)} }$ 中选取 K 个码字(codewords) 构建的.

然而, 由于 $m$ 是 2 的乘方, 当 class 类别数小于 m-1 时,K < m-1,${ \mathcal{C} \in \mathcal{T}^{K×(m-1)} }$ 违背了属性2.

因此,提出一种贪婪搜索(greedy search)方法 来从矩阵 ${ \mathcal{S} }$ 中选取 ${ \mathcal{C} }$,以逼近 属性2.

从目标编码矩阵 ${ \mathcal{S} }$ 选取一个码字(codeword),当且仅当该码字(codeword)不破坏矩阵 ${ \mathcal{C} }$ 每一列的一致性时,才将该码字(codeword) 添加到矩阵 ${ \mathcal{C} }$.

例如,当 K=10, m=128 或 m=256 时,采用贪婪搜索和随机选取来构建矩阵 ${ \mathcal{C} }$. 如图:

矩阵列中符号(symbol) ‘1’ 的数量分布情况如 Figure 2. 可以看出,贪婪搜索方法能够更好的体现矩阵列元素的一致性(理想情况,所有的列都包含 5 个符号(symbols) '1'. 采用贪婪搜索算法,当 m=256 时, 95% 的列都包含了 4-6 个符号(symbols) '1'). 随机选取会导致列元素一致性不够好.

4. CNN 中 Target Code 的应用

给定数据集 ${ \lbrace \mathbf{x}_i, \mathbf{y}_i \rbrace _{i=1}^{N} }$,
${ \mathbf{x}_i }$ 为第 i 个样本,
${ \mathbf{y}_i \in \mathcal{C} }$ 为对应的 class 类别标签,N 为样本总数.

采用CNN 来学习特征表示,损失函数采用 Euclidean loss:

${ \mathbf{W}_l }$ 和 ${ \mathbf{b}_l }$ 分别为第 ${ l }$ 层的权重和偏置.

由于 Hadamard 编码与网络结构是独立的,因此,任何网络结构都可以. 例如图:


5. Results



Last modification:October 10th, 2018 at 01:30 am