Source-linked AI summary
Strategic Classification
Moritz Hardt, Nimrod Megiddo, Christos Papadimitriou, Mary Wootters
TL;DR
Gaming can undermine classifiers used for decisions about strategic individuals because people may alter attributes after learning how classification works. The paper models this behavior as a Jury–Contestant game and develops strategy-robust learning algorithms, obtaining efficient near-optimal results for structured costs but computational hardness for general costs.
Problem
Strategic individuals may manipulate classifier-visible attributes, undermining the assumption that training and test distributions match in important applications.
Method
The paper formalizes classification as a sequential game and designs learning algorithms that anticipate Contestant’s cost-sensitive best response.
Results
Efficient near-optimal algorithms exist for separable cost functions and their structured generalizations, including cases with computationally hard-to-learn concept classes.
Takeaways & Limitations
Robust classification can be learned without requiring efficient learnability of the concept class in the uniform setting, while structured cost representations determine tractability.
Takeaways & Limitations
For general cost functions, approximating the strategic maximum is NP-hard unless P = NP, and the separability dimension can grow linearly with population size.
Abstract
from arXiv · showhide
Machine learning relies on the assumption that unseen test instances of a classification problem follow the same distribution as observed training data. However, this principle can break down when machine learning is used to make important decisions about the welfare (employment, education, health) of strategic individuals. Knowing information about the classifier, such individuals may manipulate their attributes in order to obtain a better classification outcome. As a result of this behavior---often referred to as gaming---the performance of the classifier may deteriorate sharply. Indeed, gaming is a well-known obstacle for using machine learning methods in practice; in financial policy-making, the problem is widely known as Goodhart's law. In this paper, we formalize the problem, and pursue algorithms for learning classifiers that are robust to gaming. We model classification as a sequential game between a player named "Jury" and a player named "Contestant." Jury designs a classifier, and Contestant receives an input to the classifier, which he may change at some cost. Jury's goal is to achieve high classification accuracy with respect to Contestant's original input and some underlying target classification function. Contestant's goal is to achieve a favorable classification outcome while taking into account the cost of achieving it. For a natural class of cost functions, we obtain computationally efficient learning algorithms which are near-optimal. Surprisingly, our algorithms are efficient even on concept classes that are computationally hard to learn. For general cost functions, designing an approximately optimal strategy-proof classifier, for inverse-polynomial approximation, is NP-hard.
1 Introduction
The paper formalizes gaming in classification as a sequential game and develops strategy-robust classifiers. It gives efficient near-optimal algorithms for structured cost functions, while general cost functions pose computational hardness and experiments show improved accuracy under gaming.
- Motivation: Gaming lets individuals manipulate classifier-visible attributes for favorable outcomes, threatening prediction accuracy in high-stakes applications.Examples include buying unread books to influence student admission decisions; the phenomenon is also connected to Goodhart’s law.
- Model: The model is a sequential game in which Jury publishes a classifier, Contestant changes an input at a known cost, and Jury evaluates the original input.Jury seeks high accuracy relative to the true classifier, while Contestant seeks acceptance without paying too much.
- Positive results: Efficient algorithms approach optimal payoff for certain cost functions, even when the underlying concept class is computationally intractable to learn.The paper attributes this surprising efficiency to Contestant’s input changes smoothing out intractability.
- Positive results: Separable cost functions and minima of k separable functions admit strategy-robust learning with polynomial guarantees under learnability assumptions.For minima of k separable functions, sample complexity is polynomial in k, while running time is polynomial in exp(k).
- Experiments: Experiments on Brazilian review-spam data found higher classification accuracy than standard classifiers when even a small amount of gaming occurs.The experiments also demonstrate robustness to inaccuracies in the modeled cost function and other modeling assumptions.
- Learning guarantees: Strategy-robust learning must both infer the unknown target classifier and anticipate Contestant’s best response.The paper defines non-uniform and stronger uniform guarantees, with the latter covering every target classifier in a concept class.
- Hardness and scope: For general cost functions, approximating the strategic maximum is NP-hard, including metrics under inverse-polynomial approximation unless P = NP.Any finite-domain cost function can be represented as a minimum of separable functions, but the representation may be large.
2 Separable cost functions
The section introduces separable cost functions, for which strategic classification can be reduced to structured threshold classifiers and learned with nearly optimal, efficient guarantees.
- Cost model: This model generalizes settings where each state has an intrinsic cost and moving between states costs only any additional cost.The school-books example and spam-filter example both fit this interpretation.
- Cost model: Separable costs have the form c(x,y) = max{0,c2(y) − c1(x)}, with c1(X) ⊆ c2(X) ensuring a zero-cost option.The maximum with 0 keeps costs non-negative, while the range condition lets Contestant avoid gaming at no cost.
- Learning guarantee: The algorithm for separable costs has a uniform near-optimal guarantee whose sample complexity and running time depend on the Rademacher complexity of H.Theorem 2.3 provides the guarantee simultaneously for all target classifiers in H with probability at least 1 − δ.
- Learning guarantee: If H is statistically learnable, Algorithm 1 is an efficient uniform strategy-robust learner; it also remains efficient non-uniformly when H is computationally hard to learn.The non-uniform guarantee applies for every distribution and a fixed target classifier.
- Classifier structure: For linear costs, Jury can restrict attention to affine halfspaces with a fixed normal and select the shift empirically through a one-dimensional optimization.The reduction follows because movement perpendicular to the cost direction is free.
3 General cost functions
The paper extends its approach from separable costs to minima of separable functions, covering broad cost classes while retaining efficient near-optimal learning in represented cases. General representations can be large, and guarantees depend on their size or structure.
- Every cost function on a finite domain can be represented as a minimum of separable cost functions, though not necessarily parsimoniously.
- A metric cost function can be approximated by a minimum of separable functions whose number depends essentially on the metric space’s covering number.For an ε-net S, the approximation lies between c(x,y) and c(x,y) + 4ε.
- Algorithm 2 adapts Algorithm 1 to cost functions formed as minima of separable functions.
- Algorithm 2 uses labeled samples and a description of k separable cost functions, then selects a classifier through empirical error minimization.
- With sufficient samples, Theorem 3.3 guarantees the stated bound uniformly over target classifiers, with running time O(m|B|).
- When the representation set B is large, the guarantees worsen, although structured classes may replace its size-dependent term with a smaller complexity measure.
4 NP-completeness
For general cost functions, computing an approximately optimal strategic classifier is NP-hard, even with a metric cost function, uniform distribution, and known labels. The result follows from a reduction from 3Sat that creates a payoff gap between satisfiable and unsatisfiable formulas.
- Implications: The hardness persists even when the learning algorithm receives correct labels for every member of X and even when the underlying distance function is a metric.Choosing K as a large polynomial in m converts the payoff gap into inverse-polynomial inapproximability.
- Hardness result: ε = 1/|X|^η strategic optimum computation is NP-hard for every constant η > 0.The hardness holds for finite populations with uniform distribution, metric costs, and target labels h.
- Reduction construction: The reduction from 3Sat constructs a weighted population whose duplicated points form the instance population X.The construction uses literal-occurrence points, clause-pair points, additional Q-points, and a high-weight point R.
- Reduction construction: The constructed cost function is a metric with only two nonzero distances, 1.5 and 2.5.Symmetry, zero self-distance, and the chosen distances ensure the triangle inequality.
- Payoff gap: The baseline payoff is achieved by labeling every point −1, while a satisfiable formula permits a classifier with payoff at least b + K − 9√m.The proof analyzes best responses through the graph of pairs at distance 1.5 and constrains which points an optimal classifier labels positively.
- Payoff gap: A payoff improvement beyond baseline occurs if and only if one can select noncontradictory literals, which is equivalent to satisfiability of the original formula.The decisive case selects one literal from each clause without contradictory pairs.
- Implications: The proof’s metric has separability dimension growing linearly with population size, leaving open whether the algorithm’s exponential dependence on that dimension is necessary.The alternative possibility is fixed-parameter tractability in separability dimension.
5 Experiments
The experiments compare the strategy-robust classifier with a linear SVM on Brazilian review-spam data under modeling errors and varying gaming. The robust method outperforms SVM under small gaming, remains robust to significant modeling errors, and supports hybrid accuracy–robustness trade-offs.
- Experimental setting: The experiments use 7076 Apontador review-spam instances, approximately half labeled spam, with SVM as the standard-classifier baseline.The data come from a Brazilian social network, and linear SVM is used for interpretability while retaining high accuracy.
- Experimental setting: The cost function models lost spammer revenue from changing message attributes rather than primarily monetary editing costs.It is modeled as the nonnegative truncated linear function c(x,y) = ⟨α,y −x⟩+.
- Robustness evaluation: The evaluation introduces two modeling errors: the true cost function differs from the training cost function, and actual gaming may differ from the theoretically predicted threshold.The true cost may include a squared Euclidean term, while the algorithm uses an incorrect separable cost and an inaccurate cost vector.
- Experimental design: The experiments vary ε, perturb the assumed cost vector with Gaussian noise, and scale both cost functions to control the allowed gaming amount t.Scaling by 2/t makes the Contestant willing to move distance t in the α direction, with attributes normalized to standard deviation 1.
- Robustness evaluation: The robust algorithm outperforms SVM under a small amount of gaming and in the presence of significant modeling errors.The comparison is conducted within the stated error model using SVM as a representative standard classifier.
- Hybrid classifiers: A hybrid combining the robust classifier with SVM achieves higher accuracy across a robust range of parameters.The framework assigns the known classifier a positive cost-function weight, producing different trade-offs between gaming and accuracy.
A Proof of Theorem 3.3
The proof reduces the analysis to structured threshold classifiers and compares their empirical and expected errors uniformly over admissible thresholds. A uniform convergence claim then completes the theorem.
- Strategic-response reduction: The proof defines Γ(f) as the inputs whose best response under f can obtain a positive classification outcome.This identifies which original inputs are classified positively after strategic response.
- Strategic-response reduction: For any classifier f, the proof restricts attention to a structured classifier f′ whose positive region is determined by minimum cost thresholds.The positive region is contained in cost-level sets, preserving the relevant payoff to Jury.
- Strategic-response reduction: The payoff to Jury is unchanged by replacing f with the structured classifier f′.This establishes that considering only classifiers of the threshold form is sufficient.
- Threshold optimization: The best structured classifier is obtained by selecting thresholds s that optimize Jury’s payoff.The proof relates these thresholds to the minimum b2-cost among accepted points and to Algorithm 2’s returned classifier.
- Uniform convergence: The theorem is completed by proving that empirical error c_err(s) is uniformly close to expected error err(s) over all s ∈ S_B.Claim A.1 supplies the required high-probability uniform bound, using a Rademacher-complexity argument for the threshold class H.
- Uniform convergence: The complexity analysis reduces to bounding the Rademacher complexity of H = {min_b∈B b1[s_b −2] : s ∈ S_B}.The proof derives this bound over fixed samples and invokes it to finish the claim and theorem.