search

Balletie / asml-seminar-report

Bachelor Seminar report on active state machine learning
0 stars 0 forks source link

Random sampling for equiv queries #30

Closed sander2 closed 8 years ago

sander2 commented 8 years ago

I think the "Approximating EQUIV (M) queries with MEMBER(w) queries" subsection should contain a short subsection on random sampling.

Hjdskes commented 8 years ago

Why? Is it not enough to point towards a paper that explains it? I think we need to seriously start watching the word count now, especially considering that @Balletie wanted to write about TTT and the fact that we still need a conclusion and perhaps an expansion of applications.

sander2 commented 8 years ago

Because it was the first method of approximating equiv queries, and (more importantly) because it is used often used in practice (because W-method is expensive).

sander2 commented 8 years ago

Note that random sampling is the simplest possible way to approximate equiv queries. It doesn't need to be very long. Something like this (was removed from L* section a while ago):

Answers to equivalence queries are approximated by repeatedly running random membership queries. For each of these membership queries, a random sequence of symbols from in input alphabet is generated, and is then checked against both the proposed DFA and the unknown regular set. If they do not match, the counterexample is found. This process is repeated until the desired confidence that the statemachine is correct is reached.

Hjdskes commented 8 years ago

Alright, that seems short enough to be added somewhere. Can you open a PR for this?