More Web Proxy on the site http://driver.im/

article

Change-point detection in time-series data by relative density-ratio estimation

Authors:

Masashi SugiyamaAuthors Info & Claims

Neural Networks, Volume 43

Pages 72 - 83

https://doi.org/10.1016/j.neunet.2013.01.012

Published: 01 July 2013 Publication History

Abstract

The objective of change-point detection is to discover abrupt property changes lying behind time-series data. In this paper, we present a novel statistical change-point detection algorithm based on non-parametric divergence estimation between time-series samples from two retrospective segments. Our method uses the relative Pearson divergence as a divergence measure, and it is accurately and efficiently estimated by a method of direct density-ratio estimation. Through experiments on artificial and real-world datasets including human-activity sensing, speech, and Twitter messages, we demonstrate the usefulness of the proposed method.

References

[1]

Adams, R. P., & MacKay, D. J. C. (2007). Bayesian online changepoint detection. Technical Report. arXiv:0710.3742v1¿{stat.ML}.

[2]

A general class of coefficients of divergence of one distribution from another. Journal of the Royal Statistical Society, Series B. v28 i1. 131-142.

[3]

Detection of abrupt changes: theory and application. Prentice-Hall, Inc., Upper Saddle River, NJ, USA.

[4]

Adaptive control processes: a guided tour. Princeton University Press, Princeton, NJ, USA.

[5]

Bickel, S., Brückner, M., & Scheffer, T. (2007). Discriminative learning for differing training and test distributions. In Proceedings of the 24th international conference on machine learning (pp. 81-88).

[6]

Nonparametric methods in change-point problems. Kluwer Academic Publishers, Dordrecht, the Netherlands.

[7]

Support-vector networks. Machine Learning. v20 i3. 273-297.

[8]

Information-type measures of difference of probability distributions and indirect observation. Studia Scientiarum Mathematicarum Hungarica. v2. 229-318.

[9]

20 nonparametric methods for changepoint problems. In: Krishnaiah, P.R., Rao, C.R. (Eds.), Handbook of statistics, vol. 7, Elsevier, Amsterdam, the Netherlands. pp. 403-425.

[10]

An online kernel change detection algorithm. IEEE Transactions on Signal Processing. v53 i8. 2961-2974.

[11]

An introduction to the bootstrap. Chapman & Hall/CRC, New York, NY, USA.

[12]

Garnett, R., Osborne, M.A., & Roberts, S.J. (2009). Sequential Bayesian prediction in the presence of changepoints. In Proceedings of the 26th annual international conference on machine learning (pp. 345-352).

[13]

Covariate shift by kernel mean matching. In: Quiñonero-Candela, J., Sugiyama, M., Schwaighofer, A., Lawrence, N. (Eds.), Dataset shift in machine learning, MIT Press, Cambridge, MA, USA. pp. 131-160.

[14]

Guralnik, V., & Srivastava, J. (1999). Event detection from time series data. In Proceedings of the fifth ACM SIGKDD international conference on knowledge discovery and data mining (pp. 33-42).

[15]

The marginalized likelihood ratio test for detecting abrupt changes. IEEE Transactions on Automatic Control. v41 i1. 66-78.

[16]

Adaptive filtering and change detection. Wiley, Chichester, UK.

[17]

Kernel change-point analysis. Advances in Neural Information Processing Systems. v21. 609-616.

[18]

Tests of significance. SAGE Publication, Beverly Hills, CA, USA.

[19]

Statistical outlier detection using direct density ratio estimation. Knowledge and Information Systems. v26 i2. 309-336.

[20]

Ide, T., & Tsuda, K. (2007). Change-point detection using Krylov subspace learning. In Proceedings of the SIAM international conference on data mining (pp. 515-520).

[21]

Itoh, N., & Kurths, J. (2010). Change-point detection of climate time series by nonparametric method. In Proceedings of the world congress on engineering and computer science, 2010, vol. 1.

[22]

A least-squares approach to direct importance estimation. Journal of Machine Learning Research. v10. 1391-1445.

[23]

f-divergence estimation and two-sample homogeneity test under semiparametric density-ratio models. IEEE Transactions on Information Theory. v58 i2. 708-720.

[24]

Statistical analysis of kernel-based least-squares density-ratio estimation. Machine Learning. v86 i3. 335-367.

[25]

Kanamori, T., Suzuki, T., & Sugiyama, M. (2013). Computational complexity of kernel-based density-ratio estimation: a condition number analysis. Machine Learning (in press).

[26]

Sequential change-point detection based on direct density-ratio estimation. Statistical Analysis and Data Mining. v5 i2. 114-127.

[27]

Kawahara, Y., Yairi, T., & Machida, K. (2007). Change-point detection in time-series data based on subspace identification. In Proceedings of the 7th IEEE international conference on data mining (pp. 559-564).

Digital Library

[28]

Dual representation of ¿-divergences and applications. Comptes Rendus Mathematique. v336 i10. 857-862.

[29]

On information and sufficiency. Annals of Mathematical Statistics. v22 i1. 79-86.

[30]

