Coordinate Discrete Optimization for Efficient Cross-View Image Retrieval

1 Introduction

Large-scale similarity search (or known as nearest neighbor search) is a critical task in computer science. Compact hashing techniques have gained much empirical success for fast similarity search in various fields. including computer vision [Torralba et al., 2008; Strecha et al., 2012; Liu et al., 2012; Lin et al., 2014], information retrieval [Chum et al., 2008], data mining [Eshghi and Rajaram, 2008], machine learning [Weiss et al., 2008; Salakhutdinov and Hinton, 2009; Norouzi and Fleet, 2011] and theoretic computer science [Indyk and Motwani, 1998; Charikar, 2002;

Datar et al., 2004]. As revealed by Johnson-Lindenstrauss lemma, under mild conditions, any n data points can be embedded into O(1◁✏2 ) log(n)-dimensional space with pairwise affinity distorted at most 1 ◦ ✏, which sheds light on developing compact coding scheme for similarity search. The hashing methods transform original data vectors into binary Hamming space, such that the Hamming distance between two data points approximates the original pairwise dissimilarity. With the hashing techniques, each data object can be represented using only a few binary bits. The storage cost can be thereby significantly reduced, and the nearest neighbor search can be also expedited using either Hamming ranking or the data structure of hash tables.

Conventional hashing schemes mostly take single-source data as the input. Nonetheless, in the era of big data, concurrently learning compact hash codes from heterogeneous data sources is of increasing importance. For example, each YouTube video is associated with rich information in multiple heterogenous views, including a variety of visual, spatiotemporal, or audio features extracted from the video content, the descriptive text from the caption and communitycontributed comments, and various video metadata (genre, time stamp, geo-tags, author etc.). One of the prominent benefits by concurrently learning hash codes from multi-view data is enabling cross-view retrieval. Specifically, one can search in some view by looking into relevant views (e.g., searching image database with textual queries, or vice versa). To this end, a plurality of cross-view hashing methods have been devised. Examples can be found in [Zhen and Yeung, 2012a; 2012b; Lin et al., 2015].

This paper focuses on image data and aims to elevate the performancce of hash code based cross-view image retrieval. Note that there exist two different paradigms in utilizing multi-source data for the hashing purpose: multi-view hashing and cross-view hashing. The former assumes all views are available for both the training and querying data. The latter adopts a more feasible setting, assuming only partial views are seen for the querying data. We exclude the former from the scope of this work. Our novel contribution lies in a novel cross-view hashing formulation and a corresponding optimization procedure which is characterized by the direct manipulation of discrete hash codes. Before diving into technical details we would emphasize two crucial traits of the proposed method.

First, most existing hashing methods from multi-view data still suffer from inadequate search accuracy, which can be partly imputed to the popular "relaxation + rounding" optimization strategy. To achieve high compactness, hash codes are mostly represented by binary bits. The discrete nature of hash codes makes learning the hash functions a complicated combinatorial optimization problem. Computationally, the relaxation + rounding tactic for attacking this issue is to first relax the binary variables to be continuous and afterwards round the continuous solutions. This tactic is vividly exemplified in a majority of existing cross-view hashing works such as [Kumar and Udupa, 2011; Song et al., 2013; Zhang and Li, 2014; Ding et al., 2014].

According to some recent empirical evaluations in [Liu et al., 2014; Shen et al., 2015], above relaxation + rounding schemes tend to significantly deteriorate the search accuracies, particularly when the code length becomes long. Only a few existing methods can directly conduct optimization in the hash code space. For example, ITQ [Gong and Lazebnik, 2011] learns a rotation matrix for the already-learned hash codes in order to reduce the rounding residuals. SePH [Lin et al., 2015] first learns a set of "ideal" hash code purely based on the semantic supervisory information and afterwards regresses the feature vectors to these hash codes. The work in [Liu et al., 2014] addresses the task of unsupervised hashing. It proposes a majorization-minimization scheme, such that each sub-problem with discrete variables can be solved in closed form and converges to some fixed point. [Shen et al., 2015] is its extension in a supervised setting. Clearly, a cross-view hashing method which directly optimizes the discrete code is still missing in the literature. This paper proposes a novel method of this kind.

