Как реализовать вычисление собственных значений с MapReduce / Hadoop?

Question

Это возможно, потому что PageRank был формой собственного значения, и именно поэтому появился MapReduce. Но в реальной реализации возникают проблемы, например, что каждый подчиненный компьютер должен хранить копию матрицы?

Answer 1

PageRank решает проблему доминирующего собственного вектора, итеративно находя стационарное состояние дискретного потока в сети.

Если матрица A NxM описывает вес канала (объем потока) от узла n к узлу m, то

p_{n+1} = A . p_{n} 

В пределе, когда p сходится к стационарному состоянию (p_n + 1 = p_n), это проблема собственных векторов с собственным значением 1.

Алгоритм PageRank не требует, чтобы матрица хранилась в памяти, но он неэффективен на плотных (не разреженных) матрицах. Для плотных матриц MapReduce является неправильным решением - вам нужна локальность и широкий обмен между узлами - и вам следует вместо этого взглянуть на LaPACK, MPI и друзей.

Работающую реализацию PageRank можно увидеть в библиотеке wukong (потоковая передача hadoop для ruby) или в подмодуле Heretrix pagerank . (Код Heretrix выполняется независимо от Heretrix)

(отказ от ответственности: я автор вуконга.)

Answer 2

Преамбула :

При правильной изоляции данных можно достичь результатов параллельных вычислений без полного набора данных на каждой машине.

Возьмем, к примеру, следующий цикл:

for (int i = 0; i < m[].length; i++)
{
    for (int j = 0; j < m[i].length; j++)
    {
        m[i][j]++; 
    }
}

И дана матрица следующего расположения:

       j=0   j=1   j=2
 i=0  [   ] [   ] [   ]
 i=1  [   ] [   ] [   ]
 i=2  [   ] [   ] [   ]

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

for (int i = 0; i < m[].length; i++)
{
    for (int j = 0; j < m[i].length; j++)
    {
        //For obvious reasons, matrix index verification code removed
        m[i][j] = m[i/2][j] + m[i][j+7]; 
    }
}

Очевидно, что цикл, подобный приведенному выше, становится чрезвычайно проблематичным (обратите внимание на матричные индексаторы.) Но существуют методы для развертывания циклов такого типа и создания эффективных параллельных алгоритмов.

ОТВЕТ

Возможно, Google разработал решение для вычисления собственного значения без сохранения копии матрицы на всех подчиненных компьютерах. -Или- Они использовали что-то вроде Монте-Карло или какой-то другой Алгоритм аппроксимации для разработки "достаточно близкого" вычисления.

На самом деле, я бы сказал, что Google сделает все возможное, чтобы любые вычисления, необходимые для их алгоритма PageRank, были максимально эффективными. Когда вы работаете с такими машинами, как , и , (обратите внимание на кабель Ethernet), вы не можете передавать большие наборы данных (100 гигабайт), поскольку это невозможно из-за ограничений оборудования. товарных карт NIC.

С учетом вышесказанного Google умеет удивлять сообщество программистов, и их реализация может быть совершенно иной.

постамбула

Некоторые хорошие ресурсы для параллельных вычислений включают OpenMP и MPI . Обе параллельные реализации подходят для параллельных вычислений с очень разными парадигмами, некоторые из которых проистекают из машинной реализации (кластер или распределенные вычисления).

Answer 3

Проект apache hama имеет интересную реализацию алгоритма собственных значений Якоби. Это работает на hadoop. Обратите внимание, что поворот происходит при сканировании матрицы, а не на карте уменьшить.

Answer 4

Теперь я могу ответить сам. Алгоритм PageRank использует разреженную матрицу, где он должен сходиться по собственному значению с несколькими умножениями. Таким образом, в практике PageRank процедура Map / Reduce является действительной. Вы можете выполнить умножение матриц в процедуре Map и сформировать разреженную матрицу в процедуре Reduce. Но для общего нахождения собственных значений матрицы это все еще непростая задача.

Answer 5

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

PageRank использует очень разреженную матрицу специальной формы, и любые выводы из вычисления его собственных значений почти наверняка не распространяются на общие матрицы. (редактировать: вот другая ссылка , которая выглядит интересной)