Large Deviations of Continuous Regular Conditional Probabilities

We study product regular conditional probabilities under measures of two coordinates with respect to the second coordinate that are weakly continuous on the support of the marginal of the second coordinate. Assuming that there exists a sequence of probability measures on the product space that satisfies a large deviation principle, we present necessary and sufficient conditions for the conditional probabilities under these measures to satisfy a large deviation principle. The arguments of these conditional probabilities are assumed to converge. A way to view regular conditional probabilities as a special case of product regular conditional probabilities is presented. This is used to derive conditions for large deviations of regular conditional probabilities. In addition, we derive a Sanov-type theorem for large deviations of the empirical distribution of the first coordinate conditioned on fixing the empirical distribution of the second coordinate.     

Computational algorithms for blocking probabilities in circuit-switched networks

In this paper, we develop two new general purpose recursive algorithms for the exact computation of blocking probabilities in multi-rate product-form circuit-switched networks with fixed routing. The first algorithm is a normalization constant approach based on the partition function of the state distribution. The second is a mean-value type of algorithm with a recursion cast in terms of blocking probabilities and conditional probabilities. The mean value recursion is derived from the normalization constant recursion. Both recursions are general purpose ones that do not depend on any specific network topology. The relative advantage of the mean-value algorithm is numerical stability, but this is obtained at the expense of an increase in computational costs.The results of section 2 were presented in part at the 7th ITC Seminar on Broadband Technologies, Morristown, NJ, October 1990.Supported in part by the National Science Foundation, Grant No. CCR-9015717.     

Imprecise Markov chains with absorption

We consider convergence of Markov chains with uncertain parameters, known as imprecise Markov chains, which contain an absorbing state. We prove that under conditioning on non-absorption the imprecise conditional probabilities converge independently of the initial imprecise probability distribution if some regularity conditions are assumed. This is a generalisation of a known result from the classical theory of Markov chains by Darroch and Seneta [6].     

Optimizing information using the EM algorithm in item response theory

Latent trait models such as item response theory (IRT) hypothesize a functional relationship between an unobservable, or latent, variable and an observable outcome variable. In educational measurement, a discrete item response is usually the observable outcome variable, and the latent variable is associated with an examinee’s trait level (e.g., skill, proficiency). The link between the two variables is called an item response function. This function, defined by a set of item parameters, models the probability of observing a given item response, conditional on a specific trait level. Typically in a measurement setting, neither the item parameters nor the trait levels are known, and so must be estimated from the pattern of observed item responses. Although a maximum likelihood approach can be taken in estimating these parameters, it usually cannot be employed directly. Instead, a method of marginal maximum likelihood (MML) is utilized, via the expectation-maximization (EM) algorithm. Alternating between an expectation (E) step and a maximization (M) step, the EM algorithm assures that the marginal log likelihood function will not decrease after each EM cycle, and will converge to a local maximum. Interestingly, the negative of this marginal log likelihood function is equal to the relative entropy, or Kullback-Leibler divergence, between the conditional distribution of the latent variables given the observable variables and the joint likelihood of the latent and observable variables. With an unconstrained optimization for the M-step proposed here, the EM algorithm as minimization of Kullback-Leibler divergence admits the convergence results due to Csiszár and Tusnády (Statistics & Decisions, 1:205–237, 1984), a consequence of the binomial likelihood common to latent trait models with dichotomous response variables. For this unconstrained optimization, the EM algorithm converges to a global maximum of the marginal log likelihood function, yielding an information bound that permits a fixed point of reference against which models may be tested. A likelihood ratio test between marginal log likelihood functions obtained through constrained and unconstrained M-steps is provided as a means for testing models against this bound. Empirical examples demonstrate the approach.     

Asymptotic convergence of a simulated annealing algorithm for multiobjective optimization problems

In this paper we consider a simulated annealing algorithm for multiobjective optimization problems. With a suitable choice of the acceptance probabilities, the algorithm is shown to converge asymptotically, that is, the Markov chain that describes the algorithm converges with probability one to the Pareto optimal set.     

