机器学习的时空复杂度
The train time complexity of machine learning model — The amount of time taken to train the model
机器学习模型的训练时间复杂度 -训练模型花费的时间
The test time complexity of the machine learning model — Time took to predict output for a given input query point.
机器学习模型的测试时间复杂度-预测给定输入查询点的输出所花费的时间。
Time complexity is an essential aspect to know when anyone wants their model with low latency. Let’s dive deep into details of how much time and space required by the wide variety of models to predict the output.
时间复杂度是了解何时有人想要低延迟的模型的重要方面。 让我们深入研究各种模型预测输出需要多少时间和空间。
“Assuming training data has n points with d dimensions “
“假设训练数据有n个维度为d的点”
Given query point (xq), K-NN follows these steps to predict output (yq). For each xi in the training set, Compute distance for xi and xq.
给定查询点(xq)，K-NN遵循以下步骤来预测输出(yq)。 对于训练集中的每个xi，计算xi和xq的距离。
https://www.edureka.co/blog/k-nearest-neighbors-algorithm/ https://www.edureka.co/blog/k-nearest-neighbors-algorithm/Computing distance for one point takes o(d) time, as we are computing for each xi in training it takes o(nd)
计算一个点的距离需要o(d)的时间，因为我们在训练中针对每个xi进行计算都需要o(nd)
Then store the smallest k distances in a list and the Majority vote to K points, which took o(1). As we need whole train data during run time, Space complexity will be o(nd) finally for KNN
然后将最小的k个距离存储在列表中，并且将多数票投给K点，这花费了o(1)。 由于我们在运行时需要整个火车数据，因此对于KNN，空间复杂度最终将是未知的
Run Time complexity = O(nd)
运行时间复杂度= O(nd)
Space complexity = O(nd)
空间复杂度= O(nd)
There is no train time complexity for KNN
KNN没有火车时间复杂性
Given query point (xq), Naive Bayes need just prior and likelihood probabilities to predict output (yq), which permits the model to use at low latency applications.
给定查询点(xq)，朴素贝叶斯只需要先验概率和似然概率来预测输出(yq)，这允许模型在低延迟应用程序中使用。
https://heartbeat.fritz.ai/understanding-the-mathematics-behind-naive-bayes-ab6ee85f50d0 https://heartbeat.fritz.ai/understanding-the-mathematics-behind-naive-bayes-ab6ee85f50d0So, during the training phase of Naive Bayes, it calculates all likelihood probabilities and prior probability, which takes Time complexity of O(ndc) where c= Number of classes and Space complexity= O(dc)
因此，在朴素贝叶斯训练阶段，它会计算所有似然概率和先验概率，这需要O(ndc)的时间复杂度，其中c =类数，空间复杂度= O(dc)
Train Time complexity = O(n*d*c)
火车时间复杂度= O(n * d * c)
Run Time complexity =O(d*c)
运行时间复杂度= O(d * c)
Space complexity = O(d*c)
空间复杂度= O(d * c)
For query point (xq), Logistic Regression needs just a d-dimension weight vector(W).
对于查询点(xq)，逻辑回归仅需要d维权重向量(W)。
yq = sigmoid(W.xq), which takes O(d) time and space required is O(d)
yq = sigmoid(W.xq)，耗时O(d)，所需空间为O(d)
https://www.researchgate.net/figure/Classification-decision-boundary-using-logistic-regression-The-blue-area-corresponds-to_fig5_325813999 https://www.researchgate.net/figure/Classification-decision-boundary-using-logistic-regression-The-blue-area-corresponds-to_fig5_325813999For the Training Logistic Regression, the optimization problem needs to be solved using Stochastic Gradient Descent that takes O(nd).
对于训练逻辑回归，需要使用采用O(nd)的随机梯度下降来解决优化问题。
Logistic Regression is applicable for low latency applications and memory-efficient at run time.
Logistic回归适用于低延迟应用程序，并且在运行时具有内存效率。
Train Time complexity = O(n*d)
火车时间复杂度= O(n * d)
Run Time complexity =O(d)
运行时间复杂度= O(d)
Space complexity = O(d)
空间复杂度= O(d)
Train Time complexity = O(n*log(n)*d)
火车时间复杂度= O(n * log(n)* d)
Space complexity=O(p) where p= no of nodes in tree
空间复杂度= O(p)，其中p =树中的节点数
Run Time complexity= O(k) where k= depth of tree
运行时间复杂度= O(k)，其中k =树的深度
why O(n*log(n)*d)?
为什么是O(n * log(n)* d)？
Let’s say the dataset has n points d features and all features are numerical.
假设数据集具有n个点d个特征，并且所有特征都是数字。
As the numerical feature needs to be sorted, Sorting one feature takes O(n*lgn)
由于需要对数字特征进行排序，因此对一个特征进行排序需要O(n * lgn)
Then Sorting all d features will take O(n*lgn*d)
然后，对所有d个特征进行排序将取O(n * lgn * d)
Now we need to calculate Information gain at each threshold. For one feature, it takes O(n), and for d features, it takes O(n*d) 现在我们需要计算每个阈值处的信息增益。 对于一个特征，它需要O(n)，对于d个特征，它需要O(n * d) Time complexity is O(n*lgn*d)+ O(nd) 时间复杂度为O(n * lgn * d)+ O(nd)Because of Big O notation, O(nlogn*d)+O(n*d) will be almost equal to O(nlogn*d).
由于使用大O表示法，因此O(nlogn * d)+ O(n * d)几乎等于O(nlogn * d)。
Runtime space complexity =o(no. of nodes). During Runtime for DT, it only needs if-else conditions for decisionthus space complexity is reasonable.
运行时空间复杂度= o(节点数)。 在DT的运行系统期间，仅需要if-else条件来进行决策，因此空间复杂性是合理的。
As the random forest is formed from k base learners (Decision Trees) for query point xq to predict yq we get k outputs then by Aggregation (majority weight or mean/median) is applied on the outputs of the k base learners (DTs) to generate yq.
由于随机森林是由k个基础学习者(决策树)形成的，用于查询点xq来预测yq，因此我们获得了k个输出，然后将合计(多数权重或均值/中位数)应用于k个基础学习者(DT)的输出，从而得出产生yq。
https://en.wikipedia.org/wiki/Random_forest#/media/File:Random_forest_diagram_complete.png https://zh.wikipedia.org/wiki/Random_forest#/media/File:Random_forest_diagram_complete.pngfor the random forest with m decision trees
有m个决策树的随机森林
Train Time complexity = O(n*log(n)*d*m)
火车时间复杂度= O(n * log(n)* d * m)
Space complexity=O(p*m)
空间复杂度= O(p * m)
Run Time complexity= O(k*m)
运行时间复杂度= O(k * m)
During Training, Random Forest can be parallelized as each base learner can be trained on the different core of the computer.
在培训期间，可以对随机森林进行并行化，因为可以在计算机的不同核心上对每个基础学习者进行培训。
Train Time complexity = O(n*log(n)*d*m)
火车时间复杂度= O(n * log(n)* d * m)
Space complexity=O(p*m+gamma) as has to be multiplied with m models.
空间复杂度= O(p * m + gamma)，必须与m个模型相乘。
Run Time complexity= O(k*m)
运行时间复杂度= O(k * m)
https://en.wikipedia.org/wiki/Gradient_boosting https://zh.wikipedia.org/wiki/渐变_嘘声Train Time complexity = O(n²)
火车时间复杂度= O(n²)
Space complexity=O(s)
空间复杂度= O(s)
Run-time Complexity= O(s*d)s= number of Support Vectors,d=dimentionality of the data
运行时复杂度 = O(s * d) s =支持向量的数量，d =数据的维数
www.appliedaicourse.com
www.appliedaicourse.com
https://www.hackerearth.com/practice/basic-programming/complexity-analysis/time-and-space-complexity/tutorial/#:~:text=Time%20complexity%20of%20an%20algorithm,the%20length%20of%20the%20input.&text=Let%20each%20operation%20takes%20time.
https://www.hackerearth.com/practice/basic-programming/complexity-analysis/time-and-space-complexity/tutorial/#:~:text=Time%20complexity%20of%20an%20算法，％20length％ 20of％20the％20input。＆text =让％20each％20operation％20takes％20time 。
翻译自: https://medium.com/towards-artificial-intelligence/time-and-space-complexity-of-machine-learning-models-df9b704e3e9c
机器学习的时空复杂度
