# Enabling Arbitrary Translation Objectives with Adaptive Tree Search

Wang Ling$\;\,{}^{\dagger}$
Talka, Inc.
<EMAIL_ADDRESS>
&Wojciech Stokowiec∗, Domenic Donato, Laurent Sartran,
Lei Yu & Chris Dyer
DeepMind, Ltd.
{wstokowiec,domenicd,lsartran,leiyu,cdyer}
@deepmind.com
&Austin Matthews
Amazon.com
<EMAIL_ADDRESS>Authors contributed
equally.${}\quad\qquad{}^{\dagger}\,$Work carried out while Wang Ling was at
DeepMind.

###### Abstract

We introduce an adaptive tree search algorithm, that can find high-scoring
outputs under translation models that make no assumptions about the form or
structure of the search objective. This algorithm – a deterministic variant of
Monte Carlo tree search – enables the exploration of new kinds of models that
are unencumbered by constraints imposed to make decoding tractable, such as
autoregressivity or conditional independence assumptions. When applied to
autoregressive models, our algorithm has different biases than beam search
has, which enables a new analysis of the role of decoding bias in
autoregressive models. Empirically, we show that our adaptive tree search
algorithm finds outputs with substantially better model scores compared to
beam search in autoregressive models, and compared to reranking techniques in
models whose scores do not decompose additively with respect to the words in
the output. We also characterise the correlation of several translation model
objectives with respect to BLEU. We find that while some standard models are
poorly calibrated and benefit from the beam search bias, other often more
robust models (autoregressive models tuned to maximize expected automatic
metric scores, the noisy channel model and a newly proposed objective) benefit
from increasing amounts of search using our proposed decoder, whereas the beam
search bias limits the improvements obtained from such objectives. Thus, we
argue that as models improve, the improvements may be masked by over-reliance
on beam search or reranking based methods.

##  1 Introduction

Conditional text generation tasks, such as machine translation, consist of two
parts: a model that assigns scores to candidate outputs, and a search
component that interacts with the model in order to find an output that
maximizes the score assigned by the model. This search problem is a hard
combinatorial optimization problem, and as a result, constraints are
frequently imposed on the structure of the model to make solving or
approximating the search problem easier. In neural machine translation, an
autoregressive factorization of the output probability distribution is widely
used (Kalchbrenner & Blunsom, 2013; Sutskever et al., 2014; Vaswani et al.,
2017), and a variety of conditional independence assumptions are made in other
model classes from statistical translation models (Brown et al., 1993; Koehn
et al., 2003) to non-autoregressive neural models (Lee et al., 2018). Although
these assumptions enable fast and accurate approximations to the search
problem with simple and efficient algorithms (e.g., beam search), which can be
crucial for efficient production applications, they limit the form of the
models and thereby restricting the kinds of architectures that can be used to
address observed model failures.

Despite the algorithmic benefits that beam search provides, we argue that it
is a poor foundation for long-term scientific progress toward an accurate and
reliable translation model whose scores adequately predict translation
quality. First, it can only be applied to autoregressive models, which have
well-known length calibration problems due to a tendency to drop or
“hallucinate” content, and this tendency has been remarkably resistant to
remedy across a variety of different autoregressive architectures (Koehn &
Knowles, 2017; Lin et al., 2020). The existing heuristic solutions—e.g., non-
local corrections to the search objective at decoding time, or global
statistics about the population of per-word probabilities (Wu et al., 2016;
Meister et al., 2020)—point to non-autoregressive components in the search
objective as necessary parts of the solution.111In this paper, we will use the
term non-autoregressive to refer to any model whose scores do not decompose
additively with the words in the output sequence. These include models that
make conditional independence assumptions and generate each word independent
of the others (Lee et al., 2018), but also energy based models that require a
complete translation hypothesis to compute a score, and models that make a
Bayes’ rule decomposition of the translation probability. We therefore would
like to directly work with model classes that contain these solutions, rather
than being dependent on limited heuristics that are imposed after the fact.
Second, beam search is strongly biased towards translations that yield high
initial scores due to the heuristic used to score partial translations
(Stahlberg & Byrne, 2019; Meister et al., 2020). While this feature provides
short term translation quality gains as it addresses many of the calibration
issues in autoregressive models, it is undesirable in the longer term as it
masks many modeling issues that need addressing. More importantly, as
scientific progress drives better correlations between model scores and
translation quality, search errors caused by this bias will inevitably have a
negative impact on both model scores and translation quality.

To address these shortcomings, we introduce the beam adaptive tree search
(BATS) algorithm, which is based on Monte Carlo tree search (Coulom, 2006;
Browne et al., 2012). Like MCTS, BATS estimates the value of internal nodes
(i.e., partial translations) in the search tree with estimates from an
expected-outcome model based on playouts from an auxiliary model, and these
estimates are refined as the search progresses. Because BATS is guided from
the start by the true objective—whether autoregressive or not, and due to the
refinement of initial score estimates, the BATS decoder exhibits fewer biases
as the search budget increases than beam search or reranking algorithms.

Our experimental section aims to characterise the impact of decoding
mechanisms on both non-autoregressive and autoregressive models. For
autoregressive models, we show that the calibration issues in autoregressive
models can be addressed by adding a non-autoregressive component that augments
the autoregressive sequence score with the lowest scoring produced token in
the autoregressive decomposition of the sequence, which we name max rank. We
further show that existing non-autoregressive approaches, such as the “noisy
channel” model (Yu et al., 2017; Yee et al., 2019; Ng et al., 2019; Yu et al.,
2020b; a; Liu et al., 2021), which factorize the translation probability
according to Bayes’ rule and have been argued to be better calibrated, are (1)
poorly optimized by standard reranking-based approaches, and (2) ultimately
have similar calibration failures as neural autoregressive models have.
Incorporating the max rank component to existing objectives benefits both beam
search and BATS, but the latter yields both the best translation and model
scores. Crucially, we show that our decoder can search substantially longer
and achieve higher model scores before BLEU starts to deteriorate, which
suggests a negative impact of the search bias in beam search. Finally, we show
that once autoregressive models become robust enough to address the
calibration issues, this bias has an equally negative impact on translation
quality. By fine-tuning an autoregressive model to better correlate with BLEU
using minimum risk training (Shen et al., 2016), we show that BATS can achieve
higher translation quality and a better model score compared to beam search.

##  2 Background

###  2.1 Beam Search

Translation tasks operate on the space of possible translations
$\mathcal{Y}=\Sigma^{*}\circ\\{\textsc{eos}\\}$ where $\Sigma$ is a finite
vocabulary, and eos is a symbol represents the end of a sequence. Elements in
$\mathcal{Y}$ correspond to full sentences $\bm{y}=y_{1},\ldots,y_{n}$ with
$n-1$ tokens, where $y_{n}=\textsc{eos}$ (end of sentence). Each translation
$\bm{y}$ is conditioned on a source sentence $\bm{x}$ and is assigned a score
$s(\bm{x},\bm{y})$, which measures how well $\bm{x}$ translates to $\bm{y}$.
Decoding algorithms aim to find the best hypothesis $\bm{y}^{*}\in\mathcal{Y}$
under the search objective $s(\bm{x},\bm{y})$. While autoregressive models may
assign scores to prefixes of translations, we only assume that $s$ is well
defined for full translations, $\bm{y}\in\mathcal{Y}$. In the particular case
of machine translation under standard autoregressive models, the search
objective is defined as the conditional log probability:

$\displaystyle s_{\textrm{AR}}(\bm{x},\bm{y})=\log
p(\bm{y}\mid\bm{x})=\sum_{i=1}^{|\bm{y}|}\log p(y_{i}\mid
y_{1},\ldots,y_{i-1},\bm{x}).$

As autoregressive models have probability emissions at the token level, the
search problem can be cast into a shortest path problem for weighted graphs,
where each node $p$ is identified by a sequence $\bm{y}^{(p)}$. Nodes define
an additional space $\mathcal{Y}^{*}$ including $\mathcal{Y}$ as well as
partial translations in $\Sigma^{*}$ that do not terminate with a eos token.
Each node contains $|\Sigma|+1$ edges, each appending a different word
$y_{i}\in\Sigma\cup\\{\textsc{eos}\\}$ to $\bm{y}^{(p)}$ generating a new node
$p\circ y_{i}$. Edge weights are given by the emission log probability $\log
p(y_{i}\mid\bm{y}^{(p)},\bm{x})$ according to the autoregressive model. Search
starts from the root node $\varepsilon$ with an empty sequence and nodes that
generate the eos token have a single edged with weight 0 that lead to a single
shared terminal node. One solution to this problem is A∗ search (Hart et al.,
1968), which is a best-first algorithm that iteratively searches nodes $p$
with the highest value $\hat{v}(p)=c(p)+f(p)$, where $c(p)$ is the sum of
weights of all edges from $\varepsilon$ to $p$, and $f(p)$ is a heuristic
function that attempts to estimate the sum of the edges on the highest scoring
path from $p$ to the terminal node.

Although theoretically appealing, good A∗ heuristics are difficult to obtain,
and search can be extremely expensive with poor heuristics. To remedy this,
beam search introduces approximations. Rather than a best-first traversal,
beam search proceeds iteratively along a frontier at a certain depth.
Exploration is limited to $b$ nodes at each depth, where $b$ is selected as a
hyperparameter that trades search accuracy (in terms of model score) for
speed. From depth 0 composed of just root node $\varepsilon$ until a maximum
depth limit $Y$ is reached, or another stopping criteria is reached (Klein et
al., 2017), beam search progressively scores all children of the nodes at the
current depth and prunes all generated nodes except for the top scoring $b$
nodes. Beam search scores each node with only the current cost
$\hat{v}(p)=c(p)$, and, in the case of neural machine translation, setting
$f(p)=0$. Discarding the future cost biases search towards nodes with high
scores without regard to whether they lead to a good path to the terminal
state. Thus, a large space of potentially good translations with low initial
scores is never explored. Examples include re-orderings that place high-
entropy words at the start of the sentence or shorter sentence constructions
(e.g. “Help me” vs. “Lend me a hand”).

Interestingly, autoregressive models tend to overestimate the probability of
short and ungrammatical translations that do not translate the entirety of the
source sentence, which are pruned by this scoring heuristic (Stahlberg &
Byrne, 2019; Holtzman et al., 2019). Thus, while $b$ may be set low to
increase speed, it is often set low to improve translation _quality_. However,
we believe that model changes evaluated with beam search’s biases may be
obscured. We seek to propose modeling improvements to mitigate degenerate
solutions, such that search quality and model quality are aligned.

###  2.2 Monte Carlo Tree Search

In Monte Carlo tree search (Coulom, 2006, MCTS), the Monte Carlo method
replaces the heuristically driven measure of value $\hat{v}(p)$ for a node $p$
with an expected-outcome model based on random game playouts. For instance,
given a node $p$ representing a state of a game, one can assign a value to $p$
by randomly playing from that state a certain number of times and computing
the average score obtained from the playouts. Thus, no burden is placed on the
form of the objective function, allowing the definition of arbitrary complex
objectives (e.g. winner of a chess game). Additionally, as each playout yields
a possible terminal state, both current $c(p)$ and future costs $f(p)$ are
naturally embedded within the obtained estimate. Unlike beam search and A∗
search, where the search direction is determined by value $\hat{v}(p)$, MCTS
diversifies the search space by allocating budget to less explored areas in
the search space (Kocsis & Szepesvári, 2006), and continually refines value
estimates.

