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
880
機械学習と数理最適化の融合-文脈付き確率的最短路を例として-
機械学習と数理最適化の融合-文脈付き確率的最短路を例として-
MIKIO KUBO
April 30, 2024
Tweet
Share
More Decks by MIKIO KUBO
See All by MIKIO KUBO
Python型ヒント完全ガイド 初心者でも分かる、現代的で実践的な使い方
mickey_kubo
1
86
SQLModel 入門
mickey_kubo
0
24
Gemini CLI ハンズアウト
mickey_kubo
2
260
最適化ソリューションにおける モデリングツールAMPLの活用
mickey_kubo
0
31
YAML入門 - 歴史と基本的な使い方を学ぼう
mickey_kubo
0
61
Google Agent Development Kit (ADK) 入門 🚀
mickey_kubo
2
1.1k
Google ADK実用例:Travel Concierge徹底解説
mickey_kubo
0
420
最適化と機械学習による問題解決
mickey_kubo
0
140
Agentic AIとMCPを利用したサービス作成入門
mickey_kubo
0
270
Other Decks in Research
See All in Research
Looking for Escorts in Sydney?
lunsophia
1
120
Computational OT #1 - Monge and Kantorovitch
gpeyre
0
180
A multimodal data fusion model for accurate and interpretable urban land use mapping with uncertainty analysis
satai
3
220
EarthSynth: Generating Informative Earth Observation with Diffusion Models
satai
3
100
RHO-1: Not All Tokens Are What You Need
sansan_randd
1
120
Self-supervised audiovisual representation learning for remote sensing data
satai
3
220
SSII2025 [TS1] 光学・物理原理に基づく深層画像生成
ssii
PRO
4
3.7k
Mathematics in the Age of AI and the 4 Generation University
hachama
0
160
90 分で学ぶ P 対 NP 問題
e869120
17
7.5k
SatCLIP: Global, General-Purpose Location Embeddings with Satellite Imagery
satai
3
220
Pix2Poly: A Sequence Prediction Method for End-to-end Polygonal Building Footprint Extraction from Remote Sensing Imagery
satai
3
480
クラウドのテレメトリーシステム研究動向2025年
yuukit
3
960
Featured
See All Featured
GraphQLの誤解/rethinking-graphql
sonatard
71
11k
The Power of CSS Pseudo Elements
geoffreycrofte
77
5.8k
Become a Pro
speakerdeck
PRO
28
5.4k
The Success of Rails: Ensuring Growth for the Next 100 Years
eileencodes
45
7.5k
Fashionably flexible responsive web design (full day workshop)
malarkey
407
66k
Balancing Empowerment & Direction
lara
1
400
Creating an realtime collaboration tool: Agile Flush - .NET Oxford
marcduiker
30
2.1k
Exploring the Power of Turbo Streams & Action Cable | RailsConf2023
kevinliebholz
34
5.9k
Save Time (by Creating Custom Rails Generators)
garrettdimon
PRO
31
1.3k
A Tale of Four Properties
chriscoyier
160
23k
A Modern Web Designer's Workflow
chriscoyier
694
190k
[RailsConf 2023 Opening Keynote] The Magic of Rails
eileencodes
29
9.5k
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 ☂