論文の概要: Actively Learning Combinatorial Optimization Using a Membership Oracle
- arxiv url: http://arxiv.org/abs/2405.14090v2
- Date: Fri, 26 Jul 2024 19:14:26 GMT
- ステータス: 処理完了
- システム内更新日: 2024-07-30 23:08:21.985825
- Title: Actively Learning Combinatorial Optimization Using a Membership Oracle
- Title（参考訳）: 会員制Oracleによる組合せ最適化のアクティブラーニング
- Authors: Rosario Messana, Rui Chen, Andrea Lodi,
- Abstract要約: 会員オラクルを用いて未知の線形制約を用いて最適化問題を解くことを検討する。
意思決定者の目標は、オラクルの呼び出し数に関する予算の対象となる最善の解決策を見つけることである。
代用線形制約を学習し、活用することで問題を解決するために、古典的なフレームワークを適応させる。
- 参考スコア（独自算出の注目度）: 10.834947136134463
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We consider solving a combinatorial optimization problem with an unknown linear constraint using a membership oracle that, given a solution, determines whether it is feasible or infeasible with absolute certainty. The goal of the decision maker is to find the best possible solution subject to a budget on the number of oracle calls. Inspired by active learning based on Support Vector Machines (SVMs), we adapt a classical framework in order to solve the problem by learning and exploiting a surrogate linear constraint. The resulting new framework includes training a linear separator on the labeled points and selecting new points to be labeled, which is achieved by applying a sampling strategy and solving a 0-1 integer linear program. Following the active learning literature, one can consider using SVM as a linear classifier and the information-based sampling strategy known as Simple margin. We improve on both sides: we propose an alternative sampling strategy based on mixed-integer quadratic programming and a linear separation method inspired by an algorithm for convex optimization in the oracle model. We conduct experiments on the pure knapsack problem and on a college study plan problem from the literature to show how different linear separation methods and sampling strategies influence the quality of the results in terms of objective value.
- Abstract（参考訳）: 我々は、解が与えられた場合、それが絶対的確実性で実現可能か不可能かを判断する会員オラクルを用いて、未知の線形制約で組合せ最適化問題を解くことを検討する。
意思決定者の目標は、オラクルの呼び出し数に関する予算の対象となる最善の解決策を見つけることである。
SVM(Support Vector Machines)に基づく能動的学習に着想を得て,代用線形制約を学習し,活用することによって問題を解決するために,古典的なフレームワークを適用した。
得られた新しいフレームワークは、ラベル付きポイント上で線形分離器を訓練し、ラベル付けされる新しいポイントを選択することを含み、サンプリング戦略を適用し、0-1整数線形プログラムを解くことで達成される。
アクティブラーニングの文献に従えば、SVMを線形分類器として使用することや、シンプルマージンとして知られる情報に基づくサンプリング戦略を考えることができる。
我々は,混合整数二次計画法に基づく別のサンプリング手法と,オラクルモデルにおける凸最適化アルゴリズムにインスパイアされた線形分離法を提案する。
本研究は, 純クナップサック問題と大学研究計画問題に関する実験を行い, 異なる線形分離法とサンプリング手法が, 目的値の点から結果の質にどのように影響するかを示す。
関連論文リスト
- Optimization by Parallel Quasi-Quantum Annealing with Gradient-Based Sampling [0.0]
本研究では、連続緩和による勾配に基づく更新と準量子アナリング(QQA)を組み合わせた別のアプローチを提案する。
数値実験により,本手法はiSCOと学習型解法に匹敵する性能を有する汎用解法であることが示された。
論文 参考訳（メタデータ） (2024-09-02T12:55:27Z) - Take a Step and Reconsider: Sequence Decoding for Self-Improved Neural Combinatorial Optimization [1.1510009152620668]
自己改善学習のための単純で問題に依存しないシーケンス復号法を提案する。
以前にサンプリングされたシーケンスを無視するためにポリシーを変更することで、目に見えない代替案のみを検討するように強制する。
本手法は,ジョブショップスケジューリング問題における従来のNCO手法よりも優れていた。
論文 参考訳（メタデータ） (2024-07-24T12:06:09Z) - Feature selection in linear SVMs via hard cardinality constraint: a scalable SDP decomposition approach [3.7876216422538485]
線形支援ベクトルマシン(SVM)における組込み特徴選択問題について検討する。
濃度制約が適用され、完全に説明可能な選択モデルが導かれる。
問題は、濃度制約が存在するためNPハードである。
論文 参考訳（メタデータ） (2024-04-15T19:15:32Z) - Multi-Phase Relaxation Labeling for Square Jigsaw Puzzle Solving [73.58829980121767]
本稿では,大域最適化に基づく二乗ジグソーパズルの解法を提案する。
この手法は完全に自動化されており、事前情報を前提とせず、未知または未知のピースオリエンテーションでパズルを扱うことができる。
論文 参考訳（メタデータ） (2023-03-26T18:53:51Z) - Linearization Algorithms for Fully Composite Optimization [61.20539085730636]
本稿では,完全合成最適化問題を凸コンパクト集合で解くための一階アルゴリズムについて検討する。
微分可能および非微分可能を別々に扱い、滑らかな部分のみを線形化することで目的の構造を利用する。
論文 参考訳（メタデータ） (2023-02-24T18:41:48Z) - A Lagrangian Duality Approach to Active Learning [119.36233726867992]
トレーニングデータのサブセットのみをラベル付けするバッチアクティブな学習問題を考察する。
制約付き最適化を用いて学習問題を定式化し、各制約はラベル付きサンプルにモデルの性能を拘束する。
数値実験により,提案手法は最先端の能動学習法と同等かそれ以上に機能することを示した。
論文 参考訳（メタデータ） (2022-02-08T19:18:49Z) - A Bi-Level Framework for Learning to Solve Combinatorial Optimization on
Graphs [91.07247251502564]
本稿では,2つの世界の長所を結合するハイブリッドな手法を提案する。この手法では,グラフを最適化する上層学習手法とバイレベルフレームワークを開発する。
このような二段階のアプローチは、元のハードCOでの学習を単純化し、モデルキャパシティの需要を効果的に軽減することができる。
論文 参考訳（メタデータ） (2021-06-09T09:18:18Z) - On the Adversarial Robustness of LASSO Based Feature Selection [72.54211869067979]
検討されたモデルでは、悪意のある敵がデータセット全体を観察し、レスポンス値やフィーチャーマトリックスを慎重に修正する。
両レベルの最適化問題として、敵の修正戦略を定式化する。
合成および実データを用いた数値的な例は,本手法が効率的かつ効果的であることを示している。
論文 参考訳（メタデータ） (2020-10-20T05:51:26Z) - Decomposition and Adaptive Sampling for Data-Driven Inverse Linear
Optimization [12.610576072466895]
この研究は、線形プログラムの未知のコストベクトルを推論することが目的である逆線形最適化に対処する。
本稿では,既存の手法と比較して,制約の少ない,一般的に許容可能なコスト見積の集合の回復を可能にする,新たな問題の定式化を導入する。
論文 参考訳（メタデータ） (2020-09-16T22:25:31Z) - Sparse Methods for Automatic Relevance Determination [0.0]
まず、自動妥当性決定(ARD)について検討し、スパースモデルを実現するために、追加の正規化やしきい値設定の必要性を解析的に実証する。
次に、正規化ベースとしきい値ベースという2つの手法のクラスについて論じる。
論文 参考訳（メタデータ） (2020-05-18T14:08:49Z) - Progressive Identification of True Labels for Partial-Label Learning [112.94467491335611]
部分ラベル学習(Partial-label Learning, PLL)は、典型的な弱教師付き学習問題であり、各トレーニングインスタンスには、真のラベルである候補ラベルのセットが設けられている。
既存のほとんどの手法は、特定の方法で解決しなければならない制約付き最適化として精巧に設計されており、計算複雑性をビッグデータにスケールアップするボトルネックにしている。
本稿では,モデルと最適化アルゴリズムの柔軟性を備えた分類器の新しいフレームワークを提案する。
論文 参考訳（メタデータ） (2020-02-19T08:35:15Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。