##  3 Adaptive Tree Search For Text Generation

While MCTS (Coulom, 2006) can be directly applied to decode arbitrary
translation objectives, the heuristics defined in MCTS are optimised for
environments where the computational cost of the scoring function
$s(\bm{x},\bm{y})$ is low. For instance, the playout heuristic $\hat{v}$ in
the game of go (Silver et al., 2016) runs hundreds of thousands of playouts,
which can be computed in less than a second. In neural text generation the
scoring function frequently requires the computation of a neural network
forward step, such as a log-probability computed using an autoregressive
model, rendering these practices prohibitive. One option is to rely on a
heuristic to generate samples to train a neural network that estimates
$\hat{v}$ (Leblond et al., 2021). However this has been shown to be
challenging as model scores are difficult to estimate. Instead, we describe a
variant of MCTS optimised on decoding text generation.

###  3.1 Deterministic Playout Heuristic

We start by establishing our playout function $\hat{v}(p)$, which is used as
an initializer for node values. While the Monte Carlo method is effective at
accurately estimating the value of a given sequence by performing multiple
random playouts, such practice is infeasible as each of the playouts needs to
be scored using the scoring function $s(\bm{x},\bm{y})$, which we expect will
be prohibitively expensive. Furthermore, chances that grammatical translations
are sampled using this process are extremely low due to the sparsity of high-
quality translations in $\mathcal{Y}$. Thus, rather than multiple random
playouts, we estimate the cost of a given node using a single _informed_
playout, which is guided by greedy decoding using an autoregressive model.
Therefore, given a node $p$ with prefix $y^{(p)}$, we compute $\hat{v}(p)$ by
recursively selecting the highest probability token $y$ according to an
autoregressive model $p(y\mid y^{(p)}_{1},\ldots,y^{(p)}_{i},\bm{x})$, and
scoring the translation using the objective function $s(\bm{x},\bm{y})$.

This also implies our approach does not employ the Monte Carlo estimates and
the decoding method is fully deterministic. The progression of the value
estimates relies only on the refinement of the initial value estimates
performed as the tree expands introduced in MCTS. Therefore, we will refer to
our algorithm as an adaptive tree search (ATS) algorithm.

###  3.2 Adaptive Tree Search with a modified UCT Criteria

ATS operates on search trees instead of weighted graphs. A search tree covers
the space of all possible full and partial translations $\mathcal{Y}^{*}$, and
each node encodes a particular sequence $\bm{y}^{(p)}$. Nodes have
$|\Sigma|+1$ children, each appending a new word
$y\in\Sigma\cup\\{\textsc{eos}\\}$ to the sequence $\bm{y}^{(p)}$. We denote
the child resulting from concatenating $y$ to $p$ as $p\circ y$. The child of
a node that selects the eos symbol is a terminal node, which is associated
with a element in $\Sigma^{*}$, and therefore, can be scored using the
objective $s(\bm{x},\bm{y})$. Each node stores the number of visits $n^{(p)}$
and its current value estimate $v^{(p)}$, which can be reassigned during
search. Nodes that have not been inserted in the tree have $n^{(p)}=0$ and no
estimate for $v^{(p)}$.

Search starts with the root node $\varepsilon$ with visit count
$n^{(\varepsilon)}=1$ and value $v^{(\varepsilon)}=\hat{v}(\varepsilon)$,
which corresponds to the score obtained by translating $\bm{x}$ with greedy
decoding. Afterwards the tree expands in an iterative manner, where each
iteration expands the search tree and updates its statistics.

Similar to the selection and expansion steps in ATS, we traverse the
instantiated tree, starting from $\varepsilon$ on the basis of the current
estimated values $v$, together with confidence about the quality of the
estimates. We recursively traverse the tree and select the child $p\circ y$
with the highest score according to the continuous upper confidence tree
criterion (Auger et al., 2013):

$\displaystyle\mathrm{UCT}(p,y)$ $\displaystyle=\bar{v}{(p\circ
y)}+C{\frac{\sqrt{n^{(p)}}}{1+n^{(p\circ y)}}}\pi(y\mid\bm{y}^{(p)}),$ (1)

where $C$ is a hyperparameter weighting two terms. The first term
$\bar{v}{(p\circ y)}$ encourages exploitation of nodes with known high value.
The second term ${\frac{\sqrt{n^{(p)}}}{1+n^{(p\circ
y)}}}\pi(y\mid\bm{y}^{(p)})$ encourages the algorithm to explore nodes with
low visit counts more thoroughly. Here, we specify the policy as the log-
probability obtained from an autoregressive model
$\pi(y\mid\bm{y}^{(p)})=p(y\mid\bm{y}^{(p)},\bm{x})$. The value of a node is
determined by its current estimate $\bar{v}(p\circ y)=v^{(p\circ y)}$ if
$n^{(p\circ y)}>0$. For nodes not yet inserted in the tree, which have no
value estimates, we compute an estimated value as:

$\displaystyle y^{*}$ $\displaystyle=\operatorname*{arg\,max}_{\forall
y\in\Sigma,n^{(p\circ y)}>0}v^{(p\circ y)}$ $\displaystyle\bar{v}^{(p\circ
y)}$ $\displaystyle=v(p\circ
y^{*})\frac{\pi(y\mid\bm{y}^{(p)})}{\pi(y*\mid\bm{y}^{(p)})},$ (2)

where we estimate $\bar{v}^{(p\circ y)}$ by assuming that the ratio between
policies $\pi$ between $p\circ y$ and the highest value node $p\circ y^{*}$ is
the same as the ratio between their values $\bar{v}$.

The traversal terminates when a node with $n^{(p)}=0$ or a terminal node is
reached. In the former case, the node $p$ is inserted into the tree, setting
its visit count $n^{(p)}=1$ and estimating its value $v^{(p)}=\hat{v}(p)$ as
done in the simulation step in MCTS. We note here an important difference to
many other formulations of MCTS, where selection terminates at leaf nodes
(node where all $\Sigma$ have $n^{(p)}>0$), which is followed by the expansion
step that inserts a new child prior to simulation. Expanding all children of a
node is generally considered efficient in domains with a small $\Sigma$ and
low playout cost $\hat{v}(p)$, and the standard MCTS algorithm does not
attempt to optimise the subset that needs to be expanded. In the text domain,
most words in the vocabulary are not applicable as they do not fit the context
$\bm{y}^{(p)}$ and correspond to the content in the source sentence $\bm{x}$,
and can be excluded using the value estimate described in Equation 3.2.

Next, we ascend from the selected node $p\circ y$, updating visit counts and
value estimates:

$\displaystyle n^{(p)}$ $\displaystyle\leftarrow n^{(p)}+1$ $\displaystyle
v^{(p)}$ $\displaystyle\leftarrow\max\\{v^{(p)},v^{(p\circ y)}\\},$

where each parent $p$ increases its visit count $n^{(p)}$ and updates its
value estimate $v^{(p)}$ to the child’s value if a new best translation is
found. Thus, $v^{(p)}$ represents the best translation obtained in the subtree
represented by $p$. Starting from the score obtained using greedy decoding
when $v^{(p)}$ is initialised, each new traversal that passes through $p$ has
a chance to refine this initial estimate with the newly found translation.

###  3.3 Beam Adaptive Tree Search

A standard way to guarantee progression in MCTS is to run an instance of MCTS
per word. Here, we would run an ATS instance $\textsc{ATS}(\varepsilon,k)$
with $k$ iterations starting from root $\varepsilon$. Then, we set
$\varepsilon\leftarrow\varepsilon\circ y_{1}^{*}$, where
$y_{1}^{*}=\arg\max_{y\in\Sigma}v^{(\varepsilon\circ y)}$ is the child with
the highest value estimate and repeat this process until
$y_{i}^{*}=\textsc{eos}$.

However, it has been found that in text generation tasks restricting search to
a set of high value nodes rather than a single one allows such games to be
solved at a faster rate (Baier & Winands, 2012). Thus, we modify our selection
step as follows:

$\displaystyle\mathrm{UCT_{\textit{constrained}}}(p,y,d_{\textit{min}})$
$\displaystyle=\left\\{\begin{matrix}\mathrm{UCT}(p,y)&d^{(p\circ
y)}>d_{\textit{min}}\\\ -\infty&\text{otherwise}\end{matrix}\right.$ (3)

where $d^{(p\circ y)}$ is initialised as $\ell(p\circ y)$, a function that
counts the number of edges required to reach the root node from $(p\circ y)$.
Then, the following update rule is added to ensure that the $d^{(p)}$ stores
that depth of the deepest node achievable from $p$:

$\displaystyle d^{(p)}$ $\displaystyle\leftarrow\max\\{d^{(p)},d^{(p\circ
y)}\\},$

where we update each node so that $d^{(p)}$ stores the value of the deepest
node that is accessible from $p$. Thus, in Equation 3, condition $d^{(p\circ
y)}>d_{\textit{min}}$ tests whether $p\circ y$ contains a node deeper than
$d_{\textit{min}}$.

We define $\text{BATS}(\varepsilon,k)$ as a Beam ATS instance that runs ATS
starting from the root node $\varepsilon$ with the selection criteria
$\mathrm{UCT_{\textit{constrained}}}$ with $d_{\textit{min}}=0$ and gradually
increasing $d_{\textit{min}}$ by 1 every $k$ iterations. Search stops when no
node satisfies $d^{(p\circ y)}>d_{\textit{min}}$ or until a maximum depth
$d_{\textit{max}}$.

##  4 Objectives

As decoding with a decoder on vanilla autoregressive models is unlikely to
yield translations with quality superior to beam search, as the beam search
bias is essential to overcoming the calibration issues in these models, we
propose modeling improvements in order to address these shortcomings.

###  4.1 Max Rank

Decoding in autoregressive models generally optimises a normalised log
probability (Wu et al., 2016), $\left(\log
p(\bm{y}\mid\bm{x})\right)(\frac{6}{5+|\bm{y}|})^{\alpha}$, which combines the
sum of the token level log-probabilities (when $\alpha=0$) and a length-based
adjustment, which approximates the mean of the log-probabilities as the length
$|\bm{y}|$ grows (when $\alpha=1$).

Similar to normalised log-probabilities, we consider a metric that
characterizes translation by their minimum token level log-probability. The
intuition here is that the quality of the translation is represented by the
worst decision made in the sequence. In practice, many degenerate cases in
autoregressive models are created by making a single bad decision, such as
generating a eos token prematurely or omitting translations, which can be
understood in terms of uniform information density (Meister et al., 2020).

However, the issue with the minimum of the token level log-probability is that
log-probability ranges tend to vary depending on the context and number of
translation options that are available. Thus, they are not very reflective on
the quality of the choice made as the best choice at a given timestamp could
still be the worst decision in the sequence. Instead, we optimise the
normalised rank:

$\displaystyle r(y_{i}\mid
y_{1},\ldots,y_{i-1},\bm{x})=\frac{\sum_{y\in{\Sigma}}\delta(p(y_{i}\mid
y_{1},\ldots,y_{i-1},\bm{x})>p(y\mid y_{1},\ldots,y_{i-1},\bm{x}))}{|\Sigma|}$

where we count the number of actions in $\Sigma$ with lower log-probability
than $y_{i}$. By using the rank $r$ instead of the log-probability $p$, we can
compare values within the same range at the cost of a loss in relative
precision. Thus, we name our metric max rank (MR), which is computed as
follows:

$\displaystyle\text{MR}(\bm{x},\bm{y})=\max_{i=1}^{|\bm{y}|}\log r(y_{i}\mid
y_{1},\ldots,y_{i-1},\bm{x}).$

Finally, unlike the mean and sum of log-probabilities, the max of a sequence
of log-probabilities is not autoregressive, so beam search is not applicable.

###  4.2 Noisy Channel Model

The noisy channel model uses the Bayes rule decomposition in order to
decompose the probability of a sentence $p(\bm{y}|\bm{x})$ into
$p(\bm{y}|\bm{x})=\frac{p(\bm{x}|\bm{y})p(\bm{y})}{p(\bm{x})}$ where the
channel model $p(\bm{x}|\bm{y})$ can be trained as translation model trained
in the reverse direction and $p(\bm{y})$ is a language model. Finally, the
prior $p(\bm{x})$ can be ignored in the context of a maximization problem.
Since the reverse model is not autoregressive in the space $\Sigma^{*}$, it
can bypass many of the degenerative cases in autoregressive models.

###  4.3 Minimum Risk Trained autoregressive Models

In order to show that BATS can be an attractive alternative to beam search
under autoregressive models, we need to improve the model so that the search
bias is no longer as crucial to preserving the translation quality of the
generated text. To this end, we fine-tune our models using minimum risk
training (Shen et al., 2016, MRT). The MRT training objective is designed to
minimize the empirical risk $r(\textbf{y},\textbf{y}^{\prime})$ by minimizing
it in a subset of $\Sigma^{*}$ obtained by sampling $n$ translations. This
allows the model to mitigate degenerate cases caused by optimising the
likelihood objective by fine-tuning the model on downstream metrics, such as
BLEU (Papineni et al., 2002).

##  5 Experiments

###  5.1 Setup

We conduct our experiments on the Chinese–English and Pashto–English tasks
from WMT2020 (Barrault et al., 2020), and German–English from WMT2014 (Bojar
et al., 2014), following the same training, development and test splits. Our
autoregressive model transformer baseline uses the multi-query attention model
(Shazeer, 2019). It uses the standard architecture with 6 encoder and decoder
layers with 512 hidden units, 2048 sized tied embeddings for both source and
target word projections and 8 attention heads. We tokenize the data with byte-
pair encoding (Sennrich et al., 2016) with 32K merges and set a maximum
sentence size of $Y=128$. Translation quality evaluation is performed using
sacreBLEU (Post, 2018). We choose the checkpoint that yields the highest BLEU
in the validation set using beam search with the normalisation constant
$\alpha=0.8$ and beam size $6$. We also compare a variant fine-tuned using MRT
according to the procedure described in Appendix A.3.

For the noisy channel model, we train the channel model by simply swapping the
translation direction of the autoregressive model with the same
hyperparameters. For the language model prior, we employ the TransformerXL
architecture (Dai et al., 2019) trained on 1 billion words (Chelba et al.,
2013). On non-autoregressive objectives, we use beam search as a proxy to
generate translations candidates which are rescored using the non-
autoregressive metric (Yee et al., 2019; Yu et al., 2020a). For BATS, we
simply set hyperparameter $C=1$. While optimising $C$ could lead to more
efficient optimisation of the model score, our goal is to study how model
scores are correlated with translation quality in different objectives.

The translation budget (beam size for beam search and iterations for BATS) is
swept by doubling its value starting from 1 to 256. We combine different
objective components under a log-linear model, where the weights of the
components are tuned with MERT (Och, 2003). In order for model scores to be
comparable, all weights are tuned on a pool of $256$ translations using beam
search.222Tuning $\lambda$ using BATS to genererate candidates yields similar
weights.

###  5.2 Results

Table 1 illustrates the translation quality results using BATS and beam search
on the normalised autoregressive model baseline and the optimal model (Column
“System”) for each language pair (Column “Language Pair”). We perform a grid
search over the following decisions: (1) Whether to use Max Rank (Column
“MR”), (2) Whether to use the Noisy Channel Model (Column “NC”), (3) Whether
to tune the autoregressive model using MRT (Column “MRT”), (4) Whether to use
beam search or BATS (5) The translation budget of each decoder. The
combination with the highest BLEU on the validation set is used to decode on
the test set and the BLEU scores obtained using beam search and Bats are
reported (Columns “Beam Search” and “BATS”).333The optimal models with the
highest BLEU on the validation for Beam Search and BATS are the same. We
observe that for all pairs decoding with BATS can yield gains over decoding
with beam search when using the combination of objectives with the highest
BLEU on the validation set. As expected, due to the search bias in beam
search, it does comparatively better on some language pairs, such as Chinese-
English and Pashto-English.

In terms of modeling, we note that our proposed metric, Max Rank, and the MRT
method combined yield the best results for Mandarin and German. The noisy
channel model only yields improvements in Pashto-English, when used with Max
Rank and MRT as the training data is small (500k parallel sentences) and the
model relies on the large sized language model to provide accurate
predictions.

Language Pair | System | MR | NC | MRT | Beam Search | BATS
---|---|---|---|---|---|---
Chinese–English | Baseline | No | No | No | 24.7 | 24.2
Optimal | Yes | No | Yes | 28.6 | 29.0
Pashto–English | Baseline | No | No | No | 7.5 | 7.3
Optimal | Yes | Yes | Yes | 8.1 | 9.1
German–English | Baseline | No | No | No | 30.0 | 30.0
Optimal | Yes | No | Yes | 30.3 | 31.1
Table 1: Comparison between the BLEU scores obtained using beam search and
BATS. Pairs of rows describes the results obtained using the vanilla
autoregressive model with normalisation and the best combination of models
(Max Rank, Noisy Channel and Minimum Risk Training), tuned on the validation
set. The translation budget is also tuned for each method for maximum BLEU.

###  5.3 Beam Search and BATS

We now provide a more in-depth analysis on the Chinese-English language pair,
where we believe results are more informative. Table 2 illustrates the results
obtained using some models that were explored in our grid search (Column
$s(\bm{x},\bm{y})$). For each model, we illustrate the best BLEU obtained on
the test set (Column “BLEU”), the beam size (Column “Beam”) or number of
iterations (Column “Iter”), where the best BLEU was obtained on the validation
set and the percentage improvement between results obtained using beam search
and BATS (Column “Delta”). Finally, autoregressive and non-autoregressive
models are marked with $AR$ with $NAR$, respectively. It is also important to
refer that the number of iterations in BATS and beam in beam search are not
comparable point-wise, instead we analyse the overall behavior of the model
score and BLEU curves.

##### When to use Beam Search?

In the models where beam search outperforms BATS(Rows “Log ProbabilityAR
($\alpha=0$)” and “Log ProbabilityAR ($\alpha=0.8$)”), we notice that the
search budget in both cases is always low. Figure 1 plots the evolution of the
BLEU (Top) and model score (Bottom) of both decoders as translation budget is
increased. For the normalised log-probability (Column “Log Probability
($\alpha=0.8$)”), the model scores obtained for BLEU search and BATS are very
similar. However, we an observe a large gap between the BLEU scores obtained
at the same model score. This shows that the beam search bias is filtering the
set of candidates in beam search so that they are of higher quality, even
though the model score is failing to discriminate them. Additionally, we
observe the standard BLEU curve (Stahlberg & Byrne, 2019), where after a set
of initial iterations BLEU deteriorates rapidly, which renders elaborate
decoding mechanisms unneeded. Furthermore, BATS and other MCTS-based methods
are not ideal for low search budget scenarios as they depend on high node
visit counts to accumulate enough statistics to make informed decisions. We
see in all objectives that model scores for BATS do not outperform Beam Search
until a large budget is allocated. In conclusion, if the model cannot support
high search budgets, beam search is the preferred alternative, especially if
the modeling issues can be addressed with the search bias.

##### When to use BATS?

With the addition of the noisy channel model (Row “Log Probability
($\alpha=0.8$) + NCNAR) and Max Rank (Row “Log Probability ($\alpha=0.8$) +
MRNAR”), the search budget until BLEU deteriorates for both decoders is
increased. Here, we observe that BATS is the decoding option that yields
higher BLEU and that the delta is higher when BATS can employ more iterations.

Figure 1 shows that the evolution of BLEU is considerably more stable with the
noisy channel model (Column “Log Probability ($\alpha=0.8$) + NC”) and when
Max Rank is applied (Column “Log Probability ($\alpha=0.8$) + MR”). For these
non-autoregressive models BATS yields significantly better model scores than
reranking. More interestingly, comparing the behavior of Beam Search and BATS,
similar model scores between the two methods do not yield similar BLEU scores.
In the noisy channel model, we observe that at $16$ iterations and beam size
$16$, both decoders yield similar model scores and BLEU scores. However, as
the model score increases beyond that point, the degeneration in beam search
as the score increases is significant, while BATS observes almost no
deterioration. This suggests that the beam search bias has a negative impact
in translation quality at high values of $b$ by filtering good translations
from the search space. Using Max Rank, we observe that not only BATS can
achieve considerably higher model scores as it is optimising the non-
autoregressive model directly, it also yields considerably higher BLEU scores.
In beam search, BLEU stops improving at 32 iterations even though model score
keeps increasing due to the search bias.

Finally, we observe that the search bias issue is also present when using beam
search to decode from an autoregressive model fine-tuned with MRT ( Table 2,
Row “Log Probability MRT ($\alpha=0.8)^{AR}$”). Figure 1 shows that once MRT
is applied (Column “Log Probability MRT ($\alpha=0.8$)”), not only BATS can
find significantly better model scores, but they are are associated with
better BLEU scores. Additionally, beam search stagnates after 8 iterations.

In conclusion, as translation models become more robust, there is a growing
need of better decoding mechanisms, such as BATS, in order to maximize
translation quality. We perceive that in both autoregressive and non-
autoregressive models, there is a limit to both model and BLEU scores that can
be obtained using beam search, which is partially attributed to the fact that
its search is strongly biased due to the lack of future costs.

We believe that future research will drive models to extents where translation
quality nearly perfectly matches with model scores. In an oracle setup, where
the objective is the sentence level BLEU by peeking at the reference (Row
“Oracle BLEU”), we hypothesise that the delta between beam search and BATS
would grow vastly, and observe that a delta of $39.19\%$.

| Beam Search | BATS |
---|---|---|---
$s(\bm{x},\bm{y})$ | BLEU | Beam | BLEU | Iter | Delta
Log Probability($\alpha=0$)AR | 24.7 | 2 | 24.2 | 1 | -2.0%
Log Probability($\alpha=0.8$)AR | 25.0 | 8 | 24.7 | 8 | -1.2%
Log Probability ($\alpha=0.8$) + NCNAR | 25.2 | 16 | 25.4 | 32 | 0.6%
Log Probability ($\alpha=0.8$) + MRNAR | 26.8 | 32 | 27.4 | 128 | 2.5%
Log Probability ($\alpha=0.8$) + MR + NCNAR | 26.7 | 32 | 27.4 | 128 | 2.6%
Log Probability MRT ($\alpha=0.8$)AR | 28.2 | 64 | 28.7 | 256 | 1.8%
Log Probability MRT ($\alpha=0.8$) $+MR^{NAR}$ | 28.6 | 8 | 29.0 | 256 | 1.7%
Oracle BLEUNAR | 38.6 | 256 | 53.7 | 256 | 39.2%
Table 2: Comparison between BS and MCTS on the WMT2020 Chinese-English test
set. Pairs of cells denote BLEU scores and the iteration budget achieving the
best BLEU on the validation set.

Figure 1: Comparison of BATS and beam search over different translation
budgets under different translation objectives on the WMT2020 Chinese–English
test set. Each column illustrates the BLEU (top) and the model score (bottom)
obtained using the two decoders on a different objective.

##  6 Conclusion

This paper proposes an adaptive tree search algorithm designed to optimise
arbitrary metrics. It uses rollouts from an auxiliary autoregressive model to
obtain estimates for the value estimates of internal nodes. This allows the
decoder to optimise arbitrary objectives and avoid the search biases of
manually defined heuristics, such as partial translation probability in
autoregressive models. BATS is particularly useful when models are robust
enough to allow for a higher search budget. As many existing objectives are
found to be poorly correlated with translation quality, we propose a new
metric named max rank and use existing methods, such as the noisy channel
model and minimum error rate training, to address the failure modes of vanilla
autoregressive models. Results on three language pairs are favourable to BATS
when using our proposed augmentations of the autoregressive model.
Additionally, we find that the gap in translation quality between beam search
and BATS increases as more robust models are employed. More importantly, we
observe that the search bias prevents beam search from achieving high-quality
translations as it filters good translations that are unfavoured by the search
heuristic. Thereby, the model score increases, but BLEU decreases. This shows
that beam search limits the potential of many models by establishing
translation quality ceilings unrelated to the robustness of the model, but to
the topology of the search space they establish. This suggests that as
scientific progress drives more robust models, exploring more robust decoding
methods, such as BATS, is fundamental for advancing the field of text
generation.

#### Acknowledgments

We thank Rémi Leblond, Geoffrey Irving and Phil Blunsom for useful feedback
throughout the different stages of this project.

## References

  * Auger et al. (2013) David Auger, Adrien Couëtoux, and Olivier Teytaud.  Continuous upper confidence trees with polynomial exploration - consistency.  In Hendrik Blockeel, Kristian Kersting, Siegfried Nijssen, and Filip Zelezný (eds.), _Machine Learning and Knowledge Discovery in Databases - European Conference, ECML PKDD 2013, Prague, Czech Republic, September 23-27, 2013, Proceedings, Part I_ , volume 8188 of _Lecture Notes in Computer Science_ , pp. 194–209. Springer, 2013.  doi: 10.1007/978-3-642-40988-2“˙13.  URL https://doi.org/10.1007/978-3-642-40988-2_13.
  * Baier & Winands (2012) Hendrik Baier and Mark H. M. Winands.  Beam monte-carlo tree search.  In _2012 IEEE Conference on Computational Intelligence and Games (CIG)_ , pp. 227–233, United States, September 2012. IEEE.  doi: 10.1109/CIG.2012.6374160.
  * Barrault et al. (2020) Loïc Barrault, Ondřej Bojar, Fethi Bougares, Rajen Chatterjee, Marta R. Costa-jussà, Christian Federmann, Mark Fishel, Alexander Fraser, Yvette Graham, Paco Guzman, Barry Haddow, Matthias Huck, Antonio Jimeno Yepes, Philipp Koehn, André Martins, Makoto Morishita, Christof Monz, Masaaki Nagata, Toshiaki Nakazawa, and Matteo Negri (eds.).  _Proceedings of the Fifth Conference on Machine Translation_.  Association for Computational Linguistics, Online, November 2020.  URL https://www.aclweb.org/anthology/2020.wmt-1.
  * Bojar et al. (2014) Ondřej Bojar, Christian Buck, Christian Federmann, Barry Haddow, Philipp Koehn, Johannes Leveling, Christof Monz, Pavel Pecina, Matt Post, Herve Saint-Amand, Radu Soricut, Lucia Specia, and Aleš Tamchyna.  Findings of the 2014 workshop on statistical machine translation.  In _Proceedings of the Ninth Workshop on Statistical Machine Translation_ , pp. 12–58, Baltimore, Maryland, USA, June 2014. Association for Computational Linguistics.  doi: 10.3115/v1/W14-3302.  URL https://aclanthology.org/W14-3302.
  * Brown et al. (1993) Peter F. Brown, Stephen A. Della Pietra, Vincent J. Della Pietra, and Robert L. Mercer.  The mathematics of statistical machine translation: Parameter estimation.  _Computational Linguistics_ , 19(2):263–311, 1993\.  URL https://www.aclweb.org/anthology/J93-2003.
  * Browne et al. (2012) Cameron Browne, Edward Powley, Daniel Whitehouse, Simon Lucas, Peter I. Cowling, Philipp Rohlfshagen, Stephen Tavener, Diego Perez, Spyridon Samothrakis, and Simon Colton.  A survey of monte carlo tree search methods.  _IEEE Transactions on Computational Intelligence and AI in Games_ , 4(1), Mar 2012.
  * Chelba et al. (2013) Ciprian Chelba, Tomás Mikolov, Mike Schuster, Qi Ge, Thorsten Brants, and Phillipp Koehn.  One billion word benchmark for measuring progress in statistical language modeling.  _CoRR_ , abs/1312.3005, 2013.  URL http://arxiv.org/abs/1312.3005.
  * Coulom (2006) Rémi Coulom.  Efficient Selectivity and Backup Operators in Monte-Carlo Tree Search.  In Paolo Ciancarini and H. Jaap van den Herik (eds.), _5th International Conference on Computer and Games_ , Turin, Italy, May 2006.  URL https://hal.inria.fr/inria-00116992.
  * Dai et al. (2019) Zihang Dai, Zhilin Yang, Yiming Yang, Jaime G. Carbonell, Quoc V. Le, and Ruslan Salakhutdinov.  Transformer-xl: Attentive language models beyond a fixed-length context.  _CoRR_ , abs/1901.02860, 2019.  URL http://arxiv.org/abs/1901.02860.
  * Hart et al. (1968) Peter Hart, Nils Nilsson, and Bertram Raphael.  A formal basis for the heuristic determination of minimum cost paths.  _IEEE Transactions on Systems Science and Cybernetics_ , 4(2):100–107, 1968.  doi: 10.1109/tssc.1968.300136.  URL https://doi.org/10.1109/tssc.1968.300136.
  * Holtzman et al. (2019) Ari Holtzman, Jan Buys, Maxwell Forbes, and Yejin Choi.  The curious case of neural text degeneration.  _CoRR_ , abs/1904.09751, 2019.  URL http://arxiv.org/abs/1904.09751.
  * Kalchbrenner & Blunsom (2013) Nal Kalchbrenner and Phil Blunsom.  Recurrent continuous translation models.  In _Proceedings of the 2013 Conference on Empirical Methods in Natural Language Processing_ , pp. 1700–1709, Seattle, Washington, USA, October 2013. Association for Computational Linguistics.  URL https://www.aclweb.org/anthology/D13-1176.
  * Klein et al. (2017) Guillaume Klein, Yoon Kim, Yuntian Deng, Jean Senellart, and Alexander M. Rush.  Opennmt: Open-source toolkit for neural machine translation.  _CoRR_ , abs/1701.02810, 2017.  URL http://arxiv.org/abs/1701.02810.
  * Kocsis & Szepesvári (2006) Levente Kocsis and Csaba Szepesvári.  Bandit based monte-carlo planning.  In Johannes Fürnkranz, Tobias Scheffer, and Myra Spiliopoulou (eds.), _Proceedings of the Seventeenth European Conference on Machine Learning (ECML 2006)_ , volume 4212 of _Lecture Notes in Computer Science_ , pp. 282–293, Berlin/Heidelberg, Germany, 2006. Springer.  ISBN 3-540-45375-X.  URL http://www.sztaki.hu/~szcsaba/papers/ecml06.pdf.
  * Koehn & Knowles (2017) Philipp Koehn and Rebecca Knowles.  Six challenges for neural machine translation.  In _Proceedings of the First Workshop on Neural Machine Translation_ , pp. 28–39, Vancouver, August 2017. Association for Computational Linguistics.  doi: 10.18653/v1/W17-3204.  URL https://www.aclweb.org/anthology/W17-3204.
  * Koehn et al. (2003) Philipp Koehn, Franz J. Och, and Daniel Marcu.  Statistical phrase-based translation.  In _Proceedings of the 2003 Human Language Technology Conference of the North American Chapter of the Association for Computational Linguistics_ , pp. 127–133, 2003.  URL https://www.aclweb.org/anthology/N03-1017.
  * Leblond et al. (2021) Rémi Leblond, Jean-Baptiste Alayrac, Laurent Sifre, Miruna Pislar, Jean-Baptiste Lespiau, Ioannis Antonoglou, Karen Simonyan, and Oriol Vinyals.  Machine translation decoding beyond beam search.  _CoRR_ , abs/2104.05336, 2021.  URL https://arxiv.org/abs/2104.05336.
  * Lee et al. (2018) Jason Lee, Elman Mansimov, and Kyunghyun Cho.  Deterministic non-autoregressive neural sequence modeling by iterative refinement.  In _Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing_ , pp. 1173–1182, Brussels, Belgium, October-November 2018. Association for Computational Linguistics.  doi: 10.18653/v1/D18-1149.  URL https://aclanthology.org/D18-1149.
  * Lin et al. (2020) Chu-Cheng Lin, Aaron Jaech, Xin Li, Matthew R. Gormley, and Jason Eisner.  Autoregressive modeling is misspecified for some sequence distributions.  _CoRR_ , abs/2010.11939, 2020.  URL https://arxiv.org/abs/2010.11939.
  * Liu et al. (2021) Qi Liu, Lei Yu, Laura Rimell, and Phil Blunsom and.  Pretraining the noisy channel model for task-oriented dialogue.  _Trans. Assoc. Comput. Linguistics_ , 2021.
  * Meister et al. (2020) Clara Meister, Tim Vieira, and Ryan Cotterell.  If beam search is the answer, what was the question?  _CoRR_ , abs/2010.02650, 2020.  URL https://arxiv.org/abs/2010.02650.
  * Ng et al. (2019) Nathan Ng, Kyra Yee, Alexei Baevski, Myle Ott, Michael Auli, and Sergey Edunov.  Facebook fair’s WMT19 news translation task submission.  In Ondrej Bojar, Rajen Chatterjee, Christian Federmann, Mark Fishel, Yvette Graham, Barry Haddow, Matthias Huck, Antonio Jimeno-Yepes, Philipp Koehn, André Martins, Christof Monz, Matteo Negri, Aurélie Névéol, Mariana L. Neves, Matt Post, Marco Turchi, and Karin Verspoor (eds.), _ProceedingsWMT_ , 2019.
  * Och (2003) Franz Josef Och.  Minimum error rate training in statistical machine translation.  In _Proceedings of the 41st Annual Meeting of the Association for Computational Linguistics_ , pp. 160–167, Sapporo, Japan, July 2003. Association for Computational Linguistics.  doi: 10.3115/1075096.1075117.  URL https://www.aclweb.org/anthology/P03-1021.
  * Papineni et al. (2002) Kishore Papineni, Salim Roukos, Todd Ward, and Wei-Jing Zhu.  Bleu: a method for automatic evaluation of machine translation.  In _Proceedings of the 40th Annual Meeting of the Association for Computational Linguistics_ , pp. 311–318, Philadelphia, Pennsylvania, USA, July 2002. Association for Computational Linguistics.  doi: 10.3115/1073083.1073135.  URL https://www.aclweb.org/anthology/P02-1040.
  * Popović (2015) Maja Popović.  chrF: character n-gram F-score for automatic MT evaluation.  In _Proceedings of the Tenth Workshop on Statistical Machine Translation_ , pp. 392–395, Lisbon, Portugal, September 2015. Association for Computational Linguistics.  doi: 10.18653/v1/W15-3049.  URL https://aclanthology.org/W15-3049.
  * Post (2018) Matt Post.  A call for clarity in reporting BLEU scores.  In _Proceedings of the Third Conference on Machine Translation: Research Papers_ , pp. 186–191, Brussels, Belgium, October 2018. Association for Computational Linguistics.  doi: 10.18653/v1/W18-6319.  URL https://aclanthology.org/W18-6319.
  * Sennrich et al. (2016) Rico Sennrich, Barry Haddow, and Alexandra Birch.  Neural machine translation of rare words with subword units.  In _Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pp. 1715–1725, Berlin, Germany, August 2016. Association for Computational Linguistics.  doi: 10.18653/v1/P16-1162.  URL https://www.aclweb.org/anthology/P16-1162.
  * Shazeer (2019) Noam Shazeer.  Fast transformer decoding: One write-head is all you need.  _CoRR_ , abs/1911.02150, 2019.  URL http://arxiv.org/abs/1911.02150.
  * Shen et al. (2016) Shiqi Shen, Yong Cheng, Zhongjun He, Wei He, Hua Wu, Maosong Sun, and Yang Liu.  Minimum risk training for neural machine translation.  In _Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pp. 1683–1692, Berlin, Germany, August 2016. Association for Computational Linguistics.  doi: 10.18653/v1/P16-1159.  URL https://aclanthology.org/P16-1159.
  * Silver et al. (2016) David Silver, Aja Huang, Christopher J. Maddison, Arthur Guez, Laurent Sifre, George van den Driessche, Julian Schrittwieser, Ioannis Antonoglou, Veda Panneershelvam, Marc Lanctot, Sander Dieleman, Dominik Grewe, John Nham, Nal Kalchbrenner, Ilya Sutskever, Timothy Lillicrap, Madeleine Leach, Koray Kavukcuoglu, Thore Graepel, and Demis Hassabis.  Mastering the game of go with deep neural networks and tree search.  _Nature_ , 529:484–503, 2016.  URL http://www.nature.com/nature/journal/v529/n7587/full/nature16961.html.
  * Stahlberg & Byrne (2019) Felix Stahlberg and Bill Byrne.  On NMT search errors and model errors: Cat got your tongue?  In _Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP)_ , pp. 3356–3362, Hong Kong, China, November 2019. Association for Computational Linguistics.  doi: 10.18653/v1/D19-1331.  URL https://www.aclweb.org/anthology/D19-1331.
  * Sutskever et al. (2014) Ilya Sutskever, Oriol Vinyals, and Quoc V Le.  Sequence to sequence learning with neural networks.  In Z. Ghahramani, M. Welling, C. Cortes, N. Lawrence, and K. Q. Weinberger (eds.), _Advances in Neural Information Processing Systems_ , volume 27. Curran Associates, Inc., 2014.  URL https://proceedings.neurips.cc/paper/2014/file/a14ac55a4f27472c5d894ec1c3c743d2-Paper.pdf.
  * Vaswani et al. (2017) Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, and Illia Polosukhin.  Attention is all you need.  _CoRR_ , abs/1706.03762, 2017.  URL http://arxiv.org/abs/1706.03762.
  * Wu et al. (2016) Yonghui Wu, Mike Schuster, Zhifeng Chen, Quoc V. Le, Mohammad Norouzi, Wolfgang Macherey, Maxim Krikun, Yuan Cao, Qin Gao, Klaus Macherey, Jeff Klingner, Apurva Shah, Melvin Johnson, Xiaobing Liu, Łukasz Kaiser, Stephan Gouws, Yoshikiyo Kato, Taku Kudo, Hideto Kazawa, Keith Stevens, George Kurian, Nishant Patil, Wei Wang, Cliff Young, Jason Smith, Jason Riesa, Alex Rudnick, Oriol Vinyals, Greg Corrado, Macduff Hughes, and Jeffrey Dean.  Google’s neural machine translation system: Bridging the gap between human and machine translation.  _CoRR_ , abs/1609.08144, 2016.  URL http://arxiv.org/abs/1609.08144.
  * Yee et al. (2019) Kyra Yee, Yann N. Dauphin, and Michael Auli.  Simple and effective noisy channel modeling for neural machine translation.  In Kentaro Inui, Jing Jiang, Vincent Ng, and Xiaojun Wan (eds.), _Proceedings of EMNLP_ , 2019.
  * Yu et al. (2017) Lei Yu, Phil Blunsom, Chris Dyer, Edward Grefenstette, and Tomás Kociský.  The neural noisy channel.  In _Proceedings of ICLR_ , 2017.
  * Yu et al. (2020a) Lei Yu, Laurent Sartran, Po-Sen Huang, Wojciech Stokowiec, Domenic Donato, Srivatsan Srinivasan, Alek Andreev, Wang Ling, Sona Mokra, Agustin Dal Lago, Yotam Doron, Susannah Young, Phil Blunsom, and Chris Dyer.  The DeepMind Chinese–English document translation system at WMT2020.  In _Proceedings of the Fifth Conference on Machine Translation_ , 2020a.
  * Yu et al. (2020b) Lei Yu, Laurent Sartran, Wojciech Stokowiec, Wang Ling, Lingpeng Kong, Phil Blunsom, and Chris Dyer.  Better document-level machine translation with bayes’ rule.  _Trans. Assoc. Comput. Linguistics_ , 8:346–360, 2020b.

