論文の概要: Active-LATHE: An Active Learning Algorithm for Boosting the Error
Exponent for Learning Homogeneous Ising Trees
- arxiv url: http://arxiv.org/abs/2110.14341v2
- Date: Thu, 28 Oct 2021 09:47:58 GMT
- ステータス: 処理完了
- システム内更新日: 2021-10-29 12:59:06.913232
- Title: Active-LATHE: An Active Learning Algorithm for Boosting the Error
Exponent for Learning Homogeneous Ising Trees
- Title（参考訳）: Active-LATHE:均質なイジング木を学習するためのエラー指数を高めるアクティブ学習アルゴリズム
- Authors: Fengzhuo Zhang, Anshoo Tandon, Vincent Y. F. Tan
- Abstract要約: 我々は、$rho$が少なくとも0.8$である場合に、エラー指数を少なくとも40%向上させるアルゴリズムを設計し、分析する。
我々の分析は、グラフの一部により多くのデータを割り当てるために、微小だが検出可能なサンプルの統計的変動を巧みに活用することに基づいている。
- 参考スコア（独自算出の注目度）: 75.93186954061943
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The Chow-Liu algorithm (IEEE Trans.~Inform.~Theory, 1968) has been a mainstay
for the learning of tree-structured graphical models from i.i.d.\ sampled data
vectors. Its theoretical properties have been well-studied and are
well-understood. In this paper, we focus on the class of trees that are
arguably even more fundamental, namely {\em homogeneous} trees in which each
pair of nodes that forms an edge has the same correlation $\rho$. We ask
whether we are able to further reduce the error probability of learning the
structure of the homogeneous tree model when {\em active learning} or {\em
active sampling of nodes or variables} is allowed. Our figure of merit is the
{\em error exponent}, which quantifies the exponential rate of decay of the
error probability with an increasing number of data samples. At first sight, an
improvement in the error exponent seems impossible, as all the edges are
statistically identical. We design and analyze an algorithm Active Learning
Algorithm for Trees with Homogeneous Edge (Active-LATHE), which surprisingly
boosts the error exponent by at least 40\% when $\rho$ is at least $0.8$. For
all other values of $\rho$, we also observe commensurate, but more modest,
improvements in the error exponent. Our analysis hinges on judiciously
exploiting the minute but detectable statistical variation of the samples to
allocate more data to parts of the graph in which we are less confident of
being correct.
- Abstract（参考訳）: Chow-Liu アルゴリズム (IEEE Trans.~Inform.〜Theory, 1968) は、木構造図形モデルをサンプルデータベクトルから学習するための主要な手段である。
その理論的性質はよく研究され、よく理解されている。
本稿では、辺を形成する各ノードの対が同じ相関値$\rho$を持つような、より基本的な木、すなわち「同質な木」のクラスに焦点をあてる。
我々は、"em active learning} または "em active sampling of node or variable} が許可された場合、均質木モデルの構造を学習するエラー確率を更に低減できるかどうかを問う。
我々の図形は、誤差確率の指数的な崩壊率をデータサンプル数の増加とともに定量化する、誤差指数である。
一見すると、すべてのエッジが統計的に同一であるため、エラー指数の改善は不可能に思える。
我々は,均質なエッジ(active-lathe)を持つ木に対するアルゴリズムアクティブラーニングアルゴリズムの設計と解析を行い,$\rho$ が少なくとも$0.8$ の場合,誤差指数を 40 % 以上向上させる。
$\rho$の他のすべての値に対して、私たちはまた、より控えめな、エラー指数の改善も観察します。
我々の分析は、サンプルの微小だが検出可能な統計的な変動を利用して、より多くのデータをグラフの一部に割り当てることにかかっています。
関連論文リスト
- Efficient Graph Matching for Correlated Stochastic Block Models [7.320365821066744]
2つのバランスの取れたコミュニティを持つ相関ブロックモデルの学習問題について検討する。
我々の主な成果は、この設定におけるグラフマッチングのための最初の効率的なアルゴリズムである。
我々はこれを情報理論的に可能であれば、正確なグラフマッチングのための効率的なアルゴリズムに拡張する。
論文 参考訳（メタデータ） (2024-12-03T18:36:45Z) - Neural network learns low-dimensional polynomials with SGD near the information-theoretic limit [75.4661041626338]
単一インデックス対象関数 $f_*(boldsymbolx) = textstylesigma_*left(langleboldsymbolx,boldsymbolthetarangleright)$ の勾配勾配勾配学習問題について検討する。
SGDに基づくアルゴリズムにより最適化された2層ニューラルネットワークは、情報指数に支配されない複雑さで$f_*$を学習する。
論文 参考訳（メタデータ） (2024-06-03T17:56:58Z) - NodeFormer: A Scalable Graph Structure Learning Transformer for Node
Classification [70.51126383984555]
本稿では,任意のノード間のノード信号を効率的に伝搬する全ペアメッセージパッシング方式を提案する。
効率的な計算は、カーナライズされたGumbel-Softmax演算子によって実現される。
グラフ上のノード分類を含む様々なタスクにおいて,本手法の有望な有効性を示す実験を行った。
論文 参考訳（メタデータ） (2023-06-14T09:21:15Z) - How Does Pseudo-Labeling Affect the Generalization Error of the
Semi-Supervised Gibbs Algorithm? [73.80001705134147]
擬似ラベル付き半教師付き学習(SSL)におけるGibsアルゴリズムによる予測一般化誤差(ゲンエラー)を正確に評価する。
ゲンエラーは、出力仮説、擬ラベルデータセット、ラベル付きデータセットの間の対称性付きKL情報によって表現される。
論文 参考訳（メタデータ） (2022-10-15T04:11:56Z) - Simple Stochastic and Online Gradient DescentAlgorithms for Pairwise
Learning [65.54757265434465]
ペアワイズ学習(Pairwise learning)とは、損失関数がペアインスタンスに依存するタスクをいう。
オンライン降下(OGD)は、ペアワイズ学習でストリーミングデータを処理する一般的なアプローチである。
本稿では,ペアワイズ学習のための手法について,シンプルでオンラインな下降を提案する。
論文 参考訳（メタデータ） (2021-11-23T18:10:48Z) - Decentralized Learning of Tree-Structured Gaussian Graphical Models from
Noisy Data [1.52292571922932]
本稿では,木構造ガウス図形モデル(GGM)の雑音データからの分散学習について検討する。
GGMは遺伝子制御ネットワークやソーシャルネットワークのような複雑なネットワークをモデル化するために広く利用されている。
提案した分散学習では,木構造GGMの推定にChow-Liuアルゴリズムを用いる。
論文 参考訳（メタデータ） (2021-09-22T10:41:18Z) - Chow-Liu++: Optimal Prediction-Centric Learning of Tree Ising Models [30.62276301751904]
我々は、Chow-Liuアルゴリズムの要素とツリーメートル法を組み合わせた新しいアルゴリズムを提案する。
我々のアルゴリズムは不特定性や敵の腐敗をモデル化するのに堅牢である。
論文 参考訳（メタデータ） (2021-06-07T21:09:29Z) - SGA: A Robust Algorithm for Partial Recovery of Tree-Structured
Graphical Models with Noisy Samples [75.32013242448151]
ノードからの観測が独立しているが非識別的に分散ノイズによって破損した場合、Ising Treeモデルの学習を検討する。
Katiyarら。
(2020) は, 正確な木構造は復元できないが, 部分木構造を復元できることを示した。
統計的に堅牢な部分木回復アルゴリズムであるSymmetrized Geometric Averaging(SGA)を提案する。
論文 参考訳（メタデータ） (2021-01-22T01:57:35Z) - Sample-Optimal and Efficient Learning of Tree Ising models [24.201827888085944]
最適な$O(n ln n/epsilon2)$サンプルから,$n$-variable tree-structured Isingモデルが全変動距離$epsilon$の範囲内で計算効率良く学習可能であることを示す。
我々の保証は、Chow-Liuアルゴリズムの既知の結果に従わない。
論文 参考訳（メタデータ） (2020-10-28T10:17:48Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。