Utility-Probability Duality of Neural Networks
It is typically understood that the training of modern neural networks is a
process of fitting the probability distribution of desired output. However,
recent paradoxical observations in a number of language generation tasks let
one wonder if this canonical probability-based explanation can really account
for the empirical success of deep learning. 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 that
encodes the preference revealed in training data. In this perspective, training
of the neural network corresponds to a utility learning process. Specifically,
we show that for all neural networks with softmax outputs, the SGD learning
dynamic of maximum likelihood estimation (MLE) can be seen as an iteration
process that optimizes the neural network toward an optimal utility function.
This utility-based interpretation can explain several otherwise-paradoxical
observations about the neural networks thus trained. Moreover, our
utility-based theory also entails an equation that can transform the learned
utility values back to a new kind of probability estimation with which
probability-compatible decision rules enjoy dramatic (double-digits)
performance improvements. These evidences collectively reveal a phenomenon of
utility-probability duality in terms of what modern neural networks are (truly)
modeling: We thought they are one thing (probabilities), until the
unexplainable showed up; changing mindset and treating them as another thing
(utility values) largely reconcile the theory, despite remaining subtleties
regarding its original (probabilistic) identity.
Huang Bojun, Fei Yuan
# Utility-Probability Duality of Neural Networks

###### 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(\mathbf{w})\) as a parametric model of the conditional probability distribution \(\mathbf{P}_{\mathbf{w}}[Y=\mathbf{y}|X=\mathbf{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(\mathbf{w})\) is then _thought_ to be the process of approximating \(\mathbf{P}_{\text{true}}\) with \(\mathbf{P}_{\mathbf{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}_{\mathbf{w}}\) at inference time. The first way is to choose the most likely output in \(\mathbf{P}_{\mathbf{w}}\):

\[\mathbf{y}_{\text{MAP}}\doteq\operatorname*{arg\,max}_{\mathbf{y}}\,\mathbf{P}_{\mathbf{ w}}[Y=\mathbf{y}|X=\mathbf{x}] \tag{1}\]

