Title: AN ANALYSIS OF COMPOSITE NEURAL NETWORK PERFORMANCE FROM FUNCTION COMPOSITION PER-SPECTIVE

Abstract: This work investigates the performance of a composite neural network, which is composed of pre-trained neural network models and non-instantiated neural network models, connected to form a rooted directed graph. A pre-trained neural network model is generally a well trained neural network model targeted for a specific function. The advantages of adopting such a pre-trained model in a composite neural network are two folds. One is to benefit from other's intelligence and diligence, and the other is saving the efforts in data preparation and resources and time in training. However, the overall performance of composite neural network is still not clear. In this work, we prove that a composite neural network, with high probability, performs better than any of its pre-trained components under certain assumptions. In addition, if an extra pre-trained component is added to a composite network, with high probability the overall performance will be improved. In the empirical evaluations, distinctively different applications support the above findings.

1. INTRODUCTION:

Deep learning has been a great success in dealing with natural signals, e.g., images and voices, as well as artifact signals, e.g., nature language, while it is still in the early stage in handling sophisticated social and natural applications shaped by very diverse factors (e.g., stock market prediction), or resulted from complicated processes (e.g., pollution level prediction). One of distinctive features of the complicated applications is their applicable data sources are boundless. Consequently, their solutions need frequent revisions. Although neural networks can approximate arbitrary functions as close as possible (Hornik, 1991) , the major reason for not existing such competent neural networks for those complicated applications is their problems are hardly fully understood and their applicable data sources cannot be identified all at once. By far the best practice is the developers pick a seemly neural network with available data to hope for the best. The apparent drawbacks, besides the performance, are the lack of flexibility in new data source emergence, better problem decomposition, and the opportunity of employing proven efforts from others. On the other hand, some adopts a composition of several neural network models, based on function composition using domain knowledge.

An emerging trend of deep learning solution development is to employ well crafted pre-trained neural networks (i.e., neural network models with instantiated weights), especially used as a component in a composited neural network model. Most popular pre-trained neural network models are well fine tuned with adequate training data, and made available to the public, either free or as a commercial product. During the training phase of composite neural network, the weights of pre-trained models are frozen to maintain its good quality and save the training time, while the weights of their outgoing edges are trainable. In some cases as in the transfer learning, the weights of pre-trained neural network are used as initial values in the training phase of composite neural network. It is intuitive that a composite neural network should perform better than any of its components. The ensemble learning (Freund & Schapire, 1997; Zhou, 2012) and the transfer learning (Galanti et al., 2016) have great success and are popular when pre-trained models are considered. However, the following example shows some aspects missed by these two methods, and requests for more complicated composite function.

Example 1. Assume there is a set of locations indexed as X = {(0, 0), (0, 1), (1, 0), (1, 0)} with the corresponding values Y = (0, 1, 1, 0). Obviously, the observed function is the XOR (Goodfellow et al., 2016) . Now consider three models: f 1 (x 1 , x 2 ) := x 1 , f 2 (x 1 , x 2 ) := x 2 , and f 3 (x 1 , x 2 ) := x 1 x 2 . Their corresponding output vectors are (0, 0, 1, 1), (0, 1, 0, 1), (0, 0, 0, 1) with bit-wise accuracy 50%, 50%, 25%, respectively. This means that the AdaBoosting algorithm will exclude f 1 and f 2 in the ensemble since their coefficients are 1 2 ln 1-50% 50% = 0. On the other hand, in the transfer learning, f 3 is fine-tuned by applying the gradient descent method with respect to L2 loss on wf 3 = wx 1 x 2 to transfer the source task distribution to that of the target task. The result comes to w = 0, and f 3 is excluded. Now consider g 1 (x 1 , x 2 ) = α 1 f 1 + α 2 f 2 and apply the back-propagation method with respect to the L2 loss. The results are α 1 = α 2 = 1 3 , with loss 4 3 . If further define g 2 (x 1 , x 2 ) = w 1 g 1 + w 2 f 3 , the back-propagation yields g 2 = 3g 1 -2f 3 = x 1 + x 2 -2x 1 x 2 with the output (0, 1, 1, 0). The final g 2 computes Y with loss 0. This example shows the power of composite function.

Composite Neural Network. In the transfer learning, how to overcome the negative transfer (a phenomenon of a pre-trained model has negative impact on the target task) is an important issue (Seah et al., 2013) . In the ensemble learning, it is well known that the adding more pre-trained models, it is not always true to have the better accuracy of the ensemble (Zhou et al., 2002) . Furthermore, Opitz & Maclin (1999) pointed that the ensemble by boosting having less accuracy than a single pre-trained model often happens for neural networks. In the unsupervised learning context, some experimental research concludes that although layer-wise pre-training can be significantly helpful, on average it is slightly harmful (Goodfellow et al., 2016) . These empirical evidences suggest that in spite of the success of the ensemble learning and the transfer learning, the conditions that composite neural network can perform better is unclear, especially in the deep neural networks training process. The topology of a composite neural network can be represented as a rooted directed graph. For instance, an ensemble learning can be represented as 1-level graph, while a composite neural network with several pre-trained models that each is designed to solve a certain problem corresponds to a more complicated graph. It is desired to discover a mathematical theory, in addition to employing domain knowledge, to construct a composite neural network with guaranteed overall performance. In this work, we investigate the mathematical theory to ensure the overall performance of a composite neural network is better than any a pre-trained component, regardless the way of composition, to allow deep learning application developer great freedom in constructing a high performance composite neural network.

Contributions.:

In this work, we proved that a composite neural network with high probability performs better than any of its pre-trained components under certain assumptions. In addition, if extra pre-trained component is added into a composite network, with high probability the overall performance will be improved. In the empirical evaluations, distinctively different applications support the above findings.

2. PRELIMINARIES:

In this Section, we introduce some notations and definitions about composite neural network. Parameters N ,K, d, d j , d j1 , and d j2 are positive integers. Denote {1, ..., K} as [K] and [K] ∪ {0} as [K] + . Let σ : R → R be a differentiable activation function, such as the Logistic function σ(z) = 1/(1 + e -z ) and the hyperbolic tangent σ(z) = (e z -e -z )/(e z + e -z ). For simplicity of notation, we sometimes abuse σ as a vector value function. A typical one hidden layer neural network can be formally presented as w 1,1 σ d i=1 w 0,i x i + w 0,0 + w 1,0 .We abbreviate it as f σ,W (x), where W is the matrix defined byw 1,1 , w 1,0 , ..., w 0,1 , w 0,0 . Recursively applying this representation can obtain the neural network with more hidden layers. If there is no ambiguity on the activation function, then it can be skipped as f W (x). Now assume a set of neural networks {f Wj (x j )} K j=1 is given, where W j is the real number matrix defining the neural network f Wj : R dj 1 ×dj 2 → R dj , and x j ∈ R dj 1 ×dj 2 is the input matrix of the jth neural network. For different f Wj , the corresponding d j , d j1 and d j2 can be different. For each j ∈

[K], let D j = {(x (i) j , y (i) j ) ∈ R (dj 1 ×dj 2 )×dj } N i=1

be a set of labeled data (for the jth neural network). For each i ∈ [N ], let x (i) = (x

(i) 1 , . . . , x (i) K ), y (i) = (y (i) 1 , . . . , y (i) K ), and D = {(x (i) , y (i) )} N i=1 .

For a pre-trained model (component), we mean W j is fixed after its training process, and then we denote f Wj as f j for simplicity. On the other hand, a component f Wj is non-instantiated means W j is still free. A deep feedforward neural network is a hierarchical acyclic graph, i.e. a directed tree. In this viewpoint, a feedforward neural network can be presented as a series of function compositions. For given {f Wj (x j )} K j=1 , we assume θ j ∈ R dj , j ∈ [K], which make the product θ j f Wj (x j ) is well-defined. Denote f 0 as the constant function 1, then the liner combination with a bias is defined as as Θ(f 1 , ..., f K ) = j∈[K] + θ j f j (x j ). Hence, an L layers of neural network can be denoted as

Θ (L) • σ • • • • • Θ (0) (x).

A composite neural network defined by components f Wj (x j ) can be designed as an directed tree. For instance, a composite neural network σ 2 (θ 1,0 + θ 1,1 f 4 (x 4 ) + θ 1,2 σ 1 (θ 0,0 + θ 0,1 f 1 (x 1 ) + θ 0,2 f W2 (x 2 ) + θ 0,3 f 3 (x 3 ))) can be denoted as

σ 2 • Θ 1 (f 4 , σ 1 • Θ 0 (f 1 , f W2 , f 3 )),

where f 1 and f 3 are pre-trained and f W2 is non-instantiated. Note that in this work D j is the default training data of component f j of composite neural network, but D j can be different from the training data deciding the frozen weights in the pre-trained f j .

Let a, b be the standard inner product of a and b, and || • || be the corresponding norm. For a composite neural network, the training algorithm is the gradient descent back-propagation algorithm and the loss function is the L 2 -norm of the difference vector. In particular, for a composite neural network g θ the total loss on the data set D is

L θ x; g θ = g θ (x) -y, g θ (x) -y = || g θ (x) -y|| 2 (1)

This in fact is

N i=1 g(x (i) ) -y (i) 2

. By the definition of g θ (•), this total loss in fact depends on the given data x, the components defined by {Θ j } K j=1 , the output activation σ, and the weight vector w. Similarly, let L(f j (x j )) be the loss function of a single component f i . Our goal is to find a feasible θ s.t. L θ (x; g) < min j∈[K] L(f j (x j )).

3. PROBLEM SETTINGS AND RESULTS OVERVIEW:

The problems considered in this work are as follows:

P1. What are the conditions that the pre-trained components must satisfy so that them can strictly improve the accuracy of the whole composition?

P2. Will more pre-trained components improve the accuracy of the whole composition?

Let f j be the output vector of the jth pre-trained component, and B K be the set of unit vectors in R K .

A1. Linearly Independent components (LIC) Assumption:

∀t ∈ [K], {β j } ⊂ R, s.t. f t = j∈[K]\{t} β j f j . A2. No Perfect component (NPC) Assumption: min j∈[K] i∈[N ] f j (x (i) j ) -y (i) > * ,

where * > 0 is constant.

Our results are as follows:

Theorem 1. Assume the set of components {f j (x j )} K j=1 satisfies LIC. Let g be Θ(f 1 , ..., f K ). With probability at least 1 -K πe N , there is a vector θ ∈ R K \ B K s.t. L θ (x; g) < min j∈[K] {L(f j (x j ))}. Theorem 2. Assume the set of pre-trained components {f j (x j )} K j=1 satisfies both NPC and LIC, and g be σ • Θ(f 1 , ..., f K ). Then with probability at least 1 -K πe N there exists w s.t. L w (x; g) < min j∈[K] L(f j (x j )).

Theorem 3. Assume the set of components {f j (x j )} K j=1 satisfies LIC. Let g K-1 = Θ(f 1 , ...f K-1 ) and g K = Θ(f 1 , ...f K ). With probability at least 1 -K πe N , there is a vector w ∈ R K \ B R K s.t. L w (x; g K ) < L w (x; g K-1 ).

Theorem 1, and 2 together answer Problem P1, and Theorem 3 answers Problem P2.

4. RELATED WORK:

Our framework is related but not the same with the models such as transfer learning. (Erhan et al., 2010; Kandaswamy et al., 2014; Yao & Doretto, 2010) and ensemble leaning (Zhou, 2012) .

