Online semi-supervised perception: Real-time learning without explicit feedback

1. Definição do Problema

O artigo aborda o desafio da aprendizagem semi-supervisionada online em ambientes em tempo real, onde o feedback explícito (rótulos verdadeiros) é escasso ou indisponível após a configuração inicial.

• O Cenário: O sistema opera em um jogo repetitivo contra um ambiente potencialmente adversário. Em cada passo de tempo $t$, o algoritmo observa um exemplo $x_t$ e deve prever seu rótulo $\hat{y}_t$.
• A Restrição: Os rótulos verdadeiros $y_t$ são raramente observados. O algoritmo deve depender de feedback indireto, especificamente a estrutura de variedade subjacente dos dados, para se adaptar às mudanças ambientais.
• O Objetivo: Construir um algoritmo de aprendizado adaptativo que comece com um pequeno conjunto de exemplos rotulados offline (viés inicial) e atualize continuamente seu modelo usando um fluxo de dados não rotulados para manter alta precisão e revocação.

2. Metodologia

A solução proposta combina Aprendizado Semi-Supervisionado (SSL) em grafos com técnicas de Aprendizado Online. A abordagem central envolve a construção iterativa de uma representação gráfica do mundo e sua atualização incremental.

A. Solução de Função Harmônica (Fundação Offline)

O algoritmo baseia-se na solução de função harmônica para SSL em grafos (Zhu et al.).

• Construção do Grafo: Os vértices representam exemplos de dados, e os pesos das arestas ($w_{ij}$) representam similaridade (ex.: similaridade facial).
• Objetivo: Minimizar o objetivo quadrático $\ell^T L \ell$ sujeito a rótulos fixos para o conjunto rotulado $l$, onde $L$ é o Laplaciano do grafo.
• Interpretação: A solução $\ell$ corresponde a um passeio aleatório no grafo. O rótulo de um nó não rotulado é determinado pela probabilidade de um passeio aleatório iniciado nesse nó terminar em um nó rotulado de uma classe específica.
• Regularização: Para controlar a extrapolação para dados não rotulados, os autores introduzem um parâmetro de regularização $\gamma_g$. Isso é interpretado como a adição de um "sumidouro" extra ao grafo, fazendo com que o passeio aleatório termine com probabilidade $\gamma_g/(d_i + \gamma_g)$, reduzindo assim a confiança para nós distantes dos exemplos rotulados.

B. Implementação Online via Quantização

Uma implementação online ingênua (recalcular o grafo completo a cada passo) é computacionalmente inviável ($O(t^3)$). Os autores propõem uma estratégia de Quantização para manter uma representação compacta:

1. Vértices Representativos: Em vez de armazenar cada exemplo observado, o algoritmo mantém um conjunto de vértices representativos $C_t$.
2. Algoritmo de Duplicação: Novos exemplos são mesclados em representantes existentes se estiverem dentro de um raio $R$. Se o conjunto de representantes exceder um limite $n_g$, o raio $R$ é duplicado e o conjunto é reparticionado.
3. Multiplicidades: Vértices idênticos ou mesclados são rastreados por um vetor de multiplicidade $v_t$.
4. Solução Compacta: A função harmônica é computada neste grafo reduzido $\hat{W}_t$ com termos Laplacianos ajustados ($\hat{L} + \gamma_g V$), reduzindo a complexidade para $O(n_g^3)$, independente do tempo $t$.

C. Tratamento de Outliers

Para lidar com outliers (pontos de dados que não se encaixam na variedade):

• Se a confiança do rótulo computado for zero (indicando um outlier), o algoritmo abstém-se de fazer uma previsão.
• Outliers são ignorados ao atualizar o conjunto de vértices representativos, efetivamente tratando-os como um único nó com impacto zero na solução harmônica.

3. Contribuições Principais

1. Algoritmo Inovador: Um algoritmo de aprendizado semi-supervisionado online em tempo real que não requer feedback explícito para cada passo, dependendo em vez disso do rastreamento da variedade de dados.
2. Garantias Teóricas: Os autores fornecem uma análise de limite de arrependimento. Eles provam que o arrependimento por passo diminui a uma taxa de $O(n^{-1/2})$ à medida que o número de exemplos $n$ aumenta, desde que o parâmetro de regularização $\gamma_g$ seja escolhido adequadamente ($\Omega(n^{1/4})$).
3. Implementação Eficiente: A introdução de um "algoritmo de duplicação" baseado em quantização permite que o sistema execute em tempo real, mantendo uma representação de grafo de tamanho fixo, evitando a complexidade de tempo cúbica do SSL padrão.
4. Robustez: O método demonstrou ser robusto a outliers e capaz de adaptar-se a mudanças ambientais súbitas (ex.: iluminação, localização) sem retreinamento do zero.

4. Resultados Experimentais

O algoritmo foi avaliado em três conjuntos de dados de vídeo (V1, V2, VO) envolvendo tarefas de reconhecimento facial com classificação de 8 vias.

• Métricas de Desempenho:
  • Alcançou 95% de precisão em 90% de revocação nos conjuntos de dados V1 e V2.
  • Alcançou 100% de precisão e 95% de revocação no conjunto de dados VO (que incluía mudanças súbitas de localização e iluminação).
• Comparações:
  • vs. Vizinho Mais Próximo (NN): O aprendiz proposto superou o classificador NN offline em aproximadamente 10% em precisão nos mesmos níveis de revocação, atribuído ao rastreamento da variedade de dados.
  • vs. Boosting Semi-Supervisionado Online: O método proposto superou o boosting online de última geração, particularmente quando os aprendizes fracos não cobriam toda a distribuição de dados. O método de boosting degradou-se significativamente quando a cobertura de dados estava incompleta, enquanto a abordagem baseada em grafos adaptou sua representação dinamicamente.
• Capacidade em Tempo Real: O sistema executa em tempo real, processando aproximadamente 7 quadros por segundo mesmo com um tamanho de grafo de 500 vértices representativos.

5. Significado

• Aprendizado Adaptativo: Este trabalho demonstra que modelos de aprendizado de máquina de alta qualidade podem ser construídos e mantidos em tempo real usando supervisão humana mínima (rótulos iniciais) e abundância de dados não rotulados.
• Praticidade para Problemas do Mundo Real: Aborda os problemas de "início frio" e "deriva de conceito" comuns em aplicações do mundo real, como vigilância ou robótica, onde as distribuições de dados mudam ao longo do tempo e o rotulamento é caro.
• Generalizabilidade: Embora demonstrado em reconhecimento facial, o framework é geral e aplicável a outros domínios com fluxo de dados não rotulados (ex.: reconhecimento de objetos).
• Fundação Teórica: Preenche a lacuna entre SSL baseado em grafos estático e aprendizado online dinâmico, fornecendo limites teóricos sobre a qualidade das soluções em um cenário online.

Em conclusão, o artigo apresenta um framework robusto, fundamentado teoricamente e computacionalmente eficiente para sistemas de percepção em tempo real que aprendem continuamente a partir do ambiente sem necessidade de feedback humano constante.