如何计算多分类任务中五种机器学习算法及PLCM的计算复杂度

计算复杂度通常需分训练阶段和推理阶段分别讨论，以下是各方法的具体分析：

一、单个机器学习模型的复杂度 #

1. 人工神经网络（ANN） #

• 训练阶段：以全连接ANN为例，假设样本数为N，输入特征数为F，网络层数为L，每层神经元数为H（假设各层规模相近），训练复杂度为 O(N * L * F * H)。这是因为每次前向传播+反向传播需遍历所有样本、所有层的神经元，计算权重更新。若使用卷积神经网络（CNN），复杂度需结合卷积核大小、特征图尺寸调整，但通用全连接ANN遵循上述公式。
• 推理阶段：仅需前向传播计算输出，复杂度为 O(L * F * H)，无需反向传播的权重更新步骤。

2. 随机森林 #

• 训练阶段：每棵决策树的训练复杂度为O(N * F * logN)（遍历特征选择最优分裂点，排序样本的复杂度为O(N logN)），若包含T棵树，总训练复杂度为 O(T * N * F * logN)。
• 推理阶段：对单个测试样本，需遍历每棵树的分裂路径得到预测结果，再投票汇总，复杂度为 O(T * F)。

3. CatBoost #

• 训练阶段：本质是带类别特征优化的梯度提升树，每棵树的训练复杂度与随机森林单棵树相近（O(N * F * logN)），T棵树的总训练复杂度为 O(T * N * F * logN)。CatBoost的有序分裂、对称树等优化会降低实际运行时间，但理论复杂度仍遵循此量级。
• 推理阶段：与随机森林类似，遍历T棵树加权求和输出，复杂度为 O(T * F)。

4. 支持向量机（SVM） #

• 训练阶段：若使用SMO算法求解，复杂度为 O(N²) ~ O(N³)（N为样本数）；若使用核技巧处理高维特征，每次核函数计算需O(F)时间，总复杂度变为 O(N² * F)。
• 推理阶段：需计算测试样本与所有支持向量（数量为N_sv）的核函数值并加权求和，复杂度为 O(N_sv * F)。

5. K近邻（KNN） #

• 训练阶段：无实际训练过程，仅需存储所有训练样本，复杂度为 O(N * F)（存储N个F维样本）。
• 推理阶段：对每个测试样本（共M个），需计算与所有N个训练样本的距离，再选取前K个样本投票，复杂度为 O(M * N * F)。若使用KD树、Ball树等索引结构优化，最坏复杂度仍为O(M * N * F)，平均复杂度可降至 O(M * logN * F)。

二、幂律委员会机（PLCM）融合方法的复杂度 #

PLCM的复杂度由基模型推理和PLCM融合计算两部分组成：

1. 基模型推理部分：需先运行上述5个模型完成推理，总复杂度为5个模型推理复杂度之和，即 C_ANN + C_RF + C_CatBoost + C_SVM + C_KNN（各C为对应模型的推理复杂度）。
2. PLCM融合计算部分：假设分类任务有K个类别，对每个测试样本，需对5个基模型输出的K维得分执行幂律变换、加权求和等操作，复杂度为 O(M * K * 5)（M为测试样本数）。

若PLCM需训练融合参数（如幂次、权重），训练阶段需使用基模型的输出作为训练数据，假设训练样本数为M_total，若采用线性拟合等简单方法，训练复杂度为 O((5*K)² * M_total)，远低于基模型的训练复杂度。

内容的提问来源于stack exchange，提问作者Reza