# Retrieving Black-box Optimal Images from External Databases

Ryoma Sato<EMAIL_ADDRESS>Kyoto University / RIKEN AIP

(2022)

###### Abstract.

Suppose we have a black-box function (e.g., deep neural network) that takes an
image as input and outputs a value that indicates preference. How can we
retrieve optimal images with respect to this function from an external
database on the Internet? Standard retrieval problems in the literature (e.g.,
item recommendations) assume that an algorithm has full access to the set of
items. In other words, such algorithms are designed for service providers. In
this paper, we consider the retrieval problem under different assumptions.
Specifically, we consider how users with limited access to an image database
can retrieve images using their own black-box functions. This formulation
enables a flexible and finer-grained image search defined by each user. We
assume the user can access the database through a search query with tight API
limits. Therefore, a user needs to efficiently retrieve optimal images in
terms of the number of queries. We propose an efficient retrieval algorithm
Tiara for this problem. In the experiments, we confirm that our proposed
method performs better than several baselines under various settings.

Information Retrieval, Web Searching, Linear Bandits, Private Recommender
Systems

††journalyear: 2022††copyright: rightsretained††conference: Proceedings of the
Fifteenth ACM International Conference on Web Search and Data Mining; February
21–25, 2022; Tempe, AZ, USA††booktitle: Proceedings of the Fifteenth ACM
International Conference on Web Search and Data Mining (WSDM ’22), February
21–25, 2022, Tempe, AZ, USA††doi: 10.1145/3488560.3498462††isbn:
978-1-4503-9132-0/22/02††ccs: Information systems Web searching and
information discovery††ccs: Information systems Users and interactive
retrieval Table 1. Symbols, Definitions, and Examples.

Symbol | Definition | Example
---|---|---
$\mathcal{X}$ | The set of images in the image database | The set of all images uploaded on Flickr
$\mathcal{T}$ | The set of tags | The set of all tags on Flickr
$f\colon\mathcal{X}\to\mathbb{R}$ | The objective black-box function | A deep neural network that computes a preference score of an image
$\mathcal{O}\colon\mathcal{T}\to\mathcal{X}\times 2^{\mathcal{T}}$ | The oracle for image search | A wrapper of flickr.photos.search API
$\mathcal{T}_{\text{ini}}\subseteq\mathcal{T}$ | Initially known tags |  $100$ popular tags obtained by flickr.tags.getHotList API
$B\in\mathbb{Z}_{+}$ | A budget of oracle calls | $B=500$

##  1\. Introduction

As the amount of information on the Internet continues to drastically
increase, information retrieval algorithms are playing more important roles.
In a typical situation, a user of a system issues a query by specifying
keywords, and an information retrieval algorithm retrieves the optimal items
with respect to the query words. Here, the retrieval algorithm is designed by
the service provider, not by the user. The uses of information systems have
become divergent, and various retrieval algorithms have therefore been
proposed, e.g., a cross-modal image search (Cao et al., 2016; Kordan and
Kotov, 2018), complex query retrieval (Nie et al., 2012), and conversational
recommender systems (Sun and Zhang, 2018; Christakopoulou et al., 2016).

Deep neural networks have achieved state-of-the-art performances in computer
vision tasks (Krizhevsky et al., 2012; He et al., 2016), notably image
retrieval (Babenko and Lempitsky, 2015; Gordo et al., 2016; Bell and Bala,
2015; Niu et al., 2018). In a conventional setting of image retrieval,
algorithms assume that they have full access to the image database. A
straightforward method under this setting is to evaluate all images in the
database and return the one with the maximum score. When the image database is
extremely large, two-step methods are used, i.e., a handful of images are
retrieved through fast retrieval algorithms such as a nearest neighbor search,
and the results are ranked using sophisticated algorithms. Hash coding further
improves the effectiveness and efficiency (Lai et al., 2015; Liu et al.,
2016).

In this study, we consider information retrieval under a different scenario.
Whereas most existing studies have focused on how a service provider can
improve the search algorithms, we focus on how a user of a service can
effectively exploit the search results. Specifically, we consider a user of a
service builds their own scoring function. The examples of the scoring
functions are as follows.

Example 1 - Favorite Image Retrieval: A user trains deep neural networks using
a collection of favorite images found in different services and wants to
retrieve images with similar properties in a new service.

Example 2 - Similar Image Retrieval: Deep convolutional neural networks are
known to have a superior ability to extract useful image features (Babenko and
Lempitsky, 2015; Gatys et al., 2016; Bell and Bala, 2015). Although some
online services provide similar image search engines, users do not have full
control of the search. For example, even if the service provides a similar
texture-based image search engine, some users may want to retrieve similar
images based on the semantics. The user-defined score function allows image
searches at a finer granularity.

Example 3 - Fair Image Retrieval: A search engine can be unfair to some
protected attributes. For example, when we search for images through a query
“president,” an image search engine may retrieve only male president images
(Singh and Joachims, 2018). Some users may want to use their own scoring
function, e.g., scoring male and female images equally.

Recent advancements in deep learning, such as self-supervised contrastive
learning (Chen et al., 2020; He et al., 2020) and meta-learning (Finn et al.,
2017), enable the training of deep neural networks with a few labeled samples.
In addition, many pre-trained models for various vision tasks have been
released on the Internet. Machine learning as a service platform, such as
Microsoft Azure Machine Learning Studio and AWS Machine Learning, has also
made it easy to build a machine learning model. These techniques and services
enable an individual to easily build their own black-box scoring function.
Suppose a user has already built a black-box function she wants to optimize.
How can she retrieve optimal images with respect to this function from an
image database on the Internet?

Under this setting, an individual cannot evaluate all images in the image
database because it contains a significant number of images. It is also
impossible for an individual to build a search index (e.g., a hash index)
because of both limited access to the database and the insufficient
computational resources of the individual. These limitations prohibit the use
of standard image retrieval algorithms.

In this paper, we assume that a user can access the database through a search
query alone and that a tight query budget exists. In addition, we assume
little knowledge about the database to apply our method to a new environment.
We formulate the problem through the lens of the multi-armed bandit problem
and propose a query efficient algorithm, Tiara, with the aid of pre-trained
representative word embeddings. We confirm the effectiveness of the proposed
method under various settings, including the online Flickr environment.

It is noteworthy that Bayesian optimization and optimization on deep neural
networks (Erhan et al., 2009; Simonyan et al., 2014; Nguyen et al., 2016) also
aim to optimize black-box or complex functions. However, these methods assume
a continuous and simple optimization domain, typically the entire Euclidean
space $\mathbb{R}^{d}$, a hypercube $[0,1]^{d}$, or a unit ball
$\\{x\mid\|x\|\leq 1\\}$. By contrast, we aim to _retrieve_ optimal images
from the _fixed database_. Therefore, the optimization domain is a discrete
set of images. Although there are several methods for discrete black-box
optimization (Baptista and Poloczek, 2018; Oh et al., 2019), they also assume
that the optimization domain is simple, e.g., $\\{0,1\\}^{d}$, or at least
they have full access to the optimization domain. Under our setting, an
algorithm does not even know the entire optimization domain, i.e., the image
database. This limitation causes numerous challenges, as we describe in the
following sections.

The contributions of this paper are summarized as follows:

  * •

We formulate the black-box optimal image retrieval problem. This problem
examines how a user of an online service can effectively exploit a search
engine, whereas most existing studies focus on how a service provider can
improve a search engine.

  * •

We propose Tiara, an effective method for this problem for the first time.
Tiara is a general algorithm that works in various situations and retrieves
optimal black-box images with few API queries.

  * •

We investigate the effectiveness of Tiara using many real-world data. Notably,
we conduct “in the wild” experiments on the real-world Flickr environment and
confirm that Tiara can be readily used in real-world applications.

Reproducibility: Our code is available at https://github.com/joisino/tiara.

##  2\. Background

###  2.1. Notations

Let $\mathcal{X}$ be a set of images in the image database. We do not know the
exact set of $\mathcal{X}$. Let $f:\mathcal{X}\to\mathbb{R}$ be a black-box
function that evaluates the value of an image. For example, $f$ measures the
preference of the user in favorite image retrieval and measures the similarity
in similar image retrieval. The notations are summarized in Table 1.

###  2.2. Problem Formulation

In this section, we formulate the problem of black-box optimal image
retrieval. We observe that many image databases, such as Flickr and Instagram,
support (hash) tag-based search. We assume that we can search for images by
specifying a tag through an API. For example, in the Flickr case, we use the
flickr.photos.search API.

For a formal discussion, we generalize the function of tag search APIs. Let
$\mathcal{T}\subset\Sigma^{*}$ be the set of tags, where $\Sigma^{*}$ is the
set of strings. We formalize a tag search API as a (randomized) oracle
$\mathcal{O}$ that takes a tag as input and returns an image with the tag. We
assume that $\mathcal{O}$ always returns different images even when we query
the same tag twice. In addition to the image itself, we assume that the oracle
$\mathcal{O}$ returns the set of tags of the image. Therefore, for any tag
$t\in\mathcal{T}$, $\mathcal{O}(t)\in\mathcal{X}\times 2^{\mathcal{T}}$. Let
$\mathcal{O}(t).\texttt{image}\in\mathcal{X}$ denote the returned image and
$\mathcal{O}(t).\texttt{tags}\in 2^{\mathcal{T}}$ denote the returned tags. As
the oracle returns an image with the query tag,
$t\in\mathcal{O}(t).\texttt{tags}$ always holds.

We find that myriad tags exist in real-world services, and we cannot know the
entire tag set. Therefore, we assume that we know only a fraction
$\mathcal{T}_{\text{ini}}$ of the tag set. Here, $\mathcal{T}_{\text{ini}}$
can be constructed by browsing the online service or retrieving popular tags
through an API, e.g., flickr.tags.getHotList, in the Flickr example.

We assume that there is a budget $B\in\mathbb{Z}_{+}$ for the oracle call. For
example, in the Flickr case, There is an API rate limit of $3600$ calls per
hour. Thus, it is natural to assume that we can use at most $3600$ API calls
in one task. If we retrieve many images within a short period of time, the API
limits become tighter for each retrieval. To summarize, the black-box optimal
image retrieval problem is formalized as follows.

