Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?

Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur GraphSearch.

Découvrez-en plus sur les applications Graph.

Graph
Search

fr|en

Se Connecter

Concept

Groupe de permutations

Résumé

En théorie des groupes (mathématiques), un groupe de permutations d'un ensemble X est par définition un sous-groupe du groupe symétrique SX. On parle d'un groupe de permutations de X ou, s'il n'est pas nécessaire de préciser l'ensemble X, d'un groupe de permutations. Conventions Pour un ensemble X, nous désignerons ici par SX et nous appellerons groupe symétrique de X l'ensemble des permutations de X, muni de la loi de groupe ∘ définie par f ∘ g : X → X, x ↦ f(g(x)). Cette définition convient à l'étude des actions à gauche d'un groupe sur un ensemble. Le groupe opposé du groupe noté ici SX convient à l'étude des actions à droite. Quand nous parlerons d'une action d'un groupe sur un ensemble, il s'agira d'une action à gauche. On sait qu'une action à gauche d'un groupe G sur un ensemble X peut être vue comme un homomorphisme de groupes de G dans SX. Action naturelle d'un groupe de permutations Soit G un groupe de permutations d'un ensemble X. Le groupe G agit (à g

Source officielle

https://fr.wikipedia.org/wiki/Groupe_de_permutations

À propos de ce résultat

Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.

Publications associées (12)

Publications associées

Chargement

Personnes associées

Chargement

Unités associées

Chargement

Concepts associés (28)

Concepts associés

Chargement

Cours associés (27)

Le but de ce cours est d'introduire et d'étudier les notions de base de l'algèbre abstraite.

Discrete mathematics is a discipline with applications to almost all areas of study. It provides a set of indispensable tools to computer science in particular. This course reviews (familiar) topics as diverse as mathematical reasoning, combinatorics, discrete structures & algorithmic thinking.

Étudier les concepts fondamentaux d'analyse et le calcul différentiel et intégral des fonctions réelles d'une variable.

Afficher plus

Cours associés

Chargement

Séances de cours associées (58)

Afficher plus

Séances de cours associées

Chargement

Unique decomposition of homogeneous languages and application to isothetic regions

Nicolas René Jean Ninin

A language is said to be homogeneous when all its words have the same length. Homogeneous languages thus form a monoid under concatenation. It becomes freely commutative under the simultaneous actions of every permutation group G(n) on the collection of homogeneous languages of length n is an element of N. One recovers the isothetic regions from (Haucourt 2017, to appear (online since October 2017)) by considering the alphabet of connected subsets of the space vertical bar G vertical bar, viz the geometric realization of a finite graph G. Factoring the geometric model of a conservative program amounts to parallelize it, and there exists an efficient factoring algorithm for isothetic regions. Yet, from the theoretical point of view, one wishes to go beyond the class of conservative programs, which implies relaxing the finiteness hypothesis on the graph G. Provided that the collections of n-dimensional isothetic regions over G (denoted by R-n vertical bar G vertical bar) are co -unital distributive lattices, the prime decomposition of isothetic regions is given by an algorithm which is, unfortunately, very inefficient. Nevertheless, if the collections R-n vertical bar G vertical bar satisfy the stronger property of being Boolean algebras, then the efficient factoring algorithm is available again. We relate the algebraic properties of the collections R-n vertical bar G vertical bar to the geometric properties of the space I GI. On the way, the algebraic structure R-n vertical bar G vertical bar is proven to be the universal tensor product, in the category of semilattices with zero, of n copies of the algebraic structure R-1 vertical bar G vertical bar.

2019

Chargement

The minimal faithful permutation degree (G) of a finite group G is the least nonnegative integer n such that G embeds in the symmetric group Sym(n). Clearly (G x H) (G) + (H) for all finite groups G and H. In 1975, Wright ([10]) proved that equality occurs when G and H are nilpotent and exhibited an example of strict inequality where G x H embeds in Sym(15). In 2010 Saunders ([7]) produced an infinite family of examples of permutation groups G and H where (G x H) < (G) + (H), including the example of Wright's as a special case. The smallest groups in Saunders' class embed in Sym(10). In this article, we prove that 10 is minimal in the sense that (G x H)=(G) + (H) for all groups G and H such that (G x H)

Taylor & Francis Inc2016

Chargement

Geometry of the Loss Landscape in Overparameterized Neural Networks: Symmetries and Invariances

Johanni Michael Brea, Wulfram Gerstner, Clément Hongler, Berfin Simsek, Francesco Spadaro

We study how permutation symmetries in overparameterized multi-layer neural networks generate `symmetry-induced' critical points. Assuming a network with

L

layers of minimal widths

r_1^*, \ldots, r_{L-1}^*

reaches a zero-loss minimum at

r_1^*! \cdots r_{L-1}^*!

isolated points that are permutations of one another, we show that adding one extra neuron to each layer is sufficient to connect all these previously discrete minima into a single manifold. For a two-layer overparameterized network of width

r^*+ h =: m

we explicitly describe the manifold of global minima: it consists of

T(r^*, m)

affine subspaces of dimension at least

h

that are connected to one another. For a network of width

m

, we identify the number

G(r,m)

of affine subspaces containing only symmetry-induced critical points that are related to the critical points of a smaller network of width

r&lt;r^*

. Via a combinatorial analysis, we derive closed-form formulas for

T

and

G

and show that the number of symmetry-induced critical subspaces dominates the number of affine subspaces forming the global minima manifold in the mildly overparameterized regime (small

h

) and vice versa in the vastly overparameterized regime (

h \gg r^*

). Our results provide new insights into the minimization of the non-convex loss function of overparameterized neural networks.

2021

Chargement

Geometry of the Loss Landscape in Overparameterized Neural Networks: Symmetries and Invariances

Johanni Michael Brea, Wulfram Gerstner, Clément Hongler, Berfin Simsek, Francesco Spadaro

We study how permutation symmetries in overparameterized multi-layer neural networks generate `symmetry-induced' critical points. Assuming a network with

L

layers of minimal widths

r_1^*, \ldots, r_{L-1}^*

reaches a zero-loss minimum at

r_1^*! \cdots r_{L-1}^*!

r^*+ h =: m

we explicitly describe the manifold of global minima: it consists of

T(r^*, m)

affine subspaces of dimension at least

h

that are connected to one another. For a network of width

m

, we identify the number

G(r,m)

of affine subspaces containing only symmetry-induced critical points that are related to the critical points of a smaller network of width

r&lt;r^*

. Via a combinatorial analysis, we derive closed-form formulas for

T

and

G

and show that the number of symmetry-induced critical subspaces dominates the number of affine subspaces forming the global minima manifold in the mildly overparameterized regime (small

h

) and vice versa in the vastly overparameterized regime (

h \gg r^*

). Our results provide new insights into the minimization of the non-convex loss function of overparameterized neural networks.

2021