Categoria: blog

Premessa

Questo articolo nasce dagli appunti del mio “diario di bordo” riguardo la mia più nuova e recente avventura nel mondo dei Game Engine e di conseguenza ne erediterà la scrittura caratteristica personale. In fin dei conti penso che almeno una volta nella vita di tutti gli sviluppatori è nata quella voglia di creare e plasmare forme di intrattenimento con il loro codice, e non soltanto di muovere qualche finestra/container e riempirlo di campi, pulsanti e tanta altra roba noiosa.

L’articolo si compone di due macro-parti:

  • Introduzione al Game Engine GODOT
  • Esempio pratico della realizzazione di un gioco 2D
  •  

Non peccherò di superbia, poiché essendo un novello dell’ambiente il mio codice e le mie tecniche potrebbero far storcere il naso ai più skillati in materia. Ma per me il tutto funziona come dovrebbe, il codice è leggibile e soprattutto adoro il pensiero del “less is more”.

 Insomma, le porzioni di codice che incontreremo più avanti sono state fatte DA e PER uno sviluppatore che muove i primi passi con questo Game Engine, rimanendo tuttavia una solida base per studi ed espansioni personali.

Introducing GODOT

Le circostanze del mio avvicinamento a GODOT sono al quanto bizzare…

Da avido utilizzatore della piattaforma/forum Reddit, sono solito frequentare categorie tecniche relative alla programmazione, all’hardware e assemblaggio di PC ed al PC Gaming in generale.

Il caldo insopportabile di quest’anno (2022) legato alla cappa costante tipica romana hanno in quel periodo fatto nuovamente tornare alla mia mente la voglia di approcciarmi per una volta e seriamente ad un motore di sviluppo di giochi.

Ed ecco il punto di svolta, nella categoria dello sviluppo gaming di Reddit leggo in alcuni post di un nuovo nome, a me completamente sconosciuto: GODOT. Incuriosito decido di andare a dare uno sguardo alla sua community, la cui attività è spesso e volentieri un buon indice di prima valutazione per qualsiasi prodotto informatico/framework.

Ebbene, mentre i colossi competitor nel mondo del Game Engine (Unreal Engine e Unity) rilasciavano le loro nuove major release con features spaziali e le rispettive community portavano avanti discussioni su possibili miglioramenti, nuove strategie, fix per le performance…la community di GODOT sfornava nell’80%+ dei propri post questo:

“Godette”. La mia prima reazione è stata ovviamente che “ogni giorno ci allontaniamo sempre di più da Dio”. Siamo dunque SICURAMENTE davanti ad un prodotto che o è estremamente nuovo ed è ancora alla ricerca di una sua identità/logo/mascotte oppure che non ha al momento problemi tecnici più seri di cui dover discutere…

Nonostante tutto rimango colpito da una sua tanto proclamata caratteristica: questo motore è LIGHT, leggero, performante, anche su macchine meno recenti.  Vi basti pensare che l’intero motore è racchiuso in unico download da ~70MB. Ed io che in quel momento a casa avevo soltanto tra le mani un vecchio portatile i3/4GB RAM del 2011 ho voluto mettere alla prova questa loro tanto decantata feature.

Mentre il mio povero laptop crashava per surriscaldamento al solo sussurro delle parole Unreal e Unity, ecco che scarico, lancio l’eseguibile ed avvio GODOT nel giro di pochi secondi, al limite del miracolo. Riuscendo a sopportare una prima ora di smanettamenti caotici senza crash, decido che questo prodigioso game engine sarebbe stato mio compagno per questa mia prima impresa.

