A Support Vector Machine (SVM) is a binary classifier that finds the decision boundary with the maximum margin — the widest strip separating two classes where no training points fall inside the strip.

The margin is the perpendicular distance from the decision boundary to the nearest data point on either side. Maximizing it gives the best chance of generalizing to unseen data.

Support vectors are the training points that lie exactly on the margin boundary (or inside it, in the soft-margin case). They alone determine the solution. All other points can be deleted with zero effect on the boundary.

The margin formula. The perpendicular distance between the two margin hyperplanes ($W\cdot X+b=+1$ and $W\cdot X+b=-1$) is:

Maximizing the margin means minimizing $\Vert W\Vert$. For a smooth derivative, we minimize $\frac{1}{2}\Vert W{\Vert }^2$ instead.

Hard margin SVM requires the training data to be perfectly linearly separable — every point must fall on or outside its class margin. Real data rarely satisfies this.

Two failure modes: - Overlapping classes. Points from different classes intermingle. No straight line can separate them. The hard margin problem has no feasible solution — the constraints cannot all be met. - Overfitting on separable data. Even when data is linearly separable, the maximum margin hyperplane may hug a noisy outlier, producing a narrow margin that generalizes poorly.

The fix: soft margin classification. Allow some points to violate the margin — but charge a penalty for each violation. The penalty is measured by a slack variable ${\xi }_i$.

The slack variable ${\xi }_i$ (pronounced "xi" or "epsilon" in the lecture) measures how far data point $i$ is from its correct side of the margin.

From Bishop (§7.1.1, Fig. 7.3): ${\xi }_n=0$ for points on or inside the correct margin boundary, and ${\xi }_n=|t_n-y(x_n)|$ for other points. A point exactly on the decision boundary has ${\xi }_n=1$.

Confidence interpretation:

• ${\xi }_i=0$ → high confidence (point is safely on its side)
• $0<{\xi }_i\le 1$ → moderate confidence (point is near the boundary)
• ${\xi }_i>1$ → low confidence (point is misclassified)

The optimization now trades off two competing goals:

- First term $\frac{1}{2}\Vert W{\Vert }^2$: Maximize the margin (minimize $\Vert W\Vert$). Same as hard margin. - Second term $C\sum {\xi }_i$: Penalize margin violations. $C$ controls how heavily we punish violations.

Subject to the relaxed constraints:

Notice: when ${\xi }_i=0$, the constraint reduces to the hard margin condition $y_i(W\cdot X_i+b)\ge 1$. When ${\xi }_i>0$, the right-hand side drops below 1 — the point is allowed to drift inside or even across the margin.

The Lagrangian for the soft margin (Bishop Eq. 7.22) introduces two sets of Lagrange multipliers: ${\alpha }_i$ for the margin constraints and ${\mu }_i$ for the non-negativity of ${\xi }_i$. After eliminating $W,b,\xi$, the dual is identical to the hard margin dual except that each ${\alpha }_i$ is now box-constrained: $0\le {\alpha }_i\le C$ (Bishop Eq. 7.33). This $C$ acts as an upper bound — support vectors with ${\alpha }_i=C$ lie inside or on the wrong side of the margin.

The hinge loss is the mathematical function that replaces the slack variable ${\xi }_i$ in the SVM objective. It measures the penalty for a single point:

Here $y_i(W\cdot X_i+b)$ is the "agreement" between the true label and the model's signed-distance prediction. In Bishop (§7.1.2, Eq. 7.45), this is written as $E_{SV}(y_n{t}_n)=[1-y_n{t}_n{]}_{+}$ where $[z{]}_{+}=\max (0,z)$ denotes the positive part.

The notation $\theta$ and $W$ are interchangeable — different textbooks, same weight vector.

The hinge loss mirrors the three slack-variable regimes exactly:

Case 1 — Correctly classified AND outside the margin ($y_i(W\cdot X_i+b)\ge 1$):

