Predicting ad click-through rates (CTR) is a massive-scale learning problem that is central to the multi-billion dollar online advertising industry. We present a selection of case studies and topics drawn from recent experiments in the setting of a deployed CTR prediction system. These include improvements in the context of traditional supervised learning based on an FTRL-Proximal online learning algorithm (which has excellent sparsity and convergence properties) and the use of per-coordinate learning rates.

In this paper we examine the problem of efficient feature evaluation for logistic regression on very large data sets. We present a new forward feature selection heuristic that ranks features by their estimated effect on the resulting model's performance. An approximate optimization, based on backfitting, provides a fast and accurate estimate of each new feature's coefficient in the logistic regression model. Further, the algorithm is highly scalable by parallelizing simultaneously over both features and records, allowing us to quickly evaluate billions of potential features even for very large data sets.

In this paper we examine the problem of efficiently finding sets of observations that conform to a given underlying motion model. While this problem is often phrased as a tracking problem, where it is called track initiation, it is useful in a variety of tasks where we want to find correspondences or patterns in spatial-temporal data. Unfortunately, this problem often suffers from a combinatorial explosion in the number of potential sets that must be evaluated. We consider the problem with respect to large-scale asteroid observation data, where the goal is to find associations among the observations that correspond to the same underlying asteroid. In this domain, it is vital that we can efficiently extract the underlying associations. We introduce a new methodology for track initiation that exhaustively considers all possible linkages. We then introduce an exact tree-based algorithm for tractably finding all compatible sets of points. Further, we extend this approach to use multiple trees, exploiting structure from several time steps at once. We compare this approach to a standard sequential approach and show how the use of multiple trees can provide a significant benefit.

In this paper we consider the problem of finding sets of points that conform to a given underlying model from within a dense, noisy set of observations. This problem is motivated by the task of efficiently linking faint asteroid detections, but is applicable to a range of spatial queries. We survey current tree-based approaches, showing a trade-off exists between single tree and multiple tree algorithms. To this end, we present a new type of multiple tree algorithm that uses a variable number of trees to exploit the advantages of both approaches. We empirically show that this algorithm performs well using both simulated and astronomical data.

Real world data is never as perfect as we would like it to be and can often suffer from corruptions that may impact interpretations of the data, models created from the data, and decisions made based on the data. One approach to this problem is to identify and remove records that contain corruptions. Unfortunately, if only certain fields in a record have been corrupted then usable, uncorrupted data will be lost. We present LENS, an approach for identifying corrupted fields and using the remaining noncorrupted fields for subsequent modeling and analysis. Our approach uses the data to learn a probabilistic model containing three components: a generative model of the clean records, a generative model of the noise values, and a probabilistic model of the corruption process. We provide an algorithm for the unsupervised discovery of such models and empirically evaluate both its performance at detecting corrupted fields and, as one example application, the resulting improvement this gives to a classifier.

Discovering underlying structure from co-occurrence data is an important task in a variety of fields, including: insurance, intelligence, criminal investigation, epidemiology, human resources, and marketing. Previously Kubica et al. presented the group detection algorithm (GDA) - an algorithm for finding underlying groupings of entities from co-occurrence data. This algorithm is based on a probabilistic generative model and produces coherent groups that are consistent with prior knowledge. Unfortunately, the optimization used in GDA is slow, potentially making it infeasible for many large data sets. To this end, we present k-groups - an algorithm that uses an approach similar to that of k-means to significantly accelerate the discovery of groups while retaining GDA's probabilistic model. We compare the performance of GDA and k-groups on a variety of data, showing that k-groups' sacrifice in solution quality is significantly offset by its increase in speed.

This work extends previous research on developing control software for modular robotic smart membranes to a second module type with more complicated movement, to 3-D membranes, to the presence of gravity, and to less easily manipulatable objects. Moreover, it extends the capabilities of the membranes from simple filtering to more complex sorting tasks. The control software we developed is completely decentralized, and automatically generated.

We discuss the theoretical limitations for reconfiguration of metamorphic robots made up of Telecubes, six degree of freedom cube shaped modules currently being developed at Xerox PARC. We show that by using meta-modules composed of 8 individual modules as a backbone for building the desired shape, we can establish completeness for the reconfiguration as well as time and space bounds for the process. Finally we present several open problems in the field of reconfiguration.

We demonstrate how simple local rules, inspired by social insects, produce complex dynamic behaviors required for locomotion and navigation in modular self-reconfigurable robots. We show how systems made up of many modules respond dynamically to their environment, such as obstacles during navigation. We present control algorithms tested on simulation experiments of TeleCube, a new modular robot developed at Xerox PARC.