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!



How to inference the dual form of perceptron?
**Disclaimer**: I realize this is a very late response; hopefully, it will be useful to others. Additionally, this is going to be a long answer, as I will try to work from first principles. Don't say I didn't warn you. I will solve for the (slightly more general) case when some errors are allowed as we cannot assume real-world datasets are perfectly linearly separable. However, as you will notice, the addition of an error slack variable term does not really change the derivation by much.


Finally, I only stumbled on this post because I was looking for a solution to this problem as well (but couldn't find any good sources that derived it in detail). Overall, the problem isn't too hard, but certainly not trivial either.


### Framework for linear classifiers


Before we derive the linear program that will allow us to classify data using
perceptrons, recall the general framework for linear classifiers. Let
$\mathcal{H} = \vec{w}^T\vec{x}+b = 0$ be a hyperplane defined in $\mathbb{R}^m$
and the vector $\vec{w}$ be orthogonal to $\mathcal{H}$. Then, the line that
passes through the datapoint $\vec{x}\_i$ and is orthogonal to the hyperplane is
defined by,


\begin{equation}
\tag{1}\label{eq:orthogonal\_line}
 \vec{x} - \vec{x}\_i = a\vec{w}
\end{equation}


The intersection of (\ref{eq:orthogonal\_line}) with the hyperplane is
$\vec{w}^T(a\vec{w} + \vec{x}\_i) + b = 0$, so


\begin{equation}
\tag{2}
 a = -\frac{\vec{w}^T \vec{x}\_i + b}{\vec{w}^T \vec{w}}
\end{equation}


meaning the projection of $\vec{x}\_i$ onto a point $\vec{z} \in \mathcal{H}$ is,


\begin{equation}
\tag{3}\label{eq:projection}
 P\_{\vec{z}}(\vec{x}\_i) = a\vec{w} + \vec{x}\_i = \left( -\frac{\vec{w}^T \vec{x}\_i +
 b}{\lVert \vec{w} \rVert^2} \right) \vec{w} + \vec{x}\_i
\end{equation}


By computing the norm of (\ref{eq:projection}),


\begin{equation}
\tag{4}
 \lVert P\_{\vec{z}}(\vec{x}\_i) \rVert = \left\lVert \left( -\frac{\vec{w}^T
 \vec{x}\_i + b}{\lVert \vec{w} \rVert^2} \right) \vec{w} + \vec{x}\_i \right\rVert =
 \left| - \frac{\vec{w}^T \vec{x}\_i + b}{\lVert \vec{w} \rVert} + \vec{x}\_i \right|
\end{equation}


and plugging it into the law of cosines formula,


\begin{equation}
\begin{aligned}
 \lVert P\_{\vec{z}}(\vec{x}\_i) - \vec{x}\_i \rVert^2
 &= \lVert \vec{x}\_i \rVert^2 + \lVert P\_{\vec{z}}(\vec{x}\_i) \rVert^2 - 2 \lVert
 \vec{x}\_i \rVert \rVert P\_{\vec{z}}(\vec{x}\_i) \lVert \cos(\theta) \\
 &= \lVert \vec{x}\_i \rVert^2 + \lVert P\_{\vec{z}}(\vec{x}\_i) \rVert^2 - 2 \lVert
 \vec{x}\_i \rVert \lVert P\_{\vec{z}}(\vec{x}\_i) \rVert \frac{\vec{x}\_i \cdot
 P\_{\vec{z}}(\vec{x}\_i)}{\lVert \vec{x}\_i \rVert \lVert P\_{\vec{z}}(\vec{x}\_i)
 \rVert} \\
 &= |\vec{x}\_i|^2 + \left| \left( \frac{\vec{w}^T \vec{x}\_i + b}{\lVert \vec{w}
 \rVert} \right)^2 + (\vec{x}\_i)^2 - 2 \left( \frac{\vec{w}^T \vec{x}\_i +
 b}{\lVert \vec{w} \rVert} \vec{x}\_i \right) \right| - 2 \vec{x}\_i \left(
 -\frac{\vec{w}^T \vec{x}\_i + b}{\lVert \vec{w} \rVert} + \vec{x}\_i \right) \\
 &= |\vec{x}\_i|^2 + \left| \frac{\vec{w}^T \vec{x}\_i + b}{\lVert \vec{w} \rVert}
 \right|^2 + |\vec{x}\_i|^2 - 2 \left| \frac{\vec{w}^T \vec{x}\_i + b}{\lVert \vec{w}
 \rVert} \vec{x}\_i \right| + 2 \left| \frac{\vec{w}^T \vec{x}\_i + b}{\lVert \vec{w}
 \rVert} \vec{x}\_i \right| - 2 | \vec{x}\_i |^2 \\
 &= \left| \frac{\vec{w}^T \vec{x}\_i + b}{\lVert \vec{w} \rVert} \right|^2
\end{aligned}
\tag{5}
\end{equation}


we can determine the distance of the point $\vec{x}\_i$ from its projection
$P\_{\vec{z}}(\vec{x}\_i)$ as,


\begin{equation}
\tag{6}\label{eq:margin\_distance}
 D(\vec{x}\_i, P\_{\vec{z}}(\vec{x}\_i)) = \sqrt{\lVert P\_{\vec{x}}(\vec{x}\_i) -
 \vec{x}\_i \rVert^2} = \sqrt{\left| \frac{\vec{w}^T \vec{x}\_i + b}{\lVert \vec{w}
 \rVert} \right|^2} = \frac{\lvert \vec{w}^T\vec{x}\_i + b \rvert}{\lVert \vec{w}
 \rVert} = \lvert \vec{w}^T \vec{x}\_i + b \rvert
\end{equation}


when $\lVert \vec{w} \rVert = 1$.


### Perceptron objective + constraints


Now consider that we are given a set of
training of examples, $X = \{(\vec{x}\_i, y\_i)\}\_{i=1}^{n}$, for a binary
classification task. We say that $X$ is linearly seperable if there exists a
hyperplane $\mathcal{H}$, such that


\begin{equation}
\tag{7}
 y\_i =
 \begin{cases}
 +1 & \text{if}~\vec{w}^T\vec{x}\_i + b \geq 0 \\
 -1 & \text{if}~\vec{w}^T\vec{x}\_i + b < 0
 \end{cases}
\end{equation}


Here, $\vec{w} \in \mathbb{R}^m$ is a weight vector applied to each datapoint
$\vec{x}\_i \in \mathbb{R}^{m}$ and $b$ is the bias. Using
(\ref{eq:margin\_distance}) we define a margin $\gamma\_i$ achieved by $\vec{w}$ on
the $i$-th example as,


\begin{equation}
\tag{8}
 \gamma\_i(\vec{w}) = y\_i(\vec{w}^T\vec{x}\_i + b) 
\end{equation}


Although any margin will work, we want to find the maximum margin achieveable on
all datapoints $\vec{x}\_i$,


\begin{equation}
\tag{9}
 \gamma^\* = \max\_{\vec{w} \in \mathbb{R}^m} \min\_i \gamma\_i(\vec{w})
\end{equation}


such that each example is classified correctly (aka $y\_i = \text{sign}(\vec{w}^T
\vec{x}\_i + b)$ or $\gamma\_i > 0$). However, this formulation fails to take into
account that, on arbitrary real-world datasets, misclassifications are present
(whenever $\gamma\_i \leq 0$); hence, we cannot assume the data is perfectly
linearly seperable. To fix this, we introduce a penalty known as the
**margin slack variable** for each example $(\vec{x}\_i, y\_i)$ relative to
the hyperplane $\mathcal{H}$ and the target margin $\gamma$,


\begin{equation}
\tag{10}
 \xi((\vec{x}\_i, y\_i), \mathcal{H}, \gamma) = \xi\_i = \max\{0, \gamma -
 y\_i(\vec{w}^T \vec{x}\_i + b)\}
\end{equation}


Here, $\xi\_i$ measures how much a point fails to have a margin of $\gamma$ from
$\mathcal{H}$, implying that if $\xi\_i > \gamma$, then $\vec{x}\_i$ is
misclassified by the boundary $\mathcal{H}$. This forces the constraint $\xi\_i
\geq \gamma - y\_i(\vec{w}^T\vec{x}\_i + b)$, or $y\_i(\vec{w}^T\vec{x}\_i + b) + \xi\_i
\geq \gamma$. Note that points that are correctly classified have $\xi\_i = 0$.
Now that we have the objective function and constraints, we can write the
optimization problem as,


\begin{equation}
\begin{aligned}
 & \underset{\vec{w},b}{\text{minimize}} && - \sum\_{i \in \mathcal{M}}
 y\_i(\vec{w}^T \vec{x}\_i + b) \\
 & \text{subject to} && y\_i(\vec{w}^T \vec{x}\_i + b) + \xi\_i \geq \gamma & 
 i=1,\dots,n \\
 &&& \xi\_i \geq 0 & i=1,\dots,n
\end{aligned}
\tag{11}
\end{equation}


where instead of maximizing the number of correct classifications, we minimize
over the set of misclassified points, $\mathcal{M}$. Converting it to the
standard form,


\begin{equation}
\begin{aligned}
 & \underset{\vec{w},b}{\text{minimize}} && - \sum\_{i \in \mathcal{M}}
 y\_i(\vec{w}^T \vec{x}\_i + b) \\
 & \text{subject to} && \gamma - \xi\_i - y\_i(\vec{w}^T \vec{x}\_i + b) \leq 0 & 
 i=1,\dots,n \\
 &&& -\xi\_i \leq 0 & i=1,\dots,n
\end{aligned}
\tag{12}
\end{equation}


and plugging it into the generalized Lagrangian,


\begin{equation}
\tag{13}\label{eq:lagrangian}
 L(\vec{w},b,\vec\xi,\vec\alpha,\vec\beta) = -\sum\_{i \in \mathcal{M}}
 y\_i(\vec{w}^T\vec{x}\_i + b) + \sum\_{i=1}^{n} \alpha\_i(\gamma - \xi\_i -
 y\_i(\vec{w}^T\vec{x}\_i + b)) - \sum\_{i=1}^{n} \beta\_i \xi\_i
\end{equation}


allows us to solve the dual optimization problem,


\begin{equation}
\tag{14}
 \max\_{\vec\alpha,\vec\beta \colon \alpha\_i,\beta\_i \geq 0} L\_D(\vec\alpha,\vec\beta)
\end{equation}


where $L\_D(\vec\alpha,\vec\beta)$ is the Lagrangian dual, defined by,


\begin{equation}
\tag{15}\label{eq:lagrangian\_dual}
 L\_D(\vec\alpha,\vec\beta) = \min\_{\vec{w},b,\vec\xi} L(\vec{w}, b, \vec\xi,
 \vec\alpha, \vec\beta)
\end{equation}


### Solving the Lagrangian


To compute the simplified expression for (\ref{eq:lagrangian\_dual}), we take the
derivative of $L(\vec{w},b,\vec\xi,\vec\alpha,\vec\beta)$ with respect to our
variables of interest to solve for the KKT stationary conditions,


\begin{align}
 \frac{\partial}{\partial\vec{w}} L(\vec{w},b,\vec\xi,\vec\alpha,\vec\beta) &=
 -\sum\_{i \in \mathcal{M}} y\_i \vec{x}\_i - \sum\_{i=1}^{n} \alpha\_i y\_i \vec{x}\_i
 = 0 &&\implies -\sum\_{i \in \mathcal{M}} y\_i \vec{x}\_i = \sum\_{i=1}^{n}
 \alpha\_i y\_i \vec{x}\_i \tag{16}\label{eq:stationary\_w} \\
 \frac{\partial}{\partial b} L(\vec{w},b,\vec\xi,\vec\alpha,\vec\beta) &=
 -\sum\_{i=1}^{n} y\_i - \sum\_{i=1}^{n} \alpha\_i y\_i = 0 &&\implies
 -\sum\_{i=1}^{n} y\_i = \sum\_{i=1}^{n} \alpha\_i y\_i \tag{17}\label{eq:stationary\_b} \\
 \frac{\partial}{\partial \xi\_i} L(\vec{w},b,\vec\xi,\vec\alpha,\vec\beta) &=
 - \alpha\_i - \beta\_i = 0 &&\implies \alpha\_i + \beta\_i = 0
 \tag{18}\label{eq:stationary\_xi}
\end{align}


and substitute them into (\ref{eq:lagrangian}),


\begin{equation}
\begin{aligned}
 L(\vec{w},b,\vec\xi,\vec\alpha,\vec\beta)
 &= -\sum\_{i \in \mathcal{M}} y\_i(\vec{w}^T\vec{x}\_i + b) + \sum\_{i=1}^{n}
 \alpha\_i(\gamma - \xi\_i - y\_i(\vec{w}^T\vec{x}\_i + b)) - \sum\_{i=1}^{n} \beta\_i
 \xi\_i \\
 &= -\sum\_{i \in \mathcal{M}} y\_i\vec{w}^T\vec{x}\_i - \sum\_{i=1}^{n} y\_i b +
 \sum\_{i=1}^{n} \alpha\_i \gamma -\sum\_{i=1}^{n} \alpha\_i \xi\_i - \sum\_{i=1}^{n}
 \alpha\_i y\_i \vec{w}^T \vec{x}\_i - \sum\_{i=1}^{n} \alpha\_i y\_i b -
 \sum\_{i=1}^{n} \beta\_i \xi\_i \\
 &= \sum\_{i=1}^{n} \alpha\_i y\_i \vec{w}^T \vec{x}\_i + \sum\_{i=1}^{n} \alpha\_i y\_i
 b + \sum\_{i=1}^{n} \alpha\_i \gamma - \sum\_{i=1}^{n} \alpha\_i y\_i \vec{w}^T
 \vec{x}\_i - \sum\_{i=1}^{n} \alpha\_i y\_i b - \sum\_{i=1}^{n} (\alpha\_i + \beta\_i)
 \xi\_i \\
 &= \sum\_{i=1}^{n} \alpha\_i \gamma = \sum\_{i=1}^{n} \alpha\_i (\xi\_i +
 y\_i(\vec{w}^T\vec{x}\_i + b)) 
\end{aligned}
\tag{19}
\end{equation}


The Lagrangian dual is therefore,


\begin{equation}
\tag{20}
 L\_D(\vec\alpha,\vec\beta) = \min\_{\vec{w},b,\vec{\xi}} \left[ \sum\_{i=1}^{n}
 \alpha\_i \left( \xi\_i + y\_i(\vec{w}^T\vec{x}\_i + b) \right) \right]
\end{equation}


meaning the dual optimization problem can be written as,


\begin{equation}
\begin{aligned}
 &\underset{\vec\alpha}{\text{maximize}} && \min\_{\vec{w},b,\vec\xi} \left[
 \sum\_{i=1}^{n} \alpha\_i \left( \xi\_i + y\_i(\vec{w}^T\vec{x}\_i + b) \right)
 \right] \\
 &\text{subject to} && \alpha\_i \geq 0, \quad -\sum\_{i=1}^{n} y\_i =
 \sum\_{i=1}^{n} \alpha\_i y\_i & i = 1,\dots,n
\end{aligned}
\tag{21}\label{eq:dual}
\end{equation}


since the objective function in the dual form does not depend on $\vec\beta$.


### Deriving dual form


Now that we have $\vec\alpha^\*$ (the solution to the perceptron dual), we can recover the optimal $\vec{w}^\*$ and $b^\*$ by using the KKT conditions. From condition 5 (complementary slackness), we have that $\forall i$,


\begin{align}
 \alpha\_i^\* \left( \gamma - \xi\_i^\* - y\_i({\vec{w}^\*}^T \vec{x}\_i + b^\*) \right)
 &= 0 \tag{22}\label{eq:complementary\_alpha} \\
 -\beta\_i^\* \xi\_i^\* &= 0 \tag{23}\label{eq:complementary\_beta}
\end{align}


By combining (\ref{eq:stationary\_xi}) and (\ref{eq:complementary\_beta}), notice
that $\alpha\_i^\* \xi\_i^\* = 0$ meaning that $\xi\_i^\* = 0$ for any value of
$\alpha\_i^\*$. Then, if $\forall i, \alpha\_i^\* > 0$, by
(\ref{eq:complementary\_alpha}),


\begin{equation}
\begin{aligned}
 y\_i({\vec{w}^\*}^T \vec{x}\_i + b^\*) &= \gamma - \xi\_i^\* \\
 y\_i {\vec{w}^\*}^T \vec{x}\_i + y\_i b^\* &= \gamma \\
 y\_i {\vec{w}^\*}^T \vec{w}^\* \vec{x}\_i &= (\gamma - y\_i b^\*) \vec{w}^\* \\
 \frac{y\_i \vec{x}\_i}{\gamma - y\_i b^\*} &= \vec{w}^\* \\
 \frac{y\_i \vec{x}\_i}{\gamma \pm b^\*} &= \vec{w}^\* \\
 \vec{w}^\* &= y\_i \vec{x}\_i
\end{aligned}
\tag{24}
\end{equation}


where $\gamma - y\_i b^\* \equiv \gamma \pm b^\*$ is some constant scaling factor
since $y\_i \in \{-1,+1\}$. We remove $\gamma \pm b^\*$ as it will not affect the
optimal of $\vec{w}$. By applying (\ref{eq:stationary\_b}), the optimal normal
vector $\vec{w}^\*$ becomes a linear combination taken over all training samples,


\begin{equation}
\tag{25}\label{eq:optimal\_w}
 \vec{w}^\* = \sum\_{i=1}^{n} y\_i \vec{x}\_i = \sum\_{i=1}^{n} \alpha\_i^\* y\_i
 \vec{x}\_i
\end{equation}


where $\alpha\_i^\*$ represents the number of times $\vec{x}\_i$ was misclassified.
Similarly for $b^\*$,


\begin{equation}
\begin{aligned}
 y\_i({\vec{w}^\*}^T \vec{x}\_i + b^\*) &= \gamma - \xi\_i^\* \\
 {\vec{w}^\*}^T \vec{x}\_i + b^\* &= \frac{\gamma}{y\_i} \\
 b^\* &= \frac{\gamma}{y\_i} - {\vec{w}^\*}^T \vec{x}\_i \\
 b^\* &= y\_i - {\vec{w}^\*}^T \vec{x}\_i
\end{aligned}
\tag{26}\label{eq:optimal\_b}
\end{equation}


where we remove the constant $\gamma$ as it does not affect the optimal of $b$
and $\frac{1}{y\_i} \equiv y\_i$ since $y\_i \in \{-1,+1\}$. The final decision
function is then,


\begin{equation}
\begin{aligned}
 \hat{y}(\vec{x}\_j) &= \text{sign} ({\vec{w}^\*}^T \vec{x}\_j + b^\*) \\
 &= \text{sign} \left[ \left( \sum\_{i=1}^{n} \alpha\_i^\* y\_i \vec{x}\_i
 \right)^T \vec{x}\_j + b^\* \right] \\
 &= \text{sign} \left[ \sum\_{i=1}^{n} \alpha\_i^\* y\_i \kappa(\vec{x}\_i,
 \vec{x}\_j) + b^\* \right]
\end{aligned}
\tag{27}
\end{equation}


where $\vec\alpha^\*$ is the solution of (\ref{eq:dual}), $b^\*=y\_i-\sum\_{i=1}^{n}
\alpha\_i^\* y\_i \kappa(\vec{x}\_i, \vec{x}\_j)$ is solved by substituting in
(\ref{eq:optimal\_w}) into (\ref{eq:optimal\_b}), and $\kappa(\cdot,\cdot)$
represents some non-negative semidefinite kernel function between two samples
(an inner product between samples in a high-dimensional space). However, instead
of directly solving for $\vec\alpha^\*$, we iteratively update $\alpha\_i, b$ till
some stopping criterion is met (i.e. a certain number of iterations is reached,
or no mistakes are made for all training examples). This is performed via the
kernelized version of the algorithm [1,2],
where instead of updating $\vec{w} = \vec{w} + y\_i \vec{x}\_i$ (as done in the
gradient descent formulation), we update $\alpha\_i = \alpha\_i + 1$ for each
example $\vec{x}\_i$. Note that these two procedures are equivalent, and thus,
will produce the same solution.


### References


1. <https://en.wikipedia.org/wiki/Kernel_perceptron> (Good overview)
2. [https://www.cs.umb.edu/~dsim/slidesPER.pdf](https://www.cs.umb.edu/%7Edsim/slidesPER.pdf) (Really useful)
3. <http://people.csail.mit.edu/dsontag/courses/ml12/slides/lecture3.pdf>
4. <https://ahmadzadeh.iut.ac.ir/sites/ahmadzadeh.iut.ac.ir/files//files_course/2_linear_classifiers_0.pdf>
5. [https://cseweb.ucsd.edu/~dasgupta/250B/duality-convex-handout.pdf](https://cseweb.ucsd.edu/%7Edasgupta/250B/duality-convex-handout.pdf)


