阅读 781

机器怎样学习?

本系列是台湾大学资讯工程系林軒田(Hsuan-Tien Lin)教授开设的《机器学习基石》课程的梳理。重在梳理,而非详细的笔记,因此可能会略去一些细节。

该课程共16讲,分为4个部分:

  1. 机器什么时候能够学习?(When Can Machines Learn?)
  2. 机器为什么能够学习?(Why Can Machines Learn?)
  3. 机器怎样学习?(How Can Machines Learn?)
  4. 机器怎样可以学得更好?(How Can Machines Learn Better?)

本文是第3部分,对应原课程中的9-12讲。

本部分的主要内容:

  • 线性回归算法详解,以及泛化能力的保证、能否用于二分类问题等;
  • 逻辑回归算法详解,并引入梯度下降方法;
  • 阐述PLA、线性回归、逻辑回归3种方法在分类问题上的联系与区别,并引入随机梯度下降方法;
  • 多分类问题中的OVA、OVO方法;
  • 特征的非线性变换,以及该如何控制变换后的复杂度。

1 线性回归

在第一部分中讲过机器学习的分类,当Y=R\mathcal{Y}=\mathbb{R}时,就是回归。

1.1 线性回归算法

线性回归的假设集十分简单,h(x)=wTxh(\mathbf{x})=\mathbf{w}^T\mathbf{x},其实就是感知机模型去除了符号函数。

它的逐点误差度量可设为err(y^,y)=(y^y)2\text{err}(\hat{y}, y)=(\hat{y}-y)^2,那么样本内外的误差分别为 Ein(w)=1Nn=1N(wTxnyn)2E_{\text{in}}(\mathbf{w})=\dfrac{1}{N}\sum\limits_{n=1}^{N}(\mathbf{w}^T \mathbf{x}_n-y_n)^2Eout(w)=E(x,y)P(wTxy)2E_{\text{out}}(\mathbf{w})=\mathop{\mathcal{E}}\limits_{(\mathbf{x},y)\sim P}(\mathbf{w}^T \mathbf{x}-y)^2 要最小化EinE_{\text{in}}很简单,当它取到最小时必有梯度00,因此可先计算出它的梯度:

Ein(w)=2N(XTXwXTy)\nabla E_{\text{in}}(\mathbf{w})=\dfrac{2}{N}(X^T X\mathbf{w}-X^T \mathbf{y})

令它为00即可。如图所示:

XTXX^T X可逆(当Nd+1N\gg d+1时基本上会满足),则可直接得出 wLIN=(XTX)1XTy\mathbf{w}_{\text{LIN}}=(X^T X)^{-1} X^T \mathbf{y}

如果XTXX^T X是奇异的呢?可先定义“伪逆”(pseudo-inverse)XX^\dagger,在定义完后有 wLIN=Xy\mathbf{w}_{\text{LIN}}=X^\dagger \mathbf{y}

在实践中,建议直接使用XX^\dagger,一方面可避免判断XTXX^T X是否可逆,另一方面就算在几乎不可逆的情况下,它也是在数值上稳定的。

1.2 线性回归的泛化

线性回归看起来没有“学习”过程,是一步到位的,那么它算机器学习吗?

事实上,只要可以保证Eout(wLIN)E_{\text{out}}(\mathbf{w}_\text{LIN})足够小,那么就可以说“发生了”学习。

在这里,我们不从VC维理论出发,而从另一个角度说明为什么Eout(wLIN)E_{\text{out}}(\mathbf{w}_\text{LIN})会足够小。

我们先来看平均的EinE_{\text{in}}有多大:

Ein=EDPN{Ein(wLIN w.r.t D)}\overline{E_{\text{in}}}=\mathop{\mathcal{E}}\limits_{\mathcal{D}\sim P^N}\{E_{\text{in}}(\mathbf{w}_\text{LIN} \text{ w.r.t } \mathcal{D})\}

其中

