Skip to main content
main-content
Top

Hint

Swipe to navigate through the articles of this issue

26-09-2022

Neural Combinatorial Optimization with Explanation

Authors: Zhaoyi Liu, Qianqian Duan

Published in: Neural Processing Letters

Login to get access
share
SHARE

Abstract

Different from traditional operational research optimization algorithms, Deep Learning can solve combinatorial optimization problems in real time and has been widely used. However, these models based on pointer network have difficulty in obtaining features on the graph, they are not conducive to solving problems that are modeled on the graph. Secondly, as the structure of deep learning models becomes more complex, the explanation and analysis of the models becomes more difficult. There is a lack of interpretable work on models, which seriously hinders the development of Deep Learning. In order to solve these problems, a policy network that can effectively encode features on the graph and is interpretable is proposed. Specifically, a model structure in the field of graph neural network is introduced to extract the features on the graph, and a policy network is built, the network is trained using Reinforcement Learning; an agent-based interpretability method is used to mine the features that be used as explanation in the initial feature, these mined features are used to explain the actions of policy network.The effectiveness of the above methods is verified by experiments for solving the Traveling Salesman Problem: Policy network can effectively encode the features on the graph and has good generalization ability; The interpretability experiment shows that the actions of the policy network can be explained, which proves the interpretability of the policy network.
Literature
1.
go back to reference Rahmaniani R, Crainic TG, Gendreau M, Rei W (2017) The Benders decomposition algorithm: A literature review. Eur J Oper Res 259(3):801–817 MathSciNetMATHCrossRef Rahmaniani R, Crainic TG, Gendreau M, Rei W (2017) The Benders decomposition algorithm: A literature review. Eur J Oper Res 259(3):801–817 MathSciNetMATHCrossRef
2.
go back to reference Festa P (2014) A brief introduction to exact, approximation, and heuristic algorithms for solving hard combinatorial optimization problems. In: 2014 16th international conference on transparent optical networks (ICTON), pp 1–20. IEEE. Festa P (2014) A brief introduction to exact, approximation, and heuristic algorithms for solving hard combinatorial optimization problems. In: 2014 16th international conference on transparent optical networks (ICTON), pp 1–20. IEEE.
3.
go back to reference Papadimitriou CH, Steiglitz K (1998) Combinatorial optimization: algorithms and complexity. Courier Corporation, Chelmsford MATH Papadimitriou CH, Steiglitz K (1998) Combinatorial optimization: algorithms and complexity. Courier Corporation, Chelmsford MATH
5.
go back to reference LeCun Y, Bengio Y, Hinton G (2015) Deep learning. Nature 521(7553):436–444 CrossRef LeCun Y, Bengio Y, Hinton G (2015) Deep learning. Nature 521(7553):436–444 CrossRef
6.
go back to reference Silver D, Schrittwieser J, Simonyan K, Antonoglou I, Huang A, Guez A, Hubert T, Baker L, Lai M, Bolton A, Chen Y (2017) Mastering the game of go without human knowledge. Nature 550(7676):354–359 CrossRef Silver D, Schrittwieser J, Simonyan K, Antonoglou I, Huang A, Guez A, Hubert T, Baker L, Lai M, Bolton A, Chen Y (2017) Mastering the game of go without human knowledge. Nature 550(7676):354–359 CrossRef
7.
go back to reference Zhang Y, Defazio D, Ramesh A (2021) Relex: A model-agnostic relational model explainer. In: Proceedings of the 2021 AAAI/ACM conference on AI, ethics, and society, pp 1042–1049. Zhang Y, Defazio D, Ramesh A (2021) Relex: A model-agnostic relational model explainer. In: Proceedings of the 2021 AAAI/ACM conference on AI, ethics, and society, pp 1042–1049.
8.
go back to reference Sutskever I, Vinyals O, Le QV (2014) Sequence to sequence learning with neural networks. Adv Neural Inf Process Syst, 27. Sutskever I, Vinyals O, Le QV (2014) Sequence to sequence learning with neural networks. Adv Neural Inf Process Syst, 27.
9.
go back to reference Vinyals O, Fortunato M, Jaitly N (2015) Pointer networks. Adv Neural Inf Process Syst, 28. Vinyals O, Fortunato M, Jaitly N (2015) Pointer networks. Adv Neural Inf Process Syst, 28.
10.
go back to reference Graves A (2012) Long short-term memory. Supervised Sequence Labelling with Recurrent Neural Networks, 37–45. Graves A (2012) Long short-term memory. Supervised Sequence Labelling with Recurrent Neural Networks, 37–45.
11.
go back to reference Socher R, Lin CCY, Ng AY, Manning CD (2011) Parsing natural scenes and natural language with recursive neural networks. In: ICML Socher R, Lin CCY, Ng AY, Manning CD (2011) Parsing natural scenes and natural language with recursive neural networks. In: ICML
13.
go back to reference Mnih V, Badia AP, Mirza M, Graves A, Lillicrap T, Harley T, Silver D, Kavukcuoglu K (2016) Asynchronous methods for deep reinforcement learning. In: International conference on machine learning, pp 1928–1937. PMLR Mnih V, Badia AP, Mirza M, Graves A, Lillicrap T, Harley T, Silver D, Kavukcuoglu K (2016) Asynchronous methods for deep reinforcement learning. In: International conference on machine learning, pp 1928–1937. PMLR
14.
go back to reference Nazari M, Oroojlooy A, Snyder L, Takác M (2018) Reinforcement learning for solving the vehicle routing problem. Adv Neural Inf Process Syst, 31 Nazari M, Oroojlooy A, Snyder L, Takác M (2018) Reinforcement learning for solving the vehicle routing problem. Adv Neural Inf Process Syst, 31
15.
go back to reference Vaswani A, Shazeer N, Parmar N, Uszkoreit J, Jones L, Gomez AN, Kaiser Ł, Polosukhin I (2017) Attention is all you need. Adv Neural Inf Process Syst, 30 Vaswani A, Shazeer N, Parmar N, Uszkoreit J, Jones L, Gomez AN, Kaiser Ł, Polosukhin I (2017) Attention is all you need. Adv Neural Inf Process Syst, 30
16.
go back to reference Deudon M, Cournut P, Lacoste A, Adulyasak Y, Rousseau LM (2018) Learning heuristics for the tsp by policy gradient. In: International conference on the integration of constraint programming, artificial intelligence, and operations research, pp 170–181. Springer, Cham. Deudon M, Cournut P, Lacoste A, Adulyasak Y, Rousseau LM (2018) Learning heuristics for the tsp by policy gradient. In: International conference on the integration of constraint programming, artificial intelligence, and operations research, pp 170–181. Springer, Cham.
18.
go back to reference Rennie SJ, Marcheret E, Mroueh Y, Ross J, Goel V (2017) Self-critical sequence training for image captioning. In: Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 7008–7024 Rennie SJ, Marcheret E, Mroueh Y, Ross J, Goel V (2017) Self-critical sequence training for image captioning. In: Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 7008–7024
19.
go back to reference Zhang Z, Wu Z, Zhang H, Wang J (2022) Meta-learning-based deep reinforcement learning for multiobjective optimization problems. IEEE Trans Neural Netw Learn Syst. Zhang Z, Wu Z, Zhang H, Wang J (2022) Meta-learning-based deep reinforcement learning for multiobjective optimization problems. IEEE Trans Neural Netw Learn Syst.
20.
go back to reference Khalil E, Dai H, Zhang Y, Dilkina B, Song L (2017) Learning combinatorial optimization algorithms over graphs. Adv Neural Inf Process Syst, 30. Khalil E, Dai H, Zhang Y, Dilkina B, Song L (2017) Learning combinatorial optimization algorithms over graphs. Adv Neural Inf Process Syst, 30.
21.
go back to reference Dai H, Dai B, Song L (2016) Discriminative embeddings of latent variable models for structured data. In: International conference on machine learning, pp. 2702–2711. PMLR. Dai H, Dai B, Song L (2016) Discriminative embeddings of latent variable models for structured data. In: International conference on machine learning, pp. 2702–2711. PMLR.
22.
go back to reference Mnih V, Kavukcuoglu K, Silver D, Rusu AA, Veness J, Bellemare MG, Graves A, Riedmiller M, Fidjeland AK, Ostrovski G, Petersen S (2015) Human-level control through deep reinforcement learning. Nature 518(7540):529–533 CrossRef Mnih V, Kavukcuoglu K, Silver D, Rusu AA, Veness J, Bellemare MG, Graves A, Riedmiller M, Fidjeland AK, Ostrovski G, Petersen S (2015) Human-level control through deep reinforcement learning. Nature 518(7540):529–533 CrossRef
23.
go back to reference Manchanda S, Mittal A, Dhawan A, Medya S, Ranu S, Singh A (2019) Learning heuristics over large graphs via deep reinforcement learning. arXiv:​1903.​03332. Manchanda S, Mittal A, Dhawan A, Medya S, Ranu S, Singh A (2019) Learning heuristics over large graphs via deep reinforcement learning. arXiv:​1903.​03332.
24.
go back to reference Li Z, Chen Q, Koltun V (2018) Combinatorial optimization with graph convolutional networks and guided tree search. Adv Neural Inf Process Syst, 31. Li Z, Chen Q, Koltun V (2018) Combinatorial optimization with graph convolutional networks and guided tree search. Adv Neural Inf Process Syst, 31.
25.
26.
go back to reference Bengio Y, Lodi A, Prouvost A (2021) Machine learning for combinatorial optimization: a methodological tour d’horizon. Eur J Oper Res 290(2):405–421 MathSciNetMATHCrossRef Bengio Y, Lodi A, Prouvost A (2021) Machine learning for combinatorial optimization: a methodological tour d’horizon. Eur J Oper Res 290(2):405–421 MathSciNetMATHCrossRef
27.
go back to reference Bodapati JD, Srilakshmi U, Veeranjaneyulu N (2022) FERNet: a deep CNN architecture for facial expression recognition in the wild. J Inst Eng India Ser B 103(2):439–448 CrossRef Bodapati JD, Srilakshmi U, Veeranjaneyulu N (2022) FERNet: a deep CNN architecture for facial expression recognition in the wild. J Inst Eng India Ser B 103(2):439–448 CrossRef
28.
go back to reference Williams RJ (1992) Simple statistical gradient-following algorithms for connectionist reinforcement learning. Mach Learn 8(3):229–256 MATHCrossRef Williams RJ (1992) Simple statistical gradient-following algorithms for connectionist reinforcement learning. Mach Learn 8(3):229–256 MATHCrossRef
29.
go back to reference Huang Q, Yamada M, Tian Y, Singh D, Yin D, Chang Y (2020). Graphlime: Local interpretable model explanations for graph neural networks. arXiv:​2001.​06216. Huang Q, Yamada M, Tian Y, Singh D, Yin D, Chang Y (2020). Graphlime: Local interpretable model explanations for graph neural networks. arXiv:​2001.​06216.
30.
go back to reference Karda K, Dubey N, Kanungo A, Gupta V (2022) Automation of noise sampling in deep reinforcement learning. Int J Appl Pattern Recogn 7(1):15–23 CrossRef Karda K, Dubey N, Kanungo A, Gupta V (2022) Automation of noise sampling in deep reinforcement learning. Int J Appl Pattern Recogn 7(1):15–23 CrossRef
31.
go back to reference Gupta V, Mittal M, Mittal V (2021) An efficient low computational cost method of R-peak detection. Wireless Pers Commun 118(1):359–381 CrossRef Gupta V, Mittal M, Mittal V (2021) An efficient low computational cost method of R-peak detection. Wireless Pers Commun 118(1):359–381 CrossRef
32.
go back to reference Gupta V, Mittal M (2020) Arrhythmia detection in ECG signal using fractional wavelet transform with principal component analysis. J Inst Eng (India): Series B 101(5):451–461 Gupta V, Mittal M (2020) Arrhythmia detection in ECG signal using fractional wavelet transform with principal component analysis. J Inst Eng (India): Series B 101(5):451–461
33.
go back to reference Gupta V, Mittal M, Mittal V, Saxena NK (2021) A critical review of feature extraction techniques for ECG signal analysis. J Inst Eng (India) Ser B 102(5):1049–1060 CrossRef Gupta V, Mittal M, Mittal V, Saxena NK (2021) A critical review of feature extraction techniques for ECG signal analysis. J Inst Eng (India) Ser B 102(5):1049–1060 CrossRef
34.
go back to reference Gupta V, Mittal M, Mittal V, Saxena NK (2021) BP signal analysis using emerging techniques and its validation using ECG signal. Sens Imag 22(1):1–19 Gupta V, Mittal M, Mittal V, Saxena NK (2021) BP signal analysis using emerging techniques and its validation using ECG signal. Sens Imag 22(1):1–19
35.
go back to reference Gupta V, Mittal M (2021) R-peak detection for improved analysis in health informatics. Int J Med Eng Inf 13(3):213–223 Gupta V, Mittal M (2021) R-peak detection for improved analysis in health informatics. Int J Med Eng Inf 13(3):213–223
36.
go back to reference Gupta V, Mittal M, Mittal V (2021) Chaos theory and ARTFA: emerging tools for interpreting ECG signals to diagnose cardiac arrhythmias. Wireless Pers Commun 118(4):3615–3646 CrossRef Gupta V, Mittal M, Mittal V (2021) Chaos theory and ARTFA: emerging tools for interpreting ECG signals to diagnose cardiac arrhythmias. Wireless Pers Commun 118(4):3615–3646 CrossRef
37.
go back to reference Gupta V, Mittal M (2020) Efficient R-peak detection in electrocardiogram signal based on features extracted using Hilbert transform and Burg method. J Inst Eng (India): Ser B 101(1):23–34 Gupta V, Mittal M (2020) Efficient R-peak detection in electrocardiogram signal based on features extracted using Hilbert transform and Burg method. J Inst Eng (India): Ser B 101(1):23–34
38.
go back to reference Gupta V, Mittal M, Mittal V (2020) Chaos theory: an emerging tool for arrhythmia detection. Sens Imag 21(1):1–22 Gupta V, Mittal M, Mittal V (2020) Chaos theory: an emerging tool for arrhythmia detection. Sens Imag 21(1):1–22
39.
go back to reference Gupta V, Mittal M (2019) QRS complex detection using STFT, chaos analysis, and PCA in standard and real-time ECG databases. J Inst Eng (India): Ser B 100(5):489–497 Gupta V, Mittal M (2019) QRS complex detection using STFT, chaos analysis, and PCA in standard and real-time ECG databases. J Inst Eng (India): Ser B 100(5):489–497
40.
go back to reference Gupta V, Saxena NK, Kanungo A, Kumar P, Diwania S (2022) PCA as an effective tool for the detection of R-peaks in an ECG signal processing. Int J Syst Assur Eng Manag, 1–13. Gupta V, Saxena NK, Kanungo A, Kumar P, Diwania S (2022) PCA as an effective tool for the detection of R-peaks in an ECG signal processing. Int J Syst Assur Eng Manag, 1–13.
41.
go back to reference Gupta V, Mittal M, Mittal V (2022) A Novel FrWT Based Arrhythmia Detection in ECG Signal Using YWARA and PCA. Wireless Pers Commun 124(2):1229–1246 CrossRef Gupta V, Mittal M, Mittal V (2022) A Novel FrWT Based Arrhythmia Detection in ECG Signal Using YWARA and PCA. Wireless Pers Commun 124(2):1229–1246 CrossRef
42.
go back to reference Gupta V, Mittal M, Mittal V (2021). FrWT-PPCA-based R-peak detection for improved management of healthcare system. IETE J Res, 1–15 Gupta V, Mittal M, Mittal V (2021). FrWT-PPCA-based R-peak detection for improved management of healthcare system. IETE J Res, 1–15
43.
go back to reference Gupta V, Mittal M, Mittal V, Gupta A (2022) An efficient AR modelling-based electrocardiogram signal analysis for health informatics. Int J Med Eng Inf 14(1):74–89 Gupta V, Mittal M, Mittal V, Gupta A (2022) An efficient AR modelling-based electrocardiogram signal analysis for health informatics. Int J Med Eng Inf 14(1):74–89
44.
go back to reference Gupta V, Mittal M, Mittal V, Chaturvedi Y (2022) Detection of R-peaks using fractional Fourier transform and principal component analysis. J Ambient Intell Humaniz Comput 13(2):961–972 CrossRef Gupta V, Mittal M, Mittal V, Chaturvedi Y (2022) Detection of R-peaks using fractional Fourier transform and principal component analysis. J Ambient Intell Humaniz Comput 13(2):961–972 CrossRef
45.
go back to reference Martens D, Provost F (2014) Explaining data-driven document classifications. MIS Quarter 38(1):73–100 CrossRef Martens D, Provost F (2014) Explaining data-driven document classifications. MIS Quarter 38(1):73–100 CrossRef
Metadata
Title
Neural Combinatorial Optimization with Explanation
Authors
Zhaoyi Liu
Qianqian Duan
Publication date
26-09-2022
Publisher
Springer US
Published in
Neural Processing Letters
Print ISSN: 1370-4621
Electronic ISSN: 1573-773X
DOI
https://doi.org/10.1007/s11063-022-11028-9