Применять машинное обучение к гадательной игре?

У меня проблема с игрой, которую я делаю. Я думаю, что я знаю решение (или какое решение применить), но не уверен, как все "штуки подходят друг другу".

Как работает игра:

(from Как подойти к алгоритму угадывания номера (с помощью скручивания)?)

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

Apple = 1
Pears = 2
Oranges  = 3

Затем они получат возможность выбрать любую комбинацию из них, которая им нравится (например, 100 яблок, 20 груш и 1 апельсина). Единственный результат, который получает компьютер, - это общее значение (в этом примере его $143). Компьютер попытается угадать, что у них есть. Очевидно, что он не сможет правильно разобраться в первом повороте.

         Value  quantity(day1)  value(day1)
Apple    1      100             100
Pears    2      20              40
Orange   3      1               3
Total           121             143

В следующий раз пользователь может изменить свои номера, но не более 5% от общего количества (или некоторых других процентов, которые мы можем выбрать. Например, я использую 5%). Цены на фрукты могут меняться (случайным образом), поэтому общая стоимость может измениться и на основе этого (для простоты я не меняю цены на фрукты в этом примере). Используя приведенный выше пример, на второй день игры пользователь возвращает значение $152 и $164 в день 3. Вот пример.

quantity(day2)  %change(day2)   value(day2) quantity(day3)  %change(day3)   value(day3)
104                             104         106                             106
21                              42          23                              46
2                               6           4                               12
127             4.96%           152         133             4.72%           164

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

Я пытаюсь понять, могу ли я определить, что такое количество с течением времени (при условии, что пользователь будет иметь терпение, чтобы продолжать вводить числа). Я знаю, что сейчас мое единственное ограничение - общая сумма не может превышать 5%, поэтому я не могу быть в пределах 5% точности прямо сейчас, чтобы пользователь входил в нее навсегда.

Что я сделал до сих пор:

Я взял все ценности фруктов и общую стоимость корзины фруктов, которые мне дали, и создал большую таблицу всех возможностей. Как только у меня есть список всех возможностей, я использовал теорию графов и создал узлы для каждого возможного решения. Затем я создаю ребра (ссылки) между узлами с каждого дня (например, day1 to day2), если он изменяется в пределах 5%. Затем я удаляю все узлы, у которых нет ребер (ссылки на другие узлы), и по мере того, как пользователь продолжает играть, я также удаляю целые пути, когда путь становится тупиком. Это здорово, потому что это сужает выбор вниз, но теперь я застрял, потому что я хочу еще больше сузить эти варианты. Мне сказали, что это скрытая проблема с маркой, но более сложная версия, потому что состояния меняются (как вы можете видеть выше, новые узлы добавляются каждый ход, а старые/не вероятные удаляются).

**, если это помогает, я получил замечательный ответ (с образцом кода) на реализацию python модели baum-welch (ее используется для обучения данных) здесь: Пример реализации Баум-Вельча **

Что мне нужно сделать (это может быть неправильно):

Теперь, когда я сузил результаты, я стараюсь, чтобы программа пыталась предсказать правильную основу суженной базы результатов. Я думал, что это невозможно, но несколько человек предполагают, что это можно решить с помощью скрытой марковской модели. Я думаю, что я могу запустить несколько итераций по данным (используя модель Baum-Welch), пока вероятности не стабилизируются (и должны улучшаться с большим количеством поворотов от пользователя). Способ, которым скрытые марковские модели могут проверять орфографию или почерк и улучшать, поскольку они делают ошибки (ошибки в этом случае состоят в том, чтобы выбрать корзину, которая была удалена при следующем повороте, как невероятное).

Два вопроса:

Как определить матрицу перехода и излучения, если все состояния вначале равны? Например, поскольку все состояния одинаково вероятны, необходимо что-то использовать для определения вероятности изменения состояний. Я думал использовать граф, который я сделал, чтобы весить узлы с наибольшим числом ребер, как часть расчета состояний перехода/излучения? Это имеет смысл или есть лучший подход?
Как я могу отслеживать все изменения в состояниях? Когда новые корзины добавляются и старые удаляются, возникает проблема отслеживания корзин. Я, хотя скрытая марковская модель иерархического процесса Дирихле (hdp-hmm) была бы тем, что мне нужно, но не совсем точно, как ее применять.

(извините, если я немного расстроен... немного усердно зная, что проблема разрешима, но не может концептуально понять, что нужно сделать).

Как всегда, спасибо за ваше время, и любые советы/предложения были бы весьма признательны.

Ответ 1

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

Интересно, что если вы пройдете кодирование дискретного HMM для своей проблемы, вы получите алгоритм, очень похожий на то, что вы описали в своем решении по теории графов. Большая разница заключается в том, что ваше решение отслеживает, что возможно, тогда как правильный алгоритм вывода, такой как алгоритм Virterbi, будет отслеживать, что вероятно,. Разница очевидна при перекрытии в диапазоне 5% в домене, то есть когда несколько возможных состояний могут потенциально перейти в одно и то же состояние. Ваш алгоритм может добавить 2 ребра к точке, но я сомневаюсь, что когда вы вычислите следующий день, который имеет эффект (он должен считать дважды, по существу).

В любом случае, вы можете использовать Viterbi algortihm, если вас интересует только лучшее предположение в самый последний день, я просто дам вам краткое представление о том, как вы можете просто изменить свое решение теории графов. Вместо сохранения границ между состояниями сохраняется доля, представляющая вероятность того, что состояние является правильным (это распределение иногда называют состоянием убеждений). В каждый новый день распространяйте свое состояние убеждений, увеличивая каждый ведро на вероятность его родительского (вместо добавления края, добавляющего число с плавающей запятой). Вы также должны убедиться, что ваше состояние веры правильно нормализовано (суммируется до 1), поэтому просто разделите его на сумму после каждого обновления. После этого вы можете взвешивать каждое состояние своим наблюдением, но, поскольку у вас нет шумного наблюдения, вы можете просто пойти и установить все невозможные состояния как нулевую вероятность, а затем снова нормализовать. Теперь у вас есть распределение по основным количествам, обусловленным вашими наблюдениями.

Я просматриваю здесь множество статистических данных, чтобы дать вам эту идею.

Изменить (повторно: вопросы): Ответ на ваш вопрос действительно зависит от того, что вы хотите, если вы хотите только распределение за последний день, тогда вы можете уйти с однопроходным алгоритмом, как я описал. Если, однако, вы хотите иметь правильное распределение по количествам в каждый день, вам также придется выполнить обратный проход. Следовательно, метко названный алгоритм forward-backward. Я понимаю, что, поскольку вы хотите вернуться на шаг и удалить края, вы, вероятно, хотите, чтобы распределение на все дни (в отличие от первоначально предполагалось). Конечно, вы заметили, что есть информация, которая может быть использована так, чтобы "будущее могло информировать прошлое", так сказать, и именно по этой причине вам также необходимо выполнить обратный проход, это не очень сложно. для запуска того же самого алгоритма, начинающегося в конце цепочки. Для хорошего обзора ознакомьтесь с учебником Christopher Bishop по 6 предметам на сайте videolectures.net.

Поскольку вы упомянули добавление/удаление границ, позвольте мне просто уточнить алгоритм, который я описал ранее, помните, что это для одного передового прохода. Пусть в общей сложности N возможных перестановок величин, поэтому у вас будет состояние убеждений, которое является длинным разреженным вектором N элементов (называемым v_0). На первом этапе вы получаете наблюдение за суммой, и вы заполняете вектор, устанавливая все возможные значения, чтобы иметь вероятность 1.0, а затем повторно нормализовать. На следующем шаге вы создаете новый разреженный вектор (v_1) всех 0s, перебираете все ненулевые записи в v_0 и увеличиваете (по вероятности в v_0) все записи в v_1, которые находятся в пределах 5%. Затем обнулите все записи в v_1, которые невозможны в соответствии с новым наблюдением, затем повторно нормализуйте v_1 и выбросите v_0. повторите навсегда, v_1 всегда будет правильным распределением возможностей.

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