CMU talk: Fourier Theoretic Probabilistic Inference over Permutations

Speaker: Jonathan Huang (RI @ CMU)

Venue: NSH 1507

Date: Monday, April 6, 2009

Time: 12:00 noon

Title:

Fourier Theoretic Probabilistic Inference over Permutations

Abstract:

Permutations are ubiquitous in many real-world problems, such as voting, ranking, and data association. Representing uncertainty over permutations, however, is challenging, since there are $n!$ possibilities, and common factorized probability distribution representations, such as graphical models, are inefficient due to the mutual exclusivity constraints that are typically associated with permutations.

I will talk about a recent approach for probabilistic reasoning with permutations based on the idea of approximating distributions using their low-frequency Fourier components. Maintaining the appropriate set of low-frequency Fourier terms corresponds to maintaining matrices of simple marginal probabilities which summarize the underlying distribution. Using these intuitions, I will show how to derive the Fourier coefficients of a variety of probabilistic models which arise in practice and that many useful models are either well-approximated or exactly represented by low-frequency (and in many cases, sparse) Fourier coefficient matrices.

In addition to showing that Fourier representations are both compact and intuitive, I will show how to cast common probabilistic inference operations in the Fourier domain, including marginalization, conditioning on evidence, and factoring based on probabilistic independence.

From the theoretical side, our work has tackled several problems in understanding the consequences of the bandlimiting approximation. On this front, I will present illuminating results about the nature of error propagation in the Fourier domain and propose methods for mitigating their effects.

Finally I will demonstrate the approach on several real datasets and show that our methods, in addition to being well-founded theoretically, are also scalable and provide superior results in practice.

joint work with Carlos Guestrin, Leonidas Guibas and Xiaoye Jiang

CMU RI Thesis Proposal: Distributed Algorithms for Probabilistic Inference and Learning

Date: 16 January 2009

Time: 12:00 p.m.

Place: Newell Simon Hall 1507

Type: Thesis Proposal

Who:  Stanislav Funiak

Topic: Distributed Algorithms for Probabilistic Inference and Learning

Abstract:

Probabilistic inference and learning problems arise naturally in distributed systems such as sensor networks, teams of mobile robots, and recommendation systems. In these systems, the data resides at multiple distributed locations, and the network nodes need to collaborate, in order to perform the inference or learning task.

This thesis has three thrusts. First, we propose distributed implementations of several state-of-the-art centralized inference algorithms. Our solutions address challenges, such as effective MAP estimation, scheduling of messages in loopy belief propagation, and assumed density filtering.

Many algorithms for probabilistic inference are described by graphical models, such region graphs or junction trees. These graphical models, together with the update schedule, entirely determine the behavior of the inference algorithm in a centralized settings. Yet, in distributed settings, the graphical model crucially interacts with the physical network and determines properties, such as robustness or communication complexity. In this thesis, we propose a unified view where the graphical model and its placement is optimized jointly to match both the network and the probabilistic model. In this manner, our distributed algorithms will not only attain accurate solutions, but will also have a low message complexity.

Recent advances in peer-to-peer networks offer interesting opportunities for learning latent variable models for collaborative filtering. Peer-to-peer networks simplify many aspects of distributed learning, but open an interesting challenge of supporting recommendation queries with stale local models. We propose a pull-based approach that updates the model parameters, in order to minimize its regret with respect to the optimal set of recommendations.

We demonstrate our algorithms on real-world applications in large-scale modular robot localization, camera networks and movie recommendation systems. We demonstrate that our algorithms scale to large networks and provide improved robustness and convergence properties.

Full Text - http://www.cs.cmu.edu/~sfuniak/pubs/proposal.pdf

CMU talk: Kernelized Sorting

Speaker: Le Song
Title: Kernelized Sorting
Date: Monday September 22

Abstract:
Matching pairs of objects is a fundamental operation of unsupervised learning. For instance, we might want to match a photo with a textual description of a person. In those cases it is desirable to have a compatibility function which determines how one set may be translated into the other. For many such instances we may be able to design a compatibility score based on prior knowledge or to observe one based on the co-occurrence of such objects.

