Владимир владимирович оценки весов персептронов (полиномиальных пороговых булевых функций)

На правах рукописи

УДК 510.52+519.714.27 Подольский Владимир Владимирович ОЦЕНКИ ВЕСОВ ПЕРСЕПТРОНОВ (ПОЛИНОМИАЛЬНЫХ ПОРОГОВЫХ БУЛЕВЫХ ФУНКЦИЙ) 01.01.06 – математическая логика, алгебра и теория чисел

АВТОРЕФЕРАТ

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

Москва, 2009

Работа выполнена на кафедре математической логики и теории алгоритмов Механико-математического факультета Московского государственного универ ситета имени М. В. Ломоносова.

Научный консультант: доктор физико-математических наук, профессор Николай Константинович Верещагин.

Официальные оппоненты: чл.-корр. РАН, доктор физико-математических наук Александр Александрович Разборов;

кандидат физико – математических наук, Михаил Николаевич Вялый.

Ведущая организация: Санкт-Петербургское отделение Математического института имени В. А. Стеклова РАН

Защита диссертации состоится 11 декабря 2009 г. в 16 ч. 45 мин. на заседании диссертационного совета Д.501.001.84 при Московском государст-венном уни верситете имени М. В. Ломоносова по адресу: Российская Федерация, 119991, Москва, ГСП-1, Ленинские горы, д. 1, Московский государственный универси тет имени М. В. Ломоносова, Механико-математический факультет, аудитория 14-08.

С диссертацией можно ознакомиться в библиотеке Механико-математи ческого факультета МГУ имени М. В. Ломоносова (Главное здание, 14-й этаж).

Автореферат разослан 11 ноября 2009 г.

Учёный секретарь диссертационного совета Д.501.001.84 при МГУ, доктор физико-математических наук, профессор А. О. Иванов

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

.

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

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

Булева функция f : {0, 1}n {0, 1} называется знаковой функцией цело численного многочлена p степени d от n переменных, если f (x) = 1 p(x) f (x) = 0 p(x) для всех x {0, 1}n. При этом многочлен p называется пороговым элемен том степени d для булевой функции f : {0, 1}n {0, 1}. Весом порогового элемента называется сумма модулей коэффициентов многочлена p, а длиной порогового элемента называется число мономов в многочлене p. Заметим, что обычно пороговым элементом называют то, что мы называем пороговым эле ментом степени 1. Чтобы избежать путаницы, мы будем называть пороговые элементы степени 1 линейными пороговыми элементами.

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

Richard Beigel. The polynomial method in circuit complexity. In Proc. of the Eigth Annual Conference on Structure in Complexity Theory, pages 82–95, 1993.

Michael E. Saks. Slicing the hypercube. Surveys in Combinatorics, pages 211–255, 1993.

Harry Buhrman and Ronald de Wolf. Complexity measures and decision tree complexity: A survey. Theor.

Comput. Sci., 288(1):21–43, 2002.

Alexander A. Sherstov. Communication lower bounds using dual polynomials. Bulletin of the EATCS, 95:59– 93, 2008.

Кроме обозначений {0, 1} для значений булевых переменных мы будем так же пользоваться обозначениями {1, +1}, где 1 соответствует "истине". В этом случае пороговым элементом степени d для функции f : {1, +1}n {1, +1} называется целочисленный многочлен p степени d от n переменных, такой что f (x) = 1 p(x) f (x) = 1 p(x) для всякого x {1, +1}n. Все те же меры сложности булевых функций опре деляются в этих обозначениях аналогично. Нетрудно показать (смотри ни же), что пороговая степень функции в обозначениях {0, 1} и в обозначениях {1, +1} совпадает. Для длин и весов это неверно (теоремы I, II и III ниже).

Изучение пороговых элементов началось в 1968 году с книги Минского и Пейперта5,6. С тех пор понятие пороговой степени неоднократно использова лось в доказательствах нижних оценок на размер схем и, вообще, в изуче нии сложностных классов7,8,9,10,11. С помощью нижних оценок на пороговую степень были получены важные нижние оценки в коммуникационной слож ности, в частности, доказана теорема о пороговой степени и спектральной норме 12,13 и получены продвижения в изучении знакового ранга14,15. Наконец, в вычислительной теории обучения, понятие пороговой степени использова Marvin L. Minsky and Seymour A. Papert. Perceptrons: Expanded edition. MIT Press, Cambridge, Mass., 1988.

Марвин Минский и Сеймур Пейперт. Персептроны. Издательство "Мир Москва, 1971.

Ramamohan Paturi and Michael E. Saks. Approximating threshold circuits by rational functions. Inf.

