First Model Temporal Bayesian Network (FMTBN)

We now present a more restricted TBN formulation:

1.  

2. All relations between RVs are , No relations between TRVs, and relations from TRVs to RVs are .

This model can represent anything that can be modeled with a Bayesian network as it provides a superset of the Bayesian network syntax. Also, we can explicitly model an event that occurs during an interval with the limitation that after the event has occurred, there is persistence. For example if a support technician arrived at work between 07:00am and 07:30am the technician will still be at work at 09:00am and if the tech leaves work between 4:30pm and 5:00pm, she will still be gone from work at 10:00pm. We model a tech-support situation (see below) with a three node TBN (Figure 2).

Tech support is only available if the phones are working and the support technician has arrived at work. The probability that the phones are working is 0.95. The support tech has a fifty percent chance of starting work between 7:15am and 7:45am, 25 percent chance between 7:46am and 8:15am, and a 12.5 percent chance between 8:16am and 8:45am. If the tech is not in by 8:45am, she is not coming in at all.

 

 

Figure 2: Poor Support Inc. Tech-support TBN with two RVs and one TRV. The probabilities used in the figure are the dependent probabilities rather then the break-out used in the text description, e.g. (0.5,0.25,0.125) becomes (0.5,0.5,0.5).

As all probabilities for the RVs in the TRV are dependent on all previous RVs not happening, the notation is used as shorthand for

For reasoning over the model, we focus on belief revision (i.e. finding the most probable explanation). For our example model, there are two normal RVs and one TRV. The two RVs each have two states, and , and the TRV also has two states however the TRV is only for some interval, a, b, or c. This gives a total of possible complete assignments to our TBN. The cases where the TRV is for more than one interval do not need to be considered as they have zero probability.

Now we need to choose which of these sixteen complete assignments is the most probable explanation given some evidence. A set of evidence is presented in the form of a partial assignment. For our example, is the PA for ``Phones working and technician did not arrive between 07:46 and 08:15.''

A complete assignment, M, is said to be compatible with E iff . If then M is incompatible with E. A complete assignment in our sample model compatible with E is , , , .

In a Bayesian network, the joint conditional probability of a complete assignment is found using the chain rule [2, pg. 227,]. In the FMTBN, the chain rule is also used. We perform a topological ordering on the nodes of the TBN to find the order of computation. As the TRVs are not dependent on anything, they are placed at the end of the order. The remainder of the network is a Bayesian network and the ordering is constructed accordingly.

For our example network, the set of TRVs is and the RVs are and our ordering is (SA, PH, TA) We then write the chain rule for some complete assignment Z:

 

where T is a XOR RV which has when only one of A, B, or C is , zero on all other cases. Applying this to the complete assignment above, we compute

Since and an incompatible complete assignment can not be a MPE, we only need to consider those complete assignments for which as candidates. Thus since , we derive

Following the above method, the FMTBN can be transformed into an equivalent Bayesian network that can than be used for belief revision and updating [2]. Details of the transform are available in [5]. The transform generates many conditional probabilities, requiring conditional probabilities for the ith interval. As the TRV requires only one conditional probability per interval, the large number of probabilities introduced by the transform are wasteful.

The conciseness, in terms of probabilities needed, of the TRV notation, suggests that using Bayesian networks for computation may not be the best approach. An alternate approach, using a linear constraint system, was developed. This extends an approach developed in  [3] for coding Bayesian Networks as a system of linear constraints.

The following steps produce the constraints, variables, and costs.

1. For each TRV A
   1. Introduce variables and with cost functions

      

       

   2. and the constraint

      (3) 

   3. Now let such that where and .
   4. For each RV
      1. Introduce variables and with cost functions

         

          

      2. and the constraints and .  
   5. And finally to tie A to its component RVs, we add the constraint

      

      .  

Constraint 3 ensures that, to the rest of the TBN, TRV A can only take on one value. Constraint 1e forces A to be iff one of the RVs for its intervals is . Constraint set 1(d)ii combined with the cost functions 1(d)i ensure that the cost of an instantiation set is consistent with the conditional probabilities in the TRV.

Note that the construction of the linear constraint system can be done linear to the size of . Contrast this with the conversion to Bayesian network which was exponential to the size of .

After the linear constraint system has been fleshed out for the TRVs, the method from [3] is used to provide the rules for the rest of the random variables. An algorithm from same, using mixed Boolean linear programming, allows determination of the most probable explanation.