Представление 2D-карты двойников с минимальным количеством «параметров»

Question

Я работаю над пошаговым ИИ, используя технику нейронной сети, известную как NEAT . Я пытаюсь обучить сеть, которая может перемещаться по двумерному пространству (координаты X и Y), учитывая множество значений, которые хранятся в том, что фактически является двумерным массивом.

Я вижу две стратегии использования нейронной сети:

1. Для каждой «ячейки» в сетке укажите оценки от различных эвристик в качестве входных данных для нейронов и создайте NN, который по сути является очень сложной системой «подсчета». Переместите неигрового персонажа (NPC) в место с наибольшим количеством очков.

2. Создайте сжатое значение для каждой эвристической меры (каким-то образом сжатое до минимально возможного количества бит) и предоставьте входной нейрон для каждой из этих мер.

Мне очень интересен второй вариант, потому что он представляет наименьшее количество необходимых вычислений (время выполнения игры довольно продолжительное), однако я не совсем понимаю, какой подход я мог бы использовать для создания версии «малого представления» двумерные значения heiuristic. Я знаю, что есть такие методы, как преобразования Фурье, но я не знаю, подойдут ли они моей проблеме. В основном я ищу способ преобразования массива двойных чисел 50x50 в одно или, может быть, два двойных значения. Эти два двойных значения могут быть сжаты с потерями, мне не нужно иметь возможность вернуть исходные значения, мне просто нужен разумный механизм для изменения входных данных в небольшую площадь.

Альтернатива этим двум возможностям заключается в том, чтобы каким-то образом кодировать «регион» на основе некоторого расстояния от NPC (таким образом, вы получаете фактические значения для «близкой» ячейки и приближение для «далекой» ячейки). Я не знаю точно, как бы я подключил это, но это по крайней мере избавляет от необходимости оценивать каждую клетку каждый ход игры (учитывая, что я смотрю около 5 миллионов раундов со скоростью примерно 1 секунда за раунд, любое упрощение Я могу придумать, очень помог бы).

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

Thankyou

Айдан

ИЗМЕНЕНО ДЛЯ ДОБАВЛЕНИЯ (и изменения названия):

Благодаря Крису мы усовершенствовали то, что я ищу. То, что я ищу, - это способ приблизить линию (я могу преобразовать 2D карту в линию) по как можно меньшему количеству параметров. Я использовал кубические сплайны для интерполяции и раньше, однако мне нужно что-то гораздо более выполнимое для набора данных, который довольно агрессивно варьируется между 0,0 и 1,0. То, что я действительно ищу, я полагаю, это "хэш" карты.

Я знаю, что есть такие методы, как кубические сплайны, из которых я могу выработать некоторые "ключевые точки", и эти значения являются разумной аналогией для того, что я ищу. Мне нужен способ взять 2500 значений и придумать небольшое представление этих значений, которые я могу использовать для нейронной сети. Я думаю, что NN можно научить выводить истинный смысл этих представлений или, по крайней мере, определить некоторую корреляцию между представлением и реальным миром, так что это не обязательно должна быть обратимой функцией, но я не думаю, что многие односторонние функции (такие как MD5, SHA) на самом деле тоже будут очень полезны ...

Answer 1

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

Отредактировано, чтобы добавить:

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

Отредактировано снова, чтобы добавить:

Судя по вашим комментариям, вам может показаться, что вам нужна кривая заполнения пространства . Используйте кривую, чтобы превратить ваш массив 50x50 * в строку 1x2500, а затем придумайте формулу, которая приближает значения, которые вы хотите получить для каждой ячейки массива.

* Должен ли массив быть 50х50? Может быть намного легче заполнить кривой заполнения пространства, если это квадрат немного разных размеров. Например, кривая Гильберта хорошо работает для измерений, имеющих степени двойки.

Answer 2

Одна вещь, которую вы можете попробовать, это взять БПФ вашей 1D линии и затем удалить более поздние (высокочастотные) термины. Например, в MATLAB я сделал следующее:

x = [1:1000];
y = rand(1,1000);
f = fft(y, 250); % truncate to 250 terms
plot(x,y, x,abs(ifft(f), 1000));

То, что, как правило, происходило, было то, что пики iFFT f были очень близки к пикам y. Они не обязательно были самыми высокими точками у, но они были пиками. Например, в этом цикле были пики в x = 424, 475 и 725 в инвертированном БПФ f, а также были пики в y в x = 423, 475 и 726. Однако глобальный максимум y был в x = 503, что было максимумом ifft (f), но не очень высоким.

Тем не менее, это только на самом деле сокращает использование данных в два раза, потому что я преобразовал 1000 double в 250 комплексных значений. Дальнейшее увеличение может быть получено только при использовании реальной части БПФ:

x = [1:1000];
y = rand(1,1000);
f = real(fft(y, 250)); % only uses 1/4 the space now
plot(x,y, x,abs(ifft(f, 1000)));

Это все еще дало довольно хорошие результаты: каждый главный пик ifft (f) соответствовал пику в y, который большую часть времени находился на расстоянии не более 2, и вы используете 1/4 пространства хранения двойной прямо.

Однако это все равно не даст вам результатов «одного или двух двойных значений». Теперь вы упаковываете 2500 двойных в 625. Вы можете экспериментировать, сокращая больше терминов, но вам придется проверять больше значений «близко», сокращая больше терминов. Может быть, вы можете сохранить первые 10% терминов и найти максимум, а затем посмотреть на расстояние 3 или 4; это уменьшит ваши 2500 удвоений до «простого» 250. Только тестирование определит, что лучше всего подходит для вашего приложения.

Если вы действительно в отчаянии, вы можете перейти на самые низкие 1% частоты и искать 5 или 6 в любом направлении для получения истинного пика. Но это все равно оставляет вам 25 двойных.

Я не думаю, что есть какой-либо способ преобразовать 2500 двойных в только 1 или 2, и сделать его обратимым во что-либо значимое. Взгляните на тексты теории информации, чтобы понять почему. Я предлагаю вам взять MATLAB, GNU Octave или даже Excel, поиграть с чем-то вроде этого и найти, какие результаты лучше для вас.