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 - w ∗ b ∗ 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:
Estamos interessados na capacidade de generalização desta máquina.
Dimensão VC de Vapnik-Chervonenkis :
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:
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:
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.
Outro resultado que aparece em (Vapnik, 2000), p.133, é o seguinte. Supondo novamente que, para todo , e deixando e , definimos como igual a:
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:
No entanto, em (Hastie, Tibshirani e Friedman, 2009), p.438, um resultado muito semelhante é encontrado:
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 :
Vapnik, VN (1998). Statistical Learning Theory , 1ª edição, John Wiley & Sons
Vapnik, VN (2000). A natureza da teoria estatística da aprendizagem , 2ª edição, Springer
fonte
Respostas:
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)
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
O erro de estimativa pode ser decomposto ainda mais com Agora, isso pode ser delimitado por duas etapas:Z
Limite usando McDiarmid desigualdadeZ−EZ
Limite com a complexidade RademacherEZ Rn(C)=Esupg∈C|1/n∑ni=1l(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
fonte