¿Las matrices de kernel RBF tienden a estar mal acondicionadas?

Uso la función de kernel RBF para implementar un algoritmo de aprendizaje automático basado en kernel (KLPP), la matriz de kernel resultante está extremadamente mal condicionado. El número de condición de la norma L2 viene $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}$

¿Hay alguna manera de hacerlo bien acondicionado? Supongo que el parámetro necesita ser ajustado, pero no sé exactamente cómo. $\sigma$

¡Gracias!

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

bueno, si haces

σ_{m}

$\sigma_m$ más pequeño, mejorarás el número de condición.

user189035

Respuestas:

Reducir el ancho del núcleo $\sigma_m$ generalmente reducirá el número de condición.

Sin embargo, las matrices de kernel pueden volverse singulares, o casi singulares, para cualquier función base o distribución de puntos, siempre que las funciones básicas se superpongan. La razón de esto es bastante simple:

$K$ $\det(K)$
Intercambiar dos puntos y en su interpolación es equivalente a intercambiar dos filas en , suponiendo que sus puntos de prueba permanezcan constantes. $x_i$ $x_j$ $K$
Intercambiar dos filas en una matriz cambia el signo de su determinante.

Ahora imagine elegir dos puntos y y lentamente para que cambien de lugar. Al hacer esto, el determinante de cambiará de signo, convirtiéndose en cero en algún punto intermedio. En este punto, es, por definición, singular. $x_i$ $x_j$ $K$ $K$

Pedro
fuente

¿Las matrices K no son simétricas: el intercambio de dos puntos intercambia filas y columnas?

denis

@Denis Ese es solo el caso si sus nodos y puntos de prueba son iguales y mueve ambos. Por eso, en la segunda viñeta, escribí "suponiendo que sus puntos de prueba permanezcan constantes".

Pedro

la matriz del núcleo de los gaussianos (la pregunta del OP) son positivos semi-definidos de todos modos?

denis

@Denis: Nuevamente, esta es una cuestión de cómo define su problema de interpolación RBF. Considere el caso más general en el que tiene RBFs centra en los puntos , , y desea reducir al mínimo la interpolación en los puntos , . El ejemplo del póster supone que y . Si inicialmente configuramos y , y luego simplemente movemos , podemos generar 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

Un par de sugerencias:

Elija la distancia promedio | aleatorio - más cercano . (A aproximación baratas para puntos distribuidos de manera uniforme en el cubo unidad en , es de 0,5 / .) Queremos $\sigma \sim$ $x$ $x_i$ $N$ $\mathbb{R}^d, d\ 2 .. 5$ $N^{1/d}$
a ser grande paracerca de, pequeño para ruido de fondo; trazar eso por unos pocosazar. $\phi( |x - x_i| )$ $x_i$ $x$ $x$
Desplace lejos de 0, , o menos; es decir, regularizar. $K$ $K \to K + \lambda I$ $\lambda \sim 10^{-6}$
Mire los pesos de la resolución . Si algunos siguen siendo enormes (independientemente del número de condición), eso tendería a confirmar a Boyd (abajo) que el RBF gaussiano es fundamentalmente débil. $(K + \lambda I) w = f$

(Una alternativa a RBF es la ponderación de distancia inversa, IDW. Tiene la ventaja de autoescalar, lo mismo para las distancias más cercanas 1 2 3 $\dots$ que para 100 200 300 También encuentro la opción explícita del usuario de , el número de vecinos cercanos a considerar, más claro que la búsqueda de cuadrícula en .) $\dots$ $Nnear$ $\sigma, \lambda$

John P. Boyd, La inutilidad de la Transformada rápida de Gauss para sumar series de funciones de base radial gaussianas , dice

el interpolante gaussiano RBF está mal acondicionado para la mayoría de las series en el sentido de que el interpolante es la pequeña diferencia de términos con coeficientes exponencialmente grandes.

Espero que esto ayude; Por favor comparte tu experiencia.

denis
fuente