Single Factor Multi-Level ANOVA 概念入門

簡介
在日常生活中，我們經常比較不同數據的差異。可是，由於 T 檢定只支援兩組數據的比較，若果想使用 T 檢定去比較多於兩種數據，就需要進行多次比較，比較費事失事。

例如：我們想比較年青人、中年人、老年人的心肺功能。我們採集了三組數據 (Teen, Adult, Elderly) 之後，如果用 T 檢定，我們需要同時檢定：Teen VS Adult，Teen VS Elderly 和 Adult VS Elderly 共三次比較，才能得出 μTeen = μAdult = μElderly 的結論。當處理多種數據時，這種情況將會更加嚴重，比較次數將會更多。

所以，統計學者們發明了 ANOVA (Analysis of Variance) 來解決比較多組數據的問題。

條件
ANOVA 假設所有數據均為常態分布 (normally distributed)，而且每組數據均為獨立事件 (independent events)。另外，為確保實驗不會受時間等偏差影響，每組實驗的次序都需要隨機運作 (randomized sequence)。

還有，一般來說，因子應該是類別數據 (categorical variable)（例如年齡群），而依變數 (dependent variable) 應該是連續數據 (continuous variable)（例如血糖指數）。試想想：如果依變數是類別數據的話，ANOVA 的公式就用不上了：因為根本沒有數字可以代進去呢！

界定準則
ANOVA 在於找出「這個因子 跟 實驗誤差 之間，到底有多大差距」。舉一個例子：一個人懂得多少種語言，與他的身高並沒有任何關係。所以，當你收集了有關語言數與身高的數據，經過計算，你會發現該因子組內的變異 (sum of square)，跟實驗誤差 (experimental error) 沒有太大差別（也就是說，幾組數據都長得差不多，並沒有明顯的差別）。ANOVA 正正運用這個特性，來判斷不同數據之間，會否受因子的改變而產生變化。如果不同數據，確實因為因子的改變而產生了變化，我們就能肯定，幾組數據的平均值存在差異（也就是說，由 μ1, μ2 ... 至 μN 之中，至少有一個或多個數值並不相等）。

公式
假設數據的確會因為因子改變而改變，我們就可以用以下公式 (effect model) 表達其關係，當中 y 是指單一實驗結果，μ 是指總平均 (global mean)，τ 是指因子變化產生的影響，ε 則指各數據與總平均之間的誤差：

由此可見，若果因子變化的確會影響實驗結果的話，τ 的數值一定需要十分明顯，甚至必須比 ε 大得多。從以上觀察，我們可以推算下面的公式。

下圖中， Treatment 表示因子 (Factor) 的不同數值，N 是總 sample 數量，n 是 每組的 replicates 次數（或 sample count），a 是因子組數目。以心肺功能例子來講，假設有三組人（青年、中年、老年），而每組有 15 個人的話，N = 15*3 = 45，a = 3， n = 15，當中 N-a 可移項變成 a(n-1)。

Sum of Square between treatments (SST) 是指以下項目的總和：

• 15 個青年人的血糖數據的平均，減去全部人的平均血糖數據，次方，再除以 15，
  得到類似「青年人平均的變異量 (Sum of square of teenagers) τ Teen」
• 15 個中年人的血糖數據的平均，減去全部人的平均血糖數據，次方，再除以 15，
  得到類似「中年人平均的變異量 (Sum of square of adults) τ Adult」
• 15 個老年人的血糖數據的平均，減去全部人的平均血糖數據，次方，再除以 15，
  得到類似「老年人平均的變異量 (Sum of square of elderly) τ Total」 

Sum of Square of Experimental Error (SSE) 是指以下項目的總和：

• 每一個人的血糖數據，減去全部人平均血糖數據，次方，得到類似 ε。

只要我們比較一下 τ 和 ε 的比例差別，就能判斷因子的變化，是否真的影響數據結果。
但比較之前，我們必須先將 SS 換算成 MS，將所有數據變成同一個單位。

界定準則與判定
跟 T 檢測一樣，我們同樣使用 Significance Level (α) 來判斷。

H0 (Null Hypothesis) =  μ1 = μ2 = ...= μN
Ha (Alternative Hypothesis) = 有一個或以上的 μi 不相等。
不過今次只有 one-sided test，因為 ANOVA 只能判斷 μ1, μ2 ... 之間有一個或多個不相等。

經過計算後，如果 p-Value 比 F_α, a-1, N-a 小的話，Null Hypothesis 則不成立。
（又或者說，F0 > F_α, a-1, N-a 的話，Null Hypothesis 則不成立）
（可理解成「 Null Hypothesis 真實的可能性太低，或者我錯誤否定它的可能性太低」）

使用電腦運算
使用圖形化的 SPSS 可參考：https://www.yongxi-stat.com/one-way-anova-indenpedent/
（註：當中的 Tukey / Fisher's LSD 是 Post ANOVA 方法，用來找出那一個  μi 與眾不同）

使用 MATLAB 可參考： https://www.mathworks.com/help/stats/one-way-anova.html

小結
Single Factor Multi-Level ANOVA (One-Way ANOVA) 能有效找出當一個因子的數值改變時，產生的數據是否仍然一致。對於 Performance Tweaking 等情況，這種方法特別有用。另外，如果需要加入多種因子，研究多種 factor 及其 interaction effect 的話，可使用延伸版的 Two Way ANOVA。

Two Sample t-Test（T 檢定）概念入門

簡介
日常生活中，我們常常需要比較兩種數據的差別。例如，我們想比較 A 分店與 B 分店的銷售額，又或者在食品生產過程中，我們想比較不同日子生產的貨品，重量到底有沒有差別。近年來，機器學習的流行，令不少人也想找出，更改參數到底令系統有多少實際進步。

一般來講，不採用任何統計學的方法的話，我們可以用平均值來判斷。但採用這種方法，我們難以界定兩組數據，是否「有明顯差別」。特別是當兩組數據的方差不一，但平均值相同的時候，我們很容易下錯判斷，誤以為兩者完全相同（反之亦然）。所以，T 檢定可以運用統計學的原理，幫助我們系統化地檢驗兩個平均值是否真的相等。

例如在以下圖片中，有兩組不同數據，到底他們相差多少？若果 Factor Level 2 的方差再大一點，大得把 Factor Level 1 的平均值也包含在它的 Bell Curve 之內的話，這樣算不算「沒有明顯差別」？ T 檢定正是針對以上的問題，提出一個系統化的解法。

條件
要使用 t-Test，首要條件必須是兩組數據都屬於常態分布 (two datasets are normally distributed)。而且，實驗必須以隨機順序方式 (randomized sequencing) 進行，否則結果將不準確，可能會有偏差 (bias)。

假定
原假定 (Null Hypothesis, H0) 是指「預期中的情況」，也就是兩個平均值一樣 ( μ1 = μ2 )
替代假定 (Alternative Hypothesis Ha) 是指「不在預料之中的情況」，有三種可能：

1.  μ1 >  μ2（其中一種 two sided alternative hypothesis）
2.  μ1 <  μ2（另一種 two sided alternative hypothesis）
3.  μ1 !=  μ2 (one sided alternative hypothesis)

界定準則
要判斷兩者是否相等，需使用以下的標準：

• P(Type I Error) = P(reject H0 | H0 is true) （也稱作 α 或 significance level）
  這是指「當 H0 是真實的情況下，你錯誤地否認 H0 的機會率」。當這個數字越高，反映著 H0 是真實的機率其實很高，或者你錯誤地否認 H0 的機率很高。相反，這個數字越低，代表 H0 很可能不是真實，或者你否認 H0 的決定並沒有錯。
• P(Type II Error) = P(failed to reject H0 | H0 is false) （也稱作 β 或 1-Power）
  這是指「當 H0 是錯的情況下，你沒有否認 H0 的機會率」。當這個數字越高，反映著 H0 根本就是錯的機率很好，或者你沒有正確否認 H0 的機率很好。相反，這個數字越低，反映 H0 是錯的可能性很低，或者你做錯判斷的可能性很低。基本上來講，β 越低，反映整個研究的誤差（也就是誤判的機率）很低。
• Power = 1 - β
  Power 越高，反映研究的誤差越低（也就是研究越 Powerful）。相反，越低代表誤差越大，可靠度越低。

標準公式
T 檢定有兩種：

第一種屬於 Pooled Test，是指研究數據並沒有分任何指定對象，每次都是隨機從彩池（所以就叫 Pool）中抽出來的數據，這種情況應用以下公式：

當中 S 是指從數據中計出來的方差，而 DOF 則會是 n1+n2-2。以上公式假設在理論環境之下，兩者的方差一致（也就是大部分情況）。如果實際上並非如此，或者你不能肯定以上假設的話，可應用另一公式，當中 v 是指 DOF：

第二種屬於 Paired Test，是指研究數據有分指定對象，兩組數據均由同一批人中抽取出來。這種測試特別對於減肥實驗、酒精測試等實驗十分重要：因為每個人的體質均有差別，使用 Paired 的方法可以有效減少不必要的外在因素。這種情況可用以下公式：

不理解公式原理亦無傷大雅，只需知道以上公式，主要是由 CLT 中推演出來即可。

判定是否相等
假設 Significance Level (α) 設定為 0.05，這是指「只要 H0 真實／我判錯的機會率低於 5%，我將會判定 H0 為可信」。首先，我們使用以上公式找出 t0，然後根據 t0 及 DOF，查找 t distribution table 後，我們得出 p-Value。這個 p-Value 將會與 α 作比較：

• 若 p-Value 大於 α，我們將斷定 H0 為不能否認，也就是承認 μ1 =  μ2，兩組數據相等。
• 若 p-Value 少於或等於 α，我們將否認 H0，採納 Ha。
• 若果情況為 Two-sided Test， α 需要除二，代表兩邊共享 α 的 5%，也就是每邊 2.5%。

使用電腦計算
知道以上基本概念，我們可以將所有數式交由電腦計算。主流而言，R/MATLAB/Python/SPSS 均有支援，但以 SPSS 圖形化界面的教學最多，其次是 MATLAB 的文檔最仔細。是次以 MATLAB 的文檔作示範，我們可以用 Two-sample T-Test (ttest2) 函數庫來進行計算：

