Det har funnits stort intresse för maskininlärning och algoritmiska spelteori samhällen på förståelse och användning av submodulära funktioner. Trots detta stora intresse är det inte mycket man vet om deras inlärningsförmåga med hjälp av data. Motiverade av tillämpningar, såsom prissättning varor i ekonomi, i detta dokument överväger PAC-stil lärande av submodulära funktioner i en distributionsmiljö. Ett problem instans består av en distribution på {0, 1} n och en verkligt värderad funktion på {0, 1} n som är icke-negativ, monoton och submodulär. Vi får poly(n) prover från denna fördelning, tillsammans med värdena för funktionen vid dessa provtagningspunkter. Uppgiften är att uppskatta värdet av funktionen till inom en multiplikativ faktor vid efterföljande provpunkter som dras från samma fördelning, med tillräckligt hög sannolikhet. Vi utvecklar den första teoretiska analysen av detta problem, vilket visar på ett antal viktiga och nästan snäva resultat. Till exempel, om den underliggande distributionen är en produktdistribution då vi ger en lärande algoritm som uppnår en konstant-faktor approximation (enligt vissa antaganden). Men för allmänna distributioner ger vi en överraskande Õ(n 1/3 ) nedre gräns baserat på en ny intressant klass av matroider och vi visar också en O(n 1/2 ) övre gräns. Vårt arbete kombinerar centrala frågor inom optimering (submodulära funktioner och matriser) med centrala ämnen inom lärande (distributionslärande och PAC-liknande analyser) och med centrala begrepp i pseudo-randomness (lossless expander grafer). Vår analys innebär en twist på de vanliga inlärningsteori modeller och avslöjar några intressanta strukturella och extrem egenskaper hos submodulära funktioner, som vi misstänker är användbara i andra sammanhang. I synnerhet, för att bevisa vår allmänna lägre gräns, använder vi förlustfria expanderare för att bygga en ny familj av matroider som kan ta vilt varierande rang värden på superpolynomiskt många uppsättningar; ingen sådan konstruktion var tidigare känd. Denna konstruktion visar oväntade yttre egenskaper hos submodulära funktioner.
Omöjlighetsresultat uppstår för allmänna distributioner, i vilket fall submodulära funktioner inte är (n −1/3 )-PMAC inlärbara REF.
Learning submodular functions
{'venue': "STOC '11", 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}