Comput., 112(2):257–272, 1994.

Kai-Yeung Siu, Vwani P. Roychowdhury, and Thomas Kailath. Rational approximation techniques for analysis of neural networks. IEEE Transactions on Information Theory, 40(2):455–466, 1994.

James Aspnes, Richard Beigel, Merrick L. Furst, and Steven Rudich. The expressive power of voting polynomials. Combinatorica, 14(2):135–148, 1994.

Richard Beigel, Nick Reingold, and Daniel A. Spielman. PP is closed under intersection. J. Comput. Syst.

Sci., 50(2):191–202, 1995.

Matthias Krause and Pavel Pudlk. On the computational power of depth-2 circuits with threshold and a modulo gates. Theor. Comput. Sci., 174(1–2):137–156, 1997.

Alexander A. Sherstov. Separating AC0 from depth-2 majority circuits. In Proc. of the 39th Symposium on Theory of Computing (STOC), pages 294–301, 2007.

Alexander A. Sherstov. The pattern matrix method for lower bounds on quantum communication. In Proc.

of the 40th Symposium on Theory of Computing (STOC), pages 85–94, 2008.

Alexander A. Sherstov. The unbounded-error communication complexity of symmetric functions. In Proc. of the 49th Symposium on Foundations of Computer Science (FOCS), pages 384–393, 2008.

Alexander A. Razborov and Alexander A. Sherstov. The sign-rank of AC0. In Proc. of the 49th Symposium on Foundations of Computer Science (FOCS), pages 57–66, 2008.

лось в нескольких ключевых алгоритмах16,17 и нижних оценках18.

Кроме пороговой степени, книга Минского и Пейперта также положила на чало активному изучению понятия порогового веса и его приложений. Впо следствии понятие порогового веса не раз возникало в вычислительной теории обучения19,20,21 и в теории сложности, включая оракульные разделения22, и нижние оценки на коммуникационую сложность24. Наконец, пороговый вес изучался как самостоятельная мера сложности. Было разработано множество аналитических и комбинаторных методов для доказательства нижних оценок на пороговый вес25,26,27,28,29,30,31.

Не менее активно изучалось понятие пороговой длины, смотри 1/ Adam R. Klivans and Rocco A. Servedio. Learning DNF in time 2O(n ). J. Comput. Syst. Sci., 68(2):303–318, 2004.

Ryan O’Donnell and Rocco A. Servedio. New degree bounds for polynomial threshold functions. In Proc. of the 35th Symposium on Theory of Computing (STOC), pages 325–334, 2003.

Adam R. Klivans and Alexander A. Sherstov. Unconditional lower bounds for learning intersections of half spaces. Machine Learning, 69(2–3):97–114, 2007.

Jerey Charles Jackson. The harmonic sieve: A novel application of Fourier analysis to machine learning theory and practice. PhD thesis, Carnegie Mellon University, 1995.

Adam R. Klivans, Ryan O’Donnell, and Rocco A. Servedio. Learning intersections and thresholds of halfspaces.

J. Comput. Syst. Sci., 68(4)8–840, 2004.

Adam R. Klivans and Rocco A. Servedio. Toward attribute ecient learning of decision lists and parities.

J. Machine Learning Research, 7:587–602, 2006.

Richard Beigel. Perceptrons, PP, and the polynomial hierarchy. Computational Complexity, 4:339–349, 1994.

Nikolai K. Vereshchagin. Lower bounds for perceptrons solving some separation problems and oracle separation of AM from PP. In Proc. of the Third Israel Symposium on Theory of Computing and Systems (ISTCS), pages 46–51, 1995.

Harry Buhrman, Nikolai K. Vereshchagin, and Ronald de Wolf. On computation and communication with small bias. In Proc. of the 22nd Conf. on Computational Complexity (CCC), pages 24–32, 2007.

Jehoshua Bruck. Harmonic analysis of polynomial threshold functions. SIAM J. Discrete Math., 3(2):168–177, 1990.

Kai-Yeung Siu and Jehoshua Bruck. On the power of threshold circuits with small weights. SIAM J. Discrete Math., 4(3):423–435, 1991.

Jehoshua Bruck and Roman Smolensky. Polynomial threshold functions, AC0 functions, and spectral norms.

SIAM J. Comput., 21(1):33–42, 1992.

Mikael Goldmann, Johan H astad, and Alexander A. Razborov. Majority gates vs. general weighted threshold gates. Computational Complexity, 2:277–300, 1992.

Matthias Krause and Pavel Pudlk. Computing Boolean functions by polynomials and threshold circuits.

