smallequation

$\BODY$

(1)

smallalign

$\BODY$

(2)

# Asymmetric Hashing for Fast Ranking via Neural Network Measures

Khoa Doan, Shulong Tan, Weijie Zhao, Ping Li

Cognitive Computing Lab
Baidu Research
10900 NE 8th St. Bellevue, WA 98004, USA

{khoadoan106, tanshulong2011, zhaoweijie12<EMAIL_ADDRESS>
###### Abstract

Fast item ranking is an important task in recommender systems. In previous
works, graph-based Approximate Nearest Neighbor (ANN) approaches have
demonstrated good performance on item ranking tasks with generic
searching/matching measures (including complex measures such as neural network
measures). However, since these ANN approaches must go through the neural
measures several times during ranking, the computation is not practical if the
neural measure is a large network. On the other hand, fast item ranking using
existing hashing-based approaches, such as Locality Sensitive Hashing (LSH),
only works with a limited set of measures, such as cosine and Euclidean
distance. Previous learning-to-hash approaches are also not suitable to solve
the fast item ranking problem since they can take a significant amount of time
and computation to train the hash functions due to a large number of possible
training pairs in this problem. Hashing approaches, however, are attractive
because they provide a principle and efficient way to retrieve candidate
items. In this paper, we propose a simple and effective learning-to-hash
approach for the fast item ranking problem that can be used for any type of
measure, including neural network measures. Specifically, we solve this
problem with an asymmetric hashing framework based on discrete inner product
fitting. We learn a pair of related hash functions that map heterogeneous
objects (e.g., users and items) into a common discrete space where the inner
product of their binary codes reveals their true similarity defined via the
original searching measure. The fast ranking problem is reduced to an ANN
search via this asymmetric hashing scheme. Then, we propose a sampling
strategy to efficiently select relevant and contrastive samples to train the
hashing model. We empirically validate the proposed method against the
existing state-of-the-art fast item ranking methods in several combinations of
non-linear searching functions and prominent datasets.

##  1 Introduction

The rapid growth of digital data brings plenty of opportunities but also
presents many challenges, especially in recommendation, advertising, and
information retrieval systems. In these systems, deep neural networks have
been shown to effectively capture the complex, semantic relationships between
heterogeneous objects (Severyn and Moschitti, 2015; Guo et al., 2016; Dehghani
et al., 2017; Xiong et al., 2017; Tay et al., 2018; Fan et al., 2019; Fei et
al., 2021). To obtain better model capacities, complex similarity/matching
functions–say in the forms of neural networks–are usually exploited, instead
of simple functions, such as $\ell_{2}$-distance, cosine similarity, or inner
product. However, online ranking using these advanced, non-linear similarity
functions is very challenging (Covington et al., 2016; Chen et al., 2017;
Mitra and Craswell, 2018; Chang et al., 2020; Tan et al., 2020) since it is
too time-consuming to rank all data in real-time via these complex measures.

Efficient, sub-linear ranking via neural network-based measures is called fast
neural ranking (Mitra and Craswell, 2018; Tan et al., 2020). Sub-linear time
neural ranking is considered challenging because the ranking measures (in the
forms of neural networks) are too complicated for traditional fast vector
ranking methods, i.e., approximate nearest neighbor (ANN) search algorithms.
ANN algorithms include hashing-based methods, graph-based methods, tree-based
methods, quantization-based methods, etc. (Friedman et al., 1975, 1977; Indyk
and Motwani, 1998; Broder et al., 1998; Gionis et al., 1999; Charikar, 2002;
Jégou et al., 2011; Shrivastava and Li, 2012; Datar et al., 2004; Malkov and
Yashunin, 2020; Zhao et al., 2020). Traditional ANN search methods usually
focus on some specific and simple ranking/searching measures. For example,
data-independent hashing methods are commonly used for ANN search with respect
to the cosine similarity (Goemans and Williamson, 1995; Charikar, 2002), the
chi-square similarity (Li et al., 2013), the (binary) Jaccard similarity
(Broder et al., 1998; Li and Li, 2022), and the general (real-valued) Jaccard
similarity (Manasse et al., 2010; Ioffe, 2010; Li, 2017). Recently, sub-linear
ranking under inner product becomes popular in both academic and industry, due
to its wide applications in recommendation and ads ranking. This problem is
referred to as the Maximum Inner Product Search (MIPS) (Ram and Gray, 2012;
Bachrach et al., 2014; Shrivastava and Li, 2014, 2015; Morozov and Babenko,
2018; Zhou et al., 2019). Similar to traditional ANN algorithms for fast
vector search, the MIPS methods are specially designed for the MIPS problem
and are not straightforward to extend to fast neural ranking.

To rank via neural network-based measures, Tan et al. (2020) extend the
definition of the traditional ANN search to a generic setting, called Optimal
Binary Function Search (OBFS): Let $X$ and $Y$ be subsets of Euclidean spaces,
given a data set $S=\\{x_{1},\dots,x_{n}\\}\subset X$ and a continuous binary
function (i.e., the similarity or matching function), $f:X\times
Y\to\mathbb{R}$, given $q\in Y$, OBFS aims to find:

$\displaystyle\arg\max_{x_{i}\in S}f(x_{i},q).$ (3)

In this definition, they consider an arbitrary binary function as the ranking
measure, no matter it is linear (e.g., $\ell_{2}$ or cosine) or non-linear
(e.g., a neural network). A neural network-based measure can be considered as
a special case of the binary function and the fast neural ranking problem is a
sub-problem of OBFS. Because existing ANN search methods are designed for
specific metric measures, they are not suitable to solve the OBFS task.
Furthermore, extending the existing ANN solutions to OBFS can be challenging
because they generally do not have access to the original pairwise dataset,
denoted as $\mathcal{D}_{orig}$, that is used to train $f$; for example, $f$
may be trained and provided by a third-party provider as an Off-the-shelf
product. It is impossible to re-train the ranking model.

Besides the definition, Tan et al. (2020) also provides a solution for fast
OBFS, called Search on L2 Graph (SL2G). They extend traditional graph-based
fast vector searching algorithms by constructing graph indices in the
$\ell_{2}$-distance but searching or ranking according to the binary function
$f$. SL2G is the first approximate solution for sub-linear neural ranking or
the generic OBFS problem. In SL2G, each given query is only compared with a
subset of base data instead of the whole dataset, which reduces the time
complexity significantly. Although SL2G is a sub-linear method, it is still
required to go through the ranking measure hundreds of times to promise high
retrieval recalls. For large and/or deep neural network measures (e.g., a
BERT-style model (Devlin et al., 2019; Chang et al., 2020)), such repeated
computation is not practical for online services.

This paper solves the fast neural ranking problem by learning two related hash
functions, one for the query and one for the item, whose inner product
approximates the original ranking measure $f$. Given a query, the item ranking
via $f$ is replaced with a fast ranking using the two hash functions. Hash
ranking is efficient as the distance computation is very fast, using only an
XOR and a bit count computations, each of which typically requires one CPU
cycle, in contrast to the expensive computation using the neural network
measure $f$ of SL2G. In addition, ranking over the searching data can be
performed in memory as the hash codes are memory-efficient (e.g., a million of
32-bit hash codes only occupy 4MB of memory).

Existing works in the hashing domain are typically ineffective to solve the
OBFS problem. Single-modal hashing algorithms are designed to deal with
specific measures (Broder et al., 1998; Indyk and Motwani, 1998; Gionis et
al., 1999; Charikar, 2002; Salakhutdinov and Hinton, 2009; Manasse et al.,
2010; Ioffe, 2010; Shrivastava and Li, 2012; Gong et al., 2013; Li et al.,
2013; Datar et al., 2004; Shen et al., 2015; Lin et al., 2016; Huang et al.,
2016, 2017; Li, 2017; Cao et al., 2018; Yang et al., 2018; Li and Li, 2022),
instead of arbitrary measures (i.e., $f$) such as neural networks. Other
cross-modal hashing algorithms (Jiang and Li, 2017; Li et al., 2018; Zhang et
al., 2018; Gu et al., 2019; Kang and McAuley, 2019) learn the hash functions
as part of the training process of the binary function $f$. They are not
suitable to solve the OBFS problem because, in OBFS, we cannot assume how $f$
is trained. While it is possible to enumerate a pairwise dataset, denoted as
$\mathcal{D}_{app}$, similar to $\mathcal{D}_{orig}$, from a set of queries
$q\in Y$ and a set of items $x\in S$ that are collected in the online
applications and train the hash functions using these algorithms, such
enumerations result in a large number of training instances. For example, one
million objects in each domain produce one trillion pairwise inputs. Training
hash functions on such a large number of inputs using the aforementioned
methods can lead to poor convergence of the learning process and take an
unrealistic amount of time and computation. Note that $\mathcal{D}_{orig}$ and
$\mathcal{D}_{app}$ are assumed to come from the same data distribution.

Table 1: Characteristics of potential solutions to the OBFS problem. $\times$ or ✓ indicates the method lacks or has the specific characteristic, respectively. Our FLORA satisfies all the characteristics by employing an asymmetric hashing scheme and a novel training procedure. We compare FLORA with traditional ANN, single-modal hashing, cross-modal hashing, and SL2G (Tan et al., 2020). |  | Classic ANN
---
| Single-modal
---
Hashing
| Cross-modal
---
Hashing
| SL2G
---
| FLORA
---
Works on arbitrary $f$ |  $\times$ |  $\times$ |  ✓ |  ✓ |  ✓
Not dependent on $\mathcal{D}_{orig}$ |  ✓ |  ✓ |  $\times$ |  ✓ |  ✓
Ranking without $f$ |  ✓ |  ✓ |  ✓ |  $\times$ |  ✓

To address the above limitations of the existing methods for the fast neural
ranking problem, in this paper, we propose FLORA, a Fast Learning tO RAnk
method. The advantages of FLORA over the potential solutions for the OBFS
problem are shown in Table 1. FLORA’s hashing model learns two related hash
functions to map objects from two heterogeneous domains to discrete
representations whose inner product captures the objects’ similarity defined
by the binary function $f$. Specifically, we reduce the ranking problem via
the original binary function $f$ to an approximate nearest neighbor search via
an asymmetric pair of hash functions. The model is asymmetric in the sense
that one hash function is used to preprocess the data in the database (e.g.,
items), while the other hash function is used to transform the query (e.g., a
user). This framework can approximate any form of the binary function. To
train the hash functions, we propose a novel sampling strategy that
efficiently picks input pairs out of the large number of all possible pairs
($n_{1}\times n_{2}$) so that the model training converges faster to a good
performance.

In summary, the contributions of this paper are as below:

  * •

Propose a hashing neural network that captures the relationship of the
heterogeneous objects through a pair of asymmetric hash functions. The
proposed model is learned to preserve the semantic similarity of the inputs
defined by the binary function and to generate balanced hash codes via three
novel objective functions.

  * •

Propose a novel strategy to efficiently and effectively sample data pairs to
accelerate the training process and find better local optima of the model.

  * •

Demonstrate the effectiveness of FLORA on various complex neural network-based
matching functions and several benchmark datasets used in the recommendation
domain. FLORA produces rankings with higher recalls and is significantly
better in both computation and space, compared to existing methods.

Paper organization. In Section 2, we review the fast neural ranking problem
and its potential solutions. Then we introduce the proposed hashing method,
FLORA, for the fast neural ranking problem. In Section 4, we study three
complex ranking measures and conduct experiments. The entire paper is
concluded in Section 5.

##  2 Related Work

In this section, we will first introduce some classic neural network-based
ranking models and their applications. Then, the fast neural ranking problem
will be reviewed in the context of the general top-k search. Finally, we will
discuss some potential solutions for fast neural ranking and explain their
limitations, then motivate the proposed methodology.

###  2.1 Neural Network-based Ranking Models

Recently, neural network-based models have been proposed for the ranking
problems such as recommendation, information retrieval, ads ranking, and
retrieval-based question answering (Xiong et al., 2017; Chen et al., 2017;
Devlin et al., 2019; Fan et al., 2019; Huang et al., 2019). Neural network-
based representation learning models (Huang et al., 2013; Shen et al., 2014;
Xue et al., 2017; Zamani et al., 2018; Sun et al., 2018) show superior
performance in feature learning. Heterogeneous objects can be embedded from
their raw feature spaces into a common latent space. In this space, different
objects (e.g., users and items, questions and answers) can be compared by some
classic measures, such as cosine, $\ell_{2}$ distance, or inner product.

To achieve even greater capacities in modeling complicated relationships
between heterogeneous objects, previous works try to learn meaningful matching
functions (so-called matching function learning), especially in forms of deep
neural networks (Lu and Li, 2013; Severyn and Moschitti, 2015; Dehghani et
al., 2017; Xiong et al., 2017; Tay et al., 2018), instead of the classic
measures. These works assume that there exists a mapping that can capture the
complicated relationship (e.g., non-linear and non-convex) between
heterogeneous objects. Therefore, the goal of matching function learning is to
learn the mapping by well-designed models. For the matching models (i.e.,
matching functions to be learned), Multi-Layer Perceptrons (MLPs) are commonly
adopted (Severyn and Moschitti, 2015; Dehghani et al., 2017; Tay et al., 2018;
Yu et al., 2022). Recently, BERT-style models are widely used for language
modeling (Devlin et al., 2019; Chang et al., 2020). It has been shown that
matching function learning methods outperform simple representation learning
methods in complicated ranking tasks (Xu et al., 2020).

###  2.2 Fast Neural Ranking

For online ranking services, search efficiency is as important as search
effectiveness. Fast search algorithms construct some forms of index structures
in advance in order to accelerate the online search, such as the inverted
index for free text and LSH tables for vector data. Traditional fast search
problems restrict the searching measures to metric measures (e.g., $\ell_{2}$
distance) or some simple non-metric measures, such as inner product (which is
widely exploited in recommender systems).

OBFS (i.e., Eq. (3)) (Tan et al., 2020) is a generic definition for fast
top-$K$ search. Theoretically, an OBFS task can choose any binary function as
the search measure, whether it is linear or non-linear, metric or non-metric,
convex or non-convex, or symmetric or asymmetric. Traditional ANN search and
MIPS are special cases of OBFS. Recently, neural network-based ranking
measures (Guo et al., 2016; Lu and Li, 2013; Dehghani et al., 2017; Chang et
al., 2020) increasingly become popular examples of searching binary functions,
as introduced in Section 2.1. These kinds of neural network-based searching
functions are usually non-convex. In this paper, we focus on the generic, fast
OBFS problem, especially the so-called fast neural ranking problem of how to
speed up the searching process under neural network-based measures for online
ranking services.

The Search on L2 Graph (SL2G) (Tan et al., 2020) is designed for the generic
fast OBFS problem. The basic idea of SL2G is: no matter what the given binary
function $f$ is, they construct a Delaunay graph (or an approximate one) with
respect to the $\ell_{2}$ distance in the indexing step; the $\ell_{2}$
distance is defined on searching/base data $X$ and is, therefore, independent
of the queries. Then SL2G performs the greedy search on this graph via the
binary function $f$ at query time. To achieve higher recalls, SL2G must invoke
the ranking function hundreds of times. For such reason, SL2G is not practical
when the binary functions are complex networks.

###  2.3 Learning to Hash

Existing supervised hashing approaches (Shen et al., 2015; Yang et al., 2018;
Cao et al., 2018; Gui and Li, 2018; Jiang and Li, 2018; Doan et al., 2022,
2020) are designed to deal with ANN search. Most of these methods assume that
query and database objects are homogeneous (e.g., both are images), but the
matching function may have heterogeneous pair of inputs (e.g., user and item).
While cross-modal hashing approaches (Jiang and Li, 2017; Li et al., 2018;
Zhang et al., 2018; Gu et al., 2019; Kang and McAuley, 2019) learn the hash
functions for heterogeneous objects, they are designed to use pairwise
annotated training data. To employ these methods for the OBFS problem, we need
to enumerate the pairwise data using the binary function $f$ and the separate
sets of queries (i.e., users) and database (i.e., items) since we do not have
access to the original pairwise training data that is used to train $f$. Such
enumerations can result in a large number of training instances ($n_{1}\times
n_{2}$; e.g., 1 million users and 1 million items results in one trillion
training instances), which makes it impractical to train these models.

##  3 Fast Neural Ranking with Hashing

We solve the fast neural ranking problem by learning low-dimensional discrete
hash codes whose distances approximate the original similarity measure defined
by the continuous binary function $f$. The basic idea of FLORA is: 1) no
matter what binary function $f$ is, we can always learn a pair of related hash
functions $H_{1}$ and $H_{2}$ that together approximate the similarity defined
by $f$ and 2) exact searching using $f$ is reduced to approximate searching in
the discrete space using the distance between the discrete outputs of $H_{1}$
and $H_{2}$; this searching approach avoids the possibly complex and expensive
computation of the original binary function $f$.

