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 ∧ q) → r 

(s ∨ t) → q 

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

Introduzione alla teoria dei giochi: equilibri di Nash ed equilibri multipli

La teoria dei giochi è quella scienza matematica sviluppata al fine di capire quale sia la strategia migliore che un soggetto possa attuare in situazioni che mutano non solo al variare delle sue decisioni ma anche di quelle dei soggetti a esso connessi. Tale teoria, com’è facilmente intuibile, viene applicata a molti ambiti, per esempio quelli in cui ci si prefigge di studiare un piano di marketing o una politica proficua.

Un esempio che consigliamo si può trovare al seguente link: 

Definiamo gioco una qualsiasi situazione in cui:

  • Esiste un insieme di partecipati che chiameremo giocatori;
  • Ogni giocatore ha a disposizione una serie di possibili opzioni di comportamento che chiameremo strategie;
  • Per ogni scelta di strategie ogni giocatore riceve un guadagno, detto anche payoff, generalmente rappresentato da un numero.

Ogni giocatore in generale cercherà di massimizzare il suo profitto ma non è detto che il suo unico interesse sia questo, infatti, potrebbe anche cercare si massimizzare il tornaconto di altri giocatori e, in tal caso, il concetto di guadagno andrà rivisto affinché esso descriva con completezza il grado di soddisfazione del soggetto. 

Nella teoria dei giochi è fondamentale il concetto dell’equilibrio di Nash sviluppato da John F. Nash, economista e matematico statunitense, i cui studi all’interno di questo ambito hanno portato allo sviluppo di quello che viene chiamato, il “dilemma del prigioniero”. Di seguito vediamo una sua rappresentazione schematica.

How to win at game theory | New Scientist

Rimandiamo al seguente video per una spiegazione più estesa di questo Dilemma:

Ora introduciamo qualche nuova definizione.

Una scelta di strategie, una per ogni giocatore, è socialmente ottimale se massimizza la somma dei guadagni di tutti i giocatori, mentre è Pareto-ottimale se non esiste un’altra combinazione di mosse tale che migliori i payoff di almeno un giocatore senza diminuire quello degli altri. Non lo dimostreremo qua per motivi di brevità ma se una soluzione è socialmente ottimale allora è anche Pareto-ottimale

Supporremo che ogni giocatore conosca integralmente la struttura del gioco (cioè che il gioco sia completo) e quindi che sia a conoscenza di tutte le possibili strategie e guadagni di ogni partecipante. Inoltre, assumeremo che ogni partecipante sia intelligente (cioè in grado di capire, senza commettere errori, dato un insieme di strategie possibili quale sia la più conveniente) e razionale (cioè tale che, una volta riconosciuta la/le strategia/e a massimo profitto la/le preferisca alle altre [14]).

Modelli in cui tali assunzioni non vengono fatte possono divenire estremamente complicati e non li approfondiremo nel corso di questa trattazione. 

Si consideri il seguente esempio tratto dal sesto capitolo di [2].

Esempio degli studenti

Helpful Study Partner | Funny dog memes, Dog quotes funny, Funny animals

Uno studente deve affrontare un esame e una presentazione per il giorno seguente ma non può prepararsi adeguatamente per entrambe. Per semplicità supponiamo che egli sia in grado stimare con ottima precisione quale sarà il voto ottenuto (calcolato in centesimi) da entrambe le prove al variare della sua preparazione. 

In particolare, per quel che riguarda l’esame lo studente si aspetta una votazione pari a 92 se studia e di 80 altrimenti. La presentazione, invece, deve essere fatta con un compagno e nel caso in cui entrambi lavorino su di essa la votazione relativa sarà di 100, se solo uno dei due (indipendentemente da chi) ci lavorasse di 92 e se non lo facesse nessuno di 84. Anche il compagno deve scegliere se studiare per l’esame o concentrarsi sulla preparazione e le sue previsioni sui voti sono le stesse.

Si presuma infine che i due compagni non possano comunicare e quindi mettersi d’accordo sul da farsi. L’obiettivo per entrambi è quello di massimizzare il valore medio delle due votazioni che poi andrà a costituire il voto definitivo. Schematizziamo di seguito i possibili risultati:

  • Se entrambi preparassero la presentazione prenderebbero 100 in essa e 80 nell’esame ottenendo quindi una votazione finale di 90;
  • Se entrambi studiassero per l’esame prenderebbero 92 in esso e 84 nella presentazione per una media di 88;
  • Se uno studiasse per l’esame e l’altro preparasse la presentazione avremmo che quest’ultimo prenderebbe 92 in essa ma 80 nell’esame arrivando a una media di 86, mentre l’altro prenderebbe anch’esso 92 per la presentazione (poiché ci avrebbe lavorato l’altro) e 92 all’esame ottenendo una media di 92.

