概率分类与Logistic回归

分类定义

找一个function，输入对象x的特征，输出该对象是属于n个类别中的哪一个。

生成模型

盒子抽球问题

两个盒子，每个盒子中各有XX的概率抽出红球或者蓝球，问抽出一个球，抽到x号盒子中蓝色球的概率。

需要的已知信息

将一个盒子映射成一个类别，抽一个球是某个盒子中的球的概率分别是 ；对于一个盒子，抽出球的概率分别是。

利用已知信息推测回答

对于给定的一个，就可以计算出它属于每一个盒子的概率是多少

$$P(C_i|x)=\frac{P(x|C_i)*P(C_i)}{\sum{P(x|C_i)*P(C_i)}}(贝叶斯公式)=\frac{P(x|C_i)*P(C_i)}{P(x)(全概率公式)}$$

依据哪个盒子的概率大，我们就判断这个球属于哪个盒子。

如何获得等式右边的各种数据？我们需要从训练集中估测需要的已知信息。这个想法叫做生成模型(Generative Model)。

贝叶斯公式

先验概率

先验概率是通过我们的训练集，也就是已知分类的对象来获取的。

对于某个特定分类的对象的数据，可以把它当作某个随机变量的抽样。如果我们有了这个随机变量的分布函数或概率密度函数，就可以推测其他我们未知取值的概率。

每一个真实世界中的待分类或者已分类的对象需要在数学上被抽象成一个vector，该vector的每个分量都是这个对象的attribute，我们称之为feature。

定义损失函数

如何确定这个训练集数据的分布函数或概率密度函数呢？

首先要确定这个分布的形式。是高斯分布、伯努利分布或者其他，这需要自己选择。例如对于二元分类来说，可以假设是符合Bernoulli distribution。

其次将分布函数/概率密度函数看作一个function，输入的就是向量，输出是选中的概率。如果选高斯分布，那就是求期望和协方差矩阵，分别决定了最高点和离散度。

根据已有sample求解概率密度函数的estimate，采用最大似然估计Maximum Likelihood。任意的期望和协方差都能构成高斯分布，都可以生成我们训练集中的数据，但是问题是对我们已有数据的命中率的高低。

寻找最好的函数/求参数

如何衡量一个确定estimate为的高斯函数对我们已有数据的命中率？引入样本的似然函数的概念。

对于高斯分布的样本，我们假设高斯分布的期望为，协方差矩阵为，用这些样本的概率值——也就是样本作为输入传入高斯函数后的输出——的乘积，作为样本的似然函数。

$$L(\mu,\sum) = f_{\mu,\sum}(x_1)*f_{\mu,\sum}(x_2)*f_{\mu,\sum}(x_1) * \dots * f_{\mu,\sum}(x_n)$$

能让最大的就是所有的最大似然估计。

用数学来求解就是对两个estimate分别求偏微分为0的点。直观的来看，期望就是样本平均，协方差就是样本方差。

抽球模型和分类问题的联系

回到盒子抽球问题中的贝叶斯公式，等式中的就是通过概率密度函数求得的。

我们需要定义计算出来的在什么样的情况下我们会把对象归为。可能概率大于某一个数值？

为什么令每个类别的高斯分布的协方差矩阵相同后，高斯分布获得的最大似然函数是线性的？

$$\begin{split} P(C_1|x) &= \frac{1}{1+\frac{P(x|C_2)P(C_2)}{P(x|C_1)P(C_1)}}\\&=\frac{1}{1+exp(-z)} \\&= \sigma(z)[Sigmoid \, function] \\ \end{split} \\ z = ln\frac{P(x|C_1)P(C_1)}{P(x|C_2)P(C_2)}$$

拆分，用概率密度函数替换掉表达式的中的，展开项合并，并对表达式进行关于的整理，可以得到一个一次函数。

详细推导见GoodNotes。

$$P_{\omega, b}(C_1|x) = \sigma(z) [Sigmoid Function]\\ z = \omega x + b$$

之前学的多变量分析中的判别分析，为了降低输入数据的维度，将数据投影到了组间直线的分界线上discriminant score。输入为，输出经过一个一次方程式。

整理出来得到的是一个一次函数，回顾之前的推导过程，我们需要estimate很多参数包括，并且我们做了假设样本数据服从于某个分布。

步骤优化

• 描述类别的高斯分布的协方差矩阵强制相同。此时分类的边界线，也就是最大似然函数（？）是线性的，所以也叫linear model。

  理由有二。

  第一，因为协方差矩阵和输入feature的大小的平方成正比，因此feature较大时，协方差矩阵增长会过快。

  第二，因为模型参数过多容易过拟合，应当有效减少参数。

• 如果数据的feature是一个vector，每一个维度的概率分布相互独立，可以将多维的高斯分布通过每一维度的概率密度函数相乘，转化成一维高斯分布(Naive Bayes Classifier朴素贝叶斯分类器)。

从获得的结果来看，最终只与有关，是否可以尝试直接求解这两个参数？由此引入Logistic Regression。

Logistic Regression

逻辑回归的函数集

定义Logistic Regression的函数集为$f{\omega,b}(x) = P{\omega,b}(C_1,x)=\sigma (z)\omega,b$都能让我们的训练数据集的input通过此函数获得一个output，即在该input下，分类正确的几率作为output。

对于用于训练的数据集通过某个function，可以获得input，output。要将所有的数据都转换成实际的数据，用分类结果肯定不行。对于二元分类问题直接映射分类结果到0和1；对于多元分类问题该怎么办？后面解决。

定义损失函数

如何从function set中选出令衡量效果最好的那一个function？直观来说就是能够正确分类，输出概率最大的那个function是最好的。确定最优化函数function也就是查找一个特定的$\omega^,b^$。

$$L(\omega, b) = f_{\omega,b}(x_1) f_{\omega,b}(x_2) (1-f_{\omega,b}(x_3)) \dots f_{\omega,b}(x_n) \\$$ $$\omega^*, b^* = {arg \, \max\limits_{\omega^*,b^*}} \, {L(\omega, b)} \iff {arg \, \min\limits_{\omega^*,b^*}} \,{ -\ln{L(\omega, b)}}$$

注意到有两种形式的分式在相乘，不可能展开求解，需要改写函数集来同时能够匹配分类正确/属于Class0和分类错误/属于Class1两种情况。

$$\begin{split} -\ln{L(\omega, b)} &= -\ln{f_{\omega,b}(x_1)}\ln{f_{\omega,b}(x_2)} \ln{(1-f_{\omega,b}{(x_3)})} \dots \\ &= \sum_\limits{n} -[\hat{y}^n \ln{f_{\omega,b}(x_n)} + (1-\hat{y}^n) \ln{(1-f_{\omega,b}(x_n))}] \, \\ \end{split}$$

上式可以看作两个0-1分布的交叉熵。

求导结果

MLE && Cross-Entrpy Explanation

什么是Cross Entropy？为什么作为衡量goodness of function的标准？

Reference

熵的定义

熵用于衡量随机变量的不确定性。

Entropy is a measure of the uncertainty of a random variable. If we have a random variable X, and we have probability mass function p(x) = Pr[X=x], we define the Entropy H(X) of the random variable X with

$$H(X) = -\sum\limits_{x}{p(x)\log{p(x)}}$$

由于形式和随机变量的数学期望十分相像，所以将它改写为

$$\begin{split} H(X) &= -\sum\limits_{x}{p(x)\log{p(x)}} \\ &= \sum\limits_{x}{p(x)\log{\frac{1}{p(x)}}}\\ &= \mathbb{E}_{X \sim p(x)}[\log{\frac{1}{p(x)}}] \end{split}$$

So the entropy of a random variable is the expected value of the random variable log(1/p(x)) where X is drawn from p(x).

---

交叉熵

假设对于我们的数据集，有两个分布，一个是unkown but true的distribution，一个是modeled approximate的distribution。为了衡量这两个分布之间的差异性，我们引入the Kullback–Leibler divergence (also called relative entropy)的概念。如果两个分布一摸一样的话，交叉熵就是熵。

$$\begin{split} D_{KL}(p||q) &= \sum\limits_{x}{p(x)\log{\frac{q(x)}{p(x)}}} \\&= \mathbb{E}_{X \sim p(x)}[\log{\frac{q(x)}{p(x)}}] \\ &= \mathbb{E}_{X \sim p(x)}[\log{\frac{1}{p(x)}}] - \mathbb{E}_{X \sim p(x)}[\log{\frac{1}{p(x)}}] \end{split}$$

第一项是Cross-Entropy，第二项是分布p(x)的熵。

将Cross-Entropy为，用真实分布的熵和Relative-Entropy表示Cross-Entropy，为。

---

Cross-Entropy && MLE Relationship

如何将Cross Entropy和Maximum Likelihood Estimation联系起来？需要理解的是，极大似然估计是用来估计一个概率模型的参数的一种方法。

Suppose that for a problem, we have a set of examples X_example = {x_1, x_2, …, x_m} that drawn independently from a true but unknown distribution p_data(x).

Then we try to model the true distribution by parametric model p_model(x;𝜃) with 𝜃 as the parameter.

We can say that p_model(x,𝜃) maps x to estimate the true but unknown p_data(x) given the same data.

To get the best model, we need to find such 𝜃 that yields the most similar outcome of p_model(x,𝜃) to p_data(x). We can use MLE principle to find such 𝜃, that is by using maximum likelihood estimator for 𝜃.

---

Simlification1. i.i.d.

