Московский государственный университет

имени М. В. Ломоносова

Механико-математический факультет

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

УДК 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) > для всякого 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 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.

Не менее активно изучалось понятие пороговой длины, смотри 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 halfspaces. 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):808–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.

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 halfspaces. Machine Learning, 69(2–3):97–114, 2007.

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

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

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

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

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

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

1. Для всех d и n построена булева функция от n переменных пороговой степени 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.

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

Adam R. Klivans and Alexander A. Sherstov. Unconditional lower bounds for learning intersections of halfspaces. 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, • 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 входных переменных. Мы будем изучать, как ведут себя различные величины, связанные с булевой функцией 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)|;

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} называется всякое выражение вида где 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} называется выражение вида где 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) (в обоих обозначениях булевых переменных) не могут увеличиваться при росте Реализация булевых функций пороговыми элементами соответствует реализации булевых функций булевыми схемами специального вида. Более точно, пусть F – некоторое семейство булевых функций. Персептроном в базисе F называется булева схема глубины 2 с линейным пороговым элементом на верхлинейный пороговый элемент нем уровне и с произвольными булевыми функциями f1,..., fk из F на нижнем уровне (смотри рисунок).

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

Пороговым элементам степени не выше некоторого 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 в обоn значениях {0, 1}, то 2 p( 2 (1 x1 ),..., 1 (1 xn )) – пороговый элемент степени d для функции f в обозначениях {1, +1} (множитель 2d нужен, чтобы сделать коэффициенты многочлена целыми, так как после замены переменных они имеют вид 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 следует также такой результат.

верно 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.

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

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

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

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

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 > 1 из теоремы VI легко получается верхняя оценка nO(n ) на веса пороговых элементов степени d для заданных функций.

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

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

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

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

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

константа, существует (явно заданная) функция f, такая что deg(f ) = d, константа.

Заметим, что этот результат не полностью обобщает результат Бейгеля, так как построенная нами функция зависит от 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.

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

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

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

Известно, что для всякой полиномиальной ДНФ в обозначениях {0, 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 на Adam R. Klivans and Rocco A. Servedio. Learning DNF in time 2O(n ). J. Comput. Syst. Sci., 68(2):303–318, 2004.

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}, такая что (постоянные в и O не зависят от d).

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

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

Теорема 4. Для всех n и для всякого d = 1, 2,..., n 1 (d может зависеть от n) существует (явно заданная) функция f : {1, +1}n {1, +1}, такая что 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}, такая что В этой теореме для 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.