On Symmetric and Asymmetric LSHs for Inner Product Search

Introduction

MIPS problems of the form (1) arise, e.g. when using matrix-factorization based recommendation systems (Koren et al., 2009; Srebro et al., 2005; Cremonesi et al., 2010), in multi-class prediction (Dean et al., 2013; Jain et al., 2009) and structural SVM (Joachims, 2006; Joachims et al., 2009) problems and in vision problems when scoring filters based on their activations (Dean et al., 2013) (see Shrivastava and Li, 2014a, for more about MIPS). In order to efficiently find approximate MIPS solutions, Shrivastava and Li (2014a) suggest constructing a Locality Sensitive Hash (LSH) for inner product “similarity”.

Several tree-based methods have also been proposed for inner product search (Ram and Gray, 2012; Koenigstein et al., 2012; Curtin et al., 2013). Shrivastava and Li (2014a) argue that tree-based methods, such as cone trees, are impractical in high dimensions while the performance of LSH-based methods is in a way independent of dimension of the data. Although the exact regimes under which LSH-based methods are superior to tree-based methods and vice versa are not fully established yet, the goal of this paper is to analyze different LSH methods and compare them with each other, rather than comparing to tree-based methods, so as to understand which LSH to use and why, in those regimes where tree-based methods are not practical.

As mentioned above, our study also yields an LSH for MIPS, which we refer to as simple-lsh, which is not only symmetric but also parameter-free and enjoys significantly better theoretical and empirical compared to l2-alsh(sl) proposed by Shrivastava and Li (2014a). In Appendix A we show that all of our theoretical observations about l2-alsh(sl) apply also to the alternative hash sign-lsh(sl) put forth by Shrivastava and Li (2014b).

The transformation at the root of simple-lsh was also recently proposed by Bachrach et al. (2014), who used it in a PCA-Tree data structure for speeding up the Xbox recommender system. Here, we study the transformation as part of an LSH scheme, investigate its theoretical properties, and compare it to ls-alsh(sl).

Locality Sensitive Hashing

A hash of a set $\mathcal{Z}$ of objects is a random mapping from $\mathcal{Z}$ to some alphabet $\Gamma$, i.e. a distribution over functions $h:\mathcal{Z}\rightarrow\Gamma$. The hash is sometimes thought of as a “family” of functions, where the distribution over the family is implicit.

A hash is said to be a $(S,cS,p_{1},p_{2})$-LSH for a similarity function sim over the pair of spaces $\mathcal{X},\mathcal{Y}\subseteq\mathcal{Z}$ if for any $x\in\mathcal{X}$ and $y\in\mathcal{Y}$:

When $\mathcal{X}=\mathcal{Y}$, we say simply “over the space $\mathcal{X}$”.

Here $S>0$ is a threshold of interest, and for efficient approximate nearest neighbor search, we need $p_{1}>p_{2}$ and $c<1$. In particular, given an $(S,cS,p1,p2)$-LSH, a data structure for finding $S$-similar objects for query points when $cS$-similar objects exist in the database can be constructed in time $O(n^{\rho}\log n)$ and space $O(n^{1+\rho})$ where $\rho=\frac{\log p_{1}}{\log p_{2}}$. This quantity $\rho$ is therefore of particular interest, as we are interested in an LSH with minimum possible $\rho$, and we refer to it as the hashing quality.

An asymmetric hash is said to be an $(S,cS,p_{1},p_{2})$-ALSH for a similarity function sim over $\mathcal{X},\mathcal{Y}$ if for any $x\in\mathcal{X}$ and $y\in\mathcal{Y}$:

Referring to either of the above definitions, we also say that a hash is an $(S,cS)$-LSH (or ALSH) if there exists $p_{2}>p_{1}$ such that it is an $(S,cS,p_{1},p_{2})$-LSH (or ALSH). And we say it is a universal LSH (or ALSH) if for every $S>0,0<c<1$ it is an $(S,cS)$-LSH (or ALSH).

For any $N$ (to be set later), define the $N\times N$ matrix $Z$ as follows:

where $\odot$ denotes element-wise (Hadamard) product. Now, for a sign matrix $Z$, the margin complexity of $Z$ is defined as $mc(Z)=\inf_{Z\odot X\geq 1}\left\lVert X\right\rVert_{\max}$ (see Srebro and Shraibman, 2005, and also for the definition of the max-norm $\left\lVert X\right\rVert_{\max}$), and we know that the margin complexity of an $N\times N$ triangular matrix is bounded by $mc(Z)=\Omega(\log N)$ (Forster et al., 2003), implying

Furthermore, any collision probability matrix has max-norm $\left\lVert P\right\rVert_{\max}\leq 1$ (Neyshabur et al., 2014), and shifting the matrix by $0<\theta<1$ changes the max-norm by at most $\theta$, implying $\left\lVert P-\theta\right\rVert_{\max}\leq 2$, which combined with (5) implies $\epsilon=O(1/\log N)$. For any $\epsilon=p_{1}-p_{2}>0$, selecting a large enough $N$ we get a contradiction. ∎

For completeness, we also include in Appendix B a full definition of the max-norm and margin complexity, as well as the bounds on the max-norm and margin complexity used in the proof above.

Maximum Inner Product Search

The query $q$ is normalized: Since given a vector $q$, the norm $\left\lVert q\right\rVert$ does not affect the argmax in (1), we can assume $\left\lVert q\right\rVert=1$ always.

But first, we review l2-alsh(sl) and note that it is not universal—it depends on three parameters and no setting of the parameters works for all thresholds $S$. We also compare our simple-lsh to l2-alsh(sl) (and to the recently suggested sign-alsh(sl)) both in terms of the hashing quality $\rho$ and empirically of movie recommendation data sets.

For an integer parameter $m$, and real valued parameters $0<U<1$ and $r>0$, consider the following pair of mappings:

combined with the standard $L_{2}$ hash function

Shrivastava and Li (2014a) establishShrivastava and Li (2014a) have the scaling by $U$ as a separate step, and state their hash as an $(S_{0},cS_{0})$-ALSH over $\{\left\lVert x\right\rVert\leq U\},\{\left\lVert q\right\rVert=1\}$, where the threshold $S_{0}=US$ is also scaled by $U$. This is equivalent to the presentation here which integrates the pre-scaling step, which also scales the threshold, into the hash. that for any $0<c<1$ and $0<S<1$, there exists $0<U<1$, $r>0$, $m\geq 1$, such that l2-alsh(sl) is an $(S,cS)$-ALSH over $\mathcal{X}_{\bullet},\mathcal{Y}_{\circ}$. They furthermore calculate the hashing quality $\rho$ as a function of $m,U$ and $r$, and numerically find the optimal $\rho$ over a grid of possible values for $m,U$ and $r$, for each choice of $S,c$.

Before moving on to presenting a symmetric hash for the problem, we note that l2-alsh(sl) is not universal (as defined at the end of Section 2). That is, not only might the optimal $m,U$ and $r$ depend on $S,c$, but in fact there is no choice of the parameters $m$ and $U$ that yields an ALSH for all $S,c$, or even for all ratios $c$ for some specific threshold $S$ or for all thresholds $S$ for some specific ratio $c$. This is unfortunate, since in MIPS problems, the relevant threshold $S$ is the maximal inner product $\max_{x\in\mathcal{S}}q^{\top}x$ (or the threshold inner product if we are interested in the “top-$k$” hits), which typically varies with the query. It is therefore desirable to have a single hash that works for all thresholds.

l2-alsh(sl) is not an $(S,cS)$-ALSH for inner product similarity over $\mathcal{X}_{\bullet}=\left\{x\middle|\left\lVert x\right\rVert\leq 1\right\}$ and $\mathcal{Y}_{\circ}=\left\{q\middle|\left\lVert q\right\rVert=1\right\}$.

Assume for contradiction that it is an $(S,cS)$-ALSH. For any query point $q\in\mathcal{Y}_{\circ}$, let $x\in\mathcal{X}_{\bullet}$ be a vector s.t. $q^{\top}x=S$ and $\|x\|_{2}=1$ and let $y=cSq$, so that $q^{\top}y=cS$. We have that:

where $\mathcal{F}_{r}(\delta)$ is a monotonically decreasing function of $\delta$ (Datar et al., 2004). To get a contradiction it is therefor enough to show that $\left\lVert P(y)-Q(q)\right\rVert^{2}\leq\left\lVert P(x)-Q(q)\right\rVert^{2}$. We have:

For any $U,m$ and $r$, l2-alsh(sl) is not a universal ALSH for inner product similarity over $\mathcal{X}_{\bullet}=\left\{x\middle|\left\lVert x\right\rVert\leq 1\right\}$ and $\mathcal{Y}_{\circ}=\left\{q\middle|\left\lVert q\right\rVert=1\right\}$. Furthermore, for any $c<1$, and any choice of $U,m,r$ there exists $0<S<1$ for which l2-alsh(sl) is not an $(S,cS)$-ALSH over $\mathcal{X}_{\bullet},\mathcal{Y}_{\circ}$, and for any $S<1$ and any choice of $U,m,r$ there exists $0<c<1$ for which l2-alsh(sl) is not an $(S,cS)$-ALSH over $\mathcal{X}_{\bullet},\mathcal{Y}_{\circ}$.

In Appendix A, we show a similar non-universality result also for sign-alsh(sl).

2 SIMPLE-LSH

We propose here a simpler, parameter-free, symmetric LSH, which we call simple-lsh.

For any $x\in\mathcal{X}_{\bullet}$ we have $\left\lVert P(x)\right\rVert=1$, and for any $q\in\mathcal{Y}_{\circ}$, since $\left\lVert q\right\rVert=1$, we have:

Now, to define the hash simple-lsh, take a spherical random vector $a\sim\mathcal{N}(0,I)$ and consider the following random mapping into the binary alphabet $\Gamma=\{\pm 1\}$:

simple-lsh given in (11) is a universal LSH over $\mathcal{X}_{\bullet},\mathcal{Y}_{\circ}$. That is, for every $0<S<1$ and $0<c<1$, it is an $(S,cS)$-LSH over $\mathcal{X}_{\bullet},\mathcal{Y}_{\circ}$. Furthermore, it has hashing quality:

For any $x\in\mathcal{X}_{\bullet}$ and $q\in\mathcal{Y}_{\circ}$ we have (Goemans and Williamson, 1995):

Since for any $0\leq x\leq 1$, $1-\frac{\cos^{-1}(x)}{\pi}$ is a monotonically increasing function, this gives us an LSH. ∎

3 Theoretical Comparison

Earlier we discussed that an LSH with the smallest possible hashing quality $\rho$ is desirable. In this Section, we compare the best achievable hashing quality and show that simple-lsh allows for much better hashing quality compared to l2-alsh(sl), as well as compared to the improved hash sign-lsh(sl).

For l2-alsh(sl) and sign-alsh(sl), for each desired threshold $S$ and ratio $c$, one can optimize over the parameters $m$ and $U$, and for l2-alsh(sl) also $r$, to find the hash with the best $\rho$. This is a non-convex optimization problem and Shrivastava and Li (2014a) suggest using grid search to find a bound on the optimal $\rho$. We followed the procedure, and grid, as suggested by Shrivastava and Li (2014a)We actually used a slightly tighter bound—a careful analysis shows the denominator in equation 19 of Shrivastava and Li (2014a) can be $\log F_{r}(\sqrt{1+m/2-2cSU+(cSU)^{2^{m+1}})})$. For simple-lsh no parameters need to be tuned, and for each $S,c$ the hashing quality is given by Theorem 5.3. In Figure 1 we compare the optimal hashing quality $\rho$ for the three methods, for different values of $S$ and $c$. It is clear that the simple-lsh dominates the other methods.

4 Empirical Evaluation

We also compared the hash functions empirically, following the exact same protocol as Shrivastava and Li (2014a), using two collaborative filtering datasets, Netflix and Movielens 10M.

For a given user-item matrix $Z$, we followed the pureSVD procedure suggested by Cremonesi et al. (2010): we first subtracted the overall average rating from each individual rating and created the matrix $Z$ with these average-subtracted ratings for observed entries and zeros for unobserved entries. We then take a rank-$f$ approximation (top $f$ singular components, $f=150$ for Movielens and $f=300$ for Netflix) $Z\approx W\Sigma R^{\top}=Y$ and define $L=W\Sigma$ so that $Y=LR^{\top}$. We can think of each row of $L$ as the vector presentation of a user and each row of $R$ as the presentation for an item.

