論文の概要: Maximal Closed Set and Half-Space Separations in Finite Closure Systems
- arxiv url: http://arxiv.org/abs/2001.04417v3
- Date: Mon, 13 Jun 2022 10:35:00 GMT
- ステータス: 処理完了
- システム内更新日: 2023-01-11 22:29:46.199981
- Title: Maximal Closed Set and Half-Space Separations in Finite Closure Systems
- Title（参考訳）: 有限クロージャ系における最大閉集合と半空間分離
- Authors: Florian Seiffarth, Tamas Horvath and Stefan Wrobel
- Abstract要約: いくつかの概念学習問題は、有限基底集合上の抽象的閉包系における半空間分離の特別な場合と見なすことができる。
閉包系が閉包演算子を介して暗黙的に与えられる典型的なシナリオについて、半空間分離問題はNP完全であることを示す。
2つ目の特別なケースでは、有限格子上の閉包系に焦点をあて、ジェネリックグリーディアルゴリズムを改良し、仮定格子に関する応用を示す。
- 参考スコア（独自算出の注目度）: 3.007949058551534
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Several concept learning problems can be regarded as special cases of
half-space separation in abstract closure systems over finite ground sets. For
the typical scenario that the closure system is implicitly given via a closure
operator, we show that the half-space separation problem is NP-complete. As a
first approach to overcome this negative result, we relax the problem to
maximal closed set separation, give a generic greedy algorithm solving this
problem with a linear number of closure operator calls, and show that this
bound is sharp. For a second direction, we consider Kakutani closure systems
and prove that they are algorithmically characterized by the greedy algorithm.
As a first special case of the general problem setting, we consider Kakutani
closure systems over graphs and give a sufficient condition for this kind of
closure systems in terms of forbidden graph minors. For a second special case,
we then focus on closure systems over finite lattices, give an improved
adaptation of the generic greedy algorithm, and present an application
concerning subsumption lattices.
- Abstract（参考訳）: いくつかの概念学習問題は、有限基底集合上の抽象閉包系における半空間分離の特別な場合と見なすことができる。
閉包系が閉包演算子を介して暗黙的に与えられる典型的なシナリオについて、半空間分離問題はNP完全であることを示す。
この負の結果を克服する最初のアプローチとして、この問題を最大閉集合分離に緩和し、この問題を線形数のクロージャ演算子呼び出しで解く一般の欲求アルゴリズムを与え、この境界が鋭いことを示す。
第二に,角谷閉包系を考察し,アルゴリズムによって特徴付けられることを証明した。
一般問題設定の第一の特別な場合として、グラフ上の角谷閉包系を考察し、禁止グラフマイナーーの観点からこの種の閉包系に十分な条件を与える。
第二の特別な場合として、有限格子上の閉包系に着目し、ジェネリック・グリーディアルゴリズムの適応性を高め、仮定格子に関する応用を提案する。
関連論文リスト
- Weighted mesh algorithms for general Markov decision processes: Convergence and tractability [0.9940462449990576]
離散時間有限水平マルコフ決定過程(MDP)に対するメッシュ型アプローチを提案する。
非有界な状態空間に対して、このアルゴリズムは、複雑性がある次元独立な$cgeq2$を持つ$epsilonc$であるという意味で「半有理」である。
論文 参考訳（メタデータ） (2024-06-29T10:08:23Z) - Discretize Relaxed Solution of Spectral Clustering via a Non-Heuristic
Algorithm [77.53604156112144]
我々は、元の問題と離散化アルゴリズムを橋渡しする1次項を開発する。
非ヒューリスティック法は元のグラフ切断問題を認識しているため、最終的な離散解の方が信頼性が高い。
論文 参考訳（メタデータ） (2023-10-19T13:57:38Z) - Complexity of Block Coordinate Descent with Proximal Regularization and
Applications to Wasserstein CP-dictionary Learning [1.4010916616909743]
正規化(BCD-PR)によるGauss-Sdel型ブロック座標の導出について検討する。
W(W) W(W) W(W) W(W) W(W) W(W) W(W) W(W) W(W) W(W) W(W) W(W) W(W) W(W) W(W) W(W) W(W) W(W) W(W) W(W) W(W) W(W) W(W) W(W) W(W) W(W) W(W) W(W) W(W) W) W(W) W(W) W) W(W) W(W) W) W(W) W(W) W(W)
論文 参考訳（メタデータ） (2023-06-04T17:52:49Z) - Differentially-Private Hierarchical Clustering with Provable
Approximation Guarantees [79.59010418610625]
階層クラスタリングのための微分プライベート近似アルゴリズムについて検討する。
例えば、$epsilon$-DPアルゴリズムは入力データセットに対して$O(|V|2/epsilon)$-additiveエラーを示さなければならない。
本稿では,ブロックを正確に復元する1+o(1)$近似アルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-01-31T19:14:30Z) - Approximation of optimization problems with constraints through kernel
Sum-Of-Squares [77.27820145069515]
我々は、点的不等式が非負の kSoS 関数のクラス内で等式となることを示す。
また, 等式制約に焦点をあてることで, 散乱不等式を用いることで, 制約のサンプリングにおける次元性の呪いを軽減することができることを示す。
論文 参考訳（メタデータ） (2023-01-16T10:30:04Z) - A Newton-CG based barrier-augmented Lagrangian method for general nonconvex conic optimization [53.044526424637866]
本稿では、2つの異なる対象の一般円錐最適化を最小化する近似二階定常点(SOSP)について検討する。
特に、近似SOSPを見つけるためのNewton-CGベースの拡張共役法を提案する。
論文 参考訳（メタデータ） (2023-01-10T20:43:29Z) - The Franke-Gorini-Kossakowski-Lindblad-Sudarshan (FGKLS) Equation for
Two-Dimensional Systems [62.997667081978825]
開量子系は、FGKLS(Franke-Gorini-Kossakowski-Lindblad-Sudarshan)方程式に従うことができる。
我々はヒルベルト空間次元が 2$ である場合を徹底的に研究する。
論文 参考訳（メタデータ） (2022-04-16T07:03:54Z) - Constrained mixers for the quantum approximate optimization algorithm [55.41644538483948]
ヒルベルト空間全体の部分空間への発展を制限する混合作用素を構築するための枠組みを提案する。
我々は,「ワンホット」状態の部分空間を保存するために設計された「XY」ミキサーを,多くの計算基底状態によって与えられる部分空間の一般の場合に一般化する。
我々の分析は、現在知られているよりもCXゲートが少ない"XY"ミキサーのトロタライズも有効である。
論文 参考訳（メタデータ） (2022-03-11T17:19:26Z) - A Two Stage Generalized Block Orthogonal Matching Pursuit (TSGBOMP)
Algorithm [0.3867363075280543]
いくつかの投射からの未知のスパース信号の回収は、圧縮センシングの重要な目的である。
BOMPのような既存のブロックスパース回復アルゴリズムは、一様ブロックサイズと既知のブロック境界を仮定する。
本稿では,第1段階が粗いブロック位置同定段階である2段階の手順を提案する。
第2のステージは、第1のステージで選択されたウィンドウ内の非ゼロクラスタのより微細なローカライズを実行する。
論文 参考訳（メタデータ） (2020-08-18T17:00:55Z) - Entanglement marginal problems [0.0]
絡み合いの限界問題は、多くの還元密度行列が全体分離可能な量子状態と互換性があるかどうかを決定することである。
完全分離可能な拡張を許容する量子状態境界の集合の半定値プログラミング緩和の階層性を提案する。
我々の結果は、1次元の翻訳不変系や余剰対称性を持つ高次元など無限のシステムにまで拡張される。
論文 参考訳（メタデータ） (2020-06-16T10:48:56Z) - Learning Halfspaces with Massart Noise Under Structured Distributions [46.37328271312332]
分布特異的PACモデルにおいて,マスアートノイズを伴う学習空間の問題を解く。
対数対数対数対数対数対数対数対数対数対数対数対数対数対数対数対数対数対数対数対数対数対数対数対数対数対数対数対数対数対数対数対数対
論文 参考訳（メタデータ） (2020-02-13T17:02:37Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。