2
$\begingroup$

I have been asked to implement the Pegasos algorithm as below. It is similar to the Peceptron algorithm but includes eta and lambda terms. However, there is no bias term below and I don't know how to include it in either the condition or the update. I think the update is just W0 -> W0 + eta*y[i,t], but it should only be updated if the condition is satisfied, and I used the condition below which ignores bias. enter image description here

Any ideas how to include the bias in the condition and update?

$\endgroup$

1 Answer 1

2
$\begingroup$

When you consider the bias term $b$ (scalar), the prediction for an instance $\mathbf{x}$ becames $\langle \mathbf{w},\mathbf{x}\rangle+b$ and the hinge-loss function is defined as $$ \ell((\mathbf{w},b);(\mathbf{x},y))=\text{max}\{0,1-y(\langle \mathbf{w},\mathbf{x}\rangle+b)\} $$

Therefore, you are right! One way to update the bias is $b_{t+1}\leftarrow b_{t}+\eta_{t}y_{t_{i}}$ if $y_{t_{i}}(\langle \mathbf{w}_{t},\mathbf{x}_{t_{i}}\rangle+b_{t_{i}})<1$. You can see other alternatives in section 6 of the original paper.

$\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.