Intelligent Explorer – Q-Learning Robot Navigation in a Grid

King Fahd University of Petroleum and Minerals

College of Computing and Mathematics

Computer Engineering Department

Terms 251

COE 292

Introduction to Artificial Intelligence

Topic 4.1: Artificial Neural Networks

Topic 1 COE 292 Introduction to Artificial Intelligence 2

❖ Artificial Neural Networks

❖ The Perceptron

❖ MLPs as Boolean Functions

❖ MLPs as Universal Classifiers

Outline

Topic 1 COE 292 Introduction to Artificial Intelligence 3

❖ Neural Computation is a general Machine

Learning approach that involves

processing information in a similar

manner to the networks of neurons (i.e.

Neural Networks) found in human/animal

brains

❖ Artificial Neural Networks (ANNs) are

networks of Artificial Neurons, and hence

constitute crude approximations to parts of

real brains

❖ They are massively parallel, which makes

them efficient, robust, fault and noise

tolerant

Neural Computation

Topic 1 COE 292 Introduction to Artificial Intelligence 4

❖ The information-processing units of the brain responsible for

receiving and transmitting information

❖ Neurons are connected to and receive electrical/chemical

signals from other neurons.

• dendrite: receives signals from other neurons

• Cell body (Soma): processes input

• Axon: Sends signals to other neurons

• Synapse: Transfers signals to next cell

❖ Neurons process input signals and can be activated.

Biological Neurons

Single Neuron

Soma (Cell Body)

Topic 1 COE 292 Introduction to Artificial Intelligence 5

❖ ANNs are mathematical model for learning inspired

by biological neural networks.

• Models mathematical function from inputs to outputs based on

the structure and parameters of the network.

• Allows for learning the network's parameters based on data.

❖ Neural networks have recently become central to AI

tasks like pattern recognition, prediction, and analysis.

❖ They have set new state-of-the-art benchmarks, often

surpassing previous ones significantly.

Artificial Neural Networks (ANNs)

Topic 1 COE 292 Introduction to Artificial Intelligence 6

❖ We can model a single neuron mathematically by

using a perceptron as shown below:

❖ W will be adjusted by some learning rule

❖ F is chosen by the designer

Mathematically Modeling of a single neuron

Topic 1 COE 292 Introduction to Artificial Intelligence 7

❖ The perceptron outputs 1, “Fires”, if the weighted sum of inputs (linear

transform) greater or equal a threshold T.

❖ A threshold function can be redefined so that the threshold is always at zero

A threshold unit “Fires” if the weighted sum

of inputs and the bias b is non-negative

The Perceptron

𝑓 𝑧 = ቊ 1 𝑖𝑓 𝑧 ≥ 𝑇

0 𝑜𝑡ℎ𝑒𝑟𝑤𝑖𝑠𝑒 where 𝑧 = σ𝑖=1

𝑛 𝑥𝑖𝑤𝑖

𝑓 𝑧 = ቊ 1 𝑖𝑓 𝑧 ≥ 0 0 𝑜𝑡ℎ𝑒𝑟𝑤𝑖𝑠𝑒

where 𝑧 = ෍

𝑖=1

𝑛

𝑥𝑖𝑤𝑖 − 𝑇 = ෍

𝑖=1

𝑛

𝑥𝑖𝑤𝑖 + 𝑏 𝑇 ≡

𝑏

𝑏 = −𝑇

Topic 1 COE 292 Introduction to Artificial Intelligence 8

❖ Compute the output of the following perceptron given that

(𝑥1, 𝑥2) = (2,3), (𝑤1, 𝑤2) = (3,1), and T is 1.5

❖ Answer:

Pop-up Question

𝑥1

1.5

3

𝑦

x2

1

Topic 1 COE 292 Introduction to Artificial Intelligence 9

❖ Compute the output of the following perceptron given that

(𝑥1, 𝑥2) = (2,3), (𝑤1, 𝑤2) = (3,1), and b is -1.5

❖ Answer:

Pop-up Question

𝑥1

−1.5

3

𝑏

𝑦

x2

1

Topic 1 COE 292 Introduction to Artificial Intelligence 10

❖ The activation function can be divided into two types

• Nondifferentiable Activation Function : e.g. threshold function

• Differentiable Activation Function; often non-linear

❖ The Activation Function is used at the output which normalizes

the output to a range of values and helps the network learn

complex data

❖ Examples of Differentiable functions are:

• ReLU: 𝑓 𝑥 = max(0, 𝑥)

• Sigmoid

• Tanh

• Softplus

• Rectifier

• …

The Perceptron

Softplus

Topic 1 COE 292 Introduction to Artificial Intelligence 11

❖ Compute the output of the following perceptron given that

(𝑥1, 𝑥2) = (2,3), (𝑤1, 𝑤2) = (3,1), and b is -1.5 if the

activation functions used is ReLU?

A. ReLU function

❖ Answer:

Pop-up Question

𝑥1

−1.5

3

𝑏

𝑦

x2

1

Y = 7.5

Topic 1 COE 292 Introduction to Artificial Intelligence 12

❖ Perceptron with Threshold 𝑇 • Takes an input vector 𝑋 = [𝑥1, 𝑥2, … , 𝑥𝑛]

• Applies weights to them: 𝑊 = [𝑤1, 𝑤2, … , 𝑤𝑛]

• Computes a weighted sum:

• Passes this through a threshold function

❖ Perceptron with Bias

• Computes a weighted sum

• a bias term b is added to the sum

• Passes this through an activation (e.g. Threshold ) function

Perceptron so far

𝑓 𝑧 = ቊ 1 𝑖𝑓 𝑧 ≥ 𝑇

0 𝑜𝑡ℎ𝑒𝑟𝑤𝑖𝑠𝑒

𝑧 = 𝑊. 𝑋 = σ𝑖=1 𝑛 𝑥𝑖𝑤𝑖

≥ 𝑇

≥ 0

𝑓 𝑧 = ቊ 1 𝑖𝑓 𝑧 ≥ 0

0 𝑜𝑡ℎ𝑒𝑟𝑤𝑖𝑠𝑒

𝑧 = 𝑊. 𝑋 + 𝑏 = σ𝑖=1 𝑛 𝑥𝑖𝑤𝑖 + 𝑏

𝑏 = −𝑇

Topic 1 COE 292 Introduction to Artificial Intelligence 13

Pop-up Question

𝑏 = −1

𝑤1𝑥1 + 𝑤2𝑥2 + 𝑤3𝑥3 + 𝑤4𝑥4 ≥ 1

𝑤1𝑥1 + 𝑤2𝑥2 + 𝑤3𝑥3 + 𝑤4𝑥4 − 1 ≥ 0

1 ∗ 2 + 2 ∗ −1 + −1 ∗ 1 + 3 ∗ 1 ≥ 1

2 ≥ 1

1

1 ∗ 2 + 2 ∗ −1 + −1 ∗ 1 + 3 ∗ 1 − 1 ≥ 0

1 ≥ 0

1

Application of MLP as function approximator

Topic 1 COE 292 Introduction to Artificial Intelligence 15

❖ Boolean functions are described by expressions that

consist of:

• Boolean constants: 0 (false) and 1 (true)

• Boolean variables, such as: 𝑥, 𝑦, etc.

• Boolean operators: AND (), OR (∨), NOT ( , ¯ ), XOR()

• Parentheses: to group parts of expressions and control precedence

❖ Example:

• 𝑓 = 𝑥  𝑦 ∨ ഥ𝑤𝑧

• 𝑓 = 𝑥  𝑦 ∨ ഥ𝑤𝑧

Boolean Functions

Operator Precedence

( ) 0

 1

⋀ 2

∨ 3

Topic 1 COE 292 Introduction to Artificial Intelligence 16

❖ A truth table can represent a Boolean function

• List all possible combinations of 0's and 1's assigned to input

variables

❖ If n input variables, then 2n rows

Boolean Functions Representation

x1 x2

0 0

0 1

1 0

1 1

x1 x2 x3

0 0 0

0 0 1

0 1 0

0 1 1

1 0 0

1 0 1

1 1 0

1 1 1

x1 x2 x3 x4

0 0 0 0

0 0 0 1

0 0 1 0

0 0 1 1

0 1 0 0

0 1 0 1

0 1 1 0

0 1 1 1

1 0 0 0

1 0 0 1

1 0 1 0

1 0 1 1

1 1 0 0

1 1 0 1

1 1 1 0

1 1 1 1

# rows = 22 = 4 # rows = 23 = 8 # rows = 24 = 16

Topic 1 COE 292 Introduction to Artificial Intelligence 17

❖ A truth table can represent a Boolean function

❖ If n variables, then 2n rows

❖ The following truth tables define:

• 𝐴  𝐵,

