Category: Алгоритмы

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.
— Читать дальше «Задача на собеседовании: провести прямую через набор точек»

19
Янв
2021

Как муравьи решают проблемы коммивояжёров

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

15
Янв
2021

Механика «Тетриса» легла в основу алгоритма «идеального» заполнения гостиниц

Разработчики уже пытаются получить патент на своё «изобретение».
— Читать дальше «Механика «Тетриса» легла в основу алгоритма «идеального» заполнения гостиниц»

04
Янв
2021

🐍 Анимация градиентного спуска и ландшафта функции потерь на Python

Демонстрация работающих примеров визуализации ландшафта функции потерь и анимации процесса градиентного спуска.

Статья публикуется в переводе, автор оригинального текста Tobias Roeschl.

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

Ландшафт функции потерь сверточной нейронной сети с 56 слоями (VGG-56, <a href="https://arxiv.org/abs/1712.09913" target="_blank" rel="noopener noreferrer nofollow">источник</a>)
Ландшафт функции потерь сверточной нейронной сети с 56 слоями (VGG-56, источник)

Приведенное выше изображение демонстрирует крайне невыпуклый ландшафт функции потерь нейронной сети. Ландшафт функции потерь – это визуальное представление значений, которые принимает целевая функция на наших тренировочных данных. Поскольку наша цель – визуализация потерь в трех измерениях, мы должны выбрать два параметра, которые будут изменяться, а остальные параметры останутся неизменными. Однако стоит заметить, что существуют продвинутые техники (например, сокращение размерности или filter response normalization), которые можно использовать для аппроксимации ландшафта функции потерь в подпространстве параметров с более низкой размерностью. Трехмерное представление функции потерь нейронной сети VGG с 56 слоями изображено на рис. 1. Однако это выходит за пределы данной статьи.

Искусственная нейронная сеть, над которой мы будем работать, состоит из одного входного слоя (с 784 узлами), двух скрытых слоев (с 50 и 500 узлами соответственно) и выходного слоя (с 10 узлами). Мы будем везде использовать сигмоиду в качестве функции активации. Эта нейронная сеть не будет содержать никаких порогов. Тренировочные данные состоят из изображений размером 28*28 пикселей с рукописными цифрами от 0 до 9 из набора данных MNIST. Технически, мы могли бы выбрать любые два веса из 784*50+50*500+500*10 = 69.200 весов, используемых в нашей сети, но я произвольно решил выбрать веса w250,5 (2) и w251,5(2), соединяющие 250-й и 251-й узлы второго скрытого слоя с шестым выходным нейроном, соответственно. Шестой выходной нейрон предсказывает, можно ли на данном изображении увидеть цифру ‘5’. Следующий рисунок схематически изображает архитектуру нейронной сети, с которой мы собираемся работать. Для простоты и понятности некоторые связи между нейронами – и большинство подписей с весами – были намеренно опущены.

Рис. 2. Архитектура нейронной сети (создана автором в <a href="https://app.diagrams.net/" target="_blank" rel="noopener noreferrer nofollow">draw.io</a>)
Рис. 2. Архитектура нейронной сети (создана автором в draw.io)

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

        # Импортируем библиотеки
import numpy as np
import gzip
from sklearn.preprocessing import OneHotEncoder
import matplotlib.pyplot as plt
from mpl_toolkits.mplot3d import Axes3D
from scipy.special import expit
import celluloid
from celluloid import Camera
from matplotlib import animation 

# Открываем файлы MNIST: 
def open_images(filename):
    with gzip.open(filename, "rb") as file:     
        data=file.read()
        return np.frombuffer(data,dtype=np.uint8, offset=16).reshape(-1,28,28).astype(np.float32) 

def open_labels(filename):
    with gzip.open(filename,"rb") as file:
        data = file.read()
        return np.frombuffer(data,dtype=np.uint8, offset=8).astype(np.float32) 
    
X_train=open_images("C:\\Users\\tobia\\train-images-idx3-ubyte.gz").reshape(-1,784).astype(np.float32) 
X_train=X_train/255 # rescale pixel values to 0-1

y_train=open_labels("C:\\Users\\tobia\\train-labels-idx1-ubyte.gz")
oh=OneHotEncoder(categories='auto') 
y_train_oh=oh.fit_transform(y_train.reshape(-1,1)).toarray() # one-hot-encoding of y-values
    

Чтобы создать ландшафты потерь, мы собираемся нарисовать трехмерный график потерь по отношению к двум упомянутым выше весам w250_5(2) и w251_5(2). Чтобы это сделать, мы должны определить функцию потерь среднеквадратичной ошибки по отношению к весам w_a и w_b. Потери нашей модели равны средней сумме квадратичных ошибок между предсказаниями модели и истинными значениями для каждого из 10 выходных нейронов. Для N примеров эта функция будет выглядеть так:

J(y,pred)=1N∑i=1N(∑k=110(yi,k−predi,k)2)

Здесь y и pred представляют, соответственно, матрицы актуальных и предсказанных значений y. Предсказанные значения рассчитываются прямым проходом входных данных по нейронной сети до выходного слоя. Выход каждого слоя служит входом для следующего слоя. Входная матрица умножается на матрицу весов соответствующего слоя. После этого применяется функция сигмоиды для получения выхода данного конкретного слоя. Эти матрицы весов инициализируются небольшими случайными числами с помощью генератора псевдо-случайных чисел numpy. Используя инициализацию (seed), мы можем обеспечить воспроизводимость данных. После этого мы заменяем два веса, которым разрешено изменяться, аргументами w_a и w_b. На Python мы можем реализовать функцию потерь следующим образом:

        hidden_0=50 # количество узлов первого скрытого слоя 
hidden_1=500 # количество узлов второго скрытого слоя 

# Зададим функцию потерь:
def costs(x,y,w_a,w_b,seed_):  
        np.random.seed(seed_) # задаем инициализатор генератора случайных чисел 
        w0=np.random.randn(hidden_0,784)  # матрица весов 1-го скрытого слоя
        w1=np.random.randn(hidden_1,hidden_0) # матрица весов 2-го скрытого слоя
        w2=np.random.randn(10,hidden_1) # матрица весов выходного слоя
        w2[5][250] = w_a # задаем значение веса w_250,5(2)
        w2[5][251] = w_b # задаем значение веса w_251,5(2)
        a0 = expit(w0 @ x.T)  # выход 1-го скрытого слоя 
        a1=expit(w1 @ a0)  # выход 2-го скрытого слоя 
        pred= expit(w2 @ a1) # выход последнего слоя 
        return np.mean(np.sum((y-pred)**2,axis=0)) # потери w.r.t. w_a и w_b
    

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

        # Зададим набор значений для ячеистой сети: 
m1s = np.linspace(-15, 17, 40)   
m2s = np.linspace(-15, 18, 40)  
M1, M2 = np.meshgrid(m1s, m2s) # создаем ячеистую сеть  

# Определим потери для каждой координаты ячеистой сети: 
zs_100 = np.array([costs(X_train[0:100],y_train_oh[0:100].T  
                               ,np.array([[mp1]]), np.array([[mp2]]),135)  
                        for mp1, mp2 in zip(np.ravel(M1), np.ravel(M2))])
Z_100 = zs_100.reshape(M1.shape) # Значения z для N=100

zs_10000 = np.array([costs(X_train[0:10000],y_train_oh[0:10000].T  
                               ,np.array([[mp1]]), np.array([[mp2]]),135)  
                       for mp1, mp2 in zip(np.ravel(M1), np.ravel(M2))])
Z_10000 = zs_10000.reshape(M1.shape) # Значения z для N=10,000


# Рисуем ландшафты функции потерь: 
fig = plt.figure(figsize=(10,7.5)) # создаем фигуру
ax0 = fig.add_subplot(121, projection='3d' )
ax1 = fig.add_subplot(122, projection='3d' )

fontsize_=20 # задаем размер шрифта для меток осей 
labelsize_=12 # задаем размер меток делений 

# Настраиваем дочерние рисунки (subplots): 
ax0.view_init(elev=30, azim=-20)
ax0.set_xlabel(r'$w_a$', fontsize=fontsize_, labelpad=9)
ax0.set_ylabel(r'$w_b$', fontsize=fontsize_, labelpad=-5)
ax0.set_zlabel("costs", fontsize=fontsize_, labelpad=-30)
ax0.tick_params(axis='x', pad=5, which='major', labelsize=labelsize_)
ax0.tick_params(axis='y', pad=-5, which='major', labelsize=labelsize_)
ax0.tick_params(axis='z', pad=5, which='major', labelsize=labelsize_)
ax0.set_title('N:100',y=0.85,fontsize=15) # задаем заголовок дочернего рисунка

ax1.view_init(elev=30, azim=-30)
ax1.set_xlabel(r'$w_a$', fontsize=fontsize_, labelpad=9)
ax1.set_ylabel(r'$w_b$', fontsize=fontsize_, labelpad=-5)
ax1.set_zlabel("costs", fontsize=fontsize_, labelpad=-30)
ax1.tick_params(axis='y', pad=-5, which='major', labelsize=labelsize_)
ax1.tick_params(axis='x', pad=5, which='major', labelsize=labelsize_)
ax1.tick_params(axis='z', pad=5, which='major', labelsize=labelsize_)
ax1.set_title('N:10,000',y=0.85,fontsize=15)

# Поверхностные графики потерь (= ландшафты функции потерь):  
ax0.plot_surface(M1, M2, Z_100, cmap='terrain', #поверхностный график
                             antialiased=True,cstride=1,rstride=1, alpha=0.75)
ax1.plot_surface(M1, M2, Z_10000, cmap='terrain', #поверхностный график
                             antialiased=True,cstride=1,rstride=1, alpha=0.75)
plt.tight_layout()
plt.show()
    
Рис. 3. Ландшафты функции потерь для разных размеров тренировочного набора (изображение автора)
Рис. 3. Ландшафты функции потерь для разных размеров тренировочного набора (изображение автора)

Рисунок 3 изображает два примера ландшафтов функции потерь для одних и тех же весов (w250_5(2) и w251_5(2)) и одинаковых начальных значений всех весов. Левый ландшафт был построен на первых 100 изображениях из набора данных MNIST, а правый – на первых 10.000 изображениях. При ближайшем рассмотрении левого графика там можно увидеть типичные особенности невыпуклых поверхностей: локальные минимумы, плато, хребты (иногда называемые “седловыми точками”) и “глобальный” минимум. Однако термин “минимум” следует использовать осторожно, поскольку мы видели лишь небольшой набор значений, и не проводили анализ производной.

Рис. 4 (создан автором с помощью <a href="https://app.diagrams.net/" target="_blank" rel="noopener noreferrer nofollow">draw.io</a>)
Рис. 4 (создан автором с помощью draw.io)

Градиентный спуск

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

we+1=we−αΔJ(we)

Здесь Delta J представляет градиент функции потерь, w – веса всей модели, e представляет текущую эпоху обучения, а aplha – скорость обучения.

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

∂J∂wij(2)=∂J∂outi(2)∂outi(2)∂ini(2)∂ini(2)∂wij(2)

Здесь wij определяется как вес между j-м узлом предыдущего слоя и i-м узлом текущего слоя, которым в нашем случае является выходной слой. Вход i-го нейрона выходного слоя обозначен просто как ini(2), что эквивалентно сумме активаций предыдущего слоя, умноженных на соответствующие веса связей, ведущих к этому узлу. Выход i-го нейрона выходного слоя обозначен как outi(2), что соответствует сигмоиде(ini(2)). Решая приведенное выше уравнение, мы получаем:

∂J∂wij(2)=(outi(2)−targeti)⋅outi(2)⋅(1−outi(2))⋅outj(1)

Здесь outj(1) соответствует активации j-го узла предыдущего слоя, соединенного с i-м нейроном выходного слоя связью с весом wij. Переменная targeti соответствует целевому выводу каждого из 10 нейронов выходного слоя. Возвращаясь к Рис. 2, outj(1) будет соответствовать активации h250 или h251, в зависимости от веса, по которому мы хотим рассчитать частную производную. Прекрасное объяснение обратного распространения (backpropagation), включая математические детали дифференцирования, можно найти здесь.

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

        # Сохраняем значения потерь и весов в списках: 
