#
# Implements ADABOOST with decision trees
#
# Written by:
# -- 
# John L. Weatherwax                2009-04-21
# 
# email: wax@alum.mit.edu
# 
# Please send comments and especially bug reports to the
# above email address.
#
# EPage 695
# 
#-----

source('decision_tree_learning.R')


draw_samples_according_to_weights = function( X, y, w ){
  #
  #
  #
  w = w / sum(w)

  N = length(y)
  
  inds = sample( seq(1,N), size=N, replace=TRUE, prob=w )

  return( list( X_samps=X[inds,], y_samps=y[inds] ) )
}



adaboost = function( X, y, M=50, max_depth=1 ){
  #
  # This implements the ADABOOST code from the book (using decision trees as the base learner).
  #
  # X: matrix with each row a case and each column a feature value (attribute value) for that case
  # y: a column vector with each row the TRUE/FALSE label for the corresponding row in X (can only be either TRUE/FALSE) 
  #
  N = length(y) # the number of data samples

  weights = rep( 1/N, N ) # initial weights to hold for each sample 
  hs = list() # holds each hypothesis as we create them
  zs = list() # holds the hypotheis weights which depends on how well this hypothesis performs on the data 

  # For decision_tree_learing we need some initial things: 
  # 
  # Create the initial attributes variable (an R list with items and keys as above):
  # Note our training set must have seen the possible values for each attribute.
  #
  attributes = list()
  for( cn in colnames(X) ){
    attributes[[cn]] = sort(as.matrix(unique(X[cn])))
  }

  # Compute the default classification: 
  #
  default = majority_vote(y) 

  # Begin adaboost iterations:
  #   
  for( m in 1:M ){

    # Draw samples (x,y) from training set according to weights:
    #
    res = draw_samples_according_to_weights( X, y, weights )
    X_boost = res$X_samps
    y_boost = res$y_samps

    # Learn a model using this boosted data:
    # 
    h = decision_tree_learning( X_boost, y_boost, attributes, default, max_depth=max_depth )
    hs[[m]] = h

    # Make predictions with this hypothesis:
    #
    h_prediction = rep( TRUE, 1, N )
    for( j in 1:N ){
      h_prediction[j] = decision_tree_predict_single_sample( h, X[j,] )
    }

    # Accumulate the error:
    # 
    error = 0
    for( j in 1:N ){
      if( h_prediction[j] != y[j] ){ 
        error = error + weights[j]
      }
    }

    # Modify the weights (if we have a nonzero error):
    # 
    for( j in 1:N ){
      if( h_prediction[j] == y[j] & error != 0 ){
        weights[j] = weights[j] * error / ( 1 - error ) 
      }
    }
    weights = weights / sum( weights )

    # Update the weight to use with this hypothesis:
    # 
    zs[[m]] = log( ( 1-error )/error )
  }

  return( list( trees=hs, tree_votes=zs ) )
}


adaboost_predict_single_sample = function( boosted_trees, x ){

  weights = boosted_trees$tree_votes
  hypothesis = boosted_trees$trees

  wgt_for_TRUE  = 0
  wgt_for_FALSE = 0 
  for( j in 1:length(weights) ){
    if( decision_tree_predict_single_sample( hypothesis[[j]], x )==TRUE ){
      wgt_for_TRUE = wgt_for_TRUE + weights[[j]] 
    }else{
      wgt_for_FALSE = wgt_for_FALSE + weights[[j]]
    }
  }

  if( wgt_for_TRUE > wgt_for_FALSE ){
    return(TRUE)
  }else{
    return(FALSE)
  }
}


adaboost_predict_multiple_samples = function( boosted_trees, X ){
  #
  # Predicts TRUE/FALSE label for a many samples using a decision tree
  # Note: I was not sure how to code the prediction algorithm in a vectorized way.
  # If anyone knows how to do such a thing please contact me.
  #
  n_samples = dim(X)[1]
  y = rep( FALSE, n_samples ) # some initial values 
  for( si in 1:n_samples ){
    y[si] = adaboost_predict_single_sample( boosted_trees, X[si,] )
  } 
  return(y)
}