2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 Разыграть набор векторов
Сообщение14.01.2023, 10:20 


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

 Профиль  
                  
 
 Re: Разыграть набор векторов
Сообщение14.01.2023, 11:23 
Заслуженный участник


12/08/10
1608
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$

 Профиль  
                  
 
 Re: Разыграть набор векторов
Сообщение14.01.2023, 13:38 


27/08/17
52
Null в сообщении #1577064 писал(а):
Этой информации не достаточно для однозначного определения распределения случайного вектора.

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

 Профиль  
                  
 
 Re: Разыграть набор векторов
Сообщение14.01.2023, 14:20 
Заслуженный участник


12/08/10
1608
Если я не ошибся если нужное вам распределение существует, то существует требуемое распределение с $\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$

 Профиль  
                  
 
 Re: Разыграть набор векторов
Сообщение14.01.2023, 18:05 


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

 Профиль  
                  
 
 Re: Разыграть набор векторов
Сообщение15.01.2023, 12:04 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Разыграть набор векторов
Сообщение15.01.2023, 12:15 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: Разыграть набор векторов
Сообщение15.01.2023, 15:33 


27/08/17
52
Null в сообщении #1577169 писал(а):
Тогда можно запомнить эти 60000 обучающих образов и генерировать их с равной вероятностью. Таблицу можно заархивировать. Нужны дополнительные требования.

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

 Профиль  
                  
 
 Re: Разыграть набор векторов
Сообщение16.01.2023, 13:57 
Заслуженный участник


08/04/08
8556
thepooh в сообщении #1577099 писал(а):
но переведём их в нули и единицы, например, по правилу: пиксель = 1, если значение > 127, и пиксель = 0, в противном случае.
В результате часть инфы будет похерена - я там видел 1 картинку пятерки, которая от такого преобразования превращается в почти шестерку.

thepooh в сообщении #1577099 писал(а):
Получим такие бесформенные облачка в центре экрана, т.к. исходные образы центрированы.
Нифига они там не центрированы, только приближенно.

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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 9 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group