2014 dxdy logo

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

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


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


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

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

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

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

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



Начать новую тему Ответить на тему
 
 Относительная позиция шара, вероятно, задача по ТВ
Сообщение07.10.2013, 14:33 


17/10/08

1313
Пусть имеем некоторое ограниченное неизвестное число шаров $m$, каждый из которых имеет номер $k$ (нумерация начинается с единицы). Относительной позицией шара назовем число $(k-1)/(m-1)$
Случайным образом берется шар (его номер по-прежнему неизвестен) – назовем его тестовым. Проводится ряд экспериментов, в каждом из которых выбирается $n_i-1$ шаров. Результат эксперимента принимает значение $b_i=1$, если тестовый шар имеет меньший номер, чем у каждого из $n_i-1$ выбранных в эксперименте. Если это не так, то результат эксперимента $b_i=0$.

Требуется оценить относительную позицию шара по экспериментальным данным ($n_i$ и $b_i$) – все остальное считается неизвестным.
Не могу сообразить, можно ли построить корректную вероятностную модель… Или нужно сделать какие-либо еще предположения.

 Профиль  
                  
 
 Re: Относительная позиция шара, вероятно, задача по ТВ
Сообщение07.10.2013, 16:29 
Заслуженный участник
Аватара пользователя


13/08/08
14430
Зачем нужна именно относительная позиция, непонятно. Общее количество шаров же не меняется. Но это не важно.

Можно заранее построить таблицу $m\times (m-1)$ c вероятностью для каждого тестового номера получить $1$ при каждом количестве выбираемых шаров. Это легко сделать комбинаторно.

Потом определить, при каком тестовом номере экспериментальные данные ближе всего к теоретическим.

 Профиль  
                  
 
 Re: Относительная позиция шара, вероятно, задача по ТВ
Сообщение07.10.2013, 16:42 


17/10/08

1313
$m$ по условию задачи неизвестно...

Видимо, можно составить максимальное правдоподобие...

 Профиль  
                  
 
 Re: Относительная позиция шара, вероятно, задача по ТВ
Сообщение07.10.2013, 19:45 
Заслуженный участник
Аватара пользователя


23/11/06
4171
"Тестовый" шар вынут навсегда? В $i$-м эксперименте $n_i-1$ шаров берутся без возвращения или с возвращением? Если с возвращением, то действительно все $n_i$ разные? Кстати, смысл отнимания единицы в $n_i-1$ вообще непонятен. И если выбор без возвращения, то распределения результатов опыта через параметр $\theta=\dfrac{k-1}{m-1}$ не выражаются.

Если тестовый шар ушёл навсегда и каждые $n_i-1$ шаров берутся с возвращением, то $\mathsf P_\theta(b_i=1)=(1-\theta)^{n_i-1}$, и функция правдоподобия выборки $b_1,\ldots,b_n$ есть
$$
f(\theta;\, \vec b)=(1-\theta)^{\sum b_i(n_i-1)} \prod \bigl(1-(1-\theta)^{n_i-1}\bigr)^{1-b_i}.
$$
При неодинаковых $n_i$ точка максимума функции правдоподобия находится разве что численно. Если все одинаковы ($n_i-1\equiv s$), то $\hat\theta=1-\left(\overline b\right)^{1/s}$.

 Профиль  
                  
 
 Re: Относительная позиция шара, вероятно, задача по ТВ
Сообщение08.10.2013, 00:18 


17/10/08

1313
Задача сформулирована отсюда:
https://www.kaggle.com/c/expedia-personalized-sort

Суть задачи – в предсказании, какой отель выберет посетитель. На сайте, задав параметры поиска, пользователь получает список из рекомендуемых отелей. Примерно от 5-ти до 60-ти, из чего и выбирает.
Эти данные собраны за некоторый период. Обучающая выборка где-то 10 млн. записей (в ней указано, что выбрал пользователь) – где-то 0.5 млн. поисков, тестовая – примерно 6 млн. (для них нужно упорядочить в каждом поиске пользователя отели так, чтобы в действительности выбранный отель оказался как можно выше в списке)

Одна их очевидных характеристик отеля – это его «рейтинг», с помощью которого отели просто сортируются для пользователя. Описанная выше задача – это построение рейтинга для одного отеля. Понятно, что это не единственная характеристика в задаче, но весьма значимая.

Конечно, с точки зрения ТВ, имеют место нарушения условий применимости: возвратов нет, вероятность выборки зависит от шара (отеля), и еще чего-нибудь. Можно предположить, что количество $m$ известно, но это будет явно неправильное предположение, т.к. в результат поиска попадают находящиеся в некоторой близости отели (нам неизвестной).

Остается сделать ход конем, заявив, что: пренебрежем эффектами, связанные с не возвратами, различностью вероятностей выборки отеля, и т.п. и найденную в такой упрощенной задаче вероятность объявим рейтингом отеля. А потом на проверочной выборке сверим, как это работает. Вот так мы пользуемся ТВ :-)

Поскрипев мозгами, получил похожую формулу правдоподобия (она записана несколько иначе, но тождественна приведенной выше). Отелей, если я правильно помню, где-то 135 тыс. Т.е. задачу нужно решить численно примерно столько же раз, за исключением особых случаев (дополнительно к приведенному выше случаю есть еще «не выбран ни разу», «выбран во всех случаях»)… Это, конечно, не такая большая проблема, однако ж требует времени.

Но, вероятно, этого делать не стоит… А разумно за основу взять формулу, которую вывел –mS— для одинаковых $n_i$ … Если $n_i$ различны, то использовать в формуле вместо $s$ среднее арифметическое $n_i-1$, среднее гармоническое, среднее логарифмическое и или что? Может ли теория, с учетом хода конем, что-нибудь подсказать?

P.S. Если кто-то желает поучаствовать в подобных задачах, есть возможность создания команд на сайте каггле. Основная польза - погружение в мир реальных задач. На сайте есть призы, но на них особо рассчитывать не стоит. Тем более, как на вид заработка. Для выхода на призы нужно тратить много времени, обладать квалификацией, иметь хорошее оборудование, соответствующее программное обеспечение, и т.д.

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

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



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

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


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

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