Posts tagged 机器学习

自动编程 – 语言的级别

先说一个悖论吧。 程序员的任务是让机器帮助人类做工作。 程序员的唯一工作就是开发代码。 程序员喜欢手动hack开发代码。 这就是我今天想要讨论的。 今天读到了阮一峰翻译的为什么Lisp语言如此先进?感触很深。原文Revenge of the Nerds 正如我开头说明的一样,之所以软件工程这个领域这么奇怪,有什么人月神话;有各种其他工程都完全不可能遇见的奇怪问题;即使开发得非常熟悉的类型的项目,再去开发仍然无法准确估计工期和成本;最讨厌的代码就是别人的代码,要知道别的工程领域流水线都是最重要的提高效率的方案,也就是在其他人做了某个步骤的产品基础之上在做一个步骤;即使软件工程理论已经存在和发展了几十年,软件项目的可测性和可控性都完全没有提高;被业界高呼了二十年的面向对象被骂为骗局;等等等等。。。 之所以这一切问题存在,是因为软件工程根本就是一个悖论。当别的工程领域早就摆脱了手工作坊生产,早就工业化自动化了的时候,软件工程还在手动hack代码。就像摆着高大的吊车和推土机不用,软件工程师们想要徒手建造长城,一次又一次的非要从地基开始重新建起。 这里再附上之前在代码交叉拷贝悖论中同ownwaterloo的讨论吧,在读到上述那篇文章之前,其实我们已经走到某一个角落了,其实已经离这个真理只差一步之遥了。(好吧。。虽然我说的也不见得就是啥“真理”啦。。) OwnWaterloo at 10/11/2010 18:12 不知道是不是想要这样的效果? 伪代码大致是这样: for image in [ thumb, caption, buttom /* 这里还可以更多 */ ] : image.offset(height) image.rotation(270) hawk at 10/11/2010 23:58 呜!这段代码很漂亮! 可惜c++效仿起来有难度。。 OwnWaterloo at 10/12/2010 10:36 其实那代码是一个暗示…… 做GUI这种效率不吃紧的东西, 能不用C++, 就别用C++…… 如果我早点学python, 并且发现OpenCV其实有python的绑定…… 不知道可以节省多少时间…… 陪gf玩玩什么的…… hawk at 10/12/2010 16:25 那时候因为是在winCE上做widget,没有.NET,所以只能用C++了。。 […]

人工神经网络-ANN

