Introdução (não-extensiva) a Online Machine Learning

Saulo Martiello Mastelini
26 min readSep 18, 2021

--

Obtido de: https://toppng.com/free-image/a-running-robot-robot-ru-PNG-free-PNG-Images_172989

Contato: mastelini@usp.br

Outras redes:

Instituto de Ciências Matemáticas e de Computação, Universidade de São Paulo, São Carlos, Brasil
Copyright © 2021

Quem sou eu:

Eu sou um candidato a Ph.D. na Universidade de São Paulo e um dos criadores e mantenedores do projeto River, que utilizaremos nesse post. A minha pesquisa é voltada para Aprendizado de Máquina Online.

Online Learning, Data Stream learning/mining, incremental learning (e por aí vai) são nomes que são dados à área de pesquisa onde os modelos de aprendizado são atualizados a todo momento, devem ser robustos à mudanças nas características dos dados e também operar com restrições de tempo e memória. Em geral, os modelos devem processar cada nova instância apenas uma vez e, em seguida, descartá-la.

Disclaimer

Como o título já diz, essa não é, de forma alguma, uma introdução extensiva ao tema. É apenas a minha humilde tentativa de dar um panorama geral de décadas de pesquisa em uma área que está em constante expansão e inovação. O meu enfoque de pesquisa é referente a uma pequena porção do que cobriremos nesse post.

Esse material surgiu a partir de uma tutoria prática que ministrei aos alunos da turma de 2021 do MBA em Ciência de Dados do Instituto de Ciências Matemáticas e de Computação da USP. Há dois anos eu integro a equipe de tutores que auxiliam o corpo docente na realização do curso.

Feliz ou infelizmente, todo processo de aprendizado leva tempo. Assim, não será possível aprofundar em toda uma área de pesquisa de décadas em apenas uma postagem. Mas muita calma! Toda caminhada deve partir de algum ponto :D

À medida que vamos prosseguindo com os exemplos, eu vou adicionando as importações necessárias dos pacotes Python. A ideia é irmos com calma e não acarretar uma sobrecarga cognitiva logo de cara. Vamos lá!

Ponto de partida para aprofundamento

Para quem quiser se aprofundar mais nos assuntos que vamos conversar, sugiro os seguintes recursos:

  • Livro do MOA: um livro de acesso aberto que abrange vários tópicos ligados a stream learning.
  • Documentação do River: conta com vários exemplos e tutoriais, além de referenciais práticos e teóricos! Está sempre sendo expandida, corrigida e atualizada.

Quem tiver alguma dúvida específica que a documentação não possa suprir pode sempre abrir uma “Discussion” no Github. É só ir no repositório do Github do River e clicar na aba de discussões. Alguém da equipe de desenvolvimento ou da comunidade de usuários do River com grande certeza estará disposto a ajudar!

Sobre o River

O River é um projeto open source para online learning e stream mining. Ele surgiu a partir da fusão de duas ferramentas (também open-source):

  • creme
  • scikit-multiflow

Ambos os pacotes Python abordavam o mesmo tema, mas com enfoques específicos. Após um longo tempo de planejamento e conversas, os mantenedores e times de desenvolvimento dos dois pacotes uniram forças e lançaram o River. O novo pacote é o produto dos anos de lições aprendidas no desenvolvimento das ferramentas predecessoras.

O River reune o que havia de melhor creme e scikit-multiflow (que foram descontinuados) e supera pontos fracos que existiam nos projetos anteriores. A nova ferramenta é voltada tanto para o uso no mercado quanto na academia.

O River conta com muitos contribuidores, mas a maioria do time de desenvolvimento está distribuído entre a França, Nova Zelândia e Brasil.

O artigo da ferramenta no JMLR pode ser acessado aqui.

O site do River é o: https://riverml.xyz

Existe muita demanda e nem tanto tempo 😅. Se quiserem checar os planos para o futuro, visitem o nosso Roadmap. Contribuições são bem vindas! O River é um projeto Open Source construído pela comunidade. Mesmo que alguém possa não ter conhecimento técnico dos algoritmos, sempre é possível ajudar! Correções e expansões na documentação, por exemplo, são formas de ajudar! Muitas vezes apontar erros ou bugs (através de issues) já é de grande ajuda! 😁

Sumário

  1. Online learning? Why?
  2. Batch vs. Online
  3. Estruturas necessárias: exemplo com Mean, Var e Quantile
  4. Por que usar dicionários?
  5. Como avaliar um modelo?
  6. Concept drift
  7. Exemplos de algoritmos: classificação, regressão, clustering e anomaly detection
  8. Expert module
  9. Pipelines e pré-processamento
  10. Exemplo completo
# Esses são os pacotes que estão sendo utilizados nesse notebook
# As linhas a seguir podem ser descomentadas para instalar o que for necessário

# !pip install numpy
# !pip install scikit-learn

# Ultima versão lançada
# !pip install river

# Eu estou usando a versão de desenvolvimento, que pode ser instalada com:
#!pip install git+https://github.com/online-ml/river --upgrade

1. Online Learning? Why?

Por que alguém deveria se preocupar em atualizar modelos a todo tempo? Não é só treinar e sair usando?

R: sim! Em grande parte dos casos isso é verdade.

Mas imagine que:

  • A quantidade de dados produzidas é enorme
  • Não é possível armazenar tudo
  • Existe limitação no poder computacional para treinamento dos modelos (processador, memória, bateria, etc.)
  • Os dados são não-estacionários e/ou evoluem com o tempo.

Nesses casos, posso usar aprendizado de máquina tradicional? R: sim!!

É possível usar aprendizado de máquina tradicional se:

  • Os dados são estacionários (uma amostra representativa dos dados é suficiente)

ou

  • A velocidade de produção dos dados não é tão alta (batch-incremental e os recursos computacionais são suficientes)

1.1 Batch-incremental

Um modelo tradicional de aprendizado de máquina é re-treinado de tempos em tempos. Para tal, uma janela para treinamento precisa ser definida.

Tipos de janelamento dos dados:

