<a href="https://colab.research.google.com/github/LillithChute/CS6140ML/blob/main/assignment1/assignment_1_problem_statement.ipynb" target="_parent"></a>

# CS 6140 Machine Learning: Assignment - 1 (Total Points: 100)
## Prof. Ahmad Uzair 

### Q1. Classification Trees with numerical features (45 points)

### Datasets used for the problem:

Iris: has three classes and the task is to accurately predict one of the three sub-types of the Iris flower given four different physical features. These features include the length and width of the sepals and the petals. There are a total of 150 instances with each class having 50 instances.

### Growing Decison Trees 
Decision Trees (DTs) are a non-parametric supervised learning method used for classification and regression. The goal of this question in the assignment is to create a model that predicts the value of a target variable by learning simple decision rules inferred from the data features. 

<i>Note: Write in your code only in the place holders where you are instructed to, replacing None.<i>


```python
# Do not change the code in this cell
import pandas as pd
import numpy as np
import matplotlib.pyplot as plt
%matplotlib notebook
```

### Here is the first look at your dataset and its feature columns


```python
# Do not change the code in this cell
iris_data = pd.read_csv("iris.csv")
```


```python
# Do not change the code in this cell
iris_data.drop("Id", axis=1, inplace=True)
```


```python
# Do not change the code in this cell
iris_data.head()
```


```python
# Do not change the code in this cell
iris_data.info()
```


```python
# Do not change the code in this cell
iris_data.describe()
```

### Task
Shuffle the data and change the categorical features mentioned in the species column to numeric


```python
# Start code here
# Replace the categorical target values in the Species column to numeric

# Shuffle the data
iris_data = None
# End code here
```


```python
# Do not change the code in this cell
iris_data.head()
```

### Task
Time to code your decision tree.

In the following cell, create a node class for your Decision Tree Classifier having the following attributes:
feature_index, threshold, left, right, info_gain, value, where the condition upon which the decision will be based would be defined by feature_index and threshold, while the attributes left and right will be for accessing the left and the right child of a particular node other than the leaf node in the decision tree. info_gain will denote the information gained by the split denoted by the particular decision node. The value attribute will be holding the value of the majority class of the leaf node without having the other attributes. This will help us to determine the class of new data point.


```python
class Node:  
    def __init__(self, feature_index=None, threshold=None, left=None, right=None, info_gain=None, value=None):
        # Start code here
        # for decision node
        self.feature_index = None
        self.threshold = None
        self.left = None
        self.right = None
        self.info_gain = None
        
        # for leaf node
        self.value = None
    # End code here
```

### Task
In the following cell, you will create a Decision Tree Classifier from scratch class having the following attributes: root, min_samples_split, max_depth. Other instructions have been given in doc strings and comments


