原来飞桨还可以这么玩！当人工智能邂逅蓝桥杯算法题，会擦出怎样的火花？

假如人工智能也玩起了蓝桥杯算法题… …

目前，蓝桥杯上几乎所有算法题都是每个输入都有唯一确定的输出，对于一些输入输出是线性关系的题目，利用机器学习可以做一个对应的拟合，从而根据拟合出来的模型得到最终结果。

本文会以蓝桥杯的2道算法题（Fibonacci数列、大等于n的最小完全平方数）为例，尝试使用飞桨解决上面这两道算法题。

参考资料：

• 写给小白的入门项目，神经网络前向传播原理详解
• 蓝桥杯试题入门训练之Fibonacci数列-Python满分解答
• 蓝桥杯试题算法训练之大等于n的最小完全平方数——Python满分解答

一、实现原理

虽然都说神经网络是个大黑盒，但是，其实这个黑盒并不是那么黑。

• 一个神经元就相当于一个函数，最简单的神经网络只有一个神经元
• 神经网络是由许许多多的神经元搭建起来的，也就是说一个能拟合任意函数的函数拟合器其实是由许许多多的函数搭建起来的

是不是有点像傅里叶级数？（傅里叶发现任何周期函数都可以用正弦函数和余弦函数构成的无穷级数来表示）

1.从最简单的神经网路开始

在学习机器学习的过程中，大家对神经网络应该都有一个基本概念：神经网络就像一个函数拟合器，它可以拟合任意函数。

举个例子，输入一个数，输出它的相反数，那么这个函数就是正比例函数，且它的比例系数为-1，我们试着构造一个刚刚描述的神经网络：

def NeuralNetwork(inputs, weight): # 定义神经网络prediction = inputs * weight   # 将数据与权重相乘return predictioninputs = 2  # 输入数据，可随意更换
weight = -1 # 权重
pred = NeuralNetwork(inputs, weight) # 前向传播，即获得预测结果
print(pred)

-2

刚刚我们完成的就是前向传播的过程，也就是一个预测的过程 。

预测其实就是神经网络对输入数据进行“思考”后得到的结果，更复杂的例子有：基于昨天的天气预测今天的天气

2.神经网络工作原理概述

上面的那个神经网络将输入乘以权重，将输入数据“缩放”一定的比例。神经网络的交互其实很简单：

1. 它接受输入变量，并以此作为信息来源
2. 它拥有权重变量，以此作为知识
3. 融合信息和知识，输出预测结果

目前为止，所有的神经网络都是这样工作的，它使用权重中的知识解释输入数据中的信息。

看到这里，你心中也许会有疑惑，为什么可以把权重当作知识？

另一种理解神经网络权重值的方法，是将权重作为网络的输入和预测之间敏感度的度量：

• 如果权重非常高，那么即使最小的输入也可以对预测结果产生非常大的影响；
• 如果权重很小，那么就算是很大的输入也只能对预测结果产生很小的扰动。

3.使用多个输入进行预测

在实际场景中，如果能给神经网络提供的信息越多，那么神经网络应该能做出更准确的预测。

事实上，一个网络也可以同时接受多个输入数据点。就像下面这个例子：

• 根据当前的温度、湿度、风速预测一段时间后的天气情况

weights = [0.012, 0.3, 0.25] #温度、湿度、风速的权重
inputs = [26, 0.75, 1.2] #温度、湿度、风速数据def PredSum(inputs, weights):assert(len(inputs) == len(weights))output = 0for item in range(len(inputs)):output += inputs[item] * weights[item] #将输入分别乘以其对应的权重return outputdef NeuralNetwork(inputs, weights):pred = PredSum(inputs, weights)return predpred = NeuralNetwork(inputs, weights)
print(pred) #一段时间后发生某事的概率，如下雨的概率

0.837

这种新的神经网络可以同时接受多个输入并作出预测。这使得网络能够结合多种形式的信息，做出更明智的决定。但是它使用权重的基本机制并没有改变。

