Lifted Relational Kalman Filtering

1 Introduction

Many real-world systems can be modeled by continuous variables and relationships (or dependences) among them. The Kalman Filter (KF) [Kalman, 1960] accurately estimates the state of a dynamic system given a sequence of control-inputs and observations. It has been applied in a broad range of domains which include weather forecasting [Burgers et al., 1998], localization and tracking in robotics [Limketkai et al., 2005], economic forecasting in finance [Bahmani-Oskooee and Brown, 2004] and many others. Given a sequence of observations and Gaussian dependences between variables, the filtering problem is to calculate the conditional probability density of the state variables at each timestep. Unfortunately, the KF computations are cubic in the number of random variables which limits current exact methods to domains with limited number of random variables. This has led to the combination of approximation and sampling (e.g. the Ensemble Kalman Filter [Evensen, 1994]).

This paper leverages the ability of relational languages [Friedman et al., 1999; Poole, 2003; Richardson and Domingos, 2006] to specify models with size of representation independent of the size of populations involved. Various lifted inference algorithms for relational models have been proposed [Poole, 2003; de Salvo Braz et al., 2005; Milch and Russell, 2006; Richardson and Domingos, 2006; Wang and Domingos, 2008; Choi et al., 2010]. These seek to carry computations in time independent of the size of the populations involved. However, the key challenge in relational filtering (of dynamic systems) is ensuring that the representation does not degenerate to the ground case when multiple observation are made. As more observations are received, an increasing number of objects become distinguished. This precludes the application of previously known algorithms unless approximately equivalent objects are grouped with expensive clustering algorithms.

We propose Relational Gaussian Models (RGMs) to model dynamic systems of large number of variables in a relational fashion. RGMs have as their main building block the pairwise linear Gaussian potential as detailed in Section 2. Further, we propose a new lifted filtering algorithm that is able to marginalize out random variables of the previous timestep efficiently (in time linear in the number of random variables) while maintaining the relational (RGM) representation. This prevents the model from being increasingly grounded even when individual observations are made for all random variables. Moreover, updating the relational representation takes only quadratic time in the number of relational atoms (sets of random variables). One key insight is that, given identical observation models, even when the means of the random variables are dispersed their variances remain identical. This is sufficient to maintain a relational representation.

This paper is organized as follows. Section 2 introduces definitions and the relational filtering problem. Section 3 presents our main technical results, i.e., the recursive estimation of the states of random variables in a lifted fashion. Section 4 presents our algorithm in detail together with complexity results. Section 5 shows experimental results with a housing market model. Section 6 presents a real-world application to Social Networks. Section 7 discusses previous work. We conclude in Section 8.

2 Model and ProblemDefinitions

In this section, we define Relational Gaussian Models (RGMs) and introduce the filtering problem for dynamic relational models.

2.1 Relational Continuous Models

Dependencies between variables are represented using Parfactor models 1 , i.e. parameterized factor models. Each parfactor g = (L, C, X, φ) is composed of a set of logical variables (or objects) (L), constraints on L (C), a list of relational atoms (X), and a potential function on X (φ).

Relational atoms represent the set of random variables corresponding to all ground substitutions of its logical variables. Formally, applying a substitution θ to a parfactor g yields a new parfactor gθ = (L ′ , Cθ, Xθ, φ), where L ′ is obtained by renaming the variables in L according to θ. If θ is a ground substitution, gθ is a factor. A factor f = (x, φ) is a pair where x is a list of ground random variables (x1, . . . , x|x|) and φ is a potential on x, a function from range(x) = × |x| i =1 range(xi) to R + . A factor f defines a weighting function on a valuation v = (v1, . . . , v|X|): wf (v) = φ(v1, . . . , v|x|). The weighting function for a parfactor g is the product of the weighting functions of all of its ground substitutions (factors), wg(v) = ∏ f ∈g wf (v). Hence, a set of parfactors G defines 2 a probability density proportional to,

2.2 Relational GaussianModels (RGMs)

Relational Gaussian Models (RGMs) are a subset of Relational Continuous Models (RCMs) where potentials are restricted to be Gaussian distributions. RGMs are composed of three types of parfactor models: (1) Relational Transition Models (RTMs); (2) Relational Pairwise Models (RPMs); and (3) Relational Observation Models (ROMs). Suppose that we have n relational atoms: X 1 t (L), . . ., X n t (L) where L is a list of logical variables. In a relational linear dynamic model, relational atoms are linearly influenced by controlinputs U 1 t (L), . . ., U n t (L). Similarly, a linear observation model specifies the relationship between observation variables O 1 t (L), . . ., O n t (L) and other relational atoms. Control inputs and observations are associated with relational atoms in two ways: (1) direct association; and (2) indirect association. We provide further details in Section 2.4.

