論文の概要: Binary Matrix Factorisation and Completion via Integer Programming
- arxiv url: http://arxiv.org/abs/2106.13434v1
- Date: Fri, 25 Jun 2021 05:17:51 GMT
- ステータス: 処理完了
- システム内更新日: 2021-06-28 12:54:20.241092
- Title: Binary Matrix Factorisation and Completion via Integer Programming
- Title（参考訳）: 整数プログラミングによるバイナリ行列の分解と補完
- Authors: Reka A. Kovacs, Oktay Gunluk, Raphael A. Hauser
- Abstract要約: ランク-k二元行列分解問題(k-BMF)に対するコンパクトかつ2つの指数サイズの整数プログラム(IP)を提案する。
コンパクトIPはLP緩和が弱いのに対し,指数サイズのLPはLP緩和が強いことを示す。
- 参考スコア（独自算出の注目度）: 3.4376560669160394
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Binary matrix factorisation is an essential tool for identifying discrete
patterns in binary data. In this paper we consider the rank-k binary matrix
factorisation problem (k-BMF) under Boolean arithmetic: we are given an n x m
binary matrix X with possibly missing entries and need to find two binary
matrices A and B of dimension n x k and k x m respectively, which minimise the
distance between X and the Boolean product of A and B in the squared Frobenius
distance. We present a compact and two exponential size integer programs (IPs)
for k-BMF and show that the compact IP has a weak LP relaxation, while the
exponential size LPs have a stronger equivalent LP relaxation. We introduce a
new objective function, which differs from the traditional squared Frobenius
objective in attributing a weight to zero entries of the input matrix that is
proportional to the number of times the zero is erroneously covered in a rank-k
factorisation. For one of the exponential size IPs we describe a computational
approach based on column generation. Experimental results on synthetic and real
word datasets suggest that our integer programming approach is competitive
against available methods for k-BMF and provides accurate low-error
factorisations.
- Abstract（参考訳）: binary matrix factorizationは、バイナリデータの離散的なパターンを識別するための必須のツールである。
本稿では,次数-k二進行列分解問題 (k-BMF) をブール算術の下で考慮し,nxm二進行列 X が欠落する可能性があり,それぞれ nxk と kxm の 2 つの二進行列 A と B を見出すことで,X と A と B の距離を2乗フロベニウス距離で最小化する。
我々はk-BMF用のコンパクトかつ2つの指数サイズの整数プログラム(IP)を提案し、コンパクトIPはLP緩和が弱い一方、指数サイズのLPはLP緩和が強いことを示す。
従来の2乗フロベニウスの目的と異なり、ゼロがランク-k因子化で誤ってカバーされる回数に比例する入力行列の零エントリに重みを割り当てる新たな目的関数を導入する。
指数サイズのIPの1つについて,列生成に基づく計算手法について述べる。
合成および実単語データセットの実験結果から,我々の整数プログラミング手法はk-BMFの利用可能な手法と競合し,精度の高い低エラー因数分解を提供することが示された。
関連論文リスト
- Entrywise error bounds for low-rank approximations of kernel matrices [55.524284152242096]
切り抜き固有分解を用いて得られたカーネル行列の低ランク近似に対するエントリーワイド誤差境界を導出する。
重要な技術的革新は、小さな固有値に対応するカーネル行列の固有ベクトルの非局在化結果である。
我々は、合成および実世界のデータセットの集合に関する実証的研究により、我々の理論を検証した。
論文 参考訳（メタデータ） (2024-05-23T12:26:25Z) - Recovering Simultaneously Structured Data via Non-Convex Iteratively
Reweighted Least Squares [0.8702432681310401]
線形観測から多種多様低次元構造に固執するデータを復元する新しいアルゴリズムを提案する。
IRLS法は,低/複合状態の計測に好適であることを示す。
論文 参考訳（メタデータ） (2023-06-08T06:35:47Z) - Algorithms for Boolean Matrix Factorization using Integer Programming [20.13379783488932]
BMFの1因子行列におけるサブプロブレムを解くための交互最適化(AO)戦略を提案する。
BMFの複数の解が、他のIPを用いて最適に組み合わせられるかを示す。
実験の結果,我々のアルゴリズムは中規模問題における技術状況よりも優れていた。
論文 参考訳（メタデータ） (2023-05-17T13:09:23Z) - 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) - High-Dimensional Sparse Bayesian Learning without Covariance Matrices [66.60078365202867]
共分散行列の明示的な構成を避ける新しい推論手法を提案する。
本手法では, 数値線形代数と共役勾配アルゴリズムの対角線推定結果とを結合する。
いくつかのシミュレーションにおいて,本手法は計算時間とメモリにおける既存手法よりも拡張性が高い。
論文 参考訳（メタデータ） (2022-02-25T16:35:26Z) - 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) - 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) - Boolean Matrix Factorization with SAT and MaxSAT [6.85316573653194]
我々のアプローチは、合理的な時間を保ちながら、既存のアプローチよりも優れた分解を可能にすることを示しています。
提案手法により,不完全行列の扱いも可能となる。
論文 参考訳（メタデータ） (2021-06-18T12:57:46Z) - Hybrid Trilinear and Bilinear Programming for Aligning Partially
Overlapping Point Sets [85.71360365315128]
多くの応用において、部分重なり合う点集合が対応するRPMアルゴリズムに不変であるようなアルゴリズムが必要である。
まず、目的が立方体有界関数であることを示し、次に、三線型および双線型単相変換の凸エンベロープを用いて、その下界を導出する。
次に、変換変数上の分岐のみを効率よく実行するブランチ・アンド・バウンド(BnB)アルゴリズムを開発する。
論文 参考訳（メタデータ） (2021-01-19T04:24:23Z) - Sparse PCA via $l_{2,p}$-Norm Regularization for Unsupervised Feature
Selection [138.97647716793333]
再構成誤差を$l_2,p$ノルム正規化と組み合わせることで,単純かつ効率的な特徴選択手法を提案する。
提案する非教師付きモデルを解くための効率的な最適化アルゴリズムを提案し,アルゴリズムの収束と計算の複雑さを理論的に解析する。
論文 参考訳（メタデータ） (2020-12-29T04:08:38Z) - Binary Matrix Factorisation via Column Generation [6.445605125467574]
本稿では,算術における低ランク二乗行列分解(BMF)の問題点について考察する。
混合整数線形プログラムとして問題を定式化し、列生成の大規模最適化手法を用いて解決する。
実世界のデータセットを用いた実験結果から,提案手法は高精度な因数分解を実現するのに有効であることが示された。
論文 参考訳（メタデータ） (2020-11-09T14:27:36Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。