Tweet Share Share

Last Updated on August 9, 2019

Wiele złożonych operacji na macierzach nie może być rozwiązanych wydajnie lub ze stabilnością przy użyciu ograniczonej precyzji komputerów.

Dekompozycje macierzy to metody, które redukują macierz na części składowe, które ułatwiają obliczanie bardziej złożonych operacji na macierzach. Metody dekompozycji macierzy, zwane również metodami faktoryzacji macierzy, są podstawą algebry liniowej w komputerach, nawet dla podstawowych operacji, takich jak rozwiązywanie układów równań liniowych, obliczanie odwrotności i wyznacznika macierzy.

W tym poradniku poznasz rozkłady macierzy i dowiesz się, jak je obliczać w Pythonie.

Po ukończeniu tego poradnika będziesz wiedział:

  • Co to jest rozkład macierzy i dlaczego tego typu operacje są ważne.
  • Jak obliczyć dekompozycje macierzy LU iQR w Pythonie.
  • Jak obliczyć dekompozycję macierzy Cholesky’ego w Pythonie.

Kick-startuj swój projekt z moją nową książką Linear Algebra for Machine Learning, zawierającą samouczki krok po kroku oraz pliki kodu źródłowego Pythona dla wszystkich przykładów.

Zacznijmy.

  • Aktualizacja Mar/2018: Poprawiona mała literówka w opisie QR Decomposition.
  • Aktualizacja Jul/2019: Poprawiona mała literówka przy opisie macierzy dodatnio definiowalnych.
A Gentle Introduction to Matrix Decompositions for Machine Learning

A Gentle Introduction to Matrix Decompositions for Machine Learning
Photo by mickey, some rights reserved.

Przegląd samouczka

Ten samouczek jest podzielony na 4 części; są to:

  1. Co to jest dekompozycja macierzy?
  2. Dekompozycja macierzy LU
  3. Dekompozycja macierzy QR
  4. Dekompozycja macierzy Cholesky’ego

Potrzebujesz pomocy z Algebrą liniową dla uczenia maszynowego?

Weź udział w moim darmowym 7-dniowym kursie e-mailowym (z przykładowym kodem).

Kliknij, aby się zapisać, a także otrzymać darmową wersję PDF Ebook kursu.

Pobierz swój DARMOWY mini-kurs

Co to jest dekompozycja macierzy?

Dekompozycja macierzy jest sposobem redukcji macierzy do jej części składowych.

Jest to podejście, które może uprościć bardziej złożone operacje na macierzach, które mogą być wykonywane na zdekomponowanej macierzy, a nie na samej oryginalnej macierzy.

Powszechną analogią dla dekompozycji macierzy jest faktoryzacja liczb, taka jak faktoryzacja 10 na 2 x 5. Z tego powodu dekompozycja macierzy jest również nazywana faktoryzacją macierzy. Podobnie jak faktoryzacja wartości rzeczywistych, istnieje wiele sposobów dekompozycji macierzy, stąd istnieje szereg różnych technik dekompozycji macierzy.

Dwie proste i szeroko stosowane metody dekompozycji macierzy to dekompozycja macierzy LU i dekompozycja macierzy QR.

Następnie przyjrzymy się bliżej każdej z tych metod.

Dekompozycja macierzy LU

Dekompozycja LU dotyczy macierzy kwadratowych i rozkłada macierz na składniki L i U.

1
A = L . U

Albo, bez notacji kropkowej.

1
A = LU

Gdzie A jest macierzą kwadratową, którą chcemy zdekomponować, L to macierz trójkątów dolnych, a U to macierz trójkątów górnych.

Współczynniki L i U są macierzami trójkątnymi. Faktoryzacja, która wynika z eliminacji, to A = LU.

– Strona 97, Introduction to Linear Algebra, Fifth Edition, 2016.

Dekompozycja LU jest znajdowana przy użyciu iteracyjnego procesu numerycznego i może zawieść w przypadku tych macierzy, których nie można zdekomponować lub dekomponuje się je łatwo.

Odmiana tego rozkładu, która jest numerycznie bardziej stabilna do rozwiązania w praktyce, nazywa się rozkładem LUP, lub rozkładem LU z częściowym przestawieniem.

1
A = P . L . U

W celu uproszczenia procesu dekompozycji wiersze macierzy macierzystej są ponownie uporządkowane, a dodatkowa macierz P określa sposób permutacji wyniku lub przywrócenia wyniku do pierwotnej kolejności. Istnieją również inne odmiany LU.

