https://aman.ai/cs229/gda/
https://kuleshov-group.github.io/aml-book/contents/lecture7-gaussian-discriminant-analysis.html
Modeling
GDA 是一种 probabilistic generative model, 它 model:
-
每个 p(Ck) 为 constant. 比如 in case k=2, 使用 y∼Bernulli(ϕ), 即 P(C1)=ϕ, P(C2)=1−ϕ
write in a compact way:
$p(y)=ϕy(1−ϕ)1−y(因为y只取0,1,所以这里可以得到P(C_1)= \phi,P(C_2) = 1-\phi$)
这个形式的优点是便于优化
-
对于每个 Ck, 把 p(x∣Ck) model 为一个 Gaussian distribution
$p(x∣Ck)=(2π)D/21∣Σ∣1/21exp{−21(x−μk)⊤Σ−1(x−μk)}\mathbf\Sigma表示covariancematrixoftheM$ features.
以 dim=2 为例:

recall: **cov matrix 必须是 p.s.d. 并且对称的. **
参数量
Note: For our GDA, 我们假设所有 classes 的 covariance 都一样, 即所有 classes 共享 Σ.
从而这里参数:一个是 ϕ, 一个是 μ1,⋯,μk, 一个是 Σ. 从而参数量是:
$k+kM+M(M+1)/2$
Note: Sharing Σ⟹ linear decision boundary

