Did I understand AdaBoost correctly? My mantra has always been that if you are not able to recreate something you haven't really understood it. In this manner I tried to implement the AdaBoost algorithm of Freund and Schapire
I used one of the original papers from Schapire and tried to implement it as close to the original as possible. I used the original pseudocode (as comments) and translated it into R:
library(rpart)
library(OneR)

maxdepth <- 1
T <- 100 # number of rounds

# Given: (x_1, y_1),...,(x_m, y_m) where x_i element of X, y_i element of {-1, +1}
myocarde <- read.table("http://freakonometrics.free.fr/myocarde.csv", head = TRUE, sep = ";")
#myocarde <- read.table("data/myocarde.csv", header = TRUE, sep = ";")
y <- (myocarde[ , "PRONO"] == "SURVIE") * 2 - 1
x <- myocarde[ , 1:7]
m <- nrow(x)
data <- data.frame(x, y)

# Initialize: D_1(i) = 1/m for i = 1,...,m
D <- rep(1/m, m)

H <- replicate(T, list())
a <- vector(mode = "numeric", T)
set.seed(123)

# For t = 1,...,T
for(t in 1:T) {
  # Train weak learner using distribution D_t
  # Get weak hypothesis h_t: X -> {-1, +1}
  data_D_t <- data[sample(m, 10*m, replace = TRUE, prob = D), ]
  H[[t]] <- rpart(y ~., data = data_D_t, maxdepth = maxdepth, method = "class")
  # Aim: select h_t with low weighted error: e_t = Pr_i~D_t[h_t(x_i) != y_i]
  h <- predict(H[[t]], x, type = "class")
  e <- sum(h != y) / m
  # Choose a_t = 0.5 * log((1-e) / e)
  a[t] <- 0.5 * log((1-e) / e)
  # Update for i = 1,...,m: D_t+1(i) = (D_t(i) * exp(-a_t * y_i * h_t(x_i))) / Z_t
  # where Z_t is a normalization factor (chosen so that Dt+1 will be a distribution) 
  D <- D * exp(-a[t] * y * as.numeric(h))
  D <- D / sum(D)
}
# Output the final hypothesis: H(x) = sign(sum of a_t * h_t(x) for t=1 to T)
newdata <- x
H_x <- sapply(H, function(x) as.numeric(as.character(predict(x, newdata = newdata, type = "class"))))
H_x <- t(a * t(H_x))
pred <- sign(rowSums(H_x))

#H
#a
eval_model(pred, y)
## 
## Confusion matrix (absolute):
##           Actual
## Prediction -1  1 Sum
##        -1   0  1   1
##        1   29 41  70
##        Sum 29 42  71
## 
## Confusion matrix (relative):
##           Actual
## Prediction   -1    1  Sum
##        -1  0.00 0.01 0.01
##        1   0.41 0.58 0.99
##        Sum 0.41 0.59 1.00
## 
## Accuracy:
## 0.5775 (41/71)
## 
## Error rate:
## 0.4225 (30/71)
## 
## Error rate reduction (vs. base rate):
## -0.0345 (p-value = 0.6436)

So far, so good... what I find strange is that when I compare it to AdaBoost packages my results are wanting accuracy wise:
library(JOUSBoost)
## JOUSBoost 2.1.0
boost <- adaboost(as.matrix(x), y, tree_depth = maxdepth, n_rounds = T)
pred <- predict(boost, x)
eval_model(pred, y)
## 
## Confusion matrix (absolute):
##           Actual
## Prediction -1  1 Sum
##        -1  29  0  29
##        1    0 42  42
##        Sum 29 42  71
## 
## Confusion matrix (relative):
##           Actual
## Prediction   -1    1  Sum
##        -1  0.41 0.00 0.41
##        1   0.00 0.59 0.59
##        Sum 0.41 0.59 1.00
## 
## Accuracy:
## 1 (71/71)
## 
## Error rate:
## 0 (0/71)
## 
## Error rate reduction (vs. base rate):
## 1 (p-value < 2.2e-16)

My question
Is there something that I misunderstood concerning the algorithm? Or do the other implementation just use some "tricks" (which?) to tune their results?
 A: First of all, your understanding is fine. There were some minor points in the code that I think they overall accumulated to some quirky results.


*

*Bagging. It seems you are bagging as well as boosting. That is not part of the original algorithm and is unnecessary here too. I appreciate that you did this because you thought that rpart could not take weights so you oversampled to compensate that. (Realistically, a base learner has to use weights in a straightforward manner to be useful for Adaboost.)

*Not weighting the error. As mentioned in my comment, thee paper says "select $h_t$ with low weighted error". So we want something like: sum( (h!=y) * D)... I am with you on this, it is far from crystal clear in the paper, the Wikipedia entry on adaboost is much more explicit about it.

*Casting factors to numeric incorrectly. exp(-a[t] * y * as.numeric(h)) should be exp(-a[t] * y * as.numeric(as.character( h))). It is clear you noticed this later when evaluating the learners, but you forgot to fix this inside the loop. (Even the greats do mistakes!)


I think if you implement these changes you will get an Adaboost code implementation that is really close to the one of the paper. I append a snippet with the fixes below; it leads to 100% accuracy as with the reference implementation in JOUSBoost. I think the only methodological point you missed was about the weighting of the error, which is indeed a bit unclear in the paper.
...
set.seed(123) 

data_D_t <- data

# For t = 1,...,T
for(t in 1:T) { 
  H[[t]] <- rpart(y ~., data = data_D_t, maxdepth = maxdepth, 
                  method = "class", weights = D)
  h <- predict(H[[t]], x, type = "class")
  e <- sum( (h != y) * D) 
  a[t] <- 0.5 * log((1-e) / e) 
  D <- D * exp(-a[t] * y * as.numeric(as.character(h) ) ) 
  D <- D / sum(D) 
}
# Output the final hypothesis: H(x) = sign(sum of a_t * h_t(x) for t=1 to T)
newdata <- x
H_x <- sapply(H[seq(t)], function(x)
         as.numeric(as.character(predict(x, newdata = newdata, type = "class"))))
H_x <- t(a[seq(t)] * t(H_x))
...