where MAP stands for _maximum a-posteriori probability_. When \(\mathbf{P}_{\mathbf{w}}=\mathbf{P}_{\text{true}}\), \(\mathbf{y}_{\text{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}_{\mathbf{w}}\), which makes the **actual output** a random variable, denoted by \(A\) here:

\[A\sim\mathbf{P}_{\mathbf{w}}[Y=\cdot|X=\mathbf{x}] \tag{2}\]

When \(\mathbf{P}_{\mathbf{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 2: 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}_{\mathbf{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}_{\mathbf{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=\mathbf{y}_{\text{MAP}}\) and the sampling rule \(A\sim\mathbf{P}_{\mathbf{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).
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.

### The Expectations

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

\[\mathbf{P}_{\mathbf{w}}[\mathbf{y}|\mathbf{x}]=\prod_{t}\mathbf{P}_{\mathbf{w}}[y_{t}|\mathbf{x}, \mathbf{y}_{<t}]=\prod_{t}f_{[y_{t}]}(\mathbf{x},\mathbf{y}_{<t};\mathbf{w}). \tag{3}\]

By substituting (3) into (1) and (2), we _can_ effectively maximize or sample \(\mathbf{P}_{\mathbf{w}}\) using the neural network \(f(\mathbf{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 \(\mathbf{y}\) where each token \(y_{t}\) is a greedy decision that _locally_ maximizes the token-wise probability given the auto-regressive context:

\[\mathbf{y}_{\text{greedy}}\doteq(y_{1}\ldots y_{\tau})\;\;\text{where}\;\;y_{t}= \arg\max_{a}\;\mathbf{P}_{\mathbf{w}}[a|\mathbf{x},\mathbf{y}_{<t}] \tag{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.

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

(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). 3 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}\)).

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

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

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.
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)\).

### 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 \(\{\mathbf{x}^{(i)},\mathbf{y}^{(i)}\}_{i=1..n}\) with \(\mathbf{y}^{(i)}\sim\mathbf{P}_{\text{true}}[Y|X=\mathbf{x}^{(i)}]\), then we update the model parameters \(\mathbf{w}\) toward the ones that maximize the (log-)probability of the data in \(\mathbf{P}_{\mathbf{w}}\):

\[\mathbf{w}_{\text{MLE}}=\arg\max_{\mathbf{w}}\ \log\mathbf{P}_{\mathbf{w}}[\{\mathbf{y}^{(1..n )}\}|\{\mathbf{x}^{(1..n)}\}]=\arg\max_{\mathbf{w}}\ \sum_{i=1}^{n}\sum_{t=1}^{T_{i}}\log f_{[y^{(i)}_{t}]}(\mathbf{x}^{(i)},\mathbf{y}^{ (i)}_{<t};\mathbf{w}) \tag{5}\]

where the neural network \(f\) models a softmax distribution

\[f_{[y_{t}]}(\mathbf{x},\mathbf{y}_{<t};\mathbf{w})=e^{Q_{[y_{t}]}(\mathbf{x},\mathbf{y}_{<t};\mathbf{ w})}/\sum_{a}e^{Q_{[a]}(\mathbf{x},\mathbf{y}_{<t};\mathbf{w})} \tag{6}\]

over the so-called _logit_ vector \(Q(\mathbf{x},\mathbf{y}_{<t};\mathbf{w})\). The training of \(f(\mathbf{w})\) follows a learning dynamic driven by the gradient of the MLE objective (5). 4 This gradient can be conveniently computed by substituting (6) into (5), yielding

Footnote 4: See Appendix C for how (5) corresponds _exactly_ to the NLP practice in real world.

\[\nabla_{\mathbf{w}}\log\mathbf{P}_{\mathbf{w}}[y_{i}|\mathbf{x},\mathbf{y}_{<t}] = \nabla_{\mathbf{w}}Q_{[y_{t}]}(\mathbf{w})-\nabla_{\mathbf{w}}\text{LogSumExp} \Big{(}Q(\mathbf{w})\Big{)} \tag{7}\] \[= \nabla_{\mathbf{w}}Q_{[y_{t}]}(\mathbf{w})-\sum_{a}\ f_{[a]}(\mathbf{w})\ \nabla_{\mathbf{w}}Q_{[a]}(\mathbf{w})\]

where \(\text{LogSumExp}(Q)\doteq\log\sum_{a}\exp(Q_{[a]})\), and we have omitted \((\mathbf{x},\mathbf{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}_{\mathbf{w}}\) through manipulating \(Q(\mathbf{w})\), we can reversely interpret it as a method to implement a learning dynamic of \(Q(\mathbf{w})\) through manipulating \(\mathbf{P}_{\mathbf{w}}\). In this alternative perspective, we iterate the function \(Q\)5 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}_{\mathbf{w}}\) and the iteration of \(Q(\mathbf{w})\) can be considered _dual process_ to each other that are taking place in parallel, in a learning dynamic conventionally named "MLE training".

Footnote 5: 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.

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:

\[\mathbf{y}_{\text{greedy}}=(y_{1\dots T})\;,\;y_{t}=\arg\max_{a}\;Q_{[a]}(\mathbf{x}, \mathbf{y}_{<t};\mathbf{w}) \tag{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_{\mathbf{w}}\) cannot be re-arranged to the head because of the \(f_{[a]}(\mathbf{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_{\mathbf{w}}\) to the head of (7) anyway, making it "approximately" the gradient of the following objective function:

\[J_{\text{MABE}}(\mathbf{w},\mathbf{x},\mathbf{y}) \doteq\sum_{t=1}^{T}\;\Big{(}\;Q(y_{i}|\mathbf{x},\mathbf{y}_{<t};\mathbf{w}) -\sum_{a}f(a|\mathbf{x},\mathbf{y}_{<t};\mathbf{w})Q(a|\mathbf{x},\mathbf{y}_{<t};\mathbf{w})\;\Big{)}\] \[=\sum_{t=1}^{T}\;\Big{(}\;Q(y_{i}|\mathbf{x},\mathbf{y}_{<t};\mathbf{w})- \underset{A_{t}\sim\mathbf{P}_{\mathbf{w}}}{\mathbf{E}}\;\Big{[}Q(A_{t}|\mathbf{x},\bm {y}_{<t};\mathbf{w})\Big{]}\;\Big{)} \tag{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 \(\mathbf{x},\mathbf{y}_{<t}\), for each step \(t\)). The subscript MABE stands for Maximum Advantage over Boltzmann Exploration.

From (7) to (9), we have (naively) understood the log-likelihood gradient \(\nabla_{\mathbf{w}}\log\mathbf{P}_{\mathbf{w}}\) as an approximation of \(\nabla_{\mathbf{w}}J_{\text{MABE}}\), with the impact of \(\partial\mathbf{w}\) over \(f(\mathbf{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 \(\mathbf{x}\), output \(\mathbf{y}=(y_{1}\ldots y_{T})\), and parametric model \(Q(\mathbf{w})\), we have_

\[\frac{\partial\log\mathbf{P}_{\mathbf{w}}[\mathbf{y}|\mathbf{x}]}{\partial w_{j}}=\frac{ \partial J_{\text{MABE}}}{\partial w_{j}}(\mathbf{w},\mathbf{x},\mathbf{y})\;+\;\sum_{t=1} ^{T}\mathbf{cov}_{t}\Big{[}Q,\frac{\partial Q}{\partial w_{j}}\Big{]}\qquad, \;\forall j\]

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

\[=\;\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{)} \tag{10}\]

* \(\mathbf{P}_{\mathbf{w}}\) _is the softmax distribution induced by_ \(Q(\mathbf{w})\) _as prescribed by (_3_) and (_6_),_
* \(P_{t}(a)\) _denotes_ \(\mathbf{P}_{\mathbf{w}}[a|\mathbf{x},\mathbf{y}_{<t}]\)_, the probability that the token at step_ \(t\) _is_ \(a\)_, according to_ \(\mathbf{P}_{\mathbf{w}}\)_._
* \(Q_{t}(a)\) _denotes_ \(Q(a|\mathbf{x},\mathbf{y}_{<t};\mathbf{w})\)_, the utility of outputting token_ \(a\) _at step_ \(t\)_, according to_ \(Q(\mathbf{w})\)_,_
* \(\frac{\partial Q_{t}}{\partial w_{j}}(a)\) _denote_ \(\frac{\partial Q}{\partial w_{j}}(a|\mathbf{x},\mathbf{y}_{<t};\mathbf{w})\)_, the partial derivative of_ \(Q(a|\mathbf{x},\mathbf{y}_{<t};\mathbf{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}_{\mathbf{w}}\). Proposition 1 asserts that the gradient of the probability-learning objective (5) differs from the gradient of the utility-learning objective (9) 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.

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;\mathbf{q})=\sum_{j=1}^{d}\mathds{1}[a=j]\cdot q_{j}\), where the parameter vector \(\mathbf{q}=(q_{1}\ldots q_{d})\) directly encodes the utilities for each possible action \(a\in\{1\ldots d\}\). Let \(\mathbf{p}=(p_{1}\ldots p_{d})\) be the softmax distribution induced by \(\mathbf{q}\). Let \(\mathbf{q}^{*}\) be the Q-values that maximizes \(J(\mathbf{q})=\mathbf{E}_{Y\sim\mathbf{P}_{\text{true}}}\ \Big{[}Q(Y;\mathbf{q})\Big{]}- \mathbf{E}_{\mathbf{A}\sim\mathbf{p}}\ \big{[}Q(A;\mathbf{q})\Big{]}\), and \(\mathbf{p}^{*}\) the softmax distribution by \(\mathbf{q}^{*}\), then_

\[\max_{a\in\operatorname{supp}(Y)}\ q_{a}^{*}\ >\ \max_{b\notin\operatorname{supp}(Y)}\ q_{b}^{*}\ \ +\ 1 \tag{11}\]

_where \(\operatorname{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}_{\mathbf{p}^{*}}[Q]\ )\ =\ \ \mathbf{P}_{\text{true}}[Y=a]\qquad,\ \forall a \tag{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(\mathbf{w})\) being ignored. The inequality (11) in Theorem 2 suggests that \(\mathbf{q}^{*}\), the global maximum of \(J\), separates desired actions from undesired ones by at least a constant margin, so going greedy with \(\mathbf{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 \(\mathbf{w}\) guarantees to find the _optimal_ Q-function 6 as long as the global maximum of \(J_{\text{MABE}}\) is covered by the parametric model \(Q(\mathbf{w})\).

Footnote 6: Recall that a Q-function is optimal if the greedy policy (8) finds optimal decisions (see Section 3).

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.
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).

## 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 \(\mathbf{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 \(\mathbf{q}=(q_{1}\ldots q_{d})\) be the Q-values predicted by a Q-function for a given decision context, define

\[p_{i}^{\text{dual}}\ =\ \text{CLIP}\Big{(}\ p_{i}\ (1+q_{i}-\mathbf{p}\cdot\mathbf{q} )\ \Big{)}\ /\ Z \tag{13}\]

where \(p_{i}=\text{softmax}_{[i]}(\mathbf{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 \(\mathbf{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 \(\mathbf{p}\)); the former "calibrates" the latter with a scaling factor \(1+q_{i}+\mathbf{p}\cdot\mathbf{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}-\mathbf{p}\cdot\mathbf{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.

\begin{table}
\begin{tabular}{l|r r|r r|r r} \hline \hline  & \multicolumn{2}{c|}{WMT’14 en\(\rightarrow\)de} & \multicolumn{2}{c|}{WMT’17 zh\(\rightarrow\)en} & \multicolumn{2}{c}{CNN / DailyMail} \\  & sampling & \(|\text{beam}|=1024\) & sampling & \(|\text{beam}|=1024\) & sampling & \(|\text{beam}|=1024\) \\ \hline 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) \\ \hline \hline \end{tabular}
\end{table}
Table 1: Dual probabilities significantly improve pure sampling and MAP (\(\pm\) gives \(90\%\) confidence interval from \(9\) trials).
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,7 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.

Footnote 7: In 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).

## 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.
