Skip kernel computation when nu is infeasible in NuSVC#34177
Open
Lawson-Darrow wants to merge 2 commits into
Open
Skip kernel computation when nu is infeasible in NuSVC#34177Lawson-Darrow wants to merge 2 commits into
Lawson-Darrow wants to merge 2 commits into
Conversation
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Add this suggestion to a batch that can be applied as a single commit.This suggestion is invalid because no changes were made to the code.Suggestions cannot be applied while the pull request is closed.Suggestions cannot be applied while viewing a subset of changes.Only one suggestion per line can be applied in a batch.Add this suggestion to a batch that can be applied as a single commit.Applying suggestions on deleted lines is not supported.You must change the existing code in this line in order to create a valid suggestion.Outdated suggestions cannot be applied.This suggestion has been applied or marked resolved.Suggestions cannot be applied from pending reviews.Suggestions cannot be applied on multi-line comments.Suggestions cannot be applied while the pull request is queued to merge.Suggestion cannot be applied right now. Please check back later.
Fixes #33478
When
NuSVCis fit with a callable kernel, the full kernel matrix is computed before libsvm checks whethernuis feasible. For expensive custom kernels this wastes a lot of work, since an infeasiblenuthen 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 inBaseLibSVM.fit, before the kernel is computed.The condition mirrors libsvm's check in
svm_check_parameter(svm.cpp). For every pair of classes it requiresnu * (n_i + n_j) / 2 <= min(n_i, n_j), where the counts are sample weighted to match libsvm'sW[i]. The check is gated to NuSVC only, since NuSVR and OneClassSVM are not subject to it in libsvm.An infeasible
nunow raises before any kernel call. A feasiblenuis 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 whennuis infeasible, the other checks the early verdict matches the libsvm built in kernel path across a range ofnuvalues and under sample weights.