3
$\begingroup$

Suppose I have context-free grammar (CFG) $L$ that pumps out words in that language. I want a machine learning system that can detect if a word $w$ came from $L$ or not. It has access to a stream from $L$ that is constantly producing words in $L$ at random. In this case, the system can only be trained with positive examples. The system also has access to a verifier for $L$. The system (if it chooses to) can generate strings and verify that the string is in $L$ or not. However, the system could just cheat and just use the verifier, so during the test phase, it gets disabled (during the learning phase, it uses the verifier as much as it wants). Moreover, $L$ can be augmented and changed, and the system should adapt to that change.

For instance, let's consider this regex (a regex is a CFG): $$(aa)*$$

This language only produces a string of $aa$'s of even length. Suppose I modified the regex to $(aa|bb)*$. This system should adapt to recognize this new language.

What kind of methods/approaches should I consider in my design?

Improve this question
$\endgroup$
0

1 Answer 1

Reset to default
2
$\begingroup$

The process of automatically learning a grammar from examples of a language is called grammar induction. Since you mention that L can be "augmented and changed", it might be feasible to solve this problem using an adaptive parser.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Has this been applied to NLP purposes, after POS tagging? $\endgroup$
    – lee
    Mar 27, 2018 at 19:22
  • $\begingroup$ Grammar induction has also been used in some machine-translation systems, $\endgroup$
    – Anderson Green
    Mar 29, 2018 at 22:24
  • $\begingroup$ Do you happen to have any idea how successful these methods were compared to the typical approaches? $\endgroup$
    – lee
    Mar 30, 2018 at 15:17

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .