Indici di potere esatti per ensemble con voto a maggioranza relativa

Abstract degli autori

Gli ensemble con voto a maggioranza relativa aggregano le predizioni di più classificatori di base e restituiscono la classe che riceve più voti, risolvendo di norma le parità in modo casuale. Nonostante la semplicità della regola di aggregazione, attribuire a ciascun classificatore di base il suo impatto sulle predizioni dell’ensemble è tutt’altro che immediato. L’impatto di un singolo classificatore dipende infatti da come i suoi voti interagiscono con quelli di tutti gli altri classificatori dell’ensemble, per esempio nel risolvere le parità, e non soltanto dalle sue predizioni. Affrontiamo il problema dell’attribuzione con strumenti consolidati della teoria dei giochi cooperativi, studiando gli indici di potere di Banzhaf e Shapley per nuovi giochi che modellano il voto a maggioranza relativa e la risoluzione casuale delle parità, in contesti di classificazione binaria e multiclasse. Calcolare gli indici di potere è, in generale, computazionalmente intrattabile. Sorprendentemente, i nostri metodi, denominati nel loro insieme ENPOWER, consentono di calcolare esattamente i valori di Banzhaf e Shapley in tempo lineare nel caso della classificazione binaria e in tempo polinomiale di basso grado nel caso multiclasse. Gli algoritmi di ENPOWER si basano su nuove formulazioni combinatorie degli indici di Banzhaf e Shapley, da cui derivano soluzioni in forma chiusa per il caso binario e rappresentazioni mediante funzioni generatrici ordinarie per il caso multiclasse. Convalidiamo empiricamente i metodi di ENPOWER, dimostrandone l’elevata applicabilità e ottenendo valori di attribuzione che i metodi esistenti non rilevano. Applichiamo l’attribuzione di ENPOWER alla riduzione degli ensemble e alla combinazione in ensemble, basata su prompt, di modelli visione-linguaggio.