Kam směřuje webové vyhledávání

Web-scale knowledge base

Tomáš HejlDotazovací jazyky II2010/2011

Web jako databáze

„Web-scale knowledge base“

Web obsahuje prakticky všechny dostupné znalosti

Současné vyhledávače umí nalézt stránku, která obsahuje

hledané informace neumí vytvářet souvislosti, odvozovat

2

Motivace„The Unreasonable Effectiveness of Data“

3

Fyzika vs. Vědy zahrnující člověka

FYZIKA

 

GRAMATIKA ANGLIČTINY(NEKOMPLETNÍ)

1700 stran textu

Přirozené zpracování textu není možné popsat jednoduše, jsou zapotřebí komplexní teorie. 4

Seznam slov

Google (2006)

Bilion slov včetně chyb, překlepů… včetně sekvencí slov do délky 5 a jejich

frekvencí

Zahrnuje veškeré lidské znalosti, kompletní model

5

Dosavadní úspěchy

Převod řeči na text Automatické překlady

Důvod? Pro mnoho lidí každodenní běžné aktivity Mnoho testovacích dat Velká motivace pro automatizaci

6

Méně úspěšné oblasti

Klasifikace dokumentů Rozpoznávání slovních druhů Syntaktická analýza (parsing)

V běžném životě nepříliš časté Málo testovacích dat Vyžadovány anotace lidským

expertem Anotace nebývají jednoznačné

7

Co jsme se zatím naučili I.Nespoléhat se na anotaceVyužít dostupná objemná data

Sémantické vztahy se dají často odvodit▪ Dotaz pro vyhledávač + Zvolená

odpověď▪ Formátovaná data na webu, tabulky se

záhlavím8

Co jsme se zatím naučili II. Lepší je jednodušší model s více

daty, než naopak

Podobnost s překlady Dříve: Složitá sémantická a syntaktická

pravidla Dnes: Rozsáhlá tabulka mapování frází

9

Co jsme se zatím naučili III.

Realita = nekonečné množství dat

Úspěšná reprezentace či aproximace= stačí řádově miliardy či biliony

příkladů

10

Co jsme se zatím naučili IV.Nevyřazovat ojedinělé případy

Jednotlivě jsou vzácné, ale společně tvoří model

Komplexní pravidla mohou zastarat Význam frází se mění, přibývají nová

slova

Komplexní pravidla nemusí stačit Lidé často nepíší podle pravidel, gramatiky,

pravopisu…11

Nejčastější přístup

Analýza pravděpodobnosti výskytů různých n-tic slov v textu

Mnoho jednoduchých automatických pravidel místo pravidel obecných

12

Sémantický webvs. Sémantická interpretaceDva přístupy

13

Porovnání

SÉMANTICKÝ WEB

Sémantika je ukryta v předem určených formátech

Lidé píšou v pevně daném formátu, počítače mu rozumí

SÉMANTICKÁ INTERPRETACE Sémantiku určují

lidé přirozenou tvorbou jazyka

Počítač se snaží text interpretovat

14

Sémantický web

15

Problémy sémantického webu I. Vytvoření ontologií

Již existují formáty pro mnoho témat (datum a čas, lokace, genové sekvence, rezervace hotelů…)

Méně používaná témata se zřejmě formátů nedočkají

Nutná shoda expertů, konkurenční společnosti prosazují vlastní formát

Drahé (Projekt Halo, převedení učebnice chemie, $10.000 za stránku)

16

Problémy sémantického webu II.

HTML STRÁNKA

Textový editor

SÉMANTICKÝ WEB

Webová služba

Databáze

Splnění všech požadavků na formát

Obtížné nasazení

17

Problémy sémantického webu III.Nutnost sémantické interpretace

zůstává, byť v menším měřítku

Stroj podle ontologie ví, že „Joe‘s Pizza“ je název firmy

Stroj neví, o kterou firmu s tímto názvem se jedná

Stroj neví, že jde o pizzerii 18

Sémantická interpretace

19

Sémantická interpretace

Obsah již existuje

Obsah je agregován a indexován

Obsah neumíme strojově interpretovat

20

Problém sémantické interpretace Jedno vyjádření různé významy Jeden význam různá vyjádření

Hledání synonym, atributů třídy… Pomocí tabulek v HTML Pomocí vyhledávacích dotazů

21

Získávání dat a souvislostí Web-scale knowledge base

22

Cíl - připomenutí

Nástroj

Umožňující propojení všech informací na webu

Automaticky odpovídající na faktografické dotazy

Doménově nezávislý, obecný23

Existující nástroje I.TextRunner

24

TextRunner Úvod University of Washington

Zaměření na obecný text

Analyzuje věty a vytváří systém trojic („Einstein se narodil v roce 1879“ přidá pár <Einstein,1879> do relace „narození“)

Podle frekvence výskytu kontroluje přesnost Validní informace o Einsteinově narození bude na mnoha webech

http://www.cs.washington.edu/research/textrunner/indexTRTypes.html

25

TextRunner Konkurence

Dipre

KnowItAll

SnowBall

Yago

Kylin26

TextRunner Výhody oproti konkurenci

Dávkový režim Podobně jako tradiční vyhledávače Zpracuje veškerá dostupná data najednou,

produkuje a ukládá velké množství trojic Konkurence vybírá kde hledat až podle

dotazu

Schéma si vytváří sám za běhu Konkurence vyžaduje schéma trojic, názvy

relací, fráze odpovídající relacím atd.27

TextRunner Nasazení

První test 9M stránek 1M trojic 88% úspěšnost

Druhý test 500M stránek 200M trojic Přesnost v době vydání článku (2008) ještě

nebyla známa 28

TextRunner Výstupní data

Odlišné od klasických relačních dat Počet „sloupců“▪ TextRunner – 2, SQL tabulky – více

Doména▪ SQL – „tabulkové“ hodnoty, v textu bývají

více textové Počet výskytů▪ TextRunner bere v úvahu jen vícenásobné

výskyty Názvy sloupců▪ TextRunner nemá pojmenované prvky relací 29

Existující nástroje II.WebTables

30

WebTablesÚvod

Google Research (+MIT, Univ. Washington, Berkeley)

Extrahuje data z HTML tabulek Jen 1.1% HTML tabulek obsahuje relační data! 154M tabulek je i tak největší relační databáze

vůbec (o 5 řádů)

31

WebTablesRozpoznání relační tabulky

Rozpoznání relační tabulky je obtížné

Krok 1. Vyhodit zřejmé nerelační tabulky Jen 1 řádek, 1 sloupec, kalendáře, HTML layout Ruční pravidla Odstraní cca 89% tabulek

Krok 2. Trénované statistické filtry Počet prázdných buněk, počet číselných dat, počet řádků a

sloupců… Obtížné a nedokonalé: 81% úplnost, 41% přesnost

125M rel.tab. + 146M falešných tabulek32

WebTablesDalší postup

Krok 3. Hledání metadat relací

71% relací má metadata

Na rozdíl od databází nemůžu počítat s cizími klíči atd.

Pouze hlavičky sloupců (někdy obtížné najít)▪ Opět trénované filtry▪ 89% přesnost, 85% úplnost

33

WebTablesVýhody

Tabulky přímo definují relace i jejich metadata

Tabulky určují příslušnost prvků do množin WebTables – všechny prvky sloupce TextRunner – ve „sloupci“ jsou různé

informace

Data z WebTables mohou rozšířit data z TextRunneru

34

Existující nástroje III.Deep-Web Crawl

35

Deep-Web CrawlDeep-Web data I.

Deep-Web = Data z běžných databází, dostupná pouze přes HTML formuláře

36

Deep-Web CrawlDeep-Web data II.

Na rozdíl od HTML tabulek nedostupné pomocí běžných vyhledávačů Neumí vyplňovat formuláře

Spekulace: Data v Deep-Web DB výrazně počtem převyšují doposud indexovaná data

Cca 10M takových formulářů37

Deep-Web CrawlProjekt

Google

Cíle Zpřístupnit Deep-Web DB pro

vyhledávání Univerzálně pro všechny typy formulářů

Projekt : Deep-Web Crawl Data z něj již jsou dostupná přes Google

38

Deep-Web CrawlDva přístupy: Integrace Vytvoření vyhledávačů-prostředníků pro každou doménu

(auta, knihy, nemovitosti…)

Dotaz na vyhledavač aut převede dotaz na jednotlivé dotazy pro všechny formuláře, týkající se aut, pomocí sémantického mapování složí výsledky

Problémy Ruční vytváření prostředníků a mapování je pracné a

drahé Rozpoznání domény vstupu je obtížné Mnoho domén, mnoho jazyků

Nevhodné39

Deep-Web CrawlDva přístupy: Surfacing

Odvození vhodných vstupů pro formulář

Indexování dosažených výsledků

Může využít stávající metody indexování do běžných systémů

40

Deep-Web CrawlTextové vstupy

Dva typy textových vstupů Obecné vyhledávání▪ Přijme všechny řetězce, občas nevrátí nic▪ Pomáhá analýza již naindexovaného okolí formuláře

a iterativní zlepšování analýzou vrácených výsledků „Typovaný“ vstup▪ Přijme pouze prvky své domény, která nemusí být

zřejmá▪ Používá se knihovna často používaných typů (např.

PSČ)▪ Většina těchto vstupů se dá pokrýt malým

množstvím typů41

Deep-Web CrawlKombinace vstupů

select / checkbox prvky jsou „snadné“

Není vhodné zkoušet všechny možnosti Př.: cars.com, 5 selectů = 200M

možností, reálně 650 000 aut

Algoritmus prochází kartézský součin všech možností a hledá kombinace, které generují webové stránky s unikátním obsahem

42

Deep-Web CrawlVýsledky

Několik stovek vstupů pro každý formulář

Počet vstupů je poměrný velikosti databáze, ne počtu prvků vstupu

Výsledky obsahují velké procento Deep-Web databáze, bez jediného lidského zásahu

43

Deep-Web CrawlZpracování výsledků

Při surfacingu se ztrácí struktura databáze (strukturovaná databáze HTML)

Výsledky často v podobě HTML tabulek WebTables, lepší než obyčejná

tabulka (více podobných tabulek, snazší odvozování) Prostor na zlepšení do budoucna

Popisky formulářů metadata44

Existující nástroje IV.TabEx + ProId

45

TabEx + ProIdeÚvod

Yahoo!

Zpracovává tabulky na webu, konkrétně tabulky dvojic (Atribut/Hodnota)

Cíl = trojice (Subjekt / Atribut / Hodnota)46

TabEx

Klasifikace tabulek Tabulky layoutu Tabulky Atribut/Hodnota Ostatní

5000 tabulek ohodnocených experty učení

Pravidla (layout buněk, typ obsahu…)

Přesnost 76%, úplnost 76%47

ProIde

„Protagonist Detection“

Hledání předmětu ke dvojicím atribut-hodnota V tabulce (atribut name) atp. V titulku stránky V odkazech, vedoucích na stránku Nalezení všech n-tic ve stránce

Nejčastější text odkazu 40% přesnost ProIde 65% přesnost

48

Poznatky z výzkumu

49

Zajímavé vedlejší produkty výzkumu Velkou cenu mají kolekce metadat

Názvy sloupců v tabulkách či formulářových prvků, vyskytujících se spolu

Časté hodnoty prvků s daným názvem, tedy doména daného atributu

Názvy sloupců se stejnou doménou (synonyma)

Sémantické služby, poskytující informace o těchto souvislostech, např. hledání synonym

50

Shrnutí

51

ShrnutíCíl: Web-scale knowledge base

TextRunner Zpracovává obecný text Hledá trojice (relace a dva prvky)

WebTables Zpracovává HTML tabulky Hledá relační data

Deep-Web Crawl Zpracovává data, přístupná přes formuláře Hledá relační data

TabEx + ProIde Zpracovává dvousloupcové HTML tabulky Hledá trojice (subjekt / atribut / hodnota)

52

Literatura

The Unreasonable Effectiveness of Data Alon Halevy, Peter Norvig, Fernando Pereira

Web-Scale Extraction of Structured Data Michael J. Cafarella, Jayant Madhavan, Alon Halevy

Web-Scale Knowledge Extraction from Semi-Structured Tables Eric Crestan, Patrick Pantel

53

Konec

54