Лингвистика для математиков. Исправление опечаток 2 + Токенизация презентация

Soundex
Soundex — это алгоритм для кодирования имён собственных.
1918–1922 гг. в США Роберт Расселл и Маргарет Кинг Оделл
Цель: облегчить поиск похоже звучащих фамилий
В середине XX века использовался при анализе результатов переписей населения 1890–1920 гг

Soundex

Дан список фамилий и соответствующих им кодов Soundex в перепутанном порядке. Некоторые символы пропущены:
Allaway, Anderson, Ashcombe, Buckingham, Chapman, Colquhoun, Evans, Fairwright, Kingscott, Lewis, Littlejohns, Stanmore, Stubbs, Tocher, Tonks, Whytehead
S312, T␣6␣, ␣5␣3, C42␣, T520, L␣42, A536, C155, ␣623, S356, ␣252, ␣152, ␣330, A251, A400, L2␣0

Soundex
Задание 1. Опишите пошагово, как генерируется код Soundex.
Задание 2. Установите соответствия между фамилиями и кодами Soundex и вставьте пропущенные символы.
Задание 3. Постройте коды Soundex для следующих фамилий: Ferguson, Fitzgerald, Hamnett, Keefe, Maxwell, Razey, Shaw, Upfield.

Ответы
Ответ на задание 2
Allaway: A400, Anderson: A536, Ashcombe: A251, Buckingham: B252, Chapman: C155, Colquhoun: C425, Evans: E152, Fairwright: F623, Kingscott: K523, Lewis: L200, Littlejohns: L342, Stanmore: S356, Stubbs: S312, Tocher: T260, Tonks: T520, Whytehead: W330.
Ответ на задание 3.
Ferguson: F622, Fitzgerald: F326, Hamnett: H530, Keefe: K100, Maxwell: M240, Razey: R200, Shaw: S000, Upfield: U143.

Soundex
Проблемные моменты:
Выкидывание h/w вообще-то портит много кейсов. (Придумайте сами такое имя собственное)
Для каких языков не_будет работать?
Не учитывает вариативность произношения

Улучшенный Soundex

Улучшенный Soundex
В среднем, на одно значение кода Soundex приходится 21 фамилия. В случае же улучшенной версии Soundex, к одному и тому же коду преобразуются всего 2-3 фамилии.

Soundex
Идея называется - нечёткий поиск (approximate string matching, fuzzy string searching)
Супер реализации в python и MySQL

Алгоритм Metaphone
Придумали в 1990
Существует для английского, бразильского португальского, испанского и русского
Неудобно, потому что нужно прописывать много фонетических правил, но точнее
Лучше, чем Soundex, потому что учитывает варианты произношения
Не делит буквы на группы → теряет меньше информации
кодирует слова путем уменьшения их до 16 согласных звуков: B, X, S, K, J, T, F, H, L, M, N, P, R, 0, W, Y. Ноль представляет звук "th"; X представляет "sh"

Алгоритм Metaphone
Drop duplicate adjacent letters, except for C.
If the word begins with 'KN', 'GN', 'PN', 'AE', 'WR', drop the first letter.
Drop 'B' if after 'M' at the end of the word.
'C' transforms to 'X' if followed by 'IA' or 'H' (unless in latter case, it is part of '-SCH-', in which case it transforms to 'K'). 'C' transforms to 'S' if followed by 'I', 'E', or 'Y'. Otherwise, 'C' transforms to 'K'.
'D' transforms to 'J' if followed by 'GE', 'GY', or 'GI'. Otherwise, 'D' transforms to 'T'.
Drop 'G' if followed by 'H' and 'H' is not at the end or before a vowel. Drop 'G' if followed by 'N' or 'NED' and is at the end.

Алгоритм Metaphone
'G' transforms to 'J' if before 'I', 'E', or 'Y', and it is not in 'GG'. Otherwise, 'G' transforms to 'K'.
Drop 'H' if after vowel and not before a vowel.
'CK' transforms to 'K'.
'PH' transforms to 'F'.
'Q' transforms to 'K'.
'S' transforms to 'X' if followed by 'H', 'IO', or 'IA'.
'T' transforms to 'X' if followed by 'IA' or 'IO'. 'TH' transforms to '0'. Drop 'T' if followed by 'CH'.

