# Realising Active Inference in Variational Message Passing: the Outcome-blind
Certainty Seeker

Théophile Champion<EMAIL_ADDRESS>
University of Kent, School of Computing
Canterbury CT2 7NZ, United Kingdom Marek Grześ<EMAIL_ADDRESS>
University of Kent, School of Computing
Canterbury CT2 7NZ, United Kingdom Howard Bowman<EMAIL_ADDRESS>
University of Birmingham, School of Psychology,
Birmingham B15 2TT, United Kingdom
University of Kent, School of Computing
Canterbury CT2 7NZ, United Kingdom

###### Abstract

Active inference is a state-of-the-art framework in neuroscience that offers a
unified theory of brain function. It is also proposed as a framework for
planning in AI. Unfortunately, the complex mathematics required to create new
models — can impede application of active inference in neuroscience and AI
research. This paper addresses this problem by providing a complete
mathematical treatment of the active inference framework — in discrete time
and state spaces — and the derivation of the update equations for any new
model. We leverage the theoretical connection between active inference and
variational message passing as describe by John Winn and Christopher M. Bishop
in 2005. Since, variational message passing is a well-defined methodology for
deriving Bayesian belief update equations, this paper opens the door to
advanced generative models for active inference. We show that using a fully
factorized variational distribution simplifies the expected free energy — that
furnishes priors over policies — so that agents seek unambiguous states.
Finally, we consider future extensions that support deep tree searches for
sequential policy optimisation — based upon structure learning and belief
propagation.

Keywords: Active Inference, Variational Message Passing, Free Energy
Principle, Reinforcement Learning, Kullback Leibler Control

##  1 Introduction

The free energy principle aims to provide a unified theory of the brain based
on Bayesian probability theory (Friston, 2010; Buckley et al., 2017). It takes
root in Helmholtz’s argument that observations are produced by hidden causes
that must be inferred — and the predictive coding formulation which argues
that inference and learning emerges from the reduction of the error between
predicted and actual observations. Active inference extends predictive coding
to consider generative models of actions (Friston et al., 2016; Da Costa et
al., 2020a).

In brief, active inference is a probabilistic framework that describes how
agents should act in their environment. It starts with the definition of a
generative (probabilistic) model that encodes the agent’s beliefs about its
environment. However, active inference does not rely on one particular
generative model, instead it refers to a class of generative models that
consider the impact of their actions in their environment. Active inference
also relies on learning and inference to estimate the most likely states of
the world and values of the model parameters. However, the concept behind
active inference does not dependent on a particular inference method, which
means that both variational inference (Fox and Roberts, 2012) and Monte Carlo
Markov chains (Fountas et al., 2020) can, in principle, be used.

Active inference has been successfully applied in neuroscience to explain a
wide range of brain phenomena such as habit formation (Friston et al., 2016),
Bayesian surprise (Itti and Baldi, 2009), curiosity (Schwartenbeck et al.,
2018), and dopaminergic discharges (FitzGerald et al., 2015). Active inference
is also a form of planning as inference (Botvinick and Toussaint, 2012)
consistent with Occam’s Razor (Blumer et al., 1987) and can be seen as a
generalisation of reinforcement learning (van Hasselt et al., 2015; Lample and
Chaplot, 2016) and Kullback Leibler control (Rawlik et al., 2013). This
framework has also been used to ground active vision (Ognibene and Baldassare,
2015; Heins et al., 2020; Van de Maele et al., 2021; Mirza et al., 2016, 2018)
within a strong theoretical framework.

This paper focuses on active inference using variational (a.k.a approximate
Bayesian) inference and highlights its connection to variational message
passing (Winn and Bishop, 2005). This ubiquitous message passing algorithm
builds on the variational inference literature by leveraging the structure of
the generative model to split the update equations into messages. Those
messages transmit information about the new observations and — by summing
those messages — it is possible to compute the posterior distribution over the
parameters. The decomposition of the updates into messages formalises the
modularity of the method, while remaining biologically plausible (Friston et
al., 2017b). Indeed, a key question in machine learning and computational
neuroscience is how to identify compositional models — an issue that was
identified early in the development of connectionism (Bowman and Li, 2011;
Fodor and Pylyshyn, 1988). The central requirement being that higher-order
representations (whether syntactic, semantic, perceptual, etc) can be
constructed by “plugging together” lower order representations, in such a way
that the meanings of lower-order representations do not change (e.g. the
“Jane” in “Jane loves John” is the same “Jane” as in “John loves Jane”). It
may be that the structural modularity provided by message passing
implementations of Bayesian networks enable compositionality of
representations. According to modern trends, we use the formalism of Forney
factor graphs (Forney, 2001) to represent the updates as messages sent along
the graph edges.

Forney factor graphs are graphical representations used to realise generative
models. They comprise of two kinds of round nodes that represent the
observations and the latent variables of the model. If the notion of
observations can be understood as the data available to the model, the notion
of latent variables is a bit more abstract. As an example, let us consider the
MNIST dataset (LeCun and Cortes, 2010) composed of images of hand written
digits. In this example, the pixels are observations made by the model and
latent variables could be any variables encoding the digit being represented,
such as its orientation or size. The last type of nodes — square nodes —
represent the dependency between observed and latent variables. In other
words, how does the digit being represented generate the pixels?

The first goal of this paper is to provide the reader with a full intuition of
the mathematics underlying active inference and variational message passing.
Then, this paper shows how to derive the update equations for any new
generative models. The hope is to facilitate the development of new models
that could, for example, play Atari games or model new brain mechanisms.
Finally, we use our new generative model to prove that the update equations of
active inference can be understood as variational message passing. This formal
proof complements previous work that frames active inference as belief
propagation (Friston et al., 2017b) and enables us to create an automatic and
modular implementation of active inference (van de Laar and de Vries, 2019a;
Cox et al., 2019). This message passing formulation has particular
consequences for the expected free energy, which is effectively reduced by the
change, resulting in an agent that seeks certainty, without any concern for
outcomes, whether preferred or not. We argue that the resulting behaviour may
have similarities to repetitive actions (sometimes called stimming) that are
common, for example, in autism (Gabriels, 2005).

Section 2 describes the problem used to present the (classic) model widely
used in the active inference literature. Sections 3 and 4 introduce
variational inference and Forney factor graphs, respectively. Next, Section 5
presents active inference as a decision theory based on the Bayesian view of
probability, followed by Section 6 that introduces the notion of variational
message passing. Then, Section 7 formulates active inference as variational
message passing under a fully factorised approximate posterior (i.e.
variational distribution), and explains the implications of this approximation
for the expected free energy that underwrites policy selection. Before
starting the next section, readers new to the active inference literature
might want to read Appendix D, which uses Bayes theorem to present the
simplest generative model sufficient for active inference.

##  2 Problem statement

Active inference crops up in many areas that require an agent to interact with
its environment. Throughout this paper, the explanations will be based on an
agent named Bob, whose goal is to solve the food problem presented in section
2.2. But before we investigate this problem, let us have a look at how to
simulate the interaction between Bob and his environment.

###  2.1 Simulating active inference

Most living beings are able to sense their environment through sensory inputs,
and process this sensory information to act in the world. For example,
carnivorous flowers use tiny trigger hairs on their leaves to detect flies
(sensing). When those hairs are stimulated, the ion concentrations in the
leaves increase (processing) resulting in an electrical current that closes
the leaf trapping the fly (acting). Similarly, humans gather sensory
information through their five senses (sensing), process this information to
understand their environment (processing), and finally, make use of this
understanding to act with intelligence (acting).

Sensing, processing and acting correspond to the three steps of the Action-
Perception cycle. This cycle conveniently casts active inference as an
infinite loop (van de Laar and de Vries, 2019b). Each iteration begins by
sampling the environment to obtain an observation, which is provided to the
agent. Then, the observation is used to perform inference (and learning) that
produce a higher level of understanding, for example, an image might be mapped
to a representation of the objects that it contains. And finally, this
representation is exploited when acting to prepare your diner, drive your kids
to school or solve your favourite maths problem.

###  2.2 The food problem

Speaking of which, this section is concerned with the food problem initially
proposed by Oleg Solopchuk (2018). This problem concerns an agent, named Bob,
striving to survive. To produce the energy needed by his body, Bob needs to
ingest nutriments. During periods of starvation, Bob’s stomach produces an
hormone called ghrelin. This hormone travels to the brain through the blood
and reaches a part of the brain, named the hippocampus. This area has been
shown to monitor the level of ghrelin in the blood (Kojima and Kangawa, 2005).
At the moment ghrelin reaches the hippocampus, Bob’s brain can estimate the
content of his stomach. This information can then be exploited to choose
between eating and sleeping. However, the best action depends on the outcomes
that Bob wants to witness in the future. This paper assumes that mother nature
has kindly set Bob’s preferences to be biased towards the sensation of feeling
fed (i.e. Bob enjoys observing low levels of ghrelin in his blood), which is
arguably a favourable traits under a Darwinism view of evolution. Figure 1
summarises the food problem.

Figure 1: This figure illustrates the food problem, where the goal of our
agent — Bob — is to keep his stomach full. The first thing Bob needs to
achieve his goal is to guess the state of his stomach, which can either be
full or empty. This guess is informed by the observations he makes, when
feeling hungry (high level of ghrelin) or fed (low level of ghrelin). Finally,
once Bob has reduced his uncertainty about his stomach state, he can engage in
exploitative behaviour by taking action in his environment, such as sleeping
or eating.

##  3 Variational Inference

In Bayesian statistics, one assumes a prior distribution over latent (a.k.a
hidden) variables that represent the process generating the data. When
collecting more data, new observations bring information, allowing us to
update our prior knowledge. The process of computing the most likely values of
the hidden variables is called inference. A simple inference method is to use
Bayes theorem to obtain the posterior probability distribution over the latent
variable(s) of the model:

$\displaystyle\underbrace{P(S|O)}_{\text{posterior}}=\frac{\overbrace{P(O|S)}^{\text{likelihood}}\overbrace{P(S)}^{\text{prior}}}{\underbrace{P(O)}_{\text{evidence}}}=\frac{P(O|S)P(S)}{\sum_{S}P(O|S)P(S)}.$

Since Bayes theorem is a corollary of the product rule of probability and no
approximation is needed, it belongs to the field of exact inference. However,
the computation of the evidence requires the marginalisation over all hidden
variables, which makes it intractable for all but the simplest models.

To address this intractability, one can turn to approximate or sampling based
methods. Variational inference belongs to the former and relies on an
assumption of independence. As will be explained in Section 6.1, the idea
behind variational inference is to use a distribution $Q(S)$ to approximate
the true posterior $P(S|O)$. This can be accomplished by minimising the
Kullback-Leibler (KL) divergence between some approximate and the true
posterior:

$D_{\mathrm{KL}}\left[\left.\left.{\color[rgb]{0,0,0.5}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.5}Q(S)}\right|\right|{\color[rgb]{0.9,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.9,0,0}P(S|O)}\right].$

Minimising this KL divergence is impossible because the true posterior
$P(S|O)$ is unknown. Fortunately however, it is equivalent to minimising the
variational free energy $\bm{F}$, known in machine learning as the negative
evidence lower bound (ELBO). The variational free energy is defined as the
Kullback-Leibler divergence between the variational distribution $Q(S)$ and
the generative model $P(O,S)$:

$\displaystyle\bm{F}$
$\displaystyle=D_{\mathrm{KL}}\left[\left.\left.{\color[rgb]{0,0,0.5}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.5}Q(S)}\right|\right|P(O,S)\right]=-ELBO$
$\displaystyle=D_{\mathrm{KL}}\left[\left.\left.{\color[rgb]{0,0,0.5}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.5}Q(S)}\right|\right|{\color[rgb]{0.9,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.9,0,0}P(S|O)}\right]+\ln
P(O).$

The variational distribution $Q(S)$ is used to approximate the true posterior
$P(S|O)$. In addition to the introduction of this approximate posterior, the
mean-field approximation makes the computation tractable by assuming that all
latent variables are independent:

$\displaystyle{\color[rgb]{0,0,0.5}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.5}Q(S)}=\prod_{i}Q_{i}(S_{i}),$

where $Q_{i}(S_{i})$ is the distribution over the i-th hidden state of the
model and $Q(S)$ is the joint distribution over all latent variables. This
assumption of independence constrains the expressiveness of the variational
distribution, but allows the derivation of update equations, which can be
evaluated efficiently.

At this point, an analogy might be useful to furnish an intuitive
understanding of variational inference. Imagine you drop some coffee on a
table, producing a stain with a complex shape. To compute the area of the
stain, it might be useful to first assume an elliptic shape for the stain.
However, since the stain is not actually elliptic, the solution will only be
an approximation. In this analogy, the stain is the true posterior, and the
ellipse is the approximate posterior.

This analogy should help with the understanding of Figure 2 that illustrates
the kind of results obtained by variational methods. As will be demonstrated
in Section 6.2, it is possible to prove (Fox and Roberts, 2012) that
minimising the variational free energy $\bm{F}$ with respect to $Q_{k}(S_{k})$
can be performed by iterating one of the following update equations:

$\displaystyle\ln Q_{k}(S_{k})\leftarrow\ln Q_{k}^{*}(S_{k})=\langle\ln
P(O,S)\rangle_{\sim Q_{k}}$ (1) $\displaystyle\Leftrightarrow\quad\quad\quad$
$\displaystyle Q_{k}(S_{k})\leftarrow
Q_{k}^{*}(S_{k})=\frac{1}{Z}\exp\langle\ln P(O,S)\rangle_{\sim Q_{k}},$

where $Q_{k}^{*}(S_{k})$ is the optimal posterior, $Z$ is a normalisation
constant and
$\langle\mathchoice{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\displaystyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\textstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptscriptstyle\bullet$}}}}}\rangle_{\sim
Q_{k}}$ is the expectation over all factors but $Q_{k}$. Importantly, it is
the coupling of the above update equations (i.e. one update per hidden
variable $S_{k}$) that justifies the iteration of the updates until
convergence to the free energy minimum.

Figure 2: This figure illustrates the kind of result obtained using
variational inference. The true posterior drawn in red has a complex shape and
is approximated by the variational distribution drawn in blue. The grey area
depicts the error made when using the variational distribution to approximate
the true posterior.

##  4 Forney Factor Graphs

Typically, generative models are represented graphically using a graphical
model (Koller and Friedman, 2009) or Forney factor graph (Forney, 2001). This
section focuses on the latter representation introduced by David Forney in
2001, which uses three kinds of nodes. The nodes representing hidden and
observed variables are depicted by white and grey circles, respectively. And
factors are represented using white squares, which are linked to variable
nodes by arrows or lines. Arrows are used to connect factors to their target
variable, while lines link factors to their predictors. Figure 3 shows an
example of a Forney factor graph corresponding to the following generative
model:

$\displaystyle
P(O,S)={\color[rgb]{0.9,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.9,0,0}P_{O}}(O|S){\color[rgb]{0,0,0.5}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.5}P_{S}}(S).$
(2)

Generally, factor graphs only describe the model’s structure — in terms of the
variables and their dependencies — but not the individual factors. For
example, the definitions of
${\color[rgb]{0.9,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.9,0,0}P_{O}}$
and
${\color[rgb]{0,0,0.5}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.5}P_{S}}$
are not given by Figure 3, and additional information is required, e.g.
${\color[rgb]{0,0,0.5}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.5}P_{S}}(S)=\mathcal{N}(S;\mu,\sigma)$
specifies
${\color[rgb]{0,0,0.5}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.5}P_{S}}$
as a Gaussian distribution.

Initially, variables could only connect to a limited number of factors.
However, a special kind of factor, called an equality node, dissolves this
limitation. Purists tend to represent all equality nodes, while others make
them implicit by allowing the variables to connect to an arbitrary number of
factors. For sake of clarity, this paper keeps equality nodes implicit.

Finally, factors — along with hidden and observed variables — are sometimes
called constraint, state and symbol, respectively. As explained by Yedidia
(2011), those two terminologies refer to two views on Forney factor graphs,
where factors encode probabilities and constraints encode costs. Infinite
costs represent hard constraints, while finite costs encode soft constraints.
Here, hard constraints define which configurations of the state space are
forbidden (i.e. has a probability of zero) and soft constraints encode
preferences over the state configurations (i.e. the higher the cost the
smaller the state probability). This reveals an interesting link between
Bayesian statistics and symbolic artificial intelligence, and prompts the
question of whether Bayesian statistics can be regarded as a generalisation of
symbolic artificial intelligence. For example, one could start by framing the
problem of constraint satisfaction, as an inference process on a Forney factor
graph that encodes the problem constraints.

