Domande esame finale Business intelligence e big data m

1. Reti neurali convoluzionali – meccanismo di funzionamento, possibili

applicazioni

Le reti neurali convoluzionali sono un particolare tipo di rete neurale che

gestisce dati con topologia a griglia su 1 o più dimensioni.

La chiave della CNN è l’operazione matematica chiamata convoluzione, ovvero

un prodotto scalare seguito da una somma; Se i dati sono disposti a griglia, in

generale la moltiplicazione tra matrici non è necessaria ad ogni livello della

rete.

Questo strumento è basato sul filtro convoluzionale, cioè una matrice quadrata

FxF di pesi chiamata “tensore” da applicare sull’immagine per eseguire

convoluzioni. Questo filtro si sposta sull’immagine con un passo S detto Stride e

deve ricoprire l’intera immagine di dimensioni WxH.

La larghezza e l’altezza della matrice viene sottratta alle dimensioni

dell’immagine facendo in modo che, dividendo per il passo S, si ottenga un

numero intero altrimenti non riusciamo a coprire tutta l'immagine con lo stride.

Nel caso non fosse così si deve utilizzare lo zero padding che consiste nella

aggiunta di zeri lungo il bordo dell’immagine per consentire le convoluzioni su

tutti i pixel.

Le CNN hanno 3 caratteristiche principali:

● Interazioni sparse: si hanno un numero inferiore di connessioni tra i

neuroni della rete rispetto ad una tradizionale dove ogni neurone è

collegato a tutti i neuroni degli strati adiacenti. Da ciò deriva una

maggiore efficienza, numero minore di parametri e requisiti di memoria

ridotti.

● Condivisione dei parametri: si riferisce all'utilizzo dello stesso parametro

per più di una funzione in un modello. Nelle reti tradizionali ogni elemento

della matrice dei pesi viene utilizzato esattamente una volta quando si

calcola l'output di un livello mentre in una CNN ogni membro del kernel è

utilizzato in ogni posizione dell'input.

Il costo della propagazione in avanti della CNN è kxn dove K= dim filtro

(3*3=9) e

n= larghezza dell'immagine risulta nettamente inferiore al costo della

propagazione di una rete densa di tipo tradizionale dove il costo è uguale

a nxm con m=altezza dell'immagine (k<<m). La convoluzione è quindi

notevolmente più efficiente di moltiplicazione di matrici dense in termini

di memoria requisiti ed efficienza statistica perché nello stesso tempo

permette di aggiornare i pesi molte più volte e quindi di trovare dei

parametri migliori.

● Rappresentazione equivalente (equivarianza): la particolare forma di

condivisione dei parametri fa sì che il livello abbia una proprietà chiamata

equivarianza alla traslazione. Vuol dire che una funzione f(x) è

equivariante a g se f(g(x))=g(f(x)), ovvero se l’input cambia l’output

cambia dello stesso ordine di grandezza. La convoluzione non è

equivariante a rotazioni o cambiamenti di scala, ciò significa che la rete

fa difficoltà a riconoscere immagini inquadrate non frontalmente.

La convoluzione all’interno della rete viene eseguita in tre fasi distinte che

sono CONVOLUTION STAGE, DETECTOR STAGE e POOLING STAGE.

Quest’ultima ha il compito di comprimere l’info e calcolare il v.medio o il min

e max.

L’utilizzo di questa rete è svariato e consiste riconoscimento, classificazione,

previsione ed analisi di serie temporali, audio, immagini, video.

2. Vincoli reificati

Al presentarsi dei problemi di ottimizzazione con necessità di assegnazione di

variabili tra elementi di due insiemi si hanno di fronte tre strade: le prime due

consistono nell’assegnare le variabili ad uno dei due insieme e i valori all’altro,

la terza opzione cioè il modello binario invece consiste nell’assegnare le variabili

ad ogni possibile collegamento tra gli elementi dei due insiemi. Quest’ultimo

presenta dei problemi in quanto la formulazione del problema non è compatta e

la propagazione dei vincoli potrebbe essere debole.

Per superare questi limiti si trattano i vincoli come espressioni, un vincolo

reificato è un espressione che corrisponde allo stato di fattibilità di un vincolo.

