Knowledge-Representation---Cognitive-Science-at-Northwestern知识表示在西北认知科学课件.ppt

《Knowledge-Representation---Cognitive-Science-at-Northwestern知识表示在西北认知科学课件.ppt》由会员分享，可在线阅读，更多相关《Knowledge-Representation---Cognitive-Science-at-Northwestern知识表示在西北认知科学课件.ppt（44页珍藏版）》请在三一办公上搜索。

1、Knowledge Representation,Praveen ParitoshCogSci 207: Fall 2019: Week 1Thu, Sep 30, 2019,Knowledge RepresentationPrave,Some Representations,Some,Elements of a Representation,Represented world: about what? Representing world: using what? Representing rules: how to map? Process that uses the representa

2、tion: conventions and systems that use the representations resulting from above. Analog versus Symbolic,Elements of a RepresentationRe,Marrs levels of description,Computational: What is the goal of the computation, why is it appropriate, and what is the logic of the strategy by which it can be carri

3、ed out? Algorithmic: How can this computational theory be implemented? In particular, what is the representation for the input and output, and what is the algorithm for the transformation? Implementation: How can the representation and algorithm be realized physically?,Marrs levels of descriptionCo,

4、Marrs levels of description 2,Computational: a lot of cognitive psychologyAlgorithmic: a lot of cognitive scienceImplementation: neuroscience,Marrs levels of description ,A closer look,A closer look,Overview,How knowledge representation worksBasics of logic (connectives, model theory, meaning)Basics

5、 of knowledge representationWhy use logic instead of natural language?QuantifiersOrganizing large knowledge basesOntologyMicrotheoriesResource: OpenCyc tutorial materials,OverviewHow knowledge represen,How Knowledge Representation Works,Intelligence requires knowledgeComputational models of intellig

6、ence require models of knowledgeUse formalisms to write down knowledgeExpressive enough to capture human knowledgePrecise enough to be understood by machinesSeparate knowledge from computational mechanisms that process itImportant part of cognitive model is what the organism knows,How Knowledge Repr

7、esentation W,How knowledge representations are used in cognitive models,Contents of KB is part of cognitive modelSome models hypothesize multiple knowledge bases.,KnowledgeBase,InferenceMechanism(s),LearningMechanism(s),Examples,Statements,Questions,requests,Answers,analyses,How knowledge representa

8、tions,Whats in the knowledge base?,Facts about the specifics of the worldNorthwestern is a private universityThe first thing I did at the party was talk to John.Rules (aka axioms) that describe ways to infer new facts from existing factsAll triangles have three sidesAll elephants are greyFacts and r

9、ules are stated in a formal languageGenerally some form of logic (aka predicate calculus),Whats in the knowledge base?F,Propositional logic,A step towards understanding predicate calculusStatements are just atomic propositions, with no structurePropositions can be true or falseStatements can be made

10、 into larger statements via logical connectives.Examples:C = “Its cold outside” ; C is a propositionO = “Its October” ; O is a propositionIf O then C ;if its October then its cold outside,Propositional logicA step towa,Symbols for logical connectives,Negation: not, , Conjunction: and, Disjunction: o

11、r, Implication: implies, , Biconditional: iff, -Universal quantifier: forall, Existential quantifier: exists, ,Symbols for logical connective,Semantics of connectives,For propositional logic, can define in terms of truth tables,Semantics of connectives For p,Implication and biconditional,AB AB,AB (A

12、B)(BA),Implication and biconditionalA,Rules of inference,There are many rules that enable new propositions to be derived from existing propositionsModus Ponens: PQ, P, derive QdeMorgans law: (AB), derive ABSome properties of inference rulesSoundness: An inference rule is sound if it always produces

13、valid results given valid premisesCompleteness: A system of inference rules is complete if it derives everything that logically follows from the axioms.,Rules of inferenceThere are ma,Predicate calculus,Same connectivesPropositions have structure: Predicate/Function + arguments. R, 2 ; Terms. Terms