Next, we describe how the hash functions $H_{1}$ and $H_{2}$ are learned, and
how the trained hash functions are used for fast neural ranking.

###  3.1 Hash Function Learning

Figure 1: FLORA learning-to-hash network. Item vectors and user vectors are
the inputs. These vectors are different from raw features in original pairwise
dataset, $\mathcal{D}_{orig}$.

The input of the binary function $f$ consists of two domains (for example, the
user and item domains in recommendation applications). In OBFS, we are given a
trained binary function $f$ that computes the similarity between a user and an
item.

To approximate $f$, FLORA represents each user $u$ and item $v$ using two
separate hash functions, denoted by $H_{1}:u\rightarrow\\{-1,1\\}^{m}$ and
$H_{2}:v\rightarrow\\{-1,1\\}^{m}$, respectively, where $m$ is the dimension
of the discrete spaces (i.e., the number of bits). To model the relationship
between $H_{1}$ and $H_{2}$, we extend the two-tower neural network by
incorporating a set of shared embedding layers, as presented in Figure 1. Each
user input and item input first go into two separate MLP networks, denoted as
$g_{1}$ and $g_{2}$, respectively, to extract the appropriate features for
each domain. Then, the extracted features are embedded into the same discrete
space through a shared MLP network, denoted as $g_{0}$. Equivalently,
$H_{1}=g_{0}\circ g_{1}$ and $H_{2}=g_{0}\circ g_{2}$. In this space, the
relationship between two objects is defined via the cosine similarity, which
is also linearly related to their Hamming distance. This model can learn to
extract different representations of the two domains while finally capturing
high-order interactions between the two objects in the common discrete space.

The objective function of FLORA consists of three parts. The first part,
denoted as $\mathcal{L}_{c}$, is the consistency loss that penalizes the
difference between the predicted similarity score computed in the discrete
space and the target similarity score defined by the binary function $f$. The
consistency loss is defined as follows:

$\mathcal{L}_{c}=E_{u,v}||f(v,u)-cosine(H_{1}(u),H_{2}(v))||_{2}$ (4)

where $cosine(H_{1}(u),H_{2}(v))=H_{1}(u)\cdot H_{2}(v)/2m+0.5$, since
$H_{1}(u)$ and $H_{2}(v)$ are binary vectors. Without loss of generality,
assuming $f(v,u)\in[0,1]$, this can be thought of as a problem of inner
product fitting with binary codes computed through the two hash functions.
This formulation essentially establishes an asymmetric hashing scheme because
the hash function $H_{1}$ is applied on the user (query) while a different
hash function $H_{2}$ is applied on the items (in the database). These hash
functions are jointly learned so that their discrete inner product fits the
similarity structure defined by the binary function $f$. Note that this is
different from asymmetric MIPS algorithms, e.g., Shrivastava and Li (2014),
which are linear and are designed for some specific non-metric measures. In
contrast, via inner product fitting, FLORA can learn a pair of non-linear hash
functions whose inner product, and equivalently Hamming distance,
approximately reveals the true similarity given by any definition of $f$.

The discrete-optimization objective in Eq. (4) is computationally intractable
to solve. Therefore, we replace the discrete optimization with a continuous
relaxation where the last layers of the hash functions approximate the
discrete constraint using the $tanh$ activation. Specifically, given the
continuous function $h_{1}:u\rightarrow[-1,1]^{m}$ and
$h_{2}:v\rightarrow[-1,1]^{m}$ whose last layers are with the $tanh$
activation, the consistency loss is as follows:

$\mathcal{L}_{c}=E_{u,v}||f(v,u)-cosine(h_{1}(u),h_{2}(v))||_{2}$ (5)

Besides the consistency objective, the model also needs to learn balanced hash
codes for optimal searching (Doan and Reddy, 2020). First, we need to prevent
collapsed bits. This happens when the training algorithm fails to learn a
specific bit, and thus it assigns most examples into the same bit value.
Intuitively, this means that the data points should be uniformly distributed
into the hash codes in the discrete space. To achieve balanced codes, we
propose to solve two additional objectives. The first term $L_{u}$ encourages
half of the points to be assigned to either $-1$ or $1$, and can be defined as
follows:

$\mathcal{L}_{u}=\sum_{k=1}^{m}\big{|}\sum_{i=1}^{n_{1}}h_{1,k}(u_{i})\big{|}_{1}+\big{|}\sum_{j=1}^{n_{2}}h_{2,k}(v_{j})\big{|}_{1}$
(6)

where $h_{1,k}$ and $h_{2,k}$ represent the $k$th output components of $h_{1}$
and $h_{2}$, respectively. The final objective discourages different bits to
learn correlated information of the data. Essentially, the projection of the
data points onto the discrete space should be an orthogonal projection. This
objective, denoted as $\mathcal{L}_{i}$, is defined as follows:

$\mathcal{L}_{i}=||W_{h_{1}}^{T}W_{h_{1}}-I||_{2}+||W_{h_{2}}^{T}W_{h_{2}}-I||_{2}$
(7)

