Year: 2020

Abstract:
In our modern world, an enormous amount of data surrounds us, and we are rarely interested in more than a handful of data points at once. It is like searching for needles in a haystack, and in many cases, there is no better algorithm than a random search, which might not be viable. Previously proposed algorithms for efficient database access are made for particular applications such as finding the min/max, finding all points within a range or finding the k-nearest neighbours. Consequently, there is a lack of versatility concerning what we can search when it comes to a gigantic database. In this work, we propose Search Data Structure Learning (SDSL), a generalization of the standard Search Data Structure (SDS) in which the machine has to learn how to search in the database. To evaluate approaches in this field, we propose a novel metric called Sequential Search Work Ratio (SSWR), a natural way of measuring a search’s efficiency and quality. Finally, we inaugurate the field with the Efficient Learnable Binary Access (ELBA), a family of models for Search Data Structure Learning. It requires a means to train two parametric functions and a search data structure for binary codes. For the training, we developed a novel loss function, the F-beta Loss. For the SDS, we describe the Multi-Bernoulli Search (MBS), a novel approach for probabilistic binary codes. Finally, we exhibit the F-beta Loss and the MBS synergy by experimentally showing that it is at least twice as better than using the alternative loss functions of MIHash and HashNet and twenty times better than with another SDS based on the Hamming radius.

heading: 1 INTRODUCTION
text: In many applications, the machines need to perform many searches in a gigantic database where the number of relevant documents is minuscule, e.g. ten in a billion. It is like searching for some needles in a haystack. In those cases, considering every document is extremely inefficient. For productivity, the search should not consider the whole database. Traditionally, this is accomplished by building a search data structure and seeking within it. Those data structures can take many forms. For example, there are tree-based structures such as the B-Tree (Bayer & McCreight, 1970), the k-d tree (Friedman et al., 1977), the R-Tree (Guttman, 1984) or the M-Tree (Ciaccia et al., 1997) to name a few. In addition to trees, KNNG (Paredes & Chávez, 2005) build a graph designed for the k-nearest neighbour search. Later approaches improve on KNNG, both for construction and search time and for the search quality itself. In those lines, there is Efanna (Fu & Cai, 2016), HNSW (Malkov & Yashunin, 2018) and ONNG (Iwasaki & Miyazaki, 2018). One of the most common types of search data structures is the hash table. It is so useful that it is implemented natively in programming languages such as Python (with the dictionary type). Hash table is often the main tool an application will use for efficiency. For example, from a short and noisy song sample, Shazam (Wang et al., 2003) can retrieve the whole song by using hash tables filled with well-designed fingerprints of each song.
Traditionally, the design of a search data structure was for a particular type of search. For example, hash tables can retrieve documents very quickly, even in gigantic databases. However, the query must be equal to the key. This requirement makes the hash table not always applicable. For instance, if the database is indexed by date and time and we seek all documents from a specific day, then it might not be optimal to query every second of that day with an equality search. B-Tree (Bayer & McCreight, 1970) was precisely introduced for applications where a range search is preferable (and faster insertion than dichotomic search is needed). Equality and range are far from being the only
types of search. For instance, the k-nearest neighbours is another well-studied type a search. Also, the subset search is a more exotic example that occurs when every queries and documents are sets and when a document is relevant if and only if it is a subset of the query. As a final example, the auto-complete function often uses a Trie data structure (De La Briandais, 1959) to suggest the end of each word.
It is easy not to realize how the problem of efficiently finding needles in a haystack was solved multiple times for specific applications. This is the ascertainment that make Search Data Structure Learning (SDSL) a significant subject. Machine Learning has been a very flexible paradigm, whether by solving multiple NLP (Natural Language Processing) tasks with a unique Transformer (Vaswani et al., 2017) or solving most Atari games with Reinforcement Learning (Mnih et al., 2013), the capacity of a single learning algorithm to perform on multiple tasks is outstanding. Search Data Structure Learning aims at developing generic learning algorithms meant for multiple types of search. Furthermore, what makes a document relevant need not to be described formally or even understood by a human. It might be k-nearest neighbour with a complex metric or something else altogether, the only thing we need for learning is a dataset. While we use the term ”Search Data Structure Learning” for the first time, algorithms that fall into its paradigm already exist. The large video-hosting platform YouTube implements an SDSL algorithm (Covington et al., 2016) for its recommendation system (the user being the query and the videos being the documents).
Not having a formalized definition of what makes a document relevant and relying on Machine Learning has its challenges, the most important being the evaluation. Traditional search data structure, such as the hash table, the Trie, the B-Tree, are exact, meaning the documents retrieved contains all and uniquely the relevant documents. For comparing those exact search data structures, when possible, the comparison between two exact search data structures is made with the asymptotic time complexity (the big-O notation). However, when the search is not exact, it is unclear how to compare structures with different efficiency and exactitude. The precision at Hamming distance of 2 is an attempt to unify those two properties into a single measure specific to the context of binary encoding. However, as described below, it fails in many aspects. It might seem like it is up to the programmer to decide what is more important between the speed and the quality of the retrieved documents. For example, the recall-queries per second (Aumüller et al., 2017) helps to visually understand the trade-off between speed and quality. In section 3, we describe a reliable measure to evaluate the efficiency and quality simultaneously of any search data structure. This metric solidifies the Machine Learning subfield of Search Data Structure Learning.
This article presents the SDSL framework that brings two crucial generalization w.r.t. its predecessors (Li et al., 2011; Cayton & Dasgupta, 2008). First, it allows for dynamic databases, i.e. databases that might change or evolve after training. For example, it is plausible that a company wants to design and train a search engine ready for distribution to multiple clients without further training on each client’s database. The current mindset is to retrain each time a new database is given; however, this is not feasible in many cases. Hopefully, this article motivates the research towards models that can generalize to never seen databases. Secondly, the previous framework does not support relative relations, i.e. when the relevance of a document w.r.t. a query depends on the other documents in the database. The most studied relative relations is probably the KNN task, which is relative since it is impossible to know if a document is in the k-nearest neighbour of a query without knowing the other documents. In contrast, radius search is an example of what we call an absolute relation because it is possible to know if a document is relevant to a query only by looking at the query-document pair. In this work, however, we did not introduce relative relations only for KNN. Many interesting relative relation tasks exist; for example, another rather exciting example of relative relation is the multiple supporting facts:
A harder task is to answer questions where two supporting statements have to be chained to answer the question [...] where to answer the question “Where is the football?” one has to combine information from two sentences “John is in the playground” and “John picked up the football”. (Weston et al., 2015).
In this work, we first introduce a general framework to formalize the SDSL task in which we present a novel metric to simultaneously evaluate the efficiency and quality of the search. Then, we inaugurate the field of SDSL with Efficient Learning Binary Access (ELBA) (Section 4) that describes a family of models that use a traditional search data structure and parametric functions (e.g. neural networks) to create a discrete binary code(s) for both the queries and documents. A reader familiar
with the field must appreciate the difficulty that has to be overcome when dealing with (semi)discrete structure. To instantiate ELBA, we concocted the F-beta Loss used for the training and Multi-Bernoulli Search (MBS), a novel SDS technique designed for probabilistic binary codes. Finally, for comparisons, we will instantiate ELBA with other loss functions and another SDS, namely the MIHash’s loss (Cakir et al., 2017), the HashNet’s loss (Cao et al., 2017), and the Hamming Radius Search C.4. We will then experimentally show the F-beta Loss and MBS’s advantage by putting in evidence their synergy.