这里带来的新特性是，因为有多个输入，所以要把他们各自的预测结果合在一起。因此，将每个输入乘以其各自的权重，然后对所有局部预测结果进行求和，这称为输入的加权和。

不过，像上面这样的代码虽然一次就可以处理多个输入，但是还是显得太麻烦了，因此，我们需要用到新工具：Numpy

对于创建向量和执行常见函数（如点积运算）来说，它的代码效率很高，下面是利用Numpy实现相同功能的代码：

import numpy as npweights = np.array([0.012, 0.3, 0.25])
inputs = np.array([26, 0.75, 1.2])def NeuralNetwork(inputs, weights):pred = inputs.dot(weights)return predpred = NeuralNetwork(inputs, weights)
print(pred)

0.837

4.只用一个输入做出多个输出

多输出可能是比多输入更简单的拓展。如果是3个输出，则预测过程与三个单一权重的独立神经网络是一样的。需要注意的是，这3个预测结果完全独立。

假设我们在一场球赛上，想通过某个球队的胜负记录预测球员的心情（是高兴还是悲伤）、下一场比赛的结果以及队员的受伤比例，来看看这个例子怎么做：

import numpy as npweights = np.array([0.3, 0.2, 0.9])
inputs = 0.65def NeuralNetwork(inputs, weights):pred = inputs * weightsreturn predpred = NeuralNetwork(inputs, weights)
# print(pred)
print("受伤比例预测：{}".format(pred[0]))
print("比赛胜负预测：{}".format(pred[1]))
print("悲伤程度预测：{}".format(pred[2]))

受伤比例预测：0.195
比赛胜负预测：0.13
悲伤程度预测：0.5850000000000001

5.基于多个输入得到多个输出

基于给定的多个输入，神经网络预测得到多个输出。

假设我们在一场球赛上，想通过某个球队的胜负记录、粉丝数和球员数量来预测球员的心情（是高兴还是悲伤）、下一场比赛的结果以及队员的受伤比例，来看看这个例子怎么做：

