Search

The Laplace approximation (LA) of the Bayesian posterior is a Gaussian distribution centered at the maximum a posteriori estimate. Its appeal in Bayesian deep learning stems from the ability to quantify uncertainty post-hoc (i.e., after standard network parameter optimization), the ease of sampling from the approximate posterior, and the analytic form of model evidence. However, an important computational bottleneck of LA is the necessary step of calculating and inverting the Hessian matrix of the log posterior. The Hessian may be approximated in a variety of ways, with quality varying with a number of factors including the network, dataset, and inference task. In this paper, we propose an alternative framework that sidesteps Hessian calculation and inversion. The Hessian-free Laplace (HFL) approximation uses curvature of both the log posterior and network prediction to estimate its variance. Only two point estimates are needed: the standard maximum a posteriori parameter and the optimal parameter under a loss regularized by the network prediction. We show that, under standard assumptions of LA in Bayesian deep learning, HFL targets the same variance as LA, and can be efficiently amortized in a pre-trained network. Experiments demonstrate comparable performance to that of exact and approximate Hessians, with excellent coverage for in-between uncertainty., Comment: 10 pages, 5 figures

We propose training fitted Q-iteration with log-loss (FQI-log) for batch reinforcement learning (RL). We show that the number of samples needed to learn a near-optimal policy with FQI-log scales with the accumulated cost of the optimal policy, which is zero in problems where acting optimally achieves the goal and incurs no cost. In doing so, we provide a general framework for proving small-cost bounds, i.e. bounds that scale with the optimal achievable cost, in batch RL. Moreover, we empirically verify that FQI-log uses fewer samples than FQI trained with squared loss on problems where the optimal policy reliably achieves the goal.

Origami metamaterial design enables drastic qualitative changes in the response properties of a thin sheet via the addition of a repeating pattern of folds based around a rigid folding motion. Known also as a mechanism, this folding motion will have a very small energy cost when applied uniformly; and yet uniform activation of such remains highly difficult to observe, these sheets instead generically displaying nonuniform response patterns which are not yet well understood. Here, we present a purely geometric continuum theory which captures the nonuniform, nonlinear response to generic loading as composed locally of the planar mechanism, as well as previously identified ``twist'' and ``bend'' modes which enable the patterned sheet to curve out of the plane across long distances. Our numerical analysis confirms that these three modes govern the observed nonuniform response, varying smoothly across the sheet according to three PDEs which guarantee compatibility. In analogy with the recently solved case of planar mechanism metamaterials, these ``Orisometries'' (origami + isometries, so named by us) are subextensive but infinite in number, with each mode displaying, in the linear limit, ``sheared analytic'' spatial patterns which are controlled by the Poisson's ratio of the uniform folding mechanism. Furthermore, the ``planar'' mechanism-based deformation patterns superimpose with a mathematically dual space of ``non-planar'' twist/bend deformations to span the available soft linear response. Together, our findings furnish the first quantification of the number of soft response modes available, as well as the first intuitive quantification of their spatial distribution., Comment: 7 pages + 17 pages appendices, 5 figures

Functional structures from across the engineered and biological world combine rigid elements such as bones and columns with flexible ones such as cables, fibers and membranes. These structures are known loosely as tensegrities, since these cable-like elements have the highly nonlinear property of supporting only extensile tension. Marginally rigid systems are of particular interest because the number of structural constraints permits both flexible deformation and the support of external loads. We present a model system in which tensegrity elements are added at random to a regular backbone. This system can be solved analytically via a directed graph theory, revealing a novel mechanical critical point generalizing that of Maxwell. We show that even the addition of a few cable-like elements fundamentally modifies the nature of this transition point, as well as the later transition to a fully rigid structure. Moreover, the tensegrity network displays a fundamentally new collective avalanche behavior, in which the addition of a single cable leads to the elimination of multiple floppy modes, a phenomenon that becomes dominant at the transition point. These phenomena have implications for systems with nonlinear mechanical constraints, from biopolymer networks to soft robots to jammed packings to origami sheets., Comment: 13 pages, 8 figures

Epistemic uncertainty quantification is a crucial part of drawing credible conclusions from predictive models, whether concerned about the prediction at a given point or any downstream evaluation that uses the model as input. When the predictive model is simple and its evaluation differentiable, this task is solved by the delta method, where we propagate the asymptotically-normal uncertainty in the predictive model through the evaluation to compute standard errors and Wald confidence intervals. However, this becomes difficult when the model and/or evaluation becomes more complex. Remedies include the bootstrap, but it can be computationally infeasible when training the model even once is costly. In this paper, we propose an alternative, the implicit delta method, which works by infinitesimally regularizing the training loss of the predictive model to automatically assess downstream uncertainty. We show that the change in the evaluation due to regularization is consistent for the asymptotic variance of the evaluation estimator, even when the infinitesimal change is approximated by a finite difference. This provides both a reliable quantification of uncertainty in terms of standard errors as well as permits the construction of calibrated confidence intervals. We discuss connections to other approaches to uncertainty quantification, both Bayesian and frequentist, and demonstrate our approach empirically., Comment: 18 pages, NeurIPS 2022

