•1

Corso di Basi di Dati e Sist. Inf. su Web 2005-2006 - Massimo Ruffolo - Semantic Information Extraction 1

Basi di Dati e Sistemi Informativi su Web

Corso di Laurea Specialistica in Ingegneria Informatica

Massimo Ruffolo

E-mail: ruffolo@icar.cnr.itWeb: http://www.icar.cnr.it/ruffolo

Istituto di CAlcolo e Reti ad alte prestazioni del Consiglio Nazionale delle Ricerche (ICAR-CNR)

Exeura s.r.l. – Spin-off dell’Università della Calabria

Corso di Basi di Dati e Sist. Inf. su Web 2005-2006 - Massimo Ruffolo - Semantic Information Extraction 2

Il sistema HιLεX

• Obiettivi:

– trattare informazioni in formato semi- e non strutturato

– implementare un approccio semantico all’estrazione di informazioni

• Idee centrali alla base dell'approccio proposto:

– uso di ontologie per modellare la conoscenza da estrarre

– adozione del linguaggio DLP+ (una estensione della DLP con le nozioni del paradigma orientato agli oggetti) per la rappresentazione delle ontologie

– rappresentazione bidimensionale dei documenti

– utilizzo di una grammatica bidimensionale per la rappresentazione dei pattern di estrazione

– riconoscimento dei pattern mediante il supporto di un motore di reasoning (DLV)

•2

Corso di Basi di Dati e Sist. Inf. su Web 2005-2006 - Massimo Ruffolo - Semantic Information Extraction 3

La rappresentazione della conoscenza in HιLεX

• La semantica delle informazioni da estrarre è rappresentata mediante ontologie DLP+ aventi come root class: “element”.

• Ogni istanza di element è caratterizzata da tre attributi:

– expression che descrive un concetto utilizzando un particolare formalismo

– type che specifica il tipo di formalismo usato nell'attributo expression

– label che descrive in modo informale il concetto in questione.class element (expression: string, type: expression_type(*), label: string).

(*)class expression_type ().

Corso di Basi di Dati e Sist. Inf. su Web 2005-2006 - Massimo Ruffolo - Semantic Information Extraction 4

La rappresentazione della conoscenza in HιLεX

class short_date isa {syntactic_element}.class italian_short_date isa {short_date, italian_language_element}.

Esempio

class linguistic_element isa {element}.class language_element isa {element}.

class italian_language_element isa {language_element}.class english_language_element isa {language_element}....class spanish_language_element isa {language_element}.

class syntactic_element isa {element}.class structural_element isa {element}.

•3

Corso di Basi di Dati e Sist. Inf. su Web 2005-2006 - Massimo Ruffolo - Semantic Information Extraction 5

La rappresentazione della conoscenza in HιLεX

Alcuni esempi

class number isa {syntactic_element}.signed_float: number (type: regexp_type,

expression: "[+-]\\d{1,3}(?>.\\d{3})*,\\d+",label: "float con segno").

class financial_element isa {element}.class stock_index isa {financial_element}.

dowJones: stock_index (type: dict_type,expression: "Dow Jones",label: "nome di indice di borsa").

Corso di Basi di Dati e Sist. Inf. su Web 2005-2006 - Massimo Ruffolo - Semantic Information Extraction 6

La rappresentazione bidimensionale dei documenti

•4

Corso di Basi di Dati e Sist. Inf. su Web 2005-2006 - Massimo Ruffolo - Semantic Information Extraction 7

La rappresentazione bidimensionale dei documenti

• Un documento:

– viene proiettato su di un piano cartesiano…

– …e scomposto in regioni rettangolari chiamate “portion”

(x1,y1)

(x2,y2)

(x3,y3)

(x4,y4)

• Una portion:

– è identificata da una coppia di punti a coordinate intere…

– …e rappresenta un elemento a cui è associata una particolare semantica

signed_floatdowJones

