Hnědé shlukování - Brown clustering

Hnědé shlukování je těžké hierarchické aglomerativní shlukování problém založený na distribučních informacích navržených Peterem Brownem, Williamem A. Brownem, Vincentem Della Pietrou, Peter V. de Souza, Jennifer Lai a Robert Mercer.[1] Obvykle se používá na text a seskupuje slova do shluků, o nichž se předpokládá, že jsou sémanticky příbuzné na základě toho, že jsou vloženy do podobných kontextů.

Úvod

v zpracování přirozeného jazyka, Hnědé shlukování[2] nebo Klastrování IBM[3] je forma hierarchické shlukování slov založených na kontextech, ve kterých se vyskytují, navrhl Peter Brown, William A. Brown, Vincent Della Pietra, Peter de Souza, Jennifer Lai a Robert Mercer z IBM v kontextu jazykové modelování.[1] Intuice za touto metodou spočívá v tom, že a třídní jazykový model (také zvaný shluk n-gramový model[3]), tj. ten, kde pravděpodobnosti slov vycházejí z tříd (shluků) předchozích slov, se používá k řešení datová sparita problém vlastní jazykovému modelování.

Jurafsky a Martin uvádějí příklad a systém rezervace letů to potřebuje odhadnout pravděpodobnost bigramu „do Šanghaje“, aniž by to viděli na tréninkovém setu.[3] Systém může získat dobrý odhad, pokud dokáže seskupit „Šanghaj“ s jinými názvy měst, a poté provést odhad na základě pravděpodobnosti frází jako „do Londýna“, „do Pekingu“ a „do Denveru“.

Technická definice

Hnědé skupiny položek (tj. typy ) do tříd pomocí kritéria binárního sloučení založeného na log-pravděpodobnost textu podle třídního jazykového modelu, tj. modelu pravděpodobnosti, který zohledňuje shlukování. Tedy průměr vzájemné informace (AMI) je optimalizační funkce a sloučení se volí tak, aby v globálním měřítku způsobily nejmenší ztrátu vzájemné informace.

Ve výsledku lze výstup považovat nejen za a binární strom ale možná mnohem užitečněji jako posloupnost sloučení, zakončená jednou velkou třídou všech slov. Tento model má stejnou obecnou formu jako a skrytý Markovův model, sníženo na pravděpodobnosti bigramu v Brownově řešení problému. MI je definována jako:

Nalezení shlukování, které maximalizuje pravděpodobnost dat, je výpočetně nákladné. Přístup navržený Brownem a kol. je chamtivý heurista.

Práce také navrhuje použití Brownových shluků jako zjednodušujícího jazykového modelu založeného na třídě bigram. Vzhledem k ukazatelům členství v klastru Ci pro žetony wi v textu pravděpodobnost slova instance wi dané předchozí slovo wi-1 darováno:[3]

To bylo kritizováno[Citace je zapotřebí ] jako omezená užitečnost, protože vždy předpovídá nejběžnější slovo v jakékoli třídě, a proto je omezena na | c | typy slov; to se odráží v nízkém relativním snížení rozpaků zjištěném při použití tohoto modelu a Browna.

Variace

Další práce zkoumaly trigramy v jejich přístupech k problému Brownova shlukování.[4]

Hnědé shlukování, jak je navrženo, generuje pevný počet výstupních tříd. Je důležité zvolit správný počet tříd, který je závislý na úkolu.[5] Členství v klastrech slov vyplývající z Brownova shlukování lze použít jako funkce v řadě strojově naučený úkoly zpracování přirozeného jazyka.[2]

Zobecnění algoritmu bylo zveřejněno na konferenci AAAI v roce 2016, včetně stručné formální definice verze z roku 1992 a poté také obecné formy.[6] Jádrem k tomu je koncept, že třídy uvažované pro sloučení nemusí nutně představovat konečný počet výstupů tříd a že změna počtu tříd uvažovaných pro sloučení přímo ovlivňuje rychlost a kvalitu konečného výsledku.

O chamtivé heuristice navržené Brownem et al. Nejsou známy žádné teoretické záruky. (od února 2018). Problém shlukování však lze formovat jako odhad parametrů základního jazykového modelu založeného na třídě: pro tento model je možné za mírných předpokladů vyvinout konzistentní odhad.[7]

Viz také

Reference

  1. ^ A b Peter F. Brown; Peter V. de Souza; Robert L. Mercer; Vincent J. Della Pietra; Jenifer C. Lai (1992). "Třída n-gramové modely přirozeného jazyka " (PDF). Výpočetní lingvistika. 18 (4).
  2. ^ A b Joseph Turian; Lev Ratinov; Yoshua Bengio (2010). Reprezentace slov: jednoduchá a obecná metoda pro učení pod dohledem (PDF). Sborník ze 48. výročního zasedání Asociace pro počítačovou lingvistiku.
  3. ^ A b C d Daniel Jurafsky; James H. Martin (2009). Zpracování řeči a jazyka. Pearson Education International. str. 145–146.
  4. ^ Sven Martin; Jorg Liermann; Hermann Ney (1999). "Algoritmy pro shlukování slov bigram a trigram". Řečová komunikace. 24 (1): 19–37. CiteSeerX  10.1.1.53.2354. doi:10.1016 / S0167-6393 (97) 00062-9.
  5. ^ Leon Derczynski; Sean Chester; Kenneth S. Bogh (2015). Nalaďte si hnědé shlukování, prosím (PDF). Sborník z konference o posledních pokrokech ve zpracování přirozeného jazyka.
  6. ^ Leon Derczynski; Sean Chester (2016). Zobecněné generování hnědých klastrů a souhrnných funkcí. Sborník příspěvků z třicáté konference AAAI o umělé inteligenci.
  7. ^ Karl Stratos; Do-kyum Kim; Michael Collins; Daniel Hsu (2014). Spektrální algoritmus pro výuku n-gramových modelů přirozeného jazyka založených na třídách (PDF). Sborník z 30. konference o nejistotě v umělé inteligenci.

externí odkazy