SVM Question 2

Support Vector Machines (SVMs) - Exam Preparation Notes (Continued)

XI. Introduction (From the New PDF)

2. Q (Medium): Why is the “kernel trick” important for SVMs? A: It makes SVM one of the most effective and efficient machine learning tools.

3. Q (Short): What two classifiers are combined to form the basis of an SVM? A: A linear classifier and a k-nearest neighbor (K-NN) classifier.

XII. Linear Classifier

4. Q (Medium): How do Bayesian methods (mentioned in the context of linear classifiers) make decisions, and what is a limitation related to data distributions? A: Bayesian methods are model-based and give good decisions if the models are accurate. However, because data distributions are usually unknown, accurate models require a large number of training samples.

5. Q (Long): Explain the alternative approach to Bayesian methods that uses a functional form decision boundary. What is a linear classifier an example of? A: Instead of modeling the data distribution, we assume a functional form for the decision boundary between classes. The parameters of this boundary are estimated from training data. A linear classifier is an example of this approach, assuming a linear decision boundary.

6. Q (Medium): Given a feature vector $\mathbf{x}=(x_1,x_2,...,x_n)$, write the general form of a linear discriminant function, $f(\mathbf{x})$. A: $f(\mathbf{x})=w_0+w_1{x}_1+w_2{x}_2+...+w_n{x}_n$ (or, equivalently, $f(\mathbf{x})={\sum }_{j=0}^n{w}_j{x}_j$, where $x_0=1$).

7. Q (Short): In the linear discriminant function, what are the $x_i$ and $w_i$ terms? A: $x_i$ are the variables (features), and $w_i$ are the coefficients or weights.

8. Q (Short): Geometrically, what does $f(\mathbf{x})=0$ represent? A: A hyperplane in $n$-dimensional space (and the decision boundary).

9. Q (Short): How is a data point with feature vector $\mathbf{x}$ classified using the linear discriminant function? A:

   • If $f(\mathbf{x})>0$, $\mathbf{x}$ belongs to class 1.
   • If $f(\mathbf{x})<0$, $\mathbf{x}$ belongs to class 2.

10. Q (Long): Describe the “classical” way to find the weights of a linear classifier (the theoretical solution). A: Solve a set of linear equations. For $n$-dimensional data, you need $n+1$ linear equations (or samples) to solve for the $n+1$ weights. If $d_i$ represents the class label ($d_i=1$ for class 1, $d_i=-1$ for class 2), and you have samples $({\mathbf{x}}_i,d_i)$, you can set up the equations: ${\sum }_{j=0}^n{w}_j{x}_{ij}=d_i$ for $i=1,2,...,n+1$. This can be written in matrix form as $\mathbf{X}{\mathbf{w}}^T={\mathbf{d}}^T$ and solved as ${\mathbf{w}}^T={\mathbf{X}}^{-1}{\mathbf{d}}^T$.

11. Q (Long): Describe the “optimal” solution for finding the weights of a linear classifier. What is minimized? A: The optimal solution minimizes the total squared error of $f(\mathbf{x})$ over the entire training dataset. If you have $N$ data points $({\mathbf{x}}_i,d_i)$, you minimize: $E={\sum }_{i=0}^{N-1}(f({\mathbf{x}}_i)-d_i{)}^2$. Taking the partial derivative of $E$ with respect to each $w_k$ and setting it to zero leads to a system of $n+1$ linear equations. The solution can be expressed as ${\mathbf{w}}^T=({\mathbf{X}}^T\mathbf{X}{)}^{-1}({\mathbf{X}}^T{\mathbf{d}}^T)$.

12. Q (Medium): Explain the equations obtained after partial derivative of error. A: By taking the partial derivative of the total squared error, E, with respect to each weight, $w_k$, and setting the derivative to zero ($\frac{\partial E}{\partial w_k}=0$), we get $n+1$ linear equations: ${\sum }_{i=0}^{N-1}{x}_{ik}({\sum }_{j=0}^n{w}_j{x}_{ij}-d_i)=0$, which simplifies to ${\sum }_{j=0}^n{w}_j({\sum }_{i=0}^{N-1}{x}_{ik}{x}_{ij})={\sum }_{i=0}^{N-1}{x}_{ik}{d}_i$, for k = 0, 1, 2,…n

