Learning classification trees

Algorithms for learning classification trees have had successes in artificial intelligence and statistics over many years. This paper outlines how a tree learning algorithm can be derived using Bayesian statistics. This introduces Bayesian techniques for splitting, smoothing, and tree averaging. The splitting rule is similar to Quinlan's information gain, while smoothing and averaging replace pruning. Comparative experiments with reimplementations of a minimum encoding approach,c4 (Quinlanet al., 1987) andcart (Breimanet al., 1984), show that the full Bayesian algorithm can produce more accurate predictions than versions of these other approaches, though pays a computational price.     

On the rate of convergence of the Robbins–Monro's algorithm in a linear stochastic ill-posed problem with α-mixing data

In this paper we consider a recursive method of Robbins–Monro type to estimate the solution of the linear problem Ax = u, in which the second member is measured with α-mixing errors. We also show the almost complete convergence (a.co) of this algorithm specifying its convergence rate.     

Efficient Monte Carlo simulation via the generalized splitting method

We describe a new Monte Carlo algorithm for the consistent and unbiased estimation of multidimensional integrals and the efficient sampling from multidimensional densities. The algorithm is inspired by the classical splitting method and can be applied to general static simulation models. We provide examples from rare-event probability estimation, counting, and sampling, demonstrating that the proposed method can outperform existing Markov chain sampling methods in terms of convergence speed and accuracy.     

Numerical algorithms for solving nonlinear L р-norm estimation problems: part II - a mixture method for large residual and illo-conditioned problems

The nonlinear least squares algorithm of Gill and Murray (1978) is extended and modified to solve nonlinear L _р-norm estimation problems efficiently. The new algorithm uses a mixture of 1st-order derivative (Guass-Newton) and 2nd-order derivative (Newton) search directions. A new rule for selecting the “grade” r of the p-jacobiab matrix J_p was also incorporated. This brought about rapid convergence of the algorithm on previously reported test examples.     

ML estimation for factor analysis: EM or non-EM?

To obtain maximum likelihood (ML) estimation in factor analysis (FA), we propose in this paper a novel and fast conditional maximization (CM) algorithm, which has quadratic and monotone convergence, consisting of a sequence of CM log-likelihood (CML) steps. The main contribution of this algorithm is that the closed form expression for the parameter to be updated in each step can be obtained explicitly, without resorting to any numerical optimization methods. In addition, a new ECME algorithm similar to Liu’s (Biometrika 81, 633–648, 1994) one is obtained as a by-product, which turns out to be very close to the simple iteration algorithm proposed by Lawley (Proc. R. Soc. Edinb. 60, 64–82, 1940) but our algorithm is guaranteed to increase log-likelihood at every iteration and hence to converge. Both algorithms inherit the simplicity and stability of EM but their convergence behaviors are much different as revealed in our extensive simulations: (1) In most situations, ECME and EM perform similarly; (2) CM outperforms EM and ECME substantially in all situations, no matter assessed by the CPU time or the number of iterations. Especially for the case close to the well known Heywood case, it accelerates EM by factors of around 100 or more. Also, CM is much more insensitive to the choice of starting values than EM and ECME.     

Self-updating clustering algorithm for estimating the parameters in mixtures of von Mises distributions

The EM algorithm is the standard method for estimating the parameters in finite mixture models. Yang and Pan [25] proposed a generalized classification maximum likelihood procedure, called the fuzzy c-directions (FCD) clustering algorithm, for estimating the parameters in mixtures of von Mises distributions. Two main drawbacks of the EM algorithm are its slow convergence and the dependence of the solution on the initial value used. The choice of initial values is of great importance in the algorithm-based literature as it can heavily influence the speed of convergence of the algorithm and its ability to locate the global maximum. On the other hand, the algorithmic frameworks of EM and FCD are closely related. Therefore, the drawbacks of FCD are the same as those of the EM algorithm. To resolve these problems, this paper proposes another clustering algorithm, which can self-organize local optimal cluster numbers without using cluster validity functions. These numerical results clearly indicate that the proposed algorithm is superior in performance of EM and FCD algorithms. Finally, we apply the proposed algorithm to two real data sets.     