Black-box optimal image retrieval. Given: • Black box function
$f\colon\mathcal{X}\to\mathbb{R}$ • Oracle
$\mathcal{O}\colon\mathcal{T}\to\mathcal{X}\times 2^{\mathcal{T}}$ • Known
tags $\mathcal{T}_{\text{ini}}\subseteq\mathcal{T}$ • Budget
$B\in\mathbb{Z}_{+}$ Goal: Find an image $x\in\mathcal{X}$ in the image
database with as high an $f(x)$ as possible within $B$ accesses to the oracle.

##  3\. Proposed Method

In this section, We introduce our proposed method, Tiara (Tag-based image
retrieval).

###  3.1. Bandit Formulation

We first propose regarding the black-box optimal image retrieval problem as a
multi-armed bandit problem (Lattimore and Szepesvári, 2020; Slivkins, 2019).
Specifically, we regard a tag as an arm, the budget $B$ as the time horizon,
and the objective value $f(\mathcal{O}(t).\texttt{image})$ as the reward when
we choose arm $t$. This formulation enables us to use off-the-shelf multi-
armed bandit algorithms, such as UCB (Auer et al., 2002),
$\varepsilon$-greedy, and Thompson sampling (Thompson, 1933). This formulation
is the basics of our proposed algorithm. However, there are several challenges
to a black-box optimal image retrieval problem. First, we do not initially
know all arms but only a fraction $\mathcal{T}_{\text{ini}}$ of arms.
Considering $\mathcal{T}_{\text{ini}}$ alone leads to suboptimal results
because $\mathcal{T}_{\text{ini}}$ does not contain the best arm in general.
Second, myriad arms exist, and the number $|\mathcal{T}|$ of arms is larger
than budget $B$ in practice. Standard multi-armed bandit algorithms first
explore all arms once. However, they are unable to even finish this initial
exploration phase under a tight budget constraint.

The first problem is relatively easy to solve. We obtain tags
$\mathcal{O}(t).\texttt{tags}$ when we choose arm $t$. These tags may contain
new tags. We can add such tags into the known tag set and gradually grow the
known set. A good bandit algorithm will choose relevant tags, and the returned
tags will contain relevant tags. For example, suppose that the black-box
function $f$ prefers cat images. A good bandit algorithm will choose “cat” and
“animal” tags and obtain cat images accompanied by many cat-related tags. Even
if the budget is so tight that we cannot know all tags within the budget, a
good bandit algorithm ignores irrelevant tags and prioritizes the collection
of many relevant tags. The second problem is essential and difficult to solve.
We investigate how to improve the query efficiency using tag embeddings in the
following sections.

Discussion on the max-bandit problem. It should be noted that standard bandit
algorithms aim to maximize a cumulative reward or regret, whereas the black-
box optimal image retrieval problem aims to find an image with the maximum
value. These goals are not exactly the same. The problem of obtaining a
maximum reward is known as a max $K$-armed bandit (Cicirello and Smith, 2005)
or extreme bandit (Carpentier and Valko, 2014). However, we adhere to the
standard bandit setting in this study for the following reasons: First, we
assume that the reward distribution is Gaussian-like, whereas existing
max-$K$-armed bandit algorithms (Cicirello and Smith, 2005; Carpentier and
Valko, 2014) mainly assume that rewards are drawn from extreme value
distributions, such as the GEV distribution. We find that this is not the case
in the applications considered herein, i.e., image retrieval. Second, under
our setting, an arm with a high expected value often leads to a high maximum
value because such an arm usually represents the concept captured by the
black-box function $f$. By contrast, max-bandit algorithms focus on detecting
heavy tail arms with possibly low average rewards. We find that this is not
necessary for our setting. Finally, we experimentally confirm that our
proposed method already shows a superior empirical performance even though it
does not directly maximize the maximum objective value. We leave the
exploration of the max-bandit algorithms in our setting for future work.

###  3.2. Tag Embedding

1 Data: Known tags $\mathcal{T}_{\text{ini}}\subseteq\mathcal{T}$, Black box
function $f\colon\mathcal{X}\to\mathbb{R}$, Budget $B\in\mathbb{Z}_{+}$,
Oracle $\mathcal{O}\colon\mathcal{T}\to\mathcal{X}\times 2^{\mathcal{T}}$, Tag
Embedding $\\{{\boldsymbol{v}}_{t}\in\mathbb{R}^{d}\mid t\in\mathcal{T}\\}$,
Regularization coefficient $\lambda\in\mathbb{R}_{+}$, Exploration coefficient
$\alpha\in\mathbb{R}_{+}$.

2 Result: An image $x\in\mathcal{X}$ in the image database with as high $f(x)$
as possible.

3 ${\boldsymbol{A}}\leftarrow\lambda{\boldsymbol{I}}_{d\times d}$

//  Initialize ${\boldsymbol{A}}$

4 ${\boldsymbol{b}}\leftarrow\mathbf{0}_{d}$

//  Initialize ${\boldsymbol{b}}$

5 $\mathcal{T}_{\text{known}}\leftarrow\mathcal{T}_{\text{ini}}$

//  Initialize with the initial tags

6 for  _$i\leftarrow 1$ to $B$_ do

7
$s_{t}\leftarrow{\boldsymbol{v}}_{t}^{\top}{\boldsymbol{A}}^{-1}{\boldsymbol{b}}+\alpha\sqrt{{\boldsymbol{v}}_{t}^{\top}{\boldsymbol{A}}^{-1}{\boldsymbol{v}}_{t}}\quad\forall
t\in\mathcal{T}_{\text{known}}$

//  Scores

8
$t_{i}\leftarrow\mathop{\mathrm{argmax\,}}_{t\in\mathcal{T}_{\text{known}}}s_{t}$

//  Choose the best arm

9 $r_{i}\leftarrow\mathcal{O}(t_{i})$

//  Issue an query

10 for  _$t\in r_{i}.\texttt{tags}$_ do

11
${\boldsymbol{A}}\leftarrow{\boldsymbol{A}}+{\boldsymbol{v}}_{t}{\boldsymbol{v}}_{t}^{\top}$

//  Update ${\boldsymbol{A}}$

12
${\boldsymbol{b}}\leftarrow{\boldsymbol{b}}+f(r_{i}.\texttt{image})\cdot{\boldsymbol{v}}_{t}$

//  Update ${\boldsymbol{b}}$

13 $\mathcal{T}_{\text{known}}\leftarrow\mathcal{T}_{\text{known}}\cup\\{t\\}$

//  Insert $t$ to $\mathcal{T}_{\text{known}}$

14return $\mathop{\mathrm{argmax\,}}_{x\in\\{r_{i}.\texttt{image}\mid
i=1,\cdots,B\\}}f(x)$

//  Best image

Algorithm 1 Tiara

Because we cannot choose each arm even once on average, we need to estimate
the value of each arm without observing the reward from it. We estimate the
value of one arm from the rewards obtained from the other arms. The key is how
to define the similarities of the arms. As the challenge here, we assume a new
image database, and owing to the tight API limit, it is difficult to learn the
similarities from the current environment in an online manner. To tackle this
problem, we utilize external resources. We find that a tag in an image
database is usually described through natural language and typically is a word
or composition of words. We use a pre-trained word embedding (Mikolov et al.,
2013; Pennington et al., 2014) to define the similarities between tags.
Specifically, we first decompose a tag into a bag of words by non-alphabetical
symbols, e.g., a white space. We use the mean of the word embeddings in the
bag of words as the tag embedding.

Owing to the tag embeddings, we can infer the value of an arm from similar
arms. For example, if the reward from a “cat” tag is high (resp. low), we can
assume the black-box function is highly (resp. rarely) related to cats, and we
can infer that similar tags with similar embeddings, such as “Aegean cat” and
“animal,” are also valuable (resp. irrelevant) without actually querying them.

###  3.3. Tiara

Our proposed method combines the aforementioned tag embeddings with a bandit
algorithm. Specifically, we utilize LinUCB (Li et al., 2010). Because there
are no contextual features, we use only features of arms. We define the
feature of an arm as the tag embedding introduced in Section 3.2 and apply
LinUCB to this feature. We call this variant Tiara-S, where S stands for
“single” and “simple.” However, we found that there are too many tags, and
LinUCB is still inefficient for learning a reward because of the tight query
budget and limited training samples. To improve the query efficiency, we use
another signal from the oracle. The oracle $\mathcal{O}$ returns not only an
image but also the tags of the returned image. We assume that these tags have
similar average rewards and add these tags into the training dataset.
Specifically, when we query tag $t\in\mathcal{T}$, we use
$\\{(s,f(\mathcal{O}(t).\texttt{image}))\mid
s\in\mathcal{O}(t).\texttt{tags}\\}$ as training data, whereas Tiara-S uses
only $\\{(t,f(\mathcal{O}(t).\texttt{image}))\\}$. As we will see in the
experiment, this technique significantly improves query efficiency and
performance. Algorithm 1 shows the pseudo-code of Tiara.

Time Complexity. The bottleneck of the computation is in Line 7. The inverse
matrix ${\boldsymbol{A}}^{-1}$ can be efficiently computed in an iterative
manner using the Sherman–Morrison formula, i.e.,

$({\boldsymbol{A}}+{\boldsymbol{v}}_{t}{\boldsymbol{v}}_{t}^{\top})^{-1}={\boldsymbol{A}}^{-1}-\frac{{\boldsymbol{A}}^{-1}{\boldsymbol{v}}_{t}{\boldsymbol{v}}_{t}^{\top}{\boldsymbol{A}}^{-1}}{1+{\boldsymbol{v}}_{t}^{\top}{\boldsymbol{A}}^{-1}{\boldsymbol{v}}_{t}}.$

This technique reduces the cubic dependence on the number of dimensions to the
quadratic dependence. Therefore, the computation is in Line 7 takes
$O(|\mathcal{T}_{\text{known}}|d^{2})$ time. Let $T_{\text{max}}$ be the
maximum number of tags of an image. The value of $T_{\text{max}}$ is typically
$10$ to $100$. Because $|\mathcal{T}_{\text{known}}|$ increases by at most
$T_{\text{max}}$ in an iteration, the total time complexity is
$O((|\mathcal{T}_{\text{ini}}|+BT_{\text{max}})Bd^{2})$ in the worst case. In
our problem setting, $B$ is small (e.g., in the hundreds) because of the tight
API limitation, and $|\mathcal{T}_{\text{ini}}|\approx 100$ and $d\approx 300$
are also small during the experiments. Therefore, the oracle calls in Line 9
become a bottleneck in the wall-clock time because it requires communication
to the Internet. As the oracle calls are common in all methods, Tiara is
sufficiently efficient. When the black-box function is complex, its evaluation
can be a computational bottleneck as well. Tiara evaluates $f$ as few as $B$
times, which is the same as with other baseline methods. In addition, when the
efficiency is insufficient, we can speed up Tiara through a lazy variance
update (Desautels et al., 2012) and by applying sub-sampling heuristics.111We
do not adopt such techniques in the experiments.

