論文の概要: Boolean and $\mathbb{F}_p$-Matrix Factorization: From Theory to Practice
- arxiv url: http://arxiv.org/abs/2207.11917v1
- Date: Mon, 25 Jul 2022 06:05:12 GMT
- ステータス: 処理完了
- システム内更新日: 2022-07-26 13:56:02.305565
- Title: Boolean and $\mathbb{F}_p$-Matrix Factorization: From Theory to Practice
- Title（参考訳）: Boolean と $\mathbb{F}_p$-Matrix Factorization:理論から実践へ
- Authors: Fedor Fomin, Fahad Panolan, Anurag Patil, Adil Tanveer
- Abstract要約: 我々は$mathbbF_p$-Matrix Factorizationのための新しいアルゴリズムを開発した。
EPTAS for BMFは純粋に理論上の進歩である。
また、この戦略を用いて、関連する$mathbbF_p$-Matrix Factorizationのための新しいアルゴリズムを開発する。
- 参考スコア（独自算出の注目度）: 3.658952625899939
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Boolean Matrix Factorization (BMF) aims to find an approximation of a given
binary matrix as the Boolean product of two low-rank binary matrices. Binary
data is ubiquitous in many fields, and representing data by binary matrices is
common in medicine, natural language processing, bioinformatics, computer
graphics, among many others. Unfortunately, BMF is computationally hard and
heuristic algorithms are used to compute Boolean factorizations. Very recently,
the theoretical breakthrough was obtained independently by two research groups.
Ban et al. (SODA 2019) and Fomin et al. (Trans. Algorithms 2020) show that BMF
admits an efficient polynomial-time approximation scheme (EPTAS). However,
despite the theoretical importance, the high double-exponential dependence of
the running times from the rank makes these algorithms unimplementable in
practice. The primary research question motivating our work is whether the
theoretical advances on BMF could lead to practical algorithms.
The main conceptional contribution of our work is the following. While EPTAS
for BMF is a purely theoretical advance, the general approach behind these
algorithms could serve as the basis in designing better heuristics. We also use
this strategy to develop new algorithms for related $\mathbb{F}_p$-Matrix
Factorization. Here, given a matrix $A$ over a finite field GF($p$) where $p$
is a prime, and an integer $r$, our objective is to find a matrix $B$ over the
same field with GF($p$)-rank at most $r$ minimizing some norm of $A-B$. Our
empirical research on synthetic and real-world data demonstrates the advantage
of the new algorithms over previous works on BMF and $\mathbb{F}_p$-Matrix
Factorization.
- Abstract（参考訳）: ブール行列分解 (BMF) は、2つの低ランク二項行列のブール積として与えられた二項行列の近似を求める。
バイナリデータは、多くの分野においてユビキタスであり、医学、自然言語処理、バイオインフォマティクス、コンピュータグラフィックスなどでは、バイナリ行列によるデータの表現が一般的である。
残念ながら、bmfは計算が難しく、ヒューリスティックなアルゴリズムはブール分解を計算するために使われる。
近年、理論的なブレークスルーは2つの研究グループによって独立に得られた。
Ban et al. (SODA 2019) と Fomin et al. (Trans. Algorithms 2020) は、BMFが効率的な多項式時間近似スキーム(EPTAS)を認めていることを示している。
しかし、理論的な重要性にもかかわらず、ランタイムをランクから高い倍指数で依存しているため、これらのアルゴリズムは実際に実装できない。
我々の研究を動機づける主要な研究課題は、BMFの理論的進歩が実用的なアルゴリズムに繋がるかどうかである。
私たちの作品の主な概念的貢献は次のとおりである。
EPTAS for BMFは純粋に理論的に進歩しているが、これらのアルゴリズムの背後にある一般的なアプローチはより優れたヒューリスティックな設計の基礎となる。
また、この戦略を用いて、関連する$\mathbb{F}_p$-Matrix Factorizationの新しいアルゴリズムを開発する。
ここで、有限体 gf($p$) 上の行列 $a$ が与えられたとき、ここでは $p$ は素数、整数 $r$ である。
合成および実世界のデータに関する経験的研究は、bmfおよび$\mathbb{f}_p$-matrix因子化に対する新しいアルゴリズムの利点を示しています。
関連論文リスト
- Optimized Inference for 1.58-bit LLMs: A Time and Memory-Efficient Algorithm for Binary and Ternary Matrix Multiplication [8.779871128906787]
大規模言語モデル(LLM)は、高度な計算インフラに依存しながら推論の非効率さに悩まされる。
3次重み付き1.58ビットLLMの推論時間とメモリ効率を改善するアルゴリズムを提案する。
その結果,時間とメモリの両面でのアプローチの優位性が確認され,推論時間は最大29倍,メモリ使用量は最大6倍に短縮された。
論文 参考訳（メタデータ） (2024-11-10T04:56:14Z) - Efficient Frameworks for Generalized Low-Rank Matrix Bandit Problems [61.85150061213987]
一般化線形モデル (GLM) フレームワークを用いて, citelu2021low で提案した一般化低ランク行列帯域問題について検討する。
既存のアルゴリズムの計算不可能性と理論的制約を克服するため,まずG-ESTTフレームワークを提案する。
G-ESTT は $tildeO(sqrt(d_1+d_2)3/2Mr3/2T)$ bound of regret を達成でき、G-ESTS は $tildeO を達成できることを示す。
論文 参考訳（メタデータ） (2024-01-14T14:14:19Z) - A Unified Scheme of ResNet and Softmax [8.556540804058203]
回帰問題を理論的に解析する: $| langle exp(Ax) + A x, bf 1_n rangle-1 ( exp(Ax) + Ax )
この回帰問題は、ソフトマックス回帰とResNetを組み合わせた統一的なスキームである。
論文 参考訳（メタデータ） (2023-09-23T21:41:01Z) - Algorithms for Boolean Matrix Factorization using Integer Programming [20.13379783488932]
BMFの1因子行列におけるサブプロブレムを解くための交互最適化(AO)戦略を提案する。
BMFの複数の解が、他のIPを用いて最適に組み合わせられるかを示す。
実験の結果,我々のアルゴリズムは中規模問題における技術状況よりも優れていた。
論文 参考訳（メタデータ） (2023-05-17T13:09:23Z) - Binary Matrix Factorisation and Completion via Integer Programming [3.4376560669160394]
ランク-k二元行列分解問題(k-BMF)に対するコンパクトかつ2つの指数サイズの整数プログラム(IP)を提案する。
コンパクトIPはLP緩和が弱いのに対し,指数サイズのLPはLP緩和が強いことを示す。
論文 参考訳（メタデータ） (2021-06-25T05:17:51Z) - Minimax Optimization with Smooth Algorithmic Adversaries [59.47122537182611]
対戦相手が展開するスムーズなアルゴリズムに対して,Min-playerの新しいアルゴリズムを提案する。
本アルゴリズムは,制限周期のない単調進行を保証し,適切な勾配上昇数を求める。
論文 参考訳（メタデータ） (2021-06-02T22:03:36Z) - Self-supervised Symmetric Nonnegative Matrix Factorization [82.59905231819685]
シンメトリー非負係数行列(SNMF)は、データクラスタリングの強力な方法であることを示した。
より良いクラスタリング結果を求めるアンサンブルクラスタリングにインスパイアされた,自己監視型SNMF(S$3$NMF)を提案する。
SNMFのコード特性に対する感度を、追加情報に頼らずに活用しています。
論文 参考訳（メタデータ） (2021-03-02T12:47:40Z) - Quantum algorithms for spectral sums [50.045011844765185]
正半定値行列(PSD)のスペクトル和を推定するための新しい量子アルゴリズムを提案する。
本稿では, スペクトルグラフ理論における3つの問題に対して, アルゴリズムと手法が適用可能であることを示す。
論文 参考訳（メタデータ） (2020-11-12T16:29:45Z) - Positive Semidefinite Matrix Factorization: A Connection with Phase
Retrieval and Affine Rank Minimization [71.57324258813674]
位相探索(PR)とアフィンランク最小化(ARM)アルゴリズムに基づいてPSDMFアルゴリズムを設計可能であることを示す。
このアイデアに触発され、反復的ハードしきい値(IHT)に基づくPSDMFアルゴリズムの新たなファミリーを導入する。
論文 参考訳（メタデータ） (2020-07-24T06:10:19Z) - Constant-Depth and Subcubic-Size Threshold Circuits for Matrix
Multiplication [1.9518237361775532]
大規模ニューラルネットワークハードウェアの最近の進歩は、その実践的実装を短期的可能性にしている。
しきい値ゲート論理を統合する2つの$N$を$N$行列に乗算する理論的アプローチについて述べる。
デンス行列乗算は畳み込みニューラルネットワークトレーニングにおけるコア演算である。
論文 参考訳（メタデータ） (2020-06-25T18:28:10Z) - Provably Efficient Reinforcement Learning for Discounted MDPs with
Feature Mapping [99.59319332864129]
本稿では,割引決定(MDP)のための強化学習について検討する。
本稿では,特徴写像を利用した新しいアルゴリズムを提案し,$tilde O(dsqrtT/ (1-gamma)2)$ regretを求める。
以上の結果から,提案した強化学習アルゴリズムは,最大1-γ-0.5$の係数でほぼ最適であることが示唆された。
論文 参考訳（メタデータ） (2020-06-23T17:08:54Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。