Hui-Yu Huang's Blog

To Live is to Wonder


  • 首頁

  • 關於

  • 分類

  • 歸檔

中央極限定理(Central Limit Theorem, CLT)和Pyro實現

發表於 2019-08-14 | 分類於 Statistics

中央極限定理(Central Limit Theorem, CLT)和Pyro實現

中央極限定理: 假設一母體平均數\(\mu\), 標準差\(\sigma\), 從中隨機抽取樣本數\(n\), 當\(n\)夠大時, 樣本平均數的抽樣分配會近似於常態分配

假設 \[ X_1, X_2, ..., X_n \sim i.i.d.\ N(\mu, \sigma^2) \]

\[S_n = X_1+...+X_n \] 則中央極限定理: \[Z_n = \frac{S_n-n\mu}{\sigma\sqrt{n}} \to N(0,1)\ \ as\ \ n \to \infty \]

可寫成: \[Z_n=\frac{\bar{X}-\mu}{\sigma/\sqrt{n}}\]

故:

\[E(\bar{X})=\mu_{\bar{X}}=\mu\]

\[Var(\bar{X})=\sigma_{\bar{X}}^2=\frac{\sigma}{n}\]

一般實務上樣本數\(n\)大於\(30\)就視為CTL, 也就是樣本平均數為常態分配, 且樣本平均數的平均數近似於母體平均數, 樣本平均數的變異數近似於母體變異數除以n


例如:

有一枚硬幣投到正面機率P(X=1)=0.8, 投到反面機率P(X=0)=0.2, 假設連續投160次, 其中(平均來說)投到正面次數大於130次的機率是多少?

Step 1. 計算母體平均數與母體變異數

假定硬幣投值隨機變數\(X\)為伯努利分布(Bernoulli distribution)

\[\mu = E(X)=p=0.8\]

\[\sigma^2 = Var(X)=p(1-p)=0.16\]

Step 2. 計算\(\bar{X}\)的平均數與\(\bar{X}\)的變異數

\[\mu_{\bar{X}} = \mu =0.8\]

\[\sigma_{\bar{X}}^2 = \frac{\sigma^2}{n}=\frac{0.16}{160}=0.001\]

Step 3. 用標準常態分佈的cdf求解

\[P(X_1+...+X_n>130) = P(\bar{X}>\frac{130}{160}) = P(Z>\frac{\frac{130}{160}-0.8}{\sqrt{160}})\]

利用python套件scipy來求解\(\Phi^{-1}(Z)\)

1
2
3
4
import numpy as np
import scipy.stats as stats
z = (130./160. - 0.8) / np.sqrt(0.001)
print( stats.norm.cdf(z, loc = 0, scale = 1) )

0.6536836079790194

故

\[P(X_1+...+X_n>130)=1-\Phi^{-1}(\frac{\frac{130}{160}-0.8}{\sqrt{160}})=1-0.6536 = 0.3464\]


以下是用Pyro實現中央極限定理(CLT)的程式碼驗證與信賴區間計算:

Pyro是一Uber開源深度機率程式語言, 它基於Python和PyTorch。

安裝:

1
$ pip install pyro-ppl

首先引入表頭

1
2
3
4
5
6
7
8
9
import pyro
import pyro.distributions as dist
import numpy as np
import scipy.stats as stats
import pandas as pd
import matplotlib.pylab as plt
import seaborn as sns
#import warnings
#warnings.filterwarnings('ignore')

建立一個母體, 這裡用Beta分佈, 也可以換成其他分佈來試試看

1
2
3
4
5
# 給定一個母體
param = (1, 9)
distribution = dist.Beta(*param)
print("母體平均數:{:.4f}, 母體標準差:{:.4f}" \
.format(distribution.mean, distribution.stddev))

母體平均數:0.1000, 母體標準差:0.0905

1
2
3
4
5
6
7
# 嘗試用此母體來sample出一些樣本
n = 100
samples = distribution.sample((n,))
print("樣本平均數:{:.4f}, 樣本標準差:{:.4f}" \
.format(samples.mean(), samples.std()))
# 嘗試畫出圖形來看分佈
sns.distplot(samples)

樣本平均數:0.0853, 樣本標準差:0.0846

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
# 改變n的大小, 用此母體sample出一些樣本, 並用KS-test來檢驗是否為常態分佈
# 假定若KS-test的p-value小於0.01就視為常態分佈
# 可以從樣本平均數, 樣本數n, 和母體標準差σ估算99%信心水準的信賴區間
alpha = 0.01 # 可容忍的型一誤差
confidence_level = 1-alpha # 信賴水準99%
mu = distribution.mean.numpy() # 母體平均數
sigma = distribution.stddev.numpy() # 母體標準差
Phi_inv_z = stats.norm.ppf(1-alpha/2)
columns=["樣本數n", "樣本平均數", "樣本標準差", "KS-test p-value", \
"KS-test 是否為常態分佈", "信賴區間_下界", "信賴區間_上界", \
"母體平均數是否落在信賴區間內" ]
rows = []
samples_collect = {}
for n in range(1,31):
samples = distribution.sample((n,))
samples_collect.update({n:samples})
mean_sample, std_sample = samples.mean().numpy(), samples.std().numpy()
_, p = stats.kstest(np.array(samples),"norm")
CI_lb = mean_sample-Phi_inv_z*sigma/np.sqrt(n)
CI_ub = mean_sample+Phi_inv_z*sigma/np.sqrt(n)
rows.append([n,
mean_sample.round(4),
std_sample.round(4),
p.round(4),
p<0.01,
CI_lb.round(4),
CI_ub.round(4),
(CI_lb<=mu)&(CI_ub>=mu)
])

