February 2012 - talks - lists.cs.princeton.edu

8pm tonight: What Does It Mean To Be Literate in the Age of Google?
by Adam Finkelstein 28 Feb '12

28 Feb '12

This public lecture may be of interest: http://lectures.princeton.edu/2012/daniel-m-russell/ What Does It Mean To Be Literate in the Age of Google? Daniel M. Russell Über Tech Lead for Search Quality and User Happiness, Google February 28, 2012 Louis Clark Vanuxem Lecture What does it mean to be literate at a time when you can search over billions of texts in less than 300 milliseconds? Although you might think that “literacy” is one of the great constants that transcends the ages, the skills of a literate person have changed substantially over time as texts and technology allow for new kinds of reading and understanding. Knowing how to read is just the beginning of it—knowing how to frame a question, pose a query, how to interpret the texts that you find, how to organize and use the information you discover, how to understand your metacognition—these are all critical parts of being literate as well. In this talk Russell review what literacy is today, in the age of Google, and show how some very surprising and unexpected skills will turn out to be critical in the years ahead. Daniel M. Russell is the Über Tech Lead for Search Quality and User Happiness for Google where he studies how people search for and organize information. He earned his PhD in computer science at the University of Rochester (NY), specializing in artificial intelligence until he realized that magnifying and understanding human intelligence was his real passion. Twenty years ago he foreswore AI in favor of HI, and enjoys teaching, learning, running and music, preferably all in one day. He has worked at Xerox PARC before it was PARC.com, was in the Advanced Technology Group at Apple where he wrote the first 100 web pages for www.Apple.com using SimpleText. He has also worked at IBM as a senior research scientist, and briefly at a startup that developed tablet computers a few years before the iPad.

1 0

Colloquium speaker Alekh Agarwal Tuesday Feb 28 4:30pm
by Nicole E. Wagenblast 27 Feb '12

27 Feb '12

Computation meet Statistics: Trade-offs and fundamental limits Alekh Agarwal , University of California, Berkeley Tuesday, February 28, 2012 , 4:30 PM Computer Science Small Auditorium (Room 105) The past decade has seen the emergence of datasets of an unprecedented scale, with both large sample sizes and dimensionality. Massive data sets arise in various domains, among them computer vision, natural language processing, computational biology, social networks analysis and recommendation systems, to name a few. In many such problems, the bottleneck is not just the number of data samples, but also the computational resources available to process the data. Thus, a fundamental goal in these problems is to characterize how estimation error behaves as a function of the sample size, number of parameters, and the computational budget available. In this talk, I present two research threads that provide complementary lines of attack on this broader research agenda: lower bounds for statistical estimation with computational constraints, and (ii) distributed algorithms for statistical inference. The first characterizes fundamental limits in a uniform sense over all methods, whereas the latter provides explicit algorithms that exploits the interaction of computational and statistical considerations in a distributed computing environment. [Joint work with John Duchi, Pradeep Ravikumar, Peter Bartlett and Martin Wainwright] Alekh Agarwal is a fifth year PhD student at UC Berkeley, jointly advised by Peter Bartlett and Martin Wainwright. Alekh has received PhD fellowships from Microsoft Research and Google. His main research interests are in the areas of machine learning, convex optimization, high-dimensional statistics, distributed machine learning and understanding the computational trade-offs in machine learning problems.

1 1

4:30pm Thu Mar 1 talk by Prateek Mittal in E-Quad B205
by Jennifer Rexford 24 Feb '12

24 Feb '12

> > > Speaker: > Prateek Mittal, UIUC > Title: > Trustworthy Communications Using Social Networks > Day: > Thursday, March 1, 2012 > Time: > 4:30 pm > Room: > B205, E-Quad > > Abstract: > Internet systems and applications are shifting towards a participatory paradigm, where users contribute content and resources. Popular examples include reputation systems such as Yelp, peer-to-peer networks, Web 2.0 applications like Wikipedia, and online forums such as Slashdot. These applications, however, struggle with the concepts of identity and trust, as it is easy to create a large number of pseudonyms (called Sybils) that join the system and disrupt its functionality. In this talk, I will outline two mechanisms for defending against the Sybil attack. A common theme in these mechanisms is the use of social network trust relationships to validate user identities. Such an approach forces the adversary to inﬁltrate users’ trusted social circles, presenting a signiﬁcant barrier for attack. > > First, I will present SybilInfer, an algorithm for labeling nodes in a social network as honest users or Sybils controlled by an adversary. SybilInfer uses a combination of Bayesian inference and Monte-Carlo techniques to perform a global analysis of the entire social graph to isolate attackers. Second, I will present X-Vine, a mechanism that enables users in a social network to efficiently communicate with each other, while resisting Sybil attacks. X-Vine is scalable, preserves the privacy of users’ social network contacts, and provides a basis for pseudonymous communication. Finally, I will conclude by highlighting the potential for leveraging social networks in the design of trustworthy communication systems that improve user security and privacy. > > Bio: > Prateek Mittal is a Ph.D. Candidate in Electrical and Computer Engineering at the University of Illinois at Urbana-Champaign. His research in security and privacy focuses on computer networks and distributed systems, with an emphasis on social networks and Internet protocols. He is also interested in applications of network modeling and analysis techniques to interdisciplinary settings, especially cancer genomics. He received the M.E. Van Valkenburg graduate research award for outstanding doctoral research, the Rambus Computer Engineering fellowship, and the ACM CCS 2008 outstanding paper award. He earned his M.S. in Electrical and Computer Engineering at the University of Illinois at Urbana-Champaign and a B.Tech. in Computer Science and Engineering at the Indian Institute of Technology, Guwahati. > > Host: Ruby Lee > > > > > > > > >