```python
class DecisionTreeClassifier:
    def __init__(self, min_samples_split=2, max_depth=2):
        # Start code here
        # Initialize the root of the decision tree to traverse through the decision tree to None
        self.root = None
        # initialize the stopping conditions
        self.min_samples_split = None
        self.max_depth = None
        # End code here 
        
        
    def build_tree(self, dataset, curr_depth = 0):
        """
        This will be a recursive function to build the decision tree.
        dataset: The data that you will be using for your assignment
        curr_depth: Current depth of the tree
        Returns the leaf node
        """
        # Start code here
        # Separate the features and targets into two variables X and Y
        X, Y = None
        # Extract the number of samples and number of features
        num_samples, num_features = None
        
        # split until stopping conditions are met
        if num_samples >= self.min_samples_split and curr_depth <= self.max_depth:
            # finding the best split
            best_split = None
            # check if information gain is positive
            if best_split["info_gain"] > 0:
                # recur left
                left_subtree = None
                # recur right
                right_subtree = None
                # return the decision node in the form of a dictionary
                return Node(best_split["feature_index"], best_split["threshold"],
                           left_subtree, right_subtree, best_split["info_gain"])
        # compute leaf node
        leaf_value = self.calculate_leaf_value(Y)
        # End code here
        return Node(value=leaf_value)
    
        
    def get_best_split(self, dataset, num_samples, num_features):
        """
        Function to find out the best split
        dataset: input data
        num_samples: Number of samples present in the dataset
        num_features: Number of features in the dataset
        Returns the best split
        """
        
        # dictionary to store the best split
        best_split = {}
        max_info_gain = -float("inf")
        
        # Start code here
        # loop over all the features in the data
        for feature_index in range(num_features):
            feature_values = None
            # Hint: You can use np.unique function to retrieve the values of the possible threshold
            possible_thresholds = None
            # loop over all the feature values present in the data
            for threshold in possible_thresholds:
                # get current split
                dataset_left, dataset_right = None
                # check if children are not null
                if len(dataset_left) > 0 and len(dataset_right) > 0:
                    y, left_y, right_y = None
                    # compute information gain
                    curr_info_gain = None
                    # update the best split if needed
                    if curr_info_gain > max_info_gain:
                        best_split["feature_index"] = None
                        best_split["threshold"] = None
                        best_split["dataset_left"] = None
                        best_split["dataset_right"] = None
                        best_split["info_gain"] = None
                        max_info_gain = None
        # End code here

        return best_split
                    
                    
    def split(self, dataset, feature_index, threshold):
        """
        Function to split the data to the left child and right child in the decision tree
        dataset: input data
        feature_index: feature index used to locate the index of the feature in a particular row in the dataset
        threshold: threshold value based on which the split will be calculated
        Returns the left and right datavalues from the dataset
        """
        # Start code here
        # Hint: Use list comprehension to distinguish which values would be present in left and right 
        # subtree on the basis of threshold
        dataset_left = None
        dataset_right = None
        # End code here
        return dataset_left, dataset_right
        
        
    def information_gain(self, parent, l_child, r_child, mode="entropy"):
        """
        Function to calculate information gain. This function subtracts the combined information 
        of the child node from the parent node.
        parent: value of parent node
        l_child: value of left child node
        r_child: value of right child node
        mode: based on which information gain will be calculated either entropy/gini index
        Returns the information gain
        """
        # Start code here
        # Calculate the relative sizes of the child node with respect to the parent node
        weight_l = None
        weight_r = None
        # Calculate gain on the with respect to the information gain parameter which will either be 
        # gini_index or entropy
        if mode == "gini":
            gain = None
        else:
            gain = None
        # End code here
        return gain
    
    
    def entropy(self, y):
        """
        Function to calculate the entropy
        y: target labels
        Returns entropy
        """
        # Start code here
        # Extract the class labels
        class_labels = None
        # Initialize the entropy
        entropy = None
        # Calculate the entropy
        for cls in class_labels:
            p_cls = None
            entropy = None
        # End code here
        return entropy
    
    
    def gini_index(self, y):
        """
        Function to calculate gini index
        y: target labels
        Returns gini index
        """
        # Extract the class labels
        class_labels = np.unique(y)
        # Initialize the gini_index
        gini = 0
        # Calculate the gini index
        for cls in class_labels:
            p_cls = len(y[y==cls]) / len(y)
            gini += p_cls ** 2
        return 1 - gini
    
    
    def calculate_leaf_value(self, Y):
        """
        Function to compute thr value of leaf node
        Y: target labels
        Returns leaf node value
        """
        # Start code here
        # Return the most occuring element in Y. Hint: you can use lists 
        Y = None
        return None
        # End code here
    
    def print_tree(self, tree = None, indent = " "):
        """
        Function to print the tree. Use the pre-order traversal method to print the decision tree.
        # Do not make any changes in this function
        """
        
        if not tree:
            tree = self.root
        
        if tree.value is not None:
            print(tree.value)
            
        else:
            print("X " + str(tree.feature_index), "<=", tree.threshold, "?", tree.info_gain)
            print("%sleft:" % (indent), end = " ")
            self.print_tree(tree.left, indent + indent)
            print("%sright" % (indent), end = " ")
            self.print_tree(tree.right, indent + indent)
            
            
    def fit(self, X, Y):
        """
        Function to train the tree.
        X: Features
        Y: Target
        """
        # Start code here
        # Concatenate X, Y to create the dataset and call the build_tree function recursively
        dataset = None
        self.root = None
        # End code here
        
    
    def predict(self, X):
        """
        Prediction function to calculate the all the predictions of the matrix of features 
        provided using make_predictions function
        X: Matrix of features
        Returns predictions using the make_predictions function
        """
        # Start code here
        predictions = None
        # End code here
        return predictions
    
    
    def make_predictions(self, x, tree):
        """
        Function to predict a single datapoint
        x: data
        tree: current tree
        Returns predictions
        """
        # Start code here
        # return the value if the node is a leaf node
        if tree.value != None:
            return None
        # Extract feature values of a new datapoint at a given feature index
        feature_val = None
        # Recur through left or right subtree 
        None
      # End code here
 
```