Corso di Basi di Dati e Sist. Inf. su Web 2005-2006 - Massimo Ruffolo - Semantic Information Extraction 8

Le portion e gli operatori in DLP+

class point (x: integer, y: integer).

relation portion (p: point, q: point, elem: element).

relation strictFollow (p1: point, q1: point, elem1: element,p2: point, q2: point, elem2: element).

relation strictBelow (p1: point, q1: point, elem1: element,p2: point, q2: point, elem2: element).

relation westEastRecurrence (p: point, q: point,elem: element, n: integer).

relation northSouthRecurrence (p: point, q: point,elem: element, n: integer).

relation minContain (p1: point, q1: point, elem1: element,p2: point, q2: point, elem2: element).

•5

Corso di Basi di Dati e Sist. Inf. su Web 2005-2006 - Massimo Ruffolo - Semantic Information Extraction 9

Gli operatori di base su portion

• horizontal_next:

– definisce formalmente se due portion sono adiacenti orizzontalmente

• vertical_next:

– definisce formalmente se due portion sono adiacenti verticalmente

• contain:

– definisce formalmente se due portion sono l’una contenuta nell’altra.

Corso di Basi di Dati e Sist. Inf. su Web 2005-2006 - Massimo Ruffolo - Semantic Information Extraction 10

La grammatica per il riconoscimento di nuovi element

• L'obiettivo è quello di utilizzare un formalismo grammaticale per esprimere la derivazione di un nuovo elemento partendo da uno o piùelementi di base

• Le espressioni generabili prendono il nome di HιLεX (HIgh LEveleXpression). HιLεX è la sigla che dà il nome all'intero sistema.

•6

Corso di Basi di Dati e Sist. Inf. su Web 2005-2006 - Massimo Ruffolo - Semantic Information Extraction 11

Il costrutto GENERALIZATION

class stock_index_cell isa {stock_index_structure}.

dowJones_cell: stock_index_cell (

type: hilex_type,

expression: "orContain_generalizationOf (arg: html_cell, inArg: dowJones,

condition: null)",

label: "cella contenente un nome di indice di borsa").

html_celldowJonesdowJones_cell stock_index_cell

Corso di Basi di Dati e Sist. Inf. su Web 2005-2006 - Massimo Ruffolo - Semantic Information Extraction 12

Il costrutto CHAIN

stock_index_variation_row: stock_index_structure (

type: hilex_type,

expression: “sequenceOf (arg: [stock_index, unsigned_float,

signed_float, percentage], dir: horizontal, sep: sep_01",

label: “riga contenente variazioni di un indice di borsa").

stock_index unsigned_float signed_float percentage

stock_index_variation_row

•7

Corso di Basi di Dati e Sist. Inf. su Web 2005-2006 - Massimo Ruffolo - Semantic Information Extraction 13

Il costrutto RECURRENCE

stock_index_table: stock_index_structure (

type: hilex_type,

expression: “recurrenceOf (arg: stock_index_variation_row,

range: <2,5>, dir: vertical)",

label: “tabella contenente stock_index_variation_row").

stock_index_variation_row

stock_index_variation_row

stock_index_variation_row

stock_index_structure

TechStar

DowJones

Nasdaqstock_index_table

Corso di Basi di Dati e Sist. Inf. su Web 2005-2006 - Massimo Ruffolo - Semantic Information Extraction 14

Il costrutto TABLE

stock_index_table: stock_index_structure (

type: hilex_type,

expression: “sequenceTableOf (arg: [stock_index, unsigned_float, signed_float,

percentage], range: <2,5>, dir: vertical, sep: sep_01),

label: “tabella contenente stock_index_variation_row").

techStar unsigned_float signed_float percentage

dowJones unsigned_float signed_float percentage

dasdaq unsigned_float signed_float percentage

stock_index_table

•8

Corso di Basi di Dati e Sist. Inf. su Web 2005-2006 - Massimo Ruffolo - Semantic Information Extraction 15

I dati estratti

Attraverso lapre-elaborazione del documento ed il riconoscimento dei nuovi pattern otteniamo come output le portionevidenziate in figura.

Corso di Basi di Dati e Sist. Inf. su Web 2005-2006 - Massimo Ruffolo - Semantic Information Extraction 16

Nel caso di un file di testo

sep_01: separator (type: hilex_type, expression: “recurrenceOf (arg: blank_char, range: *, dir: horizontal)", label: “separatore di blank_char").

•9

Corso di Basi di Dati e Sist. Inf. su Web 2005-2006 - Massimo Ruffolo - Semantic Information Extraction 17

I dati estratti dal file testuale

Corso di Basi di Dati e Sist. Inf. su Web 2005-2006 - Massimo Ruffolo - Semantic Information Extraction 18

Architettura generale

•10

Corso di Basi di Dati e Sist. Inf. su Web 2005-2006 - Massimo Ruffolo - Semantic Information Extraction 19

Il documento in input

Corso di Basi di Dati e Sist. Inf. su Web 2005-2006 - Massimo Ruffolo - Semantic Information Extraction 20

Il documento in input

bi_summary

•11

Corso di Basi di Dati e Sist. Inf. su Web 2005-2006 - Massimo Ruffolo - Semantic Information Extraction 21

La Knowledge Base

Corso di Basi di Dati e Sist. Inf. su Web 2005-2006 - Massimo Ruffolo - Semantic Information Extraction 22

La knowledge base

class business_intelligence isa {business_solution}.class business_process_automation isa {business_intelligence}.class business_process_management isa {business_process_automation}.

business_process_management_00: business_process_management (type: regex_type,expression: "BPM“).

business_process_management_01: business_process_management (type: hilex_type,expression: “sequenceOf (

arg: [lemma_business, lemma_process, lemma_management],dir: horizontal,sep: blank_char)“).

bi_summary: business_intelligence (type: hilex_type,expression: “andContain_generalizationOf (

arg: html_cell,inArg: [business_intelligence, html_cell]condition: notCoincident)“).

•12

Corso di Basi di Dati e Sist. Inf. su Web 2005-2006 - Massimo Ruffolo - Semantic Information Extraction 23

Il Query Analyzer

Corso di Basi di Dati e Sist. Inf. su Web 2005-2006 - Massimo Ruffolo - Semantic Information Extraction 24

Il Query Analyzer

portion (P, Q, bi_summary)

Elementi di base Elementi “hilex”

Query Analyzer

•13

Corso di Basi di Dati e Sist. Inf. su Web 2005-2006 - Massimo Ruffolo - Semantic Information Extraction 25

Il Document Analyzer

Corso di Basi di Dati e Sist. Inf. su Web 2005-2006 - Massimo Ruffolo - Semantic Information Extraction 26

Il Document Analyzer

Elementi di base

Portion contenentii concetti di base

Document Analyzer

Documento

•14

Corso di Basi di Dati e Sist. Inf. su Web 2005-2006 - Massimo Ruffolo - Semantic Information Extraction 27

Requisiti del Document Analyzer

• Modularità• Estendibilità• Flessibilità

• Efficienza• Scalabilità

Common Processing Architecture Common Processing Architecture (CPA)(CPA)

Corso di Basi di Dati e Sist. Inf. su Web 2005-2006 - Massimo Ruffolo - Semantic Information Extraction 28

La Common Processing Architecture

• L’esecuzione di un processo produttivo richiede, nella CPA, l’applicazione della seguente metodologia:

• Si individuano le sotto-fasi• Ad ogni sotto-fase si associa una rappresentazione

formale, detta “processing unit”• A partire da una descrizione del processo produttivo

(input, risultati intermedi, elaborazione finale), un componente genera i possibili grafi di connessione

• Viene scelto un grafo di connessione• A partire da tale grafo, un componente genera un oggetto

che consente di eseguire il processo iniziale

•15

Corso di Basi di Dati e Sist. Inf. su Web 2005-2006 - Massimo Ruffolo - Semantic Information Extraction 29

La Common Processing Architecture

Processing Processing unitsunits RepositoriesRepositories

Corso di Basi di Dati e Sist. Inf. su Web 2005-2006 - Massimo Ruffolo - Semantic Information Extraction 30

L’idea delle processing unit

Ogni processing unit:• Implementa un’interfaccia ben

definita• È un’unità auto-consistente,

descritta dal tipo di Input e di Output

• È un “attore” che risponde alle sollecitazioni di un manager super partes

• Può dichiarare la necessità di processing unit di supporto

•16

Corso di Basi di Dati e Sist. Inf. su Web 2005-2006 - Massimo Ruffolo - Semantic Information Extraction 31

Lo Unit Matcher

• Il criterio di base è il confronto tra i tipi di output e di input valutando le relazioni di ereditarietà tra classi

• Avvalendosi delle annotazioni introdotte con la JDK 5 èinoltre possibile discriminare processing unit altrimenti identiche quanto ai tipi gestiti

• Il modulo di confronto è sostituibile ed estendibile

Corso di Basi di Dati e Sist. Inf. su Web 2005-2006 - Massimo Ruffolo - Semantic Information Extraction 32

Grafi di processing unit

ResultResult11

ResultResult22

InputInput

•17

Corso di Basi di Dati e Sist. Inf. su Web 2005-2006 - Massimo Ruffolo - Semantic Information Extraction 33

Grafi di processing unit

Corso di Basi di Dati e Sist. Inf. su Web 2005-2006 - Massimo Ruffolo - Semantic Information Extraction 34

Il Planner implementato

• Sfrutta le primitive di concorrenza disponibili nella JDK5

• Esegue l’algoritmo entro i confini di un’unica JVM• Guida il flusso delle informazioni tra le processing unit

stabilendo dei “condotti virtuali”• Invia gli stimoli alle processing unit per guidarne i

cambiamenti di stato• Offre alle processing unit servizi di gestione dinamica

delle risorse• Implementa politiche di gestione che tendono ad

ottimizzare lo sfruttamento delle risorse e della capacità di calcolo

•18

Corso di Basi di Dati e Sist. Inf. su Web 2005-2006 - Massimo Ruffolo - Semantic Information Extraction 35

La catena per i file di testo semplice

…token(p1,q1,’management’).token(p2,q2,’systems’).…portion(p1,q1,eng_lemma_management).portion(p2,q2,eng_lemma_system).…

Corso di Basi di Dati e Sist. Inf. su Web 2005-2006 - Massimo Ruffolo - Semantic Information Extraction 36

La catena per le pagine HTML

…portion(p1,q1,eng_lemma_knowledge).…portion(p2,q2,eng_lemma_system).…

•19

Corso di Basi di Dati e Sist. Inf. su Web 2005-2006 - Massimo Ruffolo - Semantic Information Extraction 37

I vantaggi della CPA

• Semplicità la gestione della concorrenza èdemandata interamente al framework

• Flessibilità senza cambiare il codice delle processing unit è possibile:

– Riorganizzarle per adattarsi a vari processi– Eseguire lo stesso processo in ambienti

differenti (per esempio J2EE)• Scalabilità l’adattamento alle risorse disponibili è

gestito automaticamente dal framework

Corso di Basi di Dati e Sist. Inf. su Web 2005-2006 - Massimo Ruffolo - Semantic Information Extraction 38

Le prestazioni

• Il Document Analyzer, basato sulla CPA, garantisce efficienza nel:

• trattamento di documenti molto vasti o complessi• riconoscimento di un gran numero di concetti

1.100mila

550mila

720mila

360mila

24sec22sec~1000pagg

13sec11sec~500pagg

O2O1Dimensioni

•20

Corso di Basi di Dati e Sist. Inf. su Web 2005-2006 - Massimo Ruffolo - Semantic Information Extraction 39

L’ Hilex Rewriter

Corso di Basi di Dati e Sist. Inf. su Web 2005-2006 - Massimo Ruffolo - Semantic Information Extraction 40

L’ Hilex Rewriter

Elementi “hilex”

moduli direasoning

DLP+

Hilex Rewriter

“sequenceOf (arg: [lemma_business, lemma_process, lemma_management], dir: horizontal, sep: blank_char)“

module (business_process_management_01){portion (P1, Q5, business_process_management_01) :-strictFollow (P1, Q1, lemma_business, P2, Q2, blank_char),strictFollow (P2, Q2, blank_char, P3, Q3, lemma_process),strictFollow (P3, Q3, lemma_process, P4, Q4, blank_char),strictFollow (P4, Q4, blank_char, P5, Q5, lemma_management).

}

•21

Corso di Basi di Dati e Sist. Inf. su Web 2005-2006 - Massimo Ruffolo - Semantic Information Extraction 41

Il Pattern Recognizer

Corso di Basi di Dati e Sist. Inf. su Web 2005-2006 - Massimo Ruffolo - Semantic Information Extraction 42

Il Pattern Recognizer

Portion di base

Nuoveportion

Pattern Recognizer

Moduli DLP+

•22

Corso di Basi di Dati e Sist. Inf. su Web 2005-2006 - Massimo Ruffolo - Semantic Information Extraction 43

Il Pattern Extractor

Corso di Basi di Dati e Sist. Inf. su Web 2005-2006 - Massimo Ruffolo - Semantic Information Extraction 44

Il Pattern Extractor

Portion

Pattern Extractor

Documento

•23

Corso di Basi di Dati e Sist. Inf. su Web 2005-2006 - Massimo Ruffolo - Semantic Information Extraction 45

Esempio applicativo: una pagina di DBLP

• DBLP: DigitalBibliography & Library Project

• L’obiettivo– Estrarre

dalla HomePagedel prof.N.Leonele pubblicazioni che vedono tra i co-autori il prof.D.Saccàe che trattano di DisjunctiveDeductiveDatabase

Corso di Basi di Dati e Sist. Inf. su Web 2005-2006 - Massimo Ruffolo - Semantic Information Extraction 46

Esempio applicativo: una pagina di DBLP

nicola_leone: unical_professor (type: regexp_type, expression: "(?>(?>N.)|(?>Nicola))Leone").domenico_sacca: unical_professor (type: regexp_type, expression: "(?>(?>D.)|(?>Domenico))

(?>(?>Saccà)|(?>Sacca)|(?>Sacca'))").disjunctive: english_lemma (type: dict_type, expression: "disjunctive").

deductive: english_lemma (type: dict_type, expression: "deductive").database: english_lemma (type: dict_type, expression: "database").

dblp_paper_title: dblp_paper_item (type: regexp_type, expression: "(?>[\\w\\s-\\.,àèioùé'])+:\\s(.+?)\\..+").

blank_char: special_char (type: dict_type, expression: " ").

•24

Corso di Basi di Dati e Sist. Inf. su Web 2005-2006 - Massimo Ruffolo - Semantic Information Extraction 47

Esempio applicativo: una pagina di DBLP

• Il passo successivo è il riconoscimento e la caratterizzazione degli elementi di alto livello– Sintagma Disjuntive Deductive Database– Titolo con Disjuntive Deductive Database– Articolo di N.Leone e D.Saccà

leone_and_sacca_paper_on_ddd: dblp_paper_item (type: hilex_type, expression: "andContain_generalizationOf (

arg: html_cell, inArg: [domenico_sacca, nicola_leone, ddd_dblp_paper_title], condition: notCoincident)"

).

Corso di Basi di Dati e Sist. Inf. su Web 2005-2006 - Massimo Ruffolo - Semantic Information Extraction 48