We prove that any submodular function f: 0,1 ^n -> 0,1,...,k can be represented as a pseudo-Boolean 2k-DNF formula. Pseudo-Boolean DNFs are a natural generalization of DNF representation for functions with integer range. Each term in such a formula has an associated integral constant. We show that an analog of Hastad's switching lemma holds for pseudo-Boolean k-DNFs if all constants associated with the terms of the formula are bounded. This allows us to generalize Mansour's PAC-learning algorithm for k-DNFs to pseudo-Boolean k-DNFs, and hence gives a PAC-learning algorithm with membership queries under the uniform distribution for submodular functions of the form f: 0,1 ^n -> 0,1,...,k . Our algorithm runs in time polynomial in n, k^ O(k k ) , 1 and log(1 ) and works even in the agnostic setting. The line of previous work on learning submodular functions [Balcan, Harvey (STOC '11), Gupta, Hardt, Roth, Ullman (STOC '11), Cheraghchi, Klivans, Kothari, Lee (SODA '12)] implies only n^ O(k) query complexity for learning submodular functions in this setting, for fixed epsilon and delta. Our learning algorithm implies a property tester for submodularity of functions f: 0,1 ^n -> 0, ..., k with query complexity polynomial in n for k=O(( n n)^ 1 2 ) and constant proximity parameter .
For the special case of Boolean functions, characterizations of submodular and monotone submodular functions in terms of simple DNF formulas are known. A Boolean function is monotone submodular if and only if it can be represented as a monotone 1-DNF (see, e.g., Appendix A in @cite_25 ). A Boolean function is submodular if and only if it has a pure (without singleton terms) 2-DNF representation @cite_7 .
@cite_25 @cite_7
340337472 2080957551
Submodular functions are discrete functions that model laws of diminishing returns and enjoy numerous algorithmic applications that have been used in many areas, including combinatorial optimization, machine learning, and economics. In this work we use a learning theoretic angle for studying submodular functions. We provide algorithms for learning submodular functions, as well as lower bounds on their learnability. In doing so, we uncover several novel structural results revealing both extremal properties as well as regularities of submodular functions, of interest to many areas. Abstract After providing a simple characterization of Horn functions (i.e., those Boolean functions that have a Horn DNF), we study in detail the special class of submodular functions. Every prime implicant of such a function involves at most one complemented and at most one uncomplemented variable, and based on this we give a one-to-one correspondence between submodular functions and partial preorders (reflexive and transitive binary relations), and in particular between the nondegenerate acyclic submodular functions and the partially ordered sets. There is a one-to-one correspondence between the roots of a submodular function and the ideals of the associated partial preorder. There is also a one-to-one correspondence between the prime implicants of the dual of the submodular function and the maximal antichains of the associated partial preorder. Based on these results, we give graph-theoretic characterizations for all minimum prime DNF representations of a submodular function. The problem of recognizing submodular functions in DNF representation is coNP-complete.