CN105893477A

CN105893477A - Distance preserving Hash method based on double-circuit neural network

Info

Publication number: CN105893477A
Application number: CN201610186444.8A
Authority: CN
Inventors: 周文罡; 王敏; 李厚强; 田奇
Original assignee: University of Science and Technology of China USTC
Current assignee: University of Science and Technology of China USTC
Priority date: 2016-03-25
Filing date: 2016-03-25
Publication date: 2016-08-24

Abstract

The invention discloses a distance-preserving hash method based on a two-way neural network, which includes: using an unsupervised hash method to generate a binary code for each training data point, and constructing two training data points and their corresponding binary codes A data pair; the data pair is fed into a two-way neural network whose training goal is to preserve the linear distance transformation relationship of the data pair in different spaces and maintain the fidelity of the original unsupervised hashing method; By alternately updating the parameters of the neural network and the parameters of the linear distance transformation until convergence or reaching the set number of iterations, any path of the two-way neural network is taken to form a new hash function learned. By adopting the method disclosed by the invention, the retrieval performance of the unsupervised hash method can be significantly improved.

Description

A distance-preserving hashing method based on two-way neural network

技术领域technical field

本发明涉及多媒体技术领域，尤其涉及一种基于双路神经网络的保距哈希方法。The invention relates to the field of multimedia technology, in particular to a distance-preserving hash method based on a two-way neural network.

背景技术Background technique

近似最近邻查找技术是计算机视觉和多媒体应用中的一个基本问题。给定一个查询样本，近似最近邻查找技术可以以很高的概率从一个大的数据集中查找到查询样本的最近邻，并且时间复杂度为线性甚至是常数时间复杂度。近似最近邻查找技术中主要有两类方法，分别是基于树的方法和哈希方法。基于树的方法在高维空间中存在维数灾难问题，而哈希方法由于在高维空间中也表现出良好性能，变得越来越受欢迎。Approximate nearest neighbor finding technique is a fundamental problem in computer vision and multimedia applications. Given a query sample, the approximate nearest neighbor search technique can find the nearest neighbor of the query sample from a large data set with a high probability, and the time complexity is linear or even constant time complexity. There are mainly two types of methods in the approximate nearest neighbor search technology, which are tree-based methods and hash methods. Tree-based methods suffer from the curse of dimensionality in high-dimensional spaces, while hashing methods are becoming more and more popular due to their good performance in high-dimensional spaces as well.

根据是否使用训练数据，现有哈希方法可以分为两类，分别是数据依赖方法和数据独立方法。数据独立方法不使用训练数据，通常对数据应用随机映射来生成二进制码，而且有理论证明：使用数据独立性哈希方法，在汉明空间(Hamming space)中，原始空间的局部邻居结构仍然被保留。这种数据独立性方法的缺点是在大规模应用中，为了获得可以接受的性能，码长要很长，而码长变长会使得召回率(recall)变低。为了提升召回率，这类方法通常会使用多个哈希表，但这又会引发新的问题——内存占用大和计算复杂度高。According to whether training data is used or not, existing hashing methods can be divided into two categories, namely data-dependent methods and data-independent methods. The data-independent method does not use training data, and usually applies random mapping to the data to generate binary codes, and it is theoretically proved that using the data-independent hashing method, in the Hamming space, the local neighbor structure of the original space is still reserve. The disadvantage of this data independence method is that in large-scale applications, in order to obtain acceptable performance, the code length must be very long, and the longer the code length will make the recall rate (recall) lower. In order to improve the recall rate, such methods usually use multiple hash tables, but this will cause new problems-large memory usage and high computational complexity.

因此，数据依赖哈希方法开始被研究，通过使用训练数据集来学习得到更加紧致的二进制码。通过将高维数据映射为紧致的二进制码，近似最近邻搜索可以在线性时间复杂度内完成。根据训练数据是否含有标签或分类信息，数据依赖方法又可以进一步被分为三类，分别是有监督方法，半监督方法和无监督方法。Therefore, data-dependent hashing methods have been studied to learn more compact binary codes by using training data sets. By mapping high-dimensional data into compact binary codes, approximate nearest neighbor search can be done in linear time complexity. According to whether the training data contains label or classification information, data-dependent methods can be further divided into three categories, namely supervised methods, semi-supervised methods and unsupervised methods.

有监督哈希方法使用带有标签信息的训练数据进行训练，而半监督方法使用部分带有标签信息的训练数据进行训练。这两类方法通常可以将哈希函数的学习过程形式化为分类问题或最优化问题。数据对或三元组的信息通常被考虑进目标函数去指导哈希函数的学习。尽管在大多数文献中，有监督和半监督哈希方法相比于无监督方法获得了更高的性能，但在很多实际应用中，分类信息或标签数据是很难获得的。这导致无监督哈希方法仍然被广泛研究使用。Supervised hashing methods use training data with labeled information for training, while semi-supervised methods use part of the training data with labeled information for training. These two types of methods can usually formalize the learning process of the hash function as a classification problem or an optimization problem. The information of data pairs or triples is usually considered into the objective function to guide the learning of the hash function. Although supervised and semi-supervised hashing methods achieve higher performance than unsupervised methods in most of the literature, in many practical applications, classification information or labeled data is difficult to obtain. This leads to the fact that unsupervised hashing methods are still widely researched and used.

