Quais métodos existem para ajustar os hiperparâmetros SVM do kernel do gráfico gráfico?

10

Eu tenho alguns dados que existem em um gráfico . Os vértices pertencem a uma das duas classes e estou interessado em treinar um SVM para distinguir entre as duas classes. Um kernel apropriado para isso é o kernel de difusão , onde é o Laplaciano de e é um parâmetro de ajuste.G=(V,E)yi{1,1}K=exp(βL),LGβ

Ajustar o SVM requer a seleção de hiperparâmetros, portanto, tenho que ajustarConvencionalmente, usamos validação cruzada para esse problema, mas isso não parece apropriado aqui, já que a omissão de um vértice de altera o gráfico inteiro, possivelmente aumentando o número de componentes conectados! Se o número de componentes conectados mudar, alguns vértices se tornam inacessíveis a outros, e somos confrontados com um conjunto de dados muito diferente do que começamos. Ou seja, não apenas estamos perdendo o vértice removido , mas também estamos perdendo informações sobre todos os outros vértices no gráfico que estavam adjacentes a esse vértice.θ=(β,C).iGij

A noção básica de validação cruzada é que gostaríamos de aproximar o desempenho do modelo quando for apresentado novos dados. Em problemas padrão, a omissão de alguns de seus dados para teste não altera os valores dos dados de treinamento restantes. No entanto, no caso de dados gráficos, não está claro o que significa para o modelo ver dados "novos" na configuração CV. A omissão de vértices ou arestas tem o potencial de alterar completamente os dados. Por exemplo, imagine um gráfico que é um gráfico , no qual um vértice tem arestas em vértices, e todos os outros vértices têm 1 aresta. Omitindo o vértice central para construir os dados de treinamentoS=(VS,ES)kkkSdesconectará completamente o gráfico e a matriz do kernel será diagonal! Mas é claro, será possível treinar um modelo nesses dados de treinamento fornecidos em . O que é menos claro é o que significa testar o desempenho fora da amostra do modelo resultante. Alguém recalcula a matriz do kernel para e fornece isso para fazer previsões?SS

Ou, como alternativa, começa-se computando a matriz do kernel de em sua totalidade e omite linhas e colunas conforme necessário para produzir a matriz do kernel usada para estimar o SVM? Isso apresenta seus próprios problemas conceituais, uma vez que a inclusão do nó central em significa que todo vértice é acessível a partir de qualquer outro vértice, e a matriz do kernel é densa. Essa inclusão significa que há vazamento de informações entre dobras e influencia a saída da validação cruzada? Por um lado, os dados sobre os nós centrais omitidos ainda estão presentes, pois o nó central omitido faz o gráfico conectado. Por outro lado, nada sabemos sobre os rótulosSS y dos nós omitidos, para que possamos ficar à vontade com a obtenção de estimativas fora da amostra razoavelmente imparciais da realização de CV dessa maneira.

Como se seleciona hiperparâmetros para problemas desse tipo? O CV é imperfeito, mas aceitável, ou precisamos de métodos especializados? O ajuste do hiperparâmetro é mesmo possível no meu contexto?

Sycorax diz restabelecer Monica
fonte
Procure extensão fora da amostra para métodos espectrais. Eu apliquei algumas das técnicas para classificação de imagens em minha tese (olhando para trás agora, eu faria isso de maneira diferente). Os resultados foram interessantes, mas os modelos em si eram bastante frágeis e não eram fáceis de afinar.
Vladislavs Dovgalecs
@xeon Alguma recomendação de onde começar a olhar para esta literatura?
Sycorax diz Reinstate Monica

Respostas:

3

Isenção de responsabilidade: eu não estou muito familiarizado com os kernels gráficos, portanto, essa resposta pode ser baseada em suposições erradas. Concordo que a omissão de vértices durante o cálculo da matriz do kernel é subótima. Dito isto, não tenho certeza de que a validação cruzada seja necessariamente problemática. O seu contexto de aprendizagem é transdução ou indução?

No geral, não estou convencido de que calcular a matriz do kernel para um determinado base em todos os dados (ou seja, treinar e testar) necessariamente crie um vazamento de informações. Se a computação do kernel com base em todos os dados estiver correta, você poderá treinar modelos em uma configuração cv típica, usando os blocos relevantes da matriz completa do kernel (pré-computada) para treinamento / teste.β

Essa abordagem permite otimizar conjuntamente e , por exemplo, através de bibliotecas como Optunity , onde é usado para calcular o kernel com base em todos os dados e é usado para treinar modelos exclusivamente nas dobras de treinamento.βCβC

Marc Claesen
fonte
Marc, obrigado pela atenção. Meu problema é indutivo. Meu instinto é que você esteja correto e calculemos a matriz completa do kernel para todos os dados e, em seguida, omitimos linhas e colunas conforme necessário para produzir o kernel com CV. Você estaria ciente de alguma referência a esse efeito?
Sycorax diz Restabelecer Monica
Não imediatamente, mas tenho alguns colegas trabalhando em problemas comparáveis ​​(cluster espectral do kernel) que posso perguntar. Talvez eles tenham referências e / ou idéias melhores. Será atualizado quando eu souber mais.
Marc Claesen