Can Machines Learn the True Probabilities?

Broadly speaking, probabilities can be divided into two kinds, subjective and objective ones. Subjective probability, say $\Pi(A_{t+1}|$ß${}_{t})$, depends on each person’s belief and thus possibly varies from person to person, while objective one, say $P(A_{t+1}|$ß${}_{t})$, does not.

The standard theory of subjective probability was first developed by Ramsey and then further by De Finetti and Savage. Subjective probability is designed to represent a degree of belief possessed by a subject, say some person or, if possible, a machine. Hence subjective probability represents whatever is in any one’s mind upon anything as long as his/her belief system is coherent, and so can be assigned even to what is merely imagined. For example, while arguing for cogito, ergo sum, (Descartes, 2008) imagined an evil spirit that has devoted all its efforts to deceiving him. Descartes can assign some value of subjective probability to his imagination on the evil spirit in accordance with how likely it is to him that the imagination can be realized in this world, as long as Descartes’ belief system remains coherent.

In contrast, objective probability, if any, is what must be determined by objective features of our world that do not vary from person to person. The best way to understand objective probability is to consider examples. Following (Maher, 2010), for example, suppose that a coin has the same face on both sides, that is, two-headed or two-tailed. When this coin is tossed infinitely often, its relative frequency surely converges to 1 or 0. Hence the limiting relative frequency here is either 1 or 0, depending on how our world turns out to be, which is an objective matter, and not on whatever we believe.

It should be noted that subjective and objective probabilities are conceptually bifurcated in two important ways. First, recall that subjective probability represents an aspect of someone’s subjective belief, while objective probability does not. Hence the subjective probability of Descartes’ demon is positive as long as it is believed at any degree that it could exist in our world. However, this does not necessarily imply that the true objective probability of Descartes’ demon is positive, since it might be the case that such a demon is possible only in one’s imagination but impossible in our real world. We will return to this potential bifurcation between subjective and objective probability in Section 4.1.

Second, there exists an asymmetric relation between subjective and objective probability: although the subjective probability of Descartes’ demon does not necessarily bind its objective probability, the converse holds. (e.g. (Lewis, 1980)) That is, once it is proven/assumed by any agent that the true objective probability of Descartes’ demon is, say zero, then its subjective probability of the same agent is bound to this proven/assumed result on the objective probability and thus must be zero as well. From this asymmetric relationship, we derive Lemma 4.23 in Section 4.2.

As we pointed out in Section 2, learning is the phenomenon of knowledge acquisition, and knowledge must be at least a true representation. In the case of human beings, the requirement of true representation is expressed as the requirement that (propositional) knowledge be at least a true belief (e.g. (Hintikka, 1962), (Moore, 1985)). What then is the counterpart of such a requirement for machines?

In general, if a machine achieves computational success at $t$ by learning, what the machine represents by learning must be at least true at that time. Then we denote the true representation of the machine about what is learned by the “true belief” of the machine, a legitimate analogue to the true belief of human beings. It is a belief analogue, for we haven’t yet shown that machines have minds or that they have the same kinds of mental representations as human beings. It is nevertheless a legitimate belief analogue, since the computational models of machine intelligence are based on understanding human intelligence. (e.g. (Pearl, 2018), (Russell, 1998), (Valiant, 1984, 2008))

That said, let us discuss the relation between belief and learning on the machine side: the knowledge acquired by machine learning must be at least a true belief. In (Hintikka, 1962), the knowledge of a person $i$ refers to the knowledge of that person $i$ on any proposition $A$. Likewise, machine’s learning of the true objective probability $P$ here refers to the knowledge acquired by any machine on the probabilistic proposition $A_{p}$. If a machine learns the true probability as $\alpha$, then the probabilistic proposition $A_{p}$ amounts to that the true objective probability $P,$ if any, is what the very machine calculates as $\alpha$. Here, we convert the non-propositional learning into propositional learning.

