Title: FRONTAL LOW-RANK RANDOM TENSORS FOR HIGH-ORDER FEATURE REPRESENTATION

Abstract: Representing high-order (second-order or higher) information in deep neural networks is essential in many tasks such as fine-grained visual understanding and multi-modal information fusion. Bilinear models are often used to extract secondorder information. As a basis, extracting higher-order information requires extra computation. In this paper, we propose an approach to representing high-order information via a simple yet effective bilinear form. Specifically, our contribution is two-fold: (1) From the multilinear perspective, we derive a bilinear form of low complexity, assuming that the three-way tensor has low-rank frontal slices.
(2) Rather than learning the tensor entries from data, we sample the entries from different underlying distributions, and prove that the underlying distribution influences the information order. We perform temporal action segmentation experiments to evaluate our method. The results demonstrate that our bilinear form, employed as intermediate layers in deep neural networks, is computationally efficient; meanwhile it is effective as it achieves new state-of-the-art results on public benchmarks.

1. INTRODUCTION:

A standard deep convolutional neural network mainly comprises convolutional layers and pooling layers. Despite effectiveness, such layers can only extract first-order information and hence are not suitable for fine-grained recognition and information fusion. It is reported in the literature that modeling second-order feature interactions (e.g. statistical covariance and feature co-occurrence) is essential for a wide range of visual tasks like fine-grained recognition (Lin et al., 2018b; Kong & Fowlkes, 2017) , human action understanding (Girdhar & Ramanan, 2017; Cherian et al., 2017) and visual question answering (Kim et al., 2018; Fukui et al., 2016) . When considering higher-order information, the extracted features are more discriminative and yield impressive performance (Cui et al., 2017; Koniusz et al., 2017) .

Although modeling high-order feature interaction has many successful applications, most existing methods have a critical drawback: The computational cost increases exponentially with respect to the information order and the input feature dimension. Let us take bilinear pooling for second-order information extraction as an example. Given two feature vectors x ∈ R D X and y ∈ R D Y , a generic bilinear model (Ben-Younes et al., 2017, Eq. (2)) is given by: z = T × 1 x × 2 y, (1) where T ∈ R D X ×D Y ×D Z is a three-way tensor, and the operations × 1 and × 2 are the mode-1 and mode-2 multiplication, respectively. Despite being a powerful scheme, such a model tends to suffer from the curse of dimensionality and intractable computation (Bellman, 2015) . Specifically, the number of free parameters in T grows cubically as the feature dimensionality, i.e. O(D X D Y D Z ), hence limiting its use in large-scale scenarios.

To reduce the complexity, a common solution is to impose specific assumptions on the structure of T in Eq. (1). In the work of Kim et al. (2016) ; Ben-Younes et al. (2017) ; Kong & Fowlkes (2017) , low-rank assumption on T is employed. In the work of Gao et al. (2016) , count sketch is used to extract approximated second-order information, which can be represented by a shorter feature vector than the full second-order information. Although such conventional bilinear pooling methods can extract second-order information effectively, extracting higher-order information requires extra operations (Cui et al., 2017) and may further increase the computational cost.

In this paper, we aim at deriving a simple bilinear model, with which changing the order of information does not involve extra computation. Therefore, our investigations have two aspects: (1) From the multilinear perspective, we assume that each frontal slice of T -but not T itself -is a lowrank matrix. Then we derive a new bilinear form that first reduces the feature dimension and then performs vector outer product. Different from Kim et al. (2016) and Ben-Younes et al. (2017) (2) Rather than learning the model parameters from data, the entries of each frontal slice are determined by random projection matrices drawn from a specific distribution. Our key insight is that, while the low-rank structure allows a reduction in the number of parameters, the loss in representational power is compensated by the random projection matrices. In particular, we show that when these random matrices are sampled with different underlying distributions, the model approximates feature maps of different reproducing kernel Hilbert spaces (RKHSs). For example, when they are sampled from the Rademacher distribution, the model approximates the multiplication of linear kernels (cf. Theorem 1). When they are sampled from the Gaussian distribution with orthogonality constraints, the model approximates multiplication of Gaussian kernels (cf. Theorem 2). Hence, we can explicitly manipulate the model capacity without sacrificing the computational efficiency.

To verify the effectiveness of our method, we perform experiments on fine-grained action parsing, in which our bilinear model with random tensor entries is used as intermediate layers in temporal convolutional deep neural networks. The experimental results show that our method yields superior efficiency and performance to other related methods on different datasets.

