{'fraction_non_alphanumeric': 0.03364974705848917, 'fraction_numerical': 0.012561814357983288, 'mean_word_length': 4.596055979643766, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 1, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 1, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Submodular Mini-Batch Training in Generative Moment Matching Networks

Generative moment matching network (GMMN), which is based on the maximum mean discrepancy (MMD) measure, is a generative model for unsupervised learning, where the mini-batch stochastic gradient descent is applied for the update of param- eters. In this work, instead of obtaining a mini-batch randomly, each mini-batch in the iterations is selected in a submodular way such that the most informative subset of data is more likely to be chosen. In such a framework, the training objective is reformulated as optimizing a mixed continuous and submodular function with a cardinality constraint. A Majorization Minimization-like algorithm is used to iteratively solve the problem. Specifically, in each iteration of the training process, a mini-batch is first selected by solving a submodular maximization problem, and then the mini-batch stochastic gradient descent is conducted. Our experiments on the MNIST and Labeled Faces in the Wild (LFW) databases show the effectiveness of the submodular mini-batch training in the GMMN frameworks.


Introduction
Deep generative models (DGMs) [14] characterize the distribution of observations with a deeper structure of hidden variables under non-linear transformations. Typical DGMs include generative adversarial network (GAN) [3] and generative moment matching network (GMMN) [9]. Unlike GAN, whose structure involves both discriminative and generative models, the architecture of GMMN consists of generative models, and the training objective for GMMN aims to minimize the maximum mean discrepancy (MMD) [4] based loss function by applying the stochastic gradient descent. A detailed description of the GMMN architecture is introduced in Section 5. Besides, the usage of kernels brings about the computation complexity of the objective scales quadratically with the amount of data, thus the mini-batch stochastic gradient descent is required for updating parameters [11].
Traditionally, in the GMMN or other deep models training process, the mini-batch is iteratively chosen in a randomized way [5]. For example, the mini-batch can come from partitioning the shuffled training data or it can be randomly chosen from the data in each iteration. However, the randomized way cannot ensure the selected subset is the most informative for training in each iteration [12]. Furthermore, it is likely that extremely peculiar outliers are randomly collected though they are actually redundant. To overcome the problems, our work reformulates the objective of GMMN as a mini-max mixed continuous and submodular optimization, where some variables are real values and the others are restricted to the subsets corresponding to the mini-batch.
The introduction of submodularity in the objective function comes from the fact that although it is an NP-Hard problem to select the most informative subset, an approximated solution obtained by solving the submodular maximization guarantees a constant approximation factor to the optimal value. More specifically, a function f : 2 V → R + is said to be submodular if for any item a ∈ V \B and subsets Additionally, there exist effective approximation algorithms which can return solutions with constant approximation factors guaranteed in poly-nominal time [2].
The main contribution of the work is to construct a mixed continuous and submodular optimization problem based on the MMD function and provide efficient algorithms for the submodular mini-batch training in the GMMN framework. Besides, several ways are proposed to reduce computational overhead brought by the mini-batch selection. We tested the related methods on the MNIST [16] and Labeled Faces in the Wild (LFW) [6] databases in two GMMN frameworks: one is based on the data space networks, and another is based on the auto-encoder code space networks [13].
Although the mixed continuous and submodular optimization formulation for the mini-batch training is restricted to GMMN and the unsupervised tasks in this work, it motivates our future work in studying the generalization of our methods to other deep learning models and related supervised tasks based on deep learning.

Maximum Mean Discrepancy
Maximum mean discrepancy measures a divergence between two distributions given only samples extracted from each [4]. Specifically, given two sets sampled from distributions P A and P B respectively, the MMD measure L M M D 2 for the two distributions is defined in (1), where φ is the identity function which matches higher order moments, and k(·, ·) is a kernel function that replaces the inner product between the φ vectors. If universal kernels lie in the Hilbert space, MMD is 0 if and only if the two distributions P A and P B are equal. Besides, the kernel function employed in our work is the Gaussian kernel k(x, x ) = exp(− 1 2σ ||x − x || 2 ), where σ is the bandwidth parameter.
When the MMD measure is taken as a loss function with respect to the GMMN parameters w, the MMD loss function is modified as (2), where f (s; w) is a non-linear transformation of the input s.
k(X n , f (s n ; w)) The update of parameters w in GMMN aims to minimize the MMD loss function based on the back-propagation algorithm. Due to the quadratically computational complexity led by the usage of the kernel, the mini-batch stochastic gradient descend is applied in the back-propagation training process. In addition, the selection of the mini-batch normally follows a randomized way.

The Mixed Continuous and Submodular Optimization Framework
The selection of the mini-batch is controlled by introducing the submodular factors into the MMD objective function. So the former MMD loss function L M M D 2 (w) is reformulated to a new objective (3), where w denotes the parameters of the neural networks, the set A represents a variable corresponding to the mini-batch, L M M D 2 (w; A) is the modified MMD loss function, F (A; w) is designed as a submodular function, and λ denotes a regularization term.
suggests that the loss function of the parameters w relies on the selected subset A, and is explicitly shown in (4). Similarly, F (A; w) depends on the current parameters w and needs to be a monotone submodular function for selecting a subset A as shown in (5).
The monotone submodularity of MMD needs to satisfy the conditions in Corollary 1 [8]. Besides, the regularization term λ decides the representation capability of the mini-batch: at early stages, it is preferred to provide a large λ such that a more diverse subset can be selected to reveal a whole picture of the data distribution. However, at late stages, a small λ is expected for regions that are still hard to predict. Corollary 1. Let the kernel matrix K ∈ R n * n be element-wise non-negative, with equal diagonal Thus, the problem is reformulated as a mini-max optimization problem with a cardinality constraint as shown in (6), where C refers to the maximum number of the elements in the subset A.
Further, the optimization problem can be reduced to minimize a piecewise function, where each piece is defined by the subset A that obtains the maximum in the corresponding interval of w. More specifically, given the parameters w t and the subset A t at iteration t, it is assumed that there exists an optimal A * which solves (7).
However, it is normally NP-Hard to find A * t in polynominal time. Since (7) is an addition of a modular function [10] and a monotone submodular function, the combinatorial problem (7) is indeed a monotone submodular optimization. Thus, a sub-optimal approximated solutionÂ can be ensured within an interval of w t such that (8) is satisfied, where α is a constant approximation factor between When updating w at iteration t + 1, we actually minimize the objective function L mix ). Next, we will show the approximated solution based on the formulation finally gets converged to a local optimum. Lemma 2. Given a subset A, the MMD loss function L mix M M D 2 (w; A) is differentiable, and strongly convex for a constant M > 0.
Proposition 3. Let A * t andÂ t separately represent an optimal subset and a submodular subset. w * t andŵ t correspond to the solutions of (9) and (10) respectively. Then, the inequalities (11) and (12) are satisfied.
Proof. In (11), the first inequality comes from (8), the second one is from (10) and the third one is by the submodular property.
Then, by the Lemma 2 and the 2nd order Taylor expansion, we obtain (13), where ∇ w denotes the partial differential with respect to w.
By ∇ w L(w * t ; A * t ) = 0 and the inequality (11), Further, with the decrease of L mix Then, we obtain (15). When goes to 0,ŵ T gets converged to a local optimal w * T .