The database $S$ consists of all rows $R_{j}$ of $R$ (corresponding to movies) and we use each row $L_{i}$ of $L$ (corresponding to users) as a query. That is, for each user $i$ we would like to find the top $T$ movies, i.e. the $T$ movies with highest $\langle L_{i},R_{j}\rangle$, for different values of $T$.

To do so, for each hash family, we generate hash codes of length $K$, for varying lengths $K$, for all movies and a random selection of 60000 users (queries). For each user, we sort movies in ascending order of hamming distance between the user hash and movie hash, breaking up ties randomly. For each of several values of $T$ and $K$ we calculate precision-recall curves for recalling the top $T$ movies, averaging the precision-recall values over the 60000 randomly selected users.

In Figures 2 and 3, we plot precision-recall curves of retrieving top $T$ items by hash code of length $K$ for Netflix and Movielens datasets where $T\in\{1,5,10\}$ and $K\in\{64,128,256,512\}$. For l2-alsh(sl) we used $m=3,U=0.83,r=2.5$, suggested by the authors and used in their empirical evaluation. For sign-alsh(sl) we used two different settings of the parameters suggested by Shrivastava and Li (2014b): $m=2,U=0.75$ and $m=3,U=0.85$. simple-lsh does not require any parameters.

As can be seen in the Figures, simple-lsh shows a dramatic empirical improvement over l2-alsh(sl). Following the presentation of simple-lsh and the comparison with l2-alsh(sl), Shrivastava and Li (2014b) suggested the modified hash sign-alsh(sl), which is based on random projections, as is simple-lsh, but with an asymmetric transform similar to that in l2-alsh(sl). Perhaps not surprising, sign-alsh(sl) does indeed perform almost the same as simple-lsh (simple-lsh has only a slight advantage on Movielens), however: (1) simple-lsh is simpler, and uses a single symmetric lower-dimensional transformation $P(x)$; (2) simpler-lsh is universal and parameter free, while sign-alsh(sl) requires tuning two parameters (its authors suggest two different parameter settings for use). Therefor, we see no reason to prefer sign-alsh(sl) over the simpler symmetric option.

Unnormalized Queries

In the previous Section, we exploited asymmetry in the MIPS problem formulation, and showed that with such asymmetry, there is no need for the hash itself to be asymmetric. In this Section, we consider LSH for inner product similarity in a more symmetric setting, where we assume no normalization and only boundedness. That is, we ask whether there is an LSH or ALSH for inner product similarity over $\mathcal{X}_{\bullet}=\mathcal{Y}_{\bullet}=\left\{x\;\middle|\;\left\lVert x\right\rVert\leq 1\right\}$. Beyond a theoretical interest in the need for asymmetry in this fully symmetric setting, the setting can also be useful if we are interested in using sets $\mathcal{X}$ and $\mathcal{Y}$ interchangeably as query and data sets. In user-item setting for example, one might be also interested in retrieving the top users interested in a given item without the need to create a separate hash for this task.

We first observe that there is no symmetric LSH for this setting. We therefore consider asymmetric hashes. Unfortunately, we show that neither l2-alsh(sl) (nor sign-alsh(sl)) are ALSH over $\mathcal{X}_{\bullet}$. Instead, we propose a parameter-free asymmetric extension of simple-lsh, which we call simple-alsh, and show that it is a universal ALSH for inner product similarity over $\mathcal{X}_{\bullet}$.

To summarize the situation, if we consider the problem asymmetrically, as in the previous Section, there is no need for the hash to be asymmetric, and we can use a single hash function. But if we insist on considering the problem symmetrically, we do indeed have to use an asymmetric hash.

We first show we do not have a symmetric LSH:

For any $0<S\leq 1$ and $0<c<1$ there is no $(S,cS)$-LSH (by Definition 1) for inner product similarity over $\mathcal{X}_{\bullet}=\mathcal{Y}_{\bullet}=\left\{x\;\middle|\;\left\lVert x\right\rVert\leq 1\right\}$.

2 L2-ALSH(SL)

