Вероятностные методы в пороговой логике

Зуев, Юрий Анатольевич

Вероятностные методы в пороговой логике тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

Зуев, Юрий Анатольевич АВТОР

доктора физико-математических наук УЧЕНАЯ СТЕПЕНЬ

Москва МЕСТО ЗАЩИТЫ

1998 ГОД ЗАЩИТЫ

01.01.09 КОД ВАК РФ

Диссертация по математике на тему «Вероятностные методы в пороговой логике»

Автореферат диссертации на тему "Вероятностные методы в пороговой логике"

Российская Академия наук Вычислительный центр

на правах; рукописи

( 1-,-н

ЗУЕВ Юрий Анатольевич

-РОЯТНОСТНЫЕ МЕТОДЫ В ПОРОГОВОЙ ЛОГИКЕ

Специальность 01.01.09 - математическая кибернетика

АВТОРЕФЕРАТ

диссерации на соискание ученой степени доктора физико-математических наук

Москва - 1998

Работа выполнена в Вычислительном центре Российской Академии наук

Официальные оппоненты:

доктор физико-математичкских наук, профессор В.А.Ватутин

доктор физико-математичкских наук, профессор А.А.Сапоженко

доктор физико-математичкских наук, профессор В.Н.Шевченко

Институт математики Сибирского отделения РАН

11 часов 00 минут на заседании Диа. _ _____ _ _ .. _ _ _________

при Московском государственном университете имени М.В.Ломоносова по адресу: 119899, Москва, ГСП, Воробьевы горы, МГУ, факультет ВМиК, аудитория 685.

С диссертацией можно ознакомиться в библиотеке факультета ВМиК.

Ведущая организация:

Защита диссертации состоится

Автореферат разослан

Ученый секретарь Диссертационного совета профессор

Н.П.Трифонов

Общая характеристика работы

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

ахх 1 + ...-+- апхп < 6, (1)

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

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

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

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

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

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

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

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

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

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

/(у) = sgn(a0 + а\у\ + ... + апуп), (2)

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

Для произвольного весового вектора а = (во,аь... ,ап) весовой вектор ia = (too, tai,..., ta„) при t > 0 задает ту же самую пороговую функцию (2). Поэтому множество весовых векторов, задающих одну и ту же пороговую функцию, является конусом в пространстве En+i = (ао, ai, •. ■, а„). Число пороговых функций оказывается, таким образом, равным числу выпуклых многогранных конусов, на которые Еп+1 разбивается 2" гиперплоскостями вида

а0 ± ai... ± ап = 0. (3)

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

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

(4)

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

Это дает \(%2 ЛГ„ < гг. Другими методами к 1965 году независимо рядом исследователей было получено 1о£2 Аг„ > п2/2. Эти оценки не удавалось улучшить до 1989 года, когда автором было показано, что

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

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

log2 Nn ~ га2, п-> оо.

(5)

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

при условии

^ ад < ъ,

(7)

<=1

где переменные х,- булевы, а коэффициенты <?,, а,, 6 - неотрицательные действительные числа.

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

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

За последние 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) и элементарных мощностных соображений вытекает существование пороговых функций, для которых

bg2 W > п.

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

log2 [Oil < ^nlog2 п.

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

l°g2 kl ~ 7¡nlog2n,

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

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

xi-f...+a;„< (га- 1)/2,

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

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

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

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

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

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

/(у) = вял(в12/1 + ... + а„р„) = sgn(a,y),

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

Рош <П

¿=1

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

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

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

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

/ ак' ак+1 = <

I ак

ак, если sgn(ak,yk) = гк,

ак + гкук, если sgn(ak, ук) ф гк.

(8)

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

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

Содержание диссертационной работы

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

Определение 1.1.1. Расположение гиперплоскостей в т-мерном евклидовом пространстве называется квазиобщим, если пересечение любых г гиперплоскостей имеет размерность т — i или пусто.

Лемма 1.1.1. Число многогранных областей, на которые m-мерное евклидово пространство разбивается конечным множеством гиперплоскостей, всегда не меньше полного числа всевозможных аффинных подпостранств, порожденных пересечениями гиперплоскостей, считая подпространства всех размерностей от 0 (точки) до т — 1 (сами гиперплоскости) и т (все ш-мерное пространство). Причем равенство имеет место в том и только в том случае, когда расположение гиперплоскостей квазиобщее.

Определение 1.1.2. ±1-матрица А(р,т) с р строками и т столбцами обладает свойством Одлыжко, если в линейном замыкании ее строк не содержится ±1-векторов, отличных от строк матрицы А и им противоположных.

Теорема 1.1.1. Пусть свойство Одлыжко выполнено для почти всех матриц А(р, п + 1), где р — р(п), п —> сю. Тогда для числа Nn пороговых функций справедлива асимптотическая оценка

21"1

ЛnZ2-r- ^

Из теоремы 1.1.1 и из того, что почти матрицы А(р, п + 1) при р — п — о(п) обладают свойством Одлыжко, вытекает

Следствие 1.1.1. Для логарифма числа Nn пороговых функций от п переменных имеет место асимптотика

]og/V„ ~ n2, Tl —> 00.

Если верно, что почти все rbl-матрицы А{п, п+1) обладают свойством Одлыжко, то

Nn ~ 2—, я ->• оо. п!

Теорема 1.3.1. С ростом п при заданном характере изменения М(п) для логарифма числа Nn(M) пороговых множеств мощности М имеет место следующее асимптотическое поведение:

1) если М = о(п), то log Nn ~ щ

