Как создать автоматический кодировщик с использованием случайных деревьев решений: eForest
Деревья решений - чрезвычайно универсальные структуры. Вы можете использовать их для классификации и регрессии (CART, Random Forests,…), для обнаружения аномалий (Isolation Forests,…) и, как мы увидим, также для построения Auto Encoders и другие конструкции.
Отказ от ответственности: я не придумал эту идею. Этот новый автоматический кодировщик на основе дерева создан Цзи Фэном и Чжи-Хуа Чжоу [1] и называется «eForest». Свои работы они представили на AAAI-18.
Однако я думаю, что в статье не хватает некоторой ясности относительно того, как распаковывать элементы из скрытого пространства, о чем я расскажу в этой статье. Я также дам простое введение обо всех ингредиентах, используемых для создания eForest.
Итак, прежде чем мы начнем, давайте кратко рассмотрим, что такое деревья принятия решений и автокодировщики.
Краткий обзор важных концепций
Деревья решений
Дерево решений - это метод кластеризации набора выборок из n -мерного пространства признаков в разные ячейки. Это делается путем проверки наличия определенных ограничений для n функций образцов.
Возьмите пространство признаков X = ℝ × ℝ × {0, 1} × {A, B, C}, и образцы
(1.7, 4.3, 0, A) , (2.2, 3.6, 1, B), (3.5, 2.6, 0, C) и (4.1, 1.9, 1, A), живущие в пределах X например. Я составил пример дерева решений, чтобы отсортировать эти образцы по четырем ячейкам. Возможно, следующая картина даже говорит сама за себя, даже если вы никогда раньше не слышали о деревьях решений:
В конце концов, четыре образца сортируются по четырем ячейкам. Поскольку одна выборка не может проходить по двум путям одновременно (характеристика не может быть меньше или равна 4 и строго больше 4), каждая выборка сортируется ровно в одну ячейку.
Авто энкодеры
Автокодеры - это в основном алгоритмы сжатия с потерями. Они позволяют выражать данные меньшим количеством битов, что, в свою очередь, экономит память. Это также ускоряет алгоритмы (машинное обучение) с использованием этих сжатых выборок, поскольку меньший размер входных данных обычно приводит к меньшему времени выполнения.
Автокодеры состоят из двух алгоритмов:
- Кодировщик: сжимает данные, удаляя избыточность и шум.
- Декодер: пытается восстановить исходные данные из сжатой формы.
Чтобы быть более точным, кодировщик проецирует образец из n -мерного пространства признаков в его сжатую форму в m -мерном так называемом скрытом пространстве , с m ‹n.
Декодер берет образец из m -мерного скрытого пространства и снова распаковывает его в n -мерное пространство признаков.
Хороший автокодировщик должен уметь
- взять образец x
- сжать его до x ’= e (x)
- и снова распакуйте его до x ’’ = d (x ’) со свойством x≈x’ ’= d (e (x)).
Это означает, что упаковка и распаковка образца x не должны сильно его менять. Конечно, это должно выполняться для любых x пространства функций.
Обычно мы не можем ожидать получения идеальной реконструкции x. Возьмем, к примеру, n = 1 и m = 0 (т.е. скрытое пространство состоит только из одной точки x ’). Два разных образца x₁ и x₂ будут отправлены в одну и ту же точку x ’ в скрытом пространстве любым кодировщиком. Таким образом, в лучшем случае любой декодер может восстановить только x ’ до x₁ или x₂ и, следовательно, получит одно неверное декодирование. Если x ’ распаковывается до некоторого другого x, декодер даже ошибся в обоих сэмплах.
Популярным представителем автокодировщиков является Анализ главных компонентов (PCA), который линейно отображает данные от n на m размеры и обратно, хотя люди обычно используют кодировщик только для уменьшения размера данных.
Пример игрушки: eTree
Давайте теперь посмотрим, как построить автоматический кодировщик из деревьев решений. Я утверждаю, что мы уже видели отображение eForest в скрытое пространство размерности 1 в этой статье! Назовем это eTree.
Кодирование
Вернитесь к изображению примера Дерева решений или позвольте мне сделать это за вас:
Мы видим, что каждая из четырех выборок сортируется в одну из четырех корзин.
Основная идея состоит в том, чтобы использовать номер ячейки, в которую отображается образец, в качестве кодировки.
Итак, (1.7, 4.3, 0, A) и (2.2, 3.6, 1, B) кодируются как 1, (3.5, 2.6, 0, C ) кодируется как 2, а (4.1, 1.9, 1, A) кодируется как 4, или вкратце:
e ((1.7, 4.3, 0 , A)) = e ((2.2, 3.6, 1, B)) = 1, e ((3.5, 2.6, 0, C)) = 2 и
e ((4.1 , 1.9, 1, A)) = 4, где e - кодировщик eTree, который мы только что представили.
Легко, правда?
Проблема начинается, когда мы снова хотим расшифровать это число.
Расшифровка
В [1] авторы вводят правила и так называемые MCR для проведения декодирования . Идея несложная, но сначала мне было трудно понять ее из статьи. Итак, позвольте мне объяснить это по-другому.
Предположим, что мы получили кодировку 1, т.е. есть x из пространства функций с e (x) = 1, где e - кодировщик eTree. Следуя уникальному пути, ведущему в корзину 1, мы подбираем то, что я назову подсказками о вводе x.
Для посадки в бункер 1 требуется
- Подсказка 1: X₁ должно быть меньше или равно 4 и
- Подсказка 2: X₂ больше или равно 3,
т.е. мы знаем, что x выглядит примерно так:
или, чтобы быть более точным, мы можем вывести, что
Затем мы должны выбрать любой элемент из этого набора потенциальных кандидатов и использовать его для декодирования. Мы можем сделать это детерминированным или вероятностным способом, это не имеет значения.
Один из способов, который также используется в [1], - это минимальный выбор. Просто выберите минимум каждого набора, и если набор представляет собой интервал без минимума, выберите его правую границу. Используя это детерминированное правило, мы декодируем 1 в (4, 3, 0, A) (при условии A ‹B‹ C). Другие простые методы включают выбор максимума или среднего значения или просто случайную выборку из набора.
В нашем примере набор потенциальных кандидатов для декодирования 1 довольно велик, поэтому мы можем ожидать, что реконструкция будет довольно плохой. Один из способов противостоять этому - сделать дерево глубже, то есть использовать больше разделений. Чем больше разбиений, тем больше ключей, которые, в свою очередь, генерируют меньшие наборы кандидатов. Давайте воспользуемся еще одним сплитом в нашем игрушечном примере:
Здесь кодировка 1 будет декодирована в одну из
что оставляет меньше места для того, чтобы испортить первую функцию, что дает меньшую ошибку реконструкции. Другие способы улучшить декодирование - это встраивание знаний о пространстве функций, например иногда функции всегда больше нуля или меньше некоторых границ, таких как 1 или 255 (данные изображения), поэтому мы можем удалить границы, которые равны бесконечности или минус бесконечности.
Но создание дерева решений все глубже и глубже не является устойчивым решением, поскольку тогда мы столкнемся с проблемами переобучения, как в задачах регрессии и классификации. Но пока мы используем только одно измерение! Так что мы можем сделать?
eForest
Давайте подключим несколько деревьев решений параллельно для кодирования! Затем каждое дерево дает нам измерение в скрытом пространстве, и номер ячейки каждого дерева является значением функции. Рассмотрим следующий пример с 3 деревьями:
Каждое из трех деревьев решений дает нам одну координату скрытого пространства, 3 в этом примере. В нашем случае каждая скрытая функция может быть 1, 2, 3 или 4. Но также нормально, если в каждом дереве решений будет разное количество ячеек.
Итак, давайте представим, что наш вход x закодирован в (2, 1, 1) в скрытом пространстве, и мы хотим декодировать его сейчас. Нам нужно только снова собрать все улики и собрать их вместе, чтобы создать набор потенциальных кандидатов.
Подсказки:
- Из дерева 1, корзина 2:
- X₁ меньше или равно 4
- X ₂ меньше 3 - Из дерева 2, корзина 1:
- X₁ больше или равно 2
- X ₃ равно 0 - Из дерева 3, корзина 1:
- X₄ равно C
- X ₂ больше 1
Собирая все вместе, мы получаем
Таким образом, минимальное декодирование даст нам d (x) = (2, 1, 0, C).
Это почти все, что нужно для понимания eForests! Чего еще не хватает, так это того, как на самом деле обучить eForest, но это краткий вопрос:
Используйте случайные деревья решений, то есть деревья, которые используют случайные функции и случайные точки отсечения (из разумного диапазона) для разделения.
Так я и составлял свои примеры. Не было задействовано никаких сложных алгоритмов.
Теперь давайте перейдем к некоторым экспериментам, чтобы увидеть, хороши ли они с точки зрения производительности.
Эксперименты
Авторы [1] провели несколько экспериментов, в том числе с кодированием изображений, в которых блистают автокодеры CNN. Я напрямую вставлю результаты, таблицы и изображения из [1].
Вы можете найти код, использованный для экспериментов, на GitHub.
Наборы данных представляют собой классический MNIST с элементами 28x28x1 = 784 (1 цветовой канал) и CIFAR-10 с элементами 32x32x3 = 3072 (3 цветовых канала).
Об автокодировщиках, использованных в экспериментах
MLP - это нормальный автокодировщик, использующий несколько линейных слоев. Точные спецификации можно взять из [1], но MLP₁ использует скрытое пространство размером 500 и MLP₂ 1000.
CNN-AE - это сверточный автокодировщик, то есть он использует свертки внутри . Это следует этой спецификации. SWW-AE - это более изящный CNN-AE.
eForestˢ₅₀₀ - это eForest, также использующий этикетки с образцами, которые мы здесь не рассматривали. Он сжимает входные данные до 500 объектов (индекс 1000 сжимает их до 1000 измерений).
Наконец, eForestᵘ₅₀₀ - это eForest, о котором говорилось в этой статье. Номер индекса снова указывает размер скрытого пространства.
Ошибки реконструкции
Результаты выглядят многообещающими! Ошибки восстановления для наборов данных MNISt и CIFAR-10 довольно низкие. От 1]:
Но нужно провести дальнейшие эксперименты, чтобы проверить, переоснащены ли eForests или нет. По крайней мере, авторы повторно использовали модель и получили хорошие результаты, что является хорошим показателем того, что eForest хорошо обобщает и не просто выучил обучающие образцы наизусть. Повторное использование модели означает обучение модели на одной обучающей выборке и ее оценку на другой обучающей выборке.
Я просто не понимаю, почему авторы использовали скрытое пространство размерности 1000 для набора данных MNIST, когда исходные данные имеют размерность только 28 * 28 = 784. На мой взгляд, использование 500 измерений было бы более значимым. Но даже если мы используем эту искусственную настройку: eForest работает лучше, чем другие методы, а neark обеспечивает сжатие без потерь, чего я также ожидал.
Эффективность вычислений
Время обучения невероятно мало по сравнению с другими методами. Однако кодирование и декодирование занимают больше времени, что, по мнению авторов, все же оставляет место для оптимизации. От 1]:
Моя реализация Proof-of-Concept
Поскольку алгоритм довольно простой, я попробовал реализовать его сам. Мне даже не пришлось начинать с нуля, поскольку scikit-learn своего рода уже идет в комплекте с кодировщиком!
Класс RandomTreesEmbedding также создает множество случайных деревьев решений и кодирует входные данные x в зависимости от корзины, в которую они попадают. Однако они используют двоичное кодирование, которое увеличивает размер скрытого пространства. Используя мой пример с тремя деревьями и 4 ячейками на дерево, кодировка будет (0, 1, 0, 0 | 1, 0, 0, 0 | 1, 0, 0, 0) вместо (2, 1, 1), т.е. скрытое пространство будет иметь размер двенадцать вместо трех. Но преобразовать двоичное представление в одно число для каждого дерева легко, если вы знаете количество листьев на дереве. К счастью, scikit-learn помог нам здесь и предоставляет метод для этого.
Таким образом, реализовать часть кодирования просто! Вы также можете увидеть это с помощью shortencodemethod в моем коде. Это просто
output = self.random_trees_embedding.transform(X)
indices = []
start = 0
for estimator in self.random_trees_embedding.estimators_:
n_leaves = estimator.get_n_leaves()
indices.append(output[:, start:start + n_leaves].argmax(axis=1))
start = start + n_leaves
return np.array(indices).transpose()
Декодирование заняло у меня немного больше времени, и это также неэффективно, как я это сделал, пожалуйста, потерпите меня! : D Мне просто нужно было быстрое подтверждение концепции.
Вы можете найти мой код здесь. Пожалуйста, не стесняйтесь его улучшать!
Мои графические результаты:
Я думаю, что реконструкции выглядят нормально, так что, вероятно, моя расшифровка работает. Но, пожалуйста, просмотрите код, прежде чем использовать его для чего-нибудь продуктивного.
А если вам нужна реальная сделка, перейдите к официальному клону реализации на GitHub и поработайте с этим. Но будьте готовы создать виртуальную среду и вручную исправить некоторые файлы scikit-learn.
Заключение
Мы видели, как построить автоматический кодировщик с деревьями решений. Это автоматический кодировщик с уникальным, но понятным дизайном, который можно очень быстро обучить. Более того, точность восстановления может конкурировать с хорошо зарекомендовавшими себя сверточными автокодировщиками.
С другой стороны, скорость кодирования и декодирования все еще низкая, и eForest необходимо протестировать на реальных наборах данных в дикой природе. Может быть, именно вы напишете об этом статью. :)
использованная литература
[1] Дж. Фэн и З. Чжоу, AutoEncoder by Forest (2017), Тридцать вторая конференция AAAI по искусственному интеллекту.
Надеюсь, что сегодня вы узнали что-то новое, интересное и полезное. Спасибо за прочтение!
В качестве последнего пункта, если вы
- хотите помочь мне написать больше о машинном обучении и
- все равно планируете получить подписку Medium
почему бы не сделать это по этой ссылке? Это мне очень поможет! 😊
Чтобы быть прозрачным, цена для вас не меняется, но около половины стоимости подписки идет непосредственно мне.
Большое спасибо, если вы думаете поддержать меня!
Если возникнут вопросы, напишите мне в LinkedIn!
