Как обучть мдль пнмть упртые скрщня

Автор: admin от 14-01-2018, 20:30, посмотрело: 178

Недавно я натолкнулся на вопрос на Stackoverflow, как восстанавливать исходные слова из сокращений: например, из wtrbtl получать water bottle, а из bsktballbasketball. В вопросе было дополнительное усложнение: полного словаря всех возможных исходных слов нет, т.е. алгоритм должен быть в состоянии придумывать новые слова.



Вопрос меня заинтриговал, и я полез разбираться, какие алгоритмы и математика лежат в основе современных опечаточников (spell-checkers). Оказалось, что хороший опечаточник можно собрать из n-граммной языковой модели, модели вероятности искажений слов, и жадного алгоритма поиска по лучу (beam search). Вся конструкция вместе называется модель зашумлённого канала (noisy channel).



Вооружившись этими знаниями и Питоном, я за вечер создал с нуля модельку, способную, обучившись на тексте "Властелина колец" (!), распознавать сокращения вполне современных спортивных терминов.



Как обучть мдль пнмть упртые скрщня

Опечаточники используются много где: от клавиатуры вашего телефона до поисковых систем и голосовых помощников. Сделать хороший опечаточник не так просто, ибо он должен быть одновременно быстрым и готовым ко всему (в том числе исправить ошибки в словах, которые до этого никогда не видел). Именно поэтому в опечаточниках используется столько науки. Цель статьи — дать представление об этой науке и просто развлечься.



Математика внутри опечаточника



Модель зашумлённого канала рассматривает каждую аббревиатуру как результат случайного искажения исходной фразы.



Чтобы восстановить оригинальное словосочетание, надо ответить на два вопроса: какие исходные слова вероятны, и какие искажения фраз вероятны?



По теореме Байеса,



Как обучть мдль пнмть упртые скрщня



Как обучть мдль пнмть упртые скрщня



где Как обучть мдль пнмть упртые скрщня — это любое такое изменение исходной Как обучть мдль пнмть упртые скрщня, которое делает из неё наблюдаемую Как обучть мдль пнмть упртые скрщня. Символ Как обучть мдль пнмть упртые скрщня обозначает прямую пропорциональность.



И вероятность всевозможнных фраз, и вероятность трансформаций могут быть оценены с помощью статистических моделей. Я буду использовать простейший вид моделей — буквенные n-граммы. Можно было бы применять и более сложные модели (например, рекуррентные нейросети), принципиально это ничего не меняет.



Имея такие модели, можно подобрать наиболее правдоподобную исходную фразу буква за буквой, используя алгоритм жадного направленного поиска, beam search.



N-граммная языковая модель



n-граммная модель по предыдущим n-1 буквам фразы определяет вероятность следующей, n-той буквы (и игнорирует все буквы, которые были перед ними). Например, вероятность буквы "g" после последовательности "bowlin" будет вычислена 4-граммной моделью как Как обучть мдль пнмть упртые скрщня, т.к. все буквы, предшествующие этим четырём, модель для простоты игнорирует. Такие условные вероятности определяются ("выучиваются") по обучающему корпусу текстов. Продолжая пример,



Как обучть мдль пнмть упртые скрщня



где Как обучть мдль пнмть упртые скрщня — это количество сочетаний "ling" в обучающем корпусе, а Как обучть мдль пнмть упртые скрщня — количество всех 4-грамм в тексте, начинающихся на "lin".



Чтобы оценивать вероятности даже редких n-грамм более адекватно, я применил две уловки. Во-первых, к каждому счётчику я прибавляю число Как обучть мдль пнмть упртые скрщня — это гарантирует, что я не буду делить на ноль. Во-вторых, для подсчёта я использую не только n-граммы (которых может быть мало в тексте), но и (n-1)-граммы (они встречаются чаще), и так далее, вплоть до самой простой модели, которая вообще не смотрит на контекст. Но счётчики меньших порядков используются с весами, убывающими в геометрической прогрессии с темпом Как обучть мдль пнмть упртые скрщня. Поэтому на самом деле вероятность Как обучть мдль пнмть упртые скрщня я вычисляю как



