- talks - lists.cs.princeton.edu

I Mukherjee general exam
by Melissa M Lawson 12 May '08

12 May '08

Indraneel Mukherjee will present his research seminar/general exam on Friday May 16 at 2PM in Room 402. The members of his committee are: Rob Schapire (advisor), David Blei, and Ken Steiglitz. 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. ---------------------------------------- Abstract: ========= We consider the problem of learning to predict as well as the best in a group of experts making continuous predictions. We assume the learning algorithm has prior knowledge of the maximum number of mistakes of the best expert. We propose a new master strategy that achieves the best known performance for online learning with continuous experts in the mistake bounded model. Our ideas are based on drifting games, a generalization of boosting and online learning algorithms. We also prove new lower bounds based on the drifting games framework which, though not as tight as previous bounds, have simpler proofs and do not require an enormous number of experts. Papers: ======= 1. Yoav Freund and Manfred Opper. Drifting games and Brownian motion. Journal of Computer and System Sciences, 64:113--132, 2002. A preliminary version appeared in the Proceedings of the 13th Annual Conference on Computational Learning Theory, 2000. 2. Yoav Freund. An adaptive version of the boost by majority algorithm. Machine Learning, 43(3):293--318, June 2001. A preliminary version appeared in the Proceedings of the 12th Annual Conference on Computational Learning Theory, 1999. 3. Yoav Freund. Boosting a weak learning algorithm by majority. Information and Computation, 121(2):256--285, 1995. Preliminary versions appeared in the Proceedings of the Third Annual Workshop on Computational Learning Theory, 1990, and in the Proceedings of the Fifth Annual ACM Workshop on Computational Learning Theory, 1992. 4. Robert E. Schapire. Drifting games. Machine Learning, 43(3):265-291, 2001. 5. N. Cesa-Bianchi, Y. Freund, D.P. Helmbold, D. Haussler, R. Schapire, and M.K. Warmuth How to use expert advice Journal of the ACM, 44(3):427-485, 1997. 6. N. Cesa-Bianchi, Y. Freund, D.P. Helmbold, and M.K. Warmuth On-line prediction and conversion strategies Machine Learning, 25:71-110, 1996. 7. J. Abernethy, J. Langford, M. Warmuth Continuous Experts and the Binning Algorithm COLT 2006 8. Nick Littlestone and Manfred K. Warmuth The weighted majority algorithm. Information and Computation, 108:212-261, 1994. 9. Joel Spencer Ulam's searching game with a fixed number of lies. Theoretical Computer Science, 95(2):307-321, 1992 10. David Blackwell An analog of the minmax theorem for vector payoffs. Pacific J. Math. Volume 6, Number 1 (1956), 1-8. Books: ====== 1. Stuart Russell, Peter Norvig. Artificial Intelligence: A modern approach. Chapters: 3.1-3.5 4.1-4.3 6 7.1-7.6 11.1-11.5 8.1-8.3 13.1-13.6 14.1-14.5 15.1-15.6 16.1-16.3 17.1-17.4 18.1-18.5 20.1-20.3,20.5-20.6 21.1-21.4 26 2. Luc Devroye, Laszlo Gyorfi, Gabor Lugosi A Probabilistic Theory of Pattern Recognition Chapters: 2,4,6.1,6.2,6.7,6.8 7,8,12,13,14,15,16, 28, 29, 30 3. Nicolo Cesa Bianchi, Gabor Lugosi Prediction Learning and Games Chapters: 2,3, 4.1-4.3, 6.1-6.3,6.7-6.9, 7.1-7.3, 7.7 - 7.8, 8, 9.1-9.5, 9.8 - 9.11, all of 10 except 10.6, 11.1 - 11.5

1 0

J Jiang general exam - time change
by Melissa M Lawson 09 May '08

09 May '08

Joe Wenjie Jiang's general exam, scheduled for Monday May 12, has been moved from 10AM to 9:30AM start time. It will still be held in Room 402.

1 0

Juan Chen talk, Friday May 16
by Andrew W. Appel 08 May '08

08 May '08

1 0

