Fugu-MT 論文翻訳(概要): Tree Learning: Optimal Algorithms and Sample Complexity

論文の概要: Tree Learning: Optimal Algorithms and Sample Complexity

arxiv url: http://arxiv.org/abs/2302.04492v1
Date: Thu, 9 Feb 2023 08:35:17 GMT
ステータス: 処理完了
システム内更新日: 2023-02-10 16:29:11.458465
Title: Tree Learning: Optimal Algorithms and Sample Complexity
Title（参考訳）: ツリー学習:最適なアルゴリズムとサンプル複雑さ
Authors: Dmitrii Avdiukhin, Grigory Yaroslavtsev, Danny Vainstein, Orr Fischer, Sauman Das, Faraz Mirza
Abstract要約: 任意の分布から抽出したラベル付きサンプルから,データの階層木表現を学習する問題について検討する。本稿では,この問題に対する最適なサンプル境界を,学習やオンライン学習など,いくつかの学習環境において提示する。
参考スコア（独自算出の注目度）: 10.638365461509
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: We study the problem of learning a hierarchical tree representation of data from labeled samples, taken from an arbitrary (and possibly adversarial) distribution. Consider a collection of data tuples labeled according to their hierarchical structure. The smallest number of such tuples required in order to be able to accurately label subsequent tuples is of interest for data collection in machine learning. We present optimal sample complexity bounds for this problem in several learning settings, including (agnostic) PAC learning and online learning. Our results are based on tight bounds of the Natarajan and Littlestone dimensions of the associated problem. The corresponding tree classifiers can be constructed efficiently in near-linear time.
Abstract（参考訳）: ラベル付きサンプルから,任意の(おそらくは逆)分布から抽出したデータの階層的ツリー表現を学習する問題について検討する。階層構造に従ってラベル付けされたデータタプルの集合を考える。続くタプルを正確にラベル付けするために必要となるタプルの最小数は、機械学習におけるデータ収集に対する関心である。本稿では,PAC学習とオンライン学習を含むいくつかの学習環境において,この問題に対する最適サンプル複雑性境界を提案する。この結果はナタラジャンの密接な境界と関連する問題のリトルストーン次元に基づいている。対応する木分類器は、ほぼ直線時間で効率的に構築することができる。

関連論文リスト

