COMP3211 Tutorial 2
Hongliang 09/17/2019
Run the Pacman Game
• The code requires python 2
• If you don’t have it, you can install anaconda.
Run the Pacman Game (Windows)
• Install Anaconda https://www.anaconda.com/distribution/ • Open “Anaconda Prompt”
• If you installed the python 3 version of Anaconda, create a python 2.7 environment with “conda create -n py27 python=2.7”
• Then activate the environment with “conda activate py27”
• No need to create this environment if you installed the python 2 version • Go to the project directory, and “python pacman.py”
Learning TLUs (p22, agents.pdf)
• 𝑓 = 1 if σ𝑛 𝑤𝑖𝑥𝑖 ≥ 𝜃; otherwise, 𝑓 = 0. 𝑖=1
• Parameters to learn: 𝑤 ,…,𝑤 and 𝜃. 1𝑛
• We’d like to avoid special treatment for 𝜃:
σ𝑛 𝑤𝑥≥𝜃➔w𝑥+σ𝑛 𝑤𝑥≥0➔σ𝑛 𝑤𝑥≥0
𝑖=1 𝑖 𝑖 0 0 𝑖=1 𝑖 𝑖 𝑖=0 𝑖 𝑖 where 𝑤0 = −𝜃 and 𝑥0 is always set to 1.
• Then, after learning 𝑤 ,𝑤 ,…,𝑤 , we obtain both 𝑤 ,…,𝑤 and 𝜃 01𝑛 1𝑛
Linearly Separable (p17, agents.pdf)
• Not all Boolean functions can be implemented as TLUs – those can are called linearly separable functions.
• For example, XOR is not linearly separable.
• Question: Prove that y=XOR(x1, x2) is not linearly separable.
1,𝑤𝑥 +𝑤𝑥 ≥𝜃 𝑓=ቊ1122
0,𝑤𝑥 +𝑤𝑥 <𝜃 11 22
Assume that there is a solution, then
𝑤1 ⋅ 0 + 𝑤2 ⋅ 0 < 𝜃 → 𝜃 > 0
𝑤1 ⋅ 0 + 𝑤2 ⋅ 1 ≥ 𝜃 → 𝑤2 ≥ 𝜃
𝑤1 ⋅ 1 + 𝑤2 ⋅ 0 ≥ 𝜃 → 𝑤1 ≥ 𝜃
𝑤1 ⋅1+𝑤2 ⋅1<𝜃 → w1 +𝑤2 <𝜃
However, from 𝜃 > 0, 𝑤1 ≥ 𝜃 and 𝑤2 ≥ 𝜃, we have 𝑤1 + 𝑤2 ≥ 𝜃
which contradicts with
w1 + 𝑤2 < 𝜃
Neural Networks (p18, agents.pdf)
• We can use units that are similar to TLUs to form Neural Networks. • Each such unit is called a neuron.
• Neural Networks can be used to represent any Boolean functions.
Multilayer perceptron (Optional)
Multilayer perceptron (Optional)
Eachneuron:𝑦=h(σ𝑛 𝑤𝑥 +𝑏) 𝑖=1 𝑖 𝑖
Multilayer perceptron (Optional)
h is called the activation function
h𝑧 =𝑠𝑖𝑔𝑚𝑜𝑖𝑑𝑧 = 1 1+𝑒−𝑧
h𝑧 =Reluz =max(z,0)
Eachneuron:𝑦=h(σ𝑛 𝑤𝑥 +𝑏) 𝑖=1 𝑖 𝑖
Multilayer perceptron (Optional)
z=𝑔(σ𝑛 𝑤′𝑦 +𝑏′) 𝑖=1 𝑖 𝑖
𝑔 can be:
𝑔𝑥 =ቊ0, 𝑥<0 1, 𝑥≥0
TLU to Boolean Function
Question: Which Boolean function does the following TLU implement?
The TLU has three inputs. Its weight vector is (1.3, 0.5, -2.2), and the threshold is 1.
TLU to Boolean Function
Question: Which Boolean function does the following TLU implement?
The TLU has three inputs. Its weight vector is (1.3, 0.5, -2.2), and the threshold is 1.
1. Write a truth table corresponding to TLU.
2. Write Boolean functions according to truth table.
x1
x2 x3
y
0
0
0
FALSE
0
0
1
FALSE
0
1
0
FALSE
0
1
1
FALSE
1
0
0
TRUE
1
0
1
FALSE
1
1
0
TRUE
1
1
1
FALSE
𝑥1𝑥2𝑥3 + 𝑥1𝑥2𝑥3
State Machines
• A robot has 4 sensors: 𝑠1, 𝑠2, 𝑠3, 𝑠4. They correspond to north, east, south, west, respectively. Define features:
• 𝑤𝑖 = 𝑠𝑖, where 𝑖 = 1,2,3,4
• 𝑤5 = 1 iff at the previous step, the robot moved north
• 𝑤6 = 1 iff at the previous step, the robot moved south
• The production system:
𝑤 𝑤 →𝑠𝑜𝑢𝑡h,𝑤 𝑤 →𝑛𝑜𝑟𝑡h,𝑤 𝑤 →𝑛𝑜𝑟𝑡h, 212325
𝑤2𝑤6 → 𝑠𝑜𝑢𝑡h, 𝑤5 → 𝑠𝑜𝑢𝑡h, 𝑤6 → 𝑛𝑜𝑟𝑡h, 𝑤2 → 𝑛𝑜𝑟𝑡h, 1 → 𝑒𝑎𝑠𝑡 • Current status:
w1
w2
w3
w4
w5
w6
0
0
0
0
0
1
Question: what is the previous and the next position of the robot?