Discussion on graph-feedback bandits. There are several multi-armed bandit
algorithms with a so-called feedback graph setting (Mannor and Shamir, 2011;
Alon et al., 2013; Kocák et al., 2014). This is an intermediate setting
between the bandit and full feedback. Specifically, it assumes that there is
an underlying graph, where a node represents an arm, and when we choose arm
$t$, we can also observe the rewards of the neighboring arms. The underlying
graph can be directed and time-varying. Therefore, if we define the neighbor
of $t$ as $\mathcal{O}(t).\texttt{tags}$, our problem is seen as a variant of
the feedback graph setting. However, we do not employ the feedback graph
framework for the following reasons: First, existing graph feedback bandit
algorithms require the number of neighbors of each neighbor (Mannor and
Shamir, 2011; Alon et al., 2013; Kocák et al., 2014), i.e.,
$|f(\mathcal{O}(s).\texttt{tags})|,\forall s\in
f(\mathcal{O}(t).\texttt{tags})$ in our setting. We need additional API
queries to compute these values. Such additional queries are prohibitive
because the API limit is tight under our setting. Second, graph feedback
bandit algorithms assume that the reward feedback of neighboring arms is an
unbiased estimate of the true rewards (Mannor and Shamir, 2011; Alon et al.,
2013; Kocák et al., 2014). However, $f(\mathcal{O}(t).\texttt{image})$ is not
unbiased for arm $s\in\mathcal{O}(t).\texttt{tags}$. Therefore, we cannot
enjoy the theoretical guarantees of the graph feedback bandits. Third, the
improvement obtained by the feedback graph framework is on the order of
$O(\sqrt{\alpha/n})$ (Kocák et al., 2014), where $n$ is the number of arms,
and $\alpha$ is the size of the maximum independent set of the feedback graph.
Under our setting, the sizes of the feedback graphs and $\alpha$ are still
large in practice. How to leverage the existing graph-feedback bandit
algorithms for our setting is an interesting area of future study.

Discussion on the reward estimation model. Tiara uses LinUCB and a linear
model for estimating the reward from the feature vector. In general, we can
use any model for prediction. We use a linear model owing to the following
reasons: First, complex models are difficult to train with a tight sample
budget. Second, LinUCB empirically performs quite well under various tasks (Li
et al., 2010; Krishnamurthy et al., 2016) regardless of its suboptimal
theoretical regret. Third, we use the average word embeddings as the feature
vector of an arm. It has been confirmed that word embeddings are
representative and that the weighted average of the word embeddings with a
cosine similarity or liner models produce superior performances in many NLP
tasks (Arora et al., 2017; Shen et al., 2018) and sometimes outperform even
neural network-based methods.

###  3.4. Visualization and Interpretation

Although not our original goal, Tiara provides an interpretation of the black-
box function $f$ as a byproduct.

Deep neural networks suffer from interpretability issues for reliable decision
making. There have been many interpretation methods developed for deep neural
networks (Simonyan et al., 2014; Sundararajan et al., 2017). We consider
model-level interpretability (Simonyan et al., 2014; Nguyen et al., 2016; Yuan
et al., 2020), i.e., interpreting what function each model represents. It is
unclear what function each model represents by simply looking at the model
parameters of deep models. Even if the model is prepared by the user, deep
models sometimes behave in unexpected ways (Goodfellow et al., 2015; Madry et
al., 2018). Input instances that produce high values can be regarded as
representations of the model (Simonyan et al., 2014; Nguyen et al., 2016; Yuan
et al., 2020). Tiara can retrieve such images from external image databases.
Compared to methods that use a fixed dataset, the search space of Tiara is
extremely large. Therefore, there are more chances that relevant images will
be found. In addition, tag scores of Tiara also provide another interpretation
of the black-box function through words. We show that these tags are also
beneficial for interpretability by visualizing word clouds in the experiments.
The tag-based interpretability is beneficial for further exploration as well.
When the result is unsatisfactory, the user can continue manual exploration
from the tags with high scores.

##  4\. Experiments

Figure 1. Open Image Environment. (Top) Tench, (Bottom) Black Swan. (Left)
Learning curves averaged over $10$ independent runs. (Mid) Word clouds that
represent the scores computed by Tiara at the end of the last iteration. These
visualizations provide an interprtability of the black-box function. (Right)
Best images found at each iteration. Table 2. Open Image Environment. Each
score is the highest $f(x)$ found by an algorithm. The scores are averaged
over $10$ independent runs, and the standard deviations are also reported. The
highest score is highlighted by bold in each column.

Method $\backslash$ Class | Tench | Black Swan | Tibetan Terrier | Tiger Beetle | Academic Gown | Cliff Dwelling | Hook | Paper Towel | Slot Machine | Water Tower | Average
---|---|---|---|---|---|---|---|---|---|---|---
Random | 13.11 $\pm$ 5.95 | 12.62 $\pm$ 4.83 | 13.16 $\pm$ 1.92 | 8.21 $\pm$ 1.85 | 12.63 $\pm$ 4.88 | 12.63 $\pm$ 5.31 | 11.58 $\pm$ 1.51 | 10.40 $\pm$ 1.01 | 9.29 $\pm$ 1.68 | 12.09 $\pm$ 1.64 | 11.57 $\pm$ 0.89
$\epsilon$-Greedy ($\epsilon=0.01$) | 13.48 $\pm$ 6.27 | 12.30 $\pm$ 4.94 | 13.76 $\pm$ 2.16 | 7.47 $\pm$ 2.53 | 14.83 $\pm$ 5.80 | 13.32 $\pm$ 6.07 | 11.17 $\pm$ 1.85 | 9.79 $\pm$ 0.84 | 8.55 $\pm$ 1.02 | 13.25 $\pm$ 1.41 | 11.79 $\pm$ 0.99
$\epsilon$-Greedy ($\epsilon=0.1$) | 13.48 $\pm$ 6.27 | 12.06 $\pm$ 4.99 | 13.76 $\pm$ 2.16 | 8.54 $\pm$ 3.19 | 14.83 $\pm$ 5.80 | 13.06 $\pm$ 6.26 | 11.17 $\pm$ 1.85 | 9.66 $\pm$ 0.83 | 8.84 $\pm$ 0.88 | 13.25 $\pm$ 1.41 | 11.86 $\pm$ 1.08
$\epsilon$-Greedy ($\epsilon=0.5$) | 13.64 $\pm$ 6.07 | 12.30 $\pm$ 4.96 | 13.76 $\pm$ 2.16 | 9.88 $\pm$ 3.39 | 13.10 $\pm$ 4.77 | 13.36 $\pm$ 6.02 | 11.64 $\pm$ 1.96 | 9.74 $\pm$ 0.95 | 8.42 $\pm$ 1.16 | 13.06 $\pm$ 1.63 | 11.89 $\pm$ 1.07
UCB ($\alpha=0.1$) | 13.48 $\pm$ 6.27 | 12.30 $\pm$ 4.94 | 13.76 $\pm$ 2.16 | 7.47 $\pm$ 2.53 | 14.83 $\pm$ 5.80 | 13.32 $\pm$ 6.07 | 11.17 $\pm$ 1.85 | 9.79 $\pm$ 0.84 | 8.55 $\pm$ 1.02 | 13.25 $\pm$ 1.41 | 11.79 $\pm$ 0.99
UCB ($\alpha=1.0$) | 13.71 $\pm$ 5.99 | 12.33 $\pm$ 4.94 | 13.76 $\pm$ 2.16 | 9.27 $\pm$ 3.73 | 14.83 $\pm$ 5.80 | 13.32 $\pm$ 6.07 | 11.17 $\pm$ 1.85 | 10.14 $\pm$ 0.98 | 8.42 $\pm$ 1.17 | 13.25 $\pm$ 1.41 | 12.02 $\pm$ 1.14
UCB ($\alpha=10.0$) | 13.68 $\pm$ 5.98 | 12.62 $\pm$ 4.83 | 13.76 $\pm$ 2.16 | 8.21 $\pm$ 1.85 | 13.05 $\pm$ 4.58 | 13.36 $\pm$ 6.02 | 11.61 $\pm$ 2.00 | 9.77 $\pm$ 1.25 | 8.70 $\pm$ 1.50 | 13.25 $\pm$ 1.41 | 11.80 $\pm$ 0.87
Ada-$\epsilon$-Greedy ($\epsilon=0.1$) | 11.34 $\pm$ 5.84 | 12.81 $\pm$ 4.97 | 13.28 $\pm$ 1.97 | 8.70 $\pm$ 1.36 | 15.62 $\pm$ 3.38 | 10.74 $\pm$ 2.13 | 11.09 $\pm$ 1.72 | 9.93 $\pm$ 0.81 | 8.43 $\pm$ 0.88 | 10.25 $\pm$ 1.34 | 11.22 $\pm$ 1.08
Ada-UCB ($\alpha=1.0$) | 11.34 $\pm$ 5.84 | 12.81 $\pm$ 4.97 | 13.28 $\pm$ 1.97 | 8.70 $\pm$ 1.36 | 15.62 $\pm$ 3.38 | 10.74 $\pm$ 2.13 | 11.09 $\pm$ 1.72 | 9.93 $\pm$ 0.81 | 8.43 $\pm$ 0.88 | 10.25 $\pm$ 1.34 | 11.22 $\pm$ 1.08
TiaraS | 16.30 $\pm$ 8.05 | 22.79 $\pm$ 7.73 | 12.67 $\pm$ 4.23 | 15.13 $\pm$ 2.88 | 25.40 $\pm$ 1.11 | 22.21 $\pm$ 0.00 | 12.21 $\pm$ 1.65 | 9.73 $\pm$ 1.69 | 12.60 $\pm$ 2.56 | 14.81 $\pm$ 1.08 | 16.39 $\pm$ 1.21
Tiara | 26.14 $\pm$ 0.00 | 27.73 $\pm$ 0.00 | 15.92 $\pm$ 0.00 | 16.91 $\pm$ 0.00 | 25.77 $\pm$ 0.00 | 22.21 $\pm$ 0.00 | 14.06 $\pm$ 0.16 | 22.13 $\pm$ 0.00 | 16.77 $\pm$ 0.30 | 15.69 $\pm$ 0.00 | 20.33 $\pm$ 0.03

