Neural Networks

AI 101

Today

  • Follow up on the adjacency matrix lab
    • I will live-code this then post my solution on the website and link it here.
  • Bipartite graphs
  • Neurons
  • Our first neural network
    • (Single layer, fully-connected)

Matrix

  • We recall matrices from the Sudoku lab.

The Adjacency Matrix

In mathematics, a matrix (pl.: matrices) is a rectangular array of numbers or other mathematical objects with elements or entries arranged in rows and columns.

\[ \begin{bmatrix}1 & 9 & -13 \\20 & 5 & -6 \end{bmatrix} \]

Indices

  • Mini-Sudoku is 4$$4.
  • General, matrices may be \(m\) by \(n\).

\[ \mathbf{A} = \begin{pmatrix} a_{11} & a_{12} & \cdots & a_{1n} \\ a_{21} & a_{22} & \cdots & a_{2n} \\ \vdots & \vdots & \ddots & \vdots \\ a_{m1} & a_{m2} & \cdots & a_{mn} \\ \end{pmatrix} \]

Indices

  • There are \(4 \times 4 = 16\) total “positions” in a Mini-Sudoku
  • Each of these 16 “positions” are either impacted or non-impacted
    • Each position is impacted by:
      • Other positions in the same row.
      • Other positions in the same column.
      • Other positions in the same \(2\times2\) submatrix

Encoding

  • Vs. refer to each as, e.g. \(a_{mn}\).
  • Just give each “position” a unique number:

Tedious

\(a_{1,1}\) \(a_{1,2}\) \(a_{1,3}\) \(a_{1,4}\)
\(a_{2,1}\) \(a_{2,2}\) \(a_{2,3}\) \(a_{2,4}\)
\(a_{3,1}\) \(a_{3,2}\) \(a_{3,3}\) \(a_{3,4}\)
\(a_{4,1}\) \(a_{4,2}\) \(a_{4,3}\) \(a_{4,4}\)

Brief

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

Example

  • Consider the top left position.
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16

Order

  • We can write these down in numerical order.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

Correspondence

  • They correspond to the following matrix positions
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
\(a_{1,1}\) \(a_{1,2}\) \(a_{1,3}\) \(a_{1,4}\) \(a_{2,1}\) \(a_{2,2}\) \(a_{2,3}\) \(a_{2,4}\) \(a_{3,1}\) \(a_{3,2}\) \(a_{3,3}\) \(a_{3,4}\) \(a_{4,1}\) \(a_{4,2}\) \(a_{4,3}\) \(a_{4,4}\)

1’s

  • We can mark adjacent positions as one (1)
    • Like this.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
1 1 1 1 1 1 1 1

0’s

  • We can mark adjacent positions as one (1)
    • And others as zero.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
1 1 1 1 1 1 0 0 1 0 0 0 1 0 0 0

Code Cells

  • We can take that last row and treat it as list.
    • Lists begin and end with boxy brackets []
    • Lists contain multiple values, like 0 or 1
    • The values are separated by commas ,
[1,1,1,1,1,1,0,0,1,0,0,0,1,0,0,0]
  • Was:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
1 1 1 1 1 1 0 0 1 0 0 0 1 0 0 0

Further

  • This corresponds to things adjancent to position “1”
  • Next, we can do things adjacent to position “2”.
    • Same submatrix, same row, different column.
[1,1,1,1,1,1,0,0,0,1,0,0,0,1,0,0]

Definition

  • We can combine each list into a list of lists
[
    [1,1,1,1,1,1,0,0,1,0,0,0,1,0,0,0],
    [1,1,1,1,1,1,0,0,0,1,0,0,0,1,0,0],
    ...
]
  • And so on.

Types of Graphs

A Type of Graph

  • We have seen a few types of graphs.
    • Amtrak
    • Dichotomous key
    • River valley
    • Sudoku

Amtrak

  • Amtrak routes. (Linear graph)

Hiawatha MKE MKE MKA MKA MKE--MKA SVT SVT MKA--SVT GLN GLN SVT--GLN CHI CHI GLN--CHI

