Title: REINFORCED PIPELINE OPTIMIZATION: BEHAVING OPTIMALLY WITH NON-DIFFERENTIABILITIES

Abstract: Many machine learning systems are implemented as pipelines. A pipeline is essentially a chain/network of information processing units. As information flows in and out and gradients vice versa, ideally, a pipeline can be trained end-to-end via backpropagation provided with the right supervision and loss function. However, this is often impossible in practice, because either the loss function itself may be non-differentiable, or there may exist some non-differentiable units. One popular way to superficially resolve this issue is to separate a pipeline into a set of differentiable sub-pipelines and train them with isolated loss functions. Yet, from a decision-theoretical point of view, this is equivalent to making myopic decisions using ad hoc heuristics along the pipeline while ignoring the real utility, which prevents the pipeline from behaving optimally. In this paper, we show that by converting a pipeline into a stochastic counterpart, it can then be trained endto-end in the presence of non-differentiable parts. Thus, the resulting pipeline is optimal under certain conditions with respect to any criterion attached to it. In experiments, we apply the proposed approach -reinforced pipeline optimization -to Faster R-CNN, a state-of-the-art object detection pipeline, and obtain empirically near-optimal object detectors consistent with its base design in terms of mean average precision.

1. INTRODUCTION:

In the context of machine learning, many systems are implemented as pipelines consisting of multiple stages, where each stage is essentially an information processing unit. Arranged along a chain or over a network, the output of previous stages constructs the input to the subsequent stages that are directly connected. With the success of deep learning, many stages within pipelines are nowadays implemented as neural networks, which are trainable via backpropagation (Werbos, 1988) . Treating the whole pipeline as a large computation graph, just like what we do for a regular neural network, it would be desirable to train it end-to-end via backpropagation provided with the right supervision and loss function, since end-to-end training usually ensures optimality.

However, this is often impossible in practice, because a pipeline often contains some nondifferentiable parts. Either the loss function itself may be non-differentiable, or there may exist some non-differentiable computation nodes. Take Faster R-CNN (Ren et al., 2015) , a state-of-the-art object detection pipeline shown in Figure 1 , as an example. It consists of a region proposal network (RPN) and a region convolutional neural network (R-CNN) sharing a single backbone network (Girshick, 2015) . There are many non-differentiable parts within Faster R-CNN. The final evaluation criterion, i.e. mean average precision (mAP), is non-differentiable; the hard-coded region-of-interest (RoI) pooling and non-maximum suppression (NMS) operations are also non-differentiable with respect to the bounding box scores and coordinates. Such non-differentiabilities present significant challenges for training Faster R-CNN end-to-end. This is why the original implementation in (Ren et al., 2015) adopts a 4-step training strategy to approximate end-to-end learning.

The existence of non-differentiable parts prevents the whole pipeline from being trained end-to-end or optimized directly with respect to the final evaluation criterion. Prior approaches to training such pipelines rely on: 1) separate it into a set of isolated sub-pipelines where each sub-pipeline involves only differentiable parts; and 2) cherry-pick one appropriate differentiable loss function for each sub-pipeline to jointly mimic the final criterion. However, due to the interruption of the original in-Figure 1 : Faster R-CNN pipeline represented as a computation graph in testing time. Dotted lines indicate non-differentiabilities -either the edge itself is non-differentiable or the gradient passing on the edge is intentionally ignored. In testing time, network parameters θ i are kept frozen. Noting that -mAP is the real criterion measuring the performance of this pipeline. From a decision-theoretical point of view, training a pipeline in this way is equivalent to making myopic decisions using ad hoc heuristics for each sub-pipeline while completely ignoring the real utility -which is easily the opposite of doing the right thing (Russell & Wefald, 1991) . As a result, no optimality can be ensured in any form for the pipeline either in training or testing time.

In this paper, according to the theory of stochastic computation graph (SCG) (Schulman et al., 2015) , we show that by applying a so-called stochastication trick on an originally non-differentiable pipeline, we obtain a stochastic but differentiable counterpart which can then be trained completely end-to-end via backpropagation. The conversion from the original pipeline to the stochastic counterpart does not change the underlying information flow, or introduce any additional branches, thus the input-and output-distributions are always kept aligned along the pipeline. Furthermore, the gap between training and testing is closed since the same criterion is being used in both times.

