16. Learning: Support Vector Machines

Key Takeaways

• Widest Street Approach: Support Vector Machines aim to draw a straight decision boundary that creates the widest possible "street" or margin separating positive and negative samples, distinguishing them from simpler methods like neural nets or decision trees that just draw a line. 4:07
• Decision Rule & Constraints: The decision rule classifies an unknown sample based on whether w (a vector perpendicular to the median line of the street) dotted with the unknown u plus a constant b is greater than or equal to zero. This is constrained such that positive training samples yield a result of 1 or greater, and negative samples yield -1 or less, which can be unified into y_i * (w . x_i + b) >= 1. 6:56 13:33
• Optimization Objective: Maximizing the width of the street, which is expressed as 2 / ||w|| (where ||w|| is the magnitude of vector w), is mathematically equivalent and more convenient to achieve by minimizing 1/2 * ||w||^2. 21:08
• Lagrange Multipliers & Weight Vector: Using Lagrange multipliers to minimize the objective function subject to constraints reveals that the optimal weight vector w is a linear sum of the sample vectors (w = sum(alpha_i * y_i * x_i)), where alpha_i are the Lagrange multipliers and y_i is the class label (+1 or -1). Additionally, the sum of alpha_i * y_i must equal zero. 28:06 29:55
• Dot Product Dependence: Both the optimization function (the Lagrangian) and the final decision rule depend solely on the dot products of pairs of sample vectors (e.g., x_i . x_j), rather than the explicit coordinates of the vectors themselves. 38:04
• Kernel Trick for Non-Linearity: For data that is not linearly separable in the original space, a "kernel function" k(x_i, x_j) can implicitly compute the dot product of the transformed vectors phi(x_i) . phi(x_j) in a higher-dimensional space, without needing to explicitly define or calculate the transformation phi(x). This allows SVMs to find non-linear decision boundaries. Popular kernels include polynomial ((u . v + 1)^n) and radial basis functions (e^(-||u-v||^2 / sigma)). 43:50 44:07
• Convexity and Global Solutions: A significant advantage of SVMs is that the optimization problem is convex, meaning it guarantees finding a global optimum and does not suffer from the problem of getting stuck in local maxima, which can plague other machine learning models like neural networks. However, kernel choice (e.g., small sigma in RBF kernels) can still lead to overfitting. 40:04 45:50
• Historical Development: The core idea of Support Vector Machines was developed by Vladimir Vapnik in his Ph.D. thesis in the early 1960s in the Soviet Union but remained largely unknown and unapplied for nearly 30 years due to a lack of computational resources. The "kernel trick," though conceived earlier, was only recognized for its critical importance and widely developed in the early 1990s after Vapnik immigrated to the U.S. and SVMs were successfully applied to problems like handwriting recognition. 46:40 48:38