Разыграть набор векторов

[thepooh]

Добрый день! Подскажите, пожалуйста, как мне разыграть набор из N векторов размерности M, каждая компонента которых равна 0 или 1, если известны только вероятности каждой компоненты быть равной 1 и вероятности каждой пары компонент быть равными 1 одновременно.

[Null]

thepooh в сообщении #1577055 писал(а):

если известны только вероятности каждой компоненты быть равной 1 и вероятности каждой пары компонент быть равными 1 одновременно.

Этой информации не достаточно для однозначного определения распределения случайного вектора.
Например распределение $\mathbb{Z}_2^3$ не отличимо от равномерного по всем векторам.
$P(x=(000))=0$
$P(x=(001))=0.25$
$P(x=(010))=0.25$
$P(x=(011))=0$
$P(x=(100))=0.25$
$P(x=(101))=0$
$P(x=(110))=0$
$P(x=(111))=0.25$

[thepooh]

Null в сообщении #1577064 писал(а):

Этой информации не достаточно для однозначного определения распределения случайного вектора.

Да я знаю, что это не однозначное задание распределения.
Но в том и задача, что все остальные параметры распределения не важны, их можно задать как угодно или как удобно.
Требуется удовлетворить только единичным и парным вероятностям.
Ещё проблема в том, что числа довольно большие, то есть размерность векторов M~1000, количество векторов N~10000.
Я пробовал сделать так:
1. Удовлетворить единичным вероятностям несложно, для этого мы просто разыгрываем каждую компоненту каждого вектора в соответствии с заданной для неё вероятностью.
2. При этом мы скорее всего получим парные вероятности, не соответствующие тем, которые хотим получить.
3. Поэтому можно попробовать менять местами i-тые компоненты между различными векторами.
Но получить эффективный алгоритм такого типа у меня не получилось.

[Null]

Если я не ошибся если нужное вам распределение существует, то существует требуемое распределение с $\frac{M^2+M}{2}$(плюс минус 1)векторами выпадающими с ненулевой вероятностью. На хранение требуется $O(M^3)$ памяти и на поиск $O(2^M)$ времени(сомневаюсь что можно быстрее). Может у вас есть какая-нибудь дополнительная информация? Например, все $P(x_i=1)=a$, а все $P(x_i=1\cap x_j=1)=b$

[thepooh]

Извините меня, наверное сразу надо было описать задачу как она есть.
Наверное все знают про MNIST, но на всякий случай напишу, что это набор образов (чёрно белые цифры от 0 до 9) размером 28х28 пикселей.
60000 обучающих образов и 10000 контрольных.
На самом деле там используется 255 оттенков серого для каждого пикселя, но переведём их в нули и единицы, например, по правилу: пиксель = 1, если значение > 127, и пиксель = 0, в противном случае.
Теперь мы можем вычислить вероятности каждого пикселя на выборке.
После этого мы можем разыграть новый набор образов, используя эти вероятности и считая пиксели независимыми.
Получим такие бесформенные облачка в центре экрана, т.к. исходные образы центрированы.
Что если теперь мы попробуем учесть дополнительно парные вероятности, игнорируя тройные, четверные и т.д.
Получим ли мы что-то более похожее на исходные образы?

[Null]

Тогда можно запомнить эти 60000 обучающих образов и генерировать их с равной вероятностью. Таблицу можно заархивировать. Нужны дополнительные требования.

[alisa-lebovski]

Мне кажется, нечто подобное называется марковская сеть или марковское случайное поле.

[thepooh]

Null в сообщении #1577169 писал(а):

Тогда можно запомнить эти 60000 обучающих образов и генерировать их с равной вероятностью. Таблицу можно заархивировать. Нужны дополнительные требования.

Например можно добавить условие, что разыграть нужно в два раза больше образов.

[Sonic86]

thepooh в сообщении #1577099 писал(а):

но переведём их в нули и единицы, например, по правилу: пиксель = 1, если значение > 127, и пиксель = 0, в противном случае.

В результате часть инфы будет похерена - я там видел 1 картинку пятерки, которая от такого преобразования превращается в почти шестерку.

thepooh в сообщении #1577099 писал(а):

Получим такие бесформенные облачка в центре экрана, т.к. исходные образы центрированы.

Нифига они там не центрированы, только приближенно.

thepooh в сообщении #1577099 писал(а):

Что если теперь мы попробуем учесть дополнительно парные вероятности, игнорируя тройные, четверные и т.д.

Не очень понятно, как тогда сэмплировать изображения из вероятностей, потому что каждый пиксель будет входить в несколько таких вероятностей. Может еще подробнее напишете?