RUS  ENG ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ЛИЧНЫЙ КАБИНЕТ
Общая информация
Последний выпуск
Архив
Импакт-фактор
Правила для авторов

Поиск публикаций
Поиск ссылок

RSS
Последний выпуск
Текущие выпуски
Архивные выпуски
Что такое RSS



Пробл. передачи информ.:
Год:
Том:
Выпуск:
Страница:
Найти






Персональный вход:
Логин:
Пароль:
Запомнить пароль
Войти
Забыли пароль?
Регистрация


Пробл. передачи информ., 2009, том 45, выпуск 1, страницы 51–59 (Mi ppi1259)  

Эта публикация цитируется в 7 научных статьях (всего в 7 статьях)

Теория автоматов

Перцептроны с большим весом

В. В. Подольский

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

Аннотация: Пороговым элементом называется линейная комбинация входных переменных с целыми коэффициентами (весами). Он выдает 1, если сумма положительна. Максимальное абсолютное значение коэффициентов порогового элемента называется его весом. Перцептрон степени $d$ – это булева схема глубины 2 с пороговым элементом в вершине и произвольными булевыми элементами входной степени не выше $d$ на нижнем уровне. Весом перцептрона называется вес его порогового элемента.
Для всякого постоянного $d\geq 2$, не зависящего от числа входных переменных $n$, мы строим перцептрон степени $d$, для которого требуются веса, не меньшие $n^{\Omega(n^d)}$, т.е. вес всякого перцептрона степени $d$, вычисляющего ту же булеву функцию, должен быть не меньше $n^{\Omega(n^d)}$. Эта оценка точна: всякий перцептрон степени $d$ эквивалентен перцептрону степени $d$ с весом $n^{O(n^d)}$ Для случая пороговых элементов (т.е. $d=1$) результат был доказан Хостадом в [2]; мы используем технику Хостада.

Полный текст: PDF файл (564 kB)
Список литературы: PDF файл   HTML файл

Англоязычная версия:
Problems of Information Transmission, 2009, 45:1, 46–53

Реферативные базы данных:

УДК: 621.391.1:004.8
Поступила в редакцию: 22.07.2008

Образец цитирования: В. В. Подольский, “Перцептроны с большим весом”, Пробл. передачи информ., 45:1 (2009), 51–59; Problems Inform. Transmission, 45:1 (2009), 46–53

Цитирование в формате AMSBIB
\RBibitem{Pod09}
\by В.~В.~Подольский
\paper Перцептроны с~большим весом
\jour Пробл. передачи информ.
\yr 2009
\vol 45
\issue 1
\pages 51--59
\mathnet{http://mi.mathnet.ru/ppi1259}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=2513163}
\zmath{https://zbmath.org/?q=an:1171.68585}
\transl
\jour Problems Inform. Transmission
\yr 2009
\vol 45
\issue 1
\pages 46--53
\crossref{https://doi.org/10.1134/S0032946009010062}
\isi{http://gateway.isiknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&DestLinkType=FullRecord&DestApp=ALL_WOS&KeyUT=000265776300006}
\scopus{http://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-65549151265}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/ppi1259
  • http://mi.mathnet.ru/rus/ppi/v45/i1/p51

    ОТПРАВИТЬ: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles

    Эта публикация цитируется в следующих статьяx:
    1. В. В. Подольский, А. А. Шерстов, “Небольшое уменьшение степени многочлена с заданной знаковой функцией может экспоненциально увеличить его вес и длину”, Матем. заметки, 87:6 (2010), 885–899  mathnet  crossref  mathscinet; V. V. Podolskii, A. A. Sherstov, “A Small Decrease in the Degree of a Polynomial with a Given Sign Function Can Exponentially Increase Its Weight and Length”, Math. Notes, 87:6 (2010), 860–873  crossref  isi
    2. Diakonikolas I., Servedio R.A., Tan L.-Ya., Wan A., “A Regularity Lemma, and Low-weight Approximators, for Low-degree Polynomial Threshold Functions”, 25th Annual IEEE Conference on Computational Complexity - Ccc 2010, Annual IEEE Conference on Computational Complexity, 2010, 211–222  crossref  mathscinet  isi
    3. Babai L., Hansen K.A., Podolskii V.V., Sun X., “Weights of Exact Threshold Functions”, Mathematical Foundations of Computer Science 2010, Lecture Notes in Computer Science, 6281, 2010, 66–77  crossref  mathscinet  zmath  isi
    4. В. В. Подольский, “Однородная по степени нижняя оценка на веса многочленов с заданной знаковой функцией”, Алгоритмические вопросы алгебры и логики, Сборник статей. К 80-летию со дня рождения академика Сергея Ивановича Адяна, Тр. МИАН, 274, МАИК «Наука/Интерпериодика», М., 2011, 252–268  mathnet  mathscinet; Vladimir V. Podolskii, “Degree-uniform lower bound on the weights of polynomials with given sign function”, Proc. Steklov Inst. Math., 274 (2011), 231–246  crossref  isi
    5. De A., Diakonikolas I., Servedio R.A., “Deterministic Approximate Counting For Juntas of Degree-2 Polynomial Threshold Functions”, 2014 IEEE 29Th Conference on Computational Complexity (Ccc), IEEE Conference on Computational Complexity, IEEE, 2014, 229–240  crossref  mathscinet  isi
    6. Viola E., “the Communication Complexity of Addition”, Combinatorica, 35:6 (2015), 703–747  crossref  mathscinet  isi  elib
    7. Rao Ya., Zhang X., “Characterization of Linearly Separable Boolean Functions: a Graph-Theoretic Perspective”, IEEE Trans. Neural Netw. Learn. Syst., 28:7 (2017), 1542–1549  crossref  mathscinet  isi  scopus
  • Проблемы передачи информации Problems of Information Transmission
    Просмотров:
    Эта страница:369
    Полный текст:44
    Литература:26
    Первая стр.:17

     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2018