heading: 2 RELATED WORK
text: In data structure terminology, the concepts of dynamic and static structures describe whether or not the structure can change via insertion, deletion or merge. In SDSL, if the database(s) used for training are not the same as the one(s) used for evaluation, then the structure has to search for documents only seen once at insertion. From a Machine Learning perspective, this is known as a One-Shot Learning task. For example, Matching Network (Vinyals et al., 2016) tries to match never seen elements together. However, applying their technique would require a database scan. Hence it is incompatible with a gigantic database. In the same vein, soft addressing (or attention) is a differentiable mechanism to select an element from many, thus compatible with gradient descent. Memory Network (Kumar et al., 2016), Neural-Turing Machine (Graves et al., 2014) and Transformer (Vaswani et al., 2017) all use some kind of soft addressing. It is interesting for training our models but cannot be used alone in SDSL. For the same reason as above, it would require considering the whole database.
Finding the k-nearest neighbour is trivial with unlimited resources. In this field, the research focuses mainly on the efficiency of both the search and the structure’s construction. The exact algorithms are as efficient in higher dimensions than a random search due to the curse of dimensionality. Consequently, the focus has recently been on approximate k-nearest neighbour. The search data structure developed are mostly tree-based, such as the k-d tree (Friedman et al., 1977) or the K-Means tree (Nister & Stewenius, 2006), and graph-based, such as the KNNG (Paredes & Chávez, 2005), Efanna (Fu & Cai, 2016), HNSW (Malkov & Yashunin, 2018) or ONNG (Iwasaki & Miyazaki, 2018) just to name a few. A good resource for comparing those approaches is the ann-benchmark Aumüller et al. (2017). In this work, we generalize the problem to conceive algorithms able to learn what to search efficiently.
Efficient Learnable Binary Access, described below, encodes queries and documents into binary vectors. In this work, we will use neural networks as the encoders. Such encoders already exists in the literature. For example, CNNH (Xia et al., 2014), DPSH (Li et al., 2015), DHN (Zhu et al., 2016), GreedyHash (Su et al., 2018), PGDH (Yuan et al., 2018), HashGan (Cao et al., 2018), ADSH (Jiang & Li, 2018) or JMLH (Shen et al., 2019), just to name a few. Below we compare different loss functions, the F-beta Loss 4 the MIHash’s loss Cakir et al. (2017) and HashNet’s loss Cao et al. (2017).
Graph learning, introduced in Zhu et al. (2003) for semi-supervised learning, is a type of data structure learning that has shown experimentally to be a strong idea. Those models learn to do inference from graphs, sometime by generating them first. Some approaches work with static graphs (static structures) (Zhu et al., 2003; Perozzi et al., 2014; Scarselli et al., 2008; Bruna et al., 2013) while other work with dynamic graphs (dynamic structures) (Narayan & Roe, 2018; Manessi et al., 2020). While this literature does not focus on retrieval, they learn to compute using a data structure.
To put SDSL in contrast with the Learning to Search framework (Li et al., 2011). As mentioned in the introduction, it does not support dynamic databases and relative relation. It is possible to update the framework to deal with dynamic databases by taking an expectation over the databases in the retrieval quality Q(T ) and computational cost C(T ). However, it is not clear how to deal with relative relations because the selection function T (q, x) is a ”matching function” that does not exist for relative tasks. Generalizing the selection function by allowing it to consider the whole database (i.e. with T (q,X)) does not work because T (q,X) could use the ranking function s(x, q) on every document and nothing would penalize such exhaustive strategies since the computational cost is the number of candidates. Nevertheless, this is not the main issue. As with the framework proposed in Cayton & Dasgupta (2008), the computational cost does not consider the retrieval cost but only the size of the candidates set (divided by the number of documents in the database for the
latter framework). Those frameworks fail to quantify the work needed to retrieve the candidates. For example, while proposing the Learning to Search framework, the authors relied on timing to evaluate their model. The SDSL framework, proposed below, provides a unique quantity that quantifies both the cost of retrieval and the candidates’ quality simultaneously.
Finally, while not introduced as such, an SDSL algorithm is used in NLP. In this field, many articles attempt to accelerate the training and inference of the neural network based models, in which the main bottleneck is the normalization over a large vocabulary. Morin & Bengio (2005) use a precomputed tree and train their model to travel from the root to a leaf, where each leaf corresponds to a word. Doing so accelerates both training and inference. Latter, Mnih & Hinton (2009) proposed a way to learn the structure of the tree.