We show that under certain conditions the stochastic pipeline and the original pipeline share the same set of optimal parameters. Since the final criterion is the only objective being optimized here, the learned pipeline is optimal over the training data. If the testing data is sampled from the same distribution as the training data -which is usually true in most benchmark dataset, the learned pipeline is also optimal over the testing data asymptotically. In experiments, we apply the proposed approach -reinforced pipeline optimization (RPO) -to Faster R-CNN, and obtain empirically near-optimal Faster R-CNN pipelines consistent with base models with respect to mAP. Figure 3 summarizes the main approach proposed in this paper.

The rest of this paper is organized as follows. In Section 2, we introduce the theory of stochastic computation graph, and present the basic method for doing backpropagation over SCGs. In Section 3, we formally define a machine learning pipeline, introduce the so-called stochastication trick, and present our main algorithm for end-to-end pipeline optimization. In Section 4, we show the main experimental results on optimizing a Faster R-CNN pipeline. In Section 5, we discuss some related work. And finally, in Section 6, we conclude with future work.

2. BACKGROUND:

In this section, we define stochastic computation graph, and present the method of gradient estimation over stochastic computation graphs.

2.1. STOCHASTIC COMPUTATION GRAPH:

Following the work of Schulman et al. (2015) , we define stochastic computation graph as follows.

Definition 1 (Stochastic Computation Graph) A stochastic computation graph (SCG) is a directed acyclic graph (DAG) G = (V, E), where V = (I, D, S) is the set of nodes consisting of input nodes I, deterministic nodes D, and stochastic nodes S, and E is the set of directed edges between nodes. In particular, input nodes are set externally, including input data, ground truth data and trainable parameters which are denoted specifically by Θ; deterministic nodes are functions of their parents, including cost nodes which are scalar-valued functions denoted specifically by C; and, stochastic nodes which are distributed conditionally on their parents.

Given a SCG, it is assumed that all the cost nodes are deterministic. If a stochastic function is needed for a cost node, it can alternatively be constructed by attaching an identity function to a normal stochastic node. A node could either be a primitive computation, or a sophisticated composition of computations. In this paper, we view SCG in an abstract way, so a node is a set of computations with specific functionality at the high level. This abstraction is not needed to establish our main result, and the way to do abstraction over a SCG is beyond the scope of this paper.

Generally, there are two types of edges: differentiable and non-differentiable. An edge (v, w) is differentiable if w is deterministic and the Jacobian matrix ∂w ∂v exists, or w is stochastic and ∂ ∂v Pr(w | PARENTS w ) exists, where PARENTS w is the set of parents of node w. Note that, if the partial derivative over an edge is intentionally ignored, then this edge is considered nondifferentiable. For example, the derivatives with respect to the input and ground truth data are usually ignored in practice. Two relations of influence are defined for a SCG. For any node v and w in the graph, if there exists a sequence of nodes n 1 , n 2 , . . . , n K , with K ≥ 1, such that (v, n 1 ), (n 1 , n 2 ), . . . , (n K , w) are all edges in the graph, it is called that "v influences w", denoted by v ≺ w. If all the intermediate nodes n k (not including v and w) are deterministic, it is called that "v deterministically influences w", denoted by v ≺ D w.

Following the relation of deterministic influence, the set of dependencies of node v is defined as the set of parameter and stochastic nodes that deterministically influence it, i.e.

DEPS v := {u ∈ Θ ∪ S | u ≺ D v}.

Input nodes other than parameters, such as input and ground truth data, are not considered as dependencies for other nodes, since they are usually considered as constants in one run of the graph and there is no need to compute derivatives with respect to them. If node v is deterministic, the value of v is a function of DEPS v , we can write v(DEPS v ), which also applies to cost nodes; if node v is stochastic, the probability density/mass function of v is a function of DEPS v , we can write Pr(v | DEPS v ), in which case we use v to denote a sampled value of v. In the next section, it will be shown that this dependency relation suffices to estimate the derivatives of all cost nodes with respect to all trainable parameters, if a so-called differentiable requirement holds.

2.2. GRADIENT ESTIMATION ON STOCHASTIC COMPUTATION GRAPH:

Given a SCG G and a training dataset D, an optimization problem can be defined as finding the best set of parameter nodes Θ such that the expected sum of all cost nodes is minimized, more formally:

EQUATION

This optimization problem can be solved via standard stochastic gradient descent (SGD) if the gradient ∇J(Θ) exists, in which case the whole graph is considered to be differentiable. It can be shown that this gradient exists, if the following differentiable requirement is met:

Condition 1 (Differentiable Requirement) Given a SCG G = (V, E)

, it is considered differentiable, if for any parameter node θ ∈ Θ, all edges (v, w) ∈ E, satisfying θ ≺ D v and θ ≺ D w, are differentiable: either w is deterministic and Jacobian matrix ∂w ∂v exists; or w is stochastic and

∂ ∂v Pr(w | PARENTS w ) exists.

It is worth noting that this differentiable requirement does not require that all edges in the graph are differentiable. If the path from a parameter node θ to deterministic node v is blocked by some stochastic nodes, then v does not have to be differentiable with respect to its parents; if the path from a parameter node θ to a stochastic node v is blocked by other stochastic nodes, then the probability density/mass function of v conditioned on its parents does not have to be differentiable -in fact, it does not have to be known1 .

If a SCG is differentiable, then the partial derivative of J(Θ) with respect to any parameter node θ ∈ Θ can be unbiasedly estimated as:

EQUATION

where Qv = c∈C,v≺c ĉ is the sum of all sampled "downstream" costs influenced by stochastic node v. The two parts in Equation 2 are the derivatives originated from stochastic paths and deterministic paths respectively. If we let

L(Θ) = θ≺ D v,v∈S log Pr(v | DEPS v ) Qv + θ≺ D c,c∈C c(DEPS c ) -a deterministic differentiable loss function, it can be seen that ∂ ∂θ J(Θ) = E ∂ ∂θ L(Θ) .

In other words, we can apply a standard automatic differentiation procedure to L using sampled Qv values to obtain an unbiased estimator of ∂ ∂θ J(Θ). In this sense, L is called the surrogate loss function, and the corresponding surrogate optimization problem is defined as:

minimize Θ L(Θ) = θ≺ D v,v∈S log Pr(v | DEPS v ) Qv + θ≺ D c,c∈C c(DEPS c ).

(3)

Solving the surrogate optimization problem defined in Equation 3 using standard SGD via backpropagation gives us an optimal set of parameters, which is also optimal for the original optimization problem defined in Equation 1. The surrogate loss function L(Θ), however, often has a high variance due to the sampled Qv values, which may cause instability during training. To alleviate this issue, it is a common practice to subtract some "baseline" values b from Qv to reduce the variance without affecting the derivatives. As shown in (Greensmith et al., 2004; Schulman et al., 2015) , taking b = E[ Qv ] is generally a good option.

3. REINFORCED PIPELINE OPTIMIZATION:

In this paper, we assume a pipeline can be represented as a SCG, which is in turn a DAG by definition. A pipeline is differentiable if and only if the underlying SCG is differentiable, in which case it is automatically end-to-end trainable. In this section, we focus on pipelines that are not originally differentiable. For example, Figure 1 shows a Faster R-CNN pipeline in testing time, which is not differentiable due to the non-differentiable -mAP criterion and non-differentiable NMS and RoI pooling computations. We show that by applying a so-called stochastication trick on a non-differentiable pipeline, we obtain a stochastic but differentiable counterpart, which can then be trained end-to-end.

Definition 2 (Stochastication) Given a non-differentiable pipeline represented as a stochastic computation graph P = (V, E), let ⊆ E be the set of non-differentiable edges that are not resulting from gradients being intentionally ignored. For an edge (v, w) ∈ , if v is deterministic, and there exists at least one parameter node θ ∈ Θ, such that θ ≺ D v, we modify the pipeline by: 1) removing edge (v, w) from E, and 2) adding edges (v, k) and (k, w) into E, where k is a stochastic node with differentiable probability density/mass function

Pr(k | v) such that E[k] = v.

Repeat this operation until no edges can be removed from or added to the pipeline. Return the new pipeline.

For a non-differentiable pipeline P = (V, E), let P = (V , E ) be the resulting pipeline after applying the stochastication trick on P. Let ∈ E be the set of edges belonging to P that are not originally differentiable. Let ∈ E be the set of newly added edges belonging to P . For any parameter node θ ∈ V , for any edge (v, w) ∈ E , satisfying θ ≺ D v and θ ≺ D w, if (v, w) / ∈ , we must have (v, w) ∈ E and (v, w) / ∈ , implying that (v, w) is differentiable at the first place; on the other hand, if (v, w) ∈ , then w must be the newly added stochastic node under the condition that θ ≺ D v and θ ≺ D w, and (v, w) must be differentiable because Pr(w | v) is differentiable by construction. In summary, the differentiable requirement is met for pipeline P , thus P can be trained end-to-end via backpropagation in terms of the surrogate optimization problem defined in Equation 3, which solves the original optimization problem defined in Equation 1. Figure 3 gives the converted pipeline for end-to-end training on Faster R-CNN. The only structural difference between Figure 3 and Figure 1 is the two newly added stochastic nodes π 0 and π 1 -which closes the gap between training and testing while being able to optimize on the real criterion -mAP.

