Classificazione multiclasse con caratteristiche utili rare: limiti fondamentali e ottimalità del Diversity Pursuit Higher Criticism Thresholding

Abstract degli autori

Consideriamo la classificazione in spazi delle caratteristiche ad alta dimensionalità, in cui solo una frazione infinitesima delle caratteristiche è utile e il numero di classi può essere elevato. Sebbene il regime delle caratteristiche utili rare e deboli sia ben compreso nel caso binario, la sua versione multiclasse solleva nuove questioni: una caratteristica può essere utile per discriminare tra le classi senza distinguere una specifica coppia di classi. Ci concentriamo su un modello di diversità con caratteristiche rare, in cui la maggior parte delle caratteristiche è inutile, ma una piccola frazione favorisce la discriminazione tra le classi in modo rilevabile con un test di diversità applicato a ciascuna caratteristica, come l’ANOVA a una via o il test di Kruskal-Wallis. Per questo scenario, proponiamo Diversity Pursuit Higher Criticism Thresholding (DP-HCT), una procedura di screening delle caratteristiche che applica una soglia Higher Criticism all’insieme dei p-value ottenuti dai test di diversità per ciascuna caratteristica. Giustifichiamo DP-HCT nell’ambito di un modello gaussiano multiclasse Rare-and-Weak Useful Feature, con contrasti tra le medie delle classi di ampiezza fissa e direzioni casuali, estendendo il modello binario di Donoho e Jin (2008). Quando il numero di classi è fisso, il nostro modello recupera la transizione di fase del caso binario. Quando invece il numero di classi cresce in modo logaritmico rispetto al numero di caratteristiche, ricaviamo una nuova transizione di fase, strettamente più difficile, determinata dall’aumento dei gradi di libertà e dal suo effetto sul tasso di coda delle caratteristiche utili. Mostriamo che, ogniqualvolta è possibile classificare con risultati superiori al caso, DP-HCT con ANOVA, seguito da un semplice classificatore basato sulla somiglianza con le medie delle classi, raggiunge un’accuratezza asintoticamente perfetta. Esperimenti su benchmark reali di classificazione multiclasse mostrano miglioramenti sostanziali, mentre simulazioni numeriche confermano che la curva di transizione di fase ricavata predice accuratamente il comportamento di DP-HCT a campione finito nel regime in cui cresce il numero di classi.