## Enhancing Changepoint Detection: Penalty Learning through Deep Learning Techniques

Tung L Nguyen 1* and Toby Dylan Hocking 2

1* School of Informatics, Computing, and Cyber Systems, Northern Arizona University, S San Francisco, Flagstaff, 86011, Arizona, USA. 2 D´ epartement d'informatique, Universit´ de Sherbrooke, Sherbrooke e QC J1K 2R1, Quebec, Canada.

*Corresponding author(s). E-mail(s): tln229@nau.edu; Contributing authors: toby.dylan.hocking@usherbrooke.ca;

## Abstract

Changepoint detection, a technique for identifying significant shifts within data sequences, is crucial in various fields such as finance, genomics, medicine, etc. Dynamic programming changepoint detection algorithms are employed to identify the locations of changepoints within a sequence, which rely on a penalty parameter to regulate the number of changepoints. To estimate this penalty parameter, previous work uses simple models such as linear or tree-based models. This study introduces a novel deep learning method for predicting penalty parameters, leading to demonstrably improved changepoint detection accuracy on large benchmark supervised labeled datasets compared to previous methods.

Keywords: changepoint detection, supervised learning, deep learning, penalty parameter

## 1 Introduction

Changepoint detection serves as a vital tool in numerous real-life applications by pinpointing significant transitions or sudden changes in data patterns, ranging from detecting market trends in finance [1], monitoring disease outbreaks in healthcare [2], enhancing network security [3], monitoring environmental changes [4] and more.

To determine the optimal partitioning of a sequence given a fixed number of segments, several efficient algorithms can be employed to achieve precise results [5-7].

However, in many instances, the number of segments is not predetermined and must instead be inferred from the data. To address this challenge, several dynamic programming algorithms have been successfully applied to changepoint detection, including Optimal Partitioning (OPART) [8] with its variations such as Functional Pruning Optimal Partitioning (FPOP) [9] or Pruned Exact Linear Time (PELT) [7]. Labeled Optimal Partitioning (LOPART) [10] extends OPART's capabilities by leveraging predefined changepoint labels, indicating the expected number of changepoints within specific location ranges. When no such labels are defined, LOPART behaves identically to OPART. A critical aspect of these algorithms (be it OPART or LOPART) is the penalty parameter which is defined as λ in the optimization problem below:

Find m ∈ R N that minimizes the following function for a given sequence d ∈ R N

̸

$$\sum _ { i = 1 } ^ { N } l ( m _ { i }, d _ { i } ) + \lambda \sum _ { i \in P } I [ m _ { i } \neq m _ { i + 1 } ]$$

̸

̸

Where P is the possible changepoint locations set (locations in this set vary depending on whether the algorithm used is OPART or LOPART). l ( m , d i i ) is typically the negative log likelihood of the parameter m i given the value d i ; smaller values indicate a better fit. I m [ i = m i +1 ] is the indicator function, equaling 1 if there's a changepoint (i.e., m i = m i +1 ) and 0 otherwise, λ ≥ 0 represents the penalty parameter.

̸

These algorithms produce a mean vector m . From vector m , position i ∈ { 1 2 , , . . . , N - } 1 is a changepoint in the sequence d if m i = m i +1 . Each sequence is associated with labels indicating the expected number of changepoints between two locations, and the optimal set of changepoints minimizes label errors (an error occurs when the detected number of changepoints does not match the expected number of changepoints in the label). Within the algorithm, the penalty parameter λ holds significant importance in partitioning, yet its value remains fixed. Moreover, a higher λ imposes a more substantial penalty for changepoints' presence, consequently yielding smaller sets of changepoints (see Figure 1). A too high value of λ is undesirable because it results in fewer detected changepoints, potentially missing significant ones. Conversely, a too low value of λ results in an excessive number of detected changepoints, more than necessary. While the existing changepoint detection algorithms has demonstrated effectiveness, the fixed nature of λ prompts inquiry into methods for dynamically adapting this critical parameter. This study focuses on predicting the value of this penalty parameter λ to enhance changepoint detection algorithms accuracy.

Previous methods, such as those employing Bayesian Information Criterion (BIC) [11], linear models [10, 12], ALPIN [13], Maximum Margin Interval Trees (MMIT) [14] and Accelerated Failure Time (AFT) models in XGBoost [15] have made good attempts to ascertain the optimal λ value. However, these methods rely on using linear or tree-based models as learning models may constrain the ability to capture complex patterns.

Given these considerations, this study pursues a unique objective: using deep learning with chosen useful features for penalty parameter prediction. By harnessing the capabilities of deep learning, we aim to uncover complex patterns and relationships

Fig. 1 Example of different penalty parameter values result in different sets of changepoints. In this example sequence, there are four labels: three positive labels (regions with only one changepoint each) and one negative label (a region with no changepoint). Different penalty parameter values are experimented with using the OPART algorithm to detect changepoints within this sequence. From the set of changepoints and the predefined labels, there are two types of errors: false positives (fp) - more than one changepoint is detected in a positive label or when at least one changepoint is detected in a negative label, and false negatives (fn) - no changepoint is detected in a positive label. The main question of the study is: To detect changepoint positions from a given the sequence, how can we predict the best penalty parameter value for the changepoint detection algorithms?

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00856v3-figure-7b4f7979-72b9-42ea-ac05-476c73c07669.jpg)

Fig. 2 Example of point regression versus interval regression. In the plot on the left, which shows point regression, the model line tries to pass close to all the target points. In the plot on the right, which illustrates censored interval regression, the model line aims to intersect all the intervals.

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00856v3-figure-518ce441-6881-4b94-a773-dd1caaf9475d.jpg)

within the data, providing a more comprehensive approach to penalty parameter prediction. Our study on three large benchmark supervised labeled datasets shows that the new method consistently outperforms previous ones, demonstrating superior accuracy.

## Paper structure

This study is structured into five main sections. Section 1 is the general introduction about the problem of penalty parameter prediction. In Section 2, problem setting and previous methods on penalty parameter prediction is reviewed. Section 3 elaborates on our proposed method, delving into innovative approaches that extend beyond previous methods' limitations. Section 4 shows the results obtained from applying our proposed method are presented and analyzed comprehensively. Section 5 comprises the discussion and conclusion of the study.

Fig. 3 The loss value of two loss functions is determined by comparing the prediction to the target. In the left plot, the squared error loss function yields a value of 0 when the prediction ˆ reaches the target y point y . The right plot illustrates the squared hinge error (this loss function is utilized to predict values falling within a target interval rather than a single target point), where the loss value reaches 0 when the prediction ˆ falls within the interval [ y y l + ϵ, y u -ϵ ] where margin ϵ = 1.

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00856v3-figure-f980bfbf-d46d-45b6-916c-1f611d5543a5.jpg)

## 2 Literature Review

## 2.1 Problem setting

Changepoint detection algorithms take into the sequence d along with the penalty parameter λ as input and then generate the set of detected changepoints. From each sequence d , M distinct labels { ( s , e , c i i i ) } M i =1 emerge within the sequence, where c i denotes the expected number of changepoints between points at locations s i and e i . Since ALPIN [13] requires a predefined expert sequence partition (alternatively, this corresponds to each label having a size of 1 having 1 changepoint, i.e., s i = e i and c i = 1, which represents a specific special case), it is not suitable for this problem setting. There are two types of label errors: in each label, if the number of detected changepoints greater than c i , it's a false positive; if smaller, it's a false negative.

Finding the optimal set of detected changepoints require considering a range of values for the penalty parameter λ (rather than just one specific value) that minimizes the total number of label errors. Consequently, the value of penalty parameter λ to be predicted should also fall within an optimal interval, see Figure 2. This type of problem, where the objective is to find values falling within an interval, is referred to as the interval regression . In the interval regression problem, there are four types of intervals: uncensored ( -∞ &lt; y l = y u &lt; ∞ ), interval-censored ( -∞ &lt; y l &lt; y u &lt; ∞ ), left-censored ( -∞ = y l &lt; y u &lt; ∞ ) and right-censored ( -∞ &lt; y l &lt; y u = ∞ ).

Accelerated failure time (AFT) models, a class of linear models for censored outcomes, have been extensively studied [16]. In recent years, L1-regularized variants have been developed to handle high-dimensional datasets [17, 18]. Nonlinear methods for censored data, such as decision trees [19], Random Forests [20], and Support Vector Machines [21], have also been explored, though these techniques are limited to right-censored and uncensored data. In 2022, a variation of the AFT model, implemented in XGBoost, can handle various forms of censoring by applying an exponential transformation to ensure non-negative target intervals before fitting the model [15]. AFT models typically assume the data follow a specific distribution, such as normal,

Weibull, exponential, etc, then use maximum likelihood estimation to learn the model parameters in parametric censored regression settings.

Another approach to the interval regression problem involves supervised machine learning, where the model is trained by minimizing a specific loss function. This includes methods such as the L1-regularized linear model [12] and the maximal margin interval tree (MMIT) [14].

While both model learning approaches (AFT models and supervised machine learning models) yield very similar results [15], minimizing a specific loss function offers a simpler, more intuitive approach. It does not require prior assumptions about the data distribution, which can be unclear to non-experts.

As a result, squared error or absolute error, which is commonly used as a loss function in point estimate regression, cannot be employed for this problem. This type of problem requires a different loss function. This loss function, known as hinge loss, was first defined by Rigaill et al. [12], with its variants later introduced by Drouin et al. [14]. The loss function resembles the squared error (or absolute error) loss function, except it achieves a loss value of 0 within a target interval, as depicted in Figure 3, unlike the squared error (or absolute error) loss function which only achieves 0 loss at a single target point.

Using the ReLU function, the loss value is expressed as follows:

