65.9K
CodeProject 正在变化。 阅读更多。
Home

适用于 .NET Framework 的计算机代数系统

Igor S Medvedev
starIconstarIconstarIconstarIconstarIcon

5.00/5 (28投票s)

2013年6月10日

GPL3

9分钟阅读

viewsIcon

62328

downloadIcon

3491

本文介绍了一个用于符号计算的 C# 库。

Differentiation sample

引言

计算机代数系统 (CAS) 是一种用于符号数学处理的软件程序。CAS 的核心功能是以符号形式操作数学表达式。通常，为了执行此类操作，原始数据被表示为语法树，然后使用某些规则对其进行转换。本项目的主要目标是提供一种灵活且便捷的方式来指定此类转换规则。

许多 CAS 系统要么是小型研究项目，要么是企业软件。然而，没有一个是在 .NET Framework 中实现的，这是一个现代编程技术，广泛用于研究、教育和软件开发。据我们所知，目前只有一个 .NET 解决方案，名为 Math.NET。但是，它很难被认为是一个功能齐全的计算机代数系统。转换规则不像一个独立的实体那样编程，而是被处理树节点（根据其功能）的 Visitor 模式所取代。这个决定阻碍了系统的扩展，因为添加新操作需要修改现有代码。此外，即使是指数函数求导等操作仍未实现。

为了开发计算机代数系统，我们需要构建一个方便可靠的规则定义和应用框架。此类框架是所有现有 CAS 的核心部分。在这项工作中，我们基于 .NET Framework 提出了我们针对此任务的解决方案。我们无意编写企业级的计算机代数软件，因为市场上已经有很多解决方案。然而，我们相信我们的解决方案在研究领域会很有用，因为它提供了一个机会，可以使用现代高效的编程语言进行符号计算。此外，正如我们下面将看到的，.NET Framework 和 C# 语言提供了多种语法特性，有助于定义转换规则。使用这些特性来编写转换规则为符号计算带来了新的视角，并可能产生计算机代数系统的新方法。

规则定义

规则的应用可细分为三个阶段。在采样阶段，应用规则的系统（以下称为驱动程序）从语法树中选择一个树状结构，并将其节点表示为元组。在选择阶段，驱动程序会剔除不符合指定标准的元组。在第三个阶段，称为修改，驱动程序根据规则转换树。在最常见的情况下，规则处理一棵树。对于这种一元规则，会复制原始树，然后根据规则重新排列副本。在某些情况下，规则处理多棵树。例如，在逻辑推理的 modus ponens 规则中，它接受两棵树A → B和A并产生B。在这种情况下，需要创建一个新树，并使用从所选元组复制的节点来构建它。由于驱动程序在操作前总是复制节点，因此保留了初始树的正确性。

采样

为了执行采样阶段，我们需要指定我们在树中搜索的树状结构。此外，我们需要将结构中的节点映射到节点元组。我们为此使用了我们自己语法的查询字符串。让我们通过以下示例来演示查询字符串的语法。考虑图 1 中的语法树。在表 1 中，我们展示了各种查询字符串以及相应的选择和注释。

Syntax tree

图 1：语法树
表 1：查询字符串示例
查询字符串 元组 注释
A (1) 树的根节点
?A (1),(2),(3),(4),(5),(6) 树中的任意节点
?A(B) (5,6) 任意节点，只有一个子节点，即该子节点
?A(B,C) (1,2,5), (2,3,4) 树中具有两个子节点的任意节点，子节点顺序固定
?A(.B,.C) (1,2,5), (1,5,2), (2,3,4), (2,4,3) 具有两个子节点的任意节点，子节点顺序不固定
?A(.B) (1,2), (2,3), (2,4), (5,6) 具有一个子节点的任意节点
?A(?B) (1,2), (1,3), (1,4), (1,5), (1,6), (2,3), (2,4), (5,6) 具有任意后代的任意节点
?A(?B(?C)) (1,2,3), (1,2,4), (1,5,6) 任意节点、其后代以及后代的后代
?A(?B(C,D)) (1,2,3,4) 具有两个子节点的后代的任意节点