Scale Invariance Properties in the Simulated Annealing Algorithm

The Boltzmann distribution used in the steady-state analysis of the simulated annealing algorithm gives rise to several scale invariant properties. Scale invariance is first presented in the context of parallel independent processors and then extended to an abstract form based on lumping states together to form new aggregate states. These lumped or aggregate states possess all of the mathematical characteristics, forms and relationships of states (solutions) in the original problem in both first and second moments. These scale invariance properties therefore permit new ways of relating objective function values, conditional expectation values, stationary probabilities, rates of change of stationary probabilities and conditional variances. Such properties therefore provide potential applications in analysis, statistical inference and optimization. Directions for future research that take advantage of scale invariance are also discussed.     

Exponential family non-linear models for categorical data with errors of observation

We present a general framework for treating categorical data with errors of observation. We show how both latent class models and models for doubly sampled data can be treated as exponential family nonlinear models. These are extended generalized linear models with the link function substituted by an observationwise defined non-linear function of the model parameters. The models are formulated in terms of structural probabilities and conditional error probabilities, thus allowing natural constraints when modelling errors of observation. We use an iteratively reweighted least squares procedure for obtaining maximum likelihood estimates. This is faster than the traditionally used EM algorithm and the computations can be made in GLIM.¹ As examples we analyse three sets of categorical data with errors of observation which have been analysed before by Ashford and Sowden,² Goodman³ and Chen,⁴ respectively.     

Single observation adaptive search for discrete and continuous stochastic optimization

Solving a stochastic optimization problem often involves performing repeated noisy function evaluations at points encountered during the algorithm. Recently, a continuous optimization framework for executing a single observation per search point was shown to exhibit a martingale property so that associated estimation errors are guaranteed to converge to zero. We generalize this martingale single observation approach to problems with mixed discrete–continuous variables. We establish mild regularity conditions for this class of algorithms to converge to a global optimum.     

Latent class model with conditional dependency per modes to cluster categorical data

We propose a parsimonious extension of the classical latent class model to cluster categorical data by relaxing the conditional independence assumption. Under this new mixture model, named conditional modes model (CMM), variables are grouped into conditionally independent blocks. Each block follows a parsimonious multinomial distribution where the few free parameters model the probabilities of the most likely levels, while the remaining probability mass is uniformly spread over the other levels of the block. Thus, when the conditional independence assumption holds, this model defines parsimonious versions of the standard latent class model. Moreover, when this assumption is violated, the proposed model brings out the main intra-class dependencies between variables, summarizing thus each class with relatively few characteristic levels. The model selection is carried out by an hybrid MCMC algorithm that does not require preliminary parameter estimation. Then, the maximum likelihood estimation is performed via an EM algorithm only for the best model. The model properties are illustrated on simulated data and on three real data sets by using the associated R package CoModes. The results show that this model allows to reduce biases involved by the conditional independence assumption while providing meaningful parameters.     

Algorithms to Find Exact Inclusion Probabilities for Conditional Poisson Sampling and Pareto πps Sampling Designs

Conditional Poisson Sampling Design as developed by Haje´k may be defined as a Poisson sampling conditioned by the requirement that the sample has fixed size. In this paper, an algorithm is implemented to calculate the conditional inclusion probabilities given the inclusion probabilities under Poisson Sampling. A simple algorithm is also given for second order inclusion probabilities in Conditional Poisson Sampling. Furthermore a numerical method is introduced to compute the unconditional inclusion probabilities when the conditional inclusion probabilities are predetermined. Simultaneously, we study the Pareto ps sampling design. This method, introduced by Rose´n, belongs to a class of sampling schemes called Order Sampling with Fixed Distribution Shape. Methods are provided to compute the first and second order inclusion probabilities numerically also in this case, as well as two procedures to adjust the parameters to get predetermined inclusion probabilities.     

Control problems with time-lag. II