Breve Panoramica

  • Prima release pubblica nel 2014
  • Autori Argentini Juan Linietsky e Ariel Manzur
  • Free (MIT License)
  • Open Source (https://github.com/godotengine/godot)
  • Cross Platform (Windows, Linux, macOS, …)
  • 2D/3D/VR e Cross Platform (Desktop, Mobile, Web)
  • Ultima Versione stabile 3.5 (di Agosto 2022)

SA questo punto che son state fatte le prime presentazioni mi piace fare un gioco di persuasione inverso…Sarebbe semplice entrare nel dettaglio del cosa rende GODOT unico e migliore rispetto ai competitors ma questa volta preferire cominciare dal punto di vista contrario.

  • La maggior parte delle offerte di lavoro si basano ancora su Unity e Unreal Engine

  • Impossibilità di esportare per le piattaforme console, o almeno non senza cacciar fuori qualche soldo :'(

  • Lo store degli assets in GODOT offre soltanto elementi gratuiti
    (a discapito della loro qualità)

  • Nei giochi 3D le performance non sono delle migliori…

  • E’ un motore “giovane”, quindi con minori risorse e materiale online da cui attingere come riferimento/studio

Insomma, uno scenario abbastanza pesante e negativo, ma se ci pensate bene qualunque framework ed engine ha pur iniziato da qualche parte, ed in prospettiva, le feature sviluppate e a disposizione su GODOT nel giro di 8 anni dalla sua prima release sono di gran lunga superiori per numero e qualità a quelle dei due big brothers UE e Unity.

Se ancora non vi ho scoraggiato direi possiamo proseguire con una lista più rosea e positiva.

  • Ripeto: è FREE, e non prende commissioni sui giochi realizzati
  • LIGHT: con i suoi 70MB di eseguibile, GODOT probabilmente potrebbe girare anche sul forno a microonde di casa (assieme a Doom ovviamente)
  • Open Source con un attività esponenzialmente crescente
  • Beginner-friendly (sia grazie all’UI intuitiva che alla semplicità del suo linguaggio GDScript
  • Ottima documentazione (Link)
  • Alta riusabilità degli elementi/codice

Tornando a noi ho deciso di non includere un’altra feature tanto decantata in questa lista, ovvero la possibilità di usare il C# al posto del proprietario GDScript. Il motivo è semplice la versione 3 è stata la prima a supportare anche il C#, sicuramente con una base di sviluppatori già affermata nel mondo professionale, ma la sua implementazione nell’engine è a mio parere ancora acerba ed incompleta.

Ma non disperate, la sua finalizzazione in GODOT avverrà con enorme probabilità con il rilascio della versione 4, già in sviluppo parallelo alle 3 da quasi due anni. Tuttavia, trascorse queste prime settimane con l’engine posso affermare di non essermi trovato affatto male con il linguaggio proprietario GDScript: con una sintassi simile a Python, parliamo di un linguaggio di alto livello semplice ed immediato, ottimizzato per il motore. Mentre nei miei scarsi tentativi con C# mi son presto reso conto che il micromanagement necessario per una corretta gestione delle risorse uccideva completamente il mio tempo e la perfomance dei miei prodotti.

Altra feature che ho volontariamente omesso nella lista dei vantaggi è la possibilità di sviluppare usando la modalità Visual Scripting, già presente su Unreal Engine (Flow Control).

Diciamo semplicemente che questa roba non fa per me, o comunque immagino che qualsiasi sviluppatore anche junior potrebbe scrivere e mantenere del codice in GODOT molto meglio di quanto prodotto dallo strumento di Visual Scripting.

Feature simpatica, sicuramente una risposta diretta al Flow Control di UE e rivolta ad un pubblico che ancora si deve affacciare al mondo della programmazione, ma ci vuole davvero poco per rendersi indipendenti ed autonomi, passando direttamente all’editor classico di codice.

Struttura a Nodi & Scene

Anche un neofita come me apprezzerà l’altissima riusabilità e gestione delle risorse dovute all’ingegnoso sistema a nodi e scene di GODOT:

  • In GODOT un gioco può essere visto come un ALBERO di SCENE

  • Ed ogni SCENA è paragonabile ad un ALBERO di NODI

  • I NODI sono l’unità fondamentale e più piccola dei nostri giochi

  • Ci sono tantissimi NODI in GODOT specializzati in precise funzioni (musica, suoni, animazione, pulsanti, collisioni, …)

  • Un gruppo di NODI può essere infine salvato come SCENA per essere facilmente riutilizzato in…altre SCENE

Ed ora…lo creiamo o no questo giochino?

Mi rendo conto solo dopo svariati tentativi che mettere per iscritto una cosa così VISIVA come l’uso di un game engine sia davvero un’ardua impresa.

Di seguito cercherò di mostrarvi e descrivervi tutte le schermate che ci porteranno alla creazione di un giochino alla Flappy Bird (link video per chi non lo conoscesse). Poiché non sarà possibile descrivere ogni singolo incremento del codice ho deciso di mostrarvi fin dal principio l’intera scaletta del nostro sviluppo per poi entrare nel dettaglio di tutte le maggiori entità.

Ecco dunque di seguito le risorse che vi metto a disposizione:

Scaletta “Floppy Bird”

  • MenuNode con button START e CAMERA
  • WorldNode con button BACK e CAMERA
  • PlayerNode (sprite, collision) e aggiungiamolo al WorldNode
  • PlayerNode (gravity)
  • PlayerNode (FLAP)
  • WallNode (sprite, collision, movement) e aggiungiamolo al WorldNode
  • Arriviamo fino a 5 WallNode
  • Integriamo la logica di collisione del PlayerNode col body del WallNode
  • Creiamo la classe GLOBALE “Globals.gd” e aggiungiamola all’ AUTO LOAD del progetto
  • Aggiungiamo la PointArea al WallNod
  • Integriamo la logica di collisione del PlayerNode con la PointArea del WallNode
  • Mostriamo i vari score durante la partita con una Label
  • Quando muoio, salvo eventualmente il BEST SCORE
  • Creiamo una “reset area” per riposizionare e creare un loop di muri
  • Salviamo l’eventuale best score in un file quando moriamo
  • Quando si auto carica GLOBALS.gd leggiamo il best score nel file
  • A questo punto aggiungiamo il BEST SCORE anche nel menu iniziale
  • Aggiungiamo una fonte di luce (Light2D) al WorldNode
  • Aggiungiamo degli occlusori di luce al nostro WallNode
  • Cambio dello sprite del player con un ANIMATED SPRITE flying bird
  • ANIMATED SPRITE Infuocata quando supero il best score
  • MovingWall

Globals.gd (scritp)

Script nella root del progetto. Conterrà i nostri elementi “globali” come ad esempio lo score attuale ed il best score. Per essere caricato automaticamente all’avvio del gioco dovremo impostarlo nella sezione AutoLoad del progetto

Come ultimo passaggio per completare il grafo di esempio che vogliamo riprodurre ho creato e popolato in modo del tutto analogo anche la tabella arco che rappresenta il legame tra due persone, chiamata AmicoDi ovvero un arco che collega la tabella Persone a sé stessa (stavolta senza attributi).

A questo punto abbiamo ricreato esattamente la struttura che volevamo, e possiamo eseguire qualche query per renderci conto di come estrarre informazioni dal sistema appena costruito.

StartMenuNode.tscn (SCENA)CH

Scena aggiunta alla folder “scenarios”. Leggerà da un file il best score registrato (letto da Globals) ed il pulsante start ci porterà al vero e proprio gioco. Di seguito lo script associato alla scena e che regola i suddetti comportamenti.

StartMenuNode.gd (script)

WallNode.tscn (SCENA)

La scena del nostro muro è posizionata nella folder entities e si compone di 3 parti: porzione superiore, porzione inferiore del muro (il contatto col player indicherà il fine/reset partita) e l’area centrale denominata PointArea. Il player che entra in una PointArea incrementerà il suo punteggio di 1. Il muro dovrà muoversi a velocità costante verso la parte sinistra dello schermo, mentre il giocatore potrà “volare” verticalmente rimanendo sempre al centro.

WallBody.gd (script)

PlayerNode.tscn (SCENA)

La scena del nostro player è posizionata nella folder entities ed è formato principalmente da un corpo principale (con sprite), un’area leggermente più grande di lui per registrare le collisioni ed un’eventuale sprite animata che si attiva al superamento del best score. Il player viene sempre attirato giù da una costante gravità e l’unico modo che avrà di volare sarà quello di sbattere le ali premendo il comando FLAP che legheremo al pulsante spazio nelle impostazioni di progetto.

PlayerBody.gd (script)

WorldNode.tscn (SCENA)

La scena del nostro mostro di gioco è posizionata nella folder scenarios.

Gli elementi che la compongono saranno il player, delle copie di muri statici, un muro mobile, un’area di reset dei muri (per riportali a sinistra senza generarne di nuovi all’infinito) ed un pulsante per tornare al menù iniziale. Immancabile ovviamente la label a centro schermo per indicare i vari score.

WorldNode.gd (script)

Che aspettate? Premete F5 per avviare la compilazione del tutto ed avviare la vostra personalissima copia di Floppy Bird!

Articolo a cura di Luca Cerini, Senior Developer in Orbyta Tech, 23/08/2022

#jointherevolution

Introduzione

Molti di voi probabilmente conosceranno già il concetto di database a grafo, un’alternativa al classico modello di database relazionale che risulta particolarmente efficiente quando si ha a che fare con delle relazioni complesse, mutevoli e gerarchicamente strutturate tra le entità, come potrebbero essere i dati tipici di un social media. L’aspetto forse un po’ meno noto è che anche Management Studio, dalla sua versione del 2017, supporta la creazione di un DB a grafo completamente integrato nel SQL Engine, nonostante da tempo già ci fossero delle soluzioni che in qualche modo cercavano mimarne il comportamento, come le CTE ricorsive o il tipo HierarchyId.

In un DB relazionale abbiamo righe, tabelle, chiavi esterne e relazioni, mentre le entità tipiche del DB a grafo sono note come nodi (nodes) e archi (edges). Mentre i nodi non sono dissimili dal concetto di tabella come la potremmo incontrare in un normale DB, l’entità più interessante sono proprio gli archi, delle specie di relazioni “arricchite” che definiscono il rapporto tra i nodi e che sono contraddistinte a loro volta da attributi e proprietà. Per usare una definizione intuitiva, anche se non troppo precisa, possiamo considerare i nodi come “oggetti” (prodotti, luoghi, clienti etc.), e gli archi come “azioni” (vive a, comprato a, lavora per).

Ecco un esempio di DB a grafo molto semplice ma che rende già l’idea

La peculiarità del DB a grafo è proprio la possibilità di associare degli attributi direttamente alla relazione (cioè all’arco), che in questo modo supera il suo semplice compito di mettere in rapporto una tabella con un’altra, diventando dato essa stessa. Sfruttando questa struttura possiamo scrivere delle query dall’aspetto molto sintetico, che utilizzando un DB relazionale sarebbero estremamente più complesse e di difficile lettura. Grazie alle peculiarità del DB a grafo potremo tradurre in poche righe di codice interrogazioni come questa: “Trova tutte le persone nate a Torino nel 1990 che hanno valutato 5 stelle il McDonald di piazza dell’VIII Agosto di Bologna e hanno un amico, tifoso dei Los Angeles Lakers, che vive a Cagliari”.

Un esempio pratico

Non c’è cosa migliore per entrare nel vivo della questione che vedere un esempio pratico e cominciare a fare qualche prova. Se creiamo su SSMS un nuovo database ed espandiamo il menu delle tabelle, possiamo notare la presenza dell’entità Graph Tables, sotto alla quale troveremo tutte le tabelle create nel perimetro del nostro DB a grafo (il che comprende sia i nodi sia gli archi).

Per questo esempio prenderemo in considerazione una porzione ridotta del diagramma mostrato all’inizio dell’articolo, ovvero quella che coinvolge i soli nodi Persone e Ristoranti (con relativi archi); questo esempio, per quanto semplice, ci permetterà già di indagare diversi aspetti interessanti di questa funzionalità di SSMS.

Creiamo e popoliamo le entità nodi

Come prima entità creiamo una tabella nodo, in tutto e per tutto simile alla creazione di una classica tabella, se non fosse per l’aggiunta finale della dicitura “AS NODE”.

L’inserimento dei dati in questa tabella è invece del tutto indistinguibile dalla classica insert che potremmo eseguire per popolare una tabella normale.

Se eseguiamo una semplice SELECT * della tabella appena creata, possiamo già notare una prima differenza rispetto ad una tabella classica: le tabelle di tipo nodo vengono difatti equipaggiate con una colonna aggiuntiva generata automaticamente, chiamata $node_id (seguito da una stringa esadecimale).

Si tratta di una pseudo colonna utilizzabile nelle query, ed è possibile interrogarla anche omettendo la parte esadecimale, come possiamo notare nell’esempio seguente.

Il contenuto di questa particolare colonna è un JSON (anche questo generato automaticamente) che ci servirà per creare gli archi che connetteranno due tabelle nodo tra loro.

Creiamo e popoliamo allo stesso modo la tabella nodo “Ristoranti”, di cui per brevità vi mostro solo l’aspetto finale

Creiamo e popoliamo le entità archi

La sintassi per la creazione di un arco è identica alla creazione delle tabelle nodo, con la differenza che la specifica “AS NODE” sarà sostituita da “AS EDGE”

Questa relazione, che mette in rapporto le persone con i ristoranti, annovera tra i suoi attributi la valutazione che ciascuna persona ha espresso nei confronti di quel ristorante. Possiamo quindi visualizzare questa relazione tra due dati di esempio come

dove le ellissi sono i dati ospitati nei nodi Persone e Ristoranti, il connettore è la relazione rappresentata dall’arco AmaMangiareDa, e la parola tra parentesi quadre è l’attributo “Valutazione” dell’arco stesso, come lo abbiamo definito nel passaggio precedente.

Finora non abbiamo ancora collegato tra loro in nessun modo le persone e i ristoranti, quindi il prossimo passaggio consisterà nell’aggiungere dati alla tabella arco in questo modo:

Così facendo ho recuperato un record dalla tabella delle persone ovvero “Franz Liszt”, un record dalla tabella dei ristoranti, ovvero “Osteria Francescana”, e ho aggiunto la valutazione di cinque stelle che Franz Liszt ha assegnato a tale ristorante.

Se proviamo adesso ad interrogare la tabella appena popolata, otteniamo questo risultato

Esattamente come era avvenuto per le tabelle nodo, viene aggiunta automaticamente una colonna contenente un JSON, chiamata $edge_id. Possiamo anche notare la presenza delle due colonne che puntano ai nodi collegati da questo arco (praticamente delle chiavi esterne), una riferita alla tabella di partenza (quella delle persone), cioè $from_id, e una riferita alla tabella di destinazione (quella dei ristoranti), cioè $to_id, popolate con il contenuto delle rispettive colonne $node_id che avevamo recuperato al momento di inserire i dati nell’arco. Anche in questo caso il nome “vero” delle colonne generate automaticamente è seguito da una stringa esadecimale, ma analogamente a quanto avveniva per le tabelle nodo, possiamo interrogarle omettendo il suffisso.

Volendo pensare in termini relazionali alla struttura appena creata, non abbiamo fatto qualcosa di molto diverso rispetto al creare una tabella molti a molti tra la tabella Persone e la tabella Ristoranti.

Se adesso riapriamo il menu delle Graph Tables su Management studio, troviamo le tre entità create finora.

Guardando l’icona a sinistra del nome è possibile distinguere tra tabelle nodo e tabelle arco, essendo le prime contraddistinte da un pallino pieno, mentre le seconde da un connettore che unisce tra di loro due pallini vuoti.

È importante osservare che di default tutti gli archi creati sono bidirezionali; ciò significa che, se non imponiamo nessun vincolo, potremmo inserire un record in cui un ristorante recensisce un utente, che costituirebbe uno scenario un po’ strano.

Per proteggerci da questa eventualità possiamo aggiungere un vincolo sull’arco che connette le persone ai ristoranti, in modo da imporre la direzionalità delle recensioni solo dalla persona verso il ristorante.

Come ultimo passaggio per completare il grafo di esempio che vogliamo riprodurre ho creato e popolato in modo del tutto analogo anche la tabella arco che rappresenta il legame tra due persone, chiamata AmicoDi ovvero un arco che collega la tabella Persone a sé stessa (stavolta senza attributi).

A questo punto abbiamo ricreato esattamente la struttura che volevamo, e possiamo eseguire qualche query per renderci conto di come estrarre informazioni dal sistema appena costruito.

La funzione MATCH

Come primo esempio vorrei trovare quali ristoranti il signor Wagner ha valutato con più di tre stelle: la forma della query sarà la seguente

L’aspetto più significativo di questa query è sicuramente la presenza della funzione MATCH e dell’indicazione che segue (P-(A)->R).

Quello che stiamo facendo nella FROM è sostanzialmente un prodotto cartesiano tra le tabelle Persone, Ristoranti e AmaMangiareDa: la funzione Match invece si preoccupa di stabilire la gerarchia tra queste entità, mostrando con una sintassi che riproduce in modo quasi visuale la relazione tra le tabelle considerando che il nostro scopo è quello di scoprire quale persona (P) ama mangiare (A) in quale ristorante (R).

Volendo possiamo complicare un po’ di più la cosa aggiungendo il livello della relazione tra le persone. Proviamo quindi a ricavare tutti i ristoranti con valutazione uguale a 5 recensiti dagli amici del signor Wagner.

Da questo comando è possibile notare che le tabelle nodo vanno specificate nella FROM n volte, una per ogni occorrenza nel MATCH, mentre all’interno del MATCH stesso abbiamo semplicemente aggiunto degli anelli alla catena per coinvolgere nella query anche le relazioni tra persona e persona.

La funzione SHORTEST_PATH

Abbiamo detto che i DB a grafo sono molto adatti per rappresentare i legami e le relazioni tipiche di un sistema come un social network; immaginiamo quindi che la nostra tabella Persone rappresenti un mini social network di compositori ottocenteschi, i cui membri siano relazionati in questo modo

Ricordiamo che abbiamo strutturato l’arco che referenzia la tabella “Persone” con sé stessa in modo che sia bidirezionale e che non sia pesato: Richard è amico di Clara esattamente come lei lo è di lui e l’amicizia tra loro due vale esattamente come l’amicizia tra qualunque altra coppia di membri direttamente connessi di questo diagramma.

La nostra esigenza in questo momento è quella di capire qual è il minimo percorso possibile per andare da una persona all’altra, per esempio da Felix Mendelssohn (in alto a sinistra) ad Anton Bruckner (in basso a destra).

A differenza di quanto si potrebbe credere questa operazione nasconde una certa complessità, dato che stabilire dei percorsi tra i nodi è un’operazione molto costosa, come scopriremo tra poco a nostre spese. La soluzione consisterà nell’intendere ciascun percorso come una serie di nodi raggruppati, un approccio che sarà determinante nel cercare di minimizzare i passaggi tra un nodo e l’altro.

Lanciamoci in una veloce disamina di questa query, a partire dalla FROM.

L’espressione FOR PATH che segue l’arco e il nodo di destinazione ricorda in qualche modo una GROUP BY, dato che il suo scopo sarà quello di raggruppare i nodi che costituiscono il percorso minimo tra il nodo di partenza e quello di arrivo.

La funzione STRING_AGG è stata di recente aggiunta in SQL Server ed è una semplice concatenazione tra stringhe, che permette di collegare il set di nomi nella colonna Friends con i caratteri voluti (nel nostro caso, ‘->’), mentre la LAST_VALUE restituisce l’ultimo valore di un certo set (ovvero del nodo di destinazione).

Infine nella WHERE troviamo, all’interno della MATCH che abbiamo già visto, la dicitura “SHORTEST_PATH”, che ricerca il percorso più breve tra un nodo e l’altro del diagramma. Alla sintassi ormai nota per specificare a quali nodi e quali archi siamo interessati (Person1(-(fo)->Person2) abbiamo in aggiunta un segno ‘+’ che sta ad indicare che vogliamo le informazioni riguardo all’intero percorso tra ciascun membro del nodo di partenza e di quello di destinazione, senza limitare il numero dei singoli passaggi. Ogni volta che la query viene eseguita, il risultato dell’esecuzione di questo modello sarà una raccolta ordinata di nodi e archi attraversati lungo il percorso, dal nodo iniziale al nodo finale.

Questa funzionalità merita alcune riflessioni. La prima è che, se eseguiamo solamente la CTE della query esposta in precedenza, otterremo come risultato i percorsi più brevi tra il nodo Mendelssohn e tutti gli altri nodi del grafico.

Questa considerazione deve sicuramente far scattare un campanello d’allarme dal punto di vista delle performance: se già in uno schema semplice come questo abbiamo così tante ramificazioni, sicuramente per una realtà più complessa le risorse impiegate per sfornare i risultati possono esplodere facilmente. Teniamo anche in considerazione che avevamo specificato esplicitamente il nodo di partenza, cioè Mendelssohn, nella condizione WHERE: non l’avessimo fatto avremmo ottenuto i percorsi che collegano tutti i nodi dello schema con tutti gli altri nodi.

Un’azione che sicuramente aiuta a migliorare le performance in uno scenario come questo consiste nell’aggiunta un indice sulle colonne $from_id e $to_id

Proprio per limitare il dispendio di risorse, anche se ci sono due o più percorsi che portano da un nodo ad un altro con lo stesso numero di passaggi, SQL Server ne mostrerà sempre e solo uno (scelto in base al primo trovato). Prendiamo ad esempio il percorso che viene mostrato come il più breve per andare da Mendelssohn a Bruch: ci viene mostrato il corretto cammino Mendelssohn->Wagner->Schumann-> Bruch, ma al tempo stesso viene ignorato quello del tutto equipollente Mendelssohn->Wagner->Schubert-> Bruch.

Un altro aspetto interessante da notare è che di default non c’è vincolo che escluda il nodo di partenza dai nodi di arrivo, troviamo infatti alla sesta riga il loop Mendelssohn -> Wagner -> Mendelssohn.

Purtroppo al momento la funzione SHORTEST_PATH non è in grado di essere parametrizzata in modo esplicito con i nodi di partenza e di arrivo; la conseguenza di ciò è che il filtraggio dei risultati deve essere eseguito in un secondo momento tramite opportune clausole WHERE, come in questo caso: una interna alla CTE per definire il nodo di partenza e una esterna per definire il nodo di arrivo.

Come ultimo esempio possiamo indagare una sintassi alternativa al ‘+’ visto nella MATCH dell’esempio precedente, che ci permette di specificare a che livello di profondità fermare la nostra ricerca sui nodi.

In questa query abbiamo pertanto estratto tutte le persone ad un minimo di uno e un massimo di due livelli di distanza da Richard Wagner e che abbiano lasciato una recensione a MacDonalds. La prima condizione è fornita dal segmento di codice {1,2} che ha sostituito il segno ‘+’ visto in precedenza, il vincolo sulla presenza della recensione è invece espresso dalla seconda condizione all’interno della MATCH.

Conclusioni

Alla luce di queste considerazioni possiamo chiederci quando effettivamente possa convenire utilizzare un DB a grafo su SQL Server.

Attualmente SSMS non è ancora in grado di competere con tecnologie sviluppate appositamente, come Neo4j, OrientDB o HyperGraph DB, specie se teniamo presenti alcune limitazioni piuttosto importanti, ad esempio

  • Non è permesso eseguire operazioni di UPDATE sulle colonne degli archi
  • Tabelle temporanee e tabelle temporanee globali non sono supportate
  • Non è possibile eseguire query cross-database
  • Non c’è un modo diretto per convertire tabelle normali in tabelle di un DB a grafo
  • Non esiste GUI: per visualizzare il grafo dobbiamo appoggiarci a strumenti esterni come Power BI

Se però la nostra esigenza è di sviluppare un DB a grafo non eccessivamente complesso e performante senza cambiare tecnologia, sicuramente questa funzionalità già completamente integrata in SQL Server può essere di grande aiuto.

Nota

Tutto il codice utilizzato nell’articolo è disponibile a questo link

https://drive.google.com/drive/folders/1DQo4CioViLCcNylA88T02aZeLRo9q40D?usp=sharing

Sitografia

https://docs.microsoft.com/en-us/sql/relational-databases/graphs/sql-graph-architecture?view=sql-server-ver15

https://docs.microsoft.com/en-us/sql/relational-databases/graphs/sql-graph-sample?view=sql-server-ver15

https://docs.microsoft.com/en-us/sql/relational-databases/graphs/sql-graph-shortest-path?view=sql-server-ver15

https://docs.microsoft.com/en-us/sql/relational-databases/graphs/sql-graph-overview?view=sql-server-ver15

https://docs.microsoft.com/it-it/sql/relational-databases/graphs/sql-graph-shortest-path?view=sql-server-ver15

https://medium.com/swlh/how-to-make-use-of-sql-server-graph-database-features-946ce38190cc

https://novacontext.com/getting-started-with-sql-server-graph/index.html

https://www.red-gate.com/simple-talk/databases/sql-server/t-sql-programming-sql-server/sql-server-2019-graph-database-and-shortest_path/

https://www.sqlshack.com/graph-database-features-in-sql-server-2019-part-1/

#jointherevolution

Introduzione

Il New York Times presenta la data science come il settore che promette di rivoluzionare tutte le imprese e associazioni: dal governo, all’assistenza sanitaria, dal mondo accademico, alle aziende. Tuttavia, i ruoli all’interno di questa branca sono svariati e in questo articolo vi daremo una panoramica sulle principali figure professionali attualmente presenti nel campo:

  • BI developer e Data Analyst
  • Back-end developer
  • Data Scientist e AI Engineer
  • (Big) Data Engineer e Data Architect

Ogni azienda dà definizioni proprie di questi impieghi e delle responsabilità che a loro competono, ma mettendo insieme le concezioni più chiare e comuni su questo tema, iniziamo a descrivere cosa fa un BI Developer.

BI developer e Data Analyst

Uno sviluppatore di Business Intelligence (BI) è incaricato di sviluppare, distribuire e mantenere le interfacce BI. Questi includono strumenti di interrogazione e modellizzazione dati, nonché visualizzazione delle informazioni tramite report ad hoc o dashboard interattive.  Una piattaforma per la BI ha 3 livelli: origine dati, warehouse e reporting.

Nel livello dell’origine dati vengono archiviati i dati grezzi. Essi possono essere dati strutturati o non. I dati strutturati vengono archiviati in un formato predefinito e vengono comunemente archiviati nei data warehouse (DWH). I dati non strutturati invece (per esempio, video e immagini) vengono archiviati solitamente invece nei data lake (DL). Entrambi hanno un potenziale di utilizzo del cloud, ma i dati strutturati consentono meno spazio di archiviazione.

Il livello warehouse comprende tutte le tecnologie che facilitano il processo di storage per tutti i dati aziendali e gli strumenti che eseguono l’estrazione, la trasformazione e il caricamento (ETL). In questo modo i dati vengono spostati in un unico database così da standardizzare i dati in formati coerenti in modo che possano essere interrogati efficacemente. La sua implementazione e manutenzione è un campo di responsabilità per gli sviluppatori di database/ETL e gli analisti/ingegneri di dati.

Il livello di reporting è l’effettiva interfaccia BI che consente agli utenti di accedere ai dati, per esempio tramite tool come Power BI, Qlik Sense, Tableau. 

I tool di visualizzazione e analisi dati devono essere padroneggiati anche da un buon Data Analyst, colui che consente alle aziende di ottimizzare il valore dei propri asset di dati utilizzando anch’essi dashboard e report ad hoc.

Essi interrogano ed elaborano i dati, fornendone visualizzazioni, aggregazioni e interpretazioni che permettono  di trasformarli in informazioni utili al business e al processo decisionale. Hanno quindi meno dimestichezza a livello tecnico per quel che riguarda l’architettura generale che prepara i dati prima dell’ultimo layer, ma hanno forti competenze di analisi e nel dare valore pratico ai dati ottenuti. 

Lavorando sull’ultimo layer devono, inoltre, avere le competenze necessarie per interrogare agilmente i dati finali, per questo sono anche responsabili di apportare migliorie ai report e dashboard indicando al BI Developer anche l’eventuale esigenza di implementare o modificare i flussi dati.

Seguono alcuni importanti tool del settore e alcune certificazioni di interesse.

Back-end developer

Viene definito back end tutto ciò che opera dietro le quinte di una pagina web, in contrapposizione al front end, che indica invece gli elementi visibili agli occhi dell’utente, elaborati lato client (client side).

Le mansioni di questa figura sono molteplici e possono differire sia rispetto al livello di intervento sul codice, sia sul piano dei processi che portano un prodotto digitale. 

Per diventare Back End Developer è essenziale soprattutto conoscere un’ampia gamma di linguaggi di programmazione. Spesso infatti le aziende ricercano Sviluppatori Back End a partire proprio da questo requisito, richiedendo competenze di coding nel linguaggio impiegato nei propri sistemi informatici. 

Tra i linguaggi più diffusi e richiesti troviamo: Ruby, Python, C++, SQL, Java e Javascript.

A questi devono aggiungersi anche i framework già predisposti per la programmazione come Spring o Hibernate, nonché competenze di creazione e organizzazione di database digitali (tramite Oracle, MySQL, NoSQL, MongoDB, ecc.), poiché in genere le aziende dispongono già di un database digitale e cercano sviluppatori che siano in grado di operare.Inoltre bisogna tenere conto della velocità impressionante con cui si evolvono questi linguaggi, per cui è bene che uno sviluppatore si mantenga costantemente aggiornato sulle novità in termini di coding e programmazione. Proprio per questo aspetto, consigliamo delle certificazioni focalizzate sulla conoscenza dei linguaggi di programmazione: 

I back-end developer lavorano in tutti i settori dell’informatica, e molto spesso, quelli che lavorano all’interno di un team focalizzato nella data science finiscono con lo specializzarsi su metodologie e librerie padroneggiate dai data scientist o data engineer.

Data scientist e AI Engineer

Il Data Scientist è colui che analizza e interpreta dati complessi, combinando più campi, tra cui statistica, AI e analisi dei dati. Il loro lavoro può andare dall’analisi descrittiva, all’analisi predittiva. L’analisi descrittiva valuta i dati attraverso un processo noto come analisi esplorativa dei dati (EDA). L’analisi predittiva viene usata in ambito di Machine Learning per applicare tecniche di modellazione in grado di rilevare anomalie o modelli. 

L’analisi descrittiva e quella predittiva rappresentano solo un aspetto del lavoro dei data scientist. Come prerequisito essenziale emerge la capacità di programmare, per esempio usando Python e R, ma anche la capacità di implementare algoritmi sofisticati di ML.

Adesso chiariamo un’importante differenza che spesso viene tralasciata: quella tra un data scientist e un AI engineer.

Gli AI Engineer sono responsabili dello sviluppo di nuove applicazioni e sistemi che utilizzano l’Intelligenza Artificiale per migliorare le prestazioni e l’efficienza, prendere decisioni migliori, ridurre i costi e aumentare i profitti. Un esperto di intelligenza artificiale deve essere in grado di analizzare e associare i principi dell’IA al ragionamento e all’incertezza in qualsiasi ambiente prospettico, saper applicare queste tecniche per l’analisi e la ricostruzione delle immagini, risolvere una varietà di problemi o scenari complessi ma anche per modellare il comportamento umano nello svolgimenti di compiti complicati o completare processi complessi. La valutazione e il miglioramento delle prestazioni delle applicazioni nei domini di intelligenza artificiale e machine learning è un requisito importante che un AI Engineer deve avere ed è importante aver sviluppato consapevolezza e competenza su queste attività principali  poiché chiunque lavori nell’IA o nell’apprendimento automatico verrà chiesto di gestire questo tipo di responsabilità quasi quotidianamente. Si tratta di una professione complessa che richiede una grande quantità di conoscenze tecniche ed esperienze specifiche.

Un AI Engineer aiuta le aziende a creare nuovi prodotti di AI efficacemente funzionanti, mentre un data scientist implementa strumenti che utilizzando i dati promuovono un processo decisionale redditizio sfruttando anche l’AI se necessario. Queste figure lavorano a stretto contatto per creare prodotti utilizzabili per i clienti. Un data scientist per esempio potrebbe implementare i modelli di machine learning su IDE mentre un AI engineer potrebbe crearne una versione distribuibile del modello creato dal data scientist integrando i suoi modelli nel servizio finale. 

Gli AI Engineer sono anche responsabili della creazione di API di servizi Web sicure per la distribuzione di modelli. In altre parole, un data scientist utilizza l’IA come strumento per aiutare le organizzazioni a risolvere i problemi mentre un AI Engineer per servire i clienti guardando però al business da un punto strategico più basso. Entrambi devono lavorare in modo collaborativo per creare una soluzione che funzioni con la più alta efficienza e precisione possibile quando implementata nella vita reale.

Ecco alcune certificazioni consigliate: 

(Big) Data Architect e Data Engineer

Il Data Architect  è specializzato nella progettazione di sistemi informatici per la gestione e la conservazione di dati e informazioni. Egli si occupa di organizzare i dati, impostare i criteri di accesso e coordinare le varie fonti, il tutto con lo scopo di rendere i dati stessi fruibili e funzionali al raggiungimento degli obiettivi aziendali. Utilizzano la loro conoscenza dei linguaggi informatici orientati ai dati per organizzare e mantenere i dati in database relazionali e repository aziendali, sviluppando strategie di architettura dei dati per ogni area tematica del modello dati aziendale.

Le competenze professionali comuni dei data architect comprendono competenze tecniche avanzate (in particolare in linguaggi come SQL e XML), un eccellente acume analitico, una visualizzazione creativa e capacità di problem-solving, e un forte orientamento al dettaglio. Ne consegue che l’Architetto dei Dati, raccogliendo ed elaborando dati derivanti sia da fonti interne, sia da fonti esterne, può essere visto come una sorta di anello di congiunzione tra l’area IT e le altre aree dell’organizzazione. 

Chiariamo qua un’altra differenza spesso non sottolineata: i Data Architect progettano la visione e il progetto del framework dei dati dell’organizzazione, mentre il Data Engineer è responsabile della creazione di tale visione.

I data engineer si occupano del provisioning e della configurazione delle tecnologie di piattaforma dati, in locale e nel cloud. Gestiscono e proteggono il flusso di dati strutturati e non strutturati da più origini. Devono anche avere un forte background tecnico con la capacità di creare e integrare API e comprendere le pipeline dei dati e l’ottimizzazione delle prestazioni. Le competenze tecniche desiderate includono la conoscenza dei sistemi Linux, la competenza nella progettazione di database SQL e una solida padronanza di linguaggi di codifica come Java, Python, Kafka, Hive o Storm. 

Le piattaforme dati usate possono includere database relazionali e non relazionali, flussi di dati e archivi di file. I data engineer verificano inoltre che i servizi dati siano integrati in modo sicuro e trasparente.L’ambito di lavoro di un data engineer va oltre la gestione di un database e del server in cui questo è ospitato e probabilmente non include la gestione complessiva dei dati operativi. 

Un data engineer può aggiungere un notevole valore sia ai progetti di business intelligence che a quelli di data science. Quando il data engineer raccoglie i dati, operazione spesso detta di data wrangling, i progetti avanzano più rapidamente, perché i data scientist possono concentrarsi sulle proprie aree di lavoro. Un BI developer collabora a stretto contatto con un data engineer per assicurarsi che sia possibile accedere a una vasta gamma di origini dati, strutturate e non, a supporto dell’ottimizzazione dei modelli di dati, che sono in genere forniti da un data warehouse o un data lake moderno.

Di seguito alcune certificazioni possibili per un data engineer: 

I professionisti che si occupano di Big Data in particolare si specializzano nel trattare set di dati troppo grandi o complessi per essere gestiti dai tradizionali software applicativi di elaborazione dati. I dati con molti campi (righe) offrono una maggiore potenza statistica, mentre i dati con una maggiore complessità (più attributi o colonne) possono portare a un tasso di false discovery più elevato. Le sfide dell’analisi dei big data includono l’acquisizione di dati, l’archiviazione dei dati, l’analisi dei dati, la ricerca, la condivisione, il trasferimento, la visualizzazione, l’interrogazione, l’aggiornamento, la privacy delle informazioni e l’origine dati. L’analisi dei big data presenta sfide nel campionamento, consentendo quindi in precedenza solo osservazioni e campionamenti. Pertanto, i big data spesso includono dati con dimensioni che superano la capacità del software tradizionale di elaborare entro un tempo e un valore accettabili. Ecco un percorso di certificazione per iniziare a studiare il problema: https://intellipaat.com/big-data-hadoop-training/

Conclusioni

Dopo questa panoramica sulle figure professionali del settore analytics speriamo possiate averne un’idea più chiara e, perchè no, di avere ispirato alcuni di voi nella costruzione/proseguimento della propria carriera in questo settore.

FONTI:

Articolo a cura di Lucia Campomaggiore (MS BI Developer) e Carla Melia (Head of Analytics), 14.03.2022

#jointherevolution

Negli articoli precedenti abbiamo introdotto la teoria dei giochi (https://orbyta.it/teoria-dei-giochi/) e la teoria dei grafi (https://orbyta.it/teoria-dei-grafi/) e abbiamo visto come quest’ultima possa essere usata per risolvere giochi dall’equilibrio controintuitivo.

In questo articolo approfondiremo le reti andando a studiare i giochi dinamici e situazioni più complesse che ci permetteranno di analizzare la propagazione delle strategie all’interno di un network.

Giochi dinamici

Consideriamo i giochi in cui l’interazione tra i giocatori è intrinsecamente dinamica, cioè in cui i giocatori sono in grado di osservare le azioni degli altri giocatori prima di scegliere la loro miglior risposta [6].

Questo genere di giochi rientra nella categoria dei cosiddetti giochi dinamici insieme a quelli detti sequenziali nei quali i partecipanti prendono decisioni osservando a turno l’azione dell’avversario e stabilendo di conseguenza l’azione ottimale da adottare.

Si noti che l’attenzione non è posta all’alternanza sequenziale dei turni, bensì al fatto che i giocatori effettuano la loro scelta dopo che altri giocatori hanno già mosso, come nel gioco della briscola dove l’alternanza dei turni è stabilita di volta in volta in funzione di chi si è aggiudicato la mano precedente.

Si intuisce che la caratteristica principale di questi giochi è il fatto che le azioni di un giocatore possano influenzare le azioni ottimali degli altri, e questo incrementa il numero delle loro possibili strategie che adesso non coincidono più con le possibili azioni, infatti, a queste vanno aggiunte le cosiddette strategie condizionali.

È importante che i giocatori successivi abbiano informazioni sulle scelte precedentemente effettuate dagli altri giocatori, altrimenti la differenza di tempo non avrebbe alcun effetto strategico.

Esempio dinamico delle aziende

Finora abbiamo lavorato con quella che è chiamata forma normale di rappresentazione di un gioco in cui si specifica un insieme di giocatori e per ognuno di essi un insieme di strategie con i relativi payoff. Per descrivere un gioco dinamico necessitiamo, per esempio, di esplicitare quando e come i vari giocatori possono muovere.

Utilizziamo a tale scopo la cosiddetta forma estesa (o ad albero) della rappresentazione del gioco.

Immaginiamo che ci siano due aziende, P1 e P2, ognuna delle quali sta cercando di decidere in quale, tra due regioni A e B disponibili, focalizzare la propria pubblicità. P1 può decidere prima e supponiamo che:

  • Se P2 scegliesse di seguire P1 nella stessa regione allora P1 otterrebbe i 2/3 del profitto ricavabile da tale regione, mentre P2 solo il rimanente terzo;
  • Se P2 scegliesse l’altra regione allora entrambe le aziende otterrebbero il massimo ricavabile dalle zone.

Si assuma però che A abbia un potenziale di guadagno di 12 mentre B di 6. Rappresentiamo tale gioco col seguente diagramma ad albero da leggere dall’alto verso il basso.

Il nodo superiore rappresenta la mossa iniziale di P1 che può essere o A o B, da cui i due rami. I nodi sul secondo livello rappresentano le scelte di P2 che sono a loro volta A e B. I nodi inferiori coincidono con le possibili conclusioni del gioco e sotto di essi vengono riportati i rispettivi payoff di P1 e P2.

Notiamo che, una volta che P1 ha fatto la prima mossa, il comportamento di P2 è facilmente prevedibile:

  • Se P1 avesse scelto A, a P2 converrebbe scegliere B (questo perchè P2 compara gli output 4 e 6);
  • Se P1 avesse scelto B, P2 avrebbe dovuto scegliere A.

Ora cerchiamo di prevedere la mossa iniziale di P1.

  • Se P1 scegliesse A allora ci si aspetterebbe che P2 scelga B e quindi un guadagno di 12;
  • Se P1 scegliesse B, P2 sceglierebbe A e otterrebbe un guadagno di 6.

Concludiamo perciò che P1 sceglierà A e P2 B.

Generalizziamo ora la metodologia di risoluzione appena usata. Tale risoluzione, utile allo studio dei giochi dinamici, consiste nei seguenti passaggi:

  • Costruito l’albero iniziamo a considerare i penultimi nodi partendo dall’alto (backward induction). In essi il giocatore che muove ha diretto controllo sul risultato delle vincite. Questo ci permette di prevedere ciò che l’ultimo giocatore farà in tutti i casi;
  • Ci si sposta al livello superiore e, ragionando nello stesso modo, cerchiamo di capire cosa farà il giocatore nella mossa precedente;
  • Itero il processo fino ad arrivare a stabilire il comportamento del primo giocatore.

Può sembrare strano, ma il precedente risultato implica che teoricamente il vincitore di un incontro di scacchi (o un eventuale esito di parità) sia noto a priori. Siccome un tale albero ha un numero di nodi al di là di ogni possibile rappresentazione e computazione, la procedura ricorsiva delineata non è fattibile e quindi il gioco degli scacchi continua a mantenere il suo interesse.

In alcuni casi, come in questo esempio, possiamo descrivere il gioco dinamico tramite una forma normale di rappresentazione. Purtroppo, il voler convertire una rappresentazione di tipo esteso in una di tipo normale a volte provoca la perdita di alcune informazioni e non permette, dunque, di preservare la struttura del gioco.

In generale, possiamo assumere che la forma normale sia più usata nel caso di giochi a mosse simultanee, mentre quella estesa sia spesso più opportuna nella descrizione di giochi sequenziali [15].

In riferimento all’esempio, per la conversione ragioniamo come segue.

Supponiamo che, prima che la partita inizi, ogni giocatore faccia un piano per capire quali mosse effettuare considerando ogni possibile evenienza. Tutte le possibili modalità di gioco sono (indicando con XY il fatto che P2 sceglierà X se P1 sceglie Y) (AA, AB), (AA, BB), (BA, AB) e (BA, BB).

A questo punto possiamo calcolare le vincite risultanti dalle varie combinazioni di strategie e otteniamo il seguente schema:

Notiamo che per P1 A è la strategia strettamente dominante, mentre P2 non ha una strategia del genere ma le sue migliori risposte sono (BA,AB) e (BA,BB). Poiché P1 sceglierà A avremo che, proprio come ci aspettavamo, P2 sceglierà B.

Diffusione di una strategia

Potremmo in prima approssimazione pensare che l’importanza di un nodo in una rete sia data meramente dal suo grado, cioè dal numero di archi a esso collegati.

L’esempio della seguente figura ci fa notare che ciò non è necessariamente vero, infatti se si vuole far passare un’informazione nella rete, abbiamo che il comportamento del nodo centrale è fondamentale per il raggiungimento o meno del nostro scopo anche se ha un grado basso rispetto a quello di altri nodi.

La centralità di un nodo può essere più proficuamente usata come misura dell’importanza di un nodo nella rete e tale concetto è formalizzato da quello di betweeness. La betweeness di un nodo i è il numero dei cammini minimi passanti da i. In particolare la betweeness centrality del nodo v è la somma, al variare della coppia di nodi s e t, dei rapporti tra il numero di cammini minimi tra s e t passanti per v e il numero di cammini minimi totale tra s e t.

A seguito di quando detto, supponendo di essere un’azienda che voglia diffondere il più possibile una nuova tecnologia A, per scegliere i “nodi chiave” (ovviamente limitati) a cui fornire gratuitamente il prodotto affinché si diffonda in tutto il territorio, dovremmo tenere in considerazione la betweeness centrality dei vari nodi a disposizione.

Il concetto di connessione (o densità) di una rete è esplicato da quello di coefficiente di clustering[11]. Il coefficiente di clustering del nodo i, Ci ∈ [0, 1] rappresenta la densità di connessioni nelle vicinanze del nodo stesso, in particolare Ci = 1 se tutti i nodi a esso collegato sono tra loro connessi a due a due e Ci = 0 se tutti i nodi a esso connessi sono tra loro isolati.

Si può calcolare un coefficiente medio di clustering per i nodi della rete per avere una visione più generale della stessa. Se C è piccolo ci aspettiamo un grafo con poche connessioni.

Vedremo che, per il diffondersi di una nuova tecnologia, in generale è auspicabile che la rete non sia fortemente connessa (a differenza di quanto avveniva per il sorgere di una rivolta negli articoli precedenti).

Presentiamo alcuni esempi.

Esempio di reazione a catena [9]

Supponiamo di avere un grafo in cui ogni nodo possa scegliere tra due possibili comportamenti e che se due nodi sono tra loro collegati essi sono incentivati ad adottare la stessa strategia, in particolare se entrambi

scegliessero A otterrebbero un guadagno individuale di a, se entrambi scegliessero B di b, ma se scegliessero strategie distinte di 0. Se ci fossero più nodi vicini, per esempio d, e una percentuale p di loro usasse A, mentre la restante (1-p) usasse B, avremmo che A risulta una strategia efficace da usare se dpa > d(1 − p)b ossia se la somma dei payoff individuali (a) ottenuti dai nodi (d*p) che scelgono A, è maggiore della somma dei payoff individuali (b) ottenuti dal gruppo di nodi d*(1-p) che sceglie B. In sintesi, la strategia A è vincente se p> b/(a+b) , cioè la percentuale di nodi che scelgono A deve superare la percentuale del payoff b rispetto al guadagno totale possibile (a+b). Chiameremo p valore soglia.

Quindi più la connessione di un grafo aumenta (mantenendo fisso il numero di nodi) più è difficile che una nuova strategia, che segue queste regole di profitto, si diffonda partendo da pochi iniziatori.

Si pensi al caso in cui, nel grafo in questione, una parte di nodi scelga A e la restante B. Seguendo il ragionamento precedente alcuni nodi potrebbero cambiare comportamento e si innescherebbe di  conseguenza un processo di mutazione della strategia dei nodi della rete che terminerebbe al raggiungimento di una condizione di stabilità.

Si prendano per esempio a=3 e b=2 e si consideri il seguente grafo

dove all’istante iniziale tutti i nodi scelgono B, tranne v e w che scelgono A. Denotando con p il

valore soglia b/(a+b) notiamo che q = 0.4, quindi se almeno il 40 per cento dei vicini di un nodo avesse una data strategia anch’esso la adotterebbe.

Notiamo che r ha come vicini v, w, s. Di questi ne abbiamo 2 su 3 che scelgono A (cioè il 66 per cento), quindi r passerà alla strategia A e a quel punto farà la stessa cosa anche s (avendo 2 vicini su 3 che scelgono A) e di conseguenza w e v la manterranno. Si arriverà rapidamente alla propagazione totale del comportamento A. Otteniamo dunque una “reazione a catena”.

 

Esempio di non-propagazione

Si consideri la situazione precedente ma in riferimento al grafo sottostante, in cui i nodi evidenziati hanno adottato la strategia A.

E’ facile verificare, con l’iterazione del ragionamento precedente, che non vi sarà una cascata ma solo i nodi 4, 5, 6, 7, 8, 9 e 10 avranno, una volta stabilizzata la situazione, scelto A.

Per ampliare la diffusione di A quel che si può fare è

  • Diminuire il valore di q, per esempio aumentando a;
  • Focalizzarsi su alcuni nodi chiave a cui far adottare la strategia A, ma come sceglierli?

Un cluster di densità P è un insieme di nodi tali che ognuno di loro ha almeno una frazione P dei suoi vicini in tale insieme. Una cascata si conclude quando entra in un cluster sufficientemente denso.

Si consideri un insieme iniziale X di individui che adottano la strategia A con una soglia q, definita come prima, che se superata porta i nodi rimanenti (raggruppati nell’insieme Y) ad adottare anch’essi tale strategia. Se e solo se Y contiene un cluster di densità maggiore a 1-q, l’insieme X non riuscirà a realizzare un effetto a cascata completo e quindi a diffondere la strategia A.

Esempio di massimizzazione della soglia

Data una rete possiamo chiederci quale sarà la soglia q più elevata che a essa si potrà applicare ottenendo comunque un effetto a cascata. Questa quantità è chiamata capacità di diffusione, per esempio la capacità di diffusione della seguente rete, in cui i nodi che hanno adottato la nuova strategia A sono indicati in nero, è 1/2 (se raggiunta, infatti, farà sì che A si diffonda come un’onda sulle code).

In particolare si può dimostrare che nessuna rete può avere capacità maggiore a 1/2. Supponiamo ora di avere la seguente matrice di payoff

ove ogni nodo può scegliere se adottare la tecnologia A, la B o entrambe. Nel caso in cui lui e un suo vicino scelgano entrambi la strategia AB il payoff per entrambi sarà del massimo tra a e b meno un costo aggiuntivo c.

Prendiamo per esempio c=1, a=2 e b=3. Partendo dalla situazione START sottoindicata abbiamo i seguenti sviluppi:

e quindi la strategia A si diffonderà sempre di più all’aumentare delle iterazioni. È intuitivo aspettarsi che se a è molto maggiore di b la tecnologia A si diffonderà rapidamente, ma come influisce c? La sua influenza, in relazione a quella di a è sintetizzata nelle immagini sottostanti.

I giochi ripetuti

Oltre ai giochi sequenziali menzioniamo brevemente che all’interno dei giochi dinamici esistono anche i giochi ripetuti che si ripetono più volte con gli stessi giocatori e le stesse azioni/strategie tra cui scegliere. Possiamo per esempio riprendere il dilemma del prigioniero descritto nel precedente articolo sulla teoria dei giochi (https://orbyta.it/teoria-dei-giochi/). In uno scenario “one-shot” il dilemma si risolve con un equilibrio di Nash non pareto-ottimale, infatti i due prigionieri si tradiscono a vicenda, subendo entrambi la condanna. Se invece il gioco venisse ripetuto, vengono prese in considerazione la reputazione dei giocatori, basata sulle decisioni da loro prese in passato, e la punizione/reazione dell’avversario nel turno successivo. L’esito finale in questo caso dipende dal numero di turni nel gioco. Se il numero di turni è predefinito, si può dimostrare che il gioco si conclude esattamente come nel scenario “one-shot”, in un equilibrio non-pareto efficiente, perché gli giocatori sono spinti comunque a tradire. Se invece il numero di turni è sconosciuto, i giocatori sono incentivati a cooperare temendo la reazione dell’avversario nel turno successivo arrivando così ad una conclusione di equilibrio pareto-ottimale.

In questo articolo abbiamo studiato i giochi dinamici e come si risolvono tramite la metodologia di backward induction. Abbiamo visto inoltre i concetti di centralità (betweeness centrality) e del coefficiente medio di clustering per i nodi all’interno di una rete. In particolare abbiamo visto tramite alcuni esempi che per la diffusione di una strategia è importante che la rete non sia fortemente connessa. Infine abbiamo introdotto i giochi ripetuti e come si può arrivare ad una risoluzione pareto-ottimale al loro interno.

 

Bibliografia e Sitografia

[1] R. Dawkins, Il gene egoista, I edizione collana Oscar saggi, Arnoldo Mondadori Editore, 1995.

[2] D. Easley e J. Kleinberg, Networks, Crowds, and Markets: Reasoning about a Highly Con- nected World, Cambridge University Press, 2010.

[3] R. Gibbons, Teoria dei giochi, Bologna, Il Mulino, 2005.

[4] E. Martìn Novo  e A. Mendez Alonso, Aplicaciones  de la teoría  de grafos a algunos juegos   de estrategia, numero 64 di Suma, Universidad Politécnica de Madrid, 2004.

[5] S. Rizzello e A. Spada, Economia cognitiva e interdisciplinarità, Giappichelli Editore, 2011.

[6] G. Romp,Game Theory: Introduction and Applications, Mishawaka, Oxford University Press, 1997

[7] T. C. Schelling, The Strategy of Conflict, Cambridge, Massachusetts: Harvard, University Press, 1960.

[8] P. Serafini, Teoria dei Grafi e dei Giochi, a.a. 2014-15 (revisione: 28 novembre 2014).

[9] I. S. Stievano e M. Biey, Cascading behavior in networks, DET, Politecnico di Torino, 2015.

[10] I. S. Stievano e M. Biey, Interactions within a network, DET, Politecnico di Torino, 2015.

[11] I. S. Stievano, M. Biey e F. Corinto, Retie sistemicomplessi… , DET, Politecnico di Torino, 2015.

[12] A. Ziggioto e A. Piana, Modello di Lotka-Volterra, reperibile all’indirizzo http://www.itismajo.it/matematica/Lezioni/Vecchi%20Documenti%20a.s.%202011-12/Modello

%20di%20Lotka-Volterra.pdf, consultato il 15/05/2015.

[13] http://it.wikipedia.org/wiki/Equilibrio_di_Nash consultato il 12/05/2015.

[14] http://www.oilproject.org/lezione/teoria-dei-giochi-equilibrio-di-nash-e-altri-concetti-introduttivi-2471.html consultato il 13/05/2015.

[15] http://web.econ.unito.it/vannoni/docs/thgiochi.pdf consultato il 14/05/2015.

[16] https://www.youtube.com/watch?v=jILgxeNBK_8 consultato il 19/01/2021.

[17] http://www.andreaminini.it/teoriadeigiochi/giochi-ripetuti consultato il 06/07/2021.

[18] https://www.ed.ac.uk/files/atoms/files/lecture_8_game_theory.pdf consultato il 06/07/2021.

Articolo a cura di Carla Melia (Head Data Scientist), Augusto Cadini (IT Business Analyst) e Angeni Uminga (Software Developer), Orbyta Tech, 10.07.2021

#jointherevolution

Introduzione

Un sistema esperto (o basato sulla conoscenza) è un software in grado di riprodurre in modo artificiale le prestazioni di una o più persone “esperte”  in un determinato campo di attività e trova la sua applicazione nella branca dell’intelligenza artificiale.

Una delle particolarità di un sistema esperto è quella di essere in grado di mettere in atto autonomamente delle procedure di inferenza, un processo induttivo o deduttivo che permette di giungere a una conclusione a seguito dell’analisi di una serie di fatti o circostanze adeguate alla risoluzione di problemi particolarmente complessi.

Un tipico sistema esperto ha due funzioni principali: quella di trarre delle conclusioni e quindi compiere o suggerire delle scelte (COSA) e quella di spiegare in che modo, con quale ragionamento è pervenuto a quelle conclusioni (CONTROLLO).

Un sistema esperto è composto da una base di conoscenza, una memoria di lavoro, un motore inferenziale e un’interfaccia utente. 

Nella base di conoscenza sono contenute le regole deduttive e i dettami procedurali di cui il sistema si serve nel suo operato. Il motore inferenziale è necessario per indirizzare il programma a  interpretare, classificare e applicare la base di conoscenza e le relative regole per ogni singolo aspetto o scenario dello specifico campo disciplinare. La memoria di lavoro, o memoria a breve termine, contiene i dati e le conclusioni raggiunte dal sistema. Infine, l’interfaccia utente permette l’interazione fra il soggetto umano e il programma che deve dare risposta ai suoi problemi.

Queste informazioni sono piuttosto generiche ed estremamente flessibili. Il programma non è un insieme di istruzioni immutabili che rappresentano la soluzione del problema, ma un ambiente in cui rappresentare, utilizzare e modificare una base di conoscenza. 

Caratteristico dei sistemi esperti è imitare l’esperto umano non solo nelle prestazioni ma anche nel modo di eseguire inferenze. La maggior parte di essi fa uso del cosiddetto ”ragionamento di superficie” o fuzzy logic, basato sull’impiego di un gran numero di strategie o regole empiriche, dette euristiche, che legano direttamente i fatti noti con quelli da inferire, senza una vera comprensione del tipo di legame esistente.

Subentra lo stratagemma dell’euristica qualora le componenti che presiedono alle procedure di inferenza, non riescono ad ottenere il rigore connaturato ad un algoritmo, in quanto nelle situazioni altamente complicate sarebbe troppo dispendioso analizzare ogni possibilità.

È nella natura stessa delle euristiche il fatto che non si possa dimostrare che siano corrette in quanto ciò sacrificherebbe risultati altamente probabili, ma comunque fallibili, non dando sempre nella pratica il risultato migliore; tuttavia consentono agli esperti di prendere decisioni quando non sono disponibili criteri più ”forti”.

Come già detto in precedenza, per elaborare le proprie conclusioni, i sistemi esperti possono fare affidamento su una base di conoscenza, la conoscenza viene immagazzinata nella memoria a lungo termine del sistema ed è organizzata e rappresentata sotto forma di regole, ad esempio definite come strutture “if-then” (“se-allora”), che comprendono una premessa o condizione (if) e una conclusione o azione (then), e descrivono la risoluzione di un dato problema.

Un sistema esperto basato su alberi, invece, parte da un insieme di dati ed alcune deduzioni per poi creare un albero di classificazione attraverso il quale i nuovi dati verranno analizzati portando alla deduzione rappresentata dal nodo di arrivo.

Ora ci focalizzeremo sui sistemi esperti basati sulle regole. E’ quindi doverosa un’introduzione alla logica matematica. 

Sistemi esperti e logica matematica

La logica ha lo scopo di formalizzare i meccanismi di ragionamento. Faremo un breve accenno sulle proposizioni, cioè espressioni che rappresentano affermazioni che nell’ambito di questo articolo potranno essere solo o VERE o FALSE. Per quanto ciò possa sembrare scontato, esistono in verità settori in cui si può attribuire a ciascuna proposizione un grado di verità diverso da 0 e 1 e compreso tra di loro (ovvero che usano logica sfumata). 

Ad ogni proposizione elementare viene associata un variabile proposizionale. Per esempio:

  • P1: Se fa caldo ed è umido, allora pioverà. 
  • P2: Se è umido ed è estate, allora fa caldo. 
  • P3: Adesso è umido. 
  • P4: Adesso è estate. 

Se chiamo A = FA CALDO, B = È UMIDO, C = È ESTATE, D = PIOVERÀ. 

La rappresentazione in formule diventa

  • F1: A ∧B →D, 
  • F2: B ∧C →A
  • F3: B
  • F4: C

Si può voler dimostrare che da questi 4 fatti segue logicamente P5: Pioverà, ovvero F5: D. Di ciò si può occupare un sistema esperto.

Come vediamo una formula è composta da formule atomiche (o atomi) (ovvero A, B, …) e connettivi logici. 

I connettivi logici più comunemente usati sono: 

  • ¬(NOT: negazione)
  • ∨(OR: disgiunzione)
  • ∧(AND: congiunzione)
  • →(IMPLIES o IF…THEN…: implicazione)
  • ↔(IF AND ONLY IF: bi-implicazione)

Una formula è ben formata (FBF) se e solo se essa è ottenibile applicando le seguenti regole:

  • un atomo è una FBF
  • se F è una FBF, allora (¬F) è una FBF
  • se F e G sono FBF, allora (F∨G), (F∧G), (F→G), (F↔G) sono FBF

Semplificando  in questa trattazione una FBF è una formula a cui è possibile attribuire un valore di verità, vero o falso.

Le regole viste esprimono la SINTASSI (vincoli strutturali) delle formule del calcolo proposizionale. Stabilendo un ordinamento tra i connettivi è possibile eliminare alcune parentesi. L’ordine che verrà adottato è il seguente: 

  1. ¬ 
  2. ∧, ∨ 
  3. →, ↔

Così, La formula ((((A∨B)∧C)→D)↔(((¬D)→A)∨E) può essere riscritta (eliminando le parentesi esterne) come ((A∨B)∧C→D)↔(¬D→A)∨E.

La SEMANTICA della logica proposizionale richiede l’introduzione dei valori di verità. L’insieme dei valori di verità (che indicheremo con B) include VERO e FALSO, rappresentati da B= {T, F}. 

Un’interpretazione I consiste in un mapping tra l’insieme delle formule e B (specificando cioè, per ogni formula, se essa è vera o falsa). 

Come si può ricavare il valore di verità di una formula? 

Per esempio se ci chiediamo se (P ∧Q) ∨R →(P ↔R) ∧ Q possiamo porre

α= (P ∧Q) ∨R

β= (P ↔R) ∧Q 

e quindi chiederci se α →β consultando la seguente classica tavola di verità (intuitivamente, ogni riga di una tabella di verità corrisponde ad una diversa possibile situazione (interpretazione)).

Alcune formule sono vere in tutte le interpretazioni. Esse sono dette formule valide o tautologie. Altre formule sono false in tutte le interpretazioni. Esse sono dette formule inconsistenti o contraddizioni. 

Poiché ogni formula è finita e quindi contiene un numero finito di formule atomiche, è sempre possibile determinare se essa è valida, inconsistente o né l’una né l’altra. La logica proposizionale è quindi decidibile.

Alcune formule valide sono controintuitive (e sono chiamate paradossi). In esse compare il connettivo →.  

Un esempio è ¬P→(P →Q) che è sempre vera. 

Due formule F e G sono equivalenti (scritto F ⇔G) se e solo se esse hanno lo stesso valore di verità in tutte le interpretazioni. 

Il modus ponens (MP) è una semplice e valida regola d’inferenza, che afferma in parole: “Se p implica q è una proposizione vera, e anche la premessa p è vera, allora la conseguenza q è vera”, ovvero (p ∧(p →q)) →q.

Si ribadisce che l’implicazione non ha nulla a che vedere con la causalità. La logica proposizione infatti si occupa solo di “combinazioni” e non di significati di “causa-effetto”.

Non ci addentreremo nella logica dei predicati in quanto, seppur sia uno strumento  più potente e flessibile, è anche molto più complicato e non adatto alle finalità di questo articolo. 

Per poter trattare in modo meccanico, le fbf devono essere poste in forma a clausole. I passi da seguire sono

  1. Eliminazione delle implicazioni
  2. Riduzione del campo dei segni di negazione
  3. Standardizzazione delle variabili
  4. Eliminazione dei quantificatori esistenziali: ogni variabile esistenzialmente quantificata è rimpiazzata con una funzione di Skolem
  5. Conversione in forma prenessa
  6. Trasformazione della matrice in forma normale congiuntiva
  7. Eliminazione dei quantificatori universali
  8. Eliminazione dei segni di congiunzione

ESEMPIO

Si applicano in successione alcune operazioni, illustrate mediante il seguente esempio:
( ∀x){P(x) →{( ∀y){P(y) →P(f(x,y))} ∧ ¬ ( ∀y){Q(x,y) →P(y)}}}

1) Eliminazione delle implicazioni, ovvero A → B è sostituito da:

 ¬A ∨ B Pertanto: ( ∀x){P(x) →{( ∀y){P(y) →P(f(x,y))} ∧ ¬ ( ∀y){Q(x,y) →P(y)}}} 

diventa: 

( ∀x){ ¬P(x) ∨{( ∀y){ ¬P(y) ∨P(f(x,y))} ∧ ¬ ( ∀y){ ¬Q(x,y) ∨P(y)}}}

2) Riduzione del campo dei segni di negazione (la negazione applicata ad una sola lettera predicativa). 

In pratica: 

Intelligenza Artificiale – Problem Solving 2 101

 ¬(A ∧ B) è rimpiazzata da ¬A ∨ ¬ B 

¬(A ∨ B) ” ¬A ∧ ¬ B

¬¬ A ” A

 ¬ ( ∀x)A ” ( ∃x){ ¬A } 

¬ ( ∃x) A ” ( ∀x){ ¬A }

Pertanto: 

(∀x){¬P(x)∨{(∀y){¬P(y)∨P(f(x,y))}∧ ¬(∀y){¬Q(x,y)∨P(y)}}}

diventa: 

(∀x){¬P(x)∨{(∀y){¬P(y)∨P(f(x,y))}∧ (∃y){¬{¬Q(x,y)∨P(y)}}}} 

e poi: 

(∀x){¬P(x)∨{(∀y){¬P(y)∨P(f(x,y))}∧ (∃y){Q(x,y)∧¬P(y)}}} 

3) Standardizzazione delle variabili: si ribattezzano le variabili quantificate in modo che ogni quantificatore abbia una variabile apparente unica. 

In pratica: 

( ∀x){P(x) → ( ∃x)Q(x)} diventa: ( ∀x){P(x) → ( ∃y)Q(y)}

 Pertanto: 

(∀x){¬P(x)∨{(∀y){¬P(y)∨P(f(x,y))}∧ (∃y){Q(x,y)∧¬P(y)}}} 

diventa: 

(∀x){¬P(x)∨{(∀y){¬P(y)∨P(f(x,y))}∧ (∃w){Q(x,w)∧¬P(w)}}} 

4) Eliminazione dei quantificatori esistenziali: ogni variabile esistenzialmente quantificata è rimpiazzata con una funzione di Skolem. 

Per esempio supponiamo che la fbf 

( ∀ y ∃x)P(x,y) 

possa essere interpretata come: “per tutti gli y esiste un x tale che x è maggiore di y”. 

NB: x può dipendere da y! 

Allora si cerca una funzione g(y) (detta funzione di Skolem) che manda ogni valore di y nell’x che “esiste”. Quindi la fbf diventa 

( ∀y)P(g(y),y) 

Si osservi ancora.

• ∃z si elimina in: 

{( ∀w)Q(w)} → ( ∀x){( ∀y){( ∃z){P(x,y,z) → ( ∀u)R(x,y,u,z)}}} 

ottenendo: 

{( ∀w)Q(w)} → ( ∀x){( ∀y){P(x,y,g(x,y)) → ( ∀u)R(x,y,u,g(x,y))}}} 

Se il quantificatore esistenziale non si trova nel campo di un quantificatore universale, la funzione di Skolem ha zero argomenti. 

Esempio: 

( ∃x)P(x) è sostituito da P( a ) dove a è una costante che sappiamo “esistere”. 

L’esempio che stiamo seguendo diventa da così: 

( ∀x){ ¬P(x) ∨{( ∀y){ ¬P(y) ∨P(f(x,y))} ∧ ( ∃w){Q(x,w)∧¬P(w)}}}

 a così: 

( ∀x){ ¬P(x) ∨{( ∀y){ ¬P(y) ∨P(f(x,y))} ∧ {Q(x,g(x))∧¬P(g(x))}}} 

dove g(x) è una funzione di Skolem. 

5) Conversione in forma prenessa: tutti i quantificatori universali (che sono tutti diversi) vengono spostati all’inizio della fbf (forma prenessa). 