Ein(wLIN)=1Nyy^2=1N(IXX)y2\begin{aligned} E_{\text{in}}(\mathbf{w}_\text{LIN})&=\dfrac{1}{N}\Vert \mathbf{y}-\hat{\mathbf{y}}\Vert^2\\ &=\dfrac{1}{N}\Vert (I-XX^\dagger)\mathbf{y}\Vert^2 \end{aligned}

可将H=XXH=XX^\dagger称为hat matrix,因为它可将y\mathbf{y}映射到y^\hat{\mathbf{y}}。由下图可知,若y\mathbf{y}由理想的f(X)spanf(X)\in \text{span}加上噪声noise\mathbf{noise}生成,那么IHI-H也可将noise\mathbf{noise}映射为yy^\mathbf{y}-\hat{\mathbf{y}}

trace(IH)=N(d+1)\text{trace}(I-H)=N-(d+1),迹可以理解为“能量”,因此有

Ein(wLIN)=1Nyy^2=1N(IH)noise2=1N(N(d+1))noise2\begin{aligned} E_{\text{in}}(\mathbf{w}_\text{LIN}) &= \dfrac{1}{N}\Vert \mathbf{y}-\hat{\mathbf{y}}\Vert^2\\ &= \dfrac{1}{N}\Vert (I-H)\mathbf{noise}\Vert^2\\ &= \dfrac{1}{N}(N-(d+1))\Vert\mathbf{noise}\Vert^2 \end{aligned}

如果对EinE_{\text{in}}取平均,大概可以理解为 Ein=noise level(1d+1N)\overline{E_{\text{in}}}=\mathbf{noise}\text{ level} \cdot (1-\dfrac{d+1}{N}) 类似地有 Eout=noise level(1+d+1N)\overline{E_{\text{out}}}=\mathbf{noise}\text{ level} \cdot (1+\dfrac{d+1}{N}) (证明过程略)。

因此Ein\overline{E_{\text{in}}}Eout\overline{E_{\text{out}}}的关系如图:

NN\to\infty,则二者都收敛于σ2\sigma^2noise level\mathbf{noise}\text{ level}),泛化误差的期望为2(d+1)N\dfrac{2(d+1)}{N}。因此,学习是会“发生”的!

VC维理论说明的是EinE_{\text{in}}EoutE_{\text{out}}相差较远的概率有上限,而这里说明的是它们的平均差距会收敛。角度不同,但两种方式都说明了泛化的能力。

1.3 用线性回归进行二分类

在线性分类中,Y={+1,1}\mathcal{Y}=\{+1,-1\}h(x)=sign(wTx)h(\mathbf{x})=\text{sign}({\mathbf{w}^T\mathbf{x}})err(y^,y)=1[y^y]\text{err}(\hat{y},y)=\mathbf{1}_{[\hat{y}\ne y]},找它的最优解是个NP-hard问题。

由于{+1,1}R\{+1,-1\}\subset \mathbb{R},即样本的正负类别也能用实数表示,而在线性回归中Y=R\mathcal{Y}=\mathbb{R},那么,直接来一发线性回归,得到wLIN\mathbf{w}_\text{LIN},然后让g(x)=sign(wLINTx)g(\mathbf{x})=\text{sign}(\mathbf{w}_\text{LIN}^T\mathbf{x}),这是否可行呢?

把线性分类和线性回归的误差度量分别记为err0/1=1[sign(wTx)y]\text{err}_{0/1}=\mathbf{1}_{[\text{sign}(\mathbf{w}^T\mathbf{x})\ne y]}errsqr=(wTxy)2\text{err}_\text{sqr}=({\mathbf{w}^T\mathbf{x}- y})^2,它们的关系如下图:

从中可直观地看出,err0/1errsqr\text{err}_{0/1} \le \text{err}_\text{sqr}一定成立。由此,有

