Распараллеливание разложения Холецкого для использования в обучении алгоритму машинного обучения

Question

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

Допустим, у нас есть блочная матрица (ковариационная матрица, но это не относится к проблеме)

M = A  B  
    B* C

, где A и C относятся ктренировочные данные из двух разных наборов.И A, и B положительно определены.Также для простоты предположим, что A и C имеют размер nxn.

. Существует формула для проведения блока разложения Холецкого.См. http://en.wikipedia.org/wiki/Block_LU_decomposition. Подводя итог, мы получили следующий результат.

M = LU

где (* указывает на транспонирование)

L = A^{1/2}      0 
    B*A^{-*/2}  Q^{1/2}

где

Q = C - B*A^{-1}B

Теперь давайтескажем, обучение, связанное с матрицами A и C, уже было проведено, поэтому мы выполнили разложение Холецкого для A, а C дало A ^ {1/2} и C ^ {1/2} (поэтомувычислите обратные значения A ^ {- 1/2} и C ^ {- 1/2}, используя прямое замещение).

Переписывая Q в терминах этих величин, которые мы теперь имеем.

Q = Q^{1/2} Q^{*/2} = C^{1/2} C^{*/2} - B* A^{-*/2}A^{-1/2} B

У меня такой вопрос: с помощью этой установки возможно алгебраическое вычисление Q ^ {1/2} без необходимости применять разложение Холецкого к Q. Или, другими словами, я могу использовать C ^ {1/2}, чтобы помочьменя в расчете Q ^ {1/2}.Если бы это было возможно, тогда было бы возможно легко распараллелить обучение.

Заранее спасибо за любые ответы.Извините за матричный набор.Есть ли какой-нибудь разумный способ набирать математику или матрицы в частности?

Matt.

Answer 1

Вы можете сделать это с помощью последовательности холеских нисходящих:

(ниже я использую 'для транспонирования, чтобы избежать путаницы с умножением)

Если коэффициент Холески для A равен a, а для C равен c, то уравнение для Q можно написать

Q = c * c '- beta' * beta где бета = обратная (а) B (т. е. решить бета = B для бета)

Если мы напишем b [i] для i-го столбца бета-версии, то

Q = c * c '- Сумма b [i] * b [i]'

Нахождение холесского разложения

c c '- x x' (где x - вектор, а c - нижний треугольник)

известен как холеский нисходящий разряд ранга 1. Для этого существует стабильный алгоритм в Голуб и ван Лоан

Answer 2

Я думаю, что пришел к ответу, хотя это не совсем то, на что я надеялся.

Устраняя контекст машинного обучения, мой вопрос сводился к тому, будет ли знание C ^ {1/2}помощь в расчете Q ^ {- 1/2}.Ниже я более подробно остановлюсь, но, чтобы сократить погоню, ответ - да, но только в отношении стабильности, а не вычислений (не могу доказать это в настоящее время, но довольно точно).

Для того, почему ответ «да» относительно стабильности, мы смотрим на определение Q из первоначального вопроса, которое было переставлено следующим образом.

Q = C - B * A ^ {- 1} B= (C ^ {1/2} + B * A ^ {- * / 2}) (C ^ {1/2} - B * A ^ {- * / 2}) *

ЗнаяC ^ {1/2} перед этим, мы можем вычислить Q без необходимости инвертировать A напрямую.Прямая инверсия не является численно стабильной.

К сожалению, хотя я провел немало исследований по этому вопросу, не похоже, что $ C ^ {1/2} $ помогает вычислению в точном вычисленииQ ^ {- 1/2}.Наилучшим подходом является вычисление Q с использованием C ^ {1/2}, как описано выше, а затем использование Cholesky для разложения Q на Q ^ {1/2}, а затем прямая замена для вычисления Q ^ {- 1/2}.

Дальнейшие исследования

Одной областью, которую я не очень подробно изучал, была возможность использования C ^ {1/2} для аппроксимации Q ^ {- 1/2}.Нечто подобное итеративному методу, использующему C ^ {1/2} в качестве отправной точки.Я не знаю ни одного такого итеративного процесса аппроксимации, но я продолжу поиск.Я даже могу начать новый вопрос с этого вопроса.

Я обновлю вас всех, если у меня будут какие-то серьезные прорывы.