Consider a continuous time Markov chain with stationary transition probabilities. A function of the state is observed. A regular conditional probability distribution for the trajectory of the chain, given observations up to time t, is obtained. This distribution also corresponds to a Markov chain, but the conditional chain has nonstationary transition probabilities. In particular, computation of the conditional distribution of the state at time s is discussed. For s > t, we have prediction (extrapolation), while s < t corresponds to smoothing (interpolation). Equations for the conditional state distribution are given on matrix form and as recursive differential equations with varying s or t. These differential equations are closely related to Kolmogorov's forward and backward equations. Markov chains with one observed and one unobserved component are treated as a special case. In an example, the conditional distribution of the change-point is derived for a Poisson process with a changing intensity, given observations of the Poisson process.     

Simulated annealing for constrained global optimization

Hide-and-Seek is a powerful yet simple and easily implemented continuous simulated annealing algorithm for finding the maximum of a continuous function over an arbitrary closed, bounded and full-dimensional body. The function may be nondifferentiable and the feasible region may be nonconvex or even disconnected. The algorithm begins with any feasible interior point. In each iteration it generates a candidate successor point by generating a uniformly distributed point along a direction chosen at random from the current iteration point. In contrast to the discrete case, a single step of this algorithm may generateany point in the feasible region as a candidate point. The candidate point is then accepted as the next iteration point according to the Metropolis criterion parametrized by anadaptive cooling schedule. Again in contrast to discrete simulated annealing, the sequence of iteration points converges in probability to a global optimum regardless of how rapidly the temperatures converge to zero. Empirical comparisons with other algorithms suggest competitive performance by Hide-and-Seek.This material is based on work supported by a NATO Collaborative Research Grant, no. 0119/89.     

Independence for full conditional probabilities: Structure,factorization, non-uniqueness,and Bayesian networks

This paper examines concepts of independence for full conditional probabilities; that is, for set-functions that encode conditional probabilities as primary objects, and that allow conditioning on events of probability zero. Full conditional probabilities have been used in economics, in philosophy, in statistics, in artificial intelligence. This paper characterizes the structure of full conditional probabilities under various concepts of independence; limitations of existing concepts are examined with respect to the theory of Bayesian networks. The concept of layer independence (factorization across layers) is introduced; this seems to be the first concept of independence for full conditional probabilities that satisfies the graphoid properties of Symmetry, Redundancy, Decomposition, Weak Union, and Contraction. A theory of Bayesian networks is proposed where full conditional probabilities are encoded using infinitesimals, with a brief discussion of hyperreal full conditional probabilities.     

Statistical mechanics of nonlinear nonequilibrium financial markets: Applications to optimized trading

A paradigm of statistical mechanics of financial markets (SMFM) using nonlinear non-equilibrium algorithms, first published in [1], is fit to multivariate financial markets using Adaptive Simulated Annealing (ASA), a global optimization algorithm, to perform maximum likelihood fits of Lagrangians defined by path integrals of multivariate conditional probabilities. Canonical momenta are thereby derived and used as technical indicators in a recursive ASA optimization process to tune trading rules. These trading rules are then used on out-of-sample data, to demonstrate that they can profit from the SMFM model, to illustrate that these markets are likely not efficient.     

Solving nonlinearly constrained global optimization problem via an auxiliary function method

This paper considers the nonlinearly constrained continuous global minimization problem. Based on the idea of the penalty function method, an auxiliary function, which has approximately the same global minimizers as the original problem, is constructed. An algorithm is developed to minimize the auxiliary function to find an approximate constrained global minimizer of the constrained global minimization problem. The algorithm can escape from the previously converged local minimizers, and can converge to an approximate global minimizer of the problem asymptotically with probability one. Numerical experiments show that it is better than some other well known recent methods for constrained global minimization problems.     

Paradoxes in conditional probability