a Comput. Complex., 7(4):346–370, 1998.

Matthias Krause. On the computational power of Boolean decision lists. Computational Complexity, 14(4):362–375, 2006.

Adam R. Klivans and Alexander A. Sherstov. Unconditional lower bounds for learning intersections of half spaces. Machine Learning, 69(2–3):97–114, 2007.

например32,33,34,35,36.

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

Типы булевых функций, изучавшихся с этой точки зрения, включают линей ные пороговые элементы37,38,39, списки разрешения40, формулы в виде ДНФ41.

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

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

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

1. Для всех d и n построена булева функция от n переменных пороговой степени d, такая что вес любого порогового элемента степени d для этой d функции не меньше n(n ). Эта оценка неулучшаема. Этот результат верен как для обозначений {0, 1}, так и для обозначений {1, +1} для булевых переменных.

Jehoshua Bruck. Harmonic analysis of polynomial threshold functions. SIAM J. Discrete Math., 3(2):168–177, 1990.

Mikael Goldmann, Johan H astad, and Alexander A. Razborov. Majority gates vs. general weighted threshold gates. Computational Complexity, 2:277–300, 1992.

Mikael Goldmann. On the power of a threshold gate at the top. Inf. Process. Lett., 63(6):287–293, 1997.

Matthias Krause and Pavel Pudlk. Computing Boolean functions by polynomials and threshold circuits.

a Comput. Complex., 7(4):346–370, 1998.

Adam R. Klivans and Alexander A. Sherstov. Unconditional lower bounds for learning intersections of half spaces. Machine Learning, 69(2–3):97–114, 2007.

Kai-Yeung Siu and Jehoshua Bruck. On the power of threshold circuits with small weights. SIAM J. Discrete Math., 4(3):423–435, 1991.

Mikael Goldmann, Johan H astad, and Alexander A. Razborov. Majority gates vs. general weighted threshold gates. Computational Complexity, 2:277–300, 1992.

Johan Hastad. On the size of weights for threshold gates. SIAM J. Discret. Math., 7(3):484–492, 1994.

Richard Beigel. Perceptrons, PP, and the polynomial hierarchy. Computational Complexity, 4:339–349, 1994.

Nikolai K. Vereshchagin. Lower bounds for perceptrons solving some separation problems and oracle separation of AM from PP. In Proc. of the Third Israel Symposium on Theory of Computing and Systems (ISTCS), pages 46–51, 1995.

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

Этот результат верен как для обозначений {0, 1}, так и для обозначений {1, +1} для булевых переменных.

3. Для каждого d и каждого n построена булева функция от n переменных пороговой степени d, вычислимая пороговым элементом степени d + 1 с весом O(n2 ), и такая что вес любого порогового элемента степени d для этой функции не меньше 2(n). Этот результат верен для обозначений {1, +1} для булевых переменных.

4. Аналогичный результат получен для длины пороговых элементов: для каждого d и каждого n построена булева функция от n переменных поро говой степени d, вычислимая пороговым элементом степени d+1 с длиной O(d), и такая что длина любого порогового элемента степени d для этой функции не меньше 2(d). Этот результат верен для обозначений {1, +1} для булевых переменных.

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

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

• Научно-исследовательский семинар по математической логике под руко водством академика РАН С.И. Адяна, чл.-корр. РАН Л. Д. Беклемишева, проф. В. А. Успенского (2009).

• Семинар "Алгоритмические вопросы алгебры и логики" под руководством академика РАН С.И. Адяна (2008, 2009).

• "Колмогоровский семинар по сложности вычислений и сложности опре делений" под руководством проф. Н.К. Верещагина, к.ф.-м.н. А.Е. Рома щенко, чл.-корр. РАН А.Л. Семёнова, к.ф.-м.н. А.Х. Шеня (2007, 2008, 2009).

• II Международная конференция "Computer Science in Russia" (г. Екате ринбург, УрГУ, 3-7 сентября 2007 г.).

• III Международная конференция "Computer Science in Russia" (г. Москва, 7-12 июня 2008 г.).

• Семинар по сложности определений, описаний и доказательств, и по алго ритмам (Workshop on computational, descriptive and proof complexity, and algorithms) (г. Москва, НМУ, 29-31 августа 2007 г.) • XXIX Конференции молодых учёных (г. Москва, МГУ, 18 апреля 2007 г.).

Публикации. Основные результаты диссертации опубликованы в четырех работах автора [1–4].

Структура и объем работы. Диссертация состоит из введения и четырех глав. Текст диссертации изложен на 76 страницах. Список литературы вклю чает 36 наименований.

