Learn machine learning with scikit-learn, covering supervised learning, clustering, regression, SVMs, autoencoders, and ensemble methods through practical Python projects.

ml.tar.gz

Playground

Playground-SPA

Complexity CH-1

regulizer CH-1

regulizer CH-1-S

regulizer ch1_v2

complexity ch1_v2

code_widget

ST_kernel_trick-LIVE

python

pytorch

ST_Autoencoders

code_widget_torchsummary

code_widget_tqdm

SPA_tqdm

AE_multiple

SPA_server

Implementation of NN

c1l3

Implementation of NN-copy

This course focuses on core concepts, algorithms, and machine learning techniques. It explores the fundamentals, implements algorithms from scratch, and compares the results with scikit-learn, the Python machine learning library. This course contains examples, theoretical knowledge, and codes for various ML algorithms.

You’ll start by learning the essentials of machine learning and its applications. Then, you’ll learn about supervised learning, clustering, and constructing a bag of visual words project, followed by generalized linear regression, support vector machines, logistic regression, ensemble learning, and principal component analysis. You’ll also learn about autoencoders and variational autoencoders and end with three exciting projects.

By the end, you’ll have a solid understanding of machine learning and its algorithms, hands-on experience implementing such algorithms and applying them to different problems, and an understanding of how each algorithm works with the provided examples.

Fundamentals of Machine Learning: A Pythonic Introduction

The dual formulation of SVM is important because it allows us to kernelize the optimization problem, making it easier to find a hyperplane that separates the classes in a higher-dimensional feature space. Additionally, the dual formulation provides better visibility of the solution's sparsity, which explains SVM's strong generalization ability in high-dimensional feature spaces.

## Lagrangian dual of hard-margin SVM
In the case of hard-margin SVM, we have a constrained optimization problem where we want to find the parameters $\bold w$ that minimize the objective function subject to the constraint that all training samples are classified correctly with a margin of at least 1. This can be written as:

$$

\min_{\bold w} \frac{1}{2}\|\bold w\|^2 

\;\;\;\;\;\;\;s.t. \;\;\;\;\;\;\; y_i(\bold{w}^{T}\phi(\bold x_i))\ge 1 \;\;\;\;\;\;\; \forall_i
$$

We introduce a Lagrange multiplier for each constraint to apply the Lagrangian method. We call it $\bold a$ and write the Lagrangian as:
$$
L(\bold w,\bold a) = \frac{1}{2}\|\bold w\|^2 - \sum_{i=1}^n a_i(y_i\bold w^T\phi(x_i)-1)
$$
Here, the Lagrange multipliers enforce the constraints by penalizing the objective function for any violations. If a constraint is violated, the corresponding Lagrange multiplier will be non-zero, which will increase the value of the objective function.

We can then form the Lagrangian dual function by minimizing the Lagrangian to the primal variable $\bold w$ while maximizing it to the Lagrange multipliers $\bold a$:

$$
\max_{\bold a\ge\bold 0}\min_{\bold w}L(\bold w, \bold a)
$$ 

Here, $\min_{\bold w}L(\bold w, \bold a)$ is the new optimization problem, where we only need to maximize over the Lagrange multipliers $\bold a$. The solution to this problem gives us the optimal set of Lagrange multipliers, which can be used to derive the optimal set of parameters $\bold w$ for the original problem.

### Explanation of $L(\bold w,\bold a)$
Since $L(\bold w,\bold a)$ must be maximized with respect to $\bold a$, we can interpret $a_i$ as the penalty for violating the $i ^{th}$ constraint. Whenever the $i ^{th}$ constraint is violated, $y_i\bold w^T\phi(\bold x_i)-1$ becomes negative, and maximizing $a_i$ results in adding a large positive number to $\frac{1}{2}\|\bold w\|^2$. Simultaneously, $\bold w$ minimizes $L(\bold w, \bold a)$ by ensuring that the constraints are not violated.

## Lagrangian dual of soft-margin SVM
In the case of soft-margin SVM, our optimization problem and constraints are as follows:

