summaries: This paper presents a novel algorithm called beam adaptive tree search (BATS) to enable the incorporation of search objectives that cannot be easily factorized. Unlike the regular Monte Carlo tree search algorithms that relies on a large number of playouts to update the value function, BATS relies on "informed playout", which is guided by the greedy decoding of the autoregressive models. To further constrain the search space, the paper also proposed a constrained node expansion criterion that gradually increases the lower limit of the node depth $d_{min}$, and allows for expanding $k$ nodes for each depth limit $d_{min}$.  Aside from the search algorithm, the paper also explored a couple of model changes to counteract the calibration issues, including two modified search objectives and using MRT-trained autoregressive models. Experiments show that while beam search performs better for the weaker models, BATS does improve the translation quality of the hypotheses when stronger MT models are used. Analysis on different beam size also show that unlike beam search, BATS can operate at large search budget without performance degradation under stronger models.

summaries: The paper proposes an adaptive tree search algorithm for text generation. It uses an autoregressive model as the value network to produce the playout for each node. While decoding, the paper proposes a metric called max rank to address the shortcomings of utilizing the sum of token level log-probability. Results are conducted on several machine translation datasets, and the proposed method outperforms beam search in most cases.

summaries: This paper proposes an adaptive tree search algorithm for NMT models. One advantage of this algorithm is that it does not make any assumptions about search objectives, and this enables the proposed algorithm to be applied on top of more general search objectives. In addition, it studies the issue of beam search bias and revisits some tricks to alleviate it as well as a new tricks. Combined with these tricks, the proposed algorithm delivers clear BLEU improvements over a strong baseline.

summaries: **Summary**  This paper proposes an adaptive tree search algorithm BATS, an MCTS variant, for NMT that could optimize any desired objectives/metrics (e.g. BLEU). The algorithm values each internal node by scoring a greedy searched rollout (instead of that of authentic MCTS) with an autoregressive model, which avoids search biases caused by other heuristics (e.g., beam search would be biased towards shorter translations or incomplete partial generations). Plus, a new objective Max Rank is proposed with a better correlation with translation quality. Experiments show that BART works well in comparison with beam search, which is also shown to bound the progress of more robust modeling in NMT.

abstractText: We introduce an adaptive tree search algorithm, which is a deterministic variant of Monte Carlo tree search, that can find high-scoring outputs under translation models that make no assumptions about the form or structure of the search objective. This algorithm 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.

authors:
David Auger
Adrien Couëtoux
Olivier Teytaud

title: Continuous upper confidence trees with polynomial exploration - consistency

venue: Proceedings, Part I,

authors:
Hendrik Baier
Mark H.M. Winands

title: Beam monte-carlo tree search

venue: IEEE Conference on Computational Intelligence and Games (CIG),

authors:
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
Aleš Tamchyna

title: Findings of the 2014 workshop on statistical machine translation

venue: In Proceedings of the Ninth Workshop on Statistical Machine Translation,

authors:
Peter F. Brown
Stephen A. Della Pietra
Vincent J. Della Pietra
Robert L. Mercer

title: The mathematics of statistical machine translation: Parameter estimation

venue: Computational Linguistics,

authors:
Cameron Browne
Edward Powley
Daniel Whitehouse
Simon Lucas
Peter I. Cowling
Philipp Rohlfshagen
Stephen Tavener
Diego Perez
Spyridon Samothrakis
Simon Colton

title: A survey of monte carlo tree search methods

venue: IEEE Transactions on Computational Intelligence and AI in Games,

authors:
Ciprian Chelba
Tomás Mikolov
Mike Schuster
Qi Ge
Thorsten Brants
Phillipp Koehn

title: One billion word benchmark for measuring progress in statistical language modeling

title: Efficient Selectivity and Backup Operators in Monte-Carlo Tree Search

venue: 5th International Conference on Computer and Games,

authors:
Zihang Dai
Zhilin Yang
Yiming Yang
Jaime G. Carbonell
Quoc V. Le
Ruslan Salakhutdinov

title: Transformer-xl: Attentive language models beyond a fixed-length context

venue: URL http://arxiv.org/abs/1901.02860

authors:
Peter Hart
Nils Nilsson
Bertram Raphael

title: A formal basis for the heuristic determination of minimum cost paths

venue: IEEE Transactions on Systems Science and Cybernetics,

authors:
Ari Holtzman
Jan Buys
Maxwell Forbes
Yejin Choi

title: The curious case of neural text degeneration

authors:
Nal Kalchbrenner
Phil Blunsom

title: Recurrent continuous translation models

venue: In Proceedings of the 2013 Conference on Empirical Methods in Natural Language Processing,

authors:
Guillaume Klein
Yoon Kim
Yuntian Deng
Jean Senellart
Alexander M. Rush

title: Opennmt: Open-source toolkit for neural machine translation

authors:
Levente Kocsis
Csaba Szepesvári

title: Bandit based monte-carlo planning

venue: Proceedings of the Seventeenth European Conference on Machine Learning (ECML 2006),

authors:
Philipp Koehn
Rebecca Knowles

title: Six challenges for neural machine translation

venue: In Proceedings of the First Workshop on Neural Machine Translation,

authors:
Philipp Koehn
Franz J. Och
Daniel Marcu

title: Statistical phrase-based translation

venue: In Proceedings of the 2003 Human Language Technology Conference of the North American Chapter of the Association for Computational Linguistics,

authors:
Rémi Leblond
Jean-Baptiste Alayrac
Laurent Sifre
Miruna Pislar
Jean-Baptiste Lespiau
Ioannis Antonoglou
Karen Simonyan
Oriol Vinyals

title: Machine translation decoding beyond beam

venue: search. CoRR,

authors:
Jason Lee
Elman Mansimov
Kyunghyun Cho

title: Deterministic non-autoregressive neural sequence modeling by iterative refinement

venue: In Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing,

authors:
Chu-Cheng Lin
Aaron Jaech
Xin Li
Matthew R. Gormley
Jason Eisner

title: Autoregressive modeling is misspecified for some sequence distributions

authors:
Qi Liu
Lei Yu
Laura Rimell
Phil Blunsom

title: Pretraining the noisy channel model for task-oriented dialogue

venue: Trans. Assoc. Comput. Linguistics,

authors:
Clara Meister
Tim Vieira
Ryan Cotterell

title: If beam search is the answer, what was the question

authors:
Nathan Ng
Kyra Yee
Alexei Baevski
Myle Ott
Michael Auli
Sergey Edunov

title: Facebook fair’s WMT19 news translation task submission

venue: ProceedingsWMT,

title: Minimum error rate training in statistical machine translation

venue: In Proceedings of the 41st Annual Meeting of the Association for Computational Linguistics,

authors:
Kishore Papineni
Salim Roukos
Todd Ward
Wei-Jing Zhu

title: Bleu: a method for automatic evaluation of machine translation

venue: In Proceedings of the 40th Annual Meeting of the Association for Computational Linguistics,

title: chrF: character n-gram F-score for automatic MT evaluation

venue: In Proceedings of the Tenth Workshop on Statistical Machine Translation,

title: A call for clarity in reporting BLEU scores

venue: In Proceedings of the Third Conference on Machine Translation: Research Papers,

authors:
Rico Sennrich
Barry Haddow
Alexandra Birch

title: 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

venue: Association for Computational Linguistics. doi: 10.18653/v1/P16-1162. URL https://www.aclweb. org/anthology/P16-1162

title: Fast transformer decoding: One write-head is all you need

authors:
Shiqi Shen
Yong Cheng
Zhongjun He
Wei He
Hua Wu
Maosong Sun
Yang Liu

title: Minimum risk training for neural machine translation. In Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)

authors:
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
Demis Hassabis

title: Mastering the game of go with deep neural networks and tree

venue: search. Nature,

authors:
Felix Stahlberg
Bill Byrne

title: On NMT search errors and model errors: Cat got your tongue

venue: 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),

authors:
Ilya Sutskever
Oriol Vinyals
Quoc V Le

title: Sequence to sequence learning with neural networks

venue: Advances in Neural Information Processing Systems,

authors:
Ashish Vaswani
Noam Shazeer
Niki Parmar
Jakob Uszkoreit
Llion Jones
Aidan N. Gomez
Lukasz Kaiser
Illia Polosukhin

title: Attention is all you need

authors:
Kyra Yee
Yann N. Dauphin
Michael Auli

title: Simple and effective noisy channel modeling for neural machine translation

venue: Proceedings of EMNLP,

authors:
Lei Yu
Phil Blunsom
Chris Dyer
Edward Grefenstette
Tomás Kociský

title: The neural noisy channel

venue: In Proceedings of ICLR,

authors:
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
Chris Dyer

title: The DeepMind Chinese–English document translation system at WMT2020

venue: In Proceedings of the Fifth Conference on Machine Translation,

heading: 1 INTRODUCTION

text:
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.
∗Authors contributed equally. †Work carried out while Wang Ling was at DeepMind.
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., nonlocal 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.1 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 nonautoregressive 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.

heading: 2 BACKGROUND

heading: 2.1 BEAM SEARCH

text:
Translation tasks operate on the space of possible translations Y = Σ∗ ◦ {EOS} where Σ is a finite vocabulary, and EOS is a symbol represents the end of a sequence. Elements in Y correspond to full sentences y = y1, . . . , yn with n− 1 tokens, where yn = EOS (end of sentence). Each translation y is conditioned on a source sentence x and is assigned a score s(x,y), which measures how well x translates to y. Decoding algorithms aim to find the best hypothesis y∗ ∈ Y under the search objective s(x,y). While autoregressive models may assign scores to prefixes of translations, we
1In 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.
only assume that s is well defined for full translations, y ∈ Y . In the particular case of machine translation under standard autoregressive models, the search objective is defined as the conditional log probability:
sAR(x,y) = log p(y | x) = |y|∑ i=1 log p(yi | y1, . . . , yi−1,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 y(p). Nodes define an additional space Y∗ including Y as well as partial translations in Σ∗ that do not terminate with a EOS token. Each node contains |Σ|+ 1 edges, each appending a different word yi ∈ Σ ∪ {EOS} to y(p) generating a new node p ◦ yi. Edge weights are given by the emission log probability log p(yi | y(p),x) according to the autoregressive model. Search starts from the root node ε 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 v̂(p) = c(p) + f(p), where c(p) is the sum of weights of all edges from ε 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 ε 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 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.

heading: 2.2 MONTE CARLO TREE SEARCH

text: In Monte Carlo tree search (Coulom, 2006, MCTS), the Monte Carlo method replaces the heuristically driven measure of value 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 v̂(p), MCTS diversifies the search space by allocating budget to less explored areas in the search space (Kocsis & Szepesvári, 2006), and continually refines value estimates.

heading: 3 ADAPTIVE TREE SEARCH FOR TEXT GENERATION

text:
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(x,y) is low. For instance, the playout heuristic 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 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.

heading: 3.1 DETERMINISTIC PLAYOUT HEURISTIC

text:
We start by establishing our playout function 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(x,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 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 v̂(p) by recursively selecting the highest probability token y according to an autoregressive model p(y | y(p)1 , . . . , y (p) i ,x), and scoring the translation using the objective function s(x,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.

heading: 3.2 ADAPTIVE TREE SEARCH WITH A MODIFIED UCT CRITERIA

text:
ATS operates on search trees instead of weighted graphs. A search tree covers the space of all possible full and partial translations Y∗, and each node encodes a particular sequence y(p). Nodes have |Σ|+1 children, each appending a new word y ∈ Σ ∪ {EOS} to the sequence y(p). We denote the child resulting from concatenating y to p as p ◦ y. The child of a node that selects the EOS symbol is a terminal node, which is associated with a element in Σ∗, and therefore, can be scored using the objective s(x,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 ε with visit count n(ε) = 1 and value v(ε) = v̂(ε), which corresponds to the score obtained by translating 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 ε 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 ◦ y with the highest score according to the continuous upper confidence tree criterion (Auger et al., 2013):
UCT(p, y) = v̄(p ◦ y) + C √ n(p)
1 + n(p◦y) π(y | y(p)), (1)
where C is a hyperparameter weighting two terms. The first term v̄(p ◦ y) encourages exploitation of nodes with known high value. The second term √ n(p)
1+n(p◦y) π(y | y(p)) encourages the algorithm
to explore nodes with low visit counts more thoroughly. Here, we specify the policy as the logprobability obtained from an autoregressive model π(y | y(p)) = p(y | y(p),x). The value of a node is determined by its current estimate v̄(p ◦ y) = v(p◦y) if n(p◦y) > 0. For nodes not yet inserted in the tree, which have no value estimates, we compute an estimated value as:
y∗ = arg max ∀y∈Σ,n(p◦y)>0 v(p◦y)
v̄(p◦y) = v(p ◦ y∗) π(y | y (p))
π(y∗ | y(p)) , (2)
where we estimate v̄(p◦y) by assuming that the ratio between policies π between p ◦ y and the highest value node p ◦ y∗ is the same as the ratio between their values 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) = 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 Σ 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 Σ and low playout cost 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 y(p) and correspond to the content in the source sentence x, and can be excluded using the value estimate described in Equation 2.
Next, we ascend from the selected node p ◦ y, updating visit counts and value estimates: n(p) ← n(p) + 1 v(p) ← max{v(p), v(p◦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.

heading: 3.3 BEAM ADAPTIVE TREE SEARCH

text:
A standard way to guarantee progression in MCTS is to run an instance of MCTS per word. Here, we would run an ATS instance ATS(ε, k) with k iterations starting from root ε. Then, we set ε← ε ◦ y∗1 , where y∗1 = arg maxy∈Σ v
(ε◦y) is the child with the highest value estimate and repeat this process until y∗i = 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:
UCTconstrained(p, y, dmin) = { UCT(p, y) d(p◦y) > dmin −∞ otherwise (3)
where d(p◦y) is initialised as `(p ◦ y), a function that counts the number of edges required to reach the root node from (p ◦ y). Then, the following update rule is added to ensure that the d(p) stores that depth of the deepest node achievable from p:
d(p) ← max{d(p), d(p◦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◦y) > dmin tests whether p ◦ y contains a node deeper than dmin. We define BATS(ε, k) as a Beam ATS instance that runs ATS starting from the root node ε with the selection criteria UCTconstrained with dmin = 0 and gradually increasing dmin by 1 every k iterations. Search stops when no node satisfies d(p◦y) > dmin or until a maximum depth dmax.

heading: 4 OBJECTIVES

text: 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.

heading: 4.1 MAX RANK

text:
Decoding in autoregressive models generally optimises a normalised log probability (Wu et al., 2016), (log p(y | x)) ( 65+|y| ) α, which combines the sum of the token level log-probabilities (when α = 0)
and a length-based adjustment, which approximates the mean of the log-probabilities as the length |y| grows (when α = 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:
r(yi | y1, . . . , yi−1,x) = ∑ y∈Σ δ(p(yi | y1, . . . , yi−1,x) > p(y | y1, . . . , yi−1,x))
|Σ| where we count the number of actions in Σ with lower log-probability than yi. 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:
MR(x,y) = |y|
max i=1
log r(yi | y1, . . . , yi−1,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.

heading: 4.2 NOISY CHANNEL MODEL

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

heading: 4.3 MINIMUM RISK TRAINED AUTOREGRESSIVE MODELS

text: 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(y, y′) by minimizing it in a subset of Σ∗ 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).

heading: 5 EXPERIMENTS

heading: 5.1 SETUP

text:
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 multiquery 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 α = 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.2

heading: 5.2 RESULTS

text:
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”).3 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.

heading: 5.3 BEAM SEARCH AND BATS

text:
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(x,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
2Tuning λ using BATS to genererate candidates yields similar weights. 3The optimal models with the highest BLEU on the validation for Beam Search and BATS are the same.
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 (α = 0)” and “Log ProbabilityAR (α = 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 (α = 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 (α = 0.8) + NCNAR) and Max Rank (Row “Log Probability (α = 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 (α = 0.8) + NC”) and when Max Rank is applied (Column “Log Probability (α = 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 (α = 0.8)AR”). Figure 1 shows that once MRT is applied (Column “Log Probability MRT (α = 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%.

heading: 6 CONCLUSION

text:
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
Beam Search BATS s(x,y) BLEU Beam BLEU Iter Delta
Log Probability(α = 0)AR 24.7 2 24.2 1 -2.0% Log Probability(α = 0.8)AR 25.0 8 24.7 8 -1.2% Log Probability (α = 0.8) + NCNAR 25.2 16 25.4 32 0.6% Log Probability (α = 0.8) + MRNAR 26.8 32 27.4 128 2.5% Log Probability (α = 0.8) + MR + NCNAR 26.7 32 27.4 128 2.6% Log Probability MRT (α = 0.8)AR 28.2 64 28.7 256 1.8% Log Probability MRT (α = 0.8) +MRNAR 28.6 8 29.0 256 1.7% Oracle BLEUNAR 38.6 256 53.7 256 39.2%
Decoding budget
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.
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.

heading: ACKNOWLEDGMENTS

text: We thank Rémi Leblond and Phil Blunsom for useful feedback throughout the different stages of this project.

heading: A APPENDIX

text:
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.
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 (α = 0.8) + MP”) and the Max Rank objective (Row “Log Probability (α = 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(α = 0.8)”). Additionally, it clearly does not address the degenerate solutions problem in autoregressive models.
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 (Popović, 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(y, y′) = − 12 BLEU(y, y ′) − 12 ChrF(y, y ′), where BLEU(·) is the sentence level sacreBLEU (Post, 2018) and ChrF(·) is the sentence level ChrF (Popović, 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 bleu(·), chrf(·) 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.
A.4 COMPUTATIONAL COST OF BATS
For Beam Search with beam size b and a max sentence length Y , beam search requires b× Y ×A operations, where A is a transformer+softmax block. Additionally, for reranking, the model score s(x,y) needs to be computed for each of the b translations and has a computational cost of B. Thus, the total cost is b × (Y × 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(x,y). Thus, each rollout requires Y ×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)× (Y ×A+B), where z is the number of non-root nodes expanded more than once. As Y ×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 (α = 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).
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.
sum of probabilities
∑
j≤i log p(yj |y1,...,yj−1,x)
( 5+i6 ) α with α = 0.8. This example is obtained from the WMT2020 test set.

title: ENABLING ARBITRARY TRANSLATION OBJECTIVES WITH ADAPTIVE TREE SEARCH


summaries: This paper presents a model for detecting irregularities in images, such as would occur in manufacturing acceptance testing.  As a form of anomaly detection, the claims made are for a principled modeling approach and an adaptive algorithm quick to learn from just a few samples.   Based on "energy based models" for modeling data densities, the paper claims improvements to avoid the need for retraining for new tasks, such as, instead of synthesizing negative samples rom noise, using a more targeted method of “learning from inpainting” operation to learn anomalies.

summaries: The paper proposes a framework for anomaly detection and localization that allows fast adaptation to new tasks.  Specifically, the authors propose an energy-based model (EBM) with an adaptive sparse coding layer directly trained with normal features of a target task.  A meta-learning process is followed to extract common knowledge across tasks enabling few shots adaptation.  Shrinkage functions, sparse coding with large receptive fields, and learning by inpainting are introduced to improve and accelerate the EBM training.

summaries: This paper proposes an image classification system, where a set of normal patterns are stored as a "dictionary," and the degree of deviation is used as the anomaly score.    The overall architecture seems to feature a conventional deep encoder and a pattern matching module that compares the encoded latent vector against the pattern dictionary. The pattern matching is done by solving the lasso regression problem.   The authors propose a certain online learning approach, following existing few-shot learning methods, and also a synthetic sample generation approach using random perturbation combined with a gradient method.

summaries: The paper presents an anomaly detection algorithm that uses an EBM (Energy Based Model) to distinguish between 'normal' and 'anomaly'. This model generates pseudo-anomaly instances on-the-fly for each 'normal' instance and then learns to assign low energy to normal instances and high energy to pseudo-anomaly instances. The model is further designed to be able to adapt quickly (few 'normal' labeled examples) to new tasks.

abstractText: The ability to detect anomaly has long been recognized as an inherent human ability, yet to date, practical AI solutions to mimic such capability have been lacking. This lack of progress can be attributed to several factors. To begin with, the distribution of “abnormalities” is intractable. Anything outside of a given normal population is by definition an anomaly. This explains why a large volume of work in this area has been dedicated to modeling the normal distribution of a given task followed by detecting deviations from it. This direction is however unsatisfying as it would require modeling the normal distribution of every task that comes along, which includes tedious data collection. In this paper, we report our work aiming to handle these issues. To deal with the intractability of abnormal distribution, we leverage Energy Based Model (EBM). EBMs learn to associates low energies to correct values and higher energies to incorrect values. As its core, the EBM employs Langevin Dynamics (LD) in generating these incorrect samples based on an iterative optimization procedure, alleviating the intractable problem of modeling the world of anomalies. Then, in order to avoid training an anomaly detector for every task, we utilize an adaptive sparse coding layer. Our intention is to design a plug and play feature that can be used to quickly update what is normal during inference time. Lastly, to avoid tedious data collection, this mentioned update of the sparse coding layer needs to be achievable with just a few shots. Here, we employ a meta learning scheme that simulates such a few shot setting during training. We support our findings with strong empirical evidence.

authors:
Jinwon An
Sungzoon Cho

title: Variational autoencoder based anomaly detection using reconstruction probability

venue: Special Lecture on IE,

authors:
Abdourrahmane M Atto
Dominique Pastor
Gregoire Mercier

title: Smooth sigmoid wavelet shrinkage for non-parametric estimation

venue: IEEE International Conference on Acoustics, Speech and Signal Processing,

authors:
Yuequan Bao
Zhiyi Tang
Hui Li
Yufeng Zhang

title: Computer vision and deep learning–based data anomaly detection method for structural health monitoring

venue: Structural Health Monitoring,

authors:
Paul Bergmann
Sindy Löwe
Michael Fauser
David Sattlegger
Carsten Steger

title: Improving unsupervised defect segmentation by applying structural similarity to autoencoders

authors:
Paul Bergmann
Michael Fauser
David Sattlegger
Carsten Steger

title: Mvtec ad–a comprehensive real-world dataset for unsupervised anomaly detection

venue: In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition,

authors:
Richard J Bolton
David J Hand

title: Statistical fraud detection: A review

venue: Statistical science,

authors:
Louis Clouâtre
Marc Demers

title: Figr: Few-shot image generation with reptile

venue: arXiv preprint arXiv:1901.02199,

authors:
Niv Cohen
Yedid Hoshen

title: Sub-image anomaly detection with deep pyramid correspondences

venue: arXiv preprint arXiv:2005.02357,

authors:
Ingrid Daubechies
Michel Defrise
Christine De Mol

title: An iterative thresholding algorithm for linear inverse problems with a sparsity constraint

venue: Communications on Pure and Applied Mathematics: A Journal Issued by the Courant Institute of Mathematical Sciences,

authors:
David Dehaene
Oriel Frigo
Sébastien Combrexelle
Pierre Eline

title: Iterative energy-based projection on a normal data manifold for anomaly localization

authors:
Yilun Du
Igor Mordatch

title: Implicit generation and generalization in energy-based models

venue: NeurIPS,

authors:
Yilun Du
Shuang Li
Joshua Tenenbaum
Igor Mordatch

title: Improved contrastive divergence training of energy based models

venue: International Conference on Machine Learning,

authors:
Chelsea Finn
Pieter Abbeel
Sergey Levine

title: Model-agnostic meta-learning for fast adaptation of deep networks

venue: In International Conference on Machine Learning,

authors:
Chelsea Finn
Kelvin Xu
Sergey Levine

title: Probabilistic model-agnostic meta-learning

venue: arXiv preprint arXiv:1806.02817,

authors:
Ergin Utku Genc
Nilesh Ahuja
Ibrahima J Ndiour
Omesh Tickoo

title: Energy-based anomaly detection and localization

venue: arXiv preprint arXiv:2105.03270,

authors:
Spyros Gidaris
Nikos Komodakis

title: Generating classification weights with gnn denoising autoencoders for few-shot learning

venue: In IEEE Conference on Computer Vision and Pattern Recognition,

authors:
Jonathan Gordon
John Bronskill
Matthias Bauer
Sebastian Nowozin
Richard E Turner

title: Metalearning probabilistic inference for prediction

venue: arXiv preprint arXiv:1805.09921,

authors:
Kaiming He
Xiangyu Zhang
Shaoqing Ren
Jian Sun

title: Deep residual learning for image recognition

venue: In Proceedings of the IEEE conference on computer vision and pattern recognition,

title: Training products of experts by minimizing contrastive divergence

venue: Neural computation,

authors:
Yuling Jiao
Bangti Jin
Xiliang Lu

title: Iterative soft/hard thresholding with homotopy continuation for sparse recovery

venue: IEEE Signal Processing Letters,

authors:
Ming-Yu Liu
Xun Huang
Arun Mallya
Tero Karras
Timo Aila
Jaakko Lehtinen
Jan Kautz

title: Few-shot unsupervised image-to-image translation

venue: In Proceedings of the IEEE/CVF International Conference on Computer Vision,

authors:
W. Liu
D. Lian W. Luo
S. Gao

title: Future frame prediction for anomaly detection – a new baseline

authors:
Wenqian Liu
Runze Li
Meng Zheng
Srikrishna Karanam
Ziyan Wu
Bir Bhanu
Richard J Radke
Octavia Camps

title: Towards visually explaining variational autoencoders

authors:
Cewu Lu
Jianping Shi
Jiaya Jia

title: Abnormal event detection at 150 fps in matlab

venue: In Proceedings of the IEEE international conference on computer vision,

authors:
Yiwei Lu
K Mahesh Kumar
Seyed shahabeddin Nabavi
Yang Wang

title: Future frame prediction using convolutional vrnn for anomaly detection

venue: IEEE International Conference on Advanced Video and Signal Based Surveillance (AVSS),

authors:
Yiwei Lu
Frank Yu
Mahesh Kumar Krishna Reddy
Yang Wang

title: Few-shot scene-adaptive anomaly detection

venue: In European Conference on Computer Vision,

authors:
Weixin Luo
Wen Liu
Shenghua Gao

title: A revisit of sparse coding based anomaly detection in stacked rnn framework

venue: In Proceedings of the IEEE International Conference on Computer Vision,

authors:
Vijay Mahadevan
Weixin Li
Viral Bhalodia
Nuno Vasconcelos

title: Anomaly detection in crowded scenes

venue: IEEE Computer Society Conference on Computer Vision and Pattern Recognition,

authors:
Biswanath Mukherjee
L Todd Heberlein
Karl N Levitt

title: Network intrusion detection

venue: IEEE network,

authors:
Eric Nalisnick
Akihiro Matsukawa
Yee Whye Teh
Dilan Gorur
Balaji Lakshminarayanan

title: Do deep generative models know what they don’t know

venue: arXiv preprint arXiv:1810.09136,

title: Mcmc using hamiltonian dynamics. Handbook of markov chain monte carlo

authors:
Trong-Nguyen Nguyen
Jean Meunier

title: Anomaly detection in video sequence with appearancemotion correspondence

authors:
Afrooz Purarjomandlangrudi
Amir Hossein Ghapanchi
Mohammad Esmalifalak

title: A data mining approach for fault diagnosis: An application of anomaly detection

venue: algorithm. Measurement,

authors:
Siyuan Qiao
Chenxi Liu
Wei Shen
Alan L Yuille

title: Few-shot image recognition by predicting parameters from activations

authors:
Prajit Ramachandran
Barret Zoph
Quoc V Le

title: Searching for activation functions

venue: arXiv preprint arXiv:1710.05941,

authors:
Sachin Ravi
Hugo Larochelle

title: Optimization as a model for few-shot learning

venue: International Conference on Learning Representations,

authors:
Andrei A Rusu
Dushyant Rao
Jakub Sygnowski
Oriol Vinyals
Razvan Pascanu
Simon Osindero
Raia Hadsell

title: Meta-learning with latent embedding optimization

authors:
Thomas Schlegl
Philipp Seeböck
Sebastian M Waldstein
Ursula Schmidt-Erfurth
Georg Langs

title: Unsupervised anomaly detection with generative adversarial networks to guide marker discovery

venue: In International conference on information processing in medical imaging,

authors:
Vikash Sehwag
Mung Chiang
Prateek Mittal

title: Ssd: A unified framework for self-supervised outlier detection

venue: arXiv preprint arXiv:2103.12051,

authors:
Shelly Sheynin
Sagie Benaim
Lior Wolf

title: A hierarchical transformation-discriminating generative model for few shot anomaly detection

venue: arXiv preprint arXiv:2104.14535,

authors:
Jake Snell
Kevin Swersky
Richard S Zemel

title: Prototypical networks for few-shot learning

authors:
Ricardo Vilalta
Youssef Drissi

title: A perspective view and survey of meta-learning

venue: Artificial intelligence review,

authors:
Oriol Vinyals
Charles Blundell
Timothy Lillicrap
Koray Kavukcuoglu
Daan Wierstra

title: Matching networks for one shot learning

authors:
Max Welling
Yee W Teh

title: Bayesian learning via stochastic gradient langevin dynamics

venue: In Proceedings of the 28th international conference on machine learning

authors:
Jianwen Xie
Yang Lu
Song-Chun Zhu
Yingnian Wu

title: A theory of generative convnet

authors:
Haowen Xu
Wenxiao Chen
Nengwen Zhao
Zeyan Li
Jiahao Bu
Zhihan Li
Ying Liu
Youjian Zhao
Dan Pei
Yang Feng

title: Unsupervised anomaly detection via variational auto-encoder for seasonal kpis in web applications

venue: In Proceedings of the 2018 World Wide Web Conference,

authors:
Jaesik Yoon
Taesup Kim
Ousmane Dia
Sungwoong Kim
Yoshua Bengio
Sungjin Ahn

title: Bayesian model-agnostic meta-learning

venue: In Proceedings of the 32nd International Conference on Neural Information Processing Systems,

authors:
Qiang Zhang
Aldo Lipani
Shangsong Liang
Emine Yilmaz

title: Reply-aided detection of misinformation via bayesian deep learning

venue: In The world wide web conference,

authors:
Bin Zhao
Li Fei-Fei
Eric P Xing

title: Online detection of unusual events in videos via dynamic sparse coding

authors:
Junbo Zhao
Michael Mathieu
Yann LeCun

title: Energy-based generative adversarial network

venue: arXiv preprint arXiv:1609.03126,

authors:
Yang Zhao
Jianwen Xie
Ping Li

title: Learning energy-based generative models via coarse-to-fine expanding and sampling

venue: In International Conference on Learning Representations,

heading: 1 INTRODUCTION

text:
Anomaly detection is an important area of study in the field of artificial intelligence. It has found utility in computer vision applications such as industrial inspection (Bergmann et al., 2019) and video surveillance (Liu et al., 2018; Zhao et al., 2011; Nguyen & Meunier, 2019), in the context of abuse prevention such as misinformation, fraud and network intrusion detection (Zhang et al., 2019; Bolton & Hand, 2002; Mukherjee et al., 1994), and others such as system health monitoring and fault detection (Bao et al., 2019; Purarjomandlangrudi et al., 2014). In this paper, we propose an approach for detecting anomaly in images, where we have carefully designed steps to handle some of the bigger issues that have prevented the deployment of image anomaly detection in the real-world.
Image anomaly detection can generally be defined as the identification of abnormalities in a given image. An exact definition of abnormality in this case is elusive because abnormality can be derived from any unknown distribution outside of a normal population. Many studies have hence focused on modeling the normal population instead of learning irregularities, where the goal is to capture the shared concept among all of the normal data as one or several reference models. This process usually will require investing significant efforts in curating a large enough set of normal samples for each task, after which anomaly is detected as deviations from the reference model(s) (An & Cho, 2015; Xu et al., 2018). Recent work from (Sheynin et al., 2021) provides algorithms that utilize only a few normal samples to train models from scratch. However, the models still have to be provisioned for each new task, which requires considerable human efforts and expertise, and thus lack the fast deployment criterion that is often time critical for real-world applications. In view of these challenges, our goals for this work are threefold. We are interested in designing an anomaly detection system that is capable of: (G1) modeling the normal population while at the same time has a principled approach towards modeling the abnormalities; (G2) quickly adapting to a new task at inference time; and (G3) requiring only a few normal shots to update itself to the new task at hand.
For (G1), we introduce the class of Energy Based Model (EBM), which is an important family of generative models (Zhao et al., 2016; Du & Mordatch, 2019; Xie et al., 2016). EBMs have been shown to demonstrate superior capability on modeling data density and localizing anomaly (Genc et al., 2021). For our purpose, the EBM we adopted learn to assign low energy to normal samples but high energy to abnormal samples. More importantly, the abnormal samples are generated with a procedure known as Langevin Dynamics (LD) (Welling & Teh, 2011), which, in its original form, starts with a noise image (see App. Fig C) and gradually samples from the distribution along the direction of lower energy. This lends itself gracefully to utilizing the generated intermediate samples as negative/abnormal. The LD procedure is then coupled with a contrastive divergence loss (Hinton, 2002) that aims to maximize the energy differences between the normal and abnormal samples.
To achieve (G2), we propose an adaptive sparse coding layer that is attached to the deep feature extractor in the EBM. The deep features are projected into a set of feature vectors along the spatial axes, after which each vector is forwarded to the sparse coding layer, where the dictionary is constructed with the features of a few normal samples of the given task. In essence, the input representation has been decomposed into a linear combination of normal features with the sparsity constraint imposed. The final energy score is measured by the distance between the original and the reconstructed features (after the sparse coding layer). Under this scheme, the dictionary for a particular task is not obtained by learning, but instead is constructed by the feature representations of a few normal samples during inference. As a result, this simple “plug-and-play” trick allows the model to be adapted to novel tasks promptly without re-training. Further, we expect that the dictionary, which is formed by normal features, will not be able to explain the abnormal samples well, causing relatively high reconstruction error that lends itself for subsequent detection. As a bonus, a backward pass from the reconstruction error to the image is also additionally useful for localizing the abnormal regions.
Towards (G3), we utilize meta learning (Vilalta & Drissi, 2002; Finn et al., 2017) to simulate the scenario of being given a new task with a few normal shots to update the dictionary, followed by training the EBM. This is accomplished by episodic training, where in each episode the model is adapted to a held back task that is given a few normal samples. To accelerate the EBM training, we introduce “learning from inpainting”, a simple yet effective strategy for synthesizing hard abnormal samples quicker by starting the LD procedure with a synthesized image that is simply a normal sample with a noise patch injected as opposed to a noise image that is traditionally what is used.
We show the proposed framework is able to efficiently adapt to a novel task (e.g., a new object category or scenes from a new camera) with a few normal samples on both industrial inspection and video surveillance tasks. We provide both qualitative and quantitative results to demonstrate that our method outperforms other adaptive frameworks and is comparable to methods that rely on large amount of normal samples.

heading: 2 BACKGROUNDS

text:
We briefly introduce two key ingredients of the proposed method: EBMs and sparse coding.
Energy-based Model In EBMs, the goal is to learn an energy function Eθ(x) : Rd → R which parametrizes the data density pθ(x) as:
pθ(x) = exp(−Eθ(x))∫ x exp(−Eθ(x)) , (1)
where θ is the parameter of the energy function and Zθ = ∫ x exp(−Eθ(x)) is the partition function. Approximating the true data distribution pdata(x) is equivalent to minimizing the expected negative log-likelihood function over the data distribution, defined by the loss function:
LML = Ex∼pdata(x)[− log pθ(x)] = Ex∼pdata(x)[Eθ(x) + logZθ]. (2) As the computation of LML involves an intractable term Zθ, the common practice is to represent the gradient of LML as,
∇θLML = Ex+∼pdata(x)[∇θEθ(x+)] − Ex−∼pθ(x)[∇θEθ(x−)]. (3) This objective is commonly referred to as the contrastive divergence (Hinton, 2002), which decreases the energy of positive data samples x+ from the true distribution (normal samples in our use case) and increases the energy of negative samples x− from the model pθ (synthesized abnormal samples). In practice, the synthesized negative samples are achieved through Langevin dynamics (Welling &
Teh, 2011), which samples along the direction of decreasing energy score, typically starting from a given noise image:
x̃k = x̃k−1 − β 2 ∇xEθ(x̃k−1) + ωk, ωk ∼ N (0, βI), (4)
where β is the step size. The synthesizing ability of EBMs enables generating abnormal samples to help in learning a more accurate data density, and is often touted as the one of the advantages of using an EBM.
Sparse coding. Approximating a signal z ∈ Rd with the sparse linear combination over a dictionary D ∈ Rd×k can be expressed as:
min α
1 2 ||z−Dα||22 + λ||α||1, (5)
where α is the sparse coefficients, with its sparsity (l1 norm) and λ is the weight of the sparsity constraint. Dα is a sparse approximation to the original signal z. In practice, finding the dictionary atoms and the sparse coefficients is usually formulated as an optimization problem.
In this paper, we adopt Iterative Soft Thresholding Continuation (ISTC) (Jiao et al., 2017) to convert this optimization problem into linear operations with a non-linear shrinkage function, which allows sparse coding to be seamlessly integrated into the deep neural networks. To compute a sparse coefficient α, ISTC performs iterations of gradient steps on reconstruction ||z −Dα||2 and a proximal projection step to increase coefficient sparsity.
Formally, initializing the coefficients at the first step α0 with all zeros, each step of ISTC refines the sparse code with descending values of λ from λmax to λ?: each step of ISTC is expressed as:
αn+1 = σ(αn + D >(z−Dαn), λn), with λn = λmax λmax λ?
−n/N , (6)
where σ(·, ·) here is a shrinkage function that truncates small values (lower than λ) of the coefficients to 0 to enforce sparsity, and can be easily implemented by a customized ReLU activation function:
σ(z, λ) = sgn(z)(max(|z| − λ, 0)) = sgn(z)ReLU(|z| − λ). (7)

heading: 3 PROPOSED METHOD

text: The objective of our proposed method, when given an input image or video frame, is to output an anomaly score indicating how likely this input deviates from the normal, and additionally, a pixel map grounding abnormal regions. In this section, we describe the proposed fast adaptive anomaly detection framework in details. In Section 3.1, we introduce the adaptive EBM which consists of a deep feature extractor followed by an adaptive sparse coding layer. From there, we further show that utilizing larger receptive field in the sparse coding could improve training robustness (Section 3.1.1), and applying smoothed shrinkage functions could help speed up convergence (Section 3.1.2). In Section 3.2, we describe the episodic training regime on various anomaly detection tasks that mimics few-shot adaptation in the meta-testing stage while learning common knowledge across tasks. Finally, Instead of synthesizing negative samples (anomaly) directly from noise, we introduce a simple but effective “learning from inpainting” operation to accelerate the training in Section 3.3.

heading: 3.1 ADAPTIVE ENERGY-BASED MODEL

text:
An EBM is a form of generative model and it is widely used for modeling data density and sampling. While there has been recent work (Genc et al., 2021) applying EBM to anomaly detection, it still requires re-training for each new task. To efficiently adapt the EBM to novel tasks, we introduce an adaptive sparse coding layer which is conditioned on the dictionary constructed by the features of normal samples. Specifically, as illustrated in Fig 1, given an input image, x ∈ R3×h×w, we first obtain the corresponding feature z ∈ Rd×h′×w′ from the deep feature extractor Ψ with parameters θ, so that z = Ψ(x; θ). All feature vectors along spatial axes of z are then sparsely decomposed through the sparse coding layer over a task-specific dictionary D ∈ Rd×Kh′w′ , which contains the features of K normal samples of the current task as shown in the Fig 1(a). Each feature vector
of the normal sample feature is then directly used as an atom in the task dictionary. The decomposed coefficients are α = S(z;D), where α ∈ RKh′w′×h′×w′ and S denotes the iterative sparse decomposition process of (6). By multiplying the coefficient α with the dictionary D, we obtain the reconstructed features z′ = Dα. The sparsity regularization to α is important, as it encourages input features to be reconstructed by simple combinations of dictionary atoms (normal features), so that it would be difficult for features of abnormal samples to be well-approximated, therefore producing higher reconstruction errors that make it conducive for detecting anomalies. From here, the final energy score is formulated as the mean squared error (MSE) between the original and the reconstructed features:
Eθ(x;D) = MSE(z, z′) = ||Ψ(x; θ)−DS ( Ψ(x; θ);D ) ||2. (8)
In effect, Eqn. 8 depicts a conditional EBM, which is conditioned on the task-specific D formed by normal features. In the following sections, we will discuss how to make the training of this adaptive structure more robust.

heading: 3.1.1 SPARSE CODING WITH RECEPTIVE FIELD.

text: As discussed in Section 3.1, the input feature z is represented as h′ × w′ of d-dim feature vectors and they are treated independently while passing through the sparse coding layer. The region of the input image that affects one feature vector is determined by the receptive field of the feature extractor. The trade-off is that a small receptive field may not capture enough contextual information, while applying a large receptive field would make feature maps spatially coarse and make it hard to spot small anomaly regions. To solve this dilemma, instead of carefully tuning the receptive field of each layer of the feature extractor, we introduce a simple yet effective technique of applying the receptive field on the sparse coding layer. Specifically, as Fig 2 shows, rather than performing sparse coding to each individual d-dim feature vectors, we apply it on d × l × l volumes centered around each feature vector, where l is the receptive field. This is equivalent to applying a l × l, sliding window on spatial axes of the feature map and can be easily implemented by image to column (Im2Col) operation. Then we flatten the feature volumes into dl2-dim vectors and adjust the shape of the dictionary accordingly. In this way, we are able to capture contextual information without needing to carefully tune the architecture of the feature extractor and we show in the later experiments that this technique improves the robustness of the network on different types of objects.

heading: 3.1.2 SHRINKAGE FUNCTION

text:
The effectiveness of training the EBM for localizing anomaly regions heavily depends on the gradient propagation from later to earlier layers. It is shown in (Du et al., 2021) that smooth activation functions like Swish Ramachandran et al. (2017) could be beneficial here. Notably, the gradients of
…
𝐳
𝑑
𝑙
𝑙
Im2Col 𝑑×𝑙×𝑙
Figure 2: Illustration of sparse coding layer with l× l receptive filed. 1.00 0.75 0.50 0.25 0.00 0.25 0.50 0.75 1.00 X
1.00
0.75
0.50
0.25
0.00
0.25
0.50
0.75
1.00
Y
Shrinkage functions ( = 0.25) Hard Shrinkage Linear SigShrink =1.0 SigShrink =2.5 SigShrink =5.0 SigShrink =10.0 SigShrink =100.0 SigShrink =1000.0
Figure 3: Shrinkage functions.
the dictionary D are determined by the sparse coding coefficients α as shown in Eqn. 6. However, the sparsity constraint of α would turn off the gradient computation of many elements in D and this could be detrimental during the early stage of the training. To alleviate the sparse gradient issue, we replace the RELU-like shrinkage function in Eqn. 7 with its smoothed counterparts by introducing the Sigmoid based shrinkage functions (SigShrink). The SigShink is originally proposed for non-parametric signal estimation in Atto et al. (2008), and can be defined as:
στ (z, λ) = z
1 + exp(−τ(|z| − λ)) , (9)
where τ is the hyperparameter of smoothness. We present visualizations of the hard shrinkage function Eqn. 7 and SigShrink with different values of τ in Fig 3. Comparing to the hard shrinkage function which truncates small values into zeros, the SigShrink with a large τ can sharply force small values to near-zeros. Therefore, the SigShrink will guarantee non-zero gradients everywhere.

heading: 3.2 EPISODIC TRAINING

text:
To train the proposed adaptive EBM, we perform episodic training that is widely adopted by metalearning based few-shot learning tasks Finn et al. (2017); Snell et al. (2017). Following the terminology of few-shot learning, in each training episode, the model is adapted and tested with a task sampled from the underlying task distribution. Specifically, the model is adapted to a support set of the given task, then a query set with ground truth labels is applied to evaluate the adaptation, which is used to update the model parameters accordingly. As shown in Fig 4, the support set contains K normal samples {xk}Kk=1 of the current task, where K is usually a small number. The feature representations zk = Ψ(xk; θ) of these normal samples are plugged into the dictionary Di ∈ Rd×Kh ′w′ corresponding to the i-th task during the i-th episode to adapt the dictionary to the normal samples of the task. After that, the adapted model is measured by a query set consisting of M normal samples {x̂m}Mm=1 andM abnormal samples {x̂′m}Mm=1. Note that there is no actual abnormal samples given during training, instead, they are iteratively sampled from the EBM and we will discuss the initialization and sampling of these synthetic samples in details in Section 3.3. Recall that the training of EBM with contrastive divergence described in Eqn. 3 requires the estimation of energy scores of both positive samples from the true data distribution and negative samples sampled from the model distribution. The positive energy can be estimated empirically with normal samples from the query set. The negative energy can be estimated by performing the MCMC-based (Markov Chain Monte Carlo) sampling technique (Neal et al., 2011; Welling & Teh, 2011), typically Langevin Dynamics as described in Eqn. 4. Denoting the output of Langevin dynamics (sampled abnormal samples) with the initialization x̂′m as LD(x̂′m), we now have the empirical estimation of the contrastive divergence of the i-th episode as:
Lcd = 1
m M∑ m=1 [ Eθ(xm;Di)− Eθ(LD ( x̂′m);Di )] . (10)
With the energy score equivalent to the feature reconstruction error in Eqn. 8, minimizing Lcd encourages normal features to be well-reconstructed by a sparse linear combination of dictionary atoms while the features from abnormal samples tend to produce relatively higher reconstruction errors so that they can be easily spotted.

heading: 3.3 SYNTHESIZING NEGATIVE SAMPLES

text:
Typical EBM training with contrastive divergence conducts negative sampling from the modeled density using techniques such as Langevin Dynamics, which applies gradient descent to a noise initialization (App. Fig C) with small step size and large number of steps Du & Mordatch (2019). Such negative sampling steps can be costly and we argue that it is unnecessary in our case. Instead, we introduce a new strategy of “learning by inpainting”. Starting from a positive query sample x̂m, we synthesize the corresponding negative sample x̂′m by randomly placing a small uniform noise patch on the image. The Langevin Dynamics procedure is then initialized with the resulting image instead of a noise image. As the Langevin Dynamics proceeds, synthesized abnormal samples LD(x̂′m) are inpainted along the direction of “normal”, x̂m, and we introduce the following reconstruction loss:
Lrec = MSE(LD(x̂′m), x̂m). (11)
The gradient map from Lrec reveals anomaly regions, which helps with localization. We show in Fig 4(a) that, starting from a synthesized abnormal sample, only 5 steps of Langevin dynamic would be sufficient to make it visually close to the corresponding normal sample during training, serving as “hard negatives” that further facilitates the learning. The final loss of the episodic training is simply:
L = η0Lrec + η1Lcd, (12) where η0 and η1 are hyperparameters balancing two loss terms.

heading: 4 RELATED WORK

heading: 4.1 ANOMALY DETECTION

text:
Sparse coding. Early efforts on adopting sparse coding in anomaly detection are based on optimization (with L1 penalty) (Lu et al., 2013; Zhao et al., 2011). Recent advances on iterative sparse thresholding algorithms (Daubechies et al., 2004; Jiao et al., 2017) allow seamless integration of online sparse coding with deep neural networks, and (Luo et al., 2017) formulates the sparse coding as stack RNNs for video anomaly detection.
Generative models. Generative models are widely utilized in anomaly detection due to the capability in modeling the density of desired data distribution. Early efforts on variational autoencoders (VAE) based methods (An & Cho, 2015; Xu et al., 2018) are arguably having hard time calibrating uncertainties in novel samples (Nalisnick et al., 2018), accurately localizing abnormal regions through reconstruction errors (Dehaene et al., 2020). Recent efforts have explored variant generative architectures like energy-based models (EBM) (Genc et al., 2021), GANs (Sheynin et al., 2021), and combining VAE with EBM (Dehaene et al., 2020). Various methods also exploit intra-image structures (Cohen & Hoshen, 2020; Bergmann et al., 2018), cross-frame consistency (Lu et al., 2019), and motion-appearance consistency in videos (Nguyen & Meunier, 2019) while detecting anomaly.

heading: 4.2 FEW-SHOT LEARNING

text: Few-shot learning is extensively explored in classification tasks. Proposed methods are based on optimization (Finn et al., 2017; Rusu et al., 2019; Finn et al., 2018; Yoon et al., 2018; Ravi & Larochelle, 2016), learning metric (Snell et al., 2017; Vinyals et al., 2016) and parameter prediction (Gordon et al., 2018; Qiao et al., 2018; Gidaris & Komodakis, 2019). These technologies are further applied in other tasks like image generation (Clouâtre & Demers, 2019; Liu et al., 2019) and out-ofdistribution detection (Sehwag et al., 2021).

heading: 5 EXPERIMENTS

text: In this section, we conduct evaluation on the industrial inspection task with the benchmark MVTecAD dataset Bergmann et al. (2019) (Section 5.1). Even though our proposed framework is imagebased, we further demonstrate it’s efficacy on the video anomaly detection task in Section 5.2. In Section 5.3, we show ablations and insights relating to the adaptive sparse coding components. We also show additional ablations on robustness to pose variations (e.g. rotation) while applying fewshot adaptation (App. B.1) and comparing with naive background subtraction to detect anomaly (App. B.2).We provide implementation details in App. A.

heading: 5.1 INDUSTRIAL INSPECTION

text:
The goal of this anomaly detection task is to predict whether a manufactured component contains any defects. The MVTec-AD dataset includes 15 categories of object. To demonstrate the fast adaptation capability of the proposed method, we adopt a leave-one-out training strategy. Specifically, samples of each target category are reserved for testing only, and the episodic training is performed on the remaining categories. During the training stage, the model will not see any samples from the target category. During testing, we first adapt the model to the target category with 10 randomly selected
normal samples, then measure the performance with the entire testing set. We run the test 5 times, each time the model is adapted to random sets of 10 normal samples from the target category. The final result is the average of the 5 runs. Following common practice (Bergmann et al., 2019; Liu et al., 2020), we report the performance of pixel-wise anomaly localization with AUC-ROC and mIoU (mean intersection over union). IoU is the area of overlap between the predicted map and the ground truth divided by the area of union between these two.
To the best of our knowledge, no existing methods feature fast adaptation like ours. We first show the performance of fully supervised methods, which train each category with normal samples from scratch, as the “upper-bounds”. Specifically, (Bergmann et al., 2018; 2019) trains auto-encoders (AE) on massive number of normal samples and measure the reconstruction errors during the inference; AnoGAN (Schlegl et al., 2017) adopts a generative adversarial network (GAN) to learn a manifold of normal; VE-VAE (Liu et al., 2020) presents a visually explainable variational autoencode through gradient-based attention. Furthermore, we create a strong baseline by applying model-agnostic meta-learning (Finn et al., 2017) on an AE (denoted as MAML-AE, detailed in App. Sec. A.3). Numerical results of pixel-wise anomaly localization are in Table 1. Note that all results of our methods are obtained without any data augmentation. Our proposed method outperforms MAML-AE by a large margin and is competitive with the “upper-bounds”. We show the localized anomaly regions from our method in Fig 5. Additional visualizations are in the App. Fig A.

heading: 5.2 VIDEO SURVEILLANCE

text:
In video anomaly detection, a common goal is to detect abnormal events captured by surveillance cameras (e.g., a motorcycle on the sidewalk). A model trained on videos from one camera might not generalize well on other cameras due to different locations / mounting heights / lightning conditions, and it is not feasible to train one model for every new camera in practice. The ability to quickly adapt to new scenes is a significant contribution to the task of video surveillance. We are only aware of the work in (Lu et al., 2020) (r-GAN) that has such adaptation capability. Specifically, the model adapts to a new scene using gradient descent with several beginning frames of a query video, after which a GAN is applied to generate future frames. Anomaly is then detected via the discrepancy between predicted future frames and the original frames.
We follow the same evaluation regime as r-GAN by training with normal samples in all 13 scenes from SH-Tech Liu et al. (2018) and testing on UCSD Pedestrian 1, UCSD Pedestrian 2 (Mahadevan et al., 2010), and CUHK Avenue Lu et al. (2013). Note that since our method is image-based, it predicts the video frames independently without leveraging any temporal information as in r-GAN.
Category Leather Grid Hazelnut Cable Pill
l = 1 0.41 0.98 0.11 0.80 0.36 0.91 0.21 0.85 0.10 0.85 l = 3 0.42 0.98 0.12 0.81 0.40 0.94 0.24 0.87 0.22 0.88
Table 3: Comparison of different sparse coding receptive fields. We report both mIoU (left) and AUC-ROC (right) values.
Category Leather Hazelnut Cable
Ours 0.42 0.98 1.6e-4 0.40 0.94 2.4e-4 0.24 0.87 2.0e-4 No sparsity 0.32 0.90 0.9e-4 0.24 0.80 1.7e-4 0.12 0.68 1.5e-4
Table 4: Performance w/ and w/o sparsity constraint. From left to right: mIoU; AUC-ROC; the difference of averaged reconstruction errors between abnormal/normal samples.
In each episode, we adapt our model with a support set containing a few normal frames randomly sampled from the target scenes. In Table 2, we compare our method against r-GAN pre-trained on SH-Tech only (r-GAN Pre-train), fine-tuned on target datasets (r-GAN Fine-tune), and with one step gradient descent with meta-learning (r-GAN MAML). We also show the performance of MAML-AE as a baseline for image-based meta-learning method. In the last section of Table 2, we present intradataset results as well by training with 6 scenes of SH-Tech and testing on remaining 7. We follow common evaluation protocol and measure the frame-level AUC-ROC. Without leveraging temporal information and performing re-training (gradient descent), our method achieves comparable results to r-GAN MAML and outperforms image-based meta-learning method by a large margin.

heading: 5.3 ABLATION STUDIES

text: Sparse coding receptive fields. To evaluate the effectiveness of using large receptive fields in the sparse coding layer, we conduct additional experiments on the MVTec-AD dataset, and select 5 representative categories with different levels of difficulties to present the comparisons with l = 1 and l = 3 (Sec. 3.1.1) in Table 3. Sparse coding with large receptive field clearly benefits more complex structural objects (hazelnut, cable, and capsule), while the improvements are limited for the texture objects (leather and grid), where contextual regularization is intuitively less important. Shrinkage functions. To show the benefits of smooth shrinkage function, we plot the loss curves of models trained with smooth SigShrink (Eqn. 9) and non-smooth RELU-like shrinkage (Eqn. 7) functions in Fig 7. The model with smooth shrinkage function converges notably faster in the early training stage and achieves lower loss. Sparsity constraint. As discussed in Section 3.1, we impose sparsity constraint to the feature decomposition in the adaptive sparse coding layer, in order to prevent abnormal features from being well-approximated by the linear combinations of normal features, so that the reconstruction errors are effective for detecting anomaly. To validate this, we conduct experiments by removing the shrinkage function σ in the sparse coding stage (Eqn. 6). We show comparison in Table 4 with mIoU, AUC-ROC, and the difference of averaged reconstruction errors between abnormal and normal samples. Without sparsity, the performance drops dramatically, and reconstruction errors of normal and abnormal samples become closer.

heading: 6 CONCLUSION

text: In this paper, we introduced a novel framework for anomaly detection and localization that allows fast adaptation to new tasks. We formulated our model as an energy based model with an adaptive sparse coding layer, of which the dictionary is directly formed by normal features of a target task. We adopted episodic meta-learning to extract common knowledge across tasks, which has the effect of enabling few shots adaptation. We further introduced smooth shrinkage functions, sparse coding with large receptive fields, and learning by inpainting to improve and accelerate the EBM training. It’s worthy to note that when evaluating our method’s performance on industrial inspection and video anomaly detection, our method is comparable and even boasts better performance than methods trained with a large amount of normal samples. Through this work, we hope to have made a significant contribution to the important problem of anomaly detection by shedding light on our findings that anomaly detection can indeed be generalized to new tasks.

heading: B ADDITIONAL ABLATIONS

text:
B.1 ROBUSTNESS TO POSE VARIATIONS
To validate the robustness of our method to pose variations, we perform additional experiments with pose variations and provide the quantitative comparisons in Table B. We report results by performing random ±90o rotation to samples during testing stage when adapting the trained model to novel categories. We observe that the textures categories (leather and grid) are robust to any pose variations in both the query and support samples. For the hazelnut category, where there are intrinsically significant pose variations across samples, performing any new rotations does not influence the results. On the other hand, for the pill category, where all samples are aligned horizontally (see examples in Appendix, Figure A), performing rotation to only query samples results in performance drop. Performing rotation to both query and support samples help to recover the performance. The above results suggest the robustness of our methods under the condition of sufficient sample diversity in the support set.
Category Leather Grid Hazelnut Cable Pill
Original 0.42 0.98 0.12 0.81 0.40 0.94 0.24 0.87 0.22 0.88 Rotate query 0.41 0.98 0.12 0.80 0.40 0.94 0.21 0.82 0.10 0.71
Rotate query and support 0.42 0.98 0.11 0.81 0.40 0.94 0.23 0.85 0.19 0.86
Table B: Robustness to pose variations. We report both mIoU (left) and AUC-ROC (right) values.
B.2 COMPARISON TO IMAGE DIFFERENCING
Image differencing and its variances are an intuitive approach for detecting image anomaly. We perform image differencing and background subtraction on the industrial inspection and video anomaly detection task, respectively, and report performance in Table C. Our method demonstrates clear advantages.
Category Leather Hazelnut Cable UCSD Ped1 UCSD Ped2 CUHK
Image differencing 0.02 0.57 0.12 0.77 0.07 0.65 65.34 59.03 57.12 Ours 0.42 0.98 0.40 0.94 0.24 0.87 77.42 91.22 75.32
Table C: Comparing with image differencing. We report mIoU (left) and AUC-ROC (right) for industrial inspection task and AUC-ROC for video anomaly detection task.
B.3 ROBUSTNESS AGAINST CONTAMINATED TRAINING DATA
While it is a common practice among machine learning practitioners to assume clean training data, this may not be true in real world applications. In this section, we evaluate the robustness of our method against contaminated training data by inserting certain amount of abnormal samples. As shown in Table D, we progressively contaminate the normal training data by increasing the amount of abnormal data from 1% to 10%. Our proposed method is in general robust to data contamination, where contamination under 5% only decreases the performance slightly. The network is still able to perform decently in the extreme case of 10% contamination.
Contamination Leather Grid Hazelnut Cable Pill
0% 0.42 0.98 0.12 0.81 0.40 0.94 0.24 0.87 0.22 0.88 1% 0.42 0.98 0.11 0.80 0.40 0.94 0.23 0.86 0.21 0.88 2% 0.41 0.98 0.11 0.80 0.40 0.93 0.23 0.84 0.21 0.87 5% 0.40 0.96 0.11 0.78 0.39 0.93 0.22 0.84 0.20 0.87
10% 0.38 0.95 0.10 0.76 0.37 0.90 0.21 0.82 0.19 0.85
Table D: Performance evaluation against data contamination. We contaminate the normal training data by inserting increasing percentages of abnormal data.
B.4 LEVERAGING TEMPORAL INFORMATION
An EBM is agnostic to the underlying backbone network architecture, therefore it is straightforward to incorporate temporal information into the image-based anomaly detection framework described in Section 5.2. We replace the 2D convolutions in the first four layers with 3D convolutions, and have the model accepts a 5-frame input instead. Without heavy tuning, we report 5-shot performance on both ’1 frame’ (original, without temporal) and ’5 frames’ (with temporal) in Table E. The results show that when temporal information is added, it leads to further improvements.
Category UCSD Ped1 UCSD Ped2 CUHK Sh-Tech
1 frame 78.12 92.00 83.41 79.64 5 frames 79.06 91.94 84.27 80.80
Table E: Performance comparisons with temporal information incorporated.

heading: C QUALITATIVE RESULTS

text: We present in Figure 1 additional anomaly localization results of categories with different anomalies in the MVTec-AD dataset.

heading: D ADDITIONAL FIGURES

text:
Common practice of sampling from EBMs is computationally costly, requiring as many as 50 steps of Langevin Dynamics when initialized with full noise, instead of a synthesized negative sample as shown in Fig. B. Some examples are provided in Fig. C.
Input GT Prediction Input GT Prediction Input GT Prediction
Figure A: Visualizations of anomaly localization on industrial inspection data. All results are obtained by adapting the model using 10 normal samples only.
Normal sample Synthesized negative Step 1 Step 2 Step 3 Step 4 Step 5
Figure B: Sampling outputs after a few steps of Langevin Dynamics starting from each synthesized negative sample. 5 steps of Langevin dynamics are sufficient to quickly generate hard negative samples with minor artifacts.
Figure C: Figure from (Zhao et al., 2020). Generated sequences from the process of Langevin Dynamics. Initialization from noise usually requires around 50 steps to synthesize the images with desired quality (images are shown every 5 steps).