MATLAB nnmf() - матрица больших терминов для документов - проблема с памятью и скоростью

Question

У меня большая матрица терм-документов, и я хочу использовать неотрицательную матричную функцию факторизации, которую предлагает Matlab. Проблема в том, что после 1-й итерации использование памяти быстро растет и достигает вершины (моя система имеет 6 ГБ), а с другой стороны, уровни использования ЦП становятся очень низкими (около 1%-5%). Вся система ведет себя так, как будто она рухнула, и только если вы будете ждать целую вечность, вторая итерация завершится. (Обратите внимание, что для получения хороших результатов требуется еще много итераций).

Вопрос:

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

Кроме того: я сделал это с меньшей матрицей (около 7000x1800) и не было никаких проблем. Я использую разреженные матрицы, потому что матрица термина-документа имеет много нулевых элементов, и это помогает уменьшить пространство, необходимое для хранения. Например, в моем случае матрица Term-Document имеет 14608 * 18828 = 275039424 элементы и sum(sum(spa~=0)) = 1312582 ненулевые элементы:

>> whos
Name          Size                    Bytes  Class     Attributes

full      14608x18828            2200315392  double              
spa       14608x18828              21151944  double    sparse    

Answer 1

То, что наконец-то сработало:

Я проверил nnmf.m файл (реализация алгоритма предоставлена ​​Matlab) и попытался понять код. Существует одна переменная с именем 'd', которая выполняет следующие действия:d = a - w*h;и представляет собой полную матрицу с теми же размерами, что и "а" (т. е. матрица большого термина-документа):

Name             Size                    Bytes  Class      Attributes
a            14608x18828              21151944  double     sparse    
d            14608x18828            2200315392  double               
...
h                4x18828                602496  double               
h0               4x18828                602496  double               
...
w            14608x4                    467456  double               
w0           14608x4                    467456  double   

Чтобы сэкономить место в памяти, я использовал clear убрать эту матрицу, когда она не нужна. Часть старого nnmf.m файл:

d = a - w*h;
dnorm = sqrt(sum(sum(d.^2))/nm);
dw = max(max(abs(w-w0) / (sqrteps+max(max(abs(w0))))));
dh = max(max(abs(h-h0) / (sqrteps+max(max(abs(h0))))));
delta = max(dw,dh);

был заменен на этот новый:

d = a - w*h;
dnorm = sqrt(sum(sum(d.^2))/nm);
clear d;
dw = max(max(abs(w-w0) / (sqrteps+max(max(abs(w0))))));
dh = max(max(abs(h-h0) / (sqrteps+max(max(abs(h0))))));
delta = max(dw,dh);

clear d был добавлен там, потому что d никогда не использовался после этого. Для используемой матрицы терминов документ работал без проблем с памятью.

Answer 2

Я думаю, что мы все смотрели слишком много эпизодов Star Trek. Наши компьютеры не бесконечно быстрые, с бесконечным объемом памяти. Мы испорчены ожиданием, что мы можем сделать практически любое вычисление, которое мы хотим, с почти немедленными результатами. То, что вы хотите работать с факторизациями огромных матриц, не означает, что вы сможете это сделать. Получите больше памяти для работы с проблемами такого размера. Или работать над меньшими проблемами.

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

>> A = randi([0 1],100, 100);
>> B = sparse(A);
>> whos
  Name        Size             Bytes  Class     Attributes

  A         100x100            80000  double              
  B         100x100            81480  double    sparse    

Обратите внимание, что здесь A равно 50% нулю, но разреженная форма фактически требует больше памяти для хранения, чем полная версия! Помните, что вам нужно хранить не только ненулевые элементы, но и их расположение.

Хорошо, так что редкое хранилище не было таким эффективным. Но, безусловно, вы можете получить с точки зрения эффективности операций? Даже не в этом. Используя функцию времени Стив Эддинс для сравнения, я получаю следующие результаты:

>> timeit(@() A*A)
ans =
   7.3604e-05

>> timeit(@() B*B)
ans =
    0.0014884

Таким образом, разреженное умножение было значительно медленнее, чем полное умножение.

По сути, разреженная матрица с нулевым значением только 50% тратит впустую возможности разреженной формы. Если бы матрица была намного более разреженной, результаты были бы другими.