2
$\begingroup$

I have an assignment in linear programming and this question was asked: given an input of two data sets $P_1,P_2$ containing points $(x,y)$, create a linear program that finds an equation of a line the separates between the two data sets.

Now I saw in Wikipedia the article about linear separability and I didn't understand what are the variables of $w_1,w_2,\ldots,w_n$ stand for, and why does their algorithm work. If anyone could clarify this for me it would be great.

$\endgroup$
0

1 Answer 1

2
$\begingroup$

The general equation of a line in the plane is $$ ax + by = c. $$ (The equation $y = ax + b$ cannot handle vertical lines.) This line separates the plane into two parts: those satisfying $ax+by > c$, and those satisfying $ax+by < c$. Your two datasets are linearly separable if there exist $a,b,c$ such that all points in $P_1$ satisfy $ax+by > c$, and all points in $P_2$ satisfy $ax+by < c$. (If all points in $P_1$ satisfy $ax+by<c$ and all points in $P_2$ satisfy $ax+by>c$, then we can negate $a,b,c$ to get to the situation above.)

In order to find $a,b,c$ using linear programming, we need to replace the strict inequalities $>,<$ with non-strict inequalities $\ge,\le$. The idea is the for small enough $\epsilon>0$, the points in $P_1$ would actually satisfy $ax+by \geq c+\epsilon$, and the points in $P_2$ would satisfy $ax+by \leq c-\epsilon$. While we don't know $\epsilon$, if we multiply the two inequalities by $1/\epsilon$, we effectively make $\epsilon$ equal to $1$. Therefore we look for $a,b,c$ such that $ax+by \geq c+1$ for all points in $P_1$, and $ax+by \leq c-1$ for all points in $P_2$. This is a linear program, which can be solved using standard algorithms.

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