df = pd.DataFrame(data=rows, columns=columns)
df

1
2
3
4
5
6
# 嘗試畫出圖形來看分佈
for n in [1,5,10,15,20,30]:
samples = samples_collect[n]
sns.distplot(samples, label="n="+str(n))
plt.legend()
plt.show()

可以看到當n越大, 樣本平均數\(\bar{X}\)越接近常態分佈。

貝氏估計法(Bayes Estimation)介紹

發表於 2019-08-14 | 分類於 Statistics

貝氏定理(Bayes Theorem)

\[P(A|B)=\frac{P(A \cap B)}{P(B)}=\frac{P(B|A) \times P(A)}{P(B)}\]

其中\(P(A|B)\)是已知\(B\)發生的情況下, \(A\)發生的機率, 稱作\(A\)的事後機率或後驗機率(posterior probability)

而\(P(A)\), \(P(B)\)稱作事前機率或先驗機率(prior probability)

\(P(B|A)\)是已知\(A\)發生的情況下, \(B\)發生的機率, 在此稱作概似函數(likelihood function)

可以把貝氏定理理解成:

\[ 後驗機率 = \frac{ {概似函數} \times {先驗機率} }{標準化常量} \]

\[P(A|B)=\frac{P(B|A) \times P(A)}{P(B)}\]

貝氏統計

相對於之前介紹的MLE是頻率學派的點估計, 其分布的參數是固定值, 貝式學派自成一格, 它將分布的參數視為一個隨機變數, 也就是每個參數來自一個機率分布, 而非固定值

因此貝氏統計中不但可以算樣本統計量的機率, 還可以算參數的機率

假設\(X\)服從分布pdf 為\(P(x|\theta)\), 利用貝氏定理寫成連續的形式:

\[f_{x|\theta}(\theta)=\frac{ f(x_1,...,x_n|\theta) f_{\theta}(\theta)}{\int \ f(x_1,...,x_n|\theta) f_{\theta}(\theta)\ d\theta}\]

其中, \(f_{x|\theta}(\theta)\) : 後驗機率 \(f(x_1,...,x_n|\theta)\) : 概似函數 \(f_{\theta}(\theta)\) : 先驗機率 \(\int \ f(x_1,...,x_n|\theta) f_{\theta}(\theta)\ d\theta\) : 標準化常量


若假設樣本為常態分佈:

\[ X_1, X_2, ..., X_n \sim i.i.d.\ N(\mu, \sigma^2) \]

假設\(\mu\)未知, \(\sigma^2\)已知 試用貝氏統計來估計\(\mu\)

假設\(\mu \sim N(\mu_{0}, \sigma_{0}^2)\)是一個normal distribution, 則\(\mu\)的pdf可以寫成:

\[ f(\mu)=\frac{1}{\sqrt{2\pi\sigma_{0}^2} } \ exp(- \frac{(\mu-\mu_{0})^2}{2\sigma_{0}^2})\]

樣本的pdf可以寫成: \[ f(x_1,...,x_n|\mu)=\frac{1}{ {(2\pi\sigma^2)}^{\frac{n}{2}} }\ exp(- \frac{\sum_{i=1}^n(x_i-\mu)^2}{2\sigma^2})\]

兩者的joint probability為:

\[f(x_1,...,x_n,\mu) = \frac{1}{ {(2\pi\sigma^2)}^{\frac{n}{2}} \sqrt{2\pi\sigma_{0}^2} }\ exp(- \frac{\sum_{i=1}^n(x_i-\mu)^2}{2\sigma^2} - \frac{(\mu-\mu_{0})^2}{2\sigma_{0}^2})\]

上式經過整理得到:

\[f(x_1,...,x_n,\mu) =\frac{1}{\sqrt{2\pi\sigma_{post}^2} } \ exp(- \frac{(\mu-\mu_{post})^2}{2\sigma_{post}^2})\ h(x_1,...,x_n,\sigma, \mu_0, \sigma_0)\]

上式整理過程中, 與\(\mu\)沒有相關的函數一律包含進\(h\)函數中

因此後驗機率可以得到:

\[f(\mu|x_1,...,x_n) =\frac{1}{\sqrt{2\pi\sigma_{post}^2} } \ exp(- \frac{(\mu-\mu_{post})^2}{2\sigma_{post}^2})\ h'(x_1,...,x_n,\sigma, \mu_0, \sigma_0)\]

上式整理過程中, 由於\(x_1,...,x_n\)與\(\mu\)沒有相關, \(h\)函數也與\(\mu\)沒有相關 , 與\(\mu\)沒有相關的函數一律再把它包含進\(h'\)函數中

發現假設\(\mu\)的先驗機率為常態分佈下, \(\mu\)的後驗機率也是一個常態分布, 其參數為:

\[\mu_{post}=\frac{\frac{\sigma^2}{n}\mu_0+\sigma_0^2 \bar{x}}{\sigma_0^2+\frac{\sigma^2}{n}}\]

\[\sigma_{post}^2=(\frac{1}{\sigma_0^2}+\frac{1}{\sigma^2/n})^{-1}(\frac{\sigma_0^2(\sigma^2/n)}{\sigma_0^2+\sigma^2/n})\]


用網站seeing theory可以互動式的去了解統計

最大似然估計法(Maximum Likelihood Estimation, MLE)介紹

發表於 2019-08-13 | 分類於 Statistics

最大似然估計法(Maximum Likelihood Estimation, MLE)是一種頻率學派的方法, 是統計上很常用的點估計方法

似然函數(likelihood function)是一種在參數\(\theta\)下觀察到樣本出現的條件機率:

\[ L(\theta) = \prod^{n}_{i=1} {f(x_i|\theta)} \]

多取一個log, 比較方便後續微分, 叫做對數似然函數(log likelihood function):

\[l(\theta)=log(L(\theta))=\prod^{n}_{i=1} { log \ f(x_i|\theta)}\]

以下所有的\(L\)都可以用\(l\)來代替

最大似然估計法(Maximum Likelihood Estimation, MLE)是藉由給定的樣本尋找最可能的\(\theta\), 藉此來最大化似然函數(likelihood function)的方法

\[ \max_{\theta}\ L(\theta)\]

假設存在一個唯一的\(\hat{\theta}\)使得似然函數最大化, 此時:

\[ \frac{ \partial L(\theta) }{\partial \theta} = 0\ ,\ \frac{ \partial L^2(\theta) }{\partial \theta^2} < 0 \]

其中\(x_i\)是已知的樣本, 假定\(f\)是含未知參數但形式已知的函式(假設可微分), 此時可藉由上式求解最佳母體參數\(\hat{\theta}\), 求得後, 可以用該參數的母體來進行新樣本的推論


若假設樣本為常態分佈:

\[ X_1, X_2, ..., X_n \sim i.i.d.\ N(\mu, \sigma) \]

參數\(\theta\)則為\(\mu\)和\(\sigma\), 此時的\(f\)是常態分佈的pdf(機率密度函數):

\[ f(x| \mu, \sigma^2) = \frac{1}{\sqrt{2 \pi \sigma^2 }}\ exp(- \frac{(x-\mu)^2}{2 \sigma^2})\]

此時的最大對數似然函數, 經過一次微分等於零的操作後, 可以解得\(\hat{\mu}\)和\(\hat{\sigma}\):

\[ \hat{\mu} = \bar{x} = \sum^n_{i=1} \frac{x_i}{n}\]

\[ \hat{\sigma}^2 = \frac{1}{n}\sum^n_{i=1} (x_i-\bar{x})^2\]

以上就是我們常用的母體平均值和母體變異數估計公式, 是假設常態分佈的情況下推導出來

其中, 參數\(\hat{\mu}\)的估計量滿足不偏性(non-bias):

\[E[\hat{\mu}] = \mu\]

參數\(\hat{\sigma}^2\)的估計量卻沒有滿足不偏性:

\[E[\hat{\sigma}^2] = \frac{n-1}{n}\ \hat{\sigma}^2\]

這就是樣本變異量要除以\(n-1\)的原因:

\[ s^2 = \frac{1}{n-1}\sum^n_{i=1} (x_i-\bar{x})^2\]

這樣代進去才會讓母體變異數正確地滿足不偏性

統計中的信賴區間(Confidence interval)介紹

發表於 2019-08-13 | 分類於 Statistics

信賴區間(Confidence interval,CI)這個詞經常被提及,但是否真的了解其含義呢?

推論統計(statistical inference)中的參數估計(Parameter Estimation)是利用樣本統計量或其分配來估計母體參數, 例如想估計全班的身高平均, 假設全班的身高為常態分布, 隨機抽樣幾個人算身高平均, 就把它當成全班的平均, 這就是參數估計(平均值是常態分佈的一個參數)

參數估計又分成點估計(point estimate)和區間估計(Interval Estimation)

點估計顧名思義就是估計一個點, 把這個點當作母體參數, 而區間估計就是把母體參數視為一個區間範圍, 並不侷限在一固定的點

區間估計通常先求出點估計值, 然後在一個信賴水準下導出一個信賴區間, 這個信賴區間是一組上下限, 而信賴水準是指該區間包含母體參數的可信度

舉例來說, 若我們想對母體平均值做一個信賴水準95%的區間估計, 而假設資料是常態分布, 則樣本平均:

\[ \bar{X} \sim N(\mu , \frac{\sigma^2}{n} ) \]

將它標準化:

\[ Z = \frac{\bar{X}-\mu}{ \frac{\sigma}{\sqrt{n}}} \]

信賴水準95%表示:

\[P(-z\leq Z\leq z)= 1- \alpha =0.95 \]

\(z\)是quantile, 可以用程式語言python套件scipy的scipy.stats.norm.ppf(1-0.025)求得, ppf (\(\Phi^{-1}\))是cdf的反函數

1
2
import scipy.stats as stats
stats.norm.ppf(1-0.025)

1.959963984540054

故\(z\)約等於\(1.96\):

\[P(-1.96\leq Z\leq 1.96)= 1- \alpha =0.95 \]

將標準化後的\(Z\)代入:

\[P(-1.96\leq \frac{\bar{X}-\mu}{ \frac{\sigma}{\sqrt{n}}} \leq 1.96)= 1- \alpha =0.95 \]

整理一下:

\[ P(\bar{X}-1.96 \frac{\sigma}{\sqrt{n}} \leq \mu \leq \bar{X}+ 1.96 \frac{\sigma}{\sqrt{n}} )= 0.95\]

這表示我們可以從樣本平均數\(\bar{X}\), 樣本數\(n\), 和母體標準差\(\sigma\)估算95%信心水準的信賴區間為:

\[ [ \bar{X}-1.96 \frac{\sigma}{\sqrt{n}} , \bar{X}+ 1.96 \frac{\sigma}{\sqrt{n}} ] \]

從線性模型(Linear Model)到核模型(Kernel Model)

發表於 2019-07-15 | 分類於 Machine Learning

要真正了解SVM (Support Vector Machines, 支持向量機), 必須了解什麼是核模型和核技巧, 假如只粗淺地知道它是一個最大化間隔(margin)的方法就太可惜了。以下從線性模型(Linear Model)開始, 逐步講到核模型(Kernel Model), 一窺其優雅之處。

線性模型(Linear Model)

假如我們要學習一個函數\(f\), 而假定這個函數的輸入(input)是一維的, 輸出是一個純量(scalar), 最直觀的函數模擬方式就是線性模型, 考慮一個線性加法模型, 也就是把每個\(x\)前面冠上一個參數\(\theta\), 再線性加總起來:

\[f_{\theta}=\sum_{j=1}^{d} \theta_{j}x_{j}=\Theta\mathbf{x}\]

\[\mathbf{x} = (x_1, x_2, ..., x_d)^T\]

\[\Theta = (\theta_1, \theta_2,..., \theta_d)\]

廣義線性模型(Generailized Linear Model)

然而, 當遇到複雜函數時, 線性模型顯然不足以表達, 因此定義廣義線性模型:

\[f_{\theta}=\sum_{j=1}^{b} \theta_{j}\phi_{j}(\mathbf{x})=\Theta\Phi\]

\[\Theta = (\theta_1, \theta_2,..., \theta_b)\]

\[\Phi = (\phi_1(\mathbf{x}),\phi_2(\mathbf{x}), ..., \phi_b(\mathbf{x}))^T \]

其中, \(b\)是基函數(basis function)的個數, 此時就可以來表達非線性模型了, 可以透過設計一組好的基函數, 來增加模型的表達能力。

為了把特徵空間複雜化, 通常基函數的個數\(b\)會遠大於輸入的維度\(d\) (\(b>>d\)), 這個\(\phi\)可以視為是將特徵從\(d\)維映射到\(b\)維的函數。

特徵複雜化之後可以做什麼呢?

(1)對於迴歸(regression)型任務, 特徵複雜化有助於函數擬合(curve fitting)。

(2)對於分類(classification)型任務, 特徵複雜化有助於找到好的分割超平面(hyperplane)。

這裡的基函數, 可以定義成:

\[\phi(x)=(1, x, x^2, ..., x^{(b-1)})^T\]

這種形式, \(f_{\theta}\)就成為多項式(polynomial)

或是定義成:

\[\phi(x)=(1, sin(x), cos(x), sin(2x), cos(2x)..., sin(mx), cos(mx))^T\]

\[b=2m+1\] 函數\(f_{\theta}\)就成為離散傅立葉級數(Discrete Fourier series)。

經過適當設計,可以讓\(\Phi(\mathbf{x})\)成為對\(\mathbf{x}\)進行離散傅立葉變換(Discrete Fourier Transform,DFT)。

如果考慮連續傅立葉變換, 基函數可以無窮多個, 也就是說, 甚至可以將特徵從維度\(d\)投影到無窮維。

核模型(Kernel Model)

前面講到, 廣義線性模型將特徵\(\mathbf{x}\)透過\(\phi\)映射到更多維甚至無窮維的空間, 這時候就產生一個問題: 如何設計最好的\(\phi\)?

這是一個頗難的問題, 想想看, 先不要管基函數的形式怎麼設計(多項式?三角函數?指數?), 光是基函數的個數\(b\)就難以決定: 到底要投影到幾維才足夠複雜到可以解決任務, 且維度詛咒(curse of dimensionality)又不至於太過嚴重呢?

面對這種看起來毫無頭緒的問題, 這時候需要引入一些先驗假設, 而最好的先驗知識來源, 就是我們的輸入樣本(也就是數據)。

試想, 假如數據中隱含某種模式或原則, 符合模式的那些樣本彼此之間應該距離較近; 或者換個方式說, 過去有出現過的樣本在特徵空間中的分布如果集中在某個位置, 我們可以假定下一個出現的樣本應該有比較大的機率出現在相同位置。

因此, 想要從樣本中找規律, 我們有時會希望讓不同樣本之間可以產生一些互動, 此時通常會涉及到計算:\(\phi(x_i)\phi(x_j)\), 也就是兩個特徵向量的內積, 而這個內積其實並不好計算, 尤其當特徵空間維度(基函數個數\(b\))很大的時候。

此時核函數(kernel function)\(K\)就能派上用場, 核函數是一個二元函數\(K(\cdot,\cdot)\) 是一個定義內積的函數, 可被設計, 而核模型(Kernel Model)可以表示為核函數的線性組合。

\[f_{\theta}=\sum_{j=1}^{n} \theta_{j}K(\mathbf{x},\mathbf{x}_ j)=\Theta\mathbf{K}\]

其中\(n\)是樣本數, 注意: 線性模型的基函數與樣本無關, 然而核模型設計時會用到輸入樣本 , 核函數構成的矩陣\(\mathbf{K}\)可以寫成:

值得注意的是, 核模型的參數個數只與樣本數\(n\)有關, 與輸入的維度\(d\)無關, 這代表在樣本數不大(\(d>>n\))的情形下, 核模型可以避免維度災難。

即使\(n\)很大, 只要取輸入樣本 的部分集合均值 來進行計算 $ (b<<n) $ , 維度也能得到很好的控制。

\[f_{\theta}=\sum_{j=1}^{b} \theta_{j} K(\mathbf{x},\mathbf{c}_ j)=\Theta\mathbf{K}_{b \times n}\]

核模型並非線性模型, 但是線性模型可以視為核模型的特例。

透過這種定義核函數的方法, 對基函數的內積進行特殊設計, 使得不須直接設計基函數, 透過定義核函數而隱式地(implicitly)定義了基函數, 這種方法稱為核技巧(kernel trick)或核方法(kernel method)。

核函數的設計要滿足一些條件, 核函數必須是對稱函數, 且所構成的核矩陣$ $必須要是半正定(證明可參考Scholkopf and Smola, 2002)

幾種常用的核函數如下:

  1. 線性核

\[K(\mathbf{x}_i, \mathbf{x}_j)=\mathbf{x}_i^{T}\mathbf{x}_j\]

  1. 多項式核

\[K(\mathbf{x}_i, \mathbf{x}_j)=(\mathbf{x}_i^{T}\mathbf{x}_j)^d, d\geq1\]

  1. 高斯核(一種徑向基函數核, Radial basis function kernel, RBF核)

\[K(\mathbf{x}_i, \mathbf{x}_j)=exp(-\frac{||\mathbf{x}_i-\mathbf{x}_j||^2}{2\sigma^2})\]

高斯核(RBF核)是最常用的一種kernel, 它的意義是將每個樣本的出現都視為由一個高斯分布的隨機變數\(X_j \sim N(\mathbf{x}_{j}, \sigma)\)生成, 而待學習的參數\(\theta_j\)則是這個分布的高度。

高斯核模型是用高斯核函數的加權加總在逼近一個未知函數, 這個函數逼近的過程可以看做是一個簡單神經網路。

高斯核模型又有點像是\(n\)個Component的高斯混合模型(Gaussian mixture model,GMM), 兩者都需要學習每個高斯的權重(weight), 但兩者仍有本質上的不同, GMM的機率密度函數是學習出來的, 在高斯核模型中, 期望值(Means)和共變異數(Covariances)都是固定的, 不像在GMM中是可學習的參數, 這是由於RBF核當初設計的目的是為了做多變量插值的緣故。

GCN(Graph Convolutional Network)的理解

發表於 2019-07-07 | 分類於 Graph Neural Network

在深度學習領域的人,對捲積(Convolution)應該都不陌生,但不一定聽說過圖(Graph)也可以做Convolution。這篇文章對GCN(Graph Convolutional Network)做了概略的介紹。


CNN的捲積不是數學定義上的連續捲積,而是一種定義的離散捲積。我們用這種捲積來處理圖像(image),從圖像中提取特徵,並且透過神經網路來學習捲積的權重(weight)。以下所稱的捲積都是指這種局部的離散捲積。

CNN捲積有一些特性,

(1)平移不變性(shift-invariance) (2)局部性(local connectivity) (3)多尺度(multi-scale)

這些特性,暫且把它們稱作組合性(Compositionality),讓CNN捲積只能處理在歐幾里德空間(Euclidean Structure)的數據。

什麼數據是Euclidean Structure的數據呢?最經典的就是影像(image),影片(video)和音頻(speech/voice),自然語言文本(text)透過特殊處理,也可以固定維度,投影到歐幾里德空間來操作。

然而,有一些數據結構是Non-Euclidean的,例如:

  • 生物/化學分子 Chemical/Biological Graphs

  • Citation Networks / Social Networks

  • Unstructured Graphs: 例如3D點雲, 或者是半監督學習

Non-Euclidean的數據,大致上可以當作圖(Graph)來理解。也就是可以理解成\(G=(V,E)\),由頂點(vertex)和邊(edge)所構成的一種資料格式。

Euclidean數據可以當作是Non-Euclidean的一種特例。因此對Non-Euclidean理解和處理,可以在Euclidean數據上通用,這就是為什麼Non-Euclidean數據的表示法學習有其重要性。

對2D Convolution來說,Graph Convolution的想法來自於把在圖像域(image domain)運作得很好的2D捲積神經網路方法,拿到圖域(graph domain)來使用。


要了解圖的Convolution,要先了解Convolution本質上是一種aggregation操作,它是一種局部加權平均的運算。

對圖的頂點(vertex)來說,局部指的是它的鄰居,而它的鄰居由邊(edge)的存在與否,綜合邊的權重(weight)大小去定義。簡單起見,把有邊(edge)的權重都定為\(1\),沒邊(edge)的權重都定為\(0\)。

為了探討圖的性質,我們用度矩陣(degree matrix)\(D\) 和 鄰居矩陣(adjacency matrix)\(A\)來表示一個圖。度矩陣是一個對角矩陣(diagonal matrix),度矩陣對角線上的值就是該頂點連接著幾條邊,也就是鄰居矩陣的列和。

假如是無向圖,鄰居矩陣是對稱矩陣(symmetric matrix)。

1
2
import numpy as np
D = np.sum(A, 1)

另外圖論(graph theory)還定義一個東西叫做Laplacian Matrix \(L\),它最簡單的定義是\(D-A\)。在數學及物理中,Laplacian或稱Laplace operator(拉普拉斯算子)是歐幾里得空間中的一個函數的梯度的散度給出的微分算子,通常寫成 \(\Delta\)、\(\nabla^2\) 或 \(\nabla \cdot \nabla\)。可以粗糙的視為歐幾里得空間中二次微分操作。

Laplacian物理上的解釋可以是能量的流失或是物質擴散,放在圖論上來說,即是該頂點信息(message)傳播(propagation)。

圖卷積神經網路(GCN)的單層操作,則可以(但不一定要)定義成: \[Y=LX\]

因為圖的Laplacian Matrix最簡單的定義是\(L=D-A\): \[Y=LX=DX-AX\]

對單一節點來說,式中的 \(AX\) 可以視為本次操作(每單位時間)鄰居預計要從我身上拿走的訊息量。 \(DX\) 可以視為是本次操作每個節點尚未進行傳播前,本來擁有的訊息量,即是上次操作(上一個單位時間)每個頂點從它的鄰居頂點取得的訊息量。兩者相減,就是本次操作後訊息傳播的狀況。

我們用程式碼來了解一下圖的訊息傳遞:

1
2
3
4
5
6
7
8
9
10
# 定義鄰居矩陣A,故意使它不對稱,有向圖比較容易看到訊息傳遞的狀況
import numpy as np

A = np.matrix([
[0, 1, 0, 0],
[0, 0, 1, 1],
[0, 0, 0, 0],
[1, 0, 1, 0]],
dtype=float
)
1
2
3
4
5
6
# 畫圖程式(optional)
import networkx as nx
import matplotlib.pyplot as plt
G=nx.DiGraph(A)
nx.draw(G, with_labels=True)
plt.show()

這個有向圖可以理解為,每次的\(L\)操作,每個節點會依照箭頭指出的方向去提供每個鄰居節點它所要求攜帶的訊息。

1
2
3
4
5
6
7
# 定義初始特徵
X = np.matrix([[ 100., -100.],
[ 1., -1.],
[ 2., -2.],
[ 3., -3.]])

A * X
1
2
3
4
5
#輸出:
matrix([[ 1., -1.],
[ 5., -5.],
[ 0., 0.],
[ 102., -102.]])

從以上例子就可以明顯看出,因為label=3的節點提供訊息給label=0和label=2的節點,結果得到一個很大的訊息更新。

1
2
3
D = np.diag(np.array(np.sum(A, 1)).flatten())
L = D-A
L*X
1
2
3
4
5
#輸出:
matrix([[ 99., -99.],
[ -3., 3.],
[ 0., 0.],
[-96., 96.]])

結果label=3的節點更新完後,有了很大的變化。

我們這時候應該也發現了一些問題。由於圖中沒有自環,訊息只能被鄰居不斷取走,而沒有因應自身訊息做調整。這就像是預估一個人薪水多高時,只考慮他的朋友薪水多高,而沒有把該人的自身條件考慮進去,顯然不太合理。因此,因應任務需要,可以考慮增加自環。

\[\hat{A} = A+I\]

1
2
3
4
# 增加自環
I = np.diag([1]*A.shape[0])
A_hat = A + I
A_hat

1
2
3
4
5
#輸出:
matrix([[1., 1., 0., 0.],
[0., 1., 1., 1.],
[0., 0., 1., 0.],
[1., 0., 1., 1.]])
1
A_hat * X
1
2
3
4
5
#輸出:
matrix([[ 101., -101.],
[ 6., -6.],
[ 2., -2.],
[ 105., -105.]])
1
2
3
D_hat = np.diag(np.array(np.sum(A, 1)).flatten())
L_hat = D_hat-A_hat
L_hat*X
1
2
3
4
5
#輸出:
matrix([[ -1., 1.],
[ -4., 4.],
[ -2., 2.],
[-99., 99.]])

以上的傳播矩陣,不管是\(A\)還是\(\hat{A}\)還是\(L\),與convolution相似的地方在於,它們都是一種局部的aggregation操作。然而,convolution的局部連接數是固定的,這裡卻不是這樣,每個頂點鄰居數目可能都不同。

所以,不管是\(A\)還是\(\hat{A}\)還是\(L\),都還需要進行歸一化處理。以免偏好鄰居較多的節點,讓鄰居較多的節點傳播比較多的訊息量。歸一化處理的方法有兩種:(1)算術平均(2)幾何平均

於是多定義了兩種Laplacian Matrix (1)算術平均 \[L^{rw}=D^{-1}L\] (2)幾何平均 \[L^{sym}=D^{-0.5}LD^{-0.5}\]

其中,幾何平均受極端值影響較小,\(L^{sym}\)是GCN中較為常用的 Laplacian Matrix 。

故,圖卷積神經網路(GCN)的單層操作,也可以(但不一定要)定義成: \[Y=L^{sym}X\]


Eigendecomposition / Spectral decomposition of Laplacian Matrix

假設為無向圖,此時\(L^{sym}\) (以下簡稱\(L\)) 是可以被對角化的 (原因不詳述)

由於\(U\)是正交矩陣,\(UU^T=I\),\(U^T=U^{-1}\)

其中,\(U\)是已知的,\(\lambda_l\) 特徵值是未知要求取的。但我們並不直接去求或是去優化\(\lambda_l\) 。

對一個捲積函數 \(h\) 而言,可以用傅立葉轉換的卷積定理

去證明(原因不詳述),捲積後的結果為:

其中\(\hat{h}(\lambda_{l})\)要設計成:

其中\(u^{*}\)是傅立葉轉換正交特徵向量的共軛轉置

第一代GCN

Spectral Networks and Locally Connected Networks on Graphs(2013)

直接令 \(\theta_l=\hat{h}(\lambda_{l})\)

GCN的單層操作:

第一代圖捲積跟一般CNN卷積的差異:

  1. 卷積核(kernel)只在主對角線上,並不需要是二維的,卷積核個數與頂點數(n)相同
  2. 卷積核(kernel)在主對角線上的矩陣需要經過離散傅立葉矩陣轉換(\(U\),\(U^T\))

第二代GCN

Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering(2016)

設計: \(\hat{h}(\lambda_{l})\)= K是K-hop neighbor

可以導出GCN的單層操作(推導過程略): 卷積核(kernel)是\(\alpha_j\)

第二代圖捲積跟第一代圖捲積的差異:

  1. 第一代沒有局部性,卷積核個數與頂點數(n)相同,第二代只有K個參數,計算複雜度降低很多

  2. 第一代每次向前傳播都要計算一次 \(U\ diag(\theta)\ U^T\) 三者的乘積,第二代直接拿\(L\)乘上\(\alpha_j\),計算簡單一些,但複雜度仍是\(O(n^2)\)

  3. 第二代有Parameter Sharing的部份


對GCN的介紹暫時到這邊,有空再來分享paper和程式碼。實際上程式碼並沒有理論來的那麼複雜,用numpy自己刻一個是絕對可行的,假如用deep learning套件,實際上也只有用到fc layer。基於PyTorch有非常好用且完整的套件torch_geometric,雖無法handle大圖,但拿來上手可以很快進入狀況。


轉載請附上來源連結


Reference:

  • A Comprehensive Survey on Graph Neural

  • 如何理解 Graph Convolutional Network(GCN)?

  • Spectral Networks and Locally Connected Networks on Graphs(2013)

  • Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering(2016)

BP Algorithm的理解思路

發表於 2019-07-05 | 分類於 Deep Learning

本文淺顯直白的介紹反向傳播算法(BP 算法, The Back Propagation Algorithm)的理解思路, 計算過程和程式實現


我們考慮一個最簡單的layer,這個layer有兩個input \(x_1, x_2\) 和1個output \(y_1\):

則數學式可以寫成: \[ y_1 = w_{1}x_1+w_{2}x_2\]

上式的\(w\)下標是跟著\(x\)在跑, 考慮到\(y\)可以擴展成\(y_j\)(不只一個\(y\)), 我們改一下\(w\)的下標, 也把\(y\)的標號考慮進去: \[ y_1 = w_{11}x_1+w_{12}x_2\]

其中\(w_{ji}\)的第一個下標\(j\)是跟著\(y\)在跑, 而\(i\)是跟著\(x\)在跑, 整個式子可以寫成矩陣形式: \[Y=WX\]

其中令輸入\(X\)有\(n\)維, 輸出\(Y\)有\(m\)維:

\[X=[x_1,\ x_2, ... , x_i,\ ...\ ,\ x_n\ ]^T\]

\[Y=[y_1,\ y_2, ... , y_j,\ ...\ ,\ y_m\ ]^T\]

\[ W= {\left[ \begin{array}{ccc} w_{11},\ w_{12}, ... ,\ w_{1n}\ \\ ... , w_{ji}, ... \\ w_{m1},\ w_{m2}, ... ,\ w_{mn}\ \\ \end{array}\right ]} = \{ w_{ji} \}_{m \times n}\]

通常我們還會把上式加個偏置(bias) \(B\):

\[Y=WX+B\]

\(B\)維度會和\(Y\)相同 \[B=[b_1,\ b_2, ... , b_j,\ ...\ ,\ b_m\ ]^T\]

通常還會再加個可微分的激活函數\(\sigma\)來增加其非線性:

\[Y=\sigma(WX+B)\]

以上是"前饋"(forward)的部分


接下來考慮"反向傳播"(backward)的部分,假設損失函數(loss function)\(\mathbb{J}\) 有\(d\)維, 下標用\(k\)表示:

\[ Assume\ lost function\ \mathbb{J}\ has\ dim\ d \]

\[\mathbb{J}=[J_1,\ J_2, ... , J_k,\ ...\ ,\ J_d\ ]^T\]

損失梯度(Gradient)要從輸出\(Y\)流回輸入\(X\), 並流到\(W\)和\(B\)以進行權重和偏置的更新(update), 也就是可以把問題定義成:

\[ Given\ \frac{\partial J_k}{\partial y_{j}} , find\ \frac{\partial J_k}{\partial w_{ji}},\ \frac{\partial J_k}{\partial b_j} \, and\ \frac{\partial J_k}{\partial x_i} \]

梯度傳遞會用到微積分的鏈鎖率(Chain Rule), 為了方便起見我們多定義一個\(Z\):

\[ Z = WX+B \]

\[ Y = \sigma (Z) \]

\[Z=[z_1,\ z_2, ... , z_j,\ ...\ ,\ z_m\ ]^T\]

可以發現, 上式和原本的\(Y=\sigma(WX+B)\)並沒有不同, 只是計算過程中間多一個\(Z\)

定義輸出梯度(已知): \[\nabla_{out} = \frac{\partial J_k}{\partial y_{j}}\]

定義輸入梯度(待求): \[\nabla_{in} = \frac{\partial J_k}{\partial x_{i}}\]

用鏈鎖率(Chain Rule)將待求的項目展開:

\[ \frac{\partial J_k}{\partial w_{ji}} = \frac{\partial J_k}{\partial y_{j}} \frac{\partial y_j}{\partial z_j} \frac{\partial z_j}{\partial w_{ji}} = G_{kj}\ \frac{\partial z_j}{\partial w_{ji}} \ \ ...(1)\]

\[ \frac{\partial J_k}{\partial b_{j}} = \frac{\partial J_k}{\partial y_{j}} \frac{\partial y_j}{\partial z_j} \frac{\partial z_j}{\partial b_{j}} = G_{kj}\ \frac{\partial z_j}{\partial b_{j}} \ \ ...(2)\]

\[ \frac{\partial J_k}{\partial x_{i}}\ (\nabla_{in}) = \frac{\partial J_k}{\partial y_{j}} \frac{\partial y_j}{\partial z_j} \frac{\partial z_j}{\partial x_{i}} = G_{kj}\ \frac{\partial z_j}{\partial x_{i}} \ \ ...(3)\]

上列各式重複\(\frac{\partial J_k}{\partial y_{j}} \frac{\partial y_j}{\partial z_j}\)的部分, 方便起見, 定義中介梯度\(\mathbb{G}\):

\[ \mathbb{G}\ = \frac{\partial J_k}{\partial y_{j}} \frac{\partial y_j}{\partial z_j} \]

\[ \mathbb{G}= {\left[ \begin{array}{ccc} G_{11},\ G_{12}, ... ,\ G_{1m}\ \\ ... , G_{kj}, ... \\ G_{k1},\ G_{k2}, ... ,\ G_{dm}\ \\ \end{array}\right ]} =\{ G_{kj}\}_{d \times m}\]

至此, 整個計算流程(計算圖)已經很明朗了, 我們的目的就是找到:

\[ Find\ \ \mathbb{G},\ \frac{\partial z_j}{\partial w_{ji}} ,\ \frac{\partial z_j}{\partial b_{j}} ,\ \frac{\partial z_j}{\partial x_{i}} \]

只要算出上述四項, 就可以得到所求

  1. 計算\(G_{kj}\)

\[ \frac{\partial y_j}{\partial z_j} = \sigma ' (z_j) \]

\[ => G_{kj} = \frac{\partial J_k}{\partial y_{j}}\ \sigma ' (z_j) = (dout)\ \sigma ' (z_j)\]

  1. 計算\(\frac{\partial z_j}{\partial w_{ji}} ,\ \frac{\partial z_j}{\partial b_{j}} ,\ \frac{\partial z_j}{\partial x_{i}}\)

\[ \frac{\partial z_j}{\partial w_{ji}} = x_{i} \]

\[ \frac{\partial z_j}{\partial b_{j}} = 1 \]

\[ \frac{\partial z_j}{\partial x_{i}} = w_{ji} \]

  1. 代入式(1)(2)(3), 得到結果

\[ => \frac{\partial J_k}{\partial w_{ji}} = G_{kj} \ x_i\ ,\\ \ \frac{\partial J_k}{\partial b_{j}} = G_{kj} , \\ \ \frac{\partial J_k}{\partial x_{i}}\ (\nabla_{in}) = G_{kj}\ w_{ji}\ \]


以上就是整個BP演算法"單層"的計算過程, 化成python程式碼如下:

1
2
3
4
5
6
7
def backward(self,dout):  
Z,x = self.cache
G = dout * self.dactive_fn(Z)
din = G.dot(self.W.T)
dW = x.T.dot(G)
db = G.sum(axis=0)
return din,dW,db

程式碼來源: https://github.com/purelyvivid/DeepLearning_practice/blob/master/3.%20BP%20algo.py (用numpy寫一個BP algorithm)

Hui-Yu Huang

Hui-Yu Huang

關於Machine Learning, Deep Learning, Graph Neural Network, Natural Language Processing的那些事

7 文章
4 分類
GitHub E-Mail
© 2019 Hui-Yu Huang
由 Hexo 強力驅動
|
主題 — NexT.Pisces v5.1.4