We consider the problem of learning to optimize an unknown Markov decision process (MDP). We show that, if the MDP can be parameterized within some known function class, we can obtain regret bounds that scale with the dimensionality, rather than cardinality, of the system. We characterize this dependence explicitly as $\tilde{O}(\sqrt{d_K d_E T})$ where $T$ is time elapsed, $d_K$ is the Kolmogorov dimension and $d_E$ is the \emph{eluder dimension}. These represent the first unified regret bounds for model-based reinforcement learning and provide state of the art guarantees in several important settings. Moreover, we present a simple and computationally efficient algorithm \emph{posterior sampling for reinforcement learning} (PSRL) that satisfies these bounds.

We demonstrate that there is significant redundancy in the parameterization of several deep learning models. Given only a few weight values for each feature it is possible to accurately predict the remaining values. Moreover, we show that not only can the parameter values be predicted, but many of them need not be learned at all. We train several different architectures by learning only a small number of weights and predicting the rest. In the best case we are able to predict more than 95% of the weights of a network without any drop in accuracy.

Restricted Boltzmann machines (RBMs) are powerful machine learning models, but learning and some kinds of inference in the model require sampling-based approximations, which, in classical digital computers, are implemented using expensive MCMC. Physical computation offers the opportunity to reduce the cost of sampling by building physical systems whose natural dynamics correspond to drawing samples from the desired RBM distribution. Such a system avoids the burn-in and mixing cost of a Markov chain. However, hardware implementations of this variety usually entail limitations such as low-precision and limited range of the parameters and restrictions on the size and topology of the RBM. We conduct software simulations to determine how harmful each of these restrictions is. Our simulations are based on the D-Wave Two computer, but the issues we investigate arise in most forms of physical computation. Our findings suggest that designers of new physical computing hardware and algorithms for physical computers should focus their efforts on overcoming the limitations imposed by the topology restrictions of currently existing physical computers.

Runge-Kutta methods are the classic family of solvers for ordinary differential equations (ODEs), and the basis for the state of the art. Like most numerical methods, they return point estimates. We construct a family of probabilistic numerical methods that instead return a Gauss-Markov process defining a probability distribution over the ODE solution. In contrast to prior work, we construct this family such that posterior means match the outputs of the Runge-Kutta family exactly, thus inheriting their proven good properties. Remaining degrees of freedom not identified by the match to Runge-Kutta are chosen such that the posterior probability measure fits the observed structure of the ODE. Our results shed light on the structure of Runge-Kutta solvers from a new direction, provide a richer, probabilistic output, have low computational cost, and raise new research questions.

Although EEG signals due to their high temporal resolution show highly stochastic temporal evolution, it has been found that the scalp potential topographies are not so random and follow finite sets of small number of quasi-stable patterns which are termed as microstates [2]. Recently, Jamal et al. [3] investigated the temporal evolution of the frequency band-specific phase difference topographies to find periods of phase locking in multichannel EEG signals. It has been found in [4] that the phase difference topographies do not change abruptly and microstate-like quasi-stable phase locked patterns are observed in a temporal resolution of the order of milliseconds. These small number of stable phase synchronized patterns are termed as synchrostates, which switches from one to the other within the time interval of a cognitive task. The existence of synchrostates during face perception tasks was first observed in the beta (β) band (13-30 Hz) with different ensembles of EEG signals [4]. For similar visual stimuli, the interstate switching patterns only slightly change among different ensembles or trials [4], however it is different for different stimuli and also across different groups of people [3].

