0
$\begingroup$

$a,x_i \in \mathbb{R}^p, b \in \mathbb{R}$. Consider the following two systems of linear inequality:

\begin{equation}\label{eq:eq1} \begin{cases} \langle a, x_i \rangle + b > 0&\text{if }y_i = 1 \\ \langle a, x_i \rangle + b < 0&\text{if }y_i = -1 \end{cases} \end{equation} \begin{equation}\label{eq:eq2} \begin{cases} \langle a, x_i \rangle + b \ge 1&\text{if }y_i = 1\\ \langle a, x_i \rangle + b \le -1&\text{if }y_i = -1 \end{cases} \end{equation} The question is if two systems of linear inequality are equivalent.
It is easy to see that any a and b satisfying the system in equation (2) will also satisfy the system in (1). However, how do I prove that a and b satisfying the system in (1) will also satisfy the system in (2).

Note: The statement is from here. It is Remark 1 on page 2. I just don't quite understand their explanation.

$\endgroup$

2 Answers 2

1
$\begingroup$

Firstly, please notice that the link you shared is not saying a point $x_i$ satisfying the first set satisfies the second. Instead, it says that if you write such a classification in the $1^{st}$ set, and if there is a feasible solution then the $2^{nd}$ set has a feasible solution too.

The reason we do such a transformation is that a linear model can't solve strictly greater/larger condition.

I am attaching a motivating real life example as an image below.

Motivating Example

$\endgroup$
2
  • $\begingroup$ can you please give me the source for the image? $\endgroup$
    – abuchay
    May 2, 2018 at 15:16
  • $\begingroup$ It's my work in progress. I just wanted to show you a practical application. You can always use this trick for linear models with similar settings. $\endgroup$ May 2, 2018 at 21:08
0
$\begingroup$

They are not equivalent. There is no assumption about $b$. So $⟨a,x_i⟩+b$ can be i.e. $0.5$ when $y_i = 1$ and not fulfill the second condition. I think you should give more details about $a$ and $b$ to have an exact answer.

$\endgroup$
2
  • $\begingroup$ I updated my question. $\endgroup$
    – abuchay
    May 2, 2018 at 1:32
  • $\begingroup$ Adding a new answer. Check that. $\endgroup$ May 2, 2018 at 10:01

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.