1CS 6375 Machine Learning2015 SpringFinal ReviewYang LiuFinal Exam• May 11th, 2-4pm• Closed book/note• Cheat sheet allowed, one page (double side is okay)• Format is similar to midterm• Office hours – I will be in school May 4-8th– Stop by or email to schedule an appt2Extra Project/Report• Due May 5 (submit on eLearning)• What to turn in: – Your report• Format of the report: can be similar to a research paper (e.g., introduction, related work, experimental setup, results, findings and discussions, conclusion and future work)• Length: flexible (a few pages, probably not more than 10 pages)– Your executables for the test files (so that we can run it on a different test set)Topics Covered in Final• Not comprehensive – Ensemble (bagging, boosting)– Learning theory– Regression– Clustering– Support vector machines– Reinforcement learning, MDP– HMM3Ensemble• Bias/variance decomposition, tradeoff• Connection to overfitting problem• Bagging• Boosting• System combination in general()[]VarianceBiasNoisexTDxLED++=−222)(),(4Learning Theory• VC dimension & shattering– Given r data points, consider 2rtraining sets– VC: can shatter r data points (one set is enough), not r+1 data points (any)• PAC learning, sample complexity)1ln||(ln1δε+≥ HR))13(log)(8)2(log4(122εδεHVCR +≥Linear Regression• Concepts• Minimize squared error• Find solutionsε2YXε1ε3ε4^^^^ε2YXε1ε3ε4^^^^β+++=−∑iddiiiiiixwxwxwYYYL22112ˆ)ˆ(5Logistic Regression• Concepts• Posterior probability • Maximize conditional likelihood• Gradient descent)),|1(( wxypyxwwllliii=−+=∑ηK-means (special EM/GMM)• Unsupervised learning• Learn the centers µk(prototypes)• E-step: assign each point to closest prototype • M-step: use all the points assigned to the cluster∑∈=cxxcrrr||1(c)µ6Agglomerative Clustering• GMM/K-means is flat clustering• Hierarchical clustering by greedily merging clusters that are most similar• Single link: cluster distance is based on the two closest data points • Complete link: cluster distance is based on two least similar data points SVM• Training, using the dual problem:Support vectors10±=+•=≠∑bxwxywiiiiiααjijiijxxyyG '=Matrix representation, G7SVM• Testing• Soft margin – Same objective, adding constraint 0 < αi< C SV with ξi= 0αi= C SV with ξi> 0αi= 0 otherwise• Kernelsbxxybxwiiii+•=+•∑**αCi≤≤α0)()()'(jijijijiijxxyyxxKyyGΦΦ==Reinforcement Learning• Reward discount• Markov system– J*(Si) = ri+ γ * (Expected future rewards starting from your next state)= ri+ γ ΣjPij J*(Sj)– Value iteration• Jk+1(Si)=ri+ γ ΣjPij Jk(Sj)8MDP• Policy• With different actions in states• Value iteration (iterate J, after converge, get π)• Policy iteration (iterate π and J, alternate) – Omit formula here( ) ( ) ( )+=++∑+1*1*1,|maxtsttttatsJassPrsJttγ( ) ( ) ( )+=++∑+1*11,|max arg*tsttttatsJassPrsttγπ()ttsa: π=→π ASLearning• Model-based learning• Temporal difference learning (Markov system)• Q learning (MDP)()()()()()( ) ( )( )11)1()(++++−←−++←tttttttttsJrsJsJsJsJrsJsJγααγα( ) ( ) ( ) ( )( ) ( ) ( )++−←−++←++++++1111,ˆmax,ˆ)1(,ˆ,ˆ,ˆmax,ˆ,ˆ11ttatttttttttatttttasQrasQasQasQasQrasQasQttγααγα9HMM• What are they? • Markov property{S, O, Π, Π, Π, Π, Α, ΒΑ, ΒΑ, ΒΑ, Β} ABAAABBSSSOOOSOSOHMM• Three problems– P(O|λ): Forward probability – argmaxP(Q|O1..OT): Viterbi decoding– Training10Exams• Don’t panic• Read questions carefully• Ask for clarification if needed, or state what your assumption is if there’s ambiguity• Pace yourself, answer easiest questions first• Reread the question after you are done, make sure you have understood the question and answered it correctly (no obvious errors)Topicstentative1. Short questions 202. Learning theory 153. Boosting 155. Reinforcement Learning 206. Clustering 107. SVM 108. HMM
View Full Document
Unlocking...