Эффективное построение косинусной матрицы подобия из корпуса в Chapel

У меня есть корпус V векторов TF / IDF, поэтому они довольно редкие.
Это массив размером примерно 2500 на 150 000.
Я хочу вычислить косинусное сходство между каждым документом в корпусе.

Это почти самый наивный способ, который я могу придумать. Я уже знаю три или четыре оптимизации, но не хочу предполагать ответ. Я хотел бы знать наиболее эффективный с точки зрения вычислений способ использования Chapel в этом расчете. Цель состоит в том, чтобы получить X как симметричную матрицу с diag(X) = 0

use Norm,
    LinearAlgebra;

var ndocs = 2500,
    nftrs = 150000,
    docs = 1..ndocs,
    ftrs = 1..nftrs,
    V: [docs, ftrs] real,
    X: [docs, docs] real;

for i in docs {
  var n1 = norm(V[i,..]);
  for j in (i+1)..ndocs {
    var n2 = norm(V[j,..]);
    var c = dot(V[i,..], V[j,..]) / (n1*n2);
    X[i,j] = c;
    X[j,i] = c;
  }
}

Скомпилировано с использованием

chpl -I/usr/local/Cellar/openblas/0.2.20/include -L/usr/local/Cellar/openblas/0.2.20/lib -lblas cosim.chpl

== ОБНОВЛЕНО ==

Это могло бы действительно скомпилировать и запустить. В исходном коде были ошибки, как это было предложено @bradcray ниже


sparse-matrix cosine-similarity chapel
person Brian Dolan    schedule 05.09.2017    source источник
comment
Учитывая математическую задачу (максимизация функции), что такое критериальная функция и что такое метрика? Отсутствует явное заявление об этом. Какова количественная мера (cit.) наиболее эффективного с вычислительной точки зрения способа (для использования Chapel в этом вычислении)? Спасибо, Брайан, за то, что он добавил такое ясное и надежное заявление, которое позволяет таким усилиям по оптимизации не идти против движущихся песков.   -  person user3666197    schedule 05.09.2017
comment
@ brian-dolan: В приведенном выше коде есть ряд ошибок, которые я пытался отредактировать, но он был отклонен, сказав, что вместо этого мне нужно сообщить вам об изменениях. Проблема заключается в том, что ndocs и nftrs объявляются как домены, но затем используются для объявления массива (где требуются диапазоны) и как привязка во внутреннем цикле for (где требуется целое число). Вот предлагаемое мной исправление: используйте Norm, LinearAlgebra; var ndocs = 2500, nftrs = 150000, docs = 1..ndocs, ftrs = 1..nftrs, V: [docs, ftrs] real, X: [docs, docs] real; for i in docs {   -  person Brad    schedule 15.12.2017
comment
@Brad Пожалуйста, не чувствуй себя отвергнутым! Хорошо, я посмотрю и, возможно, попрошу помощи. Ах, как давно я ничего не знал о программировании ...   -  person Brian Dolan    schedule 15.12.2017

Ответы (2)


arrow_upward
1
arrow_downward

Вот некоторые улучшения, которые можно внести в исходную реализацию:

  • Выполните предварительное вычисление и кэшируйте dot(V[i, ..], V[i, ..]) для всех i в массив, чтобы уменьшить повторяющиеся вычисления.
  • Use 1..V.size or V.domain instead of 1..V.shape[1]
    • V.shape is computed from the domain sizes, rather than stored as a field.
  • Воспользуйтесь досадно параллельной природой этой программы, вычислив X параллельно

Дополнительные сведения см. В выпуске GitHub, в котором исследуются эти изменения и их влияние на время.

person ben-albrecht    schedule 26.11.2017

arrow_upward
1
arrow_downward

[Мета: Этот вопрос давил на меня из-за того, что так долго оставался без ответа. Я лично уклонялся от этого из-за использования фразы «самый эффективный с точки зрения вычислений». На практике трудно гарантировать, что какое-либо решение соответствует этому описанию с учетом вариаций, которые могут происходить от одной целевой машины или набора данных к другой. Но поскольку никто больше не выступил, я сделаю несколько комментариев в надежде, что они могут быть полезны.]

Несколько вещей, которые выделяются для меня в вашем коде:

1) Если я чего-то не упускаю, вы будете многократно, очень много раз за время вычисления вычислять norm(V[r, ..]) избыточно. Асимптотически это говорит о том, что вы выполняете квадратичную работу там, где требуется только линейная работа. Я бы предложил вычислить норму для каждой строки один раз и сохранить ее в массиве, чтобы избежать этого избыточного вычисления:

var normVrow: [docs] real = [r in docs] norm(V[r,..]);

Затем во внутреннем цикле вы можете просто обратиться к normVrow[i] или normVrow[j].

2) Поскольку это Chapel, и ваш цикл, похоже, не имеет взаимозависимостей между циклами, вместо использования последовательных for циклов, вам, вероятно, следует использовать параллельный forall цикл для этого вычисления. Возникает вопрос:

(а) измените внешний цикл на forall (что приведет к дисбалансу нагрузки, поскольку общее пространство итераций имеет треугольную форму),

(b) изменить оба цикла на forall циклов (что помогло бы решить проблему дисбаланса нагрузки за счет чрезмерной декомпозиции, но, вероятно, также увеличило бы накладные расходы), или

(c) превратить внешний цикл в динамически планируемый цикл для устранения дисбаланса нагрузки.

Моим инстинктом было бы выбрать вариант c, используя dynamic итератор:

use DynamicIters;

forall i in dynamic(ndocs) {
  ...
}

3) И последнее, что следует учитывать, - это избегать треугольного пространства итераций и просто избыточно вычислять X[i,j] и X[j,i], даже если они будут иметь одинаковое значение. Это может не иметь смысла при запуске с разделяемой памятью, но если вы выполняете вычисления в распределенном массиве X, вы, вероятно, сократите обмен данными, поскольку эти значения матрицы будут храниться на разных процессорах. При таком подходе вы можете выполнять итерацию с одним forall циклом по X.domain, и результат будет хорошо сбалансирован по нагрузке по умолчанию без необходимости в динамическом итераторе.

person Brad    schedule 09.12.2017
comment
К сожалению, у меня была кешированная копия этого вопроса в моем браузере, и я не заметил, что @bencray уже ответил на него несколько недель назад. Виноват. - person Brad; 09.12.2017