Краткое содержание работы Мы будем нумеровать цитируемые результаты заглавными римскими циф рами, а результаты автора – арабскими цифрами.

Когда мы говорим о булевой функции f, мы обычно подразумеваем, что задана последовательность {fn } булевых функций, где функция fn имеет n n= входных переменных. Мы будем изучать, как ведут себя различные величины, связанные с булевой функцией f, при n стремящемся к бесконечности.

Мы используем следующие стандартные обозначения для асимптотического поведения функций. Пусть f : N N и g : N N. Тогда • f (n) = O(g(n)) означает, что C N n N |f (n)| C|g(n)|;

• f (n) = (g(n)) означает, что c 0 N n N |f (n)| c|g(n)|;

• f (n) = (g(n)) означает, что c, C 0 N n N c|g(n)| |f (n)| C|g(n)|;

• f (n) = o(g(n)) означает, что c 0 N n N |f (n)| c|g(n)|;

Напомним основное определение работы. Пороговым элементом степени d для булевой функции f : {1, +1}n {1, +1} называется всякое выражение вида f (x) = sgn p(x), где p(x) – целочисленный многочлен степени d, а sgn обозначает знаковую функцию: sgn(t) = 1, если t положительно, sgn(t) = 0, если t = 0, и sgn(t) = иначе. Другими словами, пороговым элементом степени d для f называется це лочисленный многочлен, знаковая функция которого совпадает с f. Аналогич но, пороговым элементом степени d для булевой функции f : {0, 1}n {0, 1} называется выражение вида 1 + sgn p (x) f (x) =, где p(x) – целочисленный многочлен степени d. То есть, многочлен положите лен, когда функция принимает значение 1, и отрицателен иначе.

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

Для всякого b {0, 1} верно b2 = b, а для всякого b {1, +1} верно b2 = 1. Поэтому пороговый элемент для всякой функции в любом из двух обозначений, всегда можно считать мультилинейным (то есть линейным по каждой переменной).

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

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

С тремя параметрами порогового элемента связаны три меры сложности булевой функции (в каждой из систем обозначений): минимальная степень по рогового элемента для этой функции, называемая пороговой степенью, мини мальный вес порогового элемента для этой функции, называемый пороговым весом, и минимальная длина порогового элемента для этой функции, назы ваемая пороговой длиной. Пороговую степень булевой функции f мы будем обозначать через deg(f ) (мы скоро докажем, что это определение не зави сит от обозначений). Заметим, что поскольку всякую булеву функцию мож но реализовать пороговым элементом, и пороговые элементы всегда можно считать мультилинейными, для всякой булевой функции f от n переменных deg(f ) n.

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

Будем обозначать через W0,1 (f, d) (W±1 (f, d)) минимальный вес порогового элемента степени не выше d для функции f в обозначениях {0, 1} (в обозначе ниях {1, +1}, соответственно). Будем обозначать через L0,1 (f, d) (L±1 (f, d)) минимальную длину порогового элемента степени не выше d для функции f в обозначениях {0, 1} (в обозначениях {1, +1}, соответственно). Эти поня тия определены, только в случае d deg(f ). Иногда будет не важно, в каких именно обозначениях мы рассматриваем булеву функцию или обозначения бу дут ясны из контекста. Тогда мы будем писать просто W (f, d) и L(f, d).

Сразу заметим, что если deg(f ) d1 d2, то из определения видно, что W (f, d1 ) W (f, d2 ) и L(f, d1 ) L(f, d2 ). То есть величины W (f, d) и L(f, d) (в обоих обозначениях булевых переменных) не могут увеличиваться при росте d.

Реализация булевых функций пороговыми элементами соответствует реали зации булевых функций булевыми схемами специального вида. Более точно, пусть F – некоторое семейство булевых функций. Персептроном в базисе F называется булева схема глубины 2 с линейным пороговым элементом на верх линейный пороговый элемент 6 6 f1 f2 fk ··· 6 6 6 6 6 6 6 6 ··· x3 x1 x7 x3 x6 x8 x7 x8 x ··· нем уровне и с произвольными булевыми функциями f1,..., fk из F на нижнем уровне (смотри рисунок).

