Байесовский подход к проектированию вещественных переменных в булевы в методе простой итерации, примененном к задаче выполнимости булевых формул

Размещено на http://www.allbest.ru/

Байесовский подход к проектированию вещественных переменных в булевы в методе простой итерации, примененном к задаче выполнимости булевых формул

Ю.Ю. Огородников

Омский государственный технический университет, г.Омск, Россия

В статье представлена модификация непрерывного метода поиска глобального минимума вещественного функционала, ассоциированного с задачей выполнимости булевых формул (SAT). Известно, что данные методы далеко не всегда сходятся к глобальному минимуму из-за наличия точек-оврагов на траектории поиска. Вместо преодоления таких точек автором предлагается выполнять проектирование вещественных переменных в булевы. Для этого производится построение байесовского классификатора, использующего апостериорные вероятности верного определения каждого бита. Проведены численные эксперименты на экземплярах SAT, эквивалентных задаче факторизации целых чисел. Установлено, что предлагаемый подход проектирования с вероятностью 0,71 верно определяет единичные биты, однако для нулевых бит такая вероятность существенно ниже - около 0,04.

Ключевые слова: метод простой итерации, выполнимость булевой формулы, проектирование вещественных переменных в булевы, параметр проектирования, байесовский классификатор, единичные биты.

Введение

Задача выполнимости булевых формул (SAT) занимает центральное место в теории вычислительной сложности. В 1971 году С.Кук показал [1], что SAT является NP-полной, т.е. другие задачи из класса NP сводятся к SAT за полиномиальное время. Это обстоятельство объясняет повышенный интерес к данной проблеме - зная полиномиальный алгоритм решения SAT, станет возможным решать за «быстрое» время важные задачи науки и техники, такие как, например, задача логистики, составления расписания, различные задачи криптографии и криптоанализа. Среди последних особо стоит отметить задачу факторизации целых чисел, на которой построен известный асимметричный алгоритм шифрования RSA. Известно, что часть выполняющего набора SAT соответствует битам сомножителя числа [2], которое в свою очередь является ключом шифрования RSA. Зная данные биты, представляется возможным провести атаку на алгоритм RSA. К сожалению, в настоящее время неизвестен полиномиальный алгоритм решения задачи SAT. Однако известны так называемые вероятностные алгоритмы решения SAT, время работы которых полиномиально, однако они не гарантируют корректность работы. Другими словами, если алгоритм на выходе выдал ответ «формула выполнима», то верное решение найдено. Если же он выдал противоположный ответ, то это не означает, что формула не имеет решений. Для подобных алгоритмов известны оценки вероятности их правильной работы. Подобное можно сконструировать и для отдельных бит путем многократного проведения эксперимента и накопления статистики верного определения бит.

булевый формула итерация минимум

1. Описание метода простой итерации

Введем на множестве булевых переменных форму , где

(1)

Для экземпляров SAT, эквивалентных задаче факторизации, число переменных в каждом дизъюнкте равняется 3-м, поэтому данная форма представлена в виде 3-КНФ. Преобразуем 3-КНФ в эквивалентную ей 3-ДНФ по правилам:

(2)

и .

Также известно, что набор булевых переменных , обращающий формулу (1) в значение TRUE, обращает 3-ДНФ, полученную по правилам (2), в значение FALSE [3].

Далее преобразуем булевы переменные в вещественные по правилам:

(3)

Следующим шагом сопоставим форме функционал следующего вида:

, где и

(4)

Известно, что глобальный минимум соответствует набору булевых переменных , обращающих в значение FALSE, а - в TRUE [3].

Будем искать глобальный минимум . Вместо традиционных методов будем искать стационарные точки функционала. Для этого дифференцируем по всем переменным, тем самым получая его градиент , и приравниваем к нулю его компоненты [4]. Получаем систему уравнений вида

(5)

Будем решать систему (5) методом простой итерации. Вычислительные эксперименты показали, что траектория метода ведет в «овраг», т.е. такую точку пространства поиска , для которой значительные изменения аргумента ведут к малым изменениям аргумента, или же совсем его не изменяют. Известные различные эвристики по преодолению оврагов [5], однако можно спроецировать точку в булево пространство и определить, какие компоненты совпадают с точным решением.

2. Проектирование вещественных переменных в булевы

Данный способ подразумевает под собой построение байесовского классификатора, который определяет наиболее вероятный класс распознавания [6]. Переформулируем задачу проектирования в терминах байесовского подхода. Обозначим через вектор-приближение, сформированный на й итерации. Тогда - бит вектора-приближения. Введем два класса и . Очевидно, что эти классы не пересекаются и образуют полное пространство классов . Далее введем два события: и . Эти события являются гипотезами и состоят в том, что бит вектора-приближения принадлежит к классам и .

Пусть событие, состоящее в том, что бит вектора-приближения на итерации в номером определен верно, т.е. совпадает с точным решением. Тогда вероятность этого события.

По формуле полной вероятности имеем: .

