10 Week.docx

A Logical Formulation of Learning Learning by extension of the goal predicate Certain hypothesis predicts that a set of examples will be examples of the goal predicate Based on this prediction the goal predicate is extending to include the examples Learning by ruling out wrong hypothesis hypotheses...

A Logical Formulation of Learning Learning by extension of the goal predicate Certain hypothesis predicts that a set of examples will be examples of the goal predicate Based on this prediction the goal predicate is extending to include the examples Learning by ruling out wrong hypothesis hypotheses that are not consistent with the examples can be ruled out false negative for the hypothesis - hypothesis says it should be negative but in fact it is positive false positive for the hypothesis - if the hypothesis says it should be positive but in fact it is negative Learning by searching for the current-best-hypothesis maintain a single hypothesis, adjust it as new examples arrive in order to maintain consistency If there is a new example that is false negative – generalize by extending the hypothesis to include the false negative, If there is a new example that is false positive - specialize by decrease the hypothesis to exclude the false positive example. Generalization & specialization are logical relationships between hypotheses, i.e. if hypothesis h1, with definition C1, is a generalization of hypothesis h2 with definition C2, we have ∀ x C2(x) ⇒ C1(x) to construct a generalization of h we must find a definition C1 that is logically implied by C2. Steps of the learning process A consistent hypothesis. A false negative. The hypothesis is generalized. A false positive. The hypothesis is specialized. Least-commitment search (continuation) In order the general structure of the boundary-set to be sufficient for representing the version space without the need to explore it entirely it has to have two properties: Every consistent hypothesis (other than those in the boundary sets) is more specific than some member of the G-set, and more general than some member of the S-set Every hypothesis more specific than some member of the G-set and more general than some member of the S-set is a consistent hypothesis Knowledge in Learning Modern approach to AI is to design agents that already know something about the solution and are trying to learn some more during the process of solving problems Explanation based learning, or EBL – Explanation-based learning (EBL) extracts general rules from single examples by explaining the examples and generalizing the explanation. The goal predicate is formulated using fixed features The hypothesis is formulated logically from the background knowledge The agent does not actually learn anything factually new from the examples, it relies only on the background knowledge Relevance-based learning, or RBL Relevance-based learning (RBL) uses prior knowledge in the form of determinations to identify the relevant attributes The goal predicate accounts the relevance of a set of features The background knowledge together with the observations allows the agent to infer a new, general rule that explains the observations and it uses it to formulate the hypothesis The agent effectively uses deductive form of learning and cannot create new knowledge starting from scratch, it needs some initial knowledge Knowledge-based inductive learning, or KBI Knowledge-based inductive learning (KBIL) finds inductive hypotheses that explain sets of observations with the help of background knowledge. the background knowledge together with the new hypothesis combined explain the examples KBI is studied mainly in the field of inductive logic programming, or ILP Prior knowledge plays two key roles in reducing the complexity of learning Explanation-Based Learning A cumulative learning process which uses not only the initial background knowledge, but also its extension over the time in result of the learning process The extension of the knowledge is based on extracting general rules from individual observations Memorization: accumulate a database of input–output pairs; when the function for transforming the input into an output is required EBL create general rules that cover an entire class of cases EBL general process: Given an example, construct a proof that the goal predicate applies to the example using the available background knowledge. 2. In parallel, construct a generalized proof tree for the parametrized goal using the same inference steps as in the original proof. 3. Construct a new rule whose left-hand side consists of the leaves of the proof tree and whose right-hand side is the parametrized goal (after applying the necessary bindings from the generalized proof). 4. Drop any conditions from the left-hand side that are true regardless of the values of the parameters in the goal. Learning Using Relevance Information Inductive logic programming (ILP) techniques perform KBIL on knowledge that is expressed in first-order logic. Functional Dependencies or Determinations? Functional Dependence is a strict form of relevance of the attributes, which describe the problem Example: given nationality, language is fully determined; special syntax formalizes this as Nationality (x, n) ≻ Language (x, l) Determinations specify a sufficient basis vocabulary to construct hypotheses concerning the target predicate. Example: the nationality, the parents’ nationalities and the place of birth determine the language; A determination P ≻ Q says that if any examples match on hypothesis P, then they must also match on hypothesis Q. A determination is consistent with a set of examples if every pair that matches on the predicates on the left-hand side also matches on the goal predicate Inductive Logic Programming Top-down inductive learning method Inductive logic programming (ILP) combines inductive methods for learning with the full power of first-order inductive logic (FOIL) for logical inference The hypotheses are represented as logic programs and given the examples as facts in the programs the logical inference behind the program interpreter derives as conclusions the rules to solve the problem Use first-order literals instead of attributes to represent the examples (logically, they are facts) Use clauses to represent the hypothesis (logically, they are heuristics) Starts the inference with a clause, which represents a very general rule for solving the problem (initial hypothesis) Gradually specialize the so that it matches the facts (fits the examples) Three kinds of literals that can be added: Literals build using predicates: the literal can be negated or unnegated, any existing predicate (including the goal predicate) can be used, the arguments must all be variables literal must include at least one variable from an earlier literal or from the head of the clause. Equality and inequality literals build using comparisons: Such type of literals are used to relate new variables, coming from the examples which already appeare in the clause Arithmetic comparisons: when dealing with functions of variables, literals such as x > y and y ≤ z can be added; their truth will be determined by computational means CHOOSE-LITERAL uses a heuristic based on the idea of information gain (Ockham’s razor to eliminate irrelevant hypotheses) Inductive learning with inverse deduction An inverse resolution step takes a resolvent C and produces two clauses C1 and C2, such that C is the result of resolving C1 and C2. Alternatively, it may take a resolvent C and clause C1 and produce a clause C2 such that C is the result of resolving C1 and C2.