論文の概要: Trading off Consistency and Dimensionality of Convex Surrogates for the
Mode
- arxiv url: http://arxiv.org/abs/2402.10818v1
- Date: Fri, 16 Feb 2024 16:42:09 GMT
- ステータス: 処理完了
- システム内更新日: 2024-02-19 15:03:04.177536
- Title: Trading off Consistency and Dimensionality of Convex Surrogates for the
Mode
- Title(参考訳): コンベックス・サロゲートのモードにおける整合性と寸法のトレードオフ
- Authors: Enrique Nueve, Bo Waggoner, Dhamma Kimpara, Jessie Finocchiaro
- Abstract要約: 結果が$n$以上の多重クラス分類では、結果は少なくとも次元が$n-1$の実数に埋め込まれなければならない。
本稿では,サロゲート損失次元のトレードオフ,問題インスタンス数,単純度における一貫性領域の制限について検討する。
整合性を持つ各点の質量分布の周りには、単純体の実次元部分集合が存在するが、$n-1$次元に満たない場合、幻覚と呼ばれる現象が起こる分布が存在することを示す。
- 参考スコア(独自算出の注目度): 6.096888891865663
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: In multiclass classification over $n$ outcomes, the outcomes must be embedded
into the reals with dimension at least $n-1$ in order to design a consistent
surrogate loss that leads to the "correct" classification, regardless of the
data distribution. For large $n$, such as in information retrieval and
structured prediction tasks, optimizing a surrogate in $n-1$ dimensions is
often intractable. We investigate ways to trade off surrogate loss dimension,
the number of problem instances, and restricting the region of consistency in
the simplex for multiclass classification. Following past work, we examine an
intuitive embedding procedure that maps outcomes into the vertices of convex
polytopes in a low-dimensional surrogate space. We show that full-dimensional
subsets of the simplex exist around each point mass distribution for which
consistency holds, but also, with less than $n-1$ dimensions, there exist
distributions for which a phenomenon called hallucination occurs, which is when
the optimal report under the surrogate loss is an outcome with zero
probability. Looking towards application, we derive a result to check if
consistency holds under a given polytope embedding and low-noise assumption,
providing insight into when to use a particular embedding. We provide examples
of embedding $n = 2^{d}$ outcomes into the $d$-dimensional unit cube and $n =
d!$ outcomes into the $d$-dimensional permutahedron under low-noise
assumptions. Finally, we demonstrate that with multiple problem instances, we
can learn the mode with $\frac{n}{2}$ dimensions over the whole simplex.
- Abstract(参考訳): 結果が$n$以上の多重クラス分類では、結果がデータ分布に関係なく「正しい」分類につながる一貫した代理損失を設計するために、少なくとも$n-1$の次元を持つ実数に埋め込まれなければならない。
情報検索や構造化予測タスクのような大きな$n$の場合、$n-1$次元の代理を最適化することは、しばしば難解である。
マルチクラス分類において,サロゲート損失次元のトレードオフ,問題インスタンス数,単純度における一貫性領域の制限について検討する。
過去の研究に続いて,低次元サロゲート空間における凸ポリトープの頂点に結果をマッピングする直感的な埋め込み手法を検討した。
完全次元部分集合は、一貫性が保たれる各点質量分布の周りに存在するが、n-1$次元未満では、幻覚と呼ばれる現象が起こるような分布が存在し、それは代理損失の下での最適報告がゼロ確率の結果である。
アプリケーションに目を向けると、特定のポリトープの埋め込みと低ノイズの仮定の下で一貫性が保たれるかどうかを確認する結果が導出されます。
我々は、$n = 2^{d}$の結果を $d$-dimensional unit cube と $n = d!
低ノイズの仮定の下で、$d$-dimensional permutahedron に結果を与える。
最後に、複数の問題インスタンスで、simplex全体に対して$\frac{n}{2}$次元でモードを学習できることを実証する。
関連論文リスト
- Computational-Statistical Gaps in Gaussian Single-Index Models [77.1473134227844]
単次元モデル(Single-Index Models)は、植木構造における高次元回帰問題である。
我々は,統計的クエリ (SQ) と低遅延多項式 (LDP) フレームワークの両方において,計算効率のよいアルゴリズムが必ずしも$Omega(dkstar/2)$サンプルを必要とすることを示した。
論文 参考訳(メタデータ) (2024-03-08T18:50:19Z) - Optimal Multi-Distribution Learning [94.73322179348332]
マルチディストリビューション学習は、$k$の異なるデータ分散における最悪のリスクを最小限に抑える共有モデルを学ぶことを目指している。
本稿では,$(d+k)/varepsilon2$の順に,サンプルの複雑さを伴って,$varepsilon$-optimal randomized hypothesisを生成するアルゴリズムを提案する。
論文 参考訳(メタデータ) (2023-12-08T16:06:29Z) - Effective Minkowski Dimension of Deep Nonparametric Regression: Function
Approximation and Statistical Theories [70.90012822736988]
ディープ非パラメトリック回帰に関する既存の理論は、入力データが低次元多様体上にある場合、ディープニューラルネットワークは本質的なデータ構造に適応できることを示した。
本稿では,$mathcalS$で表される$mathbbRd$のサブセットに入力データが集中するという緩和された仮定を導入する。
論文 参考訳(メタデータ) (2023-06-26T17:13:31Z) - How many dimensions are required to find an adversarial example? [0.0]
敵の脆弱性が$dim(V)$に依存するかを検討する。
特に、$ellp$ノルム制約による標準PGD攻撃の対角的成功は、$epsilonの単調に増加する関数のように振る舞うことを示す。
論文 参考訳(メタデータ) (2023-03-24T17:36:15Z) - Pseudonorm Approachability and Applications to Regret Minimization [73.54127663296906]
我々は、高次元 $ell_infty$-approachability 問題を、低次元の擬ノルムアプローチ可能性問題に変換する。
我々は、$ell$や他のノルムに対するアプローチ可能性に関する以前の研究に類似した疑似ノルムアプローチ可能性のアルゴリズム理論を開発する。
論文 参考訳(メタデータ) (2023-02-03T03:19:14Z) - Best Policy Identification in Linear MDPs [70.57916977441262]
縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。
複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
論文 参考訳(メタデータ) (2022-08-11T04:12:50Z) - Randomized Dimensionality Reduction for Facility Location and
Single-Linkage Clustering [13.208510864854894]
ランダム次元削減は高次元問題に対するアルゴリズムを高速化するための多用途ツールである。
本稿では,施設配置問題と単一リンク階層クラスタリング問題という2つのクラスタリング問題への適用について検討する。
論文 参考訳(メタデータ) (2021-07-05T05:55:26Z) - $k$-Variance: A Clustered Notion of Variance [23.57925128327]
我々は,ランダム二成分マッチングの機構に基づく分散の一般化である $k$-variance を導入する。
1次元測度、クラスター測度、低次元部分集合に集中した測度など、いくつかの重要な場合において、この量の詳細分析を行う。
論文 参考訳(メタデータ) (2020-12-13T04:25:32Z) - Adversarial Classification: Necessary conditions and geometric flows [0.7614628596146599]
本研究では,ある逆数分類法を用いて,ある距離から最大$varepsilon$までデータ入力を不正に入力する逆数分類法について検討する。
我々は、分類境界の変化を$varepsilon$の変分として追跡するために使用できる幾何学的進化方程式を導出する。
論文 参考訳(メタデータ) (2020-11-21T14:14:12Z) - The Generalized Lasso with Nonlinear Observations and Generative Priors [63.541900026673055]
我々は、幅広い測定モデルで満たされるガウス下測度を仮定する。
この結果から, 局所埋込特性を仮定して, 均一回復保証まで拡張できることが示唆された。
論文 参考訳(メタデータ) (2020-06-22T16:43:35Z) - Error bounds in estimating the out-of-sample prediction error using
leave-one-out cross validation in high-dimensions [19.439945058410203]
高次元状態におけるサンプル外リスク推定の問題について検討する。
広範囲にわたる経験的証拠は、アウト・ワン・アウト・クロス・バリデーションの正確さを裏付ける。
この理論の技術的利点の1つは、拡張可能な近似LOに関する最近の文献から得られたいくつかの結果を明確化し、接続することができることである。
論文 参考訳(メタデータ) (2020-03-03T20:07:07Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。