что такое разряженная матрица
Разреженные матрицы: как ученые ускорили машинное обучение на 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 Илоном Маском. Она ставит своей задачей продвижение и развитие искусственного интеллекта на благо человечества. Организация плотно сотрудничает с другими учреждениями и исследователями, предоставляя открытый доступ к своим разработкам.
Что такое разряженная матрица
В предыдущей статье мы говорили о том, как можно представлять разреженные матрицы. Сегодня рассмотрим их создание с примерами кода на Python с помощью библиотеки Scipy. Читайте в этой статье: как можно создать разреженные матрицы в Python, как создаются матрицы формата списка координат (COOrdinate list), сжатого хранения столбцом (Compresed Sparse Row) и строкой (Compresed Sparse Column).
Способы создания разреженных матрицы Scipy
Самый простой формат представления разреженных матриц – это список координат (COOrdinate list, COO). Согласному этому представлению компьютер хранит массивы строк и столбцов ненулевых значений, а также сами ненулевые значения.
Разреженные матрицы Scipy имеют полезные методы для конвертации в плотные ( todense или toarray ), сжатые строкой ( tocsr ) и сжатые столбцом ( tocsc ).
Как создать список координат в Scipy
Создадим разреженную матрицу на основе плотной матрицы из предыдущей статьи. Пример кода на Python того, как создаются разреженные матрицы Scipy:
Как видите, результат тот же, что мы проделывали вручную. Первым элементом вернувшегося массива является индекс строки, вторым – индекс столбца, а справа – ненулевые значения, соответствующим этим индексам.
Мы могли бы также передать массивы индексов строк и столбцов с ненулевыми значениями. Вот так это выглядит в Python:
Преимущества списка координат:
Недостатки списка координат:
Как создать с форматом сжатого хранения строкой (CSS) в Scipy
Сжатое хранение строкой (Compressed Sparse Row, CSR) подразумевает подсчет кумулятивной суммы количества элементов в строке вместо индексов строк.
В Python-библиотеке Scipy для создания разреженных матриц с сжатым хранением строкой используется функция csr_matrix :
Разреженные матрицы данного формата поддерживают арифметические операции: сложение, вычитание, умножение, деление и возведение в степень.
Преимущества сжатого хранения строкой:
Недостатки сжатого хранения строкой:
Как создать с форматом сжатого хранения столбцом (CSС) в Scipy
Сжатое хранение столбцом (Compressed Sparse Column, CSС) подразумевает подсчет кумулятивной суммы количества элементов в столбце. В машинном обучении (machine learning) CSС-матрицы наиболее распространены, так как часто приходится работать с набором признаков, которые как раз и составляют столбцы.
В Python-библиотеке Scipy для создания разреженных матриц с сжатым хранением столбцом используется функция csc_matrix :
Обратите внимание, что последними элементами идет 3, а затем 1, поскольку подсчет происходит по столбам, а столбец с со значением 3 встречается раньше значения 1.
Преимущества и недостатки такие же, как у CSR, но только вместо строк используются столбцы.
Больше подробностей о работе с разреженными матрицами в Python для решения задач Data Science вы узнаете на специализированном курсе по машинному обучению «PYML: Введение в машинное обучение на Python» в лицензированном учебном центре обучения и повышения квалификации разработчиков, менеджеров, архитекторов, инженеров, администраторов, Data Scientist’ов и аналитиков Big Data в Москве.
Нежное введение в разреженные матрицы для машинного обучения
Дата публикации 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.
В частности, вы узнали:
У вас есть вопросы?
Задайте свои вопросы в комментариях ниже, и я сделаю все возможное, чтобы ответить.
СОДЕРЖАНИЕ
Хранение разреженной матрицы
В случае разреженной матрицы существенное сокращение требований к памяти может быть реализовано путем сохранения только ненулевых элементов. В зависимости от количества и распределения ненулевых записей могут использоваться разные структуры данных, что дает огромную экономию памяти по сравнению с базовым подходом. Компромисс заключается в том, что доступ к отдельным элементам становится более сложным, и требуются дополнительные структуры, чтобы иметь возможность однозначно восстановить исходную матрицу.
Форматы можно разделить на две группы:
Словарь ключей (ДОК)
Список списков (LIL)
LIL хранит по одному списку на строку, каждая запись содержит индекс столбца и значение. Обычно эти записи отсортированы по индексу столбца для более быстрого поиска. Это еще один формат, подходящий для построения инкрементальной матрицы.
Список координат (COO)
Сжатая разреженная строка (формат CSR, CRS или Yale)
Сжатого разреженным строки (КСО) или сжатого хранения строк (СВК) или формат Йельского представляет собой матрицу M с помощью трех (одномерных массивов), которые соответственно содержат ненулевые значения, экстенты строк и столбцов индексов. Он похож на COO, но сжимает индексы строк, отсюда и название. Этот формат обеспечивает быстрый доступ к строке и умножение матрицы на вектор ( M x ). Формат CSR используется по крайней мере с середины 1960-х годов, а первое полное описание появилось в 1967 году.
предполагая язык с нулевым индексом.
Чтобы извлечь строку, мы сначала определяем:
Затем мы берем срезы из V и COL_INDEX, начиная с row_start и заканчивая row_end.
это 4 × 6 матрица (24 записей) с 8 ненулевых элементов, так
Всего хранится 21 запись.
Форматы разреженных матриц Йельского университета (старые и новые) являются экземплярами схемы CSR. Старый формат Йельского университета работает точно так же, как описано выше, с тремя массивами; новый формат объединяет ROW_INDEX и COL_INDEX в единый массив и обрабатывает диагональ матрицы отдельно.
Для матриц логической смежности массив данных может быть опущен, поскольку наличие записи в массиве строк достаточно для моделирования двоичного отношения смежности.
Он, вероятно, известен как формат Йельского университета, потому что он был предложен в отчете о пакете разреженных матриц Йельского университета 1977 года, подготовленном факультетом компьютерных наук Йельского университета.
Сжатый разреженный столбец (CSC или CCS)
Специальная структура
Полосатая
Матрицы с достаточно малой верхней и нижней полосой пропускания известны как матрицы полос и часто поддаются более простым алгоритмам, чем общие разреженные матрицы; или иногда можно применять алгоритмы с плотной матрицей и повысить эффективность, просто перебирая сокращенное количество индексов.
Диагональ
Симметричный
Диагональ блока
Блочно-диагональная матрица состоит из суб-матриц вдоль ее диагональных блоков. Блочно-диагональная матрица A имеет вид
Уменьшение заполнения
Решение разреженных матричных уравнений
Для решения разреженных матриц существуют как итерационные, так и прямые методы.
Программное обеспечение
Многие программные библиотеки поддерживают разреженные матрицы и предоставляют решатели для разреженных матричных уравнений. Следующие программы с открытым исходным кодом:
История
Термин разреженная матрица, возможно, был придуман Гарри Марковицем, который инициировал некоторую новаторскую работу, но затем покинул эту область.
Операции над разреженными матрицами
При наличии двух разреженных матриц ( Разреженная матрица и ее представления | Набор 1 (Использование массивов и связанных списков) ) выполняйте такие операции, как сложение, умножение или транспонирование матриц в самой их разреженной форме. Результат должен состоять из трех разреженных матриц, одна из которых получена путем сложения двух входных матриц, одна — путем умножения двух матриц, а другая — путем транспонирования первой матрицы.
Пример: обратите внимание, что другие записи матриц будут равны нулю, так как матрицы редки.
Разреженная матрица, используемая в любом месте программы, сортируется в соответствии со значениями ее строк. Два элемента с одинаковыми значениями строки дополнительно сортируются в соответствии со значениями столбцов.
Теперь, чтобы добавить матрицы, мы просто перемещаемся по обеим матрицам элемент за элементом и вставляем меньший элемент (один с меньшим значением строки и столбца) в результирующую матрицу. Если мы сталкиваемся с элементом с одинаковым значением строки и столбца, мы просто добавляем их значения и вставляем добавленные данные в результирующую матрицу.
Чтобы транспонировать матрицу, мы можем просто изменить значение каждого столбца на значение строки и наоборот, однако в этом случае результирующая матрица не будет отсортирована, как нам требуется. Следовательно, мы изначально определяем количество элементов меньше, чем вставляемый столбец текущего элемента, чтобы получить точный индекс результирующей матрицы, в которую должен быть помещен текущий элемент. Это делается путем поддержания индекса массива [], чье i-е значение указывает на количество элементов в матрице меньше, чем в столбце i.
Для умножения матриц мы сначала вычисляем транспонирование второй матрицы, чтобы упростить наши сравнения и поддерживать отсортированный порядок. Таким образом, результирующая матрица получается путем обхода всей длины обеих матриц и суммирования соответствующих умноженных значений.
Любое значение строки, равное x в первой матрице, и значение строки, равное y во второй матрице (транспонированная), будут влиять на результат [x] [y]. Это получается путем умножения всех таких элементов, имеющих значение col в обеих матрицах, и добавления только тех, у которых строка в первой матрице равна x, а во второй транспонированной матрице — как y, чтобы получить результат [x] [y].
Например: рассмотрим 2 матрицы:
Полученная матрица после умножения будет получена следующим образом:
Ниже приведена реализация вышеуказанного подхода:
// Java-код для выполнения добавления,
// умножаем и переносим на разреженные матрицы
public class sparse_matrix <
// Максимальное количество элементов в матрице
// [] [0] представляет строку
// [] [1] представляет кол
// [] [2] представляет значение
int data[][] = new int [MAX][ 3 ];
// общее количество элементов в матрице
public sparse_matrix( int r, int c)
// инициализируем длину до 0
// вставляем элементы в разреженную матрицу
public void insert( int r, int c, int val)
System.out.println( «Wrong entry» );
// вставляем значение строки
// вставляем значение col
// вставить значение элемента
// увеличиваем количество данных в матрице
public void add(sparse_matrix b)
// если матрицы не имеют одинаковые размеры
System.out.println( «Matrices can’t be added» );
sparse_matrix result = new sparse_matrix(row, col);
// если строка b и столбец меньше
if (data[apos][ 0 ] > b.data[bpos][ 0 ] ||
(data[apos][ 0 ] == b.data[bpos][ 0 ] &&
data[apos][ 1 ] > b.data[bpos][ 1 ]))
// вставляем меньшее значение в результат
// если строка и столбец меньше
else if (data[apos][ 0 ] 0 ] ||
(data[apos][ 0 ] == b.data[bpos][ 0 ] &&
// вставляем меньшее значение в результат
// добавляем значения как row и col одинаковые