T Jablin general exam
by Melissa M Lawson 07 May '08

07 May '08

Tom Jablin will present his research seminar/general exam on Thursday May 15 at 1PM in Room 402. The members of his committee are: David August (advisor), Doug Clark, and J.P. 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. -------------------------------- Pattern Driven Specialization Overcomes Static Limitations on Automatic Parallelization The multi-core revolution has arrived. Unfortunately, single-threaded applications do not benefit from multiple cores, and the benefit for multi-threaded applications is limited by Amdahl's law. A recent study shows that 32-cores worth of TLP (thread-level parallelism) can be automatically extracted from sequential codes with minor annotation using static profiling, analysis, and state-of-the-art transformations.[1] To achieve the next order of magnitude of TLP, the limits of static profiling must be addressed. Many important applications, interpreters being one example, suffer severely from these limits. In the case of interpretors, it is impossible to characterize the execution patterns without the interpreted code. However, runtime observations can discover regions in the interpreter that, due to predictable patterns in the interpreted program manifesting in the interpretor, are amenable to automatic parallelization. Run-time optimization can exploit this opportunity, eliminating the need to write parallelizers for interpreted languages. In this talk, I show that even if there is little TLP in a static program, there is often considerable parallelism in the program considered with its input set. Programmers and compilers cannot exploit this potential parallelism, but the dynamic system I will propose can. Citation: [1] Revisiting the Sequential Programming Model for the Multicore Era Matthew J. Bridges, Neil Vachharajani, Yun Zhang, Thomas Jablin, and David I. August Proceedings of the 40th IEEE/ACM International Symposium on Microarchitecture (MICRO), December 2007. Reading List Compilers: Principles, Techniques, and Tools by Aho and Ullman Modern Compiler Implementation in ML by Andrew W. Appel Experiments in Program Compilation by Interpreter Specialization by Thibault et al. Identifying Hierarchical Structure in Sequences: A linear-time algorithm by G. G. Nevill-Manning and I. H. Witten Analysis of control flow patterns in the execution of SPEC CPU2000 benchmark programs by Joseph, P. J. and Mattew Jacob, T. Revisiting the Sequential Programming Model for the Multicore Era by Bridges et al. Speculative Decoupled Software Pipelining by Vachharajani et al. Decoupled Software Pipelining with the Synchronization Array by Ottoni et al. Automatic Thread Extraction with Decoupled Software Pipelining by Ottoni et al. A General Approach for Run-Time Specialization and its Application to C by Dynamic Native Optimization of Interpreters by Gregory T. Sullivan, Derek L. Bruening, Iris Baron, Timothy Garnett A Tour of Tempo: A Program Specializer for the C Language by Charles Consel, Julia L. Lawall, Anne-Françoise Le Meur

1 0

reminder: 1-2pm talk today in room 302 on Learning Structured Bayesian Networks by Marie desJardins
by Jennifer Rexford 07 May '08

07 May '08

Speaker: Professor Marie desJardins, University of Maryland Title: Learning Structured Bayesian Networks: Combining Abstraction Hierarchies and Tree-Structured Conditional Probability Tables Date/time: 1-2pm Wednesday May 7 Location: 302 in the CS Building Abstract: In this talk, I will describe our research on incorporating background knowledge in the form of feature hierarchies during Bayesian network learning. Feature hierarchies enable the learning system to aggregate categorical variables in meaningful ways, thus enabling an appropriate "discretization" for a categorical variable. In addition, by choosing the appropriate level of abstraction for the parent of a node, we also support compact representations for the local probability models in the network. We combine this notion of selecting an appropriate abstraction with context-specific independence representations, which capture local ndependence relationships among the random variables in the Bayesian network. Capturing this local structure is important because it reduces the number of parameters required to represent the distribution. This can lead to more robust parameter estimation and structure selection, more efficient inference algorithms, and more interpretable models. I will describe our primary contribution, the Tree-Abstraction-Based Search (TABS) algorithm, which learns a data distribution by inducing the graph structure and parameters of a Bayesian network from training data. TABS combines tree structure and attribute-value hierarchies to compactly represent conditional probability tables. In order to construct the attribute-value hierarchies, we investigate two data-driven techniques: a global clustering method, which uses all of the training data to build the attribute-value hierarchies, and can be performed as a preprocessing step; and a local clustering method, which uses only the local network structure to learn attribute-value hierarchies. Empirical results in several benchmark domains show that (1) combining tree structure and attribute-value hierarchies improves the accuracy of generalization, while providing a significant reduction in the number of parameters in the learned networks, and (2) data-derived hierarchies perform as well or better than expert-provided hierarchies. BIOGRAPHY Dr. Marie desJardins is an associate professor in the Department of Computer Science and Electrical Engineering at the University of Maryland, Baltimore County. Her research is in artificial intelligence, focusing on the areas of machine learning, multi-agent systems, planning, interactive AI techniques, information management, reasoning with uncertainty, and decision theory. Dr. desJardins can be contacted at the Dept. of Computer Science and Electrical Engineering, University of Maryland Baltimore County, 1000 Hilltop Circle, Baltimore MD 21250, mariedj(a)cs.umbc.edu,(410) 455-3967.

1 0

Indranil Gupta talk at 12:30pm today, room 402
by Michael J Freedman 06 May '08

06 May '08

Today, Indranil Gupta from UIUC will be visiting us and speaking at Systems Lunch in room 402 (food at 12:00pm, talk at 12:30pm). The title and abstract of his talk is below. Cheers, --mike ========= Title: Wizards and Fruitflies -- Using Eternal and Ephemeral Overlays for Monitoring Distributed Systems Speaker: Indranil Gupta, Assistant Professor, Department of Computer Science, University of Illinois at Urbana-Champaign Abstract: Many distributed applications running over emerging large-scale distributed infrastructures, such as p2p systems, PlanetLabs and Grids, require the capability to monitor and manage a large distributed set of nodes at run-time. While many solutions exist for network and infrastructure-level monitoring, there is a scarcity of management solutions that work at the level of the distributed application, e.g., for monitoring node availability, count, top-k loaded nodes, querying log-files, etc. At the same time, much work has been done in the community on both persistent overlays such as distributed hash tables (DHTs), as well as unstructured overlays (e.g., Gnutella). However, we find that two alternative, unexplored, and opposing extremes of the design spectrum - eternal and ephemeral overlays - are better suited to solving the above management tasks. We present two systems -- AVMON and MON -- that seek to provide to distributed applications (and deployers) the ability to both monitor long-term availability histories of nodes in a distributed application, as well as to query the group of nodes on the fly. AVMON is a scalable availability monitoring overlay that is resilient to selfish and colluding nodes. AVMON imbues the concept of an eternally persistent (hence eternal) overlay, where peering relationships between nodes, once established, remain forever. Our other system, called MON, allows instant monitoring and management tasks, using the novel concept of an on-demand and short-lived (hence ephemeral) overlay, which survives only for the purpose of an individual management command. Both AVMON and MON are lightweight and fast in terms of memory, computation, bandwidth, and response time. Our mathematical analysis, trace-based simulations, and deployment atop PlanetLab, all demonstrate the practical performance characteristics of these two approaches in systems containing hundreds to thousands of nodes. We touch briefly upon how to use AVMON for building availability-aware services, the usage of MON in PlanetLab, as well as on other instances of eternal and ephemeral overlays we have studied. Speaker Bio: Indranil Gupta is an assistant professor in the Department of Computer Science at the University of Illinois at Urbana-Champaign. He received his PhD in Computer Science from Cornell University in 2004. He is a recipient of the NSF CAREER award in 2005. His research group DPRG works on distributed protocols and systems, with applications to large-scale distributed systems such as peer-to-peer systems and sensor networks. DPRG research is funded by several NSF grants, including multi-disciplinary ones. For more information on DPRG, visit http://dprg.cs.uiuc.edu

1 0

Q Xi general exam
by Melissa M Lawson 05 May '08

05 May '08