无监督哈希方法使用不含任何标签信息的分类数据。这类方法通常利用数据分布的信息或好的二进制码的内在属性(例如平衡性和独立性)来保留数据邻居结构，最小量化误差。这些约束本质上属于单个点的约束，并没有直接反映哈希的保距目标。鉴于此，有必要研究一种普适性的方法提高无监督哈希方法的性能。Unsupervised hashing methods use categorical data without any label information. Such methods usually exploit the information of the data distribution or the intrinsic properties of good binary codes (such as balance and independence) to preserve the data neighbor structure and minimize the quantization error. These constraints are essentially single-point constraints and do not directly reflect the distance-keeping objective of hashing. In view of this, it is necessary to study a general method to improve the performance of unsupervised hashing methods.

发明内容Contents of the invention

本发明的目的是提供一种基于双路神经网络的保距哈希方法，可以显著提高无监督哈希方法的检索性能。The purpose of the present invention is to provide a distance-preserving hash method based on a two-way neural network, which can significantly improve the retrieval performance of the unsupervised hash method.

本发明的目的是通过以下技术方案实现的：The purpose of the present invention is achieved through the following technical solutions:

一种基于双路神经网络的保距哈希方法，包括：A distance-preserving hashing method based on a two-way neural network, comprising:

利用无监督哈希方法对每个训练数据点产生二进制码，并将两两训练数据点及其对应的二进制码构成一个数据对；Use the unsupervised hash method to generate a binary code for each training data point, and form a data pair between two training data points and their corresponding binary codes;

将数据对输入至双路神经网络中，该双路神经网络的训练目标是保持数据对在不同空间内的线性距离变换关系并保持原始的无监督哈希方法的保真度；Input data pairs into a two-way neural network trained with the goal of preserving the linear distance transformation relationship of data pairs in different spaces and maintaining the fidelity of the original unsupervised hashing method;

通过交替地更新神经网络参数和线性距离变换参数，直到收敛或达到设定的迭代次数后，取双路神经网络的任意一路，即构成了学习得到的新的哈希函数。By alternately updating the parameters of the neural network and the parameters of the linear distance transformation until convergence or reaching the set number of iterations, any path of the two-way neural network is taken to form a new hash function learned.

进一步的，所述保持数据对在不同空间内的线性距离变换关系的目标函数表达式为：Further, the expression of the objective function for maintaining the linear distance transformation relationship of data pairs in different spaces is:

$Φ Φ = = \frac{11}{22 {N N}_{p p} \cdot &Center Dot; N N} {|| || H h - - a a E E. - - b b || ||}_{F f}^{22};;$

其中，N为训练集中训练数据点的数量，N_p为数据对的数量；a和b是线性距离变换的参数；E为数据对欧氏距离矩阵，H为数据对二进制码的汉明距离矩阵，E与 Among them, N is the number of training data points in the training set, N _p is the number of data pairs; a and b are the parameters of linear distance transformation; E is the data pair Euclidean distance matrix, H is the Hamming distance matrix of data pair binary code , E and

矩阵E中的元素E(i,j)表示训练数据点x_i与x_j的欧氏距离；矩阵H中的元素H(i,j)表示练数据点x_i与x_j对应的二进制码b_i与b_j的汉明距离；假设每一二进制码为L比特，则二进制码b_i与b_j的汉明距离表示为：The element E(i, j) in the matrix E represents the Euclidean distance between the training data point x _i and x _j ; the element H(i, j) in the matrix H represents the binary code b corresponding to the training data point x _i and x _j The Hamming distance between _i and b _j ; assuming that each binary code is L bits, the Hamming distance between binary code b _i and b _j is expressed as:

$H h ((i i,, j j)) = = L L - - {b b}_{i i}^{T T} {b b}_{j j} - - {((11_{L L \times \times 11} - - {b b}_{i i}))}^{T T} ((11_{L L \times \times 11} - - {b b}_{j j})) . .$

进一步的，所述保持原始的无监督哈希方法的保真度的目标函数表达式为：Further, the objective function expression for maintaining the fidelity of the original unsupervised hashing method is:

$Ψ Ψ = = \frac{11}{22 N N} {|| || B B - - U u || ||}_{22}^{22}$

其中，B与B与U每一列都是一个训练数据点的一个二进制码；U的每一列由无监督哈希方法生成，B的每一列等于一路神经网络的输出再经二值化处理的结果。Among them, B and Each column of B and U is a binary code of a training data point; each column of U is generated by an unsupervised hash method, and each column of B is equal to the output of a neural network and then binarized.

进一步的，所述通过交替地更新神经网络参数和线性距离变换参数，直到收敛或达到设定的迭代次数包括：Further, the step of updating neural network parameters and linear distance transformation parameters alternately until convergence or reaching a set number of iterations includes:

将两个目标函数合并，则有：Combining the two objective functions, we have:

$Φ Φ + + λ λ Ψ Ψ + + β β {|| || W W || ||}^{22} = = = = \frac{11}{22 {N N}_{p p} \cdot \cdot N N} {|| || H h - - a a E E. - - b b || ||}_{F f}^{22} + + \frac{λ λ}{22 N N} {|| || B B - - U u || ||}_{22}^{22} + + β β {|| || W W || ||}^{22};;$

s.t.B∈{0,1}^N×L；stB∈{0,1} ^N×L ;

其中，λ为用来控制目标函数中前两部分重要性比例的参数，上述第三项的正则化约束条件用来降低神经网络参数的幅度，β是正则化项系数，W为神经网络参数；Among them, λ is a parameter used to control the importance ratio of the first two parts in the objective function, the regularization constraint of the third item above is used to reduce the magnitude of the neural network parameters, β is the coefficient of the regularization term, and W is the neural network parameter;

通过最小化上述目标函数来获得最优的参数W、a和b，并去掉二进制约束，使用神经网络的输出代替上述目标函数中的B，则最终的目标函数为：The optimal parameters W, a, and b are obtained by minimizing the above objective function, and the binary constraints are removed, and the output of the neural network is used Instead of B in the above objective function, the final objective function is:

${min min}_{W W,, a a,, b b} \frac{11}{22 {N N}_{ρ ρ} \cdot &Center Dot; N N} {|| || \overset{~ ~}{H h} - - a a E E. - - b b || ||}_{F f}^{22} + + \frac{λ λ}{22 N N} {|| || \overset{~ ~}{B B} - - U u || ||}_{22}^{22} + + β β {|| || W W || ||}^{22}$

$s the s . . t t . . \overset{~ ~}{B B} &Element; &Element; {{00,, 11}}^{N N \times \times L L}$

上式中，矩阵中的元素与为b_i与b_j去掉二进制约束的结果；In the above formula, the matrix elements in and The result of removing binary constraints for b _i and b _j ;

交替式优化的方式进行求解最终的目标函数：Alternative optimization is used to solve the final objective function:

固定参数W，更新a和b，则目标函数的优化变为：The parameter W is fixed, and a and b are updated, then the optimization of the objective function becomes:

${min min}_{a a,, b b} \frac{11}{22 {N N}_{p p} \cdot &Center Dot; N N} {|| || \overset{~ ~}{H h} - - a a E E. - - b b || ||}_{F f}^{22};;$

上述优化后的目标函数能够由最大似然方法求解；The above optimized objective function can be solved by the maximum likelihood method;

固定参数a和b，更新W，则目标函数的优化变为：The parameters a and b are fixed, and W is updated, then the optimization of the objective function becomes:

${min min}_{W W} L L ((W W)) = = \frac{11}{22 {N N}_{p p} \cdot &Center Dot; N N} {|| || \overset{~ ~}{H h} - - a a E E. - - b b || ||}_{F f}^{22} + + \frac{λ λ}{22 N N} {|| || \overset{~ ~}{B B} - - U u || ||}_{22}^{22} + + + + β β {|| || W W || ||}^{22};;$

将上述优化后的目标函数展成向量形式：Expand the above optimized objective function into vector form:

$L L ((W W)) = = \frac{11}{22 {N N}_{p p} \cdot &Center Dot; N N} \underset{i i}{Σ Σ} \underset{j j}{Σ Σ} {(({\overset{~ ~}{h h}}_{i i,, j j} - - {ae ae}_{i i,, j j} - - b b))}^{22} + + \frac{λ λ}{22 N N} \underset{k k}{Σ Σ} {|| || {\overset{~ ~}{b b}}_{k k} - - {u u}_{k k} || ||}^{22} + + β β {|| || W W || ||}^{22}$

上式中，根据求导的链式法则，优化后的目标函数的梯度表示为：In the above formula, According to the chain rule of derivation, the gradient of the optimized objective function is expressed as:

$\begin{matrix} \frac{\partial \partial L L ((W W))}{\partial \partial W W} = = {Σ Σ}_{i i = = 11}^{N N} \frac{\partial \partial L L ((W W))}{\partial \partial {\overset{~ ~}{b b}}_{i i}} \cdot &Center Dot; \frac{\partial \partial {\overset{~ ~}{b b}}_{i i}}{\partial \partial W W} \\ = = \frac{11}{{N N}_{p p} \cdot &Center Dot; N N} \underset{i i}{Σ Σ} \underset{j j}{Σ Σ} (({\overset{~ ~}{h h}}_{i i,, j j} - - {ae ae}_{i i,, j j} - - b b)) ((\frac{\partial \partial {\overset{~ ~}{h h}}_{i i,, j j}}{\partial \partial {\overset{~ ~}{b b}}_{i i}} \cdot &Center Dot; \frac{\partial \partial {\overset{~ ~}{b b}}_{i i}}{\partial \partial W W} + + \frac{\partial \partial {\overset{~ ~}{h h}}_{i i,, j j}}{\partial \partial {\overset{~ ~}{b b}}_{j j}} \cdot \cdot \frac{\partial \partial {\overset{~ ~}{b b}}_{j j}}{\partial \partial W W})) + + \frac{λ λ}{N N} \underset{k k}{Σ Σ} (({\overset{~ ~}{b b}}_{k k} - - {u u}_{k k})) \frac{\partial \partial {\overset{~ ~}{b b}}_{k k}}{\partial \partial W W} + + 22 β β W W \end{matrix};;$

