## Basics - **Motivation**: - Available information grows exponentially (e.g., number of new publications) - Help users to filter the information - **Goal**: - Gain intelligence/knowledge from data - **Knowledge-based System**: - "A knowledge-based system (KBS) is a program that *reasons* and uses a knowledge base to solve problems" ([Wikipedia](https://en.wikipedia.org/wiki/Knowledge-based_systems)) - Two key components: - Knowledge base (model knowledge explicitly) - Inference engine (derive new knowledge, also called *reasoning system*) - Usually, based on formal logics - Refers to the *architecture* - Types of KBS: - Expert System - Semantic Web (knowledge-based internet system) - **Reasoning**: - Apply logics and formally create new knowledge/draw conclusions - **‌Inference**: - Inference are steps in *reasoning* - **Lecture content**: - Different kinds of formal logic - Syntactic basics of first-order logic - Interpreting logical expressions - Efficiently evaluating logical expressions in a database - Design a KBS using different formal logics - Semantic Web (all KBS ideas are *reborn*) - Linked Open Data (and its connection to the semantic web) - Question Answering (related to Linked Open Data) - Vision of knowledge-based systems ### History (Dreams of AI) - 400 BC: - *Wooden pigeon* - First *intelligent machine* invented - 1950: Turing Test - 1956: Dartmouth Conference - Founding of AI Labs - Investment of much money - Creation of the research field *Artificial Intelligence* - 1967: - Marvin Minsky: "Within a generation ... the problem of creating 'artificial intelligence' will substantially be solved." - 19XX: - Ronald A. Katz invented the first automatic reasoning system for call centers - 1972: Critique of Hubert Dreyfus (UC Berkeley) - Knowledge is embodied and **not** explicit - e.g., muscle memory - *Expertise* can not readily be extracted - 1974–1980: AI winter (no research) - 1980-1987: Expert Systems - Focus: - Do **not** imitate full human brain - Find intelligent algorithms (weak AI) - Well-defined problem domains - Idea: - System draws conclusions to support people - *Simulate* human expert - Leads to expert systems - Useful application areas: - Medical diagnosis - Production/machine failure diagnosis - Financial services - 1987–1993: Second AI winter --- ### Deductive Databases - Deduce new facts using rules (leading to *inference chains*) - Most systems use first-Order logic - **Knowledge derivation**: - Apply inference rules on specific data (*facts*) - Support for uncertainty (e.g, *Almost all birds can fly*) - Recursion: Inference may take several steps - Usually, based on symbolic calculation (*logic programming languages*) - *Deductive Database System*: Database system with **limited** support for reasoning - Features of databases (transactions, recovery, etc.) - Recursive views - Efficient query evaluation #### Datalog - *Question*: - Build a deductive database on top of an RDBMS? - RDBMS (SQL) - Answer to a query are the tuples satisfying WHERE-condition - SQL-92 does not support recursion - Idea: Features of SQL + recursion - Features: - Re-evaluate query on intermediate results - Subset of Prolog (logical programming language) - No predicates as arguments allowed (forbid second-order logic) - Evaluate using fix-point iteration - Efficient bottom-up evaluation - Recursive rules - Problem: Efficient evaluation - Search space is combinatorial, bad idea? - Example: Public Transport - Database contains connections of bus stations - Computation of routes are recursive (connections are transitive) #### History - Former systems did not use RDBMS - 1984: LDL - MCC Research, Austin - Query language using *Horn clauses* - Funding was quit after the 5th generation project - Hardware-supported reasoning system (data mining engine) - 1988: Coral - University of Wisconsin - ACID support - Exodus storage manager - 1995: Lola/Butterfly - University of Passau - Bottom-up and Top-down evaluation - **Conclusion**: Deductive databases were a commercial failure - **Problem**: - No big data was available - Data mining only works with big data - **Spirit of deductive databases** survives - SQL-99 standardizes *common table expression* - i.e., `WITH`-statements (allowing recursive querying) --- ### Expert Systems (D) - *Expert Systems are knowledge-based systems for a certain task* (e.g., medicine) - **Architecture**: - User-interface: Question-response-dialog - Inference Engine: Deduce answer (using knowledge base and problem data) - Explanation System: Explain answer to the user - Knowledge Base: Rules/facts - Problem Data: Facts for a specific problem ![](images/01-arch.png) - **Requirements**: - Keep and manage valuable data in knowledge base - Support another query type - Same requirements as normal database system - 1970: MYCIN - Stanford Univeristy - Medical expert system to treat infections - Containing 600 rules - Support for uncertainty - Problem: Too big, never used in practice - 1980: Dipmeter Advisor - Schlumberger Doll Research - Goal: Support oil drilling operations (find correct spot) - Containing 90 rules - System was very successful - 1992: SHINE Expert System - *Spacecraft Health Inference Engine* - Started in 1970 by NASA and JPL - Multi-purpose inference system - Detect system failures in complex machines - System still in use (real-time system) - Deep Space Network - Lockheed Martin F-35 - Galileo Space Probe --- ### Semantic Web - 2001, Tim Berners-Lee - Vision: - Semantic Web Agent (SWA) *accesses* and *understands* Web pages - SWA plans complex tasks - SWA deduces new facts - e.g., "Asthma is chronic lung disease", "Pulmonologist is doctor for lung diseases", "Go to doctor" - Semantic Web is *web of data* - Goal: - Provide web page in machine-readable form - **NOT**: Understand natural language - Common formats for integration/combination of data - Schema of a website: - *Structure* of a web site (e.g., tags) - Website is annotated with defined tags - Different schemas must be matched (schema matching) - Ontologies: - Correct name: *Ontological models* - Ontologies describes what *exists*, its relation to other things and categorization - e.g., all tags - Offer reasoning capabilities - Automatic classification - Extract additional facts - Modeled using languages (OWL, RDFS, DAML+OIL) - Ontology contains the data (in contrast to a schema) - Taxonomy - Type of an ontology - Order things into a hierarchical structure --- ### Question Answering - Application using the semantic web - Task: Answer natural-language questions - Question types: - Factoid question: Asking about facts (e.g, *how big is x?*) - Non-factoid questions: *How was x?* - Questions: - QA in RDMBS: Data is well-structured for specific domains - QA and LOD: e.g., DBpedia - QA and the Web: Unstructured data, mostly natural language (use IR methods)