# Utility-Probability Duality of Neural Networks

Huang Bojun
Rakuten Institute of Technology,
Rakuten Group, Inc.
<EMAIL_ADDRESS>&Fei Yuan
Shanghai Artificial Intelligence
Laboratory
<EMAIL_ADDRESS>Correspondence to: Huang Bojun <<EMAIL_ADDRESS>>

###### Abstract

It is typically thought that supervised training of modern neural networks is
a process of fitting the groudtruth probabilities. However, many counter-
intuitive observations in language generation tasks let one wonder if this
canonical probabilistic explanation can really account for the observed
empirical success. To resolve this issue, we propose an alternative _utility-
based explanation_ to the standard supervised learning procedure in deep
learning. The basic idea is to interpret the learned neural network not as a
probability model but as an _ordinal utility_ function Fishburn (1990) that
encodes the preference revealed in training data. We developed a theory based
on this utility-based interpretation, in which the theoretical expectations
and empirical observations are better reconciled.

##  1 Introduction

In this paper we challenge, and fix, a standard explanation of deep learning.
The prevailing mindset nowadays is to _interpret_ a neural network
$f({\boldsymbol{w}})$ as a parametric model of the conditional probability
distribution
$\mathbf{P}_{{\boldsymbol{w}}}[Y=\boldsymbol{y}|X=\boldsymbol{x}]$, where $X$
is an expected input of the task under concern (e.g. an image/sentence/speech
audio), and $Y$ is an expected output given $X$ (e.g. a class label, a score,
or a structured object such as a sentence or an action plan) which is assumed
to follow a groundtruth distribution $\mathbf{P}_{\text{true}}$. Training of
the neural network $f({\boldsymbol{w}})$ is then _thought_ to be the process
of approximating $\mathbf{P}_{\text{true}}$ with
$\mathbf{P}_{{\boldsymbol{w}}}$. Indeed, in Goodfellow et al. (2016), the deep
learning textbook writes (p.138): “ _most supervised learning algorithms in
this book are based on estimating a probability distribution $p(y|x)$_”.

This probability interpretation of neural networks supports two natural ways
to use the learned probability model $\mathbf{P}_{{\boldsymbol{w}}}$ at
inference time. The first way is to choose the most likely output in
$\mathbf{P}_{\boldsymbol{w}}$:

$\boldsymbol{y}_{\texttt{MAP}}\doteq\arg\max_{\boldsymbol{y}}~{}\mathbf{P}_{{\boldsymbol{w}}}[Y=\boldsymbol{y}|X=\boldsymbol{x}]$
(1)

where MAP stands for _maximum a-posteriori probability_. When
$\mathbf{P}_{{\boldsymbol{w}}}=\mathbf{P}_{\text{true}}$,
$\boldsymbol{y}_{\texttt{MAP}}$ is a provably optimal output in many common
scenarios Bishop (2006); see Appendix A for a rigorous analysis.

Another sensible decision rule is to sample the output from the distribution
$\mathbf{P}_{{\boldsymbol{w}}}$, which makes the actual output a random
variable, denoted by $A$ here:

$A\sim\mathbf{P}_{{\boldsymbol{w}}}[Y=\cdot|X=\boldsymbol{x}]$ (2)

When $\mathbf{P}_{{\boldsymbol{w}}}=\mathbf{P}_{\text{true}}$, the stochastic
output $A$ is not necessarily optimal, but is necessarily a good output as
long as the expected output $Y$ is the output of a good decision policy
(because $A$ is identically distributed with $Y$; see Appendix B for more
elaboration on the soundness of the sampling rule).

The two decision rules (1) and (2) underlie a long tradition in the ML
community that reduces the problem of _learning to make decisions_ to a
probability estimation problem 111 The tradition was there before the deep
learning era. In another classic ML book, Bishop (2006) writes “
_determination of $p(\boldsymbol{x},t)$ … forms the subject of much of this
book_” (p.38). : If we could estimate $\mathbf{P}_{\text{true}}$ perfectly,
our decision would be guaranteed good. In reality, the approximation of
$\mathbf{P}_{\text{true}}$ with $\mathbf{P}_{{\boldsymbol{w}}}$ always comes
with errors, but the correspondence in the limit between decision making and
probability estimation still gives the reasonable expectation that the closer
the probability estimation is, the better the induced decision – by the two
decision rules (1) and (2) – would be.

However, it is known that many neural networks with excellent decision quality
are actually poorly calibrated in terms of probability estimation Guo et al.
(2017); Minderer et al. (2021). In fact, Guo et al. (2017) reported that for
some popular NN architectures, more powerful models (in terms of
classification quality) tend to be worse calibrated in terms of how
$\mathbf{P}_{{\boldsymbol{w}}}$ matches $\mathbf{P}_{\text{true}}$.

More importantly, recent empirical studies in NLP found that for a variety of
language generation tasks, both the MAP rule $A=\boldsymbol{y}_{\texttt{MAP}}$
and the sampling rule $A\sim\mathbf{P}_{{\boldsymbol{w}}}$ lead to very bad
performance in terms of text/decision quality Stahlberg and Byrne (2019);
Cohen and Beck (2019); Eikema and Aziz (2020); Holtzman et al. (2019); this is
the case even for extensively-trained models with state-of-the-art
architectures. On the other hand, greedy or near-greedy outputs, as a kind of
“economic yet sub-optimal” choices from the probabilistic perspective, turn
out to work significantly better, and is often the _only_ solution that is
known to work satisfactorily, not in cost, but in quality Wu et al. (2016).
These paradoxical observations form an explainability issue that challenges
the probabilistic rationale behind the empirical success in related domains
(Section 2).

To resolve this issue, we propose an alternative _value-based explanation_ to
the standard supervised learning procedure in deep learning. The basic idea is
to interpret the learned neural network not as a probability model but as an
_ordinal utility_ function Fishburn (1990); Moscati (2018) that encodes human
preference revealed in training data. We develop a theory based on this value-
based interpretation, in which the theoretical expectations and empirical
observations are better reconciled.

Specifically, in Section 3 we point out that a softmax-normalized neural
network model also comes with an un-normalized sub-model for the logits, and
that this logit sub-model is the actual functioning part of the overall model
at inference/decision time. As a result, the standard MLE training process for
softmax probability model can be equivalently seen as a certain learning
dynamic for the un-normalized sub-model. Now suppose we could _directly_
explain why the sub-models trained with this particular learning dynamic
_will_ support good greedy decisions – in a way that the explanation does not
resort to probabilistic semantics of the (sub-)model – then the probability-
based interpretation would become unnecessary and can be bypassed. What is
bypassed together is the contradiction between the probabilistic
interpretation and experimental observations.

In Section 4, we indeed provide such a non-probabilistic explanation. Without
the probabilistic semantic, the “logit sub-model” is re-interpreted as just a
Q-function, and we show that the “MLE-equivalent learning dynamic” of this
Q-function is a perturbed variant of a particular supervised Q-learning
algorithm family (called _MABE_). We mathematically prove that the unperturbed
variant of this family is indeed training the Q-function toward an _optimal_
utility function that gives optimal output under greedy decision. Then we
experimentally intervene the perturbation term, and show that the perturbation
(which makes the “MLE-equivalent variant” different from the unperturbed
variant) has little impact on the learning dynamic empirically.

Moreover, in Section 5 we derive an equation from this utility-based theory
which allows us to transform the learned Q-values back to estimations of
$\mathbf{P}_{\text{true}}$, thus bringing back the probabilistic semantic.
However, the utility-based probability estimation, called _dual probability_
in the paper, encodes a different probability space from the canonical softmax
probabilities. Intriguingly, running probability-based decision rules (1) and
(2) based on the dual probability leads to _dramatically_ better performance
in all tasks we examined (e.g. +14.6 BLEU for sampling and +17.3 for MAP in
WMT’14 en2de translation), and it also gives more reasonable probability
predictions. This result implies that the standard supervised learning
procedure in deep learning – as a utility-learning procedure now – may indeed
correspond to a dual process of probability learning, _but_ , the probability
space learned from this dual process may not be best represented by the
softmax probabilities as usually perceived.

Overall, all the evidences above collectively revealed a phenomenon of
_utility-probability duality_ , that a neural network is perhaps both a
utility function and a probability function in many deep learning settings
(Section 6).

##  2 The Paradox

It is relatively well known that the probabilities predicted by many deep
neural networks (that well support decision making in practice) do not match
the true probabilities very well Guo et al. (2017). But this observation alone
does not necessarily contradict with the probabilistic rationale behind neural
network learning. The genuine paradox manifests itself through a _reversal_ in
terms of the quality between “supposedly-rational” and “supposedly-irrational”
decisions from the probabilistic perspective. Such a reversal was observed in
a variety of _language generation_ tasks, such as machine translation Koehn
and Knowles (2017), abstractive summarization Cohen and Beck (2019), and image
captioning Holtzman et al. (2019). In this work we used three such tasks for
experimentation: WMT’14 English$\rightarrow$German (en2de), the most-widely
used machine translation (MT) benchmark, consisting of $4.5$ millions training
sentences; WMT’17 Chinese$\rightarrow$English (zh2en), another classic MT
benchmark where the source and target languages are remote, consisting of $21$
millions training examples; CNN/DailyMail, the most-widely used benchmark for
abstractive document summarization, consisting of nearly $300$ thousands of
document-abstract pairs.

###  2.1 The Expectations

In these tasks, the expected output $\boldsymbol{y}=(y_{\scriptscriptstyle
1},y_{\scriptscriptstyle 2},\dots,y_{\scriptscriptstyle T})$ consists of a
sequence of atomic decisions; each $y_{\scriptscriptstyle t}$ is called a
_token_ without loss of generality. In this case, a neural network
$f({\boldsymbol{w}})$ is usually thought to be an _auto-regressive model_ that
represents the token-wise conditional probabilities:
$f_{[y_{\scriptscriptstyle
t}]}(\boldsymbol{x},\boldsymbol{y}_{<t};{\boldsymbol{w}})=\mathbf{P}_{{\boldsymbol{w}}}[y_{t}|\boldsymbol{x},\boldsymbol{y}_{<t}]$,
where $f_{[y_{\scriptscriptstyle t}]}$ denotes the vector-component of $f$’s
output that corresponds to token $y_{\scriptscriptstyle t}$, and
$\boldsymbol{y}_{<t}\doteq(y_{\scriptscriptstyle 1},y_{\scriptscriptstyle
2},\dots,y_{\scriptscriptstyle t-1})$ denotes the partial output up to
decision step $t$. Such a neural network encodes
$\mathbf{P}_{{\boldsymbol{w}}}[\boldsymbol{y}|\boldsymbol{x}]$ through the
_product rule of probability_ , with

$\mathbf{P}_{{\boldsymbol{w}}}[\boldsymbol{y}|\boldsymbol{x}]=\prod\nolimits_{t}\mathbf{P}_{{\boldsymbol{w}}}[y_{\scriptscriptstyle
t}|\boldsymbol{x},\boldsymbol{y}_{<t}]=\prod\nolimits_{t}f_{[y_{\scriptscriptstyle
t}]}(\boldsymbol{x},\boldsymbol{y}_{<t};{\boldsymbol{w}}).$ (3)

By substituting (3) into (1) and (2), we _can_ effectively maximize or sample
$\mathbf{P}_{{\boldsymbol{w}}}$ using the neural network $f({\boldsymbol{w}})$
as we did in one-shot decision tasks. In particular, finding the MAP output
(over all possible sentences of a natural language) is a shortest-path problem
that can be solved by a backtracking search in realistic (yet costly) time, as
demonstrated by Stahlberg and Byrne (2019).

On the other hand, a seemly sub-optimal but economic choice is to simply
output a sequence $\boldsymbol{y}$ where each token $y_{\scriptscriptstyle t}$
is a greedy decision that _locally_ maximizes the token-wise probability given
the auto-regressive context:

$\boldsymbol{y}_{\text{greedy}}\doteq(y_{\scriptscriptstyle 1}\dots
y_{\scriptscriptstyle T})~{}~{}\text{where}~{}~{}y_{\scriptscriptstyle
t}=\arg\max_{a}~{}\mathbf{P}_{{\boldsymbol{w}}}[a|\boldsymbol{x},\boldsymbol{y}_{<t}]$
(4)

Comparing (1) and (4), we see that the MAP decision rule maximizes over the
combinatorial space of all possible sentences (= the output space), while the
greedy decision rule maximizes over the token space, which avoids the
combinatorial search at the cost of returning outputs with lower predicted
probability. It is thus expected that the MAP rule _should_ give higher
quality outputs than the greedy rule _if_ the model-predicted probability is a
good indicator of the true likelihood $\mathbf{P}_{\text{true}}$.

In practice, _beam search_ is a popular generalization of the greedy rule that
generates near-greedy outputs by making each decision step based on not a
single but a pool of auto-regressive contexts. With the capacity of the pool,
a.k.a. the _beam size_ , being $1$, beam search degenerates exactly to the
greedy rule (4). With the beam size tuned toward infinity, beam search will
eventually (but extremely slowly) cover the entire output space and will
return the MAP output (1) in the theoretical limit. It is thus expected that
the output quality of beam search should improve as beam size grows.

Moreover, the sampling rule (2) _should_ have reasonable performance _if_ the
neural network is well modeling the probabilities of a desired output (see
Appendix B). In other words, if sampling a probability model cannot give
reasonable outputs, it must be because the model is not well modeling the true
probabilities – in that case there is no reason to expect that picking the
greedy tokens would give something significantly better.

###  2.2 The Observations

Surprisingly, however, in a number of language generation tasks, the greedy
rule (4) and its close variants perform _much_ better than the more principled
decision rules (1) and (2). Figure 1 illustrates the issue in WMT’14 en2de,
with an experiment we designed to synthesize all the related counter-intuitive
observations together in a systematic and self-contained way. In this
experiment, a Transformer neural network with 60 millions parameters was
trained using the standard MLE loss (see Appendix G.1 for experiment setting
details). From Figure 1 we see that:

| BLEU | $\log_{10}\mathbf{P}_{{\boldsymbol{w}}}$
---|---|---
Empty output |  0.0 |  -4.3
Sampling rule (2) |  5.4 | -62.2
Greedy rule (4) | 25.6 |  -6.3
$|\text{beam}|=16$ (near-greedy) | 27.1 |  -5.6
$|\text{beam}|=1024$ (approx. MAP) |  8.6 |  -4.2
MAP rule (1) |  $\approx$ 2.1 222Stahlberg and Byrne (2019) reported BLEU$=2.1$ for the true MAP output on WMT’15 en2de. |  $>$ -4.2
Human’s output |  42.5 333See calculation method in Appendix G.1. | -18.4

Figure 1: MLE models exhibit paradoxical observations in WMT’14 en2de
Translation. The performance is measured by the standard BLEU metric in the
domain Papineni et al. (2002). $\log_{10}\mathbf{P}_{{\boldsymbol{w}}}$ gives
the order-of-magnitude of the probability as predicted by the trained model.

(1) Sampling the learned probability model $\mathbf{P}_{{\boldsymbol{w}}}$
gives bad outputs. Specifically, the performance of sampled output
(corresponding to “sampling” in Figure 1) is $5.4$ ($\pm$0.3 for $90\%$
confidence interval). As the baselines, human’s score is $42.5$, and the best
machine translation solution (“$|$beam$|$=16” in Figure 1) is $27.1$. The
performance of sampling the probability model is much closer to random
output’s ($\approx 0$), which is far from being a reasonable performance.

(2) The greedy rule gives good outputs, achieving a performance score of
$25.6$. While another $1.5$ score can be obtained by relaxing the greedy pick
to a few candidates each time (“$|$beam$|$=16” in Fig.1), the gap is rather
marginal. In general, it is fair to say that greedy outputs are nearly the
best, or that near-greedy outputs are the best.

