Research

Home Contact info

Selected Publications

Computational and Statistical Machine Learning
Algorithmic Game Theory
Computer Vision
Books

Computational and Statistical Machine Learning

A Discriminative Framework for Clustering via Similarity Functions. With Avrim Blum and Santosh Vempala. STOC 2008. [view abstract]
Problems of clustering data from pairwise similarity information are ubiquitous in Computer Science. Theoretical treatments typically view the similarity information as ground-truth and then design algorithms to (approximately) optimize various graph-based objective functions. However, in most applications, this similarity information is merely based on some heuristic: the true goal is to cluster the points correctly rather than to optimize any specific graph property. In this work, we initiate a theoretical study of the design of similarity functions for clustering from this perspective. In particular, motivated by recent work in learning theory that asks "what natural properties of a similarity function are sufficient to be able to learn well?" we ask "what natural properties of a similarity function are sufficient to be able to em cluster well?"
We develop a notion of the clustering complexity of a given property (analogous to notions of capacity in learning theory), that characterizes its information-theoretic usefulness for clustering. We then analyze this complexity for several natural game-theoretic and learning-theoretic properties, as well as design efficient algorithms that are able to take advantage of them. We consider two natural clustering objectives: (a) list clustering: analogous to the notion of list-decoding, the algorithm can produce a small list of clusterings (which a user can select from) and (b) hierarchical clustering: the desired clustering is some pruning of this tree (which a user could navigate). Our algorithms for hierarchical clustering combine recent learning-theoretic approaches with linkage-style methods.

Improved Guarantees for Learning via Similarity Functions. With Avrim Blum and Nathan Srebro. COLT 2008.

The True Sample Complexity of Active Learning. With Steve Hanneke and Jennifer Wortman. COLT 2008.
Winner of the Mark Fulk Best Student Paper Award.

New Theoretical Frameworks for Machine Learning. Thesis Proposal, May 2007.

Asymptotic Active Learning. With Eyal Even-Dar, Steve Hanneke, Michael Kearns, Yishay Mansour, and Jennifer Wortman. NIPS 2007 Workshop on Principles of Learning Design Problem. [view abstract]
We describe and analyze a PAC-asymptotic model for active learning. We show that in many cases where it has traditionally been believed that active learning does not help, active learning does help asymptotically. This view contrasts sharply with the traditional 1/\epsilon lower bounds for active learning classes such as non-homogeneous linear separators under the uniform distribution or unions of k intervals under an arbitrary distribution, both of which are learnable at an exponential rate in our model.

Margin Based Active Learning. With Andrei Broder and Tong Zhang. COLT 2007. [view abstract]
We present a framework for margin based active learning of linear separators. We instantiate it for a few important cases, some of which have been previously considered in the literature. We analyze the effectiveness of our framework both in the realizable case and in a specific noisy setting related to the Tsybakov small noise condition.

Open Problems in Efficient Semi-Supervised PAC Learning. With Avrim Blum. COLT 2007.

Robust Reductons from Ranking to Classification. With Nikhil Bansal, Alina Beygelzimer, Don Coppersmith, John Langford, and Greg Sorkin. COLT 2007. Invited to appear in a special issue of Machine Learning Journal. [view abstract]
We reduce ranking, as measured by the Area Under the Receiver Operating Characteristic Curve (AUC), to binary classification. The core theorem shows that a binary classification regret of r on the induced binary problem implies an AUC regret of at most 2r.

An Augmented PAC Model for Semi-Supervised Learning. With Avrim Blum. Book Chapter in Semi-Supervised Learning, Chapelle, O., Zien, A., and Scholkopf, B. (Eds.), MIT Press, 2006.

On a Theory of Learning with Similarity Functions. With Avrim Blum. ICML 2006. Combined with subsequent paper by Nathan Srebro in journal version, invited to appear in a special issue of Machine Learning Journal. [view abstract]
Kernel functions have become an extremely popular tool in machine learning. They have an attractive theory that describes a kernel function as being good for a given learning problem if data is separable by a large margin in a (possibly very high-dimensional) implicit space defined by the kernel. This theory, however, has a bit of a disconnect with the intuition of a good kernel as a good similarity function. In this work we develop an alternative theory of learning with similarity functions more generally (i.e., sufficient conditions for a similarity function to allow one to learn well) that does not require reference to implicit spaces, and does not require the function to be positive semi-definite. Our results also generalize the standard theory in the sense that any good kernel function under the usual definition can be shown to also be a good similarity function under our definition. In this way, we provide the first steps towards a theory of kernels that describes the effectiveness of a given kernel function in terms of natural similarity-based properties.

Agnostic Active Learning. With Alina Beygelzimer and John Langford. ICML 2006. Invited to appear in a special issue on Learning Theory of the Journal of Computer and System Sciences. [view abstract]
We state and analyze the first active learning algorithm which works in the presence of arbitrary forms of noise. The algorithm, A², relies only upon the assumption that the samples are drawn i.i.d. from a fixed distribution. We show that A² achieves exponential improvement over the usual sample complexity of supervised learning for several settings considered before in the realizable case. These include learning threshold classifiers and learning homogeneous linear separators with respect to an input distribution which is uniform over the unit sphere.