$$
\begin{aligned}
\min_{\bold{w,e}} \quad & \frac{1}{2}\|\bold w\|^2 + C\sum_{i=1}^ne_i\\
\textrm{s.t.} \quad & y_i\bold w^T\phi(\bold x_i)\ge 1-e_i \quad & i=1,2,\dots,n\\
  \quad & e_j\ge0 \quad & j=1,2,\dots,n    \\
\end{aligned}
$$

After introducing Lagrange multipliers for each constraint, we can write our Lagrangian for soft-margin SVM $L(\bold{w,e,a,b})$ as follows:

$$
L(\bold{w,e,a,b}) = \frac{1}{2}\|\bold w\|^2 + C\sum_{i=1}^ne_i - \sum_{i=1}^n a_i(y_i\bold w^T\phi(x_i)-1+e_i)-\sum_{j=1}^{n}b_ie_i
$$

Here, $\bold a \ge 0$ and $\bold b \ge 0$ are Lagrange multipliers.

### Vectorization
If we consider: 

$$
\begin{aligned}
\bold 1=\begin{bmatrix}1&1&\dots&1\end{bmatrix}^T,
\\
\Phi(X)=\begin{bmatrix}\phi(\bold x_1)&\phi(\bold x_2)&\dots&\phi(\bold x_n)\end{bmatrix}^T,
\\

\space \bold{a_{\bold y}} = \begin{bmatrix}a_1y_1&a_2y_2&\dots&a_ny_n\end{bmatrix}^T,
\\
\bold{a_{\bold e}} = \begin{bmatrix}a_1e_1&a_2e_2&\dots&a_ne_n\end{bmatrix}^T,
\end{aligned}
$$
then, we can rewrite $L(\bold{w,e,a,b})$ as follows:

$$
\begin{aligned}
L(\bold{w,e,a,b})=\frac{1}{2}\bold w^T\bold w+C\bold e^T\bold 1-\bold w^T\Phi(X)\bold{a_{\bold y}}+\bold a^T\bold 1 -\bold a^T_{\bold e} \bold 1-\bold e^T\bold b
\end{aligned}
$$

The optimization problem is solved by finding the values of $\bold{w}$ and $\bold{e}$ that minimize $L(\bold{w,e,a,b})$ subject to the constraints that $\bold{a} \ge 0$ and $\bold{b} \ge 0$. The dual problem is then formulated in terms of $\bold{a}$ and solved to obtain the values of $\bold{a}$ that maximize the objective function.

### Optimizing for $\bold{w}$ and $\bold e$


To optimize for $\bold w$ and $\bold e$, we differentiate $L$ with respect to $\bold w$ and $\bold e$ and set the resulting equations equal to zero. For $\bold w$, we obtain:

$$
\bold w = \Phi(X)\bold a_{\bold y}
$$

After differentiating $\bold L$ with respect to $\bold e$ and setting it equal to zero, we get the following:
$$
\frac{\partial L}{\partial e} = C - a - b = 0
$$

After rearranging it, we get the following:

$$
C = a + b
$$

By keeping in mind $\bold{a} \ge 0$ and $\bold{b} \ge 0$, we get the following constraint:

$$
0\le\bold a\le C
$$

Substituting these back into the Lagrangian, we obtain the dual form of the problem:

$$
\begin{align*}
L(\bold{w,e,a,b}) & = \frac{1}{2}\bold w^T\bold w+C\bold e^T\bold 1-\bold w^T\Phi(X)\bold{a_{\bold y}}+\bold a^T\bold 1 -\bold a^T_{\bold e} \bold 1-\bold e^T\bold b
\\ 

L(\bold{w,e,a,b}) & = \frac{1}{2}\bold w^T\Phi(X)\bold{a_{\bold y}} + \bold e^T(\bold a + \bold b)\bold 1 - \bold w^T\Phi(X)\bold{a_{\bold y}} + \bold a^T\bold 1 - \bold a^T_{\bold e} \bold 1 - \bold e^T\bold b \\

