Efficient active learning with generalized linear models

Active learning can significantly reduce the amount of training data required to fit parametric statistical models for supervised learning tasks. Here we present an efficient algorithm for choosing the optimal (most informative) query when the output labels are related to the inputs by a generalized linear model (GLM). The algorithm is based on a Laplace approximation of the posterior distribution of the GLM’s parameters. The algorithm requires only low-rank matrix manipulations and a single two-dimensional search to choose the optimal query and has complexity O(n) (with n the dimension of the feature space), making active learning with GLMs feasible even for high-dimensional feature spaces. In certain cases the twodimensional search may be reduced to a onedimensional search, further improving the algorithm’s efficiency. Simulation results show that the model parameters can be estimated much more efficiently using the active learning technique than by using randomly chosen queries. We compute the asymptotic posterior covariance semi-analytically and demonstrate that the algorithm empirically achieves this asymptotic convergence rate, which is generally better than the convergence rate in the random-query setting. Finally, we generalize the approach to efficiently handle both output history effects (for applications to time-series models of autoregressive type) and slow, non-systematic drifts in the model parameters. Introduction Active learning refers to the problem of selecting the optimal training set for a learning agent, given our prior knowledge and any previously observed examples. Active learning is particularly useful in settings 1) for which it is expensive to obtain labeled training examples (e.g. user ratings systems or geophysical applications), or 2) for which we have limited time to collect data (e.g. biological applications). Optimal inputs are typically selected by optimizing an objective function which quantifies the expected utility of measuring the response to a particular input. One important objective function is the expected mutual information between the response and the parameters of the model being fitted to the data (Fedorov, 1972; Mackay, 1992; Chaloner and Verdinelli, 1995). Previous work has shown that constructing a training set using this criterion is in general asymptotically more efficient and never less efficient than using a randomly constructed training set (Paninski, 2005). Active learning, however, is limited by the computational challenges of the required optimization (Cohn et al., 1996; Gilad-Bachrach et al., 2005). In particular, there are two major computational hurdles. First, the utility of each possible input depends on what has already been learned from labeled examples. Therefore, we need to be able to rapidly update the fitted model as we add new points to the training set. Second, evaluating and optimizing the mutual information over the (high-dimensional) space of unlabeled examples requires a high-dimensional integration followed by a search over the possible inputs. In general, the complexity of both the integration and optimization scales exponentially with the dimensionality. As emphasized above, many applications require that we perform these tasks in near-real time. We present methods for solving these problems using generalized linear models (GLM) for the input-output relationship and certain Gaussian approximations of the posterior distribution of the model parameters. Our emphasis is on developing techniques that scale well in high dimensions. We solve the first problem by using efficient rank-one update methods to update the Gaussian approximation to the posterior, and the second problem by a reduction to a highly tractable twodimensional optimization problem. Our results show that the resulting algorithm produces a training set which can be up to an order of magnitude more informative than the set produced by random sampling. Moreover, the algorithm is efficient enough for near real-time implementation.