We describe a joint probabilistic model for modeling the contents and inter-connectivity of document collections such as sets of web pages or research paper archives. The model is based on a probabilistic factor decomposition and allows identifying principal topics of the collection as well as authoritative documents within those topics. Furthermore, the relationships between topics is mapped out in order to build a predictive model of link content. Among the many applications of this approach are information retrieval and search, topic identification, query disambigua(cid:173) tion, focused web crawling, web authoring, and bibliometric analysis.

For many types of machine learning algorithms, one can compute the statistically `optimal' way to select training data. In this paper, we review how optimal data selection techniques have been used with feedforward neural networks. We then show how the same principles may be used to select data for two alternative, statistically-based learning architectures: mixtures of Gaussians and locally weighted regression. While the techniques for neural networks are computationally expensive and approximate, the techniques for mixtures of Gaussians and locally weighted regression are both efficient and accurate. Empirically, we observe that the optimality criterion sharply decreases the number of training examples the learner needs in order to achieve good performance.

For many types of learners one can compute the statistically "op(cid:173) timal" way to select data. We review how these techniques have been used with feedforward neural networks [MacKay, 1992; Cohn, 1994] . We then show how the same principles may be used to select data for two alternative, statistically-based learning architectures: mixtures of Gaussians and locally weighted regression. While the techniques for neural networks are expensive and approximate, the techniques for mixtures of Gaussians and locally weighted regres(cid:173) sion are both efficient and accurate. 1 ACTIVE LEARNING - BACKGROUND An active learning problem is one where the learner has the ability or need to influence or select its own training data. Many problems of great practical interest allow active learning, and many even require it. We consider the problem of actively learning a mapping X - Y based on a set of training examples {(Xi,Yi)}~l' where Xi E X and Yi E Y. The learner is allowed to iteratively select new inputs x (possibly from a constrained set), observe the resulting output y, and incorporate the new examples (x, y) into its training set. The primary question of active learning is how to choose which x to try next. There are many heuristics for choosing x based on intuition, including choosing places where we don't have data, where we perform poorly [Linden and Weber, 1993], where we have low confidence [Thrun and Moller, 1992], where we expect it 706 David Cohn, Zoubin Ghahramani, Michael I. Jordon to change our model [Cohn et aI, 1990], and where we previously found data that resulted in learning [Schmidhuber and Storck, 1993]. In this paper we consider how one may select x "optimally" from a statistical viewpoint. We first review how the statistical approach can be applied to neural networks, as described in MacKay [1992] and Cohn [1994]. We then consider two alternative, statistically-based learning architectures: mixtures of Gaussians and locally weighted regression. While optimal data selection for a neural network is computationally expensive and approximate, we find that optimal data selection for the two statistical models is efficient and accurate. 2 ACTIVE LEARNING - A STATISTICAL APPROACH We denote the learner's output given input x as y(x). The mean squared error of this output can be expressed as the sum of the learner's bias and variance. The variance 0'3 (x) indicates the learner's uncertainty in its estimate at x. 1 Our goal will be to select a new example x such that when the resulting example (x, y) is added to the training set, the integrated variance IV is minimized: IV = J 0'3 P (x)dx. (1) Here, P(x) is the (known) distribution over X. In practice, we will compute a Monte Carlo approximation of this integral, evaluating 0'3 at a number of random points drawn according to P(x). Selecting x so as to minimize IV requires computing 0-3, the new variance at x given (x, y). Until we actually commit to an x, we do not know what corresponding y we will see, so the minimization cannot be performed deterministically.2 Many learning architectures, however, provide an estimate of PWlx) based on current data, so we can use this estimate to compute the expectation of 0-3. Selecting x to minimize the expected integrated variance provides a solid statistical basis for choosing new examples. 2.1 EXAMPLE: ACTIVE LEARNING WITH A NEURAL

Examines how the performance of a memoryless vector quantizer changes as a function of its training set size. Specifically, the authors study how well the training set distortion predicts test distortion when the training set is a randomly drawn subset of blocks from the test or training image(s). Using the Vapnik-Chervonenkis (VC) dimension, the authors derive formal bounds for the difference of test and training distortion of vector quantizer codebooks. The authors then describe extensive empirical simulations that test these bounds for a variety of codebook sizes and vector dimensions, and give practical suggestions for determining the training set size necessary to achieve good generalization from a codebook. The authors conclude that, by using training sets comprising only a small fraction of the available data, one can produce results that are close to the results obtainable when all available data are used.>

We describe a series of numerical experiments that measure the average generalization capability of neural networks trained on a variety of simple functions. These experiments are designed to test the relationship between average generalization performance and the worst-case bounds obtained from formal learning theory using the Vapnik-Chervonenkis (VC) dimension (Blumer et al. 1989; Haussler et al. 1990). Recent statistical learning theories (Tishby et al. 1989; Schwartz et al. 1990) suggest that surpassing these bounds might be possible if the spectrum of possible generalizations has a “gap” near perfect performance. We indeed find that, in some cases, the average generalization is significantly better than the VC bound: the approach to perfect performance is exponential in the number of examples m, rather than the 1/m result of the bound. However, in these cases, we have not found evidence of the gap predicted by the above statistical theories. In other cases, we do find the 1/m behavior of the VC bound, and in these cases, the numerical prefactor is closely related to the prefactor contained in the bound.