introduction

L'autre jour, j'ai lu le chapitre 3 de l'introduction du professeur Kenji Fukumizu à la méthode du noyau lors d'un séminaire. Puisqu'il a été écrit à la main lors du séminaire, je voudrais réorganiser le matériel de présentation et donner une brève introduction à la méthode du noyau. Enfin (à part la théorie détaillée), nous implémenterons l'analyse des composants principaux du noyau en python. Puisque ma gamme de présentation était le noyau à valeur positive dans la première moitié et la partie finale de l'implémentation, il y a quelques omissions majeures au milieu, mais je ne pense pas qu'il y ait un gros problème.

Remarque ・ L'atmosphère est plus importante que la théorie. ・ Les éléments numérotés sont les mêmes que les numéros du livre de Fukumizu-sensei.

Connaissances préalables ・ Statistiques simples ·algèbre linéaire ・ Analyse fonctionnelle (théorie de l'espace de Hilbert)

table des matières

[Vue d'ensemble de la méthode du noyau](# Vue d'ensemble de la méthode du noyau)
[Noyau à valeur régulière](Noyau à valeur régulière) ・ [Espace de ceinture de colline nucléaire régénéré](# Espace de ceinture de colline nucléaire régénéré)
[Analyse en composantes principales du noyau (Kernel PCA)](# Analyse en composantes principales du noyau)
[Analyse de corrélation canonique du noyau (Kernel CCA)](# Analyse de corrélation canonique du noyau) ← Ajoutez si vous en avez envie.

(Beaucoup de gens peuvent se demander pourquoi ils ne prennent pas en charge les machines vectorielles, mais le séminaire n'est pas allé aussi loin. Je pense que je le lirai moi-même si j'ai le temps.)

Vue d'ensemble de la méthode du noyau

Prenons par exemple l'analyse des composants principaux. N éléments de $ m $ dimension $ X_1, ..., X_N \ in \ chi = \ mathbb {R} ^ m $ Recherchez $ u $ qui a la p-ième plus grande distribution de T} X $. C'est ce qu'on appelle le p-ième composant principal, et la compression de dimension et l'élimination du bruit peuvent être effectuées en prenant un axe inférieur à $ m $. Si vous écrivez ceci dans une formule

\frac{1}{N}\sum_{i=1}^{N}\left\{u^{\mathsf{T}}X_{i}-\frac{1}{N}\left(\sum_{j=1}^{N}u^{\mathsf{T}}X_{j}\right)\right\}^{2}

Est le plus grand\\|u\\|=1Il sera déplacé pour satisfaire. Cependant, cela ne permet pas l'extraction d'entités non linéaires car il n'effectue que des calculs linéaires. Par conséquent, les données avec une fonction non linéaireX_iEst envoyé dans un autre espace pour effectuer des calculs non linéaires.

Le noyau du calcul ci-dessus est le produit interne de $ u $ et $ X $. Dans l'exemple ci-dessus, nous pensions à $ \ mathbb {R} ^ m $, donc le produit interne normal $ \ langle u, X \ rangle_ {\ mathbb {R} ^ m} = u ^ \ mathsf {T} X $ Ca a été décidé. Cela peut être calculé même si les données $ X_i $ sont envoyées dans un autre espace $ H $ par le mappage non linéaire $ \ phi: \ chi → H $, si le produit interne est déterminé dans cet espace. Dans ce cas, le produit interne de $ u $ et $ X $ $ \ langle u, X \ rangle_ {\ mathbb {R} ^ m} $ est utilisé à la place de $ f \ dans H $ et $ \ langle f Cela signifie que l'analyse de la composante principale doit être effectuée comme suit: \ phi (X) \ rangle_H $.

En d'autres termes, la méthode du noyau consiste à utiliser le mappage $ \ phi $ pour passer à un autre espace et réfléchir au problème d'origine dans cet espace. Dans la méthode conventionnelle, il était courant d'effectuer des opérations non linéaires en utilisant le développement $ (X, Y, Z ...) \ rightarrow (X ^ 2, Y ^ 2, Z ^ 2, XY ...) $. Cependant, il y avait un problème en ce que la dimension des données à traiter augmentait avec le changement des temps et la quantité de calcul devenait énorme. La méthode du noyau utilise une fonction du noyau qui calcule efficacement le produit interne de l'espace envoyé par le mappage de caractéristiques $ \ phi $, permettant des opérations non linéaires avec un montant de calcul qui n'est pas très différent des problèmes ordinaires.

À partir de ce qui précède, l'objectif actuel est de définir avec succès le mappage de caractéristiques $ \ phi $ et l'espace $ H $.

Noyau à valeur positive

Soit l'espace de données $ \ chi $ et définissez le mappage de caractéristiques $ \ phi $ comme $ \ phi: \ chi → H $. Où $ H $ est un espace produit interne avec un produit interne $ \ langle ·, · \ rangle_H $.

Ce serait bien si le produit interne pouvait être facilement calculé avec une fonction $ k (x, y) = \ langle \ phi (x), \ phi (y) \ rangle_H $. En faisant cela, vous pouvez afficher seulement $ k $ sans considérer la représentation directe de $ \ phi $ et $ H $ (qui sera traitée dans l'exemple concret décrit plus loin), et le coût du calcul est $ \ phi $. Vous pouvez voir que cela ne dépend pas de.

Ici, nous définissons un noyau à valeur positive et considérons les propriétés qu'il satisfait.

Def Noyau de valeur positive

Lorsque la fonction $ k: \ chi × \ chi → \ mathbb {R} $ satisfait les deux propriétés suivantes, $ k $ est appelé un noyau à valeur positive sur $ \ chi $.

-Symétrie: $ k (x, y) = k (y, x) $ pour tout $ x, y \ in \ chi $ · Valeur positive: $ \ sum_ {i, j pour tout $ n \ in \ mathbb {N}, x_1 ... x_N \ in \ chi, c_1 ... c_N \ in \ mathbb {R} $ = 1} ^ {n} c_ic_jk (x_i, x_j) \ geq0 $

La canonique, en supposant la symétrie, correspond à la définition d'une valeur semi-rectangulaire dans une matrice carrée $ N × N $ telle que la composante $ ij $ est $ k (x_i, x_j) . La raison d'écrire une valeur positive ici est que la définition ci-dessus est appelée valeur régulière par convention. 　 Prop2.1 Les propriétés suivantes sont valables pour le noyau à valeur positive. (1)k(x,x)\geq0 \quad(\forall x \in \chi)$ (2)|k(x,y)| \leq k(x,x)k(y,y) \quad(\forall x,y \in \chi) (3) Pour \ Upsilon, qui est un sous-ensemble de $ \ chi, la limitation de \ Upsilon × \ Upsilon de k est un noyau de valeur positive sur \ Upsilon. $

proof(2)

A = \left(\begin{matrix}
 k(x,x) & k(x,y)\\k(x,y) & k(y,y) \end{matrix}
 \right)

Est une matrice symétrique à valeur fixe semi-positive, et toutes les valeurs propres sont réelles et non négatives, donc si vous considérez la formule de la matrice en diagonale, $ det (A) \ geq0 $. De même, comme défini, l'expression de la matrice peut être calculée et l'inégalité qui est non négative peut être transformée.

Prop2.2 Le noyau de valeur positive est fermé pour les opérations suivantes: Soit $ k_i $ un noyau de valeur positive, (1) $ ak_i + bk_j $ pour $ a, b \ in \ mathbb {R_ {\ geq0}} $ (2)k_ik_j (3)\lim_{n \to \infty}k_n

proof:(2) Puisqu'il suffit que la matrice $ N × N $ dont la composante est $ k_ik_j $ soit une valeur semi-fixe, considérons le produit Adamal de deux matrices dont les composantes sont $ k_i et k_j $, et diagonalisent l'une des matrices à une valeur positive. Remplacer dans la formule de définition du sexe.

Prop2.6 Soit $ V un espace produit interne avec un produit interne \ langle ・, ・ \ rangle_V $. Étant donné un mapping $ \ phi: \ chi \ rightarrow V, x \ mapsto \ phi (x) $, $ k (x, y) = \ angle \ phi (x), \ phi (y) \ rangle_V $ Est un noyau à valeur positive.

proof Il peut être calculé selon la définition du noyau de valeur positive.

Je voulais que le mappage de fonctionnalités $ \ phi $ satisfasse ces propriétés. Si vous définissez correctement $ V $ et préparez un mappage, vous devriez pouvoir le calculer facilement avec la valeur positive kernel $ k $. Cependant, en fait, si $ k $ est défini, $ V $ est déterminé de manière unique, et comme mentionné ci-dessus, l'expression directe de $ \ phi $ n'est pas nécessaire dans le calcul réel, donc la valeur positive du noyau $ k $ doit être déterminée. Je comprends ça.

Espace nucléaire régénéré de la ceinture de collines

Ici, nous confirmons qu'il existe une correspondance biunivoque entre le noyau de valeur positive $ k $ et l'espace produit interne $ H $ qui a certaines propriétés.

Def Regeneration Nuclear Hill Belt Space

L'espace produit interne complet $ H $ est appelé l'espace de Hilbert. Un espace de ceinture de collines $ H $ constitué de fonctions sur $ \ chi $ avec $ \ chi $ comme ensemble et satisfaisant les propriétés suivantes est appelé un espace de ceinture de collines nucléaire régénéré. -Jouabilité: $ \ forall x \ in \ chi, \ forall f \ in H, \ exists k_x \ in H s.t. \ langle f, k_x \ rangle_H = f (x) $

Pour $ k_x \ dans H $ défini ci-dessus, le noyau $ k $ déterminé par $ k (y, x) = k_x (y) $ est appelé le noyau de régénération de $ H $.

prop2.7 Noyaux régénérés sur $ \ chi $ Noyaux régénérés dans l'espace de Hilbert $ H $ $ k $ est un noyau de valeur positive sur $ \ chi $, et les noyaux régénérés dans $ H $ sont uniques.

proof Puisqu'il peut être transformé en $ k (x, y) = k_y (x) = \ langle k_y, k_x \ rangle_H = \ langle k (・, y), k (・, x) \ rangle_H $ Vous pouvez voir $ \ sum_ {i, j = 1} ^ {n} c_ic_jk (x_i, x_j) \ geq0 $. L'unicité peut être montrée en utilisant $ k et \ override {k} $ comme noyaux régénérés sur $ H $ et en utilisant la symétrie et que chacun est un noyau régénéré.

prop2.8 $||k(・,x)||_H=\sqrt{k(x,x)} $

proof Le carré du côté gauche peut être calculé en utilisant la reproductibilité.

prop2.11 Pour un noyau de valeur positive $ k $ sur l'ensemble $ \ chi $, un espace nucléaire de Hilbert régénéré sur $ \ chi $ qui satisfait les trois propriétés suivantes existe de manière unique. (1) $ \ forall x \ in \ chi, k (・, x) \ in H $ (2) Le sous-espace (paquet linéaire) étiré par $ k (・, x) (x \ in \ chi) $ est dense dans $ H $ (3) $ k $ est le noyau de régénération de $ H $

Lorsque prop2.7 et prop2.11 sont combinés, on peut voir qu'il existe une correspondance biunivoque entre le noyau de valeur positive et l'espace de Hilbert nucléaire régénéré.

Ici, si le mappage de caractéristiques $ \ phi: \ chi → H $ est défini comme $ x \ mapsto k (・, x) $, si la reproductibilité est utilisée,

\begin{align}
&\begin{split}
\langle\phi(x),\phi(y)\rangle_H &= \langle k(・,x), k(・,y)\rangle_H \\
&= \langle k_x, k_y \rangle_H \\
&= k_x(y) \\
&= k(y,x) \\
&= k(x,y)
 \end{split}\\
\end{align}

Donc, j'ai trouvé que le produit interne que je voulais calculer pouvait être calculé avec la valeur positive kernel $ k $.

Voici quelques exemples couramment utilisés de noyaux à valeur positive.

-Noyau linéaire (produit interne euclidien normal)

k_0(x,y) =　x^\mathsf{T} y

・ Type exponentiel

k_E(x,y)=exp(\beta x^\mathsf{T} y) \ (\beta>0)

・ Noyau de Gauss

k_G(x,y) =exp \left(-\frac{\|x-y\|^2}{2 \sigma^2} \right)

Analyse des composants principaux du noyau

J'ai brièvement présenté la théorie, c'est donc un exemple d'application. Analyse en composantes principales normaleuPour augmenter la dispersion lorsqu'elle est projetée par||u||=1Était à demander.

\frac{1}{N}\sum_{i=1}^{N}\left\{u^{\mathsf{T}}X_{i}-\frac{1}{N}\left(\sum_{j=1}^{N}u^{\mathsf{T}}X_{j}\right)\right\}^{2}

Mappage des fonctionnalités dans l'analyse des composants principaux du noyau\phi:\chi→HDonnées utilisantX_iÀHVoler,HProduit intérieur\langle ・,・\rangle_HÀ使って計算すれば非線形な特徴À捉えることができます。つまり以下の式À最大化するf (||f||_H=1)À求めることになります。

\frac{1}{N}\sum_{i=1}^{N}\left\{\langle f,\phi\left(X_{i}\right)\rangle_{H}\ -\ \frac{1}{N}\left(\sum_{j=1}^{N}\left\langle f,\ \phi\left(X_{j}\right)\right\rangle_H \right)\right\}^{2}

Si vous le centrez avec $ \ tilde {\ phi} (X_i) = \ phi (X_i) - \ frac {1} {N} \ sum_ {i = j} ^ {N} \ phi (X_j) $

\frac{1}{N}\sum_{i=1}^{N}\left(\langle f,\ \tilde{\phi}\left(X_{i}\right)\rangle_{H} \right)^{2}

Il s'avère que vous devriez penser à $ f $ qui maximise. $ ||f||_{H}=1$Parce que c'estfEst\tilde{\phi} \left(X_{1}\right)...\tilde{\phi} \left(X_{N}\right)Coller avecHSous-espace de

Span\left\{\tilde{\phi}\left(X_{1}\right),...,\tilde{\phi}\left(X_{N}\right)\right\} \subset H

Vous pouvez le considérer comme un élément de. Donc,

f = \sum_{i=1}^{N}\alpha_{i}\tilde{\phi}\left(X_{i}\right)

Peut être exprimé comme. En d'autres termes, le produit interne $ \ angle f, \ tilde {\ phi} (X_ {i}) \ rangle_H $ est $ \ langle \ tilte {\ phi} (X_i), \ tilde {\ phi} (X_j) \ rangle Il peut être représenté par une connexion linéaire de $, et si la centralisation de $ \ tilde {\ phi} $ est prise, c'est $ k (X_i, X_j) = \ langle \ phi (X_i), \ phi (X_j) \ rangle $. Il peut être représenté par une combinaison linéaire de k $, et le coefficient peut également être représenté en utilisant $ \ alpha $. Par conséquent, en trouvant $ \ alpha $, $ f $ est déterminé comme une fonction sur $ H $, et la maximisation peut être obtenue.

Ici pour la simplicité

\tilde{k}(X_i,X_j)= \langle \tilde{\phi}(X_i), \tilde{\phi}(X_j) \rangle_H

Soit $ \ tilde {K} $ la matrice qui a $ \ tilde {k} (X_i, X_j) $ comme composant $ ij $. C'est ce qu'on appelle la matrice gramme centralisée.

Le problème à maximiser peut être transformé comme suit et peut être réduit au problème généralisé des valeurs propres.

\begin{align}
&\begin{split}

\frac{1}{N}\sum_{i=1}^{N}\left(\langle f,\ \tilde{\phi}\left(X_{i}\right)\rangle_{H} \right)^{2} 

&= \frac{1}{N}\sum_{i=1}^{N}\left\{\sum_{j=1}^{N}\alpha_j\tilde{k}(X_j,X_i)\right\}^{2}\\
&=\frac{1}{N}\sum_{i=1}^{N}\left\{\sum_{j=1}^{N}\sum_{k=1}^{N}\alpha_{j}\alpha_{k}\tilde{k}(X_j,X_i)\tilde{k}(X_k,X_i)\right\} \\
&= \frac{1}{N}\sum_{j=1}^{N}\sum_{k=1}^{N}\left\{\alpha_{j}\alpha_{k}\sum_{i=1}^{N}\tilde{k}(X_j,X_i)\tilde{k}(X_i,X_k)\right\}\\
&= \frac{1}{N}\sum_{j=1}^{N}\sum_{k=1}^{N}\left(\alpha_{j}\alpha_{k}\tilde{K}_{jk}^2\right)\\
&=\frac{1}{N}\alpha^\mathsf{T} \tilde{K}^2 \alpha\\
\end{split}\\

&\begin{split}
||f||_H &= \langle f, f \rangle \\
&= \langle \sum_{i=1}^{N}\alpha_{i}\tilde{\phi}\left(X_{i}\right),  \sum_{j=1}^{N}\alpha_{j}\tilde{\phi}\left(X_{j}\right) \rangle \\
&= \sum_{i=1}^{N}\sum_{j=1}^{N}\alpha_i \alpha_j \langle \tilde{\phi}(X_i), \tilde{\phi}(X_j) \rangle \\
&= \alpha^\mathsf{T} \tilde{K} \alpha
\end{split}\\ 
\end{align}

D'après ce qui précède, le problème de maximisation est

\newcommand{\argmax}{\mathop{\rm arg~max}\limits}

\argmax_{\alpha \in \mathbb{R}^N} \, \alpha^\mathsf{T} \tilde{K}^2 \alpha \ \ s.t. \ \alpha^\mathsf{T} \tilde{K} \alpha = 1

Puisque $ \ tilde {K} $ est une matrice symétrique à valeur constante semi-régulière, lorsque la décomposition en valeurs propres (diagonalisation) est effectuée, une matrice unitaire $ U $ dans laquelle $ N $ vecteurs verticaux $ u ^ i $ sont disposés et une matrice diagonale $ En utilisant \ Lambda = diag (\ lambda_1, ..., \ lambda_N) \ (\ lambda_1 \ geq \ lambda_2 \ geq ... \ geq \ lambda_N \ geq 0) $,

\tilde{K} = U \Lambda U^{*}

Peut être démonté. $ \ Tilde {K} ^ 2 = U \ Lambda ^ 2 U ^ {*} $

\alpha^\mathsf{T} \tilde{K}^2 \alpha = \sum_{i=1}^{N} (\alpha^\mathsf{T} u^i)^2 \lambda_i^2

Par conséquent, en considérant $ \ lambda_1 \ geq \ lambda_2 \ geq ... \ geq \ lambda_N \ geq 0 $, le p-ième plus grand $ \ alpha $ est à $ \ alpha \ parallel u ^ p $. La longueur doit être ajustée pour satisfaire $ \ alpha ^ \ mathsf {T} \ tilde {K} \ alpha = 1 $. Si vous mettez $ \ alpha = c_p u ^ p $, sachez que $ u ^ i $ est un vecteur colonne d'une matrice unitaire.

\begin{align}
&\begin{split}
\alpha^\mathsf{T} \tilde{K} \alpha &= \sum_{i=1}^{N} (c_p u^{p^{\mathsf{T}}} u^i)^2 \lambda_i　\\
&= c_p^2 \lambda_p
\end{split}\\ 
\end{align}

Par conséquent, $ c_p = \ frac {1} {\ sqrt {\ lambda_p}} $. Par conséquent, $ f $ (p-ième broche) qui fait de la variance la p-ième plus grande

f^p = \sum_{i=1}^{N}\frac{1}{\sqrt{\lambda_p}} u_i^p \tilde{\phi}(X_i)

Et la pième composante principale des données $ X_i $ est

\begin{align}
&\begin{split}
\langle \tilde{\phi}(X_i), f^p \rangle_H &= \sum_{j=1}^N \frac{1}{\sqrt{\lambda_p}} u_j^p  \langle \tilde{\phi}(X_i), \tilde{\phi}(X_j) \rangle_H \\
&= \sum_{j=1}^N \frac{1}{\sqrt{\lambda_p}} u_j^p  \tilde{K}_{ij} \\
&= \sum_{j=1}^N \frac{1}{\sqrt{\lambda_p}}  u_j^p \sum_{k=1}^N \lambda_k u_i^k u_j^k \\
&= \frac{1}{\sqrt{\lambda_p}} \sum_{k=1}^N \lambda_k u_i^k  \sum_{j=1}^N  u_j^p  u_j^k \\
&= \frac{1}{\sqrt{\lambda_p}} \sum_{k=1}^N \lambda_k u_i^k \delta(p,k) \\
&= \sqrt{\lambda_p} u_i^p
\end{split}\\ 
\end{align}

En d'autres termes, il suffit de connaître la valeur propre et la matrice unitaire lorsque la matrice $ \ tilde {K} $ ayant $ \ tilde {k} (X_i, X_j) $ comme composant $ ij $ est décomposée en valeurs propres.

Implémentez ce qui précède en utilisant Python. Données sur le vin (http://archive.ics.uci.edu/ml/datasets/Wine) Utiliser. Nous utiliserons le noyau gaussien pour les fonctions du noyau.

import numpy as np
import matplotlib.pyplot as plt

#Lire les données
wine = np.loadtxt("wine.csv", delimiter=",")
N = wine.shape[0] #178
labels = np.copy(wine[:,0]).flatten()
wine = wine[:, 1:]

#Standardisation
mean = wine.mean(axis=0)
wine -= mean
std = wine.std(axis=0)
wine /= std

def kernel(x,y, σ=4): return np.exp(-((x-y)**2).sum() / (2*σ**2))

#Calcul de la matrice gramme centralisée K
K = np.zeros(shape=(N,N))
for i,j in np.ndindex(N,N):
    K[i,j] = kernel(wine[i,:], wine[j,:])

Q = np.identity(N) - np.full(shape=(N,N), fill_value=1/N) 
K_tilde = Q @ K @ Q

#Décomposition de valeur unique
λs, us = np.linalg.eig(K_tilde)

#Trier par ordre décroissant de valeur unique
λ_index = np.argsort(λs)
D = np.zeros(shape=(N))
U = np.zeros(shape=(N,N))
for i, index in enumerate(λ_index[::-1]):
    D[i] = λs[index]
    U[:,i] = us[:,index]

#Nième composante principale des données
X_1 = np.sqrt(D[0]) * U[:,0]
X_2 = np.sqrt(D[1]) * U[:,1]


#Créer un graphique
clasters = dict([(i,[[],[]]) for i in range(1,4)])

for i,label in enumerate(labels): 
    clasters[label][0].append(X_1[i])
    clasters[label][1].append(X_2[i])

for label,marker in zip(range(1,4), ["+","s","o"]):
    plt.scatter(clasters[label][0], clasters[label][1], marker=marker)
plt.show()

Vous pouvez voir qu'il est bien classé. À propos, la forme du graphique change considérablement en fonction de la façon dont vous sélectionnez la fonction du noyau. Même avec le même noyau gaussien, il change en fonction des réglages des hyper paramètres, vous pouvez donc faire quelque chose comme la recherche de grille.

Références

Kenji Fukumizu, Introduction à la méthode du noyau [Analyse de données avec un noyau à valeur fixe positive], Asakura Shoten, 2010

Méthode Kernel avec Python