Limites de generalização no SVM

11

Estou interessado em resultados teóricos para a capacidade de generalização de máquinas de vetores de suporte, por exemplo, limites na probabilidade de erro de classificação e na dimensão Vapnik-Chervonenkis (VC) dessas máquinas. No entanto, lendo a literatura, tive a impressão de que alguns resultados recorrentes semelhantes tendem a diferir levemente de autor para autor, particularmente no que diz respeito às condições técnicas necessárias para um dado limite.

A seguir, lembrarei da estrutura do problema SVM e do estado 3 dos principais resultados de generalização que encontrei de forma recorrente de uma forma ou de outra dou três referências principais ao longo da exposição.

Configuração do problema :

Suponha temos uma amostra de dados dos pares independentes e identicamente distribuídas (iid) em que para todos os , e . Construímos uma máquina de vetores de suporte (SVM) que maximiza a mínima margem entre o hiperplana separação definida por , e e o ponto mais próximo entre , para separar as duas classes definidas por e . Deixamos que o SVM admita alguns erros através de uma margem flexível introduzindo variáveis ​​de folga(xi,yi)1inixiRpyi{1,1}m{x:wx+b=0}wRpbRx1,,xny=1y=1 - w b ξ1,,ξn mas, para simplificar a notação, ignoramos a possibilidade de kernels. Os parâmetros da solução e são obtidos resolvendo o seguinte programa de otimização quadrática convexa:wb

minw,b,ξ1,,ξn12w2+Ci=1nξis.t.:yi(wxi+b)1ξi,i{1,,n}ξi0,i{1,,n}

Estamos interessados ​​na capacidade de generalização desta máquina.

Dimensão VC de Vapnik-ChervonenkisVC :

Um primeiro resultado é devido a (Vapnik, 2000), no qual ele limita a dimensão VC de um hiperplano de separação, teorema 5.1. Deixando, temos:R=maxxixi

VCmin((Rm)2,p)+1

Esse resultado pode ser novamente encontrado no teorema 6. (Burges, 1998). No entanto, parece que o teorema de Burges é mais restritivo que o mesmo resultado de Vapnik, pois ele precisa definir uma categoria especial de classificadores, conhecidos como classificadores tolerantes a intervalos. ao qual o SVM pertence , para indicar o teorema.

Limites da probabilidade de erros :

Em (Vapnik, 2000), o teorema 5.2 da página 139 fornece o seguinte limite na capacidade de generalização do SVM:

E[Perror]1nE[min(p,nSV,(Rw)2)]

onde é o número de vetores de suporte do SVM. Esses resultados parecem ser encontrados novamente em (Burges, 1998), equações (86) e (93), respectivamente. Mas, novamente, Burges parece diferir de Vapnik, pois ele separa os componentes dentro da função mínima acima em diferentes teoremas, com diferentes condições.nSV

Outro resultado que aparece em (Vapnik, 2000), p.133, é o seguinte. Supondo novamente que, para todo , e deixando e , definimos como igual a:ixi2R2hVCϵ[0,1]ζ

ζ=4h(ln2nh+1)lnϵ4n

Também definimos como o número de exemplos de treinamento mal classificados pelo SVM. Então, com a probabilidade , podemos afirmar que a probabilidade de um exemplo de teste não ser separado corretamente pelo hiperplano -gingin ou seja, SVM com margem tem o limite:nerror1ϵmm

Perrornerrorn+ζ2(1+1+4nerrornζ)

No entanto, em (Hastie, Tibshirani e Friedman, 2009), p.438, um resultado muito semelhante é encontrado:

ErrorTestζ

Conclusão :

Parece-me que existe um certo grau de conflito entre esses resultados. Por outro lado, duas dessas referências, embora canônicas na literatura SVM, começam a ser um pouco antigas (1998 e 2000), especialmente se considerarmos que a pesquisa sobre o algoritmo SVM começou em meados dos anos noventa.

Minhas perguntas são:

  • Esses resultados ainda são válidos hoje ou foram provados errados?
  • Desde então, limites mais rigorosos com condições relativamente frouxas foram obtidos? Se sim, por quem e onde posso encontrá-los?
  • Finalmente, existe algum material de referência que sintetize os principais resultados de generalização sobre o SVM?