We investigate the performance of Tiara using various real-world datasets.

###  4.1. Experimental Setups

####  4.1.1. Baselines

We use the following baselines.

  * •

Random queries random known tags.

  * •

$\varepsilon$-Greedy is a bandit algorithm. This algorithm chooses the best
tag with the highest empirical mean reward with a probability of
$1-\varepsilon$ and chooses a random tag with probability $\varepsilon$. The
candidate pool is set to $\mathcal{T}_{\text{ini}}$.

  * •

UCB is a bandit algorithm. The score of tag $t$ is the empirical mean reward
plus $\alpha\sqrt{1/n_{t}}$, where $n_{t}$ is the number of observations from
tag $t$, and $\alpha$ is a hyperparameter. UCB chooses the tag with the
highest score. The candidate pool is set to $\mathcal{T}_{\text{ini}}$.

  * •

Ada-$\varepsilon$-Greedy is a variant of $\varepsilon$-Greedy. This algorithm
inserts new tags to the candidate pool $\mathcal{T}_{\text{known}}$ when new
tags are found and chooses a tag from $\mathcal{T}_{\text{known}}$.

  * •

AdaUCB is a variant of UCB. This algorithm inserts new tags to the candidate
pool $\mathcal{T}_{\text{known}}$ when new tags are found and chooses a tag
from $\mathcal{T}_{\text{known}}$.

  * •

Tiara-S is a variant of Tiara that uses only the query tag for training.

####  4.1.2. Hyperparameters

We use $\lambda=1$ and $\alpha=0.01$ for Tiara and Tiara-S across all settings
without further tuning. We will show that Tiara is insensitive to the choice
of these hyperparameters over orders of magnitude in Section 4.5. We use
$300$-dimensional GloVe222https://nlp.stanford.edu/projects/glove/ trained
using six billion Wikipedia 2014 + Gigaword 5 tokens for the word embeddings.

We report the performance with various hyperparameters for the baseline
methods. Note that hyperparameter tuning is prohibitive in practice because of
the tight API limit. If we apply hyperparameter tuning, we should use these
query budgets for the main task instead. Therefore, this setting is slightly
advantageous for the baseline methods.

###  4.2. Open Images dataset

Figure 2. Safebooru Environment.444The source images are used under the
attribution, non-commercial, and no-derivative piapro license. The other
images are used with artist permission.(Left) Learning curves averaged over
$10$ independent runs. (Middle) Source images. (Right) Best Images found. In
the first row, we show the second best image for Tiara because Tiara found the
exact source image.

We use the Open Images Dataset V6 (Kuznetsova et al., 2020) to construct the
environment for the first testbed. Each image in this dataset has multi-class
annotations, such as “cat,” “Aegean cat,” and “Pumpkin pie.” An image has
$8.8$ classes on average. We use these classes as tags. We utilize ResNet18
(He et al., 2016) trained with ImageNet for the black-box functions.
Specifically, for each class $c$ of ImageNet, we use the pre-softmax logit for
$c$ as the back-box function. Among $1000$ classes of ImageNet, we use $10$
classes $c=1,101,\cdots,901$, i.e., Tench, Black Swan, Tibetan Terrier, Tiger
Beetle, Academic Gown, Cliff Dwelling, Hook, Paper Towel, Slot Machine, and
Water Tower. Note that the retrieval algorithms do not know these class names,
i.e., the function is a black-box. We use these class names for only
evaluations and interpretations of the results. Note also that the set of tags
(i.e., classes of the Open Image Dataset) differs from the set of classes of
ImageNet.

We subsample $10{,}000$ test images from the Open Images Dataset and construct
an environment. When we query tag (class) $t$, this environment returns a
random image with class $t$ and the set of classes this image belongs to. We
choose $100$ random tags as the initial known tags $\mathcal{T}_{\text{ini}}$
and set the budget to $B=500$.

We run ten trials with different seeds. Table 2 reports the means and standard
deviations of the best $f$ for each method within $B$ queries. The last column
reports the average of ten classes. These results show that Tiara performs the
best under all settings, and Tiara-S performs second best on average.

The middle panels in Figures 1 show the word clouds
555https://github.com/amueller/word_cloud generated by Tiara. The size and
color of a tag represent the score of the tag at the final iteration. These
scores provide interpretations for the black-box functions. For example, in
the case of tench, fish-related tags, such as Trout, Carp, and Milkfish, have
high scores. In the black swan case, bird-related tags, such as Swan,
Waterfowl, and Duck, have high scores. We stress again that Tiara does not use
the ground truth class name but instead treats $f$ as a black-box function.
Even when the ground truth class name is unavailable to us, the word cloud
generated by Tiara and the retrieved images indicate that $f$ is fish-related
in the first example and bird-related in the second example with significant
interpretability.

Figure 3. Flickr Environment. (Top) Black swan. (Bottom) Similar image
retrieval. (Left) Learning curves averaged over ten independent runs. (Top
middle) Word cloud generated by Tiara. (Bottom middle) Source image. (Right)
Best images found duing each iteration.

###  4.3. Safebooru Environment

The aim of this section is to confirm that Tiara is effective even in a
completely different domain. We use Safebooru as a testbed. We use a dump
retrieved on June 7, 2019 666https://www.kaggle.com/alamson/safebooru. Each
image has $34$ tags on average, such as “smile,” “long hair,” and “blonde
hair.” We use illustration2vec (Saito and Matsui, 2015) to construct the
black-box functions.

We use the latest $100{,}000$ images from this dataset and construct an
environment. As a result of the broken links, this environment contains
$81{,}517$ images in total. When we query tag $t$, this environment returns a
random image with tag $t$ and the set of tags this image belongs to. We choose
$100$ random tags as the initial known tags $\mathcal{T}_{\text{ini}}$ and set
the budget to $B=500$.

We conduct semantically similar image search experiments. We emphasize that
although this environment does not provide an official image-based search, our
algorithm enables such an image-based search. Given a source image $s$, we
compute $4096$-dimensional embedding
${\boldsymbol{v}}_{s}\in\mathbb{R}^{4096}$ using the pre-trained
illustration2vec model 777https://github.com/rezoo/illustration2vec. We use
the Gaussian kernel between the embeddings of an input image $x$ and the
source image as the black-box function, i.e.,
$f(x)=\exp(-\|{\boldsymbol{v}}_{s}-{\boldsymbol{v}}_{x}\|^{2}/\sigma^{2})$,
where ${\boldsymbol{v}}_{x}\in\mathbb{R}^{4096}$ is the embedding of input $x$
computed using the illustration2vec model, and $\sigma$ is the bandwidth of
the Gaussian kernel. We set $\sigma=100$ during this experiment. The more
semantically similar the input image is to the source, the higher the value
taken by this function.

We use two illustrations shown in Figure 4 (middle) as the source images. The
right panels in Figures 4 show images retrieved by the methods. The first
source image is in the image database, and Tiara succeeds in retrieving the
same image from the database. We show the second best image retrieved by Tiara
in this case. Even the second best image is semantically similar to the source
image, i.e., it depicts the same character with cherry blossom motifs, and has
a higher objective value than the images retrieved by the baseline methods.
For the second case, the source image is not in the database. Although not
exactly the same, Tiara succeeds in retrieving a semantically similar image
with the same characters and motifs, i.e., horn, rabbit, and costume.

These results show the flexibility of our framework such that Tiara can be
applied to not only photo-like image databases but also illustration-like
image databases using appropriate black-box functions. e.g., the
illustration2vec model.

###  4.4. Flickr Environment

The aim of this section is to confirm that Tiara is effective and readily
applicable to real-world environments. We use the online Flickr environment in
operation as a testbed. We also use ResNet18 trained with ImageNet to
construct the black-box functions. We implement oracle $\mathcal{O}$ by
combining flickr.photos.search and flickr.tags.getListPhoto APIs. We use the
license=’9,10’ option such that it returns only public domain or CC0 images.
We also set the budget to $B=500$. Because Flickr contains as many as _ten
billion_ images, it is challenging to find relevant images within $B=500$
queries. Each image has $15$ tags on average, including “summer,” “water,” and
“sea.”

We conduct two experiments in this environment. First, we conduct the same
experiment as in the open image environment. The top row of Figure 3 shows the
result for the black swan class. Compared to Figure 1, Tiara in this
environment learns more slowly than in the open image environment. We
hypothesis that this is because the Flickr environment contains noisy tags
annotated by users, which are occasionally described in foreign languages,
whereas the open image environment contains only clean tags that indicate
solid categories judged by annotators. Nevertheless, Tiara succeeds in
retrieving black swan images in several hundred queries.

Second, we conduct similar image retrieval experiments as in the safebooru
environment. We use the output of the penultimate layer of the pre-trained
ResNet18 for the image embedding. We use the Gaussian kernel between the
embeddings of an input image $x$ and the source image $s$ as the black-box
function, i.e.,
$f(x)=\exp(-\|{\boldsymbol{v}}_{s}-{\boldsymbol{v}}_{x}\|^{2}/\sigma^{2})$,
where ${\boldsymbol{v}}_{x}\in\mathbb{R}^{512}$ is the embedding of input $x$
computed using ResNet18, and $\sigma$ is the bandwidth of the Gaussian kernel.
We set $\sigma=10$ in this experiment. Figure 3 (bottom, center) shows the
source image. As the right panels show, Tiara succeeds in retrieving
semantically similar images depicting a sunrise over the sea.

Figure 4. Hyperparameter sensitivity. As the default settings, we set the
exploration coefficient as $\alpha=0.01$, regularization coefficient as
$\lambda=1.0$, and word embedding as $300$-dimensional Glove and change one
configuration in each panel. These results show that Tiara is stable with
respect to the hyperparameter choices across several orders of magnitude.

###  4.5. Hyperparameter Sensitivity

