We develop methodology that combines statistical learning methods with generalized Markov models, thereby enhancing the former to
account for time series dependence. Our methodology can accommodate very general and very long-term time dependence structures in an easily estimable and computationally tractable fashion. We apply our methodology to the scoring of sleep behavior in mice. As methods currently used to score sleep in mice are expensive, invasive, and labor intensive, there is considerable interest in developing high-throughput automated systems which would allow many mice to be scored cheaply and quickly. Previous efforts at automation have been able to differentiate sleep from wakefulness, but they are unable to differentiate the rare and important state of rapid eye movement (REM) sleep from non-REM sleep. Key difficulties in detecting REM are that (i) REM is much rarer than non-REM and wakefulness, (ii) REM looks similar to non-REM in terms of the observed covariates, (iii) the data are noisy, and (iv) the data contain strong time dependence structures crucial for differentiating REM from non-REM. Our new approach (i) shows improved differentiation of REM from non-REM sleep and (ii) accurately estimates aggregate quantities of sleep in our application to video-based sleep scoring of mice. Supplementary materials for this article are available online.