Change detection

Last updated November 26, 2024

In statistical analysis, change detection or change point detection tries to identify times when the probability distribution of a stochastic process or time series changes. In general the problem concerns both detecting whether or not a change has occurred, or whether several changes might have occurred, and identifying the times of any such changes.

In offline change point detection it is assumed that a sequence of length $T$ is available and the goal is to identify whether any change point(s) occurred in the series. This is an example of post hoc analysis and is often approached using hypothesis testing methods. By contrast, online change point detection is concerned with detecting change points in an incoming data stream.

Background

A time series measures the progression of one or more quantities over time. For instance, the figure above shows the level of water in the Nile river between 1870 and 1970. Change point detection is concerned with identifying whether, and if so when, the behavior of the series changes significantly. In the Nile river example, the volume of water changes significantly after a dam was built in the river. Importantly, anomalous observations that differ from the ongoing behavior of the time series are not generally considered change points as long as the series returns to its previous behavior afterwards.

Mathematically, we can describe a time series as an ordered sequence of observations $(x_{1},x_{2},\ldots )$ . We can write the joint distribution of a subset $x_{a:b}=(x_{a},x_{a+1},\ldots ,x_{b})$ of the time series as $p(x_{a:b})$ . If the goal is to determine whether a change point occurred at a time $\tau$ in a finite time series of length $T$ , then we really ask whether $p(x_{1:\tau })$ equals $p(x_{\tau +1:T})$ . This problem can be generalized to the case of more than one change point.

Algorithms

Online change detection

Using the sequential analysis ("online") approach, any change test must make a trade-off between these common metrics:

In a Bayes change-detection problem, a prior distribution is available for the change time.

Online change detection is also done using streaming algorithms.

Offline change detection

Basseville (1993, Section 2.6) discusses offline change-in-mean detection with hypothesis testing based on the works of Page^[2] and Picard^[3] and maximum-likelihood estimation of the change time, related to two-phase regression. Other approaches employ clustering based on maximum likelihood estimation,^{[ citation needed ]}, use optimization to infer the number and times of changes,^[4] via spectral analysis,^[5] or singular spectrum analysis.^[6]

Statistically speaking, change detection is often considered as a model selection problem.^[8]^[9]^[10] Models with more changepoints fit data better but with more parameters. The best trade-off can be found by optimizing a model selection criterion such as Akaike information criterion and Bayesian information criterion. Bayesian model selection has also been used. Bayesian methods often quantify uncertainties of all sorts and answer questions hard to tackle by classical methods, such as what is the probability of having a change at a given time and what is the probability of the data having a certain number of changepoints.^[8]

"Offline" approaches cannot be used on streaming data because they need to compare to statistics of the complete time series, and cannot react to changes in real-time but often provide a more accurate estimation of the change time and magnitude.

Applications

Change detection tests are often used in manufacturing for quality control, intrusion detection, spam filtering, website tracking, and medical diagnostics.

Linguistic change detection

Linguistic change detection refers to the ability to detect word-level changes across multiple presentations of the same sentence. Researchers have found that the amount of semantic overlap (i.e., relatedness) between the changed word and the new word influences the ease with which such a detection is made (Sturt, Sanford, Stewart, & Dawydiak, 2004). Additional research has found that focussing one's attention to the word that will be changed during the initial reading of the original sentence can improve detection. This was shown using italicized text to focus attention, whereby the word that will be changing is italicized in the original sentence (Sanford, Sanford, Molle, & Emmott, 2006), as well as using clefting constructions such as "It was the tree that needed water." (Kennette, Wurm, & Van Havermaet, 2010). These change-detection phenomena appear to be robust, even occurring cross-linguistically when bilinguals read the original sentence in their native language and the changed sentence in their second language (Kennette, Wurm & Van Havermaet, 2010). Recently, researchers have detected word-level changes in semantics across time by computationally analyzing temporal corpora (for example: the word "gay" has acquired a new meaning over time) using change point detection.^[11] This is also applicable to reading non-words such as music. Even though music is not a language, it is still written and people to comprehend its meaning which involves perception and attention, allowing change detection to be present.^[12]

Visual change detection

