Почему в SVC от Sklearn время обучения не строго линейно относительно максимальной итерации при большом размере метки?

Что ж, может быть множество причин для этого "очень небольшого изменения". 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
        )

Получил следующий вывод:

График дает:

Обратите внимание, что, в отличие от предыдущего графика, в какой-то момент нет заметного спада во времени, это просто очень крошечные колебания по всему графику.

Сравнение корреляций Пирсона

В заключении:

Без использования сжатия и кеширования (обновлено позже с кешированием) линейность улучшилась, хотя она не на 100% линейна, но если принять во внимание, что Scikit-Learn внутренне использует libsvm библиотека для обработки всех вычислений. И эта библиотека обернута с использованием C и Cython, вы будете более терпимо относиться к вашему определению «линейной» связи между maximum iterations и time. Кроме того, здесь - это отличное обсуждение того, почему алгоритмы не могут каждый раз давать одно и то же точное определенное время выполнения.

И это будет для вас еще яснее, если вы нанесете на график временные интервалы, чтобы вы могли ясно увидеть, как внезапно происходит резкое падение более чем в одном месте.

При этом он сохраняет практически тот же поток без использования уловок оптимизации.

Важное обновление

Оказалось, что вышеупомянутая причина этой проблемы (например, сжатие и кеширование) верна, или, точнее, это очень важный фактор этого явления.

Но я упустил следующее:

Я говорил о сжатии и кешировании, но пропустил более поздний параметр для кеширования, который по умолчанию установлен на 200 МБ.

Повторение одного и того же моделирования более одного раза и установка параметра cache_size на очень маленькое число (потому что ноль недопустим и вызывает ошибку) в дополнение к shrinking=False, привело к чрезвычайно близкому -to линейный узор между 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.