Optimal scaling of discrete approximations to Langevin diffusions

We consider the optimal scaling problem for proposal distributions in Hastings–Metropolis algorithms derived from Langevin diffusions. We prove an asymptotic diffusion limit theorem and show that the relative efficiency of the algorithm can be characterized by its overall acceptance rate, independently of the target distribution. The asymptotically optimal acceptance rate is 0.574. We show that, as a function of dimension n , the complexity of the algorithm is O ( n ^1/3), which compares favourably with the O ( n ) complexity of random walk Metropolis algorithms. We illustrate this comparison with some example simulations.     

Nonparametric maximum likelihood estimation of population size based on the counting distribution

Summary.  The paper discusses the estimation of an unknown population size n . Suppose that an identification mechanism can identify n _obs cases. The Horvitz–Thompson estimator of n adjusts this number by the inverse of 1− p ₀, where the latter is the probability of not identifying a case. When repeated counts of identifying the same case are available, we can use the counting distribution for estimating p ₀ to solve the problem. Frequently, the Poisson distribution is used and, more recently, mixtures of Poisson distributions. Maximum likelihood estimation is discussed by means of the EM algorithm. For truncated Poisson mixtures, a nested EM algorithm is suggested and illustrated for several application cases. The algorithmic principles are used to show an inequality, stating that the Horvitz–Thompson estimator of n by using the mixed Poisson model is always at least as large as the estimator by using a homogeneous Poisson model. In turn, if the homogeneous Poisson model is misspecified it will, potentially strongly, underestimate the true population size. Examples from various areas illustrate this finding.     

A modal method for generating binomial variables

The paper considers the problem of generating binomial random variables when the parameters n and p may vary from call to call (as in the generation of multinomial random variables), A new algorithm, based on sequentially searching alternately down and up from the modal probability, is introduced. This is easy to program and requires no special library facilities It is suitable for microcomputers as well as mainframes Some sample timings are given for a FORTRAN 7 7 implementation     

Node deletion sequences in influence diagrams using genetic algorithms

Influence diagrams are powerful tools for representing and solving complex inference and decision-making problems under uncertainty. They are directed acyclic graphs with nodes and arcs that have a precise meaning. The algorithm for evaluating an influence diagram deletes nodes from the graph in a particular order given by the position of each node and its arcs with respect to the value node. In many cases, however, there is more than one possible node deletion sequence. They all lead to the optimal solution of the problem, but may involve different computational efforts, which is a primary issue when facing real-size models. Finding the optimal deletion sequence is a NP-hard problem. The proposals given in the literature have proven to require complex transformations of the influence diagram. In this paper, we present a genetic algorithm-based approach, which merely has to be added to the influence diagram evaluation algorithm we use, and whose codification is straightforward. The experiments, varying parameters like crossover and mutation operators, population sizes and mutation rates, are analysed statistically, showing favourable results over existing heuristics.     

An alternative algorithm of the empirical likelihood estimation for the parameter of a linear regression model

ABSTRACT

Empirical likelihood (EL) is a nonparametric method based on observations. EL method is defined as a constrained optimization problem. The solution of this constrained optimization problem is carried on using duality approach. In this study, we propose an alternative algorithm to solve this constrained optimization problem. The new algorithm is based on a newton-type algorithm for Lagrange multipliers for the constrained optimization problem. We provide a simulation study and a real data example to compare the performance of the proposed algorithm with the classical algorithm. Simulation and the real data results show that the performance of the proposed algorithm is comparable with the performance of the existing algorithm in terms of efficiencies and cpu-times.     

Calculating nonparametric confidence intervals for quantiles using fractional order statistics

In this paper, we provide an easy-to-program algorithm for constructing the preselected 100(1 - alpha)% nonparametric confidence interval for an arbitrary quantile, such as the median or quartile, by approximating the distribution of the linear interpolation estimator of the quantile function Q L ( u ) = (1 - epsilon) X \[ n u ] + epsilon X \[ n u ] + 1 with the distribution of the fractional order statistic Q I ( u ) = Xn u , as defined by Stigler, where n = n + 1 and \[ . ] denotes the floor function. A simulation study verifies the accuracy of the coverage probabilities. An application to the extreme-value problem in flood data analysis in hydrology is illustrated.     

Sparse inverse covariance estimation for high-throughput microRNA sequencing data in the Poisson log-normal graphical model

