python - 在 Sklearn 的 SVC 中，当标签大小很大时，为什么训练时间与最大迭代不严格线性？

Question

我做了一个分析，试图查看 SVC 中训练时间和最大迭代之间的关系。我使用的数据是一些随机生成的数字，我根据 SVC 拟合的 max_iter 绘制了训练时间。我检查了日志，每个二进制分类器都达到了 max_iter(我输出了所有控制台日志，这些日志显示了每个二进制分类器的详细警告并对其进行了计数)。但是，我假设训练时间与迭代严格线性，但实际上，在训练数据有很多标签的情况下，例如说 40，那么情节不显示它是线性的。


似乎随着最大迭代次数的增加，每次迭代所需的时间比以前略少。而如果我们将 label_size 更改为 2(这意味着每个拟合仅包含 1 个二元分类器)，则该线是直的。



是什么导致这种情况发生？

这是我的源代码:

# -*- coding: utf-8 -*-
import numpy as np
from sklearn.svm import SVC
import time
import pandas as pd


def main(row_size, label_size):
    np.random.seed(2019)
    y = np.array([i for i in range(label_size) for j in range(row_size
                 / label_size)])
    if len(y) < row_size:
        y = np.append(y, [y[-1]] * (row_size - len(y)))
    X = np.random.rand(row_size, 300)
    print X.shape, y.shape
    return (X, y)


def train_svm(X, y, max_iter):
    best_params = {'C': 1}
    clf = SVC(
        C=best_params['C'],
        kernel=str('linear'),
        probability=False,
        class_weight='balanced',
        max_iter=max_iter,
        random_state=2018,
        verbose=True,
        )
    start = time.time()
    clf.fit(X, y)
    end = time.time()
    return end - start


if __name__ == '__main__':
    row_size = 20000
    m_iter = range(10, 401, 20)
    label_size = [40]
    data = {
        'label_size': [],
        'max_iter': [],
        'row_size': [],
        'time': [],
        }
    for it in m_iter:
        for l in label_size:
            (X, y) = main(row_size, l)
            t = train_svm(X, y, max_iter=it)
            data['label_size'].append(l)
            data['max_iter'].append(it)
            data['row_size'].append(row_size)
            data['time'].append(t)
            df = pd.DataFrame(data)
            df.to_csv('svc_iter.csv', index=None)

Answer 1

好吧，“ 非常微小的变化 ”可能有很多原因。 Scikit-Learn 不是 native 运行的，它是建立在不同的库上的，它可能会使用大量的优化器……等等!

此外，你的第一张图是 非常接近线性!

尽管如此，促成这些微小变化的一个重要的合理因素是 分解方法在支持向量机中。

分类任务分解方法的思想是将一个复杂的分类任务分解为几个更简单、更易于管理的子任务，这些子任务可以使用现有的归纳方法解决，然后将它们的解决方案结合在一起以解决原始问题。
该方法是一个迭代过程，在每次迭代中只有少数变量被更新。

有关数学方法的更多详细信息，请参阅 this paper, section 6.2 The Decomposition Method. .

此外，具体来说，SVM 实现了两个技巧，称为 收缩和 缓存 为分解方法。

收缩思想是一个最优解 α SVM 对偶问题可能包含一些有界元素(即 αi = 0 或 C)。这些元素可能在分解迭代的中间已经有界。为了节省训练时间，收缩技术尝试识别并移除一些有界元素，因此解决了一个较小的优化问题。

缓存思想是减少分解方法计算时间的有效技术，因此根据需要计算元素。我们可以使用可用内存(称为内核缓存)来存储一些最近使用的 permutation of the matrix Q_ij .然后，一些内核元素可能不需要重新计算。

有关数学方法的更多详细信息，请参阅 this paper, section 5 Shrinking and Caching.

技术证明:

我重复了你的实验(这就是我要求你的代码遵循完全相同的方法)， 与 和 没有 使用收缩和缓存优​​化。

使用收缩和缓存

参数默认值 shrinking在 sklearn SVC设置为 True ，保持原样，产生以下输出:



绘制它给出:



请注意，在某些时候，时间显着下降，反射(reflect)了收缩和缓存的效果。

不使用收缩和缓存

使用完全相同的方法，但这次设置参数 shrinking明确给 False如下:

 clf = SVC(
        C=best_params['C'],
        kernel=str('linear'),
        probability=False,
        class_weight='balanced',
        max_iter=max_iter,
        random_state=2018,
        verbose=True,
        shrinking=False
        )

产生了以下输出:



绘制它给出:



请注意，与之前的情节不同的是，在某些时候没有明显的时间下降，而只是整个情节的非常微小的波动。

比较 Pearson 相关性



综上所述:

不使用Shrinking and Caching(稍后更新缓存)，线性度有所提高，虽然不是100%线性，但如果考虑到Scikit-Learn内部使用 libsvm库来处理所有计算。这个库是用 包装的C 和 Cython ，您对 maximum iterations 之间关系的“线性”的定义会有更高的容忍度。和 time .另外， here是关于为什么算法可能不会每次都给出完全相同的精确确定运行时间的很酷的讨论。

如果你绘制间隔时间，那对你来说会更清楚，这样你就可以清楚地看到下降是如何在多个地方突然发生的。



虽然它在不使用优化技巧的情况下保持几乎相同的流程。



重要更新

事实证明，这个问题的上述原因(即收缩和缓存)是正确的，或者更准确地说，它是该现象的一个非常重要的因素。

但我错过的是以下内容:

我说的是收缩和缓存，但我错过了后面的缓存参数，默认设置为 200 MB。

多次重复相同的模拟并设置 cache_size除了 shrinking=False 之外，参数为一个非常小的数字(因为零是 Not Acceptable 并且会引发错误) ，导致 max_iter 之间非常接近线性模式和 time :

clf = SVC(
        C=best_params['C'],
        kernel=str('linear'),
        probability=False,
        class_weight='balanced',
        max_iter=max_iter,
        random_state=2018,
        verbose=False,
        shrinking=False,
        cache_size = 0.000000001
        )

顺便说一句，你不需要设置 verbose=True ，您可以通过 ConvergenceWarning 检查它是否达到了最大迭代次数。 ，因此您可以将这些警告重定向到一个文件，并且跟踪起来会容易百万倍，只需添加以下代码:

import warnings, sys
def customwarn(message, category, filename, lineno, file=None, line=None):
    with open('warnings.txt', 'a') as the_file:
        the_file.write(warnings.formatwarning(message, category, filename, lineno))
warnings.showwarning = customwarn

此外，您不需要在每次迭代后重新生成数据集，因此将其从循环中取出，如下所示:

(X, y) = main(row_size, 40)
    for it in m_iter:
        ....
        ....

定论

随着迭代次数的增加，来自 SVM 中分解方法的收缩和缓存技巧在改善执行时间方面发挥着重要作用。此外，还有其他一些小玩家可能对此事有所贡献，例如 libsvm 的内部使用。库来处理使用 C 和 Cython 包装的所有计算。