Превью

Здравствуй, Хабр! 25-го апреля 2016 года закончилось 3-х месячное напряженное соревнование Home Depot Product Search Relevance в котором нашей команде Turing Test (Igor Buinyi, Kostiantyn Omelianchuk, Chenglong Chen) удалось не только неплохо разобраться с Natural Language Processing и ML, но и занять 3-е место из 2125 команд. Полное описание нашего решения и код доступны тут, краткое интервью тут, а цель этой публикации не только рассказать о решении, которое принесло нам такой результат, но и о тех трудностях и переживаниях, через которые нам довелось пройти во время соревнования.

Как чуден и глубок русский курлык
— Генератор постов

Обработка естественного языка (natural language processing, NLP) — тема, на мой взгляд, очень интересная. Во-первых, задачи тут чисто алгоритмические: на вход принимаем совершенно примитивный объект, строчку, а извлечь пытаемся вложенный в него смысл (ну или хотя бы частичку смысла). Во-вторых, необязательно быть профессиональным лингвистом, чтобы решать эти задачи: достаточно знать родной язык на более-менее приличном уровне и любить его.

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

Бессвязность текстов в нынешней версии «Генератора» вызвана тем, что на самом деле никакого анализа он производить не умеет. Просто в одних случаях «предсказывает» продолжение предложения по собранным биграммам, а в других — заменяет в готовом предложении некоторые слова на другие, которые заканчиваются похоже. Вот и вся начинка.

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

В первой части статьи мы рассмотрели универсальный автомат Левенштейна — мощный инструмент для фильтрации слов, отстоящих от некоторого слова W на расстояние Левенштейна не более заданного. Теперь пришло время изучить способы применения этого инструмента для эффективного решения задачи нечеткого поиска в словаре.

Нечеткий поиск строк является весьма дорогостоящей в смысле вычислительных ресурсов задачей, особенно если вам необходима высокая точность получаемых результатов. В статье описан алгоритм нечеткого поиска в словаре, который обеспечивает высокую скорость поиска при сохранении 100% точности и сравнительно низком потреблении памяти. Именно автомат Левенштейна позволил разработчикам Lucene повысить скорость нечеткого поиска на два порядка

Известные ParserCombinator'ы и Parboiled предназначены исключительно для разбора формальных языков. Мы же решаем задачу разбора естественного языка и при этом хотим, чтобы с помощью той же грамматики можно было осуществлять синтез фраз на естественном языке, отражающих требуемую нам семантику. Было бы удобно иметь возможность описывать языковые конструкции вместе с правилами абстрагирования/конкретизации.

Например,

1. Преобразование числительных в число («десять» -> 10:Int)
2. и обратно (10:Int -> «десять» («десятый», «десяток» ...))
3. Преобразование числительных вместе с единицей измерения («десять рублей» <-> NumberWithMeasurement(10, RUB))
4. Неполный адрес («ул. Яблочная» <-> Address(street=«Яблочная»))
5. Адрес в пределах города («улица Яблочная дом сто двадцать три квартира сорок пять» <-> Address(street=«Яблочная», building=123, flat=45))
6. Телефон (256-00-21 («двести пятьдесят шесть ноль ноль двадцать один») <-> NumericalSequence(256,0,0,21))

Причём хотелось бы иметь следующие системные свойства:

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

Под катом — описание подхода, реализованного в библиотеке synapse-typed-expressions. Рассмотрены только числительные, но подход естественным образом распространяется на другие вышеупомянутые формальные языковые конструкции.

В прошлой статье мы уже рассказывали о новой NLP библиотеке. Однако тогда мы рассказали «обовсем» и не о чем конкретном. Сегодня мы поговорим о теоретических аспектах разбития предложения на токены лингво-независимыми алгоритмами. Теоретические выкладки будут подкреплены практической реализацией в библиотеке AIF. Поехали…

Введение

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

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

Для более четкого понимания представьте себя слепым и глухим. И, даже родись в таком состоянии, вы бы могли взаимодействовать с миром и освоить язык. Само собой, что ваше представление о мире было бы иным, нежели у всех вокруг. Но вы могли бы все таким же образом взаимодействовать с миром. Некому бы было объяснить Вам что происходит и что такое язык ив се же, как то, тактильно анализирую шрифт Брайля Вы бы понемного сдвинулись с мертвой точки.

А это значит, что для понимания сообщения на каком-либо языке нам не нужно ничего, кроме самого сообщения. При условии, что это сообщение достаточно большое. Именно эта идея и положена в основу библиотеки под названием AIF. За деталями прошу пожаловать под кат.

Привет, меня зовут Наталья, я работаю в Яндексе разработчиком в группе извлечения фактов. Весной мы рассказали о том, что такое Томита-парсер и для чего он используется в Яндексе. А уже этой осенью исходники парсера будут выложены в открытый доступ.

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

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

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

Лекция рассчитана на старшеклассников — студентов Малого ШАДа, но и взрослые смогут с ее помощью восполнить некоторые пробелы.

http://video.yandex.ru/users/e1coyot/view/4/

В далеком 2009 году на хабре уже была статья "Кузявые ли бутявки.." про pymorphy — морфологический анализатор для русского языка на Python (штуковину, которая умеет склонять слова, сообщать информацию о части речи, падеже и т.д.)

В 2012м я начал потихоньку делать pymorphy2 (github, bitbucket) — думаю, самое время представить эту библиотеку тут: pymorphy2 может работать в сотни раз быстрее, чем pymorphy (втч без использования C/C++ расширений) и при этом требовать меньше памяти; там лучше словари, лучше качество разбора, лучше поддержка буквы ё, проще установка и более «честный» API. Из негатива — не все возможности pymorphy сейчас реализованы в pymorphy2.

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

Sentiment analysis (по-русски, анализ тональности) — это область компьютерной лингвистики, которая занимается изучением мнений и эмоций в текстовых документах. Недавно на хабре появилась статья про использование машинного обучения для анализа тональности, однако, она была настолько плохо составлена, что я решил написать свою версию. Итак, в этой статье я постараюсь доступно объяснить, что такое анализ тональности, и как реализовать подобную систему для русского языка.

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

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

"Мама мыла раму":

(предложение
    (именная гр. (сущ мама))
    (глаг. гр. (глаг мыла)
        (именная гр. (сущ раму)))
    (. .)))

Это называется синтаксическим деревом предложения. В графическом виде его можно представить следующим образом (в упрощенном виде):

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

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

Зачем это нужно? Например, для автоматического определения тегов для блог-поста (для отбора существительных). Морфологическая разметка является одним из первых этапов компьютерного анализа текста.

(Части 1, 2, 3) В четвёртой части мы поговорим о проверке грамматики за пределами токенизированных передложений.

Как уже упоминалось, разбиение предложения на токены и POS-разметка уже позволяют создать простой инструмент проверки грамматической корректности текста. По крайней мере, LanguageTool плагин к Open Office работает именно так. Очевидно, что массу ошибок можно выловить на уровне размеченных токенов. Однако также очевидно, что не менее обширные классы ошибок остаются за пределами возможностей нашего модуля. Взять хотя бы такую простую вещь как согласование подлежащего и сказуемого: «дама любил собак», «любил собак дама», «собак дама любил»… как составить паттерн для правила «сказуемое должно иметь тот же род, что и подлежащее?» Даже для английского языка с более-менее чётким порядком слов это трудно, говорить о русском и вовсе не приходится.

(Часть 1, Часть 2) В прошлый раз я преждевременно упомянул токенизацию; теперь можно поговорить и о ней, а заодно и о маркировке частей речи (POS tagging).

Предположим, мы уже выловили все ошибки (какие догадались выловить) на уровне анализа текста регулярными выражениями. Стало быть, пора переходить на следующий уровень, на котором мы будем работать с отдельными словами предложения. Разбиением на слова занимается модуль токенизации. Даже в столь простой задаче есть свои подводные камни. Я даже не говорю о языках вроде китайского и японского, где даже вычленение отдельных слов текста нетривиально (иероглифы пишут без пробелов); в английском или в русском тоже есть над чем подумать. Например, входит ли точка в слово-сокращение или представляет собой отдельный токен? («др.» — это один токен или два?) А имя человека? «J. S. Smith» — сколько здесь токенов? Конечно, по каждому пункту можно принять волевое решение, но в дальнейшем оно может привести к различным последствиям, и это надо иметь в виду.

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

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

Начнём с того, что текст можно рассматривать с двух точек зрения: либо как простую последовательность слов, пробелов и знаков препинания, либо как сеть связанных между собой синтактико-семантическими зависимостями понятий. Скажем, в предложении «я люблю больших собак» можно расставить слова в любом порядке, при этом структура связей между словами будет одна и та же:

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

На сей раз появился новый повод поговорить об обработке текстов (natural language processing то бишь). Я разрабатываю модуль проверки правописания для одной конторы. На выходе должна получиться функциональность, аналогичная встроенной в MS Word, только лучше :) Не могу пока назвать себя крупным специалистом в этой области, но стараюсь учиться. В заметках постараюсь рассказать о том, куда движется наш проект, как устроен тот или иной этап обработки текста. Может, в комментариях услышу что-нибудь новое/интересное и для себя. Если проекту с этого будет польза — прекрасно. Как минимум, устаканю данные у себя в голове, а это тоже неплохо.

(Первые части: 1 2 3 4 5 6 7 8 9). Как говорилось в известной рекламе, «вы не ждали, а мы пришли» :)

За время, прошедшее после публикации девятой части, я прочитал одну хорошую книжку по теме (в to-read списке ещё парочка), множество статей, а также пообщался с несколькими специалистами. Соответственно, накопился новый объём материала, заслуживающий отдельной заметки. Как обычно, знакомлю других, параллельно структурирую знания для себя.

Сразу прошу прощения: эта часть для чтения и понимания достаточно трудна. Ну да, как говорится, не всё коту масленица. Сложным задачам соответствуют сложные тексты :)

(Первые части: 1 2 3 4 5 6 7 8). Да возрадуются минусующие, сегодня представляю вниманию читателей последнюю, по всей видимости, часть «Заметок». Как и предполагалось, мы поговорим о дальнейшем семантическом анализе; также я порассуждаюю немного о том, чем в принципе можно заняться в нашей области и какие есть трудности «научно-политического» характера.

(Первые части: 1 2 3 4 5 6 7). В этой части я расскажу о синтактико-семантическом анализаторе — как я его вижу. Обратите, кстати, внимание на часть 7 — она до главной страницы не добралась, так что не уверен, что все интересующиеся её видели.