Second, rendering reciprocal hash bits is crucial to obtain good performance. A large body of the early development of hashing methods, such as PCA-Hash and [Wang et al., 2010], require different hashing parameter vectors orthogonal to one another. This notably simplifies the numerical optimization, yet seldom entails good inter-bit complementarity with increasing code length. The works in [Xu et al., 2011; Zhen and Yeung, 2012a] sequentially learn the hash bits. At a new iteration, it assigns weights to samples in an AdaBoost fashion. More emphasis is laid on the samples that most severely violate supervisory constraints using previous hash bits. Another group of works, exemplified by [Liu et al., 2013], first generate a pool of over-complete hash bits, and then intelligently select most complementary subset.

Motivated by the empirical success in [Liu et al., 2012], we propose an efficient block-coordinate descent optimization scheme, optimizing each hash bit conditioned on others. At each iteration, a single hash bit is chosen and others are clamped. The selected hashing function and the corresponding hash codes are greedily updated for maximally complementing others. As the prominent benefit of this scheme, each sub-problem is proved to be equivalent to some quadratic form. The resultant discrete optimization problem can be efficiently solved using active set method. A rigorous convergence proof will be also provided.

2 Discrete Cross-ViewHashing

2.1 Notations

Throughout this paper we use boldface type for vectors, matrices or their collections. Assume we have a training set X that comprises of n data objects. Each data object is described by V distinct views. Let xi = (x(1) i ↪ ▷ ▷ ▷ ↪ x(V ) i ) 2 Rd1 ⇥ · · · ⇥ RdV be the feature collection for data object i, where x(v) i denotes the feature extracted from the v-th view. Following the majority of supervised hashing algorithms, let us assume that the supervision information is provided in a pairwise style. In particular, let S, D collect all similar / dissimilar pairs respectively. For notational convenience, we further introduce a supervision matrix Y 2 ¶-1↪ 0↪ 1♦n⇥n as

Let K be the desired number of hash bits and hk : Rd1 ⇥ · · · ⇥ RdV 7! ¶-1↪ 1♦↪ k = 1↪ ▷ ▷ ▷ ↪K be the corresponding hashing functions. For notational conciseness, let us stack the hash bits for all data objects, obtaining a code matrix B 2 ¶-1↪ 1♦n⇥K as below:

For brevity, denote the k-th column as Bk and the other k-1 columns as B∩k. For data object x, we use the notation b(x) to encapsulate the hash bits b1(x)↪ ▷ ▷ ▷ ↪ bK(x), and b∩k(x) for all of its hash bits except for the k-th one.

2.2 Objective Design

The proposed objective combines two considerations:

Criterion-I: semantic preservation. In the context of supervised hashing, it shall be critically ensured that similar samples have alike hash codes. We first adopt the notion of code product, which admits a one-to-one correspondence to Hamming distance and relatively easier for manipulation. A normalized version of code product ranging over [-1↪ 1] is described as

For each data pair (xi↪ xj), we would define a merit function `(xi↪ xj). Intuitively, the merit function should faithfully reflect the semantic consistency between the code product and corresponding indicator Yi↪j. Our proposed formulation supports a large spectrum of merit functions. `(xi↪ xj) is assumed to be linear with respect to b(xi) ◦ b(xj) in order to ensure algorithmic convergence. Below are two examples of valid merit functions:

Criterion-II: logistic generative probability. We also propose to leverage a generative model that estimates the probability of mapping a view-specific feature vector to some hash bit value. The purposes are two-folds: first, optimizing `(xi↪ xj) by ignoring the feature vectors may bring some hash code matrix B which perfectly satisfies all semantic supervisory constraints. We here argue that it is also important to ascertain such perfect hash codes are practically feasible based on view-specific feature vectors. And secondly, when tackling unseen querying data objects, the generative model returns their most likely hash bits.

For simplicity, we adopt linear logistic regression as the probabilistic building block, namely

where the superscript and subscript of φ(·↪ ·) collectively emphasize that the probability is for the k-th hash bit from v-th data view. wk↪v denotes the parameter vector whose length can be inferred from the context. Clearly, larger values of φ are always favored since they imply that the learned bit b has better chance to be alternatively inferred from the features.

By compiling all training data, we obtain the overall maximization problem below:

where γ > 0 is a free parameter.

3 AlternatingMaximization

The proposed cross-view hashing formulation is essentially a mixed-integer optimization problem with respect to both the discrete hash code B and continuous variables ¶wk↪v♦. The coupling of B and ¶wk↪v♦ in Eqn. (3) significantly complicates the pursuit of the optimal solutions. In fact, setting γ = 0 and adopting the linear metric function, the objective boils down to the Max-Cut problem and no polynomial-time algorithm is known to exist for achieving the global maximum. We thus adopt an alternating maximization strategy for the consideration of numerical tractability. Namely, we iterate between updating B with ¶wk↪v♦ frozen (B-Subproblem) or vice verse (W-Subproblem), which are detailed in subsequent sections respectively.

3.1 B-Subproblem

Without loss of generality, here we instantiate the merit function using the non-linear exponential form. The algorithmic description and analysis in this section also apply for other merit functions if they are linear w.r.t. the code product. Knowing ¶wk↪v♦, the B-subproblem is derived as

We tackle the above subproblem by sequentially updating the hash bits in K steps. Step k conducts a block coordinate ascent update on the k-th column of code matrix B, namely Bk. Hereafter we illustratively describe the procedure for updating bit k.

Coordinate discrete quadratic program: Importantly, we can derive an equivalent quadratic form for each sub-problem

Algorithm 1 Coordinate Discrete Optimization Procedure

• 1: Input: multi-view data X, indicator matrix Y, parameter γ.
• 2: Output: B, ¶wk↪v♦. Main Loop
• 3: Initialize ¶wk↪v♦ usingGaussian randomnumbers and initialize B according to bk(xi) = sign(PVv=1 w> k↪vx(v) i ); 4: while not converged do
• 5: Solve B-subproblem for updating the code matrix B;
• 6: SolveW-subproblem for updating parameter ¶wk↪v♦;
• 7: end while

B-subproblem

• 8: for k = 1 to K do
• 9: Calculate matrices A and Z from other K-1 bits B∩k, according to Eqns. (6)(7) respectively.
• 10: Calculate bBk by Eqn. (11) and obtain active set I; 11: Conduct active set reduction with Algorithm 2; 12: Update Bk according to Eqn. (13);
• 13: end for

W-subproblem

• 14: for (k↪ v) 2 ¶1 ▷ ▷ ▷K♦⇥ ¶1 ▷ ▷ ▷ V ♦ do
• 15: Use stochastic gradient ascent to solve Problem (14) and update wk↪v accordingly;
• 16: end for

defined on a single hash bit, which admits an efficient discrete solution. Let us first define the leave-one-out partial code product as b∩k(xi) ◦ b∩k(xj) = b(xi) ◦ b(xj) - 1K bk(xi)bk(xj). For the exponential merit function, it is easily verified

where ci↪j = 12 (e 1K Yi↪j + e- 1K Yi↪j ) and c0i↪j = 12 (e 1K Yi↪j - e- 1K Yi↪j ) are sample-specific constants. The last equality is obtained based on a simple observation: although `(xi↪ xj) is discrete and non-linear, bk(xi)bk(xj) can only take values ◦1. Therefore, we can bi-linearize e- 1K Yi↪j·bk(xi)bk(xj) through exhaustively enumerating all possible values.