Periodic networks on the verge of mechanical instability, called Maxwell lattices, are known to exhibit zero-frequency modes localized to their boundaries. Topologically polarized Maxwell lattices, in particular, focus these zero modes to one of their boundaries in a manner that is protected against disorder by the reciprocal-space topology of the lattice's band structure. Here, we introduce a class of mechanical bilayers as a model system for designing topologically protected edge modes that couple in-plane dilational and shearing modes to out-of-plane flexural modes, a paradigm that we refer to as omnimodal polarization. While these structures exhibit a high-dimensional design space that makes it difficult to predict the topological polarization of generic geometries, we are able to identify a family of mirror-symmetric bilayers that inherit the in-plane modal localization of their constitutive monolayers whose topological polarization can be determined analytically. Importantly, the coupling between the layers results in the emergence of omnimodal polarization, whereby in-plane and out-of-plane edge modes localize on the same edge. We demonstrate these theoretical results by fabricating a mirror-symmetric, topologically polarized kagome bilayer consisting of a network of elastic beams via additive manufacturing and confirm this finite-frequency polarization via finite element analysis and laser-vibrometry experiments.

Periodic lattices in hyperbolic space are characterized by symmetries beyond Euclidean crystallographic groups, offering a new platform for classical and quantum waves, demonstrating great potentials for a new class of topological metamaterials. One important feature of hyperbolic lattices is that their translation group is nonabelian, permitting high-dimensional irreducible representations (irreps), in contrast to abelian translation groups in Euclidean lattices. Here we introduce a general framework to construct wave eigenstates of high-dimensional irreps of infinite hyperbolic lattices, thereby generalizing Bloch's theorem, and discuss its implications on unusual mode-counting and degeneracy, as well as bulk-edge correspondence in hyperbolic lattices. We apply this method to a mechanical hyperbolic lattice, and characterize its band structure and zero modes of high-dimensional irreps., Comment: 10 pages, 4 figures

