論文の概要: 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$の他のすべての値に対して、私たちはまた、より控えめな、エラー指数の改善も観察します。
我々の分析は、サンプルの微小だが検出可能な統計的な変動を利用して、より多くのデータをグラフの一部に割り当てることにかかっています。
関連論文リスト
- 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) - A cautionary tale on fitting decision trees to data from additive
models: generalization lower bounds [9.546094657606178]
本研究では,異なる回帰モデルに対する決定木の一般化性能について検討する。
これにより、アルゴリズムが新しいデータに一般化するために(あるいは作らない)仮定する帰納的バイアスが引き起こされる。
スパース加法モデルに適合する大規模な決定木アルゴリズムに対して、シャープな2乗誤差一般化を低い境界で証明する。
論文 参考訳（メタデータ） (2021-10-18T21:22:40Z) - 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) - Outlier-Robust Learning of Ising Models Under Dobrushin's Condition [57.89518300699042]
本研究では, サンプルの一定割合が逆向きに破壊されるような外乱条件下で, ドブルシンの条件を満たすIsingモデルの学習問題について検討する。
我々の主な成果は、ほぼ最適誤差保証を伴うこの問題に対して、計算効率のよい最初の頑健な学習アルゴリズムを提供することである。
論文 参考訳（メタデータ） (2021-02-03T18:00:57Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。