线性模型

线性回归

基本形式

$$y = \omega^T x+b$$

而线性回归的目标为试图得到

$$f(x_i)=\omega x_i +b,使得 f(x_i)\simeq y_i$$

对于多元线性回归，可以采用最小二乘法，其中（把b加入$\omega$中去）

$$X = \begin{bmatrix} x_{11}&x_{12}&\cdots&x_{1d}&1\\ x_{21}&x_{22}&\cdots&x_{2d}&1\\ \vdots&\vdots&\ddots&\vdots&\vdots\\ x_{m1}&x_{m2}&\cdots&x_{md}&1 \end{bmatrix}=\begin{bmatrix} x_1^T&1\\ x_2^T&1\\ \vdots&\vdots\\ x_m^T&1 \end{bmatrix}\\ \\ y = (y_1;y_2;\cdots;y_m)$$

那么对于性能指标$E=(y-X\hat\omega)^T(y-X\hat\omega)$来说，

$$\frac{\partial E}{\partial\hat \omega} = 2X^T(X\hat \omega-y)$$ $$\hat \omega^* = (X^TX)^{-1}X^Ty$$

故而此时的线性回归模型为

$$f(\hat x_i^T)=\hat x_i^T(X^TX)^{-1}X^Ty$$

• 问题是有时候$X^TX$并不是满秩的，此时系统有多个解，如何选择将由学习算法的归纳偏好来决定，常见做法是引入正则化(generalization)项

广义的线性回归

• 对数线性回归形式 $$lny = \omega^Tx+b$$ 对于更一般的，可考虑 $$y=g^{-1}(\omega^Tx+b)$$

对数几率回归

• 形式：

  $$\begin{align} y = \frac{1}{1+e^{-(\omega^2x+b)}} \end{align}$$

  故而，

  $$ln(\frac{y}{1-y})=\omega^Tx+b$$

  其中,$ln(\frac{y}{1-y})$称为对数几率

  对于二分类问题，上式还等价于

  $$ln\frac{p(y=1|x)}{p(y=0|x)}=\omega^Tx+b\\ p(y=1|x)=\frac{e^{\omega^Tx+b}}{1+e^{\omega^Tx+b}}\\ p(y=0|x)=\frac{1}{1+e^{\omega^Tx+b}}$$

  可以通过极大似然法来估计$\omega$和b，对于给定数据集，他的似然函数为

  $$l(\omega,b)=\sum_{i=1}^mlnp(y_i|x_i;\omega,b)$$

  而

  $$p(y_i|x_i;\omega,b)=y_ip_1(\hat x_i;\beta)+(1-y_i)p_0(\hat x_i;\beta)$$

  最大化$l(\omega,b)$相当于最小化下式，推导过程

  $$l(\beta)=\sum^{n}_{i=1}(-y_i\beta^T\hat x_i+ln(1+e^{\beta^T\hat x_i}))$$

  上式是一个关于$\beta$的高阶可导连续凸函数，可用牛顿法求解，

  $$\beta^{t+1}=\beta^t-(\frac{\partial^2l(\beta)}{\partial\beta\partial \beta^T})^{-1}\frac{\partial l(\beta)}{\partial \beta}$$

线性/Fisher判别分析(Linear Discriminant Analysis)

• 主要思想：对给定训练集，设法将所有样例投影到一条直线上，使得同类样例的投影点尽可能接近，异类样例的投影点尽可能远离；下面用$X_i,\mu_i,\Sigma_i$分别表示第$i\in\{0,1\}$类示例的集合，均值向量，协方差矩阵

  则样本中心在直线上的投影为$\omega^T\mu_i$,若将样本投影到直线上，样本的协方差为$\omega^T\Sigma_i\omega$

  那么，为了让同类样例的投影点尽可能接近，可以让同类样例投影点的协方差尽可能小，即$\omega^T\Sigma_0\omega+\omega^T\Sigma_1\omega$尽可能小；而欲使异类样例的投影点尽可能远离，可以让类中心之间的距离尽可能大，即$\parallel \omega^T\mu_0-\omega^T\mu_1\parallel_2^2$尽可能大，故而将目标函数设为

  $$J=\frac{\parallel \omega^T\mu_0-\omega^T\mu_1\parallel_2^2}{\omega^T\Sigma_0\omega+\omega^T\Sigma_1\omega}$$

  定义类内散度矩阵为

  $$\begin{equation} \begin{aligned} S_\omega &=&\Sigma_0+\Sigma_1\\ &=&\sum_{x\in X_0}(x-\mu_0)(x-\mu_0)^T+\sum_{x\in X_1}(x-\mu_1)(x-\mu_1)^T \end{aligned} \end{equation}$$

  类间散度矩阵

  $$S_b=(\mu_0-\mu_1)(\mu_0-\mu_1)^T$$

  那么，目标函数可以重写为$J=\frac{\omega^TS_b\omega}{\omega^TS_\omega\omega}$,称之为广义瑞利商,因为分子分母均为$\omega$的二次项，因此目标函数的解与$\omega$的长度无关，只与其方向有关，不失一般性，令分母为1

  最终，问题变成了

  $$\min_{\omega}~~~-\omega^TS_b\omega\\ s.t.~~~\omega^TS_{\omega}\omega=1$$

  用拉格朗日乘子法可得

  $$S_b\omega=\lambda S_{\omega}\omega$$

  注意到$S_b\omega$的方向恒为$\mu_0-\mu_1$，不妨令

  $$S_b\omega=\lambda(\mu_0-\mu_1)$$

  故而，有

  $$\omega=\S^{-1}_{\omega}(\mu_0-\mu_1)$$

  对于多分类任务来说,可以对其进一步拓展。

多分类学习

• 一般是基于一些基本策略，利用二分类学习器来解决多分类问题。

• 拆分法:

  给定数据集$D=\{(x_1,y_1),(x_2,y_2),…,(x_m,y_m)\},y_i\in\{C_1,C_2,…,C_N\}​$

  • 一对一(OvO):将N个类别两两配对，产生$\frac{N(N-1)}{2}​$个二分任务，最终测试阶段，新样本同时提交给所有分类器，通过投票来选择最终分类结果
  • 一对其余(OvR):每次将一个类的样例作为正例，所有其他类的样例作为反例来训练N个分类器。在测试时若有一个分类器预测为正类，则对应类别标记作为最终分类结果；若有多个分类器预测为正类，则通常考虑各分类器的预测置信度，选择置信度最大的类别标记作为预测结果
  • 多对多(MvM):每次将若干个类作为正类，若干个其他类作为反类，一般用纠错输出码(Error Correction Output Codes)来进行校正
    • 编码：对N个类别进行M次划分，每次划分将一部分类划为正类，一部分划为反类，从而形成一个二分类训练集，这样一共产生M个训练集，可训练处M个分类器。
    • 解码：M个分类器分别对测试样本进行测试，这些测试的标记组成一个编码，将此编码与每个类别各自的编码进行比较，返回其中距离最小的类别作为最终预测结果。

类别不平衡问题

• 有时候训练集中正反例的数目差距比较大，而前面的推导都是基于两者相同产生的，即 $$\frac{y}{1-y}>1,则为正例$$ 现在应该改为,($m^+$,$m^-$分别为正负实例的个数) $$\frac{y}{1-y}>\frac{m^+}{m^-}$$ 即应该让 $$\frac{y'}{1-y'}=\frac{y}{1-y}\times\frac{m^-}{m^+}$$