(3) Seeking to maximize the predicted probability gives bad outputs: As we
continue to increase the beam size, we indeed find outputs with higher
probability according to the model (orange curve), but the actual translation
quality turns out to decrease (blue curve). With beam size $=1024$, the
performance has dropped to $8.6$. In fact, Stahlberg and Byrne (2019) reported
that the exact MAP output has a performance score as low as $2.1$ in a similar
WMT’15 task.

(4) The learned probability model $\mathbf{P}_{{\boldsymbol{w}}}$
significantly over-estimates some clearly bad outputs, while under-estimates,
again significantly, some clearly good outputs on the other hand.
Specifically, the model predicts a probability of around $1/10^{4}$ for the
empty translation which consists of nothing but an end-of-sequence token –
clearly such translation should never occur (and indeed the model never saw
any empty translation in the training data). 444 Probability over-estimation
is not limited to this particular output. It is a general trend that current
probability models over-estimate many very short and meaningless outputs Wu et
al. (2016); Murray and Chiang (2018).  On the other hand, the model assigns
_lower_ probability to the best-performing outputs (e.g.
$\mathbf{P}_{{\boldsymbol{w}}}[\boldsymbol{y}_{\text{greedy}}]\approx
1/10^{6}$ in Figure 1), and moreover, assigns _much lower_ probability to the
true expected outputs provided by human (with average predicted probability as
low as $1/10^{18}$).

The above observations are not limited to the particular task as demonstrated.
See Appendix G.2 and G.3 for similar results in WMT’17 zh2en translation and
in CNN-DM summarization, respectively. The pattern is the same across all
tasks: Both maximizing and sampling the learned probability model perform
poorly while going greedy or near-greedy with the “local probabilities”
performed dramatically well, and the learned model systematically assigns very
low probabilities to desired outputs while giving much higher probabilities to
undesired outputs.

These observations lead to a paradox if we insist the probabilistic
explanation: On one hand, we see strong reasons to reject the greedy rule –
for three tokens $A$, $B$, $C$, saying that “ _$AC$ is more likely than $BC$
because $P(A)>P(B)$_” (which is what the greedy rule is suggesting!) violates
basic principles of probability theory. On the other hand, we do observe that
the greedy rule works very well in reality, much better than decisions based
on $P(AC)$ and $P(BC)$.

###  2.3 Existing Explanations

The counter-intuitive observations above make one naturally wonder if the
learned neural networks are really supporting decision making _through_ good
probability modeling. Indeed, aspects of this problem have been called “ _beam
search curse_ ” Yang et al. (2018), “ _beam search bless_ ” Meister et al.
(2020), or “ _neural text degeneration_ ” Holtzman et al. (2019) – these names
may have suggested how paradoxical the community are feeling about the
problem. In the following we briefly mention some existing explanations in the
literature. See Appendix E for an extended discussion of related works.

Eikema and Aziz (2020) defended the probabilistic interpretation, arguing that
the MAP output is not a good decision rule at all for the selected task. We
however argue that tasks like translation fall in the category that MAP is
provably optimal _if_ the probability estimation is accurate (see Appendix A),
so inadequacy of MAP output can only be _caused_ by inaccuracy of probability
modeling.

Many works Ranzato et al. (2016); Zhang et al. (2019); Wu et al. (2016);
Stahlberg and Byrne (2019); Cohen and Beck (2019); Holtzman et al. (2019) seek
to find out why the learned model deviates from the groundtruth distribution.
Factors such as _exposure bias_ Wang and Sennrich (2020), _length bias_ Wu et
al. (2016), abnormal probability fluctuations Cohen and Beck (2019), and long-
tail errors Holtzman et al. (2019), are identified, with many heuristic
methods proposed to avoid the identified failure patterns. This line of works
however did not explain why (near-)greedy decisions _based on a model with so
many issues_ can somehow lead to good empirical result. Note that the
heuristics proposed in these works themselves have effectively made the
resulted solution deviating from the probability principles. It is still
unclear why we _have to_ violate well-established probability principles,
either in the form of greedy decision or by some sort of heuristic rules, to
obtain competitive performance from the learned “probability models”.

Meister et al. (2020) recently proposed to explain the effectiveness of greedy
output via a “uniform information density (UID)” hypothesis in cognitive
science. However, the precise mathematical expression of the UID hypothesis
itself is subject to different interpretations Meister et al. (2021). In
contrast, in this paper we propose a mathematically accurate and non-
probabilistic explanation.

##  3 A Duality View to MLE Training

We lay out a conceptual framework in this section which aims at resolving the
paradox as illustrated in Section 2 through a shift of mindset. Consider the
standard MLE training process for neural networks: We collect a data set
$\\{\boldsymbol{x}^{\scriptscriptstyle(i)},\boldsymbol{y}^{\scriptscriptstyle(i)}\\}_{i=1..n}$
with
$\boldsymbol{y}^{\scriptscriptstyle(i)}\sim\mathbf{P}_{\text{true}}[Y|X=\boldsymbol{x}^{\scriptscriptstyle(i)}]$,
then we update the model parameters ${\boldsymbol{w}}$ toward the ones that
maximize the (log-)probability of the data in $\mathbf{P}_{{\boldsymbol{w}}}$:

$\begin{split}{\boldsymbol{w}}_{\texttt{MLE}}&=\arg\max_{{\boldsymbol{w}}}~{}\log\mathbf{P}_{{\boldsymbol{w}}}[\\{\boldsymbol{y}^{\scriptscriptstyle(1..n)}\\}|\\{\boldsymbol{x}^{\scriptscriptstyle(1..n)}\\}]=\arg\max_{{\boldsymbol{w}}}~{}\sum_{i=1}^{n}\sum_{t=1}^{T_{i}}\log
f_{[y^{\scriptscriptstyle(i)}_{\scriptscriptstyle
t}]}(\boldsymbol{x}^{\scriptscriptstyle(i)},\boldsymbol{y}^{\scriptscriptstyle(i)}_{<t};{\boldsymbol{w}})\end{split}$
(5)

where the neural network $f$ models a softmax distribution

$f_{[y_{\scriptscriptstyle
t}]}(\boldsymbol{x},\boldsymbol{y}_{<t};{\boldsymbol{w}})=e^{Q_{[y_{\scriptscriptstyle
t}]}(\boldsymbol{x},\boldsymbol{y}_{<t};{\boldsymbol{w}})}/\sum\nolimits_{a}e^{Q_{[a]}(\boldsymbol{x},\boldsymbol{y}_{<t};{\boldsymbol{w}})}$
(6)

over the so-called _logit_ vector
$Q(\boldsymbol{x},\boldsymbol{y}_{<t};{\boldsymbol{w}})$. The training of
$f({\boldsymbol{w}})$ follows a learning dynamic driven by the gradient of the
MLE objective (5). 555 See Appendix C for how (5) corresponds _exactly_ to the
NLP practice in real world.  This gradient can be conveniently computed by
substituting (6) into (5), yielding

$\displaystyle\nabla_{{\boldsymbol{w}}}\log\mathbf{P}_{{\boldsymbol{w}}}[y_{\scriptscriptstyle
t}|\boldsymbol{x},\boldsymbol{y}_{<t}]=~{}$
$\displaystyle\nabla_{{\boldsymbol{w}}}Q_{[y_{\scriptscriptstyle
t}]}({\boldsymbol{w}})-\nabla_{{\boldsymbol{w}}}\text{LogSumExp}\Big{(}Q({\boldsymbol{w}})\Big{)}$
$\displaystyle=~{}$
$\displaystyle\nabla_{{\boldsymbol{w}}}Q_{[y_{\scriptscriptstyle
t}]}({\boldsymbol{w}})-\sum\nolimits_{a}~{}f_{[a]}({\boldsymbol{w}})~{}\nabla_{{\boldsymbol{w}}}Q_{[a]}({\boldsymbol{w}})$
(7)

where $\text{LogSumExp}(Q)\doteq\log\sum_{a}\exp(Q_{[a]})$, and we have
omitted $(\boldsymbol{x},\boldsymbol{y}_{<t})$ in $Q$’s and $f$’s argument for
brevity. (7) is a simple fact known by many, and is often utilized for the
purpose of computing the gradient of the log likelihood function.

We however argue that one can also understand (7) in the opposite direction.
Instead of viewing (7) as a method to implement a learning dynamic of
$\mathbf{P}_{{\boldsymbol{w}}}$ through manipulating $Q({{\boldsymbol{w}}})$,
we can reversely interpret it as a method to implement a learning dynamic of
$Q({{\boldsymbol{w}}})$ through manipulating $\mathbf{P}_{{\boldsymbol{w}}}$.
In this alternative perspective, we iterate the function $Q$ 666 In the new
perspective we shall perhaps not call $Q$ the “logits” any more, a name that
itself is suggesting that $Q$ is nothing but the logarithm of something else.
for its own sake, in the particular way as prescribed by the right-hand side
of (7). The left-hand side of (7) – as well as its connection to the MLE
objective (5) – is merely a human-imposed explanation about this Q-oriented
learning dynamic. More generally, the iteration of
$\mathbf{P}_{{\boldsymbol{w}}}$ and the iteration of $Q({{\boldsymbol{w}}})$
can be considered _dual process_ to each other that are taking place in
parallel, in a learning dynamic conventionally named “MLE training”.

While in principle one is free to choose either the P-iteration view or the
Q-iteration view, the former (i.e. the probabilistic interpretation) will
induce many conflicts with the empirical observations as shown in Section 2.
For this reason, we propose to explain the empirical behaviors of softmax-
normalized neural networks from the Q-iteration perspective, in which what the
neural network is expected to output are not probabilities, but are just the
un-normalized Q-values. The Q-function is trained with the RHS of (7) being
the update rule. At decision time, the well-performed greedy-to-P rule (4)
(which requires probabilistic interpretation) can be re-interpreted as a
greedy-to-Q rule:

$\boldsymbol{y}_{\text{greedy}}=(y_{\scriptscriptstyle 1\dots
T})~{}\text{,}~{}~{}y_{\scriptscriptstyle
t}=\arg\max_{a}~{}Q_{[a]}(\boldsymbol{x},\boldsymbol{y}_{<t};{\boldsymbol{w}})$
(8)

because the softmax transformation is order preserving.

Note that in above we are _not_ proposing a new algorithm, but were only
rephrasing the standard training and inference procedures in existing practice
(i.e. (5) and (4)) from another point of view. As the probabilistic semantic
is entirely discarded, all the probability-based assertions about the softmax
outputs become unexpected, thus the weak performance of probability-based
decision rules and the unreasonable probability predictions are not
paradoxical any more under the Q-iteration perspective. The only thing that
needs to be explained is _why_ the particular Q-iteration procedure (7) _can_
learn a good Q-function for greedy usage, which would be the main topic of the
next section.

Before turning to our account to the above question, we first remark that “
_learning unnormalized Q-functions in support of greedy decision making_ ” is
not a random problem we posed here just for fitting a particular experimental
result, but is a classic research topic that has been extensively studied in
reinforcement learning (RL) Watkins (1989); Mnih et al. (2015); Sutton and
Barto (2018). In RL literature, such a Q-function is also called an _action-
value_ function, or just _value function_ for short. Value functions support
decision making by assigning preferential scores to options so that optimal
ones can be identified, locally and greedily, without checking the long-term
consequence of the local decision. A value function is called an optimal
Q-function if the induced greedy decision policy (8) gives optimal outputs.

However, in existing RL literature, the concept of value has been mostly
limited to a particular type of _cardinal utility_ which corresponds to the
expected reward of a specific policy, and in RL the optimal Q-function is
typically learned via a _Bellman value iteration_ procedure. The manipulations
on the Q-function in the “MLE dynamic” (7) is clearly a very different
procedure. In fact, different from the typical RL setting where the learning
is driven by a reward signal, the dual process (7) of MLE optimization relies
on demonstrative samples of the expected output – in other words, it is an
_imitation learning_ procedure of Q-learning. The Q-function thus learned
represents an ordinal utility function that does not necessarily correspond to
some pre-defined reward; see Appendix D for more comparison and contrast
between the utility concept and the value concept in RL. Existing RL or
imitation learning literature thus cannot fully explain the utility-based
rationale behind this uncommon (but empirically effectively) procedure: If the
standard supervised MLE training of deep neural networks is actually learning
Q-functions, what is the “target” of this Q-learning dynamic? Is the learning
steered toward an _optimal_ Q-function? Can we explain this procedure, which
works well when (and to large extent, only when) coupled with the greedy
decision rule, without resorting back to the probability interpretation? We
seek to address these questions in the next section.

##  4 MLE Training as a Perturbed Dynamic of Optimal Utility Learning

Our general goal is to interpret the SGD dynamic of MLE training as an SGD
process of _some_ objective function of $Q$. There is however a technical
obstacle: If we look at (7), the gradient operator $\nabla_{{\boldsymbol{w}}}$
cannot be re-arranged to the head because of the $f_{[a]}({\boldsymbol{w}})$
term. As a result, it is not immediately clear that (7) is computing a
gradient of anything other than the log-likehood (which is the interpretation
we wanted to bypass here).

Nonetheless, let us temporarily do a “wrong” algebraic manipulation by moving
$\nabla_{{\boldsymbol{w}}}$ to the head of (7) anyway, making it
“approximately” the gradient of the following objective function:

$\displaystyle
J_{\text{MABE}}({\boldsymbol{w}},\boldsymbol{x},\boldsymbol{y})$
$\displaystyle\doteq\sum_{t=1}^{T}~{}\Big{(}~{}Q(y_{\scriptscriptstyle
t}|\boldsymbol{x},\boldsymbol{y}_{<t};{\boldsymbol{w}})-\sum\nolimits_{a}f(a|\boldsymbol{x},\boldsymbol{y}_{<t};{\boldsymbol{w}})Q(a|\boldsymbol{x},\boldsymbol{y}_{<t};{\boldsymbol{w}})~{}\Big{)}$
$\displaystyle=\sum_{t=1}^{T}~{}\Big{(}~{}Q(y_{\scriptscriptstyle
t}|\boldsymbol{x},\boldsymbol{y}_{<t};{\boldsymbol{w}})-\operatorname*{\mathbf{E}}_{\begin{subarray}{c}A_{t}\sim\mathbf{P}_{{\boldsymbol{w}}}\end{subarray}}~{}\Big{[}Q(A_{t}|\boldsymbol{x},\boldsymbol{y}_{<t};{\boldsymbol{w}})\Big{]}~{}\Big{)}$
(9)

Intuitively, $J_{\text{MABE}}$ measures the _advantage_ of outputting the
expected token $y_{t}$ over a stochastic output $A_{t}$ that follows the
softmax distribution induced by $Q$, where the advantage is the difference of
expected utilities between the two decisions (as predicted by $Q$, under
context $\boldsymbol{x},\boldsymbol{y}_{<t}$, for each step $t$). The
subscript MABE stands for Maximum Advantage over Boltzmann Exploration.

From (7) to (4), we have (naively) understood the log-likelihood gradient
$\nabla_{{\boldsymbol{w}}}\log\mathbf{P}_{{\boldsymbol{w}}}$ as an
approximation of $\nabla_{{\boldsymbol{w}}}J_{\text{MABE}}$, with the impact
of $\partial{\boldsymbol{w}}$ over $f({\boldsymbol{w}})$ being ignored. In
this sense, the MLE optimization can be seen as a _biased_ SGD dynamic of
$J_{\text{MABE}}$ optimization.

Interestingly, the log-likelihood gradient is not arbitrarily biased, but
there is a _precise_ connection between the gradients of the two functions
(see the proof in Appendix F.1):

######  Proposition 1.

Given input $\boldsymbol{x}$, output $\boldsymbol{y}=(y_{\scriptscriptstyle
1}\dots y_{\scriptscriptstyle T})$, and parametric model
$Q({\boldsymbol{w}})$, we have

$\begin{split}\frac{\partial\log\mathbf{P}_{{\boldsymbol{w}}}[\boldsymbol{y}|\boldsymbol{x}]}{\partial
w_{j}}=\frac{\partial J_{\text{MABE}}}{\partial
w_{j}}({\boldsymbol{w}},\boldsymbol{x},\boldsymbol{y})~{}+~{}\sum_{t=1}^{T}\mathbf{cov}_{t}\Big{[}Q,\frac{\partial
Q}{\partial w_{j}}\Big{]}\quad\quad,~{}~{}\forall j\end{split}$

