November 2016 - talks - lists.cs.princeton.edu

Colloquium Speaker Uri Keich, Thurs Nov 10, 12:30pm
by Nicole E. Wagenblast 10 Nov '16

10 Nov '16

Colloquium Speaker Prof. Uri Keich, University of Sydney Thursday, November 10, 12:30pm Computer Science 105 Controlling the rate of false discoveries in tandem mass spectrum identifications A typical shotgun proteomics experiment produces thousands of tandem mass spectra, each of which can be tentatively assigned a corresponding peptide by using a database search procedure that looks for a peptide-spectrum match (PSM) that optimizes the score assigned to a matched pair. Some of the resulting PSMs will be correct while others will be false, and we have no way to verify which is which. The statistical problem we face is of controlling the false discovery rate (FDR), or the expected proportion of false PSMs among all reported pairings. While there is a rich statistical literature on controlling the FDR in the multiple hypothesis testing context, controlling the FDR in the PSM context is mostly done through the "home grown" method called target-decoy competition (TDC). After a brief introduction to the problem of tandem mass spectrum identification we will explore the reasons why the mass spec community has been using this non-standard approach to controlling the FDR. We will then discuss how calibration can increase the number of correct discoveries and offer an alternative method for controlling the FDR in the presence of calibrated scores. We will conclude by arguing that our analysis extends to a more general setup than the mass spectrum identification problem. Joint work with Bill Noble (University of Washington)

1 0

Colloquium Speaker Uri Keich, Thurs Nov 10, 12:30pm- reminder
by Nicole E. Wagenblast 09 Nov '16

09 Nov '16

Colloquium Speaker Prof. Uri Keich, University of Sydney Thursday, November 10, 12:30pm Computer Science 105 Controlling the rate of false discoveries in tandem mass spectrum identifications A typical shotgun proteomics experiment produces thousands of tandem mass spectra, each of which can be tentatively assigned a corresponding peptide by using a database search procedure that looks for a peptide-spectrum match (PSM) that optimizes the score assigned to a matched pair. Some of the resulting PSMs will be correct while others will be false, and we have no way to verify which is which. The statistical problem we face is of controlling the false discovery rate (FDR), or the expected proportion of false PSMs among all reported pairings. While there is a rich statistical literature on controlling the FDR in the multiple hypothesis testing context, controlling the FDR in the PSM context is mostly done through the "home grown" method called target-decoy competition (TDC). After a brief introduction to the problem of tandem mass spectrum identification we will explore the reasons why the mass spec community has been using this non-standard approach to controlling the FDR. We will then discuss how calibration can increase the number of correct discoveries and offer an alternative method for controlling the FDR in the presence of calibrated scores. We will conclude by arguing that our analysis extends to a more general setup than the mass spectrum identification problem. Joint work with Bill Noble (University of Washington)

1 0

12pm Mon Nov 14 talk on "Efficient fault-tolerant quantum computing" by Martin Suchara in Bowen Auditorium
by Jennifer Rexford 07 Nov '16

07 Nov '16

> From: "Barbara J. Fruhling" <bfruhlin(a)Princeton.EDU> > Subject: EE Seminar - November 14, 2016, 12:00 pm, Bowen Auditorium - Dr. Martin Suchara > Date: November 7, 2016 at 1:42:17 PM EST > To: ee-seminar(a)Princeton.EDU > > > > Speaker: Dr. Martin Suchara > AT&T Labs Research > Title: Efficient Fault-Tolerant Quantum Computing > Date: Monday, November 14, 2016 > Time: 12:00 p.m. > Room: Bowen Auditorium > Light lunch served at 11:30 > Host: Prof. Jeff Thompson > > Abstract: Quantum error correction presents some of the most significant and interesting challenges that must be resolved before building an efficient quantum computer. Quantum error correcting codes allow to successfully run quantum algorithms on unreliable quantum hardware. Because quantum hardware suffers from errors such as decoherence, leakage or qubit loss, and these errors corrupt delicate quantum states rather than binary information, the known error correction techniques are complex and have a high overhead. > > In my talk I first introduce the two main families of quantum error correcting codes and quantify their overhead using specific examples of algorithms and hardware technologies. Then I describe several new techniques that I developed to reduce this overhead. For example, the maximum likelihood decoder (MLD) is an efficient algorithm that finds the recovery operation that maximizes the probability of a successful error correction given the observed error syndrome. Numerical simulations of the MLD algorithm for physical error rates around 10% showed a 100 fold reduction of the logical error probability compared to earlier techniques. I also show new designs of error correcting codes that are tailored to work more efficiently with the constraints of specific physical technologies. > > Bio: Martin Suchara is a Principal Inventive Scientist at AT&T Labs Research since 2015. Prior to joining AT&T he was a Postdoctoral Scholar in the quantum computing group at IBM T. J. Watson Research Center. His work focuses on making computation with quantum computers more efficient and reliable. He developed new quantum error correcting codes that improve error decoding efficiency. Martin received his PhD from the Computer Science department at Princeton University and postdoctoral training from UC Berkeley. Between 2011 and 2013 he coordinated the work of a small group of postdocs and students on the IARPA Quantum Computer Science Program and delivered the results to the Program Manager. Martin is the recipient of the Best Student Paper Award at ACM Sigmetrics 2011.