Relational Transition Models (RTMs) model the dependence of relational atoms at the next timestep, X j t +1 (a ′ ), on relational atoms at the current timestep, X i t (a), and (when available) control-input information. They take the following form,

where G i, j RTM ∼ N(0, σ i, j RTM ) and N(m, σ 2 ) is the normal distribution with mean m and variance σ 2 . B i, j X and B i, j U are the transition models, matrices or a constants, corresponding to two relational atoms.

1 Our representation is based on previous work [Poole, 2003; de Salvo Braz et al., 2005; Milch and Russell, 2006; Choi et al., 2010].

2 The condition is that at least a random variable has a prior distribution as outlined in [Choi et al., 2010].

For univariate state variables, we can represent the transition model with a linear Gaussian,

t

The most common transition is the transition from the current state X i t (a) to the next X i t +1 (a). It is represented as follows,

Relational ObservationModels (ROMs) represent the relationships between the hidden (state) variables, X i t (a), and the observations made at the corresponding timestep, O i (a),

t

ROM

where G i ROM ∼ N(0, σ i ROM ). H i t is the observation model, a matrix or a constant, between the hidden variables and the observations.

In the linear Gaussian representation, they take the following form,

Relational Pairwise Models (RPMs) represent Gaussian dependences between pairs of relational atoms within the same timestep as follows,

where G i, j RPM ∼ N(0, σ i, j RPM ). R i, j t is the pairwise coefficient, a matrix or a constant, between the two relational atoms.

Note that RTMs and ROMs are directed models while RPMs are undirected. The directed models represent the nature of dynamic systems (e.g. the state at the next timestep depends on the current timestep). The product of RPMs is an efficient way to represent a multivariate Gaussian density over all the state variables. 3

3 Note that a multivariate Gaussian density (of state variables) is a quadratic exponential form. The quadratic exponential form can always be decomposed into terms involving only single variables and pairs of variables. We provide additional details in Section 7.

2.3 ARelational Filtering Problem

Given a prior (or current belief) over the state variables, the filtering problem is to compute the posterior after a sequence of timesteps. The input to the problem is: (1) Relational Gaussian Model (RTMs, RPMs and ROMs); (2) current belief over the relational atoms (X i 0 ) represented by a product of relational Gaussian potentials; (3) sequence of control-inputs (U i 1 , . . . ,U i T ); and (4) sequence of observations (O i 1 , . . . ,O i T ). The output is the relational Gaussian posterior distribution over the relational atoms (X i ) at timestep T.

T

2.4 Input and Observation Association

At every timestep the control-inputs and observations must be associated with the random variables they affect. The ideas in this section apply to control-inputs and observations but we illustrate them for observations.

We distinguish two types of observations: direct and indirect. Direct observations are those made for a specific random variable. For instance, if we make an observation for each random variable in a subset A i t ⊆ X i t of the ground substitutions of relational atom X i t , we are looking at the following model,

t

In the example of Figure 1, observing the selling price of a house would dramatically reduce the variance of the hidden variable that represents the true value of that house.

Similarly, multiple direct observations, O i t = o i,1 t , o i,2 t , . . . , o i,|O i t | t , could be made for each variable in some set of random variables,

t

t

Given some notion of neighborhood (e.g. a residential neighborhood or a block of houses), indirect observation allows the possibility that observations made for a random variable, o i t (a ′ ), would influence nearby random variables, X i t (a j ), a ′ nequal aj,

t

For example, this allows the possibility that the observation of the selling price of a house would reduce the variance of the true values of neighboring houses.

Current (exact) lifted inference algorithms (e.g. [Kersting et al., 2006; Choi et al., 2010]) handle observations by partitioning the relational atoms into groupings of groundings for which identical observations and observation models apply. In contrast, our approach partitions a relational atom into sets according to the number of different types of observations associated with each random variable. For instance, if an individual observation of the same ROM type is made for each random variable then no partitioning at all is necessary. The intuition for this is that the filtering process will assign the same variance to any two hidden variables for which the same number of observations is made at the current timestep.

