論文の概要: Alpha Elimination: Using Deep Reinforcement Learning to Reduce Fill-In
during Sparse Matrix Decomposition
- arxiv url: http://arxiv.org/abs/2310.09852v1
- Date: Sun, 15 Oct 2023 14:51:22 GMT
- ステータス: 処理完了
- システム内更新日: 2023-10-17 17:40:00.398047
- Title: Alpha Elimination: Using Deep Reinforcement Learning to Reduce Fill-In
during Sparse Matrix Decomposition
- Title（参考訳）: アルファ除去: 深部強化学習を用いたスパースマトリックス分解時のフィルイン低減
- Authors: Arpan Dasgupta, Pawan Kumar
- Abstract要約: スパース行列再構成問題に対する強化学習に基づくアプローチを提案する。
提案手法では, 既存の最先端アルゴリズムと比較して, LU分解における非ゼロ数が少なくなることがわかった。
- 参考スコア（独自算出の注目度）: 1.4106487975820565
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: A large number of computational and scientific methods commonly require
decomposing a sparse matrix into triangular factors as LU decomposition. A
common problem faced during this decomposition is that even though the given
matrix may be very sparse, the decomposition may lead to a denser triangular
factors due to fill-in. A significant fill-in may lead to prohibitively larger
computational costs and memory requirement during decomposition as well as
during the solve phase. To this end, several heuristic sparse matrix reordering
methods have been proposed to reduce fill-in before the decomposition. However,
finding an optimal reordering algorithm that leads to minimal fill-in during
such decomposition is known to be a NP-hard problem. A reinforcement learning
based approach is proposed for this problem. The sparse matrix reordering
problem is formulated as a single player game. More specifically, Monte-Carlo
tree search in combination with neural network is used as a decision making
algorithm to search for the best move in our game. The proposed method,
alphaElimination is found to produce significantly lesser non-zeros in the LU
decomposition as compared to existing state-of-the-art heuristic algorithms
with little to no increase in overall running time of the algorithm. The code
for the project will be publicly available
here\footnote{\url{https://github.com/misterpawan/alphaEliminationPaper}}.
- Abstract（参考訳）: 多くの計算および科学的手法では、一般に LU 分解としてスパース行列を三角要素に分解する必要がある。
この分解の間に直面する一般的な問題は、与えられた行列が非常にスパースであるとしても、分解は充填によってより密な三角因子をもたらす可能性があることである。
重要な補充は、分解時や解法段階での計算コストとメモリ要求を著しく増大させる可能性がある。
この目的のために、分解前の補充を減らすために、いくつかのヒューリスティックスパース行列再構成法が提案されている。
しかし、そのような分解の際の最小の補充につながる最適再順序アルゴリズムを見つけることはNPハード問題であることが知られている。
この問題に対して強化学習に基づくアプローチを提案する。
スパース行列のリオーダー問題は単一プレイヤーゲームとして定式化される。
より具体的には、ニューラルネットワークと組み合わせたモンテカルロ木探索は、我々のゲームで最高の動きを探すための決定アルゴリズムとして使用される。
提案手法であるアルファエリミネーションは,アルゴリズム全体の実行時間をほとんど増減させることなく,既存の最先端ヒューリスティックアルゴリズムに比べ,lu分解の非零度が有意に小さいことが判明した。
プロジェクトのコードは、github.com/misterpawan/alphaeliminationpaper}}で公開されている。
関連論文リスト
- An Efficient Algorithm for Clustered Multi-Task Compressive Sensing [60.70532293880842]
クラスタ化マルチタスク圧縮センシングは、複数の圧縮センシングタスクを解決する階層モデルである。
このモデルに対する既存の推論アルゴリズムは計算コストが高く、高次元ではうまくスケールしない。
本稿では,これらの共分散行列を明示的に計算する必要をなくし,モデル推論を大幅に高速化するアルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-09-30T15:57:14Z) - Learning the Positions in CountSketch [49.57951567374372]
本稿では,まずランダムなスケッチ行列に乗じてデータを圧縮し,最適化問題を高速に解くスケッチアルゴリズムについて検討する。
本研究では,ゼロでないエントリの位置を最適化する学習ベースアルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-06-11T07:28:35Z) - A fast Multiplicative Updates algorithm for Non-negative Matrix Factorization [2.646309221150203]
本稿では,各サブプロブレムに対してヘッセン行列のより厳密な上界を構築することにより,乗法更新アルゴリズムの改善を提案する。
コンバージェンスはまだ保証されており、我々は実際に合成と実世界の両方のデータセットで、提案したfastMUアルゴリズムが通常の乗算更新アルゴリズムよりも数桁高速であることを示す。
論文 参考訳（メタデータ） (2023-03-31T12:09:36Z) - High-Dimensional Sparse Bayesian Learning without Covariance Matrices [66.60078365202867]
共分散行列の明示的な構成を避ける新しい推論手法を提案する。
本手法では, 数値線形代数と共役勾配アルゴリズムの対角線推定結果とを結合する。
いくつかのシミュレーションにおいて,本手法は計算時間とメモリにおける既存手法よりも拡張性が高い。
論文 参考訳（メタデータ） (2022-02-25T16:35:26Z) - Near-Optimal Algorithms for Linear Algebra in the Current Matrix
Multiplication Time [46.31710224483631]
既存の定数係数近似のスケッチ次元における対数的要素について、Nelson and Nguyen (FOCS, 2013) の主な開問題を回避する方法を示す。
私たちが使用している重要なテクニックは、不確実性原理と抽出子に基づくIndykの明示的なマッピングです。
ランク計算と列の線形独立部分集合の探索という基本的な問題に対して、我々のアルゴリズムはCheung, Kwok, Lau (JACM, 2013)を改良し、それぞれ定数係数と$log(n)$-factorの範囲内で最適である。
論文 参考訳（メタデータ） (2021-07-16T19:34:10Z) - Solving weakly supervised regression problem using low-rank manifold
regularization [77.34726150561087]
我々は弱い教師付き回帰問題を解く。
weakly"の下では、いくつかのトレーニングポイントではラベルが知られ、未知のものもあれば、無作為なノイズの存在やリソースの欠如などの理由によって不確かであることが分かっています。
数値的な節ではモンテカルロモデルを用いて提案手法を人工と実のデータセットに適用した。
論文 参考訳（メタデータ） (2021-04-13T23:21:01Z) - Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。
問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。
本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-01-07T08:00:02Z) - Ranky : An Approach to Solve Distributed SVD on Large Sparse Matrices [0.0]
特異値分解(SVD)は、多くの分野や応用分野においてよく研究されている研究トピックである。
そこで我々は,大小行列のランク問題を分散的に解く手法であるRandyを提案する。
論文 参考訳（メタデータ） (2020-09-21T11:36:28Z) - QR and LQ Decomposition Matrix Backpropagation Algorithms for Square,
Wide, and Deep -- Real or Complex -- Matrices and Their Software
Implementation [0.0]
この記事では、正方形(m = n)、幅(m n)、深さ(m > n)のいずれかの行列のQR分解に対する行列バックプロパゲーションアルゴリズムを、階数$k = min(m, n)$で提示する。
我々は, ピボット(フルランク)QR分解と深部入力行列のLQ分解のための新しい行列バックプロパゲーション結果を得た。
論文 参考訳（メタデータ） (2020-09-19T21:03:37Z) - Lagrangian Decomposition for Neural Network Verification [148.0448557991349]
ニューラルネットワーク検証の基本的なコンポーネントは、出力が取ることのできる値のバウンダリの計算である。
ラグランジアン分解に基づく新しい手法を提案する。
ランニングタイムのごく一部で、既成の解法に匹敵するバウンダリが得られることを示す。
論文 参考訳（メタデータ） (2020-02-24T17:55:10Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。