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:

  • (TypeError) 


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]]

Raises:

  • (TypeError) 


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[In] cex,
  Automaton::TransitionSystem[untyped, In, Out] hypothesis,
  Hash[Integer, Array[In]] state_to_prefix
) -> void

Raises:

  • (TypeError) 


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