IA: Computational Logic . Inductive Inference Achim Blumensath blumens@fi.muni.cz Faculty of Informatics, Masaryk University, Brno Basic Concepts Induction learning general facts from examples: Induction is the process of forming of a hypothesis (about a target concept/function) based on observed data. Example What is the next number? , , Induction learning general facts from examples: Induction is the process of forming of a hypothesis (about a target concept/function) based on observed data. Example What is the next number? , , , Induction learning general facts from examples: Induction is the process of forming of a hypothesis (about a target concept/function) based on observed data. Example What is the next number? , , , , Induction learning general facts from examples: Induction is the process of forming of a hypothesis (about a target concept/function) based on observed data. Example What is the next number? , , , , , Induction learning general facts from examples: Induction is the process of forming of a hypothesis (about a target concept/function) based on observed data. Example What is the next number? , , , , , , Induction learning general facts from examples: Induction is the process of forming of a hypothesis (about a target concept/function) based on observed data. Example What is the next number? , , , , , , ,... an = an− + an− Induction learning general facts from examples: Induction is the process of forming of a hypothesis (about a target concept/function) based on observed data. Example What is the next number? , , , , , , ,... an = an− + an− , , Induction learning general facts from examples: Induction is the process of forming of a hypothesis (about a target concept/function) based on observed data. Example What is the next number? , , , , , , ,... an = an− + an− , , , Induction learning general facts from examples: Induction is the process of forming of a hypothesis (about a target concept/function) based on observed data. Example What is the next number? , , , , , , ,... an = an− + an− , , , , Induction learning general facts from examples: Induction is the process of forming of a hypothesis (about a target concept/function) based on observed data. Example What is the next number? , , , , , , ,... an = an− + an− , , , , , Induction learning general facts from examples: Induction is the process of forming of a hypothesis (about a target concept/function) based on observed data. Example What is the next number? , , , , , , ,... an = an− + an− , , , , , ,... an =  or an = n(n − )(n − )(n − )(n − )(n − )? Fundamental Problem From a strictly logical point of view, induction is not possible: there are always several possible explanations for the observed phenomena and there is no rational basis for choosing one over the others. Hence, a hypothesis can be falsified but never verified. Consequently we need to make additional a priori assumptions (the so-called inductive bias) regarding the target concept. Inductive Learning Hypothesis A hypothesis that approximates the target concept well over a sufficiently large amount of training data will also approximate it well over unobserved examples. Occam’s Razor Use the simplest hypothesis that matches the observations. (What’s simple depends on our formalism.) Philosophy of Science Scientific Method In the th century, Francis Bacon, René Descartes, and Isaac Newton developed the scientific method based on induction. Problem of Induction David Hume was the first to point out that inductive inferences are unprovable and always subject to falsification. Falsifiability Karl Popper argued that induction does not exist. Instead science is based on conjecture and criticism. One should select hypotheses that are the easiest to falsify. Paradigm Shift Thomas Kuhn viewed science as a social process. He emphasised the role of paradigms and the way they are replaced when sufficiently many observations point to problems with the current paradigm. Machine Learning Induction (and learning in general) works best if it is interactive: ▸ form a hypothesis based on the current data ▸ test the hypothesis on new data ▸ repeat The question therefore is not whether the hypothesis is true, but how well it predicts observations. Most decent algorithms for inference use statistical methods and fall outside the scope of this course. Hypothesis Space Hypothesis Space Hypothesis Space Hypothesis Space Example         Example         x ∨ y Example         x ∨ y ¬x ∨ ¬z Boolean Functions Boolean functions In this lecture we will concentrate on learning boolean functions f ∶ {, }n → {, } (which can be encoded as propositional formulae) Example x x x x x x x x x x f (¯x)           √           ⨉⨉⨉           ⨉⨉⨉           √           √           ⨉⨉⨉           √ Conjunctive Hypotheses Setting Learning a boolean function f ∶ {, }n → {, } using as hypotheses conjunctions η ∶= xi ∧ ⋅⋅⋅ ∧ ¬xk of literals. General-to-specific ordering η is more specific than ζ if η ⊧ ζ. Idea Find the most specific hypothesis. Conjunctive Hypotheses Setting Learning a boolean function f ∶ {, }n → {, } using as hypotheses conjunctions η ∶= xi ∧ ⋅⋅⋅ ∧ ¬xk of literals. General-to-specific ordering η is more specific than ζ if η ⊧ ζ. Idea Find the most specific hypothesis. Conjunctive Hypotheses Setting Learning a boolean function f ∶ {, }n → {, } using as hypotheses conjunctions η ∶= xi ∧ ⋅⋅⋅ ∧ ¬xk of literals. General-to-specific ordering η is more specific than ζ if η ⊧ ζ. Idea Find the most specific hypothesis. √ Conjunctive Hypotheses Setting Learning a boolean function f ∶ {, }n → {, } using as hypotheses conjunctions η ∶= xi ∧ ⋅⋅⋅ ∧ ¬xk of literals. General-to-specific ordering η is more specific than ζ if η ⊧ ζ. Idea Find the most specific hypothesis. √ √ Conjunctive Hypotheses Setting Learning a boolean function f ∶ {, }n → {, } using as hypotheses conjunctions η ∶= xi ∧ ⋅⋅⋅ ∧ ¬xk of literals. General-to-specific ordering η is more specific than ζ if η ⊧ ζ. Idea Find the most specific hypothesis. √ √ √ Conjunctive Hypotheses Setting Learning a boolean function f ∶ {, }n → {, } using as hypotheses conjunctions η ∶= xi ∧ ⋅⋅⋅ ∧ ¬xk of literals. General-to-specific ordering η is more specific than ζ if η ⊧ ζ. Idea Find the most specific hypothesis. √ √ √ ⨉⨉⨉ ⨉⨉⨉ ⨉⨉⨉ Conjunctive Hypotheses Setting Learning a boolean function f ∶ {, }n → {, } using as hypotheses conjunctions η ∶= xi ∧ ⋅⋅⋅ ∧ ¬xk of literals. General-to-specific ordering η is more specific than ζ if η ⊧ ζ. Idea Find the most specific hypothesis. √ √ √ ⨉⨉⨉ ⨉⨉⨉ ⨉⨉⨉ ⨉⨉⨉ Find-S algorithm ▸ Start with η ∶= ▸ Consider the next positive example ¯b ▸ If η(¯b) is true, continue. ▸ Otherwise, find the most specific ζ such that η ⊧ ζ and ζ(¯b) is true. ▸ Continue with η ∶= ζ. This algorithm computes find the least conjunction with respect to the ⊧-ordering that covers all positive examples. If any of the negative examples is also covered, the training data cannot be described by a conjunction. Example x x x x x x x x x x f (¯x)           √           ⨉⨉⨉           ⨉⨉⨉           √           √           ⨉⨉⨉           √ η ∶= Example x x x x x x x x x x f (¯x)           √           ⨉⨉⨉           ⨉⨉⨉           √           √           ⨉⨉⨉           √ η ∶= η ∶= ¬x ∧ x ∧ ¬x ∧ x ∧ x ∧ x ∧ x ∧ ¬x ∧ ¬x ∧ x Example x x x x x x x x x x f (¯x)           √           ⨉⨉⨉           ⨉⨉⨉           √           √           ⨉⨉⨉           √ η ∶= η ∶= ¬x ∧ x ∧ ¬x ∧ x ∧ x ∧ x ∧ x ∧ ¬x ∧ ¬x ∧ x η ∶= ¬x ∧ ¬x ∧ x ∧ ¬x Example x x x x x x x x x x f (¯x)           √           ⨉⨉⨉           ⨉⨉⨉           √           √           ⨉⨉⨉           √ η ∶= η ∶= ¬x ∧ x ∧ ¬x ∧ x ∧ x ∧ x ∧ x ∧ ¬x ∧ ¬x ∧ x η ∶= ¬x ∧ ¬x ∧ x ∧ ¬x η ∶= ¬x ∧ ¬x ∧ x ∧ ¬x Example x x x x x x x x x x f (¯x)           √           ⨉⨉⨉           ⨉⨉⨉           √           √           ⨉⨉⨉           √ η ∶= η ∶= ¬x ∧ x ∧ ¬x ∧ x ∧ x ∧ x ∧ x ∧ ¬x ∧ ¬x ∧ x η ∶= ¬x ∧ ¬x ∧ x ∧ ¬x η ∶= ¬x ∧ ¬x ∧ x ∧ ¬x η ∶= ¬x ∧ ¬x ∧ x Hypothesis space Goal Compute all hypotheses consistent with the data. Let D ⊆ {, }n × {, } be the observed data and H the set of all hypotheses consistent with every datum in D. We compute the sets H+ and H− of maximal/minimal elements of H (with respect to the general-to-specific order ⊧). Candidate-Elimination Algorithm ▸ Start with H+ ∶= {⊺} and H− ∶= { }. ▸ For each positive d ∈ D: ▸ Delete from H+ every hypothesis η with η(d) = . ▸ Replace every η ∈ H− with η(d) =  by the set of all minimal ζ such that η ⊧ ζ , ζ(d) =  , and ζ ⊧ η′ , for some η′ ∈ H+ . ▸ Remove from H− all elements that are not minimal. ▸ For each negative d ∈ D: proceed analogously with H+ and H− interchanged. Example x x x f (¯x)    √    ⨉⨉⨉    √    ⨉⨉⨉         Example x x x f (¯x)    √    ⨉⨉⨉    √    ⨉⨉⨉         Step . H− = { } H+ = {⊺} Example x x x f (¯x)    √    ⨉⨉⨉    √    ⨉⨉⨉         Step . H− = { } H+ = {⊺} Step . H− = {x ∧ x ∧ ¬x} H+ = {⊺} Example x x x f (¯x)    √    ⨉⨉⨉    √    ⨉⨉⨉         Step . H− = { } H+ = {⊺} Step . H− = {x ∧ x ∧ ¬x} H+ = {⊺} Step . H− = {x ∧ x ∧ ¬x} H+ = {x, x, ¬x} Example x x x f (¯x)    √    ⨉⨉⨉    √    ⨉⨉⨉         Step . H− = { } H+ = {⊺} Step . H− = {x ∧ x ∧ ¬x} H+ = {⊺} Step . H− = {x ∧ x ∧ ¬x} H+ = {x, x, ¬x} Step . H− = {x ∧ ¬x} H+ = {x, ¬x} Example x x x f (¯x)    √    ⨉⨉⨉    √    ⨉⨉⨉         Step . H− = { } H+ = {⊺} Step . H− = {x ∧ x ∧ ¬x} H+ = {⊺} Step . H− = {x ∧ x ∧ ¬x} H+ = {x, x, ¬x} Step . H− = {x ∧ ¬x} H+ = {x, ¬x} Step . H− = {x ∧ ¬x} H+ = {¬x} Decision Trees Decision Trees Organise the function to be learned as a tree. x x x x x x x f (¯x)        √        ⨉⨉⨉        √        √        ⨉⨉⨉        √        √                                         ⨉⨉⨉ √ ⨉⨉⨉ √ √ √ √ Decision Trees Organise the function to be learned as a tree. x x x x x x x f (¯x)        √        ⨉⨉⨉        √        √        ⨉⨉⨉        √        √       ⨉⨉⨉ √ ⨉⨉⨉ √ The order of the variables xi matters. Which one do we choose? Ordered Binary Decision Diagrams (OBDDs) ▸ data structure to compactly represent a boolean function ▸ the arguments are ordered x, . . . , xn ▸ the graph is reduced: merge isomorphic subgraphs and eliminate unneeded vertices (x ∧ x) ∨ (x ∧ x) ∨ ¬(x ∨ x ∨ x) x x x x            