Makoto Kanazawa & Ryo Yoshinaka
Vidéo:
Link to the paper: here
Abstract: We consider a generalization of the “dual” approach to distributional learning of context-free grammars, where each nonterminal A is associated with a string set XA characterized by a finite set C of contexts. Rather than letting XA be the set of all strings accepted by all contexts in C as in previous works, we allow more flexible uses of the contexts in C, using some of them positively (contexts that accept the strings in XA) and others negatively (contexts that do not accept any strings in XA). The resulting more general algorithm works in essentially the same way as before, but on a larger class of context-free languages.
Any question or comment can be made using the comment section of the page below.
This is a very impressive generalisation of distributional learning! Thanks you for this work.
Can one imagine a condition like the sounded pre-fixed in the primal approach? If yes, what may it looks like? If no, why ?
Sound pre-fixed points work for both approaches. For the original primal approach, an SPP must consist of the closures of finite sets of strings. To generalize, you could think of changing either “closure” or “sets of strings”. There is some discussion in the concluding section of our paper. I can probably give more details during the Q/A period.
I have another question: as far as I understand, you do not have a result to compare FCP(k,l) and FCP(k,l,m), or about the potential hierarchy within FCP(k,l,m). What’s your intuition?
My original intuition was that of course more context-free languages are included because FC_L(k,l,m) contains many more sets than FC_L(k,l). But it’s very difficult to give examples of CFLs that differentiate the two. Perhaps you don’t get any more CFLs.
Errata to the article: https://makotokanazawa.ws.hosei.ac.jp/publications/ICGI2021_errata.pdf
Nice work ! On the FCP(k,l,m) question, I have the intuition that the union of m components can be simulated using lots of rules using just m = 1 components.
i.e. if we have a nonterminal B = A_1 \cup \dots A_m then w can just expand out all the rules using B with rules using A_i etc,
But I think that may be incorrect?
I’m not sure how the suggestion goes. If G has an SPP whose B-component is a union of m sets of the form C_i^{\triangleleft} \cap D_i^{\overline{\triangleleft}}, are we supposed to replace B with m new nonterminals A_1, \dots, A_m so that a new SPP will have the set C_i^{\triangleleft} \cap D_i^{\overline{\triangleleft}} as its A_i-component? What will the productions be that have A_i as their left-hand side?
So for every production B \to \alpha we have m productions of the form A_i \to \alpha.
Doesn’t that make all the A_i equivalent?
Oh I am wrong here; the reduction doesn’t work.
I don’t see how to construct an example though.