where $W_{h_{1}}$ and $W_{h_{2}}$ are the parameter matrices at the last
layers of the hash functions $h_{1}$ and $h_{2}$, respectively. Since $h_{1}$
and $h_{2}$ share their last layers, we have $W_{h_{1}}=W_{h_{2}}$. The
overall objective function of FLORA is a combination of the consistency loss,
uniform frequency loss, and independent-bit loss, as follows:

$\mathcal{L}=\mathcal{L}_{c}+\lambda_{u}\mathcal{L}_{u}+\lambda_{i}\mathcal{L}_{i}$
(8)

where $\lambda_{u}$ and $\lambda_{i}$ are parameters to balance the losses.
Optimizing $\mathcal{L}$ learns two hash functions $h_{1}$ and $h_{2}$ that
generate balanced hash codes and together preserve the similarity structure
defined by the binary function $f$ in an asymmetric hashing scheme.

###  3.2 Hash Function Training

Training the model in FLORA is not a trivial task, mainly because
$\mathcal{D}_{orig}$ is generally not available. There are several challenges
when the training process can only access the binary function (possibly
without the knowledge of its internal structure) and the input features of the
two domains. The number of possible training input pairs, i.e., $n_{1}\times
n_{2}$, can be extremely large, which requires a significant amount of
training time and computation. Furthermore, in a typical recommendation or
retrieval setting, the number of “relevant” items for each user is often very
small. Consequently, a large number of user-item data pairs do not contain
useful signals to train the model and can even make the training process more
difficult to converge into a good local optimum.

Figure 2: FLORA’s sampling strategy for model training, compared to other
possible sampling strategies.

It is crucial that the FLORA framework needs an efficient training approach,
i.e., an efficient sampling of $\mathcal{D}_{app}$. One natural option is to
randomly sample the pairs for training, as depicted in Option 1 in Figure
2(a). However, as later shown in Section 4, this procedure does not work well.
To achieve good retrieval performance, the hash functions need to agree on the
relevant, positive user-item pairs while disagreeing on the negative user-item
pairs. Randomly sampling the pairs does not increase the chance of the
relevant data pairs being selected, thus it may take a large number of
training steps to adequately iterate over these relevant pairs. Inspired by
this observation, we propose two efficient sampling strategies.

Let $N_{p}$ be the number of top $N_{p}$ items (w.r.t the original binary
function $f$) of a user. In training, for a user, we select an item to form
the user-item input as follows: with a probability $p$, we select an item from
the top $N_{p}$ items (called the positive set), and with probability $1-p$,
we select an item from the set of remaining items (called the negative set).
Generally, $p$ is set to $0.5$ to allow uniform selections of the positive and
negative items, thus, hereafter, we assume $p=0.5$. Note that, $N_{p}$ is
small for real-world applications, where a user is typically interested in a
small number of items. Given this sampling setup, selecting an item from the
top $N_{p}$ items is trivial because $N_{p}$ is small. Sampling from the
negative set can be done uniformly (illustrated in Option 2 in Figure 2(b)).

While this strategy provides some noticeable improvement over Option 1, we
empirically show that the second proposed strategy (Option 3) results in even
faster training convergence and a significantly better fast ranking
performance. In Option 3 (illustrated in Figure 2(c)), a negative item is
sampled as follows: an item in the negative set is selected with a probability
inversely proportional to their rank in the set. There are two reasons that
this strategy results in faster training and better performance than the other
procedures. First, items on the top of the negative set’s ranked list have
more chance of being selected; these items are more likely to provide a
relevant signal to train the model than the items near the end of the ranked
list. Second, items near the end of the ranked list still have a chance of
being selected; these negative items can provide useful signals for the model
to push the hash codes of relevant items of a user away from those of
irrelevant items during training.

For each proposed sampling option, the pairs are repeatedly sampled to form
the minibatches. Then, FLORA’s hashing model is trained on the sampled
minibatches with stochastic optimization.

###  3.3 Fast Ranking with FLORA

After the two hash functions are learned, ranking in FLORA is conducted in the
learned discrete space using an asymmetric hashing scheme. The hash codes of
the query $q$ and the item $x$ are $H_{1}(q)=sign(h_{1}(q))$ and
$H_{2}(x)=sign(h_{2}(x))$, respectively. The hash code of the query is
typically computed online via $H_{1}$, while the items’ hash codes can be pre-
computed using $H_{2}$ and serve as an indexing structure (i.e., the hash
table) for fast retrieval. There are two strategies to perform fast retrieval
of the items. Given a query, the first strategy is to enumerate the hash codes
within a Hamming ball of the query and use them for probing candidate items
with the same hash codes in the hash table. This works well when there exist
candidate items within a short Hamming distance to the query; otherwise, a
large number of hash codes must be enumerated in order to probe candidate
items.

The second strategy leverages the fact that the hash codes are low-
dimensional, discrete objects and can be operated efficiently in both
computation and memory. The size $m$ of the hash codes is often between 32 to
128 bits (equivalent to the size of 1 to 3 integers, respectively). Therefore,
the entire set of pre-computed, discrete hash codes of the items can be
efficiently kept in memory (e.g., a million 32-bit hash codes result in 4MB of
memory), and the distance calculation can be extremely fast (i.e., using one
XOR and one bit-count operation, each of which typically takes 1 CPU cycle, to
compute the Hamming distance). The approximate ranking is performed via the
Hamming distances calculated between the query’s hash code and the set of pre-
computed items’ hash codes. As we shall show later, this ranking is fast and
achieves a superior approximation of the exact ranking using the original
binary function on all datasets. Note that with other approaches, especially
the SL2G method (Tan et al., 2020), it becomes prohibitively slow when the
binary neural function $f$ is complex and the required number of retrieved
items grows because each traversal in these ANN index structures requires a
more expensive computation on the binary function.

##  4 Experiments

We evaluate the performance of FLORA in the fast ranking task under different
combinations of generic searching measures $f$’s and datasets in the
recommendation and advertising domains. It is important to note that the
comparison of the neural network-based recommendation models (i.e., $f$) is
beyond the scope of this paper. The measures $f$’s are pre-trained on the
respective datasets, and our evaluation only focuses on the fast item ranking
procedure.

###  4.1 Neural Network-based Ranking Measures

Figure 3: Two variants of the MLP models for recommendation and a Deep&Wide
variant, DeepFM, also for recommendation.

We leverage three popular neural network models in recommendation and
advertising. The first two MLP models, MLP-Concate and MLP-Em-Sum, were used
in (Tan et al., 2020) to evaluate the fast neural ranking methods. MLP-Concate
concatenates user latent vectors and item latent vectors before they go
through the MLP network (Figure 3 (a)). MLP-Em-Sum transforms the
heterogeneous vectors from the two domains into a common embedding space
before the merge operation (Figure 3 (b)). Consequently, user vectors and item
vectors will lie on the same manifold on which element-wise sum will be
operated. The third model, DeepFM (Guo et al., 2017), adopts the popular
Wide&Deep architecture with a separate factorization-machine layer and an MLP.
DeepFM has been shown to be able to learn low and high-order feature
interactions simultaneously from the raw input and demonstrates good
performance in both recommendation and click-through-rate prediction tasks.

###  4.2 Datasets

We choose three widely used datasets for recommendation:
Yelp111https://www.Yelp.com/dataset/challenge,
AmazonMovie222http://jmcauley.ucsd.edu/data/amazon (Amovie) and
Movielens-20M333https://grouplens.org/datasets/movielens/20m (Movielens). The
Yelp dataset is pre-processed and contains 25,677 users, 25,815 items, and
731,670 ratings. For Amovie, we remove the users with less than 30
interactions. This results in 7,748 users, 104,708 items, and 746,397 ratings.
Finally, for Movielens, we randomly select 25,000 users from the original
dataset of 20 million ratings, created by 138,000 users on 27,000 movies. The
resulting Movielens dataset contains 18,799 movies, and 3,670,197 ratings.
Note that the number of ratings in Movielens is significantly larger than
those in Amovie and Yelp. There are also more ties on top ranking (w.r.t $f$)
in Movielens than in the other datasets. Note that, the rating data constitute
the original pairwise dataset $\mathcal{D}_{orig}$ that is used to train $f$.

We train MLP-Concate and MLP-Em-Sum on Yelp and Amovies, and DeepFM on
Movielens to learn the corresponding neural functions. After training, we
freeze the weights of the models; the frozen models become the binary function
$f$’s. For each pair of user and item input vectors, the binary function $f$
outputs a similarity score between 0 and 1. Note that, for all models, only
the networks above the vector combination (i.e., the part within the dashed
boxes in Figure 3) are regarded as the matching function. The dimensions of
the input vectors for MLP-Em-Sum, MLP-Concate and DeepFM are set as 64, 32,
and 100, respectively.

Note that after training $f$, to ensure a general OBFS setting, we assume that
the dataset $\mathcal{D}_{orig}$ becomes unavailable. Only the two separate
sets of queries and database items (i.e., users and items, respectively) in
each of the three datasets are available to train the model or build the
ranking index in the OBFS solutions. In other words, sampling the pairs of
users and items from these two separate sets induces $\mathcal{D}_{app}$. For
each dataset, we first randomly sample 1,000 users for testing. The remaining
users are used for learning the hash functions.

###  4.3 Comparison Methods

We compare FLORA against two state-of-the-art methods for traditional ANN
search, ANNOY and HNSW (Malkov and Yashunin, 2020; Zhao et al., 2020), the
hashing-based recommendation approach, CIGAR (Kang and McAuley, 2019), that
uses pairwise/implicit feedback data for candidate ranking, and the current
state-of-the-art for fast neural ranking, SL2G. ANNOY mainly focuses on metric
measures. Similar to (Tan et al., 2020), we first retrieve the candidates by
ANNOY via $\ell_{2}$-distance (here, user vectors and item vectors are
required to have the same dimension), then re-rank the candidates via the
searching measure $f$. We modify HNSW for neural-network binary functions as
follows: we calculate $f(x,x)$ for a pair of item vectors forcibly. Then, we
use the value of $f(x,x)$ as the relevance measure to construct the index
graph by HNSW algorithm. This index-graph construction may be dramatically
different from the Delaunay graph with respect to $f(x,q)$; thus, there is no
performance guarantee. Note that we use the same dimension for the users and
items so that the modified HNSW can be implemented; otherwise, $f(x,x)$ cannot
be computed. CIGAR trains the candidate-ranking hash function using the
original pairwise rating dataset (i.e., $\mathcal{D}_{orig}$). However, since
we do not have such a dataset in OBFS, we first randomly sample a pair of
users and items and calculate the corresponding rating using $f$. This process
essentially produces $\mathcal{D}_{app}$, which is used to train the CIGAR’s
hash functions. SL2G and FLORA have no such limitations.

Note that it is not possible to evaluate most hashing approaches (Gionis et
al., 1999; Gong et al., 2013; Shen et al., 2015; Yang et al., 2018; Cao et
al., 2018; Huang et al., 2017; Lin et al., 2016; Huang et al., 2016;
Salakhutdinov and Hinton, 2009) in this work since these methods are designed
for specific measures, e.g., $\ell_{2}$, instead of arbitrary measures such as
neural networks. Evaluating cross-modal hashing approaches (Jiang and Li,
2017; Li et al., 2018; Zhang et al., 2018; Gu et al., 2019; Kang and McAuley,
2019) is also very difficult since the required $\mathcal{D}_{orig}$ is not
available. Nevertheless, we provide comparisons with CIGAR (Kang and McAuley,
2019), a representative cross-modal retrieval method that can perform
candidate ranking by learning a hash function.

Implementation Details: The asymmetric hashing network in FLORA is implemented
with Multilayer Perceptrons (MLPs). Each user or item tower is an MLP with two
layers (256-256). The shared MLP consists of two layers of 128 and $m$ units,
where $m$ is the dimension of the hash codes. Typically, higher numbers of
bits result in better retrieval performance but also increase the computation
in both training and retrieval; thus we set $m=128$, which has been previously
shown to achieve the best retrieval performance with acceptable computational
efficiency (Cao et al., 2018; Huang et al., 2017; Lin et al., 2016; Huang et
al., 2016; Salakhutdinov and Hinton, 2009; Zhang et al., 2018; Gu et al.,
2019; Kang and McAuley, 2019). We use small grid search in $\\{0.1,1,10\\}$
for both $\lambda_{u}$ and $\lambda_{i}$ and set the optimal value for each
dataset using a corresponding validation user set (10% of the training users).

###  4.4 Evaluation Metrics

We first generate the ground-truth labels by calculating the most relevant
items for each user via the learned binary function $f$. Similar to Tan et al.
(2020), we perform experiments on Top-10 and Top-100 labels. In Top-10 (or
Top-100), an item is relevant to the query if it is one of the top 10 (or top
100) items in the ground-truth ranking computed using $f$. Since we focus on
the fast ranking task, the main evaluation metric is recall; we do not
evaluate the methods on the precision. The recall values are calculated up to
200 retrieved items, a typical range for the ranking tasks in real-world
applications.

Since fast ranking with our hashing approach is very different from the
existing ANN searching algorithms, suitable evaluation approaches should be
used. If we compare FLORA against the baselines in metrics such as Recall
versus Time (i.e., how many times the algorithm can speed up over naive brute
force scanning at each recall level), FLORA will have an unfair advantage over
the baselines since each distance computation in FLORA (in the discrete space)
is significantly faster than each distance computation in the baselines (via
the binary function $f$). Therefore, we focus our evaluation of the methods on
their ranking qualities via the recall performance. This way, when FLORA
achieves good recall performance, we can confidently conclude that FLORA is
significantly fast and produces a better approximate ranking for the OBFS
problem with $f$.

###  4.5 Ranking Performance Results

We show the recall performance at various retrieval thresholds of the methods
for the Top-10 and Top-100 retrievals on Yelp and Amovies datasets in Figure 4
and Figure 5, respectively. Additionally, we present the Top-10 and Top-100
results for SL2G and FLORA on the Movielens dataset in Figure 6. As can be
seen, both ANNOY, a metric-measure ANN method, and the modified HNSW are not
able to retrieve the most relevant items. CIGAR’s retrieval performance is
also significantly worse than FLORA’s performance.

Figure 4: Top-10 recall results at different retrieval thresholds for MLP-
Concate and MLP-Em-Sum.

Figure 5: Top-100 recall results at different retrieval thresholds for MLP-
Concate and MLP-Em-Sum.

Figure 6: Top-10 and Top-100 recall results at different retrieval thesholds
for DeepFM on Movielens.

Previously, Tan et al. (2020) show that SL2G achieves both significantly
better ranking performance, which we also observe in this paper, and
computational speed compared to these ANN methods. However, FLORA consistently
outperforms SL2G in the experiments on all datasets, especially at the top of
the ranking list.

Next, we present some observations, along with important conclusions about the
difference between FLORA and other methods:

  * •

Existing hashing-based methods are not suitable to solve the OBFS problem. The
main challenge in adapting these methods is their training efficiency when we
do not have access to $\mathcal{D}_{orig}$ and have to rely on the huge
$\mathcal{D}_{app}$, which consists of all possible user-item pairs. For
example, the sizes of the enumerated $\mathcal{D}_{app}$ for Yelp, Amovie, and
Movielens are approximately 662 millions, 811 millions and 469 millions,
respectively. Later, we empirically demonstrate how FLORA overcomes this
challenge with the proposed sampling approach in Section 4.8.

  * •

FLORA exhibits significantly better early-rise recalls compared to SL2G, even
though it performs the fast ranking in the compact, discrete space. As
discussed, ranking in the discrete space is extremely fast, where each
distance calculation is hundreds to thousands of times faster than the
computation on the original binary function $f$. The item ranking can also be
performed in memory. This is not possible with the compared baselines.

  * •

While FLORA’s recall curves approach those of SL2G at the end of the ranking
lists in a few cases, the superior results of FLORA are still significant as
the preferred retrieval sizes in real applications are typically no more than
a few hundred items (also for such reason, we select 200 in the experiments).
Furthermore, since FLORA is based on hashing, we can systematically improve
its recalls by employing multiple hash tables, as will be discussed later.

  * •

When the binary function is DeepFM, we observe that the ranking computation of
SL2G, which involves several iterations over the binary function to compute
the distances, becomes too slow to be practical. In contrast, FLORA’s ranking
computation, performed in the discrete space, is nearly constant in all
experiments.

###  4.6 Exact Retrieval with Neural Function Re-ranking

FLORA ranks the items in the discrete space. This procedure has a trade-off:
more items than required are sometimes returned if there are ties at the
specified threshold in the ranking list. Suppose we want to retrieve only 1
item for a user; FLORA may instead return multiple candidate items if these
items have the same shortest Hamming distance to the user. Therefore, a re-
ranking step is needed to retrieve exactly 1 item. The re-ranking step can be
performed using $f$. Note that invoking $f$ in re-ranking makes FLORA
computationally similar to other ANN methods. However, we will empirically
show that the performance of the discrete-space ranking (i.e., FLORA) closely
resembles the performance of the ranking procedure that combines FLORA and a
re-ranking step (denoted as FLORA-R).

Figure 7: Top-10 Recall results of FLORA with and without the Re-ranking step.

Figure 7 shows the recall values at different retrieval percentages of the
items for FLORA and FLORA-R. In FLORA-R, if there are ties at a specific
threshold in the ranking list, the percentage is calculated using the size of
the list that includes all the ties. Consequently, FLORA-R is expected to be
always better than FLORA. As can be observed, there is not a noticeable
difference between the two recall curves. This means that the discrete space
ranking can be reliably used without access to the binary function $f$.

###  4.7 Improving Recall with More Hash Tables

Figure 8: FLORA with multiple hash tables: Top-10 recall and False Positive
Rate of the candidates within radius-0 of the query.

A principled approach to improve the probability of the relevant items in the
candidate list is to employ multiple hash tables. Figure 8 shows the recall of
the candidate items and their corresponding False Positive Rate (FPR) as
multiple tables are used. We find candidate items whose hash codes are within
distance 0 of the queries.

As can be observed, the recall steadily increases as more hash tables are
used. While FPR is expected to increase with more tables, empirically, we
observe that it only increases slightly after 2 or more tables are used. This
feature of FLORA is an advantage over other methods. In practice, we can
employ multiple hash tables to reach the desired recall rate.

###  4.8 Effect of Sampling on Performance

Figure 9: Effect of Sampling Strategies in FLORA

We discuss the importance of an effective sampling strategy in training.
Figure 9 shows the recall performance of different strategies. Rand refers to
random selection of training pairs (Option 1 in Figure 2(a)). Rand- refers to
Option 2 in Figure 2(b), where the positive list contains 10 items and the
negative list has the remaining items; each list is randomly selected with
probability 0.5, and items in the negative list are uniformly selected.
Finally, the remaining experiments employ Option 3 in Figure 2(c), where
$N_{p}$ denotes the size of the positive list; items in the negative list are
selected with probability proportional to their similarity scores (with
respect to the user) defined by binary function $f$. The recall of Rand is
significantly worse than the other strategies. While Rand- improves the recall
performance over Rand, it is more effective to adopt the proposed Option 3
(Figure 2(b)). Furthermore, as we shall show later, this strategy allows the
training process to quickly reach the optimal model.

###  4.9 Ablation Study

Figure 10: Recalls for different variants of the objectives.

We quantify the performance gains with respect to various objectives in FLORA
through an ablation study. Figure 10 shows the recall performance for
different variants of the loss function, as proposed in Eq. (8). Without
enforcing uniform frequency and independent bits, the recall performance drops
significantly ($L_{c}$). Adding uniform frequency ($L_{c}+L_{u}$) results in a
performance closer to that of the final model. While adding independent bits
to $L_{c}$, resulting in the model $L_{c}+L_{i}$, does not result in a
noticeable performance gain, the presence of $L_{i}$ in the final model (Eq.
(8)) improves the recall as the size of the retrieval list grows.

We conjecture that uniform frequency ensures that hash code learning does not
fall into a collapsed-bit solution, where the training process fails to learn
a specific bit, and thus it assigns most examples into the same bit value.
While this is not necessarily serious, especially when the chosen size of the
hash codes is large, this worsens the efficiency of the method because this
means that similar performance can be achieved with smaller hash codes.

###  4.10 Training Efficiency

Figure 11: Recalls during model training.

We present the recall performance during the model training in Figure 11. As
can be observed, after 20,000 iterations, the models have already approached
the optimal performance. Compared to the results of RAND and RAND- in Figure
9, the proposed sampling strategy (Option 3 in Figure 2) is significantly more
efficient in selecting relevant pairs for training. In practice, while there
is a trade-off between training time and ranking performance in the other
sampling strategies, even at a shorter training time, FLORA’s proposed
sampling strategy allows us to reach the optimal model in a significantly
shorter amount of time.

##  5 Conclusion

In this paper, we studied the fast neural ranking problem and proposed an
approximate fast ranking framework, FLORA, based on an asymmetric hashing
scheme. The proposed FLORA framework learns a pair of hash functions for two
heterogeneous domains(e.g., users and items). The hashing model learns to
preserve the original similarity of the heterogeneous objects through inner
product fitting of the corresponding binary codes produced by the hash
functions. Under this learning objective, the inner product, or equivalently
the Hamming distance, of the learned binary codes can approximately reveal the
true similarity defined by any binary function, including complex neural
network functions.

Then, we propose an efficient sampling procedure to accelerate the training
process and find better local optima of the proposed hashing model in FLORA.
This procedure divides the items into two lists, positive and negative, where
we first pick each list with equal probability, then an item in the negative
list is selected with a probability inversely proportional to their rank
defined by the neural network-based function, $f$.

Finally, we evaluate FLORA on several benchmark recommendation datasets and
neural network functions with different levels of complexity. FLORA is
significantly better than existing approaches in both computation and ranking
performance. We believe that FLORA can be used for other challenging problems
which require a fast ranking phase, such as retrieval based question answering
models. However, we leave this for future work.

## References

  * Bachrach et al. [2014] Yoram Bachrach, Yehuda Finkelstein, Ran Gilad-Bachrach, Liran Katzir, Noam Koenigstein, Nir Nice, and Ulrich Paquet.  Speeding up the xbox recommender system using a Euclidean transformation for inner-product spaces.  In _Proceedings of the Eighth ACM Conference on Recommender Systems (RecSys)_ , pages 257–264, Foster City, CA, 2014.
  * Broder et al. [1998] Andrei Z. Broder, Moses Charikar, Alan M. Frieze, and Michael Mitzenmacher.  Min-wise independent permutations.  In _Proceedings of the Thirtieth Annual ACM Symposium on the Theory of Computing (STOC)_ , pages 327–336, Dallas, TX, 1998.
  * Cao et al. [2018] Yue Cao, Bin Liu, Mingsheng Long, and Jianmin Wang.  HashGAN: Deep learning to hash with pair conditional wasserstein GAN.  In _Proceedings of the 2018 IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ , pages 1287–1296, Salt Lake City, UT, 2018.
  * Chang et al. [2020] Wei-Cheng Chang, Felix X Yu, Yin-Wen Chang, Yiming Yang, and Sanjiv Kumar.  Pre-training tasks for embedding-based large-scale retrieval.  In _Proceedings of The International Conference on Learning Representations (ICLR)_ , 2020.
  * Charikar [2002] Moses S Charikar.  Similarity estimation techniques from rounding algorithms.  In _Proceedings of the Thiry-Fourth Annual ACM Symposium on Theory of Computing (STOC)_ , pages 380–388, Montreal, Canada, 2002.
  * Chen et al. [2017] Danqi Chen, Adam Fisch, Jason Weston, and Antoine Bordes.  Reading wikipedia to answer open-domain questions.  In _Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics (ACL)_ , pages 1870–1879, Vancouver, Canada, 2017\.
  * Covington et al. [2016] Paul Covington, Jay Adams, and Emre Sargin.  Deep neural networks for youtube recommendations.  In _Proceedings of the 10th ACM Conference on Recommender Systems (RecSys)_ , pages 191–198, Boston, MA, 2016.
  * Datar et al. [2004] Mayur Datar, Nicole Immorlica, Piotr Indyk, and Vahab S Mirrokni.  Locality-sensitive hashing scheme based on p-stable distributions.  In _Proceedings of the Twentieth Annual Symposium on Computational Geometry (SCG)_ , pages 253–262, Brooklyn, NY, 2004.
  * Dehghani et al. [2017] Mostafa Dehghani, Hamed Zamani, Aliaksei Severyn, Jaap Kamps, and W. Bruce Croft.  Neural ranking models with weak supervision.  In _Proceedings of the 40th International ACM SIGIR Conference on Research and Development in Information Retrieval (SIGIR)_ , pages 65–74, Shinjuku, Tokyo, 2017.
  * Devlin et al. [2019] Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova.  BERT: pre-training of deep bidirectional transformers for language understanding.  In _Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies (NAACL-HLT)_ , pages 4171–4186, Minneapolis, MN, 2019.
  * Doan and Reddy [2020] Khoa D. Doan and Chandan K. Reddy.  Efficient implicit unsupervised text hashing using adversarial autoencoder.  In _Proceedings of the Web Conference (WWW)_ , pages 684–694, Taipei, 2020.
  * Doan et al. [2020] Khoa D Doan, Saurav Manchanda, Fengjiao Wang, Sathiya Keerthi, Avradeep Bhowmik, and Chandan K Reddy.  Image generation via minimizing fr$\backslash$’echet distance in discriminator feature space.  _arXiv preprint arXiv:2003.11774_ , 2020.
  * Doan et al. [2022] Khoa D Doan, Peng Yang, and Ping Li.  One loss for quantization: Deep hashing with discrete wasserstein distributional matching.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR)_ , pages 9447–9457, New Orleans, LA, 2022.
  * Fan et al. [2019] Miao Fan, Jiacheng Guo, Shuai Zhu, Shuo Miao, Mingming Sun, and Ping Li.  MOBIUS: towards the next generation of query-ad matching in baidu’s sponsored search.  In _Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining (KDD)_, pages 2509–2517, Anchorage, AK, 2019.
  * Fei et al. [2021] Hongliang Fei, Jingyuan Zhang, Xingxuan Zhou, Junhao Zhao, Xinyang Qi, and Ping Li.  GemNN: Gating-enhanced multi-task neural networks with feature interaction learning for CTR prediction.  In _Proceedings of the 44th International ACM SIGIR Conference on Research and Development in Information Retrieval (SIGIR)_ , pages 2166–2171, Virtual Event, Canada, 2021.
  * Friedman et al. [1975] Jerome H. Friedman, F. Baskett, and L. Shustek.  An algorithm for finding nearest neighbors.  _IEEE Transactions on Computers_ , 24:1000–1006, 1975.
  * Friedman et al. [1977] Jerome H. Friedman, J. Bentley, and R. Finkel.  An algorithm for finding best matches in logarithmic expected time.  _ACM Transactions on Mathematical Software_ , 3:209–226, 1977.
  * Gionis et al. [1999] Aristides Gionis, Piotr Indyk, and Rajeev Motwani.  Similarity search in high dimensions via hashing.  In _Proceedings of 25th International Conference on Very Large Data Bases (VLDB)_ , pages 518–529, Edinburgh, Scotland, UK, 1999.
  * Goemans and Williamson [1995] Michel X. Goemans and David P. Williamson.  Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming.  _J. ACM_ , 42(6):1115–1145, 1995.
  * Gong et al. [2013] Yunchao Gong, Svetlana Lazebnik, Albert Gordo, and Florent Perronnin.  Iterative quantization: A procrustean approach to learning binary codes for large-scale image retrieval.  _IEEE Trans. Pattern Anal. Mach. Intell._ , 35(12):2916–2929, 2013.
  * Gu et al. [2019] Wen Gu, Xiaoyan Gu, Jingzi Gu, Bo Li, Zhi Xiong, and Weiping Wang.  Adversary guided asymmetric hashing for cross-modal retrieval.  In _Proceedings of the 2019 on International Conference on Multimedia Retrieval (ICMR)_ , pages 159–167, 2019.
  * Gui and Li [2018] Jie Gui and Ping Li.  R2SDH: robust rotated supervised discrete hashing.  In _Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, KDD 2018, London, UK, August 19-23, 2018_, pages 1485–1493, 2018.
  * Guo et al. [2017] Huifeng Guo, Ruiming Tang, Yunming Ye, Zhenguo Li, and Xiuqiang He.  DeepFM: A factorization-machine based neural network for CTR prediction.  In _Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence (IJCAI)_ , pages 1725–1731, Melbourne, Australia, 2017.
  * Guo et al. [2016] Jiafeng Guo, Yixing Fan, Qingyao Ai, and W. Bruce Croft.  A deep relevance matching model for ad-hoc retrieval.  In _Proceedings of the 25th ACM International Conference on Information and Knowledge Management (CIKM)_ , pages 55–64, Indianapolis, IN, 2016\.
  * Huang et al. [2016] Chen Huang, Chen Change Loy, and Xiaoou Tang.  Unsupervised learning of discriminative attributes and visual representations.  In _Proceedings of the 2016 IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ , pages 5175–5184, 2016.
  * Huang et al. [2013] Po-Sen Huang, Xiaodong He, Jianfeng Gao, Li Deng, Alex Acero, and Larry P. Heck.  Learning deep structured semantic models for web search using clickthrough data.  In _Proceedings of the 22nd ACM International Conference on Information and Knowledge Management (CIKM)_ , pages 2333–2338, San Francisco, CA, 2013.
  * Huang et al. [2017] Shanshan Huang, Yichao Xiong, Ya Zhang, and Jia Wang.  Unsupervised triplet hashing for fast image retrieval.  In _Proceedings of the on Thematic Workshops of ACM Multimedia_ , pages 84–92, Mountain View, CA, 2017.
  * Huang et al. [2019] Xiao Huang, Jingyuan Zhang, Dingcheng Li, and Ping Li.  Knowledge graph embedding based question answering.  In _Proceedings of the Twelfth ACM International Conference on Web Search and Data Mining (WSDM)_ , pages 105–113, Melbourne, Australia, 2019\.
  * Indyk and Motwani [1998] Piotr Indyk and Rajeev Motwani.  Approximate nearest neighbors: Towards removing the curse of dimensionality.  In _Proceedings of the Thirtieth Annual ACM Symposium on the Theory of Computing (STOC)_ , pages 604–613, Dallas, TX, 1998.
  * Ioffe [2010] Sergey Ioffe.  Improved consistent sampling, weighted minhash and L1 sketching.  In _Proceedings of the 10th IEEE International Conference on Data Mining (ICDM)_ , pages 246–255, Sydney, Australia, 2010.
  * Jégou et al. [2011] Hervé Jégou, Matthijs Douze, and Cordelia Schmid.  Product quantization for nearest neighbor search.  _IEEE Trans. Pattern Anal. Mach. Intell._ , 33(1):117–128, 2011.
  * Jiang and Li [2017] Qing-Yuan Jiang and Wu-Jun Li.  Deep cross-modal hashing.  In _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ , pages 3232–3240, Honolulu, HI, 2017.
  * Jiang and Li [2018] Qing-Yuan Jiang and Wu-Jun Li.  Asymmetric deep supervised hashing.  In _Proceedings of the Thirty-Second AAAI Conference on Artificial Intelligence (AAAI)_ , pages 3342–3349, 2018.
  * Kang and McAuley [2019] Wang-Cheng Kang and Julian McAuley.  Candidate generation with binary codes for large-scale top-n recommendation.  In _Proceedings of the 28th ACM international conference on information and knowledge management_ , pages 1523–1532, 2019.
  * Li et al. [2018] Chao Li, Cheng Deng, Ning Li, Wei Liu, Xinbo Gao, and Dacheng Tao.  Self-supervised adversarial hashing networks for cross-modal retrieval.  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ , pages 4242–4251, 2018.
  * Li [2017] Ping Li.  Linearized GMM kernels and normalized random Fourier features.  In _Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD)_ , pages 315–324, Halifax, Canada, 2017.
  * Li et al. [2013] Ping Li, Gennady Samorodnitsky, and John E. Hopcroft.  Sign cauchy projections and chi-square kernel.  In _Advances in Neural Information Processing Systems (NIPS)_ , pages 2571–2579, Lake Tahoe, NV, 2013.
  * Li and Li [2022] Xiaoyun Li and Ping Li.  C-MinHash: Improving minwise hashing with circulant permutation.  In _Proceedings of the International Conference on Machine Learning (ICML)_ , pages 12857–12887, Baltimore, MD, 2022.
  * Lin et al. [2016] Kevin Lin, Jiwen Lu, Chu-Song Chen, and Jie Zhou.  Learning compact binary descriptors with unsupervised deep neural networks.  In _Proceedings of the 2016 IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ , pages 1183–1192, Las Vegas, NV, 2016.
  * Lu and Li [2013] Zhengdong Lu and Hang Li.  A deep architecture for matching short texts.  In _Advances in Neural Information Processing Systems (NIPS)_ , pages 1367–1375, Lake Tahoe, NV, 2013.
  * Malkov and Yashunin [2020] Yury A. Malkov and Dmitry A. Yashunin.  Efficient and robust approximate nearest neighbor search using hierarchical navigable small world graphs.  _IEEE Trans. Pattern Anal. Mach. Intell._ , 42(4):824–836, 2020.
  * Manasse et al. [2010] Mark Manasse, Frank McSherry, and Kunal Talwar.  Consistent weighted sampling.  Technical Report MSR-TR-2010-73, Microsoft Research, 2010.
  * Mitra and Craswell [2018] Bhaskar Mitra and Nick Craswell.  An introduction to neural information retrieval.  _Found. Trends Inf. Retr._ , 13(1):1–126, 2018\.
  * Morozov and Babenko [2018] Stanislav Morozov and Artem Babenko.  Non-metric similarity graphs for maximum inner product search.  In _Advances in Neural Information Processing Systems (NeurIPS)_ , pages 4726–4735, Montreal, Canada, 2018.
  * Ram and Gray [2012] Parikshit Ram and Alexander G Gray.  Maximum inner-product search using cone trees.  In _Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD)_ , pages 931–939, Beijing, China, 2012.
  * Salakhutdinov and Hinton [2009] Ruslan Salakhutdinov and Geoffrey Hinton.  Semantic hashing.  _International Journal of Approximate Reasoning_ , 50(7):969–978, 2009.
  * Severyn and Moschitti [2015] Aliaksei Severyn and Alessandro Moschitti.  Learning to rank short text pairs with convolutional deep neural networks.  In _Proceedings of the 38th International ACM SIGIR Conference on Research and Development in Information Retrieval (SIGIR)_ , pages 373–382, Santiago, Chile, 2015.
  * Shen et al. [2015] Fumin Shen, Chunhua Shen, Wei Liu, and Heng Tao Shen.  Supervised discrete hashing.  In _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ , pages 37–45, Boston, MA, 2015.
  * Shen et al. [2014] Yelong Shen, Xiaodong He, Jianfeng Gao, Li Deng, and Grégoire Mesnil.  Learning semantic representations using convolutional neural networks for web search.  In _Proceedings of the 23rd International World Wide Web Conference (WWW)_ , pages 373–374, Seoul, Korea, 2014.
  * Shrivastava and Li [2012] Anshumali Shrivastava and Ping Li.  Fast near neighbor search in high-dimensional binary data.  In _Proceedings of the European Conference on Machine Learning and Knowledge Discovery in Databases (ECML-PKDD), Part I_ , pages 474–489, Bristol, UK, 2012.
  * Shrivastava and Li [2014] Anshumali Shrivastava and Ping Li.  Asymmetric LSH (ALSH) for sublinear time maximum inner product search (MIPS).  In _Advances in Neural Information Processing Systems (NIPS)_ , pages 2321–2329, Montreal, Canada, 2014.
  * Shrivastava and Li [2015] Anshumali Shrivastava and Ping Li.  Asymmetric minwise hashing for indexing binary inner products and set containment.  In _Proceedings of the 24th International Conference on World Wide Web (WWW)_ , pages 981–991, Florence, Italy, 2015.
  * Sun et al. [2018] Mingming Sun, Xu Li, Xin Wang, Miao Fan, Yue Feng, and Ping Li.  Logician: A unified end-to-end neural approach for open-domain information extraction.  In _Proceedings of the Eleventh ACM International Conference on Web Search and Data Mining (WSDM)_ , pages 556–564, Marina Del Rey, CA, 2018\.
  * Tan et al. [2020] Shulong Tan, Zhixin Zhou, Zhaozhuo Xu, and Ping Li.  Fast item ranking under neural network based measures.  In _Proceedings of the Thirteenth ACM International Conference on Web Search and Data Mining (WSDM)_ , pages 591–599, Houston, TX, 2020.
  * Tay et al. [2018] Yi Tay, Luu Anh Tuan, and Siu Cheung Hui.  Latent relational metric learning via memory-based attention for collaborative ranking.  In _Proceedings of the 2018 World Wide Web Conference on World Wide Web (WWW)_ , pages 729–739, Lyon, France, 2018.
  * Xiong et al. [2017] Chenyan Xiong, Zhuyun Dai, Jamie Callan, Zhiyuan Liu, and Russell Power.  End-to-end neural ad-hoc ranking with kernel pooling.  In _Proceedings of the 40th International ACM SIGIR Conference on Research and Development in Information Retrieval (SIGIR)_ , pages 55–64, Shinjuku, Tokyo, 2017.
  * Xu et al. [2020] Jun Xu, Xiangnan He, and Hang Li.  Deep learning for matching in search and recommendation.  _Found. Trends Inf. Retr._ , 14(2-3):102–288, 2020.
  * Xue et al. [2017] Hong-Jian Xue, Xin-Yu Dai, Jianbing Zhang, Shujian Huang, and Jiajun Chen.  Deep matrix factorization models for recommender systems.  In _Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence (IJCAI)_ , pages 3203–3209, Melbourne, Australia, 2017.
  * Yang et al. [2018] Huei-Fang Yang, Kevin Lin, and Chu-Song Chen.  Supervised learning of semantics-preserving hash via deep convolutional neural networks.  _IEEE Trans. Pattern Anal. Mach. Intell._ , 40(2):437–451, 2018.
  * Yu et al. [2022] Tan Yu, Xu Li, Yunfeng Cai, Mingming Sun, and Ping Li.  S${}^{\mbox{2}}$-MLP: Spatial-shift MLP architecture for vision.  In _Proceedings of the IEEE/CVF Winter Conference on Applications of Computer Vision (WACV)_ , pages 3615–3624, Waikoloa, HI, 2022\.
  * Zamani et al. [2018] Hamed Zamani, Mostafa Dehghani, W. Bruce Croft, Erik G. Learned-Miller, and Jaap Kamps.  From neural re-ranking to neural ranking: Learning a sparse representation for inverted indexing.  In _Proceedings of the 27th ACM International Conference on Information and Knowledge Management (CIKM)_ , pages 497–506, Torino, Italy, 2018\.
  * Zhang et al. [2018] Xi Zhang, Hanjiang Lai, and Jiashi Feng.  Attention-aware deep adversarial hashing for cross-modal retrieval.  In _Proceedings of the European conference on computer vision (ECCV)_ , pages 591–606, 2018.
  * Zhao et al. [2020] Weijie Zhao, Shulong Tan, and Ping Li.  SONG: approximate nearest neighbor search on GPU.  In _Proceedings of the 36th IEEE International Conference on Data Engineering (ICDE)_ , pages 1033–1044, Dallas, TX, 2020.
  * Zhou et al. [2019] Zhixin Zhou, Shulong Tan, Zhaozhuo Xu, and Ping Li.  Möbius transformation for fast inner product search on graph.  In _Advances in Neural Information Processing Systems (NeurIPS)_ , pages 8216–8227, Vancouver, Canada, 2019.


