We establish the theoretical foundation for statistically efficient variants of the Greedy Equivalence Search algorithm. If each node in the generative structure has at most $k$ parents, we show that in the limit of large data, we can recover that structure using greedy search with operator scores that condition on at most $k$ variables. We present simple synthetic experiments that compare a backward-only variantof the new algorithm to GES using finite data, showing increasing benefit of the new algorithm as the complexity of the generative model increases.

Software applications often use classification models to trigger specialized experiences for users. Search engines, for example, use query classifiers to trigger specialized "instant answer" experiences where information satisfying the user query is shown directly on the result page, and email applications use classification models to automatically move messages to a spam folder. When such applications have acceptable default (i.e., non-specialized) behavior, users are often more sensitive to failures in model precision than failures in model recall. In this paper, we consider model-selection algorithms for these precision-constrained scenarios. We develop adaptive model-selection algorithms to identify, using as few samples as possible, the best classifier from among a set of (precision) qualifying classifiers. We provide statistical correctness and sample complexity guarantees for our algorithms. We show with an empirical validation that our algorithms work well in practice.

Model building in machine learning is an iterative process. The performance analysis and debugging step typically involves a disruptive cognitive switch from model building to error analysis, discouraging an informed approach to model building. We present ModelTracker, an interactive visualization that subsumes information contained in numerous traditional summary statistics and graphs while displaying example-level performance and enabling direct error examination and debugging. Usage analysis from machine learning practitioners building real models with ModelTracker over six months shows ModelTracker is used often and throughout model building. A controlled experiment focusing on ModelTracker's debugging capabilities shows participants prefer ModelTracker over traditional tools without a loss in model performance.

In Internet ad auctions, search engines often throttle budget constrained advertisers so as to spread their spends across the specified time period. Such policies are known as budget smoothing policies. In this paper, we perform a principled, game-theoretic study of what the outcome of an ideal budget smoothing algorithm should be. In particular, we propose the notion of regret-free budget smoothing policies whose outcomes throttle each advertiser optimally, given the participation of the other advertisers. We show that regret-free budget smoothing policies always exist, and in the case of single slot auctions we can give a polynomial time smoothing algorithm. Inspired by the existence proof, we design a heuristic for budget smoothing which performs considerably better than existing benchmark heuristics.

As users of social networking websites expand their network of friends, they are often flooded with newsfeed posts and status updates, most of which they consider to be "unimportant" and not newsworthy. In order to better understand how people judge the importance of their newsfeed, we conducted a study in which Facebook users were asked to rate the importance of their newsfeed posts as well as their friends. We learned classifiers of newsfeed and friend importance to identify predictive sets of features related to social media properties, the message text, and shared background information. For classifying friend importance, the best performing model achieved 85% accuracy and 25% error reduction. By leveraging this model for classifying newsfeed posts, the best newsfeed classifier achieved 64% accuracy and 27% error reduction.

We derive efficient algorithms for both detecting and representing matchings in lopsided bipartite graphs; such graphs have so many nodes on one side that it is infeasible to represent them in memory or to identify matchings using standard approaches. Detecting and representing matchings in lopsided bipartite graphs is important for allocating and delivering guaranteed-placement display ads, where the corresponding bipartite graph of interest has nodes representing advertisers on one side and nodes representing web-page impressions on the other; real-world instances of such graphs can have billions of impression nodes. We provide theoretical guarantees for our algorithms, and in a real-world advertising application, we demonstrate the feasibility of our detection algorithms.

In this paper we take the problem of a market-based P2P backup application and carry it through market design, to implementation, to theoretical and experimental analysis. While the long-term goal is an open market using real money, here we consider a system where monetary transfers are prohibited. We first describe the design of the P2P resource exchange market and the UI we developed. Second, we prove theorems on equilibrium existence and uniqueness. Third, we prove a surprising impossibility result regarding the limited controllability of the equilibrium and show how to address this. Fourth, we present a price update algorithm that uses daily supply and demand information to move prices towards the equilibrium and we provide a theoretical and experimental convergence analysis. The market design described in this paper is already implemented as part of a Microsoft research project on P2P backup systems and an alpha version of the software has been successfully tested.

We consider the problem of identifying the consensus ranking for the results of a query, given preferences among those results from a set of individual users. Once consensus rankings are identified for a set of queries, these rankings can serve for both evaluation and training of retrieval and learning systems. We present a novel approach to collecting the individual user preferences over image-search results: we use a collaborative game in which players are rewarded for agreeing on which image result is best for a query. Our approach is distinct from other labeling games because we are able to elicit directly the preferences of interest with respect to image queries extracted from query logs. As a source of relevance judgments, this data provides a useful complement to click data. Furthermore, the data is free of positional biases and is collected by the game without the risk of frustrating users with non-relevant results; this risk is prevalent in standard mechanisms for debiasing clicks. We describe data collected over 34 days from a deployed version of this game that amounts to about 18 million expressed preferences between pairs. Finally, we present several approaches to modeling this data in order to extract the consensus rankings from the preferences and better sort the search results for targeted queries.

In this paper we study the challenges and evaluate the effectiveness of data collected from the web for recommendations. We provide experimental results, including a user study, showing that our methods produce good recommendations in realistic applications. We propose a new evaluation metric, that takes into account the difficulty of prediction. We show that the new metric aligns well with the results from a user study.

1 Introduction The analysis and modeling of time-series data is an important area of research for many communities. In this paper, our goal is to identify models for continuousvalued time-series data that are useful for data mining in that they (1) can be learned eficiently from data, (2) support accurate predictions, and (3) are easy to interpret. To these ends, we describe an interpretable class of models that we call AutoRegressive Tree models, or ART models, that are a generalization of standard autoregressive (AR) models. We describe learning methods for ART models and compare these methods to those for alternative models. Our experiments, performed on 2,494 time-series data sets from the International Institute of Forecasters, demonstrate that ART models provide superior predictive accuracy. We concentrate on the problem of modeling the evolution of values of a continuous variable over time; that is, we model a univariate time series. The generalization to multivariate time-series analysis is straightforward and is discussed in Section 6.

We consider the problem of choosing split points for continuous predictor variables in a decision tree. Previous approaches to this problem typically either: (1) discretize the continuous predictor values prior to learning, or (2) apply a dynamic method that considers all possible split points for each potential split. We describe a number of alternative approaches that generate a small number of candidate split points dynamically with little overhead. We argue that these approaches are preferable to pre-discretization, and provide experimental evidence that they yield probabilistic decision trees with the same prediction accuracy as the traditional dynamic approach. Furthermore, because the time to grow a decision tree is proportional to the number of split points evaluated, our approach is significantly faster than the traditional dynamic approach.

Companies that maintain web sites can make considerable revenue through advertising, and consequently attracting advertisers has become an important and competitive endeavor.A property that can attract advertisers is high clickthrough rates; and therefore companies can bene t from delivery systems that serve advertisements selectively to those visitors most likely to click.In order to satisfy contractual obligations, however, these systems must simultaneously perform inventory management.For example, if a company has agreed to serve a certain number of a particular advertisement, it must do so regardless of how likely it is to be clicked.In this paper, we describe how t o u s e a linear program to identify a schedule, based on known attributes of each visitor, that maximizes the expected number of clicks give n a l l o f t h e i n ventory-management constraints.We present experimental results using real data that demonstrate that a delivery schedule from our system realizes more clicks than a schedule that was hand constructed.