Abstract
This paper addresses statistical methods for the segmental classification of linear sequence data, a task common in genomics, finance, and speech processing. The authors explore how to best report a predicted state sequence $\hat{x}$ given a posterior distribution $\pi(x|y)$. Traditional methods like the Viterbi algorithm (MAP) or marginal MAP often produce undesirable artifacts or lack control over prediction properties. We propose a decision-theoretic approach using a novel class of Markov loss functions, allowing for exact enumeration of the minimum expected loss sequence via dynamic programming. This generic method offers significant flexibility and performance improvements over existing techniques.
Introduction: Beyond the Viterbi Algorithm
In fields ranging from genomics to finance, researchers frequently use models to segment sequence data into discrete states—for example, identifying regions of DNA that have been deleted or duplicated. Once a statistical model is established, the standard practice is to report the "most probable" sequence of states, typically calculated using the Viterbi algorithm (Maximum A Posteriori, or MAP).
However, the Viterbi algorithm is an "all-or-nothing" approach. It employs a global loss function where the entire sequence is considered incorrect if even a single point is mislabeled. Conversely, "Marginal MAP"—picking the most likely label for each point independently—ignores the relationships between neighboring points, often leading to jagged, unrealistic results. In critical applications like cancer research, scientists need a "smooth" result that filters noise while preserving tiny, biologically vital segments. Standard smoothing techniques often inadvertently "erase" these small features because they do not contribute enough to the overall global probability.
The Markov Loss Function: A Flexible Framework
To address these limitations, the authors propose a Bayesian decision-theoretic framework. Instead of simply finding the most likely sequence, the goal is to identify the sequence that minimizes Expected Loss.
The core innovation is the Markov loss function, which decomposes error into three tunable parameters:
- False Call (FC): The cost of misclassifying the state at a specific location.
- False Transition (FT): The cost of reporting a state change when none exists (over-segmentation).
- False Hold (FH): The cost of failing to report a state change that actually occurred (under-segmentation).
By adjusting these costs, researchers can prioritize specific types of accuracy. For instance, one might care more about not missing a transition than about getting every single point exactly right. Crucially, the sequence minimizing this loss can be found exactly using dynamic programming, with a computational complexity of $O(S^4N)$—comparable to the standard Viterbi algorithm.
Genomic Applications and Results
The authors evaluated their method using simulated data and real-world copy number profiles from 630 colorectal tumors. These profiles served as "scaffolds" to which synthetic noise was added, creating a "ground truth" dataset that mimics the complexity of actual cancer genomics.
A key finding was the method's superior ability to retain fine details. In tests on simulated cancer data, the Markov loss approach successfully identified a tiny, critical deletion (the RBFOX1 gene) even under high "smoothness" settings. In contrast, standard methods like the Fused Lasso completely erased this deletion to achieve the same level of smoothness. The Markov loss function is adaptive; because it operates on the posterior probability, it can smooth out low-confidence noise while preserving small segments if the data for that segment is statistically significant.
Conclusion
This research demonstrates that you don't need to change your underlying statistical model (such as an HMM) to achieve better results. By simply changing the "loss function" used to interpret the model's output, researchers gain a powerful tool for adaptive smoothing and feature preservation. While the $O(S^4N)$ complexity may pose challenges for models with hundreds of states, the Markov loss approach offers a flexible, robust, and often superior alternative to traditional sequence reporting methods.
Summary updated