1
$\begingroup$

I'm working on a machine learning algorithm and have gotten stuck with how to rebalance a discrete probability distribution. I have a distribution represented as a simple array of $n$ numbers which are all bounded between $0$ to $1$ and that always sum to $1$. At a particular point I wish to update on of the numbers in the distribution by some random amount (it's still between $0$ and $1$) . At that particular point I must also update the remaining $n-1$ numbers so that the sum of the numbers in the distribution remain $1$.

My problem is that any algorithm I come up with for rebalancing fails for certain cases.

First algorithm was to uniformly distribute the difference to the remaining values. Obviously that didn't work (eg. can't subtract $0.1$ from $0.05$).

Second approach was as follows:

Let the distribution be represented by $\{p_{1},p_{2},...,p_{n}\}$ and let's assume I wish to update $p_{1}$ for the sake of argument.

Let $p^{new}_{1}$ be the new value for $p_{1}$.

Then I rebalance the remaining $n-1$ numbers by:

$p_{i} = p_{i} + ( p_{1} - p^{new}_{1} ) \frac{p_{i}}{sum}$

Where $sum = \sum_{j=2}^{n}(p_{j})$

Which also fails. For example, if some values in the distribution are $0$ then they will not get increased in the case of a positive update. I tried to correct this by checking if the sum is $0$ but that only allows me to solve the case where all $n-1$ numbers are $0$.

I feel like this should probably be very easy and that I'm just having a brain freeze at the moment...

$\endgroup$
  • 2
    $\begingroup$ Suppose you are updating $p_j$ to $p_j^{\textrm{new}}$. How about just setting $p_i^{\textrm{new}}=\frac{p_i}{p_j^{\textrm{new}}+\sum_{k\neq j}p_k}$? $\endgroup$ – assumednormal Sep 9 '12 at 17:23
  • $\begingroup$ Its similar to what I have tried, problem is, what if $p_{i}=0$ then $p^{new}_{i}$ will stay at $0$ even if we're rebalancing positively. $\endgroup$ – Erik Sep 9 '12 at 18:06
  • 1
    $\begingroup$ Why would you want a probability of zero to update to a positive number? How would changing the probability of one outcome occurring effect an outcome with zero probability of occurring? $\endgroup$ – assumednormal Sep 9 '12 at 18:11
  • 1
    $\begingroup$ It would be helpful to know more about the algorithm. What exactly are you trying to do with this algorithm? $\endgroup$ – assumednormal Sep 9 '12 at 18:27
  • 1
    $\begingroup$ Erik, @Max has directed you to an general solution: you are free to update the $p_k$ in any way you wish in response to updating $p_j$ (so long as you keep them non-negative). Afterwards, normalize the new values to sum to unity by dividing each by their sum. This is so extremely general as to be almost without content, which is why additional information about what you're trying to accomplish would help. $\endgroup$ – whuber Sep 9 '12 at 18:28
1
$\begingroup$

In the comments you say that the "algorithm in question is used to find a neighbor distribution in the search space".

So, here is a simple (@whuber?) way to get another point on the Simplex which is "close" to a given one.

Suppose that your current point is $x=(x_1,x_2,\dots,x_k)$, with $x_i\geq 0$ and $\sum_{i=1}^k x_i=1$.

Let $a_0$ be a positive constant.

Define $Y=(Y_1,Y_2,\dots,Y_k)\sim \mathrm{Dirichlet}(a_0 x_1, a_0 x_2, \dots,a_0 x_k)$. By the properties of the Dirichlet distribution, we know that $$ \mathrm{E}[Y_i] = \frac{a_0 x_i}{a_0 x_1+a_0x_2+\dots+a_0 x_k} = \frac{a_0 x_i}{a_0( x_1+x_2+\dots+x_k)} = x_i \, , $$ for $i=1,\dots,k$, and the concentration parameter is just $$ a_0 x_1+a_0x_2+\dots+a_0 x_k = a_0 \, . $$ So, if you want your next point to be close to the current point, you choose a "big" value for $a_0$. Small values of $a_0$ will "spread out" the distribution of $Y$, which is "centered" on $x$.

Here is an implementation in R.

rdirichlet <- function(a) {
    y <- rgamma(length(a), a, 1)
    return(y / sum(y))
}

a0 <- 10

x = c(0.1, 0.2, 0.1, 0.6)

y <- rdirichlet(a0 * x)

Finally, how to deal with zero components? Add $(\epsilon,\epsilon,\dots,\epsilon$) to $x$ before drawing $Y$. Fine tune $a_0$ and $\epsilon$ and it will probably work.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ +1 It's a big gun, but a very flexible one. $\endgroup$ – whuber Sep 10 '12 at 20:15

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.