ProjectProject ProposalProject Progress ReportProject Final ReportExponential Model and Maximum Entropy ModelRecap: Logistic Regression ModelHow to Extend Logistic Regression Model to Multiple Classes?Conditional Exponential ModelSlide 9Slide 10Modified Conditional Exponential ModelMaximum Entropy Model: MotivationSlide 13Slide 14Slide 15Slide 16Maximum Entropy Principle (MaxEnt)MaxEnt for Classification ProblemsSlide 19Slide 20MaxEnt ModelTranslation ProblemConstraintsSolution to MaxEntSlide 25Maximum Entropy Model versus Conditional Exponential ModelMaximum Entropy Model vs. Conditional Exponential ModelSolving Maximum Entropy ModelSlide 29Slide 30Slide 31Slide 32Improved Iterative ScalingChoice of FeaturesFeature Selection vs. RegularizersSlide 36Solving the L1 Regularized Conditional Exponential ModelSlide 38ProjectNow it is time to think about the projectIt is a team workEach team will consist of 2 peopleIt is better to consider a project of your ownOtherwise, I will assign you to some “difficult” project .Important date03/11: project proposal due04/01: project progress report due04/22 and 04/24: final presentation05/03: final report dueProject ProposalWhat do I expect?Introduction: describe the research problem that you try to solveRelated wok: describe the existing approaches and their deficiencyProposed approaches: describe your approaches and why it may have potential to alleviate the deficiency with existing approachesPlan: what you plan to do in this project?FormatIt should look like a research paperThe required format (both Microsoft Word and Latex) can be downloaded from www.cse.msu.edu/~cse847/assignments/format.zipProject Progress ReportIntroduction: overview the problem that you try to solve and the solutions that you present in the proposalProgressAlgorithm description in more detailsRelated data collection and cleanupPreliminary resultsFormat should be same as the project reportProject Final ReportIt should like a research paper that is ready for submission to research conferencesWhat do I expect?IntroductionAlgorithm description and discussionEmpirical studiesI am expecting careful analysis of results no matter if it is a successful approach or a complete failurePresentation25 minute presentation5 minute discussionExponential Model and Maximum Entropy ModelRong JinRecap: Logistic Regression ModelAssume the inputs and outputs are related in the log linear functionEstimate weights: MLE approach 1 21( | ; )1 exp ( ){ , ,..., , }mp y xy x w cw w w cqq=+ - � +� �� �=rrv*2121 1max ( ) max log ( | ; )1max log1 exp( )nreg train i iiw wn mji jww l D p y x s ws wy x w cq== == = -= -+ - � +� �� ��� �r rrr r rr r1 2{ , ,..., , }mw w w cHow to Extend Logistic Regression Model to Multiple Classes?y{+1, -1} {1,2,…,C}?1 21( | ; )1 exp ( ){ , ,..., , }mp y xy x w cw w w cqq=+ - � +� �� �=rrv( 1| )log( 1| )p y xx w cp y x== � +=-rrvrConditional Exponential ModelIntroduce a different set of parameters for each classEnsure the sum of probability to be 1( | ; ) exp( ) { , }y y y y yp y x c x w c wq q� + � =r r r r1( | ; ) exp( )( )( ) exp( )y yy yyp y x c x wZ xZ x c x wq = + �= + ��r r rrr r r( | ; )p y x qrConditional Exponential Model Predication probabilityModel parameters:For each class y, we have weights wy and threshold cyMaximum likelihood estimationexp( )( | ; ) , {1, 2,..., } exp( )y yy yyc x wp y x y Cc x wq+ �= �+ ��r rrr r1 1exp( )( ) log ( | ) logexp( )i iN Ny i ytrain i ii iy i yyc x wl D p y xc x w= =+ �= =+ �� ��r rrr rAny Problems?Conditional Exponential ModelAdd a constant vector to every weight vector, we have the same log-likelihood functionNot unique optimum solution!How to resolve this problem?0 00 010 01,exp( )( ) logexp( )exp( )logexp( )i ii iy y y yNy i ytrainiy i yyNy i yiy i yyw w w c c cc c x w wl Dc c x w wc x wc x w==� + � ++ + � +=+ + � ++ �=+ �����r r rr r rr r rr rr rSolution: Set w1 to be a zero vector and c1 to be zeroModified Conditional Exponential Model Prediction probabilityModel parameters:For each class y>1, we have weights wy and threshold cyMaximum likelihood estimation' '' 1' '' 1exp( ){2,..., }1 exp( )( | ; ) 111 exp( )y yy yyy yyc x wy Cc x wp y xyc x wq>>+ ����+ + ��=��=�+ + ����r rr rrr r1{ | 1} { | 1}1 1( ) log ( | )exp( )1log log1 exp( ) 1 exp( )i ii iNtrain i iiy i yi y i yy i y y i yy yl D p y xc x wc x w c x w== >> >=+ �= ++ + � + + ��� �� �rr rr r r rMaximum Entropy Model: MotivationConsider a translation exampleEnglish ‘in’  French {dans, en, à, au-cours-de, pendant}Goal: p(dans), p(en), p(à), p(au-cours-de), p(pendant)Case 1: no prior knowledge on tranlationWhat is your guess of the probabilities?Maximum Entropy Model: MotivationConsider a translation exampleEnglish ‘in’  French {dans, en, à, au cours de, pendant}Goal: p(dans), p(en), p(à), p(au-cours-de), p(pendant)Case 1: no prior knowledge on tranlationWhat is your guess of the probabilities?p(dans)=p(en)=p(à)=p(au-cours-de)=p(pendant)=1/5Case 2: 30% of times either dans or en is usedMaximum Entropy Model: MotivationConsider a translation exampleEnglish ‘in’  French {dans, en, à, au cours de, pendant}Goal: p(dans), p(en), p(à), p(au-cours-de), p(pendant)Case 1: no prior knowledge on tranlationWhat is your guess of the probabilities?p(dans)=p(en)=p(à)=p(au-cours-de)=p(pendant)=1/5Case 2: 30% of times either dans or en is usedWhat is your guess of the probabilities?p(dans)=p(en)=3/20 p(à)=p(au-cours-de)=p(pendant)=7/30Uniform distribution is favoredMaximum Entropy Model: MotivationCase 3: 30% of time dans or en is used, and 50% of times dans or à is usedWhat is your guess of the probabilities?Maximum Entropy Model: MotivationCase 3: 30% of time dans or en is used, and 50% of times dans or à is usedWhat is your guess of the probabilities?A good probability distribution shouldSatisfy the constraintsBe close to uniform distribution, but how?Measure Uniformality using Kullback-Leibler Distance !Maximum Entropy Principle (MaxEnt)A uniformity of distribution is measured by entropy of the distributionSolution: p(dans) = 0.2, p(a) = 0.3, p(en)=0.1, p(au-cours-de) =