Ranking database queries
Advanced Databases
Outline • ranking in IR • toepassing ranking bij database queries:
Topic 3: ranking van database queries
– many-answer problem – zero-answer problem
1
Classic ranking in IR
Ranking in IR
Basisprincipes • • • •
2
Uitgangspunten
bag of words model term frequency inverse document frequency vector space model
• collectie van N documenten boeken, tijdschriften, web-pagina’s; deze zijn geïndexeerd (inverted list)
Talloze uitbreidingen
• query (free text)
• phrase queries • Google ranking •…
opsomming van zoektermen q =
3
Ranking in IR
4
Ranking in IR: score Observatie 1
We zoeken naar een scorefunctie score(q,d) die overeenkomt met onze intuïtie betreffende relevantie
“Score van match tussen term t en document d is hoog als t vaak voorkomt in d” Term frequency tf(t,d) Het aantal voorkomens van term t in document d
5
6
1
Ranking in IR: score
Ranking in IR: score Collection frequency cf(t)
Observatie 2
aantal voorkomens van term t in collectie
query = <man, romantisch, zorgzaam>
Document frequency df(t) aantal documenten dat term t bevat
“Minder vaak voorkomende zoektermen moeten zwaarder wegen”
7
Ranking in IR: score
8
Ranking in IR: score
Inverse document frequency idf(t)
TF-IDF weging
idf(t) = log(N/df(t))
geeft aan term t in doc d een gewicht tf-idf(t,d) = tf(t,d) * idf(t)
zeldzame termen hebben een hoge idf
Vector view op documenten, queries een document d of een query q kan ten behoeve van scoring beschouwd worden als een vector over alle mogelijke zoektermen, met voor elke term een gewicht wt,d; dit kan zijn: tf, idf of tf-idf 9
Vector space model
10
Vector space model
Voor elk document d hebben we een vector
De cosine similarity tussen twee documenten d1 en d2 is het inproduct van de bijbehorende vectoren, gecorrigeerd voor de lengte
Op basis van het VSM gaan twee twee noties van similarity introduceren: 1. sim (d1,d2) 2. sim(q,d) voor query q en document d Punt 1 is van belang voor “more like this features”
… of, als je de vectoren eerst normaliseert voor hun Euclidische lengte (kleine letter v)
Daarbij zullen we gebruik maken van de notie van inproduct van twee vectoren 11
12
2
Vector space model
Vector space model
Het inproduct ( ook inner product, vector product) van twee vectoren kan op twee equivalente manieren uitgedrukt worden
Voorbeeld: drie romans Sense and Sensibility (Jane Austen), Pride and Prejudice (JA), Wuthering heights (Emily Brontë)
Cosine sim weging op tf
Voor genormaliseerde vectoren geldt dus:
13
Vector space model
Vector space model
Queries als vectoren
Voorbeeld
14
Visuele representatie Cosine Similarity
(N = 1.000.000)
15
Vector space model
16
Ranking op database queries Motivating example: “Scully query”
Er zijn talloze verfijningen
SELECT * FROM Profile WHERE skin_color = ‘grey’ AND skin_hair = 0 AND pupil_dilatation = ‘oval’ AND verbal_sound = ‘gargling’ AND length BETWEEN 3 AND 4 AND number_of_toes = 8 AND ESP_capability = ‘high’ AND character = ‘charming’
Voorbeeld: sublinear tf scaling
17
18
3
Ranking op database queries
Ranking op database queries
Twee mogelijke problemen Aanpak op basis van: 1. many answers
“Automated Ranking of Database Query Results”
er zijn veel tuples in de resultaattabel; kunnen we ranking-technieken uit de IR gebruiken?
Agrawal, Chaudhuri, Das, Gionis Microsoft Research
2. zero answers
Conference on Innovative Data Systems Research (CIDR), 2003
er zijn geen tuples die aan alle eisen voldoen, maar zouden we mbv. ranking een “zo goed mogelijk” antwoord kunnen geven?
19
Ranking op database queries
20
Ranking op database queries
Kernvraag 1
Basic query shape
Hoe generaliseer je de IR-maten en scores? SELECT * FROM R WHERE C1 AND … AND Ck
Definities
Hierin is conditie Ci van de vorm Aj = qj
We gaan vooralsnog uit van één tabel R met attributen { A1 , … , Am } en tupels { t1 , … , tn }
Een meer geavanceerde Ci is Aj IN (qj1, … , qjl)
21
Generaliseer klassieke IR
22
Generaliseer klassieke IR
(Her)definities
(Her)definities
Wat is in deze database-context de tegenhanger van het begrip:
Gegeven attribuut Ak; Voor elke waarde t uit dom(Ak) is Fk(t) het aantal tuples in R met Ak = t
• • • • • •
document query term tf df idf
Laat N = |R|; we definiëren idfk(t) = log(N/Fk(t)) We definiëren de similarity coefficiënt S(u,v) = idfk(t) als u = v, anders 0 23
24
4
Generaliseer klassieke IR
Generaliseer klassieke IR
(Her)definities
Complicaties
Gegeven een tuple T = en een query Q =
1. attribuut is niet categorisch maar numeriek
de similarity tussen T en Q is:
2. conditie heeft vorm Aj IN (qj1, … , qjl)
>> zie donderdag
neem dan de maximale S(tj,qji) in de cosine similarity
In feite is dit weer de Cosine Similarity met TF-IDF-weging 25
26
Use the workload
QF-similarity Observatie 1 In een onroerend goed database zijn nieuwe woningen vaker vertegenwoordigd dan oude. Hun IDF is dus lager. Toch is de vraag naar nieuwe woningen groter.
Oplossing 1 Laat een domeinexpert de weging bepalen: duur, applicatie-afhankelijk
Oplossing 2
Observatie 2 In een boekwinkel is de vraag naar een bepaalde auteur niet afhankelijk van het aantal boeken dat hij/zij geschreven heeft. De IDF geeft hier ook geen goede indicatie
Haal je weging uit de query workload (automatisch); dit is de verzameling queries die gedurende de levensduur van je database uitgevoerd zijn
27
28
QF-similarity
QF-similarity
QF similarity: gebruik de workload QF(q) neemt de rol van TF over in de Cosine Similarity:
Definities
S(t,q) = QF(q) als q = t, anders 0
RQF(q) is de “raw frequency” van waarde q onder attribuut A in de workload RQFMAX is de frequentie van de meest voorkomende term QF(q) = RQF(q)/RQFMAX
En wederom:
29
30
5
Attribute similarity
Attribute similarity W(t) is de subset van de queries in de workload waarin waarde t voorkomt in een IN-clause: t IN (Toyota, Nissan, Honda)
Observatie query op attributen merk, type:
De Jacquard coefficient meet de similarity tussen sets W(t) en W(q):
tuples: in beide gevallen is de S(qi,ti) = 0 maar …
31
32
Zero answers
Many answers
Aanpak
Aanpak
In plaats van stricte match op alle condities geef je een top-k selectie op basis van ranking
Kijk naar ontbrekende attributen breid je similarity uit met
Experimentele resultaten
of met
Beste resultaten: QF_IDF > QF > IDF Naarmate de workload groeide, nam de kwaliteit van QF toe
33
Experimentele resultaten QF > IDF
34
Implementatie • prototype gebruikt variant van Fagin’s top-k algorithme
• attribute similarity op basis van data mining techniek • opgave 3: donderdag inleidende presentatie door Nicola Barile
35
6