1 0

Colloquium Speaker Uri Keich, Thurs Nov 10, 12:30pm
by Nicole E. Wagenblast 07 Nov '16

07 Nov '16

Colloquium Speaker Prof. Uri Keich, University of Sydney Thursday, November 10, 12:30pm Computer Science 105 Controlling the rate of false discoveries in tandem mass spectrum identifications A typical shotgun proteomics experiment produces thousands of tandem mass spectra, each of which can be tentatively assigned a corresponding peptide by using a database search procedure that looks for a peptide-spectrum match (PSM) that optimizes the score assigned to a matched pair. Some of the resulting PSMs will be correct while others will be false, and we have no way to verify which is which. The statistical problem we face is of controlling the false discovery rate (FDR), or the expected proportion of false PSMs among all reported pairings. While there is a rich statistical literature on controlling the FDR in the multiple hypothesis testing context, controlling the FDR in the PSM context is mostly done through the "home grown" method called target-decoy competition (TDC). After a brief introduction to the problem of tandem mass spectrum identification we will explore the reasons why the mass spec community has been using this non-standard approach to controlling the FDR. We will then discuss how calibration can increase the number of correct discoveries and offer an alternative method for controlling the FDR in the presence of calibrated scores. We will conclude by arguing that our analysis extends to a more general setup than the mass spectrum identification problem. Joint work with Bill Noble (University of Washington)

1 0

Jordan Fix will present his Pre-FPO on Monday, November 7th, 2016 at 4pm in CS 401
by Nicki Gotsis 07 Nov '16

07 Nov '16

Jordan Fix will present his Pre-FPO on Monday, November 7th, 2016 at 4pm in CS 401. The members of his committee are: Advisor: David August Non-readers: David Wentzlaff, Margaret Martonosi Readers: Andrew Appel, David Callahan (Facebook) Everyone is invited to attend his talk. Abstract: Speculation with transactional memory (TM) systems helps programmers and compilers produce profitable thread-level parallel programs. Prior work shows that supporting transactions that span multiple threads, rather than requiring transactions be contained within a single thread, enables new types of speculative parallelization techniques for both programmers and parallelizing compilers. The only prior TM systems with this multithreaded transactional (MTX) support are software-based TM (STM) systems. Unfortunately, these systems are notorious for their high overheads when validating speculative memory operations, which often make otherwise good parallelization unprofitable. Thus, parallelized programs using these prior STM systems with MTX support were forced to overcome this problem through significant manual effort by the programmer to optimize away most of this speculation validation. Unfortunately, compiler technology and static analyses have not proven strong enough to relieve the programmer of this burden. This thesis presents the first complete design and implementation of a hardware TM (HTM) system with MTX support. This system provides low overhead speculation validation, enabling the aforementioned new types of speculative parallelization techniques to achieve good performance even with high amounts of speculation validation. Profitable parallelization of complex programs can be achieved even with maximal speculation validation of every load and store inside transactions of tens to hundreds of millions of instructions, thus making parallelization less laborious and more feasible for both programmers and compilers. In addition to supporting MTXs, transactions in this system are more resilient than in many other prior works. Transactions avoid false misspeculation due to branch misprediction; provide for large read and write sets that commit in a lazy fashion; and allow for context switches (and thread migration) due to common operations such as preemption or virtual memory management. This allows the system to accommodate the large and long running transactions that are needed to parallelize complex programs. Across 6 SPEC benchmarks a geomean speedup of 2.11X over sequential execution is achieved on a multicore machine with 4 cores, while increasing energy usage by 10%.

1 1

Colloquium Speaker Adam Kalai, today, 12:30pm
by Nicole E. Wagenblast 07 Nov '16

07 Nov '16

