WWW.DISSERS.RU

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

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

Pages:     | 1 | 2 ||

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

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

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

Mikael Goldmann, Johan Hstad, 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 W (f, d) = 2O(n ) и W (f, D) = 2(n) /D4d, где – некоторая положительная константа.

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

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

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

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

Известно, что для всякой полиномиальной ДНФ в обозначениях {0, 1} есть по1/роговый элемент степени O(n1/2 log n) с весом 2O(n log2 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 2(n ). J. Comput. Syst. Sci., 68(2):303–318, 2004.

1/Adam R. Klivans and Rocco A. Servedio. Learning DNF in time 2(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 efficient 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,..., n-1 и k = 1, 2,..., max{d, nd}, существует (явно заданная) функция f : {-1, +1}n {-1, +1}, такая что W (f, d) = W (f, d + 1) = · · · = W (f, d + k - 1) = 2(n/k) и nW (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.

Pages:     | 1 | 2 ||






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