Transfer Learning. Typically transfer learning deals with two data sets with different distributions, source and target domains. A neural network, such as an auto-encoder, is trained with source domain data and corresponding task, and then part of its weights are taken out and plugged into other neural network, which will be trained with target domain data and task. The transplanted weights can be kept fixed during the consequent steps or trainable for the fine-tune purpose (Erhan et al., 2010) . For multi-source transfer, algorithms of boosting based are studied in the paper (Yao & Doretto, 2010) . Kandaswamy et al. (Kandaswamy et al., 2014) proposed a method of cascading several pre-trained layers to improve the performance. Transfer learning is considered as a special case of composite neural network that the transfered knowledge can be viewed as a pre-trained component.

Ensemble (Bagging and Boosting). Since the Bagging needs to group data by sampling and the Boosting needs to tune the probability of data (Zhou et al., 2002) , these frameworks are different from composite neural network. However, there are fine research results revealing many properties for accuracy improvement (Džeroski & Ženko, 2004; Gashler et al., 2008; Zhou et al., 2002) . For example, it is known that in the ensemble framework, low diversity between members can be harmful to the accuracy of their ensemble (Džeroski & Ženko, 2004; Gashler et al., 2008) . In this work, we consider neural network training, but not data processing.

Ensemble (Stacking). Among the ensemble methods, the stacking is closely related to our framework. The idea of stacked generalization (Wolpert, 1992) , in Wolpert's terminology, is to combine two levels of generalizers. The original data are taken by several level 0 generalizers, then their outputs are concatenated as an input vector to the level 1 generalizer. According to the empirical study of Ting and Witten (Ting & Witten, 1999) , the probability of the outputs of level 0, instead of their values, is critical to accuracy. Besides, multi-linear regression is the best level 1 generalizer, and non-negative weights restriction is necessary for regression problem while not for classification problem. In (Breiman, 1996) , it restricts non-negative combination weights to prevent from poor generalization error and concludes the restriction of the sum of weights equals to 1 is not necessary (Breiman, 1996) . In (Hashem, 1997) , Hashem showed that linear dependence of components could be, but not always, harmful to ensemble accuracy, while in our work, it allows a mix of pre-defined and undefined components as well as negative weights to provide flexibility in solution design.

Recently Proposed Frameworks. In You et al. (2017) , Shan You et al. proposed a student-teacher framework where the outputs of pre-trained teachers are averaged as the knowledge for the student network. A test time combination of multiple trained predictors was proposed by Kim, Tompkin, and Richardt In Kim et al. (2017) , that the combination weights are decided during test time. In above frameworks, the usage of pre-trained neural networks generally improves the accuracy of their combination.

5. THEORETICAL ANALYSIS:

This section provides analyses of the loss function of composite neural network with the introduction of pre-trained components. For the complete proofs, please refer to Supplementary Material. Observe that for given pre-trained components {f j } K j=1 , a composite neural network can be defined recursively by postorder subtrees search. For instance,

σ 2 • Θ 1 (f 4 , σ 1 • Θ 0 (f 1 , f 2 , f 3 )) can be presented as σ 2 • Θ 1 (f 4 , g 1 ), and g 1 = σ 1 • Θ 0 (f 1 , f 2 , f 3 ).

Without loss of generality, we assume d j = d = 1 for all j ∈ [K] in the following proofs. We denote f j the vector (f j (x (1) ), • • • , f j (x (N ) )), as the sequence of f j during the training phase. Similarly, y := (y (1) , • • • , y (N ) ). Let e j be an unit vector in the standard basis of R K for each j ∈ [K], i.e. e 1 = (1, 0, • • • , 0) and e 2 = (0, 1, 0, • • • , 0), etc. Let B K be the set containing all these standard unit-length basis of R K .

Theorem 1. Assume the set of components {f j (x j )} K j=1 satisfies LIC. Let g be Θ(f 1 , ..., f K ). With probability at least 1 -K πe N , there is a vector

θ ∈ R K \ B K s.t. L θ (x; g) < min j∈[K] {L(f j (x j ))}.

Proof. (Proof Sketch) The whole proof is split to Lemma 5.1,5.2,5.3. Note that g(•) is the linear combination of θ and {f j (x j )} K j=1 . It is well known (Friedman et al., 2001) that to search the minimizer θ for L θ , i.e. to solve a least square error problem, is equivalent to find an inverse matrix defined by {f j (x j )} K j=1 . Since {f j (x j )} K j=1 satisfy LIC, the inverse matrix can be written down concretely, which proves the existence. Furthermore, if this solved minimizer θ * is not e s for some s ∈ [K] then the g θ * has lower loss than f s . Lemma 5.3 argues that the probability of θ * = e s is at most the probability of the event f -y, f = 0, where f is uniformly taken from the vector set of the same length of f -y.

The statements of Lemmas needed by previous Theorem are as follows.

Lemma 5.1.

There exists θ ∈ R K+1 s.t. L θ x; Θ (0) (f 1 , ...f K ) ≤ min j∈[K] + {L(f j (x j ))}.

This Lemma deals with the existence of the solution of the inequality. But our goal is to find a solution such that the loss is strictly less than any pre-trained component. Lemma 5.2. Denote I L θ the indicator variable for the event that at least one of e j ∈ B R K is the minimizer of L θ . Then Pr

I L θ = 1 < K πe N , i.e. Pr I L θ = 0 ≥ 1 -K πe N . Lemma 5.3. Define F( y, L(f )) = f ∈ R N : f -y 2 = L f

for given y and f . Then we have

Pr f ∈F( y,L(f )) f -y, f = 0 < 1 πe N .

The above Lemmas prove Theorem 1. The following corollary is the closed from of the optimal weights. Corollary 5.1. The closed form of the minimizer is:

[θ t ] t∈[K] + = f s , f t -1 s,t∈[K] + × f s , y s∈[K] + .

In the following, we deal with σ

• Θ(f 1 , ..., f K ) and Θ 1 • σ • Θ(f 1 , ..., f K ).

Theorem 2. Assume the set of pre-trained components {f j (x j )} K j=1 satisfies both NPC and LIC, and g be σ • Θ(f 1 , ..., f K ). Then with probability at least 1 -K πe N there exists θ s.t. L θ (x; g) < min j∈[K] L(f j (x j )).

