2014 dxdy logo

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

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


Правила форума


В этом разделе нельзя создавать новые темы.

Если Вы хотите задать новый вопрос, то не дописывайте его в существующую тему, а создайте новую в корневом разделе "Помогите решить/разобраться (М)".

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

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

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



Начать новую тему Ответить на тему На страницу Пред.  1, 2, 3, 4, 5, 6 ... 9  След.
 
 Re: Генератор для 3х зависимых дискретных величин.
Сообщение16.01.2013, 13:45 
Аватара пользователя


09/04/12
72
TOTAL в сообщении #672293 писал(а):
Sinclair в сообщении #672288 писал(а):
Я опасаюсь не того, что алгоритм не будет работать на распределении, вероятность которого один к бесконечности, а того, что по мере приближения к этому распределению, алгоритм начнет все больше ошибаться.
Если бы этого не было - можно было бы не обращать внимание на крайние случаи.
Алгоритм обязательно будет ошибаться. В крайних случая он все больше будет ошибаться. Так что осталось на практике проверить, встречаются ли частные случаи и насколько сильно алгоритм ошибается.

Проблема сложнее, чем крайние случаи.
Никак не решена проблема потери информации при задирании вероятности, как упоминается тут:
Sinclair в сообщении #672288 писал(а):
Нет. Проблема более глубокая. Смотрите. Рассмотрим упрощенный вариант:
У нас есть 3 ладьи, но которые бьют только по столбцу, но не по строке.
У нас есть 2 столбца, на каждом из которых совокупная вероятность нахождения одной из 3х ладей равна 1. Еще одна еденица вероятности распределена по оставшимся клеткам доски. Не важно, сколько мы подгоняем процесс генерации. В любом случае, у нас произойдет одно из следующих событий:
Либо вероятности нахождения ладей за пределами данных столбцов будут не нулевыми, и сможет произойти событие с ненулевой вероятностью, при котором все ладьи сгенерируются за пределами этих столбцов (хотя оба столбца должны быть заняты с вероятностью 1), либо все вероятности за пределами этих столбцов занулятся. Но тогда возникает вопрос - куда ставить третью ладью? Информация об оставшемся распределении просто потеряется.
Да, и кроме того, по мере задирания вероятности нахождения отдельных ладей в 1 по конкретным столбцам - распределение ладей по этим столбцам тоже потеряется - у каждой из них будет равная вероятность попасть туда.

То есть, у нас есть клетка, на которой зеленая ладья находится с вероятностью .66, а красная - .33. По мере отработки предложенного алгоритма обе вероятности начнут задираться к 1. Однако, в тот момент, когда первая вероятность достигнет 1, вторая будет равна .5, после чего, в ходе дальнейшего задирания соотношение начнет меняться от 1:2 к 1:1, при чем подобные отклонения начнут происходить далеко не только в крайних случаях. Можно сказать, что подобные "деформации" распределения будут скорее правилом, чем исключением.
Вот почему я пытаюсь найти другой способ решения. Например, с вероятностями непопадания.

 Профиль  
                  
 
 Re: Генератор для 3х зависимых дискретных величин.
Сообщение16.01.2013, 13:50 
Заслуженный участник
Аватара пользователя


23/08/07
5487
Нов-ск
Sinclair в сообщении #672300 писал(а):
при чем подобные отклонения начнут происходить далеко не только в крайних случаях. Можно сказать, что подобные "деформации" распределения будут скорее правилом, чем исключением.
Начнут или не начнут, будут правилом или не будут.

 Профиль  
                  
 
 Re: Генератор для 3х зависимых дискретных величин.
Сообщение16.01.2013, 13:55 
Аватара пользователя


09/04/12
72
TOTAL в сообщении #672304 писал(а):
Sinclair в сообщении #672300 писал(а):
при чем подобные отклонения начнут происходить далеко не только в крайних случаях. Можно сказать, что подобные "деформации" распределения будут скорее правилом, чем исключением.
Начнут или не начнут, будут правилом или не будут.

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

-- 16.01.2013, 14:00 --

TOTAL в сообщении #672293 писал(а):
А такой вариант.

Ставим первую ладью согласно её вероятностям. Ставим вторую ладью в оставшиеся допустимые клетки пропорционально вероятностям этих клеток. Ставим третью ладью в оставшиеся допустимые клетки пропорционально вероятностям этих клеток. Ничего отбраковывать не надо (за исключением случая, когда для очередной ладьи остались клетки с нулевой вероятностью)

