Mam na myśli w szczególności rodziny języków, które dopuszczają dowolnie długie ciągi znaków - a nie koniunkcje na n bitach lub listach decyzyjnych lub jakimkolwiek innym „prostym” języku zawartym w {0,1} ^ n.
Pytam o zwykłe języki „teoretyków automatycznych”, a nie teoretyków „logicznych”: coś w rodzaju języków, które można częściowo testować, języków o zerowej wysokości, języków, które można testować lokalnie, tego rodzaju rzeczy. Odpowiednim parametrem złożoności n jest rozmiar minimalnego akceptującego DFA. Krótko mówiąc: czy istnieje interesująca rodzina DFA w stanie n, o której wiadomo, że skutecznie można ją nauczyć PAC?
Odpowiedzi:
Niedawny wynik na wielomianowej zdolności uczenia się zestawów półliniowych na LICS 2010: Parikh Images of Regular Languages: Complexity and Applications . Chyba nie tego szukasz.
Powinieneś także rzucić okiem na artykuł Clarka i Thollarda: PAC-learnability of Probabilistic Deterministic Finite State Automata
źródło
Ten artykuł daje dobrą wskazówkę na temat wyników uczenia się PAC dla języków podzielonych na części: Nauka języków rozdzielnych liniowo
Prace Clarka i Thollarda zostały udoskonalone przez Castro i Gavaldę w sposób, który pasuje do tego, czego szukasz: w kierunku wykonalnego uczenia się PAC probabilistycznych deterministycznych automatów skończonych
I ta praca jest dobrą odpowiedzią na wstępne pytanie: O możliwości uczenia się ideałów losowych . Jednym z autorów jest prawdopodobnie ta sama osoba, która wcześniej zadała pytanie tutaj, ale znalazłem tę stronę, pracując nad tym problemem i właśnie znalazłem ten artykuł: może to pomóc innym w uzyskaniu tego odniesienia.
źródło