Answers.Body: <p>Here is a few that might be what you are looking for:</p>
  
  <ul>
  <li>Deep Sets, <a href="https://papers.nips.cc/paper/6931-deep-sets.pdf" rel="noreferrer">https://papers.nips.cc/paper/6931-deep-sets.pdf</a></li>
  <li>BRUNO: A Deep Recurrent Model for Exchangeable Data, <a href="https://arxiv.org/pdf/1802.07535.pdf" rel="noreferrer">https://arxiv.org/pdf/1802.07535.pdf</a></li>
  <li>Deep Learning with Sets and Point Clouds, <a href="https://openreview.net/pdf?id=HJF3iD9xe" rel="noreferrer">https://openreview.net/pdf?id=HJF3iD9xe</a></li>
  <li>Permutation-equivariant neural networks applied to dynamics prediction, <a href="https://arxiv.org/pdf/1612.04530.pdf" rel="noreferrer">https://arxiv.org/pdf/1612.04530.pdf</a></li>
  </ul>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2018-08-13T19:27:27.663Z
Answers.LastActivityDate: 2018-08-13T19:27:27.663Z
Answers.UserDisplayName: elgehelge
Answers.Body: <p>I have implemented Permutational Layer here using Keras: <a href="https://github.com/offchan42/superkeras/blob/master/permutational_layer.py" rel="nofollow noreferrer">https://github.com/offchan42/superkeras/blob/master/permutational_layer.py</a></p>
  <p>You can call the <code>PermutationalModule</code> function to use it.</p>
  <p>Implemented following this paper: <a href="https://arxiv.org/pdf/1612.04530.pdf" rel="nofollow noreferrer">Permutation-equivariant neural networks applied to dynamics prediction</a>.</p>
  <p>The idea is to compare all pairs of <span class="math-container">$N^2$</span> pairs from <span class="math-container">$N$</span> inputs, use the model with shared weights, then use pooling function <span class="math-container">$N$</span> times on <span class="math-container">$N$</span> inputs.</p>
  <p>The output you can use pooling again but in the paper, they don't mention another pooling.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-05-17T00:24:11.120Z
