Вероятностные методы в пороговой логике Зуев, Юрий Анатольевич

Введение к работе

Актуальность темы исследования. Булева функция / : {0,1} —> {0,1} называется пороговой, если существует линейное неравенство с действительными коэффициентами

aixi + ... -f а_пх_п < b, (1)

выполненное на тех и только тех булевых наборах х = (xi,... ,х_п), для которых /(х) = 0. Коэффициенты а,{ называются весами, b - порогом.

Как обычно, булев набор длины п можно интерпретировать либо как подмножество тг-элементного множества, либо считать его вершиной n-мерного единичного куба. Пороговая функция задается при этом гиперплоскостью, рассекающей n-мерный куб так, что в вершинах по одну сторону гиперплоскости функция равна нулю, по другую - единице. Подмножество вершин куба {0,1}" будем называть пороговым, если оно отделимо от своего дополнения гиперплоскостью.

Небольшим изменением порога или весов для пороговой функции всегда можно добиться строгого разделения гиперплоскостью ее нулевых и единичных вершин так, чтобы ни одна из вершин куба не лежала в гиперплоскости. Отметим также, что значения весов и порога всегда могут быть взяты рациональными, а стало быть и целыми.

История пороговой логики насчитывает уже более полувека и связана с исследованиями по моделированию биоло-

гических систем, синтезом схем из функциональных элементов, искусственным интеллектом, целочисленным программированием, проблемой повышения надежности информации и рядом других современных направлений науки. Столь широкая область ее применения объясняется, по-видимому, тем "переходом количества в качество", который реализуется в пороговом элементе (1).

Понятие пороговой булевой функции впервые появилось в 1943 году в работе Маккаллока и Питтса (Маккаллок У.С., Питтс У. Логическое исчисление идей, относящихся к нервной активности // Автоматы. - М.:ИЛ. 1956, с. 362-384.), предложивших пороговый элемент в качестве математической модели нервной клетки - нейрона. Эти идеи, развитые в дальнейшем Розенблаттом, впервые показавшим адаптивные возможности такой модели, стали органической частью теории искусственных нейронных сетей - важного направления современных исследований по искусственному интеллекту.

Одновременно пороговые функции простотой своей технической реализации привлекли внимание исследователей, работавших над проектированием ЭВМ. Это привело в начале шестидесятых годов к бурному росту исследований по пороговым функциям и функциональным возможностям синтеза в пороговом базисе, т.е. по проблематике, объединений в настоящее время под общим термином "пороговая логика". Обзор результатов за этот период можно найти в монографии Муроги (Muroga S. Threshold logic and its applications. -N.Y.: Wiley, 1971). Отметим также работы Э.И.Нечипорука и О.Б.Лупанова, в которых найдена асимптотическая сложность схем в пороговом базисе.

При реализации функций алгебры логики схемами из пороговых элементов число N_u пороговых функций от п пере-

менных служит естественной мерой разнообразия порогового базиса и позволяет оценивать сложность таких реализаций. Это явилось причиной пристального внимания к проблеме подсчета N_n с конца пятидесятых годов. Однако даже получение асимптотики логарифма этого числа вызвало значительные трудности.

Здесь будет удобно перейти к другому, так называемому однородному представлению для пороговых функций. Булевой функцией будем считать отображение / : {—1,1}" -» {—1,1}. Тогда пороговую функцию можно представить в виде

/(у) = sgn(a₀ + aiyi + ... + а_пу_п), (2)

считая, что линейная форма ни на одном из наборов {—1,1}" не обращается в нуль. Геометрически (2) соответствует переходу от куба {0,1}" к кубу {—1,1}". Связь между переменными г/і и Х{ задается соотношением у і = 2х,- — 1. Поэтому коэффициенты оі,... ,о„ в (2) те же, что и в (1), а обобщенный порог, или смещение, До равен $3₌₁ ^а> ~ ^Ь.

Для произвольного весового вектора a = (ao,ai,... ,а_п) весовой вектор а = (tao,tai,.. .,ta„) при t > 0 задает ту же самую пороговую функцию (2). Поэтому множество весовых векторов, задающих одну и ту же пороговую функцию, является конусом в пространстве Eⁿ⁺¹ = (оо, ai, . , о„). Число пороговых функций оказывается, таким образом, равным числу выпуклых многогранных конусов, на которые E^n+l разбивается 2" гиперплоскостями вида

а_о±аі...±а_п=0. (3)

Как было показано в середине девятнадцатого века Людвигом Шлефли, число конусов, на которые m-мерное простран-

ство разбивается К гиперплоскостями, проходящими через начало координат и находящимися в общем положении, равно

Гиперплоскости (3) находятся не в общем положении, что приводит к уменьшению числа конусов. Поэтому из (4) следует верхняя оценка для числа пороговых функций

v^/2"-l\ 2"²

Это дает log₂ N_n < п~. Другими методами к 1965 году независимо рядом исследователей было получено log₂ N_n > n²/2. Эти оценки не удавалось улучшить до 1989 года, когда автором было показано, что

log₂ N_n ~ га², п-> оо. (5)

При получении этого результата автором были открыты новые геометрические свойства разбиения пространства гиперплоскостями, а также использованы свойства случайных ±1-матриц, установленные Комлошом (J.Komlos) и Одлыжко (A.M.Odlyzko).

Другой областью знаний, поддерживающей интерес к пороговой логике, является теория целочисленного программирования. В самом деле, одной из наиболее известных NP-полных задач линейного булева программирования является задача о ранце:

максимизировать

$>ач (6)

при условии

^aiXi (7)

<=і где переменные Хі булевы, а коэффициенты Cj,

При естественной экономической интерпретации задачи переменные Хі соответствуют проектам, которые могут быть осуществлены, а; - стоимость г-го проекта, с,- - получаемый в результате его реализации доход. Таким образом, областью допустимых решений задачи о ранце является множество нулей монотонной булевой функции. Строение этого множества определяет алгоритмическую трудность решения задачи.

В задачах линейного булева программирования допустимая область может быть задана не одним, а системой неравенств. При этом возникает задача агрегирования их числа, т.е. замена их меньшим числом без изменения допустимой области. Изучение подобных вопросов привело к изучению пороговых представлений булевых функций - таких представлений с помощью систем линейных неравенств, когда допустимые для системы булевы наборы и только они являются нулями булевой функции. Геометрически пороговое представление булевой функции сводится к отсечению гиперплоскостями всех ее единичных, вершин. Минимальное число t[j) необходимых для этого линейных неравенств называется пороговым числом булевой функции / и наряду с длиной ее кратчайшей дизъюнктивной нормальной формой (д.н.ф.) может считаться мерой ее сложности.

За последние 20 лет выявились также интересные связи между пороговой логикой и теорией графов. Монотонная булева функция называется графической, если все ее нижние единицы находятся в слое 2, т.е. в ее сокращенную д.н.ф. входят только двухбуквенные конъюнкции. Графические функции от п переменных находятся во взаимно однозначном соответствии с n-вершинными графами, вершины которых соответствуют переменным, а ребра - конъюнкциям. Граф называется пороговым, если соответствующая ему графическая функция является пороговой. На языке теории графов по-роговость графа эквивалентна существованию линейного неравенства, отделяющего независимые подмножества его вершин от зависимых. Введенные Хваталом и Хаммером (Chvat Chvatal V., Hammer P.L. Aggregation of inequalities in integer programming // Annals of Discrete Mathematics. - 1977. - N 1. - P. 145-162), пороговые графы вызвали интерес у специалистов по теории графов и нашли применение при управлении параллельными вычислительными процессами.

Значительный интерес представляют новейшие результаты, связанные с целочисленной реализацией пороговых функций. Основной вопрос здесь состоит в оценке диапазона весов, достаточного для реализации любой пороговой функции от п переменных.

Из (5) и элементарных мощностных соображений вытекает существование пороговых функций, для которых

tog₂ W >« Такие функции были построены и в явном виде. Однако верхняя оценка, основанная на неравенстве Адамара для модуля определителя, давала

Впервые пример пороговой функции, при целочисленной реализации которой требуются веса сц такие, что

lg₂ kl ~ ^nlog₂n,

удалось построить Хастаду (Hastad J. On the size of weights for threshold gates // SIAM J. Discrete Math. - 1994. - V. 7. -P. 484-492), а Алоном и др. (Alon N., Vu V.H. Anti-Hadamard Matrices, Coin Weighing, Threshold Gates, and Indecomposable Hypergraphs II J. Combin. Theory, A. - 1997. - V.79. - P. 133-160) были указаны интересные связи этой задачи с задачей обращения ±1 матрицы, взвешиванием монет и другими математическими проблемами.

Хотя современная история пороговой логики насчитывает немногим более полувека, мажоритарная пороговая функция

xi +- ...+х_п< (n-1)/2,

задающая метод принятия решения простым большинством издревле использовалась человечеством, как наиболее справедливый метод принятия коллегиального решения при наличии двух альтернатив. Ее универсальность связана, по-видимому, с тем, что при нечетном п это единственная функция, являющаяся одновременно симметрической, монотонной и самодвойственной.

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

ны р > 1/2 и принимаемые решения независимы. Приоритет здесь принято отдавать французскому академику XVIII века Кондорсе, который показал, что вероятность ошибки мажоритарного решения в этом случае с ростом числа членов коллектива монотонно стремится к нулю.

В технических приложениях подобная модель нашла свое применение в середине двадцатого века в работе Джона фон Неймана (Нейман Дж. Вероятностная логика и синтез надежных организмов из ненадежных компонент. - В сб.: Автоматы. - М.: ИЛ, 1956, с. 68-139), чьи идеи вызвали целый поток исследований по повышению надежности логических схем и автоматов. Мажоритарный принцип нашел применение также в системах помехоустойчивого кодирования информации при построении декодеров.

В начале шестидесятых годов независимо рядом исследователей было подмечено, что при статистической независимости ошибок отдельных членов коллектива оптимальное коллективное решающее правило является взвешенным голосованием, т.е. пороговой решающей функцией. Статистические свойства взвешенного голосования изучались Пирсом (Пирс У. Построение надежных вычислительных машин. М: Мир, 1968), оценившим вероятность ошибки сверху, а также указавшим на возможность самообучения процедуры взвешенного голосования.

Для наглядного представления вероятностной модели, а также указания на возможную область применения результатов рассмотрим многоканальную систему передачи информации, по каждому из п каналов которой в каждый момент времени передается один и тот же символ из алфавита {—1,1}, но в процессе передачи в канале он может с некоторой вероятно-

стью измениться на противоположный. Когда по системе передается сигнал z Є { — 1,1}, то на выходе г-го канала принимается сигнал уі Є { — 1,1}, который с вероятностью р; > 1/2 совпадает с г и с вероятностью 1 — р; противоположен ему, причем эти вероятности не зависят от значения z. Априорные вероятности обоих значений сигнала z одинаковы и равны 1/2, каналы независимы. Требуется по принятому вектору у = (г/і,..., у_п) с максимальной достоверностью восстановить переданный символ г.

При перечисленных условиях оптимальное решающее правило /(у), выбирающее для каждого у Є {—1,1}" наиболее вероятное значение для z, является пороговой функцией

/(у) = sgn(ai?/i + ... + а_пу_п) = sgn(a,y),

где a; = log(pi/(l — pi)), а вероятность его ошибки была оценена сверху Пирсом как

п Рош <П²>/М1-Л)-

1=1

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

В тех случаях, когда вероятности ошибок в каналах неизвестны или нет достаточных оснований считать каналы независимыми, для получения близкого к оптимальному решающего правила естественно провести обучение решающего правила следующим образом. По многоканальной системе передается некоторая конечная тестовая последовательность символов zi,Z2,- и выбирается пороговая функция, правильно

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

_а _ Г а_к, если sgn(a_k,y_k) = 2_b

^k+1 \а_к + ^у_к, если sgn(a_k,y_k) ф z_k.

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

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

Автором совместно с С.К.Ивановым был разработан алгоритм подстройки весов "ускоренный персептрон", в котором принцип адаптации, заложенный в персептроне Розен-блатта, соединен с принципом самообучения, сформулированным Пирсом.

Цель работы. Основной целью диссертационной работы являлось установление связей между пороговой логикой и теорией вероятностей. Вероятностные методы, впервые примененные автором в пороговой логике, явились мощным средством получения в ней новых результатов и позволили сдвинуть с места проблемы, десятилетиями остававшиеся без движения. Найденная автором связь между задачей подсчета числа пороговых функций и свойствами случайных ±1-матриц позволила добиться существенного прогресса в этой классической проблеме пороговой логики. Однако связь между теорией вероятностей и пороговой логикой оказывается двусторонней, и методами пороговой логики в диссертации успешно решается одна из старейших задач теории вероятностей -оценка вероятности ошибки оптимального коллегиального решения.

Методы исследования. В работе используются методы комбинаторного анализа, теории вероятностей, линейной алгебры и многомерной геометрии.

Научная новизна. Все основные результаты диссертации являются новыми и опубликованы в работах автора. В диссертации получены следующие основные результаты:

1. найдена асимптотика логарифма числа пороговых функций от п переменных;

2. установлен порядок вероятности ошибки оптимального коллегиального решения;

3. разработан, теоретически исследован и подтвержден мо-

дельными экспериментами алгоритм обучения и самообучения процедуры взвешенного голосования "ускоренный пер-сентрон";

4. найдены асимптотики логарифма числа пороговых множеств различной мощности;

5. получена верхняя оценка для максимального значения порогового числа в классе монотонных булевых функций;

6. получен порядок типичного значения порогового числа в классе монотонных булевых чисел.

При этом результаты 1, 2 и 5 получены лично авторов. Результат 3 получен совместно с С.К.Ивановым, а результаты 4, 6 - совместно с Л.И.Липкиным, причем в обоих случаях соавторства автору принадлежала ведущая роль в научных исследованиях.

Теоретическая и практическая ценность. Работа носит теоретический характер, но разработанный автором алгоритм "ускоренный персептрон" может найти применение в задачах принятия решений, передачи и обработки информации.

Апробация работы. Результаты диссертации докладывались на международных конференциях "Математические модели в теории управляющих систем" (Красновидово, 1995), "Проблемытеоретической кибернетики" (Красновидово, 1996), на конгрессе по прикладной и индустриальной математике ИНПРЙМ-96 (Новосибирск, 1996), в Вычислительном центре РАН на семинарах под руководством академика РАН Ю.И. Журавлева, в МГУ на семинарах по математическим вопросам кибернетики под руководством член.-корр. РАН С.В.Яблонского, на семинаре отдела дискретной математики Математического института им. Стеклова РАН, на семинаре в Институте математике Сибирского отделения РАН, на дру-

гих конференциях, школах, семинарах. Исследования по теме диссертации поддерживались грантами Российского фонда фундаментальных исследований, выделявшимися по проектам N 94-01-00423-а, N 95-01-01492-а и N 97-01-0024-а, руководителем которых был автор. Материалы диссертации использовались автором в спецкурсах, читавшихся им на протяжении ряда лет на факультете Вычислительной математики и кибернетики Московского государственного университета им. Ломоносова.

Публикации. Основные результаты диссертации опубликованы в работах [1-21], список которых приводится в конце автореферата.

Структура и объем работы. Диссертация состоит из введения, 4 глав, заключения и списка литературы. При этом первые две главы посвящены метрическим (количественным) свойствам пороговых функций, а в двух последних главах изучаются статистические свойства процедур взвешенного голосования. Каждая из глав разбита на три раздела. Для обозначений определений, утверждений, лемм, теорем и следствий используется трехзначная нумерация, где первая цифра обозначает номер главы, вторая - номер раздела в главе и третья - порядковый номер утверждения в разделе. Объем работы - 126 страниц. Список литературы содержит 106 наименований.