Knowledge Representation and Reasoning PDF

Knowledge Representation and Reasoning A Brief History of KR Rafael Peñaloza Milano, 2024-2025 Università di Milano-Bicocca... in the beginning The (pre-)history of humanity is a history of knowledge representation...

Knowledge Representation and Reasoning A Brief History of KR Rafael Peñaloza Milano, 2024-2025 Università di Milano-Bicocca... in the beginning The (pre-)history of humanity is a history of knowledge representation We have always needed to transmit what we know myths constructions symbols stories ideas discoveries risks Grow and improve on previous experiences (by others) KRR 2024-2025 1 Tradition Oral and written tradition aims to preserve and propagate knowledge A huge vault of knowledge from where to pick (when needed) KRR 2024-2025 2 The test of time... but meanings get lost (or changed, by chance or on purpose) and we end up unable to update as things evolve KRR 2024-2025 3... and the test of meaning also, language is ambiguous how are we supposed to interpret it? We want to manage knowledge with some guarantees Want to be sure that we are using it as originally intended Only trained interpreters (full of allegories, metaphors, etc.) KRR 2024-2025 4 Fast Forward to the Greeks Aristotle started studying ways to make valid inferences Aristotle’s syllogisms can handle knowledge about classes Four types of sentences: A: Every X is a Y every human is mortal E: Some X are Y some humans are vegetarian I: No X is a Y no human is a god O: Some X are not Y some humans are not athletes KRR 2024-2025 5 Sentence Algebra Syllogisms are derivation rules (sentence algebra) used to extract consequences from sentences BARBARA CELARENT DARII FERIO bArbArA fErIO A every X is a Y E some X are Y A every Y is a Z I no Y is a Z A every X is a Z O some X are not Z KRR 2024-2025 6 Important Insight Derivation rules are sound “true” premises derive “true” conclusions This is the main goal of valid inference calculi They are also complete whatever follows can be derived (*) KRR 2024-2025 7 Very limited Aristotle’s syllogism calculus has important limitations: Only two classes at a time No disjunctions No complex properties No relationships between objects KRR 2024-2025 8 Long Gap For a long time, logic was the study of (variants of) syllogisms Mainly used to discuss about arguments Slowly used (implicitly) for philosophy / science again: valid inferences KRR 2024-2025 9 More recently 2000 years later, Boole (and others) study an algebra of truth values Functional manipulation of propositions (sentences) which may be “true” or “false” The results is propositional logic a simple language describing general properties Later extended to predicate logic (quantification, functions and relations) first-order, higher-order,... KRR 2024-2025 10 Drawbacks of Classical Languages Propositional logic is too inexpressive Predicate logic is too complex no sound and complete (finite) derivation system Since then, trying to find the right balance between expressivity and complexity (practicality) KRR 2024-2025 11 The Era of AI Advances in computing and automated calculations gave birth to the “AI dream” One of the first approaches: intelligent agents / intelligent systems To be intelligent, agents need to “understand” what is going on around them usually inferring implicit information and actions KRR 2024-2025 12 KR for AI To obtain such an artificial agent, we need: a machine readable language for representing knowledge a formal finite inference mechanism and an interrogation (query) language to interface with the agent KRR 2024-2025 13 First Machine-Tailored KR Formalisms Semantic Networks Graphs with connecting properties hasColor isA green frog amphibian Has no formal semantics what does it mean that a frog has green color? Every implementation interprets in its own way KRR 2024-2025 14 First Machine-Tailored KR Formalisms (II) Frames Blocks with open “windows” to fill in properties All animals have a colour, a digestive system,... specific animals have different instantiations of these properties Still, no formal semantics KRR 2024-2025 15 Enter Logic-based KR Logic-based KR: the development of languages with clear syntax and formal semantics for representing knowledge and reasoning automatically Insight: Different properties for different applications KRR 2024-2025 16 Early Approaches Propositional logic proved to be very useful in many cases For more advanced settings, predicate logic was first proposed The issue is undecidability of reasoning: not so much of a guarantee KRR 2024-2025 17 The rise of DLs Description logics are a family of KR languages fragments of first-order (predicate) logic studied for the trade-off between expressivity and computational properties There are many DLs mainly well-structured and easy to understand KRR 2024-2025 18 The Semantic Web What if machines could navigate and understand the web as we do? Problem is: represent what the page is about (this before big leaps in NLU) The SW bottleneck: machine-readable annotations DLs are the formalism underlying the standard ontology language for the SW KRR 2024-2025 19 Knowledge Graphs Started with Google announcing its “Knowledge Graph” (May 16, 2012) Companies scrambled to compete; researchers to formalise What is a knowledge graph? whatever fits your application best (*) KRR 2024-2025 20 KRR is a fruitful and successful field The Curse of Reality Reality is not as logical as we want it to be To deal with real knowledge we must handle: measures time uncertainty vagueness regulations contradictions updates... KRR 2024-2025 21 Practical use Specific applications will need ad-hoc solutions But a starting point is necessary KRR 2024-2025 22 [email protected]