HackMD
  • Beta
    Beta  Get a sneak peek of HackMD’s new design
    Turn on the feature preview and give us feedback.
    Go → Got it
      • Create new note
      • Create a note from template
    • Beta  Get a sneak peek of HackMD’s new design
      Beta  Get a sneak peek of HackMD’s new design
      Turn on the feature preview and give us feedback.
      Go → Got it
      • Sharing Link copied
      • /edit
      • View mode
        • Edit mode
        • View mode
        • Book mode
        • Slide mode
        Edit mode View mode Book mode Slide mode
      • Note Permission
      • Read
        • Only me
        • Signed-in users
        • Everyone
        Only me Signed-in users Everyone
      • Write
        • Only me
        • Signed-in users
        • Everyone
        Only me Signed-in users Everyone
      • More (Comment, Invitee)
      • Publishing
        Please check the box to agree to the Community Guidelines.
        Everyone on the web can find and read all notes of this public team.
        After the note is published, everyone on the web can find and read this note.
        See all published notes on profile page.
      • Commenting Enable
        Disabled Forbidden Owners Signed-in users Everyone
      • Permission
        • Forbidden
        • Owners
        • Signed-in users
        • Everyone
      • Invitee
      • No invitee
      • Options
      • Versions and GitHub Sync
      • Transfer ownership
      • Delete this note
      • Template
      • Save as template
      • Insert from template
      • Export
      • Dropbox
      • Google Drive Export to Google Drive
      • Gist
      • Import
      • Dropbox
      • Google Drive Import from Google Drive
      • Gist
      • Clipboard
      • Download
      • Markdown
      • HTML
      • Raw HTML
    Menu Sharing Create Help
    Create Create new note Create a note from template
    Menu
    Options
    Versions and GitHub Sync Transfer ownership Delete this note
    Export
    Dropbox Google Drive Export to Google Drive Gist
    Import
    Dropbox Google Drive Import from Google Drive Gist Clipboard
    Download
    Markdown HTML Raw HTML
    Back
    Sharing
    Sharing Link copied
    /edit
    View mode
    • Edit mode
    • View mode
    • Book mode
    • Slide mode
    Edit mode View mode Book mode Slide mode
    Note Permission
    Read
    Only me
    • Only me
    • Signed-in users
    • Everyone
    Only me Signed-in users Everyone
    Write
    Only me
    • Only me
    • Signed-in users
    • Everyone
    Only me Signed-in users Everyone
    More (Comment, Invitee)
    Publishing
    Please check the box to agree to the Community Guidelines.
    Everyone on the web can find and read all notes of this public team.
    After the note is published, everyone on the web can find and read this note.
    See all published notes on profile page.
    More (Comment, Invitee)
    Commenting Enable
    Disabled Forbidden Owners Signed-in users Everyone
    Permission
    Owners
    • Forbidden
    • Owners
    • Signed-in users
    • Everyone
    Invitee
    No invitee
       owned this note    owned this note      
    Published Linked with GitHub
    Like BookmarkBookmarked
    Subscribed
    • Any changes
      Be notified of any changes
    • Mention me
      Be notified of mention me
    • Unsubscribe
    Subscribe
    --- 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最大 公式: ![](https://i.imgur.com/G5UATT6.jpg) - 訊息量就是"bit" - 例如傳送一串字元好了,這整個字元集為 X ,而裡面每個字元 $x\in X$ 出現的機率為 P(x)。 - Shannon entropy 表示的便是:用最好的『語言』傳送這串字元**平均需要**的『位元』數。像是如果要傳送『ABC』最好的語言可能就是直接用英文吧。 ### KL divergence (KL 散度) - 又稱relative entropy(相對熵) - 是用來衡量兩種機率分布之間距離的方法之一 - 定義:用來度量使用基於 Q 的分布來編碼服從 P 的分布的樣本所需的額外的平均 bit(位元數) - 通常P 表示資料的真實分布,Q 表示資料的理論分布、估計的模型分布、或P的近似分布。 公式: ![](https://i.imgur.com/8skAplb.jpg) - $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越接近 公式: ![](https://i.imgur.com/JkFzTnj.jpg) ### Wasserstein distance ( Wasserstein 距離) - 又稱動土距離,Earth-Mover distance ( EM distance ) - 因為整個過程就像將一堆小石子透過最小的累積移動距離堆成另一個形狀 - 定義:P 跟 Q 的分布如果越接近,則對某條『路徑』$\gamma$ 來說,從真實樣本 x 走到生成樣本 y 的距離就越短 - 通常用來衡量兩個圖片的距離 公式: ![](https://i.imgur.com/qmwfX79.jpg) - $\Pi(P,Q)$ 是 P 和 Q 所有可能的聯合分佈 ( joint distribution ) 的情況 - 對於每一種可能的聯合分佈 $\gamma$ ,可以從裡面取一對x, y(真實樣本,生成樣本),並算出它們的距離 - 特性 - Wasserstein Distance不僅可算出兩個機率分布的距離,也可以算出"如何"從其中一個分布變換到另一個分布 - 可以計算離散分布和連續分布之間的距離 - 在變換連續型分布的時候可以保持它的幾何特性 ### Dynamic Time Warping (DTW) - 用來衡量兩個不同長度的 array 之間的相似度(距離) - 是 Dynamic Programming 的應用 - 主要用來分析序列型資料 ![](https://i.imgur.com/T3F7Ewd.jpg =600x800) 流程 : 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. 直到找出兩個序列的最小距離,這就是他們的相似度 ![](https://i.imgur.com/aeptDSc.png) 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 ```python= 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 ![](https://i.imgur.com/GUzU4Sc.jpg) ```python= 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 ```python= 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 ![](https://i.imgur.com/lzOfYkW.png) - 另外也會計算出 marginal probability 用來評估圖片的多樣性 - 假如這群生成的圖片的 integral of the marginal probability distribution 算出來的結果 entropy 很高的話就代表這群圖片的多樣性夠高 ![](https://i.imgur.com/eVz2Wt7.png) - 最後 Inception Score 會利用 KL-divergence 來結合條件機率和邊緣機率分布 ![](https://i.imgur.com/kPnM5bU.png) - $p(y)$: 對 N 個生成的圖片輸入到 Inception V3 中各自得到一個機率分布,然後將這些向量平均起來得到所有生成圖片在所有類別上的 marginal distribution ![](https://i.imgur.com/PPGR960.png) - $P(y|x)$: 把生成的圖片 x 輸入到 Inception V3 中得到 1000維的向量 y,也就是這個生成圖片屬於各個類別的機率分布 - IS 在這裡提出的假設是如果這個向量 y 的某個維度其值特別大就代表圖片是清晰的 (這代表某一個 class 的機率特別大) - $D_{KL}$: KL-Divergence of p(x|y) 和 p(y) ![](https://i.imgur.com/lrxmT4S.png) - 若 label distribution $p(x|y)$ 和 marginal distribution $p(y)$ 之間的距離夠大就代表生成模型夠好,因為前者是尖銳的分布,後者是均勻分布,理論上本來就要差很多 ![](https://i.imgur.com/bTax7aW.png) - 但是 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 ![](https://i.imgur.com/Kszm22D.png) - $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)

    Import from clipboard

    Advanced permission required

    Your current role can only read. Ask the system administrator to acquire write and comment permission.

    This team is disabled

    Sorry, this team is disabled. You can't edit this note.

    This note is locked

    Sorry, only owner can edit this note.

    Reach the limit

    Sorry, you've reached the max length this note can be.
    Please reduce the content or divide it to more notes, thank you!

    Import from Gist

    Import from Snippet

    or

    Export to Snippet

    Are you sure?

    Do you really want to delete this note?
    All users will lost their connection.

    Create a note from template

    Create a note from template

    Oops...
    This template is not available.


    Upgrade

    All
    • All
    • Team
    No template found.

    Create custom template


    Upgrade

    Delete template

    Do you really want to delete this template?

    This page need refresh

    You have an incompatible client version.
    Refresh to update.
    New version available!
    See releases notes here
    Refresh to enjoy new features.
    Your user state has changed.
    Refresh to load new user state.

    Sign in

    Forgot password

    or

    By clicking below, you agree to our terms of service.

    Sign in via Facebook Sign in via Twitter Sign in via GitHub Sign in via Dropbox

    New to HackMD? Sign up

    Help

    • English
    • 中文
    • Français
    • Deutsch
    • 日本語
    • Español
    • Català
    • Ελληνικά
    • Português
    • italiano
    • Türkçe
    • Русский
    • Nederlands
    • hrvatski jezik
    • język polski
    • Українська
    • हिन्दी
    • svenska
    • Esperanto
    • dansk

    Documents

    Tutorials

    Book Mode Tutorial

    Slide Mode Tutorial

    YAML Metadata

    Contacts

    Facebook

    Twitter

    Feedback

    Send us email

    Resources

    Releases

    Pricing

    Blog

    Policy

    Terms

    Privacy

    Cheatsheet

    Syntax Example Reference
    # Header Header 基本排版
    - Unordered List
    • Unordered List
    1. Ordered List
    1. Ordered List
    - [ ] Todo List
    • Todo List
    > Blockquote
    Blockquote
    **Bold font** Bold font
    *Italics font* Italics font
    ~~Strikethrough~~ Strikethrough
    19^th^ 19th
    H~2~O H2O
    ++Inserted text++ Inserted text
    ==Marked text== Marked text
    [link text](https:// "title") Link
    ![image alt](https:// "title") Image
    `Code` Code 在筆記中貼入程式碼
    ```javascript
    var i = 0;
    ```
    var i = 0;
    :smile: :smile: Emoji list
    {%youtube youtube_id %} Externals
    $L^aT_eX$ LaTeX
    :::info
    This is a alert area.
    :::

    This is a alert area.

    Versions

    Versions and GitHub Sync

    Sign in to link this note to GitHub Learn more
    This note is not linked with GitHub Learn more
     
    Add badge Pull Push GitHub Link Settings
    Upgrade now

    Version named by    

    More Less
    • Edit
    • Delete

    Note content is identical to the latest version.
    Compare with
      Choose a version
      No search result
      Version not found

    Feedback

    Submission failed, please try again

    Thanks for your support.

    On a scale of 0-10, how likely is it that you would recommend HackMD to your friends, family or business associates?

    Please give us some advice and help us improve HackMD.

     

    Thanks for your feedback

    Remove version name

    Do you want to remove this version name and description?

    Transfer ownership

    Transfer to
      Warning: is a public team. If you transfer note to this team, everyone on the web can find and read this note.

        Link with GitHub

        Please authorize HackMD on GitHub

        Please sign in to GitHub and install the HackMD app on your GitHub repo. Learn more

         Sign in to GitHub

        HackMD links with GitHub through a GitHub App. You can choose which repo to install our App.

        Push the note to GitHub Push to GitHub Pull a file from GitHub

          Authorize again
         

        Choose which file to push to

        Select repo
        Refresh Authorize more repos
        Select branch
        Select file
        Select branch
        Choose version(s) to push
        • Save a new version and push
        • Choose from existing versions
        Available push count

        Upgrade

        Pull from GitHub

         
        File from GitHub
        File from HackMD

        GitHub Link Settings

        File linked

        Linked by
        File path
        Last synced branch
        Available push count

        Upgrade

        Danger Zone

        Unlink
        You will no longer receive notification when GitHub file changes after unlink.

        Syncing

        Push failed

        Push successfully