在Sklearn的SVC中,当标签尺寸较大时,为什么训练时间与最大迭代不是严格线性的？

Question

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

似乎最大迭代次数增加,每次迭代所花费的时间比以前少得多.如果我们将label_size更改为2(这意味着每个fit只包含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不是本机操作,它建立在不同的库上,它可能正在使用大量的优化器......等等!

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

然而,在这些微小变化中起作用的一个显着的合理因素是支持向量机中的分解方法.

分类任务的分解方法的思想是将复杂的分类任务分解为几个更简单,更易于管理的子任务,这些子任务可以通过使用现有的归纳方法解决,然后将它们的解决方案连接在一起以解决原始问题.此方法是一个迭代过程,在每次迭代中只更新几个变量.

有关数学方法的更多详细信息,请参阅本文第6.2节"分解方法"..

而且具体而言,SVM 为分解方法实现了两个称为收缩和缓存的技巧.

1. 收缩的想法是?SVM对偶问题的最优解可能包含一些有界元素(即,_αi = 0或C).这些元素可能已经在分解迭代的中间被限制.为了节省训练时间,缩小技术试图识别并移除一些有界元素,从而解决了较小的优化问题.
2. 缓存思想是减少分解方法的计算时间的有效技术,因此根据需要计算元素.我们可以使用可用内存(称为内核缓存)来存储最近使用的矩阵Q _ij的一些排列.然后,可能不需要重新计算一些内核元素.

有关数学方法的更多详细信息,请参阅本文第5节"收缩和缓存".

技术证明:

我重复了你的实验(这就是我要求你的代码遵循相同的方法),使用和不使用收缩和缓存优化.

使用收缩和缓存

该参数的默认值shrinking在sklearn SVC被设定为True,保持如此,因为它是,所产生的输出如下:

绘制它给出:

请注意,在某些时候,时间下降明显反映了收缩和缓存的影响.

不使用收缩和缓存

使用相同的精确方法,但这一次,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相关性

结论:

如果不使用收缩和缓存(稍后通过缓存更新),线性度会提高,尽管它不是100%线性的,但如果考虑到Scikit-Learn在内部使用libsvm库来处理所有计算.并且这个库使用C和Cython进行包装,你对你maximum iterations和/ 之间关系的'线性'的定义有更高的容忍度time.此外,这里有一个很酷的讨论,为什么算法每次都不能提供完全相同的精确确定的运行时间.

如果你绘制间隔时间,那对你来说会更清楚,所以你可以清楚地看到滴在多个地方突然发生的突然变化.

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

重要更新

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

但我错过的是以下内容:

我在谈论收缩和缓存,但我错过了后来的缓存参数,默认设置为200 MB.

多次重复相同的模拟并将cache_size参数设置为非常小的数字(因为零是不可接受的并且抛出错误),此外shrinking=False,在和之间产生了非常接近的线性模式:max_itertime

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包装的所有计算.