Prolog, Datalog, Learning Flashcards

Question

What are the a priori constraints in ILP?

Answer 1

Prior necessity (learning is needed) and prior satisfiability (background knowledge must be consistent; no negative example should already follow from the background knowledge ).

Answer 2

*Posterior sufficiency* (completeness): All positive examples must be entailed by the learned theory and background knowledge (∀e ∈ E⁺ : B ∧ T ⊨ e). *Posterior satisfiability* (consistency): No negative examples should be entailed by the learned theory

Answer 3

Learning is framed as searching through the space of possible hypotheses (logic programs) to find one that fits the examples.

Answer 4

The set of all possible logic programs (rules) that can be formed using the available predicates and constants.

Answer 5

The predicate whose logical definition is being learned (e.g., father/2, ancestor/2).

Answer 6

Atoms/negated atoms

Answer 7

An atom is a positive predicate (e.g., parent(A,B)); a literal is an atom or its negation (e.g., not(parent(A,B))).

Answer 8

First Order Inductive Learner — a classical ILP algorithm that learns first-order logic rules using examples and background knowledge (Quinlan, 1990).

Answer 9

Recursive Datalog programs (Horn clauses).

Answer 10

A Separate-and-Conquer strategy combined with Top-Down Hill-Climbing.

Answer 11

Starting from the most general rule and greedily adding literals that increase rule quality (information gain).

Answer 12

Weighted Information Gain (WIG), which measures improvement in the ratio of positives to negatives covered.

Answer 13

Minimum Description Length — a principle to balance model complexity and data fit. To stop rule refinement when further specialization no longer reduces the total description length (prevents overfitting).

Answer 14

A rule that refers to itself in the body (e.g., ancestor(X,Y) :- parent(X,Z), ancestor(Z,Y)).

Answer 15

Infinite recursion or trivial recursion (ancestor(X,Y) :- ancestor(X,Y)).

Answer 16

Removing or avoiding overly complex or overly specific rules to prevent overfitting.

Answer 17

A specification of which literals or rules are allowed during search, used to restrict the hypothesis space.

Answer 18

Restrictions ensuring that variables appear only in predicates compatible with their semantic types (e.g., person vs. number).

Answer 19

Specifications indicating how arguments of predicates can be used (input '+', output '-', constant '#').

Answer 20

Rules indicating that some predicates are symmetric (e.g., married(A,B) = married(B,A)) so only one orientation is tested.

Answer 21

An approach that transforms flat data (like tables) into logical facts (Horn clauses) by introducing binary attributes for each possible literal (Lavrač & Džeroski, 1991). Makes ILP usable for databases

Answer 22

An extension of Linus that also handles multirelational structures and decomposes problems. Learns rules layer by layer

Answer 23

Dinus encodes output variable bindings of determinate literals as propositional attributes; Linus only handles true/false literals.

Answer 24

- Propositional and first-order logic - semantic networks - frames - ontologies - rule-based systems.

Answer 25

It provides transparency, interpretability, and explainable reasoning based on explicit knowledge. It struggles with uncertainty, ambiguity, and learning from raw data.

Answer 26

It learns symbolic rules (knowledge) from examples, combining inductive generalization with logical inference.

Answer 27

First Order Inductive Learner. Goal is to learn first-order logic rules (Horn clauses) from examples and background knowledge.

Answer 28

Recursive Datalog programs — i.e., sets of Horn clauses that can include recursion.

Answer 29

It uses a Separate-and-Conquer outer loop and a Top-Down Hill-Climbing inner loop.

Answer 30

A rule learning strategy that learns one consistent rule at a time, removes covered positives, and repeats until all positive examples are covered.

Answer 31

Remove all examples covered by the current rule from the training set.

Answer 32

Continue learning new rules for the remaining positive examples until all are covered.

Answer 33

Top-Down Hill-Climbing search.

Answer 34

Start with the most general rule and iteratively add literals that improve the rule according to a heuristic (information gain).

Answer 35

The most general rule: target(...) :- true.

Answer 36

A predicate (atom) or its negation that can appear in the body of a rule as a condition.

Answer 37

A possible predicate with variable bindings that FOIL considers adding to the rule body.

Answer 38

By combining predicate symbols, existing variables, possibly new variables, and constants that appear in examples.

Answer 39

Because the number of possible variable and predicate combinations grows combinatorially — each must be evaluated for coverage.

Answer 40

- language bias (a declarative specification defining which literals or rule structures are valid, reducing the search space) - type constraints (restrictions that ensure variables appear only in predicates with compatible argument types) - templates (schemata) that restrict which combinations are allowed

Answer 41

Weighted Information Gain (WIG) Measures how much the addition of a literal improves the purity of a rule — i.e., increases positives and reduces negatives.

Answer 42

p₀ and n₀ are the number of positive and negative examples covered **before** adding the literal. p₁ and n₁ are the number of positive and negative examples covered **after** adding the literal.

Answer 43

It may still be added if it introduces new variables required for later conditions (useful literals without gain).

Answer 44

Minimum Description Length — it stops rule refinement when additional literals no longer reduce the total description length. It prevents Overfitting — rules that perfectly fit noise or exceptions in the training data.

Answer 45

Stopping rule refinement early when no significant improvement is achieved (e.g., by MDL or gain threshold).

Answer 46

Removing unnecessary or redundant literals from rules after learning to simplify them.

Answer 47

Literals that introduce new variables which have *at most one* possible binding for each variable assignment in the head — deterministic relations. They don’t increase the number of tuples (proofs) but allow introducing new variables efficiently.

Answer 48

succ(N,N1) — every number has exactly one successor.

Answer 49

It adds all possible determinate literals to the rule to help learning continue.

Answer 50

Typically 80% of the maximum possible gain.

Answer 51

All unnecessary literals (that don’t affect accuracy) are removed from the rule.

Answer 52

A rule whose head predicate also appears in its body, enabling recursive reasoning (e.g., ancestor/2). e.g. ancestor(X,Y) :- par

Answer 53

a clause which has at most one positive literal

Answer 54

SLD Selection: Prolog selects the *first* matching rule Linear: continues with the result of the previous step Definite clauses (Horn clauses)

Answer 55

Depth-first, left-to-right. Creates choice points when multiple clauses match. On failure, backtracks to the most recent choice point, tries the next alternative.

Answer 56

Declarative and Procedural representation.

Answer 57

Declarative: It describes facts and relationships about the world — what is true. Procedural: It describes how to do things — methods

Answer 58

Logic-based representations such as predicate logic or semantic networks.

Answer 59

Production rules (IF–THEN)

Answer 60

A rule-based representation: IF THEN

Answer 61

A graph-based declarative structure linking concepts with relationships (e.g.

Answer 62

Structured objects with slots and values describing an entity’s properties and relations.

Answer 63

Organizing domain knowledge hierarchically with defined concepts and relations (used in semantic web systems).

Answer 64

Declarative representation.

Answer 65

- Search engines (Google Knowledge Graph) - Recommendation systems - Question answering (QA) systems - Semantic Web / Linked Data - AI reasoning frameworks

Prolog, Datalog, Learning Flashcards

(89 cards)