Multiple change-points detection by empirical Bayesian information criteria and Gibbs sampling induced stochastic search

Uncovering hidden change-points in an observed signal sequence is challenging both mathematically and computationally. We tackle this by developing an innovative methodology based on Markov chain Monte Carlo and statistical information theory. It consists of an empirical Bayesian information criterion (emBIC) to assess the fitness and virtue of candidate configurations of change-points, and a stochastic search algorithm induced from Gibbs sampling to find the optimal change-points configuration. Our emBIC is derived by treating the unknown change-point locations as latent data rather than parameters as is in traditional BIC, resulting in significant improvement over the latter which is known to mostly over-detect change-points. The use of the Gibbs sampler induced search enables one to quickly find the optimal change-points configuration with high probability and without going through computationally infeasible enumeration. We also integrate the Gibbs sampler induced search with a current BIC-based change-points sequential testing method, significantly improving the method’s performance and computing feasibility. We further develop two comprehensive 3-step computing procedures to implement the proposed methodology for practical use. Finally, simulation studies and real examples analyzing business and genetic data are presented to illustrate and assess the procedures.     

突发交通事件非参数诊断的变点统计方法研究

针对智能运输系统(ITS)项目特别是先进的出行信息系统的开发，建立了突发交通事件非线性非参数诊断的变点统计方法。依据交通流理论，结合均值变点模型，对变点搜索的最小二乘法和局部比较法进行了研究。利用在英国南安普敦市检获的实际数据对上述两种算法进行了标定，并对模型进行实际应用。结果显示上述方法对突发事件检测具有很高的灵敏度和有效性。     

Exploring the latent segmentation space for the assessment of multiple change-point models

This paper addresses the retrospective or off-line multiple change-point detection problem. Multiple change-point models are here viewed as latent structure models and the focus is on inference concerning the latent segmentation space. Methods for exploring the space of possible segmentations of a sequence for a fixed number of change points may be divided into two categories: (i) enumeration of segmentations, (ii) summary of the possible segmentations in change-point or segment profiles. Concerning the first category, a dynamic programming algorithm for computing the top $N$ most probable segmentations is derived. Concerning the second category, a forward-backward dynamic programming algorithm and a smoothing-type forward-backward algorithm for computing two types of change-point and segment profiles are derived. The proposed methods are mainly useful for exploring the segmentation space for successive numbers of change points and provide a set of assessment tools for multiple change-point models that can be applied both in a non-Bayesian and a Bayesian framework. We show using examples that the proposed methods may help to compare alternative multiple change-point models (e.g. Gaussian model with piecewise constant variances or global variance), predict supplementary change points, highlight overestimation of the number of change points and summarize the uncertainty concerning the position of change points.     

Detecting abrupt changes in a piecewise locally stationary time series

Non-stationary time series arise in many settings, such as seismology, speech-processing, and finance. In many of these settings we are interested in points where a model of local stationarity is violated. We consider the problem of how to detect these change-points, which we identify by finding sharp changes in the time-varying power spectrum. Several different methods are considered, and we find that the symmetrized Kullback-Leibler information discrimination performs best in simulation studies. We derive asymptotic normality of our test statistic, and consistency of estimated change-point locations. We then demonstrate the technique on the problem of detecting arrival phases in earthquakes.     

Bayesian multiple change-point estimation with annealing stochastic approximation Monte Carlo

Bayesian multiple change-point models are built with data from normal, exponential, binomial and Poisson distributions with a truncated Poisson prior for the number of change-points and conjugate prior for the distributional parameters. We applied Annealing Stochastic Approximation Monte Carlo (ASAMC) for posterior probability calculations for the possible set of change-points. The proposed methods are studied in simulation and applied to temperature and the number of respiratory deaths in Seoul, South Korea.     

Detection of multiple change-points in multivariate time series

