Применение глубокого обучения с подкреплением при сжатии данных временных рядов - документ ICDE 2020

Автор Xinyang

Признание вовлеченных людей

Во время написания этой статьи Яньцин Пэн, Фейдао, Ваншэн, Лейю, Майцзюнь и Юэси внесли большой вклад. Здесь я хочу выразить особую признательность Фейдао за руководство и помощь. Я также хочу выразить благодарность за поддержку Ксили и Деши за помощь и поддержку.

Предисловие

«Между коровьими костями есть щели, а нож очень тонкий. Следовательно, ножом легко разрезать кости ». - По материалам Пао Дин Цзе Ню.

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

С применением и популяризацией мобильного Интернета, Интернета вещей (IoT) и 5G мы вступаем в эпоху цифровой экономики. Полученные массивные данные станут объективным существованием и будут играть все более важную роль в будущем. Данные временных рядов - важная часть массивных данных. Помимо интеллектуального анализа данных, анализа и прогнозирования, важной темой обсуждения является также эффективное сжатие данных для хранения. Сегодня мы также живем в эпоху искусственного интеллекта (ИИ), когда глубокое обучение широко используется. Как мы можем использовать его в других приложениях? Суть глубокого обучения - принимать решения. Когда мы используем глубокое обучение для решения конкретной проблемы, важно найти точку прорыва и создать подходящую модель. Исходя из этого, мы можем отсортировать данные, оптимизировать потери и, наконец, решить проблему. В прошлом мы провели некоторые исследования в области сжатия данных с использованием глубокого обучения с подкреплением и нашли некоторые результаты. Мы опубликовали документ под названием Двухуровневое сжатие данных с использованием машинного обучения в базе данных временных рядов в ICDE 2020 Research Track и сделали устный отчет. Эта статья знакомит с нашими исследованиями и исследованиями, и мы надеемся, что вы найдете их полезными для других сценариев, по крайней мере, для сжатия других данных.

1. Фон

1.1 Данные временных рядов

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

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

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

1.2 Обучение с подкреплением

В зависимости от того, содержат ли образцы GroundTruth, машинное обучение подразделяется на обучение с учителем, обучение без учителя и обучение с подкреплением. Как следует из названия, обучение с подкреплением требует непрерывного обучения, которое не требует заземления. В реальном мире GroundTruth также часто недоступен. Например, человеческое познание - это в основном процесс непрерывного обучения в итеративном режиме. В этом смысле обучение с подкреплением - это процесс и метод, который больше подходит или популярен для решения реальных проблем. Итак, многие люди говорят, что если глубокое обучение постепенно станет основным инструментом для решения конкретных проблем, таких как C, Python и Java, обучение с подкреплением станет основным инструментом глубокого обучения.

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

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

Обучение с подкреплением можно разделить на следующие типы:

• Deep Q Network (DQN): этот тип больше соответствует интуитивной логике чувств людей. Он обучает сеть, которая используется для оценки Q-значения и может предоставлять вознаграждения, соответствующие действиям на основе любого состояния. Затем он выбирает действие с наибольшей наградой. Во время обучения DQN оценивает результаты «оценочного Q-значения» и «реального Q-значения» для обратного распространения. Таким образом, сеть может более точно оценить значение Q.
• Градиент политики: этот тип более сквозной. Он обучает сеть прямому выводу финального действия для любого состояния. DQN требует, чтобы Q-значения непрерывных состояний также были непрерывными, что не относится к таким случаям, как игра в шахматы. Policy Gradient игнорирует внутренний процесс и напрямую выводит действия, что является более универсальным. Однако политический градиент затрудняет оценку и сближение. Общий процесс обучения таков: Градиент политики выполняет несколько случайных действий для состояния и оценивает результаты всех действий для обратного распространения. Наконец, сеть выводит лучшее действие.
• Актер-критик: Этот тип сочетает в себе первые два типа для дополнения. С одной стороны, он использует сеть градиентов политики для вывода действий для любого состояния. С другой стороны, он использует DQN для количественной оценки действий, выводимых градиентом политики, и использует результат для направления обновления градиента политики. Как следует из названия, «Актер-критик» демонстрирует отношения, аналогичные отношениям между актером и критиком. Во время обучения сеть Actor (Policy Gradient) и сеть Critic (DQN) обучаются одновременно. При обучении «Актера» нужно только следовать указаниям «Критика». У Actor-Critic есть много вариантов, и он также является основной ветвью текущих теоретических исследований DRL.

2. Сжатие данных временных рядов

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

