  Modeling the time evolution of discrete sets of items (e.g., genetic
mutations) is a fundamental problem in many biomedical applications. We
approach this problem through the lens of continuous-time Markov chains, and
show that the resulting learning task is generally underspecified in the usual
setting of cross-sectional data. We explore a perhaps surprising remedy:
including a number of additional independent items can help determine time
order, and hence resolve underspecification. This is in sharp contrast to the
common practice of limiting the analysis to a small subset of relevant items,
which is followed largely due to poor scaling of existing methods. To put our
theoretical insight into practice, we develop an approximate likelihood
maximization method for learning continuous-time Markov chains, which can scale
to hundreds of items and is orders of magnitude faster than previous methods.
We demonstrate the effectiveness of our approach on synthetic and real cancer
data.
