0
$\begingroup$

GOAL: I want create a simple linear programming model that can be used to classify new data based off of a found hyperplane. In this particular case I have two classes and I'm given a data set in which the data is already classified.

ATTEMPT:

So I have that $x'$, $x''$ are given data and my objective is to find a "line" separating the data.

When I say I desire a "line" separating the data, what I actually mean is a vector $$a=[a_0, a_1, ..., a_n]$$ such that $$\sum_{i=1}^{n} a_i x_i = a_0$$ with the property that one class is on one side of the line and the other class is on the other side.

So far I have come up with the following thought process..

$x'$ is on one side if $$\sum_{i=1}^{n} a_{i}x'_{i} > a_{0}$$

$x''$ is on the other side if $$\sum_{i=1}^{n} a_{i}x''_{i} < a_{0}$$

We can scale up or down such an algebraic expression; the hyperplane stays the same.

So, $$\sum a_{i}x'_{i} \geq a_{0} + 1$$ and $$\sum a_{i}x''_{i} \leq a_{0} - 1$$

For each point $x'$ of class A, introduce $y'_{i} \geq 0$, where $$y'_{i} \geq a_{0} + 1 - \sum a_{i}x'_{i}$$

Similarly for each point $x''$ of B, introduce $y''_{i} \geq 0$, where

$$y''_{i} \geq \sum a_{i}x''_{i} - a_{0}+1$$

Then recall $x'$, $x''$ are data given and we are looking for $a$, $y'$, $y''$

Now I try to minimize each of $y'$, and $y''$

I obtain the linear program

\begin{array}{ll@{}ll} \text{minimize} & \displaystyle \sum_{i \in A} & y'_{i} + \displaystyle \sum_{i \in B} y''_{i} \\ \text{subject to} & y'_{i} &\geq a_{0} + 1 - \sum_{j=1}^{n} a_{j}x'_{j} &\forall i \in A\\ & y''_{i} &\geq \sum_{j=1}^{n} a_{j} x''_{j} - a_{0} + 1 &\forall i \in B\\ & a_{i} &\in \mathbb{R} &\forall i\in A \cup B\\ & y'_{i} &\geq 0 &\forall i \in A\\ & y''_{i} &\geq 0 &\forall i \in B\\ \end{array}

Once I have the vector $a$, to classify a new point $z$ I just compute $$\sum a_{i}z_{i} - a_{0}\text{,}$$ which is is either positive or negative, indicating $z$ belongs to cluster A or cluster B.

QUESTIONS:

  1. I'm struggling to determine the correctness of this model. Can this be confirmed?
  2. It's clear that to avoid misclassification, a better hyperplane would maximize the distance from the planes to each class (like a support vector machine). How can my current model be extended to do this?
$\endgroup$
0
$\begingroup$
  1. The proposed model works as expected.

  2. To avoid chance of misclassification by finding a better hyperpland that maximizes the distance from the planes to each class (like a SVM) can be done in the following way if we assume the data is linearly separable:

$minimize: \sum_{j=1}^{p}( \vec{w}_{j}^{+} + \vec{w}_{j}^{-}) $

Constraints:

  • $(\vec{w}^T\vec{x}_{j})y_j \geq 1 - \epsilon _{j}, \forall j$
  • $w_{i}^{+}, w_{i}^{-}, \epsilon_{i} \geq 0$

Where $|\vec{w}|$ is the distance from the hyperplane to a class, and $w = w^+ - w^-$

Note this is equivalent to the quadratic support vector machine approach but instead of using the L2 norm for distance we use the L1 norm

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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