- talks - lists.cs.princeton.edu

4:30pm Tue Nov 19 talk on routing algebras
by Jennifer Rexford 16 Nov '13

16 Nov '13

Speaker: Joao Sobrinho, Instituto de Telecomunicações Title: Algebra: A Tool for a Unifying View of Routing Protocol Behavior Date/time: 4:30-5:30pm, Tuesday November 19 Location: room 302 in the CS building Abstract: The Internet routing system is composed of millions of routers running one or more of several routing protocols---BGP, OPSF, IS-IS, RIP, EIGRP, DSR, AODV, OLSR, RPL---with the goal of guiding data-packets from sources to destinations. Beyond the specificity of every routing protocol, a number of questions are pertinent across wide classes of them, namely: • Does the routing protocol always terminate in a stable state devoid of forwarding loops and forwarding deflections? • Are the paths followed by data-packets optimal in some sense? • How much of the inherent resiliency of the network does the routing protocol exploit? • Does the routing protocol scale with the number of destinations? Routing selects paths for the transport of data-packets indirectly, through attributes they possess. Routing protocols operate by continually interleaving two processes: that of computing attributes of paths from characteristics of its constituent links; and that of choosing best attributes. The algebraic approach studies how the entwining of these two processes determines the global behavior of a routing protocol, providing answers to the questions above. In this talk, I will illustrate the unifying power of the algebraic approach by delving into the non-optimality of paths determined by EIGRP (Enhanced Interior Gateway Routing Protocol) and termination and resiliency issues raised by BGP (Border Gateway Protocol). In addition, I will survey recent applications of the algebraic approach, notably to the interconnection of routing instances and to route aggregation in the Internet. Bio: João Luís Sobrinho received his Licenciatura and Ph.D. degrees in Electrical and Computer Engineering from the Technical University of Lisbon, Portugal, in 1990 and 1995, respectively. During 1995 and 1996, he was a Member of the Technical Staff at Bell Labs, Nieuwegein, The Netherlands; he further consulted for Bell Labs, Murray Hill, NJ, from 1997 to 1999. He is currently Associate Professor at the Faculty of Engineering of the Technical University of Lisbon and a Researcher at the Telecommunications Institute. Prof. Sobrinho is a member of the IEEE and of the ACM. http://www.lx.it.pt/~jls/

1 0

Colloquium speaker Michael Isard Monday Nov 4, 4:30pm
by Nicole E. Wagenblast 11 Nov '13

11 Nov '13

