{'fraction_non_alphanumeric': 0.04341025432680588, 'fraction_numerical': 0.015397741122938166, 'mean_word_length': 4.014157669586474, 'pattern_counts': {'":': 0, '<': 35, '<?xml version=': 0, '>': 26, 'https://': 1, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 20, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
A linear time method for the detection of point and collective anomalies

The challenge of efficiently identifying anomalies in data sequences is an important statistical problem that now arises in many applications. Whilst there has been substantial work aimed at making statistical analyses robust to outliers, or point anomalies, there has been much less work on detecting anomalous segments, or collective anomalies. By bringing together ideas from changepoint detection and robust statistics, we introduce Collective And Point Anomalies (CAPA), a computationally efficient approach that is suitable when collective anomalies are characterised by either a change in mean, variance, or both, and distinguishes them from point anomalies. Theoretical results establish the consistency of CAPA at detecting collective anomalies and empirical results show that CAPA has close to linear computational cost as well as being more accurate at detecting and locating collective anomalies than other approaches. We demonstrate the utility of CAPA through its ability to detect exoplanets from light curve data from the Kepler telescope.


Introduction
Anomaly detection is an area of considerable importance for many time series applications, such as fault detection or fraud prevention, and has been subject to increasing attention in recent years. See [4] and [25] for comprehensive reviews of the area. As [4] highlight, anomalies can fall into one of three categories: global anomalies, contextual anomalies, or collective anomalies. Global anomalies and contextual anomalies are defined as single observations which are outliers with regards to the complete dataset and their local context respectively. Conversely, collective anomalies are defined as sequences of observations which are not anomalous when considered individually, but together form an anomalous pattern.
A number of different approaches can be taken to detect point (i.e. contextual and/or global) anomalies. These are observations which do not conform with the pattern of the data. Hence, the problem of detecting point anomalies can be reformulated as inferring the general pattern of the data in a manner that is robust to anomalies. The field of robust statistics offers a wide range of methods aimed at this problem. For instance, [28] proposed S estimators to robustly estimate the mean and variance, which were extended to a multivariate setting by [29]. A wide variety of robust time series models also exist. For example, [21] proposed a robust ARMA model, [22] a robust ARCH model, and [23] a robust GARCH model. A robust non-parametric method, which decomposes time series into trend, seasonal component, and residual was proposed by [5].
The machine learning community has also provided a rich corpus of work for the detection of point anomalies. Commonly used methods include nearest neighbour based approaches, such as the local outlier factor (Breunig et al. [3]), and information theoretical methods such as the one introduced by [8]. It is beyond the scope of this paper to review them all. Instead we refer to excellent reviews that can be found in [4] and [25].
One common drawback of several point anomaly approaches is their inability to detect anomalous segments, or collective anomalies. Such features are of significance in many applications. One example is the analysis of brain imaging data, where periods in which the brain activity deviates from the pattern of the rest state have been associated with sudden shocks ( [1]). Another example is in detecting regions of the genome with unusual copy number ( [2] [31] [36]), with such copy number variation being associated with diseases such as cancer ( [12]).
The main contribution of this paper is to use an epidemic changepoint model as a principled framework for both collective and point anomalies. An epidemic changepoint model assumes that the data follow a certain typical distribution at all time, except during some anomalous time windows. The behaviour changes away from the typical distribution at the beginning of these windows and returns to it at the end. These epidemic changes can naturally be interpreted as collective anomalies. For the case in which collective anomalies are characterised by epidemic changes in mean and/or variance, point anomalies can additionally be modelled as epidemic changes of length one in variance only. This framework thus allows for the joint modelling and detection of collective anomalies and point anomalies. We therefore call the algorithm Collective And Point Anomalies (CAPA).
As a motivation for our work, and to help make the ideas in this paper concrete, consider the problem of detecting exoplanets via the so called transit method first proposed by [33]. The luminosity of a star is measured at regular intervals, with the aim of detecting periodically recurring segments of reduced luminosity. Such periods indicate the transit of a planet ( [30]) and can naturally be interpreted as collective anomalies. The light curves are typically preprocessed ( [24]) and both the raw and whitened light curves can be accessed online. We have included the whitened light curve of the star Kepler 1132 in Figure 1 to illustrate the nature of this type of data. We note the presence of a global anomaly on day 1550 and the noisy nature of the data, making the detection of transits challenging given the weak signal induced by planetary transits. Indeed, even the transit of Jupiter past the sun reduces the latter's luminosity by only 1% ( [30]).
Existing work on the detection of collective anomalies can be found in the statistics and machine learning literature. On the statistical side, hidden Markov models have been proposed, which assume that a hidden state obeying a Markov chain determines whether the data produced is anomalous or typical ( [32]). The underlying assumption that anomalous segments share one or multiple common behaviours is very attractive for the exoplanet detection application outlined above, but can be a constraint in others. Hidden Markov models also suffer from the fact that they are not robust to global anomalies which are present in the Kepler data, as can be seen in Figure 1. Moreover, they tend to be slow to fit, which is an important disadvantage in many modern, big-data applications. For example, there are currently 40 million light curves, similar to that shown in Figure 1, that have been gathered and need analysing. Conversely, machine learning methods include LinkedIn's luminol ( [19]) which uses a sign test to detect segments of anomalous mean. However, as we will see in the simulation section of this paper, this method's performance can be poor.
Epidemic changepoints can be modelled as two classical changepoints, for the detection of which a variety of methods have been proposed ( [6], [7], [11], [15], [18]). However, this approach does not exploit the fact that the behaviour of the segment before the start and after the end of an epidemic segment is the same, which reduces its statistical power. This is a disadvantage, especially when faced with a weak signal, like in the light curve data.
The epidemic changepoint problem as such was first considered by [17], who use a cumulative sum type statistic to detect them [34]. The main corpus of work addressing the problem of their detection has since been driven by the analysis of neuroimaging and genome data. An early application of epidemic changepoints to neuroimaging data can be found in [27], who use a hidden Markov model to detect epidemic changes in mean. This was later extended by [1]. Both methods are vulnerable to point anomalies, a shortcoming in some applications like the one we consider in this paper. Another limitation is that both approaches assume the presence of at most one change. Conversely, motivated by challenges arising in Genomics, a range of methods, both univariate and multivariate, have been proposed to detect epidemic changes in mean, mainly by considering sum of squares type test statistics (see [12] [31] [36]), sometimes in combination with hidden states. They are therefore vulnerable to global anomalies. A more general Bayesian hidden state method for the detection of anomalous segments was proposed by [2].
The article is organised as follows: We begin by introducing a parametric model with epidemic changes in Section 2. This provides a general framework for collective anomalies, the location of which we infer by minimising a penalised cost. Motivated by our application, we will place a special emphasis on the detection of joint epidemic changes in mean and variance and show that epidemic changes of length one in variance only can be incorporated to model point anomalies.
In the classical changepoint setting, information is not typically shared between different segments of the data. However, in this epidemic setting, the typical parameter is shared, making it impossible to minimise the penalised cost via the dynamic programming approach of [10]. We therefore provide an algorithm in Section 3 which minimises an approximation to the penalised cost based on a robust estimate of the parameter of the typical distribution. This approximation can be minimised by a dynamic program, which can be pruned in a fashion similar to [15]. As a result of this pruning, we find that the run time of CAPA is close to O(n) in some cases.
We present theoretical results regarding the consistency of CAPA at detecting collective anomalies in Section 4. Specifically, we introduce a proof of consistency for the detection of joint classical changes in mean and variance using a penalised cost approach, which is of independent interest. We then compare CAPA to other methods in a simulation study in Section 5 and show that it outperforms them, especially in the presence of point anomalies. We conclude the paper by demonstrating in Section 6 that CAPA can be used to detect Kepler 1132-b, an exoplanet which orbits Kepler 1132 ( [20]). The proofs of the theoretical results are all given in the appendix and the supplementary material can be found at the end of the paper. Code implementing CAPA can be accessed at https://github.com/Fisch-Alex/anomaly.

A Modelling Framework for Collective Anomalies
We assume that the data follow a parametric model and model collective anomalies as epidemic changes in the model parameters. Whilst, in practice, it is unlikely that the distribution of the data in an anomalous segment will belong to the same family of distributions as the distribution of the typical data, it can nevertheless be expected that a set of parameters different from the typical distribution's will offer a better fit. We say that data x 1 , ..., x n follow a parametric epidemic changepoint model if where θ 0 is the usually unknown parameter of the typical distribution, from which the model deviates during the K anomalous segments (s 1 , e 1 ),...,(s K , e K ). We assume these windows do not overlap, i.e. e 1 ≤ s 2 , ..., e K−1 ≤ s K . Note that fitting an epidemic changepoint requires only one new set of parameters for θ, since the typical parameter is shared across the non-anomalous segments. This compares favourably with the two additional sets of parameters for θ introduced when an epidemic changepoint is fitted using two classical changepoints. We therefore gain statistical power. This gain is particularly important when θ is high dimensional. It is possible to infer the number and location of epidemic changes by choosingK, (s 1 ,ẽ 1 ),...,(sK,ẽK), and θ 0 , which minimise the penalised cost subject to e i − s i ≥l, wherel is the minimum segment length for an appropriate cost function C(x, θ) and a suitable penalty β. For example, C(x, θ) could be defined as the negative log-likelihood of x under the parametric model using parameter θ. The penalty β could then be set to (2 + ||θ|| 0 ) log(n) and this would be a BIC type penalty. Using the formulation in (1), we can infer the location of joint epidemic changes in mean and variance by minimising the penalised cost related to the negative log-likelihood of Gaussian data. In this case θ = (µ, σ 2 ) contains both the mean and variance and we minimise using a minimum segment length of 2 to account for the fact that θ is two dimensional. It is well known that many changepoint detection methods struggle in the presence of point anomalies in the data and tend to fit two changepoints around each of them ( [6]). An approach based on minimising the above cost function is not intrinsically immune to it. However, we can modify the model by allowing epidemic changes, in variance only, of length one to address this issue. We therefore chooseK, (s 1 ,ẽ 1 ),...,(sK,ẽK), µ 0 , σ 0 , as well as the set of point anomalies O ⊂ {1, ..., n}, which minimise the modified penalised cost whereβ is a penalty smaller than β. This modification ensures that it is now cheaper to fit an outlier as an epidemic changepoint in variance only than as a full epidemic change. Consequently, the method becomes robust against point anomalies, fitting epidemic changes only around true collective anomalies. This modification has the added benefit that it allows the algorithm to detect and distinguish between point and collective anomalies. This property is important for a range of applications in which collective and point anomalies have different interpretations (see Section 6 for an example).

Inference for Collective Anomalies
Algorithm 1 CAPA Algorithm (No Pruning)

Input:
A set of observations of the form, (x 1 , x 2 , . . . , xn) where x i ∈ R. Penalty constants β andβ for the introduction of a collective and a point anomaly respectively A minimum segment length l ≥ 2 Obtain robust estimates of the mean and variance 2:σ ← IQR(x 1 , x 2 , . . . , xn) 3: for i ∈ {1, ..., n} do 4: Centralise the data 5: end for 6: for m ∈ {1, ..., n} do We now turn to consider the problem of minimising the penalised cost we introduced in the previous section. Unlike in the classical changepoint problem considered by [10], the penalised cost given by equation (1) can not be minimised using a dynamic program, since the parameter θ 0 is shared across multiple segments and typically unknown. We therefore use robust statistics to obtain an estimateθ 0 for θ 0 . Such robust estimates can be obtained for a variety of models ([9] [13]). For example, the median, M -estimators, or the clipped mean can be used to robustly estimate the mean. The inter quantile range, the median absolute deviation, or the clipped standard deviation can be use to estimate the variance. Robust regression is available to estimate the parameters of AR models.
Having obtainedθ 0 , we then minimise as an approximation to (1). Since it can be expected that most data belongs to the typical distribution,θ 0 should be close to θ 0 . One might therefore expect that using this estimate will have little impact on the performance of the method, which we also show theoretically for joint changes in mean and variance in Section 4.2.
The approximation to the penalised cost can be minimised exactly by solving the dynamic programme where C(m) is the cost of the most efficient partition of the first m observations and C(0) = 0. For example, solving the dynamic programme approximately minimises the penalised cost for joint epidemic changes in mean and variance defined in equation (2). Similarly, we can minimise its point anomaly robust analogue by solving the dynamic programme where γ is a small constant ensuring that the argument of the logarithm will be larger than 0 (see Algorithm 1 for pseudocode). Adding the γσ 2 0 term is necessary when order statistics are used to obtainμ 0 . Assuming that the observations x t are independent and Normal, all sums m t=m−k+1 x t −x (m−k+1):m 2 will be non-zero with probability 1, meaning that in theory such a correction is not necessary for the other logarithmic term. In practice, observations are of finite precision and adding γσ 2 0 to the argument of the other logarithmic term, with γ set to the level of rounding should be considered.
Solving the full dynamic program is at least O(n 2 ). This lower bound can be achieved for the detection of joint changes in mean and variance. However, we can prune the solution space by borrowing ideas from [15], provided the loss function is such that adding a free changepoint will not increase the cost -a property which holds for many commonly used cost functions such as the negative log-likelihood. Indeed, the following proposition holds: holds for all a, b, and c such that a +l ≤ b < c −l. Then, if holds for some k < m −l, we can disregard k for all future steps m ≥ m +l of the dynamic programme.
Proof : Please see the Appendix. Note that the time after which an option can be discarded also depends on the minimum segment length, something not considered by [15].
This results enables us to reduce the computational cost. In practice, we found that it was close to O(n) for the detection of joint epidemic changes in mean and variance when the number of true epidemic changes increased linearly with the number of observations.

Theory for Joint Changes in Mean and Variance
We now introduce some theoretical results regarding the consistency of CAPA. All proofs for the results in this section can be found in the appendix. We establish that the consistency of CAPA can be viewed as a corollary of the consistency of a statistical procedure minimising a penalised cost function to detect classical changepoints. Consequently, we will begin by proving that method's consistency for the detection of changes in mean and variance in Section 4.1. To the best of our knowledge, no such result exists in the literature, which makes this proof of independent interest. We then proceed to proving the consistency of CAPA in Section 4.2.

Consistency of Classical Changepoint Detection
Consider the sequence x 1 , ..., x n ∈ R n which is normally distributed with K ∈ N changepoints. The sequence therefore satisfies Here 0 = t 0 ≤ ... ≤ t K+1 = n denote the start of the series, the K changepoints, and the end of the series. Changes in mean and variance can be of varying strength. To quantify this, we define the signal strength σ,k of the change in variance at the kth changepoint to be We note that 2 σ,k is equal to 0 if, and only if, σ k+1 = σ k . We also define the signal strength µ,k of change in mean at the kth changepoint to be Note that these two quantities can be combined into a global measure of signal strength 2 k = 2 σ,k + 1 2 2 µ,k for the kth change (see Lemma 7 in the Appendix for details).
We now define the penalised costC( for δ, β > 0. Here β log(n) 1+δ is a strengthened SIC-style penalty (Fryzlewicz [7]) for introducing an additional changepoint. We estimate changepoints with a cost of segment similar to the one we use to infer the location of epidemic changes in mean and variance. Since this leaves two parameters to fit, we impose a minimum segment length of two for all partitions. Assume that there exists someδ > 0 such that t k − t k−1 ≥ log(n) 1+δ+δ for all k, which ensures that the changepoints are sufficiently spaced apart to allow for their detection. Then, the following consistency result holds for the inferred number and location of changepointsK andt 1 , ...,tK inferred by minimisingC(x 1:n , τ, β): Theorem 1 Let x 1 , ..., x n follow the distribution specified above and the changes be such that k > for some > 0. Then ∀ > 0 there exist constants A(β, k , δ, ) decreasing in k , B(β, ,δ, δ, ) decreasing in , and C such that Proof : Please see the Appendix.

Consistency of CAPA
The results we obtained in the previous section can be extended to prove the consistency of CAPA for the detection of joint epidemic changes in mean and variance. As in the previous section, consider data x 1 , ..., x n which is of the form x t = µ(t) + σ(t)η t , where η t ∼ N (0, 1). Since we now assume epidemic changes, we have Here, µ 0 and σ 2 0 are the typical mean and variance respectively and K is the number of epidemic changepoints. The variables s k and e k denote the starting and end point of the kth anomalous window respectively. We impose log(n) 1+δ+δ ≤ e k − s k ≤ O( √ n) and s k+1 − e k > log(n) 1+δ+δ for someδ > 0. Treating the s k and e k like classical changepoints allows us to extend the definitions of σ , µ , and to the epidemic changepoint model. The following consistency result then holds for a partition (ŝ 1 ,ê 1 , ...,ŝK,êK) inferred by CAPA using a minimum segment length of two and β log(n) 1+δ for some δ > 0 as penalty for both point anomalies and epidemic changepoints.
Theorem 2 Let x 1 , ..., x n follow the distribution specified above and the changes be such that k > for some > 0. Then ∀ > 0 there exist constants A(β, k , δ, ) decreasing in k , B(β, ,δ, δ, ) decreasing in , and C such that Proof : Please see the Appendix.

Simulation Study
To assess the potential of CAPA, we compare its performance to that of other popular anomaly and changepoint methods on simulated data. In particular, we compare with PELT as implemented in [14], a commonly used changepoint detection method, luminol ( [19]), an algorithm developed by LinkedIn to detect segments of atypical behaviour, as well as BreakoutDetection ( [11]) which was introduced by Twitter to detect changes in mean in a way which is robust to point anomalies.
The simulation study was conducted over simulated time series each consisting of 5000 observations, for which the typical data follows a N (0, 1) distribution. Epidemic changepoints start at a rate of 0.0005 (corresponding to an average of about 2.5 epidemic changes in each series), with their length being i.i.d. P ois(30) distributed. In each anomalous segment the data is again normally distributed, with the means being i.i.d. N (0, a 2 ) distributed and standard deviations i.i.d. Γ(1/b, 1/b) distributed. We used 1. a = 1 and a = 10 for weak and strong changes in mean respectively 2. b = 1 and b = 10 for weak and strong changes in mean respectively We compared the performance of the four methods in the presence of both strong and weak changes in mean and/or variance. We also repeated the analysis with 10 i.i.d. N (0, 10 2 ) distributed point anomalies occurring at randomly sampled points in the typical data. The comparison of these methods is made using the three different approaches we detail below.

ROC
We obtained ROC curves for the four methods. For BreakoutDetection and PELT, we considered detected changes within 20 time points of true changes to be true positives and classified all other detected changes as false positives. For luminol and CAPA, we considered detected starting and end points of epidemic changes to be true positives if they were within 20 observations of a starting and end point respectively. The results regarding the precision of true positives in Section 5.2 suggest that the results in this section are robust with regard to the choice of error tolerance. We set the minimum segment length to ten for PELT, CAPA, and BreakoutDetection. To obtain the ROC curves we varied the penalty for epidemic segments in CAPA, the penalty in PELT, the threshold in luminol, and the beta parameter of BreakoutDetection.
The resulting ROC curves, as well as examples of realisations of the data for the scenario of weak and strong changes in mean can be found in Figures 2 and 3 respectively. The results for joint changes in mean and variance, as well as changes in variance can be found in the supplementary material. We see that CAPA generally outperforms PELT, even in the absence of point anomalies. This is due to it having more statistical power, by exploiting the epidemic nature of the change. This becomes particularly apparent when the changes are weak. CAPA also outperform BreakoutDetection and luminol for epidemic changes in mean, the scenario for which these methods were developed. Moreover, the performance of CAPA is barely affected by the presence of point anomalies, unlike that of the non-robust methods. This observation remained true when we repeated our analysis with N (0, 1000 2 ) distributed point anomalies. The ROC curves for these additional simulations can be found in the supplementary material.

Precision
We also investigated the precision of the true positives for the four methods. We compared the mean absolute distance between detected changes (i.e. true changes which had a detected changes within 20 observations) and       the nearest estimated change across all the 12 scenarios. We used the default penalties for all methods (i.e. the default threshold for luminol and the BIC for PELT and CAPA) except BreakoutDetection, where we found that the default penalty returned no true positives at all for many scenarios. We therefore used the results we obtained when deriving the ROC curves to set the beta parameter to an appropriate level for each case.
The results of this analysis can be found in Figure 4. We see that CAPA is generally the most precise one. Moreover, its precision is not too strongly affected by the presence of point anomalies, unlike that of PELT, whose performance is significantly deteriorated by anomalies, especially when the signal is weak. The reason for this is that PELT fits additional changes in the presence of anomalies, which results in shorter segments. This leads to less accurate parameter estimates, which results in poorer estimates for the location of the changepoint. CAPA does not face this problem since the parameter of the typical distribution is shared across all segments. This remains true when the point anomalies are are a lot stronger, as can be seen in the supplementary material.

Runtime
Finally, we investigated the relationship between the runtime of the 4 methods and the number of observations. Our comparison is based on data following a distribution identical to the one we used in Sections 5.1 and 5.2. Since this type of data favours PELT and CAPA, because the expected number of changes increases with the number of observations, we also compared the runtime of the four methods on stationary N (0, 1) data, which represents the worst case scenario for these methods. Figure 5 displays the average speed over 50 repetitions for the two cases. When comparing the slopes between 10000 and 50000 datapoints we note that it is very close to 2 for BreakoutDetection in both cases as well as CAPA and PELT for stationary data, suggesting quadratic scaling. In the presence of epidemic changes however, that slope is 1.26 for CAPA -1.14 even between 25000 and 50000 datapoints -thus suggesting near linear runtime. We now apply CAPA to the Kepler light curve data, with the aim of detecting exoplanets via the so called transit method ( [30]). As described in Section 1, this approach consists of repeatedly measuring a star's brightness for a certain period of time, thus obtaining a so called light curve. Periodically recurring dips in the measurements then point towards the transit of a planet causing a small eclipse. Since the signal of transiting planets is known to be weak, we amplify it by exploiting its periodic nature. If the period of an orbiting planet were known, the signal of its transit could be strengthened by considering all data points to have been gathered at their measurement time modulo that period. We would thus obtain an irregularly sampled time series which we can transform into a regularly sampled time series by binning the data into equally sized bins of length approximately equal to the measurement interval of the Kepler telescope and taking the average within each bin. We could then apply CAPA to this preprocessed data, which would exhibit a stronger signal for any planet with the associated period. Detecting the signal for such a planet involves detecting a collective anomaly with a reduced mean. However we need to do this whilst being robust to the point anomalies in the data, and the potentially other collective anomalies associated with planets with different periods. The results obtained by applying this method, using the default penalties of our software implementation of CAPA, to the light curve of Kepler 1132 using a period of 62.8, 62.9, and 63.0 days can be found in Figure 6. We note that using a period of 62.9 days results in a promising dip, which is not present when using 62.8 or 63 days as period.

Application to Kepler Light Curve Data
Given a light curve, the periods of exoplanets orbiting the corresponding star (if any are present) are obviously not known a priori. We can, however, apply the above approach for a range of periods, given the fact that the cost of running CAPA is comparable to that of binning the data. Since transits appear as periods of reduced mean, we record the strength of the strongest change in mean as defined by max k ( µ,k ) and estimated using the sample mean and variance in the collective anomalies, and the estimated means and variance of the typical distribution. We expect this quantity to be largest for the periods of exoplanets. We identified the strength of the strongest change in mean for all periods from 1 day to 200 days with increments of 0.01 days for the light curve of Kepler 1132. The result of this analysis can be found in Figure 7. Note that the largest change in mean is recorded at a period of 62.89 days. As with spectral methods, we also observe resonance of the main signal at integer fractions of that period. This result is consistent with the existing literature, which considers Kepler 1132 to be orbited approximately every 62.892 days by the exoplanet Kepler 1132-b whose radius is about 2.5 times that of the earth ( [20]).
We also applied CAPA to the light curves of other stars with confirmed exoplanets and were able to detect their transit signal at the right period. A more detailed exposition of these results can be found in the supplementary material.

Appendix: Proofs
This Appendix contains proofs for all the results in this papers. Proofs for Lemmata we use can be found in the supplementary material.

Proof of Proposition 1
Let m ≥ m +l. We have which shows that the cost of choosing k will always be larger than that of choosing m. We can thus disregard k.

Proof of Theorem 1
Before proving this theorem, we introduce some notation. We define the cost of a segment x i:j under the true partition {0, t 1 , ..., t K , n} and true parameters to be Note that this cost is additive, i.e. for a < b − 1 < b + 1 < c we have C(x a:c ) = C(x a:b ) + C(x (b+1):c ), whilst the fitted cost satisfies the inequalityC(x a:c ) ≥C(x a:b ) +C(x (b+1):c ). We also define the residual sum of squares Y i:j = j k=i (η k −η i:j ) 2 . Finally, we will work on the event sets E 1 , E 2 , E 3 , E 4 , E 5 , and E 6 which we define below using notation a := a(i, j) = j − i + 1 where c(a, n) < 1 satisfies a 2 · c(a, n) − 1 − log(c(a, n)) 2 = (2 + ) log(n).
Note that c(a, n) is guaranteed to exits by the intermediate value theorem. Indeed, the function f (x) = x − 1 − log(x) is continuous and satisfies f (1) = 0 and f (x) → ∞ as x → 0 + . The motivation for these events is as follows: E 1 bounds the error in the estimates of the mean, while E 2 , E 3 , and E 6 bound the error in the estimates of the variance. E 5 and E 4 are needed to prevent the existence of segments length two and three respectively in which the observations lie to close to each other, which would encourage the algorithm to erroneously fit them in a short segment of low variance. We write E = ∩E i . We are now in a position to prove the following lemmata: Lemma 1 (Yao 1988) P(E 1 ) > 1 −K 1 n − , for some constantK 1 .
Lemma 3 There exists a constantC 1 such that Y i:j − a − a log(Y i:j /a) ≤C 1 log(n) holds on E for all 1 ≤ i < j ≤ n.
Lemma 4 Let i, j be such that there exists some k such that t k−1 < i < j ≤ t k . The following holds given E : Lemma 5 Let i, j be such that ∃k such that t k−1 = i < j ≤ t k or t k−1 < i < j = t k + 1. The following then holds given E C (x i:j ) −C (x i:j ) ≤C 3 log(n) Lemma 6 Let a, b, c ∈ τ for some partition τ of x i,j such that ∃k such that t k−1 < a < b < c ≤ t k . Then, where τ −b = τ \ {b} holds on E for large enough n.
We now defineκ k = 2κ( k , 3β, δ, ), noting it decreases in k , and the set of partitions which are withinκ k log(n) 1+δ of the true partition. We will show that, for large enough n, the optimal partition lies in B given the event set E. Given the probability of E, this proves Theorem 1. Our approach will consist of showing that the cost of a partition τ / ∈ B is higher than that of the true partition with the true parameters (see Proposition 4). We will achieve this by adding free changes to τ thus splitting up the series into multiple sub-segments each containing a single true changepoint andκ k log(n) 1+δ points either side of it. This also defines a projection of τ onto the partitions of the sub-segments. We define the set of partitions for segments x i:j for which there exist a k such that: as an analogue of B for the whole of x.
If τ / ∈ B, there must be at least one sub-segment for which the projection of τ does not lie in B k . We will show in Proposition 3, that the cost of the true partition using the true parameters is at least O(log(n) 1+δ ) lower than that of the projection of τ on such a segment. We will also show in Proposition 2 that the projections of τ which are in B k have a cost which is at most O(log(n)) lower than that of the true partition with true parameters.
Proposition 2 Let i, j ∈ N , be such that there exists a k such that: t k−1 + 1 ≤ i < t k < j ≤ t k+1 , then there exists a constantC 4 such that given E, for all valid partitions τ of the form τ = {i − 1,t, j}, if n is large enough.
Proof of Proposition 2: The following cases are possible: Case 1:t = t k . Then: where the inequality follows from Lemma 4.
Case 2:t = t k + 1. Then: where the inequality follows from Lemmata 4 and 5. Case 3:t > t k + 1. Then: where the first inequality follows from the fact that introducing an unpenalised changepoint reduces cost and the second is a consequence of Lemma 4. Case 4:t = t k − 1. Symmetrical to case 2. Case 5:t < t k − 1. Symmetrical to case 3. This finishes our proof.
Proposition 3 There exists a constant n 4 (β, δ, ), such that ∀i, j for which ∃k such that holds for all τ / ∈ B k given E and n > n 4 (β, δ, ).
Case 1: |τ | = 2. We have τ = {i − 1, j}. Hence: where the second inequality follows from the definition of H and Lemma 7 and the third from Lemma 4. Case 2: |τ | = 3. We have τ = {i − 1, t k + L, j}, where |L| >κ k log(n) 1+δ . We assume L > 0, the other case being very similar. We have: where the inequalities follow from of the definition of H as well as Lemmata 7 and 4.
Proof of Proposition 4: First, consider the special case K = 0. For this case, τ / ∈ B implies thatK ≥ 1. We haveC (x 1:n , τ, β) ≥C(x 1:n , {0, n}, β) +K where the first inequality follows from Lemma 6 and the second from Lemma 4. Next assume K ≥ 1. Let τ / ∈ B. We now introduce free changepoints l 0 , l 1 , ..., l K to break up the series into multiple sub-series with one true changepoint each. We impose l 0 = 0, l K = n, |l k − t k | > 4κ k log(n) 1+δ for 0 < k ≤ K and |l k − t k+1 | > 4κ k log(n) 1+δ for 0 ≤ k < K. We also require that τ ∪ {l 0 , ..., l K } is a valid partition (i.e. one which has segments of length at least two) and that there exists ak such that τk := τ ∩ {lk −1 + 1, lk −1 + 2, ..., lk} / ∈ Bk. We are guaranteed to find such points l 0 , l 1 , ..., l K if n is such that which is satisfied if n >ñ 5 (β, δ, ,δ, ), whereñ 5 (β, δ, ,δ, ) decreases in δ. Indeed, we can choose points near the middle of the true segments which are not in τ , or by select points in τ if the former is impossible because there are too many point in τ near the middle of some segment. Since introducing free changes reduces the cost we then havẽ where the second inequality follows from Propositions 2 and 3. This finishes the proof. Proof of Theorem 1: B contains the true partition with fitted parameters which is cheaper than the true partition with true parameters. Proposition 4 shows that conditional on E the true partition with true parameters will be cheaper than all τ / ∈ B fo n >ñ 5 (β, δ, ,δ, ). The optimal partition must therefore be in B, given event set E. This proves Theorem 1, since Lemmata 1 and 2 imply that In order to prove this result, we will use the following notation in this section: We defineC E (x 1:n , τ E , β, µ, σ) to be the cost of an epidemic partition τ E = {ŝ 1 ,ê 1 , ...ŝK,êK} under a penalty β log(n) 1+δ and inferred parameters of the typical distribution µ, σ. We define C E (x 1:n , β, µ, σ), to be the cost under the true partition using the true parameters for the epidemic segments and µ, σ as estimates for the parameters of the typical distribution. We also define the set of epidemic partitions as an epidemic equivalent of B. Finally, we note that we can extend the definition of the event set E to epidemic changepoints by treating the s k and e k like classical changepoints.
We will begin by proving a simplified version of the theorem in which we run our epidemic changepoint detection algorithm without allowing for epidemic changes of length one in variance only and imposing that each segment of the data allocated to the typical distribution is of length at least two. The reason for this is that this allows us to define an equivalent non-epidemic partition, whose segments must be of length at least two, for each epidemic partition. We also begin by assuming that the parameter of the typical distribution is known.
This simplified version captures the main ideas of the full proof. We will proceed to showing that the result also holds when the typical mean and variance are unknown. This will be followed by a proof of the full result by means of introducing and proving the consistency of a modified version of the classical changepoint detection algorithm described in the previous section which also allows for segments of length one.
For now, we assume that all segments are of length at least two and that the true parameters µ 0 and σ 0 are known. This allows us to use the fact that the cost of the true epidemic partition using the true parameters is exactly the same as the cost of the corresponding true non-epidemic partition using the true parameters with twice the penalty. We can therefore prove the following proposition, as a corollary of Proposition 4.

Proof of Proposition 5:
We note that I{s k = e k−1 } log(n) 1+δ , because using fitted parameters instead of µ 0 and σ 0 for segments allocated to the typical distribution under τ E can only reduce the cost. Additionally, two epidemic changes correspond to three classical changepoints if their end and starting points coincide. Moreover, C E (x 1:n , β, µ 0 , σ 0 ) = C (x 1:n ) + Kβ log(n) 1+δ .
Therefore:C E (x 1:n , τ E , β, µ 0 , σ 0 ) − C E (x 1:n , β, µ 0 , σ 0 ) This leaves two possibilities. If τ E ∪ {0, n} / ∈ B then the above will exceed by proposition 4. Since τ E / ∈ B E , the only way we can have τ E ∪ {0, n} ∈ B is if there exists a k such that s k = e k−1 . In that case the difference will exceed by Proposition 2. This finishes the proof.
We can now use this proposition to prove Theorem 2 in the same way we used 4 to prove Theorem 1.
We now introduce the following lemma about the distribution of the median and inter-quantile range. It will allow us to prove Theorem 2 when the true parameters are unknown.
Lemma 8 There exists a constantsK 8 , D 1 , and D 2 such that for large enough n We can use this Lemma above to introduce a new event E 7 stating that the estimated parameters are close to the true parameters.
This event bounds the effect of using the estimated typical parameters instead of the true parameters for the cost of the true distribution with true non-typical parameters. Indeed, the following lemma holds: Lemma 9 There exists a constantC 7 such that given E and E 7 and n large enough we have: We can use this lemma to prove the following extension of Proposition 5 to the case when the typical parameters are inferred.
Proof of Proposition 6: We note that, as before, C E (x 1:n , β, µ, σ) = C (x 1:n ) + Kβ log(n) 1+δ , Therefore we now havẽ C E (x 1:n , τ E , β,μ,σ) − C E (x 1:n , β,μ,σ) by applying Lemma 9. The rest of the proof is identical to that of Proposition 5, with an added O(log(n)) term. In order to be able to extend Proposition 6 to the case in which we allow epidemic changes of length one in variance only, as well as segments of the typical distribution which are of length one, we will prove the consistency of the following adaptation of the algorithm detecting classical changepoints we introduced in the previous section. We now let the segment costs bẽ for k either k − 1,k, or k + 1, when i belongs to the kth segment. Given E 7 the range of allowedσ 2 andμ is therefore guaranteed to contain the estimated typical parametersσ 2 andμ when applied to x. The algorithm can obviously not be implemented in practice, as it requires knowledge of the true parameters. It is nevertheless a consistent method.
To prove this, we need to define a last event set E 8 which controls the newly introduced segments of length one: We can prove the following probability bounds Lemma 10 There exists a constantK 8 such that P( We can now prove the following proposition, adapted from Proposition 4 for this modified penalised cost approach: Proposition 7 There exists a constantñ 7 (β, δ, ,δ, ) such that given E ∩ E 8 , we havẽ for all τ / ∈ B if n ≥ñ 7 (β, δ, ,δ, ) Proof of Proposition 7: Identical to the proof of Proposition 4. We just need to replace Lemma 4 by

Lemma 11
There exists a constantC 2 such that if i, j are such that there exists some k such that t k−1 < i ≤ j ≤ t k , then given E ∩ E 7 and n large enough to also account for the newly added segments of length one. We can now prove that Proposition 8 There exists a constantñ 8 (β, δ, ,δ, ) decreasing in such that for all holds on E ∩ E 7 ∩ E 8 for n >ñ 8 (β, δ, ,δ, ).
holds even when we allow for epidemic changes of length one in variance only and do not impose that segments allocated to the typical distribution have to be of length at least two. Proof of Proposition 8: Identical to the proof of Proposition 6 using Proposition 7 instead of Proposition 4.
Proof of Lemma 2: We note that Y i:j ∼ χ 2 a−1 . [16] proved that Therefore: A Bonferroni correction therefore gives P(E 2 ∩ E 6 ) > 1 − 2n − . We can derive the following Chernoff bound for k ≥ 1 and 0 ≤c < 1: Thus if we let c(a, n) < 1 be such that a 2 · c(a, n) − 1 − log(c(a, n)) 2 = (2 + ) log(n), and write c := c(a, n) for simplicity, we have for a ≥ 2. A Bonferroni correction then gives P(E 3 ) > 1 − n − . Next we note that Consequently, we have that: A Bonferroni correction then gives P(E 5 ) > 1 − K/ √ πn − . Finally, we have: which means that holds with probability exceeding 1 − 3n − . Adding up the three inequalities then gives By a similar argument, must also hold with probability 1 − 3n − . A Bonferroni correction then gives P(E 4 ) ≥ 1 − 6Kn − . This finishes our proof.
Lemma 3 There exists a constantC 1 such that Y i:j − a − a log(Y i:j /a) ≤C 1 log(n) holds on E for all 1 ≤ i < j ≤ n.

Proof of Lemma 3:
Consider the function f (x) = x − a − a log(x/a). This function decreases monotonically on (0, a) and increases monotonically on (a, ∞). Since E 2 and E 3 bound Y i:j from above and below respectively we only have to show that Y i:j − a − a log(Y i:j /a) ≤C 1 log(n) holds for the bounds in order to prove the lemma.
This finishes the proof.
Lemma 4 Let i, j be such that there exists some k such that t k−1 < i < j ≤ t k . The following holds given E : Proof of Lemma 4: This lemma bounds the reduction in cost we can obtain by using a mean and variance fitted to a segment rather than the true mean and variance of the segment. The left bound follows from the fact C (x i:j ) fits the mean and variance to minimise the log likelihood on the segment x i:j . The right bound follows from Lemma 3 and E 1 . Indeed, which finishes the proof.
Lemma 5 Let i, j be such that ∃k such that t k−1 = i < j ≤ t k or t k−1 < i < j = t k + 1. The following then holds given E C (x i:j ) −C (x i:j ) ≤C 3 log(n) Proof of Lemma 5: This Lemma is very similar to Lemma 4, except that we slightly relax the constraint that all the data has to be located between two changepoints. This is needed because of the minimum segment length of two. We will prove this lemma for the case where t k−1 = i, the other case being very similar. We consider 3 cases: Case 1: j = t k−1 + 1. We have that: where the first inequality follows from E 1 and the second from E 5 . Case 2: j = t k−1 + 2. We have: where the inequality follows from E 1 and E 4 . Case 3: j > t k−1 + 2. We have: where the second inequality follows from case 1 and Lemma 4.

Lemma 6
Let a, b, c ∈ τ for some partition τ of x i,j such that ∃k such that t k−1 < a < b < c ≤ t k . Then, where τ −b = τ \ {b} holds on E for large enough n.
Proof of Lemma 6: This lemma applies Lemma 4 to show that removing false positives reduces the overall cost.C for large enough n.
Lemma 7 For all α > 0, there exists a constantκ( k , α, δ, ) decreasing in k such thatC ( Proof of Lemma 7 : This lemma shows that not having an estimated changepoint near a true changepoint leads to high costs. Let j − t k = t k + 1 − i = D. We have: Now E 2 implies that Moreover, where the second inequality follows from E 1 and the third from the AM-GM inequality. Combining the above two bounds shows that, We can now use this to prove the Lemma. We havẽ We note that E 1 and E 2 imply that 2D − Y i:j − 2Dη i:j ≥ 1 − 2 2(2 + )D log(n) − (4 + 2 ) log(n) − (8 + 2 ) log(n). Moreover, Noting that both terms in the product increase in D and k as well as in a and n if we set D = a log(n) 1+δ finishes our proof.
Lemma 8 There exists a constantsK 8 , D 1 , and D 2 such that for large enough n Proof of Lemma 8: Without loss of generality, we assume that µ 0 = 0 and σ 0 = 1. Sinceμ andσ only depend upon x (0.25n) ,x (0.5n) , and x (0.75n) it is sufficient to show that there exists a constant D 3 such that where q c is the cth quantile of the normal, holds for c = 0.25, 0.5, 0.75. In order to do so, we first define y (i) to be the ith largest observation belonging to the typical distribution. We note that y (cn−m) < x (cn) < y (cn+m) , where m = O(K √ n) is the number of points belonging to one of the anomalous windows. Since q (cn±m)/(n−m) − q c = O(Kn − 1 2 ), it is sufficient to show that there exists a constant D 4 such that P |y (a(n−m)) − q a | ≤ D 4 log(n) n ≥ 1 − n − for a = (cn ± m)/(n − m). We note that where Φ is the CDF of the normal distribution and U s,t the sth largest of t i.i.d. U (0, 1) random variables. The following concentration inequality ( [26]) applies to the uniform distribution where v 2 = (r/n) (1 − r/n) ≤ 1/4 by the AMGM inequality. This means that the event for the six values of a which are of interest to us holds with probability at least by a Bonferroni correction, which is 1 − O(n − ). We note that this event implies that Φ(y a(n−m) ) − a = O log(n) n holds for all six a of interest, which will be confined to the interval [0.1, 0.9] for large enough n. Hence we must also have for large enough n. This finishes our proof.
Lemma 11 There exists a constantC 2 such that if i, j are such that there exists some k such that t k−1 < i ≤ j ≤ t k , then given E ∩ E 7 and n large enough

Further Simulation Study Results
The ROC curves for weak and strong changes in variance as well as for weak and strong joint changes in mean and variance can be found in Figures 9, 10, 11, and 12. The ROC curves for all three types of collective anomalies in the presence of strong point anomalies can be found in Figures 13, 14, and 15. The precision of true positives when such point anomalies are present is compared in Figure 8. We note that CAPA is robust to such point anoamlies, unlike PELT and luminol.

Application of CAPA to Further Stars
We applied the approach detailed in Section 6 to the light curves of five further stars with known exoplanets ( [20]). Figure 16 depicts the largest detected change in mean as measured by max k ( µ,k ) per period for the five stars. We found that the 20 periods exhibiting the largest change in mean correspond to integer fractions of the orbital period of a known exoplanet in all cases. We thus observed no false positives. The results are summarised in Figure 17. We note that not all planets appear in the 20 periods with largest change in mean. This is due to the fact that their signal is weaker than the resonance of the signal of larger planets. CAPA can nevertheless detect the transit signal of the missing planet at their orbital period, with the exception of Kepler 454-c. This planet however was discovered by a different method than the transit method.               Figure 16: The strongest change in mean, as measured by max k ( µ,k ), detected by CAPA for the lightcurves of five stars with known exoplanets. All periods from 1 to 200 days at 0.01 day increment were examined