In some cases, however, such a match may not exist or it may not be given to us beforehand. That is, while we may have a good understanding of two sources, we may not understand the mapping between the two spaces. For instance, we might have two collections of documents purportedly covering the same content, written in two different languages. Can we determine the correspondence between these two sets of documents without using a dictionary?

We will present a method which is able to perform such matching WITHOUT the need of a cross-domain similarity measure and we shall show that if such measures exist it generalizes normal sorting. Our method relies on the fact that one may estimate the dependence between sets of random variables even without knowing the cross-domain mapping. Various criteria are available. We choose the Hilbert Schmidt Independence Criterion between two sets and we maximize over the permutation group to find a good match. As a side-effect we obtain an explicit representation of the covariance.

We will demonstrate this kernelized sorting using various examples, including image layout, image matching, data attribute matching and multilingual document matching.

FRC Seminar: Stingray and Daredevil: High-Speed Teleoperation and All-Weather Perception for Small UGVs

Speaker: Brian Yamauchi, Lead Roboticist, iRobot Research

Abstract:

The mission of the iRobot Research Group is to conduct applied research to develop and integrate new technologies for iRobot products. In this talk, I will describe two ongoing research projects aimed at solving key problems in mobile robotics -- teleoperating UGVs at high speeds through urban environments (Stingray) -- and navigating autonomously in poor weather and detecting obstacles through foliage (Daredevil).

For Stingray, we have partnered with Chatten Associates to provide immersive telepresence for small UGVs using the Chatten Head-Aimed Remote Viewer (HARV). We have controlled the iRobot Warrior UGV and a high-speed 1/5-scale gas-powered radio-controlled car using the HARV. We will be adding driver assist behaviors to aid the operator in driving at high speeds.

For Daredevil, we are developing an all-weather perception payload for the PackBot that integrates ultra wideband (UWB) radar, LIDAR, and stereo vision. In initial experiments, we have demonstrated that UWB radar can detect obstacles through precipitation, smoke/fog, and sparse-to-moderate foliage. The payload will fuse the low-resolution UWB radar data with high-resolution range data from LIDAR and stereo vision. This will enable the PackBot to perform obstacle avoidance, waypoint navigation, path planning, and autonomous exploration in adverse weather and through foliage.

Speaker Bio:

Dr. Brian Yamauchi is a Lead Roboticist with iRobot's Research Group. He has been conducting robotics research and development for the last 19 years. He is the Principal Investigator for the Daredevil and Stingray Projects, both funded by the US Army Tank-Automotive Research, Development, and Engineering Center (TARDEC). At iRobot, he has conducted research in mobile robot navigation and mapping, autonomous vehicles, heterogeneous mobile robot teams, robotic casualty extraction, UAV/UGV collaboration, and hybrid UAV/UGVs. Prior to joining iRobot, he conducted robotics research at the Naval Research Laboratory, the Jet Propulsion Laboratory, Kennedy Space Center, and the Institute for the Study of Learning and Expertise. He earned his BS in Applied Math/Computer Science at Carnegie Mellon University, his MS in Computer Science at the University of Rochester, and his Ph.D. in Computer Science from Case Western Reserve University.

VASC Seminar: Free Space computation using Stochastic Occupancy Grids and Dynamic Programming

Hernán Badino
Goethe Frankfurt University (Germany)
Monday March 31 @ 3:30pm

Abstract--The computation of free space available in an environment is an essential task for many intelligent automotive and robotic applications. In this talk, I propose a new approach, which builds a stochastic occupancy grid to address the free space problem as a dynamic programming task. Stereo measurements are integrated over time reducing disparity uncertainty. These integrated measurements are entered into an occupancy grid, taking into account the noise properties of the measurements. In order to cope with real-time requirements of the application, three occupancy grid types are proposed. Their applicabilities and implementations are also discussed. Experimental results with real stereo sequences show the robustness and accuracy of the method. The current implementation of the method runs on off-the-shelf hardware at 20 Hz.

Bio--Hernán Badino received his degree of Engineer from the National Technological University, Córdoba, Argentina, in 2002. He is at the moment presenting his doctoral thesis at the J. W. Goethe Frankfurt University, Germany. Mr. Badino has worked during his PhD. D with the Image Based Environment Perception Group at Daimler AG, in Stuttgart, Germany. He is currently member of the Visual Sensorics and Information Processing Group, at the Frankfurt University, engaged in a project of camera-based urban traffic sensing for driver assistance systems. Mr. Badino particular research interests in the area of computer vision include the computation of ego-motion from sequences of stereo images and the development of stereo vision algorithms for the real-time detection and tracking of static and moving objects for automotive applications.

