Part Three: Implement cross$\_$validation $[$Graded$]$

Use grid$\_$search to implement the cross$\_$validation function, which takes in the training set xTr$,$ yTr$,$ a list of depth candidates depths and performs $$k$-$Fold Cross Validation on the training set.

We will use generate$\_$kFold to generate the $$k training$/$validation splits and pass in the indices for the splits to the cross$\_$validation function. Therefore, for each $($training$\_$indices, validation$\_$indices$)$ element in indices, you need to perform grid search to find the training and validation loss for each depth for that fold. Finally, take the average training and validation loss across folds to get the "average" loss. Your implementation should return these $2$ loss vectors and the depth with the minimum average validation loss.

I've already written generate$\_$kFold and grid$\_$search, but I$\text{'}$m having trouble piecing them together in code for cross$\_$validation. Here's what I have for the first two functions:

def generate$\_$kFold$($n$,$ k$)$:

$"""$

Generates $[($training$\_$indices, validation$\_$indices$),...]$ for k$-$fold validation.

Input:

n: number of training examples

k: number of folds

Output:

kfold$\_$indices: a list of length k$.$ Each entry takes the form $($training indices, validation indices$)$

$"""$

assert k $>=2$

kfold$\_$indices $=[]$

# YOUR CODE HERE

indices $=$ np$.$arange$($n$)$

parts $=$ np$.$array$\_$split$($indices$,$ k$)$

for i in range$($k$)$:

validation$\_$indices $=$ parts$[$i$]$

training$\_$indices $=$ np$.$concatenate$($parts$[$:i$]+$ parts$[$i$+1$:$])$

kfold$\_$indices.append$(($list$($training$\_$indices$),$ list$($validation$\_$indices$)))$

return kfold$\_$indices

def grid$\_$search$($xTr$,$ yTr$,$ xVal, yVal, depths$)$:

$"""$

Calculates the training and validation loss for trees trained on xTr and validated on yTr with a number of depths.

Input:

xTr: nxd training data matrix

yTr: n$-$dimensional vector of training labels

xVal: mxd validation data matrix

yVal: m$-$dimensional vector of validation labels

depths: a list of len k of depths

Output:

best$\_$depth, training$\_$losses, validation$\_$losses

best$\_$depth: the depth that yields that lowest validation loss

training$\_$losses: a list of len k$.$ the i$-$th entry corresponds to the the training loss of the tree of depth$=$depths$[$i$]$

validation$\_$losses: a list of len k$.$ the i$-$th entry corresponds to the the validation loss of the tree of depth$=$depths$[$i$]$

$"""$

training$\_$losses $=[]$

validation$\_$losses $=[]$

best$\_$depth $=$ None

# YOUR CODE HERE

best$\_$loss $=$ float$(\text{'}$inf$\text{'})$

for depth in depths:

tree $=$ RegressionTree$($depth$=$depth$)$

tree.fit$($xTr$,$ yTr$)$

training$\_$loss $=$ square$\_$loss$($yTr$,$ tree.predict$($xTr$))$

validation$\_$loss $=$ square$\_$loss$($yVal$,$ tree.predict$($xVal$))$

training$\_$losses.append$($training$\_$loss$)$

validation$\_$losses.append$($validation$\_$loss$)$

if validation$\_$loss $<$ best$\_$loss:

best$\_$loss $=$ validation$\_$loss

best$\_$depth $=$ depth

return best$\_$depth, training$\_$losses, validation$\_$losses