論文の概要: Learning Weakly Convex Sets in Metric Spaces
- arxiv url: http://arxiv.org/abs/2105.06251v1
- Date: Mon, 10 May 2021 23:00:02 GMT
- ステータス: 処理完了
- システム内更新日: 2021-05-14 14:12:50.169599
- Title: Learning Weakly Convex Sets in Metric Spaces
- Title（参考訳）: 計量空間における弱凸集合の学習
- Authors: Eike Stadtl\"ander, Tam\'as Horv\'ath, Stefan Wrobel
- Abstract要約: 弱凸集合は閉作用素によって特徴づけられ、一対の不連結な連結ブロックの集合に一意に分解されることを示す。
我々は、例のセットと一致し、最小数の超矩形を含む弱凸集合が時間内に見つかることを示す。
- 参考スコア（独自算出の注目度）: 1.456699007803424
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We introduce the notion of weak convexity in metric spaces, a generalization
of ordinary convexity commonly used in machine learning. It is shown that
weakly convex sets can be characterized by a closure operator and have a unique
decomposition into a set of pairwise disjoint connected blocks. We give two
generic efficient algorithms, an extensional and an intensional one for
learning weakly convex concepts and study their formal properties. Our
experimental results concerning vertex classification clearly demonstrate the
excellent predictive performance of the extensional algorithm. Two non-trivial
applications of the intensional algorithm to polynomial PAC-learnability are
presented. The first one deals with learning $k$-convex Boolean functions,
which are already known to be efficiently PAC-learnable. It is shown how to
derive this positive result in a fairly easy way by the generic intensional
algorithm. The second one is concerned with the Euclidean space equipped with
the Manhattan distance. For this metric space, weakly convex sets are a union
of pairwise disjoint axis-aligned hyperrectangles. We show that a weakly convex
set that is consistent with a set of examples and contains a minimum number of
hyperrectangles can be found in polynomial time. In contrast, this problem is
known to be NP-complete if the hyperrectangles may be overlapping.
- Abstract（参考訳）: 本稿では,機械学習においてよく用いられる一般凸性の一般化である距離空間における弱凸の概念を紹介する。
弱凸集合は閉作用素によって特徴づけられ、一意な分解をペアワイズ不連結ブロックの集合に持つことが示されている。
弱凸概念を学習し、それらの形式的性質を研究するために、拡張型とインテンション型という2つの汎用的効率的なアルゴリズムを与える。
頂点分類に関する実験結果から,拡張アルゴリズムの優れた予測性能が明らかとなった。
インテンショナルアルゴリズムの多項式PAC学習性に対する2つの非自明な応用を示す。
最初の1つは$k$-convex boolean関数の学習を扱っており、これは既にpac-learnableとして知られている。
汎用インテンションアルゴリズムを用いて, この正の結果を比較的容易に導出する方法を示す。
2つ目は、マンハッタン距離を備えたユークリッド空間に関するものである。
この距離空間に対して、弱凸集合は対に非随伴な軸方向の超矩形からなる和である。
弱凸集合が一組の例と一致し、多項式時間内に最小数の超矩形を含むことを示す。
対照的に、超矩形が重なり合う場合、この問題はNP完全であることが知られている。
関連論文リスト
- Non-Convex Robust Hypothesis Testing using Sinkhorn Uncertainty Sets [18.46110328123008]
非破壊仮説テスト問題に対処する新しい枠組みを提案する。
目標は、最大数値リスクを最小限に抑える最適な検出器を探すことである。
論文 参考訳（メタデータ） (2024-03-21T20:29:43Z) - Optimal Multi-Distribution Learning [88.3008613028333]
マルチディストリビューション学習は、$k$の異なるデータ分散における最悪のリスクを最小限に抑える共有モデルを学ぶことを目指している。
本稿では, (d+k)/varepsilon2の順に, サンプルの複雑さを伴って, ヴァレプシロン最適ランダム化仮説を導出するアルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-12-08T16:06:29Z) - On Continuity of Robust and Accurate Classifiers [3.8673630752805437]
敵の訓練が仮説の堅牢性を向上させることが示されている。
仮説の頑健性と正確性は互いに相反していることが示唆されている。
本稿では,その頑健さと精度に相容れない仮説の連続性について,その代替案を提示する。
論文 参考訳（メタデータ） (2023-09-29T08:14:25Z) - Learnability, Sample Complexity, and Hypothesis Class Complexity for
Regression Models [10.66048003460524]
この研究はPACの基礎に触発され、既存の回帰学習問題に動機付けられている。
提案手法はEpsilon-Confidence Aough Correct (epsilon CoAC)で示され、Kullback Leibler divergence(相対エントロピー)を利用する。
これにより、学習者は異なる複雑性順序の仮説クラスを比較でき、それらの中から最小のエプシロンを最適に選択できる。
論文 参考訳（メタデータ） (2023-03-28T15:59:12Z) - On the Benefits of Large Learning Rates for Kernel Methods [110.03020563291788]
本稿では,カーネル手法のコンテキストにおいて,現象を正確に特徴付けることができることを示す。
分離可能なヒルベルト空間における2次対象の最小化を考慮し、早期停止の場合、学習速度の選択が得られた解のスペクトル分解に影響を及ぼすことを示す。
論文 参考訳（メタデータ） (2022-02-28T13:01:04Z) - Partial Counterfactual Identification from Observational and
Experimental Data [83.798237968683]
観測データと実験データの任意の組み合わせから最適境界を近似する有効なモンテカルロアルゴリズムを開発した。
我々のアルゴリズムは、合成および実世界のデータセットに基づいて広範囲に検証されている。
論文 参考訳（メタデータ） (2021-10-12T02:21:30Z) - Optimal oracle inequalities for solving projected fixed-point equations [53.31620399640334]
ヒルベルト空間の既知の低次元部分空間を探索することにより、確率観測の集合を用いて近似解を計算する手法を検討する。
本稿では,線形関数近似を用いた政策評価問題に対する時間差分学習手法の誤差を正確に評価する方法について述べる。
論文 参考訳（メタデータ） (2020-12-09T20:19:32Z) - Fast Objective & Duality Gap Convergence for Non-Convex Strongly-Concave
Min-Max Problems with PL Condition [52.08417569774822]
本稿では,深層学習(深層AUC)により注目度が高まっている,円滑な非凹部min-max問題の解法に焦点をあてる。
論文 参考訳（メタデータ） (2020-06-12T00:32:21Z) - Learning from Non-Random Data in Hilbert Spaces: An Optimal Recovery
Perspective [12.674428374982547]
最適回復の観点から回帰問題を考察する。
まず、有限次元ヒルベルト空間における任意の回復写像の最悪のケース誤差を計算する半定値プログラムを開発する。
最適回復法は,アルゴリズム的な視点からユーザフレンドリな式を提供する。
論文 参考訳（メタデータ） (2020-06-05T21:49:07Z) - Counterexamples to the Low-Degree Conjecture [80.3668228845075]
ホプキンスの予想は、ある高次元仮説テスト問題に対して、非時間アルゴリズムはいわゆる「単純な統計」よりも優れていると仮定する。
この予想は、統計対計算のトレードオフを理解しようとする最近の研究のラインを囲む信念を定式化する。
論文 参考訳（メタデータ） (2020-04-17T21:08:11Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。