For a positive point ($y_i=+1$) with strong positive signal $(W\cdot X_i+b)\ge 1$:

For a negative point ($y_i=-1$) with strong negative signal $(W\cdot X_i+b)\le -1$:

Numerical check: $y_i=+1,W\cdot X_i+b=3\to \max (0,1-3)=\max (0,-2)=0$. ✓

Case 2 — Correctly classified but INSIDE the margin ($0<y_i(W\cdot X_i+b)<1$):

The agreement is positive but weak. Then $1-(\text{value}\in (0,1))\in (0,1)$:

Numerical check: $y_i=+1,W\cdot X_i+b=0.3\to \max (0,1-0.3)=0.7$. Between 0 and 1. ✓

Case 3 — Misclassified ($y_i(W\cdot X_i+b)<0$):

The agreement is negative — model and truth disagree. Then $1-(\text{negative})>1$:

Numerical check: $y_i=+1,W\cdot X_i+b=-2\to \max (0,1-(-2))=3>1$. ✓

Replacing ${\xi }_i$ with hinge loss gives the full SVM objective in one expression:

Or equivalently (Bishop Eq. 7.44 with $\lambda =(2C{)}^{-1}$):

Both forms express the same trade-off. The professor's form keeps $C$ in the numerator (large $C$ = strict); Bishop's uses $\lambda$ in the regularizer position (small $\lambda$ = strict).

A dataset is linearly inseparable when no single hyperplane can separate the classes. Example: blue dots cluster near the origin, red dots surround them in a ring (the classic XOR or concentric circles pattern). A straight line cannot split a ring from its center.

Hard margin SVM has no feasible solution on such data. Soft margin helps with overlapping classes but cannot fix fundamentally non-linear decision boundaries — a straight line through a ring will always misclassify roughly half of it.

The solution: Transform data into a higher-dimensional feature space where it becomes linearly separable, then apply linear SVM in that space.

