Upgrade to Pro — share decks privately, control downloads, hide ads and more …

論文紹介:Precise Expressions for Random Projections

論文紹介:Precise Expressions for Random Projections

Random Projections (ランダム射影)の理論的考察を深めた以下の論文の紹介スライドです:
Michal Derezinski, Feynman T. Liang, Zhenyu Liao, Michael W. Mahoney, "
Precise expressions for random projections: Low-rank approximation and randomized Newton,"
NeurIPS2020

・論旨が追いやすくなるよう原論文から構成などは変えています
・なるべくself-containedな資料とするため,原論文には記載のないRandom Projections,劣ガウス分布,Implicit Regularizationそれぞれの概説を付け加えています
・画質の問題から,ブラウザ上でなくダウンロードしてお手元のPDFビューアで閲覧することをおすすめします

Takahiro Kawashima

June 19, 2023
Tweet

More Decks by Takahiro Kawashima

Other Decks in Research

Transcript

  1. 論文概要 • title: “Precise expressions for random projections: Low-rank approximation

    and randomized Newton” • authors: Michał Dereziński, Feynmann Liang, Zhenyu Liao, Michael W. Mahoney • published in: NeurIPS 2020 新たな方法で Random Projection の理論解析を行い,その正当性 を補強 2
  2. 次元削減による行列近似:最適編 巨大な行列 𝑨 ∈ ℝ𝑚×𝑛 を使って何かしたい ∠ 例:𝒂1 , …

    , 𝒂𝑛 ∈ ℝ𝑚 と 𝑦1 , … , 𝑦𝑛 ∈ {0, 1} から判別境界を引く 計算量を削減するための常套手段: ∠ 行列 𝑨 の PCA/SVD 𝑚 ≥ 𝑛 のとき,𝑨 の SVD の計算量は O(𝑚𝑛2).  PCA/SVD は最適な 𝑨 の低ランク近似を与える.  巨大な行列に対しては計算が(まだ)重いことも…… 3
  3. 次元削減による行列近似:適当編 最適な低ランク近似が大変なら,もっと適当な近似はどうか? wine データ(𝑚 = 13, 𝑛 = 178,3 クラス)を「適当な行列」で

    2 次元に射影してみる ∠ 𝑺 ∈ ℝ2×13 を 𝑠𝑖𝑗 iid ∼ N(0, 1) から生成し,𝑺𝑨 をプロット 案外アリ? 4
  4. Random Projections と JL Lemma ランダム行列による射影で巨大な行列を高速かつ近似的に扱う枠 組みを Random Projection という1.

    Random Projection からなるアルゴリズムは,基本的に次の補題 から理論的に正当化される: Johnson-Lindenstrauss (JL) Lemma 任意の 𝑨 ∈ ℝ𝑚×𝑛, 0 < 𝜖 < 1 と 𝑘 ≥ big-Omega 記法 ⏞⏞⏞⏞⏞⏞⏞ Ω(log 𝑛/(𝜖2 − 𝜖3)) に よって 𝛿 = 2𝑒−(𝜖2−𝜖3)(𝑘/4) とする. 𝑺 ∈ ℝ𝑘×𝑚 を各要素が N(0, 1/𝑘) に iid にしたがうランダム 行列とするとき,次が成り立つ: ℙ((1 − 𝜖)‖𝒂𝑖 − 𝒂𝑗 ‖2 ≤ ‖𝑺𝒂𝑖 − 𝑺𝒂𝑗 ‖2 ≤ (1 + 𝜖)‖𝒂𝑖 − 𝒂𝑗 ‖2) ≥ 1 − 𝛿 1より一般には Matrix Sketching というらしい. 5
  5. Random Projections と JL Lemma Johnson-Lindenstrauss (JL) Lemma 任意の 𝑨

    ∈ ℝ𝑚×𝑛, 0 < 𝜖 < 1 と 𝑘 ≥ Ω(log 𝑛/(𝜖2 − 𝜖3)) に よって 𝛿 = 2𝑒−(𝜖2−𝜖3)(𝑘/4) とする. 𝑺 ∈ ℝ𝑘×𝑚 を各要素が N(0, 1/𝑘) に iid にしたがうランダム 行列とするとき,次が成り立つ: ℙ((1 − 𝜖)‖𝒂𝑖 − 𝒂𝑗 ‖2 ≤ ‖𝑺𝒂𝑖 − 𝑺𝒂𝑗 ‖2 ≤ (1 + 𝜖)‖𝒂𝑖 − 𝒂𝑗 ‖2) ≥ 1 − 𝛿 主張:ランダムな射影を施しても距離構造はある程度保たれる ∠ 𝑘 ≥ Ω(log 𝑛/(𝜖2 − 𝜖3)) より  高次元であるほど恩恵大 代表的な応用例:低ランク近似 O(𝑚𝑛 log 𝑛) [1],圧縮センシング [2] 本論文では,JL Lemma とは異なる道具立てからより精密に Random Projections のふるまいを評価する. 6
  6. 方針 𝑿 ∈ ℝ𝑘×𝑛 の 𝑘 個の行ベクトルが張る部分空間への射影行列 𝑷 は 𝑷

    = 𝑿†𝑿 と書ける ∠ その直交補空間への射影行列は𝑷⟂ ∶= 𝑰 − 𝑷 = 𝑰 − 𝑿†𝑿. 論文の方針 𝑿 がランダム行列であるときの 𝑷⟂ の期待値 𝔼[𝑷⟂ ] のふる まいを通して Random Projection の理論的考察を行う 𝑿 がどのようなランダム行列であればよいかを明確化するため, まずは劣ガウス性の概念を導入していく. 7
  7. Sub-Gaussian Distributions 確率分布の裾がガウス分布より軽い(減衰が速い)確率分布は 劣ガウス分布 (sub-gaussian distribution) とよばれる: 定義:劣ガウス分布 (sub-gaussian distribution)

    ある 𝐶 > 0 が存在し,確率変数 𝑋 が任意の 𝑡 > 0 に対し ℙ(|𝑥| ≥ 𝑡) ≤ 2 exp (− 𝑡2 𝐶2 ) を満たすとき,𝑋 が従う分布は劣ガウス分布であるという. 不等式右辺はガウス分布の裾関数. 8
  8. Sub-Gaussian Norm 定義:劣ガウスノルム (sub-gaussian (Orlicz) norm) 確率変数 𝑥 の劣ガウスノルム ‖𝑋‖𝜓2

    を次で定義: ‖𝑥‖𝜓2 ∶= inf {𝑡 > 0 ∶ 𝔼[exp(𝑥2/𝑡2)] ≤ 2}. 事実:劣ガウスノルムと劣ガウス性 ‖𝑥‖𝜓2 < ∞ と 𝑥 が劣ガウス確率変数であることは等価. 例 1:𝑋 が Rademacher 確率変数(実現値 ±1 を等確率でとる) ∠ ‖𝑥‖𝜓2 = 1/ √ log 2. 例 2:𝑋 ∼ N(0, 1) ∠ ‖𝑥‖𝜓2 = √3/8. 9
  9. K-Sub-Gaussianity 事実:劣ガウスノルムと劣ガウス性 ‖𝑥‖𝜓2 < ∞ と 𝑥 が劣ガウス確率変数であることは等価. 定義:𝐾-劣ガウス確率変数 (𝐾-sub-gaussianity)

    確率変数 𝑥 が ‖𝑥‖𝜓2 ≤ 𝐾 を満たすとき,𝑥 は 𝐾-劣ガウス確 率変数であるという. また確率ベクトル 𝒙 が任意の 𝒂, ‖𝒂‖ ≤ 1 について ‖𝒙⊤𝒂‖𝜓2 ≤ 𝐾 を満たすとき, 𝒙 は 𝐾-劣ガウスであるという, 10
  10. Residual Projection Matrix の誤差 主定理:Residual Projection Matrix の誤差 𝜮 1

    2 ∈ 𝕊𝑛 + と各行が平均 𝟎, 共分散 𝑰 の 𝐾-劣ガウスな i.i.d. 確 率ベクトルである 𝒁 ∈ ℝ𝑘×𝑛 によって 𝑿 = 𝒁𝜮 1 2 とする. ̄ 𝑷⟂ ∶= (𝛾𝜮 + 𝑰)−1, with 𝛾 > 0 s.t. tr ̄ 𝑷⟂ = 𝑛 − 𝑘 および 𝜮 1 2 の stable rank 𝑟 ∶= tr(𝜮)/‖𝜮‖ を定義し,さら に 𝜌 ∶= 𝑟/𝑘 > 1 を fix する. このとき 𝜌, 𝐾 のみに依存する定数 𝐶𝜌 > 0 が存在して ‖𝑰 −𝔼[𝑷⟂ ] ̄ 𝑷 −1 ⟂ ‖ ≤ 𝐶𝜌 √ 𝑟 とでき, それが 𝑟 ≥ 𝐶𝜌 を満たす場合: (1 − 𝐶𝜌 √ 𝑟 ) ̄ 𝑷⟂ ⪯ 𝔼[𝑷⟂ ] ⪯ (1 + 𝐶𝜌 √ 𝑟 ) ̄ 𝑷⟂ . 11
  11. Residual Projection Matrix の誤差 系 1:主定理の一般化 𝑨 ∈ ℝ𝑚×𝑛(𝑚 ≥

    𝑛) と各行が平均 𝟎,共分散 𝑰 の 𝐾-劣ガウ スな i.i.d. 確率ベクトルである 𝑺 ∈ ℝ𝑘×𝑚 により 𝑷⟂ ∶= 𝑰 − (𝑺𝑨)†𝑺𝑨, ̄ 𝑷⟂ ∶= (𝛾𝑨⊤𝑨 + 𝑰)−1, with 𝛾 > 0 s.t. tr ̄ 𝑷⟂ = 𝑛 − 𝑘 とする.𝑨 の stable rank 𝑟 = ‖𝑨‖2 𝐹 /‖𝑨‖ および定数 𝜌 ∶= 𝑟/𝑘 > 1 のもと,次が成り立つ: (1 − 𝜖) ̄ 𝑷⟂ ⪯ 𝔼[𝑷⟂ ] ⪯ (1 + 𝜖) ̄ 𝑷⟂ for 𝜖 = O(𝑟− 1 2 ). 主定理の 𝜮 1 2 ∈ 𝕊𝑛 + が任意の 𝑨 ∈ ℝ𝑚×𝑛 になった. ∠  𝑨 の特異値に依存しないバウンド 12
  12. 低ランク近似の誤差 簡単のため,次の近似表記を導入2: 𝑿 𝜖 ≃ 𝒀 def ⇔ (1 −

    𝜖)𝒀 ⪯ 𝑿 ⪯ (1 + 𝜖)𝒀 ∠ 系 1 の主張は 𝔼[𝑷⟂ ] 𝜖 ≃ ̄ 𝑷⟂ . 系 2:低ランク近似の誤差 系 1 と同様の記号のもと,射影行列 𝑷 ∶= (𝑺𝑨)†𝑺𝑨 に関し 𝔼[‖𝑨 − 𝑨𝑷 ‖2 𝐹 ] 𝜖 ≃ 𝑘/𝛾 for 𝛾 > 0 s.t. ∑ 𝑖 𝛾𝜎2 𝑖 𝛾𝜎2 𝑖 + 1 = 𝑘. ∠ 適用例:Nyström 近似の近似誤差解析:𝔼[‖𝑲 − ̃ 𝑲‖trace ] 𝜖 ≃ 𝑘/𝛾. 注意:𝛾 = 𝛾(𝑘) は 𝑘 について少なくとも線形以上(後述) 2𝑿, 𝒀 がスカラーでも同様.ベクトルの場合は element-wise な順序づけ? 13
  13. 反復アルゴリズムの誤差 線形系を解く Kaczmarz 法をランダム化した一般化 Kaczmarz 法 について,次の結果が得られる: 系 3:一般化 Kaczmarz

    法の誤差 𝒙∗ を 𝑨𝒙 = 𝒃 の一意な解とし,反復アルゴリズム 𝒙𝑡+1 = arg min 𝒙 ‖𝒙 − 𝒙𝑡‖2 subj. to 𝑺𝑨𝒙 = 𝑺𝒃 を考える.このとき 𝔼[𝒙𝑡+1 − 𝒙∗] 𝜖 ≃ (𝛾𝑨⊤𝑨 + 𝑰)−1𝔼[𝒙𝑡 − 𝒙∗] for 𝜖 = O(𝑟− 1 2 ). (𝛾𝑨⊤𝑨 + 𝑰)−1 ≺ 𝑰 より期待誤差の減少が言える. Randomized Subspace Newton などほかの反復法の解析も可能. 14
  14. Implicit Regularization との関係 系 3 について 𝒙𝑡 = 𝟎 とすると,劣決定線形系

    (𝑺𝑨, 𝑺𝒃) の最小ノ ルム解についての主張が得られる: 𝔼 [ arg min 𝒙∶𝑺𝑨𝒙=𝑺𝒃 ‖𝒙‖2] − 𝒙∗ 𝜖 ≃ arg min 𝒙 {‖𝑨𝒙 − 𝒃‖2 + 𝛾−1‖𝒙‖2} − 𝒙∗. 左辺:ランダム化された最小ノルム解のバイアス 右辺:ℓ2 正則化のかかった元問題の解のバイアス ランダム化された反復アルゴリズムで overparameterized な線形 モデルを解くと implicit regularization が生じることを示唆. 16
  15. スペクトルの減衰と 𝛾 これまでの議論より, ̄ 𝑷⟂ = (𝛾𝑨⊤𝑨 + 𝑰)−1 𝜖

    ≃ 𝔼[𝑷⟂ ] がわかった. パラメータ 𝛾 は 𝑨 の特異値 {𝜎𝑖 } に対して ∑ 𝑖≥1 𝛾𝜎2 𝑖 𝛾𝜎2 𝑖 + 1 = 𝑘 を満たす必要がある. 𝛾 の厳密な解析解は求まらないが,𝑨⊤𝑨 のスペクトル 𝜎2 𝑖 の減衰 率が既知の場合,解析的な近似解がうまく求まる場合がある. 例:カーネル行列の Nyström 近似 ∠ RBF では指数関数的,Matérn では多項式的に減衰 17
  16. 指数関数的なケース 𝜎2 𝑖 が指数関数的に減衰する場合,定数 𝐶 と 𝛼 ∈ (0, 1)

    によって 𝜎2 𝑖 = 𝐶𝛼𝑖−1 とできる.近似のために 𝑚, 𝑛 → ∞ として ∑ 𝑖≥1 𝛾𝜎2 𝑖 𝛾𝜎2 𝑖 +1 の和を積 分に置き換えれば ∫ ∞ 𝑦 1 1 + (𝐶𝛾)−1𝛼−𝑥 𝑑𝑥 となるが,これは解析的に扱える3. ∠ 𝛾 ≈ (𝛼−𝑘 − 1) √ 𝛼/𝐶と決定できる 3積分範囲の 𝑦 の意味が不明.𝑦 = 0 ? 18
  17. 多項式的なケース スペクトルの減衰が多項式的な場合も同様で,積分 ∫ ∞ 𝑦 1 1 + (𝐶𝛾)−1𝑥−𝛽 𝑑𝑥

    を解くことにより,パラメータ 𝛾 を 𝛾 ≈ ((𝑘 + 1 2 ) 𝛽 𝜋 sin 𝜋 𝛽 ) 𝛽 と決定できる. 19
  18. パラメータ決定:実験 近似から得られた 𝛾 で低ランク近似の誤差を見積もる実験 𝑚, 𝑛 = 1000 とし,近似による 𝛾

    と ∑ 𝑖≥1 𝛾𝜎2 𝑖 𝛾𝜎2 𝑖 +1 = 𝑘 の数値解を 比較 ∠  解析的に扱える近似解で十分よさげ 20
  19. まとめ • 従来の PAC 型でなく,誤差の期待値を上下から抑える方針で Random Projection の精密な理論評価を行った • 漸近的な解析に基づかない

    • 射影のためのランダム行列には劣ガウス性しか仮定しないた め,Rademacher 型など non-Gaussian でも OK • もとの行列 𝑨 の最大・最小特異値に依存せず,代わりにその stable rank に依存 ∠ 𝑨 が ill-conditioned でも work • スカラーの近似誤差でなく,半正定値性による順序付け ⪯ の 意味でのバウンドなので,より informative • 低ランク近似のみならず,反復法の誤差評価や implicit regularization への示唆にも 23
  20. References i [1] Papadimitriou, C. H., Raghavan, P., Tamaki, H.,

    and Vempala, S., “Latent Semantic Indexing: A Probabilistic Analysis,” Journal of Computer and System Sciences, 61, pp.217–235, 2000. [2] Baraniuk, R., Davenport, M., DeVore, R., and Wakin, M., “A Simple Proof of the Restricted Isometry Property for Random Matrices,” Constructive Approximation, 28, pp.253–263, 2008. [3] Tsigler, A., Bartlett, P. L., “Benign Overfitting in Ridge Regression,” Journal of Machine Learning Research, 24, pp.1–76, 2023.