Math.py

在 GAN 中，我們會隨機 input 一組向量，然後生成一個我們要的物件 ( 可能是圖片、文字、語句… )。直覺的，我們總會希望這一組向量的每一個維度都代表某一個特性、性質。

但是現實總是沒有想像中美好。

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 教室
主講者 : 馬偉雲博士