Here, the partition will determine new RPMs, the pairwise parfactors which maintain the variances and covariances. In particular, the number of new RPMs is quadratic in the size of the partition. Since individual observations cause the means of the random variables to differ we store the mean information in the prior and posterior (P and Pnew in Section 3). Hence, the number of priors and posteriors is linear in the number of random variables. However, this will not affect the computational complexity of inference as long as the RPMs do not degenerate. Further details are given in Sections 3.3 and 4.

Formally, given a partition Π i = (M i 1 , M i 2 , . . . ,M i |Π i | ) of a relational atom, X i , the observation model takes the form,

l

l

l

where we omit the time subscript and where O i l is the set of observations relevant to part l.

3 Lifted Relational Kalman Filter

The Lifted Relational Kalman Filter (LRKF), just like the conventional Kalman Filter, carries two recursive computations: prediction step and update/correction step.

3.1 Lifted Prediction

In the prediction step, our current belief over the states of the relational atoms together with the RTMs, RPMs and controlinputs are used to make a best estimate of state without observation information. First, the product of potentials in the RTMs and RPMs is built. Second, the variables from the previous timestep are marginalized resulting in new RPMs and estimates of the relational atoms in the current timestep. We call this estimates the intermediate posterior, the input to the update step.

Here, φ ′i, j RPM , P i and P ′i are respectively the updated RPMs, the priors and the intermediate posteriors. More details of the integration are given in Appendix A.

3.2 Lifted Update

In the update step, the intermediate posterior P ′ i and ROMs are used to correct our estimate of the relational atoms.

When a single observation, o i t +1 , is associated with all variables in a relational atom, we calculate the posterior for one random variable X i t +1 (a) and use the result for the rest of the groundings of the same relational atom,

In the case of multiple observations O i t +1 = o i,1 t +1 , o i,2 t +1 , . . . , o i,|O i t | t +1 we may also do the computation of the posterior for a single random variable X i t +1 (a) and use the resulting posterior for all other groundings of the relational atom (to which the same set of observations applies). The calculation is similar to the above, except that multiple observations need to be considered,

3.3 Lifted Inference with Individual Observations

One of the key challenges in lifted inference is handling individual observations. Current methods ground a relational atom when different observations are made for its random variables. It is usually the case that models shatter combinatorially fast and thus forfeit the benefits of a relational representation and the applicability of lifted inference.

We solve this problem in the LRKF by noting that the variances and covariances in the model are not affected by individual observations. We are thus able to represent the variances and covariances in a relational way while allowing variables to carry individual means. Further, the lifted prediction operation applies unmodified to this representation.

Lemma 1 The variances of two random variables X(a), X(b) in an RGM are equal after a filtering step (Lifted Prediction and Lifted Update) if the following conditions hold before the filtering step: (1) both random variables are in the same relational atom; (2) the variance of both variables is the same; (3) observations are made for both variables or none of them.

Proof Given conditions (1) and (2), we first prove that the variance of both random variables is the same after the Lifted Prediction step. Note that condition (3) is not relevant to this step.

WLOG we assume Xt(a) and Xt(b) have different means, μt(a) and μt(b). Moreover, it is easy to see that the variance of X i t +1 (a) and X i t +1 (b) is the same after marginalizing all random variables of timestep t due to the following two reasons: (i) X(a) and X(b) are in the same relational atom and thus share the same relationships with other random variables; (ii) the means are not involved in the marginalizations (see Section 3.1). It follows that we can represent the potentials relevant to the marginalization of Xt(a) and Xt(b) as follows:

where c X refers to the coefficient of the termX. 4

After Xt(a) and Xt(b) are marginalized we get a potential on Xt +1(a) and Xt +1(b). The variances of the random variables are the inverses of the coefficients of their squares in the resulting potential. Thus, all we need to show is that the coefficients of the square of the random variables, Xt +1(a) 2 and Xt +1(b) 2 , are the same after marginalization. The two coefficients can be represented as follows,

4 For the sake of exposition the RTMs here represent dependences from state variables at time t to the same state variable at time t + 1 (e.g. from Xt(a) to Xt +1(a)). However, the general RTMs (e.g dependences fromXt(a) to Xt +1(b)) produce similar forms.

Condition (2) (σ 2 Xt (a) =σ 2 Xt(b) ) implies c Xt(a) 2 = c Xt(b) 2 which in turn implies c Xt +1(a) 2 = c Xt +1(b) 2 . This is enough to prove that the variance of two random variables X(a) and X(b) with different means is the same after the Lifted Prediction step.