Нетрудно заметить, что пороговый элемент для булевой функции в обозна чениях {0, 1} соответствует линейной пороговой функции, в которую подста вили произведения переменных. Так как произведение булевых переменных в обозначениях {0, 1} соответствует их конъюнкции, мы получаем, что порого вый элемент для булевой функции в обозначениях {0, 1} соответствует пер септрону в базисе из конъюнкций. Произведению переменных в обозначениях {1, +1} соответствует их сумма по модулю два, поэтому пороговый элемент для булевой функции в этих обозначениях соответствует персептрону в базисе из функций логического сложения. Заметим, что длина порогового элемента соответствует размеру персептрона (числу ребер в нем), точнее эти величины отличаются не более чем в n + 1 раз. Если же мы потребуем, чтобы на верх нем уровне персептрона была не линейная пороговая функция, а обобщенная функция голосования, то размеру схемы будет соответствовать вес порогового элемента.

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

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

Реализация булевых функций пороговыми элементами в обозначениях {0, 1} и в обозначениях {1, +1} – это, вообще говоря, разные реализации. Это видно хотя бы по соответствующим булевым схемам. Однако, между реализациями в разных обозначениях есть связь. Сейчас мы приведем известные результаты на эту тему.

Сначала установим соотношение между переменными в обозначениях {0, 1} и {1, +1}. Будем обозначать булеву переменную в обозначениях {1, +1} через b, а ту же булеву переменную в обозначениях {0, 1} через b. Тогда, легко проверить, что b = 2 (1 b) (напомним, что "истине" соответствует 1 в обозначениях {0, 1} и 1 в обозначениях {1, +1}). Обратно, b = 1 2b.

Предположим теперь, что p(x1,..., xn ) – пороговый элемент степени d для функции f в обозначениях {1, +1}. Тогда ясно, что многочлен p(12x,..., 2x ) будет пороговым элементом степени d для f в обозначениях {0, 1}. Об n ратно, если p(x,..., x ) – пороговый элемент степени d для функции f в обо 1 n значениях {0, 1}, то 2 p( 2 (1 x1 ),..., 1 (1 xn )) – пороговый элемент степени d d для функции f в обозначениях {1, +1} (множитель 2d нужен, чтобы сде лать коэффициенты многочлена целыми, так как после замены переменных m они имеют вид 2k, где m – целое, а k d).

Таким образом, по всякому пороговому элементу для заданной функции в одних обозначениях, можно легко построить пороговый элемент для той же функции в других обозначениях, причем при этом переходе степень порогового элемента не возрастает. Следовательно, deg(f ) не зависит от обозначений, в которых мы реализуем функцию f пороговыми элементами.

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

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

В работе Гольдмана42 была доказана следующая теорема.

Теорема I (Гольдман). Функция логического сложения от n переменных имеет пороговую длину 1 в обозначениях {1, +1} и экспоненциальную (от числа переменных) пороговую длину в обозначениях {0, 1}.

Mikael Goldmann. On the power of a threshold gate at the top. Inf. Process. Lett., 63(6):287–293, 1997.

Первое утверждение этой теоремы несложно, так как легко увидеть, что i xi = i xi в обозначениях {1, +1}. Существенной частью этого результата является нижняя оценка на длину пороговых элементов в обозначениях {0, 1}.

С другой стороны, в работе43 была доказана следующая теорема.

Теорема II (Краузе, Пудлак). Существует (явно заданная) функция поли номиальной пороговой длины в обозначениях {0, 1}, но экспоненциальной по роговой длины в обозначениях {1, +1}.

Ситуация с весами другая. Теорема I легко переносится на веса порого вых элементов. Действительно, функция логического сложения представима пороговым элементом с весом 1, а с другой стороны, пороговый вес всегда не меньше пороговой длины, так что функция логического сложения имеет экспоненциальный пороговый вес в обозначениях {0, 1}. Однако, в обратную сторону, в работе44 был доказан следующий результат.

Теорема III (Краузе, Пудлак). Bсякая функция от n переменных с порого вым весом W в обозначениях {0, 1} имеет пороговый вес O(n2 W 4 ) в обозна чениях {1, +1}.

Так что, если существует пороговый элемент полиномиального веса для некоторой функции в обозначениях {0, 1}, то такой же пороговый элемент существует для этой функции и в обозначениях {1, +1}. Отметим также, что из доказательства в работе45 следует также такой результат.

Теорема IV (Краузе, Пудлак). Для всякой функции f и всякого d deg(f ) верно W±1 (f, d) O(n2 W0,1 (f, d)) Таким образом, соотношение из теоремы III между пороговыми весами за данной функций f в различных обозначениях верно также и для величин W±1 (f, d) и W0,1 (f, d).

Наконец, пусть булева функция f от n переменных представима пороговым элементом p(x), степень которого постоянна и не зависит от n. Тогда путем Matthias Krause and Pavel Pudlk. Computing Boolean functions by polynomials and threshold circuits.

