論文の概要: Fast Differentiable Sorting and Ranking

• arxiv url: http://arxiv.org/abs/2002.08871v2
• Date: Mon, 29 Jun 2020 23:11:03 GMT
• ステータス: 処理完了
• システム内更新日: 2022-12-30 07:00:56.401544
• Title: Fast Differentiable Sorting and Ranking
• Title（参考訳）: 高速微分可能なソートとランキング
• Authors: Mathieu Blondel, Olivier Teboul, Quentin Berthet, Josip Djolonga
• Abstract要約: 我々は、最初の微分可能なソートおよびランキング演算子を$O(n log n)$ time と $O(n)$ space complexity で提案する。 この偉業は、置換の凸包であるペルムタヘドロンへの射影として微分可能作用素を構築し、等方最適化への還元を用いて達成する。
• 参考スコア（独自算出の注目度）: 36.40586857569459
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The sorting operation is one of the most commonly used building blocks in computer programming. In machine learning, it is often used for robust statistics. However, seen as a function, it is piecewise linear and as a result includes many kinks where it is non-differentiable. More problematic is the related ranking operator, often used for order statistics and ranking metrics. It is a piecewise constant function, meaning that its derivatives are null or undefined. While numerous works have proposed differentiable proxies to sorting and ranking, they do not achieve the $O(n \log n)$ time complexity one would expect from sorting and ranking operations. In this paper, we propose the first differentiable sorting and ranking operators with $O(n \log n)$ time and $O(n)$ space complexity. Our proposal in addition enjoys exact computation and differentiation. We achieve this feat by constructing differentiable operators as projections onto the permutahedron, the convex hull of permutations, and using a reduction to isotonic optimization. Empirically, we confirm that our approach is an order of magnitude faster than existing approaches and showcase two novel applications: differentiable Spearman's rank correlation coefficient and least trimmed squares.
• Abstract（参考訳）: ソート操作は、コンピュータプログラミングにおいて最もよく使われるビルディングブロックの1つである。 機械学習では、しばしば堅牢な統計に使用される。 しかし、函数として見なされ、区分線型であり、その結果、微分不能な多くの公理を含んでいる。 より問題となるのは関連するランキングオペレータで、順序統計やランキング指標によく使用される。 これは一意的に定数関数であり、その微分は null あるいは undefined である。 多くの作品がソートとランキングに微分可能なプロキシを提案しているが、ソートとランキング操作に期待する$o(n \log n)$の複雑さを達成していない。 本稿では、最初に$O(n \log n)$ time と $O(n)$ space complexity を持つ微分可能なソートおよびランク演算子を提案する。 さらに、我々は正確な計算と微分を楽しみます。 この偉業は、置換の凸包であるペルムタヘドロンへの射影として微分可能作用素を構築し、等方最適化への還元を用いて達成する。 経験的に、我々のアプローチは既存のアプローチよりも桁違いに速く、微分可能なスピアマンのランク相関係数と最小トリミング正方形という2つの新しい応用を示す。

関連論文リスト

• Sorting with Predictions [1.7042264000899532]
  学習強化アルゴリズムのレンズをソートする根本的な問題について検討する。 我々は,$O(sum_i log eta_i)$の正確な比較だけで,新しい,シンプルなアルゴリズムを設計する。 比較複雑性は, 検証された誤差測度に対して理論的に最適であることを示す。
  論文  参考訳（メタデータ） (2023-11-01T18:00:03Z)
• Generalized Neural Sorting Networks with Error-Free Differentiable Swap Functions [44.71975181739874]
  より抽象的で表現力に富んだ入力に対するソート問題、例えば、マルチ桁画像や画像フラグメントのソート問題をニューラルネットワークを介して検討する。 高次元入力から順序変数への写像を学習するには、ソートネットワークの微分可能性を保証する必要がある。
  論文  参考訳（メタデータ） (2023-10-11T03:47:34Z)
• Fast, Differentiable and Sparse Top-k: a Convex Analysis Perspective [21.6146047576295]
  トップk演算子はスパースベクトルを返し、非ゼロ値は入力の k 最大の値に対応する。 我々はトップk作用素を、置換の凸包であるペルムタヘドロン上の線形プログラムとみなす。 私たちのフレームワークは既存のフレームワークよりもはるかに汎用的であり、例えば、大まかに値を選択するトップk演算子を表現できる。
  論文  参考訳（メタデータ） (2023-02-02T21:32:13Z)
• Explicit Second-Order Min-Max Optimization Methods with Optimal Convergence Guarantee [86.05440220344755]
  我々は,非制約のmin-max最適化問題のグローバルなサドル点を求めるために,不正確な正規化ニュートン型手法を提案し,解析する。 提案手法は有界集合内に留まるイテレートを生成し、その反復は制限関数の項で$O(epsilon-2/3)$内の$epsilon$-saddle点に収束することを示す。
  論文  参考訳（メタデータ） (2022-10-23T21:24:37Z)
• Monotonic Differentiable Sorting Networks [29.75063301688965]
  異なるソートアルゴリズムは、サンプルの順序付けやランク付けが知られている場合にのみ、ソートとランキング管理によるトレーニングを可能にする。 現在の微分可能なソート法の一つの問題は、それらが単調でないことである。 本稿では,異なるソートネットワークにおける単調性を保証する条件スワップ操作の緩和を提案する。
  論文  参考訳（メタデータ） (2022-03-17T21:51:29Z)
• Beware of the Simulated DAG! Varsortability in Additive Noise Models [70.54639814319096]
  合成データにおける連続構造学習アルゴリズムの性能は,バラエティが如何に支配されているかを示す。 模擬添加ノイズモデルではバラツキが起こりやすいという認識を高めることを目指しています。
  論文  参考訳（メタデータ） (2021-02-26T18:52:27Z)
• PiRank: Learning To Rank via Differentiable Sorting [85.28916333414145]
  ランク付けのための新しい分類可能なサロゲートであるPiRankを提案する。 ピランクは所望の指標をゼロ温度の限界で正確に回収する。
  論文  参考訳（メタデータ） (2020-12-12T05:07:36Z)
• Ranking a set of objects: a graph based least-square approach [70.7866286425868]
  同一労働者の群集によるノイズの多いペアワイズ比較から始まる$N$オブジェクトのランク付けの問題について考察する。 品質評価のために,最小二乗内在的最適化基準に依存する非適応的ランキングアルゴリズムのクラスを提案する。
  論文  参考訳（メタデータ） (2020-02-26T16:19:09Z)
• Differentiable Top-k Operator with Optimal Transport [135.36099648554054]
  SOFTトップk演算子は、エントロピック最適輸送(EOT)問題の解として、トップk演算の出力を近似する。 提案した演算子をk-アネレスト近傍およびビーム探索アルゴリズムに適用し,性能向上を示す。
  論文  参考訳（メタデータ） (2020-02-16T04:57:52Z)

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

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。