In training of P as solving the surrogate optimization problem, once the training is converged, it is induced that we have an optimal pipeline with a set of optimal parameters Θ * over the training dataset (globally or locally optimal depending only on the training process not the pipeline itself). We now show that the original pipeline P equipped with the same set of learned parameters Θ * is also optimal over the same training dataset under certain conditions.

Recall that, in the converted pipeline P = (V , E ), the objective function is defined as v 1 , v 2 , . . . , v K and z k1 , z k2 , . . . , z k K . Then under the condition that E[z c ] is a constant, we have

J (Θ) = E c∈C c(DEPS c ) . Let κ = V -V

E c∈C,κc =∅ c(DEPS c ) = c∈C,κc =∅ c(PARENTS κc , DEPS c -κ c ) + c∈C,κc =∅ E[z c ].

In other words, the first part can be emerged into the second part. More precisely,

J (Θ) = c∈C,κc =∅ c(PARENTS κc , DEPS c -κ c ) + E c∈C,κc=∅ c(DEPS c ) + c∈C,κc =∅ E[z c ] = J(Θ) + C,

where C is a constant. Therefore, under a so-called constant drift condition, we have J (Θ) = J(Θ) + C for any set of parameters Θ. It is then clear that, if Θ * is optimal for J over a training dataset, it is also optimal for J over the same training dataset.

Condition 2 (Constant Drift Requirement) Let κ = V -V be the set of newly added stochastic nodes. Let κ c = {k ∈ κ | k ≺ D c} be the set of stochastic nodes within κ influencing cost node c. Let c(κ c , DEPS c -κ c ) = c(PARENTS κc , DEPS c -κ c ) + z c , where z c is the amortized noise term. If the noise term z c has a constant mean, the converted stochastic pipeline and the original pipeline share the same set of optimal parameters over the same training dataset.

In the case when all cost nodes c, influenced by stochastication, are linear with respect to the newly added stochastic nodes, it is easy to show that the constant drift condition is met naturally (in which case the noise term has a zero mean). Generally, it is difficult to obtain a closed-form expression for nonlinear cost functions of several random variables to check whether the constant drift condition is met. However, if the random variables are jointly Gaussian with nonzero cross-correlation, then it is possible to compute useful expectations when the nonlinear functions are memoryless (Shynk, 2012), which is beyond the scope of this paper.

In order to reduce variance in training of P , it suffices to simply use the expected value of Qk for each stochastic node k ∈ κ. Having E[k] = v, where v is the preceding deterministic node of k, it follows that the baseline values can be collected by running the pipeline P once without sampling (which is equivalent to running the original pipeline P). Figure 4 outlines the main algorithm. We call this algorithm reinforced pipeline optimization (RPO), since it is very similar to policy gradient (Sutton et al., 2000) in the context of reinforcement learning (RL), except that RL relies on a Markovian model which has to be a linear stochastic computation graph in the dimension of time (Sutton et al., 1998) , but RPO is generally applicable to any stochastic computation graph that can be represented as a DAG. RPO in Figure 4 adopts an implementation with baseline. If needed it is rather straightforward to discard baseline from it. In experiments, we test RPO with and without baseline for ablation study.

It can be interpreted that RPO solves an optimization problem defined over a stochastic computation graph via stochastic gradient descent using standard backpropagation, which happens to find the best set of parameters for the original pipeline under the condition of constant drift. If the underlying pipeline can be represented as a linear graph (i.e. a chain of nodes), it becomes a Markov decision process (MDP) where the information flow passing through the pipeline is the sequence of states, trainable models are parts of the policy, alternations made to states are actions, the performance criterion is the reward function being optimized, and other non-trainable parts are parts of the environment. Under this MDP formulation, RPO reduces to standard policy gradient. The optimal policy of the resulting MDP corresponds to the optimal stochastic pipeline possible.