##  Appendix A Appendix

###  A.1 BATS vs. ATS

The advantage of the beam variant of MCTS (Baier & Winands, 2012) is that the
search algorithm does not have to commit to a single branch every $k$
iterations. As often occurs during translations, multiple valid translation
exist and correspond to different branches in the tree and only after
furthering the search tree can the optimal translation be filtered out. In
ATS, once the eos is chosen, search ends immediately, with no chance for the
decoder to explore other branches, which accentuate issues where degenerate
solutions are chosen (e.g. prematurely ending a translation). A comparison
between ATS and BATS on our WMT2020 Chinese-English validation set using
autoregressive models is shown in Table 3, where we observe that ATS has both
a bias towards degenerate cases and yields worse model scores and BLEU.

| BATS | ATS
---|---|---
Iter | $s(\bm{x},\bm{y})$ | BLEU | $s(\bm{x},\bm{y})$ | BLEU
1 | -5.2 | 21.9 | -5.23 | 21.9
2 | -5.00 | 22.9 | -4.92 | 21.3
4 | -4.81 | 23.1 | -4.90 | 20.9
8 | -4.74 | 23.1 | -4.80 | 20.8
16 | -4.69 | 22.9 | -4.78 | 20.7
32 | -4.65 | 22.9 | -4.75 | 20.7
64 | -4.61 | 22.5 | -4.73 | 20.4
128 | -4.59 | 22.2 | -4.72 | 20.2
256 | -4.57 | 21.7 | -4.72 | 20.0

Table 3: Comparison between BATS and ATS on our WMT2020 Chinese-English
validation set, with Log Probability $(\alpha=0.8)$ as the search objective.

###  A.2 Min Prob vs. Max Rank

The most straight-forward approach to select the worst decision in a
translation is to select the lowest log-probability in the sentence. However,
log-probabilities are not a good indicator of whether a decision is good or
bad as some word translations are inherently low probability (words with many
valid translations). Thus, we decided to use the maximum rank instead. Table 4
provides a comparison between the Min Prob (Row “Log Probability
($\alpha=0.8$) + MP”) and the Max Rank objective (Row “Log Probability
($\alpha=0.8$) + MR”). We observe that while Min Prob yields a relatively
small improvement, it is significantly smaller than Max Rank’s improvement
over the baseline (Row “Log Probability($\alpha=0.8$)”). Additionally, it
clearly does not address the degenerate solutions problem in autoregressive
models.

| Beam Search | BATS |
---|---|---|---
$s(\bm{x},\bm{y})$ | BLEU | Beam | BLEU | Iter | Delta
Log Probability($\alpha=0.8$)AR | 25.0 | 8 | 24.6 | 8 | -1.2%
Log Probability ($\alpha=0.8$) + MPNAR | 24.8 | 8 | 24.7 | 16 | -0.3%
Log Probability ($\alpha=0.8$) + MRNAR | 26.8 | 32 | 27.4 | 128 | 2.5%
Table 4: Comparison between Min Prob and Max Rank in our WMT2020 Chinese-
English test set. The number of iterations is tuned on the validation set.

###  A.3 Minimum Risk Training with ChrF and BLEU

While BLEU (Papineni et al., 2002) is the downstream translation metric used
in most MT evaluations, its sentence level predictions tend to be sparse and
inaccurate. Thereby, training quickly overfits before optimal translation
quality is reached. With sentence level ChrF (Popović, 2015) training is more
stable, and a better optimal translation quality can be obtained.

We use a sample size of $8$ translations per sentence, and these are generated
via temperature sampling with temperature $0.8$. Finally, we set the risk
$r(\textbf{y},\textbf{y}^{\prime})=-\frac{1}{2}\text{BLEU}(\textbf{y},\textbf{y}^{\prime})-\frac{1}{2}\text{ChrF}(\textbf{y},\textbf{y}^{\prime})$,
where $\text{BLEU}(\cdot)$ is the sentence level sacreBLEU (Post, 2018) and
$\text{ChrF}(\cdot)$ is the sentence level ChrF (Popović, 2015). We used the
average of BLEU and ChrF because BLEU was designed as a corpus level metric,
and ChrF provides a better estimate of translation quality with sparser
matches against a reference for a single sentence.