Moskvina, V., & Zhigljavsky, A. (2003a). Application of singular-spectrum analysis to change-point detection in time series. School of Mathematics, Cardiff University. http://slb.cf.ac.uk/maths/subsites/stats/changepoint/CH_P_T_S.pdf.

[31]

An algorithm based on singular spectrum analysis for change-point detection. Communications in Statistics: Simulation and Computation. v32 i2. 319-352.

[32]

Nguyen, X., Wainwright, M.J., & Jordan, M.I. (2007). Nonparametric estimation of the likelihood ratio and divergence functionals. In Proceedings of IEEE International Symposium on Information Theory (pp. 2016-2020).

[33]

Estimating divergence functionals and the likelihood ratio by convex risk minimization. IEEE Transactions on Information Theory. v56 i11. 5847-5861.

[34]

Empirical Bayesian change point detection. Graphical Models. v1995. 1-20.

[35]

On the criterion that a given system of deviations from the probable in the case of a correlated system of variables is such that it can be reasonably supposed to have arisen from random sampling. Philosophical Magazine. v50. 157-175.

[36]

Petrović, S., Osborne, M., & Lavrenko, V. (2010). Streaming first story detection with application to Twitter. In Human language technologies: the 2010 annual conference of the North American chapter of the association for computational linguistics (pp. 181-189).

[37]

A review and comparison of changepoint detection techniques for climate data. Journal of Applied Meteorology and Climatology. v46 i6. 900-915.

[38]

Convex analysis. Princeton University Press, Princeton, NJ, USA.

[39]

Sakaki, T., Okazaki, M., & Matsuo, Y. (2010). Earthquake shakes Twitter users: real-time event detection by social sensors. In Proceedings of the 19th international conference on World Wide Web (pp. 851-860).

[40]

Estimating the support of a high-dimensional distribution. Neural Computation. v13 i7. 1443-1471.

[41]

Learning with kernels support vector machines, regularization, optimization, and beyond. MIT Press.

[42]

Estimating the dimension of a model. The Annals of Statistics. v6 i2. 461-464.

[43]

Dimensionality reduction for density ratio estimation in high-dimensional spaces. Neural Networks. v23 i1. 44-59.

[44]

Least-squares two-sample test. Neural Networks. v24 i7. 735-751.

[45]

Density ratio estimation in machine learning. Cambridge University Press, Cambridge, UK.

[46]

Density ratio matching under the Bregman divergence: a unified framework of density ratio estimation. Annals of the Institute of Statistical Mathematics. v64. 1009-1044.

[47]

Direct importance estimation for covariate shift adaptation. Annals of the Institute of Statistical Mathematics. v60 i4. 699-746.

[48]

Direct density-ratio estimation with dimensionality reduction via least-squares hetero-distributional subspace search. Neural Networks. v24 i2. 183-198.

[49]

A unifying framework for detecting outliers and change points from non-stationary time series data. IEEE Transactions on Knowledge and Data Engineering. v18 i4. 482-492.

[50]

Statistical learning theory. Wiley, New York, NY, USA.

[51]

Non-parametric change-point method for differential gene expression detection. PLoS ONE. v6 i5. e20060

[52]

Yamada, M., & Sugiyama, M. (2011). Direct density-ratio estimation with dimensionality reduction via hetero-distributional subspace analysis. In Proceedings of the twenty-fifth AAAI conference on artificial intelligence (pp. 549-554). Aug. 7-11.

[53]

Yamada, M., Suzuki, T., Kanamori, T., Hachiya, H., & Sugiyama, M. (2013). Relative density-ratio estimation for robust distribution comparison. Neural Computation (in press).

[54]

Yamanishi, K., Takeuchi, J., Williams, G., & Milne, P. (2000). On-line unsupervised outlier detection using finite mixtures with discounting learning algorithms. In Proceedings of the sixth ACM SIGKDD international conference on knowledge discovery and data mining (pp. 320-324).

Digital Library

Cited By

Nagumo RFujisawa HSalakhutdinov RKolter ZHeller KWeller AOliver NScarlett JBerkenkamp F(2024)Density ratio estimation with doubly strong robustnessProceedings of the 41st International Conference on Machine Learning10.5555/3692070.3693582(37260-37276)Online publication date: 21-Jul-2024
https://dl.acm.org/doi/10.5555/3692070.3693582
Yoon DWang YYu MHuang EJones JKukkadapu AKocas OWiepert JGoenka KChen SLin YHuang ZKong JChow MTang CWitchel EArpaci-Dusseau ARossbach CKeeton K(2024)FBDetect: Catching Tiny Performance Regressions at Hyperscale through In-Production MonitoringProceedings of the ACM SIGOPS 30th Symposium on Operating Systems Principles10.1145/3694715.3695977(522-540)Online publication date: 4-Nov-2024
https://dl.acm.org/doi/10.1145/3694715.3695977
Banik SSen SSaha SGhosh S(2024)Towards Reducing Continuous Emotion Annotation Effort During Video Consumption: A Physiological Response Profiling ApproachProceedings of the ACM on Interactive, Mobile, Wearable and Ubiquitous Technologies10.1145/36785698:3(1-32)Online publication date: 9-Sep-2024
https://dl.acm.org/doi/10.1145/3678569
Show More Cited By

Change-point detection in time-series data by relative density-ratio estimation
1. Computing methodologies

Recommendations

Sequential change-point detection based on direct density-ratio estimation

Change-point detection is the problem of discovering time points at which properties of time-series data change. This covers a broad range of real-world problems and has been actively discussed in the community of statistics and data mining. In this ...
Change-point detection in time-series data by relative density-ratio estimation
SSPR'12/SPR'12: Proceedings of the 2012 Joint IAPR international conference on Structural, Syntactic, and Statistical Pattern Recognition

The objective of change-point detection is to discover abrupt property changes lying behind time-series data. In this paper, we present a novel statistical change-point detection algorithm that is based on non-parametric divergence estimation between two ...
Multi-stage change-point detection scheme for large-scale simultaneous events

Change-point detection schemes, which represent one type of anomaly detection schemes, are a promising approach for detecting network anomalies, such as attacks and epidemics by unknown viruses and worms. These events are detected as change-points. ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Neural Networks

Neural Networks Volume 43, Issue

July, 2013

124 pages

ISSN:0893-6080

Issue’s Table of Contents

Copyright © Elsevier Ltd © 2013.

Publisher

Elsevier Science Ltd.

United Kingdom

Publication History

Published: 01 July 2013

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

81
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 06 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Nagumo RFujisawa HSalakhutdinov RKolter ZHeller KWeller AOliver NScarlett JBerkenkamp F(2024)Density ratio estimation with doubly strong robustnessProceedings of the 41st International Conference on Machine Learning10.5555/3692070.3693582(37260-37276)Online publication date: 21-Jul-2024
https://dl.acm.org/doi/10.5555/3692070.3693582
Yoon DWang YYu MHuang EJones JKukkadapu AKocas OWiepert JGoenka KChen SLin YHuang ZKong JChow MTang CWitchel EArpaci-Dusseau ARossbach CKeeton K(2024)FBDetect: Catching Tiny Performance Regressions at Hyperscale through In-Production MonitoringProceedings of the ACM SIGOPS 30th Symposium on Operating Systems Principles10.1145/3694715.3695977(522-540)Online publication date: 4-Nov-2024
https://dl.acm.org/doi/10.1145/3694715.3695977
Banik SSen SSaha SGhosh S(2024)Towards Reducing Continuous Emotion Annotation Effort During Video Consumption: A Physiological Response Profiling ApproachProceedings of the ACM on Interactive, Mobile, Wearable and Ubiquitous Technologies10.1145/36785698:3(1-32)Online publication date: 9-Sep-2024
https://dl.acm.org/doi/10.1145/3678569
Siami MNaderpour MRamezani FLu J(2024)Risk Assessment Through Big Data: An Autonomous Fuzzy Decision Support SystemIEEE Transactions on Intelligent Transportation Systems10.1109/TITS.2024.339295925:8(9016-9027)Online publication date: 1-Aug-2024
https://dl.acm.org/doi/10.1109/TITS.2024.3392959
Bayram FAhmed BHallin E(2024)Adaptive data quality scoring operations framework using drift-aware mechanism for industrial applicationsJournal of Systems and Software10.1016/j.jss.2024.112184217:COnline publication date: 1-Nov-2024
https://dl.acm.org/doi/10.1016/j.jss.2024.112184
Bao XChen LZhong JWu DZheng Y(2024)A self-supervised contrastive change point detection method for industrial time seriesEngineering Applications of Artificial Intelligence10.1016/j.engappai.2024.108217133:PBOnline publication date: 1-Jul-2024
https://dl.acm.org/doi/10.1016/j.engappai.2024.108217
Sim HCho HLee H(2024)Changepoint detection-assisted nonparametric clustering for unsupervised temporal sign segmentationEngineering Applications of Artificial Intelligence10.1016/j.engappai.2023.107323127:PBOnline publication date: 1-Jan-2024
https://dl.acm.org/doi/10.1016/j.engappai.2023.107323
Bozas AAndreadis SChatzakou DSymeonidis STheodosiadou OKyriakidis PKokkalas AStathopoulos EDiplaris STsikrika TGialampoukidis IVrochidis SKompatsiaris I(2024)From Research to Applications: What Can We Extract with Social Media Sensing?SN Computer Science10.1007/s42979-024-02712-95:5Online publication date: 24-Apr-2024
https://dl.acm.org/doi/10.1007/s42979-024-02712-9
Wang XHsieh F(2024)An encoding approach for stable change point detectionMachine Language10.1007/s10994-023-06510-x113:7(4133-4163)Online publication date: 1-Jul-2024
https://dl.acm.org/doi/10.1007/s10994-023-06510-x
Cao ZSeeuws NVos MBertrand A(2024)A semi-supervised interactive algorithm for change point detectionData Mining and Knowledge Discovery10.1007/s10618-023-00974-038:2(623-651)Online publication date: 1-Mar-2024
https://dl.acm.org/doi/10.1007/s10618-023-00974-0
Show More Cited By

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents