Skip to main content
main-content

Tipp

Weitere Artikel dieser Ausgabe durch Wischen aufrufen

26.09.2022

Neural Combinatorial Optimization with Explanation

verfasst von: Zhaoyi Liu, Qianqian Duan

Erschienen in: Neural Processing Letters

Einloggen, um Zugang zu erhalten
share
TEILEN

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.
Literatur
1.
Zurück zum Zitat 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.
Zurück zum Zitat 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.
Zurück zum Zitat 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
4.
5.
Zurück zum Zitat 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.
Zurück zum Zitat 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.
Zurück zum Zitat 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.
Zurück zum Zitat 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.
Zurück zum Zitat 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.
Zurück zum Zitat 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.
Zurück zum Zitat 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
12.
13.
Zurück zum Zitat 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.
Zurück zum Zitat 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.
Zurück zum Zitat 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.
Zurück zum Zitat 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.
Zurück zum Zitat 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.
Zurück zum Zitat 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.
Zurück zum Zitat 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.
Zurück zum Zitat 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.
Zurück zum Zitat 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.
Zurück zum Zitat 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.
Zurück zum Zitat 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.
Zurück zum Zitat Joshi CK, Laurent T, Bresson X (2019) An efficient graph convolutional network technique for the travelling salesman problem. arXiv:​1906.​01227. Joshi CK, Laurent T, Bresson X (2019) An efficient graph convolutional network technique for the travelling salesman problem. arXiv:​1906.​01227.
26.
Zurück zum Zitat 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.
Zurück zum Zitat 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.
Zurück zum Zitat 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.
Zurück zum Zitat 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.
Zurück zum Zitat 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.
Zurück zum Zitat 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.
Zurück zum Zitat 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.
Zurück zum Zitat 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.
Zurück zum Zitat 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.
Zurück zum Zitat 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.
Zurück zum Zitat 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.
Zurück zum Zitat 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.
Zurück zum Zitat 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.
Zurück zum Zitat 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.
Zurück zum Zitat 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.
Zurück zum Zitat 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.
Zurück zum Zitat 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.
Zurück zum Zitat 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.
Zurück zum Zitat 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.
Zurück zum Zitat 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
Metadaten
Titel
Neural Combinatorial Optimization with Explanation
verfasst von
Zhaoyi Liu
Qianqian Duan
Publikationsdatum
26.09.2022
Verlag
Springer US
Erschienen in
Neural Processing Letters
Print ISSN: 1370-4621
Elektronische ISSN: 1573-773X
DOI
https://doi.org/10.1007/s11063-022-11028-9