|
Эта публикация цитируется в 2 научных статьях (всего в 2 статьях)
Знаковый ранг и размерность Вапника–Червоненкиса
Н. Алонabc, Ш. Моранdbe, А. Ягудаевf a Sackler School of Mathematics and Blavatnik School of Computer Science, Tel Aviv University, Tel Aviv, Israel
b Microsoft Research, Herzliya, Israel
c School of Mathematics, Institute for Advanced Study, Princeton,
NJ, USA
d Department of Computer Science, Technion – Israel Institute of Technology, Haifa, Israel
e Max Planck Institute for Informatics, Saarbrücken, Germany
f Department of Mathematics, Technion – Israel Institute of Technology, Haifa, Israel
Аннотация:
Исследуется наибольший возможный знаковый ранг знаковых $(N \times N)$-матриц с заданной размерностью Вапника–Червоненкиса $d$. При $d=1$ этот максимум равен трем. При $d=2$ этот максимум имеет порядок $\widetilde{\Theta}(N^{1/2})$. При $d >2$ верны аналогичные, но менее точные утверждения. Нижние оценки улучшают результаты, полученные ранее Бен-Дэвидом с соавторами, верхние оценки являются новыми.
Нижние оценки получены при помощи вероятностных конструкций с использованием теоремы Уоррена из вещественной алгебраической топологии. Верхние оценки получены с использованием результата Вельцля об остовных деревьях с небольшим числом Хелли и с использованием кривой моментов.
Техника верхних оценок также используется: (i) для получения оценок на количество классов заданной размерности Вапника–Червоненкиса и на количество максимальных классов заданной размерности Вапника–Червоненкиса – тем самым получен ответ на вопрос, поставленный Франклем в 1989 г., и (ii) для разработки эффективного алгоритма, вычисляющего приближение знакового ранга с мультипликативной сложностью $O(N/\log(N))$.
Также отмечается общая связь между знаковым рангом и спектральными зазорами, которая основывается на рассуждениях Форстера. Рассмотривается $(N \times N)$-матрица смежности $\Delta$-регулярного графа, где $\Delta \leq N/2$, и ее второе собственное значение по модулю полагается равным $\lambda$.
Показано, что знаковый ранг знакового аналога этой матрицы не меньше чем $\Delta/\lambda$.
Эта связь используется при доказательстве существования максимального класса $C\subseteq\{\pm 1\}^N$, имеющего размерность Вапника–Червоненкиса $2$ и знаковый ранг $\widetilde{\Theta}(N^{1/2})$. Это дает ответ на вопрос Бен-Дэвида и его соавторов о знаковом ранге больших классов Вапника–Червоненкиса. Также указываются ограничения используемого подхода в духе теоремы Алона–Боппана.
Далее описываются связи с коммуникационной сложностью, геометрией, теорией обучения и комбинаторикой.
Библиография: 69 названий.
Ключевые слова:
размерность Вапника–Червоненкиса, конфигурация гиперплоскостей, знаковый ранг, полупространства, линейные классификаторы, коммуникационная сложность с неограниченной погрешностью.
Поступила в редакцию: 06.07.2016 и 14.10.2016
Образец цитирования:
Н. Алон, Ш. Моран, А. Ягудаев, “Знаковый ранг и размерность Вапника–Червоненкиса”, Матем. сб., 208:12 (2017), 4–41; N. Alon, Sh. Moran, A. Yehudayoff, “Sign rank versus Vapnik-Chervonenkis dimension”, Sb. Math., 208:12 (2017), 1724–1757
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/sm8780https://doi.org/10.4213/sm8780 https://www.mathnet.ru/rus/sm/v208/i12/p4
|
Статистика просмотров: |
Страница аннотации: | 382 | PDF русской версии: | 305 | PDF английской версии: | 10 | Список литературы: | 32 | Первая страница: | 19 |
|