Essenzialmente, otteniamo il potere i materializzare le variabili binarie. Per fare

ciò abbiamo bisogno di una nozione di consistenza e di un algoritmo di

filtraggio.

La Generalise Arc Concistency dice che il domicio D(c) è sempre o 0 o 1. Si

assegna 1 se c è soddisfacibile, 0 altrimenti. Successivamente filtrando c, se

otteniamo un dominio da cui sono stati eliminati tutti i valori abbiamo che

1/=D(c), mentre se 0/=D(c) allora c è un vincolo risolto, tutti i suoi

assegnamenti sono soddisfacibili.

Il metavincolo è un vincolo sui vincoli reificati, sono strumenti molto potenti ma

hanno dei difetti in quanto possono complicare i modelli e farli crescere di

dimensione ed anche il tempo di filtraggio èmaggiore, nonché porta ad un

filtraggio debole.

3. Empirical Model Learning – concetti base e applicazioni

È una tecnica avanzata e recente che è stata usata per casi reali non banali. Si

usa generalmente quando si devono risolvere problemi complessi, come ad

esempio la gestione dei semafori in una città trafficata.

Un problema diventa complesso quando non riusciamo a modellare il nostro

problema in funzione di un tipo di variabili che hanno un altro tipo di variabile al

loro interno, cioè non riusciamo ad esprimere in maniera analitica la

correlazione fra un sottoinsieme di variabili decisionali e un sottoinsieme di

variabili osservabili.

Una volta che si hanno i dati (storici o generati tramite un simulatore), EML

cerca di apprendere dei problemi di machine learning basandosi su

osservazioni. Il modello deve poi essere inserito in un sistema combinatorio

(problema di ottimizzazione) in cui c’è una funzione obiettivo da

minimizzare/massimizzare, dei vincoli da rispettare e un vincolo espresso da

una funzione che lega le variabili decisionali alle variabili osservabili.

EML= problema combinatorio+modello ML. Seppur i modelli ML siano

approssimati possono dare stime di accuratezza.

C’è una differenza fondamentale tra modelli ML e EML:

Negli ML si hanno variabili in ingresso che entrano dentro al modello ML, questo

fa le sue considerazioni e da in uscita l’output. Nell’EML c’è una retroazione:

(oltre al funzionamento normale del modello come nel ML) il modello ML viene

trasformato in un vincolo del problema stesso ed è possibile utilizzarlo per fare il

pruning di possibili domini. Propago la conoscenza all’indietro per impattare il

dominio delle variabili decisionali. Ci sono due modi per integrare il ML nel

problema combinatorio:

● Con le reti neurali NN: Implicitamente, le NN (neural networks) sono

modelli dichiarativi. Il neurone artificiale è rappresentato da delle

computazioni analiticamente esprimibili quindi il neurone potrebbe essere

rappresentato come un problema combinatorio. Occorre capire quali sono

gli ingressi e le uscite del ML, codificarle come variabili, codificare i vincoli

e inserire le equazioni non lineari NN (funzione di attivazione) nel

modello.

Si ricorre al vincolo globale ACT.FUNCTION ( [X], Y, [W], B) dove X sono gli

input, Y gli output, W i pesi e B i bias mentre la funzione di attivazione

viene approssimata come un insieme di funzioni lineari a tratti.

Il filtraggio e il pruning si possono fare anche con il vincolo globale

neuronale. È possibile fare filtraggio da x a y ma anche da y a x (e quindi

fare in modo che modifiche all’ingresso provochino modifiche all’uscita

ma anche viceversa!! → retroazione).

● Alberi decisionali : Un albero decisionale può avere vari attributi di diversi

tipi (numerici, simbolici…) ed è composto da diversi nodi. Nei nodi si fa

uno splitting in base a un particolare attributo e nelle foglie si hanno

valori che sono classi o valori predetti. Per inserire un albero decisionale

dento un modello combinatorio si inserisce una variabile decisionale per

ogni attributo (A,B,C), si inserisce una variabile decisionale per la

classe(Y), infine si impone consistenza su: Y=DT(A,B,C).

Il percorso dentro l’albero è un’implicazione logica (AND). Questa è la

chiave per considerare l’albero decisionale un modello matematico. Si