VASC Seminar: Toward a Perceptual Space for Reflectance

Title: Toward a Perceptual Space for Reflectance
Speaker: Sameer Agarwal

Location: NSH 1507, Univ. of Washington
Time: 3:30pm Monday, 24 March

Abstract -- As we make progress in measuring and modeling reflectance, it is also important that we develop a better understanding of how the human visual system perceives the reflection of light. Such a development not only has implications for efficient image synthesis, but also for computer vision where an understanding of reflectance perception will give us insight into the priors and constraints used by humans to solve various shading related problems, e.g., shape from shading and object recognition over variable and unknown lighting.

In this talk I will present a study of the perception of reflectance. I will argue that our methodology based on paired comparisons is better suited for capturing human perception and is less susceptible to experimental errors than previously used methods. The analysis of paired comparisons required the development of a new data analysis tool. In the second part of the talk I will present a new multidimensional scaling algorithm for analyzing paired comparisons. Based on semi-definite programming, this algorithm is a more general and efficient replacement for the widely used Non-metric MDS algorithm.

Using this algorithm we obtain a perceptual embedding of BRDFs from the MIT/MERL Database. This embedding, constructed purely from psychophysical data, exhibits some striking correlations with the material appearance standards that have been developed independently in the paper and paint industries. Finally, I will describe a novel perceptual interpolation scheme that uses this embedding to provide the user with an intuitive interface for navigating the space of reflectances and constructing new ones.

CMU RI Seminar: Perceiving the Actions and Intentions of Others

Perceiving the Actions and Intentions of Others: Brain Mechanisms for Social Perception

Kevin Pelphrey
Department of Psychology
Carnegie Mellon University

Mauldin Auditorium (NSH 1305 )
Talk 3:30 pm

Abstract:

Humans are intensely social beings that have evolved and develop within highly social environments in which each individual is dependent upon others. Rapid assimilation of information about other individuals is critical. We must be able to recognize specific individuals and use the history of our past interactions to guide our future behavior. We constantly engage in social perception – using cues from facial expressions, gaze shifts, body movements, and language to infer the intentions of others and plan our own actions accordingly. When approached by another individual, interpreting his or her intentions assumes even greater urgency as the distance between us diminishes. This is particularly so if the individual is a stranger, where body size, facial expressions, gestures and gait may differentiate between a potential threat and a potential ally.

Given the importance of our social interactions, it is plausible that specialized brain systems may have evolved that are critical for these different aspects of social cognition. Several candidate regions thought to comprise the social brain have been identified, including the fusiform gyrus for face perception, the posterior superior temporal sulcus for the perception of biological motion and the visual analysis of others’ intentions, and the amygdala and ventral frontal regions for the perception of emotional expression.

Members of my laboratory have been investigating the properties of these brain regions using functional magnetic resonance imaging (fMRI) in typically developing adults and children as well as in children and adults with autism, a neurodevelopmental disorder marked by severe dysfunction in aspects of social perception. In this talk, I will describe these studies in three main parts: First, I will describe our efforts using fMRI to identify the basic brain mechanisms for social perception in typically developing adults. Second, I will discuss our studies of the neural basis of social perception deficits in adults with autism. Finally, I will describe our recent efforts to chart the typical and atypical development of brain mechanisms for social perception in children with and without autism.

CNBC Seminar: An Adaptive Morphing Approach to Complex 2D and 3D Shape Coding

Ed Connor
Associate Professor and DirectorZanvyl Krieger Mind-Brain Institute Johns Hopkins University

4:00, Monday, October 1

Mellon Institute, Third Floor Social Room
Bellefield Street entrance

