Gli argomenti trattati nel libro sono nell’ordine:

1. Optimal Stopping: ovvero quanto tempo dedicare alla ricerca e all’esecuzione
2. Explore/Exploit: come bilanciare l’esplorazione di nuove opzioni o la scelta di un’opzione già conosciuta
3. Sorting: ovvero, l’arte di ordinare
4. Caching: ovvero, come organizzare oggetti utili in gruppi gerarchicamente ordinati
5. Scheduling: ovvero, come prioritizzare
6. Bayes’s Rule: come prevedere il futuro
7. Overfitting: quando l’informazione è troppa
8. Relaxation: ovvero come ridurre la complessità di un problema
9. Randomness: quando lasciare la scelta al caso
10. Networking: come creare collegamenti
11. Game Theory: come ragionano gli altri esseri umani

Tutte le attività di ricerca – dal parcheggio più vicino alla propria destinazione, alla scelta di un collaboratore, alla ricerca di una nuova casa o di un partner da sposare – sono caratterizzate da una scelta fondamentale, che si presenta ad ogni nuova opportunità: quando smettere di cercare e scegliere la soluzione migliore?

Alcuni impegni sono di breve durata (come l’occupazione di un parcheggio più o meno distante dalla destinazione desiderata), altri rappresentano un impegno di lungo termine (la scelta di un collaboratore o un partner). Qual è il rapporto ottimale tra la possibilità di esplorare nuove opzioni o la scelta di un’opzione già conosciuta? Gli autori presentano due algoritmi:

• la “regola del 37%” (37% rule)
• la “regola della soglia” (threshold rule).

LA REGOLA DEL 37%

Conoscendo il campione totale di possibili opzioni di scelta (es. dieci potenziali partner, venti appartamenti, cento candidati per una posizione), chi sceglie avrà la più alta probabilità di effettuare l’opzione migliore dopo aver visionato (esplorato) almeno il 37% delle opzioni disponibili, oppure la prima opzione che eccede una soglia limite (solitamente espressa in percentili). Su cento candidati, le opzioni per chi sceglie sono quelle di visionare almeno 37 candidati su cento, e fare un’offerta al migliore dei disponibili a partire dal trentottesimo candidato, oppure selezionare il primo candidato che sia al di sopra della soglia proposta (es. novantacinquesimo percentile).

IL BILANCIAMENTO TRA NUOVO E MIGLIORE

Allo stesso modo: come bilanciare tra “nuovo” e “migliore”? Tra il nuovo ristorante in città – che ha aperto questa settimana – e il miglior ristorante della stessa città – già provato e conosciuto da tempo? O tra quale film vedere al cinema, se quello nuovo di una produzione indipendente, o il sesto episodio di una saga già conosciuta? O anche, come ottimizzare a probabilità di vincita al casinò? Gli autori propongono tre algoritmi:

1) Win-Stay, Lose-Shift:

è utilizzato nel contesto dei casinò, prevede di restare sulla stessa slot machine/roulette finché quest’ultima continua a pagare. Non appena il gioco realizza una perdita, passare ad una slot/roulette diversa

2) The Gittings Index:

misura la probabilità di vincita calcolando il numero di giochi vincenti e perdenti delle diverse slot: l’idea è quella di restare sulla slot con l’indice più alto, perché nel lungo periodo sarà quella che pagherà maggiori dividendi

3) Upper Confidence Bound:

fa riferimento all’intervallo di confidenza (l’errore di misurazione intorno ai dati) e di scegliere l’opzione con l’intervallo di confidenza più ampio verso l’alto (cioè l’opzione con la più alta probabilità di rivelarsi migliore, sulla base delle osservazioni disponibili ora).

Per quanto riguarda l’organizzazione, esistono diversi algoritmi che possono essere utilizzati: bubble sort, che prevede l’inversione di due coppie di oggetti in base all’ordine che si vuole creare – esempio l’ordine alfabetico dei libri su uno scaffale – e di continuare nella stessa inversione finché l’intero campione non ha l’ordine desiderato. Questo sistema, semplice e intuitivo, è oltremodo inefficiente, perché segue un andamento quadratico.

