Quais são os principais teoremas do aprendizado de máquina (profundo)?

45

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?

statslearner
fonte
3
@Tim Este tópico é semelhante a stats.stackexchange.com/questions/2379/… ("Quais são os grandes problemas nas estatísticas?").
whuber
2
É um pouco amplo. Você poderia pelo menos especificar um subconjunto do Machine Learning? Se nos limitarmos ao aprendizado profundo, ou pelo menos ao aprendizado supervisionado, pode-se tentar uma resposta. Mas se você insistir em algo como "Matemática do aprendizado de máquina", uma resposta levará séculos para ser escrita.
DeltaIV 13/01/19
3
À luz do exemplo analógico do @ whuber, estou inclinado a dizer que isso deve permanecer aberto como CW, especialmente se isso puder ser limitado a um subconjunto específico de ML, como aprendizado supervisionado , conforme solicitado pelo DeltaV.
gung - Restabelece Monica
3
@DeltaIV Observe que "Deep" está no título.
ameba diz Restabelecer Monica
4
O entendimento desta questão foi o tópico de uma série recente de palestras organizadas por David Donoho: veja stats385.github.io .
precisa saber é o seguinte

Respostas:

43

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:

E[(Yf^(X))2|X=x0]=σϵ2+(Ef^(x0)f(x0))2+E[(f^(x0)Ef^(x0))2]=Irreducible error + Bias2 + Variance

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 + Variancehttps://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

Xi|μiN(θi,σ2),i=1,,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-SteinnXN(θ,σ2I)xXθθ^MLE=x

θ^JS=(1(n2)σ2||x||2)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(n2)σ2||x||2θ^JS n4θ^JS θ^MLE θc0θ^JSθ^MLEXiSe 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×pX

X=UDVT

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.UN×pDp×pUp×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]RK

K(x,y)=i=1γiϕi(x)ϕi(y)

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 deXK:X×XRHKKS={xi,yi}i=1nfHKKpor 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

minfHKi=1nL(yi,f(xi))+λ||f||HK2=min{cj}1i=1nL(yi,jcjϕj(xi))+λjcj2γj=i=1nαiK(x,xi)

(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:

  • não fornece nenhuma correlação entre o tamanho da camada oculta e alguma medida da complexidade da função de destino , como por exemplo Variação Total. Se e o necessário para um erro fixo cresceram exponencialmente com , então, neural camada única oculta redes seria inútil.Nf(x)f(x)=sin(ωx):[0,2π][1,1]Nϵω
  • não diz se a rede é aprendível . Em outras palavras, suponha que, dado e , sabemos que um tamanho NN se aproximará de com a tolerância necessária no hipercubo. Então, usando conjuntos de treinamento de tamanho e um procedimento de aprendizado como, por exemplo, suporte traseiro, temos alguma garantia de que, ao aumentar , possamos recuperar ?F(x)fϵNfMMF
  • finalmente, e pior de tudo, não diz nada sobre o erro de previsão das redes neurais. O que estamos realmente interessado em é uma estimativa do erro de previsão, pelo menos, calculados para o conjunto conjuntos de treinamento de tamanho . O teorema não ajuda nesse sentido.M

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:

  • a rede neural profunda (para fixo , é a função que associa as entradas da rede neural com suas saídas) e a perda de regularização são somas de positividade funções homogêneas do mesmo grauΦ(X,W)WΦW(X)Θ(W)
  • a função de perda é convexa e uma vez diferenciável em , em um conjunto compactoL(Y,Φ(X,W)XS

Então:

  • qualquer mínimo local para modo que uma sub-rede de tenha pesos zero, é um mínimo global ( Teorema 1 )L(Y,Φ(X,W))+λΘ(W)Φ(X,W)
  • acima de um tamanho crítico de rede, a descida local sempre convergirá para um mínimo global a partir de qualquer inicialização ( Teorema 2 ).

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Φl1l2ΦΦ, 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.Φl1l2

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:

  • assuma que (sua imagem de entrada) é quadrada-integrávelf
  • suponha que seu filtro comuta com o operador de tradução , que mapeia a imagem de entrada para uma cópia traduzida de si mesma . Um núcleo de convolução aprendido (filtro) satisfaz esta hipótese.TtfTtf
  • suponha que todos os filtros, não linearidades e pooling na sua rede atendam às chamadas condições de admissibilidade fraca , que são basicamente algum tipo de regularidade fraca e condições de limite. Essas condições são satisfeitas pelo kernel de convolução aprendido (desde que alguma operação de normalização seja executada em cada camada), ReLU, sigmoid, tanh, etc, não linearidades e pelo pool médio, mas não pelo pool máximo , mas não pelo pool máximo. Portanto, abrange algumas arquiteturas da CNN (não todas) no mundo real.
  • Finalmente, suponha que cada camada tenha um fator de pool , ou seja, o pool é aplicado em cada camada e descarta efetivamente as informações. A condição também seria suficiente para uma versão mais fraca do teorema.nSn>1Sn1

Indique com a saída da camada da CNN, quando a entrada for . Então finalmente:Φn(f)nf

limn|||Φn(Tff)Φn(f)|||=0

(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δ

GE2log2NyNγm+2log(1/δ)m

Onde:

  • GE é o erro de generalização, definido como a diferença entre a perda esperada (a perda média do classificador aprendido em todos os pontos de teste possíveis) e a perda empírica (apenas o bom e velho erro do conjunto de treinamento)
  • Ny é o número de classes
  • m é o tamanho do conjunto de treinamento
  • Nγ é o número de cobertura dos dados, uma quantidade relacionada à estrutura do espaço de entrada e à separação mínima entre pontos de diferentes classes no conjunto de treinamento. Referência:

J. Sokolic, R. Giryes, G. Sapiro e M. Rodrigues. Erro de generalização de classificadores invariantes . Em AISTATS, 2017

DeltaIV
fonte
2
+1. Ótima resposta, a última parte é muito intrigante. Na primeira parte, o teorema de Mercer se parece com o SVD que você apresentou logo acima.
Ameba diz Reinstate Monica
1
@amoeba, você está certo, mas 1) nem todos os leitores são tão habilidosos em matemática quanto você, que reconheceriam imediatamente a semelhança entre SVD, expansão de Karhunen- Loeve e o teorema de Mercer. Também 2) o outro teorema da Análise Funcional que "potencializa" o truque do kernel, e que eu escolhi não incluir, é mais difícil de explicar do que o teorema de Mercer, e eu já perdi meu sábado :-) Talvez eu o adicione amanhã!
DeltaIV 13/01/19
1
Gauss Markov parece fora de lugar, nunca vi alguém se importar com o AZUL na comunidade de ML.
Carlos Cinelli
2
Concordo que, como regra geral, a referência original (arcaica) geralmente possui notação tediosa. Dito isto, o artigo de Mercer é surpreendentemente moderno nesse aspecto e eu o adicionei exatamente por causa disso. :) (Eu disse originalmente, esta é uma resposta muito boa, este é apenas um comentário após o
voto positivo
2
Eu gosto do teorema de Mercer aqui, não o remova. E por que não ter os dois links? Apenas adicione smth like See [here] for a modern exposition, ou vice-versa, "para o artigo original".
ameba diz Restabelecer Monica
11

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:HX{0,1}01

  1. H tem a propriedade de convergência uniforme.
  2. H é PAC aprendível.
  3. H tem uma dimensão VC finita.

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.

epsilon de máquina
fonte
4

O meu favorito é a desigualdade da Kraft.

Teorema: Para qualquer método de descrição do alfabeto finito , o comprimento da palavra de código deve satisfazer a desigualdade .CA={1,,m}LC(1),,LC(2)xA2LC(x)1

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.

bayerj
fonte
4

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]mRϵ>0NFNσ