Как обучть мдль пнмть упртые скрщня



Впрочем, довольно теории! Посмотрим лучше, как выглядит код модели на языке Python





Модель "опечаток"



Языковая модель была нужна, чтобы понять, какими обычно бывают исходные фразы. Модель искажений нужна, чтобы понять, как обычно исходные фразы искажаются.



Я буду предполагать, что единственное возможное искажение — это вычёркивание из фразы некоторых символов. При желании, модель можно модифицировать, чтобы она учитывала и другие искажения, например, замены и перестановки букв.



У меня нет большой выборки, на которой можно обучать сложную модель. Поэтому для оценки вероятности искажений я буду использовать 1-граммы. То есть моя модель будет просто запоминать для каждого символа, с какой вероятностью он вычёркивается из сокращения. Впрочем, закодирую я её на всякий случай в общем виде, как n-граммную модель.





Пример работы моделей



Чтобы понять, как работают модели языка и сокращений, посмотрим на простой пример. Языковая модель обучим на одном слове и посмотрим, как она предсказывает продолжение слова "bra". С её точки зрения, "b" — самое правдоподобное продолжение (потому что эта буква чаще всего идёт после "a").



lang_model = LanguageNgramModel(1)
lang_model.fit(' abracadabra ')
print(lang_model.predict_proba(' bra'))


     0.181777
a    0.091297
b    0.272529
c    0.181686
d    0.181686
r    0.091025
dtype: float64


Модель сокращений обучим тоже на одном примере (слово, сокращение). В этом примере мы сокращали только букву "а", поэтому для неё вероятность сокращения модель оценивает высоко, а для буквы "b" — ниже. Вероятность пропуска буквы "c" модель оценила выше, чем "b", потому что "с" она реже встречала в обучающих примерах.



missed_model = MissingLetterModel(0)
missed_model.fit([('abracadabra', 'abr-c-d-br-')]) 

print({letter: missed_model.predict_proba('abr', letter) for letter in 'abc'})


{'a': 0.7166666666666667, 'b': 0.09999999999999999, 'c': 0.15}


А вот так модель сокращений оценивает вероятность того, что "abra" будет сокращена как "abr-"



print(missed_model.single_proba('', 'abra', 'abr-'))


0.164475


Жадный поиск наиболее правдоподобной фразы



Имея модели языка и искажений, теоретически можно оценить вероятность любой исходной фразы. Для этого нужно всего лишь перебрать все возможные пары (исходная фраза, трансформация) и оценить правдоподобие каждой. Но их слишком много: например, в алфавите из 27 символов возможны Как обучть мдль пнмть упртые скрщня фраз из 10 букв; перебрать их все — нереально. Нужен более хитрый алгоритм.



Мы воспользуемся тем, что обе модели — однобуквенные, и будем подбирать буквы исходной фразы одну за другой. Для этого мы заведём кучу неполных фраз-кандидатов, и для каждой оценим, насколько она соответствует аббревиатуре. Наилучшего кандидата мы дополним всеми разнообразными буквами-продолжениями и гипотезами о том, были ли они пропущены, и добавим в кучу. Чтобы не создавать слишком много вариантов, будем брать только "достаточно хорошие" продолжения. Тех кандидатов, которые уже могут быть полноценными исходными фразами, мы отложим в сторону, и в конце выдадим в качестве ответа. Процедуру будем повторять, пока не закончится куча либо максимальное число итераций.



Как обучть мдль пнмть упртые скрщня