其中，与是目标函数梯度，通过后向传播算法更新神经网络参数矩阵W；in, and is the gradient of the objective function, and the neural network parameter matrix W is updated through the backpropagation algorithm;

重复上述交替式优化过程，直到收敛或达到设定的迭代次数。Repeat the above alternating optimization process until convergence or reach the set number of iterations.

由上述本发明提供的技术方案可以看出，使用双路神经网络去保留线性距离变换关系并同时保留原始无监督哈希方法的哈希映射关系；同时，对于双路神经网络通过交替优化的方式学习得到哈希函数；该方案可以适用于大多数基于点约束的无监督哈希方法，并可以显著提高它们的检索性能。It can be seen from the above-mentioned technical solution provided by the present invention that the two-way neural network is used to retain the linear distance transformation relationship and the hash mapping relationship of the original unsupervised hash method; at the same time, for the two-way neural network through alternate optimization A hash function is learned; this scheme can be applied to most point-constrained unsupervised hashing methods and can significantly improve their retrieval performance.

附图说明Description of drawings

为了更清楚地说明本发明实施例的技术方案，下面将对实施例描述中所需要使用的附图作简单地介绍，显而易见地，下面描述中的附图仅仅是本发明的一些实施例，对于本领域的普通技术人员来讲，在不付出创造性劳动的前提下，还可以根据这些附图获得其他附图。In order to more clearly illustrate the technical solutions of the embodiments of the present invention, the following will briefly introduce the accompanying drawings that need to be used in the description of the embodiments. Obviously, the accompanying drawings in the following description are only some embodiments of the present invention. For Those of ordinary skill in the art can also obtain other drawings based on these drawings on the premise of not paying creative efforts.

图1为本发明实施例提供的一种基于双路神经网络的保距哈希方法的流程图。FIG. 1 is a flow chart of a two-way neural network-based distance-preserving hash method provided by an embodiment of the present invention.

具体实施方式detailed description

下面结合本发明实施例中的附图，对本发明实施例中的技术方案进行清楚、完整地描述，显然，所描述的实施例仅仅是本发明一部分实施例，而不是全部的实施例。基于本发明的实施例，本领域普通技术人员在没有做出创造性劳动前提下所获得的所有其他实施例，都属于本发明的保护范围。The technical solutions in the embodiments of the present invention will be clearly and completely described below in conjunction with the accompanying drawings in the embodiments of the present invention. Obviously, the described embodiments are only some of the embodiments of the present invention, not all of them. Based on the embodiments of the present invention, all other embodiments obtained by persons of ordinary skill in the art without making creative efforts belong to the protection scope of the present invention.

图1为本发明实施例提供的一种基于双路神经网络的保距哈希方法的流程图。如图1所示，其主要包括如下步骤：FIG. 1 is a flow chart of a two-way neural network-based distance-preserving hash method provided by an embodiment of the present invention. As shown in Figure 1, it mainly includes the following steps:

步骤11、利用无监督哈希方法对每个训练数据点产生二进制码，并将两两训练数据点及其对应的二进制码构成一个数据对。Step 11: Generate a binary code for each training data point by using an unsupervised hashing method, and form a data pair between two training data points and their corresponding binary codes.

本领域技术人员可以理解，利用无监督哈希方法对每个训练数据点产生二进制码可以通过现有技术实现。Those skilled in the art can understand that using an unsupervised hash method to generate a binary code for each training data point can be realized through existing technologies.

步骤12、将数据对输入至双路神经网络中，该双路神经网络的训练目标是保持数据对在不同空间内的线性距离变换关系并保持原始的无监督哈希方法的保真度。Step 12. Input the data pair into the two-way neural network. The training goal of the two-way neural network is to maintain the linear distance transformation relationship of the data pair in different spaces and maintain the fidelity of the original unsupervised hashing method.

本发明实施例中，所述双路神经网络具有完全相同的结构、参数和权值矩阵，唯一的区别是输入不同的训练数据点。In the embodiment of the present invention, the two-way neural network has exactly the same structure, parameters and weight matrix, and the only difference is that different training data points are input.

本发明实施例中，在原始欧氏空间和汉明空间中保持线性的距离变换(也就是说，数据对在原始欧氏空间内的欧氏距离，与数据对对应的二进制码在汉明空间中的汉明距离之间应该保持线性变换关系)，并同时保持原始无监督哈希方法的保真度。下面这针对这两个目标进行详细说明。In the embodiment of the present invention, linear distance transformation is maintained in the original Euclidean space and Hamming space (that is to say, the Euclidean distance of the data pair in the original Euclidean space, and the binary code corresponding to the data pair in the Hamming space should maintain a linear transformation relationship between the Hamming distances in ), while maintaining the fidelity of the original unsupervised hashing method. The following is a detailed description of these two goals.

