基于松弛Hadamard矩阵的多模态融合哈希方法

庾 骏，黄 伟，张晓波，尹贺峰

（1. 郑州轻工业大学计算机与通信工程学院，河南郑州 450000；2. 江南大学计算机与人工智能学院，江苏无锡 214000）

1 引言

随着社交媒体和移动互联网的发展，多媒体数据呈现爆炸式增长，增大了信息搜索的挑战［1］. 多媒体信息通常以图像、文本、视频、音频等多种形式出现［2］. 例如一个主题网页中包含了多种类型的媒体数据，这些不同媒体数据间有很强的互补性. 哈希作为一种有效的技术已经在信息搜索和模式识别领域引起了广泛的关注［3］. 哈希方法编码高维的数据为二值编码，保留了原始数据间的相似性信息，这极大地加速了多媒体数据搜索的速度，同时节省了大量的存储空间［4］. 目前，存在的哈希学习方法主要分为2 种：单模态哈希［5～11］和跨模态哈希［13～18］. 众多方法中具有代表性的深度协同嵌入（Deep Collaborative Embedding，DCE）模型［19］联合端对端学习和协同因子分析以学习图像和标签的公共潜在空间，并且同时解决跨模态搜索、基于内容的图像搜索和标签扩展问题. 不同于单模态哈希和跨模态哈希方法，多模态哈希联合多个模态数据综合地表征实例样本. 目标查询和数据库数据都由异构多模态特征描述. 每一种模态都从不同的角度来描述实例，并有自己的特点. 因此，有必要将不同模态特征结合起来，综合表示查询和数据库数据，以实现准确的检索. 一种简单的方式是将多个模态特征串联起来，作为单模态哈希模型的输入. 然而，这种拓展方式产生较多冗余信息，不能很好地挖掘多模态的互补性，而且可能会造成维度灾难. 基于此观察，一些多模态哈希方法被提出.多特征哈希（Multiple Feature Hashing，MFH）［20］同时保留每种模态数据的局部结构，并全局地考虑所有模态的局部结构来学习一组哈希函数，以映射媒体数据到低维的哈希编码. 多特征核哈希（Multiple Feature Kernel Hashing，MFKH）［21］阐述多个模态数据的最优线性组合相似度. 多视图潜在哈希（Multi-view Latent Hashing，MVLH）［22］旨在寻找一个统一的核特征空间，在此空间中不同模态数据被融合，然后通过多个模态共享的潜在因子学习二值编码. 多视图离散哈希（Multi-view Discrete Hashing，MVDH）［23］联合执行矩阵分解和谱聚类以学习紧凑的哈希编码，这种联合学习方法使得MVDH 产生更具判别性的哈希编码. 线上多模态哈希（Online Multimodal Hashing with Dynamic Query-adaption，OMHDQ）［24］在成对标签的监督下学习哈希编码.OMH-DQ自适应地在线编码查询数据以捕获数据动态变化.

尽管上述方法已经取得了较好的进展，但是这些方法依然存在一些缺点：（1）大多数多模态哈希方法采用内积操作来保持同类样本编码一致性和异类样本间的差异性，由于二值化离散约束的限制，解决模型优化的问题存在较大的挑战；（2）采用固定的权值对多模态数据进行哈希编码，在复杂的多模态数据场景中不能捕捉多模态数据之间的互补信息，导致检索精度提升有限. 本文中提出了一种新的多模态哈希方法（Multimodal Fusion Hashing based on Relaxed Hadamard matrix，MFH-RH）有效地解决了上述问题. 图1 是MFHRH 的框架示意图.MFH-RH 采用了两阶段的学习方式保证了学习的哈希编码具有较强的判别能力，在优化过程得到了离散变量的闭合解，提高了优化的效率，同时以一种自适应的学习方式有效地捕捉模态间的互补信息，增强了模型在复杂数据环境中的适应能力和鲁棒性.代表性的哈希方法和本文提出的方法的主要特点被总结在表1中. 本文提出的MFH-RH框架的创新点如下.

图1 本文中MFH-RH的框架示意图

