Boosting für den naiven Bayes-Klassifikator

Es gibt viele Bereiche, in denen sich die Neurowissenschaft und das maschinelle Lernen überlappen. Einer davon ist das Kombinieren des Lernens während mehrerer Lernepisoden mit kleinen Erfolgen, um am Ende ein daraus verschmolzenes, stärkeres, gelerntes Modell für eine bestimmte Aufgabe zu nutzen. Dieser Vorgang wird im maschinellen Lernen als "Boosting" (auf Deutsch "Verstärken") bezeichnet. Gerade in der IT-Branche ist das Entwickeln von Lösungen dieser Art ein sehr interessantes Thema, weshalb nachstehend eine kurze Einführung in das maschinelle Lernen erfolgen soll, die die Grundideen sowie die Anwendung des naiven Bayes-Klassifikators in R darstellt.

Grundidee

Vor allem in den 90er Jahren wurde in den Bereichen der Neurowissenschaft und des maschinellen Lernens intensiv über die Idee diskutiert, verschiedene Modelle aus Lernepisoden bei einer bestimmten Art von Aufgabe zu kombinieren (siehe Referenzen). Diese Lernprozesse stelle ich im Folgenden erst einmal kurz und intuitiv vor:

Es wird eine Aufgabe definiert, bei der inputspezifische Antworten vom Lerner erwartet werden. Musterinputs werden dem Lerner zusammen mit deren erwarteten Antworten für das Training gegeben (typischerweise ist dies im maschinellen Lernen eine Klassifizierungs- bzw. Regressionsaufgabe).
Bei einer ersten Lernepisode wird die Aufgabe nur mit kleinem bzw. "schwachem" Erfolg gelernt. Das heißt, dass die Anzahl von Fehlern noch nicht klein genug ist, um mit dem gelernten Modell zufrieden zu sein. Deshalb werden weitere Lernepisoden benötigt bzw. versucht.
Bei sukzessiven Lernepisoden konzentriert sich der Lerner vor allem darauf, die Fehler der vorherigen Lernepisode zu berücksichtigen. Daher wird jeder Lernepisode ein neugelerntes Modell zugewiesen, das sich aber im Großen und Ganzen nicht stark von den Vorgängern unterscheidet. Auf diese Weise kann das Lernen innerhalb der Episode und dank vorheriger Erfahrungen aus den Daten unter Umständen erfolgreicher werden. Der Lerneffekt wird aber immer noch nicht auf dem Niveau sein, auf dem die Aufgabe vollkommen gemeistert wird. Im Grunde genommen werden mehrere über die Episoden gelernte, schwache Modelle gesammelt.
Nach allen absolvierten Lernepisoden verfügt der Lerner über die insgesamt gesammelten Erfahrungen und kann auf diese Weise alle schwachen Modelle zu einem stärkeren gelernten Endmodell kombinieren und verschmelzen. Diese Kombinierung muss aber optimalerweise die Erfolgsquote der einzelnen schwachen Modelle berücksichtigen. Das heißt, die Schwächsten unter den Schwachen haben weniger Gewicht für die endgültige Entscheidung des kombinierten Modells.
Umso mehr Lernepisoden (schwache Modelle) durchgeführt und berücksichtigt werden, umso eher sollte der Lerner in der Lage sein, bei der Aufgabe den gesamten Fehler "beliebig" zu reduzieren. Dies ist die direkte Konsequenz der Verringerung der Gesamtvarianz.

Der ursprüngliche Algorithmus, der die oben beschriebene Logik umfasst, wurde von Freund und Schapire (1996) entworfen und heißt "AdaBoost" (steht für "Adaptable Boosting" oder "anpassbare Verstärkung").

Boosted naiver Bayes-Klassifikator

Welche Voraussetzung für ein Modell gegeben sein muss, damit es "boosted" (verstärkt) werden kann? Ein "schwacher" Lerner muss die Lernepisoden durchführen. Das heißt, das Kriterium großer Varianz muss erfüllt werden (z. B. Entscheidungsbäume mit sehr niedriger Tiefe), denn das Boosting bei Modellen mit niedriger Varianz (siehe Referenzen) ist wirkungslos. Modelle des Bayesʼschen Lernens wurden damals in den 90er Jahren u. a. wegen ihrer eleganten mathematischen Formulierung und der experimentellen Übereinstimmungen hochgeschätzt. Heutzutage sind naive Bayes-Klassifikatoren als produktive Lösungen z. B. für die Identifizierung von E-Mail-Spam sehr bekannt und durchschaubar. Der naive Bayes-Klassifikator bietet sich als "schwaches" Modell an, um ihn mit dem AdaBoost-Algorithmus zu verstärken.