Now, just as a person $i$’s knowledge on proposition $A$ must satisfy the necessary condition that the person $i$’s belief in $A$ is true, machine learning of the true probability $P$ must also satisfy the condition that the belief in $A_{p}$ of the machine is true. Note here that such a belief in $A_{p}$ is true when what has been calculated by the machine is indeed equal to the true probability $P$. Now, this calculated probability function by a machine is nothing more than the subjective probability of the machine. Therefore, the necessary condition for machine learning of true probability $P$ requires a machine to hold a true belief whose truth condition is satisfied when its subjective probability is, in fact, in congruence with the true objective probability $P$. In short, if a machine learns the true objective probability $P$, then the subjective probability $\Pi$ of the machine is actually equal to the true probability $P$.

Therefore, we obtain the following condition:

The Necessary Condition for any Machine to Learn the True Probability

(2) If a machine learns the true objective probability $P(A_{t+1}|$ß${}_{t})$, then $\Pi(A_{t+1}|$ß${}_{t})=P(A_{t+1}|$ß${}_{t})$

where $\Pi(A_{t+1}|$ß${}_{t})$ denotes the subjective probability of the machine at time $t$.

We assume, without loss of generality, that the event $A_{t+1}$ is an elementary event, for simplicity. So the event $A_{t+1}$ is a singleton, i.e. $\{\omega_{t+1}\}$.

Two things should be noted from (2): first, learning/knowledge is not necessarily equivalent to obtaining true fact that $\Pi(A_{t+1}|$ß${}_{t})=P(A_{t+1}|$ß${}_{t})$, as the converse of condition (2) does not necessarily hold. Second, if a machine is wrong in calculating the true probability at time $t$ so that $\Pi(A_{t+1}|$ß${}_{t})\neq P(A_{t+1}|$ß${}_{t})$, then by modus tollens we can derive from (2) that the machine does not learn it at that time. However, this does not preclude the machine from learning it at any other time. Then what can be said about learnability in general? According to the Success Criterion (1), a machine cannot learn any target function if it is wrong most of the time, except for a few finite cases out of infinite opportunities to learn. But can a machine be said to learn if it is correct infinitely often but also wrong as that often? We give a negative answer to this question by proving theorems in Section 4.2.

Let us start with a simple example in which a machine is trying to learn the true probability that it will rain tomorrow. A forecasting system is said to be well-calibrated if it assigns probability, say 30%, to rainy events in a test set whose long-term proportion that actually rains is 30%. According to (Dawid, 1982), a forecasting machine is self-assured that its fairly arbitrary test set of forecasts is well-calibrated. This is Theorem 4.1. In addition, we prove in Theorem 4.6 that if the machine learns the true probability, then this machine’s forecasting is truly guaranteed to be well-calibrated.

Now, let us assume that a machine has its own (not necessarily true in our context) probability distribution $\Pi$ defined over ß${}_{\infty}={\textstyle\bigvee\limits_{t=0}^{\infty}}\text{\ss}_{t},$ where ß_t is denoted by the totality of the true facts up to day $t$. The probability forecasts $\Pi(A_{t+1}|\text{\ss}_{t})$ it makes on day $t$ are for events $A_{t+1}$’s in ß_t+1 and are ß_t-measurable. For each day $t$ we have an arbitrary associated event $A_{t}\in$ ß_t, say the event of raining on day $t$. We denote the indicator of $A_{t+1}$ by $Y_{t+1}=1_{\{A_{t+1}\}}$, and introduce $\hat{Y}_{t+1}=\Pi(A_{t+1}|$ß${}_{t})$, the probabilistic forecast of machines on day $t$+1. In addition, we introduce the new indicator variables $\xi_{1},\xi_{2},\ldots,$ at choice to denote the inclusion of any particular day $t$ in the test set where $\xi_{t}=1$ if the day $t$ is included in the test set and $\xi_{t}=0$ otherwise. Now, if we set the selection criterion to include any day into the test set as the assessed probability $\alpha$ on day $t$, then we have the following theorem.

