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
Gemini CLI ハンズアウト
mickey_kubo
2
180
最適化ソリューションにおける モデリングツールAMPLの活用
mickey_kubo
0
30
YAML入門 - 歴史と基本的な使い方を学ぼう
mickey_kubo
0
53
Google Agent Development Kit (ADK) 入門 🚀
mickey_kubo
2
1k
Google ADK実用例:Travel Concierge徹底解説
mickey_kubo
0
400
最適化と機械学習による問題解決
mickey_kubo
0
140
Agentic AIとMCPを利用したサービス作成入門
mickey_kubo
0
240
最適決定木を用いた処方的価格最適化
mickey_kubo
4
1.7k
大規模な2値整数計画問題に対する 効率的な重み付き局所探索法
mickey_kubo
1
250
Other Decks in Research
See All in Research
NLP2025SharedTask翻訳部門
moriokataku
0
300
LLM-as-a-Judge: 文章をLLMで評価する@教育機関DXシンポ
k141303
3
810
MGDSS:慣性式モーションキャプチャを用いたジェスチャによるドローンの操作 / ec75-yamauchi
yumulab
0
230
(NULLCON Goa 2025)Windows Keylogger Detection: Targeting Past and Present Keylogging Techniques
asuna_jp
1
520
ノンパラメトリック分布表現を用いた位置尤度場周辺化によるRTK-GNSSの整数アンビギュイティ推定
aoki_nosse
0
320
SkySense : A Multi-Modal Remote Sensing Foundation Model Towards Universal Interpretation for Earth Observation Imagery
satai
3
240
チャッドローン:LLMによる画像認識を用いた自律型ドローンシステムの開発と実験 / ec75-morisaki
yumulab
1
440
【緊急警告】日本の未来設計図 ~沈没か、再生か。国民と断行するラストチャンス~
yuutakasan
0
130
20250502_ABEJA_論文読み会_スライド
flatton
0
170
Sosiaalisen median katsaus 03/2025 + tekoäly
hponka
0
1.3k
CSP: Self-Supervised Contrastive Spatial Pre-Training for Geospatial-Visual Representations
satai
3
210
ASSADS:ASMR動画に合わせて撫でられる感覚を提示するシステムの開発と評価 / ec75-shimizu
yumulab
1
380
Featured
See All Featured
Build The Right Thing And Hit Your Dates
maggiecrowley
36
2.8k
Large-scale JavaScript Application Architecture
addyosmani
512
110k
How to Ace a Technical Interview
jacobian
277
23k
Art, The Web, and Tiny UX
lynnandtonic
299
21k
Producing Creativity
orderedlist
PRO
346
40k
Easily Structure & Communicate Ideas using Wireframe
afnizarnur
194
16k
No one is an island. Learnings from fostering a developers community.
thoeni
21
3.3k
The World Runs on Bad Software
bkeepers
PRO
69
11k
Visualization
eitanlees
146
16k
Building Applications with DynamoDB
mza
95
6.5k
Dealing with People You Can't Stand - Big Design 2015
cassininazir
367
26k
I Don’t Have Time: Getting Over the Fear to Launch Your Podcast
jcasabona
32
2.3k
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 ☂