表1 代表性哈希方法和本文提出方法的主要特点

（1）MFH-RH 引入Hadamard 矩阵，在类别信息的监督下为多模态数据生成目标编码，促使同类数据逼近相同的哈希中心. 进一步地，对目标编码进行了松弛，增大了类间的间隔，同时采用图嵌入方法保证类内的紧凑型，因而增强了学习到的投影矩阵的判别能力.

（2）MFH-RH 采用两阶段的学习方式，能够自适应地捕捉样本模态间的互补信息，增强模型在复杂多模态数据场景中的哈希编码能力. 同时在优化过程中以闭合解的形式求解离散变量，有效地改善了优化求解效率，缓解了因二值化离散约束带来的挑战.

2 算法模型

2.1 问题描述

假定训练数据包含n个多模态实例样本，每个实例由M个不同媒体数据组成（如图片和文本），这些媒体数据是成对的且语义内容相似. 训练集中的第M媒体数据表示为其中dm是第M媒体数据的维度. 在训练集中，给定同类实例样本的类别信息.r表示实例样本的哈希编码长度，则第i个实例样本可表示成bi={+1，-1}r. 本文方法的目的就是根据已知的数据信息学习鉴别性的投影函数. 利用训练阶段学习的投影函数自适应地编码新到达的多媒体数据，生成可靠的哈希码. 在本文方法中，预先定义了每个类样本的哈希中心，促使相同类别的样本在汉明空间中逼近其类中心，不同类样本趋近于不同的类别哈希中心.C={c1，c2，…，ck}∈Rr*×k分别表示k个类别数据的哈希中心，其中r*表示哈希中心的维度. 在汉明空间选择合适的哈希中心需要满足如下要求：不同类别的哈希中心点之间的间距应该确保足够大，以使不同类样本在汉明空间中能够很好地分离开. 定义一个有效的哈希中心集，如定义一所示.

定义1哈希中心满足所有两两中心点间的距离的平均值大于或者等于r*/2，即

其中，N是两两哈希中心的组合数目，k是类别数目，DH表示汉明距离.

通过Sylvester方法［25］生成的Hadamard矩阵具有以下属性：

（1）它是一个r*阶的方阵，其中的元素是+1 或者-1.r*满足

（2）它的每行之间和每列之间都是正交的，这就确保了任意2列或2行之间的汉明距离为r*/2.

通过上述分析，可以看出Hadamard 矩阵的列向量或者行向量满足定义1，可以作为类哈希中心点. 值得注意的是生成的哈希中心的维数r*不一定等于输出编码长度r. 为了解决这个问题，采用局部敏感哈希（Local Sensitive Hashing，LSH）［26］来转换Hadamard 矩阵，以确保哈希中心和输出编码的长度一致. 具体为

2.2 训练阶段

针对第m媒体数据Xm，首先计算它的非线性 表 示φm，其 中φm中 的 第i列 为是从第m媒体数据中采用k-means聚类算法计算获得的p个锚点样本，σm表示高斯核参数. 可以获得如下映射模型：

其中，μm是第m媒体数据对应的权值系数，Wm是第m媒体数据的投影矩阵.

H被严格地限制为二值编码，为了使其具有更大的自由度，将严格的二元约束放宽为软约束. 使用松弛变量矩阵E=H+H⊙Q来取代目标编码矩阵H，其中⊙是矩阵的Hadamard 乘积，具体的推导过程见附录1. 式（4）能被改写成

其中，V是低维子空间的表示矩阵，β和λ表示惩罚参数.

为了促进类内的紧凑型，构造类紧凑性图. 邻接图被定义如下：

其中，σ是热核参数是多个配对的不同媒体数据的级联特征. 在转换后的子空间中，同类样本应该保持紧密. 基于图的正则项如下所示：

其中，L=D-S；D是一个对角矩阵，它的第i个元素定义为；Tr(·)表示矩阵的迹.

联合式（5）和式（7），总的目标函数如下所示：

其中，α，β和λ是可调参数.