2) если М = сп(1 + о(1)), то logJV„(M) ~ n(elog(l + 1/с) + log(l + c) + l);

3) если М = а(тг)п, где а(п) —> оо, loga(n) = <5(logn), то log Nn(M) ~ re loga (ra);

4) если M = nc+o(1*, где с > 1, то log7V„(M) ~ (c-l)relogn;

5) если М = где lim(/3(re)/log re) = оо, /?(п) = о(п), то log Nn(M) ~/3(п)п;

6) еслиМ = 2от'1+°11)>, где 0 < с < 1, то log Nn(M) ~ стг2.

Вторая глава диссертации посвящена пороговым представлениям булевых функций. Центральными здесь являются теоремы 2.2.1, 2.3.1 и 2.3.2.

Теорема 2.2.1. Существует функция т(п) такая, что при п —»• оо для почти всех булевых функций / от п переменных t(f) ~ т(гг). Для т(п) справедливы оценки

27(с1 + 1)п<Ф)<1пп2"/п,

где с\ и 3,41 - корень уравнения

с 1о5(1 + 1 /с) + ^(1 + с) - с = 0.

Теорема 2.3.1. Существует функция в(п) такая, что при п —> оо для почти всех монотонных булевых функций (р от п переменных ~ 0(п). Для 0(п) справедливы оценки

Теорема 2.3.2. Максимальное значение порогового числа в классе монотонных булевых функций асимптотически не превосходит \п/п, где Хп~ максимальная мощность объединения в «-мерном кубе единичных шаров Хемминга с попарно несравнимыми центрами.

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

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

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

где С2 ~ 4,76 - корень уравнения

1/2 + (с + 1/2) log(c +1/2) - с loge - с/2 = 0.

Теорема 3.3.1. Пусть 1/2 < т < р{ < М < 1, г = 1,2,...,п. Тогда для вероятности ошибки оптимального решающего правила справедливы оценки

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

а/,:т1 = ак + гкук, а в режиме самообучения

а£+1 = + sgn(aьyfc)yfc.

Поведение ускоренного персептрона в режиме обучения с учителем достаточно просто и описывается следующей теоремой.

Теорема4.1.1. Пусть ар -барицентрический вектор: ар = (2р1- 1,.. .,2р„-1), и пусть (а^,у) ф 0 для всех у е {-1,1}". Тогда при обучении с учителем бесконечная последовательность пороговых функций, порожденных ускоренным персептроном, с вероятностью 1 стабилизируется на барицентрической функции /Ду) = 8вп(а^,у).

Сложнее поведение ускоренного персептрона в режиме самообучения.

Определение 4.2.1. Вектор

М(/)= ^ Р(У)ДУ)У = М(/(У)У)

называется моментом функции где Р(у)- вероятность появления вершины у :

р(У) = ^Р{У1* = 1} + |Р{У1* = -1}.

(Термин подсказан аналогией с механикой.)

Определение 4.2.2. Самодвойственная пороговая функция / называется устойчивой, если /(у) = у), т.е. момент //(/) принадлежит конусу весовых векторов, задающих /.

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

