論文の概要: Rates of Convergence for Laplacian Semi-Supervised Learning with Low
Labeling Rates
- arxiv url: http://arxiv.org/abs/2006.02765v1
- Date: Thu, 4 Jun 2020 10:46:01 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-25 09:41:48.044199
- Title: Rates of Convergence for Laplacian Semi-Supervised Learning with Low
Labeling Rates
- Title(参考訳): 低ラベリング率ラプラシア半教師学習における収束率
- Authors: Jeff Calder, Dejan Slep\v{c}ev and Matthew Thorpe
- Abstract要約: グラフに基づくラプラシアン半教師付き学習を低ラベリングレートで研究する。
ラベルレートが非常に低い場合、ラプラシアン学習は縮退し、その解はラベル付き各データポイントのスパイクとほぼ一定となる。
- 参考スコア(独自算出の注目度): 3.867363075280544
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study graph-based Laplacian semi-supervised learning at low labeling
rates. Laplacian learning uses harmonic extension on a graph to propagate
labels. At very low label rates, Laplacian learning becomes degenerate and the
solution is roughly constant with spikes at each labeled data point. Previous
work has shown that this degeneracy occurs when the number of labeled data
points is finite while the number of unlabeled data points tends to infinity.
In this work we allow the number of labeled data points to grow to infinity
with the number of labels. Our results show that for a random geometric graph
with length scale $\varepsilon>0$ and labeling rate $\beta>0$, if $\beta
\ll\varepsilon^2$ then the solution becomes degenerate and spikes form, and if
$\beta\gg \varepsilon^2$ then Laplacian learning is well-posed and consistent
with a continuum Laplace equation. Furthermore, in the well-posed setting we
prove quantitative error estimates of $O(\varepsilon\beta^{-1/2})$ for the
difference between the solutions of the discrete problem and continuum PDE, up
to logarithmic factors. We also study $p$-Laplacian regularization and show the
same degeneracy result when $\beta \ll \varepsilon^p$. The proofs of our
well-posedness results use the random walk interpretation of Laplacian learning
and PDE arguments, while the proofs of the ill-posedness results use
$\Gamma$-convergence tools from the calculus of variations. We also present
numerical results on synthetic and real data to illustrate our results.
- Abstract(参考訳): グラフベースラプラシアン半教師付き学習を低ラベルレートで検討した。
ラプラシアン学習はグラフ上の調和拡張を使ってラベルを伝播する。
非常に低いラベルレートでは、ラプラシアン学習は縮退し、各ラベル付きデータポイントのスパイクで解は概ね一定となる。
前回の研究では、ラベル付きデータポイントの数は有限であり、ラベル付きデータポイントの数は無限になりがちである。
この作業では、ラベル付きデータポイントの数をラベル数で無限に増やすことを可能にします。
その結果、長さスケール $\varepsilon>0$ とラベリングレート $\beta>0$ のランダム幾何グラフでは、$\beta \ll\varepsilon^2$ で解が縮退しスパイクが形成され、$\beta\gg \varepsilon^2$ であればラプラシアン学習は連続ラプラス方程式とよく一致することが示された。
さらに、よく仮定された設定では、離散問題と連続PDEの解の差に対して$O(\varepsilon\beta^{-1/2})$の量的誤差推定を対数係数まで証明する。
また、$p$-Laplacian regularization も検討し、$\beta \ll \varepsilon^p$ と同じ縮退結果を示す。
この結果の証明はラプラシアン学習のランダムウォーク解釈とPDE論証を使い、不作為結果の証明は変分法からの$\Gamma$-convergenceツールを使用する。
また, 合成データおよび実データを用いて, 数値的な結果を示す。
関連論文リスト
- A Unified Framework for Uniform Signal Recovery in Nonlinear Generative
Compressed Sensing [68.80803866919123]
非線形測定では、ほとんどの先行結果は一様ではない、すなわち、すべての$mathbfx*$に対してではなく、固定された$mathbfx*$に対して高い確率で保持される。
本フレームワークはGCSに1ビット/一様量子化観測と単一インデックスモデルを標準例として適用する。
また、指標集合が計量エントロピーが低い製品プロセスに対して、より厳密な境界を生み出す濃度不等式も開発する。
論文 参考訳(メタデータ) (2023-09-25T17:54:19Z) - Active Cost-aware Labeling of Streaming Data [11.501619634838312]
本研究では,アクティブな学習者がデータポイントのストリームに直面するストリーミングデータのラベル付けについて検討する。
まず、データ入力が$K$の離散分布の1つに属し、ラベリングコストと予測誤差をキャプチャする損失によってこの問題を定式化する際の設定について検討する。
ラベル付けコストが$B$の場合、不確実性が時間とコスト依存しきい値よりも大きい場合のラベル付けを選択するアルゴリズムは、最悪の$widetildeO(Bfrac1)上限を達成する。
論文 参考訳(メタデータ) (2023-04-13T20:23:27Z) - How Does Pseudo-Labeling Affect the Generalization Error of the
Semi-Supervised Gibbs Algorithm? [73.80001705134147]
擬似ラベル付き半教師付き学習(SSL)におけるGibsアルゴリズムによる予測一般化誤差(ゲンエラー)を正確に評価する。
ゲンエラーは、出力仮説、擬ラベルデータセット、ラベル付きデータセットの間の対称性付きKL情報によって表現される。
論文 参考訳(メタデータ) (2022-10-15T04:11:56Z) - Rates of Convergence for Regression with the Graph Poly-Laplacian [3.222802562733786]
より高次規則性は、ラプラシア正規化器をポリラプラシア正規化器に置き換えることで得られる。
完全教師付き、非パラメトリック、ノイズ劣化、回帰問題におけるグラフポリラプラシア正規化を考察する。
論文 参考訳(メタデータ) (2022-09-06T08:59:15Z) - Bi-stochastically normalized graph Laplacian: convergence to manifold
Laplacian and robustness to outlier noise [8.271859911016719]
双構造正規化グラフ Laplacian to manifold (weighted-)Laplacian は Sinkhorn-Knopp (SK) の反復によって効率的に計算できる。
多様体データが外乱ノイズによって破壊されるとき、理論的にはラプラシア点の整合性を証明する。
論文 参考訳(メタデータ) (2022-06-22T21:08:24Z) - 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) - On quantitative Laplace-type convergence results for some exponential
probability measures, with two applications [2.9189409618561966]
密度 w.r.t ルベーグ測度 $(mathrmd pi_varepsilon)_varepsilon >0$ ルベーグ測度 $(mathrmd pi_varepsilon)_varepsilon >0$ ルベーグ測度 $(mathrmd pi_varepsilon)_varepsilon >0$ ルベーグ測度 $(mathrmd pi_varepsilon)_varepsilon >0$ ルベーグ測度 $(mathrmd)
論文 参考訳(メタデータ) (2021-10-25T13:00:25Z) - Learning Sparse Graph with Minimax Concave Penalty under Gaussian Markov
Random Fields [51.07460861448716]
本稿では,データから学ぶための凸解析フレームワークを提案する。
三角凸分解はその上部に対応する変換によって保証されることを示す。
論文 参考訳(メタデータ) (2021-09-17T17:46:12Z) - Projection-free Graph-based Classifier Learning using Gershgorin Disc
Perfect Alignment [59.87663954467815]
グラフベースのバイナリ学習では、既知のラベルのサブセット$hatx_i$を使って未知のラベルを推論する。
ラベルの$x_i$をバイナリ値に制限する場合、問題はNPハードである。
代わりに線形プログラム(LP)の列を解くことにより,高速なプロジェクションフリー手法を提案する。
論文 参考訳(メタデータ) (2021-06-03T07:22:48Z) - Continuum Limit of Lipschitz Learning on Graphs [0.0]
我々は$Gamma$-convergenceを使ってLipschitz学習の連続的限界を証明する。
最小化の収束を意味する関数のコンパクト性を示す。
論文 参考訳(メタデータ) (2020-12-07T15:10:35Z) - Agnostic Learning of a Single Neuron with Gradient Descent [92.7662890047311]
期待される正方形損失から、最も適合した単一ニューロンを学習することの問題点を考察する。
ReLUアクティベーションでは、我々の人口リスク保証は$O(mathsfOPT1/2)+epsilon$である。
ReLUアクティベーションでは、我々の人口リスク保証は$O(mathsfOPT1/2)+epsilon$である。
論文 参考訳(メタデータ) (2020-05-29T07:20:35Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。