$$l ( \hat { y }, y ) = l ( \hat { y }, [ y _ { l }, y _ { u } ] ) = \left ( \text{ReLU} ( y _ { l } - \hat { y } + \epsilon ) \right ) ^ { p } + \left ( \text{ReLU} ( \hat { y } - y _ { u } + \epsilon ) \right ) ^ { p } \quad \ \ ( 1 )$$

In this context, ϵ ≥ 0 represents the margin length (Rigaill et al. [12] selected a fixed ϵ = 1, while Drouin et al. [14] treated ϵ as a hyperparameter, determined via cross-validation). The parameter p , which can be either 1 or 2, defines the type of loss function (Rigaill et al. [12] chose p = 2, while Drouin et al. [14] considered both p = 1 and p = 2). The predicted value of the penalty parameter is denoted by ˆ, and y y = [ y , y l u ] represents the optimal interval, where y l ≤ y u define the lower and upper bounds, respectively.

In summary, for each labeled training sequence, a vector of sequence features is derived (e.g., length, mean, minimum value, maximum value, variance, value range, . . . ) and the optimal interval for the penalty parameter λ is determined using Algorithm 1 in [12]. During model training, this feature vector serves as input to predict the value of λ , aiming for it to fall within the optimal interval by minimizing the squared hinge loss function. The predicted value of λ is then used for partitioning new unlabeled sequences.

## Notation

Throughout the remainder of this paper, the input of all learning models is referred to as features (extracted from sequence data), while the output is the value of the penalty parameter λ to be predicted. So from now, the symbol λ refers to the penalty parameter used in the changepoint detection algorithms. The desired predicted value of λ falls within an optimal interval, referred to as the target interval . In this paper, labels do not represent the output of the model or the value to be predicted (although in machine learning, labels are sometimes used to denote the value to be predicted).

Fig. 4 Comparative Model Diagram - Previous Methods versus Our Proposal. From the raw sequence data, various sequence features are extracted such as length, mean, variance, standard deviation, minimum value, maximum value, quartiles, sum of absolute differences, . . . and various transformation functions are applied such as log, absolute, square root, square, or combinations of these. This process yields a large vector of sequence features. However, only the features without missing data or non-infinity values are utilized for learning the penalty parameter value. While previous methods rely on BIC, linear models, or decision trees for penalty parameter prediction, our proposed approach adopts MLPs for enhanced performance.

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00856v3-figure-d760a571-3c6f-4ef8-922b-da901bb129e8.jpg)

Instead, they denote regions within the sequence characterized by an expected number of changepoints.

## 2.2 Previous works

Following is a list of previous studies that have worked on predicting the value of λ , including the Bayes Information Criterion (BIC), linear and tree-based models. Define length as N i and variance as σ i for the i th sequence. To maintain consistency with the presentation of the λ prediction problem in [12] and [10], the following sections will present the prediction problem as predicting log λ instead of λ .

## BIC model

The Bayesian Information Criterion (BIC) proposed by Schwarz [11] predicts log λ i = log log N i for each i th sequence. Notably, this model is unsupervised, it does not involve learning any parameters.

## Linear model

This method constructs feature vectors x i from i th sequence. The prediction model log λ i = x T i w + b is trained using one gradient descent technique named Fast Iterative Shrinkage-Thresholding Algorithm (FISTA) algorithm by Chambolle and Dossal [22], which optimizes the parameters w and b through convex optimization with a squared hinge loss function. Hocking and Srivastava [10] utilizes a single feature x i = log log N i , while Rigaill et al. [12] employs a feature vector x i = [log log N , i log σ i ] T . Moreover, Rigaill et al. [12] employs various statistical features and transformations (square, square root, absolute, log, loglog, . . . ) in the vector of sequence features to create a

large feature vector x = [ x , x 1 2 , . . . ], followed by the application of L1 regularization to address any redundant features.

## Maximum Margin Interval Trees (MMIT)

This method, introduced by Drouin et al. [14], shares a similar concept with regression trees by Breiman et al. [23]. Instead of splitting based on minimizing squared error within regions like in [23], MMIT minimizes the hinge loss within each region (can be the squared hinge loss presented in Figure 3 or absolute hinge loss). The optimal tree architecture, determined by hyperparameters such as maximum depth, minimum sample split and loss margin, is selected through cross-validation on the train set.

## AFT Model in XGBoost

This model is a variation of the original AFT model [16], utilizing XGBoost to construct an ensemble of decision trees as the predictor. To adapt Accelerated Failure Time (AFT) models for gradient boosting frameworks like XGBoost, the model formulation is revised from the original AFT model as follows:

$$\log ( \lambda _ { i } ) = \mathcal { T } ( \mathbf x _ { i } ) + \epsilon _ { i }$$

Here, T ( x i ) represents the output from the decision tree ensemble based on input x i (replacing the linear predictor x ⊤ i β in the original AFT model). The term ϵ i is a random error following a specified distribution (e.g., normal, log-normal, Weibull).

