CS 59000 Statistical Machine learningLecture 13Yuan (Alan) QiOutline• Review of kernel trick, kernel ridge regression and kernel Principle Component Analysis• Gaussian processes (GPs)• From linear regression to GP • GP for regressionKernel Trick1. Reformulate an algorithm such that input vector enters only in the form of inner product . 2. Replace input x by its feature mapping:3. Replace the inner product by a Kernel function:Examples: Kernel PCA, Kernel Fisher discriminant, Support Vector MachinesDual variables:Dual Representation for Ridge RegressionKernel Ridge RegressionUsing kernel trick:Minimize over dual variables:QuestionGiven 100,000 2-dimenional data points, we can use the following kernel function for kernel ridge regression:Is there is a method to achieve the same result much more efficiently?Generate Kernel MatrixPositive semidefiniteConsider Gaussian kernel:Principle Component Analysis (PCA)Assume We haveis a normalized eigenvector:Feature MappingEigen-problem in feature spaceDual VariablesSuppose , we haveEigen-problem in Feature Space (1)Eigen-problem in Feature Space (2)Normalization condition:Projection coefficient:General Case for Non-zero Mean CaseKernel Matrix:Gaussian ProcessesHow kernels arise naturally in a Bayesian setting?Instead of assigning a prior on parameters w, we assign a prior on function value y.Infinite space in theoryFinite computation in practice (finite number of training set and test set)Linear Regression RevisitedLetWe haveFrom Prior on Parameter to Prior on FunctionThe prior on function value:Stochastic ProcessA stochastic process is specified by giving the joint distribution for any finite set of values in a consistent manner (Loosely speaking, it means that a marginalized distribution is the same as the joint distribution that is defined in the subspace.)Gaussian ProcessesThe joint distribution of any variables is a multivariable Gaussian distribution.Without any prior knowledge, we often set mean to be 0. Then the GP is specified by the covariance :Impact of Kernel FunctionCovariance matrix : kernel functionApplication economics & financeGaussian Process for RegressionLikelihood:Prior:Marginal distribution:Samples of GP Prior over FunctionsSamples of Data PointsPredictive Distributionis a Gaussian distribution with mean and variance:Predictive MeanWe see the same form as kernel ridge regression and kernel PCA.GP RegressionDiscussion: the difference between GP regression and Bayesian regression with Gaussian basis functions?Computational ComplexityGP prediction for a new data point:GP: O(N3) where N is number of data pointsBasis function model: O(M3) where M is the dimension of the feature expansionWhen N is large: computationally expensive.Sparsification: make prediction based on only a few basis points that summarize the information in the whole data
View Full Document
Unlocking...