• 𝐴 ∨ 𝐵,

• 𝐴  𝐵

• 𝐴

Truth Table

Not 𝑨 ∨ 𝑩𝑨  𝑩 𝑨𝑩

𝐴𝐴

x1 x2 x3 X1x2x3

0 0 0 0

0 0 1 0

0 1 0 0

0 1 1 0

1 0 0 0

1 0 1 0

1 1 0 0

1 1 1 1

Topic 1 COE 292 Introduction to Artificial Intelligence 18

❖ ¬(𝑝 ∧ 𝑞) ≡ ¬𝑝 ∨ ¬𝑞, [first law] ¬(𝑝 ∨ 𝑞) ≡ ¬𝑝 ∧ ¬𝑞, [second law]

❖ When applying De Morgan’s laws on compound propositional expressions, make sure to put brackets first around and operators

De Morgan’s Laws

• Example:

◦ ¬ (p ∧ q V r ∧ s)

◦ ≡ ¬((p ∧ q) V (r ∧ s))

◦ ≡ ¬(p ∧ q) ∧ ¬ (r ∧ s)

◦ ≡ (¬p V ¬q) ∧ (¬r V ¬s)

p q ¬p ¬q (p ∨q)

F F T T F

F T T F T

T F F T T

T T F F T

¬(p ∨q)

T

F

F

F

¬p ∧¬q

T

F

F

F

Proof: ¬(𝑝 ∨ 𝑞) ≡ ¬𝑝 ∧ ¬𝑞

Topic 1 COE 292 Introduction to Artificial Intelligence 19

❖ Build the truth table for the following Boolean

function f = p∨ (p∧ q )

Popup-Question

p q p ∧ q p ∨ (p∧ q )

F F

F T

T F

T T

Topic 1 COE 292 Introduction to Artificial Intelligence 20

❖ The perceptron can mimic primitive Boolean gates

• AND ( X  Y )

Perceptron: Universal AND Gate

X1

X2

X3

2

1

1

-1

Threshold is # Non-inverted variables

𝑦 = 𝑥1 ∧ 𝑥2

𝑦 = 𝑥1 ∧ 𝑥2

𝑦 = 𝑥1 ∧ 𝑥2

𝑦 = 𝑥1 ∧ 𝑥2

Topic 1 COE 292 Introduction to Artificial Intelligence 21

❖ The perceptron can mimic primitive Boolean gates

• AND ( X  Y )

Perceptron: AND Gate



𝑥 + 𝑦 − 2 ≥ 0

T and w * c

x  y

Topic 1 COE 292 Introduction to Artificial Intelligence 22

❖ The perceptron can mimic primitive Boolean gates

• OR ( X  Y )

Perceptron: Universal OR Gate

X1

X2

X3

0

1

1

-1 1-1 = 0

Threshold is 1- #inverted variables

𝑦 = 𝑥1 ∨ 𝑥2

𝑦 = 𝑥1 ∨ 𝑥2

𝑦 = 𝑥1 ∨ 𝑥2

𝑦 = 𝑥1 ∨ 𝑥2

Topic 1 COE 292 Introduction to Artificial Intelligence 23

❖ The perceptron can mimic primitive Boolean gates

• OR ( X  Y )

Perceptron: OR Gate

Output

y=x1˅ x2

In p

u ts

x1

x2



Threshold

1

Neuron



𝑿 ∨ 𝒀

𝑥 + 𝑦 − 1 ≥ 0

Topic 1 COE 292 Introduction to Artificial Intelligence 24

❖ The perceptron can mimic primitive Boolean gates

• NOT

Perceptron: Not Gate



Topic 1 COE 292 Introduction to Artificial Intelligence 25

Pop-up Question

Topic 1 COE 292 Introduction to Artificial Intelligence 26

Pop-up Question

Topic 1 COE 292 Introduction to Artificial Intelligence 27

❖ No solution for XOR gate using single perceptron!!

Perceptron: XOR

Topic 1 COE 292 Introduction to Artificial Intelligence 28

❖ According to the truth table:

• 𝑥 ⊕ 𝑦 = (𝑥 ∨ 𝑦) ∧ ( ҧ𝑥 ∨ ത𝑦)

• 𝑥 ⊕ 𝑦 = (𝑥 + 𝑦) ∗ ( ҧ𝑥 + ത𝑦)

• 𝑥 ⊕ 𝑦 = ( ҧ𝑥 ∧ 𝑦) ∨ (𝑥 ∧ ത𝑦)