Fonte: adaptado de Carnein, M. and Trautmann, H., 2019. Optimizing data stream representation: An extensive survey on stream clustering algorithms. Business & Information Systems Engineering, 61(3), pp.277–297.
  • Landmarks são a escolha mais comum em estratégias batch-incremental. É preciso definir o tamanho da janela de forma adequada.
  • O modelo pode ficar defasado se a janela for muito grande
  • Ou o modelo pode não capturar os padrões se a janela for muito pequena
  • Concept-drift é um problema e tanto

Atenção: batch-incremental != mini-batch. Redes neurais podem ser treinadas de forma incremental ou progressiva. No entanto, questões como “esquecimento catastrófico” são problemáticas. Esse e outros tipos de desafios são tratados na área de pesquisa chamada continual learning.

1.2 Importante lembrar

Data streams não são, necessariamente, séries temporais! 🤯

Mas qual é a diferença, então?

Basicamente, em streams não necessariamente temos dependências temporais explícitas como em séries temporais. Por exemplo: rede de sensores.

Os dados chegam temporalmente organizados, mas cada sensor tem uma taxa de transmissão específica, ou um delay específico. Alguns sensores pode falhar… outros serem adicionados. E assim por diante.

A ordem de chegada não importa… tanto, mas importa. 😜

2. Batch vs. Online

Uma boa introdução acerca da “migração” de batch para online está disponível no site do River. Aqui eu só quero dar uma visão bem geral das diferenças. Entraremos em mais detalhes posteriormente nas minúcias de avaliação de modelos em Online Learning.

Uma possível validação de um modelo tradicional de aprendizado de máquina poderia ter essa “cara”:

E a saída:

Acurácia média: 0.9045751633986928

Reparem que todo o conjunto de dados está disponível e carregado em memória. O algoritmo de árvore de decisão pode percorrer os dados de treino quantas vezes forem necessárias. Os dados de teste (validação, no nosso caso) nunca são utilizados para treino.

No fim das contas, usaríamos o conjunto completo para treinar um modelo final (supondo que já encontramos um conjunto adequado de hiper-parâmetros). Uma vez treinado, esse modelo seria utilizado para fazer predições para novas amostras (de vinhos, nesse caso).

A saída é:

Acurácia: 0.9269662921348315

Aqui, estamos percorrendo cada exemplo do conjunto de dados de forma sequencial. Os exemplos poderiam ser carregados diretamente do disco, de algum webservice, ou de onde sua imaginação te levar, sem a necessidade de salvar em memória nada.

Eis um exemplo dos dados que estamos processando, as variáveis x e y :

({'alcohol': 14.13,
'malic_acid': 4.1,
'ash': 2.74,
'alcalinity_of_ash': 24.5,
'magnesium': 96.0,
'total_phenols': 2.05,
'flavanoids': 0.76,
'nonflavanoid_phenols': 0.56,
'proanthocyanins': 1.35,
'color_intensity': 9.2,
'hue': 0.61,
'od280/od315_of_diluted_wines': 1.6,
'proline': 560.0},
2)

Cada amostra é primeiramente utilizada para teste e depois passada para o modelo. Tudo é atualizado uma amostra por vez. Notem que não podemos comparar diretamente os desempenhos obtidos porque a estratégia de avaliação foi diferente nos dois casos.

Poderíamos ainda (pseudo) embaralhar os dados antes de passar para o modelo, se temos plena confiança que os dados são estacionários.

3. Estruturas necessárias: exemplo

Dado esse choque inicial, vamos prosseguir com calma e primeiramente pensar em alguns aspectos importantes antes de vermos os algoritmos de aprendizado de máquina online.

3.1. Um exemplo, para aquecimento cerebral

Vamos supor que queremos calcular estatísticas para dados que chegam a todo momento:

  • Média
  • Variância

Hora de simular:

Vamos monitorar o desvio padrão à medida que novos dados chegam. Primeiramente, uma abordagem tradicional:

CPU times: user 1min 31s, sys: 95.3 ms, total: 1min 31s
Wall time: 1min 31s

Por padrão, o numpy calcula o desvio padrão populacional! Para usar a versão amostral precisamos passar ddof=1 como parâmetro.

CPU times: user 111 ms, sys: 54 µs, total: 111 ms
Wall time: 111 ms

Será que dá alguma diferença? E será que funciona?

(4.301100448023121e-10, 8.602200896046241e-15)

Ok… parece convincente. Mas e se o cenário fosse diferente? Se ao invés de calcularmos o desvio padrão e irmos aumentando a quantidade de dados, quisessemos descobrir um percentil das últimas N amostras?

Nesse exemplo serão as últimas 10 mil amostras;

CPU times: user 53.9 s, sys: 3.1 ms, total: 53.9 s
Wall time: 54 s

Podemos fazer um pouco melhor que isso.

CPU times: user 5.22 s, sys: 0 ns, total: 5.22 s
Wall time: 5.22 s

Como estarão os erros?

0

Espero tê-los convencido! O módulo stats do River tem várias funções úteis para sumarização de dados de forma incremental. Vale a pena checar! 🧐

A razão pela qual eu quis mostrar tudo isso é porque vários desses algoritmos são os “tijolos” que compõem os algoritmos de aprendizado de máquina. Deixo aqui, de forma lúdica, uma receita breve para online learning:

  • A junção de métricas estatísticas incrementais
  • Algumas grandezas probabilísticas
  • Algumas teorias de aprendizado de máquina que são genéricas e não limitadas ao cenário in-batch
  • Gradiente descendente
  • otras cositas

Com isso tudo é possível formar boa parte dos algoritmos de aprendizado incremental. Mas isso é extremamente genérico de se dizer, não é? Bom, no fim das contas, o aprendizado de máquina tradicional também “se resume” a algumas coisas pontuais, mas que são extremamente abrangentes por si só.

Que tal entendermos um pouco de como os exemplos anteriores funcionam e por que eles funcionam?

3.2. Uma (extremamente) breve reflexão sobre complexidade dos algoritmos

