一些重要的分类器

我今天被AIG公司的人做面试了。我希望做 Risk Analyst 的工作,因为我想自动化最优决策。我觉得我要复习以下我的知识关于分类器。请看看说,我没有错吗?

贝叶斯分类器

那么,我们先想起来吧这个定理吧。

定理(贝叶斯) 如果$A, B$是两个随机事件(把$A$叫它假设吧),那么如果我们知道概率$P(A), P(B)$的比例$\frac{P(A)}{P(B)}$和条件概率$P(B|A)$这三个概率,并如果随机事件$B$已经发生了,我们可以计算假设$A$的概率$P(A|B)$。

$$P(A|B) = P(B|A) \frac{P(A)}{P(B)}.$$

这个定理的证明依靠条件概率的定义:$P(X|Y) \overset{def}{=} \frac{P(X \cap Y)}{P(Y)}$。代入这个定义到贝叶斯定理的表示,求出:$$\frac{P(A \cap B)}{P(B)} = \frac{P(A \cap B)}{\color{red}{P(A)}} \frac{\color{red}{P(A)}}{P(B)}.$$

从这里 取消 $\color{red}{P(A)}$ 之后就得到等式的证明。

换句话说,如果我们 如果随机事件 $A$ 已经发生了,并我们知道条件概率 $P(A|H)$和$P(H)$和$P(A)$,我们可以计算 假设的概率 $P(H|A)$,并它等于 $\frac{P(A|H) P(H)}{P(A)}$。

虽然贝叶斯定理是关于随机事件的定理,但是它是应用概率测读 $P$ 被下定义的东西,所有跟着概率测读的特征,若 $P(B) \neq 0$,则 $P(A|B)$ 也是个概率测读。“概率测读”意味着它对每个可能的概率空间的元素(随机事件)相对应概率,这些概率的和相等于$1$,并它有可数可加性特性。所以,测读 $P(\cdot)$ 下定义一个概率分布。那么,分类的规则非常简单,如果我们有,比如两个可能的分类 $C_1, C_2$,并我们知道$X$ 已经发生的事件,我们计算 $P(C_1 | X) = \frac{P(X|C_1) P(C_1)}{\color{green}{P(X)}}$ 和 $P(C_2 | X) = \frac{P(X|C_2) P(C_2)}{\color{green}{P(X)}}$,评价分类为相对最大条件概率的分类。因 绿色$\color{green}{P(X)}$ 不改变,我们不要知道它。只要知道 $P(X|C_1), P(C_1), P(X|C_2), P_(C_2)$。实际上,$\color{blue}{P}(C_1)$ 和 $\color{blue}{P}(C_2)$ 是被同一个分布被下定义的值,比如,如果有只两个可能的分类 $C_1$ 和 $C_2$,这个$\color{blue}{P}$分布是伯努利分布,对吧?

解释:如果我们表示$P(C_1)$为$x_1$,$P(C_2)$为$x_2$,然后$P(X|C_1)$为$p_1$,$P(X|C_2)$为$p_2$,可以重写:
$$P(C_1 | X) \sim x_1 p_1 = \mathbb{E}[\xi_1],$$
$$P(C_2 | X) \sim x_2 p_2 = \mathbb{E}[\xi_2].$$

这里$\xi_1$服从 $P(X|C_1)$,$\xi_2$服从 $P(X|C_1)$ 条件分布。(正确吗?)

朴素贝叶斯分类器

如果上面描写的变量$X$表示一个独立的分量的随机向量$\mathbf{X}=(x_1,x_2,\cdots,x_n)$(发生的/看到的特征向量),我们可以重写$P(\mathbf{X}|C_1)=P(x_1|C_1) P(x_2|C_1) \cdots P(x_n|C_1)$,并
$$P(C_1 | X) \sim P(x_1|C_1) P(x_2|C_1) \cdots P(x_n|C_1) \cdot P(C_1),$$
$$P(C_2 | X) \sim P(x_1|C_2) P(x_2|C_2) \cdots P(x_n|C_2) \cdot P(C_2) .$$

当然,决定的规则当然是一样 $\underset{C_i}{\mathrm{argmax}} \ P(C_i | X)$ -- 有最大的条件概率的估计的分类。这里当然每个$P(x_n|C_k)$ 是一个分布,但是,这些分布是独立的分布。
$$P(x_1|C_i) P(x_2|C_i) \cdots P(x_n|C_i) \cdot P(C_i) = P(C_i) \prod_{j=1}^{n} P(x_j | C_i)$$

在英语$P(C_i)$的分布被称为“class priors“,然后$\prod_{j=1}^{n} P(x_j | C_i)$ 的分布被称为“feature probability distributions“。其实,因为这个分布是多个分布的积。那,我觉得我们可以把每个随机变量$x_j$(比如,用次数和卡方检验找到它的一维分布的最优的概率分布和它的参数的数值的估计)然后把这些分布的积得到多维分布,用它为了分类数据。(对吧?)

在这里我想写一些代码为了给一个例子怎么用它。在网上我找到了在这里一个好例子:

install.packages("e1071")
library(e1071)
classifier<-naiveBayes(iris[,1:4], iris[,5]) 
table(predict(classifier, iris[,-5]), iris[,5], dnn=list('predicted','actual'))
classifier$apriori
classifier$tables$Petal.Length
plot(function(x) dnorm(x, 1.462, 0.1736640), 0, 8, col="red", main="Petal length distribution for the 3 different species")
curve(dnorm(x, 4.260, 0.4699110), add=TRUE, col="blue")
curve(dnorm(x, 5.552, 0.5518947 ), add=TRUE, col = "green")

