論文の概要: Binary matrix factorization on special purpose hardware
- arxiv url: http://arxiv.org/abs/2010.08693v2
- Date: Fri, 7 Jan 2022 15:12:25 GMT
- ステータス: 処理完了
- システム内更新日: 2022-10-06 12:23:31.354719
- Title: Binary matrix factorization on special purpose hardware
- Title（参考訳）: 特殊目的ハードウェア上の二元行列分解
- Authors: Osman Asif Malik, Hayato Ushijima-Mwesigwa, Arnab Roy, Avradip Mandal,
Indradeep Ghosh
- Abstract要約: データマイニングに多くの応用がある重要なバイナリ行列分解(BMF)問題に焦点をあてる。
BMFのための2つのQUBO定式化を提案し、これらの定式化にクラスタリング制約をどのように組み込むかを示す。
また,いくつかの状況において,より洗練された手法よりも優れた単純なベースラインアルゴリズムを提案する。
- 参考スコア（独自算出の注目度）: 5.926928436252818
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Many fundamental problems in data mining can be reduced to one or more
NP-hard combinatorial optimization problems. Recent advances in novel
technologies such as quantum and quantum-inspired hardware promise a
substantial speedup for solving these problems compared to when using general
purpose computers but often require the problem to be modeled in a special
form, such as an Ising or quadratic unconstrained binary optimization (QUBO)
model, in order to take advantage of these devices. In this work, we focus on
the important binary matrix factorization (BMF) problem which has many
applications in data mining. We propose two QUBO formulations for BMF. We show
how clustering constraints can easily be incorporated into these formulations.
The special purpose hardware we consider is limited in the number of variables
it can handle which presents a challenge when factorizing large matrices. We
propose a sampling based approach to overcome this challenge, allowing us to
factorize large rectangular matrices. In addition to these methods, we also
propose a simple baseline algorithm which outperforms our more sophisticated
methods in a few situations. We run experiments on the Fujitsu Digital
Annealer, a quantum-inspired complementary metal-oxide-semiconductor (CMOS)
annealer, on both synthetic and real data, including gene expression data.
These experiments show that our approach is able to produce more accurate BMFs
than competing methods.
- Abstract（参考訳）: データマイニングにおける多くの基本的な問題は1つ以上のnp-hard combinatorial optimization問題に還元できる。
量子や量子にインスパイアされたハードウェアのような新しい技術の進歩は、汎用コンピュータを使用する場合と比較して、これらの問題を解決するためにかなりのスピードアップを約束するが、これらのデバイスを活用するためには、Isingや2次非制約バイナリ最適化(QUBO)モデルのような特別な形式でモデル化する必要があることが多い。
本研究では、データマイニングに多くの応用がある重要なバイナリ行列分解(BMF)問題に焦点を当てる。
BMFのための2つのQUBO式を提案する。
これらの定式化にクラスタリングの制約を簡単に組み込む方法を示す。
私たちが考える特別な目的のハードウェアは、扱える変数の数に限られており、これは大きな行列を分解する際の課題である。
我々はこの課題を克服するためのサンプリングベースアプローチを提案し、大きな長方形行列を分解する。
また,これらの手法に加えて,いくつかの状況において,より洗練された手法を上回る単純なベースラインアルゴリズムを提案する。
遺伝子表現データを含む合成データと実データの両方において、量子インスパイアされた相補的金属-酸化物-半導体(CMOS)アニールである富士通デジタルアニールの実験を行った。
これらの実験により,本手法は競合手法よりも精度の高いBMFを生成可能であることが示された。
関連論文リスト
- Double-Logarithmic Depth Block-Encodings of Simple Finite Difference Method's Matrices [0.0]
微分方程式の解法は、古典計算において最も計算コストがかかる問題の1つである。
量子コンピューティングと量子アルゴリズムの分野で最近の進歩にもかかわらず、実用的実現に向けたエンドツーエンドの応用はいまだに達成不可能である。
論文 参考訳（メタデータ） (2024-10-07T17:44:30Z) - Optimized QUBO formulation methods for quantum computing [0.4999814847776097]
実世界の金融シナリオにインスパイアされたNPハード最適化問題に対して,我々の手法を適用する方法について述べる。
2つのD波量子異方体にこの問題の事例を提出し、これらのシナリオで使用される標準手法と新しい手法の性能を比較した。
論文 参考訳（メタデータ） (2024-06-11T19:59:05Z) - Deriving Compact QUBO Models via Multilevel Constraint Transformation [0.8192907805418583]
そこで本稿では,QUBOモデルに基づくMLCTS(Multilevel Constraint Transformation Scheme)を提案する。
概念実証では、後者の問題に対する2つのQUBOモデルの性能を、汎用ソフトウェアベースソルバとハードウェアベースのQUBOソルバで比較する。
MLCTS由来のモデルは、ハードウェアベースのアプローチで最大7倍のインスタンスを解くことで、両方のソルバのパフォーマンスを著しく向上させる。
論文 参考訳（メタデータ） (2024-04-04T17:34:08Z) - Symmetric Tensor Networks for Generative Modeling and Constrained
Combinatorial Optimization [72.41480594026815]
ポートフォリオ最適化からロジスティクスに至るまで、制約付き最適化問題は業界に多い。
これらの問題の解決における主要な障害の1つは、有効な検索空間を制限する非自明なハード制約の存在である。
本研究では、Ax=bという形の任意の整数値等式制約をU(1)対称ネットワーク(TN)に直接エンコードし、それらの適用性を量子に着想を得た生成モデルとして活用する。
論文 参考訳（メタデータ） (2022-11-16T18:59:54Z) - Adiabatic Quantum Computing for Multi Object Tracking [170.8716555363907]
マルチオブジェクト追跡(MOT)は、オブジェクト検出が時間を通して関連付けられているトラッキング・バイ・検出のパラダイムにおいて、最もよくアプローチされる。
これらの最適化問題はNPハードであるため、現在のハードウェア上の小さなインスタンスに対してのみ正確に解決できる。
本手法は,既成整数計画法を用いても,最先端の最適化手法と競合することを示す。
論文 参考訳（メタデータ） (2022-02-17T18:59:20Z) - Adiabatic Quantum Graph Matching with Permutation Matrix Constraints [75.88678895180189]
3次元形状と画像のマッチング問題は、NPハードな置換行列制約を持つ二次代入問題(QAP)としてしばしば定式化される。
本稿では,量子ハードウェア上での効率的な実行に適した制約のない問題として,いくつかのQAPの再構成を提案する。
提案アルゴリズムは、将来の量子コンピューティングアーキテクチャにおいて、より高次元にスケールする可能性がある。
論文 参考訳（メタデータ） (2021-07-08T17:59:55Z) - Machine Learning Framework for Quantum Sampling of Highly-Constrained,
Continuous Optimization Problems [101.18253437732933]
本研究では,連続空間の逆設計問題を,制約のないバイナリ最適化問題にマッピングする,汎用的な機械学習ベースのフレームワークを開発する。
本研究では, 熱発光トポロジを熱光応用に最適化し, (ii) 高効率ビームステアリングのための拡散メタグレーティングを行うことにより, 2つの逆設計問題に対するフレームワークの性能を示す。
論文 参考訳（メタデータ） (2021-05-06T02:22:23Z) - Offline Model-Based Optimization via Normalized Maximum Likelihood
Estimation [101.22379613810881]
データ駆動最適化の問題を検討し、一定の点セットでクエリのみを与えられた関数を最大化する必要がある。
この問題は、関数評価が複雑で高価なプロセスである多くの領域に現れる。
我々は,提案手法を高容量ニューラルネットワークモデルに拡張可能なトラクタブル近似を提案する。
論文 参考訳（メタデータ） (2021-02-16T06:04:27Z) - Binary Matrix Factorisation via Column Generation [6.445605125467574]
本稿では,算術における低ランク二乗行列分解(BMF)の問題点について考察する。
混合整数線形プログラムとして問題を定式化し、列生成の大規模最適化手法を用いて解決する。
実世界のデータセットを用いた実験結果から,提案手法は高精度な因数分解を実現するのに有効であることが示された。
論文 参考訳（メタデータ） (2020-11-09T14:27:36Z) - Quantum-Inspired Algorithms from Randomized Numerical Linear Algebra [53.46106569419296]
我々は、リコメンダシステムと最小二乗回帰のためのクエリをサポートする古典的な(量子でない)動的データ構造を作成する。
これらの問題に対する以前の量子インスパイアされたアルゴリズムは、レバレッジやリッジレベレッジスコアを偽装してサンプリングしていると我々は主張する。
論文 参考訳（メタデータ） (2020-11-09T01:13:07Z) - Quantum Approximate Optimization for Hard Problems in Linear Algebra [0.0]
本稿では,線形代数における他の難解問題の構成要素として,二元線形最小平方体 (BLLS) に対するQAOAについて検討する。
この研究の範囲では、ノイズのない量子シミュレータ、デバイスリアリスティックノイズモデルを含むシミュレータ、2つのIBM Q 5-qubitマシンで実験を行った。
我々の数値は、基底状態のサンプリングの確率が$pleq3$のQAOA深さでBLLSのQAOAよりも優れていることを示している。
論文 参考訳（メタデータ） (2020-06-27T20:13:24Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。