Skip to main content
MathOverflow

Return to Question

added 282 characters in body
Source Link
skypemesm
skypemesm
  • 141
  • 4

Wondering if my following question is an application of information theory:

Lets say we have a factory and ship boxes of stuff outside. If a competitor stands outside my factory, observes the stream of boxes coming out of a factory and note their sizes, he can get valuable information about my manufacturing process. So in order to hoodwink him, I manually expand the boxes to sizes different than the original ones. In order to make sure that I am doing a good job at masking the original size distribution from the resultant distribution, I must make sure that I maximize relative entropy between output distribution q and input distribution p, given that I cannot just create a uniform output distribution. Is this premise correct? Do you find any flaw in the question?

The constraint, of course, is that we must use minimum amount of box material. In other words, sum of box sizes for a unit period of time must not exceed a threshold B.
i.e. $\frac{\sum_{j=1}^{i}{BS_i}}{T} \le B$

Other constraints are:

1] Both p and q must be probability distributions i.e. sum up to 1
2] $BS_i \le MS$, where MS is the maximum size of a box.

--

If we take $BS_i$ as the size of the $i^{th}$ box, then we have an optimization function applying Lagrange multiplier $\lambda$:

$ \Lambda(BS_i,\lambda,p,q) = D(q||p) + \lambda (\frac{\sum_{j=1}^{i}{BS_i}}{T} - B) $ $ = \sum_{S=1}^{n}{q(S) \log \frac{q(S)}{p(S)}} + \lambda (\frac{\sum_{j=1}^{i}{BS_i}}{T} - B)$

$ = \sum_{S=1}^{n}{q(S) \log q(S)} -\sum_{S=1}^{n}{q(S) \log p(S)} + \lambda (\frac{\sum_{j=1}^{i}{BS_i}}{T} - B)$

To proceed: Lets say we at the $i^{th}$ iteration. We know the actual box sizes that we already sent out for 1...i-1 iterations, and the actual size of the present box. i.e. $BS_0..BS_i$ are known, and hence p(BS) can be calculated and hence is a known value. We know the output box sizes till the $i-1^{th}$ iteration.

So, we have,

$ \Lambda(BS_i,\lambda,q) = \sum_{S=1}^{n}{q(S) \log q(S)} -\sum_{S=1}^{n}{k*q(S) } + \lambda (\frac{\sum_{j=1}^{i}{BS_i}}{T} - B) $

How do we now solve the optimization function, in order to get the output box size for this $i^{th} iteration?

We have, $\frac{\partial\Lambda}{\partial BS_i} = 0$, $\frac{\partial\Lambda}{\partial q(S)} = 0$, and $\frac{\partial\Lambda}{\partial \lambda} = 0$

The pertial differentiation wrt $\lambda$ results in a trivial solution. Since q(S) is dependent on $BS_i$, we will get a factor of $\frac{\partial q(S)}{\partial BS_i}$ in the other two equations.

How do I proceed from here? What I am thinking wrong?

Wondering if my following question is an application of information theory:

Lets say we have a factory and ship boxes of stuff outside. If a competitor stands outside my factory, observes the stream of boxes coming out of a factory and note their sizes, he can get valuable information about my manufacturing process. So in order to hoodwink him, I manually expand the boxes to sizes different than the original ones. In order to make sure that I am doing a good job at masking the original size distribution from the resultant distribution, I must make sure that I maximize relative entropy between output distribution q and input distribution p, given that I cannot just create a uniform output distribution. Is this premise correct? Do you find any flaw in the question?

The constraint, of course, is that we must use minimum amount of box material. In other words, sum of box sizes for a unit period of time must not exceed a threshold B.

If we take $BS_i$ as the size of the $i^{th}$ box, then we have an optimization function:

$ \Lambda(BS_i,\lambda,p,q) = D(q||p) + \lambda (\frac{\sum_{j=1}^{i}{BS_i}}{T} - B) $ $ = \sum_{S=1}^{n}{q(S) \log \frac{q(S)}{p(S)}} + \lambda (\frac{\sum_{j=1}^{i}{BS_i}}{T} - B)$

$ = \sum_{S=1}^{n}{q(S) \log q(S)} -\sum_{S=1}^{n}{q(S) \log p(S)} + \lambda (\frac{\sum_{j=1}^{i}{BS_i}}{T} - B)$

To proceed: Lets say we at the $i^{th}$ iteration. We know the actual box sizes that we already sent out for 1...i-1 iterations, and the actual size of the present box. i.e. $BS_0..BS_i$ are known, and hence p(BS) can be calculated and hence is a known value. We know the output box sizes till the $i-1^{th}$ iteration.

So, we have,

$ \Lambda(BS_i,\lambda,q) = \sum_{S=1}^{n}{q(S) \log q(S)} -\sum_{S=1}^{n}{k*q(S) } + \lambda (\frac{\sum_{j=1}^{i}{BS_i}}{T} - B) $

How do we now solve the optimization function, in order to get the output box size for this $i^{th} iteration?

We have, $\frac{\partial\Lambda}{\partial BS_i} = 0$, $\frac{\partial\Lambda}{\partial q(S)} = 0$, and $\frac{\partial\Lambda}{\partial \lambda} = 0$

The pertial differentiation wrt $\lambda$ results in a trivial solution. Since q(S) is dependent on $BS_i$, we will get a factor of $\frac{\partial q(S)}{\partial BS_i}$ in the other two equations.

How do I proceed from here? What I am thinking wrong?

