Institute Homepage
Institute Homepage EN Sign In

Publications

DEPARTMENTS

Emperical Interference

Haptic Intelligence

Modern Magnetic Systems

Perceiving Systems

Physical Intelligence

Robotic Materials

Social Foundations of Computation

Research Groups

Autonomous Vision

Autonomous Learning

Bioinspired Autonomous Miniature Robots

Dynamic Locomotion

Embodied Vision

Human Aspects of Machine Learning

Intelligent Control Systems

Learning and Dynamical Systems

Locomotion in Biorobotic and Somatic Systems

Micro, Nano, and Molecular Systems

Movement Generation and Control

Neural Capture and Synthesis

Physics for Inference and Optimization

Organizational Leadership and Diversity

Probabilistic Learning Group

Topics

Robot Learning

Conference Paper

2022

Autonomous Learning

Robotics

AI

Career

Award

Empirical Inference Technical Report International AI Safety Report Bengio, Y., Mindermann, S., Privitera, D., Besiroglu, T., Bommasani, R., Casper, S., Choi, Y., Fox, P., Garfinkel, B., Goldfarb, D., Heidari, H., Ho, A., Kapoor, S., Khalatbari, L., Longpre, S., Manning, S., Mavroudis, V., Mazeika, M., Michael, J., Newman, J., et al. (DSIT 2025/001), 2025 (Published) URL BibTeX
Safety- and Efficiency- aligned Learning Technical Report A Realistic Threat Model for Large Language Model Jailbreaks Boreiko, V., Panfilov, A., Hein, M., Geiping, J. October 2024 (Submitted)
A plethora of jailbreaking attacks have been proposed to obtain harmful responses from safety-tuned LLMs. In their original settings, these methods all largely succeed in coercing the target output, but their attacks vary substantially in fluency and computational effort. In this work, we propose a unified threat model for the principled comparison of these methods. Our threat model combines constraints in perplexity, measuring how far a jailbreak deviates from natural text, and computational budget, in total FLOPs. For the former, we build an N-gram model on 1T tokens, which, in contrast to model-based perplexity, allows for an LLM-agnostic and inherently interpretable evaluation. We adapt popular attacks to this new, realistic threat model, with which we, for the first time, benchmark these attacks on equal footing. After a rigorous comparison, we not only find attack success rates against safety-tuned modern models to be lower than previously presented but also find that attacks based on discrete optimization significantly outperform recent LLM-based attacks. Being inherently interpretable, our threat model allows for a comprehensive analysis and comparison of jailbreak attacks. We find that effective attacks exploit and abuse infrequent N-grams, either selecting N-grams absent from real-world text or rare ones, e.g. specific to code datasets.
URL BibTeX
Embodied Vision Technical Report Incremental Few-Shot Adaptation for Non-Prehensile Object Manipulation using Parallelizable Physics Simulators Baumeister, F., Mack, L., Stueckler, J. CoRR abs/2409.13228, CoRR, 2024, Submitted to IEEE International Conference on Robotics and Automation (ICRA) 2025 (Submitted)
Few-shot adaptation is an important capability for intelligent robots that perform tasks in open-world settings such as everyday environments or flexible production. In this paper, we propose a novel approach for non-prehensile manipulation which iteratively adapts a physics-based dynamics model for model-predictive control. We adapt the parameters of the model incrementally with a few examples of robot-object interactions. This is achieved by sampling-based optimization of the parameters using a parallelizable rigid-body physics simulation as dynamic world model. In turn, the optimized dynamics model can be used for model-predictive control using efficient sampling-based optimization. We evaluate our few-shot adaptation approach in several object pushing experiments in simulation and with a real robot.
URL BibTeX
Embodied Vision Technical Report Learning a Terrain- and Robot-Aware Dynamics Model for Autonomous Mobile Robot Navigation Achterhold, J., Guttikonda, S., Kreber, J. U., Li, H., Stueckler, J. CoRR abs/2409.11452, 2024, Preprint submitted to Robotics and Autonomous Systems Journal. https://arxiv.org/abs/2409.11452 (Submitted)
Mobile robots should be capable of planning cost-efficient paths for autonomous navigation. Typically, the terrain and robot properties are subject to variations. For instance, properties of the terrain such as friction may vary across different locations. Also, properties of the robot may change such as payloads or wear and tear, e.g., causing changing actuator gains or joint friction. Autonomous navigation approaches should thus be able to adapt to such variations. In this article, we propose a novel approach for learning a probabilistic, terrain- and robot-aware forward dynamics model (TRADYN) which can adapt to such variations and demonstrate its use for navigation. Our learning approach extends recent advances in meta-learning forward dynamics models based on Neural Processes for mobile robot navigation. We evaluate our method in simulation for 2D navigation of a robot with uni-cycle dynamics with varying properties on terrain with spatially varying friction coefficients. In our experiments, we demonstrate that TRADYN has lower prediction error over long time horizons than model ablations which do not adapt to robot or terrain variations. We also evaluate our model for navigation planning in a model-predictive control framework and under various sources of noise. We demonstrate that our approach yields improved performance in planning control-efficient paths by taking robot and terrain properties into account.
BibTeX
Safety- and Efficiency- aligned Learning Technical Report AI Risk Management Should Incorporate Both Safety and Security Qi, X., Huang, Y., Zeng, Y., Debenedetti, E., Geiping, J., He, L., Huang, K., Madhushani, U., Sehwag, V., Shi, W., Wei, B., Xie, T., Chen, D., Chen, P., Ding, J., Jia, R., Ma, J., Narayanan, A., Su, W. J., Wang, M., et al. 2024 BibTeX
Safety- and Efficiency- aligned Learning Technical Report Coercing LLMs to do and reveal (almost) anything Geiping, J., Stein, A., Shu, M., Saifullah, K., Wen, Y., Goldstein, T. 2024 (Submitted) URL BibTeX
Safety- and Efficiency- aligned Learning Technical Report Generating Potent Poisons and Backdoors from Scratch with Guided Diffusion Souri, H., Bansal, A., Kazemi, H., Fowl, L., Saha, A., Geiping, J., Wilson, A. G., Chellappa, R., Goldstein, T., Goldblum, M. 2024 (Submitted) URL BibTeX
Empirical Inference Technical Report Synchronizing Machine Learning Algorithms, Realtime Robotic Control and Simulated Environment with o80 Berenz, V., Widmaier, F., Guist, S., Schölkopf, B., Büchler, D. Robot Software Architectures Workshop (RSA) 2023, ICRA, 2023 (Published)
Robotic applications require the integration of various modalities, encompassing perception, control of real robots and possibly the control of simulated environments. While the state-of-the-art robotic software solutions such as ROS 2 provide most of the required features, flexible synchronization between algorithms, data streams and control loops can be tedious. o80 is a versatile C++ framework for robotics which provides a shared memory model and a command framework for real-time critical systems. It enables expert users to set up complex robotic systems and generate Python bindings for scientists. o80's unique feature is its flexible synchronization between processes, including the traditional blocking commands and the novel ``bursting mode'', which allows user code to control the execution of the lower process control loop. This makes it particularly useful for setups that mix real and simulated environments.
arxiv poster URL BibTeX
Dynamic Locomotion Technical Report Learning Plastic Matching of Robot Dynamics in Closed-Loop Central Pattern Generators: Data Ruppert, F., Badri-Spröwitz, A. Edmond, May 2022 (Published) DOI URL BibTeX
Dynamic Locomotion Physical Intelligence Technical Report Data for BirdBot Achieves Energy-Efficient Gait with Minimal Control Using Avian-Inspired Leg Clutching Badri-Spröwitz, A., Sarvestani, A. A., Sitti, M., Daley, M. A. Edmond, March 2022 DOI BibTeX
Embodied Vision Technical Report Observability Analysis of Visual-Inertial Odometry with Online Calibration of Velocity-Control Based Kinematic Motion Models Li, H., Stueckler, J. abs/2204.06651, CoRR/arxiv, 2022 (Published)
In this paper, we analyze the observability of the visual-inertial odometry (VIO) using stereo cameras with a velocity-control based kinematic motion model. Previous work shows that in general case the global position and yaw are unobservable in VIO system, additionally the roll and pitch become also unobservable if there is no rotation. We prove that by integrating a planar motion constraint roll and pitch become observable. We also show that the parameters of the motion model are observable.
URL BibTeX
Rationality Enhancement Technical Report Toward a Science of Effective Well-Doing Lieder, F., Prentice, M., Corwin-Renner, E. May 2021
Well-doing, broadly construed, encompasses acting and thinking in ways that contribute to humanity’s flourishing in the long run. This often takes the form of setting a prosocial goal and pursuing it over an extended period of time. To set and pursue goals in a way that is extremely beneficial for humanity (effective well-doing), people often have to employ critical thinking and far-sighted, rational decision-making in the service of the greater good. To promote effective well-doing, we need to better understand its determinants and psychological mechanisms, as well as the barriers to effective well-doing and how they can be overcome. In this article, we introduce a taxonomy of different forms of well-doing and introduce a conceptual model of the cognitive mechanisms of effective well-doing. We view effective well-doing as the upper end of a moral continuum whose lower half comprises behaviors that are harmful to humanity (ill-doing), and we argue that the capacity for effective well-doing has to be developed through personal growth (e.g., learning how to pursue goals effectively). Research on these phenomena has so far been scattered across numerous disconnected literatures from multiple disciplines. To bring these communities together, we call for the establishment of a transdisciplinary research field focussed on understanding and promoting effective well-doing and personal growth as well as understanding and reducing ill-doing. We define this research field in terms of its goals and questions. We review what is already known about these questions in different disciplines and argue that laying the scientific foundation for promoting effective well-doing is one of the most valuable contributions that the behavioral sciences can make in the 21st century.
Preprint BibTeX
Rationality Enhancement Technical Report Optimal To-Do List Gamification Stojcheski, J., Felso, V., Lieder, F. ArXiv Preprint, August 2020 (Published)
What should I work on first? What can wait until later? Which projects should I prioritize and which tasks are not worth my time? These are challenging questions that many people face every day. People’s intuitive strategy is to prioritize their immediate experience over the long-term consequences. This leads to procrastination and the neglect of important long-term projects in favor of seemingly urgent tasks that are less important. Optimal gamification strives to help people overcome these problems by incentivizing each task by a number of points that communicates how valuable it is in the long-run. Unfortunately, computing the optimal number of points with standard dynamic programming methods quickly becomes intractable as the number of a person’s projects and the number of tasks required by each project increase. Here, we introduce and evaluate a scalable method for identifying which tasks are most important in the long run and incentivizing each task according to its long-term value. Our method makes it possible to create to-do list gamification apps that can handle the size and complexity of people’s to-do lists in the real world.
DOI URL BibTeX
Intelligent Control Systems Technical Report Identifying Causal Structure in Dynamical Systems Baumann, D., Solowjow, F., Johansson, K. H., Trimpe, S. 2020 arXiv BibTeX
Technical Report Mediating between human driver and automation: state-of-the artand knowledge gaps : D1.1 of the H2020 project MEDIATOR Christoph, M., Cleij, D., Ahlström, H., Bakker, B., van Egmond, R., van Grondelle, E., de Ridder, H. Delft University of Technology, Delft, The Netherlands, 2019 BibTeX
Statistical Learning Theory Technical Report NEWMA: a new method for scalable model-free online change-point detection Keriven, N., Garreau, D., Poli, I. 2018 URL BibTeX
Embodied Vision Technical Report Detailed Dense Inference with Convolutional Neural Networks via Discrete Wavelet Transform Ma, L., Stueckler, J., Wu, T., Cremers, D. arxiv, 2018, arXiv:1808.01834 BibTeX
Technical Report A review on the effects of motion characteristics on motion sickness incidence Nooij, S. 197(197), Max Planck Institute for Biological Cybernetics, Tübingen, Germany, 2018
{Many forms of transport evoke symptoms of motion sickness (MS) in susceptible passengers. Symptoms include stomach awareness, palor, headache, sweating dizziness and nausea, and are caused by particular vehicle motions. The aim of this review is to summarize the literature on the relationship between motion characteristics and motion sickness. For example, which types of motions are most provocative, what is the effect of motion frequency and amplitude, and how can we predict whether a certain motion will be provocative. This review was carried out within the framework of the CORINNE project, which investigates the relationship between vibration characteristics in helicopters and the discomfort they cause on the passengers. The ISO 2631-11 proposes a method of predicting motion sickness incidence from a given motion profile, but only takes into account the vertical motion. It is to be expected that the prediction will not be optimal for helicopter trajectories, as motions in other degrees of freedom may also contribute. One of the project aims, therefore is to verify whether the current ISO method is valid, or whether it can be improved by taking motion in multiple degrees of freedom into account. In the following, we will first summarize the prediction method proposed in ISO 2631-1 and then summarize available literature on the effects of motions in other degrees of freedom. This review can then guide further research for the specific case of helicopter flight.}
BibTeX
Autonomous Motion Intelligent Control Systems Technical Report Supplemental material for ’Communication Rate Analysis for Event-based State Estimation’ Ebner, S., Trimpe, S. Max Planck Institute for Intelligent Systems, January 2016 PDF BibTeX
Autonomous Motion Intelligent Control Systems Technical Report Distributed Event-based State Estimation Trimpe, S. Max Planck Institute for Intelligent Systems, November 2015
An event-based state estimation approach for reducing communication in a networked control system is proposed. Multiple distributed sensor-actuator-agents observe a dynamic process and sporadically exchange their measurements and inputs over a bus network. Based on these data, each agent estimates the full state of the dynamic system, which may exhibit arbitrary inter-agent couplings. Local event-based protocols ensure that data is transmitted only when necessary to meet a desired estimation accuracy. This event-based scheme is shown to mimic a centralized Luenberger observer design up to guaranteed bounds, and stability is proven in the sense of bounded estimation errors for bounded disturbances. The stability result extends to the distributed control system that results when the local state estimates are used for distributed feedback control. Simulation results highlight the benefit of the event-based approach over classical periodic ones in reducing communication requirements.
arXiv BibTeX
Empirical Inference Technical Report Cosmology from Cosmic Shear with DES Science Verification Data Abbott, T., Abdalla, F. B., Allam, S., Amara, A., Annis, J., Armstrong, R., Bacon, D., Banerji, M., Bauer, A. H., Baxter, E., others, arXiv preprint arXiv:1507.05552, 2015 (Published) URL BibTeX
Empirical Inference Technical Report The DES Science Verification Weak Lensing Shear Catalogs Jarvis, M., Sheldon, E., Zuntz, J., Kacprzak, T., Bridle, S. L., Amara, A., Armstrong, R., Becker, M. R., Bernstein, G. M., Bonnett, C., others, arXiv preprint arXiv:1507.05603, 2015 (Published) URL BibTeX
Perceiving Systems Technical Report Model transport: towards scalable transfer learning on manifolds - supplemental material Freifeld, O., Hauberg, S., Black, M. J. (9), April 2014
This technical report is complementary to "Model Transport: Towards Scalable Transfer Learning on Manifolds" and contains proofs, explanation of the attached video (visualization of bases from the body shape experiments), and high-resolution images of select results of individual reconstructions from the shape experiments. It is identical to the supplemental mate- rial submitted to the Conference on Computer Vision and Pattern Recognition (CVPR 2014) on November 2013.
PDF BibTeX
Perceiving Systems Technical Report Puppet Flow Zuffi, S., Black, M. J. (7), Max Planck Institute for Intelligent Systems, October 2013
We introduce Puppet Flow (PF), a layered model describing the optical flow of a person in a video sequence. We consider video frames composed by two layers: a foreground layer corresponding to a person, and background. We model the background as an affine flow field. The foreground layer, being a moving person, requires reasoning about the articulated nature of the human body. We thus represent the foreground layer with the Deformable Structures model (DS), a parametrized 2D part-based human body representation. We call the motion field defined through articulated motion and deformation of the DS model, a Puppet Flow. By exploiting the DS representation, Puppet Flow is a parametrized optical flow field, where parameters are the person's pose, gender and body shape.
pdf BibTeX
Autonomous Motion Technical Report Learning and Optimization with Submodular Functions Sankaran, B., Ghazvininejad, M., He, X., Kale, D., Cohen, L. ArXiv, May 2013
In many naturally occurring optimization problems one needs to ensure that the definition of the optimization problem lends itself to solutions that are tractable to compute. In cases where exact solutions cannot be computed tractably, it is beneficial to have strong guarantees on the tractable approximate solutions. In order operate under these criterion most optimization problems are cast under the umbrella of convexity or submodularity. In this report we will study design and optimization over a common class of functions called submodular functions. Set functions, and specifically submodular set functions, characterize a wide variety of naturally occurring optimization problems, and the property of submodularity of set functions has deep theoretical consequences with wide ranging applications. Informally, the property of submodularity of set functions concerns the intuitive principle of diminishing returns. This property states that adding an element to a smaller set has more value than adding it to a larger set. Common examples of submodular monotone functions are entropies, concave functions of cardinality, and matroid rank functions; non-monotone examples include graph cuts, network flows, and mutual information. In this paper we will review the formal definition of submodularity; the optimization of submodular functions, both maximization and minimization; and finally discuss some applications in relation to learning and reasoning using submodular functions.
arxiv URL BibTeX
Perceiving Systems Technical Report A Quantitative Analysis of Current Practices in Optical Flow Estimation and the Principles Behind Them Sun, D., Roth, S., Black, M. J. (CS-10-03), Brown University, Department of Computer Science, January 2013 pdf BibTeX
Empirical Inference Probabilistic Numerics Technical Report Animating Samples from Gaussian Distributions Hennig, P. (8), Max Planck Institute for Intelligent Systems, Tübingen, Germany, 2013 PDF BibTeX
Empirical Inference Technical Report Maximizing Kepler science return per telemetered pixel: Detailed models of the focal plane in the two-wheel era Hogg, D. W., Angus, R., Barclay, T., Dawson, R., Fergus, R., Foreman-Mackey, D., Harmeling, S., Hirsch, M., Lang, D., Montet, B. T., Schiminovich, D., Schölkopf, B. arXiv:1309.0653, 2013 (Published) URL BibTeX
Empirical Inference Technical Report Maximizing Kepler science return per telemetered pixel: Searching the habitable zones of the brightest stars Montet, B. T., Angus, R., Barclay, T., Dawson, R., Fergus, R., Foreman-Mackey, D., Harmeling, S., Hirsch, M., Hogg, D. W., Lang, D., Schiminovich, D., Schölkopf, B. arXiv:1309.0654, 2013 (Published) URL BibTeX
Perceiving Systems Technical Report Coregistration: Supplemental Material Hirshberg, D., Loper, M., Rachlin, E., Black, M. J. (No. 4), Max Planck Institute for Intelligent Systems, October 2012 pdf BibTeX
Perceiving Systems Technical Report Lie Bodies: A Manifold Representation of 3D Human Shape. Supplemental Material Freifeld, O., Black, M. J. (No. 5), Max Planck Institute for Intelligent Systems, October 2012 pdf BibTeX
Perceiving Systems Technical Report MPI-Sintel Optical Flow Benchmark: Supplemental Material Butler, D. J., Wulff, J., Stanley, G. B., Black, M. J. (No. 6), Max Planck Institute for Intelligent Systems, October 2012 pdf BibTeX
Empirical Inference Technical Report High Gamma-Power Predicts Performance in Brain-Computer Interfacing Grosse-Wentrup, M., Schölkopf, B. (3), Max-Planck-Institut für Intelligente Systeme, Tübingen, February 2012
Subjects operating a brain-computer interface (BCI) based on sensorimotor rhythms exhibit large variations in performance over the course of an experimental session. Here, we show that high-frequency gamma-oscillations, originating in fronto-parietal networks, predict such variations on a trial-to-trial basis. We interpret this nding as empirical support for an in uence of attentional networks on BCI-performance via modulation of the sensorimotor rhythm.
PDF BibTeX
Empirical Inference Technical Report Non-stationary Correction of Optical Aberrations Schuler, C., Hirsch, M., Harmeling, S., Schölkopf, B. (1), Max Planck Institute for Intelligent Systems, Tübingen, Germany, May 2011
Taking a sharp photo at several megapixel resolution traditionally relies on high grade lenses. In this paper, we present an approach to alleviate image degradations caused by imperfect optics. We rely on a calibration step to encode the optical aberrations in a space-variant point spread function and obtain a corrected image by non-stationary deconvolution. By including the Bayer array in our image formation model, we can perform demosaicing as part of the deconvolution.
PDF BibTeX
Empirical Inference Technical Report PAC-Bayesian Analysis of Martingales and Multiarmed Bandits Seldin, Y., Laviolette, F., Shawe-Taylor, J., Peters, J., Auer, P. Max Planck Institute for Biological Cybernetics, Tübingen, Germany, May 2011
We present two alternative ways to apply PAC-Bayesian analysis to sequences of dependent random variables. The first is based on a new lemma that enables to bound expectations of convex functions of certain dependent random variables by expectations of the same functions of independent Bernoulli random variables. This lemma provides an alternative tool to Hoeffding-Azuma inequality to bound concentration of martingale values. Our second approach is based on integration of Hoeffding-Azuma inequality with PAC-Bayesian analysis. We also introduce a way to apply PAC-Bayesian analysis in situation of limited feedback. We combine the new tools to derive PAC-Bayesian generalization and regret bounds for the multiarmed bandit problem. Although our regret bound is not yet as tight as state-of-the-art regret bounds based on other well-established techniques, our results significantly expand the range of potential applications of PAC-Bayesian analysis and introduce a new analysis tool to reinforcement learning and many other fields, where martingales and limited feedback are encountered.
PDF Web BibTeX
Empirical Inference Technical Report Multiple Kernel Learning: A Unifying Probabilistic Viewpoint Nickisch, H., Seeger, M. Max Planck Institute for Biological Cybernetics, March 2011
We present a probabilistic viewpoint to multiple kernel learning unifying well-known regularised risk approaches and recent advances in approximate Bayesian inference relaxations. The framework proposes a general objective function suitable for regression, robust regression and classification that is lower bound of the marginal likelihood and contains many regularised risk approaches as special cases. Furthermore, we derive an efficient and provably convergent optimisation algorithm.
Web BibTeX
Empirical Inference Technical Report Multiple testing, uncertainty and realistic pictures Langovoy, M., Wittich, O. (2011-004), EURANDOM, Technische Universiteit Eindhoven, January 2011
We study statistical detection of grayscale objects in noisy images. The object of interest is of unknown shape and has an unknown intensity, that can be varying over the object and can be negative. No boundary shape constraints are imposed on the object, only a weak bulk condition for the object's interior is required. We propose an algorithm that can be used to detect grayscale objects of unknown shapes in the presence of nonparametric noise of unknown level. Our algorithm is based on a nonparametric multiple testing procedure. We establish the limit of applicability of our method via an explicit, closed-form, non-asymptotic and nonparametric consistency bound. This bound is valid for a wide class of nonparametric noise distributions. We achieve this by proving an uncertainty principle for percolation on nite lattices.
PDF BibTeX
Empirical Inference Technical Report Nonconvex proximal splitting: batch and incremental algorithms Sra, S. (2), Max Planck Institute for Intelligent Systems, Tübingen, Germany, 2011
Within the unmanageably large class of nonconvex optimization, we consider the rich subclass of nonsmooth problems having composite objectives (this includes the extensively studied convex, composite objective problems as a special case). For this subclass, we introduce a powerful, new framework that permits asymptotically non-vanishing perturbations. In particular, we develop perturbation-based batch and incremental (online like) nonconvex proximal splitting algorithms. To our knowledge, this is the rst time that such perturbation-based nonconvex splitting algorithms are being proposed and analyzed. While the main contribution of the paper is the theoretical framework, we complement our results by presenting some empirical results on matrix factorization.
PDF BibTeX
Empirical Inference Technical Report Computationally efficient algorithms for statistical image processing: Implementation in R Langovoy, M., Wittich, O. (2010-053), EURANDOM, Technische Universiteit Eindhoven, December 2010
In the series of our earlier papers on the subject, we proposed a novel statistical hy- pothesis testing method for detection of objects in noisy images. The method uses results from percolation theory and random graph theory. We developed algorithms that allowed to detect objects of unknown shapes in the presence of nonparametric noise of unknown level and of un- known distribution. No boundary shape constraints were imposed on the objects, only a weak bulk condition for the object's interior was required. Our algorithms have linear complexity and exponential accuracy. In the present paper, we describe an implementation of our nonparametric hypothesis testing method. We provide a program that can be used for statistical experiments in image processing. This program is written in the statistical programming language R.
PDF BibTeX
Empirical Inference Technical Report Fast Convergent Algorithms for Expectation Propagation Approximate Bayesian Inference Seeger, M., Nickisch, H. Max Planck Institute for Biological Cybernetics, December 2010
We propose a novel algorithm to solve the expectation propagation relaxation of Bayesian inference for continuous-variable graphical models. In contrast to most previous algorithms, our method is provably convergent. By marrying convergent EP ideas from (Opper&Winther 05) with covariance decoupling techniques (Wipf&Nagarajan 08, Nickisch&Seeger 09), it runs at least an order of magnitude faster than the most commonly used EP solver.
Web BibTeX
Empirical Inference Technical Report A PAC-Bayesian Analysis of Graph Clustering and Pairwise Clustering Seldin, Y. Max Planck Institute for Biological Cybernetics, Tübingen, Germany, September 2010
We formulate weighted graph clustering as a prediction problem: given a subset of edge weights we analyze the ability of graph clustering to predict the remaining edge weights. This formulation enables practical and theoretical comparison of different approaches to graph clustering as well as comparison of graph clustering with other possible ways to model the graph. We adapt the PAC-Bayesian analysis of co-clustering (Seldin and Tishby, 2008; Seldin, 2009) to derive a PAC-Bayesian generalization bound for graph clustering. The bound shows that graph clustering should optimize a trade-off between empirical data fit and the mutual information that clusters preserve on the graph nodes. A similar trade-off derived from information-theoretic considerations was already shown to produce state-of-the-art results in practice (Slonim et al., 2005; Yom-Tov and Slonim, 2009). This paper supports the empirical evidence by providing a better theoretical foundation, suggesting formal generalization guarantees, and offering a more accurate way to deal with finite sample issues. We derive a bound minimization algorithm and show that it provides good results in real-life problems and that the derived PAC-Bayesian bound is reasonably tight.
PDF Web BibTeX
Empirical Inference Technical Report Robust nonparametric detection of objects in noisy images Langovoy, M., Wittich, O. (2010-049), EURANDOM, Technische Universiteit Eindhoven, September 2010
We propose a novel statistical hypothesis testing method for detection of objects in noisy images. The method uses results from percolation theory and random graph theory. We present an algorithm that allows to detect objects of unknown shapes in the presence of nonparametric noise of unknown level and of unknown distribution. No boundary shape constraints are imposed on the object, only a weak bulk condition for the object's interior is required. The algorithm has linear complexity and exponential accuracy and is appropriate for real-time systems. In this paper, we develop further the mathematical formalism of our method and explore im- portant connections to the mathematical theory of percolation and statistical physics. We prove results on consistency and algorithmic complexity of our testing procedure. In addition, we address not only an asymptotic behavior of the method, but also a nite sample performance of our test.
PDF BibTeX
Empirical Inference Technical Report Sparse nonnegative matrix approximation: new formulations and algorithms Tandon, R., Sra, S. (193), Max Planck Institute for Biological Cybernetics, Tübingen, Germany, September 2010
We introduce several new formulations for sparse nonnegative matrix approximation. Subsequently, we solve these formulations by developing generic algorithms. Further, to help selecting a particular sparse formulation, we briefly discuss the interpretation of each formulation. Finally, preliminary experiments are presented to illustrate the behavior of our formulations and algorithms.
PDF BibTeX
Empirical Inference Technical Report Cooperative Cuts for Image Segmentation Jegelka, S., Bilmes, J. (UWEETR-1020-0003), University of Washington, Washington DC, USA, August 2010
We propose a novel framework for graph-based cooperative regularization that uses submodular costs on graph edges. We introduce an efficient iterative algorithm to solve the resulting hard discrete optimization problem, and show that it has a guaranteed approximation factor. The edge-submodular formulation is amenable to the same extensions as standard graph cut approaches, and applicable to a range of problems. We apply this method to the image segmentation problem. Specifically, Here, we apply it to introduce a discount for homogeneous boundaries in binary image segmentation on very difficult images, precisely, long thin objects and color and grayscale images with a shading gradient. The experiments show that significant portions of previously truncated objects are now preserved.
Web BibTeX
Empirical Inference Technical Report Fast algorithms for total-variationbased optimization Barbero, A., Sra, S. (194), Max Planck Institute for Biological Cybernetics, Tübingen, Germany, August 2010
We derive a number of methods to solve efficiently simple optimization problems subject to a totalvariation (TV) regularization, under different norms of the TV operator and both for the case of 1-dimensional and 2-dimensional data. In spite of the non-smooth, non-separable nature of the TV terms considered, we show that a dual formulation with strong structure can be derived. Taking advantage of this structure we develop adaptions of existing algorithms from the optimization literature, resulting in efficient methods for the problem at hand. Experimental results show that for 1-dimensional data the proposed methods achieve convergence within good accuracy levels in practically linear time, both for L1 and L2 norms. For the more challenging 2-dimensional case a performance of order O(N2 log2 N) for N x N inputs is achieved when using the L2 norm. A final section suggests possible extensions and lines of further work.
PDF BibTeX
Empirical Inference Technical Report Large Scale Variational Inference and Experimental Design for Sparse Generalized Linear Models Seeger, M., Nickisch, H. Max Planck Institute for Biological Cybernetics, August 2010
Many problems of low-level computer vision and image processing, such as denoising, deconvolution, tomographic reconstruction or super-resolution, can be addressed by maximizing the posterior distribution of a sparse linear model (SLM). We show how higher-order Bayesian decision-making problems, such as optimizing image acquisition in magnetic resonance scanners, can be addressed by querying the SLM posterior covariance, unrelated to the density's mode. We propose a scalable algorithmic framework, with which SLM posteriors over full, high-resolution images can be approximated for the first time, solving a variational optimization problem which is convex iff posterior mode finding is convex. These methods successfully drive the optimization of sampling trajectories for real-world magnetic resonance imaging through Bayesian experimental design, which has not been attempted before. Our methodology provides new insight into similarities and differences between sparse reconstruction and approximate Bayesian inference, and has important implications for compressive sensing of real-world images.
Web BibTeX
Empirical Inference Technical Report Gaussian Mixture Modeling with Gaussian Process Latent Variable Models Nickisch, H., Rasmussen, C. Max Planck Institute for Biological Cybernetics, June 2010
Density modeling is notoriously difficult for high dimensional data. One approach to the problem is to search for a lower dimensional manifold which captures the main characteristics of the data. Recently, the Gaussian Process Latent Variable Model (GPLVM) has successfully been used to find low dimensional manifolds in a variety of complex data. The GPLVM consists of a set of points in a low dimensional latent space, and a stochastic map to the observed space. We show how it can be interpreted as a density model in the observed space. However, the GPLVM is not trained as a density model and therefore yields bad density estimates. We propose a new training strategy and obtain improved generalisation performance and better density estimates in comparative evaluations on several benchmark data sets.
Web BibTeX
Empirical Inference Technical Report Generalized Proximity and Projection with Norms and Mixed-norms Sra, S. (192), Max Planck Institute for Biological Cybernetics, Tübingen, Germany, May 2010
We discuss generalized proximity operators (GPO) and their associated generalized projection problems. On inputs of size n, we show how to efficiently apply GPOs and generalized projections for separable norms and distance-like functions to accuracy e in O(n log(1/e)) time. We also derive projection algorithms that run theoretically in O(n log n log(1/e)) time but can for suitable parameter ranges empirically outperform the O(n log(1/e)) projection method. The proximity and projection tasks are either separable, and solved directly, or are reduced to a single root-finding step. We highlight that as a byproduct, our analysis also yields an O(n log(1/e)) (weakly linear-time) procedure for Euclidean projections onto the l1;1-norm ball; previously only an O(n log n) method was known. We provide empirical evaluation to illustrate the performance of our methods, noting that for the l1;1-norm projection, our implementation is more than two orders of magnitude faster than the previously known method.
PDF BibTeX
Empirical Inference Technical Report Cooperative Cuts: Graph Cuts with Submodular Edge Weights Jegelka, S., Bilmes, J. (189), Max Planck Institute for Biological Cybernetics, Tuebingen, Germany, March 2010
We introduce a problem we call Cooperative cut, where the goal is to find a minimum-cost graph cut but where a submodular function is used to define the cost of a subsets of edges. That means, the cost of an edge that is added to the current cut set C depends on the edges in C. This generalization of the cost in the standard min-cut problem to a submodular cost function immediately makes the problem harder. Not only do we prove NP hardness even for nonnegative submodular costs, but also show a lower bound of Omega(|V|^(1/3)) on the approximation factor for the problem. On the positive side, we propose and compare four approximation algorithms with an overall approximation factor of min { |V|/2, |C*|, O( sqrt(|E|) log |V|), |P_max|}, where C* is the optimal solution, and P_max is the longest s, t path across the cut between given s, t. We also introduce additional heuristics for the problem which have attractive properties from the perspective of practical applications and implementations in that existing fast min-cut libraries may be used as subroutines. Both our approximation algorithms, and our heuristics, appear to do well in practice.
PDF BibTeX
Empirical Inference Technical Report Information-theoretic inference of common ancestors Steudel, B., Ay, N. Computing Research Repository (CoRR), abs/1010.5720:18, 2010 Web BibTeX