On the exact learnability of graph parameters: The case of partition functions
We study the exact learnability of real valued graph parameters $f$ which are known to be representable as partition functions which count the number of weighted homomorphisms into a graph $H$ with vertex weights $\alpha$ and edge weights $\beta$. M. Freedman, L. Lov\'asz and A. Schrijver have given a characterization of these graph parameters in terms of the $k$-connection matrices $C(f,k)$ of $f$. Our model of learnability is based on D. Angluin's model of exact learning using membership and equivalence queries. Given such a graph parameter $f$, the learner can ask for the values of $f$ for graphs of their choice, and they can formulate hypotheses in terms of the connection matrices $C(f,k)$ of $f$. The teacher can accept the hypothesis as correct, or provide a counterexample consisting of a graph. Our main result shows that in this scenario, a very large class of partition functions, the rigid partition functions, can be learned in time polynomial in the size of $H$ and the size of the largest counterexample in the Blum-Shub-Smale model of computation over the reals with unit cost.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
On the Learnability of Possibilistic Theories
We investigate learnability of possibilistic theories from entailments in light of Angluin's exact learning model. We consider cases in which only membership, only equivalence, and both kinds of queries can be posed by t…
On statistical learning of graphs
We study PAC and online learnability of hypothesis classes formed by copies of a countably infinite graph G, where each copy is induced by permuting G's vertices. This corresponds to learning a graph's labeling, knowing …
Learning to Execute Graph Algorithms Exactly with Graph Neural Networks
Understanding what graph neural networks can learn, especially their ability to learn to execute algorithms, remains a central theoretical challenge. In this work, we prove exact learnability results for graph algorithms…
Graph Neural NetworkLanguage learnability in the limit for general metrics: a Gold-Angluin result
In his pioneering work in the field of Inductive Inference, Gold (1967) proved that a set containing all finite languages and at least one infinite language over the same fixed alphabet is not learnable in the exact sens…
A Parameterized Theory of PAC Learning
Probably Approximately Correct (i.e., PAC) learning is a core concept of sample complexity theory, and efficient PAC learnability is often seen as a natural counterpart to the class P in classical computational complexit…
PAC learning