October 2011 - talks - lists.cs.princeton.edu

Colloquioum Speaker Gerry Tesauro Wed Oct 26 4:30pm
by Nicole E. Wagenblast 24 Oct '11

24 Oct '11

How Watson Learns Superhuman Jeopardy! Strategies Gerry Tesauro, IBM Research Wednesday, October 26, 2011, 4:30 PM Computer Science Small Auditorium (Room 105) Major advances in Question Answering technology were needed for Watson to play Jeopardy! at championship level -- the show requires rapid-fire answers to challenging natural language questions, broad general knowledge, high precision, and accurate confidence estimates. In addition, Jeopardy! features four types of decision making carrying great strategic importance: (1) selecting the next clue when in control of the board; (2) deciding whether to attempt to buzz in; (3) wagering on Daily Doubles; (4) wagering in Final Jeopardy. This talk describes how Watson makes the above decisions using innovative quantitative methods that, in principle, maximize Watson's overall winning chances. We first describe our development of faithful simulation models of human contestants and the Jeopardy! game environment. We then present specific learning/optimization methods used in each strategy algorithm: these methods span a range of popular AI research topics, including Bayesian inference, game theory, Dynamic Programming, Reinforcement Learning, and real-time "rollouts." Application of these methods yielded superhuman game strategies for Watson that significantly enhanced its overall competitive record. Joint work with David Gondek, Jon Lenchner, James Fan and John Prager. Gerald Tesauro is a Research Staff Member at IBM's TJ Watson Research Center. He is best known for developing TD-Gammon, a self-teaching neural network that learned to play backgammon at human world championship level. He has also worked on theoretical and applied machine learning in a wide variety of other settings, including multi-agent learning, dimensionality reduction, computer virus recognition, computer chess (Deep Blue), intelligent e-commerce agents and autonomic computing. Dr. Tesauro received BS and PhD degrees in physics from University of Maryland and Princeton University, respectively.

1 1

October 20: SIGGRAPH Computer Graphics Film Show
by Nicole E. Wagenblast 19 Oct '11

19 Oct '11

The Princeton ACM / IEEE-CS Chapters present the 32nd annual SIGGRAPH Computer Graphics Film Show. This meeting features the latest and greatest computer animations direct from the ACM SIGGRAPH conference and Computer Animation Festival, held this summer in Vancouver. Szymon Rusinkiewicz of Princeton University is again the host and presenter. This meeting is free and open to the public. Students and their parents are welcome. There is no admission charge, and refreshments are served. Date: Thursday October 20, 2011, 8:00 pm (Refreshments and networking at 7:30 pm) Place: Friend Center Auditorium, Room 101, Olden and William Streets, Princeton University See princetonacm.acm.org for more details.

1 0

Colloquium Speaker Tom Wenisch Tues, Oct 18, 4:30pm
by Nicole E. Wagenblast 17 Oct '11

17 Oct '11

Making Enterprise Computing Green: Efficiency Challenges in Warehouse-Scale Computers Tom Wenisch, University of Michigan Tuesday October 18, 2011- 4:30pm Computer Science 105 Architects and circuit designers have made enormous strides in managing the energy efficiency and peak power demands of processors and other silicon systems. Sophisticated power management features and modes are now myriad across system components, from DRAM to processors to disks. And yet, despite these advances, typical data centers today suffer embarrassing energy inefficiencies: it is not unusual for less than 20% of a data center's multi-megawatt total power draw to flow to computer systems actively performing useful work. Managing power and energy is challenging because individual systems and entire facilities are conservatively provisioned for rare utilization peaks, which leads to energy waste in underutilized systems and over-provisioning of physical infrastructure. Power management is particularly challenging for Online Data Intensive (OLDI) services---workloads like social networking, web search, ad serving, and machine translation that perform significant computing over massive data sets for each user request but require responsiveness in sub-second time scales. These inefficiencies lead to worldwide energy waste measured in billions of dollars and tens of millions of metric tons of CO2. In this talk, I discuss what, if anything, can be done to make OLDI systems more energy-proportional. Specifically, through a case study of Google's Web Search application, I will discuss the applicability of existing and proposed active and idle low-power modes to reduce the power consumed by the primary server components (processor, memory, and disk), while maintaining tight response time constraints, particularly on 95th-percentile latency. Then, I will briefly discuss our work on PowerRouting, a proposal to dynamically switch servers among redundant power feeds to reduce overprovisioning in data center power delivery infrastructure. Finally, I will close with comments on our ongoing work examining server and cluster-level performance optimization for memcached, a distributed main-memory key-value store that acts as a cache for more expensive durable stores (e.g., a DBMS) and is a key piece of infrastructure for OLDI services. Thomas Wenisch is the Morris Wellman Faculty Development Assistant Professor of Computer Science and Engineering at the University of Michigan, specializing in computer architecture. Tom's prior research includes memory streaming for commercial server applications, store-wait-free multiprocessor memory systems, memory disaggregation, and rigorous sampling-based performance evaluation methodologies. His ongoing work focuses on data center architecture, energy-efficient server design, and multi-core / multiprocessor memory systems. Tom received an NSF CAREER award in 2009. Prior to his academic career, Tom was a software developer at American Power Conversion, where he worked on data center thermal topology estimation. He is co-inventor on four patents. Tom received his Ph.D. in Electrical and Computer Engineering from Carnegie Mellon University.

1 1

W Clarkson preFPO
by Melissa M. Lawson 14 Oct '11

14 Oct '11

Will Clarkson will present his preFPO on Friday October 21 at 2PM in the CITP Conference room (3rd floor). The members of his committee are: Ed Felten, advisor; Adam Finkelstein and Andrew Appel, readers; Rebecca Fiebrink and Brian Kernighan, nonreaders. Everyone is invited to attend his talk. His abstract follows below. --------------------- Title: Breaking Assumptions: Distinguishing Seemingly Identical Objects Using Cheap Sensors Abstract: Many security protocols and procedures implicitly rely on the idea that certain objects are indistinguishable from one another. With the increasing accuracy and availability of cheap sensors, the landscape of what can be measured has changed, forcing us to re-evaluate our preconceptions of what it means for objects to be treated as identical. In many cases, improperly relying on an item’s indistinguishably can have serious implications. In this talk, I will touch on three different examples of commonly held, but ultimately false, assumptions regarding the indistinguishably of seemingly identical items. I’ll discuss how blank sheets of paper, ‘anonymous’ bubble-forms, and your computer’s speakers are not as indistinguishable as you might think. Re-evaluating the assumption of indistinguishability reveals that each of these items has inherent physical features that allow them to be identified with surprisingly high accuracy. In each of these cases the consequences can be positive, providing for new applications, or negative, violating the application's assumption about indistinguishability.

1 0

M Hardt FPO
by Melissa M. Lawson 14 Oct '11

14 Oct '11

Moritz Hardt will present his FPO on Thursday October 20 at 3PM in Room 402. The members of his committee are; Boaz Barak, advisor; Sanjeev Arora and Rocco Servedio (Columbia), readers; Moses Charikar and Rob Schapire, nonreaders. A copy of his thesis, "A Study of Privacy and Fairness in Sensitive Data Analysis", is on display in Room 310. Everyone is invited to attend his talk.

1 0

Colloquium talk 4:30pm today- Brian Whitman
by Nicole E. Wagenblast 12 Oct '11

12 Oct '11

Trying to understand music at scale Brian Whitman, The Echo Nest Wednesday October 12, 2010- 4:30pm Computer Science 105 The Echo Nest is a music intelligence platform that has collected and analyzed data about over two million artists and 35 million songs. We've crawled billions of documents, parsed every phrase written about any band you can think of, and can tell you the pitch and timbre of every note in almost every song ever recorded. And all of that data in one way or another invisibly affects the music experience of over 150 million people every month, from recommenders to search to fingerprinting to discovery. We've done it using pragmatic and scalable approaches to machine learning, natural language processing and information retrieval and I'll be describing the particular challenges in doing quality "machine listening" at scale while recognizing the inherent reticence of music itself to be computationally analyzed. Brian Whitman (The Echo Nest) teaches computers how to make, listen to, and read about music. He received his doctorate from the Machine Listening group at MIT’s Media Lab in 2005 and his masters in Computer Science from Columbia University’s Natural Language Processing group in 2000. As the co-founder and CTO of the Echo Nest Corporation, Brian architects an open platform with billions of data points about the world of music: from the listeners to the musicians to the sounds within the songs.

