Минимально значимые переменные в линейной системе

Минимально релевантные переменные в линейной системе ( Min-RVLS ) — это задача математической оптимизации . Для заданной линейной программы требуется найти допустимое решение, в котором число ненулевых переменных минимально.

Известно, что эта задача относится к NP-трудным и даже трудно поддается аппроксимации.

Определение

Задача Min-RVLS определяется следующим образом: ^[1]

Бинарное отношение R , которое является одним из {=, ≥, >, ≠};
Матрица A размером m на n (где m — количество ограничений, а n — количество переменных);
Вектор b размером m на 1 .

Линейная система задается как: A x R b. Предполагается, что она допустима (т.е. удовлетворяет хотя бы одному x ). В зависимости от R существует четыре различных варианта этой системы: A x = b, A x ≥ b, A x > b, A x ≠ b .

Цель состоит в том, чтобы найти вектор x размером n на 1, который удовлетворяет системе A x R b и при этом содержит как можно меньше ненулевых элементов.

Особый случай

Задача Min-RVLS[=] была представлена Гари и Джонсоном ^[2] , которые назвали ее «минимально весовым решением линейных уравнений». Они доказали, что она NP-трудна, но не рассматривали приближения.

Приложения

Задача Min-RVLS важна в машинном обучении и линейном дискриминантном анализе . При наличии набора положительных и отрицательных примеров требуется минимизировать количество признаков, необходимых для их правильной классификации. ^[3] Задача известна как задача минимального набора признаков. Алгоритм, который аппроксимирует Min-RVLS в пределах фактора, может существенно сократить количество обучающих выборок, необходимых для достижения заданного уровня точности. ^[4] $O(\log(m))$

Задача о кратчайшем кодовом слове в теории кодирования — это та же задача, что и Min-RVLS[=], когда коэффициенты находятся в GF(2).

Связанные проблемы

В минимальных неудовлетворенных линейных отношениях ( Min-ULR ) нам дано бинарное отношение R и линейная система A x R b , которая теперь предполагается невыполнимой . Цель состоит в том, чтобы найти вектор x , который нарушает как можно меньше отношений, удовлетворяя при этом все остальные.

Min-ULR[≠] тривиально разрешима, поскольку любая система с действительными переменными и конечным числом ограничений-неравенств является допустимой. Что касается остальных трех вариантов:

Min-ULR[=,>,≥] являются NP-трудными даже с однородными системами и биполярными коэффициентами (коэффициентами в {1,-1}). ^[5]
NP-полная задача Минимальный набор дуг обратной связи сводится к Min-ULR[≥], с ровно одной 1 и одной -1 в каждом ограничении, и все правые части равны 1. ^[6]
Min-ULR[=,>,≥] являются полиномиальными, если число переменных n постоянно: их можно решить полиномиально с помощью алгоритма Грира ^[7] за время . $O(n\cdot m^{n}/2^{n-1})$
Min-ULR[=,>,≥] линейны, если число ограничений m постоянно, поскольку все подсистемы могут быть проверены за время O ( n ).
Min-ULR[≥] является полиномом в некотором частном случае. ^[6]
Min-ULR[=,>,≥] может быть аппроксимирован в пределах n + 1 за полиномиальное время. ^[1]
Min-ULR[>,≥] являются минимально-доминирующими-множествами -трудными, даже с однородными системами и троичными коэффициентами (в {−1,0,1}).
Min-ULR[=] не может быть аппроксимирован с точностью до множителя для любого , если только NP не содержится в DTIME ( ). ^[8] $2^{\log ^{1-\varepsilon }n}$ $\varepsilon >0$ $n^{\operatorname {полилог} (n)}$

В дополнительной задаче максимально допустимой линейной подсистемы ( Max-FLS ) цель состоит в том, чтобы найти максимальное подмножество ограничений, которые могут быть удовлетворены одновременно. ^[5]

Задача Max-FLS[≠] может быть решена за полиномиальное время.
Max-FLS[=] является NP-трудной задачей даже с однородными системами и биполярными коэффициентами.

. С целыми коэффициентами трудно аппроксимировать в пределах . С коэффициентами, превышающими GF[q], это q -аппроксимируемо. $m^{\varepsilon }$
Max-FLS[>] и Max-FLS[≥] являются NP-трудными даже с однородными системами и биполярными коэффициентами. Они 2-аппроксимируемы, но их нельзя аппроксимировать в пределах любого меньшего постоянного множителя.

Твёрдость аппроксимации

Все четыре варианта Min-RVLS трудно аппроксимировать. В частности, все четыре варианта не могут быть аппроксимированы с коэффициентом , для любого , если только NP не содержится в DTIME ( ). ^[1]^{: 247–250} Трудность доказывается сокращениями: $2^{\log ^{1-\varepsilon }n}$ $\varepsilon >0$ $n^{\operatorname {полилог} (n)}$

