HEADS - HIDA - Learn: Concept Drift

Introduction

knitr::opts_chunk$set(tidy.opts = list(width.cutoff = 60), tidy = TRUE)
library(cowplot)

Most of the time, machine learning algorithms need to learn from continuous data, ultimately an infinite amount of data. It is only natural to believe that these data will change over time, and what is now relevant, may not be in the future. So there is a need to understand when the data is changing.

Concept Drift Detection

Assuming prior knowledge of the terms used in stream learning, Drift Detection is the step of a continuous evaluation of the model error. When this error exceeds a threshold, de drift detector returns a signal informing the model that the context has changed and it must adapt to the new data distribution.

Figure 1 depicts a simple diagram showing where the detection plays its role.

Here we will simulate a concept drift using two gaussian distributions and moving one of them towards the other. We will use a simple KNN algorithm and at certain point we expect that it starts to misclassify new points. This is where the drift detector must raise a signal.

We will make 10^5 iterations, and the KNN algorithm will have a window where the model will learn how to predict the next observation. Of course we could use an evolving algorithm to avoid the re-learning process, but this is beyond this assessment. Using a window size helps to minimize the computation burden and also introduces some kind of forgetting mechanism.

The baseline error rate is given by the formula \(p_i\) that means the probability of observe a misclassification, with standard deviation of \(s_i = \sqrt{p_i(1-p_i)/{i}}\), considering that the distribution is near normal for >30 observations, the confidence interval for \(p\) is \(pi\pm\alpha*s_i\).

At every step we will keep two values: \(p_{min}\) and \(s_{min}\), updating them whenever the current \(p_i+s_i\) reaches a new minimum. In this example, we will use an \(\alpha\) of 95%, and the drift detection will be flagged when \(p_i+s_i \ge p_{min}+2*s_{min}\).

n <- 10000 # number of iterations
drift_start <- 4000 # drift will start at this observation
drift_length <- 50 # drift will end after this amount of steps
from_mean <- 5 # the distribution will start on this mean
to_mean <- 2 # and will end on this mean
sd <- 0.5 # all distributions will have this std dev
window_size <- 100 # this is the window size of KNN
k <- 1 # number of neighbours considered
slow_drift <- seq(from_mean, to_mean, length.out = drift_length) # change sequence

#### 2 clusters dataset ----
set.seed(2020)
data <- rbind(
  matrix(rnorm(n, 0, sd), ncol = 2),
  matrix(c(rnorm(n / 2, 2, sd), rnorm(n / 2, from_mean, sd)), ncol = 2)
)
data <- cbind(data, rep(c(1, 2), each = n / 2))

plot(data[, 1], data[, 2], col = data[, 3], xlim = c(-5, 8), ylim = c(-4, 7),
     main = "Clusters Starting Point", ylab = "", xlab = "")

# mix the samples
set.seed(2020)
idxs_train <- sample(seq_len(nrow(data)))
data <- data[idxs_train, ]

#### prime the model ----
# learn the first window_size examples and do a classification
class <- knn(data[1:window_size, -3], data[(window_size + 1), -3], data[1:window_size, 3], k = k)

# is it wrong?
error <- data[(window_size + 1), 3] != class

pmin <- pi <- 0.5 # initial values
smin <- si <- sqrt(pi * (1 - pi) / window_size) # initial values

# Start the iterations starting from the next observation
set.seed(2020) # set seed again because the drift will use rng
alarm <- 0
pi_counter <- NULL
for (i in seq_len(n - window_size - 1)) {

  # First do the drift if it is time
  if ((i + window_size) >= drift_start) {
    # only drift the second class
    if (data[(window_size + i + 1), 3] == 2) {
      m <- ifelse((i + window_size) < drift_start + drift_length,
        slow_drift[i + window_size - drift_start + 1], tail(slow_drift, 1)
      )
      data[(window_size + i + 1), -3] <- c(rnorm(1, 2, sd), rnorm(1, m, sd))
    }
  }

  cl <- knn(data[(i + 1):(window_size + i), -3],
    data[(window_size + i + 1), -3],
    data[(i + 1):(window_size + i), 3],
    k = k
  )
  class <- c(class, cl)
  error <- c(error, cl != data[(window_size + i + 1), 3])

  er <- sum(error) # sum(tail(error, window_size))
  # update probability of failure
  pi <- er / i
  si <- sqrt(pi * (1 - pi) / window_size)
  pi_counter <- c(pi_counter, pi)

  if ((pi + si) < (pmin + smin)) {
    pmin <- pi
    smin <- si
  } else if ((pi + si) > (pmin + 2 * smin)) {
    if (alarm == 0) {
      alarm <- (i + window_size)
    }
    pmin <- pi
    smin <- si
  }
}

The following plot shows the error rate for the KNN classifier. The black line is the drift starting point, and the red line is the detection point.

plot(pi_counter, type = "l", main = "Drift Detection", xlab = "Time", ylab = "Error Rate")
abline(v = c(drift_start, alarm), col = c(1, 2))