Introduction to Machine Learning

by Albert Major

• A decision boundary separates data points of different classes.
• In simple datasets, this can be a straight line (linear).
• In complex datasets, the boundary can be curved (nonlinear).
• The goal is to find the best boundary that separates classes with the largest possible margin.

2. Core Idea of SVM

• The basic SVM tries to find a linear hyperplane that separates two classes.
• A hyperplane is a generalization of a line (in 2D) or a plane (in 3D) to higher dimensions.
• When data is not linearly separable, SVM uses the kernel trick to project data into higher dimensions where separation becomes possible.

3. Kernel Trick

• The kernel trick maps features to a higher-dimensional space.
• Example: points mixed in a 2D circle can be separable in 3D if the center is “lifted.”
• This allows a linear boundary in higher dimensions to represent a nonlinear boundary in the original space.
• Common kernels:
  • Linear kernel – simple linear separation.
  • Polynomial kernel – introduces curved boundaries.
  • Radial Basis Function (RBF) – highly flexible, can perfectly fit training data (risk of overfitting).

4. Mathematical Formulation

• The hyperplane is defined as: WᵗX + b = 0.
  • W = weight vector (defines orientation of the boundary).
  • b = bias (defines position).
• The optimization problem: find W and b that maximize the margin (distance between classes) while correctly classifying all points.
• Margin is inversely proportional to ||W|| (the length of W).
  • So, maximizing margin means minimizing ||W||.
• For each class:
  • Points of one class: WᵗX + b ≥ 1.
  • Points of the other class: WᵗX + b ≤ -1.
  • Together: yᵢ(WᵗXᵢ + b) ≥ 1 for all training samples (yᵢ = label ±1).

5. Support Vectors

• Support vectors are the data points closest to the decision boundary.
• Only these points determine the boundary’s position.
• Other points further away have no effect.
• If support vectors move, the boundary changes.

6. Hard Margin vs Soft Margin

• Hard Margin SVM: no misclassification allowed.
  • Works only when data is perfectly separable.
  • Sensitive to outliers.
• Soft Margin SVM: allows some misclassifications for a better general boundary.
  • Introduces slack variables to permit violations of the margin rule.
  • Controlled by hyperparameter C:
    • Large C → strict separation, less tolerance for errors.
    • Small C → more flexible, allows more margin violations (better generalization).

7. Practical Considerations

• SVMs perform well on small datasets with many features.
• They can handle high-dimensional data effectively.
• Computationally expensive for very large datasets due to the kernel trick.
• No direct probability outputs (unlike logistic regression).
• Works well for classification, not typically for regression.

8. Applications

• Image classification – e.g., recognizing handwritten digits (pixels as features).
• Text classification – each word can be a feature, leading to high-dimensional vectors.
• Bioinformatics – classifying genes or proteins.
• Works best when most features are informative and the dataset is small but complex.

9. Advantages

• Strong performance with clear class boundaries.
• Robust to overfitting if C is chosen well.
• Effective in high-dimensional feature spaces.

10. Limitations

• Inefficient with very large datasets.
• Choosing the right kernel and hyperparameters requires tuning.
• No built-in probabilistic interpretation.

11. Historical Context

• First introduced in 1964.
• Updated in the 1990s.
• Still relevant and used today in research areas like cancer genomics.
• Predecessor to modern deep learning models.

12. Connection to Machine Learning Basics

• SVM follows the standard process:
  • Split data into training, validation, and test sets.
  • Tune hyperparameters (C, kernel type) using the validation set.
  • Evaluate on test data to measure generalization.
• Reinforces understanding of optimization, loss functions, and hyperparameter tuning.

13. Relation to Your Studies

• SVMs illustrate key ideas in machine learning:
  • Linear models, optimization, regularization, and high-dimensional reasoning.
  • The concept of mapping data to higher spaces appears again in neural networks.
  • Understanding SVMs helps grasp later topics like deep learning, feature engineering, and nonlinear classification.
• SVMs also demonstrate how mathematical formulation translates into real-world tasks like text or image recognition.

14. Summary Formulae

• Decision boundary: WᵗX + b = 0
• Constraints: yᵢ(WᵗXᵢ + b) ≥ 1
• Margin: 2 / ||W||
• Objective: minimize (1/2)||W||² subject to above constraints.

15. Key Takeaways

• SVM = margin-based classifier.
• Kernel trick = nonlinear transformation for separability.
• Support vectors = boundary-defining points.
• Optimization = maximize margin, minimize classification error.
• Good for small, high-dimensional datasets.
• Poor scalability on very large datasets.