Wondering if my following question is an application of information theory:

Lets say we have a factory and ship boxes of stuff outside. If a competitor stands outside my factory, observes the stream of boxes coming out of a factory and note their sizes, he can get valuable information about my manufacturing process. So in order to hoodwink him, I manually expand the boxes to sizes different than the original ones. In order to make sure that I am doing a good job at masking the original size distribution from the resultant distribution, I must make sure that I maximize relative entropy between output distribution q and input distribution p, given that I cannot just create a uniform output distribution. Is this premise correct? Do you find any flaw in the question?

The constraint, of course, is that we must use minimum amount of box material. In other words, sum of box sizes for a unit period of time must not exceed a threshold B.
i.e. $\frac{\sum_{j=1}^{i}{BS_i}}{T} \le B$

Other constraints are:

1] Both p and q must be probability distributions i.e. sum up to 1
2] $BS_i \le MS$, where MS is the maximum size of a box.

--

If we take $BS_i$ as the size of the $i^{th}$ box, then we have an optimization function applying Lagrange multiplier $\lambda$:

$ \Lambda(BS_i,\lambda,p,q) = D(q||p) + \lambda (\frac{\sum_{j=1}^{i}{BS_i}}{T} - B) $ $ = \sum_{S=1}^{n}{q(S) \log \frac{q(S)}{p(S)}} + \lambda (\frac{\sum_{j=1}^{i}{BS_i}}{T} - B)$

$ = \sum_{S=1}^{n}{q(S) \log q(S)} -\sum_{S=1}^{n}{q(S) \log p(S)} + \lambda (\frac{\sum_{j=1}^{i}{BS_i}}{T} - B)$

To proceed: Lets say we at the $i^{th}$ iteration. We know the actual box sizes that we already sent out for 1...i-1 iterations, and the actual size of the present box. i.e. $BS_0..BS_i$ are known, and hence p(BS) can be calculated and hence is a known value. We know the output box sizes till the $i-1^{th}$ iteration.

So, we have,

$ \Lambda(BS_i,\lambda,q) = \sum_{S=1}^{n}{q(S) \log q(S)} -\sum_{S=1}^{n}{k*q(S) } + \lambda (\frac{\sum_{j=1}^{i}{BS_i}}{T} - B) $

How do we now solve the optimization function, in order to get the output box size for this $i^{th} iteration?

We have, $\frac{\partial\Lambda}{\partial BS_i} = 0$, $\frac{\partial\Lambda}{\partial q(S)} = 0$, and $\frac{\partial\Lambda}{\partial \lambda} = 0$

The pertial differentiation wrt $\lambda$ results in a trivial solution. Since q(S) is dependent on $BS_i$, we will get a factor of $\frac{\partial q(S)}{\partial BS_i}$ in the other two equations.

How do I proceed from here? What I am thinking wrong?

Source Link
skypemesm
skypemesm
  • 141
  • 4

Optimization of relative entropy

Wondering if my following question is an application of information theory:

Lets say we have a factory and ship boxes of stuff outside. If a competitor stands outside my factory, observes the stream of boxes coming out of a factory and note their sizes, he can get valuable information about my manufacturing process. So in order to hoodwink him, I manually expand the boxes to sizes different than the original ones. In order to make sure that I am doing a good job at masking the original size distribution from the resultant distribution, I must make sure that I maximize relative entropy between output distribution q and input distribution p, given that I cannot just create a uniform output distribution. Is this premise correct? Do you find any flaw in the question?

The constraint, of course, is that we must use minimum amount of box material. In other words, sum of box sizes for a unit period of time must not exceed a threshold B.

If we take $BS_i$ as the size of the $i^{th}$ box, then we have an optimization function:

$ \Lambda(BS_i,\lambda,p,q) = D(q||p) + \lambda (\frac{\sum_{j=1}^{i}{BS_i}}{T} - B) $ $ = \sum_{S=1}^{n}{q(S) \log \frac{q(S)}{p(S)}} + \lambda (\frac{\sum_{j=1}^{i}{BS_i}}{T} - B)$

$ = \sum_{S=1}^{n}{q(S) \log q(S)} -\sum_{S=1}^{n}{q(S) \log p(S)} + \lambda (\frac{\sum_{j=1}^{i}{BS_i}}{T} - B)$

To proceed: Lets say we at the $i^{th}$ iteration. We know the actual box sizes that we already sent out for 1...i-1 iterations, and the actual size of the present box. i.e. $BS_0..BS_i$ are known, and hence p(BS) can be calculated and hence is a known value. We know the output box sizes till the $i-1^{th}$ iteration.

So, we have,

$ \Lambda(BS_i,\lambda,q) = \sum_{S=1}^{n}{q(S) \log q(S)} -\sum_{S=1}^{n}{k*q(S) } + \lambda (\frac{\sum_{j=1}^{i}{BS_i}}{T} - B) $

How do we now solve the optimization function, in order to get the output box size for this $i^{th} iteration?

We have, $\frac{\partial\Lambda}{\partial BS_i} = 0$, $\frac{\partial\Lambda}{\partial q(S)} = 0$, and $\frac{\partial\Lambda}{\partial \lambda} = 0$

The pertial differentiation wrt $\lambda$ results in a trivial solution. Since q(S) is dependent on $BS_i$, we will get a factor of $\frac{\partial q(S)}{\partial BS_i}$ in the other two equations.

How do I proceed from here? What I am thinking wrong?