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

Question

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

Answer 1

Преамбула:

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

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

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 разработал решение для вычисления собственного значения без сохранения копии матрицы на все подчиненные компьютерах. -Or- Они использовали что-то вроде Monte Carlo или некоторые другие Approximation Algorithm, чтобы разработать «достаточно близкий» расчет.

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

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

постамбула:

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

Answer 2

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

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

Answer 3

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

Answer 4

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

Если NxM матрица А описывает вес линии связи (количество потока) от узла п к узлу м, то

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

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

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

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

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

Answer 5

Апача hama проекта имеет интересную реализацию алгоритма собственного значения Якоби. Он работает на хаопе. Обратите внимание, что вращение происходит при сканировании матрицы, а не в уменьшении карты.