最近SC AI做得差不多了,忽然想到应该写一写关于ANN和GA的科普文章呢,毕竟自己学习只是一部分,跟大家分享也很重要嘛。自己叙述一遍的话,也能考察自己掌握的程度。 ANN, artificial neural network, 即人工神经网络,是机器学习的一种模型。我学习这个其实也是读教科书,用的是卡内基梅隆大学那本machine learning。 所以先说说机器学习吧。机器学习的基本思想就是不通过编程来让计算机完全遵守人指定的死板的流程,而是通过定义一个可学习的模型,之后向这个模型不断添加<问题,答案>这样的对(正式名称是<输入样例,目标输出>),来让计算机通过经验判断下一次接收到问题的时候,应该做出怎样的回答。 其解决方案就是根据每一次的计算机回答和人指定的标准答案进行对照,假如相符,则给予鼓励;假如不相符,则给予批评(即正激励和负激励)。通过不断的训练引导计算机逐渐获得对相关知识的理解。 人工神经网络是机器学习的一个解决方案,即采取仿生的神经元结构来对计算机进行训练。由于人的神经元的复杂性,目前用于计算机研究的神经网络通常采取的是一种简化模型。他令神经元有一个输出和多个输入。神经元通过对所有的输入进行加权求和计算出结果,并以这个结果作为输出(可以想象出来,训练一个神经网络,其实就是训练他使得每一个神经元都得到正确的权值组合)。为了保持简洁性,每个神经元的输入和输出都最好保持在0~1之间。于是这里采取了一个挤压函数,将实数域映射到0~1之间的一个小集合上。通常采用的挤压函数是sigmoid函数,sigmoid(x)=1/(1+exp(-x))。当然也可使用其他有类似特点的函数变体啦。定义好神经元之后,须将神经元根据问题需要构造成神经网络。目前业界通用的较为稳定的神经网络是单向无环的结构。往往采取三层。 第一层是输入层,根据需要,要把问题转换为一个编码,并依次作为输入给各个输入曾神经元赋值。例如,用于人脸识别的神经网络,可采取一个人脸照片的32×32的缩略图作为输入,这样的话就需要1024个输入,每个输入是0~255的像素灰度信息。有比如要从今天的天气情况推算明天的天气情况(当然实际是不可行的。。),可将想要考虑的所有天气特征依次作为输入,并传输给各个神经元。 第二层是隐藏层,它的作用是增加神经网络的复杂度,从而使神经网络可以表达更复杂的函数逻辑。已经证明,任意函数可被三层单馈神经网络(一个输入层,两个隐藏层和一个输出层)以任意精度逼近。但是,更复杂的函数就需要更多的神经单元来表征。由于我们在实现神经网络之前,往往并不能确定问题的复杂度,所以隐藏层采用的神经元数量往往是要靠经验得出的。当然也有一些动态修正的方法可以在训练的过程中增加或减少隐藏层的单元数量。 第三层是输出层,输出单元一般不使用挤压函数处理,而是让他输出线性的数据,以便同实际问题相联系。输出层同样要根据实际问题来编码。例如在人脸识别的应用中,可采取两个输出,一个表示“是人脸”,一个表示“不是人脸”,这里输出还是在0~1之间的。可采取一个阈值来确定真假,例如用>0.7表示真,<0.3表示假,之间是模糊状态。之所以采用两个输出而不是自然想到的一个,是为了稳定性。当两个神经元的输出相符时(例如“是人脸”输出0.9,“不是人脸”输出0.1),可认为模型正确得出结论;而当两个输出不符时(例如均输出0.7),则表示模型无法准确判断。 建立好模型之后就是训练了。这里采取的方法称作“梯度下降的反向传播算法”。之所以称作梯度下降,是说根据人确定的正确答案和计算机通过神经网络给出的答案之间应该会有一个差距。将这个差应用到得出这个结果的输出层上,就能得出输出层的每一个权值应该向哪个方向调整。注意到神经元输出是输入的加权和,所以权值较大的那个分量对于结果的贡献越显著,因此在训练时对他的反馈也应该相应得更明显。数学上采用方差对于权值的函数形成曲面的梯度来描写这个特征。沿着梯度下降到曲面的最小值(有时只能达到局部极小值),就是训练成功了。由于梯度从概念上说是一个无穷小增量,这里只能定义一个较小的“学习速率” η 来作为每次修正权值的增量基准。η取得太大会导致无法达到曲面的最小值(总是越过他),而太小则会导致训练的迭代次数过多,同时也会使得只能达到局部极小值(无法越过局部最小值的谷底)的问题变得严重,因此也有采用变化的η值,例如逐渐减小的η(加快训练速度),又或者带有冲量的η(越过局部最小值的谷底)。这里它的取值变成了一个复杂的研究课题这里不表了。 这就解释了什么叫做“梯度下降”,再来解释反向传播。前面说到根据输出o和标准答案t可以得到一个方差,从而修正输出单元的权值,但如何修正隐藏单元的权值呢(输入单元只有一个输入,因此没有权值也无需训练)?这就是要用到反向传播的地方。既然已经得出了修正后的输出层权值,就又可将输出层的每一个输入(即隐藏层的每一个输出)的实际值和目标值,将修正“反馈”到上一层去。当然仍然需按照每一个权值贡献不同按比例反馈。反馈之后即可得到这层单元的“目标值”了,在用这个目标值在这一层做梯度下降进行训练,这样做一直反馈到输入层为止。 总之假如能够训练使得函数达到最小值,就表示训练成功了。因为它的含义是合适的权值取值,使得模型的输出结果o和标准答案t之间的方差最小。注意由于输出单元往往不止一个所以这里o和t都是向量。方差指的是每一个单元的输出方差再求和。 好吧这些就是理论讲解啦。当然实际应用的时候对于不同的问题会有不同的变形。无论是学习速率,挤压函数,还是权值的梯度下降算法,都可以有这样或那样的改变。这些就是一方面凭经验,另一方面也靠创造性的想象力和“尝试-失败-尝试”的方法来验证啦~ 链接: 维基百科-人工神经网络 http://en.wikipedia.org/wiki/Artificial_neural_network 维基百科-反向传播算法 http://en.wikipedia.org/wiki/Backpropagation 维基百科-梯度下降算法 http://en.wikipedia.org/wiki/Gradient_descent 维基百科-机器学习 http://en.wikipedia.org/wiki/Machine_learning 图书 《机器学习》 http://www.cs.cmu.edu/~tom/mlbook.html

sc ai 估值ANN初步完成,计划作战模块的GA

连续熬了几天夜,SC AI的估值函数神经网络和训练架构终于搭建完成了,现在就是还有一些代码中的小问题需要小修小补一下,然后就是再做一个自动反复启动的程序让他自己跟自己反复对战就行了。不过要自我对战的话,需要借老爸的电脑连成局域网才行。。那之前先让他和电脑AI练练再说吧。。 这部分只做了估值函数,也就是说只是不断预测比赛谁的胜率更大,而没有让他参与到决策之中(所以决策模块仍然是最基本的“勇气值”模型)。这里我为了能够将各个单位的位置信息形成输入放到神经网络中去,花了很多时间。。直接把横纵坐标放进去肯定是没有意义的。需要一些能够更好的刻画战场情形的特征值才能有效的训练神经网络。结果是我没有采用经典的ANN三层模型,而是使用了一种动态更改的模型。 现在我使用最小生成树来刻画战场特征,并将每一个最小生成树的边当作一个输入,这个边是一个复杂输入,包含对方的hp,护盾值,是否处于攻击状态,与自己的距离等信息,对每一个信息,都需要给定一个对应的权值用于训练。因此这个神经网络的神经元就是每个单位。我再将攻击和锁定目标也作为这个神经网络的输入边,来增加刻画战场状态的特征值。为了防止神经网络出现回路,我将神经元复制一遍,分别作为输入层和隐藏层,将前面介绍的最小树边和攻击边由输入层的对应单位连接到隐藏层的目标对应单位。这样做就保证了没有回路。最后我在输出层放了两个神经元,分别代表玩家0的胜利期望和玩家1的胜利期望。最后,由于所有的单位目前都是zealot, 因此他们的特征权值应该是共享的。我参照《机器学习》上介绍的方法,每次反响传播之后将其权值求平均值再一次赋值,使其能够更快的学习和避免过度耦合。 我使用了我自己同电脑对战的一个录像用于训练。首先写了一个解析录像的小程序,将每一帧的特征信息提取出来写入文件中。之后利用另外一个程序依次将这些特征信息进行计算和处理,将简单的坐标信息转换为最小生成树和攻击边等信息。然后将这些信息作为输入来训练神经网络。目前遇到的障碍是在比赛结束之前,无法给出比赛谁胜谁负的准确信息。如果一次比赛只能根据结果训练一次,则训练周期过长,是不可胜任。我采取《涌现》一书中提到的说法,认为根据估值函数求出的估计值,越接近比赛胜利时估计值越为准确。因此可以利用后面一帧的估值作为前面一帧估值的参照量,并依此进行反向传播。为了能够得到更快的训练速度,我设置当单位数量超过敌军,或单位数量相等而总血量大于敌军时,就认为本方处于优胜状态。这或许并不完全准确但已经是非常保守的估计了。我根据书中提到的标准,设置0.9为优胜,0.1为失败(前述神经网络中所有输出均通过sigmoid函数挤压到(0,1)区间)。至少在昨晚的几次实验中,这套方案得到了较好的成效,接下来的就是要继续训练他直到稳定为止了。为此我还需要再做更多录像,然后就是要想办法让他自己跟自己对战了。 接下来要做的就是决策部分了。这部分我准备使用GA, 即遗传编程。可以根据士兵处于不同情形时(危险/安全,接敌/后方,被包围/被保护,是否接触边界等等)分别设定不同的行为(攻击,攻击移动,移动,原地不动等等),然后通过遗传编程来找到最好的组合。当然好与不好的估值,则通过前述神经网络得出。 现在最愁的一部分就是如何决策移动。因为移动是一个几乎是非离散的量。不可能去考虑地图上的全部点。一定要给出合适的特征值来刻画好的和不好的移动目标。这包括了是否被包围,是否阻碍了友军等等。然而这样的特征值仍然没有找到。前面提到的最小生成树似乎有些意义,但对整体有意义的东西用在局部上有些困难。目前还在思考对策。。。

SC AI设计的强力纠错

昨天熬了一夜之后,在非常兴奋以及脑袋糊掉的状态下写了最近的工作进展和思路。。可惜大多数都是语无伦次。。 今天在仔细读过之后,发现,大多数的想法,都是在写前面几个段落的时候和快要写完的时候不一样,结果导致前后很多矛盾,再加上使用了很多似是而非的术语,让整篇文章几乎没有说对的地方。。 这里也不可能把所有的毛病都改掉了,不过也好上一篇文章成了只有我自己才能看懂了胡言乱语。。。 先说说神经网络吧。上一篇文章多次提到神经网络,其实是指的几个不同的东西。并且这几处都没有给出神经网络的构造。而真正给出构造的一处,即采取各单位相连以广播行为等的那个构造,其实不是神经网络,最多只能说是一个参考神经网络而设计的通信模型。在Holland的一本叫做emergence的书中曾经提到过一种称之为元胞结构的构造,可能这个设计更近似于那个构造,但也还是有很多不同之处。应该说这是一个实验性的构造,也只是我的一时想象,暂时不能说他能够给AI设计起多大的帮助。 而至于使用神经网络结构来学习几项重要的特征,比如是否被封闭(能否逃离),目标健康程度能否在一击内消灭(计算护甲、hp、shield等),同理也可用上述原理计算自身是否安全。这些特征采用神经网络学习是有可能的。神经网络是一个相对静态的结构,必须用于学习能直接得到结论的结果。当然这里我说的神经网络是指没有环路的单馈三层神经网络了。这是一种成熟的技术,可以在AI学习中有很多应用。但也正是这个原因,使得他无法应用于博弈模型这样的无法立即得到反馈的机器学习中来。 昨天文章中说到的“估值函数”也是笔误,其实我想说的只是找到了几个重要的特征值,而没有希望直接设计估值函数。其实我昨天的想法是,通过设置神经网络或者类似于神经网络的其他模型,只要找到了估值特征值,令模型自行学习权值,则估值函数可以通过机器学习得到。这点也是昨天没有说清楚的。。 总之目前的状态是初步的想法有了,但是很多具体细节还没有想清楚。并且前面提到的最重要的部分,也就是类似于“元胞结构”的部分,还有很多没有明确定义的东西。这些地方还需要继续想清楚。 以上

SC AI 神经网络模型和遗传编程

今天wp升级,手欠顺便升级了一下theme,结果忘记备份导致原先的更改全部消失,又重新折腾了好久。bo的外观稍稍有点变。。 昨天由于一整天没有干正事,导致晚上相当悲剧。。熬了一整夜,不过 SC AI的神经网络模型基本上有了框架了。接下来就可以根据各种YY往里面增加参数、估值函数和各种加权了。 目前仍然以考虑zealot为主,不过我发现对zealot适用的模型,对dragoon同样适用,只是需要让他重新适应一次估值函数的权值就可以了。因此这里还是继续仅讨论zealot。首先,确定每个单位拥有进攻和溃逃两套互不相干的策略机,然后给定一个决定是进攻还是溃逃的决策机制,就可以了。 这个决策机制我称之为勇气。当估值函数超过阈值的时候,认为这个单位士气高涨,会继续进攻,而当估值函数低于阈值的时候,这个单位士气低落,会决定溃逃。如果以zealot的攻击范围为单位,将zealot周围区域分成8个方格,则可将每个方格内是否有敌军或友军单位,作为一个神经元输入,更远的敌军或友军单位,通过更多的神经元相连间接得到,任何单位决定进攻任何目标或溃逃都需要作为一个信号向外部发送并引起这个神经网络内的其他神经元的策略改变。参考神经网络模型的疲劳机制,当单位持续士气高涨的时候,会将阈值按照一定的因子提高,使之勇气下降,同理,当单位持续溃逃的时候,会将阈值相应降低,使之变得较为容易参战。这个可变的阈值,可称为单位的勇气。 勇气的估值参数主要有如下几点:自身hp和shield,正在攻击自己的敌对单位数量(以及他们的被攻击情况和健康情况),自己正在攻击的敌对单位hp和shield。考虑这些的目的主要是为了估算自己能否在生存情况下消灭正在攻击的敌人。当然这个逻辑我不准备放入估值函数中,而令其通过神经网络训练学习得到。通过给定不同的加权估值,经过训练应该能得到和人思考出的相似的结论。 假如勇气决策为进攻,则选取攻击决策机,并令其给出一个攻击指令。攻击指令可以是:攻击最近的敌人,攻击hp和shield按照某种权值计算后健康程度最差的敌人(这和需要几次攻击才能消灭敌人有关系,需要折算护甲,攻击类型和目标体积的关系等复杂内容,例如Dragoon拥有20的damage,可是攻击被打光shield的zealot时一次攻击只能造成9hp左右的伤害,这是因为dragoon的爆炸攻击类型对zealot的小型单位只能造成一半伤害,而同时未升防御的zealot拥有1的armor,会抵消10%左右的伤害),攻击盟友正在攻击的敌人,攻击威胁最高的敌人,以及保持目前攻击目标不变。而得到这个攻击指令的效果,又可以采用:攻击单位命令,移动攻击命令,巡逻命令,移动/待命等命令来实现。因此想要使用一个模型来模拟全部的可能性,实在不可能。这里必须采用遗传编程的方式,令不同的策略模型在竞争中互相杂交和进化,最后得到较优的结果。 溃逃机制主要需要考虑的是两种特殊情况,即被友军封闭和被敌军封闭。假如溃逃单位被友军封闭,最好的策略是能够通过该单位向四周发送一条信号,而使合适的单位为其让路。这个信号同样可以用于保持阵型,即“最佳防御位置”的确定。而假如溃逃单位被敌军封闭,则应该立刻变为英勇,因为无论如何也逃不出去了,应该给敌人以最后的伤害。但如何确定某单位是否被封闭了?BWAPI似乎提供了函数,但我暂时还没有测试。否则使用周围单位的位置和权值,让神经网络自己去学习也是可行之道,不过似乎大材小用了…… 以上就是最近一段时间测试和思考的内容。另外经过很多测试,对BWAPI和星际争霸游戏的各种特点也慢慢熟悉了,相信对接下来的开发会有帮助吧……