^December January – 2012 ^February

Heuristic state-space search is one of the major success stories of artificial intelligence. Designing successful search heuristics, however, is often considered to be some kind of black magic. In my talk, I will argue that "heuristic" does not imply "unprincipled" and that rigorous scientific discipline can be successfully and fruitfully applied to the study of search heuristics. Specifically, I will explore formal theoretical relationships between the major classes of heuristics that have been suggested in the area of automated planning and will show that the exploration of such relationships can guide us in the design of better, practically effective heuristics.

Efficient concurrent data structures are extremely important for obtaining good performance for most parallel programs. However, ensuring the correctness of concurrent data structure implementations can be very tricky because of concurrency bugs such as race conditions and deadlocks. In systems that use optimistic parallel execution such as boosted transactional memory systems and the Galois system, the implementation of concurrent data structures is even more complex because data structure implementations must also detect conflicts between concurrent activities and support the rollback of conflicting activities. At present, these types of concurrent data structures are implemented manually by expert programmers who write explicitly parallel code packaged into libraries for use by application programmers. This solution has its limitations; for example, it does not permit the customization or tuning of a data structure implementation for a particular application. In this talk, we present Autograph, which is the first concurrent data structure compiler that can synthesize concurrent relational data structure implementations for use by application programmers. The input to Autograph is a high-level declarative specification of an abstract data type (ADT); the output is a concurrent implementation of that ADT with conflict detection and rollback baked in. Our synthesizer is parameterized by a set of data structures called “tiles”, which are building blocks that the compiler composes to create the overall data structure. Application programmers can use a simple expression language to tune the composition of these tiles, thereby exercising high level, fine-grain control of data structure implementations. We have used Autograph to synthesize concurrent sparse graph data structures for a number of complex parallel graph benchmarks. Our results show that the synthesized concurrent data structures usually perform better than the handwritten ones; for some applications and thread counts, they improve performance by a factor of 2.

The ease of seeing conceals many complexities. A fundamental one is the problem of fragmentation – we are able to recognize objects although they are optically incomplete, e.g., due to occlusions. To overcome this difficulty, biological and artificial visual systems use a mechanism for contour completion, which has been studied by the many disciplines of vision science, mostly in an intra-disciplinary fashion. Recent computational, neurophysiological, and psychophysical studies suggest that completed contours emerge from activation patterns of orientation selective cells in the primary visual cortex, or V1. In this work we suggest modeling these patterns as 3D curves in the mathematical continuous space R^2 × S^1, a.k.a. the unit tangent bundle associated with the image plane R^2, that abstracts V1. Then, we propose that the completed shape may follow physical/biological principles which are conveniently abstracted and analyzed in this space. We implement our theories by numerical algorithms to show ample experimental results of visually completed curves in natural and synthetic scenes.

The field of automated, domain-independent planning seeks to build general-purpose algorithms enabling a system to synthesize a course of action that will achieve certain goals. Such algorithms perform reachability analysis in large-scale state models that are implicitly described in a concise manner via some intuitive declarative language. And though planning problems have been studied since the early days of Artificial Intelligence research, recent developments (and, in particular, recent developments in planning as heuristic search) have dramatically advanced the field, and also substantially contributed to some related fields such as software/hardware verification, control, information integration, etc. The difference between various algorithms for planning as heuristic search is mainly in the heuristic functions they define and use. Most typically, an (admissible) heuristic function for domain-independent planning is defined as the (optimal) cost of achieving the goals in an over-approximating abstraction of the planning problem in hand. Such an abstraction is obtained by relaxing certain constraints that are present in the specification of the real problem, and the desire is to obtain a provably poly-time solvable, yet informative abstract problem. The main questions are thus: What constraints should we relax to obtain such an effective over-approximating abstraction? How should we combine information provided by multiple such abstractions? In this talk we consider both these questions, and present some recent formal and empirical results that help answering these questions (sometimes even to optimality). Specifically, Considering Q1, we introduce a generalization of the pattern-database (PDB) homomorphism abstractions to what we called implicit abstractions. The basic idea is in abstracting the problem in hand into provably tractable fragments of optimal planning, alleviating by that the constraint of PDBs to use projections of only low dimensionality. We then introduce concrete instance of this framework called fork-decomposition, and show both formally and empirically that the admissible heuristics induced by the latter abstractions provide state-of-the-art worst-case informativeness guarantees on several standard domains. Considering Q2, we describe a procedure that takes a classical planning task, a forward-search state, and a set of abstraction-based admissible heuristics, and derives an optimal additive composition of these heuristics with respect to the given state. Most importantly, we show that this procedure is polynomial-time for arbitrary sets of all known to us abstraction-based heuristics such as PDBs, constrained PDBs, merge-and-shrink abstractions, fork-decomposition implicit abstractions, and implicit abstractions based on tractable constraint optimization. The talk is based on a joint work with Prof. Carmel Domshlak.

