Performance evaluation of evolutionary class of algorithms—An application to 0–1 knapsack problem

The 0–1 knapsack [1] problem is a well-known NP-complete problem. There are different algorithms in the literature to attack this problem, two of them being of specific interest. One is a pseudo polynomial algorithm of order O(nK), K being the target of the problem. This algorithm works unsatisfactorily, as the given target becomes high. In fact, the complexity might become exponential in that case. The other scheme is a fully polynomial time approximation scheme (FPTAS) whose complexity is also polynomial time. The present paper suggests a probabilistic heuristic which is an evolutionary scheme accompanied by the necessary statistical formulation and its theoretical justification. We have identified parameters responsible for the performance of our evolutionary scheme which in turn would keep the option open for improving the scheme.     

Elimination for Generic Sparse Polynomial Systems

We present a new probabilistic symbolic algorithm that, given a variety defined in an n-dimensional affine space by a generic sparse system with fixed supports, computes the Zariski closure of its projection to an ?-dimensional coordinate affine space with ?<n. The complexity of the algorithm depends polynomially on some combinatorial invariants associated to the supports.     

Constraint-based analysis of concurrent probabilistic hybrid systems: An application to networked automation systems

In previous publications, the authors have introduced the notion of stochastic satisfiability modulo theories (SSMT) and the corresponding SiSAT solving algorithm, which provide a symbolic method for the reachability analysis of probabilistic hybrid systems. SSMT extends satisfiability modulo theories (SMT) with randomized (or stochastic), existential, and universal quantification, as known from stochastic propositional satisfiability. In this paper, we extend the SSMT-based procedures to the symbolic analysis of concurrent probabilistic hybrid systems. After formally introducing the computational model, we provide a mechanized translation scheme to encode probabilistic bounded reachability problems of concurrent probabilistic hybrid automata as linearly sized SSMT formulae, which in turn can be solved by the SiSAT tool. We furthermore propose an algorithmic enhancement which tailors SiSAT to probabilistic bounded reachability problems by caching and reusing solutions obtained on bounded reachability problems of smaller depth. An essential part of this article is devoted to a case study from the networked automation systems domain. We explain in detail the formal model in terms of concurrent probabilistic automata, its encoding into the SiSAT modeling language, and finally the automated quantitative analysis.     

On the probabilistic analysis of an approximation algorithm for solving the <Emphasis Type="Italic">p</Emphasis>-median problem

In order to solve the location problem in the p-median form we present an approximation algorithm with time complexity O(n ₂) and the results of its probabilistic analysis. The input data are defined on a complete graph with distances between the vertices expressed by the independent random variables with the same uniform distribution. The value of the objective function produced by the algorithm amounts to a certain sum of the random variables that we analyze basing on an estimate for the probabilities of large deviations of these sums. We use a limit theorem in the form of the Petrov inequalities, taking into account the dependence of the random variables in the sum. The probabilistic analysis yields some estimates for the relative error and the failure probability of our algorithm, as well as conditions for its asymptotic exactness.     

Average complexity of a gift-wrapping algorithm for determining the convex hull of randomly given points

This paper presents an algorithm and its probabilistic analysis for constructing the convex hull ofm given points in ?ⁿ then-dimensional Euclidean space. The algorithm under consideration combines the Gift-Wrapping concept with the so-called Throw-Away Principle (introduced by Akl and Toussaint [1] and later by Devroye [10]) for nonextremal points. The latter principle had been used for a convex-hull-construction algorithm in R² and for its probabilistic analysis in a recent paper by Borgwardtet al. [5]. There, the considerations remained much simpler, because in ?² the construction of the convex hull essentially requires recognition of the extremal points and of their order only. In this paper the Simplex method is used to organize a walk over the surface of the convex hull. During this walk all facets are discovered. Under the condition of general position this information is sufficient, because the whole face lattice can simply be deduced when the set of facets is available. Exploiting the advantages of the revised Simplex method reduces the update effort to ann ×n matrix and the number of calculated quotients for the pivot search to the points which are not thrown away. For this algorithm a probabilistic analysis can be carried out. We assume that ourm random points are distributed identically, independently, and symmetrically under rotations in Rⁿ. Then the calculation of the expected effort becomes possible for a whole parametrical class of distributions over the unit ball. The results mean a progress in three directions:

a parametrization of the expected effort can be given;

the dependency onn— the dimension of the space—can be evaluated;

the additional work of preprocessing for detecting the vertices can be avoided without losing its advantages.

     

A simple heuristic approach to simplex efficiency

Consider the standard linear program:

$\text{Minimize}\text{cx}\text{subject to}\text{Ax=b, x?0}$

where A is an m × n matrix. The simplex algorithm solves this linear program by moving from an extreme point of the feasibility region to a better (in terms of the objective function cx) extreme point (via the pivot operation) until the optimal is reached. In order to obtain a feel for the number of necessary iterations, we consider a simple probabilistic (Markov chain) model as to how the algorithm moves along the extreme points. At first we suppose that if at any time the algorithm is at the jth best extreme point then after the next pivot the resulting extreme point is equally likely to be any of the j?1 best. Under this assumption, we show that the time to get from the Nth best to the best extreme point has approximately, for large N, a Poisson distribution with mean equal to the algorithm (base e) of N. We also consider a more general probabilistic model in which we drop the uniformity assumption and suppose that when at the jth best the next one is chosen probabilistically according to weights w_i, i = 1, …, j?1.     

Model-based clustering of high-dimensional data streams with online mixture of probabilistic PCA

Model-based clustering is a popular tool which is renowned for its probabilistic foundations and its flexibility. However, model-based clustering techniques usually perform poorly when dealing with high-dimensional data streams, which are nowadays a frequent data type. To overcome this limitation of model-based clustering, we propose an online inference algorithm for the mixture of probabilistic PCA model. The proposed algorithm relies on an EM-based procedure and on a probabilistic and incremental version of PCA. Model selection is also considered in the online setting through parallel computing. Numerical experiments on simulated and real data demonstrate the effectiveness of our approach and compare it to state-of-the-art online EM-based algorithms.     

Cooperative concurrent asynchronous computation of the solution of symmetric linear systems

This paper extends the idea of Brezinski’s hybrid acceleration procedure, for the solution of a system of linear equations with a symmetric coefficient matrix of dimension n, to a new context called cooperative computation, involving m agents (m ? n), each one concurrently computing the solution of the whole system, using an iterative method. Cooperation occurs between the agents through the communication, periodic or probabilistic, of the estimate of each agent to one randomly chosen agent, thus characterizing the computation as concurrent and asynchronous. Every time one agent receives solution estimates from the others, it carries out a least squares computation, involving a small linear system of dimension m, in order to replace its current solution estimate by an affine combination of the received estimates, and the algorithm continues until a stopping criterion is met. In addition, an autocooperative algorithm, in which estimates are updated using affine combinations of current and past estimates, is also proposed. The proposed algorithms are shown to be efficient for certain matrices, specifically in relation to the popular Barzilai–Borwein algorithm, through numerical experiments.     

On Smale's 17th Problem: A Probabilistic Positive Solution

Smale's 17th Problem asks “Can a zero of n complex polynomial equations in n unknowns be found approximately, on the average [for a suitable probability measure on the space of inputs], in polynomial time with a uniform algorithm?” We present a uniform probabilistic algorithm for this problem and prove that its complexity is polynomial. We thus obtain a partial positive solution to Smale's 17th Problem.     

On stochastic generation of ultrametrics in high-dimensional Euclidean spaces

We present a proof of the theorem which states that a matrix of Euclidean distances on a set of specially distributed random points in the n-dimensional Euclidean space R ⁿ converges in probability to an ultrametric matrix as n → ∞. Values of the elements of an ultrametric distance matrix are completely determined by variances of coordinates of random points. Also we present a probabilistic algorithm for generation of finite ultrametric structures of any topology in high-dimensional Euclidean space. Validity of the algorithm is demonstrated by explicit calculations of distance matrices and ultrametricity indexes for various dimensions n.     

Amortized Random Backtracking

Some nonsystematic search algorithms can deal with partial assignments of variables, and then can use constraint propagation techniques. Let us call them NSPA algorithms (Nonsystematic Search with Partial Assignments). For satisfiability or optimization problems, such NSPA algorithms scale a lot better than systematic algorithms. We show in this paper that naive NSPA algorithms have to pay a severe overhead due to the way they visit partial assignments. Amortizing the visits of partial assignments is an important feature which we introduce and analyze in this paper. We also propose a new NSPA algorithm that is amortized: it is called Amortized Random Backtracking, and performs a probabilistic exploration of the search space. It can be seen as an amortized version of iterative sampling and has given very good experimental results on a real life time tabling problem.     

Iterated Stochastic Processes: Simulation and Relationship with High Order Partial Differential Equations

In this paper, we consider the composition of two independent processes: one process corresponds to position and the other one to time. Such processes will be called iterated processes. We first propose an algorithm based on the Euler scheme to simulate the trajectories of the corresponding iterated processes on a fixed time interval. This algorithm is natural and can be implemented easily. We show that it converges almost surely, uniformly in time, with a rate of convergence of order 1/4 and propose an estimation of the error. We then extend the well known Feynman-Kac formula which gives a probabilistic representation of partial differential equations (PDEs), to its higher order version using iterated processes. In particular we consider general position processes which are not necessarily Markovian or are indexed by the real line but real valued. We also weaken some assumptions from previous works. We show that intertwining diffusions are related to transformations of high order PDEs. Combining our numerical scheme with the Feynman-Kac formula, we simulate functionals of the trajectories and solutions to fourth order PDEs that are naturally associated to a general class of iterated processes.     

An extension to possibilistic fuzzy cluster analysis

We explore an approach to possibilistic fuzzy clustering that avoids a severe drawback of the conventional approach, namely that the objective function is truly minimized only if all cluster centers are identical. Our approach is based on the idea that this undesired property can be avoided if we introduce a mutual repulsion of the clusters, so that they are forced away from each other. We develop this approach for the possibilistic fuzzy c-means algorithm and the Gustafson–Kessel algorithm. In our experiments we found that in this way we can combine the partitioning property of the probabilistic fuzzy c-means algorithm with the advantages of a possibilistic approach w.r.t. the interpretation of the membership degrees.     

Appendix to “Approximating Perpetuities”

An algorithm for perfect simulation from the unique solution of the distributional fixed point equation Y?=? _d UY?+?U(1???U) is constructed, where Y and U are independent and U is uniformly distributed on [0,1]. This distribution comes up as a limit distribution in the probabilistic analysis of the Quickselect algorithm. Our simulation algorithm is based on coupling from the past with a multigamma coupler. It has four lines of code.     

Anytime anyspace probabilistic inference

This paper investigates methods that balance time and space constraints against the quality of Bayesian network inferences––we explore the three-dimensional spectrum of “time × space × quality” trade-offs. The main result of our investigation is the adaptive conditioning algorithm, an inference algorithm that works by dividing a Bayesian network into sub-networks and processing each sub-network with a combination of exact and anytime strategies. The algorithm seeks a balanced synthesis of probabilistic techniques for bounded systems. Adaptive conditioning can produce inferences in situations that defy existing algorithms, and is particularly suited as a component of bounded agents and embedded devices.     

Fusing multiple Bayesian knowledge sources

We address the problem of information fusion in uncertain environments. Imagine there are multiple experts building probabilistic models of the same situation and we wish to aggregate the information they provide. There are several problems we may run into by naively merging the information from each. For example, the experts may disagree on the probability of a certain event or they may disagree on the direction of causality between two events (e.g., one thinks A causes B while another thinks B causes A). They may even disagree on the entire structure of dependencies among a set of variables in a probabilistic network. In our proposed solution to this problem, we represent the probabilistic models as Bayesian Knowledge Bases (BKBs) and propose an algorithm called Bayesian knowledge fusion that allows the fusion of multiple BKBs into a single BKB that retains the information from all input sources. This allows for easy aggregation and de-aggregation of information from multiple expert sources and facilitates multi-expert decision making by providing a framework in which all opinions can be preserved and reasoned over.     

On the numerical solution of a minimax control problem with a positional functional

The probabilistic analysis of an approximation algorithm for the minimum-weight m-peripatetic salesman problem with different weight functions of their routes (Hamiltonian cycles) is presented. The time complexity of the algorithm is O(mn ²). It is assumed that the elements of the distance matrix are independent equally distributed random variables with values in an upper unbounded domain [a _n , ∞), where a _n > 0. The analysis is carried out for the example of truncated normal and exponential distributions. Estimates for the relative error and failure probability, as well as conditions for the asymptotic exactness of the algorithm, are found.     

Complete tree subset difference broadcast encryption scheme and its analysis

The subset difference (SD) method proposed by Naor, Naor and Lotspiech is the most popular broadcast encryption (BE) scheme. It is suitable for real-time applications like Pay-TV and has been suggested for use by the AACS standard for digital rights management in Blu-Ray and HD-DVD discs. The SD method assumes the number of users to be a power of two. We propose the complete tree subset difference (CTSD) method that allows the system to support an arbitrary number of users. In particular, it subsumes the SD method and all results proved for the CTSD method also hold for the SD method. Recurrences are obtained for the CTSD scheme to count the number, N(n, r, h), of possible ways r users in the system of n users can be revoked to result in a transmission overhead or header length of h. The recurrences lead to a polynomial time dynamic programming algorithm for computing N(n, r, h). Further, they provide bounds on the maximum possible header length. A probabilistic analysis is performed to obtain an O(r log n) time algorithm to compute the expected header length in the CTSD scheme. Further, for the SD scheme we obtain an explicit limiting upper bound on the expected header length.     

Gated Bayesian networks for algorithmic trading

This paper introduces a new probabilistic graphical model called gated Bayesian network (GBN). This model evolved from the need to represent processes that include several distinct phases. In essence, a GBN is a model that combines several Bayesian networks (BNs) in such a manner that they may be active or inactive during queries to the model. We use objects called gates to combine BNs, and to activate and deactivate them when predefined logical statements are satisfied. In this paper we also present an algorithm for semi-automatic learning of GBNs. We use the algorithm to learn GBNs that output buy and sell decisions for use in algorithmic trading systems. We show how the learnt GBNs can substantially lower risk towards invested capital, while they at the same time generate similar or better rewards, compared to the benchmark investment strategy buy-and-hold. We also explore some differences and similarities between GBNs and other related formalisms.     

Multiresolutional decomposition and modeling with an application to joint probabilistic data association

A multiresolutional approach for measurement decomposition and system modeling is presented in this paper. The decomposition is performed in both spatial and time domains and provides an excellent platform for developing computationally efficient algorithms. Using multiresolutional decomposition and modeling, a multiresolutional joint probabilistic data association (MR-JPDA) algorithm is developed for multiple target tracking. Monte Carlo simulations demonstrate that the computation of the MRJPDA algorithm is much less than the traditional joint probabilistic data association (JPDA) algorithm with a comparable performance.