Dlaczego n-gram jest używany do identyfikacji języka tekstowego zamiast słów?

W dwóch popularnych bibliotekach identyfikacji języka, Compact Language Detector 2 dla C ++ i wykrywaczu języka dla java, oba wykorzystały (oparte na znakach) n-gramach do wyodrębnienia funkcji tekstowych. Dlaczego nie używa się worka słów (pojedyncze słowo / słownik) i jakie są zalety i wady worka słów i n-gramów?

Jakie są inne zastosowania modelu n-gramów w klasyfikacji tekstu?

Ojej. Wygląda na to, że istnieje podobne pytanie: w odniesieniu do używania modelu Bigram (N-gram) do budowy wektora cech dla dokumentu tekstowego

Ale czy ktoś może dać bardziej kompleksową odpowiedź? Co jest lepsze w przypadku identyfikacji języka?

(Mam nadzieję, że poprawnie zrozumiałem znaczenie n-gramów i worków słów, haha, jeśli nie, pomóż mi z tym.)

— dennis97519
źródło

Odpowiedzi:

Myślę, że najbardziej szczegółowe odpowiedzi można znaleźć w obszernej pracy Mehryara Mohri na ten temat. Oto link do jednego z jego slajdów na ten temat: http://www.cims.nyu.edu/~mohri/amls/lecture_3.pdf

Problem wykrywania języka polega na tym, że ludzki język (słowa) mają strukturę. Na przykład w języku angielskim bardzo często litera „u” podąża za literą „q”, podczas gdy nie jest tak w przypadku transliterowanego języka arabskiego. n-gram działa poprzez uchwycenie tej struktury. Dlatego niektóre kombinacje liter są bardziej prawdopodobne w niektórych językach niż w innych. Jest to podstawa klasyfikacji n-gramowej.

Z drugiej strony, zbiór słów zależy od przeszukiwania dużego słownika i zasadniczo dopasowania szablonów. Istnieją dwie główne wady: 1) każdy język musiałby mieć obszerny słownik słów w pliku, którego przeszukanie zajęłoby stosunkowo dużo czasu, i 2) worek słów nie zawiódłby się, jeśli żadne z nich w zestaw treningowy jest zawarty w zestawie testowym.

Zakładając, że używasz bigramów (n = 2) i masz 26 liter w twoim alfabecie, wtedy jest tylko 26 ^ 2 = 676 możliwych bigramów dla tego alfabetu, z których wiele nigdy nie nastąpi. Dlatego „profil” (do użycia słów detektora języka) dla każdego języka wymaga bardzo małej bazy danych. Z drugiej strony klasyfikator typu bag-of-words potrzebowałby pełnego słownika dla KAŻDEGO języka, aby zagwarantować wykrycie języka na podstawie dowolnego podanego zdania.

Krótko mówiąc - każdy profil językowy można szybko wygenerować przy stosunkowo niewielkiej przestrzeni funkcji. Co ciekawe, n-gramy działają tylko dlatego, że litery nie są rysowane w jednym języku - jest to wyraźnie efekt dźwigni.

Uwaga: ogólne równanie liczby n-gramów dla słów to l ^ n, gdzie l jest liczbą liter alfabetu.

— justanotherbrain
źródło

Wydaje mi się, że w przypadku niektórych bliskich języków pomocne byłoby używanie list słów oprócz n-gramów. Czasami widziałem tekst norweski sklasyfikowany jako duński. Wątpię, aby n-gram był dobrym sposobem na rozróżnienie tych dwóch języków.

— kjetil b halvorsen

Dziękuję za szczegółową odpowiedź. Mam jednak kilka pytań na ten temat. Po pierwsze, czy mógłbyś wyjaśnić, że „worek słów nie powiedzie się, jeśli żadne ze słów z zestawu treningowego nie będzie zawarte w zestawie testowym”? a po drugie, dlaczego CLD2 używa 4 gramów, co da 456976 wpisów dla języka angielskiego, gdy użycie metody słownikowej może przynieść około połowę rozmiaru profilu ( oxforddictionaries.com/words/... )?

— dennis97519,