We investigate the hyperparameter sensitivity of Tiara in this section. Tiara
has two hyperparameters, i.e., exploration coefficient $\alpha$ and
regularization coefficient $\lambda$. Tiara also has a choice of word
embeddings. It is crucial to ensure stability with respect to the
hyperparameter choices because tuning the hyperparameters in a new environment
is difficult with tight API budgets. The left panel of Figure 4 shows the
average performance of Tiara in the Open Image Dataset environment with
various values of $\alpha$ maintaining $\lambda=1.0$ (default value). The
$x$-axis is plotted on a log scale. We show the performances of Tiara-S, UCB,
and Random for reference. In this plot, we do not tune the hyperparameters of
Tiara-S accordingly to maintain the conciseness of the plot. This plot shows
that Tiara is stable with respect to $\alpha$ over several orders of
magnitude. The middle panel of Figure 4 shows the average performance with
various values of $\lambda$ maintaining $\alpha=0.01$ (default value). The
$x$-axis is plotted on a log scale. The result shows that Tiara is stable with
respect to $\lambda$ over several orders of magnitude. The right panel of
Figure 4 shows the average performance with various dimensions of the GloVe
word embedding maintaining $\alpha=0.01$ and $\lambda=1.0$ (default values).
This result shows that Tiara performs better with higher dimensional
embeddings, i.e., more expressive embeddings. It also indicates that Tiara
indeed utilizes the word embedding geometry. We recommend using high-
dimensional and strong word embeddings for Tiara.

##  5\. Related Work

###  5.1. Image Retrieval

Image retrieval has been studied for decades. The main concern is how to
retrieve relevant images (Babenko and Lempitsky, 2015; Kato et al., 2008;
Leiva et al., 2011) with efficiency (Lai et al., 2015; Liu et al., 2016). Deep
neural networks have been preferred for image retrieval in recent years
because they can extract rich features including texture (Cimpoi et al.,
2015), style (Gatys et al., 2016), and semantics (Babenko and Lempitsky,
2015). Hash-based methods have also been extensively studied for their
efficiency (Lai et al., 2015; Liu et al., 2016). In addition, many extensions
have been studied, such as multi-modal image search (Cao et al., 2016; Kordan
and Kotov, 2018) and contextual retrieval (Xie et al., 2019). We investigated
the image retrieval problem from a different perspective. Specifically, we
consider how an outsider can retrieve desirable images from an _external_
image database with as few queries as possible.

###  5.2. Web Crawling

Our problem setting can be seen as a crawling problem. Developing efficient
web crawlers is a long-standing problem in the literature (Cho et al., 1998;
Chakrabarti et al., 1999; Diligenti et al., 2000; Cho and Garcia-Molina, 2003;
Castillo, 2005; Pham et al., 2019). In particular, focused crawling
(Chakrabarti et al., 1999; McCallum et al., 2000; Johnson et al., 2003; Baeza-
Yates et al., 2005; Guan et al., 2008) is relevant to our problem setting.
Focused crawling aims to efficiently gather relevant pages by skipping
irrelevant pages.

However, there are several differences between our study and existing focused
crawling. First, focused crawling is used to search web pages by following WWW
hyperlinks, whereas we search for _images_ from an _external database_
utilizing the tag search oracle. Thus, the existing crawling methods are not
directly applicable to our setting. Second, we assume the API limit is
extremely tight, e.g., $500$, whereas existing focused crawlers typically
visit hundreds of thousands of pages. Third, existing focused crawlers focus
on retrieving pages of a specific topic (Chakrabarti et al., 1999; McCallum et
al., 2000), popular pages (Baeza-Yates et al., 2005), pages with structured
data (Meusel et al., 2014), or hidden web pages (Barbosa and Freire, 2007). By
contrast, deep convolutional neural networks in our setting realize rich
vision applications, as we show in the experiments. These applications are
qualitatively different from the existing focused crawlers and are valuable in
their own right.

###  5.3. Private Recommender Systems

Private recommender systems (Sato, 2022) aim to build a fair recommender
system when the service provider does not offer a fair system. Our problem can
also be seen as constructing a private recommender system when the black-box
function is a recommendation score. There are several differences between our
approach and private recommender systems. First, the existing methods,
PrivateRank and PrivateWalk, assume the use of an item recommendation oracle,
which is unavailable under our setting. Second, Tiara considers content-based
retrieval, whereas PrivateRank and PrivateWalk mainly focus on a collaborative
recommendation scenario. Third, our application is not limited to fairness,
and we showed promising applications, including semantically similar image
retrieval.

##  6\. Discussion and Limitations

Although we use deep neural networks as a black-box function, our framework
and the proposed method are not limited to deep neural networks. For example,
we can use human judgment as the black-box function, i.e., when we evaluate
$f(x)$, we actually ask a human viewer how much he/she likes image $x$.
Because our proposed method requires several hundred evaluations for a single
run, the current method is too inefficient for human-in-the-loop experiments.
More efficient methods are important for developing such intriguing
applications.

In this work, we have assumed that $f$ is a well-behaved function. It may be
interesting to use buggy $f$ functions. For example, when we debug a deep
neural network model $f$, applying Tiara to $f$ may reveal what $f$ has
already learned and has not yet. We hypothesize that there are much room for
further applications of Tiara.

We have assumed that the only way to access the image database is the tag
search oracle $\mathcal{O}$. Although our method is general owing to this
formulation, many other APIs are available in real applications, such as user-
based searches, popularity ranking, and collaborative filtering
recommendations. Utilizing richer information to enhance performance and query
efficiency is important in practice. At the other extreme, dropping the
assumptions of tag affinity and tag search APIs to make the method applicable
to broader databases is also an intriguing direction.

Although we have focused on image retrieval problems, our formulation is not
limited to such problems and can be applied to other domains such as music,
document, and video retrieval problems. Exploring further applications of our
framework is left as future work.

##  7\. Conclusion

In this paper, we formulated the problem of optimal image retrieval with
respect to a given black-box function from an external image database. This
problem enables each user to retrieve their preferable images from the
Internet, even if the image database does not provide such features. We
combined a bandit formulation with pre-trained word embeddings and proposed an
effective retrieval algorithm called Tiara. Finally, we confirmed the
effectiveness of Tiara using three environments, including an online Flickr
environment.

###### Acknowledgements.

This work was supported by JSPS KAKENHI GrantNumber 21J22490. We are grateful
to ARAM, トマリ, でんろく, Qie_, 亀村江龍, こんぺ伊藤, 小本呆毛, and ミテディー for allowing the use of
their wonderful illustrations.

