Распределения на подмножествах

9

Мне интересно, есть ли какие-либо стандартные распределения на подмножествах целых чисел . Эквивалентно, мы могли бы выразить это как распределение по вектору длины двоичных результатов, например, если то соответствует вектору .{1,2,...,J}JJ=5{1,3,5}(1,0,1,0,1)

В идеале я ищу некое распределение , происходящее из семейства, индексируемого конечномерным параметром , которое распределит свою массу таким образом, что два двоичных вектора и будут иметь одинаковый вероятность того, что они «близки» друг к другу, т.е. и имеют схожие вероятности. Действительно, то, что я намерен сделать, я надеюсь, это поставить априту на , что если я знаю, что довольно велика, то , вероятно, велика относительно векторов, удаленных от .νθ()θr1r2r1=(0,0,1,0,1)r2=(0,0,1,1,1)θνθ(r1)νθ(r2)r1

Одна из стратегий , которая приходит на ум бы поставить метрику или некоторую другую меру дисперсии на dθ на {0,1}J , а затем принять νθ(r)exp(dθ(r,μ)) , или что-то похожее. Явным примером будет по аналогии с нормальным распределением. Это хорошо, но я надеюсь, что есть что-то стандартное и поддающееся байесовскому анализу; с этим я не могу записать нормализующую константу.exp{rμ2/(2σ2)}

парень
источник
Выборка подмножества является основной проблемой в методологии обследования.
Стефан Лоран
@ Стефан, конечно, но я думаю, что моя проблема в том, что у меня есть какая-то дополнительная желаемая структура, которую я хотел бы, чтобы мой дистрибутив отражал. Возможно, формулировка вопроса в терминах подмножеств была плохой идеей, поскольку у меня есть смутное представление о расстоянии, работающем для меня.
парень
Вы хотели написать "... тогда , вероятно, мало ..."? Что касается нормализующей константы, рассмотрите возможность использования расстояния Хэмминга для метрики: для семейств распределений в масштабе местоположений вы можете вычислить эту константу как сумму только слагаемых. Более того, все такие семейства, которые соответствуют вашим критериям, могут быть описаны только дискретными параметрами (для местоположения) и непрерывными параметрами. J + 1 J Jvθ(r2)J+1JJ
whuber
@ whuber нет, я имел в виду большое. Я хочу, чтобы распределял его массу по точкам, которые находятся близко друг к другу. Вероятно, было бы более уместно сформулировать вопрос как наложение распределения по вершинам гиперкуба. Я рассмотрел расстояние Хэмминга (которое, я думаю, такое же, как в моем случае); Я, вероятно, хотел бы настроить его каки я думаю, что, вероятно, придется сделать MCMC для выборки из такого дистрибутива. L 1| r i - μ iνθ()L1|riμiσi|
парень
О, теперь я вижу. Но это не то, что вы изначально сказали. Например, в вашей характеристике, если велико, а - это набор векторов, "далеко" от , а - это любой вектор, не в , то также должен "вероятно" быть большим Но «не далеко» и «близко» не означают одно и то же. Было бы проще - и более внутренне согласованно - перефразировать условие, как вы это сделали в своем комментарии. Но нет, вам не нужен MCMC для выборки из распределений масштаба местоположения на основе расстояний Хэмминга: есть гораздо более эффективные способы. R r 1 r 2 R ν ( r 2 )ν(r1)Rr1r2Rν(r2)
whuber

Ответы:

6

Вы можете предпочесть семейства местоположений, основанные на расстоянии Хэмминга , из-за их богатства, гибкости и вычислительной управляемости.


Обозначения и определения

Напомним , что в свободном конечномерном модуле с базисом ( е 1 , е 2 , ... , е J ) , то расстояние Хэмминга δ H между двумя векторами v = v 1 е 1 + + v J е J и ш = ш 1 e 1 + + w J e J - количество мест i, где v iV(e1,e2,,eJ) δHv=v1e1++vJeJw=w1e1++wJeJi .viwi

