Тематичне моделювання репозиторіїв на GitHub

word cloud
Тематичне моделювання — підрозділ машинного навчання, присвячений вилучення абстрактних «тим» з набору «документів». Кожен «документ» представлений мішком слів, тобто безліччю слів разом з їх частотами. Введення в тематичне моделювання чудово описано проф. К. В. Воронцовим в лекціях ШАД [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)_{Діріхле} = \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 ГБ, і її довелося перетворити в текстовий формат 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 тем так і не вдалося знайти розумне пояснення.
Поняття
Мабуть, найцікавіша група з купою вилучені фактів з повсякденного життя:
  1. В піці є сир, а ще її згадують багато репозиторії.
  2. Терміни з математики, лінійної алгебри, криптографії, машинного навчання, цифрової обробки сигналів, генної інженерії, фізики елементарних частинок.
  3. Дні тижня. Monday, Tuesday і т. д.
  4. Всілякі факти і персонажі з RPG і інших ігор в жанрі фентезі.
  5. В IRC є псевдоніми.
  6. Безліч шаблонів проектування (говоримо за них дякую Java та PHP).
  7. Кольори. Включаючи деякі екзотичні (говоримо за них спасибі CSS).
  8. електронній пошті є CC, BCC, і її посилають протоколом SMTP і отримують POP/IMAP-ом.
  9. Як створити хороший datetime picker. Здається, це досить типовий проект на GitHub, хе-хе.
  10. Люди працюють за гроші і витрачають їх на покупку будинків і водіння (очевидно, з будинку на роботу і назад).
  11. Всіляке «залізо».
  12. Вичерпний список термінів HTTP, SSL, Internet, Bluetooth і WiFi.
  13. Все що ви хотіли б дізнатися про управління пам'яттю.
  14. Що гуглити їсти хочеться зробити свою прошивку на основі Android.
  15. штрих-коди. Величезне число різних видів.
  16. Люди. Вони діляться на чоловіків і жінок, вони живуть і займаються сексом.
  17. Відмінний список текстових редакторів.
  18. Погода. Багато типових слів.
  19. Відкриті ліцензії. Взагалі кажучи, вони не повинні були потрапити в окрему тему т. к. імена і тексти ліцензій в теорії не перетинаються. З досвіду роботи з Pygments, деякі МП підтримуються набагато гірше, ніж інші, і, судячи з усього, деякі були неправильно распарсены.
  20. Комерція. У магазини пропонують знижки і продають товари покупцям.
  21. Биткоины і блокчейн.
Людські мови
В список тем увійшли іспанська, португальська, французька і китайський. Російська в окрему тему не сформувався, що свідчить швидше про більш високому рівні наших програмістів на 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}.
Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.