xbe.at

Machine learning / Fundamentals and overview

The time complexity of 10 popular ML algorithms

7 min read, 15 sections

Contents
  1. Time Complexity of Popular ML Algorithms
  2. Linear Regression
  3. Logistic Regression
  4. Decision Trees
  5. Random Forests
  6. Support Vector Machines (SVM)
  7. K-Nearest Neighbors (KNN)
  8. K-Means Clustering
  9. Principal Component Analysis (PCA)
  10. Naive Bayes
  11. Neural Networks
  12. Real-Life Example - Image Classification
  13. Real-Life Example - Text Classification
  14. Choosing the Right Algorithm
  15. Additional Resources

Time Complexity of Popular ML Algorithms

The time complexity of machine learning algorithms is crucial for understanding their efficiency and scalability. This presentation will cover the time complexity of 10 popular ML algorithms, providing insights into their performance characteristics and practical applications.

import numpy as np
import matplotlib.pyplot as plt

algorithms = ['Linear Regression', 'Logistic Regression', 'Decision Trees', 
              'Random Forests', 'SVM', 'KNN', 'K-Means', 'PCA', 'Naive Bayes', 'Neural Networks']
complexities = ['O(nd)', 'O(nd)', 'O(nd log n)', 'O(ntd log n)', 'O(n^2d)', 
                'O(nd)', 'O(ndk)', 'O(d^3)', 'O(nd)', 'O(nde)']

plt.figure(figsize=(12, 6))
plt.barh(algorithms, range(len(algorithms)), align='center')
plt.yticks(range(len(algorithms)), algorithms)
plt.xlabel('Relative Complexity')
plt.title('Time Complexity of Popular ML Algorithms')

for i, c in enumerate(complexities):
    plt.text(0.5, i, c, va='center')

plt.tight_layout()
plt.show()

Linear Regression

Linear Regression is a fundamental algorithm with a time complexity of O(nd), where n is the number of samples and d is the number of features. This efficiency makes it suitable for large datasets with many features.

import numpy as np
from sklearn.linear_model import LinearRegression
import time

# Generate sample data
n, d = 10000, 100
X = np.random.rand(n, d)
y = np.random.rand(n)

# Measure time for fitting
start_time = time.time()
model = LinearRegression().fit(X, y)
end_time = time.time()

print(f"Time taken for {n} samples and {d} features: {end_time - start_time:.4f} seconds")

Logistic Regression

Logistic Regression, despite its name, is used for classification tasks. Its time complexity is also O(nd), making it efficient for binary and multiclass classification problems with large datasets.

from sklearn.linear_model import LogisticRegression
import numpy as np
import time

# Generate sample data
n, d = 10000, 100
X = np.random.rand(n, d)
y = np.random.randint(0, 2, n)

# Measure time for fitting
start_time = time.time()
model = LogisticRegression().fit(X, y)
end_time = time.time()

print(f"Time taken for {n} samples and {d} features: {end_time - start_time:.4f} seconds")

Decision Trees

Decision Trees have a time complexity of O(nd log n) for training. This makes them relatively efficient for medium-sized datasets but may become slower for very large datasets.

from sklearn.tree import DecisionTreeClassifier
import numpy as np
import time

# Generate sample data
n, d = 10000, 100
X = np.random.rand(n, d)
y = np.random.randint(0, 2, n)

# Measure time for fitting
start_time = time.time()
model = DecisionTreeClassifier().fit(X, y)
end_time = time.time()

print(f"Time taken for {n} samples and {d} features: {end_time - start_time:.4f} seconds")

Random Forests

Random Forests, an ensemble of Decision Trees, have a time complexity of O(ntd log n), where t is the number of trees. While more computationally intensive than a single Decision Tree, they often provide better performance and are parallelizable.

from sklearn.ensemble import RandomForestClassifier
import numpy as np
import time

# Generate sample data
n, d = 10000, 100
X = np.random.rand(n, d)
y = np.random.randint(0, 2, n)

# Measure time for fitting
start_time = time.time()
model = RandomForestClassifier(n_estimators=100).fit(X, y)
end_time = time.time()

print(f"Time taken for {n} samples and {d} features: {end_time - start_time:.4f} seconds")