11institutetext: INESC TEC, Porto, Portugal.
11email<EMAIL_ADDRESS>22institutetext: Faculty of Sciences,
University of Porto, 4169-007 Porto, Portugal
22email<EMAIL_ADDRESS>33institutetext: Faculty of Economics, University
of Porto, 4200-464 Porto. Portugal
33email<EMAIL_ADDRESS>
# Super-Resolution Analysis for
Landfill Waste Classification

Matías Molina 11 0000-0001-8799-6725 Rita P. Ribeiro 1122 0000-0002-6852-8077
Bruno Veloso 1133 0000-0001-7980-0972 João Gama 1133 0000-0003-3357-1195

###### Abstract

Illegal landfills are a critical issue due to their environmental, economic,
and public health impacts. This study leverages aerial imagery for
environmental crime monitoring. While advances in artificial intelligence and
computer vision hold promise, the challenge lies in training models with high-
resolution literature datasets and adapting them to open-access low-resolution
images. Considering the substantial quality differences and limited
annotation, this research explores the adaptability of models across these
domains. Motivated by the necessity for a comprehensive evaluation of waste
detection algorithms, it advocates cross-domain classification and super-
resolution enhancement to analyze the impact of different image resolutions on
waste classification as an evaluation to combat the proliferation of illegal
landfills. We observed performance improvements by enhancing image quality but
noted an influence on model sensitivity, necessitating careful threshold fine-
tuning.

###### Keywords:

Waste Detection Image Classification Super-resolution.

##  1 Introduction

Illegal landfills are places where waste material is dumped, violating
management laws. Illegal dumping has a tremendous impact on our ecosystem,
affecting our economy and health. As a result, various governments and
institutions worldwide have invested additional resources to prevent the
proliferation of waste dumping [13, 15, 3].

Aerial images from satellites, planes and, more recently, drones are an
important source of information for earth observation that helps in fighting
against environmental crime [1, 2]. In recent years, with the advance of
artificial intelligence and particularly computer vision approaches due to the
increasing computing capabilities and the exponential growth of available
annotated data, it has become possible to build different and accurate models
for image classification, as exemplified in numerous image recognition
challenges, including the Large Scale Visual Recognition Challenge (LSVRC)
[5], especially following the introduction of Convolutional Neural Networks
(CNNs) [8]. However, the need for an initial amount of images to train such
models makes it difficult to apply in waste detection. To build robust machine
learning methods for landfill classification, obtaining a significant amount
of landfill locations and access to their aerial images is crucial. The number
of aerial landfill datasets is limited, and they are commonly high-resolution
images. However, the location of these images is not typically provided due to
confidential information agreements. On the other hand, although it is
possible to obtain free access to different European satellite images (e.g.
Sentinel-2 via Copernicus 111Copernicus hub: https://scihub.copernicus.eu/),
these images are typically of very low resolution. In this context, we face
two challenges: i) The classification models are based on high-resolution
literature datasets with no geolocation provided, and they only contain the
standard Red, Green, and Blue (RGB) bands. ii) The open-access satellite image
banks provide low-resolution information, but we need information about
illegal landfill locations. These facts encourage us to investigate the
adaptability of the classification models built on the literature dataset to
different resolution query domains, as in the case of the freely available
image banks. However, the tremendous quality difference between the two types
of images and the lack of annotations present a hard limitation. For a
comprehensive evaluative process on the road of building machine learning and
computer vision waste detection algorithms, we motivate the evaluation of
cross-domain classification together with super-resolution enhancement, which
is the main goal of our work.

The main contributions of this manuscript lie in leveraging a dataset with
exceptionally high resolution to construct a binary classification model and
systematically evaluate the model’s performance across various resolutions.
Furthermore, we suggest an assessment of the model’s capabilities when trained
with higher-resolution images and subsequently applied to downscaled samples.
Following these experiments, we advocate utilising a super-resolution model to
enhance the quality before the classification process.

