Karakteristieke Vergelijking: Alles wat je moet weten voor Data Science

Met de explosieve groei in de beschikbaarheid van data en machinelearning-technieken heeft lineaire algebra een fundamentele plek gekregen in de wiskunde van machine learning en data science. Aspirant-ML- en data scientists hebben daarom veel baat bij het leren van kernbegrippen uit de lineaire algebra, waaronder vectoren en matrices, hun eigenschappen en de gangbare bewerkingen daarop.

Ik raad je aan onze cursus Linear Algebra for Data Science in R te volgen om een sterke wiskundige basis voor data science en machine learning op te bouwen. In de cursus ga je lineaire algebra waarderen als een mooi en interessant vakgebied dat algebra en meetkunde samenbrengt (via lijnen, vlakken en volumes). Je ziet met name hoe hoog-dimensionale data zich goed laten weergeven als vectorobjecten (zoals tekst, afbeeldingen, audio en features), en hoe deze wiskundige objecten als vectoren brede toepassingen hebben in wetenschap en techniek, zoals natuurkunde, statistiek en informatica.

In dit artikel kijken we van dichtbij naar een van de fundamentele objecten in de lineaire algebra: de matrix. Net als andere wiskundige objecten hebben matrices kenmerken die hen typeren. In het bijzonder bespreek en presenteer ik één typerend kenmerk van een vierkante matrix: het karakteristieke polynoom of de karakteristieke vergelijking. Laten we eens kijken.

Definitie van de karakteristieke vergelijking

Een polynoom is een functie met onbekenden tot en met macht n. De onbekende wordt meestal aangeduid met de letter x, maar in specifieke gevallen wordt een andere notatie gebruikt, zoals de Griekse letter 𝝀 (lambda), die we ook zullen gebruiken in onze notatie. Het karakteristieke polynoom van een vierkante matrix A ∈R^n×n met onbekende 𝝀 wordt gedefinieerd als:

Waar det(.) de determinant is van een vierkante matrix en I de identiteitsmatrix is. 

Als we dit karakteristieke polynoom gelijk aan nul zetten (om op te lossen voor 𝝀), noemen we dat de karakteristieke vergelijking. De wortels van deze polynoomvergelijking heten de eigenwaarden; dit zijn belangrijke begrippen in matrixtransformaties en machine learning (bijv. dimensiereductie). Als je eigenvectoren en eigenwaarden wilt opfrissen, hebben we een tutorial over dit onderwerp: Eigenvectors and Eigenvalues: Key Insights for Data Science.

Afleiden en berekenen van de karakteristieke vergelijking

We laten zien hoe een karakteristiek polynoom wordt opgesteld voor een 2x2-vierkante matrix A, waarbij:

Uit de definitie van een karakteristiek polynoom volgt:

Daarom is het karakteristieke polynoom voor de bovenstaande matrix A gelijk aan p_A(𝝀)=𝝀²-7𝝀+10. We kunnen de wortels van dit polynoom vinden door het aan nul gelijk te stellen.

De karakteristieke vergelijking gebruiken om eigenwaarden en eigenvectoren te vinden

Een karakteristiek polynoom van een vierkante matrix bevat belangrijke kenmerken van de bijbehorende matrix, waaronder de eigenwaarden en de determinant. Daarom kun je eigenwaarden uit een karakteristiek polynoom halen door op te lossen naar de onbekende. We illustreren het proces om eigenwaarden te vinden uit het karakteristieke polynoom voor de bovenstaande 2x2-vierkante matrix A. Zoals we lieten zien, is het karakteristieke polynoom voor deze matrix:

Om de eigenwaarde(n) te vinden, stellen we dit polynoom gelijk aan nul en zoeken we de wortels met algebraïsche (of computationele) methoden:

Dus de eigenwaarden zijn 𝝀₁=5 en 𝝀₂=2 (eigenwaarden worden conventioneel in aflopende volgorde vermeld, omdat ze de hoeveelheid informatie in bepaalde datamatrices weerspiegelen). De verzameling van alle eigenwaarden van een matrix heet het eigenspectrum of het spectrum van die matrix. Uit eigenwaarden kunnen we de eigenvectoren van een matrix afleiden in de nulruimte met (A- 𝝀I)x=0 voor elke eigenwaarde:

Voor 𝝀₁=5 vullen we 5 in en lossen we het homogene stelsel vergelijkingen op:

Dit levert een eendimensionale (d.w.z. één basisvector) eigenruimte op. We voeren hetzelfde proces uit voor 𝝀₂=2 en krijgen:

In dit voorbeeld hebben we twee verschillende eigenwaarden. Een matrix kan ook meerdere herhaalde, identieke eigenwaarden hebben, wat een meerdimensionale (d.w.z. meerdere basisvectoren) eigenruimte oplevert. In dat geval heet de dimensionaliteit van de door verschillende eigenvectoren opgespannen eigenruimte de geometrische multipliciteit van de eigenwaarde i. 

Het aantal keren dat een eigenwaarde van een matrix voorkomt, heet de algebraïsche multipliciteit. Een van de interessantste toepassingen van eigenwaarden en eigenvectoren is waarschijnlijk het PageRank-algoritme dat Google gebruikt voor het rangschikken van zoekresultaten op belangrijkheid. Onze cursus Predictive Analytics using Networked Data in R bevat een interessant hoofdstuk over het PageRank-algoritme als je meer wilt weten. 

Computationele technieken

Een karakteristiek polynoom is in feite een wiskundig polynoom met speciale eigenschappen (bijv. het bevat de spoor, de determinant en de eigenwaarden van een vierkante matrix). Het vinden van de wortels van de karakteristieke vergelijking wordt daardoor omslachtig bij hogere graden n. 

Bovendien vereist het afleiden van het karakteristieke polynoom dat je de determinant van de vierkante matrix berekent. Hoewel we om didactische redenen een voorbeeld en methode hebben gegeven om het karakteristieke polynoom op papier en met de hand af te leiden en op te lossen, worden in echte data science-toepassingen numerieke (computationele) methoden gebruikt om de wortels van een karakteristiek polynoom te berekenen of te benaderen. Laplace-expansie, Gauss-eliminatie en QR-decomposities zijn enkele methoden die numeriek de determinant kunnen vinden. 

Voor het vinden van de wortels van het karakteristieke polynoom zijn gangbare algoritmen onder andere de methode van Newton-Raphson, bisectie, de secansmethode en de methode van Müller.

Toepassingen van de karakteristieke vergelijking

Eigenwaarden en eigenvectoren zijn fundamentele wiskundige kenmerken van matrices die kunnen worden afgeleid uit een karakteristieke vergelijking van een vierkante matrix. In de statistiek en machine learning worden karakteristieke vergelijkingen gebruikt voor verschillende algoritmen die gebaseerd zijn op eigenwaarden en die worden toegepast voor dimensiereductie en informatie-extractie, zoals:

• Principal Component Analysis (PCA) en dimensiereductie, waarbij een dataset wordt teruggebracht tot een kleiner aantal vectoren op basis van de waarden van de gevonden eigenwaarden.
• Spectral clustering, een techniek die is gebaseerd op het eigenspectrum van de similariteitsmatrix van een dataset om de datadimensionaliteit te verkleinen als stap vóór het uitvoeren van clusteralgoritmen zoals k-means.
• Graftheorie en netwerkanalyse, waar eigenwaarden en eigenvectoren worden gebruikt om een graaf in gemeenschappen (hoofdcomponenten) op te splitsen, de graaf in te bedden in een ruimte met lagere dimensie voor visualisatie, en spectrale versporing om een graaf te benaderen met een vergelijkbaar eigenspectrum.
• Tijdreeksen, waar singular spectrum analysis wordt gebruikt om onderliggende patronen in de reeks te ontdekken, zoals trends, cycli en afwijkingen.

Eigenschappen van het karakteristieke polynoom

Als wiskundig object heeft een karakteristiek polynoom enkele interessante eigenschappen, waaronder:

• Monisch: De leidende coefficient van een karakteristiek polynoom is altijd één (monisch).
• Graad: De graad n van een karakteristiek polynoom is altijd gelijk aan de afmeting van de bijbehorende n×n-matrix.
• Invariantie onder matricesimilariteit: Als we een matrix transformeren en het resultaat is een vergelijkbare (similaire) matrix, dan hebben beide een identiek karakteristiek polynoom (d.w.z. de getransformeerde similaire matrix behoudt het oorspronkelijke karakteristieke polynoom).
• Coëfficiënten: De eerste leidende term van het karakteristieke polynoom is de determinant van de bijbehorende matrix, en de voorlaatste coëfficiënt is het ongetekende spoor (trace) van de bijbehorende matrix c₀=det(A) en c_n-1=-1^n-1tr(A)
• Als we in het karakteristieke polynoom elke onbekende vervangen door de oorspronkelijke vierkante matrix, resulteert dat in de nulmatrix (stelling van Cayley-Hamilton). Met andere woorden: het karakteristieke polynoom is een vernietigend (annihilerend) polynoom voor de vierkante matrix. In deze vorm kunnen de eigenwaarden direct uit de vierkante matrix worden afgeleid. Dienovereenkomstig kan worden gesteld dat elke vierkante matrix voldoet aan zijn eigen karakteristieke vergelijking.

Verdiepende onderwerpen

Tot slot geef ik graag nog een paar meer gevorderde details over karakteristieke polynomen en matrixeigenschappen als extra inkijkje in de wiskunde, maar zonder uitgebreide uitwerking.

• Minimaal polynoom: Een monisch polynoom dat nauw verwant is aan het karakteristieke polynoom is het minimale polynoom: het polynoom met de laagst mogelijke positieve graad dat de vierkante matrix A vernietigt. Omdat een karakteristiek polynoom zijn vierkante matrix ook kan vernietigen, kan het minimale polynoom uit zo’n karakteristiek polynoom worden afgeleid.
• Similariteit en diagonalisatie: Twee matrices zijn similar als ze met elkaar verbonden zijn via één gemeenschappelijke lineaire transformatie. Als twee matrices similar zijn, hebben ze ook dezelfde rang, spoor, determinant, eigenwaarden, karakteristiek polynoom en minimale polynomen. 
• Karakteristieke vergelijking van matrixmachten en -functies: Bij een matrixmacht worden de eigenwaarden tot de k-de macht verheven van de matrix A^k en wordt het bijbehorende karakteristieke polynoom afgeleid als det(A^k-λI). Voor een matrixfunctie f(x) kan het karakteristieke polynoom worden afgeleid door f() te evalueren op de eigenwaarden van A.

Conclusie

In dit artikel hebben we het karakteristieke polynoom besproken en gezien hoe het belangrijke eigenschappen van een vierkante matrix omvat, zoals de eigenwaarden, het spoor en de determinant. Gezien de belangrijke rol van eigenwaarden in data science en machine learning, helpt begrip van de karakteristieke vergelijking ons sterk bij het begrijpen hoe ML- en statistische algoritmen de hoofdcomponenten uit een datamatrix halen om patronen te vinden en de rekenefficiëntie te verbeteren.

Als je meer wilt lezen over andere belangrijke en bekende vergelijkingen in data science en machine learning, bekijk dan onze Normal Equation for Linear Regression Tutorial. DataCamp heeft ook uitstekende cursussen voor een complete en gestructureerde leerroute, zoals onze cursus Linear Algebra for Data Science in R, die ik eerder noemde en zeker aanbeveel.