Марковский процесс дескрипции модели в Java

Question

Я пишу вспомогательный алгоритм обучения на Java.

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

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

Идея довольно проста:

Объекты будут хранить комбинацию переменных, таких как ABDC, ACDE, DE, AE.

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

Процесс принятия решения будет генерировать одну случайную переменную за итерацию. Если сгенерированная переменная является частью одной из комбинаций, например. "А", который является частью ABDC и ACDE, тогда склонность к C и B (или любая следующая буква в сохраненной комбинации) увеличится.

Чтобы сделать вещи немного более понятными, давайте предположим, что "A", "B", "C", "D" и "E", являются единственно возможными переменными. Правда в том, что их будет больше, как 12 или 14, но этот максимум будет также зависеть от того, сколько я смогу обработать без задержки.

Поскольку существует пять возможных переменных, он сгенерирует взвешенный 1/5 случайного броска для первой итерации. Если этот бросок окажется "А", то на следующей итерации "В" и "С" теперь будут иметь склонность 2/5 вместо 1/5.

Если на следующей итерации будет генерироваться "B", склонность "D" увеличится до 3/5. Примечание: отношение является экспоненциальным; На самом деле, это будет не 1/5, а небольшое повышение, например, 10%, что приведет к тому, что он достигнет 50%, если достигнет 4-й переменной в последовательности.

Теперь, в Java, я, вероятно, могу добиться этой функциональности, отслеживая все сохраненные комбинации для каждого объекта. Я думал, что, распределяя процесс отслеживания небольшими шагами по каждой итерации, он не должен быть слишком медленным.

Другим решением будет сопоставление всех возможных комбинаций и их потенциальных склонностей. Это, конечно, просто потребует функцию поиска, но также создает проблемы при вычислении всех возможностей и хранении где-то, возможно, в файле.

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

Как я могу быстро вычислить этот процесс в Java?
,

Пример >>>

Только одна последовательность ABC.

Для трех чисел шансы начинаются равными, поэтому это будет выглядеть примерно так: rand(1,3)

Если A является результатом, мы увеличиваем вероятность B, потому что это следующая буква в последовательности. Допустим, мы удвоили это.

Так что теперь шансы: A=1/4, C=1/4, B=2/4

Функция теперь будет выглядеть как rand(1,4), где результаты 3 и 4 представляют вариант B.

Если следующий результат - B, мы хотим увеличить вероятность C, потому что это следующий символ в последовательности, но вдвое больше, чем он был увеличен в прошлый раз (экспоненциально).

Скорее всего, что-то вроде: A=1/6, C=1/6, B=4/6

Функция теперь является rand(1/6), где значения 3, 4, 5, 6 представляют C.

Answer 1

Вы можете написать версию C/C++, если хотите, и использовать NDK (накладные расходы NDK связаны с переводами JNI из Java в методы C/C++, но, оказавшись там, они намного быстрее)

Это одна идея. Но... я не думаю, что вам нужно заходить так далеко (по крайней мере, чтобы получить версию, которая работает для небольших наборов) (возможно, позже переход на NDK может быть лучшим вариантом для БОЛЬШИХ наборов)

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

 int[][] probs = new int[100][2];

Таким образом, вы можете думать об этом как...

1 2 1 1

4 3 4 9

как 1/4, 2/3, 1/4, 1/9 со всей целочисленной арифметикой. Это было бы проще в "некоторых" частях алгоритма, потому что вы сможете создавать хорошие вспомогательные функции для "removeColumn" (сделать 0/0, пропустить остаток обработки и т. Д. (Или как вы хотите это представить)) и 'AdjustProbabilities ()'

(вы могли бы обойтись без единого массива числителей, если сделать знаменатели единым целым (наименьшим общим знаменателем), но я бы, вероятно, сделал это оптимизацией после того, как работала версия 2D-массива)

Затем просто напишите "простые" обобщенные методы P, R и V, которые взаимодействуют с этими данными для каждого узла. Затем сделайте их регулируемыми / расширяемыми / с хорошим дизайном OO.

Затем просто "поиграйте с цифрами" для коэффициента дисконтирования и т. Д.

Я думаю, что это скорее просто "просто потратьте время, чтобы проверить это", чем вопрос о каких-либо действительно сложных математических алгоритмах и т. Д., Потому что из того, что я вижу, нет "очевидных" мест для оптимизации основных алгоритмов.