a Comput. Complex., 7(4):346–370, 1998.

Matthias Krause and Pavel Pudlk. Computing Boolean functions by polynomials and threshold circuits.

a Comput. Complex., 7(4):346–370, 1998.

Matthias Krause and Pavel Pudlk. Computing Boolean functions by polynomials and threshold circuits.

a Comput. Complex., 7(4):346–370, 1998.

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

Лемма V (Фольклор). Если функция f от n переменных представима поро говым элементом постоянной, не зависящей от n, степени d, то W0,1 (f, d) = (W±1 (f, d)).

Таким образом, если нас интересует величина W (f, d), где d – постоянно и не зависит от числа переменных n, то не имеет значения в каких обозначе ниях рассматривается функция (все результаты у нас будут с точностью до постоянного множителя).

Перейдем к обзору истории изучаемых вопросов и содержания диссертации.

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

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

В работе мы будем интересоваться величиной W (f, d) (в тех или иных обо значениях) для фиксированной функции f и различных d, для которых поня тие W (f, d) корректно. Мы будем доказывать верхние и нижние оценки на эту величину.

Еще в 60-х годах были получены нижние оценки вида 2(n) на веса поро говых элементов степени d = 1 (то есть, линейных пороговых элементов) для конкретных функций (первый такой результат был получен в46 ). Однако, они не достигали известной верхней оценки nO(n), доказанной в работе Муроги (смотри также48 ).

Теорема VI (Мурога). Для всякой булевой функции f от n переменных, если deg(f ) = 1, то W (f, 1) = nO(n).

Позднее Хостад49 доказал точную (вплоть до константы в экспоненте) ниж нюю оценку.

J. Myhill and W. H. Kautz. On the size of weights required for linear-input switching functions. IRE Trans.

on Electronic Computers, 10(2):288–290, 1961.

Saburo Muroga. Threshold logic and its applications. Wiley-Interscience, Chichester, 1971.

Johan Hastad. On the size of weights for threshold gates. SIAM J. Discret. Math., 7(3):484–492, 1994.

Johan Hastad. On the size of weights for threshold gates. SIAM J. Discret. Math., 7(3):484–492, 1994.

Теорема VII (Хостад). Существует (явно заданная) функция f от n пере менных такая что deg(f ) = 1 и W (f, 1) = n(n).

d Для случая d 1 из теоремы VI легко получается верхняя оценка nO(n ) на веса пороговых элементов степени d для заданных функций.

Следствие VIII. Для всякой булевой функции f от n переменных, если d deg(f ) = d, то W (f, d) = nO(n ) (здесь константа в O зависит от d).

Действительно, в пороговом элементе степени d не более O(nd ) одночленов.

Заменим их на новые независимые переменные. Тогда мы получим линейный пороговый элемент от O(nd ) переменных. Согласно теореме VI, он эквива d лентен некоторому пороговому элементу с весом nO(dn ). Заменяя в новом ли нейном пороговом элементе переменные обратно на одночлены, мы получаем требуемую оценку.

В главе 2 мы доказываем, что эта верхняя оценка точна.

Теорема 1. Для всякого d существует (явно заданная) булева функция f d такая что deg(f ) = d, и W (f, d) = n(n ) (константа в зависит от d).

Эта теорема не получается из теоремы VII также легко, как следствие VIII из теоремы VI. До этого результата для пороговых элементов степени d не было известно нижних оценок лучше, чем 2(n).

В параграфе 2.1 мы строим нашу функцию. В параграфе 2.2 мы доказы ваем теорему 1. В доказательстве мы используем конструкцию Хостада из теоремы VII в сочетании с новым методом комбинаторного характера.

В главе 2 мы работаем в обозначениях {1, +1}, однако, поскольку наш результат распространяется только на постоянные d (не зависящие от n), то, по лемме V, выбор обозначений в данном результате не имеет значения, результат автоматически переносится и на обозначения {0, 1}.

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

Mikael Goldmann, Johan Hastad, and Alexander A. Razborov. Majority gates vs. general weighted threshold gates. Computational Complexity, 2:277–300, 1992.

Теорема IX (Гольдман и др.). Существует (явно заданная) функция поро говой степени 1, и такая что W (f, n) = 2(n) и W (f, 1) = 2O(n).

То есть, эту функцию можно вычислить линейным пороговым элементом экспоненциального веса, и при этом всякий пороговый элемент произвольной степени для этой функции имеет экспоненциальный вес. Рассмотренная в этой теореме функция в некотором смысле самая сложная функция среди всех функций, представимых пороговыми элементами. Этот результат был дока зан в обозначениях {1, +1}, однако в силу теоремы III, он распространяется и на обозначения {0, 1}.

