WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

загрузка...
   Добро пожаловать!

Pages:     || 2 | 3 |
Московский государственный университет имени М. В. Ломоносова Механико-математический факультет

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

УДК 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 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 2(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.

Jeffrey 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 efficient 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 Hstad, 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 для этой 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 Hstad, 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 Hstad, and Alexander A. Razborov. Majority gates vs. general weighted threshold gates. Computational Complexity, 2:277–300, 1992.

Johan Hstad. 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 г.).

Pages:     || 2 | 3 |






© 2011 www.dissers.ru - «Бесплатная электронная библиотека»