0
$\begingroup$

The function $f(w,b) = \frac{1}{2} ||w||^2$ is our objective function while our constraints are all the correct classifications of the data points expressed as $g(w,b) = \sum_{i=1}^{l} (y_i (x_i \cdot w_i+b)-1)$, where $l$ is the number of data points.

The Lagrange function is therefore: $$L(w,b) = \frac{1}{2} ||w||^2 - \sum_{i=1}^{l} (a_i (y_i (x_i \cdot w+b)-1))$$ Taking the derivatives to determine the minimum of the Langrange function: $$\frac{dL}{dw} = w - \sum_{i=1}^{l} (a_i y_i x_i)$$ $$\frac{dL}{db} = - \sum_{i=1}^{l} (a_i y_i)$$ Since $\alpha$,also called a slack variable, cancels out like so if we multiply it with $w$ and $b$: $$dst = \frac{\text{hyperplane}}{\text{norm of point}} = \frac{y_i (w \cdot x+b)}{||w||} = \frac{\alpha (w \cdot x)y_i+\alpha b}{\alpha ||w||}$$

Here comes the weird part. I accidentally found out that for linearly separable data, one can simply strive to minimize the hinge loss function, which returns 0 when the predicted value of $y$ equals $y$ or in other terms and use gradient descent with the gradients of the Langrage function to minimize it: $$hinge loss = \begin{cases} 0 & \text{if } y_i (w \cdot x+b) \geq 1 \\ 1-y_i (w \cdot x+b) & \text{otherwise} \end{cases}$$ EDIT: I also just saw that the constraints are basically hinge loss if $a_i$ is $1$ when the point $i$ is on the support vector and $0$ otherwise.

So why does my code, in which I replace $\alpha$ with the hinge loss function, work when using gradient descent. What is the correlation between the scalar $a_i$, the hinge loss and the Langrage function? I took the derivatives of the Langrange for gradient descent and corrected the weights and bias with those derivatives and not with the derivatives of the hinge loss function, which is how I am used to doing it with e.g. MSE. I just stumbled upon a model that classified accurately and do not know why this works. Here is the code if necessary:

class SVM:
    def __init__(self, learning_rate=0.0000001, C=1, num_epochs=100):
        #initialisation of vars [...]

    def train(self, x, y):
        self.w = np.zeros(len(x[0]))
        for _ in range(self.num_epochs):
            for i in range(len(x)):
                self.w = self.w - self.learning_rate * self.dLdw(self.w, y[i], x[i])
                self.b = self.b - self.learning_rate * self.dLdb(y[i], x[i])

    def predict(self, x):
        return np.sign(np.dot(x, self.w) + self.b)

    def dLdw(self, w, y, x):
        return w - self.C * y * x * self.hinge_loss(y, w, self.b, x)

    def dLdb(self, y, x):
        return -self.C * y * self.hinge_loss(y, self.w, self.b, x)

    def dLda(self, w, b, x, y):
        return y * (-1 * self.hinge_loss(y, w, b, x))

    def hinge_loss(self, y, w, b, x):
        return np.maximum(0, 1 - y * (w.dot(x) + b))

I've seen this answer but to me it still does not explain why I can replace $a_i$ with the hinge loss function.

$\endgroup$

0

Your Answer

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

Browse other questions tagged or ask your own question.