Nell'ambito dell'apprendimento di relazioni, l'embedding del grafo di conoscenza, (KGE), noto anche con il nome di knowledge representation learning (KRL), è una forma di apprendimento di rappresentazioni che mira ad apprendere una rappresentazione a bassa dimensionalità delle entità e relazioni che costituiscono un KG, cercando di preservare la loro semantica. È quindi possibile usare questa rappresentazione del KG per varie applicazioni come la predizione di collegamenti (link prediction) fra entità, la classificazione delle triple, l'identificazione delle entità, il clustering e l'estrazione di relazioni.

Definizioni Un KG o grafo della conoscenza, , è una struttura che, a partire da una collezione di entità e una collezione di relazioni (binarie), definisce un insieme di fatti . Un fatto è una tripla che denota un collegamento mediante la relazione intercorrente tra la testa (head) e la coda (tail) della tripla. Tale rappresentazione rinviene dal modello dei dati del resource description framework (RDF) in cui gli enunciati sono definiti in termini di triple soggetto-predicato-oggetto. Un KG serve a rappresentare la conoscenza relativa ad un dato dominio; sfruttando la sua rappresentazione strutturata è possibile inferire nuova conoscenza con opportuni passi deduttivi o di raffinamento. Tuttavia l'uso dei KG in applicazioni complesse si confronta con limitazioni legate alla sparisità dei dati (pochi fatti disponibili rispetto alla vastità dello spazio di rappresentazione) con i conseguenti problemi di scalabilità dei metodi a livello computazionale.

Per tali motivi, l'embedding di un KG traduce ogni entità e relazione del grafo in una struttura di dimensionalità limitata, tipicamente vettori di dimensione prefissata , anche detta dimensione di embedding. In casi più generali, si possono avere differenti dimensionalità per le rappresentazioni delle entità e delle relazioni, ricorrendo anche strutture più complesse (matrici o tensori) . La rappresentazione del KG risultante sarà più densa, prestandosi ad un uso più efficiente (manipolazioni algebriche) e potrà essere più facilmente sfruttata in molteplici casi d'uso.

L'embedding di un KG è caratterizzato da quattro aspetti differenti:

Spazio di rappresentazione: È lo spazio dimensionalmente più piccolo rispetto a quello di partenza che viene usato per rappresentare le entità e le relazioni. Funzione di punteggio: È una misura della correttezza della rappresentazione incorporata delle triple. Modello di codifica: È la modalità mediante la quale le rappresentazioni incorporate delle entità e delle relazioni interagiscono tra di loro. Informazioni aggiuntive: Qualunque informazione aggiuntiva proveniente dal KG che possa essere usata per arricchire la rappresentazione incorporata. Di solito, per ogni informazione aggiuntiva, viene definita una funzione di punteggio ad hoc che verrà poi integrata con la funzione di punteggio generale del modello.. Le informazioni aggiuntive possono anche codificare conoscenza di schema da sfruttare per migliorare la correttezza semantica.

Procedura di embedding Le diverse procedure di embedding di un KG seguono in genere uno schema comune. Prima di tutto i vettori (o le strutture più complesse) che andranno a rappresentare entità e relazioni vengono inizializzati in modo casuale.

Dopodiché, utilizzando un training set l'algoritmo itera l'ottimizzazione della rappresentazione incorporata corrente fino al raggiungimento di una condizione di arresto. Di solito, la condizione di arresto è dettata dalla necessità di evitare l'overfitting del modello rispetto al training set.

A ogni iterazione, viene campionato un insieme di triple dal training set, per ognuna delle quali viene generata casualmente una tripla corrotta, i.e. un fatto che non può essere vero rispetto alla semantica del grafo di conoscenza. La corruzione di una tripla involve la sostituzione della testa, della coda, o di entrambe, con un'altra entità in modo da rendere falso il fatto risultante. La coppia con la tripla originaria assieme alla tripla corrotta viene aggiunta a un insieme che costituisce un training set per la successiva ottimizzazione della rappresentazione, sfruttando la funzione di punteggio adottata.

Alla fine dell'esecuzione dell'algoritmo, l'embedding appreso dovrebbe aver estratto il significato dalle triple e dovrebbe mettere in grado di classificare correttamente altre triple non presenti nel grafo di conoscenza ma che sono vere nella sua interpretazione intesa.

Pseudo-codice Di seguito si riporta lo pseudo-codice che specifica una tipica procedura di embedding: algoritmo Calcolo dell'embedding delle entità e delle relazioni is input: Dato un training set , l'insieme delle entità , l'insieme delle relazioni , la dimensione di embedding output: vettori di embedding delle entità e delle relazioni

inizializzazione: con valori casuali dei vettori di embedding delle entità e delle relazioni

while not condizione di arresto do // campionamento di b triple dal training set for each in do // corruzione della tripla // estrazione di una tripla corrotta

end for Aggiornare i vettori di embedding minimizzando la loss end while

Indicatori delle prestazioni Questi indici vengono spesso usati per misurare la qualità dell'embedding di un modello. La semplicità degli indici li rende applicabili per valutare le prestazioni di un algoritmo di embedding anche in caso di grafi di grandi dimensioni. Dato un insieme di predizioni classificate da un modello, si possono definire tre differenti indici delle prestazioni: Hits@K, MR, and MRR.

Hits@k Hits@k o in breve, H@k, è un indice delle prestazioni che quantifica la probabilità di trovare la predizione corretta tra le prime migliori predizioni del modello. Di solito viene usato . Hits@k riflette la precisione di un modello di embedding nel predire correttamente la relazione tra due entità.