We consider the multiple change-point problem for multivariate time series, including strongly dependent processes, with an unknown number of change-points. We assume that the covariance structure of the series changes abruptly at some unknown common change-point times. The proposed adaptive method is able to detect changes in multivariate i.i.d., weakly and strongly dependent series. This adaptive method outperforms the Schwarz criteria, mainly for the case of weakly dependent data. We consider applications to multivariate series of daily stock indices returns and series generated by an artificial financial market. __________ Translated from Lietuvos Matematikos Rinkinys, Vol. 46, No. 3, pp. 351–376, July–September, 2006.     

Robust algorithms for multiphase regression models

This paper proposes a robust procedure for solving multiphase regression problems that is efficient enough to deal with data contaminated by atypical observations due to measurement errors or those drawn from heavy-tailed distributions. Incorporating the expectation and maximization algorithm with the M-estimation technique, we simultaneously derive robust estimates of the change-points and regression parameters, yet as the proposed method is still not resistant to high leverage outliers we further suggest a modified version by first moderately trimming those outliers and then implementing the new procedure for the trimmed data. This study sets up two robust algorithms using the Huber loss function and Tukey's biweight function to respectively replace the least squares criterion in the normality-based expectation and maximization algorithm, illustrating the effectiveness and superiority of the proposed algorithms through extensive simulations and sensitivity analyses. Experimental results show the ability of the proposed method to withstand outliers and heavy-tailed distributions. Moreover, as resistance to high leverage outliers is particularly important due to their devastating effect on fitting a regression model to data, various real-world applications show the practicability of this approach.     

A novel clustering approach and prediction of optimal number of clusters: global optimum search with enhanced positioning

Cluster analysis of genome-wide expression data from DNA microarray hybridization studies is a useful tool for identifying biologically relevant gene groupings (DeRisi et al. 1997; Weiler et al. 1997). It is hence important to apply a rigorous yet intuitive clustering algorithm to uncover these genomic relationships. In this study, we describe a novel clustering algorithm framework based on a variant of the Generalized Benders Decomposition, denoted as the Global Optimum Search (Floudas et al. 1989; Floudas 1995), which includes a procedure to determine the optimal number of clusters to be used. The approach involves a pre-clustering of data points to define an initial number of clusters and the iterative solution of a Linear Programming problem (the primal problem) and a Mixed-Integer Linear Programming problem (the master problem), that are derived from a Mixed Integer Nonlinear Programming problem formulation. Badly placed data points are removed to form new clusters, thus ensuring tight groupings amongst the data points and incrementing the number of clusters until the optimum number is reached. We apply the proposed clustering algorithm to experimental DNA microarray data centered on the Ras signaling pathway in the yeast Saccharomyces cerevisiae and compare the results to that obtained with some commonly used clustering algorithms. Our algorithm compares favorably against these algorithms in the aspects of intra-cluster similarity and inter-cluster dissimilarity, often considered two key tenets of clustering. Furthermore, our algorithm can predict the optimal number of clusters, and the biological coherence of the predicted clusters is analyzed through gene ontology.     

Multi-objective Meta-heuristics for the Traveling Salesman Problem with Profits

We introduce and test a new approach for the bi-objective routing problem known as the traveling salesman problem with profits. This problem deals with the optimization of two conflicting objectives: the minimization of the tour length and the maximization of the collected profits. This problem has been studied in the form of a single objective problem, where either the two objectives have been combined or one of the objectives has been treated as a constraint. The purpose of our study is to find solutions to this problem using the notion of Pareto optimality, i.e. by searching for efficient solutions and constructing an efficient frontier. We have developed an ejection chain local search and combined it with a multi-objective evolutionary algorithm which is used to generate diversified starting solutions in the objective space. We apply our hybrid meta-heuristic to synthetic data sets and demonstrate its effectiveness by comparing our results with a procedure that employs one of the best single-objective approaches.      

An Efficient Algorithm for Bayesian Nearest Neighbours

K-Nearest Neighbours (k-NN) is a popular classification and regression algorithm, yet one of its main limitations is the difficulty in choosing the number of neighbours. We present a Bayesian algorithm to compute the posterior probability distribution for k given a target point within a data-set, efficiently and without the use of Markov Chain Monte Carlo (MCMC) methods or simulation—alongside an exact solution for distributions within the exponential family. The central idea is that data points around our target are generated by the same probability distribution, extending outwards over the appropriate, though unknown, number of neighbours. Once the data is projected onto a distance metric of choice, we can transform the choice of k into a change-point detection problem, for which there is an efficient solution: we recursively compute the probability of the last change-point as we move towards our target, and thus de facto compute the posterior probability distribution over k. Applying this approach to both a classification and a regression UCI data-sets, we compare favourably and, most importantly, by removing the need for simulation, we are able to compute the posterior probability of k exactly and rapidly. As an example, the computational time for the Ripley data-set is a few milliseconds compared to a few hours when using a MCMC approach.

     

A genetic algorithm for the preemptive and non-preemptive multi-mode resource-constrained project scheduling problem

In this paper we present a genetic algorithm for the multi-mode resource-constrained project scheduling problem (MRCPSP), in which multiple execution modes are available for each of the activities of the project. We also introduce the preemptive extension of the problem which allows activity splitting (P-MRCPSP). To solve the problem, we apply a bi-population genetic algorithm, which makes use of two separate populations and extend the serial schedule generation scheme by introducing a mode improvement procedure. We evaluate the impact of preemption on the quality of the schedule and present detailed comparative computational results for the MRCPSP, which reveal that our procedure is amongst the most competitive algorithms.     

Designing WDM Optical Networks Using Branch-and-Price

In this paper, we present an exact solution procedure for the design of two-layer wavelength division multiplexing (WDM) optical networks with wavelength changers and bifurcated flows. This design problem closely resembles the traditional multicommodity flow problem, except that in the case of WDM optical networks, we are concerned with the routing of multiple commodities in two network layers. Consequently, the corresponding optimization models have to deal with two types of multicommodity variables defined for each of the network layers. The proposed procedure represents one of the first branch-and-price algorithms for a general WDM optical network setting with no assumptions on the number of logical links that can be established between nodes in the network. We apply our procedure in a computational study with four different network configurations. Our results show that for the three tested network configurations our branch-and-price algorithm provides solutions that are on average less than 5 % from optimality. We also provide a comparison of our branch-and-price algorithm with two simple variants of the upper bounding heuristic procedure HLDA that is commonly used for WDM optical network design.     

AAR-based decomposition algorithm for non-linear convex optimisation

We introduce a new method for a task of maximal material utilization, which is to fit a flexible, scalable three-dimensional body into another aiming for maximal volume whereas position and shape may vary. The difficulty arises from the containment constraint which is not easy to handle numerically. We use a collision detection method to check the constraint and reformulate the problem such that the constraint is hidden within the objective function. We apply methods from parametric optimization to proof that the objective function remains at least continuous. We apply the new approach to the problem of fitting a gemstone into a roughstone. For this previous approaches based on semi-infinite optimization exist, to which we compare our algorithm. The new algorithm is more suitable for necessary global optimization techniques and numerical results show that it works reliably and in general outperforms the previous approaches in both runtime and solution quality.     

基于黄金分割法的离散回归方程的变点估计及其应用

本文利用变点统计学和黄金分割法讨论有多个变点的离散回归方程的交点估计和参数估计，文中提出基于黄金分割法搜索最佳变点估计和同时得到参数估计的最小二乘算法，还讨论该算法在控制领域的应用，数值模拟结果显示本文算法能给出良好的变点及参数的估计值。     

A multi-item mixture inventory model involving random lead time and demand with budget constraint and surprise function