heading: 3 FORMALISATION OF THE PROBLEM
text: Let Q be the query universe, let U be the document universe, and let D be the set of databases, i.e. the set of all finite sets of documents. The task is formulated with a set of relations corresponding to each database R = {RD : Q → 2D | D ∈ D}. This is to allow the general case where the relation is relative. Definition 3.1. The relation set R is absolute if there is a match function M : Q × U → {True, False} s.t. ∀q ∈ Q, D ∈ D, d ∈ D, M(q, d) ⇔ d ∈ RD(q) otherwise, we say it is relative.
This definition can easily be generalized to the cases where each RD is probabilistic map by using probability instead of a truth value.
For the F-beta loss to be defined in Section 4, we restrict ourselves to absolute relation sets and thus, only the query-document pair determines if the document is relevant. However, the rest of this formalization is for both relative and absolute relation sets.
The mAP is a widely used metric in information retrieval. However, it does not consider the work done to perform the ranking. An SDS could compare the query to every document in the database and have a good mAP. In SDSL, we want to monitor the quality as well as the efficiency of retrieval. The Recall Query per second (RQPS) (Aumüller et al., 2017) is also used in the ANN literature. However, it is not suitable for theoretical analysis since the results depend on the implementation and the hardware. It is possible to generalize the RQPS by changing what quantifies the amount of work done for retrieval (to something else than the number of seconds). Nevertheless, the RQPS has a parameter (k) that limits the number of candidates to generate. This parameter prevents a model from generating all documents in the database as its candidates, which would give 100% recall without any computation and, consequently, having an excellent score doing nothing. Ultimately, the parameter k is a fix to the flaw that the RQPS does not consider the precision. In SDSL, we want to legitimately compare models that might not generate the same number of candidates. To the best of our knowledge, the precision at a Hamming distance of two (p@2) is the only proposal in the literature to consolidate the search’s efficiency and quality without relying on the hardware and the implementation. Obviously, this metric has many limitations. First, it is only relevant when the model transforms the queries and documents into binary codes. More importantly, it does not consider the recall quality. For example, if a query should return several relevant documents but only one relevant document (and no irrelevant ones) are within a Hamming distance of two according to the model, the p@2 score would be maximal for this query even though the system has a very poor recall. Another significant limitation is the fact that it does not weight the score w.r.t. the distance. In many contexts, the amount of work increases a thousandfold when comparing a perfect match (Hamming distance 0) and distance 2.
In this work, we present a generic metric for any SDSL task. We grounded the metric on a very pragmatic standpoint by asking what kind of strategy a programmer would use to find relevant documents in a database quickly. At first, one might consider a random search with a good matching function (e.g. a neural network). However, if the database is enormous, this strategy will give poor performances. One could then consider filtering a significant portion of the database using a search data structure, but the retrieved documents might contain multiple false positives, decreasing the precision. We believe we can have the best of both solutions by combining them, first filtering a large portion of the database with a search data structure and then using a good matching function to filter
the retrieved documents. Finally, to evaluate if the search data structure is useful, the programmer could consider the cost of searching in the structure plus the cost of a random search in the retrieved documents versus the cost of a random search in the whole database. This is the central idea of the Search Work Ratio, the precursor of the Sequential Search Work Ratio, both defined below. Definition 3.2. A relevance oracle is an oracle capable of computing if a document is relevant. Definition 3.3. The relevance oracle cost, noted C(N,K, k), is the expected number of oracle’s calls needed to find k relevant documents within a set containingN documents whereK are relevant, when doing a random search without replacement. Lemma 3.1. C(N, K, k) = k(N + 1)/(K + 1). (Proof in appendix A.)
As mentioned previously, we do not intend for the search data structure to produce the final results. Instead, another entity (e.g. a program or a human) should refine the retrieved documents. In many applications, mainly when the relevance function is absolute, it is conceivable that this entity is nearly perfect or, at least, significantly more precise than the SDS. Consequently, we define the cost of finding k relevant documents in a set of size N containing K relevant documents as the relevance oracle cost C(N, K, k). As a generalization, we can weigh differently when the oracle receives a relevant document versus when it does not. The weighting would consider a real refinement entity’s potential errors and put different values to the false positives and false negatives. For simplicity, in this work, we will not weight the calls to the oracle.
The Search Work Ratio (SWR) is the ratio between the work done using the SDS versus the work done without using the SDS. Consequently, an SWR score of less than 1 implies that it is less costly to use the SDS and vice-versa. Furthermore, the SWR has a simple interpretation. For example, an SWR of 1/2 implies that using the SDS reduces the cost by a factor of two. Definition 3.4. Let D ∈ D, R ∈ 2D, k ∈ N, ω0 ∈ R and δ0 ∈ 2D, then the Search Work Ratio is
SWR(D, R, k, ω0, δ0) = C(|δ0|, |δ0 ∩R|, k) + ω0
C(|D|, |R|, k) ∈ R+,
where D is a database, R is the relevant documents in this database, k is the minimum number of documents we want to find, ω0 ∈ R+ is the cost of searching with the SDS, and δ0 is the candidates retrieved by the SDS. The cost could be any complexity measure, e.g. time or space. In this work, since we will work only with hash tables, ω0 will be the number of hashes computed. We assume that using the oracle has the same cost as computing a hash. The SWR has a significant flaw; it requires that the SDS find enough relevant documents. Otherwise, it is not defined. We will now slightly generalize this definition using a relevance generator to avoid this issue.
It is not rare that an SDS can be slightly modified to produce a sequence of sets of candidates.. For example, an approximate tree or graph search often employs a limit of nodes in the exploration. It is possible to modify those algorithms to generate candidates with an increasing number of nodes to explore. Definition 3.5. Let D ∈ D, R ∈ 2D, k ∈ N, ω ∈ RN and δ ∈ (2D)N s.t. T = min{t s.t. t ∈ N and | ∪ti=0 δi ∩R| ≥ k} exists, then the Sequential Search Work Ratio is
SSWR(D, R, k, ω, δ) = C(|δT |, |δT ∩R|, k − |H ∩R|) + |H|+
∑T t=0 ωt
C(|D|, |R|, k) ∈ R+,
with H = ∪T−1i=0 δi if T > 0 and H = ∅ otherwise.
The SSWR’s numerator corresponds to a random search with the relevance oracle on the last generated candidates set plus the cost of considering all previously generated candidates plus the amount of work for computing all candidates sets up to T . The SSWR uses the relevance oracle cost only over the last sets of candidates because the generator did not found enough relevant documents before generating the last sets of candidates. Consequently, an exhaustive search with the oracle in the previous sets of candidates was performed before asking the generator to yield more candidates. The SSWR account for this exhaustive search with the |H| term. Finally, the sets of candidates are intended to be mutually exclusive because this will reduce the relevance oracle cost computed over the last sets of candidates and give a better SSWR. However, it is not mandatory.
Definition 3.6. The Search Data Structure Learning (SDSL) framework consists of minimizing the expected SSWR over generators (of sets) of candidates w.r.t. database-query pairs. Formally, given a work function W : GD, q 7→ (ω0, ω1, . . . ) ∈ RN where q ∈ Q and GD is a generators w.r.t. a database D ∈ D the goal of SDSL is to minimize,
min G
ED,q [SSWR(D,RD(q), k, W(GD, q), GD(q))] .
We minimize the expectation over all databases to ensure the generator’s quality even if the database changes, i.e. for dynamic databases. By letting the distribution over D to be deterministic, we fall into the framework with a static database.

