Maximum entropy model

The principle of maximum entropy

principle ： Select the model with the maximum entropy from the model set that meets the constraint conditions .

Ideas ： From training data T Extract several features from , These characteristics are in T on Expectations of empirical distribution With them in the model p(x,y) The mathematical expectation of is equal , such , A feature corresponds to a constraint .

Suppose the classification model is a conditional probability distribution 𝑃(𝑌|𝑋), 𝑋 ∈ 𝒳 ⊆ 𝑅𝑛 Indicates input ,𝑌 ∈ 𝒴 Table condition overview
rate 𝑃(𝑌|𝑋) Output 𝑌. Given a training data set 𝑇 = {(𝑥1,𝑦1), (𝑥2,𝑦2), ⋯ , (𝑥𝑁,𝑦𝑁)}.

1. Consider the conditions that the model satisfies .

Joint distribution 𝑃(𝑋,𝑌) Empirical distribution and marginal distribution 𝑃(𝑋) The distribution of experience .

ν(𝑋 = 𝑥,𝑌 = 𝑦) Represents the sample in the training data (𝑥,𝑦) Frequency of occurrence ,

ν(𝑋 = 𝑥) Indicates that... Is entered in the training data 𝑥 Frequency of occurrence ,

𝑁 Represents the training sample size .

2. The characteristic function （feature function)𝑓(𝑥,𝑦) Description input 𝑥 And the output 𝑦 A fact between .

3. The characteristic function 𝑓(𝑥,𝑦) About the distribution of experience 𝑃̃(𝑋,𝑌) The expected value of is expressed as :

The characteristic function 𝑓(𝑥, 𝑦) About the model 𝑃(𝑌|𝑋) And experience distribution 𝑃̃(𝑋) The expected value of is expressed as ：

If the model can capture the information in the training data , Then we can assume that the two expectations are equal . namely

or

Definition ： Suppose that the set of models satisfying all the constraints is

Defined in conditional probability distribution 𝑃(𝑌|𝑋) The conditional entropy on is

Then the model set C Intermediate conditional entropy $H(P)$ The largest model is called the largest direct model . The logarithm in the formula is the natural logarithm .

For a given set of training data 𝑇 = {(𝑥1, 𝑦1), (𝑥2, 𝑦2), ⋯ , (𝑥𝑁, 𝑦𝑁)} And the characteristic function 𝑓𝑖(𝑥, 𝑦), 𝑖 = 1,2, ⋯ , 𝑛,

The maximum problem is rewritten as an equivalent minimum problem ：

Using Lagrange multiplier method, the maximum entropy model is transformed from a constrained optimization problem into an equivalent unconstrained optimization problem . Solve the original problem by solving the dual problem .

Derivation process ：