采样算法是一种深度搜索算法，它在给定树和查询字符串的解析树之间建立对应关系。为了编码规则，我们应该在程序中指定查询字符串。这可以通过将查询编码为常量字符串来实现。然而，由于查询语法中可能出现错误，例如括号不匹配或字母不正确，因此这样做并不方便。为了消除这些错误，我们通过方括号覆盖实现了查询字符串的定义。因此，现在您可以使用以下语法来编码规则：

Select(AnyA[ChildB, ChildC]);

选择

选择阶段可以进一步细分为类型选择和自定义选择。类型选择检查所选元组中节点的类型，并在类型不匹配时拒绝该元组。自定义选择可以检查附加条件，例如常数的值。类型选择必须在自定义选择之前执行，因为自定义选择的可能性取决于节点的类型。例如，要检查常数的值是否为零，我们必须确保该节点对应的是一个常数，而不是一个运算符。

在编程选择时，如何将元组提供给选择条件出现了一个挑战。我们不能将选定的节点存储在数组或列表结构中，因为这样无法为元素指定不同的类型。使用数组表示，选择只能像这样执行：

( array => array[0] is Plus && array[1] is Constant && (array[1] as Constant).Value==0 );

当然，常量转换和寻址是潜在的类型错误源。我们开发了一种使用泛型方法和代码生成的优雅解决方案来进行选择。此功能由 Rule.SelectWhere 方法响应，该方法接受 INode 数组，生成 IEnumerable<SelectOutput> 并将此枚举传递给类型为 Func<SelectOutput,WhereOutput> 的委托 where。此委托验证元组是否与过滤器匹配，并生成与已过滤元组对应的 WhereOutput 对象。

修改

当选择阶段结束后，我们会得到几个可以进行修改阶段修改的元组。但是，实际上只有一个元组将被处理，因为规则的应用可能会使其他元组失效。因此，修改阶段只处理选定的元组之一。我们开发了一种“干净”的修改方法，它不会影响初始树。相反，在修改阶段，我们复制所选树，然后在副本上执行修改。为此，我们必须找到给定元组中存在的节点的根，克隆它们，然后进一步处理包含相应节点副本的新元组。

此功能由 Rule.Apply 方法响应，该方法接受 WhereOutput 对象。然后，它通过 WhereOutput.MakeSafe 方法复制此对象，并将其副本传递给委托 apply，在其中执行修改。

创建新规则

完整的规则定义如下：

Rule
    .New("+0", StdTags.Algebraic, StdTags.Simplification, StdTags.SafeResection)
    .Select(AnyA[ChildB, ChildC])
    .Where<Arithmetic.Plus<double>, Constant<double>, INode>(z => z.B.Value == 0)
    .Mod(z => z.A.Replace(z.C.Node));

此规则查找子树X+0或0+X，并将其替换为X。我们已经定义了几组规则来实现一些功能，接下来我们将告诉您目前为止您可以使用该系统具体做什么。

简化和微分

您可以在 AlgebraicRules 和 DifferentiationRules 类中分别找到用于简化和微分的规则。要使用现有规则简化表达式，请像这样使用 ComputerAlgebra.Simplify 方法：

Expression<del4 /> expression = (x, y, z, u) => (x+42)/1 + y*0/(z-0) + 43 - Math.Pow(x, 0) * Math.Pow(u, 1)/(0+5);
// x+85 - u/5
var result = ComputerAlgebra.Simplify(expression);

要查找函数的偏导数，请使用 ComputerAlgebra.Differentiate 方法：

Expression<del3 /> function = (x, y, z) => Math.Pow(x, 3)*y - Math.Pow(x, y)+5*z;
// 5
var result = ComputerAlgebra.Differentiate(function, variable: "z");

在这里，您必须定义微分变量。在我们的例子中，它是z。

