A Neural Probabilistic Graphical Model for Learning and Decision Making in Evolving Structured Environments

Abstract

A difficult and open problem in artificial intelligence is the development of agents that can operate in complex environments which change over time. The present communication introduces the formal notions, the architecture, and the training algorithm of a machine capable of learning and decision-making in evolving structured environments. These environments are defined as sets of evolving relations among evolving entities. The proposed machine relies on a probabilistic graphical model whose time-dependent latent variables undergo a Markov assumption. The likelihood of such variables given the structured environment is estimated via a probabilistic variant of the recursive neural network.

1. Introduction

The development of artificial intelligence (AI) systems capable of keeping up with evolving environments, just like “biological systems can adapt to new environments”, was posed as Challenge One for AI by Rodney Brooks [1]. To date, the challenge is still open. The relevance of machines capable of coping with evolving environments was further pointed out in the modern framework of evolving computation [2,3]. Evolving environments are met in most machine learning applications under real-world circumstances. This is the consequence of two main factors:

• the world is not stationary, but it changes over time;
• a learning machine may be applied under different conditions [4].

Examples are found in fault diagnosis for complex dynamical systems [5], modeling of climate and financial data [6,7], detection of fraud [8] or spam [9]. As pointed out by [10], coping with these evolving environments requires approaches that overcome a fundamental assumption that holds in traditional machine learning, namely that data are drawn from a fixed distribution [10]. In this respect, the headmost contribution of this communication is to cope for the first time in a formal manner with environments that change over time according to time-dependent, unknown probabilistic laws. To this aim, the machine sought is expected to realize a statistical model of the environment that probabilistically accounts for the environmental changes.

To this end, several learning machines suitable for sequential data processing may appear to be promising, e.g., hidden Markov models (HMM) [11] or recurrent neural networks [12]. Nonetheless, in our view, the general notion of a structured environment is better expressed in terms of a relation, or set of relations, over individual entities. Each entity may be represented as a variable-size, entity-specific set of attributes that capture certain characteristics, or perspectives, of the world. Attributes may be either discrete or real-valued. Given these premises, traditional learning machines are unfeasible. The second contribution of the present communication is to present a new machine that is suitable for the aforementioned relational scenario. To the best of our knowledge, this is the first approach to modeling and learning structured environments that evolve over time.

An evolving structured environment is then expressed by means of a time-dependent graph process defined over the entities. The entities existing in the environment at time t are represented by the vertices of the graph at t. The edges of the graph encapsulate the binary relation(s) over the entities at time t. Labels in the form of real-valued attributes may, in turn, be attached to the edges. These labels account for the evolving type and characteristics of the relation(s) that hold within the environment. We assume that any decision made by the machine at time t does not depend only on the environment at time t, but also, the evolution of the environment that had occurred so far. To fix ideas, a toy example is given by an autonomous robotic platform that is required to move and assist human workers in setting up the booths and furniture within the exhibition spaces of a large trade fair pavilion. The partitioning of the building into booths, conference rooms, etc. changes from time to time, as do the amount, positioning, and type of furniture. The different rooms and pieces of furniture are the entities to be modeled in the present framework, and their mutual positioning is the relation among the entities. The features, or labels, to be associated with such entities may represent the geometry, size, weight, and specific function of the corresponding items or rooms. In order to be capable of navigating autonomously within such an evolving environment, the moving platform must be capable of keeping track of the changes, progressively adapting to the changeable spaces, and making suitable decisions accordingly.

We use a probabilistic framework, such that the environment can be described in terms of probabilistic laws over time-varying random quantities, e.g., the likelihood of the entities being related to each other at time t. Intrinsically, the machine we are introducing is a novel ‘probabilistic graphical model [13] that represents a particular joint probability density, including a set of latent variables undergoing a first-order Markov assumption, and a set of observable, time-varying random graphs drawn from properly-defined probability density functions (pdf). In the light of our previous experience with neural networks for density estimation [14,15,16], the short-term modeling of these pdfs is realized via a probabilistic radial basis functions (RBF) [17] variant of recursive neural networks (RNN) [18,19], hereby denoted by RBF-RNN. Conversely, the latent variables and their conditional probabilistic dependencies are modeled via a long-term hidden Markov chain, as in HMMs. The potentialities of combinations of short-term predictors and long-term models of evolving environments were shown empirically by [20]. Moreover, suitable change detection tests based on the HMM likelihood were proven to be successful in detecting drifts in evolving environments [21]. The present approach can be seen as an instance of the online Bayesian learning setup for evolving environments [22] extended to graphical or relational data, where the time-dependent RBF-RNNs play the role of the parameterized probabilistic observation model, and the Markov chain encapsulates implicitly the probabilistic transition model.

