本文共 10854 字，大约阅读时间需要 36 分钟。

如果需要链接，自己打印做

请参考

https://student.csc.liv.ac.uk/internal/exams/papers/Jan2018/COMP305.pdf

PAPER CODE NO.

COMP 305

EXAMINER : Dr Irina V. BiktashevaDEPARTMENT : Computer Science Tel. No. 54267

First Semester Examinations 2017/

Biocomputation

TIME ALLOWED: Two and a Half Hours

INSTRUCTIONS TO CANDIDATES

Answer FOUR questions.

If you attempt to answer more questions than the required number of

questions, the marks awarded for the excess questions answered will be

discarded (starting with the lowest mark).

Each question is worth 25 marks

1 History and Concepts.

1(a) Why are biology inspired Artificial Neural Networks and Genetic Algorithms

now considered part of Computer Science, not Computational Biology? [2 marks]

1(b) What general problems are solved by Artificial Neural Networks? Give a

couple of examples. [4 marks]

1© What problems can be solved by Genetic Algorithms? Give a couple of

examples. [4 marks]

1(d) Large numbers of academic texts are stored and made available in online

repositories. For older texts, it is necessary to convert from a paper document to an electronic document. An Optical Character Recognition (OCR) system can be used for that purpose.

i) What kind of problem is solved by the OCR system?[3 marks]ii) What are the inputs and outputs of the OCR system? Illustrate your answerwith an example.[5 marks]iii) Why does such a system require supervised learning?[3 marks]

iv) What data would be used to train an Artificial Neural Network for this task?[4 marks]

2 The McCulloch-Pitts neuron.

2 (a) Draw a flow chart for the McCulloch-Pitts neuron (MP-neuron) algorithm that

is used to compute an output in response to a particular input. NB. Assume that all weights of connections and the neuron threshold are set up in advance. [8 marks]

2 (b) Draw a diagram and explain the workings of an MP-neuron realisation of an

“OR” logical gate. [4 marks]

2© Draw a diagram and explain the workings of an MP-neuron realisation of a

“NOT” logical gate. [5 marks]

2(d) Apply your answers for the parts (a-c) of this question to deduce an output X of

the MP-neuron network below in response to the input a 1 =0, a 2 =1, a 3 =.

[8 marks]

3 Learning rules of the Artificial Neural Networks**. Hebb’s Rule.**

3(a) What is a learning rule of an artificial neural network? [3 marks]

3(b) Give the simplest mathematical formulation of Hebb’s learning rule. Explain

how to compute a correction to the weight of a connection according to the instant input and output. [4 marks]

3© Why is the Hebb’s rule called “activity product rule”? [1 mark]

3(d) Why does the Hebb’s rule represent unsupervised learning? [2 marks]

3(e) The neural network below uses Hebb’s learning rule.

Let the initial weights of connections at the time step t=1 bew 1 t=1 = 1, w 2 t=1 = 0 , w 3 t=1 = - 1;the learning rate C of the network be 0.25, that is, C = 0.25.

Complete the following table

Timestep

a 1 t^ a 2 t^ a 3 t^ w 1 t w 2 t w 3 t Xt ∆w 1 t ∆w 2 t ∆w 3 t w 1 t+1 w 2 t+1 w 3 t+

t=1 1 1 1 1 0 - 1t=2 1 1 0t=3 1 0 0

by calculating the network output value Xt, the changes in each of the three weights of connections ∆w 1 t, ∆w 2 t, and ∆w 3 t , the new weights (wnt+1)

i) at the time step t=1 [5 marks]ii) at the time step t=2 [5 marks]iii) at the time step t=3 [5 marks]

4. Supervised learning. Perceptron.

4(a) Describe the two-layer fully interconnected architecture of a Perceptron. What is

a bias input unit? [3 marks]

4(b) What is the Perceptron training set? How is it used during the error-correction

training of the Perceptron? How is an output unit’s error computed and used to define corrections to the Perceptron weights of connections (i.e. what is the Perceptron learning rule)? [7 marks]