Quanto custa para calcular a variância (no caso, desvio padrão) e o percentil nos exemplos anteriores?

Modo batch

  • Variância:
Fórmula tradicional da variância

Média é calculada com o custo O(n) → todos os elementos devem ser somados e divididos pelo total de observações

  • Com a média em mãos, precisamos calcular o desvio de cada elemento para a média e somar tais desvios ao quadrado: O(n)
  • No fim das contas, o custo final é O(n) (na notação assintótica), mas tivemos que percorrer todos os dados duas vezes (e, consequentemente, armazená-los).
  • Esse algoritmo também apresenta problemas de estabilidade, quando o número de observações é muito grande. Pode gerar erros numéricos de aproximação.
  • Percentil:

Um percentil pode ser calculado da seguinte forma:

  • Pegue um exemplo novo e remova o mais antigo
  • Ordene os dados: algo em torno de O(n log n) (n é o tamanho do buffer)
  • Encontre a posição correta, interpole e retorne

Se esse processo é repetido várias e várias vezes… dá para ver onde isso vai dar.

Modo incremental

Variância (algoritmo de Welford):

Precisamos de algumas variáveis:

Número de observações
Média amostral
Estatística de segunda ordem que gerará a variância

As atualizações das estatísticas se dão na seguinte forma:

Atualização do estimador de média
Atualização da estatística de segunda ordem
Atualização da estatística de segunda ordem

Ambas as estatísticas apresentadas anteriormente são inicializadas com zero.

Para obter a variância amostral basta usar:

Cálculo da variância amostral
Para todo n > 1

De brinde, obtemos um preditor robusto para a média 🤓

  • Percentil:

O segredo aqui está na forma de tratar os dados

  • Mantemos dois buffers
  • Um com os dados na ordem em que chegam
  • Outro com os dados ordenados: o custo de inserção de um novo ponto em um vetor já ordenado é O(log n)
  • A remoção de um valor no buffer ordenado é O(n). No buffer não-ordenado é O(1)
  • O cálculo do percentil usa o buffer ordenado

No fim das contas, sempre buscamos que cada atualização em uma métrica ou modelo de aprendizado tenha um custo constante (O(1)). Se isso não for possível, então um custo sub-linear é o objetivo!

Antes de prosseguirmos, vou mostrar mais uma aplicação legal de métricas incrementais, com requintes de processamento distribuído.

Situação hipotética:

E se estivéssemos calculando estatísticas de alguma coisa, mas a coleta era feita de forma separada? Por exemplo, estamos calculando a variância de alguma coisa a nível estadual, mas a coleta é feita por município?

(Eu sou paranaense)

(39496.429786146546, 249442.43568603016)

E se quisermos calcular a variância (ou média) total de todos os municípios?

615000

Variância:

np.var(dados_parana)268085.14104958007

Média:

np.mean(dados_parana)2475.927394402956

Nós já sabemos como fazer esse mesmo processo de forma incremental:

(39496.429786146546, 249442.4356860276)

Posso usar stats.Mean para obter a média. Mas se lembrarmos bem, o algoritmo de Welford tem um preditor de média "lá no meio", não tem?

Voilà!

var_ca.mean.get(), np.mean(dados_ca)(1500.9742744265895, 1500.9742744265982)

Agora vem a parte mais legal 🙃

Como obtemos as estatísticas para o estado inteiro?

(268085.1410495726, 268085.14104958007)

Comparando a média também obtemos resultados muito próximos: var_parana.mean.get(), np.mean(dados_parana)

(2475.927394402848, 2475.927394402956)

E se a bela e formosa cidade de Cândido de Abreu tivesse sido esquecida? Os dados tivessem sido perdidos, sei lá…

(quando eu era criança, minha cidade natal nem aparecia nos mapas impressos do Paraná, vai saber…)

(39496.429786146546, 39496.42978614286)

O mesmo vale para a média: var_ca.mean.get(), var_ca_backup.mean.get()

(1500.9742744265895, 1500.9742744265875)

No fim das contas, sempre existe um trade-off entre memória, tempo de processamento (e a quantidade de “passadas” nos dados) e a precisão dos resultados obtidos. Muitos dos algoritmos de online learning incluem um parâmetro (δ) que indica a porcentagem de “certeza” que você deseja ter nos seus resultados. Em geral, quanto mais certeza, mais tempo leva para tomar as decisões.

4. Por que usar dicionários (ou, por que usar uma representação esparsa)?

Um as primeiras coisas que podem chamar a atenção no River é o tipo de dados que é utilizado: dicionários python.

Sobre dicionários:

  • Chave x valor: chaves são únicas
  • Valores acessados via chave, ao invés de índice
  • Dicionários são estruturas naturalmente esparsas
  • Diferentemente de arrays, vetores, matrizes (e etc.) não possuem uma ordenação explícita
  • Podem ser extendidos
  • Podem ter variáveis de tipo misto

Exemplos:

O resultado:

{'batata': 3,
'carro': 2,
'data': datetime.datetime(2021, 9, 17, 12, 45, 6, 653555),
'sim_ou_não': 'sim'}

Posso adicionar um novo elemento a x : x["mais um"] = True

{'batata': 3,
'carro': 2,
'data': datetime.datetime(2021, 9, 17, 12, 45, 6, 653555),
'sim_ou_não': 'sim',
'mais um': True}

Ou deletar um elemento: del x["data"]

{'batata': 3, 'carro': 2, 'sim_ou_não': 'sim', 'mais um': True}

Esse tipo de estrutura é muito parecida com o popular formato JSON (para transferência de dados)! Fica aí a dica para aplicações reais :D

Que tal compararmos com a estratégia mais usual? Aqui estou mostrando a primeira linha dos dados:

(array([1.423e+01, 1.710e+00, 2.430e+00, 1.560e+01, 1.270e+02, 2.800e+00, 3.060e+00, 2.800e-01, 2.290e+00, 5.640e+00, 1.040e+00, 3.920e+00, 1.065e+03]),
['alcohol',
'malic_acid',
'ash',
'alcalinity_of_ash',
'magnesium',
'total_phenols',
'flavanoids',
'nonflavanoid_phenols',
'proanthocyanins',
'color_intensity',
'hue',
'od280/od315_of_diluted_wines',
'proline'])

