論文の概要: An efficient, provably exact algorithm for the 0-1 loss linear classification problem

• arxiv url: http://arxiv.org/abs/2306.12344v1
• Date: Wed, 21 Jun 2023 15:41:34 GMT
• ステータス: 処理完了
• システム内更新日: 2023-06-22 12:49:08.413411
• Title: An efficient, provably exact algorithm for the 0-1 loss linear classification problem
• Title（参考訳）: 0-1損失線形分類問題に対する効率的で確証可能な厳密なアルゴリズム
• Authors: Xi He, Max A. Little
• Abstract要約: 我々は,0-1損失分類問題を正確に解ける新しいアルゴリズムであるインクリメンタルセル列挙法(ICE)の構築について詳述する。 私たちの知る限りでは、これはこの長年の問題に対して厳格に証明された最初の時間アルゴリズムである。
• 参考スコア（独自算出の注目度）: 5.219827902658495
• License: http://creativecommons.org/licenses/by-sa/4.0/
• Abstract: Algorithms for solving the linear classification problem have a long history, dating back at least to 1936 with linear discriminant analysis. For linearly separable data, many algorithms can obtain the exact solution to the corresponding 0-1 loss classification problem efficiently, but for data which is not linearly separable, it has been shown that this problem, in full generality, is NP-hard. Alternative approaches all involve approximations of some kind, including the use of surrogates for the 0-1 loss (for example, the hinge or logistic loss) or approximate combinatorial search, none of which can be guaranteed to solve the problem exactly. Finding efficient algorithms to obtain an exact i.e. globally optimal solution for the 0-1 loss linear classification problem with fixed dimension, remains an open problem. In research we report here, we detail the construction of a new algorithm, incremental cell enumeration (ICE), that can solve the 0-1 loss classification problem exactly in polynomial time. To our knowledge, this is the first, rigorously-proven polynomial time algorithm for this long-standing problem.
• Abstract（参考訳）: 線形分類問題を解くアルゴリズムには長い歴史があり、少なくとも1936年に線形判別解析で遡る。 線形分離可能なデータの場合、多くのアルゴリズムは対応する0-1損失分類問題の正確な解を効率的に得ることができるが、線形分離できないデータに対しては、この問題が完全一般性においてnpハードであることが示されている。 別のアプローチでは、0-1 の損失(ヒンジやロジスティックの損失など)に対するサロゲートの使用や近似組合せ探索など、何らかの近似を含む。 固定次元の 0-1 損失線形分類問題に対して、正確な解を得るための効率的なアルゴリズムを見つけることは、未解決の問題である。 本稿では,0-1の損失分類問題を多項式時間で正確に解くための新しいアルゴリズム,インクリメンタルセル列挙法(ice)の構築について述べる。 我々の知る限り、これはこの長年の問題に対して厳密に証明された初めての多項式時間アルゴリズムである。

関連論文リスト

• Discretize Relaxed Solution of Spectral Clustering via a Non-Heuristic Algorithm [77.53604156112144]
  我々は、元の問題と離散化アルゴリズムを橋渡しする1次項を開発する。 非ヒューリスティック法は元のグラフ切断問題を認識しているため、最終的な離散解の方が信頼性が高い。
  論文  参考訳（メタデータ） (2023-10-19T13:57:38Z)
• Accelerating Cutting-Plane Algorithms via Reinforcement Learning Surrogates [49.84541884653309]
  凸離散最適化問題に対する現在の標準的なアプローチは、カットプレーンアルゴリズムを使うことである。 多くの汎用カット生成アルゴリズムが存在するにもかかわらず、大規模な離散最適化問題は、難易度に悩まされ続けている。 そこで本研究では,強化学習による切削平面アルゴリズムの高速化手法を提案する。
  論文  参考訳（メタデータ） (2023-07-17T20:11:56Z)
• A Data-Driven Line Search Rule for Support Recovery in High-dimensional Data Analysis [5.180648702293017]
  適切なステップサイズを適応的に決定する新しい,効率的なデータ駆動行探索法を提案する。 線形回帰問題とロジスティック回帰問題における最先端アルゴリズムとの比較は,提案アルゴリズムの安定性,有効性,優越性を示す。
  論文  参考訳（メタデータ） (2021-11-21T12:18:18Z)
• Graph Matching via Optimal Transport [11.93151370164898]
  グラフマッチング問題の解決は、運用研究、コンピュータビジョン、神経科学などへの応用により、ますます重要になっている。 現在の最先端のアルゴリズムは、非常に大きなグラフのマッチングには非効率であるが、精度は高い。 我々は,最新のグラフマッチングアルゴリズム "FAQ" (Vogelstein, 2015) を改良した GOAT を,その線形和割り当てステップを Cuturi (2013) の "Lightspeed Optimal Transport" メソッドに置き換える。
  論文  参考訳（メタデータ） (2021-11-09T19:18:18Z)
• PROMPT: Parallel Iterative Algorithm for $\ell_{p}$ norm linear regression via Majorization Minimization with an application to semi-supervised graph learning [0.0]
  スパースリカバリ,データクラスタリング,半教師付き学習など,いくつかの応用がある。 我々は、MajolizaTion Minimization (PROMPT)による$ell_P$ノルム回帰のための並列反復AlgOrithMを提案する。
  論文  参考訳（メタデータ） (2021-10-23T10:19:11Z)
• Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
  本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。 問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。 本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-01-07T08:00:02Z)
• Online Model Selection for Reinforcement Learning with Function Approximation [50.008542459050155]
  我々は、$tildeO(L5/6 T2/3)$ regretで最適な複雑性に適応するメタアルゴリズムを提案する。 また、メタアルゴリズムは、インスタンス依存の後悔境界を著しく改善することを示す。
  論文  参考訳（メタデータ） (2020-11-19T10:00:54Z)
• Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth Nonlinear TD Learning [145.54544979467872]
  本稿では,各ステップごとに1つのデータポイントしか必要としない2つの単一スケールシングルループアルゴリズムを提案する。 本研究の結果は, 同時一次および二重側収束の形で表される。
  論文  参考訳（メタデータ） (2020-08-23T20:36:49Z)
• Private Stochastic Convex Optimization: Optimal Rates in Linear Time [74.47681868973598]
  本研究では,凸損失関数の分布から得られた個体群損失を最小化する問題について検討する。 Bassilyらによる最近の研究は、$n$のサンプルを与えられた過剰な人口損失の最適境界を確立している。 本稿では,余剰損失に対する最適境界を達成するとともに,$O(minn, n2/d)$グラデーション計算を用いて凸最適化アルゴリズムを導出する2つの新しい手法について述べる。
  論文  参考訳（メタデータ） (2020-05-10T19:52:03Z)
• Learning Sparse Classifiers: Continuous and Mixed Integer Optimization Perspectives [10.291482850329892]
  混合整数計画法(MIP)は、(最適に) $ell_0$-正規化回帰問題を解くために用いられる。 数分で5万ドルの機能を処理できる正確なアルゴリズムと、$papprox6$でインスタンスに対処できる近似アルゴリズムの2つのクラスを提案する。 さらに,$ell$-regularizedsに対する新しい推定誤差境界を提案する。
  論文  参考訳（メタデータ） (2020-01-17T18:47:02Z)

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

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