The one-step-late PXEM algorithm

The EM algorithm is a popular method for computing maximum likelihood estimates or posterior modes in models that can be formulated in terms of missing data or latent structure. Although easy implementation and stable convergence help to explain the popularity of the algorithm, its convergence is sometimes notoriously slow. In recent years, however, various adaptations have significantly improved the speed of EM while maintaining its stability and simplicity. One especially successful method for maximum likelihood is known as the parameter expanded EM or PXEM algorithm. Unfortunately, PXEM does not generally have a closed form M-step when computing posterior modes, even when the corresponding EM algorithm is in closed form. In this paper we confront this problem by adapting the one-step-late EM algorithm to PXEM to establish a fast closed form algorithm that improves on the one-step-late EM algorithm by insuring monotone convergence. We use this algorithm to fit a probit regression model and a variety of dynamic linear models, showing computational savings of as much as 99.9%, with the biggest savings occurring when the EM algorithm is the slowest to converge.     

A note on the monotonicity of the ES algorithm

In the study of the robust nonparametric regression problem, Oh et al. [The role of pseudo data for robust smoothing with application to wavelet regression, Biometrika 94 (2007), pp. 893–904] developed and named the ES algorithm. In the event that the ES algorithm converges, the robust estimator can be obtained through a sequence of conventional penalized least-squares estimates, the computation of which is fast and straightforward. However, the convergence of the ES algorithm was not established theoretically in Oh et al. In this note, we show that under a certain simple condition, the ES algorithm is monotonic. In particular, the ES algorithm does converge globally in the setting of Oh et al.     

Modified minimum covariance determinant estimator and its application to outlier detection of chemical process data

To overcome the main flaw of minimum covariance determinant (MCD) estimator, i.e. difficulty to determine its main parameter h, a modified-MCD (M-MCD) algorithm is proposed. In M-MCD, the self-adaptive iteration is proposed to minimize the deflection between the standard deviation of robust mahalanobis distance square, which is calculated by MCD with the parameter h based on the sample, and the standard deviation of theoretical mahalanobis distance square by adjusting the parameter h of MCD. Thus, the optimal parameter h of M-MCD is determined when the minimum deflection is obtained. The results of convergence analysis demonstrate that M-MCD has good convergence property. Further, M-MCD and MCD were applied to detect outliers for two typical data and chemical process data, respectively. The results show that M-MCD can get the optimal parameter h by using the self-adaptive iteration and thus its performances of outlier detection are better than MCD.     

D-optimal designs via a cocktail algorithm

A fast new algorithm is proposed for numerical computation of (approximate) D-optimal designs. This cocktail algorithm extends the well-known vertex direction method (VDM; Fedorov in Theory of Optimal Experiments, 1972) and the multiplicative algorithm (Silvey et al. in Commun. Stat. Theory Methods 14:1379–1389, 1978), and shares their simplicity and monotonic convergence properties. Numerical examples show that the cocktail algorithm can lead to dramatically improved speed, sometimes by orders of magnitude, relative to either the multiplicative algorithm or the vertex exchange method (a variant of VDM). Key to the improved speed is a new nearest neighbor exchange strategy, which acts locally and complements the global effect of the multiplicative algorithm. Possible extensions to related problems such as nonparametric maximum likelihood estimation are mentioned.     

Parameter estimation of nonlinear mixed-effects models using first-order conditional linearization and the EM algorithm

Nonlinear mixed-effects (NLME) models are flexible enough to handle repeated-measures data from various disciplines. In this article, we propose both maximum-likelihood and restricted maximum-likelihood estimations of NLME models using first-order conditional expansion (FOCE) and the expectation–maximization (EM) algorithm. The FOCE-EM algorithm implemented in the ForStat procedure SNLME is compared with the Lindstrom and Bates (LB) algorithm implemented in both the SAS macro NLINMIX and the S-Plus/R function nlme in terms of computational efficiency and statistical properties. Two realworld data sets an orange tree data set and a Chinese fir (Cunninghamia lanceolata) data set, and a simulated data set were used for evaluation. FOCE-EM converged for all mixed models derived from the base model in the two realworld cases, while LB did not, especially for the models in which random effects are simultaneously considered in several parameters to account for between-subject variation. However, both algorithms had identical estimated parameters and fit statistics for the converged models. We therefore recommend using FOCE-EM in NLME models, particularly when convergence is a concern in model selection.     