1 0

S Beard General Exam
by Melissa M. Lawson 12 Oct '11

12 Oct '11

Stephen Beard will present his research seminar/general exam on Wednesday October 19 at 10AM in Room 402. The members of his committee are; David August (advisor), Andrew Appel, and Vivek Pai. Everyone is invited to attend his talk and those faculty wishing to remain for the oral exam following are welcome to do so. His abstract and reading list follow below. --------------------------- Client Driven Memory Profiling Profiling provides vital insight to a program’s run-time characteristics including data and control information. Control flow profiling is popular because it improves compiler optimizations without excessive profiling overhead (less than 2×). While memory profiling can enable aggressive speculative optimizations to overcome the perennial limits of static memory analysis, it is rarely used due to its excessive profiling overhead (29× to 290×). To help address this problem, this paper presents Client Driven Memory Profiling (CDMP). Most speculative transformations are only concerned with some subset of the dependences in the program. Given this information, CDMP profiles only those dependences which are of use to the client optimizations. As a result, CDMP incurs a running time overhead of 66× averaged across the C/C++ SPEC CPU2006 benchmark suite, a 2.2× improvement over the 143× overhead incurred by a state-of-the-art memory profiler. After combining our client targeting optimization with sampling techniques found in prior work, CDMP achieve a running time overhead of 1.8×, a 4.1× improvement over the 7.3× overhead of sampling alone, with no additional error over sampling. Reading List 1.1 Textbooks 1. A. W. Appel. Modern Compiler Implementation in C. Cambridge University Press, 1998 2. S. Muchnick. Advanced Compiler Design and Implementation. Morgan-Kaufmann Publishers, San Francisco, CA, 1997 1.2 Performance and Path Profiling 3. S. L. Graham, P. B. Kessler, and M. K. Mckusick. Gprof: A call graph execution profiler. In Proceedings of the 1982 SIGPLAN symposium on Compiler construction, SIGPLAN ’82, pages 120–126, New York, NY, USA, 1982. ACM 4. T. Ball, P. Mataga, and M. Sagiv. Edge profiling versus path profiling: The showdown. In Proceedings of the 25th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, pages 134–148, January 1998 1.3 Dependence Profiling 5. T. Chen, J. Lin, X. Dai, W.-C. Hsu, and P.-C. Yew. Data dependence profiling for speculative optimizations. In E. Duesterwald, editor, Compiler Construction, volume 2985 of Lecture Notes in Computer Science, pages 2733–2733. Springer Berlin / Heidelberg, 2004 6. A. K. Peng Wu and C. Cascaval. Compiler-driven dependence profiling to guide program parallelization. In LCPC, pages 232–248, 2008 7. M. Kim, H. Kim, and C.-K. Luk. SD3 : A scalable approach to dynamic data-dependence profiling. In Proceedings of the 2010 43rd Annual IEEE/ACM International Symposium on Microarchitecture, MICRO ’10, pages 535–546, Washington, DC, USA, 2010. IEEE Computer Society 1.4 Sampling 8. M. Arnold and B. G. Ryder. A framework for reducing the cost of instrumented code. In Proceedings of the ACM SIGPLAN 2001 conference on Programming language design and implementation, PLDI ’01, pages 168–179, New York, NY, USA, 2001. ACM 1.5 Analysis 9. M. Hind. Pointer analysis: Haven’t we solved this problem yet? In 2001 ACM SIGPLAN-SIGSOFT Workshop on Program Analysis for Software Tools and Engineering (PASTE’01), 2001 10. B. Hardekopf and C. Lin. Flow-sensitive pointer analysis for millions of lines of code. Code Generation and Optimization, IEEE/ACM International Symposium on, 0:289–298, 2011 1.6 Speculative Parallel Optimization 11. J. G. Steffan and T. C. Mowry. The potential for using thread-level data speculation to facilitate automatic parallelization. In Proceedings of the 4th International Symposium on High-Performance Computer Architecture, pages 2–13, February 1998

