論文の概要: The Computational Complexity of Positive Non-Clashing Teaching in Graphs
- arxiv url: http://arxiv.org/abs/2503.07665v1
- Date: Sat, 08 Mar 2025 21:48:02 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-03-12 15:44:49.761910
- Title: The Computational Complexity of Positive Non-Clashing Teaching in Graphs
- Title（参考訳）: グラフにおける正の非切断学習の計算複雑性
- Authors: Robert Ganian, Liana Khazaliya, Fionn Mc Inerney, Mathis Rocton,
- Abstract要約: 概念の集合の正の非クラッシング教育次元を計算する際の古典的およびパラメータ化された複雑性について検討する。
我々は、正の非クラッシング教育次元 k=2 のインスタンスに制限された場合でも、問題のNPハードネスを確立する。
- 参考スコア（独自算出の注目度）: 13.564319117200561
- License:
- Abstract: We study the classical and parameterized complexity of computing the positive non-clashing teaching dimension of a set of concepts, that is, the smallest number of examples per concept required to successfully teach an intelligent learner under the considered, previously established model. For any class of concepts, it is known that this problem can be effortlessly transferred to the setting of balls in a graph G. We establish (1) the NP-hardness of the problem even when restricted to instances with positive non-clashing teaching dimension k=2 and where all balls in the graph are present, (2) near-tight running time upper and lower bounds for the problem on general graphs, (3) fixed-parameter tractability when parameterized by the vertex integrity of G, and (4) a lower bound excluding fixed-parameter tractability when parameterized by the feedback vertex number and pathwidth of G, even when combined with k. Our results provide a nearly complete understanding of the complexity landscape of computing the positive non-clashing teaching dimension and answer open questions from the literature.
- Abstract（参考訳）: 我々は,概念の集合の正の非クラッシング教育次元,すなわち,従来確立されていたモデルの下で知的学習者を教えるのに必要とされる概念の最小の例について,計算の古典的かつパラメータ化された複雑さについて検討する。
任意の概念に対して、この問題はグラフ G 内の球の設定に懸命に移行できることが知られている。(1) 正の非クラッシングの教育次元 k=2 のインスタンスに制限されても問題のNP硬度を確立し、(2) 一般グラフ上の問題に対するほぼタイトなランニング時間上と下限、(3) G の頂点整合性によってパラメータ化されたときの固定パラメータトラクタビリティ、(4) G のフィードバック頂点数とパス幅によってパラメータ化されたときの固定パラメータトラクタビリティを下限で排除すること。
この結果から, 正の非クラッシング学習次元を計算し, 文献からのオープンな質問に答えることの難易度をほぼ完全に理解することができる。
関連論文リスト
- From Gradient Clipping to Normalization for Heavy Tailed SGD [19.369399536643773]
最近の実証的な証拠は、機械学習の応用が重尾ノイズを伴い、実際に有界分散の標準的な仮定に挑戦していることを示している。
本稿では, 勾配依存型雑音収束問題において, テール雑音下での厳密性を実現することができることを示す。
論文 参考訳（メタデータ） (2024-10-17T17:59:01Z) - NodeFormer: A Scalable Graph Structure Learning Transformer for Node
Classification [70.51126383984555]
本稿では,任意のノード間のノード信号を効率的に伝搬する全ペアメッセージパッシング方式を提案する。
効率的な計算は、カーナライズされたGumbel-Softmax演算子によって実現される。
グラフ上のノード分類を含む様々なタスクにおいて,本手法の有望な有効性を示す実験を行った。
論文 参考訳（メタデータ） (2023-06-14T09:21:15Z) - Contrastive Graph Clustering in Curvature Spaces [74.03252813800334]
本研究では,CONGREGATE という新しいグラフクラスタリングモデルを提案する。
幾何学的クラスタリングを支援するため、理論的に基底とした不均一曲率空間を構築した。
次に、拡張不要な再重み付きコントラスト的アプローチでグラフクラスタをトレーニングする。
論文 参考訳（メタデータ） (2023-05-05T14:04:52Z) - Joint Graph Learning and Model Fitting in Laplacian Regularized
Stratified Models [5.933030735757292]
ラプラシア正規化成層モデル(Laplacian regularized Stratified Model、LRSM)は、サブプロブレムの明示的または暗黙的なネットワーク構造を利用するモデルである。
本稿では,LRSMにおけるグラフ重みの重要性と感度を示し,その感度が任意に大きいことを示す。
本稿では,1つの最適化問題を解くことで,モデルパラメータを適合させながらグラフを共同学習する汎用的手法を提案する。
論文 参考訳（メタデータ） (2023-05-04T06:06:29Z) - Localized Contrastive Learning on Graphs [110.54606263711385]
局所グラフコントラスト学習(Local-GCL)という,シンプルだが効果的なコントラストモデルを導入する。
その単純さにもかかわらず、Local-GCLは、様々なスケールと特性を持つグラフ上の自己教師付きノード表現学習タスクにおいて、非常に競争力のある性能を達成する。
論文 参考訳（メタデータ） (2022-12-08T23:36:00Z) - Low-Rank Covariance Completion for Graph Quilting with Applications to Functional Connectivity [8.500141848121782]
多くのカルシウムイメージングデータセットでは、ニューロンの全個体数は同時に記録されるのではなく、部分的に重なるブロックに記録される。
本稿では、まず、低ランクココンプリートを用いた原子核構造行列を暗示するグラフ量子化法について述べる。
カルシウムイメージングデータから接続性を推定するためのこれらの手法の有効性を示す。
論文 参考訳（メタデータ） (2022-09-17T08:03:46Z) - Comprehensive Graph Gradual Pruning for Sparse Training in Graph Neural
Networks [52.566735716983956]
本稿では,CGPと呼ばれるグラフの段階的プルーニングフレームワークを動的にGNNに提案する。
LTHに基づく手法とは異なり、提案手法では再学習を必要とせず、計算コストを大幅に削減する。
提案手法は,既存の手法の精度を一致させたり,あるいは超えたりしながら,トレーニングと推論の効率を大幅に向上させる。
論文 参考訳（メタデータ） (2022-07-18T14:23:31Z) - Parameterized Hypercomplex Graph Neural Networks for Graph
Classification [1.1852406625172216]
我々は超複雑特徴変換の特性を利用するグラフニューラルネットワークを開発した。
特に、提案したモデルのクラスでは、代数自身を特定する乗法則は、トレーニング中にデータから推測される。
提案するハイパーコンプレックスgnnをいくつかのオープングラフベンチマークデータセット上でテストし,そのモデルが最先端の性能に達することを示す。
論文 参考訳（メタデータ） (2021-03-30T18:01:06Z) - A Thorough View of Exact Inference in Graphs from the Degree-4
Sum-of-Squares Hierarchy [37.34153902687548]
各エッジの1つの破損した観測からノードの未知の接地型バイナリラベリングを正確に回収する問題に取り組む。
この問題に対して、和の平方階層と呼ばれるリラクゼーションの階層を適用します。
我々は、緩和問題の双対の解がジョンソングラフとクネーサーグラフのエッジウェイトを見つけることに関連していることを示した。
論文 参考訳（メタデータ） (2021-02-16T08:36:19Z) - Semiparametric Nonlinear Bipartite Graph Representation Learning with
Provable Guarantees [106.91654068632882]
半パラメトリック指数族分布におけるパラメータの統計的推定問題として、両部グラフを考察し、その表現学習問題を定式化する。
提案手法は, 地中真理付近で強い凸性を示すため, 勾配降下法が線形収束率を達成できることを示す。
我々の推定器は指数族内の任意のモデル誤特定に対して頑健であり、広範な実験で検証されている。
論文 参考訳（メタデータ） (2020-03-02T16:40:36Z) - Convex Geometry and Duality of Over-parameterized Neural Networks [70.15611146583068]
有限幅2層ReLUネットワークの解析のための凸解析手法を開発した。
正規化学習問題に対する最適解が凸集合の極点として特徴づけられることを示す。
高次元では、トレーニング問題は無限に多くの制約を持つ有限次元凸問題としてキャストできることが示される。
論文 参考訳（メタデータ） (2020-02-25T23:05:33Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。