Using the same idea, we can also linearize φ(v) k (b↪ x(v) i ) with respect to bk(xi), obtaining

For simplifying the notations, let us introduce two matrices A↪ B 2 Rn⇥n , whose (i↪ j)-th elements are

where di↪k↪v = 1◁2 and d0i↪k↪v = 1◁(1 + e-w> k↪v x(v) i ) -1◁2.

Updating bit k can be accomplished by solving the following quadratic polynomial involving binary discrete vector Bk, whose equivalence to Problem (4) naturally holds due to above linearization transforms:

Algorithm 2 Active Set Reduction

• 1: Input: active set I, matrices A↪Z, hash vector Bk.
• 3: Set indicator s 2 ¶0↪ 1♦n as 1 for all entries in I, otherwise 0;
• 2: Output: a reduced active set Ir ✓ I.
• 4: CalculateM=A⊙ (BkB>k ) ⊙ (ss>);
• 6: vgain M(i↪ :), whereM(i↪ :) denotes row i ofM;
• 5: Initialize Ir = ¶i♦, where i 2 I is randomly chosen;
• 7: while true do
• 8: Find the largest one from the set I ∩ Ir:

• 9: if q < 0 do, break; end if
• 10: Expand the target index set Ir Ir [ ¶i♦;
• 12: end while
• 11: Update the indicator vector vgain vgain +M(i↪ :), reflecting the (scaled) gain of adding the next element into Ir;

Active set construction and reduction: Optimizing Problem (8) can be intuitively understood as flipping some hash bits so as to elevate the objective value. Noting that most samples are prone to their original hash bit values, we construct an "active set" with few samples which have the maximal potentials of being flipped. This can be efficiently completed by a signed-gradient scheme:

and the active set is set as I = ¶i ♣ bBk(i) 6= Bk(i)♦. However, simultaneously flipping all in the active set does not ensure increasing the objective. Let B0k be the final new binary solution. We later prove that a sufficient condition for a better solution is the non-negativity of the quantity below:

To this end, we propose an efficient active set screening procedure as described in Algorithm 2, which returns a subset of I that rigorously satisfies Condition (12). The idea of this procedure is initializing bBk = Bk and greedily flipping one more bit from the original active set I at each step. The vector vgain therein denotes the increase of (B0k -Bk)>A(B0k - Bk) by flipping corresponding bit. The process terminates until the quantity in Eqn. (12) stops increasing (i.e., q < 0 in Algorithm 2). The new binary solution is then calculated as

Regarding the convergence analysis, we have the major theoretic observations below:

Proof. Let us define an auxiliary function g(X) = (2ABk◁n2 + γZ◁n)> (X - Bk), where X 2 ¶◦1♦n . Note that g(Bk) = 0 and in Eqn. (11), bBk is indeed a unique maximizer of the problem bBk = argX2¶◦1♦n max g(X). Therefore g(bBk) ≥ g(Bk) = 0. Recall that bBk induces an active set I. Since g(X) is separable w.r.t. each binary variable in X, a solution induced by any subset of I will also increase the value of g(·) compared with g(Bk). Hence the solution B0k calculated according to Eqn. (13) represents some better solution compared to Bk, namely g(B0k ) ≥ g(Bk) = 0. It is verified that

By the constructions in (12) and (13), both terms on the right hand side are non-negative, which proves the claim.

B0k will eventually converge to some fixed point, as described below.

Theorem 2. Bk converges to a fixed point that satisfies sign (2ABk◁n2 +γZ◁n) = Bk, in the sense that flipping one more bit of Bk will not further increase the objective value of Problem (8).

Proof. The claim can be established through proof of contradiction. Flipping any bit of Bk incurs some change of the objective value of Problem (8). Note that A is a symmetric matrix and its diagonal elements are all zeros. It can be verified that the change by flipping a bit is exactly the corresponding quantity in (2ABk◁n2 + γZ◁n) ⊙ (-Bk), where ⊙ denotes point-wise multiplication. Once all entries of (2ABk◁n2 + γZ◁n)⊙(-Bk) become non-positive (namely sign (2ABk◁n2 + γZ◁n) = Bk), J (Bk) can not be further improved by flipping another bit. Otherwise, we can flip any bit with positive correspondence in (2ABk◁n2 + γZ◁n) ⊙ (-Bk) to further increase J (B0k ).

Remark on complexity: The complexity of B-subproblem mainly comes frommatrices A↪ Z, vector bBk, and active set reduction. It is easily verified that the complexities of computing A↪Z↪ bBk are O(n2 )↪O(V n2 )↪O(n2 ) respectively. In Algorithm 2, iteratively updating vgain can be in an O(n2 ) complexity in the worst case (i.e., a majority of samples are included in the initial active set and most are chosen into Ir by Algorithm 2). In practice, the size of active set quickly shrinks when the optimization proceeds. In addition, we also adopt a data chunk based trick for addressing large n, as detailed in the experimental section.

3.2 W-Subproblem

For each bit-view pair (k↪ v) 2 ¶1 ▷ ▷ ▷ K♦ ⇥ ¶1 ▷ ▷ ▷ V ♦, there exists an associated parameter wk↪v. When the code matrix B is fixed, they can be updated by separately solving K ⇥ V sub-problems. Each is defined as below:

Recall that we adopt a logistic form for all φ(v) k (·↪ ·), which is amenable for stochastic gradient ascend (SGA). Specifically, the stochastic gradient for data object xi is computed by

4 Experiment

This section reports the evaluation results of the proposed cross-view hashing method and state-of-the-art competitors. Hereafter we denote the proposed method as CDH (Coordinate Discrete Hashing).

Datasets: We adopt three datasets, including Wiki [Rasiwasia et al., 2010], NUS-WIDE [seng Chua et al., 2009] and MIRFlickr [Huiskes and Lew, 2008]. For all three, our data preparation is essentially identical to other relevant works.

The Wiki dataset is crawled from Wikipedia's featured documents. It consists of 2,866 image-text pairs, which are annotated with semantic labels of 10 classes. We represent image with 128-dimensional SIFT visual feature and 10dimensional LDA topical feature. 75% of the data are used for learning the hash functions and other 25% are queries.

The NUS-WIDE dataset contains 269,648 user-generated images from Flickr.com. The experiment chooses 10 most common tags and 186,577 images associated by at least one of these tags. Each image is represented by 500-D SIFT features and 1,000-D binary indicator vector for 1,000 most frequent tags appearing in NUS-WIDE. 99% and 1% of the data are for training and querying respectively.

The MIRFlickr dataset consists of 25,000 image-text pairs from 24 unique categories. For each image object, 150-D edge histogram and 500-D textual feature are extracted. The ratios of data for train/query are 95% and 5% respectively.

Baselines and Evaluation Protocol: Our method is contrasted with a large spectrum of representative cross-view hashing methods, including CVH [Kumar and Udupa, 2011], IMH [Song et al., 2013], CMSSH [Bronstein et al., 2010],

With the gradient calculation formula, the use of SGA in Problem (14) is quite standard. We thus omit more details.

3.3 Generative Model for Out-of-Sample Data

We have introduced a generative model for each view, whose posterior is defined in Eqn. (3). These generative models can faithfully infer the most possible hash code for an unseen data object, either with all views or partial views available. Let us first consider the all-view case. Given a data object x, we estimate its k-th bit by maximizing the joint probability bk = argb2¶◦1♦ max Pk(x(1) ↪ ▷ ▷ ▷ ↪ x(V ) ↪ b).

Assume different views are independent to each other conditioned on b. Applying Bayes' rules gets

where Pk(b) represents the prior of value b and can be empirically set as its percentage in the learned codes Bk on the training data.

The joint probability for partial views can be derived in a similar spirit. In cross-view hashing, typically only one view (e.g., textual or visual view for image data) is seen for a querying data object. In this extreme case, we have Pk(x(v) ↪ ◦1) = Pk(◦1)φ(v) k (◦1↪ x(v) ) when only view v is observed. Its hash bit can be inferred by simply comparing Pk(x(v) ↪ 1) and Pk(x(v) ↪ -1).

CHMIS [Zhang et al., 2011], LSSH [Zhou et al., 2014], SCM [Zhang and Li, 2014], CMFH [Ding et al., 2014], SePH [Lin et al., 2015]. We thank all authors sharing the core source codes of the algorithms. The parameters are adopted either as the defaulted ones in the software package or the suggested values in the original papers. Following the evaluation protocol of most prior works, we adopt a Hamming ranking framework for evaluating the cross-view hashing performance. The querying data objects are assumed to have partial views (visual or textual view) seen. The hash code for the queries are calculated by the probabilistic inference model as described in Section 3.3. All database samples are ranked based on the Hamming distances to the query, and a mean average precision (mAP) score is calculated from the ranked lists as the primary indicator of the search performance.

The parameter γ in our proposed CDH plays a role of balancing the learned hash code quality and the generalization ability to unseen data. We use a grid search scheme to find the optimal γ on all datasets. Particularly, multiple trials are conducted with different γ◁n values from the candidate set [0↪ 10-2 ↪ 10-1 ↪ 1↪ 5↪ 10↪ 20↪ 50]. The value with the highest objective value on the training data is found and the corresponding accuracies are reported. We initialize the hashing parameters wk↪v using random numbers drawn from 1-D Gaussian distribution, and afterwards initialize the hash bit by bk(x) = sign[PVv=1 (φ(v) k (1↪ x(v) )-0▷5)]. The largest dataset NUSWIDE contains more than 180,000 images. Since the complexity of Algorithm 2 is quadratic w.r.t. sample count, directly manipulating the entire dataset requires tremendous memory. We thus randomly split the data into several chunks, each of which contains 10,000 images. The active set scheme is separately conducted on each data chunk.

Investigation of Experimental Results: The mAP scores for all methods are reported in Table 1. It is obvious that our proposed CDH significantly outperforms all baseline methods by 5-20% absolute accuracy gain on all benchmarks with different hash code lengths. We attribute this empirical superiority to the discrete optimization scheme. Moreover, to emphasize the generative probability term in the objective, we include a variant CDH-0, which sets γ = 0 to rule out the generative models. The comparisons reveal that on most tasks a positive γ brings notable improvement.

Figure 1 presents another three sets of results obtained on Wiki and MIRFlickr. The leftmost column displays the percentage of flipped bits (proportional to the sizes of active sets I and Ir in Algorithm 2) at different optimization iterations. Clearly, both sets quickly shrink as the optimization proceeds. The middle column shows the evolution of the search accuracy of cross-view querying. Since the object values during training are not intuitively understood, we estimate another search accuracy at the training stage by randomly choosing 1,000 training samples as the queries. We find the optimization converges very fast. In practice, after scanning all K bits two passes, both the objective values and cross-view retrieval accuracy become stable. Therefore all experiments are set to terminate after updating the hash bits at most two passes. The rightmost column investigates the mAP scores under different choices of the parameter γ. It is observed that, although each dataset favors specific γ to achieve its peak performance, the accuracies are stable with a large range of γ values.

5 Concluding Remarks

We have presented a novel formulation for hash code based cross-view image retrieval. The defining traits include an optimization scheme which directly manipulate the discrete binary variables, and a coordinate ascend method which brings a simplified sub-problem in quadratic form. We provide rigorous theoretic analysis about the convergence and local optimality condition. Moreover, our quantitative evaluations on three benchmarks also strongly validate its superiority.

Acknowledgement: Part of the research work was conducted when the first author worked at the Multimedia Department of AT&T Labs, U.S.A.. This work is supported by a start-up research grant provided by Institute of Computer Science and Technology at Peking University, China.