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

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

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

The model now takes the form of alinear combination of basis functions transformed by a logistic sigmoid functiony(x, w) = σ wT φ(x)(7.108)3547. SPARSE KERNEL MACHINESSection 4.4where σ(·) is the logistic sigmoid function defined by (4.59). If we introduce aGaussian prior over the weight vector w, then we obtain the model that has beenconsidered already in Chapter 4. The difference here is that in the RVM, this modeluses the ARD prior (7.80) in which there is a separate precision hyperparameterassociated with each weight parameter.In contrast to the regression model, we can no longer integrate analytically overthe parameter vector w.

Here we follow Tipping (2001) and use the Laplace approximation, which was applied to the closely related problem of Bayesian logisticregression in Section 4.5.1.We begin by initializing the hyperparameter vector α. For this given value ofα, we then build a Gaussian approximation to the posterior distribution and therebyobtain an approximation to the marginal likelihood. Maximization of this approximate marginal likelihood then leads to a re-estimated value for α, and the process isrepeated until convergence.Let us consider the Laplace approximation for this model in more detail. Fora fixed value of α, the mode of the posterior distribution over w is obtained bymaximizingln p(w|t, α) = ln {p(t|w)p(w|α)} − ln p(t|α)=Nn=1Exercise 7.181{tn ln yn + (1 − tn ) ln(1 − yn )} − wT Aw + const (7.109)2where A = diag(αi ).

This can be done using iterative reweighted least squares(IRLS) as discussed in Section 4.3.3. For this, we need the gradient vector andHessian matrix of the log posterior distribution, which from (7.109) are given by∇ ln p(w|t, α) = ΦT (t − y) − Aw∇∇ ln p(w|t, α) = − ΦT BΦ + A(7.110)(7.111)where B is an N × N diagonal matrix with elements bn = yn (1 − yn ), the vectory = (y1 , . . . , yN )T , and Φ is the design matrix with elements Φni = φi (xn ). Herewe have used the property (4.88) for the derivative of the logistic sigmoid function.At convergence of the IRLS algorithm, the negative Hessian represents the inversecovariance matrix for the Gaussian approximation to the posterior distribution.The mode of the resulting approximation to the posterior distribution, corresponding to the mean of the Gaussian approximation, is obtained setting (7.110) tozero, giving the mean and covariance of the Laplace approximation in the formw = A−1 ΦT (t − y)−1Σ = ΦT BΦ + A.(7.112)(7.113)We can now use this Laplace approximation to evaluate the marginal likelihood.Using the general result (4.135) for an integral evaluated using the Laplace approxi-7.2.

Relevance Vector Machinesmation, we havep(t|α) =p(t|w)p(w|α) dw p(t|w )p(w |α)(2π)M/2 |Σ|1/2 .Exercise 7.19355(7.114)If we substitute for p(t|w ) and p(w |α) and then set the derivative of the marginallikelihood with respect to αi equal to zero, we obtain111− Σii = 0.− (wi )2 +22αi 2(7.115)Defining γi = 1 − αi Σii and rearranging then givesαinew =γi(wi )2(7.116)which is identical to the re-estimation formula (7.87) obtained for the regressionRVM.If we definet = Φw + B−1 (t − y)(7.117)we can write the approximate log marginal likelihood in the form1N ln(2π) + ln |C| + (t)T C−1tln p(t|α, β) = −2whereAppendix ASection 13.3C = B + ΦAΦT .(7.118)(7.119)This takes the same form as (7.85) in the regression case, and so we can apply thesame analysis of sparsity and obtain the same fast learning algorithm in which wefully optimize a single hyperparameter αi at each step.Figure 7.12 shows the relevance vector machine applied to a synthetic classification data set.

We see that the relevance vectors tend not to lie in the region of thedecision boundary, in contrast to the support vector machine. This is consistent withour earlier discussion of sparsity in the RVM, because a basis function φi (x) centredon a data point near the boundary will have a vector ϕi that is poorly aligned withthe training data vector t.One of the potential advantages of the relevance vector machine compared withthe SVM is that it makes probabilistic predictions. For example, this allows the RVMto be used to help construct an emission density in a nonlinear extension of the lineardynamical system for tracking faces in video sequences (Williams et al., 2005).So far, we have considered the RVM for binary classification problems.

