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

• arxiv url: http://arxiv.org/abs/2512.03807v1
• Date: Wed, 03 Dec 2025 13:55:54 GMT
• ステータス: 情報取得中
• システム内更新日: 2025-12-04 12:11:29.449668
• Title: Algorithms for Boolean Matrix Factorization using Integer Programming and Heuristics
• Title（参考訳）: 整数計画法とヒューリスティックスを用いたブール行列分解アルゴリズム
• Authors: Christos Kolomvakis, Thomas Bobille, Arnaud Vandaele, Nicolas Gillis,
• Abstract要約: BMFは与えられたバイナリ入力行列を2つのより小さなバイナリ要素の積として近似する。 標準的な算術に基づく二項行列分解とは異なり、BMFはブールORと行列積の演算を用いる。 役割マイニングやコンピュータビジョンにも用いられている。
• 参考スコア（独自算出の注目度）: 11.53912933736867
• License:
• Abstract: Boolean matrix factorization (BMF) approximates a given binary input matrix as the product of two smaller binary factors. Unlike binary matrix factorization based on standard arithmetic, BMF employs the Boolean OR and AND operations for the matrix product, which improves interpretability and reduces the approximation error. It is also used in role mining and computer vision. In this paper, we first propose algorithms for BMF that perform alternating optimization (AO) of the factor matrices, where each subproblem is solved via integer programming (IP). We then design different approaches to further enhance AO-based algorithms by selecting an optimal subset of rank-one factors from multiple runs. To address the scalability limits of IP-based methods, we introduce new greedy and local-search heuristics. We also construct a new C++ data structure for Boolean vectors and matrices that is significantly faster than existing ones and is of independent interest, allowing our heuristics to scale to large datasets. We illustrate the performance of all our proposed methods and compare them with the state of the art on various real datasets, both with and without missing data, including applications in topic modeling and imaging.
• Abstract（参考訳）: ブール行列分解(BMF)は、2つのより小さな二項係数の積として与えられた二項入力行列を近似する。 標準的な算術に基づく二項行列分解とは異なり、BMFはBoolean ORおよびAND演算を行列積に採用し、解釈性を改善し、近似誤差を低減する。 役割マイニングやコンピュータビジョンにも用いられている。 本稿ではまず,パラメータ行列の交互最適化(AO)を行うBMFのアルゴリズムを提案する。 次に、複数の実行からランク1因子の最適なサブセットを選択することにより、AOベースのアルゴリズムをさらに強化するための異なるアプローチを設計する。 IPベースの手法のスケーラビリティ限界に対処するため、我々は新しい欲求と局所探索ヒューリスティックスを導入する。 また、Booleanベクトルと行列のための新しいC++データ構造を構築し、既存のものよりも大幅に高速で、独立した関心を持つので、ヒューリスティックスを大規模データセットに拡張することができます。 提案手法のすべての性能を概説し、トピックモデリングや画像撮影への応用を含む、欠落データと欠落データの両方を含む、様々な実データにおける最先端の手法と比較する。

関連論文リスト

• MatRL: Provably Generalizable Iterative Algorithm Discovery via Monte-Carlo Tree Search [37.24058519921229]
  MatRLは、行列関数を計算するための反復アルゴリズムを自動的に発見する強化学習フレームワークである。 そこで本研究では,MateRLが文献の様々なベースラインを上回るアルゴリズムを生成することを示す。
  論文  参考訳（メタデータ） (2025-07-04T22:57:33Z)
• An Efficient Algorithm for Clustered Multi-Task Compressive Sensing [60.70532293880842]
  クラスタ化マルチタスク圧縮センシングは、複数の圧縮センシングタスクを解決する階層モデルである。 このモデルに対する既存の推論アルゴリズムは計算コストが高く、高次元ではうまくスケールしない。 本稿では,これらの共分散行列を明示的に計算する必要をなくし,モデル推論を大幅に高速化するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-09-30T15:57:14Z)
• Algorithms for Boolean Matrix Factorization using Integer Programming [20.13379783488932]
  BMFの1因子行列におけるサブプロブレムを解くための交互最適化(AO)戦略を提案する。 BMFの複数の解が、他のIPを用いて最適に組み合わせられるかを示す。 実験の結果,我々のアルゴリズムは中規模問題における技術状況よりも優れていた。
  論文  参考訳（メタデータ） (2023-05-17T13:09:23Z)
• A Second-Order Majorant Algorithm for Nonnegative Matrix Factorization [2.646309221150203]
  我々はNMFの2次最適化フレームワークを2次および$beta$-divergence損失関数の両方で導入する。 第二次行列 (SOM) は、ロス関数の局所的な二次的二次化をヘッセン行列の二次化によって構成する。 我々はmSOMが複数の損失関数にまたがる最先端のアルゴリズムより一貫して優れていることを示す。
  論文  参考訳（メタデータ） (2023-03-31T12:09:36Z)
• Asymmetric Scalable Cross-modal Hashing [51.309905690367835]
  クロスモーダルハッシュは、大規模なマルチメディア検索問題を解決する方法として成功している。 これらの問題に対処する新しい非対称スケーラブルクロスモーダルハッシュ(ASCMH)を提案する。 我々のASCMHは、最先端のクロスモーダルハッシュ法よりも精度と効率の点で優れています。
  論文  参考訳（メタデータ） (2022-07-26T04:38:47Z)
• Lossy compression of matrices by black-box optimisation of mixed-integer non-linear programming [1.1066593559733056]
  エッジコンピューティングでは、データサイズを抑制することは、自律運転のような複雑なタスクを実行する機械学習モデルの課題である。 行列データの効率的な損失圧縮は、それを整数と実行列の積に分解することで実現されている。 本稿では,最近開発された整数変数に対するIsingソルバを用いたブラックボックス最適化アルゴリズムを利用して,この最適化を改善する。
  論文  参考訳（メタデータ） (2022-04-22T08:58:36Z)
• Unfolding Projection-free SDP Relaxation of Binary Graph Classifier via GDPA Linearization [59.87663954467815]
  アルゴリズムの展開は、モデルベースのアルゴリズムの各イテレーションをニューラルネットワーク層として実装することにより、解釈可能で類似のニューラルネットワークアーキテクチャを生成する。 本稿では、Gershgorin disc perfect alignment (GDPA)と呼ばれる最近の線形代数定理を利用して、二進グラフの半定値プログラミング緩和(SDR)のためのプロジェクションフリーアルゴリズムをアンロールする。 実験結果から,我々の未学習ネットワークは純粋モデルベースグラフ分類器よりも優れ,純粋データ駆動ネットワークに匹敵する性能を示したが,パラメータははるかに少なかった。
  論文  参考訳（メタデータ） (2021-09-10T07:01:15Z)
• Binary Matrix Factorisation and Completion via Integer Programming [3.4376560669160394]
  ランク-k二元行列分解問題(k-BMF)に対するコンパクトかつ2つの指数サイズの整数プログラム(IP)を提案する。 コンパクトIPはLP緩和が弱いのに対し,指数サイズのLPはLP緩和が強いことを示す。
  論文  参考訳（メタデータ） (2021-06-25T05:17:51Z)
• Provably Faster Algorithms for Bilevel Optimization [54.83583213812667]
  バイレベル最適化は多くの重要な機械学習アプリケーションに広く適用されている。 両レベル最適化のための2つの新しいアルゴリズムを提案する。 両アルゴリズムが$mathcalO(epsilon-1.5)$の複雑さを達成し,既存のアルゴリズムを桁違いに上回っていることを示す。
  論文  参考訳（メタデータ） (2021-06-08T21:05:30Z)
• Sparse PCA via $l_{2,p}$-Norm Regularization for Unsupervised Feature Selection [138.97647716793333]
  再構成誤差を$l_2,p$ノルム正規化と組み合わせることで,単純かつ効率的な特徴選択手法を提案する。 提案する非教師付きモデルを解くための効率的な最適化アルゴリズムを提案し,アルゴリズムの収束と計算の複雑さを理論的に解析する。
  論文  参考訳（メタデータ） (2020-12-29T04:08:38Z)
• Multi-View Spectral Clustering with High-Order Optimal Neighborhood Laplacian Matrix [57.11971786407279]
  マルチビュースペクトルクラスタリングは、データ間の固有のクラスタ構造を効果的に明らかにすることができる。 本稿では,高次最適近傍ラプラシア行列を学習するマルチビュースペクトルクラスタリングアルゴリズムを提案する。 提案アルゴリズムは, 1次ベースと高次ベースの両方の線形結合の近傍を探索し, 最適ラプラシア行列を生成する。
  論文  参考訳（メタデータ） (2020-08-31T12:28:40Z)

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

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