====== Pojmenované entity ======
{{template>spolecne}}

Pojmenované entity //(named entities)// bývají v počítačovém zpracování přirozeného jazyka definovány různě, ale většinou zahrnují vlastní jména osob, zeměpisné názvy a názvy organizací (včetně zkratek). Mohou být víceslovné.

Pojmenované entity se chovají jinak než normální slova, proto je vhodné umět pojmenované entity v textu rozpoznat. Jedním z možných způsobů, jak to udělat, je Collinsova-Singerova metoda (Collins and Singer, 1999). Spočívá v tom, že na začátku programu předhodíte několik málo ukázek pojmenovaných entit, program se podívá do korpusu na typické okolí těchto vzorků, potom vyhledá další výrazy, které se také vyskytují v podobném okolí, prohlásí je za nové pojmenované entity a celý postup opakuje. Například na začátku řeknete, že //Bill Gates// a //George Bush// jsou osoby, //New York//, //California// a //USA// jsou místa a //IBM// a //Microsoft// jsou organizace. Program se podívá do textu a zjistí, že před jménem osoby se často vyskytují slova jako //Mr//, //president//, //dr// apod. Pak zjistí, že za slovy //Mr//, //president//, //dr// apod. se vyskytují i jiná slova, která by tedy mohla být jmény osob. Tím se mu množina jmen rozroste a nyní rozpozná další "spínače" - slova, která se vyskytují kolem jmen osob a signalizují, že něco je jméno osoby. A tak pořád dokola, až už iterace nepřinesou nic moc nového.

Metodu lze samozřejmě různě upravovat. Můžeme se dívat na 1 až N slov doleva i doprava. Můžeme klást omezení na délku (počet slov) pojmenované entity. Můžeme požadovat, aby slova v pojmenované entitě začínala velkým písmenem (ale pozor, v názvech jako //Hluboká nad Vltavou// jsou některá slova povinně s malým písmenem, zato však tato slova mohou fungovat jako další charakteristický znak zeměpisného názvu). Můžeme také experimentovat s různě sofistikovanými statistickými metodami, které určí, že dané slovo se v daném kontextu vyskytuje "dostatečně" často (nejjednodušší je asi relativní četnost překračující nějaký pokusně stanovený práh).

===== Zadání =====

Napište program v Perlu, kterému předáte jako argument cestu k souboru s korpusem, program tento korpus opakovaně čte a vyhledává spínače a pojmenované entity. Korpus je tokenizovaný text (slova jsou oddělená mezerami nebo konci řádků) v jednom jazyce v UTF-8. Program skončí po takové iteraci, ve které se mu nepodaří najít žádný nový spínač ani pojmenovanou entitu. Na závěr program vypíše přehled všech pojmenovaných entit na standardní výstup. Přehled obsahuje i typ entity (osoba / místo / organizace). V průběhu může vypisovat číslo iterace, počet nalezených entit apod. na STDERR.

Vypište seznam pojmenovaných entit, které v textu najdete po N iteracích (určete typ: osoba, místo, organizace). Vycházejí vám jako pojmenované entity i slova začínající malým písmenem? Je to dobře? Pokud ne, volitelně je zablokujte. Porovnejte výsledky s prostým seznamem slov začínajících velkým písmenem. Snažte se poznat i víceslovné entity.

V prezentaci se zamyslete mj. i nad následujícími otázkami:
  * Jaká je časová a paměťová náročnost celého učení a jedné iterace?
  * Jak moc je tato úloha jazykově závislá? Je jasné, že počáteční vzorek pojmenovaných entit musí odpovídat jazyku, ve kterém je daný korpus. Obsahuje vaše implementace ještě další prvky, které by bylo potřeba změnit, kdybychom totéž chtěli dělat s korpusem v jiném jazyce?

==== Víceslovné entity ====

Volitelně (nebo spíš téměř povinně, ale ve volitelném rozsahu) se pokuste rozpoznat i víceslovné entity. Tady je jedna možnost, jak na to:

  * Dívejte se na nějaké okno N po sobě jdoucích slov, kde N stanovíte pokusně, začněte u 2 a případně ho zvyšujte (ať bude sebevyšší, vždy půjde vymyslet delší entitu, ale to se nedá nic dělat). Pak se podívejte, jestli se příslušná skupina slov vyskytuje v textu opakovaně, alespoň M-krát. Ani tohle není v některých jazycích jednoduché, protože se může vyskytovat v různých pádech, takže zkuste s nějakou váhou započítat i výskyty, kde bude téměř stejná posloupnost slov, akorát u některých z nich se bude lišit koncovka (1 až K koncových znaků; u jazyků odlišných od češtiny se může měnit i jiná část slova). Dostatečně časté skupiny, jejichž první slovo algoritmus prohlásí za entitu, prohlaste za víceslovné entity.
  * Pak by bylo ještě možné si pohrát s jednotlivými slovy ve skupině. Pokud bude skupina končit slovem, které je samo o sobě velmi časté (předložky, spojky), je možné, že skupina vyjde jako přijatelně častá, i když to žádná skupina není. Takže si vytvořte takzvaný //stoplist// - seznam L nejčastějších slov v korpusu, třeba L = 100 až 300, a požadujte, aby skupina takovým slovem nekončila. Obsahovat ho samozřejmě může, dokonce jím asi může i začínat (předložky).
  * Další otázka by byla, jestli se mají nejdřív rozpoznávat jednoslovné entity a pak je uvedeným způsobem rozšiřovat, nebo jestli je lepší nejdřív v textu označit víceslovné výrazy, slepit si je třeba podtržítky, a pak teprve určovat entity.

===== Literatura =====

  * Michael Collins, Yoram Singer: //Unsupervised Models for Named Entity Classification//. In: Proceedings of the EMNLP conference, College Park, MD, USA, 1999

===== Další informace =====

Tento úkol (včetně zadání konkrétního jazyka) si můžete zarezervovat vyplněním formuláře na http://quest.ms.mff.cuni.cz/cgi-bin/zeman/zapoctaky/rezervace_ukolu.pl (pokud ještě není rozebrán).

Pokud se individuálně nedohodneme jinak, termín odevzdání je konec listopadu. Při některé prosincové přednášce program předvedete ostatním.

Součástí zadání bude konkrétní jazyk trénovacích dat (čeština nebo angličtina). Snažte se ale psát program tak, aby přechod na zpracování jiného jazyka byl co nejméně náročný. Není jisté, zda budu mít k dispozici také testovací data (tedy taková, ve kterých už jsou pojmenované entity vyznačené, takže můžeme spočítat, kolikrát jste se trefili). Raději s tím nepočítejte.

{{user:zeman:ukoly:cs.tok.gz|Česká trénovací data}}