Knowledge Representation and Reasoning

IBMs Watson was a AI-based computer program which could compete with the best humans in the game of jeopardy

The architecture was based on four domains:

• Natural language processing –> structured representation of the question

• Information retrieval –> retrieve text that coud potentially be relevant for finding an answer

• Knowledge & reasoning –> compute a score for each candidate

• Machine Learning –> learn to assign weights to different candidates

Aristotle’s syllogisms

Propositional Logic –> logical connectives

First Order Logic –> quantifiers

Computer programs like Prolog and Datalog –> based on the foundations of logic

Prolog is a programming language which is based on the rules of logic

Therefore it contains predicates, variables and constants as well as logical connectives, subsitutions and some reasoning rules

The principle derives new facts from given rules, facts and subsitutions until no further knowledge can be derived (fix point)

It is used in Datalog

Since forward chaining finds all possible facts which can be derived from given knowledge, backward chaining only focusses on one statement, which we want to prove/disprove

Backward chaining uses the resolution principle –> assume the opposite of a statement and try to prove it, until it leads to a contradiction

Backward chaining is used in Prolog

From given knowledge other knowledge can be derived by some advanced reasoning, e.g. “Madrid is the capital of Spain”

–> Madrid is a city

–> Spain is a country

–> Madrid is not the capital of France

–> Barcelona is not the capital of Spain

Semantics can be portrayed with the use of ontologies

An ontology is an explicit specification of a concept

Philosophical: study of being

Computer Science: a logical theory, vocabulary, formalized description of a domain

Ontologies can be represented with semantic networks

Deduction –> with given facts and rules, we can derive new facts

Induction –> deriving models from facts

Domain specific Knowledge base:

Expert Systems –> formalizing knowledge from experts and use automated reasoning

Manual Knowledge base creation:

Cyc –> try to collect all knowledge

Collaborative knowledge base:

Wikidata –> everybody can share their knowledge

Automated knowledge base:

DBPedia –> extract knowledge from Wikipedia and Google and formalize it

NELL –> extract knowledge from a ontology of a given text corpus

a proposed development of the World Wide Web in which data in web pages is structured and tagged in such a way that it can be read directly by computers.

it worked with 7 semantic layers

Many datasets are available and connected to each other

It is limited, e.g. it cannot portray quantifiers and negations

OWL (Web Ontology Language) solves many of the problems

That it is often harder to capture expert knowledge than automated reasoning

Formulating knowledge in logic was always a big field in research, one of its achievements was Prolog (uses backward chaining). Datalog (uses forward chaining) is a simple version of Prolog.

“The problem of knowledge acquisition is the critical bottleneck in artificial intelligence.” -Edward Feigenbaum

meaning that the automated reasoning part is often easier than capturing the expert knowldege (e.g. hard to formulate knowledge)

Estimation by Douglas Lenat in 1984:

350 person years and 250.000 rules should do the job of collecting the essence of the world’s knowledge

the present:

about 1.000 person years, and 21M axioms and rules are needed

DBPedia:

• extracts knowledge from Wikipedia using mappings and heuristics

NELL:

• reads documents on the web and stores it inferred

• input was: ontology, seed examples, text corpus

• output was: facts, text, patterns

• has a large degree of automation with occasional human feedback

Semantic Web:

consists of many datasets that are publicly abailable and they are all connected to each other and stored in categories that refer to its topics