Cos’è meglio fare quindi? Possiamo ragionare in questo modo:

  1. Se si sapesse che il compagno studierà per l’esame, lo studente dovrebbe scegliere di fare lo stesso in quanto ciò gli permetterebbe di ottenere una votazione media di 88, mentre focalizzarsi sulla presentazione di 86;
  2. Se si sapesse che il compagno preparerà la presentazione, lo studente dovrebbe scegliere di studiare perché così otterrebbe una media finale di 92 mentre in caso contrario di 90.

Possiamo dunque concludere che la miglior cosa da fare sarebbe, in ogni caso, studiare per l’esame.

What advice do you have for someone studying for the bar exam?

Quando, come nell’esempio presentato, un giocatore ha una strategia strettamente più conveniente delle altre, indipendentemente dal comportamento degli altri giocatori, chiameremo tale scelta strategia strettamente dominante e, supponendo la razionalità del soggetto, daremo per scontato che la adotti. 

Nell’esempio precedente, per la stessa natura del problema, ci aspettiamo un comportamento simmetrico da parte dei due giocatori che dunque sceglieranno entrambi di studiare ottenendo la votazione complessiva di 88.

È interessante però notare che se gli studenti avessero potuto accordarsi sul preparare entrambi la presentazione il risultato finale non sarebbe variato, infatti, in tal caso, lo studente si sarebbe aspettato un voto medio di 90 e dunque avrebbe deciso di studiare per l’esame sapendo che l’altro avrebbe preparato la presentazione, infatti ciò gli permetterebbe di raggiungere il 92. 

In realtà, tale piano non avrebbe funzionato perché, a una più attenta analisi, ci si accorge che anche il compagno, in un’ottica meccanicamente razionalistica incentrata sulla massimizzazione del proprio profitto, avrebbe attuato allo stesso modo e dunque entrambi avrebbero ottenuto un punteggio medio di 88, mentre, non giocando razionalmente, avrebbero potuto raggiungere la votazione di 90.

Un’ultima “definizione” prima di spiegare un tema centrale della teoria dei giochi: senza entrare in tecnicismi diremo che in pratica la miglior risposta è la scelta più conveniente che un giocatore, che crede in un dato comportamento degli altri giocatori, possa fare. 

Equilibrio di Nash

Consigliamo vivamente di guardare questo video tratto dal celeberrimo film “A Beautiful Mind” prima di proseguire. 

Dato un gioco, se nessuno dei partecipanti ha una strategia strettamente dominante, per predire l’evolversi della situazione, introduciamo il concetto di equilibrio di Nash secondo cui, in una situazione del genere, dobbiamo aspettarci che i giocatori usino le strategie che danno le migliori risposte le une alle altre. 

Si rimanda a [13] per una definizione più precisa, ma in pratica, se un gioco ammette almeno un equilibrio di Nash, ogni partecipante ha a disposizione almeno una strategia S1 alla quale non ha alcun interesse ad allontanarsi se tutti gli altri giocatori hanno giocato la propria strategia Sn. Questo perché se il giocatore i giocasse una qualsiasi altra strategia a sua disposizione, mentre tutti gli altri hanno giocato la propria strategia se, potrebbe solo peggiorare il proprio guadagno o, al più, lasciarlo invariato. Poiché questo vale per tutti i giocatori se esiste uno e un solo equilibrio di Nash, esso costituisce la soluzione del gioco in quanto nessuno dei giocatori ha interesse a cambiare strategia.

In altre parole si definisce equilibrio di Nash un profilo di strategie (una per ciascun giocatore) rispetto al quale nessun giocatore ha interesse ad essere l’unico a cambiare.

The Value of Coordination - 80,000 Hours

Esistono però giochi che presentano più equilibri di Nash.

Equilibri multipli: giochi di coordinazione

Si supponga, riprendendo l’esempio precedente, che gli studenti debbano preparare, una volta essersi divisi il lavoro, le slide della presentazione. Lo studente, senza possibilità di comunicare col compagno, deve decidere se creare le slide col programma A o col programma B considerando che sarebbe molto più facile unirle a quelle del compagno se fossero fatte con lo stesso software.

Un gioco di questo tipo è detto di coordinazione perché l’obiettivo dei due giocatori è quello di coordinarsi. In questo caso notiamo che ci sono più equilibri di Nash, cioè (A,A) e (B,B). Cosa bisogna aspettarsi?