E o target: y[0], data.target_names

(0, array(['class_0', 'class_1', 'class_2'], dtype='<U7'))

Primeiramente, vamos colocar o sklearn à prova.

((176, 13), (2, 13))
array([2, 2])

Até aqui, tudo bem. Mas, e se uma feature estivesse faltando?

operands could not be broadcast together with shapes (2,12) (13,)

Em Online Learning nós não deveríamos ficar nos preocupando com “coisa pouca” assim. Brincadeiras a parte, em um cenário de aprendizado online, sensores podem falhar, novos dados podem surgir, entre muitas outras coisas que podem alterar os dados de entrada. Precisamos de uma representação e modelos robustos quanto a isso!

Com o River, a vasta maioria dos modelos está pronta para lidar com esse tipo de problema! 🎉

Exemplo onde cada feature em uma nova observação tem 20% de chance de ser removida
x, y({'alcohol': 13.17,
'malic_acid': 2.59,
'ash': 2.37,
'alcalinity_of_ash': 20.0,
'magnesium': 120.0,
'total_phenols': 1.65,
'flavanoids': 0.68,
'nonflavanoid_phenols': 0.53,
'proanthocyanins': 1.46,
'color_intensity': 9.3,
'hue': 0.6,
'od280/od315_of_diluted_wines': 1.62,
'proline': 840.0},
2)

Se eu usar o modelo treinado para prever a próxima amostra: gnb.predict_proba_one(x)

{0: 2.2901730526821133e-23, 1: 4.523692607178262e-14, 2: 0.9999999999999538}

Até aqui, tudo bem. Vamos bagunçar a próxima amostra:

x, y = next(dataset)

Vou tirar uma cópia do x e remover umas coisas:

{'alcohol': 14.13,
'ash': 2.74,
'alcalinity_of_ash': 24.5,
'magnesium': 96.0,
'total_phenols': 2.05,
'nonflavanoid_phenols': 0.56,
'proanthocyanins': 1.35,
'color_intensity': 9.2,
'od280/od315_of_diluted_wines': 1.6,
'proline': 560.0}

Será que o nosso modelo dá conta do recado?

gnb.predict_proba_one(x_copy), y

A saída:

({0: 7.394823717897321e-13, 1: 8.511456030879924e-13, 2: 0.9999999999984084},
2)

E se ao invés de diminuir o número de features aumentasse?

x["primeira extra"] = 7.89
x["segunda extra"] = 2

Vou atualizar o modelo com a amostra contendo novas features:

1

Cada tipo de modelo implementa estratégias diferentes para lidar com atributos emergentes ou faltantes!

O que será que está acontecendo? Vamos ver a distribuição das classes: np.unique(data.target, return_counts=True)

(array([0, 1, 2]), array([59, 71, 48]))

No nosso exemplo, “1” era a classe majoritária. Essa foi a escolha feita pelo GaussianNB, já que há pouca informação acerca dos dois atributos extras que adicionamos. Mas eles já fazem parte do modelo e serão atualizados caso novas observações cheguem!

5. Como avaliar um modelo?

Já vimos em exemplos passados que os dados foram primeiramente utilizados para teste e depois para treino. Nada de Cross-validation, Leave-one-out, Holdout e coisas do tipo.

Esse tipo de avaliação se aproxima mais de um cenário de produção real. Normalmente, obtemos um dado sem a sua label (no caso supervisionado, obviamente) e precisamos fazer predições. Só depois de um tempo a verdadeira label daquele exemplo será conhecida.

Nos exemplos até aqui, nós assumimos que logo após o uso do modelo para a predição de uma amostra, a label é revelada. No entanto, um cenário ainda mais realístico é aquele onde existe um delay entre a predição e a chegada da label. Em alguns casos, certos exemplos podem nunca ter sua label obtida!

Esse tipo de estratégia de avaliação é chamada de “validação progressiva” (progressive validation) ou “prequential”.

Deixo esse ótimo post do Max Halford, onde esse tema é discutido em detalhes.

No River, podemos utilizar a função progressive_val_score disponível no módulo evaluate para realizar validações progressivas! Daqui para frente, essa função será utilizada.

Obviamente, podemos também escrever alguns for e customizar a estratégia de avaliação. Fica de acordo com o critério e a necessidade de cada um!

A saída que obtive em meu laptop foi essa:

Saída do exemplo com label delay
Exemplo com label delay

6. Concept drift

Um dos aspectos centrais em online learning reside no fato que esperamos que as distribuições dos dados podem ser não-estacionárias. Mas o que isso significa?

Primeiro, vamos pensar num exemplo de distribução estacionária:

Sabe quando ouvimos falar que a GRANDE-EMPRESA-HYPADA lançou uma rede neural MASTER-BLASTER-ULTRA-POWER-3, com 3 “zilhões” de parâmetros, treinada por 5meses com a energia suficiente para alimentar cidades? E sabe quando ouvimos falar que a base de dados utilizada foi gigante?

Pois bem, os dados não mudam. As regras linguísticas no textos de entrada (supondo um modelo de linguagem natural) ou a semântica visual das imagens (supondo um modelo de visão computacional), ou qualquer outro exemplo, tudo isso é estático. Um cachorro continuará sendo um cachorro (independente do ângulo — no entanto, dependendo da forma de captação das imagens isso pode ser um problema). Uma palavra tem um conjunto estático de sinônimos e significados. E por aí vai!

A regra do jogo não-muda. Mas e se mudasse?

Essa mudança, ou deriva de conceito (concept drift) pode ocorrer em problemas do mundo real. Exemplo:

  • padrões de consumo (papel higiênico e alcool em gel no início da pandemia)
  • questões relacionadas a clima: energia sustentável
  • trânsito, rotas

Umas das áreas de pesquisa (sim, uma área completa de pesquisa) em online learning busca criar detectores para essas situações, bem como algoritmos de aprendizado de máquina que sejam capazes de se adaptar mudanças de conceitos.

