Bishop C.M. Pattern Recognition and Machine Learning (2006) (811375), страница 80

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 80)

This still considers any possible choice for p(x, t), and so although the bounds are tighter, theyare still very conservative.7.2. Relevance Vector MachinesSupport vector machines have been used in a variety of classification and regression applications. Nevertheless, they suffer from a number of limitations, severalof which have been highlighted already in this chapter. In particular, the outputs ofan SVM represent decisions rather than posterior probabilities.

Also, the SVM wasoriginally formulated for two classes, and the extension to K > 2 classes is problematic. There is a complexity parameter C, or ν (as well as a parameter in the caseof regression), that must be found using a hold-out method such as cross-validation.Finally, predictions are expressed as linear combinations of kernel functions that arecentred on training data points and that are required to be positive definite.The relevance vector machine or RVM (Tipping, 2001) is a Bayesian sparse kernel technique for regression and classification that shares many of the characteristicsof the SVM whilst avoiding its principal limitations.

Additionally, it typically leadsto much sparser models resulting in correspondingly faster performance on test datawhilst maintaining comparable generalization error.In contrast to the SVM we shall find it more convenient to introduce the regression form of the RVM first and then consider the extension to classification tasks.7.2.1 RVM for regressionThe relevance vector machine for regression is a linear model of the form studiedin Chapter 3 but with a modified prior that results in sparse solutions.

The modeldefines a conditional distribution for a real-valued target variable t, given an inputvector x, which takes the formp(t|x, w, β) = N (t|y(x), β −1 )(7.76)3467. SPARSE KERNEL MACHINESwhere β = σ −2 is the noise precision (inverse noise variance), and the mean is givenby a linear model of the formy(x) =Mwi φi (x) = wT φ(x)(7.77)i=1with fixed nonlinear basis functions φi (x), which will typically include a constantterm so that the corresponding weight parameter represents a ‘bias’.The relevance vector machine is a specific instance of this model, which is intended to mirror the structure of the support vector machine.

In particular, the basisfunctions are given by kernels, with one kernel associated with each of the datapoints from the training set. The general expression (7.77) then takes the SVM-likeformNy(x) =wn k(x, xn ) + b(7.78)n=1where b is a bias parameter. The number of parameters in this case is M = N + 1,and y(x) has the same form as the predictive model (7.64) for the SVM, except thatthe coefficients an are here denoted wn . It should be emphasized that the subsequentanalysis is valid for arbitrary choices of basis function, and for generality we shallwork with the form (7.77). In contrast to the SVM, there is no restriction to positivedefinite kernels, nor are the basis functions tied in either number or location to thetraining data points.Suppose we are given a set of N observations of the input vector x, which wedenote collectively by a data matrix X whose nth row is xTn with n = 1, .

. . , N . Thecorresponding target values are given by t = (t1 , . . . , tN )T . Thus, the likelihoodfunction is given byp(t|X, w, β) =Np(tn |xn , w, β −1 ).(7.79)n=1Next we introduce a prior distribution over the parameter vector w and as inChapter 3, we shall consider a zero-mean Gaussian prior. However, the key difference in the RVM is that we introduce a separate hyperparameter αi for each of theweight parameters wi instead of a single shared hyperparameter. Thus the weightprior takes the formMN (wi |0, αi−1 )(7.80)p(w|α) =i=1where αi represents the precision of the corresponding parameter wi , and α denotes(α1 , .

. . , αM )T . We shall see that, when we maximize the evidence with respectto these hyperparameters, a significant proportion of them go to infinity, and thecorresponding weight parameters have posterior distributions that are concentratedat zero. The basis functions associated with these parameters therefore play no role7.2. Relevance Vector Machines347in the predictions made by the model and so are effectively pruned out, resulting ina sparse model.Using the result (3.49) for linear regression models, we see that the posteriordistribution for the weights is again Gaussian and takes the formp(w|t, X, α, β) = N (w|m, Σ)(7.81)where the mean and covariance are given bym = βΣΦT t−1Σ = A + βΦT ΦSection 3.5Exercise 7.10(7.82)(7.83)where Φ is the N × M design matrix with elements Φni = φi (xn ), and A =diag(αi ).

Note that in the specific case of the model (7.78), we have Φ = K, whereK is the symmetric (N + 1) × (N + 1) kernel matrix with elements k(xn , xm ).The values of α and β are determined using type-2 maximum likelihood, alsoknown as the evidence approximation, in which we maximize the marginal likelihood function obtained by integrating out the weight parameters(7.84)p(t|X, α, β) = p(t|X, w, β)p(w|α) dw.Because this represents the convolution of two Gaussians, it is readily evaluated togive the log marginal likelihood in the formln p(t|X, α, β) = ln N (t|0, C)1N ln(2π) + ln |C| + tT C−1 t= −2(7.85)where t = (t1 , .

. . , tN )T , and we have defined the N × N matrix C given byC = β −1 I + ΦA−1 ΦT .Exercise 7.12Section 3.5.3(7.86)Our goal is now to maximize (7.85) with respect to the hyperparameters α andβ. This requires only a small modification to the results obtained in Section 3.5 forthe evidence approximation in the linear regression model. Again, we can identifytwo approaches. In the first, we simply set the required derivatives of the marginallikelihood to zero and obtain the following re-estimation equationsαinew=(β new )−1=γim2it − Φm2N − i γi(7.87)(7.88)where mi is the ith component of the posterior mean m defined by (7.82).

Thequantity γi measures how well the corresponding parameter wi is determined by thedata and is defined by3487. SPARSE KERNEL MACHINESγi = 1 − αi Σii(7.89)in which Σii is the i diagonal component of the posterior covariance Σ given by(7.83). Learning therefore proceeds by choosing initial values for α and β, evaluating the mean and covariance of the posterior using (7.82) and (7.83), respectively,and then alternately re-estimating the hyperparameters, using (7.87) and (7.88), andre-estimating the posterior mean and covariance, using (7.82) and (7.83), until a suitable convergence criterion is satisfied.The second approach is to use the EM algorithm, and is discussed in Section 9.3.4.

These two approaches to finding the values of the hyperparameters thatmaximize the evidence are formally equivalent. Numerically, however, it is foundthat the direct optimization approach corresponding to (7.87) and (7.88) gives somewhat faster convergence (Tipping, 2001).As a result of the optimization, we find that a proportion of the hyperparameters{αi } are driven to large (in principle infinite) values, and so the weight parameterswi corresponding to these hyperparameters have posterior distributions with meanand variance both zero. Thus those parameters, and the corresponding basis functions φi (x), are removed from the model and play no role in making predictions fornew inputs.

In the case of models of the form (7.78), the inputs xn corresponding tothe remaining nonzero weights are called relevance vectors, because they are identified through the mechanism of automatic relevance determination, and are analogous to the support vectors of an SVM. It is worth emphasizing, however, that thismechanism for achieving sparsity in probabilistic models through automatic relevance determination is quite general and can be applied to any model expressed asan adaptive linear combination of basis functions.Having found values α and β for the hyperparameters that maximize themarginal likelihood, we can evaluate the predictive distribution over t for a newinput x.

Using (7.76) and (7.81), this is given byp(t|x, w, β )p(w|X, t, α , β ) dwp(t|x, X, t, α , β ) == N t|mT φ(x), σ 2 (x) .(7.90)thExercise 9.23Section 7.2.2Exercise 7.14Thus the predictive mean is given by (7.76) with w set equal to the posterior meanm, and the variance of the predictive distribution is given byσ 2 (x) = (β )−1 + φ(x)T Σφ(x)Section 6.4.2(7.91)where Σ is given by (7.83) in which α and β are set to their optimized values α andβ .

This is just the familiar result (3.59) obtained in the context of linear regression.Recall that for localized basis functions, the predictive variance for linear regressionmodels becomes small in regions of input space where there are no basis functions.In the case of an RVM with the basis functions centred on data points, the model willtherefore become increasingly certain of its predictions when extrapolating outsidethe domain of the data (Rasmussen and Quiñonero-Candela, 2005), which of courseis undesirable.

The predictive distribution in Gaussian process regression does not3497.2. Relevance Vector MachinesFigure 7.9Illustration of RVM regression using the same data set, and thesame Gaussian kernel functions,as used in Figure 7.8 for theν-SVM regression model. Themean of the predictive distribution for the RVM is shown by thered line, and the one standarddeviation predictive distribution isshown by the shaded region.Also, the data points are shownin green, and the relevance vectors are indicated by blue circles.Note that there are only 3 relevance vectors compared to 7 support vectors for the ν-SVM in Figure 7.8.1t0−10x1suffer from this problem.

However, the computational cost of making predictionswith a Gaussian processes is typically much higher than with an RVM.Figure 7.9 shows an example of the RVM applied to the sinusoidal regressiondata set. Here the noise precision parameter β is also determined through evidencemaximization. We see that the number of relevance vectors in the RVM is significantly smaller than the number of support vectors used by the SVM. For a widerange of regression and classification tasks, the RVM is found to give models thatare typically an order of magnitude more compact than the corresponding supportvector machine, resulting in a significant improvement in the speed of processing ontest data. Remarkably, this greater sparsity is achieved with little or no reduction ingeneralization error compared with the corresponding SVM.The principal disadvantage of the RVM compared to the SVM is that traininginvolves optimizing a nonconvex function, and training times can be longer than for acomparable SVM.

For a model with M basis functions, the RVM requires inversionof a matrix of size M × M , which in general requires O(M 3 ) computation. In thespecific case of the SVM-like model (7.78), we have M = N +1. As we have noted,there are techniques for training SVMs whose cost is roughly quadratic in N .

Характеристики

Список файлов книги