14、are not individuals, not propositionsRed(R), (Red R) ; A proposition, written in two ways(southOf UnicornCafe UniHall) ;a proposition(+ 2 2) ; Term, since the function + ranges over numbersQuantifiers enable general axioms to be written(forall ?x (iff (Triangle ?x) (and (polygon ?x) (numberOfSides ?

15、x 3),Predicate calculusSame connect,Model Theory,Meaning of a theory = set of models that satisfy it.Model = set of objects and relationshipsIf statement is true in KB, then the corresponding relationship(s) hold between the corresponding objects in the modeled worldThe objects and relationships in

16、a model can be formal constructs, or pieces of the physical world, or whateverMeaning of a predicate = set of things in the models for that theory which correspond to it.E.g., above means “above”, sort of,Model TheoryMeaning of a theor,Caution: Meaning pertains to simplest model,There is usually an

17、intended model, i.e., what one is representing.A sparse set of axioms can be satisfied by dramatically simpler worlds than those intendedExample: Classic blocks world axioms have ordered pairs of integers as a model( ) block(on A B) p(A) = p(B) & h(A) = h(B)+1(above A B) p(A) = p(B) & h(A) h(B)Moral

18、: Use dense, rich set of axioms,Caution: Meaning pertains to s,Misconceptions about meaning,“Predicates have definitions”Most dont. Their meaning is constrained by the sum total of axioms that mention them.“Logic is too discrete to capture the dynamic fluidity of how our concepts change as we learn”

19、If you think of the set of axioms that constrain the meaning of a predicate as large, then adding (and removing) elements of that set leads to changes in its models.Sometimes small changes in the set of axioms can lead to large changes in the set of models. This is the logical version of a discontin

20、uity.,Misconceptions about meaning“P,Representations as Sculptures,How does one make a statue of an elephant?Start with a marble block. Carve away everything that does not look like an elephant.How does one represent a concept?Start with a vocabulary of predicates and other axioms. Add axioms involv

21、ing the new predicate until it fits your intended model well.Knowledge representation is an evolutionary processIt isnt quick, but incremental additions lead to incremental progressAll representations are by their nature imperfect,Representations as SculpturesH,Introduction to Cycs KR system,These m

22、aterials are based on tutorial materials developed by Cycorp, for training knowledge entry people and ontological engineersFor this class, we have simplified them somewhat.In examinations, you will only be responsible for the simplified versions,Introduction to Cycs KR syste,NL vs. Logic: Expressive

23、ness,NL:Jims injury resulted from his falling.Jims falling caused his injury.Jims injury was a consequence of his falling.Jims falling occurred before his injury.,Logic: identify the common concepts, e.g. the relation: x caused yWrite rules about the common concepts, e.g. x caused y x temporally pre

24、cedes y,NL: Write the rule for every expression?,NL vs. Logic: ExpressivenessNL,NL vs. Logic: Ambiguity and Precision,x is running-InMotion x is changing locationx is running-DeviceOperating x is operatingx is running-AsCandidate x is a candidate,x is at the bank.river bank?financial institution?,NL

25、:Ambiguous,Logic: Precise,x is running.changing location?operating?a candidate for office?,Reasoning: Figuring out what must be true, given what is known. Requires precision of meaning.,NL vs. Logic: Ambiguity and P,NL vs. Logic:Calculus of Meaning,Logic: Well-understood operators enable reasoning:L

26、ogical constants: not, and, or, all, some,Not (All men are taller than all women).All men are taller than 12”.Some women are taller than 12”.,Not (All A are F than all B).All A are F than x.Some B are F than x.,NL vs. Logic:Calculus of Meani,Syntax: Terms (aka Constants),A sampling of some constants

27、:Dog, SnowSkiing, PhysicalAttributeBillClinton,Rover, DisneyLand-TouristAttractionlikesAsFriend, bordersOn, objectHasColor, and, not, implies, forAllRedColor, Soil-Sandy,Terms denote specific individuals or collections (relations, people, computer programs, types of cars . . . )Each Terms is a chara

28、cter string prefixed by,These denote collectionsThese denote individuals : Partially Tangible IndividualsRelationsAttribute Values,Syntax: Terms (aka Constants)A,Syntax: Propositions,Propositions: a relation applied to some arguments, enclosed in parenthesesAlso called formulas, sentencesExamples:(i

29、sa GeorgeWBush Person)(likesAsFriend GeorgeWBush AlGore)(BirthFn JacquelineKennedyOnassis),Syntax: PropositionsPropositio,Syntax: Non-Atomic Terms,New terms can be made by applying functions to other things In the Cyc system, functions typically end in “Fn”Examples of functions:BirthFn, GovernmentFn

30、, BorderBetweenFnExamples of Non-Atomic Terms:(GovernmentFn France)(BorderBetweenFn France Switzerland)(BirthFn JacquelineKennedyOnassis)Non-atomic Terms can be used in statements like any other term(residenceOfOrganization (GovernmentFn France) CityOfParisFrance),Syntax: Non-Atomic TermsNew t,Why U

31、se NATs?,UniformityAll kinds of fruits, nuts, etc., are represented in the same, compositional way: (FruitFn PLANT) *Inferential EfficiencyForward rules can automatically conclude many useful assertions about NATs as soon as they are created, based on the function and arguments used to create the NA

32、T.what kind of thing that NAT representshow to refer to the NAT in English,Why Use NATs?Uniformity,Well-formedness: Arity,Arity constraints are represented in CycL with the predicate arity:(arity performedBy 2)Represents the fact that performedBy takes two arguments, e.g.: (performedBy Assassination

33、OfPresidentLincoln JohnWilkesBooth)(arity BirthFn 1)Represents the fact that BirthFn takes one arguments, e.g.:(BirthFn JacquelineKennedyOnassis),Well-formedness: ArityArity co,Well-Formedness: Argument Type,Argument type constraints are represented in CycL with the following 2 predicates:1 argIsa (

34、argIsa performedBy 1 Action) means that the first argument of performedBy must be an individual Action, such as the assassination of Lincoln in: (performedBy AssassinationOfPresidentLincoln JohnWilkesBooth)2 argGenl(argGenl penaltyForInfraction 2 Event) means that the second argument of penaltyForIn

35、fraction must be a type of Event, such as the collection of illegal equipment use events in:(penaltyForInfraction SportsEvent IllegalEquipmentUse Disqualification),Well-Formedness: Argument Type,Why constraints are important,They guide reasoning(performedBy PaintingTheHouse Brick2)(performedBy Marth

36、aStewart CookingAPie)They constrain learning,Why constraints are importantT,Compound propositions,Connectives from propositional logic can be used to make more complex statements,(and (performedBy GettysburgAddress Lincoln)(objectHasColor Rover TanColor)(or (objectHasColor Rover TanColor)(objectHasC

37、olor Rover BlackColor)(implies (mainColorOfObject Rover TanColor)(not (mainColorOfObject Rover RedColor) (not (performedBy GettysburgAddress BillClinton),Compound propositionsConnectiv,Variables and Quantifiers,General statements can be made by using variables and quantifiersVariables in logic are l

38、ike variables in algebra Sentences involving concepts like “everybody,” “something,” and “nothing” require variables and quantifiers:Everybody loves somebody.Nobody likes spinach.Some people like spinach and some people like broccoli, but no one likes them both.,Variables and QuantifiersGener,Quanti

39、fiers,Adding variables and quantifiers, we can represent more general knowledge.Two main quantifiers:1. Universal Quantifer - forAllUsed to represent very general facts, like:All dogs are mammalsEveryone loves dogs2. Existential Quantifier - thereExistsUsed to assert that something exists, to state

40、facts like: Someone is bored Some people like dogs,QuantifiersAdding variables an,Quantifiers,Universal Quantifier(forAll ?THING (isa ?THING Thing)Existential Quantifier:(thereExists ?JOE(isa ?JOE Poodle)Others defined in CycL:(thereExistsExactly 12 ?ZOS (isa ?ZOS ZodiacSign)(thereExistsAtLeast 9 ?P

41、LNT (isa ?PLNT Planet),Everything is a thing.,Something is a poodle.,There are exactly 12 zodiac signs,There are at least 9 planets,QuantifiersUniversal Quantifie,Implicit Universal Quantification,All variables occurring “free” in a formula are understood by Cyc to be implicitly universally quantifi

42、ed. So, to CYC, the following two formulas represent the same fact:(forAll ?X(implies (isa ?X Dog)(isa ?X Animal)(implies(isa ?X Dog)(isa ?X Animal),Implicit Universal Quantificat,Pop Quiz #1,What does this formula mean?(thereExists ?PLANET (and (isa ?PLANET Planet) (orbits ?PLANET Sun),Pop Quiz #1W

43、hat does this form,Pop Quiz #1,What does this formula mean?(thereExists ?PLANET (and (isa ?PLANET Planet) (orbits ?PLANET Sun),“There is at least one planet orbiting the Sun.”,Pop Quiz #1What does this form,Pop Quiz #2,What does this formula mean?(forAll ?PERSON1(implies (isa ?PERSON1 Person) (there

44、Exists ?PERSON2 (and (isa ?PERSON2 Person) (loves ?PERSON1 ?PERSON2),Pop Quiz #2What does this form,Pop Quiz #2,What does this formula mean?(forAll ?PERSON1(implies (isa ?PERSON1 Person) (thereExists ?PERSON2 (and (isa ?PERSON2 Person) (loves ?PERSON1 ?PERSON2),“Everybody loves somebody.”,Pop Quiz #

45、2What does this form,Pop Quiz #3,How about this one?(implies (isa ?PERSON1 Person) (thereExists ?PERSON2 (and (isa ?PERSON2 Person) (loves ?PERSON2 ?PERSON1),Pop Quiz #3How about this one?,Pop Quiz #3,How about this one?(implies (isa ?PERSON1 Person) (thereExists ?PERSON2 (and (isa ?PERSON2 Person)

46、(loves ?PERSON2 ?PERSON1),“Everyone is loved by someone.”,Pop Quiz #3How about this one?,Pop Quiz #4,And this?(implies(isa ?PRSN Person)(loves ?PRSN ?PRSN),Pop Quiz #4,Pop Quiz #4,And this?(implies(isa ?PRSN Person)(loves ?PRSN ?PRSN),“Everyone loves his (or her) self.”,Pop Quiz #4“Everyone loves his,