Here, let us use the terms as follows: machine forecasts are self-assured to be well-calibrated when $\Pi$ $(p_{k}\rightarrow$ $\alpha)=1$, while those are truly guaranteed to be so when $P$ $(p_{k}\rightarrow$ $\alpha)=1$. It should be noted then that even if the forecasting machine is self-assured to be well-calibrated, this does not necessarily imply that its forecasts are truly guaranteed to be well-calibrated. Recall from Section 3.1 that there is a conceptual bifurcation between subjective and objective probability.

Now, suppose that a machine tries to learn the true probability of a particular event $A_{t+1}$. If this machine indeed learns the true probability of the event as $\alpha$, then the machine should correctly calculate the true probability of the same events repeatedly as $\alpha$ most of the time. Hence, the machine can construct a test set of those associated events $A_{t+1}$’s whose sequentially correct probabilities are $\alpha$. Then we can show further from Theorem 4.1 that the test set will be well-calibrated with true probability $P$- one. This is Theorem 4.6. In short, here “being correct as $\alpha$” itself serves as what (Dawid, 1982) calls a selection criterion.

However, note that if the size of ß_t continues to grow as $t$ goes to infinity, then ß_t’s might be different for each $t.$ Then $P(A_{t+1}|\text{\ss}_{t})$ might not stay the same as $\alpha$ even for the same events $A_{t+1}$’s across infinitely many $t$’s. Now, in order for the correct probability $\alpha$ to work as a selection criterion, it should be that $P(A_{t+1}|\text{\ss}_{t})$ stays the same as $\alpha$ at least for infinitely many $t$’s even though ß_t may vary as time passes. Therefore, we prove Lemma 4.5 from the following three assumptions. The justifications for the three assumptions are provided in Appendix C.

It should be noted from 4.2 and 4.3 that if ß_t is the set of known facts, the information on the associated events $E_{t}$’s in ß_t’s may not be independent of one another over time. Once $E_{t}$ has been known in the past at some time $t_{0},$ the same events $E_{t}$’s are more likely to be known afterwards. Repeatedly accumulated knowledge of the same events reinforces the probability that the very event will be known again in the future. However, this is not necessarily the case with the set of true facts. It will be clear in Lemma 4.5 why this independence condition matters.

Now that Lemma 4.5 has been established, $P(A_{t+1}|$ß${}_{t})$ is truly guaranteed to stay as $\alpha$ infinitely often, and thus the machine has infinite opportunities to learn $P(A_{t+1}|$ß${}_{t})$ as $\alpha$.

It should be noted that the notion of learning in Theorem 4.6 is flexible enough to allow for some finitely few potential errors, so that there can exist some $t^{\ast}<\infty$ such that $P(A_{t+1}|$ß${}_{t})\neq\alpha$ $\forall t<t^{\ast}$ while processing the data to learn.

The basic idea in the proof of Theorem 4.8 starts with constructing a counterexample in which the true probability function $P$ is deviated infinitely often from the subjective probability function $\Pi$ in such a way that the well-calibration property does not hold any longer.

Counterexample 1 Following (Oakes, 1985), let $P$ be such as $P(A_{t}|$ß${}_{t-1})=f(\Pi(A_{t}|\text{\ss}_{t-1})),$ with the function $f([0,1])\rightarrow[0,1]$ being defined by $f(x)=x+\frac{1}{2}$ $(0\leq x\leq\frac{1}{2}),$ $f(x)=1-x$ $(\frac{1}{2}<x\leq 1)$ for any event $A_{t}.$ Then, under $P$ with $P(Y_{I_{k}}=1)=f(\alpha)$ where $\hat{Y}_{t}=$ $\alpha$ for a subsequence $\{t:t=I_{1},I_{2},\ldots\}$ and $Y_{I_{k}}$’s form a Bernoulli sequence, the well-calibration property does not hold.