La teoria dei punti focali (detti anche punti di Schelling) ci dice che possiamo usare caratteristiche intrinseche del gioco per prevedere quale equilibrio sarà quello scelto, cioè quello in grado di dare a tutti i giocatori un guadagno maggiore. Thomas Schelling ne “La strategia del conflitto” descrive un punto focale come: “l’aspettativa di ogni giocatore su quello che gli altri si aspettano che lui si aspetti di fare[7]. 

Premium Vector | People with question marks. man and woman with question,  thinking guy

Per esempio, ritornando al gioco degli studenti, se lo studente S1 sapesse che il compagno S2 predilige A, allora sceglierà A, infatti sapendo che S2 a sua volta sa che lui è a conoscenza di questo fatto assumerà che quest’ultimo sceglierà effettivamente A sapendo che S1 si conformerà di conseguenza.

Schelling illustra questo concetto tramite il seguente esempio: “domani devi incontrare un estraneo a New York, che luogo e ora sceglieresti?”

Che cosa fare a New York, Stati Uniti d'America - Eventi ed attività |  Eventbrite

Questo è un gioco di coordinamento, dove tutti gli orari e tutti i luoghi della città possono essere una soluzione di equilibrio. Proponendo il quesito a un gruppo di studenti constatò che la risposta più comune era: “alla Grand Central Station a mezzogiorno”. La GCS non è un luogo che porterebbe a un guadagno maggiore (il giocatore potrebbe facilmente incontrare qualcuno al bar, o in un parco), ma la sua tradizione come luogo di incontro la rende speciale e costituisce, perciò, un punto di Schelling. Nella teoria dei giochi un punto di Schelling è una soluzione che i giocatori tendono ad adottare in assenza di comunicazione, poiché esso appare naturale, speciale o rilevante per loro.

La teoria dei giochi ben si combina con quella dei grafi e la introdurremo nei prossimi articoli per vedere altri esempi di come possa esistere un possibile conflitto tra razionalità individuale, nel senso di massimizzazione dell’interesse personale, ed efficienza, ovvero la ricerca del miglior risultato possibile, sia individuale sia collettivo.

Abbiamo anche visto che applicando una strategia individualistica si ottiene a volte un esito inferiore rispetto a quanto ottenibile nel caso in cui si possa raggiungere un accordo e che se esiste un equilibrio di Nash ed è unico, esso rappresenta la soluzione del gioco poiché nessuno dei giocatori ha interesse a cambiare strategia. 

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] S. Rizzello e A. Spada, Economia cognitiva e interdisciplinarità, Giappichelli Editore, 2011.

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

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

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

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

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

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

[11] https://it.wikipedia.org/wiki/Teoria_dei_giochi

[12] https://fiscomania.com/teoria-dei-giochi-prigioniero-nash/ 

Articolo a cura di Carla Melia e Lucia Campomaggiore, Data Scientist in Orbyta Tech, 25.03.2021

#jointherevolution

Recommender systems: principali metodologie degli algoritmi di suggerimento

Introduzione

Vi siete mai chiesti come faccia Netflix a suggerirvi il tipo di film adatto a voi? O Amazon a mostrarvi l’articolo di cui avevate bisogno? O come mai, le pubblicità che vi appaiono nei siti web facciano riferimento a qualcosa di vostro interesse? Questi sono solo alcuni esempi di un tipo di algoritmi che vengono oggigiorno usati dalla maggior parte dei siti web e dalle applicazioni per fornire agli utenti dei suggerimenti personalizzati, si tratta dei sistemi di raccomandazione.

In questo articolo scopriremo cosa sono, con quali metodi vengono implementati e come vengono valutate le loro performance.

Cosa sono i sistemi di raccomandazione 

I sistemi di raccomandazione sono un tipo di sistemi di filtraggio dei contenuti. Possono essere descritti come degli algoritmi che hanno lo scopo di suggerire all’utente di un sito web o di un’applicazione degli articoli che possano risultare di suo interesse. Davanti ad una serie di prodotti devono essere in grado di selezionare e proporre quelli più adatti per ogni utente, quindi di fornire dei suggerimenti personalizzati.

Questo tipo di algoritmi vengono utilizzati in svariati settori. Gli esempi più evidenti possono essere quelli già citati all’inizio dell’articolo quindi nei servizi di e-commerce (es. Amazon), nei servizi di streaming di film, video o musica (es. Netflix, YouTube, Spotify), ma anche nelle piattaforme social (es. Instagram), nei servizi di delivery (es. Uber Eats) e così via. In generale, ogni qualvolta ci sia la possibilità di suggerire ad un utente un contenuto, può essere utilizzato un sistema di raccomandazione per renderlo specifico per l’utente stesso. 

Immagine che contiene elettronico, vicino, cellulare

Descrizione generata automaticamente



Come vengono implementati

