DOC PREVIEW
U of I CS 498 - Knowledge Repn. & Reasoning

This preview shows page 1-2-3-4-25-26-27-51-52-53-54 out of 54 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 54 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 54 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 54 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 54 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 54 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 54 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 54 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 54 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 54 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 54 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 54 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 54 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

Knowledge Repn. & Reasoning Lec #28: Frame Systems and Description LogicsLast TimeTodayDescription Logics (DLs)Frame SystemsSlide 6Differences from DBsDescription Logics: LanguageSlide 9Slide 10AL Description Logic: LanguageSlide 12Slide 13Slide 14Slide 15Slide 16Slide 17Slide 18AL DL: FOL SemanticsDLs that Extend ALTBox: Terminological AxiomsDefinitional / NondefinitionalABox: Assertions About ElementsSlide 24Take a BreathTBox Reasoning TasksReductions to SubsumptionReductions to UnsatisfiabilitySystems vs ReasoningEliminating the TBoxABox QueriesStructural SubsumptionStructural Subsumption Algorithm for FL0Extending FL0Structural Subsumption for ALNComputing Normal Form for ALNStructural Subsumption Algorithm for ALNExampleExtending ALNPrinciples of Tableau ReasoningTableau-based Satisfiability Algorithm for ALCNSlide 42Slide 43Slide 44Slide 45Example 2Computational PropertiesRelated to DLSummary So FarApplication: Medical InformaticsSlide 51Next TimePossible ProjectsSlide 54Knowledge Repn. & ReasoningLec #28: Frame Systems and Description LogicsUIUC CS 498: Section EAProfessor: Eyal AmirFall Semester 2004(Based on slides by Lise Getoor (UMD))Last Time•Expanding expressivity of probabilistic systems: PRMsToday•Restricting expressivity of FOL: DLs•Description Logics–Language–Semantics–InferenceDescription Logics (DLs)•Originate in semantic networks (NLP), and Frame Systems (KR)•Hold information about concepts, objects, and simple relationships between them–Hierarchical information•Many DLs, differing in their expressive powerFrame SystemsPersonMan WomanConcept framesJaneObject framesFrame SystemsPersonMan WomanJaneObject frameschildageRoleschildageJill,John26Differences from DBs•Hierarchical structure (?)•Many times no closed-world assumption•Values may be missing•More expressive (?)•Semantic structure between concepts and roles•Typical reasoning tasks (satisfiability, generality/classification)Description Logics: Language•Formal language that can be analyzed•Describe frame systems with attention to the expressive power needed•Definitions are stated in a terminological part of the KB (TBox)•Assertions are made at an assertional part of the KB (Abox)Description Logics: Language .•Definitions are stated in a terminological part of the KB (TBox)•Assertions are made at an assertional part of the KB (Abox)DescriptionLanguageReasoningTBoxABoxDescription Logics: Language .•Example definition: C = AпB•Example assertion: C(John), CпD = AпBDescriptionLanguageReasoningTBoxABoxAL Description Logic: Language• AL: C,D  A | (atomic concept)T | (universal concept) | (bottom concept)A | (atomic negation)CпD | (intersection)R.C | (value restrict.)R.T | (limited existential quantific.)AL Description Logic: Language• AL: C,D  A | (atomic concept)A  Person | Female•An atomic concept corresponds to a unary predicate symbol in FOL•Extensionally, a set of world elementsAL Description Logic: Language• AL: C,D  A | (atomic concept)T | (universal concept)•Intuition: The universal concept corresponds in FOL to λx.TRUE(x), the unary predicate that holds for every objectAL Description Logic: Language• AL: C,D  A | (atomic concept)T | (universal concept) | (bottom concept)•Intuition: The bottom concept corresponds in FOL to λx.FALSE(x), the unary predicate that holds for no objectAL Description Logic: Language• AL: C,D  A | (atomic concept)T | (universal concept) | (bottom concept)A | (atomic negation)•The negation of A is the concept that is the complement of A, i.e., contains all elements that A does notFemale, PersonAL Description Logic: Language• AL: C,D  A | (atomic concept)T | (universal concept) | (bottom concept)A | (atomic negation)CпD | (intersection)•Intersection of concepts corresponds to set intersection of their elements•Person п FemaleAL Description Logic: Language• AL: C,D  A | (atomic concept)T, | (universal, bottom)A | (atomic negation)CпD | (intersection)R.C | (value restrict.)•All elements whose R is filled only by C-elementshasChild.FemaleAL Description Logic: Language• AL: C,D  A | (atomic concept)T, | (universal, bottom)A, CпDR.C | (value restrict.)R.T | (limited existential quantific.)•The concept including all elements that have role R filled by some elementhasChild.TAL DL: FOL Semantics•Interpretation I maps Δ to nonempty set ΔI and,–Every atomic concept A is mapped to AI  ΔI–TI = ΔII = Ø–(A)I = ΔI \ AI–(CпD)I = CI п DI–(R.C)I = {a  ΔI |  b. (a,b)RI  b  CI } –(R.T)I = {a  ΔI |  b. (a,b)RI}DLs that Extend ALR.C – full existential quantification•(≥n R) - number restrictionsC – negation of arbitrary concepts•CUD – union of concepts•Trigger rules – CLASSIC (configuration of systems), LOOMTBox: Terminological Axioms•C D – The left-hand side is a symbol•R S – same•C D – same •R S – same•Mother  Woman п hasChild.Person•Parent  Mother U Father•Grandmother Mother п hasChild.MotherппDefinitional / Nondefinitional•Base interpretation for atomic concepts•The TBox is definitional if every base interpretation has only one extension•Observation: If the TBox has no cycles then it is definitionalABox: Assertions About Elements•Father(Peter) C(a)•Grandmother(Mary) C(a)•hasChild(Mary,Peter) R(b,c)•hasChild(Mary,Paul) R(b,c)•hasChild(Peter,Harry) R(b,c)•C(a) – concept assertions•R(b,c) – role assertionsABox: Assertions About Elements•UNA – Unique Names Assumption•Interpretation I maps object names to elements in ΔI•Some languages allow other statements, within a fragment of FOL.•TBox,Abox equivalent to a set of axioms in FOL (with two variables, without functions)Take a Breath•So far: Language + Semantics•From here:–Reasoning Tasks–Algorithms•Later: NLP using Description LogicsTBox Reasoning Tasks•Satisfiability of C:–A model I of T such that CI is nonempty•Subsumption of C by D–For every model I of T, CI DI•Equivalence of C and D•Disjointness of C and DпReductions to Subsumption•C is unsatisfiable iff C •C,D equivalent iff C D, D C •C,D


View Full Document

U of I CS 498 - Knowledge Repn. & Reasoning

Documents in this Course
Lecture 5

Lecture 5

13 pages

LECTURE

LECTURE

39 pages

Assurance

Assurance

44 pages

LECTURE

LECTURE

36 pages

Pthreads

Pthreads

29 pages

Load more
Download Knowledge Repn. & Reasoning
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Knowledge Repn. & Reasoning and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Knowledge Repn. & Reasoning 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?