Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It only takes a minute to sign up.
Sign up to join this community
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 ?
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).
