«Théorème de Deep Noether»: intégrer des contraintes de symétrie

D'après le commentaire d'Emre ci-dessus, la section 4.4 des méthodes théoriques de groupe en apprentissage automatique par Risi Kondor contient des informations détaillées et des preuves sur la création de méthodes de noyau qui ont intrinsèquement des symétries. Je vais le résumer d'une manière, je l'espère, intuitive (je suis un physicien et non un mathématicien!).

La plupart des algorithmes ML ont une multiplication matricielle comme,

\begin{aligned} s_{i} & = \sum_{j} W_{i j} x_{j} \\ = \sum_{j} W_{i j} ({\vec{e}}_{j} \cdot \vec{x}) \end{aligned}

$\begin{align} s_i &= \sum_j W_{ij}~x_j \\ &= \sum_j W_{ij}~(\vec{e}_j \cdot \vec{x}) \end{align}$ avec

\vec{x}

$\vec{x}$ étant l'entrée et

W_{i j}

$W_{ij}$ étant les poids que nous souhaitons entraîner.

Méthode du noyau

Entrez dans le domaine des méthodes du noyau et laissez l'algorithme gérer l'entrée via,

\begin{aligned} s_{i} & = \sum_{j} W_{i j} k (e_{j}, x) \end{aligned}

$\begin{align} s_i &= \sum_j W_{ij}~k(e_j,~x) \end{align}$ où maintenant on généralise à

x, e_{j} \in X

$x, e_j \in \mathcal{X}$ .

Considérons un groupe $G$ qui agit sur $\mathcal{X}$ par $x \rightarrow T_g(x)$ pour $g \in G$ . Un moyen simple de rendre notre algorithme invariant sous ce groupe est de faire un noyau,

\begin{aligned} k^{G} (x, y) & = \frac{1}{| G |} \sum_{g \in G} k (x, T_{g} (y)) \end{aligned}

$\begin{align} k^G(x, y) &= \frac{1}{|G|} \sum_{g \in G} k(x, T_g(y)) \end{align}$ avec

k (x, y) = k (T_{g} (x), T_{g} (y))

$k(x, y) = k(T_g(x), T_g(y))$ .

Donc,

\begin{aligned} k^{G} (x, T_{h} (y)) & = \frac{1}{| G |} \sum_{g \in G} k (x, T_{g h} (y)) \\ = \frac{1}{| G |} \sum_{g \in G} k (x, T_{g} (y)) \\ = \frac{1}{| G |} \sum_{g \in G} k (T_{g} (x), y) \end{aligned}

$\begin{align} k^G(x, T_h(y)) &= \frac{1}{|G|} \sum_{g \in G} k(x, T_{gh}(y)) \\ &= \frac{1}{|G|} \sum_{g \in G} k(x, T_{g}(y)) \\ &= \frac{1}{|G|} \sum_{g \in G} k(T_{g}(x), y) \end{align}$

Pour $k(x, y) = x \cdot y$ qui fonctionne pour toutes les représentations unitaires,

\begin{aligned} k^{G} (x, T_{h} (y)) & = [\frac{1}{| G |} \sum_{g \in G} T_{g} (x)] \cdot y \end{aligned}

$\begin{align} k^G(x, T_h(y)) &= \left[ \frac{1}{|G|} \sum_{g \in G} T_{g}(x) \right] \cdot y \end{align}$

Ce qui offre une matrice de transformation qui peut symétriser l'entrée dans l'algorithme.

SO (2) Exemple

En fait, juste le groupe qui correspond à $\frac{\pi}{2}$ rotations pour plus de simplicité.

Exécutons une régression linéaire sur les données $(\vec{x}_i, y_i) \in \mathbb{R}^2 \times \mathbb{R}$ où nous nous attendons à une symétrie de rotation.

Notre problème d'optimisation devient,

\begin{aligned} min_{W_{j}} & \sum_{i} \frac{1}{2} (y_{i} - {\tilde{y}}_{i})^{2} \\ {\tilde{y}}_{i} & = \sum_{j} W_{j} k_{G} (e_{j}, x_{i}) + b_{i} \end{aligned}

$\begin{align} \min_{W_{j}} &\sum_i \frac{1}{2} (y_i - \tilde{y}_i)^2 \\ \tilde{y}_i &= \sum_j W_{j} k_G(e_j, x_i) + b_i \end{align}$