Table 5 compares the results obtained using only $\text{bleu}(\cdot)$,
$\text{chrf}(\cdot)$ and their combinations, using Beam Search with beam 6, on
the validation set in the WMT2020 Chinese-English dataset. Here, we can
observe that a combination of both scores yields the optimal translation
quality.

$\text{bleu}(\cdot)$ | $\text{chrf}(\cdot)$ | BLEU
---|---|---
- | - | 23.1
$1$ | $0$ | 23.8
$0$ | $1$ | 24.4
$\frac{1}{2}$ | $\frac{1}{2}$ | 24.7
Table 5: BLEU obtained on the WMT2020 Chinese-Englsih validation set using
different metrics as risk $r(\textbf{y},\textbf{y}^{\prime})$. Columns
“$\text{bleu}(\cdot)$” and “$\text{chrf}(\cdot)$”, denote the weights applied
and Column “BLEU” denote the BLEU obtained. The first row illustrates the BLEU
score obtained prior to MRT.

###  A.4 Computational Cost of BATS

For Beam Search with beam size $b$ and a max sentence length $Y$, beam search
requires $b\times Y\times A$ operations, where $A$ is a transformer+softmax
block. Additionally, for reranking, the model score $s(\bm{x},\bm{y})$ needs
to be computed for each of the $b$ translations and has a computational cost
of $B$. Thus, the total cost is $b\times(Y\times A+B)$. In BATS, computation
is proportional to the number of expanded nodes, when the playout heuristic is
applied. Each playout requires the computation of greedy decoding, followed by
the scoring function $s(\bm{x},\bm{y})$. Thus, each rollout requires $Y\times
A+B$ computations. Finally, all nodes that follow the path used in greedy
decoding will have the same value $v$, which means that the first node that is
expanded, which corresponds to this path will have no cost, with the exception
of the root node. Thus, the cost of BATS is $(1+z)\times(Y\times A+B)$, where
$z$ is the number of non-root nodes expanded more than once. As $Y\times A+B$
is a common denominator for both methods, we define it as the a computational
unit.

Table 6 shows the results obtained for max rank objective (row “Log
Probability ($\alpha=0.8$) $+MR$” in Table 2). The “Cost” column represents
the number of computational units, and we observe that BATS is considerably
more expensive to run than Beam Search. However, observe the model scores
(Column “Score”), we notice that Beam Search gradually decreases the rate at
which model score gains are observed (Column “Gain”) even though the cost
doubles at each row. For BATS, we observe that while the cost is extremely
high initially (73.049 at 2 iterations), the cost increases at a linear rate
with the number of iterations. More importantly, we notice considerable gains
even with high numbers of iterations (11.82 at 128 iterations). Finally, at
beam $256$, we notice that the cost of Beam Search is comparable to the cost
of running 16 BATS iterations, which achieves similar model scores.

It is important to also refer that cost efficiency is not the goal of this
work, but to expose the need for better decoders that are devoid of the beam
search bias. Many improvements to MCTS-based methods can be made to improve
efficiency, such as training value and policy networks iteratively (Silver et
al., 2016).

| Beam Search | BATS
---|---|---
Beam/Iter | Cost | $s(\bm{x},\bm{y})$ | Gain | Cost | $s(\bm{x},\bm{y})$ | Gain
1 | 1 | -0.84 | - | 1 | -0.84 | -
2 | 2 | -0.81 | 0.0296 | 73.0 | -0.81 | 0.0240
4 | 4 | -0.79 | 0.0169 | 146.4 | -0.77 | 0.0394
8 | 8 | -0.79 | 0.0030 | 217.5 | -0.77 | 0.0032
16 | 16 | -0.78 | 0.0059 | 315.7 | -0.75 | 0.0151
32 | 32 | -0.78 | 0.0048 | 421.9 | -0.74 | 0.0072
64 | 64 | -0.77 | 0.0043 | 584.3 | -0.74 | 0.0002
128 | 128 | -0.77 | 0.0035 | 641.9 | -0.73 | 0.0118
256 | 256 | -0.76 | 0.0032 | 846.3 | -0.73 | 0.0068
Table 6: Comparison between BS and MCTS in terms of computational cost using
the normalised autoregressive model in the WMT2020 Chinese-English validation
set. Cells denote the computational cost, model score obtained and the gain on
score obtained relative to the row above.

###  A.5 Example Translations and Search Errors

We compare the translated sentences using an a MRT tuned autoregressive model
for Chinese-English, where BATS and beam search yield similar BLEU but where
BATS achieves significantly lower model scores. Table 7 provides three example
translations from the test set obtained using beam 64 for beam search (row
“Beam Search”) and 256 iterations for BATS (row “BATS”), which is the setup
that obtained optimal results in the validation set. The first example shows
that beam search tends to prolong sentences by using longer expressions
(“many” vs. “there are also many”) in order to get short term value gains, but
lower overall score, also slightly shifting tone of the sentence. Figure 2
illustrates this issue, we observe that by using the expression “there are
also many”, it delays the generation of the word “technological” for three
timestamps, leading to the higher score of $-0.78729$ (left path) compared to
the alternative $1.20077$ (right path) in the same timestamp. While this score
regularizes to $-1.58682$ once the word “technological” is generated, its
likely that the alternative translation is pruned by beam search.

In the second example, we observe that beam search prefers to reorder the
original sentence, so that higher scoring terms (“U.S. destroyer USS Decatur”)
in the sentence are inserted first. However, as one can observe from the final
score, this decision is only favorable in the short term as the final score of
the sentence is substantially lower than the translation found using BATS,
which respects the order of the original sentence. In the last sentence, we
observe that in the final portion of the translation, the decoder makes a set
of individually high scoring decisions that lead to an ungrammatical
translation as all grammatical options have been filtered from the beam.

|  | $s(\bm{x},\bm{y})$
---|---|---
Source |  同样，也有不少科技企业在专利技术授权、专利技术使用等方面遭遇了不小的侵权风波。 |
Reference |  Similarly, many technology companies have encountered numerous infringements crisis in patent technology licensing and patent technology use. |
Beam Search |  Similarly, there are also many technological enterprises that have encountered great infringing waves in the licensing of patented technology and the use of patented technology. | -2.097
BATS |  Similarly, many technological enterprises have encountered great infringing waves in the licensing of patented technology and the use of patented technology. | -1.740
Source |  据中央社30日综合外电报道，据要求匿名的美国官员透露，美国驱逐舰USS Decatur驶入了南沙群岛南薰礁（Gaven Reef）和赤瓜礁（Johnson Reef）12海里范围内。 |
Reference |  According to the comprehensive foreign reports of the Central News Agency, the U.S. official who requested anonymity revealed that the United States Navy destroyer, USS Decatur, cruised into the 12 nautical mile territorial limit of Gaven Reef and Johnson Reef of the Nansha Islands. |
Beam Search |  U.S. destroyer USS Decatur sailed into the Gaven Reef and Johnson Reef 12 nautical miles (12 nautical miles) of the Southern Sand Islands, according to Central Intelligence Agency’s Comprehensive Outreach News on 30. | -2.722
BATS |  According to Central News Agency’s comprehensive external telecommunications report on 30 June, U.S. officials who requested anonymity, the USS Decatur sailed into the Gaven Reef and Johnson Reef of the Southern Sand Islands within 12 nautical miles. | -2.288
Source |  意大利疑欧派政府的目标是未来三年预算赤字相当于国内生产总值(GDP)的2.4 % ， 这表明仅管面临减赤要求仍未有债务削减 |
Reference |  The aim of Italian Eurosceptic government was that the budget deficit was equivalent to 2.4% of gross domestic product (GDP) in the next three years, suggesting that there was no debt reduction despite deficit reduction requirements. |
Beam search |  The Italian Euroskeptic government’s goal is to have a budget deficit equivalent to 2.4% of gross domestic product over the next three years, suggesting that only facing deficit reduction requirements has not yet been debt reduction. | -1.647
BATS |  The Italian Euroskeptic government’s goal is to have a budget deficit equivalent to 2.4% of gross domestic product over the next three years, indicating only that there is no debt reduction required to reduce the deficit. | -1.542
Table 7: Examples of translation obtained using beam search and BATS on the
Chinese-English test set using MRT tuned autoregressive models.

Figure 2: Illustration of the issue with the search bias in beam search where
the decoder can delay the generation of low probability words, in this case
the word “technological” in order to generate high initial scores. Edges
scores correspond to the token level log probability $\log p(y_{i}\mid
y_{1},\ldots,y_{i-1},\bm{x})$ and nodes scores correspond to the value that is
assigned to the state using the normalised partial sum of probabilities
$\frac{\sum_{j\leq i}\log p(y_{j}\mid
y_{1},\ldots,y_{j-1},\bm{x})}{(\frac{5+i}{6})^{\alpha}}$ with $\alpha=0.8$.
This example is obtained from the WMT2020 test set.


# Semantic Embedded Deep Neural Network: A Generic Approach to Boost Multi-
Label Image Classification Performance

Xin Shen, Xiaonan Zhao, Rui Luo

###### Abstract

Fine-grained multi-label classification models have broad applications in
e-commerce, such as visual based label predictions ranging from fashion
attribute detection to brand recognition. One challenge to achieve
satisfactory performance for those classification tasks in real world is the
wild visual background signal that contains irrelevant pixels which confuses
model to focus onto the region of interest and make prediction upon the
specific region. In this paper, we introduce a generic semantic- embedding
deep neural network to apply the spatial awareness semantic feature
incorporating a channel- wise attention based model to leverage the
localization guidance to boost model performance for multi- label prediction.
We observed an Avg.relative improvement of 15.27% in terms of AUC score across
all labels compared to the baseline approach. Core experiment and ablation
studies involve multi-label fashion attribute classification performed on
Instagram fashion apparels’ image. We compared the model performances among
our approach, baseline approach, and 3 alternative approaches to leverage
semantic features. Results show favorable performance for our approach.

##  I Introduction

One big issue for today’s industry to develop fashion pattern classification
model is to achieve the high precision. The challenges are in 2 aspects: 1)
it’s a multi-label problem where some patterns are minor to the whole
population; 2) the model is working on wild background images (e.g. from
Instagram). The multi-label model is used in the following applications: 1)
Fashion trend attribute extraction, 2) Image filtering according to fashion
attributes, 3) Fashion collection creation. Therefore, its accuracy is
critical to the success of the downstream applications.

Thus, we want to develop a multi-label image classification model that can
accurately process images with wild background, considering that some of our
applications use images from Instagram. For example, given a fashion image
with a fashion model wearing a pinstripe dress standing in front of flowers,
we want a network to predict the attribute "pinstripe", but network can be
confused by the irrelevant pixels from the wild background of the floral-alike
pixels. Therefore, we want the deep learning model to focus on pixels of
fashion garment in image, so to have more accurate predictions. To achieve
this, we need the classification model to be guided by regional semantic
information. In one previous work of from Mahdi M. Kalayeh et al.[17], authors
concatenate semantic segmentation mask with raw image as input feature, so the
whole CNN layers are aware of regional semantic information, which
significantly improves classification performance. However, this approach
requires a semantic segmentation model with pixel level annotation, which
cannot be used when such labels are not available.

