[Перевод] Тематическое моделирование репозиториев на GitHub19.10.2016 20:33

Тематическое моделирование — подраздел машинного обучения, посвященный извлечению абстрактных «тем» из набора «документов». Каждый «документ» представлен мешком слов, т.е. множеством слов вместе с их частотами. Введение в тематическое моделирование прекрасно описано проф. К.В. Воронцовым в лекциях ШАД [PDF]. Самая известная модель ТМ — это, конечно, Латентное размещение Дирихле (LDA). Константину Вячеславовичу удалось обобщить все возможные тематические модели на основе мешка слов в виде аддитивной регуляризации (ARTM). В частности, LDA тоже входит в множество моделей ARTM. Идеи ARTM воплощены в проекте BigARTM.

Обычно тематическое моделирование применяют к текстовым документам. Мы в source{d} (стартап в Испании) перевариваем биг дату, полученную из GitHub репозиториев (и скоро примемся за каждый публично доступный репозиторий в мире). Естественным образом возникла идея интерпретировать каждый репозиторий как мешок слов и натравить BigARTM. В этой статье пойдет речь о том как мы выполнили по сути первое в мире тематическое исследование крупнейшего хранилища open source проектов, что из этого получилось и как это повторить. docker inside!

TL; DR:

docker run srcd/github_topics apache/spark

(заменить apache/spark на любой GitHub реп по желанию).

Таблица OpenDocument с извлеченными темами.
JSON с извлеченными темами.
Обученная модель — 40МБ, gzipped pickle для Python 3.4+, Pandas 1.18+.
Dataset на data.world — скоро загрузим.

Теория

Задана тематическая вероятностная модель на множестве документов $\inline D$ которая описывает частоту появления слова $\inline w$ в документе $\inline d$ с темами $\inline t$ :

$p(w|d) = \sum_{t\in T} p(w|t) p(t|d)$

где $\inline p(w|t)$ — вероятность отношения слова $\inline w$ к теме $\inline t$ , $\inline p(t|d)$ — вероятность отношения темы $\inline t$ к документу $\inline d$ , т.о. формула выше это просто выражение полной вероятности, при условии истинности гипотезы независимости случайных величин: $\inline p(w|d,t) = p(w|t)$ . Слова берутся из словаря $\inline W$ , темы принадлежат множеству $\inline T$ которое представляет собой просто серию индексов $\inline [1, 2, \dots n_t]$ .

Нам нужно восстановить $\inline p(w|t)$ и $\inline p(t|d)$ из заданного набора документов $\inline \left\{d\in D: d = \left\{w_1 \dots w_{n_d}\right\}\right\}$ . Обычно считают что $\inline \hat{p}(w|d) = \frac{n_{dw}}{n_d}$ , где $\inline n_{dw}$ — количество вхождений $\inline w$ в документ $\inline d$ , однако это подразумевает что все слова одинаково важные что не всегда справедливо. Под «важностью» здесь имеется в виду мера, негативно скоррелированная с общей частотой появления слова в документах. Обозначим восстанавливаемые вероятности $\inline \hat{p}(w|t) = \phi_{wt}$ и $\inline \hat{p}(t|d) = \theta_{td}$ . Т.о. наша задача сводится к стохастическому матричному разложению, которая некорректно поставлена:

$\frac{n_{dw}}{n_d} ≈ \Phi \cdot \Theta = (\Phi S)(S^{-1}\Theta) = \Phi' \cdot \Theta'$

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

Задачи наподобие описанной выше решаются с помощью метода максимального правдоподобия:

$\sum_{d\in D}\sum_{w\in d}n_{dw}\ln \sum_{t}\phi_{wt} \theta_{td} \to \max_{\Phi,\Theta}$

при условиях

$\phi_{wt} > 0; \sum_{w\in W}\phi_{wt} = 1; \theta_{td} > 0; \sum_{t\in T}\theta_{td} = 1.$

Суть ARTM в том чтобы естественным образом добавить регуляризацию в виде дополнительных слагаемых:

$\sum_{d\in D}\sum_{w\in d}n_{dw}\ln \sum_{t}\phi_{wt} \theta_{td} + R(\Phi,\Theta) \to \max_{\Phi,\Theta}$

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

$R(\Phi,\Theta)_{Dirichlet} = \sum_{t,w} (\beta_w - 1)\ln \phi_{wt} + \sum_{d,t} (\alpha_t - 1)\ln \theta_{t,d}$

Переменные $\inline \Phi$ и $\inline \Theta$ могут быть эффективно вычислены с помощью итеративного EM-алгоритма. Десятки готовых ARTM регуляризаторов готовы к бою в составе BigARTM.

На этом вынужденный рерайт лекции ШАДа заканчивается и начинается

Практика

Для анализа на октябрь 2016 года были доступны около 18 миллионов репозиториев на GitHub. Их на самом деле гораздо больше, просто мы отбросили форки и «хард форки» (форк не отмечен GitHub-ом). Положим каждый репозиторий это $d$ , а каждое имя в исходниках это $w$ . Анализ исходников делался теми же инструментами, что и при глубоком обучении исходному коду в ранних экспериментах (см. наши презентации с последних конференций RE·WORK: Берлин и Лондон): первичная классификация github/linguist-ом и парсинг на основе Pygments. Текстовые файлы общего назначения отбрасывались, например README.md.

Имена из исходников следует извлекать не «в лоб», например, class FooBarBaz добавляет 3 слова в мешок: foo, bar и baz, а int wdSize добавляет два: wdsize и size. Кроме того, имена стеммировались Snowball-ом из NLTK, хотя специально мы не исследовали пользу от этого. Последний этап предобработки заключался в вычислении логарифмической версии TF-IDF взвешивания (снова, специально не исследовали, просто копировали решения из обычного НЛП) и фильтрации слишком редких и общеупотребительных имен, в нашем случае, границы были 50 и 100000 соответственно.
После того как ARTM выдал результат, нужно было вручную дать имена темам, основываясь на ключевых словах и репозиториях-представителях. Число тем было выставлено в 200, и как потом оказалось, нужно было поставить больше, т.к. тем на Гитхабе очень много. Нудная работа отняла целую неделю.

Предобработка была выполнена на Dataproc 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 и, прости господи, sklearn.

Темы

В итоге, 200 тем можно поделить на следующие группы:

Понятия — общие, гирокие и абстрактные.
Человеческие языки — оказалось, что по коду можно примерно определить родной язык программиста, наверное, отчасти благодаря смещению от стемминга.
Языки программирования — не то чтобы интересные, т.к. эту информацию мы и так знаем. У ЯП обычно есть стандартная библиотека aka «батарейки» из классов и функций, которые импортируются/включаются в исходники, и соответствующие имена детектируются нашим тематическим моделированием. Некоторые темы оказались у́же чем ЯП.
Общий IT — попали бы в Понятия если имели выразительный список ключевых слов. Репозитории часто ассоциируются с уникальным набором имен, например, говорим Рельсы, держим в уме ActiveObject и прочий Active. Частично перекликается с Философия программирования 2 — Миф и язык.
Сообщества — посвященные конкретным, потенциально узким технологиям или продуктам.
Игры.
Бред — 2 темам так и не удалось найти разумное объяснение.

Понятия

Пожалуй, самая интересная группа с кучей извлеченных фактов из повседневной жизни:

В пицце есть сыр, а еще ее упоминают многие репозитории.
Термины из математики, линейной алгебры, криптографии, машинного обучения, цифровой обработки сигналов, генной инженерии, физики элементарных частиц.
Дни недели. Monday, Tuesday и т.д.
Всевозможные факты и персонажи из RPG и других игр в жанре фэнтези.
В IRC есть псевдонимы.
Множество шаблонов проектирования (говорим за них спасибо Java и PHP).
Цвета. Включая некоторые экзотические (говорим за них спасибо CSS).
В электронной почте есть CC, BCC, и ее посылают протоколом SMTP и получают POP/IMAP-ом.
Как создать хороший datetime picker. Кажется, это весьма типичный проект на GitHub, хе-хе.
Люди работают за деньги и тратят их на покупку домов и вождение (очевидно, из дома на работу и назад).
Всевозможное «железо».
Исчерпывающий список терминов HTTP, SSL, Internet, Bluetooth и WiFi.
Все что вы хотели бы узнать про управление памятью.
Что гуглить есть хочется сделать свою прошивку на основе Android.
Штрихкоды. Огромное число разных видов.
Люди. Они делятся на мужчин и женщин, они живут и занимаются сексом.
Отличный список текстовых редакторов.
Погода. Много типичных слов.
Открытые лицензии. Вообще говоря, они не должны были попасть в отдельную тему т.к. имена и тексты лицензий в теории не пересекаются. По опыта работы с Pygments, некоторые ЯП поддерживаются гораздо хуже чем другие и, судя по всему, некоторые были неправильно распарсены.
Коммерция. У магазины предлагают скидки и продают товары покупателям.
Биткоины и блокчейн.