Очередность ладей случайна.

Я отвечал на этот вариант здесь:
Sinclair в сообщении #672247 писал(а):
В этом случае просто итоговое распределение для красной, например, ладьи, будет усредненным распределением между тремя распределениями 1) "истинное распределение красной ладьи", 2) "распределение красной ладьи, прореженное одной ладьей", 3) "распределение красной ладьи, прореженное двумя ладьями". То есть, это тоже не будет точным.

То есть, это заведомо компроммисный вариант. Боюсь для меня он не приемлем. Во всяком случае, если я его и реализую - только убедившись, что точнее сделать нельзя.
Я не перфекционист. Но задача такова, что смещенные оценки я могу позволить только как крайнюю меру.

 Профиль  
                  
 
 Re: Генератор для 3х зависимых дискретных величин.
Сообщение16.01.2013, 14:01 
Заслуженный участник
Аватара пользователя


23/08/07
5487
Нов-ск
Sinclair в сообщении #672307 писал(а):
Да, будут правилом. Реальная задача склонна к крайним случаям. Вот почему я так этим обеспокоен.
Это означает, что в реальной задаче положения ладей сильно зависимы. Так что не надо удивляться, что не удается моделировать независимыми распределениями.

 Профиль  
                  
 
 Re: Генератор для 3х зависимых дискретных величин.
Сообщение16.01.2013, 14:07 
Заслуженный участник


12/09/10
1547
Можно генерировать положение ладей с таким расчетом, чтобы после выбраковки получить заданное распределение.
Например, если у нас есть всего 2 ячейки с видимым частотным распределением $P(\xi =1) = 0.6$, $P(\xi =2) = 0.4$
вероятность выбраковки при нахождении ладьи в первой клетке - 5%, при нахождении ладьи во второй клетке - 10%.
Тогда в первую клетку мы должны генерировать с вероятностью $x$, где $x$ находится из уравнения
$\frac{0.95x}{0.9(1-x)}=\frac 64$

Пусть у нас есть матрица наблюдаемых частот $P=(p_{ij})$; $i = 1..3$ , $j = 1..64$.
$X^{(0)} = P$. Считаем вероятности выбраковки $\Delta = (\delta_{ij})$.
Пересчитываем первую строчку $X^{(0)}$. Получаем $X^{(1)}$. Матрица выбраковки у нас, конечно же, изменилась. Пересчитываем ее. Теперь корректируем 2-ю строчку. Получаем $X^{(2)}$. Пересчитываем $\Delta$. И так далее, пока последовательность $X^{(3k)}$ не сойдется к некоторому $X$ (что, конечно, не факт, но скорее всего)

 Профиль  
                  
 
 Re: Генератор для 3х зависимых дискретных величин.
Сообщение16.01.2013, 14:12 
Аватара пользователя


09/04/12
72
TOTAL в сообщении #672311 писал(а):
Sinclair в сообщении #672307 писал(а):
Да, будут правилом. Реальная задача склонна к крайним случаям. Вот почему я так этим обеспокоен.
Это означает, что в реальной задаче положения ладей сильно зависимы. Так что не надо удивляться, что не удается моделировать независимыми распределениями.

Ну, во-первых, как-то все таки удается. Во-вторых, как то все таки делать надо. Я выбираю лучшее решение в нелучших условиях. У меня есть распределения, и есть зависимость, которую надо учесть. Нужно решить задачу с максимальной утилизацией имеющейся информации - другой все равно нет, и не предвидится. Решить настолько хорошо, насколько будет возможно. Решение с задиранием вероятности таким не является - фактически, оно выдает результат с распределением, отличающимся от заданого в очень большом спектре случаев. Для второго варианта решения, представленного в заглавном посте этой проблемы и то нет. Может туда следует копать. Кроме того, я отрабатываю вариант с вероятностями непопадания.

 Профиль  
                  
 
 Re: Генератор для 3х зависимых дискретных величин.
Сообщение16.01.2013, 14:16 
Заслуженный участник
Аватара пользователя


23/08/07
5487
Нов-ск
Sinclair в сообщении #672307 писал(а):
Я отвечал на этот вариант здесь:
В этом случае просто итоговое распределение для красной, например, ладьи, будет усредненным распределением между тремя распределениями 1) "истинное распределение красной ладьи", 2) "распределение красной ладьи, прореженное одной ладьей", 3) "распределение красной ладьи, прореженное двумя ладьями". То есть, это тоже не будет точным.

Составьте и численно решите систему уравнений относительно распределений, так что итоговое усредненное будет каким надо.

 Профиль  
                  
 
 Re: Генератор для 3х зависимых дискретных величин.
Сообщение16.01.2013, 14:24 
Аватара пользователя


09/04/12
72
Cash в сообщении #672315 писал(а):
Можно генерировать положение ладей с таким расчетом, чтобы после выбраковки получить заданное распределение.
Например, если у нас есть всего 2 ячейки с видимым частотным распределением $P(\xi =1) = 0.6$, $P(\xi =2) = 0.4$
вероятность выбраковки при нахождении ладьи в первой клетке - 5%, при нахождении ладьи во второй клетке - 10%.
Тогда в первую клетку мы должны генерировать с вероятностью $x$, где $x$ находится из уравнения
$\frac{0.95x}{0.9(1-x)}=\frac 64$

Пусть у нас есть матрица наблюдаемых частот $P=(p_{ij})$; $i = 1..3$ , $j = 1..64$.
$X^{(0)} = P$. Считаем вероятности выбраковки $\Delta = (\delta_{ij})$.
Пересчитываем первую строчку $X^{(0)}$. Получаем $X^{(1)}$. Матрица выбраковки у нас, конечно же, изменилась. Пересчитываем ее. Теперь корректируем 2-ю строчку. Получаем $X^{(2)}$. Пересчитываем $\Delta$. И так далее, пока последовательность $X^{(3k)}$ не сойдется к некоторому $X$ (что, конечно, не факт, но скорее всего)

Насколько я понимаю, вы воспроизвели (более подробно и формализованно) вот это решение - post672283.html#p672283
Проблемы этого решения я указывал здесь - post672288.html#p672288
Вкратце - данное решение будет приемлемым только при относительно равномерном распределении ладей по доске. Если они склонны группироваться вокруг каких то линий - данное решение работает плохо.

-- 16.01.2013, 14:31 --

TOTAL в сообщении #672320 писал(а):
Составьте и численно решите систему уравнений относительно распределений, так что итоговое усредненное будет каким надо.

Я не понял, это как?
Кроме того, мне кажется, что исходя из тех же рассуждений, что я написал - любой способ решения через нахождения "исходных" распределений, с неучтенной выбраковкой, для последующей генерации с выбраковкой, и получением в итоге исходных распределений - в принципе не верен. Проблема не в том, как их найти. Проблема в том, что в ряде случаев их не существует вовсе. Например, как было проказано в примере с 2я столбцами с суммарной вероятностью 1. Какие бы ни брать модифицированные распределения, при последовательной генерации с выбраковкой нельзя получить исходные распределение в принципе.
Надо искать другой путь решения.

 Профиль  
                  
 
 Re: Генератор для 3х зависимых дискретных величин.
Сообщение16.01.2013, 14:38 
Заслуженный участник
Аватара пользователя


23/08/07
5487
Нов-ск
Sinclair в сообщении #672325 писал(а):
Надо искать другой путь решения.
Что считать решением?

 Профиль  
                  
 
 Re: Генератор для 3х зависимых дискретных величин.
Сообщение16.01.2013, 14:45 
Аватара пользователя


09/04/12
72
TOTAL в сообщении #672335 писал(а):
Sinclair в сообщении #672325 писал(а):
Надо искать другой путь решения.
Что считать решением?

Генератор.
То есть, мне не важно, будут ли там какие то модифицированные распределения использоваться, или вообще будет другим способом получаться результат. Главное, чтобы работало.
Например, если мне удастся написать генератор через работу с вероятностями непопадания - это подойдет. Даже если после каждой сгенерированной ладьи надо будет пересчитывать остальные.
Во всяком случае данный подход легко решает проблему со столбцами единичной вероятности - по мере такого решения просто вероятность непопадания в эти столбцы зануляется, и элементы за пределами этих столбцов выкидываются первыми. Но я еще не до конца продумал этот вариант, и не доказал, что он дает нужное распределение.
Вот, кстати, задам сразу вопрос по этому новому решению:
Вот у меня есть, например, какое то дискретное распределение. Никаких 3х величин, просто одномерное распределение. А я хочу преобразить его в "распределение непопадания" - то есть, в такое распределение, распределяя по которому значения в соответствии с вероятностями, шанс того, что некий конкретный элемент выпадет последним будет равно шансу того, что он выпадет в исходном определении. Можно как нибудь обычное распределение преобразовать в "распределение непопадания"?

 Профиль  
                  
 
 Re: Генератор для 3х зависимых дискретных величин.
Сообщение16.01.2013, 14:52 
Заслуженный участник
Аватара пользователя


06/04/10
3152
Sinclair в сообщении #672273 писал(а):
nikvic в сообщении #672268 писал(а):
Sinclair
Можно ли трактовать задачу следующим образом.
Имееется три распределения клеток (извлекаются статистикой). Требуется найти какое-либо совместное распределение с указанным дополнительным свойством.

Да, именно так. Я именно об этом говорю.
Если точнее - находить распределение не обязательно, надо построить его генератор.

У Вас - куб-64, три распределения по осям и куча запретных "ячеек" - там стоит нулевая вероятность. Вполне можно вероятность "слоя" (фиксируется одна координата, т.е. цвет и клетка доски) распределить как-то, хоть равномерно, по его свободным ячейкам.

 Профиль  
                  
 
 Re: Генератор для 3х зависимых дискретных величин.
Сообщение16.01.2013, 15:03 
Аватара пользователя


09/04/12
72
nikvic в сообщении #672339 писал(а):
У Вас - куб-64, три распределения по осям и куча запретных "ячеек" - там стоит нулевая вероятность. Вполне можно вероятность "слоя" (фиксируется одна координата, т.е. цвет и клетка доски) распределить как-то, хоть равномерно, по его свободным ячейкам.

Да, вы поняли правильно.
Я понимаю, что вы предложили, но мне как то сложно размышлять об этом в виде куба. Я попробую сначала одномерную модель - вот есть 8 ячеек, и 3 фишки, которые не могут занимать одну клетку. Есть распределения каждой фишки по этим 8и клеткам. Надо построить генератор этого распределения. Я, конечно, сглупил, что задал задачу в двумерном виде. Надо было сразу сводить к одному измерению, и задавать в таком виде.

 Профиль  
                  
 
 Re: Генератор для 3х зависимых дискретных величин.
Сообщение16.01.2013, 15:13 
Заслуженный участник


11/05/08
32166
Sinclair в сообщении #672342 писал(а):
Есть распределения каждой фишки по этим 8и клеткам. Надо построить генератор этого распределения.

А откуда следует, что такие распределения возможны?

 Профиль  
                  
 
 Re: Генератор для 3х зависимых дискретных величин.
Сообщение16.01.2013, 15:26 
Заслуженный участник
Аватара пользователя


06/04/10
3152
Sinclair в сообщении #672342 писал(а):
мне как то сложно размышлять об этом в виде куба

Трёхмерный массив, восьмеричное представление координаты :wink:
Это всё не числа, а события, их можно занумеровать потом и составить интегральную функцию распределения номера события - около 100К чисел "с нарастающим итогом".

 Профиль  
                  
 
 Re: Генератор для 3х зависимых дискретных величин.
Сообщение16.01.2013, 15:39 
Аватара пользователя


09/04/12
72
ewert в сообщении #672346 писал(а):
Sinclair в сообщении #672342 писал(а):
Есть распределения каждой фишки по этим 8и клеткам. Надо построить генератор этого распределения.

А откуда следует, что такие распределения возможны?

Распределения апостериорные. Ну вот в заглавном посте я описывал механизм получения такого распределения для шахматной доски. Такой же можно получить и для несокльких клеток, принцип тот же.

-- 16.01.2013, 15:42 --

nikvic в сообщении #672349 писал(а):
Sinclair в сообщении #672342 писал(а):
мне как то сложно размышлять об этом в виде куба

Трёхмерный массив, восьмеричное представление координаты :wink:
Это всё не числа, а события, их можно занумеровать потом и составить интегральную функцию распределения номера события - около 100К чисел "с нарастающим итогом".

Сначала нужно это решение воспроизвести для одномерного случая.
И вот вопрос сразу. Про трехмерный ваш случай. У вас ведь каждая ячейка входит сразу в 3 слоя - по каждой координате. Если мы распределим вероятность одного измерения по слою, то распределение вероятностей других слоев по этим же ячейкам будет увеличивать вероятность этого слоя, так? В этом случае распределение получается не то, которое нужно.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 127 ]  На страницу Пред.  1, 2, 3, 4, 5, 6 ... 9  След.

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



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

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


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

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