L’esempio da: 

(∀x){¬P(x)∨{(∀y){¬P(y)∨P(f(x,y))}∧ {Q(x,g(x))∧¬P(g(x))}}} 

diventa: 

(∀x∀y){¬P(x)∨{{¬P(y)∨P(f(x,y))}∧ {Q(x,g(x))∧¬P(g(x))}}} 

dove: 

(∀x∀y) è detto prefisso e {¬P(x)∨{{¬P(y)∨P(f(x,y))}∧{Q(x,g(x))∧¬P(g(x))}}} è detta matrice Intelligenza 

6) Trasformazione della matrice in forma normale congiuntiva: la matrice viene scritta come congiunzione di un numero finito di disgiunzioni di predicati e/o negazioni di predicati (forma normale congiuntiva). (In parole povere, AND di OR, ovvero prodotti di somme, ovvero, maxterm). 

Esempi di forma normale congiuntiva: 

{P(x) ∨Q(x,y)} ∧{P(w)∨¬R(y)} ∧Q(x,y) P(x) ∨ Q(x,y) P(x) ∧ Q(x,y) ¬R(y) 

In pratica si applica ripetutamente la relazione: 

A ∨ (B ∧ C) ≡ { A ∨ B } ∧ { A ∨ C} 

L’esempio 

