Восстановить матрицу

Question

Есть матрица Y 20х20. Она бинарная. К ней применяют функцию "step" и получается другая бинарная матрица X 20х20.

Задача: Мы знаем только матрицу Х. Мы знаем функцию, по которой получили матрицу Х. Нам надо предсказать Y' как можно лучше. Метрика MSE. Известно: что Y' будет состоять из вещественных чисел от 0 до 1.

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

def step(X):
    n = X.shape[0]
    W = convolve2d(X, np.ones((3, 3)), mode='same', boundary='wrap') - X
    a = np.tile(np.floor(np.arange(n) / (n / 3)) + 1, (n, 1))
    b =  a.T + 1
    a, b = np.minimum(a, b), np.maximum(a, b)
    gamma = (a + b) / 2
    return ((W <= b)&(W >= gamma)) | (X & (W >= a)& (W <= gamma))

Answer 1

Обратите внимание, что a, b, gamma -константы. W - перемешивает информацию только из 9 соседних ячеек исходной матрицы.

алгоритм (1): перебор локальных подмножеств

Берем миноры размера 4x4 в исходной матрице, перебираем все комбинации из 16 бит. Смотрим какие комбинации приводят к правильному минору 2x2 в результирующией матрице (который зависит только от изменяемых нами бит). Если во всех "правильных" комбинациях какой-то бит всегда в одном и том же значении, значит значение этого бита в исходной матрице мы становили точно. При подборе следующих квадратов 4x4, биты значения которых установленны - уже не трогаем.

Можно попробовать с квадратами 3x3 или 5x5. Но 3x3 - можно не найти решение, а 5x5 - больше трудозатраты.

Идеологически, алгоритм напоминает бота для игры в сапера. Теоретически, алгоритм должен найти точное значение матрицы Y, если это вообще возможно. И, да, он чрезвычайно трудозатратен.

способ (2): Метод Монте-Карло (или роевой метод поиска минимума)

Запоминаем матрицу вероятностей P. (Физически это вероятность, что в исходной матрице на заданном месте стоит 1.). Первоначально, матрица заполнена 0.5.

Генерируем случайную матрицу Yi, в соответствии с вероятностями P.
Xi = step(Yi)
Если Xi - лучше чем предудущая лучшая матрица - то запоминаем ее.
Сравниваем ячейки Xi и X. Растягиваем информацию для об успехе / не успехе на соседние ячейки (от которых завист успех в этой ячейке). Wins=convolve2d( ( Xi==X )*2. -1., np.ones((3, 3)), mode='same', boundary='wrap')
Поправляем вероятность P: увеличиваем вероятность тех битиков, которые привели к успеху и наоборот. P+=Wins*Xi*0.01
Поправляем P, так чтобы значения оставались в интервале [0., 1.]

Повторяем п.1-6 достаточное число раз.

Answer 2

Если что я тут код написал с "генетическим" перебором - делаем случайную матрицу и понемногу её мутируем в ожидании лучшего результата. И так много раз. Результат не очень и код грязноват, ошибка к нулю не сходится, но может пользуясь знанием из ответа Chorkov кто-то более правильную мутацию сделает. Мне просто некогда сейчас.

Код инициализации:

import numpy as np
from scipy.signal import convolve2d

def step(X):
    n = X.shape[0]
    W = convolve2d(X, np.ones((3, 3)), mode='same', boundary='wrap') - X
    a = np.tile(np.floor(np.arange(n) / (n / 3)) + 1, (n, 1))
    b =  a.T + 1
    a, b = np.minimum(a, b), np.maximum(a, b)
    gamma = (a + b) / 2
    return (((W <= b)&(W >= gamma)) | (X.astype(bool) & (W >= a)& (W <= gamma))).astype(int)

n = 20
Y = np.random.randint(0, 2, (n, n))
X = step(Y)

Код с выбором лучших мутаций:

from tqdm.auto import tqdm

YY = None
MSE_ = n*n
r = tqdm(range(100))
for z in r:
    Y1 = np.random.randint(0, 2, (n, n))
    MSE = n*n
    t = tqdm(range(10_000), leave=False)
    for i in t:
        Y2 = Y1.copy()
        for j in range(np.random.randint(1, n+1)):
            x, y = np.random.randint(0, n, 2)
            Y2[x,y] = 1 - Y2[x, y]
        X2 = step(Y2)
        MSE1 = ((X2-X)**2).sum()/n/n
        if MSE1 < MSE:
            MSE = MSE1
            Y1 = Y2
            t.set_description(f'{MSE:.2f}')
    if MSE < MSE_:
        MSE_ = MSE
        YY = Y1
        r.set_description(f'{MSE_:.2f}')

Лучше чем 0.11 так не получилось, если я вообще правильно MSE считаю.

БЛОГ НА HUSL

Восстановить матрицу

Ответы (2 шт):