岭回归需要多少空间？

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

然而，该操作是非常昂贵的存储器。这是一个简约的例子，需要在我的机器上超过2GB，并需要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 = 4000，而RAM由5GB限制。理论上矩阵求逆运算所需的最小空间是什么？这个操作如何在空间上得到优化？可以用更便宜的方法有效地替代岭回归？

来源

2016-12-03 penkovsky

我在读这个权利，'a'是一个1500 x 120000矩阵？ –

完全正确。它可能会更大。 – penkovsky

矩阵[稀疏]（https://en.wikipedia.org/wiki/Sparse_matrix）？这可以为你节省大量的时间和空间（但你可能需要像[共轭梯度]（https://en.wikipedia.org/wiki/Conjugate_gradient_method））这样的专用算法。 – leftaroundabout

简单高斯 - 约旦消去只占用的空间来存储输入和输出矩阵加上恒定辅助空间。如果我读正确，oA你需要反转的矩阵是n X n所以这不是一个问题。

你的内存使用完全由存储输入矩阵a，它使用至少1500 * 120000 * 8 = 1.34 GB支配。 n = 4000将是4000 * 120000 * 8 = 3.58 GB，超过您的空间预算的一半。我不知道你使用的是什么矩阵库，也不知道它如何存储矩阵，但是如果它们在Haskell堆中，那么GC效应可以轻松地占用另一个空间使用量的2倍。

来源

2016-12-03 15:51:24

里德，谢谢你的回答。事实上，我不得不提及，我正在使用与C例程（BLAS和LAPACK）交互的hmatrix库。然后将矩阵存储为Data.Vector.Storable数组。 – penkovsky

那么你可以逃脱3 * M + N×N的空间，但如何数值稳定，这将是我不知道。

的基础是身份

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

如果A是你的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×m个，A * A”为n×n个。

所以一个算法将是

计算C = A * A '+ MU2

执行℃的乔列斯基分解方法，即找到上三角Ü使得U' * U = C

计算矢量y = A '* b

计算向量z = A * Y

解决U' 沿z

* U = Z为ü 10

解决U * V = z对V IN Z = A'* Z

计算x =（Y - W）

计算W/MU2。

来源

2016-12-06 18:04:43 dmuir

岭回归需要多少空间？

回答

相关问题