Vi studerar komplexiteten i ungefärlig representation och inlärning av submodulära funktioner över den enhetliga fördelningen på Booleska hyperkuben {0, 1} n. Vårt huvudsakliga resultat är följande strukturella teorem: någon submodulär funktion är.-stänga i l 2 till ett verkligt värderat beslut träd (DT) djup O(1/ ska 2 ). Detta innebär omedelbart att någon submodulär funktion är nära en funktion av högst 2 variabler och har en spektral l 1 norm av 2 2 ). Det innebär också det närmaste tidigare resultatet som anger att submodulära funktioner kan approximeras av polynom av grad O(1/ på 2 ) (Cheraghchi et al., 2012). Vårt resultat bevisas genom att bygga en approximation av en submodulär funktion av en DT av rank 4/ på 2 och ett bevis på att någon rank-r DT kan calimeras av en DT djupinställning. Dessutom ger vi förbättrade inlärningsalgoritmer för ett antal relaterade inställningar. Vi bevisar också att våra PAC och agnostiska inlärningsalgoritmer i huvudsak är optimala via två nedre gränser: (1) en informationsteoretisk nedre gräns på 2  och 1 / 2/3 ) om komplexiteten i lärande monotona submodulära funktioner i någon rimlig modell (inklusive lärande med värdeförfrågningar); (2) beräkning lägre gräns för n  och 2/3 ) baserat på en minskning av lärandet av glesa pariteter med buller, allmänt tros vara intractable. Dessa är de första lägre gränserna för att lära av submodulära funktioner över den enhetliga fördelningen.
I REF visas det också att två slumpmässiga exempel (eller till och med värdefrågor) är nödvändiga för att PAC lär sig monotona submodulära funktioner till 1 -terror av.
Representation, Approximation and Learning of Submodular Functions Using Low-rank Decision Trees
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science', 'Mathematics']}