1 0

S Gerrish preFPO
by Melissa M. Lawson 23 Feb '12

23 Feb '12

Sean Gerrish will present his preFPO on Wednesday February 29 at 2:30PM in Room 402. The members of his committee are: David Blei, advisor; Rob Schapire and Hanna Wallach (UMass), readers; Kosuke Imai (POL) and Matthew Salganik (SOC), nonreaders. Everyone is invited to attend his talk. His abstract follows below. --------------------------- Title: Patterns of influence and decision-making in politics and foreign relations The past several decades have seen an explosion of digitized information in fields such as political science. In this period, a variety of statistical tools have been developed to better understand patterns in these records by incorporating information such as records of behavior and the text of documents. In this talk, I will present several recent statistical models for discovering patterns in digital records in the fields of politics, bibliometrics, and international relations. These models, which emphasize topic modeling, will link legislative text to voting patterns, written judges' opinions to citations of these opinions, and the text of newspaper articles to countries' international relations. I will also describe details of approximate posterior inference for these models, and will briefly touch upon advances in such methods. This talk includes ongoing work.

1 0

Colloquium Speaker Alekh Agarwal TuesFeb 28, 4:30pm
by Nicole E. Wagenblast 22 Feb '12

22 Feb '12

Computation meet Statistics: Trade-offs and fundamental limits Alekh Agarwal , University of California, Berkeley Tuesday, February 28, 2012 , 4:30 PM Computer Science Small Auditorium (Room 105) The past decade has seen the emergence of datasets of an unprecedented scale, with both large sample sizes and dimensionality. Massive data sets arise in various domains, among them computer vision, natural language processing, computational biology, social networks analysis and recommendation systems, to name a few. In many such problems, the bottleneck is not just the number of data samples, but also the computational resources available to process the data. Thus, a fundamental goal in these problems is to characterize how estimation error behaves as a function of the sample size, number of parameters, and the computational budget available. In this talk, I present two research threads that provide complementary lines of attack on this broader research agenda: lower bounds for statistical estimation with computational constraints, and (ii) distributed algorithms for statistical inference. The first characterizes fundamental limits in a uniform sense over all methods, whereas the latter provides explicit algorithms that exploits the interaction of computational and statistical considerations in a distributed computing environment. [Joint work with John Duchi, Pradeep Ravikumar, Peter Bartlett and Martin Wainwright] Alekh Agarwal is a fifth year PhD student at UC Berkeley, jointly advised by Peter Bartlett and Martin Wainwright. Alekh has received PhD fellowships from Microsoft Research and Google. His main research interests are in the areas of machine learning, convex optimization, high-dimensional statistics, distributed machine learning and understanding the computational trade-offs in machine learning problems.

1 0

Colloquium Speaker Michael Bernstein Wed Feb 22 4:30pm
by Nicole E. Wagenblast 21 Feb '12

21 Feb '12