Теорема 4.2.2. При статистически независимых каналах с вероятностями правильной передачи р1 > 1/2 + с, г = 1,2,..., п, с > 0, множество устойчивых функций / в положительном ортанте весов не пусто, момент /¿(/) каждой из них имеет вид

МЛ = (2Р(/)-1)а/, + е(/),

где

Р(/) = Р щгц > 0|г = 1} - вероятность правильного

решения для функции /;

а;) = (2р1 — 1,2р2 —1, •■• ,2рга — 1) - барицентрический вектор;

|е| < 4л/гаехр(—2тгс4).

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

Публикации по теме диссертации

1. Зуев Ю.А., Тришин В.П. Нижняя оценка числа неравенств, представляющих монотонную булеву функцию от п переменных // Журн. вычисл. математики и матем. физики. - 1983. - Т. 23, N3.-0. 754-756.

2. Зуев Ю.А., Тришин В.Н. О связи линейных неравенств с монотонными булевыми функциями // Журн. вычислит, математики и матем. физики. - 1984. - Т. 24, N 5. - С. 780-781.

3. Зуев Ю.А. О представлении булевых функций системами линейных неравенств // Кибернетика. - 1985. - N 5. - С. 7-9, 40.

4. Зуев Ю.А. О статистических свойствах принятия решения большинством голосов в задачах классификации // Докл. АН СССР. - 1986. - Т. 288, N2.-0. 320-322.

5. Зуев Ю.А. Вероятностная модель комитета классификаторов // Журн. вычислит, математики и матем. физики. -1986. - Т. 26. - Т. 26, N2.-0. 276-292.

6. Зуев Ю.А., Липкин Л.И. О числе линейно-отделимых бу-

левых множеств заданной мощности // Методы дискретного анализа в теории графов и логических функций. Вып.43. -Новосибирск: ИМ СО АН СССР, 1986. - С. 29-39.

7. Зуев Ю.А., Липкин Л.И. К оценке эффективности пороговых представлений булевых функций // Кибернетика. -1988. - N 6. - С. 29-37.

8. Зуев Ю.А., Липкин Л.И. Линейные отсечения заданной мощности в единичном гиперкубе // Изв. АН СССР. Техн. кибернетика. - 1988. - N 3. - С. 79-85.

9. Зуев Ю.А. Наихудший случай для принятия решениний большинством голосов // Журн. вычисл. математики и ма-тем. физики. - 1989. - Т. 29, N 8.- 0. 1256-1257.

10. Зуев Ю.А. Асимптотика логарифма числа пороговых функций алгебры логики // Докл. АН СССР. - 1989. - Т. 306, N 3.-0. 528-530.

11. Зуев Ю.А., Иванов С.К. Пороговый корректор параллельно принимаемых бинарных сигналов // В сб.: Математические методы в распознавании образов и дискретной оптимизации. - М.: ВЦ АН СССР, 1990. С. 66-75.

12. Зуев Ю.А. Комбинаторно-вероятностные и геометрические методы в пороговой логике / / Дискретная математика. - 1991. - Т. 3, вып. 2. - С. 47-57.

13. Зуев Ю.А., Иванов С.К. Повышение эффективности комплексной обработки информации в динамических системах с использованием принципов распознавания // Вопросы кибернетики. Проблемы комплексирования кибернетических динамических систем / Под ред. Е.А.Федосова. - М.: Научный совет по комплексной проблеме "Кибернетика", 1992. -86-106.