The underlying assumption is that by observing the evolution of an environment for a long enough period of time, it is possible to learn the fundamental probabilistic laws that rule its behavior, as well as its evolution, such that suitable models of such laws may be later used to make statistically sound predictions, e.g., making educated decisions. As in Just-in-time classifiers for recurrent concepts drift in evolving environments [23], the present approach exploits the notion of recurrent, underlying concepts that re-present after an unpredictable amount of time, and that the machine shall be able to detect in order to react with the adequate probabilistic response. In the present framework, these concepts are the latent states of nature ruling the pdf of the observations.

Before introducing the machine formally, we need to extend the definitions of random variables and pdf to the present, structured setup. Eventually, learning (in terms of estimating proper statistical parametric models) will rely on a training sample of streams of environmental observations over time. Decision making among the actions ${\mathcal{A}}_1,\dots ,{\mathcal{A}}_k$ in the environment $\mathit{\epsilon }$ at any future time t will take place within the Bayesian framework, relying on the action-conditional joint pdfs estimated at t via action-specific machines which observe the evolution of $\mathit{\epsilon }$.

2. Materials and Methods

The present formalization requires assumptions on the type of evolving environments we can cope with. Still, it forms a well-defined ground on which to develop proper algorithms. First, the novel notion of the random environment is introduced, broadening the definition of random graph [24] to a large extent. Let $\mathrm{\Omega }$ be a sample space, and let $\mathcal{V}$ denote any discrete or continuous-valued universe. The latter is the set of entities. A random environment (RE) on $\mathcal{V}$ and $\mathrm{\Omega }$ is a function $\mathit{\epsilon }:\mathrm{\Omega }\to \left\{\right(V,R\left)\right|V\subseteq \mathcal{V},R\subseteq V\times V\}$. Labels (namely, real-valued vectors associated with the entities or with the elements of R) can be accommodated in the definition in a straightforward manner. Let $\mathbb{E}=\left\{\right(V,R)\mid V\subseteq \mathcal{V},R\subseteq V\times V\}$ be the space of RE outcomes. A pdf for REs over $\mathcal{V}$ is defined as any function $p:\mathbb{E}\to \mathbb{R}$ such that (1) $p\left(\epsilon \right)\ge 0,\forall \epsilon \in \mathbb{E}$, and (2) ${\int }_{\mathbb{E}}p\left(\epsilon \right)d\epsilon =1$. The Lebesgue-measurability of the space of labeled graphs defined on measurable domains is shown in [25], which makes the writing ${\int }_{\mathbb{E}}p\left(\epsilon \right)d\epsilon$ meaningful. It is seen that traditional notions of probability theory, such as conditional pdf, joint pdf, statistical independence, etc., are readily extended to REs. An environment is any outcome $\epsilon$ of a RE, i.e., drawn from the corresponding pdf $p\left(\epsilon \right)$. This definition covers all cases of labeled/unlabeled entities, as well as environments having variable sizes (e.g., the number of entities making up the environment is not necessarily pre-defined, and it may change over time) and/or variable topology (e.g., two-by-two relations between pairs of entities may evolve, too).

Loosely speaking, a stochastic environment process $X\left(t\right)$ is any function that maps discrete or continuous time $t\in \mathcal{T}$ onto a corresponding RE. Since by definition REs are random variables, and since we can bijectively represent $X\left(t\right)$ as an indexed family $\left\{X\right(t\left)\right|t\in \mathcal{T}\}$, it is seen that a stochastic environment process is a special case of random process according to the classic definition of the latter (see, for instance, [26], Section 1.9, page 41). Consequently, an extension of the traditional hidden Markov model (HMM) to REs is given by proposing the novel definition of HMM over environments ($ϵ$-HMM) as a pair of stochastic processes: a hidden Markov chain, that is a traditional discrete-time random process, and an observable stochastic environment process which is a probabilistic function of the states of the former.

Let us assume that the evolution of an environment over time $t=1,\dots ,T$ has been observed, and represented as a sequence $Y={\epsilon }_1,\dots ,{\epsilon }_T$ generated by a hidden stochastic environment process. Also, let Y be the outcome of a sequence $\mathcal{W}={\omega }_1,\cdots ,{\omega }_L$ of latent states of nature, e.g., drifting concepts. No prior segmentation of Y into subsequences $Y_1,\cdots ,Y_L$ corresponding to the individual states of nature are known in advance. We propose a hybrid neural/Markovian realization [27] of $ϵ$-HMMs for the probabilistic graphical modelling of $p(Y\mid \mathcal{W})$. Using a standard HMM notation [28], an $ϵ$-HMM $\mathcal{H}$ is formally defined as $\mathcal{H}=(S,\pi ,\mathbf{A},B_{\mathit{\epsilon }})$ where: $S=\{S_1,\cdots ,S_Q\}$ is a set of states (namely, the Q different values that the hidden Markov chain can assume); $\pi =\{P(S_i\mid t=0),S_i\in S\}$ is the probability distribution of the initial states (t being a discrete time index); $\mathbf{A}$ is the $Q\times Q$ matrix of the transition probabilities, whose $ij$-th entry is $a_{ij}=P(S_j$ at time $t+1\mid S_i$ at time t); finally, $B_{\mathit{\epsilon }}$ is a set of pdfs over REs, called emission probabilities, describing the state-specific statistical distributions of the REs: $B_{\mathit{\epsilon }}=\{b_i(.)\mid b_i\left(\epsilon \right)=p(\epsilon \mid S_i),S_i\in S,\epsilon \in \mathbb{E}\}$.

The observable component of the $ϵ$-HMM is realized via neural models of the emission probabilities [29]. For each state of the $ϵ$-HMM, a neural network is introduced that estimates the corresponding emission probability given the current status of the environment being observed. Relying on the formalism we introduced in [30], for each $\iota =1,\cdots ,Q$ we assume the existence of $d\in \mathbb{N}$ and of the functions ${\varphi }_{\iota }:\mathbb{E}\to {\mathbb{R}}^d$ and $p_{\iota }:{\mathbb{R}}^d\to \mathbb{R}$ such that $b_{\iota }\left({\epsilon }_t\right)=p_{\iota }\left({\varphi }_{\iota }\left({\epsilon }_t\right)\right)$. It is seen that there are countless pairs of such functions $\varphi (.)$ and $\widehat{p}(.)$, the simplest choice being $\varphi \left(\epsilon \right)=p\left(\epsilon \right),\widehat{p}\left(x\right)=x$. The function ${\varphi }_{\iota }(.)$ is hereafter referred to as the encoding for $\iota$-th state of the $ϵ$-HMM, whereas the function $p_{\iota }(.)$ is called the emission associated with the corresponding state. We assume parametric forms ${\varphi }_{\iota }\left(\epsilon \right|{\mathbf{\theta }}_{{\varphi }_{\iota }})$ and $p_{\iota }\left(\mathbf{x}\right|{\mathbf{\theta }}_{p_{\iota }})$ for the encoding and for the emission, respectively, and we let ${\mathbf{\theta }}_{\iota }=({\mathbf{\theta }}_{{\varphi }_{\iota }},{\mathbf{\theta }}_{p_{\iota }})$. The function ${\varphi }_{\iota }\left(\epsilon \right|{\mathbf{\theta }}_{{\varphi }_{\iota }})$ is realized via an encoding network, suitable to mapping structured environments $\epsilon$ into real vectors $\mathbf{x}$, as it is found in supervised training of traditional RNNs over graphs [18,19]. Consequently, we identify the parameters ${\mathbf{\theta }}_{{\varphi }_{\iota }}$ with the weights of the encoding network. An RBF network is then used to model the emission $p_{\iota }\left({\mathbf{x}}_t\right|{\mathbf{\theta }}_{p_{\iota }})$, where the parameters of the RBF play the role of ${\mathbf{\theta }}_{p_{\iota }}$. All the parameters in the $ϵ$-HMM can be estimated from examples by means of a global optimization algorithm, presented in the next Section, aimed at the maximization of the likelihood of the very $ϵ$-HMM given time-varying sequences of empirical observations of the evolving environment.

3. Results