• 𝑥 ⊕ 𝑦 = ҧ𝑥𝑦 + 𝑥 ത𝑦

MLP: XOR

( ҧ𝑥 ∧ 𝑦) ∨ (𝑥 ∧ ത𝑦)

+: means OR

* : means AND

(X ∨ Y) ∧ (¬X ∨ ¬Y)

𝑓 𝑧

𝑓 𝑧

𝑓 𝑧 = ቊ 1 𝑧 ≥ 2 0 𝑜𝑡ℎ𝑒𝑟𝑤𝑖𝑠𝑒

𝑓 𝑧 = ቊ 1 𝑧 ≥ 1 0 𝑜𝑡ℎ𝑒𝑟𝑤𝑖𝑠𝑒

A sum (OR) of multiple products (ANDs) of variables.

A product (AND) of multiple sums (ORs) of variables.

Topic 1 COE 292 Introduction to Artificial Intelligence 29

❖ MLP are composed of networks of neurons called perceptrons.

❖ They consist of:

• An input layer:

▪ inputs are real or Boolean values, problem-based

• Multiple hidden layers

• An output layer:

▪ Outputs are real or Boolean values, problem-based

❖ Every neuron in a layer is connected to every other neuron in the next layer.

• For fully connected network, The connections (weights) between a layer with n neurons and m neurons is n*m.

❖ Can have multiple outputs for a single input

❖ “depth” in a network is the length of the longest path from a source to a sink

The Multi-Layer Perceptron (MLP)

Topic 1 COE 292 Introduction to Artificial Intelligence 30

❖ MLPs can compute any Boolean function since they can

emulate individual gates

❖ Design a single hidden layer MLP to model the Boolean expression

given below, assuming simple perceptron: 𝑜𝑢𝑡𝑝𝑢𝑡 = 1 𝑖𝑓 σ𝑖 𝑤𝑖𝑥𝑖 + 𝑏𝑖 ≥ 0. Clearly show the used weights and biases.

❖ Note that b = -T

MLPs as Boolean Functions

Y = A  B  D V ¬C  D

?

Topic 1 COE 292 Introduction to Artificial Intelligence 31

❖ Which Boolean function does the following MLP

represent?

Pop-up Question

𝑓2 𝑧 = ቊ 1 𝑧 ≥ 0.5 0 𝑜𝑡ℎ𝑒𝑟𝑤𝑖𝑠𝑒

𝑓1 𝑧 = ቊ 1 𝑧 ≥ 1.5 0 𝑜𝑡ℎ𝑒𝑟𝑤𝑖𝑠𝑒

𝑓1 𝑧 𝑓2 𝑧

Temp

𝒙 𝒚 𝑻𝒆𝒎𝒑 = 𝒙 + 𝒚 ≥ 𝟏. 𝟓 𝒙 + 𝒚 − 𝟐𝑻𝒆𝒎𝒑 ≥ 𝟎. 𝟓

0 0 𝟎 + 𝟎 ≥ 𝟏. 𝟓 → 𝟎 𝟎 + 𝟎 − 𝟐 ∗ 𝟎 ≥ 𝟎. 𝟓 → 𝟎

0 1 𝟎 + 𝟏 ≥ 𝟏. 𝟓 → 𝟎 𝟎 + 𝟏 − 𝟐 ∗ 𝟎 ≥ 𝟎. 𝟓 → 𝟏

1 0 𝟏 + 𝟎 ≥ 𝟏. 𝟓 → 𝟎 𝟏 + 𝟎 − 𝟐 ∗ 𝟎 ≥ 𝟎. 𝟓 → 𝟏

1 1 𝟏 + 𝟏 ≥ 𝟏. 𝟓 → 𝟏 𝟏 + 𝟏 − 𝟐 ∗ 𝟏 ≥ 𝟎. 𝟓 → 𝟎

𝑻𝒆𝒎𝒑 = 𝒘𝟏𝒙 + 𝒘𝟐𝒚 ≥ 𝟏. 𝟓 𝒘𝟏𝒙 + 𝒘𝟐𝒚 + 𝒘𝟑𝐓𝐞𝐦𝐩 ≥ 𝟎. 𝟓

Topic 1 COE 292 Introduction to Artificial Intelligence 32

Pop-up Questions

Topic 1 COE 292 Introduction to Artificial Intelligence 33

❖ A one-hidden-layer MLP is a Universal Boolean Function

• It can represent any function by expressing it in terms of the input

conditions that make the function true

MLPs as Boolean Functions

Note: 1. ¬𝑋 = ത𝑋 2. 𝑋1 ∧ 𝑋2 = 𝑋1𝑋2

3. 𝑋1 ∨ 𝑋2 = 𝑋1 + 𝑋2

Hints:

1. In truth tables always look for output

equal to “1”

2. The output Y is the sum of terms that

have “1” in the truth table of Y

3. To represent a term in the output

equation, put ¬𝑋𝑖 for all values of 𝑋𝑖

equal to zero and 𝑋𝑖 for all values

that correspond to one

Row 1

Row 2

A sum (OR) of multiple products (ANDs) of variables.

A product (AND) of multiple sums (ORs) of variables.

Topic 1 COE 292 Introduction to Artificial Intelligence 34

Pop-up Question

? Min

Topic 1 COE 292 Introduction to Artificial Intelligence 35

❖ Recall XOR implementation:

• An XOR needs 3 perceptrons with 2 layers per XOR

❖ XORing of 𝑁 variables – results in truth table of 2𝑁−1

product terms (i.e. 1’s) that cannot be reduced.

❖ The width of a single hidden-layer Boolean MLP with

𝑁 inputs requires 2𝑁−1 perceptrons in hidden layer

(Exponential in 𝑁)

MLPs as Boolean Functions: The XOR Function

With one hidden layer: 2𝑁−1 + 1 perceptrons

A B C D A  B  C  D

0 0 0 0 0 0 0 0 1 1 0 0 1 0 1 0 0 1 1 0 0 1 0 0 1 0 1 0 1 0 0 1 1 0 0 0 1 1 1 1 1 0 0 0 1 1 0 0 1 0 1 0 1 0 0 1 0 1 1 1 1 1 0 0 0 1 1 0 1 1 1 1 1 0 1 1 1 1 1 0

A B C A  B  C

0 0 0 0 0 0 1 1 0 1 0 1 0 1 1 0 1 0 0 1 1 0 1 0 1 1 0 0 1 1 1 1

Topic 1 COE 292 Introduction to Artificial Intelligence 36

❖ Generally, deeper networks reduce the number of neurons

(perceptrons) significantly

❖ For an 𝑁 input XOR gate: 𝑦 = 𝑥1⨁𝑥2⨁ ⋯ ⨁𝑥𝑁, total number

of needed perceptrons (hidden plus output):

MLPs as Boolean Functions

x1 x2 x3 x4 x5 x6

XOR

XOR

XOR

XOR

XOR

y

Example: 𝑦 = 𝑥1⨁𝑥2⨁𝑥3⨁𝑥4⨁𝑥5⨁𝑥6

With one hidden layer: 2𝑁−1 + 1 perceptrons

With 2 N − 1 − 1 hidden Layers: 3(𝑁 − 1) perceptrons

Topic 1 COE 292 Introduction to Artificial Intelligence 37

❖ Summary:

• Scheme 1: direct implementation from truth table (One hidden layer)

• Scheme 2: using structure (1) and associative property

• Scheme 3: using structure (2) and associate property

MLPs as Boolean Functions – The XOR Function

x1 x2 x3 x4 x5 x6

XOR

XOR

XOR

XOR

XOR

y

Example: 𝑦 = 𝑥1⨁𝑥2⨁𝑥3⨁𝑥4⨁𝑥5⨁𝑥6

Scheme/criteria # of hidden layers # of hidden layers

+ output

# of Perceptrons

in hidden layers

Total # of

Perceptrons

1 1 2 2𝑁−1 2𝑁−1 + 1

2 2 𝑁 − 1 − 1 2(𝑁 − 1) 3 𝑁 − 1 − 1 3(𝑁 − 1)

3* 2 𝑁 − 1 − 1 2 𝑁 − 1 2 𝑁 − 1 − 1 2 𝑁 − 1

Structure (1)

Structure (2)

* ONE perceptron per layer for this scheme.

Topic 1 COE 292 Introduction to Artificial Intelligence 38

❖ An MLP can represent any boolean function, only if it is sufficiently

wide and sufficiently deep, precisely (no error)

❖ A network with fewer than the minimum required number of neurons

cannot model the function

❖ Optimal width and depth depend on the number of variables and the

complexity of the Boolean function

❖ Deeper networks may require far fewer neurons than shallower

networks to express the same function

❖ The actual number of parameters in a network is the number of

connections

❖ Networks that require an exponential number of neurons will require

an exponential number of weights

MLPs as Boolean Functions

Topic 1 COE 292 Introduction to Artificial Intelligence 39

❖ The “real” valued perceptron

• Inputs and weights are real values

• Output could be Boolean or real

• Any real-valued “activation” function may operate on the

weighted sum input

❖ MLP as a function over real inputs finds a complex

“decision boundary” over a space of reals

MLPs as Universal Classifiers

28x28 image

Topic 1 COE 292 Introduction to Artificial Intelligence 40

❖ A perceptron operating on real-valued

vectors is a linear classifier

❖ Boolean perceptrons are also linear

classifiers

❖ If we have n inputs, the weights define

a decision boundary that is an n–1

dimensional hyperplane

MLPs as Universal Classifiers

X or Y X and Y

𝑤1𝑥1 + 𝑤2𝑥2 − 𝑇 ≥ 0

𝑥2 ≥ − 𝑤1

𝑤2 𝑥1 +

𝑇

𝑤2

X XOR Y

Topic 1 COE 292 Introduction to Artificial Intelligence 41

❖ Assuming the use of a single simple perceptron

𝒐𝒖𝒕𝒑𝒖𝒕 = 𝟏 𝒊𝒇 σ𝒊 𝒘𝒊𝒙𝒊 + 𝒃𝒊 ≥ 𝟎. Clearly show the used

weights and bias that detect the region below the blue

line (i.e., output =1 for area under the blue line).

MLPs as Universal Classifiers

• Find the slope of the line using (0,-2) and (-1,0)

• 𝑚 = 𝑥

2 −0

𝑥 1 +1

= −2−0

0+1

• 𝑥

2

𝑥 1 +1

= −2

1 = −2

• Equation of the line :𝑥2 = −2𝑥1 − 2

• Since class 1 below the line,

• The decision boundary is 𝑥2 ≤ −2𝑥1 − 2

• Rearrange the equation so that it is ≥ 0

• −2𝑥1 − 𝑥2 − 2 ≥ 0

• 𝑤1 = −2, 𝑤2 = −1, 𝑏 = −2

Topic 1 COE 292 Introduction to Artificial Intelligence 42

❖ Assuming the use of a single simple perceptron

𝒐𝒖𝒕𝒑𝒖𝒕 = 𝟏 𝒊𝒇 σ𝒊 𝒘𝒊𝒙𝒊 + 𝒃𝒊 ≥ 𝟎. Clearly show the

used weights and biases that detect the region below

the given line (i.e., output =1 for area under the blue line).

Pop-up Question

• 𝑥

2 −0

𝑥 1 +1

= −3−0

0+1

• 𝑥

2

𝑥 1 +1

= −3

1 = −3

• Equation of the line: 𝑥2 = −3𝑥1 − 3

• Since class 1 below the line,

• The decision boundary is 𝑥2 ≤ −3𝑥1 − 3

• Rearrange the equation so that it is ≥ 0

• −3𝑥1 − 𝑥2 − 3 ≥ 0

• 𝑤1 = −3, 𝑤2 = −1, 𝑏 = −3

Topic 1 COE 292 Introduction to Artificial Intelligence 43

Pop-up Question

Topic 1 COE 292 Introduction to Artificial Intelligence 44

Composing Complex “Decision” Boundaries

Topic 1 COE 292 Introduction to Artificial Intelligence 45

❖ Build a MLP network with a single output that fires if

the input is in the colored area

❖ The network must fire if the input is in the colored

area

Composing Complex “Decision” Boundaries

Topic 1 COE 292 Introduction to Artificial Intelligence 46

Composing Complex “Decision” Boundaries

Topic 1 COE 292 Introduction to Artificial Intelligence 47

❖ MLPs can compose arbitrarily complex decision

boundaries

Composing Complex “Decision” Boundaries

Topic 1 COE 292 Introduction to Artificial Intelligence 48

❖ Design an MLP to classify the shaded area given below, assuming simple

perceptron: 𝑜𝑢𝑡𝑝𝑢𝑡 = 1 𝑖𝑓 σ𝑖 𝑤𝑖𝑥𝑖 + 𝑏𝑖 ≥ 0. Clearly show the used weights and

biases.

Composing Complex “Decision” Boundaries

𝑥2 = −𝑥1 + 1, then Yellow region iff 𝑥2 ≤ −𝑥1 + 1 Or −𝑥2 − 𝑥1 + 1 ≥ 0

𝑥2 = 𝑥1 − 1, then Yellow region iff 𝑥2 ≥ 𝑥1 − 1 Or 𝑥2 − 𝑥1 + 1 ≥ 0

𝑥2 = −𝑥1 − 1, then Yellow region iff 𝑥2 ≥ −𝑥1 − 1 Or 𝑥2 + 𝑥1 + 1 ≥ 0

𝑥2 = 𝑥1 + 1, then Yellow region iff 𝑥2 ≤ 𝑥1 + 1 Or −𝑥2 + 𝑥1 + 1 ≥ 0

Why is this bias equal to −4?

Ans: We are ANDING the results from the

hidden layer perceptrons ➔ Threshold should

be 4 or bias = -ve of Threshold = −4

Topic 1 COE 292 Introduction to Artificial Intelligence 49

Composing Complex “Decision” Boundaries

❖ 𝑥

2 +1

𝑥 1 −0

= 0+1

1−0

❖ 𝑥

2 +1

𝑥 1

= 1

1 = 1

❖ 𝑥2 + 1 = 𝑥1

❖ 𝑥2 = 𝑥1 − 1

❖ Since class 1 above the line

❖ 𝑥2 ≥ 𝑥1 − 1

❖ Rearrange the equation to become ≥ 0

❖ −𝑥1 + 𝑥2 + 1 ≥ 0

❖ 𝑤1 = −1, 𝑤2 = 1, 𝑏 = 1

❖ 𝑥

2 +1

𝑥 1 −0

= 0+1

−1−0

❖ 𝑥

2 +1

𝑥 1

= 1

−1 = −1

❖ 𝑥2 + 1 = −𝑥1

❖ 𝑥2 = −𝑥1 − 1

❖ Since class 1 above the line

❖ 𝑥2 ≥ −𝑥1 − 1

❖ Rearrange the equation to become ≥ 0

❖ 𝑥1 + 𝑥2 + 1 ≥ 0 ❖ 𝑤1 = 1, 𝑤2 = 1, 𝑏 = 1

Topic 1 COE 292 Introduction to Artificial Intelligence 50

❖ 𝑥

2 −0

𝑥 1 −1

= 1−0

0−1

❖ 𝑥

2

𝑥 1 −1

= 1

−1 = −1

❖ 𝑥2 = −𝑥1 + 1

❖ Since class 1 below the line,

𝑥2 ≤ −𝑥1 + 1

• Rearrange the equation so

that it is ≥ 0

❖ −𝑥1 − 𝑥2 + 1 ≥ 0

❖ 𝑤1 = −1, 𝑤2 = −1, 𝑏 = 1

Composing Complex “Decision” Boundaries

❖ 𝑥

2 −0

𝑥 1 +1

= 1−0

0+1

❖ 𝑥

2

𝑥 1 +1

= 1

1 = 1

❖ 𝑥2 = 𝑥1 + 1

❖ Since class 1 below the line, 𝑥2 ≤ 𝑥1 + 1

• Rearrange the equation so that it is ≥ 0

❖ 𝑥1 − 𝑥2 + 1 ≥ 0

❖ 𝑤1 = 1, 𝑤2 = −1, 𝑏 = 1

Topic 1 COE 292 Introduction to Artificial Intelligence 51

❖ Suppose that we would like to design a

Multi-layer Perceptron MLP network to

detect all points in the shaded area shown

below, what is the number of perceptrons,

neurons, needed to achieve 100%

accuracy? What about the minimum

number of neurons?

• 1 neuron per each line

• 1 AND neuron per each closed shape

• 1 OR neuron to connect all AND neurons

• A line, a neuron, could be shared among shapes.

Pop-up Question

Topic 1 COE 292 Introduction to Artificial Intelligence 52

Pop-up Question

Topic 1 COE 292 Introduction to Artificial Intelligence 53

❖ What region is classified by the given MLP below?

Pop-up Question

𝑥 + 𝑦 ≥ 0.25 → 𝑦 ≥ −𝑥 + 0.25

−𝑥 − 𝑦 ≥ −0.75 → −𝑦 >= 𝑥 − 0.75 → 𝑦 ≤ −𝑥 + 0.75

0.25

-0.75

Topic 1 COE 292 Introduction to Artificial Intelligence 54

❖ Design an MLP to detect all points in the shaded area shown below, assuming

