“Teorema de Noether profundo”: construindo restrições de simetria

A partir do comentário de Emre acima, a Seção 4.4 dos métodos teóricos de grupo em aprendizado de máquina de Risi Kondor tem informações detalhadas e provas sobre a criação de métodos de kernel que inerentemente possuem simetrias. Vou resumir isso de uma maneira esperançosamente intuitiva (eu sou um físico, não um matemático!).

A maioria dos algoritmos de ML tem uma multiplicação de matrizes como,

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

\vec{x}

$\vec{x}$ sendo a entrada e

W_{i j}

$W_{ij}$ sendo os pesos que desejam comboio.

Método do Kernel

Digite o domínio dos métodos do kernel e deixe o algoritmo manipular a entrada 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}$ onde agora se generalizar para

x, e_{j} \in X

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

Considere-se um grupo $G$ que actua em $\mathcal{X}$ através $x \rightarrow T_g(x)$ para o $g \in G$ . Uma maneira simples de tornar nosso algoritmo invariável nesse grupo é criar um kernel,

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

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

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

Então,

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

Para $k(x, y) = x \cdot y$ que funciona para todas as representações unitárias,

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

Que oferece uma matriz de transformação que pode simetrizar a entrada no algoritmo.

Exemplo SO (2)

Na verdade, apenas o grupo que mapeia para $\frac{\pi}{2}$ rotações para simplificar.

Vamos executar a regressão linear nos dados $(\vec{x}_i, y_i) \in \mathbb{R}^2 \times \mathbb{R}$ onde esperamos uma simetria rotacional.

Nosso problema de otimização se torna,

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

O núcleo $k(x, y) = \| x - y \|^2$ satisfaz $k(x, y) = k(T_g(x), T_g(y))$ . Você também pode usar $k(x, y) = x \cdot y$ e uma variedade de núcleos.

Assim,

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

Which yields the expected spherical symmetry!

Tic-Tac-Toe

Example code can be seen here. It shows how we can create a matrix that encodes the symmetry and use it. Note that this is really bad when I actually run it! Working with other kernels at the moment.

aidan.plenert.macdonald
fonte

Good job, Aidan! If you have time, you can write a more detailed blog post. The community will be most interested.

Emre

Not sure what community you are referring to, but I started writing more. I wanted to find a way to estimate the optimal kernel given a set of data. So I optimized entropy on kernel space to intuitively get a new set of features that are symmetrically constrained and also maximally entropic (ie. informative). Now whether that it the right approach. I can't say. Just a warning, the math is a bit of a hack job right now and kind of straight out of stat mech. overleaf.com/read/kdfzdbyhpbbq

aidan.plenert.macdonald

Is there any meaningful approach when the symmetry group is not known?

leitasat

@leitasat How do you know it's symmetric if you don't know the group?