Человеческие языки

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

Языки программирования

Интересная находка в ЯП — это тема «Non-native English PHP», ассоциированная с проектами на PHP, не написанными людьми, знающими английский. Видимо, эти две группы программистов как-то принципиально по-разному пишут код. Кроме того, есть две темы, относящиеся к Java: JNI и байткод.

Общий IT

Здесь не так интересно. Существует много репозиториев с ядрами ОС — большие, шумные и несмотря на наши старания они изгадили некоторые топики. Тем не менее, кое-что стоит упомянуть:

Много информации о дронах. Они работают на Linux.
Есть много реализаций Ruby. Часто встречаются «экстремальные форки», когда люди берут чужую кодовую базу и комиттят единым целым с потерей истории изменений.
onmouseup, onmousedown и onmousemove — три гиганта, на которых стоит UI.
Огромное число баззвордов и технологий из мира Javascript.
Платформы для онлайн обучения. Особенно Moodle. Много, много Moodle.
Все когда-либо созданные открытые CMS.
Тема «Coursera Machine Learning» предоставляет отличный список репозиториев с домашней работой на курсах Coursera, посвященных машинному обучению.

Сообщества

Самая большая по численности тем группа, почти 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. Реееельсы. Сайты на Java сколлапсировали в одну смешанную тему. И конечно же нашлось место сайтам на Node.js.

Оказалось, что много проектов используют Tesseract — открытый движок OCR. Кроме того, многие используют Caffe (и ни разу не Tensorflow).

Quake 3 / idTech 3 настолько популярен в геймдеве что заслужил отдельную тему. У Unity3D их две, причем первая в основной массе это сборище студенческих проектов и домашних поделок.
Cocos2D также популярен и получил 2 темы. Наконец, нашлись 3 темы про OpenGL + WebGL. Наверное, разница в способе работы с API и используемой обвязке (GLUT и т.п.).

Неудивительно, что Chef — средство управления конфигурациями — поделил тему с готовкой еды (recipes, kitchen и т.п). Однако, WinAPI неожиданно оказался в одной теме с репозиториями про покемонов. Есть предположение, что стемминг сделал характерные имена WinAPI похожими на имена покемонов…

Игры

Много тем связаны с SDL, а также с Minecraft и RPG.

Что можно скачать

Мы приготовили образ Docker, чтобы любой желающий мог запустить нашу обученную модель на произвольном репозитории с GitHub. Нужно просто выполнить

docker run srcd/github_topics apache/spark

и вы увидите топ 5. Внутри образа зашита сериализованная матрица тем и слов, она доступна отдельно: link. Формат — pickle 4-ой версии с кортежем длины 2, первый элемент это Pandas 1.8+ SparseDataFrame, и второй — список с IDF. Кроме того, есть таблица OpenDocument и JSON с извлеченными темами.

Выводы

Как уже было написано выше, 200 тем это слишком мало, много тем оказались двойственными, тройственными или слабо выраженными. При выполнении анализа «на чистовую» нам стоит выставить 500 или 1000, однако придется забыть о ручной маркировке тем. Трудно разобраться в бесконечном количестве тем PHP, если ты не в теме:). Мне определенно пригодилось многолетнее чтение статей на Хабре, и все равно я чувствовал себя некомфортно. Но все равно получилось интересно. Выдающееся достижение ARTM на мой взгляд — извлечение тем про людей, природу, науку и даже шаблоны проектирования всего лишь из имен в исходниках.

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

P.S.

Майнинг исходного кода в трактовке классического машинного обучения (а не тяп ляп собрали метрик из AST и в продакшен) — штука новая, пока что не очень популярная, научных статей практически нет. В перспективе, мы хотим и примерно представляем как заменить часть программистов глубокой нейронной сетью, которая будет транслировать описание бизнес задач на естественном языке в код. Звучит фантастически, но технологии на самом деле созрели и если получится, произойдет революция покруче индустриализации. Людей катастрофически не хватает! Мы хайрим!

Основная трудность в этом деле — получить доступ к данным. GitHub API лимитирует число запросов у зарегистрированных пользователей числом 5000 в час, что конечно же мало, если хотим заполучить 18кк. Есть проект GHTorrent, но это лишь бледная тень тех данных, что собрали мы. Пришлось сделать особый конвейер на Go, который использует Go-Git для сверхэффективного клонирования. Насколько нам известно, полная реплика GitHub есть у трех компаний: GitHub, SourceGraph и source{d}.