Post on 01-May-2015
Documenti non strutturati sul Web e Semantica
palmonari@disco.unimib.it
Dott. Matteo Palmonari
–2–Rielaborato da Atzeni et al., Basi di Dati, Mc-Graw Hill
Semantica nelle basi di dati relazionali
• La semantica di una base di dati è definita in accordo con la struttura relazionale (algebra relazionale) ed è determinata, relativamente ai suoi elementi costitutivi (valori, tuple, relazioni), sostanzialmente da:• Livello dello schema:
• schema logico• definisce la macro-organizzazione della rappresentazione
di un dominio• vincoli di integrità
• definiscono vincoli relazionali di dettaglio tra specifici oggetti e fatti rappresentati
• Livello delle istanze:• insieme delle istanze
• costituisce l‘insieme di oggetti e fatti effettivamente rappresentati come veri nella bas di dati
–3–Rielaborato da Atzeni et al., Basi di Dati, Mc-Graw Hill
Semantica, Schemi e Istanze• Lo schema di una base di dati definisce le regole
generali cui deve aderire ciascun insieme di istanze (per essere considerato valido); è in questi termini che lo schema costituisce una parte fondamentale della semantica di una base di dati
• Tali regole (ad esempio i vincoli di integrità)• supportano l‘interrogazione delle basi di dati
(verifica della sussistenza o non sussistenza di alcuni fatti nella base di dati)
• permettono di controllare la validità dello schema• non permettono di dedurre nuove conoscenze
–4–Rielaborato da Atzeni et al., Basi di Dati, Mc-Graw Hill
Query nel modello relazionale• Il linguaggio di
interrogazione piùdiffuso per le basi di dati è SQL (Structured Query Language)
• Ragionamento piuttosto debole
SQL Query Example
•SQL (base/select)•Principio:
soddisfazione/correttezza•Meccanismo/semantica: algebra
relazionale
–5–Rielaborato da Atzeni et al., Basi di Dati, Mc-Graw Hill
–6–Rielaborato da Atzeni et al., Basi di Dati, Mc-Graw Hill
Esempi di altri data model
The Object-Oriented Data Model
–7–Rielaborato da Atzeni et al., Basi di Dati, Mc-Graw Hill
Objects/idAttributes
MethodsClasses
Class Hierachies
Alla base di JAVA/C++ etc
Object-Oriented Schema (Example)
–8–Rielaborato da Atzeni et al., Basi di Dati, Mc-Graw Hill
Cosa succede nel Web?
–9–Rielaborato da Atzeni et al., Basi di Dati, Mc-Graw Hill
•Ci sono ancora schemi e istanze?
•Che tipo di interrogazioni si possono fare?
•Che tipo di ragionamenti si possono fare?
Web page (Web 1.0)
Rielaborato da Atzeni et al., Basi di Dati, Mc-Graw Hill
10
Information Retrieval
The information retrieval system has to deal with the following tasks…
Micro-Introduction to Information Retrieval &
Search Engines
Slides and material from
Karl Aberer
EPFL-IC, Laboratoire de systèmes d'informations répartis
Information Retrieval – Document Model
• Generating structured representations of information items: this process is called feature extraction and can include simple tasks, such as extracting words from a text as well as complex methods, e.g. for image or video analysis.
Information Retrieval – Query Model
• Generating structured representations of information needs: often this task is solved by providing users with a query language and leave the formulation of structured queries to them. This is the case for example for simple keyword based query languages, as used in Web search engines. Some information retrieval systems also support the user in the query formulation, e.g. through visual interfaces.
Information Retrieval – Matching Model
• Matching of information needs with information items: this is the algorithmic task of computing similarity of information items and information need and constitutes the heart of the information retrieval model. Similarity of the structured representations is used to model relevance of information for users. As a result a selection of relevant information items or a ranked result can be presented to the user.
Information Retrieval - Efficiency
Since information retrieval systems deal usually with large information collections and/or large user communities, the efficiency of an information retrieval system is crucial. This imposes fundamental constraints on the retrieval model. Retrieval models that would capture relevance very well, but are computationally prohibitively expensive are not suitable for an information retrieval system.
Text Retrieval (search engines)
The currently most popular information retrieval systems are Web search engines. To a large degree, they are text retrieval system, since they exploit only the textual content of Web documents for retrieval. However, more recently Web search engines also start to exploit link information and even image information (e.g. Google’s page Rank). The three tasks of a Web search engine for retrieval are:
Text Retrieval (search engines)
1. extracting the textual features, which are the words or terms that occur in the documents. We assume that the web search engine has already collected the documents from the Web using a Web crawler.
Text Retrieval (search engines)
2. support the formulation of textual queries. This is usually done by allowing the entry of keywords through Web forms.
Text Retrieval (search engines)
3. computing the similarity of documents with the query and producing from that a ranked result. Here Web search engines use standard text retrieval methods, such as Boolean retrieval and vector space retrieval.
The Retrieval Model
• Determines– the structure of the document representation– the structure of the query representation– the similarity matching function•
• Relevance – determined by the similarity matching function – should reflect right topic, user needs, authority, recency– no objective measure•
• Quality of a retrieval model depends on how well it matches user needs !
• Comparison to database querying– correct evaluation of a class of query language expressions– can be used to implement a retrieval model
The Retrieval Model
• The heart of an information retrieval system is its retrieval model. The model is used to capture the meaning of documents and queries, and determine from that the relevance of documents with respect to queries. Although there exist a number of intuitive notions of what determines relevance one must keep clearly in mind that it is not an objective measure. The quality of a retrieval system can principally only be determined through the degree of satisfaction of its users. This is fundamentally different to database querying, where there exists a formally verifiable criterion for the task to be performed: whether a result set retrieved from a database matches the conditions specified in a query.
The Vector Space Model
Example
The document model
• the structure of the document representation– Term-document matrix
Example Vector-Space Retrieval
–Emanuele Della Valle - http://applied-semantic-web.org
Introduction
What does Google “understand”?
Understanding that• [page1] links [page2] page2 is interesting
Google is able to rank results!• “The heart of our software is PageRank™, a system for
ranking web pages […] (that) relies on the uniquely democratic nature of the web by using its vast link structure as an indicator of an individual page's value.”
http://www.google.com/technology/
–27
Pagine Web: query model
• Principio: “rilevanza” (documenti rilevanti)
• Meccanismo/semantica:– Contenuto: indicizzazione (feature extraction):
keywords + testo– Provenienza: pageRank– …
• Meccanismi sintattici e basati su criteri di trust
28
DirectoriesFile system
Web
Directories
Web
Directories
Blogs by topics
Directories: query model
• Principio: “appartenenza alla directory” (correttezza)
• Meccanismo/semantica:– Contenuto: documenti appartenenti alle
categorie / relazione di contenimento tra categorie
• Meccanismi di organizzazione gerarchica delle informazioni
32
Metadata / Tag / Folksonomies
• Metadati: dati che descrivono altri dati/documenti– E.g. creatore, autore, ultima modifica etc.– E.g. contenuto, caratteristiche, etc
• Sistemi di metadati Attributo-Valore– E.g. creatore: Matteo Palmonari– Spesso sistematizzati in standard o standard di fatto
• E.g. Dublincore (metadati generici)– http://dublincore.org/
• E.g. MPEG-7 (audio/video) – http://mpeg.chiariglione.org/standards/mpeg-7/mpeg-7.htm
• Sistemi di tag– E.g. Viaggi, Malesia, Mare
Metadata / Attribute-Value
File system
Music
Metadata / Attribute-ValueFile system / Images
Metadata / Attribute-ValueWeb / Images
Metadata & SearchWeb / Images
Metadata & SearchWeb / Images / Search: ‘where=malaysia’
Folksonomies
• Tagging systems – Tags (sort of concepts) associated with pieces of information
• E.g. blog posts, videos, pictures
• Tagging systems – Tags (sort of concepts) associated with pieces of information
• E.g. blog posts, videos, pictures
Folksonomies & Search
Tag Clouds
Folksonomies
Blogs
Folksonomies
• Tagging systems – Tags (sort of concepts) associated wit pieces of
information• E.g. blog posts, videos, pictures
– Semantic weaknesses:1.the ambiguity of tags, for one tag may refer to several concepts
;
2.the variability of the spelling, for several tags may refer to the same concept;
3.the lack of explicit representations of the knowledge contained in folksonomies, ambiguous relations between the piece of information and the tag;
4.the difficulties to deal with tags from different languages.
Folksonomies: query model
• Principio: “rilevanza”/”correttezza”
• Meccanismo/semantica:– Associazione tag:
• Per una query con un tag T, si trovano tutti I documenti relativi a T (annotati con T, annotati con tags simili a T etc…)
• Costruzione collaborativa dei sistemi di tag (tag cloud)
• Semantic Ambigua43
Schema vs Schemaless
• Uno schema per un insieme di dati specifica vincoli di carattere generale tra i dati– Tali vincoli organizzano in dati strutture– I dati organizzati in strutture per mezzo di schemi si
dicono dati strutturati (esempio: dati delle basi di dati relazionali)
– La struttura fornisce una chiave interpretativa per i dati
– La struttura può essere utilizzata per definire interrogazioni corrette rispetto al modello in oggetto
Schema vs Schemaless
• Esprimere vincoli su dati ha un costo:– Costo di creazione– Costo di mantenimento– Costo di gestione– Costo in termini di efficienza delle
procedure di interrogazione
Schema vs Schemaless
• Sistemi di metadati quali i sistemi di tag (annotazione) suppliscono alla mancanza di schema associando informazioni aggiuntive ai dati
• Tali informazioni possono supportare le procedure di interrogazione fornendo diverse dimensioni di ricerca e rendendole più precise
• La semantica di tali dati resta tuttavia più ambigua e, in generale, imprecisa
Schema vs Schemaless
• Come associare semantica in modo meno ambiguo sul Web?
• Annotazione dei contenuti sul Web con tecniche più sofisticate (XML, RDF, Ontologie)
Intensione/Estensione
• Nei dati strutturati è possibile individuare due aspetti delle informazioni e conoscenze rappresentate:– Intensione: vincoli generali di dominio – Estensione: dati, istanze di oggetti che
soddisfano determinati vincoliStudente Voto Lode Corso
32 01276545276545 30 e lode 02787643 27 e lode 03739430 24 04
EsamiParte Intensionale
Parte Estensionale
Estensione del concetto “voto di studente”
Intensione/Estensione
Linguaggi formali per rappresentare la conoscenza: Cosa rappresentare?
Concetti Predicati unari P(x)
Relazioni Predicati binari, ternari ... R(x,y), R(x,y,z)
Semantica standard su base insiemistica:
Concetti Insiemi
Relazioni Insiemi di n-uple
Rappresentazione ESTENSIONALE!
Statica...
Linguaggio (L)
Semantica (M)
Conoscenza sulla realtà
inferenza
Intensione/Estensione
Linguaggi formali per rappresentare la conoscenza: Cosa rappresentare?
Concetti Predicati unari P(x)
Relazioni Predicati binari, terziari ... R(x,y), R(x,y,z)
Semantica standard su base insiemistica:
Concetti Insiemi
Relazioni Insiemi di n-uple
Rappresentazione ESTENSIONALE!
Statica...
Linguaggio (L)
Semantica (M)
Conoscenza
Intensione/Estensione
Quello che interessa dal punto di vista della possibilità di fare inferenza è una caratterizzazione della rappresentazione che tratti concetti e relazioni indipendentemente dagli oggetti che nella circostanza specifica entrano a darne la definizione estensionale.
INTENSIONE di concetti e relazioni:
Proprietà formali di alto livello
Necessità di un linguaggio per definirle
Linguaggio (L)
Semantica (M)
Conoscenza
E.g. IN è transitiva
E.g. Inferire IN(x,z)
Da: IN(x,y) + IN(y,z)
inferenza
Intensione e inferenza
Proprietà di alto livello
(aspetti intensionali di una base di conoscenza)
1. Coinvolgono una sola relazione:
e.g. simmetria:
2. Coinvolgono più concetti/relazioni:
a - Interdipendenze e interdefinizioni tra relazioni
e.g. Nord Est = Nord ∩ Est
e.g. ?
b - Relazioni tra concetti
e.g. FiguraGeometrica e Triangolo...
),(→),( xyRyxR
),(↔),(∧),( yxNEyxEyxN
),(→),(∧),( zxNyzINyxN
)(→)( xicaFigGeometrxTriangolo
1- Inferenza: proprietà delle relazioni
1
1
1
1
a
b
c
d
e
f
a b c d e f
1 – Proprietà delle relazioni
e.g. IN: Transitività...
IN(a,b); IN(b,d); IN(d,e); IN(e,c)
),(),(),( zxINzyINyxIN →∧
Assioma di L
1- Inferenza: proprietà delle relazioni
1 1 1 1
1 1 1
1 1
1
a
b
c
d
e
f
a b c d e f
IN: Transitività...
IN(a,b); IN(b,d); IN(d,e); IN(e,c)
Altre proprietà?
e.g. antisimmetria?
Più proprietà? (coerenza?)
e.g. antisim + rifl + trans?
antisim + irrifl + trans ⇝⊥
Relazioni tra concetti
e.g. FiguraGeometrica e Triangolo...
)(→)( xicaFigGeometrxTriangolo
Figura geometrica
Triangolo Sfera ...
Triangolo IS-A FigGeometrica
Triangolo è sussunto da FigGeometrica ?
Triangolo eredita le proprietà di FigGeometrica ?
haPerimetro(x)
...Da 1.a:
NordEst IS-A Nord ???
),(),(∧),( yxNEyxEyxN ←
),(∧)(∧)(.)(∃ xyPartOfyPerimetroyicaFigGeometry
Schema, Vincoli, Ontologie
• Schema vs Schemaless: un continuoum• Schema, logicamente: un insieme più o meno
ricco di vincoli– Schema di database: insieme di vincoli piuttosto
ristretto– Schema di database più vincoli di integrità: insieme di
vincoli più sofisticato– Schema di database più vincoli di integrità più
business rules: insieme di vincoli molto sofisticato (infatti, intrattabile computazionalmente)
– “Ontologie”