論文の概要: On the Dual Formulation of Boosting Algorithms
- arxiv url: http://arxiv.org/abs/0901.3590v7
- Date: Sat, 27 May 2023 06:50:26 GMT
- ステータス: 処理完了
- システム内更新日: 2023-05-31 05:32:53.033181
- Title: On the Dual Formulation of Boosting Algorithms
- Title(参考訳): ブースティングアルゴリズムの双対定式化について
- Authors: Chunhua Shen and Hanxi Li
- Abstract要約: AdaBoost,LogitBoost,Soft-marginBoostのラグランジュ問題は、すべて一般化されたヒンジ損失エントロピーの双対問題であることを示す。
これらのブースティングアルゴリズムの2つの問題を見て、より良いマージン分布を維持するという観点から、ブースティングの成功を理解することができることを示す。
- 参考スコア(独自算出の注目度): 92.74617630106559
- License: http://creativecommons.org/licenses/by-nc-nd/4.0/
- Abstract: We study boosting algorithms from a new perspective. We show that the
Lagrange dual problems of AdaBoost, LogitBoost and soft-margin LPBoost with
generalized hinge loss are all entropy maximization problems. By looking at the
dual problems of these boosting algorithms, we show that the success of
boosting algorithms can be understood in terms of maintaining a better margin
distribution by maximizing margins and at the same time controlling the margin
variance.We also theoretically prove that, approximately, AdaBoost maximizes
the average margin, instead of the minimum margin. The duality formulation also
enables us to develop column generation based optimization algorithms, which
are totally corrective. We show that they exhibit almost identical
classification results to that of standard stage-wise additive boosting
algorithms but with much faster convergence rates. Therefore fewer weak
classifiers are needed to build the ensemble using our proposed optimization
technique.
- Abstract(参考訳): 我々は新しい視点からブースティングアルゴリズムを研究する。
AdaBoost,LogitBoost,および一般化ヒンジ損失を持つソフトマージンLPBoostのラグランジュ双対問題はエントロピー最大化問題である。
これらの促進アルゴリズムの二重問題から, マージンの最大化とマージン分散の制御により, マージン分布の良さを両立させることで, 促進アルゴリズムの成功を理解できることが示され, 理論上はAdaBoostが最小マージンではなく平均マージンを最大化することを示した。
二重性定式化により,カラム生成に基づく最適化アルゴリズムの開発も可能である。
本研究は, 標準段差加法アルゴリズムとほぼ同一の分類結果を示すが, 収束速度ははるかに高速であることを示す。
したがって,提案する最適化手法を用いてアンサンブルを構築するためには,弱い分類器は少ない。
関連論文リスト
- A Single-Loop Algorithm for Decentralized Bilevel Optimization [12.75011523756594]
そこで本研究では,分散化された二段階最適化を低レベルに凸した単一ループアルゴリズムを提案する。
我々のアルゴリズムは完全に単ループであり、過次勾配を近似する際に重い行列ベクトル乗法を必要としない。
解析の結果,提案アルゴリズムはサブ線形収束率が得られることがわかった。
論文 参考訳(メタデータ) (2023-11-15T13:29:49Z) - Accelerating Cutting-Plane Algorithms via Reinforcement Learning
Surrogates [49.84541884653309]
凸離散最適化問題に対する現在の標準的なアプローチは、カットプレーンアルゴリズムを使うことである。
多くの汎用カット生成アルゴリズムが存在するにもかかわらず、大規模な離散最適化問題は、難易度に悩まされ続けている。
そこで本研究では,強化学習による切削平面アルゴリズムの高速化手法を提案する。
論文 参考訳(メタデータ) (2023-07-17T20:11:56Z) - Accelerated First-Order Optimization under Nonlinear Constraints [73.2273449996098]
我々は、制約付き最適化のための一階アルゴリズムと非滑らかなシステムの間で、新しい一階アルゴリズムのクラスを設計する。
これらのアルゴリズムの重要な性質は、制約がスパース変数の代わりに速度で表されることである。
論文 参考訳(メタデータ) (2023-02-01T08:50:48Z) - Fast Computation of Optimal Transport via Entropy-Regularized
Extragradient Methods [98.85583323658366]
2つの分布間の最適な輸送距離の効率的な計算は、様々な応用を促進するアルゴリズムとして機能する。
本稿では,$varepsilon$加法精度で最適な輸送を計算できるスケーラブルな一階最適化法を提案する。
論文 参考訳(メタデータ) (2023-01-30T15:46:39Z) - Boosting as Frank-Wolfe [0.6875312133832078]
フランク=ウルフアルゴリズムと任意の二次アルゴリズムを組み合わせた汎用的なブースティング手法を提案する。
ERLPBoost や C-ERLPBoost と同じ収束保証を維持していることを示す。
論文 参考訳(メタデータ) (2022-09-22T07:36:55Z) - Provably Faster Algorithms for Bilevel Optimization [54.83583213812667]
バイレベル最適化は多くの重要な機械学習アプリケーションに広く適用されている。
両レベル最適化のための2つの新しいアルゴリズムを提案する。
両アルゴリズムが$mathcalO(epsilon-1.5)$の複雑さを達成し,既存のアルゴリズムを桁違いに上回っていることを示す。
論文 参考訳(メタデータ) (2021-06-08T21:05:30Z) - MP-Boost: Minipatch Boosting via Adaptive Feature and Observation
Sampling [0.0]
MP-BoostはAdaBoostを緩くベースとしたアルゴリズムで、インスタンスと機能の小さなサブセットを適応的に選択することで学習する。
様々な二項分類タスクにおいて,提案手法の解釈可能性,比較精度,計算時間について実験的に検証した。
論文 参考訳(メタデータ) (2020-11-14T04:26:13Z) - An Asymptotically Optimal Primal-Dual Incremental Algorithm for
Contextual Linear Bandits [129.1029690825929]
複数の次元に沿った最先端技術を改善する新しいアルゴリズムを提案する。
非文脈線形帯域の特別な場合において、学習地平線に対して最小限の最適性を確立する。
論文 参考訳(メタデータ) (2020-10-23T09:12:47Z) - Fully-Corrective Gradient Boosting with Squared Hinge: Fast Learning
Rates and Early Stopping [29.485528641599018]
本稿では,二項分類の理論的一般化を保証する効率的なブースティング手法を提案する。
提案手法に対して,$cal O((m/log m)-1/4)$の高速学習率を導出する。
どちらの学習率も、分類のためのブースティング型手法の既存の一般化結果の中で最良である。
論文 参考訳(メタデータ) (2020-04-01T00:39:24Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。