Question SVM

Support Vector Machines (SVMs) - Exam Preparation Notes

I. Introduction & Overview

2. Q (Short): What is a Support Vector Machine (SVM), according to the definition provided? A: A system for efficiently training linear learning machines in kernel-induced feature spaces, while respecting the insights of generalization theory and exploiting optimization theory.

II. Basic Concepts

6. Q (Short): Write the formula for the scalar product of two vectors, $\mathbf{a}$ and $\mathbf{b}$. A: $\mathbf{a}\cdot \mathbf{b}=||\mathbf{a}||||\mathbf{b}||\cos \theta$

7. Q (Short): What is the general form of a decision function, $f(x)$, for binary classification, and what are the resulting class labels ($y_i$)? A: $f(x)\in \mathbb{R}$. - If $f(x_i)\ge 0$, then $y_i=1$. - If $f(x_i)<0$, then $y_i=-1$.

8. Q (Medium): Briefly describe the core idea behind how SVMs work. A: SVMs find the best separating hyperplane between classes according to a criterion (e.g., maximum margin). The training process is an optimization problem, and the training data is effectively reduced to a set of support vectors.

III. Key Concepts: Feature Spaces and Kernels

9. Q (Short): Why might we map data to a higher-dimensional feature space? A: To make the data linearly separable, even if it isn’t in the original input space.

10. Q (Medium): What is a kernel function, and what property must it satisfy? A: A kernel function, $K({\mathbf{x}}_1,{\mathbf{x}}_2)$, implicitly maps data to a new feature space. It must be equivalent to an inner product in some feature space. Formally, $K({\mathbf{x}}_1,{\mathbf{x}}_2)\in \mathbb{R}$.

11. Q (Short): Give three examples of common kernel functions. A:

    • Linear: $⟨\mathbf{x}\cdot \mathbf{z}⟩$
    • Polynomial: $P((\mathbf{x}\cdot \mathbf{z}))$
    • Gaussian: $\exp (-||\mathbf{x}-\mathbf{z}|{|}^2/{\sigma }^2)$

IV. Linear Separators and Maximum Margin

13. Q (Medium): How can binary classification be viewed in terms of feature space? A: Binary classification is the task of separating classes in feature space using a hyperplane. The decision function is $f(\mathbf{x})=\text{sign}({\mathbf{w}}^T\mathbf{x}+b)$.

14. Q (Long): Given multiple possible linear separators, how does an SVM choose the “optimal” one? Explain the concept of the margin. A: The SVM aims to find the hyperplane that maximizes the margin. The margin is the distance between the hyperplane and the closest data points from either class (the support vectors). A larger margin generally leads to better generalization.

15. Q (Medium): Explain the process of finding the optimal linear separator using convex hulls. A:

    1. Find the closest points in the convex hulls of the two classes.
    2. The optimal hyperplane bisects the line segment connecting these two closest points. The normal vector of the hyperplane, $\mathbf{w}$, is given by $\mathbf{w}=\mathbf{d}-\mathbf{c}$, where $\mathbf{d}$ and $\mathbf{c}$ are the closest points. The hyperplane equation is ${\mathbf{w}}^T\mathbf{x}+b=0$.