We might hope l2-alsh(sl) is a valid ALSH here. Unfortunately, whenever $S<(c+1)/2$, and so in particular for all $S<1/2$, it is not:

For any $0<c<1$ and any $0<S<(c+1)/2$, there are no $U,m$ and $r$ such that l2-alsh(sl) is an $(S,cS)$-ALSH for inner product similarity over $\mathcal{X}_{\bullet}=\mathcal{Y}_{\bullet}=\left\{x\;\middle|\;\left\lVert x\right\rVert\leq 1\right\}$.

Let $q_{1}$ and $x_{1}$ be unit vectors such that $q_{1}^{\top}x_{1}=S$. Let $x_{2}$ be a unit vector and define $q_{2}=cSx_{2}$. For any $U$ and $m$:

where the inequality follows from $S<(c+1)/2$. Now, the same arguments as in Lemma 1 using monotonicity of collision probabilities in $\left\lVert P(x)-Q(q)\right\rVert$ establish ls-alsh(sl) is not an $(S,cS)$-ALSH. ∎

In Appendix A, we show a stronger negative result for sign-alsh(sl): for any $S>0$ and $0<c<1$, there are no $U,m$ such that sign-alsh(sl) is an $(S,cS)-ALSH$.

3 SIMPLE-ALSH

Fortunately, we can define a variant of simple-lsh, which we refer to as simple-alsh, for this more general case where queries are not normalized. We use the pair of transformations:

and the random mappings $f(x)=h_{a}(P(x))$, $g(y)=h_{a}(Q(x))$, where $h_{a}(z)$ is as in (11). It is clear that by these definitions, we always have that for all $x,y\in\mathcal{X}_{\bullet}$, $P(x)^{\top}Q(y)=x^{\top}y$ and $\left\lVert P(x)\right\rVert=\left\lVert Q(y)\right\rVert=1$.

simple-alsh is a universal ALSH over $\mathcal{X}_{\bullet}=\mathcal{Y}_{\bullet}=\left\{x\;\middle|\;\left\lVert x\right\rVert\leq 1\right\}$. That is, for every $0<S,c<1$, it is an $(S,cS)$-ALSH over $\mathcal{X}_{\bullet},\mathcal{Y}_{\bullet}$.

Shrivastava and Li (2015) also showed how a modification of simple-alsh can be used for searching similarity measures such as set containment and weighted Jaccard similarity.

Conclusion

We provide a complete characterization of when symmetric and asymmetric LSH are possible for inner product similarity: {itemize*}

For the MIPS setting, with normalized queries $\left\lVert q\right\rVert=1$ and bounded database vectors $\left\lVert x\right\rVert\leq 1$, a universal symmetric LSH is possible.

It is important to emphasize that even though in the MIPS setting an asymmetric hash, as we define here, is not needed, an asymmetric view of the problem is required. In particular, to use a symmetric hash, one must normalize the queries but not the database vectors, which can legitimately be viewed as an asymmetric operation which is part of the hash (though then the hash would not be, strictly speaking, an ALSH). In this regard Shrivastava and Li (2014a) do indeed successfully identify the need for an asymmetric view of MIPS, and provide the first practical ALSH for the problem.

This research was partially funded by NSF award IIS-1302662.

References

Appendix A Another variant

To benefit from the empirical advantages of random projection hashing, Shrivastava and Li (2014b) also proposed a modified asymmetric LSH, which we refer to here as sign-alsh(sl). sign-alsh(sl) uses two different mappings $P(x)$, $Q(q)$, similar to those of l2-alsh(sl), but then uses a random projection hash $h_{a}(x)$, as is the one used by simple-lsh, instead of the quantized hash used in l2-alsh(sl). In this appendix we show that our theoretical observations about l2-alsh(sl) are also valid for sign-alsh(sl).

where $m$ and $U$ are parameters, as in l2-alsh(sl). sign-alsh(ls) is then given by $f(x)=h_{a}(P(x))$, $g(y)=h_{a}(Q(x))$, where $h_{a}$ is the random projection hash given in (11). sign-alsh(ls) therefor depends on two parameters, and uses a binary alphabet $\Gamma=\{\pm 1\}$.