上述目标函数（8）是非凸问题，很难直接对其优化求解. 采用常用的交替方向乘子法（Alternating Direction Method of Multipliers，ADMM）对每个变量进行交替优化. 具体的过程如下.

步骤1：固定其他变量，优化Wm. 很容易获得关于Wm的子问题，如下所示：

令式（9）关于Wm的偏导等于零，可以获得其解：

步骤2：固定其他变量，优化V. 假设E=H+H⊙Q，Q≥0，其子问题如下：

同样令式（11）关于V的偏导等于零，可得它的解为

步骤3：固定其他变量，优化Q. 令R=V-H，则关于Q的子问题如下：

根据文献［28］，能获得最优解如下：

步骤4：固定其他变量，优化μm. 保留与μm有关的项，可以获得

其中Gm=||V-Wmφm||2F. 利用拉格朗日乘子法将式（15）转换成

令式（16）关于μm的偏导等于零，获得最终的解为

重复上述4 个步骤，直到算法收敛. 最后获得最优的投影矩阵Wm和权重系数μm. 哈希编码函数能被定义为其中xqm表示询问样本的第m媒体数据.

2.3 哈希编码阶段

然而，从2.2 节中学习获得的权重系数μm并不能很好地捕捉到动态数据的差异性. 期望在编码较大差异的数据时，不同媒体（模态）对应的权值能够自适应地调整. 受此思想的启发，采用一种自加权模式为新达到的多媒体数据进行哈希编码，以获得更加精确的哈希码. 在编码阶段，假定数据是以批数据形式呈现. 新达到的批数据被编码后存储在数据库中. 自适应的哈希编码过程如下所示.

其中，Bq和nq分别是新数据实例样本的编码和数目是新样本的非线性转换后的表示矩阵. 采用交替更新Bq，μqm来获得数据最优的编码特征. 具体如下.

固定Bq更新μqm：关于μqm的最优值为

固定μqm更新Bq，能获得其闭合解：