$k(x, y) = \| x - y \|^2$ $k(x, y) = k(T_g(x), T_g(y))$ $k(x, y) = x \cdot y$

Ainsi,

\begin{aligned} k_{G} (e_{j}, x_{i}) & = \frac{1}{4} \sum_{n = 1}^{4} ‖ R (n π / 2) {\vec{e}}_{j} - {\vec{x}}_{i} ‖^{2} \\ = \frac{1}{4} \sum_{n = 1}^{4} (\cos (n π / 2) - {\vec{x}}_{i 1})^{2} + (\sin (n π / 2) - {\vec{x}}_{i 2})^{2} \\ = \frac{1}{4} [2 {\vec{x}}_{i 1}^{2} + 2 {\vec{x}}_{i 2}^{2} + (1 - {\vec{x}}_{i 1})^{2} + (1 - {\vec{x}}_{i 2})^{2} + (1 + {\vec{x}}_{i 1})^{2} + (1 + {\vec{x}}_{i 2})^{2}] \\ = {\vec{x}}_{i 1}^{2} + {\vec{x}}_{i 2}^{2} + 1 \end{aligned}

$\begin{align} k_G(e_j, x_i) &= \frac{1}{4} \sum_{n=1}^4 \| R(n\pi/2)~\vec{e}_j - \vec{x}_i \|^2 \\ &= \frac{1}{4} \sum_{n=1}^4 ( \cos(n\pi/2) - \vec{x}_{i1} )^2 + ( \sin(n\pi/2) - \vec{x}_{i2} )^2 \\ &= \frac{1}{4} \left[ 2 \vec{x}_{i1}^2 + 2 \vec{x}_{i2}^2 + (1 - \vec{x}_{i1} )^2 + (1 - \vec{x}_{i2} )^2 + (1 + \vec{x}_{i1} )^2 + (1 + \vec{x}_{i2} )^2 \right] \\ &= \vec{x}_{i1}^2 + \vec{x}_{i2}^2 + 1 \end{align}$

Notez que nous n'avons pas besoin de faire la somme de car c'est la même chose pour les deux. Donc, notre problème devient, $j$

\begin{aligned} min_{W} & \sum_{i} \frac{1}{2} (y_{i} - {\tilde{y}}_{i})^{2} \\ {\tilde{y}}_{i} & = W [{\vec{x}}_{i 1}^{2} + {\vec{x}}_{i 2}^{2} + 1] + b_{i} \end{aligned}

$\begin{align} \min_{W} &\sum_i \frac{1}{2} (y_i - \tilde{y}_i)^2 \\ \tilde{y}_i &= W \left[ \vec{x}_{i1}^2 + \vec{x}_{i2}^2 + 1 \right] + b_i \end{align}$

Ce qui donne la symétrie sphérique attendue!

Tic-Tac-Toe

Un exemple de code peut être vu ici . Il montre comment nous pouvons créer une matrice qui code la symétrie et l'utiliser. Notez que c'est vraiment mauvais quand je le lance! Travailler avec d'autres noyaux en ce moment.

aidan.plenert.macdonald
la source

Bon travail, Aidan! Si vous avez le temps, vous pouvez écrire un article de blog plus détaillé. La communauté sera la plus intéressée.

Emre

Je ne sais pas de quelle communauté vous parlez, mais j'ai commencé à écrire davantage. Je voulais trouver un moyen d'estimer le noyau optimal étant donné un ensemble de données. J'ai donc optimisé l'entropie sur l'espace du noyau pour obtenir intuitivement un nouvel ensemble de fonctionnalités qui sont contraintes symétriquement et aussi entropiques au maximum (c'est-à-dire informatives). Maintenant, que ce soit la bonne approche. Je ne peux pas dire. Juste un avertissement, les maths sont un peu un travail de piratage en ce moment et un peu tout droit sorti des statistiques. overleaf.com/read/kdfzdbyhpbbq

aidan.plenert.macdonald

Existe-t-il une approche significative lorsque le groupe de symétrie n'est pas connu?

leitasat

@leitasat Comment savez-vous que c'est symétrique si vous ne connaissez pas le groupe?