Нажмите на синее слово выше, чтобы подписаться
Программа Кремниевой долины Ван
Вчера была новая волна поклонения Джеффу Дину в кругу друзей, «Дело об изученных индексных структурах». Все говорят о том, как машинное обучение может изменить некоторые фундаментальные проблемы в базах данных.
Программная собака вчера также прочитала первые несколько глав статьи и хотела рассказать о своем собственном понимании с точки зрения алгоритма и воздействия.Первые три раздела быстро просматривают содержание статьи, а последние три раздела - это эксперименты и мое личное понимание.
введение
Всякий раз, когда нам нужно быстро получить доступ к большому количеству данных, одной из первых оптимизаций, которая приходит на ум, является создание индексов. Например, когда мы хотим найти все записи в определенном временном диапазоне, мы используем B-деревья; когда мы хотим найти определенное значение ключа, мы используем Hash-Map; когда мы просто ищем, существует ли оно или нет, когда, Вы можете использовать фильтры Блума.
В процессе теоретического обучения мы часто анализируем временную сложность структуры данных в среднем или наихудшем случае и игнорируем форму реальных данных при работе. Например, когда мы знаем, что данные, которые нужно сохранить, равномерно распределены между 1 и 100M, то непосредственное использование самого числа в качестве индекса без построения B-дерева может сократить время выполнения запроса с O(log n) до O( 1) , что снижает сложность пространства с O(n) до O(1). Другими словами, оптимизация индекса для распределения данных может оптимизировать как временную, так и пространственную сложность.
Однако традиционная оптимизация баз данных оптимизируется для общих ситуаций, и для оптимизации конкретных данных требуется много рабочей силы. Поэтому Джефф и др. предложили метод машинного обучения, который лично я считаю самым большим влиянием и нововведением в этой статье.
Связь между B-деревьями и моделями машин
Фактически, само B-Tree также можно рассматривать как модель машинного обучения, предсказывающую свое положение для заданного значения ключа, как показано на следующем рисунке.
Ради эффективности индексации мы обычно не индексируем каждое ключевое слово, а помещаем примерно каждые n ключевых слов на одну и ту же страницу, а затем индексируем первое ключевое слово на странице. Следовательно, мы также можем рассматривать B-дерево как дерево регрессии, которое сопоставляет ключевые слова с интервалом, а двумя концами интервала являются pos-min_err и pos+max_err.
Продолжая аналогию, min_err и max_err здесь являются минимальной и максимальной ошибками модели машинного обучения на обучающих данных. Если мы записываем минимальную ошибку и наихудшую ошибку для каждого ключевого слова, то для любого ключевого слова положение данных может быть предсказано моделью, и если значение ключа существует, его можно искать между минимальной и максимальной ошибками.
Индекс диапазона машинного обучения
Как упоминалось выше, мы можем разработать модель, которая предсказывает, где появиться на основе ключевых показателей. Для обычных запросов диапазона, где все данные отсортированы, на ум приходит простая модель, заключающаяся в прогнозировании кумулятивной функции распределения для данного ключевого слова:p=F(key)*N, где p - прогнозируемое положение,F(key)является кумулятивной функцией распределения прогноза.
Автор упоминает проблемы, с которыми сталкивается простая функция распределения предсказания, которая включает в себя как эффективность самого Tensorflow, так и сложность контроля ошибки функции предсказания. Для преодоления вышеуказанных проблем в документе предлагается несколько схем обучения, наиболее базовыми из которых являются:learning index framework (LIF)иrecursive-model indexes (RMI).
LIF в основном предназначен для оптимизации индекса модели.Для заданного правила модели LIF создает конфигурацию индекса, оптимизирует и автоматически тестирует. Он использует модель нейронной сети, которая поставляется с Tensorflow, для изучения простых функций, таких как функции линейной регрессии. При применении в реальной базе данных LIF генерирует эффективную структуру индекса на основе C++, которая оптимизирует прогнозы модели с точностью до 30 нс.
RMI в основном оптимизирует точность поиска последней мили после получения результатов прогнозирования. Например, попытка предсказать 100 млн позиций ключевых слов с помощью одной модели дает большую минимальную и максимальную ошибку. Но если мы возьмем двухуровневую модель, где модель первого слоя сопоставляет 100 м ключевых слов с 10 000 позиций, а второй уровень сопоставляет 10 000 ключевых слов с 1 позицией, минимальная и максимальная ошибки будут намного ниже.
Как и структура модели, показанная на рисунке выше, модель 1.1 сначала прогнозирует ключевые слова, а затем выбирает выполнение модели 2.1 на основе результатов прогнозирования. Следует также отметить, что такая многоуровневая структура модели не является деревом поиска, и несколько моделей этапа 2 могут указывать на одну и ту же модель этапа 3. Кроме того, на самом низком уровне, чтобы обеспечить контролируемость минимальных и максимальных отклонений, мы также можем использовать B-дерево для завершения окончательного индекса.
Гибридное сквозное обучение, приведенное выше, описывает, как обучать гибридную модель слой за слоем, верхний слой представляет собой двухслойную нейронную сеть ReLU, а нижний слой представляет собой B-дерево.
Такая рекурсивная модель имеет несколько преимуществ: 1. Она может очень хорошо запоминать форму данных. 2. Благодаря многоуровневости нижний уровень может использовать B-дерево или дерево решений для достижения очень высокой эффективности поиска. 3. На разных этапах можно использовать смещения для вызова моделей без поиска, что упрощает выполнение низкоуровневой оптимизации языка программирования.
Мое мнение об эффекте эксперимента
Одним из преимуществ статей, подготовленных командой Google, является то, что экспериментальный процесс очень понятен и убедителен. Они протестировали несколько алгоритмов с разной конфигурацией, в том числе B-деревья разного размера страницы, и алгоритмы машинного обучения 2-го этапа разного размера (следует отметить, что 2-й этап здесь использует не гибридную структуру, а простые модели нейронной сети). ) и более сложные модели машинного обучения.
Автор делит модельное время на модельное время, то есть время, затрачиваемое на поиск модели, и время поиска, которое требуется для извлечения после нахождения соответствующей страницы.
На самом деле здесь можно обсудить много деталей. Во-первых, размер модели B-деревьев с разными размерами страниц обратно пропорционален размеру страницы, 128/16=8, поэтому экономия размера для размера страницы 16 составляет -700%. Хотя последнее время поиска страницы размером 16 очень короткое, поскольку модель относительно глубокая, в дополнение к работе ЦП необходимо учитывать большое время переключения памяти, поэтому время модели очень велико.
По сравнению с модельным временем страницы размером 128, изученный индекс увеличился в среднем более чем в 3 раза. Как ранее предполагалось группой авторов, расчет обеих моделей может быть завершен за очень короткое время. В то же время минимальная и максимальная ошибки модели во втором слое очень хороши в случае средней амортизации, поэтому время поиска в целом не хуже, чем у B-Tree.
С точки зрения структуры, поскольку нам нужно сохранить только несколько моделей размером 10-20 тыс., каждая модель очень проста, поэтому потребление памяти на порядок меньше, чем у дерева поиска, содержащего миллионы узлов.
Использование ИИ для оптимизации фундаментальных проблем
Моя первая реакция после прочтения экспериментальных результатов заключается в том, что оптимизация времени в основном исходит из времени модели, а не времени поиска, а проблема приложения — это индекс диапазона, поэтому можем ли мы преобразовать проблему в задачу более простого алгоритма? проблема с машинным обучением.
Мы можем определить хеш-функцию,h=floor((key-a)/b), нам нужно найти a и b такие, чтобы ключи меньше размера страницы получали одинаковый h. Эта хэш-функция является моделью, которую мы собираемся сделать.
Одной хеш-функции может быть недостаточно, потому что полученный диапазон ключей может быть очень большим, поэтому нам нужно несколько хэшей, которые разбиты на несколько слоев, чтобы попытаться решить эту проблему.
После этих двух шагов я также могу заменить сложную модель поиска B-Tree несколькими простыми моделями Hash. Однако, если подумать, проблема, которую я поднял, решить не так-то просто. Хеш-функция должна получить оптимальные a и b путем перечисления, что требует временной сложности O (n ^ 2), что в действительности невозможно.
Таким образом, искусственный интеллект является хорошим инструментом, помогающим нам искать и оптимизировать ответ в очень большом пространстве. С этой точки зрения индекс является адаптивной функцией с четкой целью, которую мы можем обучить. Это ломает образ мышления, который мы сформировали с точки зрения алгоритмов.Например, при построении бинарного дерева поиска вставка ключевых значений очень строгая.Необходимо настроить структуру, чтобы сохранить баланс дерево, чтобы достичь теоретического оптимального решения, но окончательный результат В результате модель очень сложна.Например, время модели B-Tree, упомянутой выше, составляет более 100 нс.
Чтобы привести еще два примера, имитация отжига использовалась для быстрого нахождения приближенного решения задачи о коммивояжере. Постоянно ищите новый путь P(i+1), а затем выбирайте приемный путь P(i+1) через вероятность имитации отжига и, наконец, остывайте. Повторение шагов возврата на самом деле является процессом, в котором ИИ пытается обновить вектор, а затем снизить скорость обучения.
Горячая AlphaGo Zero сейчас раскручивается, используя нейронную сеть для изучения вероятности выигрыша каждого хода, а затем сокращая пространство поиска. Последняя версия развивает алгоритм, играя с самим собой, чтобы получить более точные прогнозы вероятностей выигрыша, и все они по существу используют ИИ в качестве инструмента, помогающего алгоритму оптимизации сократить пространство поиска.
Эпилог
Это очень интересная статья.Поначалу внимательно изучив ее, я почувствовал, что проблема не так сложна, как сказала команда Джеффа, но после обсуждения с некоторыми учителями у меня появилось новое понимание смысла статьи.
Еще одна интересная идея в статье заключается в том, что алгоритмы «разделяй и властвуй» также могут пересекаться, и это не обязательно верно, что «разделяй и властвуй» необходимо.Разные модели на одном и том же этапе могут соответствовать одной и той же подмодели на следующем уровне Это предположение может уменьшить сложность модели и сделать алгоритм более отказоустойчивым.Прощание с традиционной моделью дерева также является завершающим штрихом.
В целом, документ указывает на некоторые очень практичные идеи, которые легко упускаются из виду большинством ученых-компьютерщиков и которые очень хорошо работают в реальных ситуациях. Однако из-за того, что модель в настоящее время не может быть объяснена, а сложность выходит из-под контроля, она не может заменить традиционный метод на данный момент.
Наконец, со ссылкой на учителя, в этой статье ИИ используется для оптимизации фундаментального строительного блока для изучения практических ограничений теоретических алгоритмов, что, по оценкам, станет тенденцией в будущем. Какие еще фундаментальные строительные блоки можно оптимизировать с помощью ИИ? При каких обстоятельствах оптимизация ИИ и теоретические алгоритмы сойдутся? Я с нетерпением жду.
Добро пожаловать в программу Силиконовой долины Ван
Оригинал статьи, все права защищены.
Пожалуйста, не перепечатывайте без разрешения.
Изображение взято из Интернета, и авторские права принадлежат оригинальному автору.