classificationEout(w)VCclassificationEin(w)+regressionEin(w)+\begin{aligned} &\text{classification} E_\text{out}(\mathbf{w})\\ \overset{VC}{\le} & \text{classification} E_\text{in}(\mathbf{w})+\sqrt{\cdots}\\ \le & \text{regression} E_\text{in}(\mathbf{w})+\sqrt{\cdots} \end{aligned}

也就是说,让回归的EinE_{\text{in}}做得足够好,也可以使得分类的EoutE_{\text{out}}足够小,只不过上限更宽松一些而已。这样做就是用边界的紧度(bound tightness)换取计算效率(efficiency)

一般wLIN\mathbf{w}_\text{LIN}可用来作为PLA或pocket算法的初始向量。

2 逻辑回归

2.1 逻辑回归算法

二分类中,我们感兴趣的是

f(x)=sign(P(+1x)12)+1,1f(\mathbf{x})=\text{sign}(P(+1|\mathbf{x})-\dfrac{1}{2}) \in {+1,-1}

但在很多场景下,我们想要做的是“软”(soft)分类,即得到某个分类的概率,此时感兴趣的是

f(x)=P(+1x)[0,1]f(\mathbf{x})=P(+1|\mathbf{x}) \in [0,1]

问题在于,我们得到的数据标签是样本的类别,而非样本被分到某个类的概率。

对于一个样本的所有特征x=(x0,x1,x2,,xd)\mathbf{x}=(x_0, x_1, x_2, \cdots,x_d),令s=i=0dwixis=\sum\limits_{i=0}^{d} w_i x_i。我们可用逻辑函数(logistic function)θ(s)\theta(s)将它转换成估计的概率。也就是说,逻辑回归(logistic regression)的假设h(x)=θ(wTx)h(\mathbf{x})=\theta(\mathbf{w}^T\mathbf{x})

最常用的逻辑函数是 θ(s)=es1+es=11+es\theta(s)=\dfrac{e^s}{1+e^s}=\dfrac{1}{1+e^{-s}}

函数图像如下:

可见,它是个光滑的、单调的、“S”形的(sigmoid)函数。

接下来,要定义逻辑回归的Ein(w)E_\text{in}(\mathbf{w})。先将目标函数f(x)=P(+1x)f(\mathbf{x})=P(+1|\mathbf{x})反表示为

