What is a support vector?Christoph F. EickMonday, April 8, 2019 Review for COSC 4368 Midtem2 ExamSolution Sketches 1) Classification and Supervised Learning in General a) What is overfitting? What are the characteristics of overfitting? What can be done in the context of decision trees to battle overfitting?The model is too complex, the testing/generalization error is not optimal, although the training error is low. b) What is the key contribution of the backpropagation algorithm? What problems does itsolve? It measures and associates an error with the nodes of the intermediate layers that then canbe used to learn the weights of incoming connections of nodes of the intermediate layers. c) What is the purpose of training, test and validation sets in Supervised Learning? What else can be said about their relationship?Training set used for model learningValidation set is used to learn the best parameters for the method that generates the model(e,g, C and kernel function parameters in the case of the SVM)Test set is used to determine the accuracy of the learnt model; e.g. to determine accuracy, testing/generalization errorAll three sets should be disjointotherwise cheating2) Reinforcement Learning a) Assume you have a policy that always selects the action that leads to the state with the highest expected utility. Present arguments that this is usually not a good policy by describing scenarios in which this policy leads to suboptimal behavior of the agent!Not suitable for unknown worlds due its lack of exploration Not suitable for changing worlds due to its lack of exploration Other answers might deserve credit. 1b) Assume the following world is given:Moreover, the current Q-table contain the following entries:Assume the agent is currently in state 2 and her policy always applies action b in every state. How does the updated Q-Table look like after the agent has applied action b the fourth time assuming when Q-Learning is used? Assume that the learning rate  and the discount rate  are both 0.5. Do not only report the updated value, but also give the formulas for the four Q-table updates. Assume that the q-table entries are initially set to 0.Q(a,s)  Q(a,s) + α [ R(s) + γ*Q(a’,s’) - Q(a,s) ]Q(b,2)= 0 + 0.5*(2 + 0 – 0)=1Q(b,1)= 0+ 0.5*0=0Q(b,3)=0+ 0.5*(-1+0.5*1-0)= 0.25Q(b,2)=1+ 0.5*(2+1*0-1)=1.5c) How does SARSA differ from Q-learning?SARSA uses the chosen action in successor state in its q-table update when estimating the“utilities of the future”, whereas Q-learning uses the optimal action in the successor stateOff policy vs. On policy Learning (add some points from the RL1 slide that discusses the difference) 23) SVMs [9]a) What are the characteristics of hyperplanes that support vector machines learn from a training set? [3]a. The margin of the learnt hyperplane is maximalb. The hyperplane separates the examples of the two classes / minimizes the error in separating the examples of the two classes (in the case of the soft margin SVM). b) The soft margin support vector machine solves the following optimization problem:What does the first term minimize? Depict all non-zero i in the figure below! Depict all support vectors in the figure below---if example j is a support vector what is its value for j. What is the advantage of the soft margin approach over the linear SVM approach? Minimize inverse margin; support vectors are example that reside on in the green class’s and white class’s hyperplane and carry the label of that hyperplane. Advantage: Soft margin SVM: can deal with datasets that contain examples that are not linearly separable.What is a support vector?Image: nlp.stanford.eduAll other points have i values of 0!widthwidth3Support vectors are the data points nearest to the hyperplane, thepoints of a data set that, if removed, would alter the position of the dividing hyperplane. Because of this, they can be considered the critical elements of a data set.c) Explain how examples are classified by SVMs! By determining the sign of the hyperplane equation!4) Expressing Natural Language Statement as FOPL Formulas a) “No vegetarian eats fish” b) “There is a student enrolled in COSC 4368 who got a grade of A in all exams of the course” v (vegetarian(v)  ~not(eat(v,Fish))s student(s)  enrolled(s, 4368)  e (is-exam(e,4368)  taken(s,e))grade(s,e,A))If you remove taken(s,e) from the above formula, and I consider this formulapartially correct; however, it does not consider missed exams and exams in thefuture. 5) Neural Networksa) How are activation functions used in neural network computations? What is neuralnetwork learning all about? Activation functions are applied to the linearly weighted sum of the input activations todetermine the activation of a particular node.Given: NN Architecture, activation function NN-Learning: Find weights that minimize a given error function (for a given training set)b) What is the main purpose of the back propagation algorithm?Already answered in