論文の概要: Efficient Algorithms for Learning Monophonic Halfspaces in Graphs
- arxiv url: http://arxiv.org/abs/2405.00853v2
- Date: Mon, 17 Jun 2024 23:04:58 GMT
- ステータス: 処理完了
- システム内更新日: 2024-06-20 01:35:12.939636
- Title: Efficient Algorithms for Learning Monophonic Halfspaces in Graphs
- Title（参考訳）: グラフにおける単音素半空間学習のための効率的なアルゴリズム
- Authors: Marco Bressan, Emmanuel Esposito, Maximilian Thiessen,
- Abstract要約: 我々は、教師付き、オンライン、アクティブな設定において、モノフォニックなハーフスペースを学習するためのいくつかの新しい結果を証明した。
我々の主な結果は、モノフォニック半空間は、n = |V(G)|$ の時間において、ほぼ最適に複雑に学習できるということである。
また、概念クラスは遅延$operatornamepoly(n)$で列挙でき、経験的リスクは2ω(G)operatornamepoly(n)$で実行可能であることも示します。
- 参考スコア（独自算出の注目度）: 7.619404259039284
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study the problem of learning a binary classifier on the vertices of a graph. In particular, we consider classifiers given by monophonic halfspaces, partitions of the vertices that are convex in a certain abstract sense. Monophonic halfspaces, and related notions such as geodesic halfspaces,have recently attracted interest, and several connections have been drawn between their properties(e.g., their VC dimension) and the structure of the underlying graph $G$. We prove several novel results for learning monophonic halfspaces in the supervised, online, and active settings. Our main result is that a monophonic halfspace can be learned with near-optimal passive sample complexity in time polynomial in $n = |V(G)|$. This requires us to devise a polynomial-time algorithm for consistent hypothesis checking, based on several structural insights on monophonic halfspaces and on a reduction to $2$-satisfiability. We prove similar results for the online and active settings. We also show that the concept class can be enumerated with delay $\operatorname{poly}(n)$, and that empirical risk minimization can be performed in time $2^{\omega(G)}\operatorname{poly}(n)$ where $\omega(G)$ is the clique number of $G$. These results answer open questions from the literature (Gonz\'alez et al., 2020), and show a contrast with geodesic halfspaces, for which some of the said problems are NP-hard (Seiffarth et al., 2023).
- Abstract（参考訳）: グラフの頂点上で二項分類器を学習する問題について検討する。
特に、ある抽象的な意味で凸である頂点の分割である単音素半空間によって与えられる分類子を考える。
単音素半空間や測地的半空間のような関連する概念は、最近関心を集め、それらの性質(例えば、VC次元)と基礎となるグラフの$G$の構造の間にいくつかの接続が引かれた。
我々は、教師付き、オンライン、アクティブな設定において、モノフォニックなハーフスペースを学習するためのいくつかの新しい結果を証明した。
我々の主な結果は、n = |V(G)|$ の時間多項式において、単音素半空間は、ほぼ最適のパッシブサンプル複雑性で学習できるということである。
これにより、単調な半空間に関するいくつかの構造的洞察に基づいて、一貫した仮説チェックのための多項式時間アルゴリズムを考案し、満足度を2ドルに下げる必要がある。
オンラインおよびアクティブな設定でも同様の結果が得られます。
また、概念クラスは遅延$\operatorname{poly}(n)$で列挙でき、経験的リスク最小化は2.^{\omega(G)}\operatorname{poly}(n)$で、$\omega(G)$は$G$の斜め数であることを示す。
これらの結果は、文献(Gonz\'alez et al , 2020)からのオープンな質問に答え、これらの問題のいくつかがNPハードである測地空間との対比を示す(Seiffarth et al , 2023)。
関連論文リスト
- Reliable Learning of Halfspaces under Gaussian Marginals [34.64644162448095]
本稿では,カライらの信頼的無知モデルにおけるPAC学習ハーフスペースの問題について検討する。
我々の主な肯定的な結果は、サンプルおよび計算複雑性を持つ$mathbbRd$上のガウス半空間の信頼性学習のための新しいアルゴリズムである。
論文 参考訳（メタデータ） (2024-11-18T02:13:11Z) - Cryptographic Hardness of Learning Halfspaces with Massart Noise [59.8587499110224]
マスアートノイズの存在下でのPAC学習ハーフスペースの複雑さについて検討した。
我々は,最適0-1誤差が小さい場合でも,リアルタイムのMassartハーフスペース学習者が$Omega(eta)$よりも良い誤差を得られることを示す。
論文 参考訳（メタデータ） (2022-07-28T17:50:53Z) - Learning a Single Neuron with Adversarial Label Noise via Gradient
Descent [50.659479930171585]
モノトン活性化に対する $mathbfxmapstosigma(mathbfwcdotmathbfx)$ の関数について検討する。
学習者の目標は仮説ベクトル $mathbfw$ that $F(mathbbw)=C, epsilon$ を高い確率で出力することである。
論文 参考訳（メタデータ） (2022-06-17T17:55:43Z) - Threshold Phenomena in Learning Halfspaces with Massart Noise [56.01192577666607]
ガウス境界の下でのマスアートノイズ付きmathbbRd$におけるPAC学習ハーフスペースの問題について検討する。
この結果は,Massartモデルにおける学習ハーフスペースの複雑さを定性的に特徴づけるものである。
論文 参考訳（メタデータ） (2021-08-19T16:16:48Z) - On the Power of Localized Perceptron for Label-Optimal Learning of
Halfspaces with Adversarial Noise [4.8728183994912415]
対比雑音を伴う$mathbbRd$の同質半空間のオンラインアクティブ学習について研究する。
私たちの主な貢献は、時間内で動作するパーセプトロンライクなアクティブラーニングアルゴリズムです。
アルゴリズムは、ほぼ最適ラベルの複雑さで基礎となるハーフスペースを学習する。
論文 参考訳（メタデータ） (2020-12-19T22:04:10Z) - Hardness of Learning Halfspaces with Massart Noise [56.98280399449707]
我々は、マッサート(有界)ノイズの存在下でPAC学習のハーフスペースの複雑さを研究します。
情報理論上最適なエラーとSQアルゴリズムで達成できる最高のエラーとの間に指数関数的なギャップがあることを示した。
論文 参考訳（メタデータ） (2020-12-17T16:43:11Z) - Small Covers for Near-Zero Sets of Polynomials and Learning Latent
Variable Models [56.98280399449707]
我々は、s$ of cardinality $m = (k/epsilon)o_d(k1/d)$ に対して $epsilon$-cover が存在することを示す。
構造的結果に基づいて,いくつかの基本的高次元確率モデル隠れ変数の学習アルゴリズムを改良した。
論文 参考訳（メタデータ） (2020-12-14T18:14:08Z) - Learning Halfspaces with Tsybakov Noise [50.659479930171585]
テュバコフ雑音の存在下でのハーフスペースの学習可能性について検討する。
真半空間に関して誤分類誤差$epsilon$を達成するアルゴリズムを与える。
論文 参考訳（メタデータ） (2020-06-11T14:25:02Z) - Classification Under Misspecification: Halfspaces, Generalized Linear
Models, and Connections to Evolvability [39.01599245403753]
特に、Massartノイズ下でのハーフスペースの学習問題を$eta$で検討する。
我々は任意のSQアルゴリズムが$mathsfOPT + epsilon$を達成するのに超ポリノミカルな多くのクエリを必要とすることを示した。
また、Massartノイズ下でハーフスペースを学習するためのアルゴリズムを実証的に研究し、いくつかの魅力的なフェアネス特性を示すことを示した。
論文 参考訳（メタデータ） (2020-06-08T17:59:11Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。