Вычисление вероятностей цепи Маркова со значениями, слишком большими для возведения в степень

Я использую формулу exp(X) в качестве скорости для цепи Маркова. Таким образом, соотношение выбора одной ссылки над другой равно exp(X1)/exp(X2). Моя проблема в том, что иногда X очень велико, поэтому exp(X) будет превышать диапазон double.

В качестве альтернативы: при заданном массиве X[i] с некоторым X[i] настолько большим, что exp(X[i]) выходит за пределы диапазона double, вычислить для каждого i exp(X[i]) / S, где S является суммой всех exp(X[i]).


java estimation exp markov-chains double-precision
person Masood_mj    schedule 17.08.2012    source источник
comment
Я внес изменения, чтобы уточнить ваш вопрос и мой ответ. Вы можете отменить их, если я ошибся.   -  person Eric Postpischil    schedule 17.08.2012

Ответы (1)


arrow_upward
3
arrow_downward

Этот псевдокод должен работать:

Let M = the largest X[i].

For each i:
    Subtract M from X[i].

Let S = the sum of exp(X[i]) for all i.

For each i:
    The probability for this i is exp(X[i]) / S.

Если M велико, то после шага вычитания некоторые X[i] будут настолько малы (имеют большие отрицательные значения), что их exp(X[i]) будет равен нулю с двойной точностью. Однако фактическая вероятность этих элементов настолько ничтожна, что нет никакой практической разницы между их фактической вероятностью и нулем, поэтому вполне нормально, что exp(X[i]) уменьшается до нуля.

Помимо ошибок потери значимости и округления, вероятности должны быть одинаковыми после преобразования вычитания, потому что:

  • ехр(х-М) = ехр(х)/ехр(М).
  • Это деление одинаково влияет как на числитель, так и на знаменатель вероятности, поэтому отношение остается прежним.
person Eric Postpischil    schedule 17.08.2012
comment
Понятно, но я хочу запустить цепь Маркова. Я должен выбрать ссылку с вероятностью exp(X1)/sum(exp(Xi)). Вместо этого я создаю кумулятивный массив exp(Xi). И сгенерируйте число от 0 до exp(Xn). Так что мне не нужно соотношение. мне нужны реальные цифры - person Masood_mj; 17.08.2012
comment
Что слишком велико, чтобы представлять его как двойное число, X или exp(X)? (Вы написали «это выйдет из двойного диапазона», когда «X» было ближайшим предшествующим существительным.) Если X слишком велико, вы должны решить эту проблему, прежде чем беспокоиться об exp(X). Если exp(X) слишком велико, нормализуйте свой Xi, вычитая из всех них наибольший Xi (сделав наибольший из них равным 0, а остальные неположительными). Это должно оставить все значимые exp(Xi) в пределах диапазона двойного числа без изменения вероятностей. (Любой Xi, который становится большим отрицательным значением, будет иметь мизерную вероятность, так что это нормально, если exp(Xi) равно нулю.) - person Eric Postpischil; 17.08.2012