Skip to content

Skip kernel computation when nu is infeasible in NuSVC#34177

Open
Lawson-Darrow wants to merge 2 commits into
scikit-learn:mainfrom
Lawson-Darrow:nusvc-early-nu-feasibility
Open

Skip kernel computation when nu is infeasible in NuSVC#34177
Lawson-Darrow wants to merge 2 commits into
scikit-learn:mainfrom
Lawson-Darrow:nusvc-early-nu-feasibility

Conversation

@Lawson-Darrow
Copy link
Copy Markdown

Fixes #33478

When NuSVC is fit with a callable kernel, the full kernel matrix is computed before libsvm checks whether nu is feasible. For expensive custom kernels this wastes a lot of work, since an infeasible nu then fails immediately with "specified nu is infeasible".

The feasibility check only depends on the per class counts and nu, not on the kernel. This moves an equivalent check to the Python side in BaseLibSVM.fit, before the kernel is computed.

The condition mirrors libsvm's check in svm_check_parameter (svm.cpp). For every pair of classes it requires nu * (n_i + n_j) / 2 <= min(n_i, n_j), where the counts are sample weighted to match libsvm's W[i]. The check is gated to NuSVC only, since NuSVR and OneClassSVM are not subject to it in libsvm.

An infeasible nu now raises before any kernel call. A feasible nu is unaffected apart from an O(n) count over the labels.

Added two regression tests in test_svm.py: one asserts the callable kernel is never invoked when nu is infeasible, the other checks the early verdict matches the libsvm built in kernel path across a range of nu values and under sample weights.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Projects

None yet

Development

Successfully merging this pull request may close these issues.

NuSVC computes kernels before checking nu feasibility

1 participant