Estimation of the intensity function of an inhomogeneous Poisson process with a change‐point

Recent work on point processes includes studying posterior convergence rates of estimating a continuous intensity function. In this article, convergence rates for estimating the intensity function and change‐point are derived for the more general case of a piecewise continuous intensity function. We study the problem of estimating the intensity function of an inhomogeneous Poisson process with a change‐point using non‐parametric Bayesian methods. An Markov Chain Monte Carlo (MCMC) algorithm is proposed to obtain estimates of the intensity function and the change‐point which is illustrated using simulation studies and applications. The Canadian Journal of Statistics 47: 604–618; 2019 © 2019 Statistical Society of Canada     

Steady-state ranked Gibbs sampler

Gibbs sampler as a computer-intensive algorithm is an important statistical tool both in application and in theoretical work. This algorithm, in many cases, is time-consuming; this paper extends the concept of using the steady-state ranked simulated sampling approach, utilized in Monte Carlo methods by Samawi [On the approximation of multiple integrals using steady state ranked simulated sampling, 2010, submitted for publication], to improve the well-known Gibbs sampling algorithm. It is demonstrated that this approach provides unbiased estimators, in the case of estimating the means and the distribution function, and substantially improves the performance of the Gibbs sampling algorithm and convergence, which results in a significant reduction in the costs and time required to attain a certain level of accuracy. Similar to Casella and George [Explaining the Gibbs sampler, Am. Statist. 46(3) (1992), pp. 167–174], we provide some analytical properties in simple cases and compare the performance of our method using the same illustrations.     

Domains of convergence for the EM algorithm: a cautionary tale in a location estimation problem

The EM algorithm is a popular method for maximizing a likelihood in the presence of incomplete data. When the likelihood has multiple local maxima, the parameter space can be partitioned into domains of convergence, one for each local maximum. In this paper we investigate these domains for the location family generated by the t-distribution. We show that, perhaps somewhat surprisingly, these domains need not be connected sets. As an extreme case we give an example of a domain which consists of an infinite union of disjoint open intervals. Thus the convergence behaviour of the EM algorithm can be quite sensitive to the starting point.     

Adaptive Multiple Importance Sampling

Abstract. The Adaptive Multiple Importance Sampling algorithm is aimed at an optimal recycling of past simulations in an iterated importance sampling (IS) scheme. The difference with earlier adaptive IS implementations like Population Monte Carlo is that the importance weights of all simulated values, past as well as present, are recomputed at each iteration, following the technique of the deterministic multiple mixture estimator of Owen & Zhou (J. Amer. Statist. Assoc., 95, 2000, 135). Although the convergence properties of the algorithm cannot be investigated, we demonstrate through a challenging banana shape target distribution and a population genetics example that the improvement brought by this technique is substantial.     

Estimation and test of several multivariate normal means under an order restriction when the dimension is larger than two

Suppose that an order restriction is imposed among several p-variate normal mean vectors. We are interested in the problems of estimating these mean vectors and testing their homogeneity under this restriction. These problems are multivariate extensions of Bartholomew's (1959) ones. For the bivariate case, these problems have been studied by Sasabuchi et al. (1983) and (1998) and some others. In the present paper we examine the convergence of an iterative algorithm for computing the maximum likelihood estimator when p is larger than two. We also study some test procedures for testing homogeneity when p is larger than two.     

The EM algorithm with gradient function update for discrete mixtures with known (fixed) number of components

