随着互联网的普及, 社交平台、分享网站等网络平台丰富了图像和视频等可视媒体数据的发布、传播和获取途径.互联网和传统媒体的融合也进一步促进了图像和视频等媒体数据的爆炸性增长.数据的爆炸性增长在为用户提供更加丰富和多元化信息来源的同时, 也使得大量内容相似或重复的图像和视频等可视媒体充斥网络, 对互联网内容提供商来说, 过滤此类“垃圾内容”或对搜索到的相似内容进行重排序, 让用户从海量数据中快速检测到对自己有用或喜欢的媒体内容非常重要.同时, 根据用户搜索或观看的媒体内容进行个性化推荐, 也是互联网企业的重要业务.另外, 可视媒体的广泛传播在丰富人们文化娱乐生活的同时, 也为暴力恐怖、淫秽色情、谣言等有害信息的传播提供了便利, 这些有害图像和视频极大地危害了社会稳定和政府公信力, 淫秽图片或视频更是影响到青少年的身心健康, 因此, 对此类有害可视媒体内容的检测和过滤也十分必要.
针对上述问题, 利用人工方式很难对海量数据进行有效审核, 因此, 利用计算机技术对海量可视媒体内容进行自动分析, 从而高效地完成内容相似性搜索和检测是现有可行的方法.但在当前大数据环境下, 内容相似性搜索检测技术面临“维数灾难”的严峻挑战, 即随着内容特征维度的增加, 计算量呈指数增加.同时, 海量数据的内容存储和检索复杂度对现代计算机设备来说也是一个巨大的考验.虽然现有的计算机软/硬件水平和通信技术已有显著提高, 但对海量数据来说, 软/硬件处理能力和通信的带宽依然有限, 为解决以上难题和挑战, 哈希学习技术被提了出来, 并成为智能信息处理领域的研究热点.
哈希学习(learning to hash)[]结合数据自身的特性和分布, 通过机器学习方法将数据映射成二进制串的形式, 同时尽可能地保持原空间中的近邻关系, 哈希学习能够显著减少数据的存储和通信开销, 从而有效提高学习系统的效率.在现有哈希学习算法中, 无监督哈希方法和有监督哈希方法是两类主要形式.
无监督哈希学习算法在哈希函数设计或哈希码的学习过程中不需要样本标签信息, 其中, 谱哈希[, ]和迭代量化哈希[]及其改进版本是两类典型的无监督哈希算法.近年来, 在图像检索领域, 结合样本的其他属性, 出现了很多无监督哈希学习算法[-], 例如, Zhu等人[, ]提出了利用文本辅助的语义迁移构造无监督哈希算法; Liu等
人[]提出了基于序列紧凑码学习的无监督哈希算法; Jiang等人[]提出了可扩展图哈希算法; Sheng等人[]提出了基于流形的归纳式哈希算法.无监督的哈希算法大多从样本内在的特性和相互关系的角度设计哈希模型, 不需要样本的标签信息, 因此, 在样本标记成本过高或者在无法获得大规模数据样本标签的情境下, 无监督哈希算法起到了重要的作用.
与无监督哈希算法相比, 有监督哈希学习在哈希学习过程中充分利用了样本标签信息.例如, Lin等人[]结合标签信息, 提出一种使用图割和决策树构建的快速监督哈希方法; Wang等人[]通过最小化经验误差, 提出一种半监督哈希学习算法; Liu等人[]提出了基于核函数的监督哈希学习算法; Nie等人[, ]结合样本类标记和相似性标记分别提出了针对视频和跨模态检索的哈希学习算法.另外, 一些以样本顺序作为监督信息的学习算法[-]也是常见的有监督哈希学习方法.近年来, 随着深度学习的发展, 基于深度学习的监督哈希算法也陆续被提出[-].监督哈希学习算法充分利用了数据标签信息, 在性能上与无监督算法相比有了很大的提升.因此, 近年来越来越多的有监督哈希学习算法被研究者所关注.
在现有监督或无监督的哈希学习算法中, 线性模型、核函数模型、神经网络模型等都是常用的哈希函数形式和模型.哈希学习的目标之一是实现海量数据的快速检索, 而线性模型因其计算简单, 运行效率高, 更符合哈希学习算法快速检索的目标, 所以在哈希学习中得到广泛应用.另外, 一些核函数模型也是线性模型的变种, 因此, 线性模型在哈希学习算法中具有重要的地位.一般来说, 基于线性模型的哈希学习算法通过一系列线性关系的项来构造目标函数, 进而学习哈希函数.
具体来说, 设有N个样本组成的样本特征矩阵为X, 训练样本的标签矩阵为Y, 标签矩阵Y的元素为1或0, 分别表示属于或不属于对应类别.线性哈希模型的目标是学到一个可以保持样本特征空间相似性的哈希矩阵B.结合数据的分布和内在特性, 线性哈希模型的形式可以设计成多种形式, 同时也可以增加多种约束项和正则项.其中, 哈希码和原始特征之间的线性回归项是主要部分, 其刻画了特征矩阵和哈希矩阵之间的关系, 通过对其参数的学习和优化, 可以实现样本外的哈希学习.除了特征和哈希码的线性关系项之外, 在无监督哈希算法中, 还通常包含样本原始特征相似关系和哈希码相似关系保持项, 而在有监督哈希算法中, 标签矩阵和哈希矩阵以及标签矩阵和特征矩阵之间的线性回归项则是目标函数中常见的部分.不失一般性, 式(1)给出了一类常见的有监督线性哈希算法的目标函数:
| $ \left\{ \begin{array}{l} \mathop {\min }\limits_{{\bf{B}}, {\bf{P}}, {\bf{W}}} {\kern 1pt} ||{\bf{B}} - {{\bf{P}}^T}{\bf{X}}||_F^2 + v{\kern 1pt} ||{\bf{Y}} - {\bf{BW}}||_F^2 + \lambda ||{\bf{W}}||_F^2\\ {\rm{s}}{\rm{.t}}.{\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\bf{B}} \in {\{ - 1, 1\} ^{n \times l}} \end{array} \right. $ | (1) |
其中, ||·||F代表矩阵的F范数.第1项代表哈希矩阵和原始特征矩阵的线性关系, 第2项代表标签矩阵和哈希矩阵的线性关系.该优化问题可以通过交替优化算法来解决.现有线性哈希模型大多是以上目标函数的变形或改进, 同时再设计不同的约束项和正则项, 构造不同的哈希学习算法.与现有算法不同, 本文方法并不设计新的目标函数, 也不增加任何约束项和正则项.对于给定的已有哈希学习算法, 本文提出一个基于相似度驱动的模型参数再优化框架, 通过该框架可以在不增加任何目标函数项和约束项的情况下, 学习得到更优的目标函数参数, 进一步提升现有哈希算法的性能.
哈希学习的一个重要特性就是相似性保持, 即在原始特征空间相似的样本, 其哈希码在汉明空间也要相似(汉明距离较小).越能够保持此相似性的哈希码, 其检索性能越好.因此, 如果在训练过程中能够获得训练集样本较优的哈希码, 则更能够学习到哈希模型较优的参数.基于此动机, 本文提出了一个基于相似度驱动的线性哈希模型参数再优化的框架.该框架的主要思路为:给定一个线性哈希模型, 首先在训练集上运行该模型多次, 得到训练集的多个哈希矩阵, 然后基于相似度保持水平来选取较优的哈希比特作为训练集样本的哈希矩阵, 利用此哈希矩阵作为哈希模型的输入, 再次优化给定哈希模型, 获得更优的哈希模型参数, 用于生成样本外哈希码.
本文的主要贡献总结如下.
(1) 提出一个哈希学习模型参数再优化框架.该框架可以应用到现有基于线性模型的哈希学习算法中, 并有效提升相应哈希学习算法的检索性能;
(2) 提出一种训练集样本优化哈希码的选择方案, 并给出理论分析.该方案的主要目的是为参数再优化提供基础, 通过该方案, 在哈希模型再优化的过程中, 可以把哈希矩阵作为已知项, 减少待优化参数, 提高效率;
(3) 在常用的公开数据库上, 把本文提出的框架应用到不同的哈希学习算法中, 实验结果表明, 本文方法对各类型哈希算法的性能都可以实现有效提升, 在部分情况下可以获得20%以上的性能提升.
本文第1节对基于相似度驱动的线性哈希模型参数再优化方法进行详细介绍, 包括基于相似度驱动的优化哈希码选择策略和哈希模型再优化方案.第2节是实验结果分析, 本节把本文的方法在公开数据库上进行实验, 并对实验结果进行分析.第3节总结全文, 并对未来的研究内容进行说明.
1 基于相似度驱动的线性哈希模型参数再优化方法本文方法的框架图如所示, 分为两个过程.
(1) 基于相似度驱动的较优哈希码选择;
(2) 线性哈希模型参数再优化.
本文方法的相关符号定义和说明见.以下各小节将对该方法进行详细介绍.
1.1 基于相似度驱动的较优哈希码选择
哈希码的选择是指如何在多个哈希码矩阵中选择较优的比特构造训练集样本的哈希码矩阵, 本文提出了一个基于相似度驱动的哈希码选择策略.如上文所述, 相似度保持是哈希学习算法的核心目标, 所谓相似度保持, 即在特征空间相似的样本, 其对应的哈希码在汉明空间中的距离要尽可能地小.为了利用相似度保持来选择较优哈希码, 本文首先定义相似度保持水平, 然后给出一个哈希码乱序相似度保持定理, 最后基于相似度保持水平和相似度保持定理介绍一个较优的哈希码选择方案.
对于给定的样本哈希矩阵B∈{–1, 1}L×N, 该矩阵第i行记为bi, 而bi也是所有样本的第i比特组成的向量.设矩阵S={sij}为样本的相似度矩阵, 对于有监督哈希学习算法, 相似度矩阵可以利用样本标签计算, 若第i个样本和第j个样本至少有一个相同标签, 则sij=1, 否则, sij=–1.对于无监督哈希学习算法, 相似度矩阵可以通过聚类算法计算, 若第i个样本和第j个属于同一个类, 则sij=1, 否则, sij=–1.
样本的第i位比特的相似度保持水平sp定义如下:
| $ sp = {\kern 1pt} ||{\bf{b}}_i^T{{\bf{b}}_i} - {\bf{S}}|{|^2} $ | (2) |
相似度保持水平sp反映了样本哈希码第i位的相似度保持的程度, 该位的sp值越小, 说明在此位上相似度保持得越好.
为了介绍较优哈希码选择策略, 本文给出如下哈希矩阵的乱序相似度保持定理.
定理1.在通过线性哈希模型得到的样本哈希矩阵中, 矩阵行的顺序对样本语义相似保持没有影响.
证明:本文从两个角度对该定理进行证明.首先, 从相似度保持的角度, 设样本哈希矩阵为B, 对哈希矩阵行进行乱序后得到的矩阵为B, 可以推导出, BTB=BTB, 因此, 经过行乱序后, 样本哈希矩阵的相似度不变.
其次, 从哈希表示的信息损失的角度进行证明.本文用一个简单的线性哈希模型来证明经过行乱序, 样本的哈希表示和原始特征之间的损失不变.不失一般性, 设乱序前的线性哈希模型的优化问题表示如下:
| $ \mathop {\min }\limits_{\bf{P}} {\kern 1pt} ||{\bf{B}} - {{\bf{P}}^T}{\bf{X}}||_F^2 + \lambda ||{\bf{P}}||_F^2{\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\rm{s}}{\rm{.t}}.{\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\bf{B}} \in {\{ - 1, 1\} ^{L \times N}} $ | (3) |
为优化映射矩阵P, 目标函数对矩阵P求导数, 并让导数等于0, 则得到矩阵P的优化解:
| $ {\bf{P}} = {({\bf{X}}{{\bf{X}}^T} + \lambda {\bf{I}})^{ - 1}}{\bf{X}}{{\bf{B}}^T} $ | (4) |
乱序后的优化问题, 只需要用乱序后的矩阵B代替优化问题(3)中的矩阵B, 同样的求解过程, 可以得到乱序后哈希矩阵和原始特征的映射矩阵P :
| $ {\bf{\bar P}} = {({\bf{X}}{{\bf{X}}^T} + \lambda {\bf{I}})^{ - 1}}{\bf{X}}{{\bf{\bar B}}^T} $ | (5) |
设Q=(XXT+λI)–1X, 则:
| $ ||{\bf{B}} - {{\bf{P}}^T}{\bf{X}}{\rm{|}}{{\rm{|}}^2}{\rm{ = }}||{\bf{B}} - {\bf{B}}{{\bf{Q}}^T}{\bf{X}}{\rm{|}}{{\rm{|}}^2} = ||{\bf{B}}({\bf{I}} - {{\bf{Q}}^T}{\bf{X}}){\rm{|}}{{\rm{|}}^2} = ||{\bf{BM}}|{|^2} = Tr({{\bf{M}}^T}{{\bf{B}}^T}{\bf{BM}}) = Tr({{\bf{B}}^T}{\bf{BM}}{{\bf{M}}^T}) $ | (6) |
其中, Tr()表示迹运算, M=I–QTX.
又因为BTB=BTB, 则可以得到
特征之间的信息损失不变.
综上可以得到, 哈希矩阵行的顺序对样本语义保持没有影响. □
对于一种哈希学习算法来说, “好”的样本特征有利于模型参数的优化和学习.如果把样本的哈希码作为样本特征的一种表示形式, 那么哈希码的每一位比特就是特征表示的每一个维度, 其对样本的表示越“好”, 则对模型参数的训练和优化就越有利, 而对哈希码每一位比特来说, “好”指的是能够充分地保留样本原始空间的相似性.因此, 为了学习得到更好的模型参数, 需要得到训练集样本较“好”的哈希码表示.基于以上定义和定理, 本文提出一个较优哈希码选择方案, 具体过程如下.
对于给定的一种线性哈希算法, 首先在训练集上运行T次, 得到训练集的T个哈希矩阵
1.2 模型参数再优化
利用以上选择策略得到的训练集哈希矩阵, 对原始哈希模型进行重新优化, 不失一般性, 本文用下式表示一个常见的线性哈希模型, 对无监督或有监督的哈希学习算法, 则再需要加上相关的项和约束即可.
| $ \mathop {\min }\limits_{\bf{P}} {\kern 1pt} ||{\bf{B}} - {{\bf{P}}^T}{\bf{X}}||_F^2 + \lambda ||{\bf{P}}||_F^2{\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\rm{s}}{\rm{.t}}{\rm{.}}{\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\bf{B}} \in {\{ - 1, 1\} ^{L \times N}} $ | (7) |
在此优化问题中, 哈希矩阵B由第1.1节得到的最优哈希码矩阵代替, 因此, 该优化问题只需要优化映射矩阵P即可.为得到优化映射矩阵, 目标函数对矩阵P求导数, 并令导数等于0, 则可以得到P的优化解:
| $ {\bf{P}} = {({\bf{X}}{{\bf{X}}^T} + \lambda {\bf{I}})^{ - 1}}{\bf{X}}{{\bf{B}}^T} $ | (8) |
综上所述, 本文提出的基于相似度驱动的线性哈希模型参数再优化框架如算法1所示.
算法1.基于相似度驱动的线性哈希模型参数再优化方法.
输入:训练集特征矩阵X, 期望哈希码长度L; 给定的哈希算法HA; 哈希模型运行次数T;
1.初始化哈希码和特征映射矩阵P
2.运行给定哈希算法T次, 得到T个样本哈希矩阵
3.利用哈希码选择策略得到训练集样本的较优哈希矩阵
4.利用式(7)和式(8)重新优化模型参数
输出:模型参数P
1.3 复杂度分析假设原哈希模型算法复杂度为C, 训练集样本数目为N, 样本哈希码长度为L, 则运行T次得到T个哈希矩阵的复杂度近似为TC.相似度保持水平值sp计算的复杂度为O(NTL), 相似度保持水平值sp排序的复杂度为O(NL1gL), 模型再优化过程的计算复杂度为O(NdL+Nd2), 其中, d为样本特征维度.因此, 本文方法的总复杂度为O(NdL+Nd2+TL1gL+NTL)+TC.而通常情况下哈希码长度L和原始模型运行次数T远小于样本特征维度d和样本数目N, 因此本文方法总复杂度可以近似为O(Nd2)+TC.进一步地, 线性哈希模型再优化映射矩阵P的复杂度往往远小于原始哈希算法复杂度, 因此, 近似来说, 本文提出的方案的算法复杂度是原始哈希模型复杂度的T倍.直观来看, T值越大, 本文方法再优化参数的性能就越好, 检索精度就越高, 因为较大的T值可以提供较多哈希矩阵以供选择.但当T值增大时, 本文方法的时间和空间复杂度也会变大.本文在实验部分针对T的不同取值做了相关实验发现, 当T较大时, 检索精度的提升很缓慢, 一个可能的原因就是, 当原始哈希模型运行的次数较大时, 得到的哈希矩阵的变化就很小了, 哈希矩阵之间的sp值变化也就很小.因此, 为了降低时间和空间复杂度, 在几乎不损失精度的前提下, 可以使用较小的T值(本文实验中T=3).总体来说, 本文提出的方法与原始模型相比, 复杂度增加较少, 但是哈希算法检索性能的提升却很大, 下面第2节中的实验结果也说明了这一点.
2 实验 2.1 实验设置本文方法主要在3个公开的图像数据库CIFAR-10[]、MS-COCO[]和NUS-WIDE[]进行了实验, 3个数据库的相关信息介绍如下.
CIFAR-10:该数据库为单标签数据库, 包含60 000幅图像, 其中有50 000个训练和10 000个测试图像.图像由10个类组成, 每个类有6 000个图像.本文实验随机地从每个类中选取5 000个图像作为训练集, 1 000幅图像作为测试集.
MS-COCO:该数据库为多标签数据库, 包含82 783幅图像, 共91个类.根据现有哈希算法的通用方式, 在本文实验中, 如果两幅图片中有至少一个相同的标签, 就认为这两幅图片是相似的.实验中, 本文方法随机地选择10 000幅图像作为训练集, 5 000图像作为测试集.
NUS-WIDE:该数据库包含了269 648幅图像, 对应于1 000个类别标签, 本文实验中选取21个包含图片较多的类别, 共约195 834幅图片.同样地, 与MS-COCO数据库的处理方式类似, 在本文实验中, 如果两幅图片有至少一个相同的标签, 就认为这两幅图片是相似的.同时, 本文实验在每类中随机选取10 500幅图像作为训练集, 2 100幅图像作为测试集.
为证明本文方法的有效性, 将本文方法分别应用到不同的哈希算法:(1)快速监督离散哈希(FSDH)[]; (2)快速扩展哈希(FSSH)[]; (3)基于列采样的离散监督哈希(COSDISH)[]; (4)扩展离散哈希(SSDH)[].实验中, 对给定哈希模型运行3次(即T=3).
本文采用平均精度均值(mean average precision, 简称mAP)作为性能指标来展示本文方法在不同哈希算法上应用的性能, 这也是多媒体检索中常用的评价准则.mAP是指检索到的全部样本的精度均值(AP).
| $ mAP = \frac{1}{Q}\sum\limits_{r = 1}^Q {AP(i)} $ | (9) |
其中, Q是查询图像的数量, AP(i)表示第i个样本的精度均值.AP定义为
| $ AP = \frac{1}{R}\sum\limits_{r = 1}^G {precision(r)\sigma (r)} $ | (10) |
其中, R表示检索样本G中相关实例的数量.如果第r个实例与查询相关, 则σ(r)=1;否则为0.precision(r)表示第r个实例的检索精度, 定义如下:
| $ precision = \frac{{Num(True{\kern 1pt} {\kern 1pt} {\kern 1pt} {\rm{Positive}})}}{{Num(True{\kern 1pt} {\kern 1pt} {\kern 1pt} {\rm{Positive) + }}Num({\rm{False}}{\kern 1pt} {\kern 1pt} {\rm{Positive)}}}} $ | (11) |
其中, Num()表示相关类别的数目.
2.2 实验结果与分析~展示了在3个公开数据库上本文方法应用在不同的哈希算法上的mAP的值.其中, 样本哈希码长度分别取24、48和64.“方法名称-i”表示相关方法第i次运行后的结果, “方法名称-s”表示把本文方法应用到相关哈希算法后的结果.从所示结果可以看出, 本文提出的再优化方法对现有哈希算法性能的提升有显著效果.特别地, 在COSDISH算法上的性能更是提高了20%以上, 在其他算法上对原算法性能的提升也在3%~8%左右.
不可否认, 在NUS-WIDE数据库上, 某些情况下, 本文方法应用在FSSH和SSDH两种算法上并没有得到性能的提升, 其中一个可能的原因是, 这两种算法在原始模型的构造中对哈希码相似度的特性已经进行了充分利用, 因此其运行得到的哈希码的相似度保持水平已经较高, 所以本文方法在应用到此类算法时, 在哈希码的优化选择上并没有体现出显著优势.但本文方法应用到这两种算法时仍然取得了与原算法相似的性能.
~分别展示了在3个数据库上本文方法应用到不同哈希算法后的检索精度(precision)和哈希码长度的关系图, 其中, 哈希码长度从12比特到128比特之间变化.在各图中, “方法名称_i”表示相关方法第i次运行后的结果, “方法名称-s”表示把本文方法应用到相关方法后的结果, “Precision@5000”表示仅考虑检索到的最相关的前5 000个结果的精度.由~同样可以看出, 本文方法对哈希算法的性能提升具有显著的作用.
和展示了本文方法应用到不同算法后的精度性能与原始算法运行次数以及哈希码长度的关系图, 由图可以看出, 本文方法应用后的精度性能随着运行次数的增加, 性能的变化很小, 这说明, 在本文方法中, 原始模型运行次数T取一个较小的值即可.同时也说明, 本文方法在不同哈希算法应用后取得了较为显著的检索性能上的提升, 但时间和空间复杂度上仅有少许增加.
3 结论
本文提出了一种基于相似度驱动的线性哈希模型参数再优化方法, 该方法对于给定的线性哈希模型, 通过两步策略, 获得原模型的更优参数, 从而提升了原始算法的性能.在这两步策略中, 第1步通过对原始模型的多次运行获得多个训练集哈希矩阵, 然后根据本文提出的相似度保持水平度量和融合选择策略, 优选得到训练集样本较优的哈希矩阵; 在第2步中, 将得到的较优哈希矩阵作为引导, 再次优化模型参数, 获得原模型更优的参数表示.实验结果表明, 本文提出的方法对原始哈希模型的检索性能有显著提升.
线性模型因其简洁和高效率在哈希模型领域取得广泛应用, 因此, 本文针对线性哈希模型的再优化问题进行了研究, 未来的工作将在非线性哈希模型上进一步加以拓展和研究.
Facebook刷粉
Telegram粉丝购买
Tiktok涨粉平台
