CS 59000 Statistical Machine learningLecture 18Yuan (Alan) QiPurdue CSOutline• Review of Gaussian Process Classification• Support Vector Machines for Linearly Separable Case• Support Vector Machines for Overlapping Class DistributionsGaussian Processes for ClassificationLikelihood:GP Prior:Covariance function:Predictive DistributionNo analytical solution.Approximate this integration:Laplace’s methodVariational BayesExpectation propagationLaplace’s method for GP Classification (1)Laplace’s method for GP Classification (2)Taylor expansion:Laplace’s method for GP Classification (3)Gaussian approximation:Support Vector MachinesSupport Vector Machines: motivated by statistical learning theory.Maximum margin classifiersMargin: the smallest distance between the decision boundary and any of the samplesMaximizing Margin Since scaling w and b together will not change the above ratio, we setIn the case of data points for which the equality holds, the constraints are said to be active, whereas for the remainder they are said to be inactive.Optimization ProblemQuadratic programming:Subject toLagrange MultiplierMaximizeSubject toGradient of constraint:Geometrical Illustration of Lagrange MultiplierLagrange Multiplier with Inequality ConstraintsActive and Inactive constraintsInactive constraint:The constraint plays no role in optimizationand so the stationary condition isEquivalently, we haveActive constraint:The sign of the Lagrange multiplier is positivewhy?Lagrange Multiplier with Inequality ConstraintsKarush-Kuhn-Tucker (KKT) conditionLagrange Function for SVMQuadratic programming:Subject to Lagrange function:Dual VariablesSetting derivatives of L with respect to w and b to zero:Dual ProblemMaximizePredictionKKT Condition, Support Vectors, and BiasThe corresponding data points in the latter case are known as support vectors. Then we can solve the bias term as follows:Computational ComplexityQuadratic programming:When Dimension < Number of data points, Solving the Dual problem is more costly.Dual representation allows the use of kernelsExample: SVM ClassificationClassification for Overlapping ClassesSoft Margin:New Cost FunctionTo maximize margin and softly penalize points that lies on the wrong side of margin (not decision) boundary, we
View Full Document
Unlocking...