Método rápido para encontrar os melhores metaparameters do SVM (que é mais rápido que a pesquisa em grade)

Estou usando modelos SVM para fazer previsões de curto prazo de poluentes do ar. Para treinar um novo modelo, preciso encontrar metaparameters apropriados para um modelo SVM (refiro-me a C, gama e assim por diante).

A documentação do Libsvm (e muitos outros livros que li) sugere o uso da pesquisa em grade para encontrar esses parâmetros - então eu basicamente treino o modelo para cada combinação desses parâmetros em um determinado conjunto e escolho o melhor modelo.

Existe alguma maneira melhor de encontrar metaparameters ótimos (ou quase ótimos)? Para mim, é principalmente uma questão de tempo de computação - uma pesquisa em grade desse problema leva cerca de duas horas (depois de algumas otimizações).

Prós da pesquisa em grade:

• Pode ser facilmente paralelizado - se você tiver 20 CPUs, ele será executado 20 vezes mais rápido, paralelizar outros métodos é mais difícil.
• Você verifica grandes partes do espaço do metaparameter, portanto, se houver uma boa solução, você a encontrará.

O lado negativo da pesquisa em grade é que o tempo de execução cresce tão rápido quanto o produto do número de opções para cada parâmetro.

Aqui está uma entrada no blog de Alex Smola relacionada à sua pergunta

Aqui está uma citação:

[...] escolha, digamos 1000 pares (x, x ') aleatoriamente do seu conjunto de dados, calcule a distância de todos esses pares e calcule a mediana, o quantil 0,1 e o 0,9. Agora escolha λ para ser o inverso de qualquer um desses três números. Com um pouco de validação cruzada, você descobrirá qual dos três é o melhor. Na maioria dos casos, você não precisará pesquisar mais.

Eu não tentei isso sozinho, mas parece meio promissor.

Se você assumir que existe uma função relativamente suave subjacente à grade de parâmetros, há certas coisas que você pode fazer. Por exemplo, uma heurística simples é começar com uma grade muito grossa de parâmetros e, em seguida, usar uma grade mais fina em torno das melhores configurações de parâmetros da grade grossa.

Isso tende a funcionar muito bem na prática, com ressalvas, é claro. A primeira é que o espaço não é necessariamente tranquilo e pode haver ótimos locais . A grade grossa pode faltar completamente e você pode acabar com uma solução abaixo do ideal. Observe também que, se você tiver relativamente poucas amostras em seu conjunto de espera, poderá ter várias configurações de parâmetros com a mesma pontuação (erro ou qualquer métrica que esteja usando). Isso pode ser particularmente problemático se você estiver aprendendo em várias classes (por exemplo, usando o método one-versus-all ), e você tiver apenas alguns exemplos de cada classe em seu conjunto de espera. No entanto, sem recorrer a técnicas desagradáveis ​​de otimização não-linear, isso provavelmente serve como um bom ponto de partida.

Há um bom conjunto de referências aqui . No passado, adotei a abordagem de que você pode razoavelmente estimar uma boa variedade de hiperparâmetros do kernel inspecionando o kernel (por exemplo, no caso do kernel RBF, garantindo que o histograma dos valores do kernel ofereça uma boa distribuição de valores, em vez de ser inclinado para 0 ou 1 - e você pode fazer isso automaticamente também sem muito trabalho), o que significa que você pode diminuir o intervalo antes de iniciar. Em seguida, você pode concentrar sua pesquisa em outros parâmetros, como o parâmetro de regularização / capacidade. No entanto, é claro que isso só funciona com kernels pré-computados, embora você possa estimar isso em um subconjunto aleatório de pontos se não quiser usar kernels pré-computados, e acho que essa abordagem também seria boa.

Eu uso o recozimento simulado para pesquisar parâmetros.

O comportamento é governado por alguns parâmetros:

• k é a constante de Boltzmann.
• T_max é a sua temperatura inicial.
• T_min é o seu limite final.
• mu_T( μ) é o quanto você abaixa a temperatura ( T->T/μ)
• i é o número de iterações em cada temperatura
• zé um tamanho de etapa - você determina o que exatamente isso significa. Eu me movo aleatoriamente por dentro old*(1±z).

1. Tome um ponto de partida (conjunto de valores de parâmetros).
2. Consiga uma energia para ele (quão bem ele se encaixa nos seus dados; eu uso valores qui-quadrado).
3. Olhe em uma direção aleatória ("dê um passo").
   • Se a energia for menor que o seu ponto atual, vá para lá.
   • Se for maior, vá para lá com uma probabilidade p = e^{-(E_{i+1} - E_i)/(kT)}.
4. Repita, ocasionalmente, diminuindo T->T/μtodas as iiterações até você acertar T_min.

Brinque um pouco com os parâmetros e você poderá encontrar um conjunto que funcione bem e rápido.

E a Biblioteca Científica GNU inclui recozimento simulado.

Se alguém estiver interessado aqui, alguns dos meus pensamentos sobre o assunto:

• Como o @tdc sugeriu, estou fazendo uma pesquisa de grade grossa / fina. Isso introduz dois problemas:
  • Na maioria dos casos, receberei um bom conjunto de metaparameteres com parâmetros muito diferentes --- estou interpretando desta maneira que esses parâmetros são soluções ideais, mas para ter certeza de que devo verificar todas as grades finas perto de todos esses parâmetros bons ( isso levaria muito tempo), então, por enquanto, verifico apenas o conjunto de metaparâmetros da vizinhança das apostas.
  • Na maioria dos casos, a pesquisa fina não aumenta o desempenho do SVM (isso pode ser devido ao fato de eu estar verificando apenas a vizinhança do melhor ponto da grade grossa.
• Eu observei o comportamento de que a maior parte do tempo de computação é gasta em conjuntos de metaparômetros que não produzirão bons resultados, por exemplo: a maioria dos conjuntos de metaparâmetros será computada em menos de 15 segundos (e a maioria deles tem taxa de erro de 15%), e alguns levam 15 minutos ( e a maioria delas tem taxas de erro maiores que 100%). Portanto, ao fazer a pesquisa na grade, eu mato pontos que levam mais de 30 segundos para calcular e presumo que eles tenham um erro infinito.
• Eu uso o multiprocessamento (que é bastante simples)

$\sigma$