論文の概要: A Machine Learning Approach to Solving Large Bilevel and Stochastic
Programs: Application to Cycling Network Design
- arxiv url: http://arxiv.org/abs/2209.09404v2
- Date: Tue, 3 Oct 2023 03:28:44 GMT
- ステータス: 処理完了
- システム内更新日: 2023-10-05 11:11:17.894040
- Title: A Machine Learning Approach to Solving Large Bilevel and Stochastic
Programs: Application to Cycling Network Design
- Title(参考訳): 大規模プログラムと確率プログラムを解く機械学習アプローチ:サイクリングネットワーク設計への応用
- Authors: Timothy C. Y. Chan, Bo Lin, Shoshanna Saxe
- Abstract要約: 我々は、多数の独立したフォロワーを含むバイレベルプログラムを解決するための、機械学習に基づく新しいアプローチを提案する。
機械学習モデルを用いて、アンサンプされたフォロワーの客観的な価値を推定する。
我々のアプローチは、追従者の客観的価値をより正確に予測し、さらに重要なのは、より高い品質のリーダー決定を生成することです。
- 参考スコア(独自算出の注目度): 4.599618895656792
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We present a novel machine learning-based approach to solving bilevel
programs that involve a large number of independent followers, which as a
special case include two-stage stochastic programming. We propose an
optimization model that explicitly considers a sampled subset of followers and
exploits a machine learning model to estimate the objective values of unsampled
followers. Unlike existing approaches, we embed machine learning model training
into the optimization problem, which allows us to employ general follower
features that can not be represented using leader decisions. We prove bounds on
the optimality gap of the generated leader decision as measured by the original
objective function that considers the full follower set. We then develop
follower sampling algorithms to tighten the bounds and a representation
learning approach to learn follower features, which can be used as inputs to
the embedded machine learning model. Using synthetic instances of a cycling
network design problem, we compare the computational performance of our
approach versus baseline methods. Our approach provides more accurate
predictions for follower objective values, and more importantly, generates
leader decisions of higher quality. Finally, we perform a real-world case study
on cycling infrastructure planning, where we apply our approach to solve a
network design problem with over one million followers. Our approach presents
favorable performance compared to the current cycling network expansion
practices.
- Abstract(参考訳): 本稿では,2段階確率計画を含む,多数の独立系フォロワーを含むバイレベルプログラムを解決するための,機械学習に基づく新しい手法を提案する。
本研究では,フォロワーのサンプリングされたサブセットを明示的に考慮し,機械学習モデルを用いて非サンプリングフォロワーの客観的値を推定する最適化モデルを提案する。
既存のアプローチとは異なり、機械学習モデルのトレーニングを最適化問題に組み込むことで、リーダー決定で表現できない一般的なフォロワー機能を利用することができます。
我々は、全従者集合を考える元の目的関数によって測定される生成したリーダー決定の最適性ギャップの境界を証明する。
次に,境界を厳格化するためのフォロワサンプリングアルゴリズムと,組込み機械学習モデルへの入力として使用できるフォロワ特徴を学習するための表現学習手法を開発した。
サイクリングネットワーク設計問題の合成例を用いて,本手法の計算性能とベースライン法との比較を行った。
我々のアプローチは、フォロー対象の値に対するより正確な予測を提供し、さらに重要なことに、より高い品質のリーダー決定を生成する。
最後に、サイクリングインフラ計画の現実的なケーススタディを行い、100万人以上のフォロワーを持つネットワーク設計問題を解決するために我々のアプローチを適用します。
提案手法は,現在のサイクリングネットワーク拡張方式と比較して,良好な性能を示す。
関連論文リスト
- Let's reward step by step: Step-Level reward model as the Navigators for
Reasoning [64.27898739929734]
Process-Supervised Reward Model (PRM)は、トレーニングフェーズ中にステップバイステップのフィードバックをLLMに提供する。
LLMの探索経路を最適化するために,PRMからのステップレベルのフィードバックを応用した欲求探索アルゴリズムを提案する。
提案手法の汎用性を探るため,コーディングタスクのステップレベル報酬データセットを自動生成する手法を開発し,コード生成タスクにおける同様の性能向上を観察する。
論文 参考訳(メタデータ) (2023-10-16T05:21:50Z) - Online Network Source Optimization with Graph-Kernel MAB [62.6067511147939]
大規模ネットワークにおける最適なソース配置をオンラインで学習するためのグラフカーネルマルチアームバンディットアルゴリズムであるGrab-UCBを提案する。
適応グラフ辞書モデルを用いて,ネットワークプロセスを記述する。
我々は、ネットワークパラメータに依存する性能保証を導出し、シーケンシャルな意思決定戦略の学習曲線にさらに影響を及ぼす。
論文 参考訳(メタデータ) (2023-07-07T15:03:42Z) - End-to-End Meta-Bayesian Optimisation with Transformer Neural Processes [52.818579746354665]
本稿では,ニューラルネットワークを一般化し,トランスフォーマーアーキテクチャを用いて獲得関数を学習する,エンド・ツー・エンドの差別化可能な最初のメタBOフレームワークを提案する。
我々は、この強化学習(RL)によるエンドツーエンドのフレームワークを、ラベル付き取得データの欠如に対処できるようにします。
論文 参考訳(メタデータ) (2023-05-25T10:58:46Z) - Graph Reinforcement Learning for Network Control via Bi-Level
Optimization [37.00510744883984]
我々は、データ駆動戦略がこのプロセスを自動化し、最適性を損なうことなく効率的なアルゴリズムを学習できると主張している。
我々は、強化学習のレンズを通してネットワーク制御の問題を提示し、幅広い問題に対処するグラフネットワークベースのフレームワークを提案する。
論文 参考訳(メタデータ) (2023-05-16T03:20:22Z) - Representation Learning with Multi-Step Inverse Kinematics: An Efficient
and Optimal Approach to Rich-Observation RL [106.82295532402335]
既存の強化学習アルゴリズムは、計算的難易度、強い統計的仮定、最適なサンプルの複雑さに悩まされている。
所望の精度レベルに対して、レート最適サンプル複雑性を実現するための、最初の計算効率の良いアルゴリズムを提供する。
我々のアルゴリズムMusIKは、多段階の逆運動学に基づく表現学習と体系的な探索を組み合わせる。
論文 参考訳(メタデータ) (2023-04-12T14:51:47Z) - Probabilistic Bilevel Coreset Selection [24.874967723659022]
本稿では,各トレーニングサンプルの確率的重みを学習することにより,コアセット選択の連続確率的2レベル定式化を提案する。
暗黙的な微分の問題を伴わずに、偏りのない政策勾配を経由し、二段階最適化問題に対する効率的な解法を開発する。
論文 参考訳(メタデータ) (2023-01-24T09:37:00Z) - Towards Automated Imbalanced Learning with Deep Hierarchical
Reinforcement Learning [57.163525407022966]
不均衡学習はデータマイニングにおいて基本的な課題であり、各クラスにトレーニングサンプルの不均等な比率が存在する。
オーバーサンプリングは、少数民族のための合成サンプルを生成することによって、不均衡な学習に取り組む効果的な手法である。
我々は,異なるレベルの意思決定を共同で最適化できる自動オーバーサンプリングアルゴリズムであるAutoSMOTEを提案する。
論文 参考訳(メタデータ) (2022-08-26T04:28:01Z) - Unsupervised Learning for Combinatorial Optimization with Principled
Objective Relaxation [19.582494782591386]
本研究は,最適化(CO)問題に対する教師なし学習フレームワークを提案する。
我々の重要な貢献は、緩和された目的がエントリーワイドな凹凸を満たすならば、低い最適化損失は最終積分解の品質を保証するという観察である。
特に、この観察は、対象が明示的に与えられていないアプリケーションにおいて、事前にモデル化される必要がある場合に、対象モデルの設計を導くことができる。
論文 参考訳(メタデータ) (2022-07-13T06:44:17Z) - Model-Based Deep Learning: On the Intersection of Deep Learning and
Optimization [101.32332941117271]
決定アルゴリズムは様々なアプリケーションで使われている。
数理モデルに頼らずにデータから調整された高度パラメトリックアーキテクチャを使用するディープラーニングアプローチが、ますます人気が高まっている。
モデルに基づく最適化とデータ中心のディープラーニングは、しばしば異なる規律とみなされる。
論文 参考訳(メタデータ) (2022-05-05T13:40:08Z) - Learning Curves for Decision Making in Supervised Machine Learning -- A
Survey [9.994200032442413]
学習曲線は、機械学習の文脈で採用されている社会科学の概念である。
本稿では,学習曲線のアプローチを3つの基準を用いて分類する枠組みを提案する。
論文 参考訳(メタデータ) (2022-01-28T14:34:32Z) - Scalable Approximate Inference and Some Applications [2.6541211006790983]
本稿では,近似推論のための新しいフレームワークを提案する。
提案する4つのアルゴリズムは,Steinの手法の最近の計算進歩に動機付けられている。
シミュレーションおよび実データを用いた結果から,アルゴリズムの統計的効率と適用性を示す。
論文 参考訳(メタデータ) (2020-03-07T04:33:27Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。