Answers.Text: Interesting.  Without looking into details, I wonder why the computation is $N^2$ instead of $N!$.  There are $N!$ possible permutations in the symmetric group.
Answers.UserDisplayName: Yan King Yin
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-05-17T03:21:56.950Z
Answers.Text: Because this is not a complete permutation. It's very different from what you think. So you better look at the details from the paper.
Answers.UserDisplayName: offchan
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2018-12-19T20:37:15.307Z
Answers.LastActivityDate: 2024-03-02T00:22:27.637Z
Answers.LastEditDate: 2024-03-02T00:22:27.637Z
Answers.UserDisplayName: offchan
Answers.Body: <p>So, a practical application of this with a lot of research is in the deep lidar processing community.  In that world, you have to do a lot of computation on point clouds which are completely unordered.  One of the seminal works in this field is Point Net (<a href="https://arxiv.org/pdf/1612.00593.pdf" rel="nofollow noreferrer">https://arxiv.org/pdf/1612.00593.pdf</a>) which solves this problem by performing all symmetric operations across channels.  1D convolutions, max pool, etc.  Any network in this style that does not project to a 2D representation has to adhere to this rule.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-02-26T14:37:35.867Z
Answers.LastActivityDate: 2020-02-26T14:37:35.867Z
Answers.UserDisplayName: juicedatom
Answers.Body: <p>Traditionally, due to the way the network is structured, each input has a set of weights, that are connected to more inputs. If the inputs switch, the output will too.</p>
  <h3>Approach 1</h3>
  <p>However, you can build a network that approaches this behaviour. In your training set, use batch learning and for each training sample, give all possible permutations to the network such that it learns to be permutation invariant. This will never be exactly invariant, it just might be close.</p>
  <h3>Approach 2</h3>
  <p>Another way to do this is to have the weights replicated for all inputs. For example, let's assume you have 3 inputs (<span class="math-container">$i_0, i_1, i_2$</span>), and the next/first hidden layer has 2 nodes (<span class="math-container">$h_{10}, h_{11}$</span>) and activation function <span class="math-container">$\phi$</span>. Assuming a fully connected layer, you have 2 weights <span class="math-container">$w_0$</span> and <span class="math-container">$w_1$</span>. The hidden layer's nodes <span class="math-container">$h_{10}$</span> and <span class="math-container">$h_{11}$</span> are given, respectively, by</p>
  <ul>
  <li><p><span class="math-container">$h_{10} = \phi(i_0 w_0 + i_1 w_0 + i_2 w_0)$</span></p>
  </li>
  <li><p><span class="math-container">$h_{11} = \phi(i_0 w_1 + i_1 w_1 + i_2 w_1)$</span></p>
  </li>
  </ul>
  <p>Thus giving you a hidden layer whose values are permutation invariant from the input. From now on, you can learn and build the rest of the network as you see fit. This is an approach derived from convolutional layers.</p>
  <h3>Approach 3</h3>
  <p>Finally, you can use a dimension reduction to achieve this. I've published this in <a href="https://www.researchgate.net/publication/341498982_Exploring_communication_protocols_and_centralized_critics_in_multi-agent_deep_learning" rel="noreferrer">Exploring Communication Protocols and Centralized Critics in Multi-Agent Deep Learning</a>, on Integrated Computer-Aided Engineering. This approach uses convolutional architectures to efficiently achieve permutation invariance.</p>
  
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-12-11T20:16:11.903Z
Answers.Text: The first approach suggested would be infeasible in my case due to the computational complexity. The second, on the other hand, seems maybe too restrictive. But it is certainly a good start. What I have come up with so far is an approach similar to the one I found in this paper: https://arxiv.org/pdf/1612.04530.pdf. First, I consider all pairs (generally all k-tuples) of inputs $x_i, x_j$, and apply some neural network on all of them (the same NN on each pair). This gives me $n^2$ outputs $f(x_i, x_j)$, and then I average them (or take maximum) and apply another NN over the result.
Answers.UserDisplayName: Josef Ondrej
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2018-01-31T14:02:28.050Z
Answers.Text: This is what I have come up with so far: https://github.com/josefondrej/Symmetric-Layers
Answers.UserDisplayName: Josef Ondrej
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2017-12-10T22:18:39.937Z
Answers.LastActivityDate: 2020-11-06T02:29:39.520Z
Answers.LastEditDate: 2020-11-06T02:29:39.520Z
Answers.UserDisplayName: BlueMoon93
Body: <blockquote>
  <p>Given a neural network <span class="math-container">$f$</span> that takes as input <span class="math-container">$n$</span> data points: <span class="math-container">$x_1, \dots, x_n$</span>. We say <span class="math-container">$f$</span> is <strong>permutation invariant</strong> if</p>
  <p><span class="math-container">$$f(x_1 ... x_n) = f(\sigma(x_1 ... x_n))$$</span></p>
  <p>for any permutation <span class="math-container">$\sigma$</span>.</p>
  </blockquote>
  <p>How could we build such a neural network? The output can be anything (e.g. a number or vector), as long as it does not depend on the order of inputs. Is there any research work on these types of neural networks?</p>
  
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2017-12-04T15:15:10.053Z
Comments.Text: Interesting question. You want to treat you inputs as a set rather than a vector. Assuming your inputs are scalar or otherwise comparable, did you consider sorting your inputs to create a permutation-invariant canonical representation and feeding that to a regular network?
Comments.UserDisplayName: mjul
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2017-12-05T08:33:24.027Z
Comments.Text: @mjul My inputs are series of bets of clients (each bet is represented by a vector of some cathegorical and continuous variables). I could order them chronologically for example, but as the time spacing between bets for each client is very different, this wouldn't make much sense. This could probably be solved using some function (fixed or learned) of time that would decay the coefficients for each bet. But I think the ordering really doesn't matter in this case so I wanted to try unordered data first, which obviously requires to treat the bets for each client symmetrically.
Comments.UserDisplayName: Josef Ondrej
Tags: <neural-networks><machine-learning><reference-request><network-design>
Title: How could we build a neural network that is invariant to permutations of the inputs?
UserDisplayName: Josef Ondrej
ThreadText: # How could we build a neural network that is invariant to permutations of the inputs?
  
  (Asked by: username_0 on 2017-12-04)
  
  > Given a neural network $f$ that takes as input $n$ data points: $x\_1, \dots, x\_n$. We say $f$ is **permutation invariant** if
  >
  > $$f(x\_1 ... x\_n) = f(\sigma(x\_1 ... x\_n))$$
  >
  > for any permutation $\sigma$.
  
  How could we build such a neural network? The output can be anything (e.g. a number or vector), as long as it does not depend on the order of inputs. Is there any research work on these types of neural networks?
  
  **Tags:** neural-networks, machine-learning, reference-request, network-design
  > **Comments:**
  > **username_1**: Interesting question. You want to treat you inputs as a set rather than a vector. Assuming your inputs are scalar or otherwise comparable, did you consider sorting your inputs to create a permutation-invariant canonical representation and feeding that to a regular network?  
  > **username_0**: @mjul My inputs are series of bets of clients (each bet is represented by a vector of some cathegorical and continuous variables). I could order them chronologically for example, but as the time spacing between bets for each client is very different, this wouldn't make much sense. This could probably be solved using some function (fixed or learned) of time that would decay the coefficients for each bet. But I think the ordering really doesn't matter in this case so I wanted to try unordered data first, which obviously requires to treat the bets for each client symmetrically.  
  
  ---
  
  ## 4 answers
  
  ### Answer by username_6 on 2017-12-10. Score: 13 | Accepted answer
  
  Traditionally, due to the way the network is structured, each input has a set of weights, that are connected to more inputs. If the inputs switch, the output will too.
  
  ### Approach 1
  
  However, you can build a network that approaches this behaviour. In your training set, use batch learning and for each training sample, give all possible permutations to the network such that it learns to be permutation invariant. This will never be exactly invariant, it just might be close.
  
  ### Approach 2
  
  Another way to do this is to have the weights replicated for all inputs. For example, let's assume you have 3 inputs ($i\_0, i\_1, i\_2$), and the next/first hidden layer has 2 nodes ($h\_{10}, h\_{11}$) and activation function $\phi$. Assuming a fully connected layer, you have 2 weights $w\_0$ and $w\_1$. The hidden layer's nodes $h\_{10}$ and $h\_{11}$ are given, respectively, by
  
  * $h\_{10} = \phi(i\_0 w\_0 + i\_1 w\_0 + i\_2 w\_0)$
  * $h\_{11} = \phi(i\_0 w\_1 + i\_1 w\_1 + i\_2 w\_1)$
  
  Thus giving you a hidden layer whose values are permutation invariant from the input. From now on, you can learn and build the rest of the network as you see fit. This is an approach derived from convolutional layers.
  
  ### Approach 3
  
  Finally, you can use a dimension reduction to achieve this. I've published this in [Exploring Communication Protocols and Centralized Critics in Multi-Agent Deep Learning](https://www.researchgate.net/publication/341498982_Exploring_communication_protocols_and_centralized_critics_in_multi-agent_deep_learning), on Integrated Computer-Aided Engineering. This approach uses convolutional architectures to efficiently achieve permutation invariance.
  
  > **Comments:**
  > **username_0**: The first approach suggested would be infeasible in my case due to the computational complexity. The second, on the other hand, seems maybe too restrictive. But it is certainly a good start. What I have come up with so far is an approach similar to the one I found in this paper: https://arxiv.org/pdf/1612.04530.pdf. First, I consider all pairs (generally all k-tuples) of inputs $x_i, x_j$, and apply some neural network on all of them (the same NN on each pair). This gives me $n^2$ outputs $f(x_i, x_j)$, and then I average them (or take maximum) and apply another NN over the result.  
  > **username_0**: This is what I have come up with so far: https://github.com/josefondrej/Symmetric-Layers  
  
  ---
  
  ### Answer by username_2 on 2018-08-13. Score: 14
  
  Here is a few that might be what you are looking for:
  
  * Deep Sets, <https://papers.nips.cc/paper/6931-deep-sets.pdf>
  * BRUNO: A Deep Recurrent Model for Exchangeable Data, <https://arxiv.org/pdf/1802.07535.pdf>
  * Deep Learning with Sets and Point Clouds, <https://openreview.net/pdf?id=HJF3iD9xe>
  * Permutation-equivariant neural networks applied to dynamics prediction, <https://arxiv.org/pdf/1612.04530.pdf>
  
  
  ---
  
  ### Answer by username_3 on 2018-12-19. Score: 5
  
  I have implemented Permutational Layer here using Keras: <https://github.com/offchan42/superkeras/blob/master/permutational_layer.py>
  
  You can call the `PermutationalModule` function to use it.
  
  Implemented following this paper: [Permutation-equivariant neural networks applied to dynamics prediction](https://arxiv.org/pdf/1612.04530.pdf).
  
  The idea is to compare all pairs of $N^2$ pairs from $N$ inputs, use the model with shared weights, then use pooling function $N$ times on $N$ inputs.
  
  The output you can use pooling again but in the paper, they don't mention another pooling.
  
  > **Comments:**
  > **username_4**: Interesting.  Without looking into details, I wonder why the computation is $N^2$ instead of $N!$.  There are $N!$ possible permutations in the symmetric group.  
  > **username_3**: Because this is not a complete permutation. It's very different from what you think. So you better look at the details from the paper.  
  
  ---
  
  ### Answer by username_5 on 2020-02-26. Score: 2
  
  So, a practical application of this with a lot of research is in the deep lidar processing community. In that world, you have to do a lot of computation on point clouds which are completely unordered. One of the seminal works in this field is Point Net (<https://arxiv.org/pdf/1612.00593.pdf>) which solves this problem by performing all symmetric operations across channels. 1D convolutions, max pool, etc. Any network in this style that does not project to a 2D representation has to adhere to this rule.
  
  
  ---
  
  