Алгоритм Metaphone
'V' transforms to 'F'.
'WH' transforms to 'W' if at the beginning. Drop 'W' if not followed by a vowel.
'X' transforms to 'S' if at the beginning. Otherwise, 'X' transforms to 'KS'.
Drop 'Y' if not followed by a vowel.
'Z' transforms to 'S'.
Drop all vowels unless it is the beginning.

Алгоритм Metaphone
ALEXANDRE → ALEKSANTRE → ALKSNTR
ALEKSANDER → ALEKSANTER → ALKSNTR

Алгоритм Metaphone
AKXN → Агашин, Акаченок, Акишин, Аксионенко, Аксионов, Акчунаев, Акшанов, Акшенцев, Акшинский, Акшинцев, Акшонов.
FSLX → Василишин, Васильчак, Васильченко, Васильчик, Васильчиков, Васильченко, Васильчук, Василющенко.
SRFM → Серафимов, Серафимский, Серафимчук, Церейфман.
Одно и то же значение кода Metaphone имеют в среднем 6 фамилий.

Русский Metaphone
2002
Этот алгоритм преобразует к одному и тому же коду в среднем 1-2 фамилии.
Учитывает безударные гласные и слияние согласных при произношение
Мало правил - круто
При это, возможно, слишком строго

Для всех гласных букв проделать следующие операции.
ЙО, ИО, ЙЕ, ИЕ → И
О, Ы, Я → А
Е, Ё, Э → И
Ю → У
Для всех согласных букв, за которыми следует любая согласная, кроме Л, М, Н или Р, либо же для согласных на конце слова, провести оглушение:
Б → П
З → С
Д → Т
В → Ф
Г → К

Для всех гласных букв проделать следующие операции.
ЙО, ИО, ЙЕ, ИЕ → И
О, Ы, Я → А
Е, Ё, Э → И
Ю → У
Для всех согласных букв, за которыми следует любая согласная, кроме Л, М, Н или Р, либо же для согласных на конце слова, провести оглушение:
Б → П
З → С
Д → Т
В → Ф
Г → К
Склеиваем ТС и ДС в Ц: ТС → Ц

Русский Metaphone примеры
ВИТАФСКИЙ → Витавский, Витовский.
ВИТИНБИРК → Витенберг, Виттенберг.
НАСАНАФ → Насанов, Насонов, Нассонов, Носонов.
ПИРМАКАФ → Пермаков, Пермяков, Перьмяков

Алгоритм Match rating approach
Использует и фонетические правила (comparison rules and encoding rules), и расстояния
Полученное расстояние между словами сравнивается с минимальным порогом
Откуда порог?

Алгоритм Match rating approach
Encoding праила:
Удалить все гласные, если они не в начале слова
Удалить вторую согласную из всех комбинаций с двумя согласными
Уменьшить длину кода до шести. Как? Соединить три первых и три последний буквы
Потом similarity comparison с таблицами по необходимости

Алгоритм Match rating approach

There is more
Другие методы из серии approximate string matching:
Caverphone
NYSIIS
Daitch-Mokotoff Soundex
Double metaphone
и т.д.
https://habr.com/ru/post/114947/

Другие методы: применение машинного обучения
В основном для случаев real word errors:
see you in five minuets! -- такие ошибки могут составлять вплоть до 15% от всех опечаток
Как? Контекст!
Проблема: проверять для каждого слова контекст -- долго!
Textbook example:
Noisy channel model

Модель noisy channel
written text → into a spoken text

Модель noisy channel

Кто такой Питер Норвиг?
Закодил один из простейших алгоритмов spellcheck (И всего лишь в 21 строчку кода!)
https://norvig.com/spell-correct.html
2007 год

Регулярные выражения и нормализация текста

ELIZA - первая Алиса

Регулярные выражения
Что это такое?
Какой-то формальный язык, помогающий искать в тексте/строке какие-то паттерны
Regex: one pattern to rule them all, one to find them. One to bring them all, and in the darkness bind them.

Формальный язык
Итак: контекстные замены -- приведите пример?

Формальный язык
Что есть в формальном языке?
Алфавит (конечный)
IPA - это алфавит
буквы кириллического алфавита
буквы латинского алфавита
набор грамматических категорий - тоже алфавит!
?
Слова
Языки

Формальные языки
У них есть много подвидов и даже иерархия, но об этом чуть дальше
Регулярный язык - это самый простой формальный язык
Регулярный язык:
Есть фиксированный алфавит
Мы говорим, что в языке, основанном на этом алфавите, все слова образуются с помощью какого-то одного (регулярного) правила

