Dizertační práce: Unsupervised Classification with Wikipedia and WordNet

Dizertační práce se věnuje problému klasifikace entit reprezentovaných jmennými frázemi v textu. Cílem je vyvinout metodu pro automatizovanou klasifikaci těchto entit v datasetech skládajících se z krátkých textových fragmentů. Důraz je kladen na metody učení bez učitele, nebo kombinaci učení s učitelem a bez učitele (angl. semi-supervised learning), přičemž nebudou vyžadovány trénovací příklady. Třídy jsou buď automaticky stanoveny, nebo zadány uživatelem.

Motivační problém

Téma práce bylo inspirováno využitím textových popisků, které se často připojují k fotografiím, pro zpřesnění výsledku klasifikátorů obrazu. Moderní klasifikační algoritmy rozpoznávají v rámci jednoho obrazu vícero objektů a následně jim přiřazují cílové třídy. Protože textový popisek obsahuje velmi často zkondenzovanou informaci o tom, co na obrázku je, může být výsledek analýzy popisku použit jako dodatečná informace při klasifikaci objektů na obrázku.

Výzkumnou výzvou je překlenutí "sémantické propasti" mezi často velmi konkrétním názvem objektu v textovém popisku (např. konkrétní jméno osoby nebo stavby) a relativně obecnou cílovou třídou klasifikátoru obrazu (např. "stavba").

Existující přístupy

Dizertační práce se zaměřila na problém identifkace entit (vlastně zmínek objektů) ve vstupním textu, a jejich následnou klasifikaci do seznamu předem definovaných tříd. Hlavní výzkumný problém představovalo to, že seznam tříd není pevně daný, ale je dán algoritmem pro klasifikaci obrazu. Z tohoto důvodu nebylo možné použít zavedené metody z oblasti zpracování přirozeného jazyka, které předpokládají existenci rozsáhlého korpusu s trénovacími daty. Klasifikací objektů (tzv. entit) se zabývají přístupy z oblasti "Named Entity Recognition", v době vzniku dizertační práce tyto algoritmy až na výjimky klasifikovaly entity do úzkého okruhu předem definovaných tříd (typicky Person, Organization, Location, Miscellaneous).

Navržené algoritmy

Jako první pokus pro řešení problému klasifikace entit byl navržen Sémantického Mapování Konceptů (angl. Semantic Concept Mapping - SCM). Tento algoritmus mapuje jmenné fráze i cílové třídy na koncepty thesauru WordNet. Grafové míry podobnosti pro WordNet jsou použity pro přiřazení nejbližší třídy k dané jmenné frázi. Pokud jmenná fráze není namapována na žádný koncept, potom je použit algoritmus Cíleného Objevování Hyperonym (angl. Targeted Hypernym Discovery - THD). Tento algoritmus extrahuje s pomocí lexiko-syntaktických vzorů hyperonymum z článku na Wikipedii, který danou jmennou frázi definuje. Toto hyperonymum je použito k namapování jmenné fráze na koncept ve WordNetu. Hyperonymum může být samo o sobě také považováno za výsledek klasifikace. V takovém případě je dosaženo klasifikace bez učitele.

Algoritmy SCM a THD byly navrženy pro angličtinu. I když je možné oba algoritmy přizpůsobit i pro jiné jazyky, byl v rámci dizertační práce vyvinut algoritmus Pytel článků (angl. Bag of Articles - BOA), který je jazykově agnostický, protože je založen na statistickém Rocchio klasifikátoru. Díky zapojení Wikipedie jako zdroje informací pro klasifikaci nevyžaduje BOA trénovací data. WordNet je využit novým způsobem, a to pro výpočet vah slov, jako pozitivní seznam slov a pro lematizaci. Byl také navržen desambiguační algoritmus pracující s globálním kontextem. Algoritmus BOA lze považovat za hlavní přínos dizertace.

Experimentální výsledky

Experimentální hodnocení navržených algoritmů je provedeno na datasetu WordSim353 používaném pro hodnocení systémů pro výpočet podobnosti slov (angl. Word Similarity Computation - WSC), a na datasetu Český cestovatel. Tento dataset byl vytvořen speciálně pro účel našeho výzkumu a je tvořen popiskami připojeným k fotografiím českého cestovatele a fotografa Juraje Kamana.

Na datasetu WordSim353 dosahuje BOA Spearmanova korelačního koeficientu 0.72 s lidským hodnocením. Tento výsledek je blízko hodnotě 0.75 dosažené algoritmem Explicit Semantic Analysis (ESA), který je podle znalosti autora nejlepším algoritmem pro daný dataset nevyžadujícím trénovací data. Algoritmus BOA je ale méně náročný na předzpracování Wikipedie než ESA.

Algoritmus SCM nedosahuje dobrých výsledků na datasetu WordSim353, ale naopak předčí BOA na datasetu Český cestovatel, který byl navržen speciálně pro úlohu klasifikace entit. Tato nesrovnalost vyžaduje další výzkum. V samostatném hodnocení THD na malém počtu pojmenovaných entit z datasetu Český cestovatel bylo správné hyperonymum nalezeno v 62% případů.

Další využití navržených algoritmů

Výstupy dizertační práce jsou využívány v rámci evropského aplikačně-výzkumného projektu LinkedTV (www.linkedtv.eu).

Webová aplikace pro klasifikaci entit

V návaznosti na dizertační práci byly navržené algoritmy použity ve spolupráci s Ing. Dojchinovským (FIT ČVUT) pro zkonstruování webové aplikace a webové služby pro identifikaci a klasifikaci entit dostupné na adrese ner.vse.cz/thd.

Tato webová služba nabízí přesnější třídy než již známé existující systémy jako DBpedia Spotlight nebo OpenCalais. První předběžné porovnání s těmito sytémy provedené na datasetu Český cestovatel ukazuje i lepší klasifikační výsledky. S ohledem na malý rozsah datasetu Český cestovatel (143 entit s inter-annotator agreement) a jeho specifičnost je potřeba provést další experimenty.

Systém je aktuálně dostupný pro angličtinu, němčinu a holandštinu. Plánuje se podpora pro češtinu.

Rozšíření báze znalostí DBpedia o miliony nových typů

Druhým dosaženým výsledkem je využití navržených algoritmů k rozšíření jedné z největších světových bází znalostí DBpedia. Tato báze znalostí je generována z Wikipedia primárně na základě analýzy polostrukturovaných dat (tzv. infoboxů) obsažených v článcích. Pomocí algoritmu THD byla provedena analýza přímo volného textu článků, což umožnilo přiřadit nový typ více jak jednomu miliónu entit v anglické DBpedii a cca 800.000 entit v německé DBpedii. Stovky tisíc z těchto entit přitom neměly ještě žádný typ z DBpedia ontology přiřazen. Porovnání duplicit s ontologií yago ještě nebylo provedeno, po odstranění duplicit vůči této ontologii se počty nově objevených typů sníží.

Například DBpedia obsahuje entitu "Tractor beam", ale není k ní přiřazený typ. Nově vzniklý dataset k ní přiřazuje typ "Device" (http://dbpedia.org/ontology/Device).

Dataset je dostupný na adrese ner.vse.cz/datasets/