Decision Tree

  • The decision tree. (Tree graph)

OakKey Start Leaves are smooth with no teeth or lobes? Evergreen Laves evergreen? Start->Evergreen True Bristles Lobes/teeth bristle-tipped? Start->Bristles False GrowthHabit Large Tree (not shrub)? Evergreen->GrowthHabit True LeafShape Leaves more than 3x long as wide Evergreen->LeafShape False LiveOak Southern live oak GrowthHabit->LiveOak True DwarfOak Dwarf live oak GrowthHabit->DwarfOak False WillowOak Willow oak LeafShape->WillowOak True ShingleOak Shingle oak LeafShape->ShingleOak False LobeCount6 3 or fewer lobes? Bristles->LobeCount6 True LobeCount7 9 or fewer lobes? Bristles->LobeCount7 False BlackjackOak Blackjack oak LobeCount6->BlackjackOak True RedOak Northern red oak LobeCount6->RedOak False WhiteOak White oak LobeCount7->WhiteOak True SwampOak Swamp chestnut oak LobeCount7->SwampOak False

Rivers

  • We’ll do rivers as edges. (Tree graph)

Gorge Richland Richland The Dalles The Dalles Richland--The Dalles Columbia Portland Portland The Dalles--Portland Columbia Astoria Astoria Portland--Astoria Columbia Bend Bend Bend--The Dalles Deschutes Salem Salem Salem--Portland Willamette

Mini-Sudoku (One)

  • Just the top-left’s connections.

SudokuBipartite cluster_cells C33 (3,3) D33 (3,3) C33--D33 D32 (3,2) C33--D32 D31 (3,1) C33--D31 D30 (3,0) C33--D30 D23 (2,3) C33--D23 D22 (2,2) C33--D22 D13 (1,3) C33--D13 D03 (0,3) C33--D03 C32 (3,2) C32--D33 C32--D32 C32--D31 C32--D30 C32--D23 C32--D22 D12 (1,2) C32--D12 D02 (0,2) C32--D02 C31 (3,1) C31--D33 C31--D32 C31--D31 C31--D30 D21 (2,1) C31--D21 D20 (2,0) C31--D20 D11 (1,1) C31--D11 D01 (0,1) C31--D01 C30 (3,0) C30--D33 C30--D32 C30--D31 C30--D30 C30--D21 C30--D20 D10 (1,0) C30--D10 D00 (0,0) C30--D00 C23 (2,3) C23--D33 C23--D32 C23--D23 C23--D22 C23--D21 C23--D20 C23--D13 C23--D03 C22 (2,2) C22--D33 C22--D32 C22--D23 C22--D22 C22--D21 C22--D20 C22--D12 C22--D02 C21 (2,1) C21--D31 C21--D30 C21--D23 C21--D22 C21--D21 C21--D20 C21--D11 C21--D01 C20 (2,0) C20--D31 C20--D30 C20--D23 C20--D22 C20--D21 C20--D20 C20--D10 C20--D00 C13 (1,3) C13--D33 C13--D23 C13--D13 C13--D12 C13--D11 C13--D10 C13--D03 C13--D02 C12 (1,2) C12--D32 C12--D22 C12--D13 C12--D12 C12--D11 C12--D10 C12--D03 C12--D02 C11 (1,1) C11--D31 C11--D21 C11--D13 C11--D12 C11--D11 C11--D10 C11--D01 C11--D00 C10 (1,0) C10--D30 C10--D20 C10--D13 C10--D12 C10--D11 C10--D10 C10--D01 C10--D00 C03 (0,3) C03--D33 C03--D23 C03--D13 C03--D12 C03--D03 C03--D02 C03--D01 C03--D00 C02 (0,2) C02--D32 C02--D22 C02--D13 C02--D12 C02--D03 C02--D02 C02--D01 C02--D00 C01 (0,1) C01--D31 C01--D21 C01--D11 C01--D10 C01--D03 C01--D02 C01--D01 C01--D00 C00 (0,0) C00--D30 C00--D20 C00--D11 C00--D10 C00--D03 C00--D02 C00--D01 C00--D00