Support Vector Machines (SVM)

SVMs have a time complexity of O(n^2d) to O(n^3d) depending on the kernel used. This quadratic to cubic relationship with the number of samples makes SVMs challenging to use with large datasets.

from sklearn.svm import SVC
import numpy as np
import time

# Generate sample data
n, d = 1000, 100  # Reduced sample size due to SVM's complexity
X = np.random.rand(n, d)
y = np.random.randint(0, 2, n)

# Measure time for fitting
start_time = time.time()
model = SVC().fit(X, y)
end_time = time.time()

print(f"Time taken for {n} samples and {d} features: {end_time - start_time:.4f} seconds")

K-Nearest Neighbors (KNN)

KNN has a training complexity of O(nd) (essentially just storing the data) but a prediction complexity of O(nd) per sample. This makes it quick to train but potentially slow for predictions on large datasets.

from sklearn.neighbors import KNeighborsClassifier
import numpy as np
import time

# Generate sample data
n, d = 10000, 100
X = np.random.rand(n, d)
y = np.random.randint(0, 2, n)

# Measure time for fitting and predicting
start_time = time.time()
model = KNeighborsClassifier().fit(X, y)
predictions = model.predict(X[:100])  # Predict for first 100 samples
end_time = time.time()

print(f"Time taken for fitting and predicting: {end_time - start_time:.4f} seconds")

K-Means Clustering

K-Means has a time complexity of O(ndk), where k is the number of clusters. This makes it relatively efficient for small to medium-sized datasets but can become slow for large datasets or high numbers of clusters.

from sklearn.cluster import KMeans
import numpy as np
import time

# Generate sample data
n, d = 10000, 100
X = np.random.rand(n, d)

# Measure time for fitting
start_time = time.time()
model = KMeans(n_clusters=5).fit(X)
end_time = time.time()

print(f"Time taken for {n} samples and {d} features: {end_time - start_time:.4f} seconds")

Principal Component Analysis (PCA)

PCA has a time complexity of O(d^3) where d is the number of dimensions. This cubic relationship with dimensions makes PCA potentially slow for high-dimensional data.

from sklearn.decomposition import PCA
import numpy as np
import time

# Generate sample data
n, d = 10000, 100
X = np.random.rand(n, d)

# Measure time for fitting
start_time = time.time()
model = PCA().fit(X)
end_time = time.time()

print(f"Time taken for {n} samples and {d} features: {end_time - start_time:.4f} seconds")

Naive Bayes

Naive Bayes has a time complexity of O(nd), making it one of the fastest algorithms for training and prediction. This efficiency makes it suitable for very large datasets.

from sklearn.naive_bayes import GaussianNB
import numpy as np
import time

# Generate sample data
n, d = 10000, 100
X = np.random.rand(n, d)
y = np.random.randint(0, 2, n)

# Measure time for fitting
start_time = time.time()
model = GaussianNB().fit(X, y)
end_time = time.time()

print(f"Time taken for {n} samples and {d} features: {end_time - start_time:.4f} seconds")

Neural Networks

The time complexity of Neural Networks varies greatly depending on the architecture, but it's generally O(nde) where e is the number of epochs. This can make them computationally intensive for large datasets or complex architectures.

from sklearn.neural_network import MLPClassifier
import numpy as np
import time

# Generate sample data
n, d = 10000, 100
X = np.random.rand(n, d)
y = np.random.randint(0, 2, n)

# Measure time for fitting
start_time = time.time()
model = MLPClassifier(hidden_layer_sizes=(100, 50), max_iter=100).fit(X, y)
end_time = time.time()

print(f"Time taken for {n} samples and {d} features: {end_time - start_time:.4f} seconds")

Real-Life Example - Image Classification

In image classification tasks, the choice of algorithm can significantly impact processing time. For a dataset of 10,000 images, each 200x200 pixels:

import numpy as np
import time
from sklearn.svm import SVC
from sklearn.ensemble import RandomForestClassifier

# Simulate image data
n, width, height = 10000, 200, 200
X = np.random.rand(n, width * height)
y = np.random.randint(0, 10, n)

# SVM
start_time = time.time()
svm = SVC().fit(X[:1000], y[:1000])  # Using subset due to SVM's complexity
svm_time = time.time() - start_time