14. Зуев Ю.А., Иванов С.К. "Ускоренный персептрон" и

самообучение процедуры взвешенного голосования // Докл. РАН. - 1993. - Т. 328, N 2. - С. 160-163.

15. Зуев Ю.А. Пороговые функции и пороговые представления булевых функций // Математические вопросы кибернетики. Вып.5. -М.: Наука, 1994. - С. 5-61.

16. Зуев Ю.А., Иванов С.К. О статистических свойствах взвешенного голосования // Докл. РАН. - 1995. - Т. 342, N 5. - С. 586-588.

17. Зуев Ю.А., Иванов С.К. Обучение и самообучение в процедурах взвешенного голосования // Журн. вычислит, математики и матем. физики. - 1995. - Т. 35, N 1. - С. 104-121.

18. Зуев Ю.А., Иванов С.К. Взвешенное голосование в многоканальных системах передачи дискретных сигналов // Проблемы передачи информации. - 1995. - Т. 31, вып. 4. -С. 22-36.

19. Зуев Ю.А. Гипотеза о случайных ±1-матрицах и асимптотика числа пороговых функций // Дискретный анализ и исследование операций. - 1995. - Т. 2, N 3. - С. 74-76.

20. Zuev Yu.A., Ivanov S.K. The Voting as a Way to Increase the Decision Reliability. In Proceedings of the Workshop on Foundations of Infomation/Decision Fusion with Applications to Engineering Problems. August 7-9, 1996. Washington, D.C. - Printed by Acadiana Printing, Inc. Lafayette, LA. - P. 206-210.

21. Зуев Ю.А. К оценке эффективности голосующих процедур // Теория вероятности и ее применения. - 1997. -Т. 42, вып. 1. - С. 74-84.

Ю.А. Зуев

Вероятностные методы в пороговой логике

Подписано в печать 03.11.98 Уч.-иад.л. 1. Усл.-печ.л. 1,3 Тираж 100 экз. Заказ 47. Бесплатно

Отпечатано на ротапринтах в ВЦ РАН 117333, Москва, ул. Вавилова, 40

Содержание диссертации автор исследовательской работы: доктора физико-математических наук, Зуев, Юрий Анатольевич

ВЕРОЯТНОСТНЫЕ МЕТОДЫ В ПОРОГОВОЙ ЛОГИКЕ

Введение

Глава 1. О числе пороговых функций %

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

1.2. Некоторые простейшие пороговые множества

1.3. Число пороговых множеств заданной мощности

Глава 2. Пороговые представления булевых функций

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

2.2. О пороговом числе типичной функции

2.3. Представление монотонных функций

Глава 3. Пороговые функции как голосующие процедуры

3.1. Модель многоканальной системы параллельной передачи информации

3.2. О принятии решения по большинству голосов

3.3. Вероятность ошибки порогового решающего правила

Глава 4. Алгоритм обучения и самообучения процедуры взвешенного голосования "ускоренный персептрон"

4.1. Классический персептрон и ускоренный персептрон в режиме обучения с учителем

4.2. Самообучение ускоренного персептрона

4.3. Результаты моделирования

Введение диссертация по математике, на тему "Вероятностные методы в пороговой логике"

1. Основные понятия и определения

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

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

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

Подмножество вершин куба {0,1}п будем называть пороговым, если оно отделимо от своего дополнения гиперплоскостью. Таким образом, с каждой пороговой функцией / связаны два пороговых множества: пороговое множество ее нулевых вершин /1(0) и пороговое множество ее единичных вершин /1(1). Каждое из них, как легко видеть, является связным, т.е. из произвольной вершины можно попасть в любую другую, переходя по ребрам куба и не выходя за пределы множества.

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

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

