論文の概要: Algorithms for Boolean Matrix Factorization using Integer Programming

• arxiv url: http://arxiv.org/abs/2305.10185v1
• Date: Wed, 17 May 2023 13:09:23 GMT
• ステータス: 処理完了
• システム内更新日: 2023-05-18 15:58:06.472438
• Title: Algorithms for Boolean Matrix Factorization using Integer Programming
• Title（参考訳）: 整数計画を用いたブール行列分解のアルゴリズム
• Authors: Christos Kolomvakis, Arnaud Vandaele, Nicolas Gillis
• Abstract要約: BMFの1因子行列におけるサブプロブレムを解くための交互最適化(AO)戦略を提案する。 BMFの複数の解が、他のIPを用いて最適に組み合わせられるかを示す。 実験の結果,我々のアルゴリズムは中規模問題における技術状況よりも優れていた。
• 参考スコア（独自算出の注目度）: 20.13379783488932
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Boolean matrix factorization (BMF) approximates a given binary input matrix as the product of two smaller binary factors. As opposed to binary matrix factorization which uses standard arithmetic, BMF uses the Boolean OR and Boolean AND operations to perform matrix products, which leads to lower reconstruction errors. BMF is an NP-hard problem. In this paper, we first propose an alternating optimization (AO) strategy that solves the subproblem in one factor matrix in BMF using an integer program (IP). We also provide two ways to initialize the factors within AO. Then, we show how several solutions of BMF can be combined optimally using another IP. This allows us to come up with a new algorithm: it generates several solutions using AO and then combines them in an optimal way. Experiments show that our algorithms (available on gitlab) outperform the state of the art on medium-scale problems.
• Abstract（参考訳）: ブール行列分解(BMF)は、2つのより小さな二項係数の積として与えられた二項入力行列を近似する。 標準的な算術を使用するバイナリ行列分解とは対照的に、BMFはBoolean OR と Boolean AND 演算を使用して行列生成を行う。 BMFはNPハード問題である。 本稿では,まず整数型プログラム(ip)を用いて,bmfの一因子行列における部分問題を解く交互最適化(ao)戦略を提案する。 また、AO内の因子を初期化する2つの方法も提供します。 そして,他のIPを用いてBMFの複数の解を最適に組み合わせる方法を示す。 これにより、AOを使って複数のソリューションを生成し、それらを最適な方法で組み合わせることで、新しいアルゴリズムを思いつくことができます。 実験の結果,我々のアルゴリズム(gitlabで利用可能)は,中規模問題における技術状況よりも優れていた。

関連論文リスト

• Randomized Algorithms for Symmetric Nonnegative Matrix Factorization [2.1753766244387402]
  対称非負行列因子化(SymNMF)は、データ解析と機械学習における技術である。 計算のためのランダム化アルゴリズムを2つ開発した。 提案手法は, 解法の品質を概ね維持し, 大規模疎水化問題と大規模疎水化問題の両方に対して, 大幅な高速化を実現する。
  論文  参考訳（メタデータ） (2024-02-13T00:02:05Z)
• Accelerating Cutting-Plane Algorithms via Reinforcement Learning Surrogates [49.84541884653309]
  凸離散最適化問題に対する現在の標準的なアプローチは、カットプレーンアルゴリズムを使うことである。 多くの汎用カット生成アルゴリズムが存在するにもかかわらず、大規模な離散最適化問題は、難易度に悩まされ続けている。 そこで本研究では,強化学習による切削平面アルゴリズムの高速化手法を提案する。
  論文  参考訳（メタデータ） (2023-07-17T20:11:56Z)
• Boolean and $\mathbb{F}_p$-Matrix Factorization: From Theory to Practice [3.658952625899939]
  我々は$mathbbF_p$-Matrix Factorizationのための新しいアルゴリズムを開発した。 EPTAS for BMFは純粋に理論上の進歩である。 また、この戦略を用いて、関連する$mathbbF_p$-Matrix Factorizationのための新しいアルゴリズムを開発する。
  論文  参考訳（メタデータ） (2022-07-25T06:05:12Z)
• Fast Differentiable Matrix Square Root and Inverse Square Root [65.67315418971688]
  微分可能な行列平方根と逆平方根を計算するためのより効率的な2つの変種を提案する。 前方伝搬には, Matrix Taylor Polynomial (MTP) を用いる方法と, Matrix Pad'e Approximants (MPA) を使用する方法がある。 一連の数値実験により、両方の手法がSVDやNSの繰り返しと比較してかなりスピードアップすることが示された。
  論文  参考訳（メタデータ） (2022-01-29T10:00:35Z)
• Binary Matrix Factorisation and Completion via Integer Programming [3.4376560669160394]
  ランク-k二元行列分解問題(k-BMF)に対するコンパクトかつ2つの指数サイズの整数プログラム(IP)を提案する。 コンパクトIPはLP緩和が弱いのに対し,指数サイズのLPはLP緩和が強いことを示す。
  論文  参考訳（メタデータ） (2021-06-25T05:17:51Z)
• Boolean Matrix Factorization with SAT and MaxSAT [6.85316573653194]
  我々のアプローチは、合理的な時間を保ちながら、既存のアプローチよりも優れた分解を可能にすることを示しています。 提案手法により,不完全行列の扱いも可能となる。
  論文  参考訳（メタデータ） (2021-06-18T12:57:46Z)
• Boolean Matrix Factorization via Nonnegative Auxiliary Optimization [0.5459797813771498]
  BMF問題を直接解く代わりに、補助行列上の制約で非負の最適化問題を解く。 二つの解空間の同値性の証明を、厳密な解の存在下で提供する。 アルゴリズムの有効性と複雑さを示すために,合成データセットと実データセットの実験を行った。
  論文  参考訳（メタデータ） (2021-06-08T21:55:49Z)
• Provably Faster Algorithms for Bilevel Optimization [54.83583213812667]
  バイレベル最適化は多くの重要な機械学習アプリケーションに広く適用されている。 両レベル最適化のための2つの新しいアルゴリズムを提案する。 両アルゴリズムが$mathcalO(epsilon-1.5)$の複雑さを達成し,既存のアルゴリズムを桁違いに上回っていることを示す。
  論文  参考訳（メタデータ） (2021-06-08T21:05:30Z)
• Self-supervised Symmetric Nonnegative Matrix Factorization [82.59905231819685]
  シンメトリー非負係数行列(SNMF)は、データクラスタリングの強力な方法であることを示した。 より良いクラスタリング結果を求めるアンサンブルクラスタリングにインスパイアされた,自己監視型SNMF(S$3$NMF)を提案する。 SNMFのコード特性に対する感度を、追加情報に頼らずに活用しています。
  論文  参考訳（メタデータ） (2021-03-02T12:47:40Z)
• Hybrid Trilinear and Bilinear Programming for Aligning Partially Overlapping Point Sets [85.71360365315128]
  多くの応用において、部分重なり合う点集合が対応するRPMアルゴリズムに不変であるようなアルゴリズムが必要である。 まず、目的が立方体有界関数であることを示し、次に、三線型および双線型単相変換の凸エンベロープを用いて、その下界を導出する。 次に、変換変数上の分岐のみを効率よく実行するブランチ・アンド・バウンド(BnB)アルゴリズムを開発する。
  論文  参考訳（メタデータ） (2021-01-19T04:24:23Z)
• 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)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。