Învățarea cu funcții submodulare: O perspectivă asupra optimizării convexe

Titlul original:

Learning with Submodular Functions: A Convex Optimization Perspective

Conținutul cărții:

Funcțiile submodulare sunt relevante pentru învățarea automată din cel puțin două motive: (1) unele probleme pot fi exprimate direct ca optimizare a funcțiilor submodulare și (2) extensia Lovsz a funcțiilor submodulare oferă un set util de funcții de regularizare pentru învățarea supravegheată și nesupravegheată. În Learning with Submodular Functions: A Convex Optimization Perspective, teoria funcțiilor submodulare este prezentată într-un mod autoconținut din perspectiva analizei convexe, prezentând legături strânse între anumite poliedre, optimizarea combinatorie și problemele de optimizare convexă.

În special, se descrie modul în care minimizarea funcțiilor submodulare este echivalentă cu rezolvarea unei mari varietăți de probleme de optimizare convexă. Acest lucru permite derivarea de noi algoritmi eficienți pentru minimizarea aproximativă și exactă a funcțiilor submodulare cu garanții teoretice și performanțe practice bune.

Prin enumerarea multor exemple de funcții submodulare, se trec în revistă diverse aplicații pentru învățarea automată, cum ar fi gruparea, proiectarea experimentală, plasarea senzorilor, învățarea structurii modelului grafic sau selectarea subseturilor, precum și o familie de norme structurate care induc sparsitatea și care pot fi derivate și utilizate din funcții submodulare. Învățarea cu funcții submodulare: A Convex Optimization Perspective este o referință ideală pentru cercetătorii, oamenii de știință sau inginerii interesați de aplicarea funcțiilor submodulare la problemele de învățare automată.