Al Rahimi deu recentemente uma palestra muito provocativa no NIPS 2017, comparando o Machine Learning atual com a Alquimia. Uma de suas afirmações é que precisamos voltar aos desenvolvimentos teóricos, ter teoremas simples que provem resultados fundamentais.
Quando ele disse isso, comecei a procurar os principais teoremas da ML, mas não consegui encontrar uma boa referência para entender os principais resultados. Então, aqui está a minha pergunta: quais são os principais teoremas matemáticos atuais (teoria) em ML / DL e o que eles provam? Eu acho que o trabalho de Vapnik iria para algum lugar aqui. Como um extra, quais são os principais problemas teóricos em aberto?
machine-learning
deep-learning
theory
statslearner
fonte
fonte
Respostas:
Como escrevi nos comentários, essa pergunta me parece muito ampla, mas tentarei responder. Para estabelecer alguns limites, começarei com um pouco de matemática subjacente à maior parte do ML e depois me concentrarei nos resultados recentes do DL.
O tradeoff de variação de desvio é mencionado em inúmeros livros, cursos, MOOCs, blogs, tweets etc. no ML, portanto, não podemos começar sem mencioná-lo:
Prova aqui: https://web.stanford.edu/~hastie/ElemStatLearn/
O Teorema de Gauss-Markov (sim, a regressão linear continuará sendo uma parte importante do Machine Learning, não importa o que: lide com ele) esclarece que, quando o modelo linear é verdadeiro e algumas suposições sobre o termo do erro são válidas, o OLS tem o mínimo erro quadrático médio (que na expressão acima é apenas ) apenas entre os estimadores lineares imparciais do modelo linear. Assim, poderia haver estimadores lineares com viés (ou estimadores não-lineares) que têm um erro quadrado médio melhor e, portanto, um erro de previsão esperado melhor que o OLS. E isso abre caminho para todo o arsenal de regularização (regressão de cordilheira, LASSO, queda de peso, etc.), que é um cavalo de batalha de ML. Uma prova é dada aqui (e em inúmeros outros livros):Bias2 + Variance https://www.amazon.com/Linear-Statistical-Models-James-Stapleton/dp/0470231467
Provavelmente mais relevante para a explosão de abordagens de regularização, como observado por Carlos Cinelli nos comentários, e definitivamente mais divertido de aprender, é o teorema de James-Stein . Considere independentes, mesma variância, mas não as mesmas variáveis aleatórias médias gaussianas:n
em outras palavras, temos um vetor aleatório gaussiano componentes . Temos uma amostra de e queremos estimar . O estimador MLE (e também UMVUE) é obviamente . Considere o estimador de James-Steinn− X∼N(θ,σ2I) x X θ θ^MLE=x
Claramente, se , reduz a estimativa do MLE para zero. O teorema de James-Stein afirma que, para , domina estritamente , ou seja, possui MSE mais baixo . Surpreendentemente, mesmo se nos encolhermos para qualquer outra constante , ainda domina . Desde o(n−2)σ2≤||x||2 θ^JS n≥4 θ^JS θ^MLE ∀ θ c≠0 θ^JS θ^MLE Xi Se for independente, pode parecer estranho que, ao tentar estimar a altura de três pessoas independentes, incluindo uma amostra do número de maçãs produzidas na Espanha, possa melhorar nossa estimativa em média . O ponto principal aqui é "em média": o erro quadrado médio para a estimativa simultânea de todos os componentes do vetor de parâmetro é menor, mas o erro quadrado de um ou mais componentes pode muito bem ser maior e, na verdade, é geralmente quando você tem observações "extremas".
Descobrir que o MLE, que na verdade era o estimador "ideal" para o caso de estimativa univariada, foi destronado para a estimativa multivariada, foi um choque na época e levou a um grande interesse em encolhimento, mais conhecido como regularização na linguagem da ML. Pode-se notar algumas semelhanças com modelos mistos e o conceito de "força de empréstimo": de fato, há alguma conexão, como discutido aqui
Visão unificada sobre o encolhimento: qual é a relação (se houver) entre o paradoxo de Stein, a regressão de crista e os efeitos aleatórios em modelos mistos?
Referência: James, W., Stein, C., Estimativa com perda quadrática . O objetivo do presente trabalho é analisar o comportamento do consumidor em relação ao consumo de bebidas alcoólicas, com o objetivo de avaliar o consumo de bebidas alcoólicas em estabelecimentos comerciais.
A Análise de Componentes Principais é a chave para o importante tópico de redução de dimensão, e é baseada na Decomposição de Valor Singular : para cada matriz real (embora o teorema generalize facilmente para matrizes complexas), podemos escreverN×p X
onde de tamanho é ortogonal, é uma matriz diagonal com elementos diagonais não negativos e de tamanho é novamente ortogonal. Para provas e algoritmos sobre como calculá-lo, consulte: Golub, G. e Van Loan, C. (1983), Matrix computations , John Hopkins University press, Baltimore.U N×p D p×p U p×p
O teorema de Mercer é a base para muitos métodos diferentes de ML: splines de chapas finas, máquinas de vetores de suporte, a estimativa de Kriging de um processo aleatório gaussiano etc. Basicamente, é um dos dois teoremas por trás do chamado truque do kernel . Seja uma função ou núcleo contínuo simétrico. se é semidefinido positivo, ele admite uma base ortonormal de funções próprias correspondentes a valores próprios não negativos:K(x,y):[a,b]×[a,b]→R K
A importância desse teorema para a teoria da ML é atestada pelo número de referências obtidas em textos famosos, como, por exemplo, o texto de Rasmussen & Williams sobre processos gaussianos .
Referência: J. Mercer, Funções do tipo positivo e negativo, e sua conexão com a teoria das equações integrais. Transações Filosóficas da Sociedade Real de Londres. Série A, Contendo documentos de caráter matemático ou físico, 209: 415-446, 1909
Há também uma apresentação mais simples em Konrad Jörgens, operadores integrais lineares , Pitman, Boston, 1982.
O outro teorema que, juntamente com o teorema de Mercer, estabelece os fundamentos teóricos do truque do kernel, é o teorema do representador . Suponha que você tenha um espaço de amostra e um kernel semidefinido positivo simétrico . Também permitem que ser os RKHS associados com . Por fim, seja uma amostra de treinamento. O teorema diz que entre todas as funções , todas admitem uma representação infinita em termos de funções próprias deX K:X×X→R HK K S={xi,yi}ni=1 f∈HK K por causa do teorema de Mercer, aquele que minimiza o risco regularizado sempre tem uma representação finita na base formada pelo núcleo avaliado nos pontos de treinamento, ou seja,n
(o teorema é a última igualdade). Referências: Wahba, G. 1990, Spline Models for Observational Data , SIAM, Filadélfia.
O teorema da aproximação universal já foi citado pelo usuário Tobias Windisch e é muito menos relevante para o Machine Learning do que para a análise funcional, mesmo que possa não parecer à primeira vista. O problema é que o teorema apenas diz que essa rede existe, mas:
Um ponto de dor menor com a versão deste teorema de Hornik é que ele não se aplica às funções de ativação do ReLU. No entanto, Bartlett já provou uma versão estendida que cobre essa lacuna.
Até agora, acho que todos os teoremas que considerei eram bem conhecidos de qualquer pessoa. Então agora é hora das coisas divertidas :-) Vamos ver alguns teoremas do Deep Learning :
Premissas:
Então:
Isso é muito interessante: as CNNs feitas apenas de camadas convolucionais, ReLU, max-pooling, ReLU totalmente conectado e camadas lineares são funções positivamente homogêneas , enquanto que se incluirmos funções de ativação sigmóide, isso não é mais verdade, o que pode explicar em parte a superioridade. desempenho em algumas aplicações do pool ReLU + max em relação aos sigmóides. Além do mais, os teoremas somente são válidos se for positivamente homogêneo em do mesmo grau que . Agora, o fato divertido é que ou regularização, embora positivamente homogênea, não têm o mesmo grau de (o grau deΘ W Φ l1 l2 Φ Φ , no caso simples da CNN mencionado anteriormente, aumenta com o número de camadas). Em vez disso, métodos mais modernos de regularização, como normalização de lotes e SGD de caminho, correspondem a uma função de regularização positivamente homogênea do mesmo grau que , e a desistência, embora não se encaixe exatamente nessa estrutura, mantém fortes semelhanças com ela. Isso pode explicar por que, a fim de obter alta precisão com CNNs, e regularização não são suficientes, mas precisamos empregar todos os tipos de truques diabólicos, como o abandono e normalização lote! Que eu saiba, essa é a coisa mais próxima de uma explicação da eficácia da normalização de lotes, que de outra forma é muito obscura, como corretamente observado por Al Rahimi em sua palestra.Φ l1 l2
Outra observação que algumas pessoas fazem, com base no Teorema 1 , é que isso poderia explicar por que a ReLU funciona bem, mesmo com o problema de neurônios mortos . De acordo com essa intuição, o fato de que, durante o treinamento, alguns neurônios da ReLU "morrem" (passam para a ativação zero e nunca se recuperam disso, pois para o gradiente da ReLU é zero) é "um recurso, não um bug ", porque se atingimos um mínimo e uma sub-rede completa morreu, provavelmente alcançamos um mínimo global (sob as hipóteses do Teorema 1x<0 ) Posso estar perdendo alguma coisa, mas acho que essa interpretação é absurda. Antes de tudo, durante o treinamento, as ReLUs podem "morrer" muito antes de atingirmos um mínimo local. Em segundo lugar, deve-se provar que, quando as unidades ReLU "morrem", elas sempre o fazem em uma sub-rede completa: o único caso em que isso é trivialmente verdadeiro é quando você tem apenas uma camada oculta, caso em que cada neurônio é naturalmente uma sub-rede. Mas, em geral, eu seria muito cauteloso ao ver "neurônios mortos" como uma coisa boa.
Referências:
B. Haeffele e R. Vidal, Otimização global no treinamento de redes neurais , Na Conferência do IEEE sobre Visão Computacional e Reconhecimento de Padrões, 2017.
B. Haeffele e R. Vidal. Optimalidade global em fatoração de tensor, aprendizado profundo e além , arXiv, abs / 1506.07540, 2015.
A classificação de imagens requer representações de aprendizado que são invariantes (ou pelo menos robustas, ou seja, muito fracamente sensíveis) a várias transformações, como localização, pose, ponto de vista, iluminação, expressão etc., que geralmente estão presentes nas imagens naturais, mas não contêm informações. para a tarefa de classificação. O mesmo vale para o reconhecimento de fala: mudanças de tom, volume, ritmo, sotaque. etc. não deve levar a uma alteração na classificação da palavra. Operações como convolução, pool máximo, pool médio, etc., usadas nas CNNs, têm exatamente esse objetivo; portanto, intuitivamente, esperamos que funcionem para esses aplicativos. Mas temos teoremas para apoiar essa intuição? Existe um teorema da invariância da tradução vertical, que, apesar do nome, não tem nada a ver com a tradução na direção vertical, mas é basicamente um resultado que afirma que os recursos aprendidos nas camadas a seguir ficam cada vez mais invariáveis à medida que o número de camadas aumenta. Isso se opõe a um antigo teorema da invariância da tradução horizontal que, no entanto, vale para as redes de dispersão, mas não para as CNNs. O teorema é muito técnico, no entanto:
Indique com a saída da camada da CNN, quando a entrada for . Então finalmente:Φn(f) n f
(as barras triplas não são um erro), o que basicamente significa que cada camada aprende características que se tornam cada vez mais invariantes e, no limite de uma rede infinitamente profunda, temos uma arquitetura perfeitamente invariante. Como as CNNs têm um número finito de camadas, elas não são perfeitamente invariantes à tradução, o que é algo bem conhecido dos profissionais.
Referência: T. Wiatowski e H. Bolcskei, Uma teoria matemática de redes neurais convolucionais profundas para extração de recursos , arXiv: 1512.06293v3 .
Para concluir, numerosos limites para o erro de generalização de uma Rede Neural Profunda com base em sua dimensão Vapnik-Chervonkensis ou na complexidade de Rademacher crescem com o número de parâmetros (alguns até exponencialmente), o que significa que eles não podem explicar por que os DNNs funcionam tão bem na prática, mesmo quando o número de parâmetros é consideravelmente maior que o número de amostras de treinamento. De fato, a teoria do VC não é muito útil no Deep Learning.
Por outro lado, alguns resultados do ano passado vincularam o erro de generalização de um classificador DNN a uma quantidade independente da profundidade e tamanho da rede neural, mas depende apenas da estrutura do conjunto de treinamento e do espaço de entrada. Sob algumas suposições bastante técnicas sobre o procedimento de aprendizado e sobre o conjunto de treinamento e o espaço de entrada, mas com muito poucas suposições sobre o DNN (em particular, as CNNs são totalmente cobertas), então com probabilidade de pelo menos , temos1−δ
Onde:
J. Sokolic, R. Giryes, G. Sapiro e M. Rodrigues. Erro de generalização de classificadores invariantes . Em AISTATS, 2017
fonte
See [here] for a modern exposition
, ou vice-versa, "para o artigo original".Penso que o seguinte teorema ao qual você alude é considerado fundamental na aprendizagem estatística.
Teorema (Vapnik e Chervonenkis, 1971) Seja uma classe de funções de hipótese de um domínio para e deixe a função de perda ser a perda de . Então, o seguinte é equivalente:H X {0,1} 0−1
Provado em uma versão quantitativa aqui:
VN Vapnik e AY Chervonenkis: Sobre a convergência uniforme de frequências relativas de eventos com suas probabilidades. Teoria da Probabilidade e suas Aplicações, 16 (2): 264-280, 1971.
A versão formulada acima, juntamente com uma boa exposição de outros resultados da teoria da aprendizagem, está disponível aqui :
Shalev-Shwartz, Shai e Shai Ben-David. Compreendendo o aprendizado de máquina: da teoria aos algoritmos. Cambridge University Press, 2014.
fonte
O truque do kernel é uma idéia geral usada em muitos lugares e vem de muitas matemáticas abstratas sobre Hilbert Spaces. Teoria demais para eu digitar (copiar ...) uma resposta aqui, mas se você passar por isso, poderá ter uma boa idéia de seus fundamentos rigorosos:
http://www.stats.ox.ac.uk/~sejdinov/teaching/atml14/Theory_2014.pdf
fonte
O meu favorito é a desigualdade da Kraft.
Essa desigualdade relaciona a compressão com as densidades de probabilidade : dado um código, o comprimento de um resultado representado por esse código é a probabilidade de log negativa de um modelo identificado pelo código.
Além disso, o teorema do almoço livre para aprendizado de máquina tem um irmão menos conhecido do teorema da não-compressão, que afirma que nem todas as seqüências podem ser compactadas.
fonte
Eu não o chamaria de teorema principal , mas acho que o seguinte (às vezes chamado de teorema da aproximação Universal) é interessante (e pelo menos para mim surpreende), pois afirma o poder aproximado das redes neurais feed-forward.
Teorema: Seja uma função contínua não constante e monotinicamente crescente. Para qualquer função contínua e qualquer , existe um inteiro e um perceptron multicamada com uma camada oculta com Neurônios que tem como ativação função para queσ f:[0,1]m→R ϵ>0 N F N σ
Obviamente, como se trata de uma declaração de existência , seu impacto para os profissionais é insignificante.
Uma prova pode ser encontrada em Hornik, Approximation Capabilities of Muitilayer Feedforward Networks, Neural Networks 4 (2), 1991,
fonte
Um bom post focado nessa questão (especificamente aprendizado profundo em vez de teoremas gerais de aprendizado de máquina) está aqui:
https://medium.com/mlreview/modern-theory-of-deep-learning-why-does-it-works-so-well-9ee1f7fb2808
Ele fornece um resumo acessível dos principais teoremas emergentes para a capacidade de generalizar redes neurais profundas tão bem.
fonte