We introduce a one-step EM algorithm to estimate the graphical structure in a Poisson-Log-Normal graphical model. This procedure is equivalent to a normality transformation that makes the problem of identifying relationships in high-throughput microRNA (miRNA) sequence data feasible. The Poisson-log-normal model moreover allows us to directly account for known overdispersion relationships present in this data set. We show that our EM algorithm provides a provable increase in performance in determining the network structure. The model is shown to provide an increase in performance in simulation settings over a range of network structures. The model is applied to high-throughput miRNA sequencing data from patients with breast cancer from The Cancer Genome Atlas (TCGA). By selecting the most highly connected miRNA molecules in the fitted network we find that nearly all of them are known to be involved in the regulation of breast cancer.     

Improving Convergence of the HastingsMetropolis Algorithm with an Adaptive Proposal

The HastingsMetropolis algorithm is a general MCMC method for sampling from a density known up to a constant. Geometric convergence of this algorithm has been proved under conditions relative to the instrumental (or proposal) distribution. We present an inhomogeneous HastingsMetropolis algorithm for which the proposal density approximates the target density, as the number of iterations increases. The proposal density at the n th step is a non-parametric estimate of the density of the algorithm, and uses an increasing number of i.i.d. copies of the Markov chain. The resulting algorithm converges (in n ) geometrically faster than a HastingsMetropolis algorithm with any fixed proposal distribution. The case of a strictly positive density with compact support is presented first, then an extension to more general densities is given. We conclude by proposing a practical way of implementation for the algorithm, and illustrate it over simulated examples.     

Estimation of weighted multinomial probabilities under log-convex constraints

Many problems in Statistics involve maximizing a multinomial likelihood over a restricted region. In this paper, we consider instead maximizing a weighted multinomial likelihood. We show that a dual problem always exits which is frequently more tractable and that a solution to the dual problem leads directly to a solution of the primal problem. Moreover, the form of the dual problem suggests an iterative algorithm for solving the MLE problem when the constraint region can be written as a finite intersection of cones. We show that this iterative algorithm is guaranteed to converge to the true solution and show that when the cones are isotonic, this algorithm is a version of Dykstra's algorithm (Dykstra, J. Amer. Statist. Assoc. 78 (1983) 837–842) for the special case of least squares projection onto the intersection of isotonic cones. We give several meaningful examples to illustrate our results. In particular, we obtain the nonparametric maximum likelihood estimator of a monotone density function in the presence of selection bias.     

Statistical and computational tradeoff in genetic algorithm-based estimation

When a genetic algorithm (GA) is employed in a statistical problem, the result is affected by both variability due to sampling and the stochastic elements of algorithm. Both of these components should be controlled in order to obtain reliable results. In the present work we analyze parametric estimation problems tackled by GAs, and pursue two objectives: the first one is related to a formal variability analysis of final estimates, showing that it can be easily decomposed in the two sources of variability. In the second one we introduce a framework of GA estimation with fixed computational resources, which is a form of statistical and the computational tradeoff question, crucial in recent problems. In this situation the result should be optimal from both the statistical and computational point of view, considering the two sources of variability and the constraints on resources. Simulation studies will be presented for illustrating the proposed method and the statistical and computational tradeoff question.     

A lower bound based smoothed quasi-Newton algorithm for group bridge penalized regression

In this paper, we propose a lower bound based smoothed quasi-Newton algorithm for computing the solution paths of the group bridge estimator in linear regression models. Our method is based on the quasi-Newton algorithm with a smoothed group bridge penalty in combination with a novel data-driven thresholding rule for the regression coefficients. This rule is derived based on a necessary KKT condition of the group bridge optimization problem. It is easy to implement and can be used to eliminate groups with zero coefficients. Thus, it reduces the dimension of the optimization problem. The proposed algorithm removes the restriction of groupwise orthogonal condition needed in coordinate descent and LARS algorithms for group variable selection. Numerical results show that the proposed algorithm outperforms the coordinate descent based algorithms in both efficiency and accuracy.     

Prior Density Selection as a Particular Case of Bayesian Model Selection: A Predictive Approach

A Bayesian model consists of two elements: a sampling model and a prior density. The problem of selecting a prior density is nothing but the problem of selecting a Bayesian model where the sampling model is fixed. A predictive approach is used through a decision problem where the loss function is the squared L ² distance between the sampling density and the posterior predictive density, because the aim of the method is to choose the prior that provides a posterior predictive density as good as possible. An algorithm is developed for solving the problem; this algorithm is based on Lavine's linearization technique.     

DINDSCAL: direct INDSCAL

The well-known INDSCAL model for simultaneous metric multidimensional scaling (MDS) of three-way data analyzes doubly centered matrices of squared dissimilarities. An alternative approach, called for short DINDSCAL, is proposed for analyzing directly the input matrices of squared dissimilarities. An important consequence is that missing values can be easily handled. The DINDSCAL problem is solved by means of the projected gradient approach. First, the problem is transformed into a gradient dynamical system on a product matrix manifold (of Stiefel sub-manifold of zero-sum matrices and non-negative diagonal matrices). The constructed dynamical system can be numerically integrated which gives a globally convergent algorithm for solving the DINDSCAL. The DINDSCAL problem and its solution are illustrated by well-known data routinely used in metric MDS and INDSCAL. Alternatively, the problem can also be solved by iterative algorithm based on the conjugate (projected) gradient method, which MATLAB implementation is enclosed as an appendix.     