devono sommare tutti i possibili percorsi dell’albero per scrivere in modo

completo i vincoli reificati che possono poi essere reintrodotti in un

problema di ottimizzazione a vincoli (anche se così non ho consistenza

globale). Una volta che l’albero è stato addestrato conosco i valori e

quindi passare dalla rappresentazione grafica a quella analitica

rappresentabile come programmazione a vincoli. Gli attributi continui

possono essere discretizzati utilizzando le soglie visualizzate nell'albero

(devo però discretizzare gli attributi numerici!).

Una considerazione non così scontata: non è detto che utilizzare modelli ML

accurati sia la cosa migliore.

L’accuratezza può essere controproducente perché implica complessità, cioè

aumenta il numero di variabili e di vincoli; inserito nel modello, a parità di

tempo, si avrà un numero minore di soluzioni possibili. Quindi è giusto

considerare un compromesso tra utilità e precisione.

4. Scheduling e allocazione di risorse con programmazione a vincoli

Una delle aree in cui la CP è utilizzata più volte sono i problemi di scheduling

(problema di pianificazione del progetto con risorse limitate, RCPSP).

Il problema di scheduling consiste nel determinare quali risorse allocare a quali

attività e quando svolgerle. Scheduling e allocazione sono problemi

storicamente affrontati con la ricerca operativa. In generale quando dobbiamo

decidere quando eseguire un insieme di attività dobbiamo introdurre la

dinamica temporale. Si devono introdurre variabili che indicano il tempo. Questo

richiede di discretizzare il tempo in qualche modo, più vado nel dettaglio del

tempo più esplode il numero di variabili che devono essere coinvolte.

Applicazioni: progetti di costruzione su larga scala, progetti di ricerca/sviluppo,

piano di produzione, ottimizzazione software parallela, ottimizzazione del

codice.

Per risolvere il problema come un CP, vado a introdurre variabili S che indicano

l’inizio dell’attività:

Si[0…Eoh]

dove Eoh è un vincolo superiore sicuro (End of Horizion) che indica quando AL

MASSIMO l’attività può finire.

Viene calcolato sommando tutte le durate delle attività che devono essere fatte

precedentemente. Viene usato perché non è sempre facile avere i domini

ristretti, anche se a volte i domini 0-Eoh possono essere larghi. Esiste sempre un

programma con un makespan ≤ eoh. A meno che i vincoli sulle risorse non

ammettano soluzione.

La modellazione più standard della funzione obiettivo è la makespan = tempo di

completamento del progetto = end time dell’ultima attività. Vado a considerare

tutte le mie attività e in particolare il loro momento di completamento. Voglio

minimizzare il massimo delle attività di completamento. Introduco variabile Z su

cui far propagazione:

min Z = massimo tempo di completamento di tutte le attività. (max si+di)

Vincoli:

- Vincoli di precedenza si+di<=sj (se esiste una relazione di precedenza tra le

attività i e j):

- Vincoli sulle risorse. Se Ck = 1 allora le attività non possono sovrapporsi. Ogni

1 attività 1 risorsa. Quindi uso vincoli binari che indicano praticamente che una

attività deve seguire l’altra.

si+di<=sj oppure sj+dj<=si

Se Ck > 1 diventa più complicato trovare un buon modello: o introduco un

vincolo di somma per ogni punto temporale o vincolo di somma per ogni inizio

di attività. Entrambi sono complicati e portano a una debole propagazione.

L’alternativa è usare un vincolo globale per considerare insieme capacità e

tempo.

Il cumulative impone consistenza su tutti gli istanti e su tutte le attività per

controllare che la capacità delle risorse non venga superata. Il filtraggio è però

NP-difficile. Il vincolo CUMULATIVE è NP-hard.

5. Programmazione a vincoli – modellazione e strategie di ricerca

L’obiettivo è ridurre al minimo il makespan, cioè il tempo di completamento

dell’attività. Quindi selezionare una posizione iniziale del cursore dell’attività SEi

sembra una buona idea. Come selezioniamo la variabile su cui fare branching?

Un criterio ragionevole è scegliere quella con SEi più piccolo. Pe risolvere i

pareggi posso andare a vedere l’LET minore, ovvero il più piccolo dei ritardi

possibili per quando far finire l’attività in base al momento d'inizio.

