Untitled Quiz

Support Vector Machine (SVM)

• SVM is a classification technique
• It finds optimal hyperplanes to separate data points of different classes
• It works well with high dimensional data, avoiding dimensionality problems
• Training time is relatively slow, but testing is fast
• Less prone to overfitting than other methods

Contents to be Covered

• Introduction to SVM
• Maximum margin hyperplane
• Linear SVM
  • Calculating maximum margin hyperplane (MMH)
  • Learning a linear SVM
  • Classifying a test sample
• Classifying multiple-class data
• Non-linear SVM
  • Concept of non-linear data
  • Soft-margin SVM
  • Kernel trick

Maximum Margin Hyperplane (MMH)

• A key concept in SVM
• Attempts to find a hyperplane that maximizes the distance (margin) to the nearest data points of either class
• This maximizes the generalization ability of the classifier

Linear SVM

• A linear SVM is used when the training data are linearly separable
• It searches for a hyperplane that maximizes the margin to the nearest data points of either class. This classifier is called Maximum Margin Classifier (MMC)

Finding MMH for a Linear SVM

• Given n data tuples (Xᵢ, Yᵢ), where Xᵢ = (Xi₁,Xi₂, ... , Xᵢₘ) is data in m-dimensional space and Yᵢ is its class label.
• To find MMH, a hyperplane equation in 2-D space is: W₀ + W₁X₁ + W₂X₂ = 0 (e.g., ax + by + c = 0)
• Points above a hyperplane satisfy: W₀ + W₁X₁ + W₂X₂ > 0

Equation of a hyperplane in n-D space

• W₁X₁ + W₂X₂ + ... + WₘXₘ = b
• Wᵢ are real numbers and b is a real constant called the intercept

Finding a Hyperplane

• Consider two decision boundaries, b₁ and b₂, above and below a hyperplane
• The equation for a point X⁺ above a decision boundary is: W.X⁺ + b = K (where K > 0)
• Similarly, for X⁻ below is: W.X⁻ + b = K⁻ (where K⁻< 0)

Calculating Margin of a Hyperplane

• The margin is the distance between the two parallel hyperplanes
• The margin can be calculated in n-dimensional space as: d = |b₂ - b₁| / ||W||

Learning for a Linear SVM

• The objective is to maximize the margin, which is equivalent to minimizing ||W||² / 2
• This is a constrained optimization problem

Searching for MMH

• The problem is formulated as a minimization problem: Minimize μ'(W, b) = ||W||² / 2 Subject to yᵢ(W.xᵢ + b) ≥ 1, ∀ i = 1,2,..., n

Lagrange Multiplier Method

• A method to solve convex optimization problems, useful for SVM.
• Two types of constraints:
  • Equality constraints: gᵢ(x) = 0
  • Inequality constraints: hᵢ(x) ≤ 0
• The Lagrangian is defined based on the objective function and the constraints.

Classifying a test sample using linear SVM

• The test data X is classified using the formula: δ(X) = W.X + b = ∑ᵢ YᵢXᵢ.X + b

Classification of Multiple-class Data

• Strategies
  • One-versus-one (OVO)
    • Find MMHs for pairs of classes
    • Test X with each classifier and decide based on the signs of the output values
    • Involves n⁴ computations for n classes
  • One-versus-all (OVA)
    • Choose a class and treat other classes as a single class
    • Create a new hyperplane, and repeat for each class
    • Less complex than OVO strategy

Non-Linear SVM

• Used when data isn't linearly separable
• Key Concepts
  • Soft Margin SVM
  • Kernel Trick

Linear SVM for Linearly Not Separable Data

• Use a soft margin approach to handle instances that violate linear separability
• Introduces slack variables to accommodate errors
• Modified objective function adds a penalty for misclassifying training instances

Soft Margin SVM

• A modified linear SVM technique that allows some misclassifications
• Introduces slack variables ($ᵢ) to address non-linear separability
• The objective function is modified to minimize both ||W||² / 2 and the sum of errors

Non-Linear to Linear Transformation: Issues

• Mapping: Choosing an appropriate transformation to higher dimensional space is complex.
• Cost of Mapping: Transforming data into higher dimensions can lead to a significant computational burden.
• Dimensionality Problem: Calculating W.X or support vectors' dot product on high-dimensional data becomes computationally expensive