- talks - lists.cs.princeton.edu

M Dudik preFPO
by Melissa M Lawson 07 Feb '07

07 Feb '07

Miro Dudik will present his preFPO on Friday February 9 at 10AM in Room 402. The members of his committee are Rob Schapire, advisor; David Blei and Stephen Phillips (AT&T), readers; Moses Charikar and Olga Troyanskaya, nonreaders. Everyone is invited to attend his talk. His abstract follows below. ----------------------------------------- Maximum entropy, generalized regularization, and modeling species habitats Maximum entropy (maxent) approach, equivalent to maximum likelihood, is a widely used method for estimating probability distributions. However, when trained on small datasets, maxent is likely to overfit. Therefore, many smoothing techniques were proposed to mitigate overfitting. In my dissertation, I propose a unified treatment for a large and general class of smoothing techniques including L1 and L2 regularization. As a result, it is possible to prove non-asymptotic performance guarantees and derive novel regularizations based on structure of the sample space. To obtain solutions for a large class of maxent problems, I propose new algorithms derived from boosting and iterative scaling. Convergence of these algorithms is proved using a novel method, which unifies previous approaches based on information geometry and compactness. As an application of maxent, I discuss an important problem in ecology: modeling distributions of biological species. Regularized maxent fits this problem well and offers several advantages over previous techniques. In particular, it addresses the problem in a statistically sound manner and allows principled extensions to situations when data is collected in a biased manner or when we have access to data on many related species. The utility of maxent is demonstrated on large real-world datasets.

1 0

C Myers preFPO
by Melissa M Lawson 05 Feb '07

05 Feb '07

Chad Myers will present his preFPO on Friday February 9 at 3:30 PM in Carl Icahn Lab Room 200. The members of his committee are: Olga Troyanskaya, advisor; Kai Li and David Botstein (MolBio, Genomics), readers; SY Kung (ELE) and Leonid Kruglyak (EEB, Genomics), non-readers. Everyone is invited to attend his talk. His abstract follows below. --------------------------------------- Title: Context-sensitive methods for learning from genomic data Abstract: Recent developments in biotechnology have enabled high-throughput measurement of several complementary cellular phenomena. The wealth of data generated by such technology promises to support computational prediction of network models, but so far, successful approaches that translate these data into accurate, experimentally testable hypotheses have been limited. My thesis focuses on machine learning and signal processing approaches that utilize contextual clues that often accompany biological data to extract useful information and make precise predictions. First, my thesis describes methods for using microarray technology to detect chromosomal aberrations. Amplification and deletion of portions of chromosomes often serves as a mechanism of rapid adaptation and have been associated with numerous cancers. Accurate and precise identification of when and where these changes occur will help us understand this important adaptive mechanism and enable steps towards effective cancer treatment. I discuss my solution to this problem, ChARM (Chromosomal Aberration Region Miner), a statistical signal processing approach based on expectation-maximization that uses chromosome context information to accurately identify even subtle chromosomal changes from either gene expression or CGH microarray data. Second, I have addressed the more general problem of integrating diverse types of functional genomic data (e.g. gene expression, protein-protein interactions, genetic interactions, sequence, and protein localization data) to understand gene function and predict biological networks. I discuss a system we have developed for integration of these diverse data and user-driven network inference. My key contribution in this area is the notion of query context-sensitive prediction. This idea is based on the observation that most experimental technologies capture different biological processes with varying degrees of success, and thus, each source of genomic data will vary in relevance depending on the biological process one is interested in predicting. Other key contributions of this work are the data visualization approaches that support intelligent, expert browsing of genomic data, which is a largely unexplored, but powerful paradigm in bioinformatics applications. I discuss evaluation of these methods and examples of biological validation, where we have used our system to characterize several new genes. Finally, my thesis addresses the question of how to use machine learning and other bioinformatics methods to direct large-scale genomic experiments. Until now, most bioinformatics methods have been applied downstream of data-generating experiments, serving mainly as tools for analysis. I discuss methods for directing large-scale experiments in the context of whole-genome genetic interaction screens. We have applied these methods in collaboration with experimental labs, and we demonstrate that such approaches enable more efficient use of high-throughput technology and, ultimately, help us to learn more novel biology.

1 0

P Shilane preFPO
by Melissa M Lawson 02 Feb '07

02 Feb '07

Phil Shilane will present his preFPO on Thursday February 8 at 10AM in Room 402. The members of his committee are; Thomas Funkhouser, advisor; Adam Finkelstein and Szymon Rusinkiewicz, readers; Andrea LaPaugh and Kai Li, nonreaders. Everyone is invited to attend his talk. His abstract follows below. ---------------------------------------- Title: Shape Distinction for 3D Model Retrieval Abstract: In recent years, there has been enormous growth in the number of 3D models and their availability to a wide segment of the population. Examples include the National Design Repository which stores 3D computer-aided design (CAD) models for tens of thousands of mechanical parts, the Protein Data Bank that has atomic positions for tens of thousands of protein molecules, and the Princeton Shape Benchmark with 36,000 everyday objects represented as polygonal surface models. Given the availability of 3D data, a key problem is searching through models efficiently. Finding similar objects in a database can provide information for protein analysis or to identify objects in a robotic-vision system. As another example, by searching a database of models, even a novice user could easily create new CAD objects or graphics models by assembling them from examples, instead of the complicated task of creating models from scratch. While previous work has approached the 3D retrieval problem by creating global feature vectors for each object or by creating numerous local feature vectors, my work focuses on "distinctive" regions of a surface that distinguish a shape from objects of a different class. Distinctive regions are analyzed based on performing a shape-based search using each surface region as a query into a database. Distinctive regions of a surface have shape consistent with objects of the same type and different from objects of other types. For a classified database of models, distinction can be analyzed in a pre-processing phase, but I also show that a likelihood model can predict distinction for new shapes based on a training set. Using a priority-driven search technique that focuses on the most distinctive regions of each shape provides better search results than any previously published work. While the current definition of distinction is based on shape retrieval, it is useful for other graphics applications such as mesh visualization, icon generation, and mesh simplification. I also propose a new methodology to analyze shape retrieval by creating a common dataset of classified 3D models and software tools called the Princeton Shape Benchmark (PSB). The freely available PSB includes the models, classification, annotations for each model, and a suite of software tools to evaluate and analyze shape-retrieval results. My experiments with these classifications expose different properties of shape-based retrieval methods that were not previously known. As an example, shape descriptors that had poor performance when considering all models in the PSB actually had the best performance on certain classes of models. Perhaps the largest contribution of the PSB is that the dataset and software tools make it easier to perform shape-similarity research. Undergraduate computer graphics courses, senior thesis work, and doctoral projects have experimented with the 3D models and tools making the PSB a de-facto standard for measuring shape-similarity methods in the Computer Graphics community.

1 0

D Dantas preFPO
by Melissa M Lawson 30 Jan '07

30 Jan '07

Daniel Dantas will present his preFPO at 10AM on Tuesday, February 6 in Room 402. The members of his committee are David Walker, advisor; Andrew Appel, Stephanie Weirich, readers; Ed Felten, and David August, nonreaders. Everyone is invited to attend his talk. His abstract follows below. ------------------------------ My thesis extends functional programming languages with aspect-oriented features, primarily to explore aspect-oriented enforcement of security policies. First, my thesis examines an aspect-oriented implementation of the Java security mechanism, which requires the security advice to be triggered by functions with diverse argument and return types. My thesis presents a new language, AspectML, that allows a programmer to define type-safe polymorphic advice using pointcuts constructed from a collection of polymorphic join points. I then compare my AspectML implementation of the Java security mechanism against the existing Java implementation. Second, in ordinary aspect-oriented programming, security and other advice added after-the-fact to an existing codebase can disrupt important data invariants and prevent local reasoning. Instead, my thesis shows that many common aspects, including security advice, can be implemented as harmless advice. Harmless advice uses a novel type and effect system related to information-flow type systems to ensure that harmless advice cannot modify the behavior of mainline code. To demonstrate the usefulness of harmless advice for security, I implemented many of the security examples used by the Naccio execution monitoring system by Evans and Twyman as harmless advice. Finally, my thesis expands the harmless advice specification to allow programmers to create interference policies for system libraries to define how those libraries can be used by aspects. These policies use a selection of compile-time type checking and run-time monitoring to enforce the desired definition of harmlessness on the aspect-oriented program. My thesis formalizes an idealized file IO system and proves that an interference policy specified by our policy language can continue to enforce our original view of harmlessness for advice that uses file IO.

1 0

S Kale preFPO
by Melissa M Lawson 23 Jan '07

23 Jan '07

Satyen Kale will present his preFPO on Tuesday January 30 at 1PM in Room 402. The members of his committee are: Sanjeev Arora, advisor; Moses Charikar and Rob Schapire, readers; Bernard Chazelle and Boaz Barak, nonreaders. Everyone is invited to attend his talk. His abstract follows below. _____ Title: Efficient Algorithms using the Multiplicative Weights Update method Algorithms based on convex optimization, especially linear and semidefinite programming, are ubiquitous in Computer Science. While there are polynomial time algorithms known to solve such problems, quite often the running time of these algorithms is very high. Designing simpler and more efficient algorithms is important for practical impact. In my talk, I will describe applications of the Multiplicative Weights Update method in the design of efficient algorithms for various optimization problems. This method, which was repeatedly discovered in quite diverse fields, is an algorithmic technique which maintains a distribution on a certain set of interest, and updates it iteratively by multiplying the probability mass of elements by suitably chosen factors based on the distribution. The central result of my thesis is a generalization of the method to the setting of symmetric matrices rather than real numbers. I will describe the following applications of the resulting Matrix Multiplicative Weights algorithm: 1. The first truly general, combinatorial, primal-dual method for designing efficient algorithms for semidefinite programming. Using these techniques, we obtain significantly faster algorithms for obtaining O(sqrt{log n}) approximations to various graph partitioning problems, such as Sparsest Cut, Balanced Separator in both directed and undirected weighted graphs, and the Min UnCut problem. 2. An O*(n^3) time derandomization of the Alon-Roichman construction of expanders using Cayley graphs. 3. An O*(n^3) time deterministic O(log n) approximation algorithm for the quantum hypergraph covering problem. 4. A simpler proof of a result of Aaronson that the gamma-fat-shattering dimension of quantum states on n qubits is O(n/gamma^2). I will also briefly mention the following algorithmic applications of the classical Multiplicative Weights Update method: 1. Fast algorithms for approximately solving several families of semidefinite programs, which beat interior point methods. 2. O(sqrt{log n}) approximation to the Sparsest Cut in graphs in O*(n^2) time.

1 0

A Karagiozova preFPO
by Melissa M Lawson 18 Jan '07

18 Jan '07

Adriana Karagiozova will present her preFPO on Thursday January 25 at 3PM in Room 402. The members of her committee are Moses Charikar, advisor; Bernard Chazelle, Bob Tarjan, readers; Boaz Barak, Bob Sedgewick, nonreaders. Everyone is invited to attend her talk. Her abstract follows below. -------------------------------------- Aspects of Network Design and Metric Space Embeddings In this talk I will present results on several problems in network design and metric space embeddings: 1) Multicommodity buy-at-bulk network design We seek to design a cheap network that satisfies the demands between the terminals of multiple source-sink pairs, where the edge costs experience economies of scale. We give the first non-trivial approximation algorithm for the general case of the problem. 2) Terminal Backup Given a graph with terminals, non-terminals and edge costs we want to find a forest that connects each terminal to at least one other terminal. We give a simple polynomial time algorithm that finds the cheapest such forest. In the process we show that a version of 3D matching, useful for tasks that involve splitting into groups of at least two members, is solvable in polynomial time. 3) Metric Ramsey phenomena A Ramsey theorem on metric spaces asks if given an arbitrary metric space, what is the size of the largest subspace that embeds into $\ell_p$ with distortion at most some target $\alpha$. Previous work shows a phase transition at $\alpha = 2$ for $p > 2$. We show that such a phase transition occurs at $\alpha = 2$ for all $p \geq 1$. 4) Embedding series-parallel graphs into $\ell_1$ We give an embedding of any n-point series-parallel metrics into $\ell_1$ with distortion O(\sqrt{\log n / \log s}), where every coordinate of the embedding is s-Lipschitz. Using this embedding we obtain various other results, among which is matching the dimension-reduction lower bound of Brinkman and Charikar.

1 0

K Park FPO
by Melissa M Lawson 17 Jan '07

17 Jan '07

KyoungSoo Park will present his final public oral on Wednesday January 24 at 2PM in Room 402. The members of his committee are: Vivek Pai, advisor: Larry Peterson and Jennifer Rexford, readers; Brian Kernighan and Andrea LaPaugh, nonreaders. A copy of his thesis, "Towards Highly Reliable and Scalable Distributed Systems" is on display in Room 310. Everyone is invited to attend his talk.

1 0

PLOrk Winter Concert : Jan. 18th
by Ge Wang 09 Jan '07

09 Jan '07

----- http://plork.cs.princeton.edu/upcoming.html ----- The Princeton Laptop Orchestra (PLOrk) presents PLOrk Winter Concert 8pm, Thursday January 18th, 2007 Taplin Auditorium, Princeton University featuring works and performances by: Perry R. Cook | MR Daniel | Scott Elmegreen | Rebecca Fiebrink | John Fontein | Michael Hammond | Anne Hege | Matt Hoffman | Laurie Hollander | Andrea Mazzariello | Ananya Misra | Spencer Salazar | Scott Smallwood | Alan Tormey | Ge Wang | Samson Young directed by Perry Cook and Ge Wang The Princeton Laptop Orchestra (PLOrk) presents an evening of new music, composed and performed by members of the Fall 2006 PLOrk ensemble and seminar. The event is free and open to the public. http://plork.cs.princeton.edu/ ----

1 0

B Guo preFPO
by Melissa M Lawson 02 Jan '07

02 Jan '07

Bolei Guo will present her preFPO on Tuesday January 9 at 1PM in Room 402. The members of her committee are; David August, advisor; Andrew Appel and Michael Hind (IBM TJ Watson), readers; Brian Kernighan and David Walker, nonreaders. Everyone is invited to attend her talk. Her abstract follows below. ------------------------------------------- "Low-Level Shape Analysis with Inductive Recursion Synthesis" Aggressive memory disambiguation for low-level code can eliminate the problem of conservatively propagating high-level memory analysis results. It critically affects the effective-ness of back-end code optimizations. In particular, automatic loop parallelization relies on a type of memory analysis called shape analysis, which determines the shapes of data structures built by the program. We designed a separation-logic-based shape analysis for low-level code. Separation logic with recursively defined predicates allows for concise yet precise description of the shapes of data structures. However, inferring such predicates is a difficult task. Current uses of separation logic involve pre-defined built-in predicates and logic rules specificially written for these predicates, limiting the class of analyzable programs. We developed an inductive learning technique to automatically infer arbitrary recursive shape predicates. In addition, to facilitate the interaction between local reasoning and the global invariants given by the recursive predicates, a notion of "truncation points" is introduced in a predicate, which gives rise to generic algorithms for unfolding and folding arbitrary data structures. This shape analysis uses the alias information provided by a fast low-level pointer analysis to identify recursive data structures and to prune away code that does not affect the result of shape analysis. It has been implemented in the Velocity compiler and evaluated on benchmarks from the SPEC2000 and Olden benchmark suites.

1 0

J Podolak preFPO
by Melissa M Lawson 11 Dec '06

11 Dec '06

Joshua Podolak will present his preFPO on Thursday December 14 at 3:30PM in Room 402. The members of his committee are Szymon Rusinkiewicz, advisor; Adam Finkelstein and Tom Funkhouser, readers; David Dobkin and Bernard Chazelle, nonreaders. Everyone is invited to attend his talk. His abstract follows below. ------------------------------ Symmetry is an important feature of almost all shapes: nearly every man-made object contains at least one plane of perfect symmetry and most natural objects exhibit near-perfect symmetries. However, symmetry information has been underutilized in computer graphics. In this thesis we will analyze both the perfect and the imperfect symmetries of 2D and 3D models and define a symmetry transform that captures all planar symmetries. We then examine some applications that can benefit from symmetry information such as alignment, completion, shape matching, segmentation, automatic viewpoint selection and remeshing.

1 0