Qian Xi will present her research seminar/general exam on Tuesday May 13 at 2PM in Room 402. The members of her committee are: David Walker (advisor), David Blei, 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. --------------------------- Ad hoc data sources are semi-structured data sources that are widely used in many research fields, but lack useful data analysis and transformation tools. The goal of the PADS system is to help programmers manipulate ad hoc data sources by providing automatic support for the generation of data processing tools. The tool generation infrastructure has multiple parts in it: (1) a simple tokenization phase (2) a rough data format inference phase (3) a data format refinement phase (4) a tool generation phase One serious limitation of the current implementation involves the tokenization phase. In particular, the current system is unable to handle ambiguous tokens. In this research, we tackle the token ambiguity problem with a more general approach. Two probabilistic models, a character-by-character Hidden Markov Model and a hierarchical model, are established by extracting statistical information from a collection of training data sources, labeled using a tool generated from hand-written descriptions. We show how to incorporate the learned Markov models into the rest of the algorithm to enhance format inference. We will explain the algorithms and implementations behind our new system and we will evaluate its success using a number of measures. Books: - Benjamin C. Pierce: Types and Programming Languages, Chapter 1-11, 13-24. - Stuart J. Russell, Peter Norvig: Artificial Intelligence, A Modern Approach (2nd edition), Chapter 13, 15 (15.1-15.3, 15.6) - Christopher M. Bishop: Pattern Recognition and Machine Learning, Chapter 8, Chapter 13 (13.1-13.2) Papers: - Kathleen Fisher, David Walker, Kenny Q. Zhu, and Peter White. From Dirt to Shovels: Fully Automatic Tool Generation from Ad Hoc Data. Proceedings of the 35th annual ACM SIGPLAN-SIGACT symposium on Principles of programming languages, 2008. - Nicholas Kushmerick, Daniel S. Weld, Robert Doorenbos. Wrapper Induction for Information Extraction. International Joint Conference on Artificial Intelligence, 1997. - David Pinto, Andrew McCallum, Xing Wei and W. Bruce Croft. Table Extraction Using Conditional Random Fields. Proceedings of the 2003 annual national conference on Digital government research. - Geert Jan Bex, Frank Neven, Thomas Schwentick, and Karl Tuyls. Inference of concise DTDs from XML data. Proceedings of the 32nd international conference on Very Large Data Bases, 2006. - Vinayak Borkar, Kaustubh Deshmukhy, and Sunita Sarawagiz. Automatic Segmentation of Text into Structured Records. Proceedings of the 2001 ACM SIGMOD international conference on Management of data, 2001. - Arvind Arasu and Hector Garcia-Molina. Extracting Structured Data From Web Pages. Proceedings of the ACM SIGMOD international conference on Management of data, pages 337¨C348, 2003. - E. M. Gold. Language Identification in the Limit. Information and Control, 1967. - Stephen Soderland. Learning Information Extraction Rules for Semistructured and Free Text. Machine Learning, 1999.

1 0

P Calamia preFPO
by Melissa M Lawson 05 May '08

05 May '08

