3
$\begingroup$

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!

$\endgroup$

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.