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

У меня есть большая матрица терминов-документов, и я хочу использовать неотрицательную матричную факторизацию, которую предлагает 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

matlab sparse-matrix nmf term-document-matrix
person tgogos    schedule 21.08.2012    source источник
comment
Я бы посоветовал называть переменную full ужасно плохой идеей, особенно когда вы работаете с разреженными матрицами, поскольку существует функция с именем full.m. Вы напрашиваетесь здесь на неприятности.   -  person    schedule 21.08.2012
comment
Вы правы, я не использую полную матрицу. Я просто дал это как информацию, чтобы показать вам разреженность моей матрицы.   -  person tgogos    schedule 21.08.2012

Ответы (2)


arrow_upward
1
arrow_downward

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

Матрицы, которые вы описываете, даже не очень разрежены, и их факторизация будет практически полностью полной. Разреженные матрицы редко представляют ценность, если количество ненулевых значений составляет небольшую долю от общего числа. Разреженная матрица, которая имеет только 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 Стива Эддинса для сравнения, я получаю следующие результаты:

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

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

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

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

person Community    schedule 21.08.2012
comment
Спасибо, что сделали разреженные матрицы более понятными для меня. Моя матрица имеет 14608 * 18828 = 275039424 элементов и сумму (сумма (spa ~ = 0)) = 1312582 ненулевых элемента, поэтому 1312582/275039424 = 0,0048, и я думаю, что хорошо справляюсь, используя разреженные матрицы. Сейчас я пытаюсь выяснить, что происходит внутри функции nnmf(), и если эта матрица когда-нибудь заполнится... - person tgogos; 21.08.2012

arrow_upward
1
arrow_downward

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

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

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 после этого никогда не использовался. Для используемой матрицы терминов-документов это работало, не вызывая проблем с памятью.

person tgogos    schedule 22.08.2012