## some more ideas

- Facts
- Based on simple wikipedia– simple grammar and simple words
- focus on collection first, and then individual and predicate
- determine the predicates first, limiting the number of predicate
- when processing, those with link can link out. thus we get the link out item
- i.e,
**William Franklin Graham, Jr.**(born November 7, 1918) better known as**Billy Graham**, is an Evangelical Christian and an evangelist.

- i.e,
- Build the graph

- Rule
- commonly used rules: genls, isA, hasA, specs

## idea

- knowledge source: simple wikipedia
- language: BASIC English

- vocabulary: 1000 most common
- http://esl.about.com/library/vocabulary/bl1000_alph1.htm
- http://simple.wikipedia.org/wiki/Wikipedia:Basic_English_combined_wordlist

- sentences to FOL: stanford parser
- determine the predicate first
- rule:OpenCyc: actually it’s still close source– just compiled classes

## simple english

wikipedia simple english version

http://simple.wikipedia.org/wiki/Simple_English_Wikipedia

## LAN

哦，那个书你没必要看的，上网搜一个图就可以了，输入rhichards rhetorical triangle就可以了，要书的话书名叫mencius on mind， I.A.Richards 写的

the meaning of meaning，那本里有一模一样的图

## Content

- Chapter 1 introduction
- Chap. 2 basic conceptual graphs
- Chap. 3 simple conceptual graphs
- Chap. 4 set and first order logic semantics are the core chapters and should be considered as the basis.
- For programming and algorithmic purposes the following materials can be added
- to the base:
- Chap. 6 basic algorithms for BG homomorphism
- Chap. 5 relationships with constraint programming techniques
- Chap. 7 techniques for trees and other tractable cases
- Chap. 8 algorithms for other specialization/generalization operations, especially maximal joins
- Chap. 10 rule processing), and Chap. 12 (algorithms for processing BGs with atomic negation
- For modeling purposes the following parts can be added to the base:
- Chap. 9 nested conceptual graphs ▲
- Chap. 10 definition and use of rules ▲
- Chap. 11 definition and use of constraints and their combination with rules▲
- Chap. 12 definition and use of atomic negation
- Chap. 13 semantic annotations

For more theory-oriented readers, expressivity, decidability and complexity results as well as stating equivalence with problems of other domains, are presented throughout the book, except in the last chapter.

This book is in electronic version, thus the note will be probably taken in the pdf file.

## July 1st Plan

- Look into the detail of Sowa’s Conceptual Graph
- Read the related chapters in
*Natural Language Understanding* - Decide whether I should read the rest chapters of principles of semantic networks

## Chapter 13 The Evolving Technology of Classification-based Knowledge Representation Systems

13.1 Introduction

The field of knowledge represnetation has not yet achieved the development of a general-purpose knowledge representation system(KRS)

This chapter outlines major principles that have been adopted by these systems, describes key features of several individual systems, and tries to identify unifying architectural themes among the various implementations that could evolve into a general purpose knowledge representation technology.

KL-ONE and its descendants share a commitment to the following architectureal features:

- They are logic-based( i.e., they appeal to first-order logic for their semantics)
- They draw a distinction between terminological and assertional knowledge, and each system implements its own specialized term-forming language
- They include a classifier that organizes terms(concepts) into a taxonomy, based on subsumption relationships between terms

13.3 Classsification-based Technology

A classification-based KRS includes two languages:

- a
*terminological*language is designed to facilitate the construction of expressions that describe classes of individuals. — “a brown, three-legged dog” - an
*assertion*language is to state constraints or facts that apply to a particular domain or world

1 2 3 |
(defconcept B3LD :is (:and Dog Brown-Thing (:exactly 3 has-leg))) |

assign B3LD to the concept representing “a brown, three-legged dog.” The assertion B3LD(Rover) states that Rover is a dog, is a brown thing, and has exactly three legs.

13.4 A KL-ONE family history

Important classifier technology issues

- terminological languages
- term classifiers
- assertion languages
- rule/constraint languages
- truth maintenance
- system performance

The defining characteristics of a TC system are

- its term-definition language
- its use of a concept classifier
- a database-like (object-centered) assertion language
- a forward-chaining recognizer
- a rule language
- automatic detection of inconsistent knowledge
- retraction of facts
- default reasoning

There is a variety of evidence suggesting that a KRS with an expressive terminological language(and incomplete classifier) is more useful tool than a KRS with a small terminological language( and a complete classifier).

## Logical Dimensions of Some Graph Formalisms

Sowa’s CSs have already been applied in NLU, HGs have such a potential, and the three-level semantics is currently being implemented as a part of an NLU system.

From a logical point of view, knowledge represnetation systems are usually disscussed along the following dimensions:

- Syntactic: What are the classes of well-formed expressions in these formalisms? Is one class bigger than the other?
- Semantic: What are their models? How can they be constructed? In other words, what are the entities the formalisms deal with, and what kind of relations can be expected to hold among them?
- Proof theoretic: What kind of inferences do these formalisms support? What kind of syntactic structures can be built by applying the rules and can any graph be derived?
- Decidability and computational complexity: How difficult is it to formally manipulate these objects? How difficult is it to prove something about them?

- Whether these formmalisms use graphs in semantically, or just psychologically, significant ways?

12.2 Conceptual Graphs

The presence of graph-theoretic concepts in the logic of conceptual graphs can be summarized as follows:

- CGs represnet formulas/ propositions. A collection of CGs represnets a theory
- since a model can be viewed as a collection of grounded formulas, one can represent a model as a collection of CGs, i.e., a theory
- The inference rules can be rxpressed in graph-theoretic terms, like projection, restriction, and matching
- But, since the theory of FOCGs corresponds to first-order logic, its semantics is standard and graphs can be eliminated without any loss in the expressive power.
- Because of the above correspondence and the undecidability of satisfaction, there is no algorithm for deriving a model for a collection of GCs.
- Models of a collection of CGs can be infinite
- Graph properties of background knowledge, like proximity or connectedness, play almost no semantic role

Notice the conflict between the need for expressive power in order to handle natural language expressions and the difficulty in inferencing and constructing a model. Sowa’s work addresses only the first problem.

The trade-offs between the expressive poer and computability are discussed by Levesque and Branchmann, and their insights apply to graph-based formalisms, too.

12.3 HIGRAPHS

12.4 Graph Guide Inference in The Three-level Semantics

main ideas:

- Reasoning takes place in a three-level structure consisting of a referential level R(a partial order of theories representing background knowledge), an object level (describing current situation), and a metalevel (constraining types of models)
- The referential level is a collection of graphs whose nodes correspond to theories describing background knowledge, and whose links represent the partial orderings on these theories.
- An object-level theory T is augmented by theories from the referential level by extending paths from subformulas of T to corresponding theories of R. The resulting new, consistent, theories PT(T) can be then further extended to PT(PT(T)), and so on.
- Models of such extensions are then built, subject to metalevel constraints.

12.5 A Graph-based representation formalism?

- First-order logic, especially in the form of conceptual graphs, makes certain types of knowledge readable. Until we are able to communicate with computers using natural language, first- order logic is perhaps the easiest formal language to carry conversations with them.
- We have noticed some gaps in the theory of conceptual graphs:

- How to handle extensions of FOCGs?
- extracting relevant chunks from the knowledge soup to sonstruct a theory which makes deduction possible

- Lack of graph-based model theory.
- The problem is how to use conceptual graphs to respresent models of theory given as a set of CGs. Conceptual graphs would now have to be restricted in order to represent only grounded relations, functions, and terms.

Imagine a system that uses higraphs to represnet the structure of terms, and conceptual graphs for propositions ; in ference could be guided by topological properties of graphs representing knowledge, as it is in inheritance networkd with exceptions and the three-level semantics; models would be graphs, too.

## Principles of Semantic Networks

- Chapter 5 Toward the Expressive Power of Natural Language ▲
- How to express natural language with Semantic Networks

- Chapter 6 Sentences, Situations, And Propositions △
- it is useful for a representation to provide entities corresponding to individual situations, and to be able to represnet facts about a situation separately from stating that something is a situation of a particular field.

- Chapter 7 Inheritance Theory And Networks With Roles △
- We present a formalization of monotonic inheritance networks with roles.

- Chapter 8 Extensions as Possible Worlds △
- a model-theoretic, path-based semantics for inheritance.

- Chapter 9 The Tractability of Path-based Inheritance
- Chapter 10 ALL:Formalizing Access-Limited Reasoning
- Chapter 11 Terminological cycles △
- When trying to represent an expert’s knowledge about a sufficiently complex domain we have to account for the vocabulary used in this domain

- Chapter 12 Logical Dimension of some graph formalisms ▲
- three knowledge representation formalisms that directly refer to graph-theoretic properties
- conceptual graphs(Sowa)
- higrahps(Harel)
- three-level semantics(Zadrozny)

- three knowledge representation formalisms that directly refer to graph-theoretic properties
- Chapter 13 The Evolving Technology of Classification-based Knowledge Representation Systems ▲ ▲
- characterize the technology that has evolved within the KL-ONE family of knowledge representation systems.

## Toward the expressive power of natural language

The structure of a knowledge representation language depends critically on its ultimate goal. For conceptual graphs, the goal is a system of logic that can express the propositional content of sentences in natural language in as simple and direct a manner as possible …

For most sentences in ordinary language, the mapping to conceptual graphs is shorter, simpler, and more direct than the mapping to predicate calculus. For some aspects of language, especially context dependencies, predicate calculus has no way to represent them, but conceptual graphs can represent them in a principled way.

5.1 Representing Semantic Structures

Natural language => Conceptual graphs => Predicate calculus

Conceptual graphs simplify the nonformalized first stage by providing direct correspondences for the semantic features of natural languages.

The function φ, which implements the second stage, must make some complex structural transformations to generate a formula.

1 2 3 |
A lady is dancing. [LADY]<--(AGNT) <--[DANCE] (∃x)(∃y)(lady(x) ∧ dance(y) ∧ agnt (y,x)). |

1 2 3 4 |
A lady is dancing. [LADY]<--(DANCING). DANCING = (λx) [PERSON: *x] <--(AGNT)<-[DANCE]. (∃x)(∃y)(lady(x) ∧ dance(y) ∧ agnt (y,x)). |

1 2 3 4 |
<em>Nine ladies are dancing.</em> [LADY: {*}@9]<--(AGNT) <--[DANCE] (∃S)(set(S) ∧ count (S,9) ∧ (∀x∈S)(∃y) (lady(x) ∧ dance(y) ∧ agnt (y,x)). |

{*}: plural referent, which indicates some unspecified elements of type LADY, and the qualifier @9 indicates that there are 9 of them.

When φ is applied to a concept with a plural referent, it must assign two quantified variables: one variable S for the set of ladies and another variable x that ranges over the elements of S.

Conceptual graphs accommodate contextual dependencies with indexical referents marked by the symbol #.

The cat is on the mat.

[CAT: #] –> (ON) –>[MAT: #].

φ operator is undefined because the predicate calculus has nothing that corresponds to #.

If the current cat is named Yojo and the current mat has serial number #81649, each # marker can be resolved to a constant:

[CAT: Yojo]–>(on)–>[MAT:#81649]

now φ can translate this graph to a formula:

cat(Yojo) ∧ mat(#81649) ∧ on(Yojo, #81649).

The search rules for resolving # markers can be adapted from * discourse representation theory* [kamp, 1981a,b]

1 2 3 4 5 |
I [PERSON: #I] you [PERSON: #you] here [PLACE:#here] now [TIME: #now] PAST = (λx) [SITUATION: *x] → (PTIM) → [TIME] → (SUCC)→[TIME:#s-time]. |

The λ-expression defines PAST as a relation that applies to a situation x that occurs at a point in time(PTIM), which is some time that has a successor, which is the time #s-time.