Minimização de risco empírico - Empirical risk minimization

Parte de uma série sobre
Aprendizado de máquina e mineração de dados
Problemas Classificação Clustering Regressão Detecção de anomalia Limpeza de Dados AutoML Regras de associação Aprendizagem por reforço Previsão estruturada Engenharia de recursos Aprendizagem de recursos Aprendizagem online Aprendizagem semissupervisionada Aprendizagem não supervisionada Aprendendo a classificar Indução gramatical
Aprendizagem supervisionada ( classificação  • regressão ) Árvores de decisão Conjuntos Ensacamento Boosting Floresta aleatória k -NN Regressão linear Baías ingénuas Redes neurais artificiais Regressão logística Perceptron Máquina de vetor de relevância (RVM) Máquina de vetores de suporte (SVM)
Clustering BÉTULA CURA Hierárquico k- significa Expectativa-maximização (EM) DBSCAN ÓPTICA Mudança média
Redução de dimensionalidade Análise Fatorial CCA ICA LDA NMF PCA PGD t-SNE
Previsão estruturada Modelos gráficos Rede Bayes Campo aleatório condicional Markov Oculto
Detecção de anomalia k -NN Fator de outlier local
Rede neural artificial Autoencoder Computação cognitiva Aprendizagem profunda DeepDream Perceptron multicamadas RNN LSTM GRU ESN Máquina de Boltzmann restrita GAN SOM Rede neural convolucional U-Net Transformador Spiking rede neural Memtransistor RAM eletroquímica (ECRAM)
Aprendizagem por reforço Q-learning SARSA Diferença temporal (TD)
Teoria Compensação de polarização-variância Teoria de aprendizagem computacional Minimização de risco empírico Aprendizagem Occam Aprendizagem PAC Aprendizagem estatística Teoria VC
Locais de aprendizado de máquina NeurIPS ICML ML JMLR ArXiv: cs.LG
Artigos relacionados Glossário de inteligência artificial Lista de conjuntos de dados para pesquisa de aprendizado de máquina Esboço do aprendizado de máquina
v t e

A minimização de risco empírico (ERM) é um princípio na teoria de aprendizagem estatística que define uma família de algoritmos de aprendizagem e é usado para fornecer limites teóricos sobre seu desempenho. A ideia central é que não podemos saber exatamente quão bem um algoritmo funcionará na prática (o verdadeiro "risco") porque não sabemos a verdadeira distribuição de dados em que o algoritmo trabalhará, mas podemos, em vez disso, medir seu desempenho em um conjunto conhecido de dados de treinamento (o risco "empírico").

Fundo

Considere a seguinte situação, que é um cenário geral de muitos problemas de aprendizagem supervisionada . Temos dois espaços de objetos e e gostaríamos de aprender uma função (freqüentemente chamada de hipótese ) que gera um objeto , dado . Para tal, temos à nossa disposição um conjunto de exemplos formativos onde é um input e é a resposta correspondente que pretendemos obter . ${\ displaystyle X}$${\ displaystyle Y}$${\ displaystyle \ h: X \ a Y}$${\ displaystyle y \ in Y}$${\ displaystyle x \ in X}$${\ displaystyle n}$${\ displaystyle \ (x_ {1}, y_ {1}), \ ldots, (x_ {n}, y_ {n})}$${\ displaystyle x_ {i} \ in X}$${\ displaystyle y_ {i} \ in Y}$${\ displaystyle \ h (x_ {i})}$

Para colocá-lo mais formalmente, assumimos que há uma distribuição de probabilidade conjunta sobre e , e que o conjunto de treinamento consiste de casos extraídos iid partir . Observe que a suposição de uma distribuição de probabilidade conjunta nos permite modelar a incerteza nas previsões (por exemplo, do ruído nos dados) porque não é uma função determinística de , mas sim uma variável aleatória com distribuição condicional para um fixo . ${\ displaystyle P (x, y)}$${\ displaystyle X}$${\ displaystyle Y}$${\ displaystyle n}$${\ displaystyle \ (x_ {1}, y_ {1}), \ ldots, (x_ {n}, y_ {n})}$${\ displaystyle P (x, y)}$${\ displaystyle y}$${\ displaystyle x}$ ${\ displaystyle P (y | x)}$${\ displaystyle x}$

Também assumimos que recebemos uma função de perda com valor real não negativa que mede o quão diferente a previsão de uma hipótese é do resultado verdadeiro. O risco associado à hipótese é então definido como a expectativa da função de perda: ${\ displaystyle L ({\ hat {y}}, y)}$${\ displaystyle {\ hat {y}}}$${\ displaystyle y.}$${\ displaystyle h (x)}$

${\ displaystyle R (h) = \ mathbf {E} [L (h (x), y)] = \ int L (h (x), y) \, dP (x, y).}$

A função de perda comumente usado em teoria é a função 0-1 perda : . ${\ displaystyle L ({\ hat {y}}, y) = {\ begin {cases} 1 & {\ mbox {if}} \ quad {\ hat {y}} \ neq y \\ 0 & {\ mbox {if }} \ quad {\ hat {y}} = y \ end {casos}}}$

O objetivo final de um algoritmo de aprendizagem é encontrar uma hipótese entre uma classe fixa de funções para a qual o risco é mínimo: ${\ displaystyle h ^ {*}}$${\ displaystyle {\ mathcal {H}}}$${\ displaystyle R (h)}$

${\ displaystyle h ^ {*} = {\ underset {h \ in {\ mathcal {H}}} {\ operatorname {arg \, min}}} \, {R (h)}.}$

Minimização de risco empírico

Em geral, o risco não pode ser calculado porque a distribuição é desconhecida para o algoritmo de aprendizagem (esta situação é conhecida como aprendizagem agnóstica ). No entanto, podemos calcular uma aproximação, chamada de risco empírico , calculando a média da função de perda no conjunto de treinamento: ${\ displaystyle R (h)}$${\ displaystyle P (x, y)}$

${\ displaystyle \! R _ {\ text {emp}} (h) = {\ frac {1} {n}} \ sum _ {i = 1} ^ {n} L (h (x_ {i}), y_ {eu}).}$

O princípio de minimização do risco empírico afirma que o algoritmo de aprendizagem deve escolher uma hipótese que minimize o risco empírico: ${\ displaystyle {\ hat {h}}}$

${\ displaystyle {\ hat {h}} = {\ underset {h \ in {\ mathcal {H}}} {\ operatorname {arg \, min}}} \, R _ {\ text {emp}} (h) .}$

Assim, o algoritmo de aprendizagem definido pelo princípio ERM consiste em resolver o problema de otimização acima .

Propriedades

Complexidade computacional

A minimização do risco empírico para um problema de classificação com uma função de perda de 0-1 é conhecido por ser um problema NP-difícil, mesmo para uma classe relativamente simples de funções como classificadores lineares . Porém, pode ser resolvido de forma eficiente quando o risco empírico mínimo é zero, ou seja, os dados são linearmente separáveis .

Na prática, os algoritmos de aprendizado de máquina lidam com isso empregando uma aproximação convexa para a função de perda de 0-1 (como a perda de dobradiça para SVM ), que é mais fácil de otimizar, ou impondo suposições sobre a distribuição (e, assim, deixando de ser um aprendizado agnóstico algoritmos aos quais o resultado acima se aplica). ${\ displaystyle P (x, y)}$

Veja também

• Estimativa de máxima verossimilhança
• Estimador M

Referências

Leitura adicional

• Vapnik, V. (2000). The Nature of Statistical Learning Theory . Ciência da Informação e Estatística. Springer-Verlag . ISBN 978-0-387-98780-4.