We now prove the result for the Lifted Update step. Regarding condition (3) there are two cases: (a) observations were made for both variables; or (b) no observations were made for either variable. In the case of (b) the proof is complete. In the case of (a), the update step for X(a) can be represented by,

where,

Likewise, after the update step the variance of X(b) is,

By condition (2) and the proof for the prediction step, σ Xt +1 (a) i = σ Xt +1(b) i . Thus, σ + Xt +1(a) = σ + Xt +1(b). ■

Lemma 2 The covariances of two pairs of variables (X(a), X(b)) and (X(a), X(c)) in an RGM are equal after a filtering step (Lifted Prediction and Lifted Update) if the following conditions hold before the filtering step: (1) the three random variables are in the same relational atom; (2) the covariance of both pairs of variables is the same; (3) observations are made for the three variables or none of them.

Proof The method used in the proof of Lemma 1 can be employed in this proof: The terms involving the individual observations do not affect terms which determine the covariance of two random variables. ■

4 Algorithms and Computational Complexity

Let X (|X|) be the set (number) of all random variables in the model and X = (X 1 , . . . ,X |X| ) be the set of relational atoms (also, a partition of X). In this section we speak of the relational atoms as sets of random variables.

Figure 3 presents our Lifted Kalman Filtering algorithm. The inputs to the algorithm are: relational atoms, X; the RGM, RTMs MX, RPMs MP and ROMs MO; the prior over the relational atoms, P0; and the control-inputs, U[1,...,T], and observations, O[1,...,T], for each timestep.

The algorithm computes the posterior recursively. Split partitions the domains of each relational atom X i as induced by the control-inputs Ut. Lifted Predict calculates new RPMs, MP 5 , and intermediate posterior, Pint, based on the transition models, MX, and the control-inputs, Ut. Then, Split Obs partitions the domains of each relational atom X i as induced by the observations, O i t . Lifted Update calculates the new posterior, Pcur, based on the intermediate posterior, Pint, the observation models, MO, and the observations, O i .

5 In our representation the number of relational atoms determines the number of RPMs which is equal to E(|X|, 2) (the number of 2combinations of |X| with repetition).

t Given the control-inputs, Split partitions relational atoms as done in previous work: e.g. Split [Poole, 2003] and SHATTER [de Salvo Braz et al., 2005]. If the control-inputs are allowed to differ for the variables in a relational atom, the model will be propositionalized. Hence, there is little advance in how we handle individual control-inputs with respect to previous algorithms [Choi et al., 2010]. 6

Algorithm Split Obs partitions a relational atom X i based on the observations. However, Split Obs will only partition a relational atom in case the conditions of Lemmas 1 and 2 do not hold, i.e., when different number of observations are made for the relational variables. If the conditions of Lemmas 1 and 2 hold, the efficiency of the relational representation will be preserved even if multiple observations are made for all variables in some or all of the relational atoms.

PROCEDURE LRKF(X,MX,MP,MO, P0, U[1,...,T], O[1,...,T]) Atoms, X = (X 1 , . . . ,X |X| ); RTM, MX, RPM, MP, and ROMMO; prior, P0; control-inputs, U[1,...,T]; observations, O[1,...,T].

1. Pcur

←

P0, Xcur

1. For t = 1 to T
2. (a) [Xcur,MX,MP,MO] ←Split(Xcur, Ut, MX, MP, MO)
3. (b) [Pint,Mp] ← Lifted Predict(Xcur, Pcur, MX, MP, Ut) (§3.1)
4. (c) [Xcur,MO] ←Split Obs(Xcur, Ot, MO) (§3.3)
5. (d) [Pcur] ←Lifted Update(Xcur, MO, Pint, Ot) (§3.2)
6. Return Xcur, Pcur

Figure 3: Algorithm Lifted Relational Kalman Filter for Relational Gaussian Models.

Lemma 3 The complexity of Lifted Predict is O(|X|·|Xt + | 2 ). Where Xt + is the set of relational atoms output by Split.

Proof This step corresponds to the marginalization (Equation (13) and Appendix A) of the variables in X. For every variable that is integrated the parameters of all, E(|Xt + |, 2), pairwise interactions between relational atoms must be updated. ■