Algorithms
In this section, we show the related algorithms for the continuous and submodular optimization framework as introduced in Section 3. First, we propose a Majorization Minimization-like algorithm for solving (6). The steps of the algorithm are shown in Algorithm 1, where steps 4-10 share the same λ value, and this decreases by a factor of β every p iterations. In each iteration, A t andŵ t are updated in an alternative way. At the final iteration T ,ŵ T gets converged to the optimal parameters w * . In addition, the update ofŵ t+1 at the step 8 is based on the mini-batch stochastic gradient descent, and the selection of A t+1 is based on the submodular maximization algorithm. for t ∈ {0, 1, ..., p} do: 5.
Get a new set of samples X s .

6.
Update all k(X n , f (s n ; w)) and f (s n ; w).

end while
Based on the conditions in Corollary 1, F (A; w) can be designed as a monotone submodular function, thus the submodular maximization can be solved by a simple greedy algorithm guaranteeing an approximation factor [1]. The procedures of the algorithm are shown in Algorithm 2. The approximated algorithm returned by the greedy algorithm ensures a constant factor to the potential optimal solution. The approximated factor relies on the submodular factor and has a lower bound 1 − e −1 [2]. More specifically, where k F ∈ [0, 1] is a submodular curvature (17) associated with the submodular function F .
Algorithm 2 The Greedy Algorithm 1. Input: The precomputed kernel matrices of the data, and the cardinality constraint C. Since the greedy algorithm finds an approximated solution with a computational complexity O(N C), the computational overhead of the algorithm is relatively high when the input data are sufficiently large. Although the accelerated greedy algorithm can significantly speed up the greedy algorithm averagely, its computational complexity reaches the same level as the naive greedy algorithm in the worst case. So, a more efficient algorithm, namely the semi-gradient ascent algorithm [7], is applied in our work as shown in Algorithm 3.

Algorithm 3 The Semi-gradient Ascent Algorithm for Submodular Maximization
1. Start with an arbitrary X 0 .

repeat: 3.
Pick a semi-gradient h Xt of the submodular function F at X t .
The semi-gradient ascent algorithm is to iteratively compute the semi-gradient h X derived from the extreme points of a sub-differential ∂ F (X) of a submodular function F for a set X ⊆ V . ∂ F (X) is defined in (18), and the extreme points of ∂ F (X) are computed via Theorem 4.
In the step 4 of Algorithm 3, m h X t (X) is a modular function and can be taken as a lower bound of the submodular function F (X). m h X t (X) is explicitly defined in (20). At iteration t, we actually maximize m h X t (X) instead of F (X t ) because the maximization of m h X t (X) is quite simple and the computational overhead is thus significantly reduced.

Experiments
This section will explain the GMMN architectures in our work, and then show our simulation results on the two databases: MNIST and the Labeled Faces in the Wild (LFW). The analysis of the results and computational overhead are also included.

The GMMN architectures
There are two types of networks applied in our experiments: one is GMMN applied in the data space and another is GMMN applied in the code space of an auto-encoder (AE) [15]. The two architectures are shown in Figure 1, where (a) illustrates a workflow of GMMN and (b) demonstrates the structure of an auto-encoder.
As to the data space network, GMMN learns a deterministic mapping from samples of a simply sample distribution to samples from the data distribution. In our work, the GMMN architecture consists of the input samples of the uniform prior distributed between −1 and 1, 4 hidden layers with ReLU units, and an output sigmoid layer. To generate a sample of GMMN, we only need to sample from the uniform prior and then pass the sample through the neural network to get the GMMN samples. The training of the GMMN parameters is based on the mixed continuous and submodular optimization framework. On the other hand, regarding the code space of auto-encoder, GMMN+AE is designed to bootstrap an auto-encoder for representing a high-dimensional data in a low-dimensional code space. This allows to capture sufficient statistical information so that the original data can be reliably reconstructed. An auto-encoder is first learned to produce a code representation of the input data, and then weights of the auto-encoder are frozen before applying GMMN to minimize the MMD between the generated codes and data codes.

Experimental setup
Our experiments are based on two datasets: MNIST and LFW. MNIST is a dataset for the task of digit recognition, and there are 50000, 10000, and 10000 data used for training, validation, and test respectively. LFW is a dataset for the task of unconstrained face recognition, which is composed of 13000 images of faces labeled with the name of the person pictured. We randomly split all the data into 11000 training data, 1000 validation data, and 1000 test data.
The architecture of the GMMN is set to 10-64-256-256-I, where I means the dimension of the input data, 10 corresponds to the dimension of samples, and 64-256-256 refer to the structure of the hidden layers. Besides, in the GMMN training process, the mini-batch size is set to 1000, and for each mini-batch a set of 1000 samples was generated from the network.
Regarding the configurations of the GMMN+AE, the auto-encoder is first learned followed by the bootstrap by GMMN. The auto-encoder for MNIST had 4 hidden layers in total, 2 layers (1024-32) for the encoder and 2 layers (32-1024) for the decoder. On the other hand, the auto-encoder for LFW had 6 hidden layers in total, 3 layers (1024-1024-32) for the encoder and 3 layers (32-1024-1024) for the decoder. The encoder and decoder had mirrored architectures, and sigmoid non-linearities were used in all layers of the auto-encoder. Cross entropy was taken as the reconstruction loss function.
Standard layer-wise pre-training was first conducted, and then all layers were fine-tuned jointly. GMMN was then trained to model the coder layer distribution using the proposed MMD objective on the final encoding layer.

Experimental Results
The experimental results were evaluated on the MMD loss measure as defined in (1). A smaller MMD loss value between the samples and real data implies the output distribution of GMMN is better approximated to the potential data distribution. In addition, we compared the performance of the mini-batch training approaches based on our continuous and submodular objective function and the randomized one. It is expected our approach can lead to better distribution consistence, while the computational overhead is marginal compared to the overall time consumed in the training process.
The experimental results of the GMMN in the data space are shown in Figure 2 and Figure 3, while the results of GMMN-AE are shown in Figure 4 and Figure 5.  The results consistently demonstrate that the curve for the MMD cost incurred by the submodular mini-batch training maintains lower values than that obtained by the randomized mini-batch training. Specifically, our method obtains more gains during the first few iterations, while keeping a relatively marginal gain when GMMN finally gets converged.    Table 1 shows the average computational overhead of the mini-batch selection compared to the total time consumed in one iteration of the training process. For comparison, the size of the mini-batch is set to 1000 for the validation and test datasets in MNIST and LFW. The results show that the submodular mini-batch selection only takes up a small fraction of the total time consumed in the training process.

Conclusion and Future Work
This work studies the submodular mini-batch training for the GMNN training in the data space and auto-encoder code space. A mixed continuous and submodular optimization framework is formulated and a Majorization Minimization-like algorithm is put forward to alternatively select the mini-batch and update the parameters of the neural network. In addition, the semi-gradient ascent submodular algorithm is applied to reduce the high computational overhead of the greedy algorithm by maximizing a modular lower bound of the submodular function. The experimental results on the MNIST and LFW databases show that the mini-batch training method obtains more gains in terms of the MMD cost, while the computational overhead incurred by the submodular mini-batch selection takes up relatively a small fraction of the total time consumed in the training process.
Future work includes a generalization of our mini-batch training approach to other deep learning models and related supervised deep learning tasks, such as automatic speech recognition, computer vision and natural language processing.