One concern on the proposed algorithm is that it might learn slowly if trained from scratch since it relies solely on the final criterion (such as -mAP for a Faster R-CNN pipeline) which is usually sparse and cannot provide relatively strong signals for the learning process. In practice, we can always supply additional cost/reward signals to guide the learning process, using techniques such as reward shaping (Ng et al., 1999) . In this sense, isolated loss functions developed for traditional non-optimal pipeline training can be reused here for accelerating end-to-end training in the early stage of training without affecting the optimality result we established. In the case the criterion function has some internal structure, we can also apply a so-called reward decomposition method on it to explicitly exploit the structure in order to obtain decomposed problems that are easier to learn (Dietterich, 2000; Russell & Zimdars, 2003; Marthi, 2007) . In our default experiment setting, we adopt pretrained models before applying end-to-end reinforced training.

4. EMPIRICAL EVALUATION:

We conduct our main experiments on Faster R-CNN which is a state-of-the-art object detection pipeline (Ren et al., 2015) . We choose Faster R-CNN for several reasons. As shown in Figure 1 , Faster R-CNN has a clear two-stage structure, namely the region proposal network (RPN) and the region convolutional neural network (R-CNN). These two stages are not linearly combined, as they share the same base feature generated from one backbone network (which prevents it from being simply modeled as an MDP). The final criterion measuring its real performance, i.e. the mAP value, is well-known to be non-differentiable. In addition, Faster R-CNN contains many other non-differentiable computations, such as RoI pooling and NMS. Furthermore, object detection is a non-trivial one-to-many problem, in the sense that, given a single image input (fixed size or not), there are potentially many output entities without knowing the exact number in advance. Therefore, end-to-end optimizing an object detection pipeline, such as Faster R-CNN, is a challenging problem for pipeline optimization.

We now describe in detail how we convert a Faster R-CNN pipeline into a stochastic counterpart and train it end-to-end using the proposed RPO algorithm. In the first stage, the raw output of RPN for each image within a mini-batch is a set of bounding boxes B RPN = {b} where a bounding box b is represented as b = (p b , o b ). Here, p b is a softmax score giving the probability of bounding box b being an object, and o b = (t x , t y , t w , t h ) is the bounding box offset with respect to an anchor box a, defined as t x = x-xa wa , t y = y-ya ha , t w = log( w wa ), and t h = log( h ha ), where x and x a are the x-coordinates for the predicted box and anchor box respectively (likewise for y-coordinate y, width w and height h). Following Ren et al. (2015) , we ignore all cross-boundary bounding boxes. After applying stochastication, during sampling, we firstly construct a Bernoulli distribution for each bounding box score with p b as the mean, denoted by B(p | p b ), from which we sample a 0-1 score pb ∼ B(p | p b ). We then construct a multivariate Gaussian distribution for each bounding box offset with o b = (t x , t y , t w , t h ) as the mean and a constant matrix Σ = σ 2 I as the covariance, denoted by , implying that if a bounding box is sampled as background (i.e. pb = 0) then its offset-part log probability is ignored. We then accumulate and average log probabilities for all bounding boxes within the same image, which reads

N (o | o b , Σ).

1 |BRPN| b∈BRPN log Pr( b | b).

The set of newly sampled bounding boxes is then passed to following stages of the pipeline. This step is depicted as node π 0 in Figure 3 . We then accumulate and average log probabilities for all bounding boxes within the same image, which reads

1 |BRCNN| b∈BRCNN log Pr( b | b).

Finally, the set of newly sampled bounding boxes is passed to the NMS operation before computing -mAP. This step is depicted as node π 1 in Figure 3 .

We implement our algorithm based on a publicly available Faster R-CNN repository2 . We evaluate the proposed RPO algorithm on the widely-used PASCAL VOC 2007 benchmark (Everingham et al., 2008) , which contains about 5k trainval images and 5k test images over 20 object categories. By default in our implementation, we firstly train Faster R-CNN with various backbone networks following a normal way with a learning rate of 0.001 which is decreased every 15 epochs with a factor of 0.1 until no further improvements can be achieved; we then apply RPO with and without baseline on the pre-trained models for additional 15 epochs. Throughout reinforced training, we use a standard SGD optimizer with a momentum of 0.9 and a learning rate of 0.0001, which is decayed every 5 epochs with a factor of 0.9. The hyper parameter for the Gaussian distributions is set to be σ = 1. Typically, a traditional Faster R-CNN pipeline may use different parameters for training and testing. For example, in the original implementation, the authors set the number of proposal regions to be 2,000 in training time, and 300 in testing time. In our implementation, we use exactly the same parameters for both training and testing time. For instance, we set the number of proposal regions to be 300 in both time. This can be seen as one advantage of our proposed method, since it further closes the gap between training and testing.