1、线性距离变换关系。1. Linear distance transformation relationship.

在不同特征空间内保持距离度量关系是二进制哈希方法的固有特点。现有一些哈希方法采用将数据对的汉明距离和欧氏距离映射到同一尺度下，例如，[0,1]，然后最小化这两个映射后距离的偏差的方法来实现保距。然而，发现这种约束由于太严格通常并没有取得很好的性能，而实际上只需要保持两个原始的欧氏距离和汉明距离之间的线性映射关系即可，这种约束通过实验证明可以显著地提高原始无监督哈希方法的性能。Preserving distance metric relationships in different feature spaces is an inherent feature of binary hashing methods. Some existing hashing methods use the method of mapping the Hamming distance and Euclidean distance of the data pair to the same scale, for example, [0,1], and then minimize the deviation of the two mapped distances to achieve distance preservation. However, it is found that this constraint usually does not achieve good performance because it is too strict. In fact, it is only necessary to maintain the linear mapping relationship between the two original Euclidean distances and Hamming distances. This constraint is proved by experiments. The performance of the original unsupervised hashing method can be significantly improved.

所述保持数据对在不同空间内的线性距离变换关系的目标函数表达式为：The expression of the objective function that maintains the linear distance transformation relationship of data pairs in different spaces is:

其中，N为训练集中训练数据点的数量，N_p为数据对的数量；a和b是线性距离变换的参数；||·||_F表示Frobenius范数，它是一种矩阵范数，等于对矩阵中每个元素求平方再求和；E为数据对欧氏距离矩阵，H为数据对二进制码的汉明距离矩阵，E与矩阵E中的元素E(i,j)表示训练数据点x_i与x_j的欧氏距离；矩阵H中的元素H(i,j)表示训练数据点x_i与x_j对应的二进制码b_i与b_j的汉明距离。Among them, N is the number of training data points in the training set, N _p is the number of data pairs; a and b are the parameters of linear distance transformation; ||·|| _F represents the Frobenius norm, which is a matrix norm, equal to Square each element in the matrix and then sum; E is the data-to-Euclidean distance matrix, H is the Hamming distance matrix from data to binary code, E and The element E(i, j) in the matrix E represents the Euclidean distance between the training data point x _i and x _j ; the element H(i, j) in the matrix H represents the binary code b corresponding to the training data point x _i and x _j The Hamming distance between _i and b _j .

上述目标函数与最小二乘方法的目标函数相似，不同点在于在我们的目标函数中，H矩阵是一个离散值矩阵，因为每两个L比特二进制码之间的汉明距离只可能取到个L+1值，分别是0，1，2，…,L。为了求解方便，本发明实施例中，汉明距离的计算与一般的计算方法(计算两个二进制码的异或码中‘1’的个数)不同，本发明实施例中H(i,j)的表达式为：The above objective function is similar to the objective function of the least squares method, the difference is that in our objective function, the H matrix is a discrete value matrix, because the Hamming distance between every two L-bit binary codes can only be taken as L+1 value, respectively 0, 1, 2, ..., L. For the convenience of solving, in the embodiment of the present invention, the calculation of the Hamming distance is different from the general calculation method (calculating the number of '1' in the XOR code of two binary codes), in the embodiment of the present invention, H(i, j ) is expressed as:

2、保持原始无监督方法的保真度。2. Maintain the fidelity of the original unsupervised method.

目前有很多传统的无监督哈希方法，仔细考虑了数据的分布特性和好的二进制码的固有属性。本发明实施例的方案针对于提升这些已经存在的无监督方法的性能。There are many traditional unsupervised hashing methods that carefully consider the distribution characteristics of the data and the inherent properties of good binary codes. The solutions of the embodiments of the present invention are aimed at improving the performance of these existing unsupervised methods.

所述保持原始的无监督哈希方法的保真度的目标函数表达式为：The objective function expression for maintaining the fidelity of the original unsupervised hashing method is:

$Ψ Ψ = = \frac{11}{22 N N} {|| || B B - - U u || ||}_{22}^{22}$

其中，B与B与U每一列都是一个训练数据点的一个二进制码；U的每一列由无监督哈希方法生成，B的每一列是一路神经网络的输出再经过二值化处理获得的二进制码。Among them, B and Each column of B and U is a binary code of a training data point; each column of U is generated by an unsupervised hash method, and each column of B is a binary code obtained by binarizing the output of a neural network.

步骤13、通过交替地更新神经网络参数和线性距离变换参数，直到收敛或达到设定的迭代次数后，取双路神经网络的任意一路，即构成了学习得到的新的哈希函数。Step 13. By alternately updating the neural network parameters and the linear distance transformation parameters until convergence or reaching the set number of iterations, any path of the two-way neural network is taken to form a new learned hash function.

