Вероятностные методы в пороговой логике тема диссертации и автореферата по ВАК РФ 01.01.09, доктор физико-математических наук Зуев, Юрий Анатольевич

• Зуев, Юрий Анатольевич
• доктор физико-математических наук
• 1998

Оглавление диссертации доктор физико-математических наук Зуев, Юрий Анатольевич

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

Введение

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