Правила регулярного языка
Приоритет операций: итерация, конкатенация, объединение

Примеры регулярных языков

Примеры регулярных выражений в лингвистике

Примеры регулярных выражений в лингвистике

Примеры регулярных выражений в лингвистике

Примеры регулярных выражений в лингвистике

Примеры регулярных выражений в лингвистике

Регулярные выражения: Хомский
Так, а причем здесь Хомский?
Иерархия Хомского
-- классификация формальных языков и формальных грамматик;
4 типа по их условной сложности

Формальная грамматика
Terminals: {s, sh, ss}
Nonterminals: {snake, I, am}
Production rules: {I → sh, am → s, snake → ss}

Формальная грамматика
Аналогия в синтаксисе:

Регулярные выражения и конечные автоматы
Есть регулярное выражение: colou?r, которое описывает такой набор слов:
{colour, color}
Как компьютер формализует, что это множество слов описывается одним регулярным выражением/языком?

Регулярные выражения и конечные автоматы
colou?r -- {colour, color}

Нарисуйте конечные автоматы для слогов
для закрытого слога
для слова с 2 гласными, разделёнными хотя бы одним согласным
В узлах какие-то условные переменные, главное - связи между узлами
Разрешены петли. Петли означают повторение много раз, что в регулярных выражениях соответствует звёздочке *

Нарисуйте конечные автоматы для слогов
для закрытого слога
для слова с 2 гласными, разделёнными хотя бы одним согласным

Регулярки в ELIZA

Регулярки в ELIZA

Нормализация текстов
Токенизация
Удаление стоп-слов
Приведение к начальной форме / лемматизация / нормализация
Разделение на предложения

Токенизация и стоп-слова
Удалить знаки препинания, хештеги, смайлики и прочую ненужную ерунду
Поделить по пробелам (смотри картинку)
Удалить стоп-слова
и, в, во, не, .. .. .., более, всегда, конечно, всю, между

Токенизация

Нормализация, лемматизация, стемминг…
В чём разница?
Токенизация и нормализация слов делаются методом каскадов простых регулярных выражений и/или с помощью конечных автоматов.

Byte-pair encoding для токенизации
Не отталкивается от того, что является лингвистически словом в конкретном языке (ура?)
Иногда нам хочется делить точно по пробелам и выделять слова типа spinach, а иногда в том же тексте нам хочется что какая-нибудь более длинная сущность тоже с пробелами внутри выделилась как слово: New York Times. А иногда мы хотим выделять морфемы в отдельные слова.
можно учитывать редкие слова или новые слова, не встречающиеся в корпусе
data compression - выгодно для экономии памяти

Byte-pair encoding для токенизации
С этим алгоритмом никакие слова не будут забыты и не распознаны

Byte-pair encoding для токенизации
Словарь на входе с информацией по частотности слов

Byte-pair encoding для токенизации
Смотрим какая комбинация из двух символов самая частотная

Byte-pair encoding для токенизации
Снова ищем самую частотную пару символов уже в новом словаре

Byte-pair encoding для токенизации
И снова:

Byte-pair encoding для токенизации
Если мы дойдем до конца выйдет вот что:
Это наш словарь

Byte-pair encoding для токенизации
Что будет с каким-нибудь неизвестным нам ранее словом lower? Оно токенизируется в два low + er.
И это супер-хорошо, потому что мы смогли отделить морфему!
Значит, и прочитать такой текст компьютер сможет, ведь у er есть собственное значение

Домашнее задание (оцениваемое)
Напишите правила для своей ELIZA, но с каким-то другим концептом, не психолога :)
паттерн описанный регуляркой у собеседника + ответная реплика ELIZA тоже описанная регуляркой. Помните, что \1 так обозначается сгруппированная информация из сообщения собеседника. То, что у него в скобочках (). Если скобочек в регулярке собеседника несколько, то сгруппированную из них информацию в ответе ELIZA можно последовательно обозначать \1, \2 и т.д.
Например:
Я: Мне очень грустно и я хочу есть = [Мм]не (.*) и я? хочу (.*)
ELIZA: Может, тебе очень грустно из-за того, что ты хочешь есть? = Может, тебе \1 из-за того, что ты хочешь \2?

Всем спасибо
Напоминаю про задание мне можно писать сюда
Можно спрашивать туда же
Сдавать либо мне сюда, либо лично сдать бумажку (перед|после) заняти(ем|я)
tg @annaklezovich
[e-mail]