Grupos e convoluções grupais

– http://colah.github.io/posts/2014-12-Groups-Convolution/
Postado em 8 de dezembro de 2014
teoria do grupo, probabilidade, convolução, matemática

Simetria
Pense num quadrado. É simétrico? Como é simétrico? Qual é a simetria? Qual é o tipo de simetria?
O que significam essas perguntas?
Se você perguntar a alguém, eles podem dizer-lhe que um quadrado tem uma simetria rotacional. Se você girar um quadrado 90°, é a mesma forma. Sem saber qual era o canto, parece exatamente o mesmo que antes. Você poderia levantá-lo, girá-lo e ajustá-lo de volta para que cubra exatamente o mesmo espaço.
Vamos chamar essa transformação de rotação r. Para ser preciso, r gira um quadrado no sentido horário em 90°. Por exemplo, rF = rF (pra baixo). (O “F” no quadrado está lá para nos permitir determinar a orientação e ver as transformações.)
Também podem dizer-lhe que um quadrado tem simetria horizontal ou simetria vertical. Você pode virar um quadrado horizontalmente ou verticalmente e ainda tem um quadrado. Vamos concentrar a simetria horizontal por enquanto. Nós chamaremos de flips horizontais s. s executa uma reflexão através de uma linha vertical da metade do quadrado. Por exemplo, sF = F (virado para a esquerda).
Agora temos duas transformações, r e s, que transformam quadrados em outro quadrado da mesma forma. Acontece que essas duas transformações formam uma espécie de “base” para todos os outros. Ao usá-los em algum padrão, você pode construir as outras transformações, como o deslizamento vertical.
Começando com o nosso quadrado original F no canto inferior esquerdo, o gráfico a seguir mostra as versões transformadas geradas pela combinação de r e s de diferentes maneiras. r e s são representados por setas de cores diferentes. As setas r são de cor azul e as setas s são vermelhas.

Podemos usar o gráfico para investigar o que acontece se realizarmos uma seqüência de transformações. Por exemplo, o que acontece se girarmos, virar e voltamos a girar novamente? Bem, começamos no nosso quadrado original, F e anotamos:
No final, ficamos com apenas uma versão horizontalmente invertida do original, . Se quisermos expressar esse fato surpreendente, podemos usar a multiplicação como notação:. Se quisermos pensar sobre o nosso gráfico um pouco mais abstratamente, podemos representar todos os quadrados como o quadrado original transformado por r e s. Por exemplo, .

Aqui, e é a transformação da identidade, que não transforma o objeto. Por exemplo e F = F. (Por que ter e, se não faz nada? É como ter o número zero.)
Podemos ir um pouco mais. O quadrado original, F, parece um pouco desnecessário em rsr F = s F. Por que não apenas dizer rsr = s? Nós podemos simplesmente ignorar F, tanto em equações como no nosso gráfico.

Agora, aqui está a realização essencial: r e s poderiam ter sido outras coisas e teríamos o mesmo gráfico exato. r poderia ter girado 90° no sentido anti-horário. s poderia ter sido vertical flips. Ou poderíamos estar a transformar um tipo de objeto completamente diferente. Tudo o que importa é a relação entre r e s, como eles interagem. O que vimos com os quadrados era apenas uma maneira particular, esse gráfico, esse padrão abstrato, poderia aparecer no mundo real.
Os matemáticos chamam esses grupos de padrões abstratos. Existe um campo inteiro de matemática dedicado a eles. As conexões entre um grupo e um objeto como o quadrado chamam-se ações em grupo.
Mas… O que é um grupo?
Nem todos os gráficos são grupos. Apenas um tipo de gráfico muito especial. (Nós não daremos uma definição formal aqui, mas teremos uma boa sensação por isso.)
Em primeiro lugar, o gráfico é direcionado (as bordas são setas) e tem bordas coloridas. Em cada vértice, exatamente uma flecha de uma determinada cor sai e uma entra.
Mas a propriedade chave desses gráficos é mais sutil. Nós criamos o nosso gráfico começar com um quadrado original, F. Mas e se disséssemos que o quadrado original era ?