Наряду с (1) для пороговых функций часто используется другое, так называемое однородное представление. Булевой функцией считается отображение / : {—1,1}™ —> {—1,1}. Тогда пороговую функцию можно представить в виде у) = 5£7г(а0 + «12/1 + . + апуп), (2) считая, что линейная форма ни на одном из наборов {—1,1}п не обращается в нуль. Геометрически (2) соответствует переходу от куба {0,1}п к кубу {—1,1}та. Связь между переменными у1 и Х{ задается соотношением у{ — 2х{ — 1. Поэтому коэффициенты а\,., ап в (2) те же, что и в (1), а обобщенный порог, или смещение, ао равен ~ "^Ь. Если ао = О, то, как сразу видно из (2), пороговая функция является самодвойственной: /(—х) = —/(х).

Заметим, что в (2) ао входит равноправно с а^ ., ап. Это позволяет (подобно однородным координатам в проективной геометрии) ввести дополнительную переменную 2/о и рассмотреть самодвойственную функцию от п + 1 переменных, совпадающую с исходной функцией / в подкубе у = 1 и называемую по отношению к ней гиперфункцией

Я(уо, 2/1 ■ ■ ■, Уп) = + 012/1 + . + апуп). (3)

Гиперфункция может быть также записана в виде /я = 2/о/ V 2/0/й, где ¡л = /(2/1, • • • ,2/п) - функция, двойственная /. Таким образом, для нахождения двойственной функции к пороговой функции, заданной в форме (1), достаточно изменить значение ао на противоположное. Отметим также, что (3) устанавливает взаимно однозначное соответствие между пороговыми функциями от п переменных и самодвойственными пороговыми функциями от 71+1 переменных, доказывая тем самым равенство их числа.

Однако на (2) можно взглянуть и иначе, рассматривая в качестве значения пороговой функции знак скалярного произведения расширенного вектора весов а = (ао, оц,., ап) и расширенного вектора-вершины у = (1,2/1,., уп) '• (4)

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

Заметим далее, что для произвольного весового вектора а = (ао: öi, • • -, 0"п) весовой вектор /а = (tao, tai,., tan) при t > О задает ту же самую пороговую функцию (2). Поэтому множество весовых векторов, задающих одну и ту же пороговую функцию, является конусом в пространстве Еп+1 — (öo? «l, • • •, а>п)- Число пороговых функций оказывается, таким образом, равным числу выпуклых многогранных конусов, на которые Еп+1 разбивается 2п гиперплоскостями вида a,Q ± а\. ± ап = 0. (5)

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

2. Этапы развития пороговой логики

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

Понятие пороговой булевой функции впервые появилось в 1943 году в работе Маккаллока и Питтса [48], предложивших пороговый элемент в качестве математической модели нервной клетки - нейрона. Эти идеи, развитые в дальнейшем Розенблаттом [61], впервые показавшим адаптивные возможности такой модели, стали в настоящее время органической частью теории искусственных нейронных сетей (см.[68]) - одного из ведущих направлений современных исследований по искусственному интеллекту.

В пятидесятые годы пороговые функции привлекли внимание исследователей простотой своей технической реализации, сулившей возможность их эффективного использования в логических схемах появившихся в те годы первых серийных ЭВМ. Это привело в начале шестидесятых годов к бурному росту исследований по пороговым функциям и функциональным возможностям синтеза в пороговом базисе, т.е. по проблематике, объединеной в настоящее время под общим термином "пороговая логика". Среди огромного числа появившихся в это время публикаций можно отметить работы Чоу [74], [75], Элгота [78], Уиндера [100], [101], [102], монографии Ху [88] и Дертоузоса [7], а среди отечественных авторов работы Нечипорука [55] и Лупанова [45], монографию Бутакова

4].

Эти исследования, в результате которых в пороговой логике возникли параметры Чоу, появилось понятие несуммируемости как критерия пороговости, предложен принцип вариации порога, вскрыта связь между исследованиями Шлефли [97] по разбиению п-мерного пространства гиперплоскостями и проблемой оценки числа пороговых функций, а также найдены эффективные алгоритмы синтеза управляющих систем в пороговом базисе, весьма полно отражены в вышедшей в 1971 году в США монографии Муроги [93] - настоящей энциклопедии по пороговой логике.

Приведем вместе с кратким обоснованием некоторые из этих базовых для пороговой логики фактов.

3. Базовые факты пороговой логики

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

Функция / : {0,1}п —»• {0,1} называется к-суммируемой, если для некоторого у, 2 < у < к, существуют у не обязательно различных наборов {х°,., х?} С /-1(0) и J также не обязательно различных наборов {х];,., х|} С /1(1) таких, что х? + . + х? = х} + . + х|, где под сложением понимается обычное покоординатное сложение векторов в поле действительных чисел. В противном случае / называется к-несуммируемой. Если / &-несуммируема для всех натуральных к, то она называется несуммируемой.