Visual change detection is one's ability to detect differences between two or more images or scenes.^[13] This is essential in many everyday tasks. One example is detecting changes on the road to drive safely and successfully. Change detection is crucial in operating motor vehicles to detect other vehicles, traffic control signals, pedestrians, and more.^[14] Another example of utilizing visual change detection is facial recognition. When noticing one's appearance, change detection is vital, as faces are "dynamic" and can change in appearance due to different factors such as "lighting conditions, facial expressions, aging, and occlusion".^[15] Change detection algorithms use various techniques, such as "feature tracking, alignment, and normalization," to capture and compare different facial features and patterns across individuals in order to correctly identify people.^[15] Visual change detection involves the integration of "multiple sensors inputs, cognitive processes, and attentional mechanisms," often focusing on multiple stimuli at once.^[16] The brain processes visual information from the eyes, compares it with previous knowledge stored in memory, and identifies differences between the two stimuli. This process occurs rapidly and unconsciously, allowing individuals to respond to changing environments and make necessary adjustments to their behavior.^[17]

Cognitive change detection

There have been several studies conducted to analyze the cognitive functions of change detection. With cognitive change detection, researchers have found that most people overestimate their change detection, when in reality, they are more susceptible to change blindness than they think.^[18] Cognitive change detection has many complexities based on external factors, and sensory pathways play a key role in determining one's success in detecting changes. One study proposes and proves that the multi-sensory pathway network, which consists of three sensory pathways, significantly increases the effectiveness of change detection.^[19] Sensory pathway one fuses the stimuli together, sensory pathway two involves using the middle concatenation strategy to learn the changed behavior, and sensory pathway three involves using the middle difference strategy to learn the changed behavior.^[19] With all three of these working together, change detection has a significantly increased success rate.^[19] It was previously believed that the posterior parietal cortex (PPC) played a role in enhancing change detection due to its focus on "sensory and task-related activity".^[20] However, studies have also disproven that the PPC is necessary for change detection; although these have high functional correlation with each other, the PPC's mechanistic involvement in change detection is insignificant.^[20] Moreover, top-down processing plays an important role in change detection because it enables people to resort to background knowledge which then influences perception, which is also common in children. Researchers have conducted a longitudinal study surrounding children's development and the change detection throughout infancy to adulthood.^[21] In this, it was found that change detection is stronger in young infants compared to older children, with top-down processing being a main contributor to this outcome.^[21]

Related Research Articles

Bayesian inference is a method of statistical inference in which Bayes' theorem is used to calculate a probability of a hypothesis, given prior evidence, and update it as more information becomes available. Fundamentally, Bayesian inference uses a prior distribution to estimate posterior probabilities. Bayesian inference is an important technique in statistics, and especially in mathematical statistics. Bayesian updating is particularly important in the dynamic analysis of a sequence of data. Bayesian inference has found application in a wide range of activities, including science, engineering, philosophy, medicine, sport, and law. In the philosophy of decision theory, Bayesian inference is closely related to subjective probability, often called "Bayesian probability".

A hidden Markov model (HMM) is a Markov model in which the observations are dependent on a latent Markov process. An HMM requires that there be an observable process $whose outcomes depend on the outcomes of in a known way. Since cannot be observed directly, the goal is to learn about state of by observing . By definition of being a Markov model, an HMM has an additional requirement that the outcome of at time must be "influenced" exclusively by the outcome of at and that the outcomes of and at must be conditionally independent of at given at time . Estimation of the parameters in an HMM can be performed using maximum likelihood estimation. For linear chain HMMs, the Baum-Welch algorithm can be used to estimate parameters.$

Pattern recognition is the task of assigning a class to an observation based on patterns extracted from data. While similar, pattern recognition (PR) is not to be confused with pattern machines (PM) which may possess (PR) capabilities but their primary function is to distinguish and create emergent patterns. PR has applications in statistical data analysis, signal processing, image analysis, information retrieval, bioinformatics, data compression, computer graphics and machine learning. Pattern recognition has its origins in statistics and engineering; some modern approaches to pattern recognition include the use of machine learning, due to the increased availability of big data and a new abundance of processing power.

A Bayesian network is a probabilistic graphical model that represents a set of variables and their conditional dependencies via a directed acyclic graph (DAG). While it is one of several forms of causal notation, causal networks are special cases of Bayesian networks. Bayesian networks are ideal for taking an event that occurred and predicting the likelihood that any one of several possible known causes was the contributing factor. For example, a Bayesian network could represent the probabilistic relationships between diseases and symptoms. Given symptoms, the network can be used to compute the probabilities of the presence of various diseases.

