"Машинное обучение"
Временная и пространственная сложность моделей машинного обучения
- Сложность обучения модели машинного обучения по времени - время, затраченное на обучение модели.
- Временная сложность теста модели машинного обучения - время, необходимое для прогнозирования выходных данных для заданной точки входного запроса.
Сложность времени - важный аспект, который нужно знать, когда кому-то нужна модель с низкой задержкой. Давайте углубимся в детали того, сколько времени и места требуется широкому спектру моделей для прогнозирования результатов.
«Предполагая, что данные обучения содержат n точек с d измерениями»
1) K-Ближайшие соседи:
Учитывая точку запроса (xq), K-NN выполняет следующие шаги, чтобы предсказать результат (yq). Для каждого xi в обучающем наборе вычислите расстояние для xi и xq.
Вычисление расстояния для одной точки занимает o (d) времени, так как мы вычисляем для каждого xi при обучении, это занимает o (nd)
Затем сохраните наименьшие k расстояний в списке и проголосуйте большинством за K очков, что потребовало o (1). Поскольку нам нужны данные всего поезда во время выполнения, сложность пространства будет окончательно отключена для KNN.
Сложность выполнения = O (nd)
Сложность пространства = O (nd)
Для KNN нет временной сложности поездов
2) Наивный байесовский:
При заданной точке запроса (xq) наивному байесовскому алгоритму нужны только априорные вероятности и вероятности правдоподобия для прогнозирования выходных данных (yq), что позволяет использовать модель в приложениях с низкой задержкой.
Итак, на этапе обучения Наивного Байеса он вычисляет все вероятности правдоподобия и априорную вероятность, для чего требуется временная сложность O (ndc), где c = количество классов, а пространственная сложность = O (dc)
Сложность времени обучения = O (n * d * c)
Сложность выполнения = O (d * c)
Сложность пространства = O (d * c)
3) Логистическая регрессия:
Для точки запроса (xq) логистической регрессии нужен только весовой вектор d-измерения (W).
yq = сигмоид (W.xq), что занимает O (d) времени, а необходимое пространство - O (d)
Для обучающей логистической регрессии проблема оптимизации должна быть решена с использованием стохастического градиентного спуска, который требует O (nd).
Логистическая регрессия применима к приложениям с малой задержкой и эффективным использованием памяти во время выполнения.
Сложность времени обучения = O (n * d)
Сложность выполнения = O (d)
Сложность пространства = O (d)
4) Дерево решений:
Сложность времени обучения = O (n * log (n) * d)
Сложность пространства = O (p), где p = количество узлов в дереве
Сложность времени выполнения = O (k), где k = глубина дерева
почему O (n * log (n) * d)?
Допустим, в наборе данных есть n точек d объектов, и все функции являются числовыми.
- Поскольку числовой объект необходимо отсортировать, для сортировки одного объекта требуется O (n * lgn)
- Тогда сортировка всех d объектов займет O (n * lgn * d)
- Теперь нам нужно рассчитать информационный прирост на каждом пороге. Для одной функции требуется O (n), а для d функций - O (n * d).
- Сложность времени O (n * lgn * d) + O (nd)
- Из-за нотации Big O O (nlogn * d) + O (n * d) будет почти равно O (nlogn * d).
Сложность рабочего пространства = o (кол-во узлов).
Во время выполнения для DT для принятия решения требуются только условия if-else
, поэтому сложность пространства является разумной.
5) Агрегация начальной загрузки с деревьями решений (или) случайным лесом:
Поскольку случайный лес формируется из k базовых учащихся (деревья решений) для точки запроса xq для прогнозирования yq, мы получаем k выходов, а затем путем агрегирования (основной вес или среднее / медианное значение) применяется к выходам k базовых учащихся (DT) для генерировать yq.
для случайного леса с m деревьями решений
Сложность времени обучения = O (n * log (n) * d * m)
Сложность пространства = O (p * m)
Сложность выполнения = O (k * m)
Во время обучения случайный лес можно распараллелить, поскольку каждый базовый ученик может обучаться на разных ядрах компьютера.
6) Дерево принятия решений по градиентному усилению:
Сложность времени обучения = O (n * log (n) * d * m)
Сложность пространства = O (p * m + gamma), которую необходимо умножить на m моделей.
Сложность выполнения = O (k * m)
7) SVM:
Сложность времени обучения = O (n²)
Сложность пространства = О
Сложность времени выполнения = O (s * d)
s = количество поддерживающих векторов, d = размерность данных
