-2
$\begingroup$

I'm struggling at finding the difference between algorithms that use i.i.d random queries then request their labels and algorithms that use membership queries.

Membership queries allow the learner to choose samples to labels, unlike i.i.d queries; But how does the learner choose those samples ?

$\endgroup$

1 Answer 1

1
$\begingroup$

Learning from iid queries (i.e., "examples" -- these aren't generally called "queries") is generally harder than learning from membership queries. For example, DFAs are very hard to learn passively (i.e., from iid labeled examples) but can be learned via membership + equivalence queries via Angluin's $L^*$ algorithm. You can also simulate equivalence queries by a large enough iid labeled sample (then the learning becomes probabilistic rather than exact).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.