高效计算 SVM 双重损失

Question

我正在尝试在 Julia 中实现 SVM 对偶优化问题。我的数据集是 60000x784 MNIST 数字识别数据集。我正在使用 one-vs-rest 策略组合 10 个分类器，所以这只是底层二元分类器的组件，其中 $\pmb y_i \in {-1,1}$

线性版本非常快：

function dual_loss(α::Vec, X::Mat, y::Vec) where {T<:AbstractFloat, Vec<:AbstractVector{T}, Mat<:AbstractMatrix{T}}
    t = α .* y
    return sum(α) - t' * X * X' * t
end

然而内核版本非常慢，我没有足够的耐心等待它完成：

function dual_loss(α::Vec, X::Mat, y::Vec, kernel::Function=dot) where {T<:AbstractFloat, Vec<:AbstractVector{T}, Mat<:AbstractMatrix{T}}
    t = α .* y
    return sum(α) - sum(@views 0.5 * t[i] * t[j] * kernel(X[i, :], X[j, :]) for i=1:size(X, 1), j=1:size(X, 1))
end

我也试过用MLKernel.jl库，还是很慢。我想知道这是由于问题本身的严重性（我在笔记本电脑上，运行在 CPU 上），还是因为我的代码优化不够？如果可以，有什么办法可以提高它的性能吗？

Answer 1

我会试一试这个问题，尽管我对 julia 不是很熟悉。 SVM 正在将您提供给它的数据转换为更高维度，以便找到数据分类之间的线性分割。这给线性拆分如何分离 10 个不同的数字带来了一些困惑（0-9 是 MNIST 数据集中包含的内容。

在线性分割代码中，我不确定如何将数据分成不同的组，因为我不相信线性 SVM 会有多大用处。这就是为什么它运行非常快，但很可能非常不准确（不知道你的结果，只是假设）。另一个要注意的是，我认为这只是将它从它开始时的维度转变为稍微大一点的维度，这对分离没有太大帮助。

在内核代码中，这应该比线性代码花费更长的时间，据我所知，它在断言最后一行来分隔数据之前被转换成更高的维度。

我认为您的代码无法优化...内核，尤其是在非常大的数据集上，可能会非常繁重。当运行在我的计算机 CPU 上使用其他 ML 策略时，我遇到了同样的问题；它将以 100% 的速度最大化并需要数小时才能执行。您可以随时租用 space 一些具有更高规格的云服务器来运行您的代码。

我还要说看看其他一些分类方法，因为我看不出如何对 10 个不同的标签进行二元分类。

如果有帮助请告诉我！

高效计算 SVM 双重损失

Calculate SVM dual loss effeciently

machine-learning

mathematical-optimization

svm

julia