指導教授：許永真臺灣大學：資訊工程學研究所柯賀祁KIRMIZI, HAKKI CANERHAKKI CANERKIRMIZI2014-11-262018-07-052014-11-262018-07-052014http://ntur.lib.ntu.edu.tw//handle/246246/261424對於智慧型代理人領域來說，賦予代理人常識推理的能力是很重要的一環，而進行常識推理的首要條件為擁有一個包含眾多基礎事實和事實間語義關係的知識庫。但是當知識的數量逐漸增加，知識管理也就變得越益複雜，因此利用在基礎事實上進行推理的方式來發掘新的關聯性和知識會比傳統使用一整個語義網路相對來得容易。本研究針對推理機制的需求，提出相應的推理方法來解決問題。 在本研究中，我提出不同的觀點，即是以語義圖步行問題來表示一個常識推理的問題。試想將一個知識庫當作一個語意超圖，則推理可被視為一個發掘概念間隱藏的關聯性之過程。在此表示法下，代理人被允許在不知道整個知識庫中所有的語意連結下透過語義圖步行法來合成語義關係，進而推理出新的知識。 雖然這個研究強調用於常識語義網路此一特定領域，但該合成法實為一般性方法。因為只要每一個特定連結都可被一個獨特的向量所表示，本方法將可以適用於在所有種類的超圖上發掘新的連結。實驗的部份，以 ConceptNet 5 此常識庫做為知識庫，進行語義圖步行推理法。分析結果指出，有許多的慣例可被以關係合成為基礎的方式推理出來。該研究除了評估ConceptNet在語義網中定義上的缺失，亦提出一些新的方向，像是語義圖步行推理法，該方法在未來可能能夠被實際使用。Enabling commonsense reasoning is an important task for intelligent agents. The very first requirement of commonsense reasoning problem is a large knowledge base containing basic facts and the semantic relations between these facts. As a knowledge base gradually becomes larger, knowledge management becomes more complex. Rather than requiring all semantic relations between concepts are present in a semantic network, a system which is provided a basic set of facts and an inference mechanism can easily discover new relationships and likewise infer new knowledge. This study attempts to address the need of such an inference mechanism and to present an inference method for this purpose. In this study, I offer another perspective to formalize commonsense reasoning problem in terms of semantic graph walk problem. Considering the knowledge base is encoded as a semantic hypergraph, reasoning can be formulated as a process to discover hidden relations between concepts. Likewise, semantic graph walk formalization allows the reasoning agents not to require all semantic relations between the concepts are present in their knowledge base and to be able to infer new knowledge by composing semantic relations in a graph walk manner. Although this study focuses on a specific domain, emph{i.e.} commonsense semantic networks, the composition mechanism encapsulates a generic method for so-called digraphs. Because each specific link is represented by a unique vector, the method can be generalized for all type of hypergraphs for discovering new links. An analysis of the experiments for semantic graph walk inference on top of ConceptNet 5 commonsense knowledge base demonstrates that there are strong heuristics that can be provided by relation composition method in terms of reasoning. The study also evaluates the shortcomings of ConceptNet definition of semantic networks as well as a few novel directions that semantic graph walk inference method might be used in the future.誌謝 iii Acknowledgements v 摘要 vii Abstract ix 1 Introduction 1 1.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.2 Basic Notations and Definitions . . . . . . . . . . . . . . . . . . . . . . 2 1.3 Problem Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.3.1 Graph Walk Formalization Problem . . . . . . . . . . . . . . . . 5 1.3.2 Graph Walk Inference Problem . . . . . . . . . . . . . . . . . . . 6 1.4 Solution Proposal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 1.4.1 Formalizing a subdigraph as a graph walk . . . . . . . . . . . . . 6 1.4.2 Formalizing reasoning problem as semantic graph walk inference 7 1.5 Thesis Organization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 2 Related Work 9 2.1 Modeling graph languages . . . . . . . . . . . . . . . . . . . . . . . . . 9 2.2 Relation Element Theory and Composition of Semantic Relations . . . . 10 2.3 Knowledge Representation and Commonsense Reasoning . . . . . . . . . 19 xi 3 Context-Free Grammar Formalization of Semantic Graph Walk 21 3.1 Graph Walk Formalization Problem and Solution . . . . . . . . . . . . . 22 3.2 Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 3.2.1 Single Path Graph Walk . . . . . . . . . . . . . . . . . . . . . . 24 3.2.2 Branching Path Graph Walk . . . . . . . . . . . . . . . . . . . . 27 3.3 Semantic actions of parsing graph walks . . . . . . . . . . . . . . . . . . 34 3.3.1 Semantic actions of parsing a single path graph walk . . . . . . . 34 3.3.2 Semantic actions of parsing a branching path graph walk . . . . . 34 4 Composition of Semantic Relations 39 4.1 Graph Walk Inference Problem and Solution . . . . . . . . . . . . . . . . 40 4.2 ConceptNet relations . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 4.3 Semantic Primitives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 4.3.1 A custom set of semantic primitives for ConceptNet . . . . . . . 42 4.4 Composition Algebra . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 4.4.1 An algebra for composing ConceptNet relations . . . . . . . . . . 45 4.5 Composition Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . 46 4.5.1 Composition of two relations . . . . . . . . . . . . . . . . . . . . 47 4.5.2 Iterative graph walk inference algorithm . . . . . . . . . . . . . . 48 4.6 Discriminator Coefficients of Relations . . . . . . . . . . . . . . . . . . 49 4.7 Analysis of pairwise combinations of relations . . . . . . . . . . . . . . . 50 5 Experiments 51 5.1 Example: Parsing a branching path graph walk . . . . . . . . . . . . . . 51 5.2 Example: Iterative graph walk inference . . . . . . . . . . . . . . . . . . 54 5.2.1 Graph Walk: ⟨IsA, HasP roperty, AtLocation⟩ . . . . . . . . . 54 5.3 Experiments with inference axioms . . . . . . . . . . . . . . . . . . . . . 57 5.3.1 Analysis of Experiments . . . . . . . . . . . . . . . . . . . . . . 58 6 Discussion 61 6.1 Limitations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61 xii 6.1.1 Composition without domain-range compatibility constraint . . . 61 6.1.2 Semantics of a chain of relations . . . . . . . . . . . . . . . . . . 61 6.1.3 Set of semantic relations . . . . . . . . . . . . . . . . . . . . . . 62 6.2 Future Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63 7 Conclusion 65 Bibliography 67879909 bytesapplication/pdf論文公開時間：2014/07/22論文使用權限：同意有償授權(權利金給回饋學校)知識建模推理引擎語意關係合成常識推理thesishttp://ntur.lib.ntu.edu.tw/bitstream/246246/261424/1/ntu-103-R00922148-1.pdf