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
January 26	No Seminar
February 2	No Seminar
February 9	QuickRank: A Recursive Ranking Algorithm Amy Greenwald  In this talk, I will describe QuickRank, an efficient algorithm for ranking individuals in a society, given a network that encodes their relationships, assuming that network possesses an accompanying hierarchical structure: e.g., the Enron email database together with the corporation's organizational chart. The QuickRank design is founded on the ``peer-review'' principle and an hypothesis due to Bonacich. Together, these premises leads to a recursive ranking algorithm which is scalable, parallelizable, and easily updateable. It is also potentially more resistant to link-spamming than other popular ranking algorithms. Joint work with John Wicks Host: Dexter Kozen
February 16	New Techniques for Counting and Sampling Solutions of Satisfiability (SAT) Problems Ashish Sabharwal Abstract: Boolean satisfiability testing or SAT has emerged as one of the leading general purpose reasoning technologies with academic interest as well as industrial success. Two natural and related extensions of SAT, with probabilistic reasoning as a key application, are the problems of counting the number and solutions and sampling from the set of solutions (near)-uniformly at random. In this talk, I'll describe a new approach for efficiently obtaining bounds on the solution count of problems with (probabilistic) correctness guarantees. This technique, which we call MBound, uses randomly generated XOR or parity constraints to cut the solution space of a problem in a controlled manner. We then simply use an off-the-shelf SAT solver --- without any modification whatsoever --- to derive a bound on the true solution count. This idea can also be extended for solution sampling. MBound scales much better than known exact counting methods, and is often able to provide lower bound model counts such as 10^40 in a matter of minutes where exact counters do not terminate after several hours, counting only up to 10^6 or so. It also serves as a more reliable platform than current approximate counting techniques, which offer no correctness guarantees and often under- or over-count. Joint work with Carla Gomes and Bart Selman.
February 23	A local bi-gram model for object recognition Dr. Larry Zitnick, MSR Matching a discrete set of local patch-based features is a useful technique for object recognition. The effectiveness of these methods relies mainly on the discrimitive power of the features' descriptors. This is best demonstrated by the effectiveness of "bag of  words" approaches. Recently, methods that additionally model the spatial relationship of features have shown improved results. In this talk, I propose a purely local bi-gram representation for modeling spatial relationships between neighboring match primitives. To increase the descriptiveness of a matching primitive, we explore using sets of one, two and three features. The recognition of new objects is accomplished by finding trees of matching primitives that obey the bi-gram model learned for a specific object class.  In addition to the local bi-gram model, I will also briefly discuss the use of feature triplets for recognition in large datasets. Host: Dan Huttenlocher
March 2	Recognizing the Intended Message of an Information Graphic Sandra Carberry, University of Delaware Information is the key to effective knowledge and decision-making. However, in order to be useful, information must be accessible. Information graphics (non-pictorial graphics such as bar charts, line graphs, and pie charts) pose accessibility problems: 1) although much attention has been devoted to the summarization, categorization, and retrieval of text documents and images, almost no attention has been given to information graphics. 2) individuals with impaired eyesight lack effective methods for accessing the information provided by information graphics. The overwhelming majority of information graphics that appear in newspapers, magazines, and formal reports have a communicative goal or message that they are intended to convey. This talk will first present our corpus study showing that the message conveyed by an information graphic in a multimodal document is generally not contained in the article's text. The talk will then present our research on identifying the primary intended message of an information graphic; this message can then be used as the core of a summary of the graphic for digital libraries or as part of an interactive natural language system for blind individuals. Our approach is to view information graphics as a form of language containing communicative signals. We will discuss the kinds of communicative signals appearing in information graphics, and describe how we exploit these in a Bayesian network for recognizing the graphic's intended message. We will present our implemented system along with the results of evaluation experiments that demonstrate the effectiveness of our methodology. This research has been done jointly with Stephanie Elzer (former graduate student at the University of Delaware and currently an assistant professor at Millersville University). Other contributors to the work include Dan Chester, Seniz Demir, and Peng Wu. Host: Claire Cardie
March 9	An Experimental Study of the Coloring Problem on Human Subject Networks Sid Suri, Cornell University Theoretical work suggests that structural properties of naturally occurring networks are important in shaping behavior and dynamics. However, the relationships between structure and behavior are difficult to establish through empirical studies, because the networks in such studies are typically fixed. We studied networks of human subjects attempting to solve the graph or network coloring problem, which models settings in which it is desirable to distinguish one’s behavior from that of one’s network neighbors. Networks generated by preferential attachment made solving the coloring problem more difficult than did networks based on cyclical structures, and "small worlds" networks were easier still. We also showed that providing more information can have opposite effects on performance, depending on network structure. Host: Jon Kleinberg
March 16	**No AI Seminar -- Have a Happy Spring Break!!**
March 23	**No AI Seminar -- SPRING BREAK**
March 30	**No AI Seminar --ACSU student/faculty luncheon**
April 6	Support Vector Method for Optimizing Rank-Based Performance Measures Yisong Yue, Cornell University When learning to rank documents for queries, optimizing a model to achieve high accuracy often yields poor results. This is partly due to the large imbalance between relevant and non-relevant documents for any given query. For example, in a dataset which has 99% non-relevant examples and 1% relevant examples, a learning algorithm which optimizes for accuracy might not be able to discriminate between relevant and non-relevant documents. As a result, such an algorithm would learn a relatively simple model which always predicts non-relevant (since that achieves 99% accuracy). Instead of accuracy, the information retrieval community focuses more on rank-based performance measures, such as mean average precision, mean reciprocal rank, and normalized discounted cumulative gain. These measures are not computed directly using the values of the predictions of each document, but rather the ranking of the documents (rankings are typically computed by sorting on the predicted values). The discrete nature and the interdependency of all the documents’ predicted values make it difficult to design machine learning algorithms to directly optimize for these measures. In this talk, we will discuss a method based on structural SVMs to directly optimize for mean average precision. We will provide an overview of the algorithm as well as a sketch of the proof of correctness. We will also present empirical results which show that our algorithm outperforms conventional SVM algorithms and can also learn a superior combination of scores from existing query retrieval functions. We will also show that this method can be generalized to optimize for a large class of rank-based measures and provide preliminary empirical results on optimizing for mean reciprocal rank and normalized discounted cumulative gain.
April 13	**CANCELLED**
April 20	**No AI Seminar -- CS Colloquium**
April 27	Detecting Research Topics via the Correlation Between Graphs and Texts Yookyung Jo - Cornell University In this talk, we discuss the problem of detecting topics in large-scale linked document collections. Recently, topic detection has become a very active area of research due to its utility for information navigation, trend analysis, and high-level description of data. We present a unique approach of detecting topics, that uses the correlation between the distribution of a term that represents a topic and the distribution of citation links relevant to a topic. Our approach is based on the intuition that if a term is relevant to a topic, the documents containing the term are more densely connected to each other than a random selection of documents. We develop a topic score measure for each term, using the likelihood ratio of binary hypotheses based on a probabilistic description of graph connectivity. We then get a ranked list of terms, where terms are ordered according to how likely it is relevant to a topic. We extend our algorithm to detect a topic represented by a set of terms, using the intuition that if the co-occurrence of terms represents a new topic, the citation pattern should exhibit the synergistic effect. We test our algorithm on two electronic research literature collections, arXiv and Citeseer. Our evaluation shows that the approach is effective and reveals some novel aspects of topic detection.
May 4	No Seminar

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