Per migliorare i tempi impiegati, possono essere utilizzati altri metodi, come il Mergesort – che prevede lo scorporo dell’intero campione in coppie, che vengono ordinate e progressivamente unite ad altre coppie in maniera progressiva, da due a due, a quattro a quattro, otto a otto, ecc. fino ad arrivare all’insieme completo. Una variazione di questo modello, chiamata Bucketsort, prevede di suddividere l’intero insieme in sottocategorie, se presenti e conosciute, senza un ordine specifico prestabilito, e procedere ad ordinare per sotto-insiemi (bucket – o “cestini”).

Come organizzare la memoria, o la cache? L’obiettivo è quello di provare a “prevedere” il futuro, e quello che ci servirà. Esistono diversi approcci per tenere in memoria, o a distanza minima, gli oggetti più utili: il primo approccio è quello di random eviction, o “estrazione randomica” da un insieme, tra tutti gli oggetti disponibili. Un altro approccio è quello di First-In, First-Out (primo ad entrare, primo ad uscire), ovvero di estrarre il primo elemento inserito in memoria, e tutti gli altri in ordine temporale. Infine, un ulteriore approccio è quello Least Recently Used, ovvero di estrarre l’elemento più a lungo inutilizzato presente in memoria.

Per organizzare le attività, esistono due principali scuole di pensiero (e relativi algoritmi): per minimizzare i tempi d’attesa, è consigliabile l’utilizzo dell’algoritmo earliest due date, ovvero completare le attività iniziando da quella con la scadenza più vicina, e proseguire nell’ordine. Per massimizzare il numero delle attività svolte, è consigliabile procedere utilizzando l’algoritmo shortest processing time, partendo, ovvero, dalle attività più veloci da svolgere, indipendentemente dalla data di scadenza, e procedere con quelle progressivamente più lunghe.

Come prevedere il futuro? Il teorema di Bayes – un ecclesiastico inglese vissuto nel 18esimo secolo – dice che la probabilità di un evento è condizionata dagli eventi avvenuti in precedenza. Questo concetto viene esteso nella legge di Laplace, che formula che per calcolare la probabilità di un evento, anche avendo a disposizione un dataset limitato di informazioni, è sufficiente contare le volte che l’evento si è verificato nel passato, aggiungere uno a questo valore, e dividere il tutto per il numero di opzioni possibili più due.

Come muoversi, invece, quando le informazioni sono troppe? Gli autori suggeriscono di utilizzare diverse tattiche, tra cui la cross-validation, dove una parte del campione di osservazione viene iterativamente rimossa dall’insieme di addestramento, e i risultati relativi a quella parte elaborati dal campione di addestramento vengono validati con i dati reali.

Anche nella gestione dei vincoli la computer science offre spunti interessanti: dato un problema con chiari vincoli – come la disposizione degli invitati ad un matrimonio su diversi tavoli, o il calendario di una stagione sportiva – i ricercatori applicano due tecniche di relaxation – constraint relaxation e Lagrangian relaxation: il primo criterio permette di rimuovere alcuni dei vincoli presenti nel problema originario, e provare ad ottimizzare la situazione per il secondo problema, più facile di quello iniziale: una volta risolto il secondo, quest’ultimo potrebbe suggerire come muoversi per risolvere anche il primo. La seconda versione, Lagrangian relaxation, ipotizza di verificare le conseguenze di ogni vincolo proposto per il problema iniziale, valutarne le conseguenze, e realizzare una soluzione ottimale tenendo in considerazione anche le penalità imposte dal mancato rispetto di alcuni dei vincoli proposti (in ordine crescente di importanza).

Per gestire la casualità, il modo migliore è partire dalle operazioni di campionamento, e di simulare i comportamenti che si vogliono studiare, mentre per le connessioni e il comportamento umano, la teoria dei giochi e il design di meccanismi di interazione possono essere utili per incentivare il comportamento desiderato.