Reference no: EM133407099
In this programming assignment students are to apply Machine Learning using the features generated from the MNIST data set and build AI's (search algorithms) for the game of Tic-Tac-Toe using Game Theory search techniques. This assignment is to be implemented by the individual student while not collaborative you are allowed to discuss on the PA2 discussion area. Please follow the requirements provided in the Programming Assignment Guideline.
Problem 1 - Feature Ranking Methods (FLDR, Decision Tree Classification)
1. Using the MNIST dataset, rank the features using Fisher's Linear Discriminant Ratio as the criteria (you may utilize your implementation from the previous assignment).
2. you will create and fit a decision tree classifier (using the scikit learn built in function) offering a new avenue for feature ranking.
(a) Create an algorithm that will accept your dataset and fit a decision tree classifier to it.
(b) Using your algorithm in part 2.1, run a 5 fold cross validation and score the model based on its ability to classify accurately.
(c) From the model you fit, extract the feature importances.
(d) Add unit testing for the feature ranking in both methods.
(e) Plot your decision tree graph and examine the key parameters displayed. Offer an analysis for how the decision tree runs its predict method along with an analysis of the runtime complexity.
(f) Compare the features importances from the decision tree classifier with the feature ranking using FLDR. Consider what sets the two methods apart and offer a discussion on the benefits of each approach.
Problem 2 - Machine Learning
In this problem the features generated from HW2 for the numerical data set are to be used. This is the starting point for this problem. A minimum of 5,000 observations need to be used in the problem. A data set developed with the numericalFeatureGeneratorExample.m will also be provided if needed. The updated data is provide as an Excel file with 42,000 observations and 60 features, 20 from each direction. In this assignment data processing and machine learning techniques need to be combined, the "best" combination is determined by the best classification accuracy:
1. Use a minimum of one of following data preprocessing methods (If more than one method, the processing order is up to you. Built-ins are not allowed.):
(a) Data Normalization
(b) Outlier Removal
(c) Feature Ranking and Selection
(d) Dimensionality Reduction
2. Use the following Machine Learning (ML) techniques (built-ins are not allowed):
(a) Bayes Classifier (built-in not allowed)
(b) Parzen Window (Gaussian kernel)
(c) Support Vector Machine using your implementation of optimization to identify the support vectors (built-ins are not allowed)
3. Use 5-fold cross validation (from HW 3) on selected process from above.
4. Provide an analysis of your results:
(a) What combination from the above methods gave the best results? The "best results" is considered the highest classification accuracy for the 10 digits from the 5-fold cross validation results.
(b) Was there any part of the combination of the techniques used computationally expensive and why?
Figure 1: An algorithm for calculating the optimal move using MINIMAX - the move that leads to a terminal state with maximum utility, under the assumption that the opponent plays to minimize utility. The functions MAX-VALUE and MIN-VALUE go through the whole game tree, all the way to the leaves, to determine the backed-up value of a state and the move to get there.
Problem 3 - Game Theory (Search Algorithms)
In the tic-tac-toe code provided add the following method to allow an unbeatable AI in your game. Implement either MiniMax or Alpha Beta to play against and allow the play to choose the skill level.
1. Best Move (Provided) - Skill Level Easy
2. Utility Based Agent and Goal Based Agent (PA1) - Skill Level Medium
3. Skill Level Hard - Implemented the MiniMax and Alpha Beta algorithm from the Game Theory document for the tic-tac-toe game. You will need to alter the provided pseudo code to input the game board.