Unit 5: Mathematical Foundations of Support Vector Machines - Practice Quiz

The core idea of SVM is to find the optimal hyperplane that has the largest possible distance, or margin, to the nearest data points of any class, which improves the model's generalization.

Support vectors are the critical data points that "support" or define the position of the hyperplane. They are the points that are closest to the decision boundary.

A linear SVM separates data using a flat boundary. In two dimensions this is a line, in three dimensions a plane, and in higher dimensions it is called a hyperplane.

A Hard Margin SVM requires that all data points are correctly classified with a margin, which is only possible if the data is perfectly separable by a hyperplane without any errors.

Soft Margin SVM introduces slack variables to allow for some misclassifications, making it flexible enough to handle overlapping classes and outliers which would prevent a hard-margin SVM from finding a solution.

The slack variable is introduced for each data point . If , it measures the degree to which the point is either inside the margin or on the wrong side of the hyperplane.

A small value creates a wider margin but allows more margin violations (a "softer" margin). A large value penalizes violations more heavily, resulting in a narrower margin (closer to a "hard" margin).

The Lagrangian method combines the objective function and its constraints into a single function. This allows us to solve the problem by finding the saddle point of this function, often by moving to the dual problem.

The variables , one for each data point, are introduced to incorporate the classification constraints into the objective function and are known as Lagrange multipliers.

A key result of the KKT conditions is that only support vectors can have non-zero Lagrange multipliers. For all other points that are correctly classified and lie outside the margin, .

The primal problem is formulated as . Minimizing the norm of the weight vector, , is mathematically equivalent to maximizing the margin, which is .

The dual formulation expresses the problem in terms of dot products of the input data points. This structure allows us to replace the dot product with a kernel function, which is the essence of the kernel trick for non-linear classification.

The kernel trick is a clever mathematical technique that uses a kernel function to calculate the result of a dot product in a high-dimensional space, avoiding the computationally expensive step of explicit data transformation.

The Radial Basis Function (RBF) kernel is a popular default choice for SVMs because of its flexibility in modeling complex, non-linear relationships. Other common kernels include Linear, Polynomial, and Sigmoid.

The linear kernel, defined as , is simply the dot product in the original feature space. This means the SVM operates without any non-linear mapping, creating a linear decision boundary.

Non-linear kernels are used to map data into a higher-dimensional space where a linear separator might exist. This is necessary when the classes cannot be separated by a simple line or plane in their original space.

SVM training involves minimizing a quadratic objective function () subject to linear inequality constraints. This specific type of problem is known as a convex quadratic program, which guarantees a unique global minimum.

The margin of an SVM is geometrically defined as . Therefore, minimizing (or its squared value for mathematical convenience) is the same as maximizing the margin.

Because the Lagrange multipliers are zero for non-support vectors, the sum in the decision function only needs to be computed over the support vectors. This makes prediction efficient, as it doesn't depend on the entire dataset.

In a 2D space, the decision boundary is a line. The margin is the region between two other lines that are parallel to the decision boundary and pass through the closest points of each class (the support vectors).

The geometric margin is given by . The optimal hyperplane is defined by . When data points are scaled to , the optimal weight vector scales to to maintain the same separating boundary decision. The new margin becomes , which is double the original margin.

The hyperparameter is a regularization parameter that controls the trade-off between maximizing the margin and minimizing the classification error. A large assigns a high penalty to misclassified points and points within the margin, forcing the optimizer to find a solution with fewer margin violations, which typically results in a narrower margin, similar to a hard-margin SVM.

The dual formulation expresses the optimization problem in terms of dot products of the input feature vectors (). This structure is key because the kernel trick works by replacing this dot product with a kernel function , allowing SVMs to efficiently learn non-linear decision boundaries in high-dimensional feature spaces without explicitly computing the transformations.

The KKT conditions for SVMs include the complementary slackness condition: . For a point that is not a support vector, it lies correctly classified and outside the margin, so . For the product to be zero, its corresponding Lagrange multiplier must be zero.

The parameter in the polynomial kernel represents the degree of the polynomial. A higher value of corresponds to a more complex decision boundary, which can fit more intricate patterns in the data but also has a higher risk of overfitting.

This is a Quadratic Programming (QP) problem because the objective function () is a quadratic function of the variables (the components of ), and all the constraints () are linear with respect to the optimization variables and .

In a hard-margin SVM, the support vectors are the critical data points that lie precisely on the margin hyperplanes (i.e., where ). These points alone define the position and orientation of the optimal separating hyperplane.