Критерий пороговости [78]. Для того, чтобы функция была пороговой, необходимо и достаточно, чтобы она была несуммируемой.

С теоремой о разделимости тесно связаны и параметры Чоу. Пусть / : (0,1}п —»• {0,1} - произвольная булева функция. Сложив как векторы все наборы х, на которых /(х) = О, получим целочисленный п-мерный вектор ., Дополнив его нулевой координатой йо = равной числу нулевых наборов функции /, получим (п + 1)-мерный вектор параметров Чоу я(/) = ($о, ¿ъ .,

Теорема Чоу [74]. Пусть / - пороговая функция, д - произвольная булева функция. Тогда если д ф /, то э^) ф в(/).

В самом деле, допустим противное. Пусть з(/) = в(д) и /¿д. Тогда

Е х = Е х'

Х6/-40) хесгЧо)

Е х + Е х = е/-1(0)п ^-1(0) хе/-1(о)\(/-1(о) Е х + Е х ' хе/-1 (0)09-40) хе^-НО)^-1^)

Е х = Е ххе/-1(о)\5-1(о) хе5-М0)\/-1(0)

Так как ^(О)! = 1^(0)1, то \f-\0) \ д-Щ\ = 1^(0) \ /1(0)| и, следовательно, « =

Ц-ЩХд-Щ] Е

1 л хе5-1(о)\/1(°) что невозможно, так как задающая пороговую функцию / гиперплоскость разделяет множества /1(0) \ <?1(0) и 5Г1(0) \ /1(0), и выпуклые оболочки этих множеств не могут пересекаться. Полученное противоречие и доказывает невозможность совпадения векторов Чоу у функций / и д.

Замечая, что в векторе з(/) каждая координата может принимать лишь целые значения от 0 до 2П, с помощью теоремы

Чоу получаем верхнюю оценку для числа Мп пороговых функций от п переменных:

2П + 1)Я+1. (6)

Принцип вариации порога [71], [3]. В его основе лежат интуитивно ясные геометрические соображения. Пусть / -пороговая функция (1). Принцип вариации порога состоит в том, что веса вх,., ап всегда можно считать выбранными таким образом, что при непрерывном изменении порога 6, гиперплоскость а\ + . + ап = 6, перемещаясь параллельно себе, пересекает вершины гиперкуба {0,1}га по одиночке. Таким образом, при изменении Ь от —оо до +оо мощность порогового множества нулей изменяется от 0 до 2п, каждый раз возрастая на единицу, в результате чего возникает 2п +1 различных пороговых функций.

Рассмотрим теперь множество всех пороговых функций от п + 1 переменных с первыми п весами и порогом как у исходной функции / и всевозможными весами ап+\. В подкубе хп+1 = 0 все они совпадают с /, а в подкубе хп+\ — 1 каждая из них получается из / вариацией порога. Как следует из принципа вариации порога, множество содержит 2п + 1 функций. Таким образом,

2П + 1)Л-Л.

Отсюда получаем

2п{п-1)12. (7)

4. Проблема оценки числа пороговых функций

