More Like this

1. Scalable multiple changepoint detection for functional data sequences

   https://doi.org/10.1002/env.2710  

   Harris, Trevor ; Li, Bo ; Tucker, J. Derek ( November 2021 , Environmetrics)

   We propose the multiple changepoint isolation (MCI) method for detecting multiple changes in the mean and covariance of a functional process. We first introduce a pair of projections to represent the variability “between” and “within” the functional observations. We then present an augmented fused lasso procedure to split the projections into multiple regions robustly. These regions act to isolate each changepoint away from the others so that the powerful univariate CUSUM statistic can be applied region‐wise to identify the changepoints. Simulations show that our method accurately detects the number and locations of changepoints under many different scenarios. These include light and heavy tailed data, data with symmetric and skewed distributions, sparsely and densely sampled changepoints, and mean and covariance changes. We show that our method outperforms a recent multiple functional changepoint detector and several univariate changepoint detectors applied to our proposed projections. We also show that MCI is more robust than existing approaches and scales linearly with sample size. Finally, we demonstrate our method on a large time series of water vapor mixing ratio profiles from atmospheric emitted radiance interferometer measurements.

    

   more » « less
2. Improved Time-Localization of Power System Forced Oscillations Using Changepoint Detection

   https://doi.org/10.1109/PESGM48719.2022.9916848  

   Dosiek, Luke ; Hosur, Sanjay ( July 2022 , 2022 IEEE Power & Energy Society General Meeting (PESGM))

   This paper explores the use of changepoint detection (CPD) for an improved time-localization of forced oscillations (FOs) in measured power system data. In order for the autoregressive moving average plus sinusoids (ARMA+S) class of electromechanical mode meters to successfully estimate modal frequency and damping from data that contains a FO, accurate estimates of where the FO exists in time series are needed. Compared to the existing correlation-based method, the proposed CPD method is based on upon a maximum likelihood estimator (MLE) for the detection of an unknown number changes in signal mean to unknown levels at unknown times. Using the pruned exact linear time (PELT) dynamic programming algorithm along with a novel refinement technique, the proposed approach is shown to provide a dramatic improvement in FO start/stop time estimation accuracy while being robust to intermittent FOs. These findings were supported though simulations with the minniWECC model. 

   more » « less
3. A Sharp Error Analysis for the Fused Lasso, with Application to Approximate Changepoint Screening

   Lin, Kevin ; Sharpnack, James L ; Rinaldo, Alessandro ; Tibshirani, Ryan J ( December 2017 , Advances in neural information processing systems)

   In the 1-dimensional multiple changepoint detection problem, we derive a new fast error rate for the fused lasso estimator, under the assumption that the mean vector has a sparse number of changepoints. This rate is seen to be suboptimal (compared to the minimax rate) by only a factor of loglogn. Our proof technique is centered around a novel construction that we call a lower interpolant. We extend our results to misspecified models and exponential family distributions. We also describe the implications of our error analysis for the approximate screening of changepoints. 

   more » « less
4. Reassessing the Constancy of End-to-End Internet Latency

   Davisson, Lily ; Jakovleski, Joakim ; Ngo, Nhiem ; Pham, Chau ; Sommers, Joel ( September 2021 , IFIP Network Traffic Measurement and Analysis Conference)

   A paper by Zhang et al. in 2001, “On the Constancy of Internet Path Properties” [1] examined the constancy of end- to-end packet loss, latency, and throughput using a modest set of hosts deployed in the Internet. In the time since that work, the Internet has changed dramatically, including the flattening of the autonomous system hierarchy and increased deployment of IPv6, among other developments. In this paper, we investigate the constancy of end-to-end Internet latency, revisiting findings of the earlier study. We use latency measurements from RIPE Atlas, choosing a set of 124 anchors with broad geographic distribution and drawn from 112 distinct autonomous systems. The earlier work of Zhang et al. relies on changepoint detection methods to identify mathematically constant time periods. We reimplement the two methods described in that earlier work and use them on the RIPE Atlas latency measurements. We also use a recently- published method (HMM-HDP) that has direct support in a RIPE Atlas API. Comparing the three changepoint detection methods, we find that the two methods used in the earlier work may miss many changepoints caused by common level-shift events. Overall, we find that the recently proposed HMM-HDP method performs substantially better. Moreover, we find that delay spikes—as defined by the earlier work—are an order of magnitude less prevalent than 20 years ago. We also find that maximum change- free regions (CFRs) along paths that we observe in today’s Internet are substantially longer than what was observed in 2001, regardless of the changepoint detection method used. In particular, the 50th percentile maximum CFR was on the order of 30 minutes in the earlier study, but our analysis reveals it to be on the order of 3 days or longer. Moreover, we find that CFR durations appear to have steadily increased over the past 5 years. 

   more » « less
5. Active multi-fidelity Bayesian online changepoint detection

   Gundersen, Gregory W. ; Cai, Diana ; Zhou, Chuteng ; Engelhardt, Barbara E. ; Adams, Ryan P. ( January 2021 , Uncertainty in artificial intelligence)

   null (Ed.)

   Online algorithms for detecting changepoints, or abrupt shifts in the behavior of a time series, are often deployed with limited resources, e.g., to edge computing settings such as mobile phones or industrial sensors. In these scenarios it may be beneficial to trade the cost of collecting an environmental measurement against the quality or "fidelity" of this measurement and how the measurement affects changepoint estimation. For instance, one might decide between inertial measurements or GPS to determine changepoints for motion. A Bayesian approach to changepoint detection is particularly appealing because we can represent our posterior uncertainty about changepoints and make active, cost-sensitive decisions about data fidelity to reduce this posterior uncertainty. Moreover, the total cost could be dramatically lowered through active fidelity switching, while remaining robust to changes in data distribution. We propose a multi-fidelity approach that makes cost-sensitive decisions about which data fidelity to collect based on maximizing information gain with respect to changepoints. We evaluate this framework on synthetic, video, and audio data and show that this information-based approach results in accurate predictions while reducing total cost. 

   more » « less