Class: Lernen::Equiv::RandomWalkOracle

Inherits:
Oracle
  • Object
show all
Defined in:
lib/lernen/equiv/random_walk_oracle.rb

Overview

RandomWalkOracle provides an implementation of equivalence query that finds a counterexample by using random walk.

This takes two important parameters:

  • ‘max_steps` (default: `1500`): It is a limit of steps of a random walk.

    If a random walk is tried up to this value and no counterexample is found,
it returns `nil` finally.

  • ‘reset_prob` (default: `0.09`): It is a probability to reset a random walk.

    On resetting a random walk, it resets a word, but it does not reset
a step counter.

Instance Attribute Summary

Attributes inherited from Oracle

#sul

Instance Method Summary collapse

Methods inherited from Oracle

#+, #stats

Constructor Details

#initialize(alphabet, sul, max_steps: 3000, reset_prob: 0.09, random: Random) ⇒ RandomWalkOracle

: (

  Array[In] alphabet,
  System::SUL[In, Out] sul,
  ?max_steps: Integer,
  ?reset_prob: Float,
  ?random: Random
) -> void



33
34
35
36
37
38
39
40
 
# File 'lib/lernen/equiv/random_walk_oracle.rb', line 33

def initialize(alphabet, sul, max_steps: 3000, reset_prob: 0.09, random: Random)
  super(sul)

  @alphabet = alphabet
  @max_steps = max_steps
  @reset_prob = reset_prob
  @random = random
end

Instance Method Details

#find_cex(hypothesis) ⇒ Object 



43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
 
# File 'lib/lernen/equiv/random_walk_oracle.rb', line 43

def find_cex(hypothesis)
  super

  reset_internal(hypothesis)
  word = []

  @max_steps.times do
    if @random.rand < @reset_prob
      reset_internal(hypothesis)
      word = []
    end

    word << @alphabet.sample(random: @random)

    hypothesis_output, sul_output = step_internal(hypothesis, word.last)

    if hypothesis_output != sul_output # steep:ignore
      @sul.shutdown
      return word
    end
  end

  nil
end