Для любого начала координат расстояние Хэмминга разбивает V на сферы S i ( v 0 ) , , где . Когда основное кольцо имеет элементов, имеет элементов, а имеет элементов. (Это сразу следует из наблюдения, что элементы отличаются от в точностиv0VVSi(v0)S i ( v 0 ) = { wV | δ H ( w , v 0 ) = i } n V n J S i ( v ) ( Ji=0,1,,JSi(v0)={wV | δH(w,v0)=i}nVnJSi(v)Si(v)vi ( J(Ji)(n1)iSi(v)vi мест - из которых есть возможностей - и что существует, независимо, выбор значений для каждого места.) п-1(Ji)n1

Аффинный перевод в действует естественным образом в его распределениях, давая семейства местоположений. В частности, когда - это любое распределение на (что означает чуть больше, чем , для всех и ) и - любой элемент из , тогда также является распределением гдеf V f : V [ 0 , 1 ] f ( v ) 0 vV vV f ( v ) = 1 w V f ( w )VfVf:V[0,1]f(v)0vVvVf(v)=1wVf(w)

f(w)(v)=f(vw)

для всех . Расположение семьи распределений инвариантна относительно этого действия: означает для всех .Ом F Ом F ( v )Ом vVvV ΩfΩf(v)ΩvV

строительство

Это позволяет нам определять потенциально интересные и полезные семейства распределений, определяя их формы в одном фиксированном векторе , который для удобства я буду считать и переводя эти «порождающие распределения» под действием чтобы получить полное семейство . Для достижения желаемого свойства, чтобы имело сопоставимые значения в близлежащих точках, просто требуется это свойство всех генерирующих распределений.0 = ( 0 , 0 , , 0 ) V Ω fv0=(0,0,,0)VΩf

Чтобы увидеть, как это работает, построим семейство местоположений всех распределений, которые уменьшаются с увеличением расстояния. Поскольку возможны только расстояния Хэмминга, рассмотрим любую убывающую последовательность неотрицательных действительных чисел = . Наборa 0 a 0a 1a J0J+1a0a0a1aJ0

A=i=0J(n1)i(Ji)ai

и определите функцию помощьюfa:V[0,1]

fa(v)=aδH(0,v)A.

Тогда, как несложно проверить, является распределением на . Кроме того, тогда и только тогда, когда является положительным кратным (как векторы в ). Таким образом, если нам нравится, мы можем стандартизировать к . V f a = f a aa R J + 1 a a 0 = 1faVfa=faaaRJ+1aa0=1

Соответственно, эта конструкция дает явную параметризацию всех таких локально-инвариантных распределений, которые уменьшаются с расстоянием Хэмминга: любое такое распределение имеет вид для некоторой последовательности и некоторый вектор . = 1 12J0 vVfa(v)a=1a1a2aJ0vV

Эта параметризация может обеспечить удобную спецификацию априоров: разложить их в априор в расположении и априор в форме . (Конечно, можно рассмотреть больший набор приоров, где местоположение и форма не являются независимыми, но это было бы более сложным делом.)va

Генерация случайных значений

Один из способов выборки из заключается в поэтапном распределении его по распределению по сферическому радиусу, а другое распределение зависит от каждой сферы:fa(v)

  1. Нарисуйте индекс из дискретного распределения на заданного вероятностями , где определено, как и раньше ,{ 0 , 1 , , J } ( Ji{0,1,,J}A(Ji)(n1)iai/AA

  2. Индекс соответствует множеству векторов, отличающихся от ровно местами. Поэтому выберите те которые размещаю из возможных подмножеств, давая каждому равную вероятность. (Это только образец Нижние индексы из без замены.) Пусть это подмножество место записывается .против я я ( Джivii яJяI(Ji)iJ iI

  3. Нарисуйте элемент , независимо выбрав значение равномерно из набора скаляров, не равных для всех и в противном случае установите . Эквивалентно, создайте вектор , выбрав случайным образом из ненулевых скаляров, когда и в противном случае установите . Установите .w j v j j I w j = v j u u j j I u j = 0 w = v + uwwjvjjIwj=vjuujjIuj=0w=v+u

Шаг 3 не нужен в двоичном случае.


пример

Вот Rреализация для иллюстрации.

rHamming <- function(N=1, a=c(1,1,1), n=2, origin) {
  # Draw N random values from the distribution f_a^v where the ground ring
  # is {0,1,...,n-1} mod n and the vector space has dimension j = length(a)-1.
  j <- length(a) - 1
  if(missing(origin)) origin <- rep(0, j)

  # Draw radii `i` from the marginal distribution of the spherical radii.
  f <- sapply(0:j, function(i) (n-1)^i * choose(j,i) * a[i+1])
  i <- sample(0:j, N, replace=TRUE, prob=f)

  # Helper function: select nonzero elements of 1:(n-1) in exactly i places.
  h <- function(i) {
    x <- c(sample(1:(n-1), i, replace=TRUE), rep(0, j-i))
    sample(x, j, replace=FALSE)
  }

  # Draw elements from the conditional distribution over the spheres
  # and translate them by the origin.
  (sapply(i, h) + origin) %% n
}

В качестве примера его использования:

test <- rHamming(10^4, 2^(11:1), origin=rep(1,10))
hist(apply(test, 2, function(x) sum(x != 0)))

Для извлечения iid элементов из дистрибутива потребовалось секунды, где , (двоичный регистр), и экспоненциально уменьшается.0.2104fa(v)J=10n=2v=(1,1,,1)a=(211,210,,21)

(Этот алгоритм не требует уменьшения ; таким образом, он будет генерировать случайные изменения из любого семейства местоположений, а не только унимодальных.)a

Whuber
источник
Спасибо за это! Расстояние Хэмминга в этом случае равно в ограниченном вершинами куба; в этом контексте расстояние Хэмминга действует изотропно. Отход от этого, я думаю, усложняет эти вещи, потому что у меня есть больше чем различных значений для моего измерения расстояния? Есть общие комментарии по этому поводу? L1RJJ
парень
Да: выбор функций расстояния будет зависеть от того, что представляют значения в . Поскольку вопрос сформулирован абстрактно, нам действительно нечего формировать мнения о том, что будет хорошим выбором. Расстояние Хемминга будет подходящим для номинальных значений и, возможно, в других случаях, но другие расстояния могут работать лучше, когда для набора { 1 , 2 , , n } присуще чувство расстояния . В двоичном случае n = 2 сложно обобщить расстояния Хэмминга: они уже довольно общие. {1,2,,n}{1,2,,n}n=2
Whuber
1

Выборка из k-детерминантного точечного процесса моделирует распределение по подмножествам, которое поощряет разнообразие, так что подобные элементы с меньшей вероятностью встречаются вместе в выборке. Обратитесь к K-детерминантной выборке точечного процесса Алекса Кулеша, Бена Таскара.

катафалк
источник