Участник:Tolstikhin/Песочница

Материал из MachineLearning.

(Различия между версиями)

Версия 12:29, 23 ноября 2008

Содержание

1 Введение.
- 1.1 Постановка задачи.
2 Сложность задачи.
3 Точное решение задачи. Алгоритм 1.
4 Приближённое решение задачи. Алгоритм 2.
- 4.1 Изложение алгоритма 2.

Введение.

В этой статье будeт рассматриваться задача поиска совместной подсистемы максимального веса для систем линейных уравнений и неравенств (MaxFS problem). Вначале будут введены общие определения и приведены некоторые результаты касательно сложности решения данной задачи. Дальше будут сформулированы вспомогательные утверждения, на основе которых мы сможем построить достаточно эффективный алгоритм, решающий задачу.

Изложение алгоритма будет сопровождаться численными примерами его работы.

Постановка задачи.

Пусть дана произвольная несовместная система линейных неравенств

$a_{i1}x_1+\dots+a_{in}x_n\geq b_i,\ i=1,2,\dots,m\ (1)$

или равенств

$a_{i1}x_1+\dots+a_{in}x_n = b_i,\ i=1,2,\dots,m,$

где $a_{ij},\ b_i$ - конечные действительные числа, числа m и n фиксированы.

Задача MaxFs состоит в нахождении совместной подсистемы, имеющей максимальную мощность (МСП).

Данная задача часто возникает при решении различных математических задач - в том числе при решении задач прогнозирования и распознавания. Примером может служить разделение объектов 2х классов обучающей выборки гиперплоскостью. В случае, когда эту задачу не удаётся решить точно, мы хотим провести гиперплоскость так, чтобы она допускала минимальное число ошибок.

Сложность задачи.

Задача выделения максимальной совместной подсистемы является NP-сложной. ([2])

Посчитаем приблизительно сложность простого перебора.

Всего $2^m-1$ подсистем. Каждую подсистему надо проверить на совместность. Например, методы, упомянутые в [1], требуют для определения совместности подсистемы состоящей из $l$ неравенств и имеющей ранг $r$ , $\left(^l_r\right)\left(^n_r\right)O((l-r)r^3)$ операций.

Понятно, что на практике данный метод не годится.

Существует другой подход к получению точного решения.

Произвольный булев вектор $(\alpha_1,...,\alpha_m)$ однозначно определяет подсистему $Sub_{\alpha}$ системы 1. $i$ -е неравенство входит в подсистему $Sub_{\alpha}$ тогда и только тогда, когда $\alpha_i=1$ .

Введём булеву функцию $g$ на $m$ -мерном булевом кубе, принимающую единицу на тех и только тех наборах $\alpha$ , которые соответствуют несовместным системам $Sub_{\alpha}$ . Очевидно, что такая булева функция монотонна. Исходная задача сводится к поиску максимального верхнего нуля монотонной функции $g$ . В книге [3] приведён алгоритм, решающий эту задачу. В худшем случае он делает $\left(2^m/sqrt{m}\right)$ шагов, где шаг - вычисление одного значения функции g.

Этот подход немного ускоряет решение задачи, но по-прежнему работает слишком медленно.

В кнгие [1] предлагается более эффективный метод решения исходной задачи.

Точное решение задачи. Алгоритм 1.

Вспомагательные определения и утверждения.

По-прежнему будем рассматривать систему 1. Допустим, что она совместна и имеет ранг $r$ .

Определение 1. Решение системы 1 - узловое, если оно обращает в равенства какие-нибудь $r$ её неравенств с линейно независимыми левыми частями.

Определение 2. Подсистема системы 1 - крайняя, если, во-первых, её ранг больше нуля и равен числу неравенств в ней, во-вторых, хотя бы одно её узловое решение удовлетворяет системе 1.

Определение 3. Крайняя подсистема - узловая подсистема, если все её узловые решения удовлетворяют системе 1.

Свойство 1. Крайняя подсистема тогда и только тогда является узловой подсистемой системы 1, когда её ранг совпадает с рангом $r$ системы 1.

Теорема 1. Каждая совместная система линейных неравенств вида 1 отличного от нуля ранга имеет хотя бы одну узловую подсистему, а значит, хотя бы одно узловое решение.

С помощью этих утверждений доказывается основная лемма, на которой держится следующий алгоритм.

Лемма. Ранг максимальной совместной подсистемы совпадает с рангом всей системы.

Изложение алгоритма 1.

Алгоритм будет выглядеть следующим образом. Будем перебирать одну за другой подсистемы мощности и ранга $r$ для данной несовместной системы 1 ранга $r$ . Среди них обязательно найдутся все узловые подсистемы для искомой МСП, так как по лемме ранг МСП равен $r$ . Из определения следует, что все узловые решения любой узловой подсистемы МСП удовлетворяют всей МСП. Это означает, что достаточно найти хотя бы одно узловое решение любой узловой подсистемы МСП и подставить его в систему 1, чтобы выделить саму МСП. Таким образом мы заменяем все неравенства в найденной подсистеме на равенства и находим решение полученной системы уравнений (в случае бесконечного числа решений - достаточно найти одно). Затем мы подставляем полученное решение в исходную систему 1 и выделяем те неравенства, которым удовлетворяет полученное решение. Эти неравенства образуют некую совместную подсистему системы 1. В какой-то момент мы найдём одну из узловых подсистем МСП и выделим МСП.

