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$

1 Answer 1

3
$\begingroup$

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.