I sistemi di raccomandazione possono essere suddivisi principalmente in due macrocategorie: metodi collaborative filtering e metodi content-based. Inoltre, questi due approcci possono essere combinati per dare origine a delle soluzioni ibride che sfruttano i vantaggi di entrambi.  

Metodi collaborative filtering

I sistemi di raccomandazione collaborative filtering utilizzano le interazioni avvenute tra utenti e articoli in passato per costruire la cosiddetta matrice di interazione utenti-articoli e da questa estrarre i nuovi suggerimenti. Si basano sull’assunzione che queste interazioni siano sufficienti per riconoscere gli utenti e/o gli articoli simili fra loro e che si possano fare delle predizioni concentrandosi su queste similarità.

Immagine che contiene testo

Descrizione generata automaticamente

Questa classe di metodi si divide a sua volta in due sottocategorie, sulla base della tecnica utilizzata per individuare le similarità tra gli utenti e/o gli articoli: metodi memory-based e metodi model-based. I primi utilizzano direttamente i valori contenuti nella matrice di interazione utenti-articoli per ricercare “il vicinato” dell’utente o dell’articolo target, i secondi assumono che dai valori della matrice sia possibile estrarre un modello con cui effettuare le nuove predizioni. 

Immagine che contiene testo

Descrizione generata automaticamente

Il vantaggio principale dei metodi collaborative filtering è dato dal fatto che non richiedono l’estrazione di informazioni sugli utenti o sugli articoli dunque possono essere utilizzati in svariati contesti. Inoltre, più gli utenti interagiscono con gli articoli, maggiori informazioni si avranno a disposizione e più le nuove raccomandazioni saranno accurate.

Il loro svantaggio emerge nel momento in cui si hanno nuovi utenti o nuovi articoli perché non ci sono informazioni passate sulle loro interazioni, questa situazione viene definita cold start problem. In questo caso per stabilire quali debbano essere le nuove raccomandazioni si sfruttano diverse tecniche: si raccomandano articoli scelti casualmente ai nuovi utenti o nuovi articoli ad utenti scelti casualmente, si raccomandano articoli popolari ai nuovi utenti o nuovi articoli agli utenti più attivi, si raccomandano un set di vari articoli ai nuovi utenti o un nuovo articolo ad un set di vari utenti, oppure, si evita di utilizzare un approccio collaborative filtering in questa fase.

Metodi memory-based

I metodi memory-based si possono a loro volta suddividere in metodi user-based e metodi item-based

I metodi user-based rappresentano gli utenti considerando le loro interazioni con gli articoli e sulla base di questo valutano la similarità tra un utente e l’altro. In generale, due utenti sono considerati simili se hanno interagito con tanti articoli allo stesso modo. Per fare una nuova raccomandazione ad un utente si cerca di identificare quelli con i “profili di interazione” più simili al suo, in modo tale da suggerirgli gli articoli più popolari tra il suo vicinato. 

Un esempio di applicazione del metodo user-based viene utilizzato da Youtube per suggerirci i video presenti nella nostra Homepage.

I metodi item-based rappresentano gli articoli basandosi sulle interazioni che gli utenti hanno avuto con loro. Due articoli vengono considerati simili se la maggior parte degli utenti che ha interagito con entrambi lo ha fatto allo stesso modo. Per fare una nuova raccomandazione ad un utente, questi metodi cercano articoli simili a quelli con la quale l’utente ha interagito positivamente.

Figura 6. Illustrazione del metodo item-based

Un esempio di applicazione del metodo item-based viene utilizzato da Amazon quando clicchiamo su un articolo e ci appare la sezione “i clienti che hanno visto questo articolo hanno visto anche” mostrandoci altri articoli simili a quello che abbiamo selezionato. 

Uno degli svantaggi dei metodi memory-based è il fatto che la ricerca del vicinato può richiedere molto tempo su grandi quantità di dati, quindi deve essere implementata attentamente e nel modo più efficiente possibile. Inoltre, bisogna evitare che il sistema raccomandi solo gli articoli più popolari e che agli utenti vengano suggeriti solo articoli molto simili a quelli che gli sono piaciuti in passato, deve essere in grado di garantire una certa diversità nei suggerimenti effettuati.

Figura 7. Confronto tra il metodo user-based e item-based

Metodi model-based

I metodi model-based si basano sull’assunzione che le interazioni tra articoli e utenti possano essere spiegate tramite un modello “nascosto”. 

Un esempio di algoritmo per l’estrazione del modello è la matrix-factorization, questo consiste sostanzialmente nella decomposizione della matrice di interazione utenti-articoli nel prodotto di due sottomatrici, una contenente la rappresentazione degli utenti e l’altra la rappresentazione degli articoli. Utenti simili in termini di preferenze e articoli simili in termini di caratteristiche avranno delle rappresentazioni simili nelle nuove matrici.

Figura 8. Illustrazione del metodo matrix-factorization

Metodi content-based

A differenza dei sistemi di raccomandazione collaborative filtering che si basano solo sull’interazione tra utenti e articoli, i sistemi di raccomandazione content-based ricercano delle informazioni aggiuntive.

Supponiamo di avere un sistema di raccomandazione che deve occuparsi di suggerire film agli utenti, in questo caso le informazioni aggiuntive potrebbero essere l’età, il sesso e il lavoro per gli utenti così come la categoria, gli attori principali e il regista per i film.

I metodi content-based cercano di costruire un modello che sappia spiegare la matrice di interazione utenti-articoli basandosi sulle features disponibili per gli utenti e gli articoli.

Dunque, considerando l’esempio precedente, si cerca il modello che spieghi come ad utenti con certe features piacciano film con altrettante features. Una volta che questo modello è stato ottenuto, fare delle predizioni per un nuovo utente è facile, basta considerare le sue features e di conseguenza verranno fatte le nuove predizioni. 

Nei metodi content-based il problema di raccomandazione viene trattato come un problema di classificazione (predire se ad un utente possa piacere o meno un articolo) o di regressione (predire il voto che un utente assegnerebbe ad un articolo).

In entrambi i casi il problema si può basare sulle features dell’utente (metodo item-centred), o sulle features dell’articolo (metodo user-centred). Nel primo caso si costruisce un modello per articolo cercando di capire qual è la probabilità che ad ogni utente piaccia quell’ articolo, nel secondo caso si costruisce un modello per utente per capire qual è la probabilità che a quell’utente piacciano gli articoli a disposizione. In alternativa si può anche valutare un modello che contenga sia le features degli utenti che quelle degli articoli.

Il vantaggio dei metodi content-based è che non soffrono del cold start problem perché i nuovi utenti e i nuovi articoli sono definiti dalle loro features e le raccomandazioni vengono fatte sulla base di queste. 



Come vengono valutati

Per valutare le performance di un sistema di raccomandazione, quindi per cercare di capire se le raccomandazioni che sta effettuando sono appropriate, vengono utilizzati principalmente tre tipi di valutazioni: user studies, la valutazione online e la valutazione offline.

La valutazione user studies prevede di proporre agli utenti delle raccomandazioni effettuate da diversi sistemi di raccomandazione e di chiedergli di valutare quali raccomandazioni ritengono migliori.

La valutazione online, chiamata anche A/B test, prevede di proporre agli utenti in real-time diverse raccomandazioni per poter valutare quali sono quelle che ottengono più “click”.

La valutazione offline prevede di fare delle simulazioni sul comportamento degli utenti partendo dai dataset passati che si hanno a disposizione.

Fonti

Articolo a cura di Monica Mura, Data Scientist in Orbyta, 11.03.2021

#jointherevolution

Quando, anni fa, ho iniziato a lavorare come consulente IT ho dovuto sviluppare e modificare script che venivano eseguiti su server UNIX. Non avevo a disposizione strumenti di tendenza. Fondamentalmente Notepad ++ per si scrive localmente sulla mia macchina e PuTTY o FileZilla per raggiungere i server remoti. Quindi, sui server, erano installati i “temibili” Vi o Vim . Così ho iniziato a usare anche Vim , e la prima cosa che ho dovuto imparare era “come uscire da Vim”.

Vim ha una curva di apprendimento ripida . In quel momento ho imparato solo pochi comandi di base, quelli fondamentali per lavorare e poi appena ho avuto la possibilità di passare a qualcos’altro l’ho fatto. Ma Vim ha anche un grande potenziale , se sai come usarlo. Ricordo che il mio capo poteva usarlo abbastanza bene ed era molto abile in questo. Certo è difficile e devi usarlo molto per iniziare a vedere miglioramenti, ma lo sforzo è ben pagato.

Alcuni giorni fa, in un tweet, ho scoperto l’esistenza di questo sito: vimforvscode.com . Ho pensato: “Wow, imparare Vim usando VS Code? 10 $ è un prezzo per cui vale la pena provare ”.  Ho installato l’ estensione VS Code : VSCodeVim e poi ho iniziato le lezioni che ho acquistato dal sito. Gli esercizi non sono difficili e ti permettono, attraverso la pratica e i suggerimenti, di imparare 22 comandi di base.

