机器学习日志8

最优边界分类器

对于我们前面学习的算法，我们的目标是寻找最大的边距从而使得我们的决策边界（超平面）更加可信。我们讲这种思想数学化表示为：

​ max_????,w,b ????

​ s.t. y⁽ⁱ⁾(w^Tx⁽ⁱ⁾ +b)≥????, i=1,…,n

​ ||w||=1

对于中间公式说明，训练样本到决策边界的距离最小为样本集的geometric margin，其中约束||w||=1目的是让functional margin等于geometric margin；

但是约束条件 ||w||=1使得上面的问题是一个非凸优化问题，这会使得运算比较困难，所以我们尝试将问题转化成为另一种格式

由于γ = γˆ/||w|，所以我们最大化的目标变成了 γˆ/||w||，即所有样本点的距离都大于functional margin，到此，我们摆脱了||w|| = 1 的约束条件，但是我们现在要最大化γˆ/||w||，这同样是一个非凸问题，同样不利于运算，所以我们继续向下；

记得我们在学习functional margin时有提过，我们可以随意缩放w和b的值，但是却可以不影响决策边界，下面就到应用他的时候了我们要缩放w和b使得：

所以我们最大化γˆ/||w|| 的目标变成了最大化1/||w||，这同理于最小化||w||²,所以问题转化为数学形式为：
$min_{w,b}\frac{1}{2}||w||^2$minw,b​21​∣∣w∣∣2

$y^{(i)}(w^Tx^{(i)}+b)≥ 1, i = 1,...,n$y(i)(wTx(i)+b)≥1,i=1,...,n

现在这个问题变成了凸二次目标和线性约束，它的结果就是最优边界分类器，可以利用QP软件求得结果。

核心方法

特征映射

前面我们根据x和y的线性关系学习了线性回归，今天我们将要学习一种非线性关系的方法；假设我们有三次函数

y = θ₃x₃ + θ₂x₂ + θ₁x + θ₀.我们通过对对变量的重写可以将他转换成linear function（一般指一次函数），首先我们定义：????：ℝ—>ℝ⁴:

让θ ∈ ℝ⁴包含输入θ₀, θ₁, θ₂, θ₀随后我们就可以重新写出我们的公式为：

这样三次函数就改写成了以????（x）表示的一次函数，为了区分输入的x和由x生成的????我们将x称为属性，将????（x）称为特征变量,将????称为特征地图；

带有特征的最小均方差

我们将推导梯度下降算法来拟合模型θ^Tφ(x),回忆我们训练θ^Tx的最小二乘问题，批梯度下降的公式为：
$\theta:=\theta+\alpha\sum_{r=1}^n(y^{(i)}-h_\theta(x^{(i)}))x^{(i)}$θ:=θ+αr=1∑n​(y(i)−hθ​(x(i)))x(i)

$:=\theta+\alpha\sum_{r=1}^n(y{(i)}-\theta^Tx^{(i)})x^(i)$:=θ+αr=1∑n​(y(i)−θTx(i))x(i)

设????：ℝ^d—>ℝ^p是将属性x映射到ℝ^p维特征????(x)的特征地图，现在我们要训练的是????属于ℝ^p的函数θ^Tφ(x)，我们可以利用????(x⁽ⁱ⁾)替换上面所有出现的x⁽ⁱ⁾:
$\theta:=\theta+\alpha\sum_{i=1}^n(y^{(i)}-\theta^T\phi(x^{(i)}))\phi(x^{(i)})$θ:=θ+αi=1∑n​(y(i)−θTϕ(x(i)))ϕ(x(i))
同样，相应的随机梯度下降更新规则为:
$\theta:=\theta+\alpha(y^{(i)}-\theta^T\phi(x^{(i)}))\phi(x^{(i)})$θ:=θ+α(y(i)−θTϕ(x(i)))ϕ(x(i))

带有核技巧的最小均方：

当特征????(x)是非常高纬度时，梯度下降和随机梯度下降的计算成本将会非常的高昂；假设对于特征地图????我们有更高纬度的输入，即x∈ℝ^d且让????(x)为一个包含小于3阶关于x的单项式的向量，我们就会有：

????(x)的维度是d³阶的。这对于计算而言是一个过长的向量———当d = 1000时，每次更新至少需要计算并存储1000³= 10⁹维向量，这比普通最小二乘更新的更新规则慢10⁶倍。

显然，d³阶的运行时间和内存使用是不可避免的，因为向量????本身的维度就接近于d³阶，即p≈d³，并且我们需要更新并存储每个输入的????并存储，所以我们要介绍核技巧，它可以明显的节省运行时间并且不用明确的存储????；

简单的说，我们假设初始值????=0，并迭代：
$\theta:=\theta+\alpha\sum_{i=1}^n(y^{(i)}-\theta^T\phi(x^{(i)}))\phi(x^{(i)})$θ:=θ+αi=1∑n​(y(i)−θTϕ(x(i)))ϕ(x(i))
观察到在任何时候，????是向量????(x⁽¹⁾)，…，????(x⁽ⁿ⁾)的线性组合。我们可以将其归纳为，在初始时：
$\theta=0=\sum_{i=1}^n0·\phi(x^{(i)})$θ=0=i=1∑n​0⋅ϕ(x(i))
假设在某些点，当????₁，…，????_n∈ℝ时，????可以被表示为：
$$
????=\sum_{i=1}^{n\beta_i\phi(x}{(i)})

\theta:=\theta+\alpha\sum_{i=1}^n(y{(i)}-\theta^T\phi(x{(i)}))\phi(x^{(i)})
$$

$=\sum_{i=1}^n\beta_i\phi(x_{(i)})+\alpha\sum_{i=1}^n(y^{(i)}-\theta^T\phi_{(i)})\phi(x_{i})$=i=1∑n​βi​ϕ(x(i)​)+αi=1∑n​(y(i)−θTϕ(i)​)ϕ(xi​)

$=\sum_{i=1}^n(\underbrace{\beta_i+\alpha(y_{(i)}-\theta^T\phi(x_{(i)})))}_{new\ \ \beta_i}\phi(x^{(i)})$=i=1∑n​(new  βi​βi​+α(y(i)​−θTϕ(x(i)​)))​​ϕ(x(i))

我们的总体思想是通过一组系数????₁，…，????_n隐含表示p维向量????，为此我们导出系数????₁，…，????_n的更新规则，使用上面的公式，我们看到新的β_i取决于旧的β_i:
$\beta_i:=\beta_i+\alpha(y_{(i)}-\theta^T\phi(x^{(i)}))$βi​:=βi​+α(y(i)​−θTϕ(x(i)))
现在我们仍然在公司中存在????，替换????用：
$\theta=\sum_{j=1}^n\beta_j\phi(x^{(j)})$θ=j=1∑n​βj​ϕ(x(j))
我们将会得到：
$\forall i \in\{1,……，n\},\beta_i=\beta_i+\alpha(y^{(i)}-\sum_{j=1}^n\beta_j\phi(x_{(j)})\phi(x^{(i)}))$∀i∈{1,……，n},βi​=βi​+α(y(i)−j=1∑n​βj​ϕ(x(j)​)ϕ(x(i)))
我们通常将????(x^(j))^T????(x⁽ⁱ⁾)写为<????(x^(j)),????(x⁽ⁱ⁾)>表示两个特征向量的内积，将????_i视为????的新的表达形式，这样我们就成功的将批梯度下降算法改成了迭代更新????值的算法。显然对于每次迭代，我们仍需要计算每一对i，j的<????(x^(j)),????(x⁽ⁱ⁾)>，并且都需要消耗复杂度为O§的操作，但是，有两个重要属性可以挽救：

1.我们可以在循环开始之前为所有i，j对预先计算成对内积<????(x^(j)),????(x⁽ⁱ⁾)>。

2.对于我们在前面定义的特征

或者其他有趣的特征，计算<????(x^(j)),????(x⁽ⁱ⁾)>是非常高效的并且不需要结算的????(x⁽ⁱ⁾)特别精确，这是因为：
$<\phi(x),\phi(z)>=1+\sum_{i=1}^dx_iz_i+\sum_{i,z\in\{1，…，d\}}x_ix_jz_iz_j+\sum_{i,j,k\in{1,…，d}}x_ix_jx_kz_iz_jz_k$<ϕ(x),ϕ(z)>=1+i=1∑d​xi​zi​+i,z∈{1，…，d}∑​xi​xj​zi​zj​+i,j,k∈1,…，d∑​xi​xj​xk​zi​zj​zk​

$=1+\sum_{i=1}^d+(\sum_{i=1}^d)^2+(\sum_{i=1}^d)^3$=1+i=1∑d​+(i=1∑d​)2+(i=1∑d​)3

$=1+<x,z>+<x,z>^2+<x,z>^3$=1+<x,z>+<x,z>2+<x,z>3

因此计算<????(x^(j)),????(x⁽ⁱ⁾)>,我们可以首先计算复杂度为O(d)次的<x,z>，然后通过计算结果的常数去计算1+<x,z>+<x,z>²+<x,z>³.

如你所见，这里的向量内积计算是特别的基础，我们定义????×????—>ℝ的映射为Kernel关于特征映射????的函数表示为：
$K(x,z)≙<\phi(x),\phi(z)>$K(x,z)=∧<ϕ(x),ϕ(z)>
为了结束讨论，我们将最终算法记为如下：

1.对于所有i，j∈{1，…，n}使用1+<x,z>+<x,z>²+<x,z>³计算所有K(x,z)≙<????(x),????(z)>的值。

2.循环计算：
$\forall i \in\{1,……，n\},\beta_i=\beta_i+\alpha(y^{(i)}-\sum_{j=1}^n\beta_j\phi(x_{(j)})\phi(x^{(i)}))\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (11)$∀i∈{1,……，n},βi​=βi​+α(y(i)−j=1∑n​βj​ϕ(x(j)​)ϕ(x(i)))                                (11)
或用向量符号表示，令K为n×n矩阵，其中K_ij = K（x^（i），x^（j）），我们有:
$\beta:=\beta+\alpha(\vec y-K\beta)$β:=β+α(y​−Kβ)
利用上面的算法，我们可以每次迭代用时间复杂度O(n)高效的更新????的显式表达????。最后，我们需要证明，显式表示β的足以计算预测θ^Tφ（x）。确实，我们有:
$\theta\phi(x)=\sum_{i=1}^n\beta_i\phi(x^{(i)})\phi(x)=\sum_{i=1}^n\beta_iK(x^{(i)},x)$θϕ(x)=i=1∑n​βi​ϕ(x(i))ϕ(x)=i=1∑n​βi​K(x(i),x)
您可能会意识到，从根本上讲，我们需要了解的有关特征映射φ（·）都封装在相应的内核函数K（·，·）中。我们将在下一部分中对此进行扩展。

内核属性

​ 在最后一个小节中，我们从一个更为详细的特征映射定义开始，它和内核函数k(x,z)≙<????(x),????(z)>相呼应。内核函数的用法非常固定，以至于当内核函数被定义时，可以预测样本x，并且整个训练算法可以被完全的用内核语言写出，而不必退回到特征映射????。

​ 因此，这样引入对另一个内核函数K(·,·)的定义，并且运行算法(11)注意到，在该算法中，在保证特征映射存在的条件下，我们不需要精确得到特征映射????，。

​ 那么，什么样的内核函数才能和特征映射????相关呢？换句话说我们需要什么样的特征映射才能使得对于所有的x，z有K(x,z)=????(x)^T????(z)。

​ 如果我们可以通过给出有效内核函数的精确表征来回答这个问题，那么我们可以将选择特征映射的接口完全更改为选择内核函数K的接口。具体来说，我们可以选择一个函数K，验证其是否满足特征描述（从而存在一个K对应的特征图φ），然后可以运行更新规则（11）。这样做的好处是，我们不必能够计算φ或将其解析地写下来，而只需要知道其存在即可。在讨论了几个内核的具体示例之后，我们将在本小节末尾回答这个问题。

​ 假设x,z∈ℝ^d,并且我们首先将K(·, ·) 假设为：
$K(x,z)=(x^T,z)^2$K(x,z)=(xT,z)2
​ 我们同样可以将它写成这样：
$K(x,z)=(\sum_{r=1}^dx_iz_i)(\sum_{j=1}^d)\\ =\sum_{i=1}^n\sum_{j=1}^dx_ix_jz_iz_j\\ =\sum_{i,j=1}^d(x_ix_j)(z_iz_j)$K(x,z)=(r=1∑d​xi​zi​)(j=1∑d​)=i=1∑n​j=1∑d​xi​xj​zi​zj​=i,j=1∑d​(xi​xj​)(zi​zj​)
​ 因此我们可以看到内核函数 K(x,z) = ⟨φ(x),φ(z)⟩和对应特征映射????（当d=3时）：

​ 再次看到内核方法的高效性，注意到无论如何计算高纬度的????（x）都需要复杂度O(d²)，但是使用 K(x,z)只需要复杂度为O(d)的计算--------和输入的属性维度是线性的。

​ 对于另一个相关的模型，我命定义 K(·,·)为：
$K(x,z)=(x^T+c)^2\\=\sum_{i,j=1}^d(x_ix_j)(z_iz_j)+\sum_{i=1}^d(\sqrt{2c}x_i)(\sqrt{2c}z_z)+c^2$K(x,z)=(xT+c)2=i,j=1∑d​(xi​xj​)(zi​zj​)+i=1∑d​(2c​xi​)(2c​zz​)+c2
​ 这个内核函数对应的特征地图为：（d=3的情况下）

​ 参数c控制着x_i（一阶）和x_ix_j(二阶)的相关权重。

​ 更广泛的说，内核K(x, z) = (x^T z + c)^k对应
$\binom{d+k}{k}$(kd+k​)
的特征空间，相应的，所有从x_i1,x_i2,…,x_ik最高为k阶。然而，尽管说在O(d_k)维度的空间，计算K(x,z)仍然只需要复杂度O(d)的时间，并且因此，我们不需要精确的表达特征向量在非常高的维度上。

内核作为相似矩阵

​ 现在我们来讨论稍有不同的内核，直观上，如果φ(x)和φ(z)特别接近，那么K(x, z) = φ(x)^T φ(z)将会特别的大。相反地，如果φ(x)和φ(z)特别远，几乎到了垂直的程度，那么K(x, z) = φ(x)^T φ(z)将会特别的小，所以，我们可以K(x,z)在某种程度上看成是φ(x)和φ(z)的相似程度。

​ 根据这种直觉，假设对于您正在处理的一些机器学习问题，您想出了一些函数K（x，z），您认为这可以合理地衡量x和z的相似程度。例如，也许您选择了：
$K(x,z)=exp(\frac{||w-z||^2}{2\sigma^2})$K(x,z)=exp(2σ2∣∣w−z∣∣2​)
​ 当x和z特别接近的时候这里的结果接近于1，反之接近于0。是否存在一种特征映射????使得K(x,z) = φ(x)^T φ(z)?回答当然是有的，这种内核叫做高斯内核，并且对应一个无限维度的特征映射????。我们将对函数K需要满足哪些属性进行精确的描述，以便它可以是与某个特征映射φ对应的有效内核函数。

有效内核的必要条件

​ 现在假设K确实是对应于某个特征映射φ的有效内核，我们首先将看到它满足哪些属性。首先，我们先想象由n个点组成的有限集（不一定是训练集）{x⁽¹⁾,…,x⁽ⁿ⁾},然后定义一个n×n的方阵，它的(i,j)输入可以被表示为K_ij=K(x⁽ⁱ⁾,x^(j)).这个矩阵被称为内核矩阵。注意，我们现在已经重复使用K既表示内核函数和内核矩阵，原因是他们显然有相似的关系。

​ 现在如果，K是一个明显的内核，那么K_ij=K(x⁽ⁱ⁾,x^(j))=????(x⁽ⁱ⁾)^T????(x^(j))=????(x^(j))^T????(x⁽ⁱ⁾)=K(x^(j),x⁽ⁱ⁾)=K_ji,并且K必须是对称的。此外，我们让????_k(x)作为向量????(x)的第k个向量，我们注意到，对于任何向量z，我们有
$z^TKz=\sum_{i}\sum_{j}z_iK_{ij}z_j\\=\sum_{i}\sum_{j}z_i\phi(x^{(i)})^T\phi(x^{(j)})z_j\\=\sum_{i}\sum_{j}z_i\sum_{k}\phi_k(x^{(i)})\phi_k(x^{(j)})z_j\\=\sum_{z}\sum_i\sum_jz_i\phi_k(x^{(i)})\phi_k(x^{(j)})z_j\\=\sum_k(\sum_iz_i\phi_k(x^{(i)}))^2\\\ge0$zTKz=i∑​j∑​zi​Kij​zj​=i∑​j∑​zi​ϕ(x(i))Tϕ(x(j))zj​=i∑​j∑​zi​k∑​ϕk​(x(i))ϕk​(x(j))zj​=z∑​i∑​j∑​zi​ϕk​(x(i))ϕk​(x(j))zj​=k∑​(i∑​zi​ϕk​(x(i)))2≥0
​ 倒数第二步利用了，对于a_i=z_i????_k(x⁽ⁱ⁾),
$\sum_{i,j}a_ia_z=(\sum_ia_i)^2$i,j∑​ai​az​=(i∑​ai​)2
​ 因此，我们证明了如果K是一个有效的内核(例如，如果K有对应的特征映射)，那么对应的内核矩阵K∈ℝ^n×n是对称半正定的。

有效内核的充足条件

​ 更一般地说，以上证明不仅是必要条件，而且是充分条件使K成为有效内核（也称为Mercer内核）。以下结果归因于Mercer.

定理（Mercer）

​ 定义K：ℝ^d×ℝ^d—>ℝ.如果K是一个Mercer内核，那么对应内核矩阵的对称半正定是K是一个Mercer内核的充分必要条件。