|F(x)f(x)|ϵ
para todos .x[0,1]m

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,

Tobias Windisch
fonte
5
Esse teorema é um pouco desinteressante, pois não é específico das redes neurais. Muitas outras classes de funções compartilham propriedades de aproximação semelhantes (e às vezes mais fortes). Veja, por exemplo, o teorema de Stone-Weierstrass. Um resultado mais interessante seria a consistência da regressão da rede neural em uma estrutura geral. Além disso, deve haver limites conhecidos sobre o erro médio de generalização em termos da complexidade da rede e do tamanho da amostra de treinamento.
Olivier
1
@ Olivier: eu concordo totalmente. Mas, embora esse teorema não seja exclusivamente dedicado às redes neurais, ainda acho sua afirmação, sua prova rigorosa e suas implicações interessantes. Por exemplo, diz que, desde que você esteja usando uma função de ativação com as propriedades declaradas acima, a capacidade aproximada da rede é a mesma (grosso modo). Ou, diz que as redes neurais estão sujeitas a super adaptação, já que você pode aprender muito com uma camada oculta.
Tobias Windisch
1
Não diz exatamente isso. Diz apenas que existe uma rede neural com uma camada oculta que pode representar , mas não diz nada sobre como cresce com , por exemplo, ou com alguma medida da complexidade de (por exemplo, sua variação total ) Não diz se você pode os pesos da sua rede, dados dados. Você verá que, em muitos casos interessantes, é exponencialmente maior para redes de uma camada oculta do que para redes multicamadas (profundas). É por isso que ninguém usa redes de camada oculta no ImageNet ou no Kaggle. fNmflearnN
DeltaIV
@ DeltaIV: Há um erro de digitação na última frase do meu comentário anterior: a palavra "aprender" deve ser realmente "aproximada" (caso contrário, minha afirmação sobre "super ajuste" não faria sentido). Obrigado pela dica!
Tobias Windisch
Sim, eu interpretei isso no sentido de "aproximar". Meu argumento é que, mesmo que você saiba que, em teoria, você pode aproximar qualquer função (em um hipercubo limitado) com uma camada NN oculta, na prática é inútil em muitos casos. Outro exemplo: os processos gaussianos com o kernel exponencial ao quadrado têm a propriedade de aproximação universal, mas não eliminaram todos os outros métodos de regressão, também pelo fato de que, para alguns problemas, o número de amostras necessárias para uma aproximação precisa cresce exponencialmente.
DeltaIV