MATLAB 中的 quadprog 花费大量时间
quadprog in MATLAB taking lot of time
我的目标是 class 使用多 class 线性 SVM（不带内核）对图像进行分类。我想编写自己的 SVM classifier
我正在使用 MATLAB 并使用提供的图像集训练了线性 SVM。
我有大约 20 classes，每个 class 有 5 张图像（总共 100 张图像），我使用的是一对一策略。
每张图片都是一个(112,92)矩阵。这意味着 112*92=10304 个值。
我正在使用 quadprog(H,f,A,C) 求解 SVM 中的二次方程 (y=w'x+b)。为一张图像调用大小为 10304 的 quadprog returns w 矢量。这意味着我必须调用 quadprog 100 次。
问题 是一个 quadprog 调用需要 35 秒才能执行。这意味着 100 张图像需要 3500 秒。这可能是由于涉及到大量的向量和矩阵。
我想减少 quadprog 的执行时间。有什么办法吗？
首先，当你使用SVM进行class化时，通常会提取图像的一个特征（如HOG），因此SVM所要操作的space维数减少。您正在使用生成 10304-D 向量的原始像素值。这是不好的。使用一些标准功能。
其次，您没有调用 quadprog 100 次。你只打一次电话。优化背后的概念是，您想要找到一个权重向量 w 和一个偏差 b ，使其满足所有图像（即所有 x_i）的 w'x_i+b=y_i。请注意，i 将从 1 变为训练集中示例的数量，但 w 和 b 保持不变。如果你想要一个只满足一个 x 的 (w,b)，你不需要任何花哨的优化。所以把你的x堆在一个NxD维数的大矩阵中，y就是一个Nx1的向量，然后调用quadprog。这将花费比 35 秒更长的时间，但您只需执行一次。这叫做training an SVM。在测试 new 图像时，您只需提取其特征，然后执行 w*x+b 以获得其 class.
第三，除非您将此作为理解 SVM 的练习，否则 quadprog 不是解决此问题的最佳方法。您需要使用一些其他适用于大数据的技术，例如 Sequential Minimal Optimization.
How can one linear hyperplane classify more than 2 classes: For multi-class classification ，支持向量机通常使用两种流行的方法：
- One-vs-one SVM：对于
C class 问题，您训练 C(C-1)/2 class 化器并在测试时测试那么多 classifiers 并选择获得最多选票的 class。
- One-vs-all SVM：顾名思义，你用 class 的正样本和所有其他 class 的负样本为每个 class 训练一个 classifier =]es.
来自 LIBSVM FAQs:
It is one-against-one. We chose it after doing the following comparison: C.-W. Hsu and C.-J. Lin. A comparison of methods for multi-class support vector machines , IEEE Transactions on Neural Networks, 13(2002), 415-425.
"1-against-the rest" is a good method whose performance is comparable to "1-against-1." We do the latter simply because its training time is shorter.
但是，还要注意，一对一的简单实现对于大规模问题可能不切实际。 LIBSVM 网站也列出了这个缺点并提供 an extension.
LIBLINEAR does not support one-versus-one multi-classification, so we provide an extension here. If k is the number of classes, we generate k(k-1)/2 models, each of which involves only two classes of training data. According to Yuan et al. (2012), one-versus-one is not practical for large-scale linear classification because of the huge space needed to store k(k-1)/2 models. However, this approach may still be viable if model vectors (i.e., weight vectors) are very sparse. Our implementation stores models in a sparse form and can effectively handle some large-scale data.
我的目标是 class 使用多 class 线性 SVM（不带内核）对图像进行分类。我想编写自己的 SVM classifier
我正在使用 MATLAB 并使用提供的图像集训练了线性 SVM。
我有大约 20 classes，每个 class 有 5 张图像（总共 100 张图像），我使用的是一对一策略。
每张图片都是一个(112,92)矩阵。这意味着 112*92=10304 个值。
我正在使用 quadprog(H,f,A,C) 求解 SVM 中的二次方程 (y=w'x+b)。为一张图像调用大小为 10304 的 quadprog returns w 矢量。这意味着我必须调用 quadprog 100 次。
问题 是一个 quadprog 调用需要 35 秒才能执行。这意味着 100 张图像需要 3500 秒。这可能是由于涉及到大量的向量和矩阵。
我想减少 quadprog 的执行时间。有什么办法吗？
首先，当你使用SVM进行class化时，通常会提取图像的一个特征（如HOG），因此SVM所要操作的space维数减少。您正在使用生成 10304-D 向量的原始像素值。这是不好的。使用一些标准功能。
其次，您没有调用 quadprog 100 次。你只打一次电话。优化背后的概念是，您想要找到一个权重向量 w 和一个偏差 b ，使其满足所有图像（即所有 x_i）的 w'x_i+b=y_i。请注意，i 将从 1 变为训练集中示例的数量，但 w 和 b 保持不变。如果你想要一个只满足一个 x 的 (w,b)，你不需要任何花哨的优化。所以把你的x堆在一个NxD维数的大矩阵中，y就是一个Nx1的向量，然后调用quadprog。这将花费比 35 秒更长的时间，但您只需执行一次。这叫做training an SVM。在测试 new 图像时，您只需提取其特征，然后执行 w*x+b 以获得其 class.
第三，除非您将此作为理解 SVM 的练习，否则 quadprog 不是解决此问题的最佳方法。您需要使用一些其他适用于大数据的技术，例如 Sequential Minimal Optimization.
How can one linear hyperplane classify more than 2 classes: For multi-class classification ，支持向量机通常使用两种流行的方法：
- One-vs-one SVM：对于
Cclass 问题，您训练C(C-1)/2class 化器并在测试时测试那么多 classifiers 并选择获得最多选票的 class。 - One-vs-all SVM：顾名思义，你用 class 的正样本和所有其他 class 的负样本为每个 class 训练一个 classifier =]es.
来自 LIBSVM FAQs:
It is one-against-one. We chose it after doing the following comparison: C.-W. Hsu and C.-J. Lin. A comparison of methods for multi-class support vector machines , IEEE Transactions on Neural Networks, 13(2002), 415-425.
"1-against-the rest" is a good method whose performance is comparable to "1-against-1." We do the latter simply because its training time is shorter.
但是，还要注意，一对一的简单实现对于大规模问题可能不切实际。 LIBSVM 网站也列出了这个缺点并提供 an extension.
LIBLINEAR does not support one-versus-one multi-classification, so we provide an extension here. If k is the number of classes, we generate k(k-1)/2 models, each of which involves only two classes of training data. According to Yuan et al. (2012), one-versus-one is not practical for large-scale linear classification because of the huge space needed to store k(k-1)/2 models. However, this approach may still be viable if model vectors (i.e., weight vectors) are very sparse. Our implementation stores models in a sparse form and can effectively handle some large-scale data.