論文の概要: Compressed Deep Networks: Goodbye SVD, Hello Robust Low-Rank
Approximation
- arxiv url: http://arxiv.org/abs/2009.05647v2
- Date: Sat, 26 Sep 2020 12:24:06 GMT
- ステータス: 処理完了
- システム内更新日: 2022-10-19 20:41:38.079411
- Title: Compressed Deep Networks: Goodbye SVD, Hello Robust Low-Rank
Approximation
- Title(参考訳): 圧縮深層ネットワーク:さよならsvd, hello robust low-rank approximation
- Authors: Murad Tukan and Alaa Maalouf and Matan Weksler and Dan Feldman
- Abstract要約: ニューラルネットワークを圧縮する一般的な手法は、完全に接続された層(または埋め込み層)に対応する行列$AinmathbbRntimes d$の$k$-rank $ell$近似$A_k,2$を計算することである。
ここで$d$は層内のニューロンの数、$n$は次のニューロンの数、$A_k,2$は$O(n+d)k)$メモリに格納できる。
これ
- 参考スコア(独自算出の注目度): 23.06440095688755
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: A common technique for compressing a neural network is to compute the
$k$-rank $\ell_2$ approximation $A_{k,2}$ of the matrix
$A\in\mathbb{R}^{n\times d}$ that corresponds to a fully connected layer (or
embedding layer). Here, $d$ is the number of the neurons in the layer, $n$ is
the number in the next one, and $A_{k,2}$ can be stored in $O((n+d)k)$ memory
instead of $O(nd)$.
This $\ell_2$-approximation minimizes the sum over every entry to the power
of $p=2$ in the matrix $A - A_{k,2}$, among every matrix
$A_{k,2}\in\mathbb{R}^{n\times d}$ whose rank is $k$. While it can be computed
efficiently via SVD, the $\ell_2$-approximation is known to be very sensitive
to outliers ("far-away" rows). Hence, machine learning uses e.g. Lasso
Regression, $\ell_1$-regularization, and $\ell_1$-SVM that use the
$\ell_1$-norm.
This paper suggests to replace the $k$-rank $\ell_2$ approximation by
$\ell_p$, for $p\in [1,2]$. We then provide practical and provable
approximation algorithms to compute it for any $p\geq1$, based on modern
techniques in computational geometry.
Extensive experimental results on the GLUE benchmark for compressing BERT,
DistilBERT, XLNet, and RoBERTa confirm this theoretical advantage. For example,
our approach achieves $28\%$ compression of RoBERTa's embedding layer with only
$0.63\%$ additive drop in the accuracy (without fine-tuning) in average over
all tasks in GLUE, compared to $11\%$ drop using the existing
$\ell_2$-approximation. Open code is provided for reproducing and extending our
results.
- Abstract(参考訳): ニューラルネットワークを圧縮するための一般的なテクニックは、完全連結層(または埋め込み層)に対応する行列 $a\in\mathbb{r}^{n\times d}$の$k$-rank $\ell_2$近似$a_{k,2}$を計算することである。
ここで、$d$は層のニューロンの数、$n$は次のニューロンのニューロンの数、$a_{k,2}$は$o(n+d)k)$ではなく$o(nd)$に格納できる。
この$\ell_2$-approximation は、行列 $A - A_{k,2}$ 内の全ての入力に対する$p=2$の和を最小化し、すべての行列 $A_{k,2}\in\mathbb{R}^{n\times d}$ のランクが $k$ となる。
SVDで効率的に計算できるが、$\ell_2$-approximation は外れ値に非常に敏感であることが知られている("far-away" rows")。
したがって、機械学習はLasso Regression、$\ell_1$-regularization、$\ell_1$-SVMのように、$\ell_1$-normを使用する。
本稿では,$k$-rank$\ell_2$近似を$\ell_p$,$p\in [1,2]$に置き換えることを提案する。
次に、計算幾何学の現代的な技術に基づいて、任意の$p\geq1$で計算するための実用的で証明可能な近似アルゴリズムを提供する。
bert、distilbert、xlnet、robertaを圧縮するためのglueベンチマークの広範な実験の結果、この理論上の利点が確認された。
例えば、我々の手法は、既存の$\ell_2$-approximationを使用して、GLUEのすべてのタスクに対して平均して0.63$%の加算ドロップ(微調整なしで)でRoBERTaの埋め込み層を28.%の圧縮で達成します。
結果の再現と拡張のためにオープンコードを提供しています。
関連論文リスト
- Optimal Embedding Dimension for Sparse Subspace Embeddings [13.387361384552484]
ランダム$mtimes n$ matrix $S$は、忘れられない部分空間埋め込み(OSE)である。
mtimes n$ random matrix $S$ with $mgeq (1+theta)d$ is an oblivious subspace embedding with $epsilon = O_theta(1)$。
これを使用すれば、現在の行列乗算時間よりも早く適用できる$O(d)$埋め込み次元で、最初の難解な部分空間埋め込みを構築することができる。
論文 参考訳(メタデータ) (2023-11-17T18:01:58Z) - $\ell_p$-Regression in the Arbitrary Partition Model of Communication [59.89387020011663]
コーディネータモデルにおける分散$ell_p$-regression問題のランダム化通信複雑性について考察する。
p = 2$、すなわち最小二乗回帰の場合、$tildeTheta(sd2 + sd/epsilon)$ bitsの最初の最適境界を与える。
p in (1,2)$ に対して、$tildeO(sd2/epsilon + sd/mathrmpoly(epsilon)$ upper bound を得る。
論文 参考訳(メタデータ) (2023-07-11T08:51:53Z) - A Nearly-Optimal Bound for Fast Regression with $\ell_\infty$ Guarantee [16.409210914237086]
行列 $Ain mathbbRntimes d$ とテンソル $bin mathbbRn$ が与えられたとき、 $ell_infty$ の回帰問題を考える。
このような$ell_infty$レグレッションの保証を得るためには、濃密なスケッチ行列を使わなければならない。
我々はまた、OCE(Oblivious Coordinate-wise Embedding)特性を利用した $ell_infty$ guarantee regression のための新しい分析フレームワークを開発した。
論文 参考訳(メタデータ) (2023-02-01T05:22:40Z) - Low-Rank Approximation with $1/\epsilon^{1/3}$ Matrix-Vector Products [58.05771390012827]
我々は、任意のSchatten-$p$ノルムの下で、低ランク近似のためのクリロフ部分空間に基づく反復法について研究する。
我々の主な成果は、$tildeO(k/sqrtepsilon)$ matrix-vector productのみを使用するアルゴリズムである。
論文 参考訳(メタデータ) (2022-02-10T16:10:41Z) - Active Sampling for Linear Regression Beyond the $\ell_2$ Norm [70.49273459706546]
対象ベクトルの少数のエントリのみを問合せすることを目的とした線形回帰のためのアクティブサンプリングアルゴリズムについて検討する。
我々はこの$d$への依存が対数的要因まで最適であることを示す。
また、損失関数に対して最初の全感度上界$O(dmax1,p/2log2 n)$を提供し、最大で$p$成長する。
論文 参考訳(メタデータ) (2021-11-09T00:20:01Z) - Learning a Latent Simplex in Input-Sparsity Time [58.30321592603066]
我々は、$AinmathbbRdtimes n$へのアクセスを考えると、潜入$k$-vertex simplex $KsubsetmathbbRdtimes n$を学習する問題を考える。
実行時間における$k$への依存は、トップ$k$特異値の質量が$a$であるという自然な仮定から不要であることを示す。
論文 参考訳(メタデータ) (2021-05-17T16:40:48Z) - Deep Learning Meets Projective Clustering [66.726500395069]
NLPネットワークを圧縮するための一般的なアプローチは、埋め込み層を行列 $AinmathbbRntimes d$ としてエンコードすることである。
計算幾何学から遠射的クラスタリングに着想を得て、この部分空間を$k$部分空間の集合で置き換えることを提案する。
論文 参考訳(メタデータ) (2020-10-08T22:47:48Z) - On Efficient Low Distortion Ultrametric Embedding [18.227854382422112]
データの基盤となる階層構造を保存するために広く用いられる方法は、データを木や超音波に埋め込む方法を見つけることである。
本稿では,$mathbbRd2(ユニバーサル定数$rho>1$)の点集合を入力として,超測度$Deltaを出力する新しいアルゴリズムを提案する。
我々のアルゴリズムの出力はリンクアルゴリズムの出力に匹敵するが、より高速な実行時間を実現する。
論文 参考訳(メタデータ) (2020-08-15T11:06:45Z) - Average Case Column Subset Selection for Entrywise $\ell_1$-Norm Loss [76.02734481158458]
最悪の場合、行列に対する良いランク-$k$近似を得るには、任意に大きい$nOmega(1)$列数が必要であることが知られている。
最小かつ現実的な分布設定では、ほぼ線形な実行時間を持つ$(k/epsilon)$-approximationとpoly$(k/epsilon)+O(klog n)$ columnsが得られる。
これは、エントリワイズで$(k/epsilon)$-approximationを達成するための任意の種類の最初のアルゴリズムである
論文 参考訳(メタデータ) (2020-04-16T22:57:06Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。