Learn-One-Rule Algorithm


Learn-One-Rule(target_attribute, attributes, examples, k)

;Returns a single rule that covers some of the Examples

  best-hypothesis = the most general hypothesis

  candidate-hypotheses = {best-hypothesis}

  while candidate-hypothesis
    ;Generate the next more specific candidate-hypotheses

    all-constraints = all "att.=val." contraints

    new-candidate-hypotheses = all specializations of candidate-hypotheses by adding all-constraints

    remove from new-candidate-hypotheses any that are duplicates, inconsistent, or not maximally specific

    ;Update best-hypothesis

    best-hypothesis = $\argmax_{h \in \text{new-candidate-hypotheses}}$ Performance(h,examples,target_attribute)

    ;Update candidate-hypotheses

    candidate-hypotheses = the k best from new-candidate-hypotheses according to Performance.

  prediction = most frequent value of target_attribute from examples that match best-hypothesis

  return IF best-hypothesis THEN prediction





Performance(h, examples, target_attribute)

  h-examples = the set of examples that match h

  return - Entropy(h-examples) wrt target_attribute