テンソルスケッチ

統計学、機械学習、アルゴリズムにおいて、テンソルスケッチは次元削減の一種であり、テンソル構造を持つベクトルに適用すると特に効率的です。^{[1] [2]このようなスケッチは、明示的}カーネル法やニューラルネットワークの双線形プーリングを高速化するために使用でき、多くの数値線形代数アルゴリズムの基礎となっています。^[3]

数学的には、次元削減行列またはスケッチ行列は、任意のベクトルに対してとなる行列である。${\displaystyle M\in \mathbb {R} ^{k\times d}}$${\displaystyle k<d}$${\displaystyle x\in \mathbb {R} ^{d}}$

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

高い確率で。言い換えれば、小さな誤差までベクトルのノルムを保存します。 ${\displaystyle M}$

テンソル スケッチには、となるようなベクトルに対して であれば、変換をより効率的に計算できるという追加の特性があります。ここで は外積ではなくクロネッカー積を表しますが、この 2 つは平坦化によって関連しています。 ${\displaystyle x=y\otimes z}$${\displaystyle y\in \mathbb {R} ^{d_{1}},z\in \mathbb {R} ^{d_{2}}}$${\displaystyle d_{1}d_{2}=d}$${\displaystyle M(y\otimes z)}$${\displaystyle \otimes }$

高速化は、まず を書き換えることによって実現されます。ここで、 は要素ごとの (アダマール) 積を表します。 および はそれぞれ、時間とで計算できます。アダマール積を含めると、全体の時間は になります。ほとんどの使用例では、この方法は、 の時間を必要とする完全な方法よりも大幅に高速です。 ${\displaystyle M(y\otimes z)=M'y\circ M''z}$${\displaystyle \circ }$${\displaystyle M'y}$${\displaystyle M''z}$${\displaystyle O(kd_{1})}$${\displaystyle O(kd_{2})}$${\displaystyle O(d_{1}d_{2}+kd_{1}+kd_{2})}$${\displaystyle M(y\otimes z)}$${\displaystyle O(kd)=O(kd_{1}d_{2})}$

などの高次テンソルの場合、節約効果はさらに顕著になります。 ${\displaystyle x=y\otimes z\otimes t}$

テンソルスケッチという用語は、2013年に造られ^[4]、同年にRasmus Pagh ^[5]が行った手法を説明しています。もともとは、高速フーリエ変換を使用してカウントスケッチの高速畳み込みを行うと考えられていました。その後の研究により、テンソルランダム埋め込みを介したはるかに大規模な次元削減に一般化されました。

テンソルランダム埋め込みは、2010年に差分プライバシーに関する論文^[6]で導入され、2012年にRudelsonらによってスパース回復の文脈で初めて分析されました。^[7]

Avronら^{[8]は、特に}多項式カーネル への応用に焦点を当てて、テンソルスケッチの部分空間埋め込み特性を研究した最初の研究者です。この文脈では、スケッチは、各ベクトルのノルムを一定の確率で保存するだけでなく、各線形部分空間内のすべてのベクトルのノルムを保存することが求められます。これは非常に強力な特性であり、より大きなスケッチサイズを必要としますが、David Woodruffの著書で説明されているように、カーネル法を非常に幅広く使用できるようになります。^[3]

面分割積は行のテンソル積として定義されます（1996年にV. Slyusar ^{[9]によって提案されました[10] [11] [12] [13] [14]}レーダーとデジタルアンテナアレイのアプリケーション用）。より直接的には、とを2つの行列とします。このとき、面分割積は^{[10] [11] [12] [13]}です。 この積が有用な理由は、次の恒等式です。 ${\displaystyle \mathbf {C} \in \mathbb {R} ^{3\times 3}}$${\displaystyle \mathbf {D} \in \mathbb {R} ^{3\times 3}}$ ${\displaystyle \mathbf {C} \bullet \mathbf {D} }$ ${\displaystyle \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].}$

${\displaystyle (\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],}$

ここで、は要素ごとの (アダマール) 積です。この演算は線形時間で計算できるため、テンソル構造を持つベクトルに対して通常の行列よりもはるかに高速に乗算できます。 ${\displaystyle \circ }$${\displaystyle \mathbf {C} \bullet \mathbf {D} }$