### Evaluating the model


```python
# Do not change the code in this cell
X = iris_data.iloc[:, :-1].values
Y = iris_data.iloc[:, -1].values.reshape(-1, 1)
from sklearn.model_selection import train_test_split
X_train, X_test, Y_train, Y_test = train_test_split(X, Y, test_size=0.2, random_state = 41)
classifier = DecisionTreeClassifier(min_samples_split=3, max_depth=3)
classifier.fit(X_train, Y_train)
classifier.print_tree()
y_pred = classifier.predict(X_test)
from sklearn.metrics import accuracy_score
print("Accuracy is: "+str(accuracy_score(Y_test, y_pred)))
```

### Q2. Regression (35 points)
Linear regression attempts to model the relationship between two variables by fitting a linear equation to observed data. One variable is considered to be an explanatory variable, and the other is considered to be a dependent variable. 

Ridge regression is a method of estimating the coefficients of multiple-regression models in scenarios where independent variables are highly correlated. 

Gradient descent is a first-order iterative optimization algorithm for finding a local minimum of a differentiable function. The idea is to take repeated steps in the opposite direction of the gradient (or approximate gradient) of the function at the current point, because this is the direction of steepest descent.

The goal of this question in the assignment is to create a model that predicts the value of a target variable by learning the relationship between independent and its corresponding dependent variable using linear regression, ridge regression and gradient descent.  

<i>Note: Write in your code only in the place holders where you are instructed to, replacing None.<i>

## Gradient descent algorithm 
\begin{equation}
\theta^{+} = \theta^{-} + \frac{\alpha}{m} (y_{i} - h(x_{i}) )\bar{x}
\end{equation}

This minimizes the following cost function

\begin{equation}
J(x, \theta, y) = \frac{1}{2m}\sum_{i=1}^{m}(h(x_i) - y_i)^2
\end{equation}

where
\begin{equation}
h(x_i) = \theta^T \bar{x}
\end{equation}


```python
# Do not change the code in this cell
true_slope = 15
true_intercept = 2.4
input_var = np.arange(0.0,100.0)
output_var = true_slope * input_var + true_intercept + 300.0 * np.random.rand(len(input_var))
```


```python
# Do not change the code in this cell
plt.figure()
plt.scatter(input_var, output_var)
plt.xlabel('x')
plt.ylabel('y')
plt.show()
```


```python
def compute_cost(ip, op, params):
    """
    Cost function in linear regression where the cost is calculated
    ip: input variables
    op: output variables
    params: corresponding parameters
    Returns cost
    """
    # Start code here
    num_samples = None
    cost_sum = None
    for x,y in zip(ip, op):
        y_hat = None
        cost_sum = None
    
    cost = None
    # End code here
    return cost
```


### Batch gradient descent
Algorithm can be given as follows:

```for j in 0 -> max_iteration: 
    for i in 0 -> m: 
        theta += (alpha / m) * (y[i] - h(x[i])) * x_bar
```


```python
def linear_regression_using_batch_gradient_descent(ip, op, params, alpha, max_iter):
    """
    Compute the params for linear regression using batch gradient descent
    ip: input variables
    op: output variables
    params: corresponding parameters
    alpha: learning rate
    max_iter: maximum number of iterations
    Returns parameters, cost, params_store
    """ 
    # Start code here
    # initialize iteration, number of samples, cost and parameter array
    iteration = None
    num_samples = None
    cost = None
    params_store = None
    
    # Compute the cost and store the params for the corresponding cost
    while iteration < max_iter:
        cost[iteration] = None
        params_store[:, iteration] = None
        
        print('--------------------------')
        print(f'iteration: {iteration}')
        print(f'cost: {cost[iteration]}')
        
        # Apply batch gradient descent
        for x,y in zip(ip, op):
            y_hat = None
            gradient = None
            params = None
            
        iteration = None
    # End code here
    
    return params, cost, params_store
```