Proof. (Proof Sketch) The whole proof is split to Lemma 5.4,5.5, and 5.6. The idea is to find an interval in the domain of σ such that the output can approximate linear function as well as possible. Then in this interval, the activation σ can approximate any given pre-trained component. However, under the assumptions LIC and NPC the gradient of the loss L is not zero with high probability. Since the training is based on the gradient descent algorithm, this none-zero gradient leads the direction of updating process to obtain a lower loss.

Lemma 5.4. Let N, K and j ∈ [K] be fixed. For small enough , there exists θ ∈ Z F,1, and Proof. (Proof Sketch) The idea is directly solve the inequality for the case of K = 2, and then generalize the result to larger K.

0 < α ∈ R s.t. |σ • Θ (0) (f 1 , ..., f K ) - fj (x) α | < . Lemma 5.5. Assume NPC holds with * > 0. If θ * /3 satisfies |σ • Θ (0) (f 1 , ..., f K )(x) -f j (x)| < * 3N for any j ∈ [K] + , then ∇ θ L( θ * /3 ) = 0. Lemma 5.6. If θ * /3 makes ∇ θ L( θ * /3 ) = 0, then there exist θ s.t. L θ (x; g) < min j∈[K] + L(f j (x j )).

Now we consider the difference of losses of:

σ • Θ (f 1 , ..., f K ) and σ • Θ(f 1 , ..., f K-1 ). Theorem 3. Assume the set of components {f j (x j )} K j=1 satisfies LIC. Let g K-1 = Θ(f 1 , ...f K-1 ) and g K = Θ(f 1 , ...f K ). With probability at least 1 -K πe N , there is a vector θ ∈ R K \ B R K s.t. L θ (x; g K ) < L θ (x; g K-1 ).

The following provides a generalized error bound for a composite neural network.

Theorem 4. Assume pre-trained components {f j } K j=1 satisfy LIC and NPC. Let {GE(f j )} K j=1 be corresponding generalization errors of {f j } K j=1 , and

Θ (L) • σ (L) • • • • • σ (1) • Θ (0) (f 1 , ..., f K ) be the composite neural network. Denote the generalization error, E{L(Θ (L) • σ (L) • • • • • σ (1) • Θ (0) (f 1 , ..., f K ))},

of the composite neural network as E{L Θ,f1,...,f K }. Then with high probability, there exist a setting of {Θ * (L) , ...,

Θ * (0) } such that E{L Θ,f1,...,f K } ≤ Θ * (L) (GE(f 1 ), ...G E (f K )).

Proof. (Proof Sketch) We apply the idea similar to Kawaguchi (2016) : the exception of non-liner activations is same with the exception of liner activations. Previous theorems provide that with high probability there exists the solution of

Θ (i) , ∀i ∈ [L] + s.t. each Θ (i)+1 σΘ (i)

approximates a degree one polynomial A Θ (i)+1 σΘ (i) ,1 as well as possible. If the weights are obey the normal distribution, then

E{L Θ,f1,...,f K } ≤ Θ * (L) (GE(f 1 ), ...G E (f K )).

6. EMPIRICAL STUDIES:

This section is to numerically verify the performance of composite network for two distinctively different applications, image classification and PM2.5 prediction. For image classification, we examined two pre-trained components, the ResNet50 (He et al., 2016) from Keras and the SIFT algorithm(Lowe, 1999) from OpenCV, running on the benchmark of ImageNet competition (Russakovsky et al., 2015) . For PM2.5 prediction, we implemented several models running on the open data of local weather bureau and environment protection agency to predict the PM2.5 level in the future hours.

6.1. IMAGENET CLASSIFICATION:

We chose Resnet50 as the pre-trained baseline model and the SIFT model as an auxiliary model to form a composite neural network to validate the proposed theory. The experiments are conducted on the 1000-class single-label classification task of the ImageNet dataset, which has been a well received benchmark for image classification applications. A reason to choose the SIFT (Scale-Invariant Feature Transform) algorithm is that its function is very different from ResNet and it is interesting to see if the performance of ResNet50 can be improved as predicted from our theory.

We trained the SIFT model using the images of ImageNet, and directed the output to a CNN to extract useful features before merging with ResNet50 output. In the composite model, the softmax functions of both ResNet50 and SIFT model are removed that the outputs of length 1000 of both models are merged before the final softmax stage. During the training process of composite network, the weights of ResNet50 and SIFT model are fixed, and only the connecting weights and bias are trained.

The ResNet50 was from He et al. that its Top-1 accuracy in our context was lower than reported in (He et al., 2016) since we did not do any fine tuning and data preprocessing. In the Figure 1 , it shows the composite network has higher accuracy than ResNet50 during almost the complete testing run.

Table 1 shows the same result that the composite network performs better too. The experiment results support the claims of this work that a composite network performs better than any of its components, and more components work better than less components. The CWB has seventy monitoring stations, one record per 6 hours, containing 26 features, such as temperature, dew point, precipitation, wind speed and direction, etc. We partitioned the observed area into a grid of 1140 km2 with 1 km×1 km blocks and aligned the both dataset into one-hour period. We called the two datasets as air quality and weather condition dataset.

We selected ConvLSTM (Convolution LSTM) and FNN (fully connected neural network) as the components used in this experiment. The reason to select ConvLSTM is that the dispersion of PM2.5 is both spatially and temporally dependent and ConvLSTM is considered capable of catching the dependency, and FNN is a fundamental neural network that acts as the auxiliary component in the experiment.

The prediction models were trained with the data of 2014 and 2015 years, then the 2016 data was used for testing. We considered two function compositions, the linear combination Θ and the Logistic function σ 1 (as Theorem 2), to combine the two components to examine the applicability of the proposed theorems.

