Análise de Algoritmos de Machine Learning
Seja bem-vindo de volta, caro humano. Aproveitando essa nossa fase de ficar analisando algoritmos (que começou nesse post e nesse outro), vamos para o que é realmente interessante: machine learning. Sim, chegou a hora de conhecer melhor as engrenagens dos mais famosos algoritmos de inteligência artificial. Como esses algoritmos são muito longos, não vamos escrever passo-a-passo como fizemos nos outros posts, mas qualitativamente vamos passar pelos algoritmos mais importantes.
Infelizmente, é impossível analisar todos os algoritmos da área em um único post (porque, acredite ou não, eles são muitos), então vamos nos ater aos modelos mais famosos.
Mas, como toda boa análise, vamos começar com uma tabela:
Legenda:
- n = número de dados de treino.
- p = número de features.
- t = número de árvores.
- s = número de vetores suporte.
Antes de ir para o ponto da questão, vamos fazer algumas considerações. O que pesa principalmente na eficiência dos algoritmos são sua quantidade de features e dados de treino. É aí que está a importância de escolher as melhores features e também tratar direito seus dados (o que você pode encontrar nesse nosso post aqui). Então, por mais que, matematicamente, essas complexidades estejam corretas, o Big-O sempre considera o pior caso, então dependendo do que você estiver fazendo, isso pode melhorar.
Decision Tree
Primeiro de tudo, é muito importante conhecer bem o seu modelo. Mas, para isso, nós temos esse post aqui para te ensinar o necessário. Depois que você tiver uma ideia, vamos ver como isso funciona. Já deixo claro que é importante o entendimento de árvores binárias para que a seguinte análise flua com mais facilidade.
Basicamente, uma árvore de decisão faz sua avaliação levando em consideração cada divisão dos dados e vai fazer isso para cada feature em cada nó que não é o nó de uma folha. Isso acontece a medida que os níveis continuam. Supondo uma árvore binária totalmente balanceada, a complexidade será O(log(n)), porque você simplesmente deverá contar quantos níveis tem. Se tivermos 1 nó, com 2 filhos e cada um deles com 2 filhos, teremos que analisar 3 camadas (o que é, aproximadamente, log de 8 na base 2, que é 3).
Porém, se tivermos uma árvore totalmente desbalanceada, com uma concentração única em um lado, teremos que andar N camadas, o que nos deixa com uma complexidade de O(n).
Além disso, outra coisa que deve ser levada em consideração é o fato que nós também temos que calcular uma probabilidade em cada nó para calcular a entropia para fazer o corte. Isso adicionará uma complexidade de O(log(n)), na mesma lígica que usamos anteriormente, por causa da estrutura de árvore binária.
Então vejamos, a complexidade de uma Decision Tree será de O(n * p * d * log(n)), sendo d a profundidade de camadas. Aplicando o que acabamos de descobrir, temos que a complexidade da árvore estará entre algo como O(n * p * log²(n)) e O(n² * p * log(n))
Random Forest
Se você não está totalmente familiarizado com esse modelo, sugiro esse nosso post.
Esse algoritmo só está aqui porque ele é basicamente o que fizemos antes… Mas multiplicado pelo número de árvores, já que a Random Forest não passa de um monte de resultados comparados de um monte de Decision Trees. Então, considerando o que foi passado anteriormente, podemos ver que a eficiência desse algoritmo estará entre algo como O(n * p * log²(n) * t) e O(n² * p * log(n) * t).
Regressão Linear
Agora é o momento desse nosso post brilhar.
Basicamente, a Regressão Linear se resume a um conjunto de multiplicações de matrizes. A complexidade de multiplicar duas matrizes, considerando que serão dois for’s encaixados, como podemos ter uma noção a partir desse post, é de 0(n²) (mas nesse caso, a matriz a ser multiplicada é de features, não a de número de dados). Como teremos que fazer isso para cada feature, teremos uma complexidade final de O(n*p²), quando avaliando X’X (a matriz e seu inverso).
Mas isso não é tudo. Quando fazemos essa multiplicação, também precisamos calcular a matriz inversa para fazer esse trabalho. Para cada feature, teremos portanto que fazer uma inversão, o que nos obriga a acrescentar a inversão dessa matriz. Para finalizar, portanto, temos uma complexidade padrão de O(n* p² + p³).
SVM
Esse é o post que vai te ajudar a entender tudo sobre esse modelo.
Para fazer o SVM funcionar, nós precisamos calcular o kernel de uma matriz conhecida como K, que consiste em um produto escalar entre uma função que tem como parâmetro um xi e um xj. Então, reduzindo muitas etapas do processo, podemos entender que será uma função que dependerá da multiplicação de dois valores numéricos. Até aí temos uma complexidade O(n²). Considerando que isso será feito para cada feature, essa complexidade fica como sendo O(n² * p).
Porém, como no caso anterior, precisaremos em uma etapa desse processo inverter uma matriz, o que nos deixa com uma complexidade O(n * p² + p³).
OBS: criar vetores suporte é algo que pode ser feito de diversas formas, o que pode fazer com que essa eficiência seja alterada. O método escolhido aqui foi apenas o mais didático, porém existem métodos bem mais eficientes que exigem mais álgebra.
KNN
Vamos dar uma olhada nesse post antes de começar a análise.
Esse é o método que, de longe, mais oferece abertura para diferentes tipos de eficiência temporal. Isso porque o método de funcionamento desse algoritmo funciona comparando cada elemento com uma quantidade x de elementos próximos.
Dessa forma, do mesmo jeito que você pode comparar um ponto apenas com os seus dois mais próximos, você pode comparar com os seus 50 mais próximos. Nesse caso, tudo depende de como o programador decide organizar os seus dados (lembrando que existem funções para achar o número de vizinhos ideal, mas se prepare porque pode demorar um pouco para rodar).
Eficiência nesse caso não é tudo. Esse é um modelo muito sensível ao parâmetro de vizinhos, então cabe a quem está programando conhecer bem seus dados e decidir se vale a pena ou não sacrificar um pouco de tempo para ter um modelo melhor ou deixar o trabalho com uma acurácia não tão boa, mas executável em um espaço de tempo razoável (o que pode nem sempre acontecer).
Naive Bayes
Por fim, esse é o último post importante para ser lido antes da nossa análise.
Agora vamos para a estrelinha de eficiência do mundo do Machine Learning. Naive Bayes, o modelo mais rápido e mais fácil de ser entendido, uma vez que ele só precisa de noções básicas de estatística.
Basicamente, tudo que você tem que fazer é calcular a probabilidade de cada dado ser de uma determinada classe. Ou seja, teremos uma complexidade O(n) quando se trata da quantidade de dados, uma vez que eles não serão multiplicados nem nada do tipo, mas sim analisados individualmente. Como deveremos fazer isso para cada feature, basta multiplicar a complexidade pelo número de features. Disso, tiramos que a complexidade final do algoritmo é de O(n * p).
Conclusão
Eu sei, eu sei, essa foi uma longa jornada. Mas olha só o tanto de coisa que deu para aprender nesse post! Agora se você quiser melhorar o tempo para rodar seu modelo, basta olhar essas eficiências e perceber onde seria mais adequado fazer algumas mudanças!
Espero que tenham gostado, até a próxima!
Para mais informações, acompanhe o grupo Turing no Facebook, Linkedin, Instagram e nossos posts do Medium :).
