Upgrade to Pro
— share decks privately, control downloads, hide ads and more …
Speaker Deck
Features
Speaker Deck
PRO
Sign in
Sign up for free
Search
Search
機械学習と数理最適化の融合-文脈付き確率的最短路を例として-
Search
MIKIO KUBO
April 30, 2024
Research
2
850
機械学習と数理最適化の融合-文脈付き確率的最短路を例として-
機械学習と数理最適化の融合-文脈付き確率的最短路を例として-
MIKIO KUBO
April 30, 2024
Tweet
Share
More Decks by MIKIO KUBO
See All by MIKIO KUBO
AMPL詳細解説
mickey_kubo
1
21
Markdown言語入門
mickey_kubo
1
10
Githubをはじめよう 初心者向け完全ガイド
mickey_kubo
1
3
生成AI時代の必須教養であるマーメイドについて解説
mickey_kubo
1
12
新プロンプトエンジニアリング⼊⾨(⼤規模⾔語モデル(LLM)の可能性を最⼤限に引き出す技術)
mickey_kubo
2
50
Sreamlit総合解説
mickey_kubo
1
3
Difyをはじめよう!
mickey_kubo
1
2
「エージェントって何?」から「実際の開発現場で役立つ考え方やベストプラクティス」まで
mickey_kubo
0
8
MOAI Lab紹介
mickey_kubo
0
51
Other Decks in Research
See All in Research
資産間の相関関係を頑健に評価する指標を用いたファクターアローケーション戦略の構築
nomamist
0
200
NLP2025参加報告会 LT資料
hargon24
1
300
NLP2025 WS Shared Task 文法誤り訂正部門 ehiMetrick
sugiyamaseiji
0
170
Mathematics in the Age of AI and the 4 Generation University
hachama
0
150
Intrinsic Self-Supervision for Data Quality Audits
fabiangroeger
0
510
Weekly AI Agents News! 1月号 アーカイブ
masatoto
1
270
Vision Language Modelと完全自動運転AIの最新動向
tsubasashi
2
450
CSP: Self-Supervised Contrastive Spatial Pre-Training for Geospatial-Visual Representations
satai
3
140
ラムダ計算の拡張に基づく 音楽プログラミング言語mimium とそのVMの実装
tomoyanonymous
0
450
公立高校入試等に対する受入保留アルゴリズム(DA)導入の提言
shunyanoda
0
3.2k
[論文紹介] iTransformer: Inverted Transformers Are Effective for Time Series Forecasting
shiba4839
0
150
The Economics of Platforms 輪読会 第1章
tomonatu8
0
170
Featured
See All Featured
YesSQL, Process and Tooling at Scale
rocio
172
14k
Responsive Adventures: Dirty Tricks From The Dark Corners of Front-End
smashingmag
251
21k
[RailsConf 2023] Rails as a piece of cake
palkan
54
5.5k
RailsConf 2023
tenderlove
30
1.1k
Producing Creativity
orderedlist
PRO
344
40k
ReactJS: Keep Simple. Everything can be a component!
pedronauck
667
120k
Rails Girls Zürich Keynote
gr2m
94
13k
Imperfection Machines: The Place of Print at Facebook
scottboms
267
13k
The Cost Of JavaScript in 2023
addyosmani
49
7.8k
A better future with KSS
kneath
239
17k
The Language of Interfaces
destraynor
158
25k
A designer walks into a library…
pauljervisheath
205
24k
Transcript
機械学習と最適化の融合 ⽂脈付き確率的最適化 と最短路を例として Mikio Kubo
確率的最短路問題 あなたは家(始点s)から⼤学(終点t)まで⾞で通勤している.⾼ 速を使う道 (s,1), (2,t)を使うと最短2時間で着くが,混雑するときに は6時間かかる.授業開始までTmax (=5) 時間の余裕があるが,でき るだけ早く着きたい.どのような経路を選択すれば良いだろうか? 移動時間
s t 1 2 1 3.5 1.5 確率 ½ で 3 確率 ½ で 1 確率 ½ で 3 確率 ½ で 1
期待値による最適化 パス s => 1 => t が最適 (期待値は4) s
t 1 2 1 3.5 1.5 期待値2 確率 ½ で 3 確率 ½ で 1 期待値 2 確率 ½ で 3 確率 ½ で 1 枝 の移動時間が独⽴と仮定 3+3 = 6 確率 ¼ 3+1 or 1+3 =4 確率 ½ 1+1 = 2 確率 ¼ 確率 ¼ で実⾏不能 (Tmax=5)
確率的最適化の解 パス s => 2 => t が最適 (期待値は 3.5
+ 1.5 = 5) s t 1 2 1 3.5 1.5 期待値2 確率 ½ で 3 確率 ½ で 1 期待値 2 確率 ½ で 3 確率 ½ で 1 Tmax=5のときの唯⼀の実⾏可能解
その他の解 パス s => 1=> 2 => t が最適 (期待値は
(5.5 + 3.5)/2 = 4.5) s t 1 2 1 3.5 1.5 期待値2 確率 ½ で 3 確率 ½ で 1 期待値 2 確率 ½ で 3 確率 ½ で 1 Tmax=5.5のときの最適解 枝 の移動時間が独⽴と仮定 3+1+1.5 = 5.5 確率 ½ 1+1+1.5 = 3.5 確率 ½ 確率 ½ で実⾏不能 (Tmax=5)
リコース解 事前にパスを決めておく即時決定 (here & now) でなく,途中の情報でパス を変えて良い待機決定(wait & see; リコース)
点1まで移動し,s=>1 の移動時間が1なら 1=> t,移動時間が3なら 1=>2=>t を選ぶ(期待値は (5.5 + 2)/2 = 3.75) s t 1 2 1 3.5 1.5 期待値2 確率 ½ で 3 確率 ½ で 1 期待値 2 確率 ½ で 3 確率 ½ で 1 枝の移動時間が同⼀と仮定 1+1 = 2 確率 ½ 3+1+1.5 = 5.5 確率 ½ Tmax=5.5のときの最適⽅策
⽂脈付き予測・最適化 過去の天気(context; ⽂脈)と移動時間のデータをもっている.天気予 報は当たっているとしたとき移動時間を予測し,それをもとに経路を選 択したい.(単に予測してから最適化は「期待値を最⼩化」と同じ.) s t 1 2 1
3.5 1.5 過去のデータ ☀ 1,1,1,3,1,1,… ☂ 3,3,1,3,3,1,… 過去のデータ ☀ 1,1,3,1,1,1,… ☂ 1,3,1,3,3,3,… ⽂脈 F = ☀ ☂ ̂ 𝑐 = 𝐸 𝑐 𝐹 ] F の条件下での移動費⽤ c の予測値 ☂ ̂ 𝑐 = 2.5 ☀ ̂ 𝑐 = 1.5
⽂脈付き予測・最適化 (1) 費⽤の実現値をもとに最適化した場合との差をロス関数として機械学習 (Smart Prediction-then-Optimize) 最適解オラクル 実現値 c が既知のときの最適値 𝑧∗
𝑐 = min "∈$ 𝑐%𝑥 ☀で実現値が移動時間 3 の場合 𝐿𝑂𝑆𝑆 ̂ 𝑐, 𝑐 = 𝑐!𝑥∗ - 𝑐 − 𝑧∗ 𝑐 = 3 + 3 − 3.5 + 1.5 = 1 SPOロス(⾮凸) 𝑥∗ s t 1 2 1 3.5 1.5 ☀ ̂ 𝑐 = 1.5 ☀ ̂ 𝑐 = 1.5 𝑥∗ ( 𝑐 s t 1 2 1 3.5 1.5 ☀ c = 3 ☀ c = 3 𝑥∗(𝑐)
⽂脈付き予測・最適化 (2) 𝐿𝑂𝑆𝑆# ̂ 𝑐, 𝑐 = max { $∈&
𝑐!𝑥 − 2 ̂ 𝑐!𝑥 } + 2 ̂ 𝑐!𝑥∗ 𝑐 − 𝑧∗ 𝑐 SPO+ロス(凸) SPOロスの上界 線形最適化 データ 解 機械学習 SPO+ロス F 𝐿𝑂𝑆𝑆! ̂ 𝑐, 𝑐 s t 1 2 1 3.5 1.5 ☀ ̂ 𝑐 = 1.5 ☀ ̂ 𝑐 = 1.5 𝑥∗ ( 𝑐 s t 1 2 1 3.5 1.5 ☀ c = 3 ☀ c = 3 𝑥∗(𝑐) = 0 + 2×5 − 5 = 5 (≥ 1)
⽂脈付き予測・ 確率的最適化 ⽂脈から予測し,シナリオ⽣成して確率的最適化 (Estimation-then-Optimize) 様々な確率的最適化の⼿法が使える(CVaR,確率制約,ロバスト) s t 1 2 1
3.5 1.5 ☀ s t 1 2 1 3.5 1.5 ☂