@ dennis97519 re: „bag-of-words ...” Załóżmy, że twój słownik zawiera tylko słowa {„pies”, „kot”, „żółw”, „zwierzę”} w języku angielskim i {„perro”, „gato” , „tortuga”, „animal”} w języku hiszpańskim. Twój słownik nie byłby w stanie sklasyfikować następującego zdania: „Osioł jest zwierzęciem”, ponieważ słowo „zwierzę” występuje w obu słownikach, ale żadne inne słowo nie istnieje. To jest skrajny przykład. Re 4-gramy: 1) Pamiętaj, że potrzebujesz słownika dla każdego języka, 2) n-gramy wydają się być rzadkie (szybsze wyszukiwanie) i 3), jak powiedział Dougal, można je przedstawić w zaledwie kilku bajtach.

— justanotherbrain

@loretoparisi - Istnieją dwa kompromisy: pierwszy to między złożonością modelu (duży N = bardziej złożony) a błędem uogólnienia (jak dobrze sobie radzisz na jakimś zestawie testowym) - nie chcesz się przeciążać. Drugim kompromisem jest złożoność obliczeniowa. Złożoność pamięci rośnie wykładniczo wraz z N. Trening jest zazwyczaj liniowy z liczbą słów w tekście, więc posiadanie bardzo długiego tekstu zwykle nie stanowi problemu. To powiedziawszy, duży tekst często oznacza więcej słów w słowniku D. Zatem znowu złożoność pamięci wynosi O (D ^ N). W praktyce zwykle najlepiej jest używać tak dużej liczby N, jak to możliwe obliczeniowo.

— justanotherbrain

@loretoparisi - W związku z tym, jak wspomniano wcześniej, N-gramy wydają się być rzadkie, ale nie zawsze jest to prawdą. Jeśli jest on rzadki dla konkretnego tekstu, sprawdzanie poprawności z innym N jest najlepszym podejściem do znalezienia optymalnego N (ponownie, z ograniczeniami obliczeniowymi).

— justanotherbrain

Litery N-gram są używane zamiast słów z kilku powodów:

1) Lista słów potrzebnych w danym języku jest dość duża, być może 100 000, jeśli weźmiesz pod uwagę szybkie, szybsze, najszybsze, szybkie, szybkie, szybkie, ... jak wszystkie inne słowa. W przypadku 80 języków potrzebujesz około 80 razy więcej słów, zajmując dużo miejsca - ponad 50 megabajtów.

2) Liczba trygramów literowych dla 26-literowego alfabetu wynosi 26 ** 3 lub około 17 000, a dla kwadratowych (N = 4) około 450 000 dla WSZYSTKICH języków używających tego alfabetu. Podobne, ale nieco większe liczby dla N-gramów w większych alfabetach o długości 30-100 znaków. W przypadku języków CJK z ponad 4000 liter w skrypcie Han, unigramy (N = 1) są wystarczające. W przypadku niektórych skryptów Unicode jest tylko jeden język na skrypt (grecki, ormiański), więc nie są potrzebne kombinacje liter (tak zwane nil-gram N = 0)

3) W przypadku słów nie ma żadnych informacji, gdy podano słowo spoza słownika, natomiast w przypadku liter N-gram często występuje co najmniej kilka przydatnych kombinacji liter w tym słowie.

CLD2 używa quadgramów dla większości skryptów Unicode (alfabetów), w tym łacińskiego, cyrylicy i arabskiego, unigramów dla skryptów CJK, nilgramów dla innych skryptów, a także zawiera ograniczoną liczbę dość charakterystycznych i dość powszechnych pełnych słów i par słów do rozróżnienia w trudnych grupach statystycznie podobnych języków, takich jak indonezyjski i malajski. Bigramy literowe i trygramy są prawdopodobnie przydatne do rozróżnienia niewielkiej liczby języków (około ośmiu, patrz https://docs.google.com/document/d/1NtErs467Ub4yklEfK0C9AYef06G_1_9NHL5dPuKIH7k/edit), ale są bezużyteczne do rozróżnienia dziesiątek języków. Tak więc CLD2 wykorzystuje kwadramy, wiążąc z każdą kombinacją liter trzy najpopularniejsze języki używające tej kombinacji. Pozwala to na obsługę 80 języków z około 1,5 MB tabel i 160 języków bardziej szczegółowo z około 5 MB tabel.

— Witryny Dick
źródło