Классификаторы машинного обучения Big-O или сложности

Чтобы оценить производительность нового алгоритма классификатора, я пытаюсь сравнить точность и сложность (большое в обучении и классификации). Из машинного обучения: обзор Я получаю полный список контролируемых классификаторов, а также таблицу точности между алгоритмами и 44 задачи тестирования из репозитория данных UCI . Тем не менее, я не могу найти обзор, бумагу или веб-сайт с Big-O для общих классификаторов, таких как:

C4.5
РИППЕР (я думаю, что это может быть невозможно, но кто знает)
ANN с обратным распространением
Наивный байесовский
K-NN
SVM

Если у кого-нибудь есть выражение для этих классификаторов, это будет очень полезно, спасибо.

machine-learning classification multiple-comparisons algorithms time-complexity Dinl
источник

Вы можете быть заинтересованы в следующей статье: thekerneltrip.com/machine/learning/… Полный отказ от ответственности, это мой блог :)

RUser4512

Не хочешь отследить места, на которые сейчас указывают мертвые ссылки вопроса?

Мэтт

@ RUser4512 действительно отличный блог! Вы также решили добавить сложность пространства?

Мэтт

@matt Спасибо :) да, но, вероятно, в другой статье, есть много вещей, чтобы сказать об этом!

RUser4512

Ответы:

$N$ $d$ $c$

Тогда обучение имеет сложности:

$O(Nd)$ $d_i$
$k$ $\mathcal{O}(1)$ $\mathcal{O}(Nd)$
$O(N^2)$ $O(N^3)$ $O(N^3)$ $O(N^{2.3})$
$O(NR)$

Сложности тестирования:

$\mathcal{O}(cd)$ $d$ $c$
$k$ $\mathcal{O}(Nd)$

Источник: «Основные векторные машины: быстрое обучение SVM по очень большим наборам данных» - http://machinelearning.wustl.edu/mlpapers/paper_files/TsangKC05.pdf

Извините, я не знаю о других.

samthebest
источник

O (n^{2})

$O(n^2)$

O (n^{3})

$O(n^3)$

@MarcClaesen Ссылка больше не работает, и она не на обратном пути. Это тот же документ: leon.bottou.org/publications/pdf/lin-2006.pdf ?

словами