company_banner

Точка, точка, запятая: машинное обучение

    Как научить поисковую машину правильно разбивать текст на предложения? Сделать так, чтобы она могла распознавать точки, которые не являются концами предложений.

    Наша статья о машинном обучении объясняет одну из техник, которые применяются в поисковой машине тогда, когда возникает нужда в корректном разбиения текста на предложения. Решение такой задачи имеет принципиальное значение, например, при генерации сниппетов поисковыми системами или при построении базы контекстов словоупотребления. Сейчас эта технология встраивается в индексатор Поиска@Mail.Ru. Точность метода, по нашим наблюдениям — не менее 99%.
    О том, как это работает, читайте в нашей статье.

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

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

    Концы предложений могут обозначаться точками, знаками вопроса и восклицания, символами конца абзаца, многоточиями и, в отдельных случаях, двоеточиями. Основные проблемы создаёт символ точки, поскольку, он также используется в сокращениях и литеральных обозначениях – датах, шифрах, адресах электронной почты, web-адресах и т.п.

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

    Основной недостаток таблиц сокращений – то, что их нельзя применить к случаям нестандартных (авторских) сокращений. Кроме того, сокращения могут находиться в конце предложения, а некоторые из них, например, «и т.п.», «и др.» часто обозначают явный конец предложения (кстати, данное предложение является исключением).

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

    Но вывести правила, позволяющие автоматически различать знаки концов предложений более чем с 99% точностью, все-таки, можно.

    Наш метод
    Метод, который мы решили использовать для Поиска@Mail.Ru, заключается в создании небольшого набора базовых правил (порядка 40) и последующем автоматическом построении классификатора, опирающегося на результаты применения этих правил.

    Базовые правила делятся на два типа – подстановки и комбинации. Подстановки задаются регулярными выражениями и проверяют конкретные простые признаки контекста такие как, например, «пробелы справа» или «одна прописная буква слева» и т.п.

    Комбинации – это алгебраические конструкции, которые строятся из подстановок, например, «прописная буква слева» + «титул справа» (титул – слово, начинающееся с прописной буквы). Каждое из базовых правил, будучи примененным к конкретному контексту, возвращает число начисленных очков, обычно это 0, -1 или +1. Конечный результат вычисляется из вектора очков посредством специального классификатора.

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

    Об обучении: деревья принятия решений
    Подбор базовых правил происходил вручную, с помощью специально разработанного декларативного языка. Для построения классификатора мы использовали алгоритм машинного обучения на основе «деревьев принятия решений».

    Обучение шло последовательно, на документах разных типов – web-страницах, художественных и формальных текстах. Всего было отобрано около 10 тыс. эпизодов с отношением количества знаков-делителей предложений к знакам, не являющимся делителями, как 2 к 3. Для получения итоговой. 99%-процентной точности потребовалось шесть этапов обучения.

    Для первого этапа обучения данные готовились вручную: потребовалось рассмотрение порядка 1000 эпизодов. На каждом последующем этапе в список обучения добавлялись эпизоды, где классификатор «ошибался» или «сомневался».

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

    В результате проведенных экспериментов мы выяснили, что к наиболее значимым правилам относятся:

    • «Тип разделителя», 3 правила. Определяют соответственно точку, знак вопроса и знак восклицания;
    • «Пробелы справа/слева». Определяют наличие пробельных символов справа и слева от разделителя;
    • «Символ пунктуации справа/слева»;
    • «Цифра справа/слева»;
    • «Прописная/строчная буква справа/слева»;
    • «Открывающая/закрывающая скобка справа/слева»;
    • «Стандартные сокращения»;
    • «Неизвестные сокращения общего вида xxx.-xx. xx.» и т.д.

    Алгоритм построения классификатора


    Рисунок 1. Фрагмент дерева принятия решений.

    В качестве основы классификатора мы использовали «деревья принятия решений», широко применяемые в машинном обучении. Пример реального «дерева» из нашего классификатора показан на рисунке 1 (мы приводим фрагмент, так как всё «дерево» слишком велико).

    В «узлах» дерева находятся условия проверки правил. Запись вида «20 < 0.5» означает, что если правило №20 набрало менее 0.5 очков, то нужно перемещаться в левое поддерево, в противном случае — в правое.

    В «листьях дерева» хранятся оценки вероятности того, что делитель является концом предложения (чем больше значение, тем выше вероятность). В данном примере «дерево» принимает решения на основе следующих правил:
    • №0 — разделитель является точкой
    • №4 — пробелы справа
    • №7 — прописная буква слева
    • №18 — многоточие(+2 для первой точки, +1 для средних, -1 для последней)
    • №20 — титул справа (титул — слово, записанное с прописной буквы).
    К сожалению, одно «дерево» не может обеспечить приемлемое качество классификации, поэтому в качестве классификатора мы используем комбинацию нескольких сотен относительно простых деревьев.

    Каждое «дерево» строится так, чтобы максимально компенсировать ошибку работы остальных «деревьев» классификатора (такой подход известен в специальной литературе под названием boosting). Дополнительно для улучшения качества работы классификатора в целом мы использовали технику bootstrapping, где для построения каждого «дерева» используется случайное подмножество обучающего множества, меняющееся от «дерева» к «дереву». Полученные таким образом композитный классификатор показывает значительно лучшее качество работы, чем отдельно взятое «дерево».

    Пример вывода размечающей программы для случайного набора фраз
    Внутри тэгов sn находятся целые предложения:
    <sn>Погода в тот день была "хорошей".</sn><sn>There is no silver bullet. </sn><sn>А. С. Пушкин - великий русский поэт. </sn><sn>Ф. М. Достоевский жил в не самое простое для России время. </sn><sn>Началом эпохи Unix считается 01. 01. 1970. </sn><sn>Василий Пупкин был назначен и. о. генерального менеджера 11.06.1999. </sn><sn>Его почтовый адрес v.pupkin@nowhere.ru.com, личная страничка здесь - nowhere.ru.com/pupkin.html - теперь все знают, как с ним связаться. </sn>
    * This source code was highlighted with Source Code Highlighter.

    В таблице приведены оценки, сделанные классификатором. Порог отсечения (равный 0,64) выбирался методом наименьших квадратов для оценок, полученных по обучающей выборке. Смещение порога объясняется несимметричностью обучающей выборки относительно числа случаев, когда знак является разделителем и когда не является.
    Решение: Контекст (разделяющий знак находится в центре): Оценка:
    да `в тот день была "хорошей". There is no silver bulle' 1,000
    да `There is no silver bullet. А. С. Пушкин — великий р' 0,734
    нет `re is no silver bullet. А. С. Пушкин — великий русс' -0,002
    нет `is no silver bullet. А. С. Пушкин — великий русский' 0,003
    да `ин — великий русский поэт. Ф. М. Достоевский жил в ' 0,972
    нет `- великий русский поэт. Ф. М. Достоевский жил в не ' -0,002
    нет `еликий русский поэт. Ф. М. Достоевский жил в не сам' 0,003
    да ` простое для России время. Началом эпохи Unix счита' 1,000
    нет `м эпохи Unix считается 01. 01. 1970. Василий Пупкин' 0,460
    нет `охи Unix считается 01. 01. 1970. Василий Пупкин был' 0,489
    да `ix считается 01. 01. 1970. Василий Пупкин был назна' 0,500
    нет `лий Пупкин был назначен и. о. генерального менеджер' 0,184
    нет ` Пупкин был назначен и. о. генерального менеджера 1' 0,050
    нет `генерального менеджера 11.06.1999. Его почтовый адр' -0,001
    нет `ерального менеджера 11.06.1999. Его почтовый адрес ' -0,001
    да `ного менеджера 11.06.1999. Его почтовый адрес v.pup' 0,500
    нет `999. Его почтовый адрес v.pupkin@nowhere.ru.com, ли' -0,055
    нет `ый адрес v.pupkin@nowhere.ru.com, личная страничка ' 0,000
    нет `адрес v.pupkin@nowhere.ru.com, личная страничка зде' 0,001
    нет `ка здесь — nowhere.ru.com/pupkin.html — тепе' 0,000
    нет `здесь — nowhere.ru.com/pupkin.html — теперь ' -0,001
    нет `p://nowhere.ru.com/pupkin.html — теперь все знают, ' -0,001
    да `нают, как с ним связаться.' 0,972

    А что у нас?
    В настоящий момент технология машинного обучения по корректной разбивке текстов на предложения встраивается в индексатор нашей поисковой системы. Это внедрение обещает улучшить качество сниппетов в Поиске@Mail.Ru, а также позволит правильнее определять контекст, в котором употребляется слово — что в свою очередь повысит релевантность поисковой выдачи.

    Внеклассное чтение
    Для более глубокого знакомства с алгоритмами машинного обучения мы рекомендуем вам книгу T.Hastie, R.Tibshirani, J.H.Friedman «The elements of statistical learning», которая доступна on-line.

    С уважением,
    Команда Поиска@Mail.Ru
    • +26
    • 16,3k
    • 8
    Mail.ru Group
    813,00
    Строим Интернет
    Поделиться публикацией

    Комментарии 8

      +3
      Спасибо. Интересно.
      А какой у вас объем обучающей/проверочной выборки? И, собственно, откуда набор данных? Сами размечали?

      А какие признаки из html вы используете? Вряд ли система предназначена для работы на plain-text.
        +3
        Объем начальной выборки приблизительно 1000 эпизодов, размечались тексты вручную. Обучались на всём подряд — различные сырые HTML-страницы, простой текст. Последующие выборки строились инкрементально: прогоняем случайный текст, отбираем те случаи, когда решение затруднено, затем эти случаи добавляются частично в обучающий, и частично в проверочный наборы. Всего потребовалось 6 таких итераций, накопленное суммарное количество эпизодов порядка 10 000.
          +1
          Спасибо.
        +3
        Спасибо, интересная информация. Как раз изучаю данную тематику.
          0
          А как с производительностью такого алгоритма при объемах обработки, свойственных поисковой системе?
            0
            Вообще, деревья решений – один из самых быстрых алгоритмов. Должен справляться )
            А если не хочется писать свою реализацию этого алгоритма, в opennlp, например, есть компонент Sentence Detector, использующий Maximum Entropy Model. Его можно обучить для русского языка.

            sourceforge.net/apps/mediawiki/opennlp/index.php?title=Sentence_Detector
              0
              Как показывает практика, вычислительная нагрузка в связи с использованием такого подхода ощутимо возрастает, но не по вине дерева решений. Профилирование показало, что проблемы возникают с регулярными выражениями, применяемыми к левым контекстам: в отдельных случаях сложность алгоритма получается квадратичной. Одним из путей решения может быть замена подобных регулярных выражений обратными (работающими справа налево). В худшем случае, представленный метод может быть применен для обучения более быстрых, но менее интуитивно понятных моделей, поскольку обучающую выборку можно сделать сколь угодно большой, без участия ассессоров.
              0
              Спасибо, очень своевременная статья, т.к в данный момент пытаемся решить похожую задачу.

              Скажите, пожалуйста, как именно называется этот алгоритм, чтобы о нём можно было подробнее почитать в книжках, подобных той, что вы указали. Это какая-то модификация ID3?

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

              Самое читаемое