論文の概要: (Machine) Learning to Improve the Empirical Performance of Discrete
Algorithms
- arxiv url: http://arxiv.org/abs/2109.14271v1
- Date: Wed, 29 Sep 2021 08:33:09 GMT
- ステータス: 処理完了
- システム内更新日: 2021-09-30 14:32:32.639058
- Title: (Machine) Learning to Improve the Empirical Performance of Discrete
Algorithms
- Title（参考訳）: (機械)離散アルゴリズムの実証的性能向上のための学習
- Authors: Imran Adham, Jesus De Loera, Zhenyang Zhang
- Abstract要約: 我々は、人間の専門家の意見なしに、与えられたデータに対して最適なアルゴリズムを選択するために機械学習手法を訓練する。
我々のフレームワークは、固定されたデフォルトのピボットルールを使用するだけで全体のパフォーマンスを改善する様々なピボットルールを推奨しています。
最短経路問題に対して、訓練されたモデルは大幅に改善され、我々の選択は最適な選択から平均.7パーセント離れている。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: This paper discusses a data-driven, empirically-based framework to make
algorithmic decisions or recommendations without expert knowledge. We improve
the performance of two algorithmic case studies: the selection of a pivot rule
for the Simplex method and the selection of an all-pair shortest paths
algorithm. We train machine learning methods to select the optimal algorithm
for given data without human expert opinion. We use two types of techniques,
neural networks and boosted decision trees. We concluded, based on our
experiments, that:
1) Our selection framework recommends various pivot rules that improve
overall total performance over just using a fixed default pivot rule.
Over many years experts identified steepest-edge pivot rule as a favorite
pivot rule. Our data analysis corroborates that the number of iterations by
steepest-edge is no more than 4 percent more than the optimal selection which
corroborates human expert knowledge, but this time the knowledge was obtained
using machine learning. Here our recommendation system is best when using
gradient boosted trees.
2) For the all-pairs shortest path problem, the models trained made a large
improvement and our selection is on average .07 percent away from the optimal
choice. The conclusions do not seem to be affected by the machine learning
method we used.
We tried to make a parallel analysis of both algorithmic problems, but it is
clear that there are intrinsic differences. For example, in the all-pairs
shortest path problem the graph density is a reasonable predictor, but there is
no analogous single parameter for decisions in the Simplex method.
- Abstract（参考訳）: 本稿では,専門家の知識を必要とせず,アルゴリズムによる意思決定や推薦を行うためのデータ駆動型経験ベースフレームワークについて述べる。
我々は,Simplex法におけるピボットルールの選択と,全対最短経路アルゴリズムの選択という,2つのアルゴリズムケーススタディの性能を改善した。
我々は、人間の意見なしに与えられたデータに対して最適なアルゴリズムを選択するために機械学習手法を訓練する。
ニューラルネットワークと強化された決定木という,2種類のテクニックを使用します。
1) 当社の選択フレームワークでは,固定デフォルトのpivotルールのみを使用して,全体的なパフォーマンスを改善するさまざまなpivotルールを推奨しています。
長年にわたり、専門家は最も急なピボットルールをお気に入りのピボットルールと認識していた。
我々のデータ分析では、最も急なエッジによるイテレーションの数は、人間の知識を裏付ける最適な選択よりも4%以上多くないが、今回は機械学習を使って得られた知識を裏付ける。
ここでは,傾斜強調木を用いた推奨システムを提案する。
2) 最短経路問題では, 訓練したモデルが大きく改善され, 我々の選択は, 最適選択から平均.07パーセント離れている。
結論は、私たちが使用している機械学習手法の影響を受けないようです。
2つのアルゴリズム問題の並列解析を試みたが、本質的な違いがあることは明らかである。
例えば、全ペア最短経路問題において、グラフ密度は妥当な予測子であるが、単純な方法において決定のための類似のパラメータは存在しない。
関連論文リスト
- Meta-Learning from Learning Curves for Budget-Limited Algorithm Selection [11.409496019407067]
予算制限のシナリオでは、アルゴリズム候補を慎重に選択し、それを訓練するための予算を割り当てることが不可欠である。
本稿では,エージェントが十分に訓練されるまで待たずに,最も有望なアルゴリズムを学習する過程において,エージェントが選択しなければならない新しい枠組みを提案する。
論文 参考訳（メタデータ） (2024-10-10T08:09:58Z) - Learning the Positions in CountSketch [49.57951567374372]
本稿では,まずランダムなスケッチ行列に乗じてデータを圧縮し,最適化問題を高速に解くスケッチアルゴリズムについて検討する。
本研究では,ゼロでないエントリの位置を最適化する学習ベースアルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-06-11T07:28:35Z) - Efficient and Optimal Algorithms for Contextual Dueling Bandits under
Realizability [59.81339109121384]
我々は,学習者が文脈情報を用いて2つの決定を下す連続的な決定設定であるK$コンテキストデュエルバンディット問題について検討するが,一方の判断が他方よりも優れていることを示唆する強調基準に基づくフィードバックのみを観察する。
提案手法は, 最善応答後悔という新たな概念に対して, 最善応答後悔に対する最適後悔率を実現するアルゴリズムである。
論文 参考訳（メタデータ） (2021-11-24T07:14:57Z) - Leveraging Experience in Lazy Search [37.75223642505171]
遅延グラフ探索アルゴリズムは、エッジ評価が計算ボトルネックとなる動き計画問題の解法において効率的である。
我々は,この問題を探索問題の状態に関するマルコフ決定過程 (MDP) として定式化する。
我々は,訓練中にMDPを解くことができる分子セレクタを計算可能であることを示す。
論文 参考訳（メタデータ） (2021-10-10T00:46:44Z) - Learning Primal Heuristics for Mixed Integer Programs [5.766851255770718]
本研究は,機械学習を用いて効果的な霊長類を自動学習できるかどうかを考察する。
本稿では,最適化問題をグラフとして表現するための新しい手法を提案する。
可変解の予測はB&B法の新たな構成であるProbabilistic Branching with guided Depth-first Searchによって行われる。
論文 参考訳（メタデータ） (2021-07-02T06:46:23Z) - Learning to Sparsify Travelling Salesman Problem Instances [0.5985204759362747]
プルーニングマシンラーニングを前処理のステップとして使用し、旅行セールスマンの問題をスパーシャライズするために正確なプログラミングアプローチを行います。
私たちの学習アプローチは、非常に少ないトレーニングデータを必要とし、数学的分析に適応可能です。
論文 参考訳（メタデータ） (2021-04-19T14:35:14Z) - Double Coverage with Machine-Learned Advice [100.23487145400833]
オンラインの基本的な$k$-serverの問題を学習強化環境で研究する。
我々のアルゴリズムは任意の k に対してほぼ最適の一貫性-破壊性トレードオフを達成することを示す。
論文 参考訳（メタデータ） (2021-03-02T11:04:33Z) - Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。
問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。
本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-01-07T08:00:02Z) - Run2Survive: A Decision-theoretic Approach to Algorithm Selection based
on Survival Analysis [75.64261155172856]
生存分析(SA)は、自然に検閲されたデータをサポートし、アルゴリズムランタイムの分散モデルを学習するためにそのようなデータを使用する適切な方法を提供する。
我々は、アルゴリズム選択に対する洗練された決定論的アプローチの基礎として、そのようなモデルを活用し、Run2Surviveを疑う。
標準ベンチマークASlibによる広範な実験では、我々のアプローチは競争力が高く、多くの場合、最先端のASアプローチよりも優れていることが示されている。
論文 参考訳（メタデータ） (2020-07-06T15:20:17Z) - Learning with Differentiable Perturbed Optimizers [54.351317101356614]
本稿では,操作を微分可能で局所的に一定ではない操作に変換する手法を提案する。
提案手法は摂動に依拠し,既存の解法とともに容易に利用することができる。
本稿では,この枠組みが,構造化予測において発達した損失の族とどのように結びつくかを示し,学習課題におけるそれらの使用に関する理論的保証を与える。
論文 参考訳（メタデータ） (2020-02-20T11:11:32Z) - Optimal Sparse Decision Trees [25.043477914272046]
この研究は、二変数に対する最適決定木のための最初の実用的なアルゴリズムを導入する。
このアルゴリズムは、探索空間と現代のシステム技術を減らす分析的境界の共設計である。
我々の実験はスケーラビリティ、スピード、最適性の証明の利点を強調します。
論文 参考訳（メタデータ） (2019-04-29T17:56:34Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。