Ovviamente le lezioni di vimforvscode.com non bastano per padroneggiare appieno Vim , ti consiglio di provare ad esercitarti molto, cercando di aggiungere gradualmente più comandi. Queste risorse possono essere utili:

  1. Barbarian meets coding è un sito meraviglioso (la home page è qualcosa di incredibile, ti consiglio – anche se non sei interessato a Vim – di dare un’occhiata!) Che tra l’altro spiega come usare VSCodeVim , c’è un libro gratuito , che puoi leggere online, con tutte le funzionalità di Vim in VS Code , e se ti serve solo un breve riepilogo puoi usare il cheat sheet
  2. Vim Cheat sheet è un cheat sheet completo per Vim , ma anche se ci sono alcuni comandi che non sono supportati nell’estensione VS Code ce ne sono altri che nel cheat sheet “barbaro” sono assenti.
  3. Vim adventures è un gioco molto carino che ti può insegnare Vim : è molto divertente, i primi 3 livelli sono gratuiti, poi devi acquistare una licenza personale da 25 $. Ho provato fino al livello 3, ma se tutti i livelli sono simili a quelli gratuiti, penso che valga il prezzo!

E così sono tornato su Vim , in VS Code ora. Devo ammettere che all’inizio mi sentivo abbastanza lento, ma, giorno dopo giorno, sento che sto migliorando e che forse sarò più efficiente di prima nel prossimo futuro.
Penso che usare Vim in VS Code possa essere un’esperienza “strana” se non ci sei abituato, ma con un po ‘di impegno e molta pratica può essere davvero soddisfacente!


Articolo a cura di Federico Gambarino

#jointherevolution

System Versioned Tables

Le tabelle con controllo delle versioni di sistema spiegate col Signore degli Anelli

Se entraste in una stanza piena di informatici e domandaste ad alta voce: “Chi di voi non ha mai cancellato dei dati per sbaglio?”, contando le mani alzate avreste una stima piuttosto accurata di quanti bugiardi avete di fronte.

Nei miei anni di lavoro su SQL Server, ammetto che mi è capitato più di una volta, per distrazione, per una convinzione errata, o per avere scritto male una condizione, di lanciare un comando che ha distrutto o modificato molti più record di quanto fosse la mia intenzione. Un’azione del genere spalanca prospettive raramente rosee, ma con gradi di gravità che possono distribuirsi su un ventaglio molto ampio: dalla semplice seccatura di doversi inventare 10 nuovi casi in ambiente di sviluppo, allo scenario da incubo di avere destinato all’oblio migliaia di righe in produzione.

Non è scopo di questo articolo una disamina approfondita sulle buone pratiche di backup di un DB, ma vorrei raccontarvi di uno strumento messo a punto su Management Studio, attivo dalla versione 2016, che può rivelarsi molto utile non solo in caso di emergenza, ma anche nella gestione abituale di qualche tabella cruciale di cui si vuole mantenere o analizzare la storia nel tempo.

L’argomento di cui vorrei parlare in questo articolo riguarda le “Temporal Tables” oppure “System-Versioned Tables”; tra le due nomenclature la mia simpatia vira con decisione verso la seconda, dato che la prima (benché sia la più usata) potrebbe generare confusione con le tabelle cancelletto (Temporary Tables), nate con una funzione completamente diversa. La dicitura più esaustiva e corretta sarebbe “System-Versioned Temporal Tables” non immune da una certa prolissità, ma d’ora in poi le chiamerò “tabelle con controllo delle versioni di sistema”, come riportato nella versione italiana di SSMS.

Partiamo con la definizione nuda e cruda:

Una tabella con controllo delle versioni di sistema è un tipo di tabella definita dall’utente, progettata per mantenere una storia completa dei cambiamenti sui dati e permettere una facile gestione nell’analisi di questi cambiamenti nel tempo. Questo tipo di tabella è detta “System-Versioned” perché il periodo di validità di ciascuna riga è gestito dal sistema (cioè dal motore di database).

Per entrare subito in medias res, fornirò un esempio pratico dell’utilizzo di questa funzionalità.

Qui di seguito ho riportato lo script di creazione di una tipica tabella con controllo delle versioni di sistema

Se fino alla quinta riga la sintassi è del tutto abituale, quelle successive aprono scenari molto più interessanti; questo script infatti non si limita a creare una sola tabella, ma due, strettamente collegate tra di loro. La prima è la tabella principale (nel nostro caso la dbo.LOTR), dal comportamento del tutto simile a una normalissima tabella, la seconda è la tabella dello storico (la dbo.LOTRHistory, definita a riga 9 dello script), nella quale sarà registrata la cronologia di tutti i cambiamenti operati nel tempo sulla tabella principale.

Senza specificare un nome personalizzato per la tabella dello storico, SQL Server avrebbe generato automaticamente un nome del genere: dbo.MSSQL_TemporalHistoryFor_xxx, con l’id dell’oggetto al posto di xxx. Suppongo sia meglio scegliersi il nome da soli.

