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

Question

谁能提供一些参考资料来说明如何确定最大似然和支持向量机分类器的计算复杂度？我一直在网上搜索，但似乎没有找到一个好的文档来详细说明如何找到对这些分类器算法的计算复杂度进行建模的方程。谢谢

Answer 1

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

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