• Мгновенно сжимает целые числа или строки. Он использует прогнозирование на большие расстояния, кодирование длин серий (RLE) и имеет множество приложений, включая InfuxDB.
• Simple8b: выполняет дельта-обработку данных. Если все дельты в результирующих deltaValues ​​совпадают, к ним применяется кодировка RLE. Если дельты разные, числа от 1 до 240 (биты каждого числа в соответствии с кодовой таблицей) упаковываются в данные в блоке 8 байтов на основе кодовой таблицы, содержащей 16 записей. Simple8b имеет множество приложений, в том числе InfuxDB.
• Планировщик сжатия: знакомит с некоторыми общими инструментами сжатия, такими как масштаб, дельта, словарь, алгоритм Хаффмана, длина цикла и исправленная константа. Затем предлагается статическое или динамическое объединение этих инструментов для сжатия данных. Идея нова, но ее эффективность не доказана.
• ModelarDB: ориентирован на сжатие с потерями на основе допустимой потери, указанной пользователем. Основная идея состоит в том, чтобы поддерживать небольшой бафф и определять, соответствуют ли данные определенному шаблону (прямая аппроксимация наклона). Если это не удается, переключите шаблон и начните новый бафф. ModelarDB применяется к IoT-полю с потерями.
• Sprintz: также применяется к Интернету вещей и ориентирован на обработку 8- или 16-разрядных целых чисел. Он использует масштабирование для выполнения прогнозирования и использует RLC для кодирования результирующих дельт и упаковки на уровне битов.
• MO: похож на Gorilla, но исключает упаковку битов. В этом методе все операции с данными выравниваются по байтам, что снижает степень сжатия, но улучшает производительность обработки.
• Gorilla: - это алгоритм сжатия дивана в высокопроизводительной системе реального времени Facebook. Он используется для сжатия без потерь и широко используется в различных областях, таких как Интернет вещей и облачные сервисы. Gorilla вводит дельта-дельта для обработки временных меток, запускает xor для преобразования данных, а затем использует Хаффмана для кодирования и битовой упаковки. На следующем рисунке показана схематическая диаграмма Gorilla.

Также существует множество связанных алгоритмов сжатия. В основном,

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

3. Двухэтапные алгоритмы сжатия, основанные на глубоком обучении.

3.1 Характеристики сжатия данных временных рядов

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

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

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

• Временная корреляция. Данные временных рядов сильно коррелированы по времени, а соответствующие данные почти непрерывны. Интервал выборки часто составляет 1 секунду или 100 миллисекунд.
• Разнообразие шаблонов. Как показано на предыдущем рисунке, шаблоны и характеристики сильно различаются.
• Масштабность данных: массивные данные необходимо обрабатывать каждый день, каждый час и каждую секунду. Общий объем данных, обрабатываемых каждый день, составляет около 10 ПБ. Следовательно, алгоритмы сжатия должны быть высокоэффективными и иметь высокую пропускную способность.

3.2 Основные концепции новых алгоритмов

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

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

Затем мы можем определить следующие три основных примитива дифференциального кодирования. Все они также могут быть расширены.)

Затем следует ли отсортировать и объединить два предыдущих инструмента для сжатия? Это возможно, но эффект плохой, потому что доля затрат на выбор шаблона и связанных с ним параметров слишком высока. На управляющую информацию в 2 байта (примитивный выбор + примитивный параметр) приходится 25% данных, которые должны быть выражены в 8 байтах.

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

3.3 Структура двухступенчатого сжатия: AMMMO

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

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

3.4 Шаблоны на основе правил и алгоритмы выбора пространства

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

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

4. Глубокое обучение с подкреплением

4.1 Моделирование проблемы

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

Тогда какую сеть мы можем использовать? Поскольку основные идентифицированные отношения включают дельта / xor, сдвиг и битовую маску, сверточная нейронная сеть (CNN) не подходит, а многослойный перцептрон с полным соединением (MLP) является правильным. Примите во внимание все моменты на временной шкале. Всего за час можно получить 3600 x 8B точек, что является огромным числом. Рассматривая аналогичные сегменты на одной временной шкале, мы можем рассматривать 32 точки как базовую единицу обработки.

Затем, как мы можем создавать обучающие образцы и как определять метки для образцов?

Мы ввели обучение с подкреплением вместо обучения с учителем для обучения по следующим причинам.

