0

Есть матрица 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))

Пример

5
  • если нельзя использовать машинное обучение, зачем вы поставили метку машинное обучение ?
    – n1tr0xs
    8 авг 2022 в 10:54
  • @n1tr0xs, исправил
    – ands
    8 авг 2022 в 11:06
  • 1
    UnboundLocalError: local variable 'b' referenced before assignment
    – CrazyElf
    8 авг 2022 в 11:14
  • @CrazyElf, спасибо за отклик. Добавил скрин с формой ввода/вывода
    – ands
    8 авг 2022 в 11:26
  • Исправьте beta = a.T + 1 на b = a.T + 1
    – CrazyElf
    8 авг 2022 в 12:02

2 ответа 2

2

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

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

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

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

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

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

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

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

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

7
  • за идею спасибо. Но не совсем понимаю, как смогу получить на выходе вещественные числа. Опишу логику, как я понял. Берем минор 4х4( пусть 1-ый вариант это будут все нули), прогоняем через функцию, сравниваем с минором 2х2 в моей матрице X. И так по всем возможным комбинациям .Правильно ли понимаю, что там где, что-то не будет сходится, я уже или усредняю или придумываю что-то, отсюда и берутся вещественные числа. Вот только не много я в шоке. Для матрицы 2х2 -это 16 вариантов. Плюс прогонять по всей матрице 20х20. А еще в выборке 50к матриц)
    – ands
    8 авг 2022 в 12:57
  • 1
    @Astraz Числа берутся из преобразование bool->int->float. Вообще-то предложенный алгоритм предполагает что мы хотим найти единственное и точное решение (т.е абсолютный минимум в любой разумной метреке). И да, он жутко не производительный. Про 50к матриц в исходной постановке задачи ничего небыло.
    – Chorkov
    8 авг 2022 в 13:19
  • Можно чуть по подробнее про bool->int->float. Все же остается не ясно для меня, появление вещественного числа. Сенк
    – ands
    8 авг 2022 в 13:38
  • @Astraz функция step, конечно, возвращает матрицу из bool-ов. Но во всех математических операциях с bool, (сложение, умножение) он преобразуеся в число True->1, False->0.
    – Chorkov
    8 авг 2022 в 13:59
  • это я понимаю, просто подумал не о том, спасибо. Я просто не понимаю, даже идя по тому алгоритму, что вы предложили, на каком этапе у меня сгенерируется допустим в матрице Y' [0][1] допустим 0.754... Ведь функция step будет генерировать на выходе (return) bool и и матрицу, которую я ей падам Y'. Так как в этой Y' появится вещественное число. Плюс по алгоритму с минором мы всегда сопоставляем бинарные числа против бинарных. Сенк
    – ands
    8 авг 2022 в 14:07
1

Если что я тут код написал с "генетическим" перебором - делаем случайную матрицу и понемногу её мутируем в ожидании лучшего результата. И так много раз. Результат не очень и код грязноват, ошибка к нулю не сходится, но может пользуясь знанием из ответа 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 считаю.

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.