0
$\begingroup$

I was referring SVM section of Andrew Ng's course notes for Stanford CS229 Machine Learning course. On page 22, he says:

Lagrangian for optimization problem:

$$\mathcal{L}(w,b,\alpha)=\frac{1}{2}\Vert w\Vert^2-\sum_{i=1}^n \alpha_i[y^{(i)}(w^Tx^{(i)}+b)-1] \quad\quad\quad \text{...equation (1)} $$

To find dual of the problem, we set derivative of $\mathcal{L}$ with respect to $w$ to zero, to get:

$$w=\sum_{i=1}^n\alpha_iy^{(i)}x^{(i)}\quad\quad\quad \text{...equation (2)}$$

Putting $w$ from equation (2) in equation (1), we get:

$$\mathcal{L}(w,b,\alpha)=\sum_{i=1}^n\alpha_i-\color{red}{\frac{1}{2}}\sum_{i,j=1}^ny^{(i)}y^{(j)}\alpha_i\alpha_j(x^{(i)})^Tx^{(j)}-b\sum_{i=1}^n\alpha_iy^{(i)}$$

But I got following putting $w$ from equation (2) in equation (1):

$$\begin{align} \mathcal{L}(w,b,\alpha) & =\frac{1}{2}\left( \sum_{i=1}^n\alpha_iy^{(i)}x^{(i)} \right)^2-\sum_{i=1}^n \alpha_i\left[y^{(i)}\left(\left( \sum_{j=1}^n\alpha_jy^{(j)}x^{(j)} \right)x^{(i)}+b\right)-1\right] \\ & =\frac{1}{2}\left( \sum_{i=1}^n\alpha_iy^{(i)}x^{(i)} \right)^2-\sum_{i,j=1}^n \alpha_i\left[y^{(i)}\left(\left( \alpha_jy^{(j)}x^{(j)} \right)x^{(i)}+b\right)-1\right] \\ & =\frac{1}{2}\left( \sum_{i=1}^n\alpha_iy^{(i)}x^{(i)} \right)^2-\sum_{i,j=1}^n \left[ y^{(i)}y^{(j)}\alpha_i \alpha_j\left(x^{(i)}\right)^Tx^{(j)} + \alpha_i y^{(i)} b -\alpha_i \right] \\ & =\color{blue}{\frac{1}{2}\left( \sum_{i=1}^n\alpha_iy^{(i)}x^{(i)} \right)^2}+\sum_{i=1}^n\alpha_i-\sum_{i,j=1}^ny^{(i)}y^{(j)}\alpha_i\alpha_j(x^{(i)})^Tx^{(j)}-b\sum_{i=1}^n\alpha_iy^{(i)} \end{align}$$

I didn't get from where Andrew Ng got red colored $\color{red}{\frac{1}{2}}$ and why didn't he got blue colored $\color{blue}{\frac{1}{2}\left( \sum_{i=1}^n\alpha_iy^{(i)}x^{(i)} \right)^2}$ (, which I got in my simplification). Where did I make mistake?

$\endgroup$

1 Answer 1

1
$\begingroup$

Assuming $x^{(i)} \in \mathbb{R}^{dx1}$ with $d>0$ we have:

$$ \frac{1}{2} \left\lVert \sum_{i=1}^n\alpha_iy^{(i)}x^{(i)} \right\rVert ^2 = \frac{1}{2}\left( \sum_{i=1}^n\alpha_iy^{(i)}x^{(i)} \right)^T \left( \sum_{i=1}^n\alpha_iy^{(i)}x^{(i)} \right) = \frac{1}{2} \sum_{i,j=1}^n y^{(i)} y^{(j)} \alpha_i \alpha_j (x^{(i)})^T x^{(j)} $$

You need to be careful here, $x^{(i)}$ is a feature vector, hence you need to make sure that you respect the dot product rules in $\mathbb{R}^{dx1}$. The further right hand side of the above comes from developing the dot product (the alpha and y are scalars).

Thus:

$$ \frac{1}{2} \left\lVert \sum_{i=1}^n\alpha_iy^{(i)}x^{(i)} \right\rVert ^2 - \sum_{i,j=1}^n y^{(i)} y^{(j)} \alpha_i \alpha_j (x^{(i)})^T x^{(j)} = \color{red}{\frac{1}{2}} \sum_{i,j=1}^n y^{(i)} y^{(j)} \alpha_i \alpha_j (x^{(i)})^T x^{(j)} + \color{red}{(-1)} \sum_{i,j=1}^n y^{(i)} y^{(j)} \alpha_i \alpha_j (x^{(i)})^T x^{(j)} $$

which ultimately gives:

$$ \frac{1}{2} \left\lVert \sum_{i=1}^n\alpha_iy^{(i)}x^{(i)} \right\rVert ^2 - \sum_{i,j=1}^n y^{(i)} y^{(j)} \alpha_i \alpha_j (x^{(i)})^T x^{(j)} = - \frac{1}{2} \sum_{i,j=1}^n y^{(i)} y^{(j)} \alpha_i \alpha_j (x^{(i)})^T x^{(j)} $$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.