Locomotion by shape changes (spermatozoon swimming, snake slithering, bird flapping) or gas expulsion (rocket firing) is assumed to require environmental interaction, due to conservation of momentum. As first noted in (Wisdom, 2003) and later in (Gu\'eron, 2009) and (Avron et al, 2006), in curved space or spacetime the non-commutativity of translations permits translation without momentum exchange, just as falling cats and lizards can self-deform to reorient in flat space without environmental interaction. Translation in curved space can occur not only in gravitationally induced curved spacetime (where translation is predicted to be on the order of $10^{-23}$ m per gait cycle) but also in the curved surfaces encountered by locomotors in real-world environments. Here we show that a precision robophysical apparatus consisting of motors driven on curved tracks (and thereby confined to a spherical surface without a solid substrate) can self-propel without environmental momentum exchange (impulse) via shape changes that can generate gauge potentials that manifest as translations. Our system produces shape changes comparable to the environment's inverse curvatures and generates from zero momentum forward movement of $10^{-1}$ cm per gait cycle even while resisted by weak gravitational and frictional forces. Dissipation via friction eventually arrests the robot but also imbues it with momentum which can be released upon a cessation of shape changes. This work demonstrates how the interaction between environmental curvature, active driving and geometric phases yields rich, exotic phenomena.

Exploration is a crucial aspect of bandit and reinforcement learning algorithms. The uncertainty quantification necessary for exploration often comes from either closed-form expressions based on simple models or resampling and posterior approximations that are computationally intensive. We propose instead an approximate exploration methodology based on fitting only two point estimates, one tuned and one overfit. The approach, which we term the residual overfit method of exploration (ROME), drives exploration towards actions where the overfit model exhibits the most overfitting compared to the tuned model. The intuition is that overfitting occurs the most at actions and contexts with insufficient data to form accurate predictions of the reward. We justify this intuition formally from both a frequentist and a Bayesian information theoretic perspective. The result is a method that generalizes to a wide variety of models and avoids the computational overhead of resampling or posterior approximations. We compare ROME against a set of established contextual bandit methods on three datasets and find it to be one of the best performing., Comment: 13 pages, 16 figures

Geometric compatibility constraints dictate the mechanical response of soft systems that can be utilized for the design of mechanical metamaterials such as the negative Poisson ratio Miura-ori origami crease pattern. Here, we develop a formalism for linear compatibility that enables explicit investigation of the interplay between geometric symmetries and functionality in origami crease patterns. We apply this formalism to a particular class of periodic crease patterns with unit cells composed of four arbitrary parallelogram faces and establish that their mechanical response is characterized by an anticommuting symmetry. In particular, we show that the modes are eigenstates of this symmetry operator and that these modes are simultaneously diagonalizable with the symmetric strain operator and the antisymmetric curvature operator. This feature reveals that the anticommuting symmetry defines an equivalence class of crease pattern geometries which possess equal and opposite in-plane and out-of-plane Poisson's ratios.

Users of music streaming, video streaming, news recommendation, and e-commerce services often engage with content in a sequential manner. Providing and evaluating good sequences of recommendations is therefore a central problem for these services. Prior reweighting-based counterfactual evaluation methods either suffer from high variance or make strong independence assumptions about rewards. We propose a new counterfactual estimator that allows for sequential interactions in the rewards with lower variance in an asymptotically unbiased manner. Our method uses graphical assumptions about the causal relationships of the slate to reweight the rewards in the logging policy in a way that approximates the expected sum of rewards under the target policy. Extensive experiments in simulation and on a live recommender system show that our approach outperforms existing methods in terms of bias and data efficiency for the sequential track recommendations problem.

We consider the zero-energy deformations of periodic origami sheets with generic crease patterns. Using a mapping from the linear folding motions of such sheets to force-bearing modes in conjunction with the Maxwell-Calladine index theorem we derive a relation between the number of linear folding motions and the number of rigid body modes that depends only on the average coordination number of the origami's vertices. This supports the recent result by Tachi which shows periodic origami sheets with triangular faces exhibit two-dimensional spaces of rigidly foldable cylindrical configurations. We also find, through analytical calculation and numerical simulation, branching of this configuration space from the flat state due to geometric compatibility constraints that prohibit finite Gaussian curvature. The same counting argument leads to pairing of spatially varying modes at opposite wavenumber in triangulated origami, preventing topological polarization but permitting a family of zero energy deformations in the bulk that may be used to reconfigure the origami sheet.

Collaborative filtering analyzes user preferences for items (e.g., books, movies, restaurants, academic papers) by exploiting the similarity patterns across users. In implicit feedback settings, all the items, including the ones that a user did not consume, are taken into consideration. But this assumption does not accord with the common sense understanding that users have a limited scope and awareness of items. For example, a user might not have heard of a certain paper, or might live too far away from a restaurant to experience it. In the language of causal analysis, the assignment mechanism (i.e., the items that a user is exposed to) is a latent variable that may change for various user/item combinations. In this paper, we propose a new probabilistic approach that directly incorporates user exposure to items into collaborative filtering. The exposure is modeled as a latent variable and the model infers its value from data. In doing so, we recover one of the most successful state-of-the-art approaches as a special case of our model, and provide a plug-in method for conditioning exposure on various forms of exposure covariates (e.g., topics in text, venue locations). We show that our scalable inference algorithm outperforms existing benchmarks in four different domains both with and without exposure covariates., Comment: 11 pages, 4 figures. WWW'16

Models for recommender systems use latent factors to explain the preferences and behaviors of users with respect to a set of items (e.g., movies, books, academic papers). Typically, the latent factors are assumed to be static and, given these factors, the observed preferences and behaviors of users are assumed to be generated without order. These assumptions limit the explorative and predictive capabilities of such models, since users' interests and item popularity may evolve over time. To address this, we propose dPF, a dynamic matrix factorization model based on the recent Poisson factorization model for recommendations. dPF models the time evolving latent factors with a Kalman filter and the actions with Poisson distributions. We derive a scalable variational inference algorithm to infer the latent factors. Finally, we demonstrate dPF on 10 years of user click data from arXiv.org, one of the largest repository of scientific papers and a formidable source of information about the behavior of scientists. Empirically we show performance improvement over both static and, more recently proposed, dynamic recommendation models. We also provide a thorough exploration of the inferred posteriors over the latent variables., Comment: RecSys 2015

We present a new analysis of Kerr-Newman-deSitter black holes in terms of thermodynamic quantities that are defined in the observable portion of the universe; between the black hole and cosmological horizons. In particular, we replace the mass $m$ with a new 'area product' parameter $X$. The physical region of parameter space is found analytically and thermodynamic quantities are given by simple algebraic functions of these parameters. We find that different geometrical properties of the black holes are usefully distinguished by the sum of the black hole and cosmological entropies. The physical parameter space breaks into a region in which the total entropy, together with $\Lambda$, $a$ and $q$ uniquely specifies the black hole, and a region in which there is a two-fold degeneracy. In this latter region, there are isentropic pairs of black holes, having the same $\Lambda$, $a$, and $q$, but different $X$. The thermodynamic volumes and masses differ in such that there are high and low density branches. The partner spacetimes are related by a simple inversion of $X$, which has a fixed point at the state of maximal total entropy. We compute the compressibility at fixed total entropy and find that it diverges at the maximal entropy point. Hence a picture emerges of high and low density phases merging at this critical point., Comment: 28 pages, 6 figures; v2 - references added

Many modern data analysis problems involve inferences from streaming data. However, streaming data is not easily amenable to the standard probabilistic modeling approaches, which assume that we condition on finite data. We develop population variational Bayes, a new approach for using Bayesian modeling to analyze streams of data. It approximates a new type of distribution, the population posterior, which combines the notion of a population distribution of the data with Bayesian inference in a probabilistic model. We study our method with latent Dirichlet allocation and Dirichlet process mixtures on several large-scale data sets.

Variational inference (VI) combined with data subsampling enables approximate posterior inference over large data sets, but suffers from poor local optima. We first formulate a deterministic annealing approach for the generic class of conditionally conjugate exponential family models. This approach uses a decreasing temperature parameter which deterministically deforms the objective during the course of the optimization. A well-known drawback to this annealing approach is the choice of the cooling schedule. We therefore introduce variational tempering, a variational algorithm that introduces a temperature latent variable to the model. In contrast to related work in the Markov chain Monte Carlo literature, this algorithm results in adaptive annealing schedules. Lastly, we develop local variational tempering, which assigns a latent temperature to each data point; this allows for dynamic annealing that varies across data. Compared to the traditional VI, all proposed approaches find improved predictive likelihoods on held-out data., Comment: published version, 8 pages, 4 figures

In many developing countries, half the population lives in rural locations, where access to essentials such as school materials, mosquito nets, and medical supplies is restricted. We propose an alternative method of distribution (to standard road delivery) in which the existing mobility habits of a local population are leveraged to deliver aid, which raises two technical challenges in the areas optimisation and learning. For optimisation, a standard Markov decision process applied to this problem is intractable, so we provide an exact formulation that takes advantage of the periodicities in human location behaviour. To learn such behaviour models from sparse data (i.e., cell tower observations), we develop a Bayesian model of human mobility. Using real cell tower data of the mobility behaviour of 50,000 individuals in Ivory Coast, we find that our model outperforms the state of the art approaches in mobility prediction by at least 25% (in held-out data likelihood). Furthermore, when incorporating mobility prediction with our MDP approach, we find a 81.3% reduction in total delivery time versus routine planning that minimises just the number of participants in the solution path., Comment: Appears in Proceedings of the Twenty-Ninth Conference on Uncertainty in Artificial Intelligence (UAI2013)

Social mobilization, the ability to mobilize large numbers of people via social networks to achieve highly distributed tasks, has received significant attention in recent times. This growing capability, facilitated by modern communication technology, is highly relevant to endeavors which require the search for individuals that posses rare information or skill, such as finding medical doctors during disasters, or searching for missing people. An open question remains, as to whether in time-critical situations, people are able to recruit in a targeted manner, or whether they resort to so-called blind search, recruiting as many acquaintances as possible via broadcast communication. To explore this question, we examine data from our recent success in the U.S. State Department's Tag Challenge, which required locating and photographing 5 target persons in 5 different cities in the United States and Europe in less than 12 hours, based only on a single mug-shot. We find that people are able to consistently route information in a targeted fashion even under increasing time pressure. We derive an analytical model for global mobilization and use it to quantify the extent to which people were targeting others during recruitment. Our model estimates that approximately 1 in 3 messages were of targeted fashion during the most time-sensitive period of the challenge.This is a novel observation at such short temporal scales, and calls for opportunities for devising viral incentive schemes that provide distance- or time-sensitive rewards to approach the target geography more rapidly, with applications in multiple areas from emergency preparedness, to political mobilization., Comment: 10 pages, 11 figures (Added Supplementary Information)

The haloarchaea are aerobic, heterotrophic, photophosphorylating prokaryotes, whose supposed closest relatives and ancestors, the methanogens, are CO2-reducing, anaerobic chemolithotrophs. Using two available haloarchaeal genomes we firstly confirmed the methanogenic ancestry of the group and then investigated those individual genes in the haloarchaea that differ in their phylogenetic signal to this relationship. We found that almost half the genes, about which we can make strong statements, have bacterial ancestry and are likely a result of multiple horizontal transfer events. Futhermore their functions specifically relate to the phenotypic changes required for a chemolithotroph to become a heterotroph. If this phylogenetic relationship is correct, it implies the development of the haloarchaeal phenotype was among the most extreme changes in cellular physiology fuelled by horizontal gene transfer., Comment: 25 pages; 3 Figures