Как меру качества кандидатов мы будем использовать оценку логарифма вероятности имеющейся аббревиатуры при условии того, что исходная фраза начинается, как этот кандидат, а заканчивается, как сама аббревиатура. Для управления поиском введём два параметра — optimism и freedom. Optimism оценивает, насколько улучшится расшифровка, когда мы дойдём до конца аббревиатуры. Этот коэффициент имеет смысл выбирать между 0 и 1, и чем ближе он к 1, тем быстрее алгоритм будет пытаться добавить новые символы в расшифровку. Freedom — это то, насколько качество кандидатов может быть хуже наилучшего текущего варианта, и при увеличении этого параметра алгоритм рассматривает больше различных вариантов. Если установить очень высокое значение freedom, алгоритм будет перебирать все варианты (коих бесконечность), и работать очень долго, но при маленьких значениях freedom куча может закончиться до того, как будет найден хоть один адекватный вариант.





Если внимательно почитать мой код, можно заметить, что я сделал ещё одно упрощение — вместо того, чтобы суммировать вероятности всех искажений исходного слова, я рассматриваю только одно искажение. Это не всегда верно: например, "ball" можно сократить до "bl", вычеркнув как первую ("b--l"), так и вторую ("b-l-") букву "l". Но если таких повторений нет, то адекватный вариант сокращения почти всегда единственный.





Применим наш алгоритм для поиска возможных расшифровок аббревиатуры "brc".



result = noisy_channel('brc', lang_model, missed_model, verbose=True, freedom=1)
print(result)


baseline score is 7.68318306228
(6.9148647560475442, ' ', 'brc ', '', 6.9148647560475442)
(6.755450684372974, ' b', 'rc ', '', 4.7044649199466617)
(5.8249119494605051, ' br', 'c ', '', 2.6863637325526679)
(7.088440394887126, ' brc', ' ', '', 1.7075575253192956)
(7.1392598304831516, ' bra', 'c ', 'a', 2.6863637325526679)
(7.6831830622750497, ' brc ', '', '', -0.0)
(8.0284469273601662, ' brac', ' ', '', 1.7075575253192956)
(8.3621576081202385, ' a', 'brc ', 'a', 6.776535093383159)
(7.6954572168460142, ' ab', 'rc ', '', 4.7044649199466617)
(6.7649184819335453, ' abr', 'c ', '', 2.6863637325526679)
(8.0284469273601662, ' abrc', ' ', '', 1.7075575253192956)
(8.0792663629561936, ' abra', 'c ', 'a', 2.6863637325526679)
(8.6231895947480908, ' abrc ', '', '', -0.0)
(8.6231895947480908, ' brac ', '', '', -0.0)
(8.6740629096242063, ' brca', ' ', 'a', 1.7075575253192956)
heap size is 0 after 15 iterations
{'brc': 7.6831830622750497, 'abrc': 8.6231895947480908, 'brac': 8.6231895947480908}


Тестирование на хоббитах



По-настоящему протестировать написанные алгоритмы можно только с хорошей языковой моделью. Мне было интересно, как качественно модель сможет расшифровывать аббревиатуры, обучившись на заведомо ограниченном корпусе — одной книге, да ещё и специфической тематики. Первая книга, которая попалась мне под руку — это "The Lord Of The Rings: The Fellowship of the Ring". Что ж, посмотрим, как язык хоббитов может помочь расшифровать современные спортивные термины.



Для начала — код для обучения модели



import re
# считываем текст
with open('Fellowship_of_the_Ring.txt', encoding = 'utf-8') as f:
    text = f.read()
# оставляем только буквы и пробелы в тексте
text2 = re.sub(r'[^a-z ]+', '', text.lower().replace('n', ' '))
all_letters = ''.join(list(sorted(list(set(text2)))))
print(repr(all_letters)) # ' abcdefghijklmnopqrstuvwxyz'
# готовим обучающую выборку для модели опечаток:
missing_set =  (
    [(all_letters, '-' * len(all_letters))] * 3 # тут считаем все буквы пропущенными
    + [(all_letters, all_letters)] * 10 # тут считаем все буквы НЕ пропущенными
    + [('aeiouy', '------')] * 30 # тут считаем пропущенными только гласные
)
# обучаем обе модели
big_lang_m = LanguageNgramModel(order=4, smoothing=0.001, recursive=0.01)
big_lang_m.fit(text2)
big_err_m = MissingLetterModel(order=0, smoothing_missed=0.1)
big_err_m.fit(missing_set)