[[SVMIITD.pdf#page=18&rect=191,23,529,315|]] 15. Q (Short): What are support vectors? A: The data points closest to the separating hyperplane.

16. Q (Short): What is the distance, $r$, from an example data point to the separating hyperplane? A: $r=\frac{{\mathbf{w}}^T\mathbf{x}+b}{||\mathbf{w}||}$

17. Q (Short): What is the margin, $\rho$, of the separator? A $\rho$ is the width of separation between classes.

18. Q (Medium): Why is maximizing the margin considered a good strategy, both intuitively and theoretically? A:

    • Intuitively: A larger margin provides more “buffer” against misclassification of new, unseen data.
    • Theoretically: Maximizing the margin minimizes the complexity of the model (related to VC dimension), which helps prevent overfitting and improves generalization.

19. Q (Short): In maximum margin classification, which training examples are crucial, and which can be ignored? A: Only the support vectors are important; other training examples are ignorable.

V. Linear SVM - Mathematical Formulation

22. Q (Long): Formulate the optimization problem for finding the maximum margin hyperplane (the primal problem). Include the constraints. A: We want to find $\mathbf{w}$ and $b$ such that:

    • $\rho =\frac{2}{||\mathbf{w}||}$ is maximized.
    • Subject to the constraints:
      • ${\mathbf{w}}^T{\mathbf{x}}_i+b\ge 1$ if $y_i=1$
      • ${\mathbf{w}}^T{\mathbf{x}}_i+b\le -1$ if $y_i=-1$ This is often reformulated as:
    • Minimize: $\Phi (\mathbf{w})=\frac{1}{2}{\mathbf{w}}^T\mathbf{w}$
    • Subject to: $y_i({\mathbf{w}}^T{\mathbf{x}}_i+b)\ge 1$ for all $i$.

23. Q (Long): Explain how the optimization problem is solved (the dual problem). What are Lagrange multipliers, and what is the final form of the solution? A: We use Lagrange multipliers, ${\alpha }_i$, one for each constraint. The dual problem is:

    • Maximize: $Q(\mathbf{\alpha })={\sum }_{i=1}^N{\alpha }_i-\frac{1}{2}{\sum }_{i=1}^N{\sum }_{j=1}^N{\alpha }_i{\alpha }_j{y}_i{y}_j{\mathbf{x}}_i^T{\mathbf{x}}_j$
    • Subject to:
      • ${\sum }_{i=1}^N{\alpha }_i{y}_i=0$
      • ${\alpha }_i\ge 0$ for all $i$ The solution has the form:
    • $\mathbf{w}={\sum }_{i=1}^N{\alpha }_i{y}_i{\mathbf{x}}_i$
    • $b=y_k-{\mathbf{w}}^T{\mathbf{x}}_k$ for any ${\mathbf{x}}_k$ such that ${\alpha }_k\ne 0$ The classifying function is: $f(\mathbf{x})={\sum }_{i=1}^N{\alpha }_i{y}_i{\mathbf{x}}_i^T\mathbf{x}+b$

24. Q (Short): How do you identify support vectors from the solution of the dual problem? A: Support vectors correspond to training points ${\mathbf{x}}_i$ where the Lagrange multiplier ${\alpha }_i$ is non-zero.

25. Q(Medium): Explain the solution to the optimization problem. A: The solution is $\mathbf{w}=\sum {\alpha }_i{y}_i{\mathbf{x}}_i$ and $b=y_k-{\mathbf{w}}^T{\mathbf{x}}_k$ for any ${\mathbf{x}}_k$ such that ${\alpha }_k\ne 0$. Each non-zero $a_i$ indicates that the corresponding $x_i$ is a support vector. The classifying function is $f(\mathbf{x})=\sum {\alpha }_i{y}_i{\mathbf{x}}_i^T\mathbf{x}+b$.

VIII. Non-linear SVMs

31. Q (Medium): How do non-linear SVMs handle data that is not linearly separable? A: They map the data to a higher-dimensional feature space where the data becomes linearly separable (or nearly so, using a soft margin).

32. Q(Medium): Describe the non-linear classification with an example. A: Consider $x=[a,b]$. Then, $x.w=w_{1}a+w_{2}b$. Now consider $\theta (x)=[a,b,ab,a^2,b^2]$, and we have, $\theta (x).w=w_{1}a+w_{2}b+w_{3}ab+w_4{a}^2+w_5{b}^2$

33. Q (Long): Explain the “kernel trick.” Why is it important? A: The kernel trick avoids explicitly computing the mapping to the high-dimensional feature space, $\varphi (\mathbf{x})$. Instead, we use a kernel function, $K({\mathbf{x}}_i,{\mathbf{x}}_j)$, which computes the inner product in the feature space directly from the input space: $K({\mathbf{x}}_i,{\mathbf{x}}_j)=\varphi ({\mathbf{x}}_i{)}^T\varphi ({\mathbf{x}}_j)$. This is crucial because the feature space can be extremely high-dimensional (even infinite), making explicit computation infeasible.

34. Q (Long): How does the dual problem formulation change for non-linear SVMs? A: The only change is that the inner product ${\mathbf{x}}_i^T{\mathbf{x}}_j$ is replaced by the kernel function $K({\mathbf{x}}_i,{\mathbf{x}}_j)$:

    • Maximize: $Q(\mathbf{\alpha })={\sum }_{i=1}^N{\alpha }_i-\frac{1}{2}{\sum }_{i=1}^N{\sum }_{j=1}^N{\alpha }_i{\alpha }_j{y}_i{y}_{j}K({\mathbf{x}}_i,{\mathbf{x}}_j)$
      • Subject to:
        • ${\sum }_{i=1}^N{\alpha }_i{y}_i=0$
        • $0\le {\alpha }_i\le C$ for all $i$ The classifying function becomes: $f(\mathbf{x})={\sum }_{i=1}^N{\alpha }_i{y}_{i}K({\mathbf{x}}_i,\mathbf{x})+b$

IX. Kernel Functions and Mercer’s Theorem

35. Q (Medium): What is a positive definite matrix? A: A square matrix A is positive definite if ${\mathbf{x}}^T\mathbf{Ax}>0$ for all nonzero column vectors $\mathbf{x}$.

36. Q(Short): What is a negative definite, positive semi-definite and negative semi-definite matrix? A: A square matrix A is negative definite if ${\mathbf{x}}^T\mathbf{Ax}<0$ for all nonzero column vectors $\mathbf{x}$. It’s positive semi-definite if ${\mathbf{x}}^T\mathbf{Ax}\ge 0$, and negative semi-definite if ${\mathbf{x}}^T\mathbf{Ax}\le 0$.

37. Q (Medium): State Mercer’s theorem. Why is it important for SVMs? A: Mercer’s theorem states that every semi-positive definite symmetric function is a kernel. This is important because it provides a way to determine if a function is a valid kernel (i.e., corresponds to an inner product in some feature space) without having to explicitly find the feature mapping $\varphi (\mathbf{x})$.

38. Q(Medium): What is a Gram Matrix? A: A matrix, K, composed of kernel values. For example: $K=\left[\begin{array}{cccc}K({\mathbf{x}}_1,{\mathbf{x}}_1)& K({\mathbf{x}}_1,{\mathbf{x}}_2)& \dots & K({\mathbf{x}}_1,{\mathbf{x}}_N)\\ K({\mathbf{x}}_2,{\mathbf{x}}_1)& K({\mathbf{x}}_2,{\mathbf{x}}_2)& \dots & K({\mathbf{x}}_2,{\mathbf{x}}_N)\\ ⋮& ⋮& \ddots & ⋮\\ K({\mathbf{x}}_N,{\mathbf{x}}_1)& K({\mathbf{x}}_N,{\mathbf{x}}_2)& \dots & K({\mathbf{x}}_N,{\mathbf{x}}_N)\end{array}\right]$

39. Q (Short): Give examples of kernel functions besides the linear, polynomial, and Gaussian kernels. A: Two-layer perceptron: $K({\mathbf{x}}_i,{\mathbf{x}}_j)=\tanh ({\beta }_0{\mathbf{x}}_i^T{\mathbf{x}}_j+{\beta }_1)$

X. SVM Applications and Extensions

40. Q (Short): List some application areas where SVMs have been successfully used. A: Text classification, genomic data analysis, and many other classification tasks.

41. Q (Short): Name two popular optimization algorithms for training SVMs. A: SMO (Sequential Minimal Optimization) and SVMlight.

42. Q (Medium): List some extensions to the basic SVM framework. A:

    • Regression
    • Variable Selection
    • Boosting
    • Density Estimation
    • Unsupervised Learning (Novelty/Outlier Detection, Feature Detection, Clustering)