Due to this counterexample from (Oakes, 1985), the machine forecaster cannot exclude the possibility that its test set may be mis-calibrated, and thus the machine cannot hold its subjective probability $\Pi$- one of being well-calibrated. Furthermore, if this artificially-imagined possibility of mis-calibration is a real possibility, then it is derived that no test set large enough can be guaranteed to be well-calibrated with the true probability $P$- one. Later in this section, we prove that if such an imagined possibility is a real one, then machines cannot learn. Meanwhile, we also prove mathematically how the (Oakes, 1985) Counterexample paralyzes Dawid’s Theorem 4.1, which amounts to the proof of Theorem 4.8.

By “at least i.o.” in Definition 4.13, we mean that Nature deviates from $\alpha$ either (i) infinitely often or (ii) all but finitely often along the stochastic path of the test set. Thus, we clearly distinguish (i) from (ii). From now on, we mean by “infinitely often” that nature not only deviates infinitely often, but also does not deviate infinitely often. On the other hand, by “all but finitely often” we mean as usual. Then, if the true probability of Nature’s perversity is zero, then we denote it by $P(P(A_{t+1}|$ß${}_{t})\neq\alpha$ at least $i.o.$ along the path of the test set$)=0$, which amounts to $P(P(A_{t+1}|$ß${}_{t})\neq\alpha$ at most for $t<\infty$ along the path of the test set$)=1$. Furthermore, if there is no confusion, we will simplify Nature’s perversity by “$P(A_{t+1}|$ß${}_{t})\neq\alpha$ at least $i.o.$” while omitting “along the path of the test set.”

Now, according to the Success Criterion (1), a machine fails to learn the true probability in case (ii), because the machine then makes wrong forecasts along the path except for a finite few of the infinite opportunities to learn. However, it seems unclear whether the machine can learn or not in case (i). On the one hand, the machine seems not to be able to learn because it makes too many errors, say infinitely many errors. On the other hand, it seems that the machine should be able to learn because it makes astronomically many correct forecasts, say infinitely often. Therefore, while adopting this definition, we clearly prove by Theorem 4.20 and Corollary 4.30 that a machine cannot learn the true probability even when it is correct infinitely often, if it is wrong that often.

Observation Provided that the machine forecast $\Pi(A_{t+1}|$ß${}_{t})$ is fixed as some value $\alpha\in\Re[0,1]$, $P($ $\Delta_{t}$ $)$ becomes the true second-order probability on the true first-order probability of such event $A_{t+1}$, that is, $P($ $\Delta_{t}$ $)$ = $P$ $\left(\text{ }P(A_{t+1}|\text{\ss}_{t})=\alpha\text{ }\right)$ where $\Delta_{t}$ denotes the event that the machine makes a correct forecast at $t$.

It should be noted here that the computable numbers by a machine are countably many (e.g. (Turing, 1936)). Thus, the true second-order probability $P$ here is a probability mass function on countable space and therefore satisfies the Kolmogorov axioms, although $\alpha$ may potentially be any real number in $\Re[0,1].$

There are various theories of learning in games. (e.g. (Nisan et al., 2007)) Therefore, what matters is what is aimed to learn through games and who are competing with each other in the games. In the standard model, a machine aims to learn what the optimal actions are to produce the minimized expected (total) loss or payoff, which is determined in a given environment, say financial market. In this case, a machine usually competes with other machines in the game. For example, in some online learning, a machine aims to learn a sequence of estimates which return the sub-linear regret, given that the loss functions are convex. It gets a possibly different amount of payoff/loss at each round of games along the stochastic path where the given sequence of games are played.

In our forecasting games, on the other hand, a machine aims to learn the true objective probability, if any, through games, and so the machine is competing with Nature in the game. Also, whoever wins a game, the winner/loser will get uniform payoff at every round along the path, for what counts is how many times the machine loses/wins along the path, not how much payoff it gets at each round along the path once it loses/wins.

