Теорема Ковера

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

Теорема

Теорема выражает число однородно линейно разделимых множеств $N$ указывает на $D$ размеры как явная считающая функция $C(N,D)$ от количества очков $N$ и размерность $D$ .

В качестве необходимого и достаточного условия требуется, чтобы точки находились в общем положении . Проще говоря, это означает, что точки должны быть максимально линейно независимыми (несовмещенными). Это условие выполняется «с вероятностью 1» или почти наверняка для случайных наборов точек, тогда как для реальных данных оно может быть легко нарушено, поскольку они часто структурированы по многообразиям меньшей размерности в пространстве данных.

Функция $C(N,D)$ следует двум различным режимам в зависимости от взаимоотношений между $N$ и $D$ .

Для $N\leq D+1$ , функция является экспоненциальной по $N$ . По сути, это означает, что любой набор помеченных точек в общем положении и в количестве, не превышающем размерность + 1, линейно разделим; на жаргоне говорят, что линейный классификатор разбивает любой набор точек с $N\leq D+1$ . Эта предельная величина известна также как размерность Вапника-Червоненкиса линейного классификатора.

Для $N>D+1$ , считающая функция начинает расти менее чем экспоненциально. Это означает, что при наличии выборки фиксированного размера $N$ , для большей размерности $D$ более вероятно, что случайное множество помеченных точек является линейно разделимым. И наоборот, при фиксированной размерности для больших размеров выборки количество линейно разделимых наборов случайных точек будет меньше, или, другими словами, вероятность найти линейно разделимую выборку будет уменьшаться с увеличением $N$ .

Следствием теоремы является то, что, учитывая набор обучающих данных, которые не являются линейно разделимыми , можно с высокой вероятностью преобразовать его в обучающий набор, который является линейно разделимым, проецируя его в многомерное пространство посредством некоторого нелинейного преобразования . или:

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

Доказательство

Доказательство теоремы Ковера о считающей функции можно получить из рекуррентного соотношения

$C(N+1,D)=C(N,D)+C(N,D-1).$

Чтобы показать это, при фиксированном $N$ , увеличение $D$ может превратить набор точек из неразделимых в разделимые, можно использовать детерминированное отображение : предположим, что существуют $N$ точки. Поднимите их на вершины симплекса в $N-1$ многомерное реальное пространство. Поскольку каждое разделение выборок на два набора можно разделить линейным разделителем , отсюда следует это свойство.

См. также

Ссылки

Хайкин, Саймон (2009). Нейронные сети и обучающиеся машины (Третье изд.). Река Аппер-Сэддл, Нью-Джерси: Pearson Education Inc., стр. 232–236. ISBN 978-0-13-147139-9 .
Обложка, ТМ (1965). «Геометрические и статистические свойства систем линейных неравенств с приложениями в распознавании образов» (PDF) . Транзакции IEEE на электронных компьютерах . EC-14 (3): 326–334. дои : 10.1109/pgec.1965.264137 . S2CID 18251470 . Архивировано из оригинала (PDF) 20 декабря 2019 г.
Мехротра, К.; Мохан, СК; Ранка, С. (1997). Элементы искусственных нейронных сетей (2-е изд.). МТИ Пресс. ISBN 0-262-13328-8 . (раздел 3.5)

Эта статистике статья, посвященная , незавершена . Вы можете помочь Википедии, расширив ее .