Paul Calamia will present his preFPO on Tuesday May 13 at 10AM in Room 402. The members of his committee are: Tom Funkhouser, Advisor; Peter Svensson (Norwegian Univ. of Science and Technology) and Perry Cook, Readers; Szymon Rusinkiewicz and Adam Finkelstein, Non-Readers. Everyone is invited to attend his talk. His abstract follows below. --------------------------- Title: Advances in Virtual-Acoustic Simulations through Edge Diffraction and Multiresolution Modeling Abstract: In recent years there has been growing interest in modeling sound propagation in complex, three-dimensional (3D) environments. With diverse applications for the military, the gaming industry, psychoacoustics researchers, architectural acousticians, and others, advances in computing power and 3D audio-rendering techniques have driven research and development aimed at closing the gap between the auralization and visualization of virtual spaces. To this end, this thesis focuses on improving the physical and perceptual realism of sound-field simulations in virtual environments through two distinct approaches: accurate and efficient computation of edge diffraction, and multiresolution modeling. To model sound propagation in virtual environments, acoustical simulation tools commonly rely on geometrical-acoustics (GA) techniques which assume asymptotically high frequencies, large flat surfaces, and ray-like paths. Such techniques can be augmented with diffraction modeling to compensate for the effect of surface size on the strength and directivity of a reflection, to allow for propagation around obstacles and into shadow zones, and to maintain soundfield continuity across reflection and shadow boundaries. Using a time-domain, line-integral diffraction expression known as the Biot-Tolstoy-Medwin (BTM) formulation, this thesis explores various aspects of diffraction calculations for virtual-acoustic simulations. Specifically, we first present analytical approximations for the BTM formulation which allow for accurate numerical computations for receivers at or near shadow and reflection boundaries, locations where the original diffraction integral experiences a singularity. We then describe an edge-subdivision strategy that allows for fast diffraction calculations with low error relative to a numerically more accurate solution. We present a novel method to find GA components using diffraction parameters which ensures continuity at reflection and shadow boundaries. Finally, to address the considerable increase in propagation paths due to diffraction, we describe a simple procedure for identifying and culling insignificant diffraction components during a virtual-acoustic simulation. The secondary thrust of this thesis involves the extension of GA techniques to highly detailed 3D models through a multiresolution approach. Such models, e.g. those created for architectural renderings or resulting from laser scans of building interiors, often exist as noisy meshes that comprise faces which are too small and too numerous for use with GA methods. To address these issues, we have developed a system in which image sources that give rise to specular reflections can be merged using frequency-dependent clustering criteria. The result is a significantly reduced set of aggregate image-sources which characterize a model's geometry and its reflection properties in a frequency-dependent, multiresoultion representation.

1 0

J Jiang general exam
by Melissa M Lawson 05 May '08

05 May '08

Joe Wenjie Jiang will present his research seminar/general exam on Monday May 12 at 10AM in Room 402. The members of his committee are: Jennifer Rexford (advisor), Mung Chiang (ELE), and Michael Freedman. 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 : Cooperative Content Distribution and Traffic Engineering in a Provider Network Traditionally, Internet Service Providers (ISPs) make profit by providing Internet connectivity, while content providers (CPs) play the more lucrative role of delivering content to users. As network connectivity is increasingly a commodity, ISPs have a strong incentive to offer content to their subscribers by deploying their own Content Distribution Networks (CDNs). Running both a CDN and the underlying network presents new opportunities for coordination between server selection (to match servers with subscribers) and traffic engineering (to select efficient routes for the traffic). In this work, we utilize a mathematical framework to show that separating server selection and traffic engineering leads to a sub-optimal equilibrium, even when the CDN is given accurate and timely information about network conditions. Leveraging ideas from cooperative game theory, we propose that the system implements a Nash bargaining solution that significantly improves the fairness and efficiency of the joint system. This study is another step towards a systematic understanding of the interactions between those who generate and distribute contents and those who provide and operate networks. Reading List Textbook [1] L. Peterson and B. Davie, Computer Networks: A Systems Approach, 3rd edition, Morgan Kaufmann Publishers, May 2003. Research papers: [1] D. Clark, "The design philosophy of the DARPA Internet protocols," ACM SIGCOMM Computer Communication Review, Vol. 18, No. 4, pp. 106-114, Aug. 1988. [2] T. Karagiannis, P. Rodriguez and K. Papagiannaki, "Should Internet Service Providers fear peer-assisted content distribution", IMC'05: Proceedings of the Internet Measurement Conference 2005 on Internet Measurement Conference, pp. 6-6, 2005. [3] A. Su, D. R. Choffnes, A. Kuzmanovic and F. Bustamante, "Drafting behind Akamai (Travelocity-based detouring)", SIGCOMM 2006, pp. 435-446, 2006. [4] M. Garetto, D. R. Figueiredo, R. Gaeta and M. Sereno, "A modeling framework to understand the tussle between ISPs and peer-to-peer file-sharing users", Performance Evaluation, vol. 64, no. 9-12, pp. 819-837, 2007. [5] V. Aggarwal, A. Feldmann and C. Scheideler, "Can ISPS and P2P users cooperate for improved performance?", ACM SIGCOMM Computer Communication Review, vol. 37, no. 3, pp. 29-40, 2007. [6] H. Xie, A, Krishnamurthy, A. Silberschatz and Y. R. Yang, "P4P: Explicit Communications for Cooperative Control Between P2P and Network Providers", P4P Working Group position paper. [7] C. Huang, J. Li and K. W. Ross, "Can Internet video-on-demand be profitable?", SIGCOMM'07, pp. 133-144, 2007. [8] M. J. Freedman, C. Aperjis and R. Johari, "Prices are Right: Managing resources and incentives in peer-assisted content distribution", in submission. [9] T. Koponen, M. Chawla, B.-G. Chun, A. Ermolinskiy, K. H. Kim, S. Shenker, I. Stoica, "A Data-Oriented (and Beyond) Network Architecture", SIGCOMM'07, pp. 181-192, 2007. [10] M. Castro, P. Druschel, A-M. Kermarrec, A. Nandi, A. Rowstron and A. Singh, "SplitStream: High-bandwidth content distribution in a cooperative environment", ACM SOSP'03. [11] Antony I. T. Rowstron and Peter Druschel, "Pastry: Scalable, Decentralized Object Location, and Routing for Large-Scale Peer-to-Peer Systems", Middleware '01: Proceedings of the IFIP/ACM International Conference on Distributed Systems Platforms Heidelberg, pp. 329-350, 2001. [12] M. Piatek, T. Isdal, T. Anderson, A. Krishnamurthy and A. Venkataramani, "Do incentives build robustness in BitTorrent?", NSDI'07.

1 0

1-2pm Wed May 7 talk on Learning Structured Bayesian Networks by Marie desJardins
by Jennifer Rexford 04 May '08

04 May '08

Speaker: Professor Marie desJardins, University of Maryland Title: *Learning Structured Bayesian Networks: Combining Abstraction Hierarchies and Tree-Structured Conditional Probability Tables Date/time: 1-2pm Wednesday May 7 Location: 302 in the CS Building Abstract: * In this talk, I will describe our research on incorporating background knowledge in the form of feature hierarchies during Bayesian network learning. Feature hierarchies enable the learning system to aggregate categorical variables in meaningful ways, thus enabling an appropriate "discretization" for a categorical variable. In addition, by choosing the appropriate level of abstraction for the parent of a node, we also support compact representations for the local probability models in the network. We combine this notion of selecting an appropriate abstraction with context-specific independence representations, which capture local ndependence relationships among the random variables in the Bayesian network. Capturing this local structure is important because it reduces the number of parameters required to represent the distribution. This can lead to more robust parameter estimation and structure selection, more efficient inference algorithms, and more interpretable models. I will describe our primary contribution, the Tree-Abstraction-Based Search (TABS) algorithm, which learns a data distribution by inducing the graph structure and parameters of a Bayesian network from training data. TABS combines tree structure and attribute-value hierarchies to compactly represent conditional probability tables. In order to construct the attribute-value hierarchies, we investigate two data-driven techniques: a global clustering method, which uses all of the training data to build the attribute-value hierarchies, and can be performed as a preprocessing step; and a local clustering method, which uses only the local network structure to learn attribute-value hierarchies. Empirical results in several benchmark domains show that (1) combining tree structure and attribute-value hierarchies improves the accuracy of generalization, while providing a significant reduction in the number of parameters in the learned networks, and (2) data-derived hierarchies perform as well or better than expert-provided hierarchies. BIOGRAPHY Dr. Marie desJardins is an associate professor in the Department of Computer Science and Electrical Engineering at the University of Maryland, Baltimore County. Her research is in artificial intelligence, focusing on the areas of machine learning, multi-agent systems, planning, interactive AI techniques, information management, reasoning with uncertainty, and decision theory. Dr. desJardins can be contacted at the Dept. of Computer Science and Electrical Engineering, University of Maryland Baltimore County, 1000 Hilltop Circle, Baltimore MD 21250, mariedj(a)cs.umbc.edu,(410) 455-3967. * *

1 0