Estou longe de ser um especialista nesse tópico, mas vou dar um panorama de como as coisas acontecem.

Suponha que temos um problema de classificação e estamos monitorando os erros do nosso classificador. Nós assinalamos com 0 quando o modelo acerta (erro zero) e 1 quando o modelo erra.

0
1
0
1
0
0
1
0
0
0

Podemos passar esses valores para um detector de drifts:

E, como esperado, nenhum drift é detectado.

E se a distribuição mudar?

Drift detectado em 575

O ADWIN é um dos detectores mais utilizados, mas existem várias alternativas, assim como vários tipos de deriva de conceito. Além disso, normalmente, os detectores são utilizados como componentes na criação de modelos preditivos. A forma na qual eles são utilizados difere de modelo para modelo. Uma característica é comum entre a maioria dos detectores de drift: eles são univariados.

7. Exemplos de algoritmos

Existem muitos algoritmos de aprendizado online. Uns são bem diferentes, outros são modificações de outros algoritmos. Assim como em aprendizado de máquina tradicional, existem opções para todo gosto.

As listas a seguir não são extensivas de modo algum. São apenas o que eu fui lembrando, tenho certa familiaridade, e o que eu vejo de popular por aí (obviamente com o meu viés pessoal). Uma boa pedida é consultar a documentação do River para ver o que há de disponível por lá!

Mostrarei de forma breve seu uso e, quando aplicável, quais dos seus hiper-parâmetros são os mais “sensíveis”, na minha experiência.

7.1. Classificação

Abordaremos uma lista de algoritmos para classificação. Se um algoritmo foi projetado apenas para classificação binária e o problema em questão é multiclasses, as ferramentas do módulo multiclass podem ser utilizadas como um wrapper:

  • OneVsOneClassifier
  • OneVsRestClassifier
  • OutputCodeClassifier

7.1.1. Logistic Regression

Versão incremental de Logistic Regression (para classificação binária). Pode ser treinada com vários otimizadores. Por padrão usa o Stochastic Gradient Descent.

Não tenho muitas dicas específicas acerca dessa família. Mas todo o conhecimento ligado a redes neurais tende a ser útil aqui.

É possível ajustar:

  • O otimizador
  • O algoritmo de inicialização
  • Regularização L2
  • A função de perda
  • entre outros

Exemplo:

Saída do exemplo com Logistic Regression
Saída do processamento com LogisticRegression

Uma variante de Logistic Regression é SoftMax Regression (voltada para problemas multi-classe e mais robusta a outliers):

Exemplo com SoftMax Regression
Exemplo com SoftMax Regression

7.1.2. Hoeffding Tree (e variantes)

Estão entre os modelos mais populares em stream mining. Historicamente um dos algoritmos mais usados, senão o mais usado. Minha pesquisa de doutorado contempla árvores de decisão e ensembles online. Existem vários classificadores no River baseados em árvores de decisão. Grande parte deles pertencem a família das Hoeffding Trees.

Hoeffding Trees (HT) têm esse nome porque elas se baseiam numa grandeza estatística chamada Hoeffding bound para decidir quando fazer uma divisão. Essa medida traz indícios que um split feito de forma incremental seria o mesmo que seria feito em um algoritmo de árvore tradicional (desde que observações suficientes sejam feitas).

Existem três variantes principais das HTs:

  • Hoeffding Tree: versão padrão
  • Hoeffding Adaptive Tree: adiciona detectores de deriva de conceito em cada nó de decisão. Se uma mudança é detectada, uma nova sub-árvore é treinada (no background) e eventualmente virá a substituir o ramo afetado.
  • Extremely Fast Decision Tree: Faz splits mais rapidamente, mas periodicamente revisita as decisões feitas e vai reconstruindo as árvores.

Principais parâmetros para ajuste comum a todas as HTs:

  • grace_period: intervalos entre tentativas de splits.
  • split_confidence: o quão "certas" sobre uma decisão as árvores devem estar, de forma a fazer um split. A "certeza" é dada por 1 - split_confidence.
  • tie_threshold: threshold abaixo do qual um split será feito, mesmo se não houver plena certeza que o melhor candidato para split é realmente a melhor escolha.
  • max_depth: profundeza máxima que uma árvore pode alcançar.

Eu escrevi um tutorial sobre HTs que aprofunda mais o que é possível se fazer com esse tipo de preditor.

Exemplo:

Exemplo com Hoeffding Tree
Exemplo com Hoeffding Tree

Podemos visualizar a estrutura da árvore.

model.draw()
Representação da árvore de decisão
Representação da árvore de decisão

Também é possível inspecionar como uma decisão é tomada:

4 ≤ 0.44069887341009073
Class 2:
P(0) = 0.1
P(1) = 0.4
P(2) = 0.5

7.1.3. Naive Bayes

O Naive Bayes é inerentemente incremental. Assim, é possível atualizar as contagens ou estimativas das distribuições de forma incremental.

Modelos disponíveis:

  • BernoulliNB, ComplementNB e MultinomialNB: voltados para os casos onde os dados são contagens (bag-of-words), ou a saída do TF-IDF.
  • GaussianNB: discretiza as features numéricas utilizando uma distribuição gaussiana por classe.

Exemplo:

Exemplo com Gaussian Naive Bayes
Exemplo com Gaussian Naive Bayes

6.1.4. Adaptive Random Forest

A adaptive random forest (ARF) é uma versão incremental do algoritmo Random Forest e combinas os seguintes ingredientes:

  • Hoeffding Trees com pitadas de aleatoriedade, como base learners (ingrediente principal)
  • Detectores de deriva de conceito por árvore
  • árvores “reserva” são treinadas em background caso drifts são detectados
  • Bagging na versão online

Além de todos os parâmetros das HTs, alguns parâmetros notáveis da ARF são:

  • warning_detector e drift_detector: detectores de warning e drift
  • n_models: o número de árvores
  • max_features: o número de features que será considerado por árvore durante splits

Exemplo:

Resultados da Adaptive Random Forest
Resultados da Adaptive Random Forest

7.1.5. Streaming Random Patches

Na ARF e random forest em geral, cada vez que um nó da árvore é dividido, um novo sub-conjunto das features é selecionado. Apenas esse subconjunto é considerado nas decisões. Esse processo pode ser referido como amostragem local de features. A (A)RF também faz amostragem de instâncias com reposição (bagging).

O Streaming Random Patches (SRP) também faz amostragem de instâncias via bagging. No entanto, a amostragem de features é global: feita apenas uma vez por modelo no ensemble. Além disso, o SRP não limita os membros do ensemble à árvores de decisão: qualquer classificador pode ser utilizado 😁

A detecção e reação a derivas de conceito (concept drift) é igual ao mecanismo adotado na ARF.

Quanto aos hiperparâmetros mais notáveis:

  • model: o classificador base
  • n_models: o número de classificadores no ensemble
  • warning_detector e drift_detector: o mesmo que na ARF

Exemplo:

Resultado do Streaming Random Patches
Resultado do Streaming Random Patches

7.2. Regressão

Para regressão, vou adotar o mesmo dataset em todos os casos, para termos uma ideia das capacidades dos algoritmos.

({0: 0.5811521325045647,
1: 0.1947544955341367,
2: 0.9652511070611112,
3: 0.9239764016767943,
4: 0.46713867819697397,
5: 0.6634706445300605,
6: 0.21452296973796803,
7: 0.22169624952624067,
8: 0.28852243338125616,
9: 0.6924227459953175},
20.0094162975429)

7.2.1. Linear Regression

A regressão linear permite a exploração de vários parâmetros:

  • otimizadores
  • funções de perda
  • regularização
  • estratégias para atualização do fator de aprendizado
  • entre outras coisas

Exemplo:

Resultados para Linear Regression

Que tal tentar outros parâmetros?

Resultados para Linear Regression com variação de parâmetros
Resultados para Linear Regression com variação de parâmetros

7.2.2. Hoeffding Tree

(minha pesquisa se situa aqui)

Temos também versões da HT para regressão. Os principais modelos para regressão de único alvo são:

  • HoeffdingTreeRegressor: versão padrão do regressor.
  • HoeffdingAdaptiveTreeRegressor: extende o anterior de forma similar à versão de classificação.

Além dos parâmetros já apresentados na árvore de classificação, outros parâmetros importantes são:

  • leaf_prediction: seleciona a estratégia de predição -- regression ou model tree
  • leaf_model: modelo preditivo utilizado nas folhas, no caso das model trees
  • splitter: algoritmo utilizado para lidar com splits em atributos numéricos

Exemplo:

Resultados do Hoeffding Tree Regressor
Resultados do Hoeffding Tree Regressor

Querem conhecer um pouco da minha pesquisa?

Resultados do Hoeffding Tree Regressor utilizando a minha proposta, QO, para lidar com atributos numéricos

Minha pesquisa:

Diminuir os custos computacionais de regressores baseados em árvores e regras de decisão, bem como ensembles destes preditores.

7.2.3. AMRules

Adaptive Model Rules.

(minha pesquisa se situa aqui também)

Cria regras de decisão baseadas na Hoeffding bound, assim como as árvores. É capaz de fazer deteção de anomalias! De fato, o AMRule “pula” amostras anômalas durante o treinamento.

Tem alguns ajustes muito parecidos com as árvores de decisão:

  • n_min: equivalente ao grace_period
  • delta: equivalente ao split_confidence
  • tau: equivalente tie_threshold
  • pred_type: equivalente leaf_prediction
  • pred_model: equivalente leaf_model
  • splitter

Em adição, outros parâmetros importantes:

  • m_min: número de instâncias que cada regra deve observar antes de começar a detectar anomalias.
  • drift_detector: o detector de concept drift utilizado pelas regras de decisão
  • anomaly_threshold: valor de corte para considerar uma amostra anômala. Instâncias serão consideradas anômalas se o score delas for menor que esse limiar.
  • ordered_rule_set: define se apenas a primeira regra que dá "match" em uma instância será utilizada, ou todas as regras.

Exemplo:

Resultados do AMRules
Resultados do AMRules

Também podemos inspecionar o modelo utilizando debug_one: print(model.debug_one(x)) (notem que os identificadores das features nesse dataset são números inteiros a partir de zero).

(estou selecionando uma nova amostra com x, y = next(get_friedman()))

0. Input
--------
0: 0.58115 (float)
1: 0.19475 (float)
2: 0.96525 (float)
3: 0.92398 (float)
4: 0.46714 (float)
5: 0.66347 (float)
6: 0.21452 (float)
7: 0.22170 (float)
8: 0.28852 (float)
9: 0.69242 (float)

1. StandardScaler
-----------------
0: 0.28929 (float)
1: -1.07485 (float)
2: 1.58610 (float)
3: 1.47168 (float)
4: -0.11737 (float)
5: 0.56379 (float)
6: -0.99330 (float)
7: -0.96557 (float)
8: -0.73064 (float)
9: 0.67069 (float)

2. AMRules
----------
Rule 10: 1 ≤ -0.5 and 3 > 0.2
Prediction: 18.18983170887722
Rule 11: 3 > 0.1
Prediction: 17.247442918348362
Final prediction: 17.718637313612792


Prediction: 17.71864

O valor de y que era esperado: print(f"Valor esperado: {y}")

Valor esperado: 20.0094162975429

Vou utilizar as capacidades de detecção de anomalias do AMRules:

(2.1127833360155464, 0.5901638190519669, 0.16666666666666666)

O primeiro valor é o score médio de anomalia, seguido pelo desvio padrão dos scores, e o suporte (porcentagem das regras de decisão que participaram na definição do score de anomalia). Em outras palavras, esse exemplo não é anômalo (como era de se esperar, já que o dataset é sintético e não conta com anomalias).

7.2.4. Adaptive Random Forest

(minha pesquisa também está aqui!)