To train this model, a distribution for the error term is selected, assuming that the model output is monotonically increasing with respect to the error. The likelihood is then constructed to accommodate various types of targets, and maximum likelihood estimation is used to train the model.

## 3 Novelty and contribution

Previous methods are constrained by a limitation: they rely on relatively simple models, such as linear models or tree-based models. These models may not fully capture the complexity inherent in the underlying data, potentially leading to suboptimal outcomes.

Our method employs Multi-Layer Perceptrons (MLPs) to predict the value of λ . Leveraging MLPs for λ prediction offers a distinct advantage, as they can extract pertinent hidden features from raw data, mitigating the need for manual feature engineering. Figure 4 provides a comparison summary between our proposed method and previous approaches. In MLPs, using an excessive number of features is not ideal, as the inclusion of noisy or irrelevant features can degrade performance To leverage MLPs effectively, we focus on selecting a subset of key features. In addition to the sequence length and variance utilized in previous methods, we incorporate two additional sequence features: the value range and the sum of absolute differences

- · Value range: The value range is defined as the difference between the maximum and minimum values in the sequence. Denoted as r i for i th sequence in Table 1.

Fig. 5 Graphs illustrating the relationship between four features and target intervals. Variance and length are selected because previous studies have incorporated them into the model. Upon examination, we observe that the range value and sum of absolute differences exhibit a discernible increasing monotonic linear relationship with the target interval, indicating their potential as good features.

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00856v3-figure-6fd2e3a9-56d4-40c0-a78a-fd1d75462cf7.jpg)

- · Sum of absolute differences: The sum of absolute differences is calculated as the sum of the absolute differences between two consecutive points in the sequence, denoted as ∑ N -1 i =1 | d i +1 -d i | , where d = [ d , d 1 2 , . . . , d N ] represents the sequence. Denoted as s i for i th sequence in Table 1.

These two features are chosen because intuitively, as the value range or the sum of absolute differences increases, the sequence tends to exhibit more fluctuations and vice versa, suggesting a need to adjust the value of λ accordingly.

Furthermore, upon visualizing the relationship between either of these features and the target intervals (representing the range of log λ to minimize training label errors), slightly increasing monotonic relationships are observed. This observation emerged after employing certain feature engineering techniques, see figure 5.

## 4 Experiments

In this section, we will delve into the detailed implementation of our proposed approach aimed at enhancing reproducibility. We begin by processing raw sequence data, with given labels for each sequence, and extracting a set of features along with the target interval using the algorithm outlined by Rigaill et al. [12]. Subsequently, we implement all baseline methods as well as our proposed method to generate predicted values for log λ (the summary of all employed models is provided in Table 1). Following this, we employ OPART with the predicted values of log λ to obtain the set of changepoints.

Table 1 List of employed models

| Model                                                     | Features                                                                                     | Model Type    | Regularization                                        | Citation       |
|-----------------------------------------------------------|----------------------------------------------------------------------------------------------|---------------|-------------------------------------------------------|----------------|
| BIC.1                                                     | log log N i                                                                                  | unsupervised  | None                                                  | [11]           |
| linear.1 linear.2 linear.4                                | log log N i log log N i , log σ i log log N i , log σ i , log r i , log log s i              | linear        | None                                                  | [10] [12] [24] |
| linear.all                                                | all features                                                                                 |               | L1                                                    | [12]           |
| mmit.1 mmit.2 mmit.4 mmit.all                             | N i N i , σ i N i , σ i , r i , s i all features                                             | tree          | max depth min split sample loss margin                | [14]           |
| aft xgboost.1 aft xgboost.2 aft xgboost.4 aft xgboost.all | N i N i , σ i N i , σ i , r i , s i all features                                             | ensemble tree | learning rate max depth                               | [15]           |
| mlp.1 mlp.2 mlp.4 mlp.all                                 | log log N i log log N i , log σ i log log N i , log σ i , log r i , log log s i all features | MLP           | hidden layers number neurons per layer early stopping | proposed       |

Notations: length N i - variance σ i - value range r i - sum of absolute difference s i

Finally, leveraging both the set of changepoints and the set of labels, we compute the accuracy rate.

## Raw sequence dataset