Lemma 4 The complexity of Lifted Update is O(|Xt + o | · |Omax|). Where Xt + o is the set of relational atoms output by Split Obs and Omax is the largest set of observations associated with a relational atom.

Proof For each relational atom in Xt + o the computation in Equation (15) iterates over all relevant observations. ■

Our main result follows,

Theorem 5 The computational complexity of LRKF is O(T · (|X|·|X ∗ t + | 2 +|X ∗ t + o |·|O ∗ max |)) where T is the number of timesteps, X, X ∗ t +, X ∗ t + o and O ∗ max are as above with the ∗ indicating the largest set across all timesteps.

6 However, we conjecture that techniques similar to the ones we used for ROMs can be applied to RTMs. Any two random variables in the same atom will have the same variance after the Lifted Predict step if they receive the same types of control inputs. That is, RTMs of the same type will increase the variances of the random variables by the same amount.

←

X

5 Experimental Results

We compare the average filtering time of LRKF and a conventional Kalman Filter by varying the number of random variables. We implemented both the LRKF and the conventional KF (which handles random variables individually) in Perl. This makes the manipulation of the dynamically changing structure convenient.

For the housing market model in Figure 1, we randomly choose the parameters of the models (priors, RTMs, RPMs, and ROMs) and provide observations for HMOt and HPOt(·). To emphasize the difference in scalability, we assume that some set of houses has individual observations in each timestep, HPOt(·), while the rest of the houses do not. We ran the two filters over 50 timesteps. The results in graph 4 confirm our theoretical results contrasting the linear time complexity of LRKF with the cubic time complexity of the Kalman Filter.

6 Application to Online Social Networks

For decades social scientists have studied how different types of relationships impact individuals and organizations. More recently, research on analyzing online social networks (OSNs) has demonstrated that relational patterns can be exploited to improve predictive models of link structure and behavior. Further, the accurate estimation of relationship strengths has applications to understanding human behavior, predicting human behavior (e.g. fraud), privacy control, information prioritization, recommender systems, search and visualization (see e.g. [Gilbert and Karahalios, 2009], [Xian et al., 2010] and references therein).

Previous work on OSNs has been characterized by two major limitations: (1) Following social media it has focused on binary friendship relations, i.e., two people can be either friends or strangers. However, in reality relationships may fall anywhere along a continuous spectrum - an observation made in the social sciences since 1973 [Granovetter, 1973] with the introduction of the notion of tie strength. (2) Works on link prediction and relationship strength estimation have given little attention to the dynamic nature of social networks (SNs). However, it has been demonstrated that the level of interactions between individuals varies widely over time. For instance, experiments on the Facebook OSN showed that, on average, 55% of the links that are active during a given month are no longer active during the following month [Viswanath et al., 2009].

Given the relational nature of SNs and the fact that interaction data is notably noisy a probabilistic and relational approach to prediction is best. However, predicting relationship strengths on a single network-snapshot has remained too expensive for current exact inference algorithms [Sen et al., 2008]. To exacerbate the above limitations, current OSNs are potentially very large and rapidly growing.

Here we show that our LRKF is able to carry accurate relationship strength prediction on large dynamic networks while using state-of-the-art modeling features and techniques. Following the modeling decisions made by [Xian et al., 2010] we propose a probabilistic model where hidden variables represent relationship strength. The model is composed of two parts (Figure 5): (1) A generative component (top) models the conditional probability of relationship strength given profile similarities and; (2) a discriminative component (bottom) models the conditional probability of the interaction activity between users given the strength of their relationship.

In [Xian et al., 2010] the hidden variables are estimated iteratively given a snapshot of the OSN. In sharp contrast, we are able to filter the state of the network as observations about user interactions are made. We extend previous work by introducing a linear Gaussian model of relationship evolution (Equation (16)) that relates state variables across timesteps. For this purpose, the control-inputs are derived from a linearcombination of profile similarities. The model has the following components,

where (i, j) ranges over all pairs of individuals, X are the relationship strength variables, U are the profile similarity feature vectors and the o k are interaction observations.

One limitation of this model, which it inherits from its static predecessor, is that relationship strengths are considered independent of each other. A better approach is to consider the dependences between edges by introducing RPMs of the form,

We envision a multivariate Gaussian version of probabilistic transitivity being represented in this fashion.

7 RelatedWork