We trained and tested both ConvLSTM and FNN using air quality dataset (Dataset A) and weather condition dataset (Dataset B) separately as the baselines (denoted as f 1 , f 2 , f 3 and f 4 ) and their training error and testing error in MSE are list in the first part of Table 2 . Then we composited FNNs using Dataset A and Dataset B, each FNN can be pre-trained (denoted as x) or non-instantiated (denoted as o). In addition, we used both linear and Sigmoid activation functions. As a result, we had eight combinations, as list in the part two. We treated ConvLSTM in the same way and the outcomes were in the part 3. Finally, we composited using one FNN and one ConvLSTM that each was the best in their category, and the resulting composite network was a tree of depth 2. For instance, the candidate of ConvLSTM of part 4 for 12 hours prediction was the 4th row (i.e., Θ(f • 3 ,f • 4 )) of part 3. Their training and testing errors in MSE were listed in the part 4.

From the empirical study results, it shows mostly the proposed theorems are followed. While the composite networks with all pre-trained components may not perform better than others in their category, (which is not a surprise), what we expect to see is after adding a new component, the composite network has improvement over the previous one. For example, the σ • Θ(f × 3 , f × 4 ) has strictly better accuracy than both f 3 and f 4 for all future predictions. Another example is the NEXT 48 hr, σ • Θ(C × , F × ) also has strictly better accuracy than both 

C = σ • Θ(f • 3 , f • 4 ) and F = σ • Θ(f • 3 , f • 4 ).

7. CONCLUSION:

In this work, we investigated the composite neural network with pre-trained components problem and showed that the overall performance of a composite neural network is better than any of its components, and more components perform better than less components. In addition, the developed theory consider all differentiable activation functions.

While the proposed theory ensures the overall performance improvement, it is still not clear how to decompose a complicated problem into components and how to construct them into a composite neural network in order to have an acceptable performance. Another problem worth some thinking is when the performance improvement will diminish (by power law or exponentially decay) even adding more components. However, in the real world applications, the amount of data, data distribution and data quality will highly affect the performance.

8. SUPPLEMENTARY MATERIAL:

For self-contained, we list some common Taylor expansion in the following. Logistic:

S(z) := 1 1+e -z = 1 2 + 1 4 z -1 48 z 3 + 1 480 z 5 -17 80640 z 7 + O(z 9 ), ∀z ∈ R, Hyperbolic Tan: tanH(z) = e z -e -z e z +e -z = z -1 3 z 3 + 2 15 z 5 + O(z 7 ), ∀|z| ≤ π 2 arcTan: arctan(z) = z -1 3 z 3 + 1 5 z 5 + +O(z 7 ), ∀|z| ≤ 1.

Definition 1. Given an activation σ(z) and its Taylor expansion T σ (z), let A σ,D (z) be the truncated the monomials of degree at most D from T σ (z). We define A σ,D (z) as the D-degree Taylor approximation polynomial, and R σ,D+1 (z) as the remainder part such that

T σ (z) = A σ,D (z) + R σ,D+1 (z).

For instance, if we set D = 3 then the Taylor expansion of Logistic function S(z) is separated as the approximation part A S(z),3 (z) = 1 2 + 1 4 z -1 48 z 3 and the remainder part R S(z),4 (z) = 1 480 z 5 +O(z 7 ). Proposition 8.1. (Error Bound of The Remainder) Let S(z) be the Logistic function. Consider the approximation A S(z),≤D (z) and the remainder R S(z),D+1 (z) defined as above. For given ∈ (0, 1 1000 ) and

D ∈ N, if |z| < 1/(D+2) , then |S(z) -A S(z),D (z)| = |R S(z),D+1 (z)| < . Proof. Note that if < 1 then for all D ∈ N, 1/(D+1) < 1. If |z| < 1/3 and D = 1, then |R S(z),D+1 (z)| ≤ - 1 48 z 3 + 1 480 z 5 - 17 80640 z 7 + O(z 9 ) < 1 24 < .

The general case (D ≥ 2) can be proven by the same argument as above.

This Proposition means that for a suitable range of z, the Logistic function can be seen as a linear function with the error at most .

Definition 2. For the Logistic activation σ(z) = S(z), > 0 and given polynomial degree D, we define Z D, = {z ∈ R : |σ(z) -A σ,D (z)| < }. Furthermore, for given components {f j : j ∈ [K]} = F , we consider the variable z = Θ(f 1 , ..., f K ) and define

Z F,D, = θ ∈ R K+1 : z = Θ(f 1 , ..., f K ), |σ(z) -A σ,D (z)| < .

Observe that if the parameters , F ,and

|F | = K are fixed, then Z F,D, ⊂ Z F,D+1, ⊂ R K+1 .

8.1. FUNCTION COMPOSITION BY LINEAR COMBINATION:

Recall that for a set of pre-trained components {f j (x j ) :

j ∈ [K]}, Θ (0) (f 1 , ...f K ) = j∈[K] + θ 0,j f j , where f 0 = 1. For simplicity, we consider Θ (1) (z) = αz. This means Θ (1) • σ • Θ (0) (f 1 , ...f K ) = θ 1,1 σ j∈[K] + θ 0,j f j + θ 1,0 .

Theorem 1 is a consequence of the following lemmas:

Proof. (of Lemma 5.1) For simplicity of notations, let g

(x) = Θ (0) (f 1 , ...f K ), hence g(x) = j∈[K] + θ j f j (x j ). Also recall that L θ (x; g) = N i=1 g(x (i) ) -y (i) 2 .

To prove the existence of the minimizer, it is enough to solve the equations of critical points, in the case of a quadratic object function. That is, to solve the set of equations:

∇ θ L (x; g) = ∂L ∂θ 0 , . . . , ∂L ∂θ K T = (0, . . . , 0) T ,

where for each s, t ∈

[K] + , ∂L ∂θ s =2 N i=1 g(x (i) ) -y (i) • f s (x (i) ) = 2 N i=1   j∈[K] + θ j f j (x (i) j ) -y (i)   • f s (x (i) ) =2   j∈[K] + θ j f s , f j -f s , y   .

Hence, to solve