Figure 3: This figure illustrates the Forney factor graph corresponding to the
following generative model:
$P(O,S)={\color[rgb]{0.9,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.9,0,0}P_{O}}(O|S){\color[rgb]{0,0,0.5}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.5}P_{S}}(S)$.
The hidden state is represented by a white circle with the variable’s name at
the centre, and the observed variable is depicted similarly but with a grey
background. The factors of the generative model are represented by squares
with a white background and the factor’s name at the centre. Finally, arrows
connect the factors to their target variable and lines link each factor to its
predictor variables.

##  5 Active Inference

So far, we have discussed variational inference and Forney factor graphs. We
now present the intuition behind the various equations that comprise the
active inference framework. We will be working with the food problem that was
introduced in Section 2.

###  5.1 Generative model

We begin by presenting the generative model introduced by Friston et al.
(2013). Instead of presenting the full generative model at once, the next
subsections build this model progressively. This should help the reader to
understand both the model and its corresponding Forney factor graph.

####  5.1.1 The D vector

As we shall see shortly, the full generative model represents the world as a
sequence of hidden states, and those states generate the observations made by
the agent. For the sake of organisation, those states are arranged
chronologically using the index $\tau$ that runs from the initial state
($S_{0}$) to the state of the last time step ($S_{T}$). This section focuses
on the initial state, whose distribution is a categorical, defined as follows:

$\displaystyle P_{S_{0}}(S_{0}|\bm{D})=\text{Cat}(S_{0};\bm{D}),$ (3)

where $\bm{D}$ is a vector containing the parameters of the categorical
distribution. In addition to the categorical distribution, the model assumes a
Dirichlet prior over the parameters $\bm{D}$, leading to:

$\displaystyle P_{D}(\bm{D})=\text{Dir}(\bm{D};d).$ (4)

In this context, the parameters $d$ of the Dirichlet distribution are called
hyperparameters, because they control the distribution of the parameters
$\bm{D}$. Figure 4 summarises this part of the model by presenting an example
of the vector $\bm{D}$, and the Forney factor graph corresponding to the two
distributions constituting Bob’s generative model.

Figure 4: This figure illustrates the vector $\bm{D}$ that defines Bob’s
beliefs about the initial hidden state, and the Forney factor graph
corresponding to (3) and (4). Since the probability of $S_{0}$ being full is
higher than the probability of it being empty, Bob thinks that at the
beginning of each trial, his stomach is more likely to be full than empty.

####  5.1.2 The A matrix

We have already mentioned that the probability of an observation (a.k.a
outcome), such as feeling hungry, depends on the value of the hidden state,
i.e. whether Bob’ stomach is full or empty. This dependency is represented by
a conditional distribution, such that the likelihood of an observation — given
a particular value of the hidden states — is defined by a categorical
distribution, as follows:

$P_{O_{\tau}}(O_{\tau}|S_{\tau}=j,\bm{A})=\text{Cat}(O_{\tau};\bm{A}_{\mathchoice{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\displaystyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\textstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptscriptstyle\bullet$}}}}}j}),$

where the j-th column of $\bm{A}$, denoted
$\bm{A}_{\mathchoice{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\displaystyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\textstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptscriptstyle\bullet$}}}}}j}$,
contains the parameters of the categorical distribution encoding the
probability of the outcomes given that $S_{\tau}=j$. Additionally, we can re-
write the above equation more concisely by letting $S_{\tau}$ be a one hot
vector, whose j-th element is equal to one, such that:

$P_{O_{\tau}}(O_{\tau}|S_{\tau},\bm{A})=\text{Cat}(O_{\tau};\bm{A}S_{\tau}),$

where because $S_{\tau}$ is a one hot vector, the multiplication of $\bm{A}$
and $S_{\tau}$ selects the j-th column of $\bm{A}$. Similarly to the treatment
of the vector $\bm{D}$, a prior over the columns of $\bm{A}$ is used. To
ensure the conjugacy between the distributions of the model, a Dirichlet prior
is used for each column. The probability of the overall matrix is then given
by the following product of Dirichlet:

$P_{A}(\bm{A})=\prod_{i}\text{Dir}(\bm{A}_{\mathchoice{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\displaystyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\textstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptscriptstyle\bullet$}}}}}i};a_{\mathchoice{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\displaystyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\textstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptscriptstyle\bullet$}}}}}i}),$

where $a$ is a matrix containing the parameters of the Dirichlet
distributions, i.e., each column of $a$ contains the parameters of one
Dirichlet distribution. Note that because each column of the matrix $\bm{A}$
is a categorical distribution, then the conjugate prior of each column is a
Dirichlet distribution. Assuming independence of the columns of $\bm{A}$, the
conjugate prior of the entire matrix $\bm{A}$ is a product of Dirichlet
distributions. Importantly, the prior over $\bm{A}$ is not a Dirichlet
distribution whose parameters are obtained by concatenation of the columns of
$\bm{A}$. Indeed, if we sample from such a (concatenated) prior, then the
elements of the entire matrix will sum up to one but the columns would not.
This is problematic because each column of $\bm{A}$ is supposed to be a
categorical distribution that sum up to one. We conclude this section with
Figure 5 that illustrates the likely matrix $\bm{A}$, along with the resulting
version of the generative model for Bob’s problem.

Figure 5: This figure illustrates the matrix $\bm{A}$ that defines how the
hidden states generate the observations. In our example with Bob, this matrix
defines the probability of Bob feeling hungry or fed while his stomach is full
or empty. Furthermore, the new version of the generative model is shown on the
right.

####  5.1.3 The B matrices

Now that the reader is familiar with the definition of the likelihood matrix
$\bm{A}$, we focus on the temporal transitions between any pair of successive
states. Those transitions are modelled similarly to the matrix $\bm{A}$ that
concerns the generation of observations from hidden states. However here, we
are concerned with the transition matrices that maps from states at one point
on time to the next. Crucially, there are as many of these matrices as the
number of allowable actions on the state in question. This follows from the
idea that each action has the potential to modify Bob’s stomach differently:
for example, eating is more likely to change Bob’s stomach from empty to full
than sleeping. Accordingly, the transition between two consecutive hidden
states is defined by a set of matrices, called the transition or $\bm{B}$
matrices, such that:

$\displaystyle P_{S_{\tau+1}}(S_{\tau+1}|S_{\tau}=i,\pi=j,\bm{B})$
$\displaystyle=\text{Cat}(S_{\tau+1};\bm{B}[U_{\tau}^{j}]_{\mathchoice{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\displaystyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\textstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptscriptstyle\bullet$}}}}}i})$
$\displaystyle\mathrel{\ensurestackMath{\stackon[1pt]{=}{\scriptstyle\Delta}}}\text{Cat}(S_{\tau+1};\bm{B}[U]_{\mathchoice{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\displaystyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\textstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptscriptstyle\bullet$}}}}}i})$

where $\mathrel{\ensurestackMath{\stackon[1pt]{=}{\scriptstyle\Delta}}}$ means
equal by definition,
$U\mathrel{\ensurestackMath{\stackon[1pt]{=}{\scriptstyle\Delta}}}U_{\tau}^{j}$
is the action predicted at time step $\tau$ by the j-th policy, and
$\bm{B}[U]$ is the matrix corresponding to the action $U$. Furthermore, active
inference defines policies as action sequences (cf. next section). By
replacing the index $i$ by a one hot vector as in the previous section,
Equation 5.1.3 can be re-written as:

$P_{S_{\tau+1}}(S_{\tau+1}|S_{\tau},\pi,\bm{B})=\text{Cat}(S_{\tau+1};\bm{B}[U]S_{\tau}).$

A Dirichlet prior is assumed for each column of the transition matrices
$\bm{B}$, leading to the following prior:

$P_{B}(\bm{B})=\prod_{i,j}\text{Dir}(\bm{B}[i]_{\mathchoice{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\displaystyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\textstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptscriptstyle\bullet$}}}}}j};b[i]_{\mathchoice{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\displaystyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\textstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptscriptstyle\bullet$}}}}}j}),$

where $b$ are the parameters of the Dirichlet distributions, $i$ and $j$
iterate over all possible actions and states, respectively. Finally, Figures 6
and 7 conclude this subsection by illustrating the matrices $\bm{B}$, and the
updated version of the generative model.

Figure 6: This figure illustrates the matrices $\bm{B}$ that define the
transition between any two consecutive hidden states. In the context of the
food problem, those matrices encode the probability of transitioning from a
full or empty stomach at time $\tau$ to a full or empty stomach at time
$\tau+1$. Figure 7: This figure shows the next version of the generative
model, where the transition between hidden states is specified by a set of
$\bm{B}$ matrices and the policies $\pi$. At this point, it should be
emphasized that the generation of outcomes through the matrix $\bm{A}$ stops
after the current time step $t$. This follows naturally from the idea that we
cannot observe future outcomes. Finally, the factor $P_{\pi}$ has not been
defined yet: it will be the subject of the next section.

####  5.1.4 The prior over policies

We now consider the prior over the policy that was left undefined in Figure 7.
But what do we exactly mean by policies? In active inference, a policy is a
sequence of actions over time, i.e. $\\{U_{t},...,U_{T-1}\\}$. As a
consequence, even if the agent expects the environment to be in the same state
at two different time steps, picking two different actions at those time steps
is still possible. Therefore, an active inference agent can perform an
epistemic action as long as there is some uncertainty to be reduced and then
switch to exploitative behaviours. Note that this definition of policy is in
opposition to most of the model-free reinforcement learning literature, where
a policy is a mapping from states to actions. In particular, states in the
context of model-free reinforcement learning are observed and therefore are
closer to the notion of observations in active inference. Technically, active
inference takes us out of the world of fixed state-action policies (where the
same action is taken from each state) into the world of sequential policy
optimisation, where different actions can be taken from the same state —
crucially, in a way that depends upon (Bayesian) beliefs about hidden states.

The last ingredient required to obtain the prior over the policies is a notion
of policy quality. In active inference, good policies are the ones that
minimise the expected free energy; that is, the free energy expected in the
future, which is defined as follows:

$\displaystyle\bm{G}(\pi)\approx\sum_{\tau=t+1}^{T}\Bigg{[}\underbrace{D_{\mathrm{KL}}[\overbrace{Q(O_{\tau}|\pi)}^{\text{expected
outcomes}}||\overbrace{P(O_{\tau})}^{\text{prior
preferences}}]}_{\text{risk}}\,\,+\,\,\underbrace{\mathbb{E}_{Q(S_{\tau}|\pi)}[\text{H}[P(O_{\tau}|S_{\tau})]]}_{\text{ambiguity}}\Bigg{]},$
(5)

where $\text{H}[\cdot]$ is the Shannon entropy, $\bm{G}$ is a vector
containing as many elements as the number of policies, and the i-th element of
$\bm{G}$ represents the quality of the i-th policy. The reader interested in
the derivation of the expected free energy is referred to Appendix C. We
should mention here that $Q(O_{\tau}|\pi)$ and $Q(S_{\tau}|\pi)$ are computed
based on the result of the inference process of the previous action-perception
cycle. Therefore, $\bm{G}$ can be regarded as a model parameter and is not
represented as a random variable in the Forney factor graph. The definition
and justification of the expected free energy are provided in Appendix C and a
recent paper by Millidge et al. (2020). Also, the expected free energy arises
naturally in mathematical treatments of the free energy principle, when
considering self-organisation at non-equilibrium steady-state (Friston, 2019;
Parr et al., 2020). At this point, we should take a moment to understand the
intuition behind the expected free energy.

Let us begin with the second term of Equation 5. For each value of the hidden
state, $P(O_{\tau}|S_{\tau}=i)$ is a categorical distribution whose parameters
correspond to the i-th column of $\bm{A}$. This distribution defines the
probability of future outcomes. Thus, the closer this distribution is to a
uniform distribution, the more uncertain we are about future outcomes. This
uncertainty is measured by the Shannon entropy, and the average of this
quantity over all possible values of $S_{\tau}$ is called the ambiguity.
Therefore, the ambiguity quantifies the degree to which a particular
observation disambiguates among its hidden or latent causes.

Next, we need to encode Bob’s preferences over future outcomes, which are
called prior preferences. Formally, those preferences are defined as a
categorical distribution whose parameters are stored in the vector $\bm{C}$.
Figure 8 illustrates this vector. It should be noted that those preferences
define the goodness of future outcomes, and we shall come back to this when
discussing the link between active inference and reinforcement learning, cf.
Appendix A.

Figure 8: This figure illustrates the vector $\bm{C}$ that defines Bob’s prior
preferences over future outcomes. This vector corresponds to the case where
Bob prefers to feel fed rather than hungry, and the intensity of those
preferences can be changed by tweaking the probabilities of the vector
$\bm{C}$. For example, $\bm{C}=(0,1)$ corresponds to an extreme preference
towards feeling fed.

To conclude, we need to consider the predicted or expected outcomes. One way
to predict future outcomes would be to compute the marginal distribution over
$O_{\tau}$ using for example the sum product algorithm (Kschischang et al.,
2001). However, this might be computationally expensive, so we will proceed
with the following formula:

$Q(O_{\tau}|\pi)=\sum_{i}P(O_{\tau}|S_{\tau}=i,A)Q(S_{\tau}=i|\pi)=\bm{A}\bm{s}_{\tau}^{\pi},$

where as will be discussed in Section 5.2,
$Q(S_{\tau}|\pi)\mathrel{\ensurestackMath{\stackon[1pt]{=}{\scriptstyle\Delta}}}\text{Cat}(S_{\tau};\bm{s}_{\tau}^{\pi})$.
This equation can be understood as a form of marginalization, where the
approximate posterior $Q(S_{\tau}|\pi)$ is our most informed belief about the
hidden states. Finally, the KL divergence between the expected outcomes and
the prior preference is called risk (cf. Appendix A for additional details).
The risk part of expected free energy is simply the divergence between the
expected outcomes and the preferred outcomes. It is this part of expected free
energy that underwrites policies that lead to preferred outcomes under
uncertainty. Minimising expected free energy therefore minimises risk (i.e.,
the divergence between anticipated and preferred outcomes) and ambiguity
(i.e., the conditional uncertainty about outcomes, given the causes). The
resulting prior over the policies is defined as:

$P_{\pi}(\pi|\gamma)=\sigma(-\gamma\bm{G}),$

where $\sigma(\cdot)$ is the softmax function, $\bm{G}$ is the expected free
energy, $\gamma$ determines the sensitivity of policy selection to the
expected free energy of each policy, and the negative sign gives high
probability to policies minimising expected free energy. Importantly, the
prior over policies is an empirical prior because the expected free energy
depends on the observations, which means that it must be re-evaluated each
time a new observation is made by the agent. In other words, the prior over
the policies is a Boltzmann distribution with $\gamma$ being the inverse
temperature. Taking this view, small values for $\gamma$ means a high
temperature and less precise prior beliefs about which policy should — or is —
being pursued. Figure 10 shows an example of this distribution and Figure 9
illustrates the current generative model.

Figure 9: This figure illustrates the Forney factor graph of the entire
generative model of the sort presented by Friston et al. (2016). Section 5.1.1
described how the probability of the initial states is defined by the vector
$\bm{D}$, and as discussed in Section 5.1.2, the matrix $\bm{A}$ defines the
probability of the observations given the hidden states. Section 5.1.3
explained that the $\bm{B}$ matrices define the transition between any
successive pair of hidden states. This transition depends on the action
performed by the agent, i.e. on the policy $\pi$. Furthermore, the prior over
the policies has been chosen in Section 5.1.4, such that policies minimising
the expected free energy are more probable. Finally, we see in section 5.1.5
that the precision parameter $\gamma$ (which modulates the stochasticity of
the agent behaviour) is distributed according to a gamma distribution. Figure
10: A distribution over the policies that gives high probability to policies
fulfilling Bob’s preferences in the future. For example, the first policy
where Bob is constantly eating has high probability, while the fourth policy
where Bob is constantly sleeping has low probability. This is congruent with
the notion that eating is more likely to make Bob feel fed than hungry, and
similarly, sleeping is more likely to make Bob feel hungry than fed.

####  5.1.5 The prior over the precision parameter

We now turn to the last part of the generative model, i.e. the prior over the
precision parameter $\gamma$. Importantly, this precision parameter has been
associated with the neuromodulator dopamine through what is called the
“precision hypothesis” (FitzGerald et al., 2015). This association of dopamine
and the precision parameter claims to unify two perspectives on the role of
dopamine. The first frames dopamine as an error signal on predicted reward
(Schultz et al., 1997) and uses the framework of TD-learning. The second,
called the incentive salience hypothesis, frames dopamine as “associating
salience and attractiveness to visual, auditory, tactile, or olfactory
stimuli” (Berridge, 2007).