Our contributions can be summarized as follows:

• We derive a novel bilinear model with a random three-way tensor. Using low-rank decomposition of each frontal slice, our method significantly reduces the number of parameters of the bilinear model, and hence can serve as a computationally efficient feature fusion operation.

• Based on different tensor entry distributions, we prove that the proposed random tensors can estimate the feature maps to reproducing kernel Hilbert spaces (RKHSs) with different compositional kernels. Therefore, the order of information is influenced by such underlying distributions.

• We combine our method with state-of-the-art deep neural networks for action segmentation and produce superior results.

2. RELATED WORK:

Representing high-order information in practice. Due to the computational cost, second-order information is mostly considered in various practical tasks, such as fine-grained image understanding (Carreira et al., 2012; Gao et al., 2016; Yu & Salzmann, 2018; Koniusz et al., 2017; Li et al., 2017a; Lin et al., 2015; 2018b; a; Kong & Fowlkes, 2017; Li et al., 2018; Wei et al., 2018; Gou et al., 2018) , fine-grained action understanding (Feichtenhofer et al., 2016; Girdhar & Ramanan, 2017; Cherian et al., 2017; Zhang et al., 2019) , visual question answering (Yu et al., 2018; Ben-Younes et al., 2017; Kim et al., 2018; Fukui et al., 2016 ) and beyond. In many studies, second-order information is extracted only once before the classification layer in a deep neural net (Yu & Salzmann, 2018; Lin et al., 2015; 2018b; a; Kong & Fowlkes, 2017; Wang et al., 2017; Diba et al., 2017; Feichtenhofer et al., 2016) . For example, Lin et al. (2018b) compute the vector outer product to merge outputs from two individual CNN streams. Wei et al. (2018) transform CNN features to the compact Grassmann manifold using singular-value decomposition. Such methods either lift the feature dimension from D to D 2 , or introduce expensive computation in both forward and backward passes, and hence are not applicable as intermediate layers in deep neural networks. Consequently, extracting higher-order (≥ 3) information is even more challenging, although it is reported that higher-order information is more discriminative. Koniusz et al. (2017) compute higher-order feature occurrence in the bag-of-words pipeline, rather than in deep neural networks.

Low-rank tensor structure. There exist many investigations on low-rank tensor decomposition for bilinear models. For instance, Kim et al. (2016) assume that each frontal slice of the three-way tensor can be decomposed into two low-rank matrices, and the fusion of the two input features can then be achieved by matrix multiplication and Hadamard product. To improve the performance of visual question answering, Yu et al. ( 2017) introduce more operations after the low-rank bilinear pooling (Kim et al., 2016) such as dropout, power normalization, L2 normalization and so forth. Ben-Younes et al. (2017) rely on Tucker decomposition of the tensor, producing three matrices and a smaller core three-way tensor.

High-order information approximation. Representing high-order information explicitly can lead to combinatorial explosions. To avoid the curse of dimensionality, feature approximation methods based on reproducing kernel Hilbert space (RKHS) theories have been recently investigated. For example, Kar & Karnick (2012) use binary random entries to approximate inner product kernels, especially the p-th order polynomial kernels. Gao et al. (2016) and Pham & Pagh (2013) use tensor sketch to approximate polynomial kernels, which has lower approximation error bound but higher computational cost. Yu et al. ( 2016) use orthogonal random features to approximate feature maps of Gaussian kernels. To boost the computational speed, a structured version with normalized Walsh-Hadamard matrices is proposed. Such feature approximation methods also improve the efficiency of higher-order information extraction. For example, based on count sketch (Gao et al., 2016) , Cui et al. (2017) extract 4 th -order information from CNN features in an efficient manner.

Herein, we design a new bilinear form with lower complexity than Kim et al. (2016 ), Yu et al. (2017) and Ben-Younes et al. (2017) . Also, it provides a generic framework to approximate feature maps of RKHSs with compositional kernels. Via sampling tensor entries from different distributions, our method shows that the output feature vector lies within certain RKHS, and hence we can manipulate the model capacity while retaining the same computational complexity.

3. PROPOSED METHOD:

In this section we first introduce how to decrease the number of parameters in the bilinear model Eq. ( 1) via low-rank assumption. Afterwards, we present our investigations on how to approximate feature maps of kernels via random projection.

3.1. TENSOR FRONTAL LOW-RANK APPROXIMATION:

Here we follow the tensor notations in Kolda & Bader (2009) . Eq. ( 1) can be re-written in terms of matrix-vector multiplication as

EQUATION

where T (3) is the mode-3 matricization of T , vec(•) denotes column-wise vectorization of a matrix, and ⊗ denotes vector outer product. In other words, the bilinear operation in Eq. ( 1) is equivalent to first computing the correlation matrix between the two features and then performing a linear projection.

It follows from Eq. ( 2) that each entry of the output feature vector z is a weighted sum of all the entries in the correlation matrix x ⊗ y, i.e.,

EQUATION

where v := vec(x ⊗ y). If the frontal matrix T [:, :, k] is a rank-one matrix, i.e., T [:, :, k] = e ⊗ f for some e ∈ R D X and f ∈ R D Y , then we can rewrite Eq. (3) as

z k = vec(e ⊗ f ), vec(x ⊗ y) = e, x f , y .

Thus, we define the projection matrices E = [e 1 , e 2 , ..., e M ] T and

F = [f 1 , f 2 , ..., f N ] T for two sets of vectors {e i } M i=1 ⊂ X and {f j } N j=1 ⊂ Y with M ≤ D X and N ≤ D Y . Then, the fusion map φ : R D X × R D Y → R M N can be defined as z := φ(x, y) = vec ((Ex) ⊗ (F y)) .

(4)

If we assume further that T [:, :, k] is a rank-R matrix, i.e., T [:, :, k] = R r=1 e r i ⊗ f r j , we obtain

EQUATION

where

E r = [e r 1 , e r 2 , ..., e r M ] T and F r = [f r 1 , f r 2 , ..., f r N ] T for r = 1, 2, ..., R.

With such a low-rank assumption, we avoid computing the high-dimensional correlation matrix x⊗y, which considerably reduces the model parameters from

D X D Y D Z to R(M D X + N D Y ) with a small value of R.

A similar low-rank assumption is also used in Ben-Younes et al. (2017) and Kim et al. (2016) , in which the two input feature vectors are first projected to a common vector space and then fused via the Hadamard product. Assuming the input feature vectors are of the same dimension D and the output feature vector is of dimension d, then such operation requires O(Dd + d) operations to compute and requires O(Dd) memory to store. In contrast, our method requires O(D

√ d + d) for computation and O(D √ d)

for storage. Since in practice it normally requires more dimensions to represent a higher-order feature, i.e. d D, our method has a consistently better runtime (see Tab. 1) and hence is more suitable to be employed in a sophisticated deep neural network.

3.2. RANDOM PROJECTION:

To compensate for the loss in model capacity caused by the low-rank assumption, we observe that the entries and associated distributions of E and F defined in Eq. ( 4) and Eq. ( 5) can indeed influence the model capacity, without adding or removing learnable parameters, network layers, etc.

Inspired by this observation, we propose to manipulate the model capacity by randomly sampling the entries of E and F from specific distributions and then perform random projection. Unlike an end-to-end learning via back-propagation, our approach provides an alternative way of building expressive representation that is explainable and is simple to use in practice.

Rademacher random projection. Motivated by Kar & Karnick (2012) and Gao et al. (2016) , we specify model parameters, i.e. the projection matrices E r and F r in the bilinear model ( 4) or (5), with random samples from the Rademacher distribution. Below we show that the bilinear model given in Eq. ( 4) unbiasedly approximates, with high probability, a feature map to a reproducing kernel Hilbert space (RKHS), in which the associated kernel is the multiplication of two linear kernels in X and Y, respectively. Theorem 1. Let E r ∈ R M ×D X and F r ∈ R N ×D Y for any r ∈ {1, 2, ..., R} be Rademacher random matrices whose entries are determined by an independent Rademacher random variable σ ∈ {-1, 1}. For any x 1 , x 2 ∈ X and y 1 , y 2 ∈ Y, let z 1 = φ(x 1 , y 1 ) and z 2 = φ(x 2 , y 2 ) be the output features given by Eq. (4). Define a kernel function by k(z 1 , z 2 ) = z 1 , z 2 , then we have

E[k(z 1 , z 2 )] = RM N x 1 , x 2 y 1 , y 2 .

Next, we characterize the error of such kernel approximations. Corollary 1. Let z 1 and z 2 be defined as in Theorem 1.

Let k(z 1 , z 2 ) = 1 R z 1 , z 2 .

