Upgrade to Pro — share decks privately, control downloads, hide ads and more …

論文読み会 ICLR2021 | Learning a Latent Search Space...

cocomoff
February 04, 2021

論文読み会 ICLR2021 | Learning a Latent Search Space for Routing Problems using Variational Autoencoders

cocomoff

February 04, 2021
Tweet

More Decks by cocomoff

Other Decks in Research

Transcript

  1. Learning a Latent Search Space for Routing Problems using Variational

    Autoencoders Authors: André Hottung, Bhanu Bhandari, Kevin Tierney, ICLR2021 (Poster) Reader: @cocomoff Feb. 3, 2021
  2. 概要 スコア: 5 7 7 6 ( ギリギリ?) 提案⼿法 CVAE-Opt

    -VAE ( 正則化項の重みが のVAE) を⽤いて学習データから特徴を埋め込む ( 解の対称性のため⼀⼯夫; Symmetry breaking) 解を⽣成するとき,制約なし最適化アルゴリズムを使いながら⽣成する 過去に紹介したECAI2020 論⽂の著者 ( おそらく) 1/13 β β
  3. 経路問題(routing problems) のためのVAE-based approach CVAE を⽤いてLatent space を学習する VAE: AE

    + hidden layer , Conditional VAE: VAE + label (condition) 意義 ( 著者談) 意味的に似ている解が潜在空間の近傍に配置される ( 補完可能) これまでの⼿法 (e.g., GA) と異なり,埋め込み⽅も学習する 解は の空間+ 最適化で探す (blackbox 最適化のイメージ) 課題 routing problem を潜在空間に落とし込む⼿法が確⽴されていない 組合せ構造は対称性を持つので,これを扱うテクニックが必要 解の対称性: 以下の解は同じ意味 TSP の解1 TSP の解2 4/13 z ∼ N(⋅) z 東京 → 神⽥ → 秋葉原 → …→ 有楽町 → 東京 神⽥ → 秋葉原 → …→ 有楽町 → 東京 → 神⽥
  4. 仕組み ( 全体像) 学習 (CVAE) stochastic encoder , decoder 探索

    解きたい問題 と学習した空間の点 からデコーダが経路を⽣成 5/13 q(z∣l, s) p(s∣l, z) l z
  5. 表現とモデル グラフ ,ノード の特徴ベクトル TSP: 2 次元の位置情報 CVRP: はdepot ,

    は顧客 ベクトル (demand など) | 既存研究と同じ 具体的なencoder/decoder は既存研究と似ている ( 次に訪問すべき点を⽰す) 6/13 G = (V , E), V = {v , … , v } 0 n v ∈ i V x i x 0 x i i
  6. Symmetry breaking 組合せ表現には対称性が存在する ( 前述) そのまま学習させると,学習した隠れ解空間 (learned latent search space)

    の 中で近くない場所に同じ解が出現するようになる 学習時に,random なsymmetrical solutions を使って,これを復元できるように学習 することで,学習した隠れ解空間がいい感じになるように祈る このテクニックによりGap が減少する効果がある 8/13
  7. β-VAE β-VAE Higgins et al. 2017: 学習に⽤いるloss function はCVAE に

    -VAE の重み付け を⼊れたもの 実装的にどういうCVAE になっているかはあまり書いていない 今回の例題においてβ がどれぐらい影響があるか 9/13 L(x, z) = E [log p(x∣z)] − βD [q(z∣x)∣∣p(z)] q(z∣x) KL β β
  8. Ablation Study | with handcrafted decoder CVAE-Opt-DE と過去に研究されたdecoder Opt-DE を⽐較する

    Opt-DE J. Bean: Genetic algorithms and random keys for sequencing and optimization ベクトル からpermutation を定義して訪問順を決めるdecoder 著者主張 CVAE-Opt-DE 強い ( あまりよく分からない) 13/13 z ∈ [0 − 1]n