## References

  * Alon et al. [2013] Noga Alon, Nicolò Cesa-Bianchi, Claudio Gentile, and Yishay Mansour.  From bandits to experts: A tale of domination and independence.  In _NeurIPS_ , pages 1610–1618, 2013.
  * Arora et al. [2017] Sanjeev Arora, Yingyu Liang, and Tengyu Ma.  A simple but tough-to-beat baseline for sentence embeddings.  In _ICLR_ , 2017.
  * Auer et al. [2002] Peter Auer, Nicolò Cesa-Bianchi, and Paul Fischer.  Finite-time analysis of the multiarmed bandit problem.  _Mach. Learn._ , 47(2-3):235–256, 2002.
  * Babenko and Lempitsky [2015] Artem Babenko and Victor S. Lempitsky.  Aggregating local deep features for image retrieval.  In _ICCV_ , pages 1269–1277, 2015.
  * Baeza-Yates et al. [2005] Ricardo A. Baeza-Yates, Carlos Castillo, Mauricio Marín, and M. Andrea Rodríguez.  Crawling a country: better strategies than breadth-first for web page ordering.  In _WWW_ , pages 864–872, 2005.
  * Baptista and Poloczek [2018] Ricardo Baptista and Matthias Poloczek.  Bayesian optimization of combinatorial structures.  In _ICML_ , pages 471–480, 2018.
  * Barbosa and Freire [2007] Luciano Barbosa and Juliana Freire.  An adaptive crawler for locating hidden-web entry points.  In _WWW_ , pages 441–450, 2007.
  * Bell and Bala [2015] Sean Bell and Kavita Bala.  Learning visual similarity for product design with convolutional neural networks.  _ACM Trans. Graph._ , 34(4):98:1–98:10, 2015\.
  * Cao et al. [2016] Yue Cao, Mingsheng Long, Jianmin Wang, Qiang Yang, and Philip S. Yu.  Deep visual-semantic hashing for cross-modal retrieval.  In _KDD_ , pages 1445–1454, 2016.
  * Carpentier and Valko [2014] Alexandra Carpentier and Michal Valko.  Extreme bandits.  In _NeurIPS_ , pages 1089–1097, 2014.
  * Castillo [2005] Carlos Castillo.  Effective web crawling.  _SIGIR Forum_ , 39(1):55–56, 2005.
  * Chakrabarti et al. [1999] Soumen Chakrabarti, Martin van den Berg, and Byron Dom.  Focused crawling: A new approach to topic-specific web resource discovery.  _Comput. Networks_ , 31(11-16):1623–1640, 1999\.
  * Chen et al. [2020] Ting Chen, Simon Kornblith, Mohammad Norouzi, and Geoffrey E. Hinton.  A simple framework for contrastive learning of visual representations.  In _ICML_ , pages 1597–1607, 2020.
  * Cho and Garcia-Molina [2003] Junghoo Cho and Hector Garcia-Molina.  Effective page refresh policies for web crawlers.  _ACM Trans. Database Syst._ , 28(4):390–426, 2003.
  * Cho et al. [1998] Junghoo Cho, Hector Garcia-Molina, and Lawrence Page.  Efficient crawling through URL ordering.  _Comput. Networks_ , 30(1-7):161–172, 1998.
  * Christakopoulou et al. [2016] Konstantina Christakopoulou, Filip Radlinski, and Katja Hofmann.  Towards conversational recommender systems.  In _KDD_ , pages 815–824, 2016.
  * Cicirello and Smith [2005] Vincent A. Cicirello and Stephen F. Smith.  The max _K-_ armed bandit: A new model of exploration applied to search heuristic selection.  In _AAAI_ , pages 1355–1361, 2005.
  * Cimpoi et al. [2015] Mircea Cimpoi, Subhransu Maji, and Andrea Vedaldi.  Deep filter banks for texture recognition and segmentation.  In _CVPR_ , pages 3828–3836, 2015.
  * Desautels et al. [2012] Thomas Desautels, Andreas Krause, and Joel W. Burdick.  Parallelizing exploration-exploitation tradeoffs with gaussian process bandit optimization.  In _ICML_ , 2012.
  * Diligenti et al. [2000] Michelangelo Diligenti, Frans Coetzee, Steve Lawrence, C. Lee Giles, and Marco Gori.  Focused crawling using context graphs.  In _VLDB_ , pages 527–534, 2000.
  * Erhan et al. [2009] Dumitru Erhan, Yoshua Bengio, Aaron Courville, and Pascal Vincent.  Visualizing higher-layer features of a deep network.  _University of Montreal_ , 1341(3):1, 2009.
  * Finn et al. [2017] Chelsea Finn, Pieter Abbeel, and Sergey Levine.  Model-agnostic meta-learning for fast adaptation of deep networks.  In _ICML_ , pages 1126–1135, 2017.
  * Gatys et al. [2016] Leon A. Gatys, Alexander S. Ecker, and Matthias Bethge.  Image style transfer using convolutional neural networks.  In _CVPR_ , pages 2414–2423, 2016.
  * Goodfellow et al. [2015] Ian J. Goodfellow, Jonathon Shlens, and Christian Szegedy.  Explaining and harnessing adversarial examples.  In _ICLR_ , 2015.
  * Gordo et al. [2016] Albert Gordo, Jon Almazán, Jérôme Revaud, and Diane Larlus.  Deep image retrieval: Learning global representations for image search.  In _ECCV_ , pages 241–257, 2016.
  * Guan et al. [2008] Ziyu Guan, Can Wang, Chun Chen, Jiajun Bu, and Junfeng Wang.  Guide focused crawler efficiently and effectively using on-line topical importance estimation.  In _SIGIR_ , pages 757–758, 2008.
  * He et al. [2016] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun.  Deep residual learning for image recognition.  In _CVPR_ , pages 770–778, 2016.
  * He et al. [2020] Kaiming He, Haoqi Fan, Yuxin Wu, Saining Xie, and Ross B. Girshick.  Momentum contrast for unsupervised visual representation learning.  In _CVPR_ , pages 9726–9735, 2020.
  * Johnson et al. [2003] Judy Johnson, Kostas Tsioutsiouliklis, and C. Lee Giles.  Evolving strategies for focused web crawling.  In _ICML_ , pages 298–305, 2003.
  * Kato et al. [2008] Makoto P. Kato, Hiroaki Ohshima, Satoshi Oyama, and Katsumi Tanaka.  Can social tagging improve web image search?  In _WISE_ , pages 235–249, 2008.
  * Kocák et al. [2014] Tomáš Kocák, Gergely Neu, Michal Valko, and Rémi Munos.  Efficient learning by implicit exploration in bandit problems with side observations.  In _NeurIPS_ , pages 613–621, 2014.
  * Kordan and Kotov [2018] Saeid Balaneshin Kordan and Alexander Kotov.  Deep neural architecture for multi-modal retrieval based on joint embedding space for text and images.  In _WSDM_ , pages 28–36, 2018.
  * Krishnamurthy et al. [2016] Akshay Krishnamurthy, Alekh Agarwal, and Miroslav Dudík.  Contextual semibandits via supervised learning oracles.  In _NeurIPS_ , pages 2388–2396, 2016.
  * Krizhevsky et al. [2012] Alex Krizhevsky, Ilya Sutskever, and Geoffrey E. Hinton.  Imagenet classification with deep convolutional neural networks.  In _NeurIPS_ , pages 1106–1114, 2012.
  * Kuznetsova et al. [2020] Alina Kuznetsova, Hassan Rom, Neil Alldrin, Jasper Uijlings, Ivan Krasin, Jordi Pont-Tuset, Shahab Kamali, Stefan Popov, Matteo Malloci, Alexander Kolesnikov, Tom Duerig, and Vittorio Ferrari.  The open images dataset v4: Unified image classification, object detection, and visual relationship detection at scale.  _IJCV_ , 2020.
  * Lai et al. [2015] Hanjiang Lai, Yan Pan, Ye Liu, and Shuicheng Yan.  Simultaneous feature learning and hash coding with deep neural networks.  In _CVPR_ , pages 3270–3278, 2015.
  * Lattimore and Szepesvári [2020] Tor Lattimore and Csaba Szepesvári.  _Bandit algorithms_.  Cambridge University Press, 2020.
  * Leiva et al. [2011] Luis A. Leiva, Mauricio Villegas, and Roberto Paredes.  Query refinement suggestion in multimodal image retrieval with relevance feedback.  In _ICMI_ , pages 311–314, 2011.
  * Li et al. [2010] Lihong Li, Wei Chu, John Langford, and Robert E. Schapire.  A contextual-bandit approach to personalized news article recommendation.  In _WWW_ , pages 661–670, 2010.
  * Liu et al. [2016] Haomiao Liu, Ruiping Wang, Shiguang Shan, and Xilin Chen.  Deep supervised hashing for fast image retrieval.  In _CVPR_ , pages 2064–2072, 2016.
  * Madry et al. [2018] Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu.  Towards deep learning models resistant to adversarial attacks.  In _ICLR_ , 2018.
  * Mannor and Shamir [2011] Shie Mannor and Ohad Shamir.  From bandits to experts: On the value of side-observations.  In _NeurIPS_ , pages 684–692, 2011.
  * McCallum et al. [2000] Andrew McCallum, Kamal Nigam, Jason Rennie, and Kristie Seymore.  Automating the construction of internet portals with machine learning.  _Inf. Retr._ , 3(2):127–163, 2000.
  * Meusel et al. [2014] Robert Meusel, Peter Mika, and Roi Blanco.  Focused crawling for structured data.  In _CIKM_ , pages 1039–1048, 2014.
  * Mikolov et al. [2013] Tomás Mikolov, Kai Chen, Greg Corrado, and Jeffrey Dean.  Efficient estimation of word representations in vector space.  In _ICLR_ , 2013.
  * Nguyen et al. [2016] Anh Mai Nguyen, Alexey Dosovitskiy, Jason Yosinski, Thomas Brox, and Jeff Clune.  Synthesizing the preferred inputs for neurons in neural networks via deep generator networks.  In _NeurIPS_ , pages 3387–3395, 2016.
  * Nie et al. [2012] Liqiang Nie, Shuicheng Yan, Meng Wang, Richang Hong, and Tat-Seng Chua.  Harvesting visual concepts for image search with complex queries.  In _MM_ , pages 59–68, 2012.
  * Niu et al. [2018] Wei Niu, James Caverlee, and Haokai Lu.  Neural personalized ranking for image recommendation.  In _WSDM_ , pages 423–431, 2018.
  * Oh et al. [2019] ChangYong Oh, Jakub M. Tomczak, Efstratios Gavves, and Max Welling.  Combinatorial bayesian optimization using the graph cartesian product.  In _NeurIPS_ , pages 2910–2920, 2019.
  * Pennington et al. [2014] Jeffrey Pennington, Richard Socher, and Christopher D. Manning.  Glove: Global vectors for word representation.  In _EMNLP_ , pages 1532–1543, 2014.
  * Pham et al. [2019] Kien Pham, Aécio S. R. Santos, and Juliana Freire.  Bootstrapping domain-specific content discovery on the web.  In _WWW_ , pages 1476–1486, 2019.
  * Saito and Matsui [2015] Masaki Saito and Yusuke Matsui.  Illustration2vec: a semantic vector representation of illustrations.  In _SIGGRAPH Asia Technical Briefs_ , pages 5:1–5:4, 2015.
  * Sato [2022] Ryoma Sato.  Private recommender systems: How can users build their own fair recommender systems without log data?  In _Proceedings of the 2022 SIAM International Conference on Data Mining, SDM_ , 2022.
  * Shen et al. [2018] Dinghan Shen, Guoyin Wang, Wenlin Wang, Martin Renqiang Min, Qinliang Su, Yizhe Zhang, Chunyuan Li, Ricardo Henao, and Lawrence Carin.  Baseline needs more love: On simple word-embedding-based models and associated pooling mechanisms.  In _ACL_ , pages 440–450, 2018.
  * Simonyan et al. [2014] Karen Simonyan, Andrea Vedaldi, and Andrew Zisserman.  Deep inside convolutional networks: Visualising image classification models and saliency maps.  In _ICLR workshop_ , 2014.
  * Singh and Joachims [2018] Ashudeep Singh and Thorsten Joachims.  Fairness of exposure in rankings.  In _KDD_ , pages 2219–2228, 2018.
  * Slivkins [2019] Aleksandrs Slivkins.  Introduction to multi-armed bandits.  _Found. Trends Mach. Learn._ , 12(1-2):1–286, 2019.
  * Sun and Zhang [2018] Yueming Sun and Yi Zhang.  Conversational recommender system.  In _SIGIR_ , pages 235–244, 2018.
  * Sundararajan et al. [2017] Mukund Sundararajan, Ankur Taly, and Qiqi Yan.  Axiomatic attribution for deep networks.  In Doina Precup and Yee Whye Teh, editors, _ICML_ , pages 3319–3328, 2017.
  * Thompson [1933] William R Thompson.  On the likelihood that one unknown probability exceeds another in view of the evidence of two samples.  _Biometrika_ , 25(3/4):285–294, 1933.
  * Xie et al. [2019] Xiaohui Xie, Jiaxin Mao, Yiqun Liu, Maarten de Rijke, Qingyao Ai, Yufei Huang, Min Zhang, and Shaoping Ma.  Improving web image search with contextual information.  In _CIKM_ , pages 1683–1692, 2019.
  * Yuan et al. [2020] Hao Yuan, Jiliang Tang, Xia Hu, and Shuiwang Ji.  XGNN: towards model-level explanations of graph neural networks.  In _KDD_ , pages 430–438, 2020.


11institutetext: Applied and Computational Mathematics Division, National
Institute of Standards and Technology (NIST), Gaithersburg, Maryland, U.S.A.,
11email<EMAIL_ADDRESS>22institutetext: Database Systems and Information Management Group, Technische
Universität, Berlin, Germany, 22email<EMAIL_ADDRESS>
33institutetext: Poolesville High School, Poolesville, Maryland, U.S.A.,
33email<EMAIL_ADDRESS>44institutetext: Wootton High School,
Rockville, Maryland, U.S.A. 44email<EMAIL_ADDRESS>
# Growing the Digital Repository of Mathematical Formulae with Generic LaTeX
Sources ††thanks: The final publication is available at
http://link.springer.com.