Then, the following inequality holds:

EQUATION

for some constants > 0, and p ≥ 1, R ≥ 1, which are independent of the feature dimensions.

Proofs of both results can be found in Appendix A and B. More details on the constants p and R can be found in Kar & Karnick (2012) . To remove the effect of the scaling factors, we rewrite Eq. ( 5) as

EQUATION

Therefore, Eq. ( 7) with binary tensor entries is capable of capturing second-order interactions between two features. We refer this bilinear form as "RPBinary" in the experiment section.

Gaussian random projection. To increase the model capacity, a common approach is to apply the nonlinear activation function ϕ(•), which gives

EQUATION

Inspired by Yu et al. ( 2016), we consider

EQUATION

where R r and S r are diagonal matrices with diagonal entries sampled i.i.d. from the chi-squared distributions χ2 (D X ) and χ 2 (D Y ) with D X and D Y degrees-of-freedom, respectively, P r and Q r are uniformly distributed random orthogonal matrices 2 , and I M ×D X and I N ×D Y are identity matrices with the first M and N rows, respectively. Here, {σ r } R r=1 and {ρ r } R r=1 are tunable bandwidth parameters.

When the nonlinear function in Eq. ( 8) is given by ϕ(Ex) := 1/M [sin(Ex), cos(Ex)] and ϕ(F y) := 1/N [sin(F y), cos(F y)], the resulting representation approximates feature maps to the RKHSs corresponding to a composition of Gaussian kernels (see Appendix C for the proof). Theorem 2. Let E r ∈ R M ×D X and F r ∈ R N ×D Y for any r ∈ {1, 2, ..., R} be random matrices whose entries are determined as in Eq. (9). For any x 1 , x 2 ∈ X and y 1 , y 2 ∈ Y, let z 1 = φ(x 1 , y 1 ) and z 2 = φ(x 2 , y 2 ) be the output features in Eq. (8). Define a kernel function k(z 1 , z 2 ) = z 1 , z 2 , then we have

EQUATION

where

b := R r=1 R r =r+1 E[ ϕ(E r x 1 ), ϕ(E r x 2 ) ]E[ ϕ(F r y 1 ), ϕ(F r y 2 ) ].

A characterization of the variance of k(z 1 , z 2 ) in Theorem 2 is given in Appendix D, which suggests that higher output feature dimension can reduce the variance of k(z 1 , z 2 ). Consequently, just by using the periodic function ϕ(•) and the Gaussian random projection, we can obtain infiniteorder information without extra computational cost. We refer this form as "RPGaussianFull" in the experiment section. In principal, one can extract different types of high-order information by using different nonlinear functions in Eq. ( 8). Further investigations on such problems are currently beyond our scope.

In practice, when used as an intermediate layer in deep neural networks, sin and cos functions are known to be difficult and unreliable to train using back-propagation (Parascandolo et al., 2016) . Therefore, we perform Taylor expansion of sin and cos, and only use the first term. Namely, we approximate sin(Ex) ≈ Ex and cos(Ex) ≈ 1. Then, we can discard the nonlinear function ϕ(•) in Eq. ( 8), and also can apply scaling factors as in Eq. ( 7). We refer this approximated version as "RPGaussian" in our experiments. In addition, we adopt a simpler version 2016), such a simplified version exhibits similar empirical behavior to the original version, especially when the feature dimensionality is high. Moreover, rather than regarding the Gaussian radii as hyper-parameters, we learn them via back-propagation when employing the model ( 7) as an intermediate layer in a deep neural network.