In reinforced training of Faster R-CNN, the final -mAP value is considered as the only cost node. The collected log probabilities multiplied by the downstream -mAP value are used to construct the surrogate loss, to which we conduct an automatic differentiation procedure via backpropagation. In the case baseline is used, the -mAP value corresponding to a non-sampling pipeline is considered as a baseline, and will be subtracted from the -mAP value resulting from sampling for variance reduction. We notice it is generally difficult to justify whether the constant drift condition is met in this setting, since the mAP value involves many non-linear computations over many random variables. However, empirically it is reasonable to assume that the learned parameters are near-optimal for the original Faster R-CNN pipeline.

Table 1 summaries experimental results in terms of mAP values before and after applying RPO averaged over 5 runs. Figure 5 reports more detailed results throughout training. Figure 6 presents some detection results of Faster R-CNN with ResNet-18 before and after applying RPO. It can be seen As ablation study, we test RPO with and without baseline. It can also be seen from the results that there are only slight differences between these two versions of RPO, suggesting that the baseline value we used may not be necessary for optimizing Faster R-CNN.

5. RELATED WORK:

Caicedo & Lazebnik (2015) and Mathe et al. (2016) propose novel methods that learn to localize objects in scenes using an attention-action strategy, which is further extended to multiple objects in (Kong et al., 2017) . Their methods model visual object detection as a sequential search problem (including stopping condition), and develop a reinforcement learning algorithm to approximately solve this problem. Their sequential models learn to predict detection hypothesis one at a time, until a stopping condition is generated, while in our method the joint policy, i.e. the two-stage networks, is able to generate all possible detection hypotheses concurrently. Very recently, Xie et al. (2018) develop a reinforcement learning algorithm to optimize a non-differentiable two-stage pipeline in inference time. The idea is to train a policy network to iteratively refine the output of the first stage in a way to make it more favorable to the second stage by optimizing some criteria. Their method needs to introduce an additional policy network, while our method treats the trainable models in the original pipeline as policies directly. Besides, their method runs over multiple iterations in the inference time, while our method runs completely in the training time, and keeps the original pipeline untouched in the inference time, which is much more efficient. Another recent related work is (Pirinen & Sminchisescu, 2018) , where the authors train a reinforcement learning agent to replace the greedy RoI selection process with a sequential attention mechanism. Similar to (Xie et al., 2018) , they introduce a separate sequential network to represent the policy, while in our method learning models are trained as policies directly. Rao et al. (2018) develop a policy gradient algorithm for learning a globally optimal Faster R-CNN object detector. Their method can be seen as an incomplete implementation of our method, in the sense that: 1) they sample a set of bounding boxes according to the softmax scores, but not the coordinates; and 2) they sample in the second stage, but not in the first stage. Besides, since bounding box coordinates are ignored in their sampling strategy, their method still relies on the standard R-CNN regression loss for training bounding box regressor. In contrast, our method optimizes a pipeline directly and solely on the final criterion that measures its real performance.

6. CONCLUSION:

In this paper, according to the theory of stochastic computation graph, we show that by converting an originally non-differentiable pipeline into a stochastic counterpart, we can then train the converted pipeline end-to-end and optimize it with any criterion attached to it. We develop a stochastication trick, and propose a novel algorithm for end-to-end pipeline optimization, namely reinforced pipeline optimization (RPO). We further show that under a constant drift condition, the converted stochastic pipeline and the original pipeline share the same set of optimal parameters over the same training dataset. In experiments, we apply RPO to the optimization of challenging Faster R-CNN pipelines, and obtain empirically near-optimal object detectors consistent with Faster R-CNN design in terms of mean average precision. In future work, we would like to extend RPO to more general pipelines that are not necessarily DAGs, for example dynamic pipelines where some computations may be dependent on some other past computations in time.

:

This is why reinforcement learning, as a specialization of SCG, can be solved model-free.

https://github.com/jwyang/faster-rcnn.pytorch

Figures and Tables:

Figure 2: Traditional Faster R-CNN pipeline represented as a computation graph in training time compromised to non-differentiabilities. Nodes in orange color indicate learning models. Lacking the ability of optimizing the real criterion -mAP, isolated RPN and R-CNN losses are being optimized instead.