But, let us come back to the prior over the precision parameters $\gamma$. In
neurobiological treatments, this prior usually takes the form of a gamma
distribution with a rate parameter $\beta$ and a shape parameter fixed to one:

$P_{\gamma}(\gamma)=\Gamma(\gamma;1,\beta).$

The graph on the right of Figure 11 illustrates two variations of this prior
for $\beta=1$ and $\beta=2$. Also, we should mention that a more flexible
prior can be obtained by removing the constraint on the shape parameter
(Friston et al., 2015), and the left hand side of Figure 11 illustrates this
extension. However, in most artificial intelligence applications (that are not
concerned with biological implementation or dopamine), $\gamma$ is usually
assumed to be one. Mainly, this design choice is made for the sake of
simplicity, even if in practice forcing $\gamma$ to be one reduces the model
flexibility, i.e. $\gamma$ can no longer be learnt.

Figure 11: This figure illustrates four gamma distributions where the values
of the parameters have been changed. The graph on the right shows the kind of
prior the model believes in by forcing the shape parameter to equal one.

Notation | Meaning
---|---
$T$ | The time horizon
$t$ | The current time steps
$\tau$ | An iterator over time step
$O_{0:t}$ | The sequence of observations between time step 0 and t
$S_{0:T}$ | The sequence of hidden states between time step 0 and T
$\pi$ | The policies
$U_{\tau}^{m}\mathrel{\ensurestackMath{\stackon[1pt]{=}{\scriptstyle\Delta}}}U$ | The action or control state predicted by the m-th policy at time step $\tau$
$\bm{A}$ | The matrix defining the likelihood mapping from the hidden states to the
observations
$\bm{A}_{\mathchoice{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\displaystyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\textstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptscriptstyle\bullet$}}}}}i}$ | The i-th column of the matrix $\bm{A}$
$\bm{B}$ | The set of transition matrices defining the mappings between any two consecutive
hidden states
$\bm{B}[U]_{\mathchoice{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\displaystyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\textstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptscriptstyle\bullet$}}}}}i}$ | The i-th column of the transition matrix $\bm{B}[U]$ corresponding to action $U$
$\bm{D}$ | The prior over the initial hidden states
$a$, $b$, $d$ | The parameters of the prior over $\bm{A}$, $\bm{B}$ and $\bm{D}$
$a_{\mathchoice{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\displaystyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\textstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptscriptstyle\bullet$}}}}}i}$ | The i-th column of the matrix $a$
$b[U]_{\mathchoice{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\displaystyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\textstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptscriptstyle\bullet$}}}}}i}$ | The i-th column of the matrix $b[U]$ corresponding to action $U$
$\gamma$ | The precision parameter related to neuromodulators such as dopamine
$\sigma(x)$ | The softmax function
$\bm{G}$ | The expected free energy
$\Gamma(\gamma;\alpha,\beta)$ | Gamma distribution with shape and inverse scale parameters $\alpha$ and $\beta$
$\text{Cat}(S_{0};\bm{D})$ | Categorical distribution over $S_{0}$ with parameter $\bm{D}$
$\text{Dir}(\bm{D};d)$ | Dirichlet distribution
Table 1: Generative Model notation

####  5.1.6 The entire generative model

Throughout this section, we have assembled incrementally the generative model
usually used in active inference, whose Forney factor graph is represented in
Figure 9. The last step is to write down the equations that constitute its
formal definition:

$\displaystyle
P(O_{0:t},S_{0:T},\pi,\bm{A},\bm{B},\bm{D},\gamma)\,\,=\,\,\,\,$
$\displaystyle
P(\pi|\gamma)P(\gamma)P(\bm{A})P(\bm{B})P(S_{0}|\bm{D})P(\bm{D})$
$\displaystyle\prod^{t}_{\tau=0}P(O_{\tau}|S_{\tau},\bm{A})\prod^{T}_{\tau=1}P(S_{\tau}|S_{\tau-1},\bm{B},\pi),$
(74)

where:

$\displaystyle P(\pi|\gamma)=\sigma(-\gamma\bm{G})$ $\displaystyle
P(\gamma)=\Gamma(\gamma;1,\beta){\color[rgb]{1,1,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,1,1}\pgfsys@color@gray@stroke{1}\pgfsys@color@gray@fill{1}\prod_{i}}$
$\displaystyle
P(\bm{A})=\prod_{i}\text{Dir}(\bm{A}_{\mathchoice{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\displaystyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\textstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptscriptstyle\bullet$}}}}}i};a_{\mathchoice{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\displaystyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\textstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptscriptstyle\bullet$}}}}}i})$
$\displaystyle
P(\bm{B})=\prod_{i,j}\text{Dir}(\bm{B}[i]_{\mathchoice{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\displaystyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\textstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptscriptstyle\bullet$}}}}}j};b[i]_{\mathchoice{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\displaystyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\textstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptscriptstyle\bullet$}}}}}j})$
$\displaystyle P(S_{0}|\bm{D})=\text{Cat}(S_{0};\bm{D})$ $\displaystyle
P(\bm{D})=\text{Dir}(\bm{D};d){\color[rgb]{1,1,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,1,1}\pgfsys@color@gray@stroke{1}\pgfsys@color@gray@fill{1}\prod_{i}}$
$\displaystyle
P(O_{\tau}|S_{\tau},\bm{A})=\text{Cat}(O_{\tau};\bm{A}S_{\tau})$
$\displaystyle
P(S_{\tau}|S_{\tau-1},\bm{B},\pi)=\text{Cat}(S_{\tau};\bm{B}[U]S_{\tau-1}){\color[rgb]{1,1,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,1,1}\pgfsys@color@gray@stroke{1}\pgfsys@color@gray@fill{1}\prod_{i}}$

Note that to keep the notation uncluttered, we have dropped the subscripts
such that $P_{S_{0}}(S_{0}|\bm{D})$ becomes $P(S_{0}|\bm{D})$, $P_{A}(\bm{A})$
becomes $P(\bm{A})$ and so forth. Table 1 provides a complete description of
the notation used to define the generative model.

###  5.2 Variational Distribution

We now turn to the definition of the variational distribution, which is used
to approximate the true posterior during variational inference (a.k.a
approximate Bayesian inference), i.e. $Q(x)\approx P(x|o)$ where $x$ and $o$
denote the hidden variables and the observations, respectively. Let us first
recall that variational inference leverages independence between latent
variables in what is known as a mean-field approximation. A structured
approximation, often made in the active inference literature111An instance
where this general assumption is not made can be found in (Parr et al., 2019).
to simplify computations is that all latent variables are independent except
for the hidden states and the policy. This leads to the following variational
distribution:

$\displaystyle
Q(S_{0:T},\pi,\bm{A},\bm{B},\bm{D},\gamma)=Q_{\pi}(\pi)Q_{A}(\bm{A})Q_{B}(\bm{B})Q_{D}(\bm{D})Q_{\gamma}(\gamma)\prod_{\tau=0}^{T}Q_{S\tau}(S_{\tau}|\pi),$
(75)

where:

$\displaystyle
Q_{S\tau}(S_{\tau}|\pi)=\text{Cat}(S_{\tau};\bm{s}_{\tau}^{\pi})$
$\displaystyle Q_{\pi}(\pi)=\text{Cat}(\pi;\bm{\pi})$ $\displaystyle
Q_{\gamma}(\gamma)=\Gamma(\gamma;1,\bm{\beta})$ $\displaystyle
Q_{D}(\bm{D})=\text{Dir}(\bm{D};\bm{d})$ $\displaystyle
Q_{A}(\bm{A})=\prod_{i}\text{Dir}(\bm{A}_{\mathchoice{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\displaystyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\textstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptscriptstyle\bullet$}}}}}i};\bm{a}_{\mathchoice{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\displaystyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\textstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptscriptstyle\bullet$}}}}}i})$
$\displaystyle
Q_{B}(\bm{B})=\prod_{i,j}\text{Dir}(\bm{B}[i]_{\mathchoice{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\displaystyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\textstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptscriptstyle\bullet$}}}}}j};\bm{b[i]_{\mathchoice{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\displaystyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\textstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptscriptstyle\bullet$}}}}}j}})$

Once again, for the sake of compactness, the subscript will be dropped, e.g.
$Q_{S\tau}(S_{\tau}|\pi)$ will be replaced by $Q(S_{\tau}|\pi)$. Table 2
summarises the notation used to define this variational distribution. It is
much easier to understand this distribution by comparing it to the definition
of the generative model in Equation 74. Indeed, the distributions over
$\bm{A}$, $\bm{B}$ and $\bm{D}$ remain Dirichlet distributions, and the
distributions over $\gamma$ and $S_{\tau}$ remain gamma and categorical
distributions, respectively. Only the distribution over $\pi$ changes from a
Boltzmann to a categorical distribution. However, both the Boltzmann and the
categorical are discrete distributions.

Notation | Meaning
---|---
$\bm{s}_{\tau}^{\pi}$ | The parameters of the posterior over $S_{\tau}$ for each policy, i.e. a vector
$\bm{s}_{\tau}^{\,\mathchoice{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\displaystyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\textstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptscriptstyle\bullet$}}}}}}$ | The parameters of the posterior over $S_{\tau}$ for all policies, i.e. a matrix
$\bm{\pi}$ | The parameters of the posterior over $\pi$, i.e. a vector
$\bm{a}$, $\bm{b}$, $\bm{d}$ | The parameters of the posterior over $\bm{A}$, $\bm{B}$ and $\bm{D}$, i.e. a matrix,
a set of matrices and a vector, respectively
$\bm{\beta}$ | The (inverse temperature) parameter of the posterior over $\gamma$
Table 2: Variational distribution notation

###  5.3 Variational Free Energy

Above, we have unpacked the generative model and variational distribution used
in active inference. This section combines those two concepts to form the
second cornerstone of the active inference framework, i.e. the variational
free energy. Section 6.1 will explain how the following equation can be
derived from the Kullback-Leibler divergence between the variational
distribution and the true posterior. However, this section explains the
intuition behind the variational free energy, which is defined as follows:

$\displaystyle\bm{F}$ $\displaystyle=\mathbb{E}_{Q}[\ln
Q(S_{0:T},\pi,\bm{A},\bm{B},\bm{D},\gamma)-\ln
P(O_{0:t},S_{0:T},\pi,\bm{A},\bm{B},\bm{D},\gamma)]$
$\displaystyle=\underbrace{D_{\mathrm{KL}}\left[\left.\left.Q(x)\right|\right|P(x|o)\right]}_{\text{relative
entropy}}\,\,\,-\underbrace{\ln P(o)}_{\text{log evidence}},$ (76)

where $x=\\{S_{0:T},\pi,\bm{A},\bm{B},\bm{D},\gamma\\}$ refers to the model’s
hidden variables, and $o=\\{O_{0:t}\\}$ refers to the sequence of observations
made by the agent. Equation 76 highlights some important properties of the
variational free energy. Indeed, the relative entropy (a.k.a KL divergence)
ensures that the variational distribution $Q(x)$ tends to get closer to the
true posterior $P(x|o)$, as the free energy is reduced. Furthermore, it shows
that the variational free energy is an upper bound on the negative log
evidence, because the relative entropy cannot be negative. Also, if the
variational distribution is equal to the true posterior, then the variational
free energy is equal to the (-ve) log evidence. The variational free energy
can also be re-arranged as:

$\displaystyle\bm{F}$
$\displaystyle=\underbrace{D_{\mathrm{KL}}\left[\left.\left.Q(x)\right|\right|P(x)\right]}_{\text{complexity}}-\underbrace{\mathbb{E}_{Q(x)}[\ln
P(o|x)]}_{\text{accuracy}},$ (77)

showing the trade-off between complexity and accuracy. The complexity
penalises the divergence of the posterior $Q(x)$ from the prior $P(x)$. The
accuracy scores how likely the observations are given the generative model and
current belief of the hidden states. Interestingly, in opposition to the
Akaike information criterion (AIC) and Bayesian information criterion (BIC),
the complexity does not depend on the number of parameters. Consequently, a
model with a lot of parameters, but that does not vary from the prior will
have zero complexity, and a model with a small number of parameters that moves
away a lot from the prior will have a large complexity. Taking this view, a
model is complex whenever the knowledge encoded by the prior fails to explain
the observed data accurately. In other words, complexity scores the degree of
belief updating that moves posterior beliefs away from prior beliefs to
provide an accurate account of any observations.

Comparison of the expression for expected free energy and variational free
energy reveals an intimate relationship. One can see that the risk is the
expected complexity, while ambiguity is expected inaccuracy. These
expectations are under the posterior predictive beliefs about outcomes in the
future under the policy in question. This is why $\bm{G}$ is called expected
free energy.

###  5.4 Update equations

All the update equations presented below come from the minimisation of the
variational free energy. This section presents the intuition behind those
updates using the notations summarized in Table 3. Let us start with the
optimal updates of $\bm{A}$, $\bm{B}$ and $\bm{D}$ that are given by:

$\displaystyle Q^{*}(\bm{D})$
$\displaystyle=\text{Dir}(\bm{D};\bm{d})\quad\quad\quad\quad\quad\,\,\,\,\text{
where }\quad\bm{d}=d+\bm{s}_{0}$ (78) $\displaystyle Q^{*}(\bm{A})$
$\displaystyle=\prod_{i}\text{Dir}(\bm{A}_{\mathchoice{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\displaystyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\textstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptscriptstyle\bullet$}}}}}i},\bm{a}_{\mathchoice{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\displaystyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\textstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptscriptstyle\bullet$}}}}}i})\quad\quad\quad\,\,\text{
where }\quad\bm{a}=a+\sum_{\tau=0}^{t}\bm{o}_{\tau}\otimes\bm{s}_{\tau}$ (79)
$\displaystyle Q^{*}(\bm{B})$
$\displaystyle=\prod_{u,i}\text{Dir}(\bm{B}[u]_{\mathchoice{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\displaystyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\textstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptscriptstyle\bullet$}}}}}i},\bm{b}[u]_{\mathchoice{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\displaystyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\textstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptscriptstyle\bullet$}}}}}i})\,\quad\text{
where
}\quad\bm{b}[u]=b[u]+\sum_{(k,\tau)\in\Omega_{u}}\bm{s}^{k}_{\tau}\otimes\bm{s}^{k}_{\tau-1}\bm{\pi}_{k}\vspace{-0.5cm}$
(80)

Looking at the above equations, these updates can be understood as counting
the number of times an event appears. For example, the update of $\bm{A}$
counts the number of times a pair of states-observations have been observed.
Taking this view, $a$ is the pseudo count of previously occurring states-
observations pairs, and $\bm{o}_{\tau}\otimes\bm{s}_{\tau}$ takes into account
the new observations. Similarly, the update of the $\bm{B}$ and $\bm{D}$
matrices, respectively count how many times the state transitions and initial
states have been observed. Additionally, the updates of the hidden states are:

$\displaystyle Q^{*}(S_{0}|\pi)$ $\displaystyle=\sigma\Big{(}\bm{\bar{D}}$
$\displaystyle+\,I(0\leq t)\,\bm{o}_{0}\,\cdot\,\bm{\bar{A}}$
$\displaystyle+\,\,\bm{s}^{\pi}_{1}\quad\cdot\bm{\bar{B}}[U_{0}^{\pi}]\Big{)}{\color[rgb]{1,1,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,1,1}\pgfsys@color@gray@stroke{1}\pgfsys@color@gray@fill{1}\sum_{i}^{T}}$
(81) $\displaystyle Q^{*}(S_{\tau}|\pi)$
$\displaystyle=\sigma\Big{(}\bm{\bar{B}}[U_{\tau-1}^{\pi}]\bm{s}^{\pi}_{\tau-1}$
$\displaystyle+\,I(\tau\leq t)\,\bm{o}_{\tau}\,\cdot\,\bm{\bar{A}}$
$\displaystyle+\,\,\bm{s}^{\pi}_{\tau+1}\cdot\bm{\bar{B}}[U_{\tau}^{\pi}]\Big{)}$
(82) $\displaystyle Q^{*}(S_{T}|\pi)$
$\displaystyle=\sigma\Big{(}\underbrace{\bm{\bar{B}}[U_{T-1}^{\pi}]\bm{s}^{\pi}_{T-1}}_{\text{past
or prior}}\,$ $\displaystyle+\underbrace{I(T\leq
t)\,\bm{o}_{T}\cdot\bm{\bar{A}}}_{\text{likelihood}}$
$\displaystyle{\color[rgb]{1,1,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,1,1}\pgfsys@color@gray@stroke{1}\pgfsys@color@gray@fill{1}+}\,\,\,\underbrace{{\color[rgb]{1,1,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,1,1}\pgfsys@color@gray@stroke{1}\pgfsys@color@gray@fill{1}\bm{\bar{B}}[U_{T-1}^{\pi}]}\quad\,\,\,\,\,}_{\text{future}}\Big{)}{\color[rgb]{1,1,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,1,1}\pgfsys@color@gray@stroke{1}\pgfsys@color@gray@fill{1}\sum^{T}}$
(83)