E r = √ D X σ r I M ×DX P r and F r = √ D Y ρ r I N ×DY Q r . According to Yu et al. (

Last but not least, it is instructive to note that, in addition to what we have proposed, the distributions of E and F can be arbitrary. We can even model these distributions using deep generative models, which is the subject of our future work.

4. EXPERIMENTS:

We conduct experiments for the task of fine-grained temporal action segmentation, which aims at assigning each individual frame an action label. In such experiments, the two input features x and Figure 1 : Performance of our RPBinary and RPGaussian model, versus dimension / rank, on datasets 50Salads and GTEA. In each plot, x-axis is the multiplier on the number of matrix rows N , y-axis is the respective performance measure, and colors denote different ranks. y in Eq. ( 7) and Eq. ( 8) are identical, and we set the same number of rows (i.e. M = N ) to matrices E r and F r for all r = 1, . . . , R. Consequently, there only remain two hyper-parameters in the bilinear model, i.e. the rank R and the number of rows N of matrices. The objectives of our experiments are two-fold: (i) To verify the effectiveness of our method, we adopt the temporal convolutional net (TCN) (Lea et al., 2017) due to its simple structure and replace the max pooling in TCN by bilinear pooling as in Zhang et al. (2019) . (ii) To demonstrate how our method can be used in practice, we propose a bilinear residual module to merge the first and second-order information, and combine it with the multi-stage temporal convolutional net (MS-TCN) (Farha & Gall, 2019) to yield state-of-the-art performance.

Datasets and evaluation metrics. We evaluate our method on the 50Salads dataset (Stein & McKenna, 2013) and the GTEA dataset (Fathi et al., 2011; Li et al., 2015) . For a fair comparison, in our experiments with TCN, we use the identical frame-wise features and temporal resolutions as Lea et al. (2017) . Also, in our experiments with MS-TCN, we use the identical frame-wise features and temporal resolutions as Farha & Gall (2019). To evaluate the performance, we use three standard metrics, i.e. frame-wise accuracy, edit score and F1 score as in Lea et al. (2017) and Farha & Gall (2019) . For the F1 score, we consider the intersection-over-union (IoU) ratio of 0.1, 0.25 and 0.5, and denote them as F1@0.1, F1@0.25 and F1@0.5, respectively. Without explicit mentioning, our F1 score means F1@0.1. Detailed definitions of these metrics are explained in Lea et al. (2017) and Farha & Gall (2019) . Since each dataset has several splits, we report the results of cross-validation.

4.1. ACTION SEGMENTATION WITH TCN ARCHITECTURE:

We use the default architecture of TCN (Lea et al., 2017) , which comprises an encoder and a decoder with symmetric modules. The convolutional layer in each individual encoder has 64 and 96 filters, respectively. We train the model using the Adam optimizer (Kingma & Ba, 2014) with a fixed learning rate of 10 -4 . Batch size is set to 8, and the training process terminates after 300 epochs.

Ablation study: Comparison between bilinear forms. In this experiment, we set the rank R = 1 and N = D/2 for our methods where D is the input feature dimension to our bilinear model. The results are shown in the first part of Tab. 1. For the performance evaluation, we repeat the experiment 3 times and report the result with the highest sum of the three metrics. To evaluate the efficiency, we report the runtime per batch (batch size=8) which is the averaged result after training Table 1 : Comparison with different bilinear pooling methods in terms of accuracy/edit score/F1 score and runtime (millisecond). For each metric and each setting, the best result is in boldface. "LearnableProjection" indicates E and F in Eq. ( 7) are learned via back-propagation. "RPBinary" indicates the model Eq. ( 7) with Rademacher random projection. "RPGaussianFull" and "RPGaussian" indicate the model Eq. ( 8) with and without ϕ(•), respectively, in which Gaussian random projection is employed. In the column of complexity, D and d denote the input and output feature dimension of our bilinear model, respectively. with the first split for 300 epochs for each dataset. Overall, the results suggest that "RPGaussian" and "RPBinary" have comparable performances, and outperform "LearnableProjection" and "RP-GaussianFull". While "LearnableProjection" is more flexible, it might require a more sophisticated training to achieve the same performance as our random projection methods. Also, we suspect that the inferior performance of "RPGaussianFull" is due to the difficulty of training.

In addition, we compare our methods with three widely used bilinear pooling methods, i.e., Compact (Gao et al., 2016) , Hadamard (Kim et al., 2016) and FBP (Li et al., 2017b) . We use the same output feature dimension for fair comparison. The results are shown in the second part of Tab. 1. They suggest that these three methods perform inferior or comparably in terms of the three metrics of action parsing, and are clearly less efficient, than our methods.

Ablation study: Investigation on the hyper-parameters of our bilinear forms. Here we investigate the influence of the rank and the output feature dimension of RPGaussian and RPBinary, with the bilinear model in Eq. ( 7). Fig. 1 shows the dependence of the model performance on ranks R ∈ {1, 2, 4, 8, 16} and matrix rows N ∈ {1, 2, 4, 8} × [ √ D] where [n] denotes the nearest integer to n. In this case, the output feature dimension is then {1, 4, 16, 64} × D. In all plots, the performance increases consistently with the matrix row N (hence the output feature dimension). This result is in line with our theoretical analysis on the kernel approximation error bound (see Corollary 1 and Appendix D): Larger values of M and N can yield lower variance upper bounds, hence better kernel approximation. One can also observe that the performance saturates when further increasing the output feature dimension. This is due to the limited capacity of the corresponding RKHS. Moreover, one can observe that increasing the rank may not consistently yield better performance. An optimal rank depends on the dataset and the applied bilinear model. 50 Salads GTEA Acc. Edit F1@0.1 F1@0.25 F1@0.5 Acc. Edit F1@0.1 F1@0.25 F1@0. In this section, we demonstrate how to effectively incorporate our method into the state-of-the-art action parsing network, MS-TCN (Farha & Gall, 2019) , to superior performance.

Implementation Details. Based on our previous experimental results, we set rank R = 4 and N = D/2 for our bilinear model. Furthermore, we propose a bilinear residual module to merge the first and the second-order information, as illustrated in Fig. 2 . First, we use bilinear pooling to extract the second-order information, and then use a regularized power normalization (Zhang et al., 2019) to densify the feature and use channel-wise max normalization to re-scale the feature value (Lea et al., 2017) . Afterwards, we use a convolution layer to reduce the feature dimension to the number of classes. Since the second-order information tends to partition an action into smaller segments (Zhang et al., 2019, Fig. 1 ), we use a larger convolution receptive field 25 according to Lea et al. (2017) . To prevent overfitting we use a dropout layer, and then we compute the average between the first-order information and the second-order information. Result. We compare our method with several state-of-the-art methods on the action segmentation task. As shown in Tab. 2, our models (especially RPBinary and RPGaussian) consistently outperform the state-of-the-arts (TCN, TDRN, MS-TCN), validating the effectiveness of the proposed bilinear model. Note that, even with RPGaussianFull, which is hard to train by back-propagation, our bilinear form achieves competitive performance on the GTEA dataset. For a fair and complete comparison, we further integrate three widely used light-weight bilinear models into the MS-TCN model, namely, Compact (Gao et al., 2016) , Hadamard (Kim et al., 2016) and FBP (Li et al., 2017b) . Again, the proposed bilinear models show superior performance on most of the evaluation metrics. Together with the results presented in Tab. 1, they clearly demonstrate the representational power and the computational efficiency of the proposed bilinear models.

5. CONCLUSION:

In this work, we propose a novel bilinear model for fusing high-dimensional features. To reduce the number of model parameters, we utilize low-rank tensor decomposition. Instead of using elementwise product as in other works, we use the outer product of the features to model the high-order correlations among feature channels. To enrich the model representiveness while retaining the number of parameters, we use random projection to approximate feature maps to reproducing kernel Hilbert spaces associated with kernel compositions. To validate the effectiveness of our method, we perform extensive experiments on the action segmentation task, and have achieved state-of-the-art performance on challenging benchmarks. Our bilinear pooling operation is lightweight, easy to use, and can serve as a natural tool for fine-grained visual understanding and information fusion. In the future we will investigate how to combine our work with the deep generative models. That is, instead of sampling entries from a pre-defined distribution, we aim to learn to model these distributions using deep generative models. 

APPENDIX A PROOF OF THEOREM 1:

Proof. It follows from Eq. ( 5) and the property of an inner product of rank-one operators that

EQUATION

Then, it follows that

E[k(z 1 , z 2 )] = R r=1 R r =1 M i=1 E[ e r i , x 1 e r i , x 2 ]   N j=1 E[ f r j , y 1 f r j , y 2 ]   = R r=1 M i=1 E[ e r i , x 1 e r i , x 2 ]   N j=1 E[ f r j , y 1 f r j , y 2 ]   + R r=1 R r =r+1 M i=1 E[ e r i , x 1 e r i , x 2 ]   N j=1 E[ f r j , y 1 f r j , y 2 ]   = RM N x 1 , x 2 y 1 , y 2 .

The last equation follows from Kar & Karnick (2012, Lemma 2) and the fact that e r i and f r j are zero-mean random variables for all i = 1, . . . , M , j = 1, . . . , N and r = 1, . . . , R.

B PROOF OF COROLLARY 1:

Proof. Let W ij := e i , x 1 e i , x 2 f j , y 1 f j , y 2 for i = 1, . . . , M and j = 1, . . . , N . For each W ij , it follows from Kar & Karnick (2012, Lemma 4) 

that -p 2 f (p R2 ) 2 ≤ W ij ≤ p 2 f (p R2 ) 2 ,

where we assume without loss of generality that p ≥ 1 and R ≥ 1. In our case, f (x) = x. Then, we have -p

4 R4 ≤ W ij ≤ p 4 R4 . Let S MN := 1 R M i=1 N j=1 W ij . Hence, we have E[S MN ] = M N x 1 , x 2 y 1 , y 2 .

Then, it follows from Hoeffding's inequality that, for all > 0,

EQUATION

)