4© A perceptron can compute only linear separable functions, that is, the functions

for which the points of the input space with function value (output) of “0” can be separated from the points with function value of “1” using a line.

Using a coordinate plane for inputs a 1 and a 2 show that the “IDENTITY” gate(see the table below) is a linear inseparable function.

a 1 a 2 “IDENTITY”

1 1 1

1 0 0

0 1 0

0 0 1

Explain your answer. [4 marks]

(to be continued)

4(d) The 3-layer network shown below implements the linear inseparable

“IDENTITY” gate. The network has weights of connections and thresholds of the processing units as shown below, and it uses the feed forward scheme to produce an output.

The output unit and both hidden units use the threshold activation step-function

 









  lj

lj

lj

ll jj

ljS

SX f S

0 ,

1 ,

where

l=h for a hidden unit l=o for the output unit

Following the feedforward scheme of the input processing,Show that this network produces correct IDENTITY output inresponse for the input a 1 =0, a 2 =1.For that, answer the following questions:

i) What is the correct output of IDENTITY gate for the inputa 1 =0, a 2 =1?[2 marks]ii) Find the outputs of the hidden units for the input a 1 =0, a 2 =1;[5 marks]

iii) Find the network output for the input a 1 =0, a 2 =1.

[3 marks] iv) Does the network produce the correct IDENTITY output in response for the input a 1 =0, a 2 =1? [1 mark]

5. Artificial Neural Networks Unsupervised Learning.
   Competitive Learning Rule, Kohonen Self-Organised Map.

5(a) Give the simplest mathematical formulation of the Kohonen competitive

learning rule. Explain how to calculate the correction to the weight of a connection according to the instant input. Why is the rule called “winner- takes-it-all”? Why does the Kohonen Self-Organised Map represent unsupervised learning? [8 marks]

5(b) The neural network below uses the “winner-takes-it-all” learning rule. At

some instant t during the network training, inputs to the network and the

weights of connections are as shown below.

(to be continued)

w 11 = 5

θ 1 = 1

θ 2 = 1

w 21 = 1

X 2

w 12 = (^1) X 1

w 22 = 1

w 13 = 5

w 23 = 1

a 1 = 1

a 2 = 2

a 3 = 2

Thus,

the instant input vector is a = {a 1 ; a 2 ; a 3 }={1; 2 ; 2};

the fan-in vector of the weights of connections to the 1st output unit is

w 1 ={w 11 ; w 12 ; w 13 }={5; 1 ; 5};

the fan-in vector of the weights of connections to the 2nd outputunit is

w 2 ={w 21 ; w 22 ; w 23 }={1; 1 ; 1};

i) Calculate the state S 1 of the first output unit, and the state S 2 of thesecond output unit at that instant.

[4 marks]

ii) What instant output X = {X 1 , X 2 } will the network produce?

[2 marks]

iii) Let the network learning rate C be set to 0.25.

Calculate changes to the weights of connections Δwji at that instant.

[4 marks]

iv) What will be the new updated weights of connections wji at that

instant?

[1 mark]

v) Let the norm of the network weights of connections be defined as

(^) 

 



2

1

3

1

2j i

w wji

What will be the new normalised weights of connections wji , j=1,2,

i=1,2,3?[6 marks]

PAPER CODE COMP305 Page 9 of 9 End

Genetic Algorithms.

6(a) Discuss the computational appeal of natural evolution. In particular, consider

parallelism, adaptation to changing environment, and optimisation of possible “solutions”. [6 marks]

6(b) Describe the basic structure of a Genetic Algorithm.

[6 marks]

6© What is a Genetic Algorithm chromosome building block, i.e. schema? What

characters are used to describe schemas of a binary chromosome? What is the order and the defining length of a schema? [5 marks]

6(d) Fill in the table below with all the schemas of the chromosome “CH” and their

corresponding orders and defining lengths.

Schema Order Defining Length

[2 marks]

6(e) Define the fitness f of a bit string x of length l=4 to be the integer represented by

