計量語言學 (持續更新中)
===

- since 2024.02 - 持續更新中
- 以下為修習 112-2 學期 NCCU計量語言學的學習筆記。為上課資料裡有興趣因此自行查找網路資源，理解整理下的筆記。
- 資料來源皆附於下方。
- 歡迎留言討論 ～

---

## Zip's Law and Keyness
### **Zipf's law (齊夫定律)**

* **意思：** 由語言學家 George Kingsley Zipf 提出的詞彙分佈規律。「在語言中，僅有幾個字使用頻率會非常高，其他大多數的字其實都很少被使用。」每個字使用的頻率和排名會呈現 **冪律(Power law)**。

* **舉例（如下圖）：** 在一英文文本中使用頻率排名第一的字是 'the'、第三是 'and'，即 'and' 的使用頻率為 'the' 的三分之一。另外，使用排序較高的單詞常為功能詞(function word)。


* **應用：** Zipf's law 該「普遍不均等規律」不只單出現在英文中，也出現在其他的自然語言。甚至也可以適用於社會其他現象，例如：收入排名、公司規模分佈等。

* **公式：** 
* n 為一單詞的排名，$P_n$ 為其概率。即 $P_n$ 隨著 $1/n^{a}$ 變化，當n越大，$Pn$則會隨之冪次下降。a 則為冪律指數，會影響冪律分佈的形狀。

* **log-log graph：** 若要觀察一文本中單詞是否有符合Zipf' law，可以對其頻率和排名取log，視其點狀分佈是否可為一直線。若可成一直線，則可視該文本有符合 Zipf' law（如下圖）。


