# Change-Point Detection in Autoregressive Processes via the Cross-Entropy Method
## 3 The Cross-Entropy Algorithm  
In order to identify the locations of change-points in the problem--Equations (8) and (9), which can be considered a combinatorial optimization problem--we use the cross-entropy (CE) algorithm. The CE method was originally developed to estimate the rare-event probabilities as an adaptive importance sampling method, based on the Kullback-Leibler divergence (or cross-entropy) minimization [43]. The main idea of the CE method can be described by a two-step iterative procedure:  
1. Generate a sample from a probability distribution. 2. In order to obtain a better sample, find the minimum cross-entropy distance between the sample distribution and a target distribution. [PERSON] [44; 45] then realized that the CE method can be used to solve combinatorial optimization problems. We recommend [46] for getting familiar with the principals and the applications of the CE method. Firstly, we formulate the rare-event probability estimation problem:  
\[I(\alpha)=\mathbf{P}_{v}(F(C)\leq\alpha)=\mathbf{E}_{v}[I_{\{F(C)\leq a\}}]= \sum_{c}I_{\{F(c)\leq a\}}f(c,v),\]  
where \(F(C)\) is the objective (or score) function defined on a finite set \(\mathcal{C}\), \(\alpha\) is a threshold, \(\mathbf{P}_{v}(F(C)\leq\alpha)\) is the corresponding probability measure when \(C\) follows the probability density function (pdf) \(f(\cdot,v)\) with a real parameter \(v\), and \(I\) is an indicator function. The main idea of the CE method is to obtain the optimal pdf from a set of pdfs \(\{f(\cdot,v)\}\) through minimizing Kullback-Leibler (or relative entropy) distance. \[v^{*} = \underset{v}{\operatorname{argmin}}\,D\{z^{*}(c),\,f(c,v)\} \tag{10}\] \[= \underset{v}{\operatorname{argmax}}\,\mathbf{E}_{u}[I_{\{F(C) \leq a\}}]\ln f(C,v)\]  
It allows us to generate a sequence \(\{f(\cdot,v)\}\) by multi-level CE implementation to get the final optimal pdf \(f(\cdot,v^{*})\). During adaptive updating procedure, a family of \(\{(\alpha_{k},v_{k})\}\) is generated and eventually converges to the optimal state \((\alpha^{*},v^{*})\). As the \(F(C)\) defined as (8) or (9), our goal is to find the minimum value of \(F(c)\), denoted by \(\alpha^{*}\),  
\[\alpha^{*}=\min_{c\in\mathcal{C}}F(c)\]  
Then, the two-step iterative procedure mentioned above can be written in the following way:  
1. Updating of the level parameter \(\alpha_{k}\). Order the performance score increasingly, \(F(C^{(1)})\leq\cdots\leq F(C^{(M)})\), \(C^{(1)},\ldots,C^{(M)}\overset{iid}{\sim}f(C,v_{k-1})\). Let \(\widehat{\alpha}_{k}\) be the \(\beta\)-quantile of the ordered performance scores, which can be denoted as, \[\widehat{\alpha}_{k}=\widehat{F}_{(\lceil\beta M\rceil)}.\]
2. Updating the reference parameter \(v_{k}\). Given \(\alpha_{k}\) and \(v_{k-1}\), we can derive \(v_{k}\) from Equation (10), \[\widehat{v}_{k}=\underset{v_{k}}{\operatorname{argmax}}\,\mathbf{E}_{v_{k-1}} [I_{\{F(C)\leq\widehat{\alpha}_{k}\}}]\ln f(C,v_{k}).\] More formally, the generic CE optimization algorithm can be described as follows (Algorithm 1). ```
1: Specify the initial parameter \(\vartheta_{0}\) of \(f(\cdot,v)\). Let \(k=1\). 2: Generate a random sample \(C^{(1)},\ldots,C^{(M)}\) from \(f(\cdot,\vartheta_{k-1})\). Evaluate and order the performance score, \(F_{(1)}\leq\cdots\leq F_{(M)}\), level parameter is estimated as \(\widehat{\alpha}_{k}=\widehat{F}_{(|\beta M|)}\). 3: Update the current parameter \(v_{k}\) by solving the stochastic problem: \[\widehat{v}_{k}=\operatorname*{argmax}_{v_{k}}\frac{1}{M}\sum_{i=1}^{M}I_{\{F(C ^{(i)})\leq\widehat{\alpha}_{k}\}}\ln f(C^{(i)},v_{k})\]
4: Stop the process if a certain stopping criterion is met; otherwise allow \(k=k+1\) and return to step 2. ```  
**Algorithm 1** Basic CE optimization algorithm. The detailed information about the properties of the CE algorithm as well as its diverse applications can be found in [43] and [44]. To date, the CE method has been modified and applied to different multiple change-point problems as a combinatorial optimization algorithm in [8; 30; 31; 32; 33; 34; 35].