13. Q (Long): Describe the iterative optimization procedure (suboptimal solution) for finding the weights of a linear classifier. A:

    1. Initialize the weights $w_0,w_1,...,w_n$ with small random values.
    2. Take the next training sample $\{\mathbf{x},d\}=\{(x_1,x_2,...,x_n),d\}$, where $d=1$ or $-1$.
    3. Compute $f(\mathbf{x})=w_0+w_1{x}_1+...+w_n{x}_n$.
    4. If $f(\mathbf{x})\ne d$ (a misclassification), update the weights: $w_0\leftarrow w_0+cdk$ and $w_j\leftarrow w_j+cd{x}_j$ for $j=1,2,...,n$, where $c$ and $k$ are positive constants.
    5. Repeat steps 2-4 for all training samples until all samples are correctly classified or the weights stop changing.

14. Q (Medium): How can a linear classifier be extended to build a nonlinear classifier? Give an example. A: By mapping the original feature vector to a higher-dimensional space. For instance, a 2D vector $(x,y)$ can be mapped to a 5D vector $(u_1,u_2,u_3,u_4,u_5)$ where $u_1=\sqrt{2}x,u_2=\sqrt{2}y,u_3=x^2,u_4=\sqrt{2}xy,u_5=y^2$. This corresponds to the polynomial kernel $(1+x+y{)}^2$.

XIII. K-Nearest Neighbor (K-NN) Classification

15. Q (Medium): Describe the basic idea of the K-Nearest Neighbor (K-NN) algorithm. A: K-NN stores all available cases and classifies new cases based on a decision function (usually a distance measure). It finds the K nearest neighbors to the new data point and assigns the new data point to the majority class among those neighbors.

16. Q (Long): Given a training dataset and a distance measure, describe the K-NN classification algorithm. A:

    1. Input the new data point $\mathbf{x}$.
    2. Compute the distance between $\mathbf{x}$ and all training samples ${\mathbf{x}}_i$: $dist(\mathbf{x}-{\mathbf{x}}_i)$.
    3. Sort the distances in ascending order and rank the training samples accordingly: ${\mathbf{x}}_{r1},{\mathbf{x}}_{r2},...,{\mathbf{x}}_{rN}$.
    4. For a 1-NN classifier, classify $\mathbf{x}$ to the class of the nearest neighbor ($y_{r1}$).
    5. For a K-NN classifier, classify $\mathbf{x}$ to the majority class among the top $k$ ranked data points.

17. Q (Short): What are two common distance measures used in K-NN? A: Euclidean distance ($L_2$) and city block distance ($L_1$).

18. Q (Medium): What is the effect of the value of ‘k’ in K-NN, and how does it affect the classifier’s resistance to outliers? A: The value of $k$ has a smoothing effect. Larger values of $k$ make the classifier more resistant to outliers but can also lead to misclassifications. The choice of $k$ is usually determined empirically.

19. Q(Medium): What is weighted K-NN and what is the advantage? A: It gives greater weight to nearer neighbors and lesser to the farther ones. This overcomes misclassifications

20. Q (Medium): What is a disadvantage of K-NN related to its dependence on training data? How does this contrast with other classifiers? A: A K-NN classifier is tied to the training data. It needs to “carry” all the training data for classification, unlike other classifiers that, once trained, can discard the training data.

21. Q (Short): What is a key advantage of a K-NN classifier related to its ability to classify nonlinearly separable data? A: It can classify data that is nonlinearly separable.

XIV. Support Vector Machine (SVM)

22. Q (Medium): What are the disadvantages of a linear classifier that SVM aims to address? A:

    • The solution is either not optimal or computationally expensive.
    • It cannot classify nonlinearly separable data.

23. Q (Medium): What are the disadvantages of a K-NN classifier that SVM aims to address? A:

    • It’s difficult to choose ‘k’.
    • Dependence on training data.

24. Q (Short): State the two primary goals of a basic (linear) SVM. A:

    • Maximize the margin separating the two classes (optimal).
    • Use only a few training data points (support vectors) to define the hyperplane (efficient).

25. Q (Short): What additional goal does a kernel-based SVM achieve? A: To be able to classify data that is nonlinearly separable.

26. Q (Medium): What is a perceptron, and how does its training process relate to that of a linear classifier? A: A perceptron is a binary linear classifier. Its training process is similar to the linear classifier, but it can perform online learning, processing training data one at a time.

27. Q (Long): Given a training dataset $D=\{({\mathbf{x}}_i,y_i)\}$, where $y_i\in \{-1,1\}$, and the dot product $⟨{\mathbf{x}}_i,{\mathbf{x}}_j⟩={\mathbf{x}}_i\cdot {\mathbf{x}}_j$, write the formulation of a perceptron and its decision function. A:

    1. $f(\mathbf{x})=⟨\mathbf{w},\mathbf{x}⟩+b$
    2. Let $w_0=b$ and $x_0=1$; then $f(\mathbf{x})=⟨\mathbf{w},\mathbf{x}⟩$
    3. $h(\mathbf{x})=\text{sign}(f(\mathbf{x}))=y_i(f(\mathbf{x}))$

28. Q(Long): Describe the perceptron training algorithm. A: 1. Take the next training data (xᵢ, yᵢ) ∈ D 2. if h(xᵢ) ≥ 0, Wk+1 ← Wk 3. if h(xᵢ) < 0, then Wk+1 ← Wk + ηyᵢxᵢ, η > 0 4. Repeat from step 1.

29. Q (Long): Explain the concept of the margin between two classes in the context of SVM. Why is maximizing the margin important? A: The margin is the distance between the separating hyperplane and the closest data points from either class (the support vectors). Maximizing the margin leads to a more robust classifier that generalizes better to unseen data.

30. Q (Medium): Given the two inequalities for the two classes: $⟨\mathbf{w},\mathbf{x}⟩+b\ge 1$ for $y_i=+1$ and $⟨\mathbf{w},\mathbf{x}⟩+b\le -1$ for $y_i=-1$. Combine them into one inequality. A: $y_i(⟨\mathbf{w},\mathbf{x}⟩+b)-1\ge 0$

31. Q (Medium): Define the equations for the hyperplanes $H_1$, $H_2$, and $H_0$ in terms of $\mathbf{w}$, $\mathbf{x}$, and $b$. A:

    • $H_1$: $⟨\mathbf{w},\mathbf{x}⟩+b-1=0$
    • $H_2$: $⟨\mathbf{w},\mathbf{x}⟩+b+1=0$
    • $H_0$: $⟨\mathbf{w},\mathbf{x}⟩+b=0$

32. Q (Medium): What is the distance from the hyperplane $H_0$ to the origin in $n$-dimensional space? A: $\frac{|b|}{||\mathbf{w}||}$

33. Q (Long): What is the margin between the two hyperplanes $H_1$ and $H_2$? What are the data points that lie on $H_1$ and $H_2$ called? A: The margin is $\frac{2}{||\mathbf{w}||}$. The data points on $H_1$ and $H_2$ are called support vectors.

34. Q (Long): Formulate the optimization problem for maximizing the margin (the primal form of the SVM). A:

    • Minimize: $f(\mathbf{w})=\frac{1}{2}||\mathbf{w}|{|}^2=\frac{1}{2}⟨\mathbf{w},\mathbf{w}⟩$
    • Subject to: $g_i(\mathbf{w},b)=y_i(⟨\mathbf{w},{\mathbf{x}}_i⟩+b)-1\ge 0$ for $i=1,2,...,N$

35. Q (Long): Write the Lagrange function, $L(\mathbf{w},b,{\alpha }_i)$, for the SVM optimization problem. A: $L(\mathbf{w},b,{\alpha }_i)=f(\mathbf{w})-{\sum }_i{\alpha }_i{g}_i(\mathbf{w},b)=\frac{1}{2}||\mathbf{w}|{|}^2-{\sum }_i{\alpha }_i[y_i(⟨\mathbf{w},{\mathbf{x}}_i⟩+b)-1]=\frac{1}{2}\mathbf{w}\cdot \mathbf{w}-{\sum }_i{\alpha }_i{y}_i(\mathbf{w}\cdot {\mathbf{x}}_i+b)+{\sum }_i{\alpha }_i$

36. Q (Long): State the primal form of the SVM optimization problem. A:

    • Minimize: $L(\mathbf{w},b,{\alpha }_i)=\frac{1}{2}\mathbf{w}\cdot \mathbf{w}-{\sum }_i{\alpha }_i{y}_i(\mathbf{w}\cdot {\mathbf{x}}_i+b)+{\sum }_i{\alpha }_i$
    • Subject to: ${\alpha }_i\ge 0$, $i=1,2,...,N$