„Theorem von Deep Noether“: Aufbau von Symmetrieeinschränkungen

Aus Emres obigem Kommentar geht hervor, dass Abschnitt 4.4 der gruppentheoretischen Methoden des maschinellen Lernens von Risi Kondor detaillierte Informationen und Beweise zum Erstellen von Kernelmethoden enthält, die von Natur aus Symmetrien aufweisen. Ich werde es auf hoffentlich intuitive Weise zusammenfassen (ich bin Physiker, kein Mathematiker!).

Die meisten ML-Algorithmen haben eine Matrixmultiplikation wie

\begin{aligned} s_{ich} & = \sum_{j} {W.}_{ich j} x_{j} \\ = \sum_{j} {W.}_{ich 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}$ wobei

\vec{x}

$\vec{x}$ die Eingabe und

W_{i j}

$W_{ij}$ die Gewichte sind, die wir trainieren möchten.

Kernel-Methode

Betreten Sie den Bereich der Kernel-Methoden und lassen Sie den Algorithmus die Eingabe über

\begin{aligned} s_{ich} & = \sum_{j} {W.}_{ich j} k (e_{j}, x) \end{aligned}

$\begin{align} s_i &= \sum_j W_{ij}~k(e_j,~x) \end{align}$ wobei wir nun auf

x, e_{j} \in X

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

Betrachten Sie eine Gruppe $G$ , die über für auf $\mathcal{X}$ einwirkt . Eine einfache Möglichkeit, unseren Algorithmus unter dieser Gruppe invariant zu machen, besteht darin, einen Kernel, $x \rightarrow T_g(x)$ $g \in G$

\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}$ mit

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

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

Also,

\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}$

Für $k(x, y) = x \cdot y$ das für alle einheitlichen Darstellungen gilt,

\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}$

Dies bietet eine Transformationsmatrix, die die Eingabe in den Algorithmus symmetrisieren kann.

SO (2) Beispiel

Eigentlich nur die Gruppe, die auf $\frac{\pi}{2}$ Einfachheit halber Umdrehungen.

Lassen Sie uns eine lineare Regression für Daten $(\vec{x}_i, y_i) \in \mathbb{R}^2 \times \mathbb{R}$ wobei wir eine Rotationssymmetrie erwarten.

Unser Optimierungsproblem wird

\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}$

Der Kern $k(x, y) = \| x - y \|^2$ erfüllt $k(x, y) = k(T_g(x), T_g(y))$ . Sie können auch $k(x, y) = x \cdot y$ und eine Vielzahl von Kerneln verwenden.

Somit ist

\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}$

$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}$

Was die erwartete sphärische Symmetrie ergibt!

Tic-Tac-Toe

Beispielcode ist hier zu sehen . Es zeigt, wie wir eine Matrix erstellen können, die die Symmetrie codiert und verwendet. Beachten Sie, dass dies wirklich schlecht ist, wenn ich es tatsächlich laufen lasse! Momentan mit anderen Kerneln arbeiten.

aidan.plenert.macdonald
quelle

Gute Arbeit, Aidan! Wenn Sie Zeit haben, können Sie einen detaillierteren Blog-Beitrag schreiben. Die Community wird am meisten interessiert sein.

Emre

Ich bin mir nicht sicher, auf welche Community Sie sich beziehen, aber ich habe angefangen, mehr zu schreiben. Ich wollte einen Weg finden, um den optimalen Kernel anhand eines Datensatzes zu schätzen. Daher habe ich die Entropie im Kernelraum optimiert, um intuitiv einen neuen Satz von Funktionen zu erhalten, die symmetrisch eingeschränkt und auch maximal entropisch (dh informativ) sind. Nun, ob das der richtige Ansatz ist. Das kann ich nicht sagen Nur eine Warnung, die Mathematik ist im Moment ein bisschen ein Hack-Job und irgendwie direkt aus dem Status mech. overleaf.com/read/kdfzdbyhpbbq

aidan.plenert.macdonald

Gibt es einen sinnvollen Ansatz, wenn die Symmetriegruppe nicht bekannt ist?

Leitasat

@leitasat Woher weißt du, dass es symmetrisch ist, wenn du die Gruppe nicht kennst?