```python
# Do not change the code in this cell
# Training the model
from sklearn.model_selection import train_test_split
x_train, x_test, y_train, y_test = train_test_split(input_var, output_var, test_size=0.20)

params_0 = np.array([20.0, 80.0])

alpha_batch = 1e-3
max_iter = 500
params_hat_batch, cost_batch, params_store_batch =\
    linear_regression_using_batch_gradient_descent(x_train, y_train, params_0, alpha_batch, max_iter)
```

### Stochastic Gradient Descent
Algorithm can be given as follows:
```shuffle(x, y)
for i in 0 -> m:
    theta += (alpha / m) * (y[i] - h(x[i])) * x_bar  
```


```python
def linear_regression_using_stochastic_gradient_descent(ip, op, params, alpha):
    """
    Compute the params for linear regression using stochastic gradient descent
    ip: input variables
    op: output variables
    params: corresponding parameters
    alpha: learning rate
    Returns parameters, cost, params_store
    """
    # Start code here
    # initialize iteration, number of samples, cost and parameter array
    num_samples = None
    cost = None
    params_store = None
    
    i = 0
    # Compute the cost and store the params for the corresponding cost
    for x,y in zip(input_var, output_var):
        cost[i] = None
        params_store[:, i] = None
        
        print('--------------------------')
        print(f'iteration: {i}')
        print(f'cost: {cost[i]}')
        
        # Apply stochastic gradient descent
        y_hat = None
        gradient = None
        params = None
        
        i = None
            
    return params, cost, params_store
```


```python
# Do not change the code in this cell
alpha = 1e-3
params_0 = np.array([20.0, 80.0])
params_hat, cost, params_store =\
linear_regression_using_stochastic_gradient_descent(x_train, y_train, params_0, alpha)
```


```python
plt.figure()
plt.scatter(x_test, y_test)
plt.plot(x_test, params_hat_batch[0] + params_hat_batch[1]*x_test, 'g', label='batch')
plt.plot(x_test, params_hat[0] + params_hat[1]*x_test, '-r', label='stochastic')
plt.xlabel('x')
plt.ylabel('y')
plt.legend()
plt.show()
print(f'Batch      T0, T1: {params_hat_batch[0]}, {params_hat_batch[1]}')
print(f'Stochastic T0, T1: {params_hat[0]}, {params_hat[1]}')
# Calculate Root Mean Square error in batch gradient descent algorithm and stochastic gradient descent algorithm
rms_batch = None
rms_stochastic = None
print(f'Batch RMS:      {rms_batch}')
print(f'Stochastic RMS: {rms_stochastic}')
```


```python
# Do not change the code in this cell
plt.figure()
plt.plot(np.arange(max_iter), cost_batch, 'r', label='batch')
plt.plot(np.arange(len(cost)), cost, 'g', label='stochastic')
plt.xlabel('iteration')
plt.ylabel('normalized cost')
plt.legend()
plt.show()
print(f'min cost with BGD: {np.min(cost_batch)}')
print(f'min cost with SGD: {np.min(cost)}')
```

### Ridge Regression

\begin{equation}
\hat{\theta} = (X^TX + \lambda I)^{-1}X^TY
\end{equation}

where
\begin{equation}
X = [\bar{x}^T_1, \bar{x}^T_2, ... , \bar{x}^T_n]^T
\end{equation}

\begin{equation}
Y = [y_1, y_2, ... , y_n]^T
\end{equation}

This solution minimizes the following cost function

\begin{equation}
J(x, \theta, y) = \sum_{i=1}^{m}(\theta^T\bar{x}_i - y_i)^2 + \lambda ||\theta||^2
\end{equation}


```python
class Ridge:
    """
    Linear least squares with L2 regularization.
    """
    
    def __init__(self, lam):
        """
        Initialize a Ridge object.
        lam: the regularization factor 
        """
        self._lambda = lam
        
    @staticmethod
    def _x_bar(x):
        """
        Create the vector x_bar.
        x: input vector
        """
        # Start code here
        return None
        # End code here
    
    def fit(self, x_train, y_train):
        """
        Generate a fit for the data.
        x_train: the input values of the training data
        y_train: the output values of the training data
        """
        # Start code here
        # stack the data
        X = None
        Y = None
        
        # compute the model coeff
        XT = None
        XTX = None
        self._coeff_hat = None
        # End code here
```