Существует сокращение от Min-ULR[=] до Min-RVLS[=]. Это также применимо к Min-RVLS[≥] и Min-RVLS[>], поскольку каждое уравнение можно заменить двумя дополнительными неравенствами.
Происходит сокращение от минимально-доминирующего набора до Min-RVLS[≠].

С другой стороны, существует сокращение от Min-RVLS[=] до Min-ULR[=]. Это также применимо к Min-ULR[≥] и Min-ULR[>], поскольку каждое уравнение можно заменить двумя дополнительными неравенствами.

Следовательно, когда R находится в {=,>,≥}, Min-ULR и Min-RVLS эквивалентны с точки зрения сложности аппроксимации.

Ссылки

^ abc Амальди, Эдоардо; Канн, Вигго (декабрь 1998 г.). «Об аппроксимируемости минимизации ненулевых переменных или неудовлетворительных отношений в линейных системах». Теоретическая информатика . 209 (1–2): 237–260. doi : 10.1016/S0304-3975(97)00115-1 .
^ Гэри, Майкл Р.; Джонсон, Дэвид С. (1979). Компьютеры и неразрешимость: Руководство по теории NP-полноты . WH Freeman. ISBN 978-0-7167-1044-8.
^ Келер, Гэри Дж. (ноябрь 1991 г.). «Линейные дискриминантные функции, определяемые генетическим поиском». ORSA Journal on Computing . 3 (4): 345–357. doi :10.1287/ijoc.3.4.345.
^ Ван Хорн, Кевин С.; Мартинес, Тони Р. (январь 1994 г.). «Проблема минимального набора признаков». Нейронные сети . 7 (3): 491–494. doi :10.1016/0893-6080(94)90082-5.
^ ab Амальди, Эдоардо; Канн, Вигго (август 1995 г.). «Сложность и аппроксимируемость поиска максимально допустимых подсистем линейных отношений». Теоретическая информатика . 147 (1–2): 181–210. doi : 10.1016/0304-3975(94)00254-G .
^ ab Sankaran, Jayaram K (февраль 1993 г.). «Заметка о разрешении невыполнимости в линейных программах путем релаксации ограничений». Operations Research Letters . 13 (1): 19–20. doi :10.1016/0167-6377(93)90079-V.
^ Грир, Р. (2011). Деревья и холмы: Методология максимизации функций систем линейных отношений . Elsevier. ISBN 978-0-08-087207-0.^{[ нужна страница ]}
^ Арора, Санджив; Бабай, Ласло; Стерн, Жак; Суидик, З. (апрель 1997 г.). «Твердость приближенных оптимумов в решетках, кодах и системах линейных уравнений». Журнал компьютерных и системных наук . 54 (2): 317–331. doi : 10.1006/jcss.1997.1472 .

[:1-1] Амальди, Эдоардо; Канн, Вигго (декабрь 1998 г.). «Об аппроксимируемости минимизации ненулевых переменных или неудовлетворительных отношений в линейных системах». Теоретическая информатика . 209 (1–2): 237–260. doi : 10.1016/S0304-3975(97)00115-1 .

[2] Гэри, Майкл Р.; Джонсон, Дэвид С. (1979). Компьютеры и неразрешимость: Руководство по теории NP-полноты . WH Freeman. ISBN 978-0-7167-1044-8.

[3] Келер, Гэри Дж. (ноябрь 1991 г.). «Линейные дискриминантные функции, определяемые генетическим поиском». ORSA Journal on Computing . 3 (4): 345–357. doi :10.1287/ijoc.3.4.345.

[4] Ван Хорн, Кевин С.; Мартинес, Тони Р. (январь 1994 г.). «Проблема минимального набора признаков». Нейронные сети . 7 (3): 491–494. doi :10.1016/0893-6080(94)90082-5.

[:0-5] Амальди, Эдоардо; Канн, Вигго (август 1995 г.). «Сложность и аппроксимируемость поиска максимально допустимых подсистем линейных отношений». Теоретическая информатика . 147 (1–2): 181–210. doi : 10.1016/0304-3975(94)00254-G .

[:2-6] Sankaran, Jayaram K (февраль 1993 г.). «Заметка о разрешении невыполнимости в линейных программах путем релаксации ограничений». Operations Research Letters . 13 (1): 19–20. doi :10.1016/0167-6377(93)90079-V.

[7] Грир, Р. (2011). Деревья и холмы: Методология максимизации функций систем линейных отношений . Elsevier. ISBN 978-0-08-087207-0.^{[ нужна страница ]}

[8] Арора, Санджив; Бабай, Ласло; Стерн, Жак; Суидик, З. (апрель 1997 г.). «Твердость приближенных оптимумов в решетках, кодах и системах линейных уравнений». Журнал компьютерных и системных наук . 54 (2): 317–331. doi : 10.1006/jcss.1997.1472 .