algorithm - 最大似然和支持向量复杂度

Question

任何人都可以提供一些引用资料来说明如何确定最大似然和支持向量机分类器的计算复杂度吗？我一直在网上搜索，但似乎没有找到详细说明如何找到对这些分类器算法的计算复杂性建模的方程式的好文档。谢谢

Answer 1

支持向量机，以及一些最大似然拟合都是凸最小化问题。因此，理论上它们可以使用 http://en.wikipedia.org/wiki/Ellipsoid_method 在多项式时间内求解。 .

我怀疑如果考虑方法，您可以获得更好的估计。 http://www.cse.ust.hk/~jamesk/papers/jmlr05.pdf表示 m 个实例上的标准 SVM 拟合成本为 O(m^3) 时间和 O(m^2) 空间。 http://research.microsoft.com/en-us/um/people/minka/papers/logreg/minka-logreg.pdf给出了逻辑回归的每次迭代成本，但没有给出估计迭代次数的理论基础。在实践中，我希望大多数时候这会达到二次收敛并且不会太糟糕。