Shortcuts: Nathan Srebro (9/2008) Ronen Basri (9/2008) William Schuler (10/2008) Michael White (10/2008) Russ Tedrake (10/2008) Douglas Downey (2/2009)
Upcoming Talks
Planned Talks
Making Sense of Unstructured Information
- Dan Roth
- MIAS Center Director and Professor of Computer Science, UIUC
- Abstract: Recent studies have shown that over 85% of the information organizations deal with is unstructured - the vast majority of which is text in different forms. A multitude of techniques has to be used in order to enable intelligent access to this information and to support transforming it to forms that allow sensible use of the information. The fundamental issue that all these techniques have to address is that of semantics - there is a need to move toward understanding the text at an appropriate level, beyond the word level, in order to support access, knowledge extraction and synthesis. We will discuss some of our research in these directions, addressing several dimensions of text understanding that can facilitate access to and extraction of knowledge from unstructured text, transforming it to forms that are useful to different users in different settings, and integrating it along multiple dimensions and with existing institutional resources.
Semantic Abstraction and Integration across Text Documents and Data Bases
- Dan Roth
- MIAS Center Director and Professor of Computer Science, UIUC
- Abstract: Intelligent access to information requires semantic integration of structured databases with unstructured textual resources. We will discuss some of our research towards identifying mentions of entities in text, identifying relations that may hold between entities and concepts in texts and determining whether different mentions of real-world entities, within and across documents, actually represent the same concept. We will also discuss using these capabilities to search unstructured text and to integrate information extracted from unstructured data with existing institutional knowledge bases.
Discovering and analyzing topic patterns in text collections
- ChengXiang Zhai
- Associate Professor of Computer Science, UIUC
- Abstract: With the explosive growth of online information, we have an urgent need for powerful text mining tools to help us digest and exploit the huge amount of information. A common task occurring in many different applications is to extract topics from text collections (e.g., major topics covered in blog articles about "Hurricane Katrina") and analyze their variations over various kinds of context such as time, location, or sources (e.g., how the coverage of subtopics differs in different places or at different time). In this talk, I will present a suite of general methods for discovering topics and analyzing their variations in text collections. These methods are all based on probabilistic modeling of topics in text. They can be used either in an unsupervised manner to automatically learn topics and variations or in a semi-supervised manner to incorporate any user preferences. All the methods are general and can be applied to many different mining tasks, such as temporal text mining, spatiotemporal text mining, author-topic analysis, cross-collection comparative analysis, and sentiment summarization. Sample experiment results from these applications will be presented.
Entity Search: Finding Stuff on the Web, Directly and Holistically
- Kevin Chang
- Associate Professor of Computer Science, UIUC
- Abstract: What have you been searching lately? With so much data on the Web, we often search for various "stuff" (e.g., a phone number, a paper, a name, a date). However, current search engines only *indirectly* take us to pages. With the scale of the Web, the stuff that we are looking for usually appears in many pages, but current search engines find pages *individually*. In support of developing more direct and holistic search mechanisms, the Web Indexing and Search for Dynamic Mining (WISDM) project at the University of Illinois is building a new search system for finding our target "entities." For such entity search, I will motivate its query semantics, develop the search mechanism, and demonstrate the current prototype in several real-world application scenarios.
Real-Time Anomaly Mining in Massive Data Streams
- Jiawei Han
- Professor of Computer Science, UIUC
- Abstract: : Traditional data mining systems and methods assume that data resides on disks or in main memory, and a data mining process can scan the data sets multiple times to uncover interesting patterns. However, real-time systems and other dynamic environments often generate tremendous (potentially infinite) volumes of stream data in fast speed. Many applications require real time mining of unusual patterns in data streams, including finding unusual network or telecommunication traffic, real-time pattern mining in video surveillance, and detecting suspicious on-line transactions or terrorist activities. Recently there have been substantial growing research interests in developing methods for querying and mining stream data. In this talk, I will first present an overview of recent developments on stream data mining and outline what are the major challenging research problems for mining dynamics of data streams in multi-dimensional space. In particular, I will be addressing the following issues in detail: (1) multi-dimensional on-line analysis methods for discovering unusual patterns in stream data; (2) dynamic stream classification methods; and (3) mining clusters in stream data.
Exploring the Power of Links in Information Network Mining
- Jiawei Han
- Professor of Computer Science, UIUC
- Abstract: : Information network analysis has been studied extensively in web search with algorithms like PageRank and HITS invented that explore page links for discovery of authoritative web pages and hubs. We show that the power of links can be systematically explored in the mining of information networks for tasks like link-based classification, clustering, information integration, and veracity analysis. Some recent results of our research that explore the crucial information hidden in links will be introduced, including (1) multi-relational classification, (2) user-guided clustering, (3) link-based clustering, (4) object distinction analysis, and (5) veracity analysis. We will discuss how to apply these techniques for DHS applications as well. The technical material is based on one thesis of my students that has received ACM SIGKDD 2008 Dissertation Award.
Past Talks
More Data Less Work: SVM Training in Time Decreasing with Larger Data Sets
- Nathan Srebro
- TTI Chicago
- Abstract: Traditional runtime analysis of training Support Vector Machines, and indeed most learning methods, shows how the training runtime increases as more training examples are available. Considering the true objective of training, which is to obtain a good predictor, I will argue that training time should be studied as a decreasing function of training set size. I will then present both theoretical and empirical results demonstrating how a simple stochastic subgradient descent approach for training SVMs indeed displays such monotonic decreasing behavior. I will also discuss a similar phenomena in the context of Gaussian mixture clustering, where it appears that excess data turns the problem from computationally intractable to computationally tractable. Joint work with Shai Shalev-Shwartz, Yoram Singer, Greg Shakhnarovich and Sam Roweis.
Approximate Nearest Subspace Search with Applications to Pattern Recognition
- Ronen Basri
- TTI Chicago and Weizmann Institute
- Abstract: Linear and affine subspaces are commonly used to describe the appearance of objects under different lighting, viewpoint, articulation, and even identity. A natural problem arising from their use is -- given a query image portion represented as a point in some high dimensional space -- find a subspace near to the query. This talk presents an efficient solution to the approximate nearest subspace problem for both linear and affine subspaces. Our method is based on a simple reduction to the problem of nearest point search, and can thus employ tree based search or locality sensitive hashing to find a near subspace. Further speedup is achieved by using random projections to lower the dimensionality of the problem. We provide theoretical proofs of correctness and error bounds of our construction and demonstrate its capabilities on synthetic and real data. Our experiments demonstrate that an approximate nearest subspace can be located significantly faster than the exact nearest subspace, while at the same time it can find better matches compared to a similar search on points, in the presence of variations due to viewpoint, lighting etc. Joint work with Tal Hassner and Lihi Zelnik-Manor.
Speech Understanding as Sequence Estimation
- William Schuler
- University of Minnesota
-
Abstract: Spoken language interfaces for applications like home organizers, reminder systems, or immersive design may need to allow users to create new entities with names not found in existing training corpora, reducing the effectiveness of conventional techniques for estimating probabilities of hypothesized words. In such cases an `interactive' language model can be used to condition probabilities of successive words on the possible meanings of those words in the current application environment. These interpretations can be defined as vectors, corresponding to distributions over head words or sets of denoted individuals in a world model; then composed with relations, defined as matrices. Unfortunately, semantic composition is typically understood to conform to syntactic phrase structure, and set intersection or matrix multiplication are generally too expensive to be practical in conventional cubic-time chart parsers, used to hypothesize this phrase structure.
Psycholinguistic studies suggest an interactive model of human language processing that works somewhat differently: First, it seems to perform *incremental* interpretation of spoken utterances, identifying referents of words in an utterance even while these words are still being pronounced. Second, it seems to preserve ambiguity by maintaining competing interpretations in parallel. And third, it seems to operate within a severely constrained short-term memory store -- possibly constrained to as few as three or four distinct elements -- which limits the complexity of interactive recognition in a natural and computationally tractable way.
In this talk I will describe how these insights have been applied to the problem of real-time interactive speech interpretation, by modeling joint distributions over referents in an explicit three- or four-element memory store, using a factored HMM-like sequence model. First, I will present evidence that even a three-element model can obtain reasonably accurate syntactic recognition and nearly complete coverage on the large syntactically-annotated Penn Treebank corpus, using a simple reversible tree transform applied during training. I will then describe how this model can be applied directly to recognition of speech repairs (spontaneous edits by a speaker involving repeated words and corrections) without introducing any additional machinery. Then I will show how this framework can be extended to perform incremental interpretation by introducing a variable over referents at each memory element, with an evaluation in an implemented real-time speech interface. The talk will conclude with a description of an implementation of this model that supports references to arbitrary sets of individuals as well as individuals themselves, requiring very large or even unbounded random variable domains. - Bio: William Schuler graduated from the University of Pennsylvania in 2003 with a PhD in Computer and Information Science, and is now an Assistant Professor of Computer Science at the University of Minnesota. He has been studying psycholinguistically-motivated models of spoken language understanding for nearly ten years, funded since 2005 by a National Science Foundation CAREER grant. In 2006 his research program was awarded a Presidential Early Career Award for Scientists and Engineers (PECASE) in a ceremony at the White House. In 2007 he was awarded a McKnight Land-Grant Professorship by the University of Minnesota, consisting of a one-year research leave and funds to promote his research.
- Two articles (the former under review, the latter in press) describing the syntax and semantics of this model are available on my web site:
- http://www-users.cs.umn.edu/~schuler/paper-jcl08wsj.pdf
- http://www-users.cs.umn.edu/~schuler/paper-jcl07slush.pdf
Towards High-Quality Paraphrasing with CCG
- Michael White
- Ohio State University
-
Abstract: Research on automatic paraphrase generation has been gaining steam in recent years. Or in other words, research on generating paraphrases automatically has seen increasing progress lately. In this talk, I'll present our initial efforts on a project whose aim is to learn to generate such paraphrases using Combinatory Categorial Grammar (CCG), and to use this technology to improve MT evaluation. In the first part of the talk, I'll show how the OpenCCG surface realizer has been extended to efficiently generate paraphrases from disjunctive logical forms, or packed semantic representations, and sketch how this method enhances the prospects for learning to generate paraphrases with a reversible lexicalized grammar. In the second part of the talk, I'll describe our progress in scaling up OpenCCG for broad coverage realization using grammars extracted from an enhanced version of the CCGbank. In particular, I'll (1) discuss the importance of our method of supertagging, or lexical category prediction, for efficient surface realization, and (2) show how our efforts to improve the CCGbank by (i) more accurately projecting Propbank roles onto it and (ii) refining the analysis of punctuation has paid off in improved realization quality, as measured by BLEU scores and exact matches.
The talk will in part cover joint work with Stephen Boxwell, Dominic Espinosa, Scott Martin, Dennis Mehay and Rajakrishnan Rajkumar.
Optimizing Locomotion
- Russ Tedrake
- Abstract: In this talk I'll describe our efforts in using computational tools from optimal control theory (including machine learning and motion planning algorithms) to design efficient and agile control systems for locomotion. I'll start by describing the passive dynamics of walking, and demonstrate that approximate optimal control can be used to design nonlinear control solutions that allow minimally-actuated bipeds to walk efficiently and dynamically, even over rough terrain. In many cases, the performance of the algorithms can be improved dramatically by exploiting knowledge about the dynamics of the plant. Then I'll describe a new line of work applying these ideas to bird-scale aerial vehicles, and argue that model-free learning methods can design high-performance control solutions in even very complicated fluid dynamic regimes. Our initial evidence includes a robotic bird which flies with flapping wings and an airplane that can land on a perch.
- Bio: Russ Tedrake is the X Consortium Assistant Professor of Electrical Engineering and Computer Science at MIT, and a member of the Computer Science and Artificial Intelligence Lab. He received his B.S.E. in Computer Engineering from the University of Michigan, Ann Arbor, in 1999, and his Ph.D. in Electrical Engineering and Computer Science from MIT in 2004, working with Sebastian Seung. After graduation, he joined the MIT Brain and Cognitive Sciences Department as a Postdoctoral Associate. In 2008, he received an NSF CAREER award, the MIT Jerome Saltzer award for undergraduate teaching, and was named a Microsoft Research New Faculty Fellow.
- AIIS Seminar Series
Autonomous Web-scale Information Extraction
- Douglas Downey
- Assistant Professor, Northwestern
- Abstract: Search engines are extremely useful tools for answering questions. However, a significant number of questions users might pose -- for example, "which nanotechnology companies are hiring on the West Coast?" -- cannot be addressed using existing search engines, because the answers do not lie on a single page. To answer these kinds of queries, users must extract and synthesize information from multiple documents. Currently, this is a tedious and error-prone manual process. In this talk, I will describe my research aimed at automating the extraction of this information from the Web. I will present a model of the redundancy inherent in the Web, and show that the model can be used to identify correct extractions autonomously, without the manually labeled examples typically assumed in previous information extraction research. However, the model has limited efficacy for the "long tail" of infrequently mentioned facts; I demonstrate how unsupervised language models can be leveraged in concert with redundancy to overcome this limitation. Lastly, I will describe recent theoretical and experimental results illustrating that a generalization of the redundancy-based approach is effective for a variety of textual classification tasks, beyond information extraction.
- Bio: Doug Downey is an assistant professor in the EECS Department of Northwestern University, which he joined in the Fall of 2008. He obtained his PhD from the University of Washington, where he was advised by Oren Etzioni and supported by an NSF Fellowship and Microsoft Research Graduate Fellowship. His research interests are in the areas of natural language processing, machine learning, and artificial intelligence. At UW, he was part of the KnowItAll project, which was aimed at utilizing the Web to autonomously extract large knowledge bases. Doug's primary research results concern probabilistic models of the redundancy inherent in large corpora, along with associated techniques that allow systems like KnowItAll to extract data autonomously at high precision.