Practical Elegance: Designing programming models for large-scale systems Michael Isard , Microsoft Research Monday, November 11, 4:30pm Computer Science 105 The growing need for systems that operate on large datasets is well known, but most programming models for such systems are either too low level to appeal to non-expert programmers, or are specialized to tightly restricted problem domains. I will describe the evolution of a programming model, and its associated systems, that I have worked on at Microsoft Research. The model encourages programmers to describe an algorithm as a series of data-parallel steps, embedded within a familiar language and programming environment (C#/.NET). In order to write code this way programmers must think indirectly about data-dependencies, but can leave out the messy details of concurrency. We believe this elegantly balances our desire to insulate programmers from implementation details with the need for the system to automatically infer safe parallel and distributed execution strategies. We have been able to design systems that take programs written in this model and execute them efficiently on large datasets and clusters of hundreds of computers. As the model has evolved we have made it more expressive, so that it now encompasses both incremental and iterative computation, while keeping the ability to execute these richer programs efficiently, at scale. Our ultimate goal is to integrate data-parallelism seamlessly into all aspects of a general-purpose programming language. Michael Isard started out as a computer vision researcher, but for the last few years has mostly been building distributed execution engines and thinking about how to program them. He received his D.Phil in computer vision from the Oxford University Engineering Science Department in 1998, and worked at the Compaq Systems Research Center in Palo Alto for three years before joining Microsoft Research in Silicon Valley in 2002.

1 1

Colloquium Speaker Barbbara Englehardt Wed Nov 6, 4:30pm
by Nicole E. Wagenblast 06 Nov '13

06 Nov '13

Bayesian models of structured sparsity for discovery of regulatory genetic variants Barbara Engelhardt , Duke University Wednesday, November 6th 4:30pm Computer Science 105 In genomic sciences, the amount of data has grown faster than statistical methodologies necessary to analyze those data. Furthermore, the complex underlying structure of these data means that simple, unstructured statistical models do not perform well. We consider the problem of identifying allelic heterogeneity, or multiple, functionally independent, co-localized genetic regulators of gene transcription. Sparse regression techniques have been critical to the discovery of allelic heterogeneity because of their computational tractability in large data settings. These traditional models are hindered by the substantial correlation between genetic variants induced by linkage disequilibrium. I describe a new model for Bayesian structured sparse regression. This model uses positive definite covariance matrices to incorporate the arbitrarily complex structure of the predictors directly into a Gaussian field to yield structure-aware sparse regression coefficients. This broadly applicable model of Bayesian structured sparsity enables more efficient parameter estimating techniques than models assuming independence would allow. On simulated data, we find that our approach substantially outperforms the state-of-the-art models and methods. We applied this model to a large study of expression quantitative trait loci, and found that our approach yields highly interpretable, robust solutions for allelic heterogeneity, particularly when the interactions between genetic variants are well approximated by an additive model.

1 1

Distinguished Colloquium Speaker Susan Dumais Tues Nov 5 4:30pm Friend 006
by Nicole E. Wagenblast 05 Nov '13

05 Nov '13

Temporal Dynamics and Information Retrieval Susan Dumais , Microsoft Research Tuesday, November 5 4:30pm Friend Center 006 Many digital resources, like the Web, are dynamic and ever-changing collections of information. However, most tools developed for interacting with Web content, such as browsers and search engines, focus on a single static snapshot of the information. In this talk, I will present analyses characterizing how Web content changes over time, how people re-visit Web pages over time, and how re-visitation patterns are influenced by changes in user intent and content. These results have implications for many aspects of information management including crawling policy, ranking and information extraction algorithms, result presentation, and system evaluation. I will describe a prototype that supports people in understanding how the information they interact with changes over time, and new information retrieval models that incorporate the temporal dynamics to improve ranking. Finally, I will conclude with speculations about "slow search" and an overview of challenges that need to be addressed to fully incorporate temporal dynamics into information systems. Susan Dumais is a Distinguished Scientist and manager of the Context, Learning and User Experience for Search (CLUES) Group at Microsoft Research. Prior to joining Microsoft Research, she was at Bell Labs and Bellcore for many years, where she worked on Latent Semantic Analysis, interfaces for combining search and navigation, and organizational impacts of new technology. Her current research focuses on user modeling and personalization, context and search, temporal dynamics of information, and novel evaluation methods. She has worked closely with several Microsoft groups (Bing, Windows Desktop Search, SharePoint, and Office Online Help) on search-related innovations. Susan has published widely in the fields of information science, human-computer interaction and cognitive science, and holds several patents on novel retrieval algorithms and interfaces. Susan is an adjunct professor in the Information School at the University of Washington. She is Past-Chair of ACM's Special Interest Group in Information Retrieval (SIGIR), and serves on several editorial boards, technical program committees, and government panels. She was elected to the CHI Academy in 2005, an ACM Fellow in 2006, received the SIGIR Gerard Salton Award for Lifetime Achievement in 2009, and was elected to the National Academy of Engineering (NAE) in 2011. More information is available at her homepage, http://http://research.microsoft.com/en-us/um/people/sdumais/

1 1

Colloquium Speaker Sergey Yekhanin Wed Oct 23 4:30pm
by Nicole E. Wagenblast 22 Oct '13

22 Oct '13

Local erasure coding for data storage Sergey Yekhanin , Microsoft Research Wednesday, October 23- 4:30pm Computer Science 105 Historically, most large distributed storage systems (e.g., Hotmail) have been using replication to provide reliability against machine failures. Today however as the amount of stored data reaches multiple Exabytes keeping few copies of data around is becoming prohibitively expensive. Therefore more and more systems are adopting erasure coding in place of replication. Local Reconstruction Codes (LRCs) are a new class of erasure correcting codes designed specifically for applications in data storage. Built upon the rich mathematical theory of locally decodable codes developed in the theory community, LRCs provide high level of reliability and allow data fragments to be reconstructed quickly in typical failure scenarios. LRCs have been recently deployed by Windows Azure Storage and are going to ship in Windows 8.1 and Windows Server 2012. In this talk we will discuss motivation behind local reconstruction codes and cover the main technical challenges and tradeoffs in the design of these codes. (Based on joint papers with Brad Calder, Michael Forbes, Parikshit Gopalan, Cheng Huang, Bob Jenkins, Jin Li, Aaron Ogus, Huseyin Simitci, and Yikang Xu.)

1 1

R Ge FPO
by Melissa M. Lawson 18 Oct '13

18 Oct '13

Rong Ge will present his FPO on Thursday October 24 at 10:30AM in Room 402. The members of his committee are: Sanjeev Arora, advisor; Moses Charikar and Sham Kakade (MSR New England), readers; Mark Braverman and Zeev Dvir,nonreaders. A copyof his thesis, "Provable Algorithms for Machine Learning Problems", is on display in Room 310. Everyone is invited to attend his talk.

1 0

Distinguished Colloquium Speaker Wed Oct 16 4:30pm Friend 006
by Nicole E. Wagenblast 16 Oct '13

16 Oct '13

On the Computational and Statistical Interface and "Big Data" Michael I. Jordan , University of California, Berkeley Wednesday, October 16th, 4:30pm Friend Center, 006 The rapid growth in the size and scope of datasets in science and technology has created a need for novel foundational perspectives on data analysis that blend the statistical and computational sciences. That classical perspectives from these fields are not adequate to address emerging problems in "Big Data" is apparent from their sharply divergent nature at an elementary level---in computer science, the growth of the number of data points is a source of "complexity" that must be tamed via algorithms or hardware, whereas in statistics, the growth of the number of data points is a source of "simplicity" in that inferences are generally stronger and asymptotic results can be invoked. Indeed, if data are a data analyst's principal resource, why should more data be burdensome in some sense? Shouldn't it be possible to exploit the increasing inferential strength of data at scale to keep computational complexity at bay? I present three research vignettes that pursue this theme, the first involving the deployment of resampling methods such as the bootstrap on parallel and distributed computing platforms, the second involving large-scale matrix completion, and the third introducing a methodology of "algorithmic weakening," whereby hierarchies of convex relaxations are used to control statistical risk as data accrue. Joint work with Venkat Chandrasekaran, Ariel Kleiner, Lester Mackey, Purna Sarkar, and Ameet Talwalkar. Michael I. Jordan is the Pehong Chen Distinguished Professor in the Department of Electrical Engineering and Computer Science and the Department of Statistics at the University of California, Berkeley. His research interests bridge the computational, statistical, cognitive and biological sciences, and have focused in recent years on Bayesian nonparametric analysis, probabilistic graphical models, spectral methods, kernel machines and applications to problems in statistical genetics, signal processing, natural language processing and distributed computing systems. Prof. Jordan is a member of the National Academy of Sciences, a member of the National Academy of Engineering and a member of the American Academy of Arts and Sciences. He is a Fellow of the American Association for the Advancement of Science. He has been named a Neyman Lecturer and a Medallion Lecturer by the Institute of Mathematical Statistics, and has received the ACM/AAAI Allen Newell Award. He is a Fellow of the AAAI, ACM, ASA, CSS, IMS, IEEE and SIAM.

1 2

Colloquium Speaker Kevin Fu Thurs Oct 10 4:30pm Friend Center 006
by Nicole E. Wagenblast 10 Oct '13

10 Oct '13

Medical Device Cyber Security: The First 164 Years Kevin Fu , University of Michigan Thursday, October 10- 4:30pm Friend Center 006 The U.S. Institute of Medicine commissioned my 2011 report on the role of trustworthy software in the context of the "510(k)" U.S. medical device regulations. More recently, the U.S. Food and Drug Administration has released draft guidance on cybersecurity for medical device manufacturing. This talk will provide a glimpse into the risks, benefits, and regulatory issues for medical device cybersecurity and innovation of trustworthy medical device software. Today, it would be difficult to find medical device technology that does not critically depend on computer software. The technology enables patients to lead more normal and healthy lives. However, medical devices that rely on software (e.g., drug infusion pumps, linear accelerators) continue to injure or kill patients in preventable ways---despite the lessons learned from the tragic radiation incidents of the Therac-25 era. The lack of trustworthy medical device software leads to shortfalls in properties such as safety, effectiveness, dependability, reliability, usability, security, and privacy. Come learn a bit about the science, technology, and policy that shapes medical device software. Kevin Fu is an Associate Professor of Electrical Engineering and Computer Science at the University of Michigan where he directs the Archimedes Center for Medical Device Security and the SPQR group. His research investigates how to achieve trustworthy computing on embedded devices with application to health care, commerce, and communication. His most recent contributions appear in computer science and medical conferences and journals such as USENIX Security and IEEE Security and Privacy. Kevin received his PhD in EECS from the MIT. Fu received a Sloan Research Fellowship, NSF CAREER award, Fed100 Award, and best paper awards from various academic silos of computing. The research is featured in critical articles by the NYT, WSJ, and NPR. Kevin was named MIT Technology Review TR35 Innovator of the Year for work on medical device security. Kevin has testified in Congress on health matters and has written commissioned work for the Institute of Medicine of the National Academies. He served as a visiting scientist at the Food & Drug Administration, the Beth Israel Deaconess Medical Center of Harvard Medical School, Microsoft Research, and MIT CSAIL. Previous employers include Bellcore, Cisco Systems, HP Labs, and Holland Community Hospital. He is a member of the ACM Committee on Computers and Public Policy and the NIST Information Security and Privacy Advisory Board. Kevin also holds a certificate of achievement in artisanal bread making from the French Culinary Institute.

1 2

A Chaney general exam
by Melissa M. Lawson 08 Oct '13

08 Oct '13

Allison Chaney will present her research seminar/general exam on Tuesday October 15 at 2PM in Room 301 (note room). The members of her committee are: David Blei (advisor), Rebecca Fiebrink, and Andrea LaPaugh. Everyone is invited to attend her talk, and those faculty wishing to remain for the oral exam following are welcome to do so. Her abstract and reading list follow below. ----- Original Message ----- Abstract Each of us are faced with the problem of selecting which books to read and movies to watch. Traditionally, we ask our trusted friends for recommendations, but algorithmic recommendation models make those choices even easier, saving us time and effort by steering us towards media we are more likely to enjoy. The downside to most probabilistic recommendations is that for some people, part of the appeal of reading or consuming other media is in creating shared experiences with friends. I present a model that incorporates social network information into recommendation models, reintroducing the social aspect to recommendation; this approach also has the potential to improve overall recommendations. This model discovers the latent trust that exists between users in a network and allows us to consider which users are more trustworthy than others, providing us insight into the social network's dynamics. Papers 1. D. Blei, A. Ng, and M. Jordan. Latent Dirichlet allocation . Journal of Machine Learning Research , 3:993–1022, January 2003. http://www.cs.princeton.edu/~blei/papers/BleiNgJordan2003.pdf 2. C. Wang and D. Blei. Collaborative topic modeling for recommending scientific articles. Knowledge Discovery and Data Mining , 2011. http://www.cs.cmu.edu/~chongw/papers/WangBlei2011.pdf 3. P. Gopalan, Scalable Recommendation with Poisson Factorization (forthcoming, supplied on request) 4. S. Purushotham, Y. Liu, and C.-C. J. Kuo. Collaborative Topic Regression with Social Matrix Factorization for Recommendation Systems . International Conference on Machine Learning, 2012. http://icml.cc/2012/papers/407.pdf 5. M. Hao, Y. Haixuan, M. R. Lyu , I. King. SoRec: Social Recommendation Using Probabilistic Matrix Factorization . Proceedings of the 17th ACM conference on Information and knowledge management , pg. 931–940, October 2008. http://appsrv.cse.cuhk.edu.hk/~hma/Paper_CIKM08_SoRec_Hao.pdf 6. H. Shan and A. Banerjee, Generalized Probabilistic Matrix Factorizations for Collaborative Filtering http://www-users.cs.umn.edu/~shan/icdm10_gpmf.pdf 7. Y. Koren, R. Bell, and C. Volinsky. Matrix Factorization Techniques for Recommender Systems . Computer , 42:30–37, August 2009. http://www2.research.att.com/~volinsky/papers/ieeecomputer.pdf 8. J. Herlocker, J. Konstan, L. Terveen, and J. Riedl. Evaluating Collaborative Filtering Recommender Systems . ACM Transactions on Information Systems , 2004. http://dl.acm.org/citation.cfm?doid=963770.963772 9. M. Hoffman, D. Blei, J. Paisley, and C. Wang. Stochastic variational inference . Journal of Machine Learning Research , 2013. http://www.cs.princeton.edu/~blei/papers/HoffmanBleiWangPaisley2013.pdf Selected Sections of Textbooks 1. S. Russell and P. Norvig, Artificial Intelligence: A Modern Approach , Prentice Hall Series in Artificial Intelligence, 2003: Chapters: 3.1-3.5, 4.1, 5, 8.1-8.3, 13.1-13.5, 14, 15, 18, 21 2. Bishop, C. M., Pattern Recognition and Machine Learning , Springer , 2006 : Chapters 1, 2, 3.1-3.3, 4.1-4.3, 8, 9, 10, 11.1-11.3, 12.1-12.2, 13, 14.1, 14.3 3. A. Gelman, J. B. Carlin, H. S. Stern, and D. B. Rubin. Bayesian Data Analysi s, Taylor & Francis, 1995: chapters 5, 6, 11 4. Spall, J. C., Introduction to Stochastic Search and Optimization: Estimation, Simulation, and Control , Wiley, 2003: Ch 2 5. J. Lazar, J. Feng, and H. Hochheiser. Research Methods in Human-Computer Interaction. John Wiley & Sons, 2010: Chapters 2,3,10-12 6. R ecommender Systems Handbook, Springer , 2010. Chapter 8: Evaluating Recommendation Systems by G. Shani and A. Gunawardana.

1 0

A Bell FPO
by Melissa M. Lawson 03 Oct '13

03 Oct '13

Ana Bell will present her FPO on Friday October 11 at 9AM in Room 402. The members of her committee are: Olga Troyanskaya, advisor; Mona Singh and Andrea LaPaugh, readers; Tom Funkhouser and Kai Li, nonreaders. A copy of her thesis, "Integrating Genomic Data to Build Networks for Proteins and Small Molecules", is on display in Room 310. Everyone is invited to attend her talk.

1 0