Tweet Share Share Share

Sidst opdateret den 9. august 2019

Mange komplekse matrixoperationer kan ikke løses effektivt eller stabilt ved hjælp af computeres begrænsede præcision.

Matrixdekompositioner er metoder, der reducerer en matrix i konstituerende dele, som gør det lettere at beregne mere komplekse matrixoperationer. Matrixdekomponeringsmetoder, også kaldet matrixfaktoriseringsmetoder, er et fundament for lineær algebra i computere, selv for grundlæggende operationer som f.eks. løsning af systemer af lineære ligninger, beregning af inversen og beregning af determinanten af en matrix.

I denne tutorial vil du opdage matrixdekompositioner, og hvordan du beregner dem i Python.

Når du har gennemført denne tutorial, vil du vide:

  • Hvad en matrixdekomposition er, og hvorfor disse typer operationer er vigtige.
  • Hvordan man beregner en LU- ogQR-matrixdekompositioner i Python.
  • Hvordan man beregner en Cholesky-matrixdekomposition i Python.

Kick-start dit projekt med min nye bog Linear Algebra for Machine Learning, herunder trinvise vejledninger og Python-kildekodefilerne til alle eksempler.

Lad os komme i gang.

  • Opdatering marts 2018: Opdateret juli/2019: Rettet en lille tastefejl i beskrivelsen af QR-dekomposition.
  • Opdateret juli/2019: Rettet en lille tastefejl ved beskrivelsen af positivt definitte matricer.
En blid introduktion til matrixdekompositioner til maskinlæring

En blid introduktion til matrixdekompositioner til maskinlæring
Foto af mickey, some rights reserved.

Tutorial Overview

Denne tutorial er opdelt i 4 dele; de er:

  1. Hvad er en matrixdekomposition?
  2. LU-matrixdekomposition
  3. QR-matrixdekomposition
  4. Cholesky-dekomposition

Har du brug for hjælp med lineær algebra til maskinindlæring?

Tag mit gratis 7-dages e-mail crashkursus nu (med prøvekode).

Klik for at tilmelde dig og få også en gratis PDF Ebook-version af kurset.

Download dit GRATIS minikursus

Hvad er en matrixdekomposition?

En matrixdekomposition er en måde at reducere en matrix til dens bestanddele.

Det er en fremgangsmåde, der kan forenkle mere komplekse matrixoperationer, som kan udføres på den dekomponerede matrix i stedet for på selve den oprindelige matrix.

En almindelig analogi for matrixdekomponering er faktorisering af tal, f.eks. faktorisering af 10 til 2 x 5. Af denne grund kaldes matrixdekomponering også for matrixfaktorisering. Ligesom faktorisering af reelle værdier er der mange måder at dekomponere en matrix på, og derfor findes der en række forskellige matrixdekomponeringsmetoder.

To enkle og meget anvendte matrixdekomponeringsmetoder er LU-matrixdekomponering og QR-matrixdekomponering.

Næste gang vil vi se nærmere på hver af disse metoder.

LU-matrixdekomposition

LU-dekompositionen er for kvadratiske matricer og dekomponerer en matrix i L og U komponenter.

1
A = L . U

Og, uden punktnotationen.

1
A = LU

Hvor A er den kvadratiske matrix, som vi ønsker at dekomponere, L er den nederste trekantmatrix og U er den øverste trekantmatrix.

Faktorerne L og U er trekantede matricer. Den faktorisering, der fremkommer ved eliminering, er A = LU.

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

LU-dekompositionen findes ved hjælp af en iterativ numerisk proces og kan mislykkes for de matricer, der ikke kan dekomponeres eller let kan dekomponeres.

En variation af denne dekomposition, der er numerisk mere stabil at løse i praksis, kaldes LUP-dekompositionen, eller LU-dekompositionen med partiel pivoting.

1
A = P . L . U

Rækkerne i den overordnede matrix omarrangeres for at forenkle dekompositionsprocessen, og den yderligere P-matrix angiver en måde at permutere resultatet eller returnere resultatet til den oprindelige rækkefølge. Der findes også andre variationer af LU.