heading: 4 EFFICIENT LEARNABLE BINARY ACCESS
text: This section describes a family of models to tackle SDSL tasks: the Efficient Learnable Binary Access (ELBA). It consists of two parametric families of functionFQ andFU (e.g. neural networks) called the queries and documents encoders, and a Multi-Bernoulli Search (MBS) data structure S that will be made explicit later. Any function from FQ and FU must have their domain onQ and U , respectively, and their image in [0, 1]n to be interpreted as the parameters of a Multi-Bernoulli1 (in its canonical form). Precisely, ELBA is specified by the following triplet ELBA = (FQ, FU , S) with FQ = {fθ : Q → [0, 1]n | θ ∈ ΘQ} and FU = {fθ : U → [0, 1]n | θ ∈ ΘU}. Note that in the particular case where Q = U , it is possible to use the same function for the queries and the documents (ELBA = (F , S)). We call this the shared variant of ELBA. As opposed to the unshared variant where the parametric families might be the same, but the parameters are free to be different (e.g. the same neural network but with different parameters).
Multi-Bernoulli Search (MBS) data structure is a key-value based data structure that implements insert and search. This data structure uses M back-end key-value based data structures compatible with binary vectors keys. The back-end data structures S1, S2, . . . , SM , must also implement insert(S, key, value) where S ∈ {S1, S2, . . . , SM} is the data structure into which we insert the value w.r.t the key. Similarly, the back-end structures must implement search(S, key), which must return the appropriate set of values. While the key given to the back-end data structures are binary vectors, the key given the MBS must be the parameters of a Multi-Bernoulli distribution of dimension n, i.e.
key = π = (π1, π2, . . . , πn) ∈ [0, 1]n.
For insertion, the MBS computes the M most probable outcomes of the Multi-Bernoulli (which might not be unique) and uses them as the keys for inserting in a back-end data structures. For searching, the MBS computes the T most probable outcomes of the Multi-Bernoulli (which, again, might not be unique) and uses them as the keys for searching in each back-end data structures. Consequently, the search performs TM back-end searches. The pseudo-code is in the appendix B.2. Note that the insert method does not require T . Consequently, we can make the insertions and then choose T. This fact makes possible the modification of the search to generate candidates every time it searches in a back-end structure. Finally, to conform with the SDSL’s framework, it is possible to generate candidates by yielding candidates each time we search in a back-end structure.
Computing efficiently the top-k most probable outcomes of a Multi-Bernoulli is not trivial. In the appendix B, we describe how to do it. Throughout this work, we will use the Hashing MultiBernoulli Search (HMBS), an implementation of the MBS that uses hash tables as its back-end data structures. An example of how inserting, searching and generating can be found in the appendix B.3.
To implement ELBA, we need a means to select a function from each parametric family. As the parametric families, we consider neural networks, which we aim to train with gradient descent. Consequently, we need a loss function. Thus in this section, we will describe the F-beta Loss, a novel loss function design to perform well with MBS.
1The Multi-Bernoulli is a random vector composed of n independent but not identical Bernoulli.
We will restrain ourselves to absolute relevance function. For this reason, we will use a dataset of the form {(qi, di, ri)}Ni=1 = (qi, di, M(qi, di))}Ni=1. The model will try to predict the Matching functionM. We will denote the matching prediction function M̂θ. Since the Multi-Bernoulli Search requires the (canonical) parameters of the Multi-Bernoulli representation of the query {πqi }ni=1 for search and of the document {πdi }ni=1 for insert (with n the chosen number of Bernoulli in the Multi-Bernoulli random variables), it is primordial that the model provides such quantity in its computational pipeline. Let fQθ (q) = π q and fUθ (d) = π d be the parametric functions for the queries and the documents, both implemented with a neural network ending with a sigmoid. Note that, depending on the case, the two neural networks might or might not share parameters. Finally, since we want to create a synergy with Hashing Multi-Bernoulli Search, we need the bits to be all equal if and only if the matching prediction function is one. Thus we define,
M̂θ(q, d) = n∏ i=1 πqi π d i + (1− π q i )(1− π d i ),
which is the probability of both Multi-Bernoulli random variables are equal according to the distributions {πqi }ni=1 and {πdi }ni=1. We define three essential quantities: the recall, the fallout, and the predicted matching marginal (pmm for short), respectively:
rθ = Eq,d|M(q,d) [ M̂θ(q, d) ] , sθ = Eq,d|¬M(q,d) [ M̂θ(q, d) ] , mθ = Eq,d [ M̂θ(q, d) ] .
We can compute empirical averages to produce unbiased estimators of those quantities.
r̂θ = 1 |I+| ∑ i∈I+ M̂θ(qi, di), ŝθ = 1 |I−| ∑ i∈I− M̂θ(qi, di), m̂θ = qr̂θ + (1− q)ŝθ.
where I+ and I− are the sets of indexes for query-document pairs in the dataset that match and do not match, respectively, and with q being the probability of having a matching pair. It is also possible to derive an estimator for the precision pθ = qrθmθ , with p̂θ = qr̂θ m̂θ . However, it is biased.
For numerical stability and because the gradients w.r.t rθ, sθ and mθ are near zero when the training starts, we need to consider their logarithm for the loss function. Maximizing precision gives a model capable of discriminating between positive and negative pairs, but it leaves the recall untouched, and having a high recall is vital for the HMBS to find the relevant documents. Furthermore, only maximizing the recall induce the model towards a constant Multi-Bernoulli distribution with zero entropy, i.e., independent of the input and where all the probabilities are near 0 or 1. We tried maximizing the recall while minimizing the fallout, i.e. with a loss similar to maxθ log(rθ) − λ log(sθ). However, we found it extremely hard to optimize — there was no sweet spot for lambda. When the model’s recall was sufficient, it was because it collapsed to a constant function. Scheduling λ to alternate between a small value and a relatively high value has shown limited experimental success. In the end, we were looking for a tradeoff between the precision and the recall. The F-beta came naturally. However, since our precision estimator is biased, it is simpler to reparameterize the standard F-beta with the pmm using pθ = qrθmθ given us,
Fβ = (1 + β2)qrθ qβ2 +mθ with β ∈ R+
For the above reasons, we considered the logarithm of the F-beta,
logFθ = log((1 + β 2)q) + log(rθ)− log(qβ2 +mθ) with β ∈ R+
However, if we replace the recall term by its estimator directly we will get the LogSumExp (LSE) w.r.t. log M̂θ(qi, di) for i ∈ I+. i.e., log(r̂θ) = LSE{log M̂θ(qi, di) | i ∈ I+} which is known to act as a soft maximum (not to be confused with its gradient, the Softmax). Doing this will yield a near-zero gradient for the matching pairs with the lowest predicted matching value. It would be problematic since those pairs are the ones that need the most gradient.
Instead, we propose an alternative estimator of the log F-beta, which we call the F-beta Loss, where we replace the LSE with the average logarithm of the predicted matching value.
log F̂θ = c+ 1 |I+| ∑ i∈I+ log M̂θ(qi, di)− log(qβ2 + m̂θ)
with β ∈ R+ and c = log(1 + β2) + log q. Note that it is simple to compute with numerical stability the logarithm of the sigmoid function. Most, if not all, Machine Learning libraries natively define this function.

heading: 5 EXPERIMENTS AND RESULTS
text: We performed all experiments on a dataset build from MNIST (LeCun et al., 1998), which we call NoisyMnist. We do not intend NoisyMnist to be a challenging task but rather a tool to analyze the convergence properties and draw comparisons between each models’ qualities. In this dataset, the document and query are MNIST images with value ranging from 0 to 1 with additive Gaussian noise (the value can consequently go below 0 and above 1). The mean and std of the noise is 0 and 0.2, respectively. The relevance function of NoisyMnist is absolute, and we define the matching function as follows: a query match with a document if and only if their original MNIST image was the same before we added the noise. In figure 1, there are 6 examples of queries-documents pairs. For evaluation, We build a fixed database with 10K different images from MNIST not accessible while training. From those 10K, we randomly selected 1K to create the queries. Finally, we added the noise on each image (the query and their corresponding document do not share the same noise). In this evaluation database, there is a unique document relevant for each query. It is one in ten thousand, making it a proper database for SDSL.
We considered two alternatives for the F-beta Loss and one alternative to the MBS. For the F-beta Loss, we selected the loss function of MIHash (Cakir et al., 2017) and the loss function of HashNet (Cao et al., 2017) because of their compatibility with with ELBA. More specifically, they both produce quantities that can be interpreted as the parameters of a Multi-Bernoulli, and they both can be trivially generalized to the unshared case. Furthermore, as an alternative to MBS, we choose the Hamming Radius Search (HRS) described in appendix C.4. Combining the three losses with the two data structures creates six Efficient Learnable Binary Access models. We deployed each model in both the shared and unshared categories, for a total of twelve scenarios.
Training was run 5 times for each model, and the top 5 sets of parameters w.r.t the SSWR were selected for a total of 25 sets of parameters for each of the twelve models. All the values provided are the average of those 25 points. Each training consisted of 100K batches of size 32, which was plenty for all models to converge. At each 500 batches, we performed an evaluation giving us 200 sets of parameters to select from. We performed all evaluations using the same fixed set of 10K validation documents and a corresponding fixed set of 1K validation query described above. Those documents and queries were never seen while training. All networks are ResNet18 (He et al., 2016) adapted to MNIST, i.e. the first convolution takes from one channel with no stride and the last linear layer output a vector of size 64 (for 64 bits). The hyperparameters and training schedule can be found in the appendix C. Finally, we use halting for all six models as is describe below.
When using generators iterating over binary codes, such as HRS and MBS, it is crucial to halt the iteration before it finishes. For example, for 64 bits, there are 264 possible hashes, which is certainly larger than any database. In those cases, it does not make sense to compute every possible hash. Halting is the mechanism that decides when to stop a relevance generator and produce the database’s remaining document as the final candidates set. Note that, when halting, the SSWR is always greater than one. In all experiments with HRS, we used a halting of 2081. It corresponds to generating every document with binary codes within a radius of two from the query’s code (for 64 bits). In this case, halting afterward is arbitrary since the next 41664 codes (distance of 3) come in no particular order. Finally, in all experiments with HMBS, we use a halting of 5001, which corresponds to stopping when the amount of work done exceeds the expected amount of work without an SDS, i.e. C(10000, 1, 1). Table 1 shows that F-beta (from this work) outperforms MIHash and HashNet in both unshared and shared categories. Noteworthily, MIHash and HashNet fail in the unshared categories. While HashNet successfully produces binary codes with lower Hamming distance for positive than negative pairs, the distance is way too high to be used with hash tables. MIHash, on the other hand, only push towards increasing the mutual information between the Hamming distance and whether or not the pair matches. It implies that there is no (explicit) pressure towards having a small Hamming distance. The synergy between the loss function and shared parameters is why MIHash and HashNet produce low Hamming distances for positive pairs for the shared problem. The found solutions for the unshared problem are not available when the queries and documents networks are the same. Parameter sharing acts as a colossal regularization. Those poor results suggest that both MIHash and HashNet are constrained to similarity search. Making F-beta the superior loss function for ELBA with hash table based SDS.
On the other hand, HMBS’s results are far superior to those of HRS. In the case of shared F-beta, they are 46 times better. The only case for which it is not true is for shared HashNet. However, both of those models are not competitive. The fat tail of its Hamming distances distribution is at cause. In our experiments, we noted that varying the halting did not seem to change the results drastically. Additional figures provided in the appendix D might convey a more intuitive understanding of the contrast between the different scenarios.

