psych 421

deefer

Chapter5.2_Single-layernetworksandBooleanfunctions-revisedfor3rdedition.ppt

Home >Psychology homework help >psych 421

Chapter 5.2:
Single-layer networks and Boolean functions

Cognitive Science  José Luis Bermúdez / Cambridge University Press 2020

Overview

Introduce single unit networks and Boolean functions

Introduce Hebbian learning

Introduce the perceptron convergence rule and linear separability

Explain the limits of learning in single unit networks

Cognitive Science  José Luis Bermúdez / Cambridge University Press 2020

Single-unit networks as logic gates

• Single-unit networks can function as logic gates

• They can compute basic binary Boolean functions

• Because of this, networks of single-unit networks can compute any Boolean function whatsoever

Cognitive Science  José Luis Bermúdez / Cambridge University Press 2020

Boolean functions

• Named after the mathematician and logician George Boole - inventor of Boolean algebra, Boolean functions etc etc

• Functions from sets of truth values to truth values

Truth values are TRUE and FALSE

• Boolean functions can be of any (finite) arity

0-ary function (e.g. the TRUE)

1-ary function (e.g. NOT)

binary function (e.g. AND)

Cognitive Science  José Luis Bermúdez / Cambridge University Press 2020

Functions

• Mappings from a domain of objects into a range

• For Boolean functions the domain is made up of (tuples of) truth values

– Binary Boolean functions: the domain is all the different possible pairs of truth values

• For Boolean functions the range is always the same

– The set {TRUE, FALSE}

Cognitive Science  José Luis Bermúdez / Cambridge University Press 2020

Boolean functions

• Boolean functions can be represented by truth tables

• AND, NOT, and OR are all Boolean functions

• Every Boolean function can be represented by a formula in disjunctive normal form

A	B	A AND B
FALSE	FALSE	FALSE
FALSE	TRUE	FALSE
TRUE	FALSE	FALSE
TRUE	TRUE	TRUE

Cognitive Science  José Luis Bermúdez / Cambridge University Press 2020

Single unit networks

• If we represent TRUE by 1 and FALSE by 0 then we can use single-unit networks to represent Boolean functions

• The arity of the function is given by the number of inputs to the unit

• The weights, activation functions, and threshold need to be set so that the output is always 1 or 0

• use a binary threshold activation function

Cognitive Science  José Luis Bermúdez / Cambridge University Press 2020

OR-Network

W1 = 1

T = 1

T=1

W1=1

W2=1

The “neuron” will fire in every case except where both inputs are 0.

Cognitive Science  José Luis Bermúdez / Cambridge University Press 2020

This is a fill-in-the-blank for an OR gate.

Cognitive Science  José Luis Bermúdez / Cambridge University Press 2020

Learning in neural networks

• Neural networks are important because they allow us to model how information-processing capacities are learnt

• If we abstract away from learning, networks of single unit networks are simply implementations of symbolic systems

• Two types of learning

Supervised [requires feedback]

Unsupervised [no feedback]

Cognitive Science  José Luis Bermúdez / Cambridge University Press 2020

Unsupervised learning

• Simplest algorithms for unsupervised learning are forms of Hebbian learning

• Basic principle: Neurons that fire together, wire together

• “When an axon of a cell A is near enough to excite call B or repeatedly or persistently takes part in firing it, some growth or metabolic change takes place in both cells such that A’s efficiency, as one of the cells firing B, is increased.”

Cognitive Science  José Luis Bermúdez / Cambridge University Press 2020

Hebbian learning

• Standardly used in pattern associator networks

• Very good at generalizing patterns

• Also feature in more complex learning rules (e.g. competitive learning)

• Simple formal expression: w12 =  x a1 x a2

Cognitive Science  José Luis Bermúdez / Cambridge University Press 2020

Perceptron convergence rule

• Also known as the delta rule

• Distinct from Hebbian learning in that training depends upon the discrepancy between actual output and intended output

 = error measure

(Intended output – actual output)

Cognitive Science  José Luis Bermúdez / Cambridge University Press 2020

Applying the delta rule

Delta rule gives algorithm for changing threshold and weights as a function of  and  (a learning rate constant

T = –  �x 

Wi =  �x  x Ii

Cognitive Science  José Luis Bermúdez / Cambridge University Press 2020

Perceptron convergence theorem

The perceptron convergence rule will converge on a solution in every case where a solution is possible

i.e. it will generate a set of weights and a threshold that will compute every Boolean function that can be computed by a perceptron (i.e. a single layer network)

But which functions are those?

Cognitive Science  José Luis Bermúdez / Cambridge University Press 2020

Linearly separable functions

Notion of linear separability can be extended to cover n-ary Boolean functions for n > 2

Cognitive Science  José Luis Bermúdez / Cambridge University Press 2020

XOR is linearly separable

• Network must output 1 when I2=1

• So we have 1 x W2 > T

• Likewise, the network must output 1 when I1 =1

• So we have 1 x W1 > T

• But then we must have (1xW1)+(1xW2)>T

• So the network will output 1 when I1 and I2 are both 1

I1	I2	Output
0	0	0
0	1	1
1	0	1
1	1	0

Cognitive Science  José Luis Bermúdez / Cambridge University Press 2020

XOR network

Cognitive Science  José Luis Bermúdez / Cambridge University Press 2020