# Outlier Detection for Multivariate Time Series Using Dynamic Bayesian Networks
## 2 Theoretical Background
### Dynamic Bayesian Networks  
The proposed method is designed to handle discrete multivariate temporal data. In this case, consider the discretization of time in time slices \(\mathcal{T}=\{0,\ldots,T\}\). Moreover, as for the BN case, variables are always discrete-valued. A discrete _multivariate time series_ (MTS) is a set of observations from \(n\) time-dependent variables. Consider a set of subjects \(\mathcal{H}\) of size \(N\). Observations for each variable are measured over \(T\) time instants, gathered in a MTS dataset \(D=\{\mathbf{x}^{h}[t]\}_{h\in\mathcal{H},t\in\mathcal{T}}\) where \(\mathbf{x}^{h}[t]=(x_{1}^{h}[t],\ldots,x_{n}^{h}[t])\). Hence, the overall size of \(D\) is given by \((n\times T)\times N\) single-valued observations. **Definition 1** (Subject observations). : _Given a dataset \(D\), the observations of a subject \(h\) constitute the set \(D^{h}=\{\mathbf{x}^{h}[t]\}_{t\in\mathcal{T}}\) of \(n\) variables measured throughout time \(\mathcal{T}\)._  
To model MTS we considered inter-variable as well as temporal dependencies. DBNs [26] are BNs which relate variables over adjacent time slices, modeling probability distributions over time, and therefore can be used to model MTS. A time-dependent discrete random vector, \(\mathbf{X}[t]=(X_{1}[t],\ldots,X_{n}[t])\), expresses the value of the set of variables at time \(t\). From a graphical perspective, nodes represent the variables \(X_{i}\) at specific time slices \(t\), \(X_{i}[t]\), and possess time-dependent parameters. Unlike standard BNs, DBNs are composed by a _prior network_\(B^{0}\), denoting the distribution of initial states, and multiple _transition networks_. A transition network has two types of connectivity among variables noted as _inter-slice_ and _intra-slice_ connectivities. The latter refers to variable dependencies at the same time frame. Inter-slice connectivity is responsible for the temporal aspect relating variables of different time slices, allowing only dependencies that follow forward in time. Let \(\mathbf{X}[t_{1}:t_{2}]\) denote the set of random vectors \(\mathbf{X}\) for the time interval \(t_{1}\leq t\leq t_{2}\). In addition, let \(P(\mathbf{X}[t_{1}:t_{2}])\) denote the joint probability distribution over the trajectory of the process from \(\mathbf{X}[t_{1}]\) to \(\mathbf{X}[t_{2}]\). Using the chain rule, the joint probability over \(\mathbf{X}\) is given by:  
\[P(\mathbf{X}[0:t])=P(\mathbf{X}[0])\prod_{i=1}^{T}P(\mathbf{X}[t]|\mathbf{X}[0:t-1]).\]  
Common simplifying assumptions consider \(m\)-\(th\) order Markov and stationary processes, which we describe next. **Definition 2** (\(m\)-\(th\) order Markov DBN). : _A DBN is said to be a \(m\)-th order Markov DBN if, for all \(t\geq 0\),_  
\[P(\mathbf{X}[t]|\mathbf{X}[0:t-1])=P(\mathbf{X}[t]|\mathbf{X}[t-m:t-1]). \tag{3}\]  
In a \(m\)-\(th\) order Markov DBN, \(m\) is called the _Markov lag_. Considering both inter and intra-slices connectivity, attributes \(\mathbf{X}[t]\) can admit parent nodes from \(t-m\) to \(t\), being transition networks expressed by \(B^{t}_{t-m}\). **Definition 3** (Stationarity DBN). : _A \(m\)-\(th\) order Markov DBN is said to be stationary if, for all \(t\geq 0\), the structure and parameters of each \(B^{t}_{t-m}\) are the same._  
For the stationary case, the only transition network \(B^{t}_{t-m}\) is thus invariant over time, being unrolled through time. To address the non-stationary case, a different network \(B^{t}_{t-m}\) for each transition \(t\to t-m\) is required. In Figure 1, a stationary first-order Markov DBN is depicted, composed by a prior network \(B^{0}\), over \(t=0\), and a transition network \(B^{t}_{t-1}\), for all \(1\leq t\leq T\). The connections \(X_{1}[t]\to X_{2}[t]\) and \(X_{2}[t]\to X_{3}[t]\) represent the intra-slice connectivity of the transition network \(B^{t}_{t-1}\) which correlates the attributes in the same time frame. Temporal relations are present in the inter-connectivity, being connections \(X_{1}[t-1]\to X_{1}[t]\) and \(X_{2}[t-1]\to X_{2}[t]\).