Classification: Given options(classes), the function outputs the correct one.

Probabilistic Generative Model

features and predict target

• 一共有7个features，其中
• Total = HP + Attack + Deffense + SP Atk + Sp Def + Speed
• predict target: type of pokemon

How to do Classification

• 收集Training data for Classification
• 考虑如果做分类？

Classification as Regression?（分类问题是否可以用回归算法处理？）

以二分类举个例子

• Training: Class 1 means the target is 1; Class 2 means the target is -1
• Testing: $\text{closer to 1}\to \text{class 1};\text{closer to -1}\to \text{class 2}$

这样直接用Regression来解决Classification的问题，会发生如下图的情况：

• 当样本feature如左图所示，则$y=b+w_1{x}_1+w_2{x}_2$的函数可以很好的工作。
• 当样本feature如右图所示，由于右下角的数据，导致Regression的Loss函数在求最小值时，会倾向于给出紫色的线段的方程。即Loss函数会由于“太正确”而导致最终预测结果出错。
• Penalize to the examples that are “too correct” … (Bishop, P186)

Ideal Alternatives(理想的做法)

• Function (Model): $$\delta (x)\Rightarrow \{\begin{array}{ll}g(x)>0& \text{Output = class 1}\\ else& \text{Output = class 2}\end{array}$$
• Loss Function
  • The number of times f get incorrect results on training data. $$L(f)=\sum _n\delta (f(x^n)\ne {\hat{y}}^n)$$
• Find the best function:
  • Example: Perceptron, SVM

Generative Model

• $P(C_1)$是从两个分类中，随机选中Class1的几率，$P(C_2)$是从两个分类中，随机选中Class2的几率。
• 假设x为其中一种颜色的圆圈，则：$P(x|C_1)$表示从Class1中选中x的几率，$P(x|C_2)$表示从Class2中选中x的几率，
• 选中x属于class1的几率就是：$P(C_1|x)=\frac{P(C_1)P(x|C_1)}{P(C_1)P(x|C_1)+P(C_2)P(x|C_2)}$
• 选中x的总几率就是： $P(x)=P(x|C_1)P(C_1)+P(x|C_2)P(C_2)$
• Estimating the Probabilities From training data, 这整个想法就叫做Generative Model

Gaussian Distribution

• $f_{\mu ,\sum }(x)=\frac{1}{(2\pi {)}^{D/2}}\frac{1}{|\sum {|}^{1/2}}exp\{-\frac{1}{2}(x-\mu {)}^T\sum ^{-1}(x-\mu )\}$
• input: vector x, output: probability of sampling x(实际是probability density，概率密度与概率成正比,此处简略为概率)
• The shape of the function determines by mean $\mu$ and covariance matrix $\sum$(协方差矩阵)

Maximum Likelihood（找mean$\mu$和covariance matrix $\mathrm{\Sigma }$的方法）

• mean $\mu$控制原点的位置。
• covariance matrix $\mathrm{\Sigma }$决定图形的形状。
• 虽然图中左下角的点都可以求出相对于两个圈的概率，但是这两个概率的大小是不一样的。
• 给定一个Gaussian的$\mu$和$\mathrm{\Sigma }$,就可以求出对应的Likelihood:
  • $L(\mu ,\mathrm{\Sigma })=f_{\mu ,\mathrm{\Sigma }}(x^1)f_{\mu ,\mathrm{\Sigma }}(x^2)f_{\mu ,\mathrm{\Sigma }}(x^3)\dots \dots f_{\mu ,\mathrm{\Sigma }}(x^n)$
  • 这里的每一个$f_{\mu ,\mathrm{\Sigma }}(x^1)$展开，都是$f_{\mu ,\sum }(x)=\frac{1}{(2\pi {)}^{D/2}}\frac{1}{|\sum {|}^{1/2}}exp\{-\frac{1}{2}(x-\mu {)}^T\sum ^{-1}(x-\mu )\}$
• Maximum Likelihood: ${\mu }^{\ast },{\mathrm{\Sigma }}^{\ast }=arg\underset{\mu ,\mathrm{\Sigma }}{max}L(\mu ,\mathrm{\Sigma })$
  • ${\mu }^{\ast }$为取x的平均值: ${\mu }^{\ast }=\frac{1}{n}\sum _{i=1}^n{x}^i$
  • ${\mathrm{\Sigma }}^{\ast }=\frac{1}{n}\sum _{i=1}^n(x^i-{\mu }^{\ast })(x^i-{\mu }^{\ast }{)}^T$

采用上诉方法得到的测试结果

Modifying Model (Ref: Bishop chapter 4.2.2)

• 给每一个Gaussian有一个自己的$\mu$和自己的covariance matrix $\mathrm{\Sigma }$是很少见的
• 常见的做法是，不同的Class对应的Gaussian可以share相同的covariance matrix $\mathrm{\Sigma }$

模型修改后如何计算$\mu$和$\mathrm{\Sigma }$

• 假设有数量为n的class1,数量为m的class2
• likelihood: $$\begin{array}{rl}L({\mu }^1,{\mu }^2,\mathrm{\Sigma })=& f_{{\mu }^1,\mathrm{\Sigma }}(x^1)f_{{\mu }^1,\mathrm{\Sigma }}(x^2)\dots \dots f_{{\mu }^1,\mathrm{\Sigma }}(x^n)\\ \times & f_{{\mu }^2,\mathrm{\Sigma }}(x^{n+1})f_{{\mu }^2,\mathrm{\Sigma }}(x^{n+2})\dots \dots f_{{\mu }^2,\mathrm{\Sigma }}(x^{n+m})\end{array}$$
• 如下图， ${\mu }^1$, ${\mu }^2$和原来一样计算: $$\begin{array}{rl}{\mu }^1& =\frac{1}{n}\sum _{i=1}^n{x}^i\\ {\mu }^2& =\frac{1}{m}\sum _{i=1}^m{x}^i\end{array}$$
• ${\mathrm{\Sigma }}^{\ast }$的计算修改为：$\mathrm{\Sigma }=\frac{n}{n+m}{\mathrm{\Sigma }}^1+\frac{m}{n+m}{\mathrm{\Sigma }}^2$

模型修改后画出的图形

• 从原来的曲线，变成了一条直线
• 由于边界(boundary)是一条直线，所以这种模型也叫做Linear Model。
• 在这个模型下，考虑所有的7个features进行计算，则accuracy从原来的54%上升到73%

总结一下3个步骤

• Function Set(Model): $$\begin{array}{rl}P(C_1|x)& =\frac{P(C_1)P(x|C_1)}{P(C_1)P(x|C_1)+P(C_2)P(x|C_2)}\\ & \{\begin{array}{ll}\text{if}P(C_1|x)>0.5& \text{, output: class 1}\\ Otherwise& \text{, output: class 2}\end{array}\end{array}$$
• Goodness of a function:
  • The mean $\mu$ and covariance $\mathrm{\Sigma }$ that maximizing the likelihood(the probability of generating data)
• Find the best function: easy

Probability Distribution

• You can always use the distribution you like
• 假设$P(x|C^1)$构成Class1的x有K个，且K个x想对于Class1的几率是独立的，则：$P(x|C1)=P(x_1|C_1)P(x_2|C_1)\cdots P(x_K|C_1)$，这个会得到1-D Gaussian,参数会进一步简化
• For binary features, you may assume they are from Bernouli distributions.
• If you assume all the dimensions are independent, then you are using Naive Bayes Classifier.

Posterior Probability

• 设有表达式(1)上下同时除上表达式$P(C_1)P(x|C_1)$得到表达式(2)
• 设$z=ln\frac{P(C_1)P(x|C_1)}{P(C_2)P(x|C_2)}$,则表达式(2)变为表达式(3)
• 表达式(3)和(4)等价，为Sigmoid Function $$\begin{array}{}\text{(1)}& P(C_1|x)& =\frac{P(C_1)P(x|C_1)}{P(C_1)P(x|C_1)+P(C_2)P(x|C_2)}\text{(2)}& & =\frac{1}{1+\frac{P(C_2)P(x|C_2)}{P(C_1)P(x|C_1)}}\text{(3)}& & =\frac{1}{1+ex{p}^{-z}}\text{(4)}& & =\sigma (z)\end{array}$$

求z

• 设$N_1$是Class1出现的次数，$N_2$是Class2出现的次数
• 表达式(3)和(4)为Gaussian的Distribution
• 表达式(5)上下同时除以$\frac{1}{(2\pi {)}^{D/2}}$得到表达式(6) $$\begin{array}{rl}z& =ln\frac{P(C_1)P(x|C_1)}{P(C_2)P(x|C_2)}\\ \text{(1)}& & =ln\frac{P(C_1)}{P(C_2)}+ln\frac{P(x|C_1)}{P(x|C_2)}\text{(2)}& ln\frac{P(C_1)}{P(C_2)}& =\frac{\frac{N_1}{N_1+N_2}}{\frac{N_2}{N_1+N_2}}=\frac{N_1}{N_2}\text{(3)}& P(x|C_1)& =\frac{1}{(2\pi {)}^{D/2}}\frac{1}{|{\mathrm{\Sigma }}^1{|}^{1/2}}exp\{-\frac{1}{2}(x-{\mu }^1{)}^T({\mathrm{\Sigma }}^1{)}^{-1}(x-{\mu }^1)\}\text{(4)}& P(x|C_2)& =\frac{1}{(2\pi {)}^{D/2}}\frac{1}{|{\mathrm{\Sigma }}^2{|}^{1/2}}exp\{-\frac{1}{2}(x-{\mu }^2{)}^T({\mathrm{\Sigma }}^2{)}^{-1}(x-{\mu }^2)\}\text{(5)}& ln\frac{P(x|C_1)}{P(x|C_2)}& =ln\frac{\frac{1}{(2\pi {)}^{D/2}}\frac{1}{|{\mathrm{\Sigma }}^1{|}^{1/2}}exp\{-\frac{1}{2}(x-{\mu }^1{)}^T({\mathrm{\Sigma }}^1{)}^{-1}(x-{\mu }^1)\}}{\frac{1}{(2\pi {)}^{D/2}}\frac{1}{|{\mathrm{\Sigma }}^2{|}^{1/2}}exp\{-\frac{1}{2}(x-{\mu }^2{)}^T({\mathrm{\Sigma }}^2{)}^{-1}(x-{\mu }^2)\}}\text{(6)}& & =ln\frac{\frac{1}{|{\mathrm{\Sigma }}^1{|}^{1/2}}exp\{-\frac{1}{2}(x-{\mu }^1{)}^T({\mathrm{\Sigma }}^1{)}^{-1}(x-{\mu }^1)\}}{\frac{1}{|{\mathrm{\Sigma }}^2{|}^{1/2}}exp\{-\frac{1}{2}(x-{\mu }^2{)}^T({\mathrm{\Sigma }}^2{)}^{-1}(x-{\mu }^2)\}}\text{(7)}& & =ln\frac{|{\mathrm{\Sigma }}^2{|}^{1/2}}{|{\mathrm{\Sigma }}^1{|}^{1/2}}exp\{-\frac{1}{2}[(x-{\mu }^1{)}^T({\mathrm{\Sigma }}^1{)}^{-1}(x-{\mu }^1)-(x-{\mu }^2{)}^T({\mathrm{\Sigma }}^2{)}^{-1}(x-{\mu }^2)]\}\text{(8)}& & =ln\frac{|{\mathrm{\Sigma }}^2{|}^{1/2}}{|{\mathrm{\Sigma }}^1{|}^{1/2}}-\frac{1}{2}[(x-{\mu }^1{)}^T({\mathrm{\Sigma }}^1{)}^{-1}(x-{\mu }^1)-(x-{\mu }^2{)}^T({\mathrm{\Sigma }}^2{)}^{-1}(x-{\mu }^2)](x-{\mu }^1{)}^T({\mathrm{\Sigma }}^1{)}^{-1}(x-{\mu }^1)& =x^T({\mathrm{\Sigma }}^1{)}^{-1}x-x^T({\mathrm{\Sigma }}^1{)}^{-1}{\mu }^1-({\mu }^1{)}^T({\mathrm{\Sigma }}^1{)}^{-1}x+({\mu }^1{)}^T({\mathrm{\Sigma }}^1{)}^{-1}{\mu }^1\\ & =x^T({\mathrm{\Sigma }}^1{)}^{-1}x-2({\mu }^1{)}^T({\mathrm{\Sigma }}^1{)}^{-1}x+({\mu }^1{)}^T({\mathrm{\Sigma }}^1{)}^{-1}{\mu }^1\\ (x-{\mu }^2{)}^T({\mathrm{\Sigma }}^2{)}^{-1}(x-{\mu }^2)& =x^T({\mathrm{\Sigma }}^2{)}^{-1}x-2({\mu }^2{)}^T({\mathrm{\Sigma }}^2{)}^{-1}x+({\mu }^2{)}^T({\mathrm{\Sigma }}^2{)}^{-1}{\mu }^2\\ z& =ln\frac{|{\mathrm{\Sigma }}^2{|}^{1/2}}{|{\mathrm{\Sigma }}^1{|}^{1/2}}-\frac{1}{2}{x}^T({\mathrm{\Sigma }}^1{)}^{-1}x+({\mu }^1{)}^T({\mathrm{\Sigma }}^1{)}^{-1}x-\frac{1}{2}({\mu }^1{)}^T({\mathrm{\Sigma }}^1{)}^{-1}{\mu }^1\\ & +\frac{1}{2}{x}^T({\mathrm{\Sigma }}^2{)}^{-1}x-({\mu }^2{)}^T({\mathrm{\Sigma }}^2{)}^{-1}x+\frac{1}{2}({\mu }^2{)}^T({\mathrm{\Sigma }}^2{)}^{-1}{\mu }^2+ln\frac{N_1}{N_2}\end{array}$$

求 $\sigma (z)$

• 当${\mathrm{\Sigma }}_1={\mathrm{\Sigma }}_2=\mathrm{\Sigma }$时，表达式(1)变为表达式(2)
• 设: $w^T=({\mu }_1-{\mu }_2{)}^T{\mathrm{\Sigma }}^{-1}$以及$b=-\frac{1}{2}({\mu }^1{)}^T({\mathrm{\Sigma }}^1)-1{\mu }^1+\frac{1}{2}({\mu }^2{)}^T({\mathrm{\Sigma }}^2)-1{\mu }^2+ln\frac{N_1}{N_2}$则(2)可以推导为(3)
• In generative model, we estimate $N_1,N_2,{\mu }^1,{\mu }^2,\mathrm{\Sigma }$, then we have w and b. $$\begin{array}{rl}z& =ln\frac{|{\mathrm{\Sigma }}^2{|}^{1/2}}{|{\mathrm{\Sigma }}^1{|}^{1/2}}-\frac{1}{2}{x}^T({\mathrm{\Sigma }}^1{)}^{-1}x+({\mu }^1{)}^T({\mathrm{\Sigma }}^1{)}^{-1}x-\frac{1}{2}({\mu }^1{)}^T({\mathrm{\Sigma }}^1{)}^{-1}{\mu }^1\\ \text{(1)}& & +\frac{1}{2}{x}^T({\mathrm{\Sigma }}^2{)}^{-1}x-({\mu }^2{)}^T({\mathrm{\Sigma }}^2{)}^{-1}x+\frac{1}{2}({\mu }^2{)}^T({\mathrm{\Sigma }}^2{)}^{-1}{\mu }^2+ln\frac{N_1}{N_2}\text{(2)}& & =({\mu }_1-{\mu }_2{)}^T{\mathrm{\Sigma }}^{-1}x-\frac{1}{2}({\mu }^1{)}^T({\mathrm{\Sigma }}^1)-1{\mu }^1+\frac{1}{2}({\mu }^2{)}^T({\mathrm{\Sigma }}^2)-1{\mu }^2+ln\frac{N_1}{N_2}\text{(3)}& & =w\cdot x+bP(C_1|x)& =\sigma (z)\\ & =\sigma (w\cdot x+b)\end{array}$$

reference video