Thus, winning strategy is not equivalent to learning strategy. Now, in case when a machine does not learn that it wins/loses a game even though it indeed does so, it does not matter what it gets as payoff when it wins/loses because it cannot learn how much it gets at each round. What matters, on the contrary, is how many times it wins along the path, and this is why our game setting in Lemma 4.15 adopts a uniform payoff at each round.

Regarding Theorem 4.17, it is worth noting the following three things: (i) $($Case 1$)$ is equivalent to the strong law of large numbers under a weaker assumption than i.i.d.: if the true probability $P(A_{t+1}|$ß${}_{t})$ exists and $P(A_{t+1}|$ß${}_{t})$ is identically distributed as $\alpha$ all but finitely often along the path, then the limiting relative frequency converges to the same $P(A_{t+1}|$ß${}_{t})$ as $\alpha$ with true probability $P$- one. (ii) $($Case 2$)$ shows that if (Oakes, 1985) holds with $\Pi-$subjective probability $>0$, then (Dawid, 1982) does not hold, which amounts to the proof of Theorem 4.8. (iii) $($Case 3$)$ shows, combined with Theorem 4.6, that if $P$$(P(A_{t+1}|$ß${}_{t})\neq\alpha$ at most $f.o.$ along the test set$)\neq 1$, then a machine cannot learn the true probability $P(A_{t+1}|$ß${}_{t})$ as $\alpha$. Thus, the third result (iii) has the following important implication for time-series analysis: a machine cannot relax the assumption that the true probability $P(A_{t+1}|$ß${}_{t})$ is identically distributed along the stochastic path, if the machine aims to learn the true probability $P(A_{t+1}|$ß${}_{t})$. To learn, the machine needs some identical distributional assumptions such as stationarity or ergodicity.

In other words, when Nature deviates from forecasters for any event $A_{t+1}$, she does not discriminate against some forecasters in favor of the others whose forecasts $\alpha$ Nature decides to conform to all but finitely often for sure.

Now, let us discuss what it means in Theorem 4.20 by the condition that the true second-order probability is strictly less than 1. Note from Lemma 4.15 that $P$ $\left(P(A_{t+1}|\text{\ss}_{t})=\alpha\right)=1$ if and only if Nature moves first and then the machine moves later after observing what move Nature takes in the forecasting game at time $t$. Thus, it is clear from the condition of Theorem 4.20 why and when the machine fails to learn the true probability if Nature is uniformly perverse: when the machine cannot move later after observing the true move of Nature infinitely often, there always exists a real possibility that the machine may not be able to match Nature’s move that often. Hence the machine cannot be truly guaranteed to be well-calibrated, which again implies the impossibility of machine learning. Since the machine cannot observe the true move of Nature in those forecasting games, the true probability is unobservable by the machine.

So far we have shown that it is of real possibility that Nature is perverse, and thus that no machines can learn the true objective probability. Now someone might argue that its proof holds only under the condition that Nature is uniformly perverse. Nature may not be uniformly perverse, however, but only selectively perverse, so that, for some forecast $\alpha_{0}$, Nature may decide to be benevolent enough to conform to that $\alpha_{0}$. Then it may be the case that the true probability of Nature being perverse is zero for this $\alpha_{0}$, and accordingly that machines may be given an opportunity to learn the true objective probability for that $\alpha_{0}$.

Note, however, that it is entirely Nature’s decision when she will be benevolent to a machine and when she will not. Therefore, it is still a random event to the machine whether Nature is perverse or not. If so, we will show further that, even if the true probability of Nature’s being perverse is zero with some $\alpha_{0},$ a machine still cannot learn the true probability if it cannot learn which forecast is the right $\alpha_{0}$ for any event $A_{t+1}$.