В работе51 была доказана следующая теорема.

Теорема X (Бейгель). Существует (явно заданная) функция f от n пе ременных, такая что deg(f ) = 1, W (f, 1) = 2O(n) и для всякого D верно W (f, D) = 2(n/D ) (здесь константа в (n/D2 ) не зависит от D).

Этот результат был получен в связи с разделением некоторых сложностных классов. Теорема X была доказана в обозначениях {0, 1}, но она не переносится автоматически на обозначения {1, +1} с помощью леммы V, так как резуль тат верен и для D зависящих от n. Однако, доказательство Бейгеля легко переносится и на обозначения {1, +1}.

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

о n1/ Теорема 2. Для всех n и d D log n, где – некоторая положительная константа, существует (явно заданная) функция f, такая что deg(f ) = d, d d /D4d W (f, d) = 2O(n ) и W (f, D) = 2(n), где – некоторая положительная константа.

Заметим, что этот результат не полностью обобщает результат Бейгеля, так как построенная нами функция зависит от D, а также показатель экспоненты содержит D4 (при d = 1), а не D2.

Теорема 2 содержательна и для непостоянных D. Например, мы можем зафиксировать произвольное d и положить D = log n. Тогда мы получаем последовательность функций fn : {0, 1}n {0, 1} пороговой степени d, таких что всякий пороговый элемент степени не выше log n, вычисляющий fn, имеет Richard Beigel. Perceptrons, PP, and the polynomial hierarchy. Computational Complexity, 4:339–349, 1994.

4d d вес 2(n / log n). В частности, эта оценка верна для всех пороговых элементов любой постоянной степени.

Доказательство теоремы 2, также как и теоремы X, проходит в обозначе ниях {0, 1}. Однако, так же, как и в случае теоремы X, доказательство легко переносится и на обозначения {1, +1}.

Получение оценок на веса пороговых элементов интересно также и для функций из ограниченных классов. В главе 3 мы рассмотрим один из самых простых таких классов (в том смысле, что функции, лежащие в нем, вычисли мы булевыми схемами очень ограниченного вида), а именно дизъюнктивные нормальные формы (ДНФ) полиномиального (от числа переменных) разме ра. Этот класс активно изучался в теории обучения, в частности, и с точки зрения пороговой степени и порогового веса (смотри работу52 и ссылки в ней).

Известно, что для всякой полиномиальной ДНФ в обозначениях {0, 1} есть по 1/ роговый элемент степени O(n1/2 log n) с весом 2O(n log n), а также пороговый элемент степени O(n1/3 log n)53. Функция из теоремы X также представима в виде полиномиальной ДНФ.

Мы докажем, что если d постоянно, то существуют полиномиальные ДНФ, удовлетворяющие теореме 2. Это дает первую более чем экспоненциальную оценку (большую, чем 2(n) ) на веса пороговых элементов для функций, пред ставимых в виде полиномиальных ДНФ.

В параграфе 3.1 мы строим функции, удовлетворяющие теореме 2. В пара графе 3.2 мы изучаем вопросы, связанные с представлением этих функций в виде ДНФ. В параграфе 3.3 мы формулируем основной результат этой главы и приступаем к доказательству. В параграфе 3.4 мы неформально описыва ем основные идеи доказательства теоремы 2. В параграфе 3.5 мы доказываем необходимые вспомогательные результаты. В параграфе 3.6 мы доказываем теорему 2 и формулируем следствия из нее. Доказательство получается раз витием метода, использованного для доказательства теоремы 1.

Можно заметить, что для функции, построенной в теореме IX, величина W (f, d) меняется плавно при изменении d. То есть, при увеличении d на 1/ Adam R. Klivans and Rocco A. Servedio. Learning DNF in time 2O(n ). J. Comput. Syst. Sci., 68(2):303–318, 2004.

1/ Adam R. Klivans and Rocco A. Servedio. Learning DNF in time 2O(n ). J. Comput. Syst. Sci., 68(2):303–318, 2004.

величина W (f, d) для этих функций уменьшается не более чем полиномиаль но. Для функции из теоремы X W (f, d) слабо меняется при d близких к 1 (в действительности, в работе54 доказывается, что оценка в теореме X близка к точной для всех d = O(n1/3 ), так что W (f, d) для функции из этой теоремы меняется плавно для всех d не превышающих O(n1/3 )). Для функции из теоре мы 2 W (f, d) слабо меняется при D близких к d. Возникает вопрос, возможна ли обратная ситуация. То есть, существуют ли функции f, для которых вели чина W (f, d) сильно изменяется при небольших изменениях d? В главе 4 мы даем положительный ответ на этот вопрос. Результаты главы 4 справедливы в обозначениях {1, +1}, и это существенно используется в доказательстве. Не известно, можно ли перенести эти результаты на обозначения {0, 1}.