The major obstacle to understanding neural representation of complex shape is the sampling problem. Shape space is so vast that standard stimulus strategies typically undersample or entirely miss a neuron's tuning region. Also, any a priori choice of a stimulus set biases and limits the experimental results. To overcome these problems, we implemented an adaptive morphing procedure in which neural responses provide online feedback to guide evolution of stimuli from random starting points. We evaluated this new technique in studies of 2D and 3D shape coding in monkey areas V4 and IT. Each cell was initially tested with one or more starting generations of 50 random shape stimuli. Response rates determined the probability with which ancestor stimuli gave rise to morphed descendants in subsequent stimulus generations. We fit geometric shape coding models that showed strong cross-validation between separate lineages, thus confirming the robustness of the method. The radical efficiency gain and freedom from bias of adaptive sampling could enable detailed exploration of previously intractable issues in visual, tactile, and auditory shape coding.

http://www.mb.jhu.edu/connor.asp

MIT talk: Do robots offer a quantum leap in studying whales?

Speaker: Roger Payne , Ocean Alliance, Lincoln, MA
Date: Tuesday, February 6 2007
Relevant URL: http://www.oceanalliance.org/wci

Abstract:

Payne will review his 39 year study of Patagonian right whales one conclusion of which is that a key to conserving any species seems to be to learn to live with it, and from that experience to build it into human consciousness. But learning to live with whales that migrate 8,000 miles each year requires one to overcome the obstacle of keeping up with them, something that has failed in spite of numerous attempts to achieve it. Storms are what usually cause those who tag and follow whales to lose them. However, robots show great promise in enabling boats to keep up with whales, something that may offer a chance for a major leap in understanding of whales, and that may even someday allow future generations to guide whales into waters in which there is no whaling industry.

MIT report: Online Active Learning in Practice

Title: Online Active Learning in Practice
Authors: Monteleoni, Claire and Kaariainen, Matti
Advisor: Tommi Jaakkola
Issue Date: 23-Jan-2007

Abstract: We compare the practical performance of several recently proposed algorithms for active learning in the online setting. We consider two algorithms (and their combined variants) that are strongly online, in that they do not store any previously labeled examples, and for which formal guarantees have recently been proven under various assumptions. We perform an empirical evaluation on optical character recognition (OCR) data, an application that we argue to be appropriately served by online active learning. We compare the performance between the algorithm variants and show significant reductions in label-complexity over random sampling.

URI: http://hdl.handle.net/1721.1/35784

CMU RI Seminar: Socially Guided Machine Learning

Andrea Thomaz
Post-Doctoral Associate
MIT

Abstract
There is a surge of interest in having robots leave the labs and factory floors to help solve critical issues facing our society, ranging from eldercare to education. A critical issue is that we will not be able to preprogram these robots with every skill they will need to play a useful role in society; robots will need the ability to interact and learn new things 'on the job' from everyday people. This talk introduces a paradigm, Socially Guided Machine Learning, that reframes the Machine Learning problem as a human-machine interaction, asking: How can systems be designed to take better advantage of learning from a human partner and the ways that everyday people approach the task of teaching?

In this talk I describe two novel social learning systems, on robotic and computer game platforms. Results from these systems show that designing agents to better fit human expectations of a social learning partner both improves the interaction for the human and significantly improves the way machines learn.

Sophie is a virtual robot that learns from human players in a video game via interactive Reinforcement Learning. A series of experiments with this platform uncovered and explored three principles of Social Machine Learning: guidance, transparency, and asymmetry. For example, everyday people were able to use an attention direction signal to significantly improve learning on many dimensions: a 50% decrease in actions needed to learn a task, and a 40% decrease in task failures during training.

On the Leonardo social robot, I describe my work enabling Leo to participate in social learning interactions with a human partner. Examples include learning new tasks in a tutelage paradigm, learning via guided exploration, and learning object appraisals through social referencing. An experiment with human subjects shows that Leo's social mechanisms significantly reduced teaching time by aiding in error detection and correction.

CMU VASC talk: Subspectral Algorithms for Sparse Learning, Optimization & Inference

Baback Moghaddam
MERL
Monday, Jan 29, 3:30pm, NSH 1507

Subspectral Algorithms for Sparse Learning, Optimization & Inference

