Gli autori hanno testato l'approccio SpringRank su set di dati sintetici, dove sono note le classifiche di verità di base, e confrontato i risultati con altri metodi di classificazione. Crediti:Caterina De Bacco, Daniel B. Larremore, e Cristopher Moore
Qualche volta, sapere chi vince e chi perde è più importante di come si gioca.
In un articolo pubblicato questa settimana in Progressi scientifici , i ricercatori del Santa Fe Institute descrivono un nuovo algoritmo chiamato SpringRank che utilizza vittorie e sconfitte per trovare rapidamente le classifiche in agguato nelle grandi reti. Quando testato su un'ampia gamma di set di dati sintetici e reali, che vanno dalle squadre in un torneo di basket del college NCAA al comportamento sociale degli animali, SpringRank ha superato altri algoritmi di classificazione nella previsione dei risultati e nell'efficienza.
Fisica Caterina De Bacco, un ex borsista post-dottorato al Santa Fe Institute, ora alla Columbia University, afferma che SpringRank utilizza informazioni già integrate nella rete. Analizza i risultati di uno a uno, o a coppie, interazioni tra individui. Per classificare le squadre di basket NCAA, Per esempio, l'algoritmo tratterebbe ogni squadra come un singolo nodo, e rappresentare ogni gioco come un vantaggio che porta dal vincitore al perdente. SpringRank analizza quei bordi, e in quale direzione viaggiano, determinare una gerarchia. Ma è più complicato che assegnare semplicemente la classifica più alta alla squadra che ha vinto più partite; Dopotutto, una squadra che gioca esclusivamente squadre di basso rango potrebbe non meritare di essere al top.
Confronto tra i metodi di classificazione SpringRank e Bradley-Terry-Luce (BTL) regolarizzati nella previsione di una varietà di set di dati. Crediti:Caterina De Bacco, Daniel B. Larremore, e Cristopher Moore
"Non è solo una questione di vittorie e sconfitte, ma quali squadre hai battuto e contro quali hai perso, "dice il matematico Dan Larremore, un ex borsista post-dottorato al Santa Fe Institute, ora all'Università del Colorado Boulder. Larremore e De Bacco hanno collaborato con l'informatico Cris Moore, anche all'Istituto Santa Fe, sulla carta.
Come suggerisce il nome, SpringRank tratta le connessioni tra i nodi come molle fisiche che possono contrarsi ed espandersi. Poiché i fisici conoscono da tempo le equazioni che descrivono i moti delle molle, dice De Bacco, l'algoritmo è di facile implementazione. E a differenza di altri algoritmi di classificazione che assegnano numeri ordinali ai nodi:in primo luogo, secondo, Terzo, eccetera., —SpringRank assegna a ciascun nodo un numero a valori reali. Di conseguenza, i nodi possono essere vicini tra loro, disperso, o disposti in schemi più complicati e rivelatori, come cluster di nodi classificati in modo simile.
"Le idee della fisica spesso ci danno algoritmi eleganti ed efficaci, " dice Moore. "Questa è un'altra vittoria per questo approccio".
Le classifiche di basket NCAA sono solo un'area in cui il nuovo algoritmo SpringRank supera i concorrenti. Nel diagramma sopra, i punti sopra la linea mostrano le prove in cui SpringRank prevedeva le partite in modo più accurato. Crediti:Caterina De Bacco, Dan Larremore, e Cris Moore
Nella carta, i ricercatori hanno testato il potere predittivo di SpringRank su una varietà di set di dati e situazioni, compresi i tornei sportivi, comportamenti di dominanza animale tra i parrocchetti in cattività e gli elefanti asiatici in libertà, e le pratiche di assunzione di docenti tra le università.
I ricercatori hanno caricato il codice per SpringRank su GitHub, un archivio di codice online, e dicono che sperano che altri ricercatori, soprattutto nelle scienze sociali, lo userà. "Può essere applicato a qualsiasi set di dati, "dice De Bacco.
Il prossimo set di dati che lei e i suoi coautori intendono analizzare con SpringRank è diverso da quelli presenti nel Progressi scientifici carta. Lavoreranno con Elizabeth Bruch, un professore esterno al Santa Fe Institute, analizzare i modelli di messaggistica nei mercati degli appuntamenti online.
