Quando: 28 de abril de 2023, sexta, às 16h
Onde: Sala 2077
Título: Um algoritmo de aprendizagem universalmente consistente com um erro monótono
Palestrante: Vladimir Pestov (UFPB e uOttawa)
Resumo: Vou apresentar uma solução, em afirmativo, de um problema em aberto desde 1996 sobre a existência de um algoritmo de aprendizagem com as propriedades em título (JMLR 23(157):1−27, 2022).
Um algoritmo (ou regra) de aprendizagem supervisionada é uma aplicação associando um classificador a cada amostra rotulada, predizendo os rótulos desconhecidos de todos os pontos. O erro de classificação é a probabilidade de associar um rótulo errado. Um algoritmo é chamado universalmente consistente se, qualquer que seja a lei de distribuição de dados rotulados, o erro de classificação converge para o erro menor possível (o erro de Bayes) no limite quando o tamanho da amostra cresce. Intuitivamente, quanto mais dados, menos o erro de classificação, mas todos os algoritmos conhecidos admitem situações onde o erro cresce temporariamente para alguns valores do tamanho. Vou descrever um algoritmo que possui a monotonicidade.
Depois da pré-publicação do meu algoritmo, um grupo de pesquisadores (Bousquet, Daniely, Kaplan, Mansour, Moran, e Stemmer, arXiv:2202.05246 [cs.LG]) já estendeu o resultado mostrando que qualquer algoritmo consistente pode ser convertido em um algoritmo monótono. Vou tentar discutir o resultado deles também.
