Constructing the Markov Chain

We explored several approaches to design a language for CTMCs in Chapter 3. In this chapter, we will use the variation that uses the pipe operator, %>%, together with an add_edge function. We will collect edges in three lists: one list for the “from” states, one for the “to” states, and one for the rates associated with the transitions. Also, we will collect the unbound variables in the rate expressions when we create new edges, so later changes to scopes will not affect the parameters of the CTMC model. To represent a CTMC, we create a class and a list that holds the “from” state, “to” state, rates, and parameters lists.

ctmc <- function()
  structure(list(from = NULL,
                 rate = NULL,
                 to = NULL,
                 params = NULL),
            class = "ctmc")

We want the syntax for constructing a CTMC to look like this:

m <- ctmc() %>%
  add_edge(foo, a, bar) %>%
  add_edge(foo, 2*a, baz) %>%
  add_edge(foo, 4, qux) %>%
  add_edge(bar, b, baz) %>%
  add_edge(baz, a + x*b, qux) %>%
  add_edge(qux, a + UQ(x)*b, foo)

Therefore, we need to implement the add_edge such that it takes four arguments: the CTMC, the “from” state, the rate of the transition, and the “to” state. The CTMC is implicitly provided to the function calls when we are using the pipe operator. The other three arguments should be provided as expressions, and the add_edge function will implement a non-standard evaluation to handle them.

We want the “from” and “to” states to be single symbols, but we will translate these into strings that we can use as row and column names in the rate matrix for the CTMC. The rate associated with a transition should be an expression, and to get the scope of the expression right, we will translate it into a quosure. We will then extract the unbound variables in this expression—unbound in the environment in which the quosure is defined—and add them to the parameters of the model. The implementation looks like this:

add_edge <- function(ctmc, from, rate, to) {
  from <- enexpr(from); stopifnot(is_symbol(from))
  to <- enexpr(to); stopifnot(is_symbol(to))

  from <- as_string(from)
  to <- as_string(to)

  ctmc$from <- cons(from, ctmc$from)
  ctmc$to <- cons(to, ctmc$to)

  r <- enquo(rate)
  ctmc$rate <- cons(r, ctmc$rate)
  ctmc$params <- cons(collect_symbols_q(get_expr(r), get_env(r)),
                       ctmc$params)

  ctmc
}

We use enexpr for from and to since we want these symbols to be just that, symbols, and not something we will want to evaluate in any context. We use enquo for the rate parameter, on the other hand, because we do want to have its environment available when we evaluate the expression. We do not evaluate it yet, though. We cannot evaluate it until we know the parameters for the model, and we do not want those to be fixed inside the CTMC object. We use the rate environment, however, when extracting the unbound variables in the rate expression.

Generally, it is a good idea to be able to get some information about an object we construct by printing it, but the default print function for a ctmc object will show the list of lists. This representation, especially for the linked lists, can be hard to decipher. Instead, we can implement a print function for this class by defining a function with the name print.ctmc. The information we want to display is the parameters of the model and the edge structure, and we can implement this function like this:

print.ctmc <- function(x, ...) {
  from <- lst_to_list(x$from) %>% rev()
  to <- lst_to_list(x$to) %>% rev()
  rate <- lst_to_list(x$rate) %>% rev()
  parameters <- lst_to_list(x$params) %>%
    unlist() %>% unique() %>% rev()

  cat("CTMC:
")
  cat("parameters:", paste(parameters), "
")
  cat("transitions:
")
  for (i in seq_along(from)) {
    cat(from[[i]], "->", to[[i]],
        "	[", deparse(get_expr(rate[[i]])), "]
")
  }
  cat("
")
}

The implementation is straightforward. We translate the linked lists into lists to make them easier to work with when we loop over the edges, and we reverse them so we will display them in the order in which they were added to the model. With the linked lists, we prepend new edges, so they are represented in the opposite order than the one in which they were added. For the parameters, we remove duplications using unique as well. After that, we simply print the parameters as a list and print a line for each edge, showing the “from” and “to” states together with the rate expression on the edge. For the latter, we use get_expr to get the bare expression, rather than the quosure, and we use the function deparse to translate the expression into a string that we can print.

With the three functions we have defined so far, we can now create and print a continuous time Markov chain.

x <- 2
m <- ctmc() %>%
  add_edge(foo, a, bar) %>%
  add_edge(foo, 2*a, baz) %>%
  add_edge(foo, 4, qux) %>%
  add_edge(bar, b, baz) %>%
  add_edge(baz, a + x*b, qux) %>%
  add_edge(qux, a + UQ(x)*b, foo)
m
## CTMC:
## parameters: a b
## transitions:
## foo -> bar   [ a ]
## foo -> baz   [ 2 * a ]
## foo -> qux   [ 4 ]
## bar -> baz   [ b ]
## baz -> qux   [ a + x * b ]
## qux -> foo   [ a + 2 * b ]

This example shows that we can have expressions on the edges that are constants, such as the edge from foo to qux that has the rate four. We can have expressions with unbound variables, a, b, and 2*a. And we can have expressions that involve a bound variable, the last two edges. Notice here that the second-to-last edge, from baz to qux, has a rate expression that includes the (unevaluated) variable x, while the last edge, from qux to foo, contains the expression a + 2*b, where the value of x has been inserted. This is the difference between including a bound variable and unquoting it in the expression. Since x is a bound variable, it is not considered a parameter of the model, but in the second-to-last expression, it will be used when we evaluate the rate. If we change its value, we also change the value of the rate expression. For the last rate expression, we have already inserted the value of x, so here we will not change the expression by changing the value of x.

Constructing a Rate Matrix

We saw how we could translate a list of edges into a rate matrix in Chapter 3, but in this chapter, we want to do a little more. In Chapter 3, we had numeric rates on the edges; we now have expressions. Instead of translating the CTMC into a rate matrix, we will create a function for generating rate matrices—a function that, given values for the parameters of the Markov model, will provide us with the corresponding rate matrix.

We implement this functionality via a closure. We write a function that extracts the information we need to build the rate matrix from the ctmc object and then define a function for computing the rate matrix given the model’s parameters. It then returns this closure function. The implementation can look like this:

get_rate_matrix_function <- function(ctmc) {
  from <- lst_to_list(ctmc$from) %>% rev()
  to <- lst_to_list(ctmc$to) %>% rev()
  rate <- lst_to_list(ctmc$rate) %>% rev()

  nodes <- c(from, to) %>% unique() %>% unlist()
  parameters <- lst_to_list(ctmc$params) %>%
    unlist() %>% unique() %>% rev()

  n <- length(nodes)

  f <- function() {
    args <- as_list(environment())
    Q <- matrix(0, nrow = n, ncol = n)
    rownames(Q) <- colnames(Q) <- nodes
    for (i in seq_along(from)) {
      Q[from[[i]], to[[i]]] <- eval_tidy(rate[[i]], args)
    }
    diag(Q) <- -rowSums(Q)
    Q
  }
  formals(f) <- make_args_list(parameters)

  f
}

Once again, we translate the linked lists into list objects and reverse them. We then get a list of unique nodes in the model by combining the from and to lists, removing duplicates, and we translate the resulting list into a vector that we will later use to set row and column names of the rate matrix. We extract the parameters for the model by translating the linked list into a list, and we then translate that into a vector, remove duplicates, and reverse the result to get the parameters in the order in which they were added to the edges.

The closure we define initially takes no formal arguments. We set those from the CTMC arguments after we have defined the function. We do it this way only because it is an easier way to define the function compared to constructing expressions and using something like the new_function construction we used earlier. Before we return the closure, it will have a list of formal arguments. Since we don’t know what these will be, we use a trick to get hold of them inside the closure: we get the local environment before we define any local variables—so at this point it will contain only the parameters passed to the function call—and make a list out of them. That list, we can use later to over-scope the evaluation of the rate expressions inside the closure.

For the actual construction of the rate matrix, there is little to surprise. We get the size of the matrix from the number of states in the CTMC. We then create the matrix and name rows and columns according to the nodes they represent. Then we (tidy) evaluate all the rate expressions to fill in the cells of the matrix, and finally, we adjust the diagonal so all rows sum to zero.

We now have a command in our language for getting a rate matrix function.

Qf <- m %>% get_rate_matrix_function()
Qf

## function (a, b)
## {
##     args <- as_list(environment())
##     Q <- matrix(0, nrow = n, ncol = n)
##     rownames(Q) <- colnames(Q) <- nodes
##     for (i in seq_along(from)) {
##         Q[from[[i]], to[[i]]] <- eval_tidy(rate[[i]], args)
##     }
##     diag(Q) <- -rowSums(Q)
##     Q
## }
## <environment: 0x7fdf6e76fed8>

When we provide the model parameters to this function, we get the rate matrix.

Qf(a = 2, b = 4)

##     foo bar baz qux
## foo -10   2   4   4
## bar   0  -4   4   0
## baz   0   0 -10  10
## qux  10   0   0 -10

Remember that the edge from baz to qux holds an expression that refers to the global variable x. If we change the value of this variable, we also change the result of evaluating the Qf function.

x <- 1
Qf(a = 2, b = 4)

##     foo bar baz qux
## foo -10   2   4   4
## bar   0  -4   4   0
## baz   0   0  -6   6
## qux  10   0   0 -10

The edge from qux to foo, where we substitute the value for x at the time we created the edge, using UQ, does not change.

Traces

An observation for a continuous-time Markov chain is a trace—a sequence of states and at which time points we observe the states. In any real data analysis, we would probably write functions to obtain data from files, but since we are exploring domain-specific languages, let’s write one for specifying traces. We will make traces depend on the CTMC that we want to use them with so we can test that the states in a trace are also states in the CTMC. If you want to use several CTMCs to analyze the same trace, you could remove these tests, or you could make the trace object depend on a list of legal states instead of a ctmc object.

We take the same approach as for the ctmc class: we write a function for creating an object to represent traces, and we then have functions for adding information to a trace. The information we want to store in a trace is a list of states and a list of time points in which we observe the states. For the consistency checks between CTMC and trace, we will also store the nodes in the CTMC. The constructor for the trace class looks like this:

ctmc_trace <- function(ctmc) {
  nodes <- c(lst_to_list(ctmc$from), lst_to_list(ctmc$to)) %>%
    unique %>% unlist
  structure(list(nodes = nodes, states = NULL, at = NULL),
            class = "ctmc_trace")
}

We add a verb to the language, a function adding observations of states at specific time points. This function mainly checks the consistency between states and the ctmc object and then adds states and time points to the ctmc_trace object’s lists.

add_observation <- function(trace, state, at) {
  state <- enexpr(state)
  stopifnot(is_symbol(state))
  state <- as_string(state)
  stopifnot(state %in% trace$nodes)
  stopifnot(is.numeric(at))
  stopifnot(is.null(trace$at) || at > trace$at$car)

  trace$states <- cons(state, trace$states)
  trace$at <- cons(at, trace$at)

  trace
}

As for CTMC objects, we want a printing function for traces. Here, I will take a different approach than what we did for the ctmc print function. I will translate traces into data frames—tibble objects to be precise—and print the result. If I was writing a package for CTMCs, I might take a different approach, but I will use the transformation into data frames later to compute likelihoods, so I exploit the transformation in the print function as well. To translate a ctmc_trace object into a tibble object, we specialize the as_tibble function. After that, we specialize the print function.

as_tibble.ctmc_trace <- function(x, ...) {
  states <- x$states %>% lst_to_list() %>% unlist() %>% rev()
  at <- x$at %>% lst_to_list() %>% unlist() %>% rev()
  tibble(state = states, at = at)
}
print.ctmc_trace <- function(x, ...) {
  df <- as_tibble(x)
  cat("CTMC trace:
")
  print(df)
}

We now have the functionality to create and print traces.

tr <- ctmc_trace(m) %>%
  add_observation(foo, at = 0.0) %>%
  add_observation(bar, at = 0.1) %>%
  add_observation(baz, at = 0.3) %>%
  add_observation(qux, at = 0.5) %>%
  add_observation(foo, at = 0.7) %>%
  add_observation(baz, at = 1.1)
tr

## CTMC trace:
## # A tibble: 6 x 2
##   state    at
##   <chr> <dbl>
## 1 foo   0.
## 2 bar   0.100
## 3 baz   0.300
## 4 qux   0.500
## 5 foo   0.700
## 6 baz   1.10

Computing Likelihoods

The final functionality we will implement for this example is for computing the likelihood of parameters given a CTMC and a trace. In Chapter 3, we saw how to translate a rate matrix into a transition-probability matrix by first multiplying the rate matrix by a scalar—the time period that has passed between two observations—and then (matrix-)exponentiating the result. We will reuse the function we implemented there.

transition_probabilities <- function(Q, t) expm(Q * t)

For computing the likelihood, we will create a verb in our domain-specific language that translates a CTMC and a trace into a function. This function will take the parameters of the CTMC as arguments—as the function for creating rate matrices we wrote earlier—and then return the likelihood for those parameters. This is a function we could then use for maximum-likelihood estimation by combining it with an optimization algorithm, of which there are several available in various R packages.

The implementation is straightforward. We get the rate matrix function from the ctmc object and translate the trace into a data frame and store the results in the closure of the function. Then we use the same trick as we used earlier to get the arguments inside the closure, evaluate the rate-matrix function to get the rate-matrix, and put the data from the data frame into a format we need for the computation. That computation is just running through the trace and computing the transition probabilities from two consecutive observations. Since it is a Markov model, the joint probability is the product of them. After we have created the closure, we set its formal arguments, similar to what we did with the rate-matrix function.

get_likelihood_function <- function(ctmc, trace) {
  rate_func <- ctmc %>% get_rate_matrix_function()
  trace_df <- as_tibble(trace)

  lhd_function <- function() {
    args <- as_list(environment())
    Q <- do.call(rate_func, args)

    n <- length(trace_df$state)
    from <- trace_df$state[-n]
    to <- trace_df$state[-1]
    delta_t <- trace_df$at[-1] - trace_df$at[-n]

    lhd <- 1
    for (i in seq_along(from)) {
      P <- transition_probabilities(Q, delta_t[i])
      lhd <- lhd * P[from[i],to[i]]
    }
    lhd
  }
  formals(lhd_function) <- formals(rate_func)

  lhd_function
}

That is it; we can now compute likelihoods for a CTMC.

lhd <- m %>% get_likelihood_function(tr)
lhd(a = 2, b = 4)

## [1] 0.00120108

In an actual data analysis context, we probably would want to compute the log likelihood instead. For traces of any useful length, the actual likelihood will lead to underflow since we are dealing with finite-bit floating-point numbers. Modifying the likelihood function to a log-likelihood function is a simple matter of changing the product to a sum and taking the log of P[from[i],to[i]].

There might be more functionality you would like to add to a language like this, but even with the few functions we have implemented so far, we have a useful domain-specific language. We have not used any operator overloading to implement it; we didn’t have to do that. We have used tidy evaluation extensively, though, to implement the non-standard evaluation we use for rate expressions.