In statistics, Markov chain Monte Carlo (MCMC) is a class of algorithms used to draw samples from a probability distribution. Given a probability distribution, one can construct a Markov chain whose elements' distribution approximates it – that is, the Markov chain's equilibrium distribution matches the target distribution. The more steps that are included, the more closely the distribution of the sample matches the actual desired distribution.

Psychophysics quantitatively investigates the relationship between physical stimuli and the sensations and perceptions they produce. Psychophysics has been described as "the scientific study of the relation between stimulus and sensation" or, more completely, as "the analysis of perceptual processes by studying the effect on a subject's experience or behaviour of systematically varying the properties of a stimulus along one or more physical dimensions".

In digital image processing and computer vision, image segmentation is the process of partitioning a digital image into multiple image segments, also known as image regions or image objects. The goal of segmentation is to simplify and/or change the representation of an image into something that is more meaningful and easier to analyze. Image segmentation is typically used to locate objects and boundaries in images. More precisely, image segmentation is the process of assigning a label to every pixel in an image such that pixels with the same label share certain characteristics.

<span class="mw-page-title-main">Event-related potential</span> Brain response that is the direct result of a specific sensory, cognitive, or motor event

An event-related potential (ERP) is the measured brain response that is the direct result of a specific sensory, cognitive, or motor event. More formally, it is any stereotyped electrophysiological response to a stimulus. The study of the brain in this way provides a noninvasive means of evaluating brain functioning.

Sensor fusion is a process of combining sensor data or data derived from disparate sources so that the resulting information has less uncertainty than would be possible if these sources were used individually. For instance, one could potentially obtain a more accurate location estimate of an indoor object by combining multiple data sources such as video cameras and WiFi localization signals. The term uncertainty reduction in this case can mean more accurate, more complete, or more dependable, or refer to the result of an emerging view, such as stereoscopic vision.

Bayesian inference of phylogeny combines the information in the prior and in the data likelihood to create the so-called posterior probability of trees, which is the probability that the tree is correct given the data, the prior and the likelihood model. Bayesian inference was introduced into molecular phylogenetics in the 1990s by three independent groups: Bruce Rannala and Ziheng Yang in Berkeley, Bob Mau in Madison, and Shuying Li in University of Iowa, the last two being PhD students at the time. The approach has become very popular since the release of the MrBayes software in 2001, and is now one of the most popular methods in molecular phylogenetics.

The nested sampling algorithm is a computational approach to the Bayesian statistics problems of comparing models and generating samples from posterior distributions. It was developed in 2004 by physicist John Skilling.

In the study of complex networks, a network is said to have community structure if the nodes of the network can be easily grouped into sets of nodes such that each set of nodes is densely connected internally. In the particular case of non-overlapping community finding, this implies that the network divides naturally into groups of nodes with dense connections internally and sparser connections between groups. But overlapping communities are also allowed. The more general definition is based on the principle that pairs of nodes are more likely to be connected if they are both members of the same community(ies), and less likely to be connected if they do not share communities. A related but different problem is community search, where the goal is to find a community that a certain vertex belongs to.

Bayesian approaches to brain function investigate the capacity of the nervous system to operate in situations of uncertainty in a fashion that is close to the optimal prescribed by Bayesian statistics. This term is used in behavioural sciences and neuroscience and studies associated with this term often strive to explain the brain's cognitive abilities based on statistical principles. It is frequently assumed that the nervous system maintains internal probabilistic models that are updated by neural processing of sensory information using methods approximating those of Bayesian probability.

In statistics and machine learning, ensemble methods use multiple learning algorithms to obtain better predictive performance than could be obtained from any of the constituent learning algorithms alone. Unlike a statistical ensemble in statistical mechanics, which is usually infinite, a machine learning ensemble consists of only a concrete finite set of alternative models, but typically allows for much more flexible structure to exist among those alternatives.

A sense is a biological system used by an organism for sensation, the process of gathering information about the surroundings through the detection of stimuli. Although, in some cultures, five human senses were traditionally identified as such, many more are now recognized. Senses used by non-human organisms are even greater in variety and number. During sensation, sense organs collect various stimuli for transduction, meaning transformation into a form that can be understood by the brain. Sensation and perception are fundamental to nearly every aspect of an organism's cognition, behavior and thought.