Figure 3: Reinforced Faster R-CNN pipeline represented as a SCG in training time, where π 0 and π 1 are the augmented stochastic nodes. This pipeline optimizes directly on the real criterion -mAP, and behaves the same way in both training and testing time, except that in testing time sampling is actually not needed, and parameters are kept frozen.

Figure 4: Reinforced pipeline optimization (RPO) with baseline. Note that the original pipeline may have some additional differentiable costs (line 7), which are optimized simultaneously (line 11). The original pipeline is assumed to only have deterministic nodes. If it in fact has some stochastic nodes, only slight modifications are needed for extension.

Here, I is an identity matrix and σ is a hyper parameter which needs to be set before training. For each bounding box offset, we then sample a new offset nearby ôb ∼ N (o | o b , Σ). By sampling pb and ôb , we obtain a new bounding box b = (p b , ôb ). The overall log probability for b is computed as log Pr( b | b) = log B(p b | p b ) + pb log N (ô b | o b , Σ)

Similarly, in the second stage, the raw output of R-CNN for each image is a set of bounding boxes B RCNN = {b}. But here b is represented as b = (p b , r b ), where p b is a vector of softmax probabilities with p b [c] being the probability of bounding box b belonging to class c, and r b is a vector of rectangles with r b [c] = (x 0 , y 0 , x 1 , y 1 ) being the predicted rectangle conditioned that b belongs to class c. During sampling, we firstly construct a categorical distribution for each bounding box with p b as the mean, denoted by C(p | p b ), from which we sample a one-hot distribution pb ∼ C(p | p b ). We then construct a vector of multivariate Gaussian distributions for each bounding box with r b [c] as the means, denoted by N (r | r b [c], Σ) where Σ = σ 2 I, from which we sample a set of new rectangles nearby rb [c] ∼ N (r | r b [c], Σ). At this point, we obtain a new bounding box b = ( pb , rb ). Let the vector of log probabilities over all classes be log Pr(r b | r b ) = [log N (r b [c] | r b [c], Σ)]. The overall log probability is computed as log Pr( b | b) = log C( pb | p b ) + (1 -pb [0]) log Pr(r b | r b ) [arg max c pb [c]]. The second term indicates that only the log probability corresponding to a sampled non-background class is considered.

(a) Faster R-CNN with ResNet-18. (b) Faster R-CNN with ResNet-34. (c) Faster R-CNN with ResNet-101. (d) Faster R-CNN with VGG-16.

Figure 5: Experimental results shown as mAP values on PASCAL VOC 2007 validation set while training on training set. The results are averaged over 5 runs of RPO with and without baseline on Faster R-CNN with various backbone networks. The xand yaxes are number of epochs and mAP value respectively. The shaded area represents 95% confidence interval.

Figure 6: Selected detection results of Faster R-CNN with ResNet-18 before (top row) and after (bottom row) applying RPO. Blue boxes are ground truths; green boxes are predictions. These test images are from PASCAL VOC 2007 validation set. It can be seen that the results after reinforced training make much more sense.

Empirical results shown as mAP values on PASCAL VOC 2007 validation set after training on training set. The mAP Values are obtained before and after applying RPO with and without baseline over various backbone networks.

Table content: <table><tr><td colspan="2">Backbone Network ResNet-18</td><td>ResNet-34</td><td>ResNet-101</td><td>VGG-16</td></tr><tr><td>Pre-trained</td><td>50.57%</td><td>61.24%</td><td>74.89%</td><td>66.69%</td></tr><tr><td>RPO w/ baseline</td><td colspan="4">52.25 ± 0.07% 61.94 ± 0.12% 75.05 ± 0.10% 67.44 ± 0.11%</td></tr><tr><td colspan="5">RPO w/o baseline 52.25 ± 0.05% 61.84 ± 0.05% 75.04 ± 0.07% 67.43 ± 0.10%</td></tr></table>