(∀x∀y){¬P(x)∨{{¬P(y)∨P(f(x,y))}∧ {Q(x,g(x))∧¬P(g(x))}}} 

diventa: 

(∀x∀y){{¬P(x)∨ ¬P(y)∨P(f(x,y))}∧ {¬P(x)∨Q(x,g(x))}∧ {¬P(x)∨¬P(g(x))}} 

7) Eliminazione dei quantificatori universali: resta la sola matrice in cui, essendo le variabili legate, sono tutte universalmente quantificate. 

8) Eliminazione dei segni di congiunzione. I segni di congiunzione (cioè ∧; esempio: A ∧ B) sono eliminati dando luogo a due fbf (nell’esempio, A e B). Applicando ripetutamente questo rimpiazzo si ottiene una lista finita di fbf, ognuna delle quali è una disgiunzione ( ∨) di formule atomiche e/o di negazioni di formule atomiche.

Esempio trasformazione in clausola “Tutti i romani che conoscono Marco o odiano Cesare o pensano che tutti quelli che odiano qualcuno sono matti”

fbf corrispondente: ∀x [romano(x) ∧ conosce (x, Marco)] → [odia(x, Cesare) ∨ ( ∀y ( ∃z odia(y, z)) →credematto (x, y))] 

1. eliminazione segni implicazioni: 

∀x ¬[romano(x) ∧ conosce (x, Marco)] ∨ [odia(x, Cesare) ∨ ( ∀y ¬ ( ∃z odia(y, z)) ∨ credematto (x, y))] 

2. riduzione portata negazione: 

∀x [ ¬romano(x) ∨ ¬conosce (x, Marco)] ∨ [odia(x, Cesare) ∨ ( ∀y ∀z ¬odia(y, z) ∨ credematto (x, y))] 

3. Standardizzazione variabili: qui nessuna modifica: ogni quantificatore lega già una variabile differente 

4. Spostamento dei quantificatori: 

∀x ∀y ∀z [eccetera] 

5. Eliminazione quantificatori esistenziali: non ce ne sono

6. Eliminazione prefisso: (resta la matrice) 

[ ¬romano(x) ∨ ¬conosce (x, Marco)] ∨ [odia(x, Cesare) ∨ ¬odia(y, z) ∨ credematto (x, y))] 

7. Trasformazione in congiunzione di disgiunzioni (AND di OR): 

¬romano(x) ∨ ¬conosce (x, Marco) ∨ odia(x, Cesare) ∨ ¬odia(y, z) ∨ credematto (x, y)) (1 sola clausola)

Una clausola di Horn è una disgiunzione di letterali in cui al massimo uno dei letterali è positivo. Esempio: ¬L∨¬B e ¬L∨¬B∨C sono clausole di Horn, ¬L∨B∨C non lo è. Sono importanti perché si possono scrivere come implicazioni la cui premessa è una congiunzione di letterali positivi e la cui conclusione è un singolo letterale positivo. Ad esempio, ¬L∨¬B∨C è equivalente a (L∧B)→C.

Per risolvere i problemi di logica esistono molti modi, useremo il modus ponens come esempio.

La risoluzione è un processo iterativo che, ad ogni passo, confronta (risolve) due clausole genitori e permette di inferire una nuova clausola. Per la risoluzione si considerano due clausole che contengono la stessa formula atomica, una volta affermata e una volta negata. La risolvente è ottenuta combinando tutte le formule atomiche delle clausole genitori eccetto quelle che cancella. Se si produce la clausola vuota, si ha una contraddizione. Il tentativo sarà quello di trovare una contraddizione, se esiste. Se non esiste, la procedura può non avere mai termine.

Risoluzione nella logica proposizionale usando il MP: il procedimento è il seguente: 

Procedimento: 

  1. Trasformare tutte le proposizioni in F in forma a clausole. 
  2. Negare S e trasformare il risultato in forma a clausole. Aggiungerlo all’insieme di clausole ottenute al passo 1).
  1. Ripetere fino a quando viene trovata una contraddizione o non si può più andare avanti i passi seguenti:
    1. Selezionare due clausole. Chiamarle clausole genitori. 
    2. Risolverle insieme. La clausola risultante, chiamata la risolvente, sarà la disgiunzione di tutte le formule atomiche di entrambe le clausole genitori con la seguente eccezione: se vi sono coppie di formule atomiche L e ¬L, tali che una delle clausole genitori contenga L e l’altra contenga ¬L, allora eliminare sia L che ¬L dalla risolvente. 
    3. Se la risolvente è la clausola vuota, allora è stata trovata una contraddizione. In caso contrario, aggiungerla all’insieme di clausole a disposizione della procedura.

ESEMPIO

siano dati i seguenti assiomi: 

Assiomi: 

p 

(p ∧ q) → r 

(s ∨ t) → q 

t 

Convertiti in forma a clausole: 

p

¬p ∨ ¬q ∨ r

¬s ∨ q 

¬t ∨ q

 t 

Si voglia dimostrare r. 

Dopo aver trasformato gli assiomi in forma a clausola, si introduce nella lista ¬r (già in forma a clausola). 

Poi si selezionano le clausole a 2 a 2 e si risolvono (conviene scegliere clausole che contengono la stessa forma atomica una volta affermata e una volta negata).

Si ottiene, ad esempio: 

Nota: la proposizione 2 è vera se sono vere ¬p, ¬q, r 

Al primo passo si assume che ¬r sia vera, insieme alla preposizione 2. 

Ciò può accadere solo se è vera 

¬p oppure ¬q. 

È quello che afferma la risolvente! 

Conclusione: 

per provare r, si prova che ¬r crea contraddizione. Si inserisce quindi ¬r nella lista di forme a clausola e si cerca, mediante risoluzione, se esiste questa contraddizione (metodo della refutazione).

Ci siamo concentrati per semplicità su un esempio di meccanismo performato da un SE usando la logica classica ma i tipi di ragionamento sono tanti, per esempio, potremmo utilizzare:

  • La logica non monotona: permette di cancellare e aggiungere enunciati alla base dati. In questa logica la credenza in un enunciato si può basare sulla mancata credenza in qualche altro enunciato (ragionamento by default).
  • Il Ragionamento probabilistico: rende possibile rappresentare inferenze probabili ma incerte.
  • La Logica sfumata (fuzzy logic): permette di rappresentare proprietà di oggetti continue (non binarie) o sfumate.
  • Il Concetto di spazi di credenza: permette di rappresentare modelli di insiemi di credenze inserite l’uno nell’altro.

Concludiamo l’articolo dando qualche indicazione sul problema della rappresentazione della conoscenza, fondamentale in questo ambito. 

Rappresentazione delle conoscenza

La rappresentazione della conoscenza è una branca dell’intelligenza artificiale che studia il modo in cui avviene il ragionamento umano, e si preoccupa di definire dei simbolismi o dei linguaggi che permettano di formalizzare la conoscenza al fine di renderla comprensibile alle macchine, per potervi fare dei ragionamenti automatici (inferendo le informazioni presenti) ed estrarre così nuova conoscenza. 

Attraverso il linguaggio scelto si andranno ad effettuare una serie di asserzioni sul mondo, che andranno insieme a costituire una base di conoscenza (KB, Knowledge Base). È inoltre importante che il linguaggio scelto per fare le asserzioni sia anche in grado di operare sulla KB per estrarre nuova conoscenza e per aggiungerne di nuova.

I metodi di rappresentazione della conoscenza schematicamente si suddividono in impliciti ed espliciti. In generale occorre rappresentare: collezione di oggetti, collezione di attributi (proprietà degli oggetti) e insiemi di relazioni (tra gli oggetti). La scelta della rappresentazione influenza lo sforzo di ricerca, in quanto può permettere di riconoscere concetti semplificanti (simmetrie, analogie, ecc.) e formare macro operatori (può essere utile utilizzare variabili nella descrizione degli stati). 

Un problema connesso, detto problema del contorno o frame problem, è quello di rappresentare un mondo in cui ci sono cose che cambiano e cose che non cambiano. Per ovviare il problema si può, per esempio, tenere traccia solo dei cambiamenti (lo stato di partenza è descritto in modo completo) o modificare lo stato iniziale con operatori “invertibili” in modo che si possa tornare indietro “annullando” i passi effettuati.

Caratteristiche di un buon sistema di rappresentazione:

  • Adeguatezza rappresentativa: poter rappresentare tutti i tipi di conoscenza relativi a un dominio. 
  • Adeguatezza inferenziale: poter manipolare le strutture rappresentative in modo da inferire nuova conoscenza
  • Efficienza inferenziale: poter incorporare informazioni in più da usare come guida verso gli obiettivi nei meccanismi di inferenza (focalizzazione dell’attenzione/euristica)
  • Efficienza nell’acquisizione: capacità di acquisire facilmente nuova conoscenza.

Occorre che il sistema possieda e sappia manipolare una grande quantità di conoscenza del mondo (semantica e pragmatica) e conosca la sintassi e possieda il vocabolario del linguaggio. E’ desiderabile ma complicato tenere separati i due livelli (ma alcune interpretazioni sintattiche non sono possibili se non si conosce il contesto).

Classificazione delle tecniche:

  • metodi dichiarativi: la conoscenza viene rappresentata come collezione statica di fatti, affiancata da un piccolo insieme di procedure generali per la manipolazione (esempio: logica dei predicati). Vantaggi: 
  • Ogni fatto va immagazzinato solo una volta, indipendentemente dal numero di modi in cui può essere usato.
  • È facile aggiungere nuovi fatti al sistema, senza cambiare né gli altri fatti né le procedure.
  • metodi procedurali: la conoscenza viene rappresentata come procedure per il suo uso. Vantaggi:
  • È facile rappresentare la conoscenza su come fare le cose
  • È facile rappresentare la conoscenza che non si inserisce facilmente in molti schemi dichiarativi semplici, come ad esempio il ragionamento per default e quello probabilistico
  • È facile rappresentare la conoscenza euristica su come fare le cose in modo efficiente

La maggior parte dei sistemi funzionanti usa una combinazione dei due metodi. 

La descrizione delle strutture di conoscenza avviene mediante schemi, ovvero un’organizzazione attiva di relazioni passate, o di esperienze passate, che devono supporre siano operanti in ogni risposta organica adattiva. Senza entrare nel dettaglio elenchiamo di seguito alcuni tipi di schemi.

  • Frame (quadri), spesso usati per descrivere una collezione di attributi che un determinato oggetto, per esempio, una sedia, in genere possiede.
  • Script (copioni), usati per descrivere sequenze di eventi comuni, come ad esempio ciò che succede quando si va al ristorante.
  • Stereotipi, usati per descrivere insiemi di caratteristiche che spesso nelle persone sono presenti contemporaneamente.
  • Modelli a regole, usati per descrivere caratteristiche comuni condivise all’interno di un insieme di regole in un sistema di produzioni.

In questo articolo abbiamo visto alcuni concetti base dei sistemi esperti, estremamente potenti anche se poco conosciuti nell’ambito dell’IA. Abbiamo anche introdotto in maniera intuitiva concetti propri della logica matematica e del problema della rappresentazione della conoscenza. Per approfondire l’argomento consigliamo i seguenti testi:

  • Stuart J. Russell, Peter Norvig, “Intelligenza Artificiale. Un approccio Moderno”, Pearson Education Italia, Milano.
  • E. Rich, “Intelligenza artificiale”, McGraw Hill, Milano.
  • N.J. Nilsson, “Metodi per la risoluzione dei problemi nell’intelligenza artificiale”, Angeli, Milano.
  • Nils J. Nilsson, “Intelligenza Artificiale”, Apogeo,Milano.
  • I. Bratko, “Programmare in prolog per l’intelligenza artificiale”, Masson Addison Wesley, Milano.