A posição que dizemos que é a posição “inicial” é arbitrária. Não importa em qual posição você pensa como a inicial, o gráfico é o mesmo. O gráfico é perfeitamente simétrico, em algum sentido.1 Imagine que as bordas são caminhos de cores diferentes que você pode andar, e você está parado em um dos nós: a partir da sua perspectiva, o gráfico é o mesmo, não importa em que nó você esteja. Não importa em que nó você esteja, indo pelo caminho vermelho, pelo caminho azul e, depois, pelo caminho vermelho e, em seguida, pelo caminho azul novamente o trará de volta para onde você começou.
No espaço euclidiano, argumentamos sobre pontos pelo sua posição relativa a uma origem. Da mesma forma, no nosso grupo, selecionamos alguma origem (por exemplo, F) e falamos sobre pontos pelas suas posições relativas. Chamamos essas posições relativas (como r, s ou r3s), os elementos do grupo.
Assim como podemos adicionar vetores de diferença de pontos, podemos “adicionar” elementos de um grupo juntos. Na verdade não é adição, é claro, mas é uma maneira natural de combinar elementos do grupo. Às vezes, falamos sobre isso por analogia com adição e escrita, combinando dois elementos a e b como a+b, enquanto outras vezes fazemos analogias com a multiplicação e escrevemos a⋅b.
“Adicionando” ou “multiplicando” dois elementos de grupo é realmente bastante semelhante à adição de vetores. Nós decidimos que um ponto no gráfico é o nosso elemento de identidade (a posição original), e encontrar os dois elementos que queremos multiplicar, a e b. Nós escolhemos caminhos da identidade para a e b. Em seguida, colocamos o caminho para o final de b, para nos levar a+b ou a⋅b (dependendo da notação escolhida).

A Perspectiva Algébrica
(Esta seção é opcional).
A descrição acima é quase irreconhecível como teoria do grupo, a partir de uma perspectiva tradicional. Geralmente, pensamos em grupos como uma espécie de abstração.
Há muitos tipos de objetos matemáticos e, à medida que você olha para eles, um deles vê padrões. Por exemplo, na aritmética, vemos a⋅(b+c)= a⋅b + a⋅c e na teoria de conjuntos vemos A∩ (B∪C) = A∩B ∪ A∩C. Existem muitos outros exemplos desse padrão e muitos outros padrões.
Também percebeu que muitos resultados importantes são verdadeiros para uma ampla classe de objetos, e eles são todos verdadeiros pela mesma razão. Eles são verdadeiros porque todos os objetos observam um padrão particular. Saber que um objeto matemático obedece a esse padrão é suficiente para provar o resultado.
Então, nós formalizamos esses padrões no que chamamos estruturas matemáticas.2 Há muitos deles e você pode encontrar uma lista muito longa de algébricas na wikipedia. Podemos estudar uma estrutura matemática e provar os resultados que possuem para qualquer instância dessa estrutura. (Programadores e cientistas da computação podem ver isso como fazendo matemática polimórfica.3)
Agora podemos dar a definição clássica de um grupo. Não se preocupe muito se tiver problemas para seguir.
Definição: Um grupo G = (S, ⋅) é um conjunto S equipado com uma operação binária (⋅), uma função que mapeia pares de elementos de grupo para elementos de grupo, com as seguintes propriedades:
– Existe um elemento de identidade, e∈S, tal que e⋅x = x⋅e = x para todo o x∈S.
– Para todos os elementos x∈S, existe um elemento inverso x-1∈S tal que x⋅x-1 = x-1⋅x = e.
– A operação (⋅) é associativa. Ou seja, (a⋅b) ⋅c = a⋅ (b⋅c) para todos a, b, c∈S
Por que essas regras? Por que não mais ou menos? Bem, podemos definir um grupo para ter mais ou menos requisitos. Se fosse mais fraco, tinha menos requisitos, mais tipos de objetos seriam grupos e os resultados que provamos sobre os grupos seriam mais amplamente aplicáveis. Se fosse mais forte, tinha mais requisitos, estariamos a falar sobre um tipo de objeto mais específico e poderia provar mais sobre eles. Em matemática, muitas vezes equilibra generalidade e especificidade como essa.
Os matemáticos estudam versões mais fracas e fortes de grupos. Mas, de alguma forma, os grupos são especiais. Eles não são muito gostosos, eles não são muito frios: eles estão certos.
Isso pode parecer meio arbitrário. Por que essas regras específicas devem ser uma coleção particularmente boa? Uma coisa que eu acho muito útil e motivadora é perceber que eles são equivalentes aos requisitos que fizemos quando pensávamos em grupos como gráficos. A identidade corresponde ao fato de haver um ponto de partida, inversa para poder retroceder nas setas, e a associatividade é equivalente à simetria perfeita do gráfico.

