Distributional Learning of Graph Languages Generated by Fixed-Interface Clause Systems
This provides a theoretical framework for learning graph languages, which is relevant for computational linguistics and graph-based machine learning, but the result is incremental as it adapts existing distributional learning techniques to a specific graph formalism.
The paper extends distributional learning to graph languages generated by fixed-interface clause systems, proving that for any fixed parameter tuple, the target language is identifiable in the limit from positive data and membership queries with polynomial-time update.
Distributional learning provides a framework for studying the learnability of structured languages from positive data. In this paper, we extend this framework to graph languages generated by fixed-interface clause systems. We formulate fixed-interface graph pattern clause systems and define a learning model based on positive presentations and membership queries. We consider a bounded class of graph languages satisfying the finite context property under a bounded-degree assumption. The bounds are expressed by a parameter tuple $(Δ,m,s,t,w,d)$, which controls both the generated graph class and the structural complexity of the clause systems. We give an oracle-guided learning algorithm that constructs hypotheses from boundary representations induced by observed positive examples. The proof shows that target contexts eventually appear in the sample, target clauses are reconstructed over the corresponding predicate representatives, and spurious clauses are excluded by membership queries. Hence, for every fixed parameter tuple $(Δ,m,s,t,w,d)$, the target language is identifiable in the limit from positive data and membership queries. We also prove that the learner has polynomial-time update on $\mathcal{FICSL}^{\mathrm{FCP}}_Δ(m,s,t,w,d)$. Thus, the paper gives a parameterized reformulation of distributional learning for regular FGS-style graph languages in a fixed-interface setting.