A particularly large class of macromolecular interactions consists of those mediated by a linear sequence motif in the partner molecule: peptide, DNA or RNA. Two approaches to computationally characterize such motif-mediated interactions have been put forward, using either machine learning algorithms or molecular modeling. Using the example of MHC class I proteins, I will discuss each approach's strengths and demonstrate their ability to shed light on intriguing biological phenomena.

A fundamental task in Natural Language Processing (NLP) is learning the syntax of human languages from text. The task is defined both in the sentence level ("syntactic parsing") where a syntactic tree describing the head-argument structure is to be created, and in the word level ("part-of-speech tagging") where every word is assigned a syntactic category such as noun, verb, adjective etc. This syntactic analysis is an important building block in NLP applications such as machine translation and information extraction. While supervised learning algorithms perform very well on these tasks when large collections of manually annotated text (corpora) exist, creating manually annotated corpora is costly and error prone due to the complex nature of annotation. Since most languages and text genres do not have large syntactically annotated corpora, developing algorithms that learn syntax with little human supervision is of crucial importance. The work I will describe is focused on learning better parsing and tagging models from limited amounts of manually annotated training data.Our key observation is that existing models for these tasks are defined at the sentence level, keeping inference tractable at the cost of discarding inter-sentence information. In this work we use Markov random fields to augment sentence-level models for parsing and part-of-speech tagging with inter-sentence constraints. To handle the resulting inference problem, we present a dual decomposition algorithm for efficient, exact decoding of such global objectives. We apply our model to the lightly supervised setting and show significant improvements to strong sentence-level models across six languages. Our technique is general and can be applied to other structured prediction problems in natural language processing and in other fields, to enable inference over large collections of data. Joint work with Alexander Rush, Amir globerson and Michael Collins.

A typical problem in speech and language processing has a very large number of training examples, is sequential, highly structured, and has a unique measure of performance, such as the word error rate in speech recognition, or the BLEU score in machine translation. The simple binary classification problem typically explored in machine learning is no longer adequate for the complex decision problems encountered in speech and language applications. Binary classifiers cannot handle the sequential nature of these problems, and are designed to minimize the zero-one loss, i.e., correct or incorrect, rather than the desired measure of performance. In addition, the current state-of-the-art models in speech and language processing are generative models that capture some temporal dependencies, such as Hidden Markov Models (HMMs). While such models have been immensely important in the development of accurate large-scale speech processing applications, and in speech recognition in particular, theoretical and experimental evidence have led to a wide-spread belief that such models have nearly reached a performance ceiling. In this talk, I first present a new theorem stating that a general learning update rule directly corresponds to the gradient of the desired measure of performance. I present a new algorithm for phoneme-to-speech alignment based on this update rule, which surpasses all previously reported results on a standard benchmark. I show a generalization of the theorem to training non-linear models such as HMMs, and present empirical results on phoneme recognition task which surpass results from HMMs trained with all other training techniques. I will then present the problem of automatic voice onset time (VOT) measurement, one of the most important variables measured in phonetic research and medical speech analysis. I will present a learning algorithm for VOT measurement which outperforms previous work and performs near human inter-judge reliability. I will discuss the algorithm’s implications for tele-monitoring of Parkinson’s disease, and for predicting the effectiveness of chemo-radiotherapy treatment of head and neck cancer.

Machine learning is an effective tool for predicting structured outputs, such as those arising from holistic scene understanding or 3D protein folding. As these problems grow in size, scalable and efficient methods are important for accurate prediction. In this talk I will present how to use duality theory to decompose large-scale prediction problems to many small-scale problems interdependent by messages that are sent along its correlated variables. The use of duality enabled us to handle efficiently web-scale data and achieve several improvements over existing prediction methods for indoor scene understanding, 3D depth estimation and 3D protein folding. In some cases, such as pose estimation, prediction is ambiguous. In this talk I will also present efficient methods for sampling from the set of probable predictions. This approach is based on new approximations and bounds for weighted counting which compute the weight of the heaviest configuration.

A popular approach to deal with the "curse of dimensionality" in relation with high-dimensional data analysis is to assume that points in these datasets lie on a low-dimensional manifold immersed in a high-dimensional ambient space. Kernel methods operate on this assumption and introduce the notion of local affinities between data points via the construction of a suitable kernel. Spectral analysis of this kernel provides a global, preferably low-dimensional, coordinate system that preserves the qualities of the manifold. In this presentation, the scalar relations used in this framework will be extended to matrix relations, which can encompass multidimensional similarities between local neighborhoods of points on the manifold. We utilize the diffusion maps methodology together with linear-projection operators between tangent spaces of the manifold to construct a super-kernel that represents these relations. The properties of the presented super- kernels are explored and their spectral decompositions are utilized to embed the patches of the manifold into a tensor space in which the relations between them are revealed. Two applications of the patch- to-tensor embedding framework for data clustering and classification will be presented.