This study employs three large datasets: two DNA copy number profiles sourced from neuroblastoma tumors [12] (available at https://github.com/tdhock/neuroblastomadata), known for detailed (3730 sequences) and systematic (3418 sequences) data collection. And the last one is a large epigenomic dataset comprising 17 sub-datasets (4913 sequences total) [25] (accessible at https://archive.ics.uci.edu/ml/machinelearning-databases/00439/peak-detection-data.tar.xz).

## Evaluation Metrics

The primary evaluation metric utilized is the accuracy rate (percentage) of the test set, which depends on the total number of labels and the total number of label errors. These errors are calculated as the sum of false positives and false negatives across all labels j in the test sets. A false positive occurs when label j exhibits more predicted changepoints than expected for either a positive or negative label. A false negative occurs when the number of predicted changepoints is less than expected in positive labels.

Fig. 6 Mean test accuracy and ± 1 standard deviation across 6 folds for each method. To enhance clarity in the comparison visualization, method BIC and some small accuracies have been omitted (in the dataset detailed, methods mmit.1, mmit.2, and mmit.4 are excluded; in the dataset systematic, methods mmit.1 and mmit.2 are omitted; in the dataset epigenomic, method mmit.all is not included). Across all three datasets, mlp.4 exhibits superior accuracy compared to all baseline methods, boasting higher mean accuracy as well as improved accuracy variability.

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00856v3-figure-60ea4a59-906d-473e-8100-f8e6778418f3.jpg)

## Cross-validation setup

For each dataset, every sequence is assigned a unique identifier, referred to as sequenceID. The dataset is then divided into six folds based on sequenceID. During each iteration, one fold is designated as the test set, while the remaining five folds form the train set. Therefore this process is iterated six times, yielding six test accuracy rates. Figure 6 illustrates the mean accuracy rate across all six test folds, along with the corresponding plus-minus one standard deviation intervals.

## Training models

Below are presented the features, target interval, baseline models implementation, MLP configurations, as well as the loss function and optimizer.

## Features. Four sets of features are explored:

- · 1 feature: sequence length, same as [11] and [10]
- · 4 features: sequence length, variance, value range, sum of absolute difference (a subset of all features to utilize MLPs)
- · 2 features: sequence length and variance, same as [12]
- · all features: same as [12] and [14]. Features are selected from a large vector, as only those without missing data (values too small for the computer to store), infinity values are retained, or zero variance.

Each feature can be transformed using either the log( ) · or log log( ) · function (see Table 1) to ensure compatibility and enable straightforward comparisons with previous methods (BIC and linear models).

Target intervals. Every sequence within each dataset comes with its own set of labels, indicating the expected number of changepoints within specific regions. For each sequence, the target interval is the range of λ value that minimizes the number of label errors (for each sequence with its set of detected changepoints, the minimum number of label errors is 0, and the maximum number of label errors is equal to the number of labels assigned to the sequence).

Baseline Models Implementation. All baseline models (BIC, linear, MMIT and AFT model in XGBoost) with four different sets of features were employed.

For the linear models, we utilize the R package penaltyLearning [26]. In the case without regularization, we apply the Max Margin Interval Regression model using corresponding features. For L1 regularization, we use the same Max Margin Interval Regression model with L1 regularization. The L1 regularization parameter begins at 0.001 and is increased by a factor of 1.2 until no features remain. Cross-validation is employed to determine the optimal L1 regularization value. In addition to using the R package, we also implemented this model in Python. Instead of using FISTA, we employed the widely-used Adam optimizer for gradient descent and achieved same results to those obtained with the author's original code.

The MMIT method is implemented using the R package mmit [27]. We use crossvalidation with cv = 2 to select the best hyperparameters. The hyperparameters considered include a list for max depth values (0, 1, 5, 10, 20, Inf), a list for margin (or ϵ from equation 1) values (0, 1, 2), a list for loss type values (hinge, square equivalent to p = 1 or p = 2 in Equation 1) and a list for min sample values (0, 1, 2, 4, 8, 16, 20).

The AFT model is implemented using the Python package xgboost . We use cross-validation with cv=2 to select the best hyperparameters. The hyperparameters considered include a list of learning rate values (0.01, 0.1, 0.2) and a list of max depth values (6, 8, 10, 20). Training data is prepared by converting feature and target data, with the target values transformed using the exponential function to ensure non-negativity. The selected hyperparameters from cross-validation step are then used to train the final model on the entire training dataset, with a maximum of 10,000 boosting rounds and early stopping after 100 rounds without improvement. Predictions are made on the test dataset and transformed back to the original scale using a logarithm.

MLP Configurations. To implement each MLP model, a two-fold cross-validation was employed on the train set to determine the optimal number of hidden layers and the number of neurons per hidden layer. This selection was based on achieving the highest accuracy rate on the corresponding validation set. Different MLP configurations were validated, including models with 1 to 4 hidden layers and all hidden layer of one model can have sizes of 2, 4, 8, 16, 32, 64, 128, 256 or 512 neurons.

Table 2 Chosen MLP configuration count across 6 folds for each dataset

| layers   | neurons   | detailed   | detailed   | systematic   | systematic   | systematic   | systematic   |   epigenomic | epigenomic   | epigenomic   | total   |
|----------|-----------|------------|------------|--------------|--------------|--------------|--------------|--------------|--------------|--------------|---------|
| layers   | neurons   | 1 2        | 4 all      | 1            | 2            | 4            | all          |            1 | 2 4          | all          | total   |
| 1        | ≤ 64 > 64 | 1          | 1          | 1 2          | 1            | 2 1          | 1 1          |            2 |              | 2            | 11 4    |
| 2        | ≤ 64 > 64 | 1 2        | 4 1 2      |              |              | 1            | 2            |            2 | 1 5          | 4            | 22 3    |
| 3        | ≤ 64 > 64 | 5 2        |            | 1            | 1 2          | 1            |              |            4 | 3            |              | 17 2    |
| 4        | ≤ 64 > 64 | 1          | 1 2 1      | 2            | 1 1          | 1            | 1 1          |            1 |              |              | 9 4     |

For each MLP model from each dataset, 6 folds are tested, resulting in the selection of 6 MLP configurations. The dataset 'detailed' has 3,730 sequences, 'systematic' has 3,418, and 'epigenomic' has 4,913. Observing the trend in the table, it is evident that the preference leans towards MLPs with 2 or 3 hidden layers and not greater than 64 neurons. Specifically, out of the 72 chosen architectures, 15 have 1 hidden layer, 25 have 2 hidden layers, 19 have 3 hidden layers, and 13 have 4 hidden layers.

Fig. 7 MLP configurations' average validation accuracies, regardless of number of features. For datasets detailed and systematic, it's generally preferable to have fewer hidden layers, typically around 4 to 8 neurons per layer suffice. In dataset epigenomics, where accuracy remains relatively consistent across various numbers of hidden layers, optimal accuracy tends to be achieved with a neuron count ranging from 8 to 256.

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00856v3-figure-42fa49ea-98f1-4407-a6cb-4b6710d14281.jpg)

MLP Implementation. All MLP models were trained using PyTorch, with ReLU activation functions applied to all hidden layers to provide greater generalization compared to the linear model.

Number of iterations with Early Stopping. There is one early stopping technique, presented by Prechelt [28], controls the number of iterations. It uses the 'patience' parameter to decide when to stop learning. During neural network training, setting a large maximum number of iterations and specifying the value for patience parameter allows for monitoring the training process. If the loss value from the train set does not decrease after the specified number of patience iterations, the training process is halted. This technique helps prevent overfitting. In our study, we set the maximum number of iterations to 12000 and patience parameter value to 20 iterations.

Loss function and optimizer. The Adam optimizer is employed to minimize the squared hinge loss function with margin ϵ = 1 (linear models and MLPs).

## 5 Discussion and conclusion

## Discussion

Effect of Feature Selection. The experiments show that accuracy improves as the number of features increases (from 1 to 2 to 4, excluding the case of all features), regardless of whether linear, tree-based, or MLP models are used. Perhaps the reason lies in the better quality of the larger feature set. If we closely examine the feature sequence length in Figure 5, the relationship between sequence length and the target interval of λ is not entirely clear. This lack of clarity could explain why models relying solely on this feature exhibit lower accuracy compared to others. Remarkably, nonlinear models such as decision trees or MLPs exhibit lower accuracy when employing all features compared to when using only 4 features. So selecting only 4 features proves highly beneficial, enhancing model accuracy (both linear models and MLPs) while also potentially reducing training time for the models. This divergence can be attributed to the inherent challenge faced by MLPs in effectively eliminating unnecessary features.

Using MLPs effect. employing MLPs with appropriate configuration (see Figure 7 and Table 2) yields a enhancement in accuracy when contrasted with linear models and trees. In the case of the same feature set, it's not guaranteed that MLPs will consistently outperform linear models. For instance, in the dataset detailed, the linear model with two features perform better than the MLP. Similarly, in the dataset systematic, the linear model with one feature has the better performance than the MLP.

Comparison of MMIT, AFT in XGBoost vs Linear Model Accuracy. In many scenarios where the number of features remains constant, MMIT and AFT in XGBoost do not exhibit superior performance compared to linear models. This observation is consistent with results reported in [14] for the dataset Systematic, and [15] for the dataset Epigenomic, where the accuracy rates of AFT in XGBoost were similar to those of linear models and MMIT. This lack of improvement is often attributed to the presence of observable linear relationships between features and target intervals, as illustrated in Figure 5.

Comparison of MLP and Linear Model Accuracy. Examine Figure 6, for the linear model, performance generally improves as the number of features increases. However, this trend does not hold for MLP models; when there are too many features, their performance declines. Additionally, with just 1 or 2 features, MLP does not outperform the linear model-MLP only surpasses the linear model when 4 features are used.

## Conclusion

MLP models with chosen four features generally achieve higher accuracy in changepoint detection compared to linear models and decision trees. However, it's important

to note that the training process for MLPs is significantly more time-consuming than that for linear models.

## Limitations of this study

There are several considerable limitations from this study below

May not be applicable to other sequence datasets. Intuitively, features such as variance, value range, and sum of absolute difference play a role in predicting this penalty problem for these particular benchmark datasets. However, these features may not be relevant in other types of sequence datasets.

May overlook some other useful features. By focusing on a limited number of features and their relationship with target intervals, we may overlook additional useful features and potential interactions between features.

Challenges in Selecting the Optimal MLP Configuration. The process of identifying the most suitable MLP configuration is inherently time-consuming. It entails evaluating a plethora of configurations, each comprising different combinations of hidden layers and neurons. Our task entails validating 36 distinct MLP models for each pair of train and test sets (we considered variations in the number of hidden layers, ranging from 1 to 4, and the number of neurons per layer, which can be 2, 4, 8, 16, 32, 64, 128, 256, or 512). This exhaustive exploration represents a significant computational challenge. Furthermore, we did not delve into exploring architectures with varying neuron counts across layers within a single model.

## Future Work

Various neural network architectures can be explored. Beyond MLPs, one might investigate the performance of other architectures tailored to the specific characteristics of the data. In some cases, these alternative network structures may yield superior results compared to MLPs or linear models. About feature selection, instead of manual feature extraction, it could be worthwhile to explore Recurrent Neural Networks (RNNs) [29] for directly extracting features from raw sequences. Variants like Gated Recurrent Units (GRUs) [30] or Long Short-Term Memory networks (LSTMs) [31] could be examined for this task. Moreover, as feature transformations like logarithmic scaling were employed, it's worth exploring alternative approaches to feature engineering.

## Reproducible Research Material

For those interested in replicating our study, all the code and associated materials are available at this link:

github.com/lamtung16/ML ChangepointDetection. This commitment to reproducibility ensures transparency and allows others to validate and build upon our findings.

## Declarations

No funding was received for conducting this study.

## References

- [1] Lattanzi, C., Leonelli, M.: A change-point approach for the identification of financial extreme regimes. Brazilian Journal of Probability and Statistics 35 (4) (2021) https://doi.org/10.1214/21-bjps509
- [2] Muggeo, V.M.R., Adelfio, G.: Efficient change point detection for genomic sequences of continuous measurements. Bioinformatics 27 (2), 161-166 (2010) https://doi.org/10.1093/ bioinformatics/btq647 https://academic.oup.com/bioinformatics/articlepdf/27/2/161/48869568/bioinformatics 27 2 161.pdf
- [3] Tartakovsky, A.G., Polunchenko, A.S., Sokolov, G.: Efficient computer network anomaly detection by changepoint detection methods. IEEE Journal of Selected Topics in Signal Processing 7 (1), 4-11 (2013) https://doi.org/10.1109/JSTSP. 2012.2233713
- [4] Reeves, J., Chen, J., Wang, X.L., Lund, R., Lu, Q.Q.: A review and comparison of changepoint detection techniques for climate data. Journal of Applied Meteorology and Climatology 46 (6), 900-915 (2007) https://doi.org/10.1175/jam2493. 1
- [5] Auger, I.E., Lawrence, C.E.: Algorithms for the optimal identification of segment neighborhoods. Bulletin of mathematical biology 51 (1), 39-54 (1989)
- [6] Bai, J., Perron, P.: Computation and analysis of multiple structural change models. Journal of applied econometrics 18 (1), 1-22 (2003)
- [7] Killick, R., Fearnhead, P., Eckley, I.A.: Optimal detection of changepoints with a linear computational cost. Journal of the American Statistical Association 107 (500), 1590-1598 (2012)
- [8] Jackson, B., Scargle, J.D., Barnes, D., Arabhi, S., Alt, A., Gioumousis, P., Gwin, E., Sangtrakulcharoen, P., Tan, L., Tsai, T.T.: An algorithm for optimal partitioning of data on an interval. IEEE Signal Processing Letters 12 (2), 105-108 (2005)
- [9] Maidstone, R., Hocking, T., Rigaill, G., Fearnhead, P.: On optimal multiple changepoint algorithms for large data. Statistics and Computing 27 (2), 519-533 (2016) https://doi.org/10.1007/s11222-016-9636-3
- [10] Hocking, T.D., Srivastava, A.: Labeled optimal partitioning. Computational Statistics 38 (1), 461-480 (2023) https://doi.org/10.1007/s00180-022-01238-z

| [11]   | Schwarz, G.: Estimating the Dimension of a Model. The Annals of Statistics 6 (2), 461-464 (1978) https://doi.org/10.1214/aos/1176344136                                                                                                             |
|--------|-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------|
| [12]   | Rigaill, G., Hocking, T.D., Bach, F., Vert, J.-P.: Learning Sparse Penalties for Change-Point Detection using Max Margin Interval Regression (2013). https:// inria.hal.science/hal-00824075 Accessed 2024-01-10                                    |
| [13]   | Truong, C., Gudre, L., Vayatis, N.: Penalty learning for changepoint detection. In: 2017 25th European Signal Processing Conference (EUSIPCO), pp. 1569-1573 (2017). https://doi.org/10.23919/EUSIPCO.2017.8081473                                  |
| [14]   | Drouin, A., Hocking, T.D., Laviolette, F.: Maximum margin interval trees. In: Proceedings of the 31st International Conference on Neural Information Process- ing Systems. NIPS'17, pp. 4954-4963. Curran Associates Inc., Red Hook, NY, USA (2017) |
| [15]   | Barnwal, A., Cho, H., Hocking, T.: Survival regression with accelerated failure time model in xgboost. Journal of Computational and Graphical Statistics 31 (4), 1292-1302 (2022)                                                                   |
| [16]   | Wei, L.-J.: The accelerated failure time model: a useful alternative to the cox regression model in survival analysis. Statistics in medicine 11 (14-15), 1871-1879 (1992)                                                                          |
| [17]   | Cai, T., Huang, J., Tian, L.: Regularized estimation for the accelerated failure time model. Biometrics 65 (2), 394-404 (2009)                                                                                                                      |
| [18]   | Huang, J., Ma, S., Xie, H.: Regularized estimation in the accelerated failure time model with high-dimensional covariates. Biometrics 62 (3), 813-820 (2006)                                                                                        |
| [19]   | Quinlan, J.R.: Induction of decision trees. Machine learning 1 , 81-106 (1986)                                                                                                                                                                      |
| [20]   | Breiman, L.: Random forest. Machine Learning 45 (1), 5-32 (2001) https://doi. org/10.1023/a:1010933404324                                                                                                                                           |
| [21]   | P¨lsterl, o S., Navab, N., Katouzian, A.: An efficient training algorithm for kernel survival support vector machines. arXiv preprint arXiv:1611.07054 (2016)                                                                                       |
| [22]   | Chambolle, A., Dossal, C.H.: On the convergence of the iterates of' fista'. Journal of Optimization Theory and Applications 166 (3), 25 (2015)                                                                                                      |
| [23]   | Breiman, L., Friedman, J.H., Olshen, R.A., Stone, C.: Classification and regres- sion trees (cart). Biometrics 40 (3), 358 (1984)                                                                                                                   |
| [24]   | Lavielle, M.: Using penalized contrasts for the change-point problem. Signal Processing 85 (8), 1501-1510 (2005) https://doi.org/10.1016/j.sigpro.2005.01.012                                                                                       |
| [25]   | Hocking, T.D., Goerner-Potvin, P., Morin, A., Shao, X., Pastinen, T., Bourque,                                                                                                                                                                      |

- G.: Optimizing ChIP-seq peak detectors using visual labels and supervised machine learning. Bioinformatics 33 (4), 491-499 (2016) https://doi.org/10. 1093/bioinformatics/btw672 https://academic.oup.com/bioinformatics/articlepdf/33/4/491/49037984/bioinformatics 33 4 491.pdf
- [26] Hocking, T.D.: penaltyLearning: Penalty Learning. (2024). R package version 2024.1.25. https://github.com/tdhock/penaltylearning
- [27] Drouin: Maximum Margin Interval Trees. (2017). https://github.com/aldro61/ mmit
- [28] Prechelt, L.: Early Stopping - But When?, pp. 53-67. Springer, ??? (2012). https://doi.org/10.1007/978-3-642-35289-8 5 . http://dx.doi.org/10. 1007/978-3-642-35289-8 5
- [29] Hopfield, J.J.: Neural networks and physical systems with emergent collective computational abilities. Proceedings of the National Academy of Sciences 79 (8), 2554-2558 (1982) https://doi.org/10.1073/pnas.79.8.2554 https://www.pnas.org/doi/pdf/10.1073/pnas.79.8.2554
- [30] Cho, K., Merri¨nboer, B., Gulcehre, C., Bahdanau, D., Bougares, F., Schwenk, e H., Bengio, Y.: Learning phrase representations using RNN encoder-decoder for statistical machine translation. In: Moschitti, A., Pang, B., Daelemans, W. (eds.) Proceedings of the 2014 Conference on Empirical Methods in Natural Language Processing (EMNLP), pp. 1724-1734. Association for Computational Linguistics, Doha, Qatar (2014). https://doi.org/10.3115/v1/D14-1179 . https: //aclanthology.org/D14-1179
- [31] Hochreiter, S., Schmidhuber, J.: Long short-term memory. Neural Comput. 9 (8), 1735-1780 (1997) https://doi.org/10.1162/neco.1997.9.8.1735
Tung L Nguyen Toby Dylan Hocking
Enhancing Changepoint Detection: Penalty Learning through Deep Learning Techniques
Changepoint detection, a technique for identifying significant shifts within
data sequences, is crucial in various fields such as finance, genomics,
medicine, etc. Dynamic programming changepoint detection algorithms are
employed to identify the locations of changepoints within a sequence, which
rely on a penalty parameter to regulate the number of changepoints. To estimate
this penalty parameter, previous work uses simple models such as linear or
tree-based models. This study introduces a novel deep learning method for
predicting penalty parameters, leading to demonstrably improved changepoint
detection accuracy on large benchmark supervised labeled datasets compared to
previous methods.