I will present a class of "subspectral" algorithms (i.e. sparse eigenvector techniques) for solving NP-hard combinatorial optimization problems in three general applied domains: (1) Supervised/unsupervised learning, in the traditional or orthodox sense (e.g. PCA & LDA), (2) Quadratic/Entropic Optimization (e.g. Least-Squares & MaxEnt) and (3) Inference, in the strict probabilistic/Bayesian sense (e.g. Automatic Relevance Determination and variational methods like Expectation Propagation). Subspectral algorithms for both exact (optimal) and greedy (approximate) solutions of these general sparse optimization problems are derived using analytic eigenvalue bounds. Specifically, an efficient "dual-pass" greedy algorithm is shown to yield near-optimal solutions for all possible cardinalities (at once) in a fraction of the time it takes for most continuous relaxation methods to find solutions of comparable quality for a single cardinality. I will present sample applications of subspectral optimization techniques in .sparse PCA. for feature selection (statistics), .sparse LDA. for classification (gene discovery), sparse kernel regression (robotics & control), sparse quadratic programming (portfolio optimization), graph model selection (sensor networks) as well as sparse Bayesian inference for computer vision (face recognition & OCR).

Bio:
Baback Moghaddam's research interests are in computational vision with a main focus on probabilistic visual learning. His related areas of interest and expertise include statistical modeling, Bayesian data analysis, machine learning and pattern recognition. He obtained his PhD in Electrical Engineering and Computer Science (EECS) from the Massachusetts Institute of Technology (MIT) in 1997 where he was a member of the Vision and Modeling Group at the MIT Media Laboratory where he developed a fully-automatic vision system which won DARPA's 1996 "FERET" Face Recognition Competition.

Dr. Moghaddam was the winner of the 2001 Pierre Devijver Prize from the International Association of Pattern Recognition for his "innovative approach to face recognition" and received the Pattern Recognition Society Award for "exceptional outstanding quality" for his journal paper "Bayesian Face Recognition." He currently serves on the editorial board of the journal Pattern Recognition and has contributed to numerous textbooks on image processing and computer vision including the core chapter in Springer-Verlag's latest biometric series, "Handbook of Face Recognition."

Dr. Moghaddam's past research included infrared (IR) image analysis for the Office of Naval Research (ONR), segmentation of synthetic aperture radar (SAR) imagery for MIT Lincoln Laboratory as well as designing a micro-gravity experiment for laser annealing of amorphous silicon which was flown aboard the US Space Shuttle in 1990.

http://www.merl.com/people/baback

CMU ML talk: Approximate inference using planar graph decomposition

Approximate inference using planar graph decomposition
by Amir Globerson and Tommi Jaakkola
NIPS 2006

A number of exact and approximate methods are available for inference calculations in graphical models. Many recent approximate methods for graphs with cycles are based on tractable algorithms for tree structured graphs. Here we base the approximation on a different tractable model, planar graphs with binary variables and pure interaction potentials (no external field). The partition function for such models can be calculated exactly using an algorithm introduced by Fisher and Kasteleyn in the 1960s. We show how such tractable planar models can be used in a decomposition to derive upper bounds on the partition function of non-planar models. The resulting algorithm also allows for the estimation of marginals. We compare our planar decomposition to the tree decomposition method of Wainwright et. al., showing that it results in a much tighter bound on the partition function, improved pairwise marginals, and comparable singleton marginals.

CMU ML talks: Greedy Layer-Wise Training of Deep Networks

Greedy Layer-Wise Training of Deep Networks
by Yoshua Bengio, Pascal Lamblin, Dan Popovici and Hugo Larochelle
NIPS 2006

Deep multi-layer neural networks have many levels of non-linearities allowing them to compactly represent highly non-linear and highly-varying functions. However, until recently it was not clear how to train such deep networks, since gradient- based optimization starting from random initialization appears to often get stuck in poor solutions. Hinton et al. recently introduced a greedy layer-wise unsupervised learning algorithm for Deep Belief Networks (DBN), a generative model with many layers of hidden causal variables. In the context of the above optimization problem, we study this algorithm empirically and explore variants to better understand its success and extend it to cases where the inputs are continuous or where the structure of the input distribution is not revealing enough about the variable to be predicted in a supervised task. Our experiments also confirm the hypothesis that the greedy layer-wise unsupervised training strategy mostly helps the optimization, by initializing weights in a region near a good local minimum, giving rise to internal distributed representations that are high-level abstractions of the input bringing better generalization.