嶺迴歸需要多少空間？

在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

嶺迴歸需要多少空間？

回答

相關問題