基於使用循環關係性類神經網路解數獨之 規則解釋模組

以作者查詢圖書館館藏

、以作者查詢臺灣博碩士

、以作者查詢全國書目

、勘誤回報

、線上人數：27

、訪客IP：3.147.86.216

姓名

劉宗祐(LAU CHUNG YAU) 查詢紙本館藏

畢業系所

資訊工程學系

論文名稱

基於使用循環關係性類神經網路解數獨之規則解釋模組
(Rule-based Explaining Module for Solving Sudoku using Recurrent Relational Network)

相關論文

★ 基於edX線上討論板社交關係之分組機制	★ 利用Kinect建置3D視覺化之Facebook互動系統
★ 利用 Kinect建置智慧型教室之評量系統	★ 基於行動裝置應用之智慧型都會區路徑規劃機制
★ 基於分析關鍵動量相關性之動態紋理轉換	★ 基於保護影像中直線結構的細縫裁減系統
★ 建基於開放式網路社群學習環境之社群推薦機制	★ 英語作為外語的互動式情境學習環境之系統設計
★ 基於膚色保存之情感色彩轉換機制	★ 一個用於虛擬鍵盤之手勢識別框架
★ 分數冪次型灰色生成預測模型誤差分析暨電腦工具箱之研發	★ 使用慣性傳感器構建即時人體骨架動作
★ 基於多台攝影機即時三維建模	★ 基於互補度與社群網路分析於基因演算法之分組機制
★ 即時手部追蹤之虛擬樂器演奏系統	★ 基於類神經網路之即時虛擬樂器演奏系統

檔案

[Endnote RIS 格式]

[Bibtex 格式]

[相關文章]

[文章引用]

[完整記錄]

[館藏目錄]

[檢視]

[下載]

本電子論文使用權限為同意立即開放。
已達開放權限電子全文僅授權使用者為學術研究之目的，進行個人非營利性質之檢索、閱讀、列印。
請遵守中華民國著作權法之相關規定，切勿任意重製、散佈、改作、轉貼、播送，以免觸法。

摘要(中)

近年來有越來越多關於機器學習的應用，在很多不同的領域中都會使用類神經網路作為輔助的工具來加速以及改善原本工作的表現和效率。雖然機器學習已被廣泛的使用，但是在某一些領域中如果涉及到非常重要的決定的話，則仍然可能會讓人懷疑類神經網路的可信度和可靠度，例如在醫學上的應用。類神經網路讓人懷疑的原因絕大部份是來自於它的「黑盒子」特色。類神經網路的學習只取決於人們給它的資料，但是人們並不懂為甚麼類神經網路會做出那樣的決定。由於類神經網路輸出結果缺乏參考資料，使得人們無法完全信賴類神經網路以及機器學習所帶來的任何決定。
在此，我們提出一個規則解釋模組 (Rule-based Explaining Module) 針對於使用規則來解釋循環關係性類神經網路 (Recurrent Relational Network) 的輸出結果。我們選擇RRN作為我們解釋的對象是因為RRN本身擁有關係的特性能為它自己本身學習解釋自身帶來不少好處。規則解釋模組核心的想法是易於實作和能夠輕易地加入各種類神經網路上，以改善它們輸出結果的說服力。模組需要前置的知識，又或是說規則來進行學習解釋。我們將會討論相關的研究、我們的方法以及最後在解數獨上進行實驗。我們實驗使用了Gordon Royle的Minimum Sudoku作為資料集的基底，並加上我們的規則解數獨步驟器 (Rule-based Sudoku Step Solver) 的處理，最後輸出解數獨所需要的規則資料給予規則解釋模組進行學習。最後我們實驗的辨認規則平均準確度達到98%以上。

摘要(英)

Nowadays, there are more and more applications based on the machine learning. Many areas are using neural network as a support tool to their works. However, in some areas that may include crucial decision which may cause some doubt to the people of whether the neural network is reliable or not such as medical usage. Although there are many applications based on machine learning, people are not fully trusted the neural network because of its unexplainable results from the “black box”. Neural network only learns the solution by feeding datasets to it and people don’t know why a trained neural network will make a specific decision. People can’t totally trust it without any reference.
Therefore, we proposed Rule-based Explaining Module (REM) to add further explanation to the Recurrent Relational Network’s (RRN) outputs, which we chosen RRN as the most suitable neural network for our module because of its feature of learning the relations that beneficial for learning to explain itself. The core idea of the module is to be easily implemented and be able to applies to different neural networks for improving the persuasion of the output. It requires the prior knowledge or called rules to provide to the REM to learn to explain. We are going to have discussions to related work, our main method and finally test our model with experiments on solving Sudoku puzzles. We preprocess the Minimum Sudoku from Gordon Royle and other Sudoku puzzle datasets with our Rule-based Sudoku Step Solver and generated the rule for our REM to learn. We got a positive result from our experiment receiving over 98% of accuracy of the rules.

關鍵字(中)

★ 可解釋人工智慧
★ 循環關係性類神經網路
★ 數獨

關鍵字(英)

★ Explainable AI
★ Recurrent Relational Network
★ Sudoku

論文目次

摘要 i
Abstract ii
List of Figures iii
List of Tables iv
Glossary and List of Abbreviations v
1 Introduction 1
2 Related Work 5
2.1 Expert System 5
2.1.1 CLIPS 6
2.2 Graph Neural Network 7
2.2.1 GNNExplainer 7
2.3 Relational Network 9
2.3.1 Recurrent Relational Network 9
2.3.2 Discriminative Relational Recurrent Network 10
2.4 Explainable AI (XAI) 12
2.4.1 Neural-Symbolic Computing 12
2.4.2 Automated Concept-based Explanation (ACE) 13
3 Methodology 15
3.1 Recurrent Relational Network 15
3.1.1 Model Architecture 17
3.1.2 Message passing 18
3.1.3 Recurrent Nodes Update 19
3.1.4 Output from hidden state 19
3.2 Rule-based Explaining Module 20
3.2.1 Multi-tasks learning 22
3.2.2 Separated tasks optimization learning 23
3.3 Rules and Rule-based Sudoku Step Solver 25
3.3.1 Sudoku solving rules 25
3.3.2 Rule-based Sudoku Step Solver 31
4 Experiments 33
4.1 Datasets 33
4.1.1 1 million Sudoku games (1M Sudoku) 33
4.1.2 Gordon Royle’s Minimum Sudoku 34
4.2 Dataset preprocessing 35
4.2.1 Gathering data from Minimum Sudoku 35
4.3 Results of Rule-based Sudoku Step Solver 37
4.3.1 Sudoku solving result on Minimum Sudoku 37
4.3.2 Sudoku solving result on 1 million Sudoku games 37
4.4 Results of Rule-based Explanation Module 38
4.4.1 Training 38
4.4.2 Testing 40
4.4.3 Rules explanation example 44
5 Discussion and Conclusion 48
6 Reference 50

參考文獻

[1] A. Adadi, M. Berrada, “Peeking Inside the Black-Box: A Survey on Explainable Artificial Intelligence (XAI),” in IEEE Access, vol. 6, pp. 52138-52160, doi: 10.1109/ACCESS.2018.2870052, 2018
[2] Gary Riley, “Implementation of CLIPS Expert System Sudoku solving” https://sourceforge.net/p/clipsrules/code/HEAD/tree/branches/63x/examples/sudoku/
[3] Franco Scarselli, Marco Gori, “The Graph Neural Network Model”, IEEE TRANSACTIONS ON NEURAL NETWORKS, VOL. 20, NO. 1, JANUARY 2009
[4] Zhitao Ying, Dylan Bourgeois, Jiaxuan You et al., “GNNExplainer: Generating Explanations for Graph Neural Networks”, Advances in Neural Information Processing Systems 32 (NeurIPS 2019)
[5] Rasmus Berg Palm, Ulrich Paquet, Ole Winther, “Recurrent Relational Networks”, Advances in Neural Information Processing Systems 31 (NeurIPS 2018)
[6] Adam Santoro, David Raposo, “A simple neural network module for relational reasoning”, Advances in Neural Information Processing Systems 30 (NeurIPS 2017)
[7] Bernhard Hobiger, “HoDoKu - Sudoku generator/solver/trainer/analyzer”, http://hodoku.sourceforge.net/en/index.php
[8] Chen Sun, Abhinav Shrivastava, Carl Vondrick et al., “Relational Action Forecasting”, 2019 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR 2019)
[9] Luís C. Lamb, Artur d’Avila Garcez, Marco Gori et al., “Graph Neural Networks Meet Neural-Symbolic Computing: A Survey and Perspective”, Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence Survey track. Pages 4877-4884. https://doi.org/10.24963/ijcai.2020/679 (IJCAI 2020)
[10] Gordon Royle, “Minimum Sudoku”, http://staffhome.ecm.uwa.edu.au/~00013890/sudokumin.php
[11] Arel Cordero, “AREL’s SUDOKU GENERATOR”, https://www.ocf.berkeley.edu/~arel/sudoku/main.html
[12] Kyubyong Park, “1 million Sudoku games”, https://www.kaggle.com/bryanpark/sudoku
[13] Gordon Royle, “Good at Sudoku? Here’s some you’ll never complete”, https://theconversation.com/good-at-sudoku-heres-some-youll-never-complete-5234
[14] Luis C. Lamb, Artur d’Avila Garcez, Marco Gori et al., “Graph Neural Networks Meet Neural-Symbolic Computing: A Survey and Perspective”, Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence (IJCAI-20) Survey Track
[15] Artur d′Avila Garcez, Marco Gori, Luis C. Lamb et al., “Neural-Symbolic Computing: An Effective Methodology for Principled Integration of Machine Learning and Reasoning”, https://arxiv.org/abs/1905.06088
[16] Fan Yang, Zhilin Yang, William W. Cohen, “Differentiable Learning of Logical Rules for Knowledge Base Reasoning”, Advances in Neural Information Processing Systems 30 (NeurIPS 2017)
[17] Bologna, G. “A Simple Convolutional Neural Network with Rule Extraction”, Appl. Sci. 2019, 9, 2411. https://doi.org/10.3390/app9122411
[18] Amirata Ghorbani, James Zou, James Wexler et al., “Towards Automatic Concept-based Explanations”, Advances in Neural Information Processing Systems 32 (NeurIPS 2019)
[19] A. Adadi and M. Berrada, “Peeking Inside the Black-Box: A Survey on Explainable Artificial Intelligence (XAI)” , in IEEE Access, vol. 6, pp. 52138-52160, 2018, doi: 10.1109/ACCESS.2018.2870052.
[20] Peter Norvig, “Solving Every Sudoku Puzzle”, https://norvig.com/sudoku.html

指導教授

施國琛(Timothy K. Shih)

審核日期

2021-8-11

推文