On neural networks with equivariance or invariance property

Abstract

Single- or multi-layer perceptrons, commonly known as neural networks, are universal approximators that can approximate any continuous functions arbitrarily well when the number of perceptrons is allowed to grow indefinitely. When prior knowledge about the target function is available, constraints can be imposed on the neural network to improve approximation accuracy. As an example, it is well known that convolutional neural networks (CNN) \cite{lecun1990handwritten} yield good performance on image classification. And its parameter-sharing scheme can also reduce the risk of overfitting. One of the key properties of image classification is that it is invariant to translation of input image. The translation invariance in CNN is achieved with two steps. On the one hand, the convolutional layer gives a translation equivariance as it is a linear time invariant system. The translation of the input image will be kept as a transformation of the output. On the other hand, the pooling layer will introduce local invariance. The stack of convolutional layers and pooling layers will then reach a receptive field the same size as input and also enforces global invariance. Inspired by the success of CNN on image related tasks, plenty of CNN generalizations \cite{gens2014deep, henaff2015deep, simonovsky2017dynamic, cohen2018spherical,chidester2018rotation} have been studied in other tasks. \emph{Domain invariance}, which refers to the property that the output is invariant to certain transformation of the input features is a crucial property which can help to generalize CNN to other machine learning applications. The works which introduce domain invariance fall into two categories. One of the categories introduces the invariance by injecting invariant constrains. The other category builds the equivariant network layer then achieves invariance by applying the pooling or normalization layer. In the equivariant network layer, the input is transformed by some group transformation the output is transformed correspondingly. As in the CNN example, the invariance can be achieved by first using equivariant layers then apply the pooling layer. In this dissertation, we will focus on the invariance and equivariance of neural networks and analyze the neural network architecture which can achieve invariance or equivariance. The main works can be summarized as following. \noindent\textbf{The Connections Between Convolutional Architecture and Equivariant Property} Convolutional neural networks have achieved great success in speech, image, and video signal processing tasks in recent years. There have been several attempts to justify the convolutional architecture and to generalize the convolution operation for treatment of other data types such as graphs and manifolds. Based on group representation theory and noncommutative harmonic analysis, it has recently been shown that the so-called group equivariance requirement of a feed-forward neural network necessitates the convolutional architectures. In our work, based on the familiar concepts of linear time-invariant systems, we develop an elementary proof of the same result. The nonlinear activation function, being a necessary components of practical deep neural networks, has been glossed over in previous analyses of the connection between equivariance and convolution. We identify sufficient conditions for the non-linear activation functions to preserve equivariance, and hence the necessity of the group convolution structure. Our analysis method is simple and intuitive, and holds the potential to be applied to more challenging scenarios such as non-transitive domains and multiple simultaneous equivariances. \noindent\textbf{Characteristics of Generalized Convolutional Neural Networks} Based on the analysis method above, a theoretical support for details of network architecture design is then provided in our work. We first analyze the necessary and sufficient condition for a neural network to be group equivariant when the group acts on the sub-domain of input/output. This part gives a theoretical support for how should we combine channels in a neural network layer. Meanwhile, it also gives guidelines for designing neural networks with partial equivariance/invariance. To further investigate the characteristics of generalized convolutional neural networks, we then analyze the multiple equivariance case. The result shows the connection between model parameter sharing and equivariant property. In particular, we find that a model will have more parameter sharing if more equivariances are required. Meanwhile, we establish a universality result for shallow and deep generalized group convolutional neural networks as approximators of continuous group-equivariant functions. After choosing the network architecture, one common question we need to answer is that how many neurons do we want in our hidden layer? We show that the generalized convolution mapping to a quotient space is a projection of the image of a generalized convolution which maps to the maximum quotient space. This can be used to obtain guidelines for choosing the feature size of hidden layer. \noindent\textbf{Neural Networks with Invariant Properties} In the traditional convolutional neural networks, the spatial invariant properties are introduced by adding a global pooling layer after the convolutional layers. For some specific applications, there are still some potential for us to further reduce the model complexity by introduce invariant property in earlier layers. An partial permutation invariant model for learning graph node embedding is introduced based on the classical invariant theory. In the image processing application, an affine equivariant preprocessing method is proposed to build neural networks invariant to affine transformation. \noindent\textbf{Partially Permutation Invariant Graph Node Embedding Model} Graph node embedding aims at learning a vector representation for all nodes given a graph. It is a central problem in many machine learning tasks (e.g., node classification, recommendation, community detection). The key problem in graph node embedding lies in how to define the dependence to neighbors. Existing approaches specify (either explicitly or implicitly) certain dependencies on neighbors, which may lead to loss of subtle but important structural information within the graph and other dependencies among neighbors. This intrigues us to ask the question: can we design a model to give the maximal flexibility of dependencies to each node's neighborhood. In our recent work, we propose a novel graph node embedding method (named \textbf{\OM}) via a novel notion of \textit{partial permutation invariant set function}, to capture any possible dependence. The partial permutation invariant set function is designed based on the set of \textit{invariant basis} with respect to permutation group. Our method 1) can learn an \textit{arbitrary} form of the representation function from the neighborhood, without losing any potential dependence structures, and 2) is applicable to both homogeneous and heterogeneous graph embedding, the latter of which is challenged by the diversity of node types. Furthermore, we provide theoretical guarantee for the representation capability of our method for general homogeneous and heterogeneous graphs. Empirical evaluation results on benchmark data sets show that our proposed {\OM} method outperforms the state-of-the-art approaches on producing node vectors for various learning tasks of both homogeneous and heterogeneous graphs. \noindent\textbf{Learning Models Invariant to Affine Transformations for Image Processing} The way designing invariant/partial invariant neural networks with invariant basis is difficult to extend to groups other than permutation group. Because the invariant basis is expensive to calculate. Even if we get the set of invariant basis, it will be very large and is not helpful to reduce model complexity. An alternative which can introduce invariant property to neural network is adding an equivariant transformer as a pre-processing layer. This equivariant transformer will revert all the affine transformations happens in the input. Thus the model will be invariant to affine transformations. Invariance to affine transformations is desirable property for many computer vision tasks like image classification and motion tracking. Enforcing and taking advantage of such affine invariance property is an essential part for building efficient models for machine learning. However, it has been challenging to build models that are provably affine invariant. Previous works have achieved partial invariance, such as invariance to shifting and to rotation. We propose to build an affine-invariant model in two steps. First, we apply image normalization, which renders the density function represented by the image to have zero mean and identity covariance matrix. The resulting normalized image is then processed by a second stage neural network that is either an equivariant transformer network (ETN) or group convolution networks. We provide proof of invariance and demonstrate the performance improvement of such neural networks in processing images that have been affine transformed.