在步骤12中获得两个目标函数后，可以将两个目标函数合并，则有：After obtaining the two objective functions in step 12, the two objective functions can be combined, then:

s.t.B∈{0,1}^N×L；stB∈{0,1} ^N×L ;

其中，λ为用来控制目标函数中前两部分重要性比例的参数，上述的第三项正则化约束条件用来降低神经网络参数的变化幅度，β是正则化项系数，W为神经网络参数；Among them, λ is a parameter used to control the importance ratio of the first two parts in the objective function, the above-mentioned third regularization constraint is used to reduce the variation range of the neural network parameters, β is the regularization term coefficient, and W is the neural network parameter ;

通过最小化上述目标函数来获得最优的参数W、a和b，由于二进制约束的存在，上面的融合后的目标函数不可直接求解。为了处理这个问题，直接去掉二进制约束，使用神经网络的输出代替上述目标函数中的B，则最终的目标函数为：The optimal parameters W, a, and b are obtained by minimizing the above objective function. Due to the existence of binary constraints, the above fused objective function cannot be directly solved. To deal with this problem, directly remove the binary constraint and use the output of the neural network Instead of B in the above objective function, the final objective function is:

${min min}_{W W,, a a,, b b} \frac{11}{22 {N N}_{ρ ρ} \cdot \cdot N N} {|| || \overset{~ ~}{H h} - - a a E E. - - b b || ||}_{F f}^{22} + + \frac{λ λ}{22 N N} {|| || \overset{~ ~}{B B} - - U u || ||}_{22}^{22} + + β β {|| || W W || ||}^{22}$

上式中，矩阵中的元素与表示神经网络输出，所需要的目标二进制码b_i与b_j为与进行二值化的结果；In the above formula, the matrix elements in and Represents the output of the neural network, the required target binary codes b _i and b _j are and The result of binarization;

然而上述目标函数仍然难以直接求解，本发明实施例中，采用交替式优化的方式进行求解最终的目标函数：However, the above objective function is still difficult to solve directly. In the embodiment of the present invention, an alternate optimization method is used to solve the final objective function:

1)固定参数W，更新a和b，则目标函数的优化变为：1) Fix the parameter W, update a and b, then the optimization of the objective function becomes:

将矩阵与E展成两个列向量时，上面这个目标退化为线性回归问题，可以由最大似然方法直接求解。the matrix When expanding with E into two column vectors, the above objective degenerates into a linear regression problem, which can be directly solved by the maximum likelihood method.

2)固定参数a和b，更新W，则目标函数的优化变为：2) The parameters a and b are fixed, and W is updated, then the optimization of the objective function becomes:

由于目标函数L(W)是连续的，所以可以通过神经网络的后向传播方法学习得到神经网络的参数矩阵W。相比于传统的神经网络的后向传播方法，本发明实施例中的双路神经网络的后向传播方法只进行部分的修改即可。详细来说，可以将上式中的目标函数展成向量形式：Since the objective function L(W) is continuous, the parameter matrix W of the neural network can be obtained by learning the backward propagation method of the neural network. Compared with the traditional neural network backpropagation method, the two-way neural network backpropagation method in the embodiment of the present invention only needs to be partially modified. In detail, the objective function in the above formula can be expanded into vector form:

$L L ((W W)) = = \frac{11}{22 {N N}_{p p} \cdot \cdot N N} \underset{i i}{Σ Σ} \underset{j j}{Σ Σ} {(({\overset{~ ~}{h h}}_{i i,, j j} - - {ae ae}_{i i,, j j} - - b b))}^{22} + + \frac{λ λ}{22 N N} \underset{k k}{Σ Σ} {|| || {\overset{~ ~}{b b}}_{k k} - - {u u}_{k k} || ||}^{22} + + β β {|| || W W || ||}^{22}$

上式中，e_i,j、u_k分别表示矩阵E、二进制码B、二进制码U变为向量形式的结果，根据求导的链式法则，优化后的目标函数的梯度表示为：In the above formula, e _i,j , u _k respectively represent the results of matrix E, binary code B, and binary code U being transformed into vector form. According to the chain rule of derivation, the gradient of the optimized objective function is expressed as:

$\begin{matrix} \frac{\partial \partial L L ((W W))}{\partial \partial W W} = = {Σ Σ}_{i i = = 11}^{N N} \frac{\partial \partial L L ((W W))}{\partial \partial {\overset{~ ~}{b b}}_{i i}} \cdot &Center Dot; \frac{\partial \partial {\overset{~ ~}{b b}}_{i i}}{\partial \partial W W} \\ = = \frac{11}{{N N}_{p p} \cdot &Center Dot; N N} \underset{i i}{Σ Σ} \underset{j j}{Σ Σ} (({\overset{~ ~}{h h}}_{i i,, j j} - - {ae ae}_{i i,, j j} - - b b)) ((\frac{\partial \partial {\overset{~ ~}{h h}}_{i i,, j j}}{\partial \partial {\overset{~ ~}{b b}}_{i i}} \cdot &Center Dot; \frac{\partial \partial {\overset{~ ~}{b b}}_{i i}}{\partial \partial W W} + + \frac{\partial \partial {\overset{~ ~}{h h}}_{i i,, j j}}{\partial \partial {\overset{~ ~}{b b}}_{j j}} \cdot &Center Dot; \frac{\partial \partial {\overset{~ ~}{b b}}_{j j}}{\partial \partial W W})) + + \frac{λ λ}{N N} \underset{k k}{Σ Σ} (({\overset{~ ~}{b b}}_{k k} - - {u u}_{k k})) \frac{\partial \partial {\overset{~ ~}{b b}}_{k k}}{\partial \partial W W} + + 22 β β W W \end{matrix};;$