给定参数, 预测
从而, 固定学习到的参数, 我们对 input data x 属于的类别作出的预测是: (by Bayes' theorem)
$p(C1∣x)=p(x∣C1)p(C1)+p(x∣C2)p(C2)p(x∣C1)p(C1)$
我们可以把它转化成 sigmoid 的形式:
Define log-odd:
$a:=logp(C2∣x)p(C1∣x)=logp(x∣C2)p(C2)p(x∣C1)p(C1)那么p\left(C_1 \mid \mathbf{x}\right)可转化为:p(C1∣x)=1+exp(−a)1=σ(a)$
log-odds 的推导
=logexp{−21(x−μ2)⊤Σ−1(x−μ2)}exp{−21(x−μ1)⊤Σ−1(x−μ1)}+logP(C2)P(C1)={−21(x−μ1)⊤Σ−1(x−μ1)}−{−21(x−μ2)⊤Σ−1(x−μ2)}+logP(C2)P(C1)=(μ1−μ2)⊤Σ−1x−21μ1⊤Σ−1μ1+21μ2⊤Σ−1μ2+logP(C2)P(C1)=(Σ−1(μ1−μ2))⊤x+b where b=−21μ1⊤Σ−1μ1+21μ2⊤Σ−1μ2+logp(C2)p(C1)因而: 当 GDA 作为一个判别模型 时,我们可以得到决策边界:
$p(C1∣x)=1+e−wTx−b1$
这恰好是 逻辑回归(Logistic Regression)的形式,其中:
w=Σ−1(μ1−μ0)
b=−21(μ1TΣ−1μ1−μ0TΣ−1μ0)+log1−ϕϕ
可以 generalizes to normalized exponential (softmax) :
$pi=∑jexp(qj)exp(qi)$
Learning: maximize Log likelihood
P(x,C1)P(x,C2)=P(x∣C1)P(C1)=(2π)D/21∣Σ∣1/21exp{−21(x−μ1)⊤Σ−1(x−μ1)}ϕ=P(x∣C2)P(C2)=(2π)D/21∣Σ∣1/21exp{−21(x−μ2)⊤Σ−1(x−μ2)}(1−ϕ)因而给定训练数据 {(xi,yi)}i=1m ,我们可以写出 likelihood 函数:
$L(ϕ,μ0,μ1,Σ)=∏i=1NP(x(i),y(i);ϕ,μ0,μ1,Σ)$
通过最大化这个似然函数,可以学习到最优的 μk, Σ, 以及 π=P(y=1).
ℓ(ϕ,μ0,μ1,Σ)=logL=logi=1∏Np(x(i)∣y(i);ϕ,μ0,μ1,Σ)p(y(i);ϕ)=i=1∑Nlogp(x(i)∣y(i);ϕ,μ0,μ1,Σ)+i=1∑Nlogp(y(i);ϕ)=i=1∑N[log(2π)2M∣Σ∣211−21(x(i)−μy(i))⊤Σ−1(x(i)−μy(i))+logϕy(i)+log(1−ϕ)(1−y(i))]≃i=1∑N[−21log∣Σ∣−21(x(i)−μy(i))⊤Σ−1(x(i)−μy(i))+y(i)logϕ+(1−y(i))log(1−ϕ)](the constant term is independent of the parameters, thus removed.)
通过最大化这个函数,我们可以求得参数的 MLE 估计:
$ϕ^=m1i=1∑myiμ^0=∑i=1m1(yi=0)∑i:yi=0xiμ^1=∑i=1m1(yi=1)∑i:yi=1xiΣ^=m1i=1∑m(xi−μyi)(xi−μyi)T$
MLE 推导 (hw 2(3))
ϕ^
∂ϕ∂ℓ=i=1∑N(ϕy(i)−1−ϕ1−y(i))=i=1∑Nϕ1(y(i)=1)+1−ϕN−∑i=1NI(y(i)=1)Therefore, ϕML=N1∑i=1N1(y(i)=1), i.e**. the fraction of the training examples such that y(i)=1.**
μ^k
∇μ0ℓ=−21i:y(i)=0∑∇μ0(x(i)−μ0)⊤Σ−1(x(i)−μ0)=−21i:y(i)=0∑∇μ0[−2μ0⊤Σ−1x(i)+μ0⊤Σ−1μ0]=−21i:y(i)=0∑[−2Σ−1x(i)+2Σ−1μ0]By setting the gradient to zero,
i:y(i)=0∑[Σ−1x(i)−Σ−1μ0]i=1∑NI{y(i)=0}Σ−1x(i)−i=1∑NI{y(i)=0}Σ−1μ0=0=0Thus we obtain μ0ML=∑i=1NI{y(i)=0}∑i=1NI{y(i)=0}x(i), i.e., the mean of the training examples with y(i)=0
Σ^
对于 M=1 case,
When everything is a scalar, the log-likelihood of the data can be re-written as
ℓ(ϕ,μ0,μ1,Σ)≃i=1∑N[−21log∣Σ∣−21(x(i)−μy(i))⊤Σ−1(x(i)−μy(i))+y(i)logϕ+(1−y(i))log(1−ϕ)]=i=1∑N[−logσ−2σ21(x(i)−μy(i))2+y(i)logϕ+(1−y(i))log(1−ϕ)]By taking derivative with respect to σ and set it to zero:
∇σℓ=i=1∑N[−σ1+σ31(x(i)−μy(i))2]=0Obtain: σML=N1∑i=1N(x(i)−μy(i))2.
对于 general case,
$ℓ(ϕ,μ0,μ1,Σ)≃∑i=1N[−21log∣Σ∣−21(x(i)−μy(i))⊤Σ−1(x(i)−μy(i))+y(i)logϕ+(1−y(i))log(1−ϕ)]$
为了计算 gradient 我们需要用到 matrix gradient properties:
$∇Xlog∣X∣=X−1以及∇X(a⊤X−1a)=−X−1aa⊤X−1$
Using the hints and taking gradient w.r.t Σ and setting it to zero, we get
∇Σ=i=1∑N[−21Σ−1+21Σ−1(x(i)−μy(i))(x(i)−μy(i))⊤Σ−1]=0using which we obtain ΣML=N1∑i=1N(x(i)−μy(i))(x(i)−μy(i))⊤
如果不假设 sharing Σ^: Decision boundaries between some classes can be quadratic when they have different covariances.

Comparison between GDA and Logistic regression (or softmax regression)
- Logistic regression has less parameters and is more flexible about data distribution.
- GDA has a stronger modeling assumption and works well when the distribution follows the assumption.