Manipulating Predictions over Discrete Inputs in Machine Teaching

Xiaodong Wu, Yufei Han, Hayssam Dahrouj, Jianbing Ni, Zhenwen Liang, Xiangliang ZhangarXiv 2024 · DOI · arXiv

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:

  1. Teacher Dataset Construction: The teacher identifies influential base samples from the training set using k-nearest neighbors (k-NN) with Jaccard distance.
  2. 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.
  3. 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.

Figure 2: CSR-Improve vs Sample Percentage (MALWARE). DMT reaches high success rates much faster than continuous-domain adaptations like Frogs or Witch's Brew.

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.

Figure 4: CSR-Poison vs Sample Percentage (MALWARE). DMT-align reaches 100% success while baselines fail to impact the discrete features effectively.

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

Abstract

Machine teaching often involves the creation of an optimal (typically minimal) dataset to help a model (referred to as the `student') achieve specific goals given by a teacher. While abundant in the continuous domain, the studies on the effectiveness of machine teaching in the discrete domain are relatively limited. This paper focuses on machine teaching in the discrete domain, specifically on manipulating student models' predictions based on the goals of teachers via changing the training data efficiently. We formulate this task as a combinatorial optimization problem and solve it by proposing an iterative searching algorithm. Our algorithm demonstrates significant numerical merit in the scenarios where a teacher attempts at correcting erroneous predictions to improve the student's models, or maliciously manipulating the model to misclassify some specific samples to the target class aligned with his personal profits. Experimental results show that our proposed algorithm can have superior performance in effectively and efficiently manipulating the predictions of the model, surpassing conventional baselines.
BibTeX
@misc{wu2024manipulating,
  author = {Xiaodong Wu and Yufei Han and Hayssam Dahrouj and Jianbing Ni and Zhenwen Liang and Xiangliang Zhang},
  title = {{Manipulating Predictions over Discrete Inputs in Machine Teaching}},
  year = {2024},
  eprint = {2401.17865},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2401.17865},
}
Figure