Project Now it is time to think about the project It is a team work It is better to consider a project of your own Each team will consist of 2 people 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 due Project 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 zip Project 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 report Project 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 discussion Exponential Model and Maximum Entropy Model Rong Jin Recap Logistic Regression Model Assume the inputs and outputs are related in the log linear function r 1 p y x q v r 1 exp y x w c q w1 w2 wm c Estimate weights MLE approach w1 w2 wm c r r r n w max l D max log p y x q s w reg train i i r r i 1 w w n max log r i 1 w 1 m 2 s w r r j 1 j 1 exp y x w c 2 How to Extend Logistic Regression Model to Multiple Classes y 1 1 1 2 C r 1 p y x q v r 1 exp y x w c q w1 w2 wm c r p y 1 x v r log w c r x p y 1 x Conditional Exponential Model Introduce a different set of parameters for each class r r r r p y x q exp c y x wy qy c y wy Ensure the sum of probability r p y x q r r r 1 p y x q r exp c y x wy Z x r r r Z x y exp c y x wy to be 1 Conditional Exponential Model Predication probability r r exp c y x wy r p y x q r r y 1 2 C y exp c y x wy Model parameters For each class y we have weights wy and threshold cy Maximum likelihood estimation r r exp c yi xi wyi r N N l Dtrain i 1 log p yi xi i 1 log r r exp c x wy y y i Any Problems Conditional Exponential Model Add a constant vector to every weight vector we have the same log likelihood r r r function wy wy w0 c y c y c0 r r r exp c c x w w N yi 0 i yi 0 l Dtrain i 1 log r r r y exp c y c0 xi wy w0 r r exp c x wyi N yi i i 1 log r r exp c x wy y y i Not unique optimum solution How to resolve this problem Solution Set w1 to be a zero vector and c1 to be zero Modified Conditional Exponential Model Prediction probability r r exp c y x wy r r 1 exp c x wy y r y 1 p y x q 1 r r 1 y 1 exp c y x wy y 2 C y 1 Model parameters For each class y 1 we have weights wy and threshold cy Maximum likelihood estimation r N l Dtrain i 1 log p yi xi r r exp c x wyi 1 yi i i y 1 log r r i yi 1 log r r i 1 y 1 exp c y xi wy 1 y 1 exp c y xi wy 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 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 used 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 Case 2 30 of times either dans or en is used What is your guess of the probabilities p dans p en p p au cours de p pendant 1 5 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 favored 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 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 Measure Uniformality using Kullback Leibler Distance A good probability distribution should Satisfy the constraints Be close to uniform distribution but how Maximum Entropy Principle MaxEnt A uniformity of distribution is measured by entropy of the distribution P max H P P where H P p dans log p dans p en log p en p a log p a p au course de log p au course de p pendant log p pendant subject to p dans p en 3 10 p dans p a 1 2 p dans p en p a p au cours de p pendant 1 Solution p dans 0 2 p a 0 3 p en 0 1 p au cours de 0 2 p pendant 0 2 MaxEnt for Classification Problems Want a p y x to be close to a uniform distribution Maximize the conditional entropy of training data r r r r N N H y x i 1 H y xi i 1 y p y xi log p y xi Constraints Valid probability distribution r i y p y xi 1 From training data the model should be …