2

我有一组变量X, Y, ..., Z。我的工作是设计一个函数,它采用这组变量并产生一个整数。我有一个健身功能来测试这个。

我对这个问题的第一次尝试是假设我可以建模f为一个线性函数:

f(X, Y, ..., Z) -> aX + bY ... cZ

我的第一个想法是使用 PSO(粒子群优化)或遗传算法来解决问题fa, b, .., c我相信它们肯定会产生良好的结果。

另一方面,我觉得也许真的不需要那种进化算法。首先,我可以为a,b, .., c. 作为f一个线性函数,尝试几个点然后对它们进行线性回归之类的事情不是更容易吗?在线性回归之后,尝试更多点,这一次更接近看起来像一个好的“点”,再次对它们进行线性回归?

它有什么缺点?任何有此类问题经验的人?我能想到的最大的一个可能是,我认为好的起始值a,b, .., c可能是“局部最优”,并且拥有某种进化算法会给我一个全局算法。

f如果重要的话,应该是类似国际象棋游戏的 Minimax 算法的近似函数。

谢谢

4

3 回答 3

3

您正在描述一个回归问题,这是一个经典的机器学习问题。有数以千计的科学论文和整本教科书都是关于这个主题的。我建议在线查看一些机器学习课程或查看标准机器学习文本

一般方法与您提到的类似,求解变量的线性系数以最小化一些损失,通常是平方误差之和(L2 损失)。这是可取的,因为它是一个凸函数,因此包含一个最小值,并且可以在多项式时间内求解权重。但是,就像你提到的那样,真正的函数可能不在这个函数类中,你的估计会很差。在这种情况下的方法不是尝试使用一些晦涩的粒子群方法或遗传算法或任何其他全局优化技术进行某种非凸优化。你的陈述“......可能是一个“局部最优”,并且拥有某种进化算法会给我一个全局算法。” 是一个天真的。全局优化是 NP-Hard 的,这些技术只是近似值,绝对不能保证运行时间或最优性,而且它们几乎从不工作。

一个更被接受的方法是使用“特征扩展”,它采用你的变量X, Y, ..., Z并将非线性变换应用于一些新的 set phi(X), phi(Y), ..., phi(Z)。此时,您可以使用最小二乘法(如果您使用 L2)或其他方式为每个特征找到最佳线性权重。如何找到好的特征是机器学习中的一个悬而未决的问题,但是有很多想法和免费可用的算法可以做到这一点。

于 2010-10-15T22:26:18.480 回答
1

考虑到您正在开发一款游戏,首先想到的是一个古老的跳棋程序,由Arthur Samuel在 1950 年代开发, Russell 和 Norvig在他们关于游戏的章节中提到(除其他外;它仍然无监督/半监督机器学习的经典之作)。

该程序假设棋盘的价值是棋盘位置的线性函数。我不知道细节,但我假设每个玩家的棋子值 +1,对手的棋子值 -1,空域为 0。每个方格都有一个与之相关的权重,这是通过让程序对战来学习的本身一些(大量)次数,在每场比赛后评估比赛。

这种策略被称为自我训练,也被应用在经典的步步高软件TD-Gammon中,该软件基于神经网络(多层/非线性)。关于该程序的 Wikipedia 页面有一些潜在的有趣参考。

这个答案正在变成一篇关于我不是专家的文章。请参阅相关文献。

于 2010-10-15T17:33:16.513 回答
1

如果我理解你的问题,你有一个接受输入的函数,然后提供一些输出,这应该与类似国际象棋的游戏的近似函数有关,你应该猜测它是如何计算输出的。

您没有说明输入变量是什么,所以我无法说出每个变量的域是什么,但一般策略是保持所有输入相同,并迭代域中的所有值一个变量。对所有输入重复并使用生成的数据集来指导您的下一组测试。该函数使用的实际方法很可能是绝对愚蠢的,如果不将每个输入映射到每个输出,就无法合理地重现。

于 2010-10-15T21:30:14.157 回答