FONTI:

  • Slide del corso GESTIONE DELLA CONOSCENZA E INTELLIGENZA ARTIFICIALE, Politecnico di Torino, Elio Piccolo, 2017.
  • https://it.wikipedia.org/wiki/Sistema_esperto, consultato il 20.05.2021
  • Roger Schank e Robert Abelson, Scripts, Plans, Goals, and Understanding: An Inquiry Into Human Knowledge Structures, Lawrence Erlbaum Associates, Inc., 1977.
  • https://www.treccani.it/enciclopedia/sistemi-esperti_%28Enciclopedia-della-Scienza-e-della-Tecnica%29/#:~:text=Insiemi%20di%20programmi%20software%20in,’ambito%20dell’intelligenza%20artificiale, consultato il 09.07.2021.

Articolo a cura di Carla Melia, Lucia Campomaggiore e Ludovico Dellavecchia, 01.08.2021

#jointherevolution

The chosen one: .NET 5

.NET 5, il successore di .NET Core 3.1 e .NET Framework 4.8, mira a fornire agli sviluppatori .NET una nuova esperienza di sviluppo multipiattaforma. Mette ordine alla frammentazione dell’universo .NET che si è verificata nel corso degli anni e apporta nuove straordinarie funzionalità. Di seguito i cinque punti su cui concentrarci per capire agevolmente quali sono i punti di forza dell’ultima release per gli sviluppatori di casa Microsoft.

1. Piattaforma Unificata

La prima cosa che c’è da sapere è che .NET 5 offre una nuova visione unificata del mondo .NET.

Se abbiamo già lavorato con .NET, dovremmo essere a conoscenza della sua frammentazione di piattaforme sin dalla sua prima versione nel 2002. .NET Framework è stato inizialmente progettato per Windows, ma la sua specifica di runtime, nota anche come Common Language Infrastructure (CLI), fu standardizzata come ECMA 335.

Questa standardizzazione consentì a chiunque di creare la propria implementazione del runtime .NET. Infatti non si attese molto per veder comparirne i primi all’orizzonte: abbiamo Mono per sistemi basati su Linux, Silverlight per applicazioni basate su browser, framework .NET Compact e Micro per dispositivi mobili e con risorse limitate e così via.

Per questi motivi, Microsoft decise di scrivere .NET Core da zero pensando esclusivamente alla compatibilità multipiattaforma. Queste diverse implementazioni hanno sollevato la necessità di capire “dove” potrebbe essere eseguito un pacchetto .NET.

Dovresti creare versioni diverse della tua libreria per distribuirla? La risposta a questa domanda fu .NET Standard, ovvero una specifica formale delle API comuni che dovresti aspettarti tra le implementazioni della CLI. In altre parole, se crei la tua libreria per uno specifico .NET Standard, avrai la garanzia che verrà eseguita su tutti i runtime che implementano tale specifica.

Si comprende dunque che, in questa situazione disordinata, la compatibilità di implementazione desiderata non era così facile da ottenere. Questo è il motivo per cui .NET 5 appare in scena.

La nuova piattaforma .NET è il successore unificato delle varie versioni .NET: .NET Framework, .NET Standard, .NET Core, Mono, ecc. È ufficialmente la prossima versione di .NET Core 3.1, ma sostanzialmente determina la fine di .NET Framework, .NET Standard e le altre varianti che hanno causato grossi grattacapi agli sviluppatori .NET.

.NET 5 fornisce un set comune di API che allinea le diverse implementazioni di runtime. Questo set di API è identificato dal Net5.0 Target Framework Moniker (TFM), che è il token impostato nel progetto .NET per specificare il framework di destinazione. Ciò consente l’esecuzione dell’applicazione su qualsiasi implementazione di runtime che supporta .NET 5. Tuttavia, è comunque possibile compilare applicazioni per una piattaforma specifica. Ad esempio, per creare un’applicazione che utilizza l’API di Windows, è necessario specificare il TFM net5.0-windows. In questo modo, la creazione di un’applicazione specifica per la piattaforma è una tua scelta, non una scelta che dipende dall’implementazione di runtime che stai utilizzando per sviluppare la tua applicazione.

Naturalmente, realizzare questa piattaforma unificata ha richiesto uno sforzo significativo e una riorganizzazione dell’architettura interna. Alcune funzionalità sono state rimosse dal set di API di base, come vedrai più avanti, ma la piattaforma ha ottenuto un miglioramento generale delle prestazioni.

Mentre il nuovo .NET 5 viene fornito con l’obiettivo di unificazione della piattaforma, il piano iniziale è cambiato a causa del COVID-19. In effetti, .NET 5 pone le basi dell’unificazione, ma sarà completato con .NET 6 a novembre 2021. Con tale rilascio, otterremo la versione stabile della nuova Universal UI ed anche il supporto per i TFM specifici per Android ( net6.0-android) e iOS (net6.0-ios).

2. Nuove funzionalità in C#

La seconda cosa da tenere a mente riguarda C#. .NET 5 include C# 9, la nuova versione del principale linguaggio di programmazione della piattaforma .NET. Ci sono diverse nuove funzionalità, e di seguito ne troveremo un piccolissimo assaggio, giusto per farci “venir fame”.

Dichiarazioni Top-Level

Tra le nuove funzionalità, una delle più notevoli è l’introduzione di dichiarazioni top-level (o di primo livello). Per sapere cosa sono, diamo un’occhiata al seguente programma:

Ebbene, il precedente blocco potrà essere tranquillamente sostituito dal semplice ed unico:

Le istruzioni top-level consentono di concentrarsi su ciò che conta davvero in piccoli programmi e utilità per console e utilizzare C# con un approccio più orientato agli script.

Tipi di record

Un’altra interessante novità sono i tipi di record. Con i record, possiamo dichiarare un tipo di riferimento immutabile, ovvero un tipo basato sulla classe che non può essere modificato dopo la sua creazione. Un esempio di tipo di riferimento immutabile incorporato è la classe System.String. Dopo aver creato un’istanza di System.String, non è più possibile modificarne il valore.

Considera la seguente dichiarazione del tipo di record:

Possiamo creare un istanza del record Person come faremmo per una classe, ma non ne possiamo alterare ad esempio la proprietà FirstName.

Potremo comunque confrontare due istanze del record Person come si trattassero di tipologie primitive:

Init setters

C# 9 aggiunge anche la funzione di init setters per definire proprietà che possono essere solo inizializzate. Consideriamo la seguente definizione di classe:

Questa classe definisce una persona con proprietà LastName e FirstName che possono essere inizializzate, ma non modificate. La proprietà Address può essere invece modificata in qualsiasi momento:

3. .NET MAUI, the Universal UI

Come terzo punto, dobbiamo sapere che .NET 5 offre un nuovo modo di creare interfacce utente multipiattaforma. Grazie al framework UI dell’app multipiattaforma .NET, noto anche come .NET MAUI, saremo in grado di creare interfacce utente per Android, iOS, macOS e Windows con un unico progetto.

In realtà, questa funzionalità è ancora in corso e verrà rilasciata con .NET 6, ma possiamo iniziare a dare un’occhiata a .NET MAUI per essere pronto quando verrà rilasciato ufficialmente fin dal .NET 5.

.NET MAUI può essere considerato un’evoluzione di Xamarin.Forms, il framework open source per la creazione di app iOS e Android con un’unica base di codice .NET. Ma questo nuovo framework propone un modello universale per la creazione di interfacce utente su piattaforme mobili e desktop.

.NET MAUI

Oltre al buon vecchio Model-View-ViewModel (MVVM) pattern, .NET MAUI supporta anche il recentissimo Model-View-Update (MVU).

4. Supporto Single-File Applications

Altra grande feature che otterremo in .NET 5 è il supporto alle single-file applications, ovvero applicazioni pubblicate e distribuite come un singolo file. Ciò significa che la nostra applicazione e tutte le sue dipendenze sono raggruppate in un unico file.

Ad esempio, supponiamo di eseguire il seguente comando all’interno della cartella del nostro progetto .NET 5:

Otterremo un singolo file contenente l’intera applicazione creata per Linux, tutte le dipendenze usate nel  progetto ed il runtime .NET (–self-contained true). Ciò significa che non è nemmeno necessario installare il runtime .NET sul computer/server di destinazione.

Naturalmente, si potranno specificare questi parametri nella configurazione del progetto:

Notate bene che questa funzionalità non usa lo stesso approccio delle applicazioni a file singolo che puoi compilare in .NET Core 3.1. In .NET Core 3.1. L’applicazione a file singolo è solo un modo per creare pacchetti binari: in fase di esecuzione vengono poi scompattati in una cartella temporanea, caricati ed eseguiti. In .NET 5, l’applicazione a file singolo ha una nuova struttura interna e viene eseguita direttamente senza penalizzazioni delle prestazioni.

A questo link è possibile trovare la documentazione di questa tipologia di rilascio.

5. Tecnologie non più supportate

Per ultimo punto, è obbligo parlare anche di chi esce dal ciclo delle tecnologie supportate, non solo dei nuovi arrivati.

Come detto sopra, la revisione dell’architettura e il tentativo di rendere .NET 5 un vero e proprio framework di programmazione multipiattaforma ha portato alla rimozione di alcune funzionalità supportate in .NET Framework. Diamo una rapida occhiata alle funzionalità rimosse e alle possibili alternative.

Web Forms

Per molto tempo, ASP.NET Web Forms è stata la principale tecnologia per creare interfacce utente web dinamiche. Tuttavia, non è un segreto che la sua durata fosse strettamente legata al destino di .NET Framework. .NET Core non supporta Web Form, quindi il fatto che non sia più supportato in .NET 5 non dovrebbe essere una grande novità.

Tuttavia, abbiamo alcune alternative per creare interfacce utente web. Se stiamo realizzando applicazioni web tradizionali, Razor Pages è una di queste alternative. Se vuoi creare applicazioni a pagina singola, puoi usare invece Blazor.

Windows Communication Foundation (WCF)

Anche WCF, il framework di comunicazione tradizionale per Windows, sarà deprecato. Questo può sembrare un po’ scioccante per gli sviluppatori che lo hanno utilizzato per creare le loro applicazioni orientate ai servizi. Tuttavia, è abbastanza comprensibile se ci rendiamo conto che l’obiettivo principale di .NET 5 è diventare un framework multipiattaforma.

L’alternativa a WCF consigliata da Microsoft è la migrazione a gRPC. Ma se abbiamo nostalgia di WCF o vuoi preparare una transizione graduale, puoi provare il progetto open source CoreWCF.

Windows Workflow Foundation

Infine, .NET 5 non includerà nemmeno Windows Workflow Foundation, la tecnologia del motore del flusso di lavoro disponibile in .NET Framework. Non esiste un sostituto ufficiale per questa tecnologia. Tuttavia, potremo usare un progetto di porting open source, CoreWF, per tentare di spostare i flussi di lavoro esistenti su .NET 5 o crearne di nuovi.

Primi Passi Insieme

Nella seconda parte di questo articolo sperimenteremo insieme la creazione di un nuovo progetto web tramite Visual Studio sfruttando il framework .NET 5 e mettendo subito alla prova il suo aspetto multipiattaforma, pubblicandolo su di una macchina Linux (Ubuntu).

Non temiate la lunghezza della scrollbar verticale del vostro browser, la guida è stata resa il più user-friendly possibile riportando intere porzioni di codice e schermate dei “punti salienti”, ecco spiegato il motivo della sua lunghezza.

Creiamo il nuovo progetto con Visual Studio

Creiamo il nuovo progetto cross platform “MyCrossPlatformApp” partendo dal template “ASP.NET Core Web App”. Se non si trova il suddetto template tra quelli disponibili, assicurarsi di aver selezionato la voce “All platforms” e soprattutto che sia installata sul vostro Visual Studio la relativa SDK.

NB! E’ essenziale selezionare come Target Framework -> .NET 5

Una volta completato lo scaffolding del nuovo progetto possiamo tranquillamente procedere con la sua pubblicazione.

Non sono necessarie ulteriori modifiche essendo il nostro obiettivo ultimo l’esecuzione del progetto su una macchina Linux. Possiamo comunque provare a far partire il progetto per assicurarci che non contenga errori (e che Visual Studio non stia tentando di nascosto di sabotarci…).

Il risultato sarà la classica pagina di benvenuto del template selezionato.

Eradicati i nostri dubbi riguardo la bontà della compilazione del progetto, possiamo finalmente pubblicarlo.

Il risultato della pubblicazione sarà una cartella contenente exe, dll e files di configurazione del nostro applicativo, compilati per il rilascio sulla nostra piattaforma desiderata.

Procediamo dunque cliccando col destro sulla nostra soluzione nell’explorer di Visual Studio e selezionado la voce Publish.

Questo avvierà il wizard di creazione di un nuovo Profilo di Pubblicazione.

Delle varie modalità di pubblicazione, sceglieremo la più grezza e legacy, ovvero la pubblicazione su cartella/folder. In questo modo, lasciando tutte le impostazioni di default proposte nella successiva schermata, avremo il nostro risultato nella sotto cartella di progetto bin\Release\net5.0\publish .

Una volta creato il nuovo profilo di pubblicazione possiamo procedere cliccando dapprima su Publish (1) ed in seguito esaminando il risultato cliccando sulla cartella di output (2).

Et voilà! Una volta terminata la pubblicazione su cartella possiamo chiudere con Visual Studio ed iniziare a dedicarci alla nostra macchina Linux. Essendo il progetto compilato con un framework multipiattaforma (.NET5), nella cartella bin\Release\net5.0\publish avremo tutto il necessario per far partire l’app su qualsiasi Sistema Operativo in cui è installabile la relativa runtime.

Di seguito procederemo con la pubblicazione sull’ultima versione server Debian e l’ultima versione long-term support di Ubuntu Server.

UBUNTU 20.04 LTS &  Apache

Prerequisiti

  1. Salvo particolarissime eccezioni o esigenze, sarebbe ideale cominciare a riscaldarci sul terminale con la solita sfilza di formalismi necessari a partire con tutti i repositori e pacchetti aggiornati:
    1. sudo apt-get update
    1. sudo apt-get upgrade
    1. sudo apt-get dist-upgrade
    1. sudo apt-get autoclean
    1. sudo apt-get autoremove

  2. Nonostante sia un appunto banale e per molti scontato, tengo a precisare che per trasferire il nostro progetto sul server Ubuntu in questa guida faremo uso del protocollo SFTP. Sarà dunque necessario installare sulla macchina in questione la versione server di SSH (se non già presente) con il comando:
    1. sudo apt-get install openssh-server

Step#1 – Installazione Runtimes

Per prima cosa dobbiamo assicurarci che siano installate le runtime di .NET5 e ASP.NET Core 5. Procediamo con il seguente comando per listarle tutte:

dotnet –list-runtimes

Se il risultato dovesse essere il seguente (“command not found”) allora dobbiamo fare un passetto indietro, installandone almeno una.

Installare le runtime .NET non è complicato.
come già visto per l’SSH, possiamo tranquillamente procedere con la loro installazione tramite il packet manager di Ubuntu apt:

  • Runtime .NET5
    sudo apt-get install dotnet-runtime-5.0
  • Runtime ASP.NET Core 5
    sudo apt-get install aspnetcore-runtime-5.0

Con gran probabilità, arrivati a questo punto vi scontrerete con la mancanza dei pacchetti dotnet-runtime-5.0 e aspnetcore-runtime-5.0 negli attuali repository della vostra macchina, come da screen di seguito (“Unable to locate package (…)”) .

Non disperate: oltre alla guida ufficiale Microsoft per l’aggiunta del repository (LINK) potrete nuovamente fare affidamento a quanto segue di questa guida. Infatti, per l’aggiunta dei repository ufficiali Microsoft sul nostro server Ubuntu basterà eseguire i seguenti comandi:

curl -sSL https://packages.microsoft.com/keys/microsoft.asc | sudo tee /etc/apt/trusted.gpg.d/microsoft.asc
sudo apt-add-repository https://packages.microsoft.com/ubuntu/20.04/prod
sudo apt-get update

A questo punto saremo in grado di ritentare con successo l’installazione delle runtime .NET come descritto poche righe addietro, assicurandoci infine che compaiano nella lista fornita dal comando:

dotnet –list-runtimes

Step#2 – Installazione & Config. Apache

Dobbiamo sapere che le applicazioni .Net vengono eseguite su server Kestrel. Il nostro web server Apache fungerà da server proxy e gestirà il traffico dall’esterno della macchina reindirizzandolo al server Kestrel. Possiamo dunque vedere il nostro web server Apache come un middle layer per l’applicazione .Net .

Di seguito vedremo come installare e configurare un’installazione pulita di Apache sul nostro server Ubuntu per servire la nostra applicazione.

Diamo quindi i seguenti comando per installare Apache ed abilitare in seconda battutati i moduli proxy,proxy_http, proxy_html e proxy_wstunnel.

sudo apt-get install apache2
sudo a2enmod proxy proxy_http proxy_html proxy_wstunnel
sudo a2enmod rewrite
systemctl restart apache2

Possiamo confermare la corretta installazione di Apache navigando con un browser all’indirizzo del nostro server. Se tutto è andato liscio, il risultato sarà la pagina di default di Apache con tanto di messaggio evidenziato IT WORKS come da screen:

Arrivati a questo punto,dovremo creare un file conf per configurare il nostro proxy su Apache.
Forniamo dunque il seguente comando per entrare nell’editor di testo nano :

sudo nano /etc/apache2/conf-enabled/netcore.conf

Copiamo ora la seguente configurazione nel file vuoto appena aperto per poi salvarlo con la combinazione (per chi non la conoscesse) CTRL+O -> INVIO -> CTRL+X .

NB! La porta 5000 è quella usata di default dal server Kestrel con cui si eseguono le applicazioni .Net

<VirtualHost *:80> 
   ServerName localhost 
   ProxyPreserveHost On 
   ProxyPass / http://127.0.0.1:5000/
   ProxyPassReverse / http://127.0.0.1:5000/ 
   RewriteEngine on 
   RewriteCond %{HTTP:UPGRADE} ^WebSocket$ [NC] 
   RewriteCond %{HTTP:CONNECTION} Upgrade$ [NC] 
   RewriteRule /(.*) ws://127.0.0.1:5000/$1 [P] 
   ErrorLog /var/log/apache2/netcore-error.log 
   CustomLog /var/log/apache2/netcore-access.log common 
</VirtualHost>

Ora con il seguente comando ci assicuriamo che non siano presenti errori nella configurazione appena create su Apache:

sudo apachectl configtest

A prescindere dai vari warning segnati, se riceviamo infine il messaggio Syntax OK possiamo procedere con il riavvio di Apache:

sudo service apache2 restart

Effettuando nuovamente la navigazione con un browser puntando all’indirizzo della nostra macchina, ci accorgeremo di non avere più la pagina di default di Apache esposta, bensì un messaggio di Service Unavailable . Risultato del tutto normale poiché Apache sta già funzionando da server proxy, mirando in realtà alla porta 5000 della macchina sulla quale non è ancora stata avviata la nostra applicazione .Net con Kestrel.

Step#3 – Spostamento Progetto & Creazione Servizio

E’ giunto ora il momento di riversare il nostro progetto compilato sul nostro server Linux.

Come anticipato nelle premesse di questa guida, uno degli strumenti più comodi per chi lavora su una macchina Windows è WinSCP, con il quale potremo trasferire files tramite SFTP.

Prima di spostare i files, sarebbe utile creare preventivamente la cartella di destinazione del progetto, che nel nostro caso si chiamerà MyCrossPlatformApp e sarà nella home della mia utenza cerini.

cd /home/cerini
mkdir MyCrossPlatformApp

Ecco che una volta connessi con WinSCP potremo spostare comodamente il progetto nella cartella appena creata anche con un semplice Drag&Drop.

Possiamo finalmente testare il corretto funzionamento della nostra soluzione cross platform e della bontà della configurazione del reverse proxy di Apache avviando l’applicazione e facendo di conseguenza partire il server Kestrel sulla porta 5000 col comando:

dotnet MyCrossPlatformApp.dll

Visitando nuovamente col browser la nostra macchina, il messaggio di “Service Unavailable” sarà soltanto un lontano ricordo.

Rimane soltanto un ultimo “problema”:
l’esecuzione dell’applicazione è contestualizzata all’istanza di terminale che ha lanciato il comando dot, dunque fin quando non ne termineremo l’esecuzione con la combinazione di comandi CTRL+C, l’istanza di questo terminale sarà occupata da questo unico job, impedendoci di usarla per qualsiasi altro task.

E’ qui che entrano in gioco i service di Ubuntu. Un service (o servizio se preferite in italiano) su Ubuntu costituisce la gestione regolarizzata di uno o più processi in totale autonomia dell’OS ed in background.

Tra i vari parametri configurabili di un servizio, troviamo quelli che ne definiscono il tempo di esecuzione, partenza e comportamento in caso di errore, come ad esempio il riavvio od un nuovo tentativo ad una certa distanza temporale.

I servizi su Ubuntu sono facilmente gestibili con il comando service o il suo sinonimo systemctl, fornendo come parametro l’operazione da effettuare sul servizio specificato:enalbe, disable, stop, start, restart e status.

Creiamo dunque il file di configurazione per il servizio che si occuperà di avviare (e tenere avviata) la nostra applicazione .NET sul server.
Come in precedenza, usiamo l’editor nano per creare il suddetto file:

sudo nano /etc/systemd/system/MyCrossPlatformApp.service

Avviato l’editor del nuovo file vuoto, possiamo copiare al suo interno la seguente configurazione, salvandola infine con CTRL+O -> INVIO -> CTRL+X :

[Unit]

Description=ASP .NET Web Application

[Service]

WorkingDirectory=/home/cerini/MyCrossPlatformApp

ExecStart=/usr/bin/dotnet /home/cerini/MyCrossPlatformApp/ MyCrossPlatformApp.dll

Restart=always

# Restart service after 10 seconds if the dotnet service crashes:

RestartSec=10

SyslogIdentifier=dotnet5-demo

User=www-data

Environment=ASPNETCORE_ENVIRONMENT=Production

[Install]

WantedBy=multi-user.target


Tra le config più interessanti troviamo la WorkingDirectory con cui diamo il contesto della cartella di esecuzione, ExecStart che definisce il vero e proprio comando da eseguire (dotnet + dll), Restart e RestartSec con cui definiamo il comportamento in caso di errore/crash del servizio.

Possiamo dunque abilitare il servizio e tentarne l’avvio:

sudo systemctl enable MyCrossPlatformApp

sudo systemctl start MyCrossPlatformAppt

Controlliamo infine che sia correttamente partito con:

sudo systemctl status MyCrossPlatformApp

La prova del nove la potrete tranquillamente avere navigando come al solito dal vostro browser.

Provare per credere! E se vi sentite fortunati (e ne avete la possibilità) provate a riavviare il vostro server: il servizio avvierà la vostra applicazione .NET automaticamente una volta ripartito Ubuntu.

Articolo a cura di Luca Cerini, Senior Developer in Orbyta Tech, 07/09/2021

#jointherevolution

Fonte: https://www.networkworld.com/article/2878394/mit-researchers-show-you-can-be-identified-by-a-just-few-data-points.html

Network Science e Social Network Analysis

Introduzione

I network (o reti) sono uno strumento potente ed efficace per rappresentare la realtà che ci circonda e sono infatti presenti in quasi ogni aspetto della nostra vita. Amici, parenti, il Web, le strade di una città… tutto può essere modellato sotto forma di network. Lo scopo di questa rappresentazione è quello di studiare un sistema cercando di catturarne la sua complessità e le relative cause. In generale, un network è la semplice descrizione di un insieme composto da entità interconnesse, che chiamiamo nodi, e le loro connessioni/relazioni, che chiamiamo link. I nodi possono rappresentare ogni genere di entità: persone, luoghi, siti web, cellule, etc. Le relazioni a loro volta possono esprimere ogni tipo di interazione/scambio/flusso che avviene fra due entità, quindi pagamenti, scambi di messaggi, like su Facebook, etc.

Nota: In questo articolo i social network vanno intesi come reti sociali e non come i siti di social networking come Facebook e Twitter.

I network sociali sono un particolare tipo di network dove i nodi sono persone interconnesse da un qualche tipo di relazione. Ci sono tantissimi tipi di social network, al punto che questa è la categoria di network più studiata in assoluto. Per esempio la sociologia, il ramo da cui è partito lo studio delle reti sociali, cerca di stabilire delle regole emergenti dal comportamento collettivo degli individui.  Nell’ambito della medicina si può studiare la propagazione di malattie attraverso una rete sociale, in economia si studia come il comportamento di un individuo influenza quello di un altro sulla base di meccanismi di incentivi ed aspettative degli altri. Nel campo della ricerca i social network vengono utilizzati per studiare gli autori più influenti e come hanno collaborato fra loro nello studio di un determinato argomento.

La complessità delle connessioni della società moderna, data da fenomeni come internet, crisi finanziarie o epidemie è data dal comportamento aggregato di gruppi di persone le cui azioni hanno conseguenze sul comportamento di tutti gli altri. Il crescente interesse verso lo studio di tale complessità ha reso la Social Network Analysis uno degli strumenti di visualizzazione e rappresentazione dei sistemi complessi più utilizzati.

Teoria dei Grafi

La Social Network Analysis ed in generale tutta la Network Science si basa sui concetti chiave della teoria dei grafi di nodo e legame, andando ad ampliare questa branca della matematica con una serie di termini e metriche propri, dati dallo sviluppo autonomo di questo campo di ricerca.

L’avvento della teoria dei grafi si riconduce a un aneddoto del 1736 della città Prussiana di Königsberg, città natale di Immanuel Kant e Leonhard Euler, per noi Eulero. Eulero si trovò ad affrontare un problema matematico legato alla città di Königsberg, la quale era divisa ai tempi in quattro settori dal fiume Pregel, connessi tra loro da sette ponti. Solo cinque di questi sono sopravvissuti ai bombardamenti della Seconda guerra mondiale e allo stesso modo molti edifici sono stati demoliti. Il problema con cui si cimentò Eulero, irrisolto fino a quel momento, era quello di collegare tutti e sette i ponti potendo passare solo una volta su ciascuno di questi.

Eulero formalizzò il problema ricorrendo a un grafo i cui nodi erano i quattro settori della città, e i collegamenti erano i ponti. Dimostrò così che un tale percorso esiste solo se tutti i nodi hanno grado (numero di link) pari, tranne la partenza e l’arrivo. Questo tipo di percorso, rinominato poi Eulerian path in suo onore, non è effettivamente possibile in questo sistema in quanto ognuno dei quattro nodi ha un numero dispari di connessioni. La vera novità di questo approccio fu l’aver formalizzato in forma topologica il problema, andando a definire questo tipo di percorso come una proprietà intrinseca del grafo.

La forza dei legami deboli e la Small-World property

La teoria della “forza dei legami deboli” nasce da uno studio di Mark Granovetter degli anni 60 diventato poi un classico della sociologia. Granovetter, attraverso una serie di interviste, andò a studiare come le persone che avevano recentemente cambiato mestiere a Boston fossero venute a conoscenza della nuova opportunità. La maggior parte di queste persone erano immigrati irlandesi, i quali erano soliti trascorrere una buona quantità di tempo nei pub. Il lavoro ed in particolare quello edilizio, settore principale di queste persone, era molto instabile portando a frequenti passaggi dallo stato di occupazione a quello di disoccupazione. L’obiettivo iniziale della ricerca era di capire il ruolo delle conversazioni nei pub nella ricerca del nuovo lavoro.  Scoprì che molte persone avevano trovato il nuovo lavoro attraverso i contatti personali e pertanto decise di soffermarsi proprio su questi. Emerse dalla sua ricerca che questi contatti erano perlopiù conoscenti piuttosto che amici stretti. Solo il 30% degli intervistati aveva trovato lavoro attraverso i contatti più stretti. 

Fonte: https://www.nature.com/articles/srep05739/figures/2

Da qui la distinzione tra legami forti e deboli. I legami forti erano amici e parenti, mentre i legami deboli semplici conoscenti. Granovetter teorizzò quindi che i legami forti sono maggiormente disposti a fornire un supporto emotivo, ma appartenendo alla stessa cerchia di chi in questo caso sta cercando lavoro, hanno meno possibilità di fornire informazioni che non conosciamo. I legami deboli a differenza, appartenendo a cerchie da noi distanti sono in contatto con realtà a noi sconosciute ed hanno per questo accesso a informazioni nuove. Le implicazioni di questo studio sono vastissime e tuttora oggetto di studio. Il perché i social media siano diventati uno strumento così potente è riconducibile proprio al concetto di legame debole. Essenzialmente, i social media non fanno altro che mantenere ed amplificare i legami deboli, definiti in questo caso come legami sociali che non richiedono alcun attaccamento emotivo, necessità di comunicare o tempo da dedicare. Nonostante questo, risultano estremamente potenti in quanto fungono da canali per il passaggio di informazioni tra persone distanti sia in termini fisici che sociali (es reddito, cultura, etc). Quando due persone comunicano attraverso un legame debole, l’informazione che passa attraverso di esso è di solito nuova, e proviene da un diverso punto di vista.

Dal punto di vista dei network i legami forti (come quelli tra coniugi e amici intimi) tendono a riunire i nodi in cluster stretti e densamente interconnessi. All’interno di questi cluster si sviluppa una conoscenza specifica ma non si generano conoscenze “distanti” a livello di contenuti. Poiché diverse nicchie conservano diversi tipi di conoscenza, sono i collegamenti tra i questi sub-network a permettere la condivisione. Tali collegamenti sono chiamati ponti. Granovetter ha quindi capito che nelle reti sociali i legami che tengono insieme la rete stessa sono, paradossalmente, i legami “deboli”.

La famosa teoria dei sei gradi di separazione si basa proprio su questo concetto, ovvero che attraverso i semplici legami deboli due persone qualunque del globo sono in grado di entrare in contatto mediante un massimo di sei persone. L’esperimento fu condotto negli anni 60 da Stanley Milgram, data a cui risale la prima prova empirica dell’esistenza dei cosiddetti network small world. L’idea era quella di misurare la distanza sociale fra sconosciuti. Furono quindi selezionate 160 persone in Kansas e Nebraska per mandare una lettera a una persona selezionata in Massachussets. Ogni persona doveva mandare la lettera alla persona di sua conoscenza che reputava più adatta a raggiungere il destinatario. In questo caso solo il 26% di lettere arrivarono a destinazione correttamente, mostrando però che il numero medio di intermediari erano di poco superiori a 6. L’esperimento fu ripetuto nel 2003 usando però le email. Anche in questo caso si mise in luce il fatto che il path medio in termini di persone erano 5-7 individui. La maggior parte dei network del mondo reale hanno il percorso critico (il più veloce) medio molto breve, secondo quella che viene definita small word property. Questa proprietà rende le reti molto efficienti in termini di velocità di propagazione delle informazioni.

Fonte: https://mathspig.wordpress.com/tag/6-degrees-of-separation-explained/

Clustering

Una caratteristica che si osserva nelle reti sociali è che gli individui tendono ad aggregarsi in comunità, dette cluster. Questa proprietà, già nota nella sociologia come transitività, è stata poi ripresa nella network science con il nome di clustering. Come tale, questo coefficiente esprime la misura di quanti amici di un individuo sono a loro volta amici fra loro. A livello di rete si calcola come frazione di tutti i possibili triangoli (o triadi) che esistono nella rete, mentre a livello di singolo nodo corrisponde alla frazione di tutti i possibili triangoli che contengono il nodo in esame.

Una delle modalità per cui si formano cluster è quella della vicinanza a un altro nodo. Anche questo concetto è ampiamente trattato nella Social Network Analysis, e prende il nome di assortatività. Essa esprime la preferenza per un nodo ad interagire con un altro nodo avente caratteristiche simili. Nel caso delle reti sociali queste caratteristiche possono essere sesso, età, luogo, argomenti di interesse e così via. Alcuni ricercatori hanno visto che è possibile stabilire con una certa accuratezza l’orientamento politico di un individuo anche se non presente nel suo profilo guardando le caratteristiche della sua cerchia di amicizie. Una regola empirica è che se due persone sono simili in qualche modo, è più probabile che si selezionino a vicenda e diventino due nodi interconnessi. A questo aspetto si lega la teoria delle bolle di filtraggio di Eli Pariser che sarebbe interessante approfondire, ma questo esula dal tema dell’articolo.

Watts–Strogatz Model

Per studiare come emergono le caratteristiche di un network, come la small world property o il clustering, si utilizzano degli algoritmi di simulazione che generano dei modelli. Questi modelli vengono poi comparati con i dati reali per capirne le differenze e studiarne i meccanismi.

Il modello Watts–Strogatz (1998) è un network avente proprietà small world che allo stesso tempo possiede un buon coefficiente di clustering. Può essere generato in modo sperimentale risultando in un network dove la maggior parte dei nodi sono collegati a un numero relativamente ristretto di vicini in maniera piuttosto regolare, con alcune eccezioni dati da legami deboli con nodi distanti. Watts e Strogatz notarono che nel mondo reale non si riscontravano pressoché in nessuna situazione né network regolari, dove tutti i nodi sono strettamente legati ai propri vicini, né network completamente randomici, dove invece i collegamenti fra nodi non seguono nessuna logica particolare. Osservarono infatti che la realtà circostante era sempre una via di mezzo fra questi due tipi di network, ovvero una forte aggregazione in cluster tipica di un network regolare e allo stesso tempo una forte propensione alla propagazione di informazioni secondo la small world property, tipica invece di un random network. La soluzione che proposero è quindi l’interpolazione di questi due estremi.

L’algoritmo di generazione di un modello Watts–Strogatz parte da un network regolare dove tutti i nodi sono connessi ai propri vicini, e in modo randomico elimina alcuni di questi collegamenti andandoli a sostituire con collegamenti a nodi più distanti. In questo modo le proprietà topologiche locali fra nodi vicini rimangono intatte, ma si permette ai legami deboli di fungere da collegamento con nodi anche molto distanti.

. 

Fonte: https://www.nature.com/articles/30918

Il problema delle reti Watts-Strogatz è dato dall’inaccuratezza nella distribuzione dei gradi (il numero di collegamenti di ciascun nodo).  Il numero di vicini di un nodo è infatti circa lo stesso per tutti i nodi, e differisce leggermente dal valore medio, seguendo così una distribuzione di Poisson. Risulta così un network molto omogeneo, che non rispecchia però la distribuzione delle reti reali. Nel mondo reale si assiste infatti a una fortissima disuguaglianza fra il grado dei nodi, secondo quella che viene definita “legge di potenza”, ovvero ci sono molti nodi con poche connessioni e pochi nodi con molte connessioni. Barabasi e Albert hanno considerato questo aspetto andando a creare un modello che si basa sulla legge di potenza.  Una distribuzione che segue la legge di potenza è denominata power law distribution, distribuzione a invarianza di scala (scale-free distribution) o anche distribuzione di Pareto. La peculiarità di questo tipo di distribuzioni sta proprio nell’assenza di una scala caratteristica dei fenomeni. 

Fonte: http://networksciencebook.com/chapter/4#hubs

 Scale free and Barabasi-Albert Model

Il modello Barabasi-Albert (1999) si discosta dal modello Watts-Strogatz aggiungendo realismo nel meccanismo di clustering dei nuovi nodi. Mentre il modello Watts-Strogatz parte da un set di nodi dall’inizio alla fine, il Barabasi-Albert aggiunge i nodi uno per volta rendendo il modello dinamico.

L’idea alla base è di generare una rete secondo una progressiva aggregazione di nodi seguendo una logica di preferenza verso i nodi più grandi, chiamata attaccamento preferenziale. In altre parole, quando si aggiungono nuovi nodi, questi andranno a connettersi tendenzialmente a nodi già largamente interconnessi, che vengono definiti hub.

Fonte: https://makeagif.com/i/0Ccn3L

Questo principio viene anche definito come “rich get richer”, ovvero i nodi più grandi tendono a diventare ancora più grandi. La probabilità che un nuovo nodo si colleghi a uno vecchio è proporzionale al grado del vecchio nodo. Per esempio un nodo con grado 10 è 10 volte più probabile che venga raggiunto da un nuovo nodo rispetto a un altro nodo avente grado 1. La proprietà di small world viene in questo caso garantita proprio dagli hub, che fungono da ponte principale fra coppie di nodi non collegati.

Fonte: https://en.wikipedia.org/wiki/Mediation-driven_attachment_model

Questo tipo di modello trova un ampissimo riscontro nel mondo reale, come per esempio le pagine Web. Numerosi studi hanno dimostrato che più un sito è citato, ossia possiede più hyperlink, e più è probabile che verrà citato nuovamente e viceversa. La causa sottostante a questo fenomeno è spiegata dal fatto che più hyperlink ha un sito web e più è visibile, di conseguenza è più probabile che il sito riceva altri hyperlink.  Questo stesso meccanismo si manifesta allo stesso modo nella legge di Pareto, per cui la ricchezza tende a concentrarsi nelle mani di pochi individui molto ricchi mentre è molto scarsa nel resto della popolazione (il 20% della popolazione possiede l’80% delle risorse, oppure il 20% delle parole di una lingua compongono l’80% del parlato).

Misure di centralità

Spostando l’analisi a livello di singolo nodo all’interno della rete, la SNA permette di studiare le relazioni di ogni attore nella rete mostrandone le gerarchie e fornendo un quadro per spiegare la struttura e l’evoluzione dei singoli nodi e dei gruppi di nodi. Le reti sociali sono sistemi complessi e come tali necessitano di una moltitudine di metriche e strumenti di analisi. Le principali sono le centralità, ma vi sono anche la distribuzione dei gradi, la topologia della rete locale, la struttura della comunità e l’evoluzione della rete.

La prima domanda che potrebbe sorgere analizzando una rete è: chi è il più importante?

Ovviamente la risposta è dipende, e qui andremo a spiegare brevemente perché.

Generalmente sono le misure di centralità a rispondere a questa domanda. Le misure di centralità sono usate per calcolare l’importanza di un individuo all’interno del network, tuttavia sono vari i criteri di importanza: potere, l’influenza, o altre caratteristiche individuali delle persone. Per questo motivo ci sono diverse misure di centralità della rete. Analizzeremo le 4 principali.

Degree centrality

Se si vuole misurare il numero di connessioni che ha un individuo allora la degree centrality fa al caso nostro. Su Facebook per esempio corrisponderebbe al numero dei nostri amici. E’ logico pensare che più una persona abbia collegamenti e più abbia influenza sulle altre persone. Ma non è necessariamente così.  Scott Adams, il creatore del fumetto Dilbert, sostiene che il potere di una persona è inversamente proporzionale al numero di chiavi nel suo portachiavi. Un custode ha le chiavi di tutti gli uffici e nessun potere. L’amministratore delegato non ha bisogno di una chiave, c’è sempre qualcuno ad aprirgli la porta. Effettivamente sono molti i casi in cui una persona di potere ha relativamente pochi contatti e per questo sono necessarie altre metriche di centralità.

Una breve digressione può essere fatta riguardo le due sottomisure della degree-centrality date dal numero di link in entrata o in uscita di un nodo, ovvero centralità in-degree e out-degree. Questo aspetto è interessante perché viene usato per misurare il livello di fiducia verso un individuo della rete. Semplificando molto (in quanto bisognerebbe tenere conto di molti altri aspetti), un attore con un basso valore di fiducia può essere identificato da un alto valore di centralità out-degree a cui corrispondono bassi valori di centralità out-degree degli attori con cui comunica. Ciò può essere spiegato dal fatto che questo attore si sente sicuro nel diffondere informazioni, ma gli altri attori non diffondono queste informazioni perché non reputano affidabile tale informazione.

Fonte:https://cambridge-intelligence.com/social-network-analysis/

Closeness centrality

Un altro modo di misurare la centralità è quello di guardare quanto un nodo è “vicino” agli altri nodi. La closeness centrality è usata per misurare la lunghezza media del percorso più breve da un nodo verso un qualunque altro nodo. Maksim Tsvetovat e Alexander Kouznetsov la definiscono la misura dei gossippari poiché rappresenta l’abilità di un attore di trasmettere o condividere informazioni da un lato del network all’altro. Minore è la distanza totale nella rete e più la closeness centrality sarà alta. In altre parole, rappresenta la velocità con cui l’informazione può raggiungere altri nodi da un dato nodo di partenza: i gossippari fanno arrivare le informazioni molto più velocemente degli altri.

Betweeness Centrality

La betweeness centrality è una misura che viene usata per studiare il ruolo di un nodo nella propagazione di una informazione. Se un nodo è l’unico collegamento ponte fra altri due nodi si può dire che abbia una posizione in qualche modo privilegiata o strategica. La Betweeness Centrality va a misurare proprio questo valore. Viene infatti spesso usata per misurare il traffico nei network di trasporti. Si calcola andando a contare quante volte un nodo è attraversato da un percorso critico (il percorso più breve, o anche Eulerian path) rispetto al totale dei percorsi critici.

Se c’è un buco strutturale (una forma di discontinuità nel flusso di informazioni) in una rete, la persona che detiene la posizione di intermediazione può assumere una posizione strategica per collegare o scollegare i nodi in un gruppo, e quindi gode di un vantaggio competitivo rispetto agli altri nodi. Gli attori con un alto valore di betweeness centrality sono come dei guardiani che controllano il flusso di informazioni tra gli altri. 

Generalmente i nodi aventi alta betweeness sono quelli aventi anche alta degree centrality, in quanto sono i cosiddetti hub che abbiamo descritto sopra. Questo non è però il caso in cui un nodo va a collegare due regioni del network diverse e semplicemente scollegate. In questo caso il nodo può avere pochi collegamenti con altri nodi, ma fungere da ponte tra due regioni molto distanti della rete.

Cercando di mettere insieme i pezzi, si può dire che un nodo avente una alta betweeness centrality può corrispondere a uno dei due estremi di un legame debole di Granovetter, che a sua volta garantisce a un network la proprietà di small world vista sopra.

Eigenvector Centrality