The main result of the present communication is the following gradient-ascent global training technique. The proposed technique is based on the maximum likelihood (ML) criterion. Using standard notation [28], the likelihood $\mathcal{L}$ of the $ϵ$-HMM given the sequence Y is given by $\mathcal{L}={\sum }_{\iota \in \mathcal{F}}{\alpha }_{\iota ,T}$, where ${\alpha }_{\iota ,T}$ is the forward term for state $\iota$ at time T. The sum is extended to the set $\mathcal{F}$ of all final states [31] of the $ϵ$-HMM. Let us write $q_{\iota ,t}$ in order to represent the fact that the Markov chain is in state $S_{\iota }$ at time t. Then, the forward terms ${\alpha }_{\iota ,t}=P(q_{\iota ,t},{\epsilon }_1,\cdots ,{\epsilon }_t)$ and the backward terms ${\beta }_{\iota ,t}=P({\epsilon }_{t+1},\dots ,{\epsilon }_T|q_{\iota ,t})$ can be computed recursively as usual [28]. In turn, the forward-backward algorithm [28] can be used for ML estimation of the parameters of the underlying Markov chain, i.e., initial and transition probabilities. For a generic RBF-RNN parameter $\theta \in {\mathbf{\theta }}_{\iota }$, instead, gradient-ascent over $\mathcal{L}$ entails a learning rule in the form $\Delta \theta =\eta \frac{\partial \mathcal{L}}{\partial \theta }$, where $\eta \in {\mathbb{R}}^{+}$ is the learning rate. We can rewrite $\frac{\partial \mathcal{L}}{\partial \theta }$ as:

$$\frac{\partial \mathcal{L}}{\partial \theta }=\sum _{q=1}^Q\sum _{t=1}^T{\beta }_{q,t}\frac{{\alpha }_{q,t}}{b_q\left({\epsilon }_t\right)}\frac{\partial b_q\left({\epsilon }_t\right)}{\partial \theta }$$

(1)

The usual computations over the trellis of a standard HMM [28] can be used to obtain the quantities in the right-hand side of Equation (1), except for $\frac{\partial b_q\left({\epsilon }_t\right)}{\partial \theta }$ (where $b_q\left({\epsilon }_t\right)$ is the output from the corresponding RBF-RNN at time t). Hereafter, we focus on the computation of this partial derivative. Since (i) each state of the $ϵ$-HMM has its own RBF-RNN, (ii) in HMMs the emission probabilities for different states are mutually independent [28], and (iii) in HMMs the individual observations (i.e., environments) in the input sequence are assumed to be mutually independent given the state [28], we can simplify the notation by dropping the indexes $\iota$ and t, and we resort to the calculation of the derivatives of the generic emission $p\left(\varphi \left(\epsilon \right|{\mathbf{\theta }}_{\varphi })\right|{\mathbf{\theta }}_p)$. For any free parameter in the RBF-RNNs, say $\theta$, an explicit formulation for $\frac{\partial p\left(\varphi \left(\epsilon \right|{\mathbf{\theta }}_{\varphi })\right|{\mathbf{\theta }}_p)}{\partial \theta }$ can be obtained as follows. Eventually, the resulting formulation shall be put in place of $\frac{\partial b_q\left({\epsilon }_t\right)}{\partial \theta }$ into Equation (1) and the latter, in turn, into the overall learning rule $\Delta \theta =\eta \frac{\partial \mathcal{L}}{\partial \theta }$. There are three categories of parameters of the RBF-RNN that the algorithm shall estimate:

• the hidden-to-output connection weights $c_1,\cdots ,c_n$ of the RBF. In order to ensure the satisfaction of the axioms of probability, these weights must range over $(0,1)$ and sum to one. This is guaranteed by introducing n unconstrained variables ${\gamma }_1,\cdots ,{\gamma }_n$ such that

  $$c_i=\frac{\varsigma \left({\gamma }_i\right)}{{\sum }_{j=1}^n\varsigma \left({\gamma }_j\right)}$$

  (2)

  where $\varsigma \left(x\right)=1/(1+e^{-x})$. The generic variable ${\gamma }_i$ is estimated via ML. This guarantees the satisfaction of the axioms. The quantity $\frac{\partial p\left(\varphi \left(\epsilon \right|{\mathbf{\theta }}_{\varphi })\right|{\mathbf{\theta }}_p)}{\partial c_i}$ is computed by applying the chain rule to $\frac{\partial p\left(\varphi \left(\epsilon \right|{\mathbf{\theta }}_{\varphi })\right|{\mathbf{\theta }}_p)}{\partial {\gamma }_i}$ for $i=1,\dots ,n$.
