- 學位論文
分支網路中性價比最高之最佳分支位置演算法
Optimal Branch Location for Cost-effective Inference on Branchynet
摘要
深度神經網路近幾年在機器學習的使用上非常廣泛。為了達到較高的預測正確率，網路的深度不斷的在增加。但在提高預測正確率的同時，同時也需要花費較多的推斷時間以及能源。 前人提出了分支網路的這個技術來處理這個問題，這個技術在原本的網路當中，加入分支，這些分支可以讓資料不須執行完整個網路就可以提前離開產生預測結果。 分支網路需要人工調整一些超參數，這些超參數會非常影響分支網路的效果。而我們這篇論文主要是探討在那些位置加入這些分支會是最佳的。根據我們所知道的，之前還沒有人探討過類似問題。首先我們先定義了分支位置決定問題，並且也證明分支位置決定問題是一個NP完備問題。之後我們提出了一個動態規劃演算法來找到一個網路中最佳的分支位置。 我們將我們的演算法在四種不同深度的VGG網路上做實驗，實驗結果顯示我們的演算法可以有效地計算出最佳分支位置並且經準的預估預測正確率以及實際推斷時間。
並列摘要
Deep Neural Networks (DNNs) are very popular in many machine learning domains. To achieve higher accuracy, DNNs have become deeper and larger. However, the improvement in accuracy comes with the price of the longer inference time and energy consumption. The marginal cost to increase a unit of accuracy has become higher as the accuracy itself is rising. The Branchynet, known as early exits, is an architecture to address increasing marginal cost for improving accuracy. The Branchynet adds extra {\em side classifiers} to a DNN model. The inference on a significant portion of the samples can exit from the network earlier via these side branches if they already have high confidence in the results. The Branchynet requires manually tuning the learning hyperparameters, e.g., the locations of branches and the confidence threshold for early exiting. The effectiveness of this manual tuning dramatically impacts the efficiency of the tuned networks. To the best of our knowledge, there are no efficient algorithms to find the best branch location, which is a trade-off between the accuracy and inference time on the Branchynet. We propose an algorithm to find the optimal branch locations for the Branchynet. We formulate the problem of finding the optimal branch location for the branchynet as an optimization problem, and prove that the branch placement problem is an NP-complete problem. We then derive dynamic programming that runs in pseudo-polynomial time and solves the branch placement problem optimally. We also implement our algorithm and solve the branch placement problems on four types of VGG networks. The experiment results indicate that our dynamic programming can find the optimal branch locations for generating the maximum number of correct classifications within a given time budget. We also run the four VGG models on a GeForce RTX-3090 GPU with the branch combination found by the dynamic programming. The experiment results show that our dynamic programming accurately predicts the number of correct classifications and the execution time on the GPU.