論文の概要: Efficient Algorithms for Learning and Compressing Monophonic Halfspaces in Graphs
- arxiv url: http://arxiv.org/abs/2506.23186v1
- Date: Sun, 29 Jun 2025 11:14:16 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-07-01 21:27:53.763788
- Title: Efficient Algorithms for Learning and Compressing Monophonic Halfspaces in Graphs
- Title(参考訳): グラフにおける単音素半空間の学習と圧縮のための効率的なアルゴリズム
- Authors: Marco Bressan, Victor Chepoi, Emmanuel Esposito, Maximilian Thiessen,
- Abstract要約: 誘導経路下での閉包によって定義されるグラフハーフ空間の概念であるモノフォニックハーフ空間について検討する。
文献からオープンな質問に回答し,これらの学習問題のほとんどはNPハードである測地学のハーフスペースとは対照的であることを示す。
- 参考スコア(独自算出の注目度): 6.974741712647656
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Abstract notions of convexity over the vertices of a graph, and corresponding notions of halfspaces, have recently gained attention from the machine learning community. In this work we study monophonic halfspaces, a notion of graph halfspaces defined through closure under induced paths. Our main result is a $2$-satisfiability based decomposition theorem, which allows one to represent monophonic halfspaces as a disjoint union of certain vertex subsets. Using this decomposition, we achieve efficient and (nearly) optimal algorithms for various learning problems, such as teaching, active, and online learning. Most notably, we obtain a polynomial-time algorithm for empirical risk minimization. Independently of the decomposition theorem, we obtain an efficient, stable, and proper sample compression scheme. This makes monophonic halfspaces efficiently learnable with proper learners and linear error rate $1/\varepsilon$ in the realizable PAC setting. Our results answer open questions from the literature, and show a stark contrast with geodesic halfspaces, for which most of the said learning problems are NP-hard.
- Abstract(参考訳): グラフの頂点に対する凸性の抽象概念とハーフスペースの対応する概念は、最近、機械学習コミュニティから注目を集めている。
本研究では、誘導経路の下での閉包によって定義されるグラフハーフ空間の概念である、モノフォニックハーフ空間について研究する。
我々の主な結果は、2$-satisfiability(英語版)に基づく分解定理であり、これはある種の頂点部分集合の不連結和として単音素半空間を表現できる。
この分解を用いて,教育,能動学習,オンライン学習など,様々な学習問題に対して,効率的かつ(ほぼ)最適なアルゴリズムを実現する。
最も顕著なのは、経験的リスク最小化のための多項式時間アルゴリズムである。
分解定理とは独立に、効率的で安定で適切なサンプル圧縮スキームを得る。
これにより、適切な学習者と線形誤り率1/\varepsilon$で、音素半空間を効率よく学習することができる。
文献からオープンな質問に回答し,これらの学習問題のほとんどはNPハードである測地学のハーフスペースとは対照的であることを示す。
関連論文リスト
- Efficient Algorithms for Learning Monophonic Halfspaces in Graphs [7.619404259039284]
我々は、教師付き、オンライン、アクティブな設定において、モノフォニックなハーフスペースを学習するためのいくつかの新しい結果を証明した。
我々の主な結果は、モノフォニック半空間は、n = |V(G)|$ の時間において、ほぼ最適に複雑に学習できるということである。
また、概念クラスは遅延$operatornamepoly(n)$で列挙でき、経験的リスクは2ω(G)operatornamepoly(n)$で実行可能であることも示します。
論文 参考訳(メタデータ) (2024-05-01T20:34:12Z) - Minimax Optimization: The Case of Convex-Submodular [50.03984152441271]
ミニマックス問題は連続領域を超えて連続離散領域や完全離散領域にまで拡張される。
連続変数に関して目的が凸であり、離散変数に関して部分モジュラーであるような凸-部分モジュラーミニマックス問題のクラスを導入する。
提案アルゴリズムは反復的であり、離散最適化と連続最適化の両方のツールを組み合わせる。
論文 参考訳(メタデータ) (2021-11-01T21:06:35Z) - Learning Weakly Convex Sets in Metric Spaces [2.0618817976970103]
機械学習理論における中心的な問題は、ゼロエラーを持つ一貫した仮説を効率的に見つけることができるかどうかである。
このアルゴリズムの一般的な考え方は、弱凸仮説の場合にまで拡張可能であることを示す。
論文 参考訳(メタデータ) (2021-05-10T23:00:02Z) - Agnostic Proper Learning of Halfspaces under Gaussian Marginals [56.01192577666607]
ガウスの下の半空間を不可知的に学習する問題を考察する。
我々の主な成果は、この問題に対するエム第一固有学習アルゴリズムである。
論文 参考訳(メタデータ) (2021-02-10T18:40:44Z) - Hardness of Learning Halfspaces with Massart Noise [56.98280399449707]
我々は、マッサート(有界)ノイズの存在下でPAC学習のハーフスペースの複雑さを研究します。
情報理論上最適なエラーとSQアルゴリズムで達成できる最高のエラーとの間に指数関数的なギャップがあることを示した。
論文 参考訳(メタデータ) (2020-12-17T16:43:11Z) - A Polynomial Time Algorithm for Learning Halfspaces with Tsybakov Noise [55.45544638410858]
本研究では,Tsybakovノイズの存在下でのPAC学習の相同性半空間の問題について検討する。
我々のアルゴリズムは、任意の精度$epsilon$で真のハーフスペースを学習する。
論文 参考訳(メタデータ) (2020-10-04T22:19:06Z) - Learning Halfspaces with Tsybakov Noise [50.659479930171585]
テュバコフ雑音の存在下でのハーフスペースの学習可能性について検討する。
真半空間に関して誤分類誤差$epsilon$を達成するアルゴリズムを与える。
論文 参考訳(メタデータ) (2020-06-11T14:25:02Z) - Learning Halfspaces with Massart Noise Under Structured Distributions [46.37328271312332]
分布特異的PACモデルにおいて,マスアートノイズを伴う学習空間の問題を解く。
対数対数対数対数対数対数対数対数対数対数対数対数対数対数対数対数対数対数対数対数対数対数対数対数対数対数対数対数対数対数対数対数対
論文 参考訳(メタデータ) (2020-02-13T17:02:37Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。