論文の概要: 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を線形分類器として使用することや、シンプルマージンとして知られる情報に基づくサンプリング戦略を考えることができる。 我々は,混合整数二次計画法に基づく別のサンプリング手法と,オラクルモデルにおける凸最適化アルゴリズムにインスパイアされた線形分離法を提案する。 本研究は, 純クナップサック問題と大学研究計画問題に関する実験を行い, 異なる線形分離法とサンプリング手法が, 目的値の点から結果の質にどのように影響するかを示す。

関連論文リスト

• Learning-augmented smooth integer programs with PAC-learnable oracles [6.4126799144358975]
  予測オラクルを組み込んだフレームワークを導入し、目的の線形サロゲートを構築し、線形プログラミングによって解決する。 提案手法は,古典的な高密度政権から近距離政権へ効果的にトラクタブル近似を拡張できることを実証する。 帰納的アルゴリズムが有界擬似次元を持つことを証明し、ほぼ最適性能のオラクルを学習できるようにする。
  論文  参考訳（メタデータ） (2026-01-22T05:55:36Z)
• Randomized multi-class classification under system constraints: a unified approach via post-processing [8.354034992258482]
  ランダム化分類器上での線形汎関数として表現可能なシステムレベルの制約下でのマルチクラス分類の問題について検討する。 本稿では,与えられたベース分類器を調整し,再学習せずに一般制約を満たすポストプロセッシング手法を提案する。
  論文  参考訳（メタデータ） (2025-12-16T09:53:22Z)
• Online Inference of Constrained Optimization: Primal-Dual Optimality and Sequential Quadratic Programming [55.848340925419286]
  等式制約と不等式制約を持つ2次最適化問題の解に対するオンライン統計的推測について検討した。 これらの問題を解決するための逐次プログラミング(SSQP)手法を開発し、目的の近似と制約の線形近似を逐次実行することでステップ方向を計算する。 本手法は,Hjek と Le Cam の意味での最適原始双対制限行列を用いて局所正規性を示す。
  論文  参考訳（メタデータ） (2025-11-27T06:16:17Z)
• Single-loop Algorithms for Stochastic Non-convex Optimization with Weakly-Convex Constraints [49.76332265680669]
  本稿では、目的関数と制約関数の両方が弱凸である問題の重要な部分集合について検討する。 既存の手法では、収束速度の遅さや二重ループ設計への依存など、しばしば制限に直面している。 これらの課題を克服するために,新しい単一ループペナルティに基づくアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2025-04-21T17:15:48Z)
• 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)
• Bilevel Optimization for Feature Selection in the Data-Driven Newsvendor Problem [8.281391209717105]
  本稿では、意思決定者が過去のデータにアクセス可能な機能ベースのニュースベンダー問題について検討する。 そこで本研究では,スパースモデル,説明可能なモデル,およびアウト・オブ・サンプル性能の改善を目的とした特徴選択について検討する。 本稿では,2レベルプログラムに対する混合整数線形プログラムの修正について述べる。
  論文  参考訳（メタデータ） (2022-09-12T08:52:26Z)
• Smoothed Online Learning is as Easy as Statistical Learning [77.00766067963195]
  この設定では、最初のオラクル効率、非回帰アルゴリズムを提供する。 古典的な設定で関数クラスが学習可能な場合、文脈的包帯に対するオラクル効率のよい非回帰アルゴリズムが存在することを示す。
  論文  参考訳（メタデータ） (2022-02-09T19:22:34Z)
• A Lagrangian Duality Approach to Active Learning [119.36233726867992]
  トレーニングデータのサブセットのみをラベル付けするバッチアクティブな学習問題を考察する。 制約付き最適化を用いて学習問題を定式化し、各制約はラベル付きサンプルにモデルの性能を拘束する。 数値実験により,提案手法は最先端の能動学習法と同等かそれ以上に機能することを示した。
  論文  参考訳（メタデータ） (2022-02-08T19:18:49Z)
• Learning Proximal Operators to Discover Multiple Optima [66.98045013486794]
  非家族問題における近位演算子を学習するためのエンドツーエンド手法を提案する。 本手法は,弱い目的と穏やかな条件下では,世界規模で収束することを示す。
  論文  参考訳（メタデータ） (2022-01-28T05:53:28Z)
• 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)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。