∇ θ L (x; g) = 0 is equivalent to solve f s , f t s,t∈[K] + × [θ t ] t∈[K] + = f s , y s∈[K] + , where f s , f t s,t∈[K] + is a (K + 1) by (K + 1) matrix, [θ t ] t∈[K] + and f s , y s∈[K] + are both 1 by (K + 1). Note that linear independence of { f j } j∈[K] + makes f s , f t s,t∈[K] +

a positive-definite Gram matrix (Horn & Johnson, 2012) , which means the inversion f s , f t

-1 s,t∈[K] +

exists. Then θ is solved:

EQUATION

The above shows the existence of the critical points. On the other hand, since L θ (x; g) is the summation of square terms, i.e. paraboloid, the the critical points can only be the minimum.

The meaning of the gradient on a function surface is the direction that increases the function value most efficiently. Hence, if the gradient is not the zero vector then the corresponding point can not be the minimizer of the function surface. Recall for any s ∈

[k], ∂L ∂θt t∈[K] + θ= es = 2 f s -y, f t t∈[K] + .

Before the proof of Lemma 5.2, we need the upper bound of the probability of some events. Note that y is defined according to the given training data, and for each j ∈ [K] + the length of f j -y,

i.e. f -y , is also given. The question is, for fixed y what is the probability of selected f is perpendicular to f -y? A folklore approach is considering that { f = (f (x (1) ), ..., f (x (N ) ))} obeys the normal distribution, and setting the mean of f (x (i) ) as y (i) for each i ∈ [N ]. In the following we propose another simple probability argument to obtain a loose upper bound.

Proof. (of Lemma 5.3) Observe that f -y, f = 0 ⇔ ( f -y) ⊥ f , which implies the angle between them, ∠ ( f -y), f , is in the interval [ π- 2 , π+ 2 ] for small ∈ R + , as shown in the left part of Figure 2 . The red, orange, and blue vectors show three possibles of the pair of f and f -y. The length of f -y is fixed since f and y are given, but the angle between f -y and y can decide whether ( f -y) ⊥ f . The gray circle collects all possible end-point of the vector f -y emission from the end-point of y. Although on the whole circle there are exactly two specific angles 3 can satisfy ( f -y) ⊥ f , we give a loose small interval with respect to π. In particularly, we set 0 < < e -N .

Pr:

f ∈F( y,L f ) ∠ ( f -y), f = π 2 ≤ Pr f ∈F( y,L f ) π - 2 ≤ ∠ ( f -y), f ≤ π + 2 = π < 1 πe N .

Now we are ready to proof Lemma 5.2. 3 That is, two points on the circumference, which is in fact measure zero on all possible angle [0, 2π) We denote A the event that at least one of e j ∈ B R K is the minimizer of L( θ) for convenience.

I L( w) = 1 ⇔ the event A is true ⇒ ∂L ∂θt t∈[K] + θ= es = 2 f s -y, f t t∈[K] + = [0] K×1 for somes ∈ [K] + ⇒ f 1 -y, f 1 = 0 ∧ f 1 -y, f 2 = 0 ∧ • • • ∧ f 1 -y, f K = 0 or • • • or f K -y, f 1 = 0 ∧ f K -y, f 2 = 0 ∧ • • • ∧ f K -y, f K = 0

Hence, for given y and L(f

j ) = f j -y 2 , ∀ ∈ [K] + , we have Pr I L( w) = 1 ≤ j∈[K] + Pr f j -y, f 1 = 0 ∧ f j -y, f 2 = 0 ∧ • • • ∧ f j -y, f K = 0 ≤K • Pr f 1 -y, f 1 = 0 < K πe N ,

where the second inequality is based on the symmetry between f s and f t for any s, t ∈ [K] + , and the last inequality is by Lemma 5.3.

Proof. (of Theorem 3) We start from a simple case:

Claim: ∃β ∈ R s.t. i∈[N ] (f 1 (x i ) -y i ) 2 - i∈[N ] (f 1 (x i ) + βf 2 (x i ) -y i ) 2 > 0. Proof. i∈[N ] (f 1 (x i ) -y i ) 2 - i∈[N ] (f 1 (x i ) + βf 2 (x i ) -y i ) 2 = i∈[N ] (f 1 (x i ) -y i ) 2 -(f 1 (x i ) + βf 2 (x i ) -y i ) 2 =   - i∈[N ] f 1 (x i ) 2   β 2 +   2 i∈[N ] (f 2 (x i )y i -f 2 (x i )f 1 (x i ))   β

Observe that the above is a quadratic equation of β with negative leading coefficient. Hence, to obtain the maximum of the difference, we can set

β = i∈[N ] (f 2 (x i )y i -f 2 (x i )f 1 (x i )) i∈[N ] f 1 (x i ) 2 = y -f 1 , f 2 f 2 , f 2

Note that if y -f 1 , f 2 = 0 then the last pre-trained component is no need to be added. We aim to calculate the probability of this case. Observe that y -f 1 , f 2 = 0 ⇔ ( y -f 1 ) ⊥ f 2 . This condition is different from previous Lemma. Here we have to find the upper bound of the probability of ( y -f 1 ) ⊥ f 2 for given f 1 and y. As shown in the left part of Figure 2 ), the angle between f 2 and y must be in a specific interval, say [ π- 2 , π+ 2 ] for small ∈ R + . In order to be concrete, we set 0 < < e -N . Pr f ∈F( y,1)

( y -f 1 ) ⊥ f 2 ≤ π < 1 πe N .

The general case can be reduced to the above claim by considering g K-1 as f 1 and θ k f K as βf 2 . Furthermore, since there there K possibles the be selected as the least pre-trained component, the probability is upper bounded by K πe N .

8.2. FUNCTION COMPOSITION BY NON-LINEAR ACTIVATION:

Proof. (of Lemma 5.4) Although the lemma is an existence statement, we give a constructive proof here. By setting D = 1 in Proposition 8.1, we know that for Logistic S(z) and 0 < < 1/1000, the degree-one Taylor approximation A S(z),1 = 1 2 + 1 4 z with the remainder

