Principle of Maximum Entropy ? Maximum Entropy Models?
https://bactra.org/notebooks/max-ent.html
$$p(X) = \frac{\exp (X)}{\sum \exp (X)}$$
위와 같은 꼴을 가진 모델을 maximum entropy 모델이라 부른다. 위의 식은 아래와 같이 다시 쓸 수 있다.
$$p(X) = \frac{1}{Z} \exp (f(X))$$
이를 한 번 더 변환하면 아래와 같이 쓸 수도 있다.
$$p(X) = \frac{1}{Z} \exp (\frac{- E(X)}{T})$$
이를 볼츠만Boltzmann distribution이라 한다. 여기에서 $E(X)$는 보통 에너지라 불리고 $T$는 온도라 부른다.
특정 제약을 만족하는 모델 중 가장 정보이론적으로 "합당한" 모델을 찾아보자.
$$\log P(x|\theta) = \sum_{c \in \mathscr{C}} \phi_{c}(x_{c})^T \theta_{c} - \log Z(\theta)$$
where there are $\mathscr{C}$ features derived from $x$'s.
The Principle of Maximum Entropy
Subject to precisely stated prior data (such as a proposition that expresses testable information), the probability distribution which best represents the current state of knowledge is the one with largest entropy.
Wallis derivation
Suppose an individual wishes to make a probability assignment among $m$ mutually exclusive propositions. She has some testable information, but is not sure how to go about including this information in her probability assessment. She therefore conceives of the following random experiment. She will distribute $N$ quanta of probability (each worth 1/N) at random among the $m$ possibilities. (One might imagine that she will throw $N$ balls into $m$ buckets while blindfolded. In order to be as fair as possible, each throw is to be independent of any other, and every bucket is to be the same size.) Once the experiment is done, she will check if the probaiblity assignment thus obtained is consistent with her information. (For this step to be successful, the information must be a constraint given by an open set in the space of probability measures). If it is inconsistent, she will reject it and try again. If it is consistent, her assessment will be
$p_i = \frac{n_i}{N}$
where $p_i$ is the probability of the $i$-th proposition, while $n_i$ is the number of qunata that were assigned to the $i$-th proposition (i.e., the number of balls that ended up in bucket $i$).
Now, in order to reduce the graininess of the probability assignment, it will be necessary to use quite a large number of quanta or probability. Rather than actually carry out, and possibly have to repeat, the rather long random experiment, the protagonist decides to simply calculate and use the most probable result. The probability of any particular result is the multinomial distribution
$$Pr(p) = W \cdot m^{-N}$$
where
$$W = \frac{N!}{n_1! n_2 ! \cdots n_m!}$$
is sometimes known as the multiplicity of the outcome.
The most probable result is the one which maximizes the multiplicity $W$. Rather than maximizing $W$ directly, the protagonist could equivalently maximize any monotonic increasing function of $W$. She decides to maximize
\begin{align} \frac{1}{N} \log W &= \frac{1}{N} \log \frac{N!}{n_1! n_2! \cdots n_m!} \\ &= \frac{1}{N} \log \frac{N!}{(Np_1)!(Np_2)! \cdots (Np_m)!} \\ &= \frac{1}{N} (\log N! - \sum_{i = 1}^m \log((Np_i)!)) \end{align}
At this point, in order to simplify the expression, the protagonist takes the limit as $N \to \infty$, i.e., as the probability levels go from grainy discrete values to smooth continuous values. Using Stirling's approximation, she finds
\begin{align} \lim_{N \to \infty} (\frac{1}{N} \log W) &= \frac{1}{N} (N \log N - \sum_{i = 1}^m Np_i \log (N p_i)) \\ &= \log N - \sum_{i = 1}^m p_i \log (Np_i) \\ &= \log N - \log N \sum_{i = 1}^m p_i - \sum_{i = 1}^m p_i \log p_i\\ &= (1 - \sum_{i = 1}^m p_i) \log N - \sum_{i = 1}^m p_i \log p_i \\ &= - \sum_{i = 1}^m p_i \log p_i\\ &= H(p) \end{align}
All that remains for the protagonist to do is to maximize entropy under the constraints of her testable information. She has found that the maximum entropy distribution is the most probable of all "fair" random distributions, in the limit as the probability levels go from discrete to continuous.
Understanding MaxEnt
Suppose we want to assign a tag to the word zzfish. What is the probabilistic tagging model that makes the fewest assumptions, imposing no constraint at all? Intuitively it would be the equiprobable distribution.
NN = 1/45 JJ = 1/45 NNS = 1/45 VB = 1/45 ...
Now suppose we had some training data labeled with part-of-speech tags, and from this data we learned only one fact: the set of possible tags for zzfish are NN, JJ, NNS, and VB. What is the tagging model which relies on this constraints, but makes no further assumption at all? Since one of these must be the correct tag, we know that
$$P(NN) + P(JJ) + P(NNS) + P(VB) = 1$$
Since we have no further information, a model which makes no further assumptions beyond what we know would simply assign equal probability to each of these words.
NN 1/4 JJ 1/4 NNS 1/4 VB 1/4 ... 0
In the first example, where we wanted an uninformed distribution over 45 part-of-speech, and in this case, where we wanted an uninformed distribution over 4 parts-of-speech, it turns out that of all possible distributions, the equipron distribution has the maximum entropy.
The intuition of MaxEnt modeling is that the probabilistic model we are building should follow whatever constraints we impose on it, but beyond these constraints it should follow Occam's Razor, i.e., make the fewest possible assumptions.
Suppose we looked at our tagged training data and noticed that 8 times out of 10, zzfish was tagged as some sort of common nou, either NN or NNS. We can think of this as specifying the feature 'word is zzfish and $t_i$ = NN or $t_i$ = NNS'. We might now want to modify our distribution so that we give 8/10 of our probability mass to nouns, i.e. now we have 2 constraints.
$$P(NN) + P(JJ) + P(NNS) + P(VB) = 1$$ $$P(\text{word is zzfish and } t_i = \text{ NN or } t_i = \text{ NNS}) = 8/10$$
but make no further assumptions (keep JJ and VB equiprobable, and NN and NNS equiprobable).
NN 4/10 JJ 1/10 NNS 4/10 VB 1/10 ... 0
Now suppose we don't have any more information about zzfish. But we notice in the training data that for all English words (not just zzfish) verbs (VB) occur as 1 word in 20. We can now add this constraint (corresponding to the feature $t_i$ = VB)
$$P(NN) + P(JJ) + P(NNS) + P(VB) = 1$$ $$P(\text{word is zzfish and } t_i = \text{ NN or } t_i = \text{ NNS}) = 8/10$$ $$P(VB) = 1/20$$
The resulting maximum entropy distribution is now as follows:
NN 4/10 JJ 3/20 NNS 4/10 VB 1/20
In summary, the intuition of maximum entropy is to build a distribution by continuously adding feature. Each feature is an indicator function, which picks out a subset of the training observations. For each feature we add a constraint on our total distribution, specifying that our distribution for this subset should match the empirical disribution we saw in our training data. We then choose the maximum entropy distribution which otherwise accords with these constrains. Berger et al. (1996) pose the optimization problem of finding this distribution as follows
"To select a model from a set C of allowed probability distributions, choose the model $p^{*} \in C$ with maximum entropy H(p)"
$$p^{*} = \mathrm{argmax}_{p \in C} H(p)$$
Now we come to the important conclusion. Berger et al. (1996) show that the solution to this optimization problem turns out to be exactly the probability distribution of a multinomial logistic regression model whose weights $W$ maximize the likelihood of the training data! Thus the exponential model for multinomial logistic regression, when trained according to the maximum likelihood criterion, also finds the maximum entropy distribution subject to the constraints from the feature functions.
The Equivalence of Logistic Regression and Maximum Entropy Models
Given data $x^{(1)}, \ldots, x^{(m)} \in \mathbb{R}^n$ and corresponding label $y^{(1)}, \ldots, y^{(m)} \in \mathbb{R}^k$, find the model $\pi(\cdot): \mathbb{R}^n \to \mathbb{R}^k$.
$x_{j}^{(i)}$ denotes $i$-th example's $j$-th coordinate.
Let $\pi(\cdot)$ be a function mapping from the space the $x^{(i)}$ are in into vectors indexed by the categories. $\pi(x)_{u}$ denotes the probability $\pi(\cdot)$ assigns in input situation $x$ to category $u$.
Let's try to find a model $\pi(\cdot)$ that satisfies the following.
$$ \forall u, j \sum_{i = 1}^m \pi(x^{(i)})_u x_j^{(i)} = \sum_{i = 1}^m \mathbb{I}(u = y^{(i)})x_j^{(i)}$$
Explained in words, the sum of any coordinate $j$ of the $x^{(i)}$'s from all the training data in a particular category $u$ is equal to the sum of probability mass the model places in that coordinate summed across all data $(\forall u, j)$.
This condition implies that $\pi(x^{(i)})_u$ behaves very much like the indicator function $\mathbb{I}(u = y^{(i)})$.
We wish to find a model $\pi(\cdot)$ that satisfies the above equation. Also, let's assume that $\pi(x)_v \ge 0$ and $\sum_{v=1}^k \pi(x)_v = 1$, for $\pi(\cdot)$ to behave like a probability distribution.
Now we turn to the principle of maximum entropy. The entropy of $\pi(\cdot)$ is defined as follows.
$$- \sum_{v = 1}^k \sum_{i = 1}^m \pi(x^{(i)})_v \log (\pi(x^{(i)}))_v)$$
We find $\pi(\cdot)$ that maximizes the entropy while obeying the previous constraints.
Set up a Lagrangian for sum to one constraint and the indicator function approximation assumption. We exclude the grater than or equal to zero constraint here because working with inequalities is cumbersome. We can introduce the inequality constraints in the Lagrangian but this requires introducing more variables.
$$L = \sum_{j=1}^n \sum_{v=1}^k \lambda_{v, j} (\sum_{i=1}^m \pi(x^{(i)})_v x_j^{(i)} - \mathbb{I}(v = y^{(i)})x_k^{(i)}) + \sum_{v = 1}^k \sum_{i = 1}^m \beta_i (\pi (x^{(i)})_v - 1) - \sum_{v = 1}^k \sum_{i = 1}^m \pi(x^{(i)})_v \log (\pi(x^{(i)})_v)$$
Optimal $\pi^{*}(\cdot)$ will satisfy $\frac{\partial}{\partial \pi(x^{(i)})_u} L = 0 \forall i, u$.
$$\frac{\partial}{\partial \pi(x^{(i)})_u} L = \lambda_u x^{(i)} + \beta_i - \log(\pi(x^{(i)})_u) - 1$$
Solving for this we get the following.
\begin{align} 0 &= \lambda_u x^{(i)} + \beta_i - \log(\pi(x^{(i)}_u) - 1 \\ \pi(x^{(i)})_u= e^{\lambda_u x^{(i)} + \beta_i - 1} \end{align}
Note that we have never assumed any parametric form of $\pi(\cdot)$. It just flows out from the assumptions and the maximum entropy principle.
Since we want sum to one constraint to hold.
$$\sum_{v = 1}^k e^{\lambda_v x^{(i)} + \beta_i - 1} = 1$$
Therefore,
$$e^{\beta_i} = \frac{1}{\sum_{v = 1}^k e^{\lambda_v x^{(i)} - 1}}$$
Plugging this back into the original equation, we get
$$\pi(x)_u = \frac{e^{\lambda_u x}}{\sum_{v = 1}^k e^{\lambda_v x}}$$
This is the exact multi-category version of the sigmoid. This derivation gives some indication that the sigmoid function is in some sense special among the different GLM models.
We have derived this from general principle of maximum entropy and the calculus of variations.
References
위의 유도는 John Mount의 The equivalence of logistic regression and maximum entropy models에 기반하였다.
Maximum entropy에 기반한 아이디어와 베이지안 접근에 대한 많은 토론이 있었다. 엄밀한 의미에서 maximum entropy 모델은 베이지안 관점과 다른 접근 방법이며 그런 이유로 Radford Neal과 같은 사람들은 MaxEnt 모델의 사용이 틀렸다고 주장하였다.
실용적인 관점에서 봤을 때, 모델의 prior 분포를 쉽게 표현할 수 있다면 베이지안 접근을 활용하고 모델이 지켜야 하는 제약 조건을 서술하는 것이 쉽다면 MaxEnt 모델을 활용하는 것이 좋다는 의견도 있다.