Page 1 of 1

Питон BIG DATA (лингвиста, статиста, ... )

Posted: Thu, 5 Nov 2015, 18:27:33
by dyvniy
pymorphy и pymystem
http://habrahabr.ru/post/176575/
Spoiler
pymorphy2
Алгоритмы*, Python*
В далеком 2009 году на хабре уже была статья "Кузявые ли бутявки.." про pymorphy — морфологический анализатор для русского языка на Python (штуковину, которая умеет склонять слова, сообщать информацию о части речи, падеже и т.д.)

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

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



Какие были проблемы у pymorphy:

достаточно медленная скорость работы (несколько сотен слов/сек при установке по умолчанию);
зависимость от словарей с aot.ru, которые непонятно как пополнять / исправлять;
некоторые проблемы с API — например, по API для склонятора могло показаться, что библиотека сама снимает неоднозначность разбора, хотя это и не так;
буква ё поддерживалась способом «везде заменить все ё на е»;
достаточно сложная установка — нужно качать словари, какие-то разные форматы и т.д. (даже на японском кто-то серию видеоуроков сделал);
Python 3.x поддерживался только в версии с bitbucket, которая так и не была выпущена в свет;
невозможно склонять инфинитив: глагол было можно поставить в форму инфинитива, а обратно — уже нет;
слова, записанные через дефис, склонялись не всегда правильно;
ну и т.д.


До того, как сделать pymorphy, я ни на Python не писал никогда, ни обработкой текстов на естественном языке не занимался (pymorphy был способом поразбираться и в том, и в другом) — вполне понятно, что там многое можно было сделать лучше.

Но многое в pymorphy1 было все-таки сделано правильно. Например, документация на русском и установка без особых зависимостей (главное — без необходимости в компиляторе); более-менее нормальный процесс разработки с тестами; само качество разбора и предсказания было достаточно высоким. Интеграция с django была тоже хорошим «маркетинговым» ходом — с ней, правда, были некоторые концептуальные проблемы (нельзя правильно просклонять слово прямо в шаблоне, не разрешив неоднозначность разбора — а это в API никак предусмотрено не было).

Несмотря на все свои недостатки, библиотека (неожиданно) оказалась довольно востребованной — например, нагуглил, что pymorphy был слегка использован при разработке системы Speech-to-Text для русского языка в рамках французского проекта Quaero, и рекомендуется в качестве учебного материала в некоторых ВУЗах. Не думаю, что тут какая-то большая моя заслуга, скорее просто оказался в нужном месте в нужное время.

Я долго не хотел ломать обратную совместимость и пытался развивать то, что есть (хотя buriy, например, даже форк сделал, который ломал обратную совместимость, но работал быстрее). Решающим толчком к написанию pymorphy2 послужил проект OpenCorpora — ребята оттуда, кроме всего прочего (а там много «всего прочего»), взяли словарь из aot.ru, полностью переделали его структуру и занялись пополнением и прочими улучшениями.

Итак, появилась идея использовать словарь из OpenCorpora.

В pymorphy использовались словари из aot.ru, почти никак не обработанные (они переводились в формат sqlite, но по сути структура оставалась та же). Отдельно хранились «основы» слов, отдельно «приставки», отдельно «окончания», и отдельно — правила образования слов из этих частей. Этот способ был хорош тем, что на его основе удалось реализовать морфологический анализатор за пару «уикендов» без особых усилий и исследований.

Но все это — доступ к данным через множество оберток и (особенно) сбор слов из частей питоньим кодом — негативно сказывалось на скорости работы; как-то радикально улучшить скорость у меня при таком подходе не получалось, решения были сложные и не особо помогали (примечание: вариант «переписать все как есть, но на C++» работает быстро, но требует больше памяти, чем в pymorphy2 в итоге получилось).

Короче говоря, в pymorphy2 я захотел попробовать какой-то другой подход, раз уж словари новые, и все равно многое, связанное со словарями, переписывать. При этом хотелось, чтоб pymorphy2 остался питоньей библиотекой, а не просто оберткой к куче С/С++ кода — хотелось, чтоб логика разбора так и осталась на питоне. Было несколько вариантов, что делать.

Автоматы-автоматы

Первый вариант, который приходил на ум — переформулировать задачу в терминах конечных автоматов. lightcaster хорошо описал подход тут: habrahabr.ru/post/109736/. Подход красивый, что есть то есть.

Что меня тут смутило:

а) в статье ипользовалась C++ библиотека OpenFST (вроде самый популярный способ реализации конечных автоматов), но заставлять пользователей ставить ее вручную — не вариант;
б) даже с использованием C++ библиотеки результаты, судя по статье, были достаточно скромные (2 тыс слов/сек против 100+ тыс слов/сек у mystem или lemmatizer); понятное дело, что эту цифру можно было бы, скорее всего, значительно улучшить (да и lightcaster пишет, что ничего не оптимизировал) — но все же;
в) это один из тех подходов, который (по моему мнению) повышает порог вхождения — я считаю, что это скорее минус.

В итоге получалось, что мне нужно было бы: разобраться, как оптимизировать код и почему даже с C++ библиотекой получается так медленно; написать более простую в установке обертку для OpenFST (или использовать другую реализацию FST — например, сделать свою) + сделать реализацию небольшой части OpenFST (или просто реализацию FST) на Python (чтоб pymorphy можно было использовать без компилятора), ну и формулировать все алгоритмы в терминах конечных автоматов.

Несколько лет назад lightcaster присылал мне еще набросок реализации pymorphy на конечных автоматах (питоний, без C расширений, я в нем ничерта тогда не понял :) — набросок в итоге работал со скоростью тоже около 2тыс слов/сек и требовал около 300Мб памяти. Все это, с одной стороны, неплохо, но с другой — не очень вдохновляло все-таки; было ясно, что если решать этим методом «в лоб», то будет работать не очень-то и быстро, и что нужно писать сильно лучше, чем человек, в теме разбирающийся. Короче, показалось, что это много работы и негарантированный результат (+ еще другие соображения архитектурного характера, ближе к концу статьи будут). Возможно, и неправильно показалось, кто знает — я ж не пробовал, отговорки только.

Этим путем (рассматривать задачу исключительно как задачу об автоматах) я не пошел. Хотя — как сказать, все зависит от точки зрения :)

Скопируем-ка mystem

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

Суть метода (как я его понял)

Trie

В методе используются префиксные деревья (Trie) — чтоб реализовать метод, нужна реализация Trie для Python. Мне не хотелось использовать питонью реализацию (я опасался за скорость и прожорливость по памяти), а готовых python-оберток к какой-нибудь хорошей C/C++ реализации Trie я, к удивлению, не нашел.

Писать свою C/C++ реализацию структур данных смысл бывает редко: на C/C++ очень много чего уже есть, и многие из библиотек реализуют state-of-art алгоритмы. Почему? Вот придумал человек хитрую структуру данных, написал об этом статью в научный журнал. Чтоб результаты можно было повторить, автор нередко выкладывает реализацию, и чаще всего — именно на C или C++. Если и не выкладывает, то кто-нибудь другой бумагу читает и пишет реализацию — тоже именно на C/C++ (ok, иногда еще на Java пишут такое).

Да и все-таки pymorphy2 — это хобби-проект, и тратить на него очень много времени не получилось бы; лучше было постараться расходовать время эффективно и изобретать поменьше велосипедов. Короче говоря, решил я взять готовую реализацию Trie и сделать для нее обертку на Cython (отдельным пакетом, никак не связанным с pymorphy2).

В этом подходе есть 2 больших плюса:

1) Структуру данных можно будет использовать и для других целей; даже если бы подход себя не оправдал (спойлер: так и вышло, он себя не оправдал), то усилия бы не были потрачены зря;
2) сложность, связанная со структурами данных, «утаскивается» из самого морфологического анализатора; анализатор общается с Trie через простой API, а сам занимается только собственно разбором слов. Чтоб понять алгоритм работы, не нужно детально разбираться в том, как устроено префиксное дерево. Кроме того, замена реализации базовых структур данных (например, на питонью) — задача простая; у нас есть четко выраженная граница (=интерфейс) между морф. анализатором и хранилищем для слов.

Сперва мне приглянулась библиотека libdatrie, про обертку для нее писал тут: habrahabr.ru/post/147963/. Некоторые вещи в библиотеке пришлось поправить (обычно выходило так — я писал рабочую реализацию на C, автор библиотеки все выкидывал и писал более идиоматичный C код для того же самого — и правильно делал, т.к. C-код у него и правда был лучше :); в итоге получилась вполне себе юзабельная обертка.

С datrie и подходом «укради все у mystem!» получалось 20-60тыс слов/сек (без предсказателя и с минимумом питоньей обвязки; почему такой разброс — не помню уже, погода, наверное), и занимало это все около 30Мб памяти.

Со скоростью затык был в неожиданном (для меня) месте: больше всего тормозило сопоставление допустимых разборов для «окончаний» слова и допустимых разборов для «начал» слов (это часть алгоритма). В моей реализации это сводилось к нахождению пересечения 2 отсортированных списков цифр. Очевидный способ («параллельно пройтись по обоим спискам») оказался в этой задаче гораздо медленней, чем подход «идти по короткому списку, а в длинном искать цифры сужающимся двоичным поиском». Но и этот второй вариант оставался узким местом, даже переписанный на Cython — что с ним делать, я не знал. Наверное, можно было этот код написать получше, но сразу не получилось.

Кроме того, 30Мб — это, с одной стороны, хорошо, а с другой — у aot.ru ведь меньше (то пишут, что 9Мб, то 19Мб — будем считать, что 9, у меня руки не дошли проверить). Потребление памяти — это важно, т.к. pymorphy используется еще и для стрельбы из пушки по воробьям (склонения слов на сайте), а это требует загружать его в каждый веб-процесс. Ну или если не загружать (из-за того, что памяти жалко), то городить огород с отдельным сервисом (на zeromq каком-нибудь, или с общением по http) — чего тоже не хочется.

Реализация datrie — это не «наивное» trie на указателях, datrie и так раза в 2 памяти меньше должен требовать, чем обычное префиксное дерево (так что 30Мб — это еще хорошо).

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

marisa-trie

Но я решил не сдаваться и не отказываться от подхода «a la mystem», а попробовать заменить datrie на что-то еще (что было довольно глупо, но имело хорошие последствия). Выбор пал на C++ библиотеку marisa-trie, которую написал гуру структур данных Susumu Yata. Для нее я тоже сделал python-обертку примерно с тем же интерфейсом, что и у datrie.

Когда я начал тестировать marisa-trie, у меня сперва глаза на лоб полезли. Смотрите:

если взять и загрузить все 3 миллиона русских слов в питоний словарь, это займет около 600Мб оперативной памяти (в list — около 300Мб);
если загрузить эти же данные в datrie, то это займет 70Мб RAM — что уже достаточно круто;
а если загрузить эти же данные в MARISA-Trie, то это займет еще в 10 раз меньше — 7Мб памяти.


Как так получается? Дело в том, что MARISA-Trie — это на самом деле вовсе не Trie :) Что это такое — я так по-нормальному и не разобрался; папка с «мясом» в исходниках называется grimoire; описание алгоритма — исключительно на японском.

Судя по всему, MARISA-Trie — это «succinct» реализация Patricia-Trie (wiki), в которой каждому узлу может сопоставляться не только текстовая информация, но и MARISA-Trie следующего уровня. «Succinct» означает, что структура дерева закодирована битовым массивом, что позволяет тратить на нее очень мало памяти. Ну и там есть интересная особенность: MARISA Trie выступает сразу еще и в роли «perfect hash». Каждому ключу присваивается уникальный номер из диапазона 0 до len(trie)-1, и каждому числу от 0 до len(trie)-1 соответствует единственный ключ; можно как по номеру получить ключ, так и по ключу получить номер.

По скорости — datrie быстрее, чем marisa-trie, раз в 10.

Вернемся к pymorphy. После простой замены datrie на marisa-trie у меня получилось, что все хозяйство занимает 5Мб памяти, а работает со скоростью 2-5 тыс слов/сек (без предсказателя).

С одной стороны — 5Мб — это круто (хотя пока и без предсказателя). Но с другой — 2-5 тыс слов/сек — медленно после 20-60 тыс слов/сек, + жестко завязываться на marisa-trie не очень хотелось, т.к. это бы привело к требованию компилятора для установки pymorphy2. Я вполне понимал, как работает datrie, и написать совместимую питонью реализацию проблемой бы не стало, но marisa-trie… В случае с marisa-trie портировать было бы можно, но это бы потребовало больше усилий, и работало бы, скорее всего, мееедленно — этот вопрос бы, вероятно, «отложился», и pymorphy2 требовал бы компилятор для установки.

Сама по себе попытка была тупиковой, но выявила одну интересную вещь: 5Мб (алгоритм «почти mystem» + marisa-trie) и 7Мб («все слова целиком поместим в marisa-trie») — цифры очень даже сопоставимые. Эти цифры открыли мне наконец глаза на тот факт, что не стоит отбрасывать подходы, при которых все слова будут загружаться в память сразу и целиком (без разбиения на начала и концы).

Интуитивно: если все слова держать в памяти «как есть», то нужно будет делать меньше вычислений, слова не нужно будет собирать из кусочков — все должно работать быстрее, и код должен получиться проще.

На этом месте идеей «скопировать mystem» я заниматься прекратил; недоделанные варианты с datrie и marisa-trie доступны в ранних коммитах pymorphy2.

У меня есть подозрение, что в mystem используется (ну согласно публикации, я не могу знать, что там сейчас используется) несколько trie с частями слов не из-за того, что они позволяют как-то удобнее описывать алгоритмы для предсказателя, а просто для того, чтоб не хранить все слова в памяти в полном виде. По моим тестам, с обычным trie это бы заняло (слова + данные о их парадигмах) мегабайт 300-400, с datrie — мегабайт 200, но с MARISA-Trie все можно было бы вместить мегабайт в 20. Использовать несколько «обычных» trie, как в бумаге по mystem — хороший трюк, но этот способ, как мне думается (могу быть не прав, до конца подход «хочу свой mystem» не довел), принципиально работает медленнее, чем «все слова храним как есть».

Назад в будущее

Само по себе MARISA-Trie для того, чтоб держать все слова в памяти, не подходило: оно было небыстрым — что нивелировало потенциальный выигрыш в скорости от того, что слова не нужно было бы собирать по кусочкам, + в API отсутствовала возможность «пошагово» перемещаться по дереву произвольным образом, что было нужно я-уже-не-помню-для-чего, вероятно — для правильной поддержки буквы ё. Дальше было смутное воспоминание о том, что в aot.ru все слова как-то в памяти держали сразу.

Итак, я стал перечитывать описание морфологического анализатора с aot.ru, а в частности — параграф «Бинарное представление словаря». Вернулся, так сказать, к тому, с чего все началось.

В статье на aot.ru все называется «автомат».

Вариант с «отчуждаемой» структурой данных (которую можно использовать для чего-то еще — ну как datrie или marisa-trie) мне архитектурно нравился (и нравится) гораздо больше специализированного автомата со словарем. Специализированный автомат был бы «похоронен» в pymorphy2 — оттуда ничего нельзя было бы использовать повторно, отлаживать его можно было бы только в рамках pymorphy, и сложность накапливалась бы именно в рамках pymorphy. Я обычно пробегал глазами тот параграф, думал «хм-хм, нехорошо» и выдумывал способ, как бы сделать по-другому.

Но на вещи можно смотреть под разными углами. Наверное, это должно было бы быть очевидным с самого начала, но до меня только после того, как попробовал сделать «клон mystem», дошло, что автомат, используемый в aot, на самом деле ровно то же самое, что структура данных DAWG, в которую в качестве ключей записываются слова (с приписанными в конец аннотациями). И что все операции, описанные там, прекрасно ложатся на тот же самый API, который был в datrie и marisa-trie.

