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)
    • 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)