ForK > 2 classes, we again make use of the probabilistic approach in Section 4.3.4 inwhich there are K linear models of the formak = wkT x(7.120)3567. SPARSE KERNEL MACHINES20−2−202Figure 7.12 Example of the relevance vector machine applied to a synthetic data set, in which the left-hand plotshows the decision boundary and the data points, with the relevance vectors indicated by circles. Comparisonwith the results shown in Figure 7.4 for the corresponding support vector machine shows that the RVM gives amuch sparser model. The right-hand plot shows the posterior probability given by the RVM output in which theproportion of red (blue) ink indicates the probability of that point belonging to the red (blue) class.which are combined using a softmax function to give outputsexp(ak )yk (x) = .exp(aj )(7.121)jThe log likelihood function is then given byln p(T|w1 , .

. . , wK ) =N Kn=1 k=1tnkynk(7.122)where the target values tnk have a 1-of-K coding for each data point n, and T is amatrix with elements tnk . Again, the Laplace approximation can be used to optimizethe hyperparameters (Tipping, 2001), in which the model and its Hessian are foundusing IRLS.

This gives a more principled approach to multiclass classification thanthe pairwise method used in the support vector machine and also provides probabilistic predictions for new data points. The principal disadvantage is that the Hessianmatrix has size M K ×M K, where M is the number of active basis functions, whichgives an additional factor of K 3 in the computational cost of training compared withthe two-class RVM.The principal disadvantage of the relevance vector machine is the relatively longtraining times compared with the SVM. This is offset, however, by the avoidance ofcross-validation runs to set the model complexity parameters.

Furthermore, becauseit yields sparser models, the computation time on test points, which is usually themore important consideration in practice, is typically much less.357ExercisesExercises7.1 ( ) www Suppose we have a data set of input vectors {xn } with correspondingtarget values tn ∈ {−1, 1}, and suppose that we model the density of input vectors within each class separately using a Parzen kernel density estimator (see Section 2.5.1) with a kernel k(x, x ).

Write down the minimum misclassification-ratedecision rule assuming the two classes have equal prior probability. Show also that,if the kernel is chosen to be k(x, x ) = xT x , then the classification rule reduces tosimply assigning a new input vector to the class having the closest mean. Finally,show that, if the kernel takes the form k(x, x ) = φ(x)T φ(x ), that the classificationis based on the closest mean in the feature space φ(x).7.2 () Show that, if the 1 on the right-hand side of the constraint (7.5) is replaced bysome arbitrary constant γ > 0, the solution for the maximum margin hyperplane isunchanged.7.3 ( ) Show that, irrespective of the dimensionality of the data space, a data setconsisting of just two data points, one from each class, is sufficient to determine thelocation of the maximum-margin hyperplane.7.4 ( ) www Show that the value ρ of the margin for the maximum-margin hyperplane is given by1=anρ2N(7.123)n=1where {an } are given by maximizing (7.10) subject to the constraints (7.11) and(7.12).7.5 ( ) Show that the values of ρ and {an } in the previous exercise also satisfy1= 2L(a)ρ2(7.124)is defined by (7.10).

Similarly, show thatwhere L(a)1= w2 .ρ2(7.125)7.6 () Consider the logistic regression model with a target variable t ∈ {−1, 1}. Ifwe define p(t = 1|y) = σ(y) where y(x) is given by (7.1), show that the negativelog likelihood, with the addition of a quadratic regularization term, takes the form(7.47).7.7 () Consider the Lagrangian (7.56) for the regression support vector machine. Bysetting the derivatives of the Lagrangian with respect to w, b, ξn , and ξn to zero andthen back substituting to eliminate the corresponding variables, show that the dualLagrangian is given by (7.61).3587.

SPARSE KERNEL MACHINES7.8 () www For the regression support vector machine considered in Section 7.1.4,show that all training data points for which ξn > 0 will have an = C, and similarlyall points for which ξn > 0 will have an = C.7.9 () Verify the results (7.82) and (7.83) for the mean and covariance of the posteriordistribution over weights in the regression RVM.7.10 ( ) www Derive the result (7.85) for the marginal likelihood function in theregression RVM, by performing the Gaussian integral over w in (7.84) using thetechnique of completing the square in the exponential.7.11 ( ) Repeat the above exercise, but this time make use of the general result (2.115).7.12 ( ) www Show that direct maximization of the log marginal likelihood (7.85) forthe regression relevance vector machine leads to the re-estimation equations (7.87)and (7.88) where γi is defined by (7.89).7.13 ( ) In the evidence framework for RVM regression, we obtained the re-estimationformulae (7.87) and (7.88) by maximizing the marginal likelihood given by (7.85).Extend this approach by inclusion of hyperpriors given by gamma distributions ofthe form (B.26) and obtain the corresponding re-estimation formulae for α and β bymaximizing the corresponding posterior probability p(t, α, β|X) with respect to αand β.7.14 ( ) Derive the result (7.90) for the predictive distribution in the relevance vectormachine for regression.

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

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