Сколько пространства требуется для регрессии гребня?

Question

В Haskell, ridge regression может быть выражена как:

import Numeric.LinearAlgebra 

createReadout :: Matrix Double → Matrix Double → Matrix Double 
createReadout a b = oA <\> oB 
    where 
    μ = 1e-4 

    oA = (a <> (tr a)) + (μ * (ident $ rows a)) 
    oB = a <> (tr b) 

Однако, эта операция очень дорого памяти. Вот минималистский пример, который требует более 2 ГБ на моей машине и занимает 3 минуты.

import Numeric.LinearAlgebra 
import System.Random 

createReadout :: Matrix Double -> Matrix Double -> Matrix Double 
createReadout a b = oA <\> oB 
    where 
    mu = 1e-4 
    oA = (a <> (tr a)) + (mu * (ident $ rows a)) 
    oB = a <> (tr b) 

teacher :: [Int] -> Int -> Int -> Matrix Double 
teacher labelsList cols' correctRow = fromBlocks $ f <$> labelsList 
    where ones = konst 1.0 (1, cols') 
     zeros = konst 0.0 (1, cols') 
     rows' = length labelsList 
     f i | i == correctRow = [ones] 
      | otherwise = [zeros] 

glue :: Element t => [Matrix t] -> Matrix t 
glue xs = fromBlocks [xs] 

main :: IO() 
main = do 

    let n = 1500 -- <- The constant to be increased 
     m = 10000 
     cols' = 12 

    g <- newStdGen 

    -- Stub data 
    let labels = take m . map (`mod` 10) . randoms $ g :: [Int] 
     a = (n >< (cols' * m)) $ take (cols' * m * n) $ randoms g :: Matrix Double 
     teachers = zipWith (teacher [0..9]) (repeat cols') labels 
     b = glue teachers 

    print $ maxElement $ createReadout a b 
    return() 

$ междусобойчик Exec GHC - -O2 Test.hs

$ Время ./test
./test 190.16s пользователя 5.22s система 106% CPU 3: 03,93 общая

Задача состоит в том, чтобы увеличить константу n, по крайней мере, до n = 4000, в то время как оперативная память ограничена 5 ГБ. Что такое минимальное пространство, которое требует теория преобразования матрицы? Как оптимизировать эту операцию с точки зрения пространства? Может ли регрессия гребня быть эффективно заменена более дешевым методом?

Answer 1

Простой гауссово-иорданское устранение требует только пространства для хранения входных и выходных матриц и постоянного вспомогательного пространства. Если я правильно читаю, матрица oA вам нужно инвертировать n x n, так что это не проблема.

Использование памяти полностью зависит от хранения входной матрицы a, которая использует не менее 1500 * 120000 * 8 = 1,34 ГБ. n = 4000 будет 4000 * 120000 * 8 = 3,58 ГБ, что составляет более половины вашего космического бюджета. Я не знаю, какую матричную библиотеку вы используете или как она хранит свои матрицы, но если они находятся в куче Haskell, то эффекты GC могут легко учитывать другой фактор 2 в использовании пространства.

Answer 2

Ну, вы можете уйти с пространством 3 * m + nxn, но насколько это будет с численным стабильностью, я не уверен.

Основой является тождественным

inv(inv(Q) + A'*A)) = Q - Q*A'*R*A*Q 
where R = inv(I + A*Q*A') 

Если А ваша матрица А и

Q = inv(mu*I*mu*I) = I/(mu*mu) 

то решение вашей конька регрессии

inv(inv(Q) + A'*A)) * A'*b 

немного больше алгебра показывает

inv(inv(Q) + A'*A)) = (I - A'*inv((mu2 + A*A'))*A)/mu2 
where mu2 = mu*m 

Заметим, что поскольку A является n x m, A * A 'является n x n.

Так один алгоритм будет

Compute C = A * A '+ mu2

Делает Чолески разложения, из С, то есть найти верхнюю треугольную U, так что U' * U = C

Вычислить вектор у = А «* б

Вычислить вектор г = А * у

решить U» * и = г для и в г

Решить U * V = г при г в г

вычислить ш = А '* г

Вычислить х = (у - ш)/mu2.