A simple algorithm for the adaptation of scores and power behavior of the corresponding rank test

The purpose of this paper is twofold:On one hand we want to give a very simple algorithm for evaluating a special rank estimator of the type given in Behnen, Neuhaus, and Ruymgaart (1983) for the approximate optimal choice of the scores-generating function of a two-sample linear rank test for the general testing problem H_o:F=G versus H₁:F ≤ G, F ≠ G, in order to demonstrate that the corresponding adaptive rank statistic is simple enough for practical applications. On the other hand we prove the asymptotic normality of the adaptive rank statistic under H (leading to approximate critical values) and demonstrate the adaptive behavior of the corresponding rank test by a Monte Carlo power simulation for sample sizes as low as m=10, n=10.     

Extended tables for moments of gamma distribution order statistics

Apart from having intrinsic mathematical interest, order statistics are also useful in the solution of many applied sampling and analysis problems. For a general review of the properties and uses of order statistics, see David (1981). This paper provides tabulations of means and variances of certain order statistics from the gamma distribution, for parameter values not previously available. The work was motivated by a particular quota sampling problem, for which existing tables are not adequate. The solution to this sampling problem actually requires the moments of the highest order statistic within a given set; however the calculation algorithm used involves a recurrence relation, which causes all the lower order statistics to be calculated first. Therefore we took the opportunity to develop more extensive tables for the gamma order statistic moments in general. Our tables provide values for the order statistic moments which were not available in previous tables, notably those for higher values of m, the gamma distribution shape parameter. However we have also retained the corresponding statistics for lower values of m, first to allow for checking accuracy of the computtions agtainst previous tables, and second to provide an integrated presentation of our new results with the previously known values in a consistent format     

Obtaining least absolute value estimates for a two-way classification model

The importance of the two-way classification model is well known, but the standard method of analysis is least squares. Often, the data of the model calls for a more robust estimation technique. This paper demonstrates the equivalence between the problem of obtaining least absolute value estimates for the two-way classification model and a capacitated transportation problem. A special purpose primal algorithm is developed to provide the least absolute value estimates. A computational comparison is made between an implementation of this specialized algorithm and a standard capacitated transportation code.     

改进BP神经网络在经济预测中的应用

针对传统BP学习算法收敛速度慢、对步长依赖明显等缺点，提出一种利用搜索较优步长的BP算法。其在网络训练中，能够在每次迭代中搜索出一个相对合理的步长，从而使步长的选择对学习速度的影响大大降低。对经济预测仿真结果表明，新算法对步长选择的依赖性小于传统BP算法。     

A special purpose linear programming algorithm for obtaining least absolute value estimators in a linear model with dummy variables

Dummy (0, 1) variables are frequently used in statistical modeling to represent the effect of certain extraneous factors. This paper presents a special purpose linear programming algorithm for obtaining least-absolute-value estimators in a linear model with dummy variables. The algorithm employs a compact basis inverse procedure and incorporates the advanced basis exchange techniques available in specialized algorithms for the general linear least-absolute-value problem. Computational results with a computer code version of the algorithm are given.     

Parameter Estimation in Large Dynamic Paired Comparison Experiments

Paired comparison data in which the abilities or merits of the objects being compared may be changing over time can be modelled as a non-linear state space model. When the population of objects being compared is large, likelihood-based analyses can be too computationally cumbersome to carry out regularly. This presents a problem for rating populations of chess players and other large groups which often consist of tens of thousands of competitors. This problem is overcome through a computationally simple non-iterative algorithm for fitting a particular dynamic paired comparison model. The algorithm, which improves over the commonly used algorithm of Elo by incorporating the variability in parameter estimates, can be performed regularly even for large populations of competitors. The method is evaluated on simulated data and is applied to ranking the best chess players of all time, and to ranking the top current tennis-players.     

Improved cross-entropy method for estimation

The cross-entropy (CE) method is an adaptive importance sampling procedure that has been successfully applied to a diverse range of complicated simulation problems. However, recent research has shown that in some high-dimensional settings, the likelihood ratio degeneracy problem becomes severe and the importance sampling estimator obtained from the CE algorithm becomes unreliable. We consider a variation of the CE method whose performance does not deteriorate as the dimension of the problem increases. We then illustrate the algorithm via a high-dimensional estimation problem in risk management.