其中，与是目标函数梯度，通过后向传播算法更新网络参数W；通过对比可以发现，本发明实施例中的双路神经网络的后向传播算法与一般后向传播算法的唯一区别就在于每个前面的系数不再相同。因此，使用本发明实施例中的后向传播算法更新双路神经网络。in, and is the gradient of the objective function, and the network parameter W is updated through the backpropagation algorithm; through comparison, it can be found that the only difference between the backpropagation algorithm of the two-way neural network in the embodiment of the present invention and the general backpropagation algorithm is that each The preceding coefficients are no longer the same. Therefore, the two-way neural network is updated using the backpropagation algorithm in the embodiment of the present invention.

重复上述交替式优化过程1)～2)，直到收敛或达到设定的迭代次数。由于双路神经网络的两路完全相同，对应的参数矩阵W已经求出，可以直接取其中任意一路网络作为哈希的映射函数，再将神经网络的输出进行二值化处理即可获得最终的二进制码。Repeat the above alternate optimization process 1) to 2) until convergence or reach the set number of iterations. Since the two paths of the two-way neural network are exactly the same, the corresponding parameter matrix W has been obtained, and any one of the networks can be directly taken as the mapping function of the hash, and then the output of the neural network can be binarized to obtain the final binary code.

本发明实施例上述方案中，使用双路神经网络去保留线性距离变换关系并同时保留原始无监督哈希方法的哈希映射关系；同时，对于双路神经网络通过交替优化的方式学习得到哈希函数；该方案可以适用于大多数基于点约束的无监督哈希方法，并可以显著提高它们的检索性能。In the above scheme of the embodiment of the present invention, the two-way neural network is used to retain the linear distance transformation relationship and the hash mapping relationship of the original unsupervised hash method; at the same time, the two-way neural network is learned through alternate optimization to obtain the hash function; this scheme can be applied to most unsupervised hashing methods based on point constraints and can significantly improve their retrieval performance.

通过以上的实施方式的描述，本领域的技术人员可以清楚地了解到上述实施例可以通过软件实现，也可以借助软件加必要的通用硬件平台的方式来实现。基于这样的理解，上述实施例的技术方案可以以软件产品的形式体现出来，该软件产品可以存储在一个非易失性存储介质(可以是CD-ROM，U盘，移动硬盘等)中，包括若干指令用以使得一台计算机设备(可以是个人计算机，服务器，或者网络设备等)执行本发明各个实施例所述的方法。Through the above description of the implementation manners, those skilled in the art can clearly understand that the above embodiments can be implemented by software, or by means of software plus a necessary general hardware platform. Based on this understanding, the technical solutions of the above-mentioned embodiments can be embodied in the form of software products, which can be stored in a non-volatile storage medium (which can be CD-ROM, U disk, mobile hard disk, etc.), including Several instructions are used to make a computer device (which may be a personal computer, a server, or a network device, etc.) execute the methods described in various embodiments of the present invention.

以上所述，仅为本发明较佳的具体实施方式，但本发明的保护范围并不局限于此，任何熟悉本技术领域的技术人员在本发明披露的技术范围内，可轻易想到的变化或替换，都应涵盖在本发明的保护范围之内。因此，本发明的保护范围应该以权利要求书的保护范围为准。The above is only a preferred embodiment of the present invention, but the scope of protection of the present invention is not limited thereto. Any person familiar with the technical field can easily conceive of changes or changes within the technical scope disclosed in the present invention. Replacement should be covered within the protection scope of the present invention. Therefore, the protection scope of the present invention should be determined by the protection scope of the claims.

Claims

1. A distance-preserving hash method based on a two-way neural network is characterized by comprising the following steps:

generating a binary code for each training data point by using an unsupervised Hash method, and forming a data pair by every two training data points and the binary codes corresponding to the training data points;

inputting the data pairs into a two-way neural network, wherein the training target of the two-way neural network is to keep the linear distance transformation relation of the data pairs in different spaces and keep the fidelity of the original unsupervised Hash method;

the neural network parameters and the linear distance transformation parameters are alternately updated until convergence or a set iteration number is reached, and any one of the two-way neural network is taken, so that a new hash function obtained by learning is formed.

2. The method of claim 1, wherein the objective function expression for maintaining the linear distance transform relationship of the data pairs in different spaces is:

Φ = \frac{1}{2 N_{p} \cdot N} | | H - a E - b | |_{F}^{2};

where N is the number of training data points in the training set, N_pIs the number of data pairs; a and b are parameters of the linear distance transform; e is a data-to-Euclidean distance matrix, H is a Hamming distance matrix of a data-to-binary code, E and

the element E (i, j) in the matrix E represents the training data point x_iAnd x_jThe Euclidean distance of; the element H (i, j) in the matrix H represents the training data point x_iAnd x_jCorresponding binary code b_iAnd b_jThe hamming distance of; assuming that each binary code is L bits, the binary code b_iAnd b_jThe hamming distance of (a) is expressed as:

H (i, j) = L - b_{i}^{T} b_{j} - {(1_{L \times 1} - b_{i})}^{T} (1_{L \times 1} - b_{j}) .

3. the method of claim 2, wherein the objective function expression that preserves the fidelity of the original unsupervised hashing method is:

Ψ = \frac{1}{2 N} | | B - U | |_{2}^{2}

wherein B andeach column of B and U is a binary code of a training data point; each column of U is generated by an unsupervised Hash method, and each column of B is equal to the result of output of one path of neural network and then binarization processing.

4. The method of claim 2 or 3, wherein the updating by alternately updating the neural network parameters and the linear distance transform parameters until convergence or a set number of iterations is reached comprises:

merging the two objective functions, then:

\begin{matrix} Φ + λ Ψ + β | | W | |^{2} = = \frac{1}{2 N_{p} \cdot N} | | H - a E - b | |_{F}^{2} + \frac{λ}{2 N} | | B - U | |_{2}^{2} + β | | W | |^{2}; \\ s . t . B &Element; {0, 1}^{N \times L}; \end{matrix}

wherein λ is a parameter for controlling the importance ratio of the first two parts in the objective function, the regularization constraint condition of the third term is used for reducing the amplitude of the neural network parameter, β is a regularization term coefficient, and W is the neural network parameter;

obtaining optimal parameters W, a and b by minimizing the objective function and removing binary constraints, using the output of the neural networkReplacing B in the objective function, the final objective function is:

\begin{matrix} \min_{W, a, b} \frac{1}{2 N_{p} \cdot N} | | \tilde{H} - a E - b | |_{F}^{2} + \frac{λ}{2 N} | | \tilde{B} - U | |_{2}^{2} + β | | W | |^{2} \\ s . t . \tilde{B} &Element; {0, 1}^{N \times L} \end{matrix}

in the above formula, matrixElement (1) of Andis b is_iAnd b_jRemoving the result of the binary constraint;

solving the final objective function in an alternating optimization mode:

with the parameters W fixed, updating a and b, the optimization of the objective function becomes:

\min_{a, b} \frac{1}{2 N_{p} \cdot N} | | \tilde{H} - a E - b | |_{F}^{2};

the optimized objective function can be solved by a maximum likelihood method;

with the parameters a and b fixed, and W updated, the optimization of the objective function becomes:

\min_{W} L (W) = \frac{1}{2 N_{p} \cdot N} | | \tilde{H} - a E - b | |_{F}^{2} + \frac{λ}{2 N} | | \tilde{B} - U | |_{2}^{2} + + β | | W | |^{2};

and spreading the optimized objective function into a vector form:

L (W) = \frac{1}{2 N_{p} \cdot N} \underset{i}{Σ} \underset{j}{Σ} {({\tilde{h}}_{i, j} - {ae}_{i, j} - b)}^{2} + \frac{λ}{2 N} \underset{k}{Σ} | | {\tilde{b}}_{k} - u_{k} | |^{2} + β | | W | |^{2}

in the above formula, the first and second carbon atoms are,according to the chain rule of derivation, the gradient of the optimized objective function is expressed as:

\begin{matrix} \frac{\partial L (W)}{\partial W} = Σ_{i = 1}^{N} \frac{\partial L (W)}{\partial {\tilde{b}}_{i}} \cdot \frac{\partial {\tilde{b}}_{i}}{\partial W} \\ = \frac{1}{N_{p} \cdot N} \underset{i}{Σ} \underset{j}{Σ} ({\tilde{h}}_{i, j} - {ae}_{i, j} - b) (\frac{\partial {\tilde{h}}_{i, j}}{\partial {\tilde{b}}_{i}} \cdot \frac{\partial {\tilde{b}}_{i}}{\partial W} + \frac{\partial {\tilde{h}}_{i, j}}{\partial {\tilde{b}}_{j}} \cdot \frac{\partial {\tilde{b}}_{j}}{\partial W}) + \frac{λ}{N} \underset{k}{Σ} ({\tilde{b}}_{k} - u_{k}) \frac{\partial {\tilde{b}}_{k}}{\partial W} + 2 β W \end{matrix};

wherein, andupdating a neural network parameter matrix W through a back propagation algorithm, wherein the target function gradient is the target function gradient;

and repeating the alternating optimization process until convergence or a set iteration number is reached.