Русский
Русский
English
Статистика
Реклама

Optimization

Делаем схему выбора мест в кинозале на React о canvas, красивом дизайне и оптимизации

25.12.2020 18:10:30 | Автор: admin

В богатой экосистеме Тинькофф есть лайфстайл-сервисы. Купить билеты на различные мероприятия - в кино, театры, на концерты, спортивные события можно на https://www.tinkoff.ru/entertainment/, а также в мобильном приложении.

Меня зовут Вадим и я расскажу вам, как мы это делали в команде Развлечений в Тинькофф Банке.


Что нужно, чтобы купить билет в кино?

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

дизайн схемы выбора местдизайн схемы выбора мест

Мы придумали три варианта реализации такой схемы.

1. Сделать все на старом добром HTML

Схема на HTML. Найдено на просторах ИнтернетаСхема на HTML. Найдено на просторах Интернета

Плюсы:

  • Удобно стилизовать.

  • Удобно работать в React.

  • Все доступно (A11Y).

Минусы:

  • Растет количество DOM-нод и глубина DOM-дерева (пример на изображении выше).

  • Проблемы с производительностью при взаимодействии с пользователем (перемещение схемы).

2. Использовать SVG

Плюсы и минусы примерно такие же, как и с HTML.

Получилось найти только схему метро на SVGПолучилось найти только схему метро на SVG

3. Canvas

Стильно. Ярко. Производительно.Стильно. Ярко. Производительно.

Плюсы:

  • Удобно стилизовать (можно нарисовать что угодно).

  • Меньше проблем с производительностью.

Минусы:

  • Не получится совместить с Server Side Rendering.

  • Проблемы с A11Y (нет из коробки).

Мы решили делать схему на canvas, потому что нам важно, чтобы все было красиво и с приятным UX для пользователя. Также с технической стороны у нас пропадают проблемы с глубиной DOM-дерева и количеством нод в нем. Тем более что canvas без проблем работает даже в Internet Explorer 11.

Конечно, на наше решение повлияло и то, что использовать canvas намного интереснее, чем просто работать с SVG- и HTML-решениями.

Экосистема вокруг canvas

Итак, мы отправились выбирать библиотеку для более удобной работы с canvas. Как оказалось, их существует достаточно большое количество, из самых популярных Konva, PixiJS, Fabric.js и Phaser.

Из этого многообразия мы выбрали PixiJS. Ключевые особенности Pixi: он быстрый, гибкий и производительный. Также наши коллеги активно рекомендовали использовать именно его.

Простой код на PixiJS. Мы инстанцируем Pixi.Appс заданным конфигом (например, ширину, высоту, цвет фона, разрешение). Добавляем объекты на сцену (Stage в терминологии Pixi), пишем простой цикл и получаем сетку 5 5 из кроликов, которые вращаются вокруг своей оси пример с официального сайта Pixi

Структура и читаемость

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

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

Вписываем в React

Кроме сложности понимания кода возникает другой вопрос: как это вписать в парадигму React?

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

Одно из решений, которое понравилось нам, библиотека react-pixi-fiber. Ее плюс в том, что мы пишем привычный нам JSX, а под капотом происходит взаимодействие с Pixi и мы получаем наш canvas.

В этой библиотеке у нас уже есть обертки для всех нативных объектов Pixi. К примеру, вместо инстанцирования класса Pixi.Textмы используем react-элемент <Text />.

Также есть удобное АПИ для создания своих объектов CustomPIXIComponent

Приблизительно так теперь выглядит код для нашей схемы выбора мест. Здесь уже нет никаких инстансов Pixi, у нас обычный JSX: компоненты Stage, Container, посадочные места, привычный маппинг данных на react-компоненты.

А вот как выглядит создание своего компонента. Он немного отличается от привычных react-компонентов, но, если разобраться, по сути тут все то же самое. У нас есть ссылка на отображаемый компонент graphics и привычное слово props. Также почти привычным образом мы можем использовать обработчики событий, например ховер, клик и так далее.

Применяем все на практике

Какие у нас были вводные для отрисовки кресел?

У нас была информация в виде массива объектов. В каждом данные, необходимые для отрисовки сиденья: размеры, координаты, номер места и ряда.

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

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

Вариант с загрузкой кресла как простой текстуры мы сразу отбросили: были проблемы с отображением на retina-экранах и в целом с изменением размеров без визуальной деформации. А с SVG в то время были проблемы у PixiJS: некорректно работала подгрузка ассетов в SVG.

Поэтому мы решили сами рисовать каждое кресло.

Рисуем кресло на PixiJS

Для удобства мы разделили кресло на сектора:

A полукруглые края подлокотников.
B подлокотник.
C кривая от подлокотников до спинки кресла.
D спинка кресла.
E верхняя часть кресла.
F средняя часть кресла.
G нижняя часть кресла.

Ширина одной клетки width / 22.
Высота одной клетки height / 16.
Кресло в макете у нас имеет размер 22 пикселя на 16, таким образом, каждая черточка или буковка это пиксель в сетке.

Затем мы разделили эту сетку на зоны: подлокотники, спинка и так далее. И отрисовали все по частям, используя PixiJS и CustomPIXIComponent.

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

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

Схемы секторов

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

От наших партнеров приходила такая схема секторов.
Собственно массив секторов в поле sectors с информацией о каждом секторе, название площадки, а также строка hallScheme, которая занимает почти 236 килобайт.

Как оказалось, это схема секторов площадки в SVG и закодирована в base64.

Что же нам с этим делать?

Первым нашим решением было парсить этот SVG и как-то перевести на PixiJS.

Второй вариант просто вставить это как HTML, повесить обработчики через стандартные методы.

Рассмотрев эти варианты и взвесив плюсы и минусы, мы решили пойти дальше и сделать третий вариант парсить эту SVG и превращать ее в react-элементы.

Выбором для парсера стал html-react-parser. Эта библиотека парсит любой валидный HTML в react-элементы. Работает как на стороне Node.js, так и на стороне браузера. Но решающим стало то, что любой элемент из оригинальной разметки можно заменить на что угодно.

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

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

Вот так теперь выглядит ВТБ Арена.Вот так теперь выглядит ВТБ Арена.

Поговорим об оптимизации

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

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

В замечательной документации по Pixi можно найти упоминание об этом тикере. Как понятно из описания, это некий цикл, который выполняет что-то за некий интервал времени, в нашем случае приблизительно каждые 16 мс.

Но почему именно 16 миллисекунд?

Вспомним понятие 60 кадров в секунду - это нужно, чтобы обеспечить плавность анимации и перемещений. Также, новые фильмы снимают в 60 кадров в секунду, что дает более плавную картинку.

Чтобы получить такую частоту обновления, нужно каждую секунду обновлять изображение 60 раз: 1000 мс 60 = 16,6666 мс.

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

Так как мы не работаем напрямую с Pixi, получить доступ к регулированию цикла обновления мы не могли.

Исходный код компонента Stage из react-pixi-fiberИсходный код компонента Stage из react-pixi-fiber

Как видно, вся работа с Pixi происходит внутри компонента Stage от react-pixi-library. К сожалению, официальных способов от создателей react-pixi-library по работе с Ticker нет.

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

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

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

Пока мы все это изучали, обнаружили, что у Pixi на Github есть целая wiki, где очень много интересной информации:

Забавно, что на оффициальном сайте Pixi ссылку на эту wiki не найти.

Главный совет по оптимизации заключается в том, что инстансы объектов Pixi.Graphics стоят дорого и не кэшируются, в отличие от текстур, спрайтов и так далее. А наши кресла, как сложные объекты, как раз и являются инстансами Pixi.Graphics.

Выводы

Какие выводы из этого всего можно сделать?

  1. Чем меньше оберток тем более гибко мы можем оптимизировать приложение.

  2. Работа с canvas отличается от обычных рутинных задач.

  3. Pixi заточен под более интерактивные вещи, например игры.

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

Подробнее..

Оптимизация работы с PostgreSQL в Go от 50 до 5000 RPS

05.11.2020 20:23:57 | Автор: admin

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


Входе разработки калькулятора цены доставки возникла такая задача: есть структура базы данных PostgreSQL и запрос кней отсервиса наGo. Нужно заставить всё это работать достаточно быстро. Витоге нам удалось поднять пропускную способность сервиса с50 до5000RPS и выявить пару нюансов приобщении сервиса сбазой. Обэтом и пойдёт рассказ.



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


Структура базы данных


Структура базы данных


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


Объём данных такой:


  • send: ~400 тысяч записей;
  • receive: ~160 миллионов записей.

SQL-запрос


SELECT r.terminal_id,       r.lat, r.lon,       r.tariff_zone_id,       r.min_term, r.max_termFROM   receive rINNER JOIN (   SELECT DISTINCT ON (s.provider) provider, tariff_id, s.tag_from_id, Point(s.lat, s.lon) <-> Point (:seller_lat, :seller_lon) AS dist   FROM   send s   WHERE       s.lat BETWEEN :seller_leftbot_lat AND :seller_righttop_lat       AND s.lon BETWEEN :seller_leftbot_lon AND :seller_righttop_lon       AND :now BETWEEN s.active_from AND s.active_until       AND s.max_weight > :weight AND s.max_height > :height AND s.max_length > :length AND s.max_width > :width AND s.max_declared_cost > :declared_cost   ORDER  BY provider, dist   ) AS s USING (tag_from_id)WHERE   r.lat BETWEEN :buyer_leftbot_lat AND :buyer_righttop_lat   AND r.lon BETWEEN :buyer_leftbot_lon AND :buyer_righttop_lon   AND r.max_weight > :weight AND r.max_height > :height AND r.max_length > :length AND r.max_width > :width AND r.max_declared_cost > :declared_costLIMIT :limit;

