Klasyfikatory uczenia maszynowego duże O lub złożoność

Aby ocenić wydajność nowego algorytmu klasyfikatora, próbuję porównać dokładność i złożoność (duże O w treningu i klasyfikacji). Z uczenia maszynowego: recenzja Otrzymuję pełną listę nadzorowanych klasyfikatorów, tabelę dokładności między algorytmami i 44 problemy testowe z repozytorium danych UCI . Nie mogę jednak znaleźć recenzji, artykułu papierowego ani strony internetowej z dużym O dla popularnych klasyfikatorów, takich jak:

C4.5
RIPPER (Myślę, że to może nie być możliwe, ale kto wie)
ANN z propagacją wsteczną
Naiwny Bayesian
K-NN
SVM

Jeśli ktoś ma jakieś zdanie na temat tych klasyfikatorów, będzie to bardzo przydatne, dziękuję.

— Dinl
źródło

Może Cię zainteresować następujący artykuł: thekerneltrip.com/machine/learning/... Pełna klauzula o wyłączności , to mój blog :)

— RUser4512

Chcesz prześledzić miejsca, w których wskazywały już martwe linki pytania?

— mat

@ RUser4512 naprawdę świetna narada na blogu! czy rozważałeś także dodanie złożoności przestrzeni?

— mat.

@matt Dziękuję :) tak, ale prawdopodobnie w innym artykule jest wiele do powiedzenia na ten temat!

— RUser4512

Niech = liczba przykładów szkoleniowych, = wymiarowość cech = liczba klas. $N$ $d$ $c$

Zatem szkolenie ma złożoność:

Naiwny Bayes to , wystarczy tylko obliczyć częstotliwość każdej wartości cechy dla każdej klasy. $O(Nd)$ $d_i$
-NN znajduje się w (niektórzy twierdzą nawet, że nie istnieje, ale złożoność treningu w przestrzeni to ponieważ trzeba przechowywać dane, co również wymaga czasu). $k$ $\mathcal{O}(1)$ $\mathcal{O}(Nd)$
$O(N^2)$ $O(N^3)$ $O(N^3)$ $O(N^{2.3})$
$O(NR)$

Testowanie złożoności:

$\mathcal{O}(cd)$ $d$ $c$
$k$ $\mathcal{O}(Nd)$ ponieważ musisz porównać punkt testowy z każdym punktem danych w bazie danych.

Źródło: „Podstawowe maszyny wektorowe: Szybkie szkolenie SVM na bardzo dużych zestawach danych” - http://machinelearning.wustl.edu/mlpapers/paper_files/TsangKC05.pdf

Przepraszam, nie wiem o innych.

— samthebest
źródło

Nie do końca prawda: złożoność treningowa SVM jądra jest pomiędzy

O (n^{2})

$O(n^2)$ i

O (n^{3})

$O(n^3)$ w zależności od C ; Patrz np. Obsługa wektorowych solverów maszynowych Bottou i Lin (sekcja 4.2).

— Marc Claesen

@MarcClaesen Link już nie działa i nie znajduje się na maszynie powrotnej. Czy to ten sam artykuł: leon.bottou.org/publications/pdf/lin-2006.pdf ?

— wordsforthewise