' abcdefghijklmnopqrstuvwxyz'


Четырёхграммную модель языка я выбрал, сравнив правдоподобие разных моделей на "тестовой выборке" — самом конце книги. Оказалось, что качество предсказания вероятности букв растёт с ростом порядка модели до 4. Ещё больший порядок я не стал использовать, ибо с ростом порядка сильно падает скорость работы модели.



for i in range(5):
    tmp = LanguageNgramModel(i, 0.001, 0.01)
    tmp.fit(text2[0:-5000])
    print(i, tmp.single_log_proba(' ', text2[-5000:]))


0 -13858.8600648
1 -11608.8867664
2 -9235.21749986
3 -7461.78935696
4 -6597.9544372


Применим наш алгоритм к разным сокращениям. Загаданного мной Сэма, например, модель распознала без труда, да ещё и добавила других опций (впрочем, с более высоким скором, а значит, менее правдоподобных).



noisy_channel('sm', big_lang_m, big_err_m)


{'sam': 7.3438449620080997,
 'same': 9.5091694602417469,
 'some': 7.6890573935288824}


Фродо тоже распознаётся без проблем



noisy_channel('frd', big_lang_m, big_err_m)


{'frodo': 6.8904938902680888}


Кольцо угадывается однозначно.



noisy_channel('rng', big_lang_m, big_err_m)


{'ring': 7.6317120419343913}


Прежде чем запускать "wtrbtl", проверим расшифровку по частям. С водой всё отлично.



noisy_channel('wtr', big_lang_m, big_err_m)


{'water': 8.6405279255413898}


Бутылку модель распознаёт уже не так уверенно. Всё-таки битвы во "Властелине колец" упоминаются чаще бутылок.



noisy_channel('btl', big_lang_m, big_err_m)


{'battle': 12.620490427990008,
 'bottle': 13.3327872548629,
 'but all': 14.66815480120338,
 'but ill': 15.387630853411283}


Например, в таких вот словосочетаниях:



noisy_channel('batlhrse', big_lang_m, big_err_m)


{'battle horse': 25.194823785457018, 'battle horses': 27.40528952535044}


Для бутылки с водой вылезло много альтернатив:



noisy_channel('wtrbtl', big_lang_m, big_err_m)


{'water battle': 23.76999162985074,
 'water bottle': 23.962598992336815,
 'water but all': 24.445047133561353,
 'water but ill': 25.164523185769259,
 'water but lay': 25.601336188357113,
 'water but lie': 26.668305553728047}


Зато баскетбол (никогда не виденный) модель распознала почти правильно, благо слово "basket" в обучающем тексте встречалось. Но чтобы это сделать, пришлось вручную увеличить ширину "луча", из которого модель выбирает варианты.



print(noisy_channel('bsktball', big_lang_m, big_err_m, freedom=5))


{'bsktball': 33.193085889457429, 'basket ball': 33.985227947093364}


Зато слово "ball" в обучающем тексте не встретилось ни разу, и самостоятельно модель его не восстановила (зато заподозрила в "bl" имя Бильбо). Слово "bowling" во "Властелине колец" тоже ни разу не встречалось, но исходя из какого-то общего представления о языке модель его всё-таки предложила.



print(noisy_channel('bwlingbl', big_lang_m, big_err_m, freedom=5))