Peer review (iclr2019):
 Pros: + Improving joint training of non-differentiable pipelines is a meaningful and relevant problem + Using the stochastic computation graph structure to smooth a pipeline in a structured way is a plausible idea Cons: + The main result of the paper concerning sufficient conditions for optimality of the method seems dubious + It is not obvious why this method would outperform simple baselines, and baselines for joint training were tried + The notation seems unnecessarily bloated and overly formal + The exposition spends too much time on prior work, too little on the contribution, and the description of the contribution is confusing The submission describes a method for smoothing a non-differentiable machine learning pipeline (such as the Faster-RCNN detector), so that gradient-based methods may be applied to jointly train all the parameters of the pipeline. In particular, the proposal involves recasting the pipeline as a stochastic computation graph (SCG), adding stochastic nodes to this graph, and then using REINFORCE-style policy gradients to perform parameter learning on the SCG. It is claimed that under certain conditions, the optimal parameters of the resulting SCG are also optimal for the original pipeline. The method is applied to optimizing the parameters of Faster-RCNN. I think making non-differentiable pipelines differentiable is an intuitively appealing concept. A lot of important, practical machine learning systems fall into this category, so devising a nice way to do global parameter optimization for such systems could potentially have significant impact. In general, we can’t hope to make much meaningful progress on the problem of optimizing general nonlinear, differentiable functions, but it is plausible that a method that targets key non-differentiable components for smoothing—such as this paper—could outperform a generic black-box optimizer. So, I think the basic idea here is plausible and addresses an important problem. Unfortunately, I think this work loses sight of that high-level goal: to me, the key question is whether the proposed approach outperforms any other simple method for global parameter optimization in the presence of nonlinearities and nondifferentiability. The paper fails to answer this question because no baselines for global parameter optimization were tried. We can just treat the pipeline as a black box mapping parameters to training set performance, and so any black-box optimization method can be applied to this problem. It is not clear that the proposed method would outperform an arbitrary black box optimization method such as simulated annealing, Nelder-Mead, cross-entropy method, etc. I think there are also much simpler methods in a similar vein to the proposed method that might also perform just as well as the proposal. One key conceptual issue here is that reducing the problem to a reinforcement learning problem, as the submission does, is not much of a reduction at all. First, if the goal is to do global parameter optimization, then we don’t really have to smooth the pipeline itself: we can just smooth the black box mapping parameters to performance, and then optimize that with SGD. There are many ways to do this--if we want to use policy gradient, we can just express the problem as something in this form: min_.phi E_{.theta ~ q_.phi} C(.theta) where C is the black-box mapping parameters .theta to a performance index (such as mean AP), q_.phi is a distribution over parameters (e.g., Gaussian), and .phi are the distribution parameters (e.g., mean, covariance of the Gaussian). We can then optimize this using REINFORCE policy gradients. If we want to really smooth the pipeline itself, then it is also easy to do this by devising a suitable MDP and then applying REINFORCE with the usual MDP structure. We simply identify the state s_t at time t with the output of the t’th pipeline stage, introduce a new ‘action’ variable a_t representing a ’stochastified output’, and trivial dynamics (P(s_{t+1} | s_t, a_t) = .delta(s_{t+1} - a_t)). If the policy is a Gaussian (P(a_t | s_t) = N(a_t; s_t, .Sigma)), then this is similar to relaxing the constraint that one stage’s output is equal to the input of the next stage, and somehow quadratically penalizing their difference. In fact, there is a neural network training method based explicitly on this penalization view [A], and it would make yet another great baseline to try. In fact, the proposed method is essentially similar to what I have just described, but it is unfortunately described in an overcomplicated way that obscures the true nature of the method. I think the whole SCG framework is overkill here. Too much of the paper is spent just rehashing the SCG framework, and the very heavy notation again just obscures the essential character of the method. If there were, as the paper claims, some interesting condition under which the method produces solutions that are optimal under the original pipeline, that would be remarkable and interesting. However, I have serious doubts about this part of the paper. The key problem is the statement that “It follows that c(k_c, DEPS_c - k_c) = c(…) + z_c”. The paper seems to be claiming that if E z = 0, then c(k + z) = c(k) + z, which can’t possibly be true in general. The heavy and opaque notation makes it very difficult to understand this section. Perhaps it would help to consider a very simple example. Suppose we want to minimize E_{x ~ q} c(y(x)) (where x ~ q means x is distributed as q). We can introduce only one new stochastic node (k = y + z), between y and c. Clearly c(y + z) is not generally equal to c(y) + z, even if E z = 0. In summary, I think the submission needs a lot of work on multiple axes before it can make a significant impact. The most important issues are a complete lack of relevant baselines and the dubious claims about sufficient conditions for optimality. The idea could have merit, but it needs to be carefully compared and motivated with respect to existing work (such as [A]) as well as the simple baselines I have mentioned. The presentation also needs to be revised to find the simplest expression of the method and to focus on the interesting parts. [A] Taylor, Gavin, et al. "Training neural networks without gradients: A scalable admm approach." International Conference on Machine Learning. 2016.