It-sikkerhed - Perceptron Algoritmen

I denne video er der en introduktion til perceptron-algoritmen og vi ser på hvordan den kan bruges på data fra facebook.

Perceptron-algoritmen i 2 dimensioner.

Vi starter med punkter i planen. Dvs punkter med 2 koordinater.

Vi forestiller os at vi har en mængde punkter med to koordinater. Disse punkter er er enten røde eller blå. Denne klassificering skal være lineært separabel, dvs der skal findes en ret linje der deler punkterne op så de røde er på den ene side af linjen og de blå punkter er på den anden side. Perceptron-algoritmen finder denne linje.

Man starter med en tilfældig linje. Tager det første punkt og undersøger om det er på den rigtige side af linjen. Hvis punktet er på den rigtige side af linjen, så gør man ikke noget. Hvis punkter er på den forkerte side af linje, så skal linjen ændres(opdateres) så punktet er på den rigtige side af den nye linje. Sådan bliver man ved indtil alle punkterne er blevet behandlet.

Vi har en funktion der hedder desided output:

(1)
\begin{align} \delta (X) = \left\{ \begin{array}{ll} +1 & \mbox{hvis $x$ er rød}\\ -1 & \mbox{hvis $x$ er blå} \end{array} \right. \end{align}

Terminologien er lidt anderledes en i er vant til fra matematik. I vores koordinatsystem hedder den vandrette akse $x_{1}$ og den lodrette akse $x_{2}$
Vi har en linje som vi starter med. Den hedder $\omega$ og er repræsenteret som en vektor med 3 koordinater.

(2)
\begin{align} \omega = \left( \begin{array}{l} \omega_{0}\\ \omega_{1}\\ \omega_{2} \end{array} \right) \end{align}

Dette repræsenterer en linje på følgende måde: $0=\omega_{0}+\omega_{1}x_{1}+\omega_{2}x_{2}$. For at udregningerne bliver ens vil vi skrive $0=\omega_{0}x_{0}+\omega_{1}x_{1}+\omega_{2}x_{2}$, hvor $x_{0}=1$.

  1. Vælg et punkt $X=(x_{1},x_{2})$ som input.
  2. Hvis den er korret klassificeret, dvs hvis $\omega_{0}x_{0}+\omega_{1}x_{1}+\omega_{2}x_{2}$ har samme fortegn som $\delta (X)$, skal der ikke gøres noget.
  3. Ellers skal $\omega$ updateres således
(3)
\begin{array} {ll} \omega_{0}&=&\omega_{0}+\eta \delta (x) x_{0}\\ \omega_{1}&=&\omega_{1}+\eta \delta (x) x_{1}\\ \omega_{2}&=&\omega_{2}+\eta \delta (x) x_{2} \end{array}
Koordinatsystem.png

hvor $\eta$ er en korrektionsfaktor.

Lad os starte på eksemplet i øvelsen.

Vi starter med en tilfældig linje:

(4)
\begin{align} \omega = \left( \begin{array}{l} 0\\ 1\\ 0.5 \end{array} \right) \end{align}

Det betyder at vores linje er $0=0+1x_{1}+0.5x_{2}$. Hvis vi isolere $x_{2}$ fås $x_{2}=-2x_{1}$. Den skærer altså den lodrette akse i 0 og har en hældningskoefficient på $-2$.
Eksemplet fortsætter i opgaven Håndkøring af perceptronalgoritmen

Perceptron-algoritmen i 3 dimensioner.

Vi har udnyttet at en linje deler planen op i to dele. Vi vil nu generalisere denne metode til 3 dimensioner.

Ligesom linjen deler planen i to dele, gælder der i rummet, at planen deler rummet i 2 dele.
Vi har sat en ekstra akse på koordinatsystemet. Den kalder vi $x_{3}$-aksen.
Vi har en plan som vi starter med. Den hedder $\omega$ og er repræsenteret som en vektor med 4 koordinater.

(5)
\begin{align} \omega = \left( \begin{array}{l} \omega_{0}\\ \omega_{1}\\ \omega_{2}\\ \omega_{3} \end{array} \right) \end{align}

Dette repræsenterer en plan på følgende måde: $0=\omega_{0}+\omega_{1}x_{1}+\omega_{2}x_{2}+\omega_{3}x_{3}$.

  1. Vælg et punkt $(x_{1},x_{2},x_{3})$ som input.
  2. Hvis den er korret klassificeret, dvs hvis $\omega_{0}x_{0}+\omega_{1}x_{1}+\omega_{2}x_{2}+\omega_{3}x_{3}$ har samme fortegn som $\delta (X)$, skal der ikke gøres noget.
  3. Ellers skal w updateres således
(6)
\begin{array} {ll} \omega_{0}&=&\omega_{0}+\eta \delta (x) x_{0}\\ \omega_{1}&=&\omega_{1}+\eta \delta (x) x_{1}\\ \omega_{2}&=&\omega_{2}+\eta \delta (x) x_{2}\\ \omega_{3}&=&\omega_{3}+\eta \delta (x) x_{3} \end{array}


hvor $\eta$ og $\delta (x)$ er helt som før.

Perceptron-algoritmen i n dimensioner.

Ligesom planen deler rummet i 2 dele gælder der i n dimensioner at en hyperplan deler det n-dimensionelle rum i to dele.
Vi har sat ekstra akser på koordinatsystemet. Den sidste kalder vi $x_{n}$-aksen, hvor $n$ er antallet af akser.
Glem alt om se en illustration over dette.
Vi har en hyperplan som vi starter med. Den hedder $\omega$ og er repræsenteret som en vektor med n koordinater.

(7)
\begin{align} \omega = \left( \begin{array}{l} \omega_{0}\\ \omega_{1}\\ \omega_{2}\\ \omega_{3}\\ \vdots \\ \omega_{n} \end{array} \right) \end{align}

Dette repræsenterer en plan på følgende måde: $0=\omega_{0}+\omega_{1}x_{1}+\omega_{2}x_{2}+\omega_{3}x_{3}+ ... + \omega_{n}x_{n}$.

  1. Vælg et punkt $(x_{1},x_{2},x_{3},...,x_{n})$ som input.
  2. Hvis den er korret klassificeret, dvs hvis $\omega_{0}x_{0}+\omega_{1}x_{1}+\omega_{2}x_{2}+\omega_{3}x_{3}...+\omega_{n}x_{n}$ har samme fortegn som $\delta (X)$, skal der ikke gøres noget.
  3. Ellers skal w updateres således
(8)
\begin{array} {ll} \omega_{0}&=&\omega_{0}+\eta \delta (x) x_{0}\\ \omega_{1}&=&\omega_{1}+\eta \delta (x) x_{1}\\ \omega_{2}&=&\omega_{2}+\eta \delta (x) x_{2}\\ \omega_{3}&=&\omega_{3}+\eta \delta (x) x_{3}\\ \vdots \\ \omega_{n}&=&\omega_{n}+\eta \delta (x) x_{n} \end{array}


hvor $\eta$ og $\delta (x)$ er helt som før.

Øvelser

Håndkøring af perceptronalgoritmen

Medmindre andet er angivet, er indholdet af denne side licenseret under Creative Commons Attribution-NonCommercial 3.0 License