We describe a method for computing provably exact maximum a poste- riori (MAP) estimates for a subclass of problems on graphs with cycles. The basic idea is to represent the original problem on the graph with cy- cles as a convex combination of tree-structured problems. A convexity argument then guarantees that the optimal value of the original problem (i.e., the log probability of the MAP assignment) is upper bounded by the combined optimal values of the tree problems. We prove that this upper bound is met with equality if and only if the tree problems share an opti- mal configuration in common. An important implication is that any such shared configuration must also be the MAP configuration for the original problem.

We establish a new hardness result that shows that the difficulty of plan- ning in factored Markov decision processes is representational rather than just computational. More precisely, we give a fixed family of fac- tored MDPs with linear rewards whose optimal policies and value func- tions simply cannot be represented succinctly in any standard parametric form. Previous hardness results indicated that computing good policies from the MDP parameters was difficult, but left open the possibility of succinct function approximation for any fixed factored MDP. Our result applies even to policies which yield a polynomially poor approximation to the optimal value, and highlights interesting connectionswith the com- plexity class of Arthur-Merlin games.

We present the bump mixture model, a statistical model for analog data where the probabilistic semantics, inference, and learning rules derive from low-level transistor behavior. The bump mixture model relies on translinear circuits to perform probabilistic infer- ence, and floating-gate devices to perform adaptation. This system is low power, asynchronous, and fully parallel, and supports vari- ous on-chip learning algorithms. In addition, the mixture model can perform several tasks such as probability estimation, vector quanti- zation, classification, and clustering. We tested a fabricated system on clustering, quantization, and classification of handwritten digits and show performance comparable to the E-M algorithm on mix- tures of Gaussians.

The information bottleneck (IB) method is an information-theoretic formulation, this method constructs for clustering problems. Given a joint distribution a new variable that are informative . Maximum likelihood (ML) of mixture models is a standard statistical about approach to clustering problems. In this paper, we ask: how are the two methods related? We define a simple mapping between the IB problem and the ML prob- lem for the multinomial mixture model.

We propose a dynamic Bayesian model for motifs in biopolymer se- quences which captures rich biological prior knowledge and positional dependencies in motif structure in a principled way. Our model posits that the position-specific multinomial parameters for monomer distribu- tion are distributed as a latent Dirichlet-mixture random variable, and the position-specific Dirichlet component is determined by a hidden Markov process. Model parameters can be fit on training motifs using a vari- ational EM algorithm within an empirical Bayesian framework. Varia- tional inference is also used for detecting hidden motifs. Our model im- proves over previous models that ignore biological priors and positional dependence.

In this paper, we propose a Bayesian framework, which constructs shared-state triphone HMMs based on a variational Bayesian approach, and recognizes speech based on the Bayesian prediction classi(cid:2)cation; variational Bayesian estimation and clustering for speech recognition (VBEC). An appropriate model structure with high recognition perfor- mance can be found within a VBEC framework. Unlike conventional methods, including BIC or MDL criterion based on the maximum likeli- hood approach, the proposed model selection is valid in principle, even when there are insuf(cid:2)cient amounts of data, because it does not use an asymptotic assumption. In isolated word recognition experiments, we show the advantage of VBEC over conventional methods, especially when dealing with small amounts of data.

Convergence for iterative reinforcement learning algorithms like TD(O) depends on the sampling strategy for the transitions. How(cid:173) ever, in practical applications it is convenient to take transition data from arbitrary sources without losing convergence. In this paper we investigate the problem of repeated synchronous updates based on a fixed set of transitions. This allows to analyse if a certain reinforcement learning algorithm and a cer(cid:173) tain function approximator are compatible. For the combination of the residual gradient algorithm with grid-based linear interpolation we show that there exists a universal constant learning rate such that the iteration converges independently of the concrete transi(cid:173) tion data.

This paper describes a system for the unsupervised learning of morpho- logical suffixes and stems from word lists. The system is composed of a generative probability model and hill-climbing and directed search algo- rithms. By extracting and examining morphologically rich subsets of an input lexicon, the directed search identifies highly productive paradigms. Quantitative results are shown by measuring the accuracy of the morphological relations identified. Experiments in English and Pol- ish, as well as comparisons with another recent unsupervised morphol- ogy learning algorithm demonstrate the effectiveness of this technique.

We present a simple direct approach for solving the ICA problem, using density estimation and maximum likelihood. Given a candi(cid:173) date orthogonal frame, we model each of the coordinates using a semi-parametric density estimate based on cubic splines. Since our estimates have two continuous derivatives, we can easily run a sec(cid:173) ond order search for the frame parameters. Our method performs very favorably when compared to state-of-the-art techniques.

In recent years variational methods have become a popular tool for approximate inference and learning in a wide variety of proba- bilistic models. For each new application, however, it is currently necessary (cid:12)rst to derive the variational update equations, and then to implement them in application-speci(cid:12)c code. Each of these steps is both time consuming and error prone. In this paper we describe a general purpose inference engine called VIBES ('Variational Infer- ence for Bayesian Networks') which allows a wide variety of proba- bilistic models to be implemented and solved variationally without recourse to coding. New models are speci(cid:12)ed either through a simple script or via a graphical interface analogous to a drawing package.