Quindi, faccio partire l’attività con SEi minore e l’intera durata dell’attività

diventa obbligatoria. A questo punto, devo propagare sia i vincoli di precedenza

che i vincoli cumulative. Seleziono la prossima variabile da far partire, la

schedulo e propago i vincoli. Se ho stesso LET posso scegliere in base all’indice.

Il processo viene ripetuto fino a quando tutte le variabili sono state assegnate.

In questo modo ottengo uno schedule.

Questo processo è un famoso approccio euristico greedy che si chiama

pianificazione basata su regole di priorità (PRB scheduling). Funziona bene in

molti casi.

Gli schedule ottenuti con PRB possono essere sub-ottimi. Per fare soluzioni

ottime, è necessario fare ricerca e backtracking e quindi tornare al punto di

partenza. Visto che la scelta iniziale della soluzione subottima è stata s1=0

posso mettere vincolo opposto s1=! 0 ma è debole, non propagherebbe bene,

infatti se arrivasse in fondo scoprirei che anche quello non porterebbe ad una

soluzione ottima.

C’è un metodo più intelligente: contrassegnare l’attività Si come posticipata.

Non è possibile selezionare un’attività posticipata per il branching finchè il suo

valore SEi non cambia. Questo al fine di non far ottenere una soluzione di

braching diversa quindi faccio sempre partire le attività al loro SEi e la decisione

di scheduling cambia quando SEi viene modificato. Ciò avviene tramite

propagazione e filtraggio anche su quella attività.

La strategia ha un nome particolare, si chiama SetTimes. Le idee principali sono

posticipare le attività, scegliere sempre un’attività con il minimo SEi e far

iniziare le attività in corrispondenza del loro SEi. Implicitamente fa scelte di

coordinamento. In genere è una strategia molto efficace. Tecnicamente però è

una strategia incompleta perché nei punti di scelta non si vedono tutte le

possibili alternative (non partizioniamo lo spazio di ricerca). O facciamo iniziare

un’attività a SEi o la facciamo aspettare. Con domini molto grandi ci vorrebbe

troppo tempo. Ci sono casi in cui il SetTimes non funziona, ad esempio se la

funzione di costo non è regolare e c’è una penalità associata a far partire troppo

presto una attività o altri vincoli collaterali che alterano la struttura del

problema.

6. Programmazione a vincoli – tipologie di vincoli e algoritmi di filtraggio (è

possibile sia discutere di multipli algoritmi sia andare a fondo nel dettaglio di un

particolare algoritmo, a discrezione del candidato)

Nella programmazione a vincoli ne esistono vari tra cui il vincolo cumulative.

Esso viene formalizzato come un vincolo globale nella forma:

Il suo utilizzo è consigliabile quando è possibile modificare il tempo delle

attività.

Esso pone consistenza sul fatto che la quantità richiesta sia sempre inferiore o

uguale alla capacità.

Tale consistenza pone un controllo sulla fattibilità di Si. Il cumulative è NP-hand,

una diretta conseguenza di ciò è che il filtraggio su di esso non risulta ottimale.

Alcuni algoritmi di filtraggio per CUMULATIVE :

– Filtraggio disgiuntivo

– Filtraggio basato su timetable (orari)

– Ricerca dei margini (edge-finder)

– Regole not-first/not-last

– Edge-finding timetable

– Ragionamento energetico

Per quanto riguarda il timetable, esso si basa sull’idea di fare affidamento su un

profilo di utilizzo minimo. Si va a calcolare il profilo di utilizzo minimo delle

risorse: il consumo di risorsa minimo per ogni istante di tempo. il profilo viene

usato per determinare i limiti delle variabili Si.

Nomenclature: ESTi = prima partenza possibile

dell’attività EETi = pima fine possibile della

mia attività LSTi = ultima partenza possibile

della mia attività LETi = ultima fine possibile della

mia attività

Se abbiamo che LSTi < EETi: abbiamo un intervallo temporale in cui

necessariamente l’attività verrà eseguita = ai. A prescindere di quando io cerchi

di spostare la mia attività sicuramente in quell’intervallo la mia attività deve

essere eseguita.

Se aggreghiamo tutte le parti obbligatorie otteniamo il profilo di utilizzo, come