Mini-Sudoku (All)

  • All connections

SudokuBipartite cluster_cells C33 (3,3) D33 (3,3) C33--D33 D32 (3,2) C33--D32 D31 (3,1) C33--D31 D30 (3,0) C33--D30 D23 (2,3) C33--D23 D22 (2,2) C33--D22 D13 (1,3) C33--D13 D03 (0,3) C33--D03 C32 (3,2) C32--D33 C32--D32 C32--D31 C32--D30 C32--D23 C32--D22 D12 (1,2) C32--D12 D02 (0,2) C32--D02 C31 (3,1) C31--D33 C31--D32 C31--D31 C31--D30 D21 (2,1) C31--D21 D20 (2,0) C31--D20 D11 (1,1) C31--D11 D01 (0,1) C31--D01 C30 (3,0) C30--D33 C30--D32 C30--D31 C30--D30 C30--D21 C30--D20 D10 (1,0) C30--D10 D00 (0,0) C30--D00 C23 (2,3) C23--D33 C23--D32 C23--D23 C23--D22 C23--D21 C23--D20 C23--D13 C23--D03 C22 (2,2) C22--D33 C22--D32 C22--D23 C22--D22 C22--D21 C22--D20 C22--D12 C22--D02 C21 (2,1) C21--D31 C21--D30 C21--D23 C21--D22 C21--D21 C21--D20 C21--D11 C21--D01 C20 (2,0) C20--D31 C20--D30 C20--D23 C20--D22 C20--D21 C20--D20 C20--D10 C20--D00 C13 (1,3) C13--D33 C13--D23 C13--D13 C13--D12 C13--D11 C13--D10 C13--D03 C13--D02 C12 (1,2) C12--D32 C12--D22 C12--D13 C12--D12 C12--D11 C12--D10 C12--D03 C12--D02 C11 (1,1) C11--D31 C11--D21 C11--D13 C11--D12 C11--D11 C11--D10 C11--D01 C11--D00 C10 (1,0) C10--D30 C10--D20 C10--D13 C10--D12 C10--D11 C10--D10 C10--D01 C10--D00 C03 (0,3) C03--D33 C03--D23 C03--D13 C03--D12 C03--D03 C03--D02 C03--D01 C03--D00 C02 (0,2) C02--D32 C02--D22 C02--D13 C02--D12 C02--D03 C02--D02 C02--D01 C02--D00 C01 (0,1) C01--D31 C01--D21 C01--D11 C01--D10 C01--D03 C01--D02 C01--D01 C01--D00 C00 (0,0) C00--D30 C00--D20 C00--D11 C00--D10 C00--D03 C00--D02 C00--D01 C00--D00

Bipartite

Definition

  • The mini-sudoku graph is a bipartite graph
    • Two collections of nodes.
    • Every edge goes from one collection to the other.
  • It just means two parts.

Examples

  • Here’s a canonical representation from Wikipedia

Simple bipartite graph; two layers

Other Bipartite Graphs

  • A common one is students-to-universities

SudokuBipartite cluster_cells C13 Just Like Normal People D13 Just Like College C13--D13 C23 Children of Professors D23 Highly Selective C23--D23 C33 Children of Presidents D33 Ivy League Peers C33--D33

Other Bipartite Graphs

  • Couples on The Breakfast Club (1985)

SudokuBipartite cluster_cells D13 Claire (Princess) C23 Brian (Brain) D13--C23 C33 Bender (Criminal) D13--C33 D23 Allison (Basket Case) C13 Andrew (Athlete) D23--C13 D23--C23

The Brain?

src

The Neuron

Neurons

  • There are biological neurons.
    • Brain cells
    • Actually exist
  • There are theoretical, machine learning or AI neurons
    • Don’t “actually” exist
    • Are simulated by computers

The basic units that receive inputs, each neuron is governed by a threshold and an activation function.

Image, UOregon

src

Neurons as Nodes

  • We can treat each cell body as a node in a graph.
    • Or train station in Amtrak.
  • We can treat each axon as an edge in graph.
    • Or train connection in Amtrak

