InnovationQ will be updated on Sunday, Oct. 22, from 10am ET - noon. You may experience brief service interruptions during that time.
Browse Prior Art Database

A Method for Classification in which Data might be Subject to Manipulation

IP.com Disclosure Number: IPCOM000242170D
Publication Date: 2015-Jun-22
Document File: 4 page(s) / 43K

Publishing Venue

The IP.com Prior Art Database


Disclosed is a method to prevent user manipulation of data classification in machine learning.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 45% of the total text.

Page 01 of 4

A Method for Classification in which Data might be Subject to Manipulation

Entities that rely on classification algorithms for making decisions often face the problem that data provided by interested parties may be manipulated, in view of the classification algorithm, to benefit the interested parties. This kind of behavior by interested parties is often referred to as gaming. Therefore, the party designing the classifier has to take into account that the choice of classifier might cause a change in the values of some attributes in order to benefit an interested. The party designing the classifier therefore has to make a good choice with respect to this situation.

Learning and classification are modeled as a sequential two-player game between a jury , which learns a classifier, and a contestant , which receives an input to the classifier, drawn from an unknown distribution. Before being classified by the

jury, the contestant may change the associated input based on revealed information about the jury's classifier. However, the contestant incurs a cost for these changes according to a cost function known to both players. The jury's goal is to achieve high classification accuracy with respect to a known target function and the contestant's original input. Moreover, it is assumed that the contestant plays the best response to the jury's action (i.e. a strategy that maximizes the contestant's payoff, given jury's move). The contestant's payoff is determined by the associated classification outcome and the cost of achieving it. For certain cost functions, the optimum score can be approximated arbitrarily closely.

The deterioration of prediction accuracy due to unforeseen events is often described as concept drift, which arises in a

number of contexts. A sequence of works on adversarial learning is motivated by the question of learning in the presence of an adversary that tampers with the examples of a learning algorithm. Typical application examples in this line of work include intrusion detection and spam fighting.

The novel method introduced herein stems from a game-theoretic modeling of the situation. Recent work considers alternative game-theoretic notions. [1] A notable difference with the setup is that current approaches define the

equilibrium with respect to the sample, while the novel method defines it with respect to the underlying distribution. The definition here provides generalization bounds. Beyond this difference, the existing methods focus on learning-centered linear classifiers when the Euclidean squared norm is the cost function. The Euclidean norm is not separable; therefore, the results here are incomparable.

The following two algorithms summarize the novel method.

Algorithm 1: A gaming-robust classification algorithm for separable cost functions


Page 02 of 4

1. Inputs: Labeled examples (x1,h(x1)),...,(xm,h(xm)) from xi ~ D i.i.d.

Also, a description of a separable cost function c(x;y) = max { 0; c2(y) - c1(x) }....