SUNMONTUEWEDTHUFRISAT
Events for April 15, 2010
-
Planning and Learning in Information Space
Thu, Apr 15, 2010
Thomas Lord Department of Computer Science
Conferences, Lectures, & Seminars
Time: 12:00 PMRoom: EEB 248Talk Title: Planning and Learning in Information SpaceSpeaker: Professor Nicholas Roy Host: Professor Gaurav SukhatmeAbstract:Decision making with imperfect knowledge is an essential capability for unmanned vehicles operating in populated, dynamic domains. For example, a UAV flying autonomously indoors will not be able to rely on GPS for position estimation, but instead use on-board sensors to track its position and map the obstacles in its environment. The planned trajectories for such a vehicle must therefore incorporate sensor limitations to avoid collisions and to ensure accurate state estimation for stable flight -- that is, the planner must be be able to predict and avoid uncertainty in the state, in the dynamics and in the model of the world. Incorporating uncertainty requires planning in information space, which leads to substantial computational cost but allows our unmanned vehicles to plan deliberate sensing actions that can not only improve the state estimate, but even improve the vehicle's model of the world and how people interact with the vehicle.I will discuss recent results from my group in planning in information space; our algorithms allow robots to generate plans that are robust to state and model uncertainty, while planning to learn more about the world. I will describe the navigation system for a quadrotor helicopter flying autonomously without GPS using laser range-finding, and will show how these results extend to autonomous mapping, general tasks with imperfect information, and human-robot interaction.Bio:Nicholas Roy is an Associate Professor in the Department of Aeronautics & Astronautics at the Massachusetts Institute of Technology and a member of the Computer Science and Artificial Intelligence Laboratory (CSAIL) at MIT. He received his Ph. D. in Robotics from Carnegie Mellon University in 2003. His research interests include autonomous systems, mobile robotics, human-computer interaction, decision-making under uncertainty and machine learning.
Location: Hughes Aircraft Electrical Engineering Center (EEB) - 248
Audiences: Everyone Is Invited
Contact: CS Front Desk
-
CS Colloq: Niv Buchbinder - CANCELLED
Thu, Apr 15, 2010 @ 03:30 PM - 05:00 PM
Thomas Lord Department of Computer Science
Conferences, Lectures, & Seminars
Talk Title: Randomized k-Server Conjecture (Online Algorithms meet Linear Programming)
Speaker: Dr. Niv Buchbinder
Host: Prof. David KempeTALK CANCELLEDAbstract:
The k-server problem is one of the most central and well studied problems in competitive analysis and is considered by many to be the "holy grail" problem in the field. In the k-server problem, there is a distance function d defined over an n-point metric space and k servers located at the points of the metric space. At each time step, an online algorithm is given a request at one of the points of the metric space, and it is served by moving a server to the requested point. The goal of an online algorithm is to minimize the total sum of the distances traveled by the servers so as to serve a given sequence of requests. The k-server problem captures many online scenarios, and in particular the widely studied paging problem.A twenty year old conjecture states that there exists a k-competitive online algorithm for any metric space. The randomized k-server conjecture states that there exists a randomized O(log k)-competitive algorithm for any metric space. While major progress was made in the past 20 years on the deterministic conjecture, only little is known about the randomized conjecture.We present a very promising primal-dual approach for the design and analysis of online algorithms. We survey recent progress towards settling the k-server conjecture achieved using this new framework.Bio:
Niv Buchbinder is a post-doctoral researcher at Microsoft Research, New England at Cambridge, MA.
Previously, he was a Ph.D. student in Computer Science at Technion, Israel Institute of Technology under the supervision of Prof Seffi Naor.
His main research interests are algorithms for combinatorial problems in offline and online settings. He is also interested in algorithmic game theory problems.
Location: Seaver Science Library (SSL) - 150
Audiences: Everyone Is Invited
Contact: CS Front Desk
-
CS Colloq: Jesse Davis
Thu, Apr 15, 2010 @ 03:30 PM - 05:00 PM
Thomas Lord Department of Computer Science
Conferences, Lectures, & Seminars
Talk Title: Predicate Invention and Transfer LearningSpeaker: Jesse DavisHost: Prof. Gaurav Sukhatme and Prof. Craig KnoblockAbstract: Machine learning has become an essential tool for analyzing biological and clinical data, but significant technical hurdles prevent it from fulfilling its promise. Standard algorithms make three key assumptions: the training data consist of independent examples, each example is described by a pre-defined set of attributes, and the training and test instances come from the same distribution. Biomedical domains consist of complex, inter-related, structured data, such as patient clinical histories, molecular structures and protein-protein interaction information. The representation chosen to store the data often does not explicitly encode all the necessary features and relations for building an accurate model. For example, when analyzing a mammogram, a radiologist records many properties of each abnormality, but does not explicitly encode how quickly a mass grows, which is a crucial indicator of malignancy. In the first part of this talk, I will focus on the concrete task of predicting whether an abnormality on a mammogram is malignant. I will describe an approach I developed for automatically discovering unseen features and relations from data, which has advanced the state-of-the-art for machine classification of abnormalities on a mammogram. It achieves superior performance compared to both previous machine learning approaches and radiologists.In the second part of this talk, I will address the problem of generalizing across different domains. Unlike machines, humans are able take knowledge learned in one domain and apply it to an entirely different one. Computationally, the missing link is the ability to discover structural regularities that apply to many different domains, irrespective of their superficial descriptions. This is arguably the biggest gap between current learning systems and humans. I will describe an approach based on a form of second-order Markov logic, which discovers structural regularities in the source domain in the form of Markov logic formulas with predicate variables, and instantiates these formulas with predicates from the target domain. This approach has successfully transferred learned knowledge between a molecular biology domain and a Web one. The discovered patterns include broadly useful properties of predicates, like symmetry and transitivity, and relations among predicates, like various forms of homophily.Bio: Jesse Davis is a post-doctoral researcher at the University of Washington. He received his Ph.D in computer science at the University of Wisconsin – Madison in 2007 and a B.A. in computer science from Williams College in 2002. His research interests include machine learning, statistical relational learning, transfer learning, inductive logic programming and data mining for biomedical domains.
Location: Seaver Science Library (SSL) - 150
Audiences: Everyone Is Invited
Contact: CS Front Desk
