Тензорный эскиз

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

Математическое определение

Математически матрица уменьшения размерности или эскиза представляет собой матрицу $M\in \mathbb {R} ^{k\times d}$, где $k<d$, такой, что для любого вектора $x\in \mathbb {R} ^{d}$

$|\|Mx\|_{2}-\|x\|_{2}|<\varepsilon \|x\|_{2}$

с высокой вероятностью. Другими словами, $M$ сохраняет норму векторов с точностью до небольшой ошибки.

Тензорный эскиз обладает дополнительным свойством: если $x=y\otimes z$ для некоторых векторов $y\in \mathbb {R} ^{d_{1}},z\in \mathbb {R} ^{d_{2}}$ такой, что $d_{1}d_{2}=d$, преобразование $M(y\otimes z)$ можно вычислить более эффективно. Здесь $\otimes$ обозначает произведение Кронекера , а не внешнее произведение , хотя они связаны сглаживанием .

Ускорение достигается предварительной перезаписью $M(y\otimes z)=M'y\circ M''z$, где $\circ$ обозначает поэлементное ( Адамара ) произведение. Каждый из $M'y$ и $M''z$ можно вычислить во времени $O(kd_{1})$ и $O(kd_{2})$, соответственно; включая произведение Адамара, дает общее время $O(d_{1}d_{2}+kd_{1}+kd_{2})$. В большинстве случаев использования этот метод значительно быстрее, чем полный $M(y\otimes z)$ требующий $O(kd)=O(kd_{1}d_{2})$ время.

Для тензоров более высокого порядка, таких как $x=y\otimes z\otimes t$, экономия еще более впечатляющая.

История

Термин «тензорный эскиз» был придуман в 2013 году. описание техники Расмуса Пага с того же года. Первоначально предполагалось использовать быстрое преобразование Фурье для быстрой свертки эскизов подсчета . Более поздние исследовательские работы обобщили его на гораздо более широкий класс уменьшений размерности с помощью случайных вложений тензора.

Тензорные случайные вложения были представлены в 2010 году в статье на дифференциальную конфиденциальность и впервые были проанализированы Rudelson et al. в 2012 году в условиях редкого восстановления.

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

Тензорные случайные проекции

Произведение граневого расщепления определяется как тензорное произведение строк (предложено В. Слюсарем в 1996 году для радаров и цифровых антенных решеток ). Более прямо, пусть $\mathbf {C} \in \mathbb {R} ^{3\times 3}$ и $\mathbf {D} \in \mathbb {R} ^{3\times 3}$ быть две матрицы. Тогда продукт, расщепляющий лицо $\mathbf {C} \bullet \mathbf {D}$ является $\mathbf {C} \bullet \mathbf {D} =\left[{\begin{array}{c }\mathbf {C} _{1}\otimes \mathbf {D} _{1}\\\hline \mathbf {C} _{2}\otimes \mathbf {D} _{2}\\\hline \mathbf {C} _{3}\otimes \mathbf {D} _{3}\\\end{array}}\right]=\left[{\begin{array}{c c c c c c c c c }\mathbf {C} _{1,1}\mathbf {D} _{1,1}&\mathbf {C} _{1,1}\mathbf {D} _{1,2}&\mathbf {C} _{1,1}\mathbf {D} _{1,3}&\mathbf {C} _{1,2}\mathbf {D} _{1,1}&\mathbf {C} _{1,2}\mathbf {D} _{1,2}&\mathbf {C} _{1,2}\mathbf {D} _{1,3}&\mathbf {C} _{1,3}\mathbf {D} _{1,1}&\mathbf {C} _{1,3}\mathbf {D} _{1,2}&\mathbf {C} _{1,3}\mathbf {D} _{1,3}\\\hline \mathbf {C} _{2,1}\mathbf {D} _{2,1}&\mathbf {C} _{2,1}\mathbf {D} _{2,2}&\mathbf {C} _{2,1}\mathbf {D} _{2,3}&\mathbf {C} _{2,2}\mathbf {D} _{2,1}&\mathbf {C} _{2,2}\mathbf {D} _{2,2}&\mathbf {C} _{2,2}\mathbf {D} _{2,3}&\mathbf {C} _{2,3}\mathbf {D} _{2,1}&\mathbf {C} _{2,3}\mathbf {D} _{2,2}&\mathbf {C} _{2,3}\mathbf {D} _{2,3}\\\hline \mathbf {C} _{3,1}\mathbf {D} _{3,1}&\mathbf {C} _{3,1}\mathbf {D} _{3,2}&\mathbf {C} _{3,1}\mathbf {D} _{3,3}&\mathbf {C} _{3,2}\mathbf {D} _{3,1}&\mathbf {C} _{3,2}\mathbf {D} _{3,2}&\mathbf {C} _{3,2}\mathbf {D} _{3,3}&\mathbf {C} _{3,3}\mathbf {D} _{3,1}&\mathbf {C} _{3,3}\mathbf {D} _{3,2}&\mathbf {C} _{3,3}\mathbf {D} _{3,3}\end{array}}\right].$ Причина полезности этого продукта заключается в следующем:

