How do I include the Bias term in the Pegasos algorithm?

Question

How do I include the Bias term in the Pegasos algorithm?

Matthew Martin

2022年2月28日 03:03

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.

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

Topic perceptron machine-learning

Category Data Science

ammirante · Accepted Answer · 2021年9月22日 22:53

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.

How do I include the Bias term in the Pegasos algorithm?

About