^October November – 2010 ^December

The process of extracting useful knowledge from large datasets has become one of the most pressing problems in today's society. The problem spans entire sectors, from scientists to intelligence analysts and web users, all of whom are constantly struggling to keep up with the larger and larger amounts of content published every day. With this much data, it is often easy to miss the big picture.

In this paper, we investigate methods for automatically connecting the dots – providing a structured, easy way to navigate within a new topic and discover hidden connections. We focus on the news domain: given two news articles, our system automatically finds a coherent chain linking them together. For example, it can recover the chain of events starting with the decline of home prices (January 2007), and ending with the ongoing health-care debate.

We formalize the characteristics of a good chain and provide an efficient algorithm (with theoretical guarantees) to connect two fixed endpoints. We incorporate user feedback into our framework, allowing the stories to be refined and personalized. Finally, we evaluate our algorithm over real news data. Our user studies demonstrate the algorithm's effectiveness in helping users understanding the news.

Cooperative game theory is all about how selfish agents might agree to collaborate and then share their spoils. It allows answering questions such as: Can selfish behaviour jeopardize our heath treatments in hospitals? Would the political power balance change if a big party decided to split into two smaller parties? How might pirates share a hidden treasure when they need each other to find it? Cooperation can be problematic when agents collaborate to attack an economic or political system. For example, agents participating in an auction can coordinate their bids in order to pay less for obtaining their items and political parties may strategically merge or split to increase their influence. This talk examines computational aspects of such phenomena, focusing on collusion in auctions and attacks in decision making bodies. Auctions based on the VCG mechanism are excellent in achieving truthful bids and an optimal allocation when agents do not collude. However, they are very susceptible to collusion. I will demonstrate this in multi-unit auctions and path procurement auctions, showing how the colluders can compute their optimal joint bidding strategy and reasonable agreements for sharing the gains. I will then consider attacks in weighted voting games, a known model for cooperation between agents in decision-making bodies, showing how agents can compute strategies that increase their power. The analysis for both domains is based on the core and the Shapley value, prominent solution concepts from cooperative game theory.

Active contours are used extensively in vision for more than two decades, primarily for applications such as image segmentation and object detection. The vast majority of active contours models make use of closed curves and the few that employ open curves rely on either fixed boundary conditions or no boundary conditions at all. We discuss a new class of open active contours with free boundary conditions, in which the end points of the open active curve are restricted to lie on two parametric boundary curves. We discuss how this class of curves may assist and facilitate various vision applications and we demonstrate its utility in applications such as boundary detection, feature tracking, seam carving, and image stitching.

Identification of rare variants by resequencing is important both for detecting novel variations and for screening individuals for known disease alleles. New technologies enable low-cost resequencing of target regions, although it is still prohibitive to test more than a few individuals. We propose a novel pooling design that enables the recovery of novel or known rare alleles and their carriers in groups of individuals. The method is based on a Compressed Sensing (CS) approach, which is general, simple and efficient. CS allows the use of generic algorithmic tools for simultaneous identification of multiple variants and their carriers. We model the experimental procedure and show via computer simulations that it enables the recovery of rare alleles and their carriers in larger groups than were possible before. Our approach can also be combined with barcoding techniques to provide a feasible solution based on current resequencing costs. For example, when targeting a small enough genomic region (~100 bp) and using only ~10 sequencing lanes and ~10 distinct barcodes per lane, one recovers the identity of 4 rare allele carriers out of a population of over 4000 individuals. We demonstrate the performance of our approach over several publicly available experimental data sets.

Joint work with Amnon Amir from the Weizmann Institute of Science, and Or Zuk from the Broad Institute of MIT and Harvard

Hidden Markov models (HMMs) were introduced and studied in the late 1960s, and early 1970s. One of the first applications of HMMs was speech recognition, starting in the mid-1970s. In the second half of the 1980s, HMMs began to be applied to recognition of handwritten text in images, commonly known as offline handwriting recognition (OHR). In this talk, I'll present the Hidden Markov Model, and show some examples, of how it can be applied to offline handwriting recognition.

Supervised Learning problems often involve inference of complex structured labels such as image segmentations of grid shape graphs. To achieve high accuracy in these tasks, one is often interested in introducing dependencies between label parts. However this usually results in inference problems that are NP hard. A natural approach is to use tractable approximation of the inference problems. In this talk I will present our recent work on approximate inference, using duality to extend the belief propagation algorithms to convex programs. Specifically, we show how convex belief propagation algorithms solve convex relaxations of the partition function, also referred as the free energy, as well as linear programming relaxations of integer linear programs. Also, I will present how duality and local inference can be applied to approximate current learning frameworks of conditional random fields (CRFs) and structured support vector machines (SVMs), and show highly scalable message-passing algorithms for these approximations. I will also present how these approximations can be applied to learn image segmentations. Based on joint work with: Amnon Shashua, Raquel urtasun, Ross Girshik

Can we use statistical Natural Language Processing methods on redundant data? Document collections (corpora) may include large amount of redundancy due to copied texts, this phenomena is common in news articles and Electronic Health Records. Methods for detecting and handling redundancy are common in the fields of Bioinformatics for creating sequence databases as well as for plagiarism detection. We will show that redundant text may bias statistical methods for processing such corpora as well as a robust heuristic for identifying a non-biased subset a corpus.

Gene Translation (GT) is the complex process of decoding the mRNA sequences by the ribosome to produce proteins. The rapid accumulation of genomic data and large scale measurements that are related to GT (e.g. sequencing of genomes and measurements of gene expression, protein abundance, and ribosome densities) enables developing computational models and performing large scale systems biological study of this biological process.In this talk, I will survey our recent results in understanding and modeling GT.Specifically, I will describe: (1) a novel systems biological analysis of the dynamic of ribosome movement based on the different features mRNA sequences, a key to understanding GT. (2) A computationally efficient predictive model of GT that is based on the physical and dynamic nature of this process. The talk is self-contained and requires no prior knowledge in Biology.

We define a novel variation on the constrained sequence alignment problem, the Sequence Alignment with Regular Expression Path Constraint (SA-REPC) problem, in which the constraint is given in the form of a regular expression. Our definition extends and generalizes the existing definitions of alignment-path constrained sequence alignments to the expressive power of regular expressions. We give a solution for the new variation of the problem and demonstrate its application to integrate microRNA-target interaction patterns into the target prediction computation. Our approach can serve as an efficient filter for more computationally demanding target prediction filtration algorithms. We compare our implementation for the SA-REPC problem, cAlign, to other microRNA target prediction algorithms.