- PVSM.RU - https://www.pvsm.ru -
Тематическое моделирование [1] — подраздел машинного обучения, посвященный извлечению абстрактных «тем» из набора «документов». Каждый «документ» представлен мешком слов [2], т.е. множеством слов вместе с их частотами. Введение в тематическое моделирование прекрасно описано проф. К. В. Воронцовым [3] в лекциях ШАД [PDF [4]]. Самая известная модель ТМ — это, конечно, Латентное размещение Дирихле [5] (LDA). Константину Вячеславовичу удалось обобщить все возможные тематические модели на основе мешка слов в виде аддитивной регуляризации [6] (ARTM). В частности, LDA тоже входит в множество моделей ARTM. Идеи ARTM воплощены в проекте BigARTM [7].
Обычно тематическое моделирование применяют к текстовым документам. Мы в source{d} [8] (стартап в Испании) перевариваем биг дату, полученную из GitHub репозиториев (и скоро примемся за каждый публично доступный репозиторий в мире). Естественным образом возникла идея интерпретировать каждый репозиторий как мешок слов и натравить BigARTM. В этой статье пойдет речь о том как мы выполнили по сути первое в мире тематическое исследование крупнейшего хранилища open source проектов, что из этого получилось и как это повторить. docker inside!
TL;DR:
docker run srcd/github_topics apache/spark
(заменить apache/spark
на любой GitHub реп по желанию).
Таблица OpenDocument с извлеченными темами. [9]
JSON с извлеченными темами. [10]
Обученная модель [11] — 40МБ, gzipped pickle для Python 3.4+, Pandas 1.18+.
Dataset на data.world — скоро загрузим.
Задана тематическая вероятностная модель на множестве документов которая описывает частоту появления слова в документе с темами :
где — вероятность отношения слова к теме , — вероятность отношения темы к документу , т.о. формула выше это просто выражение полной вероятности [12], при условии истинности гипотезы независимости случайных величин: . Слова берутся из словаря , темы принадлежат множеству которое представляет собой просто серию индексов .
Нам нужно восстановить и из заданного набора документов . Обычно считают что , где — количество вхождений в документ , однако это подразумевает что все слова одинаково важные что не всегда справедливо. Под «важностью» здесь имеется в виду мера, негативно скоррелированная с общей частотой появления слова в документах. Обозначим восстанавливаемые вероятности и . Т.о. наша задача сводится к стохастическому матричному разложению, которая некорректно поставлена:
В задачах машинного обучения обычно применяют регуляризацию [13] как способ улучшить характеристики модели на неизвестных данных (как следствие, уменьшается переобучение [14], сложность и т.д.); в нашем случае, она просто необходима.
Задачи наподобие описанной выше решаются с помощью метода максимального правдоподобия [15]:
при условиях
Суть ARTM в том чтобы естественным образом добавить регуляризацию в виде дополнительных слагаемых:
Поскольку это простое сложение, мы можем комбинировать различные регуляризаторы в одной оптимизации, например, проредить матрицу и увеличить независимость тем. LDA формулируется в терминах ARTM так:
Переменные и могут быть эффективно вычислены с помощью итеративного EM-алгоритма [16]. Десятки готовых ARTM регуляризаторов готовы к бою в составе BigARTM [7].
На этом вынужденный рерайт лекции ШАДа заканчивается и начинается
Для анализа на октябрь 2016 года были доступны около 18 миллионов репозиториев на GitHub. Их на самом деле гораздо больше, просто мы отбросили форки и «хард форки» (форк не отмечен GitHub-ом). Положим каждый репозиторий это , а каждое имя в исходниках это . Анализ исходников делался теми же инструментами, что и при глубоком обучении исходному коду в ранних экспериментах (см. наши презентации с последних конференций RE·WORK [17]: Берлин [18] и Лондон [19]): первичная классификация github/linguist [20]-ом и парсинг на основе Pygments [21]. Текстовые файлы общего назначения отбрасывались, например README.md [22].
Имена из исходников следует извлекать не «в лоб», например, class FooBarBaz
добавляет 3 слова в мешок: foo
, bar
и baz
, а int wdSize
добавляет два: wdsize
и size
. Кроме того, имена стеммировались Snowball [23]-ом из NLTK [24], хотя специально мы не исследовали пользу от этого. Последний этап предобработки заключался в вычислении логарифмической версии TF-IDF [25] взвешивания (снова, специально не исследовали, просто копировали решения [26] из обычного НЛП) и фильтрации слишком редких и общеупотребительных имен, в нашем случае, границы были 50 и 100000 соответственно.
После того как ARTM выдал результат, нужно было вручную дать имена темам, основываясь на ключевых словах и репозиториях-представителях. Число тем было выставлено в 200, и как потом оказалось, нужно было поставить больше, т.к. тем на Гитхабе очень много. Нудная работа отняла целую неделю.
Предобработка была выполнена на Dataproc [27] aka Spark в облаке Google, а основные действия производились локально на мощном компьютере. Результирующая разреженная матрица имела размер около 20 GB, и ее пришлось преобразовать в текстовый формат Vowpal Wabbit, чтобы ее смог переварить BigARTM CLI. Данные были перемолоты довольно быстро, за пару часов:
bigartm -c dataset_vowpal_wabbit.txt -t 200 -p 10 --threads 10 --write-model-readable bigartm.txt --regularizer "0.05 SparsePhi" "0.05 SparseTheta"
Parsing text collection... OK.
Gathering dictionary from batches... OK.
Initializing random model from dictionary... OK.
Number of tokens in the model: 604989
================= Processing started.
Perplexity = 586350
SparsityPhi = 0.00214434
SparsityTheta = 0.422496
================= Iteration 1 took 00:11:57.116
Perplexity = 107901
SparsityPhi = 0.00613982
SparsityTheta = 0.552418
================= Iteration 2 took 00:12:03.001
Perplexity = 60701.5
SparsityPhi = 0.102947
SparsityTheta = 0.768934
================= Iteration 3 took 00:11:55.172
Perplexity = 20993.5
SparsityPhi = 0.458439
SparsityTheta = 0.902972
================= Iteration 4 took 00:11:56.804
...
-p
задает число итераций. Уверенности в том, какие регуляризаторы использовать, не было, так что активирована только «sparsity». Сказалось отсутствие подробной документации (разработчики пообещали это исправить). Важно отметить, что объем оперативной памяти, который потребовался для работы на пике был не больше 30 GB, что очень круто на фоне gensim [28] и, прости господи, sklearn [29].
В итоге, 200 тем можно поделить на следующие группы:
Пожалуй, самая интересная группа с кучей извлеченных фактов из повседневной жизни:
В список тем вошли испанский, португальский, французский и китайский. Русский в отдельную тему не сформировался, что свидетельствует скорее о более высоком уровне наших программистов на GitHub, пишущих сразу на английском, чем о малом количестве русских репозиториев. В этом смысле, китайские репозитории убивают.
Интересная находка в ЯП — это тема «Non-native English PHP», ассоциированная с проектами на PHP, не написанными людьми, знающими английский. Видимо, эти две группы программистов как-то принципиально по-разному пишут код. Кроме того, есть две темы, относящиеся к Java: JNI и байткод.
Здесь не так интересно. Существует много репозиториев с ядрами ОС — большие, шумные и несмотря на наши старания они изгадили некоторые топики. Тем не менее, кое-что стоит упомянуть:
Самая большая по численности тем группа, почти 100. Много репозиториев оказались частными облачными хранилищами конфигураций для текстовых редакторов, особенно Vim и Emacs. Т.к. у Vim всего одна тема, в то время как у Emacs две, надеюсь, это поставит окончательную точку в споре какой редактор лучше!
Встретились сайты на всех известных веб движках, написанных на Python, Ruby, PHP, Java, Javascript и т.д. Сайты на PHP используют движки WordPress, Joomla, Yii, VTiger, Drupal, Zend, Cake и Symphony почему-то обязательно с Doctrine (по теме на каждый). Python: Django, Flask, Google AppEngine. Ruby: Rails и только Rails. Реееельсы [33]. Сайты на Java сколлапсировали в одну смешанную тему. И конечно же нашлось место сайтам на Node.js.
Оказалось, что много проектов используют Tesseract [34] — открытый движок OCR. Кроме того, многие используют Caffe [35] (и ни разу не Tensorflow).
Quake 3 / idTech 3 настолько популярен в геймдеве что заслужил отдельную тему. У Unity3D их две, причем первая в основной массе это сборище студенческих проектов и домашних поделок.
Cocos2D также популярен и получил 2 темы. Наконец, нашлись 3 темы про OpenGL + WebGL. Наверное, разница в способе работы с API и используемой обвязке (GLUT и т.п.).
Неудивительно, что Chef [36] — средство управления конфигурациями — поделил тему с готовкой еды (recipes, kitchen и т.п). Однако, WinAPI неожиданно оказался в одной теме с репозиториями про покемонов. Есть предположение, что стемминг сделал характерные имена WinAPI похожими на имена покемонов…
Много тем связаны с SDL [37], а также с Minecraft и RPG.
Мы приготовили образ Docker, чтобы любой желающий мог запустить нашу обученную модель на произвольном репозитории с GitHub. Нужно просто выполнить
docker run srcd/github_topics apache/spark
и вы увидите топ 5. Внутри образа зашита сериализованная матрица тем и слов, она доступна отдельно: link [11]. Формат — pickle 4-ой версии [38] с кортежем длины 2, первый элемент это Pandas 1.8+ SparseDataFrame [39], и второй — список с IDF. Кроме того, есть таблица OpenDocument [9] и JSON [10] с извлеченными темами.
Как уже было написано выше, 200 тем это слишком мало, много тем оказались двойственными, тройственными или слабо выраженными. При выполнении анализа «на чистовую» нам стоит выставить 500 или 1000, однако придется забыть о ручной маркировке тем. Трудно разобраться в бесконечном количестве тем PHP, если ты не в теме :). Мне определенно пригодилось многолетнее чтение статей на Хабре, и все равно я чувствовал себя некомфортно. Но все равно получилось интересно. Выдающееся достижение ARTM на мой взгляд — извлечение тем про людей, природу, науку и даже шаблоны проектирования всего лишь из имен в исходниках.
В планах добавить к модели файлы readme и возможно другие текстовые источники. Наверное, они усилят группу Понятия.
Майнинг исходного кода в трактовке классического машинного обучения (а не тяп ляп собрали метрик из AST и в продакшен) — штука новая, пока что не очень популярная, научных статей практически нет. В перспективе, мы хотим и примерно представляем как заменить часть программистов глубокой нейронной сетью, которая будет транслировать описание бизнес задач на естественном языке в код. Звучит фантастически, но технологии на самом деле созрели и если получится, произойдет революция покруче индустриализации. Людей катастрофически не хватает! Мы хайрим!
Основная трудность в этом деле — получить доступ к данным. GitHub API лимитирует число запросов у зарегистрированных пользователей числом 5000 в час, что конечно же мало, если хотим заполучить 18кк. Есть проект GHTorrent [40], но это лишь бледная тень тех данных, что собрали мы. Пришлось сделать особый конвейер на Go, который использует Go-Git [41] для сверхэффективного клонирования. Насколько нам известно, полная реплика GitHub есть у трех компаний: GitHub, SourceGraph [42] и source{d}.
Автор: markhor
Источник [43]
Сайт-источник PVSM.RU: https://www.pvsm.ru
Путь до страницы источника: https://www.pvsm.ru/open-source/200930
Ссылки в тексте:
[1] Тематическое моделирование: https://ru.wikipedia.org/wiki/%D0%A2%D0%B5%D0%BC%D0%B0%D1%82%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%BE%D0%B5_%D0%BC%D0%BE%D0%B4%D0%B5%D0%BB%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5
[2] мешком слов: https://en.wikipedia.org/wiki/Bag-of-words_model
[3] К. В. Воронцовым: http://www.machinelearning.ru/wiki/index.php?title=%D0%A3%D1%87%D0%B0%D1%81%D1%82%D0%BD%D0%B8%D0%BA:Vokov
[4] PDF: http://www.machinelearning.ru/wiki/images/e/e6/Voron-ML-TopicModeling-slides.pdf
[5] Латентное размещение Дирихле: https://ru.wikipedia.org/wiki/%D0%9B%D0%B0%D1%82%D0%B5%D0%BD%D1%82%D0%BD%D0%BE%D0%B5_%D1%80%D0%B0%D0%B7%D0%BC%D0%B5%D1%89%D0%B5%D0%BD%D0%B8%D0%B5_%D0%94%D0%B8%D1%80%D0%B8%D1%85%D0%BB%D0%B5
[6] аддитивной регуляризации: http://link.springer.com/article/10.1007/s10994-014-5476-6
[7] BigARTM: https://github.com/bigartm/bigartm
[8] source{d}: http://sourced.tech
[9] Таблица OpenDocument с извлеченными темами.: https://storage.googleapis.com/github-repositories-topic-modeling/topics.ods
[10] JSON с извлеченными темами.: https://storage.googleapis.com/github-repositories-topic-modeling/topics.json
[11] Обученная модель: https://storage.googleapis.com/github-repositories-topic-modeling/repo_topic_modeling.pickle.gz
[12] полной вероятности: https://ru.wikipedia.org/wiki/%D0%A4%D0%BE%D1%80%D0%BC%D1%83%D0%BB%D0%B0_%D0%BF%D0%BE%D0%BB%D0%BD%D0%BE%D0%B9_%D0%B2%D0%B5%D1%80%D0%BE%D1%8F%D1%82%D0%BD%D0%BE%D1%81%D1%82%D0%B8
[13] регуляризацию: https://ru.wikipedia.org/wiki/%D0%A0%D0%B5%D0%B3%D1%83%D0%BB%D1%8F%D1%80%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D1%8F_(%D0%BC%D0%B0%D1%82%D0%B5%D0%BC%D0%B0%D1%82%D0%B8%D0%BA%D0%B0)
[14] переобучение: https://ru.wikipedia.org/wiki/%D0%9F%D0%B5%D1%80%D0%B5%D0%BE%D0%B1%D1%83%D1%87%D0%B5%D0%BD%D0%B8%D0%B5
[15] метода максимального правдоподобия: https://ru.wikipedia.org/wiki/%D0%9C%D0%B5%D1%82%D0%BE%D0%B4_%D0%BC%D0%B0%D0%BA%D1%81%D0%B8%D0%BC%D0%B0%D0%BB%D1%8C%D0%BD%D0%BE%D0%B3%D0%BE_%D0%BF%D1%80%D0%B0%D0%B2%D0%B4%D0%BE%D0%BF%D0%BE%D0%B4%D0%BE%D0%B1%D0%B8%D1%8F
[16] EM-алгоритма: https://ru.wikipedia.org/wiki/EM-%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC
[17] RE·WORK: https://www.re-work.co/
[18] Берлин: https://goo.gl/4zq8g9
[19] Лондон: https://goo.gl/wRQCLS
[20] github/linguist: https://github.com/github/linguist
[21] Pygments: http://pygments.org/
[22] README.md: http://README.md
[23] Snowball: http://snowballstem.org/
[24] NLTK: http://www.nltk.org/
[25] TF-IDF: https://en.wikipedia.org/wiki/Tf%E2%80%93idf
[26] решения: https://www.quora.com/Why-is-the-performance-improved-by-using-TFIDF-instead-of-bag-of-words-in-LDA-clustering
[27] Dataproc: https://cloud.google.com/dataproc/
[28] gensim: https://radimrehurek.com/gensim/
[29] sklearn: http://scikit-learn.org/stable/
[30] Философия программирования 2 — Миф и язык: https://habrahabr.ru/post/247363/
[31] CSS: https://habrahabr.ru/company/ua-hosting/blog/269013/
[32] Moodle: https://moodle.org/
[33] Реееельсы: https://habrahabr.ru/post/301532/
[34] Tesseract: https://github.com/tesseract-ocr/tesseract
[35] Caffe: https://github.com/BVLC/caffe
[36] Chef: https://github.com/chef/chef
[37] SDL: http://www.libsdl.org/
[38] pickle 4-ой версии: https://docs.python.org/3/library/pickle.html#pickle-protocols
[39] SparseDataFrame: http://pandas.pydata.org/pandas-docs/stable/sparse.html?highlight=sparsedataframe
[40] GHTorrent: http://ghtorrent.org/
[41] Go-Git: https://github.com/src-d/go-git
[42] SourceGraph: https://sourcegraph.com/
[43] Источник: https://habrahabr.ru/post/312596/?utm_source=habrahabr&utm_medium=rss&utm_campaign=best
Нажмите здесь для печати.