heading: 6 CONCLUSION AND FUTURE WORK
text: In this article, we proposed a novel and practical field of Machine Learning called Search Data Structure Learning, for which we propose a natural metric, the SSWR. We inaugurated this field with a new family of models, the Efficient Learnable Binary Access, which we instantiated with the F-beta Loss and the MBS that outperformed multiple alternatives, reducing by at least a factor of two the SSWR. We cannot overstate the importance of F-beta in this project. The capacity to obtain convergence on discrete output without being caught in a local minimum is a powerful tool. In NLP, the F-beta led us to several exciting breakthroughs when learning semantically rich discrete embedding for words. The fact that studying SDSL led to breakthroughs in other domains is, for us, an attestation of its significance.
Furthermore, we plan to extend the formalization to consider insertion, deletion, dependent queries, and dependent retrieved documents in future work. Such generalization could be useful for tasks like dialogue modelling or question answering. Also, in this work, the halting procedure was simplistic. In the future, we are interested in working with models that can decide when to stop based on the query and the retrieved documents. Finally, we are eager to work with non-hashing-based approaches, such as trees or graphs.

heading: A THE RELEVANCE ORACLE COST
text: Formally, let S be a set of N documents containing K ≤ N relevant documents. From this K elements, we want to find at least k ≤ K elements. We want to compute how many calls in expectation are needed to find those k elements if we sample from S uniformly without replacement. We will denote this expectation C(N,K, k). Let G(k ; N,K, n) be the Hypergeometric Distribution with parameters N , K, n. This distribution gives the probability that from a set with N documents from which K are relevant, we sample exactly k relevant documents in n uniform trials without replacement.
G(k ; N,K, n) = ( K k )( N−K n−k )( N n
) . Let P(n ; N,K, k) be probability distribution, defined below, with parameters N , K, k. This gives the probability that from a set with N documents from which K are relevant, it takes n uniform trials without replacement to get precisely k relevant documents. We have,
P(n ; N,K, k) = G(k − 1 ; N,K, n− 1)K − (k − 1) N − (n− 1) ,
which is the probability that we have k − 1 relevant documents in n − 1 trials multiplied by the probability that we sample a relevant document in a set with N − (n − 1) documents from which K − (k − 1) are relevant. Finally, the expectation of P(n ; N,K, k) yields the wanted measure. I.e. if X ∼ P(· ; N,K, k) then,
C(N, K, k) = E [X] = N∑ n=1 nP(n ; N,K, k) = ( N + 1 K + 1 ) k,
with the last equality shown below A.1.
Lemma A.1. If X ∼ P(· ; N,K, k) then,
E [X] = ( N + 1
K + 1
) k
Proof. with A ≥ a, B ≥ b and A ≥ B all natural numbers.
E [X] = N∑ n=1 nP(n ; N,K, k)
= N−(K−k)∑ n=k nP(n ; N,K, k) remove zeros
= N−(K−k)∑ n=k nG(k − 1 ; N,K, n− 1)K − (k − 1) N − (n− 1)
= N−(K−k)∑ n=k n
( K k−1 )( N−K n−k )( N n−1 ) K − (k − 1) N − (n− 1)
= N−(K−k)∑ n=k n k
K−k+1 ( K k )( N−K n−k ) n
N−n+1 ( N n ) K − (k − 1) N − (n− 1)
with ( A
a− 1
) =
a
A− a+ 1
( A
a
)
= N−(K−k)∑ n=k k
( K k )( N−K n−k )( N n
) =
N−(K−k)∑ n=k k
( n k )( N−n K−k )( N K ) with (Bb )(A−Ba−b )( A a ) = (ab)(A−aB−b)( A B
) =
k( N K ) N−(K−k)∑ n=k ( n k )( N − n K − k ) =
k( N K )(N + 1 K + 1 ) a variant of Vandermonde’s identity
= k( N K ) N + 1 K + 1
( N
K
) with ( A+ 1
a+ 1
) = A+ 1
a+ 1
( A
a ) = ( N + 1
K + 1
) k