##  2 Related Work

This section explores two essential aspects: literature datasets used for
landfill classification tasks and methodologies employed to enhance image
resolution. Each subsection provides crucial insights into these key
components of our study.

###  2.1 Image classification for landfills discovery

The high performance of deep learning (DL) in image classification,
particularly in identifying landfills in aerial photographs, relies on the
availability of high-quality datasets to build the models. Unfortunately, such
datasets have been lacking in the field, posing a significant challenge in
developing scalable and accurate methods. To address this critical gap, Torres
and Fraternali [17] introduced the AerialWaste dataset for the specific task
of landfill detection. What sets this dataset apart is that it has been
meticulously annotated by professional photo interpreters, making it valuable
for building well-accurate image classifiers. AerialWaste contains 10434
images of very-high-resolution images generated from different sources: AGEA
Orthophotos (1000$\times$1000 pixels and 0.2m Ground Sampling Distance, GSD),
WORLDView-3 (700$\times$700 pixels and 0.3m GSD) and GoogleEarth
(1000$\times$1000 pixels and 0.5m GSD). They also provide 3478 positive and
6956 negative samples, indicating the presence or absence of waste,
respectively. The authors also provide the results of training a deep residual
model for binary classification using the ResNet-50 [6] architecture,
initialized with transfer learning from ImageNet [5] and augmented with a
Feature Pyramid Network (FPN) [11]. Another deep learning model applied to
landfill monitoring is RetinaNet [12] with DenseNet [7] as the backbone to
identify landfills as an object detection task in satellite images of the
Shanghai district [4, 16]. One important conclusion of this study is the
positive impact of data augmentation.

Despite the different literature models to address classification, detection
or segmentation for landfills, in most cases, the primary challenge involves
the lack of annotations and the different sizes of the contained waste. The
recent public Aerial Waste dataset provides an important amount of annotated
images and the evaluation of the binary classification through ResNet-50+FPN.
We use this dataset for our experiments, and the ResNet model is the base for
our classification benchmark.

###  2.2 Image quality improvement

Super-resolution (SR) is one of the most popular techniques that aim to
enhance the resolution and quality of images. It is particularly useful when
dealing with low-resolution images. The general idea behind SR is to learn to
generate missing details in low-resolution images by correlating them with
their original high-resolution pair. Various models have been explored in the
literature to address super-resolution for different tasks [9, 14]. The
standard optimization approach minimizes the mean squared error (MSE) between
the original high-resolution image and the high-resolution version constructed
from the low-resolution input. In addition, it is common to consider the
convergence to the peak signal-to-noise ratio (PSNR) as a complementary
measure. One of the most popular models uses a generative adversarial network
(GAN) approach (SRGAN) [14] and employs a deep residual network (ResNet)
architecture. Based on SRGAN, Lim et al. propose an enhanced model (Enhanced
Deep residual network for Super-Resolution, EDRS) [10] as a simplified version
of the SRGAN architecture by removing the unnecessary modules. The authors
also suggest minimizing the L1 norm instead of the MSE or L2 norm. Such
modification increases the original performance, improving the computation
time. In the following sections, we explain our proposal based on using ResNet
for classification and the EDSR baseline for our experiments.

In our work, we extend and incorporate the SR framework into the
classification pipeline to address the specific challenges of landfill
classification at different resolution settings. We perform an exhaustive
evaluation to understand how super-resolution can serve as a pre-process,
mitigating the resolution gap and enhancing the performance of our
classification model.

In Figure 1 it is possible to visualize an example of applying our
implementation of the EDSR model on a downscaled sample of the Aerial Waste
dataset.

Figure 1: Super-Resolution (SR) example: low-resolution input (left), SR
output (center) and high-resolution ground truth (right).

##  3 Methodology

Since our study focuses on evaluating waste detection through image
classification at different resolution domains, we leverage the advances in
computer vision and deep learning for this task. We use high-resolution aerial
images annotated with the presence or absence of waste.

We propose reproducing the ResNet-50 model with transfer learning from
ImageNet and trained with aerial waste, as proposed in [17]. To analyze the
impact of the different scales, we are not augmenting the architecture with
FPN. The first experiment is to train the model by downscaling the entire
dataset. It provides us with a general behaviour of the tasks throughout
different resolutions. After this, we use the model trained with the highest
resolution to query the different downscaled test samples to understand how
much information is missing at each resolution domain. Finally, we propose
using a super-resolution to improve each downscaled sample to the original
image to analyze its impact when classifying.

In summary, the three experimental scenarios are:

  * I.

Waste classification at different resolutions: ResNet-50 for binary
classification at different resolutions given by the different image size
dimensions {256, 128, 64, 32, 16, 8}. The output of this experiment aims to
answer the following question: How good is the model performance while trained
with data of inferior quality?

  * II.

High-resolution training for waste classification: ResNet-50 for binary
classification, train with high-resolution images and querying with different
lower resolutions. The output of this experiment aims to answer the following
question: How good is the model performance when it is queried with data of
inferior quality?

  * III.

Waste classification and super-resolution enhancement: ResNet-50 for binary
classification and Enhanced Deep Super-Resolution network (EDSR) for image
quality improvement. The EDSR is trained to be applied to images of different
resolutions to match the resolution of the images on which the ResNet model
has been trained. The output of this experiment aims to answer the following
question: How good is the classification model when it is combined with a
super-resolution enhancement as a pre-processing step?

In all the cases, we use the provided train and test split and also split the
training part to use the $20\%$ for validation. We found the best learning
rate by a grid search into {1e-2, 1e-3, 1e-4, 1e-5}, with 1e-4 being the best
value. Moreover, as the ResNet is pre-trained with ImageNet, we did an initial
validation, freezing a different number of layers to find the best possible
option to avoid overfitting. Freezing the first two layers best works for us
(as also worked in [17]).

###  3.1 Experimental Setup

####  3.1.1 Metrics.

We evaluate the classification model with the standard Accuracy, Precision,
Recall and F1 Score metrics for a comprehensive analysis. In addition, we also
consider the True Positive Rate (TPR) and False Positive Rate (FPR) for a
deeper analysis, as is discussed in Section 3.2.

For super-resolution, we use the two widely used metrics, Peak Signal-to-Noise
Ratio (PSNR) and Structural Similarity Index (SSIM) [10].

####  3.1.2 Experiment I.

Table 1: Different downscales and respective resolution (meters) for each source. Downscale | Size (px) | AGEA (m) | WV3 (m) | Google (m)
---|---|---|---|---
0 (initial) | 256 | 0.78 | 0.82 | 1.95
1 ($1/2$) | 128 | 1.56 | 1.64 | 3.9
2 ($1/4$) | 64 | 3.10 | 3.28 | 7.8
3 ($1/8$) | 32 | 6.24 | 6.56 | 15.6
4 ($1/16$) | 16 | 12.48 | 26.24 | 31.2
5 ($1/32$) | 8 | 24.96 | 52.48 | 62.4

The initial experiment involves training ResNet classifiers on different
dataset resolutions. Initially, the dataset is resized to $512\times 512$, and
subsequent experiments with a size of $256\times 256$ yielded similar
performance. Therefore, $256\times 256$ is chosen as the initial size for
further experiments, representing the highest resolution.

The experiment outputs ResNet-50 models trained on images of sizes $256\times
256$, $128\times 128$, $64\times 64$, $32\times 32$, $16\times 16$, and
$8\times 8$. This corresponds to scaling the images down by factors of
$1/2^{5}$ ($1/2$, $1/4$, $1/8$, $1/16$, and $1/32$, respectively). Considering
the original dataset size and resolutions, as described in Section 2.1, three
different resolutions are obtained for each image source, and the resulting
resolutions are calculated with respect to each resizing. These details are
summarized in Table 1. Despite the original dataset having various sizes and
resolutions, this table serves as a reference, emphasizing that beyond the
size of $32\times 32$, we start approaching the resolution of open and
accessible satellite imagery banks. We denote different models by indicating
the input size in a sub-index: $ResNet_{256}$, $ResNet_{128}$, …,
$ResNet_{8}$.

####  3.1.3 Experiment II.

The goal of the second experiment is to analyze the behaviour of the model
trained with our higher size ($ResNet_{256}$) and apply it across all
different resolutions (sizes of 128, 64, 32, 16 and 8). In this experiment,
the model is trained only once using 256-size images. After that, it queries
using the same testing split with different image sizes.

####  3.1.4 Experiment III.

The final experiment aims to enhance the quality of the downscaled images to
improve the final performance of the classification task. We use super-
resolution to enhance the different downscaled images to the original input
size of 256 and then classify them with the same ResNet model trained with
images of size 256. We implement other EDSR models to learn how to improve
each downscaled image to the original size of 256 $\times$ 256.

In this case, we trained only one model for classification $ResNet_{256}$, and
we built different super-resolution models $SR_{128\rightarrow
256},SR_{64\rightarrow 256},..,SR_{8\rightarrow 256}$.

####  3.1.5 Training and evaluation.

The ResNet model was trained using the original split provided by the dataset
authors. The validation was performed using the $20\%$ of the training set. We
stop the training at the epoch in which the loss training function converges,
and the validation loss function deviates from it. We use the ResNet-50
architecture and the ImageNet pre-trained options. Depending on the input size
setting, we needed between 17 and 20 epochs to train the model. Despite that,
the process behaviour is similar in all the cases.

The Super Resolution model (EDSR) was trained using the dataset resize to
$256\times 256$ as high-resolution and each of one of its downscaled versions
as low-resolution. Continuing the high- and low-resolution input pairs. In
this case, we follow three different metrics: the loss function (L1 loss),
Pick Signal to Noise Radio (PSNR) and the structural similarity index measure
(SSMI). We focused on the loss and PSNR curves more than the SSMI since the
different downscaled images make it more challenging to achieve a good SSMI
even though it also converges.

###  3.2 Results

The results of experiments I and II, involving training and testing the model
at different resolutions, are summarized in Table 2. For a more comprehensive
comparison, refer to Figure 2, where solid lines depict the different metrics
of training and testing the classification model at each resolution. While the
model shows reasonable performance across different resolutions, a noticeable
decline occurs beyond a certain point, especially when the resolution is
downscaled to size 32. Dashed lines represent the performance of training the
model with high-resolution images (size 256) and testing with each lower
resolution. An important observation is that despite is possible to obtain a
suitable performance at lower resolutions, from a certain point in advance,
the performance declines with a stronger tendency (e.g., training with a model
for image size 256 is significantly less effective for images of size 32, 16,
or 8). This suggests that (taking our reference in Table 1) training a model
for a resolution of 1 meter does not ensure good performance at 10 meters. We
demonstrate quantitatively that these observations align with the literature
concerning the lack of annotation and the resolution gap. These challenges
hinder the classification model adaptation.

Table 2:  Evaluation of models trained on different resolutions (Experiment I) and maximum resolution (Experiment II) by image size.  Size | Experiment I | Experiment II
---|---|---
(px) | F1-score | Recall | Precision | Accuracy | F1-score | Recall | Precision | Accuracy
256 | 0.8600 | 0.8793 | 0.8416 | 0.9044 | 0.8366 | 0.8092 | 0.8659 | 0.8944
128 | 0.8381 | 0.8598 | 0.8175 | 0.8891 | 0.7819 | 0.7563 | 0.8093 | 0.8591
64 | 0.8139 | 0.8598 | 0.7727 | 0.8687 | 0.6767 | 0.5954 | 0.7837 | 0.8100
32 | 0.7931 | 0.8241 | 0.7644 | 0.8564 | 0.2036 | 0.1161 | 0.8279 | 0.6967
16 | 0.6684 | 0.6034 | 0.7489 | 0.8000 | 0.0000 | 0.0000 | 0.0000 | 0.6660
8 | 0.4280 | 0.3057 | 0.7173 | 0.7271 | 0.0000 | 0.0000 | 0.0000 | 0.6660
Figure 2:  Evaluation of models trained on different resolutions (Experiment
I) - solid lines - and on maximum resolution (Experiment II) - dashed lines -
by image size.

Experiment III is summarized in Table 3. It shows the results of the super-
resolution enhancement by setting a standard classification threshold at $0.5$
compared to the results after choosing the best possible threshold.

In Figure 3, we observe the impact of using super-resolution (SR) to improve
the quality when querying the model trained with higher-resolution images. The
final result shows intermediate performance between Experiment I and
Experiment II, which means the SR approach improves when querying with lower
resolutions than the training. Nevertheless, it is evident how this
methodology impacts the model sensitivity (high recall) that biases the F1
Score up. To better understand the behaviour of the model sensitivity when SR
is applied, we analyzed the true positive rate and the false positive rate
throughout different threshold values during testing. The impact of changing
the default classification threshold during testing could be examined in
Figure 4. The plot shows a model with lesser sensitivity than the default
threshold while maintaining the F1 score with no significant decrease.

Table 3:  Evaluation of the model with Super-Resolution enhancement on downscaled images (Experiment III): default vs best threshold by image size.  Size | Default threshold | Best threshold
---|---|---
(px) | F1-score | Recall | Precision | Accuracy | F1-score | Recall | Precision | Accuracy
256 | 0.8600 | 0.8793 | 0.8416 | 0.9044 | 0.8600 | 0.8793 | 0.8416 | 0.9044
128 | 0.5674 | 0.9943 | 0.3970 | 0.4937 | 0.6402 | 0.8908$\blacktriangledown$ | 0.4997$\blacktriangle$ | 0.6656
64 | 0.5636 | 0.9954 | 0.3931 | 0.4852 | 0.6295 | 0.8897$\blacktriangledown$ | 0.4871$\blacktriangle$ | 0.6503
32 | 0.5812 | 0.9897 | 0.4114 | 0.5236 | 0.6185 | 0.8414$\blacktriangledown$ | 0.4890$\blacktriangle$ | 0.6534
16 | 0.6061 | 0.9471 | 0.4456 | 0.5889 | 0.5988 | 0.7299$\blacktriangledown$ | 0.5076$\blacktriangle$ | 0.6733
8 | 0.5931 | 0.8402 | 0.4583 | 0.6150 | 0.5918 | 0.7425$\blacktriangledown$ | 0.4920$\blacktriangle$ | 0.6580
Figure 3: Evaluation of models trained on different resolutions (Experiment I) - solid lines - and SR enhancement with default threshold (Experiment III) - dashed lines - by image size.  Figure 4: Evaluation of models trained on different resolutions (Experiment I) - solid lines - and SR enhancement with best threshold (Experiment III) - dashed lines - by image size.  Table 4: Best thresholds for SR enhancement (Experiment III) based on the ROC curves by image size. Size | 128 | 64 | 32 | 16 | 8
---|---|---|---|---|---
Threshold | 0.97 | 0.98 | 0.97 | 0.92 | 0.76

Regarding the threshold selection process, we could refer to the different
Receiver Operating Characteristic curves (ROC) shown in Figure 5. The ROC
curves indicate high values for both TPR and FPR rates when the threshold is
set to $0.5$ (shown as a red circle). The best threshold, thus, that makes a
good compromise between both rates is plotted as a black star. It was revealed
that higher thresholds can lead to a better compromise between both rates
(Table 4. We consider a $95\%$ as enough confidence level, and consequently,
we set to $0.95$ all the thresholds greater than that. Another interesting
observation is that the threshold maximizing both rates decreases as the
original image resolution is reduced. These thresholds converge to the default
one as the resolution decreases. We can conclude that the model’s sensitivity
can be adjusted, and its utility depends on the specific problem domain. A
more sensitive model may be preferred in environmental crimes, particularly in
detecting illegal landfills. This allows environmental agencies and
governments to verify potential issues on-site. However, the model might incur
a higher false negative rate in other scenarios, potentially missing a
possible illegal landfill. This study motivates further exploration of various
domain applications to provide a more comprehensive and cross-functional
evaluation.

In summary, super-resolution enhances classification performance when the
resolution of the query image is lower than the resolutions used during
training. However, it also increases the model’s sensitivity. As a result, it
becomes essential to fine-tune the threshold according to the domain’s
specific requirements.

(a) $ResNet\circ SR_{8\rightarrow 256}$ (b) $ResNet\circ SR_{16\rightarrow
256}$

(c) $ResNet\circ SR_{32\rightarrow 256}$ (d) $ResNet\circ SR_{64\rightarrow
256}$

(e) $ResNet\circ SR_{128\rightarrow 256}$

Figure 5: ROC curves obtained with SR enhancement (Experiment III).

##  4 Conclusions

This study makes contributions by introducing a dual-model approach, combining
a classification model and a super-resolution model, to address challenges in
waste detection related to varying image resolutions. The methodology focused
on combining both models to analyze the performance of waste classification
and the pertinence of resolution enhancement motivated by the lack of
information in conjunction with the different resolutions, which is a crucial
challenge in literature. The research design involved a series of experiments
to fairly compare image quality’s influence on building classification models
and explore potential improvements. The experiments reveal important insights
into the performance of waste detection models at various image resolutions.
It evidences that the classifiers can be effectively trained at different
resolutions. Still, their effectiveness declines as the resolution decreases,
especially after the third downscaling, which resolutions correlate with the
low resolution provided by the various open-access satellite imagery services.
While training with high-resolution images initially yields favourable
results, performance deteriorates as the resolution decreases. This indicates
that a model designed for higher resolutions performs poorly at lower
resolutions, especially after the first downscaling. These observations align
with the challenges highlighted in existing literature, demonstrating the
impact of the scarcity of annotations and the resolution gap.

Furthermore, we observe improvement in terms of performance when applying
super-resolution to enhance image quality. This approach notably impacts the
model’s sensitivity, leading to higher recall and, consequently, increased F1
Score. The study also explores the model’s sensitivity at varying threshold
values, showcasing the importance of adjusting thresholds to match specific
problem domains. In summary, super-resolution improves the waste
classification performance for lower-resolution images. Still, it intensifies
the model’s sensitivity, underscoring the need for threshold fine-tuning
tailored to specific domain requirements.

For future research, we intend to assess different super-resolution models and
verify the variability using various public and collected datasets.

## Acknowledgements

This work was supported by the EMERITUS project, which was funded by the
European Union’s Horizon Europe research and innovation programme under Grant
Agreement 101073874.

## References

  * [1] Esa: Earth observation finds a role in environmental treaties.  https://www.esa.int/Applications/Observing_the_Earth/Earth_observation_finds_a_role_in_environmental_treaties.  Accessed: Nov. 2023.
  * [2] Esa: Satellite technology to help fight crime.  https://www.esa.int/Enabling_Support/Preparing_for_the_Future/Space_for_Earth/Satellite_technology_to_help_fight_crime.  Accessed: Nov. 2023.
  * [3] Europol: Environmental crime in the age of climate change, threat assessment 2022.  https://www.europol.europa.eu/publications-events/publications/environmental-crime-in-age-of-climate-change-2022-threat-assessment, 2022.  Accessed: Nov. 2023.
  * [4] Shynggys Abdukhamet.  Landfill detection in satellite images using deep learning.  Shanghai Jiao Tong University Shanghai: Shanghai, China, 2019.
  * [5] Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei.  Imagenet: A large-scale hierarchical image database.  In 2009 IEEE conference on computer vision and pattern recognition, pages 248–255. Ieee, 2009.
  * [6] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun.  Deep residual learning for image recognition.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 770–778, 2016.
  * [7] Gao Huang, Zhuang Liu, Laurens Van Der Maaten, and Kilian Q Weinberger.  Densely connected convolutional networks.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 4700–4708, 2017.
  * [8] Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton.  Imagenet classification with deep convolutional neural networks.  In F. Pereira, C.J. Burges, L. Bottou, and K.Q. Weinberger, editors, Advances in Neural Information Processing Systems, volume 25. Curran Associates, Inc., 2012.
  * [9] Christian Ledig, Lucas Theis, Ferenc Huszár, Jose Caballero, Andrew Cunningham, Alejandro Acosta, Andrew Aitken, Alykhan Tejani, Johannes Totz, Zehan Wang, et al.  Photo-realistic single image super-resolution using a generative adversarial network.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 4681–4690, 2017.
  * [10] Bee Lim, Sanghyun Son, Heewon Kim, Seungjun Nah, and Kyoung Mu Lee.  Enhanced deep residual networks for single image super-resolution.  In Proceedings of the IEEE conference on computer vision and pattern recognition workshops, pages 136–144, 2017.
  * [11] Tsung-Yi Lin, Piotr Dollár, Ross Girshick, Kaiming He, Bharath Hariharan, and Serge Belongie.  Feature pyramid networks for object detection.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 2117–2125, 2017.
  * [12] Tsung-Yi Lin, Priya Goyal, Ross Girshick, Kaiming He, and Piotr Dollár.  Focal loss for dense object detection.  In Proceedings of the IEEE international conference on computer vision, pages 2980–2988, 2017.
  * [13] Adi Mager and Vered Blass.  From illegal waste dumps to beneficial resources using drone technology and advanced data analysis tools: A feasibility study.  Remote Sensing, 14(16):3923, 2022.
  * [14] Kamal Nasrollahi and Thomas B Moeslund.  Super-resolution: a comprehensive survey.  Machine vision and applications, 25:1423–1468, 2014.
  * [15] Desirée Rodríguez-Robles, Julia García-González, Andrés Juan-Valdés, Julia Mª Morán-del Pozo, and M Ignacio Guerra-Romero.  Overview regarding construction and demolition waste in spain.  Environmental technology, 36(23):3060–3070, 2015.
  * [16] Rocio Nahime Torres and Piero Fraternali.  Learning to identify illegal landfills through scene classification in aerial images.  Remote Sensing, 13(22), 2021.
  * [17] Rocio Nahime Torres and Piero Fraternali.  Aerialwaste dataset for landfill discovery in aerial and satellite images.  Scientific Data, 10(1):63, 2023.