- talks - lists.cs.princeton.edu

Colloquium Speaker Yoram Singer, Mon Feb 9, 4:30pm
by Nicole E. Wagenblast 08 Feb '15

08 Feb '15

Colloquium Speaker Yoram Singer, Google Research Monday, February 9, 4:30pm Computer Science 105 Learning compact models from high dimensional large datasets I review the design, analysis, and implementation of stochastic optimization techniques, online algorithms, and modeling approaches for learning in high dimensional spaces using large amounts of data. The focus is on algorithms and models that are efficient, accurate, and yield compact models. Concretely, the forward-backward shrinkage algorithm (Fobos), mirror descent for learning composite objectives (COMID), and the adaptive gradient (AdaGrad) algorithm. We also discuss simple yet effective modeling approaches based on locality for learning from high dimensional data. Yoram Singer is a senior research scientist at Google. From 1999 through 2007 he was an associate professor at the Hebrew University of Jerusalem. From 1995 through 1999 he was a member of the technical staff at AT&T Research. He was the co-chair of the conference on Computational Learning Theory (COLT) in 2004 and of Neural Information Processing Systems (NIPS) in 2007. He serves as an editor of the Journal of Machine Learning, IEEE Signal Processing Magazine, and IEEE Trans. on Pattern Analysis and Machine Intelligence.

1 0

Tianqiang Liu's preFPO Feb. 10 at 10am in CS rm 301.
by Nicki Gotsis 06 Feb '15

06 Feb '15

Tianqiang Liu's will present his PreFPO on Feb. 10 at 10am in CS rm 301. The members of his committee are below: Advisor: Thomas Funkhouser Readers: Szymon Rusinkiewicz, Wilmot Li (Adobe System) Non-readers: Adam Finkelstein, Jianxiong Xiao Everyone is invited to attend his talk. The talk title and abstract follow below: Title: Analyzing, Optimizing and Synthesizing Scenes by Reasoning About Relationships Between Objects Abstract: Large numbers of virtual 3D scenes have been widely used for various applications, such as video games, movies, and creation of product images for furniture catalogs, which leads to an enormous demand for scene modeling. On the one hand, manually modeling 3D scenes is extremely tedious, which requires selecting and placing hundreds of objects even for a single scene. On the other hand, a data-driven approach to 3D scene modeling is also challenging, due to the large variabilities in 3D scenes (e.g. object classes and object placement), and the hardness of maintaining plausibility of 3D scenes (e.g. relative positions and style compatibility between objects). In this thesis, we utilize relationships between objects as cues to address three problems in scene understanding and scene synthesis. First, we develop an algorithm to consistently segment and annotate 3D scenes in online repositories by using a probabilistic grammar learned from examples. Our grammar encodes the geometry priors of object classes and spatial relationships between objects within a semantic group. During experiments with these algorithms, we find our algorithm outperforms alternative approaches that consider only shape similarities and/or spatial relationships without considering semantic groups. Second, we develop a tool to optimize a 3D scene in order to create an aesthetically appealing composition for it. Recently, companies are creating product advertisements and catalog images using computer renderings of 3D scenes. However, this is challenging, not only due to the need to balance the trade-off among aesthetic principles and design constraints, but also because of the huge search space induced by possible camera parameters, object replacement, material choices, etc.. In this work, we identify a set of composition rules by constraining the relationships between objects in the scene space as well as the image space, and develop algorithms to optimize the 2D composition by changing the camera view, object placement and materials. The value of this tool is demonstrated in a variety of applications motivated by product catalogs. Third, we learn a style compatibility metric for furniture models and develop style-aware suggestion systems. Existing tools for selecting models for synthesizing 3D scenes generally ignore style compatibility between objects, and presence of incompatible styles diminishes the plausibility of the resultant 3D scenes. In this work, we develop a mathematical representation of style compatibility between objects that can be used to guide 3D scene modeling tools. During experiments, we find our method is effective at predicting style compatibility agreed upon by people, and we find in user studies that the learned compatibility metric is useful for novel interactive tools.

1 0