where $\mathbf{cov}_{t}\Big{[}Q,\frac{\partial Q}{\partial
w_{j}}\Big{]}\doteq\underset{\scriptscriptstyle A_{t}\sim
P_{t}}{\mathbf{cov}}\Big{[}Q_{t}(A_{t})~{},~{}\frac{\partial Q_{t}}{\partial
w_{j}}(A_{t})\Big{]}$

$\displaystyle=~{}$
$\displaystyle\sum_{a}P_{t}(a)\cdot\Big{(}~{}Q_{t}(a)-\sum_{b}P_{t}(b)Q_{t}(b)~{}\Big{)}\cdot\Big{(}~{}\frac{\partial
Q_{t}}{\partial w_{j}}(a)-\sum_{b}P_{t}(b)\frac{\partial Q_{t}}{\partial
w_{j}}(b)~{}\Big{)}$ (10)

  * $\bullet$

$\mathbf{P}_{{\boldsymbol{w}}}$ is the softmax distribution induced by
$Q({\boldsymbol{w}})$ as prescribed by (3) and (6),

  * $\bullet$

$P_{t}(a)$ denotes
$\mathbf{P}_{{\boldsymbol{w}}}[a|\boldsymbol{x},\boldsymbol{y}_{<t}]$, the
probability that the token at step $t$ is $a$, according to
$\mathbf{P}_{{\boldsymbol{w}}}$,

  * $\bullet$

$Q_{t}(a)$ denotes $Q(a|\boldsymbol{x},\boldsymbol{y}_{<t};{\boldsymbol{w}})$,
the utility of outputting token $a$ at step $t$, according to
$Q({\boldsymbol{w}})$,

  * $\bullet$

$\frac{\partial Q_{t}}{\partial w_{j}}(a)$ denote $\frac{\partial Q}{\partial
w_{j}}(a|\boldsymbol{x},\boldsymbol{y}_{<t};{\boldsymbol{w}})$, the partial
derivative of $Q(a|\boldsymbol{x},\boldsymbol{y}_{<t};{\boldsymbol{w}})$ at
step $t$,

Intuitively, the $\mathbf{cov}_{t}$ term in (10) is the covariance between
$Q(A_{t})$ and its derivative when $A_{t}$ follows the Boltzmann exploration
policy $\mathbf{P}_{{\boldsymbol{w}}}$. Proposition 1 asserts that the
gradient of the probability-learning objective (5) differs from the gradient
of the utility-learning objective (4) by exactly this covariance (or by the
cumulative covariance in sequential decision setting). For complex models with
millions or billions of parameters, if the model output is not strongly
correlated to the partial derivative of a single parameter, the covariance
term identified in Proposition 1 would have limited impact on the learning
progress. As a key result, we empirically found that this is indeed true: in
all the tasks we have experimented, the perturbation from this covariance term
cannot significantly affect the learning, not only for the final performance,
but also throughout the entire learning dynamic.

Specifically, consider a MABE($\lambda$) family of Q-learning algorithms as
defined by Algorithm 1. MABE(0) optimizes $J_{\text{MABE}}$ based on unbiased
estimator of $\nabla J_{\text{MABE}}$. MABE(1) adds the covariance term to the
gradient estimator, thus is equivalent to traditional MLE training. For other
$\lambda$, MABE($\lambda$) does not seem to have principled interpretations,
but is simply constructed by perturbing the gradient estimator with a
$\lambda$ multiple of the covariance, where $\lambda$ can be either positive
or negative. By tuning $\lambda$ to different values, we can control how
significantly the gradient is perturbed.

Algorithm 1 The MABE($\lambda$) algorithm.

Input: A supervised training data $\mathcal{D}$; a Q-model
$Q({\boldsymbol{w}})$ with $|{\boldsymbol{w}}|=d$; perturbation coefficient
$\lambda$.

for SGD step $k=0,1,2,\dots$ do

obtain a minibatch
$\\{\boldsymbol{x}^{\scriptscriptstyle(i)},\boldsymbol{y}^{\scriptscriptstyle(i)}\\}_{i=1}^{B}$
from $\mathcal{D}$

set $\Delta\leftarrow\frac{1}{B}\sum_{i=1}^{B}\Delta^{\scriptscriptstyle(i)}$,
where

$\Delta^{\scriptscriptstyle(i)}=\nabla
J_{\text{MABE}}({\boldsymbol{w}},\boldsymbol{x}^{\scriptscriptstyle(i)},\boldsymbol{y}^{\scriptscriptstyle(i)})+\lambda~{}\mathbf{cov}^{\scriptscriptstyle(i)}\Big{|}_{{\boldsymbol{w}}={\boldsymbol{w}}^{k}}$
and
$\mathbf{cov}^{\scriptscriptstyle(i)}=\Big{<}\sum_{t=1}^{T_{i}}\mathbf{cov}_{t}\Big{[}Q,\frac{\partial
Q}{\partial w_{j}}\Big{]}\Big{>}_{j=1..d}$

update ${\boldsymbol{w}}$ using $-\Delta$ as the gradient estimator

end for

Output: $\arg\max Q({\boldsymbol{w}}^{k})$ as the decision rule.

(a) WMT’14 (English$\rightarrow$German)

(b) WMT’17 (Chinese$\rightarrow$English)

(c) CNN/DailyMail Summarization

Figure 2: SGD dynamic of $J_{\text{MABE}}$ when the gradient is perturbed by
the covariance term (10). Performance of the Q-greedy decision rule is
evaluated on the test set every $5000$ SGD steps. BLEU and ROUGE are standard
metrics for corresponding tasks.

Figure 2 shows the learning curves of MABE($\lambda$) under five values of
$\lambda$, ranging from $-2$ to $2$. Generally speaking, all the learning
curves are similar, in all the three tasks being examined, not only in the end
but almost throughout the training process. Performance of the perturbed
variant MABE(1), a.k.a. MLE training, is slightly lower than the unperturbed
variant MABE(0) (see Fig. 7, 10, 13 in the appendix for the numerical scores).
The learning under $\lambda=2$ (which is 2x perturbed) was somewhat slower at
the beginning, but managed to catch up with other variants in later stage of
the learning. Importantly, MABE(1) – a.k.a. the SGD-based MLE training of
softmax-normalized neural networks – does not seem to be anything uniquely
different from the other “non-probabilistic” variants in the MABE($\lambda$)
family. Under the greedy decision rule, its performance is generally similar
to (often slightly lower than) that of the unperturbed variant MABE(0).

So far we have re-interpreted a classic statistical learning procedure (i.e.
SGD-based MLE) as a kind of Q-learning algorithm (i.e. MABE($\lambda$)). Now
we investigate the optimality of this Q-learning algorithm. Given that the
performance of MABE($\lambda$) is similar under modest perturbation
coefficient $\lambda$, in the following we focus on analyzing MABE(0), the
learning dynamic without any perturbation. In the following we prove that when
the Q-model is expressive enough, the global maximum of $J_{\text{MABE}}$ is
indeed an optimal Q-function (See the proof in Appendix F.2).

######  Theorem 2.

Consider a tabular model
$Q(a;\boldsymbol{q})=\sum_{j=1}^{d}\mathds{1}[a=j]\cdot q_{j}$, where the
parameter vector $\boldsymbol{q}=(q_{1}\dots q_{d})$ directly encodes the
utilities for each possible action $a\in\\{1\dots d\\}$. Let
$\boldsymbol{p}=(p_{1}\dots p_{d})$ be the softmax distribution induced by
$\boldsymbol{q}$. Let $\boldsymbol{q}^{*}$ be the Q-values that maximizes
$J(\boldsymbol{q})=\operatorname*{\mathbf{E}}_{\begin{subarray}{c}Y\sim\mathbf{P}_{\text{true}}\end{subarray}}~{}\Big{[}Q(Y;\boldsymbol{q})\Big{]}-\operatorname*{\mathbf{E}}_{\begin{subarray}{c}A\sim\boldsymbol{p}\end{subarray}}~{}\Big{[}Q(A;\boldsymbol{q})\Big{]}$,
and $\boldsymbol{p}^{*}$ the softmax distribution by $\boldsymbol{q}^{*}$,
then

$\max_{a\in\mathrm{supp}(Y)}~{}q^{*}_{a}~{}~{}>~{}~{}\max_{b\not\in\mathrm{supp}(Y)}~{}q^{*}_{b}~{}~{}+~{}~{}1$
(11)

where $\mathrm{supp}(Y)$ is the support of $\mathbf{P}_{\text{true}}$ (which
is thus the set of all desired actions), and moreover,

$p^{*}_{a}\cdot(~{}1+q^{*}_{a}-\mathbf{E}_{\boldsymbol{p}^{*}}[Q]~{})~{}~{}=~{}~{}\mathbf{P}_{\text{true}}[Y=a]\quad\quad,~{}~{}\forall
a$ (12)

The function $J$ in Theorem 2 is an idealized form of the MABE objective
$J_{\text{MABE}}$, with the loss of parameterization in $Q({\boldsymbol{w}})$
being ignored. The inequality (11) in Theorem 2 suggests that
$\boldsymbol{q}^{*}$, the global maximum of $J$, separates desired actions
from undesired ones by at least a constant margin, so going greedy with
$\boldsymbol{q}^{*}$ can provably avoid undesired actions. This fact
established a strict optimality property for the global maximum of
$J_{\text{MABE}}$: Maximizing $J_{\text{MABE}}$ over ${\boldsymbol{w}}$
guarantees to find the _optimal_ Q-function 777 Recall that a Q-function is
optimal if the greedy policy (8) finds optimal decisions (see Section 3).  as
long as the global maximum of $J_{\text{MABE}}$ is covered by the parametric
model $Q({\boldsymbol{w}})$.

As MABE(0) is just a standard stochastic gradient process of $J_{\text{MABE}}$
optimization, this optimality result (which is subject to model errors, data
errors, and optimization errors) supports the soundness of the MABE family of
Q-learning algorithms to the same strength as how the SGD-based MLE procedure
has been justified in the probabilistic explanation of deep learning. In this
way, we subsumed the SGD dynamic of MLE as a perturbed variant of a learning
dynamic towards optimal Q-function (where the perturbation does not
significantly affect the learning dynamic).

Table 1: Dual probabilities significantly improve pure sampling and MAP ($\pm$
gives $90\%$ confidence interval from $9$ trials).

|  WMT’14 en$\rightarrow$de |  WMT’17 zh$\rightarrow$en | CNN / DailyMail
---|---|---|---
| sampling | $|\text{beam}|=1024$ | sampling | $|\text{beam}|=1024$ | sampling | $|\text{beam}|=1024$
Softmax Probability |  5.4 $\pm$0.3 | 8.6 |  8.3 $\pm$0.2 | 11.9 |  21.1 $\pm$0.1 | 20.1
Dual Probability |  20.0 $\pm$0.2 | 25.9 |  17.7 $\pm$0.1 | 21.1 |  27.9 $\pm$0.1 | 27.1
| (+14.6) | (+ 17.3) | (+ 9.4) | (+ 9.2) | (+ 6.8) | (+ 7.1)

##  5 The Dual Probabilities

In above we have been arguing that the empirical effectiveness of standard
deep learning procedures can be better explained without interpreting the
neural networks as probability models. In some cases, however, people may just
want to have a probability model Papamakarios et al. (2017). Interestingly,
our non-probabilistic theory entails a way to bring back the probabilistic
semantic by transforming the learned Q-values (back) to probability
estimations.

Specifically, (12) in Theorem 2 gives a precise relationship between the
Q-value of an action and the _true_ probability that the action is an desired
one. The equation holds at the global maximum $\boldsymbol{q}^{*}$ of
$J_{\text{MABE}}$. In practice, the optimization is never exact for modern
neural networks , yet we can still use the equation as a guidance to transform
the Q-values obtained from MABE optimization to an approximation of the
probabilities $\mathbf{P}_{\text{true}}$. Specifically, let vector
$\boldsymbol{q}=(q_{1}\dots q_{d})$ be the Q-values predicted by a Q-function
for a given decision context, define

$p^{\text{dual}}_{i}~{}=~{}\text{CLIP}\Big{(}~{}p_{i}~{}(1+q_{i}-\boldsymbol{p}\cdot\boldsymbol{q})~{}\Big{)}~{}/~{}Z$
(13)

where $p_{i}=\text{softmax}_{[i]}(\boldsymbol{q})$,
$\text{CLIP}(x)\doteq\min(\max(0,x),1)$ trims the predictions to $[0,1]$, and
$Z$ is the sum of the numerator in (13) across all $i$. The clipping and
$Z$-normalization in (13) are not needed if $\boldsymbol{q}$ is exactly
optimized.

We call the probability predictions by (13), the _dual probabilities_ of the
Q-values. Note that the dual probabilities $p^{\text{dual}}$ are different
from the predictions computed directly from the softmax transformation (which
gives $\boldsymbol{p}$); the former “calibrates” the latter with a scaling
factor $1+q_{i}+\boldsymbol{p}\cdot\boldsymbol{q}$.

Empirically, we found that the dual probabilities (13) perform much better
than the commonly used softmax probabilities, when both are used in
probability-compatible decision rules, as Table 2 shows (also see Appendix
G.1, G.2 and G.3).

Taking WMT’14 en2de as example, translations by sampling the dual
probabilities attain a BLEU score of $20.0$, which is a gain of $+14.6$ (or
$+370\%$) over sampling with the traditional softmax probabilities (cf. Figure
1). The dual probability makes pure probability sampling a much more
competitive decision rule now. Similarly, the dual probabilities also
drastically improve the real-world performance of (approximate) probability
maximization. For search with beam size $=1024$, for example, its BLEU score
in WMT’14 en2de is lifted from $8.6$ to $25.9$, a gain of $+17.3$, and the
score is higher than greedy’s. Moreover, the dual probability of the empty
output is now strictly zero on $2736$ of the $2737$ testing instances. In
fact, the raw scaling factor $1+q_{i}-\boldsymbol{p}\cdot\boldsymbol{q}$ of
the end-of-seq token was negative (thus was clipped to $0$) in all but one
instances. It is only a pity that the model will also assign zero probability
for most of the reference translations ($2614$ out of $2737$, which is less
than the number for empty outputs though). On the other hand, the dual
probability model is much more confident for self-generated outputs; see
Figure 6 in Appendix G.1.

Similar gains in probability prediction and utilization can be observed in all
tasks we examined. See Appendix G.1, G.2 and G.3 for more details. Overall,
dual probability models exhibit much more reasonable behaviors than
traditional softmax probability models.

Importantly, the dual probability formula (13) does not use any
hyperparameter, and is derived from first principles. Recall that in Section 3
we proposed to think of the Q-learning dynamic of (7) as a dual process that
simultaneously optimizes the Q-values _and_ the softmax probabilities. But
now, in light of the advantage of the dual probabilities as observed in this
section, it seems that the probability given by (13) is a more accurate
probability model. As a result, if we say that the neural network is
representing both utility and probability, the probability counterpart seems
to be better represented by the probability given in (13), instead of by the
commonly recognized softmax probability.

##  6 Conclusions

To summarize, we have demonstrated how the current practice of neural networks
contradicts with its canonical probabilistic explanation in some complex
decision tasks. This motivated us to develop an alternative explanation, in
which the classic SGD-based MLE optimization process of softmax-normalized
neural networks is interpreted as a supervised Q-learning algorithm (MABE(1)).
Our utility-based theory is inherently free of the paradoxical probabilistic
semantics, and yet can induce a dual probability space when needed, with
significantly improved performance.

Based on results in this paper, one can either say that the neural network
trained from “SGD-based MLE optimization” is modeling a utility function,
whose theoretical optimality is characterized by Theorem 2, or, one could also
say that the neural network is indeed modeling a probability space, of not the
softmax probability (6), but of the dual probability (13).