LU-dekompositionen bruges ofte til at forenkle løsningen af systemer af lineære ligninger, f.eks. til at finde koefficienterne i en lineær regression, samt til at beregne determinanten og inversen af en matrix.

LU-dekompositionen kan implementeres i Python med lu()-funktionen. Mere specifikt beregner denne funktion en LPU-dekomponering.

Eksemplet nedenfor definerer først en 3×3 kvadratisk matrix. LU-dekompositionen beregnes, hvorefter den oprindelige matrix rekonstrueres ud fra komponenterne.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
# LU-dekomponering
from numpy import array
from scipy.linalg import lu
# definere en kvadratisk matrix
A = array(, , ])
print(A)
# LU-dekomponering
P, L, U = lu(A)
print(P)
print(L)
print(U)
# rekonstruere
B = P.dot(L).dot(U)
print(B)

Afprøvning af eksemplet udskriver først den definerede 3×3-matrix, derefter P-, L- og U-komponenterne i dekompositionen, og til sidst rekonstrueres den oprindelige matrix.

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

QR-matrixdekomposition

QR-dekompositionen gælder for m x n matricer (ikke begrænset til kvadratiske matricer) og dekomponerer en matrix i Q- og R-komponenter.

1
A = Q . R

Og, uden punktnotationen.

1
A = QR

Hvor A er den matrix, som vi ønsker at dekomponere, Q er en matrix med størrelsen m x m, og R er en øverste trekantmatrix med størrelsen m x n.

QR-dekompositionen findes ved hjælp af en iterativ numerisk metode, der kan mislykkes for de matricer, der ikke kan dekomponeres, eller som nemt kan dekomponeres.

Som LU-dekompositionen bruges QR-dekompositionen ofte til at løse systemer af lineære ligninger, selv om den ikke er begrænset til kvadratiske matricer.

QR-dekompositionen kan implementeres i NumPy ved hjælp af funktionen qr(). Som standard returnerer funktionen Q- og R-matricerne med mindre eller “reducerede” dimensioner, hvilket er mere økonomisk. Vi kan ændre dette til at returnere de forventede størrelser m x m for Q og m x n for R ved at angive mode-argumentet som ‘komplet’, selv om dette ikke er påkrævet for de fleste applikationer.

Eksemplet nedenfor definerer en 3×2-matrix, beregner QR-dekompositionen og rekonstruerer derefter den oprindelige matrix ud fra de dekomponerede elementer.

1
2
3
4
5
6
7
8
9
10
11
12
13
# QR-dekomponering
from numpy import array
from numpy.linalg import qr
# definer en 3×2 matrix
A = array(, , ])
print(A)
# QR-dekomposition
Q, R = qr(A, ‘complete’)
print(Q)
print(R)
# rekonstruer
B = Q.dot(R)
print(B)

Afprøvning af eksemplet udskriver først den definerede 3×2-matrix, derefter Q- og R-elementerne og til sidst den rekonstruerede matrix, der passer til det, vi startede med.

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

Cholesky-dekomposition

Cholesky-dekompositionen gælder for kvadratiske symmetriske matricer, hvor alle egenværdierne er større end nul, såkaldte positivt definitte matricer.

For vores interesser i maskinlæring vil vi fokusere på Cholesky-dekompositionen for reelle matricer og se bort fra de tilfælde, hvor vi arbejder med komplekse tal.

Dekompositionen er defineret som følger:

1
A = L . L^T

Og uden punktnotationen:

1
A = LL^T

Hvor A er den matrix, der skal dekomponeres, L er den nedre trekantede matrix, og L^T er transponeringen af L.

Den dekomponerede kan også skrives som produktet af den øvre trekantede matrix, for eksempel:

1
A = U^T . U

Hvor U er den øverste trekantede matrix.

Cholesky-dekompositionen anvendes til løsning af lineære mindste kvadrater til lineær regression samt til simulerings- og optimeringsmetoder.

Ved dekomponering af symmetriske matricer er Cholesky-dekomponeringen næsten dobbelt så effektiv som LU-dekomponeringen og bør foretrækkes i disse tilfælde.