最后输出的Bq被当成是新达到的批数据的最后输出编码，并存储于数据库中以供询问数据查询. 本文方法的整个过程被总结在算法1 中. 算法的复杂度分析如下：计算φm需要O(np)，则M个模态的计算复杂度为O(Mnp)；更新Wm耗费O(np2)，则M个模态的计算复杂度为O(Mnp2)；由于式（15）中的求逆过程只需计算一次，因此计算V的时间复杂度为O(rn2)；算法总的时间复杂度为O(iter×(Mnp2+rn2)，其中iter是总的迭代次数.

算法1 基于松弛Hadamard矩阵的多模态融合哈希(MFH-RH)训练阶段:输入:训练数据矩阵Xm ∈Rdm×n,数据的类别信息,参数α,β,γ和λ.根据2.1节生成训练数据的目标输出编码H ∈Rr×n.计算训练数据的非线性转换矩阵φm.计算邻接矩阵S,并得到图拉普拉斯矩阵L.初始化:投影矩阵Wm,μm,V重复:步骤1 根据式(10)更新Wm;步骤2 根据式(12)更新V;步骤3 根据式(14)更新Q;步骤4 根据式(17)更新μm;直至收敛.输出:投影矩阵Wm(m=1，…，M).哈希编码阶段:For q=1,…,T do获取新达到的多媒体数据实例Xq计算非线性表示矩阵φq m重复:根据式(19)计算μq m根据式(20)计算Bq直至收敛.输出Bq 并存储在数据库end

3 实验及结果分析

在这部分，在2个公开数据集上执行多媒体检索实验来验证提出的MFH-RH的有效性. 实验数据、对比方法、评估方法和详细的实验结果将被详细介绍. 所有实验运行在Intel（R）Core（TM）I7-10700 CPU @2.9GHz和16GB内存的工作站上.

3.1 数据集

3 个常见的多模态数据集被用来评估所有对比算法和MFH-RH的检索性能.

WiKi 数据集［29］是一个单标签多模态数据集，总共包含2866 个多媒体文件. 每个多媒体文件包含一张图片和一段文字，且被划分为10 个类别中的一类. 每张图片表示成128维SIFT 直方图向量. 每段文字通过Latent Dirichlet Allocation（LDA）［30］表示为一个10 维的特征向量. 随机选取一个包含2173 个文件的子集作为训练集和数据库，剩余的963个文件作为询问测试集.

Pascal Sentence 数据集［31］包含1000 对图像-文本样本. 该数据集被划分为20 个种类. 每个类别包含50 对图像-文本. 随机从每类中抽选30 对样本组成了包含600对样本的训练集. 剩余的样本作为询问测试集. 每张图片由4096 维CNN 视觉特征表示［32］. 针对文本，首先获得300 维的BoW（Bag of Word）特征，然后利用LDA 模型获取在100个主题中的概率分布.

MirFlickr 数据集［17］从Flickr 网站收集而来. 数据集被划分为24 个种类，包含了25 000 对图像-文本. 保留了至少出现20次的标签，然后移除那些没有标签的数据. 每对样本被分配到多个类别. 因此，MirFlickr 是个多标签数据集. 每张图片被表示为150维的边缘直方图特征. 至于文本，利用Principal Component Analysis（PCA），从BoW特征中抽取的500维向量作为其特征表示. 随机从包含15 902对样本的数据库中随机选择5000对数据作为训练集，剩余693对图像文本作为询问测试集.

3.2 实验设置

在训练阶段，Hadamard 矩阵的列作为对应类的哈希中心. 对于单标签数据集WiKi 和Pascal Sentence，数据的目标编码设置为它所属类的哈希中心. 而针对多标签数据集MirFlickr，将多个类哈希中心的质点作为数据的目标编码. 在实验中，对比7 种相关的哈希方法来验证提出的方法在多媒体检索任务中的有效性. 它们被划分为两大类. 一是多模态哈希方法，包括MFH［20］，MVLH［22］和OMH-DQ［24］. 二是单模态哈希方法，包括ITQ［6］，LSH［7］，DLLE［8］，HCOH［9］. 由于单模态哈希方法并不能同时处理多个模态数据，为了公平对比，采用级联操作将多模态级联后的特征作为模型的输入. 参考原始论文中给出的参数候选范围，对各个模型中的手动参数进行细心调整并记录最好的结果. 在提出的模型中，α和β的值在一个较大候选范围{1e-5，1e-4，1e-3，1e-2，1e-1，1e1}内 进 行 调 整.λ在WiKi，Pascal Sentence和MirFlickr分别设置为1e-5，1e-2和1e-1.γ设置为0.5. 训练阶段，算法的最大迭代次数为50. 采用kmeans聚类算法获得锚点样本，在3个数据集上锚点数目p分别为1000，600，1000. 使用平均精确度（mean Average Precision，mAP）作为检索性能的评价指标. 针对一个询问数据q，Average Precision（AP）的定义如下：

其中，Pq(i)表示前i个检索结果的精度；如果第i个结果是真的邻域样本，则δq(i) =1，否则δq(i) =0；lq是前R个检索结果的正确结果的数目；mAP 被定义成所有询问样本的平均AP. 在本文实验中R设为数据库的尺度.

此外，另一种广泛使用的评价标准——哈希查找（hash lookup）被采纳在对比实验中. 构造查找表以返回落在查询点的汉明半径d内的那些点. 计算所有查询的平均召回率和准确率. 根据哈希查找协议，随着汉明半径d的增加，绘制了Precision-Recall（PR）曲线以便更直观地评估性能.

3.3 对比实验结果

在这部分，将讨论和分析在3 个不同数据集上的实验结果. 详细的实验观察描述如下（表中加粗的数据表示性能最好的方法）. 在WiKi，Pascal Sentence 和MirFlickr 数据集上的对比实验结果如表2 所示. 可以清楚地观察到本文提出的MFH-RH 在WiKi 和Pascal Sentence 上超过了所有的对比方法. 在MirFlickr 上，当哈希编码设置为16bit 时，本文提出的MFH-RH 低于OMH-DQ. 但是随着编码长度的增大，本文提出的方法在精度上高于所有方法. 本文提出的MFH-RH 优于对比方法HCOH. 具体地，在WiKi，Pascal Sentence 和Mir-Flickr 上，MFH-RH 针对不同哈希编码长度设置下的检索精度的平均值分别高于HCOH 14.7%，34.1%和2.8%. HCOH 是一种基于Hadamard 矩阵的线上哈希学习方法. 与HCOH 对比的实验结果表明，多模态数据的有效融合相比简单的级联特征在哈希学习中能更好地挖掘多模态数据间的互补信息. 本文方法在Pascal Sentence 上提升相当明显的可能原因在于该数据集采用高维度的CNN 特征，级联后的多模态特征携带的冗余信息太多. 与OMH-DQ 相比，本文提出的方法在WiKi 和Pascal Sentence 上分别取得了平均26%和10.9%的精度提升. 这说明利用Hadamard矩阵引导哈希函数学习是非常有效的，极大增强了哈希编码的判别性. 随着编码长度的增大，本文提出的MFH-RH 在性能上得到稍微改善. 在Pascal Sentence 数据集上，当哈希编码设置为32 bit，64 bit和128 bit 时，检索性能没有获得进一步改善. 这说明本文方法对哈希编码长度不是特别敏感，在较短编码长度设置下能够取得满意的检索精度. 图2 展现 了 所 有 方 法 在WiKi，Pascal Sentence 和MirFlickr 上的PR 曲线. 从图2 中可以观察到，本文提出的方法优越于其他的方法. 这些实验结果表明，基于Hadamard矩阵的多模态融合哈希在多媒体数据检索中是非常有效的.

图2 所有方法在三个数据集上的PR曲线

表2 各算法在WiKi、Pascal Sentence、MirFlickr数据集上执行多媒体数据检索的mAP性能比较

为了获得直观的视觉对比，图3呈现一个多模态检索的例子. 几种对比方法和本文提出的MFH-RH 返回的5个检索结果被展现在图3的右边. 检索结果是按从左到右进行排序的，由于文本通常比较长，因此检索结果中实例的文本数据被省去，带有红色框的实例代表是正确相关的检索结果. 从图3 中可以发现，ITQ 和LSH 在前5 个检索结果中未发现正确的检索结果；DLLE，HCOH，MFH，MVLH，OMH-DQ 在返回的结果中排序为第四个或第五个实例才能找到相关正确的结果. 而本文提出的MFH-RH 的相关结果的排序是第二个和第三个. 也就是说在前三个检索结果中，本文提出的MFH-RH 就能检索出与询问样本相关的检索结果.图3 中展现的检索例子表明，MFH-RH 方法优于其他的对比方法，在多模态检索任务中能表现出优越的性能.

图3 WiKi 数据集上多模态检索任务实例（由于篇幅限制，检索结果只呈现图片内容）

深度多模态哈希模型将异构多模态数据与当今先进的深度学习框架结合学习辨别性的二值化编码特征，可以捕捉高层语义信息，在多模态哈希检索任务中取得了较高的检索精度. 深度多视图哈希（Deep Multi-View Hashing，DMVH）［33］和正交正则化多视图哈希（Deep Multi-modal Hashing with Orthogonal Regularization，DMHOR）［34］都是无监督的深度方法. 深度协作多视图哈希（Deep Collaborative Multi-View Hashing，DCMVH）［35］是一种有监督的深度多模态散列方法，它在类标签的监督下学习紧凑的散列码. 语义驱动可解释的深度多模态哈希（Semanticdriven Interpretable Deep Multi-modal Hashing，SIDMH）［36］在深度哈希结构中生成语义驱动的可解释哈希编码特征. 在实验中，本文算法与上述深度哈希方法在Pascal Sentence 数据集上进行实验对比，对比实验结果被呈现在表3 中. 与上述多模态深度模型相比，本文提出的算法取得了最好的检索性能. 相比最佳的对比方法DCMVH，本文提出的MFH-RH 在所设置的多种哈希长度的实验条件下获得平均0.91%的改善. 实验结果表明，MFH-RH 能够生成具有较强语义表达能力的哈希特征，进而有效地改善多模态哈希检索精度.

表3 不同方法在Pascal Sentence数据集上的性能比较

3.4 消融实验结果

本文基于Hadamard矩阵设计一种松弛的哈希中心去指导投影矩阵学习，以学习具有强大判别性的哈希函数. 松弛的目的是增大不同类别数据间的边界. 执行消融研究来验证松弛模型的有效性. 式（4）是无松弛步骤的模型，记为MFH. 在3 个数据集上进行对比实验，实验结果展现在表4 中. 从实验结果中看出MFHRH 在检索性能上优于MFH，尤其是在WiKi 和Pascal Sentence数据集上. 因此，这种基于Hadamard矩阵的松弛方法能够改善哈希检索的性能. 对数据进行编码过程中，采用一种自适应的加权模式对多模态数据编码，以捕捉多媒体数据之间的差异性. 为了验证其有效性，设计下面的对照实验. 令“固定权值”表示在训练阶段学习获得的权值用于编码阶段.“动态权值”指的适应不同数据的动态权值. 对比实验结果如图4所示. 从实验结果中，“动态权值”模式相比“固定权值”性能得到了改善. 相比MirFlickr 数据集，在WiKi 和Pascal Sentence 上的提升更加明显. 为了进一步研究其原因，通过实验观察数据编码过程中图片模态和文本模态对应权值变化趋势. 从图4 中可以看出WiKi 和Pascal Sentence 数据集上权值变化相比MirFlickr 波动幅度更大. 这说明WiKi 和Pascal Sentence 数据的差异性相对较大. 结合图4、图5 的实验结果，可以发现自适应的加权模式在数据差异较大的数据环境下更具鲁棒性.

图4 数据编码过程中图片模态和文本模态对应权值变化趋势

图5 自适应的动态权值和固定权值的对比实验结果

表4 MFH-RH与非松弛的MFH方法的多媒体检索性能比较

3.5 参数敏感性分析

本文提出的模型存在2个惩罚参数α和β. 为了探究其对检索结果的影响，在实验过程中将它们的值设置在一个较大的候选范围内{1e-5，1e-4，1e-3，1e-2，1e-1，1e1}，来观察检索性能的变化. 从图6中在3个数据集上的实验结果可以观察到，本文模型在一个较大区域内mAP值的变化较小. 因此本文模型对超参数的敏感性不太大.

图6 不同α和β组合对应的mAP值

3.6 算法收敛性分析

在训练阶段，基于算法1的整个过程被重复直至算法收敛或者达到最大迭代次数. 图7 展示哈希长度设置为64 bit 时，WiKi，Pascal Sentence 和MirFlickr 上的收敛曲线. 在其他哈希长度设置下，曲线的变化趋势与64 bit 长度的情况是相似的. 从图7 可以看出本文算法在10次迭代内就基本上趋于收敛.

图7 训练阶段算法的收敛性曲线

4 结束语

本文提出了一种用于多媒体检索的新型多模态哈希学习方法. 该方法在类别信息的监督下利用Hadamard 矩阵为数据生成目标哈希编码，指导判别性的哈希函数学习. 在提出的框架中，提出松弛严格的二值化目标编码为松弛变量矩阵，这使得拥有更大的自由度去拟合目标矩阵，从某种意义上增大了类间的间隔. 同时保留类内的局部流形结构，增强类内的紧凑性. 在编码阶段，引入一种自适应的多模态加权方式，有效地捕捉到数据的动态差异. 在3 个公开的多模态数据集上进行对比实验，在实验中本文提出的方法取得了很好的精度且超过了最新的方法. 实验结果表明，基于松弛Hadamard 矩阵的多模态哈希学习方法在多媒体检索中是非常有效的.

附录1

松弛变量矩阵E被定义为

式（22）中，qij≥0 有利于增大不同类别样本间的间距，以学习判别性的投影矩阵.其中

通过一个辅助变量Q和原始编码矩阵H联合表示松弛变量矩阵E，其中变量Q被定义如下：

因此E=H+H⊙Q，其中⊙是矩阵的Hadamard乘积.