<p>Learning from iid queries (i.e., &quot;examples&quot; -- these aren't generally called &quot;queries&quot;) 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 <span class="math-container">$L^*$</span> algorithm. You can also simulate equivalence queries by a large enough iid labeled sample (then the learning becomes probabilistic rather than exact).</p>

CC BY-SA 4.0
2023-11-21T13:50:13.997Z
2023-11-21T13:50:13.997Z
Aryeh
<p>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.</p>
<p>Membership queries allow the learner to choose samples to labels, unlike i.i.d queries; But how does the learner choose those samples ?</p>

<query-complexity><sampling>
What is really the difference between membership queries and "querying in i.i.d?
Saginus
# What is really the difference between membership queries and "querying in i.i.d?

(Asked by: username_0 on 2023-11-19)

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 ?

**Tags:** query-complexity, sampling


---

## 1 answers

### Answer by username_1 on 2023-11-21. Score: 1

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).


---

