Logistic回归的搜索/预测时间复杂度是多少? [英] What is the Search/Prediction Time Complexity of Logistic Regression?

问题描述

我正在研究机器学习算法的时间复杂度，但找不到用于预测新输入的Logistic回归的时间复杂度是多少.我已经读到，对于分类是O(c * d)，c表示类的数量，d表示维的数量，并且我知道对于线性回归，搜索/预测时间的复杂度是O(d).您能否解释一下Logistic回归的搜索/预测时间复杂度是多少? 预先谢谢你

I am looking into the time complexities of Machine Learning Algorithms and I cannot find what is the time complexity of Logistic Regression for predicting a new input. I have read that for Classification is O(c*d) c-beeing the number of classes, d-beeing the number of dimensions and I know that for the Linear Regression the search/prediction time complexity is O(d). Could you maybe explain what is the search/predict time complexity of Logistic Regression? Thank you in advance

其他机器学习问题的示例: https://www.thekerneltrip.com/machine/learning/computational -complexity-learning-algorithms/

Example For The other Machine Learning Problems: https://www.thekerneltrip.com/machine/learning/computational-complexity-learning-algorithms/

推荐答案

基于梯度优化的逻辑回归方法的训练复杂度:O((f + 1)csE)，其中:

• f -功能数量(由于偏差而为+1).每个特征的乘积乘以权重(f操作，+1表示偏差).另一种f + 1操作，用于将所有这些操作相加(获得预测).使用梯度方法来提高相同数量操作的权重计数，因此我们总共得到 4 *(f + 1)(两个用于前进，两个用于后退)，简称为 O(f + 1).
• c -您的逻辑回归中的类数(可能的输出).对于二进制分类，它是一个，因此该术语被取消了.每个类别都有对应的权重集.
• s -您数据集中的样本数量，我认为这很直观.
• E -您愿意进行梯度下降的时期数(整个数据集都通过)

Complexity of training for logistic regression methods with gradient based optimization: O((f+1)csE), where:

• f - number of features (+1 because of bias). Multiplication of each feature times it's weight (f operations, +1 for bias). Another f + 1 operations for summing all of them (obtaining prediction). Using gradient method to improve weights counts for the same number of operations, so in total we get 4* (f+1) (two for forward pass, two for backward), which is simply O(f+1).
• c - number of classes (possible outputs) in your logistic regression. For binary classification it's one, so this term cancels out. Each class has it's corresponding set of weights.
• s - number of samples in your dataset, this one is quite intuitive I think.
• E - number of epochs you are willing to run the gradient descent (whole passes through dataset)

注意:这种复杂性可以根据正则化(另一种c操作)而改变，但是其背后的想法是这样的.

Note: this complexity can change based on things like regularization (another c operations), but the idea standing behind it goes like this.

• f +1 -您只需将每个权重乘以特征值，添加偏差并将所有权重加在一起即可.
• c -您为每个类别都进行此操作，对于二进制预测则为1.
• f + 1 - you simply multiply each weight by the value of feature, add bias and sum all of it together in the end.
• c - you do it for every class, 1 for binary predictions.
• (f + 1)c -查看一个样本的复杂性
• s -样本数量
• (f+1)c - see complexity for one sample
• s - number of samples

对于多类逻辑回归，它将为 softmax ，而线性回归(顾名思义)具有线性激活(实际上没有激活).它不会使用大的O表示法来改变复杂度，但它是训练期间的另一个 c * f 操作(不想进一步弄乱图片)，将其乘以2作为反向传播.

For multiclass logistic regression it will be softmax, while linear regression, as the name suggests, has linear activation (effectively no activation). It does not change the complexity using big O notation, but it's another c*f operations during the training (didn't want to clutter the picture further) multiplied by 2 for backprop.

这篇关于Logistic回归的搜索/预测时间复杂度是多少?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！