論文の概要: Linear Separation via Optimism
- arxiv url: http://arxiv.org/abs/2011.08797v1
- Date: Tue, 17 Nov 2020 17:44:40 GMT
- ステータス: 処理完了
- システム内更新日: 2022-09-24 16:13:25.973296
- Title: Linear Separation via Optimism
- Title（参考訳）: 最適性による線形分離
- Authors: Rafael Hanashiro, Jacob Abernethy
- Abstract要約: 我々は,超平面を$frac1gamma$の更新で分離する簡単な手法であるOptimistic Perceptronアルゴリズムを提案する。
また,この方法がPerceptronより有意に優れていることも実験的に明らかにした。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Binary linear classification has been explored since the very early days of
the machine learning literature. Perhaps the most classical algorithm is the
Perceptron, where a weight vector used to classify examples is maintained, and
additive updates are made as incorrect examples are discovered. The Perceptron
has been thoroughly studied and several versions have been proposed over many
decades. The key theoretical fact about the Perceptron is that, so long as a
perfect linear classifier exists with some margin $\gamma > 0$, the number of
required updates to find such a perfect linear separator is bounded by
$\frac{1}{\gamma^2}$. What has never been fully addressed is: does there exist
an algorithm that can achieve this with fewer updates? In this paper we answer
this in the affirmative: we propose the Optimistic Perceptron algorithm, a
simple procedure that finds a separating hyperplane in no more than
$\frac{1}{\gamma}$ updates. We also show experimentally that this procedure can
significantly outperform Perceptron.
- Abstract（参考訳）: 二項線形分類は、機械学習文学の初期から研究されてきた。
おそらく最も古典的なアルゴリズムはパーセプトロンであり、例を分類するのに使われる重みベクトルが維持され、不正確な例として付加的な更新が行われる。
パーセプトロンは徹底的に研究され、数十年にわたっていくつかのバージョンが提案されてきた。
パーセプトロンに関する重要な理論的事実は、完全線型分類器がいくつかのマージン $\gamma > 0$ を持つ限り、そのような完全線型分離器を見つけるのに必要な更新数は$\frac{1}{\gamma^2}$であるということである。
完全に対処されたことがないのは、より少ない更新でこれを達成するアルゴリズムが存在するか、ということです。
本論文では,これを肯定的に答える。我々は,$\frac{1}{\gamma}$ update 以下で分離超平面を求める単純な手続きである楽観的パーセプトロンアルゴリズムを提案する。
また,この方法がパーセプトロンを著しく上回ることも実験的に示す。
関連論文リスト
- Learning to Relax: Setting Solver Parameters Across a Sequence of Linear System Instances [42.16343861129583]
オンライン学習アルゴリズムでは、シーケンス長が増加するにつれて、全体のコストが最高の$omega$に近づくように、一連のインスタンスに対してパラメータを選択できることが示される。
我々の研究は、高精度線形システム解法の最初の学習理論処理と、データ駆動型科学計算のエンドツーエンド保証を提供する。
論文 参考訳（メタデータ） (2023-10-03T17:51:42Z) - Oracle Efficient Online Multicalibration and Omniprediction [15.476402844435704]
オンライン逆境設定における全方位予測について検討する。
我々は、無限ベンチマーククラス$F$に対してよく定義された新しいオンラインマルチキャリブレーションアルゴリズムを開発した。
我々は、我々のレートが改善できる範囲について、上と下の境界を示す。
論文 参考訳（メタデータ） (2023-07-18T06:34:32Z) - No-Regret Linear Bandits beyond Realizability [34.06789803260447]
報酬関数が線形でない場合の線形帯域について検討する。
既存の作業は、最良の線形近似のsup-norm誤差を測定する均一な不特定パラメータ$epsilon$に依存している。
ここでは、各入力においてx$の近似誤差のみを必要とし、x$の準最適差に比例する、より自然なミス種別モデルを記述する。
論文 参考訳（メタデータ） (2023-02-26T07:15:31Z) - Pseudonorm Approachability and Applications to Regret Minimization [73.54127663296906]
我々は、高次元 $ell_infty$-approachability 問題を、低次元の擬ノルムアプローチ可能性問題に変換する。
我々は、$ell$や他のノルムに対するアプローチ可能性に関する以前の研究に類似した疑似ノルムアプローチ可能性のアルゴリズム理論を開発する。
論文 参考訳（メタデータ） (2023-02-03T03:19:14Z) - On Accelerated Perceptrons and Beyond [17.479295705933698]
RosenblattのPerceptronアルゴリズムは、$n$の線形分離可能なデータポイントを正しく分類する線形しきい値関数を見つけるのに使うことができる。
基本的な結果は、Perceptron が $Omega(sqrtlog n/gamma)$ iterations の後に収束するということである。
最近、より洗練されたアルゴリズムでこの速度を2乗係数で$Omega(sqrtlog n/gamma)$に改善する研究がいくつかある。
論文 参考訳（メタデータ） (2022-10-17T19:12:30Z) - Scalable Differentially Private Clustering via Hierarchically Separated
Trees [82.69664595378869]
我々は,最大$O(d3/2log n)cdot OPT + O(k d2 log2 n / epsilon2)$,$epsilon$はプライバシ保証であることを示す。
最悪の場合の保証は、最先端のプライベートクラスタリング手法よりも悪いが、提案するアルゴリズムは実用的である。
論文 参考訳（メタデータ） (2022-06-17T09:24:41Z) - Matrix Completion via Non-Convex Relaxation and Adaptive Correlation
Learning [90.8576971748142]
閉形式解によって最適化できる新しいサロゲートを開発する。
そこで我々は, 上向きの相関関係を利用して, 適応的相関学習モデルを構築した。
論文 参考訳（メタデータ） (2022-03-04T08:50:50Z) - Linear-Sample Learning of Low-Rank Distributions [56.59844655107251]
ktimes k$, rank-r$, matrices to normalized $L_1$ distance requires $Omega(frackrepsilon2)$ sample。
我々は、$cal O(frackrepsilon2log2fracepsilon)$ sample, a number linear in the high dimension, and almost linear in the matrices, usually low, rank proofs.というアルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-09-30T19:10:32Z) - Improving predictions of Bayesian neural nets via local linearization [79.21517734364093]
ガウス・ニュートン近似は基礎となるベイズニューラルネットワーク(BNN)の局所線形化として理解されるべきである。
この線形化モデルを後部推論に使用するので、元のモデルではなく、この修正モデルを使用することも予測すべきである。
この修正された予測を"GLM predictive"と呼び、Laplace近似の共通不適合問題を効果的に解決することを示す。
論文 参考訳（メタデータ） (2020-08-19T12:35:55Z) - The Strategic Perceptron [11.078814063722803]
正であると分類されたい戦略エージェントが存在する場合、パーセプトロンアルゴリズムはエージェントの真の位置を観察できないかもしれない。
2つの解の間に永久に振動する予測器の例を示す。
私たちの主な貢献は、戦略エージェントの存在下で多くの誤りを犯すPerceptronスタイルのアルゴリズムの修正です。
論文 参考訳（メタデータ） (2020-08-04T17:20:24Z) - A new regret analysis for Adam-type algorithms [78.825194932103]
理論的には、オンライン凸最適化に対する後悔の保証は、急速に崩壊する$beta_1to0$スケジュールを必要とする。
最適なデータ依存リセット境界を一定の$beta_1$で導出できる新しいフレームワークを提案する。
論文 参考訳（メタデータ） (2020-03-21T19:19:51Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。