^{PhamとPagh [4]}のテンソルスケッチはを計算します 。ここで、と は独立したカウントスケッチ行列で、 はベクトル畳み込みです。彼らは、驚くべきことに、これが に等しいことを示しています。これはテンソル積のカウントスケッチです。 ${\displaystyle C^{(1)}x\ast C^{(2)}y}$${\displaystyle C^{(1)}}$${\displaystyle C^{(2)}}$${\displaystyle \ast }$${\displaystyle C(x\otimes y)}$

この関係は面分割積の観点から次のように 見ることができる。

${\displaystyle C^{(1)}x\ast C^{(2)}y={\mathcal {F}}^{-1}({\mathcal {F}}C^{(1)}x\circ {\mathcal {F}}C^{(2)}y)}$ここで、 はフーリエ変換行列です。${\displaystyle {\mathcal {F}}}$

は正規直交行列なので、のノルムには影響せず、無視できます。残るのは です。 ${\displaystyle {\mathcal {F}}}$${\displaystyle {\mathcal {F}}^{-1}}$${\displaystyle Cx}$${\displaystyle C\sim {\mathcal {C}}^{(1)}\bullet {\mathcal {C}}^{(2)}}$

一方で、

${\displaystyle {\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年^[15]には、十分にランダムな独立行を持つ任意の行列であれば、テンソルスケッチを作成するのに十分であることが示されました。これにより、実ガウスジョンソンリンデンシュトラウス行列などのより強力な保証を持つ行列を使用できるようになります。

特に、次の定理が得られる。

およびとなるiid 行を持つ行列を考えます。 がおよびからなる独立した行列であるとします。${\displaystyle T}$${\displaystyle T_{1},\dots ,T_{m}\in \mathbb {R} ^{d}}$${\displaystyle E[(T_{1}x)^{2}]=\|x\|_{2}^{2}}$${\displaystyle E[(T_{1}x)^{p}]^{1/p}\leq {\sqrt {ap}}\|x\|_{2}}$${\displaystyle T^{(1)},\dots ,T^{(c)}}$${\displaystyle T}$${\displaystyle M=T^{(1)}\bullet \dots \bullet T^{(c)}}$

すると、任意のベクトルに対して確率的に${\displaystyle |\|Mx\|_{2}-\|x\|_{2}|<\varepsilon \|x\|_{2}}$${\displaystyle 1-\delta }$${\displaystyle x}$

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

特に、 の要素がである場合、 が小さいときの通常のジョンソン・リンデンシュトラウスの定理と一致する が得られます。 ${\displaystyle T}$${\displaystyle \pm 1}$${\displaystyle m=O(\varepsilon ^{-2}\log 1/\delta +\varepsilon ^{-1}({\tfrac {1}{c}}\log 1/\delta )^{c})}$${\displaystyle m=O(\varepsilon ^{-2}\log 1/\delta )}$${\displaystyle \varepsilon }$

論文^{[15]では、}ガウス分布を持つテンソルランダム化射影を用いた構成には依存性が必要であることも示されている。 ${\displaystyle \varepsilon ^{-1}({\tfrac {1}{c}}\log 1/\delta )^{c}}$

面分割積に基づくテンソルスケッチにおける 指数関数的な依存性のため、2020年に^[15]で異なるアプローチが開発され、 ${\displaystyle c}$

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

このようなことは、 ${\displaystyle M}$

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

この方法では、一般的なテンソル スケッチ メソッドを 2 つのテンソルの順序にのみ適用し、行数の指数依存性を回避します。

^[15]このように次元削減を組み合わせると、係数だけ増加するということが証明されています。 ${\displaystyle c}$${\displaystyle \varepsilon }$${\displaystyle {\sqrt {c}}}$

高速ジョンソン・リンデンシュトラウス変換は次元削減行列である

行列が与えられた場合、行列ベクトル積の計算には時間がかかります。高速ジョンソンリンデンシュトラウス変換（FJLT）^[16]は、 2006年に AilonとChazelleによって導入されました。${\displaystyle M\in \mathbb {R} ^{k\times d}}$${\displaystyle Mx}$${\displaystyle kd}$

この方法のバージョンでは 、 ${\displaystyle M=\operatorname {SHD} }$

1. ${\displaystyle D}$各対角要素が独立している対角行列です。${\displaystyle D_{i,i}}$${\displaystyle \pm 1}$

行列とベクトルの乗算は時間内に計算できます。 ${\displaystyle Dx}$${\displaystyle O(d)}$

1. ${\displaystyle H}$はアダマール行列であり、行列とベクトルの乗算を100分で行うことができる。${\displaystyle O(d\log d)}$
2. ${\displaystyle S}$各行に 1 つだけ 1 がある以外はすべてゼロのサンプリング マトリックスです。${\displaystyle k\times d}$

対角行列を、完全に独立しているのではなく、対角線上の値のテンソル積を持つ行列に置き換えると、高速に計算できるようになります。 ${\displaystyle \pm 1}$${\displaystyle \operatorname {SHD} (x\otimes y)}$

この例として、 が2 つの独立したベクトルで、 が対角線上にある対角行列であるとします。次のように分割できます。 ${\displaystyle \rho ,\sigma \in \{-1,1\}^{2}}$${\displaystyle \pm 1}$${\displaystyle D}$${\displaystyle \rho \otimes \sigma }$${\displaystyle \operatorname {SHD} (x\otimes y)}$

${\displaystyle {\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}}}$

言い換えると、は 2 つの高速ジョンソン・リンデンシュトラウス変換に分割され、全体の削減には直接的なアプローチの場合 よりも時間がかかります。${\displaystyle \operatorname {SHD} =S^{(1)}HD^{(1)}\bullet S^{(2)}HD^{(2)}}$${\displaystyle O(d_{1}\log d_{1}+d_{2}\log d_{2})}$${\displaystyle d_{1}d_{2}\log(d_{1}d_{2})}$

同じアプローチを拡張して、次のような高次の積を計算することもできる。${\displaystyle \operatorname {SHD} (x\otimes y\otimes z)}$

Ahleら^[15]は、 が行を持つ場合、任意のベクトルに対しての確率でとなり、次数テンソルとの高速な乗算が可能になることを示しています。 ${\displaystyle \operatorname {SHD} }$${\displaystyle \varepsilon ^{-2}(\log 1/\delta )^{c+1}}$${\displaystyle |\|\operatorname {SHD} x\|_{2}-\|x\||\leq \varepsilon \|x\|_{2}}$${\displaystyle x\in \mathbb {R} ^{d^{c}}}$${\displaystyle 1-\delta }$${\displaystyle c}$

同年、Jinら^{[17]は、サブサンプルされたアダマール行列を含む}RIPと呼ばれるより一般的な行列のクラスに対して同様の結果を示した。彼らは、行数が であればこれらの行列をテンソルに分割できることを示した。 の場合、これは以前の結果と一致します。 ${\displaystyle \varepsilon ^{-2}(\log 1/\delta )^{2c-1}\log d}$${\displaystyle c=2}$

これらの高速な構築は、前述の再帰アプローチと組み合わせることができ、全体的に最も高速なテンソル スケッチが得られます。

いわゆる「データ認識型」テンソルスケッチを行うことも可能である。データにランダム行列を掛ける代わりに、データポイントはポイントのノルムに応じて一定の確率で独立してサンプリングされる。^[18]

カーネル法は、データ ポイントの類似性を測定するための「特徴空間」を設計する自由をアルゴリズムに与えるため、機械学習で人気があります。単純なカーネル ベースのバイナリ分類器は、次の計算に基づいています。

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

ここで、はデータ点、は 番目の点のラベル（−1 または +1）、 はのクラスの予測です。 関数はカーネルです。 典型的な例としては、ラジアル基底関数カーネル、、およびなどの多項式カーネルがあります。 ${\displaystyle \mathbf {x} _{i}\in \mathbb {R} ^{d}}$${\displaystyle y_{i}}$${\displaystyle i}$${\displaystyle {\hat {y}}(\mathbf {x'} )}$${\displaystyle \mathbf {x'} }$${\displaystyle k:\mathbb {R} ^{d}\times \mathbb {R} ^{d}\to \mathbb {R} }$${\displaystyle k(x,x')=\exp(-\|x-x'\|_{2}^{2})}$${\displaystyle k(x,x')=(1+\langle x,x'\rangle )^{2}}$

このように使用されるカーネル法は「暗黙的」と呼ばれます。となる関数のペアを見つける「明示的」カーネル法を実行する方が速い場合もあります。これにより、上記の計算は次のように表すことができます。 ${\displaystyle f,g:\mathbb {R} ^{d}\to \mathbb {R} ^{D}}$${\displaystyle k(x,x')=\langle f(x),g(x')\rangle }$

${\displaystyle {\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 ,}$

ここで、値は事前に計算できます。 ${\displaystyle \sum _{i=1}^{n}y_{i}f(\mathbf {x} _{i})}$

この方法の問題点は、特徴空間が非常に大きくなる可能性があることです。つまり、 です。たとえば、多項式カーネルの場合、およびが得られます。ここで、はテンソル積であり、です。がすでに大きい場合、はデータ ポイントの数 ( ) よりもはるかに大きくなる可能性があるため、明示的な方法は非効率的です。 ${\displaystyle D>>d}$${\displaystyle k(x,x')=\langle x,x'\rangle ^{3}}$${\displaystyle f(x)=x\otimes x\otimes x}$${\displaystyle g(x')=x'\otimes x'\otimes x'}$${\displaystyle \otimes }$${\displaystyle f(x),g(x')\in \mathbb {R} ^{D}}$${\displaystyle D=d^{3}}$${\displaystyle d}$${\displaystyle D}$${\displaystyle n}$

テンソル スケッチの考え方は、が よりも小さくてもという性質が依然として維持される近似関数を計算できるというものです。 ${\displaystyle f',g':\mathbb {R} ^{d}\to \mathbb {R} ^{t}}$${\displaystyle t}$${\displaystyle d}$${\displaystyle \langle f'(x),g'(x')\rangle \approx k(x,x')}$

この方法は2020年に^[15]高次多項式やラジアル基底関数カーネルでも機能することが示されました。

行列 として表される 2 つの大きなデータセットがあり、内積が最大となる行を見つけたいとします。 を計算して、すべての可能性を調べるだけで済みます。ただし、これには少なくとも時間がかかり、おそらく標準的な行列乗算手法を使用するのに近いものになります。 ${\displaystyle X,Y\in \mathbb {R} ^{n\times d}}$${\displaystyle i,j}$${\displaystyle \langle X_{i},Y_{j}\rangle }$${\displaystyle Z=XY^{T}\in \mathbb {R} ^{n\times n}}$${\displaystyle n^{2}}$${\displaystyle n^{2}}$${\displaystyle n^{2}d}$

圧縮行列乗算の考え方は、一般的な同一性である

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

ここで、 はテンソル積です。 の (線形) 近似を効率的に計算できるため、それらを合計して完全な積の近似値を得ることができます。 ${\displaystyle \otimes }$${\displaystyle X_{i}\otimes Y_{i}}$

双線形プーリングは、異なるソースから 2 つの入力ベクトルを取得し、テンソル積をニューラル ネットワークへの入力層として 使用する手法です。${\displaystyle x,y}$${\displaystyle x\otimes y}$

^[19]では、著者らは必要な変数の数を減らすためにテンソルスケッチの使用を検討した。

2017年の別の論文^[20]では、要素ごとの積を使用して結合される前に、入力特徴のFFTが取られています。これも元のテンソルスケッチに対応しています。

• Ahle, Thomas; Knudsen, Jakob (2019-09-03). 「Almost Optimal Tensor Sketch」. ResearchGate . 2020-07-11に閲覧。
• Slyusar, VI (1998). 「レーダーアプリケーションにおけるマトリックスの最終製品」(PDF) .無線エレクトロニクスと通信システム. 41 (3): 50–53.
• Slyusar, VI (1997-05-20). 「面分割行列積に基づくデジタルアンテナアレイの解析モデル」(PDF) . Proc. ICATT-97, キエフ: 108–109.
• Slyusar, VI (1997-09-15). 「レーダーへの応用のための行列積の新しい演算」(PDF) . Proc. Direct and Inverse Problems of Electromagnetic and Acoustic Wave Theory (DIPED-97)、リヴィウ: 73–74。
• Slyusar, VI (1998 年 3 月 13 日)。「行列の面積のファミリーとその特性」(PDF)。サイバネティクスとシステム分析 C/C of Kibernetika I Sistemnyi Analiz.- 1999。35 ( 3 ) : 379–384。doi :10.1007/BF02733426。S2CID 119661450  。