Models of neural computation are attempts to elucidate, in an abstract and mathematical fashion, the core principles that underlie information processing in biological nervous systems, or functional components thereof. This article aims to provide an overview of the most definitive models of neuro-biological computation as well as the tools commonly used to construct and analyze them.

The free energy principle is a theoretical framework suggesting that the brain reduces surprise or uncertainty by making predictions based on internal models and updating them using sensory input. It highlights the brain's objective of aligning its internal model and the external world to enhance prediction accuracy. This principle integrates Bayesian inference with active inference, where actions are guided by predictions and sensory feedback refines them. It has wide-ranging implications for comprehending brain function, perception, and action.

Biological motion perception is the act of perceiving the fluid unique motion of a biological agent. The phenomenon was first documented by Swedish perceptual psychologist, Gunnar Johansson, in 1973. There are many brain areas involved in this process, some similar to those used to perceive faces. While humans complete this process with ease, from a computational neuroscience perspective there is still much to be learned as to how this complex perceptual problem is solved. One tool which many research studies in this area use is a display stimuli called a point light walker. Point light walkers are coordinated moving dots that simulate biological motion in which each dot represents specific joints of a human performing an action.

Jurimetrics is the application of quantitative methods, especially probability and statistics, to law. In the United States, the journal Jurimetrics is published by the American Bar Association and Arizona State University. The Journal of Empirical Legal Studies is another publication that emphasizes the statistical analysis of law.

In neuroscience, predictive coding is a theory of brain function which postulates that the brain is constantly generating and updating a "mental model" of the environment. According to the theory, such a mental model is used to predict input signals from the senses that are then compared with the actual input signals from those senses. Predictive coding is member of a wider set of theories that follow the Bayesian brain hypothesis.

References