Selv om symmetriske, positivt definitte matricer er ret specielle, forekommer de ret hyppigt i nogle anvendelser, så deres specielle faktorisering, kaldet Cholesky-dekomponering, er god at kende til. Når man kan bruge den, er Cholesky-dekomposition ca. en faktor to hurtigere end alternative metoder til løsning af lineære ligninger.

– Side 100, Numeriske opskrifter: The Art of Scientific Computing, Third Edition, 2007.

Cholesky-dekompositionen kan implementeres i NumPy ved at kalde funktionen cholesky(). Funktionen returnerer kun L, da vi nemt kan få adgang til L transponeringen efter behov.

Eksemplet nedenfor definerer en 3×3 symmetrisk og positivt bestemt matrix og beregner Cholesky-dekompositionen, hvorefter den oprindelige matrix rekonstrueres.

1
2
3
4
5
6
7
8
9
10
11
12
# Cholesky-dekomponering
from numpy import array
from numpy.linalg import cholesky
# definere en 3×3 matrix
A = array(, , ])
print(A)
# Cholesky-dekomposition
# L = cholesky(A)
print(L)
# rekonstruere
> B = L.dot(L.T)
print(B)

Kørsel af eksemplet udskriver først den symmetriske matrix, derefter den nedre trekantede matrix fra dekomponeringen efterfulgt af den rekonstruerede matrix.

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

Udvidelser

Dette afsnit indeholder en liste over nogle idéer til udvidelse af vejledningen, som du måske ønsker at udforske.

  • Skab 5 eksempler, hvor du bruger hver operation med dine egne data.
  • Søg i artikler om maskinlæring og find 1 eksempel på hver operation, der bruges.

Hvis du udforsker nogle af disse udvidelser, vil jeg gerne vide det.

Videre læsning

Dette afsnit indeholder flere ressourcer om emnet, hvis du ønsker at gå dybere ned i emnet.

Bøger

  • Afsnit 6.6 Matrixdekompositioner. No Bullshit Guide To Linear Algebra, 2017.
  • Lektion 7 QR-faktorisering, Numerisk lineær algebra, 1997.
  • Afsnit 2.3 LU-dekomponering og dens anvendelser, Numeriske opskrifter: The Art of Scientific Computing, Third Edition, 2007.
  • Afsnit 2.10 QR-dekomposition, Numerical Recipes: The Art of Scientific Computing, Third Edition, 2007.
  • Afsnit 2.9 Cholesky Decomposition, Numerical Recipes: Numerical Recipes: The Art of Scientific Computing, Third Edition, 2007.
  • Lektion 23, Cholesky Decomposition, Numerical Linear Algebra, 1997.

API

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

Artikler

  • Matrixdekomposition på Wikipedia
  • LU-dekomposition på Wikipedia
  • QR-dekomposition på Wikipedia
  • Cholesky-dekomposition på Wikipedia

Summary

I denne vejledning, har du opdaget matrixdekompositioner, og hvordan man beregner dem i Python.

Specifikt har du lært:

  • Hvad en matrixdekomposition er, og hvorfor disse typer operationer er vigtige.
  • Hvordan man beregner en LU- ogQR-matrixdekomposition i Python.
  • Hvordan man beregner en Cholesky-matrixdekomposition i Python.

Har du spørgsmål?
Sæt dine spørgsmål i kommentarerne nedenfor, og jeg vil gøre mit bedste for at besvare dem.

Få styr på lineær algebra til maskinlæring!

Linear algebra til maskinlæring

Udvikle en fungerende forståelse af lineær algebra

…ved at skrive kodelinjer i python

Opdag hvordan i min nye E-bog:
Linear Algebra for Machine Learning

Den indeholder selvstuderende tutorials om emner som:
Vektornormer, Matrixmultiplikation, Tensorer, Eigendekomposition, SVD, PCA og meget mere…

Finally Understand the Mathematics of Data

Skip de akademiske. Just Results.

Se, hvad der er inde i

Tweet Share Share Share

By: adminPosted on

Skriv et svar

Din e-mailadresse vil ikke blive publiceret.