Class: Lernen::Algorithm::KearnsVazirani::KearnsVaziraniLearner

Inherits:
Learner
  • Object
show all
Defined in:
lib/lernen/algorithm/kearns_vazirani/kearns_vazirani_learner.rb

Overview

KearnzVaziraniLearner is an implementation of Kearnz-Vazirani algorithm.

Kearns-Vazirani is introduced by [Kearns & Vazirani (1994) “An Introduction to Computational Learning Theory”](direct.mit.edu/books/monograph/2604/An-Introduction-to-Computational-Learning-Theory).

Instance Method Summary collapse

Methods inherited from Learner

#learn

Constructor Details

#initialize(alphabet, sul, automaton_type:, cex_processing: :binary) ⇒ KearnsVaziraniLearner

: (

  Array[In] alphabet, System::SUL[In, Out] sul,
  automaton_type: :dfa | :moore | :mealy,
  ?cex_processing: cex_processing_method
) -> void



27
28
29
30
31
32
33
34
35
36
 
# File 'lib/lernen/algorithm/kearns_vazirani/kearns_vazirani_learner.rb', line 27

def initialize(alphabet, sul, automaton_type:, cex_processing: :binary)
  super()

  @alphabet = alphabet.dup
  @sul = sul
  @automaton_type = automaton_type
  @cex_processing = cex_processing

  @tree = nil
end

Instance Method Details

#add_alphabet(input) ⇒ Object 



39
40
41
 
# File 'lib/lernen/algorithm/kearns_vazirani/kearns_vazirani_learner.rb', line 39

def add_alphabet(input)
  @alphabet << input
end

#build_hypothesis ⇒ Object 



44
45
46
47
48
49
 
# File 'lib/lernen/algorithm/kearns_vazirani/kearns_vazirani_learner.rb', line 44

def build_hypothesis
  tree = @tree
  return tree.build_hypothesis if tree

  [build_first_hypothesis, { 0 => [] }]
end

#refine_hypothesis(cex, hypothesis, state_to_prefix) ⇒ Object 



52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
 
# File 'lib/lernen/algorithm/kearns_vazirani/kearns_vazirani_learner.rb', line 52

def refine_hypothesis(cex, hypothesis, state_to_prefix)
  tree = @tree
  if tree
    tree.refine_hypothesis(cex, hypothesis, state_to_prefix)
    return
  end

  @tree =
    DiscriminationTree.new(
      @alphabet,
      @sul,
      cex:,
      automaton_type: @automaton_type,
      cex_processing: @cex_processing
    )
end