論文の概要: An efficient, provably exact, practical algorithm for the 0-1 loss
linear classification problem
- arxiv url: http://arxiv.org/abs/2306.12344v2
- Date: Wed, 2 Aug 2023 21:22:26 GMT
- ステータス: 処理完了
- システム内更新日: 2023-08-04 16:36:04.143275
- Title: An efficient, provably exact, practical algorithm for the 0-1 loss
linear classification problem
- Title（参考訳）: 0-1損失線形分類問題に対する効率的、確証的、実用的なアルゴリズム
- Authors: Xi He, Waheed Ul Rahman, Max A. Little
- Abstract要約: インクリメンタルセル(ICE)は,0-1損失分類問題を正確に時間内に解くことができることを示す。
この長年の問題に対する、厳格に証明された実用的なアルゴリズムとしては、これが初めてだ。
- 参考スコア（独自算出の注目度）: 4.418462313508022
- 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 rigorous construction of a new
algorithm, incremental cell enumeration (ICE), that can solve the 0-1 loss
classification problem exactly in polynomial time. We prove correctness using
concepts from the theory of hyperplane arrangements and oriented matroids. We
demonstrate the effectiveness of this algorithm on synthetic and real-world
datasets, showing optimal accuracy both in and out-of-sample, in practical
computational time. We also empirically demonstrate how the use of approximate
upper bound leads to polynomial time run-time improvements to the algorithm
whilst retaining exactness. To our knowledge, this is the first,
rigorously-proven polynomial time, practical 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。