where $t$ can be thought of as a global variable referring to the present time
point, and
$I(\mathchoice{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\displaystyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\textstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptscriptstyle\bullet$}}}}})$
is an indicator function that equals one if the condition is true and zero
otherwise. A closer look at these updates reveals that the hidden states are
updated by gathering information from the past, the future, and the likelihood
mapping. In Equation 81, the information from the past is replaced by some
information from the prior over the initial state, and in Equation 83, the
information from the future disappears because we have reached the limits of
the time horizon (i.e. $\tau==T$). Similarly, in Equations 82 and 83, the
indicator function ensures that there is no information from the likelihood
mapping after the current time step $t$ because no observations are available.
For additional information about the above updates, the reader is referred to
Sections 7.7 and 7.8 as well as Appendix G. Interestingly, Parr and Friston
(2018) proposed a model in which future observations are latent variables, and
in this case, information will be sent along the edges connecting future
states and future observations. Finally, the update of $\gamma$ and $\pi$
takes the following form:

$\displaystyle
Q^{*}(\gamma)=\Gamma\Big{(}\gamma;1,\beta+\bm{G}\cdot(\bm{\pi}-\bm{\pi}_{0})\Big{)}$
$\displaystyle
Q^{*}(\pi)=\sigma\Big{(}-\frac{1}{\bm{\beta}}\bm{G}-\mathcal{F}\Big{)}$

where $\bm{\pi}_{0}=\sigma(-\gamma\cdot\bm{G})$, $\sigma(\cdot)$ is the
softmax function, and $\mathcal{F}$ is a vector whose $\pi$-th element is
defined as:

$\displaystyle\mathcal{F}_{\pi}=\bm{s}^{\pi}_{0}\cdot(\ln\bm{s}^{\pi}_{0}-\bm{\bar{D}})+\sum_{\tau=1}^{T}\bm{s}^{\pi}_{\tau}\cdot(\ln\bm{s}^{\pi}_{\tau}-\bm{\bar{B}}[U]\bm{s}^{\pi}_{\tau-1})-\sum_{\tau=0}^{t}\bm{o_{\tau}}\cdot\bm{\bar{A}}\bm{s}^{\pi}_{\tau}.$

Section 7 will derive update equations similar to those above that can be
decomposed as a sum of messages coming from the parent, children and co-
parents of each node.

Notation | Meaning
---|---
$A\otimes B=AB^{T}$, $A\cdot B=A^{T}B$ | outer and inner products
$\llbracket a,b\rrbracket$ | all the natural numbers between $a$ and $b$
$\Omega_{u}=\Big{\\{}(k,\tau):U^{k}_{\tau-1}=u,\tau\in\llbracket 1,T\rrbracket\Big{\\}}$ | all $(k,\tau)$ such that the $k$-th policy predicts
action $u$ at time $\tau-1$
$\bm{s}_{\tau}=\bm{s}^{\,\mathchoice{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\displaystyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\textstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptscriptstyle\bullet$}}}}}}_{\tau}\cdot\bm{\pi}$ | the expected state at time $\tau$
$\langle f(X)\rangle_{P_{X}}\mathrel{\ensurestackMath{\stackon[1pt]{=}{\scriptstyle\Delta}}}\mathbb{E}_{P_{X}}[f(X)]$ | is the expectation of $f(X)$ over $P_{X}$
$\psi(x)$ | the digamma function used to compute
analytical solutions, e.g. for $\langle\ln\bm{D}_{i}\rangle_{Q_{D}}$.
$\bm{\bar{D}_{i}}=\langle\ln\bm{D}_{i}\rangle_{Q_{D}}=\psi(\bm{d}_{i})-\psi(\sum_{i}\bm{d}_{i})$ | the expected logarithm of $\bm{D}$
$\bm{\bar{A}}_{ij}=\langle\ln\bm{A}_{ij}\rangle_{Q_{A}}=\psi(\bm{a}_{ij})-\psi(\sum_{k}\bm{a}_{kj})$ | the expected logarithm of $\bm{A}$
$\bm{\bar{B}}[u]_{ij}=\langle\ln\bm{B}[u]_{ij}\rangle_{Q_{B}}=\psi(\bm{b}[u]_{ij})-\psi(\sum_{k}\bm{b}[u]_{kj})$ | the expected logarithm of $\bm{B}$
Table 3: Update equations notation

###  5.5 Action selection

This section focuses on the various strategies available to pick the next
action(s) that the agent will then perform. In active inference, the action
selection process is performed after iteration of the update equations.
Indeed, according to the Action-Perception cycle presented in Section 2, the
agent first minimises the variational free energy and then acts in its
environment. The first strategy entails summing the posterior evidence for the
policies predicting each action, and to execute the action with the highest
sum of posterior evidence:

$\displaystyle
u_{t}^{*}=\operatorname*{arg\,max}_{u}\sum_{m=1}^{|\pi|}\delta_{u,U^{m}_{t}}Q(\pi=m),$

where $|\pi|$ is the number of policies, $U^{m}_{t}$ is the action predicted
at the current time step by the policy $\pi$, and $\delta_{u,U^{m}_{t}}$ is an
indicator function that equals one if $u=U^{m}_{t}$ and zero otherwise. Since
the model knows the posterior over the policies (i.e. sequences of actions)
another strategy is to simply sample an entire policy (e.g. a sequence of
actions) without re-computing the posterior at each timestep, i.e. Bob selects
a policy, closes his eyes and performs the sequence of actions entailed by
that multi-step policy. In the case of single-step policies, this is
equivalent to the first strategy. This leads to a trade-off between
computational time and quality of the actions selected. Indeed, the more
actions selected at once, the less computational time required, but the less
informed those actions will be.

Another strategy used in planning is called a Monte Carlo tree search (Browne
et al., 2012). The most well-known example of Monte Carlo tree search is
probably the victory of AlphaGo against Lee Sedol — the go world champion — in
2016 (Silver et al., 2016). Interestingly, this method has been used recently
with an active inference agent (Fountas et al., 2020). The simplest version of
this algorithm starts with an empty tree, i.e. a single node representing the
current state. Then, the root node is expanded such that the states that are
reachable from the current state become its children. Those children are
linked to the root node by edges representing the actions leading to those
states. Afterwards, simulations of the environment are run to evaluate how
good those new child states are. In the context of reinforcement learning, the
goodness of the states corresponds to whether or not rewarding terminal states
are reached during the simulations. Similarly, in the context of active
inference, the expected free energy scores the goodness of outcomes. Finally,
the reward or EFE is back-propagated upward in the tree. Iterating this four-
steps process (i.e. selection, expansion, simulation and backpropagation)
furnishes a posterior over the best action to perform next.

##  6 Variational Message Passing

In the previous sections, our focus was on explaining the intuition behind
active inference. The current section is more technical. We begin with the KL
divergence between the variational distribution $Q(x)$ and the true posterior
$P(x|o)$, which underwrites the minimisation of the variational free energy.
Then, we derive two update equations well known from the Bayesian statistics
community. The first explains how the approximate posterior can be computed
using variational inference. And the second reveals that the optimal posterior
can be thought of as a sum of messages. Finally, the message based equation is
specialised for the class of exponential conjugate models that we use to
describe the method of Winn and Bishop (2005) as a five-step process. During
this section, we will be using a few properties that are summarised in
Appendix B.

###  6.1 Justification of the Variational Free Energy

As mentioned in Section 3, the computation of the true posterior — using Bayes
theorem quickly becomes intractable as the number of hidden states increases.
The variational free energy (VFE), or equivalently, the negative evidence
lower bound (-ELBO), aims to solve this intractability problem by
approximating the true posterior with another distribution: the variational
distribution. To justify the use of the variational free energy, let us first
note that the following expression can be obtained from the product rule:

$P(x|o)=\frac{P(o,x)}{P(o)}.$ (84)

Since the KL divergence measures the distance between two distributions, we
can minimise the KL divergence between the variational distribution and the
true posterior. And this will keep the variational distribution close to the
true posterior. Starting with this KL divergence, and substituting Equation 84
within it, we obtain:

$\displaystyle
D_{\mathrm{KL}}\left[\left.\left.Q(x)\right|\right|P(x|o)\right]$
$\displaystyle=D_{\mathrm{KL}}\left[\left.\left.Q(x)\right|\right|P(x,o)\right]+\mathbb{E}_{Q(x)}[\ln
P(o)]$
$\displaystyle=\underbrace{D_{\mathrm{KL}}\left[\left.\left.Q(x)\right|\right|P(x,o)\right]}_{\text{VFE
= -ELBO}}+\underbrace{\ln P(o)}_{\text{log evidence}},$

where the expectation over the log evidence can be dropped due to the lack of
a dependence of $\ln P(o)$ on $Q(x)$. Because the log evidence does not depend
on the latent variables, it can be safely ignored during the minimisation
process. In other words, minimising the variational free energy is equivalent
to minimising the KL divergence between the variational distribution and the
true posterior, and ensuring that the variational distribution is a good
approximation of the true posterior.

###  6.2 Variational Inference Updates

As we have just noted, variational methods rely on the minimisation of the
variational free energy, or equivalently, the maximisation of an evidence
lower bound. So, let us start with the former:

$D_{\mathrm{KL}}\left[\left.\left.Q(x)\right|\right|P(o,x)\right]=\mathbb{E}_{Q(x)}[\ln
Q(x)-\ln P(x,o)].$

Using the mean-field assumption $Q(x)=\prod_{i}Q_{i}(x_{i})$, the log
property, and the linearity of expectation. The above equation can be
rewritten as:

$D_{\mathrm{KL}}\left[\left.\left.Q(x)\right|\right|P(o,x)\right]=\mathbb{E}_{Q(x)}[\ln
Q_{k}(x_{k})]+\mathbb{E}_{Q(x)}[\ln\prod_{j\neq
k}Q_{j}(x_{j})]-\mathbb{E}_{Q(x)}[\ln P(x,o)].$

Note that $\ln Q_{k}(x_{k})$ is a constant w.r.t all factors but
$Q_{k}(x_{k})$, and $\ln\prod_{j\neq k}Q_{j}(x_{j})$ is a constant w.r.t
$Q_{k}(x_{k})$. Using the expectation of a constant, the above equation can be
rewritten as:

$D_{\mathrm{KL}}\left[\left.\left.Q(x)\right|\right|P(o,x)\right]=\mathbb{E}_{Q_{k}(x_{k})}[\ln
Q_{k}(x_{k})]+\mathbb{E}_{\sim Q_{k}(x_{k})}[\ln\prod_{j\neq
k}Q_{j}(x_{j})]-\mathbb{E}_{Q(x)}[\ln P(x,o)],$

where $\mathbb{E}_{\sim Q_{k}(x_{k})}[\cdot]$ is the expectation over all
factors but $Q_{k}(x_{k})$. If the goal is to minimise the free energy w.r.t
$Q_{k}(x_{k})$, the second term can be safely considered as a constant $C$.
Also, using the factorisation of the variational distribution, the third term
can be rewritten as $\mathbb{E}_{Q_{k}(x_{k})}[\mathbb{E}_{\sim
Q_{k}(x_{k})}[\ln P(x,o)]]$, leading to:

$\displaystyle
D_{\mathrm{KL}}\left[\left.\left.Q(x)\right|\right|P(o,x)\right]$
$\displaystyle=\mathbb{E}_{Q_{k}(x_{k})}[\ln
Q_{k}(x_{k})]-\mathbb{E}_{Q_{k}(x_{k})}[\mathbb{E}_{\sim Q_{k}(x_{k})}[\ln
P(x,o)]]+C$ $\displaystyle=\mathbb{E}_{Q_{k}(x_{k})}\Big{[}\ln
Q_{k}(x_{k})-\mathbb{E}_{\sim Q_{k}(x_{k})}[\ln P(x,o)]\Big{]}+C$
$\displaystyle\mathrel{\ensurestackMath{\stackon[1pt]{=}{\scriptstyle\Delta}}}\mathbb{E}_{Q_{k}(x_{k})}\Big{[}\ln
Q_{k}(x_{k})-\ln Q_{k}^{*}(x_{k})\Big{]}+C$
$\displaystyle=D_{\mathrm{KL}}\left[\left.\left.Q_{k}(x_{k})\right|\right|Q_{k}^{*}(x_{k})\right]+C,$

where $\mathrel{\ensurestackMath{\stackon[1pt]{=}{\scriptstyle\Delta}}}$ means
equal by definition, and $\ln
Q_{k}^{*}(x_{k})\mathrel{\ensurestackMath{\stackon[1pt]{=}{\scriptstyle\Delta}}}\mathbb{E}_{\sim
Q_{k}(x_{k})}[\ln P(x,o)]$. The KL divergence can not be negative which means
that $Q_{k}(x_{k})=Q_{k}^{*}(x_{k})$ minimises the free energy, and for this
reason $Q_{k}^{*}(x_{k})$ is called the optimal posterior.

###  6.3 Variational Message Passing Updates

Restarting with the definition of $Q_{k}^{*}(x_{k})$ and using the
factorisation of the generative model, we get:

$\displaystyle\ln Q_{k}^{*}(x_{k})$
$\displaystyle\mathrel{\ensurestackMath{\stackon[1pt]{=}{\scriptstyle\Delta}}}\mathbb{E}_{\sim
Q_{k}(x_{k})}[\ln P(x,o)]$ $\displaystyle=\mathbb{E}_{\sim
Q_{k}(x_{k})}[\ln\prod_{i}P(N_{i}|\text{pa}_{i})],$

where $N_{i}$ iterates over all nodes, i.e. all latent and observed variables,
and $\text{pa}_{i}$ are the parents of $N_{i}$. The term in the above product
can be classified into three groups: the terms that do not depend on $x_{k}$,
the terms whose target variable ($N_{i}$) is $x_{k}$ and the terms whose
predictors ($\text{pa}_{i}$) contains $x_{k}$. Building on this observation,
one can use the log property and the linearity of expectation to isolate the
terms that depend on $x_{k}$:

$\displaystyle\ln Q_{k}^{*}(x_{k})$
$\displaystyle=\langle\ln\prod_{i}P(N_{i}|\text{pa}_{i})\rangle_{\sim Q_{k}}$
$\displaystyle=\langle\ln
P(x_{k}|{\color[rgb]{.75,0,.25}\definecolor[named]{pgfstrokecolor}{rgb}{.75,0,.25}\text{pa}_{k}})\rangle_{\sim
Q_{k}}+\sum_{c_{j}\in{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\text{ch}_{k}}}\langle\ln
P(c_{j}|x_{k},{\color[rgb]{.5,0,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,0,.5}\text{cp}_{kj}})\rangle_{\sim
Q_{k}}+C,$ (85)

where $\langle\cdot\rangle_{\sim Q_{k}}$ is just another notation for
$\mathbb{E}_{\sim Q_{k}(x_{k})}[\cdot]$, and the constant $C$ comes from the
terms of the product that do not depend on $x_{k}$. Equation 85 is the
variational message passing equation that tells us how to compute the optimal
posterior of any hidden state $x_{k}$ based on its Markov blanket, i.e.
$x_{k}$’s parents
${\color[rgb]{.75,0,.25}\definecolor[named]{pgfstrokecolor}{rgb}{.75,0,.25}\text{pa}_{k}}$,
children
${\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\text{ch}_{k}}$
and co-parents
${\color[rgb]{.5,0,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,0,.5}\text{cp}_{kj}}$.
For readers unfamiliar with the notion of Markov blankets, Figure 12 provides
a visual depiction of the underlying notion.

Figure 12: This figure illustrates the Markov blanket of node $\bm{A}$, which
is drawn in grey surrounded by a dashed line. The nodes
${\color[rgb]{0.01,0.75,0.24}\definecolor[named]{pgfstrokecolor}{rgb}{0.01,0.75,0.24}F}$
and
${\color[rgb]{0.01,0.75,0.24}\definecolor[named]{pgfstrokecolor}{rgb}{0.01,0.75,0.24}G}$
are the parents of $\bm{A}$ and the nodes
${\color[rgb]{0,0,0.5}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.5}C}$ and
${\color[rgb]{0,0,0.5}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.5}D}$ are
the children of $\bm{A}$. The node
${\color[rgb]{0.5,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.5,0,0}E}$ is
the co-parent of $\bm{A}$ with respect to
${\color[rgb]{0,0,0.5}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.5}D}$ and
the node
${\color[rgb]{0.5,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.5,0,0}B}$ is
the co-parent of $\bm{A}$ with respect to
${\color[rgb]{0,0,0.5}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.5}C}$.

