Colloquium

"Digital divide" vs."melting pot", "great liberator" vs."social stratifier". In all of the rhetoric comparing Internet use among diverse populations, remarkably little attention has been paid to the voices of the users themselves. In this talk I will discuss an on-line community designed to unite over 3000 young people from 139 countries, and the research analyzing their on-line discourse over a period of five years. The participants, aged 10 to 16, spoke many different languages and represented a wide variety of economic and cultural backgrounds. Without ever seeing each other face-to-face, and in a community almost entirely free of adult intervention, these young people traded messages, and then elected leaders to represent their community in a real-world meeting in Boston with political and industry leaders from around the world. I will discuss results from our empirical study on the linguistic style differences and language cues that predict who was elected a leader on-line. Results demonstrate the ways in which leadership and community involvement for these young people on-line takes on very different forms from that prized by adults, and from that described for young people in the face-to-face world. This lecture is part of the /@rts series which explores interrelations of new technologies and traditional practices of arts and humanities.

For more information about this lecture, /@rts the series and sponsoring organizations, please visit our website: http://www.princeton.edu/slasharts

An important, open vision problem is to automatically describe what people are doing in a sequence of video. This problem is difficult for several reasons. First, one needs to determine how many people (if any) are in each frame and estimate their configurations (where they are and what their arms and legs are doing). But finding people and localizing their limbs is hard because people (a) wear a variety of different clothes, (b) appear in a variety of poses and (c) tend to partially occlude themselves and each other. Secondly, one must sew together estimated configuration reports from across frames into a motion path; this is tricky because people can move fast and unpredictably. Finally, one must describe what each person is doing; this problem is poorly understood, not least because there is no natural or canonical set of categories into which to classify activities. In this talk I will discuss our progress on this problem. We develop a tracker that works in two stages; i t first (a) builds a model of appearance of each person in a video and then (b) tracks by detecting those models in each frame ("tracking by model-building and detection"). We then marry our tracker with a motion synthesis engine that works by re-assembling pre-recorded motion clips. The synthesis engine generates new motions that are human-like and close to the image measurements reported by the tracker. By using labeled motion clips, our synthesizer also generates activity labels for each image frame ("analysis by synthesis"). We have extensively tested our system, running it on hundreds of thousands of frames of unscripted indoor and outdoor activity, a feature-length film, and legacy sports footage.

Managing large and growing collections of information is a central goal of modern computer science. Data repositories of texts, images, music, and genetic information have become widely accessible, necessitating good methods of retrieval, organization, and exploration. In this talk, I will describe probabilistic models of information collections, for which the above problems can be cast as statistical queries.

First, I will describe the use of graphical models as a flexible framework for the representation of modeling assumptions. Fast posterior inference algorithms based on variational methods allow us to specify complex Bayesian models and apply them to large datasets.

With this framework in hand, I will develop latent Dirichlet allocation (LDA), a graphical model particularly suited to analyzing text collections. LDA posits an index of hidden topics which describe the underlying documents. The topics are learned from a collection, and new documents can be situated into that collection via posterior inference. Extensions of LDA can index a set of images, or multimedia collections of related text and images. I will illustrate the use of such models with several datasets.

Finally, I will describe nonparametric Bayesian methods for relaxing the restriction to a fixed number of topics. These methods allow for models based on the natural assumption that the number of topics grows with the collection. I will extend this idea to trees, and to models for discovering both the structure and content of a topic hierarchy.

Joint work with Michael Jordan, Andrew Ng, Thomas Griffiths, and Josh Tenenbaum

Over the last few years, product groups at Microsoft have increasingly relied on automated defect detection tools to find software failures before releasing products to customers. In this talk, I will describe how a small set of program analysis / compiler geeks have tried to change the way we build software. In particular, I'll talk about a new approach to defect detection that involves the use of simple but effective specifications, automatic inference of specifications, powerful defect detection tools, and plenty of good old fashioned software engineering process.

Bio

Zhe Yang works in the Center for Software Excellence at Microsoft Corporation, where he leads the Engine development in the Program Analysis research group. This group is responsible for building innovative tools that help programmers, both within Microsoft and elsewhere, improve the quality of the software they create. Zhe Yang received a bachelor's degree from Shanghai Jiao Tong University and a PhD from New York University.