Colloquium Speaker Peter Bailis, Thurs Feb 12, 12:30pm
by Nicole E. Wagenblast 06 Feb '15

06 Feb '15

Colloquium Speaker Peter Bailis, UC Berkeley Thursday February 12, 12:30pm Computer Science 105 Coordination Avoidance in Distributed Databases The rise of Internet-scale geo-replicated services has led to considerable upheaval in the design of modern data management systems. Namely, given the availability, latency, and throughput penalties associated with classic mechanisms such as serializable transactions, a broad class of systems (e.g., "NoSQL") has sought weaker alternatives that reduce the use of expensive coordination during system operation, often at the cost of application integrity. When can we safely forego the cost of this expensive coordination, and when must we pay the price? In this talk, I will discuss the potential for coordination avoidance -- the use of as little coordination as possible while still ensuring application integrity -- in several modern data-intensive domains. Specifically, I will demonstrate how to leverage the semantic requirements of applications in data serving, transaction processing, and statistical analytics to enable more efficient distributed algorithms and system designs. The prototype systems I have built demonstrate order-of-magnitude speedups compared to their traditional, coordinated counterparts on a variety of tasks, including referential integrity and index maintenance, transaction execution under common isolation models, and asynchronous convex optimization. I will also discuss our experiences studying and optimizing a range of open source applications and systems, which exhibit similar results. Peter Bailis is a Ph.D. candidate at UC Berkeley working in databases and distributed systems. As part of his dissertation work, he has studied and built high performance distributed data management systems for large scale transaction processing, data serving, and statistical analytics in the AMPLab and BOOM projects under the advisement of Joseph M. Hellerstein, Ali Ghodsi, and Ion Stoica. He is the recipient of the NSF Graduate Research Fellowship, the Berkeley Fellowship for Graduate Study, and best-of-conference citations for research appearing in both SIGMOD and VLDB. He received his A.B. in Computer Science from Harvard College in 2011, where he also received the CRA Outstanding Undergraduate Researcher Award.

1 0

Colloquium Speaker Omer Reingold, today, 12:30pm
by Nicole E. Wagenblast 04 Feb '15

04 Feb '15

Colloquium Speaker Randomness Vs. Memory: A Treasure(s) Hunt Omer Reingold, Weizmann Institute of Science Wednesday, February 4, 12:30pm Computer Science 105 Randomness Vs. Memory: A Treasure(s) Hunt Randomness plays a major role in computation, allowing the execution of tasks that would otherwise be impossible or prohibitively inefficient. Yet the relative power of randomness compared with other resources of computation is mostly unresolved. In this talk we will address the tradeoff between memory and randomness. Namely, can randomness signiﬁcantly reduce the amount of memory needed for algorithmic tasks? This is one of the central problems in Computational Complexity and its study is tied with the study of pseudorandom generators that fool memory-bounded algorithms (i.e. combinatorial objects that look random to small-memory distinguishers). There are many exciting questions on the path towards resolving the randomness vs memory problem. In this talk we will focus on two such areas of research. First, we will discuss small memory algorithms for graph connectivity as well as pseudorandom walks, which we will relate to the general problem of randomness vs. memory. Then we will describe pseudorandom families of hash functions for data structures that are simultaneously small and efficient (with applications to load balancing, the two-choice paradigm, cuckoo hashing, and min-hashing). We will relate such families to progress on more traditional pseudorandom objects such as epsilon-bias sequences and functions with limited independence. Omer Reingold is a Professor of Computer Science at the Weizmann Institute of Science and a Visiting Professor at Stanford University. Past positions include Microsoft Research, the Institute for Advanced Study in Princeton, NJ, and AT&T Labs. His research is in the Foundations of Computer Science and most notably in Computational Complexity and the Foundations of Cryptography with emphasis on randomness, derandomization and explicit combinatorial constructions. He is an ACM Fellow and among his distinctions are the 2005 Grace Murray Hopper Award and the 2009 Gödel Prize.

1 0

Colloquium Speaker Yoram Singer, Mon Feb 9, 4:30pm
by Nicole E. Wagenblast 03 Feb '15