# Random Forest
start_time = time.time()
rf = RandomForestClassifier().fit(X, y)
rf_time = time.time() - start_time

print(f"SVM time (1000 samples): {svm_time:.2f} seconds")
print(f"Random Forest time (10000 samples): {rf_time:.2f} seconds")

Real-Life Example - Text Classification

For text classification tasks, such as spam detection on a dataset of 100,000 emails:

import numpy as np
import time
from sklearn.feature_extraction.text import CountVectorizer
from sklearn.naive_bayes import MultinomialNB
from sklearn.linear_model import LogisticRegression

# Simulate text data
n = 100000
texts = [f"Sample email text {i}" for i in range(n)]
y = np.random.randint(0, 2, n)

# Vectorize text
vectorizer = CountVectorizer()
X = vectorizer.fit_transform(texts)

# Naive Bayes
start_time = time.time()
nb = MultinomialNB().fit(X, y)
nb_time = time.time() - start_time

# Logistic Regression
start_time = time.time()
lr = LogisticRegression().fit(X, y)
lr_time = time.time() - start_time

print(f"Naive Bayes time: {nb_time:.2f} seconds")
print(f"Logistic Regression time: {lr_time:.2f} seconds")

Choosing the Right Algorithm

When selecting an ML algorithm, consider:

  1. Dataset size: Large datasets may require algorithms with lower time complexity.
  2. Feature dimensionality: High-dimensional data can slow down certain algorithms.
  3. Model interpretability: Some faster algorithms may sacrifice interpretability.
  4. Prediction speed: Consider both training and prediction time complexities.
  5. Accuracy requirements: More complex algorithms might offer better performance at the cost of longer run times.
import numpy as np
import matplotlib.pyplot as plt

def complexity(n, d, algorithm):
    if algorithm == 'Linear':
        return n * d
    elif algorithm == 'Quadratic':
        return n**2 * d
    elif algorithm == 'Log-linear':
        return n * np.log(n) * d

n_range = np.logspace(2, 6, num=100)
d = 100

plt.figure(figsize=(10, 6))
for algo in ['Linear', 'Quadratic', 'Log-linear']:
    times = [complexity(n, d, algo) for n in n_range]
    plt.loglog(n_range, times, label=algo)

plt.xlabel('Number of samples')
plt.ylabel('Relative time')
plt.title('Algorithm Complexity vs Dataset Size')
plt.legend()
plt.grid(True)
plt.show()

Additional Resources

For more in-depth analysis of ML algorithm complexities and performance:

  1. "Scalable Machine Learning Algorithms in Computational Biology and Biomedicine" - https://arxiv.org/abs/2102.08369
  2. "A Comparative Study on the Performance of Machine Learning Algorithms for IoT Intrusion Detection" - https://arxiv.org/abs/2103.12710
  3. "Machine Learning for Large-Scale Quality Control of 3D Shape Models in Neuroimaging" - https://arxiv.org/abs/1611.04720

These papers provide detailed insights into the performance and scalability of various ML algorithms in different domains.

More in Fundamentals and overview

  1. Top Machine Learning Algorithms Explained14 min

    Linear regression serves as a foundational predictive modeling algorithm that establishes relationships between dependent and independent variables through a...

  2. Supervised Machine Learning Concepts and Techniques22 min

    Supervised Machine Learning is a fundamental concept in artificial intelligence where an algorithm learns from labeled training data to make predictions or...

  3. Transitioning Engineers to Machine Learning14 min

    Engineers can indeed transition into the machine learning field, regardless of their background. This transition requires dedication, time, and continuous...

  4. Seven Most Used Machine Learning Algorithms11 min

    Machine learning engineers rely on a set of core algorithms to solve various problems. This presentation will cover seven fundamental algorithms: Logistic...

  5. Understanding and Addressing Class Imbalance9 min

    Class imbalance occurs when one class in a dataset significantly outnumbers others. This phenomenon is common in real-world scenarios, such as fraud...

  6. Preparing for a Machine Learning Interview11 min

    Machine learning is a vast field with numerous concepts to grasp. Understanding the fundamental principles is crucial for success in interviews and practical...