Abstract
This paper studies online change detection in exponential families when both the parameters before and after change are unknown. We follow a standard statistical approach to sequential change detection with generalized likelihood ratio test statistics. We interpret these statistics within the framework of information geometry, hence providing a unified view of change detection for many common statistical models and corresponding distance functions. Using results from convex duality, we also derive an efficient scheme to compute the exact statistics sequentially, which allows their use in online settings where they are usually approximated for the sake of tractability. This is applied to real-world datasets of various natures, including onset detection in audio signals.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
References
Adams, R.P., MacKay, D.J.C.: Bayesian online changepoint detection. Technical report, University of Cambridge, Cambridge, UK (2007)
Amari, S.-I., Nagaoka, H.: Methods of Information Geometry. American Mathematical Society, Providence (2000)
Barndorff-Nielsen, O.: Information and Exponential Families in Statistical Theory. Wiley, Chichester (1978)
Basseville, M., Nikiforov, I.V.: Detection of Abrupt Changes: Theory and Application. Prentice-Hall, Inc., Upper Saddle River (1993)
Brown, L.D.: Fundamentals of Statistical Exponential Families with Applications in Statistical Decision Theory. Institute of Mathematical Statistics, Hayward (1986)
Canu, S., Smola, A.: Kernel methods and the exponential family. Neurocomputing 69(7-9), 714–720 (2006)
Cont, A., Dubnov, S., Assayag, G.: On the information geometry of audio streams with applications to similarity computing. IEEE Transactions on Audio, Speech, and Language Processing 19(4), 837–846 (2011)
Desobry, F., Davy, M., Doncarli, C.: An online kernel change detection algorithm. IEEE Transactions on Signal Processing 53(8), 2961–2974 (2005)
Dessein, A.: Computational Methods of Information Geometry with Real-Time Applications in Audio Signal Processing. PhD thesis, Université Pierre et Marie Curie, Paris, France (December 2012)
Dessein, A., Cont, A.: An information-geometric approach to real-time audio segmentation. IEEE Signal Processing Letters 20(4), 331–334 (2013)
Fearnhead, P.: Exact and efficient Bayesian inference for multiple changepoint problems. Statistics and Computing 16(2), 203–213 (2006)
Girshick, M.A., Rubin, H.: A Bayes approach to a quality control model. The Annals of Mathematical Statistics 23(1), 114–125 (1952)
Guédon, Y.: Exploring the segmentation space for the assessment of multiple change-point models. Technical report, Institut National de Recherche en Informatique et en Automatique, Sophia Antipolis, France (2008)
Harchaoui, Z., Bach, F., Moulines, E.: Kernel change-point analysis. In: Advances in Neural Information Processing Systems, vol. 21, pp. 609–616. NIPS Foundation, La Jolla (2009)
Harchaoui, Z., Lévy-Leduc, C.: Multiple change-point estimation with a total variation penalty. Journal of the American Statistical Association 105(492), 1480–1493 (2010)
Killick, R., Fearnhead, P., Eckley, I.A.: Optimal detection of changepoints with a linear computational cost. Technical report, Lancaster University, Lancaster, UK (2011)
Lai, T.L., Xing, H.: Sequential change-point detection when the pre- and post-change parameters are unknown. Sequential Analysis: Design Methods and Applications 29(2), 162–175 (2010)
Leveau, P., Daudet, L., Richard, G.: Methodology and tools for the evaluation of automatic onset detection algorithms in music. In: 5th International Conference on Music Information Retrieval, Barcelona, Spain, pp. 72–75 (October 2004)
Lorden, G.: Procedures for reacting to a change in distribution. The Annals of Mathematical Statistics 42(6), 1897–1908 (1971)
Page, E.S.: Continuous inspection schemes. Biometrika 41(1-2), 100–115 (1954)
Pollak, M., Siegmund, D.: Approximations to the expected sample size of certain sequential tests. The Annals of Statistics 3(6), 1267–1282 (1975)
Polunchenko, A.S., Tartakovsky, A.G.: State-of-the-art in sequential change-point detection. Methodology and Computing in Applied Probability 14(3), 649–684 (2012)
Poor, V.H., Hadjiliadis, O.: Quickest Detection. Cambridge University Press, New York (2009)
Roberts, S.W.: A comparison of some control charts procedures. Technometrics 8(3), 411–430 (1966)
Rockafellar, R.T.: Convex Analysis. Princeton University Press, Princeton (1970)
Shiryaev, A.N.: On optimum methods in quickest detection problems. Theory of Probability and its Applications 8(1), 22–46 (1963)
Siegmund, D., Venkatraman, E.S.: Using the generalized likelihood ratio statistic for sequential detection of a change-point. The Annals of Statistics 23(1), 255–271 (1995)
Turner, R., Saatci, Y., Rasmussen, C.E.: Adaptive sequential Bayesian change point detection. In: NIPS Workshop on Temporal Segmentation, Whistler, Canada (December 2009)
Vert, J.-P., Bleakley, K.: Fast detection of multiple change-points shared by many signals using group LARS. In: Advances in Neural Information Processing Systems, vol. 23, pp. 2343–2351. NIPS Foundation, La Jolla (2010)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Dessein, A., Cont, A. (2013). Online Change Detection in Exponential Families with Unknown Parameters. In: Nielsen, F., Barbaresco, F. (eds) Geometric Science of Information. GSI 2013. Lecture Notes in Computer Science, vol 8085. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-40020-9_70
Download citation
DOI: https://doi.org/10.1007/978-3-642-40020-9_70
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-40019-3
Online ISBN: 978-3-642-40020-9
eBook Packages: Computer ScienceComputer Science (R0)