Tweet Share Share Share

Sist uppdaterad den 9 augusti 2019

Många komplexa matrisoperationer kan inte lösas effektivt eller stabilt med hjälp av datorernas begränsade precision.

Matrisdekompositioner är metoder som reducerar en matris i beståndsdelar som gör det lättare att beräkna mer komplexa matrisoperationer. Metoder för matrisdekompositioner, även kallade metoder för faktorisering av matriser, är en grund för linjär algebra i datorer, även för grundläggande operationer som att lösa system av linjära ekvationer, beräkna inversen och beräkna determinanten för en matris.

I den här handledningen kommer du att upptäcka matrisdekompositioner och hur man beräknar dem i Python.

När du har slutfört den här handledningen kommer du att veta:

  • Vad en matrisdekomposition är och varför dessa typer av operationer är viktiga.
  • Hur man beräknar en LU- ochQR-matrisdekomposition i Python.
  • Hur man beräknar en Cholesky-matrisdekomposition i Python.

Kicka igång ditt projekt med min nya bok Linear Algebra for Machine Learning, inklusive steg-för-steg-handledning och Pythons källkodsfiler för alla exempel.

Sätt igång.

  • Uppdatering mars 2018:
  • Uppdatering juli 2019: Rättade ett litet tryckfel i beskrivningen av positivt bestämda matriser.
A Gentle Introduction to Matrix Decompositions for Machine Learning

A Gentle Introduction to Matrix Decompositions for Machine Learning
Foto av mickey, some rights reserved.

Tutorial Overview

Denna tutorial är uppdelad i fyra delar, de är:

  1. Vad är en matrisdekomposition?
  2. LU-matrisdekomposition
  3. QR-matrisdekomposition
  4. Cholesky-dekomposition

Behövs hjälp med linjär algebra för maskininlärning?

Ta min kostnadsfria 7-dagars snabbkurs via e-post nu (med exempelkod).

Klicka för att registrera dig och få en gratis PDF-version av kursen.

Ladda ner din kostnadsfria minikurs

Vad är en matrisdekomposition?

En matrisdekomposition är ett sätt att reducera en matris till dess beståndsdelar.

Det är ett tillvägagångssätt som kan förenkla mer komplexa matrisoperationer som kan utföras på den dekomponerade matrisen snarare än på själva den ursprungliga matrisen.

En vanlig analogi för matrisdekomponering är faktorisering av tal, till exempel faktoriseringen av 10 till 2 x 5. Därför kallas matrisdekomponering också för matrisfaktorisering. Precis som vid faktorisering av reella värden finns det många sätt att sönderdela en matris, därför finns det en rad olika metoder för matrisdekomposition.

Två enkla och allmänt använda metoder för matrisdekomposition är LU-matrisdekompositionen och QR-matrisdekompositionen.

Nästan kommer vi att titta närmare på var och en av dessa metoder.

LU-matrisdekomposition

LU-dekompositionen gäller för kvadratiska matriser och dekomponerar en matris i L- och U-komponenter.

1
A = L . U

Och, utan punktnotering.

1
A = LU

Varvid A är den kvadratiska matris som vi vill dekomponera, L är den nedre triangelmatrisen och U är den övre triangelmatrisen.

Faktorerna L och U är triangulära matriser. Den faktorisering som kommer från elimineringen är A = LU.

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

LU-dekompositionen hittas med hjälp av en iterativ numerisk process och kan misslyckas för de matriser som inte kan dekomponeras eller som lätt kan dekomponeras.

En variant av denna dekomposition som är numeriskt mer stabil att lösa i praktiken kallas LUP-dekompositionen, eller LU-dekompositionen med partiell pivotering.

1
A = P . L . U

Raderna i den överordnade matrisen ordnas om för att förenkla sönderdelningsprocessen och den ytterligare P-matrisen anger ett sätt att permutera resultatet eller återställa resultatet till den ursprungliga ordningen. Det finns även andra varianter av LU.

LU-dekompositionen används ofta för att förenkla lösningen av system av linjära ekvationer, t.ex. för att hitta koefficienterna i en linjär regression, samt för att beräkna determinanten och inversen av en matris.

LU-dekompositionen kan implementeras i Python med funktionen lu(). Mer specifikt beräknar denna funktion en LU-dekomposition.

Exemplet nedan definierar först en 3×3 kvadratisk matris. LU-dekompositionen beräknas och därefter rekonstrueras den ursprungliga matrisen från komponenterna.

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

Att köra exemplet visar först den definierade 3×3-matrisen, sedan P-, L- och U-komponenterna i dekompositionen, och slutligen rekonstrueras den ursprungliga matrisen.

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

QR-matrisdekomposition

QR-dekompositionen gäller för m x n-matriser (inte begränsat till kvadratiska matriser) och dekomponerar en matris i Q- och R-komponenter.

1
A = Q . R

Och, utan punktnotering.

1
A = QR

Varvid A är den matris som vi vill dekomponera, Q är en matris med storleken m x m och R är en övre triangelmatris med storleken m x n.

R QR-dekompositionen hittas med hjälp av en iterativ numerisk metod som kan misslyckas för de matriser som inte kan dekomponeras, eller som lätt kan dekomponeras.

Likt LU-dekompositionen används QR-dekompositionen ofta för att lösa system av linjära ekvationer, även om den inte är begränsad till kvadratiska matriser.

R QR-dekompositionen kan implementeras i NumPy med hjälp av funktionen qr(). Som standard returnerar funktionen Q- och R-matriserna med mindre eller ”reducerade” dimensioner som är mer ekonomiska. Vi kan ändra detta till att returnera de förväntade storlekarna m x m för Q och m x n för R genom att ange argumentet mode som ”complete”, även om detta inte krävs för de flesta tillämpningar.

Exemplet nedan definierar en 3×2-matris, beräknar QR-dekompositionen och rekonstruerar sedan den ursprungliga matrisen från de dekomponerade elementen.

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

Att köra exemplet visar först den definierade 3×2-matrisen, sedan Q- och R-elementen och slutligen den rekonstruerade matrisen som stämmer överens med det vi började med.

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

Cholesky-dekomposition

Cholesky-dekompositionen gäller för kvadratiska symmetriska matriser där alla egenvärden är större än noll, så kallade positivt bestämda matriser.

För våra intressen inom maskininlärning kommer vi att fokusera på Cholesky-dekompositionen för realvärdesmatriser och bortse från fallen när vi arbetar med komplexa tal.

Dekompositionen definieras på följande sätt:

1
A = L . L^T

Och utan punktnotering:

1
A = LL^T

Varvid A är matrisen som ska delas upp, L är den nedre triangulära matrisen och L^T är transponeringen av L.

Den sönderdelade matrisen kan också skrivas som produkten av den övre triangulära matrisen, till exempel:

1
A = U^T . U

Varvid U är den övre triangulära matrisen.

Cholesky-dekompositionen används för att lösa linjära minsta kvadrater för linjär regression, samt simulerings- och optimeringsmetoder.

När man dekomponerar symmetriska matriser är Cholesky-dekompositionen nästan dubbelt så effektiv som LU-dekompositionen och bör föredras i dessa fall.

Symmetriska, positivt bestämda matriser är visserligen ganska speciella, men de förekommer ganska ofta i vissa tillämpningar, så deras speciella faktorisering, kallad Cholesky-dekomposition, är bra att känna till. När du kan använda den är Cholesky-dekomposition ungefär en faktor två snabbare än alternativa metoder för att lösa linjära ekvationer.

– Sida 100, Numeriska recept: The Art of Scientific Computing, Third Edition, 2007.

Cholesky-dekompositionen kan implementeras i NumPy genom att anropa funktionen cholesky(). Funktionen returnerar endast L eftersom vi enkelt kan få tillgång till L transponeringen vid behov.

Exemplet nedan definierar en 3×3 symmetrisk och positivt bestämd matris och beräknar Cholesky-dekompositionen, varefter den ursprungliga matrisen rekonstrueras.

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

Att köra exemplet visar först den symmetriska matrisen, sedan den nedre triangulära matrisen från dekompositionen följt av den rekonstruerade matrisen.

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

Utvidgningar

Det här avsnittet listar några idéer för att utvidga handledningen som du kanske vill utforska.

  • Skapa 5 exempel där du använder varje operation med dina egna data.
  • Sök i artiklar om maskininlärning och hitta 1 exempel där varje operation används.

Om du utforskar någon av dessa utvidgningar vill jag gärna veta.

Fortsatt läsning

Det här avsnittet innehåller fler resurser om ämnet om du vill gå djupare.

Böcker

  • Avsnitt 6.6 Matrisdekompositioner. No Bullshit Guide To Linear Algebra, 2017.
  • Föreläsning 7 QR Factorization, Numerical Linear Algebra, 1997.
  • Avsnitt 2.3 LU Decomposition and Its Applications, Numerical Recipes: The Art of Scientific Computing, Third Edition, 2007.
  • Avsnitt 2.10 QR-dekomposition, Numerical Recipes: The Art of Scientific Computing, Third Edition, 2007.
  • Avsnitt 2.9 Cholesky-dekomposition, numeriska recept: The Art of Scientific Computing, Third Edition, 2007.
  • Föreläsning 23, Cholesky Decomposition, Numerical Linear Algebra, 1997.

API

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

Artiklar

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

Resumé

I denna handledning, upptäckte du matrisdekompositioner och hur man beräknar dem i Python.

Specifikt har du lärt dig:

  • Vad en matrisdekomposition är och varför dessa typer av operationer är viktiga.
  • Hur man beräknar en LU- ochQR-matrisdekomposition i Python.
  • Hur man beräknar en Cholesky-matrisdekomposition i Python.

Har du några frågor?
Sätt dina frågor i kommentarerna nedan så ska jag göra mitt bästa för att svara.

Hantera linjär algebra för maskininlärning!

Linjär algebra för maskininlärning

Utveckla en fungerande förståelse av linjär algebra

…genom att skriva rader av kod i python

Upptäck hur i min nya Ebook:
Linear Algebra for Machine Learning

Den innehåller självstudier om ämnen som:
Vektornormer, matrismultiplikation, tensorer, Eigendekomposition, SVD, PCA och mycket mer…

Finnally Understand the Mathematics of Data

Skippa det akademiska. Bara resultat.

Se vad som finns inuti

Tweet Share Share Share

By: adminPosted on

Lämna ett svar

Din e-postadress kommer inte publiceras.