SUNMONTUEWEDTHUFRISAT
Conferences, Lectures, & Seminars
Events for January
-
GTHB Seminar
Tue, Jan 11, 2011 @ 12:00 PM - 01:30 PM
Thomas Lord Department of Computer Science
Conferences, Lectures, & Seminars
Speaker: Prof. Fan Chung Graham , Distinguished Professor of Mathematics, Distinguished Professor of Computer Science and Engineering,UCSD
Talk Title: Graph coloring games and memoryless voter models
Abstract: We analyze a network coloring game which can also describe a voter model. Each node represents a voter and is colored according to its preferred candidate, or undecided. Each hyperedge is a subset of nodes and can be viewed as a chat group. We consider interaction-based strategies involving chat groups: in each round of the game, one chat group is chosen randomly, and voters in the group can change colors based on informed discussion. We analyze the game as a random walk on the associated weighted directed state graph. Under certain `memoryless' conditions on the interaction strategies, the spectrum of the state graph can be explicitly determined and the random walk on the state graph converges to its stationary distribution in $O(m \log n)$ time, where $n$ denotes the number of voters and $m$ denotes the number of chat groups. This can then be used to determine the appropriate cut-off time for voting. For example, we show that the problem of estimating the probability that `blue' wins within an error bound of $\epsilon$ takes $O((\log 1/\epsilon) m \log n)$ rounds, provided the interaction strategies are memoryless.
This is a joint work with Alex Tsiatas and based on previous work with Ron Graham.
Biography: Fan Chung Graham received a B.S. degree in mathematics from National Taiwan University in 1970 and a Ph.D. in mathematics from the University of Pennsylvania in 1974, after which she joined the technical staff of AT&T Bell Laboratories. From 1983 to 1991, she headed the Mathematics, Information Sciences and Operations Research Division at Bellcore. In 1991 she became a Bellcore Fellow. In 1993, she was the Class of 1965 Professor of Mathematics at the the University of Pennsylvania. Since 1998, she has been a Professor of Mathematics and Professor of Computer Science and Enginering at the University of California, San Diego. She is also the Paul Erdos Professor in Combinatorics.
Her research interests are primarily in graph theory, combinatorics, and algorithmic design, in particular in spectral graph theory, extremal graphs, graph labeling, graph decompositions, random graphs, graph algorithms, parallel structures and various applications of graph theory in Internet computing, communication networks, software reliability, chemistry, engineering, and various areas of mathematics.
She was awarded the Allendoerfer Award by Mathematical Association of America in 1990. Since 1998, she has been a member of the American Academy of Arts and Sciences.
**Lunch served at 12pm. Talk begins at 12:10pm.
RSVP by Fri 1/7 to gthb-seminar@isi.edu.
Host: Prof. Milind Tambe, USC
Location: Seeley Wintersmith Mudd Memorial Hall (of Philosophy) (MHP) - 106
Audiences: Everyone Is Invited
Contact: Kanak Agrawal
-
CS Colloquium
Thu, Jan 13, 2011 @ 03:30 PM - 05:00 PM
Thomas Lord Department of Computer Science
Conferences, Lectures, & Seminars
Speaker: Dr. Zornitsa Kozareva, ISI, USC: Natural Language (Lexical Semantics)
Talk Title: Learning the Encyclopedia of the World using the Web
Abstract: How can we automatically build the Encyclopedia of the World, that will contain not only high-level information such as found in Wikipedia, but also particular facts such as "Who appeared in a concert in the Hollywood Bowl last night?" ?This is a challenging problem, which was never solved despite many have worked on it. In this talk, I will present novel algorithms for information gathering, sifting and organization that can rapidly, accurately and completely cover any area of interest mining unstructured text on the Web. I will describe a semi-supervised bootstrapping procedure, which uses a recursive lexico-syntactic pattern and an instance of a given semantic relation to scan billions of Web documents, and automatically harvest and taxonomize thousands to millions of new instances, facts and semantic relations. I will describe graph-based algorithms used to validate and rank the harvested knowledge. Finally, I will show that the algorithms (1) outperform state-of-the-art systems like KnowItAll and Yago, (2) enrich existing human-built knowledge repositories like WordNet, and (3) accurately reconstruct taxonomies starting from scratch. The developed search technology has shown that it is possible to begin the building of the Encyclopedia of the World and has opened up new directions for research.
Biography: Zornitsa Kozareva is a Research Scientist in the Natural Language group at the Information Sciences Institute, University of Southern California (USC/ISI). She received her PhD with Cum Laude from the University of Alicante, Spain. Her research interests lie in Web-based knowledge acquisition, text mining, lexical semantics, ontology population and multilingual information extraction. In 2010, Zornitsa co-organized one of the biggest challenges in the area of semantics called SemEval. She co-organized the CCIACADA/VACCINE Reconnect Conference. She was the leader of the team that won the answer validation challenge (AVE-2006) for French and Italian, and a member of the team that won the Spanish Geographic Information Retrieval (GeoClef-2006) challenge.
Host: Prof. Aiichiro Nakano
Location: SSL 150
Audiences: Everyone Is Invited
Contact: Kanak Agrawal
-
CS Colloquium
Tue, Jan 18, 2011 @ 03:30 PM - 05:00 PM
Thomas Lord Department of Computer Science
Conferences, Lectures, & Seminars
Speaker: Dr. David DeVault, USC Institute for Creative Technologies (ICT)
Talk Title: Toward flexible, robust, and rapid understanding of user speech in natural language dialogue systems
Abstract: This talk presents recent research that targets two of the major limitations in current natural language dialogue systems. One limitation is that while systems face substantial uncertainty in understanding user speech, they usually have only a rudimentary ability to overcome uncertainty in their dialogues. A second and related limitation arises from the fact that human speakers are by nature highly interactive while speaking, using incremental responses such as backchannels, interruptions, and overlapping speech to signal their understanding and resolve uncertainty when it arises. However, most implemented dialogue systems have little or no support for incremental interaction.
In the first part of the talk, I will present a probabilistic approach to dialogue management, called "contribution tracking", which I developed as a way to improve the flexibility of dialogue systems in overcoming uncertainty. On this approach, when faced with an ambiguous utterance, systems can spawn multiple threads of interpretation to track the likely meanings as the dialogue proceeds. I will highlight several concrete results and benefits of this approach in an implemented dialogue system that plays a collaborative reference game. These benefits include improved robustness to clarification failure, flexible aggregation of information across utterances with probabilistic inference, and the use of successful
ambiguity resolution to automatically improve the agent's understanding models with machine learning.
In the second part of the talk, I will present more recent work, carried out within the dialogue group at the USC Institute for Creative Technologies, which has aimed to enable incremental interaction and overlapping speech in our SASO-EN virtual humans. This work has created a data-driven approach to incremental understanding and prediction of user utterance meaning during user speech. Among the results I will discuss is a prototype system that often enables a virtual human to anticipate how a user's utterance will end, and to quickly generate and utter a completion of the user's utterance for them. (Joint work with Kenji Sagae and David Traum.)
Biography: David DeVault is a Research Scientist at the USC Institute for Creative Technologies (ICT), where he is a member of the natural language dialogue group. David obtained his Ph.D. from the Department of Computer Science at Rutgers University in 2008, and was a Postdoctoral Research Associate at USC/ICT from 2008-2010. David's research focuses on the development of techniques to enable dialogue systems to respond to the inevitable uncertainties of communication in a way that is more flexible, more robust, and more human-like. His work spans the areas of natural language understanding, dialogue management, and natural language generation.
Host: Prof. Kevin Knight
Location: Seaver Science Library (SSL) - 150
Audiences: Everyone Is Invited
Contact: Kanak Agrawal
-
An Optimization-Based Framework for Automated Market-Making
Wed, Jan 19, 2011 @ 10:00 AM - 11:30 AM
Thomas Lord Department of Computer Science
Conferences, Lectures, & Seminars
Speaker: Prof. Jenn Wortman Vaughan , UCLA
Talk Title: An Optimization-Based Framework for Automated Market-Making
Abstract: A prediction market is a financial market designed to aggregate information. To facilitate trades, prediction markets are often operated by automated market makers. The market maker trades a set of securities with payoffs that depend on the outcome of a future event. For example, the market maker might offer a security that will pay off $1 if and only if a Democrat wins the 2012 presidential election. A risk neutral trader who believes that the probability of a Democrat winning is p should be willing to purchase this security at any price below p, or sell it at any price above p. The current market price can then be viewed as the traders? collective estimate of how likely it is that a Democrat will win the election.
Market-based estimates have proved to be accurate in a variety of domains, including business, entertainment, and politics. However, when the number of outcomes is very large, it is generally infeasible to run a simple prediction market over the full outcome space. There has been a surge of recent research examining the tractability of running standard prediction market mechanisms (such as the popular Logarithmic Market Scoring Rule) over combinatorial outcome spaces by limiting the space of available securities. While this line of research has led to a few positive results, it has led more often to hardness results or to markets with undesirable properties such as unbounded worst case market maker loss.
We take a different approach. Building on ideas from convex optimization, we propose a general framework for the design of efficient prediction market mechanisms over very large or infinite outcome spaces. We start with an arbitrary space of securities with bounded payoff, and establish a framework to design markets tailored to this space. We prove that any market satisfying a set of intuitive conditions must price securities via a convex potential function and that the space of reachable prices must be precisely the convex hull of the security payoffs. We then show how the convex potential function can be defined in terms of an optimization over the convex hull of the security payoffs. The solution to the optimization problem gives the security prices. Using this framework, we provide an efficient prediction market mechanism for predicting the landing location of an object on a sphere. In addition, we show that we can relax our "no-arbitrage" condition to design a new eff icient market maker for "pair betting" on rank orderings, which is known to be #P-hard to price using existing mechanisms. This relaxation also allows the market maker to charge transaction fees so that the depth of the market can be dynamically increased as the number of trades increases.
This talk is based on joint work with Jake Abernethy and Yiling Chen.
Biography: Jenn Wortman Vaughan is an assistant professor in the Computer Science Department at UCLA. She completed her Ph.D. at the University of Pennsylvania in 2009. Before arriving at UCLA, she spent a year as a Computing Innovation Fellow at Harvard. Her research interests are in machine learning, algorithmic economics, social computing, and algorithms, all of which she studies using techniques from theoretical computer science. Her recent research has won several best student paper awards, as well as Penn's 2009 Rubinoff dissertation award for innovative applications of computer technology. In her spare time, she is involved in a variety of efforts to provide support for women in computer science; most notably, she co-founded the Annual Workshop for Women in Machine Learning, which was held for the fifth time this year.
Host: Prof. David Kempe
Location: Hedco Neurosciences Building (HNB) - Auditorium
Audiences: Everyone Is Invited
Contact: Kanak Agrawal
-
CS Colloquium
Thu, Jan 20, 2011 @ 03:30 PM - 05:00 PM
Thomas Lord Department of Computer Science
Conferences, Lectures, & Seminars
Speaker: Aleksander Madry , MIT
Talk Title: Electrical Flows and Laplacian Systems: A New Tool for Graph Algorithms
Abstract: In recent years, the emergence of massive computing tasks that arise in context of web applications and networks has made the need for efficient graph algorithms more pressing than ever. In particular, it lead us to focus on reducing the running time of the algorithms to make them as fast as possible, even if it comes at a cost of reducing the quality of the returned solution. This motivates us to expand our algorithmic toolkit to include techniques capable of addressing this new challenge.
In this talk, I will describe how treating a graph as a network of resistors and relating the combinatorial properties of the graph to the electrical properties of the resulting circuit provides us with a powerful new set of tools for the above pursuit. As an illustration of their applicability, I will use these ideas to develop a new technique for approximating the maximum flow in capacitated, undirected graphs that yields the asymptotically fastest-known algorithm for this problem.
Biography: Aleksander is a PhD candidate in Computer Science at MIT, advised by Michel Goemans and Jonathan Kelner. His research focuses on algorithmic graph theory, i.e. design and analysis of very efficient (approximation) algorithms for fundamental graph problems. He also enjoys investigating topics in combinatorial optimization - especially the ones involving dealing with uncertainty.
Host: Prof. David Kempe
Location: Seaver Science Library (SSL) - 150
Audiences: Everyone Is Invited
Contact: Kanak Agrawal
-
USC Water Institute Seminar
Fri, Jan 21, 2011 @ 11:00 AM - 12:00 PM
Thomas Lord Department of Computer Science
Conferences, Lectures, & Seminars
Speaker: Thomas C. Harmon, University of California, Merced & UCLA Center for Embedded Networked Sensing (CENS)
Talk Title: Whole Stream Metabolism as a Beacon for Change in Aquatic Ecosystems: Results from a Study of the Human-Dominated River Basin
Abstract: Metabolism estimates (gross primary production, GPP and community respiration, CR), based on the continuous monitoring of flow and water properties (primarily dissolved oxygen, temperature), can provide an integrative assessment of the effects of various disturbances on aquatic ecosystem function. The long-term goal of this work is to learn how to relate GPP/CR responses in lotic ecosystems to natural and anthropogenic disturbances, such as short- or long-term reservoir operational changes for drought management, flood control, fish habitat enhancement, or salinity and nutrient discharges due to land management practices. This presentation highlights observations from a GPP/CR observational network embedded in the human-dominated San Joaquin River Basin (SJRB) including reaches of the SJR and the Lower Merced River, located in the Central Valley of California. The network enables spatial (both longitudinal and transverse gradients) and temporal (daily, seasonal and interannual) variation of these metabolism estimates. The observational network will be described in terms of: (1) design and installation of a reproducible infrastructure of GPP/CR observational nodes, (2) analysis aimed linking the spatiotemporal metabolic trends to natural factors such as the seasonal radiation availability or nutrient input from leaf decay, and (3) separating natural effects from the ones triggered by human disturbances in order to better inform water resources management decisions. For example, observations over the 2009-10 water year, demonstrate that the Lower Merced River behaves as a heterotrophic system, with significant human-triggered temporal changes in metabolism clearly observable by the monitoring network. For example, the GPP/CR ratio decreased from 0.6 to 0.2 as a consequence of a large flow disturbance associated with short-term reservoir releases mandated biannually to support salmon migration. This and other examples set at different temporal and spatial scales will be presented and discussed in terms of management implications.
Biography: Tom Harmon is Professor and Chair of the School of Engineering and Founding Faculty member at the University of California, Merced. He is also affiliated with the Sierra Nevada Research Institute. He directs contaminant transport observation and management research for the UCLA Center for Embedded Networked Sensing (CENS), and maintains an adjunct position in the UCLA Department of Civil & Environmental Engineering. Professor Harmon earned a B.S. in Civil Engineering from the Johns Hopkins University, and M.S. and Ph.D. degrees in Environmental Engineering from Stanford University. As an environmental engineer, his teaching and research focuses on a variety of topics pertaining to understanding and solving soil, groundwater, and surface water problems in natural and engineered environmental systems.
Host: Prof. Gaurav Sukhatme
Audiences: Everyone Is Invited
Contact: Kanak Agrawal
-
CS Colloquium
Tue, Jan 25, 2011 @ 11:00 AM - 12:30 PM
Thomas Lord Department of Computer Science
Conferences, Lectures, & Seminars
Speaker: Tudor Dumitras, Senior Research Engineer, Symantec Research Lab
Talk Title: Improving the Dependability of Distributed Systems through AIR Software Upgrades
Abstract: Traditional fault-tolerance approaches concentrate almost entirely on responding to, avoiding, or tolerating unexpected faults or security violations. However, scheduled events, such as software upgrades, account for most of the system unavailability and often introduce data loss or latent errors. In this talk, I will present two empirical studies that identify the leading causes of upgrade failure---breaking hidden dependencies---and of planned downtime---hanging database schemas---in distributed enterprise systems. I will also describe Imago, a system that incorporates end-to-end mechanisms for improving the dependability of large-scale distributed systems that undergo major software upgrades.
The key idea is to isolate the production system from the upgrade operations in order to avoid breaking hidden dependencies. The end-to-end upgrade is an atomic operation, executed online even when performing complex schema and data conversions. Imago harnesses the opportunities provided by emerging technologies, such as cloud computing, to simplify major enterprise-system upgrades and to improve their dependability. This approach separates the functional aspects of the upgrade (e.g., data migration) from the mechanisms for online upgrade (e.g., atomic switchover), enabling an upgrade-as-a-service model.
Biography: Tudor Dumitras is a Senior Research Engineer at Symantec Research Labs. At SRL, he is building the Worldwide Intelligence Network Environment (WINE), which will enable researchers in academia to analyze field data, collected at Symantec. The goal of this project is to create a standard benchmark for cloud-security research. Tudor received a Ph.D. degree from Carnegie Mellon University. His prior research focused on improving the dependability of large-scale distributed systems (addressing operator errors during software upgrades), of enterprise systems (addressing the predictability of fault-tolerant middleware), and of embedded systems (addressing soft errors in networks-on-chip). He received the 2009 John Vlissides Award, from ACM SIGPLAN, for showing significant promise in applied software research, and the Best Paper Award at ASP-DAC'03. He holds undergraduate degrees from the Ecole Polytechnique in Paris and the "Politehnica" University in Bucharest.
Host: Prof. Ramesh Govindan
Location: Charles Lee Powell Hall (PHE) - 631
Audiences: Everyone Is Invited
Contact: Kanak Agrwal
-
CS Colloquium
Thu, Jan 27, 2011 @ 03:30 PM - 05:00 PM
Thomas Lord Department of Computer Science
Conferences, Lectures, & Seminars
Speaker: Dr. Donald Metzler, USC, Information Sciences Institute
Talk Title: Learning to Effectively and Efficiently Rank at Scale
Abstract: anking functions serve as the "brains" of modern search engines. Developing ranking functions that are both effective (i.e., produce highly relevant results) and efficient (i.e., produce a ranking in a short amount of time) is a challenging research problem, especially when dealing with large document collections, such as the Web. Machine learning has been shown to be useful for learning highly effective ranking functions, but such approaches typically do not consider efficiency costs which are critical in real applications. In this talk, I will provide an overview of the challenges of ranking at scale and describe my recent research into leveraging machine learning to yield effective and efficient ranking functions for information retrieval applications.
Biography: Donald Metzler is a Research Scientist in the Natural Language group at the University of Southern California's Information Sciences Institute. Prior to joining USC he was a Research Scientist in the Search and Computational Advertising group at Yahoo! Research. He obtained his Ph.D. from the University of Massachusetts in 2007. His research interests include information retrieval, Web search, computational advertising, and applications of machine learning to large-scale text problems. He is currently serving on the senior program committees of WWW and SIGIR. He has published over 35 research papers, has 16 patents pending, and is the co-author of Search Engines: Information Retrieval in Practice.
Host: Prof. Louis-Philipe Morency
Location: Seaver Science Library (SSL) - 150
Audiences: Everyone Is Invited
Contact: Kanak Agrawal