Brains as Graphs

  • Somehow, information reaches the brain.
  • We’ll just not worry about that for now, but…
    • Touch in the hands/skins
    • Vision in the eye
    • Olfaction, temperature, etc.
  • We’ll call these sensory neurons

Example

  • We imagine, for example, a sensory neuron in each finger.

SudokuBipartite cluster_cells R5 R5 R4 R4 R3 R3 R2 R2 R1 R1 L1 L1 L2 L2 L3 L3 L4 L4 L5 L5

Regard

  • Fingers as the top, sensing layer in RED
  • Neurons in the brain as the lower, thinking layer in BLUE

SudokuBipartite cluster_cells R5 R5 B0 B0 R5--B0 R4 R4 B9 B9 R4--B9 R3 R3 B8 B8 R3--B8 R2 R2 B7 B7 R2--B7 R1 R1 B6 B6 R1--B6 L1 L1 B5 B5 L1--B5 L2 L2 B4 B4 L2--B4 L3 L3 B3 B3 L3--B3 L4 L4 B2 B2 L4--B2 L5 L5 B1 B1 L5--B1

Meaning

  • Perhaps the braincell “B3” encodes good movie
    • I usually use give two thumbs up - both “R1” and “L1”.

SudokuBipartite cluster_cells R5 R5 B0 B0 R5--B0 R4 R4 B9 B9 R4--B9 R3 R3 B8 B8 R3--B8 R2 R2 B7 B7 R2--B7 R1 R1 B6 B6 R1--B6 B3 B3 R1--B3 L1 L1 B5 B5 L1--B5 L1--B3 L2 L2 B4 B4 L2--B4 L3 L3 L3--B3 L4 L4 B2 B2 L4--B2 L5 L5 B1 B1 L5--B1

Meaning

  • Perhaps the braincell “B5” encodes “pinch of salt”
    • I usually use right thumb and index finger - R1 and R2

SudokuBipartite cluster_cells R5 R5 B0 B0 R5--B0 R4 R4 B9 B9 R4--B9 R3 R3 B8 B8 R3--B8 R2 R2 B7 B7 R2--B7 B5 B5 R2--B5 R1 R1 B6 B6 R1--B6 R1--B5 B3 B3 R1--B3 L1 L1 L1--B5 L1--B3 L2 L2 B4 B4 L2--B4 L3 L3 L3--B3 L4 L4 B2 B2 L4--B2 L5 L5 B1 B1 L5--B1

Meaning

  • Perhaps the braincell “B4” encodes “light switch”
    • I usually use an index finger - L2 or R2

SudokuBipartite cluster_cells R5 R5 B0 B0 R5--B0 R4 R4 B9 B9 R4--B9 R3 R3 B8 B8 R3--B8 R2 R2 B7 B7 R2--B7 B5 B5 R2--B5 B4 B4 R2--B4 R1 R1 B6 B6 R1--B6 R1--B5 B3 B3 R1--B3 L1 L1 L1--B5 L1--B3 L2 L2 L2--B4 L2--B4 L3 L3 L3--B3 L4 L4 B2 B2 L4--B2 L5 L5 B1 B1 L5--B1

Another example

  • Perhaps fingers and keys on the keyboard.

SudokuBipartite L5 L5 A A L5--A L4 L4 S S L4--S L3 L3 D D L3--D L2 L2 F F L2--F R2 R2 J J R2--J R3 R3 K K R3--K R4 R4 L L R4--L R5 R5 ; ; R5--;

Typing

  • This is how I learned to type!
    • Some neurons in my brain associate fingers with keys!
Finger position on a keyboard

Notes

https://en.wikipedia.org/wiki/Bipartite_graph https://www.geeksforgeeks.org/deep-learning/what-is-fully-connected-layer-in-deep-learning/ https://en.wikipedia.org/wiki/Neural_network_(machine_learning) https://www.geeksforgeeks.org/deep-learning/neural-networks-a-beginners-guide/ https://en.wikipedia.org/wiki/Perceptron