As matrizes do kernel do RBF tendem a estar mal condicionadas?

Eu uso a função RBF do kernel para implementar um algoritmo de aprendizado de máquina baseado em kernel (KLPP), a matriz do kernel resultante mostra-se extremamente mal-condicionado.O número da condição da norma L2 vem $K$

K (i, j) = \exp (\frac{- (x_{i} - x_{j})^{2}}{σ_{m}^{2}})

$K(i,j)= \exp\left({\frac{-(x_{i}-x_{j})^2}{ \sigma_{m}^2}}\right)$

10^{17} - 10^{64}

$10^{17}-10^{64}$

Existe alguma maneira de torná-lo bem condicionado? Eu acho que o parâmetro precisa ser ajustado, mas não sei exatamente. $\sigma$

Obrigado!

linear-algebra machine-learning interpolation support-vector-machines ZeyuHu
fonte

bem, se você melhorará o número da condição.

σ_{m}

$\sigma_m$

precisa saber é o seguinte

Respostas:

Reduzir a largura do kernel geralmente reduz o número da condição. $\sigma_m$

No entanto, as matrizes do kernel podem se tornar singulares, ou quase singulares, para qualquer função básica ou distribuição de pontos, desde que as funções básicas se sobreponham. A razão para isso é realmente bastante simples:

A matriz do kernel é singular quando seu determinante é zero. $K$ $\det(K)$
Trocar dois pontos e na sua interpolação é equivalente a trocar duas linhas em , assumindo que seus pontos de teste permaneçam constantes. $x_i$ $x_j$ $K$
Trocar duas linhas em uma matriz alterna o sinal de seu determinante.

Agora imagine escolher dois pontos e e -los lentamente para que eles mudem de lugar. Enquanto isso, o determinante de trocará de sinal, tornando-se zero em algum ponto intermediário. Nesse ponto, é, por definição, singular. $x_i$ $x_j$ $K$ $K$

Pedro
fonte

As matrizes K não são simétricas - trocar dois pontos troca linhas e colunas?

Denis13

@ Denis Esse é apenas o caso se seus nós e pontos de teste forem os mesmos e você mover os dois. É por isso que, na segunda bala, escrevi "assumindo que seus pontos de teste permanecem constantes".

Pedro Pedro

a matriz do kernel dos gaussianos (a pergunta do OP) é semidefinida positiva de qualquer maneira?

Denis

@ Denis: Novamente, esta é uma questão de como você define seu problema de interpolação RBF. Considere o caso mais geral, onde você tem RBFs centrada nos pontos , , e que pretende minimizar a interpolação nos pontos , . O exemplo do pôster assume e . Se inicialmente configuramos e e depois movemos o , podemos gerar trivialmente singular .

N

$N$

x_{i}

$x_i$

i = 1 \dots N

$i=1\dots N$

M

$M$

ξ_{j}

$\xi_j$

j = 1 \dots M

$j=1\dots M$

M = N

$M=N$

ξ_{j} = x_{i}

$\xi_j=x_i$

M \leftarrow N

$M\leftarrow N$

ξ_{j} \leftarrow x_{i}

$\xi_j \leftarrow x_i$

x_{i}

$x_i$

K

$K$

Pedro

Algumas sugestões:

Escolha a distância média | aleatório - mais próximo . (Uma aproximação barata para pontos distribuídos uniformemente no cubo da unidade em é 0,5 / .) Queremos ser grande para próximo a , pequeno para ruído de fundo; traçar isso por alguns aleatórios . $\sigma \sim$ $x$ $x_i$ $N$ $\mathbb{R}^d, d\ 2 .. 5$ $N^{1/d}$
$\phi( |x - x_i| )$ $x_i$ $x$ $x$
Desloque longe de 0, , ou mais; isto é, regularize. $K$ $K \to K + \lambda I$ $\lambda \sim 10^{-6}$
Observe os pesos da solução . Se alguns ainda são enormes (independentemente do número da condição), isso tenderia a confirmar Boyd (abaixo) que a RBF gaussiana é fundamentalmente fraca. $(K + \lambda I) w = f$

(Uma alternativa ao RBF é a ponderação por distância inversa, IDW. Ela tem a vantagem do dimensionamento automático, o mesmo para as distâncias mais próximas 1 2 3 e para 100 200 300 Também acho a escolha explícita do usuário por , o número de vizinhos próximos a considerar, mais clara que a pesquisa em grade em .) $\dots$ $\dots$ $Nnear$ $\sigma, \lambda$

John P. Boyd, A inutilidade da Fast Gauss Transform para somar séries de funções de base radial gaussiana , diz

o interpolante gaussiano de RBF está mal condicionado para a maioria das séries, no sentido de que o interpolante é a pequena diferença de termos com coeficientes exponencialmente grandes.

Espero que isto ajude; por favor, compartilhe sua experiência.

denis
fonte