heading: B TOP-K MAXIMAL MULTI-BERNOULLI OUTCOMES
text: Let bi be n independent and non-identical Bernoulli random variables with probability πi to be one. Let zi be the most probable outcome of bi and let pi be the probability that bi be the most probable outcome (bi = zi) i.e.
zi = { 1 if πi > 1/2 0 otherwise
pi = { πi if πi > 1/2 1− πi otherwise
note that pi is always greater or equal than 1/2. The theorem B.2 gives us the following result.
P (b=x) > P (b=y)⇐⇒ n∑ i=1
s.t. xi 6=zi
log(pi)− log(1− pi) < n∑ i=1
s.t. yi 6=zi
log(pi)− log(1− pi)
This implies that finding the Top-K Minimal Subset Sum of A = {a1, a2, . . . , an} with ai = log(pi) − log(1 − pi) ≥ 0 will yield the Top-K Maximal Multi-Bernoulli Outcomes. The Top-K Minimal Subset Sum problem can be solve using standard programming techniques. The pseudocode for the reduction is in the appendix B.2.

heading: B.1 REDUCTION TO TOP-K MINIMAL SUBSET SUM
text: Lemma B.1. Let pi ∈ [0, 1], ai ∈ {0, 1} and bi ∈ {0, 1}, for i ∈ {0, 1, . . . , n} then
n∏ i=1 paii (1− pi) 1−ai < n∏ i=1 pbii (1− pi) 1−bi
⇐⇒ n∏ i=1 p1−aii (1− pi) ai > n∏ i=1 p1−bii (1− pi) bi
Proof. Let I+ = {i | i ∈ N, 1 ≤ i ≤ n, ai = bi} and let I+ = {i | i ∈ N, 1 ≤ i ≤ n, ai 6= bi} we have,
n∏ i=1 paii (1− pi) 1−ai < n∏ i=1 pbii (1− pi) 1−bi
⇐⇒ ∏ i∈I+ paii (1− pi) 1−ai ∏ i∈I− paii (1− pi) 1−ai < ∏ i∈I+ pbii (1− pi) 1−bi ∏ i∈I− pbii (1− pi) 1−bi
⇐⇒ ∏ i∈I− paii (1− pi) 1−ai < ∏ i∈I− pbii (1− pi) 1−bi
⇐⇒ ∏ i∈I− p1−bii (1− pi) bi < ∏ i∈I− p1−aii (1− pi) ai since ∀i ∈ I−, ai = 1− bi
⇐⇒ ∏ i∈I+ p1−bii (1− pi) bi ∏ i∈I− p1−bii (1− pi) bi < ∏ i∈I+ p1−aii (1− pi) ai ∏ i∈I− p1−aii (1− pi) ai
⇐⇒ n∏ i=1 p1−bii (1− pi) bi < n∏ i=1 p1−aii (1− pi) ai
Theorem B.2. Let b be a Multi-Bernoulli of parameter π ∈ ]0, 1[n and let
zi = { 1 if πi > 1/2 0 otherwise
pi = { πi if πi > 1/2 1− πi otherwise
then, for any x ∈ {0, 1}n and y ∈ {0, 1}n we have
P (b=x) > P (b=y)⇐⇒ n∑ i=1
s.t. xi 6=zi
log(pi)− log(1− pi) < n∑ i=1
s.t. yi 6=zi
log(pi)− log(1− pi)
Proof. For notational simplicity, let x̄i = xi ⊕ zi and let ȳi = yi ⊕ zi (with ⊕ being the exclusive or)
P (b=x) >P (b=y) ⇐⇒ n∏ i=1 P (bi=xi) > n∏ i=1 P (bi=yi) since the Bernoulli are independent
⇐⇒ n∏ i=1 πxii (1− πi) 1−xi > n∏ i=1 πyii (1− πi) 1−yi
⇐⇒ n∏ i=1 p1−x̄ii (1− pi) x̄i > n∏ i=1 p1−ȳii (1− pi) ȳi proved by cases (πi > 1/2 and πi ≤ 1/2)
⇐⇒ n∏ i=1 px̄ii (1− pi) 1−x̄i < n∏ i=1 pȳii (1− pi) 1−ȳi by lemma B.1
⇐⇒ n∑ i=1 x̄i log(pi) + (1− x̄i) log(1− pi) < n∑ i=1 ȳi log(pi) + (1− ȳi) log(1− pi)
⇐⇒ n∑ i=1 x̄i (log(pi)− log(1− pi)) + log(1− pi) <
n∑ i=1 ȳi (log(pi)− log(1− pi)) + log(1− pi)
⇐⇒ n∑ i=1 x̄i (log(pi)− log(1− pi)) < n∑ i=1 ȳi (log(pi)− log(1− pi))
⇐⇒ n∑ i=1
s.t. x̄i=1
log(pi)− log(1− pi) < n∑ i=1
s.t. ȳi=1
log(pi)− log(1− pi)
Remark. The case where πi is exactly one or zero for some i can be trivially taken into account by setting the bit to the only possible value. All outcomes that are not generated will have probability zero.

heading: B.2 ALGORITHMS
text: Algorithm 1 Multi-Bernoulli Search Data Structure - insert Require: Int n, Int M , SDSArray[M] S, RealArray[n] key, Object value
outcomes← Top-K Maximal Multi-Bernoulli Outcomes(M, n, key) for i ∈ {1, . . . , M} do
insert(Si, outcomesi, value) end for
Algorithm 2 Multi-Bernoulli Search Data Structure- search Require: Int n, Int M , Int T , SDSArray[M] S, RealArray[n] key
values← set() outcomes← Top-K Maximal Multi-Bernoulli Outcomes(T, n, key) for j ∈ {1, . . . , T} do
for i ∈ {1, . . . , M} do values← values ∪ search(Si, outcomesj)
end for end for return values
Algorithm 3 Top-K Maximal Multi-Bernoulli Outcomes Require: Int k, Int n, RealArray[n] π
1: z ← BinaryArray[n] 2: p← RealArray[n] 3: a← RealArray[n] 4: for i = 1, . . . , n do 5: if πi > 1/2 then 6: zi ← 1 7: pi ← πi 8: else 9: zi ← 0
10: pi ← 1− πi 11: end if 12: ai ← log(pi)− log(1− pi) 13: end for 14: outcomes← BinaryArray[k × n] 15: index← TopKMinimalSubsetSumIndexes(k, n, a) 16: for j = 1, . . . , k do 17: for i = 1, . . . , n do 18: if i ∈ indexesj then 19: outcomesji ← 1− zi 20: else 21: outcomesji ← zi 22: end if 23: end for 24: end for 25: return outcomes

heading: B.3 HMBS EXAMPLE
text: In this example, the number of bits in the Multi-Bernoulli is n = 3, the number of back-end data structures is M = 3, and the number of search keys is T = 2. Since this is a Hashing MultiBernoulli Search data structure, the M = 3 back-end structures will be hash tables; we will call them H1, H2 and H3.
Let say we want to insert a document with the following key,
π1 = (0.3, 0.1, 0.8).
We first need to compute its M = 3 most probable outcomes. Here they are in order:
(0, 0, 1), (1, 0, 1), (0, 0, 0)
then we will insert the document in H1 using the most probable outcome as the key, insert the document in H2 with the second most probable outcome as the key and insert the document in H3 with the third most probable outcome as the key.
Now, let say we have two other documents to insert with the following keys, respectively:
π2 = (0.7, 0.9, 0.2), π3 = (0.3, 0.2, 0.1).
Here are their M = 3 most probable outcomes, respectively:
(1, 1, 0), (0, 1, 0), (1, 1, 1) and (0, 0, 0), (1, 0, 0), (0, 1, 0).
We will then insert both of them in the M = 3 hash tables like we did for the first document.
To search in the HMBS given a query π = (0.1, 0.6, 0.2), we first need to compute its T = 2 most probable outcomes:
(0, 1, 0), (0, 0, 0).
We will then search in the M = 3 hash tables with these T = 2, doing a total of TM = 6 search in the back-end structures. These searches will find all of the three documents since the first document
is in H3 with the key (0, 0, 0), the second document is in H2 with the key (0, 1, 0) and the third document is both in H1 with the key (0, 0, 0) and in H3 with the key (0, 1, 0).
To generate documents as in the SDSL’s framework, we do not need the parameter T . However, we might want to halt before considering all possible outcomes of the query. With the same query as above, say we want to generate document but halt after the fifth hashes, i.e. after doing 5 searches in the back-end structures. We will first generate the most probable outcome (0, 1, 0) and search in H1; however, we will find nothing. We will then try the same outcome in H2 and find the second document, which we will yield. Then we will try the same outcome in H3 and find the third document, which we will yield. After this, we will compute the second most probable outcome (0, 0, 0) and search in H1 to find the third document again; thus, we will do nothing. After we will try the same outcome in H2 and find nothing. Finally, we will halt since we computed 5 hashes, ultimately never finding the first documents. Note that if there were multiple documents simultaneously, we would have yielded them together as a set.

heading: C EXPERIMENTS’ MODELS

heading: C.1 FBETA
text: For the F-beta model 4 we use ramping for the β hyperparameter using this equation,
log2 βi = { i 32−810K − 32 if i < 10K −8 otherwise
for each batch i = 0, . . . , 100K.

heading: C.2 MIHASH
text: MIHash Cakir et al. (2017) is based on the mutual information
I(X,Y ) = ∑ z∈Ω P (X=z, Y=z) log ( P (X=z, Y=z) P (X=z)P (Y=z) ) and a generalization of the Hamming distance,
d(x, y) = 1
2 (n− x · y)
for x and y in Rn. Note that if x and y are in {0, 1}n, d(2x− 1, 2y − 1) is their Hamming distance.
Lets use the above notation, i.e. let fQθ (q) = π q ∈ [0, 1]n and fUθ (d) = πd ∈ [0, 1]n be the parametric query and document functions (in the original article, they uses the same function for the queries and the documents). Let X and Y be two Multi-Bernoulli of dimension n with parameters πq and πd respectively. Finally, with H = d(2X − 1, 2Y − 1), they aim to maximize,
I(H,M(q, d))
To allow gradient descent, they use differentiable histogram binning, i.e. they approximate P (H=k | M(q, d)=1) with
P (H=k | M(q, d)=1) = 1 |I+| ∑ i∈I+ δi,k
with
δi,k = { di − (k − 1) if di ∈ [k − 1, k] (k + 1)− di if di ∈ [k, k + 1] 0 otherwise
and di = d(2πqi − 1, 2πdi − 1). Similarly they estimate P (H=k | M(q, d)=0) and P (H=k) to compute the mutual information.

heading: C.3 HASHNET
text: HashNet Cao et al. (2017) optimize an increasingly closer to discrete sequence of tasks to alleviate the challenge of solving a discrete task with differentiable methods. It is possible to frame their approach entirely with sigmoids but it is is simpler to use the tanh function as in the original article. Let NetQθ (q) = logits q ∈ Rn and NetUθ (d) = logits d ∈ Rn be the parametric query and document
functions before activation. Let gQθ (q) = tanh ( βNetQθ (q) ) and gUθ (d) = tanh ( βNetUθ (d) ) be the activated functions. Note that,
fQθ (q) = gQθ (q) + 1
2 fUθ (d) =
gUθ (d) + 1
2
For simplicity, let gQi = g Q θ (qi) and g U i = g U θ (di). In their work they modelize the matching random variable with,
M(qi, di) ∼ Ber ( σ ( α gQi · g U i )) This gives,
P (M(qi, di)=m) = σ ( α gQi · g U i )m ( 1− σ ( α gQi · g U i ))1−m Finally, they train the model with the (weighted) negative log-likelihood.
Ji = wi ( log ( 1 + exp ( α gQi · g U i )) −miα gQi · g U i ) with wi a positive real number useful when match and non-match are unbalanced. In the following experiment we ignored this term since the task is way to unbalanced and adding a weighting term would break the loss function.
The β term, in the tanh, is first set to 1 and then increased when a convergence criteria is obtain. This process repeats ten times, creating a sequence of of increasingly harder optimization which, if repeated infinitely, would converge to a discrete optimization.
lim β→∞ tanh(βx) = sign(x)
In all experiments, we use α = 0.2 for the sigmoid to have enough signal in the range [−32, 32].

heading: C.4 HAMMING RADIUS SEARCH
text: The Hamming Radius Search (HRS) is a naive approach to quickly find documents indexed with a binary code which have low Hamming distance r (the radius) to a particular binary code (the query). For insertion, we map each document’s binary code the the document using a hash table. For searching, we compute all binary codes at distance than 0 (i.e. only the query) and use the hash table, then we do the same for distance up to r, the radius.
The number a binary codes to consider grow very quickly w.r.t to the radius. For example, at radius 2 with 64 bits codes, the number of codes to consider is 2081.(
64
0
) + ( 64
1
) + ( 64
2
) = 2081
and for the radius 3 we there is 43745 codes to consider. Radius 3 would not make sense for a database of 10K elements as the last 41664 elements comes in no particular order. This is why we consider for the following experiments 2081 hash before halting for Hamming Radius Search.

heading: D SUPPLEMENTARY FIGURES
text: Figure 2: The average Hamming distance of the 25 models of each 6 HMBS models w.r.t. the positive (matching) pairs and negative (non-matching) pairs. Using the fixed 10K documents and 1K queries, creating 1K positive pairs and 9999K negative pairs for which we computed the Hamming distance.
Figure 3: The average SSWR Curves W.r.t Halt number for Fbeta, Shared-Fbeta and SHaredMIHash. The colored area is±0.01xSTD of the respective curve. The range of the y axis is changing throughout each graphs, this could be misleading when comparing the STD. As a reference, the average STD is 0.1259, 0.0374 and 0.0864 for Fbeta, Shared-Fbeta and Shared-MIHash respectively.

Review summaries:
In this paper, the authors proposed Search Data Structure Learning (SDSL), which they claim to be a generalization of the standard Search Data Structure. They also present a new metric called Sequential Search Work Ratio (SSWR) to evaluate the quality and efficiency of the search. They introduced a new loss called F-beta Loss, showing their algorithm is better than two previous results, MIHash (Cakir et al. 2017) and HashNet (Cao et al. 2017).