Learned Factor Graphs for Inference From Stationary Time Sequences

Nir Shlezinger, Nariman Farsad, Yonina C. Eldar, Andrea J. Goldsmith

TL;DR

This paper introduces a novel framework for time series inference by learning components of factor graphs using neural networks, rather than training end-to-end deep models. This hybrid approach leverages domain knowledge about the statistical structure of time series while using data to learn the specific functional relationships, leading to more compact models, reduced data requirements, and improved robustness.

What Problem Does This Paper Address?

Traditional methods for inferring hidden states from observed time sequences often rely on model-based algorithms that require complete knowledge of the underlying statistical model. While powerful, these methods struggle when the model is complex or unknown. On the other hand, purely data-driven deep learning approaches often require massive amounts of labeled data and can be computationally expensive. This paper addresses the challenge of performing accurate and robust inference on time sequences when the underlying statistical model is not fully known, aiming to bridge the gap between model-based and data-driven methods.

Methods

The core contribution is a framework that learns function nodes of a factor graph, rather than the entire inference process. This approach leverages the stationary and Markovian properties of time sequences, allowing a single neural network to represent a function node that can be reused across different sequence lengths. Specifically, the authors propose using neural networks (DNNs) to learn the conditional probability distributions that define the factor graph's function nodes. This learned factor graph is then used with conventional message-passing algorithms like the Sum-Product (SP) algorithm for inference. The paper also shows how this framework can be adapted to use the Viterbi algorithm for inference, leading to a data-driven ViterbiNet.

Key aspects of the method include:

  • Hybrid Model-Based/Data-Driven: Combines prior knowledge of the factor graph structure (Markovian, stationary) with data-driven learning of the function nodes.
  • Learned Function Nodes: Neural networks are trained to estimate the conditional probability densities (e.g., $P(Y_i|S_i, S_{i-1})$) that constitute the factor graph's function nodes.
  • Stationarity Exploitation: A single learned function node can be used for sequences of varying lengths, reducing the need for length-specific models.
  • Compact Models: By learning only function nodes, the neural networks are typically smaller and require less training data compared to end-to-end deep models.
  • Adaptability: The learned factor graph can be used with different inference algorithms (SP, Viterbi).

Datasets

  • Sleep-EDF Expanded database: Used for sleep stage detection. The authors specifically utilized the Sleep Cassette (SC) subset.
  • Simulated data: Used for symbol detection in digital communications, generated for Gaussian and Poisson channels with varying signal-to-noise ratios (SNRs) and channel conditions (perfect CSI, CSI uncertainty).

Key Insights and Ideas

  • Decomposition of Inference: Learning function nodes separately from the inference algorithm is more efficient and data-frugal than training an entire end-to-end deep model for inference.
  • Leveraging Domain Knowledge: Explicitly incorporating structural domain knowledge (stationarity, Markovian property) into the factor graph structure significantly simplifies the learning task.
  • Compactness and Efficiency: The learned function node approach leads to significantly smaller neural networks that can be trained with much less data, making inference feasible on resource-constrained devices.
  • Robustness to Model Uncertainty: The learned factor graph approach demonstrates improved robustness to imperfect knowledge of the underlying statistical model compared to traditional model-based methods.
  • Unified Framework: The learned factor graph can serve as a common representation for different inference algorithms (SP, Viterbi), offering flexibility.

Key Results

  • Sleep Stage Detection: Using a 5-layer fully-connected network as a learned function node for SP inference improved accuracy by 3.6% (to 82.8%) compared to using the network directly as a classifier (79.2%). A 34-layer ResNet also showed improvement (84.2% vs. 82.3%). Training on a single patient's data achieved accurate inference on their remaining data.
  • Symbol Detection (Gaussian Channel): Learned factor graphs achieved symbol error rates (SERs) close to the model-based SP algorithm with perfect CSI, significantly outperforming it under CSI uncertainty. They also outperformed data-driven methods like SBRNN and FGNN when trained with limited data.
  • Symbol Detection (Poisson Channel): Similar improvements were observed, with learned factor graphs approaching model-based SP performance under CSI uncertainty.
  • Blockwise Stationary Channels: An online training mechanism allowed learned factor graphs to track changing channel conditions, approaching the performance of model-based SP with instantaneous CSI, especially at higher SNRs. Joint training also showed benefits over initial training.
  • Computational Complexity: The learned factor graph approach offers reduced computational complexity compared to end-to-end deep learning models like SBRNN for symbol detection.

Limitations and Future Work

  • Computational Feasibility for Large State Spaces: For very large state cardinalities $|S|^{l+1}$, SP inference (and thus learned factor graphs using SP) can become computationally prohibitive. The authors suggest exploring state reduction techniques for such scenarios.
  • Unsupervised Training: While the framework can be adapted for unsupervised training, this was left for future investigation.
  • Blockwise Stationary Tracking: While online training shows promise for tracking blockwise stationary variations, further improvements could be explored using syndrome decoders.
  • Extension to Loopy Factor Graphs: The current framework primarily focuses on cycle-free factor graphs. Factor graph neural networks might be more advantageous for loopy graphs where SP inference deviates from the MAP rule.
  • Learning Different Function Nodes for Different Time Instances: For highly non-stationary scenarios, learning separate function nodes for different time instances could be explored, though this would increase data requirements.

Summary updated

BibTeX
@article{shlezinger2022learned,
  author = {Nir Shlezinger and Nariman Farsad and Yonina C. Eldar and Andrea J. Goldsmith},
  title = {{Learned Factor Graphs for Inference From Stationary Time Sequences}},
  journal = {IEEE TSP},
  year = {2022},
  doi = {10.1109/tsp.2021.3139506},
}
Figure