^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.

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

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

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.