This study deals with a multi-item mixture inventory model in which both demand and lead time are random. A budget constraint is also added to this model. The optimization problem with budget constraint is then transformed into a multi-objective optimization problem with the help of fuzzy chance-constrained programming technique and surprise function. In our studies, we relax the assumption about the demand, lead time and demand during lead time that follows a known distribution and then apply the minimax distribution free procedure to solve the problem. We develop an algorithm procedure to find the optimal order quantity and optimal value of the safety factor. Finally, the model is illustrated by a numerical example.     

Efficient algorithms for machine scheduling problems with earliness and tardiness penalties

In this paper, we study the multi-machine scheduling problem with earliness and tardiness penalties and sequence dependent setup times. This problem can be decomposed into two subproblems—sequencing and timetabling. Sequencing focuses on assigning each job to a fixed machine and determine the job sequence on each machine. We call such assignment a semi-schedule. Timetabling focuses on finding an executable schedule from the semi-schedule via idle-time insertion. Sequencing is strongly NP-hard in general. Although timetabling is polynomial-time solvable, it can become a computational bottleneck if the procedure is executed many times within a larger framework. This paper makes two contributions. We first propose a quantum improvement to the computational efficiency of the timetabling algorithm. We then apply it within a squeaky wheel optimization framework to solve the sequencing and overall problem. Finally, we demonstrate the strength of our proposed algorithms by experiments.     

A Projected Subgradient Algorithm for Bilevel Equilibrium Problems and Applications

In this paper, we propose a new algorithm for solving a bilevel equilibrium problem in a real Hilbert space. In contrast to most other projection-type algorithms, which require to solve subproblems at each iteration, the subgradient method proposed in this paper requires only to calculate, at each iteration, two subgradients of convex functions and one projection onto a convex set. Hence, our algorithm has a low computational cost. We prove a strong convergence theorem for the proposed algorithm and apply it for solving the equilibrium problem over the fixed point set of a nonexpansive mapping. Some numerical experiments and comparisons are given to illustrate our results. Also, an application to Nash–Cournot equilibrium models of a semioligopolistic market is presented.     

Semideterministic Global Optimization Method: Application to a Control Problem of the Burgers Equation

This paper has two objectives. We introduce a new global optimization algorithm reformulating optimization problems in terms of boundary-value problems. Then, we apply this algorithm to a pointwise control problem of the viscous Burgers equation, where the control weight coefficient is progressively decreased. The results are compared with those obtained with a genetic algorithm and an LM-BFGS algorithm in order to check the efficiency of our method and the necessity of using global optimization techniques.     

Generalized mirror averaging and <Emphasis Type="Italic">D</Emphasis>-convex aggregation

We study the problem of aggregation of estimators. Given a collection of M different estimators, we construct a new estimator, called aggregate, which is nearly as good as the best linear combination over an l ₁-ball of ℝ^M of the initial estimators. The aggregate is obtained by a particular version of the mirror averaging algorithm. We show that our aggregation procedure statisfies sharp oracle inequalities under general assumptions. Then we apply these results to a new aggregation problem: D-convex aggregation. Finally we implement our procedure in a Gaussian regression model with random design and we prove its optimality in a minimax sense up to a logarithmic factor.      

Tournament Competition and its Merits for Coevolutionary Algorithms

In a competitive coevolutionary algorithm, the competition strategy, selecting opposing individuals, has a great influence on the performance of the algorithm. Therefore, a good competition strategy is crucial for an effective and efficient competitive coevolutionary algorithm. In this paper, we propose a new competition strategy called tournament competition. We investigate its characteristics and merits when applied to adversarial problems. To verify the performance of the new strategy, we first classify adversarial problems into two types: solution-test problems and game problems. We apply the strategy to both types. A set of experiments compares our strategy to several existing competition strategies and analyzes several aspects such as solution quality, evolution speed, and coevolutionary balance. The experimental results indicate that some of the existing competition strategies give different patterns according to problem types. The results also support that the proposed tournament strategy has the potential for finding good solutions, regardless of problem types.