COVID-19 Time-series Prediction by Joint Dictionary Learning and Online NMF

Hanbaek Lyu, Christopher Strohmeier, Georg Menz, Deanna NeedellarXiv 2020 · arXiv

In the early months of 2020, researchers faced a daunting task: predicting the spread of COVID-19 with very little historical data. While traditional epidemiological models and deep learning were the go-to tools, a team from UCLA proposed a radically different approach. By treating pandemic trends like snippets of text or patches of an image, they applied Dictionary Learning and Online Nonnegative Matrix Factorization (NMF) to forecast the future of the virus.

TL;DR

This paper introduces a model-free framework that learns "elemental" patterns of disease spread (dictionary atoms) from multiple countries simultaneously. By combining minibatch initialization with online adaptation, the method produces interpretable, short-term forecasts for COVID-19 cases, deaths, and recoveries without requiring the rigid assumptions of traditional compartmental models.

What Problem Does This Paper Address?

Predicting a pandemic in real-time is notoriously difficult. Researchers usually rely on two extremes:

  1. Compartmental Models (e.g., SIR): These use differential equations to simulate transitions between "Susceptible," "Infected," and "Recovered" populations. While theoretically sound, they require precise parameter tuning and can be too rigid for complex, real-world data.
  2. Deep Learning: While powerful, these models are "black boxes" and typically require massive datasets—something that wasn't available in the first few months of the COVID-19 outbreak.

The authors identify a "scarcity of information" problem. Most countries in early 2020 were in an exponential growth phase, providing very few examples of what "containment" or "peaking" actually looked like in the data.

Methods

The researchers treat time-series data as a collection of short "evolution instances." Their approach consists of four main pillars:

Dictionary Learning via NMF

Nonnegative Matrix Factorization (NMF) decomposes a complex dataset into two parts: a dictionary (the fundamental "building blocks" or "atoms" of the data) and a code (how to combine those blocks to recreate the original signal). Because the data is non-negative (you can't have negative cases), NMF ensures the results are physically meaningful.

Schematic of Nonnegative Matrix Factorization (NMF) decomposing data into a dictionary and code.

Hankel Matrices

To turn a 1D time-series into something NMF can process, they use a "Hankel matrix" structure. This essentially stacks overlapping windows of time-series data into a 2D matrix, allowing the algorithm to learn temporal shapes.

Minibatch to Online Transition

They first use "minibatch learning" to find a general dictionary from the entire available history. Then, they switch to "online learning," which allows the dictionary to adapt dynamically as new daily reports arrive. This hybrid approach balances historical context with current trends.

Recursive Extrapolation

To predict the future, the model performs a "partial fit." It takes the most recent data, finds the best combination of dictionary atoms to describe it, and uses the "tail" of those atoms to project the next day's value. This is repeated recursively to forecast up to 30 days out.

Datasets

The study utilized the JHU CSSE COVID-19 Data, specifically:

  • Metrics: Daily new confirmed cases, deaths, and recoveries.
  • Scope: Data from January 19, 2020, to April 12, 2020.
  • Geography: Six countries with distinct outbreak trajectories: South Korea, China, the US, Italy, Spain, and Germany.
  • Preprocessing: The authors applied a 5-day moving average to smooth noise and a log-transform ($x \mapsto \log(x+1)$) to stabilize high fluctuations.

Key Insights and Ideas

  • Latent Correlations: By learning a joint dictionary across six countries, the model captures hidden similarities. For example, the growth pattern in Italy might help the model predict a similar upcoming phase in the US.
  • Interpretability is Built-in: Unlike a neural network, you can actually see the dictionary atoms. An atom might represent a "steady plateau," a "sharp spike," or a "gradual decay." The final prediction is just a weighted sum of these visible shapes.
  • Model-Free Universality: Because the model doesn't assume any underlying biological mechanism (like infection rates or recovery periods), it is "universal." It learns the "model" directly from whatever data it is given.
  • Transfer Learning: The authors suggest that a dictionary learned from a country that has already peaked (like China) can be "transferred" to act as a starting point for a country just beginning its outbreak.

Key Results

The algorithm successfully identified 24 primary dictionary atoms that represent the "alphabet" of the pandemic's evolution. The "online" component proved crucial; as the dictionary traversed the time-series, it updated its atoms to reflect the changing reality of social distancing measures and healthcare responses.

30-day predictions for daily new confirmed cases across six countries alongside the joint dictionary of evolution patterns.

The recursive extrapolation provided reasonable 30-day projections for all three metrics across the six countries, as seen in the confirmed cases prediction above.

Limitations and Future Work

  • Hyperparameter Sensitivity: The model relies on several parameters (like $\lambda$ for sparsity) that require careful tuning. Choosing a $\lambda$ that is too high can cause predictions to drop to zero unrealistically fast.
  • Uncertainty Growth: As with all recursive models, the variance (uncertainty) of the prediction grows the further into the future you forecast.
  • Future Directions: The authors propose extending this to a tensor-based setting, where more variables (like mobility data or weather) could be encoded into a single multi-dimensional dictionary for even more accurate "joint" predictions.

Summary updated

Abstract

Predicting the spread and containment of COVID-19 is a challenge of utmost importance that the broader scientific community is currently facing. One of the main sources of difficulty is that a very limited amount of daily COVID-19 case data is available, and with few exceptions, the majority of countries are currently in the "exponential spread stage," and thus there is scarce information available which would enable one to predict the phase transition between spread and containment. In this paper, we propose a novel approach to predicting the spread of COVID-19 based on dictionary learning and online nonnegative matrix factorization (online NMF). The key idea is to learn dictionary patterns of short evolution instances of the new daily cases in multiple countries at the same time, so that their latent correlation structures are captured in the dictionary patterns. We first learn such patterns by minibatch learning from the entire time-series and then further adapt them to the time-series by online NMF. As we progressively adapt and improve the learned dictionary patterns to the more recent observations, we also use them to make one-step predictions by the partial fitting. Lastly, by recursively applying the one-step predictions, we can extrapolate our predictions into the near future. Our prediction results can be directly attributed to the learned dictionary patterns due to their interpretability.
BibTeX
@misc{lyu2020covid,
  author = {Hanbaek Lyu and Christopher Strohmeier and Georg Menz and Deanna Needell},
  title = {{COVID-19 Time-series Prediction by Joint Dictionary Learning and Online NMF}},
  year = {2020},
  eprint = {2004.09112},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2004.09112},
}
Figure