Les matrices du noyau RBF ont-elles tendance à être mal conditionnées?

J'utilise la fonction de noyau RBF pour implémenter un algorithme d'apprentissage machine basé sur le noyau (KLPP), la matrice de noyau résultante $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)$ est extrêmement mal conditionnée.Le nombre de conditions de la norme L2 est de

10^{17} - 10^{64}

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

Existe-t-il un moyen de le rendre bien conditionné? Je suppose que le paramètre $\sigma$ doit être réglé, mais je ne sais pas exactement comment.

Merci!

linear-algebra machine-learning interpolation support-vector-machines ZeyuHu
la source

eh bien, si vous faites

σ_{m}

$\sigma_m$ plus petit, vous améliorez le nombre de conditions.

user189035

Réponses:

$\sigma_m$

Cependant, les matrices du noyau peuvent devenir singulières, ou proches du singulier, pour toute fonction de base ou distribution de points, à condition que les fonctions de base se chevauchent. La raison en est assez simple:

$K$ $\det(K)$
Échanger deux points et dans votre interpolation équivaut à échanger deux lignes en , en supposant que vos points d'essai restent constants. $x_i$ $x_j$ $K$
L'échange de deux lignes dans une matrice change le signe de son déterminant.

Imaginez maintenant choisir deux points et et les faire pivoter lentement pour qu'ils changent de place. Ce faisant, le déterminant de changera de signe, devenant nul à un moment donné entre les deux. À ce stade, est, par définition, singulier. $x_i$ $x_j$ $K$ $K$

Pedro
la source

Les matrices K ne sont-elles pas symétriques - l'échange de deux points permute les lignes et les colonnes?

denis

@Denis Ce n'est le cas que si vos nœuds et points d'essai sont identiques et que vous vous déplacez tous les deux. C'est pourquoi, dans la deuxième puce, j'ai écrit "en supposant que vos points d'essai restent constants".

Pedro

la matrice de noyau des gaussiens (la question du PO) est-elle positive semi-définie de toute façon?

denis

@Denis: Encore une fois, il s'agit de savoir comment définir votre problème d'interpolation RBF. Considérons le cas le plus général où vous avez RBFs centrée sur les points , , et que vous voulez minimiser l'interpolation aux points , . L'exemple de l'affiche suppose et . Si nous définissons initialement et , puis déplaçons simplement , nous pouvons générer trivialement singulier .

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

Quelques suggestions:

Choisissez la distance moyenne | aléatoire - plus proche . (Une approximation bon marché pour points uniformément répartis dans le cube unitaire dans , est 0,5 / .) Nous voulons être grand pour près de , petit pour le bruit de fond; tracer cela pour quelques aléatoires . $\sigma \sim$ $x$ $x_i$ $N$ $\mathbb{R}^d, d\ 2 .. 5$ $N^{1/d}$
$\phi( |x - x_i| )$ $x_i$ $x$ $x$
Décaler de 0, , ou plus; c'est-à-dire régulariser. $K$ $K \to K + \lambda I$ $\lambda \sim 10^{-6}$
Regardez les poids de la résolution . Si certains sont encore énormes (indépendamment du numéro de condition), cela tendrait à confirmer Boyd (ci-dessous) que le RBF gaussien est fondamentalement faible. $(K + \lambda I) w = f$

(Une alternative à RBF est la pondération de distance inverse, IDW. Elle a l'avantage de la mise à l'échelle automatique, la même pour les distances les plus proches 1 2 3 que pour 100 200 300 . Je trouve également le choix explicite de , le nombre de voisins proches à considérer, plus clair que la recherche dans la grille sur .) $\dots$ $\dots$ $Nnear$ $\sigma, \lambda$

John P. Boyd, L'inutilité de la transformation de Gauss rapide pour additionner des séries de fonctions de base radiales gaussiennes , dit

l'interpolant gaussien RBF est mal conditionné pour la plupart des séries dans le sens où l'interpolant est la petite différence de termes avec des coefficients exponentiellement grands.

J'espère que cela t'aides; veuillez partager votre expérience.

denis
la source