Crowd-Powered Systems Michael Bernstein , MIT Wednesday, February 22, 2012 , 4:30 PM - 5:30 PM Computer Science Small Auditorium (Room 105) Crowd-powered systems combine computation with human intelligence, drawn from large groups of people connecting and coordinating online. These hybrid systems enable applications and experiences that neither crowds nor computation could support alone. Unfortunately, crowd work is error-prone and slow, making it difficult to incorporate crowds as first-order building blocks in software systems. I introduce computational techniques that decompose complex tasks into simpler, verifiable steps to improve quality, and optimize work to return results in seconds. These techniques advance crowdsourcing into a platform that is reliable and responsive to the point where crowds can be used in interactive systems. In this talk, I will present two crowd-powered systems to illustrate these ideas. The first, Soylent, is a word processor that uses paid micro-contributions to aid writing tasks such as text shortening and proofreading. Using Soylent is like having access to an entire editorial staff as you write. The second system, Adrenaline, is a camera that uses crowds to help amateur photographers capture the exact right moment for a photo. It finds the best smile and catches subjects in mid-air jumps, all in realtime. These systems point to a future where social and crowd intelligence are central elements of interaction, software, and computation. Michael Bernstein is a PhD candidate in Computer Science at the Massachusetts Institute of Technology. His research in human-computer interaction focuses on crowdsourcing and social computing systems. He has been awarded Best Student Paper at UIST 2010, Best Paper at ICWSM 2011, the NSF graduate research fellowship and the Microsoft Research PhD fellowship. His work has appeared in venues like the New York Times, Slate, CNN and The Atlantic. He earned his masters in Computer Science at MIT, and a bachelors degree in Symbolic Systems at Stanford University.

1 1

Colloquium Speaker Ohad Shamir Tues Feb 21 4:30pm
by Nicole E. Wagenblast 17 Feb '12

17 Feb '12

Machine Learning: Higher, Faster, Stronger Ohad Shamir , Microsoft Research New England Computer Science Small Auditorium (Room 105) Tuesday, February 21, 2012 , 4:30 PM - 5:30 PM Over the past decade, machine learning has emerged as a major and highly influential discipline of computer science and engineering. As the scope and variety of its applications increase, it faces novel and increasingly challenging settings, which go beyond classical learning frameworks. In this talk, I will present two recent works which fall under this category. The first work introduces a new model of sequential decision making with partial information. The model interpolates between two well-known online learning settings ("experts" and multi-armed bandits), and trades-off between the information obtained per round and the total number of rounds required to reach the same performance. The second work discusses the problem of parallelizing gradient-based learning algorithms, which is increasingly important for web-scale applications, but is highly non-trivial as these algorithms are inherently sequential. We show how this can be done using a generic and simple protocol, prove its theoretical optimality, and substantiate its performance experimentally on large-scale data. Ohad Shamir is a postdoctoral researcher at Microsoft Research New England. He joined Microsoft in 2010 after receiving a Ph.D. in computer science from the Hebrew university, advised by Prof. Naftali Tishby. His research focuses on machine learning, with emphasis on novel algorithms which combine practical applicability and theoretical insight. His work was recognized by several awards, such as the Hebrew University's Schlomiuk Ph.D. thesis prize, the COLT 2010 best paper award, and the Wolf foundation scholarship.

1 0

B Kapicioglu preFPO
by Melissa M. Lawson 16 Feb '12

16 Feb '12

Berk Kapicioglu will present his preFPO on Wednesday February 22 at 11AM in Room 402. The members of his committee are: Rob Schapire, advisor; David Blei and Tony Jebara (Columbia), readers; Jennifer Rexford and Andrea LaPaugh, nonreaders. Everyone is invited to attend his talk. His abstract follows below. ----- Original Message ----- Title: Applications of Machine Learning to Location Data. Abstract: First, we introduce a new graphical model for tracking radio-tagged animals and learning their movement patterns. The model provides a principled way to combine radio telemetry data with an arbitrary set of user-deﬁned, spatial features. We describe an efﬁcient stochastic gradient algorithm for ﬁtting model parameters to data and demonstrate its eﬀectiveness via asymptotic analysis and synthetic experiments. We also apply our model to real datasets, and show that it outperforms the most popular radio telemetry software package used in ecology. We conclude that integration of different data sources under a single statistical framework, coupled with appropriate parameter and state estimation procedures, produces both accurate location estimates and an interpretable statistical model of animal movement. Second, we present the “Place Discovery” problem, where the goal is to provide a context-dependent and personalized ranking of nearby places. To the best of our knowledge, we are the first to pose this as a machine learning problem. We provide a new matrix approximation algorithm that leverages implicit bipartite ranking and spatial constraints. We demonstrate on real location datasets that our methods significantly improve on the amount of personalization achieved by state-of-the-art matrix approximation methods, such as Maximum-Margin Matrix Factorization. Lastly, we talk about “Location Prediction”. Here, the goal is to predict the coordinates (i.e. latitude and longitude) of a user at an arbitrary time in the future. We design an unsupervised hierarchical Bayesian graphical model for location prediction that learns natural topics such as home and work from unlabeled location data. We apply our model both to data gathered from mobile applications, where there are many users but each user has sparse location points, and to data gathered from cellular carriers. Our model outperforms existing methods in both cases.

