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.

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.

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.

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.

: 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.

: 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.

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.

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.

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.

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.

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.