Math.py

Shortest Paths ( DijKstra’s Algorithm )

Scenario

$G=(V,E)\ is\ a\ directed\ graph\ and\ I(e)=lenth\ of\ edge\ e\in E,\ where\ I(e)\geq0\ can\ be\ distance,time\ or\ cost.$
$Find\ the\ shortest\ path\ P(v)\ from\ s\ to\ each\ other\ v\in V-{s},\ where\ I(P)=lenth\ of\ P=\sum_{e\in P} I(e)$
給定一個有向圖以及每個 edge 的 “長度”( 可以是距離、花費時間、花費成本…)，試圖找出從 s 出發距離最短的路徑。

概要 Abstrct

深層殘差網路不管在預測準確度以及收斂速度上都有著非常好的表現。在這篇論文中，作者們從前向及反向的信息傳播分析中，提出了將 shortcut connection 以及相加後的 activation 均使用恆等映射 (identity mapping) ，信息能夠藉由前後向傳播在 block 間進行傳遞。這篇論文中，利用一系列的「消融實驗」( ablation experiments )[^註1]來確定這些恆等映射的重要性。

前面提到了 GAN 利用 JS-Divergence 來進行量測並且逐步改進模型，這樣的闡述看起來似乎很合理，但事實上卻會遇到一些困境。

從上一個部分的推導，我們可以知道如果我們調整 $V(G,D)$，最後的結果可能就會是另外一種計算 Divergence 的方式，而不會是 JS-Divergence。那我們能不能找出一個 divergence 通式，直接藉由調整通式來改變我們想要的 Divergence ?

Interval Partition

Scenario

$Let\ {I(i)=\big[s(i),f(i)\big)\mid i=1,2,3,\cdots,n}\ is\ a\ set\ of\ requests\ interval.$
$Partition\ these\ requests\ into\ a\ minimum\ number\ of\ compatible(no\ overlap)\ subsets.$
給定一個區間，以及 $n$ 個子區間，試圖將這個子區間分成最少的子集合，子集合內的子區間互不重疊。

在正式進入 Generative Adversarial Network ( GAN, 生成對抗網路 )的理論基礎以前，我覺得必須要先簡單定義出一些概念，以利後面的理論探討。

Greedy algorithm

當我們在設計演算法時，往往都是一個一個步驟累積而成，而每一個步驟往往都必須要對某些狀況做決定。Greedy Algorithm 在每一個步驟都選擇「當下」「最好」的決定。也就是說，Greedy Algorithm 在每一步驟下都必須要去試著最優化我們所訂定的規範 (criterion)。而且，這樣的演算法不會回頭、不會反悔、不會猶豫。

Directed Acyclic Graphs (DAGs) 是被廣泛討論的一種有向圖型態。而接下來要講的 Topological Ordering 也主要是針對 DAGs 做討論。

時間 : 2019.10.31
地點 : 台灣大學德田館 103 教室
主講者 : 馬偉雲博士

當我們在使用 GAN 進行生成時，其實有一個很大的問題是，帶有 label 的訓練資料並不容易取得。

舉例來說，如果我們想要讓一張照片利用 Generator 生成梵谷畫風格，訓練資料根本無法取得，因為我們可以有很多的照片，但卻沒有梵谷畫這些風景的資料 ; 又或者，我們想做一個A轉換成B人聲的模型，通常很難讓 B 照著 A 所念的文字照著念一次 ( 可能不同語言、或是收集上有困難…等因素 )，這時候的 GAN 就如同 Unsupervised Learning 任務一般。