При реализации функций алгебры логики схемами из пороговых элементов число пороговых функций от п переменных служит естественной мерой разнообразия порогового базиса и позволяет оценивать сложность таких реализаций. Это явилось причиной пристального внимания к проблеме подсчета с конца пятидесятых годов. Так как получение точной формулы для не представлялось возможным, то исследования сосредоточились на прямом подсчете с помощью ЭВМ значений Ып для небольших значений тг, а также на получении асимптотических оценок для при п —» оо. На этом пути к 1965 году удалось получить лишь порядок логарифма этого числа. Как следует из (6) и (7) п2/2<\о%2Мп<п2. (8)

Нижняя оценка здесь была независимо получена несколькими авторами описанным выше методом вариации порога [71], [3], что же касается верхней оценки, то асимптотику п2 дали различные подходы и исторически первым был подход, использующий представление (2) и основанный на подсчете числа конусов, на которые (тг +1)-мерное пространство Еп+1 = (ао>яъ • • • :ап) разбивается 2п гиперплоскостями (5).

Этот подход для оценки числа пороговых функций впервые был использован в 1959 году [95] и независимо повторен многими авторами (см. [93]). Позже, однако, выяснилось, что пальму первенства здесь следует отдать выдающемуся швейцарскому математику девятнадцатого века Людвигу Шлефли ([97], с. 209-212), показавшему около 1850 года, что число конусов, на которые т-мерное пространство разбивается К гиперплоскостями, проходящими через начало координат и находящимися в общем положении, равно

С:1)

0 4 у

При этом сама постановка задачи и ее решение для 3-мерного пространства методом, который применим для пространства любого числа измерений, принадлежит знаменитому геометру Якобу Штейнеру [98].

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

После получения оценок (8) внимание исследователей сосредоточилось на вопросе асимптотического поведения отношения Л^/тг2, который, однако, вызвал значительные трудности и не поддавался решению в течение четверти века. Подсчет же с использованием ЭВМ, который удалось провести до п = 8, дал (к^2Лу/82 = 0,68740 (см. [93]), что не позволяло даже предположительно ответить на вопрос об асимптотике этого отношения.

Задача была решена автором в 1989 году [22] (полностью доказательство опубликовано в [24]), показавшим, что

1о§2 Ып ~ п2, п оо. (10)

При получении зтого результата автором были открыты новые геометрические свойства разбиения пространства гиперплоскостями, а также использованы свойства случайных ±1-матриц.

5. Пороговые функции в целочисленном пр ограммир овании

Другой областью знаний, поддерживающей интерес к пороговой логике, является теория целочисленного программирования (см., например, [65]). В самом деле, одной из наиболее известных NP-пoлныx задач линейного булева программирования является задача о ранце: максимизировать п и) г=1 при условии п

12) 1 где переменные Х{ булевы, а коэффициенты c¿,a¿,6 - неотрицательные действительные числа.

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

6. Пороговые представления булевых функций

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

Пороговое представление можно рассматривать и как дизъюнкцию пороговых функций, т.е. подобно д.н.ф. считать его схемой глубины 2. При этом аналогия между длиной кратчайшей д.н.ф. и пороговым числом становится особенно отчетливой. Решение обеих задач сводится к задаче о покрытии единичных вершин булевой функции, но в первом случае покрытие осуществляется подкубами, соответствующими допустимым конъюнкциям, а во втором - допустимыми пороговыми множествами. Целесообразность использования в ряде случаев вместо д.н.ф. порогового представления видна уже из примера мажоритарной функции, выражающей принятие решения простым большинством, которая задается одним неравенством хх + . + хп < {п - 1)/2, но требует для своего представления с помощью д.н.ф. элементарных конъюнкций - огромного числа при больших п.

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

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

Сначала Хаммером, Ибараки и Пильдом [83] и независимо автором и Тришиным [13] было доказано существование монотонных булевых функций 1р с пороговым числом равным

71 \ / и о и

1п/21//п' чт0 вместе с тривиальнои верхней оценкой давало

Построенный в [83] и [13] пример воспринимался как исключительный, пока автором и Липкиным [19] с помощью

13) открытого Коршуновым [37] строения множества почти всех монотонных булевых функций не было показано, что почти все они имеют пороговые числа, по порядку равные /п■

Верхняя оценка в (13) была существенно понижена автором в [13] и [19] и им же была высказана гипотеза, что нижняя оценка в (13) правильно отражает порядок максимального значения порогового числа, но этот вопрос продолжает оставаться открытым.

7. Пороговая логика и теория графов

За последние 20 лет выявились также интересные связи между пороговой логикой и теорией графов. Монотонная булева функция называется графической, если все ее нижние единицы находятся в слое 2, т.е. в ее сокращенную д.н.ф. входят только двухбуквенные конъюнкции. Графические функции от п переменных находятся во взаимно однозначном соответствии с п-вершинными графами, вершины которых соответствуют переменным, а ребра - конъюнкциям. Граф называется пороговым, если соответствующая ему графическая функция является пороговой. На языке теории графов по-роговость графа эквивалентна существованию линейного неравенства, отделяющего независимые подмножества его вершин от зависимых. Введенные Хваталом и Хаммером [76], пороговые графы вызвали интерес у специалистов по теории графов, и им было посвящено значительное число публикаций. Они также нашли применение при управлении параллельными вычислительными процессами. В настоящее время связанные с ними вопросы вошли в монографии и учебники по теории графов (см. [81], [9]).

8. Целочисленная реализация пороговых функций

Значительный интерес представляют новейшие результаты, связанные с целочисленной реализацией пороговых функций. Основной вопрос здесь состоит в оценке диапазона весов, достаточного для реализации любой пороговой функции от п переменных. Из (10) и элементарных мощностных соображений вытекает существование пороговых функций, для которых о§2к1 > п.

На заре пороговой логики такие функции были построены и в явном виде (см. [93], [4]). Однако верхняя оценка, основанная на неравенстве Адамара для модуля определителя, давала

1о§2Н £

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

27].

Впервые пример пороговой функции, при целочисленной реализации которой требуются веса аг- такие, что удалось построить Хастаду [85], а Алоном и др. [72] были указаны интересные связи этой задачи с задачей обращения ±1 матрицы, взвешиванием монет и другими математическими проблемами.

9. Пороговые функции как голосующие процедуры принятия решений

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

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

В технических приложениях подобная модель нашла свое применение в середине двадцатого века в работе Джона фон Неймана [54], чьи идеи вызвали целый поток исследований по повышению надежности логических схем и автоматов (см. [44], [53], [51], [6]). Мажоритарный принцип нашел применение также в системах помехоустойчивого кодирования информации при построении декодеров (см. [60], [50], [47]).

В начале шестидесятых годов независимо рядом исследователей было подмечено, что при статистической независимости ошибок отдельных членов коллектива оптимальное коллективное решающее правило является взвешенным голосованием, т.е. пороговой решающей функцией (см. [52], [75], [8], [56]). Статистические свойства взвешенного голосования изучались Пирсом [58], оценившим вероятность ошибки сверху, а также указавшим на возможность самообучения процедуры взвешенного голосования.

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

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

РСш <П[58].

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

10. Адаптация пороговых решающих правил

В тех случаях, когда вероятности ошибок в каналах неизвестны или нет достаточных оснований считать каналы независимыми, для получения близкого к оптимальному решающего правила естественно провести обучение решающего правила следующим образом. По многоканальной системе передается некоторая конечная тестовая последовательность символов ¿2,. и выбирается пороговая функция, правильно или с малым числом ошибок классифицирующая их п-мерные образы у1,уг, • • • • Для этого может быть использован пер-септронный алгоритм адаптации, предложенный Розенблаттом [61], корректирующий весовой вектор (4) при передаче каждого тестового символа г к согласно правилу а = Г ак, если 8^(ак,ук) = к+1 \ ак + если sgn(ak, ук) ф гк.

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

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

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

11. Содержание диссертационной работы

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

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