Howard S. Cohl 11 Moritz Schubotz 22 Marjorie A. McClain 11 Bonita V. Saunders
11 Cherry Y. Zou 33 Azeem S. Mohammed 33 Alex A. Danoff 44

###### Abstract

One initial goal for the DRMF is to seed our digital compendium with
fundamental orthogonal polynomial formulae. We had used the data from the NIST
Digital Library of Mathematical Functions (DLMF) as initial seed for our DRMF
project. The DLMF input LaTeX source already contains some semantic
information encoded using a highly customized set of semantic LaTeX macros.
Those macros could be converted to content MathML using LaTeXML. During that
conversion the semantics were translated to an implicit DLMF content
dictionary. This year, we have developed a semantic enrichment process whose
goal is to infer semantic information from generic LaTeX sources. The
generated context-free semantic information is used to build DRMF formula home
pages for each individual formula. We demonstrate this process using selected
chapters from the book “Hypergeometric Orthogonal Polynomials and their
$q$-Analogues” (2010) by Koekoek, Lesky and Swarttouw (KLS) as well as an
actively maintained addendum to this book by Koornwinder (KLSadd). The generic
input KLS and KLSadd LaTeX sources describe the printed representation of the
formulae, but does not contain explicit semantic information. See
http://drmf.wmflabs.org.

##  1 Introduction

Formula home pages are the principal conceptual objects for the DRMF project.
These should contain the full context-free semantic information concerning
individual orthogonal polynomial and special function (OPSF) formulae. The
DRMF is designed for a mathematically literate audience and should (1)
facilitate interaction among a community of mathematicians and scientists
interested in compendia formulae data for orthogonal polynomials and special
functions; (2) be expandable, allowing the input of new formulae from the
literature; (3) represent the context-free full semantic information
concerning individual formulae; (4) have a user friendly, consistent, and
hyperlinkable viewpoint and authoring perspective; (5) contain easily
searchable mathematics; and (6) take advantage of modern MathML tools for
easy-to-read, scalably rendered content driven mathematics. In this paper we
will discuss the DRMF seeding projects whose goal is to import data, for
example, from traditional print media (cf. Figure 1).

ptplainLaTeXsourceDLMF and
DRMFmacroreplacementFormulametadataincorporationDLMF LaTeX sourceReview
andPackaging ProcessWikixmlDump Figure 1: Data flow of seeding projects. For
most of the input LaTeX source distributions, DLMF and DRMF macros are not
incorporated. For the DLMF LaTeX source, the DLMF macros are already
incorporated.

We are investigating various sources for seed material in the DRMF [3]. We
have been given permission to use a variety of input resources to generate our
online compendium of mathematical formulae. The current sources that we are
incorporating into the DRMF are given as follows: (1) NIST Digital Library of
Mathematical Functions (DLMF111We use the typewriter font in this document to
refer to our seeding datasets.) [6, 1]; (2) Chapters 1, 9, and 14 (a total of
228 pages with about 1800 formulae) from the Springer-Verlag book
“Hypergeometric Orthogonal Polynomials and their $q$-Analogues” (2010) by
Koekoek, Lesky and Swarttouw (KLS) [7]; (3) Tom Koornwinder’s Additions to the
formula lists in “Hypergeometric orthogonal polynomials and their
$q$-Analogues” by Koekoek, Lesky and Swarttouw (KLSadd) [10]; (4) Wolfram
Computational Knowledge of Continued Fractions Project (eCF); and the Bateman
Manuscript Project (BMP) [5, 4] (see Table 1). Note that the DLMF, KLS,
KLSadd, and eCF datasets are currently being processed within our pipeline.
For the BMP dataset, we have furnished high-quality print scans to Alan Sexton
and are currently waiting on the math OCR generated LaTeX output for this
dataset which is currently being generated. In this paper we focus on DRMF
seeding of generic LaTeX sources, namely those which do not contain explicit
semantic information.

Table 1: Overview of the first three stages of the DRMF project. Note that the numbers which are given are rough estimates. |  Stage 1 |  |  Stage 2 |  |  Stage 3
---|---|---|---|---|---
Started in | 2013 |  | 2014 |  |  2015
Dataset |  | DLMF,
---
semantic LaTeX
|  | KLS,
---
plain LaTeX
|  | eCF: Mathematica
---
BMP: book images
| Semantic
---
enrichment
| identify constraints,
---
substitutions,
notes, names,
proofs, …
|  | add
---
new
semantic
macros
|  | image recognition
---
macro suggestion
Technologies |  | manual review,
---
rule-based
approaches
| improved rules |  |  | natural language
---
processing and
machine learning
| Number of
---
formula
home pages
500 |  | 1500 |  | 5000
| Human time
---
per formula
homepage
10 minutes |  | 5 minutes |  | 1 minute
| Test corpora
---
contribution
| gold standard
---
for constraint
and proof
detection
|  | gold standard
---
for
macro
replacement
|  | evaluation
---
metrics

##  2 Seeding with Generic LaTeX Sources

DRMF seeding projects collect and stream OPSF mathematical formulae into
formula pages. Formula pages are classified into those which list formulae in
a broad category, and the individual formula home pages for each formula.
Generated formula home pages are required to contain bibliographic information
and usually contain a list of symbols, substitutions and constraints required
by the formulae, proofs and formula names if available, as well as related
notes. Every semantic formula entity (e.g., function, polynomial, sequence,
operator, constant or set) has a unique name and a link to its definition or
description.

For LaTeX sources which are extracted from the DLMF project, the semantic
macros are already incorporated [11]. However, for generic sources such as the
KLS dataset, the semantic macros need to be inserted in replacement for the
LaTeX source which represents that mathematical object.

Here we give representative examples for the trigonometric sine function,
gamma function, Jacobi polynomial and little $q$-Laguerre/Wall polynomials,
which are rendered respectively as $\sin z$, $\Gamma(z)$,
$P_{n}^{(\alpha,\beta)}(x)$, and $p_{n}(x;a|q)$. These functions and
orthogonal polynomials have LaTeX presentations given respectively by \sin z,
\Gamma(z), P_n^{(\alpha,\beta)}(x), and p_n(x;a|q). The semantic
representations for these functions and orthogonal polynomials are given
respectively by \sin@@{z}, \EulerGamma@{z}, \Jacobi{\alpha}{\beta} {n}@{x},
\littleqLaguerre{n}@{x}{a}{q}. The arguments before the @ or @@ symbols are
parameters and the arguments after the @ or @@ symbol are in the domain of the
functions and orthogonal polynomials. The different between the @ or @@
symbols indicates a specified difference in presentation, such as the
inclusion of the parentheses or not in our trigonometric sine example. For the
little $q$-Laguerre polynomials, one has three arguments within parentheses.
These three arguments are separated by a semi-colon and a vertical bar. Our
macro replacement algorithm indentifies these polynomials, and then extracts
the information about what the contents of each argument is. Furthermore there
are many ways in LaTeX to represent open and close parenthese, our algorithm
identifies these. Also, since the vertical bar in LaTeX can be represented by
‘$|$’ or ‘\mid’, we search for both of these patterns. Our algorithm, for
instance, also searches for and removes all LaTeX white-space characters such
as those given by \, \\! or \hspace{}. There are many other details about
making our search and replace work, which we will not mention here.

##  3 KLS Seeding Project

In this section we describe how we augment the input KLS LaTeX source in order
to generate formula pages (see Figure 1). We are developing software processes
input LaTeX source to generate output LaTeX source with semantic mathematical
macros incorporated. The semantic LaTeX macros that we are using (664 total
with 147 currently being used for the DRMF project) are being developed by
NIST for use in the DLMF and DRMF projects. Whenever possible, we use the
standardized definitions from the NIST Digital Library of Mathematical
Functions [6]. If the definitions are not available on the DLMF website, then
we link to definition pages in the DRMF with included symbols lists. One main
goal of this seeding project is to incorporate mathematical semantic
information directly into the LaTeX source. The advantage of incorporating
this information directly into the LaTeX source is that mathematicians are
capable of editing LaTeX whereas human editing of MathML is not feasible. This
enriched information can be further modified by mathematicians using their
regular working environment.

For the 3 chapters of the KLS dataset plus the KLSadd dataset, a total number
of 89 semantic macros were replaced a total of 3308 times. That’s an average
of $1.84$ macros replaced per formula. Note that the KLSadd dataset is
actively being maintained, and when a new version of it is published, in an
automated fashion, incorporate this new information into the DRMF. This
fraction will increase when more algebraic substitution formulae are included
as formula metadata. The most common macro replacements are given as follows.
The macro for the cosine function, Racah polynomial, Pochhammer symbol,
$q$-hypergeometric function, Euler gamma function, and $q$-Pochhammer symbol
were converted a total number of times equal to 117, 205, 237, 266, and 659.
Our current conversions, which use a rule based approach, can be quite
complicated due to the nature of the variety of combinations of LaTeX input
for various OPSF objects. In LaTeX there are many ways of representing
parentheses which are usually used for function arguments. Also, there are
many ways to represent spacing delimiters which can mostly be ignored as far
as representing the common semantic information for a mathematical function
call. Our software canonicalizes these additional meaningless degrees of
freedom and generates easy-to-read semantic LaTeX source and improves the
rendering. Developing automatic software which performs macro replacements for
OPSF functions in LaTeX is a challenging task. The current status of our rule-
based approach is highly tailored to our specific KLS and KLSadd input LaTeX
source.

Historically, the desired need for formal consistency has driven
mathematicians to adopt consistent and unique notations [2]. This is extremely
beneficial in the long run. We have interacted on a regular basis with the
authors of the KLS and KLSadd datasets. They agree that our assumptions about
consistent notations are correct and they consider using our semantic LaTeX
macros in future volumes. Certainly the benefit of using these macros in
communicating with different computer systems is clear.

Once semantic macros are incorporated, the next task is to identify formula
metadata. Formula metadata can be identified within and must be associated
with formulae. One must then identify semantic information for the formula
within the surrounding text to produce formula annotations which describe this
semantic information. There are annotations which can be summarized as
constraints, substitutions, proofs and formula names if available, as well as
related notes. The automated extraction of formula metadata is a challenging
aspect of the seeding project and future computer implementations might use
machine learning methods to achieve this goal. However, we have built
automated algorithms to extract formula metadata. We have for instance
identified substitutions by associating definitions for algebraic or OPSF
functions which are utilized in surrounding formulae. The automation process
continues by merging these substitution formulae as annotations in the
original formulae which use them. Another extraction algorithm we have
developed is the identification of related variables, understanding their
dependencies and merging corresponding annotations with the pre-existing
formula metadata. We have manually reviewed the printed mathematics to
identify formula metadata. After we have exhausted our current rule-based
approach for extracting the formula annotations, we will perform the manual
insertion of the missing identified annotations into the LaTeX source. This
will then be followed by careful checking and expert editorial review. This
also evaluates the quality of our rule-based approach and creates a gold
standard for future programs.

Once the formula metadata has been completely extracted from the text, then
the remainder of the text should be removed and one is left with a list of
LaTeX formulae with associated metadata. From this list (at the current stage
of our project), we use this semantic LaTeX source to generate Wikitext. One
of the features of the generated Wikitext is that we use a glossary that we
have developed of our DLMF and DRMF macros to identify semantic macros within
a formula and its associated metadata. Presentation and meaningful content
MathML is generated from the DLMF and DRMF macros using a customized LaTeXML
server (http://gw125.iu.xsede.org) hosted by the XSEDE project that includes
all generated semantic macros. From this glossary, we generate symbols lists
for each formula which uses recognized symbols. The generated Wikitext is
converted to the MediaWiki xml-Dump format, which is then bulk imported to our
wiki instance. Our DRMF Wiki has been optimized for MathML-output. Because we
are using Mathoid to render mathematical expressions [14], browsers without
MathML-support can display DRMF formulae within MediaWiki. However, some
MathML-related features (such as copying parts of the MathML output) are not
available on these browsers.

At the moment, There are 1282 KLS and KLSadd wikitext pages. The current
number of KLS and KLSadd formula home pages is 1219 and the percentage of non-
empty symbols lists in formula home pages is given by 98.6 percent. This
number will increase as we continue to merge substitution formulae into
associated metadata and as we continue to expand our macro replacement effort.
We have detected 208 substitutions which originally appeared as formulae. We
inserted these in an automated fashion into 515 formulae. The goal of our
learning is to obtain a mostly unambiguous content representation of the
mathematical OPSF formulae which we use.

##  4 Future outlook

The next seeding projects which we will focus on are those which correspond to
image and Mathematica inputs (see Table 1). We have been given permission from
Caltech to use the BMP dataset within the DRMF. In the BMP dataset, the
original source for data are printed pages of books. We are currently
collaborating on the development of mathematical optical character recognition
(OCR) software [15] for use in this project. We plan to utilize this math OCR
software to generate LaTeX output which will be incorporated with the DLMF and
DRMF semantic macros using our developed macro replacement software.

We are already developing for our next source, namely the incorporation of the
Wolfram eCF dataset into the DRMF. We have been furnished the Mathematica
source (also known as Wolfram language) for this dataset and we are currently
developing software which translates in both directions from the Wolfram
language to our semantic LaTeX source with DRMF and DLMF macros incorporated
(cf. Table 1).

For the DLMF source, due to the hard efforts of the DLMF team for more than
the past ten years, we already have semantic macros implemented, and all that
remains is to extract the metadata from the text associated with formulae,
removing the text after the content has been transferred, converting formulae
information in tables to lists of distinct formulae, and generating formula
home pages. We already have mostly achieved this for DLMF Chapter 25 on the
Riemann Zeta function and are currently at work on Chapters 5 (gamma
function), 15 (hypergeometric function), 16 (generalized hypergeometric
functions), 17 ($q$-hypergeometric and related functions) and 18 (orthogonal
polynomials) which will ultimately be merged with the KLS and KLSadd datasets.
Then we will continue to the remainder of the DLMF chapters.

Once semantic information has been inserted into the LaTeX source, there is a
huge number of possibilities on how this information can be used. Given that
our datasets are collections of OPSF formulae, we plan on taking advantage of
the incorporated semantic information as an exploratory tool for symbolic and
numerical experiments. For instance, one may use this semantic content to
translate to computer algebra system (CAS) computer languages such as those
used by Mathematica, Maple or Sage. One could then use the translated formulae
while taking advantage of any of the features available in those software
packages. We should also mention that the DRMF seeding projects generate real
content MathML. This has been a huge problem for Mathematics Information
Retrieval research for many years [12, 9]. One major contribution of the DRMF
seeding projects is that they offer quite reasonable content MathML.

From a methodological point of view, we are going to develop evaluation
metrics that measure the degree of semantic formula enrichment. These should
be able to evaluate new approaches such as mathematical language processing
[13] and/or machine learning approaches based on the created gold standard.
Additionally, we are considering the use of sTeX [8], in order to simplify the
definition of new macros. Eventually, we can also develop a heuristic which
suggests new semantic macros based on statistical analysis.

Acknowledgements 222The mention of specific products, trademarks, or brand
names is for purposes of identification only. Such mention is not to be
interpreted in any way as an endorsement or certification of such products or
brands by the National Institute of Standards and Technology, nor does it
imply that the products so identified are necessarily the best available for
the purpose. All trademarks mentioned herein belong to their respective
owners.
We are indebted to Wikimedia Labs, the XSEDE project, Springer-Verlag, the
California Institute of Technology, and Wolfram Research Inc. for their
contributions and continued support. We would also like to thank Roelof
Koekoek, Tom Koornwinder, Roberto Costas-Santos, Eric Weisstein, Dan Lozier,
Alan Sexton, Bruce Miller, Abdou Youssef, Charles Clark, Volker Markl, George
Andrews, Mourad Ismail, and Dmitry Karp for their advice, invaluable
assistance, and support.

## References

  * [1] NIST Digital Library of Mathematical Functions.  http://dlmf.nist.gov, Release 1.0.9 of 2014-08-29.  Online companion to [6].
  * [2] G. E. Andrews, R. Askey, and R. Roy.  Special functions, volume 71 of Encyclopedia of Mathematics and its Applications.  Cambridge University Press, Cambridge, 1999.
  * [3] H. S. Cohl, M. A. McClain, B. V. Saunders, M. Schubotz, and J. C. Williams.  Digital Repository of Mathematical Formulae.  In S. M. Watt, J. H. Davenport, A. P. Sexton, P. Sojka, J. Urban, editor, Intelligent Computer Mathematics, Lecture Notes in Artificial Intelligence 8543, pages 419--422. Springer, 2014.
  * [4] A. Erdélyi, W. Magnus, F. Oberhettinger, and F. G. Tricomi.  Tables of integral transforms. Vols. 1-2.  McGraw-Hill Book Company, Inc., New York-Toronto-London, 1954.
  * [5] A. Erdélyi, W. Magnus, F. Oberhettinger, and F. G. Tricomi.  Higher transcendental functions. Vols. 1-3.  Robert E. Krieger Publishing Co. Inc., Melbourne, Fla., 1981.
  * [6] F. W. J. Olver and D. W. Lozier and R. F. Boisvert and C. W. Clark, editor.  NIST Handbook of Mathematical Functions.  Cambridge University Press, New York, NY, 2010.  Print companion to [1].
  * [7] R. Koekoek, P. A. Lesky, and R. F. Swarttouw.  Hypergeometric orthogonal polynomials and their $q$-analogues.  Springer Monographs in Mathematics. Springer-Verlag, Berlin, 2010.  With a foreword by Tom H. Koornwinder.
  * [8] M. Kohlhase.  Using LaTeX as a semantic markup format.  Mathematics in Computer Science, 2(2):279--304, 2008.
  * [9] M. Kohlhase and I. Sucan.  A search engine for mathematical formulae.  In Jacques Calmet, Tetsuo Ida, and Dongming Wang, editors, Artificial Intelligence and Symbolic Computation, volume 4120 of Lecture Notes in Computer Science, pages 241--253. Springer Berlin Heidelberg, 2006.
  * [10] T. H. Koornwinder.  Additions to the formula lists in ‘‘Hypergeometric orthogonal polynomials and their $q$-analogues’’ by Koekoek, Lesky and Swarttouw.  arXiv:1401.0815v2, 2015.
  * [11] B. R. Miller and A. Youssef.  Technical Aspects of the Digital Library of Mathematical Functions.  Annals of Mathematics and Artificial Intelligence, 38(1-3):121--136, 2003.
  * [12] M.-Q. Nghiem, G. Y. Kristianto, G. Topić, and A. Aizawa.  Which One Is Better: Presentation-Based or Content-Based Math Search?  In S. M. Watt, J. H. Davenport, A. P. Sexton, P. Sojka, and J. Urban, editors, Intelligent Computer Mathematics, volume 8543 of Lecture Notes in Computer Science, pages 200--212. Springer International Publishing, 2014.
  * [13] R. Pagel and M. Schubotz.  Mathematical Language Processing Project.  In M. England, J. H. Davenport, A. Kohlhase, M. Kohlhase, P. Libbrecht, W. Neuper, P. Quaresma, A. P. Sexton, P. Sojka, J. Urban, and S. M. Watt, editors.  Joint Proceedings of the MathUI, OpenMath and ThEdu Workshops and Work in Progress track at CICM co-located with Conferences on Intelligent Computer Mathematics (CICM 2014), Coimbra, Portugal, July 7-11, 2014, volume 1186 of CEUR Workshop Proceedings. http://CEUR-WS.org, 2014.
  * [14] M. Schubotz and G. Wicke.  Mathoid: Robust, Scalable, Fast and Accessible Math Rendering for Wikipedia.  In Stephen M. Watt, James H. Davenport, Alan P. Sexton, Petr Sojka, and Josef Urban, editors, Intelligent Computer Mathematics, volume 8543 of Lecture Notes in Computer Science, pages 224--235. Springer International Publishing, 2014.
  * [15] A. P. Sexton.  Abramowitz and Stegun - a resource for mathematical document analysis.  In Johan Jeuring, John Campbell, Jacques Carette, Gabriel Dos Reis, Petr Sojka, Makarius Wenzel, and Volker Sorge, editors, Conferences on Intelligent Computer Mathematics (CICM 2012), volume 7362 of Lecture Notes in Computer Science, pages 159--168. Springer Berlin/Heidelberg, 2012.