Now, let us define Nature’s decision to be selectively perverse at $t$ to show by Lemma 4.28 that once Nature decides so at $t$, our real world remains as such.

Note that $t_{s}$ is ß_t-measurable, because ß_t includes all the true facts up to $t$ and so whatever Nature decides at $t$, say the event $\{P(A_{\alpha_{0}}(t+1)|$ß${}_{t})=0\}$ belongs to the set of true facts, ß_t.

Note that along the stochastic path considered in Corollary 4.30, $P(P(A_{t+1}|$ß${}_{t})\neq\alpha_{0}$ at least $i.o.)=0$ $\forall t>t_{s}$. Now, for this $\alpha_{0}$,

(3)     $\limsup\limits_{t\rightarrow\infty}$ $P(P(A_{t+1}|$ß${}_{t})\neq\alpha_{0})\leq P(P(A_{t+1}|$ß${}_{t})\neq\alpha_{0}$ at least $i.o)=0$

Therefore, without loss of generality, letting $t^{\ast}\geq t_{s}$ with $t^{\ast}<\infty$,

(4)     $P(P(A_{t+1}|$ß${}_{t})=\alpha_{0})=1,$ $\forall t>t^{\ast}\geq t_{s}$ with $t^{\ast}<\infty$.

Now, (4) means by Lemma 4.15 that the true probability is observable at any time $t>t^{\ast}$ along this path. Then why is the machine still unable to learn the true probability, even though the machine can move after observing what move Nature takes at the forecasting games all along that path after $t^{\ast}$? According to Corollary 4.30, this is because the machine cannot be self-assured whether the true probability will remain observable at any time after $t^{\ast}$+1 onward, even if the machine observes Nature’s true move at time $t^{\ast}$+1. Let us show this by the following Lemma 4.31.

From Theorem 4.20 and Corollary 4.30, we conclude that the impossibility of learning is derived under the assumption either that Nature is uniformly perverse or that Nature is selectively perverse but a machine is not self-assured of whether the stopping time arrives or not. What would then happen in the case where Nature is selectively perverse and a machine is self-assured of the stopping time $t_{s}$ when the $t_{s}$ indeed exists? We show in the following that a machine can learn the true probability in this case, and further that this is the only case in which a machine can learn it.

Let us now define when the true probability is directly observable based on the notion of population. The concept of population in Definition 4.34 is mainly indebted to (von Mises, 1957, 1967). Since the true probability is defined as the empirical distribution of this population available to a machine, the probability is said to be directly observable by the machine.

Now, in case where the sequence $\{A_{t+1}\}_{t=0}^{k-1}$ is a time-series, Definition 4.34 means that $\Pi$$(A_{t^{\ast}+1}|$ß${}_{t^{\ast}})=\frac{1}{k}\sum\limits_{t=0}^{k-1}1_{\{A_{t+1}\}}=P$$(A_{t^{\ast}+1}|$ß${}_{t^{\ast}})$ with $k=t^{\ast}$. Thus, when $t^{\ast}$ goes to infinity, the directly observable true probability becomes the limiting relative frequency, the representative objective true probability.

Two things should be noted from Theorem 4.36. First, whenever the true probability is not directly observable, a machine cannot learn the true probability. Now recall from Definition 2.1 that the machine is an ideal one with no practical limits on computational resources such as time or storage spaces. Therefore, this implies that no real machines, hindered by many practical limits in our world, can overcome this impossibility of learning either, whenever the true probability is not directly observable. Second, Theorem 4.36 also says that the true probability is directly observable by a machine whenever it can learn the true probability. Once a machine learns the true probability and so it is successfully computable, then the next question is how complex it is to compute. Now that the true probability is directly observable, this makes it easier to deal with the complexity problem. (e.g. Sorting algorithm) Thus, Theorem 4.36 directly connects the problem of computational solvability to the problem of complexity.

Now, let us finish this section by adding one more claim that the Success Criterion (1) to compute the true probability is sufficient for learning it.