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

2 Answers 2

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$
1
  • $\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
    Commented Mar 18, 2016 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$
1
  • $\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
    Commented Mar 18, 2016 at 12:29

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .