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

• Автор: Зуев, Юрий Анатольевич
• Шифр специальности: 01.01.09
• Научная степень: Докторская
• Год защиты: 1998
• Место защиты: Москва
• Количество страниц: 126 с. : ил.

ОГЛАВЛЕНИЕ
ВЕРОЯТНОСТНЫЕ МЕТОДЫ В ПОРОГОВОЙ ЛОГИКЕ
Введение
Глава 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} называется пороговой, если существует линейное неравенство с действительными коэффициентами
ОхЖ! + ... + апхп < Ь, (1)
выполненное на тех и только тех булевых наборах х — (х
Как обычно, булев набор длины п можно интерпретировать либо как подмножество п-элементного множества, что совершенно естественно во многих прикладных задачах, либо считать его вершиной п.-мерного единичного куба. Пороговая функция задается при этом гиперплоскостью, рассекающей 77-мерный куб так, что в вершинах по одну сторону гиперплоскости функция равна нулю, по другую - единице. Подобный взгляд оказывается весьма полезным в теоретических исследованиях, так как позволяет использовать геометрическую интуицию при решении различных вопросов, связанных с пороговой логикой.
Подмножество вершин куба {0,1}” будем называть пороговым, если оно отделимо от своего дополнения гиперплоскостью. Таким образом, с каждой пороговой функцией

перплоскости Ьг.|_1, а также, что квазиобщность расположения сохраняется внутри каждой гиперплоскости. Лемма доказана.
Лемма 1.1.1 в сочетании со свойствами случайных ±1-матриц позволяет оценить число пороговых функций снизу. Матрицу с элементами, равными +1 или —1, имеющую р строк и т столбцов, будем обозначать А(р, т). Как показано в серии работ Комлоша [90, 91, 92], ранг почти всех ±1-матриц А(р,т) при р < т равен р. Одлыжко [94] исследовал более тонкое свойство ± 1-матриц.
Определение 1.1.2. ±1—матрица А(р,т) обладает свойством Одлыжко, если в линейном замыкании ее строк не содержится ± 1-векторов, отличных от строк матрицы А и им противоположных.
Как показал сам Одлыжко [94], почти все ±1-матрицы А(р, т) при р < т — т/пт обладают этим свойством. В работе Кана, Комлоша и Семереди [92] этот результат был усилен. Ими показано, что свойством Одлыжко обладают почти все ±1-матрицы А(р,т) при р < т — с, где с - некоторая константа, а в качестве гипотезы выдвинуто предположение, что константу с можно положить равной 1. Покажем, к каким выводам относительно числа пороговых функций это приводит. Следующая теорема выражает сущность использованного автором в [22] и [24] подхода, а в наиболее близком виде к данной здесь формулировке представлена в [31].
Теорема 1.1.1. Пусть свойство Одлыжко выполнено почти для всех матриц А(р,п + 1), где р = р(п) < п, п -э оо. Тогда для числа Мп пороговых функций справедлива асим-