simple perceptron: 𝑜𝑢𝑡𝑝𝑢𝑡 = 1 𝑖𝑓 σ𝑖 𝑤𝑖𝑥𝑖 + 𝑏𝑖 ≥ 0. Clearly show the used

weights and biases. Note the detected region is Region 1 UNION Region 2.

❖ SOLUTION 1:

❖ Region 1:

• Line 1: x1=0 → x1 ≥ 0 → (1)x1 + (0) x2 ≥ 0

• Line 2: x2=0 → x2 ≥ 0 → (0)x1 + (1)x2 ≥ 0

• Need an AND gate to confine the output to 1st quadrant

❖ Region 2:

• Line 3: x1=0 → x1 ≤ 0 → (-1)x1 + (0)x2 ≥ 0

• Line 4: x2=0 → x2 ≤ 0 → (0)x1 + (-1)x2 ≥ 0

• Need an AND gate to confine the output to 3rd quadrant

❖ Need an OR gate to combine 1st quadrant and 3rd quadrant

❖ Number of needed perceptons: 3+3+1 = 7

Example 2:

𝑥1 ≥ 0 𝑎𝑛𝑑

𝑥2≥ 0

𝑥1 ≤ 0 𝑎𝑛𝑑

𝑥2≤ 0

Region 1

Region 2 Line 1

Line 2

Topic 1 COE 292 Introduction to Artificial Intelligence 55

❖ Design an MLP that classifies all points in the highlighted in Fig.1 as 1, and all

other points as 0.

❖ The highlighted area includes all points to the right of the line x1 = −3,

EXCLUDING those in the fourth quadrant.

❖ This can NOT be done using 2 layers MLP

❖ You can divide the area into two regions: region1 and region2.

❖ The two regions in Fig2 will be implemented using 3 layers with 8 perceptrons.

❖ You can do better (less perceptrons) by dividing the designated area as in fig. 3.

❖ This can be implemented using 3 layers with 7 perceptrons.

Example 3

Region-1

R eg

io n

-2

Region-1

Region-2

Fig.1 Fig.2 Fig.3

Topic 1 COE 292 Introduction to Artificial Intelligence 56

❖ Considering the 2 common lines in Fig 2: line1

and X1 axis, that will save us 2 perceptrons.

❖ Region-1 is defined by two boundaries:

• 𝑥1 = −3 → 𝑥1 + 3 ≥ 0

• 𝑥2 = 0 → 𝑥2 ≥ 0

❖ Region-2 is defined by three boundaries

• 𝑥1 = −3 → 𝑥1 + 3 ≥ 0

• 𝑥2 = 0 → 𝑥2 ≤ 0 → −𝑥2 ≥ 0

• 𝑥1 = 0 → 𝑥1 ≤ 0 → −𝑥1 ≥ 0

❖ The MLP with 6 neurons that does the required

job

Example 3 – cont’d

Region-1

R eg

io n

-2

Fig.2

Topic 1 COE 292 Introduction to Artificial Intelligence 57

❖ Note that if we use Regions division

as in Fig 3 on previous slide:

❖ Then Region-2 can be defined using

two boundaries (instead of 3): X1=-3

and X1=0.

❖ In this case, Region-1 and Region-2

overlap, but that is NOT a problem

for the final OR operation.

❖ Then the connection/weight

highlighted in RED is NOT needed

❖ You still need 6 neurons to define the

desired boundary.

Example 3 – cont’d

INTRODUCTION TO AI 57

Region-1

Region-2

Topic 1 COE 292 Introduction to Artificial Intelligence 58

❖ Note that if we use Regions division

as in Fig 4 on previous slide:

❖ Then Region-2 can be defined using

two boundaries (instead of 3): X1=-3

and X1=0.

❖ In this case, Region-1 and Region-2

overlap, but that is NOT a problem

for the final OR operation.

❖ Then the connection/weight

highlighted in RED is NOT needed

❖ You still need 6 neurons to define the

desired boundary.

Example 3 – cont’d

INTRODUCTION TO AI 58

Fig.3

Topic 1 COE 292 Introduction to Artificial Intelligence 59

❖ A multilayer network of perceptrons with a single

hidden layer can be used to

• represent any Boolean function precisely (no error)

• approximate any continuous function to any desired accuracy

Summary

Topic 1 COE 292 Introduction to Artificial Intelligence 60

❖ Slides have been used from:

• https://www.cs.cmu.edu/~bhiksha/courses/deeplearning/Sprin

g.2019/www/

Acknowledgments