1
$\begingroup$

I am reading through the Computer Vision: Models, Learning, and Inference book to get an understanding of computer vision. The author describes the high-level steps taken to arrive at one of the derivations, but I'm stuck in working through the details.

An excerpt from the book (available at above link), describing the problem:

"Problem 4.3 Taking equation 4.29 as a starting point, show that the maximum likelihood parameters for the categorical distribution are given by $$ \hat{\lambda_k} = \frac{N_k}{\sum_{m=1}^{6}N_m} $$ where $N_k$ is the number of times that category $K$ was observed in the training data.

Equation 4.29 $$ L = \sum_{k=1}^{6} N_k \log[\lambda_k] + v\Bigg(\sum_{k=1}^{6}\lambda_k - 1 \Bigg) $$ where the second term uses the Lagrange multiplier $v$ to enforce the constraint on the parameters $\sum_{k=1}^{6}\lambda_k=1$".

The high-level description of how to solve this is given:

"We differentiate $L$ with respect to $\lambda_k$ and $v$, set the derivatives to zero, and solve for $\lambda_k$"

I think some of my confusion comes in how to take the partial derivative when it comes to within a summation. I have found some questions which seem similar, but I'm not sure how to apply them to this equation: 1, 2. I'll now list out the steps I took so far and hope to be pointed in the right direction.

Partial derivative of $L$ with respect to $\lambda_k$: $$ \frac{\partial L}{\partial \lambda_k} = \frac{\partial}{\partial \lambda_k} \Bigg[ \sum_{k=1}^{6} N_k \log[\lambda_k] + v\Bigg(\sum_{k=1}^{6}\lambda_k - 1 \Bigg) \Bigg] $$

$$ = \sum_{k=1}^{6} N_k \frac{1}{\lambda_k} + \frac{\partial}{\partial \lambda_k} \Bigg[ v\Bigg(\sum_{k=1}^{6}\lambda_k - 1 \Bigg) \Bigg] $$

$$ = \sum_{k=1}^{6} N_k \frac{1}{\lambda_k} + \frac{\partial}{\partial \lambda_k} \Bigg[ v \sum_{k=1}^{6}\lambda_k - v \Bigg] $$

$$ = \sum_{k=1}^{6} N_k \frac{1}{\lambda_k} + v \sum_{k=1}^{6}1 $$

$$ = \sum_{k=1}^{6} N_k \frac{1}{\lambda_k} + 6v $$

Partial derivative of $L$ with respect to $v$: $$ \frac{\partial L}{\partial v} = \frac{\partial}{\partial v} \Bigg[ \sum_{k=1}^{6} N_k \log[\lambda_k] + v\Bigg(\sum_{k=1}^{6}\lambda_k - 1 \Bigg) \Bigg] $$ $$ = \frac{\partial}{\partial v} \Bigg[ v\Bigg(\sum_{k=1}^{6}\lambda_k - 1 \Bigg) \Bigg] $$ $$ = \frac{\partial}{\partial v} v\sum_{k=1}^{6}\lambda_k - v $$ $$ = \sum_{k=1}^{6}\lambda_k - 1 $$

At this point, I imagine I would set both equations equal to zero and solve for $\lambda_k$. However, I don't know that I did the differentiation correctly and if so, I'm not sure how to proceed with solving for $\lambda_k$ (removing it from the summation?).

$\endgroup$
0
$\begingroup$

The problem stems from you writing

$$\frac{\partial}{\partial \lambda_k} \sum^6_{k=1} N_k \log{[\lambda_k]} = \sum^k_{k=1}N_k \frac{1}{\lambda_k} \quad \quad \text{(wrong!)}$$

You are probably getting confused since you have used the same variable $k$ to denote both the $\lambda$ you are differentiating with and the summation variable.

Avoid doing this, and it will be clearer to you that $$\frac{\partial}{\partial \lambda_k} \sum^6_{i=1} N_i \log{[\lambda_i]} = \frac{N_k}{\lambda_k}$$

Similarly,

$$\frac{\partial}{\partial \lambda_k}\left[v \sum^6_{i=1} \lambda_i - v \right] = v$$

Then

$$\frac{\partial L}{\partial \lambda_k} = \frac{N_k}{\lambda_k} + v$$

Set that to $0$ to get $\lambda_k = -N_k/v$.

Substitute that into the constraint

$$1 = \sum^6_{i=1} \lambda_i = - \frac{\sum^6_{i=1} N_i}{v} \Longrightarrow v = -\sum^6_{i=1} N_i$$

Then substitute this $v$ to get the result:

$$\lambda_k = \frac{N_k}{\sum^6_{i=1} N_i}$$

$\endgroup$
  • $\begingroup$ You're right, I needed to understand that I should use a different variable for the summation index. Thank you for the clear explanation. $\endgroup$ – Peter Mar 18 '16 at 12:27
0
$\begingroup$

The calculation of $\partial L\over\partial v$ is correct, but in your calculation of $\partial L\over\partial\lambda_k$ you need to distinguish the $k$ you are interested in from the $k$ used as the summation index. Better to use a different index for the summation, as in: $$ L = \sum_{i=1}^{6} N_i \log[\lambda_i] + v\Bigg(\sum_{i=1}^{6}\lambda_i - 1 \Bigg)\tag1 $$ When you differentiate $L$ wrt $\lambda_k$ you are interested in a specific $k$ among the set $\{1,\ldots,6\}$. In both of the summations in (1) this $\lambda_k$ appears in only one of the six terms; the other $\lambda_i$ are treated as constant, so the partial derivative of $L$ wrt $\lambda_k$ is: $$ {\partial L\over\lambda_k}={N_k\over\lambda_k}+v.$$ The above calculation is valid for each $k$; you've now got $6$ equations along with the one for $\partial L\over\partial v$. Solve these simultaneously and you'll get the advertised values for $\hat\lambda_1,\ldots,\hat\lambda_6$.

$\endgroup$
  • $\begingroup$ Thank you for pointing out I needed to use a different variable for the summation. I was stuck on this for some time and I appreciate the explanation. $\endgroup$ – Peter Mar 18 '16 at 12:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.