{'bwling blue': 31.318936077746862, 'bwling bilbo': 30.695249686758611, 'bwling ble': 34.490254059547475, 'bwling black': 31.980325659562851, 'bwling blow': 33.15061216480305, 'bewilling blue': 30.937989778499748, 'bewilling bilbo': 30.314303387511497, 'bewilling ble': 34.109307760300361, 'bewilling black': 31.599379360315737, 'bewilling blin': 34.685939493896406, 'bewilling blow': 32.769665865555929, 'bewilling bill': 32.156071732628014, 'bewilling below': 32.195518180732158, 'bwling bill': 32.537018031875135, 'bewilling belia': 32.550377929021479, 'bwling below': 32.576464479979279, 'bwling belia': 32.931324228268608, 'bwling belt': 33.203704016765826, 'bwling bling': 33.393527121566656, 'bwling bell': 34.180762531759534, 'bowling blue': 30.676613106535022, 'bowling bilbo': 30.052926715546771, 'bowling ble': 33.847931088335635, 'bowling black': 31.338002688351011, 'bowling blin': 34.42456282193168, 'bowling blow': 32.508289193591203, 'bowling bill': 31.894695060663285, 'bowling below': 31.934141508767446, 'bowling bl': 34.983414721126472, 'bowling blad': 34.992926061009179, 'bowling belia': 32.289001257056761, 'bwling blind': 35.000922570770712}


Генерация упоротых текстов



Под конец, чтобы немного развеселить вас, я попробовал превратить в сокращения уже сам кусок текста "Властелина колец". Получилось странно.



part = text[10502:11149]
result = ''
for i, letter in enumerate(part):
    if np.random.rand() * 0.5 < big_err_m.single_proba(part[0:i], letter):
        result += letter
print(result)


This bok s largly cncernd wth Hbbts, nd frm its pges  readr ma dscver much f thir charctr nd  littl f thir hstr. Furthr nfrmaton will als b fond n the selction from the Red Bok f Wstmarch that hs already ben publishd, ndr th ttle of The Hobbit. Tht stor was dervd from the arlir chpters of the Red Bok, cmpsed by Blbo hmslf, th first Hobbit t bcome famos n the world at large, nd clld b him There and Bck Again, sinc thy tld f his journey into th East and his return: n dvntr whch latr nvolved all the Hobbits n th grat vnts of that Ag that re hr rlatd.


Языковую модель можно использовать, чтобы сгенерировать текст "в стиле Толкина", правда, без всякого смысла.



np.random.seed(20)
text = "Frodo"
for i in range(300):
    proba = big_lang_m.predict_proba(text)
    text += np.random.choice(proba.index, size=1, p=proba)[0]
print(text+'.')


Frodo would me but them but his slipped in he see said pippin silent the names for follow as days are or the hobbits rever any forward spoke ened with and many when idle off they hand we cried plunged they lit a simply attack struggled itself it for in a what it was barrow the will the ears what all grow.


Генерировать "с нуля" связные тексты наука о данных пока так и не научилась. Ибо для этого нужен самый настоящий искусственный интеллект, обладающий пониманием сюжета, разворачивавшегося когда-то в Средиземье.



Заключение



Обработка естественного языка — вообще-то очень сложная смесь науки, технологии, и магии. Даже учёные-лингвисты не до конца понимают законов, в соответствии с которыми устроена речь. И до тех времён, когда машины смогут в полном смысле слова понимать тексты, ещё очень не скоро.



Обработка естественного языка — это ещё и весело. Вооружившись парой статистических моделек, оказывается, можно и распознавать, и порождать неочевидные аббревиатуры. Для тех, кто хочет продолжить мои развлечения, вот полный код эксперимента.



А вот если заменить n-граммную модель на рекуррентную нейросетку, можно генерировать тексты более высокой степени связности (и даже почти компилируемый код). В ближайшем будущем я попробую сгенерить нейронкой типичную статью в стиле Хабра (который я уже распарсил), поэтому подписывайтесь и ждите :)



Источник: Хабрахабр

Категория: Программирование » Веб-разработка

Уважаемый посетитель, Вы зашли на сайт как незарегистрированный пользователь.
Мы рекомендуем Вам зарегистрироваться либо войти на сайт под своим именем.

Добавление комментария

Имя:*
E-Mail:
Комментарий:
Полужирный Наклонный текст Подчеркнутый текст Зачеркнутый текст | Выравнивание по левому краю По центру Выравнивание по правому краю | Вставка смайликов Выбор цвета | Скрытый текст Вставка цитаты Преобразовать выбранный текст из транслитерации в кириллицу Вставка спойлера
Введите два слова, показанных на изображении: *