For every fixed d and every n, we construct an n-point set G in R^d such that every line in R^d is contained in a halfspace that contains only 2n/(d+2) points of G (up to lower-order terms). Apparently, the point set G satisfies the following more general property: For every k, every k-flat in R^d is contained in a halfspace that contains only (k+1) n / (d+k+1) points of G (up to lower-order terms). In 2008,Bukh, Matousek, and Nivasch conjectured the following generalization of Rado's centerpoint theorem: For every n-point set S in R^d and every k, there exists a k-flat f in R^d such that every halfspace that contains f contains at least (k+1) n / (d+k+1) points of S (up to lower-order terms). (The centerpoint theorem is obtained by setting k=0.) Such a flat f would be called a "centerflat". Thus, our upper bound construction shows that the leading constant (k+1)/(k+d+1) in the above conjecture is tight (certainly for k = 1, and apparently for all k). The set G of our construction is the "stretched grid" – a point set which has been previously used by Bukh et al. for other related purposes. Joint work with Boris Bukh.

Many image restoration tasks are ill posed problems, often solved with image priors. Since image priors are only approximate, in general this yields suboptimal restoration results. Given the large body of work on image priors and on image restoration algorithms, this begs fundamental questions of what are optimal restoration procedures, what are (if any) inherent limitations imposed by the statistics of natural images, and what potential gains we may expect from additional years of research efforts.

In this talk we focus on these problems for the simplest restoration task of natural image denoising, where the goal is to estimate a clean natural image, given a noise-corrupted version of it.

We propose a statistical framework and a non-parametric computational approach to study these questions: what is optimal natural image denoising ? what are its fundamental lower bounds, and how far are current algorithms from optimality ?

As we shall see, answers to these questions involve both computational limitations, information-statistical issues and a fundamental property of natural images - scale invariance. Their combination allows us to give a ballpark estimate on the best achievable denoising, and to suggest directions for potential improvements of current algorithms.

Joint work with Anat Levin, Fredo Durand and Bill Freeman.

The Sliding Scale Conjecture was posed by Bellare, Goldwasser, Lund and Russell in 1993 and has been open since. It says that there are PCPs with constant number of queries, polynomial alphabet and polynomially small error. We show that the conjecture can be proved assuming a certain geometric conjecture about curves over finite fields. The geometric conjecture states that there are small families of low degree curves that behave, both in their distribution over points and in the intersections between pairs of curves from the family, similarly to the family of all low degree curves.

Forty years ago, Wiesner pointed out that quantum mechanics raises the striking possibility of money that cannot be counterfeited according to the laws of physics. We propose the first quantum money scheme that is (1) public-key—meaning that anyone can verify a banknote as genuine, not only the bank that printed it, and (2) cryptographically secure, under a "classical" hardness assumption that has nothing to do with quantum money.Our scheme is based on hidden subspaces, encoded as the zero-sets of random multivariate polynomials. A main technical advance is to show that the "black-box" version of our scheme, where the polynomials are replaced by classical oracles, is unconditionally secure.Previously,such a result had only been known relative to a quantum oracle (and even there, the proof was never published). Even in Wiesner's original setting—quantum money that can only be verified by the bank—we are able to use our techniques to patch a major security hole in Wiesner's scheme. We give the first private-key quantum money scheme that allows unlimited verifications and that remains unconditionally secure, even if the counterfeiter can interact adaptively with the bank. Our money scheme is simpler than previous public-key quantum money schemes, including a knot-based scheme of Farhi et al.The verifier needs to perform only two tests, one in the standard basis and one in the Hadamard basis—matching the original intuition for quantum money, based on the existence of complementary observables.Our security proofs use a new variant of Ambainis's quantum adversary method, and several other tools that might be of independent interest.

A compression algorithm for a computation problem is a polynomial-time algorithm that compresses instances of the given problem into equivalent instances. The performance of the compression is naturally measured with respect to its worst-case output size. While NP-hard problems cannot have compression algorithms with non-trivial performance guarantees in terms of the original input size (assuming NP is not in P), some NP-hard problems have surprisingly good compressions when performance is measured in terms of the input solution size. In this talk we discuss some recently developed lower bounds for the compressibility of NP-hard problems when the latter measure is used.

In algorithmic graph theory one strives to exploit graph structure to design efficient algorithms for important, practical problems. In this talk we make the case for this paradigm by discussing recent progress in algorithms for fundamental optimization problems in planar graphs, with applications to basic problems in computer vision known as early vision tasks. We first discuss nearly linear time algorithms for computing shortest paths in directed planar graphs with positive and negative length arcs. We then describe in more detail a nearly linear time algorithm for finding a maximum single commodity flow in a planar network with multiple sources and sinks. These algorithms rely on a host of structural properties of planar graphs, including a beautiful relation between circulations in a planar graph and shortest paths in the planar dual of that graph. We conclude with a brief discussion of distance oracles for planar graphs. No prior knowledge of planar graphs is assumed.