Как реализовать вычисления собственных значений с MapReduce/Hadoop?
Это возможно, потому что PageRank был формой собственного значения, и именно поэтому MapReduce представил. Но, кажется, проблемы в реальной реализации, такие как каждый ведомый компьютер должен поддерживать копию матрицы?
5 ответов
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) или в подмодуле Heranrix pagerank. (Код Heretrix выполняется независимо от Heretrix)
(отказ от ответственности: я автор вуконга.)
ПРЕАМБУЛА:
При правильном связывании данных можно достичь результатов параллельных вычислений без полного набора данных на каждой машине.
Возьмем для примера следующий цикл:
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. Обе параллельные реализации подходят к параллельным вычислениям с очень разных парадигм, некоторые из которых проистекают из машинной реализации (кластер или распределенные вычисления).
Я подозреваю, что это трудно поддается большинству матриц, за исключением тех, которые имеют специальные структуры (например, разреженные матрицы или те, которые имеют определенные блочные структуры). Слишком сильная связь между матричными коэффициентами и собственными значениями.
PageRank использует очень разреженную матрицу особой формы, и любые выводы из вычисления ее собственных значений почти наверняка не распространяются на общие матрицы. (редактировать: вот еще одна ссылка, которая выглядит интересно)
У проекта apache hama есть интересная реализация алгоритма собственных значений Якоби. Это работает на hadoop. Обратите внимание, что поворот происходит при сканировании матрицы, а не на карте уменьшения.
Я могу ответить себе сейчас. Алгоритм PageRank использует разреженную матрицу, где он должен сходиться по собственному значению с несколькими умножениями. Таким образом, в практике PageRank процедура Map/Reduce является действительной. Вы можете выполнить умножение матриц в процедуре Map и сформировать разреженную матрицу в процедуре Reduce. Но для общего нахождения собственных значений матрицы это все еще непростая задача.