The key insight (from Cover's theorem): a complex classification problem cast into a high-dimensional space is more likely to be linearly separable than in a low-dimensional space. You may need thousands or even infinite dimensions — and that's fine, because the kernel trick (§17.5) lets us compute in that space without ever constructing it explicitly.

Let $\varphi$ (phi) be the feature mapping:

A concrete example — mapping 2D to 5D:

The $\sqrt{2}$ factors are not arbitrary. They ensure $\varphi (A{)}^T\varphi (B)=(A^{T}B{)}^2$ for the polynomial kernel. Here's why: expanding $(A_1{B}_1+A_2{B}_2{)}^2$ gives $A_1^2{B}_1^2+A_2^2{B}_2^2+2A_1{A}_2{B}_1{B}_2$. The cross-term coefficient 2 must be distributed as $\sqrt{2}\cdot \sqrt{2}$ between the two $\varphi$ vectors for the dot product to work. Verified against Bishop §7.1 and the kernel trick derivation in §17.5.

How do we know $\varphi$? In practice, we work backward: start from a desired kernel function $K(X_i,X_j)=\varphi (X_i{)}^T\varphi (X_j)$, then derive $\varphi$ by algebraic expansion (§17.6). Libraries like sklearn.svm.SVC handle this automatically — you just pick the kernel.

The non-linear SVM process: 1. Map: Transform every data point $X_i\to \varphi (X_i)$ into the higher-dimensional feature space. 2. Classify: Run standard linear SVM (hard or soft margin) on the transformed points $\varphi (X_i)$.

The linear hyperplane found in the $\varphi$-space corresponds to a non-linear decision boundary in the original space. Both represent the same classifier — just viewed through different lenses.

Every formula from linear SVM carries over — just replace $X$ with $\varphi (X)$:

Decision boundary:

Primal objective (soft margin):

Weight vector:

Prediction for a new point $Z$:

Notice: every appearance of $\varphi$ is inside a dot product $\varphi (\cdot )\cdot \varphi (\cdot )$. This is the opening the kernel trick exploits.

The kernel trick computes $K(X_i,X_j)=\varphi (X_i{)}^T\varphi (X_j)$ — the dot product in the high-dimensional feature space — directly from the original points $X_i,X_j$, without ever constructing $\varphi (X_i)$ or $\varphi (X_j)$.

This gives the exact same mathematical result as the expensive explicit mapping. It is not an approximation. It is an algebraic identity: certain functions $K$ can be rewritten as dot products of some $\varphi$, and evaluating $K$ on the original inputs is infinitely cheaper than computing $\varphi$ and then the dot product.

A kernel function $K$ is defined as:

Wherever linear SVM uses $X_i\cdot X_j$ (the dot product in the original space), non-linear SVM uses $K(X_i,X_j)$. The decision function becomes:

All the duality, sparsity, and margin properties carry over — only the "similarity measure" between points changes from a simple dot product to a kernel evaluation.

A function $K(X_i,X_j)$ is a valid kernel iff there exists some mapping $\varphi$ such that:

To prove validity, find $\varphi$. The method is algebraic expansion: write $K$ as a sum of terms, each of which is a product of something depending only on $X_i$ and something depending only on $X_j$. Those "something" vectors are $\varphi (X_i)$ and $\varphi (X_j)$.

A function $K(X_i,X_j)$ must behave like a dot product in some feature space. Arbitrary functions don't. For the SVM dual to be a valid convex optimization problem (bounded below, with a unique solution), the kernel must satisfy specific mathematical conditions.

Mercer's theorem states that a function $K$ is a valid kernel (a Mercer kernel) if it satisfies:

1. Continuity: $K$ is a continuous function — no jumps or breaks. 2. Symmetry: $K(X_i,X_j)=K(X_j,X_i)$. Dot products are symmetric, so kernels must be too.

These are the two conditions the professor emphasizes for this course.

Additional condition from the full Mercer theorem: The kernel matrix (Gram matrix) formed by evaluating $K$ on any finite set of points must be positive semi-definite. This means for any set of points $\{x_1,\dots ,x_n\}$ and any vector $c\in {\mathbb{R}}^n$:

This condition ensures the SVM dual objective is bounded below (Bishop §7.1, Eq. 7.10 context). For this course, focus on symmetry and continuity. The PSD condition is the deeper mathematical guarantee.

Data: 2D points, two classes:

- Blue class (4 points): $(1,1),(1,-1),(-1,1),(-1,-1)$ — clustered at the corners of a unit square centered at the origin. - Red class (4 points): $(2,0),(0,2),(-2,0),(0,-2)$ — lying on the axes at distance 2 from the origin, forming a diamond around the blue cluster.

The blue points form an inner square; the red points form an outer diamond. No single straight line can separate them — the red points surround the blue points. This is the classic "ring and center" linear inseparability pattern.

The mapping function $\varphi$ is given (from the lecture PDF):

The condition $\sqrt{X_1^2+X_2^2}\ge 2$ checks whether the point is at Euclidean distance $\ge 2$ from the origin — i.e., whether it's a red point.

Blue points (distance $\sqrt{1^2+1^2}=\sqrt{2}<2$): unchanged.

Red points (distance $=2$, so the first formula applies):

After mapping: blue points remain at $(\pm 1,\pm 1)$; red points move to $(8,6)$ and $(10,4)$. The data is now linearly separable — blue cluster near the origin, red cluster far in the upper-right. A straight line can separate them.

FACT ML (also written FACCT — Fairness, Accountability, and Transparency) is a framework for responsible AI deployment:

- Fairness: The absence of bias toward any individual or group — whether that bias is intentional or unintentional. A fair model does not systematically disadvantage people based on race, gender, ethnicity, age, or other protected attributes.

- Accountability: Determining who takes responsibility when an ML system causes harm. If an autonomous vehicle crashes or an AI hiring tool discriminates — who is liable? The developer? The deployer? The organization? This must be defined before the project starts, not after a failure.

- Transparency: Ensuring models are understandable and auditable. Stakeholders (users, regulators, affected parties) should be able to inspect how decisions are made, especially in high-stakes domains.

These three pillars must be addressed at the start of any ML/AI project — not retrofitted after deployment.

ML models approximate patterns in training data. If the data contains bias (e.g., historically fewer women in engineering roles), the model learns that pattern as a "rule." Worse, because ML models optimize for overall accuracy, they can amplify the bias — the model treats the biased correlation as a stronger signal than it actually is.

Example: Word embedding models exhibit gender stereotypes. The vector for "nurse" is closer to "woman" and "engineer" is closer to "man" — not because of biology, but because training text corpora reflect historical occupational gender distributions. The model then reinforces those associations in downstream applications (job recommendation, search ranking).

Interpretability is the ability to explain why a model made a specific decision, in terms a human can understand.

Domains where interpretability is non-negotiable:

• Autonomous vehicles: If a self-driving car brakes suddenly and causes a collision, investigators must know why — was it a sensor error, a misclassified obstacle, or a correct decision?
• Criminal justice: If an algorithm recommends denying bail, the defendant has a constitutional right to challenge the reasoning.
• Finance: Fair lending laws require explainable credit decisions. "The algorithm said no" is not a legal defense.
• Healthcare: A misdiagnosis from an opaque model can kill. Doctors need to verify the model's reasoning against clinical knowledge.

In all these domains, interpretability is a legal and ethical requirement, not a nice-to-have.

Decision Trees: Naturally interpretable — each prediction is a path of if-then-else rules from root to leaf. You can point to the exact sequence of feature splits that produced the output. The KD-tree visualization shows how the feature space is recursively partitioned, making the geometry explicit. The root split uses the most important feature (highest information gain).

Linear Regression: Each feature gets a weight $w_j$. The prediction is $\sum w_j{x}_j+b$. You can say "Feature $j$ contributed $w_j{x}_j$ to the prediction." The weights directly quantify influence.

K-Nearest Neighbors (KNN): Explaining a KNN prediction: "This point is classified as Class A because 4 of its 5 nearest neighbors belong to Class A. Here are those neighbors." This mirrors how people make decisions by analogy — looking at similar past cases.

Regularization affects how many features the model uses, which directly impacts interpretability:

- L1 (Lasso): Penalty = $\sum |w_i|$. The diamond-shaped constraint region forces many weights to exactly zero. Result: a sparse model using only a handful of features. You can list all contributing features on one hand.

- L2 (Ridge): Penalty = $\sum w_i^2$. The circular constraint shrinks all weights toward zero but never to exactly zero. Result: all features remain, just with smaller weights. Explaining a prediction requires naming 200 features.

Why L1 wins for interpretability: Explaining "I classified this as Class 1 because Features 3, 7, and 12 indicated it" is feasible. Explaining it in terms of 200 features is not. Sparse = interpretable.

When you need high accuracy but also need explanations, use post-hoc explanation tools:

LIME (Local Interpretable Model-agnostic Explanations): - Explains individual predictions, not the whole model. - Model-agnostic: treats the model as a black box — queries it with modified inputs, observes outputs. - How it works (image example): Model predicts "dog." LIME creates variations of the image (hide the ear, blur the nose, mask the tail) and asks the model to re-predict each. If hiding the ear drops the "dog" confidence sharply, the ear was important. LIME builds a simple local model (e.g., linear) around that one prediction to show which input regions mattered. - Works on ANY model: neural nets, SVMs, ensembles, anything.

SHAP (SHapley Additive exPlanations): - Based on Shapley values from cooperative game theory — each feature is a "player" and the prediction is the "payout." SHAP fairly distributes the prediction among features. - Provides both local (per-prediction) and global (overall feature importance) explanations. - More theoretically grounded than LIME but computationally heavier.

Together: These tools bridge the accuracy-interpretability gap. Train a high-accuracy black box, then use LIME/SHAP to explain its decisions when needed.