It is shown that paradoxes arise in conditional probability calculations, due to incomplete specification of the problem at hand. This is illustrated with the Borel and the Kac-Slepian type paradoxes. These are significant in applications including Bayesian inference. Also Rényi's axiomatic setup does not resolve them. An open problem on calculation of conditional probabilities in the continuous case is noted.     

A general importance sampling algorithm for estimating portfolio loss probabilities in linear factor models

This paper develops a novel importance sampling algorithm for estimating the probability of large portfolio losses in the conditional independence framework. We apply exponential tilts to (i) the distribution of the natural sufficient statistics of the systematic risk factors and (ii) conditional default probabilities, given the simulated values of the systematic risk factors, and select parameter values by minimizing the Kullback–Leibler divergence of the resulting parametric family from the ideal (zero-variance) importance density. Optimal parameter values are shown to satisfy intuitive moment-matching conditions, and the asymptotic behaviour of large portfolios is used to approximate the requisite moments. In a sense we generalize the algorithm of Glasserman and Li (2005) so that it can be applied in a wider variety of models. We show how to implement our algorithm in the $t$ copula model and compare its performance there to the algorithm developed by Chan and Kroese (2010). We find that our algorithm requires substantially less computational time (especially for large portfolios) but is slightly less accurate. Our algorithm can also be used to estimate more general risk measures, such as conditional tail expectations, whereas Chan and Kroese (2010) is specifically designed to estimate loss probabilities.     

Finite difference methods for the weak solutions of the Kolmogorov equations for the density of both diffusion and conditional diffusion processes

The paper treats the problem of obtaining numerical solutions to the Fokker-Plank equation for the density of a diffusion, and for the conditional density, given certain “white noise” corrupted observations. These equations generally have a meaning only in the weak sense; the basic assumptions on the diffusion are that the coefficients are bounded, and uniformly continuous, and that the diffusion has a unique solution in the sense of multivariate distributions. It is shown that, if the finite difference approximations are carefully (but naturally) chosen, then the finite difference solutions to the formal adjoints yield immediately a sequence of approximations that converge weakly to the weak sense solution to the Fokker-Plank equation (conditional or not), as the difference intervals go to zero.The approximations seem very natural for this type of problem. They are related to the transition functions of a sequence of Markov chains, the measures of whose continuous time interpolations converge weakly to the (measure of) diffusion, as the difference intervals go to zero, and, hence, seem to have more physical significance than the usual (formal or not) approximations. The method is purely probabilistic and relies heavily on results of the weak convergence of measures on abstract spaces.     

On approximation of smoothing probabilities for hidden Markov models

We consider the smoothing probabilities of hidden Markov model (HMM). We show that under fairly general conditions for HMM, the exponential forgetting still holds, and the smoothing probabilities can be well approximated with the ones of double-sided HMM. This makes it possible to use ergodic theorems. As an application we consider the pointwise maximum a posteriori segmentation, and show that the corresponding risks converge.     

Maximising entropy on the nonparametric predictive inference model for multinomial data

The combination of mathematical models and uncertainty measures can be applied in the area of data mining for diverse objectives with as final aim to support decision making. The maximum entropy function is an excellent measure of uncertainty when the information is represented by a mathematical model based on imprecise probabilities. In this paper, we present algorithms to obtain the maximum entropy value when the information available is represented by a new model based on imprecise probabilities: the nonparametric predictive inference model for multinomial data (NPI-M), which represents a type of entropy-linear program. To reduce the complexity of the model, we prove that the NPI-M lower and upper probabilities for any general event can be expressed as a combination of the lower and upper probabilities for the singleton events, and that this model can not be associated with a closed polyhedral set of probabilities. An algorithm to obtain the maximum entropy probability distribution on the set associated with NPI-M is presented. We also consider a model which uses the closed and convex set of probability distributions generated by the NPI-M singleton probabilities, a closed polyhedral set. We call this model A-NPI-M. A-NPI-M can be seen as an approximation of NPI-M, this approximation being simpler to use because it is not necessary to consider the set of constraints associated with the exact model.