Kernels as Features: On Kernels, Margins, and Low-dimensional Mappings. With Avrim Blum and Santosh Vempala. Machine Learning Journal 2006. An extended abstract appears in the 15th International Conference on Algorithmic Learning Theory (ALT '04). [view abstract]
Kernel functions are typically viewed as implicit mappings to a high-dimensional space that allow one to "magically" get the power of that space without having to pay for it, if data is separable in that space by a large margin. In this paper we show that in the presence of a large margin, a kernel can instead be efficiently converted into a mapping to a low dimensional space. In particular, we give an efficient procedure that, given black-box access to the kernel and unlabeled data, generates a small number of features that approximately preserve both separability and margin.

A PAC-style Model for Learning from Labeled and Unlabeled Data. With Avrim Blum. COLT 2005. [view abstract]
There has been growing interest in practice in using unlabeled data together with labeled data in machine learning, and a number of different approaches have been developed. However, the assumptions these methods are based on are often quite distinct and not captured by standard theoretical models. In this work we describe a PAC-style model designed with semi-supervised learning in mind, that can be used to help thinking about the problem of learning from labeled and unlabeled data and many of the different approaches taken. Our model provides a unified framework for analyzing when and why unlabeled data can help, and in which one can discuss both algorithmic and sample complexity issues.

Co-Training and Expansion: Towards Bridging Theory and Practice. With Avrim Blum and Ke Yang. NIPS 2004. [view abstract]
Co-training is a method for combining labeled and unlabeled data when examples can be thought of as containing two distinct sets of features. It has had a number of practical successes, yet previous theoretical analyses have needed very strong assumptions on the data that are unlikely to be satisfied in practice.
In this paper, we propose a much weaker expansion assumption on the underlying data distribution, that we prove is sufficient for iterative co-training to succeed given appropriately strong PAC-learning algorithms on each feature set, and that to some extent is necessary as well. This expansion assumption in fact motivates the iterative nature of the original co-training algorithm, unlike stronger assumptions (such as independence given the label) that allow a simpler one-shot co-training to succeed. We also heuristically analyze the effect on performance of noise in the data. Predicted behavior is qualitatively matched in synthetic experiments on expander graphs.

Algorithmic Game Theory

Item Pricing for Revenue Maximization. With Avrim Blum and Yishay Mansour. ACM Conference on Electronic Commerce, 2008. A preliminary version appeared in the Dagstuhl Workshop on Computational Social Systems and the Internet 2007. [view abstract]
Presents two main results on revenue maximization in combinatorial auctions. (1) for the case of unlimited supply, the random single price auction achieves a logarithmic approximation for bidders with general valuation functions (not just single-minded or unit-demand as was previously known). (2) for the case of limited supply, subadditive valuation functions, such a mechanism (with bidders arriving in an arbitrary order) achieves an exp(sqrt(log(n)loglog(n))) approximation, with a near-matching lower bound.

Reducing Mechanism Design to Algorithm Design via Machine Learning. With Avrim Blum, Jason D. Hartline, and Yishay Mansour. Journal of Computer and System Sciences 2007, special issue on Learning Theory (invited). [view abstract]
In this work, we make an explicit connection between machine learning and mechanism design. In doing so, we obtain a unified approach for considering a variety of profit maximizing mechanism design problems, including many that have been previously considered in the literature. In particular, we use techniques from Sample Complexity in machine learning theory to reduce problems of incentive compatible mechanism design to standard algorithmic questions. We apply these results to a wide variety of revenue maximizing pricing problems, including the problem of auctioning a digital good, the attribute auction problem, and the problem of item pricing in unlimited supply combinatorial auctions. It is worth noting that from a learning perspective, these settings present several unique challenges: the loss function is discontinuous and asymmetric, and the range of bidders' valuations may be large.

Mechansim Design, Machine Learning, and Pricing Problems. With Avrim Blum. SIGecom Exchanges 2007, special issue on Combinatorial Auctions (invited). [view abstract]
Short survey article on machine learning techniques for mechanism design.

Approximation Algorithms and Online Mechanisms for Item Pricing. With Avrim Blum. Theory of Computing 2007. An extended abstract appears in ACM Conference on Electronic Commerce, 2006 [view abstract]
We present approximation and online algorithms for a number of problems of pricing items to consumers so as to maximize seller's revenue in an unlimited supply setting. Our main result is an O(k)-approximation for pricing items to single-minded bidders who each want at most k items. This improves over recent independent work of Briest and Krysta, 2006 who achieve an O(k²) bound. We also show how our algorithms can be applied to the online setting, in which customers arrive over time and must be presented with prices that depend only on information gained from customers seen in the past

A Theory of Loss-leaders: Making Money by Pricing below Cost. With Avrim Blum, Hubert Chan, and MohammadTaghi Hajiaghayi. WINE 2007. Also available as Technical Report, CMU-CS-07-143. [view abstract]
We consider the problem of assigning prices to goods of fixed marginal cost in such a way as to maximize revenue in the presence of single-minded customers. We focus in particular on the question of how pricing certain items below their marginal costs can lead to an improvement in overall profit, even when customers behave in a fully rational manner. We develop two frameworks for analyzing this issue that we call the rebate and coupon models, and examine both fundamental profitability gaps (to what extent can pricing below cost help to improve profit) as well as algorithms for pricing in these models in a number of settings.

Random Sampling Auctions for Limited Supply. With Nikhil Devanur, Jason D. Hartline, and Kunal Talwar. Technical Report, CMU-CS-07-154.

Computer Vision

Person Identification in Webcam Images: An Application of Semi-Supervised Learning. With Avrim Blum, Pakyan Choi, John Lafferty, Brian Pantano, Mugizi Rwebangira, and Xiaojin Zhu. ICML 2005 Workshop on Learning with Partially Classified Training Data.

Handwritten Text Localization in Skewed Documents. With Ergina Kavallieratou, Doru Balcan, and Nikos Fakotakis. International Conference on Image Processing (ICIP) 2001. [view abstract]
In this paper we present a system for handwritten text localization in document images. Our system performs skew angle correction using Wigner-Ville transform and localizes the handwritten areas in documents based on several measures concerning regularity in shape and in dimensions.

An Adaptive Resonance Theory (ART) Based Approach to Handwritten/ Machine-Printed Text Discrimination. With Doru Balcan. ICC&IE 2001.

Books

Search and Knowledge Representation in Artificial Intelligence. Theory and Applications. With Florentina Hristea. University of Bucharest Publishing House, 2005 (in Romanian).