---
tags: ML notes
---

# 機器學習中的距離

ML 需要許多算距離的方法來計算不同資料之間的關係，例如計算兩個機率分布之間的"距離"，此篇整理了我所知的所有與機器學習相關的距離算法

[toc]

## 衡量兩點距離

### Euclidean Distance

定義：兩個點在歐式空間的距離

一維：
${d(p,q)={\sqrt {(p-q)^{2}}}}$

二維：
${d(p,q)={\sqrt {(q_{1}-p_{1})^{2}+(q_{2}-p_{2})^{2}}}}$

### Manhattan Distance

- 又稱 L1-distance
- 定義：在歐式空間的固定直角坐標系上兩點所形成的線段對軸產生的投影的距離總和。也就是一個點在方格上要走幾格才能到另一個點。

公式：${ d(x,y)=\left|x_{1}-x_{2}\right|+\left|y_{1}-y_{2}\right|}$

### Chebyshev distance

- 又稱 L∞度量、棋盤距離
- 定義：在向量空間中二個點之間其各座標數值差的最大值，在棋盤上是從一個位置移動到另一個位置所需的部步數
- 公式：${D_{\rm {Chebyshev}}(p,q):=\max _{i}(|p_{i}-q_{i}|)\ }$

### Minkowski Distance ( 明氏距離 )

- 可用來同時代表Euclidean Distance、 Manhattan Distance、Chebyshev distance

公式：${\displaystyle \left(\sum _{i=1}^{n}|x_{i}-y_{i}|^{p}\right)^{1/p}}$

- 當 p=0，為明氏距離
- 當 p=1，為曼哈頓距離
- 當 p=2，為歐式距離

---
**以上所有距離的共同缺點是**
1. 沒有考慮到單位
2. 沒有考慮到各分量的分布可能不同

### Standardized Euclidean Distance

- 利用z-score標準化將所有資料的分布都標準化到mean和std一樣
- standardized value = (original value – mean) / standard deviation
- 也可以把Std的倒數看成是一種權重，變成Weighted Euclidean Distance

## 衡量兩個向量的距離

### Consine Distance

定義：通過測量兩個向量的夾角的餘弦值來度量它們之間的相似性。0度角的餘弦值是1，而其他任何角度的餘弦值都不大於1；並且其最小值是-1。

Cosine Similarity公式：${\text{similarity}}=\cos(\theta )={A\cdot B \over \|A\|\|B\|}={\frac {\sum \limits _{{i=1}}^{{n}}{A_{i}\times B_{i}}}{{\sqrt {\sum \limits _{{i=1}}^{{n}}{(A_{i})^{2}}}}\times {\sqrt {\sum \limits _{{i=1}}^{{n}}{(B_{i})^{2}}}}}}$

- 可看成 **A和B共同有的東西 / A擁有的東西開根號 * B擁有的東西開根號**
- 1 - Cosine Similarity 就是 Cosine Distance
- 在 Document match 中，A 和 B 是詞頻向量，這時候餘弦相似性可以被看作是在比較過程中把文件長度正規化的方法

### Jaccard Distance

- 就是 1 - 交集/聯集

Jaccrad Index公式：$J(A,B)={{|A\cap B|} \over {|A\cup B|}}={{|A\cap B|} \over {|A|+|B|-|A\cap B|}}$

距離公式就是1-Jaccrd Index：$d_{J}(A,B)=1-J(A,B)={{|A\cup B|-|A\cap B|} \over |A\cup B|}$

### Shannon Entropy 算兩個分布的差異

- Informative : 已經有很多確定的事情，不確定性少，Entropy小
- Noinformative : 沒有任何資訊，所有事情發生的可能性都一樣，Entropy最大

公式:

- 訊息量就是"bit"
- 例如傳送一串字元好了，這整個字元集為 X ，而裡面每個字元 $x\in X$ 出現的機率為 P(x)。
- Shannon entropy 表示的便是：用最好的『語言』傳送這串字元**平均需要**的『位元』數。像是如果要傳送『ABC』最好的語言可能就是直接用英文吧。

### KL divergence (KL 散度)

- 又稱relative entropy(相對熵)
- 是用來衡量兩種機率分布之間距離的方法之一
- 定義：用來度量使用基於 Q 的分布來編碼服從 P 的分布的樣本所需的額外的平均 bit(位元數)
- 通常P 表示資料的真實分布，Q 表示資料的理論分布、估計的模型分布、或P的近似分布。

公式:

- $D_{KL}(P||Q)$ 是從分布 Q 到 P 的 KL 散度
- 三個特性：
- 非負
- 若等於零則代表P和Q幾乎一樣
- 不對稱 $D_{KL}(P||Q) \neq D_{KL}(Q||P)$

- 舉例：假設今天要傳送一份中文資料，若以中文編碼其詞所需bit為30，而利用英文去編碼所需bit為55，那麼此時中文就是 P ，英文就是 Q，而其$D_{KL}(P||Q)$ = 55 - 30 = 25

### Jensen-Shannon divergence ( JS 散度)

- KL-Divergence 的變形，但解決了不對稱性的問題
- 定義：從分佈 Q 到 M 的 KL 散度 加上從分佈 P 到 M 的 KL 散度，且 M 是 PQ 的平均
- JSD越小則P跟Q越接近
公式:

### Wasserstein distance ( Wasserstein 距離)
- 又稱動土距離，Earth-Mover distance ( EM distance )
- 因為整個過程就像將一堆小石子透過最小的累積移動距離堆成另一個形狀
- 定義：P 跟 Q 的分布如果越接近，則對某條『路徑』$\gamma$ 來說，從真實樣本 x 走到生成樣本 y 的距離就越短
- 通常用來衡量兩個圖片的距離

公式: 

- $\Pi(P,Q)$ 是 P 和 Q 所有可能的聯合分佈 ( joint distribution ) 的情況
- 對於每一種可能的聯合分佈 $\gamma$ ，可以從裡面取一對x, y(真實樣本，生成樣本)，並算出它們的距離
- 特性
- Wasserstein Distance不僅可算出兩個機率分布的距離，也可以算出"如何"從其中一個分布變換到另一個分布
- 可以計算離散分布和連續分布之間的距離
- 在變換連續型分布的時候可以保持它的幾何特性

### Dynamic Time Warping (DTW)
- 用來衡量兩個不同長度的 array 之間的相似度(距離)
- 是 Dynamic Programming 的應用
- 主要用來分析序列型資料


流程 :
1. 找出要分析的兩個 array 的 head 跟 tail，head 和 head 對齊，tail 和 tail 對齊
2. 把 head_1 ~ tail_1 以及 head_2 ~ tail_2 之間的序列分割成一樣的點個數
3. 計算 DTW[i, j] = cost + min(DTW[i-1, j ],
DTW[i , j-1],
DTW[i-1, j-1])
4. 直到找出兩個序列的最小距離，這就是他們的相似度

Warping function 的限制 [cs730_slides13](http://www.mathcs.emory.edu/~lxiong/cs730_s13/share/slides/searching_sigkdd2012_DTW.pdf)
1. 序列資料需要是單調性的
- 也就是時間不會往回走，避免有相同的特徵與時間相交
2. 連續性
- 確保一一對應，不會有忽略掉的重要特徵
3. 邊界條件 (Boundary case)
- 假如他們之間共有 k 個點，則 $i_1 = 1, i_k = n$，而 $j_1 = 1, j_k = m$
- 確保先後順序不會改變，不會集中考慮其中一個序列

Implementation
- Pure DTW

def dtw(s, t):
    n, m = len(s), len(t)
    dtw_matrix = np.zeros((n+1, m+1))
    for i in range(n+1):
        for j in range(m+1):
            dtw_matrix[i, j] = np.inf
    dtw_matrix[0, 0] = 0
    
    for i in range(1, n+1):
        for j in range(1, m+1):
            cost = abs(s[i-1] - t[j-1])
            # take last min from a square box
            last_min = np.min([dtw_matrix[i-1, j], dtw_matrix[i, j-1], dtw_matrix[i-1, j-1]])
            dtw_matrix[i, j] = cost + last_min
    return dtw_matrix

- DTW with windows
- 避免一個有限 element 的 array 匹配到有無限 element 的 array

def dtw(s, t, window):
    n, m = len(s), len(t)
    w = np.max([window, abs(n-m)])
    dtw_matrix = np.zeros((n+1, m+1))
    
    for i in range(n+1):
        for j in range(m+1):
            dtw_matrix[i, j] = np.inf
    dtw_matrix[0, 0] = 0
    
    for i in range(1, n+1):
        for j in range(np.max([1, i-w]), np.min([m, i+w])+1):
            dtw_matrix[i, j] = 0
    
    for i in range(1, n+1):
        for j in range(np.max([1, i-w]), np.min([m, i+w])+1):
            cost = abs(s[i-1] - t[j-1])
            # take last min from a square box
            last_min = np.min([dtw_matrix[i-1, j], dtw_matrix[i, j-1], dtw_matrix[i-1, j-1]])
            dtw_matrix[i, j] = cost + last_min
    return dtw_matrix

- 用 Package
- fastdtw, SparseDTW, PrunedDTW

from fastdtw import fastdtw
from scipy.spatial.distance import euclidean

x = np.array([1, 2, 3, 3, 7])
y = np.array([1, 2, 2, 2, 2, 2, 2, 4])

distance, path = fastdtw(x, y, dist=euclidean)

print(distance)
print(path)
# 5.0
# [(0, 0), (1, 1), (1, 2), (1, 3), (1, 4), (2, 5), (3, 6), (4, 7)]

https://blog.csdn.net/zouxy09/article/details/9140207?spm=1001.2014.3001.5501

### Inception Score (IS)
基於當時性能最好的圖片分類模型 Inception V3 對一組生成的圖片(synthetic images) 的分類情況來評估產生出來的圖片品質，類別共有1000類 (ImageNet)
- 利用計算出每一個生成的圖片的 class probabilities 來評估圖片的品質
- 假如這群生成的圖片被分類成某一個 class 的機率相對於其他 class 特別高 (分類為某類的信心很高)，代表這群生成的圖片的品質好
- 也可以想成是生成的圖片的條件機率有較低的 entropy

- 另外也會計算出 marginal probability 用來評估圖片的多樣性
- 假如這群生成的圖片的 integral of the marginal probability distribution 算出來的結果 entropy 很高的話就代表這群圖片的多樣性夠高

- 最後 Inception Score 會利用 KL-divergence 來結合條件機率和邊緣機率分布
- $p(y)$: 對 N 個生成的圖片輸入到 Inception V3 中各自得到一個機率分布，然後將這些向量平均起來得到所有生成圖片在所有類別上的 marginal distribution 
- $P(y|x)$: 把生成的圖片 x 輸入到 Inception V3 中得到 1000維的向量 y，也就是這個生成圖片屬於各個類別的機率分布
- IS 在這裡提出的假設是如果這個向量 y 的某個維度其值特別大就代表圖片是清晰的 (這代表某一個 class 的機率特別大)
- $D_{KL}$: KL-Divergence of p(x|y) 和 p(y)
- 若 label distribution $p(x|y)$ 和 marginal distribution $p(y)$ 之間的距離夠大就代表生成模型夠好，因為前者是尖銳的分布，後者是均勻分布，理論上本來就要差很多

- 但是 IS 只是將生成圖片和 ImageNet 的圖片做比較，並沒有將生成出來的圖片與真實圖片做比較，實際上並無法真正反映出生成模型的好壞，因此後來才會有 FID

### Fréchet Inception Distance (FID)
是一種計算兩群圖片(生成出來的圖片與真實圖片)特徵向量之間距離的 metrics
- The FID metric is the squared Wasserstein metric between two multidimensional Gaussian distributions

計算流程
- FID 將 Inception V3 的最後一層輸出層換成一個 2048 維的 pooling layer，其輸出就會被當成圖片的特徵向量
- 因為被換掉的 Inception V3 輸出層本來就是 2048 維
- 將真實圖片與生成的圖片丟入這個修改過的網路，得到真實圖片的特徵向量與生成圖片的特徵向量
- 利用以下公式計算出 FID
- $r$ 為真實圖片，$g$ 為生成圖片
- $Tr$ 為矩陣上對角線的總和 (trace)，也就是 eigenvalue 的總和
- If a non-zero vector v let $Av = \lambda v$，then $\lambda$ is eigenvalue of matrix $A$
- $\sum{_r}$ 為真實圖片的 covariance martix
- $\sum{_g}$ 為生成圖片的 covariance martix

特性
- FID 越低代表兩組圖片越相似，而這在 GAN 就代表模型表現越好，若 FID=0，代表兩組圖片一樣
- Inception V3 所提取出來的特徵未必符合多元常態分布，可能因此失真　
- IS 和 FID 都無法避免 overfitting，假如模型直接複製訓練資料來產生的話兩個 metrics 都會表現得很好
- 不論是 IS 還是 FID 都是根據特徵是否出現來評估，並不會看圖片特徵的位置 (有可能會出現嘴上眼下的圖片)

# Reference
- [GAN系列文(1)–distance of distribution](https://angnotes.wordpress.com/2017/12/04/gan%E7%B3%BB%E5%88%97%E6%96%871-distance-of-distribution/)
- [Drift Metrics: How to Select the Right Metric to Analyze Drift](https://towardsdatascience.com/drift-metrics-how-to-select-the-right-metric-to-analyze-drift-24da63e497e)
- [如何评价GAN网络的好坏？IS（inception score）和FID（Fréchet Inception Distance）](https://blog.csdn.net/qq_27261889/article/details/86483505)
- [全面解析Inception Score原理及其局限性](https://www.jiqizhixin.com/articles/2019-01-10-18)
- [A simple explanation of the Inception Score
](https://medium.com/octavian-ai/a-simple-explanation-of-the-inception-score-372dff6a8c7a)