Чтобы запрос работал быстро, нужно создать пару индексов:


CREATE INDEX send_idx ON send(lon, lat, active_from, active_until);CREATE INDEX receive_idx ON receive(tag_from_id, lon, lat);

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


Порядок полей виндексах тоже важен. Например, долготу(lon) есть смысл ставить виндексе впереди широты(lat): Россия вытянута вширотном направлении, и долгота оказывается более селективна.


Структура БД и SQL запрос.


Сервис наGo


Винтересах статьи сервис будет максимально упрощён. Он всего лишь:


  • разбирает входные данные;
  • формирует запрос и шлёт его вБД;
  • сериализует ответ базы вJSON и отдаёт его.

В реальности он ещё считает цену наоснове tariff_zone_id, но суть та же: основная нагрузка ложится набазу данных, вGo происходит минимум действий. Построен сервис наобычном Server изnet/http и использует одну горутину назапрос.


Архитектура решения


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


Для расчёта цены используем отдельный микросервис сосвоим хранилищем.


В качестве хранилища мы рассматривали Elasticsearch, MongoDB, Sphinx и PostgreSQL. По результатам исследования выбрали PostgreSQL: он закрывает наши потребности и приэтом существенно проще вподдержке длянашей компании, your mileage may vary.


Налоги и комиссии встатье рассматривать не будем. Нас интересует только базовая цена доставки отподрядчика.


Тестовый стенд



Сервис развёрнут вKubernetes натрёх подах по500Мб. База развёрнута вLXC-контейнере с4ядрами и 16Гб памяти. Вкачестве connection pooler используется pgbouncer, развёрнутый вконтейнере сбазой.


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


План запроса


Посмотрим, как исполняется запрос кбазе данных:



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


Основные же затраты идут напоиск поbtree-индексу побольшой таблице.


Результаты в лоб


Пора уже запустить тест.



50RPS / 314мс для99-го перцентиля


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


Подход к оптимизации


Оптимизация это цикл изнескольких шагов:


  1. Определить цели и индикаторы. Чего хотим и как будем измерять успех.
  2. Создать тестовые данные. Внашем случае заполнить базу и сгенерировать ленту запросов ксервису.
  3. Добиться полной нагрузки одного изресурсов, увидеть узкое место.
  4. Расширить узкое место.
  5. Повторять додостижения целей.

Наши цели 200RPS минимум, лучше 500RPS. Индикаторы пропускная способность сервиса и время отклика.


Тестовые данные это важно


Мы старались помаксимуму использовать реальные данные. Использовали их, где получалось, длянаполнения базы, добавив шум. Длясоздания ленты запросов собрали реальные запросы спрода. Где это было невозможно, использовали генератор. Было ясно, что любые предположения, не основанные нареальных данных, будут снижать надёжность результатов тестов.


Изначально мы использовали ленту в20тысяч запросов. И довольно быстро удалось добиться такого результата:



Тут сервис держит 1000RPS при52.5мс. Всё красиво, кроме скачков времени отклика, но давайте попробуем потестировать ту же конфигурацию наленте в150тысяч запросов:



Уже на200RPS сервис заваливается. Запросы отваливаются потаймауту, появляются 500-ки. Оказывается, предыдущий тест врёт примерно в10раз попропускной способности.


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


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


Переезд на pgx/v4


Скачки времени отклика награфиках выше намекают наналичие проблем вподключении сервиса кбазе.


Досих пор мы использовали библиотеку pgx третьей версии и не ограничивали размер пула соединений. Если уж оптимизировать эту часть, то давайте переедем начетвёртую версию и уже наней будем всё настраивать. Тем более, пронеё есть много хороших отзывов.
Переехали, ограничили пул до10соединений. Пробуем:



Стало лучше, но принципиально ничего не изменилось. Вчём дело? Смотрим метрики pgbouncerа:



Синий число активных клиентских соединений (cl_active), красные точки число клиентских соединений, которым не досталось серверного соединения (cl_waiting, правая шкала, снимается раз в30секунд).


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


Откат на pgx/v3


На тот момент баг вpgx/v4 еще не был исправлен, и мы воспользовались воркэраундом: откатились натретью версию и отключили отмены запросов.



Сильно лучше не стало, но самые хорошие новости ждали нас вметриках pgbouncer:



Число активных соединений растёт домаксимума поднагрузкой здесь пул ограничен до12 и не падает доконца теста.


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



130RPS при20параллельных запросах


В метриках контейнера сбазой мы увидели полку воперациях ввода-вывода:



Жёлтое это число операций чтения (растёт вниз). Мы выбрали всю квоту контейнера наоперации чтения, то есть нам удалось, наконец-то нормально нагрузить базу.


Масштабируем базу по диску


Проверим, является ли узким местом диск. Увеличиваем квоту контейнера в8раз, смотрим:



Открытый тест: 500RPS / 109мс



Закрытый тест: 745RPS


В закрытом тесте пропускная способность выросла со130RPS до745 почти линейный рост. Значит, мы действительно упираемся вдиск.


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



Открытый тест: 3000RPS / 602мс



Закрытый тест (20инстансов): 2980RPS / 62мс


Заметим, что закрытому тесту явно не хватает 20параллельных запросов, чтобы нагрузить сервис. Мы съели вообще весь диск навсём сервере сбазой:



Зелёное число операций чтения (растёт вниз)


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


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


Масштабируем базу по памяти


Смотрим размеры наших таблиц и индексов:


SELECT      pg_size_pretty( pg_total_relation_size('send')) send,      pg_size_pretty(pg_indexes_size('send')) send_indexes,      pg_size_pretty( pg_total_relation_size('receive')) receive,      pg_size_pretty(pg_indexes_size('receive')) receive_indexes;

Видим 21Гб данных и 6Гб индексов. Это существенно больше полезного объёма данных, но тут Постгресу виднее.


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


Смотрим список конфигураций и находим вот такую:



8ядер, 64Гб памяти, effective_cache_size 48Гб


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



Открытый тест: 4000RPS / 165мс



Закрытый тест (100инстансов): 5440RPS / 106мс



Операции чтения (зелёное) нануле, операции записи (жёлтое) внезначительных количествах


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



Утилизация CPU полностью загружены все 8ядер


Теперь мы упираемся впроцессор. Это хорошо: масштабировать его относительно просто, а мешать мы никому не будем.


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



Опять cl_waiting подскочил. Вэтот раз, правда, cl_acitve (жёлтое) не падает, а cl_waiting (красные точки, правая шкала) не поднимается выше 12.


Ну, это просто ошибка вконфигурации базы. Размер пула должен быть 24, именно такой пул выставлен всервисе. А настороне базы он остался равным 12. Исправляем, смотрим:



Открытый тест: 5000RPS / 140мс
Закрытый тест (100инстансов): 5440RPS / 94мс


Вот теперь хорошо. Взакрытом тесте результаты те же, а вот воткрытом пропускная способность выросла с4000 до5000RPS. Стоит отметить, что нет никакого смысла использовать больше соединений, чем размер пула БД: это лишь портит производительность. Впрочем, это наблюдение заслуживает более пристального изучения.


Куда делась 1000 RPS


Итак, превышение размера пула сервиса надразмером пула БД вдва раза ведёт кпотере 20% пропускной способности (с5000RPS до4000RPS). Почему? И почему взакрытом тесте разница не видна?


Давайте разберём, что вообще происходит, когда сервис выполняет запрос через pgx. Вот мы посылаем некий запрос:


rows, err := h.db.QueryContext(ctx, `SELECT 1`)

h.db это пул соединений. Внутри QueryContext происходит Pool.Acquire(), который захватывает конкретное соединение длявыполнения нашего запроса. Соединений навсех не хватает, требуется синхронизация, длячего используется sync.Cond:


func (p *Pool) Acquire(ctx context.Context) (*Resource, error) {  //...  p.cond.Wait()  //...

sync.Cond внутри это пара атомиков, мьютекс и очередь насвязном списке (см. notifyList, который используется подкапотом уsync.Cond), то есть издержки насинхронизацию здесь минимальны. Горутина просто записывает себя вконец очереди и паркуется, ожидая, пока рантайм её разбудит. Ктому же всё это происходит настороне сервиса, который не является узким местом внашем случае.


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


Видимо, вэтом и кроется причина потери производительности: мультиплексирование соединений наpgbouncerе поднагрузкой зло.


Разница результатов открытого и закрытого тестов


Почему разница не заметна взакрытом тесте, уменя точного ответа нет, но есть рабочая гипотеза.


Судя покоду find_server(), pgbouncer не стремится любой ценой подключить соединение ксерверному. Нашлось свободное серверное соединение хорошо, подключим. Нет придётся подождать. Этакая кооперативная многозадачность, вкоторой соединения не очень хотят кооперироваться.


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


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


Но это лишь правдоподобные рассуждения, хорошо бы их проверить. Когда-нибудь потом.


Запуск на холодную


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


Перезагружаем сервис и сервер сбазой, смотрим:



Разогнались до5000RPS за10секунд, примерно заминуту домаксимума. Значит, никакие механизмы прогрева кэша нам не нужны, можно сразу подавать боевой трафик.


Переезд pgx/v4, попытка номер два


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



Открытый тест: 5000RPS / 217мс, 5300RPS / 645мс
Закрытый тест: 5370RPS / 43мс


По производительности примерно то же самое, что и втретьей версии. Разница втом, как сервис деградирует призаведомо запредельной нагрузке. Счетвёртой версией это происходит медленнее.


Подбор размера пула в сервисе


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


Общее число соединений есть смысл выбирать винтервале отчисла ядер, доступных базе, доограничения начисло серверных соединений уpgbouncer (каким его выбрать вопрос дляDBA).


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


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


Не забываем


Закрывать результат


Это обсуждали множество раз, но тем не менее. Даже если вдокументации кбиблиотеке написано, что закрывать Rows необязательно, лучше всё же закрыть самому через defer.


rows, err := conn.Query(...)if err != nil {    return err}defer rows.Close()  // лучше закрыть принудительноfor rows.Next() {    // ...}if rows.Err() != nil {    return err}

Как только внутри цикла поrows.Next() случится паника или мы сами добавим туда выход изцикла rows останется незакрытым. Незакрытый результат это соединение, которое не может быть использовано другими запросами, но занимает место впуле. Его придется убивать потаймауту и заменять нановое, а это долго.


Быстрые транзакции


Применительно кpgbouncer: медленные транзакции забивают серверный пул.


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


Особенно опасны незакрытые транзакции, а это ошибка, которую вGo сделать довольно легко. Если pool_mode установлен вtransaction, как это сделано унас, то незакрытая транзакция надолго занимает собой соединение, внашем случае надва часа.


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


Keepalive


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


Проверять гипотезы практикой


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


TL;DR, или выводы


  1. Прокачали сервис от50 до5000RPS, не применяя никакой особой магии.
  2. Мультиплексирование соединений вpgbouncerе поднагрузкой зло.
  3. Использовать всервисе пул большего размера, чем вбазе данных вредно.
  4. Выработать привычку делать транзакции быстрыми и закрывать результаты БД.

Благодарности


Кроме меня надзадачей работали коллеги изДоставки: Кирилл Любаев, Александр Кузнецов, Алексей Власов.


И огромное спасибо всем, кто помогал:
Андрею Аксёнову заидеи, что гео-индексы здесь не нужны, что инты рулят и вообще, проще лучше.
Павлу Андрееву, нашему DBA-инженеру, затерпение и оптимизацию настороне PostgreSQL.

Подробнее..

Quantization Aware Training. Или как правильно использовать fp16 inference в TensorRT

21.05.2021 12:08:14 | Автор: admin

Low-precision inference в TensorRT сегодня - мастхэв, бест практис и прочие иностранные. Сконвертить из TensorFlow легко, запустить легко, использовать fp16 легко. Да и КПД выше, чем у pruning или distillation. На первый взгляд всё работает идеально. Но на самом деле всё ли так гладко? Рассказываем, как мы в TrafficData споткнулись об fp16, встали и написали статью.

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

Что за зверь ваш low-precision?

float16

И так, low-precision inference - запуск нейронных сетей в типе пониженной точности. Но зачем это нужно? По умолчанию все фреймворки учат и сохраняют модели в типе float32. Оказывается, что количество знаков во fp32 - часто избыточно. Ну а зачем нам эти сотни знаков после запятой? Можно просто скастовать fp32 веса во fp16, чтобы получить ускорение прямого прогона и уменьшение используемой памяти в 2 раза. При этом сохранив исходную точность модели. Единственное условие - наличие тензорных ядер в вашем GPU.

int8 и прочее

Кроме fp16 с простым кастованием есть много идей по более оптимальному использованию бит в 16-битном значении. Просто чтобы напомнить:

Но этого мало. Использование нейронных сетей в высоконагруженных системах и мобильных платформах заставляет еще сильнее ужимать сети и ускорять инференс. Добро пожаловать в мир int8 и int4. Да, в них квантуют. Да, в int8 всего 256 значений. Да, это работает. Со своими сложностями, конечно - здесь уже просто так не кастанёшь, как в случае с fp16. Нужно внимательно изучать распределения значений в слоях, чтобы эффективно использовать предоставленный небольшой диапазон значений.

Объясню, почему мы не смотрим на 8/4 битные квантизации. Дело в том, что здесь не обойтись без потери точности. Например, тут говорят как оптимально юзать int4 и радуются, что потеряли не 15%, а 8% точности. Или вот красноречивая табличка от Nvidia о западении точности при использовании int8:

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

TensorRT

Если у вас мобильные решения или просто инференс на CPU, то попробуйте TensorFlow Lite. Но в основном, говоря про low-precision inference в проде, сегодня имеют ввиду TensorRT - кроссплатформенный SDK для супер-быстрой работы на GPU от Nvidia. TensorRT легко превращает ваши модели в оптимизированные Engines. Сконвертить можно из любого нейросетевого фреймворка через ONNX. Engine - очень важная сущность в TensorRT. При билде происходит оптимизация под текущий GPU - на других GPU engine либо не запустится, либо будет работать неоптимально. Короче говоря, есть ряд параметров, которые нужно знать или задать заранее:

  • GPU. На чём собрали Engine, на том пусть он и работает. Но допустим общий билд для карточек одного семейства - Turing или Ampere. Например, мы билдили Engine для RTX 2060 и он замечательно работает на RTX 2080 Super. Создание отдельного Engine для RTX 2080 Super существенного ускорения не создает.

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

  • InputSize. Мы работаем с изображениями. И размер входного изображения иногда может меняться во время рантайма. Но TRT требует его задавать жестко, что логично. Да, есть возможность задать минимальный и максимальный размеры, а TRT создаст несколько профилей оптимизации. Но всё же это не так гибко, как в TensorFlow, а иногда нужно.

  • Precision. Собственно мы можем задать fp32/fp16/int8. Первые два различаются лишь выбором флага. С int8 я мало экспериментировал. Но судя по документации, отличие лишь в необходимости калибровочного датасета - набора картинок, на основании которого TRT определит распределения значений на разных слоях.

Ну и под конец еще добавлю, что в рантайме эти движки отжирают лишь необходимый минимум GPU RAM и замечательно работают параллельно (если правильно работать с TensorRT Context в вашем коде рантайма).

Контекст задачи

Окей, чтобы было понятнее, какие проблемы возникли, пара слов о нашем продукте. Мы пилим TrafficData - ПО для оценки трафика c камер и дронов, в рилтайме и постфактум, в дождь и снег. Нам важно, чтобы ночью детектилось вот так:

И не хуже.

На opentalks.ai2020 мы рассказывали, как, используя Pruning и физичность данных, ускорили обработку в 4 раза и не потеряли в точности. Статью про Pruning я уже выкладывал. Но сегодня давайте поговорим конкретно про low-precision inference.

Как мы запустились и потеряли нежные фичи

Скачивая либы TensorRT, бонусом вы получаете набор примеров с кодом для самых разных архитектур и ситуаций. Для билда движков мы использовали пример SampleUffSSD (UFF - универсальный формат описания сети, через который мы конвертили наши .pb), cлегка его закастомив под входной тензор от YOLO. И хотя TensorRT очень много обновляется и всё больше новых интересных слоев поддерживает, тогда мы запускались на версии, где не было реализации ResizeBilinear операции для Upsample слоя. И мы накостылили Conv2DTranspose вместо него, чтобы не писать кастомный слой. Первая сконверченная модель была радостью, как и её скорость работы.

Даже если перейти с fp32 из TF в fp32 TRT, то уже получается неслабое ускорение - на 15-20%. В конце концов TRT использует и много других оптимизаций, например горизонтальные, вертикальные и любые другие LayerFusion.

Для инференса мы закастомили пример trtExec, обернув его для использования в .NET коде. На вход - байты изображения, на выходе - нераспарсенные байты выхода YOLO. Здесь аккуратно работайте с CudaStream и ExecutionContext. Тогда ни память не утечет, ни потоки обработки не закорраптятся.

И так, мы реализовали TensorRT fp16 inference. Сбилдили движки для разных карточек. Прогнали основные тесты - колебания точности в пределах погрешности. И всё замечательно работало несколько месяцев. А дальше - история.
10:00. Звонок клиента:
- У нас тут на одном ролике TrafficData плохо работает - машинки двоятся.
- Окей, скиньте ролик разберемся.
Смотрим ролик - да, проблема есть. Ролик с тенями и на нём тени отмечаются, как второе авто.

13:00. Добрали изображения в основной датасет. Поставили доучиться с низким LR.

16:00. Тестим на версии с инференсом в TensorFlow - всё замечательно. Билдим новый Engine. Тестим на версии с инференсом в TensorRT - опять машины двоятся:

17:00. Идём домой.

Следующее утро началось с мема:

Стало очевидно, что проблема в TensorRT, а конкретно - в преобразовании весов во fp16. Мы проверили еще несколько других роликов со сложными условиями и увидели, что после преобразования во fp16 проблемы появились и в других местах. Стали появляться пропуски детекции на ночных видео, некоторые билборды стали определяться как авто. Короче вот так мы потеряли нежные, но важные фичи, про которые оригинальная сеть во fp32 знала, а вот во fp16 успешно забыла. Что делать?

Quntization Aware Training. Учи на том, на чем будет работать

Подсознательно мы сразу понимали, что если мы обучаем на fp32, а потом инференсим на fp16, то выйдет неприятная вещь. Вот эти жалкие циферки далеко после запятой потеряны и так влияют. Тогда зачем мы их учили на каждом батче? Идея Quntization Aware Training крайне проста - учи и помни о том типе, в котором будешь инференсить. Т.е. в типе fp16 должны быть все веса сверток, активаций и градиентов. Не удивляйтесь, если первые запуски в TensorFlow окажутся с NaN-лоссом. Просто внимательно инспектируйте происходящее. Мы потратили пару недель, переписали всё обучение на fp16 и проблема была решена.

Как в Tensorflow 2.0?

Тут небольшое отступление о том, как мы были рады обновлению TF2.0. Работая под TF1.15 мы кусали локти, заставляя запуститься обучение во fp16, переписывая слои. Но это заработало. А потом пришел TF2.0 - используешь tf.train.experimental.enable_mixed_precision_graph_rewrite над оптимизатором и всё заводится, как моя Lada Granta. Но всё же стоит обратить внимание на whitelist - не все ноды по умолчанию будут работать во fp16. Часть стоит поправить руками. Ну и дополнительный бонус - огромная экономия памяти, которой не получалось в TF1.15. Батч-сайз для нашей кастомной YOLOv4.5 увеличился в 2 раза - с 4 до 8. Больше батч - лучше градиенты.

Выводы

Fp16 inference - это здорово. Только не стоит забывать про Quntization Aware Training, если вы хотите сохранить точность оригинальной модели. Это позволило нам сделать еще шаг в сторону оптимизации наших и клиентских мощностей:

Что особенно важно в годы дефицита чипов и дорогих GPU. Я всё же за использование GPU в тех местах, где они приносят пользу людям, автоматизируя что-то. А не там, где они приносят прибыль, делая деньги из подогретого воздуха.

А вообще вся тематика ускорения инференса сетей сегодня - очень интересное поле для экспериментов. Хочется попробовать десятки новых способов Pruning, Distillation или квантования в int4, но всех Баксов Банни не догонишь. Пробуйте новое, но не забывайте отдыхать.

Подробнее..

Уравнение теории ценообразования. Ликбез для гика, ч. 9

05.02.2021 16:09:35 | Автор: admin

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

В основу этой статьи легли четыре мои видеолекции из курса Finmath for Fintech, которые можно найти на YouTube: Основное уравнение теории ценообразования, Стохастический коэффициент дисконтирования, Связь цен и корреляции рисков и Избыточная доходность. Риски.

Основное уравнение теории ценообразования

Для начала рассмотрим некоторую игрушечную задачу. Начнем с воображаемого инвестора, который думает, сколько ему потратить сегодня, сколько ему вложить, чтобы получить какую-то прибыль завтра. У него есть горизонт планирования, состоящий из двух дней: сегодня t и завтра t+1. Предположим, поначалу наш инвестор был ленив и потреблял все, что он получал. Назовем это ситуацией потребителя П. Потребитель получает какую-то зарплату et (какой-то доход earnings) и всю ее потребляет сt (consumption). Аналогично выглядит ситуация завтра:

ct+1 = et + 1

Теперь, предположим, наш потребитель задумался о том, чтобы вложить часть своей зарплаты в какой-то актив (A), одна единица которого стоит pt и который завтра принесет инвестору выручку в размере xt+1. Нужно объяснить, почему мы обозначили цену сегодня и выручку завтра разными буквами. Дело в том, что цена сегодня это фиксированное число, она известна. В то время как xt+1 (та выручка, которую принесет актив завтра) это случайная величина, не гарантированная: может быть больше, может меньше. Это рисковый инструмент. Предположим, что наш инвестор решил стать настоящим инвестором (И) и купить N штук этого актива. Тогда его потребление сегодня уменьшается:

сt = et - Npt

Но завтра его потребление увеличится, потому что он получит

сt + 1 = et + 1 + Nxt+1

Возникает естественный вопрос: лучше ли поведение инвестора (И), чем поведение простого потребителя (П)? Уточним вопрос. Какое значение N наиболее оптимально?

Чтобы ответить на это, нужно понять, что именно означает оптимально. То есть мы должны выяснить, какую функцию мы здесь оптимизируем. Мы можем смоделировать поведение инвестора, введя некоторую функцию полезности. Функция полезности или функция удовольствия зависит от уровня потребления. Запишем это. Если сегодня уровень потребления сt, то сегодняшнее значение уровня полезности u(сt). Соответственно, для завтрашнего уровня потребления u(сt+1).

В нашей временной модели, состоящей из двух временных периодов сегодня и завтра, мы бы хотели, чтобы ответ на вопрос какое N является оптимальным? зависел от этих двух величин (u(сt) и u(сt+1)). Поэтому мы сейчас их объединим в одну общую функцию полезности. Наша общая функция полезности будет иметь следующий вид: потребление сегодня плюс бета, помноженная на математическое ожидание потребления завтра.

U = u(сt) + E[u(сt+1)]

Сегодняшнее потребление нам известно, потому что про сегодня у нас есть полная информация. Завтрашнее потребление зависит от того, какова будет величина сt+1. А она включает в себя выручку от того же актива, в который мы вложились. В нашу общую функцию полезности входит ожидаемое удовольствие от потребления завтра. Случайная величина сt+1 включает в себя доход от нашего актива, в который мы вложились, именно поэтому здесь стоит знак математического ожидания. Более того, мы дисконтируем это ожидаемое удовольствие на некоторый коэффициент , который можно назвать коэффициентом нетерпения (нам всегда хочется здесь и сейчас, чем в какой-то абстрактный момент времени завтра).

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

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

Типичным вариантом будет функция такого вида:

Итак, наш инвестор хочет максимизировать общую функцию полезности, найти оптимальный уровень вложений N:

Umax

Условием первого порядка для решения этой оптимизационной задачи является условие равенства нулю производной.

Распишем выражение:

Давайте теперь посмотрим на это уравнение, на условие первого порядка, и решим его относительно цены актива сегодня pt. Величины u'(ct) и не являются случайными, они определены. Поэтому мы их можем внести под знак математического ожидания. Получим следующую формулу:

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

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

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

Стохастический коэффициент дисконтирования

Итак, у нас есть выражение:

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

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

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

Если убрать зависимость от индекса t, то можно записать уравнение установления цен в максимально компактном виде:

Если есть какие-то рисковые инструменты, тогда стоимость будет следующей:

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

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

Простейший случай это вклад. У вас есть 1 рубль сегодня, и вы ожидаете какую-то доходность завтра Rt+1. Это может быть какая-то акция, у которой есть сегодняшняя цена pt. Завтрашняя цена может быть какая-то иная, случайная величина pt+1, плюс дополнительно владельцу этой акции могут быть выплачены какие-то дивиденды dt+1 (цена и дивиденды, конечно, связаны). Это может быть какой-то бонд, у которого, наоборот, купон фиксированный 1, и тогда речь идет о том, какая у него цена сегодня pt. Это может быть опцион, например колл-опцион. Вы покупаете его за некоторую сумму сегодня Ct, и он дает вам выручку, которая связана со страйк-ценой, с ценой актива по какой-то такой формуле из теории опционов: max(St - K, O). Во всех этих и многих других ситуациях (наш список можно продолжить) уравнение установления цен, полученное нами, применимо. С практической точки зрения вопрос заключается только в том, чтобы объяснить или предложить модель построения этого стохастического коэффициента дисконтирования m.

Связь цен и корреляции рисков

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

cov(m,x) = E[mx] - E[m]E[x]

Выражение E[mx] и присутствует в уравнении установления цен. Перепишем наше уравнение установления цен, выразив этот компонент через два остальных члена этого равенства:

pt = E[m]E[x] + cov(m,x)

Само математическое ожидание стохастического коэффициента дисконтирования E[m] можно представить себе следующим образом. Если у нас есть безрисковый вклад, то есть мы вложили единицу, то тогда мы должны получить:

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

Теперь заменим математическое ожидание стохастического коэффициента дисконтирования E[m] на величину, обратную базовой процентной ставке:

Итак, что же у нас получилось? Сегодняшняя цена актива имеет две составляющие. Первая составляющая зависит только от самого актива (это, можно сказать, приведенное, с помощью базовой процентной ставки, к сегодняшнему дню математическое ожидание выручки нашего актива). Вторая составляющая, которая добавляется, связывает наш актив и коэффициент дисконтирования. Назовем вторую часть формулы cov(m,x)платой за риск. Она является поправкой к приведенной текущей стоимости, к первой части формулы. Давайте подумаем, какой может быть поправка. Она может быть как отрицательной, так и положительной. Это зависит от того, как наш актив скоррелирован со стохастическим коэффициентом дисконтирования. Давайте вспомним формулу для m и напишем это выражение чуть более подробно:

Величина u't(ct) не является случайной.

Чем больше потребление, тем меньше становится производная функции u, то есть с увеличением потребления u't+1уменьшается. Если же наш актив ведет себя следующим образом: когда потребление увеличивается, наш актив тоже увеличивается (то есть это актив, который хорошо работает в ситуации, когда экономика и благосостояние растут), то тогда такой актив имеет отрицательную ковариацию cov(m,x). Наш актив становится дешевле. Когда наш актив является чем-то вроде страховки и, наоборот, хорошо работает, когда потребление падает, в тех ситуациях он приносит нам доход. А когда употребление растет, он не так хорош, его поведение, поведение этой случайной величины и поведение производной функции u' одинаковы эта величина положительная, и мы платим дополнительную величину.

Функция u вогнутая, чем больше растет потребление (consumption), тем производная этой функции меньше. Если величина x с ростом потребления увеличивается, то есть ведет себя как актив, который приносит хорошую прибыль, когда экономика растет, он скоррелирован отрицательно с величиной u', и тогда добавка, плата за риск, отрицательна. Какой в этом смысл? Если вы дополнительно инвестируете в такой актив,то ваш уровень потребления как пользователя становится более волатильным и для вас это приемлемо только в том случае, если цена этого актива будет с каким-то дисконтом (cov(m,x) будет снижать цену по сравнению с базовой стоимостью). И наоборот, когда актив это что-то вроде страховки (когда потребление падает) и ведет себя хорошо, то тогда он положительно скоррелирован с производной функцией u, и тогда у вас появляется дополнительная премия, которую вы платите, чтобы инвестировать в этот актив.

Избыточная доходность. Системный и идиосинкратический риск

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

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

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

Посмотрим, что нам еще дает уравнение установления цен, записанное в таком виде:

Рисковый актив x обладает некоторой волатильностью. Заметим, что в наше уравнение установления цен входит именно ковариация m и x, а не вариация случайной величины x. Например, если x и m скоррелированы слабо, значение ковариации практически равно нулю, то, несмотря на то что x может иметь очень большую или очень маленькую волатильность, цена p, согласно этому уравнению, будет той же самой и определяться компонентой формулы E[x]/Rf, фактически от E[x]. Из этого можно сделать вывод: важна волатильность случайной величины x сама по себе, а именно ее проекция на m. Можно записать, что x является суммой двух величин проекции величины x на m и всего остального:

Для проекции можно записать явную формулу:

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

Случайная величина x, ожидаемая доходность актива, может иметь некоторую волатильность, то есть некоторый риск. При этом часть этого риска влияет на цену (является систематическим риском та часть, которая является проекцией на m). Другая же часть, хоть и является случайной, никак не влияет на цену и называется идиосинкратической. Риск какого-то инструмента, какого-то актива, всегда распадается на систематическую и идиосинкратическую части.

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

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

Одной из первых попыток построить работающую модель была попытка под названием CAPM (Capital Asset Pricing Model), которая утверждает, что наш стохастический коэффициент дисконтирования есть просто линейная комбинация, в которую входит Rw доходность портфеля благосостояния.

Доходность этого портфеля благосостояния можно померить, если в качестве ориентира взять какой-нибудь большой индекс, например Standard & Poor's 500, и посмотреть доходность этого индекса. Эту модель называют моделью с одним фактором. Более сложные модели, такие как APT (Arbitrage pricing theory), говорят, что m представляет собой линейную комбинацию нескольких факторов.

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

Все статьи этой серии

Подробнее..

Из песочницы Расширение возможностей алгоритмов Машинного Обучения с помощью библиотеки daal4py

26.10.2020 14:14:03 | Автор: admin

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


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


Введение


Scikit-Learn предоставляет серьёзный набор инструментов для решения Machine Learning задач. Классификация, Регрессия, Кластеризация sklearn обладает алгоритмами для всего этого. С некоторыми из этих алгоритмов мы и поработаем.


В 2019 году на базе Intel Data Analytics Acceleration Library (DAAL) формируется библиотека daal4py. Intel презентовало решение, напрямую относящееся к predictive data analysis, имеющее существенное преимущество среди аналогов за счёт производительности и простоты использования.


Технология daal4py позволяет увеличить производительность
классических методов sklearn за счёт ускоренных вычислений(в частности матричных преобразований), базирующихся на Intel DAAL.


Реализация


Рассмотрим методы daal4py.sklearn на тестовой задаче.


Датасет, опубликованный на kaggle: Cardiovascular Disease dataset
Задачей поставлено создание модели, способной сделать предсказание относительно наличия или отсутствия сердечно-сосудистых заболеваний у человека.


Данная задача задача классификации, поэтому было решено использовать ensamble из моделей LogisticRegression, RandonForestClassifier и KNeighborsClassifier, пропущенные через инструмент подгона параметров GridSearchCV, реализации Scikit-Learn.


Для начала обучим обе реализации алгоритмов на одинаковых параметрах и сравним их:


Функции обучения и вывода лучших классификаторов:


from sklearn.model_selection import GridSearchCV# Best Logistic Regressiondef get_best_clf_lr(name, clf, params):    start = timer()    grid_clf = GridSearchCV(estimator=clf, param_grid=params, n_jobs=-1)    grid_clf.fit(X_train, y_train)    end = timer()    learning_time = end - start    print(learning_time)    return name, learning_time, grid_clf.best_estimator_# Best Random Forest Classifierdef get_best_clf_rf(name, clf, params):    start = timer()    grid_clf = GridSearchCV(estimator=clf, param_grid=params, n_jobs=-1, cv=5)    grid_clf.fit(X_train, y_train)    end = timer()    learning_time = end - start    print(learning_time)    return name, learning_time, grid_clf.best_estimator_# Best K Neighbors Classifierdef get_best_clf_knn(name, clf, params):    start = timer()    grid_clf = GridSearchCV(estimator=clf, param_grid=params, n_jobs=-1)    grid_clf.fit(X_train, y_train)    end = timer()    learning_time = end - start    print(learning_time)    return name, learning_time, grid_clf.best_estimator_

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


from sklearn.ensemble import RandomForestClassifier as RandomForestClassifier_sklfrom daal4py.sklearn import ensemble# Random Forest Classifierparams_RF = {    'n_estimators': [1, 3, 5, 7, 10],    'max_depth': [3, 5, 7, 9, 11, 13, 15],    'min_samples_leaf': [2, 4, 6, 8],    'min_samples_split': [2, 4, 6, 8, 10]}name, lrn_time, model = get_best_clf_lr("RF_sklearn", RandomForestClassifier_skl(random_state = 42), params_RF)learn_data_skl.append([name, model, lrn_time])name, lrn_time, model = get_best_clf_lr("RF_daal4py", ensemble.RandomForestClassifier(random_state = 42), params_RF)learn_data_daal.append([name, model, lrn_time])

Очевидным является прирост скорости обучения моделей. Особенно ярко он выражен на модели KNeigborsClassifier, где скорость обучения модели увеличилась в 45раз. Это невероятный показатель, позволяющий нагружать алгоритм, увеличением количества итераций, перебираемых гиперпараметров или ещё чем-нибудь другим. На остальных алгоритмах ускорение составило 1.5 2 раза.


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


Последующее объединение моделей в ensamble и определяло финальный вид модели.
В качестве метрики качества использовали ROC_AUC score.


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


Заключение


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


GitHub
Dataset
Daal4py

Подробнее..

Black-Box Optimization Challenge, или как подбирать гиперпараметры для моделей

27.01.2021 12:10:40 | Автор: admin

Всем привет! В этом посте я расскажу, как наша команда участвовала и заняла третье место в Black-Box Optimization Challenge соревновании по автоматическому подбору параметров для моделей машинного обучения. Особенность соревнования в том, что алгоритм не знает, какая модель машинного обучения используется, какую задачу она решает, и за что отвечает каждый из оптимизируемых параметров.


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



Меня зовут Никита Сазанович, я учусь на 2-м курсе магистратуры Программирование и анализ данных в Питерской Вышке. На протяжении трех месяцев мы с командой из JetBrains Research участвовали в соревновании по Black-Box Optimization (BBO) и заняли в нем третье место. Команда состояла из меня, Юрия Белоусова и Анастасии Никольской, которые тоже учатся в магистратуре, и руководителя нашей лаборатории Алексея Шпильмана. Наше решение строит разбиение пространства параметров и оптимизирует какой-то его участок, используя байесовскую оптимизацию. Про соревнование, наше решение и смежные понятия мы и поговорим в статье.


Что такое BBO


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



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


По аналогии, black box оптимизация должна оптимизировать какую-то модель, или в общем случае функцию $f$, у которой есть несколько входов $x_1, x_2, ..., x_n$, и есть возможность наблюдать выходной результат. Что за модель, для какой задачи мы наблюдаем результат, и что представляют из себя абстрактные параметры $x_i$, мы не знаем. К примеру, для линейной регрессии $y$ по $x$ мы можем определить два параметра: наклон $k$ и сдвиг $b$. А в качестве функции $f$ будем считать среднеквадратическую ошибку на нашем датасете $\{x_i, y_i\}$ в предположении того, что модель выглядит как $y=kx+b$. Тогда, зная, что у модели есть два вещественных параметра, алгоритм BBO оптимизации должен подобрать оптимальные наклон и сдвиг на нашем датасете.


Конечно, линейная регрессия имеет оптимальное решение в закрытой форме, и оптимизацию таким способом нам проводить не обязательно. Кроме того, даже если мы решили оптимизировать параметры линейной регрессии, а не найти их в закрытой форме, почему бы нам не использовать градиенты среднеквадратической ошибки? И это разумный вопрос, потому что если у нас есть возможность найти градиенты для каждого параметра, мы можем проводить оптимизацию классическими методами. Поэтому BBO в основном применяется в случаях, когда нет возможности посчитать градиент функции потерь по параметрам. Обычно такими параметрами являются гиперпараметры алгоритмов машинного обучения. Например, для метода k-ближайших соседей гиперпараметрами являются количество рассматриваемых соседей $n_{neighbors}$ и степень расстояния $p$, которое используется для определения близости.


Соревнование по BBO


Разобравшись в том, зачем и что собой представляет BBO, давайте поговорим про соревнование. Black-Box Optimization Challenge был организован разработчиками таких компаний, как Twitter, SigOpt, Valohai, Facebook, и проходил в рамках конференции NeurIPS 2020. Вся информация про соревнование расположена по адресу: https://bbochallenge.com.


Постановка задачи была следующая. Проверяющий код загадывает какую-то модель машинного обучения, выбирает датасет и метрику, с помощью которой он будет оценивать наборы гиперпараметров. Для однообразности, в случае если большее значение метрики соответствует лучшему результату (к примеру, метрика точности), проверяющий код будет возвращать отрицание ее значения, чтобы задача всегда заключалась в минимизации. Вашему алгоритму на старте передается информация о количестве параметров и ограничения на каждый из них вида $x_1$ это вещественное число в диапазоне [0.01, 100], $x_2$ это целое число в диапазоне [1, 4], а $x_3$ принимает категориальные значения из набора ['linear', 'poly', 'rbf', 'sigmoid']. Eсли провести обучение загаданной модели на выбранном датасете с предлагаемыми вами параметрами, ваш алгоритм должен предлагать какие-то наборы этих параметров, на которые проверяющий код будет возвращать значения метрики,. Более того, ваш алгоритм должен предлагать не один, а восемь наборов в каждой итерации, после чего он получает результаты. И количество таких итераций (загадал -> получил результаты -> ...) ограничено 16. То есть всего ваш алгоритм может предложить 128 конфигураций. Проверяющий код выставляет вам оценку в зависимости от того, насколько вам удалось уменьшить значение метрики одним из предложенных наборов.


Для лучшего понимания давайте посмотрим, как такое взаимодействие происходит для решения на задаче оптимизации точности классификации рукописных цифр (описание датасета) деревом принятия решений. У дерева принятия решений выделено шесть параметров, которые описаны в классе sklearn DecisionTreeClassifier:


  • $max\_depth$ означает максимальную глубину дерева (целое число от 1 до 15);
  • $min\_samples\_split $ означает минимальное число в процентах от всех сэмплов для того, чтобы дальше рассматривать разбиения этой вершины (вещественное число от 0.01 до 0.99);
  • $min\_samples\_leaf $ означает минимальное число в процентах от всех сэмплов, которое должно быть в любом листе (вещественное число от 0.01 до 0.49);
  • $min\_weight\_fraction\_leaf $ означает минимальный вес, который должен находиться в любом из листьев (вещественное число от 0.01 до 0.49);
  • $max\_features $ означает максимальный процент от всего числа признаков, которые мы будем рассматривать для одного разбиения (вещественное число от 0.01 до 0.99);
  • $min\_impurity\_decrease $ стоит за минимальным уменьшением impurity (число, использующееся для выбора разбиений) в нашем дереве (вещественное число от 0.0 до 0.5).

Рассмотрим некоторые итерации взаимодействия (все вещественные числа представлены с точностью до 3 цифр после запятой):


  • в __init__ алгоритм получает информацию о 6 параметрах, их типах и диапазонах значений;
  • в первом suggest алгоритм предлагает наборы (значения для параметров в порядке представления выше)
    [5, 0.112, 0.011, 0.010, 0.204, 0.250],
    [13, 0.144, 0.052, 0.017, 0.011, 0.362],
    [4, 0.046, 0.077, 0.013, 0.079, 0.075],
    [8, 0.014, 0.204, 0.072, 0.036, 0.237],
    [9, 0.985, 0.065, 0.067, 0.015, 0.122],
    [13, 0.379, 0.142, 0.266, 0.097, 0.313],
    [15, 0.015, 0.088, 0.142, 0.143, 0.438],
    [14, 0.461, 0.020, 0.030, 0.613, 0.204];
  • в первом вызове observe получает результаты
    [-0.107, -0.107, -0.107, -0.107, -0.107, -0.107, -0.107, -0.107];
  • в последнем suggest алгоритм предлагает наборы
    [9, 0.066, 0.013, 0.031, 0.915, 0.000],
    [8, 0.024, 0.012, 0.019, 0.909, 0.010],
    [9, 0.185, 0.020, 0.025, 0.925, 0.005],
    [15, 0.322, 0.014, 0.024, 0.962, 0.001],
    [10, 0.048, 0.018, 0.011, 0.939, 0.015],
    [12, 0.082, 0.017, 0.021, 0.935, 0.006],
    [7, 0.045, 0.015, 0.027, 0.954, 0.009],
    [12, 0.060, 0.014, 0.017, 0.921, 0.011];
  • и получает в observe результаты
    [-0.740, -0.757, -0.614, -0.476, -0.738, -0.747, -0.750, -0.766];
  • в итоге проверяющий код выставляет алгоритму оценку 109.78492, которая получается из минимума полученной метрики и границам, установленными авторами этого теста.

Заметим, что результаты, которые получает алгоритм, это отрицание точности классификации, так как в любом тесте ставится задача минимизации. На первой итерации наши предложения получают точность ~10%, что приблизительно соответствует случайной классификации 10 цифр. Но на последней итерации точности гораздо выше и достигают 76%.


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


Как решать BBO


Одно из самых базовых вариантов решения такой задачи это использование случайного поиска. Это метод и являлся baseline-ом, с которым сравнивались все предложенные решения. Для задачи с двумя параметрами рассмотренные этим методом наборы могут выглядеть так:



Техника довольно простая: мы знаем, сколько каких параметров, и какие значения они принимают. В __init__ мы запоминаем параметры и их диапазоны. На каждой итерации suggest мы сэмплируем 8 наборов из диапазонов и предлагаем их. Обработка результатов нас не интересует, поэтому observe оставляем пустым. Реализация этого метода представлена здесь.


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


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



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


Как же использовать результаты, возвращаемые алгоритму? Ведь понятно, что если мы сами последовательно подбираем гиперпараметры, то мы опираемся на результаты. Пусть мы попробовали два набора $S_1$ и $S_2$, и на наборе $S_1$ наша точность классификации составляет $92\%$, а на наборе $S_2$ $54\%$. Мы не равнодушны к таким результатам. Вероятно, мы не будем больше пробовать обучить нашу модель на параметрах близких к $S_2$, а будем пробовать что-то близкое к $S_1$.


Наиболее популярным способом учета результатов является байесовская оптимизация. Оптимизация происходит из предположения о начальном распределении значений (prior), и с получением дополнительных результатов оно перестраивается (posterior). При использовании байесовской оптимизации в BBO чаще всего прибегают к гауссовским процессам. О них мы и поговорим далее.


Гауссовские процессы


С работой гауссовских процессов разберемся на примере задачи максимизации функции одной переменной $f$. Для оптимизации этой функции мы построим суррогатную модель $s$, которая будет приближать истинную функцию $f$. Описываться наша суррогатная модель будет гауссовским процессом. Значения $s$ будут совпадать с значениями $f$ в тех точках $x_i$, результаты которых мы знаем. Значения в остальных точках $x$ наша модель будет представлять распределениями, ведь мы не знаем их наверняка. Используя гауссовский процесс, эти распределения будут нормальными $\mathcal{N}(\mu,\sigma^2)$. Оценки на среднее $\mu$ и дисперсию $\sigma^2$ получаются из определения гауссовского процесса, который задается значениями в определенных точках и матрицей ковариаций с выбранным ядром. Более подробно про технику гауссовского процесса и нахождения $\mu$ и $\sigma^2$ можно почитать, например, в Википедии. Нам же будет важно его применение для оптимизации.


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



Здесь пунктирной линией показана истинная функция $f$, а сплошной оценки на среднее значение суррогатной модели $s$. Синим фоном можно видеть оценку на отклонение значения от среднего. Для оптимизации функции нам нужно определиться, каким способом мы будем выбирать следующую точку. Эта стратегия обычно называется acquisition function или функцией приобретения. Существует множество способов выбора этой функцией. Наиболее популярными являются вероятность улучшения (Probability of Improvement, PI) и ожидаемое улучшение (Expected Improvement, EI). Они обе вычисляются по текущему оптимуму и оценке на среднее и дисперсию в точке. На рисунке в качестве следующей точки мы выбираем ту, у которой функция приобретения (на рисунке изображена зеленым цветом) максимальна, и предлагаем ее. Получив результат, мы видим следующее:



Добавляется новое наблюдение, и максимум функции приобретения переходит в другую точку, которую мы и запрашиваем далее:



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


В случае BBO нам нужно лишь проводить не максимизацию, а минимизацию, к которой легко перейти. В итоге имеем следующий алгоритм. В __init__ мы запоминаем наше пространство и преобразуем все переменные к вещественным значениям. Далее мы сэмплириуем (используя, например, Latin hypercube sampling) наборы для инициализации в течение нескольких первых итераций. В первых вызовах suggest мы предлагаем наши заготовленные наборы для инициализации. При вызове observe мы всегда лишь сохраняем пары $\{x_i, y_i\}$. А в дальнейших suggest мы поступаем следующим образом:


  1. Строим гауссовский процесс по уже имеющимся наблюдениям $\{x_i, y_i\}$.
  2. Сэмплируем какое-то количество кандидатов $n_{cand}$ (в нашем решении $n_{cand}=min(100*D, 5000)$, где $D$ количество оптимизируемых параметров).
  3. Используя построенный гауссовский процесс, мы вычисляем оценки на средние и дисперсии значений в кандидатах.
  4. Вычисляем функцию приобретения в этих $n_{cand}$ кандидатах и выбираем 8 с наибольшими значениями.
  5. Возвращаем эти точки как наши предложения проверяющему коду.

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


Наш подход


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


В качестве подхода байесовской оптимизации мы использовали алгоритм TuRBO, которой является небольшим ответвлением от классических гауссовских процессов. Основное отличие состоит в том, что оптимизация проводится в доверительном регионе (откуда и название Trust Region Bayesian Optimization). Для интересующихся можно почитать оригинальную статью или код от организаторов соревнования.


Важной же частью нашего решения стало построение разбиения пространства гиперпараметров. Идея состоит в том, что если мы как-то ограничим все пространство допустимых значений, то байесовской модели будет проще получить хорошие результаты за столь малое количество итераций. В примере с методом k-ближайших соседей если мы каким-нибудь обучаемым методом поймем, что хорошее решение лежит в подпространстве, где $n_{neighbors}>50$ и $p\le2$, то имея меньшее пространство (а иногда и количество измерений), наша байесовская модель будет точнее.


Вот как этот обучаемый метод работает. Каждые 4 итерации (то есть не более 4 раз, т.к. всего имеем 16 итераций) мы перестраиваем разбиение всего пространства параметров. Пусть мы перестраиваем разбиение на итерации $t$ (от 1 to $16$), и у нас есть набор наблюдений $D_t$ который состоит из запрошенных нами точек и результатов $(x_1, y_1)$, ..., $(x_{n_t}, y_{n_t})$, где $n_t=8t$. Мы рекурсивно делим текущий набор наблюдений на левое и правое поддеревья. Деление выглядит следующим образом:


  1. Мы запускаем метод k-средних, чтобы разделить наши наблюдения на 2 кластера по значению метрики, которую мы пытается минимизировать. Под 1-ым кластером будем подразумевать точки с меньшим средним значением метрики, а под 2-ым с большим.
  2. Использую эти метки кластеров, мы обучаем SVM модель, которая будет классифицировать точки в кластер 1 или 2. Мы знаем метки для текущих точек, и на них и обучаем модель.
  3. Так как у модели не всегда получается идеально приблизить метки, то наша SVM модель может классифицировать имеющиеся точки не так, как им были назначены кластера. Поэтому для каждой точки мы вычисляем ее кластер заново относительно SVM, и все точки с предсказаниями 1 отправляются в левое поддерево, а с 2 в правое.

Мы продолжаем этот процесс рекурсивно пока не достигнем максимальной глубины $max_{depth}=5$, или количество точек в какой-то вершине станет недостаточным для инициализации байесовской модели в дальнейшем.


Исполнив этот метод, мы получаем дерево, в листьях которого расположены какие-то наборы точек, а в вершинах с детьми находятся SVM модели (критерии разбиения). Имея какую-то случайную точку, мы можем однозначно сопоставить ее с регионом нашего дерева, пройдя по этому дереву от корня до листа.


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


К примеру, рассмотрим такое разбиение и работу TuRBO для модели SVM, у которой было выделено три параметра: коэффициент регуляризации $C$, параметр ядра $gamma$ и эпсилон для критерия остановки $tol$. Три параметра образуют трехмерное пространство. После разбиения пространства можно выделить два региона: точки, которые лежат в самом левом листе (зеленый цвет), и все остальные (красный цвет). Вот как это выглядит:



Темно-зеленым здесь отмечен доверительный регион TuRBO, и именно в нем и строится гауссовский процесс. Черным цветом обозначены 8 точек, которые будут возвращены нашим алгоритмом из suggest в рассматриваемой итерации.


Заключение


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


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


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

Подробнее..

Оптимизация хранимых данных на 93 (Redis)

12.03.2021 16:12:58 | Автор: admin

Хотелось бы поделиться опытом оптимизации данных с целью уменьшения расходов на ресурсы.

В системе рано или поздно встает вопрос об оптимизации хранимых данных, особенно если данные хранятся в оперативной памяти, как это БД Redis.

Как временное решение, можно увеличить RAM тем самым можно выиграть время.

Redis это no-sql база данных, профилировать ее можно с помощью встроенной команды redis-cli --bigkeys, которая покажет кол-во ключей и сколько в среднем занимает каждый ключ.

Объемными данными оказались исторические данные типо sorted sets. У них была ротация 10 дней из приложения.

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

Данные из себя представляли события измененияцены / даты доставки у оффера. Офферов было очень много порядка 15000 в каждом фиде (прайслисте).

Рассмотрим следующий пример данных события по офферу:

Сделано с помощью http://json.parser.online.fr/Сделано с помощью http://json.parser.online.fr/

{"EventName":"DELIVERY_CHANGED","DateTime":"2021-02-22T00:04:00.112593982+03:00","OfferId":"109703","OfferFrom":{"Id":"109703","Name":"Саундбар LG SN11R","Url":"https://www.example.ru/saundbar-lg-sn11r/?utm_source=yandex_market&utm_medium=cpc&utm_content=948&utm_campaign=3&utm_term=109703","Price":99990,"DeliveryAvailable":true,"DeliveryCost":0,"DeliveryDate":"2021-02-24T23:49:00+03:00"},"OfferTo":{"Id":"109703","Name":"Саундбар LG SN11R","Url":"https://www.example.ru/saundbar-lg-sn11r/?utm_source=yandex_market&utm_medium=cpc&utm_content=948&utm_campaign=3&utm_term=109703","Price":99990,"DeliveryAvailable":true,"DeliveryCost":0,"DeliveryDate":"2021-02-23T00:04:00.112593982+03:00"}}

Такое событие занимает 706 байт.

Оптимизация

  1. Для начала я уменьшил ротацию до 7 дней, так как использовалась именно последняя неделя. Здесь стоит отметить, что шаг весьма легкий(в исходном коде изменил 10 на 7), сразу сокращает размер RAM на 30%.

  2. Удалил из хранилища все данные, которые записывались, но не использовались во время чтения, такие как name, url, offerId что сократило еще примерно на 50%.

    Cтало:

    {"EventName":"DELIVERY_CHANGED","DateTime":"2021-02-22T00:04:00.112593982+03:00","OfferId":"109703","OfferFrom":{"Price":99990,"DeliveryAvailable":true,"DeliveryCost":0,"DeliveryDate":"2021-02-24T23:49:00+03:00"},"OfferTo":{"Price":99990,"DeliveryAvailable":true,"DeliveryCost":0,"DeliveryDate":"2021-02-23T00:04:00.112593982+03:00"}}

    Теперь событие занимает 334 байта.

    1. Переделал формат хранение с json в бинарный protobuf.

      Об этом шаге хотелось бы рассказать подробнее

      1. Составил схему хранение данных, в случее с protobuf это proto - файл:

        syntax = "proto3";import "google/protobuf/timestamp.proto";message OfferEvent {  enum EventType {    PRICE_CHANGED = 0;    DELIVERY_CHANGED = 1;    DELIVERY_SWITCHED = 2;    APPEARED = 3;    DISAPPEARED = 4;  }  EventType event_name = 1;  google.protobuf.Timestamp date_time = 2;  string offer_id = 3;  message Offer {    int32 price = 1;    bool delivery_available = 2;    int32 delivery_cost = 3;    google.protobuf.Timestamp  delivery_date = 4;  }  Offer offer_from = 4;  Offer offer_to = 5;} 
        
      2. Исходное сообщение в текстовом protobuf формате будет выглядеть так

        event_name: DELIVERY_CHANGEDdate_time {  seconds: 1613941440}offer_id: "109703"offer_from {  price: 99990  delivery_available: true  delivery_date {    seconds: 1614199740  }}offer_to {  price: 99990  delivery_available: true  delivery_date {    seconds: 1614027840  }}
        
      3. Сообщение в итоговом бинарном protobuf формате будет выглядеть так

        echo 'event_name: DELIVERY_CHANGEDdate_time {  seconds: 1613941440}offer_id: "109703"offer_from {  price: 99990  delivery_available: true  delivery_date {    seconds: 1614199740  }}offer_to {  price: 99990  delivery_available: true  delivery_date {    seconds: 1614027840  }}' | protoc --encode=OfferEvent offerevent.proto | xxd -p | tr -d "\n"0801120608c095cb81061a06313039373033220e08968d061001220608bcf7da81062a0e08968d061001220608c0b8d08106
        

      Теперь событие занимает 50 байт. Это сократило потребление памяти на 85%.

      Бинарное сообщение без proto-схемы можно посмотреть с помощью онлайн-сервиса https://protogen.marcgravell.com/

Итого

Оптимизация места более, чем в 14 раз (50 байт против 706 байт изначальных), то есть на 93%.

Подробнее..

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

14.04.2021 10:21:24 | Автор: admin
image
Привет, Хабр.

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

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

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


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

Существует много открытых фреймворков для решения оптимизационных задач таких как Gekko, Pyomo, Python-mip, а так же различное проприетарное ПО типа IBM ILOG CPLEX Optimization Studio.

План статьи




Задача оптимизации


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

$$display$$\begin{aligned} {\large f(\vec{x}) \rightarrow \underset{\vec{x} \in X}{\min} },\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; \\ X = \left\{\vec{x} \; | \; g_{i}(\vec{x}) \leq 0, \; h_{k}(\vec{x}) = 0, \;\\ i = 1, \ldots, m, \;k=1\ldots,p \right\} \subset R^n.\end{aligned} \;\;\; (1)$$display$$


Т.е. среди всех векторов множества $X$, которое ограничено условиями $g_{i}(\vec{x}) \leq 0$ и $h_{k}(\vec{x}) = 0,$ необходимо найти такой вектор $\vec x^* $, при котором значение $f(\vec{x}^*)$ будет минимальным на всем множестве $X$.
При линейных ограничениях и линейной целевой функции задача (1) относится к классу задач линейного программирования и может быть решена симплекс-методом.

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


Представим себе современный банк, работающий с физическими лицами и продающий им свои основные продукты: кредитные карты, кредиты наличными и т.д. Каждому клиенту банк может предложить один из продуктов $P_i, \; i = 1, \ldots, n$ в одном из доступных для коммуникации каналов $C_{k}, \; k = 1, \ldots, m$ (звонок, смс и т.д.). При этом количество доступных для отправки в неделю/месяц коммуникаций в каждом канале (объем канала) ограничено

$\begin{aligned} &\sum Calls \leq N_1 \\ &\sum Sms \leq N_2 \\ &\sum Email \leq N_3 \\ &\sum Push \leq N_4 \\ \end{aligned} \;\;\;(2)$


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

image

Рис. 1

Теперь, имея на руках в таблице в базе данных для каждого клиента вероятности отклика на отдельные продукты в определенном канале, ограничения на объем коммуникаций (2) и тот факт, что за одну коммуникацию можно предложить клиенту только один продукт, зададимся вопросом, а какой именно продукт и в каком канале лучше всего предложить каждому из доступных для коммуникации клиентов?

image


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

$\begin{cases} p_{11}x_{11} + p_{12}x_{12} + p_{13}x_{13} + p_{21}x_{21} + p_{22}x_{22} + p_{31}x_{31} + p_{32}x_{32} + p_{33}x_{33} \rightarrow \max \\\\ Одному \;клиенту\; не\; более \; одного\; продукта \\ x_{11} + x_{12} + x_{13} \leq 1 \\ x_{21} + x_{22} \leq 1 \\ x_{31} + x_{32} + x_{33} \leq 1 \\ \\ Ограничение \; количества \; звонков \\ x_{12} + x_{21} + x_{31} \leq N_1 \\ \\ Ограничение \; количества \; смс \\ x_{13} + x_{22} + x_{33} \leq N_2 \\\\ Ограничение \; количества \; имейлов\\ x_{11} + x_{32} \leq N_3 \\ \\ x_{ik} \in \left\{0, 1 \right\} \end{cases} \;\;\; (3)$


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

В случае, если целью коммуникаций будет максимизация будущей доходности, то целевую функцию в задаче (3) можно записать в виде

$\begin{aligned}D_{11}p_{11}x_{11} + D_{12}p_{12}x_{12} + D_{13}p_{13}x_{13} &+D_{23}p_{21}x_{21} + D_{22}p_{22}x_{22} +\\+ D_{34}p_{31}x_{31} + D_{32}p_{32}x_{32} + &D_{32}p_{33}x_{33} \rightarrow \max,\end{aligned}\;\;\; (4)$


где $D_{ik}$ доходность от k-го продукта на i-м клиенте. Значения $D_{ik}$ могут быть получены с помощью прогнозных моделей или оценены каким-то другим способом.

Замечания
  1. Описанные выше подходы предполагают, что мы имеем достаточно хорошие прогнозы/оценки для $p_{ik}$ и $D_{ik}.$
  2. Если скоры $p_{ik}$ для различных продуктов получены от разных моделей и при этом они (скоры) плохо согласуются с реальной вероятностью отклика (это можно увидеть, например, по графику как на Рис. 1), то перед оптимизацией их необходимо откалибровать. Про различные способы калибровки можно почитать по ссылке.
  3. Предполагается также, что количество коммуникаций, на которые банк готов потратить средства, меньше, чем количество клиентов, которым банк готов предложить свои продукты. В противном случае оптимизировать будет нечего.


Немного кода


Попробуем решить задачу маркетинговой оптимизации, поставленную в виде (3) с помощью библиотеки MIP, упомянутой выше. Возьмем случайным образом сгенерированный датасет объемом в 6000 строк, в котором содержится 1000 клиентов, каждому из которых можно предложить один из 3-х продуктов в двух каналах SMS и звонок.

Код
import pandas as pdfrom mip import Model, MAXIMIZE, CBC, BINARY, OptimizationStatusframe = pd.read_csv('table_for_optimization.csv')frame.head()


image

Предположим, что у нас есть ограничение на объем коммуникаций: 500 SMS и 200 звонков. Напишем функцию для решения задачи оптимизации.

Код
def optimize(frame: pd.DataFrame, channel_limits: dict) -> list:    """    Возвращает массив оптимальных предложений    """        df = frame.copy()        #создание модели    model = Model(sense=MAXIMIZE, solver_name=CBC)    #вектор бинарных переменных задачи    x = [model.add_var(var_type=BINARY) for i in range(df.shape[0])]    df['x'] = x    #целевая функция    model.objective = sum(df.score * df.x)    #ограничения на количество коммуникаций в каждом канале    for channel in df.channel.unique():        model += (sum(df[df.channel==channel]['x']) <= channel_limits[channel])    #ограничения на количество продуктов для каждого клиента    for client in df.client_id.unique():        model += (sum(df[df['client_id']==client]['x']) <= 1)            status = model.optimize(max_seconds=300)        del df        if status == OptimizationStatus.OPTIMAL or status == OptimizationStatus.FEASIBLE:        return [var.x for var in model.vars]    elif status == OptimizationStatus.NO_SOLUTION_FOUND:        print('No feasible solution found')


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

Код
#объем доступных коммуникаций в каналахCHANNELS_LIMITS = {    'call': 200,    'sms': 500}optimal_decisions = optimize(frame=frame, channel_limits=CHANNELS_LIMITS)frame['optimal_decision'] = optimal_decisions#распределение продуктов в каналахframe[frame['optimal_decision']==1].groupby(['channel', 'product']).\                                    agg({'client_id': 'count'}).\                                    rename(columns={'client_id': 'client_cnt'})


image

Весь код и данные доступны по ссылке.

P.S.


В зависимости от типа прогнозных моделей мы можем располагать не просто средней оценкой вероятности отклика $p_{ik},$ а также иметь распределение этого значения для каждого клиента и продукта. В таком случае задача оптимизации (3) может быть дополнена условием

$\sum (отклик \;с \;вероятностью \geq K ) \geq N. \;\;\; (5)$


Более того, если в нашем распоряжении есть распределение для каждой вероятности $p_{ik}$, то мы можем также решать и обратную задачу: минимизировать количество коммуникаций при условях типа (5) с учетом определенных ограничений, задаваемых бизнесом.

Благодарю коллег из команды GlowByte Advanced Analytics за помощь и консультации при подготовке этой статьи.
Подробнее..

Категории

Последние комментарии

  • Имя: Макс
    24.08.2022 | 11:28
    Я разраб в IT компании, работаю на арбитражную команду. Мы работаем с приламы и сайтами, при работе замечаются постоянные баны и лаги. Пацаны посоветовали сервис по анализу исходного кода,https://app Подробнее..
  • Имя: 9055410337
    20.08.2022 | 17:41
    поможем пишите в телеграм Подробнее..
  • Имя: sabbat
    17.08.2022 | 20:42
    Охренеть.. это просто шикарная статья, феноменально круто. Большое спасибо за разбор! Надеюсь как-нибудь с тобой связаться для обсуждений чего-либо) Подробнее..
  • Имя: Мария
    09.08.2022 | 14:44
    Добрый день. Если обладаете такой информацией, то подскажите, пожалуйста, где можно найти много-много материала по Yggdrasil и его уязвимостях для написания диплома? Благодарю. Подробнее..
© 2006-2024, personeltest.ru