weights_2_5_250=[] 
weights_2_5_251=[] 
costs=[] 

seed_= 135 # для инициализации генератора случайных чисел
N=100 # размер выборки 

# Задаем нейронную сеть: 
class NeuralNetwork(object):
    def __init__(self, lr=0.01):
        self.lr=lr
        np.random.seed(seed_) # Инициализируем генератор случайных чисел
        # Инициализируем матрицы весов: 
        self.w0=np.random.randn(hidden_0,784)  
        self.w1=np.random.randn(hidden_1,hidden_0)
        self.w2=np.random.randn(10,hidden_1)
        self.w2[5][250] = start_a # задать стартовое значение для w_a
        self.w2[5][251] = start_b # задать стартовое значение для w_b
    
    def train(self, X,y):
        a0 = expit(self.w0 @ X.T)  
        a1=expit(self.w1 @ a0)  
        pred= expit(self.w2 @ a1)
        # Частные производные функции потерь w.r.t. весов выходного слоя: 
        dw2= (pred - y.T)*pred*(1-pred)  @ a1.T / len(X)   # ... среднее по выборке
        # Обновляем веса: 
        self.w2[5][250]=self.w2[5][250] - self.lr * dw2[5][250] 
        self.w2[5][251]=self.w2[5][251] - self.lr * dw2[5][251] 
        costs.append(self.cost(pred,y)) # дописываем значения потерь в список
    
    def cost(self, pred, y):
        return np.mean(np.sum((y.T-pred)**2,axis=0))
    
# Начальные значения w_a/w_b: 
starting_points = [  (-9,15),(-10.1,15),(-11,15)] 

for j in starting_points:
    start_a,start_b=j
    model=NeuralNetwork(10) # установить скорость обучения в 10
    for i in range(10000):  # 10,000 эпох           
        model.train(X_train[0:N], y_train_oh[0:N]) 
        weights_2_5_250.append(model.w2[5][250]) # дописываем значения весов в список
        weights_2_5_251.append(model.w2[5][251]) # дописываем значения весов в список

# Create sublists of costs and weight values for each starting point: 
costs = np.split(np.array(costs),3) 
weights_2_5_250 = np.split(np.array(weights_2_5_250),3)
weights_2_5_251 = np.split(np.array(weights_2_5_251),3)
    

Поскольку мы обновляем только два веса из многих тысяч весов модели, потери будут падать лишь незначительно, несмотря на сравнительно высокую скорость обучения alpha=10. Это также является причиной того, что веса, которые мы собирались изменять, существенно меняются, тогда как остальные веса меняются лишь незначительно при обновлении весов всей модели. Теперь мы можем анимировать три траектории градиентного спуска для трех различных начальных точек.

        fig = plt.figure(figsize=(10,10)) # создаем фигуру
ax = fig.add_subplot(111,projection='3d' ) 
line_style=["dashed", "dashdot", "dotted"] # стили линий
fontsize_=27 # задаем размер шрифта для меток осей 
labelsize_=17 # задаем размер шрифта для меток делений
ax.view_init(elev=30, azim=-10)
ax.set_xlabel(r'$w_a$', fontsize=fontsize_, labelpad=17)
ax.set_ylabel(r'$w_b$', fontsize=fontsize_, labelpad=5)
ax.set_zlabel("costs", fontsize=fontsize_, labelpad=-35)
ax.tick_params(axis='x', pad=12, which='major', labelsize=labelsize_)
ax.tick_params(axis='y', pad=0, which='major', labelsize=labelsize_)
ax.tick_params(axis='z', pad=8, which='major', labelsize=labelsize_)
ax.set_zlim(4.75,4.802) # задаем диапазон значений по z в графике

# Определяем, график каких эпох рисовать:
p1=list(np.arange(0,200,20))
p2=list(np.arange(200,9000,100))
points_=p1+p2

camera=Camera(fig) # создаем объект Camera
for i in points_:
    # Рисуем три траектории градиентного спуска...
    #... каждая начинается из своей начальной точки
    #... и имеет собственный уникальный стиль линии:
    for j in range(3): 
        ax.plot(weights_2_5_250[j][0:i],weights_2_5_251[j][0:i],costs[j][0:i],
                linestyle=line_style[j],linewidth=2,
                color="black", label=str(i))
        ax.scatter(weights_2_5_250[j][i],weights_2_5_251[j][i],costs[j][i],
                   marker='o', s=15**2,
               color="black", alpha=1.0)
    # Surface plot (= loss landscape):
    ax.plot_surface(M1, M2, Z_100, cmap='terrain', 
                             antialiased=True,cstride=1,rstride=1, alpha=0.75)
    ax.legend([f'epochs: {i}'], loc=(0.25, 0.8),fontsize=17) # позиция надписи
    plt.tight_layout() 
    camera.snap() # сделать снимок после каждой итерации
    
animation = camera.animate(interval = 5, # интервал между фреймами в миллисекундах
                          repeat = False,
                          repeat_delay = 0)
animation.save('gd_1.gif', writer = 'imagemagick', dpi=100)  # сохраним анимацию  
    
Рис. 5. Траектории градиентного спуска (создано автором)
Рис. 5. Траектории градиентного спуска (создано автором)

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

        fig = plt.figure(figsize=(10,10)) # создаем фигуру
ax0=fig.add_subplot(2, 1, 1) 
ax1=fig.add_subplot(2, 1, 2) 

# Задаем параметры дочерних рисунков (subplots): 
ax0.set_xlabel(r'$w_a$', fontsize=25, labelpad=0)
ax0.set_ylabel(r'$w_b$', fontsize=25, labelpad=-20)
ax0.tick_params(axis='both', which='major', labelsize=17)
ax1.set_xlabel("epochs", fontsize=22, labelpad=5)
ax1.set_ylabel("costs", fontsize=25, labelpad=7)
ax1.tick_params(axis='both', which='major', labelsize=17)

contours_=21 # задаем количество контурных линий
points_=np.arange(0,9000,100) # определяем, какие эпохи рисовать

camera = Camera(fig) # создаем объект Camera
for i in points_:
    cf=ax0.contour(M1, M2, Z_100,contours_, colors='black', # контурный график
                     linestyles='dashed', linewidths=1)
    ax0.contourf(M1, M2, Z_100, alpha=0.85,cmap='terrain') # контурные графики с заливкой 
    
    for j in range(3):
        ax0.scatter(weights_2_5_250[j][i],weights_2_5_251[j][i],marker='o', s=13**2,
               color="black", alpha=1.0)
        ax0.plot(weights_2_5_250[j][0:i],weights_2_5_251[j][0:i],
                linestyle=line_style[j],linewidth=2,
                color="black", label=str(i))
        
        ax1.plot(costs[j][0:i], color="black", linestyle=line_style[j])
    plt.tight_layout()
    camera.snap()
    
animation = camera.animate(interval = 5,
                          repeat = True, repeat_delay = 0)  # создаем анимацию 
animation.save('gd_2.gif', writer = 'imagemagick')  # сохраняем анимацию в gif
    
Рис.6. Траектории градиентного спуска в 2D (создано автором)
Рис.6. Траектории градиентного спуска в 2D (создано автором)

Обе анимации иллюстрируют, что при невыпуклом ландшафте функции потерь градиентный спуск может “зависнуть” на локальном минимуме, седловой точке или плато. Для преодоления некоторых из этих проблем было изобретено множество вариантов градиентного спуска (ADAGRAD, Adam и т.д.) Однако я хочу разъяснить, что не все ландшафты функции потерь сильно невыпуклые в заданном диапазоне значений w_a и w_b. Выпуклость функции потерь зависит, среди прочего, от количества скрытых слоев – у глубоких нейронных сетей ландшафт функции потерь обычно сильно невыпуклый.

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

Рис. 7. N=500, w200-30(1), w200-31(1). Создано автором (<a href="https://gist.github.com/dbc60bb7c6ef0b8ae3f8ceab8c334b57.git" target="_blank" rel="noopener noreferrer nofollow">код</a>)
Рис. 7. N=500, w200-30(1), w200-31(1). Создано автором (код)
Рис. 8 N=1000, w5_5(1), w5_6(1). Создано автором (<a href="https://gist.github.com/4f87869ae3e94eb6331fb9e213e9f343.git" target="_blank" rel="noopener noreferrer nofollow">код</a>).
Рис. 8 N=1000, w5_5(1), w5_6(1). Создано автором (код).

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

Полный блокнот с исходными текстами визуализации можно найти в моем GitHub’е.

Ссылки

База рукописных цифр MNIST (Янн ЛеКун, Коринна Кортес и Крис Буржс).

  1. Ли Хао и др. “Визуализация ландшафтов функции потерь нейронных сетей”. Достижения нейронных систем обработки информации, 2018.
  2. https://machinelearningmastery.com/how-to-normalize-center-and-standardize-images-with-the-imagedatagenerator-in-keras/
  3. https://machinelearningmastery.com/why-training-a-neural-network-is-hard/
  4. https://mattmazur.com/2015/03/17/a-step-by-step-backpropagation-example/
  5. Мэттью Стэйб, Сашанк Дж. Редди, Сэтьен Кэйл, Санджив Кумар, Суврит Сра. “Избежание седловых точек адаптивными градиентными методами” (2019).
  6. Ян Дофин и др. “Обнаружение и уничтожение проблемы седловых точек при невыпуклой оптимизации в пространстве с большим количеством измерений”. NIPS (2014).
  7. А. Хороманска, М. Хенафф, М. Матье, Г.Б. Аруз и Я. ЛеКун. “Ландшафты функции потерь нейронных сетей со множеством слоев”. Журнал исследований машинного обучения, 38, 192-204.

Приложение

Демонстрационное изображение (создано автором)
Демонстрационное изображение (создано автором)
25
Дек
2020

Как работает лифт в небоскребах? Алгоритмы + задачи с собеседований

Алгоритм по которому работает лифт в высотном здании должен учитывать множество факторов. Он сложнее чем у обычного лифта.
— Читать дальше «Как работает лифт в небоскребах? Алгоритмы + задачи с собеседований»

08
Дек
2020

На GitHub опубликовали алгоритм для расшифровки «пикселизированных» изображений

Очень часто объекты, которые пытаются сделать анонимными, скрывают за пиксельной сеткой. Что-то похожее можно получить, открыв картинку с низким разрешением на полный экран. И вот, судя по всему, начался процесс заката данного способа шифрования.
— Чит…

30
Ноя
2020

Хакатон Code Battle Online: Tetris

Игровой мини-хакатон для начинающих IT-специалистов с базовыми навыками в C#, Java, JavaScript, Python или C++.
— Читать дальше «Хакатон Code Battle Online: Tetris»

24
Ноя
2020

Стоит прочитать: обзор книги Кормена и Лейзерсона «Алгоритмы. Построение и анализ»

В книге охватывается основной спектр современных алгоритмов: сортировки, графовые алгоритмы, динамическое программирование и тому подобное.
— Читать дальше «Стоит прочитать: обзор книги Кормена и Лейзерсона «Алгоритмы. Построение и анализ»»

03
Ноя
2020

🐍Сложность алгоритмов и операций на примере Python

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

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

Такой тип анализа называется статическим, так как не требует запуска программы, – в противовес динамическому, или эмпирическому, анализу, при котором проводятся измерения параметров работающего кода.

Классы сложности операций в Python

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

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

Параметр N, который вы встретите далее, – это размер структуры данных – len(data_structure).

Рассмотрим основные операции некоторых структур данных в Python.

Списки (lists)

Операция Пример Сложность Примечания
Получение элемента l[i] O(1)
Сохранение элемента l[i] = 0 O(1)
Размер списка len(l) O(1)
Добавление элемента в конец списка l.append(5) O(1)
Удаление последнего элемента (pop) l.pop() O(1) То же, что и l.pop(-1)
Очищение списка l.clear() O(1) То же, что и l = []
Получение среза l[a:b] O(b-a) l[1:5] => O(1), l[:] => O(len(l) – 0) = O(N)
Расширение l.extend(...) O(len(…)) Зависит от размера расширения
Создание list(...) O(len(…)) Зависит от размера итерируемой структуры (…)
Сравнение списков (==, !=) l1 == l2 O(N)
Вставка l[a:b] = ... O(N)
Удаление элемента (del) del l[i] O(N) Зависит от i. O(N) – в худшем случае
Проверка наличия x in/not in l O(N) Линейный поиск в списке
Копирование l.copy() O(N) То же, что и l[:]
Удаление значения (remove) l.remove(...) O(N)
Удаление элемента (pop) l.pop(i) O(N) O(N-i). Для l.pop(0) => O(N)
Получение минимального/максимального значения min(l)/max(l) O(N) Линейный поиск в списке
Разворачивание списка l.reverse() O(N)
Перебор for v in l: O(N) В худшем случае, без прерывания цикла (return/break)
Сортировка l.sort() O(N Log N)
Умножение k*l O(k N) 5*l => O(N), len(l)*l => O(N2)

Кортежи (tuples) поддерживают все операции, которые не изменяют структуру данных – и они имеют такие же классы сложности, как у списков.

Множества (sets)

Операция Пример Сложность Примечания
Размер множества len(s) O(1)
Добавление элемента s.add(5) O(1)
Проверка наличия значения x in/not in s O(1) Для списков и кортежей => O(N)
Удаление значения (remove) s.remove(..) O(1) Для списков и кортежей => O(N)
Удаление значения (discard) s.discard(..) O(1)
Удаление значения (pop) s.pop() O(1) Удаляемое значение выбирается “рандомно”
Очищение множества s.clear() O(1) То же, что и s = set()
Создание set(...) O(len(…)) Зависит от размера итерируемой структуры (…)
Сравнение множеств (==, !=) s != t O(len(s)) То же, что и len(t)
Сравнение множеств (<=/<) s <= t O(len(s)) issubset
Сравнение множеств (>=/>) s >= t O(len(t)) issuperset s <= t == t >= s
Объединение (union) s | t O(len(s)+len(t))
Пересечение (intersection) s & t O(len(s)+len(t))
Разность (difference) s – t O(len(s)+len(t))
Симметричная разность s ^ t O(len(s)+len(t))
Перебор множества for v in s: O(N) В худшем случае, без прерывания цикла (return/break)
Копирование s.copy() O(N)

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

Неизменяемые множества (frozen sets) поддерживают все операции, которые не изменяют структуру данных – и они имеют такие же классы сложности, как у обычных множеств.

Словари (dict и defaultdict)

Операция Пример Сложность Примечания
Получение элемента d[k] O(1)
Сохранение элемента d[k] = v O(1)
Размер словаря len(d) O(1)
Удаление элемента (del) del d[k] O(1)
get/setdefault d.get(k) O(1)
Удаление (pop) d.pop(k) O(1)
Удаление (popitem) d.popitem() O(1) Удаляемое значение выбирается “рандомно”
Очищение словаря d.clear() O(1) То же, что и s = {} или s = dict()
Получение ключей d.keys() O(1) То же для d.values()
Создание словаря dict(...) O(len(…))
Перебор элементов for k in d: O(N) Для всех типов: keys, values, items. В худшем случае, без прерывания цикла

Как видно, большинство операций со словарями имеют сложность O(1).

Тип defaultdict поддерживает все эти операции с теми же классами сложности. Таким образом, вызов конструктора в том случае, если значения не найдены в defaultdict, имеет сложность O(1).

Тонкости анализа

Обратите внимание, что операция for i in range(...) имеет сложность O(len(...)). Для for i in range(1, 10) она равна O(1).

Если len(alist) – это N, тогда for i in range(len(alist)) будет иметь сложность O(N), так как цикл выполняется N раз.

При этом for i in range(len(alist)/2) также имеет сложность O(N). В этом случае цикл выполняется N/2 раз, и мы можем отбросить константу 1/2. При увеличении размера списка вдвое выполняемая работа также удваивается.

Точно так же for i in range(len(alist)/1000000) имеет сложность O(N). Это важно понять, так как нас интересует, что происходит, когда N стремится к бесконечности.

***

При сравнении двух списков на равенство, класс сложности должен быть O(N), как указано в таблице выше. Однако в реальности это значение нужно умножить на O==(…), где O==(…) это класс сложности для операции сравнения (==) двух значений в списке. Если мы работаем с целыми числами (int), то сложность сравнения будет равна O(1), если со строками (string), то в худшем случае мы получим O(len(string)).

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

Составные классы сложности

Разобравшись со сложностью отдельных операций мы переходим к их комбинированию.

Закон сложения для O-нотации

O(f(n))+O(g(n))=O(f(n)+g(n))

При сложении двух классов сложности складываются функции этих классов. В конечном счете, O(f(n) + g(n)) приводит нас к большему из двух исходных классов – так как меньший член выражения просто отбрасывается.

Таким образом,

O(N)+O(log⁡N)=O(N+log⁡N)=O(N)

так какN растет быстрее, чем log N:

limx→∞log⁡NN=0

Это правило позволяет вычислить класс сложности для последовательности операций. Например, сначала мы выполняем выражение со сложностью O(f(n)), а следом за ним – O(g(n)). Тогда выполнение обоих выражений (одно за другим) будет иметь сложность O(f(n)) + O(g(n)), то есть O(f(n) + g(n)).

Пример

Вызов функции f(...) имеет сложность O(N), а вызов g(...)O (N * log N). Вызываем эти функции друг за другом:

        f(...)
g(...)
    

Сложность этого действия будет равна:

O(N)+O(Nlog⁡N)=O(N+Nlog⁡N)=O(Nlog⁡N)

Если мы вызовем функцию f(...) дважды:

        f(...)
f(...)
    

то получим:

O(N)+O(N)=O(N+N)=O(2N)=O(N)

Константа 2 в вычислениях отбрасывается.

Условия

Отдельно разберем исполнение условий (if). Сначала выполняется само условие, а затем один из блоков (if или else).

        if test:
  block 1
else:
  block 2
    

Предположим, что вычисление условия test имеет сложность O(T), блока block 1O(B1), а блока block 2O(B2).

Тогда сложность всего кода будет равна:

O(T)+max(O(B1),O(B2))

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

Подставим реальные значения:

  • testO(N),
  • block 1O(N2),
  • block 2O(N).

и вычислим сложность кода:

O(N)+max(O(N2),O(N))=
O(N)+O(N2)=O(N+N2)=O(N2)

Если бы операция test имела класс сложности O(N3), то общая сложность кода составила бы O(N3).

O(N3)+max(O(N2),O(N))=
O(N3)+O(N2)=O(N3+N2)=O(N3)

Фактически, общий класс сложности для if-условий можно записать еще проще:

O(T)+O(B1)+O(B2)

Для первого примера в этом случае получим:

O(N)+O(N2)+O(N)=O(N2)

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

Закон умножения для O-нотации

O(f(n))∗O(g(n))=O(f(n)∗g(n))

Если мы повторяем O(N) раз некоторый процесс с классом сложности O(f(N)), то результирующий класс сложности будет равен:

O(N)×O(f(N))=O(N×f(N))

Предположим, некоторая функция f(...) имеет класс сложности O(N2). Выполним ее в цикле N раз:

        for i in range(N):
    f(...)
    

Сложность этого кода будет равна:

O(N)×O(N2)=O(N×N2)=O(N3)

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

Статический анализ на практике

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

Для всех трех примеров размер списка обозначим как N, а сложность операции сравнения элементов примем за O(1).

Алгоритм 1

Список уникален, если каждое его значение не встречается ни в одном последующем индексе. Для значения alist[i] последующим фрагментом списка будет срез alist[i+1:].

        def is_unique1 (alist : [int]) -> bool:
  for i in range(len(alist)):             # 1
    if alist[i] in alist[i+1:]:           # 2
      return False                        # 3
  return True                             # 4
    

Определим сложность для каждой строки метода:

  1. O(N) – для каждого индекса. Создание объекта range требует выполнения трех последовательных операций: вычисления аргументов, передачу их в __init__ и выполнение тела __init__. Две последние имеют класс сложности O(1). Сложность len(alist) также O(1), поэтому общая сложность выражения range(len(alist)) – O(1) + O(1) + O(1) = O(1).
  2. O(N) – получение индекса + сложение + создание среза + проверка in: O(1) + O(1) + O(N) + O(N) = O(N)
  3. O(1) – в худшем случае никогда не выполняется, можно проигнорировать.
  4. O(1) – в худшем случае всегда выполняется.

Таким образом, класс сложности целой функции is_unique1 равен:

O(N)×O(N)+O(1)=O(N2)

Если размер списка увеличится вдвое, то выполнение функции займет в 4 раза больше времени.

***

Возможно, вы хотели написать так:

O(N)×(O(N)+O(1))+O(1)

ведь выражение if cостоит из вычисления самого условия (O(N)) и блока return False (O(1)). Но в худшем случае этот блок никогда не будет выполнен и цикл продолжится, поэтому мы не включаем его в формулу. Но даже если добавить его, то ничего не изменится, так как O(N) + O(1) – это по-прежнему O(N).

Кроме того, в худшем случае вычисляемый срез списка – это alist[1:]. Его сложность – O(N-1) = O(N). Однако, когда i == len(alist) этот срез будет пуст. Средний срез содержит N/2 значений, что по-прежнему даем нам сложность O(N).

***

Вместо срезов можно использовать вложенный цикл. Сложность функции при этом не изменится.

        def is_unique1 (alist : [int]) ->bool:
  for i in range(len(alist)):          # O(N)
    for j in range(i+1, len(alist)):   # O(N)
      if alist[i] == alist[j]          # O(1)
        return False                   # O(1)
 return True                           # O(1)
    

Класс сложности целой функции тот же:

O(N)×O(N)×O(1)+O(1)=O(N2)

Алгоритм 2

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

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

        def is_unique2 (alist : [int]) -> bool:
  copy = list(alist)             # 1
  copy.sort()                    # 2
  for i in range(len(alist)-1):  # 3
    if copy[i] == copy[i+1]:     # 4
      return False               # 5
  return True                    # 6
    

Сложность по строчкам:

  1. O(N).
  2. O(N log N) – для быстрой сортировки.
  3. O(N) – на самом деле N-1, но это то же самое. Операции получения размера списка и вычитания имеют сложность O(1).
  4. O(1) – сложение, две операции получения элемента по индексу и сравнение – все со сложностью O(1).
  5. O(1) – в худшем случае никогда не выполняется.
  6. O(1) – в худшем случае всегда выполняется.

Общий класс сложности функции is_unique2:

O(N)+O(N×log⁡N)+O(N)×O(1)+O(1)=
O(N+Nlog⁡N+O(N×1)+1)=
O(N+Nlog⁡N+N+1)=O(Nlog⁡N+2N+1)=O(Nlog⁡N)

Сложность этой реализации меньше, чем is_unique1. Для больших значений N is_unique2 будет выполняться значительно быстрее.

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

Класс сложности O(N log N) хуже, чем O(N), но уже значительно лучше, чем O(N2).

Фактически, в код метода можно внести одно упрощение:

        # было
copy = list(alist)    # O(N)
copy.sort()           # O(N log N)

# стало
copy = sorted(alist)  # O(N log N)
    

Функция sorted создает список с теми же значениями и возвращает его отсортированную версию. Поэтому нам не требуется явно создавать копию.

Это изменение ускорит выполнение кода, но не повлияет на его сложность, так как O(N + N log N) = O(N log N). Ускорение – это всегда хорошо, но намного важнее найти алгоритм с минимальной сложностью.

Нужно отметить, что is_unique2 работает только в том случае, если все значения в списке сравнимы между собой (для сортировки используется оператор сравнения <). Если список заполнен одновременно строками и числами, ничего не получится. В то же время is_unique1 использует только оператор ==, который может сравнивать значения разных типов без выбрасывания исключений.

Алгоритм 3

Список уникален, если при превращении в множество (set) его размер не изменяется.

        def is_unique3 (alist : [int]) -> bool:
  aset = set(alist)               # O(N)
  return len(aset) == len(alist)  # O(1)
    

Рассчитать класс сложности для всей функции очень просто:

O(N)+O(1)=O(N+1)=O(N)

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

Тело функции можно записать в одну строчку:

        return len(set(alist)) == len(alist)
    

Сложность при этом не изменится.

В отличие от is_unique2, эта реализация может работать и со смешанными списками (числа и строки). В то же время требуется, чтобы все значения были хешируемыми/неизменяемыми. Например, is_unique3 не будет работать для списка списков.

***

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

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

Кроме того, при анализе важно учитывать дополнительные ограничения реализации (например, типы данных).

Приоритетные очереди

Рассмотрим еще один важный пример зависимости вычислительной сложности от реализации алгоритма – приоритетные очереди.

Этот тип данных поддерживает две операции:

  • добавление значения;
  • извлечение значения с самым высоким приоритетом из оставшихся.

Разные реализации приоритетных очередей имеют разные классы сложности этих операций:

add remove
Реализация 1 O(1) O(N)
Реализация 2 O(N) O(1)
Реализация 3 O(log N) O(log N)

Реализация 1

Новое значение добавляется в конец списка (list) или в начала связного списка (linked list) – O(1).

Чтобы найти приоритетное значение для удаления осуществляется поиск по списку – O(N).

Легко добавить, но трудно удалить.

Реализация 2

Для нового значения определяется правильное место – для этого перебираются элементы списка (или связного списка) – O(N).

Зато самое приоритетное значение всегда находится в конце списка (или в начале связного списка) – O(1).

Легко удалить, но трудно добавить.

Реализация 3

Используется двоичная куча, которая позволяет реализовать обе операции со “средней” сложностью O(log N), что для больших значений ближе к O(1), чем к O(N).

Теперь проведем анализ этих реализаций на реальных задачах.

Сортировка

Чтобы отсортировать N значений с помощью приоритетной очереди, нужно сначала добавить все значения в очередь, а затем удалить их все.

Реализация 1

N×O(1)+N×O(N)=O(N)+O(N2)=O(N2)

Реализация 2

N×O(N)+N×O(1)=O(N2)+O(N)=O(N2)

Реализация 3

N×O(log⁡N)+N×O(log⁡N)=
O(Nlog⁡N)+O(Nlog⁡N)=O(Nlog⁡N)

Примечание: N * O(…) – это то же самое, что и O(N) * O(…).

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

Третья реализация оказывается быстрее всех, так как ее среднее время O(N log N) ближе к O(1), чем к O(N).

10 максимальных значений

Теперь найдем с помощью приоритетной очереди 10 максимальных значений. Для этого в очередь помещаются N элементов, а извлекаются только 10.

Реализация 1

N×O(1)+10×O(N)=O(N)+O(N)=O(N)

Реализация 2

N×O(N)+10×O(1)=O(N2)+O(1)=O(N2)

Реализация 3

N×O(log⁡N)+10×O(log⁡N)=
O(Nlog⁡N)+O(log⁡N)=O(Nlog⁡N)

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

***

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

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

09
Сен
2020

Краткое описание десяти основных алгоритмов на графах с визуализацией графов и примерами использования алгоритмов на практике.

Графы стали мощным средством моделирования и представ…

18
Авг
2020

Какой самый сложный алгоритм вы использовали в своей работе — рассказывают эксперты

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

21
Май
2020

Зачем программисту изучать алгоритмы

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

14
Апр
2020

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

Небольшая заметка про отображение бинарных файлов в виде картинок и применение средств computer vision для обнаружения троянов и вирусов.

Любой софт,
предназначенный специально д…

04
Мар
2020

Хороший, плохой, злой: как Яндекс использует нейросети для борьбы со спамом и матом

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

Любой сайт, где пользователи могут са…

24
Фев
2020

Как шифровать информацию с помощью роста кристаллов

Учёные из Университета Глазго показали, что истинно случайные числа для криптографии можно создавать, наблюдая за ростом кристаллов. Рассказываем, как это работает.

Эпоха автомат…

04
Фев
2020

Python и динамическое программирование на примере задачи о рюкзаке

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

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

Описание проблемы

Представим, что на данный момент вы живёте в довольно большой квартире площадью 100 м2, а вещи занимают 50 м2. Вы знаете, что площадь нового жилья составит 40 м2 и хотите, чтобы вещи занимали не более 20 м2. Вы любите, когда на полу есть свободное место, да и не всё можно поставить впритык друг к другу. Нужно составить список вещей, определить площадь, занимаемую каждой вещью и составить рейтинг ценности предметов. Конечная цель – максимизировать материальную ценность того, что разместится на 20 квадратных метрах.

Перечисляем предметы

Вы составили список вещей и выразили занимаемую площадь в квадратных дециметрах (1 дм2 = 0.01 м2). Каждому предмету сопоставили ценность по шкале от 0 до 100. Получилась сводка данных о 29 предметах, которую можно оформить как словарь вида {'название предмета':(площадь, ценность) }:

            stuffdict = {'couch_s':(300,75), 
             'couch_b':(500,80), 
             'bed':(400,100), 
             'closet':(200,50), 
             'bed_s':(200,40), 
             'desk':(200,70), 
             'table':(300,80),
             'tv_table':(200,30),
             'armchair':(100,30),
             'bookshelf':(200,60), 
             'cabinet':(150,20),
             'game_table':(150,30),
             'hammock':(250,45),
             'diner_table_with_chairs':(250,70),
             'stools':(150,30),
             'mirror':(100,20),
             'instrument':(300,70),
             'plant_1':(25,10),
             'plant_2':(30,20),
             'plant_3':(45,25),
             'sideboard':(175,30),
             'chest_of_drawers':(25,40),
             'guest_bed':(250,40),
             'standing_lamp':(20,30), 
             'garbage_can':(30,35), 
             'bar_with_stools':(200,40), 
             'bike_stand':(100,80),
             'chest':(150,25),
             'heater':(100,25)
            }
        

Готово! Теперь видно, что кровать ('bed') занимает 400 дм2, а её ценность составляет 100, игровой стол ('game_table') занимает 150 дм2 квадратных метра и имеет ценность 30.

Максимазация ценности

Как максимизировать суммарную ценность объектов так, чтобы суммарная площадь не превышала 2000 дм2? Можно попробовать перебрать все возможные комбинации и рассчитать суммарную ценность для каждой из комбинаций. Решение получится, если выбрать максимальную суммарную ценность для 2000 дм2. Но вот незадача: и комбинаторика, и теория множеств утверждают, что 29 предметов дают 2²⁹ возможных комбинаций выбора предметов.

То есть более 536 миллионов. Похоже, такой перебор займёт некоторое время. Нельзя ли быстрее?

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

Примечание: описанные выше случаи соответствуют полному перебору (метод «грубой силы», англ. brute force) и жадному (англ. greedy) алгоритму.

***

Динамическое программирование

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

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

Этапы решения задачи с помощью динамического программирования

  1. Создаём словарь со списком элементов и их параметрами (площадь, ценность).
  2. Создаём списки значений площади и ценности.
  3. Используем списки для построения таблиц мемоизации.
  4. Получаем элементы из последней строки таблицы. Последняя строка таблицы мемоизации содержит оптимальное решение. Возможно, существует несколько оптимальных решений. Например, когда есть два предмета с одинаковой площадью и стоимостью или ряд предметов имеют суммарные площадь и ценность, как у другого предмета.

Рассмотрим, как реализовать этот план на практике. Первый шаг мы предусмотрительно выполнили ранее, перейдём ко второму.

Создаём списки значений площади и ценности

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

            def get_area_and_value(stuffdict):
    area = [stuffdict[item][0] for item in stuffdict]
    value = [stuffdict[item][1] for item in stuffdict]        
    return area, value
        

Используем списки для мемоизации

Пусть n – общее число предметов, A – их максимально допустимая суммарная площадь в новом жилище (2000 дм2). Составим таблицу из n + 1 строк и A + 1 столбцов. Строки пронумеруем индексом i, столбцы – индексом a (чтобы помнить что в столбцах площадь, area). То есть в качестве номеров столбцов мы рассматриваем дискретные значения площади, отличающиеся друг от друга на 1.

            def get_memtable(stuffdict, A=2000):
      area, value = get_area_and_value(stuffdict)
      n = len(value) # находим размеры таблицы
      
      # создаём таблицу из нулевых значений
      V = [[0 for a in range(A+1)] for i in range(n+1)]

      for i in range(n+1):
            for a in range(A+1):
                  # базовый случай
                  if i == 0 or a == 0:
                        V[i][a] = 0

                  # если площадь предмета меньше площади столбца,
                  # максимизируем значение суммарной ценности
                  elif area[i-1] <= a:
                        V[i][a] = max(value[i-1] + V[i-1][a-area[i-1]], V[i-1][a])

                  # если площадь предмета больше площади столбца,
                  # забираем значение ячейки из предыдущей строки
                  else:
                        V[i][a] = V[i-1][a]       
      return V, area, value
        

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


Если площадь текущего элемента меньше или равна площади (номеру столбца) текущей ячейки, вычисляем значение ячейки следуя правилу:

            V[i][a] = max(value[i-1] + V[i-1][a-area[i-1], V[i-1][a])
        

То есть выбираем максимальное из двух значений:

  1. Сумма ценности текущего предмета value[i-1] и величины элемента из предыдущей строки i-1 с площадью, меньшей на величину площади текущего предмета area[i-1]. Обратите внимание: нужно помнить, что элементы в таблице отличаются по нумерации на единицу из-за нулевой строки.
  2. Значение элемента предыдущей строки с той же площадью, то есть из того же столбца, что текущая ячейка. То же значение устанавливается в случае, если площадь текущей ячейки меньше, чем площадь текущего элемента (см. блок else)

За счёт такого подхода при одной и той же суммарной площади элементов происходит максимизация суммарной ценности.

Забираем нужные элементы из последней строки таблицы

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

            def get_selected_items_list(stuffdict, A=2000):
      V, area, value = get_memtable(stuffdict)
      n = len(value)
      res = V[n][A]      # начинаем с последнего элемента таблицы
      a = A              # начальная площадь - максимальная
      items_list = []    # список площадей и ценностей
    
      for i in range(n, 0, -1):  # идём в обратном порядке
            if res <= 0:  # условие прерывания - собрали "рюкзак" 
                  break
            if res == V[i-1][a]:  # ничего не делаем, двигаемся дальше
                  continue
            else:
                  # "забираем" предмет
                  items_list.append((area[i-1], value[i-1]))
                  res -= value[i-1]   # отнимаем значение ценности от общей
                  a -= area[i-1]  # отнимаем площадь от общей
            
      selected_stuff = []

      # находим ключи исходного словаря - названия предметов
      for search in items_list:
            for key, value in stuffdict.items():
                  if value == search:
                        selected_stuff.append(key)
            
      return selected_stuff
        

Итак, мы нашли список:

            >>> stuff = get_selected_items_list(stuffdict)
>>> print(stuff)
['bike_stand', 'garbage_can', 'standing_lamp', 'chest_of_drawers',
'plant_3', 'plant_2', 'diner_table_with_chairs', 'bookshelf',
'armchair', 'table', 'desk', 'bed', 'couch_s']
        

Проверим суммарные площадь и ценность собранных предметов:

            >>> totarea = sum([stuffdict[item][0] for item in stuff])
>>> totvalue = sum([stuffdict[item][1] for item in stuff])
>>> print(totarea)
2000
>>> print(totvalue)
715
        

Получилось! Собираем вещи и отправляемся в путь (звучит песня Mamas & Paps – San Francisco).

***

Бонус: Тепловая карта таблицы

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


Для построения использовалась библиотека matplotlib:

            def plot_memtable(V, stuffdict):
    plt.figure(figsize=(30,15))
    item_list = list(stuffdict.keys())
    item_list.insert(0, 'empty')
    sns.heatmap(V, yticklabels=item_list)
    plt.yticks(size=25)
    plt.xlabel('Area', size=25)
    plt.ylabel('Added item', size=25)
    plt.title('Value for Area with Set of Items', size=30)
    plt.show()
        

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