### Constructing the Basis Path Set by Eliminating the Path Dependency

ZHU Juanping1, MENG Qi2, CHEN Wei2, WANG Yue2, MA Zhiming3

1. 1. School of Mathematics and Statistics, Yunnan University, Kunming 650500, China;
2. Microsoft Research Asia, Beijing 100190, China;
3. Academy of Mathematics and Systems Science, Chinese Academy of Science, Beijing 100190, China
• Received:2020-08-31 Revised:2021-07-05 Online:2022-10-25 Published:2022-10-12
• Supported by:
This research was supported by Project for Innovation Team (Cultivation) of Yunnan Province under Grant No.202005AE160006 and Key Project of Yunnan Provincial Science and Technology Department and Yunnan University under Grant No.2018FY001014.

ZHU Juanping, MENG Qi, CHEN Wei, WANG Yue, MA Zhiming. Constructing the Basis Path Set by Eliminating the Path Dependency[J]. Journal of Systems Science and Complexity, 2022, 35(5): 1944-1962.

The newly appeared$\mathcal{G}$-SGD algorithm can only heuristically find the basis path set in a simple neural network,so its generalization to a more practical network is hindered.From the perspective of graph theory,the BasisPathSetSearching problem is formulated to find the basis path set in a complicated fully connected neural network.This paper proposes algorithm DEAH to hierarchically solve the BasisPathSetSearching problem by eliminating the path dependencies.For this purpose,the authors discover the underlying cause of the path dependency between two independent substructures.The path subdivision chain is proposed to effectively eliminate the path dependency,both inside the chain and between chains.The theoretical proofs and the analysis of time complexity are presented for Algorithm DEAH.This paper therefore provides one methodology to find the basis path set in a general and practical neural network.
 [1] Wu S, Dimakis A G, and Sanghavi S, Learning distributions generated by one-layer ReLU networks, 33rd Conference on Neural Information Processing Systems (NeurIPS 2019), Vancouver, Canada, 2019.[2] Wang Y, Liu Y T, and Ma Z M, The scale-invariant space for attention layer in neural network, Neurocomputing, 2020, 392:1-10.[3] Neeyshabur B, Salakhutdinov R R, and Srebro N, Path-sgd:Path normalized optimization in deep neural networks, NIPS 15 Proceedings of the 28th International Conference on Neural Information Processing Systems, 2015, 2422-2430.[4] Zheng S X, Meng Q, Zhang H S, et al., Capacity control of ReLU neural networks by basis-path norm, Thirty-third AAAI Conference on Artificial Intelligence (AAAI2019), 2019.[5] Meng Q, Zheng S X, Zhang H S, et al., G-SGD:Optimizing ReLU neural networks in its positively scale-invariant space, International Conference of Learning Representations (ICLR2019), 2019.[6] Rumelhart D E, Hinton G E, and Williams R J, Learning representations by back-propagating errors, Nature, 1986, 323(6088):533-536.[7] Fan F, Xiong J, Li M, et al., On interpretability of artificial neural networks:A survey, IEEE Transactions on Radiation and Plasma Medical Sciences, 2021, 5(6):741-760.[8] Guan C, Wang X, Zhang Q, et al., Towards a deep and unified understanding of deep neural models in NLP, Proceedings of the 36th International Conference on Machine Learning, Long Beach, California, USA, 2019.[9] Hooker S, Erhan D, Kidermans P, et al., A Benchmark for Interpretability Methods in Deep Neural Networks, 33rd Conference on Neural Information Processing Systems (NeurIPS 2019), Vancouver, Canada, 2019.[10] Inoue K, Expressive numbers of two or more hidden layer ReLU neural networks, 2019 Seventh International Symposium on Computing and Networking workshops (CANDARW 2019), 2019.[11] Zhang Q S, Cao R M, Shi F, et al., Interpreting CNN knowledge via an explanatory graph, The Thirty-Second AAAI Conference on Artificial Intelligence, 2018, 4454-4463.[12] Wu M, Wicker M, Ruan W, et al., A game-based approximate verification of deep neural networks with provable guarantees, Theoretical Computer Science, 2020, 807:298-329.[13] Ensign D, Neville S, Paul A, et al., The complexity of explaining neural networks through (group) invariants, Theoretical Computer Science, 2020, 808:74-85.[14] Xing R T, Xiao M, Zhang Y Z, et al., Stability and Hopf bifurcation analysis of an (n+m)-neuron double-ring neural network model with multiple time delays, Journal of Systems Science&Complexity, 2021, DOI:10.1007/s11424-021-0108-2.[15] Zhu J P, Meng Q, Chen W, et al., Interpreting basis path set in neural networks, Journal of Systems Science and Complexity, 2020, 33(1):1-13.[16] Corberan A and Laporte G, Arc Routing Problems, Methods, and Applications, Society for Industrial and Applied Mathematics, 2015.[17] Jensen J B and Gutin G Z, Digraphs:Theory, Algorithms and Applications (Second Edition), Springer, New York, 2009.[18] Korte B and Vygen J, Combinatorial Optimization, Theory and Algorithm (Fifth Edition), Springer, New York, 2012.[19] Babu C S and Diwan A A, Subdivisions of graphs:A generalization of paths and cycles, Discrete Mathematics, 2008, 308(19):4479-4486.[20] Bondy J A and Murty U S R, Graph Theory, Section 10.1, 2008.[21] Dettlaff M, Raczek J, and Yero I G, Edge subdivision and edge multisubdivision versus some domination related parameters in generalized corona graph, Opuscula Mathematica, 2016, 36(5):575-588.[22] Chaieb M, Jemai J, and Mellouli K, A hierarchical decomposition framework for modeling combinatorial optimization problems, Procedia Computer Science, 2015, 60:478-487.[23] Chang Y, Tang H, Cheng Y, et al., Dynamic hierarchical energy efficient method based on combinatorial optimization for wireless sensor networks, Sensors, 2017, 17(7):1665.[24] Ochiai H, Kanazawa T, Tamura K, et al., Combinatorial optimization method based on hierarchical structure in solution space, Electronics and communications in Japan, 2016, 99(18):25-37.[25] Racke H, Optimal hierarchical decompositions for congestion minimization in networks, Proceedings of the 40th Annual ACM Symposium on Theory of Computing, 2008, 255-264.
 [1] BAI Yun, WANG Shouyang, ZHANG Xun. Foreign Trade Survey Data:Do They Help in Forecasting Exports and Imports? [J]. Journal of Systems Science and Complexity, 2022, 35(5): 1839-1862. [2] LIU Mingshuo, FANG Yong, DONG Huanhe. Equilibria and Stability Analysis of Cohen-Grossberg BAM Neural Networks on Time Scale [J]. Journal of Systems Science and Complexity, 2022, 35(4): 1348-1373. [3] ZHAO Yuzhuo, MA Dan, MA Hongwei. Adaptive Neural Network Control of Thermoacoustic Instability in Rijke Tube: A Fully Actuated System Approach [J]. Journal of Systems Science and Complexity, 2022, 35(2): 586-603. [4] GUO Yingxin, GE Shuzhi Sam, ARBI Adnène. Stability of Traveling Waves Solutions for Nonlinear Cellular Neural Networks with Distributed Delays [J]. Journal of Systems Science and Complexity, 2022, 35(1): 18-31. [5] NIAN Fuzhong · LI Jia. The Module-Phase Synchronization of Complex-Valued Neural Networks with Time-Varying Delay and Stochastic Perturbations [J]. Journal of Systems Science and Complexity, 2021, 34(6): 2139-2154. [6] ZHU Juanping · MENG Qi · CHEN Wei · MA Zhiming. Interpreting the Basis Path Set in Neural Networks [J]. Journal of Systems Science and Complexity, 2021, 34(6): 2155-2167. [7] QIAO Chen, LIANG Dong, SUN Kefeng. Dynamics Analysis for Generic Projection Continuous-Time RNNs with Bounded Matrices [J]. Journal of Systems Science and Complexity, 2015, 28(4): 799-812. [8] BENEKI Christina , YARMOHAMMADI Masoud. FORECASTING EXCHANGE RATES: AN OPTIMAL APPROACH [J]. Journal of Systems Science and Complexity, 2014, 27(1): 21-28. [9] XIAO Yi , XIAO Jin , LIU John , WANG Shouyang. A MULTISCALE MODELING APPROACH INCORPORATING ARIMA AND ANNS FOR FINANCIAL MARKET VOLATILITY FORECASTING [J]. Journal of Systems Science and Complexity, 2014, 27(1): 225-236. [10] CHEN Qiang , YU Li, NAN Yurong. FINITE-TIME TRACKING CONTROL FOR MOTOR SERVO SYSTEMS WITH UNKNOWN DEAD-ZONES [J]. Journal of Systems Science and Complexity, 2013, 26(6): 940-956. [11] GUO Jianxin , ZHANG Qiang, GAO Xiao-Shan. TRACKING ERROR REDUCTION IN CNC MACHINING BY RESHAPING THE KINEMATIC TRAJECTORY [J]. Journal of Systems Science and Complexity, 2013, 26(5): 817-835. [12] Jianjun WANG;Zongben XU. NEURAL NETWORKS AND THE BEST TRIGOMOMETRIC APPROXIMATION [J]. Journal of Systems Science and Complexity, 2011, 24(2): 401-412. [13] Zhenping LI;Ruisheng WANG;Xiang-Sun ZHANG;Luonan CHEN. SELF-ORGANIZING MAP OF COMPLEX NETWORKS FOR COMMUNITYDETECTION [J]. Journal of Systems Science and Complexity, 2010, 23(5): 931-941. [14] Yong ZHAO;Qishao LU ;Zhaosheng FENG. STABILITY FOR THE MIX-DELAYED COHEN-GROSSBERG NEURAL NETWORKS WITH NONLINEAR IMPULSE [J]. Journal of Systems Science and Complexity, 2010, 23(3): 665-680. [15] Ronghu CHI;Zhongsheng HOU. A NEW NEURAL NETWORK-BASED ADAPTIVE ILC FOR NONLINEAR DISCRETE-TIME SYSTEMS WITH DEAD ZONE SCHEME [J]. Journal of Systems Science and Complexity, 2009, 22(3): 435-445.
Viewed
Full text

Abstract