Date( Fall 2005 ) Speaker and Abstract 2005/09/09 Speaker: Allen Tannenbaum Affiliation: School of Electrical and Computer Engineering, Georgia Tech Area: Computer vision, Image Processing, Biomedical Imaging Title: Methods for Segmentation and Registration of Medical Imagery Abstract: We will describe some recent work on two key problems in medical imagery: segmentation and registration. We will also describe controlled active vision techniques for image guided surgery and therapy. The underlying method is based on certain flows which give rise to (nonlinear) geometric equations which are invariant with respect to a given transformation group action. We will provide some relevant results from the theory of curve and surface evolution, and show how these may be used for a number of areas in computer vision and image processing, such as image enhancement, optical flow, registration image segmentation, shape theory, and invariant scale-spaces. We will demonstrate these techniques with a wide variety of medical images including MR, CT, and ultrasound. The talk is designed to be accessible to a general audience with an interest in medical imaging. 2005/09/30 Speaker: Wes Huang Affiliation: Rensselaer Polytechnic Institute Area: Robotics Title: Mapping and Exploration with Sensing-Limited Robots Abstract: Despite their sensing limitations, blind people are able to explore and navigate in the world. We have been developing algorithms for robots with sensing limitations --- sparse and limited-range sensing --- to make maps and subsequently navigate using those maps. Our motivation is twofold: to improve the capabilities of inexpensive robots with a limited array of sensors and to investigate the relationship between sensing limitations and a robot's mapping and navigation abilities. As an example of the sensing limitations we have in mind, our robots are equipped with only five IR rangefinders that have a maximum range of 80 cm. First, I will present our work in creating topological maps with these robots. These topological maps are defined in terms of robot behaviors: nodes in our map are locations where behaviors terminate, and the robot has a choice of behaviors at each node to take it to another location. Our approach in this work has been to develop behaviors that explicitly consider the geometry of the world, so the resulting map represents relevant aspects of the geometry while still reflecting the "topological" connectivity between places. In particular, we have devised robot behaviors that trace the generalized Voronoi diagram under the $L_\infty$ distance metric, resulting in a complete algorithm for mapping rectilinear worlds with sparse short-range sensing. Next, I will discuss how topological maps from multiple robots (without a common reference frame) can be merged using a combination of techniques from image registration and graph matching. Finally, I will show some preliminary results in applying a particle filter SLAM (simultaneous localization and mapping) technique to robots with sparse sensing to create maps of large-scale environments. 2005/10/07 Speaker: Rick Durrett Affiliation: Cornell University Title: Life in a Small World Abstract: In 1998 Strogatz and Watts created their small world random graph by starting with a ring of sites each of which was connected to its k nearest neighbors in each direction and then rewiring a small fraction p of connections. One can in a straightforward way define a two dimensional version starting from a torus. This gives a graph that is a more reasonable model for the spread of infectious diseases. We get colds and the flu not only from our next door neighbors in suburbia, but also from people we see at work and from germs our children bring home from school. Motivated by this story, we will investigate the behavior of epidemics, percolation, the Ising model, random walks, and the voter model on the small world graph and compare their behavior to processes on regular lattices. The talk will cover parts of Chapters 5 and 6 of my almost finished book which can be found at http://www.math.cornell.edu/~durrett/. 2005/10/21 Speaker: Douglas Eck Affiliation: Université de Montréal Area: Machine Learning & Music Title: Predicting the Similarity Between Two Music Audio Files Abstract: I will give a short overview of some open questions in music information retrieval (MIR) that have relevance in the domain of machine learning. I will then focus on the issue of predicting the similarity between two sound files containing music. By way of introducing the problem, I will briefly describe a recent algorithm from our lab that proved successful at predicting the genre and artist of a sound file. This algorithm won the genre prediction category and placed second in the artist recognition category at a recent international MIR contest (MIREX 2005). I will spend most of the talk discussing a method to extract long-timescale structure from music audio files. Specifically I will introduce the Autocorrelation Phase Matrix, a data structure that stores intermediate results of the standard autocorrelation function. With this matrix it is possible to recover phase information that is normally lost in computing autocorrelation. I will discuss why this information is important and will talk about how the Autocorrelation Phase Matrix can be useful for problems like tempo prediction and beat tracking. I will conclude with speculations on the utility of this structure as a general feature for measuring music similarity. 2005/10/28 Speaker: David Notkin Affiliation: University of Washington Title: An Empirical Study of Code Clone Genealogies Abstract: There has been a broad assumption that code clones are inherently bad and that eliminating clones by refactoring would solve the problems of code clones. To investigate whether this assumption is valid, we developed a formal definition of clone evolution and built a clone genealogy tool that automatically extracts the history of code clones from a source code repository. Using our clone genealogy extractor, we studied the evolution of code clones in two Java open source projects. Our study of clone evolution contradicts some conventional wisdom about clones; refactoring may not benefit many clones for two reasons. First, many code clones exist in the system for only a short time, disappearing soon after; extensive refactoring of such short-lived clones may not be worthwhile if they are to diverge from one another very soon. Second, many clones, especially long-lived clones that have changed consistently with other elements in the same group, are not locally refactorable due to the programming language limitations. Our study discovers that there are types of clones that refactoring would not help, and it opens up opportunities for clone maintenance tools that target unaddressed classes of clones using clone genealogy information. This is joint work with Miryung Kim, Vibha Sazawal, and Gail Murphy. 2005/11/18 Speaker: Frank Pfenning Affiliation: Carnegie Mellon University Area: Trustworthy Computing, Logic and Type Theory Title: Distributed System Security via Logical Frameworks Abstract: In an on-going project at Carnegie Mellon University we are implementing a scalable distributed security architecture using smartphones and embedded devices in order to control access to a variety of resources such as office doors and computer accounts. At the heart of the effort is a so-called authorization logic which plays a dual role for policy specification and policy enforcement. A policy is specified as a collection of logical axioms that permit us to reason about who has access to which resources. A policy is enforced by requiring a formal proof of the right to access a resource before that access is granted. We sketch the overall architecture and then focus on the authorization logic and how it is implemented in a logical framework. We also discuss some recent results that exploit the representation of authorization logic in a logical framework in order to prove important properties of policies, such as non-interference between principals. 2005/11/30 Speaker: Rich Sutton Affiliation: University of Alberta Title: Empirical Artificial Intelligence Abstract: I propose that experience --- the explicit sequence of actions and sensations over an agent's life --- should play a central role in all aspects of artificial intelligence. In particular: Knowledge representation should be in terms of experience. Recent work has shown that a surprisingly wide range of world knowledge can be expressed as predictions of experience, enabling it to be automatically verified and tuned, and grounding its meaning in data rather than in human understanding. Planning/reasoning should be in terms of experience. It is natural to think of planning as comparing alternative future experiences. General methods, such as dynamic programming, can be used to plan using knowledge expressed in predictive form. State representation should be in terms of experience. Rather than talk about objects and their metric or even topological relationships, we represent states by the predictions that can be made from them. For example, the state "John is in the coffee room" corresponds to the prediction that going to the coffee room will produce the sight of John. Much here has yet to be worked out. Each of the "should"s above can also be read as a "could", or even a "perhaps could". I am optimistic and enthusiastic because of the potential for developing a compact and powerful theory of AI in the long run, and for many easy experimental tests in the short run. 2005/12/02 Speaker: Janos Pach Affiliation: City College, CUNY and Renyi Institute, NYU Title: From Sam Loyd to Laszlo Fejes Toth: The Fifteen Puzzle and Discrete Motion Planning Abstract: We discuss a variety of discrete motion planning questions that can be regarded as far-reaching generalizations of the fifteen puzzle. For instance, given an initial position of a system of n congruent circular or square modules in the plane, is it possible to transform it into a prescribed target position, obeying certain natural motion rules? If the answer is yes, what is the smallest number of steps sufficient for completing this task? We survey some recent developments in this field, including the discovery of unexpected connections between questions of this type and old density problems for disk packings, due to Laszlo Fejes Toth (1915-2005).