The Random Forest Kernel and other kernels for big data from random partitions

We present Random Partition Kernels, a new class of kernels derived by demonstrating a natural connection between random partitions of objects and kernels between those objects. We show how the construction can be used to create kernels from methods that would not normally be viewed as random partitions, such as Random Forest. To demonstrate the potential of this method, we propose two new kernels, the Random Forest Kernel and the Fast Cluster Kernel, and show that these kernels consistently outperform standard kernels on problems involving real-world datasets. Finally, we show how the form of these kernels lend themselves to a natural approximation that is appropriate for certain big data problems, allowing $O(N)$ inference in methods such as Gaussian Processes, Support Vector Machines and Kernel PCA.

A reversible infinite HMM using normalised random measures

Copyright 2014 by the author(s). We present a nonparametric prior over reversible Markov chains. We use completely random measures, specifically gamma processes, to construct a countably infinite graph with weighted edges. By enforcing symmetry to make the edges undirected we define a prior over random walks on graphs that results in a reversible Markov chain. The resulting prior over infinite transition matrices is closely related to the hierarchical Dirichlet process but enforces reversibility. A reinforcement scheme has recently been proposed with similar properties, but the de Finetti measure is not well characterised. We take the alternative approach of explicitly constructing the mixing measure, which allows more straightforward and efficient inference at the cost of no longer having a closed form predictive distribution. We use our process to construct a reversible infinite HMM which we apply to two real datasets, one from epigenomics and one ion channel recording.

A derivation of the asymptotic random-coding prefactor

This paper studies the subexponential prefactor to the random-coding bound for a given rate. Using a refinement of Gallager's bounding techniques, an alternative proof of a recent result by Altuǧ and Wagner is given, and the result is extended to the setting of mismatched decoding. © 2013 IEEE.

Initiation of immersed granular avalanches.

By means of coupled molecular dynamics-computational fluid dynamics simulations, we analyze the initiation of avalanches in a granular bed of spherical particles immersed in a viscous fluid and inclined above its angle of repose. In quantitative agreement with experiments, we find that the bed is unstable for a packing fraction below 0.59 but is stabilized above this packing fraction by negative excess pore pressure induced by the effect of dilatancy. From detailed numerical data, we explore the time evolution of shear strain, packing fraction, excess pore pressures, and granular microstructure in this creeplike pressure redistribution regime, and we show that they scale excellently with a characteristic time extracted from a model based on the balance of granular stresses in the presence of a negative excess pressure and its interplay with dilatancy. The cumulative shear strain at failure is found to be ≃ 0.2, in close agreement with the experiments, irrespective of the initial packing fraction and inclination angle. Remarkably, the avalanche is triggered when dilatancy vanishes instantly as a result of fluctuations while the average dilatancy is still positive (expanding bed) with a packing fraction that declines with the initial packing fraction. Another nontrivial feature of this creeplike regime is that, in contrast to dry granular materials, the internal friction angle of the bed at failure is independent of dilatancy but depends on the inclination angle, leading therefore to a nonlinear dependence of the excess pore pressure on the inclination angle. We show that this behavior may be described in terms of the contact network anisotropy, which increases with a nearly constant connectivity and levels off at a value (critical state) that increases with the inclination angle. These features suggest that the behavior of immersed granular materials is controlled not only directly by hydrodynamic forces acting on the particles but also by the influence of the fluid on the granular microstructure.

A derivation of the source-channel error exponent using nonidentical product distributions

This paper studies the random-coding exponent of joint source-channel coding for a scheme where source messages are assigned to disjoint subsets (referred to as classes), and codewords are independently generated according to a distribution that depends on the class index of the source message. For discrete memoryless systems, two optimally chosen classes and product distributions are found to be sufficient to attain the sphere-packing exponent in those cases where it is tight. © 2014 IEEE.