• The mean vector ${\mathbf{\mu }}_i$ and covariance matrix ${\mathrm{\Sigma }}_i$ of the generic i-th Gaussian kernel $K_i\left(\mathbf{x}\right)=G(\mathbf{x};{\mu }_i,{\mathrm{\Sigma }}_i)$ in the RBF. For each component $j=1,\cdots ,d$ of the encoding space, ML parametric estimation of Gaussian mixture models [11] is applied in order to compute the quantities $\frac{\partial p\left(\varphi \left(\epsilon \right|{\mathbf{\theta }}_{\varphi })\right|{\mathbf{\theta }}_p)}{\partial {\mu }_{ij}}$ and $\frac{\partial p\left(\varphi \left(\epsilon \right|{\mathbf{\theta }}_{\varphi })\right|{\mathbf{\theta }}_p)}{\partial {\sigma }_{ij}}$.
• The parameters $\mathcal{U}=\{v_1,\cdots ,v_u\}$ of the encoding network. For each $v\in \mathcal{U}$, the quantity $\frac{\partial p\left(\varphi \left(\epsilon \right|{\mathbf{\theta }}_{\varphi })\right|{\mathbf{\theta }}_p)}{\partial v}$ is obtained as follows: $\frac{\partial p\left(\varphi \left(\epsilon \right|{\mathbf{\theta }}_{\varphi })\right|{\mathbf{\theta }}_p)}{\partial v}=\frac{\partial p\left(\varphi \left(\epsilon \right|{\mathbf{\theta }}_{\varphi })\right|{\mathbf{\theta }}_p)}{\partial y}\frac{\partial y}{\partial v}$, where y represents the output from the neuron that is fed from v. The partial derivative $\frac{\partial y}{\partial v}$ is computed as usual. As for $\frac{\partial p\left(\varphi \left(\epsilon \right|{\mathbf{\theta }}_{\varphi })\right|{\mathbf{\theta }}_p)}{\partial y}$, the backpropagation through structures (BPTS) algorithm can be applied [18,19]. First, computation of the derivative $\frac{\partial p\left(\varphi \left(\epsilon \right|{\mathbf{\theta }}_{\varphi })\right|{\mathbf{\theta }}_p)}{\partial y}$ is straightforward for the connection weights v between hidden and output neurons. This yields the initialization of the $\delta$’s to be backpropagated via BPTS. Then, let us turn our attention to the hidden weights $v=v_{m\ell }$, where ℓ and m are the hidden neurons connected by v. Relying on the aforementioned initialization of the $\delta$’s, the derivative $\frac{\partial p\left(\varphi \left(\epsilon \right|{\mathbf{\theta }}_{\varphi })\right|{\mathbf{\theta }}_p)}{\partial v_{m\ell }}$ is finally obtained via standard BPTS.

After the training process has been completed, an estimation of the likelihood at time t of an $ϵ$-HMM given an evolving random environment $\mathit{\epsilon }$ can be obtained from the forward terms on the t-th column of the trellis, as in plain HMMs [28]. In turn, action-specific $ϵ$-HMMs shall be trained and applied for each possible action, say ${\mathcal{A}}_1,\dots ,{\mathcal{A}}_k$, in those tasks that require to decide which action to undertake at any time t in the environment $\mathit{\epsilon }$. In this setup, the i-th $ϵ$-HMM models the corresponding action-conditional pdf, namely $p({\epsilon }_1,\dots ,{\epsilon }_t\mid {\mathcal{A}}_i)$. Provided that the prior probability of any individual action is known, be estimated via the usual frequentist approach of Bayesian decision theory [32], the action is chosen to rely on Bayes’ decision rule, as usual, as the action ${\mathcal{A}}_{max}$ that maximizes $p({\epsilon }_1,\dots ,{\epsilon }_t\mid {\mathcal{A}}_i)P\left({\mathcal{A}}_i\right),i=1,\dots ,k$.

4. Summary and Conclusions

Most environments may be described as relations over entities whose attributes are random variables. In turn, evolving environments do implicitly entail time sequences of varying relations. The goal of this communication was the foundation of an ad-hoc paradigm for learning and modeling the statistical properties of such sequences. The goal was pursued by combining probabilistic graphical models, encoding neural networks, and constrained RBFs within a unifying framework. A ML adaptation algorithm for the parameters of the overall model was devised under an implicit assumption of recurrent concepts drift, where the concepts are represented by the latent variables. We expect applications in real-world scenarios, as well as extensions of the technique to the incremental real-time adaptation of the parameters.