The KF [Kalman, 1960; Roweis and Ghahramani, 1999] is a method for estimating the state of a dynamic process given a sequence of noisy observations. It is restricted to linear dynamic and linear measurement models both with additive Gaussian noise. The Extended Kalman Filter (EKF) [Sorenson and Stubberud, 1968] extends the KF to non-linear systems. For high dimensional data, a sampling method has been devised, the Ensemble Kalman Filter [Evensen, 1994]. Exact Kalman Filtering for high dimensional data is not feasible because exact filtering requires matrix inversions which take time cubic in the number of random variables.

Our RGMs represent the probability density as a product of node and edge factors. Any multivariate Gaussian is a quadratic exponential and can thus be written in this form. This is related to the information form of the Gaussian density and is the basis of other models such as Directed Gaussian Models (DGMs) [Cowell, 1998] and Gaussian Markov Random Fields (GMRFs) [Rue and Held, 2005]. However, RGMs are relational while DGMs and GMRFs are not. Thus, the previous models do not have a compact (relational) representations and, more importantly, an efficient (lifted) exact inference algorithm.

Relational probabilistic models allow the specification of models with size independent of the sizes of the populations in the model [Friedman et al., 1999; Poole, 2003; Richardson and Domingos, 2006]. Lifted inference algorithms [de Salvo Braz et al., 2005; Milch and Russell, 2006] attempt to carry as much of the computations without propositionalizing the model. [Poole, 2003], solves inference problems by dynamically splitting and unifying sets of ground atoms. [de Salvo Braz et al., 2005] (FOVE) introduced counting elimination to efficiently eliminate atoms with different parameterizations. [Milch et al., 2008] (C-FOVE) take a slightly different approach with the introduction of counting formulas. However, all of the above lifted inference algorithms are not applicable to models with continuous variables.

[Kersting et al., 2006] introduced Logical HMMs that combine ideas from Statistical Relational Learning and dynamic models. Indeed their work, as ours, pursues the benefits that the relational approach brings to inference and learning. However, their work is inherently discrete and further, they assume specific transition and observation models.

For relational models with continuous variables, recent advances have made inference possible. [Wang and Domingos, 2008] is an approximate algorithm based on sampling, search and local optimization. [Choi et al., 2010] is an exact variable elimination algorithm for continuous domains. The latter algorithm is similar to the marginalization problem that is part of the prediction step in filtering. However, none of these algorithms have been devised with dynamic models in mind nor do they address the problem of individual observations.

8 Conclusion and FutureWork

We propose Relational Gaussian Models to represent and model dynamic systems in a relational (first-order) way. Further, we present the first algorithm for filtering or tracking at the first-order level. Our theoretical analysis and empirical tests show that our approach leads to significant gains in efficiency and enables filtering for systems with very large numbers of random variables. We also make the case for the applicability of lifted inference to address real-world problems by taking a recently proposed model of social relationship strength and extending it to large dynamic networks.

A limitation of our exact filtering is that we shatter the model when the random variables in a relational atom receive different numbers of observations because their variances and covariances become different. Our current understanding is that approximate re-grouping of random variables is the only general recourse in this case.

Acknowledgements

We wish to thank Jihye Seong, Jeongkeun Lee and the anonymous reviewers for their valuable comments. This work was supported in part by NSF award IIS-09-17123 - RI: Scaling Up Inference in Dynamic Systems with Logical Structure and NSF award ECS-09-43627 - Improving Prediction of Subsurface Flow and Transport through Exploratory Data Analysis and Complementary Modeling. Abner Guzman-Rivera was supported by the C2S2 Focus Center, one of six research centers funded under FCRP, a Semiconductor Research Corp. entity.

A Details of Lifted Prediction

The integration is done using the following rule,

t

where A is a constant, B a linear form of random variables except X i t (a ∗ ), and C is a quadratic form of random variables except X i (a ∗ ).

t The integration of one random variable in Equation (12) can be represented as follows,

when c, c j t and c j t +1 represent constants calculated from Equation (19), and X j represents ∑a ′ ∈A j X j (a ′ ).

t t Note the quadratic form in Equation (18) includes the following types of expression,

where [X 2 ] is ∑a∈A X(a) 2 , and [XX] is ∑a,a ′ ∈A,anequala ′ X(a)X(a ′ ). Now, Equation (20) is integrated as follows,

Here, R ′ t , R ′ t +1 , R ′ t,t +1 , μt, μt +1, σ ′ t RPM and σ ′ t +1 RPM are new constants derived from Equation (22).