$(\mathbf {C} \bullet \mathbf {D} )(x\otimes y)=\mathbf {C} x\circ \mathbf {D} y=\left[{\begin{array}{c }(\mathbf {C} x)_{1}(\mathbf {D} y)_{1}\\(\mathbf {C} x)_{2}(\mathbf {D} y)_{2}\\\vdots \end{array}}\right],$

где $\circ$ является поэлементным произведением ( Адамара ). Поскольку эту операцию можно вычислить за линейное время, $\mathbf {C} \bullet \mathbf {D}$ можно умножить на векторы с тензорной структурой гораздо быстрее, чем на обычные матрицы.

Построение с быстрым преобразованием Фурье

Тензорный эскиз Фама и Пага вычисляет $C^{(1)}x\ast C^{(2)}y$, где $C^{(1)}$ и $C^{(2)}$ являются независимыми матрицами эскизов счета и $\ast$ векторная свертка . Они показывают, что, как ни удивительно, это равно $C(x\otimes y)$ – счетный эскиз тензорного произведения!

Оказывается, это соотношение можно рассматривать в терминах произведения разделения граней как

$C^{(1)}x\ast C^{(2)}y={\mathcal {F}}^{-1}({\mathcal {F}}C^{(1)}x\circ {\mathcal {F}}C^{(2)}y)$, где ${\mathcal {F}}$ – матрица преобразования Фурье .

С ${\mathcal {F}}$ является ортонормированной матрицей, ${\mathcal {F}}^{-1}$ не влияет на норму $Cx$ и его можно игнорировать. Осталось только это $C\sim {\mathcal {C}}^{(1)}\bullet {\mathcal {C}}^{(2)}$.

С другой стороны,

${\mathcal {F}}(C^{(1)}x\ast C^{(2)}y)={\mathcal {F}}C^{(1)}x\circ {\mathcal {F}}C^{(2)}y=({\mathcal {F}}C^{(1)}\bullet {\mathcal {F}}C^{(2)})(x\otimes y)$.

Приложение к общим матрицам

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

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

В частности, мы получаем следующую теорему

Рассмотрим матрицу $T$ с iid строками $T_{1},\dots ,T_{m}\in \mathbb {R} ^{d}$, такой, что $E[(T_{1}x)^{2}]=\|x\|_{2}^{2}$ и $E[(T_{1}x)^{p}]^{1/p}\leq {\sqrt {ap}}\|x\|_{2}$. Позволять $T^{(1)},\dots ,T^{(c)}$ быть независимым, состоящим из $T$ и $M=T^{(1)}\bullet \dots \bullet T^{(c)}$.

Затем $|\|Mx\|_{2}-\|x\|_{2}|<\varepsilon \|x\|_{2}$ с вероятностью $1-\delta$ для любого вектора $x$ если

$m=(4a)^{2c}\varepsilon ^{-2}\log 1/\delta +(2ae)\varepsilon ^{-1}(\log 1/\delta )^{c}$.

В частности, если записи $T$ являются $\pm 1$ мы получаем $m=O(\varepsilon ^{-2}\log 1/\delta +\varepsilon ^{-1}({\tfrac {1}{c}}\log 1/\delta )^{c})$ что соответствует нормальной Джонсона Линденштрауса теореме $m=O(\varepsilon ^{-2}\log 1/\delta )$ когда $\varepsilon$ мал.

