что такое разреженная матрица

Разреженные матрицы: как ученые ускорили машинное обучение на GPU

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

Трудности тренировки крупных нейронных сетей на GPU

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

Чтобы добиться схожего результата на центральном процессоре, придется выстроить инфраструктуру из нескольких кластеров CPU, что очень дорого. Система Google для тренировки нейросетей на CPU стоила порядка 5 млрд долларов. Сегодня ученые из Стэнфорда построили систему с аналогичной вычислительной мощностью на GPU всего за 33 тыс. долларов.

Однако здесь есть трудности: использовать весь потенциал GPU на ресурсоемких задачах не так просто. Для обработки данные должны храниться в памяти GPU, однако её объем невелик, что затрудняет тренировку крупных моделей. Например, модель VGG-16 требует около 14 ГБ, в то время как объем памяти Nvidia Titan X составляет 12 ГБ. И эту карту Nvidia позиционирует как один из самых мощных GPU для глубокого обучения.

Как верно заметил EvilGenius18 в комментариях, 7 декабря компания Nvidia представила новую карту Titan V на архитектуре Volta. Она обладает вычислительной мощностью 110 TFLOPS на задачах глубокого обучения, что в 9 раз больше, чем у предшественницы.

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

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

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

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

Решение от OpenAI

Команда OpenAI разработала программное обеспечение, которое моделирует работу крошечных ядер, способных взаимодействовать с такими матрицами. Ядра опробовали на обучении сетей, анализирующих обзоры на сайтах Amazon и IMDB. Как сообщает команда, уровень ошибок в работе со сводом данных IMDB был снижен с 5,91% до 5,01%.

Ядра реализованы с использованием CUDA, программно-аппаратной архитектуры параллельных вычислений от Nvidia. Но модель OpenAI пока доступна только для TensorFlow. Скотт Грей (Scott Gray), член команды Open AI, сказал, что решение может быть распространено на другие архитектуры, кроме Google TPU2. Компания Nvidia уже знает о работе OpenAI и готова оптимизировать свои системы.

Альтернативные проекты

Концепция разреженных матриц получила свое воплощение в компиляторе с открытым исходным кодом под названием Taco. О проекте, над которым работает команда ученых из Массачусетского технологического института в партнерстве с Adobe Research, стало известно в ноябре. Разработчики искали способ автоматизировать процесс обработки чисел в разреженных матрицах. И использовали для этого тензоры.

О своих разработках в области машинного обучения в декабре отчиталась и компания IBM. Решение ИТ-гиганта — DuHL — предлагает новый метод переноса данных с CPU на GPU. Основная задача технологии — определить, какая информация наиболее важна для алгоритма обучения, и передать её сети в правильном порядке. Исследования показали, что новый подход на основе DuHL в 10 раз быстрее по сравнению с классическим методом последовательной передачи данных между процессорами. Следующая цель компании — предложить DuHL как услугу в облаке.

Но в IBM не первыми придумали переносить GPU-вычисления в облако. Подобные проекты, работающие в том числе по модели IaaS, уже известны. Изначально услугу vGPU предоставляла компания Nvidia. Сейчас этим занимаются и AMD, и Intel.

Об OpenAI

OpenAI — это некоммерческая исследовательская организация, основанная главой Tesla Илоном Маском. Она ставит своей задачей продвижение и развитие искусственного интеллекта на благо человечества. Организация плотно сотрудничает с другими учреждениями и исследователями, предоставляя открытый доступ к своим разработкам.

Источник

Нежное введение в разреженные матрицы для машинного обучения

Дата публикации 2018-03-14

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

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

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

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

После завершения этого урока вы узнаете:

Обзор учебника

Этот урок состоит из 5 частей; они есть:

Разреженная матрица

Разреженные матрицы отличаются от матриц с ненулевыми значениями, которые называются плотными матрицами.

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

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

Ниже приведен пример небольшой 3 x 6 разреженной матрицы.

Пример имеет 13 нулевых значений из 18 элементов в матрице, давая этой матрице показатель разреженности 0,722 или около 72%.

Проблемы с разреженностью

Разреженные матрицы могут вызывать проблемы в отношении сложности пространства и времени.

Космическая сложность

Очень большие матрицы требуют много памяти, а некоторые очень большие матрицы, с которыми мы хотим работать, немногочисленны.

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

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

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

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

Сложность времени

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

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

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

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

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

Разреженные матрицы в машинном обучении

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

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

Данные

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

Три примера включают в себя:

Подготовка данных

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

Три распространенных примера включают в себя:

Области исследования

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

Три примера включают в себя:

Если в языковой модели 100 000 слов, то вектор объектов имеет длину 100 000, но для короткого сообщения электронной почты почти все функции будут иметь нулевое число.

Работа с разреженными матрицами

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

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

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

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

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

Разреженные матрицы в Python

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

