classification,机器学习中分类问题的探讨.ppt

* * * * * * * * * * * * Forward pointer to feature selection; … * * * \eta smoothing parameter! Update only when a mistake is made = prevent overfitting * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * Memory requirement scale with number of datapoints * * * 16 min; 3 min question * * * * * * 25min * * * * * * * Talk about regularization? Add a lambda?? 35min * Kernel Trick Implement an infinite-dimensional mapping implicitly Only inner products explicitly needed for training and evaluation Inner products computed efficiently, in finite dimensions The underlying mathematical theory is that of reproducing kernel Hilbert space from functional analysis Kernel Methods If a linear algorithm can be expressed only in terms of inner products it can be “kernelized” find linear pattern in high-dimensional space nonlinear relation in original space Specific kernel function determines nonlinearity Kernels Some simple kernels Linear kernel: k(x,z) = xTz ? equivalent to linear algorithm Polynomial kernel: k(x,z) = (1+xTz)d ? polynomial decision rules RBF kernel: k(x,z) = exp(-||x-z||2/2?) ? highly nonlinear decisions Gaussian Kernel: Example A hyperplane in some space Kernel Matrix k(x,y) K i j Kij=k(xi,xj) Kernel matrix K defines all pairwise inner products Mercer theorem: K positive semidefinite Any symmetric positive semidefinite matrix can be regarded as an inner product matrix in some space Kernel-Based Learning K {(xi,yi)} Data Embedding Linear algorithm k(x,y) or y Kernel-Based Learning K Data Embedding Linear algorithm Kernel design Kernel algorithm Kernel Design Simple kernels on vector data More advanced string kernel diffusion kernel kernels over general structures (sets, trees, graphs...) kernels derived from graphical models empirical kernel map Methods I) Instance-based methods: 1) Nearest neighbor II) Probabilistic models: 1) Na?ve Bayes 2) Logistic Regression III) Linear Models: 1) Perceptron 2) S