Бумага также показывает, что зависимость от $\varepsilon ^{-1}({\tfrac {1}{c}}\log 1/\delta )^{c}$ необходим для конструкций, использующих тензорные рандомизированные проекции с гауссовыми элементами.

Вариации

Рекурсивная конструкция

Из-за экспоненциальной зависимости от $c$ в тензорных скетчах на основе произведения разбиения граней в 2020 году был разработан другой подход что применимо

$M(x\otimes y\otimes \cdots )=M^{(1)}(x\otimes (M^{(2)}y\otimes \cdots ))$

Мы можем добиться такого $M$ позволяя

$M=M^{(c)}(M^{(c-1)}\otimes I_{d})(M^{(c-2)}\otimes I_{d^{2}})\cdots (M^{(1)}\otimes I_{d^{c-1}})$.

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

Это можно доказать это объединение $c$ подобные уменьшения размерности только увеличиваются $\varepsilon$ по фактору ${\sqrt {c}}$.

Быстрые конструкции

Быстрое преобразование Джонсона – Линденштрауса представляет собой матрицу уменьшения размерности.

Дана матрица $M\in \mathbb {R} ^{k\times d}$, вычисление матричного векторного произведения $Mx$ берет $kd$ время. Быстрое преобразование Джонсона-Линденштрауса (FJLT), был представлен Эйлоном и Шазель в 2006 году.

Версия этого метода принимает $M=\operatorname {SHD}$ где

1. $D$ представляет собой диагональную матрицу , где каждый диагональный элемент $D_{i,i}$ является $\pm 1$ независимо.

Умножение матрицы на вектор $Dx$ можно вычислить в $O(d)$ время.

1. $H$ — матрица Адамара , допускающая умножение матрицы на вектор во времени $O(d\log d)$
2. $S$ это $k\times d$ матрица выборки , состоящая из всех нулей, за исключением одной единицы в каждой строке.

Если заменить диагональную матрицу на матрицу, имеющую тензорное произведение $\pm 1$ значения на диагонали, вместо того, чтобы быть полностью независимыми, можно вычислить $\operatorname {SHD} (x\otimes y)$ быстрый.

В качестве примера позвольте $\rho ,\sigma \in \{-1,1\}^{2}$ быть двумя независимыми $\pm 1$ векторы и пусть $D$ быть диагональной матрицей с $\rho \otimes \sigma$ по диагонали. Тогда мы можем расстаться $\operatorname {SHD} (x\otimes y)$ следующее:

${\begin{aligned}&\operatorname {SHD} (x\otimes y)\\&\quad ={\begin{bmatrix}1&0&0&0\\0&0&1&0\\0&1&0&0\end{bmatrix}}{\begin{bmatrix}1&1&1&1\\1&-1&1&-1\\1&1&-1&-1\\1&-1&-1&1\end{bmatrix}}{\begin{bmatrix}\sigma _{1}\rho _{1}&0&0&0\\0&\sigma _{1}\rho _{2}&0&0\\0&0&\sigma _{2}\rho _{1}&0\\0&0&0&\sigma _{2}\rho _{2}\\\end{bmatrix}}{\begin{bmatrix}x_{1}y_{1}\\x_{2}y_{1}\\x_{1}y_{2}\\x_{2}y_{2}\end{bmatrix}}\\[5pt]&\quad =\left({\begin{bmatrix}1&0\\0&1\\1&0\end{bmatrix}}\bullet {\begin{bmatrix}1&0\\1&0\\0&1\end{bmatrix}}\right)\left({\begin{bmatrix}1&1\\1&-1\end{bmatrix}}\otimes {\begin{bmatrix}1&1\\1&-1\end{bmatrix}}\right)\left({\begin{bmatrix}\sigma _{1}&0\\0&\sigma _{2}\\\end{bmatrix}}\otimes {\begin{bmatrix}\rho _{1}&0\\0&\rho _{2}\\\end{bmatrix}}\right)\left({\begin{bmatrix}x_{1}\\x_{2}\end{bmatrix}}\otimes {\begin{bmatrix}y_{1}\\y_{2}\end{bmatrix}}\right)\\[5pt]&\quad =\left({\begin{bmatrix}1&0\\0&1\\1&0\end{bmatrix}}\bullet {\begin{bmatrix}1&0\\1&0\\0&1\end{bmatrix}}\right)\left({\begin{bmatrix}1&1\\1&-1\end{bmatrix}}{\begin{bmatrix}\sigma _{1}&0\\0&\sigma _{2}\\\end{bmatrix}}{\begin{bmatrix}x_{1}\\x_{2}\end{bmatrix}}\,\otimes \,{\begin{bmatrix}1&1\\1&-1\end{bmatrix}}{\begin{bmatrix}\rho _{1}&0\\0&\rho _{2}\\\end{bmatrix}}{\begin{bmatrix}y_{1}\\y_{2}\end{bmatrix}}\right)\\[5pt]&\quad ={\begin{bmatrix}1&0\\0&1\\1&0\end{bmatrix}}{\begin{bmatrix}1&1\\1&-1\end{bmatrix}}{\begin{bmatrix}\sigma _{1}&0\\0&\sigma _{2}\\\end{bmatrix}}{\begin{bmatrix}x_{1}\\x_{2}\end{bmatrix}}\,\circ \,{\begin{bmatrix}1&0\\1&0\\0&1\end{bmatrix}}{\begin{bmatrix}1&1\\1&-1\end{bmatrix}}{\begin{bmatrix}\rho _{1}&0\\0&\rho _{2}\\\end{bmatrix}}{\begin{bmatrix}y_{1}\\y_{2}\end{bmatrix}}.\end{aligned}}$

Другими словами, $\operatorname {SHD} =S^{(1)}HD^{(1)}\bullet S^{(2)}HD^{(2)}$, распадается на два быстрых преобразования Джонсона–Линденштрауса, и полное приведение требует времени $O(d_{1}\log d_{1}+d_{2}\log d_{2})$ скорее, чем $d_{1}d_{2}\log(d_{1}d_{2})$ как и при прямом подходе.

Тот же подход можно распространить на вычисление произведений более высокой степени, таких как $\operatorname {SHD} (x\otimes y\otimes z)$

Ахле и др. показывает, что если $\operatorname {SHD}$ имеет $\varepsilon ^{-2}(\log 1/\delta )^{c+1}$ ряды, затем $|\|\operatorname {SHD} x\|_{2}-\|x\||\leq \varepsilon \|x\|_{2}$ для любого вектора $x\in \mathbb {R} ^{d^{c}}$ с вероятностью $1-\delta$, позволяя при этом быстро умножать со степенью $c$ тензоры.

Джин и др., в том же году показал аналогичный результат для более общего класса матриц под названием RIP , который включает в себя субдискретные матрицы Адамара. Они показали, что эти матрицы допускают разбиение на тензоры при условии, что количество строк равно $\varepsilon ^{-2}(\log 1/\delta )^{2c-1}\log d$. В случае $c=2$ это соответствует предыдущему результату.

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

Создание эскизов с учетом данных

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

Приложения

Явные полиномиальные ядра

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

${\hat {y}}(\mathbf {x'} )=\operatorname {sgn} \sum _{i=1}^{n}y_{i}k(\mathbf {x} _{i},\mathbf {x'} ),$