1 0

M Zoufaly general exam
by Melissa M. Lawson 04 Oct '11

04 Oct '11

Matt Zoufaly will present his research seminar/general exam on Tuesday October 11 at 8AM in Room 402. The members of his committee are: David August, advisor; Margaret Martonosi, JP Singh. Everyone is invited to attend his talk, and those faculty wishing to remain for the oral exam following are welcome to do so. His abstract and reading list follow below. Title: A Framework for Runtime Parallelization Abstract: Performance no longer scales with the abundance of parallel resources provided by multicore devices. Prior work in manual parallelization as well as automatic static parallelization have shown promise, but a return to the era where processor improvements alone could be relied upon to consistently deliver improved application performance remains more desirable. To help address this problem, I present the HyPar dynamic parallelization framework for multicore systems. HyPar is a hybrid of lightweight hardware extensions and an efficient run-time parallelizer designed to provide the illusion of a single fast processor core for sequential binaries. In addition to a hot loop detector, each core in a HyPar system includes a memory characterizer. These memory characterizers guide memory speculation during parallelization, and they provide for distributed memory misspeculation detection during parallel execution. An instance of the HyPar framework, configured to use a custom memory characterizer and to perform the speculative DOALL transformation, yields a geomean speedup of 2.4x for 14 unmodified sequential x86 binaries on a commodity machine with four cores using simulated hardware components. Reading List: 1.1 Textbooks • A. W. Appel. Modern Compiler Implementation in ML. Cambridge University Press, 1998 • J. L. Hennessy and D. A. Patterson. Computer Architecture: A Quantitative Approach. Morgan Kaufmann, San Francisco, CA, 1996 1.2 Binary Parallelization Papers • B. Hertzberg and K. Olukotun. Runtime automatic speculative parallelization. In Code Generation and Optimization (CGO), 2011 9th Annual IEEE/ACM International Symposium on, pages 64 –73, april 2011 • A. Kotha, K. Anand, M. Smithson, G. Yellareddy, and R. Barua. Automatic parallelization in a binary rewriter. In Proceedings of the 2010 43rd Annual IEEE/ACM International Symposium on Microarchitecture, MICRO ’43, pages 547–557, Washington, DC, USA, 2010. IEEE Computer Society • C. Wang, Y. Wu, E. Borin, S. Hu, W. Liu, D. Sager, T. fook Ngai, and J. Fang. Dynamic parallelization of single-threaded binary programs using speculative slicing. In ICS’09, pages 158–168, 2009 • E. Yardimci and M. Franz. Dynamic parallelization and mapping of binary executables on hierarchical platforms. In CF ’06: Proceedings of the 3rd ACM International Conference on Computing Frontiers, pages 127–138, New York, NY, USA, 2006. ACM 1.3 Speculative Parallelization • L. Rauchwerger and D. Padua. The LRPD test: speculative run-time parallelization of loops with privatization and reduction parallelization. ACM SIGPLAN Notices, 30(6):218–232, 1995 • J. G. Steffan, C. B. Colohan, A. Zhai, and T. C. Mowry. A scalable approach to thread-level speculation. In Proceedings of the 27th International Symposium on Computer Architecture, pages 1–12, June 2000 • H. Zhong, M. Mehrara, S. Lieberman, and S. Mahlke. Uncovering hidden loop level parallelism in sequential applications. In HPCA ’08: Proceedings of the 14th International Symposium on High-Performance Computer Architecture, 2008 1.4 Dynamic Optimizations • V. Bala, E. Duesterwald, and S. Banerjia. Dynamo: A transparent dynamic optimization system. In Proceedings of the ACM SIGPLAN ’00 Conference on Programming Language Design and Implementation, pages 1–12, June 2000 • A. Cristal, O. Santana, F. Cazorla, M. Galluzzi, T. Ramirez, M. Pericas, and M. Valero. Kilo-instruction processors: overcoming the memory wall. Micro, IEEE, 25(3):48 – 57, may-june 2005 • M. C. Merten, A. R. Trick, R. D. Barnes, E. M. Nystrom, C. N. George, J. C. Gyllenhaal, and W. W. Hwu. An architectural framework for runtime optimization. to appear in IEEE Transactions on Computers Special Issue on Dynamic Optimization, 2001 1.5 Memory Profiling • D. M. Gallagher, W. Y. Chen, S. A. Mahlke, J. C. Gyllenhaal, and W. W. Hwu. Dynamic memory disambiguation using the memory conflict buffer. In Proceedings of 6th International Conference on Architectural Support for Programming Languages and Operating Systems, pages 183–193, October 1994 • M. Herlihy and J. E. B. Moss. Transactional memory: Architectural support for lock-free data structures. In Proceedings of the 20th Annual International Symposium on Computer Architecture (ISCA), 1993

