^November December – 2010 ^January

The standard problem of authorship attribution is that of determining which of a small closed set of candidates (for each of whom we have known writings) is the author of some anonymous text. This problem is well understood and can be regarded as solved (using standard NLP and machine learning tools). However, in the real world, we rarely encounter the standard problem, but rather much harder problems in which there are thousands of candidate authors and we have no guarantee that any of them is the actual author. We will review the state of the art regarding the harder versions and will discuss a number of very useful applications. If time permits, we will discuss some recent astonishing results on biblical literature.

The popularity of game theory can be witnessed through the widespread application of its models to different research areas. However, the application of game theoretical models is often done with limited consideration to the underlying assumptions of the models. In this talk I present two problem domains and show how such inherited assumptions limit the accuracy and usefulness of the solutions. The first domain comes form mainstream AI, game-tree search. Game-tree search algorithms are heavily based on theoretical results that assume both unbounded computational resources and rational players. In reality, for most games, players cannot search the entire tree due to computational limitations. As such, algorithms use various techniques to increase their search horizon under a common assumption that deeper search yields more accurate decisions. However, it was shown more than 30 years ago that there exist a class of games, namely Pathological games, in which this assumption is incorrect. In this research I show that game-tree pathology is a local phenomena that might exist in *all* games. I will then present an algorithm that recognizes pathological sub-trees and adapts its decision procedure accordingly. The second problem is the evolution of cooperation, an interdisciplinary problem from AI and Theoretical Biology. To study this problem researchers often use the Prisoner's dilemma game to model the interactions between players. Most of the existing works use the selfish, self-maximizing player model that was inherited from game theoretical analysis. However, theories from the social and behavioral sciences show that people explicitly consider the payoff of other players when making decisions. As such, we utilize the Social Value Orientation theory to present a new player model which provide a more accurate description of human behavior. With this new model we were able to gain new insights on the evolution of cooperative societies.

Linear classification is a fundamental problem of machine learning, in which positive and negative examples of a concept are represented in Euclidean space by their feature vectors, and we seek to find a hyperplane separating the two classes of vectors. We give the first sublinear-time algorithms for linear classification and other related problems in machine learning, including the kernelized versions of these problems. These new algorithms are based on a primal-dual approach, and use a combination of novel sampling techniques and the randomized implementation of online learning algorithms. We give lower bounds which show our running times to be nearly best possible in the unit-cost RAM model. Joint work with Ken Clarkson and David Woodruff, appeared in FOCS 2010.

Boosting is a general method in machine learning to improve the prediction accuracy of weak learners. A classic boosting algorithm that deals with the case of deciding between two possible classes is the Adaboost algorithm of Freund and Shpire (JCSS 1997). We propose a new approach to generalize AdaBoost to the multi-class setting. The basic idea is to map labels and confidence-based classifiers to a normed vector space, and to measure performance by distances in this space. The result is a meta-algorithm whose concrete implementations can address various scenarios, from the standard case where each example is assigned to a single class, to more complex settings where each example may belong to a set of classes, and where there is a structure on the label-space which can be captured by distances in a normed space. Joint work with Michal Rosen-Zvi.

Given a weighted graph, the maximum weight matching problem (MWM) is to find a set of vertex-disjoint edges with maximum weight. In the 1960s Edmonds showed that MWMs can be found in polynomial time. At present the fastest MWM algorithm, due to Gabow and Tarjan, runs in roughly $O~(msqrt{n})$ time, where $m$ and $n$ are the number of edges and vertices in the graph. Surprisingly, restricted versions of the problem, such as computing $(1-epsilon)$-approximate MWMs or finding maximum cardinality matchings, are not known to be much easier. The best algorithms for these problems also run in $O~(msqrt{n})$ time.

In this paper we present the first near-linear time algorithm for computing $(1-epsilon)$-approximate MWMs. Specifically, given an arbitrary real-weighted graph and $epsilon>0$, our algorithm computes such a matching in $O(mepsilon^{-2}log^3 n)$ time. The previous best approximate MWM algorithm with comparable running time could only guarantee a $(2/3-epsilon)$-approximate solution. In addition, we present a faster algorithm, running in $O(mlog nlogepsilon^{-1})$ time, that computes a $(3/4-epsilon)$-approximate MWM.

I will introduce confidence-weighted linear classifiers, a class of algorithms that maintain confidence information about classifier parameters. Instead of a single weight vector, learned hypotheses are given by Gaussian distributions over weight vectors, with a covariance matrix that represents uncertainty about weights and correlations between different weights. Learning in this framework updates parameters by estimating weights and increasing model confidence. I will describe few online algorithms that maintain a Gaussian distribution over weight vectors, updating the mean and variance of the model with each instance. A mistake bound analysis shows that indeed the algorithm performs better under some conditions and also relates between our model and the margin and loss analysis of previous models. Empirical evaluation on a range of NLP tasks show that our algorithm improves over other state of the art online and batch methods, learns faster in the online setting, ends itself to better classifier combination after parallel training and is suites better for active learning. Based on joint work with Mark Dredze,Alex Kulesza and Fernando Pereira.

The classical randomness notions of Schnorr and Kurtz permit gamblers to bet any amount of money within their means. In this talk, we consider a more realistic paradigm in which gamblers must place a minimum bet of one dollar. The corresponding randomness notion turns out to be incomparable with the classical notions mentioned above. Most casinos operate by exploiting the law of large numbers, however, by examining an even more restrictive model in which we ban wagers greater than a million dollars, we obtain an alternate principle through which an online casino might operate profitably. The open questions at the end of this talk should be accessible to a general audience.