This concludes the proof.

C PROOF OF THEOREM 2 ϕ(E r x 1 ), ϕ(E r x 2 ) ϕ(F r x 1 ), ϕ(F r x 2 ) .

Hence, with E r = 1 σ r I M ×D X R r P r and F r = 1 

D APPROXIMATION ERROR BOUND FOR GAUSSIAN RANDOM PROJECTION:

We characterize the variance of k(z 1 , z 2 ) used in Theorem 2. To simplify the presentation, we focus on the case that R = 1.

Corollary 2. Let z 1 , z 2 , and k(z 1 , z 2 ) be defined as in Theorem 2, as well as R = 1, a = x 1x 2 2 2 /σ and b = y 1 -y 2 2 2 /ρ. Then, there exist functions f and g such that

EQUATION

where

A = 1 2M 1 -e -a 2 2 - M -1 D X e -a 2 a 4 + f (a) D 2 X , C = exp - b 2 2 2 B = 1 2N 1 -e -b 2 2 - N -1 D Y e -b 2 b 4 + g(b) D 2 Y , D = exp - a 2 2 2 .

Proof. Let R=1. Then, we have

k(z 1 , z 2 ) = ϕ(Ex 1 ), ϕ(Ex 2 ) U ϕ(F x 1 ), ϕ(F x 2 ) V .