Здесь вероятность верного определения бита при условии, что он отнесен к классу (другими словами, распознан как нулевой бит). Соответственно, - вероятность верного определения бита при распознавании его как единичного.

По формуле Байеса имеем:

и (6)

и - это вероятности верного отнесения бита к классам и при условии, что - верно определён. Именно на данных апостериорных вероятностях вычисляются параметры проектирования. Для успешного их вычисления требуется знание четырех вероятностей: , , , .

Вероятности и - безусловные. Изначально они задаются эвристически, например, можно взять и . В процессе выполнения метода простой итерации вероятности и пересчитываются в зависимости от значения переменной и параметра проектирования .

и

Вероятности и - априорные. Они могут быть получены на основании статистических испытаний обыкновенного метода простой итерации. В работе [6] описаны методы по определению вероятности верного определения бит. К сожалению, лишь для некоторых нулевых бит удалось получить высокие вероятности, для остальных же они существенно ниже. Однако полученные данные можно использовать как априорные в байесовском проектировании.

Таким образом, после каждой итерации метода последовательных приближений происходит вычисление апостериорных вероятностей по формулам (10). В зависимости от того, какая вероятность окажется больше, происходит проектирование либо в 0, либо в 1. В работе [7] показано, что данный способ проектирования является оптимальным по верному определению единичных бит, однако нулевые биты определяет не так хорошо, как другие.

3. Численные эксперименты

В данном разделе представлены результаты тестирования байесовского подхода к проектированию переменных. Тестирование проводилось на экземплярах SAT, эквивалентных задаче факторизации целых чисел. Для каждой размерности использовалось 1000 экземпляров задачи SAT. В таблице 1 приведены данные по верному определению нулевых и единичных бит в зависимости от параметра проектирования .

Таблица 1. Тестирование байесовского подхода к проектированию

Как видно из представленных данных, метод определяет наибольшее число единиц при . При этом число верно определяемых нулей при параметре , принадлежащим указанному диапазону, меньше, чем в остальных случаях.

На рисунках 1 и 2 приведены графики зависимости процента верно определенных единиц и нулей для экземпляров SAT, эквивалентных задаче факторизации целых чисел.

Рис.1. Процент верно определенных единичных бит

Рис. 2. Процент верно определенных нулевых бит

Как видно из представленных данных, процент верно определенных единиц с увеличением размерности стабилизируется в районе 65 - 73%, для нулей же такой процент существенно ниже: от 3 до 18-ти. Причем процент верно определенных нулей падает с увеличением размерности задачи. Это объясняется тем, что при проектировании мы не учитывали связи между переменными - использовали так называемую наивную байесовскую схему.

Заключение

В статье рассмотрен метод байесовский подход к проектированию переменных, основанный на вычислении апостериорных вероятностей верного определения бит. Проектирование также зависит от безусловного параметра . Экспериментально установлено, что метод наиболее эффективен при . Проведены численные эксперименты на экземплярах SAT, эквивалентных задаче факторизации целых чисел. Установлено, что метод верно распознаёт до 73% единиц и до 18% процентов нулей.

Библиографический список

1. Cook S. The complexity of theorem-proving procedures / S. Cook // In proceedings of the third annual ACM symposium on Theory of computing. - 1971. P. 151 -158.

2. Дулькейт В.И. Сведение задачи факторизации, дискретного логарифмирования и логарифмирования на эллиптической кривой к решению ассоциированных задач ВЫПОЛНИМОСТЬ / В.И. Дулькейт // Компьютерная оптика. - 2010. - T. 34, № 1. - C. 118 - 123.

3. Gu J. On Optimizing a Search Problem / J.Gu // In N. G. Bourbakis, editor, Artificial Intelligence Methods and Applications. 1992. - Vol. 1, chapter 2. - P. 63 105.

4. Дулькейт В.И. Непрерывные аппроксимации решения задачи ВЫПОЛНИМОСТЬ применительно к криптографическому анализу асимметричных шифров / В.И. Дулькейт, Р.Т.Файзуллин, И.Г.Хныкин // Компьютерная оптика. - 2009. - T. 33, № 1. - С. 68 - 73.

5. Gu J. Local search for satisfiability (SAT) problem /J.Gu // IEEE Trans, on Systems, Man, and Cybernetics. - 1993. - 23 (4) Jul. - P. 1108 - 1129.

6. Огородников Ю.Ю. Определение нулевых бит задачи 3-ВЫПОЛНИМОСТЬ, ассоциированной с задачей факторизации / Ю.Ю.Огородников, Р.Т. Файзуллин // Компьютерная оптика. - 2014. - Т. № 3. - С. 521 - 529.

7. Огородников Ю.Ю. Проектирование вещественных переменных в булевы в методе простой итерации, применённом к задаче выполнимости булевых формул / Ю.Ю. Огородников // Научный вестник НГТУ. - 2015. - Т. № 1. - С. 183 - 200.

Размещено на Allbest.ru