Class: Lernen::Algorithm::Learner

Inherits:
Object
  • Object
show all
Defined in:
lib/lernen/algorithm/learner.rb

Overview

Learner is an abstraction of implementations of learning algorithms.

Note that this class is abstract. We should implement the following method:

  • #oracle
  • #refine(cex, hypothesis, state_to_prefix)
  • #build_hypothesis

Instance Method Summary collapse

Instance Method Details

#add_alphabet(input) ⇒ Object

Adds the given input to the alphabet.

In the default, this method raises TypeError as the learner does not support adding an input character to the alphabet.

: (In input) -> void

Raises:



55
56
57
 
# File 'lib/lernen/algorithm/learner.rb', line 55

def add_alphabet(input)
  raise TypeError, "This learner does not support adding an input character to the alphabet"
end

#build_hypothesis ⇒ Object

This is an abstract method. r : () -> [Automaton::TransitionSystem[untyped, In, Out], Hash[Integer, Array[In]]]

Raises:



75
76
77
 
# File 'lib/lernen/algorithm/learner.rb', line 75

def build_hypothesis
  raise TypeError, "abstract method: `build_hypothesis`"
end

#learn(oracle, max_learning_rounds: nil) ⇒ Object

Runs the learning algorithm and returns an inferred automaton.

max_learning_rounds is a parameter for specifying the maximum number of iterations for learning. When max_learning_rounds: nil is specified, it means the algorithm only stops if the equivalent hypothesis is found.

: ( Equiv::Oracle[In, Out] oracle, ?max_learning_rounds: Integer | nil ) -> Automaton::TransitionSystem[untyped, In, Out]



27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
 
# File 'lib/lernen/algorithm/learner.rb', line 27

def learn(oracle, max_learning_rounds: nil)
  hypothesis, state_to_prefix = build_hypothesis
  cex = oracle.find_cex(hypothesis)
  return hypothesis if cex.nil?

  learning_rounds = 0
  loop do
    break if max_learning_rounds && learning_rounds == max_learning_rounds
    learning_rounds += 1

    refine_hypothesis(cex, hypothesis, state_to_prefix)

    hypothesis, state_to_prefix = build_hypothesis
    cex = oracle.find_cex(hypothesis)
    break if cex.nil?
  end

  hypothesis
end

#refine_hypothesis(cex, hypothesis, state_to_prefix) ⇒ Object

Refine the learning hypothesis by the given counterexample.

This is an abstract method.

: ( Array cex, Automaton::TransitionSystem[untyped, In, Out] hypothesis, Hash[Integer, Array[In]] state_to_prefix ) -> void

Raises:



68
69
70
 
# File 'lib/lernen/algorithm/learner.rb', line 68

def refine_hypothesis(cex, hypothesis, state_to_prefix)
  raise TypeError, "abstract method: `refine_hypothesis`"
end