Вот уж правду говорят, что «There are only two hard problems in Computer Science: cache invalidation and naming things.» Не знаю насчет «cache invalidation», но вот «naming things» тут прочувствовал в полной мере.

Кажешься себе полным идиотом в такие моменты; все было просто, все было перед глазами с самого начала, и мне об этом много раз говорили (и про автоматы, и про DAWG).

Итак, новый план был такой: по проторенной дорожке

найти реализацию DAWG на С/С++;
сделать для неё обертку с тем же API, что у datrie и marisa-trie;
записать в DAWG все слова (сразу с информацией об их грамматических формах)
бонус — сделать исключительно питонью библиотечку для чтения DAWG-ов, чтоб упростить установку.


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

Хорошая библиотека для DAWG (dawgdic) нашлась у того же Susumu Yata, который написал marisa-trie; я сделал для нее питонью обертку: github.com/kmike/DAWG и питонью «читалку» этого формата: github.com/kmike/DAWG-Python (для установки которой не нужен компилятор).

Весь словарь целиком без аннотаций занял в DAWG около 3Мб, а с аннотациями (= с информацией о том, как каждое слово разбирать) — около 7Мб. Для сравнения — если загрузить все эти данные в питоний словарь «как есть», то это занимает несколько гигабайт памяти.

Дальше оставалось только написать pymorphy2 :)

Статья и так получается какая-то бесконечная, а про то, как pymorphy2 внутри устроен сейчас — пока почти ничего и не было. Чтоб не раздувать текст еще больше, ничего и не будет; о том, как внутри устроен pymorphy2, довольно (излишне?) подробно рассказано в документации, даже с картинками. Я бы все-таки отметил, что pymorphy2 — это не клон lemmatizer на Python, там все устроено по-другому, но информация с aot.ru, конечно, помогла сильно.

Приведу тут два забавных бенчмарка (процессор ноутбучный 1.8 Ghz, под Python 3.3 с использованием DAWG и под PyPy 1.9 с использованием DAWG-Python):

Memory usage: 13.8M dictionary, 25.4M total (load time 0.14s)
py33 runtests: commands[1]

benchmarking MorphAnalyzer():
morph.parse(w) 29950 words/sec
morph.parse(w) 47474 words/sec (considering word frequencies)
morph.word_is_known(w) 244816 words/sec
[p.normal_form for p in morph.parse(w)] 27807 words/sec
[p.normalized for p in morph.parse(w)] 18231 words/sec
[p.lexeme for p in morph.parse(w)] 3421 words/sec
[{'NOUN'} in p.tag for p in morph.parse(w)] 23862 words/sec
[p.tag.POS == 'NOUN' for p in morph.parse(w)] 22157 words/sec

morph.tag(w): 96342 words/sec (considering word frequencies)
morph.tag(w): 46767 words/sec
morph.tag(w): 46935 words/sec (umlauts removed from input)
morph.tag(w): 36331 words/sec (str(tag) called)

benchmarking MorphAnalyzer(result_type=None):
morph.parse(w) 35088 words/sec
morph.parse(w) 62431 words/sec (considering word frequencies)


Memory usage: 40.5M dictionary, 84.8M total (load time 0.39s)
pypy runtests: commands[1]

benchmarking MorphAnalyzer():
morph.parse(w) 41360 words/sec
morph.parse(w) 108858 words/sec (considering word frequencies)
morph.word_is_known(w) 243742 words/sec
[p.normal_form for p in morph.parse(w)] 51728 words/sec
[p.normalized for p in morph.parse(w)] 37551 words/sec
[p.lexeme for p in morph.parse(w)] 14612 words/sec
[{'NOUN'} in p.tag for p in morph.parse(w)] 44878 words/sec
[p.tag.POS == 'NOUN' for p in morph.parse(w)] 45129 words/sec

morph.tag(w): 133086 words/sec (considering word frequencies)
morph.tag(w): 60049 words/sec
morph.tag(w): 62567 words/sec (umlauts removed from input)
morph.tag(w): 52632 words/sec (str(tag) called)

benchmarking MorphAnalyzer(result_type=None):
morph.parse(w) 60777 words/sec
morph.parse(w) 124226 words/sec (considering word frequencies)


Забавным тут я нахожу то, что (а) цифры очень похожие, несмотря на то, что «внутри» действия очень разные (C++ обертка + интерпретатор vs jit-компилятор), и (б) что PyPy быстрее.

Сама по себе реализация DAWG на C++ (если ее использовать из питона, с учетом Cython-обертки) в несколько раз быстрее, чем DAWG-Python под PyPy, и ранние версии pymorphy2 (которые делали всего меньше) были быстрее под CPython. С течением времени фич становилось больше, код сложнее, pymorphy2 тормознее (ранние версии и 200+тыс слов/сек разбирать могли — правда, не очень хорошо и не очень удобно); более быстрая базовая структура данных «перевешивать» перестала — и под PyPy pymorphy2 теперь работает быстрее. С другой стороны, ускорить версию под CPython понятно как — переписать еще что-нибудь на Cython (к слову: делать я этого не планирую); с PyPy это не так очевидно.

Можно заметить, что разбор 100 тыс слов/сек в реальном тексте вполне можно получить как с Python 3.3 (получение грамматической информации), так и с PyPy (полный разбор, с начальной формой и удобным API). Для сравнения: «настоящий» mystem (написанный, видимо, на C++) работал (по моим тестам когда-то на ранних этапах) всего раза в полтора-два быстрее, и требовал столько же памяти; из этого я для себя сделал вывод — возможно, неправильный, — что в mystem используется все-таки подход с несколькими trie; если бы слова хранились целиком, С++ реализация отрываться должны была бы сильнее, даже если mystem и что-то еще вдобавок делает хитрое. Ну это так, опять ничем не подкрепленная болтовня.

Если не использовать ни PyPy, ни C++ реализацию DAWG, pymorphy2 все равно будет работать во много раз быстрее (по прикидкам — в пару десятков раз), чем pymorphy1 cо всеми включенными ускорениями — ну и разбирать лучше.

Как можно помочь

Интересный вопрос остается — что делать с pymorphy1. Там сейчас есть фичи, которых нет в pymorphy2 (например, интеграция с django, согласование слов с цифрами и склонение фамилий), но в версии на битбакете я поломал обратную совместимость. Выпускать еще одну обратно несовместимую версию pymorphy как-то глупо :) поэтому там все болтается в подвешенном состоянии. У меня рук на все категорически не хватает.

Было бы здорово, если б кто-то помог с портированием недостающих фич из pymorphy1;
любая помощь OpenCorpora — это помощь и pymorphy2 тоже;
в трекере есть немало открытых багов (разной степени хардкорности);
в pymorphy2 сейчас встроен очень примитивный токенизатор — можно повыдумывать токенизатор получше; там еще хорошо бы понять, как соотносятся классы из pymorphy2.units.by_shape.py с токенизацией;
можно улучшить CLI, чтоб pymorphy2 можно было использовать как полноценную утилиту командной строки;
можно попробовать написать еще предсказатели для pymorphy2 (см. как сделаны нынешние в pymorphy2.units) — нужно больше глаз, чтоб понять, хороший ли интерфейс для расширения (+ возможно, получится улучшить разбор и добавить что-то новое в стандартную поставку);
ну и можно просто начать использовать pymorphy2.


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

Да и в pymorphy2 уже несколько людей серьезный вклад внесли, кстати :)

Ссылки

Исходный код: github, bitbucket
Документация: pymorphy2.rtfd.org
Баг-трекер: github.com/kmike/pymorphy2/issues
Обсуждение/поддержка: гугл-группа
Структуры данных для Python, возникшие в процессе: DAWG, DAWG-Python, marisa-trie, datrie, hat-trie
pymorphy, pymorphy2, natural language processing, NLP, DAWG, trie, marisa-trie, datrie, mystem
+97

23,8к

291


Коробов Михаил @kmike карма322,0 рейтинг0,0
Сайт Github

Похожие публикации
+14
Детекция кожи в Wolfram Language (Mathematica) 8,9к 60 6
+18
Новая языково-независимая NLP библиотека 14,6к 155 15
+5
Business Natural Languages 12,1к 38 12
Комментарии (42)

+3 Midas15 апреля 2013 в 06:55#
Огромное спасибо за pymorphy, подобные вещи не то что платны, а порой секретны.
Используем его в научном проекте,

Сделано (планируется ли) в pymorphy2, разбор предложений без двусмысленности?
Например:
Моя машина дорогая.
Мой — Мыть
Машина — Маша
дорогой

а должно быть:
Мой
Машина
дорогой
0 tanenn15 апреля 2013 в 07:28#↵↑
А это вообще кто-нибудь умеет кроме человека делать? У вас еще пример простой, а есть и просто печаль типа «косил косой косой косой».
0 Midas15 апреля 2013 в 07:51#↵↑
Ну так, pymorphy это делает ))
+1 samodum15 апреля 2013 в 11:16#↵↑
pymorphy делает только морфологический анализ, и показывает все результаты, в т.ч. и двучмысленные.
+1 VersusVoid15 апреля 2013 в 07:53#↵↑
Умеет, но это уже задача синтаксического анализатора.
0 bolk15 апреля 2013 в 07:57#↵↑
Или классическое «души прекрасные порывы», где без контекста вообще не понять что имеется ввиду.
+2 kmike15 апреля 2013 в 12:08#↵↑
Это планируется, но не совсем в рамках pymorphy2. Pymorphy2 просто смотрит на то, как слово написано, и выдает все разумные варианты разбора. Ну т.е. как — если просто брать первый разбор, который выдает pymorphy2, то где-то 70% слов (чуть больше) будут разобраны правильно (это если не учитывать пунктуацию, с ней 80%).

Если нужно лучше — то нужно знать, как предложения разбираются на самом деле. А для этого нужно имеющуюся неоднозначность разбора поснимать вручную сначала. И вот этим как раз занимается opencorpora.org/ — когда там все будет готово, мы будем знать:

а) какие разборы встречаются чаще (=> pymorphy2 даже без учета контекста сможет выдавать их в более точном порядке);
б) как разборов друг с другом согласуются (=> можно будет написать штуку, снимающую неоднозначность с учетом контекста).

Размеченные тексты есть также в НКРЯ ( www.ruscorpora.ru/ ), и почти все системы, о которых я знаю, натренированы именно на НКРЯ — но там все мутно с лицензией, и проект «только для своих».
0 Granovsky15 апреля 2013 в 12:13#↵↑
Миша, спасибо за пиар :-)
0 kmike15 апреля 2013 в 12:19#↵↑
это вам спасибо :)
+1 eveel15 апреля 2013 в 13:08#↵↑
Если быть совсем строгим и скучным, то можно сказать, что снятие неоднозначности не входит в задачу морфологического анализа. Разумеется, такой ответ никого не интересует.

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

Возможно, в вашей задаче можно обойтись простым согласованием именных групп. Эвристика проста: если у вас имеются пары прилагательных и существительных, согласующихся по числу, роду, падежу, то отбросьте остальные варианты их разбора.
+2 hardtop15 апреля 2013 в 09:37#
Это очень, очень круто! Спасибо, Михаил.
0 kmike15 апреля 2013 в 19:35#↵↑
спасибо)
+3 Neutral15 апреля 2013 в 10:25#
Очень увлекательная статья, я словно детектив читал.
Меня всегда удивляли комментарии в духе "- спасибо, как раз ищу морфологический анализатор!", а теперь сам оставляю такой. Мне действительно скоро потребуется разбирать слова и я уже несколько дней держу в уме статью о pymorphy1. Это рок, не иначе.
Спасибо!
+2 kmike15 апреля 2013 в 19:34#↵↑
рок \m/
+3 marvin15 апреля 2013 в 10:52#
Вау. Роскошная библиотека (активно использовал pymorphy1 – просто незаменимая вещь)

И еще более роскошная статья. В ней есть все:
1. Активный поиск решения
2. Промежуточный вариант, который «недожал»
3. Возврат к истокам
4. Хэпи энд ;)
0 kmike15 апреля 2013 в 19:34#↵↑
Спасибо) Статья с трудом писалась, я ее все выходные редактировал, так что комплимент статье особенно приятен)
0 Zend15 апреля 2013 в 10:54#
Очень интересно! А литературу не посоветуете по этой теме?
+1 kmike15 апреля 2013 в 12:19#↵↑
По структурам данных — Ахо, Ульман — «Структуры данных и алгоритмы». Про обработку текста — nlp.stanford.edu/fsnlp/, например. Если попроще, без особых деталей — то nltk.org/book/ — но там гораздо меньше все объясняется. Курсы на coursera по NLP хорошие (и от Стенфорда, и идущий сейчас от Колумбийского университета). Про детали того, как все для русского языка делается — статьи читать можно. Чтоб все понимать, хорошо бы знания тории вероятности и статистики освежить (или получить): «машинное обучение» — это большей частью то же самое, что и статистика.

Морфологический анализ — это только один небольшой шаг к тому, чтоб с текстом что-то делать, не всегда даже обязательный :)
0 Zend15 апреля 2013 в 12:21#↵↑
Огромнейшее спасибо!
0 Neir015 апреля 2013 в 12:36#
Спасибо за статью и библиотеку, глянул на нее, когда реализовывал собственный морфологический анализатор на c#. У меня в качестве хранилища лексем использовался trie, не помню какое было потребление памяти и скорость, но для меня это было не критично.
0 kmike15 апреля 2013 в 19:32#↵↑
А есть ссылка?
0 Neir015 апреля 2013 в 22:26#↵↑
Нет, ссылочки нету, но могу попробовать поискать и выложить
+1 eveel15 апреля 2013 в 12:47#
Михаил, отличная работа!
0 kmike15 апреля 2013 в 19:32#↵↑
Спасибо!
+2 lightcaster15 апреля 2013 в 12:49#
Михаил, хорошая работа, поздравляю :).

Один момент — не увидел по тексту, позволяет ли та реализация DAWG, что вы используете, минимизировать автомат. Если нет — этим стоит занятся, т.к. можно сохранить большое количество памяти без деградации по скорости. Кстати, в aot было хитро — они использовали алгоритм, где при добавлении слова автомат поддерживался минимально возможным.

ps я делаю pure-с клон openfst, более бедный по функционалу, но более оптимальный по скорости и памяти. пока это только сырой драфт. Как доделаю, было бы интересно потестировать на морфологии.
+1 kmike15 апреля 2013 в 13:22#↵↑
Спасибо! Да, в dawgdic точно такая же хитрость — алгоритм построения устроен так, что автомат, который описывает граф, внутри сразу оказывается минимизированным. Там еще что хорошо — граф внутри не на указателях построен (вроде в aot на указателях, если правильно помню), а в «double array» закодирован и лежит в памяти единым куском. Это позволяет память экономить + для кэша процессора это лучше, чем по указателям прыгать.

Ага, сравнить было бы интересно :)
+1 lightcaster15 апреля 2013 в 14:09#↵↑
Ага, массивом граф представлять — правильная идея. Могут возникнуть проблемы добавления-удаления, но здесь не тот случай. Тут статичного представления достаточно.

Успехов :).
+3 kmike15 апреля 2013 в 15:18#↵↑
Кстати, то, что граф представлен массивом, очень помогло в написании pure-python читалки для него: все данные загружаются в питоний array.array и занимают ровно столько же памяти, сколько и в C++ реализации.
0 wickedweasel16 апреля 2013 в 13:50#
Михаил, не подскажете, какие есть альтернативы добавлению в словарь неизвестных слов через OpenCorpora? Я понимаю, что это приоритетный способ, но есть желание это делать более оперативно.
+3 Granovsky16 апреля 2013 в 13:54#↵↑
Алексей, вы можете создать здесь тикет со списком слов, мы добавим в течение максимум пары дней.
0 wickedweasel16 апреля 2013 в 14:13#↵↑
Это было бы круто. Я тогда постараюсь прогнать список слов на текущем pymorphy2 и выявить недостающие. А вы добавляете неизвестные слова, но которые успешно предсказываются?
+3 Granovsky16 апреля 2013 в 14:15#↵↑
Да, мы всё добавляем. В одной системе успешно предсказываются, в другой нет — мы не хотим за этим следить :-)
0 wickedweasel16 апреля 2013 в 19:23#↵↑
Отправил Вам 2.5к слов в #393.
0 wickedweasel17 апреля 2013 в 14:15#↵↑
А вы не парсите wiktionary.org? Они тоже по CC-BY-SA данные предоставляют.
0 Granovsky17 апреля 2013 в 14:17#↵↑
Парсим: code.google.com/p/opencorpora/issues/detail?id=157
+3 kmike16 апреля 2013 в 15:19#↵↑
В pymorphy2 можно неизвестные слова добавить и без участия OpenCorpora, если очень нужно. Я, правда, не пробовал, но суть такая: в pymorphy2 за разбор и предсказание отвечают отдельные «юниты», в том числе за разбор по словарю (см. github.com/kmike/pymorphy2/blob/master/pymorphy2/units/by_lookup.py ). Можно подготовить XML-ку со своими дополнениями к словарю, скомпилировать ее через «pymorphy dict compile» и добавить еще один «юнит» для разбора по этому новому словарю в MorphAnalyzer (там в конструкторе параметр есть). Чтоб создать такой юнит, понадобится, видимо, просто отнаследоваться от DictionaryAnalyzer и в методе __init__ записать в атрибут .dict новый словарь (вместо того, что будет передаваться в параметрах). «Словарь» в этом случае — экземпляр pymorphy2.opencorpora_dict.wrapper.Dictionary.

Добавить этот юнит, наверное, лучше сразу за юнитом для разбора по стандартному словарю. В этом случае при разборе (склонении и т.д.) pymorphy2 попробует сначала разобрать по стандартному словарю, если не выйдет — по дополнительному, если опять не выйдет — включатся предсказатели.

Понятное дело, лучше в OpenCorpora все добавлять — но хочется думать, что этот use-case архитектурно предусмотрен :)
+1 kmike16 апреля 2013 в 15:35#↵↑
… или еще примитивней — сделать наследника BaseAnalyzerUnit и реализовать нужные методы (tag, parse, lexeme, normalized). Хоть даже вот так (чтоб суть видна была; код организовать по-другому лучше, конечно):

class AlyoshenkaAnalyzer(BaseAnalyzerUnit):
# слова "Алёшенька" в словаре нет и оно из-за этого разбирается как имя женского рода
# пусть хотя бы метод tag работает
def tag(word, word_lower, seen_tags):
if word_lower in {"алешенька", "алёшенька"}:
return [self.morph.TagClass('NOUN,masc,anim,Name sing,nomn')]
return []

Для других методов там посложнее; у наследника DictionaryAnalyzer плюс тот, что никакого кода писать не нужно, и работать все будет быстро.
0 wickedweasel16 апреля 2013 в 19:24#↵↑
Похоже, самым разумным тогда будет поднять свой инстанс OpenCorpora, чтобы вносить слова через удобный интерфейс. В любом случае спасибо за информацию.
+2 jishi16 апреля 2013 в 13:53#
Огромное спасибо. Если вы не против — перепишу на PHP.
+2 wickedweasel16 апреля 2013 в 14:02#↵↑
На PHP уже давно есть PHPMorphy. Правда, если не ошибаюсь, его автор, Владимир Камаев, в последнее время не очень поддерживает проект. Насколько я знаю, последняя версия живёт тут: github.com/heromantor/phpmorphy
0 kmike16 апреля 2013 в 15:21#↵↑
phpMorphy вроде неплох (это, насколько помню, был почти 1-в-1 клон lemmatizer с aot.ru) — но против переписывания pymorphy2, конечно же, ничего не имею против :)
0 MikeLP18 марта 2014 в 00:51 (комментарий был изменён)#↵↑
Большое человеческое спасибо за труд автору! Немного не в ту ветку но все же.
https://github.com/Digsolab/pymystem3

пасибо этой
http://vk.com/rybolos

Posted: Mon, 9 Nov 2015, 12:02:18
by dyvniy
анализ сисястости моделей плейбоя
http://habrahabr.ru/post/251225/

Posted: Mon, 26 Nov 2018, 16:43:28
by dyvniy
Расчёт гармоник, быстрое преобразовние Фурье
https://habr.com/post/431010/

Posted: Tue, 9 Apr 2019, 10:53:28
by dyvniy
Не уверен что там питон, но задачки интересные
https://habr.com/ru/company/yandex/blog/327444/
Spoiler
Спортивный анализ данных, или как стать специалистом по data science
Блог компании Яндекс,
Big Data,
Data Mining,
Машинное обучение,
Спортивное программирование
Меня зовут Пётр Ромов, я — data scientist в Yandex Data Factory. В этом посте я предложу сравнительно простой и надежный способ начать карьеру аналитика данных.

Многие из вас наверняка знают или хотя бы слышали про Kaggle. Для тех, кто не слышал: Kaggle — это площадка, на которой компании проводят конкурсы по созданию прогнозирующих моделей. Её популярность столь велика, что часто под «кэглами» специалисты понимают сами конкурсы. Победитель каждого соревнования определяется автоматически — по метрике, которую назначил организатор. Среди прочих, Kaggle в разное время опробовали Facebook, Microsoft и нынешний владелец площадки — Google. Яндекс тоже несколько раз отметился. Как правило, Kaggle-сообществу дают решать задачи, довольно близкие к реальным: это, с одной стороны, делает конкурс интересным, а с другой — продвигает компанию как работодателя с солидными задачами. Впрочем, если вам скажут, что компания-организатор конкурса задействовала в своём сервисе алгоритм одного из победителей, — не верьте. Обычно решения из топа слишком сложны и недостаточно производительны, а погони за тысячными долями значения метрики не настолько и нужны на практике. Поэтому организаторов больше интересуют подходы и идейная часть алгоритмов.



Kaggle — не единственная площадка с соревнованиями по анализу данных. Существуют и другие: DrivenData, DataScience.net, CodaLab. Кроме того, конкурсы проводятся в рамках научных конференций, связанных с машинным обучением: SIGKDD, RecSys, CIKM.

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

Три года назад несколько студентов ШАД начали собираться и решать разные интересные задания, в том числе взятые с Kaggle. Например, среди этих ребят был нынешний обладатель второго места и недавний лидер рейтинга Kaggle Станислав Семёнов. Со временем встречи получили название тренировок по машинному обучению. Они набирали популярность, участники стали регулярно занимать призовые места и рассказывать друг другу о своих решениях, делиться опытом.

Чтобы было понятно, чем именно мы занимаемся на тренировках, я приведу несколько примеров. В каждом примере сначала идёт видео с рассказом, а затем — текст, составленный по мотивам видео.

Задача классификации изображений автомобилей

Ссылка на MachineLearning.ru.

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



Постановка задачи. По изображениям автомобилей необходимо определить марку и модель. Метрикой служила точность предсказаний, то есть доля правильных ответов. Выборка состояла из трёх частей: первая часть была доступна для обучения изначально, вторая была дана позже, а на третьей требовалось показать финальные предсказания.



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



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



Заметим, что наилучшее качество достигается на архитектурах Inception и ResNet.

Fine-tuning сетей. Обучать глубокую нейронную сеть с нуля — довольно затратное по времени занятие, к тому же не всегда эффективное с точки зрения результата. Поэтому часто используется техника дообучения сетей: берётся уже обученная на ImageNet сеть, последний слой заменяется на слой с нужным количеством классов, а потом продолжается настройка сети с низким темпом обучения, но уже на данных из конкурса. Такая схема позволяет обучить сеть быстрее и с более высоким качеством.



Первый подход к дообучению GoogLeNet показал примерно 92% точности при валидации.

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



Валидация результатов. После появления выдачи второй части выборки я разбил выборку на несколько частей. Все дальнейшие результаты показаны на этом разбиении.



ResNet-34 Torch. Можно воспользоваться готовым репозиторием авторов архитектуры, но, чтобы получить предсказания на тесте в нужном формате, приходится исправлять некоторые скрипты. Кроме того, нужно решать проблемы большого потребления памяти дампами. Точность при валидации — около 95%.




Inception-v3 TensorFlow. Тут тоже использовалась готовая реализация, но была изменена предобработка изображений, а также ограничена обрезка картинок при генерации батча. Итог — почти 96% точности.



Ансамбль моделей. В итоге получилось две модели ResNet и две модели Inception-v3. Какое качество при валидации можно получить, смешивая модели? Вероятности классов усреднялись с помощью геометрического среднего. Веса (в данном случае — степени) подбирались на отложенной выборке.



Результаты. Обучение ResNet на GTX 980 занимало 60 часов, а Inception-v3 на TitanX — 48 часов. За время конкурса удалось опробовать новые фреймворки с новыми архитектурами.



Задача классификации клиентов банка

Ссылка на Kaggle.

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



Постановка задачи. По обфусцированным данных из заявок на страхование необходимо предсказать, можно ли без дополнительных ручных проверок подтвердить запрос. Для банка это процесс автоматизации обработки заявок, а для аналитиков данных — просто задача машинного обучения по бинарной классификации. Имеется около 230 тысяч объектов и 130 признаков. Метрика — LogLoss. Стоит отметить, что команда-победитель расшифровала данные, что помогло им выиграть соревнование.

Избавление от искусственного шума в признаках. Первым делом стоит посмотреть на данные. Cразу бросаются в глаза несколько вещей. Во-первых, все признаки принимают значения от 0 до 20. Во-вторых, если посмотреть на распределение любого из признаков, то можно увидеть следующую картинку:



Почему так? Дело в том, что на этапе анонимизации и зашумления данных ко всем значениям прибавлялся случайный шум, а потом проводилось масштабирование на отрезок от 0 до 20. Обратное преобразование было проведено в два шага: сначала значения округлялись до некоторого знака после запятой, а потом подбирался деноминатор. Требовалось ли это, если дерево всё равно подбирает порог при разбиении? Да, после обратного преобразования разности переменных начинают нести больший смысл, а для категориальных переменных появляется возможность провести one-hot кодирование.

Удаление линейно зависимых признаков. Ещё мы заметили, что некоторые признаки являются суммой других. Понятно, что они не нужны. Для их определения брались подмножества признаков. На таких подмножествах строилась регрессия для предсказания некоторой другой переменной. И если предсказанные значения были близки к истинным (стоит учесть искусственное зашумление), то признак можно было удалить. Но команда не стала с этим возиться и воспользовалась уже готовым набором фильтрованных признаков. Набор подготовил кто-то другой. Одна из особенностей Kaggle — наличие форума и публичных решений, с помощью которых участники делятся своими находками.

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

Кодирование категориальных переменных. Бросилось в глаза то, что некая переменная V22 имеет большое число значений, но при этом, если взять подвыборку по некоторому значению, число уровней (различных значений) других переменных заметно уменьшается. В том числе имеет место хорошая корреляция с целевой переменной. Что можно сделать? Самое простое решение — построить для каждого значения V22 отдельную модель, но это всё равно что в первом сплите дерева сделать разбиение по всем значениям переменной.

Есть другой способ использования полученной информации — кодирование средним значением целевой переменной. Другими словами, каждое значение категориальной переменной заменяется средним значением таргета по объектам, у которых данный признак принимает то же самое значение. Произвести такое кодирование напрямую для всего обучающего множества нельзя: в процессе мы неявно внесём в признаки информацию о целевой переменной. Речь идёт об информации, которую почти любая модель обязательно обнаружит.

Поэтому такие статистики считают по фолдам. Вот пример:



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

Останутся ли проблемы ещё с чем-нибудь? Да — с редко встречающимися категориями и с кросс-валидацией.

Редко встречающиеся категории. Допустим, некоторая категория встретилась всего несколько раз и соответствующие объекты относятся к классу 0. Тогда среднее значение целевой переменной тоже будет нулевым. Однако на тестовой выборке может возникнуть совсем другая ситуация. Решение — сглаженное среднее (или smoothed likelihood), которое вычисляется по следующей формуле:



Здесь global mean — среднее значение целевой переменной по всей выборке, nrows — то, сколько раз встретилось конкретное значение категориальной переменной, alpha — параметр регуляризации (например, 10). Теперь, если некоторое значение встречается редко, больший вес будет иметь глобальное среднее, а если достаточно часто, результат окажется близким к начальному среднему по категории. Кстати, эта формула позволяет обрабатывать и неизвестные ранее значения категориальной переменной.

Кросс-валидация. Допустим, мы посчитали все сглаженные средние для категориальных переменных по другим фолдам. Можем ли мы оценить качество модели по стандартной кросс-валидации k-fold? Нет. Давайте рассмотрим пример.



К примеру, мы хотим оценить модель на третьем фолде. Мы обучаем модель на первых двух фолдах, но в них есть новая переменная со средним значением целевой переменной, при подсчёте которой мы уже использовали третий тестовый фолд. Это не позволяет нам корректно оценивать результаты, но возникшая проблема решается подсчётом статистик по фолдам внутри фолдов. Снова обратимся к примеру:



Мы по-прежнему хотим оценить модель на третьем фолде. Разобьём первые два фолда (обучающую выборку нашей оценки) на некоторые другие три фолда, в них посчитаем новый признак по уже разобранному сценарию, а для третьего фолда (это тестовая выборка нашей оценки) посчитаем по первым двум фолдам вместе. Тогда никакая информация из третьего фолда при обучении модели использоваться не будет и оценка получится честной. В соревновании, которое мы обсуждаем, корректно оценить качество модели позволяла только такая кросс-валидация. Разумеется, «внешнее» и «внутреннее» число фолдов может быть любым.

Построение признаков. Мы использовали не только уже упомянутые сглаженные средние значения целевой переменной, но и weights of evidence. Это почти то же самое, но с логарифмическим преобразованием. Кроме того, полезными оказались фичи вида разности количества объектов положительного и отрицательного классов в группе без какой-либо нормировки. Интуиция тут следующая: масштаб показывает степень уверенности в классе, но что делать с количественными признаками? Ведь если их обработать похожим образом, то все значения «забьются» регуляризацией глобальным средним. Одним из вариантов является разделение значений на бины, которые потом считаются отдельными категориями. Другой способ заключается просто в построении некой линейной модели на одном признаке с тем же таргетом. Всего получилось около двух тысяч признаков из 80 отфильтрованных.

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


Взято из блога Александра Дьяконова

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

На первом уровне у команды было 200-250 различных моделей, на втором — ещё 20-30, на третьем — ещё несколько. Результат — блендинг, то есть смешивание предсказаний различных моделей. Использовались разнообразные алгоритмы: градиентные бустинги с разными параметрами, случайные леса, нейронные сети. Главная идея — применить максимально разнообразные модели с различными параметрами, даже если они дают не самое высокое качество.

Работа в команде. Обычно участники объединяются в команды перед завершением конкурса, когда у каждого уже имеются свои наработки. Мы объединились в команду с другими «кэглерами» ещё в самом начале. У каждого участника команды была папка в общем облаке, где размещались датасеты и скрипты. Общую процедуру кросс-валидации утвердили заранее, чтобы можно было сравнивать между собой. Роли распределялись следующим образом: я придумывал новые признаки, второй участник строил модели, третий — отбирал их, а четвёртый управлял всем процессом.

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

Общение с компанией-организатором. После успешного выступления в конкурсе происходит общение с компанией в виде совместного конференц-звонка. Участники рассказывают о своём решении и отвечают на вопросы. В BNP людей не удивил многоуровневый стекинг, а интересовало их, конечно же, построение признаков, работа в команде, валидация результатов — всё, что может им пригодиться в улучшении собственной системы.

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

Наша команда заняла третье место. Всего участвовало почти три тысячи команд.

Задача распознавания категории объявления

Ссылка на DataRing.

Это ещё один конкурс «Авито». Он проходил в несколько этапов, первый из которых (как, впрочем, ещё и третий) выиграл Артур Кузин N01Z3.



Постановка задачи. По фотографиям из объявления необходимо определить категорию. Каждому объявлению соответствовало от одного до пяти изображений. Метрика учитывала совпадения категорий на разных уровнях иерархии — от общих к более узким (последний уровень содержит 194 категории). Всего в обучающей выборке был почти миллион изображений, что близко к размеру ImageNet.



Сложности распознавания. Казалось бы, надо всего лишь научиться отличать телевизор от машины, а машину от обуви. Но, например, есть категория «британские кошки», а есть «другие кошки», и среди них встречаются очень похожие изображения — хотя отличить их друг от друга всё-таки можно. А как насчёт шин, дисков и колёс? Тут и человек не справится. Указанные сложности — причина появления некоторого предела результатов всех участников.



Ресурсы и фреймворк. У меня в распоряжении оказались три компьютера с мощными видеокартами: домашний, предоставленный лабораторией в МФТИ и компьютер на работе. Поэтому можно было (и приходилось) обучать по несколько сетей одновременно. В качестве основного фреймворка обучения нейронных сетей был выбран MXNet, созданный теми же ребятами, которые написали всем известный XGBoost. Одно это послужило поводом довериться их новому продукту. Преимущество MXNet в том, что прямо из коробки доступен эффективный итератор со штатной аугментацией, которой достаточно для большинства задач.



Архитектуры сетей. Опыт участия в одном из прошлых соревнований показал, что лучшее качество показывают архитектуры серии Inception. Их я и задействовал здесь. В GoogLeNet была добавлена батч-нормализация, поскольку она ускоряла обучение модели. Также использовались архитектуры Inception-v3 и Inception BN из библиотеки моделей Model Zoo, в которые был добавлен дропаут перед последним полносвязным слоем. Из-за технических проблем не удавалось обучать сеть с помощью стохастического градиентного спуска, поэтому в качестве оптимизатора использовался Adam.



Аугментация данных. Для повышения качества сети использовалась аугментация — добавление искажённых изображений в выборку с целью увеличения разнообразия данных. Были задействованы такие преобразования, как случайное обрезание фотографии, отражение, поворот на небольшой угол, изменение соотношения сторон и сдвиг.



Точность и скорость обучения. Сначала я разделил выборку на три части, но потом отказался от одного из этапов валидации для смешивания моделей. Поэтому впоследствии вторая часть выборки была добавлена в обучающее множество, что улучшило качество сетей. Кроме того, GoogLeNet изначально обучался на Titan Black, у которого вдвое меньше памяти по сравнению с Titan X. Так что эта сеть была дообучена с большим размером батча, и её точность возросла. Если посмотреть на время обучения сетей, можно сделать вывод, что в условиях ограниченных сроков не стоит использовать Inception-v3, поскольку с двумя другими архитектурами обучение идёт заметно быстрее. Причина в числе параметров. Быстрее всех учится Inception BN.



Построение предсказаний.

Как и Евгений в конкурсе с марками автомобилей, Артур использовал предсказания на кропах — но не на 10 участках, а на 24. Участками послужили углы, их отражения, центр, повороты центральных частей и ещё десять случайных.

Если сохранять состояние сети после каждой эпохи, в результате образуется множество различных моделей, а не только финальная сеть. С учётом оставшегося до конца соревнования времени я мог использовать предсказания 11 моделей-эпох — поскольку построение предсказаний с помощью сети тоже длится немало. Все указанные предсказания усреднялись по следующей схеме: сначала с помощью арифметического среднего в рамках групп по кропам, далее с помощью геометрического среднего с весами, подобранными на валидационном множестве. Эти три группы смешиваются, потом повторяем операцию для всех эпох. В конце вероятности классов всех картинок одного объявления усредняются с помощью геометрического среднего без весов.



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



Обучение с нуля vs. fine-tuning. Уже после завершения конкурса выяснилось, что несмотря на большой размер выборки стоило обучать сеть не с нуля, а при помощи предобученной сети. Этот подход демонстрирует более высокие результаты.



Задача обучения с подкреплением

Соревнование Black Box Challenge, о котором писали на Хабрахабре, было не совсем похоже на обычный «кэгл». Дело в том, что для решения было недостаточно разметить некоторую «тестовую» выборку. Требовалось запрограммировать и загрузить в систему код «агента», который помещался в неизвестную участнику среду и самостоятельно принимал в ней решения. Такие задачи относятся к области обучения с подкреплением — reinforcement learning.

О подходах к решению рассказал Михаил Павлов из компании 5vision. В конкурсе он занял второе место.



Постановка задачи. Для среды с неизвестными правилами нужно было написать «агента», который взаимодействовал бы с указанной средой. Схематично это некий мозг, который получает от чёрного ящика информацию о состоянии и награде, принимает решение о действии, после чего получает новое состояние и награду за совершённое действие. Действия повторяются друг за другом в течение игры. Текущее состояние описывается вектором из 36 чисел. Агент может совершить четыре действия. Цель — максимизировать сумму наград за всю игру.



Анализ среды. Изучение распределения переменных состояния среды показало, что первые 35 компонент не зависят от выбранного действия и только 36-я компонента меняется в зависимости от него. При этом разные действия влияли по-разному: некоторые увеличивали или уменьшали, некоторые никак не меняли. Но нельзя сказать, что вся среда зависит от одной компоненты: в ней могут быть и некие скрытые переменные. Кроме того, эксперимент показал, что если совершать более 100 одинаковых действий подряд, то награда становится отрицательной. Так что стратегии вида «совершать только одно действие» отпадали сразу. Кто-то из участников соревнования заметил, что награда пропорциональна всё той же 36-й компоненте. На форуме прозвучало предположение, что чёрный ящик имитирует финансовый рынок, где портфелем является 36-я компонента, а действиями — покупка, продажа и решение ничего не делать. Эти варианты соотносились с изменением портфеля, а смысл одного действия понятен не был.



Q-learning. Во время участия основной целью было попробовать различные техники обучения с подкреплением. Одним из самых простых и известных методов является q-learning. Его суть в попытке построить функцию Q, которая зависит от состояния и выбранного действия. Q оценивает, насколько «хорошо» выбирать конкретное действие в конкретном состоянии. Понятие «хорошо» включает в себя награду, которую мы получим не только сейчас, но и будущем. Обучение такой функции происходит итеративно. Во время каждой итерации мы пытаемся приблизить функцию к самой себе на следующем шаге игры с учётом награды, полученной сейчас. Подробнее можно почитать в ещё одной статье на Хабрхабре. Применение q-learning предполагает работу с полностью наблюдаемыми марковскими процессами (другими словами, в текущем состоянии должна содержаться вся информация от среды). Несмотря на то, что среда, по заявлению организаторов, не удовлетворяла этому требованию, применять q-learning можно было достаточно успешно.



Адаптация к black box. Опытным путём было установлено, что для среды лучше всего подходил n-step q-learning, где использовалась награда не за одно последнее действие, а за n действий вперёд. Среда позволяла сохранять текущее состояние и откатываться к нему, что облегчало сбор выборки — можно было из одного состояния попробовать совершить каждое действие, а не какое-то одно. В самом начале обучения, когда q-функция ещё не умела оценивать действия, использовалась стратегия «совершать действие 3». Предполагалось, что оно ничего не меняло и можно было начать обучаться на данных без шума.



Процесс обучения. Обучение происходило так: с текущей политикой (стратегией агента) играем весь эпизод, накапливая выборку, потом с помощью полученной выборки обновляем q-функцию и так далее — последовательность повторяется в течение некоторого количества эпох. Результаты получались лучше, чем при обновлении q-функции в процессе игры. Другие способы — техника replay memory (с общим банком данных для обучения, куда заносятся новые эпизоды игры) и одновременное обучение нескольких агентов, играющих асинхронно, — тоже оказалось менее эффективными.



Модели. В решении использовались три регрессии (каждая по одному разу в расчёте на каждое действие) и две нейронных сети. Были добавлены некоторые квадратичные признаки и взаимодействия. Итоговая модель представляет собой смесь всех пяти моделей (пяти Q-функций) с равными весами. Кроме того, использовалось онлайн-дообучение: в процессе тестирования веса́ старых регрессий подмешивались к новым весам, полученным на тестовой выборке. Это делалось только для регрессий, поскольку их решения можно выписывать аналитически и пересчитывать достаточно быстро.



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



Итоги. Команда 5vision заняла второе место, но с совсем небольшим отрывом от обладателей «бронзы».




Итак, зачем нужно участвовать в соревнованиях по анализу данных?

Призы. Успешное выступление в большинстве соревнований вознаграждается денежными призами или другими ценными подарками. На Kaggle за семь лет разыграли более семи миллионов долларов.
Карьера. Иногда призовое место выливается в смену работы.
Опыт. Это, конечно, самое главное. Можно изучить новую область и начать решать задачи, с которыми вы раньше не сталкивались.



Сейчас тренировки по машинному обучению проводятся по субботам каждую вторую неделю. Место проведения — московский офис Яндекса, стандартное число гостей (гости плюс яндексоиды) — 60-80 человек. Главным свойством тренировок служит их злободневность: всякий раз разбирается конкурс, завершившийся одну-две недели назад. Это мешает всё точно спланировать, но зато конкурс ещё свеж в памяти и в зале собирается много людей, попробовавших в нём свои силы. Курирует тренировки Эмиль Каюмов, который, кстати, помог с написанием этого поста.

Кроме того, есть другой формат: зарешивания, где начинающие специалисты совместными усилиями участвуют в действующих конкурсах. Зарешивания проводятся по тем субботам, когда нет тренировок. На мероприятия обоих типов может прийти любой, анонсы публикуются в группах на Фейсбуке и ВКонтакте, есть YouTube-канал с прямыми трансляциями. Кстати, зарешивания также проходят в Санкт-Петербурге, Новосибирске, Екатеринбурге и Калининграде. Если вашего города нет в списке, а небольшое сообщество уже сформировалось — попробуйте организовать несколько встреч самостоятельно.



Вот и всё. Посещаете тренировки, слушаете, пробуете участвовать, занимаете какие-нибудь далёкие места, начинаете ходить на зарешивания, снова пробуете — замечая или не замечая, что из вас вырастает data scientist. Если сейчас вы разработчик или devops, то пройти подобный путь реально и, что самое главное, не так уж и сложно. Например — проще, чем пробовать стать аналитиком данных каким-нибудь другим способом.

Полезные ссылки, или как начать решать:

Если вы уже не новичок и хотите в сжатые сроки «прокачаться» по основным темам — пройдите курc Яндекса «Введение в машинное обучение» на Coursera.
Желающим изучать предмет постепенно больше подойдёт специализация «Машинное обучение и анализ данных».
Сообщество Open Data Science (каналы #mltrainings_beginners, #mltrainings_live).
Теги:
data science
kaggle
контест
тренировки
валидация
стекинг
блендинг
xgboost
классификация
распознавание изображений
imagenet
resnet
inceptionv3
mxnet
adam
аугментация данных
black box
чёрный ящик
конкурсы разработчиков
q-learning
нейронные сети
+61
47,6k
13

Яндекс 490,00
Как мы делаем Яндекс

12,0
Карма
0,0
Рейтинг
3
Подписчики
Петр Ромов romovpa
Data Scientist
Github
Поделиться публикацией
ПОХОЖИЕ ПУБЛИКАЦИИ
24 июня 2018 в 13:54 Выявление и классификация токсичных комментариев. Лекция в Яндексе
+23
7,7k
65
23
16 мая 2018 в 11:00 Безопасный каршеринг: составляющие, основные проблемы и конкурс Яндекса
+38
15k
25
31
1 апреля 2018 в 14:34 Нативная валидация как фреймворк. Лекция в Яндексе
+35
5,9k
66
1
ВАКАНСИИ КОМПАНИИ ЯНДЕКС
Разработчик интерфейсов
Москва
Полный рабочий день
Вакансии компании
Создать резюме
Комментарии 13
irepetitor_ru
27 апреля 2017 в 12:43
–10
Неспособно участие в кэглах сделать аналитика данных. Если человек не понимает как совершенствовать методологию, не делает самоанализ, и с ним коуча нет, то будет как слепой котёнок, наступать на грабли, причём на разные. Или просто воспроизводить одни и те же ошибки.

gef0rce
27 апреля 2017 в 12:51
+4
То есть самообучение невозможно?
irepetitor_ru
27 апреля 2017 в 14:08
0
Возможно. Речь о недостаточности участия в кэгле без должного самоанализа как минимум. Или анализа со стороны.
tomzarubin
27 апреля 2017 в 14:59
–2
Самоанализ, самокопание, наставничество? Нет, спасибо. Лучше зарешать котиков на Кэггле, за неделю посмотрев CS231n, и занять 100ое место с 0.

gef0rce
27 апреля 2017 в 15:01
0
Но разве форум, другие участники и коммьюнити не дают «анализ со стороны»?

romovpa
27 апреля 2017 в 15:14
+2
Для того мы и проводим тренировки и зарешивания, чтобы люди не только участвовали в соревнованиях, но и помогали друг другу, делились опытом, анализировали свои и чужие ошибки. Приходите на тренировку.
recontemplator
21 января 2018 в 20:56
0
А вот, Jeremy Howard, говорит, что именно участвуя в соревнованиях он продвинулся в теме, гораздо сильнее чем любыми иными способами. youtu.be/Q0z-l2KRYFY?t=3547

Его, конечно, сложно считать беспристрастным в этом вопросе, он даже возглавлял Kaggle какое-то время. Но его достижения в сфере анализа данных — неоспоримы. И не только «спортивные» но и коммерческие и академические. И мне он кажется искренне желающим «поделиться рабочим рецептом».
fireSparrow
27 апреля 2017 в 12:58
+2
Участие в чём-либо само по себе никогда не делает из человека специалистом в чём бы то ни было.

Но если человек замотивирован и активно ищет возможности для саморазвития, то участие в Kaggle будет ему на пользу.

А наличие наставника не так уж обязательно, хотя, конечно, тоже плюс.

cepera_ang
27 апреля 2017 в 13:16
+1
Ага, ага, сказал коуч, у которого зависит зарплата от того, как много людей он сможет убедить в том, что без коуча жизни нет.
irepetitor_ru
27 апреля 2017 в 14:02
0
Вы увидели то, что хотели увидеть.
Я не преподаю deep learning. Мой тезис касается участия в кэглах и прочих забегах.

cepera_ang
27 апреля 2017 в 14:16
+3
При чём тут преподавание диплёнинга?
Статья: — «Пацаны, смотрите как можно соревноваться и за счёт этого учиться, вот вам опыт десятков других людей, рассказ как учиться на своих и чужих ошибках, самосовершенствоваться и проверять себя, вот вам курсы, вот еженедельные собрания, вот коммьюнити»
Вы: — «Если человек не понимает как совершенствовать методологию, не делает самоанализ, и с ним коуча нет, то будет как слепой котёнок, наступать на грабли, причём на разные. Или просто воспроизводить одни и те же ошибки.» (в фоне: «Я, я такой коуч, который не даст вам наступать на грабли и воспроизводить одни и те же ошибки»).


John_Minority
27 апреля 2017 в 16:33
+1
Коуч не спсобен сделать аналитика данных, он обычно вообще ничего не способен, кроме как быть коучем.
Такая вот профессия — быть коучем и сотрясать воздух пустыми словами.

ternaus
27 апреля 2017 в 19:06
+2
Kaggle — это не все, и даже и не рядом. Но это очень много. И с грамотным наставником или в сильном коллективе все это идет гораздо лучше — это факт.


Про менторство понятно, у тебя в описании профиля написано. А вот в разрезе соревновательного машинного обучения. Не мог бы ты поделиться ссылкой на свой Kaggle profile?


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


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

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