Тензорный скетч () — метод уменьшения размерности, используемый в статистике, машинном обучении и алгоритмах обработки больших данных. Он особенно эффективен применительно к векторам, имеющим тензорную структуру. Такой скетч может быть использован для ускорения билинейного объединения в нейронных сетях и является краеугольным камнем во многих алгоритмах числовой линейной алгебрыWoodruff, David P. «Sketching as a Tool for Numerical Linear Algebra.» Theoretical Computer Science 10.1-2 (2014): 1-157..
История Термин тензорный скетч (эскиз) был придуман в 2013 г. и в том же году описан как метод Расмусом Пегом.
Сначала соответствующий метод базировался на использовании быстрого преобразования Фурье, чтобы реализовать быструю свёртку аналогично отсчётному скетчу. В результате дальнейших исследований его обобщили на значительно больший класс методов уменьшения размерности с помощью случайных тензорных проекций.
Тензорные проекции В основе одного из вариантов тензорного скетча лежит применение торцевого произведения матриц, предложенного Слюсарем В. И.Anna Esteve, Eva Boj & Josep Fortiana (2009): Interaction Terms in Distance-Based Regression, Communications in Statistics — Theory and Methods, 38:19, P. 3501 в 1996 г. ().
Торцевое произведение двух матриц с одинаковым количеством строк и имеет вид:
Целесообразность использования этого произведения заключается в его свойстве:
где — поэлементное произведение Адамара.
На этой основе произвольный тензорный скетч вида можно представить как , где матрицы и имеют меньшую размерность, и . Поскольку операции и выполнимы за линейное время и соответственно, переход к представлению позволяет выполнить умножение на векторы с тензорной структурой намного быстрее, чем формируется исходное выражение , а именно за время .
Для тензоров более высокого порядка, например, , экономия будет ещё более значимой.
Подобное преобразование удовлетворяет лемме о малых искажениях исходных данных большой размерности.
См. также Торцевое произведение Лемма о малом искажении
Примечания
Категория:Прикладная математика *