Dekompozycja LU jest często używana do uproszczenia rozwiązywania układów równań liniowych, takich jak znajdowanie współczynników w regresji liniowej, a także do obliczania wyznacznika i odwrotności macierzy.

Dekompozycję LU można zaimplementować w Pythonie za pomocą funkcji lu(). Dokładniej, funkcja ta oblicza dekompozycję LU.

Poniższy przykład najpierw definiuje macierz kwadratową 3×3. Obliczana jest dekompozycja LU, a następnie oryginalna macierz jest rekonstruowana ze składników.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
# LU decomposition
from numpy import array
from scipy.linalg import lu
# define a square matrix
A = array(, , ])
print(A)
# LU decomposition
P, L, U = lu(A)
print(P)
print(L)
print(U)
# reconstruct
B = P.dot(L).dot(U)
print(B)

Wykonanie przykładu powoduje najpierw wydrukowanie zdefiniowanej macierzy 3×3, następnie składowych P, L i U rozkładu, a na końcu zrekonstruowanie oryginalnej macierzy.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
]
]
]
]
]

R Dekompozycja macierzy QR

Dekompozycja QR jest dla macierzy m x n (nie ogranicza się do macierzy kwadratowych) i rozkłada macierz na składowe Q i R.

1
A = Q . R

Albo, bez notacji kropkowej.

1
A = QR

Gdzie A jest macierzą, którą chcemy zdekomponować, Q macierz o rozmiarze m x m, a R jest macierzą trójkątną górną o rozmiarze m x n.

Rozkład QR jest znajdowany przy użyciu iteracyjnej metody numerycznej, która może zawieść dla tych macierzy, które nie mogą być rozłożone lub są łatwe do rozłożenia.

Podobnie jak rozkład LU, rozkład QR jest często używany do rozwiązywania układów równań liniowych, chociaż nie jest ograniczony do macierzy kwadratowych.

Rozkład QR może być zaimplementowany w NumPy przy użyciu funkcji qr(). Domyślnie funkcja zwraca macierze Q i R z mniejszymi lub „zredukowanymi” wymiarami, co jest bardziej ekonomiczne. Możemy to zmienić, aby zwrócić oczekiwane rozmiary m x m dla Q i m x n dla R, określając argument mode jako 'complete’, chociaż nie jest to wymagane dla większości zastosowań.

Poniższy przykład definiuje macierz 3×2, oblicza dekompozycję QR, a następnie rekonstruuje oryginalną macierz z rozłożonych elementów.

1
2
3
4
5
6
7
8
9
10
11
12
13
# Dekompozycja QR
from numpy import array
from numpy.linalg import qr
# define a 3×2 matrix
A = array(, , ])
print(A)
# QR decomposition
Q, R = qr(A, 'complete’)
print(Q)
print(R)
# reconstruct
B = Q.dot(R)
print(B)

Running the example first prints the defined 3×2 matrix, then the Q and R elements, then finally the reconstructed matrix that matches what we started with.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
]
]
]
]

Dekompozycja Cholesky’ego

Dekompozycja Cholesky’ego jest dla kwadratowych macierzy symetrycznych, w których wszystkie wartości własne są większe od zera, tzw. macierzy dodatnio definiowalnych.

Dla naszych zainteresowań w uczeniu maszynowym, skupimy się na dekompozycji Cholesky’ego dla macierzy rzeczywisto-wartościowych i zignorujemy przypadki, gdy pracujemy z liczbami zespolonymi.

Rozkład ten definiuje się następująco:

1
A = L . L^T

Albo bez notacji kropkowej:

1
A = LL^T

Gdzie A jest macierzą podlegającą dekompozycji, L jest macierzą trójkątną dolną, a L^T jest transpozycją L.

Rozkład można również zapisać jako iloczyn macierzy trójkątnych górnych, na przykład:

1
A = U^T . U

Gdzie U jest macierzą trójkątną górną.

Dekompozycja Cholesky’ego jest używana do rozwiązywania liniowych najmniejszych kwadratów dla regresji liniowej, a także metod symulacyjnych i optymalizacyjnych.

Przy rozkładaniu macierzy symetrycznych, rozkład Cholesky’ego jest prawie dwa razy bardziej wydajny niż rozkład LU i powinien być preferowany w tych przypadkach.

Chociaż symetryczne, dodatnio określone macierze są raczej specjalne, występują dość często w niektórych zastosowaniach, więc dobrze jest wiedzieć o ich specjalnej faktoryzacji, zwanej rozkładem Cholesky’ego. Gdy można go użyć, rozkład Cholesky’ego jest o czynnik dwa szybszy niż alternatywne metody rozwiązywania równań liniowych.

– Strona 100, Numerical Recipes: The Art of Scientific Computing, Third Edition, 2007.

Dekompozycja Cholesky’ego może być zaimplementowana w NumPy poprzez wywołanie funkcji cholesky(). Funkcja zwraca tylko L, ponieważ możemy łatwo uzyskać dostęp do transpozycji L w razie potrzeby.

Poniższy przykład definiuje macierz 3×3 symetryczną i dodatnio określoną i oblicza rozkład Cholesky’ego, a następnie oryginalna macierz jest rekonstruowana.

1
2
3
4
5
6
7
8
9
10
11
12
# Cholesky decomposition
from numpy import array
from numpy.linalg import cholesky
# define a 3×3 matrix
A = array(, , ])
print(A)
# Cholesky decomposition
L = cholesky(A)
print(L)
# reconstruct
B = L.dot(L.T)
print(B)

Wykonanie przykładu najpierw drukuje macierz symetryczną, następnie macierz trójkątną dolną z dekompozycji, a po niej macierz zrekonstruowaną.

1
2
3
4
5
6
7
8
9
10
11
]
]
]

Rozszerzenia

Ta sekcja zawiera kilka pomysłów na rozszerzenie samouczka, które możesz chcieć zbadać.

  • Stwórz 5 przykładów używając każdej operacji z własnymi danymi.
  • Przeszukaj dokumenty dotyczące uczenia maszynowego i znajdź 1 przykład użycia każdej operacji.

Jeśli zbadasz któreś z tych rozszerzeń, chętnie się dowiem.

Dalsza lektura

Ta sekcja zapewnia więcej zasobów na ten temat, jeśli szukasz głębiej.

Książki

  • Sekcja 6.6 Matrix decompositions. No Bullshit Guide To Linear Algebra, 2017.
  • Lecture 7 QR Factorization, Numerical Linear Algebra, 1997.
  • Section 2.3 LU Decomposition and Its Applications, Numerical Recipes: The Art of Scientific Computing, Third Edition, 2007.
  • Section 2.10 QR Decomposition, Numerical Recipes: The Art of Scientific Computing, Third Edition, 2007.
  • Section 2.9 Cholesky Decomposition, Numerical Recipes: The Art of Scientific Computing, Third Edition, 2007.
  • Lecture 23, Cholesky Decomposition, Numerical Linear Algebra, 1997.

API

  • scipy.linalg.lu() API
  • numpy.linalg.qr() API
  • numpy.linalg.cholesky() API

Artykuły

  • Rozkład macierzy na Wikipedii
  • Rozkład LU na Wikipedii
  • Rozkład QR na Wikipedii
  • Rozkład Cholesky’ego na Wikipedii

Podsumowanie

W tym tutorialu, odkryłeś rozkłady macierzy i jak je obliczać w Pythonie.

W szczególności dowiedziałeś się:

  • Czym jest rozkład macierzy i dlaczego tego typu operacje są ważne.
  • Jak obliczyć rozkłady macierzy LU iQR w Pythonie.
  • Jak obliczyć rozkład macierzy Cholesky’ego w Pythonie.

Czy masz jakieś pytania?
Zadawaj pytania w komentarzach poniżej, a ja postaram się odpowiedzieć.

Zapoznaj się z algebrą liniową dla uczenia maszynowego!

Algebra liniowa dla uczenia maszynowego

Rozwiń działające zrozumienie algebry liniowej

…pisząc linie kodu w pythonie

Odkryj jak w moim nowym Ebooku:
Algebra liniowa dla uczenia maszynowego

Zawiera on samouczki na takie tematy jak:
normy wektorowe, mnożenie macierzy, tensory, Eigendekompozycja, SVD, PCA i wiele więcej…

Zrozum wreszcie matematykę danych

Opuść akademickość. Just Results.

See What’s Inside

Tweet Share Share

By: adminPosted on

Dodaj komentarz

Twój adres e-mail nie zostanie opublikowany.