the binary number x. (e.g., f (0011) = 3, f (1111) = 15).

i) What is the average fitness of the schema 10 under f?

[3 marks]

ii) What is the average fitness of the schema 0*1* under f?[3 marks]

PAPER CODE NO.

COMP 305

考官：Irina V. Biktasheva博士 Irina V. Biktasheva博士系别：计算机科学系 电话：54267 电话：54267

2017年第一学期考试/

生物计算

允許的時間： 两个半小时

##对候选人的说明。

□回答四个问题。

如果你试图回答的问题超过了规定的数目

＃＃题，多答题的分数为

弃权（从最低分开始）。

每题25分

1历史和概念。

1(a)为什么生物学启发的是人工神经网络和遗传算法？

现在被认为是计算机科学的一部分，而不是计算生物学的一部分？ [2分]

1(b)人工神经网络能解决哪些一般问题？给出一个

几个例子。 [4分]

1（三）遗传算法可以解决哪些问题？请举出几个

举例说明。 [4分]

1(d)大量的学术文本在网上储存和提供。

储存库。对于较旧的文本，有必要将纸质文件转换为纸质文件。 电子文件。光学字符识别(OCR)系统可以实现以下功能 用于这一目的。

一）OCR系统解决了什么样的问题？[3分]二）OCR系统的输入和输出是什么？说明你的答案并举例说明。[5分]三）为什么这样的系统需要监督学习？[3分]

四）对于这个任务，将使用什么数据来训练人工神经网络？[4分]

2 McCulloch-Pitts神经元。

2 (a)画出McCulloch-Pitts神经元(MP-neuron)算法的流程图，该算法为

用于计算对特定输入的输出。 NB. 假设所有连接的权重和神经元阈值都被设置为 预先。 [8分]

2 (b) 画出一个MP-神经元实现的示意图，并解释其工作原理。

"OR "逻辑门。 [4分]

2©画出一个MP-神经元实现的示意图并解释其工作原理。

"NOT "逻辑门。 [5分]

2(d)运用本题(a-c)部分的答案，推导出输出X为

##下面的MP-神经元网络对输入a 1 =0，a 2 =1，a 3 =。

[8分]

人工神经网络的3个学习规则**。Hebb规则.**

3（a）什么是人工神经网络的学习规则？[3分]

3(b)给出希伯学习法则的最简单数学公式。解释

如何根据连接的权重计算修正。 即时输入和输出。[4分]

3©为什么希伯规则被称为 “活动积规则”？[1分]

3(d)为什么Hebb规则能代表无监督学习？[2分]

3(e)下面的神经网络使用Hebb的学习规则。

让时间步t=1时连接的初始权重为w 1 t=1 = 1，w 2 t=1 = 0 ，w 3 t=1 = - 1。网络的学习率C为0.25，即C=0.25。

填写下表

时间步骤

a 1 t^ a 2 t^ a 3 t^ w 1 t w 2 t w 3 t Xt ∆w 1 t ∆w 2 t ∆w 3 t w 1 t+1 w 2 t+1 w 3 t+。

t=1 1 1 1 1 0 - 1t=2 1 1 0t=3 1 0 0

通过计算网络输出值Xt。∆w 1 t、∆w 2 t 和 ∆w 3 t 三个连接的权重变化。新权重(wnt+1)

一）在时间步长t=1时[5分]。二）在时间步长t=2时[5分]。三）在时间步骤t=3时[5分]。

4. 监督学习。Perceptron。

4（a）描述Perceptron的两层全互连结构。什么是

一个偏置输入单元？ [3分]

4（b）什么是Perceptron训练集？它在纠错过程中是如何使用的？

Perceptron的训练？如何计算输出单元的误差并将其用于 定义对连接的Perceptron权重的修正（即什么是 Perceptron学习规则）？) [7分]

4©感知器只能计算线性可分离函数，即函数

其中输入空间中函数值(输出)为 "0 "的点可以是 与函数值为 "1 "的点用一条线分开。

