論文の概要: 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}$次元でモードを学習できることを実証する。
関連論文リスト
- On Reductions and Representations of Learning Problems in Euclidean Spaces [15.07787640047213]
多くの実用的な予測アルゴリズムはユークリッド空間における入力を表現し、離散的な0/1分類損失を真の自明な代理損失に置き換える。
我々は古典的トポロジカルアプローチと凸性を考慮したボルスク・ウラム理論の一般化を開発する。
また、ランダム性を利用して、より小さな次元で表現できる自然な分類タスクも提示する。
論文 参考訳（メタデータ） (2024-11-16T12:09:37Z) - Better Locally Private Sparse Estimation Given Multiple Samples Per User [2.9562742331218725]
ユーザレベルの局所微分プライベートスパース線形回帰について検討する。
我々は、$n$のユーザがそれぞれ$m$のサンプルを提供していれば、$d$の線形依存を排除できることを示した。
本稿では,まず候補変数を選択し,次に狭義の低次元空間で推定を行うフレームワークを提案する。
論文 参考訳（メタデータ） (2024-08-08T08:47:20Z) - Learning with Norm Constrained, Over-parameterized, Two-layer Neural Networks [54.177130905659155]
近年の研究では、再生カーネルヒルベルト空間(RKHS)がニューラルネットワークによる関数のモデル化に適した空間ではないことが示されている。
本稿では,有界ノルムを持つオーバーパラメータ化された2層ニューラルネットワークに適した関数空間について検討する。
論文 参考訳（メタデータ） (2024-04-29T15:04:07Z) - Computational-Statistical Gaps in Gaussian Single-Index Models [77.1473134227844]
単次元モデル(Single-Index Models)は、植木構造における高次元回帰問題である。
我々は,統計的クエリ (SQ) と低遅延多項式 (LDP) フレームワークの両方において,計算効率のよいアルゴリズムが必ずしも$Omega(dkstar/2)$サンプルを必要とすることを示した。
論文 参考訳（メタデータ） (2024-03-08T18:50:19Z) - 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) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。