Трудность заключается в том, что мы не знаем какая из подсистем является узловой для МСП. Поэтому приходится перебирать все подсистемы мощности и ранга $r$ и находить одно их узловое решение. Затем выделять по узловому решению подсистему, соответствующую ему. Сравнивая мощности всех систем, полученных таким путём, мы найдём МСП. Также мы найдём одно его решение.

Сложность алгоритма

Общее число операций приведённого алгоритма оценивается сверху выражением:

$K_1mn^2+\left(^m_r\right)\left(K_2nr^2+K_3mn\right)$ ,

где $K_1,K_2,K_3$ - некоторые действительные числа.

Краткое обоснование полученной оценки. Предположим, что $n < m$ . Вычисление ранга $r$ матрицы исходной системы 1 требует $O(mn^2)$ операций (приведение к треугольному виду). Число подсистем мощности $r$ в системе 1 - $\left(C^r_m\right)$ . Для найденной подсистемы ранга $r$ нахождение одного узлового решения занимает $O(r^2)$ операций. Подстановка найденного решения во все неравенства системы 1 - $O(mn)$ операций.

Эта оценка уже гораздо лучше оценки для полного перебора. К сожалению алгоритм всё ещё остаётся неподъёмным на практике при больших значениях $n$ и $m$ .

Приближённое решение задачи. Алгоритм 2.

Точное решение задачи выделения максимальной совместной подсистемы - NP-полная задача.

Однако, если отказаться от нахождения точной МСП и ограничиться нахождением приближённой МСП, задачу можно решить за полиномиальное время. Основная идея - перебирать не всевозможные подсистемы ранга и мощности $r$ , а только часть из них.

Дело в том, что для нахождения точного решения нам достаточно наткнуться хотя бы на одну узловую подсистему МСП. При малом числе переменных и большом числе неравенств в системе 1 можно рассчитывать на то, что МСП имеет большое число узловых подсистем. А значит мы с большой вероятностью наткнёмся на неё. В противном случае мы не рассмотрим ни одну из узловых подсистем МСП и получим неточное решение.

Одна из возможных реализаций неполного перебора, приведённая в [1], представлена ниже.

Изложение алгоритма 2.

По-прежнему пытаемся найти МСП несовместной системы 1 ранга $r$ . Как и выше каждая подсистема определяется вектором $v=(v_1,...,v_r)$ . Введём вспомогательные переменные:

$s$ - номер строящейся "ветви" множества подсистем;

$t$ - номер текущего неравенства в подсистеме, $1\leq t \leq r$ ;

$p$ - параметр перехода к одному из этапов алгоритма. $p \in \{-1,0,1\}$ .

$h$ - параметр алгоритма.

Алгоритм выглядит следующим образом.

Инициализация переменных: $s=1, p=1, v_1=1, t=2$ .

Этап 1 ( $p=1$ )

$v_t:=v_{t-1}+1$ ;

Если( $v_t>m$ )

$t:=t-1, p=-1$ ;

Иначе

{

Если( $t<r$ )

$t:=t+1,p=1$ ;

Если( $t==r$ )

{построили очередную подсистему.

обрабатываем её.

$p:=0$ }

}

Этап 2 ( $p=0$ )

$v_t:=v_t+h$ ;

Если( $v_t>m$ )

$t:=t-1, p=-1$ ;

Иначе

{построили очередную подсистему.

обрабатываем её.

$p:=0$ }

Этап 3 ( $p=-1$ )

Если( $t\neq 1$ )

{

$v_t:=v_t+h$ ;

Если( $v_t>m$ )

$t:=t-1$ ;

Иначе

$t:=t+1, p=1$ ;

}

Если ( $t==1$ ) {

$s:=s+1$ ;

$v_1:=s$ ;

Если( $v_1>m$ ) возврат;

Иначе $t=2, p=1$

}

Уменьшая параметр $h$ мы увеличиваем мощность перебираемых подсистем.

Источник — «http://www.machinelearning.ru/wiki/index.php?title=%D0%A3%D1%87%D0%B0%D1%81%D1%82%D0%BD%D0%B8%D0%BA:Tolstikhin/%D0%9F%D0%B5%D1%81%D0%BE%D1%87%D0%BD%D0%B8%D1%86%D0%B0»

@@ Строка 118: / Строка 118: @@
 Предположим, что <tex>n < m</tex>.
 Вычисление ранга <tex>r</tex> матрицы исходной системы 1 требует <tex>O(mn^2)</tex> операций
-(приведение к треугольному виду). Число подсистем мощности <tex>r</tex> в системе 1 - <tex>\left(^m_r\right)</tex>.
+(приведение к треугольному виду). Число подсистем мощности <tex>r</tex> в системе 1 - <tex>\left(C^r_m\right)</tex>.
 Для найденной подсистемы ранга <tex>r</tex> нахождение одного узлового решения занимает <tex>O(r^2)</tex> операций.
 Подстановка найденного решения во все неравенства системы 1 - <tex>O(mn)</tex> операций.

Участник:Tolstikhin/Песочница

Материал из MachineLearning.

Версия 12:29, 23 ноября 2008

Содержание

Введение.

Постановка задачи.

Сложность задачи.

Точное решение задачи. Алгоритм 1.

Вспомагательные определения и утверждения.

Изложение алгоритма 1.

Сложность алгоритма

Приближённое решение задачи. Алгоритм 2.

Изложение алгоритма 2.

Просмотры

Личные инструменты

Навигация

Поиск

Инструменты