что такое разряженная матрица
Что такое разряженная матрица
В предыдущей статье мы говорили о том, как можно представлять разреженные матрицы. Сегодня рассмотрим их создание с примерами кода на 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 в Москве.
Разреженные матрицы: как ученые ускорили машинное обучение на 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.
В частности, вы узнали:
У вас есть вопросы?
Задайте свои вопросы в комментариях ниже, и я сделаю все возможное, чтобы ответить.
Этап № 6
Цель работы – реализовать алгоритмы обработки разреженных матриц, сравнить эти алгоритмы со стандартными алгоритмами обработки матриц.
Краткие теоретические сведения
В виде матриц достаточно широко представляется информация во многих областях человеческой жизнедеятельности. Матричные задачи часто используются при решении разреженных линейных алгебраических уравнений; разреженных обычных и обобщенных спектральных задач, при этом матрицы могут быть достаточно большие (больше 10
элементов), а число ненулевых элементов при матрице порядка n может выражаться как n
, где g Алгоритмы обработки разреженных матриц предусматривают действия только с ненулевыми элементами и, таким образом, количество операций будет пропорционально количеству ненулевых элементов.
Существуют различные методы хранения элементов матрицы в памяти.
Например, линейный связный список, т.е. последовательность ячеек, связанных в определенном порядке. Каждая ячейка списка содержит элемент списка и указатель на положение следующей ячейки. Можно хранить матрицу, используя кольцевой связный список, двунаправленные стеки и очереди. Существует диагональная схема хранения симметричных матриц, а также связные схемы разреженного хранения. Связная схема хранения матриц, предложенная Кнутом, предлагает хранить в массиве (например, в AN) в произвольном порядке сами элементы, индексы строк и столбцов соответствующих элементов (например, в массивах I и J), номер (из массива AN) следующего ненулевого элемента, расположенного в матрице по строке (NR) и по столбцу (NC), а также номера элементов, с которых начинается строка (указатели для входа в строку – JR) и номера элементов, с которых начинается столбец (указатели для входа в столбец – JC). Данная схема хранения избыточна, но позволяет легко осуществлять любые операции с элементами матрицы.
Наиболее широко используемая схема хранения разреженных матриц – это схема, предложенная Чангом и Густавсоном, называемая: «разреженный строчный формат». Эта схема предъявляет минимальные требования к памяти и очень удобна при выполнении операций сложения, умножения матриц, перестановок строк и столбцов, транспонирования, решения систем линейных уравнений, при хранении коэффициентов в разреженных матрицах и т.п.
В этом случае значения ненулевых элементов хранятся в массиве AN, соответствующие им столбцовые индексы – в массиве JA. Кроме того, используется массив указателей, например IA, отмечающих позиции AN и JA, с которых начинаются описание очередной строки. Дополнительная компонента в IA содержит указатель первой свободной позиции в JA и AN.
Разреженный вектор – это разреженная матрица-строка или матрица-столбец, поэтому рассмотрим скалярное умножение разреженных векторов (как частный случай работы с матрицей) с использованием так называемого расширенного массива указателей IP. Например, есть два разреженных вектора a и b размером N. Значения векторов приведены в таблице.
Разряженная матрица и двусвязный список
Здравствуйте всем. Есть такая задачка.
Написать программу, которая с помощью самостоятельно созданной структуры данных двусвязный список работает с разреженной матрицей. Необходимо для заданной разреженной матрицы A выполнить ее транспонирование, то есть получить матрицу В=А^T. Элементы матрицы А представляют собой целые числа. Разреженная матрица задаётся во входном файле в виде списка триплетов (номер строки, номер столбца, значение элемента). Программа считывает входные данные из файла и сохраняет список триплетов матрицы А в виде списка с двумя связями. При этом список триплетов в списке с двумя связями хранится упорядоченно (сначала по первому индексу, потом по второму). Программа должна создать новый список с двумя связями, сформировать в нем список триплетов для матрицы В=А^T и записать элементы этого списка в файл.
Входные данные: список триплетов исходной матрицы А, который хранится в текстовом файле (формат хранения определяется разработчиком).
Выходные данные: список триплетов транспонированной матрицы, который должен быть записан в конец файла с входными данными. Список триплетов транспонированной матрицы быть отделен каким-либо способом от исходных данных, то есть при просмотре файла должно быть понятно, что является выходными данными.
Важно: Список триплетов, представляющий собой входные данные, хранится в файле неупорядоченно. Упорядоченность списка триплетов, хранящихся в памяти компьютера, достигается посредством вставки очередного триплета в список с двумя связями с учетом порядка следования триплетов.
Подскажите как лучше организовать двусвязный список для данной задачи! Можно на примере ООП, но можно и без этого.
Вот пока то, что есть, не совсем понимаю, как написать правильный конструктор и copyconstructor. Правильно ли написан метод добавления элемента в список?
Разряженная матрица
Экономное использование памяти предусматривает, что для тех элементов матрицы, в которых наверняка.
Разряженная Матрица
Разряженная Матрица общего вида.Найти сумму её элементов
Как создать Разряженная Ленточная матрица
Как создать разряженную ленточную матрицу, так что бы мы вводили только Например 1, 2, 3, и.