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