• Создать меченые сэмплы сложно: размер 32 сэмплов равен 256 байтам. Теоретически существует 256²⁵⁶ возможностей для сэмплов. Для каждого из этих образцов нам нужно просмотреть 300 тысяч возможностей, чтобы найти лучший. В результате нам приходится иметь дело с огромными рабочими нагрузками по созданию и отбору образцов и созданию этикеток.
• Это не обычная проблема с одним классом. Когда сдают образец, не бывает только одного лучшего результата. Вместо этого многие варианты могут достичь того же эффекта сжатия. Соответственно, обучение N классов (N неизвестно) может быть сложнее.
• Чтобы решить эту проблему, нам нужен автоматический метод. Выбор параметров, таких как инструмент сжатия, вероятно, будет расширен. В таком случае необходимо заново создать всю обучающую выборку. Следовательно, в этом случае требуется автоматический метод.

Затем, какой тип обучения с подкреплением мы должны выбрать; DQN, политический градиент или актер-критик? Как мы проанализировали ранее, DQN не применяется к случаю, когда награды и действия прерываются. Параметры, такие как majorMode 0 и 1, приводят к совершенно разным результатам. Следовательно, DQN не применяется. Кроме того, нелегко оценить проблемы сжатия и сеть не сложна. Следовательно, Актер-Критик не требуется. Итак, мы выбрали Градиент Политики.

Распространенная потеря градиента политики - это использование медленно повышающейся базовой линии в качестве метрики, показывающей, является ли текущее действие разумным. Для этого образца Policy Gradient не подходит, что приводит к плохим результатам. Это связано с тем, что в образце слишком много (256²⁵⁶) теоретических состояний блока. Таким образом, мы спроектировали убыток.

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

4.2 Сетевая структура обучения с глубоким подкреплением

На следующем рисунке показана вся сетевая структура.

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

fn (copi) описывает эффект сжатия, который указывает на положительную обратную связь, если она выше среднего значения N блоков. Hcs (copi) указывает кросс-энтропию; чем выше вероятность получить высокий балл, тем надежнее и лучше результат, и наоборот. H (cop) указывает кросс-энтропию, которая используется в качестве коэффициента нормализации, чтобы избежать лечения сети и выполнить сходимость для достижения локального оптимума.

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

5. Данные результатов

5.1 Экспериментальный план

Мы получили тестовые данные, случайным образом выбрав в общей сложности 28 временных шкал из 2 больших сценариев, Alibaba Cloud IoT и сервера. Мы также выбрали набор данных UCR, который является наиболее распространенным в области анализа и интеллектуального анализа данных временных рядов. Основная информация:

Мы выбрали Gorilla, MO и Snappy в качестве алгоритмов сравнения. Поскольку AMMMO представляет собой структуру двухэтапного алгоритма сжатия, и на первом этапе для выбора параметров могут использоваться различные алгоритмы, мы выбрали Lazy (просто задав некоторые универсальные параметры), rnd1000Avg (получение среднего эффекта от 1000 случайных выборок), Analyze (с использованием ручной код) и ML (алгоритм глубокого обучения с подкреплением).

5.2 Сравнение эффектов сжатия

Что касается общей степени сжатия, двухэтапная адаптивная многомодовая степень сжатия AMMMO значительно улучшила эффект сжатия по сравнению с эффектами Gorila и MO, при этом средняя степень сжатия увеличивается примерно на 50%.

Тогда как насчет производительности ML? На следующем рисунке сравнивается влияние сжатия на тестовом наборе B с точки зрения машинного обучения. В целом ML немного лучше, чем Analyze, и намного лучше, чем rnd1000Avg.

5.3 Эффективность работы

Исходя из конструкторской концепции МО, АМММО убрала бит-набивку. Это позволяет AMMMO работать на высоких скоростях на процессорах. Это также делает его идеальным для платформ параллельных вычислений, таких как графические процессоры. Кроме того, AMMMO делится на два этапа. Первый этап имеет худшую производительность, но в большинстве случаев глобальные параметры сжатия можно использовать повторно. Например, данные определенного устройства за последние два дня можно использовать повторно. На следующем рисунке показано общее сравнение производительности. Экспериментальная среда - «Intel CPU 8163 + Nvidia GPU P100», а код AMMMO - P100.

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

5.4 Эффект от обучения алгоритму

Сеть, обученная методом глубокого обучения с подкреплением, дала хороший конечный эффект. Итак, узнал ли он содержательный контент? В следующей таблице сравнивается производительность трех алгоритмов на нескольких наборах тестов. Мы можем видеть, что выбор параметров ML аналогичен таковому в Analyze и RandomBest, особенно в выборе байтового смещения и majorMode.

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

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

Мнения, выраженные здесь, предназначены только для справки и не обязательно отражают официальные взгляды Alibaba Cloud.

Первоисточник: