The model of perceptron is a linear binary classifier, which is $f(x)=\mathbb{sign}(w^Tx+b)$. $x$ is the datapoint as $w$ as well as $b$ are the parameters.

The cost function of Primal Perceptron is $$\min\limits_{w,b}-\sum_{x_i\in M}{y_i\left(w^Tx_i+b\right)}$$.

Where $M$ means the datapoints set where some points is misclassified that satisfied $y_i(w^Tx_i+b)\le0$. And $y_i \in \{-1,+1\}$ is the label(target) of $x_i$, which is in the output spaces.

We can use SGD algorithm to update the parameters $w$ and $b$ with $w \leftarrow w+\eta y_ix_i,b\leftarrow \eta y_i$. Finally, we could get $w=\sum_{i=1}^N\alpha_iy_ix_i,b=\sum_{i=1}^N\alpha_iy_i$, if we let $\alpha_i = n_i\eta$ and the original value of $(w,b)$ is $(0,0)$. And $n_i$ means the counts where datapoint $(x_i,y_i)$ is misclassified.

So we can get the dual form of perceptron. $$f(x)=sign\left(\sum_{j=1}^N\alpha_jy_jx_j+b\right)$$.

Using that $\alpha_i \leftarrow \alpha_i+\eta,b\leftarrow b+\eta y_i$ to update.

Generally, We can get the dual form of an constrained optimization problem with Lagrange duality. But I failed to inferene the dual form of perceptron using Lagrange duality. It seems that this form is obtained directly through computing the final optimal solution. As a noob to operation reaserch, I am confused about this process. So could you guys explian the theoretical basis behind this process to me? Thanks!


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.