Abstract
In a world with data that change rapidly and abruptly, it is important to detect those changes accurately. In this paper we describe an R package implementing a generalized version of an algorithm recently proposed by Hocking et al. [2020] for penalized maximum likelihood inference of constrained multiple change-point models. This algorithm can be used to pinpoint the precise locations of abrupt changes in large data sequences. There are many application domains for such models, such as medicine, neuroscience or genomics. Often, practitioners have prior knowledge about the changes they are looking for. For example in genomic data, biologists sometimes expect peaks: up changes followed by down changes. Taking advantage of such prior information can substantially improve the accuracy with which we can detect and estimate changes. Hocking et al. [2020] described a graph framework to encode many examples of such prior information and a generic algorithm to infer the optimal model parameters, but implemented the algorithm for just a single scenario. We present the gfpop package that implements the algorithm in a generic manner in R/C++. gfpop works for a user-defined graph that can encode prior assumptions about the types of change that are possible and implements several loss functions (Gauss, Poisson, binomial, biweight and Huber). We then illustrate the use of gfpop on isotonic simulations and several applications in biology. For a number of graphs the algorithm runs in a matter of seconds or minutes for 10^5 data points.
Introduction: The Challenge of Structured Change-Point Detection
In many fields, from genomics to finance, data arrives as a sequence where the underlying "truth" changes abruptly at specific points. Standard change-point detection algorithms often struggle because they treat every change as equally likely. However, practitioners often have prior knowledge about the structure of these changes. For example, a biologist looking for a "peak" in genomic data expects an upward change followed by a downward one.
Existing tools were often either too specialized (handling only one type of constraint) or computationally prohibitive for large datasets. The gfpop R package addresses this gap by providing a generalized, efficient framework for detecting abrupt changes in univariate data while enforcing user-defined constraints via a graph.
The gfpop Framework
The core of the package is the Generalized Functional Pruning Optimal Partitioning (gfpop) algorithm. The "aha" moment of the framework is that complex domain knowledge can be translated into a simple directed graph. This turns a difficult statistical problem into a path-finding problem on a graph.
Key Technical Highlights
- Graph-Based Constraints: Users define a directed graph where nodes represent states and edges represent possible transitions. Each edge can carry a constraint (e.g., $\mu_t \le \mu_{t+1}$), a penalty for the change ($\beta$), and a specific loss function.
- Functional Pruning: Unlike standard dynamic programming which can be slow ($O(n^2)$),
gfpopuses functional pruning to reduce the search space. This allows the algorithm to run in near-linear time for many common scenarios. - Diverse Loss Functions: The package supports several analytical decompositions (L2, Lin-log, and Log-log), enabling the use of Gaussian, Poisson, Binomial, and robust losses like Huber and biweight. Robust losses are particularly critical for handling outliers in "dirty" real-world data.
Applications and Results
The authors evaluate gfpop using both simulations and high-impact real-world applications, including DNA Copy Number data for cancer research, neuroscience calcium imaging for neuron spikes, and ECG data for heartbeat analysis.
- Superior Accuracy in Genomics: On DNA copy number data, the constrained
gfpopmodel achieved zero label errors, whereas unconstrained models consistently produced false positives or missed relevant changes. - Robustness to Outliers: In simulations with 30% outliers,
gfpopusing a biweight loss was the only method capable of accurately recovering the true underlying signal. Standard "least-squares" approaches failed catastrophically in these scenarios. - Computational Speed: For a dataset of $10^5$ points,
gfpopcan find optimal change-points in roughly 0.35 seconds, making it practical for modern high-throughput data.
Conclusion and Future Work
While gfpop is slightly slower than hyper-specialized tools, its generality makes it a powerful asset for researchers. Currently, the package supports "collapsed" graphs where state transition rules are time-independent. Future work may address time-dependent constraints, auto-correlated noise, and online detection for real-time applications.
Summary updated