The constraint for soft-margin SVM is . A point is correctly classified if . If , then . Even if the point satisfies the constraint, it's possible for to be negative, meaning the point is on the wrong side of the hyperplane. Specifically, always indicates a misclassified point.

The dual problem is derived using the method of Lagrange multipliers. Each is a Lagrange multiplier introduced for the constraint corresponding to the data point . Their optimal values determine which points are support vectors.

The parameter defines how much influence a single training example has. A small means that the influence is large and far-reaching, resulting in a smoother, less complex decision boundary. As approaches 0, the RBF kernel SVM model behaves similarly to a linear SVM.

From the KKT conditions, the optimal weight vector is given by . Since the Lagrange multipliers are zero for all non-support vectors, the sum is only over the support vectors (where ). Therefore, is a linear combination of only the support vectors.

In a soft-margin SVM, the dual constraints are . When , the point is a margin-violating support vector (either misclassified or inside the margin). If many points have , it suggests that the penalty for misclassification is not high enough to enforce a stricter margin, meaning is likely too small for the desired level of accuracy.

Maximizing is equivalent to minimizing . For mathematical convenience (to make the objective function differentiable and remove the square root), this is further transformed into minimizing . This is a strictly convex function, which guarantees a unique global minimum, and the factor of 1/2 simplifies the derivative during optimization.

A function is a valid kernel if its corresponding Gram matrix is positive semi-definite for any set of data points. While the polynomial, RBF, and (for some parameters) sigmoid kernels satisfy this condition, the function does not generally produce a positive semi-definite Gram matrix and thus does not correspond to a dot product in some feature space. It violates Mercer's theorem.

The primal problem optimizes over variables ( and ). The dual problem optimizes over variables (the ). When the number of data points is much larger than the number of features , solving the primal problem with variables is often more efficient than solving the dual with variables, especially when using a linear kernel.

The prediction for a new point depends only on the kernel evaluations between the new point and the support vectors. Since the set of support vectors is often a small subset of the entire training dataset, the summation is over a relatively small number of terms, making the prediction computationally efficient regardless of the dimensionality of the feature space.

The primal objective for soft-margin SVM is to minimize . The term penalizes the model for having non-zero slack variables. Since corresponds to a point violating the margin, minimizing this sum encourages the model to classify points correctly and keep them outside the margin.

For high-dimensional and sparse data like text features, linear models often perform very well and are computationally efficient. A linear kernel SVM is equivalent to mapping the data to an even higher-dimensional space where it is more likely to be linearly separable. Non-linear kernels like RBF can be less effective and much slower to train in this context.

The hard-margin SVM requires that every data point is correctly classified with a margin of at least 1. If the data is not linearly separable, it is impossible to find a hyperplane that satisfies this condition for all points. Therefore, the optimization problem has no feasible solution.

Strong duality means that there is zero gap between the primal and dual solutions. The maximum value of the dual objective is equal to the minimum value of the primal objective. This is a crucial property that allows us to solve the dual problem to find the solution for the primal, which is particularly useful for applying the kernel trick.

Non-uniform scaling ( is not a multiple of the identity matrix) changes the geometry of the feature space, altering distances and angles. This will change the optimal separating hyperplane's orientation and position relative to the data points. Consequently, the maximal geometric margin will change, and the set of points that become support vectors can also change as different points may become closest to the new optimal boundary.

As , the penalty for misclassification becomes infinitely high. The optimizer will try desperately to make all slack variables equal to zero. For non-linearly separable data, this is impossible. The model will compromise by finding a hyperplane with a very small margin (large ) that attempts to thread the needle between the classes, making the boundary very complex and highly influenced by every single point, leading to extreme overfitting.

The primal problem's complexity depends on the number of features (solving for ). The dual problem's complexity depends on the number of samples (solving for and often requiring an Gram matrix). When and a linear kernel is used, solving the primal directly is much more efficient as you are optimizing over a -dimensional space instead of an -dimensional one.

The set of valid kernels (functions that produce a positive semi-definite Gram matrix) is closed under positive scaling, addition, and element-wise product (Hadamard product). However, the difference of two kernels is not guaranteed to be a valid kernel because the resulting Gram matrix may not be positive semi-definite (it could have negative eigenvalues).

The KKT conditions for soft-margin SVM include and , where . If , then . This means the condition is satisfied for any . Since , the point is a support vector. Such points are often called 'bounded' support vectors and represent margin violators (either misclassified or correctly classified but inside the margin).