Although this duality phenomenon may best manifest itself in sequential
decision tasks,888In one-shot classification tasks, the MAP rule (1)
degenerates to the greedy rule (4), thus many problems observed in this paper
will not show up, except that the inaccuracy of softmax probability
estimations can still be observed Guo et al. (2017). we believe the conceptual
implications of our duality theory may apply to all deep learning tasks
because the probability interpretation of neural networks has been framed as a
unified logical framework for all learning tasks. Our results challenged this
mindset, and our theory provides a better unified framework to reason about
deep neural networks.

## Acknowledgments

Authors of this paper would like to thank Rui Ding, Jingjing Xu, Shion
Ishikawa, Liang Li, and Lihua Wang for giving many helpful comments on
previous versions of this paper.

## References

  * Akbareian [2015] Emma Akbareian.  The blue and black (or white and gold) dress: Actual colour, brand, and price details revealed.  _The Independent_ , 2015.
  * Bishop [2006] Christopher M Bishop.  Pattern recognition and machine learning.  2006\.
  * Bojun [2022] Huang Bojun.  Lagrangian method for q-function learning (with applications to machine translation).  In _Proceedings of the 39th International Conference on Machine Learning_ , volume 162 of _Proceedings of Machine Learning Research_ , pages 2129–2159, 17–23 Jul 2022.
  * Cohen and Beck [2019] Eldan Cohen and Christopher Beck.  Empirical analysis of beam search performance degradation in neural sequence models.  In _International Conference on Machine Learning_ , pages 1290–1299. PMLR, 2019.
  * Eikema and Aziz [2020] Bryan Eikema and Wilker Aziz.  Is map decoding all you need? the inadequacy of the mode in neural machine translation.  In _Proceedings of the 28th International Conference on Computational Linguistics_ , pages 4506–4520, 2020.
  * Fishburn [1990] Peter C Fishburn.  Utility theory and decision theory.  _Utility and Probability_ , pages 303–312, 1990.
  * Garg et al. [2021] Divyansh Garg, Shuvam Chakraborty, Chris Cundy, Jiaming Song, and Stefano Ermon.  Iq-learn: Inverse soft-q learning for imitation.  _Advances in Neural Information Processing Systems_ , 34, 2021.
  * Goodfellow et al. [2016] Ian Goodfellow, Yoshua Bengio, and Aaron Courville.  _Deep Learning_.  MIT Press, 2016.
  * Guo et al. [2017] Chuan Guo, Geoff Pleiss, Yu Sun, and Kilian Q Weinberger.  On calibration of modern neural networks.  In _International Conference on Machine Learning_ , pages 1321–1330. PMLR, 2017.
  * Hassan et al. [2018] Hany Hassan, Anthony Aue, Chang Chen, Vishal Chowdhary, Jonathan Clark, Christian Federmann, Xuedong Huang, Marcin Junczys-Dowmunt, William Lewis, Mu Li, et al.  Achieving human parity on automatic chinese to english news translation.  _arXiv preprint arXiv:1803.05567_ , 2018.
  * Holtzman et al. [2019] Ari Holtzman, Jan Buys, Li Du, Maxwell Forbes, and Yejin Choi.  The curious case of neural text degeneration.  In _International Conference on Learning Representations_ , 2019.
  * Koehn and Knowles [2017] Philipp Koehn and Rebecca Knowles.  Six challenges for neural machine translation.  In _Proceedings of the First Workshop on Neural Machine Translation_ , pages 28–39, 2017.
  * Lafer-Sousa et al. [2015] Rosa Lafer-Sousa, Katherine L Hermann, and Bevil R Conway.  Striking individual differences in color perception uncovered by ‘the dress’ photograph.  _Current Biology_ , 25(13):R545–R546, 2015.
  * Lan et al. [2020] Qingfeng Lan, Yangchen Pan, Alona Fyshe, and Martha White.  Maxmin q-learning: Controlling the estimation bias of q-learning.  In _International Conference on Learning Representations_ , 2020.
  * Lewis et al. [2020] Mike Lewis, Yinhan Liu, Naman Goyal, Marjan Ghazvininejad, Abdelrahman Mohamed, Omer Levy, Veselin Stoyanov, and Luke Zettlemoyer.  Bart: Denoising sequence-to-sequence pre-training for natural language generation, translation, and comprehension.  In _Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics_ , pages 7871–7880, 2020.
  * Lillicrap et al. [2015] Timothy P Lillicrap, Jonathan J Hunt, Alexander Pritzel, Nicolas Heess, Tom Erez, Yuval Tassa, David Silver, and Daan Wierstra.  Continuous control with deep reinforcement learning.  _arXiv preprint arXiv:1509.02971_ , 2015.
  * Lin [2004] Chin-Yew Lin.  ROUGE: A package for automatic evaluation of summaries.  In _Text Summarization Branches Out_ , pages 74–81, Barcelona, Spain, July 2004. Association for Computational Linguistics.
  * Meister et al. [2020] Clara Meister, Ryan Cotterell, and Tim Vieira.  If beam search is the answer, what was the question?  In _Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP)_ , pages 2173–2185, 2020.
  * Meister et al. [2021] Clara Meister, Tiago Pimentel, Patrick Haller, Lena Jäger, Ryan Cotterell, and Roger Levy.  Revisiting the Uniform Information Density hypothesis.  In _Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing_ , pages 963–980, Online and Punta Cana, Dominican Republic, November 2021. Association for Computational Linguistics.  doi: 10.18653/v1/2021.emnlp-main.74.  URL https://aclanthology.org/2021.emnlp-main.74.
  * Minderer et al. [2021] Matthias Minderer, Josip Djolonga, Rob Romijnders, Frances Hubis, Xiaohua Zhai, Neil Houlsby, Dustin Tran, and Mario Lucic.  Revisiting the calibration of modern neural networks.  _Advances in Neural Information Processing Systems_ , 34, 2021.
  * Mnih et al. [2015] Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A Rusu, Joel Veness, Marc G Bellemare, Alex Graves, Martin Riedmiller, Andreas K Fidjeland, Georg Ostrovski, et al.  Human-level control through deep reinforcement learning.  _Nature_ , 518(7540):529–533, 2015.
  * Moscati [2018] Ivan Moscati.  _Measuring utility: From the marginal revolution to behavioral economics_.  Oxford Studies in History of E, 2018.
  * Murray and Chiang [2018] Kenton Murray and David Chiang.  Correcting length bias in neural machine translation.  In _Proceedings of the Third Conference on Machine Translation: Research Papers_ , pages 212–223, 2018.
  * Osa et al. [2018] Takayuki Osa, Joni Pajarinen, and Gerhard Neumann.  _An Algorithmic Perspective on Imitation Learning_.  Now Publishers Inc., 2018.  ISBN 168083410X.
  * Ott et al. [2018] Myle Ott, Michael Auli, David Grangier, and Marc’Aurelio Ranzato.  Analyzing uncertainty in neural machine translation.  In _International Conference on Machine Learning_ , 2018.
  * Papamakarios et al. [2017] George Papamakarios, Theo Pavlakou, and Iain Murray.  Masked autoregressive flow for density estimation.  In I. Guyon, U. Von Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, editors, _Advances in Neural Information Processing Systems_ , volume 30, 2017.
  * Papineni et al. [2002] Kishore Papineni, Salim Roukos, Todd Ward, and Wei-Jing Zhu.  Bleu: a method for automatic evaluation of machine translation.  In _Proceedings of the 40th annual meeting of the Association for Computational Linguistics_ , pages 311–318, 2002.
  * Post [2018] Matt Post.  A call for clarity in reporting bleu scores.  In _Proceedings of the Third Conference on Machine Translation (WMT)_ , pages 186–191, 2018.
  * Ranzato et al. [2016] Marc’Aurelio Ranzato, Sumit Chopra, Michael Auli, and Wojciech Zaremba.  Sequence level training with recurrent neural networks.  In _International Conference on Learning Representations_ , 2016.
  * Rei et al. [2020] Ricardo Rei, Craig Stewart, Ana C Farinha, and Alon Lavie.  COMET: A neural framework for MT evaluation.  In _Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP)_ , pages 2685–2702, November 2020.
  * See et al. [2017] Abigail See, Peter J Liu, and Christopher D Manning.  Get to the point: Summarization with pointer-generator networks.  In _Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pages 1073–1083, 2017\.
  * Sennrich et al. [2016] Rico Sennrich, Barry Haddow, and Alexandra Birch.  Neural machine translation of rare words with subword units.  In _Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pages 1715–1725, 2016\.
  * Stahlberg and Byrne [2019] Felix Stahlberg and Bill Byrne.  On nmt search errors and model errors: Cat got your tongue?  In _Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP)_ , pages 3347–3353, 2019.
  * Sutton and Barto [2018] Richard S Sutton and Andrew G Barto.  _Reinforcement learning: An introduction_.  MIT press, 2018.
  * Vaswani et al. [2017] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, L ukasz Kaiser, and Illia Polosukhin.  Attention is all you need.  In _Proceedings of the 31st International Conference on Neural Information Processing Systems_ , pages 6000–6010, 2017.
  * Wang and Sennrich [2020] Chaojun Wang and Rico Sennrich.  On exposure bias, hallucination and domain shift in neural machine translation.  In _Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics_ , pages 3544–3552, 2020.
  * Watkins [1989] CJCH Watkins.  Learning from delayed rewards.  _PhD thesis, King’s College, University of Cambridge_ , 1989.
  * Wu et al. [2016] Yonghui Wu, Mike Schuster, Zhifeng Chen, Quoc V. Le, Mohammad Norouzi, Wolfgang Macherey, Maxim Krikun, Yuan Cao, Qin Gao, Klaus Macherey, Jeff Klingner, Apurva Shah, Melvin Johnson, Xiaobing Liu, L ukasz Kaiser, Stephan Gouws, Yoshikiyo Kato, Taku Kudo, Hideto Kazawa, Keith Stevens, George Kurian, Nishant Patil, Wei Wang, Cliff Young, Jason Smith, Jason Riesa, Alex Rudnick, Oriol Vinyals, Greg Corrado, Macduff Hughes, and Jeffrey Dean.  Google’s neural machine translation system: Bridging the gap between human and machine translation.  _CoRR_ , abs/1609.08144, 2016.  URL http://arxiv.org/abs/1609.08144.
  * Yang et al. [2018] Yilin Yang, Liang Huang, and Mingbo Ma.  Breaking the beam search curse: A study of (re-)scoring methods and stopping criteria for neural machine translation.  In _Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing_ , pages 3054–3059, October-November 2018.
  * Zhang et al. [2019] Wen Zhang, Yang Feng, Fandong Meng, Di You, and Qun Liu.  Bridging the gap between training and inference for neural machine translation.  In _Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics_ , pages 4334–4343, 2019.
  * Zhao et al. [2009] Hongmei Zhao, Jun Xie, Qun Liu, Yajuan Lü, Dongdong Zhang, and Mu Li.  Introduction to china’s cwmt2008 machine translation evaluation.  In _Proceedings of Machine Translation Summit XII: Papers_ , 2009\.

##  Appendix A On the Optimality of Probability Maximization

The Maximum-A-Posteriori principle is very intuitive in the sense that, given
an input, if we have to make one and _only one_ output, then selecting the one
that we think is most likely to be the expected output $Y$ is a quite natural
idea. For a number of common performance metrics, this intuition is indeed
formally supported by the provable optimality of maximizing the true
probability $\mathbf{P}_{\text{true}}$.

Specifically, given a decision task with expected input $X$ and expected
output $Y$, suppose the goal is to determine the actual output $A$ so as to
maximize an _expected utility_

$\mathbf{E}_{X,A}[U(X,A)]=\sum_{\boldsymbol{x}}\mathbf{P}(\boldsymbol{x})\sum_{\boldsymbol{a}}\mathbf{P}({\boldsymbol{a}}|\boldsymbol{x})~{}U(\boldsymbol{x},{\boldsymbol{a}})$
(14)

where

$U(\boldsymbol{x},{\boldsymbol{a}})=\sum_{\boldsymbol{y}}\mathbf{P}_{\text{true}}(\boldsymbol{y}|\boldsymbol{x})~{}\delta({\boldsymbol{a}},\boldsymbol{y})$
(15)

and $\delta({\boldsymbol{a}},\boldsymbol{y})$ is a similarity score between
output ${\boldsymbol{a}}$ and output $\boldsymbol{y}$.

Case 1: Suppose $\delta$ is a binary score that simply measures if the actual
output $A$ has correctly predicted $Y$ or not; that is, suppose
$U({\boldsymbol{a}},\boldsymbol{y})=\mathds{1}[{\boldsymbol{a}}=\boldsymbol{y}]$.
In this case the expected utility corresponds to the commonly used _prediction
accuracy_ , and we have
$U(\boldsymbol{x},{\boldsymbol{a}})=\sum_{\boldsymbol{y}}\mathbf{P}_{\text{true}}(\boldsymbol{y}|\boldsymbol{x})~{}\mathds{1}[{\boldsymbol{a}}=\boldsymbol{y}]=\mathbf{P}_{\text{true}}({\boldsymbol{a}}|\boldsymbol{x})$,
so maximizing the probability
$\mathbf{P}_{\text{true}}({\boldsymbol{a}}|\boldsymbol{x})$ is equivalent to
maximizing the utility $U(\boldsymbol{x},{\boldsymbol{a}})$, given the input
$\boldsymbol{x}$.

Case 2: Suppose for any given $\boldsymbol{x}$, the expected output $Y$ is
deterministic, denoted by $\boldsymbol{y}_{\boldsymbol{x}}$. Equivalently, we
are assuming that there exists a _unique groundtruth_ behind each observation;
for example, given a picture $\boldsymbol{x}$, the object in that picture is
always, say, a dog, no matter when or how many times the picture is observed.
In this case, the distribution $\mathbf{P}_{\text{true}}$ degenerates and has
$\mathbf{P}_{\text{true}}(\boldsymbol{y}_{\boldsymbol{x}}|\boldsymbol{x})=1$,
so we have
$U(\boldsymbol{x},{\boldsymbol{a}})=\sum_{\boldsymbol{y}}\mathbf{P}_{\text{true}}(\boldsymbol{y}|\boldsymbol{x})~{}\delta({\boldsymbol{a}},\boldsymbol{y})=\delta({\boldsymbol{a}},\boldsymbol{y}_{\boldsymbol{x}})$.
Now as long as $\delta$ is a similarity score, it is necessary that for any
${\boldsymbol{a}}$,
$\delta({\boldsymbol{a}},\boldsymbol{y}_{\boldsymbol{x}})\leq\delta(\boldsymbol{y}_{\boldsymbol{x}},\boldsymbol{y}_{\boldsymbol{x}})$
(i.e. $\boldsymbol{y}_{\boldsymbol{x}}$ is the one that is most similar to
itself); in other words, the utility function
$U(\boldsymbol{x},{\boldsymbol{a}})=\delta({\boldsymbol{a}},\boldsymbol{y}_{\boldsymbol{x}})$
attains its maximum at ${\boldsymbol{a}}=\boldsymbol{y}_{\boldsymbol{x}}$. On
the other hand, as $\mathbf{P}_{\text{true}}({\boldsymbol{a}}|\boldsymbol{x})$
also attains its maximum at ${\boldsymbol{a}}=\boldsymbol{y}_{\boldsymbol{x}}$
(because
$\mathbf{P}_{\text{true}}(\boldsymbol{y}_{\boldsymbol{x}}|\boldsymbol{x})=1$),
maximizing $\mathbf{P}_{\text{true}}({\boldsymbol{a}})$ is again equivalent to
maximize $U(\boldsymbol{x},{\boldsymbol{a}})$ in this case (that is, when $Y$
is deterministic conditioned on $X$ and $\delta$ is a similarity score).