In this section, we show that, like l2-alsh(ls), sign-alsh(ls) is not a universal ALSH over $\mathcal{X}_{\bullet},\mathcal{Y}_{\circ}$, and moreover for any $S>0$ and $0<c<1$ it is not an $(S,cS)$-ALSH over $\mathcal{X}_{\bullet}=\mathcal{Y}_{\bullet}$:

sign-alsh(sl) is not an $(S,cS)$-ALSH for inner product similarity over $\mathcal{X}_{\bullet}=\left\{x\middle|\left\lVert x\right\rVert\leq 1\right\}$ and $\mathcal{Y}_{\circ}=\left\{q\middle|\left\lVert q\right\rVert=1\right\}$.

and sign-alsh(sl) is an $(S,cS)$-ALSH. For any query point $q\in\mathcal{Y}_{\circ}$, let $x\in\mathcal{X}_{\bullet}$ be a vector s.t. $q^{\top}x=S$ and $\|x\|_{2}=1$ and let $y=cSq$, so that $q^{\top}y=cS$. We have that:

The monotonicity of $1-\frac{\cos^{-1}(x)}{\pi}$ establishes a contradiction. To get the other bound on $c$, let $\alpha_{m}=\sqrt[2^{m+1}]{\frac{(m/2)}{2^{m+1}-2}}$ and assume for contradiction that:

and sign-alsh(sl) is an $(S,cS)$-ALSH. For any query point $q\in\mathcal{Y}_{\circ}$, let $x\in\mathcal{X}_{\bullet}$ be a vector s.t. $q^{\top}x=S$ and $\|x\|_{2}=1$ and let $y=(\alpha_{m}/U)q$. By the monotonicity of $1-\frac{\cos^{-1}(x)}{\pi}$, to get a contradiction is enough to show that

For any $U,m$ and $r$, sign-alsh(sl) is not a universal ALSH for inner product similarity over $\mathcal{X}_{\bullet}=\left\{x\middle|\left\lVert x\right\rVert\leq 1\right\}$ and $\mathcal{Y}_{\circ}=\left\{q\middle|\left\lVert q\right\rVert=1\right\}$. Furthermore, for any $c<1$, and any choice of $U,m,r$ there exists $0<S<1$ for which sign-alsh(sl) is not an $(S,cS)$-ALSH over $\mathcal{X}_{\bullet},\mathcal{Y}_{\circ}$, and for any $S<1$ and any choice of $U,m,r$ there exists $0<c<1$ for which sign-alsh(sl) is not an $(S,cS)$-ALSH over $\mathcal{X}_{\bullet},\mathcal{Y}_{\circ}$.

For any $S>0$ and $0<c<1$ there are no $U$ and $m$ such that sign-alsh(sl) is an $(S,cS)$-ALSH for inner product similarity over $\mathcal{X}_{\bullet}=\mathcal{Y}_{\bullet}=\left\{x\;\middle|\;\left\lVert x\right\rVert\leq 1\right\}$.

Similar to the proof of Theorem 5.2, for any $S>0$ and $0<c<1$, let $q_{1}$ and $x_{1}$ be unit vectors such that $q_{1}^{\top}x_{1}=S$. Let $x_{2}$ be a unit vector and define $q_{2}=cSx_{2}$. For any $U$ and $m$:

Now, the same arguments as in Lemma 1 using monotonicity of collision probabilities in $\left\lVert P(x)-Q(q)\right\rVert$ establish sign-alsh(sl) is not an $(S,cS)$-ALSH. ∎

Appendix B Max-norm and margin complexity

For any two sets of objects and hashes over them, if $P$ is the collision probability matrix, then $\left\lVert P\right\rVert_{\max}\leq 1$.

For each $f$ and $g$, define the following biclustering matrix:

For any function $f:\mathcal{Z}\rightarrow\Gamma$, let $R_{f}\in\{0,1\}^{n\times|\Gamma|}$ be the indicator of the values of function $f$:

Margin complexity

For any sign matrix $Z$, the margin complexity of $Z$ is defined as:

Let $Z\in\{\pm 1\}^{N\times N}$ be a sign matrix with +1 on and above the diagonal and -1 below it. Forster et al. (2003) prove that the margin complexity of matrix $Z$ is $\Omega(\log N)$.