# How to inference the dual form of perceptron?

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!

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,

$$$$\tag{1}\label{eq:orthogonal_line} \vec{x} - \vec{x}_i = a\vec{w}$$$$

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

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

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

$$$$\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$$$$

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

$$$$\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|$$$$

and plugging it into the law of cosines formula,

\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}

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

$$$$\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$$$$

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

$$$$\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}$$$$

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,

$$$$\tag{8} \gamma_i(\vec{w}) = y_i(\vec{w}^T\vec{x}_i + b)$$$$

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

$$$$\tag{9} \gamma^* = \max_{\vec{w} \in \mathbb{R}^m} \min_i \gamma_i(\vec{w})$$$$

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$$,

$$$$\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)\}$$$$

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{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}

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{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}

and plugging it into the generalized Lagrangian,

$$$$\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$$$$

allows us to solve the dual optimization problem,

$$$$\tag{14} \max_{\vec\alpha,\vec\beta \colon \alpha_i,\beta_i \geq 0} L_D(\vec\alpha,\vec\beta)$$$$

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

$$$$\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)$$$$

### 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{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}

The Lagrangian dual is therefore,

$$$$\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]$$$$

meaning the dual optimization problem can be written as,

\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}

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{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}

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,

$$$$\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$$$$

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

\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}

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{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}

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.