Abstract | ||
---|---|---|
In active learning, membership queries and equivalence que- ries have established themselves as the standard combination to be used. However, they are quite “unnatural” for real learning environments (membership queries are oversimplified and equivalence queries do not have a correspondence in a real life setting). Based on several linguistic arguments that support the presence of corrections in children's language acquisition, we propose another kind of query called correction query. We provide an algorithm that learns DFA using correction and equivalence queries in polynomial time. Despite the fact that the worst case complexity of our algorithm is not better than Angluin's algorithm, we show through a large number of experiments that the average number of queries is considerably reduced by using correction queries. |
Year | DOI | Venue |
---|---|---|
2006 | 10.1007/11872436_23 | ICGI |
Keywords | Field | DocType |
correction query,language acquisition,active learning,real learning environment,large number,real life setting,average number,equivalence que,membership query,equivalence query,learning dfa,polynomial time | Deterministic automaton,Active learning,Computer science,Theoretical computer science,Finite-state machine,Natural language,Equivalence (measure theory),Language acquisition,Time complexity,Worst-case complexity | Conference |
Volume | ISSN | ISBN |
4201 | 0302-9743 | 3-540-45264-8 |
Citations | PageRank | References |
21 | 1.00 | 3 |
Authors | ||
3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Leonor Becerra-Bonache | 1 | 65 | 11.46 |
Adrian-Horia Dediu | 2 | 315 | 25.79 |
Cristina Tîrnăucă | 3 | 38 | 4.10 |