Utiliza uma versão da HoeffdingTreeRegressor como preditor base. Tem todos os hiper-parâmetros da árvore de decisão e os parâmetros que já foram apresentados na ARF para classificação.

Além disso, adiciona um parâmetro que tende a impactar bastante os resultados:

  • agregation_method: como as predições individuais de cada árvore serão combinadas.

Exemplo:

Resultados do Adaptive Random Forest Regressor
Resultados do Adaptive Random Forest Regressor

7.7.5. Streaming Random Patches

(minha pesquisa também está aqui)

É a versão para regressão do SRP apresentado anteriormente. Compartilha os mesmos parâmetros apresentados para o algoritmo de classificação.

Exemplo:

Resultados do Streaming Random Patches Regressor, com regressores lineares
Resultados do Streaming Random Patches Regressor, com regressores lineares

Podemos também utilizar Bagging para unir regressores.

Resultado do Bagging de Hoeffding Adaptive Tree Regressors
Resultado do Bagging de Hoeffding Adaptive Tree Regressors

7.3. Clustering

Algoritmos incrementais para clustering devem ser capazes de se adaptarem às mudanças constantes nos dados. Por exemplo, alguns clusters podem surgir, outros desaparecerem. É uma área ativa de pesquisa, com muitos algoritmos disponíveis!

Apresentarei um algoritmo particional baseado em protótipos, para ilustrar.

7.3.1. k-Means

Existem várias versões incrementais do k-Means. A versão no River adiciona um parâmetro chamado halflife que controla o nível das atualizações incrementais.

Silhouette: 0.394768

Vamos diminuir o número de clusters.

Silhouette: 0.810066

E aumentar o valor de halflife.

Silhouette: 0.833915

7.4. Anomaly detection

Até o momento o River conta com um detector de anomalias, que é a versão incremental da Isolation Forest. Estou longe de ser um especialista no assunto, mas preparei esse exemplo para detecção de fraudes em transações de cartão de crédito:

CPU times: user 48.3 s, sys: 82.9 ms, total: 48.4 sWall time: 48.6 s

Resultado do limiar estático: metric_static

BalancedAccuracy: 67.06%, Precision: 0.156504, Recall: 0.345291, F1: 0.215385

Resultado do limiar dinâmico: metric_dynamic

BalancedAccuracy: 84.10%, Precision: 0.106383, Recall: 0.695067, F1: 0.184524
Número de amostras: 100000
Número de anomalias: 223
Número de anomalias detectadas (estático): 492
Número de anomalias detectadas (dinâmico): 1457
Match detecções (estático): 0.3452914798206278
Match detecções (dinâmico): 0.695067264573991

Vamos checar como estava o limiar dinâmico no final? Ele é calculado por: var.mean.get() + 1.5 * (var.get() ** 0.5)

0.5411217746289352

Leitura extra!

Um membro do Spike escreveu um tutorial muito bom sobre detecção de anomalias usando River. Um cenário de produção real é abordado e a exploração vai muito além do meu simples exemplo. Recomendo muito a leitura!

8. Expert stuff

O módulo expert traz utilidades para seleção e combinação de modelos.

Abordarei dois exemplos:

  1. Seleção de modelos
  2. Combinação de modelos

8.1. Selecionando um modelo de forma online

Suponha que eu tenho um conjunto de hiper-parâmetros que gostaria de avaliar, mas não gostaria de rodar todos os modelos para descobrir qual é o melhor. Vamos usar a regressão linear como exemplo aqui. O algoritmo SuccessiveHalving será utilizado. Ele realiza "rodadas" de competição entre os modelos e vai descartando os menos promissores, tudo de maneira incremental.

O meu modelo base será um regressor linear (juntamente com um StandardScaler incremental):

Aqui, eu monto um grid de hiper-parâmetros para exploração.

168

Esses 168 regressores lineares competirão de forma online para descobrirmos qual configuração é a melhor.

Resultados do Successive Halving Regressor
Resultados do Successive Halving Regressor

Podemos acessar o melhor modelo encontrado: model.best_model._get_params()

{'StandardScaler': {'with_std': True},
'LinearRegression': {'optimizer': (river.optim.sgd.SGD,
{'lr': (river.optim.schedulers.Constant, {'learning_rate': 0.01})}),
'loss': (river.optim.losses.Squared, {}),
'l2': 0.1,
'intercept_init': 3.5,
'intercept_lr': (river.optim.schedulers.Constant, {'learning_rate': 0.01}),
'clip_gradient': 1000000000000.0,
'initializer': (river.optim.initializers.Zeros, {})}}

8.2. Combinação de modelos

Nós já vimos alguns ensembles, mas também é possível combinar modelos de outras formas. Aqui, utilizaremos uma combinação baseada em decaimento exponencial de erros.

Resultados do Exponentially Weighted Average Regressor
Resultados do Exponentially Weighted Average Regressor

9. Pipelines e pré-processamento

Vocês notaram que eu tenho usado muito os operadores “|” e “+” em alguns contextos?

Esses operadores são utilizados para criar pipelines. Eles são algo que chamamos de “sugar syntax”.

No River nós podemos usar operadores explícitos, assim como no sklearn.

Vamos supor que no exemplo anterior, algumas das features que seriam passadas ao nosso modelo eram categóricas. Poderíamos aplicar um encoding nesses exemplos para garantir que nosso modelo funcionaria com a regressão linear.

Representação de pipeline de processamento gerada pelo River
Representação de pipeline de processamento gerada pelo River

Que coisa linda né? Eu “escondi o ouro” e propositalmente não mostrei essa visualização anteriormente. Muito útil para debugging. Prático? Pode ficar ainda melhor!

Sugar syntax! Vou montar o mesmo pipeline sem usar explicitamente os componentes de compose.

O mesmo pipeline é obtido, mas de forma muito menos “verborrágica”
O mesmo pipeline é obtido, mas de forma muito menos “verborrágica”

Muito mais legível, na minha humilde opinião! E o melhor de tudo: basta tratar o pipeline como um modelo e utilizar learn_one/predict_one (e cia.). Todas as operações serão realizadas automaticamente.