Case 3: In reality, the determinism assumption in Case 2 can be slightly
relaxed, to the situation that the expected output $Y$ is not deterministic,
but all the possible “utterances” of $Y$ has the same equivalent “meaning”
(and that $\delta$ is a measure of _semantic similarity_). For example, it is
very common that given a question (e.g. “what does the following English
sentence mean in German?”), there is a definite answer at the semantic level,
but this answer may admit multiple different yet equivalent expressions in
natural language. In this case, there is still a unique groundtruth at the
semantic level, and it is reasonable to say that an answer $A$ to the question
should be judged affirmatively as long as it matches _any_ equivalent
utterance of this unique groundtruth.

It can be proved that for Case 3, delivering the “most likely” output
$\boldsymbol{y}_{\texttt{MAP}}$ is still optimal, for a similar reason as in
Case 2. Specifically, given input $\boldsymbol{x}$, let $\mathrm{supp}(Y)$ be
the support of the distribution $\mathbf{P}_{\text{true}}$ conditioned on
$\boldsymbol{x}$. Suppose we replace the average-form utility (15) to a
function that measures how similar the actual output ${\boldsymbol{a}}$ is
with _any_ expected output $\boldsymbol{y}\in\mathrm{supp}(Y)$, that is,

$U(\boldsymbol{x},{\boldsymbol{a}})=\max_{\boldsymbol{y}\in\mathrm{supp}(Y)}~{}\delta({\boldsymbol{a}},\boldsymbol{y})\quad\text{,
where }~{}Y\sim\mathbf{P}_{\text{true}}(\cdot|\boldsymbol{x}).$ (16)

(16) entails that $U(\boldsymbol{x},{\boldsymbol{a}})$ would attain its
maximum at any ${\boldsymbol{a}}\in\mathrm{supp}(Y)$. This means the maximum
point of $\mathbf{P}_{\text{true}}$, which must be within the support of
$\mathbf{P}_{\text{true}}$ (i.e. within $\mathrm{supp}(Y)$), is necessarily a
maximum point of the $U(\boldsymbol{x},{\boldsymbol{a}})$ in (16) too. Note
that the similarity measure $\delta$ in (16) is general and needs not to be
binary.

In summary, from above we see that maximizing the _true_ probability of $Y$ –
suppose we could do it – is guaranteed to be exactly optimal either if the
instance-wise utility is binary (Case 1), or if the groundtruth is unique
(Case 2) or “essentially unique” (Case 3). As these conditions are quite
common in practice, the optimality helps justify the widely-held conceptual
reduction from optimal decision to probability estimation, and also underlie
the widely-adopted decision rule of maximum a-posteriori which replaces the
true probability $\mathbf{P}_{\text{true}}$ with the estimated a-posteriori
probability $\mathbf{P}_{{\boldsymbol{w}}}$, with the hope that
$\mathbf{P}_{{\boldsymbol{w}}}$, as a “close” approximation of
$\mathbf{P}_{\text{true}}$, can still achieve “good” performance.

##  Appendix B On the Soundness of Probability Sampling

A probability model that specifies the distribution of the _actual_ output
conditioned on given input is usually called a _decision policy_ in machine
learning literature (particularly in reinforcement learning literature) Sutton
and Barto [2018]. As a special case, a deterministic policy maps each input to
a definite output, and is also called a _discriminant function_ in statistics
and statistical learning literature Bishop [2006]. The probability sampling
rule (2) asks the decision making agent to generate the actual output $A$ by
sampling a learned distribution $\mathbf{P}_{{\boldsymbol{w}}}$ of the
expected output $Y$. In other words, $\mathbf{P}_{{\boldsymbol{w}}}$ is used
as a decision policy under the sampling rule.

When $\mathbf{P}_{{\boldsymbol{w}}}=\mathbf{P}_{\text{true}}$, the actual
output $A$ sampled from policy $\mathbf{P}_{{\boldsymbol{w}}}$ would be
identically distributed with the expected output $Y$ which follows
$\mathbf{P}_{\text{true}}$. In this case if $Y$ is a “target of prediction”
that is to be used in the utility function for similarity comparison, as in
the case of (15) and (16) in Section A, then an identically distributed $A$ to
such $Y$ is not necessarily optimal. Instead, an optimal policy may generate
the MAP output, which is deterministic, as discussed in Section A.

However, the probability sampling rule enjoys a universal quality guarantee,
regardless of the utility function, if the expected output $Y$ itself is the
outcome of another policy. This can be easily observed from the expected
utility formula (14), where the performance of a policy depends only on the
probability distributions induced by the policy. If $Y$ is considered an
expected output, this is equivalent to say that $\mathbf{P}_{\text{true}}$ is
an expected policy, in this case a policy giving the identical distribution
$\mathbf{P}_{{\boldsymbol{w}}}=\mathbf{P}_{\text{true}}$ is necessarily an
expected policy too, by virtue of (14). In particular, if
$Y\sim\mathbf{P}_{\text{true}}$ is the outcome of an optimal policy, then the
probability sampling rule (2) based on
$\mathbf{P}_{{\boldsymbol{w}}}=\mathbf{P}_{\text{true}}$ is necessarily an
optimal decision rule too.

As a concrete example, consider the famous picture in Figure 3, and suppose
the task is to predict the color of the dress in it by observing the picture
(only). The ground truth is that the dress

Figure 3:

is in blue and black Akbareian [2015], but average human beings are known to
have divergent opinions on their observed color: $57\%$ saw the dress as blue
and black, $30\%$ saw it as white and gold, $11\%$ saw it as blue and brown,
and $2\%$ reported it as "other color", according to Lafer-Sousa et al.
[2015]. In this case, it seems that the optimal decision should match the
unique and deterministic groundtruth (and following the MAP rule based on the
human distribution indeed gives the optimal decision in this example). Yet, a
decision policy that with probability $57\%$ outputs “blue and black” and with
probability $30\%$ outputs “white and gold” etc. is _as good as human beings_
in predicting the groundtruth (for this particular picture), even though it
may not be the optimal policy.

Importantly, in many practices, the outputs in training data are indeed
generated by randomly recruiting a group of human beings and letting them
access to the same task inputs with what the AI/ML models would access to; the
training data thus obtained does not represent the groundtruth, the true
target of prediction, but is merely a sample of the “human policy”. What
matters here is only the overall conditional distribution (conditioned on the
input) as represented by the training data, and reproducing the same
distribution in AI/ML model’s actual outputs should thus be considered as good
(or as bad), no matter what the utility behind the human choices actually is.

In summary, making the actual output $A$ identically distributed with $Y$ (or
with as close distribution as possible) is a reasonable decision rule when the
expected output $Y$ represents an imitation target at distributional level. In
practice, this idea has been indeed widely adopted, and is known as _behavior
cloning_ in imitation learning Osa et al. [2018]. It is also the basic idea of
_language modeling_ in NLP.

##  Appendix C Is the Training of Auto-regressive Models In Practice Really
Following MLE Principle?

The MLE principle is the theoretical foundation for the standard cross-entropy
loss based training of auto-regressive models. This is explicitly documented
in numerous literature. However, deep learning practice often deviate from its
claimed theoretical rationale in some nuanced yet important ways, and some
readers of this paper might think that the “actual training algorithm” for the
auto-regressive models we studied is not optimizing the MLE objective (5), but
is instead optimizing the token-level cross-entropy loss (for example, a
reviewer of an older version of the paper is holding this position).

We point out that the objective function of "maximizing the (averaged) token
probability", of "maximizing the (averaged) sequence probability", and of
"maximizing the training data’s probability" – denoted by $J_{token}$,
$J_{seq}$, and $J_{data}$ (resp.) – these three objectives differ only in a
constant factor. Specifically, for a training data consisting of $n$
$(\boldsymbol{x}^{\scriptscriptstyle(i)},\boldsymbol{y}^{\scriptscriptstyle(i)})$
pairs,

$\begin{split}J_{data}&\doteq\log\mathbf{P}_{{\boldsymbol{w}}}[\\{\boldsymbol{y}^{\scriptscriptstyle(1..n)}\\}|\\{\boldsymbol{x}^{\scriptscriptstyle(1..n)}\\}]=\sum_{i=1}^{n}\sum_{t=1}^{T_{i}}\log\mathbf{P}_{{\boldsymbol{w}}}[y^{\scriptscriptstyle(i)}_{\scriptscriptstyle
t}|\boldsymbol{x}^{\scriptscriptstyle(i)},\boldsymbol{y}^{\scriptscriptstyle(i)}_{<t}]\\\
J_{seq}&\doteq\frac{1}{n}\sum_{i=1}^{n}\log\mathbf{P}_{{\boldsymbol{w}}}[\boldsymbol{y}^{\scriptscriptstyle(i)}|\boldsymbol{x}^{\scriptscriptstyle(i)}]=\frac{1}{n}\sum_{i=1}^{n}\sum_{t=1}^{T_{i}}\log\mathbf{P}_{{\boldsymbol{w}}}[y^{\scriptscriptstyle(i)}_{\scriptscriptstyle
t}|\boldsymbol{x}^{\scriptscriptstyle(i)},\boldsymbol{y}^{\scriptscriptstyle(i)}_{<t}]=J_{data}/n\\\
J_{token}&\doteq\frac{1}{\sum_{i=1}^{n}T_{i}}\sum_{i=1}^{n}\sum_{t=1}^{T_{i}}\log\mathbf{P}_{{\boldsymbol{w}}}[y^{\scriptscriptstyle(i)}_{\scriptscriptstyle
t}|\boldsymbol{x}^{\scriptscriptstyle(i)},\boldsymbol{y}^{\scriptscriptstyle(i)}_{<t}]=J_{data}/\sum\nolimits_{i=1}^{n}T_{i}\end{split}$

where $n$ and all the $T_{i}$’s are constants. This means the three objectives
must share the same _optimization landscape_ everywhere (including the same
set of global optima, local optima, saddle points, etc.). Whenever one
objective function is increased/decreased, the other two are necessarily
increased/decreased too (and to the same rate).

Among the three, $J_{data}$ is exactly the MLE objective (5), which is in the
sum-form. In order to estimate its gradient with a mini-batch, we have to turn
it into average-form, e.g. to either $J_{seq}$ or $J_{token}$. In this, a
notable implementation detail is that most popular training programs of auto-
regressive models (huggingface, fairseq, tensor2tensor, etc.) sample the mini-
batch in the unit of complete sequence, not in the unit of token. In other
words, the mini-batch obtained in real-world training programs is an i.i.d.
sample of _only_ the sequence-level loss $J_{seq}$. In particular, tokens in
the same sequence are not independently sampled – they are either included
together or excluded together in the mini-batches.

In summary, current training programs in practice are doing faithful SGD-based
optimization for the MLE objective $J_{data}$, with the sequence-level loss
$J_{seq}$ being its average-form surrogate for the sake of gradient
estimation.

##  Appendix D Ordinal Utility, Cardinal Utility, and Value function in RL

The concept of utility was proposed and extensively studied in decision theory
Fishburn [1990], and is also central in microeconomics Moscati [2018]. In its
cardinal interpretation, the utility of a decision is a real number that
represents the “value” of the decision to a decision maker _such that_ the
decision maker is said rational if it always chooses the option that maximizes
the utility (or the expected utility when facing uncertainty). Such a cardinal
utility function is assumed to (pre-)exist for a decision maker, and the
decision maker can be classified as “rational” or “irrational” based on this
utility function.

As an example, the _action-value_ function in reinforcement learning Sutton
and Barto [2018], usually denoted as a Q-function, can be seen as a cardinal
utility function which is pre-defined by a reward function and the associated
Markov Decision Process model, and a rational decision policy that maximizes
its action-value under any state is an optimal policy.

However, the cardinal interpretation of utility often suffers from
measurability problem in practice Moscati [2018]. Given a specific decision
maker, it is often hard to quantitatively measure its cardinal utility
function (even if it exists). What is actually observable is the decisions
eventually made by the decision maker. For example, this is exactly the case
in the supervised learning setting as studied in this paper: the supervised
training data only reveals the actual outputs chosen, not the utilities behind
them. Moreover, real-world decision makers often has bounded rationality only,
in which case the revealed decisions are not necessarily aligned with the
cardinal utility function at all.

For the above reasons, modern literature have largely shifted to estimating an
_ordinal utility_ function from revealed preference of a decision maker. An
ordinal utility function uniquely encodes a preference order over the choices
by assigning each choice with a preferential score (a.k.a. the utility value).
The absolute value of the score is not necessarily equal to any (hypothetical)
cardinal utility, but it is solely the rank of the scores that is responsible
for modeling the observed decision preferences revealed in data. This idea of
ordinal utility was adopted in modern economics as a more practical approach
to utility analysis(a.k.a. the so-called “ordinal revolution”); see Chapter 5
of the book Moscati [2018] for more information.

We remark that even though the action-value functions in RL has a cardinal
definition under the MDP framework, in practice the _actual_ Q-functions
learned by RL algorithms often work as an ordinal utility function. For
example, traditional Q-learning algorithms usually seek to iterate a
parameterized Q-function toward the solution of a Bellman optimality equation.
However, under nonlinear parameterization, the learned Q-function is known to
diverge in general Sutton and Barto [2018] and often predict Q-values that are
far from the Bellman-optimal Q-function Lan et al. [2020], Lillicrap et al.
[2015], yet it can still well support decision making in practice Mnih et al.
[2015]. Recently, new Q-learning algorithms have been proposed that do not
seek to approximate the canonical Bellman-optimal Q-function at all Garg et
al. [2021] but focus on learning any Q-function with which the greedy policy
is optimal Bojun [2022]. The optimal Q-function of this more general class is
essentially an ordinal utility function that encodes the decision preference
of an optimal policy without the cardinal constraint of being the Bellman-
optimal Q-function.

In this paper we interpret the output of a modern neural network as an ordinal
utility function as discussed above, and we explained why the “apparent
likelihood maximization” procedure – when applied to a big softmax-normalized
model – is approximately estimating a utility function and why this utility-
based explanation better accounts for what we observed in experiments.

##  Appendix E Extended Discussion on Related Works

The facts shown in Section 2, that both maximizing and sampling the learned
probability model perform poorly while going greedy or near-greedy with the
local probabilities performed surprisingly well, and that the model assigns
very low probabilities to desired outputs while giving much higher
probabilities to undesired outputs, make one naturally wonder if the learned
neural networks are really supporting decision making _through_ good
probability modeling. In this section we discuss some existing explanations in
the literature on this issue.

Eikema and Aziz [2020] defended the probabilistic interpretation of the
learned translation models by showing that the predicted probabilities
$\mathbf{P}_{{\boldsymbol{w}}}$ do match the groundtruth probabilities
$\mathbf{P}_{\text{true}}$ in some statistics. They then attributed the
pathological behavior of MAP output to the high entropy of the distribution
being represented, arguing that when the most probable output has a
probability as low as $1/10^{4}$, one should simply not trust the MAP rule.
While this argument does make sense, we stress that the low predicted
probability of the MAP output (or equivalently, the high entropy of
$\mathbf{P}_{{\boldsymbol{w}}}$) itself is suggesting that the learned
distribution $\mathbf{P}_{{\boldsymbol{w}}}$ is very different from the true
distribution $\mathbf{P}_{\text{true}}$ as the latter _should have been_
highly concentrated. In fact, tasks like text translation or summarization
fall in the category that the expected output is essentially unique, either
directly at utterance level like in the specific WMT’14 dataset, or at the
semantic level more generally; in this case the MAP output _would_ be optimal
if the learned probability $\mathbf{P}_{{\boldsymbol{w}}}$ _were_ indeed
accurate about estimating $\mathbf{P}_{\text{true}}$ (see Section A for
elaborations). In other words, the inadequacy of MAP output can only be
_caused_ by the inaccuracy of probability modeling.

