Эффективное вычисление или аппроксимация VC-измерения нейронной сети

19

Моя цель состоит в том, чтобы решить следующую проблему, которую я описал ее вводом и выводом:

Входные данные:

Направленный ациклический граф с узлами, источниками и стоком ( ).грамммN1м>N1

Выход:

VC-размерность (или приближение к ней) для нейронной сети с топологией .грамм

Больше подробностей :

  • Каждый узел в является сигмовидным нейроном. Топология фиксирована, но веса на ребрах могут варьироваться алгоритмом обучения.грамм
  • Алгоритм обучения фиксирован (скажем, обратное распространение).
  • В узлами источника являются входными нейронами и может принимать только строки из в качестве входных данных.N{-1,1}N
  • Узел приемника является единицей вывода. Он выводит реальное значение из которое мы округляем до или до если оно больше определенного фиксированного порога от .[-1,1]1-1δ0

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


Вопрос

Существует ли эффективный способ (т. при изменении на задачу решения: размерность VC меньше входного параметра ?) Для вычисления этой функции? Если нет, есть ли результаты твердости?пК

Существует ли эффективный на практике способ вычисления или аппроксимации этой функции? Если это приближение, есть ли гарантии на его точность?

Примечания

Я задал похожий вопрос на stats.SE, но он не вызвал интереса.

Артем Казнатчеев
источник
1
Это могло бы сделать вопрос более автономным, если бы вы могли сделать передаточную функцию более явной. Т.е. указать фактические формулы для распространения информации.
Суреш

Ответы:

9

Если вы хотите еще больше ограничить проблему, разрешив многоуровневую сеть, то «Машинное обучение» Тома Митчелла дает верхнюю границу ( ) (раздел 7.4.4), где s - это число внутренние узлы (которые должны быть больше 2), d - это размерность VC отдельных узлов, а e - это основание натурального логарифма. Если вам не хватает количества обучающих примеров, то этой информации должно быть достаточно.2dsжурнал(еs)sdе

Это не совсем ответ на ваш вопрос, но он может помочь вам в пути. Результат обусловлен Баумом и Хаусслером (1989).

Питер
источник