Basi di Dati e Sistemi Informativi su Web - staff.icar.cnr.itstaff.icar.cnr.it/ruffolo/files/Basi di...

•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: [email protected]: 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


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


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 ().



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



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").


La rappresentazione bidimensionale dei documenti

•4


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


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


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.


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


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


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


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_structure

TechStar

DowJones

Nasdaqstock_index_table


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


I dati estratti

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


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


I dati estratti dal file testuale


Architettura generale

•10


Il documento in input


Il documento in input

bi_summary

•11


La Knowledge Base


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


Il Query Analyzer


Il Query Analyzer

portion (P, Q, bi_summary)

Elementi di base Elementi “hilex”

Query Analyzer

•13


Il Document Analyzer


Il Document Analyzer

Elementi di base

Portion contenentii concetti di base

Document Analyzer

Documento

•14


Requisiti del Document Analyzer

• Modularità• Estendibilità• Flessibilità

• Efficienza• Scalabilità

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


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


La Common Processing Architecture

Processing Processing unitsunits RepositoriesRepositories


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


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


Grafi di processing unit

ResultResult11

ResultResult22

InputInput

•17


Grafi di processing unit


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


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).…


La catena per le pagine HTML

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

•19


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


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


L’ Hilex Rewriter


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


Il Pattern Recognizer


Il Pattern Recognizer

Portion di base

Nuoveportion

Pattern Recognizer

Moduli DLP+

•22


Il Pattern Extractor


Il Pattern Extractor

Portion

Pattern Extractor

Documento

•23


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



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



• 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)"

).


Basi di Dati e Sistemi Informativi su Web - staff.icar.cnr.itstaff.icar.cnr.it/ruffolo/files/Basi di...

Documents

Transcript of Basi di Dati e Sistemi Informativi su Web - staff.icar.cnr.itstaff.icar.cnr.it/ruffolo/files/Basi di...