利用坐标平面对输入a 1和a 2进行显示，"IDENTITY "门(见下表)是一个线性不可分割的函数。

A 1 A 2 “IDENTITY”

1 1 1

1 0 0

0 1 0

0 0 1

解释一下你的答案。[4分]

(待续)

4(d)下图所示的3层网络实现了线性不可分离

"IDENTITY "门。网络中连接的权重和阈值为 处理单元，如下图所示，它采用前馈方案以 产生产出。

输出单元和两个隐藏单元都使用阈值激活步长-。功能

lj

lj

lj

ll jj

ljS

SX f S

0 ,

1 ,

哪儿

l=h为隐藏单位 输出单元的l=o

按照输入处理的前馈方案。显示该网络在以下情况下产生正确的IDENTITY输出。输入a 1=0，a 2=1的响应。为此，请回答以下问题。

一）输入的IDENTITY门的正确输出是什么？A 1=0，A 2=1？[2分]二）求输入a 1=0，a 2=1的隐藏单元的输出。[5分]

三）求输入a 1=0，a 2=1的网络输出。

[3分] 四）网络是否产生正确的IDENTITY输出，在 输入a 1=0，a 2=1的响应？ [1分]

5. 人工神经网络无监督学习。
   竞争性学习规则，Kohonen自组织图。

5(a)给出Kohonen竞争性学习的最简单的数学计算公式

学习规则。解释如何计算对权重的修正。 根据即时输入的情况进行连接。为什么这个规则被称为 “赢家”？ 占有一切"？为什么科霍宁自组织地图代表了 “自组织”？ 无监督学习？ [8分]

5(b)下面的神经网络采用 "赢家通吃 "的学习规则。在

##在网络训练期间的某个瞬间t，网络的输入和。

连接的权重如下所示。

(待续)

w 11 = 5

θ 1 = 1

θ 2 = 1

w 21 = 1

X 2

w 12 = (^1) X 1

w 22 = 1

w 13 = 5

w 23 = 1

a 1 = 1

a 2 = 2

a 3 = 2

因此：

瞬间输入向量为a = {a 1 ; a 2 ; a 3 }={1; 2 ; 2}。

第1个输出单元的连接权重的扇形输入向量是

W 1 ={W 11 ; W 12 ; W 13 }={5; 1 ; 5};

连接到第2个输出端的权重的扇形输入向量。单位是

W 2 ={W 21 ; W 22 ; W 23 }={1; 1 ; 1};

一）计算第一输出单元的状态S1，以及第一输出单元的状态S2。在该瞬间，第二个输出单元。

[4分]

二）网络将产生什么即时输出X = {X 1 , X 2 }？

[2分]

三）设网络学习率C为0.25。

＃＃计算该时刻连接权重Δwji的变化。

[4分]

＃＃四）什么将是新的更新权重的连接wji在该。

瞬?

[1分]

五）让连接的网络权重的规范定义为： 1．

(^)

2

1

3

1

2j i

w wji

＃＃什么将是新的规范化权重的连接wji ，j=1，2。

i=1,2,3?[6分]

文件編號 COMP305 第 9 頁，共 9 頁。

遗传算法。

6(a)讨论自然进化的计算魅力。特别是，考虑

并行性，适应不断变化的环境，并优化可能的环境。 “解决方案”。 [6分]

6（b）描述遗传算法的基本结构。

[6分]

6©什么是遗传算法染色体构件，即模式？什么是

字符是用来描述二元染色体的模式？是什么？ 顺序和模式的定义长度？ [5分]

6(d)在下表中填入 "CH "染色体的所有图式及其。

相应的顺序和定义长度。

模式顺序定义长度

[2分]

6(e)定义长度为l=4的比特串x的适格度f为整数，用以下方法表示： 1．

二进制数x.（如：f（0011）=3，f（1111）=15）。

一）在f下，模式10的平均适合度是多少？

〔3分

二）在f下，模式0*1*的平均适合度是多少？[3分]

转载地址：https://dequn.blog.csdn.net/article/details/113830645 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！