1 0

P Jiang preFPO
by Melissa M. Lawson 13 Feb '12

13 Feb '12

Peng Jiang will present his preFPO on Friday February 17 at Noon in Lewis Thomas Lab 118 (note location). The members of his committee are: Mona Singh, advisor; Hilary Coller (MOL) and Olga Troyanskaya, readers; Leonid Kruuglyak (Genomics) and Bernard Chazelle, nonreaders. Everyone is invited to attend his talk. His abstract follows below. ----- Original Message ----- Title: Computational Analysis of Transcriptional and post-Transcriptional regulation Abstract: Transcription factors (TFs) and miRNAs are regulators for a wide range of biological processes. While binding speciﬁcities for numerous D. melanogaster TFs have been experimentally determined, the genomic binding targets for the majority of them are unknown, with even less known about the transcriptional regulators of miRNAs and the network-level interplay between TFs and miRNAs. We computationally constructed a large-scale transcriptional regulatory network for D. melanogaster. Based on several lines of experimental data, we annotated the transcription start sites for 37 integenic miRNAs. We uncovered conserved binding sites for TFs with known speciﬁcities in promoters of miRNAs and protein-coding genes. The inferred D. melanogaster transcriptional network is the largest to date, and consists of regulatory targets for 267 TFs, covering 56 intergenic miRNA loci and 11,232 protein-coding genes. Using this network, we predicted GO biological processes for miRNAs based upon their upstream regulators and downstream targets. Finally, we found that the network exhibits a surprisingly diverse array of network motifs consisting of both miRNAs and TFs. On the level of post-Transcriptional regulation, transcript degradation is a widespread and important mechanism for regulating protein abundance. Two major regulators of transcript degradation are RNA Binding Proteins (RBPs) and microRNAs (miRNAs). We computationally explored whether RBPs and miRNAs cooperate to promote transcript decay. We defined five RBP motifs based on the evolutionary conservation of their recognition sites in 3' UTRs as the binding motifs for Pumilio (PUM), U1A, Fox-1, Nova, and AU-rich element (ARE) binding proteins. Recognition sites for some of these RBPs tended to localize at the beginning or end of 3' UTRs. A specific group of miRNA recognition sites were enriched within 50 nts upstream and downstream of the RBP recognition sites of PUM, ARE, Fox-1 and U1A. The presence of both a PUM recognition site and a recognition site for preferentially co-occurring miRNAs was associated with faster decay of the associated transcripts. For PUM and its co-occurring miRNAs, binding of the RBP to its recognition sites was predicted to rescue nucleotides within nearby miRNA recognition sites from hybridization with other nucleotides at a higher rate than expected. miRNAs that preferentially co-occur with PUM binding sites tended to have recognition sites that are reverse complements to the PUM recognition motif. These sites have the potential to form hairpin secondary structures that would normally limit RISC accessibility, but would be more accessible to miRNAs in response to the binding of PUM. In sum, our computational analyses suggest that PUM can coordinately fine-tune the accessibility of multiple microRNA recognition sites.

1 0

11am Tue Feb 7 talk on distributed streaming algorithms
by Jennifer Rexford 07 Feb '12

07 Feb '12

Speaker: Zhenming Liu, Harvard Title: Continuous Distributed Counting for Non-monotonic Streams Date/time: 11am-noon, Tuesday February 7 Location: room 302 in the CS building Abstract: We consider the problem of tracking a sum of values in a distributed environment where the input values arrive from k distributed streams. It is required that an estimate of the sum is maintained by a coordinator node that is within a prescribed relative error tolerance, at any time with high probability. The goal is to achieve such objective with small total communication with the coordinator node, in order to minimize the use of network bandwidth that may be a scarce resource. This is a basic distributed computation problem that is of interest for various applications including data aggregation and iterative solving of various computational problems. Specifically, we consider a setting where the input values are selected and assigned to sites by an adversary but the arrival order of the input items is random. We show a randomized protocol with a sub-linear total communication with respect to the number of updates and its matching lower bound. This result stands in between the previously known results that for monotonic partial sums (all value updates either positive or negative), the expected total communication is logarithmic in the number of updates, and that for general worst-case inputs, the total required communication is linear in the number of updates. Finally, we also discuss applications of the sum tracking module for tracking the second frequency moment and for solving a Bayesian linear regression. Bio: Zhenmin Liu is a PhD candidate in the theory of computation group at Harvard, working with Michael Mitzenmacher. His research focuses on stochastic processes, optimization, and algorithm design, as well as their applications to distributed computation and big data analytics.

1 0