Оценки весов персептронов : полиномиальных пороговых булевых функций

• Автор: Подольский, Владимир Владимирович
• Шифр специальности: 01.01.06
• Научная степень: Кандидатская
• Год защиты: 2009
• Место защиты: Москва
• Количество страниц: 76 с. : ил.

Оглавление
Введение
1 Предварительные сведения
2 Нижняя оценка на веса пороговых элементов
2.1 Построение функции
2.2 Основной результат
3 Однородная нижняя оценка на веса пороговых элементов
3.1 Построение функции
3.2 Представление ОМВ^ в виде ДНФ
3.3 Основной результат
3.4 План доказательства
3.5 Вспомогательные результаты
3.6 Доказательство основного результата
4 Увеличение степени пороговых элементов на 1 может сильно уменьшить их вес
4.1 Формулировка результатов
4.2 Соотношения между характеристиками функций
4.3 О функциях с афинно разреженным спектром
4.4 Случай маленькой степени
4.5 Случай большой степени
4.6 Основной результат и его обобщения

Введение
Работа относится к области сложности вычислений, одному из разделов математической логики и теории алгоритмов. Более конкретно, мы исследуем некоторый способ реализации булевых функций многочленами и вопросы сложности такой реализации.
Реализация булевых функций действительными многочленами играет важную роль в теории сложности, начиная от сложности вычислений и заканчивая квантовыми вычислениями и теорией обучения [3, 29, 8', 31] В данной работе мы рассматриваем один из таких способов реализации, а именно пороговые элементы и связанные с ними меры сложности: пороговую степень, пороговый вес и пороговую длину.
Булева функция /: {0,1}п —» {0,1} называется знаковой функцией целочисленного многочлена р степени д от п переменных, если
( /О) = 1 =>■ р(х) > 0 [/(ж) = 0 => р(х) <
для всех х 6 {0,1}”. При этом многочлен р называется пороговым элементом степени в, для булевой функции /: {0,1}71 —> {0,1}. Весом порогового элемента называется сумма модулей коэффициентов многочлена р, а длиной порогового элемента называется число мономов в многочлене р. Заметим, что обычно пороговым элементом называют то, что мы называем пороговым элементом степени 1. Чтобы избежать путаницы, мы будем называть пороговые элементы степени 1 линейными пороговыми элементами. Обобщенной функцией голосования называется линейный пороговый элемент, у которого все коэффициенты равны ±1.

Пороговой степенью булевой функции / называется минимальная степень порогового элемента для /. Пороговым весом булевой функции / называется минимальный вес порогового элемента для /. Пороговой длиной булевой функции / называется минимальная длина порогового элемента для /.
Кроме обозначений {0,1} для значений булевых переменных мы будем также пользоваться обозначениями {—1,+1}, где — 1 соответствует "истине". В этом случае пороговым элементом степени d для функции /: {—1,+1}п —> {—1,+1} называется целочисленный многочлен р степени d от п переменных, такой что
Г f(x) = 1=> р{х) > О
/0) = -1 =>р(х) < о
для всякого х 6 {—1,+1}и. Все те же меры сложности булевых функций определяются в этих обозначениях аналогично. Нетрудно показать (смотри ниже), что пороговая степень функции в обозначениях {0,1};И в обозначениях (—1, +1} совпадает. Для длин и весов это неверно (теоремы I, II и III ниже).
Изучение пороговых элементов началось в 1968 году с книги Минского и Пейперта [23, 1]. С тех пор понятие пороговой степени неоднократно использовалось в доказательствах нижних оценок на размер схем и, вообще, в изучении сложностных классов [27, 35, 2, 5, 20, 30]. С помощью нижних оценок на пороговую степень были получены важные нижние оценки в коммуникационной сложности, в частности, доказана теорема о пороговой степени и спектральной норме [30, 32] и получены продвижения в изучении знакового ранга [33, 28]. Наконец, в вычислительной теории обучения, понятие пороговой степени использовалось в нескольких ключевых алгоритмах [16, 26] и нижних оценках [18].
Кроме пороговой степени, книга Минского и Пейперта также положила начало активному изучению понятия порогового веса и его приложений. Впоследствии понятие порогового веса не раз возникало в вычис-
Теперь мы перейдем к определению нашей функции. Она будет зависеть от трех натуральных параметров п, сі и Б, где сі ^ Б. Первые два параметра задают число входных переменных (более точно, функция будет имеет тай переменных). Смысл параметров й и О следующий: функция будет реализуема пороговым элементом степени й (с большим весом), но не реализуема никаким пороговым элементом степени не выше £) с маленьким весом (мы уточним, что значит “маленький” и “большой” позже).
Разобьем (1п входных переменных на сі групп одинакового размера п: (ж1, ж2,..., х ), где Xі — (:г, хг2, ■ ■ ■, хгп). Всякий набор значений переменных хг задает множество натуральных чисел Хі = {у|ж) = 1}. И наоборот, всякое подмножество Хі множества [та] задает единственный набор значений переменных хг. Так что, далее мы будем предполагать, что наша функция отображает кортежи (Хі,... , А)г) длины сі подмножеств [та] в {0,1}.
Аналогично функции ОМВ(ж), значение нашей функции на кортеже (Хі,... , АГД зависит только от максимального (в некотором линейном порядке на множестве [та] ) кортежа (ац,..., ау), лежащего в множестве Хі х - ■ • х Х([- Порядок на множестве [та]гі будет довольно сложным и будет играть ключевую роль в доказательстве. Перейдем к определению этого порядка.
Сначала мы определим .0+1 различный линейный порядок на множестве [та]. Первый порядок <і - это обычный порядок: 1,2,... ,п. Остальные порядки получаются из первого циклическими сдвигами. Более точно, разобьем множество [та] на О + 1 блок щ,..., ио+1 одинакового размера так, чтобы каждый блок состоял из последовательных элементов: щ = (г—1)/Щ+1> • ■ •) (формально, это определение годится только для та, делящихся на Б + 1; если та не делится на О + 1, будем считать, что блоки устроены также, и их размеры отличаются не более чем на 1). Для всякого г = 2, ...,£) + 1 порядок С, получается из порядка <х