Содержание к диссертации
Введение
Глава 1. О возможности определения неизвестных параметров дискретного узла с помощью переоценки вероятностей для пороговых функций 24
1.1. Переоценка вероятностей для мажоритарных функций 24
1.2. Сравнительный анализ некоторых дискретных методов для мажоритарных функций 39
1.3. Переоценка вероятностей для пороговых функций 42
1.4. О возможности восстановления правила выделения существенных переменных для пороговых функций 55
1.5. О восстановлении пороговой функции 63
1.6. Переоценка вероятностей совокупностей переменных и о некоторых статистических аналогах пороговых функций 70
1.7. Переоценка вероятностей значений переменных для произвольных пороговых функций с использованием геометрического подхода 75
Глава 2. Исследование возможностей переоценки вероятностей для других классов функций 81
2.1. Переоценка вероятностей для некоторого класса непороговых функций 82
2.2. Переоценка вероятностей для функций с нелинейными членами в псевдобулевом задании 87
2.3. О суперпозиции пороговых функций 95
2.4. Достаточные условия уменьшения числа неравенств в некоторых системах без потери решений 100
2.5. Переоценка вероятностей по системе ограниченного количества псевдобулевых неравенств с использованием геометрического подхода 110
2.6. Переоценка вероятностей для пороговых функций -значной логики 115
2.7. О некоторых классах к -значных функций 129
2.8. Еще об одном классе -значных функций 133
Заключение 137
Литература 140
Приложение 144
- Сравнительный анализ некоторых дискретных методов для мажоритарных функций
- Переоценка вероятностей совокупностей переменных и о некоторых статистических аналогах пороговых функций
- Переоценка вероятностей для функций с нелинейными членами в псевдобулевом задании
- Переоценка вероятностей по системе ограниченного количества псевдобулевых неравенств с использованием геометрического подхода
Введение к работе
Исследование систем описывающих функционирование узлов дискретной аппаратуры булевых уравнений (СБУ)
/(*)=«,, t = U~t, (1)
связанное с нахождением представлений нелинейных булевых уравнений из системы (1) в базисе арифметических операций в поле действительных чисел, является актуальным направлением в дискретной математике. Его развитие обусловливается как задачами анализа СБУ, так и задачами синтеза булевых функций и различных устройств обработки дискретной информации. Аналитические задачи являются расширением арсенала математических методов исследования СБУ (1). В области синтеза замена нелинейных булевых уравнений на равносильные действительные соотношения приводит к расширению возможностей задания булевых функций алгоритмическим путем в базисе традиционных арифметических команд вычислительной техники. Вместе с тем появляется возможность задания булевых функций на новой элементной базе с реализацией операций суммирования и сравнения с высоким быстродействием, а также непосредственно в физической или химической среде. Наиболее известными образцами таких вычислительных модулей являются нейроплаты и ней-росети с широкими функциональными возможностями.
Линейные неравенства, лежащие в основе этих идей, могут возникать естественно, как следствие работы того или иного узла, но могут быть введены и искусственно, путем специального преобразования исходной задачи.
К анализу СБУ, которым занимались многие авторы [1-9, 20, 31, 34, 35, 38, 41, 43], относятся псевдобулевые методы, сводящие решение СБУ к решению систем псевдобулевых уравнений или неравенств (метод разделяющей поверхности, метод замены булева равенства на линейное псевдобулево равен сто с неоднозначно определенной правой частью, метод, использующий экстраполяцию булевых уравнений выпуклыми функционалами и другие). В большинстве случаев предлагаются способы построения таких систем уравнений или
неравенств, что задача решения СБУ сводится к отысканию булевого вектора, минимизирующего некоторую функцию и удовлетворяющего построенным ограничениям. Ограничения и функцию удобно выбирать линейными, что позволяет использовать для решения получаемой задачи хорошо разработанный аппарат линейного программирования. Значительная часть исследований, проводимых в этой области ранее, была связана с методом разделяющих плоскостей (МРП) [9, 35], основанном на сведении нелинейных булевых уравнений к равносильным системам линейных псевдобулевых неравенств, и решении последних методами линейного программирования.
Вопросы решения систем линейных неравенств относительно дискретных неизвестных представляют большой практический интерес. В настоящее время не существует универсальных аналитических методов, позволяющих за приемлемое время решить произвольную действительную систему относительно дискретных неизвестных либо ответить на вопрос, совместна она или нет. Мало внимания уделялось проблеме переноса вероятностной меры из действительной области в булеву. Вместе с тем сама специфика линейного псевдобулевого неравенства позволяет получать дополнительную информацию о значениях входных переменных с помощью теоретико-вероятностных методов.
Теоретико-вероятностный подход к анализу СБУ определяет научную задачу разработки методики получения дополнительной информации относительно значений входных переменных булевой функции по ее выходным значениям при использовании псевдобулевого способа задания.
Целями работы являются расширение возможностей решения систем линейных псевдобулевых неравенств, восстановления различных параметров дискретных устройств, повышение скорости настройки нейросетевых моделей.
Процесс решения псевдобулевых систем неравенств можно рассматривать в более общем смысле. Задание действительных ограничений для булевых переменных определяет некую меру «выполнимости» этих неравенств, или -меру соответствия тех или иных значений искомых переменных тем неравенствам, в которых они участвуют. Решение системы означает, что на множестве
всех возможных значений переменных задана или вырожденная, если решение единственное либо не существует, или невырожденная вероятностная мера, если решений не меньше двух, в соответствии с которой переменные принимают свои значения. По существу происходит перенос вероятностной меры из действительной области в булевую.
В работах [1, 3; 5, 20] введены понятия полуслучайных, случайных и заведомо совместных случайных систем уравнений. Отличительной особенностью систем линейных неравенств, возникающих при анализе дискретных задач, является, как правило, обязательное наличие одного или нескольких решений. Следовательно, такие системы согласно введенной терминологии можно классифицировать как заведомо совместные случайные системы неравенств. В диссертации показано, что эта вероятностная мера зависит от количества и качества неравенств системы, использующихся для ее построения.
В диссертации рассмотрены свойства широкого класса систем линейных псевдобулевых и псевдо- к -значных неравенств с применением методов математического анализа, теории вероятностей, математической статистики, комбинаторного анализа и аналитической геометрии.
Дадим несколько определений. Определение 1. Функцию /fa,...,яи) такую, что
/:Я"->Я,
где В = ВхВх...хВ, В = GF(2) - поле из двух элементов, назовем булевой функ
цией от «переменных.
Определение 2. Псевдобулеву функцию ф(х1 хп) определим отображением
ф:Вя ->R, где В = Z? х Я х... х Д, В-GF{2) - поле из двух элементов, R - поле действительных чисел.
Определение 3. Псевдобулевым ограничением назовем соотношение
где Q - одно из следующих ограничений, определенных в поле R:
=, ф, >, <, >, ^. Определение 4. Пару чисел (,, к2), где ,, к2 - такие минимальные числа, что для булевой функции / выполняется
/(*p...,*j=i<»{«Px,>^>, у=йТ,
їм назовем пороговой структурой функции /.
Определение 5. Булеву функцию /fa хв) назовем пороговой, если ее поро
говая структура есть (і, і).
Чаще будем пользоваться следующим эквивалентным определением пороговой функции: / - пороговая, если
л і-]
Коэффициенты ап i = l, п, назовем весовыми коэффициентами, а число с - порогом.
Определение 6. Пороговую функция назовем мажоритарной, если все весовые коэффициенты равны единице.
Для получения основных результатов и оценок рассмотрен некоторый простейший узел дискретной аппаратуры со сдвиговым характером поступления входной информации и с пороговой функцией на выходе. В работе [38] определено понятие системы рекуррентного типа, описывающей функционирование такого узла. Существует несколько аргументов по поводу целесообразности исследования вероятностных свойств такого автомата. Во-первых, сложность нахождения неизвестных параметров дискретных узлов зависит от пороговых структур функций, реализующихся этими узлами, а изучение свойств пороговой функции является важным этапом на этом пути. Во-вторых, и об этом будет сказано ниже, функции с ограниченной пороговой структурой могут рассматриваться в качестве статистических аналогов реально использующихся функций, либо - как моделирующие некоторые более сложные процессы. В-
третьих, исследование малоизученных свойств пороговых функций и их последующее использование в различных нейронных моделях позволит, вероятно, улучшить количественные и качественные характеристики последних при решении большого класса различных задач.
В зависимости от различных типов пороговой функции результаты были достигнуты с применением разных методов. Для мажоритарных функций оценки получены при прямом подсчете вероятностей, для других пороговых функций удалось использовать некоторые методы теории вероятностей и аналитической геометрии. Необходимо отметить, что построение меры на множестве допустимых значений переменных предпринималось как в асимптотике, то есть при стремлении количества неизвестных в бесконечность, и с наложением ограничений на весовые коэффициенты, так и для любого конечного числа переменных без каких-либо ограничений..
В ряде работ [19, 22], посвященных исследованию свойств узлов дискретной аппаратуры, было замечено, что между знаками выходной последовательности могут возникать корреляционные связи, зависящие от различных параметров. Эти связи описываются с помощью распределений мультиграмм в выходной последовательности, которые используются при разработке методов определения неизвестных параметров рассматриваемых узлов. Поэтому вполне естественно, что для успешного решения ряда задач дискретной математики необходимо использование на выходе таких обобщенных мультиграмм (или, что то же самое, - таких подсистем линейных псевдобулевых неравенств), для которых апостериорные вероятности максимально приближены к единице. Определение 7. Обобщенной v -граммой (a;i *... * а, ), 1 <, ix <... < /,, < t, назовем
упорядоченную мультиграмму с фиксированными значениями aiit...,air на местах ї,,...,/, соответственно.
На уровне идеи представляется очевидным то, что рассматривать нужно обобщенные и-граммы (и — количество входных переменных функции), или п неравенств, в образовании которых участвует искомая переменная, поскольку в данной подсистеме содержится наиболее полная информация об этой перемен-
ной. В работе [3] было показано преимущество использования т-грамм, т>п, (метод окрестностей). В диссертации аналитически доказана эффективность применения «-грамм специального вида. Указанные мультиграммы формируют подсистемы с повышенной вероятностью появления некоторых решений. Были найдены условия, налагаемые на выходную обобщенную мультиграмму, при которых апостериорная вероятность стремится к единице. По таким мульти-граммам можно локально восстанавливать значения некоторых переменных с высокой вероятностью. Общая идея локального подхода к решению задач дискретной математики высказывалась в работе [17].
Использование одной оптимальной п -граммы при построении вероятностной меры, близкой к вырожденной, с алгебраической точки зрения совпадает по смыслу с выделением из исходной системы подсистемы максимального ранга. Иными словами, существует широкий класс систем п линейных псевдобулевых неравенств от п(п -1)+1 переменных, по каждой из которых можно определить значение некоторой неизвестной с вероятностью, стремящейся к единице с ростом л. Нахождение начального вектора (НВ) входной линейной рекуррентной последовательности (ЛРП) в этом случае при прочих известных параметрах рассматриваемой схемы сводится к построению и решению булевой системы линейных уравнений (СЛУ) с ограниченным числом искажений в правой части.
Выше обсуждались вопросы, связанные с переоценкой вероятностей значений некоторых переменных для пороговой функции. Здесь для более уверенного определения неизвестной ж, использовалась подсистема
где I - псевдобулевая линейная форма, ***'П*''* = {*i4...i4* jH{^,...,1^)= {xt}, Q - один из знаков , <, j = 1, v.
Далее рассматривается принципиально иная ситуация — функции с пороговой структурой (i,, к2), Aj, kj 2. Сначала изучаются арифметические соотношения между весовыми коэффициентами, которые позволяют свести переоценку ве-
роятностей для новых функций к уже решенной задаче для пороговых функций. Затем с помощью геометрической интерпретации оценены апостериорные вероятности для произвольной булевой функции с ограниченной пороговой структурой. Это эквивалентно вычислению оценок весов функции и всех ее подфункций.
Рассматривается булева функция с пороговой структурой (2,2). Переменные переупорядочиваются в соответствии с убыванием модулей W -b\, / = 1, п,
где /(х,,...,хп) = 1«.
-і
1=1
Изучение апостериорных вероятностей значений переменных по одному значению функции с пороговой структурой (2,2) показало, что максимальная информация из неравенств извлекается для переменной х, (в отличие от переменной с максимальным по модулю весовым коэффициентом - для пороговой функции).
Асимптотический подход к оценке апостериорных вероятностей для пороговых функций имеет сильные и слабые стороны. К первым можно отнести скорость, простоту и точность в вычислениях, к недостаткам - ограниченную применимость. Решение задачи на основе геометрической интерпретации позволяет получать оценки апостериорных вероятностей для любых функций с ограниченной пороговой структурой, но за счет повышения сложности вычислений.
Если при решении задач дискретной математики удается построить систему булевых нелинейных, а иногда и линейных, уравнений с искаженными правыми частями, то получение дополнительной информации о некоторых состояниях входной последовательности позволяет уменьшить вероятность искажения, а для некоторых уравнений — свести ее к нулю. Решение СЛУ с искаженными правыми частями в общем случае является экспоненциальной по сложности задачей. С помощью достигнутых в данной работе оценок апостери-
орных вероятностей в некоторых случаях согласно [2, 3, 8] можно решать СЛУ с искаженными правыми частями за полиномиальное время.
В диссертации рассмотрены вопросы, связанные с восстановлением других параметров дискретных устройств, где используются полученные результаты.
Разработана методика восстановления неизвестной пороговой функции. К этой задаче сводится, например, настройка порогового элемента [13, 15]. Такая задача в принципе разрешима с помощью алгоритма решения систем линейных неравенств Хачияна за полиномиальное время, однако реализация этого метода на практике является очень трудоемким процессом. В диссертации предложен и математически обоснован простой алгоритм, с помощью которого на сравнительно небольшой длине выходной последовательности за полиномиальное время строится пороговая функция, стремящаяся по вероятности к исходной.
Рассмотрена задача восстановления правила выделения существенных переменных. Она разбита на две части, когда у исследователя имеется в наличии входная и выходная последовательности либо только выходная последовательность, и сведена к задаче разделения двух простых биномиальных гипотез.
Интересное приложение имеет задача восстановления неизвестных весовых коэффициентов каскада пороговых функций. Имеется в виду настройка нейросетей - суперпозиции пороговых функций. Фактически перед исследователем стоят две задачи. Во-первых, построение объекта, нейросети, который бы заданную входную последовательность значений преобразовывал в выходную. Во-вторых, адаптация этого объекта реальной жизни, то есть при поступлении на входы новых данных нейросеть должна сгенерировать на выходе результат, с некоторой точностью соответствующий практике. Первая часть задачи решается в настоящее время путем многократного повторения одних и тех же действий: по входу нейросетью со случайно заданными весовыми коэффициентами строится выход, который затем сравнивается с обучающим, после чего по некоторому алгоритму пересчитываются коэффициенты в соответствии с ошибкой. Этот процесс отнимает у исследователя очень много времени, и не гарантирует
решение второй задачи. Дальнейшее развитие результатов, полученных в диссертации, могло бы существенно упростить решение задач по настройке нейро-сетей.
Определим следующее вероятностное пространство
(в»*-1, Г, р), где в"+в~1 - декартово произведение N + n-ї множеств Л = {0, і}, 2 - сигма-алгебра на множестве в*1*"'1 (то есть I - это множество всех подмножеств BN*"-1 с заданными на нем операциями пересечения, объединения и разности), и вероятностная мера Р: 2 -»[о, і] такая, что
Р{А є S}= />{(*,,.., Wi)} = -J4-.
(ji,..^iv+»-iW ^
Тогда очевидно определяется вероятность произвольного события, состоящего из более коротких последовательностей.
Входные переменные, подающиеся на вход устройства в каждом такте работы, считаем независимыми равномерно распределенными (если не оговорено обратное) на множестве В случайными величинами. Семейство вероятностных мер на выходе устройства задается стандартным образом, а именно: определим вероятностное пространство
К . р).
где Вк - декартово произведение N множеств В = {о, l}, Z - сигма-алгебра на множестве BN, а Р - вероятностная мера со свойством
f{B = W».yJk,6{o,i},*=iriv^s}-2^^.
D *
где D = х1,..,,хк_і.л_і) \ j\xl,,..fxu) = ylr j\X2,...txntl) = y2f"t Л',''%+л/ = J'^fl, Для дальнейшего изложения введем новые понятия. Определение 8. Апостериорную вероятность
р{х{1)=8А*і>*-*к)\=р{
12 где дс^ участвует в образовании знака выходной последовательности /j=ilt su...,sv_1 - расстояния между существенными переменными в системе рекуррентного типа, назовем вероятностью переоценки входного значения х^ по выходной обобщенной v-грамме ( *i2 *...*/,,).
Будем также говорить о переоценке вероятности как о процессе вычисления вероятности переоценки значения некоторой переменной по выходной v -грамме, ;tw - переоцениваемая переменная по v -грамме. Переоценку вероятности полагаем успешной, если
^^Хч'-ч))'^^' или р{хЬ)^/{h*h*.--*K)}
эффективной, если существует 4> такое, что
pixb)=Xh*h*-*K)}-Ao>p^J)=^ илиХх)"^ч*.»ч))^л<^ОЇ=^
для достаточно больших и;
v -наилучшей по некоторой v -грамме ( * /2 * 4)» если
р{х0) "X Ч *.-Ч))а р{хЬ) =Хл *Л *..-*л)) для любых v-грамм (/, * j2 *...* jv); наилучшей по v-грамме (/, */2*...*i„), если
{^ = SA Ч *..-Ч))Ь К^ =ЯЬ\ * А ..*>.))
для произвольной ^ -граммы (/і * Л * * л)» ^ = 1,и;
переоценку вероятности для переменной х^ считаем успешнее переоценки вероятности для переменной х^'\ если выполняются неравенства
^^Я^^^^У^'^Я^^^оУт
Переменная дг(у) может и не участвовать в образовании знаков i2,...,iy.
При решении задач для пороговых функций к -значной логики были использованы точно такие же методы, полученные результаты тем не менее заметно отличаются.
13 Определение 9. Функцию /(*,,„.,*„) такую, что
/: Я" -> В, где В = ВхВх...хВ, Я = {о,...Д-і}, назовем -значной функцией от п переменных.
Определение 10. Псевдо- к -значную функцию ф(хі,...,хп) определим отображением
ф: В" -* R, где В = ВхВх...хВ, В = {0,...,к-1}, Л - поле действительных чисел. Определение 11. Псевдо- к -значным ограничением назовем соотношение
(*(*,,..„;r„)g г, reR,
где б - одно из следующих ограничений, определенных в поле R:
=, ф, >, <, s, <.
Например, для наилучшей переоценки вероятности фиксированного значения переменной в системе рекуррентного типа нельзя указать выходную мультиграмму, по которой эта переоценка проводится, основываясь только на значности весовых действительных коэффициентов (в отличие от булевого случая). Для построения такой мультиграммы следует вычислить апостериорные вероятности по всем возможным v -граммам и найти максимальную, что реализуемо для небольших значений v. Хотя, учитывая предварительный характер такой задачи, выполнение этих действий представляется целесообразным. Используя полученные в работе результаты, можно локализовать значения элементов входной последовательности и тем самым сократить перебор.
Требуют дальнейшего изучения задачи: - разбиение по какому-либо признаку і-множества {о,...Д-і} на несколько непересекающихся подмножеств Л,-» * = 1» t г переоценка вероятностей
(хеА/ ^ . гт
Ч Д'.Ч'.-.Ч)> ' '
и выбор наилучшей переоценки; если в этом случае одна из вероятностей значительно преобладает над другими, то это дает дополнительную информацию о переменной;
- если из системы неравенств, описывающей функционирование дискретного узла, удается выделить несколько подсистем 5,,...,5,, представить А;-множество
{0,..,,A:-l} В ВИДЄ
{о Л-і} = р4> ДГМ;*0, для всех \<,i
У-1
подсчитать вероятности переоценки
и упорядочить их
то, пересекая подмножества А1% и Ah, получим с большой вероятностью новое,
меньшее по мощности, подмножество, в котором с повышенной вероятностью находится искомое решение.
Данные обстоятельства нужно учитывать при дальнейшем использовании этого и других алгоритмов, а также методов перебора. Применение такой методики оправдано еще и тем, что вычисление апостериорных вероятностей
где хіг...,хі є {xlt.,.,xn}, S - подсистема исходной системы неравенств, может
оказаться проще, чем вычисление вероятностей переоценок значения для отдельной переменной, и, в то же время, полученные оценки апостериорных вероятностей могут существенно отличаться от априорных. Из вида псевдо- к -значных неравенств можно заранее сделать выводы о том, как эффективнее разбить к -множество.
Таким образом, применение пороговых функций в качестве статистических аналогов либо как результат суммарных наблюдений за некоторыми свойствами различных узлов дискретной аппаратуры позволяет существенно упро-
стить решение задач по определению неизвестных параметров схемы. Последнее замечание является весьма актуальным для применения в дискретной математике.
Структура диссертации.
Диссертация состоит из введения, двух глав, заключения, списка литературы (44 наименования) и приложения. Работа изложена на 148 стр., из них 113 стр. основного текста. Нумерация утверждений, определений, примеров и формул во введении и главах - независимая. Ссылки на утверждения, определения, примеры и формулы внутри главы - по номеру, например, «определение 7», «формула (11)»; ссылки на введение и другую главу - с добавлением префикса, например, «система (0.2)» - ссылка на систему (2) из введения, «теорема 1.12» -ссылка на теорему 12 из главы 1.
Постановка задачи.
Рассмотрим систему булевых уравнений
Ш]--$)=г>- ' = w/. (2)
Пусть из системы (2) каким-либо приемом удалось выделить подсистему, для которой можно построить эквивалентную систему псевдобулевых неравенств
^ + ... + ^^. j^lT. (3)
Решение системы (2), очевидно, является решением системы (3). Следовательно, если решить систему (2) одним из известных способов не удастся, то важное значение приобретает умение исследователем решать систему псевдобулевых неравенств. Примерами задач, в которых необходимо решать системы линейных неравенств, являются задачи оптимизации в различных экономических моделях, задачи настройки пороговых элементов в неироматематике и многие другие.
Будем теперь полагать, что система (2) описывает функционирование некоторого дискретного устройства и является системой рекуррентного типа [38], {xj - его входная, \у,) - выходная последовательности.
В диссертации рассматриваются задачи определения различных параметров дискретных устройств с использованием действительных пороговых соотношений: восстановление начального вектора (НВ) рекуррентной последовательности, определение существенных переменных функции, восстановление неизвестной пороговой функции.
Все результаты получены для случая, когда двоичные переменные распределены равномерно. Данное допущение присутствует в большинстве практических задач дискретной математики. Для неравномерно распределенных входных переменных доказательства соответствующих утверждений принципиально не изменятся.
Рассмотрим дискретный узел, порождающий систему (2) рекуррентного типа с параметрами: -начальный вектор рекуррентной последовательности х^ = [х\\...,хр) длины N;
-булева функция /: {0,l}" -> {0,1} такая, что f(x) = 1 <=> ^а,х, >.с, п ~ количество
1=1
существенных переменных функции, n
-правило К выделения существенных переменных из рекуррентной последовательности на вход функции / с условием: разность между индексами двух существенных переменных, максимально удаленных друг от друга в рекуррентной последовательности, не превосходит N; -выходная последовательность Г.
Требуется с помощью переоценки вероятностей определить различные параметры данного узла с наименьшими затратами времени и вычислительных мощностей.
Определение 12. Величину rmi„(s, a, S) назовем длиной выходной последовательности узла, необходимой для нахождения неизвестного параметра s с по-
мощью некоторого фиксированного алгоритма а с заданным уровнем надежности S.
Пусть А =
/l'""/(V)
- набор расстояний между любыми двумя сущест-
венными переменными. Тогда правило К выделения существенных переменных можно записать в следующем виде:
:[1\...,(ЛГ-1)**-'],
где f' означает, что в А содержится к} чисел j. Дадим определение кратности
расстояния.
Определение 13. Назовем к2 кратностью расстояния j в наборе Kt а
k = max к, - максимальной кратностью К.
IsjsJV-l J r
Параметр к играет важную роль при подсчете вероятностей, оценка последних при произвольном к затруднена, так как при к > 1 некоторые входные переменные становятся зависимыми величинами. В то же время при большом к апостериорные вероятности значительно отличаются от априорных, поэтому при создании различных дискретных устройств существует стремление ограничить к. Исходя из этого в дальнейшем будем рассматривать важный частный случай, когда к является константой.
Покажем на следующих примерах, как параметр к влияет на переоценку вероятности.
Пример 14. Пусть функция /- мажоритарная, то есть /(ж) = 1 <=>*-с- ^ас"
смотрим при и->оо и к = п~\ выходную обобщенную биграмму
(^ = 1 * //+; = О), / - такое расстояние, что к, = к. Ей соответствует система неравенств
(
х,+,,.+.хя >с
Вычитая из первого неравенства второе, получим
(x, -1
Следовательно, биграмма (l*0) (а также и (0*l)) определяет значения двух входных переменных. Вероятность появления в выходной последовательности биграммы (1*0) ((о*і)) равна
Лемма 15. Если г - константа, т,г є Z, т -> оо, то
+ г
(1 + 0(1)).
Доказательство проводится с помощью формулы Стирлинга [40]:
Л"
л/2яи (l + o(l)) При и-»оо.
Используя лемму, получим при Я -> оо
Я(і*о)}=Н(ом)}=-7^(і+0(і))^И(і*о)и(о*і)} = ^(і+0(і)).
Таким образом, из системы (2) формируется подсистема
k, =*/. / = й^. (4)
Зная линейный закон функционирования ЛРП, можно составить систему линейных булевых уравнений относительно неизвестного НВ. Следовательно, система (4) равносильна системе
где Ц - булевы линейные формы.
Чтобы набрать СЛУ максимального ранга, необходимо в среднем o(NlnN) уравнений. Поэтому для решения задачи таким способом понадобится 0\N4nlnN) знаков выходной последовательности. Трудоемкость метода оценивается величиной Г = 7]+Т2, где 7] = o{n1 Ыг N) - сложность решения системы
линейных уравнений (СЛУ) методом Гаусса, Тг = 0[NnJnfaN) - сложность составления СЛУ по выходной последовательности.
В следующем примере вероятность переоценки отлична от единицы, поэтому правая часть СЛУ относительно НВ ЛРП известна в вариантах.
Пример 16. Пусть функция /- мажоритарная и с = — , и -* «э, = и-2, расстояние / такое, что к, = к. Тогда выходной биграмме (і * о) соответствует система неравенств
W + ... + xf>;>c, J/(*f> #) = r,=l.
Вычтем из /-го неравенства (/+/)-е, получим:
^) + ^-^-^^1. Из последнего неравенства нельзя однозначно найти ни одну из переменных. Прибегнем к переоценке вероятности:
+ 2
+ ,
уС-1;
«
Следовательно, существует возможность составить СЛУ с искаженными правыми частями с вероятностью искажения, не превышающей 1/6 для всех достаточно больших п.
Определим два класса пороговых функций, анализу которых уделено в диссертации основное внимание. Рассмотрим пороговую функцию f:
Определение 17. Функцию / назовем пороговой функцией 1-го типа, если для каждого индекса j, не превосходящего фиксированного /, весовой коэффици-
ент aj есть величина, не меньшая по порядку, чем Л^* > и ПРИ этом
1-І+І
ам =
при п -* со (такое условие, наложенное на весовые коэффици-
енты, будем называть условием (*));
если все весовые коэффициенты удовлетворяют условию: а(=о{в) при
п -> со, то функцию / назовем пороговой функцией 2-го типа (условие (**)).
Обзор полученных результатов.
В главе 1 получены основные результаты для мажоритарных и пороговых функций по переоценке вероятностей значений входных переменных при наблюдении выходных мультиграмм.
В1.1и1.3 решена задача наилучшей переоценки апостериорных вероятностей значений переменных, подающихся на входы функции, по подсистемам систем линейных псевдобулевых неравенств рекуррентного типа, или, что то же самое, указана структура мультиграмм, переоценка вероятностей по которым наилучшая. Оценки длин выходных последовательностей, необходимых для решения систем (2) рекуррентного типа методом максимального правдоподобия (ММП), и трудоемкости алгоритмов для мажоритарных функций и пороговых функций 2-го типа совпадают в асимптотике. Показано, что на длине 0(n) поиск решения системы уравнений рекуррентного типа сводится к построению и решению СЛУ с искаженными правыми частями, при этом вероятность искажения не превосходит в асимптотике некоторую константу, меньшую \. При благоприятном стечении обстоятельств вероятность искажения
стремится к нулю, однако вероятность такого события с экспоненциальной скоростью убывает.
В 1.2 показано преимущество разработанного алгоритма для мажоритарной функции по сравнению с некоторыми другими методами дискретного анализа.
При неизвестном правиле выделения существенных переменных ( 1.4) по входной и выходной последовательностям применение метода переоценки вероятностей приводит к тому, что, используя о(п) знаков выходной последовательности, или - 0(п) уравнений системы (2), можно полностью определить правило выделения существенных переменных с «малыми» весовыми коэффициентами (для пороговых функций 1 -го и 2-го типа). С помощью o(l) знаков находится правило выделения переменных функции с «большими» весовыми коэффициентами (для функций 1-го типа). Показано, что на длине о{п2) знаков выходной последовательности с достаточной надежностью определяется правило выделения существенных переменных для пороговых функций 1-го и 2-го типа при неизвестной входной последовательности. Знание самой функции не требуется. Алгоритм, решающий данную задачу, тривиальный и имеет полиномиальную сложность.
В 1.5 предложен способ восстановления неизвестной пороговой функции по коротким входным и выходным последовательностям: на длине o(n) знаков выходной последовательности (или - с помощью 0{м) уравнений из исходной системы рекуррентного типа) построена пороговая функция, стремящаяся к исходной по вероятности с ростом N.
В 1.6 рассмотрены некоторые статистические аналоги пороговых функций.
В 1.7 с помощью геометрической интерпретации условия задачи переоценка вероятностей для любой пороговой функции без каких-либо ограничений сведена к вычислению интеграла от рациональной функции.
В главе 2 рассмотрены некоторые классы А-значных функций (к 2), к которым применима разработанная методика. Показана возможность быстрой переоценки апостериорных вероятностей для совокупности ограниченного числа пороговых функций с одинаковой линейной псевдобулевой формой и разными порогами ( 2.1); для функций с ограниченным количеством нелинейных членов в псевдобулевой форме ( 2,2); для суперпозиции пороговых функций ( 2.3). В 2.4 указаны условия, налагаемые на весовые коэффициенты, при кото-
рых функции с пороговой структурой (ktl\ к,1йЗ, являются пороговыми. В 2.5 геометрический подход к переоценке вероятности значения переменной, рассмотренный в главе 1, распространен на булевы функции с пороговой структурой (k,l), к, It 2, что фактически означает возможность переоценки для любой булевой функции (или - возможность переоценки вероятности значения переменной по произвольной системе линейных псевдобулевых неравенств).
В 2.6, 2.7,2.8 выведены формулы апостериорных вероятностей для пороговых функций к -значной логики (к > 2 ), Отличительными особенностями здесь являются, во-первых, то, что для любого значения функции существует одно или два значения входной переменной, вероятность переоценки которого 1-наилучшая (см. определение 8). Во-вторых, то, что вероятность переоценки заранее выбранного входного значения по v -грамме, построенной из (v-l)-наилучшей (и-])-граммы, может не являться v -наилучшей (в отличие от булевой пороговой функции).
Практическая значимость результатов диссертации заключается в том, что все предлагаемые автором процедуры доведены до алгоритмов и программ, реализованных в программных комплексах анализа систем линейных псевдобулевых неравенств и синтеза различных параметров дискретных устройств, и позволяют:
получать в режиме реального времени дополнительную информацию о значениях входных переменных по выходу пороговой функции;
сводить решение систем линейных псевдобулевых неравенств рекуррентного типа к решению СЛУ с искаженной правой частью путем выделения подсистем, переоценка вероятностей входов по которым максимальна;
находить с определенной точностью правило выделения существенных переменных и неизвестную пороговую функцию;
локально восстанавливать переменные в произвольных системах с ограниченным числом линейных псевдобулевых неравенств.
Комплексы программного обеспечения, построенные в соответствии с предложенными в диссертации принципами, эксплуатируются в ряде НИР по
анализу систем линейных неравенств, а также в учебном процессе ИКСИ Академии ФСБ РФ.
Апробация и публикации. Основные результаты диссертации прошли апробацию на научно-технических, военно-научных конференциях и семинарах в в/ч 26165, ИКСИ Академии ФСБ, на IV Всероссийском симпозиуме по прикладной и промышленной математике (весенне-летняя сессия 2003 года). Результаты исследований опубликованы в 4 статьях, 2 тезисах докладов.
Сравнительный анализ некоторых дискретных методов для мажоритарных функций
В работах [2, 3] было показано, что при выполнении некоторых условий задача восстановления искаженной ЛРП с помощью локально-статистического метода (ЛСМ) имеет полиномиальную сложность. Пусть числа соотношений st, в которых участвуют переоцениваемые переменные, удовлетворяют неравенст вам s, s сіп—, где Г пр, р 1; вероятность искажения можно считать фиксированной величиной (для разных переменных вероятности переоценок различны, некоторые могут стремиться к единице, но при больших и все ограничены сверху величиной »0.268941). Тогда если число переменных в производных линейных уравнениях фиксировано, р,с 0, то существует a = max)/? +1, 2 + c(l - 2pf2rJ 1 такой, что при Г = па сложность восстановления искаженной рекуррентной последовательности оценивается как Г2 =0{пт), где г тах[з, Д + 1, 2 + с(\-2р) 2г\. Оценка / Дл Ч ЛҐМ7, ]=C?(jV), полученная в теореме 8, используется при решении задачи методом максимального правдоподобия (ММП) или случайного поиска решений, которые имеют экспоненциальную сложность. Длина выходной последовательности, таким образом, влияет на выбор метода решения задачи.
Если ограничение на количество переменных в производных линейных уравнениях не выполняется, то трудоемкость ЛСМ возрастает экспоненциально с ростом N. Как в дальнейшем будет показано для некоторых классов пороговых функций, для переоценки вероятностей значений переменных можно использовать такие v-граммы, что при решении СЛУ с искаженными правыми частями трудоемкость есть полиномиальная величина (апостериорные вероятности стремятся к единице, причем г-граммы появляются в выходной последовательности достаточно часто).
Таким образом, в 1.1, во-первых, найдено количественное выражение дополнительной информации о значениях переменных мажоритарной функции, содержащейся в мультиграммах различной длины в выходной последовательности (для систем рекуррентного типа). Во-вторых, установлена структура мультиграмм (или, что то же самое, структура подсистем булевых систем (0.2) рекуррентного типа с мажоритарной функцией), минимизирующих объем исходной системы (0.2), необходимый для решения систем уравнений с искажениями методом максимального правдоподобия с заданной надежностью.
Одним из универсальных методов решения СБУ рекуррентного типа является метод полного перебора. Он заключается в последовательном опробовании в качестве вариантов решения всех возможных двоичных начальных векторов ЛРП. Его трудоемкость составляет Г0 = o{lN) операций. Для больших значений N использование этого метода неприемлемо. Однако на практике принято сравнивать вновь разработанный алгоритм, в первую очередь, именно с методом полного перебора.
Трудоемкость решения СБУ (0.2) оценивается, какT = Tt + T2t где 7J = 0[N3n) - число операций для составления СЛУ, Тг - сложность решения СЛУ с искаженной правой частью. В общем случае выполняется асимптотическое равенство 7J=o(r2), так как Т2 имеет экспоненциальный характер роста. Величина Т2 исследовалась в работах [2, 3, 6, 8, 38], и для нее можно использовать оценку В предыдущем параграфе было показано, что вероятность искажения асимптотически оценивается сверху числом \-р «0.268941. Тогда верна следующая сравнительная характеристика
Проведем анализ метода линейных статистических аналогов (ЛСА) применительно к дискретному узлу с мажоритарной функцией на выходе. Обозначим вероятность совпадения функций /( ) и ах: Целое число Aj называется коэффициентом статистической структуры функции f(x). Метод ЛСА заключается в следующем: необходимо найти такую булеву линейную функцию ах, для которой коэффициент статистической структуры максимален по модулю; затем в исходной системе заменить функцию /( ) на найденный аналог ах; в результате получится СЛУ с искаженными правыми частями, решение которой (в статистическом смысле) является решением исходной системы.
Переоценка вероятностей совокупностей переменных и о некоторых статистических аналогах пороговых функций
Экспоненциальный характер зависимости от j свидетельствует о том, что алгоритм применим при ограниченном у. Однако его рекомендуется использовать на начальном этапе исследования системы линейных псевдобулевых неравенств, поскольку он может привести к сокращению числа неравенств в системе без потери равносильности. Введение нелинейных членов в псевдобулевые неравенства усложнит переоценку, но при их ограниченном количестве следует решать задачу с помощью разложения системы по переменным.
Такой подход правомерен, если исходная система неравенств - случайная (результат каких-либо наблюдений, оценок, измерений и т.д.). Признаками случайной системы обладает и итоговая, результирующая система неравенств, построенная в качестве равносильной для некоторой системы булевых уравнений.
Переоценка вероятностей по системе ограниченного количества псевдобулевых неравенств с использованием геометрического подхода Рассмотренные в 2.4 соотношения между весовыми коэффициентами не охватывают все возможные случаи взаимного расположения двух различных плоскостей в я -мерном пространстве. Тем не менее при решении рассматри ваемой задачи представляется целесообразным проверка этих соотношений, так как при их выполнении дальнейшие вычисления вероятностей переоценок значительно упрощаются. Предположим теперь, что не выполняется ни одно из соотношений 1.1-1.3. Рассмотрим общую задачу оценки вероятности события без ограничения общности положим af = Х = 1. Идея подсчета этой вероятности заключается в вычислении площади поверхности части сферы, заключенной между граничными плоскостями. Площадь будем вычислять двумя способами. Первый способ основан на оценке площади поверхности части сферы, являющейся пересечением сферы с семейством некоторого пучка плоскостей [21]. Второй способ заключается в последовательном пересечении со сферой плоскостей Ц = с, и Lj = с2. Второй способ является универсальным, он применим для вычисления площади части сферы, являющейся пересечением ограниченного числа гиперполупространств, 1 способ. Рассмотрим пучок плоскостей, проходящих через гиперпрямую, являющуюся пересечением плоскостей Ц{х) = сх и Zj(x) = c2. Общее уравнение произвольной плоскости пучка имеет вид: Условию (17) удовлетворяют и вершины куба .V, заключенные «между» плоскостями , = сх и Ц=с2. Оценкой вероятности события А и В служит величина, равная площади поверхностей семейства (я-1)-мерных сфер, являющихся пересечением п -мерных сферы Г„ и плоскости L, = 0, заданной уравнением (16), для всех t с, деленной на площадь поверхности и-мерной сферы я, Вновь произведем преобразования системы координат, описанные в 1.7. Получим следующие уравнения плоскости и сферы: Вычисление интегралов I носит предварительный характер. Обе оценки вероятностей верны для произвольного и, большего 1, отсутствуют всякие ограничения на весовые коэффициенты. Второй способ можно применять к оценке вероятностей событий, являющихся пересечением конечного числа гиперполупространств. Данный метод и последние замечания значительно расширяют класс булевых функций от п переменных, для которых удается получить вероятности переоценок значений любых входных переменных по выходу функции, значений любых совокупностей переменных по выходу функции, рассчитать приблизительную весовую структуру. Для систем (0.2) рекуррентного типа с максимальной кратностью k = l (определение 0.13) можно рассчитывать вероятности переоценок по выходным мультиграммам. Пример 13. Оценим с помощью разработанного в параграфе метода вероятность события Полученное значение достаточно точно согласуется с практикой. Предлагается следующий алгоритм локального решения системы линейных псевдобулевых неравенств: а) перебор всевозможных подсистем исходной системы, состоящих из к нера венств, к - ограниченное наперед заданное число; б) для каждой подсистемы переоценка вероятностей значений переменных по подсистеме; 115 в) если вероятность переоценки некоторой переменной стремится к единице (нулю), проверяем ее значение по другим неравенствам, не вошедшим в под систему; г) считаем данную переменную локально восстановленной, если ее значение не противоречит проверяемым неравенствам. Трудоемкость алгоритма не превосходит величины nML, где К - число не равенств в исходной системе, М - трудоемкость пункта б (рекомендуется все однотипные вычисления провести на предварительном этапе, тогда величина М окажется константой), L = 0(п) - трудоемкость проверки непротиворечивости неравенства после подстановки в него варианта решения.
Переоценка вероятностей для функций с нелинейными членами в псевдобулевом задании
В диссертации разработана методика получения дополнительной информации относительно значений входных переменных булевой функции по ее выходным значениям при использовании псевдобулевого способа задания, имеющая невысокую вычислительную сложность. Построенные алгоритмы применимы для расширения возможностей решения систем псевдобулевых неравенств, восстановления различных параметров дискретных устройств, настройки нейросетей с независимыми входами.
В главе 1 получены основные результаты для мажоритарных и пороговых функций по переоценке вероятностей значений входных переменных при наблюдении выходных мультиграмм. Для систем рекуррентного типа указана структура мультиграмм, переоценка вероятностей по которым наилучшая. Показано, что на небольшой длине поиск решения системы линейных неравенств рекуррентного типа сводится к построению и решению СЛУ с искаженными правыми частями. Разработан и проанализирован алгоритм выделения существенных переменных пороговой функции по входной и выходной (или только по выходной) последовательностям ограниченной длины. Построен теоретико-вероятностный метод восстановления пороговой функции, стремящейся по вероятности к неизвестной исходной пороговой функции. С помощью геометрической интерпретации условия задачи получена возможность переоценки вероятностей для произвольной пороговой функции без каких-либо ограничений на весовые коэффициенты.
В главе 2 рассмотрены некоторые классы Jt-значных функций (k 2), к которым применима разработанная методика. Показана возможность быстрой переоценки апостериорных вероятностей для совокупности ограниченного числа пороговых функций с одинаковой линейной псевдобулевой формой и разными порогами; для функций с ограниченным количеством нелинейных членов в псевдобулевой форме; для суперпозиции пороговых функций. Получены условия, накладываемые на весовые коэффициенты, при которых функции с пороговой структурой (k,l),, k,l 3, являются пороговыми. Геометрический подход к переоценке вероятностей значений переменных распространен на произвольную булеву функцию с ограниченной пороговой структурой, что фактически означает возможность переоценки вероятностей для любой булевой функции. Рассмотрены вопросы получения дополнительной информации о значениях входов по выходам для пороговых функций jt-значной логики (к 2).
В результате проведенных в диссертации исследований установлено, что для расширения возможностей решения систем линейных псевдобулевых неравенств, восстановления различных параметров дискретных устройств, повышения скорости настройки нейросетевых моделей необходима разработка математического аппарата анализа булевых функций с использованием их псевдобу-левого способа задания. Эта задача была решена на основе переоценки вероятностей для пороговых функций, а также - с помощью геометрического подхода -для произвольных булевых функций с ограниченной пороговой структурой.
Основные результаты диссертационной работы заключаются в следующем. 1. Разработана методика подсчета апостериорных вероятностей значений входных переменных по одному выходному значению пороговой функции. 2. Построен алгоритм поиска в исходной системе рекуррентного типа подсистем линейных псевдобулевых неравенств специального вида, переоценка вероятностей значений входных переменных по которым максимальна. 3. Предложен способ восстановления неизвестной пороговой функции по коротким входным и выходным последовательностям. 4. Описана процедура построения каскада пороговых функций (нейросети) по независимым в совокупности входным и выходной учебным последовательностям. 5. Разработан метод подсчета весов всех подфункций произвольной булевой функции с ограниченной пороговой структурой. На защиту выносятся следующие результаты. Вероятностно-статистический метод анализа систем линейных псевдобулевых неравенств. Алгоритм решения систем линейных псевдобулевых неравенств, основанный на вероятностно-статистическом методе. Построенный алгоритм распространен на системы с произвольными булевыми уравнениями. К нерешенным проблемам по данной тематике можно отнести следующие: получение дополнительной информации относительно входов по выходу для пороговой функции при условии, что некоторые входные переменные зависимы; распространение геометрического подхода на функции -значной логики (k 2); разработка метода решения систем псевдо-А-значных неравенств с использованием вероятностно-статистического подхода. Решение данных проблем помогло бы перейти к рассмотрению вопросов теоретического обоснования правильности настройки и работы различных ней-росетевых и генетических алгоритмов. В заключение автор хотел бы выразить глубокую благодарность научному руководителю д.т.н. Никонову Владимиру Глебовичу за помощь, оказанную при проведении исследований и написании работы; признательность за критику и помощь д.ф.м.н. Балакину Геннадию Васильевичу, к.т.н, Коновальчику Павлу Михайловичу, д.ф.м.н. Алиеву Физули Камиловичу, к.ф.м.н. Колпакову Сергею Анатольевичу, к.ф.м.н. Мельникову Сергею Юрьевичу, к.ф.м.н. Смирнову Владимиру Георгиевичу, к.т.н. Поспелову Гелию Ивановичу.
Переоценка вероятностей по системе ограниченного количества псевдобулевых неравенств с использованием геометрического подхода
Во всех шести случаях взаимных расположений д,, ,, сх на числовой прямой рассмотрены условия, налагаемые на весовые коэффициенты линейных псевдобулевых форм і,, L;, L) у при которых переоценка вероятностей по системе трех неравенств сводится к переоценке вероятностей по системе двух неравенств. По существу это означает, что два неравенства поглощают третье. В геометрическом смысле - множество вершин куба, отделяемое одной плоскостью, является подмножеством множества вершин, отделяемых двумя другими плоскостями. Подобным образом можно анализировать и другие булевы функции с ограниченной пороговой структурой. Однако на примере функций с пороговой структурой (к, /), 2 к, I , 3, видно, что трудоемкость такой задачи растет с экспоненциальной скоростью.
Исходя из полученных для системы двух неравенств результатов построим алгоритм, уменьшающий при выполнении определенных условий количество неравенств в исходной системе (0.3).
Пусть исходная система (0.3) случайная и состоит из к псевдобулевых неравенств. Перебираем всевозможные пары неравенств. Если для очередной пары неравенств при некоторой фиксации j переменных весовые коэффициенты и пороги удовлетворяют одному из условий 1.1-1.3, то разбиваем систему по полной группе событий по j переменным. Далее исключаем из системы без нарушения равносильности соответствующее неравенство при фиксации определенными значениями переменных xi„,.,xi .
В результате работы алгоритма получится совокупность подсистем из менее чем к неравенств, в которых некоторые переменные зафиксированы всеми возможными двоичными значениями. Трудоемкость Т алгоритма можно оценить так: перечисление пар неравенств - операции, для каждой пары переор всех фиксаций до у переменных включительно - 2 операций, проверка условий 1.1-1.3 - 0(l) операций, упорядочение коэффициентов требует ((n j)ln(n J )) операций. Следовательно, трудоемкость оценивается величиной
Экспоненциальный характер зависимости от j свидетельствует о том, что алгоритм применим при ограниченном у. Однако его рекомендуется использовать на начальном этапе исследования системы линейных псевдобулевых неравенств, поскольку он может привести к сокращению числа неравенств в системе без потери равносильности. Введение нелинейных членов в псевдобулевые неравенства усложнит переоценку, но при их ограниченном количестве следует решать задачу с помощью разложения системы по переменным. Такой подход правомерен, если исходная система неравенств - случайная (результат каких-либо наблюдений, оценок, измерений и т.д.). Признаками случайной системы обладает и итоговая, результирующая система неравенств, построенная в качестве равносильной для некоторой системы булевых уравнений. Переоценка вероятностей по системе ограниченного количества псевдобулевых неравенств с использованием геометрического подхода Рассмотренные в 2.4 соотношения между весовыми коэффициентами не охватывают все возможные случаи взаимного расположения двух различных плоскостей в я -мерном пространстве. Тем не менее при решении рассматри ваемой задачи представляется целесообразным проверка этих соотношений, так как при их выполнении дальнейшие вычисления вероятностей переоценок значительно упрощаются. Предположим теперь, что не выполняется ни одно из соотношений 1.1-1.3. Рассмотрим общую задачу оценки вероятности события без ограничения общности положим af = Х = 1. Идея подсчета этой вероятности заключается в вычислении площади поверхности части сферы, заключенной между граничными плоскостями. Площадь будем вычислять двумя способами. Первый способ основан на оценке площади поверхности части сферы, являющейся пересечением сферы с семейством некоторого пучка плоскостей [21]. Второй способ заключается в последовательном пересечении со сферой плоскостей Ц = с, и Lj = с2. Второй способ является универсальным, он применим для вычисления площади части сферы, являющейся пересечением ограниченного числа гиперполупространств, 1 способ. Рассмотрим пучок плоскостей, проходящих через гиперпрямую, являющуюся пересечением плоскостей Ц{х) = сх и Zj(x) = c2. Общее уравнение произвольной плоскости пучка имеет вид: Условию (17) удовлетворяют и вершины куба .V, заключенные «между» плоскостями , = сх и Ц=с2. Оценкой вероятности события А и В служит величина, равная площади поверхностей семейства (я-1)-мерных сфер, являющихся пересечением п -мерных сферы Г„ и плоскости L, = 0, заданной уравнением (16), для всех t с, деленной на площадь поверхности и-мерной сферы я,
