machine-learning - 逻辑回归的搜索/预测时间复杂度是多少？

Question

我正在研究机器学习算法的时间复杂度，但我找不到预测新输入的逻辑回归的时间复杂度。我读过，分类是 O(c*d) c-类的数量，d-维度的数量，我知道对于线性回归，搜索/预测时间复杂度是 O(d)。您能否解释一下逻辑回归的搜索/预测时间复杂度是多少？预先感谢您

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

Answer 1

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

• f - 特征数量(由于偏差+1)。每个特征乘以它的权重(f 运算，+1 表示偏差)。另一个 f + 1 运算用于对所有这些进行求和(获得预测)。使用梯度方法来提高相同操作次数的权重计数，因此总共我们得到 4* (f+1) (两个用于前向传递，两个用于向后传递)，这就是 O(f+1)。
• c - 逻辑回归中的类数(可能的输出)。对于二元分类来说，它是一个，所以这个术语被抵消了。每个类别都有其相应的权重集。
• s - 数据集中的样本数量，我认为这个非常直观。
• E - 您愿意运行梯度下降的纪元数(整个数据集)

注意:这种复杂性可能会根据正则化(另一个 C 操作)等内容而改变，但其背后的想法是这样的。

一个样本的预测复杂度:O((f+1)c)

• f + 1 - 只需将每个权重乘以特征值，加上偏差，最后将所有结果相加即可。
• c - 您对每个类都执行此操作，1 表示二元预测。

许多样本的预测复杂度:O((f+1)cs)

• (f+1)c - 查看一个样本的复杂性
• s - 样本数量

逻辑回归和线性回归在复杂性方面的差异:激活函数。

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