The paper is focussing on some recent developments in nonparametric mixture distributions. It discusses nonparametric maximum likelihood estimation of the mixing distribution and will emphasize gradient type results, especially in terms of global results and global convergence of algorithms such as vertex direction or vertex exchange method. However, the NPMLE (or the algorithms constructing it) provides also an estimate of the number of components of the mixing distribution which might be not desirable for theoretical reasons or might be not allowed from the physical interpretation of the mixture model. When the number of components is fixed in advance, the before mentioned algorithms can not be used and globally convergent algorithms do not exist up to now. Instead, the EM algorithm is often used to find maximum likelihood estimates. However, in this case multiple maxima are often occuring. An example from a meta-analyis of vitamin A and childhood mortality is used to illustrate the considerable, inferential importance of identifying the correct global likelihood. To improve the behavior of the EM algorithm we suggest a combination of gradient function steps and EM steps to achieve global convergence leading to the EM algorithm with gradient function update (EMGFU). This algorithms retains the number of components to be exactly k and typically converges to the global maximum. The behavior of the algorithm is highlighted at hand of several examples.     

A two‐step proximal‐point algorithm for the calculus of divergence‐based estimators in finite mixture models

Estimators derived from the expectation‐maximization (EM) algorithm are not robust since they are based on the maximization of the likelihood function. We propose an iterative proximal‐point algorithm based on the EM algorithm to minimize a divergence criterion between a mixture model and the unknown distribution that generates the data. The algorithm estimates in each iteration the proportions and the parameters of the mixture components in two separate steps. Resulting estimators are generally robust against outliers and misspecification of the model. Convergence properties of our algorithm are studied. The convergence of the introduced algorithm is discussed on a two‐component Weibull mixture entailing a condition on the initialization of the EM algorithm in order for the latter to converge. Simulations on Gaussian and Weibull mixture models using different statistical divergences are provided to confirm the validity of our work and the robustness of the resulting estimators against outliers in comparison to the EM algorithm. An application to a dataset of velocities of galaxies is also presented. The Canadian Journal of Statistics 47: 392–408; 2019 © 2019 Statistical Society of Canada     

Convergence behavior of an iterative reweighting algorithm to compute multivariate M-estimates for location and scatter

The iteratively reweighting algorithm is one of the widely used algorithm to compute the M-estimates for the location and scatter parameters of a multivariate dataset. If the M estimating equations are the maximum likelihood estimating equations from some scale mixture of normal distributions (e.g. from a multivariate t-distribution), the iteratively reweighting algorithm is identified as an EM algorithm and the convergence behavior of which is well established. However, as Tyler (J. Roy. Statist. Soc. Ser. B 59 (1997) 550) pointed out, little is known about the theoretical convergence properties of the iteratively reweighting algorithms if it cannot be identified as an EM algorithm. In this paper, we consider the convergence behavior of the iteratively reweighting algorithm induced from the M estimating equations which cannot be identified as an EM algorithm. We give some general results on the convergence properties and, we show that convergence behavior of a general iteratively reweighting algorithm induced from the M estimating equations is similar to the convergence behavior of an EM algorithm even if it cannot be identified as an EM algorithm.     

A multiple group item response theory model with centered skew-normal latent trait distributions under a Bayesian framework

Very often, in psychometric research, as in educational assessment, it is necessary to analyze item response from clustered respondents. The multiple group item response theory (IRT) model proposed by Bock and Zimowski [12] provides a useful framework for analyzing such type of data. In this model, the selected groups of respondents are of specific interest such that group-specific population distributions need to be defined. The usual assumption for parameter estimation in this model, which is that the latent traits are random variables following different symmetric normal distributions, has been questioned in many works found in the IRT literature. Furthermore, when this assumption does not hold, misleading inference can result. In this paper, we consider that the latent traits for each group follow different skew-normal distributions, under the centered parameterization. We named it skew multiple group IRT model. This modeling extends the works of Azevedo et al. [4], Bazán et al. [11] and Bock and Zimowski [12] (concerning the latent trait distribution). Our approach ensures that the model is identifiable. We propose and compare, concerning convergence issues, two Monte Carlo Markov Chain (MCMC) algorithms for parameter estimation. A simulation study was performed in order to evaluate parameter recovery for the proposed model and the selected algorithm concerning convergence issues. Results reveal that the proposed algorithm recovers properly all model parameters. Furthermore, we analyzed a real data set which presents asymmetry concerning the latent traits distribution. The results obtained by using our approach confirmed the presence of negative asymmetry for some latent trait distributions.