Discovering Data Structures: Nearest Neighbor Search and Beyond [18.774836778996544]
データ構造をエンド・ツー・エンドで学習するための一般的なフレームワークを提案する。我々のフレームワークは、基礎となるデータ分布に適応し、クエリと空間の複雑さをきめ細やかな制御を提供する。まず、この枠組みを近接探索問題に適用する。
論文参考訳（メタデータ） (2024-11-05T16:50:54Z)
Learning accurate and interpretable decision trees [27.203303726977616]
我々は、同じドメインから繰り返しデータにアクセスして決定木学習アルゴリズムを設計するためのアプローチを開発する。本研究では,ベイズ決定木学習における事前パラメータのチューニングの複雑さについて検討し,その結果を決定木回帰に拡張する。また、学習した決定木の解釈可能性について検討し、決定木を用いた説明可能性と精度のトレードオフを最適化するためのデータ駆動型アプローチを提案する。
論文参考訳（メタデータ） (2024-05-24T20:10:10Z)
Optimal Sample Complexity of Contrastive Learning [12.108926584457736]
比較学習の複雑さ、すなわち、高い精度を得るのに十分なラベル付き一般化の最小数について研究する。我々は、任意の距離関数に焦点をあてて、様々な設定でサンプルの複雑さに厳密な境界を与える。本稿では,VC/ナタラジャンによる試料の複雑さに関する理論的境界が,実験結果に強い予測力を持つことを示す。
論文参考訳（メタデータ） (2023-12-01T06:57:11Z)
Learning bounded-degree polytrees with known skeleton [15.137372516678143]
有界次数ポリツリーの効率的な適切な学習のための有限サンプル保証を確立する。基礎となる無向グラフが知られているとき、d$-polytreesを時間で学習し、任意の有界$d$のサンプル複雑性を学習する効率的なアルゴリズムを提供する。
論文参考訳（メタデータ） (2023-10-10T06:03:51Z)
Information-Computation Tradeoffs for Learning Margin Halfspaces with Random Classification Noise [50.64137465792738]
ランダム分類ノイズを用いたPAC$gamma$-marginハーフスペースの問題について検討する。我々は、問題のサンプル複雑性と計算効率の良いアルゴリズムのサンプル複雑性との間に固有のギャップを示唆する情報計算トレードオフを確立する。
論文参考訳（メタデータ） (2023-06-28T16:33:39Z)
Hierarchical clustering with dot products recovers hidden tree structure [53.68551192799585]
本稿では,階層構造の回復に着目した凝集クラスタリングアルゴリズムの新しい視点を提案する。クラスタを最大平均点積でマージし、例えば最小距離やクラスタ内分散でマージしないような、標準的なアルゴリズムの単純な変種を推奨する。このアルゴリズムにより得られた木は、汎用確率的グラフィカルモデルの下で、データ中の生成的階層構造をボナフェイド推定することを示した。
論文参考訳（メタデータ） (2023-05-24T11:05:12Z)
Dive into Layers: Neural Network Capacity Bounding using Algebraic Geometry [55.57953219617467]
ニューラルネットワークの学習性はそのサイズと直接関連していることを示す。入力データとニューラルネットワークのトポロジ的幾何学的複雑さを測定するためにベッチ数を用いる。実世界のデータセットMNISTで実験を行い、分析結果と結論を検証した。
論文参考訳（メタデータ） (2021-09-03T11:45:51Z)
Robustifying Algorithms of Learning Latent Trees with Vector Variables [92.18777020401484]
Recursive Grouping (RG) と Chow-Liu Recursive Grouping (CLRG) のサンプル複雑性について述べる。 RG,CLRG,Neighbor Joining (NJ) およびSpectral NJ (SNJ) をトラッピングした内積を用いて強化する。我々は、潜在木の構造学習において、最初の既知のインスタンス依存の不合理性の結果を導出する。
論文参考訳（メタデータ） (2021-06-02T01:37:52Z)
Probabilistic Label Trees for Extreme Multi-label Classification [8.347190888362194]
極端なマルチラベル分類(XMLC)の問題は,木としてラベルを整理することで効率的に処理される。 PLTは多ラベル問題に対する階層的ソフトマックスの一般化として扱うことができる。このモデルを導入し、トレーニングと推論手順とその計算コストについて論じる。完全にオンラインのアルゴリズムと木構造を持つアルゴリズムとの間には,特定の等価性があることを実証する。
論文参考訳（メタデータ） (2020-09-23T15:30:00Z)
Forest R-CNN: Large-Vocabulary Long-Tailed Object Detection and Instance Segmentation [75.93960390191262]
我々は、オブジェクトカテゴリ間の関係に関する事前知識を利用して、きめ細かいクラスを粗い親クラスにクラスタリングする。そこで本研究では,NMS再サンプリング法を提案する。提案手法はフォレストR-CNNと呼ばれ,ほとんどのオブジェクト認識モデルに適用可能なプラグイン・アンド・プレイモジュールとして機能する。
論文参考訳（メタデータ） (2020-08-13T03:52:37Z)
OSLNet: Deep Small-Sample Classification with an Orthogonal Softmax Layer [77.90012156266324]
本稿では,ニューラルネットワークのサブスペースを見つけることを目的としている。そこで本研究では,Orthogonal Softmax Layer (OSL) を提案する。実験結果から,提案OSLは4つの小サンプルベンチマークデータセットとの比較に用いた手法よりも優れた性能を示した。
論文参考訳（メタデータ） (2020-04-20T02:41:01Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。