[pic_reference](https://www.intmath.com/blog/mathematics/zipf-distributions-log-log-graphs-and-site-statistics-702)
[Reference_1](https://phys.org/news/2017-08-unzipping-zipf-law-solution-century-old.html)
[Reference_2](https://www.youtube.com/watch?v=4dofBw9r0P4)
[Reference_3](https://en.wikipedia.org/wiki/George_Kingsley_Zipf)
[Reference_4](https://en.wikipedia.org/wiki/Zipf%27s_law)

### **Keyness**

* 藉由比較單詞在 target corpus 和 reference corpus 中的頻率（兩者為獨立的corpus），以計算keywords。 如果一詞比起在 reference corpus 更常在 target corpus中出現，即有可能為 target corpus 的 keyword。

統計上計算 keyness的方法有許多種，例如：Log-likelihood Ratio ($G^2$) 或 Chi-square。

[Reference_1](https://alvinntnu.github.io/NTNU_ENC2036_LECTURES/keyword-analysis.html)
[Reference_2](https://lexically.net/downloads/version7/HTML/keyness_definition.html)

* **Log-Likelihood (LL)**

**likelihood vs. probability:**
likelihood (概似性)：在已知所得的觀測結果上，推估其相關母數。
probability (機率)：在已知母數情況下，預測接下來觀測上的結果。

log-likelihood 即對 likelihood 取log，可讓計算更為簡單，也避免小數不斷相乘後下溢 (underflow)。
[Reference_1](https://www.simplilearn.com/tutorials/statistics-tutorial/difference-between-probability-and-likelihood)

* **Odd Ratio (OR) 勝算比**
兩互斥事件的概率比值。
常用於logistic 二元分類的回歸模型中。

* 舉例：以下圖實驗組 vs. 對照組為例
實驗組中發生結果的勝算= A/B
對照組中發生結果的勝算= C/D
勝算比= (A/B) / (C/D) = AD/BC

即如果勝算比 AD/BC >1：這表示實驗組中發生該事件的勝算較對照組更大，即實驗組相對於對照組更有可能發生。


[Reference_1](https://www.yongxi-stat.com/odds-ratio-or-r/)

---

## Hierarchical Cluster Analysis
### **Hierarchical Clustering Analysis (HCA)**

- **層次聚類 (Hierarchical clustering)**
以樹狀結構有層次地呈現分群(clustering)結果，適合階層式的數據(hierarchical data)，例如：生物學領域，以觀察資料的分群結構以便後續的相似度計算。

- **clustering (分群)**：不像分類 (classification) 任務的資料有明確的類別 (label)。原始資料沒有明確的類別，依照資料的相似性去分群（越近越容易分在同一群），再從分群結果中發現不同群之間的親疏遠近之別。例如常見的分群法：k-means。
- **Dendrogram:** 古希臘文 déndron（樹） 和 grámma（圖畫）組成，意旨「樹狀圖」。Hierarchical clustering 即以階層性為特色，因此很適合以樹狀圖的方式來圖像化。以便直觀了解每一簇之間的遠近關係。以下圖為例，在同一分支群(clade) 中的資料(leaf)就比起與另一分支群中的資料點相近。

* Hierarchical clustering 又可以依照資料是以 1.「聚合」方式合併還是以 2.「分裂」方式展開而分為以下兩者

**1. Agglomerative Hierarchical Clustering (AHC) 聚合式階層分群法:**

即每一個資料慢慢向上(bottom-up)一層一層合併，最後成為一簇 (cluster)。
AHC為一種概念，如何計算決定哪兩個資料點/群類要合併有許多不同的演算法。
以下為常見的 AHC 演算法：
- **single-linkage agglomerative algorithm 單一連結聚合演算法**
又稱「最近法」，即計算不同群聚中最接近兩點間的距離。
$C_i$ 、$C_j$ 代表 clustering i 和 clustering j，而 a 為 $C_i$ 中的一個點、b 為 $C_j$ 中的一個點。
$$d(C_i, C_j) = \min_{a \in C_i, b \in C_j} \text{d}(a, b)$$

- **complete-linkage agglomerative algorithm 完全連結聚合演算法**
又稱「最遠法」，計算不同群聚中最遠兩點間的距離。
$$d(C_i, C_j) = \max_{a \in C_i, b \in C_j} \text{d}(a, b)$$
- **average-linkage agglomerative algorithm 平均連結聚合演算法**
計算不同群聚間各點與各點間距離總和的平均。
$$d(C_i, C_j) = \sum_{a \in C_i,b \in C_j}\frac{\text{d}(a, b)}{|C_i||C_j|} $$
- **Ward's method 華德法**
將兩群合併後，各點到合併後的群中心的距離平方和。
μ 為 $C_i$ ∪$C_j$  的平均值；這裡 a 指兩群合併後 ($C_i$ ∪$C_j$) 群中的一個點。
$$ d(C_i,C_j) = \sum_{a \in C_i\cup C_j} ||a-μ||$$

**2. Divisive Hierarchical Clustering 分裂式階層分群法 :**

即AHC的相反，以一群資料出發，向下(top-down) 的方式慢慢分裂成為一個一個資料點。

* 如何**計算點和點之間的距離**也有很多方式，以下為常見的幾種方式：

- **Euclidean distance 歐幾里得距離：**
可用來計算空間中 點p 和 點q 之間的距離，公式中 n 為維度。

$$d(p, q) = \sqrt{\sum_{i=1}^{n} (p_i - q_i)^2}$$

- **Manhattan distance 曼哈頓距離：**
表明兩個點 (p,q) 在標準座標系統上的絕對值總和。原本是在計算像曼哈頓一班的方形建築區塊城市中最短的行車距離。n為維度。
$$ d(p, q) = \sum_{i=1}^{n} |p_i - q_i|$$
- **Canberra Distance 坎培拉距離：**
計算向量空間中 點p 和 點q 之間的距離，是 Manhattan distance 的加權版本。
p 和 q 皆為向量，n為維度。
$$d(p, q) = \sum_{i=1}^{n} \frac{|p_i - q_i|}{|p_i| + |q_i|}$$

[Reference_Clustering](https://web.ntnu.edu.tw/~algo/Fitting.html)
[Reference_HCA_1](http://mirlab.org/jang/books/dcpr/dcHierClustering.asp?title=3-2%20Hierarchical%20Clustering%20(%B6%A5%BCh%A6%A1%A4%C0%B8s%AAk)&language=chinese)
[Reference_HCA_2](https://tomohiroliu22.medium.com/%E6%A9%9F%E5%99%A8%E5%AD%B8%E7%BF%92-%E5%AD%B8%E7%BF%92%E7%AD%86%E8%A8%98%E7%B3%BB%E5%88%97-82-%E8%81%9A%E5%90%88%E5%BC%8F%E9%9A%8E%E5%B1%A4%E5%88%86%E7%BE%A4%E6%B3%95-agglomerative-hierarchical-clustering-5f064b996d20)
[Reference_AHC_1](https://r.qcbs.ca/workshop09/book-en/clustering.html)
[Reference_Euclidean distance](https://en.wikipedia.org/wiki/Euclidean_distance)
[Reference_Manhattan_distance](https://zhuanlan.zhihu.com/p/101277851)
[Reference_Dendrogram](https://online.visual-paradigm.com/tw/knowledge/business-design/what-is-dendrogram/)

### **Multidimensional Scaling (MDS)** 多維/元尺度分析

- MDS為一種多變量分析，主要是把高維空間的資料映射到低維空間以減少計算上的複雜，以讓其可視化（人類只能看到三維空間的東西）、更好地進行分析。
可以分為：1. 數值(metric) 2. 非數值(Non-metric)。

**1. metric Multidimensional Scaling (MDS) 數值多元尺度分析**
MDS 在映射的時候更注重點和點之間的距離，盡可能讓點和點之間在低維空間的距離可以保持像在高維空間中一樣。使用迭代優化(iterative optimization)最小化**stress**。
- **stress：**
指**擬合度(goodness-of-fit)**，stress越小越接近0則代表擬合地更好。

**2. Non-metric multidimensional scaling (NMDS) 非數值多元尺度分析**
NMDS 更在意的是點和點之間的排名，即在降維成低維空間後點和點的誰比較近/遠，而非彼此之間的距離。

- 多維尺度分析可以用在多個領域，例如：行銷學。降維之後的結果也常被以 **感知圖/知覺圖(Perceptual Map)** 的方式呈現。以利圖視分析不同資料點的定位差異，如下圖。

[Reference_MDS_1](https://medium.com/marketingdatascience/%E5%AE%9A%E4%BD%8D%E6%8A%80%E8%A1%93-%E5%A4%9A%E5%85%83%E5%B0%BA%E5%BA%A6%E5%88%86%E6%9E%90-multidimensional-scaling-b21c8a99dfb4)
[Reference_MDS_2](https://www.youtube.com/watch?v=Yt0o8ukIOKU)
[Reference_stress_1](http://cda.psych.uiuc.edu/mds_509_2013/readings/systat_scaling_manual.pdf)

---
## Dispersion, Principal Component Analysis

### **Principal Component Analysis (PCA) 主成份分析**

- 主要為降維投影作用，降維可以有助於高維資料視覺化以及減少計算量。讓資料量變小的同時仍可維持顯著的趨勢，投影過後還仍可以符合最大可分性和最小重構性。
1. **最大可分性**：點在投影後不可以全部都太集中，才可以保有區別性。即 **variance（方差、變異數）** 越大，沿該線的資料點的離散度就越大。
2. **最小重構性：** 可以讓原本點到投影點之間的距離盡量小一些，以減少降維之後的差異。

- PCA會想要去找到一條盡可能最擬合每個點的線，即每一個點到投影在此條線上的點距離必須最小化。


- 算點到直線距離時可以採用 **勾股定理 $a^2$ = $b^2$ + $c^2$** 的概念，因為點不動，所以點到原點的距離固定（即 $a^2$ 數值固定）。因此想要 $b^2$ 總合最小化，可以從計算 $c^2$ 下手，算出 $c^2$ 最大的值即為 $b^2$ 最小的值。


這時候每一個點在找出直線上的投影點到原點的距離則可以 $Cn^2$ 表示，即要最大化 $C1^2$ + $C2^2$+ $C3^2$..+ $Cn^2$。此時這條直線就叫做「主成分1」，即PC1。

- 假設現在樣本只有兩個特徵，PC1斜率為 1/4，則代表樣本依照特徵 $x1$ 在x軸移動四個單位時，會在y軸特徵 $x2$ 會移動一個單位，即代表 $x1$ 比 $x2$ 更影響特徵分佈。
- 完成PC1之後就可以接著進行PC2，PC2會是描述樣本分佈的另一個維度，需要在這個平面上取出和PC1相差最大的PC2，以去抓去盡可能多的訊息。因此選定和PC1線**垂直正交(orthogonal)** 的線。
- 最後再把PC1和PC2轉成新的X,Y軸為新的座標系統再重新表示樣本的分佈（如下面動態影片呈現）。


- 如果此時有n維的空間，則可以分出n個樣本，以此類推PC3需要跟PC1和PC2都正交，確保提取出的主成分之間是獨立的，每個主成分都捕捉到數據中的新變異性。
- PC1會保留有最大的特徵值，依序PC2, PC3...會帶有越來越小的特徵值。每個主成分都是由原始數據的線性組合組成的，而這些線性組合是通過 **特徵值（eigenvalue）** 和 **特徵向量（eigenvector）** 來確定的。特徵值表示每個主成分所解釋的變異性的量，而特徵向量則表示主成分的方向（詳細計算和線性代數的概念有關）。
- 因此可以用**碎石圖(scree plot)** 去表示「先陡後緩」的訊息量。碎石圖因為看起來像是碎石坡，而岩石掉落並堆積在山坡上所以先有一個急降，然後接著會比較平緩。也會選擇一條"elbow"線，並選擇此條線以上的所有資訊。

[Reference_PCA1](https://www.youtube.com/watch?v=WquvZBWzI5Q)
[Reference_PCA2](https://www.youtube.com/watch?v=FgakZw6K1QQ)
[Reference_PCA3](https://leemeng.tw/essence-of-principal-component-analysis.html)
[Reference_ScreePlot](https://sanchitamangale12.medium.com/scree-plot-733ed72c8608)

### **Dispersion 離散分佈**

- 可用來計算一個字被使用得多廣，多計算該字詞出現在多少個文本之中。
- 計算離散度的方式有很多種，假設以chi-square的方式計算，可以假設一詞在文本中的分散程度為平均，再計算chi-square視是否計算出的數值與期望值相差很大，即可知某一詞在文本之間分佈是否平均、離散程度為何。在訊息檢索上，TF-IDF一樣含有dispersion的概念。

- **Term Frequency - Inverse Document Frequency (TF-IDF)：**$$TF-IDF(t, d) = TF(t, d) × IDF(t)$$
- **TF即詞頻（term frequency）**：看一個字在一篇文章中出現幾次，即在總字數中所出現過的次數。
- **IDF即逆文件頻率（Inverse Document Frequency）**：考慮一個字在語料庫中多少個文章中出現過。
公式中N為文章總數，df(t)為一單詞t出現的文章數。為了避免單詞完全沒有出現分母會為0，所以在分母加上1。但實際上TF-IDF的計算有許多變體，有考慮不同加權的計算。為方便計算IDF也取log，因大多時候文本數量很大。

$$ IDF(t) = log(N / (1 + df(t))) $$
- IDF出現在多少不同的文章。舉例一些常出現的stopwords，例如：the, a/an，高頻率出現在每一個文章中，但卻沒有帶有訊息量、不具區辨性。因此如果一個詞在語料庫中的每一個文章都很常出現，則會有很低的IDF，相反而言如果只有在幾個文章中出現，就會獲得較大的IDF值。考慮IDF才可以知道某些詞是不是只有出現在單幾個文章中，詞頻很低，但是可以有效地區分某些文章、帶有區辨的訊息。

[Reference_TFIDF_1](https://www.cc.ntu.edu.tw/chinese/epaper/0031/20141220_3103.html)
[Reference_Dispersion_1](https://www.tandfonline.com/doi/abs/10.1080/09296174.2020.1782716)

## Entropy
### Entropy (Information Entropy)
- Entropy (熵) 的概念出自於熱力學，描述物理系統之無秩序或亂度的量度。之後在資訊領域也有 information entropy 「資訊熵」的概念，描述資訊的「不確定度」。

- 在理解上可以從「事件發生所帶來驚奇程度的平均值」幫助理解，因此講 entropy 之前需要先講 驚喜度(surprise)。
舉例：今天箱子裡面有 999 顆橘色球和 1 顆藍色球，伸手抽出橘色球的 機率(probability) 就遠高於抽出藍色球的機率。如果今天只抽一次就抽出藍色球，相對的驚喜度就會很高。

所以可以說，越低的機率會有越高的驚喜度；相反來說，越高的機率，驚喜度就會相對比較低。

聽起來機率和驚喜度是相反的，但兩者之間的計算不能單純以倒數呈現，其中原因之一如果機率 = 1，機率倒數 (inverse of probability) 之後驚喜度會 = 1。
例如：有一個硬幣怎麼躑都是正面，這樣正面的機率為1。在倒數之後，驚喜度還是為1。如果想要這時候的驚喜度為 0 的話，就**必須取log** (log1=0)。另外，如果硬幣只會出現正面，這樣出現反面的機率為 0，而分母不可為0，同時可以解釋為量化不可能出現事件的驚喜度是沒有意義的。（如下圖）

- Note: 當像在硬幣這樣的例子中，只會有正面或反面的兩種情況時，通常在計算這樣例子的驚喜度取log時會使用底數2，而非底數10。

- 如下例子，在計算硬幣 正面(p=0.9) 和 反面(p=0.1) 的時候，可以看見例子中「兩次正面後一次反面」的機率為 (0.9 * 0.9 * 0.1)。下圖計算其驚喜度 ( 即log₂(1/probability) )的結果最終其實就等於**驚喜度的加總** (probability: 0.9 = surprise: 0.15 ; probability: 0.1 = surprise: 3.32)。


- 假設現在躑硬幣100次，計算平均的驚喜程度，也就是正面出現100次跟每次帶來的驚喜程度，還有反面出現100次以及其帶來的驚喜程度，最後除以100，就可以計算出每一次躑硬幣的平均驚喜程度，也就是 Entropy（每一次躑硬幣的不確定度）。

- 從上面可以看到分子和分母的100（躑硬幣100次）可以對消，所以其實 entropy計算上就是每一個機率和其驚喜度相乘之後的總和（如下圖）。

- 從這裡就可以進一步去推導出 Entropy 的公式：
把 `log(1/p(x))` 拆解成 `[log(1) - log (p(x))]` ，因為`log(1) = 0` 所以這部分又可以等於 `[0 - log(p(x))]` ，即 `- log (p(x))`，把負號往前移就可以得到 Shannon 最初提出的 Entropy 公式如下：

$$ H(X) = -∑ p(x) * log(p(x)) $$

- 而 Entropy 可以用來量化相似和相異程度，也是 Decision tree 中決定樹要如何往下做每一個決策的衡量標準之一。

[Reference_Entropy_1](https://www.youtube.com/watch?v=YtebGVx-Fxw)
[Reference_Entropy_2](https://medium.com/%E4%BA%BA%E5%B7%A5%E6%99%BA%E6%85%A7-%E5%80%92%E5%BA%95%E6%9C%89%E5%A4%9A%E6%99%BA%E6%85%A7/entropy-%E7%86%B5-%E6%98%AF%E7%94%9A%E9%BA%BC-%E5%9C%A8%E8%B3%87%E8%A8%8A%E9%A0%98%E5%9F%9F%E7%9A%84%E7%94%A8%E9%80%94%E6%98%AF-1551e55110fa)

### Relative entropy vs. Cross entropy

- **Relative entropy**
又稱為Kullback-Leibler distance、Kullback-Leibler divergence（KL散度）。
$$ D(P || Q) = ∑ P(x) * log(P(x)/Q(x)) = ∑ P(x)logP(x) - P(x)logQ(x) $$

- 是用來量化兩個機率（P 和 Q）分佈的相對差異有多大，計算兩者之間的差距。從上面公式也可以解釋為「需要**額外**多少個資源，才能用 機率分佈P 完整描述 機率分佈Q」。
因此當兩者分佈相同時，relative entropy 會為0；而兩者分佈差異越大的話，relative entropy 越大。

- **Cross entropy**
用來衡量一個機率分佈 Q 對於一個機率分佈 P 的表現的指標。
從公式來看，cross entropy 只考慮 relative entropy 的後半，即「若用表示 機率分佈P 的方式描述 機率分佈Q 需要多少資源」。
$$ H(P, Q) = -∑P(x) * log(Q(x))$$

- 機器學習中理想會希望模型預測答案跟正確答案之間越相近越好，為了計算模型預測出的標籤分佈和正確答案的標籤分佈之間的差異，cross entropy 可以用來當作模型訓練的 損失函數(loss function)。P 即為真實數據的機率分佈，而 Q 為模型預測的機率分佈。因此，計算出來的 cross entropy數值越小，即預測出來的結果跟真實數據越相近。

[Reference_relative/cross_entropy_1](https://flag-editors.medium.com/%E6%A9%9F%E5%99%A8%E5%AD%B8%E7%BF%92%E5%8B%95%E6%89%8B%E5%81%9Alesson-10-%E5%88%B0%E5%BA%95cross-entropy-loss-logistic-loss-log-loss%E6%98%AF%E4%B8%8D%E6%98%AF%E5%90%8C%E6%A8%A3%E7%9A%84%E6%9D%B1%E8%A5%BF-%E4%B8%8A%E7%AF%87-2ebb74d281d)