論文の概要: Efficiently Learning the Graph for Semi-supervised Learning
- arxiv url: http://arxiv.org/abs/2306.07098v1
- Date: Mon, 12 Jun 2023 13:22:06 GMT
- ステータス: 処理完了
- システム内更新日: 2023-06-13 14:29:26.552935
- Title: Efficiently Learning the Graph for Semi-supervised Learning
- Title（参考訳）: 半教師あり学習におけるグラフの学習
- Authors: Dravyansh Sharma, Maxwell Jones
- Abstract要約: 共役勾配法を用いてスパース族から最良のグラフを効率的に学習する方法を示す。
我々の手法は、軽度な滑らかさの仮定の下で、オンラインのサブ線形後悔でグラフを効率的に学習するためにも利用できる。
提案手法を実装し,ベンチマークデータセット上の学習グラフを用いた半教師付き学習の先行研究に対して,大幅な(sim$10-100x)スピードアップを示す。
- 参考スコア（独自算出の注目度）: 4.518012967046983
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Computational efficiency is a major bottleneck in using classic graph-based
approaches for semi-supervised learning on datasets with a large number of
unlabeled examples. Known techniques to improve efficiency typically involve an
approximation of the graph regularization objective, but suffer two major
drawbacks - first the graph is assumed to be known or constructed with
heuristic hyperparameter values, second they do not provide a principled
approximation guarantee for learning over the full unlabeled dataset. Building
on recent work on learning graphs for semi-supervised learning from multiple
datasets for problems from the same domain, and leveraging techniques for fast
approximations for solving linear systems in the graph Laplacian matrix, we
propose algorithms that overcome both the above limitations.
We show a formal separation in the learning-theoretic complexity of sparse
and dense graph families. We further show how to approximately learn the best
graphs from the sparse families efficiently using the conjugate gradient
method.
Our approach can also be used to learn the graph efficiently online with
sub-linear regret, under mild smoothness assumptions. Our online learning
results are stated generally, and may be useful for approximate and efficient
parameter tuning in other problems. We implement our approach and demonstrate
significant ($\sim$10-100x) speedups over prior work on semi-supervised
learning with learned graphs on benchmark datasets.
- Abstract（参考訳）: 計算効率は、ラベルなしの例が多数あるデータセット上の半教師付き学習に古典的なグラフベースのアプローチを使用する際の大きなボトルネックである。
効率を改善する技術として一般的には、グラフ正規化の目的を近似するが、2つの大きな欠点がある。まず、グラフはヒューリスティックなハイパーパラメータ値で知られ、構築されていると仮定される。
複数のデータセットから半教師付き学習のためのグラフを同じ領域から学習する最近の研究と、グラフラプラシアン行列における線形系を解くための高速近似手法の活用を基礎として、上記の制限を克服するアルゴリズムを提案する。
スパースおよび高密度グラフファミリーの学習理論的複雑性の形式的分離を示す。
さらに,共役勾配法を用いて,スパース族から最良グラフを効率的に学習する方法を示す。
本手法は,軽度な平滑性仮定の下で,線形後悔を伴うオンライングラフを効率的に学習するためにも利用できる。
オンライン学習の結果は一般に述べられ、他の問題に対する近似的かつ効率的なパラメータチューニングに有用である。
提案手法を実装し,ベンチマークデータセット上の学習グラフを用いた半教師付き学習の先行研究に対して,重要な($10-100x)スピードアップを示す。
関連論文リスト
- Improved Graph-based semi-supervised learning Schemes [0.0]
本研究では,ラベルの少ない大規模データセットの分類に対処するため,いくつかの既知のアルゴリズムの精度を向上させる。
私たちのフレームワークは、グラフベースの半教師あり学習の領域にあります。
論文 参考訳（メタデータ） (2024-06-30T16:50:08Z) - Localized Contrastive Learning on Graphs [110.54606263711385]
局所グラフコントラスト学習(Local-GCL)という,シンプルだが効果的なコントラストモデルを導入する。
その単純さにもかかわらず、Local-GCLは、様々なスケールと特性を持つグラフ上の自己教師付きノード表現学習タスクにおいて、非常に競争力のある性能を達成する。
論文 参考訳（メタデータ） (2022-12-08T23:36:00Z) - ARIEL: Adversarial Graph Contrastive Learning [51.14695794459399]
ARIELは、ノードレベルとグラフレベルの両方の分類タスクにおいて、現在のグラフコントラスト学習法よりも一貫して優れている。
ARIELは敵の攻撃に対してより堅牢である。
論文 参考訳（メタデータ） (2022-08-15T01:24:42Z) - Condensing Graphs via One-Step Gradient Matching [50.07587238142548]
ネットワーク重みを訓練せずに1ステップのみの勾配マッチングを行う1ステップ勾配マッチング方式を提案する。
我々の理論的分析は、この戦略が実際のグラフの分類損失を減少させる合成グラフを生成することができることを示している。
特に、元のパフォーマンスの最大98%を近似しながら、データセットサイズを90%削減することが可能です。
論文 参考訳（メタデータ） (2022-06-15T18:20:01Z) - Optimal Propagation for Graph Neural Networks [51.08426265813481]
最適グラフ構造を学習するための二段階最適化手法を提案する。
また、時間的複雑さをさらに軽減するために、低ランク近似モデルについても検討する。
論文 参考訳（メタデータ） (2022-05-06T03:37:00Z) - Learning Graphs from Smooth Signals under Moment Uncertainty [23.868075779606425]
与えられたグラフ信号の集合からグラフ構造を推測する問題を検討する。
従来のグラフ学習モデルは、この分布の不確実性を考慮していない。
論文 参考訳（メタデータ） (2021-05-12T06:47:34Z) - Learnable Graph Matching: Incorporating Graph Partitioning with Deep
Feature Learning for Multiple Object Tracking [58.30147362745852]
フレーム間のデータアソシエーションは、Multiple Object Tracking(MOT)タスクの中核にある。
既存の手法は、主にトラックレットとフレーム内検出の間のコンテキスト情報を無視する。
そこで本研究では,学習可能なグラフマッチング手法を提案する。
論文 参考訳（メタデータ） (2021-03-30T08:58:45Z) - Data driven algorithms for limited labeled data learning [35.193000364580975]
類似ノードが類似するラベルを持つ可能性が高いという暗黙の仮定の下で,ラベルのない例がグラフで接続されるグラフベースの手法に注目した。
本稿では,このグラフを学習するための新しいデータ駆動アプローチを提案し,分布形式とオンライン学習形式の両方において強力な形式的保証を提供する。
論文 参考訳（メタデータ） (2021-03-18T22:19:19Z) - Multilayer Clustered Graph Learning [66.94201299553336]
我々は、観測された層を代表グラフに適切に集約するために、データ忠実度用語として対照的な損失を用いる。
実験により,本手法がクラスタクラスタw.r.tに繋がることが示された。
クラスタリング問題を解くためのクラスタリングアルゴリズムを学習する。
論文 参考訳（メタデータ） (2020-10-29T09:58:02Z) - Learning Product Graphs Underlying Smooth Graph Signals [15.023662220197242]
本稿では,製品グラフの形式で与えられるデータから構造化グラフを学習する方法を考案する。
この目的のために、まずグラフ学習問題は線形プログラムとして表され、これは(平均的に)最先端のグラフ学習アルゴリズムより優れている。
論文 参考訳（メタデータ） (2020-02-26T03:25:15Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。