L(\bold{w,e,a,b}) & = \bold e^T \bold a + \bold e^T \bold b - \frac{1}{2}\bold w^T\Phi(X)\bold{a_{\bold y}} + \bold a^T\bold 1 - \bold a^T_{\bold e} \bold 1 - \bold e^T\bold b \\

L(\bold{w,e,a,b}) & = \bold e^T \bold a  + \bold e^T \bold b - \frac{1}{2}\bold w^T\Phi(X)\bold{a_{\bold y}} + \bold a^T\bold 1 - \bold e^T \bold a - \bold e^T \bold b \\

L(\bold{w,a}) & = - \frac{1}{2}\bold w^T\Phi(X)\bold{a_{\bold y}} + \bold a^T\bold 1 \\

L(\bold{a}) & = - \frac{1}{2}(\Phi(X)\bold{a_{\bold y}})^T\Phi(X)\bold{a_{\bold y}} + \bold a^T\bold 1 \\

L(\bold{a}) &= - \frac{1}{2}\bold{a_{\bold y}}^T\Phi(X)^T\Phi(X)\bold{a_{\bold y}} + \bold a^T\bold 1 \\

L(\bold{a}) &= \bold a^T\bold 1 - \frac{1}{2}\bold{a_{\bold y}}^TK\bold{a_{\bold y}} \\

\end{align*}
$$

Here, $K = \Phi(X)^T\Phi(X)$ is the Gram Matrix.
 

In step one, we substitute the values of $\bold{w}$ and $\bold{C}$ into the Lagrangian equation $L(\bold{w,e,a,b})$. In step two, we subtract the common terms and open the bracket to get a more simplified equation. Next, we replace $\bold a^T_{\bold e}$ with  $\bold e^T \bold a$, as it's the dot product of vectors $\bold a$ and $\bold e$, and we can write it as $\bold e^T \bold a$ because both are vectors instead of matrices. This allows us to simplify the equation. Now, we cancel out the common terms with opposite signs. Then, we substitute the value of $\bold w$ again, and as we know $(AB)^T = B^T A^T$, so after the substitution, our equation leads to $- \frac{1}{2}\bold{a_{\bold y}}^T\Phi(X)^T\Phi(X)\bold{a_{\bold y}} + \bold a^T\bold 1$, where $\Phi(X)^T\Phi(X)$ is a Gram matrix, also known as a kernel matrix. After substituting $\bold K$ and rearranging, we arrive at the dual form of the problem.

Using these results to eliminate $\bold w$ and $\bold e$, we arrive at the following dual problem:

$$
\begin{aligned}
\max_{\bold a} \quad & L(\bold a)\\
\textrm{s.t.} \quad & 0\le \bold a \le C
\end{aligned}
$$

Here:

$$
L(\bold a) = \bold a^T\bold 1 - \frac{1}{2}\bold a^T_{\bold y}K\bold a_{\bold y}
$$

> **Note:** The computation of the Gram matrix involves only the kernel function and not the explicit computation of the feature map; it can be efficiently computed even for high-dimensional data.

### Prediction
Once the dual variable $\bold a$ is estimated, the prediction $\hat{y}_t$ for $\phi(\bold x_t)$ can be done as follows:

$$
\hat{y}_t = \bold w^T\phi(\bold x_t)=\bold a^T_{\bold y}\Phi(X)^T\phi(\bold x_t)
$$

Learn dual formulation and derive Lagrangian dual function for hard and soft-margin SVM.





Dual Formulation

Learn dual formulation and derive Lagrangian dual function for hard and soft-margin SVM.

Course Overview

Supervised Learning

Detect Cyber Intrusion Using Machine Learning

Clustering

Project: Bag of Visual Words

Generalized Linear Regression

Face Recognition Using Kernel Linear Discriminant

Support Vector Machine

Logistic Regression

Ensemble Learning

Early Stage Diabetes Prediction Using Ensemble Learning

Decoding Dimensions: PCA and Autoencoders

Image Reconstruction Using PCA

Image Colorization using Autoencoders

Colorful Face Generation with VAEs

Appendix

Wrapping Up

Dual Formulation

Why dual formulation?

Lagrangian dual of hard-margin SVM