但是,我想自己做概率分布参数的数值的估计。可能最简单的方法是只计算每个条件分布的$\mathrm{E}[X]$和$\mathrm{Var}[X]$,但是我想起MLE(最大似然估计)。我看一点点在维基百科的这个网页,就想起来了。其实,最大似然估计求出的方法很简单。只要做个假定“我们能把多维分布,重写它为独立的分布的积“:
$$f(x_1,x_2,\ldots,x_n\;|\;\theta) = f(x_1|\theta)\times f(x_2|\theta) \times \cdots \times f(x_n|\theta)$$
这样做之后,如果我们已经知道的分布模型我们可以最优化它的参数用一下的方法为了合适数据$x_1, x_2, \cdots, x_n$。为了找到最合适的$\theta$,要尝试每个$\mathbf{X}$和$\theta$的组合,找这个函数的最大的值(概率)。

(对不起,我的汉语不行,我真的要多点看中文的百科!但是我有时候想使自己的单词描写东西)

http://www.robots.ox.ac.uk/~az/lectures/est/lect56.pdf

感知机

感知机模拟我们的神经元。我们的神经元个细胞的原理非常简单。每个神经细胞实行I/0功能:输入和输出。神经细胞有多个输入(被称为树突)和一个输出(被称为轴突)。如果神经细胞从树突接受足多(阈值以上的)刺激,那么神经细胞就发出信号通过它的轴突。每个输入一定有不相等的影响对神经元的决定是否要发出信号,所以把每个输入表示为$x_i, i=1,\dots,n$,我们要对每个输入给相对应的影响的强度$w_i, i=1,\dots,n$。如果我们把神经元的阈值表示为$b$,我们可以写这个决定的规则这样:
$$x_1 w_1 + x_2 w_2 + \cdots + x_n w_n > b$$
就是,如果在左边的多项式的值大于神经细胞的阈值,神经细胞会发出信号。如果不,它不会发出信号。所以,这样的分类器被称为“二元分类器“。还有,如果我们表示$c = -b$,重写这个不等式为:
$$x_1 w_1 + x_2 w_2 + \cdots + x_n w_n + c > 0$$
我们会看到这个不等式的解是$n$维超平面$x_1 w_1 + x_2 w_2 + \cdots + x_n w_n + c = 0$以上的$n$空间的$n$维向量。我们的头脑的神经细胞在学习的时候,我们可以说它一直重新调整这个$n$维超平面的定义(所有的$w_1,\cdots, w_n$和$c$),改变这个$n$维超平面位置和方向。但是,这个多项式下定义一个线性对象,所以这样的分类器被称为“二元线性分类器“。

注意:这个方法是一种几何方法,我们不应用概率论。

支持向量机

感知机只能做线性分类,因为超平面是线性的对象。但是,平时世界的现象是无线性的。我们能学习无线性的模式,因为多个神经元生成多层神经网络。但是,每个神经元好像感知机只有有限的树突(输入)的个数。以前人工智能的研究者集中模拟自然的神经元。但是,大约在1990年,科学家发现了一个超过神经元的限制的”超级感知机“的概念,被称为支持向量机。它的定义是从现代的数学的“泛函分析“的一个分支来的。其实,"向量“和“函数”这两概念很相似。每个向量下定义一个函数(这个函数的定义域是指标集,然后到达域是个,比如实数集),每个函数,如果它的定义域的集合是有序集,定义一个向量。若这样的函数的定义域的元素数的个数是无穷,则我们有$\mathbb{R}^\infty$向量空间的元素。其实,支持向量机就是在这样的无穷维空间(RKHS -- 一种希尔伯特空间)里被下定义的一种概念。如果我们把感知机的决定规则的方程,重写它为:
$$x_1 w_1 + x_2 w_2 + \cdots > b$$
我们就有支持向量机的决定规则。如果表示$c = -b$,只要发现无穷空间的超平面的方程式$x_1 w_1 + x_2 w_2 + \cdots + c = 0$(这里$1,2,...$ 属于不可数的指标集$I$),就可以有判别边界,分类数据点。

根本很简单的概念,但是在现实(在我们世界)我们的数据的测关值(向量)有只有限的随机变量的个数(维数)。还有,上面所示的方程式(多项式),虽然有无穷的项数,但它也是个线性组合。支持向量机有什么用?用它怎么能够学习非线性的模式?

其实,支持向量机也是个线性分类器。但是,它的原理很简单:原来的数据的线性化!理论上,我们先要表示我们的数据到无穷维数的希尔伯特空间,用特别的映射(被称为 Positive Semi-Definite Kernel -- 分类机的半正定核函数)为了线性化它,然后求出这些无穷维数的空间的向量的数量积。但是,实际上,我们不能把有限的维数的空间的向量,求出相对应的无穷维数的空间的向量。幸好,从数学的观点来看有一个很美丽的方法(Kernel Trick)怎么(不管我们不能求出无穷空间的相对应的向量)计算这些相对应的无穷维数的空间的向量的数量积$\mathcal{K}(\mathbf{x^1}, \mathbf{x^2}) = \langle \mathbf{x^1}, \mathbf{x^2} \rangle $!(根据这里,计算数据的核函数的值等价于计算这个数量积。)

实际上,有很多可能的数据的线性化的方法,对吧。其实,有各种各样的半正定核函数。对每个希望分类的数据的对象,我们要想想应用什么核函数为了能区别这些对象。我在这里找到的一个启发式怎么选择核函数的启发式就是: A kernel can be viewed as a similarity measure. A good kernel should have high values when applied to two similar objects, and it should have low values when applied to two dissimilar objects.(最相似的对象应该是更近)。

(我有兴趣的问题:如果我们有比感知机好的分类器,从这些分类器做的头脑会做更好的头脑吗?)

http://www.kernel-methods.net/tutorials/KMtalk.pdf