###  6.4 Conjugate exponential model

The variational message passing algorithm can be derived for the class of
conjugate exponential models (Winn and Bishop, 2005). Those models have a
likelihood function and a prior in the exponential family. Furthermore, the
prior and the likelihood are conjugate, meaning that the posterior will have
the same form as the prior. We follows the steps in Winn and Bishop, while
referring the interested reader to (Winn and Bishop, 2005) for more details.
The derivations in equations 86-90 are clarified in the example in Figure 13.

Returning to our goal of computing the posterior over $x_{k}$ (cf. Equation
85), we assume that $P(x_{k}|\text{pa}_{k})$ and
$P(c_{j}|x_{k},\text{cp}_{kj})$ are in the exponential family, i.e.

$\displaystyle\ln
P(x_{k}|\text{pa}_{k})={\color[rgb]{0.828125,0.69140625,0.05859375}\definecolor[named]{pgfstrokecolor}{rgb}{0.828125,0.69140625,0.05859375}\mu_{k}}(\text{pa}_{k})\cdot{\color[rgb]{.75,0,.25}\definecolor[named]{pgfstrokecolor}{rgb}{.75,0,.25}u_{k}}(x_{k})+{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}h_{k}}(x_{k})+z_{k}(\text{pa}_{k})$
(86) $\displaystyle\ln
P(c_{j}|x_{k},\text{cp}_{kj})=\mu_{j}(x_{k},\text{cp}_{kj})\cdot
u_{j}(c_{j})+h_{j}(c_{j})+z_{j}(x_{k},\text{cp}_{kj})$ (87)

where $\mu_{k}(\text{pa}_{k})$, $u_{k}(x_{k})$, $h_{k}(x_{k})$ and
$z_{k}(\text{pa}_{k})$ are the parameters, the sufficient statistics, the
underlying measure and the log partition, respectively. For a specific
example, Equation 92 shows the Dirichlet distribution written in the form of
the exponential family. The first step of the Winn and Bishop method takes
advantage of the conjugacy constraint to re-arrange Equation 87 as a function
of $u_{k}(x_{k})$ that appears in Equation 86:

$\displaystyle\ln
P(c_{j}|x_{k},\text{cp}_{kj})={\color[rgb]{0.01,0.75,0.24}\definecolor[named]{pgfstrokecolor}{rgb}{0.01,0.75,0.24}\mu_{j\rightarrow
k}}(c_{j},\text{cp}_{kj})\cdot{\color[rgb]{.75,0,.25}\definecolor[named]{pgfstrokecolor}{rgb}{.75,0,.25}u_{k}}(x_{k})+\lambda(c_{j},\text{cp}_{kj}),$
(88)

where $\mu_{j\rightarrow k}(c_{j},\text{cp}_{kj})$ and
$\lambda(c_{j},\text{cp}_{kj})$ emerge from the re-arrangement. For a specific
example of this first step, the reader is referred to the derivation from (93)
to (94), Figure 13 also provides an example of $\mu_{j\rightarrow
k}(c_{j},\text{cp}_{kj})$. The second step substitutes Equations 88 and 86
within the variational message passing equation leading to:

$\displaystyle\ln Q_{k}^{*}(x_{k})$
$\displaystyle=\langle{\color[rgb]{0.828125,0.69140625,0.05859375}\definecolor[named]{pgfstrokecolor}{rgb}{0.828125,0.69140625,0.05859375}\mu_{k}}(\text{pa}_{k})\cdot{\color[rgb]{.75,0,.25}\definecolor[named]{pgfstrokecolor}{rgb}{.75,0,.25}u_{k}}(x_{k})+{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}h_{k}}(x_{k})+z_{k}(\text{pa}_{k})\rangle_{\sim
Q_{k}}$
$\displaystyle+\sum_{c_{j}\in\text{ch}_{k}}\langle{\color[rgb]{0.01,0.75,0.24}\definecolor[named]{pgfstrokecolor}{rgb}{0.01,0.75,0.24}\mu_{j\rightarrow
k}}(c_{j},\text{cp}_{kj})\cdot{\color[rgb]{.75,0,.25}\definecolor[named]{pgfstrokecolor}{rgb}{.75,0,.25}u_{k}}(x_{k})+\lambda(c_{j},\text{cp}_{kj})\rangle_{\sim
Q_{k}}+\text{Const}.$

The third step relies on taking the exponential of both sides, using the
linearity of expectation and factorising by $u_{k}(x_{k})$ to obtain:

$\displaystyle Q_{k}^{*}(x_{k})$
$\displaystyle=\exp\Bigg{\\{}\Big{[}\langle{\color[rgb]{0.828125,0.69140625,0.05859375}\definecolor[named]{pgfstrokecolor}{rgb}{0.828125,0.69140625,0.05859375}\mu_{k}}(\text{pa}_{k})\rangle_{\sim
Q_{k}}+\sum_{c_{j}\in\text{ch}_{k}}\langle{\color[rgb]{0.01,0.75,0.24}\definecolor[named]{pgfstrokecolor}{rgb}{0.01,0.75,0.24}\mu_{j\rightarrow
k}}(c_{j},\text{cp}_{kj})\rangle_{\sim
Q_{k}}\Big{]}\cdot{\color[rgb]{.75,0,.25}\definecolor[named]{pgfstrokecolor}{rgb}{.75,0,.25}u_{k}}(x_{k})+{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}h_{k}}(x_{k})+\text{Const}\Bigg{\\}},$
(89)

where the above constant just absorbed $z_{k}(\text{pa}_{k})$ and
$\lambda(c_{j},\text{cp}_{kj})$, which does not depend on $x_{k}$. At this
point, we already see that the prior (86) and the approximate posterior (89)
have the same functional form, i.e., only their parameters differ. The fourth
step re-parameterizes $\mu_{k}(\text{pa}_{k})$ and $\mu_{j\rightarrow
k}(c_{j},\text{cp}_{kj})$ in terms of the expectation of the sufficient
statistics of the children, parents and the co-parents:

$\displaystyle Q_{k}^{*}(x_{k})$
$\displaystyle=\exp\Bigg{\\{}{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\mu_{k}^{*}}\cdot{\color[rgb]{.75,0,.25}\definecolor[named]{pgfstrokecolor}{rgb}{.75,0,.25}u_{k}}(x_{k})+{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}h_{k}}(x_{k})+\text{Const}\Bigg{\\}}$
$\displaystyle{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\mu_{k}^{*}}={\color[rgb]{0.828125,0.69140625,0.05859375}\definecolor[named]{pgfstrokecolor}{rgb}{0.828125,0.69140625,0.05859375}\tilde{\mu}_{k}}(\\{{\color[rgb]{.5,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,.5,.5}\pgfsys@color@gray@stroke{.5}\pgfsys@color<EMAIL_ADDRESS>u_{i}(i)\rangle_{Q_{i}}}\\}_{i\in\text{pa}_{k}})+\sum_{c_{j}\in\text{ch}_{k}}{\color[rgb]{0.01,0.75,0.24}\definecolor[named]{pgfstrokecolor}{rgb}{0.01,0.75,0.24}\tilde{\mu}_{j\rightarrow
k}}({\color[rgb]{.5,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,.5,.5}\pgfsys@color@gray@stroke{.5}\pgfsys@color<EMAIL_ADDRESS>u_{j}(c_{j})\rangle_{Q_{j}}},\\{{\color[rgb]{.5,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,.5,.5}\pgfsys@color@gray@stroke{.5}\pgfsys@color<EMAIL_ADDRESS>u_{l}(l)\rangle_{Q_{l}}}\\}_{l\in\text{cp}_{kj}}),$ (90)

where
${\color[rgb]{0.828125,0.69140625,0.05859375}\definecolor[named]{pgfstrokecolor}{rgb}{0.828125,0.69140625,0.05859375}\tilde{\mu}_{k}}$
is a re-parameterization of
${\color[rgb]{0.828125,0.69140625,0.05859375}\definecolor[named]{pgfstrokecolor}{rgb}{0.828125,0.69140625,0.05859375}\mu_{k}}(pa_{k})$
in terms of the expectation of the sufficient statistic of the parents of
$x_{k}$, and similarly
${\color[rgb]{0.01,0.75,0.24}\definecolor[named]{pgfstrokecolor}{rgb}{0.01,0.75,0.24}\tilde{\mu}_{j\rightarrow
k}}$ is a re-parameterization of
${\color[rgb]{0.01,0.75,0.24}\definecolor[named]{pgfstrokecolor}{rgb}{0.01,0.75,0.24}\mu_{j\rightarrow
k}}$. The exact form of
${\color[rgb]{0.828125,0.69140625,0.05859375}\definecolor[named]{pgfstrokecolor}{rgb}{0.828125,0.69140625,0.05859375}\tilde{\mu}_{k}}$
and
${\color[rgb]{0.01,0.75,0.24}\definecolor[named]{pgfstrokecolor}{rgb}{0.01,0.75,0.24}\mu_{j\rightarrow
k}}$ vary from distribution to distribution. An example of those re-
parameterizations is visible from Equation 95 to 96.

To understand the intuition behind (90), let us consider the following
example: given the Forney factor graph illustrated in Figure 13, we wish to
compute the posterior of $Y$. Then, the only parent of $Y$ is $Z$, the only
child of $Y$ is $X$ and the only co-parent of $Y$ with respect to $X$ is $W$.
Therefore, applying equation 90 to our example leads to the equation presented
in Figure 13 whose components can be interpreted as messages. Indeed, each
variable (i.e. $X$, $Z$ and $W$) sends the expectation of their sufficient
statistic (i.e. a message) to the square node in the direction of Y (i.e.
either $P_{X}$ or $P_{Y}$). Those messages are then combined using a function
(i.e. either $\tilde{\mu}_{Y}$ or $\tilde{\mu}_{X\rightarrow Y}$) whose output
(i.e. another set of messages) are summed to obtain the optimal parameters
$\mu_{Y}^{*}$. The computation of the optimal parameters (90) can then be
understood as a message passing procedure.

Figure 13: This figure illustrates the computation of the optimal posterior
parameters for the variable $Y$ as a message passing procedure, which requires
the transmission of messages from the parent
(${\color[rgb]{0.828125,0.69140625,0.05859375}\definecolor[named]{pgfstrokecolor}{rgb}{0.828125,0.69140625,0.05859375}\text{m}_{2}}$)
and child
(${\color[rgb]{0.01,0.75,0.24}\definecolor[named]{pgfstrokecolor}{rgb}{0.01,0.75,0.24}\text{m}_{3}}$)
factors. Additionally, the message from the child factor
(${\color[rgb]{0.01,0.75,0.24}\definecolor[named]{pgfstrokecolor}{rgb}{0.01,0.75,0.24}\text{m}_{3}}$)
requires the computation of messages from the co-parent
(${\color[rgb]{0.5,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.5,0,0}\text{m}_{4}}$)
and child
(${\color[rgb]{0,0,0.5}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.5}\text{m}_{5}}$)
variables. Also, the message from the parent
(${\color[rgb]{0.828125,0.69140625,0.05859375}\definecolor[named]{pgfstrokecolor}{rgb}{0.828125,0.69140625,0.05859375}\text{m}_{2}}$)
factor requires the computation of a message
(${\color[rgb]{0.56,0.14,0.56}\definecolor[named]{pgfstrokecolor}{rgb}{0.56,0.14,0.56}\text{m}_{1}}$)
from the parent variable. Set notation and associated brackets {} have been
dropped, since there is only ever one parent or co-parent.

Returning to the Winn and Bishop (2005) method, the last step computes the
(set of) expectations associated with
$\\{{\color[rgb]{.5,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,.5,.5}\pgfsys@color@gray@stroke{.5}\pgfsys@color<EMAIL_ADDRESS>u_{j}(j)\rangle_{Q_{j}}}\\}_{j\in\text{pa}_{Y}}$,
${\color[rgb]{.5,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,.5,.5}\pgfsys@color@gray@stroke{.5}\pgfsys@color<EMAIL_ADDRESS>u_{X}(X)\rangle_{Q_{X}}}$, and
$\\{{\color[rgb]{.5,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,.5,.5}\pgfsys@color@gray@stroke{.5}\pgfsys@color<EMAIL_ADDRESS>u_{j}(j)\rangle_{Q_{j}}}\\}_{j\in\text{cp}_{YX}}$. Because all nodes of the
model are in the exponential family, the moment generating function can be
used to prove the following:

$\displaystyle{\color[rgb]{.5,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{.5,.5,.5}\pgfsys@color@gray@stroke{.5}\pgfsys@color<EMAIL_ADDRESS>u_{N}(N)\rangle_{Q_{N}}}=-\frac{\partial\tilde{z}_{N}(\theta_{N})}{\partial\theta_{N}},$
(91)

where $N$ is any node of the graphical model, $\theta_{N}$ are the natural
parameters of the distribution over $N$, and $\tilde{z}_{Z}(\theta_{N})$ is a
re-parameterisation of the log partition w.r.t the natural parameters of the
distribution over $Z$. Note that another way to compute those expectations
will be presented in Section 7.3.

##  7 The link between Active Inference and Variational Message Passing

The previous sections have presented the theory behind active inference and
variational message passing. This section focuses on the link between those
two frameworks. First, we slightly modify the generative model and the
variational distribution. These modifications concern a small part of the
generative model and to ensure conjugacy between the random variables of the
model. Then, we derive new update equations based on the Winn and Bishop
method (Winn and Bishop, 2005). As we will see, those updates can be
interpreted as a passing of messages that highlight the connection between
variational message passing and belief updating in (planning as) active
inference.

###  7.1 Generative model modifications

In order to perform variational message passing, we have made three
modifications to the generative model described by Equation 74. First, the
prior over the precision parameter $\gamma$ is removed. Second, the softmax
function forming the prior over the policies is transformed into a categorical
distribution with parameters $\alpha$. This is a mild modification because the
softmax function is frequently used to represent a categorical distribution,
e.g. neural classifiers using a softmax function as output layer or similarly
to the updates of $Q(s_{\tau})$ and $Q(\pi)$ presented in Section 5.4.
Finally, we assume a Dirichlet distribution over the parameters $\alpha$.
Figure 14 illustrates this new generative model where:

$\displaystyle P(\pi|\alpha)$ $\displaystyle=\text{Cat}(\pi;\alpha)$
$\displaystyle P(\alpha)$ $\displaystyle=\text{Dir}(\alpha;\theta).$

The conjugacy between the Dirichlet and categorical distributions enables us
to derive update equations that can be interpreted as messages. Recall that
the prior over policies was used to bias the policy selection towards the
policies that minimise expected free energy. This can be implemented in a
straightfoward way — while preserving conjugacy — by setting the parameters of
the Dirichlet as follows:

$\displaystyle\theta=\overrightarrow{c}-\bm{G},$

where $\bm{G}$ is the expected free energy and $\overrightarrow{c}$ is a
vector of constants whose elements satisfy the following properties:

  1. 1.

$\forall i,j:\overrightarrow{c}_{i}=\overrightarrow{c}_{j}$, i.e. all elements
are equal;

  2. 2.

$\forall j:\overrightarrow{c}_{j}>\max_{i}\bm{G}_{i}$, i.e. all $\theta_{j}$
are strictly positive.

To better understand the influence of $P(\alpha)$ on the selection of
policies, we imagine a Dirichlet with $K$ parameters as a distribution over a
$(K-1)$-simplex. Assuming that all $\theta_{i}$ are greater than one, the
point of this simplex with the highest probability, i.e. the mode
$m_{\alpha}$, has the following coordinates:

$m_{\alpha}=\begin{bmatrix}\frac{\theta_{1}-1}{\big{(}\sum_{k=1}^{K}\theta_{k}\big{)}-K}&\ldots&\frac{\theta_{K}-1}{\big{(}\sum_{k=1}^{K}\theta_{k}\big{)}-K}\end{bmatrix}.$

Studying a few special cases of the above equation sheds some light on how
policy selection is influenced by $P(\alpha)$. If the i-th numerator of the
coordinates, i.e. $\theta_{i}-1$, equal one and all others equal zero, then
the mode $m_{\alpha}$ is at the corner of the simplex corresponding to the
i-th axis. If all numerators are equal to one, then the mode is at the centre
of the simplex. Intuitively, this means that the bigger $\theta_{i}$ is
relative to the other $\theta_{j}\,\,\forall j\neq i$, the closer $m_{\alpha}$
is to the i-th corner of the simplex. Additionally, the closer $m_{\alpha}$ is
to the i-th corner of the simplex, the more likely the i-th policy will be.
Therefore, the bigger $\theta_{i}$ the more likely the i-th policy. Finally,
the only part of the numerators that is not a constant is $\bm{G}_{i}$ and the
smaller $\bm{G}_{i}$ the bigger the i-th numerator. Thus, in accord with the
active inference literature, $P(\alpha)$ favours policies that minimise the
expected free energy.

Another perspective on this parameterisation of priors over policies is to
think of $\overrightarrow{c}$ as pseudo-counts that ‘promote’ each policy
according to how often it was previously pursued, before adding (-ve) expected
free energy. If these pseudo-counts are suitably small, adding expected free
energy will have a greater effect in the sense that expected free energy
scores the number of times each policy would be pursued. Quantitatively, this
means that a difference in the expected free energy between one policy and
another can now be interpreted in terms of Dirichlet parameters or pseudo-
counts.

It could be argued that the Dirichlet parameterisation of the prior over
policies is a more natural parameterisation than the gamma distribution used
to explain dopamine. Furthermore, as noted above, in most applications, gamma
is set to one. More importantly, the precision parameter is only relevant for
generative models where policies entail past transitions. In look-ahead
policies or tree search implementations of planning, policies only concern
future states. This means the precision of prior beliefs about policies
relative to posterior beliefs (based upon the evidence a particular policy is
being pursued) becomes irrelevant. In this case, the Dirichlet
parameterisation above may be preferred.

Figure 14: The new generative model obtained after replacing the gamma
distribution by a Dirichlet distribution.

###  7.2 Variational distribution modifications

The variational distribution presented in Section 5.2 is an example of a
structured variational distribution, because factors such as
$Q(S_{\tau},\pi)=Q(S_{\tau}|\pi)Q(\pi)$ model the (posterior) dependency
between $S_{\tau}$ and $\pi$. Performing inference with such a joint
distribution falls under the category of structured variational inference
(Wiegerinck, 2000; Xing et al., 2012) and will not be covered in this paper.
Instead, we assume a fully factorised distribution such that:

$\displaystyle
Q(S_{0:T},\pi,\bm{A},\bm{B},\bm{D},\gamma)=Q(\pi)Q(\bm{A})Q(\bm{B})Q(\bm{D})Q(\gamma)\prod_{\tau=0}^{T}Q(S_{\tau}),$

where $Q(\pi)=\text{Cat}(\pi;\tilde{\alpha})$,
$Q(S_{\tau})=\text{Cat}(S_{\tau};\tilde{\bm{D}}_{\tau})$ and all the other
factors remain unchanged. This is a rather severe mean-field approximation:
although it allows for straightforward application of variational message
passing, removing the conditional dependencies of hidden states in the future
on action means the agent cannot individuate the consequences of action. Under
this functional form the expected free energy reduces to:

$\displaystyle\bm{G}(\pi)=\sum_{\tau=1}^{T}\mathbb{E}_{Q(S_{\tau-1},\bm{B})}\Big{[}\text{H}[P(S_{\tau}|S_{\tau-1},\bm{B},\pi)]\Big{]}.$

Namely, the expected conditional entropy of the hidden states. Also, we refer
the interested reader to Appendix H for a derivation of the above equation.
Intuitively, this means that good policies select actions that lead to
unambiguous hidden states. This highlights a major limitation of the mean-
field approximation required by the variational message passing proposed by
(Winn and Bishop, 2005) in the context of active inference. In other words,
when removing key structure from the variational distribution, the factor over
the hidden states $Q(S_{\tau}|\pi)$ no longer depends on the policy $\pi$ and
most of the terms in the expected free energy become constants w.r.t $\pi$.
Figure 15 illustrates an alternative generative model, implementing tree
search as a form of structure learning, which is not impacted by this issue
because the future states in this model still depend upon the action
undertaken by the agent. We refer the reader to our companion paper (Champion
et al., 2021) for details. A related treatment that performs exact Bayesian
inference by considering a slightly different generative model can be found in
(Friston et al., 2020).

Before we turn to the derivation of the messages, we highlight the differences
between active inference as presented in Section 5 and the current treatment.
The former is an example of structured variational inference
$({\color[rgb]{0,0,0.5}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.5}*})$.
In contrast, the work presented in this section assumes a fully factorised
variational distribution and will be strictly framed as a message passing
algorithm, i.e. variational message passing
$({\color[rgb]{0.5,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.5,0,0}*})$.
Figure 16 illustrates those differences. Finally, in the remaining sections,
we present the derivation of the messages for $\bm{D}$, $\bm{A}$, $\pi$ and
$\alpha$, and we refer the reader to Appendices F and G for the derivations of
the messages for $\bm{B}$ and $S_{\tau}$, respectively.

Figure 15:  This figure illustrates an alternative new (expandable) generative
model allowing planning under active inference. In this model, the future is
now a tree like generative model whose branches correspond to the policies
considered by the agent. Each edge connecting two states in the future
correspond to an action and the nodes in light grey represent possible
expansions of the current generative model. Figure 16:  This figure
illustrates the differences between the framework presented in Section 5 that
belongs to the field of structured variational inference (Bishop and Winn,
2003) denoted by
(${\color[rgb]{0,0,0.5}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.5}*}$),
and the work presented below that belongs to the field of variational message
passing (Winn and Bishop, 2005) denoted by
(${\color[rgb]{0.5,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.5,0,0}\times}$).
The other abbreviations BPT, E, VI and SVMP correspond to belief propagation
on tree graphical models (Kschischang et al., 2001), the elimination algorithm
(Cozman, 2000), variational inference (Blei et al., 2017) and structured (or
cluster) variational message passing (Lin et al., 2018), respectively.
Importantly, note that BPT is a specific kind of belief propagation which does
not involve generalized BP (Yedidia et al., 2000) or loopy belief propagation
(Murphy et al., 2013).

###  7.3 Messages for D

This section applies the method of Winn and Bishop discussed in Section 6.4 to
compute the messages of $\bm{D}$. Let us start with the definition of the
Dirichlet and categorical distributions written in the form of the exponential
family:

$\displaystyle\ln P(\bm{D};d)$
$\displaystyle=\underbrace{\begin{bmatrix}d_{1}-1\\\ ...\\\
d_{|S|}-1\end{bmatrix}}_{\mu_{D}(d)}\cdot\underbrace{\begin{bmatrix}\ln\bm{D}_{1}\\\
...\\\ \ln\bm{D}_{|S|}\end{bmatrix}}_{u_{D}(\bm{D})}\underbrace{-\ln
B(d)}_{z_{D}(d)}$ (92)

$\displaystyle\ln P(S_{0};\bm{D})$
$\displaystyle=\underbrace{\begin{bmatrix}\ln\bm{D}_{1}\\\ ...\\\
\ln\bm{D}_{|S|}\end{bmatrix}}_{\mu_{S0}(\bm{D})}\cdot\underbrace{\begin{bmatrix}[S_{0}=1]\\\
...\\\ [S_{0}=|S|]\end{bmatrix}}_{u_{S0}(S_{0})}$ (93)

where $B(d)$ is the Beta function and $|S|$ is the number of values a hidden
state can take. The first step requires us to re-write Equation 93 as a
function of $u_{D}(\bm{D})$, this is straightforward because
$\mu_{S0}(\bm{D})$ is just another name for $u_{D}(\bm{D})$. Using the fact
that the inner product is commutative:

$\displaystyle\ln P(S_{0};\bm{D})$
$\displaystyle=\underbrace{\begin{bmatrix}[S_{0}=1]\\\ ...\\\
[S_{0}=|S|]\end{bmatrix}}_{\mu_{S_{0}\rightarrow\bm{D}}(S_{0})}\cdot\underbrace{\begin{bmatrix}\ln\bm{D}_{1}\\\
...\\\ \ln\bm{D}_{|S|}\end{bmatrix}}_{u_{D}(\bm{D})}.$ (94)

The second step aims to substitute Equations 92 and 94 within the variational
message passing equation (85), i.e.

$\displaystyle\ln Q^{*}(\bm{D})$
$\displaystyle=\Big{\langle}\underbrace{\begin{bmatrix}{\color[rgb]{1,.5,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,.5,0}d_{1}-1}\\\
...\\\
{\color[rgb]{1,.5,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,.5,0}d_{|S|}-1}\end{bmatrix}}_{\mu_{D}(d)}\cdot\underbrace{\begin{bmatrix}\ln\bm{D}_{1}\\\
...\\\ \ln\bm{D}_{|S|}\end{bmatrix}}_{u_{D}(\bm{D})}\underbrace{-\ln
B(d)}_{z_{D}(d)}\Big{\rangle}+\Big{\langle}\underbrace{\begin{bmatrix}{\color[rgb]{.75,0,.25}\definecolor[named]{pgfstrokecolor}{rgb}{.75,0,.25}[S_{0}=1]}\\\
...\\\
{\color[rgb]{.75,0,.25}\definecolor[named]{pgfstrokecolor}{rgb}{.75,0,.25}[S_{0}=|S|]}\end{bmatrix}}_{\mu_{S_{0}\rightarrow\bm{D}}(S_{0})}\cdot\underbrace{\begin{bmatrix}\ln\bm{D}_{1}\\\
...\\\
\ln\bm{D}_{|S|}\end{bmatrix}}_{u_{D}(\bm{D})}\Big{\rangle}+\text{Const},$

where
$\langle\mathchoice{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\displaystyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\textstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptscriptstyle\bullet$}}}}}\rangle$
refers to
$\langle\mathchoice{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\displaystyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\textstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptscriptstyle\bullet$}}}}}\rangle_{\sim
Q_{\bm{D}}}$. Note that in the above equation, $d_{i}$ are fixed parameters,
therefore there is not any posterior over $d$ and the first expectation
$\langle\cdot\rangle_{\sim Q_{\bm{D}}}$ can be removed. The third step rests
on taking the exponential of both sides, using the linearity of expectation
and factorising by $u_{D}(\bm{D})$ to obtain:

$\displaystyle Q^{*}(\bm{D})$
$\displaystyle=\exp\Bigg{\\{}\begin{bmatrix}{\color[rgb]{1,.5,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,.5,0}d_{1}-1}+\langle{\color[rgb]{.75,0,.25}\definecolor[named]{pgfstrokecolor}{rgb}{.75,0,.25}[S_{0}=1]}\rangle\\\
...\\\
{\color[rgb]{1,.5,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,.5,0}d_{|S|}-1}+\langle{\color[rgb]{.75,0,.25}\definecolor[named]{pgfstrokecolor}{rgb}{.75,0,.25}[S_{0}=|S|]}\rangle\end{bmatrix}\cdot
u_{D}(\bm{D})+\text{Const}\Bigg{\\}},$ (95)

where $z_{D}(d)$ have been absorbed into the constant term because it does not
depend on $\bm{D}$. The fourth step is a re-parameterisation done by observing
that $\langle[S_{0}=i]\rangle$ is the i-th element of the expectation of the
vector $u_{S0}(S_{0})$, i.e. $\langle
u_{S0}(S_{0})\rangle_{i}=\langle[S_{0}=i]\rangle$:

$\displaystyle Q^{*}(\bm{D})$
$\displaystyle=\exp\Bigg{\\{}\underbrace{\begin{bmatrix}{\color[rgb]{1,.5,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,.5,0}d_{1}-1}+\langle{\color[rgb]{.75,0,.25}\definecolor[named]{pgfstrokecolor}{rgb}{.75,0,.25}u_{S0}(S_{0})}\rangle_{1}\\\
...\\\
{\color[rgb]{1,.5,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,.5,0}d_{|S|}-1}+\langle{\color[rgb]{.75,0,.25}\definecolor[named]{pgfstrokecolor}{rgb}{.75,0,.25}u_{S0}(S_{0})}\rangle_{|S|}\end{bmatrix}}_{\tilde{\mu}_{\bm{D}}(...)+\tilde{\mu}_{S_{0}\rightarrow\bm{D}}(...)}\cdot
u_{D}(\bm{D})+\text{Const}\Bigg{\\}}.$ (96)

The last step consists of computing the expectation of $\langle
u_{S0}(S_{0})\rangle_{i}$ for all $i$. This can be achieved by realising that
the probability of an indicator function for an event is the probability of
this event, i.e $\langle
u_{S_{0}}(S_{0})\rangle_{i}=\langle[S_{0}=i]\rangle=Q(S_{0}=i)=\tilde{\bm{D}}_{0i}$.
Substituting this result in Equation 96, leads to the final result:

$\displaystyle Q^{*}(\bm{D})$
$\displaystyle=\exp\Bigg{\\{}\begin{bmatrix}{\color[rgb]{1,.5,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,.5,0}d_{1}-1}+{\color[rgb]{.75,0,.25}\definecolor[named]{pgfstrokecolor}{rgb}{.75,0,.25}\tilde{\bm{D}}_{01}}\\\
...\\\
{\color[rgb]{1,.5,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,.5,0}d_{|S|}-1}+{\color[rgb]{.75,0,.25}\definecolor[named]{pgfstrokecolor}{rgb}{.75,0,.25}\tilde{\bm{D}}_{0|S|}}\end{bmatrix}\cdot
u_{D}(\bm{D})+\text{Const}\Bigg{\\}}.$

Indeed, the above equation is in fact a Dirichlet distribution in exponential
family form, and can be re-written into its usual form to obtain the final
update equation:

$\displaystyle Q^{*}(\bm{D})$
$\displaystyle=\text{Dir}(\bm{D};{\color[rgb]{1,.5,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,.5,0}d}+{\color[rgb]{.75,0,.25}\definecolor[named]{pgfstrokecolor}{rgb}{.75,0,.25}\tilde{\bm{D}}_{0}}).$

In the following sections, we provide derivations for the messages of
$\bm{A}$, $\bm{B}$, $\pi$, $\alpha$, and $S_{\tau}$. Those derivations are
similar to the one presented above. We encourage technical readers to go
through those derivations because they constitute the main contribution of
this paper. However, a reader uninterested in the algebraic details of the
proofs may want to jump to Section 7.7.

###  7.4 Messages for A

In the previous section, we have shown how to compute the messages for
$\bm{D}$, which are based on the conjugacy between a categorical
$P(S_{0}|\bm{D})$ and a Dirichlet $P(\bm{D};d)$ distributions. In this
section, we dive into the derivation of the messages of $\bm{A}$, which relies
on the same kind of conjugacy. We start with the definition of $P(\bm{A};a)$,
which is a product of Dirichlet distributions. This product can be turned into
a sum by taking the logarithm of both sides and using the log property to
obtain:

$\displaystyle\ln P(\bm{A};a)$
$\displaystyle=\ln\prod_{i}P(\bm{A}_{\mathchoice{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\displaystyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\textstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptscriptstyle\bullet$}}}}}i};a_{\mathchoice{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\displaystyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\textstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptscriptstyle\bullet$}}}}}i})=\sum_{i}\ln\text{Dir}(\bm{A}_{\mathchoice{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\displaystyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\textstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptscriptstyle\bullet$}}}}}i};a_{\mathchoice{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\displaystyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\textstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptscriptstyle\bullet$}}}}}i})$
$\displaystyle=\sum_{i}\underbrace{\begin{bmatrix}a_{1i}-1\\\ ...\\\
a_{|O|i}-1\end{bmatrix}\cdot\begin{bmatrix}\ln\bm{A}_{1i}\\\ ...\\\
\ln\bm{A}_{|O|i}\end{bmatrix}-\ln
B(a_{\mathchoice{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\displaystyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\textstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptscriptstyle\bullet$}}}}}i})}_{\text{Logarithm
of Dirichlet}}$ $\displaystyle=\underbrace{\begin{bmatrix}a_{11}-1\\\ ...\\\
a_{|O||S|}-1\end{bmatrix}}_{\mu_{A}(a)}\cdot\underbrace{\begin{bmatrix}\ln\bm{A}_{11}\\\
...\\\
\ln\bm{A}_{|O||S|}\end{bmatrix}}_{u_{A}(\bm{A})}\underbrace{-\sum_{i}\ln
B(a_{\mathchoice{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\displaystyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\textstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptscriptstyle\bullet$}}}}}i})}_{z_{A}(a)},$
(97)

where $|O|$ is the number of possible outcomes. Note that the vectors
$u_{A}(\bm{A})$ and $\mu_{A}(a)$ step through all the elements of the matrices
$\bm{A}$ and $a$, respectively. Also, for each time step $\tau$ up to the
present time $t$, the random matrix $\bm{A}$ has one child $O_{\tau}$ (see
Figure 14), and its probability mass function $P(O_{\tau}|\bm{A},S_{\tau})$ is
a product of categorical distributions that can be written as:

$\displaystyle\ln P(O_{\tau}=k|\bm{A},S_{\tau}=l)$
$\displaystyle=\ln\bm{A}_{kl}$
$\displaystyle=\sum_{i,j}[O_{\tau}=i][S_{\tau}=j]\ln\bm{A}_{ij}$
$\displaystyle=\underbrace{\begin{bmatrix}[S_{\tau}=1]\ln\bm{A}_{11}\\\ ...\\\
[S_{\tau}=|S|]\ln\bm{A}_{|O||S|}\end{bmatrix}}_{\mu_{O_{\tau}}(\bm{A},S_{\tau})}\cdot\underbrace{\begin{bmatrix}[O_{\tau}=1]\\\
...\\\ [O_{\tau}=|O|]\end{bmatrix}}_{u_{O_{\tau}}(O_{\tau})}.$ (98)

Finally, the re-parameterisation in the fourth step will require the
probability mass function of $S_{\tau}$ (see Figure 14), i.e. the co-parent of
$\bm{A}$ with respect to $O_{\tau}$, to be written in the form of the
exponential family as follows:

$\displaystyle\ln P(S_{\tau}=k|\bm{B},S_{\tau-1}=l,\pi=m)$
$\displaystyle=\ln\bm{B}[U_{\tau-1}^{m}]_{kl}$
$\displaystyle=\sum_{i,j,k,u}[S_{\tau}=i][S_{\tau-1}=j][\pi=k][U_{\tau-1}^{k}=u]\ln\bm{B}[u]_{ij}$
$\displaystyle=\mu_{S_{\tau}}(\bm{B},S_{\tau-1},\pi)\cdot
u_{S_{\tau}}(S_{\tau}),$ (99)

where:

$\displaystyle\mu_{S_{\tau}}(\bm{B},S_{\tau-1},\pi)=\begin{bmatrix}\sum_{j,k,u}[S_{\tau-1}=j][\pi=k][U_{\tau-1}^{k}=u]\ln\bm{B}[u]_{1j}\\\
...\\\
\sum_{j,k,u}[S_{\tau-1}=j][\pi=k][U_{\tau-1}^{k}=u]\ln\bm{B}[u]_{|S|j}\end{bmatrix},$

and:

$\displaystyle u_{S_{\tau}}(S_{\tau})=\begin{bmatrix}[S_{\tau}=1]\\\ ...\\\
[S_{\tau}=|S|]\end{bmatrix}.$

The first step requires us to re-write Equation 7.4 as a function of
$u_{A}(\bm{A})$, this is done by expanding the inner product and re-arranging:

$\displaystyle\ln P(O_{\tau}|\bm{A},S_{\tau})$
$\displaystyle=\underbrace{\begin{bmatrix}[O_{\tau}=1][S_{\tau}=1]\\\ ...\\\
[O_{\tau}=|O|][S_{\tau}=|S|]\end{bmatrix}}_{\mu_{O_{\tau}\rightarrow\bm{A}}(O_{\tau},S_{\tau})}\cdot\underbrace{\begin{bmatrix}\ln\bm{A}_{11}\\\
...\\\ \ln\bm{A}_{|O||S|}\end{bmatrix}}_{u_{A}(\bm{A})}.$ (100)

The second step aims to substitute Equations 7.4 and 100 within the
variational message passing equation (85), i.e.

$\displaystyle\ln Q^{*}(\bm{A})$
$\displaystyle=\Big{\langle}\begin{bmatrix}{\color[rgb]{1,.5,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,.5,0}a_{11}-1}\\\
...\\\
{\color[rgb]{1,.5,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,.5,0}a_{|O||S|}-1}\end{bmatrix}\cdot
u_{A}(\bm{A})\Big{\rangle}+\sum_{\tau=0}^{t}\Big{\langle}\begin{bmatrix}{\color[rgb]{.75,0,.25}\definecolor[named]{pgfstrokecolor}{rgb}{.75,0,.25}[O_{\tau}=1][S_{\tau}=1]}\\\
...\\\
{\color[rgb]{.75,0,.25}\definecolor[named]{pgfstrokecolor}{rgb}{.75,0,.25}[O_{\tau}=|O|][S_{\tau}=|S|]}\end{bmatrix}\cdot
u_{A}(\bm{A})\Big{\rangle}+\text{Const},$

where
$\langle\mathchoice{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\displaystyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\textstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptscriptstyle\bullet$}}}}}\rangle$
refers to
$\langle\mathchoice{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\displaystyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\textstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptscriptstyle\bullet$}}}}}\rangle_{\sim
Q_{\bm{A}}}$. The third step builds on this equation by pulling the sum over
all time steps $\tau$ inside the vector, using the linearity of expectation,
factorising $u_{A}(\bm{A})$, and taking the exponential of both sides:

$\displaystyle Q^{*}(\bm{A})$
$\displaystyle=\exp\Bigg{\\{}\begin{bmatrix}{\color[rgb]{1,.5,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,.5,0}a_{11}-1}+\sum_{\tau=0}^{t}\langle{\color[rgb]{.75,0,.25}\definecolor[named]{pgfstrokecolor}{rgb}{.75,0,.25}[O_{\tau}=1]}\rangle\langle{\color[rgb]{.75,0,.25}\definecolor[named]{pgfstrokecolor}{rgb}{.75,0,.25}[S_{\tau}=1]}\rangle\\\
...\\\
{\color[rgb]{1,.5,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,.5,0}a_{|O||S|}-1}+\sum_{\tau=0}^{t}\langle{\color[rgb]{.75,0,.25}\definecolor[named]{pgfstrokecolor}{rgb}{.75,0,.25}[O_{\tau}=|O|]}\rangle\langle{\color[rgb]{.75,0,.25}\definecolor[named]{pgfstrokecolor}{rgb}{.75,0,.25}[S_{\tau}=|S|]}\rangle\end{bmatrix}\cdot
u_{A}(\bm{A})+\text{Const}\Bigg{\\}},$

where we used that $a_{ji}$ are hyperparameters that are constant w.r.t the
expectation
$\langle\mathchoice{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\displaystyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\textstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptscriptstyle\bullet$}}}}}\rangle_{\sim
Q_{\bm{A}}}$. The fourth step consists of two re-parameterisations performed
by observing that $\langle[O_{\tau}=j]\rangle$ and
$\langle[S_{\tau}=i]\rangle$ are the expectations of the j-th and i-th
elements of the vectors $u_{O_{\tau}}(O_{\tau})$ and $u_{S_{\tau}}(S_{\tau})$,
respectively (cf. Equation 7.4 and 7.4). Substituting those re-
parameterisations in the above equation leads to:

$\displaystyle Q^{*}(\bm{A})$
$\displaystyle=\exp\Bigg{\\{}\underbrace{\begin{bmatrix}{\color[rgb]{1,.5,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,.5,0}a_{11}-1}+\sum_{\tau=0}^{t}\langle{\color[rgb]{.75,0,.25}\definecolor[named]{pgfstrokecolor}{rgb}{.75,0,.25}u_{O_{\tau}}(O_{\tau})}\rangle_{1}\langle{\color[rgb]{.75,0,.25}\definecolor[named]{pgfstrokecolor}{rgb}{.75,0,.25}u_{S_{\tau}}(S_{\tau})}\rangle_{1}\\\
...\\\
{\color[rgb]{1,.5,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,.5,0}a_{KN}-1}+\sum_{\tau=0}^{t}\langle{\color[rgb]{.75,0,.25}\definecolor[named]{pgfstrokecolor}{rgb}{.75,0,.25}u_{O_{\tau}}(O_{\tau})}\rangle_{|O|}\langle{\color[rgb]{.75,0,.25}\definecolor[named]{pgfstrokecolor}{rgb}{.75,0,.25}u_{S_{\tau}}(S_{\tau})}\rangle_{|S|}\end{bmatrix}}_{\tilde{\mu}_{\bm{A}}(...)+\sum_{\tau}\tilde{\mu}_{O_{\tau}\rightarrow\bm{A}}(...)}\cdot
u_{A}(\bm{A})+\text{Const}\Bigg{\\}}.$ (101)

The last step consists of computing the expectation of
$\langle{\color[rgb]{.75,0,.25}\definecolor[named]{pgfstrokecolor}{rgb}{.75,0,.25}u_{O_{\tau}}(O_{\tau})}\rangle_{i}$
and
$\langle{\color[rgb]{.75,0,.25}\definecolor[named]{pgfstrokecolor}{rgb}{.75,0,.25}u_{S_{\tau}}(S_{\tau})}\rangle_{j}$
for all $i$ and $j$. Since, the probability of an indicator function for an
event is the probability of this event, we are searching for the probabilities
of $O_{\tau}=j$ and $S_{\tau}=i$. The probability of $O_{\tau}=j$ is the j-th
element of the vector $\bm{o_{\tau}}$, which is a one hot vector containing
the observation from the environment at time $\tau$. The posterior probability
of $S_{\tau}$ is by definition $Q(S_{\tau})=\tilde{\bm{D}}_{\tau}$.
Substituting the probabilities of $O_{\tau}=j$ and $S_{\tau}=i$ in Equation
101, leads to:

$\displaystyle Q^{*}(\bm{A})$
$\displaystyle=\exp\Bigg{\\{}\begin{bmatrix}{\color[rgb]{1,.5,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,.5,0}a_{11}-1}+\sum_{\tau=0}^{t}{\color[rgb]{.75,0,.25}\definecolor[named]{pgfstrokecolor}{rgb}{.75,0,.25}\bm{o}_{\tau
1}\tilde{\bm{D}}_{\tau 1}}\\\ ...\\\
{\color[rgb]{1,.5,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,.5,0}a_{|O||S|}-1}+\sum_{\tau=0}^{t}{\color[rgb]{.75,0,.25}\definecolor[named]{pgfstrokecolor}{rgb}{.75,0,.25}\bm{o}_{\tau|O|}\tilde{\bm{D}}_{\tau|S|}}\end{bmatrix}\cdot
u_{A}(\bm{A})+\text{Const}\Bigg{\\}}$ (102)
$\displaystyle=\prod_{i}\exp\Bigg{\\{}\begin{bmatrix}{\color[rgb]{1,.5,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,.5,0}a_{1i}-1}+\sum_{\tau=0}^{t}{\color[rgb]{.75,0,.25}\definecolor[named]{pgfstrokecolor}{rgb}{.75,0,.25}\bm{o}_{\tau
1}\tilde{\bm{D}}_{\tau i}}\\\ ...\\\
{\color[rgb]{1,.5,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,.5,0}a_{|O|i}-1}+\sum_{\tau=0}^{t}{\color[rgb]{.75,0,.25}\definecolor[named]{pgfstrokecolor}{rgb}{.75,0,.25}\bm{o}_{\tau|O|}\tilde{\bm{D}}_{\tau
i}}\end{bmatrix}\cdot\begin{bmatrix}\ln\bm{A}_{1i}\\\ ...\\\
\ln\bm{A}_{|O|i}\end{bmatrix}+\text{Const}\Bigg{\\}}.$ (103)

Finally, one can recognise in Equation 103 the product of Dirichlet
distributions written into their exponential form, i.e.

$\displaystyle Q^{*}(\bm{A})$
$\displaystyle=\prod_{i}\text{Dir}(\bm{A}_{\mathchoice{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\displaystyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\textstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptscriptstyle\bullet$}}}}}i},\bm{a}_{\mathchoice{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\displaystyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\textstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptscriptstyle\bullet$}}}}}i})\text{
where
}\bm{a}={\color[rgb]{1,.5,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,.5,0}a}+\sum_{\tau}{\color[rgb]{.75,0,.25}\definecolor[named]{pgfstrokecolor}{rgb}{.75,0,.25}\bm{o}_{\tau}}\otimes{\color[rgb]{.75,0,.25}\definecolor[named]{pgfstrokecolor}{rgb}{.75,0,.25}\tilde{\bm{D}}_{\tau}}.$

The origin of the outer product in the computation of the parameters can be
understood by considering $P^{\tau}$ the outer product between $\bm{o_{\tau}}$
and $\bm{s_{\tau}}$ such that $P^{\tau}_{ij}=\bm{o}_{\tau i}\bm{s}_{\tau j}$.
Then, Equation 102 shows that:
$\bm{a}_{ij}=a_{ij}+\sum_{\tau}P^{\tau}_{ij}\Leftrightarrow\bm{a}=a+\sum_{\tau}\bm{o}_{\tau}\otimes\bm{s}_{\tau}$.

###  7.5 Messages for $\pi$

We now turn to the messages for $\pi$. Note, that the definition of the
$P(S_{\tau}|\bm{B},S_{\tau-1},\pi)$ and $P(\pi|\alpha)$ are given by Equations
7.4 and 111, respectively. The first step requires us to re-write Equation 7.4
as a function of $u_{\pi}(\pi)$. Using the inner product definition and re-
arranging we obtain:

$\displaystyle\ln P(S_{\tau}=k|\bm{B},S_{\tau-1}=l,\pi=m)$
$\displaystyle=\begin{bmatrix}\sum_{i,j,u}[S_{\tau}=i][U_{\tau-1}^{1}=u][S_{\tau-1}=j]\ln\bm{B}[u]_{ij}\\\
...\\\
\sum_{i,j,u}[S_{\tau}=i][U_{\tau-1}^{|\pi|}=u][S_{\tau-1}=j]\ln\bm{B}[u]_{ij}\end{bmatrix}\cdot
u_{\pi}(\pi).$ (104)

The second step aims to substitute Equations 111 and 104 within the
variational message passing equation, i.e.

$\displaystyle\ln Q^{*}(\pi)$
$\displaystyle=\Big{\langle}\begin{bmatrix}{\color[rgb]{1,.5,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,.5,0}\ln\alpha_{1}}\\\
...\\\
{\color[rgb]{1,.5,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,.5,0}\ln\alpha_{|\pi|}}\end{bmatrix}\cdot
u_{\pi}(\pi)\Big{\rangle}$
$\displaystyle+\sum_{\tau=1}^{T}\Big{\langle}\begin{bmatrix}\sum_{i,j,u}{\color[rgb]{.75,0,.25}\definecolor[named]{pgfstrokecolor}{rgb}{.75,0,.25}[S_{\tau}=i][U_{\tau-1}^{1}=u][S_{\tau-1}=j]\ln\bm{B}[u]_{ij}}\\\
...\\\
\sum_{i,j,u}{\color[rgb]{.75,0,.25}\definecolor[named]{pgfstrokecolor}{rgb}{.75,0,.25}[S_{\tau}=i][U_{\tau-1}^{|\pi|}=u][S_{\tau-1}=j]\ln\bm{B}[u]_{ij}}\end{bmatrix}\cdot
u_{\pi}(\pi)\Big{\rangle}+\text{Const},$

where
$\langle\mathchoice{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\displaystyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\textstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptscriptstyle\bullet$}}}}}\rangle$
refers to
$\langle\mathchoice{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\displaystyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\textstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptscriptstyle\bullet$}}}}}\rangle_{\sim
Q_{\pi}}$. The third step relies on pulling the summation over all time steps
inside the vector, taking the exponential of both sides, using the linearity
of expectation and factorising by $u_{\pi}(\pi)$ to obtain:

$\displaystyle Q^{*}(\pi)$
$\displaystyle\propto\exp\Bigg{\\{}\underbrace{\begin{bmatrix}\langle{\color[rgb]{1,.5,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,.5,0}\ln\alpha_{1}}\rangle+\sum_{\tau,i,j,u}{\color[rgb]{.75,0,.25}\definecolor[named]{pgfstrokecolor}{rgb}{.75,0,.25}[U_{\tau-1}^{1}=u]}\langle{\color[rgb]{.75,0,.25}\definecolor[named]{pgfstrokecolor}{rgb}{.75,0,.25}[S_{\tau}=i]}\rangle\langle{\color[rgb]{.75,0,.25}\definecolor[named]{pgfstrokecolor}{rgb}{.75,0,.25}[S_{\tau-1}=j]}\rangle\langle{\color[rgb]{.75,0,.25}\definecolor[named]{pgfstrokecolor}{rgb}{.75,0,.25}\ln\bm{B}[u]_{ij}}\rangle\\\
...\\\
\langle{\color[rgb]{1,.5,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,.5,0}\ln\alpha_{|\pi|}}\rangle+\sum_{\tau,i,j,u}{\color[rgb]{.75,0,.25}\definecolor[named]{pgfstrokecolor}{rgb}{.75,0,.25}[U_{\tau-1}^{|\pi|}=u]}\langle{\color[rgb]{.75,0,.25}\definecolor[named]{pgfstrokecolor}{rgb}{.75,0,.25}[S_{\tau}=i]}\rangle\langle{\color[rgb]{.75,0,.25}\definecolor[named]{pgfstrokecolor}{rgb}{.75,0,.25}[S_{\tau-1}=j]}\rangle\langle{\color[rgb]{.75,0,.25}\definecolor[named]{pgfstrokecolor}{rgb}{.75,0,.25}\ln\bm{B}[u]_{ij}}\rangle\end{bmatrix}}_{\mu^{*}_{\pi}}\cdot
u_{\pi}(\pi)\Bigg{\\}}.$

The fourth step is a re-parameterisation implemented by observing that
$\langle\ln\alpha_{k}\rangle$, $\langle[S_{\tau}=i]\rangle$,
$\langle[S_{\tau-1}=j]\rangle$ and $\langle\ln\bm{B}[u]_{ij}\rangle$ are
elements of the vectors $\langle u_{\alpha}(\alpha)\rangle$, $\langle
u_{S_{\tau}}(S_{\tau})\rangle$, $\langle u_{S_{\tau-1}}(S_{\tau-1})\rangle$
and $\langle u_{B}(\bm{B})\rangle$, respectively:

$\displaystyle\mu^{*}_{\pi}$
$\displaystyle=\begin{bmatrix}\langle{\color[rgb]{1,.5,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,.5,0}u_{\alpha}(\alpha)}\rangle_{1}+\sum_{\tau,i,j,u}{\color[rgb]{.75,0,.25}\definecolor[named]{pgfstrokecolor}{rgb}{.75,0,.25}[U_{\tau-1}^{1}=u]}\langle{\color[rgb]{.75,0,.25}\definecolor[named]{pgfstrokecolor}{rgb}{.75,0,.25}u_{S_{\tau}}(S_{\tau})}\rangle_{i}\langle{\color[rgb]{.75,0,.25}\definecolor[named]{pgfstrokecolor}{rgb}{.75,0,.25}u_{S_{\tau-1}}(S_{\tau-1})}\rangle_{j}\langle{\color[rgb]{.75,0,.25}\definecolor[named]{pgfstrokecolor}{rgb}{.75,0,.25}u_{B}(\bm{B})}\rangle_{u,i,j}\\\
...\\\
\langle{\color[rgb]{1,.5,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,.5,0}u_{\alpha}(\alpha)}\rangle_{|\pi|}+\sum_{\tau,i,j,u}{\color[rgb]{.75,0,.25}\definecolor[named]{pgfstrokecolor}{rgb}{.75,0,.25}[U_{\tau-1}^{|\pi|}=u]}\langle{\color[rgb]{.75,0,.25}\definecolor[named]{pgfstrokecolor}{rgb}{.75,0,.25}u_{S_{\tau}}(S_{\tau})}\rangle_{i}\langle{\color[rgb]{.75,0,.25}\definecolor[named]{pgfstrokecolor}{rgb}{.75,0,.25}u_{S_{\tau-1}}(S_{\tau-1})}\rangle_{j}\langle{\color[rgb]{.75,0,.25}\definecolor[named]{pgfstrokecolor}{rgb}{.75,0,.25}u_{B}(\bm{B})}\rangle_{u,i,j}\end{bmatrix}.$
(105)

The last step consists of computing the expectation of $\langle
u_{\alpha}(\alpha)\rangle_{k}$, $\langle u_{S_{\tau}}(S_{\tau})\rangle_{i}$,
$\langle u_{S_{\tau-1}}(S_{\tau-1})\rangle_{j}$ and $\langle
u_{B}(\bm{B})\rangle_{u,i,j}$ for all $i$, $j$, $k$ and $u$:

  * •

$\langle
u_{\alpha}(\alpha)\rangle_{k}=\langle\ln\alpha_{k}\rangle=\psi(\tilde{\alpha}_{k})-\psi(\sum_{l}\tilde{\alpha}_{l})\mathrel{\ensurestackMath{\stackon[1pt]{=}{\scriptstyle\Delta}}}\bar{\alpha}_{k}$

  * •

$\langle
u_{S_{\tau}}(S_{\tau})\rangle_{i}=\langle[S_{\tau}=i]\rangle=\tilde{\bm{D}}_{\tau
i}$

  * •

$\langle
u_{S_{\tau-1}}(S_{\tau-1})\rangle_{j}=\langle[S_{\tau-1}=j]\rangle=\tilde{\bm{D}}_{(\tau-1)j}$

  * •

$\langle
u_{B}(\bm{B})\rangle_{u,i,j}=\langle\ln\bm{B}[u]_{ij}\rangle=\psi(\bm{b}[u]_{ij})-\psi(\sum_{l}\bm{b}[u]_{lj})\mathrel{\ensurestackMath{\stackon[1pt]{=}{\scriptstyle\Delta}}}\bar{\bm{B}}[u]_{ij}$

Furthermore, the indicator function in the k-th row of Equation 105 filters
out all elements where $u\neq U_{\tau-1}^{k}$. Substituting those results in
Equation 105, leads to the final result:

$\displaystyle Q^{*}(\pi)$
$\displaystyle\propto\exp\Bigg{\\{}\begin{bmatrix}{\color[rgb]{1,.5,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,.5,0}\bar{\alpha}_{1}}+\sum_{\tau,i,j}{\color[rgb]{.75,0,.25}\definecolor[named]{pgfstrokecolor}{rgb}{.75,0,.25}\tilde{\bm{D}}_{\tau
i}}{\color[rgb]{.75,0,.25}\definecolor[named]{pgfstrokecolor}{rgb}{.75,0,.25}\tilde{\bm{D}}_{(\tau-1)j}}{\color[rgb]{.75,0,.25}\definecolor[named]{pgfstrokecolor}{rgb}{.75,0,.25}\bar{\bm{B}}[U_{\tau-1}^{1}]_{ij}}\\\
...\\\
{\color[rgb]{1,.5,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,.5,0}\bar{\alpha}_{|\pi|}}+\sum_{\tau,i,j}{\color[rgb]{.75,0,.25}\definecolor[named]{pgfstrokecolor}{rgb}{.75,0,.25}\tilde{\bm{D}}_{\tau
i}}{\color[rgb]{.75,0,.25}\definecolor[named]{pgfstrokecolor}{rgb}{.75,0,.25}\tilde{\bm{D}}_{(\tau-1)j}}{\color[rgb]{.75,0,.25}\definecolor[named]{pgfstrokecolor}{rgb}{.75,0,.25}\bar{\bm{B}}[U_{\tau-1}^{|\pi|}]_{ij}}\end{bmatrix}\cdot
u_{\pi}(\pi)\Bigg{\\}}.$

Indeed, the above equation is a Categorical distribution in the exponential
family form, and can be re-written into its usual form as follows:

$\displaystyle Q^{*}(\pi)$ $\displaystyle=\text{Cat}(\pi;\alpha^{*})\,\,\text{
where
}\,\,\alpha^{*}=\sigma\Bigg{(}{\color[rgb]{1,.5,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,.5,0}\bar{\alpha}}+\sum_{\tau=1}^{T}{\color[rgb]{.75,0,.25}\definecolor[named]{pgfstrokecolor}{rgb}{.75,0,.25}\mathbb{F}_{\tau}}\Bigg{)}\,\,\text{
and
}\,\,\mathbb{F}_{\tau}=\begin{bmatrix}\langle\tilde{\bm{D}}_{\tau}\otimes\tilde{\bm{D}}_{\tau-1},\bar{\bm{B}}[U_{\tau-1}^{1}]\rangle_{F}\\\
...\\\
\langle\tilde{\bm{D}}_{\tau}\otimes\tilde{\bm{D}}_{\tau-1},\bar{\bm{B}}[U_{\tau-1}^{|\pi|}]\rangle_{F}\end{bmatrix},$

where it should be stressed that
$\langle\mathchoice{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\displaystyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\textstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptscriptstyle\bullet$}}}}},\mathchoice{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\displaystyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\textstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptscriptstyle\bullet$}}}}}\rangle_{F}$
is not an expectation but the Frobenius product, i.e. a generalisation of the
inner product to matrices.

###  7.6 Messages for $\alpha$

In this section, we focus on the messages for $\alpha$, whose derivation is
identical to the messages of $\bm{D}$. To see this, note that $P(\bm{D})$ was
a Dirichlet with parameters $d$. Furthermore, the only child of $\bm{D}$ was
$S_{0}$ whose prior and posterior were categorical distributions with
parameters $\bm{D}$ and $\tilde{\bm{D}}$. Similarly, note that $P(\alpha)$ is
a Dirichlet with parameters $\theta$. Furthermore, the only child of $\alpha$
is $\pi$ whose prior and posterior are categorical distributions with
parameters $\alpha$ and $\tilde{\alpha}$. From this observation, we directly
obtain the following result:

$\displaystyle Q^{*}(\alpha)$
$\displaystyle=\text{Dir}(\alpha;{\color[rgb]{1,.5,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,.5,0}\theta}+{\color[rgb]{.75,0,.25}\definecolor[named]{pgfstrokecolor}{rgb}{.75,0,.25}\tilde{\alpha}}).$

###  7.7 Summary of messages

Next, we focus on explaining the intuition behind the resulting equations. The
first point is the coloration of the equations in orange and purple. The
orange colour corresponds to messages from the parent factors, which
correspond to messages of type $\text{m}_{2}$ in Figure 13. This means that
each orange message is a function of the expectation of the sufficient
statistic of the parent variables, i.e. a function of messages of type
$\text{m}_{1}$. Similarly, the purple colour corresponds to messages from the
child factors, which correspond to messages of type $\text{m}_{3}$ in Figure
13. Once again, this means that each purple message is a function of the
sufficient statistics of the co-parent and child variables, i.e. a function of
messages of type $\text{m}_{4}$ and $\text{m}_{5}$, respectively. Let’s see
how these play out in our newly derived equations.

##### Messages for $\alpha$:

$\displaystyle Q^{*}(\alpha)$
$\displaystyle=\text{Dir}(\alpha;{\color[rgb]{1,.5,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,.5,0}\theta}+{\color[rgb]{.75,0,.25}\definecolor[named]{pgfstrokecolor}{rgb}{.75,0,.25}\tilde{\alpha}})$

Recall that $\mu_{\alpha}=\theta$ is an $\text{m}_{2}$ message (orange
colour). However, $\alpha$ does not have any parent variables thus
$\mu_{\alpha}$ is a constant, i.e. a function of zero $\text{m}_{1}$ messages.
Furthermore, we know that $\alpha$ has only one child variable ($\pi$) and no
co-parent variables. Therefore,
$\mu_{\pi\rightarrow\alpha}(\tilde{\alpha})=\tilde{\alpha}$ is the only
$\text{m}_{3}$ message (purple colour) for $\alpha$, where
$\tilde{\alpha}=\langle u_{\pi}(\pi)\rangle_{Q_{\pi}}$ is an $\text{m}_{5}$
message.

##### Messages for $\bm{D}$:

$\displaystyle Q^{*}(\bm{D})$
$\displaystyle=\text{Dir}(\bm{D};{\color[rgb]{1,.5,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,.5,0}d}+{\color[rgb]{.75,0,.25}\definecolor[named]{pgfstrokecolor}{rgb}{.75,0,.25}\tilde{\bm{D}}_{0}})$

Similarly for the messages of $\alpha$, $\mu_{\bm{D}}=d$ and
$\mu_{S_{0}\rightarrow\bm{D}}(\tilde{\bm{D}}_{0})=\tilde{\bm{D}}_{0}$, where
$\tilde{\bm{D}}_{0}$ should be thought of as a message from a child variable
($\text{m}_{5}$ message).

##### Messages for $\bm{A}$:

$\displaystyle Q^{*}(\bm{A})$
$\displaystyle=\prod_{i}\text{Dir}(\bm{A}_{\mathchoice{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\displaystyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\textstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptscriptstyle\bullet$}}}}}i},\bm{a}_{\mathchoice{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\displaystyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\textstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptscriptstyle\bullet$}}}}}i})\text{
where
}\bm{a}={\color[rgb]{1,.5,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,.5,0}a}+\sum_{\tau}{\color[rgb]{.75,0,.25}\definecolor[named]{pgfstrokecolor}{rgb}{.75,0,.25}\bm{o}_{\tau}}\otimes{\color[rgb]{.75,0,.25}\definecolor[named]{pgfstrokecolor}{rgb}{.75,0,.25}\tilde{\bm{D}}_{\tau}}$

Following the same reasoning, $\mu_{\bm{A}}=a$ is an $\text{m}_{2}$ message
and because $\bm{A}$ does not have any parent variables then $\mu_{\bm{A}}$ is
a constant. Also, $\bm{A}$ has one child variable ($O_{\tau}$) for each time
step $\tau\in\llbracket 0,t\rrbracket$ and one co-parent variable ($S_{\tau}$)
for each of them, which implies that there are $t+1\,\,\text{m}_{3}$ messages
for $\bm{A}$, i.e.
$\mu_{O_{\tau}\rightarrow\bm{A}}(\bm{o}_{\tau},\tilde{\bm{D}}_{\tau})=\bm{o}_{\tau}\otimes\tilde{\bm{D}}_{\tau}\,\,\forall\tau\in\llbracket
0,t\rrbracket$. Because the $O_{\tau}$ are observed, we know that the
$\text{m}_{5}$ messages transmitted by this node will be the observation made
at time $\tau$ ($\bm{o}_{\tau}$). Additionally, the $\text{m}_{4}$ message
from the hidden variables $S_{\tau}$ are the expectation of their sufficient
statistics, i.e. $\langle
u_{S_{\tau}}(S_{\tau})\rangle_{Q_{S_{\tau}}}=\tilde{\bm{D}}_{\tau}$. This
confirms the idea that $\mu_{O_{\tau}\rightarrow\bm{A}}$ is a function of the
sufficient statistics of the child and co-parent variables. Figure 17
concludes this paragraph with a visual representation of the messages for
$\bm{A}$.

Figure 17:  This figure illustrates the passing of messages required to update
the posterior over $\bm{A}$. The messages of type
${\color[rgb]{0.828125,0.69140625,0.05859375}\definecolor[named]{pgfstrokecolor}{rgb}{0.828125,0.69140625,0.05859375}\text{m}_{2}}$,
${\color[rgb]{0.01,0.75,0.24}\definecolor[named]{pgfstrokecolor}{rgb}{0.01,0.75,0.24}\text{m}_{3}}$,
${\color[rgb]{0.5,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.5,0,0}\text{m}_{4}}$
and
${\color[rgb]{0,0,0.5}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.5}\text{m}_{5}}$
come from the parent factors, child factors, co-parent variables and child
variables, respectively.

##### Messages for $\bm{B}$:

$\displaystyle Q^{*}(\bm{B})$
$\displaystyle=\prod_{u,i}\text{Dir}(\bm{B}[u]_{\mathchoice{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\displaystyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\textstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptscriptstyle\bullet$}}}}}i},\bm{b}[u]_{\mathchoice{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\displaystyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\textstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptstyle\bullet$}}}}}{\mathbin{\vbox{\hbox{\scalebox{0.5}{$\scriptscriptstyle\bullet$}}}}}i})\quad\text{
where
}\quad\bm{b}[u]={\color[rgb]{1,.5,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,.5,0}b[u]}+\sum_{(k,\tau)\in\Omega_{u}}{\color[rgb]{.75,0,.25}\definecolor[named]{pgfstrokecolor}{rgb}{.75,0,.25}\tilde{\alpha}_{k}}{\color[rgb]{.75,0,.25}\definecolor[named]{pgfstrokecolor}{rgb}{.75,0,.25}\tilde{\bm{D}}_{\tau}}\otimes{\color[rgb]{.75,0,.25}\definecolor[named]{pgfstrokecolor}{rgb}{.75,0,.25}\tilde{\bm{D}}_{\tau-1}}$

Sticking with this reasoning, $\mu_{\bm{B}}=b$ is an $\text{m}_{2}$ message
and because $\bm{B}$ does not have any parent variables then $\mu_{\bm{B}}$ is
a constant equal to $b$. Also, $\bm{B}$ has one child variable ($S_{\tau}$)
for each time step $\tau\in\llbracket 1,T\rrbracket$ and all policies
$\forall\pi\in\llbracket 1,|\pi|\rrbracket$, along with two co-parent
variables ($S_{\tau-1}$ and $\pi$) for each of those child variables. This
implies that there are $T\times|\pi|\,\,\text{m}_{3}$ messages for $\bm{B}$,
i.e. $\mu_{S_{\tau}\rightarrow
S_{\bm{B}}}(\tilde{\alpha}_{k},\tilde{\bm{D}}_{\tau},\tilde{\bm{D}}_{\tau-1})=\tilde{\alpha}_{k}\tilde{\bm{D}}_{\tau}\otimes\tilde{\bm{D}}_{\tau-1},\,\,\forall\tau\in\llbracket