Один из перспективных подходов в машинном обучении базируется на запоминании уже разобранных примеров и поиске похожего образца. Например, у нас уже есть коллекция расшифрованных аудиозаписей, и если появляется новый звуковой файл, мы ищем похожий образец и на его основе строим распознавание. Рассмотрим, как базируясь на этом принципе, можно построить морфологию русского языка.
В большинстве случаев словоформа образуется за счет изменения суффикса слова. При этом в простейшем случае правило, согласно которому будет определяться нормальная форма, задается тройкой (n,newsuffix,morphinfo), где
Словарь с проекта AOT содержит около 5 миллионов словоформ, по которым строится порядка 30 тысяч правил для определения нормальной формы слова. Собственно, это и есть те самые обработанные результаты, столь необходимые для построения нашего алгоритма. При этом на первый взгляд кажется, что для нахождения нужного правила необходимо хранить все 5 миллионов словоформ. В действительности это не так.
Попробуем построить эвристику для нахождения нормальной формы слова, которая в тоже время поможет уменьшить количество хранимой информации. Для этого будем использовать следующую закономерность: чем более длинный общий суффикс имеют два слова, тем с большей вероятностью у них будет одинаковое правило для формирования нормальной формы.
Поступим следующим образом: отсортируем все словоформы в лексографическом порядке перевернутых слов. Например, для слов а, оружие, сторона, море верным будет такой порядок: а, сторона, оружие, море. Мы получаем следующую закономерность: слова, находящиеся после сортировки рядом, будут с большей вероятностью иметь одинаковое правило. Теперь удалим из нашего списка все слова, правила которых совпадают с правилом предшествующего ему слова. В нашем распоряжении останется около 500 тысяч слов, то есть мы смогли сократить объем хранимой информации в 10 раз. Таким образом, чтобы получить нормальную словоформу для какого-либо слова, нам необходимо найти наибольшее слово из оставшегося списка, не превосходящее данное и применить правило от него. Данный алгоритм будет корректно работать для всех слов из словаря и даст хорошую эвристику для незнакомых примеров. Этот подход был использован и для добавления поддержки русского языка в lucene.
Также для уменьшения объема занимаемой информации мы можем произвести дополнительное кодирование, при котором шесть подряд идущих букв представляются как 32-хбитный int. Таким образом, список образцов, по которым производится поиск нужного правила, представляется как двухмерный массив чисел, в котором одна строка соответствует одному слову. Для нахождения нужного образца необходимо использовать бинарный поиск. Скорость данного алгоритма составляет порядка 200 тысяч слов в секунду. Кроме того, возможны дальнейшие улучшения: например, использование префиксного дерева для хранения и поиска информации. Но это уже тема для следующего разговора.
В большинстве случаев словоформа образуется за счет изменения суффикса слова. При этом в простейшем случае правило, согласно которому будет определяться нормальная форма, задается тройкой (n,newsuffix,morphinfo), где
- n — длина суффикса, который нужно отбросить;
- newsuffix — новый суффикс, добавление которого даст нормальную форму;
- morphinfo — морфологическая информация (например, падеж, род и т.д.).
Словарь с проекта AOT содержит около 5 миллионов словоформ, по которым строится порядка 30 тысяч правил для определения нормальной формы слова. Собственно, это и есть те самые обработанные результаты, столь необходимые для построения нашего алгоритма. При этом на первый взгляд кажется, что для нахождения нужного правила необходимо хранить все 5 миллионов словоформ. В действительности это не так.
Попробуем построить эвристику для нахождения нормальной формы слова, которая в тоже время поможет уменьшить количество хранимой информации. Для этого будем использовать следующую закономерность: чем более длинный общий суффикс имеют два слова, тем с большей вероятностью у них будет одинаковое правило для формирования нормальной формы.
Поступим следующим образом: отсортируем все словоформы в лексографическом порядке перевернутых слов. Например, для слов а, оружие, сторона, море верным будет такой порядок: а, сторона, оружие, море. Мы получаем следующую закономерность: слова, находящиеся после сортировки рядом, будут с большей вероятностью иметь одинаковое правило. Теперь удалим из нашего списка все слова, правила которых совпадают с правилом предшествующего ему слова. В нашем распоряжении останется около 500 тысяч слов, то есть мы смогли сократить объем хранимой информации в 10 раз. Таким образом, чтобы получить нормальную словоформу для какого-либо слова, нам необходимо найти наибольшее слово из оставшегося списка, не превосходящее данное и применить правило от него. Данный алгоритм будет корректно работать для всех слов из словаря и даст хорошую эвристику для незнакомых примеров. Этот подход был использован и для добавления поддержки русского языка в lucene.
Также для уменьшения объема занимаемой информации мы можем произвести дополнительное кодирование, при котором шесть подряд идущих букв представляются как 32-хбитный int. Таким образом, список образцов, по которым производится поиск нужного правила, представляется как двухмерный массив чисел, в котором одна строка соответствует одному слову. Для нахождения нужного образца необходимо использовать бинарный поиск. Скорость данного алгоритма составляет порядка 200 тысяч слов в секунду. Кроме того, возможны дальнейшие улучшения: например, использование префиксного дерева для хранения и поиска информации. Но это уже тема для следующего разговора.
