Автозамена
Автокоррекция в обработке естественного языка (NLP) относится к функции или алгоритму, который автоматически исправляет или предлагает исправления ошибок или ошибок при вводе текста. Автозамена обычно используется в таких приложениях, как обмен сообщениями, обработка текстов и поисковые системы, чтобы помочь пользователям исправлять орфографические ошибки, опечатки и грамматические ошибки.
Автозамена в НЛП обычно включает несколько шагов, в том числе:
- Обнаружение ошибок: алгоритм НЛП выявляет потенциальные ошибки во входном тексте, такие как слова с ошибками, повторяющиеся буквы или другие распространенные ошибки.
- Генерация кандидатов: алгоритм генерирует список возможных исправлений для каждой ошибки, учитывая близлежащие слова, контекст и общеупотребительные языковые шаблоны.
- Ранжирование кандидатов: алгоритм ранжирует сгенерированные исправления на основе таких факторов, как частота появления, сходство с входным словом и контекст.
- Предложение по исправлению: первое исправление для каждой ошибки представляется пользователю в качестве предложения, которое может быть применено автоматически или выбрано пользователем вручную.
- Отзывы пользователей: система автозамены также может собирать отзывы пользователей, например, когда исправление принимается или отклоняется, чтобы со временем повысить свою точность.
Автозамена в NLP обычно обучается на больших наборах текстовых данных, включая правильные и неправильные текстовые пары, для изучения закономерностей и внесения точных исправлений. Он также может включать методы машинного обучения, такие как системы на основе правил, статистические модели или алгоритмы глубокого обучения, чтобы повысить его точность и адаптировать к различным языкам, диалектам и стилям письма.
Построение модели
1. Определите слово с ошибкой
При выявлении слова с ошибкой можно проверить, есть ли оно в словаре. Если он не найден, вероятно, это опечатка.
2. Найдите строки на расстоянии редактирования
3. Отфильтруйте кандидатов
На этом шаге вы хотите взять все слова, созданные выше, а затем сохранить только фактические слова, которые имеют смысл и которые вы можете найти в словаре.
4. Расчет вероятностей слов
Обратите внимание, что вы сохраняете количество слов, а затем можете использовать его для построения вероятностей. Если вы хотите создать немного более сложную автозамену, вместо этого вы можете использовать два слова, идущие рядом. Вы можете использовать предыдущее слово, чтобы решить позже. Например, какое сочетание более вероятно, друг или их друг?
Минимальное расстояние редактирования
Минимальное расстояние редактирования позволяет:
- Оценить сходство между двумя строками
- Найдите минимальное количество правок между двумя строками
- Реализуйте исправление орфографии, сходство документов, машинный перевод, секвенирование ДНК и многое другое.
Помните, что изменения включают:
- Вставить (добавить букву) «до»: «сверху», «два»…
- Удалить (удалить букву) ‘шапка’: ‘ха’, ‘ат’, ‘хт’
- Заменить (заменить 1 букву на другую) «челюсть»: «баночка», «лапа», …
Вот конкретный пример, где мы вычисляем стоимость (т.е. расстояние редактирования) между двумя строками.
Чем больше ваши строки, тем сложнее вычислить минимальное расстояние редактирования. Поэтому теперь необходимо использовать алгоритм минимального расстояния редактирования!
Алгоритм минимального расстояния редактирования
Алгоритм минимального расстояния редактирования (MED), также известный как расстояние Левенштейна или расстояние редактирования, представляет собой метод, обычно используемый в обработке естественного языка (NLP) для вычисления сходства или различия между двумя последовательностями. Он измеряет количество односимвольных правок (вставок, удалений или замен), необходимых для преобразования одной строки в другую.
Алгоритм MED широко используется в различных задачах NLP, таких как проверка орфографии, выравнивание последовательности ДНК и измерение сходства текста. Это может быть реализовано с помощью динамического программирования, которое является эффективным способом расчета MED между двумя последовательностями.
При вычислении минимального расстояния редактирования вы должны начать с исходного слова и преобразовать его в целевое слово. Давайте посмотрим на следующий пример:
Чтобы перейти от #→#, вам нужна стоимость 0. От p→# вы получите 1, потому что это стоимость удаления. p→s равно 2, потому что это минимальная стоимость, которую можно использовать, чтобы перейти от p к s. Вы можете продолжать в том же духе, заполняя по одному элементу за раз, но оказывается, что есть более быстрый способ сделать это!
Есть три уравнения:
- D[i,j] = D[i-1, j] + del_cost: это указывает на то, что вы хотите заполнить текущую ячейку (i,j), используя стоимость в ячейке, найденной непосредственно выше.
- D[i,j] = D[i, j-1] + ins_cost:это указывает на то, что вы хотите заполнить текущую ячейку (i,j), используя стоимость в ячейке, найденную непосредственно в ее левый.
- D[i,j] = D[i-1, j-1] + rep_cost:стоимость репутации может быть 2 или 0 в зависимости от того, собираетесь ли вы ее заменить или нет.
На каждом временном шаге вы проверяете три возможных пути, по которым вы можете прийти, и выбираете наименее дорогой. Когда вы закончите, вы получите следующее:
Подводя итог, вы видели расстояние Левенштейна, которое определяет стоимость операции. Если вам нужно восстановить путь перехода от одной строки к другой, вы можете использовать обратную трассировку. Вы должны держать простой указатель в каждой ячейке, сообщающий, откуда вы пришли, чтобы туда попасть. Итак, вы знаете путь, пройденный через стол из верхнего левого угла в нижний правый угол. Затем вы можете реконструировать его.
Этот метод вычислений вместо грубой силы называется методом динамического программирования. Сначала вы решаете наименьшую подзадачу, а затем, повторно используя этот результат, решаете следующую по величине подзадачу, сохраняете этот результат, повторно используете его снова и так далее. Это именно то, что вы сделали, заполнив каждую ячейку от верхнего правого до нижнего левого. Это хорошо известная техника в компьютерных науках!
Вот базовый псевдокод для алгоритма минимального расстояния редактирования:
function minimum_edit_distance(str1, str2):
m = length of str1
n = length of str2
Initialize a 2D array D with dimensions (m+1) x (n+1) and set D[0][0] = 0
for i from 1 to m:
D[i][0] = i
for j from 1 to n:
D[0][j] = j
for i from 1 to m:
for j from 1 to n:
if str1[i-1] == str2[j-1]:
cost = 0
else:
cost = 1
D[i][j] = minimum of (D[i-1][j] + 1), (D[i][j-1] + 1), (D[i-1][j-1] + cost)
return D[m][n]
В этом псевдокоде str1 и str2 являются входными строками, для которых необходимо вычислить MED. Алгоритм использует двумерный массив D для хранения промежуточных результатов. Внешний цикл перебирает символы строки str1, а внутренний цикл перебирает символы строки str2. Алгоритм вычисляет стоимость каждой операции редактирования (вставки, удаления или замены) и сохраняет минимальную стоимость в D[i][j]. Наконец, значение в D[m][n] представляет минимальное расстояние редактирования между str1 и str2.
Алгоритм MED имеет временную сложность O(mn), где m и n — длины входных строк, а также пространственную сложность O(mn), поскольку требует сохранения промежуточных результатов в двумерном массиве. Однако существуют оптимизированные версии алгоритма, которые могут уменьшить объем памяти до O(min(m, n)), если проблема связана с использованием памяти.
Ссылка
Юнес Бенсуда Мурри, Обработка естественного языка с классификацией и векторными пространствами
DeepLearning.AI делает эти слайды доступными для образовательных целей. Вы не можете использовать или распространять эти слайды в коммерческих целях. Вы можете делать копии этих слайдов и использовать или распространять их в образовательных целях, если вы указываете DeepLearning.AI в качестве источника слайдов.
Остальные сведения о лицензии см.
