Abstract
Machine Teaching involves a "teacher" constructing a minimal dataset to guide a "student" model toward a specific prediction goal. While well-established for continuous data, machine teaching for discrete, categorical data—such as medical records or malware features—remains a significant challenge due to the combinatorial nature of the input space. We introduce Discrete Machine Teaching (DMT), an iterative algorithm that strategically modifies training data to manipulate model predictions on discrete inputs. By combining gradient-guided feature selection with an iterative retraining loop, DMT achieves near 100% success in both correcting model errors and performing targeted poisoning attacks, significantly outperforming existing continuous-domain baselines.
Introduction
Most research on manipulating model predictions focuses on continuous domains, where gradients can be used to incrementally adjust input features (e.g., pixels in an image). However, many critical systems, including clinical prediction tools and malware detectors, rely on discrete categorical inputs. In these settings, features cannot be "nudged"; they must be flipped entirely (e.g., changing a binary flag for a specific medical condition). This transforms machine teaching into a daunting combinatorial optimization problem. Existing methods often fail because they produce continuous values that lose effectiveness when rounded back to discrete integers.
The Discrete Machine Teaching Framework
The proposed DMT framework operates through an iterative loop between the teacher and the student model. The process involves three primary stages:
- Teacher Dataset Construction: The teacher identifies influential base samples from the training set using k-nearest neighbors (k-NN) with Jaccard distance.
- Gradient Guided Greedy Method (GGGM): To identify which discrete features to flip, the algorithm utilizes the student model's gradients to filter for high-impact candidates. It then selects modifications based on either a Distance Score ($g_{dist}$), which minimizes the Euclidean distance to the target, or an Alignment Score ($g_{align}$), which aligns the gradient of the perturbed sample with that of the target sample.
- Iterative Student Update: Modified samples are added to the training set, and the student model is retrained. This cycle continues until the target prediction is achieved.
Experimental Evaluation
DMT was evaluated on three real-world discrete datasets: Electronic Health Records (EHR) for clinical diagnosis, MALWARE features for detection, and Intrusion Prevention System (IPS) network traffic. The performance was measured by the Change Success Rate (CSR) relative to the percentage of the training set modified.
Key Results: Error Correction and Poisoning
DMT demonstrated superior performance across both beneficial (improvement) and malicious (poisoning) tasks. In the malware improvement task, DMT-align corrected model errors by modifying as little as 0.13% of the training data.
In the poisoning (malicious) setting, the gap between DMT and baselines is even more pronounced. While DMT-align reaches 100% success, continuous-domain baselines like "Frogs" often fail to make any meaningful impact on discrete features.
Discussion and Insights
- The Power of Iteration: Small, incremental updates are more effective than single-shot modifications, as iteration allows the teacher to adapt to the student's shifting decision boundaries.
- Alignment vs. Distance: Gradient alignment ($g_{align}$) is generally more effective than simple output distance. By matching the direction of influence, the teacher finds more potent perturbations requiring fewer changes to the dataset.
- Failure of Continuous Baselines: Methods designed for images perform poorly on discrete data. Their reliance on rounding continuous outputs back to discrete values makes them significantly less efficient than DMT’s native discrete search.
Conclusion
Discrete Machine Teaching provides a robust framework for manipulating predictions in domains where inputs are categorical. While computationally intensive due to the requirement for iterative retraining, DMT achieves near-perfect success rates with a minimal data footprint. Future work will explore "black-box" scenarios where the teacher has limited access to the student's internal gradients and seek formal theoretical guarantees for success in discrete combinatorial settings.
Summary updated