03 Feb '15

Colloquium Speaker Yoram Singer, Google Research Monday, February 9, 4:30pm Computer Science 105 Learning compact models from high dimensional large datasets I review the design, analysis, and implementation of stochastic optimization techniques, online algorithms, and modeling approaches for learning in high dimensional spaces using large amounts of data. The focus is on algorithms and models that are efficient, accurate, and yield compact models. Concretely, the forward-backward shrinkage algorithm (Fobos), mirror descent for learning composite objectives (COMID), and the adaptive gradient (AdaGrad) algorithm. We also discuss simple yet effective modeling approaches based on locality for learning from high dimensional data. Yoram Singer is a senior research scientist at Google. From 1999 through 2007 he was an associate professor at the Hebrew University of Jerusalem. From 1995 through 1999 he was a member of the technical staff at AT&T Research. He was the co-chair of the conference on Computational Learning Theory (COLT) in 2004 and of Neural Information Processing Systems (NIPS) in 2007. He serves as an editor of the Journal of Machine Learning, IEEE Signal Processing Magazine, and IEEE Trans. on Pattern Analysis and Machine Intelligence.

1 0

Colloquium Speaker Omer Reingold Wed Feb 4, 12:30pm
by Nicole E. Wagenblast 03 Feb '15

03 Feb '15

Colloquium Speaker Randomness Vs. Memory: A Treasure(s) Hunt Omer Reingold, Weizmann Institute of Science Wednesday, February 4, 12:30pm Computer Science 105 Randomness Vs. Memory: A Treasure(s) Hunt Randomness plays a major role in computation, allowing the execution of tasks that would otherwise be impossible or prohibitively inefficient. Yet the relative power of randomness compared with other resources of computation is mostly unresolved. In this talk we will address the tradeoff between memory and randomness. Namely, can randomness signiﬁcantly reduce the amount of memory needed for algorithmic tasks? This is one of the central problems in Computational Complexity and its study is tied with the study of pseudorandom generators that fool memory-bounded algorithms (i.e. combinatorial objects that look random to small-memory distinguishers). There are many exciting questions on the path towards resolving the randomness vs memory problem. In this talk we will focus on two such areas of research. First, we will discuss small memory algorithms for graph connectivity as well as pseudorandom walks, which we will relate to the general problem of randomness vs. memory. Then we will describe pseudorandom families of hash functions for data structures that are simultaneously small and efficient (with applications to load balancing, the two-choice paradigm, cuckoo hashing, and min-hashing). We will relate such families to progress on more traditional pseudorandom objects such as epsilon-bias sequences and functions with limited independence. Omer Reingold is a Professor of Computer Science at the Weizmann Institute of Science and a Visiting Professor at Stanford University. Past positions include Microsoft Research, the Institute for Advanced Study in Princeton, NJ, and AT&T Labs. His research is in the Foundations of Computer Science and most notably in Computational Complexity and the Foundations of Cryptography with emphasis on randomness, derandomization and explicit combinatorial constructions. He is an ACM Fellow and among his distinctions are the 2005 Grace Murray Hopper Award and the 2009 Gödel Prize.

1 0

Yiming Liu will present his Pre FPO on Monday, Feb. 9, 2015 at 1:30pm in CS 301
by Nicki Gotsis 02 Feb '15

02 Feb '15

Yiming Liu will present his Pre FPO on Monday, Feb. 9, 2015 at 1:30pm in CS 301. The members of his committee are as follows: His advisor is Szymon Rusinkiewicz; his readers are Adam Finkelstein and Aseem Agarwala (Adobe); and his non readers are Thomas Funkhouser and Jianxiong Xiao. His abstract is below. Traditional systems for image design and enhancement are completely reliant on user input, either to generate content directly or to evaluate and tune algorithms. The input must be generated by talented artists, and it is applicable only to the image for which it was originally intended. This poses scalability challenges for such traditional image generation and editing systems. An alternative paradigm, which is being researched in a variety of content-generation domains, is to exploit the large amount of data made available by users over the Internet. This data may take many forms: images, image keywords, and even judgments about image quality. Although the data is noisy and was not originally intended for the task at hand, it nevertheless serves as a useful source of "prior information". These priors make it possible to build image design and enhancement systems that require only a small amount of user input, and do not require the users to be professional artists or designers. This thesis describes three such systems, including low-level image-processing (motion deblurring), high-level editing (keyword-based image stylization), and image design (sketch-driven iconification). First, by learning based on a massive online user study, we develop a metric for automatically predicting the perceptual quality of images produced by motion deblurring algorithms, without access to the original images. Second, by leveraging online image search engines, we investigate an approach to photo filtering that only requires the user to provide one or more keywords. Third, we develop a system that converts a rough user-provided sketch into an attractive customized pictogram by remixing portions of icons retrieved from a large online repository. The projects in this talk are joint work with Aseem Agarwala, Sunghyun Cho, Michael Cohen, Adam Finkelstein, Cynthia Lu, Szymon Rusinkiewicz, Matt Uyttendaele, and Jue Wang.

1 0

Aaron Wong will present his FPO on Monday, Feb. 9, 2015 at 10:30am in CS 301
by Nicki Gotsis 02 Feb '15

02 Feb '15

Aaron Wong will present his FPO on Monday, Feb. 9, 2015 at 10:30am in CS 301 The members of his committee are: Non-readers: Moses Charikar, Kai Li; Readers: Barbara Engelhardt, Mona Singh A copy of his thesis is available in Room 310. Everyone is invited to attend his talk. ABSTRACT Biologists using modern experimental methods are generating a massive number of genomescale datasets. In particular, the rate of large-scale data creation in most organisms is quickly outpacing biologists’ ability to perform detailed follow-up experiments. Thus a substantial gap exists between the massive data being generated and the comparatively small number of experimental validations being performed (i.e. biology knowledge). In this manuscript, we present four solutions that broadly address this growing disparity, focusing on disease- and tissue-specific genomic analysis. These solutions are unified by their approaches to this problem: by combining and integrating available public genome-wide measurements to enable biological discoveries that would otherwise be impossible. First, we demonstrate a method to systematically transfer experimental knowledge between organisms inferred from high-throughput experimental data. By leveraging functional genomic data, we can improve the coverage and accuracy of function predictions across diverse organisms and machine learning methods. Second, we present an interactive web server that addresses the needs of biologists to visualize their experimental results in the context of multi-species functional predictions and relationships. Third, we describe a method that, for the first time, leverages large data compendia to build genome-scale tissue-specific functional maps in human by integrating thousands of genomescale datasets. Our method can extract both functional and tissue/cell-type signals even when genomic data are not resolved for the tissue and very little are known about the expression of genes in the tissue. Finally, we detail a method for biologists to analyze their genome-scale datasets in the context of the massive public data compendium. Biologists are generating and trying to make sense of massive high-throughput datasets, and their biological questions can be more precisely addressed within the biological context of their experiment. By incorporating their experimental results in the search and integration of gene expression compendia, we demonstrate improved predictive performance in identifying additional functionally related genes.

1 0

Colloquium Speaker Omer Reingold Wed Feb 4, 12:30pm
by Nicole E. Wagenblast 29 Jan '15

29 Jan '15

Colloquium Speaker Randomness Vs. Memory: A Treasure(s) Hunt Omer Reingold, Weizmann Institute of Science Wednesday, February 4, 12:30pm Computer Science 105 Randomness Vs. Memory: A Treasure(s) Hunt Randomness plays a major role in computation, allowing the execution of tasks that would otherwise be impossible or prohibitively inefficient. Yet the relative power of randomness compared with other resources of computation is mostly unresolved. In this talk we will address the tradeoff between memory and randomness. Namely, can randomness signiﬁcantly reduce the amount of memory needed for algorithmic tasks? This is one of the central problems in Computational Complexity and its study is tied with the study of pseudorandom generators that fool memory-bounded algorithms (i.e. combinatorial objects that look random to small-memory distinguishers). There are many exciting questions on the path towards resolving the randomness vs memory problem. In this talk we will focus on two such areas of research. First, we will discuss small memory algorithms for graph connectivity as well as pseudorandom walks, which we will relate to the general problem of randomness vs. memory. Then we will describe pseudorandom families of hash functions for data structures that are simultaneously small and efficient (with applications to load balancing, the two-choice paradigm, cuckoo hashing, and min-hashing). We will relate such families to progress on more traditional pseudorandom objects such as epsilon-bias sequences and functions with limited independence. Omer Reingold is a Professor of Computer Science at the Weizmann Institute of Science and a Visiting Professor at Stanford University. Past positions include Microsoft Research, the Institute for Advanced Study in Princeton, NJ, and AT&T Labs. His research is in the Foundations of Computer Science and most notably in Computational Complexity and the Foundations of Cryptography with emphasis on randomness, derandomization and explicit combinatorial constructions. He is an ACM Fellow and among his distinctions are the 2005 Grace Murray Hopper Award and the 2009 Gödel Prize.

1 0

Joshua Kroll's PreFPO will take place Feb 3, 2015 at 2pm in CITP conference room (Sherrerd 306)
by Nicki Gotsis 28 Jan '15

28 Jan '15

Joshua Kroll will present his PreFPO on Feb 3, 2015 at 2pm in CITP conference room (Sherrerd 306). The members of his committee are: Ed Felten (advisor); Matt Green (Johns Hopkins University) and Arvind Narayanan (readers); Andrew Appel and Nick Feamster (nonreaders). Everyone is invited to attend his talk. The talk title and abstract follow below: Title: Accountable Algorithms Abstract: Important decisions about people are increasingly made by algorithms: Votes are counted; voter rolls are purged; financial aid decisions are made; taxpayers are chosen for audits; air travelers are selected for search; credit eligibility decisions are made. Citizens, and society as a whole, have an interest in making these processes more transparent. Yet the full basis for these decisions is rarely available to affected people: the algorithm or some inputs may be secret; or the implementation may be secret; or the process may not be precisely described. A person who suspects the process went wrong has little recourse. And an oversight authority who wants to ensure that decisions are made according to an acceptable policy has little assurance that proffered decision rules match decisions for actual users. Traditionally, Computer Science addresses these problems by demanding a specification of the desired behavior, which can then be enforced or verified. But this model is poorly suited to real-world oversight tasks, where the specification might be complicated or might not be known in advance. For example, laws are often ambiguous precisely because it would be politically (and practically) infeasible to give a precise specification of their meaning. Instead, people do their best to approximate what they believe the law will allow and disputes about what is actually acceptable happen after-the-fact via expensive investigation and adjudication (e.g. in a court or legislature). As a result, actual oversight, in which real decisions are reviewed for their correctness, fairness, or faithfulness to a rule happens only rarely, if at all. Further, Computer Science often sees rules as self-enforcing: the mere fact that an automated check fails is sufficient to demonstrate that some choice was invalid. However, like all rules, automated rules (even those implemented by cryptography) are just the intentions of a system designer and only bear relevance to the extent that people will actually follow them, either due to internalized incentives or the external threat of punishment. In this thesis, we present a novel approach to relating the tools of technology to the problem of overseeing decision making processes. Our methods use the tools of computer science to cryptographically ensure the technical properties that can be proven, while providing information necessary for a political, legal, or social oversight process to operate effectively. First, we present a system for the accountable execution of legal warrants, in which the decision by a judge to allow an investigator access to private or sensitive records is realized cryptographically, so that the investigator's access to sensitive information is limited to only that information which the judge has explicitly allowed (and this can be confirmed by a disinterested third party). This system is an example of the current style of technical systems for accountability: a well-defined policy, specified in advance, is operationalized with technical tools. However, our construction does not just enforce the policy, but can convince others that the policy is being enforced correctly. Second, we present accountable algorithms, unifying the tools of zero-knowledge computational integrity with cryptographic commitments to design processes that admit meaningful after-the-fact oversight, consistent with the norm in law and policy. Accountable algorithms can attest to the valid operation of a decision policy even when all or part of that policy is kept secret.

1 0