Following the idea, we propose to solve this problem with an innovative model
that has 3 components: 1) We use classification label to train a image
classifier, but use it as class activation map (CAM) generator, which contains
regional information. 2) We use CAM as an input to learn a semantic embedding
for each pixel, where regional semantic information is encoded. 3) We
concatenate semantic embedding with the raw image tensor as input features and
feed them into a channel wise attention based image classification model to
enhance the fine-grained multi-label prediction.

Figure 1: The model structure of the proposed Semantic Embedded ResNest50
Classifier

##  II Related Work

#### Semantic guidance

Semantic guidance,i.e. using semantic information as an extra input or feature
to guide feature extraction or classification, are widely adopted to boost
target tasks, such as classification, visual search, GAN based image
rectification and semantic based regression [19, 20], crowd counting[23], etc.
Some previous work[17, 21] uses semantic information as input of CNN networks
to train a CNN classifier. Some previous works perform attentions between
semantic segmentation output and feature maps from CNN backbone [3, 10, 11,
6], but these methods rely on a supervised semantic segmentation model to
generate the semantic segmentation map. There are some research works using
class activation maps to boost the CNN model to extract fine-grained visual
features[25]. Human semantic parsing[6] is used for person-reID. Dense
pose[16] are used to train generative models for outfit transfer or outfit
generation[8]. In the work of crow counting[23], semantic segmentation map is
used to correct the final prediction from the regression model.

#### Multi-label classification

Multi-label classification problem is hard mainly because of the nature of
imbalanced distribution. Some previous works also leveraged semantic
information to help the problem. In the work[27], regional latent semantic
dependencies are learned by a mixer of CNN and LSTM model. Similarly, in their
work[24], they uses Mask R-CNN model to generate object bounding boxes, then
perform a graph based multi-label classifier. To our best knowledge, all these
works rely on a pre-trained semantic segmentation model or an object detection
model, which has same semantic dictionary[28, 5] as the target task. This is a
major drawback for generalization on any tasks.

##  III Method

Firstly, we fine-tune a pre-trained ResNet50[4] incorporated with attention-
based SGE module[12] with multi-label Sigmoid Cross-Entropy loss (denoted as
BCEWithLogitsLoss in PyTorch). We added a convolution layer after Resnet50 to
transform the feature map from $\mathbb{[}h^{\prime},w^{\prime},2048]$ to
$\mathbb{[}h^{\prime},w^{\prime},c]$, where c equals to number of classes (see
Fig. 2). The class activation map ($\mathbb{[}h^{\prime},w^{\prime},c]$) is
used as input to generate semantic embeddings in the next component.

Figure 2: Model structure and training scheme of the semantic generator

As shown in Fig.1, we utilize CAM Model to generate a class activation map
(CAM) $\mathbb{\lambda}$ in the size of
$\mathbb{[}Batch,W,H,{num}\\_{class}]$. We then feed the CAM into a Semantic
Feature Embedding Module - a 5-layer of deconvolution network. Instance
normalization [22] is plugged in deconvolution layers to normalize the output
of regional semantic embedding ${\lambda}^{{}^{\prime}}$. The regional
semantic embedding ${\lambda}^{{}^{\prime}}$ from the embedding layer in the
size of $\mathbb{[}Batch,256,256,D]$ is concatenated with the raw image as
extra $D$ channel(s).

The concatenated tensor is fed into the channel-wise attention based multi-
label image classifier (ResNest50[26]). We found that channel wise attention
is better than plain convolutions, when it learns the correlation between the
regional semantic embedding and the raw RGB channels. We further added more
fully connected layers (FCs) to introduce more non- linearity.

##  IV Experiments

###  IV-A Dataset Description

We collected 34,158 Instagram fashion apparel images for women’s dressing,
such as dress, tops, and bottoms where the image contains a wilder background
noise, shown in the right figure of Fig.3. Images are annotated in a multi-
label fashion with 11 pattern attributes: {Solid, Plaid, Floral, Stripe,
Check, Graphic, Tie Dye, Animal, Words/Letters, Dot, Paisley}.The dataset
shows a severe label imbalance issue, see Fig.4. These images were randomly
partitioned into training(70%) and testing(30%).

Figure 3: The left image shows a women’s shirt containing pattern attributes
of "Animal" and "Dots" and "Graphics". The right image shows a sample of the
image domain we develop and test the model on, where the background behind the
model is quite noisier, which makes it more challenging for a DNN model to
predict the pattern attribute from such images. Figure 4: The label
distribution visualization

###  IV-B Problem Setting and Evaluation Metrics

We defined this visual detection work as a multi-label classification problem,
given the nature of the fashion attributes which could co-exist in a same
women’s dressing, as shown in the left figure of Fig.3. In turn the ground
truth is labeled into the form of multi-label one-hot vector, such as
[1,0,0,0,0,0,1,1,0,0,0], and the output from the model is the corresponding
probability distribution for each label in the same dimension as the ground
truth. The model performance is evaluated using the area under the curve (AUC)
of precision-recall curve on the test set for each label shown in Fig.5

Figure 5: Sample of Model Performance Visualization of PR- Curve. The number
in the legend manifests this approach’s AUC score

###  IV-C Network and Training

We selected 2 models for experimental comparisons: 1) the baseline model is a
ResNest50 [26] without applying any semantic guidance (referred as ResNest50),
2) our Semantic Embedded ResNest50 approach (referred as Semantic Embedded
ResNest50). Model parameters can be found in Fig.1. We also found that
increasing the output channel size from 1 to 3 of the last deconvolution layer
does not consistently improve the model performance (see Ablation Study).
Thus, we set the output channel size to be 1. We trained models using Sigmoid
Cross-Entropy loss. We reduced learning rate when the loss has stopped
improving after 4 epochs. The learning rate was initiated to be $1e^{-5}$ and
Adam Optimizer[7] was adopted.

##  V Results and Discussion

Table.I compares the model performance between baseline approach (plain
ResNest50) and our approach (Semantic Embedded ResNest50). Our approach out-
performed the baseline approach across ALL labels in terms of the AUC score,
with relative improvement ranging from 7.54% to 35.41%. This manifests using
semantic embedding as a guidance significantly boosts up the model performance
as the extra localization information embedded helps a network to focus more
onto the region of interest and ignore irrelevant pixels.

TABLE I: Comparison on the label-wise AUC performance: 1). Baseline: ResNest50 with raw RGB input, 2).Our approach: Semantic Embedded ResNet50 leveraging semantic embedding | Solid | Plaid | Floral | Stripe | Check | Animal | Graphics | Paisley |  Tie Dye | Dot |  Words Letters
---|---|---|---|---|---|---|---|---|---|---|---
ResNest50 | 0.809 | 0.747 | 0.621 | 0.704 | 0.732 | 0.786 | 0.468 | 0.440 | 0.596 | 0.624 | 0.555
Semantic Embedded ResNest50 | 0.870 | 0.840 | 0.740 | 0.793 | 0.791 | 0.880 | 0.509 | 0.549 | 0.807 | 0.791 | 0.626
Relative Improvement | 7.54% | 12.40% | 19.19% | 12.59% | 7.99% | 11.98% | 8.83% | 24.84% | 35.41% | 26.80% | 12.75%

We consider the majority class to be the label with image samples over 5% and
the rest are minorities. In turn, the majority classes are Solid, Stripe and
Animal, while minorities are Plaid, Check, Graphics, Paisley, Tie Dye, Dot,
Words/Letters, and Floral. We compared the average relative improvement across
all majorities and all minorities respectively. According to Table.II, our
approach yields a higher improvement on minority classes (image samples under
5%) than it performs on majorities. From this perspective, our approach can be
leveraged to alleviate label imbalanced issue.

TABLE II: Avg. Relative Improvement over majority classes and over minority classes Avg. Relative Improvement over Majorities | 11.45%
---|---
Avg. Relative Improvement over Minorities | 16.64%
Figure 6: The visualization showing the comparison between the baseline’s
approach and our approach. All four images contain at least 1 minority class
and might/ might not contain majority class. For example, Image.A contains one
majority class as solid, and one minority class as floral

Further, Fig.6 visualizes four image samples with the multi-label predictions
made by the baseline approach and our approach respectively. From the
prediction results, our approach shows a preciser prediction than the baseline
approach and it could better capture the pattern of minority classes. In turn
when an image contains both majority class and minority class, our approach
does not solely focus onto majority class but also makes a correct prediction
for minority class (see Image.A and Image.B). Meanwhile, we observed that for
label "tie dye", the baseline approach tends to be confused by the wild
background pixels (see Image.C) and by the less-strong and insignificant pixel
signal of "tie dye" (see Image.D), while our approach could successfully
extract the needed pixels for a correct prediction.

###  V-A Ablation Study

The classification module is composed with 2 modules: 1) Semantic Embedding
Module which serves to embed a raw CAM into a semantic embedding with the
shape of $\mathbb{[}Batch,256,256,1]$, and 2). ResNest50 as the classification
backbone to provide the network with a channel- wise attention mechanism. We
conducted 3 following ablation studies: 1) we compared our Semantic Embedded
Module to embed a raw CAM with a simple interpolation based tensor-reshape. We
performed tensor reshape and a channel-wise summation with min-max
normalization to achieve a 1-D feature map in the shape of
$\mathbb{[}Batch,256,256,1]$, 2) we wanted to understand if a plain
convolution network without channel- wise attention, Resnet50, can be used to
substitute the ResNest50 (referred as Semantic Embedded Resnet50). 3) we
tested if a 3- channel embedded semantic feature generated by Semantic
Embedding Module could achieve a better model performance (referred as
3-channel Semantic Embedded ResNest50) compared to 1-D semantic embedding.

TABLE III: Comparison on the label-wise AUC performance between our approach Semantic Embedded ResNest50 and all other 3 ablation studies models: 1) Manually Reshaped Semantic, 2) Semantic Embedded Resnet50, 3) 3-channel Semantic Embedded ResNest50 | Solid | Plaid | Floral | Stripe | Check | Animal | Graphics | Paisley | Tie Dye | Dot |  Words/ Letters
---|---|---|---|---|---|---|---|---|---|---|---
ResNest50 Deconv D=1 | 0.870 | 0.840 | 0.740 | 0.793 | 0.791 | 0.880 | 0.509 | 0.549 | 0.807 | 0.791 | 0.626
ResNest50 Reshaped D=1 | -0.387 | -0.726 | -0.620 | -0.670 | -0.350 | -0.768 | -0.478 | -0.523 | -0.785 | -0.740 | -0.601
Resnet50 Deconv D=1 | -0.028 | -0.0366 | -0.024 | -0.013 | -0.018 | -0.013 | -0.021 | -0.027 | -0.025 | -0.024 | -0.1072
ResNest50 Deconv D=3 | -0.093 | +0.008 | -0.006 | -0.040 | +0.011 | +0.019 | -0.145 | -0.056 | +0.014 | +0.016 | -0.032

The comparison between $2^{nd}$ row and $1^{st}$ row from Table.III shows a
heavily decayed performance for the approach of concatenating a manually
reshaped and normalized semantic map. This manifests this approach harms the
overall learning progress. The interpolation based reshaping mechanism and
channel- wise summation to reshape a raw CAM from a dimension of [w’, h’, c]
into [256, 256, 1] introduces many noises to the original CAM. Still this
manually work is not learnable, thus, at the inference stage, the extra
information provided by this manually reshaped semantic feature is in a random
pattern to a DNN. This introduces more irrelevant noises for a DNN to process
and in turn hurts the model performance.

Further, the comparison between Semantic Embedded Resnet50 and Semantic
Embedded ResNest50, shown in $3^{rd}$ row and $1^{st}$ row, manifests this
alternative approach fails to yield a boosted performance. The average
relative decrease in terms of AUC score across all labels using this approach
compared to our approach’s is 4.39%. These manifest that our approach,
Semantic Embedded ResNest50 which leverages the channel- wise attention
mechanism, is more sensitive to the semantic embedding guidance. The channel-
wise attention mechanism enables a soft-attention-like effect via the semantic
embedding guidance to help the classifier to learn the localization
information better and in turn help the classifier to focus more onto the
region of interest for a better model performance.

Lastly, the last row of Table.III shows the model performance comparison
between our approach of using a 1-channel semantic embedding and an
alternative approach of using a 3-channel semantic embedding. The mixed
performance manifests that there is no significant correlation between the
channel size of the semantic embedding and model performance. The Semantic
Embedded Module we built, shown in Fig.1, expands the input raw CAM’s
dimension by 2X without changing the channel size over the first 4
deconvolution layers, and the last deconvolution layer performs both dimension
reshaping and channel size squeezing. In turn, the localization information
from raw CAM is both retained throughout the entire 5 deconvolution layers no
matter whether the last layer convolves the feature into a 3 channel or 1
channel.That is, the 1-channel semantic embedding embeds the information more
densely, while the semantic information from a 3-channel semantic embedding is
more diluted and distributed across 3 channels.

##  VI Industrial Impact

Our work presents a generic deep neural network structure to build a multi-
label classification model with a high precision and recall. This model serves
as a crucial upper stream for many down stream applications across E-commerce,
such as Fashion Industry. For example, to understand how a fashion attribute
evolve over a time period, we need the temporal signal of a certain attribute
over a time period, and our work can contribute to make attribute signal
extraction and aggregation. Further, this model can be used as image content
understanding for customer search query to products matching on the fashion
attribute level. For example, when a customer search a query of "Floral Tie
Dye Shirt", most existed query to product matcher mechanism is based on the
similarity between query and product-titles. However, a free text based signal
might contain more noises and even fake attribute signal (sellers tend to
include more attribute information to make a title attractive) compared to
pure visual signal representation. Hence, our model can serve as a proficient
encoder for semantic embeddings, providing valuable support to a wide range of
downstream applications. Examples of such applications include text embedding/
image embedding based query-to-product matching and sequential-based item
retrieval, where our model’s capabilities can significantly enhance the
overall performance and effectiveness. [1, 2, 9]. More importantly, we
introduced a generic deep learning approach to achieve a high- performance
backbone more than fashion detection domain. Many other industries, such as
mechanical industry, could leverage our approach to build their own high-
performance backbone to operate tasks including but not limited to object’s
relocation and deviation detection. By reframing the conventional approach of
object status detection using traditional geometric based computer vision into
a machine learning-based classification and regression problem, our solution
offers a compelling alternative to existing works [14, 15] that heavily depend
on costly hardware. In doing so, we introduce an efficient methodology that
addresses this challenge with remarkable efficacy.

##  VII Conclusion

Overall, by leveraging our proposed approach, Semantic Embedded ResNest50,
enables us to obtain a boosted model performance in terms of fine grained
multi- label prediction. The trainable semantic embedding layer enables a
dynamic mechanism to reshape and to embed a raw CAM into the desired shape
without introducing extra noises and losing signals during the process of
deconvolution, while the channel- wise attention based classifier backbone
enables a soft- attention- like mechanism to leverage the localization
information provided by the embedded semantic map to help the network to focus
more onto the region of interest from the RGB channel. Experimental results on
fashion pattern attribute classification show significant boost using this
proposed approach with a well- rounded improvement across all labels ranging
from 7.54% to 35.41% in terms relative AUC improvement compared to the
baseline approach. Moreover, our approach shows a favorable performance to the
minority classes, which improves a model’s robustness upon the minority
classes. To further improve the model’s generalization abilities upon minority
classes, we could incorporate label distribution stabilization techniques [18,
13].

Our next step is to investigate an end to end solution from generating the raw
CAM to embed the semantic embedding, and to the prediction layer using one
single DNN model. This merged deep learning approach could remove the training
efforts of a separate CAM generator, which in turn removes a dependency.

## References

  * [1] Yankai Chen, Jie Zhang, Yixiang Fang, Xin Cao, and Irwin King.  Efficient community search over large directed graphs: An augmented index-based approach.  In Proceedings of the Twenty-Ninth International Conference on International Joint Conferences on Artificial Intelligence (IJCAI), pages 3544–3550, 2021.
  * [2] Yankai Chen, Yifei Zhang, Menglin Yang, Zixing Song, Chen Ma, and Irwin King.  Wsfe: Wasserstein sub-graph feature encoder for effective user segmentation in collaborative filtering.  The 46th SIGIR Conference on Research and Development in Information Retrieval (SIGIR), 2023.
  * [3] Eduardo FIDALGO, E. Alegre, V. González-Castro, and Laura Fernández-Robles.  Boosting image classification through semantic attention filtering strategies.  Pattern Recognit. Lett., 112:176–183, 2018.
  * [4] 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.
  * [5] Xiao-Yuan Jing, Fei Wu, Zhiqiang Li, R. Hu, and Dafan Zhang.  Multi-label dictionary learning for image annotation.  IEEE Transactions on Image Processing, 25:2712–2725, 2016.
  * [6] M. Kalayeh, Emrah Basaran, M. Gokmen, M. Kamasak, and M. Shah.  Human semantic parsing for person re-identification.  2018 IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 1062–1071, 2018.
  * [7] Diederik P Kingma and Jimmy Ba.  Adam: A method for stochastic optimization.  arXiv preprint arXiv:1412.6980, 2014.
  * [8] Christoph Lassner, Gerard Pons-Moll, and P. Gehler.  A generative model of people in clothing.  2017 IEEE International Conference on Computer Vision (ICCV), pages 853–862, 2017.
  * [9] Jiacheng Li, Ming Wang, Jin Li, Jinmiao Fu, Xin Shen, Jingbo Shang, and Julian McAuley.  Text is all you need: Learning language representations for sequential recommendation, 2023.
  * [10] Kunpeng Li, Ziyan Wu, K. Peng, Jan Ernst, and Yun Fu.  Tell me where to look: Guided attention inference network.  2018 IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 9215–9223, 2018.
  * [11] Ming Li, Yiming Zhao, Yecheng Lyu, and Ziming Zhang.  Self-supervised visual attention learning for vehicle re-identification.  ArXiv, abs/2010.09221, 2020.
  * [12] Xiang Li, Xiaolin Hu, and Jian Yang.  Spatial group-wise enhance: Improving semantic feature learning in convolutional networks.  arXiv preprint arXiv:1905.09646, 2019.
  * [13] Jiabin Liu, Bo Wang, Xin Shen, Zhiquan Qi, and Yingjie Tian.  Two-stage training for learning from label proportions.  arXiv preprint arXiv:2105.10635, 2021.
  * [14] Yue Mei, Sicheng Wang, Xin Shen, Stephen Rabke, and Sevan Goenezen.  Mechanics based tomography: a preliminary feasibility study.  Sensors, 17(5):1075, 2017.
  * [15] Yue Mei, Sicheng Wang, Xin Shen, Stephen Rabke, and Sevan Goenezen.  Erratum: Mei, y., et al. mechanics based tomography: A preliminary feasibility study. sensors 2017, 17, 1075.  Sensors, 18(2):384, 2018.
  * [16] N. Neverova, Riza Alp Güler, and I. Kokkinos.  Dense pose transfer.  In ECCV, 2018.
  * [17] J. Scheurer, Claudio Ferrari, Luis Berenguer Todo Bom, M. Beer, W. Kempf, and Luis Haug.  Semantic segmentation of histopathological slides for the classification of cutaneous lymphoma and eczema.  In MIUA, 2020.
  * [18] Xin Shen, Praful Agrawal, and Zhongwei Cheng.  Data efficient training with imbalanced label sample distribution for fashion detection, 2023.
  * [19] Xin Shen, Kyungdon Joo, and Jean Oh.  Fishrecgan: An end to end gan based network for fisheye rectification and calibration, 2023.
  * [20] Xin Shen, Yan Zhao, Sujan Perera, Yujia Liu, Jinyun Yan, and Mitchell Goodman.  Learning personalized page content ranking using customer representation, 2023.
  * [21] Shusuke Takahama, Y. Kurose, Yusuke Mukuta, Hiroyuki Abe, M. Fukayama, A. Yoshizawa, M. Kitagawa, and T. Harada.  Multi-stage pathological image classification using semantic segmentation.  2019 IEEE/CVF International Conference on Computer Vision (ICCV), pages 10701–10710, 2019.
  * [22] Dmitry Ulyanov, Andrea Vedaldi, and Victor Lempitsky.  Instance normalization: The missing ingredient for fast stylization.  arXiv preprint arXiv:1607.08022, 2016.
  * [23] Hao Xu, Chengyao Zheng, Y. Nie, and Si-Yu Xia.  Crowd counting with segmentation map guidance.  2019 Chinese Control Conference (CCC), pages 7716–7721, 2019.
  * [24] Jiahao Xu, Hongda Tian, Zhiyong Wang, Yang Wang, Wenxiong Kang, and F. Chen.  Joint input and output space learning for multi-label image classification.  IEEE Transactions on Multimedia, 23:1696–1707, 2021.
  * [25] Wenjie Yang, Houjing Huang, Zhang Zhang, Xiaotang Chen, Kaiqi Huang, and Shu Zhang.  Towards rich feature discovery with class activation maps augmentation for person re-identification.  2019 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), pages 1389–1398, 2019.
  * [26] Hang Zhang, Chongruo Wu, Zhongyue Zhang, Yi Zhu, Haibin Lin, Zhi Zhang, Yue Sun, Tong He, Jonas Mueller, R Manmatha, et al.  Resnest: Split-attention networks.  arXiv preprint arXiv:2004.08955, 2020.
  * [27] Junjie Zhang, Qi Wu, Chunhua Shen, J. Zhang, and Jianfeng Lu.  Multilabel image classification with regional latent semantic dependencies.  IEEE Transactions on Multimedia, 20:2801–2813, 2018.
  * [28] F. Zhou, Sheng Huang, and Yun Xing.  Deep semantic dictionary learning for multi-label image classification.  In AAAI, 2021.