import numpy as np#从左到右分别是：[是否受伤, 是否胜利, 是否难过]
weights = np.array([[0.02, 0.01, 0.05],    #胜负记录[0.001, 0.025, 0.04],  #粉丝数量[0.013, 0.03, 0.001]]) #球员数量
inputs = np.array([0.65, 12.0, 8.0])       #分别是该球队的胜负记录、粉丝数量、球员数量def NeuralNetwork(inputs, weights):pred = inputs.dot(weights)return predpred = NeuralNetwork(inputs, weights)
# print(pred)
print("受伤比例预测：{}".format(pred[0]))
print("比赛胜负预测：{}".format(pred[1]))
print("悲伤程度预测：{}".format(pred[2]))

受伤比例预测：0.129
比赛胜负预测：0.5465
悲伤程度预测：0.5205

分析一下上面这个例子，这个神经网络对输入数据执行了3次独立的加权和操作，产生了3个预测结果。其实就是简单的矩阵运算，横行乘竖列再相加。

6.用预测结果进一步预测

神经网络是可以堆叠的！可以将一个网络的输出提供给另一个网路作为输入。这相当于两个连续的向量矩阵乘法。

这样做的原因是：在处理复杂问题时，对于单一权重矩阵来说过于复杂（即参数的数量不够）。

还是上面的例子：在一场球赛上，想通过某个球队的胜负记录、粉丝数和球员数量来预测球员的心情（是高兴还是悲伤）、下一场比赛的结果以及队员的受伤比例：

import numpy as np#从左到右分别是：[是否受伤, 是否胜利, 是否难过]
InputHiddent = np.array([[0.2, 0.01, 0.05],      #隐藏层第一个单元[0.01, 0.025, 0.04],     #隐藏层第二个单元[0.13, 0.03, 0.001]])    #隐藏层第三个单元#从左到右分别是：隐藏层第一个单元到第三个单元的权重
HiddentPrediction = np.array([[0.02, 0.1, 0.5],  #胜负记录[0.01, 0.25, 0.04],  #粉丝数量[0.013, 0.3, 0.01]]) #球员数量weights = [InputHiddent, HiddentPrediction]      #存放权重值，[输入到隐藏层的权重， 隐藏层到输出的权重]
inputs = np.array([0.65, 12.0, 8.0])             #分别是该球队的胜负记录、粉丝数量、球员数量def NeuralNetwork(inputs, weights):hid = inputs.dot(weights[0]) #计算隐藏层的输出pred = hid.dot(weights[1])   #将上一层（隐藏层）的输出带入下一层的输入return predpred = NeuralNetwork(inputs, weights)
# print(pred)
print("受伤比例预测：{}".format(pred[0]))
print("比赛胜负预测：{}".format(pred[1]))
print("悲伤程度预测：{}".format(pred[2]))

受伤比例预测：0.0380315
比赛胜负预测：0.421775
悲伤程度预测：0.672065

二、拟合斐波那契数列

Fibonacci数列是蓝桥杯试题入门训练的题目，算是一道入门的题目，我们尝试让神经网络试试看，看看能不能解决这道题

1.问题描述

斐波那契数列的递推公式为：$F_n=F_{n-1}+F_{n-2}$，其中$F_1=F_2=1$。

当n比较大时，$F_n$也非常大，现在我们想知道，$F_n$除以10007的余数是多少。

输入格式

输入包含一个整数n。

输出格式

输出一行，包含一个整数，表示$F_n$除以10007的余数。

2.生成数据

数据几乎是所有模型的关键，它决定着模型的天花板。

# 生成输入数据
import numpynum_inputs=1
num_examples=10
features = numpy.random.randint(1, 10, (num_examples, num_inputs))

print(features[:,0])

# 生成输入对应的标签
def Fibonacci(n):F = [1, 1]if n <= 2:for item in range(n):F.append(F[item] + F[item + 1])return F[n - 1]%10007else:for item in range(n - 2):result = (F[0] + F[1]) % 10007 # 计算出下一项后直接取余数，不影响结果 F[0], F[1] = F[1], resultreturn result # 直接输出余数，不需要再除10007labels = []
for item in features[:,0].tolist():labels.append(Fibonacci(item))
labels = numpy.expand_dims(labels, axis=-1) #注意：需要在最后增加一个维度

print(labels[:,0])

# 将数据转换成tensor
import paddlefeatures = features.astype('float32')
labels = labels.astype('float32')
train_datas = paddle.to_tensor(features)
y_true = paddle.to_tensor(labels)

3.构建线性回归模型

import paddleclass Regressor(paddle.nn.Layer):def __init__(self):super(Regressor, self).__init__()self.fc1 = paddle.nn.Linear(1, 2)self.fc2 = paddle.nn.Linear(2, 2)self.fc3 = paddle.nn.Linear(2, 1)def forward(self, inputs):hiddent = self.fc1(inputs)pred = self.fc2(hiddent)pred = self.fc3(pred)return predmodel = Regressor()

4.构建优化器和损失函数

# 定义Momentum优化器
lr = paddle.optimizer.lr.CosineAnnealingDecay(learning_rate=0.5, T_max=50)
optimizer = paddle.optimizer.Adam(learning_rate=lr,parameters=model.parameters(),weight_decay=paddle.regularizer.L2Decay(0.0001))
mse_loss = paddle.nn.MSELoss()

5.模型训练

for i in range(1000):y_predict = model(train_datas)loss = mse_loss(y_predict, y_true)loss.backward()optimizer.step()optimizer.clear_grad()print(loss.numpy())

[3.0985627]

6.模型验证

斐波那契数列的前9项：

n	1	2	3	4	5	6	7	8	9
F(n)	1	1	2	3	5	8	13	21	34

infer_features = numpy.random.randint(1, 10, (1, 1)).astype('float32')
infer_features = paddle.to_tensor(infer_features)fetch_list = model(infer_features)

print(infer_features)
print(fetch_list)

Tensor(shape=[1, 1], dtype=float32, place=CUDAPlace(0), stop_gradient=True,[[6.]])
Tensor(shape=[1, 1], dtype=float32, place=CUDAPlace(0), stop_gradient=False,[[9.02307510]])

斐波那契数列的第6项是8，模型的预测输出是9.02，取整就是9，虽然不是很准确，但是结果接近。

三、大等于n的最小完全平方数

大等于n的最小完全平方数是蓝桥杯试题算法训练里的练习题，难度比斐波那契数列要难一些，我们用飞桨来解这一题，过程跟上一题类似。

1.问题描述

输出大等于n的最小的完全平方数。

若一个数能表示成某个自然数的平方的形式，则称这个数为完全平方数

Tips：注意数据范围

输入格式

一个整数n

输出格式

大等于n的最小的完全平方数

• 样例输入

71711

• 样例输出

71824

2.生成数据

# 生成输入数据
import numpynum_inputs=1
num_examples=10
features = numpy.random.randint(1, 10, (num_examples, num_inputs))

# 生成输入对应的标签
import mathdef PerfectSquare(n):result = 0if n >= 0:result = n ** 0.5result = math.ceil(result)result = result ** 2return resultlabels = []
for item in features[:,0].tolist():labels.append(PerfectSquare(item))
labels = numpy.expand_dims(labels, axis=-1) #注意：需要在最后增加一个维度

# 将数据转换成tensor
import paddlefeatures = features.astype('float32')
labels = labels.astype('float32')
train_datas = paddle.to_tensor(features)
y_true = paddle.to_tensor(labels)

3.构建线性回归模型

import paddlemodel = paddle.nn.Linear(in_features=1, out_features=1) # 使用最简单的线性变换层

4.构建优化器和损失函数

# 定义Momentum优化器
lr = paddle.optimizer.lr.CosineAnnealingDecay(learning_rate=0.25, T_max=100)
optimizer = paddle.optimizer.Adam(learning_rate=lr,parameters=model.parameters(),weight_decay=paddle.regularizer.L2Decay(0.0002))
mse_loss = paddle.nn.MSELoss()

5.模型训练

for i in range(100):y_predict = model(train_datas)loss = mse_loss(y_predict, y_true)loss.backward()optimizer.step()optimizer.clear_grad()print(loss.numpy())

[0.77032995]

6.模型验证

infer_features = numpy.random.randint(1, 10, (1, 1)).astype('float32')
infer_features = paddle.to_tensor(infer_features)fetch_list = model(infer_features)

print(infer_features)
es = numpy.random.randint(1, 10, (1, 1)).astype('float32')
infer_features = paddle.to_tensor(infer_features)fetch_list = model(infer_features)

print(infer_features)
print(fetch_list)

Tensor(shape=[1, 1], dtype=float32, place=CUDAPlace(0), stop_gradient=True,[[6.]])
Tensor(shape=[1, 1], dtype=float32, place=CUDAPlace(0), stop_gradient=False,[[8.56781006]])

6的最小完全平方数是9，模型的输出是8.56，比较接近9，但是还有点差距，不过总的来说，是可以近似拟合的。

四、总结与升华

本文尝试使用机器学习的方法来解蓝桥杯上的算法题，主要用的是拟合，只是提供一个思路，实际上并不能解题（实际上是先用传统方法人脑解题，写出能算出结果的函数，然后根据这一函数生成训练数据，最后训练出线性回归模型）

本文使用简单的线性变换层组建网络，使用少量数据进行拟合，模型输出能近似预期结果，但还有一定的差距，有很大的提升的空间，感兴趣的开发者可以基于本项目，尝试使用更多的数据、更复杂的网络等。

个人简介

北京联合大学 机器人学院 自动化专业 2018级 本科生 郑博培
百度飞桨开发者技术专家 PPDE
百度飞桨官方帮帮团、答疑团成员
深圳柴火创客空间 认证会员
百度大脑 智能对话训练师
阿里云人工智能、DevOps助理工程师

我在AI Studio上获得至尊等级，点亮9个徽章，来互关呀！！！

https://aistudio.baidu.com/aistudio/personalcenter/thirdview/147378