RACOG

RACOG (Rapidly Converging Gibbs) iteratively builds badges of synthetic instances using minority given ones. But it rules out first burnin generated badges and from that moment onwards, it picks a badge of newly-generated examples each lag iterations.

wRACOG

The downside of RACOG is that it clearly depends on burnin, lag and the requested number of instances numInstances. wRACOG (wrapper-based RACOG) tries to overcome that problem. Let wrapper be a classifier, that could be declared as it follows:

myWrapper <- structure(list(), class = "C50Wrapper")
trainWrapper.C50Wrapper <- function(wrapper, train, trainClass){
  C50::C5.0(train, trainClass)
}

That is, a wrapper should be an S3 class with a method trainWrapper following the generic method:

trainWrapper(wrapper, train, trainClass, ...)

Furthermore, the result of trainWrapper must be a predict callable S3 class.

Another example of wrapper with a knn (which can get a little tricky, since it is a lazy classificator):

library("FNN")
myWrapper <- structure(list(), class = "KNNWrapper")

predict.KNN <- function(model, test){
  FNN::knn(model$train, test, model$trainClass)
}

trainWrapper.KNNWrapper <- function(wrapper, train, trainClass){
  myKNN <- structure(list(), class = "KNN")
  myKNN$train <- train
  myKNN$trainClass <- trainClass
  myKNN
}

where train is the unlabeled tranining dataset, and trainClass are the labels for the training set.

An example of call for this dataset may consist in splitting haberman dataset (provided by the package) into train and validation, and calling wracog with both partitions and any of the aforementioned wrappers:

data(haberman)

trainFold <- sample(1:nrow(haberman), nrow(haberman)/2, FALSE)
newSamples <- wracog(haberman[trainFold, ], haberman[-trainFold, ],
                     myWrapper, classAttr = "Class")
head(newSamples)

##   Age Year Positive    Class
## 1  54   61        5 positive
## 2  47   63        0 positive
## 3  49   65        0 positive
## 4  39   65        0 positive
## 5  72   58        0 positive
## 6  45   60        1 positive

Central limit theorem

Let W₁, …, W_m be a collection of independent and identically distributed random variables, with 𝔼(W_i) = μ and Var(W_i) = σ² < ∞. Hence: $$ \lim_{m} P\left[\frac{\sqrt{m}}{\sigma} \left(\underbrace{\frac{1}{m}\sum_{i=1}^m W_i}_{\overline{W}} - \mu \right) \le z \right] = \phi(z) $$

where ϕ is the distribution function of N(0, 1).

That is, $\frac{\overline{W} - \mu}{\sigma/\sqrt{m}} \rightarrow N(0,1)$ probability-wise.

Let S⁺ = {x_i = (w₁⁽ⁱ⁾, …w_d⁽ⁱ⁾)}_i = 1^m be the minority instances. Now, let’s fix some j ∈ {1, …d}, and let’s assume that j-ith column follows a numerical random variable W_j, with mean μ_j and standard deviation σ_j < ∞. Let’s compute $\sigma_j' = \sqrt{\frac{1}{m}\sum_{i=1}^m \left(w_j^{(i)} - \frac{\sum_{i=1}^m w_j^{(i)}}{m} \right)^2}$ the biased estimator for the standard deviation. It can be proven that instances generated with $\bar{w}_j = w_j^{(i)} - \frac{\sigma_j'}{\sqrt{m}}\cdot r, r\sim N(0,1)$ have the same sample mean as the original ones, and their sample variance tends to the original one.

Outline of the algorithm

Our algorithm will proceed as follows:

• For each numerical attribute j = 1, …, d compute the standard deviation of the column, $\sigma_j' = \sqrt{\frac{1}{m}\sum_{i=1}^m \left(w_j^{(i)} - \frac{\sum_{i=1}^m w_j^{(i)}}{m} \right)^2}$.
• For a given instance x_i = (w₁⁽ⁱ⁾, …, w_d⁽ⁱ⁾), for each attribute attribute j, generate:

$$ \bar{w}_j = \left\{\begin{array}{ll} w_j^{(i)} - \frac{\sigma_j'}{\sqrt{m}}\cdot r, r\sim N(0,1) & \textrm{if numerical attribute}\\ \textrm{pick uniformly over } \{w_j^{(1)}, \ldots w_j^{(m)}\} & \textrm{otherwise} \end{array}\right. $$

Motivation

Given a distribution function of a random variable X, namely F(x), if that function has an almost everywhere derivative, then, almost everywhere, it holds: $$ f(x) = \lim_{h\rightarrow 0} \frac{F(x+h) - F(x-h)}{2h} = \lim_{h\rightarrow 0} \frac{P(x-h < X \le x+h)}{2h} $$

Given random samples of X, X₁, …X_n, namely x₁, …x_n, an estimator for f could be the mean of samples in ]x − h, x + h[ divided by the length of the interval: $$ \widehat{f}(x) = \frac{1}{2hn} \bigg[\textrm{Number of samples } x_1, \ldots, x_n \textrm{ that belong to ]x-h, x+h[}\bigg] $$

If we define $\omega(x) = \left\{\begin{array}{ll} \frac{1}{2} &, |x| < 1\\ 0 & \textrm{otherwise} \end{array}\right.$

and $w_h(x) = w\left(\left|\frac{x}{h}\right|\right)$, then we could write f̂ as: $$ \widehat{f}(x) = \frac{1}{nh} \sum_{i=1}^n \omega_h(x-x_i) $$

It we assume that x₁, …, x_n are equidistant with distance 2h (they are placed in the middle of 2h length intervals), f̂ could be seen as an histogram where each bar has a 2h width and a $\frac{1}{2nh} \cdot \bigg[[\textrm{Number of samples } x_1, \ldots, x_n \textrm{ that belong to the interval}]\bigg]$ length. Parameter h is called bandwidth.

In multivariate case (d dimensional), we define: $$ \widehat{f}(x) = \frac{1}{nh^d} \sum_{i=1}^n \omega_h(x-x_i) $$

Kernel methods

If we took $w = \frac{1}{2} \Large{1}\normalsize_{]-1,1[}$, then f̂ would have jump discontinuities and we would have jump derivatives. On the other hand, we could took ω, where w ≥ 0, ∫_Ωω(x)dx = 1, Ω ⊆ X a domain, and w were even, and that way we could have estimators with more desirable properties with respect to continuity and differentiability.

f̂ can be evaluated through its MISE (Mean Integral Squared Error): $$ MISE(h) = \underset{x_1, \ldots, x_d}{\mathbb{E}} \int (\widehat{f}(x) - f(x))^2 dx $$

Example of kernel estimation

Search of optimal bandwidth

We take a first approximation to h as the value: $$ h_{Silverman} = \left(\frac{4}{m(d+2)}\right)^{\frac{1}{d+4}} $$ where d is number of attributes and m the size of the minority class.

Reshaping the equation of the cross validation function and differentiating:

And a straightforward gradient descendent algorithm is used to find a good h estimation.

Introduction to Game Theory

Let (P, T, f) be our game space. We would have a set of players, P = {1, …, n}, and T_i = {1, …, k_i}, set of feasible strategies for the i-th player, resulting in T = T₁ × … × T_n. We can easily assign a payoff to each player taking into account his/her own strategy as well as other players’ strategy. So f will be given by the following equation: $$ \begin{array}{rll} f: T &\longrightarrow& \mathbb{R}^n\\ t &\longmapsto& (f_1(t), \ldots, f_n(t)) \end{array} $$

t_−i will denote (t₁, …, t_i − 1, t_i + 1, …, t_n) and similarly we can denote f_i(t_i, t_−i) = f_i(t).

An strategic Nash equilibrium is a tuple (t₁, …, t_n) where f_i(t_i, t_−i) ≥ f_i(t′_i, t_−i) for every other t′ ∈ T, and all i = 1, …, n. That is, an strategic Nash equilibrium maximizes the payoff for all the players.

The strategy for each player will be picked with respect to a given probability: $$ \delta_i \in \Delta_i = \{(\delta_i^{(1)}, \ldots, \delta_i^{(k_i)}) \in (R^{+}_0)^{k_i} : \sum_{j=1}^{k_i} \delta_i^{(j)} = 1\} $$ We define Δ₁ × … × Δ_n := Δ and we call an element δ = (δ₁, …, δ_n) ∈ Δ an strategy profile. Having a fixed strategy profile δ, the overall payoff for the i-th player is defined as: u_i(δ) = ∑_{(t1, …, tn) ∈ T}δ_i^(t_i)f_i(t)

Given u_i the payoff for a δ strategy profile in the i-th player and δ ∈ Δ we will denote

A probabilistic Nash equilibrium is a strategy profile x = (δ₁, …, δ_n) verifying u_i(δ_i, δ_−i) ≥ u_i(δ′_i, δ_−i) for every other δ′ ∈ Δ, and all i = 1, …, n.

A theorem ensures that every game space (P, T, f) with finite players and strategies has a probabistic Nash equilibrium

Particularization to imbalance problem

Let S be the original training set, E the synthetic generated instances. Our players would be S ∪ E. Every player would be able to pick between two different strategies: 0 - being a negative instance - and 1 - being a positive instance -. Players of S would always have a fixed strategy, where the i-th player would have δ_i = (0, 1) (a 0 strategy) in case it is a negative instance or δ_i = (1, 0) (a 1 strategy) otherwise.

The payoff for a given instance is affected only by its own strategy and its k nearest neighbors in S ∪ E. That is, for every x_i ∈ E, we will have u_i(δ) = ∑_{j ∈ NN^k(x)}(x_i^Tw_ijx_j) where w_ij = g(d(x_i, x_j)) and g is a decreasing function (the further, the lower payoff). In our implementation, we have considered $g(z) = \frac{1}{1+z^2}$, with d the euclidean distance.

Each step should involve an update to the strategy profiles of instances of E. Namely, if x_i ∈ E, the following equation will be used:

That is, we are reinforcing the strategy that is producing the higher payoff, in detriment to the opposite strategy. This method has enough convergence guarantees.

Let’s recall the header for neater:

neater(dataset, newSamples, k, iterations, smoothFactor, classAttr)

Then a rough sketch of the algorithm is:

• Compute k nearest neighbors for every instance of E:=newSamples.
• Initialize strategy profiles of dataset∪newSamples.
• Iterate iterations times updating payoffs with the aforementioned rule and strategy profiles.
• Keep only those examples of newSamples with probability of being positive instances higher than 0.5.