首先，預備兩組資料：

load examgrades
x = grades(:,1);
y = grades(:,2);

執行 ttest2 算出 μ1 (from x) 與 μ2 (from y) 是否相等：

[h,p,ci,stats] = ttest2(x,y)

當中，h=0 指在默認 α=0.05 下，不能否認 Null hypothesis。

小結
使用 Two Sample t-Test 可以有系統地分辨兩組數據的相似度，所以，對於機器學習訓練等研究來講，特別有用。因為要評測神經網絡的性能，不能單看準確度，更要看當參數改變後，兩個結果有沒有顯著進步和差別，繼而找出最有影響力的參數，加以調整。

Scyther Formal Verification 入門與安全特性

1. 使用 Scyther 的動機
Scyther 是一套自動挖掘網絡協議 (Network Protocol) 漏洞的軟件。由於用手計算／用算式去推算漏洞的步驟十分繁複，系統性也不高，所以研究人員都偏向採用這類驗證工具（Formal Verification Tools）去找不同協議的問題。

Scyther v1.1.3 截圖

Scyther 屬於進程演算 (process calculi) 的驗證工具，特點在於每一個協議參與者均會有一個 Role（角色），而研究人員則只需要按著不同的角色去編寫程序。同類型的例子還有 AVISPA 和 ProVerif。相比起 rule-based 的 Tamarin Prover，Scyther 更簡單直覺，但壞處則是原生支援的算法也比 Tamarin 少。

---

2. Scyther 中的不同名詞

在進程演算的工具中，Agent 主要指「執行 Role 的代理人」，在 Scyther 中它的角色並不明顯。此外，Nonce 則指「一次性編碼」（number used once），大概就是 token 的意思。

另外，Scyther 的 Threat Model 是基於 Dolev-Yao Model。簡單來說，它指的是攻擊者對網絡有全權控制（包括但不限於截取信息、更改順序、修改信息內容、扮作信息接收者等）。但另一方面，它也假設了加密算法完全可靠（也就是說攻擊者唯一知道加密內容的方法，就是要找出密碼）。所以，這種假設專門針對協議上的邏輯問題，並排除了加密算法的漏洞、或者是電腦病毒、內鬼泄露機密等其他因素。

還有以下數個，在 Scyther 的協議中常見的 Role Terms:

• Var - 變數名
• Fresh - 新鮮變數名，會隨著建立新實體 (instantiation) 時派一個新的初始值
• Role - 角色（例如 Alice 和 Bob）
• Func - 函數名
• sk(RoleTerm) / pk(RoleTerm) / k(RoleTerm, RoleTerm) - 密鑰（私鑰／公鑰／對稱）
• pk(rt)^-1 = sk(rt) - 公鑰的 inverse key 就是私鑰，反之亦然
• Run - 類似 Thread / Process 的概念，就是經過實體化（instantiation）的 Role。
• RunTerm - 在 run 中的已實體化變數 
• RunEvent - 將 Role 實體化成 Run 的事件 (Event)
• Agents - 執行 Role 的代理人
• RID - unique run identifier

而 Scyther 的基本文法也十分清晰：

• send(R, R', rt) - 由 R 傳送到 R'，內容為 rt
• claim(R, c) - R 需要滿足 security claim c 
• claim(R, secret, rt) - R 需要確保變數 rt 的機密性 (secret to adversary)

---

3. Scyther 中的不同驗證強度 (Aliveness / Synchronization / Agreement)
對方存在 Aliveness:

• Weak Aliveness - 對方存在，且成功運行協議（假設對方絕對可信）
• Weak Aliveness in the Correct Role - 對方存在，且身份正確（Alice 找 Bob，而非兩個 Alice）
• Recent Aliveness - 對方近期存在，且成功運行協議（利用 token 確保對方未死）
• Recent Aliveness in the Correct Role - 對方近期存在，且身份正確（確保 Alice 找到未死的 Bob）

成功同步 Synchronization:

• Non-injective (non one-to-one) Synchronization - 成功運行整個協議（不會因被攻擊，以致只運行到一半）
• Injective Synchronization - 成功運行整個協議，而且對方也是一對地成功運行

協議內容同步 Agreement:

• Non-injective Agreement - 運行協議後，變數 (Variables) 得到預期的結果
• Injective Agreement - 運行協議後，變數得到預期結果，而且只能一對一地運行（不能有 Intruder 先發送一個請求，然後 Alice 接手回應的情景） 
• Weakagree - 所有協議執行者，均扮演著預期的角色。例如有三個人，他們知道自己是A，B 和 C，而其餘兩個人都正確知道，自己正在跟 B,C / A,C / A,B 對話。

安全強度表：

---

4. Scyther 的實例
參考 /scyther-mac-v1.1.3/Protocols/needham-schroeder-lowe.spdl
運行截圖：

---

Reference:

[1] The Scyther Tool - https://people.cispa.io/cas.cremers/scyther/index.html
[2] Operational Semantics and Verification of Security Protocols - https://www.springer.com/gp/book/9783540786351