Il detto “dimmi chi sono i tuoi amici e ti dirò chi sei” si traduce nella social network analysis nella centralità dell’autovettore. Questa misura ci dà informazioni su un attore sulla base delle relazioni che ha con i suoi vicini, cioè i suoi contatti più stretti. Di nuovo Maksim Tsvetovat e Alexander Kouznetsov hanno trovato l’analogia perfetta, ovvero Don Vito Corleone. Egli infatti con le misure di centralità precedenti non si sarebbe potuto riconoscere come il boss, poiché non ha molti collegamenti diretti e non scambia molte parole in giro. Ecco quindi l’utilità dell’eigenvector centrality. Sostanzialmente si basa sull’algoritmo di Bonacich, che iterativamente calcola un peso per ciascuno dei link di un nodo basandosi su quello degli attori vicini. Può essere definita come un’estensione della degree-centrality poiché va a guardare proprio questa metrica nei vicini, ed infatti un attore con alta eigenvector centrality è connesso a nodi aventi molte connessioni a loro volta.

Pagerank

Simile alla Eigenvector Centrality in quanto si basa sullo stesso principio di calcolo dei pesi ricorsivo è il pagerank, l’algoritmo sviluppato da Larry Page come parte essenziale delle prime versioni di Google per indicizzare le pagine Web. Il PageRank è una misura di centralità che calcola il prestigio di un nodo, inteso come pagina Web. Le pagine Web sono i nodi di un grafo orientato dove i link fra nodi sono gli  hyperlink alla pagina stessa (link alla pagina presenti su altre pagine web). Il grado di un nodo è calcolato come la probabilità che una persona capiti casualmente su quella pagina cliccando un link. 

Questo processo è conosciuto come random walk, ed è una semplice simulazione di come l’utente naviga nel web. La pagina con il più alto indice di ranking è quindi la destinazione più probabile. Si potrebbe pensare perchè non usare direttamente la in-degree centrality allora? Il Pagerank è in questo caso molto più efficiente perché tiene conto dell’importanza della pagina da cui proviene l’hyperlink. Ovvero se la pagina target viene citata dal Wall Street Journal sarà molto più alta in ranking rispetto a una pagina citata da un sito di spam. 

Conclusione 

Come abbiamo visto in questo articolo la SNA è uno strumento di analisi estremamente potente ed affascinante che può essere utilizzato in concomitanza con molti altri modelli nel contesto della data science. Uno di questi è la teoria dei giochi, con la quale è possibile applicare alcune delle analisi di cui abbiamo parlato, come vedremo nei prossimi articoli. 

Fonti

  • Albert, and Barabasi. Network Science. Cambridge University Press, 2016.
  • Easley, David, and Jon Kleinberg. Networks, Crowds, and Markets: Reasoning about a Highly Connected World. Cambridge University Press, 2010.
  • Menczer, Filippo, et al. A First Course in Network Science. Cambridge University Press, 2020.
  • Tsvetovat, Maksim, and Alexander Kouznetsov. Social Network Analysis for Startups. O’Reilly, 2011.
  • Zinoviev, Dimitry. Complex Network Analysis in Python. Adaobi Obi Tulton, 2018.

Articolo a cura di Giovanni Ceccaroni, Data Scientist in Orbyta Tech, 22.06.2021

#jointherevolution

Isolation levels on SSMS

“La palla è mia!”
“Non è vero, l’ho vista prima io!”
“Sì, ma io corro più veloce e l’ho presa per primo!”

Se potessimo parlare la lingua del database, probabilmente sentiremmo in continuazione discussioni come questa. Nel mondo ideale gli utenti accedono ai nostri dati in buon ordine, uno alla volta, e poi chiudono la porta quando escono, ma nel mondo reale può capitare che gli stessi dati vengano interrogati o addirittura modificati da persone differenti nel medesimo momento.

Cosa succede allora in questi casi? Chi ha la precedenza? Quello che ha acceduto per primo al dato? O quello che l’ha modificato per primo? E cosa viene visualizzato da una query che interroga un dato modificato da un altro? Si vede sempre lo stato più aggiornato?

L’intento di questo articolo è di fornire qualche risposta a simili domande.

Le transazioni

Per prima cosa dobbiamo prendere confidenza con un’entità fondamentale per il discorso che stiamo per affrontare, vale a dire la transazione. Con transazione si intende una serie di operazioni che vengono raggruppate tra loro: in questo modo, se anche solo una di esse va in errore, vengono annullate tutte quante così da lasciare i dati in uno stato consistente, cioè com’erano prima che cominciasse la prima delle operazioni della transazione.

Aiutiamoci subito con un esempio pratico: Emma deve effettuare un bonifico a Marta. L’operazione di trasferimento di denaro da un conto all’altro si articola in due semplici passaggi, cioè

  • prelevare la somma dal conto di Emma
  • versarla sul conto di Marta

Non serve un gigantesco sforzo di immaginazione per capire che queste due operazioni non possono essere disgiunte una dall’altra; o vanno a buon fine entrambe (e allora viene eseguita l’operazione di commit) o devono fallire entrambe (e allora viene eseguito un rollback, che riporta tutto a com’era prima). Supponiamo infatti che per un problema tecnico non si riesca a versare il denaro sul conto di Marta: se le due operazioni non fossero legate (quindi raggruppate in una transazione), potremmo avere la sgradevolissima situazione in cui, al verificarsi di un errore tra l’operazione a. e l’operazione b., i soldi non sarebbero né sul conto di Emma né sul conto di Marta perché prelevati da un conto ma non ancora versati sull’altro.

Le proprietà ACID

Perché una transazione si possa definire tale deve rispettare le proprietà ACID, ovvero

  1. Atomicità
  2. Consistenza
  3. Isolamento
  4. Durabilità

L’atomicità è la proprietà che abbiamo appena visto, ovvero l’impossibilità di un’esecuzione parziale delle operazioni raggruppate nella transazione. È nota anche come la regola del “o tutto o niente”.

Consistenza significa che una transazione deve lasciare i dati in uno stato coerente, quindi rispettando, per esempio, i vincoli di integrità.

L’isolamento consiste nel separare una transazione da quello che sta succedendo con le altre transazioni eseguite parallelamente, in modo che una transazione fallita non impatti sulle altre transazioni in esecuzione (e questo sarà il punto principale sviluppato in questo articolo).

Durabilità (o persistenza) significa non perdere i dati una volta che sono stati scritti, o meglio, non perderli dal momento in cui la base dati si impegna a scriverli.

Scegliere un isolation level

Un livello di isolamento inferiore (quindi più permissivo) aumenta la capacità di accedere ai dati contemporaneamente da parte di più utenti, ma aumenta il numero di effetti di concorrenza, come la dirty read che vedremo in dettaglio più avanti. Al contrario, un livello di isolamento più elevato riduce i tipi di effetti di concorrenza che gli utenti potrebbero riscontrare, ma richiede più risorse di sistema e aumenta le possibilità che una transazione ne blocchi un’altra. Il livello di isolamento più alto infatti garantisce che una transazione recuperi esattamente gli stessi dati ogni volta che viene ripetuta un’operazione di lettura, ma lo fa eseguendo dei blocchi (lock) che potrebbero avere un impatto su altri utenti nei sistemi multiutente.

Effetti di concorrenza

In questa sezione vedremo i tre principali tipi di scenari che possono presentarsi in un livello di isolamento non elevato quando due transazioni sono in concorrenza tra loro.

Dirty read

Questa eventualità può verificarsi se la transazione 1 ha la possibilità di visualizzare un dato modificato dalla transazione 2 quando quest’ultima non è stata ancora confermata (ovvero non è stato eseguito un commit). Se qualcosa nella transazione 2 va storto, la transazione 1 avrà avuto accesso a un dato che in teoria non è mai esistito. Avendo la possibilità di guardare dati non ancora validati dal marchio di una commit, in una dirty read la lettura non viene fatta dal disco o dalla cache, ma direttamente dal transaction log.

Es. Supponiamo che il redattore di un giornale possa leggere l’articolo di un suo giornalista mentre questi lo sta scrivendo. Il giornalista aggiunge una frase, il redattore stampa l’articolo per guardarselo a casa, il giornalista ci ripensa e toglie la frase di prima. Il redattore avrà quindi stampato l’articolo con una frase che non verrà mai pubblicata.

Nonrepeatable read

In questo caso la transazione 1 legge un dato, la transazione 2 lo modifica e viene chiusa, la transazione 1 (che è sempre rimasta aperta), riesegue la stessa query ottenendo un risultato differente rispetto a quello ottenuto in prima istanza.

Es. Riprendendo l’esempio di prima, il redattore (sempre con la capacità di vedere in tempo reale le modifiche ai pezzi che i giornalisti stanno scrivendo), deve stampare due copie di un articolo da distribuire ai suoi due assistenti. Il redattore stampa la prima copia, il giornalista aggiunge una frase, il redattore stampa la seconda copia che invece contiene la frase appena aggiunta. I due assistenti si troveranno così per le mani due versioni diverse dello stesso articolo.

Phantom read

Lo scenario qui è quasi un caso particolare della nonrepeatable read, ovvero: la transazione 1 esegue una query che ritorna un set di dati, la transazione 2 inserisce dei nuovi record, la transazione 1 (che anche in questo caso non è mai stata chiusa) riesegue la query di prima trovando dei dati in più rispetto all’interrogazione precedente.

Es. Il redattore vuol fare avere ai suoi due assistenti una copia di tutti gli articoli pubblicati da uno dei suoi giornalisti. Il redattore stampa gli articoli per il primo assistente, nel mentre il giornalista in questione pubblica un nuovo articolo; quando il redattore stampa la seconda copia del plico per l’altro assistente, questo conterrà un articolo in più. Di nuovo i due assistenti avranno in mano dei dati discordanti. Il caso è molto simile a prima ma la vera differenza sta nel fatto che mentre la nonrepeatable read riguardava l’aggiornamento di un articolo (ovvero l’update di un record) ma entrambi gli assistenti avevano in mano lo stesso numero totale di articoli, la phantom read implica una differenza nel numero di articoli totali in possesso dei due assistenti (ovvero del numero totale di record).

In breve

Parlando di isolamento delle transazioni, questi tre casi sono rappresentati in una specie di ordine gerarchico, dal più sporco al meno sporco. Un livello di isolamento in cui si può verificare uno dei tre casi implica a cascata che si possano verificare anche quelli “meno sporchi”, per il principio secondo cui se rapini una banca probabilmente non ti fai molti scrupoli a parcheggiare in divieto di sosta. Un livello di isolamento che consente dirty read consentirà pertanto anche phantom read, ma non vale il viceversa.

I livelli di isolamento

Non è affatto detto che vedere sempre un dato al massimo livello di aggiornamento sia un fatto negativo, ma ci sono dei casi in cui la priorità è avere un set di dati stabili, indipendentemente da quello che stanno facendo le transazioni concorrenti. Per questo motivo su SSMS abbiamo la possibilità di settare cinque diversi livelli di isolamento a seconda delle nostre esigenze, ciascuno dei quali consente o inibisce il verificarsi degli scenari descritti prima.

Dirty Read Nonrepeatable Read Phantom Read
Isolation level      
Read uncommitted Permesso Permesso Permesso
Read committed Non permesso Permesso Permesso
Repeatable read Non permesso Non permesso Permesso
Serializable Non permesso Non permesso Non permesso
Snapshot Non permesso Non permesso Non permesso

Su SSMS il comando per settare il livello di isolamento è il seguente

SET TRANSACTION ISOLATION LEVEL <TuoLivello>;

Read uncommitted

Come si può notare dalla tabella, questo livello di isolamento è il più permissivo di tutti, dato che consente addirittura la dirty read, ovvero la lettura di dati modificati da un’altra transazione attualmente in corso. Guardiamo con un esempio quello che succederebbe con due transazioni in concorrenza tra loro.

Figura 1

All’inizio sul conto di Emma ci sono 3000 €. La banca apre prima transazione, la seconda transazione è aperta da Emma che vuol vedere lo stato del suo conto. A questo punto la banca preleva i soldi dal conto di Emma per trasferirli su un altro conto. Con il livello di isolamento Read Uncommitted Emma è in grado di sapere in tempo reale quello che succede, ragion per cui vedrebbe il suo conto scendere a 2000 € anche se l’operazione non è stata ancora confermata. Supponiamo che qualcosa nella transazione vada storto e l’operazione sia annullata. A questo punto Emma vedrebbe i soldi sul suo conto tornare magicamente a 3000 €; veder fluttuare il proprio saldo senza apparente motivo è un’eventualità che molto probabilmente non piacerebbe a nessun utente.

Read committed

Questo è il livello predefinito del Motore di database di SQL Server: in tale livello non è possibile per una transazione leggere i dati modificati da un’altra transazione ma non ancora committati, scongiurando in questo modo il pericolo di dirty read. La conseguenza di questa strategia è che l’operazione di lettura di un dato modificato da un’altra transazione rimarrà in attesa fino a quando la prima transazione non sarà stata committata.

Tuttavia a una transazione è consentito di visualizzare i dati precedentemente letti (non modificati) da un’altra transazione senza attendere il completamento della prima transazione. Questo, come vedremo, non ci salvaguarda dall’eventualità che possano ancora verificarsi dei casi di nonrepeatable read o phantom read.

Figura 2

Figura 1

Qui siamo nello stesso caso di prima, ovvero la banca apre la transazione per prelevare i soldi dal conto di Emma, Emma apre la seconda transazione, ma dal momento in cui la prima transazione ha effettuato un’operazione di modifica sul suo conto, Emma non può più vedere quello che sta succedendo finché l’operazione concorrente non si conclude. In questo caso, come nel caso illustrato prima, per qualche motivo l’operazione fallisce, ma Emma non vedrà mai il suo conto in uno stato inconsistente. Il prezzo da pagare ovviamente consiste nel dover aspettare che l’operazione di modifica da parte della banca sia confermata da un commit o annullata da un rollback.

Figura 3

Se invece l’operazione va a buon fine abbiamo un caso lampante di nonrepeatable read, dato che Emma vede il valore del proprio saldo cambiare all’interno della sua transazione dopo che la banca conferma l’operazione con un commit. È importante rendersi conto che questo è un caso diverso dalla dirty read del primo esempio, dato che alla fine della sua transazione, pur se diverso dall’inizio, Emma ha davanti agli occhi un dato reale e confermato.

Repeatable Read

Qui il motore di database di SQL Server mantiene i lock di lettura e scrittura sui dati selezionati fino alla fine della transazione. Pertanto basta che una transazione sia aperta in lettura su un dato per fare sì che questo dato non sia modificabile da altre transazioni, rendendo impossibile il verificarsi di non-repeatable read. I casi di phantom read sono però ancora possibili, come illustrato nell’esempio qui sotto: la stessa query infatti fornisce due set di dati con un numero diverso di record totali all’interno della stessa transazione.

Figura 4

La transazione 1, aperta dall’impiegato 1 della banca, richiede di visualizzare tutti i conti attualmente attivi, ottenendo come risultato che l’unica correntista è Emma (probabilmente non si tratta di una banca molto grande). Nello stesso momento però l’impiegato 2 apre un nuovo conto a nome di Marta e conferma con un commit. Se a questo punto l’impiegato 1 inoltra nuovamente la richiesta di vedere i conti attualmente attivi, leggerà un record in più rispetto a quanto letto a inizio transazione (phantom read).

Serializable

Questo è il livello più alto di isolamento, in cui le transazioni sono completamente isolate l’una dall’altra. Qui abbiamo che

  • Un dato non potrà essere letto se ci sono transazioni in corso che hanno modificato quel dato
  • Nessuna transazione potrà modificare un dato che sta venendo letto da una transazione in corso
  • Nessuna transazione potrà effettuare operazioni di insert che soddisfino le condizioni di select di un’altra transazione in corso

Il costo di un livello di isolamento così blindato consiste nell’avere l’impatto più elevato sulle performance rispetto a tutti gli altri livelli.

Figura 5

In questo esempio l’impiegato 1 (nella transazione 1) effettua esattamente come prima un’operazione di visualizzazione dei conti attivi. L’impiegato 2, che invece sta aprendo un nuovo conto a nome di Marta (nella transazione 2), deve aspettare che l’impiegato 1 chiuda la sua transazione per poter finalizzare la creazione del nuovo conto. A questo livello di isolamento vediamo che è sufficiente compiere una select per bloccare un’operazione di insert da parte di una transazione concorrente.

Snapshot

Il livello di isolamento snapshot utilizza il controllo delle versioni delle righe per fornire coerenza di lettura a livello di transazione. Se è impostato il livello snaphot, in caso di transazioni concorrenti verrà letta la versione consistente più recente da quando è iniziata la transazione, senza bloccare l’azione di lettura su un dato modificato da un’altra transazione (come invece avviene nel livello serializable). In comune con il livello serializable ha però il fatto di proteggerci dall’eventualità di dirty read, nonrepeatable read e phantom read.

Figura 6

Qui Emma apre una transazione per sapere qual è il saldo del suo conto. Diversamente da prima la banca ha la possibilità di modificare tale saldo durante la transazione concorrente. Dopo l’aggiornamento da parte della banca (e conseguente commit), Emma continuerà a visualizzare la stessa cifra che vedeva all’inizio, prima che questa venisse modificata. La cifra aggiornata sarà disponibile alla lettura da parte di Emma solo dopo che anche lei avrà chiuso la sua transazione. L’inconveniente evidente del livello snapshot è che due utenti che stanno estraendo lo stesso dato nello stesso istante, potrebbero trovarsi di fronte a due valori differenti.

Conclusioni

Ma allora qual è il sistema migliore da adottare? La risposta è, come al solito: dipende.

Quello che dobbiamo tenere presente è sempre il bilancio costi / benefici, che si può esprimere essenzialmente in due modi dai nomi variopinti, ovvero la concorrenza pessimistica e la concorrenza ottimistica.

Concorrenza pessimistica

È la via più intransigente: nel momento in cui un utente compie un’operazione che porta ad un lock, gli altri utenti non possono compiere nessuna operazione che vada in conflitto con quel lock finché non viene rilasciato. Si chiama concorrenza pessimistica perché si basa sul principio che molti utenti potrebbero intervenire contemporaneamente sugli stessi dati, e quindi il costo di proteggere i dati con dei lock è inferiore rispetto ad effettuare il rollback delle transazioni in conflitto tra loro.

Concorrenza ottimistica

In questo caso gli utenti non bloccano i dati quando li leggono. Quando un utente aggiorna i dati, il sistema controlla se un altro utente ha modificato i dati dopo che sono stati letti. Se un altro utente ha aggiornato i dati, viene generato un errore. In genere, l’utente che riceve l’errore subisce il rollback della transazione e deve ricominciare. Questo tipo di concorrenza è chiamato ottimistico perché viene utilizzato principalmente in ambienti in cui vi è una bassa contesa per i dati e dove il costo del rollback occasionale di una transazione è inferiore al costo del blocco dei dati durante la lettura.

Bibliografia

https://docs.microsoft.com/en-us/sql/connect/jdbc/understanding-isolation-levels?view=sql-server-ver15

https://www.geeksforgeeks.org/acid-properties-in-dbms/

https://www.mssqltips.com/sqlservertip/2977/demonstrations-of-transaction-isolation-levels-in-sql-server/

https://www.red-gate.com/simple-talk/sql/t-sql-programming/questions-about-t-sql-transaction-isolation-levels-you-were-too-shy-to-ask/

Articolo a cura di Giovanni Bertoglio, 21.06.2021

#jointherevolution

Creare un podcast in automatico a partire da audio vocali e musica

Nel 2011, mentre studiavo architettura al Politecnico di Torino e vivevo nel collegio universitario di Grugliasco, mi sono imbattuto in una delle più belle esperienze della mia vita. Insieme al mio amico Angelo ho progettato e realizzato una webradio studentesca che trasmetteva direttamente dal collegio. Il progetto, durato 5 anni è stato di grande scuola per me, sia dal punto di vista umano, sia professionale. Ero il classico “tecnico tutto fare” 🧑‍🔧 : in quel periodo mi sono occupato di piccoli software radiofonici, della programmazione e della gestione del palinsesto, ma ovviamente anche nella manutenzione del server della radio e dello studio dal quale trasmettevamo. Ho conosciuto piu di 60 ragazzi, divisi in gruppi di lavoro, uno per tramissione!

Nell’ultimo periodo (coinciso più o meno con l’ascesa dei podcast su Spotify) è tornata la mia curiosità verso il mondo della radio. Mi sono chiesto quanto fosse possibile migliorare/ottimizzare il processo di creazione di una trasmissione radiofonica o un podcast. Avevo già trattato quest’argomento in un precedente articolo in cui mi concentravo sul come mixare la voce di uno speaker insieme ad altri suoni. In questi giorni ho realizzato un piccolo script che passo passo crea un’intera trasmissione a partire da una cartella di files.

Struttura di una puntata radiofonica

Per realizzare questo piccolo progetto ho utilizzato FFMPEG, nota libreria per la manipolazione del suono (leggi il mio articolo al riguardo con degli esempi d’uso). Questa libreria permette di applicare dei filtri al suono in maniera programmatica, quindi attraverso un linguaggio di programmazione. Studiando la ricchissima documentazione (e con l’aiuto dell’ottima community di FFMPEG) sono riuscito a realizzare questo Batch che programmaticamente mette in sequenza dei file audio, tramite l’uso di dissolvenze o somme di suoni. Vediamo uno schema:

Traducendo questo semplice schema in un codice programmabile, questo somiglia ad un array di oggetti (file audio) che dovranno essere messi in sequenza, ma a certe condizioni:

  • il parlato dovrà sempre avere un sottofondo leggero di musica
  • i brani partiranno con una dissolvenza (fade) nel momento in cui il parlato sta per finire
  • il parlato comincia un momento prima del termine del brano

Ecco uno schema piu preciso di quello che succederà:

Script per elaborare il parlato con un sottofondo

Questo script va eseguito con l’ultima versione di NodeJs installata, e richiede diverse librerie esterne, la piu importante è fluent-ffmpeg, ovvero un wrapper di FFMPEG per NodeJs. Lo script converte una serie di audio registrati con solo voce in diversi file in cui la voce è accompagnata da un sottofondo musicale leggero che parte e finisce in dissolvenza.

var mp3Duration = require('mp3-duration');
var ffmpeg = require('fluent-ffmpeg');
var fs = require('fs')
 
let array = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]; //un generico array di file audio di voce
 
let promises = [];
 
array.forEach(speech => {
 
    let speechFile = speech + '.mp3';
    let backgroundFile = 'sottofondo.mp3';
    let backgroundLooped = speech + '_onlybackground.mp3';
    let speechWithBackground = speech + '_.mp3'
 
    let p = mp3Duration(speechFile, function (err, dur) {
 
        //recupero la durata dello speech
        let durataVoce = Math.round(dur);
 
        //creo un loop della durata dello speech
        ffmpeg(backgroundFile)
            .inputOption("-stream_loop -1") //loop infinito del sottofondo
            .audioFilters('afade=t=in:ss=0:d=8')  //fadein che dura 8 secondi
            .audioFilters('afade=t=out:st=' + (durataVoce - 10) + ':d=5')   //fadeout che dura 8 secondi e parte 10 secondi prima della fine dell'audio
            .duration(durataVoce) //taglio alla durata della voce
            .audioBitrate(320)
            .output(backgroundLooped)
            .on('end', function () {
 
                //faccio un mix con la voce
 
                ffmpeg()
                    .addInput(backgroundLooped)
                    .addInput(speechFile)
                    .complexFilter(['[1]compand=attacks=0.4:points=-80/-80|-12.4/-12.4|-6/-8|0/-6.8|20/-2.8:gain=12:volume=-40[a1]',
                        '[a1]channelsplit=channel_layout=stereo:channels=FR[a2]',
                        '[0][a2]amix=inputs=2:dropout_transition=0.2:weights=1 10,dynaudnorm'])
                    .audioBitrate(320)
                    .save(speechWithBackground)
                    .on('end', function () {
                        //rimuovo il file del background
                        console.log(speech + " - Completato");
                        fs.unlinkSync(backgroundLooped);
 
                    });
            }).run();
 
    });
 
    promises.push(p);
});

Script per mettere in sequenza i file audio

Una volta terminata l’elaborazione dei file audio del parlato, non ci resta che mixare il tutto seguendo lo schema precedente. I brani saranno leggermente anticipati rispetto al termine del parlato, in modo da accentuare l’effetto radiofonico finale. Ogni brano inizierà e finirà con una dissolvenza automatica di 10 secondi (impostata nella variabile fadeDuration). Inoltre verrà applicato un filtro normalizzazione audio, che consentirà di assottigliare le differenze di volume tra i brani, migliorando l’esperienza di ascolto.

var ffmpeg = require('fluent-ffmpeg');
 
let speeches = [
    {
        tipo: 'musica',
        file: "sigla.mp3"
    },
    {
        tipo: 'voce',
        file: "1_.mp3"
    },
    {
        tipo: 'musica',
        file: "musica1.mp3"
    },
    {
        tipo: 'voce',
        file: "2_.mp3"
    },
    {
        tipo: 'musica',
        file: "musica2.mp3"
    }
]
 
 
let command = ffmpeg();
let filters = [];
let combo = 0;
let fadeDuration = 10;
 
for (let i = 0; i < speeches.length; i++) {
 
    //aggiungo l'input
 
    speech = speeches[i];
    command.addInput(speech.file);
    successivo = i + 1;
 
    //se sono all'ultimo non faccio niente perche mi interessa la combo precedente
    if (i < speeches.length - 1) {
 
        //se l'attuale è voce
        if (speech.tipo == 'voce') {
 
            //abbasso il volume della musica successiva
            filters.push('[' + successivo + ']volume=0.3[low' + successivo + ']');
 
            if (i < 1) {
                filters.push('[' + i + '][low' + successivo + ']acrossfade=d=' + fadeDuration + ':c1=nofade:c2=exp[combo' + combo + ']');
            } else {
 
                output = '[combo' + (combo + 1) + ']';
                if (successivo == speeches.length - 1) {
                    output = ",loudnorm";
                }
 
                filters.push('[combo' + combo + '][low' + successivo + ']acrossfade=d=' + fadeDuration + ':c1=nofade:c2=exp' + output);
                combo++;
            }
 
 
            //se l'attuale è musica
        } else if (speech.tipo == 'musica') {
 
            if (i < 1) {
                filters.push('[' + i + ']volume=0.4[low' + i + ']');
                filters.push('[low' + i + '][' + successivo + ']acrossfade=d=' + fadeDuration + ':c1=exp:c2=nofade[combo' + combo + ']');
            } else {
 
                output = '[combo' + (combo + 1) + ']';
                if (successivo == speeches.length - 1) {
                    output = ",loudnorm";
                }
 
                filters.push('[combo' + combo + '][' + successivo + ']acrossfade=d=' + fadeDuration + ':c1=exp:c2=nofade' + output);
                combo++;
            }
 
        }
    }
 
}
 
command.complexFilter(filters)
    .save("totale1.mp3")
    .audioBitrate(320)
    .on('end', function () {
        //rimuovo il file del background
        console.log(" - Completato");
    });

Risultato

Ho utilizzato questo piccolo script per realizzare una trasmissione di prova, a partire da un file vocale registrato con lo smartphone. Chiaramente è un progetto ancora molto semplice, ma che crea interessanti spunti su come automatizzare il processo di missaggio (mix) di puntate radiofoniche o podcast.

Articolo a cura di Carlo Peluso, 18.05.2021

Link articolo originale: https://straquenzu.p3lus0s.net/creare-un-podcast-in-automatico-a-partire-da-audio-vocali-e-musica

#jointherevolution

Introduzione alla teoria dei grafi per la teoria dei giochi

Nell’articolo precedente (https://orbyta.it/teoria-dei-giochi/) abbiamo illustrato i principi base della teoria dei giochi e, tramite qualche esempio, abbiamo scoperto come può essere utilizzata per attuare la strategia più conveniente in una situazione in cui il guadagno finale dipende dalle mosse effettuate dagli altri giocatori.

In questo secondo articolo scopriremo cos’è la teoria dei grafi e come può essere integrata nella teoria dei giochi. Inoltre, introdurremo un altro tipo di equilibrio di Nash, ovvero gli equilibri di Nash per strategie miste.

La teoria dei grafi

I grafi possono essere utilizzati per schematizzare delle situazioni o processi e ne consentono l’analisi in termini quantitativi e algoritmici.

Tecnicamente, un grafo (o rete) G è una coppia (V, E) dove V è un insieme finito i cui elementi sono detti vertici o nodi ed E è un sottoinsieme i cui elementi, detti archi o lati, sono coppie di oggetti in V.

Per esempio, nella seguente immagine vediamo un grafo con vertici V={A,B,C,D} ed archi E={(A,B), (B,A), (B,D), (D,B), (D,C), (C,D), (B,C), (C,B)}.

Una digrafo è un grafo che possiede almeno un arco orientato, cioè un arco caratterizzato da un verso che non può essere percorso nel verso opposto.

Per esempio modificando il grafo precedente come segue otteniamo un digrafo con archi E={(B,A), (B,D), (D,B), (D,C), (C,D), (B,C), (C,B)}.

Introduciamo ora qualche esempio pratico per capire come i grafi possono essere utilizzati nella teoria dei giochi.

Esempio numerico [4]

Consideriamo una situazione in cui sono presenti due giocatori e il primo di essi, A, sceglie un numero tra 1,2 e 3. Il secondo partecipante, B, somma al numero detto 1,2 o 3. A farà lo stesso nel turno successivo e così via finché uno dei due arriverà ad esclamare 31 vincendo.
Tale gioco può essere rappresentato tramite il seguente digrafo:

I vertici sono i numeri naturali dall’1 al 31 e gli archi che partono dal vertice n entrano in quelli n+1, n+2 e n+3 se 1 ≤ n ≤ 28. Dal 29 escono degli archi entranti in 30 e 31, dal 30 in 31 e dal 31 nessuno.

Dunque, il giocatore che riesce a dire 27 ha vinto perché il giocatore successivo potrà selezionare solo i vertici 28, 29, o 30 e, in ognuno di questi casi, il primo riuscirà a posizionarsi sul 31.

Possiamo quindi porci come obiettivo di arrivare al 27 e non al 31. Ma a questo punto chi dirà 23 riuscirà a vincere e, applicando il ragionamento iterativamente, concludiamo che i nodi da toccare per vincere sono X = {3, 7, 11, 15, 19, 23, 27, 31}.

Osserviamo che:

  • Se un giocatore dice un numero non appartenente a X allora l’avversario ha sempre la possibilità di farlo e dunque di vincere.
  • Se un giocatore dice un numero appartenente a X allora l’avversario non potrà che scegliere un numero ad esso non appartenente.

In conclusione, analizzando il grafo, scopriamo che l’obiettivo è quello di occupare sempre le posizioni di X.

Esempio della protesta

Supponiamo di voler manifestare contro una data azione di un governo dittatoriale. Tale evento risulterà vantaggioso solo se il numero di manifestanti sarà sufficientemente elevato, d’altro canto se ciò non dovesse accadere andremmo in contro ad un payoff assai negativo in quanto potremmo supporre che, in tal caso, lo stato sederà la manifestazione in modo violento.

Supponiamo che ogni persona decida di partecipare alla protesta solo se sa che almeno un numero sufficiente di cittadini vi aderirà.

Supponiamo di avere 4 cittadini e rappresentiamo il fatto che il cittadino w conosca il comportamento di quello u e viceversa con la presenza del lato (w,u). La cifra accanto a un nodo indica il numero minimo di manifestanti totali affinché il nodo in questione si unisca all’impresa.

Consideriamo le seguenti situazioni:

Notiamo che nel caso A la rivolta non avrà luogo in quanto ognuno dei partecipanti non ha modo di sapere il comportamento che adotterà il nodo ad esso non collegato.

Nel caso B invece ognuno tra u, v e w saprà che esistono almeno altri due nodi che richiedono almeno tre partecipanti totali e che a loro volta hanno questa informazione. Dunque la protesta si svolgerà, in particolare u, v e w saranno i manifestanti.

Equilibrio di Nash per strategie miste

Esistono dei giochi in cui non sono presenti gli equilibri di Nash che abbiamo introdotto nell’articolo precedente, ovvero quelli basati su strategia pure. Una strategia pura infatti fornisce una descrizione completa del modo in cui un individuo gioca una partita. In particolare, essa determina quale scelta farà il giocatore in qualsiasi situazione che potrebbe affrontare.

Una strategia mista per un giocatore è una distribuzione di probabilità sull’insieme delle strategie pure che ha a disposizione. Ogni strategia pura P può essere vista come un caso particolare di strategia mista che assegna probabilità pari a 1 a P e pari a 0 a tutte le altre strategie pure.

Abbiamo quindi due tipi di equilibri di Nash: quelli per le strategie pure, analizzati finora, si hanno quando tutti i giocatori hanno a disposizione solo strategie pure, altrimenti si parla di equilibri di Nash per strategie miste.

Limitandoci ad un gioco a due partecipanti, un equilibrio di Nash per le strategie miste è una coppia di scelte (che ora sono probabilità) tale che ognuna sia la miglior risposta all’altra.

Introduciamo un esempio.

Esempio dell’attaccante/difensore

Si consideri un gioco in cui c’è un attaccante A e un difensore D.

L’attaccante può scegliere tra le strategie di attacco a1 o a2 mentre il difensore può difendersi da a1, e quindi applicare la strategia d1, o viceversa difendersi da a2, e quindi applicare la strategia d2.

Supponiamo che:

  • se D scegliesse la giusta strategia di difesa, cioè di contro ai (i = 1, 2), avremmo per A un guadagno di 0;
  • se D scegliesse d1 e A scegliesse a2, A otterrebbe un guadagno di 5 e D una perdita pari;
  • se D scegliesse d2 mentre A scegliesse a1, A ricaverebbe un guadagno di 10 e D una perdita pari.


Riassumiamo la situazione del gioco nella seguente tabella indicando in ogni riquadro: a sinistra della virgola il guadagno ottenuto da A e a destra della virgola quello ottenuto da D.

Nel nostro esempio a1 e a2 sono le strategie pure a disposizione dell’attaccante, mentre difendere da a1 e difendere da a2 quelle del difensore.

Dato che i due giocatori otterrebbero dei guadagni nettamente contrastanti potremmo concludere che in questo genere di giochi (detti strettamente competitivi) non esistano equilibri di Nash.

Se uno dei due giocatori sapesse il comportamento dell’altro allora potrebbe scegliere la strategia atta a massimizzare il suo profitto e inevitabilmente a minimizzare quello dell’avversario. Ognuno dei giocatori cercherà perciò di rendere imprevedibile la propria strategia.

Sia p la probabilità che A scelga a1 e q la probabilità che D scelga d1. Per ora sappiamo solo che esiste almeno un equilibrio per le strategie miste ma non quali debbano essere i valori effettivi di p e q.

Usiamo il principio secondo cui un equilibrio misto sorge quando le probabilità utilizzate da ciascun giocatore fanno sì che il suo avversario non abbia motivo di preferire una delle due opzioni disponibili all’altra.

Se supponiamo che D abbia una probabilità q di giocare d1 allora abbiamo che i possibili guadagni per A sono:

  • (0)(q) + (10)(1 − q) = 10 − 10q se scegliesse a1;
  •  (5)(q) + (0)(1 − q) = 5q se scegliesse a2.

Per far in modo che per A sia indifferente scegliere tra a1 e a2 imponiamo 10−10q = 5q da cui q = 2/3.

Ora supponiamo che A abbia una probabilità p di mettere in atto a1. I possibili guadagni per D allora sono:

  • (0)(p) + (−5)(1 − p) = 5p − 5 se scegliesse d1
  • (−10)(p) + (0)(1 − p) = −10p se scegliesse d2

Imponendo 5p − 5 = −10p otteniamo p = 1/3.

Quindi abbiamo che gli unici possibili valori di probabilità che possono apparire nell’equilibrio per la strategia mista sono p = 1/3 per l’attaccante e q = 2/3 per il difensore.

Si noti inoltre che il guadagno atteso di A nel caso in cui scelga a1 e D scelga d1 è di 10/3 e quello di D è di -10/3.

Ciò ci suggerisce un’analisi controintuitiva: la probabilità di A di sferrare l’attacco più forte è di un terzo, ovvero, in un modello continuo, potremmo immaginare che solo per un terzo del tempo A provi ad attaccare con a1.

Perché usare così poco la strategia più potente?

La risposta è che se A provasse sempre ad attaccare con a1 allora D sarebbe persuaso a rispondere spesso con d1, il che ridurrebbe il payoff atteso da A. D’altro canto si consideri che poiché p = 1/3 fa sì che D scelga senza preferenza una delle due strategie e abbiamo che, quando A usa tale valore di probabilità, allora, indipendentemente dalle scelte di D, esso si assicura un payoff di 10/3.

Esempio delle imprese

Consideriamo ora il fatto che anche se un giocatore non ha una strategia dominante, esso potrebbe avere strategie che sono dominate da altre. Si consideri il seguente esempio.

Supponiamo che due imprese, F1 e F2, stiano progettando di aprire un negozio in una delle sei città situate lungo sei uscite consecutive su una strada. Possiamo rappresentare la disposizione di queste città utilizzando un grafo a sei nodi come quello nella figura sottostante [2].

Supponiamo che F1 possa aprire il suo negozio in A, C o E mentre F2 in B, D o F. Una volta che i negozi apriranno, i clienti delle varie città faranno compere nel centro a loro più vicino. Si assuma che ogni città abbia lo stesso numero di clienti e che i guadagni dei negozi siano direttamente proporzionali al numero di clienti attirati. Otteniamo facilmente la tabella di guadagni sottostante.

Si può verificare che nessuno dei giocatori ha una strategia dominante: per esempio se F1 scegliesse la locazione A allora la risposta strettamente migliore di F2 sarebbe B, mentre se F1 scegliesse E la risposta strettamente migliore di F2 sarebbe D. Nonostante ciò notiamo che A è una strategia strettamente dominata per F1, infatti in ogni situazione in cui F1 ha l’opzione di scegliere A, esso riceverà un guadagno strettamente migliore scegliendo C. Analogamente F è una strategia strettamente dominata per F2. Abbiamo dunque che F1 non sceglierà A e F2 non sceglierà F. Possiamo a questo punto non considerare i nodi F e A, e da ciò ricaviamo la seguente tabella di payoff:

B ed E divengono rispettivamente le nuove strategie strettamente dominate per F2 e F1 e quindi possono essere a loro volta eliminate. Arriviamo alla conclusione che F1 sceglierà C e F2 D.

Questo modo di procedere è chiamato cancellazione iterativa delle strategie strettamente dominate. Notiamo inoltre che la coppia (C,D) costituisce l’unico equilibrio di Nash del gioco ed infatti questa metodologia di studio è anche utile a trovare gli equilibri di Nash. Generalizziamo di seguito il processo appena presentato.

Dato un numero arbitrario di n giocatori abbiamo che la cancellazione iterativa delle strategie strettamente dominate procede come segue:

  1. Si parte da un giocatore, si trovano tutte le sue strategie strettamente dominate e le si eliminano;
  2. Si considera il gioco semplificato ottenuto. Si eliminano eventuali nuove strategie strettamente dominate;
  3. Si itera il processo finché non si trovano più strategie strettamente dominate.

Si può dimostrare che l’insieme degli equilibri di Nash della versione originale del gioco coincide con quello della versione finale così ottenuta.

Consideriamo un problema in cui due giocatori A e B possano optare per la strategia a o b con i seguenti guadagni simmetrici:

In questo caso a è una strategia debolmente dominata poiché in ogni caso ogni giocatore può solo migliorare il suo guadagno scegliendo b. Inoltre si noti che (b,b) è un equilibrio di Nash.

Quando abbiamo delle strategie debolmente dominate non è consigliabile procedere con il metodo della cancellazione, poiché questa operazione potrebbe distruggere degli equilibri.

D’altro canto è intuitivo pensare che nessun giocatore scelga di assecondare l’equilibrio (a,a) composto da strategie debolmente dominate se non ha modo di prevedere il comportamento dell’altro giocatore: perché non usare la strategia (b,b) che nel peggiore dei casi comunque non inficia il  guadagno?

In questo articolo abbiamo visto come la teoria dei grafi può essere usata in quella dei giochi andando a risolvere giochi che hanno dato risultati controintuitivi. Nel prossimo articolo, approfondiremo le reti andando a studiare situazioni più complesse che ci permetteranno di analizzare la propagazione delle strategie all’interno di una rete.

Bibliografia e sitografia

[2] D. Easley e J. Kleinberg, Networks, Crowds, and Markets: Reasoning about a Highly Con- nected World, Cambridge University Press, 2010.

[3] R. Gibbons, Teoria dei giochi, Bologna, Il Mulino, 2005.

[4] E. Martìn Novo e A. Mendez Alonso, Aplicaciones de la teoría de grafos a algunos juegos de estrategia, numero 64 di Suma, Universidad Politécnica de Madrid, 2004.

[8] P. Serafini, Teoria dei Grafi e dei Giochi, a.a. 2014-15 (revisione: 28 novembre 2014).

[9] I. S. Stievano e M. Biey, Cascading behavior in networks, DET, Politecnico di Torino, 2015.

[10] I. S. Stievano e M. Biey, Interactions within a network, DET, Politecnico di Torino, 2015.

[11] I. S. Stievano, M. Biey e F. Corinto, Reti e sistemi complessi, DET, Politecnico di Torino, 2015.

[12] A. Ziggioto e A. Piana, Modello di Lotka-Volterra, reperibile all’indirizzo http://www.itismajo.it/matematica/Lezioni/Vecchi%20Documenti%20a.s.%202011-12/Modello

%20di%20Lotka-Volterra.pdf, consultato il 15/05/2015.

 [15] http://web.econ.unito.it/vannoni/docs/thgiochi.pdf consultato il 14/05/2015.

Articolo a cura di Monica Mura e Carla Melia, Data Scientist in Orbyta Tech, 01.05.2021

#jointherevolution