Теорема 3. Для всех n и для всякого d = 1, 2,..., n 1 (d может зависеть от n) существует (явно заданная) функция f : {1, +1}n {1, +1}, такая что W (f, d) = exp{(n)} и W (f, d + 1) = O(n2 ) (постоянные в и O не зависят от d).

Другими словами, мы покажем, что требующийся вес пороговых элемен тов для заданной функции может сильно измениться в ответ на небольшие изменения степени пороговых элементов. Этот результат опубликован в сов местной работе [2]. Для d n, где – некоторая константа, результат теоремы доказана автором. Для d n результат теоремы доказан А. А. Шерстовым.

Кроме того, мы доказываем результат, аналогичный теореме 3, для порого вой длины.

Теорема 4. Для всех n и для всякого d = 1, 2,..., n 1 (d может зависеть от n) существует (явно заданная) функция f : {1, +1}n {1, +1}, такая что L(f, d) = exp{(d)} и L(f, d + 1) = O(d).

Adam R. Klivans and Rocco A. Servedio. Toward attribute ecient learning of decision lists and parities.

J. Machine Learning Research, 7:587–602, 2006.

Оценка на L(f, d) в этом результате близка к оптимальной, так как суще ствует не более (n + 1)d одночленов степени не выше d. То есть, длина всякого порогового элемента степени не выше d не превышает (n + 1)d.

Наконец, мы доказываем следующее обобщение теоремы 3.

Теорема 5. Для всех n и для всяких d = 1, 2,..., n1 и k = 1, 2,..., max{d, n d}, существует (явно заданная) функция f : {1, +1}n {1, +1}, такая что W (f, d) = W (f, d + 1) = · · · = W (f, d + k 1) = 2(n/k) и n W (f, d + k) = O.

k В этой теореме для d n, где – некоторая константа, доказательство принадлежит автору. Для d n доказательство принадлежит А. А. Шерсто ву.

Доказательство результатов главы 4 сочетает в себе технику преобразова ний Фурье, линейной алгебры и теории приближений.

В параграфе 4.1 мы формулируем основные результаты главы. В парагра фе 4.2 мы доказываем вспомогательные соотношения между различными пара метрами булевых функций. В параграфе 4.3 мы доказываем вспомогательный результат о пороговых элементах для функций, спектр которых не равен нулю лишь на афинном подпространстве Zn. В параграфе 4.4 мы доказывам основ ной результат главы для случая d n, где – некоторая константа. Результат доказывается сначала для d = 1, а затем с помощью результатов параграфа 4. обобщается на все d n. В параграфе 4.5 мы доказываем основной результат главы для случая d n, а также теорему 4. Для этого мы используем совер шенно другую технику. В параграфе 4.6 мы доказываем основной результат этой главы, а также его обобщения.

Благодарности.

Автор выражает глубокую благодарность своему научному руководителю доктору физико–математических наук, профессору Николаю Константинови чу Верещагину за постановку задач и помощь в работе. Автор благодарит академика РАН Сергея Ивановича Адяна за внимание к работе. Автор при знателен участникам "Колмогоровского семинара по сложности вычислений и сложности описаний" и участникам семинара "Алгоритмические вопросы алгебры и логики" за полезные обсуждения. Автор также благодарен всем со трудникам кафедры математической логики и теории алгоритмов за теплую творческую атмосферу.

Список литературы [1] В. В. Подольский. Перцептроны с большим весом. Проблемы передачи информации, 45(1):51–59, 2009.

[2] В. В. Подольский, А. А. Шерстов. Уменьшение на единицу степени многочлена с за данной знаковой функцией может экспоненциально увеличить его вес и длину. Успехи математических наук, 69(5):179–180, 2009.

[3] Vladimir V. Podolskii. Perceptrons of large weight. In Proc. of the Second International Computer Science Symposium in Russia (CSR), pages 328–336, 2007.

[4] Vladimir V. Podolskii. A uniform lower bound on weights of perceptrons. In Proc. of the Third International Computer Science Symposium in Russia (CSR), pages 261–272, 2008.

В работе [2] В. В. Подольскому принадлежат теоремы 3 и 4;

А. А. Шерстову принадлежат теоремы 2 и 5;

теорема 1 непосредственно вытекает из теорем 4 и 5.