1 0

Colloquium Speaker Eric Xing: Thrus, Oct 6th- 4:30pm
by Nicole E. Wagenblast 04 Oct '11

04 Oct '11

Jointly Maximum Margin and Maximum Entropy Learning of Graphical Models Eric Xing, Carnegie Mellon University Thursday, October 6, 2011- 4:30pm Computer Science, 105 Graphical models (GMs) offer a powerful language to elegantly define expressive distributions, and a generic computational framework to support reasoning under uncertainty in a wide range of problems. Popular paradigms for training GMs include the maximum likelihood estimation, and more recently the max-margin learning, each enjoys some advantages, as well as weaknesses. For example, the maximum margin structured prediction model such as M3N lacks a straightforward probabilistic interpretation of the learning scheme and the prediction rule. Therefore its unique advantages such as support vector sparsity and kernel tricks cannot be easily conjoined with the merits of a probabilistic model such as Bayesian regularization, model averaging, and ability to model hidden variables. In this talk, I present a new general framework called Maximum Entropy Discrimination Markov Networks (MEDN), which integrates the margin-based and likelihood-based approaches and combines and extends their merits. This new learning paradigm naturally facilitates integration of the generative and discriminative principles under a unified framework, and the basic strategies can be generalized to learn arbitrary GMs, such as the generative Bayesian networks, models with structured hidden variables, and even nonparametric Bayesian models, with a desirable maximum margin effect on structured or unstructured predictions. I will discuss a number of theoretical properties of this approach, and show applications of MEDN to learning a wide range of GMs including: fully supervised structured i/o model, max-margin structured i/o models with hidden variables, a max-margin LDA-style model for jointly discovering “discriminative” latent topics and predicting document label/score of text documents, or total scene and objective categories in natural images, etc. Our empirical results strongly suggest that, for any GM with structured or unstructured labels, MEDN always leads to a more accurate predictive GM than the one trained under either MLE or Max Margin. Joint work with Jun Zhu. Dr. Eric Xing is an associate professor in the School of Computer Science at Carnegie Mellon University. His principal research interests lie in the development of machine learning and statistical methodology; especially for solving problems involving automated learning, reasoning, and decision-making in high-dimensional and dynamic possible worlds; and for building quantitative models and predictive understandings of biological systems. Professor Xing received a Ph.D. in Molecular Biology from Rutgers University, and another Ph.D. in Computer Science from UC Berkeley. His current work involves, 1) foundations of statistical learning, including theory and algorithms for estimating time/space varying-coefficient models, sparse structured input/output models, and nonparametric Bayesian models; 2) computational and statistical analysis of gene regulation, genetic variation, and disease associations; and 3) application of statistical learning in social networks, computer vision, and natural language processing. Professor Xing has published over 140 peer-reviewed papers, and is an associate editor of the Annals of Applied Statistics, the PLoS Journal of Computational Biology, and an Action Editor of the Machine Learning journal. He is a recipient of the NSF Career Award, the Alfred P. Sloan Research Fellowship in Computer Science, and the United States Air Force Young Investigator Award.

1 1