Nach einer kurzen Internetrecherche findet man zwar R-Pakete z. B. für das Boosting von Entscheidungsbäumen, aber nicht für den naiven Bayes-Klassifikator. Es gibt in der Literatur mehrere Varianten des AdaBoost-Algorithmus, aber ich habe mich diesmal dafür entschieden, den ursprünglichen "AdaBoost.M1" von Freund und Schapire mit dem naiven Bayes-Klassifikator in R zu programmieren. Dank der R-Syntax und der R-Pakete ist dies echt simpel und man lässt sich schnell von der Idee begeistern, den einfachen Klassifikator mit seiner verstärkten Version zu vergleichen.

Und hier ist mein Vergleich...

Problem: Klassifikation zweier Klassen {0, 1} mit 52 Merkmalen.

Datenquelle: Ich habe 1.000 Beobachtungen von 52 Prädiktoren ohne fehlende Werte und der Zielvariablen aus dem "Weight Lifting Exercises Dataset" selektiert. Diese Datensätze sind hier zugänglich und können, laut deren "CC BY-SA"-Lizenzierung, frei selektiert, verarbeitet und sowohl akademisch als auch kommerziell benutzt werden, solange die darauf basierenden Werke auch unter den Bedingungen von "CC BY-SA" veröffentlicht sind.

Datenaufbereitung: Die Datensätze wurden von Anfang an 70%/30% für Training und Test getrennt, derselbe Seed wurde immer benutzt etc.

Vergleichskriterium: "Accuracy" aus der R-Funktion "confusionMatrix()".

Ergebnisse:

1. Normaler naiver Bayes-Klassifikator:

nLearners = 1; Accuracy = 0.6500; 95% CI = (0.5931, 0.7039)

2. Boosted naiver Bayes-Klassifikator:

nLearners = 3; Accuracy = 0.6900; 95% CI = (0.6343, 0.7419) nLearners = 6; Accuracy = 0.7067; 95% CI = (0.6516, 0.7576) nLearners = 12; Accuracy = 0.7133; 95% CI = (0.6586, 0.7638) nLearners = 24; Accuracy = 0.7167; 95% CI = (0.6620, 0.7670)

Das Ergebnis mit den Testdaten war zwar nicht unerwartet, aber trotzdem sehr erfreulich. Das Gute ist, dass jeder meinen R-Code mit seinen eigenen Daten testen kann. Sogar die Klassifikationsmethode kann durch eine andere dank des R-Pakets "caret" sehr schnell ersetzt und getestet werden!

Und hier unten füge ich noch meinen R-Code bei:

<pre>
#----- Initialisierung -----#

# Notwendige Pakete
library(ggplot2)
library(lattice)
library(MASS)
library(klaR)
library(caret)

# Loeschen vom alten Workspace
rm(list = ls())
gc()

# Arbeitsverzeichnis
setwd("C:/Users/UserName/Documents/ProjectFolder/")

# Parameter
set.seed(79)
dataFile = "bnb_sample_data.csv"
rootModName <- "mod_nb_class_"
extModName <- ".rda"
pDatSelTrain <- 0.7
trainMethod <- "cv"
kFolds <- 5
laplaceCorr <- 1
useKernEstim <- TRUE
plotVarsHists <- FALSE
nLearners <- 24

# Loeschen alter Modelle
file.remove(list.files(pattern = rootModName))

#----- Datenaufbereitung -----#

# Datenbeladung aus CSV-Datei
datFull <- read.csv(file = dataFile, header = TRUE, sep = ",",
                    na.strings = c("NA", ""))

# Dateneigenschaften
nDat <- length(datFull[[1]])
nFeat <- length(datFull)
iPred <- nFeat

# Datenexploration: Histogramme aller Variablen
if (plotVarsHists == TRUE) {
  graphics.off()
  for (i in 1:nFeat) {
    hist(datFull[, i],
         xlab = names(datFull)[i],
         main = paste("Histogram ", i, sep = "")) 
  }
}

# Setzen der Groesse der Trainingsdaten
iDatSel <- floor(pDatSelTrain*nDat)

# Trennung fuer Training und Test
datFull$unif_rnd_val <- runif(nDat, min = 0, max = 1)
datFullSort <- datFull[order(datFull[, (nFeat + 1)], decreasing = TRUE), ]
datTrain <- datFullSort[1:iDatSel, 1:nFeat]
datTest <- datFullSort[(iDatSel + 1):nDat, 1:nFeat]

# Festlegung der Zielvariablen als Klassen
datTrain[, iPred] <- factor(datTrain[, iPred])
datTest[, iPred] <- factor(datTest[, iPred])

# Dateneigenschaften
nDatTrain <- dim(datTrain)[1]
nDatTest <- dim(datTest)[1]

# Zusammenfassung der Trainings- und Testdatensaetze
#summary(datTrain)
#summary(datTest)

#----- Modelltraining -----#

# Modelltuning
modSel <- trainControl(method = trainMethod, number = kFolds)
modTun <- data.frame(.fL = laplaceCorr, .usekernel = useKernEstim)

# Initialisieren der Wahrscheinlichkeiten der Beobachtungen
pObs <- rep(1.0/nDatTrain, nDatTrain)
Beta <- c()

# Trainieren der Modelle mit AdaBoost.M1
for (j in 1:nLearners) {

       # Ziehe Stichprobe mit Zuruecklegen nach den pObs
       indWhgtXj <- sample(seq(1:nDatTrain), nDatTrain, replace = TRUE, prob = pObs)
       wghtXj <- datTrain[indWhgtXj, ]

       # Training des Modells mit Kreuzvalidierung
       modNBClass <- train(classes ~ .,
                           data = wghtXj,
                           method = "nb",
                           tuneGrid = modTun,
                           trControl = modSel)
       #print(modNBClass)
       #print(modNBClass$finalModel)

       # Rechnen der Modellvorhersagen
       predNBClass <- predict(modNBClass, datTrain)

       # Rechnen der Fehlerrate
       Ejt <- abs(as.numeric(as.character(predNBClass))    
                  as.numeric(as.character(datTrain$classes)))
       rm(predNBClass)
       Ej <- sum(pObs*Ejt)

       # Wenn Fehlerrate > 1/2, dann Training mit bereits gelernten Modellen beenden
       if (Ej > 0.5) {
              nLearners <- j - 1
              print(paste("Adaptives Lernen beendet. Error = ", Ej, "; Anzahl Lerner = ",
                          nLearners, sep = ""))
              break
       }
       # Ansonsten Gewichte der Beobachtungen lernen und Modell speichern
       else {
             # Rechnen der Lernrate
             Beta[j] <- Ej/(1.0 - Ej)

             # Reduzieren der Gewichte nur fuer richtige Vorhersagen
             pObs <- (1.0 - Ejt)*Beta[j]*pObs + Ejt*pObs

             # Normalisieren der Wahrscheinlichkeiten der Beobachtungen
             pObs <- pObs/sum(pObs)

             # Speichern des trainierten Modells in eine R-Datei
             thisModFile <- paste(rootModName, j, extModName, sep = "")
             save(modNBClass, file = thisModFile)
             rm(modNBClass)
       }
}

#----- Modelltesting -----#

# Testen der Modelle mit AdaBoost.M1
wghtPredNBClass <- rep(0, nDatTest)
for (j in 1:nLearners){
       # Gelerntes Modell wieder abholen
       thisModFile <- paste(rootModName, j, extModName, sep = "")
       load(thisModFile)

       # Vorhersage des gelernten Modells
       predNBClass <- predict(modNBClass, datTest)
       rm(modNBClass)

       # Kombinieren der Modelle
       if (nLearners >= 2) {
             # Vorhersage mit Gewichtung des gelernten Modells
             wghtPredNBClass <- wghtPredNBClass +
                                log(1.0/Beta[j])*as.numeric(as.character(predNBClass))
       }

       else {
             # Nicht boosted Vorhersagen
             wghtPredNBClass <- as.numeric(as.character(predNBClass))
       }
       rm(predNBClass)
}

# Normierung der Vorhersagen, wenn mehrere Modelle
if (nLearners >= 2) {
       wghtPredNBClass <- wghtPredNBClass/sum(log(1.0/Beta))
}

# Umsetzung wieder in Klassen
totPredNBClass <- as.factor(as.integer(wghtPredNBClass > 0.5))

# Zeigen der Wahrheitsmatrix
print(nLearners)
confusionMatrix(totPredNBClass, datTest$classes, positive = "1")

#----- Ende der Routine! -----#</pre>

Referenzen

Boosting and Naïve Bayesian Learning. Elkan, Technical Report UC San Diego, 1997.
Interpretable Boosted Naïve Bayes Classification. Ridgeway et al., KDD-98 Proceedings, 1998.
Maschinelles Lernen. Alpaydin, Oldenbourg Verlag, 2008.
Implementation of Naive Bayesian Classifier and Ada-Boost Algorithm Using Maize Expert System. Korada et al., IJIST, 2012.