$$\begin{split} \theta_{ML} &= arg\max \limits_{\theta} p_{model}(X_{example};\theta) \\ & \stackrel{i.i.d}{\longrightarrow} arg\max \limits_{\theta}\prod_{i=1}^{m}p_{model}(x_{i};\theta) \end{split}$$

---

Simplification2. prodction to summation

算数下溢the underflow problem

The product of p_model(x_i;𝜃) is going to be very close to 0 when the example set size m is large since the probability will be in the range of 0≤p_model(x_i;𝜃)≤1. This could cause a serious underflow to the computer, resulting in a less precise estimation of the model.

数据量很大的时候会导致每一个数据的出现概率很小，乘积就会无限趋近于零，在计算机中处理浮点数会带来很大的误差。一个解决办法就是取对数，将相成转换为相加。

改写式子，并scale一个，让他变成数学期望的形式。

$$\begin{split} \theta_{ML} &= arg\max \limits_{\theta}\sum_{i=1}^{m}p_{model}(x_{i};\theta) \\&= arg\max \limits_{\theta} {\frac{1}{m} \cdot \sum_{i=1}^{m}\log {p_{model}(x_{i};\theta) }} \\ &= arg\max \limits_{\theta} \mathbb{E}_{X\sim p_{example(x)}}{[\log{p_{model}(x; \theta)}]} \end{split}$$

最后的形式和Cross-Entropy一样。

---

过程总结

This shows that we can see the problem of getting the best parameter 𝜃_ML using maximum likelihood estimation as minimizing the cross-entropy between our parametric model p_model(x;𝜃) and the empirical example distribution p_example(x).

Train our model by minimizing the cross-entropy loss since it can lead us to the maximum likelihood estimator of the parameter 𝜃_ML that yields the best model according to the training example.

---

寻找最好的函数

用梯度下降法求解。对进行微分，运用链式法则在两个偏微分上下分别引入偏微分，获得结果

$$\frac{\partial{(-\ln{L(\omega, b)} )}}{\partial{w}} = \sum_{n} -(\hat{y}^n-f_{w,b}(x_n))x_i^n$$ $$w_i \leftarrow w_i - \eta \sum_{n} -(\hat{y}^n-f_{w,b}(x_n))x_i^n$$

如何理解括号中的相减的两个式子？代表着Larger Difference, Larger Update。

逻辑回归与线性回归的区别

从两方面考虑。

第一，实际数据的输出target。对于逻辑回归，限定在0～1之间。对于线性回归，可以是任何实数。

第二，定义的损失函数的输出output。对于逻辑回归，由于Sigmoid Function的性质，限定在0～1之间。对于线性回归，可以是任何值。

为什么不像线性函数中一样使用Square Error代表Loss Function？

从两方面解释。

一方面，output of loss function无论是close to target还是far from target，loss function梯度下降后的偏微分都可以是零。

另一方面，交叉熵距离target越远，微分值越大，更新参数越大。但是平方误差在离target很远的时候，微分值特别小，更新参数会特别慢，效果很差。

Discriminative Model V.S. Generative Model

用逻辑回归和生成模型找出来的是不一样的。因为两个模型所做的assumpition都不同，逻辑回归并没有做任何假设；但是生成模型预先假设了样本符合某个分布，给予了更多的信息。

生成方法的优势在于训练数据集很小的情况下，结果受数据量的影响很小，基于分布假设，对噪声数据有更好的鲁棒性。

判别方法的优势在于看训练数据集计算，训练数据量越大，error越小。

多类别分类 n-class

$$input \stackrel{\omega_i ,b_i}{\longrightarrow} z_i \stackrel{exponential}{\longrightarrow} e^{z_i} \stackrel{normalize}{\longrightarrow} output=\frac{e^{z_i}}{\sum_{j=1}^{n}{e^{z_i}}}$$

exponential和normalize的过程都可以被一个叫softmax的方程来完成，这个步骤的工作就是对最大值进行强化。

target该如何定义？如果用连续的0-1-2-3-4存在类别之间有距离大小的问题，而每个类别应当同等看待地位相同。用一个列向量来表示target。

逻辑回归的限制

逻辑回归就是区分类别，如果raw data并不能让逻辑回归做区别的？比如在平面上，一个正方形的四个顶点，对角同类别，无论怎么拉线都不能分类。这种时候该怎么办？

利用特征转换Feature Transfomation。但是如何衡量一个特征转换的优劣又是需要考虑的。

逻辑回归可以用来做特征转换，也可以用来做分类。把这些逻辑回归级联在一起就得到级联逻辑回归模型。

一个逻辑回归的输入可以来源于其他逻辑回归的输出，这个逻辑回归的输出也可以是其他逻辑回归的输入。把每个逻辑回归称为一个 Neuron（神经元），把这些神经元连接起来的网络，就叫做 Neural Network（神经网络）。