Referências :

Burges, JC (1998). "Um tutorial sobre máquinas de vetores de suporte para reconhecimento de padrões", Data Mining and Knowledge Discovery , 2: 121-167

Hastie, T., Tibshirani, R. e Friedman, J. (2009). The Elements of Statistical Learning , 2ª edição, Springer

Vapnik, VN (1998). Statistical Learning Theory , 1ª edição, John Wiley & Sons

Vapnik, VN (1999). "Uma visão geral da teoria estatística da aprendizagem", IEEE Transactions on Neural Networks , 10 (5): 988-999

Vapnik, VN (2000). A natureza da teoria estatística da aprendizagem , 2ª edição, Springer

Daneel Olivaw
fonte
uma referência que resume os limites de risco de ponta (para 2008) para SVMs: "Support Vector Machines" (Ingo Steinwart, Andreas Christmann, Springer 2008) .
registre

Respostas:

3

Não conheço a literatura a que você se refere em detalhes, mas acho que um resumo abrangente dos limites da generalização que deve estar atualizado pode ser encontrado em Boucheron et al. (2004) (Link: https://www.researchgate.net/profile/Olivier_Bousquet/publication/238718428_Advanced_Lectures_on_Machine_Learning_ML_Summer_Schools_2003_Canberra_Australia_February_2-14_2003_Tubingen_Germany_August_4-16_2003_Revised_Lectures/links/02e7e52c5870850311000000/Advanced-Lectures-on-Machine-Learning-ML-Summer-Schools-2003- Canberra-Austrália-fevereiro-2-14-2003-Tuebingen-Alemanha-agosto-4-16-2003-Revised-Lectures.pdf # page = 176 )

Esboçarei parte do SVM vinculado a seguir, deixando de fora detalhes e provas.

Antes de elaborar especificamente sobre o SVM bound, precisamos entender o que os limites de generalização estão tentando alcançar.

Primeiro, vamos supor que a verdadeira probabilidade seja conhecida; o melhor classificador possível seria o classificador bayes, ou seja, P(Y=+1|X=x)

g={+1  ifP(Y=1|X=x)>0.51  otherwise

O objetivo da teoria da aprendizagem estatística agora é encontrar a diferença entre um classificador da classe (por exemplo, SVM) e o classificador bayes, ou seja, Note-se que é a perda dada dados e esperadas é o melhor classificador possível na classe modelo . O termo é chamado de erro de estimativa e geralmente o foco, pois pode ser delimitado muito mais facilmente que o erro de aproximação (o outro termo). Também omitirei o erro de aproximação aqui.C

g^n=argmingCLn(g)
L(g^n)L(g)=L(g^n)L(gc)+L(gc)L(g).
L(g)=El(g(X),Y)gcCZ=:L(g)L(g^n)

O erro de estimativa pode ser decomposto ainda mais com Agora, isso pode ser delimitado por duas etapas:Z

Z=ZEZ+EZ.
  1. Limite usando McDiarmid desigualdadeZEZ

  2. Limite com a complexidade RademacherEZRn(C)=EsupgC|1/ni=1nl(g(Xi),Yi)|

Usando a desigualdade de McDiarmids, pode-se mostrar que, se a função de perda estiver em um intervalo não superior a , a etapa um resultará em um limite de onde é o nível de confiança. Para o segundo passo, podemos mostrar que Se você possui uma função de perda discreta, ou seja, não Lipschitz, como o 0-1 , você precisaria da VC-Dimension para limitar ainda mais a complexidade do Rademacher. No entanto, para funções L-lipschitz, como a perda de dobradiça, isso pode ser delimitado por queB

ZEZ2Bln(1/δ)2n,
δ
EZ2Rn(C),
Rn(C)λLR/n,

λindica o regularizador. Como para a perda de dobradiça e (prove com a desigualdade de Gauchy-Schwartz), isso simplifica ainda mais. Finalmente, reunindo todos os resultados, podemos vincular L=1B=1+λR
L(g^n)L(gc)2(1+λR)ln(1/δ)2n+4λLR/n
dkoehn
fonte