где $\mathbf {x} _{i}\in \mathbb {R} ^{d}$ являются точками данных, $y_{i}$ это этикетка $i$-я точка (либо -1, либо +1), и ${\hat {y}}(\mathbf {x'} )$ это предсказание класса $\mathbf {x'}$. Функция $k:\mathbb {R} ^{d}\times \mathbb {R} ^{d}\to \mathbb {R}$ это ядро. Типичными примерами являются ядро ​​радиальной базисной функции , $k(x,x')=\exp(-\|x-x'\|_{2}^{2})$и полиномиальные ядра , такие как $k(x,x')=(1+\langle x,x'\rangle )^{2}$.

При таком использовании метод ядра называется «неявным». Иногда быстрее сделать «явный» метод ядра, в котором пара функций $f,g:\mathbb {R} ^{d}\to \mathbb {R} ^{D}$ находятся такие, что $k(x,x')=\langle f(x),g(x')\rangle$. Это позволяет выразить приведенные выше вычисления как

${\hat {y}}(\mathbf {x'} )=\operatorname {sgn} \sum _{i=1}^{n}y_{i}\langle f(\mathbf {x} _{i}),g(\mathbf {x'} )\rangle =\operatorname {sgn} \left\langle \left(\sum _{i=1}^{n}y_{i}f(\mathbf {x} _{i})\right),g(\mathbf {x'} )\right\rangle ,$

где значение $\sum _{i=1}^{n}y_{i}f(\mathbf {x} _{i})$ можно рассчитать заранее.

Проблема этого метода в том, что пространство признаков может быть очень большим. То есть $D>>d$. Например, для полиномиального ядра $k(x,x')=\langle x,x'\rangle ^{3}$ мы получаем $f(x)=x\otimes x\otimes x$ и $g(x')=x'\otimes x'\otimes x'$, где $\otimes$ – тензорное произведение и $f(x),g(x')\in \mathbb {R} ^{D}$ где $D=d^{3}$. Если $d$ уже большой, $D$ может быть намного больше, чем количество точек данных ( $n$), поэтому явный метод неэффективен.

Идея тензорного эскиза заключается в том, что мы можем вычислять приближенные функции $f',g':\mathbb {R} ^{d}\to \mathbb {R} ^{t}$ где $t$ может быть даже меньше, чем $d$, и которые все еще обладают свойством, $\langle f'(x),g'(x')\rangle \approx k(x,x')$.

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

Умножение сжатой матрицы

Предположим, у нас есть два больших набора данных, представленных в виде матриц. $X,Y\in \mathbb {R} ^{n\times d}$, и мы хотим найти строки $i,j$ с крупнейшими внутренними продуктами $\langle X_{i},Y_{j}\rangle$. Мы могли бы вычислить $Z=XY^{T}\in \mathbb {R} ^{n\times n}$ и просто посмотри на все $n^{2}$ возможности. Однако для этого потребуется как минимум $n^{2}$ времени и, вероятно, ближе к $n^{2}d$ используя стандартные методы матричного умножения.

Идея умножения сжатых матриц — это общее тождество.

$XY^{T}=\sum _{i=1}^{d}X_{i}\otimes Y_{i}$

где $\otimes$ – тензорное произведение . Поскольку мы можем вычислить ( линейное ) приближение к $X_{i}\otimes Y_{i}$ эффективно, мы можем суммировать их, чтобы получить приближение для полного продукта.

Компактное многолинейное объединение

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

Билинейное объединение — это метод получения двух входных векторов. $x,y$ из разных источников и используя тензорное произведение $x\otimes y$ в качестве входного слоя нейронной сети.

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

В 2017 году еще одна статья выполняет БПФ входных объектов перед их объединением с использованием поэлементного произведения. Это снова соответствует исходному эскизу тензора.

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

• Але, Томас; Кнудсен, Якоб (3 сентября 2019 г.). «Почти оптимальный тензорный эскиз» . Исследовательские ворота . Проверено 11 июля 2020 г.
• Слюсарь, В.И. (1998). «Конечные продукты в матрицах радиолокационных приложений» (PDF) . Радиоэлектроника и системы связи . 41 (3): 50–53.
• Слюсарь, В.И. (20 мая 1997 г.). «Аналитическая модель цифровой антенной решетки на основе изделий из матриц с разделением граней» (PDF) . Учеб. ICATT-97, Киев : 108–109.
• Слюсарь, В.И. (15 сентября 1997 г.). «Новые операции с матрицами для применения в радарах» (PDF) . Учеб. Прямые и обратные задачи теории электромагнитных и акустических волн (ДИПЕД-97), Львов. : 73–74.
• Слюсарь В.И. (13 марта 1998 г.). «Семейство лицевых продуктов матриц и его свойства» (PDF) . Кибернетика и системный анализ К/С Кибернетика и Системный Анализ.- 1999 . 35 (3): 379–384. дои : 10.1007/BF02733426 . S2CID   119661450 .