Movatterモバイル変換


[0]ホーム

URL:


Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

Sign up
Appearance settings

Determining whether a state is new from the equivalence oracle's perspective.#68

Discussion options

I'm studying the implementation of theStatePrefixEqOracle and I've taken an interest in thedepth_first parameter which, when true, makes the oracle explore the new states of the hypothesis first, as explained in the comments:

classStatePrefixEqOracle(Oracle):"""    Equivalence oracle that achieves guided exploration by starting random walks from each state a walk_per_state    times. Starting the random walk ensures that all states are reached at least walk_per_state times and that their    surrounding is randomly explored. Note that each state serves as a root of random exploration of maximum length    rand_walk_len exactly walk_per_state times during learning. Therefore excessive testing of initial states is    avoided.    """def__init__(self,alphabet:list,sul:SUL,walks_per_state=10,walk_len=12,depth_first=False):"""        Args:            alphabet: input alphabet            sul: system under learning            walks_per_state:individual walks per state of the automaton over the whole learning process            walk_len:length of random walk            depth_first:first explore newest states        """

I noticed that to achieve this, the list of states to be explored is sorted based on the length of the access sequence, as showcased in the following snippet:

ifself.depth_first:# reverse sort the states by length of their access sequences# first do the random walk on the state with longest access sequencestates_to_cover.sort(key=lambdax:len(x.prefix),reverse=True)else:random.shuffle(states_to_cover)

Does greater length of access sequence imply that a state is newer?

You must be logged in to vote

Hi,

in general yes, but not necessarily*. I will explain in a bit why. Thisself.depth_first is a small heuristic that I have added when developing this oracle, tbh, it would have the same guarantees and everything without it, I just liked the idea that you first try to find counterexamples for states with the longer prefix. In the end, it does not matter as much, as all states will serve as an origin for a test case exactlywalks_per_state times.

* I like to think of L* as a BFS exploration of underlying/hidden state space, while KV is more depth-first. So, in L*, shorter prefixes are generally identified early on, while in KV this is not necessarily the case.

TLDR:
The heuristic I liked…

Replies: 1 comment 3 replies

Comment options

Hi,

in general yes, but not necessarily*. I will explain in a bit why. Thisself.depth_first is a small heuristic that I have added when developing this oracle, tbh, it would have the same guarantees and everything without it, I just liked the idea that you first try to find counterexamples for states with the longer prefix. In the end, it does not matter as much, as all states will serve as an origin for a test case exactlywalks_per_state times.

* I like to think of L* as a BFS exploration of underlying/hidden state space, while KV is more depth-first. So, in L*, shorter prefixes are generally identified early on, while in KV this is not necessarily the case.

TLDR:
The heuristic I liked, may lead to earlier identification of counterexamples, but upon completion of the whole test suite (walks_per_state tests of from each state of lengthwalk_len), the order does not matter.

You must be logged in to vote
3 replies
@steve-anunknown
Comment options

Understood, thanks for the insight! I will explore it some more on my own.

@emuskardin
Comment options

Just had a random realization: if you care about which states are youngest/identified last, in the L* you can see this by simply looking at the S set of the observation table. The S set is an ordered list where the the last element of the list is the last identified element, first element is the initial state and so on... so it is ordered from youngest to oldest.

In KV I would have to think a bit more, but this does not help you much from oracle perspective.

In an oracle, you can keep a list of list of states, where each sublist "identifies" the age of the state.

So in eq Oracle, you can do something like this:

       ....       # in init        # list of lists which identifies in which learning round state is identified/how old the state is        # [[s1,s2], [s3], [s4,s5,s6]]        # s1 and s2 are oldest, and s4,s5,s6 youngest        self.state_identification_round = []    def find_cex(self, hypothesis):        if self.state_identification_round is []:            self.state_identification_round.append([s.state_id for s in hypothesis.states])                new_states = []        for s in hypothesis.states:            state_existed_before = any(s.state_id in previous_generation for previous_generation in self.state_identification_round)            if not state_existed_before:                new_states.append(s.state_id)                self.state_identification_round.append(new_states)
@steve-anunknown
Comment options

This looks good. I tried something similar, using a dictionary with the state ids as keys and the 'age' of the states as values, incrementing them with each round. I will give your idea a try too, just for the sake of comparison.

Answer selected bysteve-anunknown
Sign up for freeto join this conversation on GitHub. Already have an account?Sign in to comment
Category
Q&A
Labels
None yet
2 participants
@steve-anunknown@emuskardin

[8]ページ先頭

©2009-2025 Movatter.jp