Category: Алгоритмы

13
Окт
2021

☕ Распространенные алгоритмы и структуры данных в JavaScript: стеки, очереди и связные списки

Продолжая серию статей об алгоритмах и структурах данных в JavaScript, рассмотрим другие линейные (массивоподобные) структуры – стеки, очереди и связные списки.

08
Окт
2021

Конференция HighLoad++ 2021

Крупнейшая в Европе IT-конференция для разработчиков высоконагруженных систем. В программе более 130 докладов, персональные консультации и полезные знакомства.
— Читать дальше «Конференция HighLoad++ 2021»

06
Окт
2021

☕ Распространенные алгоритмы и структуры данных в JavaScript: основные понятия и работа с массивами

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

27
Сен
2021

Идеи динамического программирования: одномерные задачи, часть 2

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

27
Сен
2021

Идеи динамического программирования: одномерные задачи, часть 2

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

22
Сен
2021

Идеи динамического программирования: одномерные задачи, часть 1

Разбираем несколько классических задач динамического программирования с использованием одномерного массива и без него.
— Читать дальше «Идеи динамического программирования: одномерные задачи, часть 1»

08
Сен
2021

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

Директор по технологии IVI рассказывает, что такое хайлайты в онлайн-кинотеатрах, зачем их показывают и как создают.
— Читать дальше ««Кому-то больше понравится сцена со взрывом, кому-то — с поцелуем»: что такое хайлайты в онлайн-кинотеатрах и какие ал…

12
Авг
2021

Онлайн-хакатон «Цифровой форсаж атомных городов»

Командам предстоит решать задачи и предлагать идеи по улучшению цифрового сервиса в «атомных» городах. Призовой фонд — 1 млн рублей.
— Читать дальше «Онлайн-хакатон «Цифровой форсаж атомных городов»»

12
Авг
2021

🤖 Машинное обучение для начинающих: алгоритм случайного леса (Random Forest)

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

Алгоритм случайного леса (Random Forest) — универсальный алгоритм машинного обучения, суть которого состоит в использовании ансамбля решающих деревьев. Само по себе решающее дерево предоставляет крайне невысокое качество классификации, но из-за большого их количества результат значительно улучшается. Также это один из немногих алгоритмов, который можно использовать в абсолютном большинстве задач.

В каких задачах используется?

Благодаря своей гибкости Random Forest применяется для решения практически любых проблем в области машинного обучения. Сюда относятся классификации (RandomForestClassifier) и регрессии (RandomForestRegressor), а также более сложные задачи, вроде отбора признаков, поиска выбросов/аномалий и кластеризации.

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

        import pandas as pd 
from sklearn.ensemble  import RandomForestClassfier 
from sklearn.feature_selection import SelectFromModel 
X_train,y_train,X_test,y_test = train_test_split(data,test_size=0.3)
 sel = SelectFromModel(RandomForestClassifier(n_estimators = 100)) 
sel.fit(X_train, y_train)
    

Здесь мы на основе классификации просто добавляем метод для отбора признаков.

Порядок действий в алгоритме

  • Загрузите ваши данные.
  • В заданном наборе данных определите случайную выборку.
  • Далее алгоритм построит по выборке дерево решений.
  • Дерево строится, пока в каждом листе не более n объектов, или пока не будет достигнута определенная высота.
  • Затем будет получен результат прогнозирования из каждого дерева решений.
  • На этом этапе голосование будет проводиться для каждого прогнозируемого результата: мы выбираем лучший признак, делаем разбиение в дереве по нему и повторяем этот пункт до исчерпания выборки.
  • В конце выбирается результат прогноза с наибольшим количеством голосов. Это и есть окончательный результат прогнозирования.

Теоретическая составляющая алгоритма случайного дерева

По сравнению с другими методами машинного обучения, теоретическая часть алгоритма Random Forest проста. У нас нет большого объема теории, необходима только формула итогового классификатора a(x):


Где

  • N – количество деревьев;
  • i – счетчик для деревьев;
  • b – решающее дерево;
  • x – сгенерированная нами на основе данных выборка.

Стоит также отметить, что для задачи классификации мы выбираем решение голосованием по большинству, а в задаче регрессии – средним.

Реализация алгоритма Random Forest

Реализуем алгоритм на простом примере для задачи классификации, используя библиотеку scikit-learn:

        class sklearn.ensemble.RandomForestClassifier(n_estimators=10, criterion='gini', max_depth=None, min_samples_split=2, min_samples_leaf=1, min_weight_fraction_leaf=0.0, max_features='auto', max_leaf_nodes=None, min_impurity_split=1e-07, bootstrap=True, oob_score=False, n_jobs=1, random_state=None, verbose=0, warm_start=False, class_weight=None)
    

Работаем с алгоритмом по стандартному порядку действий, принятому в scikit-learn. Вычисляем AUC-ROC (площадь под кривой ошибок) для тренировочной и тестовой частей модели, чтобы определить ее качество:

        from sklearn.ensemble import RandomForestRegressor 
from sklearn.metrics import roc_auc_score 
# далее - (X, y) - для обучения, (X2, y2) - для контроля
# модель - регрессор 
model =  RandomForestRegressor(n_estimators=10,                              
                               oob_score=True,
                               random_state=1) 
model.fit(X, y) # обучение 
a = model.predict(X2) # предсказание  
print ("AUC-ROC (oob) = ", roc_auc_score(y, model.oob_prediction_)) 
print ("AUC-ROC (test) = ", roc_auc_score(y2, a))
    

Необходимые параметры алгоритма

Число деревьев – n_estimators

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

Часто при большом увеличении n_estimators качество на обучающей выборке может даже доходить до 100%, в то время как качество на тесте выходит на асимптоту, что сигнализирует о переобучении нашей модели. Лучший способ избежать этого – прикинуть, сколько деревьев вам достаточно, зафиксировав момент, когда качество теста еще не становится стабильно-неизменным.

Критерий расщепления – criterion

Также один из самых важных параметров для построения, но без значительной возможности выбора. В библиотеке sklearn для задач классификации реализованы критерии gini и entropy. Они соответствуют классическим критериям расщепления: джини и энтропии.

В свою очередь, для задач регрессии реализованы два критерия (mse и mae), которые являются функциями ошибок Mean Square Error и Mean Absolute Error соответственно. Практически во всех задачах используется критерий mse.

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

Число признаков для выбора расщепления – max_features

При увеличении max_features увеличивается время построения леса, а деревья становятся похожими друг на друга. В задачах классификации он по умолчанию равен sqrt(n), в задачах регрессии – n/3.

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

Минимальное число объектов для расщепления – min_samples_split

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

Ограничение числа объектов в листьях – min_samples_leaf

Аналогично с min_samples_split, но при увеличении данного параметра качество модели на обучении падает, в то время как время построения модели сокращается.

Максимальная глубина деревьев – max_depth

Чем меньше максимальная глубина, тем быстрее строится и работает алгоритм случайного дерева.

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

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

Преимущества алгоритма


  • Имеет высокую точность предсказания, которая сравнима с результатами градиентного бустинга.
  • Не требует тщательной настройки параметров, хорошо работает из коробки.
  • Практически не чувствителен к выбросам в данных из-за случайного семплирования (random sample).
  • Не чувствителен к масштабированию и к другим монотонным преобразованиям значений признаков.
  • Редко переобучается. На практике добавление деревьев только улучшает композицию.
  • В случае наличия проблемы переобучения, она преодолевается путем усреднения или объединения результатов различных деревьев решений.
  • Способен эффективно обрабатывать данные с большим числом признаков и классов.
  • Хорошо работает с пропущенными данными – сохраняет хорошую точность даже при их наличии.
  • Одинаково хорошо обрабатывает как непрерывные, так и дискретные признаки
  • Высокая параллелизуемость и масштабируемость.

Недостатки алгоритма


  • Для реализации алгоритма случайного дерева требуется значительный объем вычислительных ресурсов.
  • Большой размер моделей.
  • Построение случайного леса отнимает больше времени, чем деревья решений или линейные алгоритмы.
  • Алгоритм склонен к переобучению на зашумленных данных.
  • Нет формальных выводов, таких как p-values, которые используются для оценки важности переменных.
  • В отличие от более простых алгоритмов, результаты случайного леса сложнее интерпретировать.
  • Когда в выборке очень много разреженных признаков, таких как тексты или наборы слов (bag of words), алгоритм работает хуже чем линейные методы.
  • В отличие от линейной регрессии, Random Forest не обладает возможностью экстраполяции. Это можно считать и плюсом, так как в случае выбросов не будет экстремальных значений.
  • Если данные содержат группы признаков с корреляцией, которые имеют схожую значимость для меток, то предпочтение отдается небольшим группам перед большими, что ведет к недообучению.
  • Процесс прогнозирования с использованием случайных лесов очень трудоемкий по сравнению с другими алгоритмами.

Заключение

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

Действенный и простой в понимании, алгоритм имеет значительный недостаток – заметное замедление работы при определенной настройке параметров внутри него.

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

Дополнительные материалы:

09
Авг
2021

Teleperformance заставляет удалённых сотрудников устанавливать дома камеры для контроля эффективности

Компания Teleperformance внедряет систему видеоконтроля за сотрудниками для мониторинга их эффективности. Камеры будут записывать видео и звук.
— Читать дальше «Teleperformance заставляет удалённых сотрудников устанавливать дома камеры для контроля эфф…

09
Авг
2021

👨‍🎓️ Нужны ли программисту математика, английский язык, теория алгоритмов и паттерны проектирования?

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

Разумеется, ответить на такие вопросы может только программист с большим опытом работы. Поэтому писать эту статью доверили именно мне – разработчику со стажем в 28 лет (C++, Delphi, C#), чьи первые продаваемые программы работали еще под MS-DOS. И математику, и английский, и алгоритмы, и проектирование я знаю очень хорошо – но это не сделало меня не только тимлидом, но даже “сеньором”. Так что я не собираюсь вас убеждать, что без всего этого ваша карьера обречена. Способность быстро написать работающий код, который потребовало начальство, было и остается самой важной способностью программиста. Конечно, оценить качество этого кода сумеют немногие, и ваше начальство едва ли входит в их число, зато оно наверняка оценит вашу исполнительность.

Иногда возникают нюансы. Вам приходится не только писать код, но и формализовать задачу, поставленную заказчиком на манер знаменитого “копать от забора и до обеда”. Или ваш код, написанный “на коленке” за пару минут, работает слишком медленно. Или ваша программа выдает исключение, давно описанное на stackoverflow.com, но вы не умеете читать по-английски. Или возникает необходимость сделать рефакторинг кода, а для вас это звучит как “харакири”. Как правило, начальству наплевать на то, как вы справитесь с этими проблемами, но справиться вы обязаны – “вы же программист”! За что же вам платят эдакие деньжищи?

Математика

Давным-давно, когда компьютеры были большими, а зарплаты программистов – маленькими, каждый программист был математиком. Помните главного героя “Понедельника начинается в субботу” братьев Стругацких, программиста Сашу Привалова?


– Кристобаль Хозевич, – сказал я. – Я ее все-таки решил. Вы были совершенно правы. Пространство заклинаний действительно можно свернуть по любым четырем переменным…
…Я отдал ему листки, он сел рядом со мною, и мы вместе разобрали задачу с начала и до конца и с наслаждением просмаковали два изящнейших преобразования, одно из которых подсказал мне он, а другое нашел я сам…

Это мы опубликуем. Это никому не стыдно опубликовать.

Аркадий и Борис Стругацкие, «Понедельник начинается в субботу»

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

В моем дипломе, полученном на факультете прикладной математики, гордо значится специальность – математик. Хотя все понимали, что нас учат на программистов. Нас научили использовать численные методы для решения сложных задач, которые нельзя решить аналитически – например, уравнения теплопроводности. Пригодилось ли это на практике? Пока нет, но еще может пригодиться. Если говорить о нужности для программиста, всю высшую математику можно разделить на три части:

  1. То, что вы будете использовать каждый день: дискретная математика. О ней мы сейчас поговорим подробнее.
  2. То, что вам нужно для решения возникающих математических задач: дифференциальное и интегральное исчисление, линейная алгебра, статистика. Эти разделы математики используются не каждый день, а у многих программистов – даже не каждый год, но знать их все равно очень полезно, а во многих компаниях – даже необходимо. Почему? Если вам хоть изредка приходится ставить математическую постановку задачи – вы просто не сможете этого сделать без соответствующей математической базы. Имея базу, вы сможете найти информацию о своей задаче в Интернете и использовать ее, а без базы вы эту информацию просто не поймете!
  3. Специфические знания. Нужны только для решения задач из определенной прикладной области. Если вы пишете программы именно в этой области – знание необходимых разделов математики будет огромным плюсом, а если не пишете – эти разделы вам не нужны.

Дискретная математика

Этот раздел математики изучает конечные структуры и содержит множество различных подразделов. Самый важный подраздел для программистов – это математическая логика, в которую входит обработка привычных каждому программисту логических операций вроде and, or, и not. Например, следующий оператор срабатывает, если верно a, но не b, или, наоборот, верно b, но не a:

        if ((a && !b) || (!a && b))
{
   // Сделаем что-нибудь
}
    

Если вы изучали дискретную математику, то сразу поймете, что то же самое можно написать гораздо проще, используя операцию “исключающее ИЛИ”, причем код будет не только намного короче, но и станет работать быстрее:

        if (a ^ b)
{
   // Сделаем что-нибудь
}
    

Математическая логика также помогает “инвертировать” логические выражения или упрощать их, что может потребоваться программисту буквально каждый день:

        // Сложное логическое выражение
if ((a || b) && (c || !b))
{
}
// Инвертированное логическое выражение
if ((!a && !b) || (!c && b))
{
}
    

Еще один важнейший раздел дискретной математики для программистов – это теория графов. Если слово “граф” для вас ассоциируется с графом Монте-Кристо, а не со структурой данных, состоящей из вершин и соединяющих их ребер, вы рискуете не только провалиться на любом собеседовании, но еще и опозориться:

С чем должно ассоциироваться слово "граф" для программиста
С чем должно ассоциироваться слово “граф” для программиста

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

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

Для освоения всей дискретной математики вам будет достаточно всего одной книги: “Дискретной математики для программистов” Рона Хаггарти. Было бы очень здорово, если бы все пробелы в нашем образовании можно было закрыть, изучив всего одну книгу, правда? Пробелы в школьных знаниях поможет закрыть наш онлайн-марафон, а если вам нужны и другие области математики, например, чтобы изучить науку о данных, можно начать с курса «Библиотеки программиста».

Английский язык


Ду ю спик инглиш? Говорите, “академиев не кончали”? Не страшно! Из четырех основных навыков, проверяемых на серьезных экзаменах по языку (чтение, сочинение, разговор и аудирование) программисту достаточно только первого – чтения, но при этом читать придется не Агату Кристи, а техническую литературу по специальности, что намного труднее.

Если вы не умеете быстро и без напряжения читать книги по программированию на английском языке – это значит, что вы просто не сможете постоянно следить за передним краем даже в своей области, не говоря уже о смежных. Конечно, российские издательства выпускают переводы книг по программированию, но к моменту их выхода на Западе уже успевает выйти новое издание. К тому же качество этих переводов настолько плохое, что я предпочитаю читать книги в оригинале, то есть на английском. Зачастую электронные версии самых свежих книг на английском языке появляются задолго до их печати, то есть я могу осваивать новые технологии одновременно со всем миром. К тому же, книг по программированию выходит так много, что далеко не каждая из них вообще будет переведена на русский!

Иногда вам придется и написать абзац-другой – например, задать вопрос на форуме или в отдел технической поддержки. Поскольку писать сочинения вроде “London is the capital of Great Britain” вам едва ли понадобится, это не должно вызвать особых трудностей, если вы уже хорошо умеете читать. Даже если вы сделаете пару ошибок, не страшно – лишь бы вас правильно поняли.

Многие фирмы работают на Запад, и там регулярно проводятся совещания на английском языке. Вот там вам уже понадобятся и разговорные навыки, и аудирование, и даже хорошее произношение. Такие фирмы прямо пишут в своих вакансиях что-то вроде “English – Upper-Intermediate”. Высококлассному специалисту с большим опытом должно быть очень обидно упускать такие вакансии только из-за незнания языка.


С другой стороны, многие фирмы устраивают своим сотрудникам бесплатные курсы английского языка. Не упускайте эту возможность! Знание языка – это не излишество, а необходимость. Несмотря на то, что сам код можно писать, не зная даже английского алфавита.

Научиться говорить и воспринимать английский на слух по книгам невозможно – для этого гораздо лучше подойдут учебные видео. А вот научиться читать с помощью книг можно – см. например, “English Through Reading“.

Теория алгоритмов


Как вы думаете, чем тимлид отличается от джуниора? Нет, не выслугой лет, и не заслугами перед компанией. Настоящий тимлид обязан отлично знать теорию алгоритмов и хорошо разбираться в проектировании. Почему? Да потому, что в большинстве компаний нет выделенных проектировщиков (в Штатах их обычно называют “архитекторами программ”, software architect), и никто выше тимлида не способен принять правильное решение о том, каким должен быть продукт, и как его следует писать. Впрочем, о проектировании мы поговорим чуть ниже, а сейчас речь о теории алгоритмов.
Алгоритм – это метод решения задачи. Он может быть правильным (если программа во всех случаях работает правильно) или неправильным – если она работает правильно не всегда. Он также может быть эффективным (если программа затрачивает минимально возможное количество ресурсов, особенно времени и оперативной памяти) или неэффективным, если намного больше.

Теория алгоритмов оценивает не точное количество ресурсов (которое на практике редко можно рассчитать), а характер его зависимости от размеров исходных данных, называемой сложностью. Например, цикл по всем элементам массива имеет вычислительную сложность O(N), где N – количество элементов массива. Это значит, что количество вычислительных операций пропорционально N. Общеизвестно, что сложность быстрой сортировки (в среднем) равна O(N * logN), а сложность бинарного поиска – O(log N). Поиск в хеш-таблице происходит еще быстрее: при правильно подобранных ключах и достаточном размере таблицы его сложность O(1), то есть вообще не зависит от размера входных данных! Этим и обусловлена широкая популярность хеш-таблиц, а также базирующихся на них словарей (dictionary) и множеств (set).

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

Теоретически, вы можете писать код, и не зная об алгоритмах, но это будет код школьника-троечника. Причем страшнее всего то, что вы этого даже не почувствуете! Если вам не хватает английского языка – это всегда очевидно: вы не можете понять текст, постоянно лезете в словарь, или, что еще хуже, пользуетесь автоматическим переводчиком. Если вам не хватает математической подготовки – вы, конечно, не сможете обнаружить нехватку самостоятельно, но хотя бы почувствуете, что чего-то не понимаете. А вот люди, ничего не знающие об алгоритмах, не получают никаких “звоночков”. Они успешно пишут код, который прекрасно проходит все тесты (поскольку размер данных в тестах обычно невелик), но у пользователя работать не будет.

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

Хороших книг по теории алгоритмов очень много. Начать стоит с учебника С.М. Окулова “Программирование в алгоритмах“, доступного даже для школьников. Если вы по-настоящему любите математику, возьмитесь за классическую книгу Дональда Кнута “Искусство программирования” – там вы найдете не только описания алгоритмов, но и доказательства сложности многих из них. Ну, а если вы умеете читать по-английски и уже знаете основы теории – беритесь за “Продвинутые алгоритмы и структуры данных” Марчелло Ла Рокка.

Паттерны проектирования


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

Пожалуй, впервые важность проектирования была продемонстрирована в книге Ф.Брукса “Мифический человеко-месяц”, вышедшей в далеком 1975-м, но она была ориентирована на менеджеров, а не на программистов. В 1994-м Э. Гамма, Р. Хелм, Р. Джонсон и Д. Влиссидес (называемые “бандой четырех”, “Gang of Four”) опубликовали книгу “Паттерны объектно-ориентированного проектирования“, заложившую основы современного подхода к проектированию ПО. В книге описано множество типовых приемов (которые авторы назвали “паттернами”), помогающих улучшить проекты проекты программ, и это стало основным фактором ее популярности. Стало модно задавать вопросы по паттернам проектирования на собеседованиях, и юные соискатели начали заучивать их наизусть. (Я не рассматриваю SOLID, появившийся позднее, поскольку он слабо помогает проектировать – но заучить его для собеседований вам тоже придется).

К сожалению, навыки кодирования и проектирования очень сильно отличаются друг от друга, так что гениальный проектировщик вряд ли окажется еще и супер-кодировщиком (а когда такое все же случается, в мире появляется очередной Линус Торвальдс). Типичный кодировщик – это юноша, очень быстро набирающий код, то есть обдумывающий его еще быстрее. Типичный проектировщик – это человек с большим опытом, который может не набрать ни одной строки кода на протяжении нескольких дней или даже недель. Его задача – придумать наилучшую архитектуру продукта, вот он и думает. Разумеется, кодировщики, ничего не знающие о проектировании, считают проектировщика просто бездельником! Именно поэтому крупные компании не ставят проектировщика в подчинение руководителю команды кодировщиков, а придумывают для него особую должность “архитектора” (software architect).

Так понадобятся ли вам “паттерны проектирования”? Как проектировщик с огромным опытом, ответственно заявляю: вам понадобятся не только они, но и глубокое понимание проектирования в целом. Ведь паттерны проектирования – это всего лишь несколько типовых ситуаций и подходов к их проектированию. Даже если выучить их наизусть, проектировщиком это вас все равно не сделает – ведь умение забивать гвозди и вкручивать шурупы еще не делает человека столяром. Как минимум, нужно еще понимать, в каких случаях стоит использовать каждый паттерн, а в каких не стоит, и каких целей он помогает достичь – иначе вы будете забивать шурупы молотком и думать, что правильно применили паттерн.

Отличный пример широко распространенного, но неправильного понимания паттерна проектирования дает паттерн Bridge (Мост). Начнем с правильного примера использования этого паттерна на C# (код взят из документации Microsoft):

        using System;
using System.Data;

namespace IDbConnectionSample {
   class Program {
      static void Main(string[] args) {
         IDbConnection connection;

         // First use a SqlClient connection
         connection = new System.Data.SqlClient.SqlConnection(@"Server=(localdb)\V11.0");
         Console.WriteLine("SqlClient\r\n{0}", GetServerVersion(connection));
         connection = new System.Data.SqlClient.SqlConnection(@"Server=(local);Integrated Security=true");
         Console.WriteLine("SqlClient\r\n{0}", GetServerVersion(connection));

         // Call the same method using ODBC
         // NOTE: LocalDB requires the SQL Server 2012 Native Client ODBC driver
         connection = new System.Data.Odbc.OdbcConnection(@"Driver={SQL Server Native Client 11.0};Server=(localdb)\v11.0");
         Console.WriteLine("ODBC\r\n{0}", GetServerVersion(connection));
         connection = new System.Data.Odbc.OdbcConnection(@"Driver={SQL Server Native Client 11.0};Server=(local);Trusted_Connection=yes");
         Console.WriteLine("ODBC\r\n{0}", GetServerVersion(connection));

         // Call the same method using OLE DB
         connection = new System.Data.OleDb.OleDbConnection(@"Provider=SQLNCLI11;Server=(localdb)\v11.0;Trusted_Connection=yes;");
         Console.WriteLine("OLE DB\r\n{0}", GetServerVersion(connection));
         connection = new System.Data.OleDb.OleDbConnection(@"Provider=SQLNCLI11;Server=(local);Trusted_Connection=yes;");
         Console.WriteLine("OLE DB\r\n{0}", GetServerVersion(connection));
         }

      public static string GetServerVersion(IDbConnection connection) {
         // Ensure that the connection is opened (otherwise executing the command will fail)
         ConnectionState originalState = connection.State;
         if (originalState != ConnectionState.Open)
            connection.Open();
         try {
            // Create a command to get the server version
            // NOTE: The query's syntax is SQL Server specific
            IDbCommand command = connection.CreateCommand();
            command.CommandText = "SELECT @@version";
            return (string)command.ExecuteScalar();
         }
         finally {
            // Close the connection if that's how we got it
            if (originalState == ConnectionState.Closed)
               connection.Close();
         }
      }
   }
}
    

Интерфейс IDBConnection реализует Мост между клиентским приложением и базой данных (БД). Цель паттерна – полная изоляция клиента от деталей реализации каждой конкретной БД. Конкретным объектом, реализующим этот интерфейс, может быть любой экземпляр класса, унаследованного от DBConnection (код создает экземпляры SqlConnection, OdbcConnection и OleDbConnection), но клиент никогда не должен узнать, какого именно. Это позволяет разработчикам клиентского приложения сделать его по-настоящему мультиплатформным, а разработчикам Моста – постепенно добавлять поддержку новых БД, которая не заставит разработчиков клиента ничего менять. Важная парадигма: для клиентского приложения оба “берега”, соединяемых Мостом, всегда представляют одно и то же (в нашем примере – БД), только на “его” берегу находится абстрактное представление о БД, а на “чужом” – ее конкретная реализация.

Теперь взгляните, какой “пример Моста” приведен на сайте Метанит. Там объект программиста обращается к объекту языка программирования через “мост”. Непонятно, зачем изолировать объекты языков программирования от объектов программистов, но проблема даже не в этом. Во-первых, вы не можете заранее предсказать все, что вам потребуется от языков программирования – а это значит, что ваш “мост”, скорее всего, через некоторое время придется изменять, тогда как одна из целей настоящего Моста заключается именно в защите клиента от изменений (как вы думаете, будет ли когда-нибудь изменен IDBConnection?). Во-вторых, вы не можете раз и навсегда определить даже вид соотношения между языками и программистами! Кто сказал, что каждый программист знает только один язык? Такие “мосты” только напрасно усложняют проект и не приносят никакой реальной пользы.

А вот пример того же паттерна с сайта Refactoring Guru. Здесь строится “мост” между пультами и управляемыми с их помощью устройствами. Этот пример уже имеет смысл, поскольку управлять с пульта проще, чем кнопками на устройстве (клиенту всегда проще работать с абстрактным интерфейсом Моста, избавляющим его от ненужных деталей реализации), но все-таки он неудачен. Не все команды управления телевизором и радио будут совпадать. Но самое главное – пульт не скрывает от клиента конкретную реализацию: клиент по-прежнему смотрит телевизор, а не пульт, и слушает радио, а не пульт. А мы уже знаем, что основная цель Моста – именно изоляция клиента от конкретной реализации.

Настоящий проектировщик не только использует паттерны правильно, но и придумывает свои. Вы же не считаете, что “банда четырех” описала все возможные паттерны? Например, прекрасная книга Мартина Фаулера “Шаблоны корпоративных приложений” содержит паттерны проектирования приложений, предоставляющих пользователям удаленный доступ к базам данных.

Удачи вам в определении того, чего вам не хватает, и успешного устранения этих пробелов!

***
Если вы хотите наработать необходимую для изучения Data Science математическую базу и подготовиться к углубленным занятиям в «Школе обработки данных» или Computer Science Center, обратите внимание на онлайн-курс «Библиотеки программиста». С помощью опытных преподавателей из ведущих вузов страны сделать это будет намного проще, чем самостоятельно по книгам.

Дополнительные материалы:

09
Авг
2021

Google выпустила Translatotron 2 — улучшенный ИИ для синхронного перевода устной речи. Теперь его нельзя использовать для дипфейка

Исследователи исправили главный недостаток алгоритма для перевода речи Translatotron. Теперь технологию нельзя использовать для создания дипфейков.
— Читать дальше «Google выпустила Translatotron 2 — улучшенный ИИ для синхронного перевода устной речи. …

02
Авг
2021

Twitter запустила соревнование по поиску предубеждений модели машинного обучения. За первое место платят 3,5$ тыс.

Twitter объявила программу по поиску «предупреждений алгоритмов». Это поможет снизить предвзятость моделей машинного обучения к разным социальным группам.
— Читать дальше «Twitter запустила соревнование по поиску предубеждений модели машинного обучения…

06
Июл
2021

В Бельгии искусственный интеллект стыдит политиков, которые используют телефон на заседаниях. И это пугает

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

05
Июл
2021

🤖 Вариационные автоэнкодеры (VAE) для чайников – пошаговое руководство

Практическое руководство в стиле “сделай сам” с работающим кодом создания и обучения VAE для лиц знаменитостей на Keras.

Текст публикуется в переводе, автор статьи – Мишель Кана.

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

Мотивация

Зачем нужно генерировать новые данные, если в мире и так огромное количество данных? Согласно IDC, в мире более 18 зеттабайтов данных.

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

Как сгенерировать изображения, которых никто не видел?

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

Пример изображения и его реконструкции с помощью нашего кода VAE
Пример изображения и его реконструкции с помощью нашего кода VAE

Данные

Мы используем подмножество широко известного набора данных Знаменитостей, который поможет нам создать модель генерации лиц. Этот набор можно скачать с сайта CelebFacesA. Он предоставляет большой набор атрибутов лиц, содержащий более 200 тысяч изображений знаменитостей, для каждого из которых указано значение 40 атрибутов.

  • 10.177 личностей;
  • 202.599 изображений;
  • 5 важнейших локаций;
  • 40 бинарных атрибутов для каждого изображения.
        import pandas as pd

df_celeb = pd.read_csv('list_attr_celeba.csv')
df_celeb.head()
    

Ниже мы выбираем случайные лица и выводим их метаданные (атрибуты). Изображения имеют высоту 218 пикселей, ширину 178 пикселей и 3 цветовых канала.

        import matplotlib.pyplot as plt
import random
from skimage.io import imread

def show_sample_image(nb=3, df=df_celeb, verbose=True):
    f, ax = plt.subplots(1, nb, figsize=(10,5))
    for i in range(nb):
        idx = random.randint(0, df.shape[0]-1)
        img_id = df.loc[idx].image_id
        img_uri = 'img_align_celeba/' + img_id
        img = skimage.io.imread(img_uri)  
        if verbose:
            label = img_id
            for col in df.columns:
                if df.loc[idx][col]==1:
                    label = label + '\n' + col  
            if nb > 1:
                ax[i].imshow(img)
                ax[i].set_title(label)
            else:
                ax.imshow(img) 
                ax.set_title(label)
        
    return img, list(df.loc[idx][1:df.shape[1]])
  
sample_img, sample_img_meta = show_sample_image()
    

Что такое автоэнкодер (AE)?

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

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

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

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

Как работают компоненты автоэнкодера
Как работают компоненты автоэнкодера
  • Модель энкодера переводит входное значение X в маленькое плотное представление Z, примерно так же, как работает сверточная нейронная сеть, используя фильтры для усвоения представлений.
  • Модель декодера можно считать генеративной моделью, способной генерировать специфические признаки X’.
  • Энкодер и декодер обычно обучаются вместе. Функция потерь штрафует объединенную сеть за создание выходных лиц, отличающихся от входных лиц.

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

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

Что такое вариационный автоэнкодер (VAE)?

Как правило, скрытое пространство Z, создаваемое энкодером, редко заселено, то есть трудно предсказать, распределение значений в этом пространстве. Значения разбросаны, и пространство обычно хорошо визуализируется в двухмерном представлении.

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

Более того, если в пространстве есть промежутки между кластерами, и декодер получит вариацию из такого промежутка, ему не хватит знаний, чтобы сгенерировать что-нибудь полезное.

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

Переход от AE к VAE, используя случайные переменные
Переход от AE к VAE, используя случайные переменные

Вместо прямой передачи скрытых значений декодеру, VAE используют их для расчета средних значений и стандартных отклонений. Затем вход декодера собирается из соответствующего нормального распределения.

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

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

Генератор данных изображений

Давайте создадим (условный) VAE, который сможет обучаться на лицах знаменитостей. Мы используем пользовательский эффективный по памяти генератор Keras, чтобы справиться с нашим большим набором данных (202599 изображений, примерно по 10Кб каждое). Его цель – получать пакеты изображений на лету в процессе обучения.

        import numpy as np

class CustomCelebrityFaceGenerator(Sequence):
    # инициализируем пользовательский генератор
    def __init__(self, df, batch_size, target_height, target_width, conditioning_dim=0):
        self.df = df
        self.batch_size = batch_size
        self.target_height = target_height
        self.target_width = target_width
        self.conditioning_dim = conditioning_dim
        
    # перетасуем данные после каждой эпохи 
    def on_epoch_end(self):
        self.df = self.df.sample(frac=1)
    
    # выберем пакет в виде тензора
    def __getitem__(self, index):
        cur_files = self.df.iloc[index*self.batch_size:(index+1)*self.batch_size]
        X, y = self.__data_generation(cur_files)
        return X, y
    
    # 
    def __data_generation(self, cur_files):
        # инициализируем пустые тензоры для хранения изображений  
        X = np.empty(shape=(self.batch_size, self.target_height, self.target_width, 3))
        Y = np.empty(shape=(self.batch_size, self.target_height, self.target_width, 3))
        # инициализируем пустой тензор для хранения условных переменных
        if self.conditioning_dim > 0:
            C = np.empty(shape=(self.batch_size, self.conditioning_dim))
        
        # проходим циклом по текущему пакету и создаем тензоры 
        for i in range(0, self.batch_size):
            # читаем изображение
            file = cur_files.iloc[i]
            img_uri = 'img_align_celeba/' + file.image_id
            img = skimage.io.imread(img_uri)
            # изменяем размеры изображения
            if img.shape[0] != self.target_height or img.shape[1] != self.target_width:
                img = skimage.transform.resize(img, (self.target_height, self.target_width)) 
            # сохраняем изображение в тензорах 
            img = img.astype(np.float32) / 255.
            X[i] = img
            Y[i] = img
            # сохраняем условные параметры в тензорах
            if self.conditioning_dim > 0:
                C[i] = list(file[1:file.shape[0]])
            
        if self.conditioning_dim > 0:
            return [X, C], Y
        else:
            return X, Y
    
    # получить количество пакетов
    def __len__(self):
        return int(np.floor(self.df.shape[0] / self.batch_size))
    

Нейронная сеть VAE

Мы хотим, чтобы наш энкодер был сверточной нейронной сетью, принимающей изображение и выдающей параметры распределения Q(z | [x,c]), где x – входное изображение лица, c – условная переменная (атрибуты лица), а z – скрытая переменная. В этой статье мы используем простую архитектуру, состоящую из двух сверточных слоев и слоя группировки (pooling).

Декодер – это сверточная нейронная сеть, построенная по-другому. Это генеративная нейронная сеть, выдающая параметры распределения похожести P([x,z] | c).

        from keras.layers import Conv2D, MaxPooling2D, UpSampling2D

def get_encoder_network(x, num_filters):  
    x = Conv2D(num_filters, 3, activation='relu', padding='same', kernel_initializer='he_normal')(x)
    x = Conv2D(num_filters, 3, activation='relu', padding='same', kernel_initializer='he_normal')(x)
    x = MaxPooling2D()(x)
    return x

def get_decoder_network(x, num_filters):
    x = UpSampling2D()(x)
    x = Conv2D(num_filters, 3, activation='relu', padding = 'same', kernel_initializer = 'he_normal')(x)
    x = Conv2D(num_filters, 3, activation='relu', padding = 'same', kernel_initializer = 'he_normal')(x)
    return x
    

Вот так выглядит архитектура всей сети VAE:

        from keras.layers import Input, Dense, Reshape, Concatenate, Flatten, Lambda, Reshape
from keras.models import Model
from keras import backend as K
from keras.optimizers import Adam

# функция для создания нейронной сети автоэнкодера 
def get_vae(height, width, batch_size, latent_dim, 
            is_variational=True, conditioning_dim=0,
            start_filters=8, nb_capacity=3, 
            optimizer=Adam(lr=0.001)):
    
    # ВХОД ##
    
    # создаем слой для входного изображения 
    # объединяем метаданные изображений 
    inputs = Input((height, width, 3))
    if conditioning_dim > 0:
        condition = Input([conditioning_dim])
        condition_up = Dense(height * width)(condition)
        condition_up = Reshape([height, width, 1])(condition_up)
        inputs_new = Concatenate(axis=3)([inputs, condition_up])
    else:
        inputs_new = inputs
    
    
    # ЭНКОДЕР ##
    
    # создаем кодирующие слои 
    # дублируем кодирующие слои, увеличивая фильтры 
    eblock = get_encoder_network(inputs_new, start_filters)
    for i in range(1, nb_capacity+1):
        eblock = get_encoder_network(eblock, start_filters*(2**i))
        
    # создаем слой скрытого пространства
    _, *shape_spatial = eblock.get_shape().as_list()
    eblock_flat = Flatten()(eblock)    
    if not is_variational:
        z = Dense(latent_dim)(eblock_flat)
    else:
        # выборка скрытых значений из нормального распределения
        def sampling(args):
            z_mean, z_log_sigma = args
            epsilon = K.random_normal(shape=(batch_size, latent_dim), mean=0., stddev=1.)
            return z_mean + K.exp(z_log_sigma) * epsilon
        
        z_mean = Dense(latent_dim)(eblock_flat)
        z_log_sigma = Dense(latent_dim)(eblock_flat)
        z = Lambda(sampling, output_shape=(latent_dim,))([z_mean, z_log_sigma])
    
    if conditioning_dim > 0:
        z_ext = Concatenate()([z, condition])

        
    ## ДЕКОДЕР ##
    
    # создаем декодирующие статьи
    inputs_embedding = Input([latent_dim + conditioning_dim])
    embedding = Dense(np.prod(shape_spatial), activation='relu')(inputs_embedding)
    embedding = Reshape(eblock.shape.as_list()[1:])(embedding)
    
    # дублируем кодирующие слои, увеличивая фильтры 
    dblock = get_decoder_network(embedding, start_filters*(2**nb_capacity))
    for i in range(nb_capacity-1, -1, -1):
        dblock = get_decoder_network(dblock, start_filters*(2**i))
        
    output = Conv2D(3, 1, activation = 'tanh')(dblock)
    
    ## VAE ##
    
    # объединяем энкодер с декодером 
    decoder = Model(input = inputs_embedding, output = output)
    if conditioning_dim > 0:
        encoder_with_sampling = Model(input = [inputs, condition], output = z)
        encoder_with_sampling_ext = Model(input = [inputs, condition], output = z_ext)
        vae_out = decoder(encoder_with_sampling_ext([inputs, condition]))
        vae = Model(input = [inputs, condition], output = vae_out)
    else:
        encoder_with_sampling = Model(input = inputs, output = z)
        vae_out = decoder(encoder_with_sampling(inputs))
        vae = Model(input = inputs, output = vae_out)
    
    # определяем потери VAE как сумму MSE and потерь расстояния Кульбака-Лейблера
    def vae_loss(x, x_decoded_mean):
        mse_loss = K.mean(mse(x, x_decoded_mean), axis=(1,2)) * height * width
        kl_loss = - 0.5 * K.mean(1 + z_log_sigma - K.square(z_mean) - K.exp(z_log_sigma), axis=-1)
        return mse_loss + kl_loss
        
    if is_variational:
        vae.compile(loss=vae_loss, optimizer=optimizer)
    else:
        vae.compile(loss='mse', optimizer=optimizer)    
        
    return vae, encoder_with_sampling, decoder

# гиперпараметры
VARIATIONAL = True
HEIGHT = 128 
WIDTH = 128 
BATCH_SIZE = 16 
LATENT_DIM = 16
START_FILTERS = 32 
CAPACITY = 3 
CONDITIONING = True 
OPTIMIZER = Adam(lr=0.01)

vae, encoder, decoder = get_vae(is_variational=VARIATIONAL,
                                   height=HEIGHT, 
                                   width=WIDTH, 
                                   batch_size=BATCH_SIZE, 
                                   latent_dim=LATENT_DIM,
                                   conditioning_dim=df_celeb.shape[1]-1, 
                                   start_filters=START_FILTERS,
                                   nb_capacity=CAPACITY,
                                   optimizer=OPTIMIZER)
    

Обучение

Ниже представлен процесс обучения моделей VAE на наборе данных celebA. Этот код выполнялся около 8 часов на инстансе AWS с использованием 1 GPU.

        # делим изображения на тренировочный набор и набор валидации
msk = np.random.rand(len(df_celeb)) < 0.5
df_celeb_train = df_celeb[msk]
df_celeb_val = df_celeb[~msk]

# создаем генераторы изображений для обучения
gen = CustomCelebrityFaceGenerator(df_celeb_train, 
                          batch_size=BATCH_SIZE, 
                          target_height=HEIGHT, 
                          target_width=WIDTH, 
                          conditioning_dim=df_celeb.shape[1]-1)

# создаем генераторы изображений для валидации
gen_val = CustomCelebrityFaceGenerator(df_celeb_val, 
                          batch_size=BATCH_SIZE, 
                          target_height=HEIGHT, 
                          target_width=WIDTH, 
                          conditioning_dim=df_celeb.shape[1]-1)

# обучаем вариационный автоэнкодер
vae.fit_generator(gen, verbose=1, epochs=20, validation_data=gen_val)
    

Визуализируем скрытые представления

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

        # выбираем случайное изображение
sample_img, sample_img_meta = show_sample_image(nb=1)

# функция для кодирования одного изображения, возвращающая его скрытое представление
def encode_image(img, conditioning, encoder, height, width, batch_size):
    # изменяем размеры изображения
    if img.shape[0] != height or img.shape[1] != width:
        img = skimage.transform.resize(img, (height, width))
    # заполняем изображение, чтобы оно соответствовало размеру пакета
    img_single = np.expand_dims(img, axis=0)
    img_single = img_single.astype(np.float32)
    img_single = np.repeat(img_single, batch_size, axis=0)
    # используем энкодер для вычисления представления в скрытом пространстве
    if conditioning is None:
        z = encoder.predict(img_single)
    else:
        z = encoder.predict([img_single, np.repeat(np.expand_dims(conditioning, axis=0), batch_size, axis=0)])
    return z

# выводим представление в скрытом пространстве, созданное энкодером
z = encode_image(sample_img.astype(np.float32) / 255., 
                 np.array(sample_img_meta), 
                 encoder, HEIGHT, WIDTH, BATCH_SIZE)
print('latent sample:\n', z[0])
    


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

        def decode_embedding(z, conditioning, decoder):
    if z.ndim < 2:
        z = np.expand_dims(z, axis=0)
    if conditioning is not None:
        z = np.concatenate((z, np.repeat(np.expand_dims(conditioning, axis=0), z.shape[0], axis=0)), axis=1)
    return decoder.predict(z)

# восстановим исходное изображение, используя представление скрытого пространства 
ret = decode_embedding(z, sample_img_meta, decoder)
plt.imshow(ret[0])
plt.show()
    

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

Генерируем новые лица

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

        def generate_new_images_vae(nb=16, smiling=None, male=None, no_beard=None, attractive=None, 
                        bald=None, chubby=None, eyeglasses=None, young = None):
    sample_training_img, sample_training_img_meta = show_sample_image(nb=1, verbose=False)
    plt.clf();
    f, ax = plt.subplots(2, nb//2, figsize=(20,7));
    for i in range(nb):
        meta=2*np.random.rand(meta_cols.shape[0])-1
        meta[2] = attractive if attractive else meta[2]
        meta[4] = bald if bald else meta[4]
        meta[13] = chubby if chubby else meta[13]
        meta[15] = eyeglasses if eyeglasses else meta[15]
        meta[20] = male if male else meta[20]
        meta[24] = no_beard if no_beard else meta[24]
        meta[31] = smiling if smiling else meta[31]
        meta[39] = young if young else meta[39]
        z1 = np.random.rand(LATENT_DIM, LATENT_DIM)
        ret = decode_embedding(z1, meta, decoder)
        ax[i%2][i//2].imshow(ret[0])
        ax[i%2][i//2].set_title('generated img {}'.format(i))
    ax[0][0].imshow(sample_training_img)
    ax[0][0].set_title('training img')
    
 generate_new_images_vae()
    

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

От улыбки станет мир светлей

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

        # интерполяция скрытого пространства, чтобы изменить исходное изображение
def display_manifold(decoder, height, width, base_vec, 
                     bound_x=15, bound_y=15, 
                     axis_x=0, axis_y=1, n=15,
                     desc_x = 'x', desc_y = 'y', 
                     file_out=None):
 
    figure = np.zeros((height * (n if bound_y > 0 else 1), width * (n if bound_x > 0 else 1), 3))
    grid_x = np.linspace(-bound_x, bound_x, n) if bound_x > 0 else [0]
    grid_y = np.linspace(-bound_y, bound_y, n) if bound_y > 0 else [0]
    individual_outputs = []

    for i, yi in enumerate(grid_y):
        for j, xi in enumerate(grid_x):
            z_sample = base_vec.copy()
            z_sample[axis_x] = xi 
            z_sample[axis_y] = yi 

            x_decoded = decoder.predict(np.expand_dims(z_sample, axis=0))
            sample = np.clip(x_decoded[0], 0, 1)
            figure[i * height: (i + 1) * height, j * width: (j + 1) * width] = sample
            individual_outputs.append(sample)

    plt.figure(figsize=(10, 10))
    plt.imshow(figure)
    plt.xlabel(desc_x)
    plt.ylabel(desc_y)
    if file_out is not None:
        plt.savefig(file_out, dpi=200, bbox_inches='tight')
    return figure, individual_outputs

# доступные атрибуты
meta_cols = df_celeb.columns[1:].values

# изменяемые атрибуты
dim1 = 'Male'
dim2 = 'Smiling'

# используемое скрытое пространство 
base_vec = np.array(list(z[0]) + sample_img_meta)

# создаем изменения
rendering, _ = display_manifold(
                                decoder, 
                                HEIGHT, 
                                WIDTH, 
                                base_vec, 
                                bound_x=15, 
                                bound_y=15, 
                                axis_x=LATENT_DIM + np.where(meta_cols==dim1)[0][0], 
                                axis_y=LATENT_DIM + np.where(meta_cols==dim2)[0][0], 
                                n=10,
                                desc_x = dim1,
                                desc_y = dim2,
                                file_out = 'rendering_celeba_' + dim1.lower() + '_' + dim2.lower() + '.png'
                                )
    

Заключение

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

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

Этический аспект использования технологий VAE/GAN для создания фейковых изображений, видео и новостей следует рассматривать серьезно, и они должны применяться ответственно.

Огромное спасибо Винсенту Кассеру (Vincent Casser) за его замечательный код, содержащий более продвинутый подход к реализации сверточных автоэнкодеров для обработки изображений, приведенный в его блоге. Винсент разрешил мне адаптировать его код VAE для этой статьи. Создание работающего VAE с нуля довольно сложно, так что за код следует благодарить Винсента.

Если вы хотите узнать больше об автоэнкодерах, читайте статью Джозефа Рокка «Разбираемся с вариационными автоэнкодерами (VAE)».

07
Июн
2021

Опубликован список из 10 максимально полезных GitHub-репозиториев

Он будет интересен как начинающим разработчикам, так и тем, кто готовится к интервью в крупнейших IT-компаниях.
— Читать дальше «Опубликован список из 10 максимально полезных GitHub-репозиториев»

31
Май
2021

🎥 Делаем DeepFake на коленке: пошаговое практическое руководство

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

14
Апр
2021

Курс «PHP + MySQL за 1,5 месяца»

12 занятий, практика на каждом уроке, сертификат об окончании курса и возможность попасть в команду BrainForce. Старт в любой день.
— Читать дальше «Курс «PHP + MySQL за 1,5 месяца»»

30
Мар
2021

🤖 Применение искусственного интеллекта для общественного блага

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

Что…

29
Мар
2021

Муравей Лэнгтона — загадочный клеточный автомат

Одна из нерешённых задач математики с простейшей формулировкой и необъяснимым поведением. Попробуйте поэкспериментировать.
— Читать дальше «Муравей Лэнгтона — загадочный клеточный автомат»

19
Мар
2021

Видео: девушка-разработчик написала программу на Python для создания необычных портретов

Один из тех проектов, которые поначалу кажутся простыми, но в процессе вызывают боль и страдание.
— Читать дальше «Видео: девушка-разработчик написала программу на Python для создания необычных портретов»

12
Мар
2021

🤖📊 Как машинное обучение упорядочивает большие данные

Когда в работу с большими данными вступает машинное обучение, игра выходит на новый уровень. Рассказываем, как и зачем методы Machine Learning применяется в сфере Big Data.

Что такое большие данные?

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

Анализ больших данных – относительно новая, но довольно востребованная сфера рынка труда. Спрос на специалистов в этой области постоянно растет.

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

Аналитик Big Data – специалист, который выявляет и исследует закономерности в данных с помощью специальных программных средств.

5V больших данных


Работа с большими данными строится вокруг пяти основных принципов (c англ. V’s of Big Data: Volume, Velocity, Variety, Veracity, Value):

  1. Объем: количество собираемой компаниями информации действительно огромно, поэтому ее объем становится критическим фактором в аналитике.
  2. Скорость: практически все происходящее вокруг нас (поисковые запросы, социальные сети и т. д.) очень быстро генерирует новые данные, многие из которых могут быть использованы в бизнес-решениях.
  3. Разнообразие: генерируемая информация неоднородна и может быть представлена в различных форматах, таких, например, как видео, текст, базы данных, числа, сенсорные данные и т. д. Понимание типов больших данных является ключевым фактором для раскрытия их ценности.
  4. Достоверность: данные высокой достоверности содержат много записей, которые ценны для анализа и которые вносят значимый вклад в общие результаты. Данные с низкой достоверностью содержат высокий процент бессмысленной информации, которая называется шумом.
  5. Ценность: возможность трансформировать большие данные в бизнес-решения.

Откуда получают большие данные


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

Некоторые из основных источников Big Data:

  • Социальные сети;
  • Облачные Хранилища;
  • Веб-страницы;
  • Интернет вещей.

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

Что такое машинное обучение?


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

Алгоритмы машинного обучения могут быть применены к каждому этапу работы с большими данными, включая следующие:

  • Сегментацию данных;
  • Анализ данных;
  • Моделирование.

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

Как машинное обучение применяется в Big Data?

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

Примеры применения алгоритмов МО для больших данных

Автоматизация Маркетинга

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

Целевая аудитория – это краеугольный камень любого бизнеса. Каждое предприятие должно понимать рынок, на который оно хочет ориентироваться. Машинное обучение использует контролируемые и неконтролируемые алгоритмы для точной интерпретации потребительских паттернов и поведения. Опираясь на машинное обучение и большие данные, автоматизация маркетинга может использовать анализ тональности текста, сегментацию клиентов и прямой маркетинг, с помощью персонализированных сообщений для удовлетворения потребностей клиентов. СМИ и индустрия развлечений используют машинное обучение, чтобы понять симпатии и антипатии аудитории и предложить ей подходящий контент.

Анализ тональности текста


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

Рекомендательные системы

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

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

Чтобы создать хорошую рекомендацию по продукту, система должна иметь четкое представление о желаниях и потребностях как клиента, так и компании. Большая часть этой информации может быть собрана из активности в социальных сетях, веб-форм, истории местоположений и множества других источников. Сопоставляя данные с конкретными уникальными потребностями человека и активностью других клиентов, основанные на машинном обучении рекомендательные системы обеспечивают бизнесу автоматизированный маркетинговый процесс. Например, Netflix широко их использует, чтобы предложить правильный контент зрителям.

Регулирование рисков

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

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

Расшифровка паттернов

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

Прогнозная аналитика


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

***

Мы рассмотрели возможности и сферы применения машинного обучения в больших данных. Если вы еще не определились со специализацией, начните с базового онлайн-курса «Библиотеки программиста» по математике в Data Science. Без царицы наук в этой области обойтись не получится, а с помощью опытных преподавателей из ведущих вузов страны получить знания намного проще, чем самостоятельно по книгам. Также ведется запись и на продвинутый курс. Удачи в освоении востребованной профессии!

02
Мар
2021

🤖 Современные рекомендательные системы

Сегодня мы поглубже нырнем в особенности работы алгоритмов искусственного интеллекта, на которых построили бизнес Facebook, Google и другие ИТ-гиганты.

Не далее чем в мае 2019 Facebook выложил в открытый доступ исходный код некоторых своих подходов к рекомендациям и представил DLRM (Deep-Learning Recommendation Model – рекомендательную модель глубокого обучения). Эта статья попробует объяснить, как и почему DLRM и другие современные подходы к рекомендациям работают настолько хорошо, посредством анализа их происхождения от прежних результатов в данной области и детального объяснения внутренних деталей их работы и заложенных в них идей.


Персонализированная реклама, основанная на ИИ, сегодня царствует в онлайн-маркетинге, и такие компании, как Facebook, Google, Amazon, Netflix и прочие – короли джунглей этого онлайн-маркетинга, поскольку они не просто усвоили этот тренд, а фактически сами воплотили его в жизнь и построили на нем всю свою бизнес-стратегию. Netflix’овские “другие фильмы, которые могут вам понравиться” и Amazon’овские “люди, купившие это, купили также…” – всего лишь несколько примеров из реального мира.

Само собой, будучи постоянным пользователем Facebook и Google, в какой-то момент я спросил себя:

КАК ИМЕННО ЭТА ШТУКА РАБОТАЕТ?

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

Чтобы понять, откуда происходят современные передовые рекомендательные системы, нам придется взглянуть на два основных подхода к задаче

предсказания, насколько данному пользователю понравится данный продукт,

которая в мире онлайнового маркетинга складывается в предсказание показателя кликабельности (click-through rate, CTR) для возможных рекламных объявлений, основанное как на явной обратной связи (рейтинги, лайки и т.п.), так и на неявной (клики, истории поиска, комментарии или посещения веб-сайтов).

Коллаборативная фильтрация против фильтрации на основе содержимого

1. Фильтрация на основе содержимого (content-based filtering)

Грубо говоря, рекомендация на основе содержимого пытается предсказать, понравится ли пользователю некоторый продукт, используя его онлайновую историю. Это включает, помимо всего прочего, поставленные пользователем лайки (например, на Facebook), ключевые слова, которые он искал (например, в Google), а также простые клики и посещения определенных веб-сайтов. В конечном счете она концентрируется на собственных предпочтениях каждого пользователя. Мы можем, например, построить простой бинарный классификатор (или регрессор), предсказывающий ожидаемый уровень кликабельности (или рейтинг) определенной группы рекламных объявлений для данного пользователя.

2. Коллаборативная фильтрация

Коллаборативная фильтрация пытается предсказать, может ли пользователю понравиться определенный продукт, путем анализа предпочтений похожих пользователей. Здесь мы можем подумать об уже привычном для нас (по примеру рекомендации фильмов) подходе факторизации матриц (matrix factorization – MF), при котором матрица рейтингов приводится к одной матрице, описывающей пользователей и другой, описывающей фильмы.

Недостаток классической MF в том, что мы не можем использовать никакие признаки, кроме пользовательских оценок – например, жанр фильма, год выхода и т.д. – MF приходится догадываться обо всем этом из имеющихся оценок. Кроме того, MF страдает от так называемой “проблемы холодного старта”: новый фильм, который еще никто не оценил, не может быть рекомендован. Фильтрация на основе содержимого справляется с этими двумя проблемами, но ей не хватает предсказательной мощности просмотра предпочтений других пользователей.

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

1. Машина Факторизации (Factorization Machine)

Одна из идей гибридной модели, предложенная Стеффеном Рендлом в 2010-м – это Машина Факторизации. Она придерживается базового математического подхода, комбинируя факторизацию матриц с регрессией:

y^(x):=w0+∑i=0nwixi⏟regressionpart+∑i=1n∑j=i+1n⟨vi,vj⟩xixj⏟MFpartw0∈R;w∈Rn;V∈Rn∗k;vi,vj∈Rk

Здесь <vi, vj> – произведение векторов, которые можно рассматривать как строки матрицы V.

Понять смысл этого уравнения довольно просто, если посмотреть на пример представления данных x, попадающих в эту модель. Давайте рассмотрим пример, представленный Стеффеном в его статье о Машине Факторизации.

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

  • пользователь u из множества U = {Alice (A), Bob (B),…}
  • фильм i из множества I = {“Титаник” (TN), “Ноттинг Хилл” (NH), “Звездные Войны” (SW), “Стар Трек” (ST),…}
  • оценка r из {1, 2, 3, 4, 5}, поставленная во время t.
Рис.1. С. Рендл, "Машины факторизации", Международная конференция IEEE по Data Mining, 2010.
Рис.1. С. Рендл, “Машины факторизации”, Международная конференция IEEE по Data Mining, 2010.

Посмотрев на приведенный выше рисунок, мы увидим представление данных в гибридной рекомендательной модели. Как разреженные признаки, представляющие пользователя и оцениваемый объект, так и любая другая дополнительная информация об объекте или мета-информация (в этом примере – Time и Last Movie Rated) попадают в вектор признаков x, который соответствует значению целевой переменной y. Теперь главное – то, как они обрабатываются моделью.

  • Регрессионая часть FM обрабатывает и разреженные, и плотные данные (например, Time), как обычная задача линейной регрессии, и, таким образом, может считаться подходом фильтрации на основе содержимого в составе FM.
  • Часть MF отвечает за взаимодействие между блоками признаков (например, взаимодействие между “Пользователем” и “Фильмом”), где матрицу V можно рассматривать как встроенную матрицу, используемую в подходах коллаборативной фильтрации. Эти отношения пользователь-фильм предоставляют нам догадки вроде:

Пользователю i, которому соответствует вектор vi (представляющий его предпочтения к параметрам фильмов), похожий на вектор vj пользователя j, скорее всего, понравятся те же фильмы, что и пользователю j.

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

Однако, несмотря на то, что подход Машины Факторизации с первого взгляда кажется “лучшей моделью из обоих миров”, многие области ИИ, такие, как обработка естественного языка или машинное зрение, давно доказали, что

если взять нейронную сеть, то будет еще лучше!

2. Широкие и глубокие: нейронная коллаборативная фильтрация (NCF) и Глубокие Машины Факторизации (DeepFM)

Для начала бросим взгляд на то, как можно реализовать коллаборативную фильтрацию с помощью нейронных сетей, просмотрев статью об NCF. В конце концов это приведет нас к Глубоким Машинам Факторизации (DeepFM), представляющим собой нейросетевую версию машин факторизации. Мы увидим, почему они превосходят обычные машины факторизации, и как можно интерпретировать архитектуру этих нейронных сетей. Мы увидим, что DeepFM была разработана как улучшение вышедшей до этого модели Wide&Deep от Google, которая была одним из первых крупных прорывов в области глубокого обучения рекомендательных систем. В конце концов это приведет нас к упомянутой выше статье по DLRM, опубликованной Facebook’ом в 2019-м, которую можно считать упрощением и небольшим усовершенствованием DeepFM.

NCF

В 2017-м группа исследователей опубликовала свою работу о Нейронной Коллаборативной Фильтрации (NCF). Она содержит обобщенный фреймворк для изучения нейронных зависимостей, моделируемых факторизацией матриц при коллаборативной фильтрации с помощью нейронной сети. Авторы также объяснили, как получить зависимости высшего порядка (MF имеет порядок всего лишь 2), и как объединить оба эти подхода.

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

Рис. 2. Из статьи "Нейронная коллаборативная фильтрация" Кс. Хе, Л. Ляо, Х. Жанг, Л. Ни, Кс. Ху, Ц. Чуа – Материалы 26-й международной конференции по World-Wide Web, 2017.
Рис. 2. Из статьи “Нейронная коллаборативная фильтрация” Кс. Хе, Л. Ляо, Х. Жанг, Л. Ни, Кс. Ху, Ц. Чуа – Материалы 26-й международной конференции по World-Wide Web, 2017.

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

В реальных задачах мы не просто используем двоичные векторы, соответствующие пользователю и объекту в качестве необработанных данных для их представления, но, очевидно, включаем и прочую дополнительную или мета-информацию, которая может представлять ценность (например, возраст, страну, аудио- и текстовые записи, метки времени,…), так что в реальности у нас получается набор данных очень высокой размерности, сильно разреженный и содержащий смесь качественных переменных с количественными. К этому моменту представленную на рис. 2 нейронную сеть можно считать и рекомендацией на основе содержимого в виде простого нейронного бинарного классификатора прямого прохода. И эта интерпретация – ключевая для понимания того, почему этот подход в конце концов оказывается гибридным между коллаборативной фильтрацией и рекомендациями на основе содержимого. Эта нейронная сеть может усвоить любые функциональные зависимости – например, взаимодействия 3-й степени и выше, вроде x1 * x2 * x3, или любые нелинейные трансформации в классическом понимании, используемом в нейронных классификаторах – в виде sigma(.. sigma(w1x1+w2x2+w3x3+b)).

Вооружившись мощью изучения зависимостей высшего порядка, мы можем использовать простой способ изучения зависимостей 1-го и 2-го порядков, скомбинировав нейронную сеть с широко известной моделью для их изучения, Машиной Факторизации. Именно это авторы DeepFM предложили в своей статье. Идея этой комбинации – параллельно изучать зависимости между признаками низких и высоких порядков – ключевая часть многих современных рекомендательных систем, и в том или ином виде ее можно найти почти в каждой архитектуре нейронной сети, предлагаемой в этой области.

DeepFM

DeepFM – это смешанный подход, включающий факторизацию матриц и глубокую нейронную сеть, причем оба используют один и тот же входной слой представления (embedding). Необработанные признаки трансформируются, чтобы закодировать категориальные признаки унитарным кодом (one-hot encoding). Итоговое предсказание (показатель кликабельности), выдаваемое последним словом нейронной сети, определяется так:

y^=sigmoid(yFM+yDNN)

То есть, это сумма предсказаний матричной факторизации и нейронной сети, пропущенная через сигмоидную функцию активации.

Компонент факторизации матриц – это обычная Машина Факторизации, оформленная в стиле архитектуры нейронной сети:

Рис. 3. из статьи Х. Гуо, Р. Тэнг, Ю. Е, Ж. Ли и Кс. Хе "DeepFM – нейронная сеть на основе машины факторизации для предсказания показателя кликабельности. arXiv:1703.04247, 2017
Рис. 3. из статьи Х. Гуо, Р. Тэнг, Ю. Е, Ж. Ли и Кс. Хе “DeepFM – нейронная сеть на основе машины факторизации для предсказания показателя кликабельности. arXiv:1703.04247, 2017

Часть сложения (Addition) этого слоя матричной факторизации получает вектор входных данных x от слоя разреженных признаков (Sparse Features) и умножает каждый элемент на его вес (Normal Connection) перед суммированием. Часть перемножения векторов (Inner Product) также получает вектор x, но только после его прохождения через слой представления и просто перемножает представленные векторы без весов (“Weight-1 Connection”). Сложение обеих частей вместе приводит к вышеупомянутому уравнению для Машины Факторизации:

yFM:=w0+∑i=0nwixi+∑i=1n∑j=i+1n⟨vi,vj⟩xixj

В этом уравнении перемножение xixj нужно только для записи суммы от 1 до n. Оно не является частью вычислений нейронной сети. Нейронная сеть автоматически знает, произведение каких векторов vi и vj потребуется, благодаря архитектуре слоя представления.

Архитектура слоя представления выглядит следующим образом:

Рис. 4. из статьи Х. Гуо, Р. Тэнг, Ю. Е, Ж. Ли и Кс. Хе "DeepFM – нейронная сеть на основе машины факторизации для предсказания показателя кликабельности. arXiv:1703.04247, 2017
Рис. 4. из статьи Х. Гуо, Р. Тэнг, Ю. Е, Ж. Ли и Кс. Хе “DeepFM – нейронная сеть на основе машины факторизации для предсказания показателя кликабельности. arXiv:1703.04247, 2017

Здесь Vp – матрица представлений для каждого поля p={1,2…,m} c k столбцами и количеством строк, соответствующим количеству элементов поля, закодированных двоичным образом. Выход этого слоя представления определяется как

a(0)=[e1,e2,…em]

и важно отметить, что этот слой не полносвязный, а именно – нет связей между необработанным входом любого поля и представлением любого другого поля. Представьте это следующим образом: вектор значений для пола (например, (0, 1)), закодированный унитарным кодом, не может иметь ничего общего с вектором представлений для дня недели (например, вектором (0, 1, 0, 0, 0, 0, 0), закодированный “Вторник”, или его вектором представления, например, для k=4, (12, 4, 5, 9).

Компонент FM – это Машина Факторизации, отражающая высокую важность взаимодействий 1 и 2 порядка, которые прямо складываются с выходом глубокого компонента и передаются в сигмоидную функцию активации последнего слоя.

Глубоким компонентом, как предполагается, теоретически может быть нейронная сеть любой архитектуры. Авторы рассмотрели стандартный многоуровневый перцептрон прямого прохода (а также так называемую PNN). Стандартный многоуровневый перцептрон изображен на следующем рисунке:

Рис. 5. из статьи Х. Гуо, Р. Тэнг, Ю. Е, Ж. Ли и Кс. Хе "DeepFM – нейронная сеть на основе машины факторизации для предсказания показателя кликабельности. arXiv:1703.04247, 2017
Рис. 5. из статьи Х. Гуо, Р. Тэнг, Ю. Е, Ж. Ли и Кс. Хе “DeepFM – нейронная сеть на основе машины факторизации для предсказания показателя кликабельности. arXiv:1703.04247, 2017

Нейронная сеть на основе стандартного многослойного перцептрона со слоем представления между необработанными данными (сильно разреженными после унитарного кодирования категориальных переменных) и следующими слоями нейронной сети описывается следующей формулой:

a(l+1)=σ(W(l)a(l)+b(l))

где sigma – функция активации, W – матрица весов, a – результат функции активации предыдущего слоя, а b – порог.

Это приводит к общей архитектуре нейронной сети DeepFM:

Рис. 6. Общая архитектура DeepFM
Рис. 6. Общая архитектура DeepFM

со следующими параметрами:

  • Скрытый вектор Vi для измерения влияния взаимодействий признака i с другими признаками (слой представления).
  • Vi передается в компонент FM для моделирования взаимодействий 2 порядка (компонент FM).
  • wi взвешивает важность необработанного признака i 1-го порядка (компонент FM).
  • Vi также передается в Глубокий компонент для моделирования всех взаимодействий высших порядков (>2)(Глубокий компонент).
  • WI и bI – веса и пороги нейронной сети (Глубокий компонент).

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

Сравнение с Wide&Deep и NeuMF

Есть много вариаций, о которых можно задуматься, чтобы “отполировать” эту архитектуру и сделать ее еще лучше. Однако в основном все они сходятся в своем гибридном подходе, заключающемся в одновременной обработке взаимодействий высших и низших порядков. Авторы DeepFM также предложили замену многоуровневого перцептрона на так называемую PNN, глубокую нейронную сеть, получающую в качестве входных данных выводы FM и слоя представления.

Авторы статьи про NCF также предложили похожую архитектуру, которую они назвали NeuMF (Neural Matrix Factorization – нейронная факторизация матриц). Вместо использования FM в качестве компонента низшего порядка они используют обычную факторизацию матриц, результаты которой передаются в функцию активации. Этому подходу, однако, не хватает взаимодействий 1 порядка, моделируемых линейной частью FM. Авторы также указали, что модель имеет различные представления пользователя и объекта для матричной факторизации и многослойного перцептрона.

Как упомянуто выше, команда исследователей Google была одной из первых, предложивших нейронные сети для гибридного подхода к рекомендации. DeepFM можно рассматривать как дальнейшеее развитие алгоритма Wide&Deep от Google, который выглядит примерно так:

Рис. 7. Х-Т Ченг, Л. Кос, Дж. Хармсен, Т. Шакед, Т. Чандра, Х. Арадхье, Г. Андерсон, Г. Коррадо, В. Чаи, М. Испир, Р. Анил, З. Хак, Л. Хонг, В. Джейн, Кс. Лю и Х. Шах. "Широкое и глубокое обучение для рекомендательных систем" – Материалы 1 семинара по глубокому обучению для рекомендательных систем, стр. 7-10, 2016.
Рис. 7. Х-Т Ченг, Л. Кос, Дж. Хармсен, Т. Шакед, Т. Чандра, Х. Арадхье, Г. Андерсон, Г. Коррадо, В. Чаи, М. Испир, Р. Анил, З. Хак, Л. Хонг, В. Джейн, Кс. Лю и Х. Шах. “Широкое и глубокое обучение для рекомендательных систем” – Материалы 1 семинара по глубокому обучению для рекомендательных систем, стр. 7-10, 2016.

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

ϕk(x)=∏i=1dxickicki∈{0,1}

Это выражает взаимодействие между d признаками (с предшествующим представлением признаков или без него), умножая их друг на друга (показатель степени равен 1, если xi является частью k-й трансформации).

Легко видеть, что DeepFM является развитием этой модели, поскольку она не требует никакого предварительного конструирования признаков и может обучиться взаимодействиям низкого и высокого порядка на основе одних и тех же входных данных, разделяющих один и тот же слой представления. DeepFM действительно содержит Машину Факторизации как часть основной сети, тогда как Wide&Deep не выполняет произведение векторов в какой-либо части сети, а делает это предварительно на шаге конструирования признаков.

3. DLRM – рекомендационная модель глубокого обучения

Ну что ж, рассмотрев различные варианты от Google, Huawei (команда исследователей, стоящая за архитектурой DeepFM) и прочих, давайте познакомимся с видением исследователей Facebook. Они опубликовали свою статью о DLRM в 2019-м, и она в основном фокусируется на практической реализации этих моделей. Решения с параллельным обучением, переложение расчетов на GPU, а также различная обработка постоянных и категориальных признаков.

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

Нейронная сеть DLRM, как описано в <a href="http://arxiv.org/abs/1906" target="_blank" rel="noopener noreferrer nofollow">статье про DLRM</a>. Рисунок Макса Беккерса
Нейронная сеть DLRM, как описано в статье про DLRM. Рисунок Макса Беккерса

Предложение DLRM – это нечто вроде упрощенной и модифицированной версии DeepFM в том смысле, что оно также использует произведение векторов, но намеренно пытается держаться подальше от взаимодействий высших порядков, не обязательно прогоняя представленные категориальные признаки через многослойный перцептрон. Такой дизайн предназначен для копирования подхода, используемого в Машине Факторизации, когда она рассчитывает взаимодействия второго порядка между представлениями. Мы можем рассматривать всю DLRM как отдельную часть DeepFM, компонент FM. Можно считать, что классический Глубокий компонент DeepFM, вывод которого складывается с выводом компонента FM в финальном слое DeepFM (а потом передается в функцию сигмоиды) в DLRM полностью отсутствует. Теоретические преимущества DeepFM очевидны, поскольку ее дизайн намного лучше приспособлен для изучения взаимодействий высших порядков, однако, по мнению специалистов Facebook:

“взаимодействия выше второго порядка, используемые в других сетях, не обязательно стоят дополнительных затрат вычислительной мощности и памяти”.

4. Обзор и кодирование

Представив различные подходы к глубокой рекомендации, их теоретические основы, преимущества и недостатки, я был просто вынужден взглянуть на предлагаемую реализацию DLRM на PyTorch на GitHub-странице Facebook.

Я изучил детали реализации и протестировал предлагаемые специальные API наборов данных, которые авторы создали для прямой обработки различных наборов данных. Как соревнование по рекламе дисплеев на Kaggle от Criteo, так и их набор данных Terabyte имеют готовые реализации API, их можно загрузить и впоследствии использовать для обучения полной DLRM всего одной командой bash (инструкции см. в репозитории DLRM). Затем я расширил API модели DLRM от Facebook, добавив шаги загрузки и предварительной обработки для другого набора данных, “Предсказание показателя кликабельности для рекламы DIGIX в 2020”. Результат можно найти здесь.

Примерно так же, как и для приведенных авторами примеров, после загрузки и распаковки данных DIGIX, вы также сможете обучить модель на этом наборе данных одной командой bash. Все шаги предварительной обработки, размеры представлений и параметры архитектуры нейронной сети были настроены на обработку набора данных DIGIX. Блокнот, который проведет вас по этим шагам, можно найти здесь. Эта модель выдает приличные результаты, и я продолжаю над ней работать с целью улучшения производительности посредством лучшего понимания необработанных данных и процесса работы с рекламными объявлениями, используемого в DIGIX. Специализированная очистка данных, настройка гиперпараметров и конструирование признаков – все это вещи, над которыми я хотел бы еще поработать, и они упомянуты в блокноте. Моей первой целью было технически рациональное расширение API модели DLRM, способное использовать необработанные данные DIGIX в качестве входных данных.

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

Ссылки

Стеффен Рендл, “Машины факторизации”, Международная конференция IEEE по Data Mining, стр. 995-1000, 2010.

Ксианьян Хе, Лизи Ляо, Ханванг Жанг, Ликианг Ли, Ксиа Ху и Тат-Сенг Чуа. “Нейронная коллаборативная фильтрация”, Материалы 26-й международной конференции по World-Wide Web, стр. 173-182, 2017.

Хуифенг Гуо, Руиминг Тэнг, Юнминь Е, Женгуо Ли и Ксиукианг Хе. “DeepFM: нейронная сеть для предсказания показателя кликабельности, основанная на машине факторизации”, препринт arXiv:1703.04247, 2017.

Джианксун Лиан, Ксиаохуан Жоу, Фуженг Жанг, Жонгксиа Чен, Ксинг Кси и Гуангжонг Сун. “xDeepFM: комбинируем явные и неявные взаимодействия признаков для рекомендательных систем”, в Материалах 24-й международной конференции ACM SIGKDD по исследованию знаний и Data Mining, стр. 1754–1763. ACM, 2018.

Хенг-Це Ченг, Левент Коц, Джеремия Хармсен, Тал Шакед, Тушар Чандра, Хриши Арадхье, Глен Андерсон, Грег Коррадо, Вей Чай, Мустафа Испир, Рохан Анил, Закария Хак, Личан Хонг, Вихан Джайн, Ксяобинг Лю и Хемаль Шах. “Широкое и глубокое обучение для рекомендательных систем”, в материалах 1-го семинара по глубокому обучению рекомендательных систем”, стр. 7-10, 2016.

М. Наумов, Д. Мудигер, Х.М. Ши, Дж. Хуанг, Н. Сундараман, Дж. Парк, Кс. Ванг, У. Гупта, Ц. Ву, А.Г. Аццолини, Д. Джулгаков, А. Малевич, И. Чернавский, Ю. Лю, Р. Кришнамурти, А. Ю, В. Кондратенко, С. Перейра, Кс. Чен, В. Чен, В. Рао, Б. Джиа, Л. Ксионг и М. Смелянский “Рекомендационная модель глубокого обучения для систем персонализации и рекомендации”, CoRR, vol. abs/1906.00091, 2019. [Онлайн]. Доступна здесь.

02
Мар
2021

🤖 Как устроены современные рекомендательные системы?

Сегодня мы глубоко погрузимся в особенности работы алгоритмов искусственного интеллекта, на которых построили бизнес Facebook, Google и другие ИТ-гиганты. Внимание: статья рассчитана на специалистов.

Современные рекомендательные системы

Не далее чем в мае 2019 Facebook выложил в открытый доступ исходный код некоторых своих подходов к рекомендациям и представил DLRM (Deep-Learning Recommendation Model – рекомендательную модель глубокого обучения). Эта статья попробует объяснить, как и почему DLRM и другие современные подходы к рекомендациям работают настолько хорошо, посредством анализа их происхождения от прежних результатов в данной области и детального объяснения внутренних деталей их работы и заложенных в них идей.


Персонализированная реклама, основанная на ИИ, сегодня царствует в онлайн-маркетинге, и такие компании, как Facebook, Google, Amazon, Netflix и прочие – короли джунглей этого онлайн-маркетинга, поскольку они не просто усвоили этот тренд, а фактически сами воплотили его в жизнь и построили на нем всю свою бизнес-стратегию. Netflix’овские “другие фильмы, которые могут вам понравиться” и Amazon’овские “люди, купившие это, купили также…” – всего лишь несколько примеров из реального мира.

Само собой, будучи постоянным пользователем Facebook и Google, в какой-то момент я спросил себя:

КАК ИМЕННО ЭТА ШТУКА РАБОТАЕТ?

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

Чтобы понять, откуда происходят современные передовые рекомендательные системы, нам придется взглянуть на два основных подхода к задаче

предсказания, насколько данному пользователю понравится данный продукт,

которая в мире онлайнового маркетинга складывается в предсказание показателя кликабельности (click-through rate, CTR) для возможных рекламных объявлений, основанное как на явной обратной связи (рейтинги, лайки и т.п.), так и на неявной (клики, истории поиска, комментарии или посещения веб-сайтов).

Коллаборативная фильтрация против фильтрации на основе содержимого

1. Фильтрация на основе содержимого (content-based filtering)

Грубо говоря, рекомендация на основе содержимого пытается предсказать, понравится ли пользователю некоторый продукт, используя его онлайновую историю. Это включает, помимо всего прочего, поставленные пользователем лайки (например, на Facebook), ключевые слова, которые он искал (например, в Google), а также простые клики и посещения определенных веб-сайтов. В конечном счете она концентрируется на собственных предпочтениях каждого пользователя. Мы можем, например, построить простой бинарный классификатор (или регрессор), предсказывающий ожидаемый уровень кликабельности (или рейтинг) определенной группы рекламных объявлений для данного пользователя.

2. Коллаборативная фильтрация

Коллаборативная фильтрация пытается предсказать, может ли пользователю понравиться определенный продукт, путем анализа предпочтений похожих пользователей. Здесь мы можем подумать об уже привычном для нас (по примеру рекомендации фильмов) подходе факторизации матриц (matrix factorization – MF), при котором матрица рейтингов приводится к одной матрице, описывающей пользователей и другой, описывающей фильмы.

Недостаток классической MF в том, что мы не можем использовать никакие признаки, кроме пользовательских оценок – например, жанр фильма, год выхода и т.д. – MF приходится догадываться обо всем этом из имеющихся оценок. Кроме того, MF страдает от так называемой “проблемы холодного старта”: новый фильм, который еще никто не оценил, не может быть рекомендован. Фильтрация на основе содержимого справляется с этими двумя проблемами, но ей не хватает предсказательной мощности просмотра предпочтений других пользователей.

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

1. Машина Факторизации (Factorization Machine)

Одна из идей гибридной модели, предложенная Стеффеном Рендлом в 2010-м – это Машина Факторизации. Она придерживается базового математического подхода, комбинируя факторизацию матриц с регрессией:

y^(x):=w0+∑i=0nwixi⏟regressionpart+∑i=1n∑j=i+1n⟨vi,vj⟩xixj⏟MFpartw0∈R;w∈Rn;V∈Rn∗k;vi,vj∈Rk

Здесь <vi, vj> – произведение векторов, которые можно рассматривать как строки матрицы V.

Понять смысл этого уравнения довольно просто, если посмотреть на пример представления данных x, попадающих в эту модель. Давайте рассмотрим пример, представленный Стеффеном в его статье о Машине Факторизации.

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

  • пользователь u из множества U = {Alice (A), Bob (B),…}
  • фильм i из множества I = {“Титаник” (TN), “Ноттинг Хилл” (NH), “Звездные Войны” (SW), “Стар Трек” (ST),…}
  • оценка r из {1, 2, 3, 4, 5}, поставленная во время t.
Рис.1. С. Рендл, "Машины факторизации", Международная конференция IEEE по Data Mining, 2010.
Рис.1. С. Рендл, “Машины факторизации”, Международная конференция IEEE по Data Mining, 2010.

Посмотрев на приведенный выше рисунок, мы увидим представление данных в гибридной рекомендательной модели. Как разреженные признаки, представляющие пользователя и оцениваемый объект, так и любая другая дополнительная информация об объекте или мета-информация (в этом примере – Time и Last Movie Rated) попадают в вектор признаков x, который соответствует значению целевой переменной y. Теперь главное – то, как они обрабатываются моделью.

  • Регрессионая часть FM обрабатывает и разреженные, и плотные данные (например, Time), как обычная задача линейной регрессии, и, таким образом, может считаться подходом фильтрации на основе содержимого в составе FM.
  • Часть MF отвечает за взаимодействие между блоками признаков (например, взаимодействие между “Пользователем” и “Фильмом”), где матрицу V можно рассматривать как встроенную матрицу, используемую в подходах коллаборативной фильтрации. Эти отношения пользователь-фильм предоставляют нам догадки вроде:

Пользователю i, которому соответствует вектор vi (представляющий его предпочтения к параметрам фильмов), похожий на вектор vj пользователя j, скорее всего, понравятся те же фильмы, что и пользователю j.

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

Однако, несмотря на то, что подход Машины Факторизации с первого взгляда кажется “лучшей моделью из обоих миров”, многие области ИИ, такие, как обработка естественного языка или машинное зрение, давно доказали, что

если взять нейронную сеть, то будет еще лучше!

2. Широкие и глубокие: нейронная коллаборативная фильтрация (NCF) и Глубокие Машины Факторизации (DeepFM)

Для начала бросим взгляд на то, как можно реализовать коллаборативную фильтрацию с помощью нейронных сетей, просмотрев статью об NCF. В конце концов это приведет нас к Глубоким Машинам Факторизации (DeepFM), представляющим собой нейросетевую версию машин факторизации. Мы увидим, почему они превосходят обычные машины факторизации, и как можно интерпретировать архитектуру этих нейронных сетей. Мы увидим, что DeepFM была разработана как улучшение вышедшей до этого модели Wide&Deep от Google, которая была одним из первых крупных прорывов в области глубокого обучения рекомендательных систем. В конце концов это приведет нас к упомянутой выше статье по DLRM, опубликованной Facebook’ом в 2019-м, которую можно считать упрощением и небольшим усовершенствованием DeepFM.

NCF

В 2017-м группа исследователей опубликовала свою работу о Нейронной Коллаборативной Фильтрации (NCF). Она содержит обобщенный фреймворк для изучения нейронных зависимостей, моделируемых факторизацией матриц при коллаборативной фильтрации с помощью нейронной сети. Авторы также объяснили, как получить зависимости высшего порядка (MF имеет порядок всего лишь 2), и как объединить оба эти подхода.

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

Рис. 2. Из статьи "Нейронная коллаборативная фильтрация" Кс. Хе, Л. Ляо, Х. Жанг, Л. Ни, Кс. Ху, Ц. Чуа – Материалы 26-й международной конференции по World-Wide Web, 2017.
Рис. 2. Из статьи “Нейронная коллаборативная фильтрация” Кс. Хе, Л. Ляо, Х. Жанг, Л. Ни, Кс. Ху, Ц. Чуа – Материалы 26-й международной конференции по World-Wide Web, 2017.

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

В реальных задачах мы не просто используем двоичные векторы, соответствующие пользователю и объекту в качестве необработанных данных для их представления, но, очевидно, включаем и прочую дополнительную или мета-информацию, которая может представлять ценность (например, возраст, страну, аудио- и текстовые записи, метки времени,…), так что в реальности у нас получается набор данных очень высокой размерности, сильно разреженный и содержащий смесь качественных переменных с количественными. К этому моменту представленную на рис. 2 нейронную сеть можно считать и рекомендацией на основе содержимого в виде простого нейронного бинарного классификатора прямого прохода. И эта интерпретация – ключевая для понимания того, почему этот подход в конце концов оказывается гибридным между коллаборативной фильтрацией и рекомендациями на основе содержимого. Эта нейронная сеть может усвоить любые функциональные зависимости – например, взаимодействия 3-й степени и выше, вроде x1 * x2 * x3, или любые нелинейные трансформации в классическом понимании, используемом в нейронных классификаторах – в виде sigma(.. sigma(w1x1+w2x2+w3x3+b)).

Вооружившись мощью изучения зависимостей высшего порядка, мы можем использовать простой способ изучения зависимостей 1-го и 2-го порядков, скомбинировав нейронную сеть с широко известной моделью для их изучения, Машиной Факторизации. Именно это авторы DeepFM предложили в своей статье. Идея этой комбинации – параллельно изучать зависимости между признаками низких и высоких порядков – ключевая часть многих современных рекомендательных систем, и в том или ином виде ее можно найти почти в каждой архитектуре нейронной сети, предлагаемой в этой области.

DeepFM

DeepFM – это смешанный подход, включающий факторизацию матриц и глубокую нейронную сеть, причем оба используют один и тот же входной слой представления (embedding). Необработанные признаки трансформируются, чтобы закодировать категориальные признаки унитарным кодом (one-hot encoding). Итоговое предсказание (показатель кликабельности), выдаваемое последним словом нейронной сети, определяется так:

y^=sigmoid(yFM+yDNN)

То есть, это сумма предсказаний матричной факторизации и нейронной сети, пропущенная через сигмоидную функцию активации.

Компонент факторизации матриц – это обычная Машина Факторизации, оформленная в стиле архитектуры нейронной сети:

Рис. 3. из статьи Х. Гуо, Р. Тэнг, Ю. Е, Ж. Ли и Кс. Хе "DeepFM – нейронная сеть на основе машины факторизации для предсказания показателя кликабельности. arXiv:1703.04247, 2017
Рис. 3. из статьи Х. Гуо, Р. Тэнг, Ю. Е, Ж. Ли и Кс. Хе “DeepFM – нейронная сеть на основе машины факторизации для предсказания показателя кликабельности. arXiv:1703.04247, 2017

Часть сложения (Addition) этого слоя матричной факторизации получает вектор входных данных x от слоя разреженных признаков (Sparse Features) и умножает каждый элемент на его вес (Normal Connection) перед суммированием. Часть перемножения векторов (Inner Product) также получает вектор x, но только после его прохождения через слой представления и просто перемножает представленные векторы без весов (“Weight-1 Connection”). Сложение обеих частей вместе приводит к вышеупомянутому уравнению для Машины Факторизации:

yFM:=w0+∑i=0nwixi+∑i=1n∑j=i+1n⟨vi,vj⟩xixj

В этом уравнении перемножение xixj нужно только для записи суммы от 1 до n. Оно не является частью вычислений нейронной сети. Нейронная сеть автоматически знает, произведение каких векторов vi и vj потребуется, благодаря архитектуре слоя представления.

Архитектура слоя представления выглядит следующим образом:

Рис. 4. из статьи Х. Гуо, Р. Тэнг, Ю. Е, Ж. Ли и Кс. Хе "DeepFM – нейронная сеть на основе машины факторизации для предсказания показателя кликабельности. arXiv:1703.04247, 2017
Рис. 4. из статьи Х. Гуо, Р. Тэнг, Ю. Е, Ж. Ли и Кс. Хе “DeepFM – нейронная сеть на основе машины факторизации для предсказания показателя кликабельности. arXiv:1703.04247, 2017

Здесь Vp – матрица представлений для каждого поля p={1,2…,m} c k столбцами и количеством строк, соответствующим количеству элементов поля, закодированных двоичным образом. Выход этого слоя представления определяется как

a(0)=[e1,e2,…em]

и важно отметить, что этот слой не полносвязный, а именно – нет связей между необработанным входом любого поля и представлением любого другого поля. Представьте это следующим образом: вектор значений для пола (например, (0, 1)), закодированный унитарным кодом, не может иметь ничего общего с вектором представлений для дня недели (например, вектором (0, 1, 0, 0, 0, 0, 0), закодированный “Вторник”, или его вектором представления, например, для k=4, (12, 4, 5, 9).

Компонент FM – это Машина Факторизации, отражающая высокую важность взаимодействий 1 и 2 порядка, которые прямо складываются с выходом глубокого компонента и передаются в сигмоидную функцию активации последнего слоя.

Глубоким компонентом, как предполагается, теоретически может быть нейронная сеть любой архитектуры. Авторы рассмотрели стандартный многоуровневый перцептрон прямого прохода (а также так называемую PNN). Стандартный многоуровневый перцептрон изображен на следующем рисунке:

Рис. 5. из статьи Х. Гуо, Р. Тэнг, Ю. Е, Ж. Ли и Кс. Хе "DeepFM – нейронная сеть на основе машины факторизации для предсказания показателя кликабельности. arXiv:1703.04247, 2017
Рис. 5. из статьи Х. Гуо, Р. Тэнг, Ю. Е, Ж. Ли и Кс. Хе “DeepFM – нейронная сеть на основе машины факторизации для предсказания показателя кликабельности. arXiv:1703.04247, 2017

Нейронная сеть на основе стандартного многослойного перцептрона со слоем представления между необработанными данными (сильно разреженными после унитарного кодирования категориальных переменных) и следующими слоями нейронной сети описывается следующей формулой:

a(l+1)=σ(W(l)a(l)+b(l))

где sigma – функция активации, W – матрица весов, a – результат функции активации предыдущего слоя, а b – порог.

Это приводит к общей архитектуре нейронной сети DeepFM:

Рис. 6. Общая архитектура DeepFM
Рис. 6. Общая архитектура DeepFM

со следующими параметрами:

  • Скрытый вектор Vi для измерения влияния взаимодействий признака i с другими признаками (слой представления).
  • Vi передается в компонент FM для моделирования взаимодействий 2 порядка (компонент FM).
  • wi взвешивает важность необработанного признака i 1-го порядка (компонент FM).
  • Vi также передается в Глубокий компонент для моделирования всех взаимодействий высших порядков (>2)(Глубокий компонент).
  • WI и bI – веса и пороги нейронной сети (Глубокий компонент).

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

Сравнение с Wide&Deep и NeuMF

Есть много вариаций, о которых можно задуматься, чтобы “отполировать” эту архитектуру и сделать ее еще лучше. Однако в основном все они сходятся в своем гибридном подходе, заключающемся в одновременной обработке взаимодействий высших и низших порядков. Авторы DeepFM также предложили замену многоуровневого перцептрона на так называемую PNN, глубокую нейронную сеть, получающую в качестве входных данных выводы FM и слоя представления.

Авторы статьи про NCF также предложили похожую архитектуру, которую они назвали NeuMF (Neural Matrix Factorization – нейронная факторизация матриц). Вместо использования FM в качестве компонента низшего порядка они используют обычную факторизацию матриц, результаты которой передаются в функцию активации. Этому подходу, однако, не хватает взаимодействий 1 порядка, моделируемых линейной частью FM. Авторы также указали, что модель имеет различные представления пользователя и объекта для матричной факторизации и многослойного перцептрона.

Как упомянуто выше, команда исследователей Google была одной из первых, предложивших нейронные сети для гибридного подхода к рекомендации. DeepFM можно рассматривать как дальнейшеее развитие алгоритма Wide&Deep от Google, который выглядит примерно так:

Рис. 7. Х-Т Ченг, Л. Кос, Дж. Хармсен, Т. Шакед, Т. Чандра, Х. Арадхье, Г. Андерсон, Г. Коррадо, В. Чаи, М. Испир, Р. Анил, З. Хак, Л. Хонг, В. Джейн, Кс. Лю и Х. Шах. "Широкое и глубокое обучение для рекомендательных систем" – Материалы 1 семинара по глубокому обучению для рекомендательных систем, стр. 7-10, 2016.
Рис. 7. Х-Т Ченг, Л. Кос, Дж. Хармсен, Т. Шакед, Т. Чандра, Х. Арадхье, Г. Андерсон, Г. Коррадо, В. Чаи, М. Испир, Р. Анил, З. Хак, Л. Хонг, В. Джейн, Кс. Лю и Х. Шах. “Широкое и глубокое обучение для рекомендательных систем” – Материалы 1 семинара по глубокому обучению для рекомендательных систем, стр. 7-10, 2016.

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

ϕk(x)=∏i=1dxickicki∈{0,1}

Это выражает взаимодействие между d признаками (с предшествующим представлением признаков или без него), умножая их друг на друга (показатель степени равен 1, если xi является частью k-й трансформации).

Легко видеть, что DeepFM является развитием этой модели, поскольку она не требует никакого предварительного конструирования признаков и может обучиться взаимодействиям низкого и высокого порядка на основе одних и тех же входных данных, разделяющих один и тот же слой представления. DeepFM действительно содержит Машину Факторизации как часть основной сети, тогда как Wide&Deep не выполняет произведение векторов в какой-либо части сети, а делает это предварительно на шаге конструирования признаков.

3. DLRM – рекомендационная модель глубокого обучения

Ну что ж, рассмотрев различные варианты от Google, Huawei (команда исследователей, стоящая за архитектурой DeepFM) и прочих, давайте познакомимся с видением исследователей Facebook. Они опубликовали свою статью о DLRM в 2019-м, и она в основном фокусируется на практической реализации этих моделей. Решения с параллельным обучением, переложение расчетов на GPU, а также различная обработка постоянных и категориальных признаков.

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

Нейронная сеть DLRM, как описано в <a href="http://arxiv.org/abs/1906" target="_blank" rel="noopener noreferrer nofollow">статье про DLRM</a>. Рисунок Макса Беккерса
Нейронная сеть DLRM, как описано в статье про DLRM. Рисунок Макса Беккерса

Предложение DLRM – это нечто вроде упрощенной и модифицированной версии DeepFM в том смысле, что оно также использует произведение векторов, но намеренно пытается держаться подальше от взаимодействий высших порядков, не обязательно прогоняя представленные категориальные признаки через многослойный перцептрон. Такой дизайн предназначен для копирования подхода, используемого в Машине Факторизации, когда она рассчитывает взаимодействия второго порядка между представлениями. Мы можем рассматривать всю DLRM как отдельную часть DeepFM, компонент FM. Можно считать, что классический Глубокий компонент DeepFM, вывод которого складывается с выводом компонента FM в финальном слое DeepFM (а потом передается в функцию сигмоиды) в DLRM полностью отсутствует. Теоретические преимущества DeepFM очевидны, поскольку ее дизайн намного лучше приспособлен для изучения взаимодействий высших порядков, однако, по мнению специалистов Facebook:

“взаимодействия выше второго порядка, используемые в других сетях, не обязательно стоят дополнительных затрат вычислительной мощности и памяти”.

4. Обзор и кодирование

Представив различные подходы к глубокой рекомендации, их теоретические основы, преимущества и недостатки, я был просто вынужден взглянуть на предлагаемую реализацию DLRM на PyTorch на GitHub-странице Facebook.

Я изучил детали реализации и протестировал предлагаемые специальные API наборов данных, которые авторы создали для прямой обработки различных наборов данных. Как соревнование по рекламе дисплеев на Kaggle от Criteo, так и их набор данных Terabyte имеют готовые реализации API, их можно загрузить и впоследствии использовать для обучения полной DLRM всего одной командой bash (инструкции см. в репозитории DLRM). Затем я расширил API модели DLRM от Facebook, добавив шаги загрузки и предварительной обработки для другого набора данных, “Предсказание показателя кликабельности для рекламы DIGIX в 2020”. Результат можно найти здесь.

Примерно так же, как и для приведенных авторами примеров, после загрузки и распаковки данных DIGIX, вы также сможете обучить модель на этом наборе данных одной командой bash. Все шаги предварительной обработки, размеры представлений и параметры архитектуры нейронной сети были настроены на обработку набора данных DIGIX. Блокнот, который проведет вас по этим шагам, можно найти здесь. Эта модель выдает приличные результаты, и я продолжаю над ней работать с целью улучшения производительности посредством лучшего понимания необработанных данных и процесса работы с рекламными объявлениями, используемого в DIGIX. Специализированная очистка данных, настройка гиперпараметров и конструирование признаков – все это вещи, над которыми я хотел бы еще поработать, и они упомянуты в блокноте. Моей первой целью было технически рациональное расширение API модели DLRM, способное использовать необработанные данные DIGIX в качестве входных данных.

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

Ссылки

Стеффен Рендл, “Машины факторизации”, Международная конференция IEEE по Data Mining, стр. 995-1000, 2010.

Ксианьян Хе, Лизи Ляо, Ханванг Жанг, Ликианг Ли, Ксиа Ху и Тат-Сенг Чуа. “Нейронная коллаборативная фильтрация”, Материалы 26-й международной конференции по World-Wide Web, стр. 173-182, 2017.

Хуифенг Гуо, Руиминг Тэнг, Юнминь Е, Женгуо Ли и Ксиукианг Хе. “DeepFM: нейронная сеть для предсказания показателя кликабельности, основанная на машине факторизации”, препринт arXiv:1703.04247, 2017.

Джианксун Лиан, Ксиаохуан Жоу, Фуженг Жанг, Жонгксиа Чен, Ксинг Кси и Гуангжонг Сун. “xDeepFM: комбинируем явные и неявные взаимодействия признаков для рекомендательных систем”, в Материалах 24-й международной конференции ACM SIGKDD по исследованию знаний и Data Mining, стр. 1754–1763. ACM, 2018.

Хенг-Це Ченг, Левент Коц, Джеремия Хармсен, Тал Шакед, Тушар Чандра, Хриши Арадхье, Глен Андерсон, Грег Коррадо, Вей Чай, Мустафа Испир, Рохан Анил, Закария Хак, Личан Хонг, Вихан Джайн, Ксяобинг Лю и Хемаль Шах. “Широкое и глубокое обучение для рекомендательных систем”, в материалах 1-го семинара по глубокому обучению рекомендательных систем”, стр. 7-10, 2016.

М. Наумов, Д. Мудигер, Х.М. Ши, Дж. Хуанг, Н. Сундараман, Дж. Парк, Кс. Ванг, У. Гупта, Ц. Ву, А.Г. Аццолини, Д. Джулгаков, А. Малевич, И. Чернавский, Ю. Лю, Р. Кришнамурти, А. Ю, В. Кондратенко, С. Перейра, Кс. Чен, В. Чен, В. Рао, Б. Джиа, Л. Ксионг и М. Смелянский “Рекомендационная модель глубокого обучения для систем персонализации и рекомендации”, CoRR, vol. abs/1906.00091, 2019. [Онлайн]. Доступна здесь.

19
Фев
2021

10 вопросов на позицию специалиста по Data Science

По 5 вопросов с собеседований из двух обязательных для Data Scientist областей знаний — теории вероятности и машинного обучения
— Читать дальше «10 вопросов на позицию специалиста по Data Science»

29
Янв
2021

Задача на собеседовании: провести прямую через набор точек

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