↑ van den Burg, Gerrit J. J.; Williams, Christopher K. I. (May 26, 2020). "An Evaluation of Change Point Detection Algorithms". arXiv: 2003.06222 [stat.ML].
↑ Page, E. S. (June 1957). "On problems in which a change in a parameter occurs at an unknown point". Biometrika. 44 (1/2): 248–252. doi:10.1093/biomet/44.1-2.248. JSTOR 2333258.
↑ Picard, Dominique (1985). "Testing and estimating change-points in time series". Advances in Applied Probability. 17 (4): 841–867. doi:10.2307/1427090. JSTOR 1427090. S2CID 123026208.
↑ Yao, Yi-Ching (1988-02-01). "Estimating the number of change-points via Schwarz' criterion". Statistics & Probability Letters. 6 (3): 181–189. doi:10.1016/0167-7152(88)90118-6. ISSN 0167-7152.
↑ Ghaderpour, E.; Vujadinovic, T. (2020). "Change Detection within Remotely Sensed Satellite Image Time Series via Spectral Analysis". Remote Sensing. 12 (23): 4001. Bibcode:2020RemS...12.4001G. doi: 10.3390/rs12234001 . hdl: 11573/1655315 .
↑ Alanqary, Arwa (2021). "Change Point Detection via Multivariate Singular Spectrum Analysis". Advances in Neural Information Processing Systems. 34: 23218–30. ISBN 978-1-7138-4539-3.
↑ Li, Yang; Zhao, Kaiguang; Hu, Tongxi; Zhang, Xuesong. "BEAST: A Bayesian Ensemble Algorithm for Change-Point Detection and Time Series Decomposition". GitHub .
1 2 Zhao, Kaiguang; Wulder, Michael A; Hu, Tongx; Bright, Ryan; Wu, Qiusheng; Qin, Haiming; Li, Yang (2019). "Detecting change-point, trend, and seasonality in satellite time series data to track abrupt changes and nonlinear dynamics: A Bayesian ensemble algorithm". Remote Sensing of Environment. 232: 111181. Bibcode:2019RSEnv.23211181Z. doi: 10.1016/j.rse.2019.04.034 . hdl: 11250/2651134 . S2CID 201310998.
↑ Chen, Jie; Gupta, Arjun K (2001). "On change point detection and estimation". Communications in Statistics - Simulation and Computation. 30 (3): 665–697. doi:10.1081/SAC-100105085. S2CID 121138768.
↑ Yoshiyuki, Ninomiya (2015). "Change-point model selection via AIC". Annals of the Institute of Statistical Mathematics. 67 (5): 943–961. doi:10.1007/s10463-014-0481-x. S2CID 254234584.
↑ Kulkarni Vivek; Rfou Rami; Perozzi Bryan; Skiena Steven (2015). "Statistically Significant Detection of Linguistic Change". Proceedings of the 24th International Conference on World Wide Web. pp. 625–635. arXiv: 1411.3315 . doi:10.1145/2736277.2741627. ISBN 9781450334693. S2CID 9298083.
↑ Kleinsmith, Abigail L. (2023). "Expertise effects on visual change detection in the music reading domain: Evidence from eye movements". In Dissertation Abstracts International: Section B: The Sciences and Engineering (Vol. 84, Issue 3–B).
↑ Ramey, Michelle M.; Henderson, John M.; Yonelinas, Andrew P. (December 2022). "Eye movements dissociate between perceiving, sensing, and unconscious change detection in scenes". Psychonomic Bulletin & Review. 29 (6): 2122–2132. doi: 10.3758/s13423-022-02122-z . ISSN 1069-9384. PMC 11110961 . PMID 35653039. S2CID 249276616.
↑ Morgenstern, Tina; Trommler, Daniel; Naujoks, Frederik; Karl, Ines; Krems, Josef F.; Keinath, Andreas (February 2023). "Comparing the sensitivity of the box task combined with the detection response task to the lane change test". Transportation Research Part F: Traffic Psychology and Behaviour. 93: 159–171. Bibcode:2023TRPF...93..159M. doi:10.1016/j.trf.2023.01.004. S2CID 256050914.
1 2 Ventura, Paulo; Guerreiro, José Carlos; Pereira, Alexandre; Delgado, João; Rosário, Vivienne; Farinha-Fernandes, António; Domingues, Miguel; Cruz, Francisco; Faustino, Bruno; Wong, Alan C.-N. (April 2022). "Change detection vs. change localization for own-race and other-race faces". Attention, Perception, & Psychophysics. 84 (3): 627–637. doi: 10.3758/s13414-022-02448-9 . ISSN 1943-3921. PMID 35174465. S2CID 246904080.
↑ He, Chuanxiuyue; Rathbun, Zoe; Buonauro, Daniel; Meyerhoff, Hauke S.; Franconeri, Steven L.; Stieff, Mike; Hegarty, Mary (August 2022). "Symmetry and spatial ability enhance change detection in visuospatial structures". Memory & Cognition. 50 (6): 1186–1200. doi:10.3758/s13421-022-01332-z. ISSN 0090-502X. PMC 9365739 . PMID 35705852.
↑ Williams, Jamal R.; Robinson, Maria M.; Schurgin, Mark W.; Wixted, John T.; Brady, Timothy F. (December 2022). "You cannot "count" how many items people remember in visual working memory: The importance of signal detection–based measures for understanding change detection performance". Journal of Experimental Psychology: Human Perception and Performance. 48 (12): 1390–1409. doi:10.1037/xhp0001055. ISSN 1939-1277. PMC 10257385 . PMID 36222675.
↑ Barnas, Adam J.; Ward, Emily J. (October 2022). "Metacognitive judgements of change detection predict change blindness". Cognition. 227: 105208. doi: 10.1016/j.cognition.2022.105208 . PMID 35792349. S2CID 239626887.
1 2 3 Liu, Kang; Li, Xuelong (July 2022). "Bio-inspired Multi-Sensory Pathway Network for Change Detection". Cognitive Computation. 14 (4): 1421–1434. doi:10.1007/s12559-021-09968-w. ISSN 1866-9956. S2CID 247283289.
1 2 Oude Lohuis, Matthijs N.; Marchesi, Pietro; Pennartz, Cyriel M.A.; Olcese, Umberto (2022-06-29). "Functional (ir)Relevance of Posterior Parietal Cortex during Audiovisual Change Detection". The Journal of Neuroscience. 42 (26): 5229–5245. doi:10.1523/JNEUROSCI.2150-21.2022. ISSN 0270-6474. PMC 9236290 . PMID 35641187.
1 2 Deguire, Florence; López-Arango, Gabriela; Knoth, Inga Sophia; Côté, Valérie; Agbogba, Kristian; Lippé, Sarah (2022-11-21). "Developmental course of the repetition effect and change detection responses from infancy through childhood: a longitudinal study". Cerebral Cortex. 32 (23): 5467–5477. doi:10.1093/cercor/bhac027. ISSN 1047-3211. PMC 9712715 . PMID 35149872.