On the exact learnability of graph parameters: the case of partition functions

DOI10.4230/LIPICS.MFCS.2016.63MaRDI QIDQ4608626zbMATH OpenOpenAlexFDO

Authors Nadia Labai, Johann A. Makowsky

Publication date 21 March 2018

Full work available at URL https://arxiv.org/abs/1606.04056

zbMATH Keywords

partition functionconnection matricesweighted homomorphismexact learning

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Computational learning theory (68Q32) Graph theory (including graph drawing) in computer science (68R10) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Abstract: 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 $$. 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.

Recommendations

• Parameterized Learnability of k-Juntas and Related Problems
• Parameterized learnability of juntas
• How many queries are needed to learn?
• scientific article; zbMATH DE number 1263194
• The complexity of partition functions

Cited in

(1)

• My writing

This page was built for publication: On the exact learnability of graph parameters: the case of partition functions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4608626)