ad esempio:

Per ogni istante temporale dovrò cercare l’utilizzo minimo garantito dalle

risorse.

Quindi, per ogni attività i: -Perlustrazione della linea temporale (timeline sweep:

SWEEP è anche il nome del propagatore) -Ricerca dell’orario di inizo adatto

-Aggiornamento del dominio di Si di conseguenza.

Esempio filtraggio di una singola attività Ai

Mantengo un cursore per la linea temporale la cui posizione iniziale è SEi

(earliest start time). Controllo se è disponibile una capacità sufficiente. In caso

positivo, il cursore passa alla modalità di controllo e memorizzo la posizione

corrente del cursore in una variabile S*. In modalità di controllo, testo se S* è un

momento di inizio valido → questo è vero se c’è abbastanza capacità

nell’intervallo [s* , s*+di[ Pertanto, continuo a controllare finchè non raggiungo

s* + di. In modalità di controllo, ci spostiamo solo tra Latest Start Times perché

le parti obbligatorie iniziano solo presso gli LST, quindi l’utilizzo delle risorse può

aumentare solo a LST.

Se il filtraggio non è sufficiente, passiamo alla modalità ricerca. In modalità

controllo abbiamo concluso che s* non è un inizio valido. Quindi ora cerchiamo

un’altra ora di inizio candidata. In modalità di ricerca, ci muoviamo solo tra gli

EET (early end time) perché le parti obbligatorie terminano agli EET quindi

l’utilizzo delle risorse può diminuire solo negli EET.

Se c’è capacità sufficiente passiamo alla modalità di controllo. Memorizziamo la

posizione corrente del cursore in una variabile s* e controlliamo nell’intervallo

[s* , s*+di[ In modalità di controllo la perlustrazione può procedere fino a sLi

+di. Ad un certo punto raggiungiamo s* +di durante la modalità di controllo →

possiamo rimuovere D(Si) imponendo s* come ESTi.

Se in qualche momento durante la modalità di ricerca superiamo SLi possiamo

falliire immediatamente.

Possiamo quantificare la sua complessità? I limiti superiori delle variabili iniziali

possonoesserecalcolati in modo simile. Il profilo può essere calcolato in O(n

logn). Approccio: ordina e poi scansiona. Lo sweep (perlustrazione) ha una

complessitàO(n). Dobbiamo filtrare n attività. Nel complesso, l'algoritmo ha

complessità O(n^2).

Altri metodi di filtraggio: edge finder, ragionamento energetico, timetable edge

finding.

Ottimizzazione degli iperparametri – strategie e metodi

I modelli di Deep Learning (DL) e Machine Learning(ML) sono composti da due

diversi tipi di parametri:

• Parametri del modello: appresi durante l'addestramento del modello (ad

esempio, i pesi e la distorsione di una rete neurale)

• Iperparametri: l'insieme di parametri arbitrari che possono essere impostati

dagli utenti prima dell'allenamento (ad esempio, numero di strati di neuroni in

una rete neurale) Determinano come è strutturato il nostro modello.

L’ottimizzazione degli iperparametri è un tipo di problema di ottimizzazione. Ci

sono delle tecniche ma è ancora un problema aperto.

In generale, i dati del dataset vengono utilizzati in parte per il training (70% -

training set), in parte per trovare il valore corretto degli iperparametri

(validation set) e in parte per testare il modello (test set). Il validation set serve

per esplorare diverse configurazioni di iperparametri in modo da trovare la

migliore.

Il problema è complicato anche perchè deve essere fatto in un tempo adeguato.

Per valutare l’efficienza del fine tuning occorre considerare:

- Efficienza hardware: misura il costo dei sistemi per eseguire un singolo

aggiornamento

- Efficienza statistica: misura di quanti aggiornamenti abbiamo bisogno per

ottenere una risposta della qualità che vogliamo

Esistono diverse strategie per la messa a punto degli iperparametri:

- Ricerca manuale

- A griglia

- Casuale

- Ottimizzazione automatica

Ricerca Manuale: si basa sull'esperienza del professionista ML e/o sulla

conoscenza del dominio. I valori degli iperparametri vengono selezionati

mediante regolazione manuale, ovvero scegliendo v