Um grupo de três cartões
Considere três cartas, . Existem algumas transformações que são naturais para aplicar-lhes. Chamaremos a operação de mudar as duas primeiras cartas (12). Da mesma forma, chamaremos a operação de troca das segundas cartas (23). Assim,

Juntas, essas duas operações geram um grupo, o Symmetric Group em 3 símbolos, S3.
Cada elemento do grupo é uma maneira particular de reorganizar os cartões, uma permutação.

Baralhar Cartões
Uma coisa interessante para pensar é baralhar. Quando baralhamos cartões, tentamos colocá-los em um pedido aleatório, uma permutação aleatória. Isso significa que criamos uma distribuição de probabilidade sobre o grupo.
Idealmente, o nosso baralho nos daria uma distribuição uniforme – toda permutação seria igualmente provável. Mas podemos facilmente imaginar um baralho imperfeito, onde algumas permutações são mais prováveis do que outras.

Claro, se o primeiro baralho não os aleatorizar, podemos repetir novamente!

Geralmente, as repetidas baralhas causam a difusão da massa de probabilidade, aproximando-nos da distribuição uniforme.5
Este deve ser semelhante ao exemplo bola caindo no post Entendendo Convoluções. Fundamentalmente, eles são a mesma coisa: convolução.

Convolução do grupo
As visualizações anteriores das distribuições de probabilidade nas permutações foram meio confusas. A maneira natural de visualizá-lo é no diagrama Cayley!
Consideremos uma distribuição de probabilidade muito simples. 40% do tempo que aplicamos a operação (12), permutando os nossos cartões para . 60% do tempo que aplicamos (23), permutando nossos cartões para . Esse é um baralho terrível, mas é fácil de pensar.

Para ser um pouco mais explícito, vamos imaginar-nos como começar com toda a densidade de probabilidade nos cartões não perturbeados (ou seja, a identidade) e, em seguida, baralhamos.
Quando baralhamos aleatoriamente, mostramos essa distribuição, obtendo alguma permutação a com probabilidade f(a).

O que acontece quando baralhamos uma segunda vez?
Bem, a primeira vez que baralhamos, obtivemos uma permutação com probabilidade f(a). Na segunda vez que vamos baralhar, obteremos outra permutação b com probabilidade g(b). Essas duas ações acontecem com a probabilidade f(a)g(b) e o resultado é uma permutação c=b⋅a.

Para obter a probabilidade real de c, no entanto, não basta apenas olhar para um par de permutações que nos levam a c. Em vez disso, precisamos resumir todos os pares possíveis de permutações. Esta é a convolução de g e f (como na composição da função, o lado direito é o primeiro).

Substituindo b=ca-1, obtemos:

Isso pode ser bem pensado como uma soma sobre as permutações intermediárias, a, vendo a probabilidade dessa permutação intermediária, e a probabilidade da permutação necessária para nos levar a c de lá.

Alternativamente, podemos substituir a = b-1c para obter:

A definição tradicional da convolução grupal. (Se você deixar a operação em grupo ser adição, esta é a definição normal de convolução.)

Outras generalizações de convolução
(Esta seção é opcional e assume um fundo mais forte do que o resto do artigo. Menos leitores com inclinação matemática podem querer ignorar esta seção.)
A definição tradicional de convolução exige que você seja capaz de tomar inversas e multiplique todos os elementos por qualquer outro elemento. Isso significa que você precisa estar a trabalhar num grupo, ou talvez um quasigroup.
Mas se você mudar para a definição (g*f)(c)=Σb⋅a=cg(b)f(a), o que parece muito mais natural, a convolução faz sentido em quase qualquer estrutura algébrica com um operador binário. Certamente, você pode falar sobre convoluções em monoids, groupoids e categorias. Tanto quanto posso dizer, ninguém realmente considerou isso.
Uma coisa fofa sobre isso é que a convolução muitas vezes herda as propriedades algébricas dos domínios das funções que estão sendo convolvidas. Por exemplo, se você convolve as funções em domínios associativos, a operação de convolução é associativa:

Da mesma forma, se o domínio é comutativo, a convolução também. E se tem identidade, a convolução também. Infelizmente, a convolução não é inversa se o domínio tiver inversos, de modo que o paralelo se desintegra nos monóides de Abelian.
Com a matemática a trabalhar tão bem, você pode se perguntar se há algum motivo em que realmente possa usar esses. Bem, a convolução em monóides parece natural nos casos em que você “não pode voltar atrás”. E a convolução nas categorias permite um tipo de estado. Na verdade, acho que você poderia naturalmente descrever o autômato probabilístico em termos de convolução de categorias.
Conclusão
Este ensaio tem uma perspectiva incomum sobre a teoria grupal. Os diagramas de Cayley existem há muito tempo, mas, tanto quanto eu sei, levá-los a sério como uma abordagem para a teoria do grupo, como um tipo de fundação, é uma idéia recente, projetada por Nathan Carter em seu livro Visual Group Theory. Os leitores interessados estão convidados a olhar para o livro dele.
As convoluções de grupo fornecem linguagem elegante para falar de muitas situações envolvendo probabilidade. Mas, uma vez que esta é uma série de postagens de blog sobre redes neurais convolutivas, você pode suspeitar que eu tenho outros interesses neles. Bem, você adivinhou corretamente. As circunvoluções grupais estendem naturalmente as redes neurais convolutivas, com tudo combinando muito bem. Uma vez que as redes neurais convolutivas são uma das ferramentas mais poderosas na aprendizagem de máquinas no momento, isso é bastante interessante. Na nossa próxima publicação, exploraremos essas redes.
Próximas postagens nesta série
Esta publicação faz parte de uma série de redes neurais convolutivas e as suas generalizações. As duas primeiras postagens serão revisadas para aqueles que estão familiarizados com a aprendizagem profunda, e os mais recentes devem ser de interesse para todos. Para obter atualizações, inscreva-se no meu feed RSS!
Por favor, comente abaixo ou ao lado. Os pedidos de envio podem ser feitos no github.
Reconhecimentos
Estou grato a Yomna Nasser, a Harry de Valence, a Sam Eisenstat e a Sebastian Zany por terem tido tempo para ler e comentar a versão preliminar desta publicação – os seus comentários melhoraram muito!
Também agradeço a Guillaume Alain, Eliana Lorch, Dario Amodei, Aaron Courville, Yoshua Bengio e Michael Nielsen pela discussão da convolução grupal e as suas aplicações potenciais às redes neurais.
1. Observe que a incorporação do gráfico não é necessariamente simétrica.
2. Geralmente as pessoas falam sobre as estruturas algébricas, estruturas matemáticas abstratas da álgebra. Existem estruturas matemáticas abstratas semelhantes em outras áreas, particularmente na análise. Por exemplo: espaços métricos, espaços topológicos e espaços de medida. No entanto, estes raramente são agrupados na forma como são as estruturas algébricas.↩
3. Esta é realmente uma analogia muito profunda. Na programação, muitas vezes tentamos escrever funções polimórficas que podem atuar em vários tipos de objetos. Em matemática, estamos a tentar fazer provas polimórficas que podem operar em diferentes tipos de objetos matemáticos. A correspondência Curry-Howard formaliza essa conexão entre programas e provas.
(Algumas linguagens de programação, como Haskell, até mesmo implementações de estruturas algébricas comuns como classes!)
Também vale a pena notar que, assim como a maioria das abordagens do polimorfismo na programação nos dá subclasses e superclasses, as estruturas algébricas também possuem “subestruturas” e “super-estruturas”.
4. A parte da associatividade é um pouco complicada de ver, especialmente porque nunca definimos rigorosamente a “simetria perfeita” dos nossos “gráficos de grupo”.
Uma definição é que, dado um loop que origina e no gráfico, ((bc)d)… = e, essa mesma seqüência também é um loop se ele começa em um ponto a, isto é (((ab)c )d)…= a. É bastante direto ver que isso decorre da associatividade, mas o que dizer da outra direção?
Bem, queremos provar para todos a, b, c que, a(bc)=(ab)c. Seja d=(bc)-1, o reverso do caminho para bc. Então (bc)d=e é um loop. Pela simetria do gráfico, ((ab)c)d=a. Agora, multiplicamos por d-1=(bc) para obter (ab)c=a(bc), que é associatividade.↩
5. Quantas vezes você tem que baralhar um baralho de cartas para torná-lo realmente aleatório? Esta questão foi explorada pelo matemático Persi Diaconis.↩
6. Não consigo encontrar instâncias de pessoas que falem sobre essas convoluções como coisas independentes, mas a operação parece estar construída de forma implícita em objetos construídos para estudar essas estruturas. Assim como a multiplicação em anéis de grupo é a convolução grupal, a multiplicação em anéis monóides é a convolução monoidal, a multiplicação em álgebras grupóides é a convolução grupóide e a multiplicação em álgebras categóricas é a convolução de categoria.

Sobre o autor

Sara Filipa

Comentar

por: Sara Filipa

Posts recentes

Comentários

Arquivos

Categorias

Meta