Multi-parametric solution-path algorithm for instance-weighted support vector machines
Multi-parametric solution-path algorithm for instance-weighted support vector machines
复制标题
DOI：
10.1007/s10994-012-5288-5
复制
发表时间：
2010-09
期刊：
影响因子：
7.5
通讯作者：
Masayuki Karasuyama;Naoyuki Harada;Masashi Sugiyama;I. Takeuchi
中科院分区：
文献类型：
--
作者：
Masayuki Karasuyama;Naoyuki Harada;Masashi Sugiyama;I. Takeuchi
支持向量机 (SVM) 的实例加权变体最近引起了相当大的关注，因为它们在各种机器学习任务中都很有用，例如非平稳数据分析、异方差数据建模、迁移学习、排序学习和转导。这些场景中的一个重要挑战是克服计算瓶颈——实例权重经常动态或自适应地变化，因此必须重复计算加权SVM解。在本文中，我们开发了一种算法，可以有效、准确地更新加权 SVM 解，以适应实例权重的任意变化。从技术上讲，这一贡献可以被视为单个正则化参数的传统解决方案路径算法到多个实例权重参数的扩展。然而，这种扩展引起了一个重大问题，即必须在高维空间中识别断点（解决方案路径转向的位置）。为了促进这一点，我们引入了实例权重的参数化表示。我们还使用临界区域的概念提供权重空间中的几何解释：一个多面体，其中当前的仿射解仍然是最优的。然后我们在解路径与多面体边界的交叉点处找到断点。通过对各种实际应用的广泛实验，我们证明了所提出算法的实用性。
Aninstance-weightedvariant of the support vector machine (SVM) has attracted considerable attention recently since they are useful in various machine learning tasks such as non-stationary data analysis, heteroscedastic data modeling, transfer learning, learning to rank, and transduction. An important challenge in these scenarios is to overcome the computational bottleneck—instance weights often change dynamically or adaptively, and thus the weighted SVM solutions must be repeatedly computed. In this paper, we develop an algorithm that can efficiently and exactly update the weighted SVM solutions for arbitrary change of instance weights. Technically, this contribution can be regarded as an extension of the conventionalsolution-pathalgorithm for a single regularization parameter to multiple instance-weight parameters. However, this extension gives rise to a significant problem thatbreakpoints(at which the solution path turns) have to be identified in high-dimensional space. To facilitate this, we introduce a parametric representation of instance weights. We also provide a geometric interpretation in weight space using a notion ofcritical region: a polyhedron in which the current affine solution remains to be optimal. Then we find breakpoints at intersections of the solution path and boundaries of polyhedrons. Through extensive experiments on various practical applications, we demonstrate the usefulness of the proposed algorithm.