为啥会把这两个东西放一块呢:-I?这两个程序编写的任务相似性还不少,都是给你数值计算的算法,让你去编程实现,不限语言,定期要提交结果。一个是最优化方法的课上,老师要求编程实现Fibonacci法和黄金分割法,下周检查。另一个是人工智能导论的课上,老师改革了一下实验课程,要求我们照着一篇论文,实现基本的构造性覆盖算法以完成分类任务。人工智能导论的理论课还要交一份课程报告,我寻思想把实现这个算法的过程写一份开发总结文档,当成课程论文提交上去。进而想到可以在写博客的时候也就完成这件事。于是,就有了这个杂糅起来的博文。

先写实现fib法和黄金分割法的过程。最优化这门课我是没怎么去听的,想做掉这个作业自然是课后拿着名词去搜索。首先搞清楚了黄金分割法。输入就是给定一个一元多项式,一个区间范围,一个精度。输出就是这个多项式在给定区间范围内的极值点。过程就是每一次迭代在0.382和0.618比例处设置两个试探点,根据这两个点的函数值大小,砍掉某一边0.382比例的区间范围,在剩下的区间范围中继续迭代,直到区间长度小于给定的精度。课本和某些网上的介绍中,每一次迭代的赋值过程更为复杂,确实利用了0.618划分的自相似性,减少了计算量,不过增加了阅读难度。我在代码实现中为了保证可读性,没有完全按照那些更为复杂的迭代赋值版本去写,而只是按照

[计算lambda、mu -> 计算试探点值 -> 通过迭代区间边界砍掉某块区间]

的过程去编写,保证了代码的简洁易懂。当前的机器条件下,“优化”一定是在确定了代码的性能瓶颈位置后,有针对性地去进行优化。盲目的优化是代码可读性的杀手。

之后是考虑实现代码。第一个问题出现:多项式怎么表示?本来想复制粘贴以前写OJ题时自己写的polynomial类,不过很快想到,这次既然完全不限实现方式,那看看boost库呢?结果boost的math模块里真有现成的polynomial类。这次实现这些数值运算程序,boost库帮到不少忙。不过我也知道,boost库有个问题:拖家带口(ーー;),引用一个boost模块,基本是意味着编译你的C++源代码的环境得预先装好整个boost库。这不是啥好消息……不过我寻思,之后带去如果展示的话,肯定是在我自己电脑上,实在不行的话就把输入输出都写友好点,编译成现成的cmd程序,再带去用。于是,决定下来引用boost库去完成问题。之后的问题不太大,就是跟着polynomial的模版形式,写几个模版形式,实现要求的算法的函数。为了提升输出的友好程度,从polynomial的官方文档里粘贴了一个打印多项式的函数,引入了对lexical_cast的依赖。中途实现的时候因为牵涉到double的大小比较,又多写了几个用到eps,辅助比较double的短函数。

之后是写fib法的实现。看了一会才发现,就是用f(n – 2) / f(n – 1)和f(n – 1) / f(n)去替换0.382和0.618……不过fib法相比黄金分割法,因为是从后到前地取数列的数进行计算,所以就多了index越界的可能性。测试程序的时候因为这个多遇到几次运行错误。

fib法和黄金分割法的实现代码见:

https://github.com/ylink-lfs/optim_course_imp


之后是写编写构造性覆盖算法过程的总结,同时也算写掉导论课的课程报告。

首先放一份老师发放的PDF完整版本,是介绍构造性覆盖算法的中文论文,老师要求我们实现其中的基础部分。

构造性覆盖算法

我说一下我对这个算法的大概理解:这个算法实现的是对样本进行分类,创新之处是改进了神经网络中的神经元结构,构造神经元不是基于BP,而是论文中提出的不断基于“距离”“半径”去构造“超球领域”以分割样本。算法大致步骤是这样:首先归一化所有给定样本的每个属性值,然后对每个样本的属性进行升维,让所有样本的属性向量长度相同,投影到一个超球面上。之后,需要分多少类,就随机取多少样本,依次用于初始化对应数目的神经元,作为“超球领域”的中心。之后有三种方法去构造每一个神经元的“半径”:最小半径、最大半径,取中半径。我选了目前实现最方便的最小半径法去实现,老师有其他要求再加代码扩展。最小半径法就是找到当前神经元负责的类别中,与该神经元的中心样本距离最远的当前关注类别的样本,以此作为这个神经元的“半径”。对每个神经元进行找半径的操作之后,训练阶段就结束了。这比BP神经网络基于梯度下降的训练法快多了……测试时,对每个测试样本,依次计算每个神经元对样本的响应程度——是否落在“超球领域”的范围内,计算测试样本和中心样本的距离和神经元存储半径的相对大小即可。如果只有一个神经元正面响应,其他神经元都是负面响应,那么可以将样本划归到正面响应的那个类中。如果有多个正面响应,那么延迟决策。延迟决策也有多种方法,我用了最容易实现的距离中心最近原则。最后跑出的结果震荡有点大,低的时候验证结果是0,高的时候也能到百分之80多,打算之后再问问老师。

之后是讨论代码实现部分。获取到数据时,发现论文里提到的若干数据集,最容易写代码转化的是wine数据集,展示如下:

2,12.04,4.3,2.38,22,80,2.1,1.75,.42,1.35,2.6,.79,2.57,580
3,12.86,1.35,2.32,18,122,1.51,1.25,.21,.94,4.1,.76,1.29,630

第一个数字就是整数表示的类别,不过是1~x编码的,其他的列都是各项属性数据。其他数据集中,wave数据集一时没看明白怎么用;有的数据集是属性一栏不是浮点数,给了一堆布尔值,没想明白怎么处理;还有的数据集类别用了字符串表示,需要我去做hash处理。还有更多奇葩的情况,wine数据集算是最安分的,于是决定写代码就照着它去写。不过“照着它去写”仅仅体现在数据处理部分,数据集的不同被我隔离在不同的数据处理函数中。数据处理函数我设计的接口是参数任意,返回一个设计好的vector<input_data>向量,自己写了一个wine数据集的处理,另外留了这个接口

struct input_data
{
	//class id tagged from 0 to [class_numbers] - 1
	int class_id;
	vector<double> attributes;
	friend boost::serialization::access;
	template<typename Archive>
	void serialize(Archive& ar, const unsigned int version)
	{
		ar & class_id;
		ar & BOOST_SERIALIZATION_NVP(attributes);
	}
};

//Dataset reader interface:
vector<input_data> read_your_dataset(/*args*/)
{
	//Use all sort of fucking args as long as returning a vector containing structs as described in .h file.
	//If dataset attributes aren't normalized in advance, you need to call normalize_attributes(mid_v) manually.
	return vector<input_data>();
}

来做其他数据集的扩展支持。只要写符合这个形式的读取函数,就能处理对应的数据集。

之后是升维操作。升维操作其实体现在代码里就是一次vector的push_back……说的玄乎。对每一个样本,用公式算一下应该push_back什么值进去,完事。

然后构造神经元。神经元我设计出一个类。讲课时老师推荐用的结构体有5个字段,3个是保存训练过程中的信息的,我简化到只有两个:中心点和半径。另外想到之前用过的深度学习框架(呕),都是有保存checkpoint功能的,那我干脆也加一个。于是就引入了Boost的serialization库。为了保证能跑起来,就要给input_data类和neuron类都加上serialize函数。序列化vector还要用它给定的宏。然后……感觉构造这部分就没啥讲了😂。

之后是训练方式的选择。一般机器学习有两种方式:k-fold validation和分好训练集测试集之后一个一个epoch迭代。本来因为畏惧实现的难度,想用第二种方式实现,不过看了论文和数据集之后,确实是k-fold validation优于第二种方案,那就用交叉验证呗。写完这个之后让我更加坚定地相信,python语法和其下深度学习框架的API,是坨屎。那就实现吧。首先把数据的index分成k堆,之后进入一个k次数的循环,每次循环先选定k堆中哪一堆是验证集,初始化一堆neuron,之后对每个neuron,用每个样本进行一次训练,最终期望得到那个最大的半径值。如果我没写错的话,的确是比传统的训练方法快得多。目前代码的实现没把序列化加进去,不过函数都是写好的,有需求就能往里去放。

然后是写验证和结果输出。验证函数设计成返回一个double值,就是验证阶段计算出的Accuracy。取每个数据,之后送入每个神经元,得到一组预测结果,然后判断是直接归为某类,还是继续做延迟决策。也没啥可以展开的地方。

代码实现见这个链接:

https://github.com/ylink-lfs/ml-course-project