ML: N-грами
Вступ
Цей документ є продовженням обговорення імовірнісних методів у машинному навчанні. Ми розглянемо класичний і такий, що не втратив свого значення, метод n-грам для прогнозування послідовностей. Як приклад таких послідовностей будуть розглянуті букви і слова текстів природною мовою. Однак, цей же підхід з невеликими модифікаціями можна використовувати при аналізі часових рядів і в інших задачах.
Наведені далі приклади на Python використовують бібліотеку nltk (Natural Language Toolkit) і можуть бути знайдені у файлі ML_NGrams.ipynb. Розглянутий також суттєво швидший модуль my_ngrams.py, заснований на деревоподібному представленні n-грам.
nltk: Словник
Нехай проведена токенізація послідовності (вона розбита на елементарні символи). Як токени можуть виступати букви, слова природної мови або номери інтервалів зміни дійсної величини (при аналізі часових рядів). Щоб створити словник усіх можливих токенів, у nltk їхній список text передається екземпляру класу Vocabulary:
from nltk.lm import Vocabulary text = ['a', 'b', 'r', 'a', 'c', 'a', 'd', 'a', 'b', 'r', 'a'] vocab = Vocabulary(text, unk_cutoff=2)Клас Vocabulary є надбудовою над стандартним класом Counter(), екземпляр якого знаходиться в vocab.counts. Він складає частотний словник. Параметр unk_cutoff задає поріг для рідкісних слів. Якщо слово в списку зустрічається менше unk_cutoff разів, то воно замінюється на службове слово '<UNK>' (невідоме).
Словник пам'ятає всі токени (vocab[t] повертає число появ токена t у списку).
При цьому конструкція
t in vocab повертає True тільки для токенів
з частотою вищою або рівною порогу unk_cutoff:
print(vocab['a'], 'a' in vocab) # 5 True зустрівся 5 разів, потрапив у словник print(vocab['c'], 'c' in vocab) # 1 False не потрапив у словник (1 < unk_cutoff=2) print(vocab['Z'], 'Z' in vocab) # 0 False такого взагалі не булоТекст для словника можна додавати довільне число разів:
vocab.update(['c', 'c']) # додали слів print(vocab['c'], 'c' in vocab) # 3 True перевищує поріг cutoffІнформацію про словник, список слів (включно з <UNK>) і список токенів без урахування порогу, можна отримати таким чином:
print(vocab) # Vocabulary cutoff=2 unk_label='<UNK>' and 5 items
len(vocab) # 5 число слів включаючи токен '<UNK>'
sorted(vocab) # ['<UNK>', 'a', 'b', 'c', 'r'] що вважає словником
sorted(vocab.counts) # ['a', 'b', 'c', 'd', 'r'] все, що отримав
[ (v, vocab[v]) for v in vocab] # [('a',5), ('b',2), ('r',2), ('c',3), ('<UNK>',2)]
За допомогою методу lookup у будь-якому списку (включно з вкладеними списками)
можна перевірити слова на наявність їх у словнику і незнайомі (або рідкісні) замінити на '<UNK>'
vocab.lookup('a') # 'a'
vocab.lookup(['a', 'aliens']) # ('a', '<UNK>')
vocab.lookup(['a', 'b', ['Z', 'b']]) # ('a', 'b', ('<UNK>', 'b'))
nltk: N-грами
Послідовність n токенів у тексті називається n-грамою. У nltk функція ngrams повертає генератор на список усіх n-грам. Для випадку n=2 служить функція bigrams. Так, для списку цілих чисел [1...5] отримаємо всі 3-грами і 2-грами:
from nltk.util import ngrams, bigrams list( ngrams ([1,2,3,4,5], 3) ) # [(1, 2, 3), (2, 3, 4), (3, 4, 5)] list( bigrams([1,2,3,4,5]) ) # [(1, 2), (2, 3), (3, 4), (4, 5)]Підкреслимо, що функції повертають генератори. Тому, якщо написати bg = bigrams([1,2,3,4,5]), а потім двічі викликати list(bg), то другий виклик поверне порожній список (генератор відпрацює в першому виклику).
При обробці природної мови, тексти розбиваються на речення. У nltk прийнято оточувати речення токенами <s> ...</s>. Для виконання цієї процедури існує набір функцій препроцесингу. Вони також повертають генератори, тому є "одноразовими":
from nltk.lm.preprocessing import pad_both_ends, padded_everygram_pipeline list( pad_both_ends(['a','b'], n=2) ) ) # ['<s>', 'a', 'b', '</s>'] list( pad_both_ends(['a','b'], n=3) ) ) # ['<s>', '<s>', 'a', 'b', '</s>', '</s>']Параметр n вказує для яких n-грам "потрібне" таке "забивання":
list( bigrams( pad_both_ends(['a','b'], n=2) ) ) # [('<s>','a'), ('a','b'), ('b','</s>')]
Використовувати значення n > 2 або взагалі відмовитися від падінгу (n=1) залежить від конкретної задачі.
За допомогою функції padded_everygram_pipeline можна підготувати список речень для роботи з n-грамами:
sents = [['a', 'b'], ['b', 'a'] ] # 2 "речення" train, vocab = padded_everygram_pipeline(2, sents) print( list(vocab) ) # ['<s>', 'a', 'b', '</s>', '<s>', 'b', 'a', '</s>']Залежно від задачі, "речення" можуть бути як реальними реченнями тексту, так і окремими документами. Слід пам'ятати, що при обчисленні умовних ймовірностей (див. нижче) n-грами будуть складатися всередині кожного "речення" без їхнього перетину між "реченнями".
Сенс використання забивок полягає в можливості отримання ймовірності першого, другого і т.д. слова в реченні. Наприклад для триграм, якщо "<s> <s> мама мыла раму </s> </s>", то ймовірність першого слова дорівнює P(<s> <s> => мама).
Зазначимо також, що, як і раніше, padded_everygram_pipeline повертає "одноразові" генератори, тому на практиці вони одразу передаються в наступну ланку обробки тексту. Крім цього, перший аргумент padded_everygram_pipeline повинен, незалежно від падінгу, дорівнювати числу n-грам, інакше буде отримано невірний генератор train.
nltk: Умовні ймовірності
Нагадаємо, що імовірнісна мовна модель для даного слова $w$, за його контекстом $\{\mathcal{T} - w\}$ (текст $\mathcal{T}$ без слова $w$) передбачає ймовірність цього слова: $P(w|\mathcal{T} - w)$. Зазвичай, як контекст використовуються слова, що йдуть перед $w$. Якщо відома умовна ймовірність $ P( w_n\,|\, w_1...w_{n-1})\equiv P(w_1...w_{n-1}\Rightarrow w_n)$ того, що після ланцюжка слів (токенів) $w_1...w_{n-1}$ йде слово $w_n$, то вибравши найбільшу ймовірність, можна передбачити це слово. Оцінка таких умовних ймовірностей проводиться за допомогою частотного аналізу появи в тексті n-грам $(w_1,...,w_{n})$.
Відповідні підрахунки в nltk здійснюються сімейством мовних моделей. Розглянемо спочатку клас MLE (Maximum Likelihood Estimator):
from nltk.lm import MLE sents = [['a','b','c'], ['b', 'a'] ] # 2 "речення" train, vocab = padded_everygram_pipeline(n, sents) n = 2 lm = MLE(n) # працюємо з біграмами lm.fit(train, vocab) # навчаємося (рахуємо ймовірності)Генератор vocab містить весь текст з об'єднаними реченнями (оточеними символами <s>, </s>). Він використовується для складання словника. У train знаходиться генератори n-грам для кожного речення. Складання n-грам проводиться окремо для кожного речення. Тому, незалежно від наявності забивок <s>, </s>, n-грами для 1,2,...,n між реченнями не перетинаються.
Оскільки для великих текстів функція fit працює достатньо повільно, бажано виводити процес її роботи. Наприклад, нехай є одне речення зі списку слів: words і нас цікавлять ймовірності n-грам (для n=1,...,n). Тоді модель можна навчити таким чином:
lm = MLE(n)
lm.fit( [ ngrams(words,1) ], words) # юніграми і словник
for i in range(2, n+1):
lm.fit( [ ngrams(words, i) ] ) # наступні n-грами
print(f"n:{i:2d}> ngrams:{lm.counts.N():10d}")
Після навчання (метод fit) можна вивести число запам'ятованих n-грам і словник (попередній приклад):
print(lm.counts.N()) # 16 число n-грам, n=1,2 print(sorted(lm.vocab) ) # ['</s>', '<UNK>', '<s>', 'a', 'b', 'c']Число появ у тексті і ймовірність одиничного символу повертає об'єкт counts і метод score:
print(lm.counts['a'], lm.score('a')) # 2 0.222 = 2/9 (з урахуванням символів '</s>''<s>')
Число 2-грам і умовну ймовірність P(a => b)
отримуємо так:
print(lm.counts[['a']]['b'], lm.score('b', ['a'])) # 1 0.5
Дійсно, в тексті є дві біграми, що починаються з 'a':
('a','b') і ('a','</s>'), де друга - в кінці другого речення.
Тому P(a => b) = 1/2.
У загальному випадку, якщо contex=$[w_1,...,w_{n-1}]$,
то число n-грам дорівнює lm.counts[context][$w_n$],
а умовна ймовірність $P(w_1...w_{n-1}\Rightarrow w_n)$ дорівнює
lm.score($w_n$, context).
nltk: Ентропія і перплексія
Знаючи умовні ймовірності, можна обчислити перплексію тестового тексту, який необхідно попередньо розбити на n-грами:
test = [('a', 'b'), ('b', 'a'), ('a', 'b')]
print("e=", lm.entropy(test) ) # 1.0
print("p=", lm.perplexity(test), 2**lm.entropy(test) ) # 2.0 2.0
print( [ lm.score(b[-1], b[:-1] ) for b in test] ) # [0.5, 0.5, 0.5]
Ентропія $H$ (з логарифмом за основою 2), а потім перплексія $\mathcal=2^H$
обчислюється таким чином:
sum( [ -lm.logscore(ng[-1], ng[:-1]) for ng in test] )/len(test)де lm.logscore дорівнює двійковому логарифму від lm.score.
Проблеми великих словників
Якщо в марковських моделях мови, як елементарні символи виступають слова, то розмір словника стає дуже великим. Це призводить до таких проблем:
- Словник природної мови відкритий і при тестуванні моделі можуть з'являтися слова, яких не було в навчальному корпусі (проблема OOV - out of vocabulary).
- Число умовних ймовірностей достатньо швидко зростає і вимагає помітних витрат пам'яті.
Так, число унікальних (1...10)-грам російських букв на тексті довжиною 6'678'346
букв дорівнює:
[33, 898, 10'651, 68'794, 278'183, 794'837, 1'633'700, 2'609'627, 3'540'927, 4'338'087].
Чим довший навчальний текст, тим більше буде потрібно пам'яті. - Більшість слів у словнику мають малу ймовірність (закон Ципфа) і для обчислення умовних ймовірностей з їхньою участю, необхідні дуже великі корпуси текстів. У будь-якому випадку, деякі n-грами, з тестового корпусу виявляться відсутніми в тренувальному. Відповідні їм умовні ймовірності будуть дорівнювати нулю.
З проблемою OOV можна боротися таким чином. Рідкісні слова в навчальному корпусі одразу замінюються на одне слово UNK (unknown). Відповідно, умовні ймовірності будуть містити це службове слово і більш-менш справлятися з незнайомими словами (також замінюваними на UNK) при тестуванні моделі. Наведемо приклад:
sents = [['a', 'b', 'c'], ['b', 'a'] ] # 2 "речення"
vocab = Vocabulary(unk_cutoff=2)
for s in sents:
vocab.update(s)
sents = vocab.lookup(sents) # (('a', 'b', '<UNK>'), ('b', 'a'))
train, vocab = padded_everygram_pipeline(2, sents)
lm = MLE(2)
lm.fit(train, vocab)
print( lm.score('<UNK>')) # 0.11111 = 1/9
print( lm.score('<UNK>', ['b'] ) ) # 0.5 = P(b => <UNK>)
Поява нульових ймовірностей, що не дозволяють обчислити ентропію і перплексію,
розглянемо на такому тренувальному корпусі:
('a', 'b', 'c', 'b', 'a').
Біграми ('a','c') в цьому корпусі немає.
Якщо вважати, що P('a' => 'c') = 0, то при тестуванні отримаємо нульову
ймовірність і нескінченні ентропію і перплексію:
test = [('a', 'b'), ('a', 'c')]
print(lm.score('c', ['a'])) # 0.0 P( a => c)
print(lm.entropy(test) ) # inf
Взагалі, якщо оцінювати умовну ймовірність за формулою:
$$
P(w_1...w_{n-1}\Rightarrow w_n) = \frac{N(w_1...w_n)}{N(w_1...w_{n-1})},
$$
то для довгих n-грам нулю може дорівнювати, як чисельник $N(w_1...w_n)$,
так і знаменник $N(w_1...w_{n-1})$.
Крім цього, при малих значеннях $N(w_1...w_{n-1})$ оцінка емпіричної умовної
ймовірності стає дуже ненадійною.
Згладжування, відкат і інтерполяція
Проблему нульових умовних ймовірностей можна вирішувати різними способами. Найпростіший і грубий - це зробити нульові ймовірності маленькими, але ненульовими. Для цього використовують згладжування Lidstone, окремий випадок якого ($\gamma=1$) називається згладжуванням Лапласа $$ \tilde{P}(w_1,...,w_{n-1}\Rightarrow w_n) = \frac{ N(w_1...w_n) + \gamma}{N(w_1...w_{n-1})+|\mathcal{V}|\cdot\gamma}, $$ де $N(...)$ - число появи послідовностей слів у тексті, а $+|\mathcal{V}|$ - число слів у словнику. Неважко побачити, що сума $\tilde{P}$ за всіма $w_n\in \mathcal{V}$ дорівнює одиниці. Зазначимо, що, якщо в навчальному корпусі немає n-грами $(w_1...w_{n-1})$, то ймовірності всіх слів словника будуть дорівнювати $1/|\mathcal{V}|$.
Інший спосіб - це відкат (backoff). Так, якщо, наприклад, $P(w_1,w_2 \Rightarrow w_3)$ дорівнює нулю (3-грама $w_1w_2w_3$ не зустрілася в навчальному корпусі), то беруть ймовірність $P(w_2 \Rightarrow w_3)$. Якщо і вона дорівнює нулю, то просто $P(w_3)$. Такий метод вимагає додаткового нормування, оскільки сума отримуваних ймовірностей за всіма словами словника, взагалі кажучи, не дорівнює 1. Відповідно, перплексія буде обчислена невірно. Існують різні варіації backoff-стратегії, що усувають цю проблему.
Достатньо простий спосіб боротьби з нульовими ймовірностями - це інтерполяція, за допомогою якої умовну ймовірність обчислюють таким чином: $$ \tilde{P}(w_1...w_{n-1}\Rightarrow w_n) = \frac{ P(w_1...w_n\Rightarrow w) +\lambda_1\, P(w_2...w_{n-1}\Rightarrow w) +... + \lambda_n\,P(w) } { 1+\lambda_1+...+\lambda_n }. $$ Коефіцієнти $\lambda_1,...\lambda_n$ повинні спадати (більшу вагу дають довші умовні ймовірності). Однак, якщо вони дорівнюють нулю, інформація про ймовірність символу $w_n$ буде отримана з коротшої умовної ймовірності і $\tilde{P}$ ніколи не буде нульовою. Наприклад, можна вибрати $\lambda_k=\beta^k$, де $\beta \in [0...1]$ - параметр моделі. Формально, сума цього виразу за всіма $w$ зі словника дорівнює одиниці (завдяки знаменнику). Однак, це буде так, тільки, якщо $P(w_{n-k}...w_{n-1} \Rightarrow w_n)$ відмінна від нуля хоча б для одного $w_n$. Тому, і в чисельнику, і в знаменнику слід прибирати перші доданки для $P(w_{1}...w_{k} \Rightarrow w)$ у яких $N(w_{1}...w_{k})=0$ (тобто $P=0$ для всіх слів словника).
Можна також ліквідувати доданки з малим значенням $N(w_{1}...w_{k})$ (оскільки вони дають ненадійне значення ймовірності) або враховувати у вагах похибку виміру ймовірності.
nltk: Мовні моделі
Методи боротьби з нульовими умовними ймовірностями реалізовані в nltk як різні мовні моделі. Вони мають однотипний інтерфейс, але різні алгоритми обчислення функції score. Розглянута вище модель MLE для умовної ймовірності просто повертає N(w_1...w_n)/N(w_1...w_{n-1}) Інші моделі мають такі назви:
- nltk.lm.Laplace - Laplace (add one) smoothing
- nltk.lm.Lidstone - Lidstone-smoothed scores
- nltk.lm.KneserNeyInterpolated - Kneser-Ney smoothing
- nltk.lm.WittenBellInterpolated - Witten-Bell smoothing
class Interpolated(LanguageModel):
def __init__(self, beta, *args, **kwargs):
super().__init__(*args, **kwargs)
self.beta = beta
def unmasked_score(self, word, context=None):
if not context:
counts = self.context_counts(context)
return counts[word] / counts.N() if counts.N() > 0 else 0
prob, norm, coef = 0, 0, 1;
for i in range(len(context)+1):
counts = self.context_counts(context[i:])
if counts.N() > 0:
prob += coef * ( counts[word] / counts.N() )
norm += coef
coef *= self.beta
return prob/norm
Метод unmasked_score викликається в методі score
після заміни незнайомих токенів на <UNK> (за допомогою функції lookup).
Наведемо приклади обчислення біграмних умовних ймовірностей і їхньої суми за допомогою різних
методів:
MLE(2) [0.0, 0.0, 0.5, 0.0, 0.5 ] 1.0 Laplace(2) [0.125, 0.125, 0.25, 0.125, 0.25 ] 0.875 Lidstone(0.5, 2) [0.1, 0.1, 0.3, 0.1, 0.3 ] 0.900 KneserNey(2) [0.016, 0.016, 0.466, 0.016, 0.466] 0.983 WittenBell(2) [0.049, 0.049, 0.438, 0.024, 0.438] 1.0 Smooth(0.5, 2) [0.074, 0.074, 0.407, 0.037, 0.407] 1.0 Backoff(2) [0.222, 0.222, 0.5, 0.111, 0.5 ] 1.555Звернемо увагу на останній рядок, у якому представлено результат наївного відкату backoff, який призводить до завищених ймовірностей, сума яких більша за одиницю.
nltk: Генерація тексту
Дану мовну модель можна використовувати для генерації тексту. Для цього служить метод generate, який може почати генерацію з випадкового слова або затравочного тексту text_seed (списку початкових слів):lm.generate(5, random_seed=3) # ['<s>', 'b', 'a', 'b', 'c'] lm.generate(4, text_seed=['<s>'], random_seed=3) # ['a', 'b', 'a', 'b']
Метод generate для отримання чергового слова бере список text_seed (або накопичений при генерації текст), відрізає від нього останні (n = lm.order) - 1 символів (контекст). Потім шукає слова, які в тестовій послідовності могли слідувати за цим контекстом. Якщо таких слів немає, контекст укорочується. Ймовірності таких слів далі обчислюються "чесно" в рамках даної мовної моделі.
Статистичні властивості російської мови
Розглянемо 33 букви в текстах російської мови з алфавітом: "_абвгдежзийклмнопрстуфхцчшщъыьэюя", переводячи текст у нижній регістр, замінюючи 'ё' на 'e' і "неалфавітні" символи на пробіли (підкреслення _ - це пробіл). Потім усунемо кілька поспіль пробілів. Ймовірності окремих букв за текстом довжини N=8'343'164 дорівнюють:
'_': 0.1641, 'с': 0.0437, 'у': 0.0238, 'б': 0.0143, 'э': 0.0030, 'о': 0.0948, 'л': 0.0407, 'п': 0.0234, 'ч': 0.0126, 'ц': 0.0030, 'е': 0.0701, 'р': 0.0371, 'я': 0.0182, 'й': 0.0093, 'щ': 0.0029, 'а': 0.0685, 'в': 0.0368, 'ь': 0.0159, 'ж': 0.0084, 'ф': 0.0017, 'и': 0.0554, 'к': 0.0290, 'ы': 0.0155, 'ш': 0.0071, 'ъ': 0.0003 'н': 0.0551, 'м': 0.0264, 'г': 0.0152, 'х': 0.0070, 'т': 0.0516, 'д': 0.0259, 'з': 0.0144, 'ю': 0.0049,
Перплексія $e^H$ російського тексту за ймовірностями поодиноких букв дорівнює: 20.7 ($\ln H=3.03$, $\log_2H = 4.37$).
Умовні і спільні ймовірності глибини два, відсортовані за спаданням умовних ймовірностей (перша цифра $P(\mathbf{э}\Rightarrow\mathbf{т})=0.83$, друга - $P(\mathbf{э},\mathbf{т})=0.0025$):
эт,0.83, 0.0025 ще,0.52, 0.0015 ъя,0.41, 0.0001 ы_,0.29, 0.0045 пр,0.27, 0.0064 й_,0.79, 0.0074 го,0.50, 0.0076 по,0.40, 0.0093 м_,0.29, 0.0076 щи,0.27, 0.0008 я_,0.63, 0.0114 ъе,0.45, 0.0001 за,0.36, 0.0052 че,0.28, 0.0035 ко,0.27, 0.0078 ь_,0.62, 0.0098 х_,0.45, 0.0031 и_,0.32, 0.0176 ше,0.28, 0.0020 то,0.27, 0.0138 ю_,0.53, 0.0026 же,0.41, 0.0035 хо,0.30, 0.0021 у_,0.28, 0.0066 е_,0.26, 0.0180
Для 3-грам аналогічно, але з фільтром за спільними ймовірностями $P(x_1,x_2,x_3) > 0.001$:
ые_, 0.98, 0.0011 ся_, 0.91, 0.0032 ее_, 0.84, 0.0011 их_, 0.79, 0.0012 ый_, 0.98, 0.0015 ий_, 0.89, 0.0011 ть_, 0.83, 0.0046 ия_, 0.78, 0.0011 лся, 0.97, 0.0014 я_, 0.86, 0.0022 ой_, 0.83, 0.0030 му_, 0.77, 0.0016 что, 0.95, 0.0030 эт, 0.85, 0.0024 его, 0.83, 0.0025 ие_, 0.75, 0.0016 сь_, 0.95, 0.0025 ая_, 0.84, 0.0017 это, 0.81, 0.0020 ей_, 0.71, 0.0014 ет_, 0.46, 0.0021Для 4-грам з фільтром $P(x_1,x_2,x_3,x_4) > 0.0001$
огда, 1.00, 0.0006 рый_, 1.00, 0.0002 _ее_, 1.00, 0.0004 ные_, 1.00, 0.0006 оей_, 1.00, 0.0002 рые_, 1.00, 0.0002 _ей_, 1.00, 0.0001 ный_, 1.00, 0.0007 оего, 1.00, 0.0001 сех_, 1.00, 0.0001 ках_, 1.00, 0.0001 оих_, 1.00, 0.0001 _кто, 1.00, 0.0003 ных_, 1.00, 0.0004Перплексія достатньо швидко насичується і перестає зменшуватися (len(text_trn)=6'678'346, len(text_tst)=1'664'818, методи див. в додатку і my_ngrams.py):
Laplas(1,order) Interpolated(beta, minN=1) Interpolated(beta, minN=3)
order 0.1 0.5 0.8 0.2 0.5 0.8
----------------------------------------------------------------------------------------
1 20.74 20.74 20.74 20.74 20.74 20.74 20.74
2 12.04 12.25 13.27 13.92 12.51 13.27 13.92
3 8.25 8.33 9.24 10.11 8.50 9.24 10.11
4 5.85 5.79 6.52 7.43 5.91 6.52 7.44
5 5.00 4.59 5.01 5.83 4.62 5.02 5.84
6 5.49 4.39 4.34 4.98 4.23 4.35 5.01
7 7.17 4.95 4.12 4.53 4.31 4.11 4.58
8 9.94 6.20 4.16 4.30 4.61 4.07 4.35
9 4.33 4.19 4.99 4.11 4.25
10 4.56 4.16 5.36 4.18 4.20
11 4.81 4.16 4.26 4.18
12 5.04 4.17 4.32 4.18
------------------------------------------------------------------------------------------
best 5.00 4.39 4.12 4.16 4.23 4.07 4.18
Генерація тексту за затравочною фразою "три девицы под окном пряли поздно вечерко" (нижче повторюємо "вечерко" і використовуємо інтерполяцію з $\beta=0.5$):
1 вечеркоелшыго сво гшо ддлтготуэут ттм уи е т ьгевокбт кы жслиотепяниэ дпжевткк нотго вдат на кытен ауьд 2 вечеркогогл ауек кинуге дис уко т номотме виешеызл пряь анй верилере альо овокалиср блччл фричридаелю 3 вечеркообойыхоложе жал с илсяузна эти сти тсково кахопнодто слыекеть наня мот сквексар ни о внылсяарус 4 вечеркокончистоотвалиамекам отается дерсталовом пе я назы и ги сел такогдая что полегкомордиямоглазавшна 5 вечерконечноговя потоненным что стало человам по как что мая тичесили глу приваннытные готовый фарее 6 вечерком состоинственно он не круглой не было и правительно бы чепухую зервы отдадоставая разбогат я 7 вечерком по возвращаясь ко торчащегося обратом городаряла креслу отправятся сказала анна мира а о с 8 вечерком спасибо комов ну и что на паука одуванчик способно расправах вот загременно перемену на часы 9 вечерком главная самое не будет но если согласится а помогать ими и очень и очень доволен и наобороны
- пробіл, голосні, глухі, дзвінкі, ьъ, як насичується перплексія
- розбиття слів на "склади", мінімізація ентропії
Для 28 англійських букв _'abcdefghijklmnopqrstuvwxyz (плюс пробіл і апостроф)
_ 0.1957, i 0.0498, u 0.0189, k 0.0100, e 0.1055, s 0.0486, m 0.0188, v 0.0072, t 0.0725, r 0.0451, g 0.0179, j 0.0025, a 0.0679, d 0.0415, y 0.0163, ' 0.0022, o 0.0592, l 0.0311, f 0.0157, x 0.0012, h 0.0533, w 0.0215, p 0.0140, z 0.0008, n 0.0501, c 0.0196, b 0.0124, q 0.0004перплексія дорівнює 17.07. Для MarkovInterpolated(beta=0.5, minN = 3) при order = 9 перплексія знижується до 2.97 (з len(text_trn)=17'246'125 і len(text_tst)=4'696'973).
Рівень слів
Найпопулярніші слова в ipm (instances per million words для "корпусу" довжиною 1'097'544 слів).
и: 40571 за: 4516 мы: 2458 теперь: 1542 раз: 1148 этом: 922 в: 23556 из: 4439 для: 2205 была: 1457 во: 1138 вам: 910 не: 23270 же: 3894 нет: 2193 ничего: 1453 тоже: 1115 всех: 910 что: 16062 она: 3835 уже: 2184 чем: 1446 один: 1098 тем: 892 на: 15092 сказал: 3828 ну: 2183 были: 1445 здесь: 1096 ей: 885 я: 13387 от: 3565 когда: 2023 того: 1442 том: 1083 сам: 885 он: 11503 еще: 3417 если: 1977 быть: 1433 после: 1070 которые: 872 с: 11490 мне: 3396 до: 1944 будет: 1419 потому: 1066 тогда: 872 то: 8884 бы: 3343 или: 1908 этого: 1416 тебе: 1061 про: 867 а: 8884 ты: 3277 него: 1828 тут: 1353 вас: 1055 больше: 867 как: 7987 меня: 3231 ни: 1776 время: 1316 со: 1050 сказала: 857 это: 7628 да: 3210 есть: 1776 где: 1305 чего: 1035 нам: 844 все: 6730 только: 3164 даже: 1720 себя: 1298 тебя: 1021 ним: 840 но: 6510 о: 3048 их: 1714 потом: 1297 дело: 1014 через: 836 его: 5999 был: 2874 там: 1709 ли: 1284 человек: 1009 спросил: 834 к: 5932 вот: 2717 кто: 1707 под: 1263 который: 993 тот: 817 по: 5455 вы: 2632 очень: 1698 себе: 1235 сейчас: 985 можно: 816 у: 4948 они: 2552 чтобы: 1690 нас: 1234 просто: 971 глаза: 796 так: 4815 ее: 2508 надо: 1599 этот: 1226 при: 951 нибудь: 785 было: 4580 ему: 2507 может: 1552 без: 1172 них: 939 знаю: 782
3-грами, відсортовані за спаданням умовної ймовірності:
о том что, 0.54, 0.00030 по крайней мере, 0.99, 0.00010 в том что, 0.45, 0.00020 несмотря на то, 0.41, 0.00010 для того чтобы, 0.84, 0.00018 так и не, 0.22, 0.00009 на то что, 0.58, 0.00015 в конце концов, 0.62, 0.00009 в то время, 0.56, 0.00013 в первый раз, 0.80, 0.00009 я не знаю, 0.12, 0.00011 в это время, 0.57, 0.00009 так же как, 0.34, 0.00011 в самом деле, 0.59, 0.00009 на самом деле, 0.85, 0.00011 не может быть, 0.35, 0.00009 то время как, 0.70, 0.00010 после того как, 0.88, 0.00009 то что он, 0.11, 0.00010 до сих пор, 1.00, 0.00009
Якщо обмежитися достатньо коротким корпусом довжиною 1'097'544 слів і слова, що зустрічаються менше 10 разів, замінити на <UNK>, то вийде словник у 10'598 слів. У цьому випадку, на відміну від букв, суттєвого зменшення перплексії досягти не можна. Так для MarkovInterpolated(beta=1, minN = 3) маємо:
order: 1 2 3 4 5 perplexity: 454.94 250.91 236.91 239.85 241.06Число унікальних n-грам: [10'598, 331'262, 757'821, 990'097, 1'068'222] достатньо велике і для якісної роботи марковської моделі потрібен суттєво більший корпус текстів.
У національному корпусі російської мови www.ruscorpora.ru довжиною близько 200 млн слів. Там же доступні для завантаження 2,3,4,5 - грами словоформ з їхніми частотами.
Для англійських слів на корпусі 3'825'715 слів (ROCStories) і словнику 10'180 (див. файл 100KStories.zip), маємо:
order: 1 2 3 4 5 6 perplexity: 479.75 156.73 117.26 112.24 112.22 112.30Результати можна поліпшити, якщо обчислювати n-грами і перплексію за реченнями (у ROCStories вони виділені).
Загальні проблеми марковських моделей
Крім зазначених вище проблем великих словників, існує ряд концептуальних обмежень марковських моделей.
- Мова, хоча і є лінійною послідовністю слів, за своєю природою має деревоподібну, ієрархічну структуру (як у рамках одного речення, так і в логіці всього тексту). Наприклад, у реченні "она быстро повернулась и радостно ему улыбнулась" закінчення "ась" визначаються словом "она" і слабко залежать від відстані до нього.
- Марковські моделі є символьними. На рівні слів, у них спочатку не враховується морфологічна і семантична близькість слів. Наприклад "любил" і "любила" (морфологія) або "яблоко" і "груша" (семантика) незалежні об'єкти, що характеризуються тільки номером слова в словнику. Ці проблеми частково долає векторне представлення слів.
Додаток
Деревоподібне представлення n-грам
Напишемо на Python код, який обчислює спільні і умовні ймовірності, для послідовності букв або слів. При аналізі тексту будемо будувати дерево послідовностей, що зустрічаються, і запам'ятовувати число таких зустрічей. Розглянемо таке дерево на прикладі тексту "мама_мыла_раму" (рівень символів).
Нехай ми обмежилися триграмами (необхідними для обчислення спільних $P(x_1,x_2,x_3)$ і умовних $P(x_1,x_2\Rightarrow x_3)$ ймовірностей). Будемо ковзати текстом вікном у три символи, зсуваючись на один символ. Перша послідовність "мам" дає першу гілку дерева root -> м -> а -> м. У кожному вузлі записуємо одиницю. Наступна послідовність "ама" породить ще одну гілку, що виходить із кореня. Третя послідовність "ма_" починається як перша гілка, тому перші два її вузли збільшать лічильники в "м" і "а", а другий вузол "а" розщепиться на дві гілки (для символів "м", "_").
Неважко побачити, що умовна ймовірність $P(\mathbf{ма}\Rightarrow \mathbf{м})$ дорівнює відношенню числа в нижньому вузлі "м" до числа в попередньому йому вузлі "a", тобто 1/2=0.5. Спільна ймовірність $P(\mathbf{мам})$ дорівнює відношенню числа в останньому вузлі до загального числа послідовностей довжини 3. Це ж дерево дає коротші умовні або спільні ймовірності: $P(\mathbf{м} \Rightarrow \mathbf{а}) = P(\mathbf{ма})/P(\mathbf{а})=2/3$.
На Python будемо зберігати кожен вузол у формі словника всіх гілок, що виходять з нього, із зазначенням числа count потрапляння у цю гілку від кореня: words = { word: [count, words], ...}. Словник word має таку ж структуру. Наприклад, дерево вище починається таким чином:
{'м': [3, {'а': [2, {'м': [1, {}],
'_': [1, {}] }],
'ы': [1, {'л': [1, {}]} ]]
}
],
...
}
Клас NGramsCounter
Наведемо клас NGramsCounter, який підраховує умовні і спільні ймовірності максимальної глибини order. Словами можуть бути символи, рядки або числа (індекси слів).
class NGramsCounter:
def __init__(self, order = 1):
self.order = order # глибина дерева (макс. довжина n-grams)
self.root = {} # корінь дерева (наш словник)
self.ngrams= [0]*(order+1) # число n-grams довжини n=1,2,...,order
Метод add додає нові приклади зі списку слів lst. Якщо словами є символи, то lst може бути рядком, інакше це обов'язково список.
def add(self, lst):
for n in range(self.order): # скільки яких n-grams додалося
self.ngrams[n+1] += max(len(lst) - n , 0)
for i in range( len(lst) ): # біжимо по тексту
node = self.root
for n, w in enumerate(lst[i: i+self.order]):
if w in node: node[w][0] += 1 # це слово вже було
else: node[w] = [1, {}] # нове слово
node = node[w][1] # на наступний вузол дерева
Метод prob отримує на вхід список слів lst і повертає умовну ймовірність P(lst[0],...,lst[len-2] => lst[len-1]), при len==1: P(lst[0]), якщо cond = True або безумовну ймовірність при cond = False Якщо слова це символи, то lst може бути рядком, інакше це список.
def prob(self, lst, cond=True):
n_cur, n_prv, _ = self.counts(lst)
if n_cur == 0:
return 0 # слово не знайшли - ймовірність 0
return n_cur/(n_prv if cond else self.ngrams[len(lst)])
Повний код класу (з додатковими перевірками і іншими методами) можна знайти в my_ngrams.py.
Приклади використання NGramsCounter
counter = NGramsCounter(3) # буде 1,2,3 - грам
counter.add('мама мыла раму') # підраховуємо n-грами букв
print("розмір словника:", len(counter.root)) # 7
print("слова словника:", counter.branches()) # [('м', 4), ('а', 4), ...]
print(counter.ngrams[1:]) # [14, 13, 12] число n-грам n=1,2,3
print(counter.unique() ) # [7, 10, 12] унікальних n-грам
N1, N2, _ = counter.counts('м') # N1 раз була 'м', N2 - довжина тексту
print("N('м'), N = ", N1, N2) # 4, 14
print("P('м') = ", counter.prob('м')) # 0.2857 = 4/14 = N1/N2
N1, N2, _ = counter.counts('ма') # N1 раз було 'ма', N2 - було 'м'
print("N('ма'),N('м') = ", N1, N2) # 2, 4
print("P('м=>а') = ", counter.prob('ма')) # 0.5 = 2/4 = N1/N2
print("P(ма=>м) = ", counter.prob('мам')) # 0.5 = 2/4 умовна
print("P(мам) = ", counter.prob('мам', False))# 0.083 = 1/12 спільна
print(counter.branches('ма')) # [('м', 1), (' ', 1)] що після ма
counter.all_branches()
# [(['м', 'а', 'м'], 1), (['м', 'а', ' '], 1),... всі гілки
Ймовірності в класі NGramsCounter обчислюються як просте відношення N1/N2. Для більш просунутих способів слід використовувати нащадків від класу Markov.
Мовні моделі містять у собі counter, який наповнюється у функціях add. Але можна їм передати і зовнішній counter, що зручно при використанні кількох моделей:
lm = MarkovLaplas(beta=1, order=3, counter=counter)
print(lm.counter.prob("ру")) # 0
print(lm.prob("ру")) # 0.125 = (0+1)/(1+7)
print(lm.perplexity("мама умыла раму")) # 4.886
Доступні такі мовні моделі:
- Markov
- MarkovLaplas
- MarkovInterpolated
- MarkovLaplasInterpolated
- MarkovBackoff
