Logistic回归的搜索/预测时间复杂度是多少？

Question

我正在研究机器学习算法的时间复杂度，但找不到用于预测新输入的Logistic回归的时间复杂度是多少。我已经读到，对于分类而言，O为（c * d），C为类数，d为维数。我知道，对于线性回归，搜索/预测时间复杂度为O（d）。您能否解释一下Logistic回归的搜索/预测时间复杂度是多少？先感谢您

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

Answer 1

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)

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

Complexity of predictions for one sample: O((f+1)c)

• 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.

Complexity of predictions for many samples: O((f+1)cs)

• (f+1)c - see complexity for one sample
• s - number of samples

Difference between logistic and linear regression in terms of complexity: activation function.

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