Selected Publications

Computational and Statistical Machine Learning
Algorithmic Game Theory
Computer Vision
Books

Computational and Statistical Machine Learning

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

Clustering

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

• Clustering with Interactive Feedback. With Avrim Blum. Manuscript, 2008. [view abstract]
  In this paper, we consider the problem of clustering under a natural type of feedback in the form of split and merge requests. We analyze the and provide efficient algorithms as well as informationtheoretic upper and lower bounds.e learning threshold classifiers and learning homogeneous linear separators with respect to an input distribution which is uniform over the unit sphere.
  
  

Semi-Supervised Learning

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

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

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

Ranking

• Robust Reductions 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.
  
  

Algorithmic Game Theory

Algorithms for Pricing Problems

• Item Pricing for Revenue Maximization. With Avrim Blum and Yishay Mansour. ACM Conference on Electronic Commerce, 2008. [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.
  

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

Mechanism Design

• 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.
  
  
  A preliminary version of this paper appears in the Proceedings of the 46th Annual Symposium on Foundations of Computer Science (FOCS) 2005, under the title Mechanism Design via Machine Learning .
  
  A related paper on Sponsored Search Auction Design via Machine Learning appears in the Workshop on Sponsored Search Auctions, 2005.
  

• Mechanism 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.
  

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

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