Since U and V are independent, we have

EQUATION

where 

(

Var(U ) ≤ 1 2M 1 -e -a 2 2 - M -1 D X e -a 2 a 4 + f (a) D 2 X Var(V ) ≤ 1 2N 1 -e -b 2 2 - N -1 D Y e -b 2 b 4 + g(b) D 2 Y .

Substituting everything back into (14) yields the result.

:

D and d are input and output feature dimensions of the bilinear model, respectively; usually, D d.

Specifically, P r and Q r are uniformly distributed on the Stiefel manifold(Yu et al., 2016; Muirhead, 2009).

Figures and Tables:

, that first lift the feature dimension and then perform Hadamard product, our method has runtime complexity O(D √ d + d) and space complexity O(D √ d) compared to O(Dd + d) and O(Dd) in their works 1 . Thus, our bilinear operation is lightweight and can be employed in deep neural networks as intermediate layers in an efficient manner.

Figure 2: A combination of MS-TCN Farha & Gall (2019) and our bilinear pooling method, in which the blue layers are proposed by us and the orange layers are proposed by MS-TCN.

Our bilinear residual module is applied at the end of each single stage of MS-TCN. To conduce fair comparison with the baseline MS-TCN model, we keep other model configurations and the loss function (including the hyper-parameters) unchanged. Similarly to Farha & Gall (2019), we use the Adam (Kingma & Ba, 2014) optimizer with a learning rate of 0.0005. The batch size is set to 1.

Let R = 1. Then, k(z 1 , z 2 ) := z 1 , z 2 = ϕ(Ex 1 ), ϕ(Ex 2 ) ϕ(F x 1 ), ϕ(F x 2 ) where ϕ(Ex) := 1 √ M [sin(e 1 x), . . . , sin(e M x), cos(e 1 x), . . . , cos(e M x)], ϕ(F y) := 1 √ N [sin(f 1 y), . . . , sin(f M y), cos(f 1 y), . . . , cos(f M y)].With E = 1 σ I M ×D X RP and F = 1 ρ I N ×D Y SQ, we have E[k(z 1 , z 2 )] = E[ ϕ(Ex 1 ), ϕ(Ex 2 ) ]E[ ϕ(Fy1 ), ϕ(F y 2 ) ] equality follows from Yu et al. (2016, Theorem 1). For R > 1, we have k(z 1 , z 2 ) := z 1 , z 2 =

ρ r I N ×D Y S r Q r , (E r x 1 ), ϕ(E r x 2 ) ]E[ ϕ(F r y 1 ), ϕ(F r y 2 ) ] = R r=1 E[ ϕ(E r x 1 ), ϕ(E r x 2 ) ]E[ ϕ(F r y 1 ), ϕ(F r y 2 ) ] (E r x 1 ), ϕ(E r x 2 ) ]E[ ϕ(F r y 1 ), ϕ(F r y 2 ) ] (E r x 1 ), ϕ(E r x 2 ) ]E[ ϕ(F r y 1 ), ϕ(F r y 2 ) ] E[ ϕ(E r x 1 ), ϕ(E r x 2 ) ]E[ ϕ(F r y 1 ), ϕ(F r y 2 ) ].

E[U ]) 2 = (E [ ϕ(Ex 1 ), ϕ(Ex 2 ) ]) 2 Var(U ) = Var ( ϕ(Ex 1 ), ϕ(Ex 2 ) ) (E[V ]) 2 = (E [ ϕ(F y 1 ), ϕ(F y 2 ) ]) 2 Var(V ) = Var ( ϕ(F y 1 ), ϕ(F y 2 ) )It follows from Yu et al. (2016, Theorem 1) that (E[U ]) 2 = expand b = y 1 -y 2 2 2 /ρ. Then, by Yu et al. (2016, Theorem 1), there exists a function f and g such that

Comparison with other models on temporal action segmentation task. The best results are in boldface, the second-best results are underlined.

Table content: <table/>

Kaicheng Yu and Mathieu Salzmann. Statistically-motivated second-order pooling. In Proceedings of the European Conference on Computer Vision (ECCV), pp. 600-616, 2018. Zhou Yu, Jun Yu, Jianping Fan, and Dacheng Tao. Multi-modal factorized bilinear pooling with co-attention learning for visual question answering. IEEE International Conference on Computer Vision (ICCV), pp. 1839-1848, 2017.

Table content: <table><tr><td>Zhou Yu, Jun Yu, Chenchao Xiang, Jianping Fan, and Dacheng Tao. Beyond bilinear: Generalized</td></tr><tr><td>multimodal factorized high-order pooling for visual question answering. IEEE Transactions on</td></tr><tr><td>Neural Networks and Learning Systems, 29(12):5947-5959, 2018.</td></tr><tr><td>Yan Zhang, Siyu Tang, Krikamol Muandet, Christian Jarvers, and Neumann. Local temporal</td></tr><tr><td>bilinear pooling for fine-grained action parsing. In Proceedings IEEE Conf. on Computer Vi-</td></tr><tr><td>sion and Pattern Recognition (CVPR), June 2019. URL https://arxiv.org/abs/1812.</td></tr><tr><td>01922.</td></tr></table>

Peer review (iclr2020):
In this paper, a bilinear form based on a 3D tensor with low rank frontal slices is proposed in order to reduce the number of operations and memory requirements. Additionally, it is proved that, if factor matrices are randomly chosen and following predefined distributions, then the obtained fusion map is an unbiased estimator of some specific RKHS operators. I found interesting the fact that, instead of learning the projection matrices, this method proposes using randomly generated matrices. However, it is not clear the advantage of using randomly generated matrices in terms of computation cost and performance compared with matrices learned from data. Below, I list the issues of the paper: - In this paper, it is suggested that using random matrices is better than learning them from data, but it is not clear what is the advantage. From the computational point of view, it is intuitive that learning matrices will increase the computation cost but there is no comparison or theoretical evaluation for this. Also, it is not clear if the performance using learned matrices will be better or worse than the proposed in the randomized algorithm. A comparison against learned projection matrices would clarify this point. - The authors prove that using random matrices can be seen as an approximation of using RKHS (Theorem 1 and 2). However, what is the computational cost of using the RKHS operators instead? This should be clarified to highlight the advantage of the method. Additionally, comparisons with experiments using RKHS operators could give a better evaluation of the method. - In the Introduction, it is suggested that standard deep convolutional neural networks extract only first-order information. I cannot agree with this. In fact, the use of nonlinear mappings such as sigmoid or ReLu functions has the effect of introducing higher order information. I think this should be clarified in the paper. - In page 3, it is mentioned that “Via sampling tensor entries from different distributions…”, but I see that what is actually controlled is the distribution of projection matrices entries instead, which, of course affects the distribution of tensor entries. I think this should be clarified in the paper. - Quality of plots in Fig. 1 are rather low. I would suggest to use bigger fonts, to set the same y-axis limits in each row, and to use thicker lines, etc.