|R S(z),2 | < . Define M := 10 • max j∈[K] + ,i∈[N ] {|f j (x i )|}. Hence by setting z = fj (xj ) M , we have S fj (xj ) M -1 2 - fj (xj ) 4M

<:

. This means that for the givenj ∈ [K], θ j = 1 M , θ 0 = and for all j = j, θ j = 0. Furthermore, α = 4M . This lemma implies that the S(z) can approximate linear function as possible in a non-zero length interval, hence if the scaling of θ is allowed then Theorem 1 can be applied. Corollary 8.1. If the activation function is the Logistic, S(z), and {f j (x j )} K j=1 satisfies LIC, then with high probability there is a vector θ s.t

. L θ x; σ • Θ (0) (f 1 , ..., f K ) < min j∈[K] + L(f j (x j )).

Proof. Set of above Lemma as * 3N , then previous Lemma shows that there exists θ which maps {f j } into Z σ•Θ (0) ,1, *

3N:

. Since the output of σ • Θ (0) is a linear function with error at most * 3N , we have the same conclusion.

Proof. Let g(x) = σ • Θ (0) (f 1 , ..., f K )(x) for short. First observe that |g(x) -f j (x)| < * 3N ⇒ ∀i ∈ [N ],g(x (i) ) -f j (x (i) ) > - * 3N . Then i∈[N ] g(x (i) ) -y (i) = i∈[N ] (g(x (i) ) -fj(x (i) )) + (fj(x (i) ) -y (i) ) > N • - * 3N + * = 2 * 3 > 0.

On the other hand, it can be calculated that

∇ θ L (x; g) | θ= θ * /3 = ∂L ∂w 0 , ∂L ∂θ 1 , . . . , ∂L ∂θ K , ∂L ∂b 0 T | θ= θ * /3 , where [a] T is the transpose of the matrix [a]. Also note that ∂L ∂w0 | θ= θ * /3 = 2 • i∈[N ] (g(x (i) ) -y (i) ) • S(z), and ∂L ∂b0 | θ= θ * /3 = 2 • i∈[N ] (g(x (i) ) -y (i) ) • 1. Since i∈[N ] (g(x (i) ) -y (i) ) > 0, we can conclude ∇ θ L (x; g) | θ= θ * /3 = 0.

Proof. (of Lemma 5.6 ) By previous Lemma, it is valid to consider the best performance component, f j * ; i.e. L(f j * ) = min j∈[K] + L(f j (x j )). Since ∇ θ L( θ * /3 ) = 0, by definition of the gradient, moving along the direction of -∇ θ L( θ * /3 )/ ∇ θ L( θ * /3 ) with a step-size α > 0 must strictly decrease the value of L θ (x; g). W.L.O.G, we can assume this α is optimal; that is, if α > r > 0 then

L( θ * /3 ) > L( θ * /3 ) -r • ∇ θ L( θ * /3 )/ ∇ θ L( θ * /3 ) , while if r = α + δ for some δ > 0 then L( θ * /3 ) ≤ L( θ * /3 ) -r • ∇ θ L( θ * /3 )/ ∇ θ L( θ * /3

) . The issue is how to find a proper step-size r > 0? We consider the line search approach such that:

r * = arg min r∈R    L   θ 0 -r • ∇ θ L( θ 0 ) ∇ θ L( θ 0 )     

This outputs F * then we can make sure that L θ 0 > L θ 0 -r • ∇ θ L( θ 0 )/ ∇ θ L( θ 0 ) . Since the underlining θ 0 is θ * /3 that makes the loss is the same with the best one. Hence, we have ( θ 0 -r * • ∇ θ L( θ * /3 )/ ∇ θ L( θ * /3 ) ) to fit our goal (beating the best one).

Combining these lemmas can obtain the conclusion of Theorem 2.

Corollary 8.2. The process of Lemma 5.5 converges.

Proof. (of 8.2) It is know that if a monotone decreasing sequence is bounded below, then this sequence convergences. ..... (revising) Repeating the process of Lemma 2, we can obtain a strictly decreasing sequence: L( θ 0 ) > L( θ 1 ) > L( θ 2 ) > . . . . Note that ∀i, ( θ i ) ≥ 0. This means the sequence is monotone decreasing and bounded below, so theoretically it converges by monotone convergence theorem of mathematical analysis. Algorithmically, the gradient descent based sequence finding process stops at some term with ∇ θ L( θ ) = 0, which is a (local) minimum or a saddle point.

Corollary 8.3. If the assumptions in Theorem 2 are satisfied, then with height probability there exists θ s.t. L θ is a (local) minimum or a saddle point, while L θ (x; g) < min j∈[K] + |L(f j (x j ))| still holds.

Assume the pre-trained component set {f j (x j )} K j=1 satisfies both NPC and LIC, then there exists θ s.t. L θ (x; g) < min j∈[K] + L(f j (x j )).

In the previous proof, the critical properties of activations are local linearity and differentiability. Hence, it is not hard to check that if we replace σ(•) in Eq. ( 1) with other common activations, the conclusion still holds. By local linearity we mean that on a non-zero length interval in its domain, the function can approximate the linear mapping as well as possible.

Corollary 8.4. Theorem 1 and 2 can apply on any activations with local linearity and differentiability.

Based on Corollary 5.1 and Lemma 5.6, it is natural to obtain the process of finding θ: by gradient descent or the closed form of Corollary 5.1. We can compute the optimal weights for the bottom Sigmiod block. On the other hand, after random initializing, the parameters of un-trained components in the Relu or Tanh blocks are assigned. This implies they can be treated as the all pre-trained case in Theorem 1 or 2. In fact, given the outputs from bottom level block then Corollary 5.1 provides weights improving the accuracy. Then it goes to the next up level block until the top, which is the forwarding steps of Back-propagation LeCun et al. (1988) . Hence with initialization for un-trained component, Corollary 5.1 is essentially the same as Back-propagation.