Existem várias possibilidades com compose e Pipelines. Um bom ponto de partida: The art of using pipelines.

Algumas delas serão melhor abordadas no exemplo da próxima seção. A documentação do módulo é bem completa, vale a pena conferir!

10. Exemplo completo

Nesse exemplo iremos aplicar todos os conceitos vistos anteriormente.

Atenção:

O objetivo aqui é aplicação de conhecimento, e não lidar com o problema preditivo em si.

Provavelmente a extração de melhores features melhoraria o desempenho preditivo do regressor.

O dataset a ser utilizado é um subconjunto do Airlines. Utilizaremos dois anos do conjunto total (2007 e 2008). O dataset deve ser extraído para a mesma pasta deste notebook. Eu preparei uma versão em csv do conjunto. Ela pode ser baixada nos seguintes links: parte 1 e parte 2. Os arquivos compactados devem ser extraídos.

O dataset conta com mais de 15 milhões de amostras referentes a vôos realizados no período mencionado. O objetivo é prever o atraso de cada vôo em minutos.

Vamos começar com as importações necessárias:

Em seguida, a leitura dos dados a partir do disco. As amostras serão lidas sem que o dataset completo necessite ser carregado para a memória:

O próximo passo é definir funções para tratamento dos dados:

Essa é a “cara” dos dados em x, sem nenhum pré-processamento. Esse é o primeiro exemplo na base de dados:

{'Year': 2007,
'Month': 1,
'DayofMonth': 1,
'DayofWeek': 1,
'CRSDepTime': '10',
'CRSArrTime': '738',
'UniqueCarrier': 'NW',
'FlightNum': 336,
'ActualElapsedTime': 270.0,
'Origin': 'LAX',
'Dest': 'DTW',
'Distance': 1979.0,
'Diverted': 'no'}

Mãos à obra! Hora de montar o pipeline de pré-processamento. Ele inclui:

  • Imputting (substituímos os valores None que artificialmente foram incluídos na base pela média incremental dos valores válidos)
  • Descarte de variáveis categóricas cuja cardinalidade é muito alta (elas não são utilizadas diretamente pelo regressor final, mas são empregadas na extração de novos atributos)
  • Tratamento de dados categórios (One-hot-encoding) e numéricos (Standard Scaling)
  • Extração de features, a partir da agregação de valores passados do target de acordo com múltiplos critérios

A seguir, o pipeline de pré-processamento dos dados:

Pipeline de pré-processamento. Os gráficos são interativos quando utilizados no jupyter notebook. Cada elemento pode ser inspecionado
Pipeline de pré-processamento. Os gráficos são interativos quando utilizados no jupyter notebook. Cada elemento pode ser inspecionado

Estamos adicionando seis novos atributos que são agregações dos valores de atraso no vôo a partir de combinações de:

  • aeroporto de saída
  • aeroporto de destino
  • empresa aérea

Como os números de vôo costumam ter uma certa “semântica” dentro de uma mesma empresa aérea, eu arrisquei e os deixei serem tratados como um atributo númerico.

Vamos verificar o que o nosso pipeline de pré-processamento está fazendo:

{'Year': 0.0,
'DayofMonth': 0.0,
'FlightNum': 0.0,
'ActualElapsedTime': 0.0,
'Distance': 0.0,
'approx_time_zone_diff_min': 0.0,
'exp_dep_hour': 0.0,
'exp_dep_minute': 0.0,
'exp_arr_hour': 0.0,
'exp_arr_minute': 0.0,
'delay_ewm_0.8_by_Origin_and_Dest_and_UniqueCarrier_and_FlightNum': 0.0,
'delay_ewm_0.8_by_Origin_and_Dest_and_UniqueCarrier': 0.0,
'delay_ewm_0.8_by_Dest_and_UniqueCarrier': 0.0,
'delay_ewm_0.8_by_Origin_and_UniqueCarrier': 0.0,
'delay_ewm_0.8_by_Origin_and_Dest': 0.0,
'delay_ewm_0.8_by_DayofWeek_and_UniqueCarrier': 0.0,
'Month_January': 1,
'DayofWeek_Mon': 1,
'Diverted_no': 1}

A maioria dos valores é zero (com exceção das features categóricas após o One-hot encoding) porque apenas um exemplo foi processado pelo nosso pipeline atual. Notem também que pelo fato de não haver ainda um preditor no pipeline, a função chamada no final foi a transform_one .

Aqui eu preparo o modelo preditivo e o adiciono ao final do pipeline de pré-processamento. Utilizarei regras de decisão para fazer a regressão do valor de atraso dos voos.

Pipeline completo de processamento, incluindo tratamento dos dados, extração de atributos e regressor baseado em regras de decisão
Pipeline completo de processamento, incluindo tratamento dos dados, extração de atributos e regressor baseado em regras de decisão

Aqui, “apenas” 2 milhões de exemplos foram considerados, mas a função slice_data pode ser utilizada para escolhar a proporção a ser considerada.

A saída obtida (se preparem para um log longo):

Log de saída para o exemplo completo

Esse exemplo foi executado no meu laptop rodando Linux, com 16GB de RAM e um processador Core i7–8550U. Dois milhões de amostras foram processadas pelo nosso pipeline em menos de 20 minutos. O modelo completo, ao final do processamento, tinha menos de 20 MB em memória e obteve um erro de cerca de 20 minutos ao predizer o atraso dos vôos (o valor flutuou durante o processamento).

E esse foi o nosso exemplo de aplicação do River em um problema real de regressão online! O pipeline criado trata o pré-processamento dos dados (com conversão de tipos, imputting de dados faltantes e criação de novas features) e é robusto à deriva de conceito.

Espero que o exemplo e os conteúdos, em geral, possam ter sido úteis :) Qualquer dúvida é só me contatar!

Fiquem de olho no River, muita coisa boa vem por aí! Até a próxima!

--

--

Saulo Martiello Mastelini

I’m a PhD candidate at University of São Paulo — Brazil, researching Online Machine Learning. I’m one of the maintainers of River and sometimes also a musician.