Classificadores de aprendizado de máquina big-O ou complexidade

14

Para avaliar o desempenho de um novo algoritmo classificador, estou tentando comparar a precisão e a complexidade (grande O no treinamento e classificação). No Machine Learning: uma revisão , recebo uma lista completa de classificadores supervisionados, também uma tabela de precisão entre os algoritmos e 44 problemas de teste no repositório de dados da UCI . No entanto, não consigo encontrar uma crítica, documento ou site com o big-O para classificadores comuns como:

  • C4.5
  • RIPPER (acho que isso pode não ser possível, mas quem sabe)
  • RNA com Propagação Traseira
  • Ingênuo bayesiano
  • K-NN
  • SVM

Se alguém tiver alguma expressão para esses classificadores, será muito útil, obrigado.

Dinl
fonte
2
Você pode estar interessado no seguinte artigo: thekerneltrip.com/machine/learning/... negação completa, é meu blog :)
RUser4512
Importa-se de rastrear os locais onde os agora links mortos da questão apontaram?
18818 matt19
@ RUser4512 realmente ótimo blog deliberação! você também considerou adicionar complexidade de espaço?
18818 matt19
1
@matt Obrigado :) sim, mas provavelmente em outro artigo, há muitas coisas a dizer sobre isso também!
precisa

Respostas:

11

Seja = número de exemplos de treinamento, d = dimensionalidade dos recursos ec = número de aulas.Ndc

Então o treinamento tem complexidades:

  1. Naive Bayes é , tudo o que precisa fazer é calcular a frequência de cada valor de recurso d i para cada classe.O(Nd)dEu
  2. -NN está em O ( 1 ) (algumas pessoas até dizem que é inexistente, mas a complexidade espacial do treinamento é O ( N d ), pois você precisa armazenar os dados, o que também leva tempo).kO(1)O(Nd)
  3. SVM não linear não aproximado é O ( N 2 ) ou O ( N 3 ), dependendo do kernel. Você pode obter um O ( N 3 ) abaixo de O ( N 2.3 ) com alguns truques.O(N2)O(N3)O(N3)O(N2.3)
  4. SVM aproximado é , onde R é o número de iterações.O(NR)

Complexidades de teste:

  1. O ingênuo Bayes está em pois é necessário recuperar d valores de recursos para cada uma das classes c .O(cd)dc
  2. -NN está em O ( N d ), pois você precisa comparar o ponto de teste com todos os pontos de dados do seu banco de dados.kO(Nd)

Fonte: "Máquinas vetoriais principais: treinamento rápido sobre SVM em conjuntos de dados muito grandes" - http://machinelearning.wustl.edu/mlpapers/paper_files/TsangKC05.pdf

Desculpe, eu não sei sobre os outros.

samthebest
fonte
6
Não está totalmente certo: a complexidade do treinamento do SVM do kernel está entre e O ( n 3 ), dependendo de C ; Consulte, por exemplo , os solventes da máquina de vetores de suporte da Bottou e Lin (seção 4.2). O(n2)O(n3)
Marc Claesen
@ MarcClaesen O link não funciona mais e não está na máquina de retorno. Este é o mesmo artigo: leon.bottou.org/publications/pdf/lin-2006.pdf ?
wordsforthewise