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

Question

В Haskell регрессия гребня может быть выражена как:

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 ()

$ cabal exec ghc - -O2 Test.hs

$ time./Test
./Test 190.16s пользователь 5.22s система 106% процессор 3:03.93 всего

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

Answer 1

Простое исключение Гаусса-Джордана занимает только место для хранения входных и выходных матриц плюс постоянное вспомогательное пространство. Если я правильно читаю, матрица oA вам нужно инвертировать это n Икс 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 - это nxm, A * A '- это nx n.

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

Вычислить C = A * A '+ mu2

Сделайте холеский разложение C, то есть найдите верхний треугольник U так, чтобы U'*U = C

Вычислить вектор y = A '* b

Вычислить вектор z = A * y

Решите U'*u = z для u в z

Решить U*v = z для v в z

вычислить w = A '* z

Вычислить x = (y - w)/mu2.