Many works do posit that the learned model deviates from the groundtruth
distribution, and they seek to find out why. Ranzato et al. [2016] suggested
that the distributional mismatch could be due to the inevitable discrepancy
between the decision contexts that the model will encounter at training and
testing time (in translation, for example, the decision context corresponds to
the partial translations $\boldsymbol{y}_{<t}$). Wang and Sennrich [2020]
attributes the beam search pathology (observation (3) in Section 2.2) to this
discrepancy. Subsequent studies, such as Zhang et al. [2019], proposed methods
to reduce this _exposure bias_ in order to facilitate better probability
modeling. This line of works however did not explain why (near-)greedy
decisions _based on a model that is suffering from the exposure bias_ can
somehow lead to good empirical result. It appears that the model we obtained
is not arbitrarily biased, but the bias _happens to_ best support a certain
kind of decision rule (i.e. the greedy rule), across different tasks,
different models, and different data sets.

Wu et al. [2016] observed that the beam search pathology is associated with
the tendency to output shorter sentences under more extensive search.
Stahlberg and Byrne [2019] confirmed that this _length bias_ is mostly due to
errors in probability estimation, instead of to errors caused by the non-
admissible search. On the other hand, Cohen and Beck [2019] observed abnormal
fluctuations of token-wise probabilities in pathological outputs, providing
another factor associated to the search pathology. In addition, Holtzman et
al. [2019] found that the inadequacy of the sampled output (observation (1) in
Section 2.2) is related to errors in the long tail of the distribution. All
these works also complemented their discoveries with heuristic rules to
prevent the search/sampling procedure from running into the identified
pathological situations. These studies identified the failure patterns when
the probability-based decision rules are getting wrong. But again, they did
not shed too much light on why probability-_incompatible_ decision rules such
as the greedy rule turn out to work much better. Note that the heuristics
proposed in these works themselves have effectively made the resulted search
or sampling procedure a deviation from the probability principles. These
results leave it open for why we _have to_ deviate from well-established
probability principles, either in the form of greedy decision or by some sort
of heuristic-augmented search/sampling, to obtain competitive performance from
the learned “probability models”.

Meister et al. [2020] connected the pathological fluctuation of token-level
probabilities as observed in Cohen and Beck [2019] to a “uniform information
density (UID)” hypothesis in cognitive science, offering a probability-based
explanation to the effectiveness of greedy output. However, the precise
mathematical expression of the UID hypothesis itself is subject to different
interpretations Meister et al. [2021]. For example, Meister et al. [2020]
examined a number of different regularization terms, all considered as a form
of UID regularization; it turns out that the two “purest UID regularizers”
performed the worst, while a “greedy UID regularizer” (Eq.11 of the paper,
which literally penalizes for deviating from the greedy output) performs the
best. It is then subject to debate regarding if the greedy UID regularizer
here has facilitated preference to UID outputs or directly to greedy outputs.
In contrast, in this paper we seek to develop a mathematically clear and non-
probabilistic account to explain the effectiveness of greedy outputs.

##  Appendix F Proofs

###  F.1 Proof of Proposition 1

###### Proposition 1.

Given input $\boldsymbol{x}$, output $\boldsymbol{y}=(y_{\scriptscriptstyle
1}\dots y_{\scriptscriptstyle T})$, and parametric model
$Q({\boldsymbol{w}})$, we have

$\begin{split}\frac{\partial\log\mathbf{P}_{{\boldsymbol{w}}}[\boldsymbol{y}|\boldsymbol{x}]}{\partial
w_{j}}=\frac{\partial J_{\text{MABE}}}{\partial
w_{j}}({\boldsymbol{w}},\boldsymbol{x},\boldsymbol{y})~{}+~{}\sum_{t=1}^{T}\mathbf{cov}_{t}\Big{[}Q,\frac{\partial
Q}{\partial w_{j}}\Big{]}\quad\quad,~{}~{}\forall j\end{split}$

where $\mathbf{cov}_{t}\Big{[}Q,\frac{\partial Q}{\partial
w_{j}}\Big{]}\doteq\underset{\scriptscriptstyle A_{t}\sim
P_{t}}{\mathbf{cov}}\Big{[}Q_{t}(A_{t})~{},~{}\frac{\partial Q_{t}}{\partial
w_{j}}(A_{t})\Big{]}$

$\displaystyle=~{}$
$\displaystyle\sum_{a}P_{t}(a)\cdot\Big{(}Q_{t}(a)-\sum_{b}P_{t}(b)Q_{t}(b)\Big{)}\cdot\Big{(}\frac{\partial
Q_{t}}{\partial w_{j}}(a)-\sum_{b}P_{t}(b)\frac{\partial Q_{t}}{\partial
w_{j}}(b)\Big{)}\hskip 39.74872pt$

  * $\bullet$

$\mathbf{P}_{{\boldsymbol{w}}}$ is the softmax distribution induced by
$Q({\boldsymbol{w}})$ as prescribed by (3) and (6),

  * $\bullet$

$P_{t}(a)$ denotes
$\mathbf{P}_{{\boldsymbol{w}}}[a|\boldsymbol{x},\boldsymbol{y}_{<t}]$, the
probability that the token at step $t$ is $a$, according to
$\mathbf{P}_{{\boldsymbol{w}}}$,

  * $\bullet$

$Q_{t}(a)$ denotes $Q(a|\boldsymbol{x},\boldsymbol{y}_{<t};{\boldsymbol{w}})$,
the utility of outputting token $a$ at step $t$, according to
$Q({\boldsymbol{w}})$,

  * $\bullet$

$\frac{\partial Q_{t}}{\partial w_{j}}(a)$ denote $\frac{\partial Q}{\partial
w_{j}}(a|\boldsymbol{x},\boldsymbol{y}_{<t};{\boldsymbol{w}})$, the partial
derivative of $Q(a|\boldsymbol{x},\boldsymbol{y}_{<t};{\boldsymbol{w}})$ at
step $t$,

###### Proof.

From (7) (and (3)), we have that for any component $j$ of the model parameter
${\boldsymbol{w}}$,

$\frac{\partial\log\mathbf{P}_{{\boldsymbol{w}}}[\boldsymbol{y}|\boldsymbol{x}]}{\partial
w_{j}}=\sum_{t=1}^{T}\Big{(}~{}\frac{\partial Q_{[y_{\scriptscriptstyle
t}]}}{\partial
w_{j}}(\boldsymbol{x},\boldsymbol{y}_{<t};{\boldsymbol{w}})-\sum_{a}~{}f_{[a]}(\boldsymbol{x},\boldsymbol{y}_{<t};{\boldsymbol{w}})~{}\frac{\partial
Q_{[a]}}{\partial
w_{j}}(\boldsymbol{x},\boldsymbol{y}_{<t};{\boldsymbol{w}})~{}\Big{)}.$

By definition of $J_{\text{MABE}}$ (i.e. (4)),

$\begin{split}\frac{\partial
J_{\text{MABE}}({\boldsymbol{w}},\boldsymbol{x},\boldsymbol{y})}{\partial
w_{j}}=~{}&\frac{\partial}{\partial
w_{j}}\sum_{t=1}^{T}~{}\Big{(}~{}Q_{[y_{\scriptscriptstyle
t}]}(\boldsymbol{x},\boldsymbol{y}_{<t};{\boldsymbol{w}})-\sum_{a}f_{[a]}(a|\boldsymbol{x},\boldsymbol{y}_{<t};{\boldsymbol{w}})Q_{[a]}(\boldsymbol{x},\boldsymbol{y}_{<t};{\boldsymbol{w}})~{}\Big{)}\\\
=~{}&\sum_{t=1}^{T}~{}\Bigg{(}~{}\frac{\partial Q_{[y_{\scriptscriptstyle
t}]}}{\partial
w_{j}}(\boldsymbol{x},\boldsymbol{y}_{<t};{\boldsymbol{w}})-\sum_{a}f_{[a]}(\boldsymbol{x},\boldsymbol{y}_{<t};{\boldsymbol{w}})~{}\frac{\partial
Q_{[a]}}{\partial
w_{j}}(\boldsymbol{x},\boldsymbol{y}_{<t};{\boldsymbol{w}})\\\
&\quad\quad\quad-\sum_{a}Q_{[a]}(\boldsymbol{x},\boldsymbol{y}_{<t};{\boldsymbol{w}})~{}\frac{\partial
f_{[a]}}{\partial
w_{j}}(\boldsymbol{x},\boldsymbol{y}_{<t};{\boldsymbol{w}})~{}\Bigg{)}\\\
=~{}&\frac{\partial\log\mathbf{P}_{{\boldsymbol{w}}}[\boldsymbol{y}|\boldsymbol{x}]}{\partial
w_{j}}-\sum_{t}\sum_{a}Q_{t}(a)~{}\frac{\partial P_{t}}{\partial
w_{j}}(a)\end{split}$

So now we only need to prove that

$\sum_{a}Q_{t}(a)~{}\frac{\partial P_{t}}{\partial
w_{j}}(a)=\underset{\scriptscriptstyle A_{t}\sim
P_{t}}{\mathbf{cov}}\Big{[}Q_{t}(A_{t})~{},~{}\frac{\partial Q_{t}}{\partial
w_{j}}(A_{t})\Big{]}.$ (17)

At the right-hand side of (17), $Q_{t}(A_{t})$ and $\frac{\partial
Q_{t}}{\partial w_{j}}(A_{t})$ are two random variables defined on top of the
sample space of $A_{t}\sim P_{t}$. Recall that for any random variables $X$
and $Y$,
$\mathbf{cov}[X,Y]\doteq\mathbf{E}[(X-\mathbf{E}[X])(Y-\mathbf{E}[Y])]=\mathbf{E}[X(Y-\mathbf{E}[Y])]$,
thus

$\displaystyle\underset{\scriptscriptstyle A_{t}\sim
P_{t}}{\mathbf{cov}}\Big{[}Q_{t}(A_{t})~{},~{}\frac{\partial Q_{t}}{\partial
w_{j}}(A_{t})\Big{]}=~{}$
$\displaystyle\operatorname*{\mathbf{E}}_{\begin{subarray}{c}A_{t}\sim
P_{t}\end{subarray}}~{}\Big{[}Q_{t}(A_{t})~{}\Big{(}~{}\frac{\partial
Q_{t}}{\partial
w_{j}}(A_{t})-\operatorname*{\mathbf{E}}_{\begin{subarray}{c}A_{t}\sim
P_{t}\end{subarray}}\big{[}~{}\frac{\partial Q_{t}}{\partial
w_{j}}(A_{t})~{}\big{]}~{}\Big{)}\Big{]}$ $\displaystyle=~{}$
$\displaystyle\sum_{a}P_{t}(a)~{}Q_{t}(a)~{}\Big{(}~{}\frac{\partial
Q_{t}}{\partial w_{j}}(a)-\sum_{b}P_{t}(b)\frac{\partial Q_{t}}{\partial
w_{j}}(b)~{}\Big{)}$ (18) $\displaystyle=~{}$
$\displaystyle\sum_{a}P_{t}(a)~{}Q_{t}(a)~{}\frac{\partial\log
P_{t}(a)}{\partial w_{j}}$ (19) $\displaystyle=~{}$
$\displaystyle\sum_{a}Q_{t}(a)~{}\frac{\partial P_{t}(a)}{\partial w_{j}}$

Note that from (18) to (19) we have utilized the equation (7) again. ∎

###  F.2 Proof of Theorem 2

###### Theorem 2.

Consider a tabular model
$Q(a;\boldsymbol{q})=\sum_{j=1}^{d}\mathds{1}[a=j]\cdot q_{j}$, where the
parameter vector $\boldsymbol{q}=(q_{1}\dots q_{d})$ directly encodes the
estimated utilities for each possible action $a\in\\{1\dots d\\}$. Let
$\boldsymbol{p}=(p_{1}\dots p_{d})$ be the softmax distribution induced by
$\boldsymbol{q}$. Let $\boldsymbol{q}^{*}$ be the Q-values that maximizes
$J(\boldsymbol{q})=\operatorname*{\mathbf{E}}_{\begin{subarray}{c}Y\sim\mathbf{P}_{\text{true}}\end{subarray}}~{}\Big{[}Q(Y;\boldsymbol{q})\Big{]}-\operatorname*{\mathbf{E}}_{\begin{subarray}{c}A\sim\boldsymbol{p}\end{subarray}}~{}\Big{[}Q(A;\boldsymbol{q})\Big{]}$,
and $\boldsymbol{p}^{*}$ the corresponding softmax distribution,

  1. (1)

for any action $a\in\\{1\dots d\\}$,

$p^{*}_{a}\cdot(~{}1+q^{*}_{a}-\mathbf{E}_{\boldsymbol{p}^{*}}[Q]~{})~{}~{}=~{}~{}\mathbf{P}_{\text{true}}[Y=a]$

  2. (2)

let $\mathrm{supp}(Y)$ be the support of $\mathbf{P}_{\text{true}}$ (which is
thus the set of all desired actions),

$\max_{a\in\mathrm{supp}(Y)}~{}q^{*}_{a}~{}~{}>~{}~{}\max_{b\not\in\mathrm{supp}(Y)}~{}q^{*}_{b}~{}~{}+~{}~{}1$

###### Proof.

We first prove Conclusion (1). Applying Proposition 1 to $J(\boldsymbol{q})$ –
which corresponds to a special case of $J_{\text{MABE}}$ with $T=1$ (single
step) and $|\mathrm{supp}(X)|=1$ (single input) – yields

$\frac{\partial J}{\partial
q_{j}}=\operatorname*{\mathbf{E}}_{\begin{subarray}{c}Y\sim\mathbf{P}_{\text{true}}\end{subarray}}~{}\Big{[}\frac{\partial
Q}{\partial
q_{j}}(Y;\boldsymbol{q})\Big{]}-\operatorname*{\mathbf{E}}_{\begin{subarray}{c}A\sim\boldsymbol{p}\end{subarray}}~{}\Big{[}\frac{\partial
Q}{\partial q_{j}}(A;\boldsymbol{q})\Big{]}-\underset{\scriptscriptstyle
A\sim\boldsymbol{p}}{\mathbf{cov}}\Big{[}Q(A;\boldsymbol{q}),\frac{\partial
Q}{\partial q_{j}}(A;\boldsymbol{q})\Big{]}$ (20)

Since $\frac{\partial Q}{\partial q_{j}}(a;\boldsymbol{q})=\mathds{1}[a=j]$,
we have that for _any_ random variable $Z$,

$\mathbf{E}_{Z}\Big{[}\frac{\partial Q}{\partial
q_{j}}(Z;\boldsymbol{q})\Big{]}~{}=~{}\sum_{z}\mathbf{P}[Z=z]~{}\frac{\partial
Q}{\partial
q_{j}}(z;\boldsymbol{q})~{}=~{}\sum_{z}\mathbf{P}[Z=z]~{}\mathds{1}[a=j]~{}=~{}\mathbf{P}[Z=j].$
(21)

Applying (21) to (20), yields

$\begin{split}\frac{\partial J}{\partial
q_{j}}&=\mathbf{P}_{\text{true}}(j)-p_{j}-\underset{\scriptscriptstyle
A\sim\boldsymbol{p}}{\mathbf{cov}}\Big{[}Q(A;\boldsymbol{q}),\frac{\partial
Q}{\partial q_{j}}(A;\boldsymbol{q})\Big{]}\\\
&=\mathbf{P}_{\text{true}}(j)-p_{j}+\mathbf{E}_{\boldsymbol{p}}[Q]\cdot\mathbf{E}_{\boldsymbol{p}}[\frac{\partial
Q}{\partial q_{j}}]-\mathbf{E}_{\boldsymbol{p}}[Q\cdot\frac{\partial
Q}{\partial q_{j}}]\\\ &=\mathbf{P}_{\text{true}}(j)-p_{j}+\mathbf{E}[Q]\cdot
p_{j}-\mathbf{E}_{\boldsymbol{p}}[Q\cdot\frac{\partial Q}{\partial
q_{j}}]\end{split}$

With the same the argument as in (21), we similarly have
$\mathbf{E}_{\boldsymbol{p}}[Q\cdot\frac{\partial Q}{\partial
q_{j}}]=\sum_{a}p_{a}\cdot q_{a}\cdot\mathds{1}[a=j]~{}=~{}p_{a}\cdot q_{a}$,
thus