您可以在 SimplificationDemo、DifferentiateDemo 项目以及 SimpleTests、DifferentiationTest 的测试类中找到这些功能的示例。

回归

我们研究的第一个目标是符号回归任务，在那里我们使用简化规则来改进进化符号计算的现有解决方案。在符号回归中，遗传算法通过变异和交叉处理表达式，并逐渐创建符合实验数据的表达式。表达式中的常量也通过变异找到。我们用标准公知的数值回归改进了算法的这一部分。假设算法找到了函数F(x1,...,xn)作为潜在解决方案。令Φ(x1,...,xn,c1,...,cm)为函数F，其中常量被替换为参数ci。令E(c1,...,cm)为误差函数：

Error function

其中集合 实验数据 是实验数据。通过微分规则，我们可以计算 偏导数 并使用梯度下降法改进ci，以便Φ更好地拟合实验数据。该技术已通过实验测试，并证明比通过遗传算法寻找常量更优。

我们决定将进化算法和符号计算分开，因此现在您可以独立于遗传算法使用数值回归。为此，您应该创建 RegressionAlgorithm 类的新实例并调用 Run() 方法。RegressionAlgorithm 的构造函数接受表达式、实验数据、精度和梯度下降的初始步长。您可以在 RegressionDemo 项目和 RegressionTests 类中找到这些示例。

分辨率

分辨率技术非常简单：

  1. 找到包含相同谓词的两个子句，其中一个子句中的谓词被否定，而另一个子句中的谓词未被否定。
  2. 对这两个谓词执行统一。(如果统一失败，则表明您选择了错误的谓词。返回上一步并重试。)
  3. 如果未绑定的变量（在统一的谓词中已绑定）也出现在两个子句的其他谓词中，则将它们替换为在这些谓词中的绑定值（项）。
  4. 丢弃统一的谓词，并将两个子句中剩余的谓词组合成一个新子句，同样由∨运算符连接。

所有谓词都必须采用 Skolem 标准型，因此我们需要一种工具来定义此类谓词的无量词部分。为此，我们生成了几个方法和常量。因此，我们现在可以定义如下形式的公式：

Expression<del2> clause = (x, y) => P(a, x, f(g(y))) | !Q(x) | R(b);

统一算法实现在 UnificationService 类中。它非常简单，我们在此不详细描述。

该技术的主要部分，即分辨率规则，作为该系统的标准规则实现：

Rule
    .New("Resolve", StdTags.Inductive, StdTags.Logic, StdTags.SafeResection)
    .Select(A[ChildB], C[ChildD])
    .Where<Logic.MultipleOr, SkolemPredicateNode, Logic.MultipleOr, 
      SkolemPredicateNode>(z => UnificationService.CanUnificate(z.B, z.D) && 
      (z.B.IsNegate || z.D.IsNegate))
    .Mod(Modificator);

其中 Modificator 方法对两个谓词执行统一，并将两个子句中剩余的谓词组合成一个新子句。

要获取两个谓词的可能解析列表，您必须像这样使用 ComputerAlgebra.Resolve 方法：

Expression<del1 /> node1 = (x) => P(x) | !Q(x);
Expression<del1 /> node2 = (x) => !P(x) | Q(x);
// [!Q(x) ∨ Q(x); P(x) ∨ !P(x)] 
var result = ComputerAlgebra.Resolve(Expressions2LogicTree.Parse(node1), 
             Expressions2LogicTree.Parse(node2));

像往常一样，您可以在 ResolutionDemo 项目和 ResolutionTests 测试类中找到示例。

进一步发展

本项目完全是研究性的：所有进一步的开发将由下一代学生进行。如果他们取得了有趣的结果，他们一定会写一篇新文章。

如果您觉得这个主题很有趣，我们很乐意您将我们的系统用于您自己的研究。 

历史 

  • 2013 年 6 月 9 日 - 原版本发布。 
© . All rights reserved.