8.3. A MIX OF PRE-TRAINED AND UN-TRAINED COMPONENTS:

Now we first consider some of {f Θj (x j )} K j=1 are pre-trained and some are un-trained, and then investigate the hierarchical combination of both kinds of components. In particularly, Eq. ( 1) can be re-written as g(x) = w 0 • σ (θ 1 f 1 + θ 2 f Θ2 ) + b 0 , where f 1 is a pre-trained component and f Θ2 is un-trained. Since Θ 2 is not fixed, it can not be checked that LIC and NPC assumptions are satisfied. On the other hand, after initialization, f Θ2 can be seen as a pre-trained component at any a snapshot during training phase.

Theorem 5. In the end of an weight updating iteration, if the components f 1 and f Θ2 satisfy LIC and NPC assumptions, then with high probability w updated in the next iteration can improve the loss.

:

https://opendata.epa.gov.tw/Home

http://opendata.cwb.gov.tw/index

Figures and Tables:

Figure 1: Image Classification Validation Accuracy

Figure 2: An illustration of Lemma 5.3 (the left) and Lemma 5.4 (the right)

Validation Error of Image Classification

Table content: <table><tr><td/><td>ResNet50</td><td colspan="2">SIFT composite</td></tr><tr><td colspan="3">number of parameter 25636712 2884200</td><td>3000</td></tr><tr><td>Validation Error (%)</td><td>70.1184</td><td>13.1252</td><td>71.5079</td></tr></table>

Training and Testing Errors of PM2.5 Prediction

Table content: <table><tr><td>Model</td><td>Next 12 hr</td><td/><td>Next 24 hr</td><td/><td>Next 48 hr</td><td/><td>Next 72 hr</td><td/></tr><tr><td>(input)</td><td>TarinError</td><td colspan="2">TestError TarinError</td><td colspan="2">TestError TarinError</td><td colspan="2">TestError TarinError</td><td>TestError</td></tr><tr><td>f1: FNN-A</td><td>100.1812</td><td>92.8528</td><td>134.7095</td><td>118.6065</td><td>141.6287</td><td>136.8358</td><td>148.1807</td><td>143.9980</td></tr><tr><td>f2: FNN-B</td><td>134.1137</td><td>120.0019</td><td>139.8016</td><td>128.5960</td><td>136.7693</td><td>134.9001</td><td>142.7637</td><td>140.8650</td></tr><tr><td>f3: ConvLSTM-A</td><td>54.2775</td><td>88.8156</td><td>57.5677</td><td>111.9122</td><td>74.8937</td><td>129.7418</td><td>77.7394</td><td>132.8923</td></tr><tr><td>f4: ConvLSTM-B</td><td>67.8625</td><td>118.4351</td><td>73.1519</td><td>125.6062</td><td>68.7069</td><td>137.0789</td><td>84.9656</td><td>138.6642</td></tr><tr><td>Θ(f × 1 ,f × 2 ) Θ(f × 1 ,f • 2 ) Θ(f • 1 ,f × 2 ) Θ(f • 1 ,f • 2 ) σ • Θ(f × 1 ,f × 2 ) σ • Θ(f × 1 ,f • 2 ) σ • Θ(f • 1 ,f × 2 ) σ • Θ(f • 1 ,f • 2 )</td><td colspan="2">99.7005 F : 90.0214 95.6804 93.0173 95.8110 93.1131 101.1584 90.2671 102.7556 90.6280 98.1241 93.1098 94.9931 91.4667 98.2596 91.3646</td><td colspan="2">130.7800 120.3185 121.9737 126.6807 133.1453 127.4999 124.5461 124.4182 F : 114.2274 115.9283 117.9781 117.7771 114.5264 117.7397 118.8107 117.7332</td><td colspan="2">139.9744 F : 132.4764 134.3893 134.0270 134.0676 135.2255 132.6726 132.8069 135.9256 133.2544 135.1553 134.1469 131.2684 135.1281 134.5078 132.8316</td><td colspan="2">144.6826 F : 137.8403 139.6226 140.5209 136.2009 144.0116 139.2339 139.3322 145.1052 139.2513 137.7562 142.1778 140.1604 144.5220 138.0456 139.8351</td></tr><tr><td>Θ(f × 3 ,f × 4 ) Θ(f × 3 ,f • 4 ) Θ(f • 3 ,f × 4 ) Θ(f • 3 ,f • 4 ) σ • Θ(f × 3 ,f × 4 ) σ • Θ(f × 3 ,f • 4 ) σ • Θ(f • 3 ,f × 4 ) σ • Θ(f • 3 ,f • 4 )</td><td colspan="2">27.1760 27.1519 27.4436 26.3063 C: 70.8670 85.8922 81.7688 78.5360 28.3844 84.9029 27.5981 80.7848 26.4125 78.3990 26.5131 75.5778</td><td>49.1624 42.7932 44.3214 40.1879 43.2981 44.4197 42.3181 42.3912</td><td>108.3157 104.2375 107.0898 100.8474 109.3709 98.1051 103.3361 C: 94.6242</td><td colspan="2">37.2116 33.2831 C: 110.4213 123.2186 31.4910 129.1829 25.3312 119.1634 31.2413 123.0041 29.7649 111.6793 30.4183 128.4138 27.5812 112.8075</td><td colspan="2">60.6415 74.3055 C: 110.9952 131.0565 68.4413 139.5661 76.1782 120.6814 63.7286 130.4122 69.3182 117.0719 64.4193 136.6043 70.5132 117.6480</td></tr></table>

Peer review (iclr2019):
 This paper studies composite neural network performance from function composition perspective. In theorems 1, 2 and 3, the authors essentially prove that as the basis functions (pre trained components) increases (satisfying LIC condition), there are more vectors/objects can be represented by the basis. To me, this is a very straight forward result. As the basis increases while the LIC condition is satisfied, we can of course represent more objects (the new component is one of them). I don*t see any novelties here. The result is straightforward, and this should be a clear rejection.