Jádro stromu - Tree kernel

v strojové učení, jádra stromů jsou aplikace obecnějšího pojmu kladně definitivní jádro do stromových struktur. Nacházejí aplikace v zpracování přirozeného jazyka, kde je lze použít strojově naučený analýza nebo klasifikace vět.

Motivace

Při zpracování přirozeného jazyka je často nutné porovnávat stromové struktury (např. analyzovat stromy ) pro podobnost. Taková srovnání lze provést výpočtem tečkované výrobky vektorů vlastností stromů, ale tyto vektory mají tendenci být velmi velké: techniky NLP dospěly do bodu, kdy je jednoduchý závislostní vztah přes dvě slova zakódován vektorem několika milionů funkcí.[1] Může být nepraktické představovat složité struktury, jako jsou stromy, s vektory funkcí. Dobře navržená jádra umožňují výpočetní podobnost nad stromy bez výslovného výpočtu vektorů funkcí těchto stromů. Navíc, metody jádra byly široce používány v úlohách strojového učení (např. SVM ), a tak spousta algoritmů nativně pracuje s jádry nebo má rozšíření, které zpracovává kernelizace.

Příkladem aplikace je klasifikace vět, například různých typů otázek.[2]

Příklady

Volební obvod analyzuje strom pro větu: „Kočka jí myš.“
Totéž jako výše, pro větu: „Myš jí kočku.“

Zde jsou uvedeny dva příklady jádra stromů aplikované na stromy volebních obvodů vět „Kočka jí myš.“ a „Myš jí kočku.“. V tomto příkladu jsou „A“ a „a“ stejná slova a ve většině aplikací NLP by byla reprezentována stejným tokenem.

Zájmem těchto dvou jader je to, že vykazují velmi odlišnou zrnitost (jádro stromu podmnožiny je mnohem jemnější než jádro podstromu) pro stejnou výpočetní složitost. Oba lze vypočítat rekurzivně v čase O (| T1|. | T2|).[3]

Jádro podstromu

V případě stromu volebních obvodů je podstrom definován jako uzel a všechny jeho podřízené prvky (např. [NP [D [A]] [N [myš]]] je podstrom dvou stromů). Terminály nejsou považovány za podstrom (např. [A] není podstrom). Jádro podstromu spočítá počet běžných podstromů mezi dvěma danými stromy.

V tomto příkladu existuje sedm běžných podstromů:

[NP [D [a]] [N [kat]]],
[NP [D [a]] [N [myš]]],
[N [myš]],
[N [kočka]],
[V [jí]],
[D [a]] (započítáno dvakrát, protože se objeví dvakrát).

Jádro stromu podmnožiny

Strom podmnožiny je obecnější strukturou než podstrom. Základní definice je stejná, ale v případě stromů podmnožiny nemusí být listy terminály (např. [VP [V] [NP]] je strom podmnožiny obou stromů), ale i zde se jednotlivé uzly nepovažují za stromy. Kvůli této obecnější definici existuje více stromů podmnožiny než podstromů a častější stromy podmnožiny než běžné podstromy.

V tomto příkladu existuje 54 běžných stromů podmnožiny. Sedm společných podstromů a mimo jiné:

[NP [D] [N]] (počítáno dvakrát),
[VP [V [jí]] [NP]] ...

Viz také

Poznámky

  1. ^ McDonald, Ryan; Pereira, Fernando; Ribarov, Kiril; Hajič, Jan (2005). Neprojektivní analýza závislostí pomocí algoritmů Spanning Tree. HLT – EMNLP.
  2. ^ Zhang, Dell; Lee, Wee Sun (2003). Klasifikace otázek pomocí podpůrných vektorových strojů. SIGIR.
  3. ^ Collins, Michael; Duffy, Nigel (2001). Konvoluční jádra pro přirozený jazyk. Pokroky v systémech zpracování neurálních informací.

Reference

  • Jun Sun, Min Zhang a Chew Lim Tan. Jádro stromové sekvence pro přirozený jazyk
  • Alessandro Moschitti. Zajištění praktičnosti jader stromu pro studium přirozeného jazyka

externí odkazy