Lo stretto legame tra le due tabelle si può riscontrare facilmente guardando l’esplora oggetti.

Le colonne della tabella dbo.LOTRHistory, creata automaticamente dallo script, saranno (per nome e per tipo), esattamente uguali a quelle della dbo.LOTR, ma senza nessuno dei vincoli originali (chiave primaria, chiavi esterne etc.); anche gli indici e le statistiche non discendono dalla tabella principale e potranno essere gestiti in modo del tutto indipendente.

Che non siano tabelle normali lo si può riscontrare anche osservando che, nel menu di entrambe, non è prevista l’opzione “Elimina”.

Se volessimo eliminare una delle due entità sarebbe necessario utilizzare questo comando per svincolarle dal versionamento.

Un’altra caratteristica essenziale per la creazione di una tabella con controllo delle versioni di sistema è la presenza di due colonne di tipo datetime2, cioè la SysStartTime e la SysEndTime (righe 6 e 7 dello script di creazione), il cui contenuto è infatti gestito direttamente dal sistema; questa loro particolarità ci impedirà di apportare qualunque intervento o modifica su di loro. Grazie a queste due colonne sarà possibile tenere traccia del momento preciso in cui un record della tabella dbo.LOTR ha subìto una variazione di qualche tipo.

Ma procediamo con il nostro esempio pratico, inserendo un po’ di dati all’interno della tabella principale. La popoleremo con i personaggi del romanzo “Il Signore degli Anelli”, di Tolkien, e la qualifica che hanno all’inizio del libro

Proviamo a fare una select della tabella e vediamo cosa restituisce.

Finora non sembrano esserci particolari soprese, anche se avrete notato che le due colonne SysStartTime e SysEndTime, pur non essendo state valorizzate esplicitamente nella insert, hanno assunto rispettivamente i valori della data in cui è stato effettuato l’inserimento, e della data più grande disponibile nel formato datetime2, ovvero: 9999-12-31 23:59:59.9999999.

Proviamo a vedere cosa accade se eseguiamo un’operazione di update sui personaggi del nostro elenco che diventeranno parte della Compagnia dell’Anello, aggiornando la loro qualifica con il valore “Membro della compagnia dell’Anello”.

Se interroghiamo la tabella principale, troviamo esattamente quello che possiamo aspettarci da un’operazione compiuta su una qualsiasi tabella della nostra base dati, ovvero:

È immediato notare che non è cambiata solo la qualifica dei membri interessati, ma anche la loro SysStartTime, che riporta l’ora della modifica. Il record relativo a Saruman, non essendo coinvolto dall’update, ha mantenuto invariata la SysStartTime di prima, corrispondente al momento della sua creazione.

Se non ci interessa visualizzare il valore delle colonne SysStartTime e SysEndTime a ogni select, sarà sufficiente dichiarare “hidden” le due colonne in questione nello script di creazione iniziale.

La faccenda si fa più interessante se guardiamo cosa è successo nella tabella dbo.LOTRHistory, di cui per semplicità tireremo fuori solo i risultati relativi a Boromir.

Dato che la tabella dello storico contiene solo i dati relativi a ciò che c’era nel passato, troveremo un unico record, corrispondente al valore della ormai obsoleta qualifica di Boromir, con data SysEndTime identica alla SysStartTime assegnata allo stesso personaggio sulla tabella dbo.LOTR.

Ovviamente, se cercheremo di ripetere la stessa query sulla dbo.LOTRHistory per Saruman, che non ha subìto modifiche dopo essere stato creato, non troveremo nessun record.

La cronologia sulla dbo.LOTRHistory terrà traccia anche di tutti i cambiamenti successivi, tant’è vero che se eseguo un nuovo update su Boromir, una select su dbo.LOTR restituirà il valore aggiornato come avrebbe fatto una normalissima tabella.

Nella dbo.LOTRHistory, a questo punto, troveremo due record: uno per ciascuno degli stati precedenti di Boromir.

In questo frangente si capisce come mai la tabella dbo.LOTRHistory non abbia gli stessi vincoli della sua gemella: due cambiamenti sul record con Id = 1 nella tabella dbo.LOTR portano ad avere due record con Id = 1 sulla tabella dello storico, condizione che avrebbe generato un errore di violazione di chiave se la dbo.LOTRHistory avesse ereditato la PK dalla tabella principale.

È anche facile notare come tutti i cambiamenti consecutivi registrati nella dbo.LOTRHistory abbiano la SysEndTime del record più vecchio coincidente con la SysStartTime del nuovo, proprio come la SysEndTime del nuovo coinciderà con la SysStartTime del valore corrispondente sulla tabella principale.

