代码之家  ›  专栏  ›  技术社区  ›  devoured elysium

如何最好地解决未知函数形式的确定问题

  •  2
  • devoured elysium  · 技术社区  · 14 年前

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

    我在这个问题上的第一个突破是假设我可以建模 f 作为线性函数:

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

    我的第一个想法是使用粒子群优化(PSO)或遗传算法来解决 f 对于 a, b, .., c 我相信他们一定会有好的结果。

    另一方面,我觉得也许不需要这种进化算法。首先,我可以想出几个好的“起点” a,b, .., c . 存在 f 一个线性函数,是不是应该更容易尝试几个点,然后对它们进行线性回归?在线性回归之后,再尝试几个点,这次更接近于一个好的“点”,再次对它们进行线性回归?

    它的缺点是什么?有没有人在这些问题上有经验?我能想到的最大的一个可能就是我认为良好的开始价值观 A,B,C,C 可能是一个“局部最优”,有某种进化算法会给我一个全局最优。

    f 如果重要的话,应该是象棋类游戏的极大极小算法的近似函数。

    谢谢

    3 回复  |  直到 14 年前
        1
  •  3
  •   fairidox    14 年前

    你描述的是一个回归问题,这是一个典型的机器学习问题。有成千上万的科学论文和整本教科书只写这个主题。我建议在网上看一些机器学习课程,或者去看看 standard machine learning text .

    一般的方法类似于您所提到的,求解变量的线性系数以最小化一些损失,通常是平方误差之和(l2损失)。这是可取的,因为它是一个凸函数,因此包含一个最小值,权重可以在多项式时间内求解。但是,正如您提到的,真正的函数可能不在这个函数类中,并且您的估计很差。这种情况下的方法是 尝试用一些模糊粒子群方法或遗传算法或其他全局优化技术进行非凸优化。你的陈述“…可能是一个“局部最优”,有某种进化算法会给我一个全局最优。全局优化是NP困难的,这些技术只是近似的,对运行时间和最优性没有绝对的保证,而且几乎不起作用。

    一种更为普遍的方法是使用“功能扩展”,它接受变量 X, Y, ..., Z 并将非线性变换应用于一些新的集合 phi(X), phi(Y), ..., phi(Z) . 此时,您可以使用最小二乘法(如果使用l2)或其他方法为每个特征找到最佳线性加权。如何找到好的特性是机器学习中的一个开放性问题,但是有大量的想法和免费可用的算法可以做到这一点。

        2
  •  1
  •   Fred Foo    14 年前

    考虑到你正在做一个游戏,首先想到的是一个古老的跳棋程序,它是由 Arthur Samuel 在20世纪50年代 Russell and Norvig 在他们关于游戏的章节中(其中,它仍然是无监督/半监督机器学习的经典之作)。

    该程序假定棋盘格的值是棋盘位置的线性函数。我不知道细节,但我假设每个玩家的棋子值+1,对手的棋子值-1,空的区域值0。每个方块都有一个与之相关联的权重,这是通过让程序对自己进行若干次(大量)的比赛来学习的,每次比赛后对比赛进行评估。

    这种策略被称为自我训练,也被应用于经典的双陆棋软件中。 TD-Gammon 基于神经网络(多层/非线性网络)。关于这个程序的维基百科页面有一些潜在的有趣的参考资料。

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

        3
  •  1
  •   Nick Larsen    14 年前

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

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