Многие функции NumPy и SciPy линейной алгебры, которые работают с массивами NumPy, могут прозрачно работать с разреженными массивами SciPy. Кроме того, библиотеки машинного обучения, использующие структуры данных NumPy, также могут прозрачно работать с разреженными массивами SciPy, такими как scikit-learn для общего машинного обучения и Keras для глубокого обучения.

Плотная матрица, хранящаяся в массиве NumPy, может быть преобразована в разреженную матрицу, используя представление CSR, вызываяcsr_matrix ()функция.

В приведенном ниже примере мы определяем разреженную матрицу 3 x 6 как плотный массив, преобразуем ее в разреженное представление CSR, а затем преобразуем обратно в плотный массив, вызываяtodense ()функция.

При выполнении примера сначала печатается определенный плотный массив, затем представление CSR, а затем восстановленная плотная матрица.

NumPy не предоставляет функцию для расчета разреженности матрицы.

Тем не менее, мы можем легко вычислить его, сначала найдя плотность матрицы и вычтя ее из единицы. Количество ненулевых элементов в массиве NumPy может быть заданоcount_nonzero ()Функция и общее количество элементов в массиве может быть задано свойством размера массива. Таким образом, разреженность массива может быть рассчитана как

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

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

расширения

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

Если вы исследуете какое-либо из этих расширений, я хотел бы знать.

Дальнейшее чтение

Этот раздел предоставляет больше ресурсов по теме, если вы хотите углубиться.

книги

статьи

Резюме

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

В частности, вы узнали:

У вас есть вопросы?
Задайте свои вопросы в комментариях ниже, и я сделаю все возможное, чтобы ответить.

Источник

Работа с разреженными наборами данных в пандах и склеарне

Дата публикации Nov 5, 2019

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

Разреженные наборы данных часто бывают большими, что затрудняет использование стандартных инструментов Python машинного обучения, таких как pandas и sklearn. Нередко памяти среднего локального компьютера недостаточно для хранения или обработки большого набора данных. Даже если памяти достаточно, время обработки может значительно увеличиться.

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

Что такое разреженная матрица?

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

При работе с разреженными матрицами рекомендуется использовать выделенные структуры данных для эффективного хранения и обработки. Мы будем ссылаться на некоторые из доступных структур в Python в следующих разделах.

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

пример

Рассмотрим следующую таблицу с оценками пользователей для фильмов

А теперь представьте, что мы хотим обучить классификатор Факторизационных машин. Факторизационные машины (ФМ) являются основным предиктором, способным хорошо работать в задачах с высокой разреженностью, таких как рекомендательные системы. Согласно оригиналубумаганам нужно преобразовать набор данных в следующий формат:

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

Ниже мы продемонстрируем некоторые способы, которые облегчают преобразование и обработку таких наборов данных в pandas и sklearn.

Набор данных

Мы будем использоватьMovieLens 100Kобщедоступный набор данных, доступныйВот, Учебный файл содержит 100 000 оценок 943 пользователей по 1682 предметам. Для объема этого анализа мы будем игнорироватьотметка времениколонка.

Давайте загрузим данные в кадр данных pandas.

Горячее кодирование

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

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

Теперь давайте применим преобразование и проверим использование памяти преобразованным фреймом данных.

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

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

Совет 1: Используйте разреженные структуры Pandas для хранения разреженных данных

Панды Разреженные Структуры

Pandas предоставляет структуры данных для эффективного хранения разреженных данных. В этих структурах нулевые значения (или любое другое указанное значение) фактически не сохраняются в массиве.

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

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

В нашем примере мы преобразуем закодированные столбцыразрежённый массивs, которые представляют собой 1-й массив, в котором хранятся только ненулевые значения.

Если мы проверимdtypesнового фрейма данных мы видим, что преобразованные столбцы теперь имеют типРазреженный [uint8, 0], Это означает, что нулевые значения не сохраняются, а ненулевые значения сохраняются какuint8, D-тип ненулевых элементов может быть установлен при преобразовании вразрежённый массив

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

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

Совет 2: Используйте разреженный параметр в пандах get_dummies

Можно создать разреженный фрейм данных напрямую, используяредкийпараметр в пандахget_dummies, Этот параметр по умолчаниюЛожь, ЕслиПравдазакодированные столбцы возвращаются какразрежённый массив, Установивразреженный = Trueмы создаем разреженный фрейм данных напрямую, без предварительного плотного фрейма данных в памяти.

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

Давайте продолжим разделять входные и целевые переменные. Мы создадим два набора векторов X, y, используя для сравнения плотные и разреженные фреймы данных.

Сплит X, у

Поезд-тест сплит и обучение модели

Далее мы переходим кsklearnвыполнить разделение на обучающие тесты на наших наборах данных и обучить модель логистической регрессии. Хотя мы использовали Факторизационные машины в качестве эталонной модели для создания нашего обучающего набора, здесь мы будем обучать простую модель логистической регрессии в sklearn только для демонстрации различий в памяти и скорости среди плотных и разреженных наборов данных. Советы, которые мы обсудим в этом примере, можно перенести в реализации Python FM, такие какxlearn,

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

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

Совет 3: Преобразовать в скудную разреженную матрицу

Scipy разреженные матрицы

Пакет Scipy предлагает несколько типов разреженных матриц для эффективного хранения. Sklearn и другие пакеты машинного обучения, такие как imblearn, принимают разреженные матрицы в качестве входных данных. Поэтому при работе с большими разреженными наборами данных настоятельно рекомендуется преобразовать наш фрейм данных Pandas в разреженную матрицу, прежде чем передавать его в sklearn.

В этом примере мы будем использоватьлила такжексоформаты. В документах Scipy вы можете увидеть преимущества и недостатки каждого формата. Для эффективного построения матрицы рекомендуется использовать либоdok_matrixилиlil_matrix, [источник]

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

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

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

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

Источник

Разреженная матрица

При хранении разреженных матриц и манипулировании ими на компьютере полезно и часто необходимо использовать специализированные алгоритмы и структуры данных, которые используют преимущества разреженной структуры матрицы. Специализированные компьютеры были созданы для разреженных матриц [1], поскольку они распространены в области машинного обучения. [2] Операции с использованием стандартных структур и алгоритмов с плотной матрицей являются медленными и неэффективными при применении к большим разреженным матрицам, поскольку обработка и память тратятся на нули. Разреженные данные по своей природе легче сжимаются и, следовательно, требуют значительно меньшего объема памяти.. Некоторыми очень большими разреженными матрицами невозможно манипулировать с помощью стандартных алгоритмов плотных матриц.

СОДЕРЖАНИЕ

Хранение разреженной матрицы [ править ]

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

Форматы можно разделить на две группы:

Словарь ключей (DOK) [ править ]

Список списков (LIL) [ править ]

LIL хранит по одному списку на строку, каждая запись содержит индекс столбца и значение. Обычно эти записи отсортированы по индексу столбца для более быстрого поиска. Это еще один формат, подходящий для построения инкрементальной матрицы. [4]

Список координат (COO) [ править ]

Сжатая разреженная строка (формат CSR, CRS или Йельского университета) [ править ]

Сжатого разреженным строки (КСО) или сжатого хранения строк (СВК) или формат Йельского представляет собой матрицу M с помощью трех (одномерных массивов), которые соответственно содержат ненулевые значения, экстенты строк и столбцов индексов. Он похож на COO, но сжимает индексы строк, отсюда и название. Этот формат обеспечивает быстрый доступ к строке и умножение матрицы на вектор ( M x ). Формат CSR используется по крайней мере с середины 1960-х годов, а первое полное описание появилось в 1967 году [6].

предполагая язык с нулевым индексом.

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

Затем мы берем срезы из V и COL_INDEX, начиная с row_start и заканчивая row_end.

это 4 × 6 матрица (24 записей) с 8 ненулевых элементов, так

Всего хранится 21 запись.

Форматы разреженных матриц Йельского университета (старые и новые) являются экземплярами схемы CSR. Старый формат Йельского университета работает точно так же, как описано выше, с тремя массивами; новый формат объединяет ROW_INDEX и COL_INDEX в единый массив и обрабатывает диагональ матрицы отдельно. [8]

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

Он, вероятно, известен как формат Йельского университета, потому что он был предложен в отчете о пакете разреженных матриц Йельского университета 1977 года, подготовленном факультетом компьютерных наук Йельского университета. [9]

Сжатый разреженный столбец (CSC или CCS) [ править ]

Особая структура [ править ]

Бандиты [ править ]

( Икс Икс Икс ⋅ ⋅ ⋅ ⋅ Икс Икс ⋅ Икс Икс ⋅ ⋅ Икс ⋅ Икс ⋅ Икс ⋅ ⋅ ⋅ Икс ⋅ Икс ⋅ Икс ⋅ ⋅ Икс Икс ⋅ Икс Икс Икс ⋅ ⋅ ⋅ Икс Икс Икс ⋅ ⋅ ⋅ ⋅ ⋅ Икс ⋅ Икс ) <\displaystyle \left(<\beginX&X&X&\cdot &\cdot &\cdot &\cdot &\\X&X&\cdot &X&X&\cdot &\cdot &\\X&\cdot &X&\cdot &X&\cdot &\cdot &\\\cdot &X&\cdot &X&\cdot &X&\cdot &\\\cdot &X&X&\cdot &X&X&X&\\\cdot &\cdot &\cdot &X&X&X&\cdot &\\\cdot &\cdot &\cdot &\cdot &X&\cdot &X&\\\end>\right)>

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

Диагональ [ править ]

Симметричный [ править ]

Диагональ блока [ править ]

Блочно-диагональная матрица состоит из суб-матриц вдоль ее диагональных блоков. Блочно-диагональная матрица A имеет вид

Уменьшение заполнения [ править ]

Решение разреженных матричных уравнений [ править ]

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

Программное обеспечение [ править ]

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

История [ править ]

Термин разреженная матрица, возможно, был придуман Гарри Марковицем, который инициировал некоторую новаторскую работу, но затем покинул эту область. [10]

Источник