Mass spectrometry can involve two soft ionization techniques: matrix-assisted laser desorption ionization (MALDI) and surface-enhanced laser desorption and ionization (SELDI). For each analyzed fluid sample, MALDI or SELDI hardwares generate a high-dimensional mass spectrum, recording between 10,000 and 20,000 "mass-to-charge (m/z) ratios" corresponding to the ionized peptides present in the fluid sample, as well as "intensities" roughly quantifying the concentrations of these peptides in the sample. Generally m/z ratios take values anywhere between 200 and 20,000 Daltons, and are acquired with a known relative accuracy ρ which depends on the acquisition modalities, and ranges from 0.1% to 0.3%. Analyzing this type of high dimensional data oftern requires specialized software tools, implementing sophisticated machine learning techniques such as SVM (support vector machines) (Li and others (2004), Yu and others (2005)), artificial neural networks (Ball and others (2002)), or random forests (Izmirlian (2004)). These techniques typically generate "black-box" classifiers, which often reach good discrimination levels between cancerous and control groups, but are difficult to interpret biologically in terms of characteristic biomarkers patterns. This often leads to unexpected performance variations on totally new data sets. To develop clinically usable software tools for analysis of mass spectra acuired by MALDI or SELDI hardwares, a key step is to implement automated discovery of explicit "signatures", i.e. short lists of proteomic biomarkers with high discriminating powers between cancer groups (Yasui and others (2003)). Some easily interpretable automatic classifiers, such as linear combinations of biomarker weights (Wang and Chang (2011)), can be found in previous studies, but these approaches do not attempt to quantify the discriminating impact of simultaneous presence for specific pairs of biomarkers.

We propose a new Bayesian tracking and parameter learning algorithm for non-linear non-Gaussian multiple target tracking (MTT) models. We design a Markov chain Monte Carlo (MCMC) algorithm to sample from the posterior distribution of the target states, birth and death times, and association of observations to targets, which constitutes the solution to the tracking problem, as well as the model parameters. In the numerical section, we present performance comparisons with several competing techniques and demonstrate significant performance improvements in all cases.

We propose a new framework for how to use sequential Monte Carlo (SMC) algorithms for inference in probabilistic graphical models (PGM). Via a sequential decomposition of the PGM we find a sequence of auxiliary distributions defined on a monotonically increasing sequence of probability spaces. By targeting these auxiliary distributions using SMC we are able to approximate the full joint distribution defined by the PGM. One of the key merits of the SMC sampler is that it provides an unbiased estimate of the partition function of the model. We also show how it can be used within a particle Markov chain Monte Carlo framework in order to construct high-dimensional block-sampling algorithms for general PGMs.

This paper introduces a linear state-space model with time-varying dynamics. The time dependency is obtained by forming the state dynamics matrix as a time-varying linear combination of a set of matrices. The time dependency of the weights in the linear combination is modelled by another linear Gaussian dynamical model allowing the model to learn how the dynamics of the process changes. Previous approaches have used switching models which have a small set of possible state dynamics matrices and the model selects one of those matrices at each time, thus jumping between them. Our model forms the dynamics as a linear combination and the changes can be smooth and more continuous. The model is motivated by physical processes which are described by linear partial differential equations whose parameters vary in time. An example of such a process could be a temperature field whose evolution is driven by a varying wind direction. The posterior inference is performed using variational Bayesian approximation. The experiments on stochastic advection-diffusion processes and real-world weather processes show that the model with time-varying dynamics can outperform previously introduced approaches.

In many statistical learning problems, the target functions to be optimized are highly non-convex in various model spaces and thus are difficult to analyze. In this paper, we compute Energy Landscape Maps (ELMs) which characterize and visualize an energy function with a tree structure, in which each leaf node represents a local minimum and each non-leaf node represents the barrier between adjacent energy basins. The ELM also associates each node with the estimated probability mass and volume for the corresponding energy basin. We construct ELMs by adopting the generalized Wang-Landau algorithm and multidomain sampler that simulates a Markov chain traversing the model space by dynamically reweighting the energy function. We construct ELMs in the model space for two classic statistical learning problems: i) clustering with Gaussian mixture models or Bernoulli templates; and ii) bi-clustering. We propose a way to measure the difficulties (or complexity) of these learning problems and study how various conditions affect the landscape complexity, such as separability of the clusters, the number of examples, and the level of supervision; and we also visualize the behaviors of different algorithms, such as K-mean, EM, two-step EM and Swendsen-Wang cuts, in the energy landscapes. Key words and phrases: Non-convex Optimization, Visualization, Clustering, Bi-clustering, Markov chain Monte Carlo. 1. INTRODUCTION In many statistical learning problems, the energy functions to be optimized are highly non-convex.