$\frac{\partial J}{\partial
q_{j}}=\mathbf{P}_{\text{true}}(j)-p_{j}+\mathbf{E}_{\boldsymbol{p}}[Q]\cdot
p_{j}-p_{j}\cdot q_{j}$ (22)

At $\boldsymbol{p}^{*}$ and $\boldsymbol{q}^{*}$, $\frac{\partial J}{\partial
q_{j}}=0$ for all $j$, so

$p^{*}_{j}\cdot(~{}1+q^{*}_{j}-\mathbf{E}_{\boldsymbol{p}^{*}}[Q]~{})~{}=~{}\mathbf{P}_{\text{true}}(j)\quad,~{}~{}\forall
j\in\\{1\dots d\\}$ (23)

which gives Conclusion (1).

To derive Conclusion (2), we will prove a stronger result, that

######  Proposition 3.

A $\boldsymbol{q}^{*}$ that maximizes $J$ will assign the same utility,
$\operatorname*{\mathbf{E}}_{\begin{subarray}{c}\boldsymbol{p}^{*}\end{subarray}}[Q]-1$,
to every undesired action $b\not\in\mathrm{supp}(Y)$.

What immediately follows Proposition 3 is that there must be at least one
desired action $a\in\mathrm{supp}(Y)$ such that
$q^{*}_{a}>\mathbf{E}_{\boldsymbol{p}^{*}}[Q]$ (as otherwise no action would
have utility above the _averaged_ utility
$\mathbf{E}_{\boldsymbol{p}^{*}}[Q]$), and therefore,
$\max_{a\in\mathrm{supp}(Y)}~{}q^{*}_{a}~{}~{}>~{}~{}\mathbf{E}_{\boldsymbol{p}^{*}}[Q]~{}~{}=~{}~{}\max_{b\not\in\mathrm{supp}(Y)}~{}q^{*}_{b}+1$.

Now we prove Proposition 3. Consider an arbitrary undesired action
$b\not\in\mathrm{supp}(Y)$. For any such $b$, $\mathbf{P}_{\text{true}}(b)=0$.
As a result, the left-hand side of (23) must be zero too, for $j=b$; that is,
$p^{*}_{b}\cdot(1+q^{*}_{b}-\mathbf{E}_{\boldsymbol{p}^{*}}[Q])=0$. So there
can be only two possibilities: either
$1+q^{*}_{b}-\mathbf{E}_{\boldsymbol{p}^{*}}[Q]=0$ which is exactly what
Proposition 3 is asserting, or $p^{*}_{b}=0$. In the following we show that
$p^{*}_{b}=0$ is impossible, even as a limit.

Strictly speaking, $p^{*}_{b}$ cannot be exactly zero simply because
$\boldsymbol{p}^{*}$ is a softmax distribution with finite logits. But one may
wonder the possibility that a $\boldsymbol{p}^{*}$ with $p^{*}_{b}=0$ is a
_supremum_ of $J$ in the limit; in that case the optimization of
$J(\boldsymbol{q})$ (i.e. the MABE optimization) may update $q^{*}_{b}$
towards $-\infty$ (although never reaches it), thus breaks Proposition 3. 999
Note that in this case
$\mathbf{E}_{\boldsymbol{p}^{*}}[Q]=\sum_{i}p^{*}_{i}q^{*}_{i}$ is still
finite, thus well defined, because
$\lim\limits_{q^{*}_{b}\rightarrow-\infty}p^{*}_{b}q^{*}_{b}=0$.

It turns out that such a supremum with $q^{*}_{b}=-\infty$ cannot exist for
the $J$ as defined. Specifically, consider the process of taking an arbitrary
$\boldsymbol{q}$ with $q_{b}=\mathbf{E}[Q]-1$ then decreasing $q_{b}$ down
toward $-\infty$ (while keeping all other $q_{j\neq b}$ fixed). As
$q_{b}<\mathbf{E}[Q]-1$ throughout this process, we have
$1+q_{b}-\mathbf{E}[Q]<0$ all the time, and thus by (22), $\frac{\partial
J}{\partial q_{b}}=\mathbf{P}_{\text{true}}(b)-p_{b}(1+q_{b}-\mathbf{E}[Q])>0$
throughout the process. Since $q_{b}$ is decreasing, $J$ must be also
decreasing due to the positive derivative. Therefore, $J$ cannot attain a
maximum (or supremum) at $q_{b}=-\infty$, not even a local maximum/supremum. ∎

As an example, Figure 4 illustrates the function $J$ when there are only two
actions (i.e. $d=2$) and assume action $1$ is the expected/desired one. In
this case $\boldsymbol{q}=(q_{1},q_{2})$, and Figure (4) shows the cross
section at $q_{1}=0$ for the 2D function $J(\boldsymbol{q})$ (the shape is the
same at all $q_{1}$’s). The global maximum of $J(\boldsymbol{q})$ is attained
at
$q_{2}=\operatorname*{\mathbf{E}}_{\begin{subarray}{c}\boldsymbol{p}\end{subarray}}[\boldsymbol{q}]-1$.
Notably, we see that the MABE objective function $J$ is non-convex, and yet it
has a unique _local_ maximum point.

Figure 4: Shape of the MABE objective $J(\boldsymbol{q})$, for
$\boldsymbol{q}=(q_{1},q_{2})$.

##  Appendix G More Experimental Results

In this section we present our experimental results in details, task by task.

###  G.1 Translation-WMT14en2de

The WMT’14 NewsTest English$\rightarrow$German (en2de) task asks to translate
English sentences in news articles into German sentences, and is among the
most-used public benchmarks in machine translation. In this task, the expected
input $X$ is an English sentence following distribution defined by the
training data, the expected output $Y$ is a sequence of German tokens, ending
with a special End-Of-Sentence(EOS) token. EOS is generated either as part of
the actual output (by the learned model), or is forced by the system when the
translation is $2$x long compared with the source sentence.

The training dataset 101010https://nlp.stanford.edu/projects/nmt/ consists of
$4.5$ million sentences of translation examples, and the testing dataset
consists of $2737$ examples. The data was pre-processed and post-processed
using the BPE tokenizer Sennrich et al. [2016] provided by YouTokenToMe
111111https://github.com/VKCOM/YouTokenToMe, with shared vocabulary of size
$37000$. We used SacreBLEU Post [2018] to calculate the BLEU scores.

We first trained the standard TransformerBase neural network Vaswani et al.
[2017] for $100,000$ SGD steps with the standard cross-entropy loss, which
corresponds exactly to the MLE procedure (5) as discussed in the paper. We
followed the same hyperparameter setting recommended in Vaswani et al. [2017],
which is known to achieve a BLEU score around $27.3$ under a near-greedy
decision rule. A dropout rate of $0.1$ and labeling smoothing of $0.1$ are
applied, again as recommended by Vaswani et al. [2017].

The learned neural network was then used to power a number of different
decision rules:

  * •

Temperature-regulated Sampling: A generalization of the pure sampling rule
(2), in which the sampling probabilities are scaled by a temperature parameter
$\beta$, with
$\mathbf{P}[A_{t}=y|\boldsymbol{x},\boldsymbol{y}_{<t}]\propto(\mathbf{P}_{{\boldsymbol{w}}}[Y_{t}=y|\boldsymbol{x},\boldsymbol{y}_{<t}])^{1/\beta}$.
When $\beta=1$, the temperature-regulated sampling implements exactly the
probability sampling rule (2). With $\beta$ tuned toward $0$, the
parameterized sampling deviates from the genuine probability predictions, and
is biased more and more toward near-greedy outputs. The greedy rule
corresponds to $\beta=0$.

  * •

Greedy Decoding: The greedy decision rule (4).

  * •

Beam Search: The standard and _vanilla_ version of beam-search decoding, which
uses the estimated probability as the heuristic score of a partial output in
the search (see Algorithm 1 in Stahlberg and Byrne [2019]).

The translation performance on the testing set is reported in Figure 5. The
figure also shows the estimated probabilities according to the softmax
probability model (the sentence-level probability of the translation for each
testing instance was estimated, then their logarithms with base $10$ were
averaged over all testing instances). As discussed in Section 2.2, these
results exhibit counter-intuitive behaviors if we think of the learned neural
network as a probability model.

In comparison, the translation performance and the estimated probabilities
make much more sense if we instead use the dual probabilities as prescribed by
(13), as Figure 6 shows: The sampling output based on dual probabilities is
still not the best (as expected, see Section B), but is much more reasonable
now. Going greedy with the dual probabilities gives better outputs than
sampling (25.6 vs 20.0), and in fact is giving the same output with the greedy
ones under softmax probabilities (this is expected as both probability models
are order preserving). The beam search result, approximately representing the
MAP output, is further slightly better the greedy ones (25.9 vs 25.7) under
the dual probabilities, which again aligns with the expectation that truly
maximizing the probabilities should help with the performance (instead of
hurting it, as in the case of softmax probability).

In terms of probability estimation, the dual probability model is generally
less perplexed than the softmax model, as Figure 6(right) shows. The
likelihood of empty output (which is zero) is also correctly estimated by the
dual probabilities now. It is only a pity that the model will also assign zero
probability for most of the reference translations ($2614$ out of $2737$,
which is less than that for empty outputs though). In fact, the dual
probability model will assign reasonable likelihood to most _tokens_ in the
reference translations, but may only occasionally judge some tokens as
“impossible”; however, once there is a single token is judged so in a
reference translation, the probability of the whole sentence becomes zero. We
tend to think of this as a fragile nature of the probability-based method in
general.

Finally, Figure 7 shows the learning curves of different MABE($\lambda$)
variants in WMT’14 en2de, which complements Figure 2(a) of Section 4 with more
numerical details. All variants use the same hyperparameter setting with the
aforementioned MLE training, except that label smoothing is disabled (as it is
incompatible to value learning). Each point in the figure gives the test-set
BLEU score of model trained by a given algorithm variant for a given number of
SGD steps. The results are averaged over four random seeds.

We see that all algorithms demonstrate similar learning curves, with MABE(2)
slighly left behind at the beginning stage. MABE(0), the unperturbed variant,
appears to perform slightly better than other perturbed variants.

###  G.2 Translation-WMT17zh2en

The WMT’17 Chinese$\rightarrow$English (zh2en) task asks to translate news
articles in Chinese into English. The expected input $X$ is a Chinese sentence
(distribution defined by the training data), and the expected output $Y$ is a
sequence of English tokens, again ending with the EOS token which is either
generated or forced when the output reaches $2$x long than the input. As the
two languages are more distinct, it is generally considered a harder
translation task than WMT’14 en2de.

The raw WMT’17 zh2en training data contains 25 million sentences of
translation examples from three sources: News Commentary, UN Parallel Corpus
and CWMT Corpus. 121212https://www.statmt.org/wmt17/translation-
task.html#download We cleaned the raw data following the steps described in
Hassan et al. [2018] (with slight difference in parameter details):

  * •

Sentences with illegal characters (such as URLs, characters of other
languages) and empty sentences are removed.

  * •

Duplicate translation examples are dropped.

  * •

Both the source and target sentences should contain at least 3 words and at
most 80 words.

  * •

Chinese sentences without any Chinese characters are discarded.

The final training data set consists of about 21 million sentence-pairs. The
testing set _newstest2017_ was left intact. For Chinese data, we adopting the
Jieba tokenizer131313https://github.com/fxsjy/jieba before the byte pair
encoding (BPE). English sentences are tokenized using the scripts provided in
Moses before using BPE. The BPE vocabularies for Chinese and English are
generated separately, each with a merge-operation budget of 32000. The
generated Chinese and English vocabulary contains 50K and 33K sub-word tokens,
respectively.

We conducted the same set of experiments in WMT’17 zh2en as we did in WMT’14
en2de: We trained a TransformerBase neural network (8 heads for each multi-
head module in both encoder and decoder layers; 512 for the dimensions of
input and output layers, and 2048 for the inner feed-forward layers), first
with the standard MLE loss then with the MABE($\lambda$) losses, for $100,000$
SGD steps each. The hyperparameter setting is identical across all losses
(optimizer and learning rate settings followed Vaswani et al. [2017], training
batch size is roughly 36,000 English tokens, drop-out rate is 0.3), except
that the label smoothing weight is 0.1 for MLE (0.0 for MABE variants,
including MABE(1)). BLEU calculation is by SacreBLEU.

Figure 8 illustrates the behaviors of the MLE model under various decision
rules. We see that Probability sampling and maximization (approximated by beam
search with beam size $=1024$) failed in WMT’17 zh2en too, achieving only
$8.3$ and $11.9$, respectively. In comparison, greedy outputs reaches $22.6$,
which is only $0.8$ BLEU lower than the best solution (beam search with beam
size $=4$). All the four observations discussed in Section 2.2 occurred in
WMT’17 zh2en too. Similarly, the dual probabilities dramatically improve the
performance of sampling and MAP in WMT’17 zh2en, to the levels that match the
expectations much better, as Figure 9 shows.

Trends in the learning curves of different MABE variants (Figure 10) also very
much resembled what we saw in WMT’14 en2de. Each data point is the averaged
result over four trials. There is no clear “winner” or “loser”– MABE(2), which
receives doubled perturbation, is again slower in the learning progress at the
beginning, but it quickly catches up and slightly exceeds other variants
around the end of the training. The experimental results once again support
our main hypothesis that the covariance-based perturbation in MABE($\lambda$)
does not make significant difference under modest $\lambda$.

###  G.3 Summarization-CNN/DM

The CNN/DailyMail Summarization task asks to generate abstracts for news
articles collected from CNN and DailyMail. The excepted input $X$ is a full
news article in English, and the expected output $Y$ is a (much shorter)
sequence of English tokens, ending with EOS. EOS is forced if the length of
the output reaches $1024$. Comparing with translation tasks, the CNN/DailyMail
task has about $30$x larger inputs and about $3$x larger outputs.

The datasets were prepared by following the procedure used by Lewis et al.
[2020]. We first downloaded the raw CNN/DailyMail dataset
141414https://cs.nyu.edu/$\sim$kcho/DMQA/, then pre-processed the data
(including the train-dev-test split) using scripts
151515https://github.com/abisee/cnndailymail from See et al. [2017]. Then
following the code repository
161616https://github.com/pytorch/fairseq/blob/main/examples/bart/README.summarization.md
of Lewis et al. [2020], we used the GPT-2’s BPE model to convert the pre-
processed data into tokenized sequences over a BPE vocabulary. The final
training data consists of nearly $0.3$ million article-abstract pairs, and the
testing set consists of $2000$. ROUGE, the standard document-summarization
metric, was employed for performance measurement. More specifically, the ROUGE
score reported below is the arithmetic mean of the F1 scores of ROUGE-1,
ROUGE-2, and ROUGE-L.

The TransformerBase neural network in this task has 8 attention heads, 768
dimensions for input and output layers, and 2048 dimensions for the inner
feed-forward layers. We trained the neural network on an A100 GPU, again using
the cross-entropy (=MLE) loss and the MABE($\lambda$) loss with
$\lambda=-2,-1,0,1,2$. Each training lasts for $50,000$ gradient steps, and
each step is based on a mini-batch of about 64 instances. Drop-out rate is
0.1, and label smoothing is 0.1 for MLE; no label smoothing for MABE variants.
All the decision rules used at test time are identical to the ones used in
translation experiments.

From Figure 11 we see that the probability sampling and maximization rules
perform better in CNN/DailyMail summarization, but still have wide gap in
performance compared with the greedy rule ($8.0$ and $9.0$ ROUGE scores lower,
respectively). Once again, the dual probability model largely filled the gap
here, as Figure 12 shows.

Figure 13 shows the learning curves of different MABE variants on
CNN/DailyMail. Each data point is the mean value over two trials. It appears
that positive perturbations (MABE(1) and MABE(2)) lead to slightly lower
result, while negative perturbations (MABE(-1) and MABE(-2)) lead to slightly
higher result. The gap between the unperturbed variant MABE(0) and and the
MLE-equivalent variant MABE(1) is relatively larger in this task (around $1$
ROUGE score).

| BLEU | $\log_{10}\mathbf{P}_{{\boldsymbol{w}}}$
---|---|---
sampling | 5.4 | -62.2
$\beta=0.75$ | 18.3 | -13.5
$\beta=0.5$ | 23.2 | -7.8
$\beta=0.25$ | 25.1 | -6.5
greedy | 25.6 | -6.3
$|\text{beam}|=4$ | 26.8 | -5.8
$|\text{beam}|=16$ | 27.1 | -5.6
$|\text{beam}|=64$ | 25.6 | -5.4
$|\text{beam}|=256$ | 21.5 | -5.1
$|\text{beam}|=512$ | 16.2 | -4.7
$|\text{beam}|=1024$ | 8.6 | -4.2
empty | 0.0 | -4.3
expected | 42.4 171717See calculation method in Section G.5. | -18.4

Figure 5: On WMT’14 en$\rightarrow$de, MLE model exhibits paradoxical
behaviors.

Figure 6: On WMT’14 en$\rightarrow$de, dual probabilities give much more
reasonable probability predictions.

| BLEU (greedy)
---|---
| @90k steps | @95k steps | @100k steps
MLE (ls=0.1) | 25.2 | 25.5 | 25.6
MABE(0) | 25.2 | 25.6 | 25.5
MABE(1) | 25.4 | 25.3 | 25.3
MABE(2) | 25.0 | 25.1 | 25.2
MABE(-1) | 25.5 | 25.2 | 25.5
MABE(-2) | 25.0 | 25.1 | 25.2

Figure 7: On WMT’14 en$\rightarrow$de, different MABE($\lambda$) variants have
similar learning dynamics.

| BLEU | $\log_{10}\mathbf{P}_{{\boldsymbol{w}}}$
---|---|---
sampling | 8.3 | -46.3
$\beta=0.75$ | 16.7 | -14.6
$\beta=0.5$ | 20.3 | -10.2
$\beta=0.25$ | 22.0 | -8.8
greedy | 22.6 | -8.5
$|\text{beam}|=4$ | 23.4 | -7.9
$|\text{beam}|=16$ | 22.9 | -7.5
$|\text{beam}|=64$ | 22.1 | -7.3
$|\text{beam}|=128$ | 21.7 | -7.1
$|\text{beam}|=256$ | 21.0 | -7.0
$|\text{beam}|=512$ | 19.3 | -6.8
$|\text{beam}|=1024$ | 11.9 | -5.9
empty | 0.00 | -4.5
expected | 41.82 181818See calculation method in Section G.5. | -35.2

Figure 8: On WMT’17 zh$\rightarrow$en, MLE model exhibits paradoxical
behaviors.

Figure 9: On WMT’17 zh$\rightarrow$en, dual probabilities give much more
reasonable probability predictions.

| BLEU (greedy)
---|---
| @90k steps | @95k steps | @100k steps
MLE (ls=0.1) | 22.5 | 22.9 | 22.6
MABE(0) | 22.8 | 23.1 | 23.0
MABE(1) | 22.4 | 22.4 | 22.1
MABE(2) | 23.1 | 23.4 | 23.3
MABE(-1) | 22.5 | 22.5 | 22.7
MABE(-2) | 22.5 | 22.6 | 22.4

Figure 10: On WMT’17 zh$\rightarrow$en, different MABE($\lambda$) variants
have similar learning performance.

| ROUGE | $\log_{10}\mathbf{P}_{{\boldsymbol{w}}}$
---|---|---
sampling | 21.1 | -91.5
$\beta=0.75$ | 27.4 | -23.5
$\beta=0.5$ | 28.6 | -14.6
$\beta=0.25$ | 28.9 | -12.4
greedy | 29.1 | -11.6
$|\text{beam}|=4$ | 29.6 | -8.5
$|\text{beam}|=16$ | 28.7 | -7.2
$|\text{beam}|=64$ | 27.5 | -7.3
$|\text{beam}|=128$ | 26.1 | -6.5
$|\text{beam}|=256$ | 25.5 | -6.7
$|\text{beam}|=1024$ | 20.1 | -5.9
empty | 0.00 | -5.8
expected | 100.00 191919Lack of multi-reference data to calculate the actual ROUGE scores. ROUGE=100 for the reference summarizations in single-reference data set. | -85.7

Figure 11: On CNN/DailyMail, MLE model exhibits paradoxical behaviors.

Figure 12: On CNN/DailyMail, dual probabilities give more reasonable
probability predictions.

| ROUGE (greedy)
---|---
| @40k steps | @45k steps | @50k steps
MLE (ls=0.1) | 28.7 | 28.8 | 29.1
MABE(0) | 29.2 | 28.8 | 29.1
MABE(1) | 28.0 | 27.8 | 28.1
MABE(2) | 28.5 | 28.4 | 28.5
MABE(-1) | 28.9 | 29.0 | 29.4
MABE(-2) | 29.4 | 29.3 | 29.4

Figure 13: On CNN/DailyMail, different MABE($\lambda$) variants have similar
learning performance.

###  G.4 COMET Scores of the Dual Probability Model

In above we have been using the standard performance metrics to evaluate
probability models (BLEU Papineni et al. [2002] for machine translation, and
ROUGE Lin [2004] for document summarization). These metrics use n-gram
matching at the utterance level to evaluate similarity of two texts, and are
under challenge when serving as performance metrics for tasks that require
semantic-level paraphrase matching. To demonstrate that the performance gains
by replacing softmax probabilities with dual probabilities are not a result of
the flaw of these metrics themselves, we evaluate using a neural-network based
metric called COMET Rei et al. [2020], which was recently proposed as an
alternative to the traditional “heuristic”-based metrics. As shown in Table
LABEL:tab:comet, the trend is quite similar to what we observed in the
previous experimentation sections, that the dual probability significantly
boosts the COMET score of probability sampling and beam search with large
beam, compared with the performance when using the softmax probability.

Table 2: COMET scores of the dual probability model compared with the softmax
probability model.

|  WMT’14 en$\rightarrow$de |  WMT’17 zh$\rightarrow$en | CNN / DailyMail
---|---|---|---
| sampling | $|\text{beam}|=1024$ | sampling | $|\text{beam}|=1024$ | sampling | $|\text{beam}|=1024$
Softmax Probability | 0.38 | 0.53 | 0.59 | 0.64 | 0.45 | 0.52
Dual Probability | 0.67 | 0.72 | 0.76 | 0.78 | 0.60 | 0.61
| (+0.29) |  (+ 0.19) |  (+ 0.17) | (+ 0.14) | (+ 0.15) | (+ 0.09)
Greedy | 0.71 | 0.79 | 0.62

###  G.5 Estimating The Performance of Expected Outputs

Accurately benchmarking human’s performance is important for us to calibrate
our understanding and expectation on the results from AI systems. To fairly
evaluate the quality of human translation, it is important that we use
_independent_ samples of the “actual human translation” $A$ and of the
“expected human translation” $Y$ to calculate the BLEU scores. However, the
standard WMT dataset only provide a single reference translation for each
source sentence, in which case $A$ and $Y$ are strongly coupled and would
always lead to a BLEU of strictly 100, which over-estimated the human
performance. Fortunately, Ott et al. [2018] released a dataset which provides
ten human translations (per source sentence) for 500 instances in the WMT’14
en$\rightarrow$de test set. See Table 3 for an example of the multi-reference
data. For WMT’17 zh$\rightarrow$en, the CWMT2008 datasetZhao et al. [2009]
provides a multi-reference data for Chinese$\rightarrow$English news
translation in which each source sentence is attached with four human
translations. We used these multi-reference datasets to measure the task score
of expected output (i.e. human translation) in Figure 5 and 8.

Specifically, for each source sentence
$\boldsymbol{x}^{\scriptscriptstyle(i)}$ in the multi-reference dataset, we
randomly sampled a human translation as the expected output
$\boldsymbol{y}^{\scriptscriptstyle(i)}$, then randomly sampled (with
replacement) another human translation as the actual output
$\boldsymbol{a}^{\scriptscriptstyle(i)}$. The (independently) sampled expected
and actual outputs for the whole corpus are then fed to the SacreBLEU script
to compute a BLEU score. This process was repeated for 50 times to guarantee
statistical significance. For English$\rightarrow$German translation, the mean
corpus-BLEU score of human translations is 42.54 (95% confidence interval:
42.15 - 42.93) For Chinese$\rightarrow$English translation, the mean corpus-
BLEU score is 41.82 (95% confidence interval: 41.43 - 42.20).

For the CNN/DailyMail summarization task, we did not find multi-reference
dataset, thus simply marked 100 for human outputs.

Table 3: An example of multi-reference translations for WMT’14 en2de. Source
is the source sentence #1 in the dataset, Target is the official translation
in _newstest2014_ , and Reference1-10 are the additional translations provided
by Ott et al. [2018]. [Source]: Orlando Bloom and Miranda Kerr still love each
other
---
[Target]: Orlando Bloom und Miranda Kerr lieben sich noch immer
[Reference1]: Orlando Bloom und Miranda Kerr lieben sich noch
[Reference2]: Orlando Bloom und Miranda Kerr lieben sich immer noch .
[Reference3]: Orlando Bloom und Miranda Kerr lieben sich noch immer .
[Reference4]: Orlando Bloom und Miranda Kerr lieben sich immer noch .
[Reference5]: Orlando Bloom und Miranda Kerr lieben einander immer noch
[Reference6]: Orlando Bloom und Miranda Kerr lieben einander immer noch
[Reference7]: Orlando Bloom und Miranda Kerr lieben sich immer noch
[Reference8]: Orlando Bloom und Miranda Kerr lieben sich immer noch
[Reference9]: Orlando Bloom und Miranda Kerr lieben sich immer noch
[Reference10]: Orlando Bloom und Miranda Kerr lieben sich noch immer .

###  G.6 Reproducibility and Source Code

We provided our research source code in supplementary material to facilitate
reproducibility. The README.md file gives detailed instructions to run

  * $\bullet$

Experiment1 (Figure 2, 7, 10, 13): train a model with MABE($\lambda$) losses
and with the label-smoothed MLE loss

  * $\bullet$

Experiment2 (Figure 1, 5, 8, 11): run different decision rules based on the
learned softmax probability model

  * $\bullet$

Experiment3 (Table 1, Figure 6, 9, 12): run the same set of decision rules
based on the learned dual probability model

on all the three tasks as discussed above: WMT’14 en2de, WMT’17 zh2en, and
CNN/DailyMail.

The entire experimentation pipeline is fully de-randomized once the random
seed is specified. It takes roughly 240 hours to run the full experiment
pipeline with one seed, on an A100 GPU. In total, the multi-seed experiment
results presented in the paper take about 800 GPU hours (for A100).

Finally, as an implementation trick to conveniently compute the covariance
term (10) with automatic differentiation library (e.g. pytorch), we utilized
the equation (18) in Section F.1, which gives

$\displaystyle\underset{\scriptscriptstyle A_{t}\sim
P_{t}({\boldsymbol{w}})}{\mathbf{cov}}\Big{[}Q_{t}(A_{t};{\boldsymbol{w}})~{},~{}\nabla_{{\boldsymbol{w}}}Q_{t}(A_{t};{\boldsymbol{w}})\Big{]}~{}~{}\Big{|}_{{\boldsymbol{w}}={\boldsymbol{w}}^{+}}$
(24) $\displaystyle=~{}$
$\displaystyle\sum_{a}P_{t}(a;{\boldsymbol{w}})~{}Q_{t}(a;{\boldsymbol{w}})~{}\Big{(}~{}\nabla_{{\boldsymbol{w}}}Q_{t}(a;{\boldsymbol{w}})-\sum_{b}P_{t}(b;{\boldsymbol{w}})\nabla_{{\boldsymbol{w}}}Q_{t}(b;{\boldsymbol{w}})~{}\Big{)}~{}~{}\Big{|}_{{\boldsymbol{w}}={\boldsymbol{w}}^{+}}$
$\displaystyle=~{}$
$\displaystyle\sum_{a}P_{t}(a;{\boldsymbol{w}}^{+})~{}Q_{t}(a;{\boldsymbol{w}}^{+})~{}\Big{(}~{}\nabla_{{\boldsymbol{w}}}Q_{t}(a;{\boldsymbol{w}})-\sum_{b}P_{t}(b;{\boldsymbol{w}}^{+})\nabla_{{\boldsymbol{w}}}Q_{t}(b;{\boldsymbol{w}})~{}\Big{)}~{}~{}\Big{|}_{{\boldsymbol{w}}={\boldsymbol{w}}^{+}}$
$\displaystyle=~{}$
$\displaystyle\nabla_{{\boldsymbol{w}}}\Bigg{(}~{}\underline{\sum_{a}P_{t}(a;{\boldsymbol{w}}^{+})~{}Q_{t}(a;{\boldsymbol{w}}^{+})~{}\Big{(}~{}Q_{t}(a;{\boldsymbol{w}})-\sum_{b}P_{t}(b;{\boldsymbol{w}}^{+})Q_{t}(b;{\boldsymbol{w}})~{}\Big{)}}~{}\Bigg{)}~{}~{}\Big{|}_{{\boldsymbol{w}}={\boldsymbol{w}}^{+}}$
(25)

So, in our pytorch-based implementation, we first compute the function in (25)
(the part highlighted by the underline), scale it by $\lambda$ and add to the
$J_{\text{MABE}}$ function, then perform back-propagation over the composite
loss, which will give the MABE($\lambda$) gradient as prescribed in Algorithm
1, due to (25).

##  Appendix H Limitations and Future Works

In this section we discuss limitations of the current work, as well as the
opportunities for future works.

First of all, the current paper focuses on studying a foundation of machine
learning, and specifically, seeking to challenge and improve a widely-held
_mindset_ on a widely-used training procedure in machine learning.
Consequently, this paper is largely a theory paper (where the theory is
defended not by pure mathematics but by a combination of mathematical _and_
experimental evidences). The primary goal here is thus not to propose new
algorithms that immediately give empirical gains.

However, we believe our utility-based theory implies many opportunities to
invent such new algorithms in the future. One direction is to investigate
deeper into the MABE($\lambda$) algorithm family. In our experiments, we see
that the commonly used MABE(1) (a.k.a. MLE) is usually not the best-performing
variant in this family, and the unperturbed variant MABE(0) often performs
slightly better (e.g. compare the two in Figure 7, 10, and 13). The
MABE($\lambda$) algorithms presented in this paper are in the “vanilla
version”, without tricks such as label smoothing; the hyperparameters are set
to the optimal setting for the MLE baseline (because our goal is not to beat
it but to subsume it). It would be interesting works to develop and fine-tune
the MABE($\lambda$) into a more fully-fledged solution.

The dual probability formula (13) employed a simple heuristic way to “adjust”
the probability predictions – by first clipping to $[0,1]$ then normalizing
the sum. As the choice here is somewhat arbitrary, it is possible that this
adjustment could distort the probability predictions (with the payoff of
preserving the axiom of probability). Note that such adjustment is only needed
because the Q-values are not perfectly learned. Further investigation on the
best way to refine the dual probability prediction here can be an interesting
future work.

We also note that the beam search with beam size $=1024$ in our experiment
would take much longer time than greedy decoding (50x for translation and 150x
for summarization) – it is clear that beam search is a bottleneck if we
seriously want to explore the combinatorial solution space – previously such
exploration is not meaningful given the pathological behavior of traditional
softmax probability. It would be interesting to see if more advanced search
algorithms (such as Monte Carlo Tree Search) can better utilize the dual
probability model.

Finally, there are also open questions in our value-based interpretation. For
example, one limitation of the current theory is that it cannot explain why
near-greedy outputs, such as search with a small beam size (e.g. 4) based on
the “problematic” softmax probability can slightly outperform pure greedy
outputs (although the margin is limited – e.g. $27.1$ vs $25.6$ in WMT’14
en2de – and the gain quickly disappears as the search scales up). Of course,
it would be always interesting to test our theory in more machine learning
tasks.