Knowledge Representation Flashcards
What are the major phases of Watson?
- Query Processing
- Answer Candidate Generation
- Evidence Retrieval & Scoring
- Evidence Ranking
Answering questions requires only keyword evidence.
False.
Keyword matching may be weak relative to other types of evidence.
To answer complex questions, it is not sufficient to simply match text in queries to text in documents. What kinds of knowledge are required?
Temporal, biographical, geographical and linguistic (e.g., different meanings of the word ‘arrival’)
Aristotle, by thinking of automation, laid the foundations for logic
True. He observed that such patterns work for all types of objects.
What does propositional logic consist of?
- Propositions (TRUE, FALSE)
- Logical operators (AND, OR, NOT, IMPLIES)
What does first order logic add to propositional logic?
- Constants (represent objects, e.g. Frodo)
- Relations (represent relations, e.g. married)
- Quantifiers (represent existential or universal states)
Prolog is a powerful logic-based programming language.
True. Prolog means Programming and Logic.
What is Datalog?
A simple version of Prolog. It adds automated reasoning to database queries.
Who performed the first automated theorem proving?
J.A. Robinson, in 1965
When did Kowalski and Colmerauer make the first attempts for programming in logic?
In the 1950s.
A predicate denotes a relation between two objects.
True.
In Logical Notation, what do Constants and Variables represent?
- Constants: some objects
- Variables: unknown objects
In Prolog, we can’t describe relations.
False.
We can denote the relation “pam is a parent of bob” in a statement parent(pam,bob)
In Prolog, we can query relations only unidirectionally.
False. We can query in both directions:
?- parent(X,liz) or
?- parent(liz,X)
In Prolog, what is a Conjunction?
When we connect two conditions (literals) with the logical operator (AND), denoted by a comma.
happy(john), sunny_day both must be true
In Prolog, different variable names have to be different objects.
False.
In Prolog, how do we define a new relation?
We assign a new name to a conjunctive definition.
Formally, a rule is a logical implication A ^ B → C. How is it written in Prolog?
In Prolog, implication is written reversed using ‘:-’ instead of ‘←’, meaning C :- A, B.
C is the head of the rule (conclusion), while A, B is the body
What does father(X,Y) :- parent(X,Y), male(X) mean in Prolog?
X is the father of Y, if X is a parent of Y and X is male.
Is this valid syntax in Prolog?
greatgrandfather(X,Y) :- father(X,Z), grandparent(Z,Y)
Yes. It is the syntax for defining multiple relations in one statement.
It is not possible to assign constants to variables in Prolog.
False. The operation is called substitution and assigns a constant to a variable.
literal L = {parent(X,Y)}
substitution θ = {X/tom, Y/bob}
What is Forward Chaining?
A logical reasoning method.
Process:
- System examines which rules are applicable to the facts
- when matching rule is found, new fact is generated & added to the fact collection
Process repeats until no new facts can be derived (“fix point”)
What is the Elementary Production Principle?
A fundamental concept of Forward Chaining.
What are the three main components of the Elementary Production Principle?
- Rule H :- B1, …, Bn (logical statement)
- Set of known facts F1, …, Fn (knowledge base)
- Substitution mapping θ the body literals to the known facts
Rule: parent(X, Y) :- father(X, Y).
Facts: father(john, mary)
What is the Herbrand base?
A complete dictionary of all possible facts that can be stated in a given logical language.
It is built with predicates (like “parent_of”), constants (like specific names) and functions (create new terms by building all possible true/false statements e.g., parent(john, mary))
What is backwards chaining?
Reasoning strategy that starts with desired conclusion and works backward to find supporting facts.
What is the purpose of ontologies?
To encode the knowledge about a domain, form a common vocabulary and describe the semantics of its terms.
“An ontology is an explicit specification of a conceptualization”
What are ontologies in CS?
A formalized description of a domain, a shared vocabulary or a logical theory
What is a Semantic Network?
Multiple statements about the same entities.
What does this RDF schema establish?
:Country a rdfs:Class .
:City a rdfs:Class .
:locatedIn a rdfs:Property .
:capitalOf rdfs:subPropertyOf :locatedIn .
:capitalOf rdfs:domain :City .
:capitalOf rdfs:range :Country .
:Madrid :capitalOf :Spain .
Definition of Terminology (T-Box)
* If x is the capital of y, then x must be a City and y must be a Country
* Being a capital of a country implies being located in that country (through the subproperty relationship)
* Only cities can be capitals (domain restriction)
* Cities can only be capitals of countries (range restriction)
Assertion (A-Box)
* Madrid is the capital of Spain.
What are the elements of an RDF schema?
- CLASS (e.g., :Country, :City)
- PROPERTY (e.g., capitalOf)
- DOMAIN (subject) and RANGE (object) constraints on property
- Domain: :City (subject must be City)
- Range: :Country (object must be Country)
RDF Schemas allow for deductive reasoning.
True.
Given facts and rules, we can derive new facts. The corresponding tools are called reasoners.
What is the opposite of deduction?
Induction, meaning deriving models from facts, e.g., data mining, machine learning
What is OWL?
The Web Ontology Language, a syntactic extension of RDFS.
How was OWL created and by whom?
The Web consortium W3C created OWL by fusing DAML (result of a European-wide project) and OIL (US-American development).
What kinds of strategies for Knowledge Base Construction are there?
- Domain-Specific (Experts)
- Manual (Cyc)
- Collaborative (Wikidata)
- Automated (Watson)
What was the first successful knowledge-intensive system?
DENDRAL project (Buchanan et al. 1969).
It was aiming to infer molecular structure from formula of the molecule and the mass spectrum.
In which project did Feigenbaum discover the Knowledge Acquisition Bottleneck?
MYCIN for diagnosing blood infections and to antibiotics recommendations with adjusted dosage.
What was R1/XCON?
An expert system for configuring computers at DEC, saved $40 Mio a year (McDermott, 1982)
In 1984, the founder of Cyc (Douglas Lenat) estimated that 350 person years and 250,000 rules should do the job of collecting the essence of the world’s knowledge.
True.
What is NELL?
NELL (Never-Ending Language Learning) is a computer system that continuously learns to read and understand web content.
Which layers did Tim Berners-Lee’s vision include on top of the WWW (TCP-IP-DataLink)?
- XML
- RDF
- Ontology vocabulary
- Logic
- Proof
- Digital Signature
- Trust
Which technologies do the four major phases of Watson use?
- NLP
- Information Retrieval
- Knowledge & Reasoning
- ML
What are the components of the Elementary Production Princinple (EPP)?
- Rule: A logical statement of the form H :- B1, …, Bn (Head:Body)
- Known facts: A set of facts F1, …, Fn that exist in the knowledge base
- Substitution: A mapping θ, unifies body literals with known facts
- Rule: parent(X, Y) :- father(X, Y).
- Facts: father(john, mary).
Applying EPP:
1. The substitution θ = {X/john, Y/mary} matches the body of the rule to the fact
2. Applying θ to the head of the rule: parent(X, Y) θ = parent(john, mary).
3. We derive the new fact: parent(john, mary)
How does Backwards Chaining work?
- starts with goal (or hypothesis)
- works backward through rules to find facts that support goal (using DFS)
- continue until all facts are proven true or the search fails
What is the main difference in the automated construction of
knowledge bases in DBPedia and NELL?
- DBpedia focuses on transforming semi-structured Wikipedia data into a structured knowledge base
- NELL aims to learn how to read and extract knowledge from the broader web continuously
Why is Manual KB Construction as in Cyc so difficult?
- vast scale of knowledge
- maintaining consistency
- complexities of knowledge representation
- need for continuous curation
Why is logic not enough for knowledge representation?
It lacks expressiveness for uncertainty, context and relationships.
What is the vision behind the Semantic Web as opposed to the WWW?
- traditional web is primarily designed for human consumption and relies on keyword matching and hyperlinks for navigation
- Semantic Web aims to create a web experience where machines can process information in ways that more closely mimic human comprehension