@

Valori più grandi indicano migliori qualità predittive.

Mean rank (MR) Mean rank è la media della posizione in una lista ordinata di un oggetto predetto da un modello tra tutti i possibili elementi che possono essere predetti.

Più il valore è piccolo, più il modello di embedding è affidabile.

Mean reciprocal rank (MRR)

Mean reciprocal rank misura il numero di triple che sono predette correttamente. Se la prima tripla è predetta correttamente, allora viene sommato 1, se la seconda tripla è predetta correttamente viene sommato , e così via.

Valori più grandi sono indice di modelli migliori.

Applicazioni Task di apprendimento automatico Il completamento di un grafo di conoscenza, knowledge graph completion (KGC) in inglese, è un task che mira a estrarre nuova conoscenza dal modello di embedding del grafo tramite diverse tecniche di inferenza. In particolare, si completa una tripla inferendo entità o relazioni mancanti. I sotto-task corrispondenti sono denominati predizione dell'entità o del collegamento, i.e. predire usando l'embedding dell'entità di coda / testa oppure le relazioni più probabili che connettono due entità date.

La classificazione delle triple è un problema di classificazione binaria. Data una tripla, il modello di embedding valuta la sua plausibilità ossia determina se il fatto sia vero o falso. La decisione sulla classificazione viene presa sulla base del valore della funzione di punteggio adottata rispetto ad una data soglia.

Il clustering è un'altra applicazione per la quale si può sfruttare un embedding sparso al fine di condensare la rappresentazione di entità semanticamente simili, quindi vicine in uno spazio a bassa dimensionalità.

Applicazioni nella vita quotidiana L'uso del KGE è sempre più pervasivo in molte applicazioni.

Nel caso dei sistemi di raccomandazione, gli embedding possono aiutare a superare le limitazioni rinvenienti dall'uso dell'apprendimento per rinforzo. Per addestrare questo tipo di sistemi è necessario avere a disposizione un gran numero di informazioni sugli utenti, ma sfruttando l'uso di un grafo già costruito per rappresentare conoscenza riguardante le correlazioni degli elementi e usando i modelli di embedding si possono inferire raccomandazioni, risolvendo le limitazioni di cui sopra. In farmacologia, il drug repurposing riguarda il riutilizzo di un farmaco già presente sul mercato per uno scopo terapeutico differente da quello iniziale. Sfruttando i diversi grafi con conoscenza biomedica generati grazie alla vasta letteratura del settore e tramite tecniche di link prediction sui relativi modelli di embedding è stata dimostrata la possibilità di scoprire nuove relazioni (indicazioni) tra farmaci e malattie . L'incorporamento di KG è stato anche utilizzato nel dominio delle politiche sociali.

Modelli

Data una collezione di triple (o fatti) , l'embedding del KG produce, per ogni entità e ogni relazione presente nel grafo un vettore continuo atto a preservarne la semantica. denota l'embedding di una tripla , con e , dove e sono, rispettivamente, le dimensioni degli embedding delle entità e delle relazioni. La funzione di punteggio di un dato modello, denotata con , misura la distanza fra gli embedding di e dato quello di , o in altra parole, quantifica la plausibilità della rappresentazione del fatto corrispondente .

Rossi et al. hanno proposto una tassonomia dei modelli di embedding che identifica tre principali famiglie: modelli a decomposizione di tensori, modelli geometrici e modelli di apprendimento profondo. Una cronologia dei principali modelli delle diverse famiglie è mostrata in figura. Modelli a decomposizione di tensori I modelli a decomposizione del tensori sono una famiglia di modelli di embedding dei KG che per rappresentare il grafo usano una matrice multidimensionale esplorabile solo in parte: un KG non rappresenta completamente un dominio. In particolare, questi modelli usano un tensore tridimensionale, che viene decomposto in vettori di dimensioni inferiori che rappresentano gli embedding di entità e relazioni. Il tensore è una struttura adatta a rappresentare in modo semplice un KG poiché tiene conto della possibile esistenza di relazioni tra entità senza bisogno di conoscenza pregressa che riguardi la struttura del grafo, rendendo i modelli di questa classe leggeri e di facile addestramento pur soffrendo di problemi legati alla loro sparsità a causa dell'alta dimensionalità.

Modelli bilineari Questa famiglia di modelli utilizza equazioni lineari per incorporare le connessioni tra le entità in relazione fra loro. In particolare, la rappresentazione incorporata delle relazioni è una matrice bidimensionale. Durante la procedura di embedding, questi modelli utilizzano solo singoli fatti per calcolare la rappresentazione incorporata e ignorano le altre associazioni alla stessa entità o relazione. DistMult: Dal momento che la matrice di embedding della relazione è una matrice diagonale, la funzione di punteggio non può distinguere fatti asimmetrici. ComplEx: Come DistMult utilizza una matrice diagonale per rappresentare le relazioni, ma ComplEx adotta una rappresentazione nello spazio vettoriale complesso e il prodotto hermitiano, ed è in grado di distinguere fatti simmetrici e asimmetrici. Questo approccio è scalabile in termini di costi di tempo e spazio anche su KG di grandi dimensioni . ANALOGY: Questo modello codifica nell'embedding la struttura analogica del KG per simulare il ragionamento induttivo. Utilizzando una funzione obiettivo differenziabile, ANALOGY gode di buone capacità di generalizzazione sul piano teorico e di scalabilità a livello computazionale. È stato dimostrato che un embedding prodotto da ANALOGY può essere visto come un caso speciale di quelli prodotti da DistMul, ComplEx e HolE.