User Interfaces for Information Visualization"* *Human perceptual skills are remarkable, but largely underutilized by current graphical user interfaces. The next generation of animated GUIs and visual data mining tools can provide users with remarkable capabilities if designers follow the Visual Information-Seeking Mantra: Overview first, zoom and filter, then details-on-demand Then dynamic queries allow user control of widgets, such as sliders and buttons that update the result set within 100msec. Seven types of information visualizations (1-, 2-, 3-, multi-dimensional data, temporal, tree and network data) will be shown in examples for U.S. Census, time series searching, and gene expression data. Commercial success stories based on our early work include multi-dimensional data in dynamic scattergrams (www.spotfire.com), hierarchical stock market data in treemaps (www.smartmoney.com/marketmap), and production monitoring/product catalogs in treemaps (www.hivegroup.com).

This talk will emphasize scientific and statistical data analysis such as gene expression studies, multi-variate temporal data sets, and hierarchical clustering. For more info and to download programs, visit: www.cs.umd.edu/hcil/treemap www.cs.umd.edu/hcil/timesearcher www.cs.umd.edu/hcil/hce

Large-scale distributed systems are hard to deploy, and distributed hash tables (DHTs) are no exception. To lower the barriers facing DHT-based applications, we have created a public DHT service called OpenDHT. Designing a DHT that can be widely shared, both among mutually-untrusting clients and among a variety of applications, poses two distinct challenges. First, there must be adequate control over storage allocation so that greedy or malicious clients do not use more than their fair share. Second, the interface to the DHT should make it easy to write simple clients, yet be sufficiently general to meet a broad spectrum of application requirements. In this talk I will describe our solutions to these design challenges. I'll also report on our early deployment experiences with OpenDHT and describe the variety of applications already using the system.

Network models for game theory and economics provide a powerful framework for studying strategic interactions in large population settings. The semantics of these networks are that nodes represent parties (e.g. players or consumers) and edges represent strategic or economic interactions. These models allow the incorporation of rich structure into the network, allowing the promise of increased applicability of strategic reasoning to large, complex systems.

In this talk, I will present algorithms and learning models for game theoretic and economic equilibria --- focusing on how the network structure influences the learning process and the outcomes. This work highlights many natural connections to AI and modern probabilistic modeling. I will also provide results at the intersection of this line of study and topics in social network theory.

This is joint work with Dean Foster, Michael Kearns, John Langford, Luis Ortiz, Robin Pemantle, and Siddharth Suri.

Today's Internet is at risk. A single misbehaving router--whether through misconfiguration or malicious intent--can hijack routes, bringing down over a third of the Internet. This critical vulnerability stems from the pervasive assumption inherent in existing protocols that any information propagated by routers is correct. Emerging security proposals for Internet routing require a public key infrastructure and a trusted central authority, and thus are unlikely to see wide deployment.

In this talk, I will first describe Listen and Whisper, two decentralized and deployable security mechanisms that improve the security of the Border Gateway Protocol (BGP), the current inter-domain routing protocol. Their combination eliminates the threat of route hijacking due to misconfigurations and restricts the damage that deliberate attackers can cause. Using a real-world deployment of these mechanisms within the Berkeley campus network, we have been able to detect several routing anomalies.

Then, I will show how these techniques can be extended to provide a foundational suite of security primitives to achieve secure routing in an arbitrary network against a bounded number of adversaries. These techniques address two open theoretical problems: (a) Under what constraints can one achieve decentralized key distribution given a bounded number of adversaries? (b) When can one achieve Byzantine agreement if the underlying graph is not known to the nodes?

Bio

Lakshminarayanan Subramanian is currently a PhD candidate at UC Berkeley working with Professors Randy H. Katz, Ion Stoica and Scott Shenker. He received an M.S. in Computer Science from UC Berkeley in 2002 and a B.Tech in Computer Science from the Indian Institute of Technology, Madras in 1999. His research interests are in the areas of networking and distributed systems with specific emphasis on routing, network security, Internet architecture, overlay networks and quality of service.

A central open question of computational neuroscience is to identify the data structures and algorithms that are used in mammalian cortex to support successive acts of the basic cognitive tasks of memorization and association. This talk addresses the simultaneous challenges of realizing these two distinct tasks with the same data structure, and doing so while respecting the following four basic quantitative parameters of cortex, the neuron number, the synapse number, the synapse strengths, and the switching times. Previous work apparently had not succeeded in reconciling all these opposing constraints, the low values of synapse strengths that are typically observed experimentally having contributed a particular obstacle. We describe a computational scheme that supports both memory formation and association, and is feasible on networks of model neurons that respect the widely observed values of the above-mentioned four quantitative parameters. Our scheme allows for both disjoint and shared representations. The algorithms are simple, and in one version both memorization and association require just one step of neighborly influence. The issues of interference among the different circuits that are established, of robustness to noise, and of the stability of the hierarchical memorization process are addressed. A calculus, therefore, is implied for analyzing the capabilities of particular neural systems and subsystems, in terms of their basic numerical parameters.