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

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

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

Но что произойдет, если у нас нет доступа к полной матрице данных? Например, мы можем захотеть сжимать данные локально на каждом из миллиарда граничных устройств, а затем агрегировать их в облаке. Это не просто крупномасштабная проблема электронной коммерции, ту же проблему можно найти и в условиях большой науки. Массив квадратных километров, например, будет производить необработанные данные со скоростью 157 ТБ / с. Собрать все данные в одном месте кажется совершенно непрактичным: если предположить, что вы храните эти данные на DVD-дисках, без футляра для хранения, через полтора часа вы получите коллекцию DVD-дисков олимпийского размера!

Чтобы решить эту проблему, можем ли мы построить матрицу набросков, в которой нам нужно только подмножество данных за раз? Ракшит ответил утвердительно! Это можно сделать, применив матрицу блочно-диагонального эскиза.

Хотя это кажется логичным решением, нужно ли доплачивать? Очевидно нет!

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

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

Бумага Rakshith показывает, что мы можем выбирать размер каждого блока в соответствии с термином согласованности, который может принимать значения от (1 / # блоков) до 1.

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

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

Интересно, что границы, полученные для такого выбора размеров эскиза, совпадают с современными границами для неблокируемого эскиза, красиво замыкая круг!

В конце презентации Ракшит указал на две другие свои работы, которые вы можете проверить, на Децентрализованное создание эскизов матриц низкого ранга и Создание графических эскизов для графовых нейронных сетей. Если тема пробудила у вас любопытство по поводу техники рисования, этот обзор от Дэвида Вудраффа может развлечь вас на некоторое время. Наконец, в LightOn мы вычисляем плотные случайные проекции буквально со скоростью света. Если вы хотите опробовать эти алгоритмы или новую идею, вы можете зарегистрироваться в LightOn Cloud или подать заявку в LightOn Cloud for Research Program!

Ссылка

Локализованное построение эскизов для матричного умножения и гребневой регрессии Ракшита С. Шриниваса, Марка А. Давенпорта, Джастина Ромберга, ArXiV 2003.09097

О нас

LightOn - компания, занимающаяся аппаратным обеспечением, которая разрабатывает новые оптические процессоры, которые значительно ускоряют вычисления с помощью машинного обучения. Процессоры LightOn открывают новые горизонты в областях вычислений и инженерии, которые сталкиваются с вычислительными ограничениями. Заинтересованы в ускорении вычислений? Попробуйте наше решение на LightOn Cloud! 🌈

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

Автор

Якопо Поли, ведущий инженер по машинному обучению в LightOn AI Research.

Благодарности

Мы хотели бы поблагодарить Виктуар Луи за большую часть усилий по организации встречи.