The SVM objective function is strictly convex with respect to . For a convex optimization problem, any local minimum is a global minimum, and the minimum value of the objective function is unique. Because the objective is strictly convex, the optimal solution for the primal variables (the weight vector ) is also unique. The bias may not be unique in certain edge cases (e.g., if there are no support vectors with ).

In a higher-dimensional space, data points become sparser, and it's more likely that a separating hyperplane can be found. With more dimensions (degrees of freedom), there is more 'room' to place a hyperplane that is further away from all data points. This is a key concept behind Cover's theorem and the motivation for using kernels to map data to higher dimensions, where linear separability and larger margins become more probable.

The SVM decision boundary is determined solely by the support vectors. A point correctly classified and strictly outside the margin has a corresponding Lagrange multiplier . Such a point is not a support vector. Removing it from the dataset does not change the set of active constraints in the optimization problem. Therefore, retraining the model will yield the exact same decision boundary.

The dual formulation's objective function involves terms of the form . The final decision rule is also based on dot products: . The kernel trick works by replacing these dot products with a kernel function . The primal formulation, which solves for directly, involves the feature vectors in its constraints () and is not structured in a way that only involves dot products, making the kernel trick inapplicable.

As , the term also approaches 0. Using a Taylor expansion, for small . So, . In the SVM decision function, many of these terms are constant or depend on the norm of a single point, behaving like offsets. The dominant term that depends on both and is the linear dot product . Therefore, the behavior of the kernel becomes increasingly linear, and the decision boundary approaches a linear hyperplane.

Taking the derivative of the Lagrangian with respect to and setting it to zero gives: . This directly implies that the optimal weight vector is . From the KKT conditions, we know that only for support vectors, meaning is a linear combination of the feature vectors of only the support vectors.

Changing the regularization to the L1-norm results in what is known as an L1-SVM. The objective function is no longer quadratic, so it is not a standard QP problem (though it is still a convex problem). The L1-norm is known for inducing sparsity, meaning it encourages many of the components of the weight vector to be exactly zero. This has the effect of performing automatic feature selection.

This is the definition of a positive semi-definite (PSD) matrix. It ensures that the kernel function behaves like a dot product in some (possibly infinite-dimensional) feature space, which is crucial for the geometry of the SVM. It guarantees that squared distances in the feature space are non-negative and that the dual optimization problem is convex and well-posed.

The hard-margin SVM boundary is defined by the support vectors, which are the points lying exactly on the margin hyperplanes (). If a new point satisfies the margin constraint of the existing solution, i.e., , it does not violate any constraints and does not provide any new information that would force the hyperplane to move. It is not a support vector, so the optimal solution remains unchanged.

In optimization theory, weak duality states that the optimal value of the dual problem provides a lower bound on the optimal value of the primal problem. The difference between these values is the duality gap. For SVMs, the problem is constructed such that strong duality holds, meaning the duality gap is zero. This guarantees that solving the easier dual problem gives us the same optimal solution as solving the primal problem.

In the Lagrangian of the primal problem, we have terms and . The stationarity condition with respect to yields , which gives . Since the KKT conditions require and , this relationship directly implies that must be less than or equal to , creating the box constraint in the dual problem.

To make the fastest progress towards the global optimum, SMO prioritizes the multipliers that are currently 'most wrong'. The KKT conditions must hold at the optimal solution. Therefore, a good heuristic is to select a point that currently violates these conditions by the largest amount. This strategy helps the algorithm converge more quickly than random or sequential selection.

A function is a valid Mercer kernel if its Gram matrix is positive semi-definite (PSD) for any set of points. The function is not a valid kernel. The diagonal elements of its Gram matrix are . A PSD matrix must have non-negative diagonal elements. More formally, the Gram matrix for this function can have negative eigenvalues, violating the PSD condition. The other options are the well-known Polynomial kernel, RBF kernel, and a valid intersection-style kernel.

A very small places a high emphasis on minimizing (maximizing the margin) and a very low emphasis on penalizing slack variables . The optimizer might find that it can achieve a much smaller (a much wider margin) by allowing a few points to fall within the margin or even be misclassified, as the penalty for doing so is negligible. It prioritizes a simple, wide-margin solution over perfect classification.

A larger places a higher penalty on misclassification errors (the terms). To reduce these errors, the model will try to fit the data more closely. This often requires a more complex decision boundary, which in the linear case corresponds to a smaller margin. Since the margin is inversely related to , a smaller margin implies a larger . Therefore, as increases, the model tolerates a larger in order to reduce classification errors, causing to increase or stay the same.