Artificial Intelligence Seminar

The AI seminar will meet weekly for lectures by graduate students, faculty, and researchers emphasizing work-in-progress and recent results in AI research. Lunch will be served starting at noon, with the talks running between 12:15 and 1:15. The new format is designed to allow AI chit-chat before the talks begin. Also, we're trying to make some of the presentations less formal so that students and faculty will feel comfortable using the seminar to give presentations about work in progress or practice talks for conferences.

Date	Title/Speaker/Abstract/Host
September 10	Co-evolution of Actions and Abstractions for Active Learning. Hod Lipson, Computational Synthesis Lab, Cornell University We present a co-evolutionary algorithm for automated system identification suitable for inference and manipulation of a wide range of nonlinear systems with a minimum of experimentation on the target system. The algorithm synthesizes an explicit model directly from the observed data produced by intelligently generated tests. The algorithm is composed of two co-evolving populations: One population evolves candidate models that estimate the structure of the hidden system; The second population explores informative tests that either extract new information from the hidden system or elicit desirable behavior from it. The fitness of candidate models is their ability to explain behavior of the target system observed in response to all tests carried out so far; the fitness of candidate tests is their ability to make the models disagree in their predictions. We demonstrate this estimation-exploration algorithm in grammar induction, gene network inference, and robot damage recovery.
September 17	Determining the Hierarchical Structure of Perspective and Speech Expressions Eric Breck News articles report on facts, events, and opinions with the intent of conveying the truth. However, the facts, events, and opinions appearing in the text are often known only second- or third-hand, and as any child who has played "telephone" knows, this relaying of facts often garbles the original message. Properly understanding the information filtering structures that govern the interpretation of these facts, then, is critical to appropriately analyzing them. In this work, we present a learning approach that correctly determines the hierarchical structure of information filtering expressions 78.30% of the time. Joint work with Claire Cardie.
September 24	Social Network Analysis of Text Dragomir R. Radev, University of Michigan Textual data is everywhere, in email and scientific papers, in online newspapers and e-commerce sites. The Web contains more than 200 terabytes of text not even counting the contents of dynamic textual databases. This enormous source of knowledge is seriously underexploited. Textual documents on the Web are very hard to model computationally: they are unstructured, time-dependent, collectively authored, and of uneven importance. Traditional grammar-based techniques don't scale up to address such problems. Novel representations and analytical tools are needed. NewsInEssence (www.newsinessence.com) is a system that crawls the Web for news, automatically clusters them by topic, and produces user-defined extractive summaries of each cluster. A recent addition to the battery of summarization algorithms available to NewsInEssence is the Cosine Centrality method. In this talk I will describe how one can apply the theory of social networks and stochastic processes (in particular rank-based prestige and random walks on undirected graphs) to multi-document text summarization. (I will begin my talk with a short tutorial on the mathematics needed for the rest of the talk.)  If time permits, at the end of the talk, I will quickly describe two recent ongoing projects in my research group: one on machine learning for object classification using random walks on bipartite (feature-object) graphs and another on using phylogenetic techniques for fact tracking in evolving multi-document summarization.
October 1	Obtaining Calibrated Probabilities from Boosting Alexandru Niculescu-Mizil Boosted decision trees typically yield good accuracy, precision, and ROC area. However, because the outputs from boosting are not well calibrated posterior probabilities, boosting yields poor squared error and cross-entropy. We empirically demonstrate why boosting predicts distorted probabilities. We examine three calibration methods for correcting this distortion: Platt Scaling, Isotonic Regression, and Logistic Correction. Experiments show that calibration significantly improves the probabilities predicted by boosting. After calibration, boosted decision trees predict better probabilities than other learning methods such as SVMs, neural nets, bagged decision trees, and k-nearest neighbor, even after these other methods are calibrated. Joint work with Rich Caruana.
October 8	The KDD-Cup 2004 Post-Game Show Rich Caruana and Thorsten Joachims What do you get if you ask 102 groups of machine learning researchers and students to solve the same learning problems? In this talk, we will analyze the results of this year's KDD-Cup. The KDD-Cup is an annual competition held in conjunction with the SIG-KDD Conference. Cornell chaired the KDD-Cup this year. The competition consisted of two datasets - one from particle physics, and one on protein homology detection. For both datasets, participants were asked to submit four sets of prediction, each set optimizing to a different performance measure. From the sets of predictions we computed the performances of the different groups and declared winners. Although we will talk about how we determined the winners, the presentation will not focus on individual competitors, but on how the field of competitors behaved as a whole. Beyond their primary purpose of determining the winners, the 500+ sets of predictions are a great resource for analysing how the community approached these learning problems. For example, did all competitors that performed well submit essentially the same predictions? Would some of the groups have done better if they had collaborated? Did groups manage to achieve better performance by optimizing to the different performance criteria? In this talk we will address these questions and show some surprising results. Joint work with Lars Backstrom.
October 15	Sleeping Beauty Reconsidered: Conditioning and Reflection in Asynchronous Systems Joe Halpern Here is the Sleeping Beauty problem: Some researchers are going to put you to sleep. During the two days that your sleep will last, they will briefly wake you up either once or twice, depending on the toss of a fair coin (heads: once; tails: twice). After each waking, they will put you back to sleep with a drug that makes you forget that waking. When you are first awakened, to what degree ought you believe that the outcome of the coin toss is heads? It seems that the answer is obvious: 1/2. After all, it was 1/2 before you were put to sleep and you knew all along that you would be woken up. So it should still be 1/2 when you are actually woken up. But lots of people have also argued for the answer 1/3. (I'll explain why in the talk.) Besides being a fun problem to think about, this problem reveals problems with conditioning in asynchronous systems and systems where agents have imperfect recall. I'll describe a formal model in which to think about these things, and discuss implications for various properties that have been considered in the literature, like Savage's Sure Thing Principle.
October 21 Thursday Upson Lounge (1st Floor)	All You Really Need to Know About Computer Science Was Learned Pursuing Artificial Intelligence Ray Mooney, University of Texas at Austin Most of the fundamental concepts in computing were developed by people who were trying to understand, emulate, or augment the human mind. This list of concepts includes Boolean logic, finite-state machines, formal grammars, Turing machines, linked lists, recursion, garbage collection, combinatorial search, automated theorem proving, time-shared operating systems, computer networks, graphical user interfaces, and computational complexity theory. This talk will describe how the history of all of these fundamental computing concepts is ultimately rooted in the historical pursuit of artificial intelligence. Unfortunately, subsequently, AI has become increasingly isolated from the rest of computer science, to the detriment of both. I believe the time is ripe for a re-integration of AI into the rest of computing. My goal is to start the semester with a light, mildly entertaining, and potentially controversial talk that provokes thought and discussion about the role of AI in the broader enterprise of computer science.
October 29	Data Mining in Metric Space: An Empirical Analysis of Supervised Learning Performance Criteria Rich Caruana & Alex Niculescu, Cornell University Many criteria can be used to evaluate machine learning performance. Different criteria are appropriate in different settings, and it is not always clear which criteria to use. To make things worse, learning methods that perform well on one criterion may not perform well on other criteria. For example, SVMs and boosting are designed to optimize accuracy, wheras neural nets typically optimize squared error or cross entropy. We conducted an empirical study using a variety of learning methods (SVMs, neural nets, kNN, bagged and boosted trees, and boosted stumps) to compare nine boolean classification performance metrics: Accuracy, Lift, F-Score, Area under the ROC Curve, Average Precision, Precision/Recall Break-Even Point, Squared Error, Cross Entropy, and Probability Calibration. Multidimensional scaling (MDS) shows that these metrics span a low dimensional manifold. The three metrics that interpret predictions as probabilities: squared error, cross entropy, and calibration, lay in one part of metric space surprisingly far away from the metrics that depend on the ordering entailed of the predicted values: ROC area, average precision, break-even point, and lift. In between them fall two metrics that depend on comparing predictions to a threshold: accuracy and F-score. As expected, max margin methods (SVMs and boosted trees) perform well on metrics like accuracy, but perform poorly on probability metrics such as squared error. What was not expected was that the margin methods have excellent performance on ordering metrics such as ROC area and average precision. We introduce a new metric, SAR, that combines squared error, accuracy, and ROC area into one metric. MDS and correlation analysis shows that SAR is centrally located and correlates well with other metrics, suggesting that it is a good general purpose metric to use when more specific criteria are not known. This is an updated version of a talk given at the KDD2004 Conference.
November 5 Upson Lounge (1st Floor)	Heavy-tailed Phenomena in Computation  Carla P. Gomes In recent years, it has become clear that extreme events often occur much more frequently than standard statistical distributions would predict. Non-standard statistical models have recently been used to characterize phenomena as diverse as earthquakes, financial market fluctuations, and internet traffic. Computational processes are also characterized by extreme fluctuations. In fact the runtime distributions of computational search methods exhibit intriguing properties, often characterized by very long tails or ``heavy tails''. I will provide an overview of heavy-tailed distributions in combinatorial search. I will discuss how one can dramatically boost the performance of computational search procedures for solving real-world problems by exploiting the heavy tailed phenomena. I will also present formal models of heavy-tails in combinatorial search and discuss different ``statistical regimes of heavy-tailed behavior'' in combinatorial domains, providing a general characterization of parameter regions where heavy-tailed behavior is prevalent.
November 12	Supervised Clustering with SVMs Thomas Finley Supervised and semisupervised clustering attempts to apply supervised learning to clustering for settings where a user has a prior notion of what constitutes a correct clustering of data. Examples of these types of problems include the noun-phrase coreference problem where we cluster noun phrases referring to the same entity, and news story clustering where we cluster news stories on the same topic. In these settings, we cluster multiple small sets of items. We train over examples of sets of items and partitionings over the sets to learn an item pair similarity measure. Previous work used a binary classifier trained over item pairs to learn a pairwise similarity measure. Unfortunately this does not account for the complex interactions among items in clustering, nor optimize to the loss function appropriate for the specific task. Therefore, complex heuristics to model these interactions and the role of the loss function are necessary. To overcome these problems, we adapt an SVM for learning complex output spaces to clustering, include the clustering algorithm in the learning process, and directly optimize clustering quality to an arbitrary loss function. This removes any need for heuristics to model how data will interact with the clusterer and the loss function. Joint work with Thorsten Joachims.
November 18 Thursday Upson 5130	Data Science: Machine Learning in Biology and Chemistry Kristin Bennett, Rensselaer Polytechnic Institute The availability of data and powerful data analysis methods is changing the nature of scientific research.  The traditional scientific method is hypothesis driven.  Now more research is becoming data driven.   In this work we examine "Data Science" problems in biology and chemistry that are being addressed using machine learning and data mining techniques. We examine novel learning methods developed to address the challenges of these applications.  In biology,  Bayesian models are used to cluster DNA fingerprints of tuberculosis strains in order to facilitate epidemiology investigation.  In cheminformatics, spectral kernel methods are used to predict the bioactivities of molecules to facilitate drug discovery and chromatography.
November 26	No AI Seminar - Thanksgiving Break
December 3	Efficient Non-parametric Revelation of Ordinal Preferences Carmel Domshlak Research on reasoning about user preferences in artificial intelligence attempts both to connect between modeling principles coming from philosophy, psychology, and economics, and to develop computational tools grounded in these principles. The goal is to provide users with effective, computationally efficient decision-support tools that will assist users in their everyday activities (e.g., choosing an attractive vacation package.) Extensive research in this direction significantly reduced the gap between theory and practice of decision theory. However, the gap is still there. The main problem to date is that there is no universal solution for the problem that is efficient for all sets of choices and all types of preference information. In this talk we'll present our recent work making a step towards such a solution, providing a generically efficient platform for reasoning about ordinal user preferences. Our proposal is based on exploiting and extending ideas from two different branches of artificial intelligence, namely knowledge representation and machine learning. Both theoretical foundations and preliminary empirical evaluation will be discussed. Joint work with Thorsten Joachims.

See also the AI graduate study brochure.

Please contact any of the faculty below if you'd like to give a talk this semester. We especially encourage graduate students to sign up! 

Back to CS course websites