Se conoscete il Signore degli Anelli, saprete che alla fine del primo episodio Boromir passa a miglior vita, per questo motivo saremo costretti a cancellarlo dalla nostra tabella dbo.LOTR.

Il risultato che otteniamo dopo questa operazione non è molto diverso da quanto possiamo aspettarci, cioè la tabella principale non avrà più nessun record relativo a Boromir, ma la sua tabella dello storico dbo.LOTRHistory ospiterà tutte le sue precedenti incarnazioni.

Finora abbiamo incontrato una netta separazione tra presente e passato; o abbiamo eseguito una query sulla dbo.LOTR per avere un quadro della situazione al momento attuale, o abbiamo eseguito una query sulla dbo.LOTRHistory, per ottenere lo scenario completo sugli stati passati di uno dei personaggi. Verrebbe da chiedersi se esiste un modo per avere una visione d’insieme di tutti gli stati, quelli passati e quello attuale; la risposta ovviamente è sì, e consiste nell’eseguire una query sulla dbo.LOTR utilizzando la clausola FOR SYSTEM_TIME ALL.

Dato che Boromir non è più nella tabella principale, faremo la prova con un altro personaggio ancora attivo, cioè Sam.

È chiaro che, nella storia di ciascun personaggio, possiamo sempre riconoscere come attualmente valido il solo e unico record che reca come data nella SysEndTime il valore 9999-12-31 23:59:59.999999; nel caso di valori cancellati, invece (come per Boromir), nessuna SysEndTime assumerà tale valore, essendo la SysEndTime con data più alta quella corrispondente al momento dell’eliminazione del record.

Ci sono in tutto cinque possibili condizioni per la clausola FOR SYSTEM_TIME, che ci consentono una buona flessibilità al fine di ottenere le informazioni che vogliamo rispetto al tempo, vale a dire

  • ALL
  • AS OF
  • FROM TO
  • BETWEEN AND
  • CONTAINED IN ( , )

Scorrendo velocemente il loro utilizzo abbiamo che la AS OF dà l’immagine del dato in un preciso istante nel tempo. Sapendo che il personaggio di Boromir è stato creato alle 8:56 della mattina del 2 Agosto 2020 con il titolo di Capitano di Gondor e modificato più di tre ore dopo, non è sconvolgente scoprire che il risultato della query che ne richiede lo stato alle 8:57 restituisce la sua qualifica iniziale.

La FROM … TO e la BETWEEN hanno sostanzialmente lo stesso scopo, cioè quello di fornire tutta la storia di un record in un determinato intervallo di date

La sottile differenza tra le due è data dal fatto che la BETWEEN mostrerà anche un cambiamento il cui inizio coincide esattamente con l’estremo superiore dell’intervallo di date scelto. Abbiamo perciò che il cambiamento di stato di Boromir a “Membro poco convinto della Compagnia dell’Anello” avvenuto in questa data: 2020-08-02 12:55:23.3687849, a parità di intervalli sarà mostrato solo dalla BETWEEN e non dalla FROM … TO.

Da ultima, la CONTAINED si limita a restituire i periodi contenuti interamente (quindi iniziati e conclusi) nell’intervallo di tempo specificato

Per avere un promemoria del funzionamento di queste clausole, trovo sempre utile aiutarmi con una rappresentazione grafica; in questo caso i quattro stati rappresentati racchiudono tutta la storia degli stati, compreso quello in corso (se esiste).

Conclusioni:

Le tabelle con controllo delle versioni di sistema sono uno strumento molto utile non solo per recuperare dati cancellati inavvertitamente da tabelle sensibili (una sorta di backup tabellare), ma anche per ricostruire la storia di un determinato dato e il suo andamento nel tempo senza dover ricorrere a procedure, trigger o altri mezzi dalla manutenzione macchinosa. Sicuramente, data la grande mole di informazioni che può accumularsi nel tempo (ad es. una tabella con molte colonne che viene aggiornata spesso), può valere la pena di considerare qualche meccanismo di pulizia periodica di tali tabelle; è però importante tenere a mente che questo strumento è stato creato pensando ad una conservazione del dato per lunghi periodi, e che un uso intelligente di indici e statistiche sulla tabella dello storico (indipendenti dalla tabella principale) può aumentarne considerevolmente l’efficienza senza dover ricorrere a misure che rischierebbero di snaturarne lo scopo.

Script con il codice usato nell’articolo:

https://bit.ly/2PvKyMo

Fonti:

https://www.mssqltips.com/sqlservertip/3680/introduction-to-sql-server-temporal-tables/

https://docs.microsoft.com/en-us/sql/relational-databases/tables/temporal-tables

https://www.sqlshack.com/temporal-tables-in-sql-server/

#jointherevolution