P(yx)={f(x)for y=+11f(x)for y=1P(y|\mathbf{x})=\begin{cases} f(\mathbf{x})&\text{for } y=+1\\ 1-f(\mathbf{x})&\text{for } y=-1 \end{cases}

假设手中的数据集为 D={(x1,),(x2,×),,(xN,×)}\mathcal{D}=\{(\mathbf{x}_1,\circ),(\mathbf{x}_2,\times),\ldots, (\mathbf{x}_N,\times)\}

那么,由ff生成D\mathcal{D}的概率为

P(x1)f(x1)×P(x2)(1f(x2))××P(xN)(1f(xN)\begin{aligned} &P(\mathbf{x}_1)f(\mathbf{x}_1)\\ \times &P(\mathbf{x}_2)(1-f(\mathbf{x}_2))\\ \times &\cdots\\ \times &P(\mathbf{x}_N)(1-f(\mathbf{x}_N) \end{aligned}

由我们的假设hh生成D\mathcal{D}的似然(likelihood)为

P(x1)h(x1)×P(x2)(1h(x2))××P(xN)(1h(xN)\begin{aligned} &P(\mathbf{x}_1)h(\mathbf{x}_1)\\ \times &P(\mathbf{x}_2)(1-h(\mathbf{x}_2))\\ \times &\cdots\\ \times &P(\mathbf{x}_N)(1-h(\mathbf{x}_N) \end{aligned}

如果hfh\approx f,那么hh生成D\mathcal{D}的似然也应该接近于由ff生成D\mathcal{D}的概率,并且由ff生成D\mathcal{D}的概率应该是较大的(正好被我们抽样抽到)。所以,机器学习算法可以取

g=argmaxhlikelihood(h)g=\mathop{\arg\max}\limits_{h} \text{likelihood}(h)

h(x)=θ(wTx)h(\mathbf{x})=\theta(\mathbf{w}^T\mathbf{x}),由函数的性质可知,1h(x)=h(x)1-h(\mathbf{x})=h(-\mathbf{x}),所以

likelihood(h)=P(x1)h(x1)×P(x2)h(x2)××P(xN)h(xN)\begin{aligned} &\text{likelihood}(h)\\ =&P(\mathbf{x}_1)h(\mathbf{x}_1)\\ \times &P(\mathbf{x}_2)h(-\mathbf{x}_2)\\ \times &\cdots\\ \times &P(\mathbf{x}_N)h(-\mathbf{x}_N) \end{aligned}

P(x1)P(\mathbf{x}_1)P(x2)P(\mathbf{x}_2)、……、P(xN)P(\mathbf{x}_N)都与hh无关,因此有

likelihood(logistic h)n=1Nh(ynxn)\text{likelihood}(\text{logistic } h)\propto \prod\limits_{n=1}^N h(y_n\mathbf{x}_n)

现在要将它最大化,以找出最终的hh。可先把θ(s)\theta(s)代入,再取对数(对数函数单调,不改变最大化取值的点),变为

maxwlnn=1Nθ(ynwTxn)\max\limits_\mathbf{w} \ln\prod\limits_{n=1}^N\theta(y_n\mathbf{w}^T\mathbf{x}_n)

再取相反数(最大化变为最小化)、除NN(不改变最值点)后,又可变为

minw1Nn=1Nlnθ(ynwTxn)\min\limits_\mathbf{w} \dfrac{1}{N}\sum\limits_{n=1}^N - \ln \theta(y_n\mathbf{w}^T\mathbf{x}_n)

θ(s)\theta(s)展开得到

minw1Nn=1Nln(1+exp(ynwTxn))\min\limits_\mathbf{w} \dfrac{1}{N}\sum\limits_{n=1}^N \ln \left(1+\exp(-y_n\mathbf{w}^T\mathbf{x}_n)\right)

err(w,x,y)=ln(1+exp(ywx))\text{err}(\mathbf{w},\mathbf{x},y)=\ln\left(1+\exp(-y\mathbf{w}\mathbf{x})\right)

这就是交叉熵误差(cross-entropy error),而n=1Nerr(w,xn,yn)\sum\limits_{n=1}^N \text{err}(\mathbf{w},\mathbf{x}_n,y_n)就是Ein(w)E_\text{in}(\mathbf{w})

2.2 梯度下降

接下来就要最小化Ein(w)E_\text{in}(\mathbf{w}),它是连续的、可微的、二次可微的、凸的,因此可以试着让它梯度为00。求出它的梯度

Ein(w)=1Nn=1Nθ(ynwTxn)(ynxn)\nabla E_{\text{in}}(\mathbf{w})=\dfrac{1}{N}\sum_{n=1}^N\theta(-y_n\mathbf{w}^T\mathbf{x}_n)(-y_n\mathbf{x}_n)

它的梯度可以看成是以θ()\theta(\cdot)为权重的ynxn-y_n\mathbf{x}_n的加权平均。要让它为0,有两种方式:

  • 让所有的θ(ynwTxn)\theta(-y_n\mathbf{w}^T\mathbf{x}_n)都为0,这意味着所有样本都满足ynwnxn0y_n\mathbf{w}_n\mathbf{x}_n\gg 0,也即D\mathcal{D}是线性可分的;
  • D\mathcal{D}不是线性可分的,要让加权和为0,这是个非线性方程,没有闭式解(closed-form solution)。

可用与PLA中类似的方法进行迭代,即wt+1wt+ηv\mathbf{w}_{t+1}\leftarrow\mathbf{w}_t+\eta\mathbf{v},其中v\mathbf{v}确定了更新的方向,η\eta确定了更新的步长,如图:

怎么迭代呢?可用贪心算法,一步步让EinE_\text{in}变小。假设已经给定某个η\eta,要确定v\mathbf{v}的方向,每一步的更新问题就转换成了

minv=1Ein(wt+ηv)\min\limits_{\Vert\mathbf{v}\Vert=1}E_\text{in}(\mathbf{w}_t+\eta\mathbf{v})

看起来仿佛更难解了。但如果η\eta足够小,我们可以用局部线性近似展开它(泰勒展开,Taylor expansion):

Ein(wt+ηv)Ein(wt)+ηvTEin(wt)E_\text{in}(\mathbf{w}_t+\eta\mathbf{v})\approx E_\text{in}(\mathbf{w}_t)+\eta\mathbf{v}^T\nabla E_\text{in}(\mathbf{w}_t)

式中Ein(wt)E_\text{in}(\mathbf{w}_t)Ein(wt)\nabla E_\text{in}(\mathbf{w}_t)已知,η\eta给定,只需确定v\mathbf{v}即可,注意到上式第二项本质上是两个向量内积,当两个向量方向相反时值最小,因此要最小化上式,可取

v=Ein(wt)Ein(wt)\mathbf{v}=-\dfrac{\nabla E_\text{in}(\mathbf{w}_t)}{\Vert\nabla E_\text{in}(\mathbf{w}_t)\Vert}

梯度下降的迭代更新就变成了:对于给定的较小η\etawt+1wtηEin(wt)Ein(wt)\mathbf{w}_{t+1}\leftarrow\mathbf{w}_t-\eta\dfrac{\nabla E_\text{in}(\mathbf{w}_t)}{\Vert\nabla E_\text{in}(\mathbf{w}_t)\Vert}

η\eta太小会导致非常慢,太大会导致不稳定,最好用变化的η\eta,如下图所示:

那么,η\eta怎么变比较好?可让它与Ein(wt)\Vert\nabla E_\text{in}(\mathbf{w}_t)\Vert正相关,将原来固定的η\eta乘上Ein(wt)\Vert\nabla E_\text{in}(\mathbf{w}_t)\Vert即可。这样,更新规则也就变成了

wt+1wtηEin(wt)\mathbf{w}_{t+1}\leftarrow\mathbf{w}_t-\eta{\nabla E_\text{in}(\mathbf{w}_t)}

这个新的η\eta可叫作固定的学习率learning rate)。

3 分类的线性模型

3.1 三种算法的比较

s=wTxs=\mathbf{w}^T\mathbf{x},以下是总结三种模型(线性分类、线性回归、逻辑回归):

这里的ysys可称为分类正确度分数(classification correctness score),即度量分类有多正确,该值越大,说明分类越“正确”。

若将交叉熵误差函数errCE(s,y)\text{err}_\text{CE}(s,y)做scale(除ln2\ln 2),得到 errSCE(s,y)=log2(1+exp(ys))\text{err}_\text{SCE}(s,y)=\log_2(1+\exp(-ys))

把它们的误差函数都画出来,可得下图:

从图中可知,一定有 err0/1errSCE(s,y)=1ln2errCE(s,y)\text{err}_{0/1} \le \text{err}_\text{SCE}(s,y) = \dfrac{1}{\ln 2}\text{err}_\text{CE}(s,y)

由此可以用VC维理论证明,使用errCE\text{err}_\text{CE}也可以做好分类任务,有两种思路:

  • 从分类的角度出发,有
Eout0/1(w)Ein0/1(w)+Ω0/11ln2EinCE(w)+Ω0/1\begin{aligned} E_\text{out}^{0/1}(\mathbf{w})&\le E_\text{in}^{0/1}(\mathbf{w})+\Omega^{0/1}\\ &\le \dfrac{1}{\ln 2} E_\text{in}^\text{CE}(\mathbf{w})+\Omega^{0/1} \end{aligned}
  • 从交叉熵角度出发,有
Eout0/1(w)1ln2EoutCE(w)1ln2EinCE(w)+1ln2ΩCE\begin{aligned} E_\text{out}^{0/1}(\mathbf{w})&\le \dfrac{1}{\ln 2} E_\text{out}^\text{CE}(\mathbf{w})\\ &\le \dfrac{1}{\ln 2} E_\text{in}^\text{CE}(\mathbf{w})+\dfrac{1}{\ln 2}\Omega^\text{CE} \end{aligned}

不管用哪种方式,只要保证EinCEE_\text{in}^\text{CE}足够小,都可以保证Eout0/1(w)E_\text{out}^{0/1}(\mathbf{w})也足够小,也就是说,使用逻辑回归或线性回归都可以做线性分类。

用PLA、线性回归、逻辑回归做分类,三种方法的优缺点如下:

3.2 随机梯度下降

PLA每次迭代的时间复杂度为O(1)O(1),但逻辑回归(或pocket算法)每次迭代都需要对D\mathcal{D}中的所有样本进行一次运算,时间复杂度为O(N)O(N),能不能让每次迭代的时间复杂度也变成O(1)O(1)

我们在做更新wt+1wt+ηv\mathbf{w}_{t+1}\leftarrow\mathbf{w}_t+\eta\mathbf{v}时,取了

v=Ein(wt)=1Nn=1Nθ(ynwtTxn)(ynxn)\begin{aligned} \mathbf{v}&=-\nabla E_{\text{in}}(\mathbf{w}_t)\\ &=-\dfrac{1}{N}\sum_{n=1}^N\theta(-y_n\mathbf{w}_t^T\mathbf{x}_n)(-y_n\mathbf{x}_n) \end{aligned}

可以看到,计算梯度需要遍历所有样本,复杂度实在太高了。可将它里面的1Nn=1N\dfrac{1}{N}\sum\limits_{n=1}^{N}看作是期望E\mathcal{E},相当于不断随机抽一个样本计算出来的结果的平均。若将随机抽一个样本nn算出来的梯度称为随机梯度werr(w,xn,yn)\nabla_\mathbf{w}\text{err}(\mathbf{w},\mathbf{x}_n,y_n),那么真正的梯度可看作是它的期望:

wEin(w)=Erandom nwerr(w,xn,yn)\nabla_\mathbf{w} E_\text{in}(\mathbf{w})=\mathop{\mathcal{E}}_{\text{random }n}\nabla_\mathbf{w}\text{err}(\mathbf{w},\mathbf{x}_n,y_n)

这样,就可以用随机梯度下降(Stochastic Gradient Descent,SGD)进行迭代。它的好处是非常简单,计算的成本低,非常适用于大数据或在线学习的情况,缺点是不够稳定。

在逻辑回归中,用SGD更新的步骤就变成了

wt+1wt+ηθ(ynwtTxn)(ynxn)\mathbf{w}_{t+1}\leftarrow\mathbf{w}_t+\eta\cdot \theta(-y_n\mathbf{w}_t^T\mathbf{x}_n)(y_n\mathbf{x}_n)

这与PLA中的更新步骤十分相似,PLA中是这样的:

wt+1wt+11[yNsign(wtTxn)](ynxn)\mathbf{w}_{t+1}\leftarrow\mathbf{w}_t+1 \cdot \mathbf{1}_{[y_N\ne \text{sign}(\mathbf{w}_t^T \mathbf{x}_n)]}(y_n\mathbf{x}_n)

因此用SGD的逻辑回归,可以看作是“软”的PLA。而反过来,若取η=1\eta=1,则PLA在wtTxn\mathbf{w}_t^T \mathbf{x}_n很大的时候也可以看作是用SGD的逻辑回归。

在用SGD时,有两个经验法则:

  • 什么时候停止?tt足够大的时候就可以(不要判断梯度是否真的为0,否则又会带来梯度计算的复杂度);
  • x\mathbf{x}在一般范围内时,就取η=0.1\eta=0.1吧。

4 多分类问题

4.1 用逻辑回归做多分类

假设Y={,,,}\mathcal{Y}=\{\square, \diamondsuit,\triangle,\star\},数据分布如下图:

可对每个类别分别做一次分类,如下图:

但这样做,在最后要把它们结合起来时,会出现问题,有些区域无法判定属于哪一类:

怎么解决呢?可以用逻辑回归做“软”分类器,依旧是对每个类别kk,用数据集

D[k]={(xn,yn=21[yn=k]1)}n=1N\mathcal{D}_{[k]}=\{(\mathbf{x}_n,y_n'=2\cdot\mathbf{1}_{[y_n=k]}-1)\}_{n=1}^{N}

做一次逻辑回归,得到一个分类器w[k]\mathbf{w}_{[k]}

做完后要将它们结合起来,可取g(x)=argmaxkYθ(w[k]Tx)g(\mathbf{x})=\arg\max_{k\in\mathcal{Y}}\theta(\mathbf{w}_{[k]}^T\mathbf{x}),这样就得到某个点应该属于哪一类了:

这样做称为OVA(One-Versus-All) Decomposition,好处是有效率,可以和类似逻辑回归的方法结合起来,但缺点在于当KK很大时,往往会使D[k]\mathcal{D}_{[k]}非常不平衡,比如有100类,并且分布比较均匀,OVA每次用于训练的样本的两类数据的个数就会非常悬殊。

可以再进行扩展,如multinomial ('coupled') logistic regression,加入一些如“属于不同类的概率加起来应该为1”之类的限制,让它更适合用于多分类。

4.2 用二分类做多分类

为了克服不平衡问题,可以对两两类别进行训练,即用数据集

D[k,]={(xn,yn=21[yn=k]1):yn=k or yn=}\mathcal{D}_{[k,\ell]}=\{(\mathbf{x}_n,y_n'=2\cdot\mathbf{1}_{[y_n=k]}-1):y_n=k\text{ or } y_n=\ell\}

进行线性二分类:

最后,取 g(x)=tournament champion{w[k,]Tx}g(\mathbf{x})=\text{tournament champion}\{\mathbf{w}_{[k,\ell]}^T\mathbf{x}\}

即可:

这样的方法叫作OVO(One-Versus-One)Decomposition,好处在于有效率(因为每次训练用的数据量较少),并且是稳定的,可以和任何二分类方法相结合,但缺点在于不断计算w[k,]\mathbf{w}_{[k,\ell]}的操作总共的复杂度是O(K2)O(K^2),需要更多运算空间。当KK不是非常大时,OVO很常用。

5 非线性变换

对于某些数据集来说,不管怎么使用线性模型,EinE_{in}都很大:

5.1 二次的假设集

我们发现,如果用一个圆来做它的分类界线,它其实是可分的:

所以我们要重新设计圆形PLA、圆形回归、……吗?当然不是。我们可以将xX\mathbf{x}\in\mathcal{X}用变换Φ\Phi映射到zZ\mathbf{z}\in\mathcal{Z},使得在X\mathcal{X}中圆形可分的数据在Z\mathcal{Z}中线性可分。

通过由Φ2(x)=(1,x1,x2,x12,x1x2,x22)\Phi_2(\mathbf{x})=(1,x_1,x_2,x_1^2,x_1x_2,x^2_2)映射而来的Z\mathcal{Z}空间,可构成一般的二次假设集:

HΦ2={h(x):h(x)=h~(Φ2(x)) for some linear h~ on Z}\mathcal{H}_{\Phi_2}=\{h(\mathbf{x}):h(\mathbf{x})=\tilde h(\Phi_2(\mathbf{x}))\text{ for some linear }\tilde h \text{ on }\mathcal{Z}\}

当然也可以用更高次的非线性变换,用非线性变换的流程如下图:

具体步骤如下:

  1. 先用Φ\Phi{(xn,yn)}\{(\mathbf{x}_n,y_n)\}变换到{(zn=Φ(xn),yn)}\{(\mathbf{z}_n=\Phi(\mathbf{x}_n),y_n)\}
  2. {(zn,yn)}\{(\mathbf{z}_n,y_n)\}和线性分类算法A\mathcal{A}训练出模型w~\tilde{\mathbf{w}}
  3. 返回g(x)=sign(w~TΦ(x))g(\mathbf{x})=\text{sign}\left(\tilde{\mathbf{w}}^T \Phi(\mathbf{x})\right)即可。

5.2 复杂度的代价

假设用QQ次的非线性变换:

ΦQ(x)=(1,x1,x2,,xd,x12,x1x2,,xd2,,x1Q,x1Q1x2,,xdQ)\begin{aligned} \Phi_Q(\mathbf{x})=(&1,\\ &x_1,x_2,\ldots,x_d,\\ &x_1^2,x_1 x_2,\ldots,x_d^2,\\ &\cdots,\\ &x_1^Q,x_1^{Q-1}x_2,\ldots,x_d^Q) \end{aligned}

式中的项数1+d~1+\tilde d是多少呢?若有dd个特征,可以在补上1后认为上面式子后边的每一项都是QQ次的,也就是说要对d+1d+1项每项都赋予一个次数,并且所有次数之和必须为QQ。可以用隔板法:想象共有Q+d+1Q+d+1个小球,要在它们的空隙中放入dd个隔板,隔成d+1d+1段,每一段的小球个数减去1代表了对应位置的项的次数,由于要求每段中至少有1个小球,因此两端不能放隔板,共有Q+dQ+d个位置可放隔板,共有(Q+dd)\binom{Q+d}{d}种放法,也就是说,上式等号右边的项数

1+d~=(Q+dd)=O(Qd)1+\tilde d=\binom{Q+d}{d}=O(Q^d)

QQ较大时,一方面计算或存储的成本非常高,另一方面1+d~1+\tilde ddVC(HΦQ)d_\text{VC}(\mathcal{H}_{\Phi_Q})的上界,QQ太大会导致dVCd_\text{VC}过大,模型损失了泛化能力。

5.3 QQ的选择

如何选择QQ?假设Φ0(x)=(1)\Phi_0(\mathbf{x})=(1)Φ1(x)=(Φ0(x),x1,x2,,xd,)\Phi_1(\mathbf{x})=\left(\Phi_0(\mathbf{x}),x_1,x_2,\ldots,x_d,\right),……,ΦQ(x)=(ΦQ1(x),x1Q,x1Q1x2,,xdQ,)\Phi_Q(\mathbf{x})=\left(\Phi_{Q-1}(\mathbf{x}),x_1^Q,x_1^{Q-1}x_2,\ldots,x_d^Q,\right),将它们的假设集分别记为H0\mathcal{H}_0H1\mathcal{H}_1,……,HQ\mathcal{H}_Q,它们存在嵌套关系

H0H1H2\mathcal{H}_0 \subset \mathcal{H}_1\subset\mathcal{H}_2\subset\cdots

如图所示:

并且,它们的VC维满足

dVC(H0)dVC(H1)dVC(H2)d_\text{VC}(\mathcal{H}_0)\le d_\text{VC}(\mathcal{H}_1)\le d_\text{VC}(\mathcal{H}_2)\le\cdots

若取gi=argminhHiEin(h)g_i=\arg\min_{h\in \mathcal{H}_i} E_\text{in}(h),则它们的EinE_\text{in}满足

Ein(g0)Ein(g1)Ein(g2)E_\text{in}(g_0)\ge E_\text{in}(g_1)\ge E_\text{in}(g_2)\ge \cdots

如何选择QQ?安全的做法是,先看Ein(g1)E_\text{in}(g_1)是否已经足够小,如果足够小,就可以了,否则,就用再稍微复杂一些的模型,也就是在下图中向右移动: