1.2 The Basic Idea
Suppose we are given training data
X times; R, where X denotes the space of the input patterns (e.g. X = Rd). These might be, for instance, exchange rates for some currency measured at subsequent days together with corresponding econometric indicators. In ε-SV regression [Vapnik, 1995], our goal is to find a function f(x) that has at most ε deviation from the actually obtained targets yi for all the training data, and at the same time is as flat as possible. In other words, we do not care about errors as long as they are less than ε, but will not accept any deviation larger than this. This may be important if you want to be sure not to lose more than ε money when dealing with exchange rates, for instance.
For pedagogical reasons, we begin by describing the case of linear functions f, taking the form
with w isin; X,b isin; R (1)
wheredenotes the dot product in X. Flatness in the case of (1) means that one seeks a small w. One way to ensure this is to minimize the norm,. We can write this problem as a convex optimization problem:
minimize
(2)
subject to
The tacit assumption in (2) was that such a function f actually exists that approximates all pairs (xi,yi) with ε precision, or in other words, that the convex optimization problem is feasible. Sometimes, however, this may not be the case, or we also may want to allow for some errors. Analogously to the “soft margin” loss function [Bennett and Mangasarian, 1992] which was adapted to SV machines by Cortes and Vapnik [1995], one can introduce slack variables xi;i,xi;ilowast; to cope with otherwise infeasible constraints of the optimization problem (2). Hence we arrive at the formulation stated in [Vapnik, 1995].
minimize
(3)
subject to
The constant C gt; 0 determines the trade-off between the flatness of f and the amount up to which deviations larger than ε are tolerated. This corresponds to dealing with a so called ε–insensitive loss function |xi;|ε described by
|xi;|ε :=| | minus; | | le; (4) 0 if xi; ε
xi; ε otherwise.
Fig. 1 depicts the situation graphically. Only the points outside the shaded region contribute to the cost insofar, as the deviations are penalized in a linear fashion. It turns out that
Figure 1: The soft margin loss setting for a linear SVM.
in most cases the optimization problem (3) can be solved more easily in its dual formulation.4 Moreover, as we will see in Sec. 2, the dual formulation provides the key for extending SV machine to nonlinear functions. Hence we will use a standard dualization method utilizing Lagrange multipliers, as described in e.g. [Fletcher, 1989].
1.3 Dual Problem and Quadratic Programms
The key idea is to construct a Lagrange function from the objective function (it will be called the primal objective function in the rest of this article) and the corresponding constraints, by introducing a dual set of variables. It can be shown that this function has a saddle point with respect to the primal and dual variables at the solution. For details see e.g. [Mangasarian, 1969, McCormick, 1983, Vanderbei, 1997] and the explanations in section 5.2. We proceed as follows:
Here L is the Lagrangian and eta;i,eta;ilowast;,alpha;i,alpha;lowast;i are Lagrange multipliers. Hence the dual variables in (5) have to satisfy positivity constraints, i.e.
alpha;(ilowast;),eta;i(lowast;) ge; 0. (6)
Note that by alpha;(ilowast;), we refer to alpha;i and alpha;lowast;i .
It follows from the saddle point condition that the partial derivatives of L with respect to the primal variables (w,b,xi;i,xi;ilowast;) have to vanish for optimality.
(7)
(8)
(9)
Substituting (7), (8), and (9) into (5) yields the dual optimization problem.
maximize
(10)
subject to
In deriving (10) we already eliminated the dual variables eta;i,eta;ilowast; through condition (9) which can be reformulated as
. Eq. (8) can be rewritten as follows
, thus
This is the so-called Support Vector expansion, i.e. w can be completely described as a linear combination of the training patterns xi. In a sense, the complexity of a functionrsquo;s representation by SVs is independent of the dimensionality of the input space X, and depends only on the number of SVs.
Moreover, note that the complete algorithm can be described in terms of dot products between the data. Even when evaluating f(x) we need not compute w explicitly. These observations will come in handy for the formulation of a nonlinear extension.
1.4 Computing b
So far we neglected the issue of computing b. The latter can be done by exploiting the so called Karush–Kuhn–Tucker (KKT) conditions [Karush, 1939, Kuhn and Tucker, 1951]. These state that at the point of the solution the product between dual variables and constraints has to vanish.
(12)
and(13)
This allows us to make several useful conclusions. Firstly only samples (xi,yi) with corresponding alpha;(ilowast;) = C lie outside the ε–insensitiv
剩余内容已隐藏，支付完成后下载完整资料
1.2 基本思想
假设我们有训练数据 X times; R，其中X表示输入模式的空间（例如X=Rd）。例如，这些可能是某些货币在随后几天的汇率以及相应的经济计量指标。在ε-SV回归[Vapnik，1995]中，我们的目标是找到一个函数f（x），对于所有的训练数据，该函数与实际获得的目标yi的偏差最大，同时尽可能平坦。换言之，只要误差小于ε，我们就不关心误差，但不接受任何大于此的误差。例如，如果你想确保在处理汇率时损失不超过ε货币，这一点可能很重要。
出于教学的原因，我们首先描述线性函数f的情况，形式如下：
，有wisin;X，bisin;R（1）
其中表示X中的点积。平面度在（1）的情况下表示寻求小w。确保这一点的一种方法是最小化标准。我们可以把这个问题写成一个凸优化问题：
最小化
(2)
满足于
（2）式的默认假设是这样的函数f实际上存在，它以ε精度逼近所有对（xi，yi），或者换句话说，凸优化问题是可行的。然而，有时情况可能并非如此，或者我们也可能希望允许出现一些错误。类似于Cortes和Vapnik[1995]对SV机器进行调整的“软边际”损失函数[Bennett和Mangasarian，1992]，可以引入松弛变量zeta;i，zeta;i*，以处理优化问题（2）中其他不可行的约束。因此，我们得出了[Vapnik，1995]中所述的公式。
最小化
(3)
满足于
常数Cgt;0决定了f的平面度与允许偏差大于ε的量之间的折衷。这对应于处理所谓的ε-不灵敏损失函数
图1以图形方式描绘了情况。只有阴影区域以外的点才有助于成本，因为偏差是以线性方式惩罚的。结果表明，在大多数情况下，优化问题（3）可以用它的对偶公式更容易地解决。4此外，我们将在第4节中看到。2.对偶公式为支持向量机扩展到非线性函数提供了关键。因此，我们将使用拉格朗日乘子的标准二元化方法，如[Fletcher，1989]所述。
图1：线性支持向量机的软边际损失设置
1.3对偶问题与二次规划
其核心思想是通过引入一个对偶变量集，从目标函数（本文后面将称之为原始目标函数）和相应的约束条件中构造拉格朗日函数。结果表明，该函数对解的原、对偶变量有一个鞍点。有关详细信息，请参见[Mangasarian，1969，McCormick，1983，Vanderbei，1997]和第5.2节中的解释。我们进行如下操作：
这里L是拉格朗日方程，eta;i，eta;i，alpha;i，alpha;i是拉格朗日乘子。因此（5）中的对偶变量必须满足正性约束，即 alpha;(ilowast;),eta;i(lowast;) ge; 0. (6)
注意，在alpha;（i）*中，我们指的是alpha;i和alpha;*i。
从鞍点条件出发，L对原始变量（w，b，zeta;i，zeta;ilowast;）的偏导数必须为最优性而消失。
将（7），（8）和（9）代入（5）得到对偶优化问题。
在推导（10）时，我们已经通过条件（9）消除了双变量eta;i，eta;ilowast;，条件（9）可以重新表述为等式（8）可以被重写为这就是所谓的支持向量展开，即W可以完全描述为线性组合的训练模式席。从某种意义上说，SVs表示函数的复杂度与输入空间X的维数无关，只取决于SVs的个数。
此外，请注意，完整的算法可以用数据之间的点积来描述。即使在计算f（x）时，我们也不需要显式地计算w。这些观测结果将有助于描述非线性扩张。
1.4计算b
到目前为止，我们忽略了计算b的问题，后者可以通过利用所谓的Karush-Kuhn-Tucker（KKT）条件来实现[Karush，1939，Kuhn和Tucker，1951]。这些状态表明在解的点上，对偶变量和约束之间的乘积必须消失并且这使我们能够得出几个有用的结论。首先，只有相应的alpha;（i）＝C的样本（席，彝）位于ε-不敏感管的外部。其次alpha;ialpha;*i=0，即不可能存在同时为非零的一组对偶变量alpha;i，alpha;*i。这让我们可以得出结论结合对alpha;*i的类似分析，我们有如果某个alpha;（ilowast;）isin;（0，C），则不等式变为等式。另见[Keerthi等人，2001]了解选择b的进一步方法。
另一种计算b的方法将在内部点优化的背景下讨论（参见第5） 是的。结果发现b是优化过程的副产品。进一步的考虑应推迟到相应的章节。另见[Keerthi等人，1999]了解计算常数偏移量的进一步方法。
最后要注意SV展开的稀疏性。从（12）中，只有对于，拉格朗日乘子可以是非零的，或者换句话说，对于ε-管内的所有样本（即图1中的阴影区域）alpha;i，i i i消失：对于，（12）中的第二因子是非零，因此必须为零，使得KKT条件满足。因此，我们有一个稀疏的W的XI（即我们不需要所有xi描述W）。带有非变异系数的例子称为支持向量。
2 核函数
2.1 预处理非线性
下一步是使SV算法非线性化。例如，可以通过简单地将训练模式xi预处理由映射进入某些特征空间F，如[Aielman等人，1964，尼尔森，1965 ]中所描述的，然后应用标准SV回归算法。让我们简单地看一下[Vapnik，1995]中给出的一个例子。
例1（二维空间）考虑映射Phi;：和。在这种情况下，下标是指xisin;R2的分量。对线性SV机器的预处理特征进行训练，得到一个二次函数。
虽然这种方法在上面的特定示例中似乎是合理的，但是对于高阶和高维的多项式特征，由于阶p的不同单项特征的数目是，其中d＝dim（X），因此在计算上很容易变得不可行。OCR任务的典型值（具有良好的性能）[Scholkopf等人，1995，Scholkopf等人，1997，Vapnik, 1995]为p = 7,d = 28 · 28 = 784，对应于3.7*10的16次方。
2.2通过内核的隐式映射
显然这种方法是不可行的，我们必须找到一种计算成本更低的方法。关键的观察结果[Boser等人，1992年]是，对于例1的特征图，我们有如前一节所述，SV算法只依赖于模式席之间的点积。因此，只需知道而不是明确地知道Phi;，这就允许我们重申SV优化问题：同样，f（11）的扩展可以写成与线性情况不同的是，不再显式地给出w。还要注意，在非线性设置中，优化问题对应于在特征空间而不是输入空间中找到最平坦函数。
2.3内核条件
现在出现的问题是，哪些函数对应于某个特征空间F中的点积。下面的定理描述了这些函数（定义在X上）。
定理2（Mercer[1909]）假设，使得积分算子为正的（这里mu;表示X上的测量值，mu;（X）有限且supp（mu;）=X）。设Psi;jisin;L2（X）为与特征值相关联的Tk的特征函数，并使之正规化 其中级数几乎所有都是绝对一致收敛的。不太正式地说，这个定理意味着如果那么我们可以在一些特征空间中写为点积。根据这个条件，我们可以得出一些关于核组成的简单规则，这些规则也满足Mercer的条件[Schouml;lkopf等人，1999a]。在下面我们将调用这样的函数k容许SV核。
推论3（核的正线性组合）由k1，k2可容许的SV核和c1，c2ge;0表示是一个可容许的核。这直接从（21）出发，借助于积分的线性。更一般地，可以证明可容许核集形成凸锥，在点收敛Berg等人的拓扑中是闭的。[1984年]。
推论4（核的积分）设为Xtimes;X上的对称函数，使得存在。那么k是一个可容许的SV核。
这可以直接从（21）和（23）通过重新排列积分顺序来表示。我们现在给出了平移不变核的一个充分必要条件。
定理5（核的乘积）用k1和k2表示
是一个可容许的核。这可以通过将Mercer定理的“展开部分”应用于核k1和k2，并观察到两两求和中的每个项
在检查时产生正系数（21）。
定理6（Smola，Scholkopf，and Muller[1998c]）平移不变核是可容许的SV核，当且仅当傅里叶变换是非负的。我们将在第7节中对这个定理给出一个证明和一些额外的解释。它遵循插值理论[Michelli，1986]和正则化网络理论[Girosi等人，1993]。对于点积类型的内核，即，存在充分的条件成立
定理7（Burges[1999]）点积型的任何核都必须满足k（zeta;）ge;0，part;zeta;k（zeta;）ge;0和part;zeta;k（zeta;） zeta;part;zeta;2k（zeta;）ge;0（26）为了成为一个可容许的SV核，任何zeta;ge;0。注意，定理7中的条件只是必要的，而不是充分的。上述规则对于从业者来说是有用的工具，既可以用来检查内核是否是可接受的SV内核，也可以用来实际构造新的内核。一般情况由以下定理给出。
定理8（Schoenberg[1942]）点积型核无限维Hilbert上的定义
空间，具有幂级数扩展当且仅当所有的ange;0时才成立。
一个稍弱的条件适用于有限维空间。更多详情见[Berg等人，1984年，Smola等人，2001年]。
2.4示例
在[Scholkopf等人，1998b]中，通过显式地计算映射，证明了具有pisin;N的齐次多项式核k和是合适的SV核（参见Poggio[1975]）。根据这一观察，我们可以立即得出结论[Boser等人，1992年，Vapnik，1995年]，这种类型的核即pisin;N，cge;0的非齐次多项式核也是可容许的：将k重写为齐次核之和并应用推论3。另一个看起来很吸引人的内核，是双曲正切核，因为它类似于神经网络通过应用定理8，可以检查这个核是否真的满足Mercer的条件[ovalo，2000]。奇怪的是，内核已经在实践中得到了成功的应用；参见Schouml;lkopf[1997]对其原因进行了讨论。
翻译不变量核非常普遍。在[Aizerman等人，1964年，Michelli，1986年，Boser等人，1992]中表明是一个可容许的SV核。此外，我们可以证明[Smola，1996，Vapnik等人，1997]，即（1X表示集合X上的指示符函数和otimes;卷积运算）
由单位逆的2n 1卷积定义的2n 1阶B样条也是可容许的。我们将把进一步的考虑推迟到第7节，在这里将更详细地指出与正则化算子的联系。
3成本函数
到目前为止，用于回归的SV算法似乎相当奇怪，几乎与其他现有的函数估计方法（例如[Huber，1981，Stone，1985，Ha–rdle，1990，haste and Tibshirani，1990，Wahba，1990]）没有关系。然而，一旦转换成一个更标准的数学符号，我们将观察到与先前工作的联系。为了简单起见，我们将再次只考虑线性情况，因为使用前一章中描述的核方法，对非线性情况的扩展是直接的。
3.1风险功能
让我们先回到第1.2节的情况。在那里，我们有一些训练数据X：=
我们现在假设，这个训练集是从某个概率分布P（x，y）中画出的iid（独立且相同分布）。我们的目标是找到一个函数，使期望风险最小化（cf.[Vapnik，1982]）
（c（x，y，f（x））表示基于经验数据x决定如何惩罚估计误差的成本函数。鉴于我们不知道P（x，y）的分布，我们只能使用x来估计最小化R[f]的函数f。一种可能的近似方法是用经验估计代替积分，得到所谓的经验风险函数第一个尝试是找到一些函数类H的经验风险最小化f0：=argminfisin;H Remp[f]，然而，如果H非常丰富，即它的“容量”非常高，例如在处理非常高维空间中的少量数据时，这可能不是一个好主意，因为它会导致过度拟合，从而导致不好的泛化特性。因此，在SV案例中，应增加一个容量控制项，这将导致正则化风险函数[Tikhonov和Arsenin，1977，Morozov，1984，Vapnik，1982] 其中，lambda;gt;0是所谓的正则化常数。许多算法，如正则化网络[Girosi等人，1993]或具有权重衰减网络的神经网络[例如Bishop，1995]最小化类似于（35）的表达式。
3.2最大似然和密度模型
如第1.2节所述，SV情况下的标准设置为ε-不敏感损耗
很容易证明，在特定损失函数为（36）的情况下，最小化（35）等于最小化（3），唯一的区别是。
损失函数如pgt;1的| y-f（x）| pε可能不可取，因为超线性增加导致估计量的稳健性丧失[Huber，1981]：在这些情况下，成本函数的导数无界增长。当plt;1时，c变为非凸。
对于c（x，y，f（x））=（yminus;f（x））2的情况，我们恢复了最小均方拟合方法，与标准SV损失函数不同，该方法导致矩阵求逆，而不是二次规划问题。
问题是（35）中应该使用哪个成本函数。一方面，我们希望避免一个非常复杂的函数c，因为这可能导致困难的优化问题。另一方面，我们应该使用最适合问题的特定成本函数。此外，在假设样本由底层函数依赖加加性噪声产生时，即密度为p（ZEI）的Yi＝FTrE（席） 席I i，然后在最大似然意义下，最优代价函数为
这可以看出如下。估计的可能性
对于附加噪声和iid数据
最大化相当于最小化。通过使用（37）我们得到然而，这种推理产生的成本函数可能是非凸的。在这种情况下，必须找到一个凸代理才能有效地处理这种情况（即找到相应优化问题的有效实现）。
另一方面，如果我们从现实世界的问题中得到一个特定的成本函数，我们应该尽可能找到一个与该成本函数最接近的代理，因为它是性能wrt。这个特殊的成本函数最终是重要的。
表1概述了一些常见的密度模型以及由（37）。我们将在下面对c（x，y，f（x））施加的唯一要求是，对于固定的x和y，我们在f（x）中有凸性。这一要求的提出，是因为我们要确保最小优化问题的存在性和唯一性（对于严格凸性）[Fletcher，1989]。
3.3解方程
为了简单起见，我们将另外假设c是对称的，并且在
剩余内容已隐藏，支付完成后下载完整资料
资料编号：[410095]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