Colloquium Speaker Adam Kalai, Microsoft Research Monday, November 7, 2016 - 12:30pm Computer Science 105 Meta-unsupervised-learning: a principled approach to unsupervised learning Unsupervised Learning and exploratory data analysis are among the most important and yet murkiest areas within machine learning. Debates rage even about how to choose which objective function to optimize. We introduce a principled data-driven approach: “meta-unsupervised-learning” using a collection of related or unrelated learning problems. We present simple agnostic models and algorithms illustrating how the meta approach circumvents impossibility results for novel "meta" problems such as meta-clustering, meta-outlier-removal, meta-feature-selection, and meta-embedding. We also present empirical results showing how the meta approach improves over standard techniques for problems such as outlier removal and choosing a clustering algorithm and a number of clusters. We also train an unsupervised neural network that learns from prior supervised classification problems drawn from learning problems at openml.org. Joint work with Vikas Garg from MIT Adam Tauman Kalai received his BA from Harvard, and MA and PhD under the supervision of Avrim Blum from CMU. After an NSF postdoctoral fellowship at M.I.T. with Santosh Vempala, he served as an assistant professor at the Toyota Technological institute at Chicago and then at Georgia Tech. He is now a Principal Researcher at Microsoft Research New England. His honors include an NSF CAREER award and an Alfred P. Sloan fellowship. His research focuses on machine learning, human computation, and algorithms.

1 0

Colloquium Speaker Adam Kalai, Monday Nov 7, 12:30pm- reminder
by Nicole E. Wagenblast 06 Nov '16

06 Nov '16

Colloquium Speaker Adam Kalai, Microsoft Research Monday, November 7, 2016 - 12:30pm Computer Science 105 Meta-unsupervised-learning: a principled approach to unsupervised learning Unsupervised Learning and exploratory data analysis are among the most important and yet murkiest areas within machine learning. Debates rage even about how to choose which objective function to optimize. We introduce a principled data-driven approach: “meta-unsupervised-learning” using a collection of related or unrelated learning problems. We present simple agnostic models and algorithms illustrating how the meta approach circumvents impossibility results for novel "meta" problems such as meta-clustering, meta-outlier-removal, meta-feature-selection, and meta-embedding. We also present empirical results showing how the meta approach improves over standard techniques for problems such as outlier removal and choosing a clustering algorithm and a number of clusters. We also train an unsupervised neural network that learns from prior supervised classification problems drawn from learning problems at openml.org. Joint work with Vikas Garg from MIT Adam Tauman Kalai received his BA from Harvard, and MA and PhD under the supervision of Avrim Blum from CMU. After an NSF postdoctoral fellowship at M.I.T. with Santosh Vempala, he served as an assistant professor at the Toyota Technological institute at Chicago and then at Georgia Tech. He is now a Principal Researcher at Microsoft Research New England. His honors include an NSF CAREER award and an Alfred P. Sloan fellowship. His research focuses on machine learning, human computation, and algorithms.

1 0

Colloquium Speaker Adam Kalai, Monday Nov 7, 12:30pm
by Nicole E. Wagenblast 01 Nov '16

01 Nov '16

Colloquium Speaker Adam Kalai, Microsoft Research Monday, November 7, 2016 - 12:30pm Computer Science 105 Meta-unsupervised-learning: a principled approach to unsupervised learning Unsupervised Learning and exploratory data analysis are among the most important and yet murkiest areas within machine learning. Debates rage even about how to choose which objective function to optimize. We introduce a principled data-driven approach: “meta-unsupervised-learning” using a collection of related or unrelated learning problems. We present simple agnostic models and algorithms illustrating how the meta approach circumvents impossibility results for novel "meta" problems such as meta-clustering, meta-outlier-removal, meta-feature-selection, and meta-embedding. We also present empirical results showing how the meta approach improves over standard techniques for problems such as outlier removal and choosing a clustering algorithm and a number of clusters. We also train an unsupervised neural network that learns from prior supervised classification problems drawn from learning problems at openml.org. Joint work with Vikas Garg from MIT Adam Tauman Kalai received his BA from Harvard, and MA and PhD under the supervision of Avrim Blum from CMU. After an NSF postdoctoral fellowship at M.I.T. with Santosh Vempala, he served as an assistant professor at the Toyota Technological institute at Chicago and then at Georgia Tech. He is now a Principal Researcher at Microsoft Research New England. His honors include an NSF CAREER award and an Alfred P. Sloan fellowship. His research focuses on machine learning, human computation, and algorithms.

1 0