Dolne granice uczenia się w zapytaniu o członkostwo i modelu kontrprzykładowym

Dana Angluin ( 1987 ; pdf ) definiuje model uczenia się z zapytaniami o członkostwo i teoriami (kontrprzykłady do proponowanej funkcji). Pokazuje, że zwykły język reprezentowany przez minimalny DFA z stanów jest możliwy do nauczenia się w czasie wielomianowym (gdzie proponowane funkcje to DFA) z zapytaniami o członkostwo i co najwyżej kwerendami teoretycznymi ( to rozmiar największego kontrprzykładu podanego przez opiekuna). Niestety nie omawia ona dolnych granic.$n$$O(mn^2)$$n−1$$m$

Możemy nieco uogólnić model, zakładając magicznego nauczyciela, który może sprawdzić równość między dowolnymi funkcjami i dostarczyć kontrprzykłady, jeśli są inne. Następnie możemy zapytać, jak trudno jest uczyć się klas większych niż zwykłe języki. Interesuje mnie to uogólnienie i oryginalne ograniczenie do zwykłych języków.

Czy są znane dolne granice liczby zapytań w modelu członkostwa i kontrprzykładu?

Interesują mnie dolne granice liczby zapytań członkowskich, zapytań teoretycznych lub kompromisów między nimi. Interesują mnie dolne granice dla dowolnej klasy funkcji, nawet dla bardziej skomplikowanych klas niż zwykłe języki.

Jeśli nie ma dolnych granic: Czy istnieją znane bariery w udowadnianiu dolnych granic zapytania w tym modelu?

Powiązane pytania

Czy istnieją ulepszenia algorytmu Dany Angluin do uczenia się regularnych zestawów

Tak, niektóre dolne granice są znane. Na przykład, zakładając, że , nie można nawet poprawnie nauczyć się formuł DNF z odczytem trzykrotnie w czasie wielomianowym. Cały artykuł opracowuje takie wyniki twardości przy użyciu czegoś zwanego „problemem reprezentacji”.$NP \neq coNP$

$O(n)$$O(n^2+ n \log m)$

Jednym łatwym sposobem na osiągnięcie dolnych granic jest teoria informacji. Możesz dowiedzieć się, ile jest różnych celów i ile bitów daje zapytanie itp. Te górne granice zbliżają się, ale ich nie ma. Istnieją również kwestie, o których należy pomyśleć, dotyczące tego, w jaki sposób „kontrprzykłady” docierają do ucznia. Dobrze dobrany kontrprzykład może dostarczyć sporo informacji.

Uaktualnienie do powyższej dyskusji : Angluin i Dohrn zajmują się tym zagadnieniem przy pomocy losowych kontrpróbek w ostatnim artykule .