Эффективно вычислять поэлементное произведение для каждого столбца в массиве

avatar
Alex Pharaon
8 августа 2021 в 18:21
62
0
0

У меня есть разреженный массив numpy, содержащий около 60 000 строк и 10 000 столбцов. Каждый элемент в массиве равен либо 0, либо 1. Каждый столбец необходимо поэлементно умножить на четыре других столбца из матрицы, и я хочу вычислить все 10 000 ^ 5 комбинаций столбцов для умножения. После этого шага последовательные единицы в столбце удаляются, так что за единицей может следовать только ноль. Затем я умножаю эту матрицу на вектор и сохраняю результат (хотя код для этого не показан ниже).

Сначала я попытался использовать numpy с циклами for, но время выполнения было слишком медленным, поэтому я попытался использовать cupy. Это все еще очень медленно. Метод, который я пробовал, заключается в смещении массивов для вычисления всех возможных комбинаций. Есть 5 циклов for, так как я хочу выполнить поэлементное умножение на 5 массивов. Мне нужны все возможные комбинации этого из 10 000 столбцов. Проблема в том, что мне нужно найти более быстрый метод и буду признателен за любую помощь! Ниже приведен код, который я пробовал до сих пор.

for a in range(1,global_signals.shape[1]):
  arr_1 = cp.empty(shape=(global_signals.shape))

  arr_1[:,a:] = global_signals[:,:-a]
  arr_1[:,:a] = global_signals[:,-a:]

  for b in range(1,global_signals.shape[1]):
    arr_2 = cp.empty(shape=(global_signals.shape))

    arr_2[:,b:] = global_signals[:,:-b]
    arr_2[:,:b] = global_signals[:,-b:]

    for c in range(1,global_signals.shape[1]):
      arr_3 = cp.empty(shape=(global_signals.shape))

      arr_3[:,c:] = global_signals[:,:-c]
      arr_3[:,:c] = global_signals[:,-c:]

      for d in range(1,global_signals.shape[1]):
        arr_4 = cp.empty(shape=(global_signals.shape))

        arr_4[:,d:] = global_signals[:,:-d]
        arr_4[:,:d] = global_signals[:,-d:]

        for e in range(1,global_signals.shape[1]):
          arr_5 = cp.empty(shape=(global_signals.shape))

          arr_5[:,e:] = global_signals[:,:-e]
          arr_5[:,:e] = global_signals[:,-e:]

          mul_1 = cp.multiply(arr_1,arr_2,arr_3)
          mul_2 = cp.multiply(arr_4,arr_5)
          mul_result = cp.multiply(mul_1,mul_2)

          shifted = cp.append(cp.zeros((1,mul_result.shape[1]),dtype='float32'), mul_result[:-1], axis=0)
          final_signals = cp.where((shifted == 0) & (mul_result == 1), 1, 0)

Недавно я услышал об альтернативных представлениях разреженных матриц. Я был бы признателен за помощь в том, как лучше всего использовать это, в сочетании с тем, как лучше всего оптимизировать мой приведенный выше код, чтобы ускорить вычисления. Пожалуйста, дайте мне знать, если что-то неясно и нуждается в разъяснении :)

Источник
user_na
8 августа 2021 в 18:28
0

Я, наверное, что-то упускаю. Но если я вас правильно понял, у вас есть 4 столбца, в которых есть 0 или 1. При этом здесь всего 16 различных комбинаций. Ваш массив будет иметь более или менее только дубликаты. Разве вы не можете просто сделать вложенный where, чтобы покрыть все 16 возможных комбинаций 0/1?

Alex Pharaon
8 августа 2021 в 19:21
0

У меня 10 000 столбцов. Я хочу выбрать 5 оптимальных столбцов таким образом, чтобы при их умножении поэлементно удалять последовательные, а затем умножать на конечный вектор, чтобы получить наивысший балл. Для этого я вычисляю все возможные комбинации выбора 5 столбцов из моей матрицы/массива из 10 000 столбцов. Таким образом, нужно вычислить 10 000^5 различных комбинаций.

Jérôme Richard
8 августа 2021 в 22:31
0

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

Alex Pharaon
8 августа 2021 в 22:36
0

Ха-ха-ха, спасибо @JérômeRichard, да, я понял. Сначала я попытался найти алгоритм и думаю, что это проблема дискретной оптимизации, поскольку я хочу выбрать 5 лучших столбцов из матрицы (т.е. 5 векторов-столбцов), которые после выполнения всех вышеупомянутых вычислений дают наивысший «счет», когда скалярный продукт вычисляется с другим вектором. Вы случайно не знаете какой-нибудь алгоритм, который я мог бы использовать?

Jérôme Richard
8 августа 2021 в 23:31
0

Я не очень разбираюсь в математической оптимизации, но есть некоторая библиотека, реализующая решатели CSP (задачи удовлетворения ограничений). Инструменты Google OR — одни из самых известных для этого. Scipy, а также некоторые базовые математические алгоритмы оптимизации (например, LBFGS, Netwton, SGD). Есть хороший шанс, что один из подходов даст неплохие результаты, но, вероятно, не оптимальные.

Alex Pharaon
9 августа 2021 в 12:21
0

Найденное решение не обязательно должно быть оптимальным - я был бы рад хорошему :). Я немного новичок в этой области ... У вас есть какие-либо советы @JérômeRichard, какой из них использовать или как вообще реализовать что-то подобное, поскольку это мой первый раз. Ваш совет будет очень ценен!

Jérôme Richard
9 августа 2021 в 18:58
0

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

Alex Pharaon
9 августа 2021 в 20:31
0

Хорошо, спасибо @JérômeRichard :)

Ответы (0)