2016/06/13 by Labai, Nadia, Makowsky, Johann A.
#Combinatorics (math.CO) #FOS: Computer and information sciences #FOS: Mathematics #G.2.1 #I.2.6 #Machine Learning (cs.LG)
paper · doi:10.48550/arxiv.1606.04056
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 α and edge weights β. M. Freedman, L. Lovász 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.