```python
# Do not change the code in this cell
c2 = 0.03
c1 = 1.25
c0 = 3.23
x_in = np.linspace(-15.0, 19.4, 250)
y_out = c1 * x_in ** 2 + c1 * x_in + c0 + 400.0 * np.random.rand(len(x_in))

plt.figure()
plt.scatter(x_in, y_out)
plt.xlabel('x')
plt.ylabel('y')
plt.show()
```


```python
# Do not change the code in this cell
# Train using the custom Ridge class

x_train, x_test, y_train, y_test = train_test_split(
    x_in, y_out, test_size=0.20)

lam = 0.1
ridge = Ridge(lam)
ridge.fit(x_train, y_train)
```


```python
# Do not change the code in this cell
# Plot test data and model predictions
plt.figure()
plt.scatter(x_test, y_test)
x_test_sorted = np.sort(x_test)
plt.plot(x_test_sorted,
         ridge._coeff_hat[0] + ridge._coeff_hat[1]*x_test_sorted + ridge._coeff_hat[2]*x_test_sorted**2,
         '-r', label='custom')
plt.xlabel('x')
plt.ylabel('y')
plt.legend()
plt.show()

# print the coeff
print(f'custom: {ridge._coeff_hat[0]}, {ridge._coeff_hat[1]}, {ridge._coeff_hat[2]}')
```


```python
# Effect of regularization factor
coeff_store = []
norm_store = []
factors = np.linspace(0.0, 1.0, 10)
for l in factors:
    # Star code here
    # instantiate the Ridge class using l and store it in ridge
    ridge = None
    # fit the data to your model
    None
    # append co-effecients 
    None
    # append normalized co-effecients using np.linalg.norm
    None
```


```python
# Do not change the code in this cell
plt.figure()
plt.subplot(411)
coeff_0 = [c[0] for c in coeff_store]
plt.plot(factors, coeff_0, 'or')
plt.ylabel('c0')
plt.subplot(412)
coeff_1 = [c[1] for c in coeff_store]
plt.plot(factors, coeff_1, 'og')
plt.ylabel('c1')
plt.subplot(413)
coeff_2 = [c[2] for c in coeff_store]
plt.plot(factors, coeff_2, 'ob')
plt.ylabel('c2')
plt.subplot(414)
plt.plot(factors, norm_store, 'o')
plt.xlabel('lambda')
plt.ylabel('Norm')
plt.show()
```

### Q3. Theory (10 marks)

Consider training a binary decision tree using entropy splits.

(a) Prove that the decrease in entropy by a split on a binary yes/no feature can never be greater than 1 bit.

(b) Generalize this result to the case of arbitrary multiway branching.

### Q4. Gradient Descent Application (10 marks)

1. For the function \begin{equation} f(x, y) = ln(1 + xy), \end{equation}
find the unit vector that gives the direction of steepest descent at the point
P (2, 3). Also find the direction of no change at this point.


2. A businessperson can sell a product in France and Japan and charge different prices in each region. Let x represent the number of units sold in France and y represent the number of units sold in Japan. According to demand rules, the business owner must set the unit price at 97-(x/10) dollars in France and 83-(y/20) dollars in Japan in order to sell all of the units. The cost of production is ${\$ 3}$ per unit, in addition to a base capital of ${\$ 20,000}.$ If the industrialist intends to maximize profit, how many units should he aim to sell in each country?


```python

```

65d352750a637236a37a544afd0b89c3f8326efa
ipynb
Jupyter Notebook
assignment1/assignment_1_problem_statement.ipynb
LillithChute/CS6140ML
82edd545658bbd39541d45318ad123ec6cf42d98
MIT
assignment1/assignment_1_problem_statement.ipynb
LillithChute/CS6140ML
82edd545658bbd39541d45318ad123ec6cf42d98
MIT
assignment1/assignment_1_problem_statement.ipynb
LillithChute/CS6140ML
82edd545658bbd39541d45318ad123ec6cf42d98
MIT
Qwen/Qwen-72B
1. YES
2. YES